4. Iteration Methods

发布于 2026 年 8 月 17 日

上一篇已经得到 Bellman 最优方程，并证明 Bellman 最优算子是压缩映射。这一篇讨论三种由此产生的动态规划算法：

1. 价值迭代（Value Iteration）
2. 策略迭代（Policy Iteration）
3. 截断策略迭代（Truncated / Modified Policy Iteration）

1. Value Iteration

价值迭代（Value Iteration）生成的是一串价值估计，每轮直接做一次 Bellman 最优更新，它不会把某个中间策略的真实价值完整算出来。每轮只是基于当前 $v_k$ 贪心地向前更新一步，策略通常是隐含在 $\max_a$ 里面的 $v_0\rightarrow v_1\rightarrow v_2\rightarrow\cdots\rightarrow v^*$

因此它叫“价值迭代”：外层不断变化和逼近的是 $v_k$

价值迭代可以拆成两个概念步骤

1.1 Policy update：计算一次策略

给定当前价值估计 $\mathbf v_k$，选择相对于它的贪心策略：

$$\boxed{ \pi_{k+1} \in\arg\max_\pi \left(\mathbf r_\pi+\gamma P_\pi\mathbf v_k\right) }$$

这里的最大化是逐状态进行的。对某个状态 $s$，先定义一步前瞻动作价值：

