动态规划

这一课的读法：

§ 1示例：3×4 得分网格

策略评估、策略改进、值迭代都靠同一件事成立：用 Bellman 递归，把指数多的完整轨迹压成对「状态价值」的反复复用。这件事在 4×4 仓库里和 γ、转移概率、收敛判据混在一起，不容易单独看清。先用一个更小、更硬的例子把它拆出来看一遍，再回仓库。

三个里只有两个在取最大：策略改进和值迭代。策略评估算的是期望——按给定策略把动作加权平均，它没有 max。三者共有的是递归复用那一层，不是取最大那一步。

一张 3×4 的网格，每格写着走进这一格能拿到的分：

规则四条：① 从左上角 (0,0) 出发，出发时先把那格的 1 收下；② 每步选一个动作 ↑ ↓ ← →，会出界的动作不能选；③ 每走进一格就把那格的分再收一次——回头路允许，重复得分也允许；④ 恰好走 K 步，问累计分最大能是多少。

先想清楚该记什么。只记「现在在哪一格」不够，因为还剩几步会改变答案；只记「已经攒了多少分」也不够，因为下一步能去哪只取决于位置。两样都得记，于是记成一张三维表：

读法：k 是已经走过的步数，(i,j) 是行、列，都从 0 数起。走不到的格子记 −∞，意思是「k 步到不了这儿」。于是初始只有一格有值：dp[0][0][0] = 1，其余全是 −∞。

1.1　路径像树一样散开

从起点开始，每一步、每个位置都往四个方向分叉，树杈的数目按 4^k 涨。但格子总共只有 12 个，可达的位置数根本涨不动。把六层全摆出来（· 表示 −∞，即这一步到不了）：

逐层数一遍可达格数：1 → 2 → 4 → 5 → 6 → 6，第 4 步就到顶了。到顶的原因有两条：网格一共 12 格；而且每走一步 i+j 的奇偶必翻，所以第 k 步只可能站在奇偶与 k 一致的那 6 格里。等走到第 5 步，树杈已经有 4⁵ = 1024 条，落点却仍然只有 6 个。

最后一层就是答案。终点 (2,3) 到起点的曼哈顿距离正好是 5，所以它第一次可达就是第 5 步——dp[5][2][3] = 18，这就是走满 5 步能拿到的最高分。倒着追一遍每一格是从哪儿来的，路径只有一条：

它一步都没浪费：5 步是最短路的长度，而这条最短路又恰好穿过右上角那串高分格（5 和 10）。注意这不是必然的——把 K 放宽到 6，最优解变成 dp[6][2][2] = 20，反而不停在终点：规则要求恰好走满 K 步、又不许原地不动，所以第 6 步只能从 (2,3) 走开——往 (1,3) 加 1、往 (2,2) 加 2，于是落在 (2,2)。再放宽到 K = 7，才谈得上折回去把 10 分格再收一次：(2,3)→(2,2)→(2,3)，答案跳到 30。

1.2　同一步到同一格，就地合并

看上面 dp[3] 里高亮的那一格。第 3 步的 (1,0) 上，正好有三条路径撞在一起：

三条路的走法完全不同，但此刻的处境一模一样：都走了 3 步，都站在 (1,0)。往后能选哪些动作、能走到哪些格、还能拿多少分，三条完全相同——差别只剩已经攒下的那个数。既然如此，攒了 2 和 4 的两条无论后面怎么走都赶不上第三条，当场丢弃：

丢掉的是路径，留下的是一个数。这就是「重复子问题」的实际含义——重复的不是路径，是处境。

把这件事写成一层的循环，就得到了这一课所有算法的原型：

第一行 new = dp[k][i][j] + grid[ni][nj] 是「已经攒的分 + 进新格拿到的分」；第二行的 max 就是合并——谁先算到无所谓，同一个 (k+1, ni, nj) 上只留最大的那个数。一层填完再填下一层，dp[k+1] 只依赖 dp[k]，前面的层用完即可丢。

1.3　贪心、暴力搜索、DP

贪心的规则最省事：每一步都挑「进去那格数字最大」的邻居。跑一遍看它去了哪：

五步拿到 9，而且在 (1,0) 与 (2,0) 之间来回走，离终点一步都没有靠近。失手就在第一步：起点的两个邻居是 (1,0) = 0 和 (0,1) = −1，贪心选 0。可 5 步到终点的最优路是这条：

