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]$$

💡 为什么一定会收敛：

每迭代一次，误差就乘以 γ（<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^π 贪心得到的新策略 π'，一定不比 π 差。

因为策略数量有限、每次严格变好或不变，所以有限步内必然收敛到最优策略。

💡 一个反直觉的事实：策略迭代通常只需要很少几轮就收敛 （第 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]$$

两者对比

💡 它们其实是同一个算法族的两端： 中间还有「广义策略迭代」——评估做几轮就去改进，不必等收敛。 ⭐ 后面所有算法（包括 PPO）本质上都是广义策略迭代： 一边估价值，一边改策略，两者交替推进。看懂这条线，后面就不会觉得算法是散的。

🧮 四、在第 3 章那个 MDP 上跑一遍

✅ 两条路殊途同归：第 3 章是解方程，这里是迭代逼近。 迭代法的好处是 —— 状态一多，方程组根本解不动，但迭代永远能跑。

💀 五、动态规划的两个致命限制

限制 1：必须知道 P 和 R（模型已知）

限制 2：要遍历所有状态（维度灾难）

🔗 这正是数学原理第 5 章维度灾难在强化学习里的样子。 表格法的天花板不是算法不好，是状态空间根本存不下。

🗺️ 六、这一章在整条线里的位置

⭐ 每一步都是在放宽一个限制。

🔗 七、和站内其他章的关系

✅ 检查点

1. 动态规划要求你知道什么？现实中通常满足吗？
2. 策略评估为什么一定收敛？关键条件是什么？
3. 策略改进定理说了什么？为什么能保证有限步收敛？
4. 价值迭代和策略评估在公式上唯一的区别是什么？
5. 策略迭代和价值迭代各自的代价在哪？实践中一般用哪个？
6. 什么是广义策略迭代？为什么说后面所有算法都是它？
7. 动态规划的两个致命限制是什么？分别由哪章解决？

🛑 可以停在这里

⚡ 走神救援

下一节 👉 05-蒙特卡洛与时序差分.md