第 1 课 · Stage 0 · MDP 与 Bellman 算子

第一课 · Stage 0

马尔可夫决策过程与 Bellman 算子

承接上一课那个值函数。·这一课把问题写成 MDP，并交出值必须满足的两个方程——只给方程，不给算法。

上一课那条五格链上没有选择——只能往前走，所以 V 和 V⋆ 是同一个数。这一课换成一个真正要做决策的环境：一台 AGV 在 4×4 的仓库里找充电桩。14 个状态、4 个动作，整张表就印在这一页上——我们把它一格一格刷出来，看着数字从充电桩往外长；然后看这套办法在哪一步不再成立。不成立的那几处，正是后面每一步要接手的地方。

§ 1示例：4×4 仓库网格

一间 4×4 的仓库。AGV 每一步往上下左右挪一格，撞墙或撞货架就留在原地（这一步照样白走）。走到右下角的充电桩（画圈那格）就停下，任务结束。下图里 AGV 画在 (0,0)，但它可以从任何一格出发——值迭代一次把 14 个格子的答案全算出来。

奖励只有一条：每走一步 −1，进充电桩之后不再有任何奖励。你没有告诉它路线，只告诉它「每多走一步就亏一点」——越快到，累计奖励越高。折扣 = 0.9。

为什么用 −1，而不是「到了给 +100」。两种写法都能让它到桩，但 −1 把「快」直接写进了每一步：任何一条多绕的路，值上立刻就差。而「只在终点给奖励」是稀疏奖励——在这个 4×4 上无所谓，等状态一多，它就是最难学的一类问题（§5 那张传播图就是原因）。

数一数规模：16 格去掉 2 个货架 = 14 个状态；除去充电桩，每格 4 个动作 = 52 个状态-动作对。整张表能印在纸上，这正是这一课要的：每一个结论你都能自己核对。

§ 2MDP 的五个要素

§1 那间仓库是用中文描述的：撞墙留在原地、走到桩就结束。这些话要变成能算的东西，先得一条条指认成记号。这一节把它写成 MDP 的五个要素。

五样东西合起来写成一个五元组，这就是 MDP 的全部定义：

MDP = ( S, A, P, r, γ )

五样填满，「最优策略」这四个字才有定义——少一样，问题本身就没提清楚，也就谈不上求解。

MDP 的第几样	符号	这间仓库里是什么
状态空间	S	AGV 在哪一格。14 个，(3,3) 是吸收态——进去就不出来
动作空间	A	上、下、左、右，4 个
转移	P(s′\|s,a)	确定性：选了方向就走那一格；出界或撞货架则原地不动。§7 会给它加上打滑
奖励	r(s,a)	每走一步 −1，进桩之后为 0
折扣	γ	0.9。有效视野 = 10 步

五样里最需要多说一句的是转移 P。它不是一个数——对每一对 (s, a)，它各给出一张「下一格可能是谁」的概率表：

P(s′ | s, a) ＝在状态 s 选了动作 a 的条件下，下一格恰好是 s′ 的概率。

中间那道竖线是条件概率的记法，不是除号，也不是绝对值。取值上有 0 ≤ P ≤ 1，并且对固定的 (s, a)，Σ_s′ P(s′|s,a) = 1——走一步总得落在某一格，概率加起来必须是 1。

这间仓库现在是确定性的，所以 P 只取 0 和 1（选了方向就 100% 走那一格），一张概率表退化成「查一个落点」，看不出它是个分布。要到 §7 加上 10% 打滑，它才第一次取到 0 和 1 以外的值。

状态为什么只要「在哪一格」就够。因为知道了格子编号，下一步会去哪、能拿多少奖励就全定了——再多的历史也给不出额外信息。这就是马尔可夫性对状态变量的要求。反过来说：如果地面打滑与否取决于上一步的速度，那「格子编号」就不够了，你得把速度也加进状态。状态选漏了，后面所有理论一句都不成立。

§ 3最优值函数 V^⋆ 与它的闭式解

五个要素齐了，可要求的那个东西还没露面。这一节先把答案摆出来——每格一个数的那张表 V⋆，外加它在这间仓库里的闭式解；怎么算出来留到 §5。

上一课那条链上，值是一格一格刷出来的。这间仓库也一样，只是每格多了 4 个动作要比。跑一遍值迭代（§5 讲怎么跑），得到的就是下面这张表——每格一个数，外加每格一个箭头 π⋆：

3.1　折扣因子 γ

这张表你可以完全不靠代码验一遍。确定性、每步 −1，所以从离桩 d 步的格子出发，最优走法就是直奔充电桩，累计奖励是

V^⋆(s) = −1 − γ − γ² − ⋯ − γ^d−1离桩 d 步，直奔充电桩，每步 −1= −(1 − γ^d) / (1 − γ)有限项等比数列求和= −10 (1 − 0.9^d)代入 γ = 0.9，即 1/(1−γ) = 10

离桩几步 d	公式给的 −10(1−0.9^d)	值迭代跑出来的
0	0.0000	0.0000
1	-1.0000	-1.0000
2	-1.9000	-1.9000
3	-2.7100	-2.7100
4	-3.4390	-3.4390
5	-4.0951	-4.0951
6	-4.6856	-4.6856

逐格核对，最大差 0.0。但别把这两张表当成同一个东西。d 是「几步」，是这张地图的几何性质；值是打折之后的累计奖励。它们在这里一一对应，只因为奖励结构特别简单（确定性 + 每步固定 −1）。§7 就是现成的反例：加上打滑之后，每格的最短路 d 一个都没变，值却全变了，还有两格的最优动作翻了向。之所以特意挑一个有闭式解的例子，是为了让你手里有一把不靠代码的尺子——绝大多数问题没有这个待遇。

这不是巧合，是这一课后面全部结论的落脚点：值迭代收敛到的那个东西，就是「最优地走下去能拿多少」这句话本身。以后所有算法都在近似它，而近似得好不好，永远是拿这张表当尺子量的。

的三个身份在这张表上一次看全：它是你关心多远的未来——未来第 t 步的奖励被打折 0.9^t，把所有未来的权重加起来：

