第 4 章 · 动态规划：模型已知时的解法

如果转移概率已知（"模型在手"），贝尔曼方程可以直接迭代求解。策略迭代与价值迭代是两大经典；它们的价值估计部分（策略评估/改进）也是后面无模型方法的模板。

策略评估：解一个线性系统

固定策略下贝尔曼方程是线性方程组，直接解 $O(|S|^3)$ 贵；迭代策略评估反复套用更新式直到 $\Delta < \theta$——更实用。这就是"预测问题"（给定策略求价值）。

策略改进与策略迭代

策略改进定理：对一切 $s$ 满足

则 $\pi'$ 不差于 $\pi$（贪心改进 $\pi'(s) = \arg\max_a q_\pi(s,a)$ 恒满足）。评估 ↔ 改进交替：

有限 MDP 必在有限步收敛到最优策略（策略数有限 + 单调不减）。

价值迭代与异步方法

策略迭代的评估轮可能很费——价值迭代把改进并入更新式（max 替代平均）：

一次遍历 = 一轮"截断评估 + 贪心改进"，收敛更快。广义策略迭代（GPI）是全书的统一视图：任何 RL 算法 = 评估与改进的两个过程部分重叠互相推动——两条腿走路，松散耦合即可收敛。 DP 的局限：需要完整模型（$p$）+ 全状态扫描（维度灾难）；它的遗产：后面所有无模型方法都是"从采样中重造这两个过程"。

老师的提醒

• DP 的自检实验：4×4 网格世界手跑价值迭代十轮，看价值从边界向内传播——贝尔曼方程的" backward 传播"立刻具象。
• 记住家族谱系：模型已知 → DP；模型未知但能采样 → MC（整回合）与 TD（单步）——后面两章都在"重造"这一章。

自检

• 策略改进定理的陈述与贪心改进为何满足它？
• 价值迭代与策略迭代的更新式差别？
• GPI 的统一视图说了什么？

更深一层：动态规划是"评估与改进的两条腿"

策略迭代（评估 → 改进交替）与价值迭代（合并为一步 max）的差异值得作为算法设计范本读：策略迭代的评估轮可能很费（迭代到收敛），价值迭代把改进并入更新式（截断评估 + 贪心改进），广义策略迭代（GPI）的视图统一两者：任何 RL 算法 = 评估与改进的两个过程部分重叠互相推动——两条腿走路，松散耦合即可收敛。这个统一视图是全书的方法论核心：MC、TD、Q-learning、策略梯度全是 GPI 的具体形态。

DP 的局限（需要完整模型 + 全状态扫描的维度灾难）是后面所有无模型方法的动机——MC 与 TD 的工作就是"从采样中重造 DP 的两个过程"。DP 给的是模板，不是答案——这是 Sutton 书的纲领。

推导细读：策略改进定理的"贪心合法性"

策略改进定理：对一切 $s$ 满足 $q_\pi(s, \pi'(s)) \ge v_\pi(s)$ 则 $\pi'$ 不差于 $\pi$。贪心改进 $\pi'(s) = \arg\max_a q_\pi(s,a)$ 恒满足——贪心策略改进是免费的升级（在当前价值函数下贪心，得到不差的新策略）。这个定理的证明（逐状态展开）干净得像艺术品，它是"迭代改进"的合法性证书。RL 的全部收敛性证明都从这条定理出发——评估的近似性 + 改进的贪心性 + 有限 MDP 的有限策略数 = 策略迭代必收敛。

在真实世界里：动态规划的"工程落地清单"

DP 在工程里的落地清单：库存管理（最优订货策略的 DP 解）、路径规划（最短路径的动态规划）、资源分配（背包问题的 DP）、最优控制（LQR 的 Riccati 方程 = 连续版 DP）。DP 的价值不在"解大问题"而在"建立结构"——最优子结构 + 重叠子问题的识别能力，是算法工程师的核心竞争力。

专题深入：动态规划的"两迭代一收敛"完整版

第四章 DP 的骨架是两个迭代算法与一个收敛定理：策略评估（迭代解贝尔曼期望方程：$v_{k+1}(s) = \sum_a\pi(a|s)\sum_{s'}p[s',r|s,a][r + \gamma v_k(s')]$——压缩映射保证收敛）；价值迭代（把评估一步与 max 合并：$v_{k+1}(s) = \max_a(\cdots)$——压缩映射直接收敛到 v*）；策略迭代（评估到收敛 + 贪心改进交替——有限步终止（策略单调改善且数量有限）；广义策略迭代 GPI（评估与改进异步穿插）是几乎所有 RL 算法的统一框架图——DP/蒙特卡洛/TD 都在"GPI 框架 + 不同评估器"里定位）。"max 算子是压缩的"是价值迭代收敛的核心；异步 DP（原地更新、优先扫描——大状态空间的速度工程）。DP 的边界：需要完整模型 p(s', r|s, a) + 全状态扫描——棋类与网格可、真实世界不可——这就是模型免学习方法（第五六章）的出场理由。

推导细读：DP 收敛性与"计算经济学"完整版

第四章的推导细节：压缩映射定理的完整引用（$\|V_{k+1} - V^*\|_\infty \le \gamma\|V_k - V^*\|_\infty$ ⟹ 几何收敛、误差界 $\|V_k - V^*\| \le \gamma^k\|V_0 - V^*\|$——"γ 越大越慢"的定量出处；策略评估提前截断的误差可控（truncated policy iteration 介于两算法之间，实践最优））；改进引理（$v_{\pi'} \ge v_\pi$ 逐点成立，除非已是最优——贪心改进的合法性证明）；状态空间的维数灾难（Backgammon $10^{20}$ 状态——DP 表格法的死亡边界：需要函数近似（第九章）与采样（第五六章）双重救场）。DP 的现代岗位：状态空间百万内 + 模型已知的规划问题（库存、资源调度、博弈求解的底层）；作为理论基准——DP 解就是"标准答案"，模型免学习算法的收敛性常拿它对照。

工程案例细节：规划算法的工程用法工程版

第四章的工程出口：仓库机器人路径规划（网格世界 + 障碍惩罚 + 到达奖励——价值迭代给出全局最优策略，参数变化（货物位置）重算代价可接受）；游戏求解（西洋跳棋的双人版本（minimax 与 DP 的结合——retrograde analysis 从终局反向归档，国际象棋残局库 Lomonosov 表就是 DP 思想）；金融的期权定价（美式期权的最优行止 = MDP + DP——量化金融的 lattice/树方法本质是价值迭代）；资源分配与调度（多周期库存、设备维护更换策略（状态 = 机器老化度，动作 = 修/换）——运筹学与 RL 在 DP 处握手）；作为 RL 课程的实验地基（Gridworld 是一切算法的首个试金石——"先在小格子收敛再上真实环境"是 RL 开发的纪律）。DP 的定位总结：模型已知时它是精确解，模型未知时它是理论灯塔。