CS234 L2 · 已知世界模型 · 放映厅

知识点 1

开场

1 / 82

讲解

L1 建的是词汇表，L2 开始有定理。这一讲的设定是：转移和奖励都直接交给你，唯一的问题是后果被延迟时该怎么行动。Brunskill 分三层搭形式化 —— 马尔可夫过程、马尔可夫奖励过程、马尔可夫决策过程 —— 然后给出两个规划算法和两条收敛论证。本片仍按六拍走，其中第二拍会同情地说出一个貌似合理的错误模型，第五拍再回去指名杀掉它。这么做有实证依据：直接撞击学习者已有的错误模型，其效应量在教学研究里稳定落在 d≈0.79–0.83（Muller 等，2008）。它和「动画 vs 静态图」的效应（d≈0.37）不是同一条量表上可以相除的两个数，但前者的量级确实大得多。干净的讲解会让人觉得更清楚、更省力，而这恰恰是问题 —— 没有碰撞，新解释会被归档在旧模型旁边，而不是替换掉它。还有一件事要先说明：这一讲有 19 处证明被跳过，其中好几处是承重的。本片会在它们出现的地方明确标出来，而不是假装讲座讲全了。

知识点 2

1 · 「链会忘掉起点」缺了两个前提

2 / 82

d_{t + 1} = d_{t} P P [s] [s^{'}] = P (s^{'} ∣ s)

讲座开头（约 00:07:01）断言「链跑得够久就收敛到平稳分布、与起点无关」。在这条链上它是假的，而前提一个都没说。

讲解

L2 的头七分钟在建马尔可夫过程，其中有一句听上去人畜无害的话：链跑久了会收敛到一个平稳分布，而且与起点无关。她没有加任何条件。屏幕上这条链只有两个状态，转移是确定的：A 必去 B，B 必回 A。它是一条完全合法的马尔可夫链。我们马上会看到，它的分布永远不收敛——不是收敛得慢，是根本不收敛。先说明记号：这一讲从头到尾没有固定 P 是行随机还是列随机。她在学生提问时反复说「取决于你怎么记，要不要转置，它会在左边或右边」。本片统一用 P[s][s′] = P(s′|s)、分布是行向量、右乘 P，值函数写成 V = R + γPV。你在读别的书时务必先确认对方用的是哪一套。

3 / 82

马尔可夫链会忘掉起点跑得足够久，从哪出发都一样

这个直觉大部分时候是对的 —— 这正是它危险的地方。

讲解

这个错误模型值得同情，因为它在你遇到的绝大多数链上都成立。随机性确实会把初始信息抹平，这是「混合」的图像，而且它是对的——在满足条件的时候。问题在于，这个直觉把「有随机性」当成了充分条件。它不是。刚才那条 A↔B 链一点随机性都没有，可它仍然是一条马尔可夫链；而即使加了随机性，只要周期结构还在，分布照样不收敛。真正的条件有两条，讲座一条都没说：不可约（任何状态都能到达任何状态）与非周期（回到自身的步数的最大公约数是 1）。加上有限状态，才有 Perron–Frobenius 给出的唯一平稳分布与收敛性。

4 / 82

d_{t} (A) = Pr (s_{t} = A) d_{0} = (1, 0)

读法：横轴是时间，第 t 根柱子是「时刻 t 在 A 的概率」—— 这不是一条轨迹，是概率的演化。

讲解

接下来三镜都用同一张图：横轴是时间 t，第 t 根柱子的高度是「时刻 t 处在状态 A 的概率」。收敛就是柱子最终停住，不收敛就是柱子永远在动。这里有个本讲学生问答里被反复追问的混淆，值得先拆开：这排柱子画的是概率分布的演化，不是某一条轨迹。智能体在任何一个时刻都只处在一个状态里，不会同时在 A 和 B。d_t 是对所有可能轨迹取平均之后的东西。

5 / 82

P = (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}) d_{0} = (1, 0)

周期 2：d = (1,0),(0,1),(1,0),… 永远震荡，不收敛 —— 起点的奇偶性一步也没被抹掉。

讲解

看什么：看柱子有没有停下来。从左到右一根根出现，高度在 1 和 0 之间来回跳，到最后一根仍然在跳。它不是收敛得慢，是根本没有在靠近任何一个值。　—— 这就是反例，两行就能写完。P 是一个置换矩阵，d₀=(1,0)，于是 d₁=(0,1)，d₂=(1,0)，……分布在两点之间永远震荡。注意它一点信息都没忘：只要告诉我现在是第几步，我就能倒推出起点在哪。所谓「跑久了就忘掉起点」在这条链上完全失效。有一个常见的补救说法：取时间平均。Cesàro 平均确实收敛到 (0.5, 0.5)，这也是为什么很多教材在这里会加上「时间平均意义下」。但讲座说的是分布本身收敛，而分布本身不收敛。这个区别在后面学到策略的状态占用测度（state occupancy measure）时会再次出现，届时它是承重的。

6 / 82

P = (\begin{matrix} 0.9 & 0.1 \\ 0.2 & 0.8 \end{matrix}) d_{0} = (1, 0)

非周期且不可约：d_t(A) = 2/3 + (1/3)·0.7^t → 0.667。偏离量按 0.7 的幂衰减，这次真的收敛。

讲解

看什么：还是看柱子有没有停下来。这一次高度是单调地往下压，每一根比前一根更靠近 0.667，最后几根几乎一样高。和上一镜的来回跳形成直接对照。　—— 只改一件事：给两个状态都加上自环，让 P 变成 0.9/0.1 与 0.2/0.8。链立刻变成不可约且非周期，于是分布收敛到唯一的平稳分布 (2/3, 1/3)。收敛是几何速率的：d_t(A) = 2/3 + (1/3)·0.7^t，那个 0.7 是 P 的第二大特征值。第一大特征值恒为 1（行随机矩阵必然如此，右特征向量是全 1 向量），决定混合速度的是第二大的那个。这个事实在 KP3 讲 (I−γP) 可逆时会再用一次。从 B 出发是 d_t(A) = 2/3 − (2/3)·0.7^t，从下方逼近同一个 0.667 —— 这才是「忘掉起点」该有的样子。

7 / 82

指名反驳：随机性不是充分条件。三者齐备才有唯一平稳分布 + 与起点无关的收敛。（本讲共 19 处跳过的证明，本片逐处标注。）

讲解

指名回去：「有随机性所以会混合」是不充分的。要的是不可约与非周期，加上有限状态，这才是 Perron–Frobenius 定理的前提。两个前提各自对应一类反例。缺非周期，就是刚才那条 A↔B 链，分布永远震荡。缺不可约，取两个互不连通的吸收态，极限分布完全由你从哪边出发决定——这时候「与起点无关」错得更彻底。为什么要在导论性的一句话上花一整集：因为这句话后面会被反复使用。策略的状态占用测度、平均奖励设定下的最优性、以及 TD 学习的收敛性分析，全都建立在「该链有唯一平稳分布」之上。如果你把这个条件当成自动成立的，那么在周期性或不可约性被破坏的环境里（多智能体交替行动、带有不可逆失败态的机器人任务），你会得到一个默默不成立的结论。

8 / 82

知识点 1 · 总结

「链跑久了会忘掉起点」缺了两个前提

核心结论

反例两行：P = [[0,1],[1,0]]，d₀=(1,0) ⟹ d 在 (1,0) 与 (0,1) 之间永远震荡，不收敛。

底层机制

正确条件是不可约 + 非周期 + 有限状态（Perron–Frobenius），讲座一条都没说。

常见误解

误解：「有随机性就会混合」。随机性既不必要也不充分 —— 决定收敛的是链的图结构。

与你的考试

收敛速率由 P 的第二大特征值给出：例中 0.7，故 d_t(A)=2/3+(1/3)·0.7^t。

9 / 82

知识点 1 · 检验

P = [[0,1],[1,0]]，d₀ = (1, 0)。关于 d_t 当 t→∞，下面哪句是对的？

知识点 3

2 · 算值函数的三条路：代价不同，能走多远也不同

10 / 82