1 + γ + γ² + γ³ + ⋯ = 1/(1 − γ) = 10

这个 10 是折扣回报的下界：每步奖励 −1 时，无论走多少步、能不能到达充电桩，累计折扣奖励都不会低于 −10。折扣把一个无限项的求和压成了有限值——第 100 步的那个 −1 仍在式子里，但它的权重只有 0.9¹⁰⁰ ≈ 0.000027，对结果不再有影响。三个身份分别是：它是有效视野 1/(1−γ) = 10 步；它是所有误差界里的放大器（§6 那条界就带着它）；它还决定值的量级——同一间仓库， = 0.5 时左上角是 -1.9688，0.9 时 -4.6856，0.99 时 -5.8520。 不是超参数，它是问题定义的一部分：改它就是改题目。

同一条级数还解释了它为什么也是误差放大器（§6 那条界里的 9 倍）：某一步上的误差 ε 会沿着后续所有步传下去，累计起来是 ε(1 + + ² + ⋯) = ε/(1−)。「看多远」与「误差被放大多少」，是同一个求和的两种读法——想看得远，就得接受近似误差被放大同样的倍数。

§ 4值函数、Bellman 方程与最优算子

§3 摆出了 V⋆ 这张表，可「值」这个词到现在只有一种含义。这一课有 4 个动作，一整族相关的量才第一次分家——这一节把该分清的记号一次分清，并给出它们必须满足的两个方程。

真做算法时你会同时遇到一整族相关的量——照某个给定策略能拿多少、在这一格先走某个动作能拿多少、某个动作比平均好多少。它们不是各自独立的定义，而是同一个回报，在不同条件下取平均。

这一节把这一族一次讲完。后面每一课都在这套记号里说话，所以哪怕前面提过的（回报、V⋆），这里也重新过一遍——目的是让你在一个地方就能看清它们彼此是怎么推出来的，而不是记住六个定义。

4.1　回报 G

回报上一课已经定义过，这里只回忆一行——它把「今后能拿多少」从一句话变成一个能算、能取平均的量：

G_t = Σ_k=0^∞ γ^kR_t+k+1 = R_t+1 + γR_t+2 + γ²R_t+3 + ⋯

换到这间仓库代一遍：从离桩 4 步的格子直奔充电桩，四步各罚 −1，

G = −1 − 0.9 − 0.81 − 0.729 = −3.4390

正是 §3 表里 d = 4 那一行。§3 那条闭式 −10(1−0.9^d) 就是这个和的求和公式，没有别的内容。上一课强调过的那一点在这里要用上：回报是一个样本，不是一个估计——确定性时它唯一，一旦落点带随机（§7 的打滑）每次都不一样，所以下面每一个「值」都带着一个求平均的 E。

4.2　策略 π

它解决什么问题：要谈「值」，必须先说清楚按谁的走法算。

π(a|s) ＝在状态 s 选动作 a 的概率， Σ_a π(a|s) = 1

确定性策略是它的特例（某个动作概率为 1，其余为 0）。把它和环境摆在一起，能看清一步之内谁说了算：

p_π(s′|s) = Σ_a π(a|s)智能体
你能改的 P(s′|s,a)环境
给定的

读一遍：从 s 走一步、落到 s′ 的概率，等于把每个动作的「你选它的概率 × 它把你送到 s′ 的概率」乘起来再加总。

右边那个 P 是 §2 五要素里的「转移」，你改不了。这门课所有算法，动的都只有 π(a|s) 那一项。§3 那张 14 个箭头的图，就是一个确定性策略。

4.3　状态价值 V^π

它解决什么问题：不能给策略打分，就无从比较两个策略的好坏，也就谈不上「改进」。

V^π(s) = E_π[ G_t | S_t = s ]

读法：从 s 出发、此后一直照 π 走，回报的平均值。§3 那张表其实是 V^π⋆——最优策略下的那一张；换一个策略，同一格的数就会变（下一课给「一律往右」打分，会有 10 个格子全是 −10）。

4.4　动作价值 Q^π

Q⋆ 这个名字上一课出现过——那条链上每格只有一个动作，所以它和 V⋆ 是同一组数。这一课每格有 4 个动作，它才第一次和 V 分开，也才看得出它是干什么用的。

它解决什么问题：手上只有 V 时，要挑动作就必须先知道每个动作会落到哪——也就是必须有转移 P。Q 把这一步预先算好存起来，选动作退化成在这一行里挑最大。这一条是后面能彻底拿掉模型的关键。

Q^π(s,a) = E_π[ G_t | S_t = s, A_t = a ]

这个式子读一遍就够了：在状态 s 下先把第一步定死为 a，之后一直照策略 π 走，所能拿到的回报的平均值。

和 V 的差别只有一句话：Q 多固定了第一步，之后的走法完全一样。所以把第一步按策略平均掉，就回到 V：

V^π(s) = Σ_a π(a|s) Q^π(s,a)

读一遍：把这一格上每个动作的动作价值，按策略选它的概率加权平均，就回到这一格的状态价值。

用 §3 的表现算一格。取 (2,0)，它离桩 4 步；四个动作各走一步之后落到哪、那一格值多少，都能直接查表——Q⋆(s,a) = −1 + 0.9·V⋆(s′)：

动作 a	落点 s′	V⋆(s′)	Q⋆(s,a) = −1 + 0.9·V⋆(s′)
上	(1,0)，离桩 5 步	−4.0951	−4.6856
下	(3,0)，离桩 3 步	−2.7100	−3.4390 ← 最大
左	撞墙，留在 (2,0)	−3.4390	−4.0951
右	(2,1)，离桩 3 步	−2.7100	−3.4390 ← 并列最大

四个数里最大的是 −3.4390，正是 §3 表里 d = 4 那一行。这不是巧合，而是下一节那台机器的定义。

4.5　优势 A^π

它解决什么问题：比较动作时绝对值不好用——上面四个数全是负的，一眼看不出差距。优势把「比平均好多少」直接标出来，改不改这个动作变成看正负号。

