动态规划：策略评估、策略迭代与值迭代
本文基于模型知识整理（生成时未联网核对），关键结论建议对照 Sutton & Barto 教材复核。
一句话定义
当转移核 $p(s'|s,a)$ 与奖励完全已知时，动态规划（DP）在表格上反复施加贝尔曼算子求解：策略评估（算 $v^\pi$）、策略迭代（评估→贪心改进→循环）、值迭代（把改进的 max 融进每轮更新）——它们是理解一切 RL 算法的"理想参照系"。
为什么重要
DP 需要模型，实践中大都无法直接用，但它是概念基准：策略改进定理（贪心于 $v^\pi$ 必不更差）、收敛性证明、"评估-改进"交替骨架，全部被后续无模型方法继承——GPI（广义策略迭代）正是 Sutton 对整个 RL 的统一视角。看懂 DP，"评估与改进互相咬合上升"这幅图就有了。
前置知识
kp-004（贝尔曼方程）；不动点迭代的直觉。
核心概念
- 策略评估（预测问题）：解线性方程组 $v^\pi = r_\pi + \gamma P_\pi v^\pi$；数值方案是迭代式 $v_{k+1}(s) = \sum_a \pi(a|s)\sum_{s'} p(s'|s,a)[r + \gamma v_k(s')]$，γ<1 保证收敛。
- 策略改进：$\pi'(s) = \arg\max_a \sum_{s'} p(s'|s,a)[r + \gamma v^\pi(s')]$；由策略改进定理，$v^{\pi'} \ge v^\pi$（逐状态）。
- 策略迭代：评估（解到收敛）→ 改进 → 循环；有限 MDP 上有限轮收敛到 $\pi^*$。
- 值迭代：把"评估一步+改进"合并：$v_{k+1}(s) = \max_a \sum_{s'} p(s'|s,a)[r + \gamma v_k(s')]$——直接逼近 $v^*$，每轮只做一次备份。
- 广义策略迭代（GPI）：任何"评估与改进交替"的过程，两者互相拉扯最终相遇于 $v^*$ 与 $\pi^*$——MC、TD、Q-Learning 全是 GPI 的实例。
原理与机制
为什么贪心改进不会变差：若 $\pi'$ 贪心于 $v^\pi$，则对每个 s 有 $q^\pi(s, \pi'(s)) \ge v^\pi(s)$；沿轨迹展开得 $v^{\pi'}(s) \ge v^\pi(s)$。这一行证明是 RL 理论的顶梁柱——"利用当前估计变好"从此有了保证，无模型方法（kp-008）的策略改进同样靠它背书。
计算复杂度的现实约束：DP 每轮要对全部状态-动作对做期望备份，且需要转移核。维度灾难：状态数随变量数指数增长（10100 网格 10^100 状态）——这是" curse of dimensionality"，也是为什么转向采样式方法（kp-007/008）：不必访问所有状态，只学"去过的"状态。
异步 DP：不必整表同步更新，按任意顺序就地更新（Gauss-Seidel 式）也收敛——这个"优先级/就地更新"思想在现代回放优先级（kp-011）与实时规划中延续。
图示
策略迭代: π₀ ─评估─► v^{π₀} ─贪心改进─► π₁ ─评估─► v^{π₁} ──► … → π*
值迭代: v₀ ─max备份─► v₁ ─max备份─► v₂ ──► v* → 贪心提取 π*
GPI 统一图: 评估(算真v)与改进(往π*拉)两条线互相咬合收敛于交点直观类比
策略迭代像"先精确复盘每一步的价值，再据此改打法，循环"；值迭代像"边走边想：每步直接挑'当下最好+未来折现'最大的路"。两者殊途同归；DP 的唯一奢侈是"知道地图全程"（转移核），真实世界没有这张地图——于是有了后面整个无模型世界。
实例或案例
- GridWorld/迷宫：几十轮值迭代即收敛，可视化价值扩散过程。
- 库存控制/设备更换：状态空间小且模型可辨识时，DP 是工业标准解。
- 概念后代：TD(λ) 的前向/后向视图（kp-008）、MCTS 的值备份（kp-021）都是贝尔曼备份的不同采样/聚焦版本。
常见误区
- 误区一："DP 是 RL 的入门玩具所以可以跳过"。它是收敛性与策略改进定理的出处；不看它，后面 on-policy 收敛、Q-Learning 正确性全是"信仰"。
- 误区二："值迭代每轮都要策略收敛"。值迭代刻意不完整评估，用 max 备份直接奔 v*——比策略迭代每轮更便宜。
- 误区三："模型已知问题就简单"。转移核未知≠不存在；DP 的前提是"能查表"，采样方法的前提只是"能交互"。
与其他知识点的关系
- kp-004：DP 是贝尔曼方程的表格解法。
- kp-008：TD 把"期望备份"换成"样本备份"，模型不再需要。
- kp-021：MCTS 是聚焦在当前状态子树上的局部 DP。
- kp-017：Actor-Critic 的"critic 评估 + actor 改进"是 GPI 在函数逼近下的延续。
自测题
- 策略改进定理说了什么？一句话证明思路？
答：贪心于 $v^\pi$ 的新策略逐状态不劣（$v^{\pi'} \ge v^\pi$）；因为 $q^\pi(s,\pi'(s)) \ge v^\pi(s)$ 沿轨迹展开即得。
- 策略迭代与值迭代的区别？
答：前者每轮把评估解到收敛再改进，轮少而每轮贵；后者把 max 融进更新、每轮一次备份，逼近 v* 更直接。
- DP 为什么在大状态空间不可行？RL 如何绕开？
答：备份要遍历全部状态-动作对且需转移核，复杂度指数级；RL 改用采样（只学访问过的状态）与函数逼近（泛化到未访问状态）。
延伸阅读
- Sutton & Barto 教材第 4 章（DP 全章）。
- David Silver 课程 Lecture 3。
- Bertsekas《Neuro-Dynamic Programming》（DP 与函数逼近的衔接）。