这条最优路第一步就要先收一个 −1。贪心只看眼前那一格的分，永远不会走这一步，于是也永远走不到右下角那个 10。

暴力搜索不会看错。K = 5 时枚举 4⁵ = 1024 条动作序列，其中不出界的有 157 条，逐条算到底再取最大，答案同样是 18。它的问题只有一个：K = 12 时 4¹² = 16 777 216。

DP 那一行的格子数就是 (K+1) × 12：随 K 线性涨，与动作数无关。暴力那一行随 K 指数涨。两者的答案永远相同，因为合并掉的那些路径，本来就不可能是最优的。

1.4　前向 dp 与值迭代

值迭代本身就是一种 dp，两者不对立。差别只有两处：表有几张，每格装什么。

一、表有几张——看「还剩几步」是不是一个变量。本节的 K 是题目规定的，改了 K 答案就变（K=5 最优 18 分停在终点，K=6 最优 20 分反而不停），所以每层是一个独立的答案，得全留着。上一课没有步数上限，γ < 1 让远处的影响按 γ^k 衰减，逼到某一步「剩几步」就不再影响答案——于是只剩「你在哪一格」，一张表反复覆写就够。现成的证据：仓库里最远的格子离桩 6 步，值迭代 7 遍就精确收敛，再多给步数一个数都不会变。

二、每格装什么——决定你最后拿到什么。

前向 dp 每格记的是过去，argmax 挑出「我是从哪条路来的、哪条分最高」——倒着追能还原出 §1.1 那条 18 分的路径，但半路上问它下一步往哪，它答不上来。值迭代每格记的是未来，argmax 挑出的直接就是「下一步该往哪走」，所以它给的是一张每格都写着往哪走的表：先离线刷到不再变，之后走路只查表。

下面几节讲的算法，全是值迭代那一行的变体：§5 策略评估把 max 换成「照策略加权平均」，§6 策略改进再把它换回 max，§7 策略迭代是两者交替做到不动，而 §8 值迭代是把这一交替压到极端。

本节的每个数（各层 dp 表、三条撞在一起的路径、贪心的 9、最优的 18、157 条不出界序列）都由 code/01_dp.ipynb 跑出来，改 grid 或 k 重跑不到 1 秒。

§ 2Bellman 最优方程

它们的定义、每个记号的含义、怎么从值函数一步步推出来，上一课已经逐条讲过，这里不重复。之所以要摆出来，是因为后面四个算法各自都是把其中一个方程原样改写成更新规则——不把式子放在眼前，改写那一步看不出改在哪儿。

上一课的结论是这一行，它说的是「最优值必须自洽」：

为了看清后面在改哪儿，把它按功能分成三块——这一课每个算法都只动其中一块：

第三块里那个期望，展开就是按转移概率 P(s′|s,a) 加权求和（P 就是 MDP 五要素里的「转移」，它保证这个期望能落成一个具体的数）。整行写开就长这样，这是这一课后面所有式子的原型：

这个式子读一遍就够了：站在 s，把 4 个动作各试一遍——每个动作算「这一步当场收多少，加上落点的值按概率加权后打一个 γ 折」——取其中最大的那个数，就是 V⋆(s)。

拿一个真数字对一遍。这一课的仓库是确定性的（打滑那版在上一课），所以 P 只取 0 和 1：在格 (2,2) 选「下」，落点 100% 是那一格，其余 13 格的概率全是 0，那个 Σ 里只剩一项活着——

对照上一课打滑版的同一套算术：格 (2,0) 选「下」是 −1 + 0.9 × [ 0.90×(−3.0579) + 0.05×(−3.7536) + 0.05×(−2.9829) ] = −3.7801。式子一个字没变，变的只是 P 那一列的数——确定性是「一个 1 加一堆 0」，打滑是「0.90 / 0.05 / 0.05」。这就是为什么那个 Σ 必须一直写在式子里：它不是装饰，是留给 P 的位置。

§ 3Bellman 期望方程

Bellman 期望方程说的是：给定一个策略 π 时，值表必须满足什么。它和 §2 那个最优方程只差外层那一处——那里策略还没定， 在所有动作里挑；这里策略已经给定，外层换成 Σ_a π(a|s)，照它给的概率求平均。对应的算子写作 ：

这个式子读一遍就够了：在状态 s 下，按照策略 π 选择各个动作 a，再考虑每个动作可能产生的所有下一状态 s′ 和奖励 r，把「当场的奖励 r ＋ 折扣后的下一状态价值 γV^π(s′)」按概率加权平均。