A^π(s,a) = Q^π(s,a) − V^π(s)

这个式子读一遍就够了：在状态 s 下，选动作 a 比「按照当前策略的平均水平」到底好多少。正的表示比平均好，负的表示比平均差，0 表示正好持平。

上面那格的四个优势：−1.2466 / 0 / −0.6561 / 0（上 / 下 / 左 / 右）。两个并列最优恰好都是 0，其余全为负——这不是这一格的巧合：

Σ_a π(a|s) A^π(s,a) = Σ_a π(a|s)Q^π(s,a) − V^π(s) = V^π(s) − V^π(s) = 0

V 本来就是 Q 的平均，「比平均好多少」平均起来必然是 0。在最优策略下更进一步：最优动作的优势恰好是 0、其余为负——于是「哪个动作最优」变成「哪一格等于 0」。

4.6　Bellman 期望方程

它解决什么问题：4.3 到 4.5 全是定义，写的都是一条无穷长的和——照着定义你一个数都算不出来。Bellman 方程把「今后能拿多少」改写成「这一步 + 下一格的值」，于是可以递推、可以解方程。这是从理解走到能算的那一步。

V^π(s) = Σ_a π(a|s)你的选择
按 π 平均 Σ_s′ P(s′|s,a)环境的随机
按 P 平均 [ r(s,a) + γV^π(s′) ]这一步的奖励
+ 打折后的未来值

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

两层求和各管一件事，缺一层这个式子就不成立。在这一课它们都是退化的：策略是确定性的（外层只剩一项）、转移也是确定性的（内层只剩一项），两个 Σ 各自只剩一项，于是还原成你熟悉的那一行 V(s) = −1 + 0.9V(s′)。要到 §7 加上 10% 打滑，内层才真的展开成 0.90 / 0.05 / 0.05 三项。

4.7　Bellman 最优方程

上一课用「预算无限」讲过 V⋆，也讲过为什么它的方程两边是同一个函数——那套论证这里一个字都不用改。缺的只是一句相对于策略的准确定义：

V⋆(s) = max_π V^π(s)，对每一个 s 都成立

读一遍：对每一格，在所有可能的策略里，挑出让这一格的值最大的那个策略，取到的那个数就是 V⋆(s)。

把 4.6 那个式子的外层求和换掉，就得到 Bellman 最优方程：

V⋆(s) = max_a [ r(s,a) + γ Σ_s′ P(s′|s,a) V⋆(s′) ]
π⋆(s) = argmax_a Q⋆(s,a)

读一遍：在状态 s 下，把每个动作可能产生的下一状态按概率加权，算出「当场的奖励 + 折扣后的下一状态价值」，然后取最大的那个动作；下面那行的 argmax 交出的则是取到最大值的动作本身。

全部改动只有一处：Σ_a π(a|s) 变成 max_a——不再按策略平均，而是直接挑最好的。

这一处之所以不同，是因为两个方程里「策略定没定」不一样。

Bellman 期望方程：策略 π 已经给定。每一格该走哪个动作是别人写好的，你没得挑，所以对动作只能按 π 给的概率求平均——外层那个 Σ_a π(a|s) 就是在做这件事。它回答的是：照这个策略走，每一格值多少。

Bellman 最优方程：策略还没定，它本来就是要算出来的东西。动作是你自己挑，所以对动作取最大。它回答的是：最好能值多少。

	Bellman 期望方程	Bellman 最优方程
策略	已经给定的 π	还没定，正是要求的
对动作怎么办	按 π 的概率求平均	在所有动作里取最大
外层写什么	Σ_a π(a\|s)	max_a
解出来是谁	V^π：这个策略的分数	V⋆：所有策略里最好的分数
对 V 线性吗	线性——能直接解方程组	非线性——max 让它解不出闭式，只能一轮轮刷

最后一行是下一课整课的起点：那一个 max 决定了后面四个算法怎么分岔。至于 max 与 argmax 的区别：max 取的是那个最大的值，argmax 取的是达到它的那个动作，一个是数，一个是动作。

整族的关系收在一张表里：

关系	式子	一句话
V 由 Q 得到	V^π(s) = Σ_a π(a\|s)Q^π(s,a)	把固定住的第一步按策略平均掉
Q 由 V 得到	Q^π(s,a) = r(s,a) + γΣ_s′P(s′\|s,a)V^π(s′)	先走一步，剩下的交给 V
优势	A^π = Q^π − V^π	比按策略平均好多少
最优	V⋆(s) = max_a Q⋆(s,a)	平均换成取最大
最优策略	π⋆(s) = argmax_a Q⋆(s,a)	取的不是值，是动作

读别的书时的一个坑：记号不统一。Sutton & Barto 用小写 v_π、q_π，本讲义统一用大写 V、Q，含义完全一样。大小写也别混：r(s,a) 是奖励函数（给定 s、a 就确定），R_t+1 是某一次真的收到的那一个奖励。奖励的下标也有两种写法：这里的 R_t+1 指「在时刻 t 行动之后收到的」，也有书把同一项记成 R_t。看一个新公式先确认这两件事，能省掉大量对不上号的困惑。

4.8　Bellman 最优算子 T^⋆

把 4.7 那条 Bellman 最优方程的右边单独拿出来——就是 max_a 外加方括号里那一串「这一步的奖励 + 打折后落点的值」。方程里代进去的是 V⋆ 本身；现在改成随便喂它一张表 V，它照样算得出一张新表——这台「吃一张表、吐一张表」的机器就是算子。它就是 Bellman 最优算子 。费这个劲给它起个名字，是因为有了名字之后，下面两句才写得出来，而这一课后面全部结论都是它们的展开：

：刷 k 遍 = 同一个算子作用 k 次。「会不会收敛」于是变成「反复作用同一个算子会不会收敛」——这个问题数学里有现成答案（§6）。
：作用一次不变。Bellman 方程从 14 条等式合并成关于整张表的一个条件。

