【强化学习全景系列 之四】上帝视角：动态规划，当你知道世界的所有规则

【强化学习全景系列 之四】

上帝视角：动态规划，当你知道世界的所有规则

在上一章，我们揭示了强化学习的“宇宙基石”——贝尔曼方程。它优美地描述了价值函数必须满足的递归关系。但它也留下了一个巨大的前提：方程中的环境动态 p ( s ′ , r ∣ s , a ) p(s\', r | s, a) p(s′,r∣s,a) 是已知的。

今天，我们将探讨一个理想化的情境：如果智能体真的拥有了这种“上帝视角”，即它对一个完全可知的马尔可夫决策过程（MDP） 了如指掌时，我们能做什么？答案是，我们可以动用一个极其强大的“规划”（Planning）工具集——动态规划（Dynamic Programming, DP），来直接“解出”这个世界的最优解。

【上一篇】【强化学习全景系列 之三】宇宙基石：贝尔曼方程的递归之美

---

一、动态规划的前提：一个完全透明的世界

在我们开始之前，必须再次强调DP方法的核心前提：智能体拥有一个完美的环境模型。

在强化学习的语境下，一个完美的环境模型意味着我们掌握了构成马尔可夫决策过程（MDP）的所有要素：

• $\mathcal{S}$: 所有可能状态的集合。
• $\mathcal{A}$: 所有可能动作的集合。
• $P$: 状态转移概率，即 p ( s ′ ∣ s , a ) = P [ S t + 1= s ′ ∣ S t = s , A t = a ] p(s\' | s, a) = \\mathbb{P}[S_{t+1}=s\' | S_t=s, A_t=a] p(s′∣s,a)=P[St+1​=s′∣St​=s,At​=a]。
• $R$: 奖励函数，为简化，我们常使用其期望形式 r ( s , a ) = E [ R t + 1∣ S t = s , A t = a ] r(s, a) = \\mathbb{E}[R_{t+1} | S_t=s, A_t=a] r(s,a)=E[Rt+1​∣St​=s,At​=a]。
• $\gamma$: 折扣因子，决定了未来奖励的重要性。

这就像下棋时，你不仅知道棋子怎么走，还拥有了一本“天书”，上面精确记录了你走任何一步后，对手所有可能的应对方式、其发生的概率，以及每种应对会带来的直接得分。你甚至可以基于这本天书，完美预判出棋局在未来任意步后的所有可能走向和最终胜率。

在现实世界中，这种假设几乎从不成立。我们无法精确预测天气、股市，也无法完全建模一个复杂机器人的所有物理交互。然而，DP的价值并不在于其直接的泛用性，而在于它为我们提供了两个至关重要的贡献：

1. 理论基准 (Theoretical Benchmark)：DP算法为求解MDP提供了计算上的理论最优解。所有其他强化学习算法，尤其是在模型未知情况下的算法，都可以视作是对DP思想的一种“近似”或“模拟”，并以DP的解作为性能的黄金标准。
2. 算法思想的摇篮 (Algorithmic Cradle)：DP孕育了后续所有强化学习算法的核心思想——自举（Bootstrapping）。即“用旧的价值估计来更新和提升当前的价值估计”。这个思想是后续更实用的时序差分（TD）学习的基石。

DP的核心，就是利用价值函数的递归性，将描述性质的贝尔曼方程，转化为可迭代、可计算的 赋值操作。下面，我们将深入探讨两种主要的DP算法。

---

二、策略评估 (Policy Evaluation)：你的计划到底有多好？

这是DP中最基础的任务，也被称为“预测问题”（Prediction Problem）。

• 目标：给定一个固定的策略 $\pi (a|s)$，精确计算出该策略下所有状态的价值函数 V π ( s ) V^\\pi(s) Vπ(s)。
• 方法：迭代式策略评估（Iterative Policy Evaluation）。
• 核心思想：将贝尔曼期望方程从一个静态的“真理陈述”变成一个动态的“更新规则”。

回顾贝尔曼期望方程：
它描述了 V π (s) V^\\pi(s) Vπ(s)必须满足的性质：
V π ( s ) = ∑ a ∈ Aπ ( a ∣ s ) ( r ( s , a ) + γ ∑ s ′ ∈ S p ( s ′ ∣ s , a ) V π ( s ′ ) ) V^\\pi(s) = \\sum_{a \\in \\mathcal{A}} \\pi(a|s) \\left( r(s,a) + \\gamma \\sum_{s\' \\in \\mathcal{S}} p(s\'|s, a) V^\\pi(s\') \\right) Vπ(s)=a∈A∑​π(a∣s)(r(s,a)+γs′∈S∑​p(s′∣s,a)Vπ(s′))

迭代更新规则：
我们从一个任意的初始价值函数 V 0 (s) V_0(s) V0​(s) 开始（通常全部设为0），然后反复对所有状态 $s\in \mathcal{S}$ 进行以下同步更新（synchronous backup），直到价值函数收敛：
V k + 1( s ) ← ∑ a ∈ Aπ ( a ∣ s ) ∑ s ′ , rp ( s ′ , r ∣ s , a ) [ r + γ V k ( s ′ ) ] V_{k+1}(s) \\leftarrow \\sum_{a \\in \\mathcal{A}} \\pi(a|s) \\sum_{s\', r} p(s\', r|s, a) \\left[r + \\gamma V_k(s\')\\right] Vk+1​(s)←a∈A∑​π(a∣s)s′,r∑​p(s′,r∣s,a)[r+γVk​(s′)]
注意：这里的 p ( s ′ , r ∣ s , a ) p(s\',r|s,a) p(s′,r∣s,a) 是联合概率，求和后等价于上面使用期望奖励 $r(s,a)$ 的形式。

这个过程如何理解？——价值的涟漪

1. 初始化 ($k=0$)： V 0 V_0 V0​ 全是0。我们对世界一无所知，认为所有状态都毫无价值。
2. 第一次迭代 ($k=1$)：我们用 V 0 V_0 V0​（全是0）来计算 V 1 V_1 V1​。此时，一个状态的价值 V 1 ( s ) V_1(s) V1​(s) 就等于遵循策略 $\pi$ 能获得的单步即时奖励的期望值。这相当于我们只“看到”了眼前一步的利益，价值信息首次从奖励源头产生。
3. 第二次迭代 ($k=2$)：我们用 V 1 V_1 V1​ 来计算 V 2 V_2 V2​。这时，一个状态的价值 V 2 ( s ) V_2(s) V2​(s) 不仅包含了即时奖励，还包含了下一步能到达的状态的单步价值（ V 1 V_1 V1​）的折扣期望。价值信息开始从奖励源头向外传递一步。
4. 持续迭代 ($k\to \infty$)：随着 $k$ 的增加，价值信息就像投石入水产生的“涟漪”一样，从奖励源头（高奖励或低奖励的状态）开始，依据状态转移概率 $p$ 这张“地图”，一波一波地、反向地传播到整个状态空间。每一次迭代，我们都在用旧的、看得更短浅的价值函数 V k V_k Vk​ 来“自举”（bootstrap），计算出一个更准确、看得更长远的价值函数 V k + 1 V_{k+1} Vk+1​。

为什么这个过程一定会收敛？
从数学上讲，只要折扣因子 $\gamma <1$ 或者任务是分幕式的（保证能终止），上述更新操作所对应的贝尔曼算子 (Bellman Operator) T π T^\\pi Tπ 是一个压缩映射 (Contraction Mapping)。根据巴拿赫不动点定理，反复应用一个压缩映射，最终必然会收敛到唯一的不动点，而这个不动点正是当前策略 $\pi$ 的真实价值函数 V π V^\\pi Vπ。

---

三、策略迭代 (Policy Iteration)：在“评估”与“改进”之间翩翩起舞

知道了如何评估一个策略，我们自然会想：如何找到最优策略 π ∗ \\pi^* π∗ 呢？策略迭代（Policy Iteration）算法给出了一个优雅而强大的解答。

它将寻找最优解的过程分解为两个交替执行的步骤，就像一场优美的双人舞，在策略评估和策略改进两个环节之间循环，直至舞步无法再优化，达到完美的和谐。这个过程也被称为广义策略迭代 (Generalized Policy Iteration, GPI)。

算法流程：

1. 初始化 (Initialization)：

   • 从一个任意（甚至很差）的确定性策略 π 0 \\pi_0 π0​ 开始。
   • 初始化一个价值函数 V 0 V_0 V0​（例如全为0）。

2. 进入循环 (Iteration Loop): 对于 $k=0,1,2,...$

   • (E) 策略评估 (Policy Evaluation)
     使用上一节介绍的迭代方法，为当前的策略 π k \\pi_k πk​ 计算其准确的价值函数 V π k V^{\\pi_k} Vπk​。
     V π k ⟵ E Iterative Policy Evaluation for  π k V^{\\pi_k} \\stackrel{E}{\\longleftarrow} \\text{Iterative Policy Evaluation for } \\pi_k Vπk​⟵E​Iterative Policy Evaluation for πk​
     注意：这一步本身就是一个完整的迭代过程，理论上需要迭代至完全收敛。

   • (I) 策略改进 (Policy Improvement)
     一旦我们有了准确的 V π k V^{\\pi_k} Vπk​，我们就可以站在“巨人”的肩膀上，寻找一个更好的策略 π k + 1 \\pi_{k+1} πk+1​。方法非常直观：对于每一个状态 $s$，我们不再盲从旧策略 π k \\pi_k πk​，而是环顾四周，贪婪地选择那个能引导我们到“最有价值”的后续状态的动作。

     具体来说，我们首先为每个状态 $s$ 和动作 $a$ 计算其动作价值函数 Q π k ( s , a ) Q^{\\pi_k}(s, a) Qπk​(s,a)：
     Q π k ( s , a ) = r ( s , a ) + γ ∑ s ′ ∈ S p ( s ′ ∣ s , a ) V π k ( s ′ ) Q^{\\pi_k}(s, a) = r(s,a) + \\gamma \\sum_{s\' \\in \\mathcal{S}} p(s\'|s, a) V^{\\pi_k}(s\') Qπk​(s,a)=r(s,a)+γs′∈S∑​p(s′∣s,a)Vπk​(s′)
     这个公式计算的是：在状态 $s$ 选择动作 $a$ 后，遵循旧策略 π k \\pi_k πk​ 一直走下去所能得到的期望总回报。

     然后，我们构造一个新的、改进的策略 π k + 1 \\pi_{k+1} πk+1​，它在每个状态都选择能最大化Q值的动作：
     π k + 1 ( s ) = arg ⁡ max ⁡ a ∈ A   Q π k ( s , a ) \\pi_{k+1}(s) = \\underset{a \\in \\mathcal{A}}{\\arg\\max} \\, Q^{\\pi_k}(s, a) πk+1​(s)=a∈Aargmax​Qπk​(s,a)

3. 终止条件 (Termination)：当策略改进后，新的策略 π k + 1 \\pi_{k+1} πk+1​ 与旧的策略 π k\\pi_k πk​ 完全相同（即对于所有状态 $s$， π k + 1 ( s ) = π k ( s ) \\pi_{k+1}(s) = \\pi_k(s) πk+1​(s)=πk​(s)），说明我们已经无法通过贪心找到更好的动作了。此时的策略已经收敛，它就是最优策略 π ∗\\pi^* π∗，其对应的价值函数 V π k V^{\\pi_k} Vπk​ 就是最优价值函数 V ∗V^* V∗。

为什么这个改进是有效的？
这背后有强大的策略改进定理 (Policy Improvement Theorem) 作为支撑。该定理指出，如果对于某个状态 $s$，我们发现存在一个动作 $a$ 使得 Q π k (s,a)> V π k (s) Q^{\\pi_k}(s, a) > V^{\\pi_k}(s) Qπk​(s,a)>Vπk​(s)，那么我们创建一个新策略 π k + 1 \\pi_{k+1} πk+1​，在状态 $s$ 选择动作 $a$，在其他状态仍遵循 π k \\pi_k πk​，那么新策略的价值一定优于旧策略，即 V π k + 1 (s)≥ V π k (s) V^{\\pi_{k+1}}(s) \\ge V^{\\pi_k}(s) Vπk+1​(s)≥Vπk​(s) 对所有状态成立。我们贪婪地对所有状态进行改进，保证了每一步迭代都让策略变得更好或保持不变，最终必然收敛到最优。

---

四、价值迭代 (Value Iteration)：更直接的贪婪之路

策略迭代非常强大，但它的“评估”步骤需要进行多次完整的迭代直至收V值收敛，计算成本较高。我们不禁要问：真的有必要每次都等到 V π V^\\pi Vπ 完全精确了再改进吗？能不能把舞蹈的两个舞步合并成一步，让舞姿更“迅猛”？

价值迭代（Value Iteration） 给出了一个更高效的答案。它的核心思想是：将策略评估的单次迭代和策略改进“融合”在一步。它不再显式地维护和操作策略 $\pi$，而是直接迭代价值函数，直至其收敛到最优价值函数 V ∗ V^* V∗。

价值迭代直接将贝尔曼最优方程作为其更新规则：

回顾贝尔曼最优方程：
它描述了最优价值函数 V ∗ (s) V^*(s) V∗(s) 必须满足的性质：
V ∗ ( s ) = max ⁡ a ∈ A ( r ( s , a ) + γ ∑ s ′ ∈ S p ( s ′ ∣ s , a ) V ∗ ( s ′ ) ) V^*(s) = \\max_{a \\in \\mathcal{A}} \\left( r(s,a) + \\gamma \\sum_{s\' \\in \\mathcal{S}} p(s\'|s, a) V^*(s\') \\right) V∗(s)=a∈Amax​(r(s,a)+γs′∈S∑​p(s′∣s,a)V∗(s′))

迭代更新规则：
V k + 1( s ) ← max ⁡ a ∈ A ∑ s ′ , rp ( s ′ , r ∣ s , a ) [ r + γ V k ( s ′ ) ] V_{k+1}(s) \\leftarrow \\max_{a \\in \\mathcal{A}} \\sum_{s\', r} p(s\', r|s, a) \\left[r + \\gamma V_k(s\')\\right] Vk+1​(s)←a∈Amax​s′,r∑​p(s′,r∣s,a)[r+γVk​(s′)]

对比一下策略评估的更新规则，区别在哪里？

• 策略评估 (Policy Evaluation)：
  V k + 1( s ) ← ∑ a π ( a ∣ s ) … V_{k+1}(s) \\leftarrow \\sum_{a} \\pi(a|s) \\dots Vk+1​(s)←∑a​π(a∣s)…
  它是在计算一个给定策略下的期望，是在遵循一个固定的“计划”。
• 价值迭代 (Value Iteration)：
  V k + 1( s ) ← max ⁡ a … V_{k+1}(s) \\leftarrow \\max_{a} \\dots Vk+1​(s)←maxa​…
  它在每一步更新时都直接在所有动作中选择最优，相当于隐含地执行了一次“贪婪”的策略改进。

价值迭代可以看作是策略迭代的一个变种，其中策略评估的步骤被缩减为仅仅进行一次扫描（一次迭代）。它直接将最优性原理（Principle of Optimality）作为更新的动力，每一次迭代都将相邻状态的“最优”价值信息传播出去，因此通常比策略迭代更快收敛到最优价值函数。

当价值函数收敛到 V ∗ V^* V∗ 后（即 V k + 1 V_{k+1} Vk+1​ 与 V k V_k Vk​ 的差异小于某个阈值），我们只需进行最后一次策略提取，即可得到最优策略 π ∗ \\pi^* π∗：
π ∗ ( s ) = arg ⁡ max ⁡ a ∈ A ∑ s ′ , rp ( s ′ , r ∣ s , a ) [ r + γ V ∗ ( s ′ ) ] \\pi^*(s) = \\underset{a \\in \\mathcal{A}}{\\arg\\max} \\sum_{s\', r} p(s\', r|s, a) \\left[r + \\gamma V^*(s\')\\right] π∗(s)=a∈Aargmax​s′,r∑​p(s′,r∣s,a)[r+γV∗(s′)]

---

五、DP算法对比与总结

特性 策略迭代 (Policy Iteration) 价值迭代 (Value Iteration) 核心思想 在“评估”和“改进”两个独立步骤间循环 将评估（一步）和改进融合在单次更新中 更新目标 迭代策略 π k \\pi_k πk​，并为其计算精确的 V π k V^{\\pi_k} Vπk​ 直接迭代价值函数 V k V_k Vk​，使其趋近于 V ∗ V^* V∗ 核心公式 评估: V k + 1 ← T π kV k V_{k+1} \\leftarrow T^{\\pi_k}V_k Vk+1​←Tπk​Vk​ (多次)
改进: π k + 1 ← greedy ( V π k ) \\pi_{k+1} \\leftarrow \\text{greedy}(V^{\\pi_k}) πk+1​←greedy(Vπk​) V k + 1 ← max ⁡ a ( r + γ P V k ) V_{k+1} \\leftarrow \\max_a (r+\\gamma P V_k) Vk+1​←maxa​(r+γPVk​) (贝尔曼最优算子) 单次迭代复杂度 较高（内部包含一个完整的策略评估循环） 较低（一次全状态扫描） 收敛速度 迭代次数通常较少，但每次迭代耗时 迭代次数通常较多，但每次迭代飞快 最终产出 直接收敛到最优策略 π ∗ \\pi^* π∗ 和最优价值 V ∗ V^* V∗ 收敛到最优价值 V ∗ V^* V∗，需要额外一步提取 π ∗ \\pi^* π∗

本章小结：DP的力量与枷锁，以及通往未来的大门

本章，我们站在“上帝视角”，学习了如何使用动态规划来“规划”一个已知MDP的最优解决方案。

• 策略评估：告诉我们如何精确评估一个给定计划的好坏。
• 策略迭代：通过“评估-改进”的循环，稳步逼近并保证找到最优策略。
• 价值迭代：一种更高效的算法，通过直接迭代最优价值函数来加速求解。

DP的力量在于，它为强化学习提供了一套坚实的理论基础和算法原型。自举（Bootstrapping），即用现有价值估计来更新价值估计的思想，将贯穿我们后续学习的所有高级算法，如时序差分（TD）学习。

然而，DP也戴着沉重的枷锁：

1. 维度诅咒 (Curse of Dimensionality)：它要求对状态空间进行全量扫描和存储（for s in S）。当状态空间巨大时（如围棋有 1 0 170 10^{170} 10170 个状态，或机器人手臂的连续角度状态），这在计算和存储上都变得不可行。
2. 完美模型的诅咒 (Curse of the Perfect Model)：它最大的软肋，就是对完美环境模型 p ( s ′ , r ∣ s , a ) p(s\',r|s,a) p(s′,r∣s,a) 的依赖。这在绝大多数现实问题中都是一个无法满足的奢侈条件。

这恰恰为我们打开了通往下一章的大门。在现实的“黑盒”世界里，我们没有天书，没有上帝视角。智能体必须亲自与环境交互，通过一次次的尝试（Trial）和犯错（Error），从自己收集到的经验（Experience）样本中学习。

那么，当模型未知时，我们该怎么办？

我们将如何仅凭经验样本来估计价值？又将如何找到最优策略？

这将是我们下一季要探索的主题：无模型强化学习（Model-Free Reinforcement Learning）。我们将从蒙特卡洛（Monte Carlo）方法和时序差分（Temporal-Difference）学习开始，进入一个更加真实、也更加激动人心的强化学习新世界。

【下一篇】【强化学习全景系列 之五】蒙特卡洛：不到黄河心不死，从完整经验中学习

订阅专栏，不错过最新讯息！