迭代策略评估 | Codeboy's Blog

形式陈述

给定有限折扣 MDP 和固定平稳马尔可夫策略 $\pi$ ，迭代策略评估从任意有界 $v_0$ 出发，执行

v_{k+1}(s)=\sum_a\pi(a\mid s) \left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)v_k(s')\right] =(T^\pi v_k)(s).

由Bellman 期望算子的 $\gamma$ -压缩性，

\|v_k-v_\pi\|_\infty \le\gamma^k\|v_0-v_\pi\|_\infty.

若 $|r_\pi(s)|\le R_{\max}$ 且 $v_0=0$ ，右侧可进一步界为 $\gamma^kR_{\max}/(1-\gamma)$ 。

实际计算更常用可观测的连续迭代差。由 $v_k-v_\pi=(v_k-v_{k+1})+(T^\pi v_k-T^\pi v_\pi)$ ，得到

\|v_k-v_\pi\|_\infty \le\frac{\|v_{k+1}-v_k\|_\infty}{1-\gamma}.

因此给定容差 $\varepsilon>0$ ，当更新差不超过 $(1-\gamma)\varepsilon$ 时，返回 $v_k$ 就有所需证书；返回刚算出的 $v_{k+1}$ 也安全，因为其误差至多为前者的 $\gamma$ 倍。压缩性使更新差趋零，因而该正容差规则有限步停止； $\gamma=0$ 时一次更新已得到精确值。只检查某几个常访问状态不能给全状态 sup-norm 证书。

设状态数为 $n$ ，且 $P_\pi,r_\pi$ 已预先算好。按单位成本算术计，同步一轮的稠密扫描为 $O(n^2)$ ；稀疏表示仅存非零项时为 $O(\operatorname{nnz}(P_\pi)+n)$ ，两个价值向量占 $O(n)$ 额外空间，不含模型存储。初始化需 $O(n)$ 工作， $K$ 轮将单轮扫描成本乘以 $K$ 。对零初值、 $\varepsilon>0$ 和 $0<\gamma<1$ ，取满足 $\gamma^K R_{\max}/(1-\gamma)\le\varepsilon$ 的非负整数 $K$ 即足够； $\gamma=0$ 时一次更新精确完成。模型构造与有限精度位成本另计，上述误差证书按精确算术成立。

同步版本用完整的旧向量 $v_k$ 计算所有新分量；原地 Gauss–Seidel 更新会立刻使用刚算出的分量。后者常更快，但收敛证明需要每个状态持续被更新并保留适当的异步迭代条件。

直觉

第一次更新只看一步奖励，第二次把一步后的估计接上，经过 $k$ 次后信息大致传播了 $k$ 步。算法无需枚举整条轨迹；每轮把上一轮“余生值”接到当前一步后面。折扣使更远处的信息影响越来越弱，所以有限次传播能逼近无限时域。

它与直接求解 $(I-\gamma P_\pi)v=r_\pi$ 得到同一个答案。线性求解一次性利用全局代数结构，迭代法则只需反复做矩阵—向量乘法，适合稀疏大系统；哪一个更省取决于状态数、稀疏性和所需精度。

迭代策略评估：固定策略箭头不变，状态价值经过 Bellman sweep 逐轮收敛 — 固定策略下的反复价值扫描

例子与边界

取

P_\pi=\begin{pmatrix}4/5&1/5\\1/10&9/10\end{pmatrix}, \quad r_\pi=(1,0)^\top, \quad\gamma=1/2, \quad v_0=(0,0)^\top.

同步更新依次给出

v_1=(1,0)^\top,

v_2=(7/5,1/20)^\top, \qquad v_3=(313/200,37/400)^\top.

精确解是 $(22/13,2/13)^\top$ 。第一状态的奖励先进入 $v_1$ ，再经转移概率逐轮传到第二状态；这个轨迹展示的是信息传播，而非重新解一次线性方程。

当 $\gamma$ 很接近一时，几何收敛可能非常慢。 $\gamma=1$ 的继续型任务不再由上述压缩论证覆盖；含终止吸收态的随机最短路也需“适当策略”等额外条件。若更新时使用样本转移而不是完整期望，算法已变成随机近似，固定步长会在不动点附近波动，不能继续引用确定性误差界。

推论与应用

在策略迭代中，评估步骤可用迭代逼近精确值，也可只做有限轮后改进策略，形成 modified policy iteration。有限评估减少单轮代价，却需要另行保证误差不会破坏改进方向。

迭代策略评估也是动态规划备份的基准：它假设模型 $P,r$ 已知并对所有下一状态求和。TD(0)用一次实际转移替代这份完整期望，保留一步 bootstrap 结构，同时引入采样噪声。

参考资料

Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction, 2nd ed., MIT Press, 2018, Sec. 4.1.
Martin L. Puterman, Markov Decision Processes, Wiley, 1994, Sec. 6.3.
Dimitri P. Bertsekas and John N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Prentice Hall, 1989, Ch. 6.

形式陈述 ​

反向链接

形式陈述