里没有乘法，所以不存在左乘右乘：它就是 () 省掉括号，像 sin x 就是 sin(x)。不是数、也不是矩阵，是一台作用；是被作用的那整张表。（策略定死的倒真能写成矩阵：是 14 维列向量，就是乘转移矩阵、乘、加奖励向量；但带着，非线性，写不成矩阵——这正是它难对付的根源。）

§ 5值迭代

§4 把该定义的都定义完了，可方程本身算不出任何一个数。这一节回答 §3 那张表「怎么算出来」。

值迭代：从任意一张值表出发，反复作用 T^⋆，直到表不再变化。得到的那张表就是 V^⋆。

为什么可以从任意一张表出发。你不知道 V^⋆，但可以先猜一张（全填 0 也行），再用 T^⋆ 把它改好一点：对每一格把 4 个动作试一遍，看「这一步拿多少 + 落到哪一格、那一格在旧表里写的是多少」，取最大的填回去；整张刷完得到一张新表。§6 会证明这个过程与起点无关，必然收敛到同一张表。

§4.8 那两条式子在这里各管一头：V_k = T^⋆V_k−1 说怎么往下走，V^⋆ = T^⋆V^⋆ 说走到哪儿停。

5.1　例：格 (2,2) 的一次备份

「一次备份」就是这台机器落到某一格上的动作：把这一格的 4 个动作试一遍，各算「当场的 −1 + 0.9 × 旧表里落点的值」，取最大写回去。一格一次备份；14 格全做一遍叫「刷一遍」。下面把其中一次展开——取格子 (2,2)，用已经收敛的 当旧表：

试的动作	当场拿到	落到哪	落点的值	合计 −1 + 0.9 × 落点值
上	-1.0	(1,2)	-2.7100	-3.4390
下	-1.0	(3,2)	-1.0000	-1.9000 ← 最大
左	-1.0	(2,1)	-2.7100	-3.4390
右	-1.0	(2,2)	-1.9000	-2.7100

三件事一起看。「右」撞的是货架，原地不动还得付这一步——所以它落回自己身上，这一路算出来是 −2.71。「上」和「左」一样差，因为都绕远了一格。而算出来的最大值 −1.9000，正好等于表里存的 (2,2)——而「不再变」说的是整张表：把作用上去，表里 14 个数一个都不变，这一格只是其中一个。

5.2　例：在仓库里刷一遍

下面这个组件就是这间仓库。每按一次「算一格」做一次备份，盯着数字从充电桩往外一圈圈变准。

交互 · 刷一遍 = 作用一次 T⋆

按「算一格」开始。每一格都是拿旧表的数字算的。

γ 0.90 打滑 0%

当前是第 0 轮本轮最大改动 — 离 V⋆ 还差 — γ^k = 1.000

灰格是货架（进不去），圈出来的是充电桩。每走一步 −1，撞墙或撞货架留在原地。深色边框的格子表示这一格已经和最终答案一致。把「打滑」打开，落点就变成三个格子的分布，每一步都要把三个落点的值按概率加权平均——注意收敛会立刻变慢。

前 6 轮并排放在一起，把「刷一遍，消息走一格」看得更死：

深色数字表示这一格已经和最终答案一模一样了。规律整齐得可以当定理背：离充电桩 d 步的格子，正好在第 d 轮变准——14 格无一例外。所以刷 7 遍之后整张表精确收敛（最远的格子离桩 6 步，第 7 遍确认没有任何改动）。

上一课那句「起点离奖励 50 步，就得刷 51 遍」，在这张 14 格的图上就是这条规律：信息只能顺着转移图一格一格往回传，一遍只走一格。

§ 6收敛性：γ-压缩与唯一解

§5 让值迭代跑起来了，7 遍之后表就不再变——可那是这间仓库的实测结果，不是保证。这一节给出保证。

要证的是两件事：凭什么值迭代一定收敛，而且不论从哪个 V₀ 出发都收敛到同一个 V^⋆。

先说清要证的是什么。

γ-压缩：对任意两个值函数 V、W，作用一次 T^⋆ 之后，两者的距离不超过原来的 γ 倍。
解存在且唯一：满足 T^⋆V = V 的值函数有且只有一个，它就是 V^⋆。

‖T⋆V − T⋆W‖_∞ ≤ γ ‖V − W‖_∞ （γ-压缩） V^⋆ = T^⋆V^⋆ （作用一次不变，且只有这一张）

读一遍：上一行说作用一次之后，两者的距离不超过原来的 γ 倍（‖·‖_∞ 的定义下面马上给）；下一行说「作用一次之后还是自己」的值函数只有一个，就是 V^⋆。
这里的值函数就是 §3 那种「每格一个数」的东西——存放形式是一张表，但定理讲的是它作为一个整体的性质，与你用表、用数组还是用网络存它无关。

这里的距离指的是：V 与 W 逐个状态作差，取差得最大的那个状态，记作 ‖V − W‖_∞——14 个格子里最大的那个差。sup 范数就是这个意思。

补一句：‖·‖_∞ 里那个 ∞ 是什么意思。双竖线是范数——给「一个东西有多大」定一个数。一列数 x = (x₁, …, x_n) 最常用的一族叫 p 范数：

‖x‖_p = ( |x₁|^p + |x₂|^p + ⋯ + |x_n|^p )^1/p

p = 1 是「全部加起来」，p = 2 是我们熟悉的直线距离。而 p 越大，最大的那一项就越占主导——让 p → ∞ 取极限，其余项全被压没，剩下的正好是绝对值最大的那一个：

‖x‖_∞ = max_i |x_i|

所以下标 ∞ 不是「无穷大」，是「p 取到无穷时的那个范数」。拿 x = (1, 4, 2) 试：‖x‖₁ = 7，‖x‖₂ ≈ 4.583，‖x‖₁₀ ≈ 4.033，‖x‖_∞ = 4。

为什么这一课非用它不可。把一整张值表看成一个 14 维的向量，两张表的距离就是「逐格差里最大的那个」。它保证的是最坏的那一格——一旦这个数小，每一格都小，没有例外。换成 p = 2 或者「平均差」，你只知道整体上差不多，完全可能有某一格误差很大。值迭代要的正是这种「没有一格坏」的保证。