§ 4「DP」的两个含义，以及四个算法的位置

大的那个是通用的算法思想——§1 那张得分网格用的就是它，算法课上做过的 dp 题也在这一层。小的那个是强化学习书里说的 DP：已知模型的 MDP 上的规划，也就是下面四节的四个算法。

4.1　dp 的思想：两条，§1 已经演示过

§1 那张 3×4 网格上做的事，抽出来只有两条——不是新东西，你已经见过了：

4.2　同一套技术怎么搬到 MDP 上

值函数恰好也满足那两条，所以技术能原样搬过来——不是打比方，是同一个条件在两个问题上都成立：

4.3　从方程到算法：把等号换成赋值

但方程是等式：等号两边同时出现 V，照着它一个数也填不出来。动态规划把等号换成赋值箭头，右边的 V 一律读上一稿——右边就全是已知的数了：

这个式子读一遍就够了：左边下标 k+1、右边下标 k，就是这一课四个算法的共同骨架。剩下的差别只有两处——右边照哪个方程写，以及算完写回哪张表。

4.4　为什么一个 dp 变成了四个算法

差别只有一样：待求的量多了一个。§1 的网格只要求一个东西——每格的最高分；MDP 上要求两个：值表 V 和 策略 π，而且它们互相定义（V 要照 π 才算得出来，π 要照 V 才挑得出来）。两个互相依赖的未知量，就有四种排法：

前面几课的例子分别站在哪儿：

所以上一课其实是抄了近路：它跳过评估与改进，直接端出「用最优方程、每格更新一次」这一条，因为那是最短、最快能算出一张表的路。这一课把跳过的部分补回来。

§ 5策略评估

下面每个数字都从这里来：16 格去掉 2 个货架 ＝ 14 个状态；右下角的充电桩是终点，进去就不再动、值恒为 0，所以真正要更新的是另外 13 格；每格 4 个动作，合起来 13 × 4 ＝ 52 个状态-动作对。每走一步 −1，γ = 0.9。

这一节走的是 4.4 那张表的第一行：右边照 Bellman 期望方程写，算完写回值表。

§3 那条 Bellman 期望方程说的是这张表必须满足什么；把等号换成赋值、右边的 V 读上一稿，就是评估算法：

这个式子读一遍就够了：站在 s，照策略把每个动作按它的概率过一遍，每个动作再把可能的落点按概率过一遍，各算「这一步的奖励 + 打折后落点在上一稿里的值」，全部加权平均，写成这一格的新值。

这一步有两个名字要记住。把全部 14 格挨个更新一遍叫做一次扫描（sweep）；而算 V_k+1(s) 时用的是另一个状态的估计值 V_k(s′)、而不是等一整条轨迹跑完的真实回报，这叫自举（bootstrapping）——拿一个估计去更新另一个估计。这两个词后面每一课都会用到。

右下角那个下标是关键：算新表只读旧表（V_k），和第 0 课那条备份公式的规矩一模一样。写成算子就是一行：

算子写法读一遍：把上面那一整套动作打包成一个算子 T^π，输入旧表、输出新表，反复作用到新表和旧表一模一样——那张不再变的表就是 V^π。

而因为 T^π 对 V 是线性的，那条 V^π = T^πV^π 也可以不迭代、直接解——把它按矩阵写开：

读一遍：14 个未知数、14 条方程，一次矩阵求逆就把整张表解出来，一轮迭代都不用跑。

其中 P^π 是 14×14 的转移矩阵（第 s 行第 s′ 列 = 照 π 走一步从 s 到 s′ 的概率），r^π 是 14 维的即时奖励向量。γ < 1 保证 I − γP^π 可逆，所以解存在且唯一。

5.1　例：给「一律往右」打分

先找个策略来评。挑一个足够简单、能一眼看穿的：不管在哪一格，一律往右走（撞墙就留在原地）。它的分数表长这样：

5.2　迭代求解与直接求解

路一：反复代入。随便填一张表，然后照着策略一遍遍刷，直到不动。这就是把 反复作用——和上一课一模一样的收缩论证，所以它必然收敛。这次花了 264 轮。

路二：直接解方程。既然 是线性的，那 V^π = T^πV^π 就是上面那组线性方程，高斯消元一次出结果。

