决策会改变未来机会
局部看来诱人的奖励未必是最佳选择,因为行动也会改变下一个状态。无限时域折扣马尔可夫(Markov)决策过程明确表达这项取舍。本节研究有限且已知的模型并最大化期望奖励;这是在已知模型下规划,不声称模型已从数据学得。
定义 10.1.1
(折扣马尔可夫决策过程)
令 为有限非空状态集。每个状态 有有限非空行动集 。选择 时取得有限确定奖励 ,再以概率 转移至 ,这些概率非负且总和为一。模型不随时间改变,且在给定当前状态与行动后,下一状态分布与更早历史独立。取折扣因子 。状态—行动对只有有限个,因此奖励有界;每条轨迹的折扣回报 均绝对收敛;即使 也约定 。策略可依赖已观察历史,也可随机化;平稳确定性策略则在每个状态选一个固定行动。对起始状态 ,以 表示策略 的期望折扣回报,并设 。
定义 10.1.2
(Bellman 算子与价值迭代)
对以 为索引的实数向量,定义 Bellman 算子:
最大化在期望之外:行动在抽取下一状态之前选定。有限行动集保证存在达到最大值的行动。价值迭代可由任意有限向量 开始,反复令 。
迭代为何收敛
定理 10.1.3
(Bellman 算子的压缩性)
对任何以 为索引的实向量 ,都有 。
证明
(最大值不放大差距,概率则取平均)
对向量 ,写 。两个有限数列最大值之差的绝对值,不大于逐项差的最大绝对值。应用此不等式,并利用概率非负且总和为一,得
此式对每个状态都成立。因此 。
定理 10.1.4
(价值迭代收敛至唯一不动点)
对任意起始向量 ,迭代 在 下收敛至满足 的向量 。它是 的唯一不动点,且 。
证明
(等比差值给出柯西(Cauchy)序列)
压缩性使相邻差值按等比速度下降:。由等比级数的尾和, 在有限维上确界范数中是柯西序列,故收敛至某个 。同一不等式给出算子连续性,所以 。若也有 ,则 ,迫使两向量相等。不动点唯一。
概念视角算法
每个迭代向量都是有限步长的最优值
从 出发,向量 是从 出发的 步计划中, 的最大期望值:每次 Bellman 更新都在最前面多加一个决策。在两状态表中, 是最佳的两步奖励,连续停留两次和先移动再在 收取奖励都能达到。这也解释了因子 :第 步之后的部分以 加权。
定理 10.1.5
(不动点就是最优价值)
设 为 的不动点。对每个起始状态 都有 ,即使容许依赖历史的随机化策略也是如此。此外,在每个状态选取使 达到最大值的行动,便定义出一个平稳确定性策略 ,且 。
证明
(以 N 步把每个策略与不动点比较)
由于 不小于任何行动的 Bellman 表达式,先对已观察历史及所选行动取条件期望。马尔可夫性使下一状态期望等于所指定的概率加权和;对任意随机行动再取平均仍保持不等式。反复运用 步,对每个策略 得
因 有界,最后一项趋近零;若 ,奖励尾和的绝对值最多为 。因此没有策略可得到更大回报,即 。在每个状态依精确向量 选取达最大值的行动,并使用该平稳策略:每步不等式均成等式,因此这个平稳确定性策略达到 ,故 。
证明透视
最优性证明中每项假设用在哪里
不易想到的一步,是不把任意策略与未知的最优回报比较,而是与不动点 比较,并在时刻 截断,把 当作终端奖励。每个成分各有作用。不动点方程 提供单步不等式:对每个行动 , 不小于 。马尔可夫性使这个不等式可在任何已观察历史之后应用,所以依赖历史与随机化都不会带来额外好处。 与 有限使 和奖励有界,而 使 与奖励尾和在 时消失。论证能够闭合,是因为对贪心平稳策略,链中每个不等式都成为等式,所以这个策略达到其他策略只能从下方逼近的上界。若没有 ,终端项不一定消失,与 的比较便无法说明无限和。
可计算的停止证书
命题 10.1.6
(残差误差界)
对任何以 为索引的实向量 ,令 ,则
证明
(三角不等式加压缩性)
三角不等式与压缩性给出 ,其中用到 。把最后一项移到左边,得 ,而 ,故可两边除以它。
小残差证明价值向量在上确界范数下接近;它本身不能在近似行动价值接近时确定最优行动,也不表示模型精确反映真实环境。
常见错误
(残差并不等于误差)
当 接近 时,若因相邻两次迭代只差 便把 当作误差,是错误的。取一个状态、一个行动、奖励 及 ,则 。数值 的误差是 ,但 ,残差只有 。此处误差恰好等于 ,所以因子 不能省去。
例题
例题 10.1.7
(带有并列的两状态例子)
有两个状态 ,且 。在 ,停留给奖励 1 并返回 ;移动给奖励 0 并移至 。在 唯一行动给奖励 3 并返回 。这些确定性转移是概率模型的特例。Bellman 方程为
从 开始,顺序为 :
| 迭代次数 | 以前一行计算时在 的最大化行动 | ||
|---|---|---|---|
| 0 | 0 | 0 | 无 |
| 1 | 1 | 3 | 停留 |
| 2 | 并列 | ||
| 3 | 移动 |
不动点的 方程给出 。在 ,移动得到 3;若 ,停留得到 ,所以移动严格较好。向量 满足两式,故是唯一不动点。第 2 次迭代的并列是用 比较行动,并非使用最终价值;它不代表最优策略并列。
例如 的残差是 ,故误差上界为 。此例的实际上确界误差也恰为 。
常见错误
(迭代向量中的并列不代表最优值中的并列)
从中间向量读出贪心行动,可能选到次优行动。在上面的例题中, 使 处的停留与移动并列(两者都给 )。但依 ,停留只值 ,移动值 ,所以只有移动是最优的。应由 取出策略,或由证书足以分开各行动的迭代向量取出。
例题 10.1.8
(随机转移)
令 。在 ,唯一行动给奖励 4 并返回 。在 ,稳妥给奖励 1 并返回 ;冒险给奖励 0,并各以概率 移至 或 。于是
的方程给出 。检验向量 :稳妥的表达式是 ,冒险的表达式是 ,所以 ,而 。此向量是不动点,因此就是唯一的 ,且 处的最优行动是冒险。
再取 ,这是永远选稳妥的策略的价值。此时 ,,故 ,证书给出误差至多为 。真正误差是 ,落在证书范围内。残差为正,反映永远稳妥并非最优:在 冒险严格更好。
例题 10.1.9
(完全不重视未来的边界情形)
沿用同一模型,但取 。算子变成:对任何 都有 ,,所以不论 为何,,且 。因此 , 处的最优行动是稳妥。当 时,同一模型偏好冒险,因为 使到达 的机会计入价值。两者对比显示,折扣因子决定如何在眼前奖励与日后机会之间取舍。
限制与练习
上述收敛论证需要折扣和有界奖励。若令 ,便失去压缩保证,而无折扣无限和可能发散;平均奖励或有限时域问题需要各自的条件。转移不确定性由所指定概率处理,但概率与奖励的模型误差需另行分析。
反例模式
取消折扣会破坏唯一性与存在性
声称“对每个 ,算子 都有唯一不动点,且价值迭代收敛到它”,在 时并不成立。取一个状态、一个行动、奖励 。此时对每个实数 都有 ,所以每个数都是不动点:由 出发的迭代停在 ,由 出发的则停在 ,唯一性失效。现在把奖励改为 ,则 没有不动点,而 发散,与无折扣和 发散一致。修补方法就是原有假设 (或改用有限时域、平均奖励等其他框架)。
快速检查
(在例题中计算 ,再多做一次 Bellman 更新以计算其残差。用来计算 的 行动是否并列?)
解答 · 答案
用 : 处停留的表达式是 ,移动的表达式是 ,所以 ,移动严格更好,并无并列。又 。再更新一次得 ,所以 的残差是 。证书把误差限制在 内,而实际误差 与之吻合。
快速检查
(若 ,Bellman 算子返回什么?需要多少次更新才到达不动点?)
解答 · 答案
当 ,对任何 都有 ,输出与输入无关。从任何 出发,更新一次已得 ,第二次更新不再改变它。最优策略是短视的:选即时奖励最大的行动。
快速检查
(考虑另一个单步问题:共同外生随机结果独立于行动,每个行动—结果组合的收益均已指定。给一个两种结果的例子,使先观察结果再选行动能提高期望收益。解释此信息顺序为何不同于先选行动。)
解答 · 答案
设结果为 或 ,概率各为 。行动 在 时给 1、在 时给 0;行动 在 时给 0、在 时给 1。先选行动时,每个行动的期望收益都是 。先观察结果则可在 后选 、在 后选 ,必得 1。前一种顺序计算的是 ,后一种是 。Bellman 算子中,行动在抽取下一状态之前选定,属于前一种顺序。原 MDP 中依行动而变的转移概率本身并未指定所有行动的共同联合结果。
练习 10.1.10
(证明:对实数 与 ,有 。这就是压缩性证明中用到的不等式。)
基础证明
提示(1)
选一个使 达到最大值的下标,再与 的同一项比较。
解答(3)
- 1
先证一个方向
关键一步
令 ,并选 使 。由于 ,得 。
依据: 的最大值不小于它的第 项 。
- 2
交换两个数列的角色
把 与 对调,同一论证给出 。
- 3
合并两个方向
∎与它的相反数都不大于 ,所以 。