它为什么又叫 sup 范数？sup 是上确界（supremum），格子有限时 sup 就是 max，两个词换着用没差别。但状态空间是连续、无穷多个的时候，最大值可能取不到（只能无限逼近），那时只能写 sup——教科书统一写 sup，就是为了把这种情况一并盖住。读法：‖V − W‖_∞ 念「V 减 W 的无穷范数」。

用现成的两张表看：第 3 轮和第 4 轮逐格相减，取绝对值——

14 个差里最大的是 0.729（有 7 格同时取到，图里描了边的那些），所以 ‖V₄ − V₃‖_∞ = 0.729。这个数你已经见过两次：组件里的「本轮最大改动」就是它，下面停机界那张表第 4 行的输入也是它。

这两件事合起来一次给出三个结论：V⋆ 存在且唯一、从任何初值出发都收敛、刷 k 遍误差最多剩 γ^k。下面从一行不等式开始——两个之差，不超过逐项之差里最大的那个：

| max_a A(a) − max_a B(a) |两边各自挑出最优，
再比这两个赢家差多少 ≤ max_a | A(a) − B(a) |先逐个动作比差，
再挑差得最多的那个

为什么右边一定不小：左边只有一对赢家可比，右边允许每个动作各挑自己最有利的那笔差。把 A、B 换成「同一格上，两张表各自算出的 4 个动作值」，证明就只剩下面四行。

现在任取两张表，盯住同一格 。这台机器在这一格上做的事是「4 个动作各算一个值，取最大」，两张表只是那个落点值不一样：

整条证明里只有第四行用到了 sup 范数，而它用的正是 sup 范数的定义：一个子集里的最大值，不会超过全集里的最大值。换成别的度量这一步立刻不成立——比如把「最大的差」换成「平均的差」，那 4 个落点的平均差完全可能大于全表的平均差（它们可能恰好是差最大的那 4 格）。Stage 1 的致命三角就是从换范数开始失效的，那里的投影算子只在「按数据分布加权的平均」下才有这条性质，两个范数对不上，这条链子就断了。

把其中一张取成真答案，就得到你要的那句话——因为作用一次之后还是它自己（）：每刷一遍，你离答案的距离最多剩 0.9 倍；刷 k 遍最多剩。距离只能往下掉、而且掉得不比几何级数慢，所以一定收敛，并且只能收敛到一个地方（Banach 压缩映射定理）。这条证明里没有用到「线性」「二次」「连续」中的任何一个，所以它在后面每一个 Stage 都还成立。

实测这间仓库前几轮的衰减比：0.7558 / 0.7092 / 0.6310 / 0.4737，几何平均 0.6327——比 = 0.9 还快。是上界，不是速度：真跑多快还取决于问题本身（这里是确定性最短路，所以第 7 遍直接精确归零）。

6.1　推论：停机判据

你不知道，所以「离答案还有多远」看起来没法算。但收缩性白送你一条只用相邻两轮就能算的界：

读一遍：只要这一轮整表最大的改动已经小于 ε，这张表离真答案就最多差 γε/(1−γ)——γ = 0.9 时就是 9ε。箭头左边那个量——相邻两轮的最大改动——你每轮都算得出来；箭头右边那个——离真答案还差多少——你算不出来。这条界的全部作用，就是拿前者换后者。

第 k 轮	本轮最大改动	界说「最多还差」	实际还差
1	1.0000	9.0000	3.6856
2	0.9000	8.1000	2.7856
3	0.8100	7.2900	1.9756
4	0.7290	6.5610	1.2466
5	0.6561	5.9049	0.5905
6	0.5905	5.3144	0.0000

界是保守的（第 1 轮：界说 9.0，实际 3.69），但它是你在不知道答案时唯一能算出来的东西。注意那个放大倍数 /(1−) = 9：它是这一课所有误差的公共放大器——迭代没刷够、模型不准、函数逼近有偏差，最后都要乘上它才是值函数上的误差。越接近 1，你对每一处近似的容忍度就越低（0.99 时这个倍数是 99）。

6.2　例：有限遍精确与几何逼近

那个 7 遍不是 γ 给的，是这间仓库的尺寸给的。确定性最短路有一条比收缩性更强的性质——预算够了就精确：离桩 d 步的格子，只要预算 k ≥ d，再多给也不会更好，所以 V_k(s) 直接等于 V⋆(s)，一格不差（上面「离桩 d 步的格子正好在第 d 轮变准」就是它）。最远的格子离桩 6 步，第 6 遍全表算准，第 7 遍用来确认没有改动，于是 7 ＝ d_max + 1。把 γ 换成 0.5、0.99、0.999 重跑，仍然是 7 遍——γ 只改每一格的数值，不改「消息要传几格」。

「V⋆ 不是 k→∞ 才有的吗，怎么 7 遍就到了？」因为极限不等于「要走无穷步才到」——1, 1, 1, … 的极限也是 1，第一项就到了。这里正是这一类：预算 k ≥ d 之后，多给的那些步根本没有奖励可拿（车已经停在桩里，奖励早就停了），于是 V_d ＝ V_d+1 ＝ ⋯ ＝ V⋆，序列从第 d 遍起就是常数。对照上一课那条链：s₄ 一直发分，预算每加 1 就还能多吃一口 γ^k−1——越来越小但永远大于 0，所以 V_k 严格递增、永远碰不到 6.5610，极限只在 ∞ 处取到，「66 遍」是人划的精度线，不是收敛。

那什么时候才轮到 γ 说话？一有随机性就轮到了。精确收敛是确定性独有的福利；把组件里的「打滑」打开，值迭代立刻退回几何逼近——永远差一点点，只能靠阈值停手。同一间仓库、同样 γ = 0.9，只是加了 10% 打滑：

停机阈值	确定性	打滑 10%
10⁻³	7 遍	13 遍
10⁻⁶	7 遍	19 遍
10⁻¹²	7 遍	32 遍