两条路算出来的 14 个数，逐格最大差 8e-12——就是浮点误差的量级。

既然能一次解出来，为什么还要迭代？因为消元的代价是状态数的三次方（14 格无所谓，百万格就免谈），而且一旦转移规则不在手里，方程根本列不出来——迭代那条路只需要「能采样」，这就是它能一直延续到深度强化学习的原因。

§ 6策略改进

这一步叫贪心改进。它和上一课那次备份算的是同一个量，区别只在结果写去哪里——备份写回值表，改进写回策略。评估与改进恰好互为反向，下一节把它们接成一个循环。写成定义：

这个式子读一遍就够了：在当前状态 s 下，把每一个可能的动作 a 都试着算一遍未来期望回报，然后选出回报最大的那个动作。

方括号里那一项正是 Q^π，所以「改进」就是把 Q 表的每一行取 argmax，没有别的内容。它和 §2 那个 V⋆ 的式子长得几乎一样，差别只在：max 取的是那个最大的数，argmax 取的是达到它的那个动作。

6.1　例：对「一律往右」改一次

对 5.1 那张分数表做一次改进，10 个格子换了方向：

注意一个反直觉的细节：这一次改进之后，左上角的值还是 -10.0。10 个格子改了方向，但改完仍然到不了桩——只是从「撞墙」变成了「绕圈」。改进保证不变差，可没保证一步到位。

§ 7策略迭代

写成定义：

这条链读一遍就够了：先给一个随便的策略，算出它的值表；照着值表把策略改好；再算新策略的值表，再改……直到某一轮改完策略一个格子都没变，就停。

停机条件那一步值得多看一眼：策略不再变，说明它已经对自己的分数表贪心，即 π(s) = argmax_a Q^π(s,a)，于是 V^π(s) = max_a Q^π(s,a)——这正是 Bellman 最优方程。「策略不动」和「拿到最优解」是同一件事，不是近似。

第一轮为什么要 264 遍，后面几轮只要 2 遍？第一轮评估的是「一律往右」——那张表上有 10 个格子永远到不了桩，值要从 0 一路几何逼近到 −10，刷到 10⁻¹² 就得 264 遍。后面几轮接着上一轮那张表往下算，改动只发生在少数几格、而且都是有限步就能走到桩的格子，两遍就到位。

§ 8值迭代

值迭代上一课就用过了，这里再出现一次不是重讲——是它的身份变了。上一课把它当作「解 Bellman 最优方程的一个办法」直接端出来，你只知道它管用；放进这一节的序列里才看得清楚：它是策略迭代把评估减到只剩一次的产物，不是另外冒出来的一个算法。顺带把层级也摆正：dp 是一类做法（把 Bellman 方程当更新规则反复用），值迭代只是其中一个成员，策略评估、策略改进、策略迭代是另外几个。

值迭代就是把评估减到最短：只评估一次，立刻改进；而且因为「评估一次 + 取最大」可以写成同一个动作，它连策略都不用显式存——每一轮直接对值表取 就行。这正是上一课那个 。

写成定义：把评估那一步的 Σ_a π(a|s) 直接换成 max_a，评估与改进就合并成了一个动作：

这个式子读一遍就够了：站在 s，把 4 个动作各算一遍「这一步的奖励 + 打折后落点在上一稿里的值」，直接取最大写回去——不问策略说该走哪，就要最好的那一个。

和评估式逐字对比，差别只有一处：Σ_a π(a|s) 换成了 max_a。这也是为什么值迭代不需要显式存策略——策略藏在那个 max 里，最后才取出来一次。

8.1　广义策略迭代：把「每轮评估几次」当旋钮

把「每轮评估几次」当成一个旋钮 m，前面四节的算法就排在同一条轴上。m 卡在两端之间的那一档有自己的名字——改进策略迭代（modified policy iteration）：评估不做到底，只刷 m 遍就去改进。

这条轴有个名字：广义策略迭代（generalized policy iteration）。评估想让值表配得上当前策略，改进想让策略配得上当前值表。两件事互相打断——一方刚做完，另一方的结果就不再准确，于是只能交替往前推。至于每次各做多少，是可以调的。后面的算法只是把这个旋钮调到不同位置：值迭代调到最小，而 Stage 1 之后的方法连「扫全表」都做不到，只能拿采样到的几条转移做很少几次评估。