$$q_k(s,a) =\sum_r p(r\mid s,a)r +\gamma\sum_{s'}p(s'\mid s,a)v_k(s')$$

于是：

$$\pi_{k+1}(\cdot\mid s) \in\arg\max_{\pi(\cdot\mid s)} \sum_a\pi(a\mid s)q_k(s,a)$$

因为 $\mathbf v_k$ 在本轮中是常量，最大化一个关于动作概率的线性函数时，可以把全部概率放在某个最大动作上。若：

$$a_k^*(s)\in\arg\max_a q_k(s,a)$$

就可以取确定性策略：

$$\pi_{k+1}(a\mid s) = \begin{cases} 1,&a=a_k^*(s)\\ 0,&a\neq a_k^*(s) \end{cases}$$

重点标注： 这里的策略概率会“变成 $0/1$”。有限 MDP 至少存在一个确定性的贪心策略；如果最大动作不唯一，也可以任选一个，或只在这些最大动作之间随机化。

1.2 Value update：计算一次价值

用刚得到的贪心策略做一次 Bellman 更新：

$$\boxed{ \mathbf v_{k+1} =\mathbf r_{\pi_{k+1}} +\gamma P_{\pi_{k+1}}\mathbf v_k }$$

逐状态写为：

$$\begin{aligned} v_{k+1}(s) &=\sum_a\pi_{k+1}(a\mid s)q_k(s,a)\\ &=\max_a q_k(s,a)\\ &=[T\mathbf v_k](s) \end{aligned}$$

因此价值迭代本质上就是：

$$\boxed{ \mathbf v_{k+1}=T\mathbf v_k }$$

重点标注： 每一轮只“算一次 $\pi$、更新一次 $v$”。这里的 $\pi_{k+1}$ 通常只是帮助理解或最终输出策略；实现时可以直接对 $q_k(s,a)$ 取最大值。

1.3 为什么价值迭代收敛

上一章已经证明 $T$ 在无穷范数下是压缩映射：

$$\|T\mathbf u-T\mathbf v\|_\infty \leq\gamma\|\mathbf u-\mathbf v\|_\infty$$

所以从任意 $\mathbf v_0$ 出发：

$$\|\mathbf v_k-\mathbf v^*\|_\infty \leq\gamma^k\|\mathbf v_0-\mathbf v^*\|_\infty \xrightarrow{k\to\infty}0$$

批注保留： 价值迭代的“收敛保证”来自前面证明过的压缩映射定理。

伪代码如下：

value = {state: 0.0 for state in states}

while True:
    next_value = {
        state: max(
            expected_return(state, action, value)
            for action in actions(state)
        )
        for state in states
    }
    if max(abs(next_value[state] - value[state]) for state in states) < epsilon:
        value = next_value
        break
    value = next_value

policy = {
    state: max(actions(state), key=lambda action: expected_return(state, action, value))
    for state in states
}

2. Policy Iteration

策略迭代（Policy Iteration）生成的是一串策略： $\pi_0\rightarrow\pi_1\rightarrow\pi_2\rightarrow\cdots$ 为了可靠地改进策略，它每一轮需要： 把当前策略 $\pi_k$ 的价值 $v_{\pi_k}$ 算清楚； 根据 $v_{\pi_k}$ 产生更好的策略 $\pi_{k+1}$。 所以价值计算虽然很多，但它只是“评估当前策略”的内部步骤。外层真正被替换、被迭代的是策略。

价值迭代只对当前贪心策略做一次价值更新。策略迭代则在改进策略前，先把当前策略的真实价值算出来。

2.1 Policy evaluation：计算 $\mathbf v_{\pi_k}$

固定策略 $\pi_k$，其价值满足：

$$\boxed{ \mathbf v_{\pi_k} =\mathbf r_{\pi_k} +\gamma P_{\pi_k}\mathbf v_{\pi_k} }$$

策略评估有两种做法。

第一种是直接求解线性方程：

$$\boxed{ \mathbf v_{\pi_k} =(I-\gamma P_{\pi_k})^{-1}\mathbf r_{\pi_k} }$$

第二种是固定策略 $\pi_k$，反复进行 Bellman 更新，直到收敛：

$$\mathbf v_{\pi_k}^{(j+1)} =\mathbf r_{\pi_k} +\gamma P_{\pi_k}\mathbf v_{\pi_k}^{(j)}$$

因为这个固定策略下的更新是压缩映射，所以当 $j\to\infty$ 时：

$$\mathbf v_{\pi_k}^{(j)}\longrightarrow\mathbf v_{\pi_k}$$

重点标注： 这一阶段是在“算 $v$”。它的计算复杂度通常较高：可以做矩阵求逆，也可以进行多次迭代直至收敛。

2.2 Policy improvement：计算 $\pi_{k+1}$

根据 $\mathbf v_{\pi_k}$ 选择贪心策略：

$$\boxed{ \pi_{k+1} \in\arg\max_\pi \left( \mathbf r_\pi+\gamma P_\pi\mathbf v_{\pi_k} \right) }$$

也就是对每个状态选择：

$$\pi_{k+1}(s) \in\arg\max_a \left[ \sum_r p(r\mid s,a)r +\gamma\sum_{s'}p(s'\mid s,a)v_{\pi_k}(s') \right]$$

这一阶段只需要“算一次 $\pi$”，实际上得到的$\pi_{k+1}$是 对 $\mathbf v_{\pi_k}$ 的贪心策略

关键问题是：

1. 为什么这样选出的策略一定不比原策略差？
2. 为什么最终收敛到的策略是最优策略

2.3 策略改进定理

结论： 若 $\pi_{k+1}$ 对 $\mathbf v_{\pi_k}$ 贪心，则：

$$\boxed{ \mathbf v_{\pi_{k+1}}\geq\mathbf v_{\pi_k} }$$

这里的向量不等式表示对所有状态逐元素成立。

由 $\pi_{k+1}$ 的贪心性：

$$\mathbf r_{\pi_k} +\gamma P_{\pi_k}\mathbf v_{\pi_k} \leq \mathbf r_{\pi_{k+1}} +\gamma P_{\pi_{k+1}}\mathbf v_{\pi_k}$$

差值证明：

$$\begin{aligned} \mathbf v_{\pi_k}-\mathbf v_{\pi_{k+1}} &= \left(\mathbf r_{\pi_k}+\gamma P_{\pi_k}\mathbf v_{\pi_k}\right) -\left(\mathbf r_{\pi_{k+1}}+\gamma P_{\pi_{k+1}}\mathbf v_{\pi_{k+1}}\right)\\ &\leq \gamma P_{\pi_{k+1}} \left(\mathbf v_{\pi_k}-\mathbf v_{\pi_{k+1}}\right) \end{aligned}$$

反复代入 $n$ 次得到：

$$\mathbf v_{\pi_k}-\mathbf v_{\pi_{k+1}} \leq (\gamma P_{\pi_{k+1}})^n \left(\mathbf v_{\pi_k}-\mathbf v_{\pi_{k+1}}\right)$$

当 $n\to\infty$ 时，右边趋于 $0$，因此仍然得到：

$$\mathbf v_{\pi_k}\leq\mathbf v_{\pi_{k+1}}$$

直观上，反复代入是在不断把“尚未确定符号的剩余价值差”推向更远的未来； 折扣因子使这部分剩余影响最终衰减为零。一次代入无法做到这一点。

2.4 为什么最终策略是最优策略

a. 直观方案

策略迭代产生单调不减的价值序列：

$$\mathbf v_{\pi_0} \leq\mathbf v_{\pi_1} \leq\cdots \leq\mathbf v^*$$

有限状态、有限动作下，确定性策略的数量也是有限的。只要策略仍能被严格改进，就不会回到一个价值更低的旧策略，因此算法最终会在某个策略 $\bar\pi$ 处稳定：

$$\bar\pi \in\arg\max_\pi \left(\mathbf r_\pi+\gamma P_\pi\mathbf v_{\bar\pi}\right)$$

这说明：

$$\begin{aligned} T\mathbf v_{\bar\pi} &=\mathbf r_{\bar\pi} +\gamma P_{\bar\pi}\mathbf v_{\bar\pi}\\ &=\mathbf v_{\bar\pi} \end{aligned}$$

即 $\mathbf v_{\bar\pi}$ 是 Bellman 最优算子 $T$ 的不动点。由于该不动点唯一：

$$\boxed{ \mathbf v_{\bar\pi}=\mathbf v^* }$$

所以 $\bar\pi$ 是最优策略。

b. 另一种证明：与价值迭代比较并使用夹逼定理

利用

$$\boxed{ \mathbf u_k \leq\mathbf v_{\pi_k} \leq\mathbf v^* }$$

左边: 把策略迭代产生的真实策略价值，与一条价值迭代序列进行比较。

右边：显然最优即上界，所以我们主要证明左边

为了避免符号混淆，用 $\mathbf u_k$ 表示价值迭代序列：

$$\mathbf u_{k+1}=T\mathbf u_k$$

$T$ 为贝尔曼最优算子

策略迭代仍然产生策略序列 $\pi_0,\pi_1,\ldots$ 及对应的真实价值 $\mathbf v_{\pi_k}$。选择满足下式的价值迭代初值：

$$\mathbf u_0\leq\mathbf v_{\pi_0}$$

下面用归纳法证明：

$$\boxed{ \mathbf u_k\leq\mathbf v_{\pi_k}, \qquad \forall k }$$

假设第 $k$ 轮已经满足：

$$\mathbf u_k\leq\mathbf v_{\pi_k}$$

Bellman 最优算子 $T$ 具有单调性，容易理解

如果一个价值函数在所有状态上都不大于另一个价值函数，那么分别进行一次 Bellman 最优更新后，这个大小关系仍然保持。

$$T\mathbf u_k\leq T\mathbf v_{\pi_k}$$

其中左边就是价值迭代的下一步：

$$T\mathbf u_k=\mathbf u_{k+1}$$

而 $\pi_{k+1}$ 是相对于 $\mathbf v_{\pi_k}$ 的贪心策略，所以：

$$\begin{aligned} T\mathbf v_{\pi_k} &=\max_\pi \left( \mathbf r_\pi+\gamma P_\pi\mathbf v_{\pi_k} \right)\\ &=\mathbf r_{\pi_{k+1}} +\gamma P_{\pi_{k+1}}\mathbf v_{\pi_k} \end{aligned}$$

重看 $v_{\pi_{k}}$ 与 $v_{\pi_{k+1}}$ 的关系

从 $v_{\pi_{k}}$ 出发，中间需要先做一次策略改进得到 $\pi_{k+1}$，然后多次固定策略值迭代得到 $v_{\pi_{k+1}}$

接下来需要说明，这个只更新一次的结果不会超过新策略的真实价值。先看第一次更新为什么不会比旧策略价值更小。

因为 $\pi_{k+1}$ 是关于 $\mathbf v_{\pi_k}$ 的贪心策略，而旧策略 $\pi_k$ 也是最大化中的候选策略，所以：

$$\begin{aligned} \mathbf r_{\pi_{k+1}} +\gamma P_{\pi_{k+1}}\mathbf v_{\pi_k} &\geq \mathbf r_{\pi_k} +\gamma P_{\pi_k}\mathbf v_{\pi_k}\\ &=\mathbf v_{\pi_k} \end{aligned}$$

最后一个等号来自旧策略 $\pi_k$ 的 Bellman 方程。这个不等式是贪心选择直接带来的一步改进，并没有提前使用最终结论 $\mathbf v_{\pi_{k+1}}\geq\mathbf v_{\pi_k}$。

为了观察继续使用新策略会发生什么，定义一个普通的价值序列。这里 $k$ 表示外层的策略改进次数，$j$ 表示固定新策略后、内层的价值评估次数：

$$\mathbf w^{(0)}=\mathbf v_{\pi_k}$$

固定使用新策略 $\pi_{k+1}$，反复进行价值更新：

$$\boxed{ \mathbf w^{(j+1)} =\mathbf r_{\pi_{k+1}} +\gamma P_{\pi_{k+1}}\mathbf w^{(j)} }$$

第一次更新为：

$$\mathbf w^{(1)} =\mathbf r_{\pi_{k+1}} +\gamma P_{\pi_{k+1}}\mathbf v_{\pi_k} =T\mathbf v_{\pi_k}$$

下面完整证明这个序列单调递增，并且收敛到 $\mathbf v_{\pi_{k+1}}$。

第一步：证明 $\mathbf w^{(0)}\leq\mathbf w^{(1)}$

把第一次更新与旧策略的价值比较：

$$\begin{aligned} \mathbf w^{(1)} &=\mathbf r_{\pi_{k+1}} +\gamma P_{\pi_{k+1}}\mathbf v_{\pi_k}\\ &\geq\mathbf r_{\pi_k} +\gamma P_{\pi_k}\mathbf v_{\pi_k}\\ &=\mathbf v_{\pi_k}\\ &=\mathbf w^{(0)} \end{aligned}$$

其中，不等号来自 $\pi_{k+1}$ 对 $\mathbf v_{\pi_k}$ 的贪心选择；第二个等号来自旧策略 $\pi_k$ 的 Bellman 方程。因此：

$$\boxed{ \mathbf w^{(0)}\leq\mathbf w^{(1)} }$$

第二步：归纳证明后续更新一直不下降

先计算第二次更新与第一次更新的差：

$$\begin{aligned} \mathbf w^{(2)}-\mathbf w^{(1)} &=\left( \mathbf r_{\pi_{k+1}} +\gamma P_{\pi_{k+1}}\mathbf w^{(1)} \right)\\ &\quad-\left( \mathbf r_{\pi_{k+1}} +\gamma P_{\pi_{k+1}}\mathbf w^{(0)} \right)\\ &=\gamma P_{\pi_{k+1}} \left( \mathbf w^{(1)}-\mathbf w^{(0)} \right)\\ &\geq0 \end{aligned}$$

最后一个不等号成立，是因为 $\gamma\geq0$、$P_{\pi_{k+1}}$ 的元素都是非负数，而且已经证明 $\mathbf w^{(1)}-\mathbf w^{(0)}\geq0$。

一般地，如果 $\mathbf w^{(j-1)}\leq\mathbf w^{(j)}$，那么：

$$\begin{aligned} \mathbf w^{(j+1)}-\mathbf w^{(j)} &=\gamma P_{\pi_{k+1}} \left( \mathbf w^{(j)}-\mathbf w^{(j-1)} \right)\\ &\geq0 \end{aligned}$$

所以通过归纳法得到：

$$\boxed{ \mathbf w^{(0)} \leq\mathbf w^{(1)} \leq\mathbf w^{(2)} \leq\cdots }$$

相邻差值也可以直接写成：

$$\mathbf w^{(j+1)}-\mathbf w^{(j)} =\left(\gamma P_{\pi_{k+1}}\right)^j \left( \mathbf w^{(1)}-\mathbf w^{(0)} \right) \geq0$$

第三步：证明序列一定收敛

我们已经2-Bellman_equation中证明过了

由于这个不动点唯一：

$$\boxed{ \mathbf w^{(j)} \xrightarrow{j\to\infty} \mathbf v_{\pi_{k+1}} }$$

结合第二步的单调性：

$$\mathbf w^{(0)} \leq\mathbf w^{(1)} \leq\mathbf w^{(2)} \leq\cdots \longrightarrow\mathbf v_{\pi_{k+1}}$$

所以第一次更新的结果不会超过最终收敛结果：

$$\boxed{ T\mathbf v_{\pi_k} =\mathbf w^{(1)} \leq\mathbf v_{\pi_{k+1}} }$$

与一般 Bellman 迭代的区别

上面的更新公式与固定策略 $\pi$ 的一般 Bellman 迭代本质相同：

$$\mathbf x^{(j+1)} =\mathbf r_\pi+\gamma P_\pi\mathbf x^{(j)}$$

对任意初值 $\mathbf x^{(0)}$，定义误差：

$$\boldsymbol\delta_j =\mathbf x^{(j)}-\mathbf v_\pi$$

由迭代公式和 Bellman 方程相减可得：

$$\boldsymbol\delta_{j+1} =\gamma P_\pi\boldsymbol\delta_j$$

不断展开：

$$\boldsymbol\delta_j =\left(\gamma P_\pi\right)^j \boldsymbol\delta_0$$

因此：

$$\|\boldsymbol\delta_j\|_\infty \leq\gamma^j \|\boldsymbol\delta_0\|_\infty \xrightarrow{j\to\infty}0$$

这只能保证 $\mathbf x^{(j)}\to\mathbf v_\pi$，不能保证序列递增。从任意初值出发，它可能从下方递增、从上方递减，甚至在不同方向上来回变化。

例如，单状态下令 $r=1$、$\gamma=0.5$，则真实价值为 $v_\pi=2$：

• 从 $x^{(0)}=0$ 出发，得到 $0,1,1.5,1.75,\ldots$，序列递增；
• 从 $x^{(0)}=10$ 出发，得到 $10,6,4,3,2.5,\ldots$，序列递减。

当前的 $\mathbf w^{(j)}$ 之所以能够保证递增，是因为它不是任意初始化，而是同时满足两个特殊条件：

1. $\mathbf w^{(0)}=\mathbf v_{\pi_k}$；
2. $\pi_{k+1}$ 是相对于 $\mathbf v_{\pi_k}$ 的贪心策略。

第二个条件保证第一步不下降：

$$\mathbf w^{(0)}\leq\mathbf w^{(1)}$$

非负转移矩阵再把这个顺序保持到后续所有迭代。因此：

情况	初始值	能够保证的性质
一般 Bellman 迭代	任意 $\mathbf x^{(0)}$	收敛到 $\mathbf v_\pi$，但不一定单调
当前的策略改进证明	$\mathbf w^{(0)}=\mathbf v_{\pi_k}$，且 $\pi_{k+1}$ 对它贪心	单调递增并收敛到 $\mathbf v_{\pi_{k+1}}$

现在把归纳关系连接起来：

$$\boxed{ \mathbf u_{k+1} =T\mathbf u_k \leq T\mathbf v_{\pi_k} \leq\mathbf v_{\pi_{k+1}} }$$

所以归纳假设在第 $k+1$ 轮仍然成立，进而对所有 $k$ 都有：

$$\mathbf u_k\leq\mathbf v_{\pi_k}$$

另一方面，最优价值是所有策略价值的逐状态上界：

$$\mathbf v_{\pi_k}\leq\mathbf v^*$$

于是得到夹逼关系：

$$\boxed{ \mathbf u_k \leq\mathbf v_{\pi_k} \leq\mathbf v^* }$$

价值迭代由 Bellman 最优算子的压缩性保证：

$$\mathbf u_k\xrightarrow{k\to\infty}\mathbf v^*$$

因此对每一个状态分别使用夹逼定理：

$$\boxed{ \mathbf v_{\pi_k} \xrightarrow{k\to\infty} \mathbf v^* }$$

这就从“收敛”的角度证明了策略迭代最终趋于最优。

注意： 这个夹逼证明使用了前面已经得到的策略改进定理，尤其是“按照新策略更新一次的结果不超过新策略的真实价值”。所以它适合证明策略价值最终趋于 $\mathbf v^*$，但不能反过来替代策略改进定理的证明，否则会形成循环论证。

批注保留： “如何保证最优？”可以用两件事回答：价值序列由策略改进定理保证单调不减，并且始终被 $\mathbf v^*$ 上界住；更关键的是，策略稳定时其价值满足 Bellman 最优方程，而该方程的解唯一，因此稳定策略就是最优策略。

策略迭代伪代码如下：

policy = initialize_policy(states)

while True:
    # Policy evaluation
    value = evaluate_policy(policy, states, gamma)

    # Policy improvement
    next_policy = {
        state: max(
            actions(state),
            key=lambda action: expected_return(state, action, value),
        )
        for state in states
    }

    if next_policy == policy:
        break
    policy = next_policy

3. Truncated Policy Iteration

策略迭代的策略评估需要精确求解线性方程，或一直迭代到收敛；价值迭代则只做一步 Bellman 最优更新。截断策略迭代位于二者之间：每轮只对当前策略评估固定的 $m$ 步，然后立刻改进策略。

给定本轮的初值 $\mathbf v_k^{(0)}$，先进行 $m$ 次截断策略评估：

$$\boxed{ \mathbf v_k^{(j+1)} =\mathbf r_{\pi_k} +\gamma P_{\pi_k}\mathbf v_k^{(j)}, \qquad j=0,1,\ldots,m-1 }$$

再令 $\mathbf v_k=\mathbf v_k^{(m)}$，并做一次贪心策略改进：

$$\boxed{ \pi_{k+1} \in\arg\max_\pi \left(\mathbf r_\pi+\gamma P_\pi\mathbf v_k\right) }$$

三种算法的计算节奏可以概括为：

方法	每轮价值更新	每轮策略更新
Value Iteration	$1$ 次最优 Bellman 更新	$1$ 次贪心选择，可隐式完成
Policy Iteration	求逆，或迭代至策略价值收敛	$1$ 次贪心选择
Truncated Policy Iteration	固定 $m$ 次策略评估	$1$ 次贪心选择

因此，$m$ 控制了“把时间花在评估当前策略”还是“更快地改进策略”之间的权衡：$m$ 很大时接近策略迭代；只做很少的评估步时更接近价值迭代。

3.1 截断评估的单调性

使用上一轮的价值作为本轮初值 与上面的证明类似：

$$\mathbf v_k^{(0)}=\mathbf v_{k-1}$$

并且 $\pi_k$ 是相对于 $\mathbf v_{k-1}$ 的贪心策略，那么第一次更新满足：

$$\begin{aligned} \mathbf v_k^{(1)} &=\mathbf r_{\pi_k} +\gamma P_{\pi_k}\mathbf v_{k-1}\\ &=T\mathbf v_{k-1}\\ &\geq\mathbf v_{k-1} =\mathbf v_k^{(0)} \end{aligned}$$

在这个初始条件成立时，后续截断评估也是单调的。相邻两次迭代之差为：

$$\begin{aligned} \mathbf v_k^{(j+1)}-\mathbf v_k^{(j)} &=\gamma P_{\pi_k} \left(\mathbf v_k^{(j)}-\mathbf v_k^{(j-1)}\right)\\ &=(\gamma P_{\pi_k})^j \left(\mathbf v_k^{(1)}-\mathbf v_k^{(0)}\right)\\ &\geq 0 \end{aligned}$$

所以：

$$\boxed{ \mathbf v_k^{(j+1)}\geq\mathbf v_k^{(j)} }$$

重要批注： 上述单调性依赖 $\mathbf v_k^{(0)}=\mathbf v_{k-1}$ 以及第一次更新不下降等条件。实际工程中，初始化、异步更新、采样误差或函数近似可能破坏这些精确前提，所以这个命题更适合作为定性指导，不能不加检查地当作所有实现中的严格保证。

4. 三种方法的关系

三种算法都在交替处理同一对问题：

• 评估： 当前策略到底有多好？
• 改进： 根据当前价值，能否换成更好的策略？

它们的主要区别只是每次改进策略前，把评估做得多彻底：

$$\text{Value Iteration} \longleftrightarrow \text{Truncated Policy Iteration} \longleftrightarrow \text{Policy Iteration}$$

价值迭代每轮成本低，但可能需要较多轮；策略迭代每轮评估成本高，但策略通常能在较少轮内稳定；截断策略迭代用有限次评估在两者之间取得折中。

最值得记住的三个结论是：

1. 价值迭代的收敛来自 Bellman 最优算子的压缩性；
2. 策略迭代的单调改进来自策略改进定理，策略稳定时即达到最优；
3. 截断策略迭代减少了策略评估成本，但理论单调性依赖其初始化和更新条件。