确定性那一列纹丝不动——它第 7 遍就精确归零了，阈值订多严都一样。§7 里说的「7 遍变成 32 遍」正是打滑那一列的最后一行（跑到机器精度）。在这种一般情形下，遍数由 γ 和精度一起定：把 ‖V_k − V⋆‖_∞ ≤ γ^k‖V₀ − V⋆‖_∞ 反解，要把误差压到 ε 需要

k ≥ ln( ε(1−γ) / R_max ) ⁄ ln γ

读一遍：要把误差压到 ε，至少得刷这么多遍。ε 订得越小、γ 越靠近 1，这个数越大。

γ	有效视野 1/(1−γ)	放大器 γ/(1−γ)	要刷几遍
0.5	2	1	8
0.9	10	9	66
0.95	20	19	149
0.99	100	99	917
0.999	1 000	999	11 508

最后一列取 ε = 0.01、R_max = 1、V₀ = 0。它是那条界给出的上界，真实问题常常快得多——但增长的量级就是这个：γ 每往 1 靠近一位，遍数大约乘 10。

所以「几遍」有两套算法，别混用。确定性最短路里遍数由距离决定，与 γ 无关；一旦有随机性，遍数由 γ 和精度决定，大致按 1/(1−γ) 涨。这间仓库里那个 7 不是一般规律——它是这一课每个数都能手算的原因，也是它最不像真实问题的地方。

判断该用哪一套，只要问两句：终点之后还发奖励吗？转移是确定的吗？三个例子并排：

	第 0 课五状态链	本课 4×4 仓库	仓库 + 10% 打滑
终点之后还发奖励	发（s₄ 每步 +1）	不发（进桩就停）	不发
转移	确定	确定	随机
收敛类型	几何逼近，永不精确	有限遍精确	几何逼近
遍数由谁决定	γ 和精度	距离（与 γ 无关）	γ 和精度
要刷几遍	66（ε = 0.01）	7 ＝ d_max + 1	13 / 19 / 32
怎么停	订阈值，看 Δ	整表不再改动	订阈值，看 Δ

链那一列的 66 遍是上一课算出来的（γ = 0.9，差距要小于 0.01）；打滑那一列的 13 / 19 / 32 对应阈值 10⁻³ / 10⁻⁶ / 10⁻¹²，就是上面那张表。同一间仓库，只是把落点从「一格」换成「三格的分布」，第一列的做法就整个失效了——精确收敛靠的是「预算够了就到顶」，而随机之后永远有一条越来越细的尾巴够不到底。

§ 7随机转移与期望

前面六节都站在一条没写出来的假设上：动作的结果是确定的——让它往右，它就一定往右。真机上不是。这一节只改这一条，看哪些结论跟着变、哪些不变。

只改一条规则：选定一个方向，有 10% 的概率被地面带偏——左右两个垂直方向各 5%。撞墙撞货架照旧算「留在原地」。

公式先变。确定性时「落点」是一个格子，查一个数就行；现在落点是三个格子上的概率分布，那一项就得按概率加权平均：

(T⋆V)(s) = max_a { −1 + 0.9 · [ 0.90·V(直走) + 0.05·V(偏左) + 0.05·V(偏右) ]方括号里这一项，就是 Bellman 方程里 E_s′ 的展开形式 }

两个容易漏的点：三个落点可以重复——贴着墙时偏出去的那一支撞墙又回到原地，同一个格子被算两次；而 −1 那一项不受影响——不管滑到哪，这一步的 −1 照样要扣。

7.1　一格对照

还是 §4.4 那一格 (2,0)。确定性时它的四个动作值是 −4.6856 / −3.4390 / −4.0951 / −3.4390（上 / 下 / 左 / 右）——「下」和「右」并列最优，值迭代按枚举顺序取了「下」。

同一格，打滑 10% 之后（旧表用打滑版收敛的值表）：

动作	落点分布	期望落点值	合计 −1 + 0.9 × 期望
上	90% → 格 (1,0)（-4.44） 5% → 格 (2,0)（-3.7536） 5% → 格 (2,1)（-2.9829）	-4.3328	-4.8995
下	90% → 格 (3,0)（-3.0579） 5% → 格 (2,0)（-3.7536） 5% → 格 (2,1)（-2.9829）	-3.089	-3.7801
左	90% → 格 (2,0)（-3.7536） 5% → 格 (1,0)（-4.44） 5% → 格 (3,0)（-3.0579）	-3.7531	-4.3778
右	90% → 格 (2,1)（-2.9829） 5% → 格 (1,0)（-4.44） 5% → 格 (3,0)（-3.0579）	-3.0595	-3.7536 ← 最大

平局被打破了，赢的是「右」。只差 0.0265，但方向很说明问题：从 (2,0) 往下走，两个偏移方向里有一个是左——那边是墙，滑过去白撞一下还留在原地。往右走，两个偏移方向（上、下）都是真格子。确定性时「贴着墙走」不付出任何代价；一旦会打滑，它就要付代价了。

所以准确的说法不是「最优策略翻了向」，而是：确定性时这两格各有两个并列最优，打滑把平局打破了，随机性挑走了离墙远的那个。这是「鲁棒」两个字第一次以数字的形式出现。另一格 (2,1) 的原因完全相同。

把上面这套算法接到组件上——默认就带 10% 打滑，每一步的算式行会把三个落点的概率、值和加权和全部列出：

交互 · 打滑之后的同一个算子

按「算一格」开始。算式里那个方括号，就是三个落点按概率加权的期望。

γ 0.90 打滑 10%

当前是第 0 轮本轮最大改动 — 离 V⋆ 还差 — γ^k = 1.000

把打滑拉回 0%，收敛立刻回到 7 遍；拉到 40%，值继续变差、边角的格子会更明显地绕开墙走。注意「离 V⋆ 还差」这一栏——随机之后它不再归零，只是越来越小。

值全线变差：左上角从 -4.6856 掉到 -5.0279。打滑让你平均要多走几步，值就得更差一点。
两格的最优动作被改写：(2,0) 和 (2,1)，都是上面那种「平局被打破，改选离墙远的那个」。
收敛从 7 遍变成 32 遍：确定性时值迭代是有限步精确收敛；随机之后它才真正变成「几何逼近」——每遍只把误差乘掉一个左右，永远差一点点。