「备份」在这一课的口径统一成一次动作评估——算一次「r + γ·落点的值」。所以：评估扫一遍 = 13 次（每格只算它选定的那个动作），取最大或改进一遍 = 52 次（每格 4 个动作全试）。这和上一课的说法不同：上一课把「一格上 4 个动作试一遍、取最大写回」整体叫一次备份；这一课改按单个动作计，是为了让没有 max 的评估和有 max 的改进能放在同一把尺子上比。换算是固定的：上一课的一次备份 ＝ 这里的 4 次。

§ 9计算代价：轮数与总更新次数

这条轴还有一个更重要的下游：后面 Stage 2 的 actor-critic，骨架就是 m 很小的策略迭代——critic 只刷几步就交给 actor，actor 也只改一点点，交替进行。你在这张表上看到的权衡，会原样出现在那里，只不过评估从「扫全表」换成了「采几条轨迹」。

§ 10三种更新都依赖转移模型 P

策略迭代是评估与改进的交替，所以真正不同的更新只有三种：评估、改进、值迭代。这三种共同依赖的东西只有一样：转移模型 P——每个动作会把你带到哪儿、概率各是多少。这一节说明为什么三种更新一个都绕不开它，以及绕开它的唯一出路。

回头看改进那一步，把它完整写出来：

要选出最好的动作，你必须知道每个动作会把你带到哪儿、概率各是多少。这一课的三种更新——评估、改进、值迭代——没有一件能绕开这个 P。而真机上没有人会给你 P。

10.1　动作值函数 Q

解法用的不是新东西：Q 前面两课都出现过——上一课还在仓库里算过一格。这里只是把它的一个性质拿来用——与其存「这一格值多少」，不如直接存「在这一格做这个动作值多少」：

代价是表变大：值表一格一个数，Q 表一格四个数——13 个非终点格各 4 个动作，52 个数对 14 个数。换来的是选动作这件事不再需要模型。仓库里格 (2,2) 那一行是这样的：

§ 11本章小结

1. Bellman 最优方程里只有三样东西：取最大（决策）、这一步的奖励、打折后的未来值。取最大是唯一让它非线性的部件。
2. 把取最大换成「照策略办」，方程就变成线性的——所以策略评估既能迭代，也能一次解出来（这里两条路差 8e-12）。
3. 永远到不了终点的策略，值是 −1/(1−γ) = −10。折扣把无穷长的失败压成一个有限的数。
4. 策略改进定理保证逐格不降，但只保证不变差、不保证一步到位——这一课改进一次之后，左上角依然是 −10。
5. 值迭代 = 只评估一次就改进的策略迭代。轮数少不等于算得少：策略迭代 5 轮、3796 次备份，值迭代 7 轮、364 次备份。
6. 三种更新都卡在同一个 P 上。把它吸收进 Q，选动作就不再需要模型——这是通往下一课唯一的门。
7. DP 是后面所有方法的模板，不是一个会被淘汰的老算法。它的两个限制——要有完整的 P、每次扫描都要碰遍整个状态空间——决定了后面每一步在改什么：蒙特卡罗去掉模型，改用整条轨迹的真实回报；时序差分留下自举，但只用一条采样的转移；Q-learning 把这里的最优备份原样搬到采样出来的动作价值上。换掉的是「怎么拿到那一步的信息」，没换的是这一课的更新骨架。

11.1　这一课在整本书里的位置

这一课交出的不是四个算法，是一副骨架：在一个 MDP 上，用某种数据，反复做「评估 ⇆ 改进」。后面所有的方法——一直到 RLHF——都没有换掉这副骨架，只是把其中某一处换掉。整本书一共只换六处：

图里出现的三个记号，都是 §2 那个 MDP 五元组 (S, A, P, r, γ) 里的成员：P(s′|s,a) 是转移概率——在状态 s 选了动作 a 之后，下一格恰好是 s′ 的概率；r(s,a) 是奖励函数——这一步当场拿到多少；π 是策略——每一格该走哪个动作。P̂ 读作「P hat」，表示从数据里估出来的那张转移表，不是真的 P。

源文件 docs/assets/gpi-skeleton.drawio（draw.io 打开可改）。

这六支不是并列的六个话题，是有先后的。前三支（转移概率、值函数怎么估、策略怎么改）是骨架内部的事，这一课把 ① 的「已知」那一行做完了；后三支（数据、表示、奖励函数）是骨架外部的前提，每换掉一条，就多一类新方法，也多一类新麻烦：