📑 本页目录（点开跳转）
04 · 动态规划：知道规则时怎么解
⏱ 18 分钟 ｜ 🎁 理想情况的基准线
🎯 一句话
如果你完全知道环境规则（P 和 R），贝尔曼方程就是一个方程组， 可以直接迭代解出来 —— 这就是动态规划。
⚠️ 现实中你几乎从不知道 P 和 R。 那为什么还要学这一章？因为后面所有算法都是它的近似版， 而且它给了你一个"如果什么都知道，最好能做到多好"的上限参照。
🔁 一、策略评估：给定策略，算出它值多少
做法：把贝尔曼期望方程当成赋值语句，反复迭代。
$$V_{k+1}(s) \leftarrow \sum_a \pi(a|s)\Big[R(s,a) + \gamma\sum_{s'}P(s'|s,a)V_k(s')\Big]$$
① 所有 V 初始化为 0
② 用上面的公式，根据【旧的 V】算出【新的 V】
③ 重复，直到 V 几乎不再变化
💡 为什么一定会收敛：
每迭代一次，误差就乘以 γ（<1）。γ^k → 0，所以必然收敛，且收敛到唯一解。 这在数学上叫「压缩映射」——γ<1 是全部保证的来源。
🔨 十几行就能写完
def policy_eval(pi, states, actions, P, R, gamma=0.9, tol=1e-8):
V = {s: 0.0 for s in states}
while True:
delta = 0
for s in states:
v_new = sum(
pi[s][a] * (R[(s, a)] + gamma * sum(
p * V.get(s2, 0.0) for s2, p in P[(s, a)].items()))
for a in actions)
delta = max(delta, abs(v_new - V[s]))
V[s] = v_new
if delta < tol: # ⭐ 收敛判据看【最大变化量】
return V
♻️ 二、策略迭代：评估 → 改进 → 再评估
① 随便来个策略 π₀
② 【评估】：算出 V^π
③ 【改进】：每个状态改成贪心选 argmax_a Q(s,a)
④ 策略没变？停。变了？回到 ②
π₀ →评估→ V₀ →改进→ π₁ →评估→ V₁ →改进→ π₂ ...
🔑 策略改进定理（这一章唯一需要记的理论）： 按 V^π 贪心得到的新策略 π'，一定不比 π 差。
因为策略数量有限、每次严格变好或不变，所以有限步内必然收敛到最优策略。
💡 一个反直觉的事实：策略迭代通常只需要很少几轮就收敛 （第 3 章那个 MDP 只要 2 轮）—— 大部分时间花在里面的"评估"上。
⚡ 三、价值迭代：把两步合成一步
观察：策略评估要迭代到完全收敛，很浪费 —— 反正马上就要改策略了。
价值迭代：干脆只做一次评估就改进，合并成一个公式：
$$V_{k+1}(s) \leftarrow \max_a\Big[R(s,a) + \gamma\sum_{s'}P(s'|s,a)V_k(s')\Big]$$
和策略评估的唯一区别：Σ π(a|s) 换成了 max_a ⭐
→ 直接迭代贝尔曼【最优】方程
→ 收敛后得到 V*，再 argmax 一次拿到 π*
两者对比
| 策略迭代 | 价值迭代 | |
|---|---|---|
| 每轮代价 | 高（要把评估迭代到收敛） | 低（只扫一遍） |
| 轮数 | 少（通常 < 10） | 多 |
| 实现难度 | 稍复杂 | 简单 ⭐ |
| 实践首选 | ✅ 一般用这个 |
💡 它们其实是同一个算法族的两端： 中间还有「广义策略迭代」——评估做几轮就去改进，不必等收敛。 ⭐ 后面所有算法（包括 PPO）本质上都是广义策略迭代： 一边估价值，一边改策略，两者交替推进。看懂这条线，后面就不会觉得算法是散的。
🧮 四、在第 3 章那个 MDP 上跑一遍
初始 V = {上课: 0, 刷机: 0}
第 1 轮（价值迭代）：
上课: max(学: 2+0.9(0.8·0+0.2·0)=2, 玩: 1+0.9·0=1) = 2
刷机: max(学: -1+0.9(0.6·0+0.4·0)=-1, 玩: 1+0.9(0.9·0)=1) = 1
第 2 轮：
上课: max(2+0.9·0.8·2=3.44, 1+0.9·1=1.9) = 3.44
刷机: max(-1+0.9(0.6·2+0.4·1)=0.44, 1+0.9·0.9·1=1.81) = 1.81
...继续迭代...
收敛：V*(上课)=7.1429 V*(刷机)=5.2632 ⭐ 和第 3 章解方程的结果一致
✅ 两条路殊途同归：第 3 章是解方程，这里是迭代逼近。 迭代法的好处是 —— 状态一多，方程组根本解不动，但迭代永远能跑。
💀 五、动态规划的两个致命限制
限制 1：必须知道 P 和 R（模型已知）
下围棋：你知道规则 ✅ 但状态太多（见限制2）
玩 Atari：你【不知道】游戏内部逻辑 ❌
推荐系统：你【不知道】用户看到某个商品后会怎样 ❌
RLHF：你【不知道】人类会怎么打分 ❌
⭐ 现实中绝大多数问题都是「模型未知」
→ 第 5 章开始讲怎么在不知道规则的情况下学
限制 2：要遍历所有状态（维度灾难）
每一轮都要对【每个状态】算一遍
围棋：10¹⁷⁰ 个状态 💀
Atari 一帧画面：256^(84×84) 💀💀
语言模型的上下文：词表^长度 💀💀💀
→ 第 8 章开始用神经网络【近似】价值函数，不再存表
🔗 这正是数学原理第 5 章维度灾难在强化学习里的样子。 表格法的天花板不是算法不好，是状态空间根本存不下。
🗺️ 六、这一章在整条线里的位置
| 问题的条件 | 用什么方法 | 在哪一章 |
|---|---|---|
| 模型已知 + 状态少 | 动态规划 | 本章 |
| 模型未知 + 状态少 | MC / TD | 第 5 章 |
| 模型未知 + 状态少 | Q-learning | 第 6 章 |
| 模型未知 + 状态多 | DQN ⭐ | 第 8 章 |
| 动作连续 | 策略梯度 ⭐ | 第 9 章起 |
⭐ 每一步都是在放宽一个限制。
🔗 七、和站内其他章的关系
| 相关的地方 | 这里的位置 |
|---|---|
| 第 3 章贝尔曼方程 | 本章把它当赋值语句迭代 |
| 数学原理 05维度灾难 | 限制 2 的理论根据 |
| 算法课的动态规划 | 同一个思想（用子问题的解拼出大问题） |
✅ 检查点
- 动态规划要求你知道什么？现实中通常满足吗？
- 策略评估为什么一定收敛？关键条件是什么？
- 策略改进定理说了什么？为什么能保证有限步收敛？
- 价值迭代和策略评估在公式上唯一的区别是什么？
- 策略迭代和价值迭代各自的代价在哪？实践中一般用哪个？
- 什么是广义策略迭代？为什么说后面所有算法都是它？
- 动态规划的两个致命限制是什么？分别由哪章解决？
👀 答案
- 必须知道转移概率 P 和奖励函数 R（模型已知）。现实中绝大多数问题都不满足——玩 Atari 不知道游戏内部逻辑、推荐不知道用户反应、RLHF 不知道人类怎么打分。
- 因为每迭代一次误差乘以 γ，γ<1 所以 γ^k→0，必然收敛到唯一解（压缩映射）。关键条件就是 γ<1。
- 按 V^π 贪心得到的新策略 π' 一定不比 π 差。因为策略数量有限且每次严格变好或不变，所以有限步内必收敛到最优。
- 策略评估用 Σπ(a|s)·[...]（按策略加权），价值迭代用 max_a[...]（直接取最好）。
- 策略迭代：每轮代价高（评估要迭代到收敛）但轮数少；价值迭代：每轮便宜但轮数多。实践一般用价值迭代（实现简单）。
- 评估做几轮就去改进、不必等收敛。后面所有算法（含 PPO）本质都是它：一边估价值一边改策略，两者交替推进。
- ①必须知道模型 P、R → 第 5 章（MC/TD 从经验中学）②要遍历所有状态，状态一多就爆炸 → 第 8 章（用神经网络近似，不再存表）。
🛑 可以停在这里
⚡ 走神救援
动态规划=知道环境规则(P,R)时，把贝尔曼方程当赋值语句反复迭代。⭐收敛保证来自 γ<1（每轮误差乘γ，压缩映射）。策略迭代=评估→改进→再评估，靠策略改进定理（按V^π贪心的新策略一定不比旧的差）保证有限步收敛；价值迭代=把两步合一，公式上唯一区别是 Σπ(a|s) 换成 max_a，实现简单所以实践首选。⭐两者是同一族的两端，中间是「广义策略迭代」——后面所有算法（包括PPO）本质都是它：一边估价值一边改策略，交替推进。在第3章那个MDP上迭代收敛到 V(上课)=7.1429、V(刷机)=5.2632，和解方程结果一致；迭代法的好处是状态一多方程组解不动但迭代永远能跑。💀两个致命限制：①必须知道P和R（现实中Atari/推荐/RLHF全都不知道）→第5章解决 ②要遍历所有状态（围棋10¹⁷⁰个）→第8章用神经网络近似。每往后一章就是放宽一个限制。
下一节 👉 05-蒙特卡洛与时序差分.md