这一改动是通往 Stage 1 的门。上面那三个数 0.90 / 0.05 / 0.05，是我写规则时定的。真机上没人会给你它们——地面多滑、轮子会不会空转，你只能推一下看看去哪了。期望算不出来，就只能拿样本去估：把方括号里那一项换成「我这次实际滑到的那一格」，就是下一课的全部内容。

§ 8表格法的三个前提

§7 把例子改得更像真机了，但整套做法仍然站在三个前提上。这一节把它们逐条列出来，并指出各自由后面哪一步接手。

这间仓库里值迭代做得很彻底：52 个状态-动作对，7 遍扫描，误差有界、什么时候能停也算得出来。而这份彻底是三个前提换来的，真问题里一个都不成立。每失效一个，就对应后面的一步：

这一课默认成立的	真问题里为什么不成立	由此引出
状态能一个个枚举 14 格全刷一遍	换成 100×100 的仓库图，再加上朝向与载货状态，格数指数级增长；机械臂 6 个关节各分 121 格就是 9.85×10²⁴ 格——表存不下，也刷不完	Stage 1 ③ 把表换成函数：值函数逼近
转移规则在你手上落点直接查规则	真机上地面多滑、轮子打不打转、货架有没有被挪走，没人会告诉你。你能拿到的只有一条条采样出来的轨迹	Stage 1 ① 期望换采样：Q-learning
动作能枚举，取 max 是精确的 4 个方向逐个试	连续的速度与转角没法逐个试；就算硬离散化，动作数也随关节数指数级涨	Stage 2 ① 不再枚举：直接把策略当参数优化

三条不是各自独立失效的，前两条同时失效时最危险。状态多到必须用函数逼近，模型又拿不到、只能靠自举，再加上 off-policy，三者凑齐就是致命三角。此时 §6 那套收缩论证的前提当场消失：那里的每一步都建立在「反复作用同一个算子、每一格独立地被精确更新」之上，而函数逼近意味着改一格会牵动一片，自举意味着目标自己也在动。定理没了，收敛就不再有保证——Stage 1 ④ 要补回来的正是这一样东西。

§ 9习题

四道题都能在 §5 的控件里直接拉，或者改两行 code/grid_dp.py 重跑。每题先自己写下预测的数，再展开对答案。

1 · 把从 0.9 调到 0.5，再调到 0.99。先预测：轮数会变吗？值会怎么变？

答案

换成 0.5 / 0.9 / 0.99，轮数都是 7（确定性最短路，轮数由最远格子的距离定，与无关），变的是值和视野：

	有效视野	左上角的值	刷几遍
0.50	2.0	-1.9688	7
0.90	10.0	-4.6856	7
0.99	100.0	-5.8520	7

2 · 把货架挪到 (2,2)，堵死斜穿的那条路。重跑一遍，看哪些格的最优动作翻了向——你会发现值函数的形状记住了地图。

答案

把 (1,1) 的货架挪到 (2,2) 之后，它和 (2,3) 连成一堵横墙，右上角那四格再也不能顺着右边下来。

翻向的只有两格，方向都是掉头去走左边那条竖道：(0,1) 由「右」改成「下」，(1,2) 由「下」改成「左」。绕路的代价逐格记在值里——

格子	挪之前 d	挪之前的值	挪之后 d	挪之后的值
(0,2)	4	-3.4390	6	-4.6856
(0,3)	5	-4.0951	7	-5.2170
(1,2)	3	-2.7100	5	-4.0951
(1,3)	4	-3.4390	6	-4.6856

两张地图共有的格子里，另外八格一个数都没动（原来的货架 (1,1) 现在空了出来，离桩 4 步，值 -3.4390），包括左上角的 -4.6856——AGV 从 (0,0) 出发本来就走左边那条道，这堵墙挡的是别人的路。(0,1) 也一样：值没变，只是它原来那条等长的向右绕法被封了，平手换了个人赢。

闭式解 -10(1-0.9^d) 仍然逐格对得上：地图换了，尺子没换——值函数的形状记住的是这张地图，不是某一条路。最远的格子从 6 步变成 7 步，值迭代也就从 7 遍变成 8 遍：轮数由最远距离定，这条规律跟着地图一起变。

3 · 把打滑从 10% 加到 40%。看最优策略还敢不敢贴着货架走。

答案

打滑从 10% 提到 40%，最优策略一格都没有再变——翻向的仍然只有 §7 里那两格 (2,0)、(2,1)（「下」改「右」）。

两个值得看的点。第一，为什么加大打滑不再改策略：那两格在确定性下本来就是平手（两条同样 4 步的路），打滑做的事是把平手破开；一旦破开，最优动作就定下来了，滑得再厉害也不会换。第二，它还敢不敢贴着货架走：敢。(1,2) 在 40% 打滑下仍然选「下」（-4.7528，比往「左」绕的 -5.2451 好 0.49），(2,2) 也仍然选「下」。原因在偏移的落点上：从 (1,2) 往下走，往左滑的那一支撞在货架 (1,1) 上，原地不动只亏这一步，不会把车带到另一条路上去。货架在这里挡住了偏移，贴着它走反而是抗打滑的走法。

真正随打滑一起涨的是代价和轮数：

打滑	(0,0) 的值	刷几遍到 1e-12	翻向的格子
0%	-4.6856	7	——
10%	-5.0279	32	(2,0)、(2,1)
40%	-6.5699	80	(2,0)、(2,1)

轮数为什么涨了这么多。确定性时值迭代 7 遍就精确到底：每一格的值是一个有限项的和（最远 6 步，走到就结束）。一带上概率，车永远有一支还在路上，这个和变成一条无穷长的级数，只能按几何速度一遍遍往下逼近——收敛的速度上界由 0.9 定死，收敛的时刻由你要的精度定。

「鲁棒」在这张图上值多少。把确定性算出来的策略原样放到 40% 打滑的环境里评估（只做策略评估，不重算），(0,0) 比重算过的策略只亏 0.0589，亏得最惨的 (2,1) 也只亏 0.2303。所以打滑改变的主要不是走法，而是值本身：同一格从 -4.69 变成 -6.57。策略的鲁棒性和值的鲁棒性是两件事，这里第一次分开。