V (s) = R (s) + γ \sum_{s^{'}} P (s^{'} ∣ s) V (s^{'})

同一个 V，三条求法。差别不在正确性，在代价与可迁移性。

讲解

MRP 的 Bellman 方程只有一行：状态的值等于它的即时奖励，加上 γ 乘以后继状态值的期望。讲座给了三条求解路径，并且难得地把代价也讲了。先把一个记号陷阱说清楚。这里写的是 R(s)，奖励按当前状态编号；Sutton & Barto 写的是 R(s)=E[R_{t+1}|S_t=s]，奖励按下一时刻编号。两者差一格。本讲之后引入动作时又会悄悄换成 R(s,a)，而方程本身没有重写。你在对照两本书的公式时，第一件要核对的就是这个下标。

11 / 82

有闭式解就该用闭式解迭代是没有解析解时的退而求其次

这个排序在数值分析课上通常是对的 —— 精确解优于迭代解。

讲解

这个错误模型来自一个真实而且通常正确的经验：在数值分析里，能写出解析解就别去迭代。解析解精确、一步到位、不需要选步数、不需要判收敛。讲座本身也确实把闭式解摆在了显眼位置，而且它是这一讲里唯一「写得出来」的解。所以把它当作正统答案、把迭代当作退路，是很自然的读法。接下来三镜会给出三个理由，说明在 RL 里这个排序是反的。

12 / 82

V = R + γ P V ⟹ (I - γ P) V = R ⟹ V = (I - γ P)^{- 1} R

统一的试验台：7 格火星车走廊，奖励只有两端非零，固定策略「一直向右」。

讲解

本片后面所有数字都出自这一个 MRP：七个状态排成走廊，s₁ 给 +1，s₇ 给 +10，中间全是 0，γ=0.9。固定策略「一直向右」，每一步有一半概率真的右移、一半概率原地不动。把 Bellman 方程写成向量形式 V = R + γPV，移项得 (I−γP)V = R，再求逆就是闭式解。这一步代数上只有三个动作，但它要求 (I−γP) 可逆——那是下一集的内容，而且讲座把它当成了一句顺口的话带过。

13 / 82

V_{k + 1} (s) \leftarrow R (s) + γ \sum_{s^{'}} P (s^{'} ∣ s) V_{k} (s^{'}) V_{0} = 0

V₁：一轮扫描只走了一步 —— 只有 s₇ 和 s₁ 知道自己拿了奖励，其余六个仍是 0。

讲解

看什么：看柱子出现的顺序：从最右边 s₇ 开始，一根根往左冒。这个顺序就是回代顺序 —— 每个 V(sᵢ) 都要等 V(sᵢ₊₁) 算完。也注意这一轮左边六根几乎都还贴着地面。　—— 从 V₀ = 0 开始扫第一轮。每个状态取自己的即时奖励，加上 γ 乘以后继的旧值——而旧值全是 0，所以第一轮结束时只有本身带奖励的 s₁ 和 s₇ 非零。这就是动态规划的图像：奖励的信息每扫一轮只能往外传一格。她在课上专门用嘴描述过这件事（「s₇ 很好这个事实会慢慢往回流」），而这正是静态公式最藏不住又最说不清的部分。所需扫描轮数因此和状态图的直径同阶。

14 / 82

V_{5} （第 5 轮扫描后）

V₅：锋面推进到 s₃ 附近就熄灭了。柱顶数字：s₃=0.41 很小但非零，s₂=0.00 精确为零。

讲解

看什么：看柱子从右往左在哪里熄灭：s₇ 到 s₄ 明显立着，到 s₃ 附近就贴地了。这条熄灭线就是传播锋面，它每轮向左推进大约一格。s₂ 与 s₃ 谁是精确的 0、谁只是很小，看柱顶的数字，不要看柱高 —— 在这个量程下它们都不到一个像素。　—— 第五轮。右侧四个状态已经有了可观的值，而锋面刚好推到 s₃；s₂ 仍然精确地等于 0。这里可以读出两件事。一是扫描轮数与距离的关系：s₂ 离 +10 有五步，所以它至少要第六轮才可能非零。二是这些中间值全都不是任何策略的值函数，它们是「只剩 k 步可走」时的值——这个观察在 KP8 会变成一个正式的陈述，也是值迭代最容易被误读的地方。还有一个细节值得注意：s₁ 的 1.79 不是从右边传过来的，而是它自己的 +1 在原地累积。两股信息在走廊中间相遇。

15 / 82

V_{\infty} = (I - γ P)^{- 1} R 与迭代到收敛的结果逐位相同

收敛值：V(s₇) = 10/(1−0.9) = 100，正是 R_max/(1−γ) 那个界取到等号。三条路算的确实是同一个 V。

讲解

这是收敛后的 V。闭式解 (I−γP)⁻¹R 与迭代到收敛的结果逐位相同——讲座里说三种方法给出同一个量，但从未验证过，这里用同一组数字核对了一遍。右端 V(s₇)=100 恰好等于 10/(1−0.9)，也就是 L1 给出的界 R_max/(1−γ) 在此处取到等号：s₇ 永远拿 +10，不多不少。左端 V(s₁)=31.82 不是 1/(1−0.9)=10，因为这个策略会把它带离 s₁ 去吃 +10。顺带一提，讲座里那个 s₆ 的手算示例（约 00:41:49）口述成「0 加 0.5 乘 0 加 0.5 乘 10」得 5，但她写在板上的式子是 0 + γ(0.5·V(s₆)+0.5·V(s₇))，γ=0.5 时应得 2.5。以写出来的式子为准。

16 / 82

指名反驳：闭式解是这一讲的终点，迭代是整门课的起点 —— 它此后再没出现过。

讲解

指名回去。第一，闭式解只在固定策略下成立。控制问题里 Bellman 最优方程带着 max_a，它是非线性的，没有矩阵可以求逆——这是最要命的一条。第二，代价。求逆是 |S|² 到 |S|³，而迭代每轮是 |S|²，并且误差按 γ^k 几何衰减，要多准有多准。这里必须注意一个她没说的事：|S|² 这个数字对 MRP 或固定策略是对的，对值迭代不对——值迭代每轮是 |S|²|A|，因为每个状态都要遍历所有动作。不要把 |S|² 直接搬过去。第三，也是最重要的：迭代这条路能继续往下走。加上动作就是策略评估，加上 max 就是值迭代，把模型拿掉就是 L3 的时序差分。闭式解在这一讲之后再也没有出现过。至于蒙特卡洛：它的优势是完全不需要模型，代价是误差只按 N^(−1/2) 衰减。讲座说「有数学界可以告诉你需要多少次模拟」但没有点名——那是 Hoeffding 不等式，L3 会用到。

17 / 82

知识点 2 · 总结

闭式解是这一讲的终点，迭代是整门课的起点

核心结论

三条路给出同一个 V（已逐位核对）：MC 误差 N^(−1/2)、闭式 |S|³、迭代每轮 |S|² 且误差 γ^k 衰减。

底层机制

关键差别不是精度，是可迁移性：加 max_a 后方程非线性，闭式解失效，而迭代原样能用。

常见误解

误解：「迭代是没有解析解时的将就」。反了 —— 闭式解才是只在固定策略这一特例下成立的。

与你的考试

每轮复杂度：MRP/策略评估 |S|²，但值迭代是 |S|²|A|，讲座没说，别直接搬。

18 / 82

知识点 2 · 检验

为什么控制问题（求 V*）里不能用 V = (I − γP)⁻¹R 这条路？

知识点 4

3 · (I−γP)⁻¹ 为什么一定存在，γ=1 时又为什么真的塌掉

19 / 82

V = (I - γ P)^{- 1} R

课上有学生问了，讲座「先记下，回头答」，约 00:41:08 才用一句谱半径带过 —— 而那句话也没证。

讲解

上一集把 (I−γP)V=R 求了逆，就默认了它可逆。这件事课堂上有学生当场问过，她先记下，四十分钟后才回来用一句话答掉：P 是随机矩阵所以特征值模长不超过 1，因此 γ<1 时 I−γP 没有零特征值。这个回答是对的，但那句「随机矩阵的特征值模长不超过 1」本身在讲座里是断言，不是推导。它其实一行就能证，这一集会补上。更值得追问的是反面：什么时候它真的不可逆？答案不是什么病态的构造，而是一个你一定会遇到的取值。

20 / 82

可逆性是个数值问题大多数时候没事，碰到病态就换算法

这个模型对随机取来的矩阵是对的。但 I − γP 不是随机取来的。

讲解

这个错误模型来自线性代数课的经验：随手写一个矩阵，它几乎必然可逆，奇异矩阵在参数空间里是零测集。于是可逆性被归档成一个数值问题——条件数大就换个求解器。对随机取来的矩阵，这完全正确。但 I−γP 不是随机取来的：P 的每一行都恰好加到 1，这是一个刚性的代数约束，而它会在 γ=1 时精确地制造出一个奇异矩阵。不是「接近奇异」，是精确奇异。

21 / 82

\sum_{s^{'}} P (s^{'} ∣ s) = 1 对每个 s ⟺ P 1 = 1

这不是巧合也不是近似 —— 它就是「概率加起来等于 1」这句话本身。由此一行得到 ρ(P) ≤ ‖P‖_∞ = 1。

讲解

先把「行随机」翻译成特征值的语言。每一行加起来等于 1，写成矩阵形式就是 P 乘全 1 向量等于全 1 向量——也就是说，1 是 P 的特征值，全 1 向量是对应的特征向量。这不是近似，也不是通常情况，它就是概率归一化这句话本身。顺手把讲座断言的那句补上：行和范数 ‖P‖_∞ 等于最大的行绝对值和，对随机矩阵恰好是 1；而谱半径不超过任何一个算子范数，所以 ρ(P) ≤ 1。一行，不需要 Gershgorin。于是 γ<1 时，γP 的所有特征值模长不超过 γ<1，1−γλ 不可能为零，I−γP 可逆。

22 / 82

(I - γ P) 1 = 1 - γ P 1 = 1 - γ 1 = (1 - γ) 1

柱高 = (1−γ)。再往下画不出来：γ=0.99 时是 0.01（约 3px），γ=1 时精确为 0。

讲解

现在做一件很短的事：把全 1 向量代进 (I−γP)。因为 P·1 = 1，结果是 (1−γ)·1。这一行同时给了两个结论。第一，(1−γ) 是 I−γP 的一个特征值，全 1 向量是对应的特征向量。第二，当 γ→1 时这个特征值趋于 0——矩阵越来越接近奇异，条件数按 1/(1−γ) 爆炸。γ=0.99 时它已经是 0.01，γ=0.999 时是 0.001。柱子画的就是这个特征值随 γ 的变化。最右边 γ=1 那根高度精确为 0：不是很小，是零。

23 / 82

γ = 1 : (I - P) 1 = 0 ⟹ I - P 奇异

γ = 1 时 I − P 精确奇异：给所有状态同加常数 c，方程依然成立 ⟹ 解不唯一 ⟹ 不可能有逆。

讲解

γ=1 时，(I−P)·1 = 0。一个非零向量被映成零向量，所以 I−P 的零空间非平凡，它精确奇异——不是数值上接近奇异，是代数上不可逆。这件事有一个不依赖矩阵的解释，而且更好记：γ=1 时，如果 V 是 V = R + PV 的一个解，那么 V + c·1 也是解，因为 P(c·1) = c·1，常数原样穿过去。解成了一整条直线，而有唯一解是可逆的同义词，所以不可能可逆。这不是一个病态的角落。平均奖励设定（average-reward RL）用的就是 γ=1，它必须另起炉灶，用相对值函数和 Poisson 方程来处理这个常数自由度。你在读连续控制或排队论方向的 RL 论文时会直接撞上它。

24 / 82

指名反驳：不是「通常可逆偶尔病态」，是 γ 一个参数完全决定的二分 —— 与 P 的具体数值无关。

讲解

指名回去。对 I−γP 而言，可逆性完全不取决于 P 的具体数值。γ<1 时必可逆，γ=1 时必奇异，中间没有「通常可逆、偶尔病态」这回事。这是代数结论，不是数值经验。但代价是连续的：条件数大约按 1/(1−γ) 增长。γ=0.99 时已经在 100 的量级，γ=0.999 时是 1000。所以在长时域问题上，闭式解即使理论上存在，数值上也越来越不可用——而这恰好是迭代法反过来占优的区间。最后标注一处跳过的证明：她断言了「随机矩阵的特征值模长不超过 1」而没有给论证。本集用 ρ(P) ≤ ‖P‖_∞ = 1 补上了，一行。这一讲这样的地方共有 19 处，本片会逐处标出来。

25 / 82

知识点 3 · 总结

(I−γP) 的可逆性由 γ 完全决定，与 P 的数值无关

核心结论

行随机 ⟺ P·1 = 1 ⟹ (I−γP)·1 = (1−γ)·1。γ<1 必可逆；γ=1 时精确奇异。

底层机制

γ=1 的解不唯一：V 是解则 V+c·1 也是解，常数原样穿过 P。有唯一解 = 可逆。

常见误解

误解：「可逆是数值问题，偶尔病态」。这里是代数二分，没有中间地带。

与你的考试

代价连续：条件数 ~ 1/(1−γ)。γ=0.99 → 100 量级，长时域下闭式解数值上也失效。

26 / 82

知识点 3 · 检验

γ = 1 时 (I − P) 为什么不可逆？

知识点 5

4 · 固定策略把 MDP 塌回 MRP

27 / 82

V^{π} (s) = E_{π} [r_{t} + γ r_{t + 1} + γ^{2} r_{t + 2} + \dots ∣ s_{t} = s]

MDP = MRP + 动作：每个状态不再只有一条出边。那 MRP 那三把工具是不是要重造？

讲解

把动作加进来，每个状态就不再只有一条出边。火星车的每一格都可以选择向左或向右，于是转移概率变成 P(s′|s,a)，奖励变成 R(s,a)。这里有一个记号断层要提前说破：MRP 的 Bellman 方程是用 R(s) 写的，而 MDP 这里悄悄换成了 R(s,a)，方程本身没有重写一遍。读者得自己把带动作下标的形式推回去。这是这一讲最容易在做题时卡住的地方之一。现在的问题是：蒙特卡洛、闭式解、迭代 DP 这三把工具，要不要为 MDP 重造一遍？

28 / 82

策略评估需要新算法MDP 多了一整个维度，得重造工具

这个模型不荒谬：多一个维度，通常确实意味着要换方法。

讲解

这个错误模型很自然：多了一整个动作维度，转移核从矩阵变成了三阶张量，看起来确实该有新方法。而且课程的章节编排也在暗示这一点——策略评估被当作一个单独的标题讲。于是很容易把它当成一个新问题。真相比这省事得多，而且省得有点出乎意料。

29 / 82

R^{π} (s) = \sum_{a} π (a ∣ s) R (s, a) P^{π} (s^{'} ∣ s) = \sum_{a} π (a ∣ s) P (s^{'} ∣ s, a)

于是 V^π(MDP) = V(诱导出的 MRP)。披露：约 00:32:36 口头说成「显然的求平均」，两个等式都没写在板上。

讲解

关键在这两行。固定一个策略 π 之后，在每个状态上把动作按 π(a|s) 加权求和，动作这一维就被积掉了：奖励变成 R^π(s)，转移变成 P^π(s′|s)。剩下的对象没有动作，它就是一个 MRP。这不是近似，是恒等变换。于是 V^π 可以直接用 MRP 的三条路来算：蒙特卡洛跑轨迹、闭式解 (I−γP^π)⁻¹R^π、或者迭代 DP。一个新算法都不需要。按本片的披露约定标注一下：这个构造在讲座里（约 00:32:36）是口头说的「显然求个平均」，两个等式都没写在板上，而且「诱导 MRP 的值函数等于原 MDP 的 V^π」这件事从未验证过。它确实是对的，但它是一条需要写出来的引理。

30 / 82

π_{left} : 每格都向左 ⟹ V^{π_{left}} = (I - γ P^{π})^{- 1} R^{π}

π = 一直向左：V(s₁)=10=1/(1−0.9)，卡在 s₁ 永远只吃那个 +1。完全合法、精确可评估、但很糟。

讲解

拿一个明显糟糕的策略试一下：每一格都向左。它照样是一个合法策略，照样可以被精确评估。读一下数字。V(s₁)=10，正好等于 1/(1−0.9)——向左走出 s₁ 是不可能的，所以它永远原地吃那个 +1，值就是 +1 的折扣和。V(s₇)=21.18 仍然不低，因为 s₇ 自己就给 +10，即使策略要求往左走，也有一半概率原地不动。中间五个状态的值都在 3.67 到 6.69 之间，全都很低——它们既够不到 +1，也够不到 +10。这就是一个糟糕策略的值函数长的样子：它是准确的，只是不好。准确和好是两件事，这个区别在 KP7 会变成两个算法的分野。

31 / 82

π_{left} ⟶ π_{right} 同一个 MDP，换一个 π ，换一个 MRP

π 不是在 MDP 里「挑一条路」，π 是在挑一个 MRP —— 于是换一条完全不同的值曲线。

讲解

看什么：看柱子的形状整个翻过来：π_left 下是左高右低（除了 s₇ 自己那根），π_right 下变成单调右升。不是所有柱子等比长高，是次序和形状都换了 —— 因为换掉的不是数值，是被诱导出来的那个 MRP。　—— 同一个 MDP，只换策略，值函数整个换了形状。π_left 下是左高右低，π_right 下是单调右升，s₇ 从 21.18 涨到 100。要看见的东西是：π 不是在既有的 MRP 上「挑一条路」，π 是在挑哪一个 MRP。每个策略都对应一个不同的 (R^π, P^π)，也就对应一个不同的线性方程组。策略空间有多大，可选的 MRP 就有多少个——这正好是下一集的题目。顺带把讲座里一个被学生当场抓到的笔误记下来：策略评估那页幻灯片写的是 V_k，实际应当是 V^π_k，她确认了是笔误（约 00:42:10）。缺了那个 π 上标，整页的意思就变成了值迭代。

32 / 82

指名反驳：这是恒等变换，不是新问题。代价也照搬 —— 迭代每轮仍是 |S|²，到值迭代才变 |S|²|A|。

讲解

指名回去：不需要任何新算法。固定策略把 MDP 恒等地变回 MRP，三把工具全部继承，连复杂度都继承。这里要格外小心一个数字。策略评估每轮仍然是 |S|²，因为 π 已经固定、动作维度已经被求和掉了。但值迭代不是——它每轮是 |S|²|A|，因为每个状态都要把所有动作试一遍再取 max。讲座给了前一个数字，没给后一个，而把 |S|² 直接搬到值迭代上是一个常见错误。这一条也提前解释了 KP7 的一个关键事实：策略迭代的每一轮里都藏着一次完整的策略评估，所以「策略迭代只要 6 轮」和「值迭代要 20 轮」根本不是同一个单位下的数。

33 / 82

知识点 4 · 总结

固定策略把 MDP 恒等地塌回 MRP

核心结论

R^π(s)=Σ_a π(a|s)R(s,a)，P^π(s′|s)=Σ_a π(a|s)P(s′|s,a) ⟹ V^π(MDP)=V(诱导 MRP)。

底层机制

π 不是在 MDP 里选一条路，π 是在选一个 MRP：每个策略对应一组不同的 (R^π, P^π)。

常见误解

误解：「多一个动作维度就要新算法」。这是恒等变换，MC / 闭式解 / 迭代 DP 全部继承。

与你的考试

复杂度：策略评估每轮 |S|²（π 固定），值迭代每轮 |S|²|A| —— 别把前者搬给后者。

34 / 82

知识点 4 · 检验

同一个 MDP 下，π_left 与 π_right 的值函数形状完全不同。最准确的说法是？

知识点 6

5 · 策略空间：|A|^|S| 个，指数但有限 —— 而你永远不必走出它

35 / 82

确定性策略 = 给每个状态指定一个动作。这样的策略一共有多少个？

讲解

一个确定性策略就是给每个状态指定一个动作。火星车有 7 个状态、2 个动作，屏幕上这个「一路向右」就是其中之一。问题：这样的策略一共有多少个？这个问题在课堂上问出来之后，有学生明确表达了惊讶——他预期的量级和真实答案差得很远。她因此专门停下来，用一个两状态的例子把四个策略一个个列了出来。这说明这里有一个真实的绊脚石，值得当作一集来处理。

36 / 82

7 × 2 = 14 个或者：|S|^|A| = 7² = 49 个

两个错法：一个把它当成线性，一个把底数和指数写反了。

讲解

这里有两个常见错法，值得分开说。第一个是线性直觉：每个状态一个选择，7 个状态 2 个动作，于是 14。这个数其实数的是「(状态, 动作) 对」的个数，不是策略的个数——它把「一共有多少个可选项」和「有多少种选法的组合」混为一谈了。第二个更隐蔽：写成 |S|^|A| = 7² = 49。指数形式对了，但底数和指数反了。讲座里她明确强调过是 2 的 7 次方而不是 7 的 2 次方，说明这个方向确实容易记反。判别的办法很简单：指数上应该是「独立选择的次数」，也就是状态数。

37 / 82

| Π_{det} | = | A |^{| S |}

每个状态独立选一次，所以每加一个状态叶子数就乘以 |A|：两状态两动作 → 4 个叶子。

讲解

把它画成树就一目了然。第一层是 s₁ 选左还是选右，第二层是 s₂ 选左还是选右——而 s₂ 的选择不受 s₁ 影响，两个选择完全独立。所以每加一个状态，叶子数就乘以 |A| 而不是加上 |A|。这正是讲座里她做的事：在一个两状态两动作的 MDP 上把四个策略一个个列出来（左左、左右、右左、右右）。四个，不是四种情况里的某几种。于是指数上是状态数：|A|^|S|。判别口诀：指数 = 独立做选择的次数。火星车是 2⁷ = 128。

38 / 82

7 个状态 2 个动作

128。线性猜测差了 9 倍，底数写反差了 2.6 倍 —— 差的是量级，不是零头。

讲解

看什么：看三根柱子依次出现的高度差：先是 14（线性猜测），再是 49（底数写反），最后 128 才立起来。前两根加起来还不到第三根的一半 —— 这个差距会随状态数继续拉开。　—— 三个答案放在同一根尺子上。线性猜测 14、底数写反 49、正确答案 128。在 7 个状态上，差距还只是「几倍」。但这三条曲线的增长方式完全不同：状态数变成 20 时，线性猜测给 40，|S|^|A| 给 400，而 |A|^|S| 给一百多万。所以这不是一个记错了数字的问题，是把一个指数问题当成了多项式问题。这个量级正是「穷举所有策略」这条路走不通的原因。穷举是可行的——策略空间毕竟有限——但每评估一个策略都要解一次线性方程组，128 次还能忍，2²⁰ 次不行。

39 / 82

指数、但有限。披露：第二条讲座只给了直觉（「无限长的未来每时刻看起来都一样」），没有证明。

讲解

指数很吓人，但真正重要的性质是有限，而有限给出两个结论。第一，策略迭代必然终止。每一轮都严格改进，所以同一个策略不可能被访问两次，轮数被 |A|^|S| 顶住。这个界极其宽松——火星车实际只用了 6 轮，而界是 128——但它保证了算法不会打转。第二，也是更深的一条：你永远不必走出这个有限集合。定理说，无限时域折扣有限 MDP 存在一个确定性的、平稳的最优策略。随机化帮不上忙，让策略依赖时间也帮不上忙。这件事一点都不显然，因为在有限时域下它就是假的（L1 已经讲过：时域将尽时最优动作会变），在部分可观测下它也是假的（POMDP 的最优策略经常需要随机化）。披露：这条定理在讲座里（约 00:48:51）只给了一句直觉——「无限长的未来在每个时刻看起来都一样」——没有证明随机化不能更好，也没有证明历史依赖策略不能更好。这是本讲最承重的一处跳过。

40 / 82

指名反驳：判别口诀 —— 指数上是「独立做选择的次数」。有限时域下这条不成立（L1 KP9）。

讲解

指名回去。128 个，不是 14 也不是 49。指数上是状态数，因为每个状态独立做一次选择——口诀是「指数 = 独立做选择的次数」。 14 那个数字本身并不是没有意义，它数的是 (状态, 动作) 对的个数，也就是 Q 表的格子数。把 Q 表的大小误当成策略空间的大小，是这个错误最常见的来源。最后再强调一遍那个静默的前提：这 128 个确定性平稳策略里一定有一个是最优的。这句话依赖于「无限时域 + 折扣 + 有限」这三个条件，缺一不可。L1 的最后一集已经给过反例：时域有限时，最优策略是非平稳的，它会随着剩余步数改变。

41 / 82

知识点 5 · 总结

确定性策略有 |A|^|S| 个 —— 指数，但有限

核心结论

火星车 2⁷ = 128。指数上是状态数，因为每个状态独立选一次动作。

底层机制

有限 ⟹ 策略迭代必终止（同一策略不会出现两次）；且最优解一定落在这个有限集合里。

常见误解

误解：14（那是 Q 表格子数）或 49（底数指数写反）。口诀：指数 = 独立做选择的次数。

与你的考试

「存在确定性平稳最优策略」只在无限时域 + 折扣 + 有限下成立；有限时域下最优策略非平稳。

42 / 82

知识点 5 · 检验

一个 MDP 有 20 个状态、4 个动作。确定性策略有多少个？

知识点 7

6 · 策略改进定理：只贪一步，为什么整条未来都更好

43 / 82

π_{i + 1} (s) = \arg max_{a} Q^{π_{i}} (s, a)

第 1 步用新动作，第 2 步往后全是旧策略 —— 凭什么由此断定整条未来都更好？她自己说：「这里有点怪」。

讲解

策略改进的定义只有一行：新策略在每个状态上，按旧策略的 Q 值取 argmax。请盯住那个上标。Q^{π_i} 的意思是：第一步用新动作 a，之后全部按旧策略 π_i 走。所以贪心只动了一步，后面那条无限长的尾巴完全没变。凭什么由此断定新策略在每个状态上都不劣于旧策略？这不是显然的。她在课上也是这么说的——「这里有点怪」，「这是不是件好事，应该至少让人有点不确定」。这一集就是把这个不确定解掉。

44 / 82

贪心只保证第一步更好第一步贪一口，后面说不定亏更多

这个顾虑不是杞人忧天 —— 最短路、背包、特征选择里，贪心确实会栽在这上面。

讲解

这个错误模型值得非常认真地对待，因为它在别处几乎总是对的。贪心算法栽在「局部最优不等于全局最优」上，是算法课的主线之一。所以真正的问题不是「贪心为什么可能有问题」，而是这里为什么没问题。答案不在于 RL 的贪心更聪明，而在于一个结构性的事实：这个不等式可以被反复施加，而每施加一次，就把多一个时间步锁死成新策略。她把要点提炼成两个动作：一是 V^π 是 max_a Q^π 的下界，二是把那个 max 重写成 π_{i+1} 的定义。接下来四镜就是把这两个动作反复用。

45 / 82

V^π₁(s) = Q^π₁(s, π₁(s)) ≤ max_a Q^π₁(s,a)

动作一：π₁(s) 只是众多 a 中的一个，取 max 不会更小。平凡，但承重。

讲解

先建立第一个动作，它平凡到几乎不像一步：V^π(s) 就是 Q^π(s, π(s))——按旧策略行动的价值。而 π(s) 只是所有动作中的一个，所以它不会超过对所有 a 取的最大值。一行不等式：V^π₁(s) ≤ max_a Q^π₁(s,a)。为了让屏幕上的式子能读，本集把 π_i 写成 π₁、π_{i+1} 写成 π₂。另外说明一处转录问题：讲座字幕在这段把 Q 值写成了 R，还把 π_i(s) 写成了 π_i(a)。被界住的量是 Q 值，不是即时奖励；下标里是状态，不是动作。

46 / 82

V^π₁(s) ≤ Q^π₁(s, π₂(s)) = r(s, π₂(s)) + γ Σ_s′ P(s′|s, π₂(s))V^π₁(s′)

动作二：max 改写成 π₂ 的定义，再展开一层 Bellman。第 1 步已经换成 π₂ 了。

讲解

第二个动作：取到最大值的那个动作，按定义就叫 π₂(s)。所以 max_a Q^π₁(s,a) 可以直接写成 Q^π₁(s, π₂(s))——这不是一个新的不等式，只是换了个名字。然后把 Q 展开一层：立即奖励 r(s, π₂(s))，加上 γ 乘以后继状态的 V^π₁(s′)。现在请盯住右端那个 V^π₁(s′)。它和整个不等式的左端是同一个形状。这意味着我们可以对它再用一次同样的不等式——这就是全部的诀窍。

47 / 82

V^π₁(s) ≤ r(s, π₂(s)) + γ Σ_s′ P(s′|s, π₂(s))[ r(s′, π₂(s′)) + γ Σ_s″ P(s″|s′, π₂(s′))V^π₁(s″) ]

再代一次：第 2 步也变成 π₂。展开 k 次 ⟹ 前 k 步全是 π₂，尾项 γ^k·V^π₁，而 |V^π₁| ≤ R_max/(1−γ) 有界。

讲解

对内层那个 V^π₁(s′) 再用一次完全相同的不等式。于是第二步的动作也变成了 π₂，而尾巴上的 V^π₁ 被推到了 s″。这就是全部机制：每代入一次，就把多一个时间步从 π₁ 换成 π₂，同时把残留的 V^π₁ 往后推一步，而它前面的系数每次多乘一个 γ。展开 k 次之后，前 k 步全部是 π₂ 的动作，尾项是 γ^k 乘以一个 V^π₁。这里用到了 L1 建立的有界性：|V^π₁| ≤ R_max/(1−γ)。有界量乘以 γ^k，当 k→∞ 时趋于零。这一步必须有 γ<1 和有界奖励，否则整个论证塌掉。

48 / 82

V^π₁(s) ≤ lim_k→∞ E_π₂[ r₀ + γr₁ + γ²r₂ + ⋯ + γ^k−1r_k−1 ] + γ^kV^π₁ ⟶ V^π₂(s)

极限：右边正是 V^π₂(s)。于是 V^π₁ ≤ V^π₂ 逐状态成立；π₁ 非最优时至少一处严格小于。

讲解

取极限。前面那一整段是「全程按 π₂ 行动」的折扣回报期望，尾项 γ^k 乘一个有界量趋于零。于是右边收敛到的东西，正好就是 V^π₂(s) 的定义。结论：V^π₁(s) ≤ V^π₂(s)，对每一个状态都成立。而且如果 π₁ 不是最优的，那么至少存在一个状态使不等式严格——这正是「严格改进」的来源，也是 KP5 里「同一个策略不会被访问两次」的依据。回头看，整个论证没有用到任何关于 MDP 的特殊性质，只用了三件事：Q 的定义、max 不小于任一项、以及 γ^k 乘有界量趋于零。

49 / 82

指名反驳：贪心只改一步 —— 但这一步可以被代入无穷多次。承重前提：γ < 1 且奖励有界。

讲解

指名回去。这个顾虑的前半句完全正确：贪心确实只改了一步。错的是后半句——它假设「只改一步」这个操作只能做一次。实际上它可以被代入无穷多次，每次锁死一个时间步，极限处整条轨迹都变成了新策略。这就是为什么策略改进不像别处的贪心那样会栽跟头：它不是在一个固定的目标函数上做局部搜索，而是在用一个自我增强的不等式。承重前提要记住：γ<1 且奖励有界。少了它们，尾项 γ^k·V^π₁ 不会消失，整个论证塌掉。最后按约定披露一处：讲座证明了单调改进，也论证了终止，但没有证明「停下来的那个策略是全局最优」。那一步需要说明贪心算子的不动点满足 Bellman 最优方程，因而其值就是 V*。她在约 00:55:16 直接说了「保证收敛到全局最优」，并顺带断言这里没有局部最优——后者同样没有给论证。

50 / 82

知识点 6 · 总结

贪心只改一步，但这一步可以被代入无穷多次

核心结论

两个动作：① V^π ≤ max_a Q^π；② 把那个 max 写成 π₂ 的定义。反复代入 ⟹ V^π₁ ≤ V^π₂ 逐状态成立。

底层机制

每代入一次锁死一个时间步，尾项 γ^k·V^π₁ → 0（要 γ<1 且奖励有界）；极限处整条轨迹都是 π₂。

常见误解

误解：「贪心只保证第一步，后面可能亏回去」。前半句对，后半句假设了代入只能做一次。

与你的考试

严格改进 + 策略空间有限 ⟹ 策略迭代终止。但「终止即最优」讲座没证（需贪心不动点 ⟹ Bellman 最优方程）。

51 / 82

知识点 6 · 检验

策略改进定理的证明里，「反复代入」这一步到底在做什么？

知识点 8

7 · 策略迭代与值迭代，手里拿的不是同一种东西

52 / 82

V^{*} = (31.82, 36.67, 44.81, 54.77, 66.94, 81.82, 100.00)

两条路通向同一个 V*，每轮都在做「评估 + 贪心」。那中途手里拿的是同一种东西吗？

讲解

策略迭代和值迭代都收敛到同一个 V*，而且两者每轮都在做「某种评估」加「某种贪心」。在教科书的广义策略迭代框架里，它们确实是同一个谱系上的两点。但这一集问的不是终点，而是中途：在算法还没收敛的时候，你手里那个数组到底是什么东西？这个问题的答案，是两个算法唯一真正的分野，也是最容易被含混过去的地方。

53 / 82

V_k 是第 k 轮贪心策略的值算法一边改进策略，一边把它的值算准

这个模型让「V_k 对应哪个策略」成为一个有答案的问题。它没有。下面用真实数字检验。

讲解

这个错误模型非常顺口：策略在变好，值在变准，两件事同步推进。值迭代的伪代码里那个 max 看起来就是在做贪心，所以把 V_k 读成「当前贪心策略的值函数」几乎是自动的。如果这个模型成立，「V_k 对应的那个策略」就是一个有意义的短语，你就可以说「值迭代在第 k 轮持有策略 π_k 及其值 V_k」。下面三镜用火星车的真实数字来检验它。检验方法很直接：把值迭代第 2 轮的贪心策略拿出来，精确地评估它，看看得到的值是不是 V₂。

54 / 82

PI: (π_{i}, V^{π_{i}}) VI: V_{k}

PI 每轮内部解一次完整线性方程组，所以一轮很贵；VI 的贪心策略是事后读出来的，不是它维护的对象。

讲解

先把两个算法在每一轮结束时手里的东西写清楚。策略迭代持有一对：一个策略 π_i，和它精确的值函数 V^{π_i}。之所以精确，是因为每一轮内部都做了一次完整的策略评估——解一个线性方程组，或者迭代到收敛。所以 PI 的一轮很贵。值迭代只持有一个数组 V_k。贪心策略是你想看的时候事后从 V_k 读出来的，算法本身并不维护它。请注意：能从 V_k 读出一个策略，和 V_k 等于那个策略的值，完全是两件事。下一镜就把它们撞在一起。

55 / 82

VI 第 2 轮： V_{2} 贪心读出 π =\leftarrow\leftarrow\leftarrow\leftarrow\to\to\to

VI 的 V₂ 几乎还贴着地面：中间三个精确为 0，最大的 s₇ 也只有 19.00。记住这个策略。

讲解

值迭代扫两轮，得到 V₂ = (1.90, 0.45, 0, 0, 0, 4.50, 19.00)。信息只从两端传出去两格，中间三个状态还精确地等于 0。现在从 V₂ 贪心读出一个策略：在每个状态上比较向左和向右的 Q 值，得到 ←←←←→→→。记住这个策略。下一镜把同一个策略拿去精确评估。

56 / 82

同一个策略 \leftarrow\leftarrow\leftarrow\leftarrow\to\to\to 的精确值函数

左边是 VI 手里的 V₂，右边是同一个策略真正的值函数。数字差了一个量级 —— V₂ 不是任何策略的值函数。

讲解

看什么：看柱子涨了多少：s₅ 从 0.00 直接跳到 66.94，s₇ 从 19.00 跳到 100.00。起点几乎贴着地面，终点几乎顶格。两端是同一个策略 —— 变的只是「这个数组是什么」。　—— 把 ←←←←→→→ 这个策略精确评估一遍，得到 (10.00, 8.18, 6.69, 5.48, 66.94, 81.82, 100.00)。和 V₂ 对比：s₅ 从 0 变成 66.94，s₇ 从 19 变成 100。策略完全相同，数字差了一个量级。 所以那个错误模型被直接证伪了：V₂ 不是它自己贪心策略的值函数，也不是任何别的策略的值函数。它是另一种东西——下一镜说清楚是什么。顺带说一句：巧的是，策略迭代第 2 轮持有的策略正好也是 ←←←←→→→，而它配套的值函数正是右边这一组。所以这张图也可以读成：同一轮次上，PI 手里是右边，VI 手里是左边。

57 / 82

V_{k} (s) = max_{π} E_{π} [\sum_{t = 0}^{k - 1} γ^{t} r_{t} | s_{0} = s]

V₂ 那么小是因为只走 2 步根本够不到 +10。披露：约 01:07:34 只作断言，对 k 的归纳没做，有限时域那节整节跳过。

讲解

V_k 的正确身份是：只剩 k 步可走时的最优值。它是一个有限时域问题的解。这解释了 V₂ 为什么那么小：只允许走两步，从 s₅ 出发根本够不到 +10——每步只有一半概率真的移动，两步走到两格外的概率很低。不是算法算得不准，是它在如实回答一个不同的问题。这也给出了那句最容易被误引的话的正确读法。她说「值迭代让你随时知道最优值和最优策略，但前提是你只能行动 k 步」。中途读出的贪心策略对 k 步问题最优，对无限时域问题不是。把这句话缩写成「值迭代始终维持一个最优策略」就错了。披露：V_k 等于 k 步最优值这件事在讲座里是断言（约 01:07:34），对 k 的归纳没有做；而能把它讲清楚的有限时域那一整节，因为时间关系被整节跳过了。

58 / 82

指名反驳：本例 PI 6 轮终止但每轮含完整评估；VI 的贪心策略第 11 轮才最优，而值还差得远。

讲解

指名回去。V_k 不是任何策略在原问题下的值函数，这一点已经被同一个策略的两套数字直接证伪了。两个算法真正的分野可以压成一句话：策略迭代手里拿的是「准确但不够好」，值迭代手里拿的是「够好但不准确」。PI 的中间物是一个被精确评估过、但通常还不最优的策略；VI 的中间物是一个恰好最优、但只对 k 步问题成立的值。还要提醒一件在比较时最容易出错的事：轮数不能直接比。火星车上 PI 用 6 轮终止，VI 的贪心策略到第 11 轮才变成最优，而那时值还差 V* 很远。但 PI 的每一轮内部含一次完整的策略评估，VI 的每一轮只是 |S|²|A| 的一次扫描。两者的「一轮」不是同一个单位。

59 / 82

知识点 7 · 总结

PI 拿的是「准确但不够好」，VI 拿的是「够好但不准确」

核心结论

火星车实测：VI 的 V₂=(1.90,0.45,0,0,0,4.50,19.00)，其贪心策略 ←←←←→→→ 的真实值是 (10,8.18,6.69,5.48,66.94,81.82,100)。同一策略，差一个量级。

底层机制

V_k 是「只剩 k 步」时的最优值 —— 一个有限时域问题的解，不是任何策略在原问题下的值。

常见误解

误解：「V_k 是当前贪心策略的值函数」。也别把她那句话缩写成「VI 始终维持最优策略」。

与你的考试

轮数不可直接比：PI 每轮内含一次完整评估（~|S|³），VI 每轮只是一次 |S|²|A| 扫描。

60 / 82

知识点 7 · 检验

值迭代跑到第 k 轮，从 V_k 贪心读出策略 π_k。下面哪句正确？

知识点 9

8 · 值迭代收敛，不是因为「更新越来越小」

61 / 82

V_{k + 1} (s) \leftarrow max_{a} [R (s, a) + γ \sum_{s^{'}} P (s^{'} ∣ s, a) V_{k} (s^{'})]

值迭代 = 把同一个算子 B 反复套用在它自己的输出上。

讲解

值迭代就是把 Bellman 最优备份反复套用在它自己的输出上。把这个映射记作 B，算法就是 V_{k+1} = B V_k：拿上一轮的 V，套一次 B，得到下一轮的 V，如此反复。实践中它在相邻两轮的差足够小时停下来 —— ‖V_k − V_{k−1}‖ < ε 就退出循环。

62 / 82

两个问题必须一起回答：会停吗？停在同一处吗？

讲解

有两个问题必须回答。第一，凭什么保证它一定会停 —— 也就是凭什么保证更新幅度早晚小于 ε？第二，凭什么保证不管 V₀ 取什么，都停在同一个地方？第二个问题她在课堂最后当作思考题留了出去（「初始化会不会影响最终结果」），课上没有回答。这一集会把两个问题一起解掉，因为它们的答案是同一个。

63 / 82

因为更新越来越小所以它一定会收敛 · 你每跑一遍，确实都看到它一轮比一轮小

这是你很可能持有的模型。它听上去像一个理由。

讲解

「更新越来越小，所以早晚会小于 ε，算法就停了」—— 这是绝大多数人默认持有的模型。它很难起疑，因为它在经验上总是成立：你跑一遍值迭代，确实会看到更新一轮比一轮小。问题在于，观察到的现象被当成了机制。

64 / 82

循环论证：它会收敛，因为它在收敛。

讲解

把这句话展开，看它在论证什么：「它会收敛，因为它在收敛。」更新幅度趋于零和收敛是同一件事的两种说法 —— 更新变小是结论，不是原因。两句话互为理由，绕成一个圈，而这个圈绕得很隐蔽。真正的问题从来没被回答：更新幅度凭什么变小？答案不在 V 上，在算子 B 上。

65 / 82

‖ B V - B V^{'} ‖_{\infty} \leq γ ‖ V - V^{'} ‖_{\infty} (γ < 1)

γ-压缩：算子把任意两点之间的距离，一次至少缩到 γ 倍。

讲解

真正的原因是：B 是一个 γ-压缩。它把任意两个值向量之间的 sup 范数距离，每作用一次就至少缩小到 γ 倍。最要紧的是这句话的主语：它说的不是某个特定 V 的性质，而是算子 B 的性质，与初值取什么完全无关。这就是为什么它能同时回答前面那两个问题。

66 / 82

四步只用了概率和为 1 与 max 的次可加性 —— 没用 MDP 的任何结构。

讲解

证明只有四步，讲座讲得很快（约 01:11:15）。第一步，把两个独立的 max 之差上界为单个 max 的差；第二步，相同的 R(s,a) 相消；第三步，把每个 |V(s′)−V′(s′)| 上界为 sup 范数距离，从而提到求和外面；第四步，用 Σ_{s′}P(s′|s,a)=1 把求和消掉，剩下 γ 乘 sup 范数距离。值得注意的是：四步里没有用到 MDP 的任何特殊结构，只用了「概率和为 1」与「max 的次可加性」。

67 / 82

V_{0}^{(a)} = 0 V_{0}^{(b)} = (50, - 20, 80, 0, 100, - 50, 30)

柱高 = 两条轨迹之间的 sup 距离。两个任意起点，各自套用 B。

讲解

看什么：看柱子每一根比前一根矮多少。从第二根开始，每根都恰好是前一根的 0.9 倍 —— 不是大致、不是平均，是精确的 0.9。这个比值就是 γ，而它与两个起点是什么完全无关。　—— 拿两个毫不相干的起点：一个全零，一个是随手写的 (50, −20, 80, 0, 100, −50, 30)，两者初始距离 100。各自反复套用 B，每一根柱子的高度就是这一轮两条轨迹之间的 sup 范数距离 ‖V^(a)_k − V^(b)_k‖。结果是 100 → 45 → 40.5 → 36.45 → 32.81 → 29.52 → 26.57 → 23.91。第一步缩得比 γ 还狠（0.45），之后每一步恰好是前一步的 0.9000。γ 就是 0.9。这说明 γ-压缩的界在这里是紧的 —— 不是一个宽松的最坏情况估计，而是实际发生的速率。第一步之所以更快，是因为那个随手写的起点在某些坐标上的偏差被 max 直接切掉了；一旦进入稳定模式，速率就锁在 γ 上。

68 / 82

B V^{*} = V^{*} ⟹ ‖ V_{k} - V^{*} ‖_{\infty} \leq γ^{k} ‖ V_{0} - V^{*} ‖_{\infty}

把上一镜的 V′ 换成 V* 本身 —— 两点的距离就变成误差。

讲解

把上一镜里的 V′ 换成 V* 本身 —— 它满足 B V* = V*，是 B 的不动点，套一次 B 原地不动。于是压缩不等式变成 ‖V_k − V*‖ ≤ γ‖V_{k−1} − V*‖，逐层展开就得到 ‖V_k − V*‖ ≤ γ^k‖V₀ − V*‖。 γ<1，所以右边指数趋于零。两个向量之间的距离，在这里变成了「当前值离答案还有多远」。

69 / 82

压缩 ⟹ 收敛 + 不动点唯一 + 与初值无关。三个结论同一个来源。

讲解

三个结论一起掉出来。第一，收敛，而且是几何速率，每轮误差乘 γ。第二，不动点唯一：如果有两个不动点，它们之间的距离既等于自身、又不超过自身的 γ 倍，那只能是零。第三，与初值无关：V₀ 只出现在界的常数里，不影响收敛与否，也不影响收敛到哪里。这正好回答了她留在课堂最后的那道思考题 —— 初始化不影响最终结果。披露两处。Banach 不动点定理本身她明确说「是个不错的练习」，留给了学生（约 01:12:52）。另外，「B 的不动点就等于 V*」以及「对 V* 贪心就得到最优策略」这两件事被隐式使用，但从未被点名为需要证明的命题。

70 / 82

讲座口述的是左边，板上证的是右边。差别不是措辞。

讲解

这里有一个值得精确指出的问题。她在约 01:09:50 给压缩下的口头定义是「距离不会变大，而且可以缩小」—— 这描述的是非扩张（non-expansive），不是压缩。两者的差别不是措辞上的：恒等映射 BV = V 就是非扩张的，它的每一个点都是不动点，迭代永远停在 V₀ 不动，不收敛到任何唯一的地方。板上实际证明的是带模数 γ<1 的严格压缩，是对的；但说出来的定义太弱，弱到不足以支撑结论。

71 / 82

收敛来自 γ-压缩不是「更新变小」· 那是结论，不是原因

读到「压缩」就追问模数是多少 —— 没有 γ<1，后面全部不成立。

讲解

指名回去。「更新越来越小」是收敛的同义反复，不是原因。原因在算子上：B 是 γ-压缩，压缩映射有唯一不动点，迭代以几何速率收敛到它，与初值无关。所以读到「压缩」这个词时，永远要追问模数是多少。没有那个 γ<1，前面所有的收敛性都不成立。

72 / 82

知识点 8 · 总结

收敛来自算子的 γ-压缩，不是「更新变小」

核心结论

‖BV − BV′‖_∞ ≤ γ‖V − V′‖_∞。实测两个任意起点：距离 100 → 45 → 40.5 → 36.45 → …，比值精确锁在 0.9000 = γ。

底层机制

主语是算子不是 V，所以同时给出三件事：几何收敛、不动点唯一、与初值无关。

常见误解

误解：「更新越来越小所以收敛」是循环论证。另：讲座口述的定义是非扩张，它不保证收敛（恒等映射即是）。

与你的考试

Banach 不动点定理被留作练习；「B 的不动点 = V*」与「对 V* 贪心即最优」都被隐式使用、从未证明。

73 / 82

知识点 8 · 检验

「B 是非扩张的」（‖BV−BV′‖ ≤ ‖V−V′‖）足以保证值迭代收敛到唯一不动点吗？

知识点 10

9 · 停机判据的缺口：ε 不是误差，γ/(1−γ)·ε 才是

74 / 82

while ‖ V_{k} - V_{k - 1} ‖_{\infty} > ε : V_{k + 1} \leftarrow B V_{k}

停机判据衡量的是相邻两轮的差。它不是你想要的那个误差 —— 而讲座完全没回答这个问题。

讲解

这是值迭代的标准停机条件：相邻两轮的 sup 范数差小于 ε 就停。几乎所有实现都这么写，课程作业里也这么写。你设 ε=0.01，跑到条件满足，拿走 V_k。问题是：此时 V_k 离真正的 V* 有多远？这个问题在讲座里完全没有被回答。逐讲索引里这一条是明确记录在案的：算法在 ‖V_k−V_{k−1}‖<ε 时停，但让这个 ε 变得有意义的那个标准界从未被提起，γ^k 衰减也没提。这一集就是把这个缺口补上。

75 / 82

ε 就是精度设 ε = 0.01 就是结果精确到 0.01

把步长当成到终点的距离 —— 这是所有迭代算法共有的陷阱。

讲解

这个错误模型来自一个几乎普适的习惯：在梯度下降里看梯度范数，在牛顿法里看步长，在值迭代里看相邻两轮的差。步长小了就认为到了。它在很多场合是合理的近似。但它默认了一件事：剩余距离与单步步长同阶。当迭代以几何速率 γ 收敛时，剩余距离是所有未来步长之和，也就是一个公比为 γ 的几何级数——而级数和与首项之比是 1/(1−γ)，这个数在 γ 接近 1 时会非常大。下面用真实数字看它有多大。

76 / 82

‖ V_{k} - V^{*} ‖_{\infty} \leq \frac{γ}{1 - γ} ‖ V_{k} - V_{k - 1} ‖_{\infty}

推导一行：剩余距离 = 未来所有增量之和，而 γ + γ² + ⋯ = γ/(1−γ)。这个界讲座一次都没出现过。

讲解

正确的界一行就能推出来。V_k 到 V* 的距离，不超过从 k 开始所有未来增量的总和；而由 γ-压缩，第 j 个未来增量不超过 γ^j 乘以当前增量。于是求和得到 γ+γ²+γ³+… = γ/(1−γ)。所以：真实误差 ≤ γ/(1−γ) 乘以你看到的那个增量。这个放大系数在 γ=0.9 时是 9，γ=0.99 时是 99，γ=0.999 时是 999。深度强化学习里 γ=0.99 是默认值，所以 99 这个数字不是学术上的假想。

77 / 82

γ = 0.9 : 停机于 k = 67

你以为误差 0.0096，实际 0.0860 —— 差 9 倍。比值 0.08595/0.00955 = 9.00，正是 γ/(1−γ)，界取到了等号。

讲解

看什么：看两根柱子的高度比。左边先出现，是你在终端里看到的那个数；右边接着立起来，明显高出一大截。比值不是「大概几倍」，是精确的 9.00。　—— 在火星车上跑一遍。γ=0.9，阈值 0.01，第 67 轮时增量首次降到 0.00955，算法停下。此时 V_k 与 V* 的真实距离是 0.08595。比值 9.00——正是 γ/(1−γ)。这里有一件比「有个缺口」更值得注意的事：这个界取到了等号。它不是教科书里那种宽松的最坏情况估计，在这个 MDP 上就是实际发生的倍数。所以你不能用「界一般很松，实际会好很多」来安慰自己。

78 / 82

γ = 0.99 : 停机于 k = 689

γ=0.99：你以为误差 0.0099，实际 0.983，差 99 倍。左边那根几乎看不见 —— 这正是它的问题。

讲解

看什么：看左边那根柱子有多小：它几乎贴着地面、几乎看不出来，而右边那根几乎顶格。你在终端里读到的就是左边那个数，而你真正关心的是右边那个。　—— 换成深度 RL 的默认值 γ=0.99，同一个 MDP，同一个阈值 0.01。这次要跑 689 轮才停，停下时增量 0.00993，而真实误差是 0.98322。比值 99.00，又一次取到等号。请对照 V* 的量级看这个数：γ=0.99 时 V* 在 889 到 1000 之间，所以 0.98 的绝对误差占比其实很小。这说明一件重要的事——这个缺口在相对误差上没那么可怕，可怕的是你以为自己知道它是多少。如果你的下游逻辑依赖「V_k 精确到 0.01」（比如用值的差来比较两个动作），那么 0.98 的误差足以让你选错动作。还有一个代价常被忽略：从 γ=0.9 到 γ=0.99，达到同一阈值所需的轮数从 67 涨到 689，十倍。这也是 1/(1−γ) 在起作用。

79 / 82

ε = δ \frac{1 - γ}{γ}

指名反驳：ε 是步长不是精度。顺带 —— 本例 γ=0.9 时第 11 轮贪心策略已最优，而值要到第 67 轮。

讲解

指名回去。ε 衡量的是步长，不是到终点的距离。两者之间差一个 γ/(1−γ)，而且在本例的两次实测里这个界都取到了等号。要真正保证 ‖V_k−V*‖<δ，阈值必须设成 ε = δ(1−γ)/γ。γ=0.99、δ=0.01 时是 1.01×10⁻⁴，比直觉上的 0.01 小了两个数量级。最后一件实用的事。在本例里，γ=0.9 时贪心策略在第 11 轮就已经最优了，而值要到第 67 轮才满足 ε=0.01。如果你只要策略、不要值，可以停得早得多。但注意这需要另一套判据——「贪心策略连续若干轮不变」并不严格保证最优，它只是一个启发式。严格的做法是用 ‖V_k−V*‖ 的界去控制动作间隙：当误差小于最优动作与次优动作 Q 值之差的一半时，贪心策略就一定最优了。这条在讲座里同样没有出现。

80 / 82

知识点 9 · 总结

ε 是步长，不是精度：真实误差是它的 γ/(1−γ) 倍

核心结论

‖V_k−V*‖ ≤ γ/(1−γ)·‖V_k−V_{k−1}‖。实测 γ=0.9：0.00955 → 0.08595（×9.00）；γ=0.99：0.00993 → 0.98322（×99.00）。两次都取到等号。

底层机制

剩余距离是所有未来增量之和，增量按 γ 几何衰减，级数和 γ+γ²+⋯ = γ/(1−γ)。

常见误解

误解：「设 ε=0.01 就是精确到 0.01」。这是把步长当成到终点的距离 —— 所有迭代算法共有的陷阱。

与你的考试

要精度 δ，阈值取 ε = δ(1−γ)/γ。另：贪心策略常远早于值收敛（本例第 11 轮 vs 第 67 轮）。

81 / 82

知识点 9 · 检验

γ = 0.99，值迭代在 ‖V_k − V_{k−1}‖ = 0.01 时停止。‖V_k − V*‖ 最大可能是多少？

知识点 11

完

82 / 82

讲解

回头看这九集，三件事在这门课后面会反复用到。第一，策略改进定理的力量来自反复代入：贪心只改了一步，但同一个不等式可以一路套下去，每套一次就多锁死一个时间步，极限处右边整个变成 V^{π₂}。它依赖 γ<1 与奖励有界，缺一不可。第二，值迭代的收敛不来自「更新变小」——那是循环论证。它来自 Bellman 最优算子在 sup 范数下是 γ-压缩，而压缩映射有唯一不动点。实测两个任意起点的距离比值精确锁在 0.9000，界是紧的。第三，停机判据量的是步长，不是精度：真实误差是它的 γ/(1−γ) 倍，γ=0.99 时是 99 倍，而且实测取到等号。这个界讲座一次都没提过。顺带记住那 19 处被跳过的证明里最承重的三处：存在确定性平稳最优策略（只给了直觉）、策略迭代停下来即全局最优（只证了改进与终止）、Banach 不动点定理（留作练习）。下一讲把 P 和 R 拿走。这一讲所有算法的第一步都是「对所有 s′ 求和」，没有模型时这一步直接做不了 —— L3 的全部内容就是用样本替掉那个求和，以及为此付出的偏差与方差代价。

CS234 L2 · 已知世界模型 · 全片速览

开场

1 · 「链会忘掉起点」缺了两个前提

「链跑久了会忘掉起点」缺了两个前提

2 · 算值函数的三条路：代价不同，能走多远也不同

闭式解是这一讲的终点，迭代是整门课的起点

3 · (I−γP)⁻¹ 为什么一定存在，γ=1 时又为什么真的塌掉

(I−γP) 的可逆性由 γ 完全决定，与 P 的数值无关

4 · 固定策略把 MDP 塌回 MRP

固定策略把 MDP 恒等地塌回 MRP

5 · 策略空间：|A|^|S| 个，指数但有限 —— 而你永远不必走出它

确定性策略有 |A|^|S| 个 —— 指数，但有限

6 · 策略改进定理：只贪一步，为什么整条未来都更好

贪心只改一步，但这一步可以被代入无穷多次

7 · 策略迭代与值迭代，手里拿的不是同一种东西

PI 拿的是「准确但不够好」，VI 拿的是「够好但不准确」

8 · 值迭代收敛，不是因为「更新越来越小」

收敛来自算子的 γ-压缩，不是「更新变小」

9 · 停机判据的缺口：ε 不是误差，γ/(1−γ)·ε 才是

ε 是步长，不是精度：真实误差是它的 γ/(1−γ) 倍

完