从 Policy Improvement 到 Value Iteration：Bellman Equation 如何找到最优策略？

上一篇推完了 Bellman Equation。那篇最后写了一句：Bellman Equation 是一个递归关系，不是一种算法——Value Iteration 和 Policy Iteration 才是利用它求解的具体方法。

当时没有展开。这一篇接着走。

到上一篇结束时，我对 Bellman Equation 的理解停留在"评价"这件事上。Bellman Expectation Equation 描述了一个策略下各状态价值的递归关系，Bellman Optimality Equation 描述了最优价值函数的递归关系。但具体怎么从一个普通策略出发，找到最优策略，还没想清楚。

之前介绍 V 和 Q 的那篇结尾提到了 Policy Evaluation 和 Policy Improvement 的交替循环，也提到"策略改进定理保证改进后的 Policy 不会比原来差"。但没有解释这个保证从何而来。这篇来认真跟一遍。

本文讨论的所有算法，都假设环境的转移概率和 Reward 函数完全已知——这是 Model-Based Dynamic Programming 的场景。

如果能评价策略，能不能找到更好的

#

先简短回顾。\(V^\pi(s)\) 是从状态 \(s\) 出发、遵循策略 \(\pi\) 时 Return 的期望。\(Q^\pi(s,a)\) 是在状态 \(s\) 执行动作 \(a\)、后续遵循 \(\pi\) 时 Return 的期望。定义和推导见之前的文章。

对于确定性策略，V 和 Q 之间有一个很直接的关系。假设当前策略 \(\pi\) 在状态 A 选择动作 \(a_1\)：

因为 V 就是"完全遵循 \(\pi\)“的长期期望，而 Q 指定的第一步恰好与 \(\pi\) 选择的动作一致。

用数字看。状态 A 有三个动作：

旧策略在 A 选 \(a_1\)，所以 \(V^\pi(A) = Q^\pi(A, a_1) = 10\)。

但 \(a_2\) 的 Q 值是 15，比 10 高。自然的想法：构造一个新策略，在 A 改选 \(a_2\)。

