第 4 课 · 动态规划算法

对应《动手学强化学习》第 4 章 · 约 40 分钟（含动手实验）

1. 动态规划与强化学习

动态规划（DP）的思想：把问题分解为子问题，先解子问题并保存答案，再组合出原问题的解。对 MDP 来说，贝尔曼方程天然给出了这种递归结构——一个状态的价值由后继状态的价值导出。

• 策略迭代 = 策略评估（用贝尔曼期望方程）+ 策略提升，交替进行；
• 价值迭代 直接用贝尔曼最优方程做 DP。

2. 悬崖漫步（Cliff Walking）环境

4×12 网格世界：起点在左下角，终点在右下角，之间是一段悬崖。每个状态可采取上、下、左、右四个动作，撞墙则原地不动。每走一步奖励 −1，掉入悬崖奖励 −100并结束（回到起点重新开始一幕也可以视为终止）。智能体要学会：绕开悬崖，用最短路径到达终点（最优回报 −13）。

3. 策略迭代

策略评估：算出一个策略有多好

把第 3 课的贝尔曼期望方程改成迭代形式——用上一轮的价值函数计算这一轮的：

可以证明 k→∞ 时 V^k 收敛到 V^π（不动点）。实践中当 max|V^k+1(s) − V^k(s)| < θ 时提前停止。

策略提升：让策略变得更好

已知 V^π 后，在每个状态贪心地选动作价值最大的动作：

策略提升定理保证：若所有状态满足 Q^π(s, π′(s)) ≥ V^π(s)，则 V^π′(s) ≥ V^π(s)——新策略只会更好不会更差。当提升后策略不再变化时，就得到了最优策略。

策略迭代 = 评估 ⇄ 提升 循环

4. 价值迭代：不要等评估收敛

策略评估往往要扫很多轮才收敛（书中悬崖漫步例子：5 次循环里评估总共扫了上百轮）。一个自然的想法：每轮评估只扫一遍就直接提升——这就是价值迭代。它直接迭代贝尔曼最优方程：

价值迭代不维护显式策略，收敛后用一次 argmax 恢复出 π*。书中结果：同一环境下价值迭代只需 14 轮扫描，远少于策略迭代。当 γ<1 时贝尔曼最优算子是 γ-压缩算子，收敛性有严格保证（扩展阅读 4.7）。

5. 🧪 动手实验：在浏览器里跑动态规划

下面复现了书中实验（γ=0.9，θ=0.001）。建议玩法：

1. 选策略迭代，连续点"更新一轮"，看价值（数字与蓝底深浅）如何从起点向全网格传播；评估收敛后自动触发一次策略提升，策略箭头会瞬间变化——数数几轮循环后收敛（书中 5 轮）；
2. 重置后切价值迭代，"跑到收敛"，对比扫描轮数（书中 14 轮）；
3. 收敛后点▶ 播放最优路线：智能体会先向上再向右沿崖顶走最短路径，回报 −13。

6. 冰湖环境：随机转移下的最优策略

书中 4.5 节还在 Gym 的冰湖（Frozen Lake）上验证了两种算法：4×4 网格、冰面打滑——每个动作会等概率滑向 3 个相邻状态（转移是随机的），到达目标奖励 +1，掉冰洞结束。结果两算法得到完全一致的价值与策略（例如 V ≈ [0.069, 0.061, 0.074, …, 0.639]）。有趣的是最优策略看起来"反直觉"：目标左边一格最优动作是向下而非向右——因为打滑可能把你滑到更难走的位置，向下更保险。这说明策略必须适应环境的随机性。

检查你的理解

练习（书后习题方向）

← 返回课程目录