4 · 把「旧表快照」拿掉。现在的值迭代握着两张表：一轮开始先把旧表冻成一份快照，14 个格子全都查这份快照，整轮算完再整表替换（src = 快照 → 结果写进 new → V = new）。现在把冻快照那一步删掉，改成算完一格就立刻写回同一张表，其它一个字不改。
跑之前先押三个答案：① 它还收敛吗？② 收敛到的还是同一张 V⋆ 吗？③ 遍数会变吗？
然后把另外两个旋钮各试几档——初值（全填 0 / 全填 +100 / 全填 −100）、扫描顺序（从 (0,0) 正序 / 从充电桩 (3,3) 倒序），十二组跑完，看哪一组和别人不一样。

答案

先给结论，三句话：① 收敛，而且是必然收敛；② 收敛到的还是同一张 V⋆，逐格最大差 0.0；③ 遍数在十二组里有 7 组是 7 遍、4 组是 30 遍（全填 +100 那档），只有一组掉到 3 遍——而那一组的功劳并不在「一张表」上。

下面把话说细。先钉住表头那两个词，它们说的是同一张值表怎么写回去：

同步更新（两张表）：整张表全部算完再交换。每一格都拿同一张旧表的数字算，就是正文那句 V_k = T^⋆V_k−1。
原地覆盖（一张表）：算完一格立刻写回原表。同一遍里排在后面的格子，读到的已经是这一遍刚更新过的邻居。

另外两个旋钮：初值是第 0 轮全填什么（充电桩那格恒为 0）；扫描顺序是一遍之内按什么次序走格子——正序从 (0,0) 逐行扫到 (3,3)，倒序从充电桩 (3,3) 倒着扫回 (0,0)。三个旋钮（写回方式 2 × 初值 3 × 扫描顺序 2）组合出十二行，其中只有一行与众不同：

写回方式	初值	扫描顺序	刷几遍收敛
同步更新（两张表）	0	正序	7
同步更新（两张表）	0	倒序	7
同步更新（两张表）	100	正序	30
同步更新（两张表）	100	倒序	30
同步更新（两张表）	−100	正序	7
同步更新（两张表）	−100	倒序	7
原地覆盖（一张表）	0	正序	7
原地覆盖（一张表）	0	倒序	7
原地覆盖（一张表）	100	正序	30
原地覆盖（一张表）	100	倒序	30
原地覆盖（一张表）	−100	正序	7
原地覆盖（一张表）	−100	倒序	3

十二行的终值全都收敛到同一张 V^⋆（逐格最大差 0.0）——怎么写回、按什么顺序扫、从哪儿起步，都不影响答案是谁，只影响多久到。而「多久到」只在最后一行被改善了：原地覆盖单独拿出来一点用没有，倒序单独拿出来一点用没有，悲观初值单独拿出来也一点用没有，三个凑齐才从 7 遍掉到 3 遍。

为什么全填 0 的时候倒着扫也没用？因为在「每步 −1」的问题里，0 是一个过分乐观的初值：会一直挑那些还没更新过、仍然写着 0 的邻居，你把更新顺序排得再好也传不出去。换成悲观初值（全填 −100）再从充电桩倒着扫，一遍之内就能顺着「桩 → 一步邻居 → 两步邻居」把真值一路推出去，3 遍见底——就是表里最后那一行。

但别把这份提速算到「一张表」头上。原地覆盖本身不提速——六个原地配置里五个都是 7 遍或 30 遍，和两张表逐行打平。它真正的作用是让「扫描顺序」这个旋钮存在：两张表时每一格都读同一份冻住的快照，你按什么次序去填新表，填完都一模一样，顺序在数学上根本不起作用。所以一张表是前置条件，不是加速器；那 3 遍是顺序与初值凑出来的，而且是在「目标在角落、倒序几乎完美贴合信息流向、只有 14 格」这种最好情况下。

反过来看就清楚了：两张表在表格里的成本几乎为零——不比一张表慢，只多一份内存。所以后面真要放弃它，绝不会是为了速度：一旦值不再存成表、而是由一组共享参数算出来，「冻住的旧表」就没有现成的东西可对应，那份白拿的保证也就跟着没了。

§ 10本章小结

整章的概念收在下面这张图里。每一格三行：名字、式子、一句能读懂的话——箭头是「怎么从上一个推出下一个」。名字记不住不要紧，先看那句话和那个箭头。

三句话把这一章串起来。
① 答案是一张表。问题写成 MDP 之后，你要的东西就是 14 个数：V⋆(s) = 从这一格最优地走下去能拿多少。它满足 V⋆ = T⋆V⋆，但这是一致性条件——照着它本身算不出任何东西。
② 算法是反复作用同一个算子。T⋆ 输入一张表、输出一张表，在 sup 范数下是 γ-压缩；Banach 于是同时给出两件事：这样的表只有一张、从任何初值出发都收敛，刷 k 遍误差最多剩 γ^k。整条证明只用到「γ-压缩」这一件事，所以后面每个 Stage 都还成立。
③ 误差都要过同一个放大器。你能拿来停机的只有后验界，倍数 γ/(1−γ)，本课是 9 倍。不管误差出在哪一步，最后都要乘上它。

而这一切站在三个前提上：格子能枚举、转移 P 在手、max 取得精确。真问题里一个都不成立——§8 把这三条逐条列出，并指出各自由后面哪一步接手。

← 上一章值函数与最优值函数下一章 →动态规划

§ 1示例：4×4 仓库网格

§ 2MDP 的五个要素

§ 3最优值函数 V⋆ 与它的闭式解

3.1 折扣因子 γ

§ 4值函数、Bellman 方程与最优算子

4.1 回报 G

4.2 策略 π

4.3 状态价值 Vπ

4.4 动作价值 Qπ

4.5 优势 Aπ

4.6 Bellman 期望方程

4.7 Bellman 最优方程

4.8 Bellman 最优算子 T⋆