\(\arg\max\) 返回的是让 \(Q^\pi\) 取最大值的那个动作，不是最大值本身。这里 \(\pi'(A) = a_2\)。

对于随机策略，V 是 Q 的加权平均：\(V^\pi(s) = \sum_a \pi(a \mid s) \, Q^\pi(s, a)\)。加权平均不超过最大值，所以不管确定性策略还是随机策略，都有：

到这里似乎很简单——根据旧 Q 选最大的动作就行了。但我很快卡在一个问题上。

\(Q^\pi(A, a_2) = 15\) 这个数字是"在 A 执行 \(a_2\)、后续遵循旧策略 \(\pi\)“算出来的。新策略 \(\pi'\) 在其他状态也可能改了动作。当未来实际使用 \(\pi'\) 而不是 \(\pi\) 时，那个 15 还能当数吗？

一个公式里的两个策略

#

我在这个地方卡了很久。问题出在 \(Q^\pi(s, \pi'(s))\) 这个写法——一个表达式里出现了两个不同的策略。

把 Q 展开：

逐项看：

• \(A_t = \pi'(s)\)：当前这一步的动作由新策略决定。
• \(R_{t+1}\)：执行这个动作后环境返回的即时 Reward。Reward 是环境对状态和动作的响应，不属于某个策略。
• \(S_{t+1}\)：执行这个动作后环境转移到的下一状态。同样由环境决定。
• \(V^\pi(S_{t+1})\)：从下一状态开始，遵循旧策略 \(\pi\) 的长期期望。

上标 \(\pi\) 管的是后续策略，参数 \(\pi'(s)\) 管的是当前动作。

也就是说，\(Q^\pi(s, \pi'(s))\) 描述的是：第一步用新策略选动作，后续全部用旧策略。

把它和 \(Q^{\pi'}(s, \pi'(s))\) 对比——后者的上标也换成了 \(\pi'\)，意味着第一步和后续步骤都由新策略决定。那就等于 \(V^{\pi'}(s)\)。

所以前面的困惑可以说得更精确了。我们已经知道 \(V^\pi(s) \le Q^\pi(s, \pi'(s))\)，但这只证明了"第一步换成新动作、后续用旧策略"不会变差。真正想知道的是 \(V^\pi(s)\) 和 \(V^{\pi'}(s)\) 的关系——后者是全部换成新策略。

为什么换一步不变差，就能保证全部换也不变差？

为什么整个新策略都不会变差

#

这就是 Policy Improvement Theorem（策略改进定理）。

起点是前面建立的不等式。对所有状态 \(s\)：

展开右边的 Q：

这是 Bellman Equation 的定义展开。动作 \(A_t\) 由新策略决定，但从 \(S_{t+1}\) 开始的价值 \(V^\pi(S_{t+1})\) 仍然是旧策略的评价。

关键的一步来了。\(V^\pi(s') \le Q^\pi(s', \pi'(s'))\) 对所有状态成立，\(S_{t+1}\) 也不例外。用这个不等式替换期望内部的 \(V^\pi(S_{t+1})\)。因为 \(\gamma \ge 0\)，不等式方向不变（期望的单调性）：

再把 \(Q^\pi(S_{t+1}, \pi'(S_{t+1}))\) 用 Bellman 展开，得到 \(R_{t+2} + \gamma V^\pi(S_{t+2})\) 的期望。代入后：

这里省略了条件表达式中的完整写法，但含义是：前两步动作由新策略 \(\pi'\) 决定，从 \(S_{t+2}\) 开始仍然用旧策略的价值。

这个替换可以继续做下去。每做一次，就把"新策略负责"的范围往后推一步。在折扣回报、奖励有界的标准条件下，反复展开最终得到：

右边所有动作都由 \(\pi'\) 决定，这就是 \(V^{\pi'}(s)\) 的定义。

这个证明里我觉得最值得记住的一点：不需要事先知道 \(V^{\pi'}\) 的数值，就能证明它不低于 \(V^\pi\)。 整个推导只用了一个事实——在每个状态选旧 Q 的最大动作不会比旧策略原来选的差——然后通过递推把这一步的优势扩展到了整条轨迹。

几个需要保持清醒的边界：

• 保证的是期望 Return 不降低，不是每条随机轨迹的实际收益都不降低。
• 证明依赖准确的 \(V^\pi\)。如果价值函数本身是不精确的估计值，这个保证不自动成立。
• 使用函数近似（比如神经网络）逼近 Q 时，不享有同样的严格改进保证。
• “不变差"不代表一定严格变好——如果旧策略已经是最优的，\(\pi' = \pi\)。

一次改进为什么不够

#

既然能改进一次，为什么不反复改进？这就是 Policy Iteration（策略迭代）。

但我在想的时候遇到了一个困惑。Policy Improvement 对所有状态同时选最优动作，为什么一次不能直接找到最优策略？为什么需要评估、改进、再评估、再改进？

用一个两状态的例子来看。折扣因子 \(\gamma = 0.9\)。

状态 A 有两个动作：

• 直接结束，Reward = 1。
• 前往 B，Reward = 0。

状态 B 有两个动作：

• \(b_0\)：Reward = 0，结束。
• \(b_1\)：Reward = 3，结束。

所有转移确定性。

初始策略 \(\pi_0\)：A 选结束，B 选 \(b_0\)。

评估：

看 A 的 Q 值：

A 不愿意改——结束的 Q = 1 高于前往 B 的 Q = 0。

但 B 这边：\(Q^{\pi_0}(B, b_1) = 3 \gt 0 = Q^{\pi_0}(B, b_0)\)。B 应该改成 \(b_1\)。

\(\pi_1\)：A 仍然结束，B 改为 \(b_1\)。

重新评估 \(\pi_1\)：

再看 A 的 Q 值：

2.7 > 1。这次 A 发现前往 B 更好了。

\(\pi_2\)：A 前往 B，B 选 \(b_1\)。

再检查：\(Q^{\pi_2}(A, \text{结束}) = 1 \lt 2.7\)，\(Q^{\pi_2}(B, b_0) = 0 \lt 3\)。没有状态能进一步改进。收敛了。

第一轮改进时，A 判断"前往 B"的 Q = 0——因为在 \(\pi_0\) 下 B 的价值就是 0。A 当然不愿意前往一个毫无价值的状态。

B 的策略改进之后，B 的价值从 0 变成了 3。但这个变化还没有反映到第一轮 A 的 Q 值中——那时候用的还是 \(\pi_0\) 下的价值函数。

当前轮用于判断动作优劣的 Q，是在旧策略下计算的。后续状态的新策略价值还没有反映进去。 必须重新执行 Policy Evaluation，让 B 的新价值传播回来，A 才能在下一轮看到新的机会。

需要澄清一点。标准 Policy Improvement 对所有状态同时选新动作，不是"先改 A 再改 B"的执行顺序问题。真正的原因是价值信息的传播——一轮评估之后，后继状态的改进才会反映到当前状态的 Q 值中。环境转移的方向是 A → B，而价值信息的传播方向与之相反。

策略评估本身也需要迭代

#

上一节反复提到"重新评估”。评估一个策略的价值函数本身就是一个计算任务。

最简单的例子。只有一个状态 A：每步 Reward = 1，执行后回到 A，\(\gamma = 0.9\)，策略固定。

Bellman Expectation Equation：

解方程得 \(V^\pi(A) = 10\)。这个例子只有一个状态一个方程，直接解出来了。多个状态就是一个线性方程组——原则上也可以直接求解。

另一种做法是 Iterative Policy Evaluation（迭代式策略评估）：从 \(V_0(A) = 0\) 出发，反复用 Bellman 更新。

每一次 Bellman 更新，都把多一步未来 Reward 的影响纳入当前价值。第一轮只看到下一步的 \(R = 1\)。第二轮看到了两步：\(1 + 0.9 \times 1 = 1.9\)。随着迭代推进，越来越远的未来 Reward 被折扣后累加进来，逐渐逼近真实解 10。

这里要区分两件事。

Policy Evaluation 是一个计算目标——求出给定策略的准确价值函数。

Iterative Policy Evaluation 是达成这个目标的一种具体算法。

经典 Policy Iteration 需要的是当前策略足够准确的价值函数，不限定必须用哪种方法求解。解线性方程组也行，迭代逼近也行。

不等评估完就直接优化

#

到这里，Policy Iteration 的完整结构已经清楚了：

 1初始化策略 π
 2
 3while 策略尚未稳定:
 4    # Policy Evaluation
 5    固定当前策略 π
 6    反复使用 Bellman Expectation Equation 更新 V
 7    直到求得当前策略足够准确的价值函数
 8
 9    # Policy Improvement
10    根据当前 Q 值
11    对每个状态选出最大 Q 的动作
12    得到新策略

在 Policy Evaluation 期间，动作选择规则不变。 即使 V 的估计值更新了很多次，也不会中途重新选动作。

这让我产生了一个想法。既然最终目标是最优价值函数 \(V^*\)，能不能在每次 Bellman 更新的时候，不固定某个策略，而是直接考虑所有动作取最大值？

这就是 Value Iteration（价值迭代）。

1初始化 V
2
3while 价值尚未收敛:
4    对每个状态 s:
5        根据当前 V
6        计算所有动作的 Bellman 更新值
7        取最大值作为新的 V(s)
8
9根据最终 V 提取贪心策略

几个关键区别：

• 右侧是当前的价值估计 \(V_k\)，不要求它是某个固定策略的精确价值函数。
• 每次更新都直接对动作取 max。不存在"固定某个中间策略、评估到收敛、再改进"的过程。
• 最终收敛后，对每个状态取 \(\arg\max\) 来提取最优策略。

用同一个 A/B 例子来运行 Value Iteration。初始 \(V_0(A) = V_0(B) = 0\)。

第一轮：

第二轮：

收敛了。\(V^*(A) = 2.7\)，\(V^*(B) = 3\)。提取贪心策略：A 选前往 B，B 选 \(b_1\)——和 Policy Iteration 的最终结果一致。

两种方法明明都在迭代，到底有什么区别

#

A/B 例子太简单——两种方法的中间数值恰好几乎相同。换一个例子来看。

一个状态 A，两个动作：

• 退出：Reward = 5，结束。
• 继续：Reward = 1，回到 A。

\(\gamma = 0.9\)。

Policy Iteration：

初始策略 \(\pi_0\) 选退出。\(V^{\pi_0}(A) = 5\)。

改成继续。新策略 \(\pi_1\) 固定为"继续”，做 Policy Evaluation：

如果用迭代法做这一步 Policy Evaluation，就要固定动作"继续”，反复更新 \(V_0 = 0, V_1 = 1, V_2 = 1.9, \ldots\) 直到逼近 10。中途不会重新比较退出和继续。

检查：\(Q^{\pi_1}(A, \text{退出}) = 5 \lt 10\)，策略不再改变。结束。

Value Iteration：

Value Iteration 每一轮都重新比较退出和继续。第一轮选了退出（5 > 1），但从第二轮开始继续就超过了退出，之后一路逼近 10。

两种方法最终都得到 \(V^*(A) = 10\)，最优策略是继续。但计算过程不同。

Policy Iteration 先确定了"继续"，然后固定这个动作，一直评估到收敛。 评估期间不管退出的 Q 是多少。

Value Iteration 每一轮都把两个动作的值算一遍，取最大的。 没有"固定某个策略"的阶段。

这个例子中 Policy Iteration 用精确求解做 Evaluation，两步就到了最优。Value Iteration 需要很多轮才逼近 10。但这不意味着 PI 总是比 VI 快——如果 PI 的 Evaluation 也用迭代方式，内部也需要很多次更新才能收敛。两种方法的计算效率取决于具体问题，不能简单断言谁更快。

Value Iteration 为什么能收敛

#

前面只是跑了具体的数字。为什么 Value Iteration 在一般情况下也能收敛到 \(V^*\)？

回顾 上一篇提到的 Bellman Optimality Equation：

\(V^*\) 是这个方程的不动点——把 \(V^*\) 代入右边，算出来还是 \(V^*\)。

定义 Bellman Optimality Operator（贝尔曼最优算子）\(T_*\)：

Value Iteration 做的就是 \(V_{k+1} = T_* V_k\)——反复对当前估计应用这个算子。

这个算子有一个关键性质。对于任意两个价值函数 \(V\) 和 \(W\)：

这叫 Contraction Mapping（压缩映射）。无论 \(V\) 和 \(W\) 差多远，经过一次 \(T_*\) 运算后最大差距至多缩小到原来的 \(\gamma\) 倍。

直觉上，误差逐步缩小：

其中 \(e_k = \|V_k - V^*\|_\infty\) 是当前估计与真实 \(V^*\) 之间的最大绝对误差。在有限折扣 MDP（\(\gamma \lt 1\)）且奖励有界的标准条件下，\(V_k\) 收敛到唯一的 \(V^*\)。

几个边界要说清楚：

• 这个收敛保证有明确的数学前提，不是对任意设置都成立的。
• 中间的 \(V_k\) 不对应任何固定策略的精确价值函数——它只是逐步逼近 \(V^*\) 的估计值。
• 收敛保证的是价值函数收敛，不要求中间每一步提取的贪心策略都严格优于上一步。
• 不能直接把 Policy Improvement Theorem 用在不精确的 \(V_k\) 上——那个定理要求准确的旧策略价值函数。

收敛之后，对每个状态取 \(\arg\max_a\) 提取贪心策略，就得到最优策略 \(\pi^*\)。

三种方法的关系

#

回头看一遍。

Policy Iteration 和 Value Iteration 不是完全割裂的。可以这样理解：PI 做完整评估（迭代到收敛）再改进，VI 做一次 Bellman 更新就立刻取 max。中间还存在一种 Modified Policy Iteration（修正策略迭代）——只做有限次评估更新（比如 5 次），就重新执行改进。它处于 PI 和 VI 之间的连续谱上。

从后续状态传回来的价值信息，能够改变前面状态的最优动作选择。Bellman Equation 利用的正是这种递归结构。 A/B 例子里 B 的价值变化"传回"A、使 A 的最优动作改变，就是这个机制的体现。

但不要把这简单等同于确定性 DP 的一遍递推。确定性 DP 通常假设状态之间的依赖关系是 DAG，按拓扑排序递推一遍就能求解。MDP 的状态转移可以有环——Agent 可以反复回到同一个状态（退出/继续的例子就是如此）。有环的情况下不能按固定顺序递推一遍完事，而是需要通过反复迭代逼近不动点。

写在最后

#

这篇讨论的所有方法都有一个共同前提：环境的转移概率 \(P(s' \mid s, a)\) 和 Reward 函数已知。 Bellman Equation 里的期望之所以能算出来，正是因为转移概率已知。

但现实中很多问题的环境模型并不可用。不知道转移概率，不知道 Reward 的完整分布——Agent 能做的只是和环境交互，观察 State、执行 Action、收到 Reward。

如果只有交互样本而没有环境模型，应该怎么利用 Bellman Equation 的递归结构来学习策略？

这是下一篇要面对的问题。

参考资料

#

• 理解 Bellman Equation：从条件期望到概率 DP — Bellman Equation 推导与 DP 联系
• 从 Return 到 Q-Function：强化学习如何评价一个尚未发生的决策 — V、Q 定义与 Policy Evaluation/Improvement 概念
• Sutton & Barto, Reinforcement Learning: An Introduction (2nd edition), Chapter 4
• MIT 6.S191: Introduction to Deep Learning — https://introtodeeplearning.com/