CS234 L1 · 强化学习导论 · 放映厅

知识点 1

开场

1 / 87

讲解

这一讲本身不证明任何东西 —— 它建立词汇表。但本片的结构不是照搬讲座：每个知识点都按六拍走，其中第二拍会同情地说出一个貌似合理的错误模型，第五拍再回去指名杀掉它。这么做有实证依据：在教学研究里，正面撞击学习者的错误模型带来的效应（d≈0.79–0.83）大约是「用动画而非静态图」（d≈0.37）的两倍。干净的讲解会让人觉得更清楚、更省力，而这恰恰是问题 —— 没有碰撞，新解释会被归档在旧模型旁边，而不是替换掉它。

知识点 2

1 · 三个承重词：序贯 · 好 · 学

2 / 87

强化学习：智能体学会做出一序列好的决策。那么——把监督学习的 loss 换成 − reward，是不是就得到 RL 了？

讲解

这句定义 Brunskill 在开场第二分钟就给了，看上去像客套话，其实每个词都在划边界：删掉「学」剩下规划——模型已知，难的只是算；删掉「序贯」剩下赌博机——动作不影响下一个观测；删掉「好」就没有优化问题。真正麻烦的是第四种删法：三个词一个不删，只把监督信号从标签换成分数。它看起来什么也没破坏，本片要查的就是它到底破坏了什么。

3 / 87

监督学习给真标签，无监督学习什么都不给，RL 给的是你那个动作值几分——正好落在中间。所以 RL 就是监督信号更弱的监督学习：把 CE 换成 − r，其余照旧。

讲解

这个模型有课本级的出处：Brunskill 自己在这一讲里说，RL 拿到的东西「介于监督与无监督之间」——你交出一个标签，世界回你一个效用分。顺着这句往下推，结论几乎不可抗拒：既然只是监督信号变弱了，那 RL 无非是更难的监督学习，把交叉熵换成负奖励、多采样、再想办法降方差，其余照旧。做过 SFT 再上 RLHF 的人尤其容易停在这里，因为两边的训练循环看上去确实一模一样。

4 / 87

先把要用的东西命名：五格走廊、起点 s3、两个动作、两个确定性策略 π_L / π_R、奖励 r(s)、访问频率 d(s)（4 步里停在 s 的时间比例）。它们还什么都没做。

讲解

五个格子、一个起点、两个动作，够用了。两点先讲明。其一，奖励挂在所处的状态上，写作 r(s)，这是 CS234 的约定；Sutton&Barto 把转移之后那个奖励记成 R_t+1，两套记号每个下标都差一（记号）。其二，d(s) 是访问频率而不是转移概率：它是策略跑完 4 步后各格子被占用的时间比例，五个数加起来等于 1。这两样东西下一镜才开始动。

5 / 87

同一个世界、同一套 r(s)，只是换了策略。除了共同的起点 s3，两条轨迹没有一个格子重合。

讲解

先不谈分布，只看两条路。π_L 两步撞上左墙，剩下的时间全耗在 s1；π_R 两步到达右端，剩下的时间全停在 s5。注意除了共同的起点 s3，这两条轨迹没有一个格子重合。这就是「序贯」的全部内容：第一个动作本身没给你任何奖励，它做的是把你送进一片完全不同的区域，而你之后能看见什么、能拿到什么，全由那片区域决定。

6 / 87

每根柱子 = 正上方那个状态被访问的时间比例。把策略从 π_L 拨到 π_R —— 数据本身就换了。监督学习里换掉参数，这排柱子一根都不会动。

讲解

看什么：盯住最左和最右那两根：策略一拨过去，s1 那根要从 0.50 塌到 0.00、s5 那根要从 0.00 涨到 0.50，而中间 s3 那根必须全程钉在 0.25 一动不动——看到「四根重排、起点不动」，就等于看见了「除了起点，你站在哪里全由 θ 说了算」。　—— 把两条轨迹折成频率，得到的不是同一个分布的两次采样，而是两个不同的分布，挑选它们的正是策略本身。这就是真正的分界线：监督学习里数据分布 D 是外生的，你换模型、换初始化、换优化器，D 一根柱子都不会动；RL 里 θ 同时干两件事——决定在给定状态怎么选，以及决定你会站到哪些状态上去。第二件事在监督学习里根本不存在。

7 / 87

\begin{aligned} SL : & J (θ) = \sum_{z} D (z) ℓ (z, θ) \\ RL : & J (θ) = \sum_{s} d_{θ} (s) r (s) \end{aligned}

d^π_L=(0.50,0.25,0.25,0,0) 给 Σd·r = 0.50；d^π_R=(0,0,0.25,0.25,0.50) 给 5.00。r(s)=(+1,0,0,0,+10) 两边完全相同 —— 监督学习把 θ 放进被加项，RL 把 θ 放进权重。

讲解

所以这个例子里 J 从 0.50 变到 5.00，不是因为奖励改了——r(s)=(+1,0,0,0,+10) 一个字没动——而是因为求和的权重整个换掉了。这也解释了「好」为什么不能删：没有 J 就没法说 π_R 比 π_L 好。顺带一提，这里用的是每步平均奖励 Σd(s)r(s)，γ 尚未登场；折扣回报 V^π 是后面的知识点，别把两者混起来。

8 / 87

\begin{aligned} SL : & \nabla_{θ} J = \sum_{z} D (z) \nabla_{θ} ℓ (z, θ) \\ RL : & \nabla_{θ} J = \sum_{z} p_{θ} (z) r (z) \nabla_{θ} \log p_{θ} (z) \end{aligned}

那条谱系是真的，但它只有一根轴。分界线在另一根轴上 —— 只有 RL 的 d 会随 θ 移动，沿谱系走再远也跨不过去。

讲解

「RL 只是监督信号更弱的监督学习」错在把二维的事画成了一维：谱系那根轴量的是信号强弱，分界线却在另一根轴上——D 不含 θ，d_θ 含 θ。后果直接落到梯度上：测度不含 θ 时导数可以钻进求和号（上行）；含 θ 时唯一的梯度来源是 ∇log p_θ（下行）。而 r 不含 θ，照上行去算恰好是 0——你只要真写出一个非零的 loss，就不得不请出 log π_θ，那正是 REINFORCE：它不是技巧，是链式法则打在会移动的测度上（补课）。

9 / 87

知识点 1 · 总结

三个承重词，与那条真正的分界线

核心结论

θ 不在被加项里，它在求和的权重里：监督学习 J=Σ D(z)ℓ(z,θ)，D 与 θ 无关；RL 的 J=Σ d_θ(s)r(s)。

底层机制

走廊那一例 J 从 0.50 变到 5.00，而 r(s)=(+1,0,0,0,+10) 一个字没改 —— 变的是权重。

常见误解

误解：把 RL 放进「监督→RL→无监督」的信号强弱谱系中间。谱系是真的，但它只有一根轴。

与你的考试

删「学」→规划，删「序贯」→赌博机，删「好」→没有优化问题。

10 / 87

知识点 1 · 检验

你把一批 LLM agent 的执行轨迹（由策略 π_b 采集）冻成数据集，用 − reward 当 loss 跑 SGD 训出 π_θ。训练 loss 一路下降，但把 π_θ 放回环境真跑，回报反而低于 π_b。最可能的原因是哪一条？

知识点 3

2 · 四要素坐标系

11 / 87

这四个要素同时出现才叫 RL。但它们的难度并不相等 —— 如果只能放弃一个，放弃哪个损失最小？

讲解

四盏灯是这一讲的坐标系，后面所有范式的区别都是灭掉其中某几盏。但坐标系本身不告诉你哪个轴更难走。这一集只问一件事：这四个里哪一个是真正的理论难点？先说结论的形状——大多数人会挑错，而挑错的那个恰好是四个里看起来最简单的。

12 / 87

探索是四者里最便宜的ε-greedy 三行代码，退火一下就完事

ε-greedy：以 1−ε 选当前最好的，以 ε 随机挑一个；ε 从 0.1 退火到 0.01 —— 探索这件事就算办完了。难的是优化。

讲解

这个判断很难避免，因为它有教科书作依据：介绍探索时第一个例子几乎总是 ε-greedy，而 ε-greedy 确实只有三行——以 1−ε 的概率选当前估计最好的，以 ε 的概率随机挑一个，再让 ε 随时间衰减。相比之下优化那一栏要面对高维非凸、要调学习率、要处理方差，看起来才是硬骨头。于是很自然地把探索归进「工程细节」。下面用两条臂检验一下这个判断。

13 / 87

只有两个数字要记：估计值 Q̂（至今观测到的平均收益）与样本数 n（区间宽度 ∝ 1/√n）。B 才是好臂 —— 但智能体不知道，它只有 Q̂。

讲解

设定尽量简单：两条臂，真实均值 0.50 与 0.60，所以 B 是好臂。但智能体看不见 μ，它只有自己算出来的 Q̂ 和样本数 n。策略取最极端的一端——纯贪心，ε=0，每步都选 Q̂ 更大的那条。这样做不是为了让它失败得难看，而是为了把「探索不足」这一个变量单独隔离出来：优化没有难度（就两个数取最大），泛化没有难度（就两条臂），延迟后果也没有（拉一次结算一次）。四盏灯里只剩探索这一盏在起作用。

14 / 87

热身各拉一次：Q̂(A)=1.00，Q̂(B)=0.00，区间都还很宽。A 恰好得 1、B 恰好得 0 —— 在 μ=0.5 / 0.6 下这是很平常的一次运气。

讲解

先给两条臂各一次机会。A 这次得了 1，B 这次得了 0。这不是刻意构造的坏运气——在均值 0.5 和 0.6 的伯努利臂上，这个结果出现的概率是 0.5×0.4 = 0.2，五次里有一次。注意此刻两条臂的置信区间都很宽：一个样本几乎什么都不能确定。真正的问题出在下一步：纯贪心会怎么用这两个数字。

15 / 87

此后一万步纯贪心每步都选 A：它的区间收缩到 0.49–0.51 正压在自己的真值线上，~~而 B 那根一动不动~~ —— n(B) 永远是 1。

讲解

上一镜两根区间一样宽，这一镜看它们的宽度差：A 那根已经收到 0.49–0.51 的一条细线（n 从 1 涨到 9999），B 那根仍然贯穿全图——因为 n(B) 还是 1。两镜对照就是这一集的全部论证：贪心收敛了，收敛到了错的臂，而且它手上没有任何数据显示 B 更好。注意 A 这一半在统计上完全正常、无可指责；问题全在另一半。

16 / 87

探索的真正困难：删失方式由你自己决定，错误的估计阻止了纠正它所需的数据。这不是采样效率问题 —— 给它一亿步也不会好转。

讲解

把机制画成回路就清楚了：Q̂(B) 偏低 → 贪心不选 B → B 拿不到新数据 → Q̂(B) 保持偏低。这是一个闭环，而且它自我维持——**增加步数不解决**，因为多出来的每一步都落在 A 上。这就是探索与其它三个要素在性质上的差别：优化不足可以用更多算力补，泛化不足可以用更多数据补，而探索不足会让「更多数据」这件事本身失效，因为你拿不到需要的那部分数据。回到 KP1 的结论：策略决定数据分布，而数据分布又决定策略学到什么。

17 / 87

那句话错的不是「三行代码」，而是~~把探索当成噪声问题~~。ε-greedy 对「哪条臂更该被试」一无所知（Q̂ 差 0.001 和差 0.5，它给的探索概率一模一样）；UCB 让区间宽度参与决策，于是「n=1 的臂区间宽」直接变成「去拉它」的理由。

讲解

现在指名回去。「探索三行代码就办了」这句话，错的不是说 ε-greedy 简单——它确实简单，也确实能打破上面那个死锁，因为每一步都有 ε 的概率去碰 B。错的是它背后的模型：把探索当成**给决策加噪声**。加噪声的方案对「哪条臂更值得试」毫无判断力——两条臂估计值差 0.001 还是差 0.5，它给的探索概率完全一样，于是既在明显该利用的地方浪费，也在明显该探索的地方不够。真正的解法是让**不确定性本身参与决策**：UCB 选的是「估计值 + 置信半径」最大的那条，于是「B 只有一个样本、区间很宽」这件事直接成为去拉它的理由。死锁在机制上就不可能出现。这条线是 L11–13 三整讲的内容——如果探索真是工程细节，它不会占三讲。

18 / 87

知识点 2 · 总结

四要素里最贵的是探索，而它看起来最便宜

核心结论

探索的困难不是「多试几次」，而是删失方式由你自己决定：错的估计会阻止你拿到纠正它的数据。

底层机制

死锁：Q̂(B) 偏低 → 不选 B → B 无新数据 → Q̂(B) 保持偏低。本例 n(B) 永久冻结在 1。

常见误解

误解：把探索当成给决策加噪声。加噪声降低死锁概率，但对「哪个动作更值得试」没有判断力。

与你的考试

正解是让不确定性参与决策（UCB / Thompson）—— L11–13 三整讲。

19 / 87

知识点 2 · 检验

本例中纯贪心跑一万步后，它对臂 B 的置信区间宽度会怎样？

知识点 4

3 · 用四盏灯划清边界

20 / 87

三个相邻范式，各自是 RL 减去某几盏灯。模仿学习只减掉一盏——那省下来的困难，~~去哪儿了~~？

讲解

四盏灯是上一拍建立的坐标系。Brunskill 用整整五张 slide 做这件事：同样的四条，每张划掉不同的几条，分别用来分开规划、监督学习、无监督学习和模仿学习——那本来就是一个动画，被拆成了五张静态图。但分类本身不值钱，值钱的是它能不能预测代价。模仿学习只灭掉一盏灯，是四个范式里最像 RL 的那一个。那么它省下的那部分困难，是真的消失了，还是换了个地方冒出来？

21 / 87

ε T = 0.1 \times 10 = 1

模仿学习把 RL 约化成监督学习，探索问题被绕开了。既然是监督学习，就按分类问题结账：错一步赔一步，总和 = T = 10。

讲解

这条推理链每一步都站得住，官方 slide 第 26 页写的原话就是「Reduces RL to supervised learning」和「Avoids exploration problem」。把专家轨迹上的每个「状态→动作」当成一个带标签的样本，训练一个分类器，探索问题确实不存在了：数据是现成的，不用自己去采。既然现在它是标准分类问题，那就按分类问题结账——每步错误率 ε，走 T 步，期望错 ε·T 步，ε=0.1、T=10 就是 1 步。训练时 90% 准确，测试时也该差不多，监督学习的泛化理论一向是这么用的。

22 / 87

一张表代替五张 slide：规划灭一盏，监督学习灭两盏，模仿学习也只灭一盏。记号：π* 专家 · π 学到的 · ε 每步分类误差 · T 时域 · t 首次偏离时刻 · J 期望总代价（每步 ∈ [0,1]）。

讲解

把牌摊开：列是四盏灯，行是四个范式。规划只灭「探索」——动力学和奖励已经给你（围棋规则就是模型），难点全在算，所以 L2 整讲都在做规划。监督学习灭两盏，而且反馈更强，它给的是正确标签。无监督学习那一行和监督学习一模一样，区别只在连标签也没有。模仿学习也只灭一盏，但灭法不同：探索被「别人的示范」顶替了。表下那句话是第一条真正的分界——RL 的反馈是评估性的，只告诉你所选动作得几分；监督学习的反馈是指导性的，直接告诉你正确答案是什么。

23 / 87

T = 10，每步正确率 90%（ε = 0.1）。从 t = 3 起，剩下的 8 步全部落在示范没覆盖的状态里 —— 那里没有任何监督信号。

讲解

把 T=10、ε=0.1 这条具体轨迹画出来。绿线是专家示范，绿点是示范数据覆盖到的状态；监督学习的泛化保证只在这些状态构成的分布上成立。假设第一次分类错误发生在 t=3，智能体落到了一个专家从未去过的状态。要紧的不是这一步错了，而是从这一步起，它每一步的输入都来自训练时没见过的分布——那里的分类器保证是空的。剩下的 8 步不是「有可能错」，而是「没有任何理由认为它对」。

24 / 87

同一批柱子、同一个坐标轴，只换了「一次错误值多少」的定义：监督记账总和 = T = 10，轨迹记账总和 = 10+9+…+1 = 55 = T(T+1)/2。

讲解

看什么：盯住最左边 t=1 那根柱子和最右边 t=10 那根：如果 t=1 从 1 格长到满格 10、而 t=10 始终停在 1 格不动，就说明「代价取决于错在什么时候」这件事被看到了；如果十根一起等比例长高，那就说明什么也没发生。　—— 于是必须换一种记账。柱高不再是「错一步赔一步」，而是「首次偏离发生在 t 时，之后还剩多少步处在无保证区」，也就是 T−t+1。柱子的位置一根没动，只有高度在变：t=1 那根从 1 涨到 10，t=10 那根纹丝不动——早错致命，晚错便宜。把柱子加起来，10+9+…+1 = 55 = T(T+1)/2。监督记账的总和是 T，轨迹记账的总和是 T²/2 的量级。多出来的那个 T，就是「一次错误会污染整条剩余轨迹」的价格。

25 / 87

J (π) - J (π^{*}) \approx ε \sum_{t = 1}^{T} (T - t + 1) = ε \frac{T (T + 1)}{2}

三角形的面积就是那个 T²。补课：课上只讲了直升机漂移的故事，没给这个界。

讲解

具体实例还在屏上，现在写成一般式。乘上首次偏离的概率 ε，得到 ε·T(T+1)/2；ε=0.1、T=10 时是 5.5 步（这是小 ε 下的一阶估计，精确值 4.14——已经偏离过就不再重复计入）。【补课】定理形式来自 Ross–Bagnell 2010：J(π) ≤ J(π*) + εT²，并且有构造使这个二次项紧，所以它不是分析放松的产物。L01 只讲了直升机漂移的故事，L07 才给这个界。DAgger 的做法是在学生自己走到的状态上查询专家，把它拉回 O(εT)。　具体：ε = 0.1、T = 10 → 0.1 × 55 = 5.5 步（小 ε 下的一阶估计，精确值 4.14）　定理形式（Ross–Bagnell 2010）：J(π) ≤ J(π*) + εT²，且二次项是紧的　换成 T = 100、每步 99% 正确：εT 仍是 1 步，而 εT² = 100 步 = 整条轨迹　DAgger（2011）把它拉回 O(εT)：代价是训练时要能在学生走到的状态上查询专家

26 / 87

~~账表用错了~~ —— 监督学习的灯表里「延迟后果」是灭的，而模仿学习这盏还亮着，它的标价正好是多出来的那个 T：εT 少乘了一个 T。

讲解

回到第二拍：那条推理错在哪一步？不在「约化成监督学习」，这一步是对的。错在下一步——它顺手把监督学习那一整张灯表也搬了过来。可模仿学习的灯表里「延迟后果」还亮着，灭掉的只有「探索」。εT 恰恰是在延迟后果灭掉的前提下成立的：样本独立，一次错误只弄坏这一个样本。延迟后果亮着，就意味着一次错误改变了之后所有样本的分布，单次错误的代价从 1 变成 T−t+1，于是多乘了一个 T。对做 LLM agent 的人：在专家轨迹上做 SFT 就是行为克隆，工作流越深，这个二次项越咬人。

27 / 87

知识点 3 · 总结

相邻范式 = RL 减去某几盏灯

核心结论

规划=RL−探索；监督学习=RL−探索−延迟后果，且反馈是标签；模仿学习=RL−探索（用示范替代）。

底层机制

RL 收到的是所选动作的评估性分数，监督学习收到的是指导性的正确答案。

常见误解

误解：以为模仿学习绕开了 RL 的困难。它保留延迟后果，困难转成分布偏移，误差近似按深度平方累积。

与你的考试

四灯表就是课程地图：L2 规划 · L7 模仿 · L3 起才真正开始「学」。

28 / 87

知识点 3 · 检验

同一个行为克隆策略，每步分类误差固定为 ε = 0.001（99.9% 正确）。任务时域从 T = 10 拉长到 T = 100。按第二拍那笔监督学习的账，期望损失变成 10 倍。按本集的三角形记账，它变成多少倍？

知识点 5

4 · 交互回路、历史、智能体状态

29 / 87

回路上来回运的只有 aₜ 出去、oₜ 与 rₜ 回来。那 MDP 五元组 ⟨S,A,P,R,γ⟩ 里那个 S，是谁写下来的？

讲解

这个回路是整门课唯一的数据来源：算法能拿到的每一个比特，都从这两条线上过。可是翻开任何一本教材，MDP 的第一个符号就是状态空间 S，而 S 从来没有出现在这两条线上——世界发出的是观测，不是状态。这一集就补这个缺口：S 从哪来、谁有权定它、定错了要付什么价。

30 / 87

最自然的读法：状态是环境的一部分。⟨S,A,P,R,γ⟩ 把 S 与 A 并列写在最前面；obs, info = env.reset() 一行就把状态递到手上；画转移图时状态圆圈也画在环境那侧。我的活儿是在给定的 S 上学 π。

讲解

这个读法几乎每个人第一次都会采用，而且它有很好的理由：MDP 的定义把 S 和 A 并列写在最前面，看上去都属于问题本身；Gym 里一行 env.reset() 就把状态递到手上；教科书画转移图时，状态圆圈也确实画在环境那一侧。顺着这条读法往下走，「状态空间多大」就成了一个客观事实——你只能去查，不能去选。Brunskill 在课上也说，早期讨论里状态常被当成某种不可变的东西。

31 / 87

h_{t} = (a_{1}, o_{1}, r_{1}, a_{2}, o_{2}, r_{2}, \dots, a_{t}, o_{t}, r_{t})

hₜ 是记录，f 是你挑的压缩，sₜ = f(hₜ) 是结果。aₜ 由你发出、oₜ 与 rₜ 由世界发出，真实世界状态从不出现在这条带子上。slide 46：sₜ 还可装算法自身的元信息。记号：hₜ 从 a₁ 起没有 o₀；slide 47 把 f 漏印成 sₜ = (hₜ)。

讲解

三个符号各就各位。hₜ 是到 t 为止的完整交互记录，一条只增不减的带子；f 是任意一个把带子映成某个对象的函数，它不受世界约束，是你写在智能体里的代码；sₜ = f(hₜ) 才是算法真正读到的东西。slide 46 还多说了一句关键的话：sₜ 可以包含算法自身的元信息，比如已经花掉多少计算、还剩几步决策。这一条先记下，最后一拍要用它做刀。

32 / 87

一条 6 格走廊，只有四面墙感（读数位序上右下左）：|O| = 2⁴ = 16，动作上下左右 |A| = 4，撞墙原地不动。c₂ 到 c₅ 读数完全相同，可它们在世界里是四个不同的位置。

讲解

看什么：看黄色 token 从 c₁ 一格一格走到 c₆：位置在变，而它脚下 c₂..c₅ 那四格的读数始终是同一串 1010 —— 位置动了、观测纹丝不动，这就算是看到了 f₁ = oₜ 分不清它们。　—— 把数字钉死：观测是 4 比特，名义上 |O| = 2⁴ = 16（这条走廊里实际只出现三种读数）；动作四个，撞墙原地不动。c₁ 左侧有墙读 1011，c₆ 右侧有墙读 1110，中间四格上下有墙、左右通行，一律读 1010。取 sₜ = oₜ 的智能体在这四格里收到的输入完全一致，却处在四个不同位置上——它没有任何办法知道自己离出口还有几步。

33 / 87

s_{t} = f (h_{t}) f_{1} = o_{t} f_{2} = (o_{t - 1}, a_{t}, o_{t}) f_{3} = h_{t} (t = 10)

同一条 6 格走廊、同一条 hₜ，|O| = 16、|A| = 4，世界侧一个比特都没改。变的只有 f —— |S| 从 16（只留最近读数）到 1024（两次读数 + 中间那个动作）再到 1.15×10¹⁸（整条带子一个字不丢）。

讲解

三个 f 都作用在同一条 hₜ 上，世界侧一个比特都没改。位宽这样算：f₁ 只留 4 比特；f₂ 留两次读数加中间那个动作，4+2+4 = 10 比特；f₃ 取 t = 10 的整条带子，每步 2+4 比特（把 rₜ 当作 oₜ 的函数，否则再乘 |R|¹⁰），共 60 比特。于是 |S| 从 16 到 1024 再到 2⁶⁰ ≈ 1.15×10¹⁸——同一个世界，三个完全不同的 MDP。写下这些差别的只有 f。

34 / 87

f : H \to S, | S | = | f (H) |

同一条走廊的三个 f 仍在屏上：|S| ≤ 16 / 1024 / 1.15×10¹⁸。|S| = |f(H)| 是 f 的值域大小，属于你；充分性才是你和世界共同决定的。补课：样本复杂度 ~ |S||A| / ((1−γ)³ε²) —— |S| 线性进入，所以全历史不是保守选择。

讲解

抽象只有一句：f : H → S，S = f(H) 是 f 的值域，所以 |S| 是你的属性，不是世界的属性。两端都会失败。太小则不充分：f₁ 连 c₂..c₅ 都分不清，Markov 条件当场破掉。太大则学不动——【补课】表格式 RL 拿到 ε-最优策略的样本复杂度约为 |S||A|/((1-γ)³ε²)（Azar 等 2013 的下界，Sidford 等 2018 达到），|S| 线性进入；把 10⁶ 条长度 10 的轨迹撒进 1.15×10¹⁸ 个状态，重复访问几乎不会发生，这就是「无从泛化」的确切含义。

35 / 87

同一条走廊，三个 f 给出 |S| ≤ 16 / 1024 / 1.15×10¹⁸（f₃ 取 t = 10）。回到那句 ~~「S 是环境的一部分」~~ —— 这条线上只运 aₜ 与 (oₜ, rₜ) 两样。sₜ 由你在自己这侧组装 —— 最近读数、前几步的记忆，还有已用计算量、还剩几步决策（世界不发这两个数）。环境定的是 O，定 f 的人是你：S = f(H)。

讲解

错误模型断在一个可以逐字检查的地方：Gym 的接口属性叫 observation_space，从来没有叫 state_space——这个命名是准确的，是我们把它读成了状态。五元组里的 S 也不是环境自带的：换一个 f，P 和 R 全部跟着换，最优策略跟着换，而世界一个比特都没动。最锋利的一刀在左下第三行——「还剩几步决策」根本不是世界里的物理量，可它明明白白写在 slide 46 的 sₜ 里。

36 / 87

知识点 4 · 总结

回路 → 历史 → 智能体状态：S 是设计出来的

核心结论

sₜ = f(hₜ) 是你选定的压缩。环境定的是观测空间 O，定 f 的人是你。

底层机制

选 f 同时定下两件反向变动的事：充分性与 |S|。而 |S| 线性进入表格式 RL 的样本复杂度。

常见误解

误解：把 sₜ 当成世界的真实状态。回路上只运 aₜ 出去、oₜ 与 rₜ 回来，sₜ 从未跨过那条线。

与你的考试

f 的现代形式就是递归序列模型：RNN 是它，LLM agent 的 context window 也是它。

37 / 87

知识点 4 · 检验

把这条走廊从 6 格加长到 60 格（中间 58 格读数全是 1010），f₂（保留最近两次读数与中间那个动作）会怎么变？

知识点 6

5 · Markov 条件 = 充分统计量

38 / 87

p (s_{t + 1} ∣ s_{t}, a_{t}) = p (s_{t + 1} ∣ h_{t}, a_{t})

Markov 条件说：把 hₜ 换成 sₜ，对下一步的预测一点都不变。它是一个关于「条件分布相等」的断言。

讲解

先把条件本身读准。它不是「未来只依赖现在」这种口号，而是一个精确的断言：两个条件分布相等。左边只给 sₜ 和 aₜ，右边给整段历史 hₜ 和 aₜ，两者对 s_{t+1} 的预测完全一样。用统计学的话说，sₜ 是历史关于未来的**充分统计量**。这一集要查的不是这个条件本身，而是人们拿它去问的那句话：「这个问题是不是马尔可夫的？」

39 / 87

有些问题天生是马尔可夫的，有些天生不是 —— 判断它，就是在判断这个世界。

讲解

这个模型几乎是被术语本身诱导出来的：我们说「马尔可夫决策过程」，把 Markov 当成 process 的形容词，于是它听起来像在描述那个过程。配上两个例子更是天衣无缝——下棋，当前局面显然包含一切；只有四向墙感的机器人，显然看不到全局。于是「这个问题是不是马尔可夫的」看起来是一道关于世界的判断题，答案由世界给定，你只能接受。下面做一件很小的事就能检验它：不动世界，只换表示。

40 / 87

先命名：一个世界、两处混叠的格子（A 该向左、B 该向右）、三种表示（f₁ = oₜ · f₂ = hₜ · f₃ = b(s) 对位置的后验信念）、两个判据（① 是否充分 ② 状态空间多大）。都还没开始检验。

讲解

世界固定下来：一条五格走廊，机器人只有四向墙感。格 A 和格 B 的读数都是 1010——上下有墙、左右无墙，一模一样；但它们在世界里位置不同，最优动作也不同。接下来不动这个世界，只换三种把历史压缩成状态的方式 f，并对每一种问两个问题：它充分吗？它的状态空间有多大？两个判据都要问，因为只问第一个会得出「取全历史就完事了」这种没用的答案。

41 / 87

p (s_{t + 1} ∣ o_{t}, a_{t}) \neq p (s_{t + 1} ∣ h_{t}, a_{t})

f₁ = oₜ 不充分：Markov 条件在此失效 —— 历史确实多知道一件事（从左边进来 → 我在 A；从右边进来 → 我在 B）。② 状态空间 |S| = 16。

讲解

第一种表示：直接令 sₜ = oₜ，也就是只看最近一次观测。此时 A 与 B 被压到同一个状态，而从它们出发的转移不同，于是屏上那个不等号成立——给定 oₜ 的预测与给定 hₜ 的预测不一样，Markov 条件失效。注意失效的原因说得很具体：历史里有一条 oₜ 没有的信息，就是「我是从哪边走进这条走廊的」。状态空间倒是很小，四位墙感一共 16 种。所以 f₁ 在判据②上满分，在判据①上不及格。

42 / 87

s_t := h_t

f₂ = hₜ 充分，而且是平凡地充分 —— 等式两边成为同一个条件分布，无需任何假设。代价：② |S| 随 t 指数增长，实践中不可用。

讲解

第二种表示：令 sₜ := hₜ。此时 Markov 条件的证明是平凡的——把定义代进去，等式两边字面上就是同一个条件分布，无需对世界做任何假设。这个平凡性正是整集的转折点：**它说明任何过程都可以被做成 Markov 的**。代价当然是状态空间随时间步指数增长，一条 t 步的历史有指数多种，没法拿它做算法。所以 f₂ 在判据①上满分，在判据②上不及格——恰好和 f₁ 相反。【补课】课上只是断言「取全历史就是 Markov 的」，没有给出这个代入证明，也没有点出它的推论。

43 / 87

b_{t} (s) = p (s_{t} = s ∣ h_{t})

f₃ 兼顾两条：信念充分，且维度不随时间增长。

讲解

看什么：盯住五根柱子的形状变化：起始是五格等概率（都是 0.20 的平顶），观测进来之后概率必须集中到 A 与 B 两格上、其余三格塌到接近 0。看到「平顶变成两个尖峰」，就等于看见了「观测把信念收窄了」；如果五根一起等比例升降，那说明观测没有携带信息，这一镜的论点不成立。　—— 第三种表示：不记全部历史，只记它蕴含的那件事——我现在在哪的后验概率分布 b(s)。走进走廊之前，五个格子等可能；观测到 1010 并结合「我是从左边进来的」之后，概率集中到 A 上。【补课】课上顺口提过「维护一个信念分布就能决策」但没证——这就是**信念状态 MDP 归约**：b 是 POMDP 的充分统计量，于是原问题化为一个以信念为状态的 MDP。代价是状态空间从有限集变成了连续单纯形，但关键在于它的**维度不随 t 增长**，这是它与 f₂ 的根本差别。深度 RL 里用 RNN 隐状态当 sₜ，是这条路线的近似版本。　表示三： f₃ = b(s) 对自己位置的后验信念　① 充分？充分（信念是 POMDP 的充分统计量）　② 状态空间？连续单纯形，但不随 t 增长

44 / 87

世界一个字都没改，变的只有这一列。所以「这个问题是不是马尔可夫的」问错了对象 —— 它问的是表示，不是世界。真问题：能否找到一个既充分、又足够小的表示。

讲解

现在指名回去。开头那个模型说「有些问题天生马尔可夫，有些天生不是」。但这张表里，世界从头到尾是同一条走廊、同一套墙感，一个字都没改，而「是否充分」这一列却随着 f 的选择在变。f₂ 的平凡证明更是把话说死了：任何过程都能被做成 Markov 的。所以那句问话问错了对象——它以为在问世界，实际在问你选的表示。至于下棋为什么感觉「天生 Markov」：那不是棋的属性，而是**棋盘这个表示恰好既充分又紧凑**，好到你根本没意识到自己做了一次选择。真正的问题因此变成了一个设计问题：能否找到既充分又足够小的 f。这个问题贯穿整门课——函数逼近就是在挑 f，而 POMDP 的困难就是 f 必须自己从历史里攒信息。

45 / 87

\underset{slide 上写了}{\underset{⏟}{p (s_{t + 1} ∣ s_{t}, a_{t}) = p (s_{t + 1} ∣ h_{t}, a_{t})}} \underset{课上没写，但必需}{\underset{⏟}{p (r_{t} ∣ s_{t}, a_{t}) = p (r_{t} ∣ h_{t}, a_{t})}}

补课：完整的 Markov 假设是两条，课上只写了转移那一条。少了右边这条，V(s) 作为「s 的函数」就没有良好定义 —— 上面那个反例里转移完全 Markov，而 V 却不是 s 的函数。Sutton&Barto 直接写联合分布 p(s′,r | s,a) 更干净。

讲解

【补课】顺手补掉这一讲的一个真实漏洞。slide 上的 Markov 条件只约束了**转移**，而后面所有内容都默认 V(s)、Q(s,a) 是状态的函数——要让这个成立，奖励也必须只依赖 (sₜ,aₜ)。屏上那个反例就够说明问题：设想奖励取决于你是第几次到访某个状态，那么转移可以完全 Markov，而 V 却不是 s 的函数，因为同一个 s 在不同时刻值不同。所以完整的假设是转移 + 奖励两条。Sutton&Barto 第 3 章的处理更干净：直接写一个联合分布 p(s′,r|s,a)，两条一次说完（【记号】这也是两套记号的又一处差别）。

46 / 87

知识点 5 · 总结

Markov 性是表示的性质，不是世界的性质

核心结论

sₜ 是历史关于未来的充分统计量，而「是否充分」取决于你选的 f:H→S。

底层机制

取 sₜ:=hₜ 平凡满足 Markov（代入定义即得），代价是 |S| 随 t 指数增长。信念 b(s) 充分且维度不随 t 增长。

常见误解

误解：去问「这个问题是不是马尔可夫的」。下棋之所以像天生 Markov，是棋盘这个表示恰好又充分又紧凑。

与你的考试

【补课】完整假设是转移 + 奖励两条，slide 只写了转移。

47 / 87

知识点 5 · 检验

「任何过程取 sₜ := hₜ 都满足 Markov 条件」—— 这个平凡事实说明了什么？

知识点 7

6 · MDP / POMDP / 赌博机

48 / 87

四位墙感（上/下/左/右各有没有墙），别的什么都不知道。A 与 B 是两个不同的位置，读数却逐位相同（上墙·下墙·左通·右通）。多读几次，能不能把它们分开？

讲解

这个例子是 Brunskill 在黑板上现画的，她自己说后排大概看不清——它是全讲唯一一个真正的反例论证，值得画清楚。机器人的观测空间只有 16 个取值（四边各有无墙），而横向走廊里第 1 到第 5 格的读数完全一样，A、B 只是其中两格。注意问题问的不是「能不能猜对」，而是「多读几次能不能分开」：这两件事在噪声下是同一件事，在这里不是。

49 / 87

重复测量同一个量，半宽 0.46 → 0.23 → 0.12 → 0.06：噪声是「围绕真值的抖动」，而抖动能被平均掉。所以 POMDP 不过是 MDP 外面套了一层测量误差：观测模型照写、算法照用，只把 k 加大。

讲解

这个说法在你自己的领域里几乎是条件反射：LLM 输出不稳定就多采几条、投票或自一致性聚合；估计量有噪声就加样本，标准误按 1/√k 往下掉。它在噪声下是完全正确的，屏上那组收缩的区间就是它的机制，货真价实。而且它给出的工程建议非常省事：观测模型照写、算法照用，只把采样次数加大——多数 POMDP 的实际处理确实是从这里起步的。

50 / 87

b_{t} (s) = p (s_{t} = s ∣ h_{t})

四个对象：s 世界状态（不可见）· o 观测（四位墙感）· Λ = p(o|A)/p(o|B) 似然比 · b(s) 对 s 的后验。k = 站在原地重复读到同一个 o 的次数。全片只有这四个东西在动。

讲解

【记号】课上只说了一句「maintain a belief state over what the other cards are」，没给符号。本片沿用标准 POMDP 记号 bₜ(s) = p(sₜ = s | hₜ)。【补课】完整的信念更新要同时用观测模型与转移模型：b′(s′) ∝ p(o|s′,a) · Σ_s p(s′|s,a) b(s)——这就是课上提了却没证的信念状态 MDP 归约，b 是 POMDP 的充分统计量，代价是状态空间从有限集变成概率单纯形。为把话说干净，下面让机器人站在原地重复读数，转移那一项冻住，只剩似然。

51 / 87

先把那个说法当真算一遍：设 p(o|A) = 0.8、p(o|B) = 0.2，于是 Λ = 4；先验 b₀(A) = b₀(B) = 0.50（k = 0 那根就是先验）。b(A) 以 4^k 压向 1 —— 读五次就到 0.999。

讲解

数字是精确的：b_k(A) = 0.8^k / (0.8^k + 0.2^k)。k=1 → 0.800，k=2 → 0.941，k=3 → 0.985，k=5 → 0.999。指数收敛，快得几乎不用讨论。这一镜的作用是把第 2 拍那个说法当真算一遍：只要两格的读数分布确实不同，重复读数就真的能把它们分开，而且极快。请记住这排柱子的形状——下一镜只改一个数字。

52 / 87

唯一的改动：把两格读数分布改成相同，p(o|A) = p(o|B)，于是 Λ 从 4 变成 1。先验没动、k 没动、贝叶斯公式没动 —— 六根柱子全部~~塌回先验 0.50~~。1^k ≡ 1，k 再大也不动。

讲解

看什么：看 k=1 到 k=5 这五根柱子是否全部落回 0.50 那条灰线上——只把似然比 Λ 从 4 改成 1，后验就退回先验，看到这一点才算数。　—— 这就是全片那一步。混叠的精确含义不是「这次读数碰巧一样」，而是 p(·|A) 与 p(·|B) 作为分布完全相同。于是任何观测序列的似然比都是 1×1×…×1 = 1，后验比值恒等于先验比值——不是这一次分不开，而是~~任何数据都分不开~~。统计学里这有名字：A 与 B 在这个观测模型下~~不可识别~~（non-identifiable）。不可识别不是「估计得慢」，是「数据里根本没有这条信息」。

53 / 87

\frac{b_{k} (A)}{b_{k} (B)} = {(\frac{p (o ∣ A)}{p (o ∣ B)})}^{k} \cdot \frac{b_{0} (A)}{b_{0} (B)}

一般形式是比值形式的贝叶斯更新：采样次数 k 进的是指数，观测模型的区分度 Λ 是底数。

讲解

把前两镜合成一个式子：b_k(A)/b_k(B) = Λ^k · b₀(A)/b₀(B)。采样次数 k 只能进到指数上，观测模型的区分度 Λ 是底数。加样本就是把指数拉大，这对 Λ>1 有效、对 Λ=1 完全无效——1 的任何次幂都是 1。于是「观测是否充分」有了定量版本：不是问观测有多准，而是问是否存在一对状态使 Λ ≡ 1。屏上那两根柱子是同一个 k、同一个先验、同一个公式算出来的。　k 只出现在指数上。底数是 1 的时候，指数再大也没有用。　同一个 k = 5 · 同一个先验 0.50 · 同一个更新公式

54 / 87

判据一：p(o′|oₜ,aₜ) = p(o′|hₜ,aₜ)（能把 hₜ 缩成 oₜ 吗）。判据二：p(o′|hₜ,aₜ) = p(o′|hₜ)（能把 aₜ 划掉吗）。两条互相独立，所以真正的表格是 2×2；课上讲的三分法只占三格。

讲解

两条判据形式上是同一句话：某个条件分布里，能不能划掉一个参数。判据一划掉 hₜ（留 oₜ 就够，这就是 sₜ = oₜ 的 Markov 条件），判据二划掉 aₜ（动作不影响下一个观测）。它们互相独立，所以真正的表格是 2×2，右下那格课上没提但确实存在。【补课】课上说赌博机是 MDP 的「简单版本」却没给归约：判据二成立时 aₜ 对 o′ 无影响，逐步最大化即时奖励即最优，问题退化成 H=1——这才是「没有延迟后果」的准确说法。

55 / 87

左：噪声，标准误 ∝ 1/√k。右：混叠，b(A) 与 k 完全无关。~~POMDP 只是噪声大一点的 MDP~~ 断在 Λ = 1 —— 底数是 1，样本量进不了式子。1/√k 压的是方差，混叠丢的是可识别性；补救办法也不同：噪声加样本，混叠只能改表示。

讲解

指名说清：~~POMDP 只是噪声大一点的 MDP，多采样就好~~，断点在 Λ=1。左边那组区间是这个说法自己的机制，1/√k，压的是方差；右边丢的是可识别性，与样本量无关。补救办法因此完全不同：噪声加数据，混叠只能改表示——全历史、信念分布、RNN 隐状态，或者对你手上的 LLM agent 来说，就是 context 里到底带了什么。带不进 context 的那部分信息，采样再多、投票再多也拿不回来。

56 / 87

知识点 6 · 总结

三分法与它的两条判据

核心结论

判据只有两条：观测是否充分、动作是否影响未来。

底层机制

感知混叠是 POMDP 的典型成因：不同世界状态给出相同观测，只有累积历史能区分。

常见误解

误解：以为 POMDP 只是噪声大一点的 MDP。不可区分是系统性的，加采样无用，只能改表示。

与你的考试

赌博机不是玩具：去掉延迟后果，才能把探索问题分析干净（L11–13）。

57 / 87

知识点 6 · 检验

把走廊 A、B 的观测模型改成 p(o|A) = 0.51、p(o|B) = 0.49（几乎混叠，但不完全）。先验各 0.50，站在原地连续读到同一个 o。要让 b(A) ≥ 0.99，k 大约要多大？先算，再看选项。

知识点 8

7 · 三大部件与折扣和的收敛性

58 / 87

γ = 1右边这个和还是一个数吗

价值函数是一个无穷项的和：V^π(s) = E[r_t + γr_{t+1} + γ²r_{t+2} + γ³r_{t+3} + ⋯]。课上原话是「折扣因子 γ 在 0 和 1 之间」，官方 slides 上连这句都没写 —— 那么真的取到 1 的时候呢？

讲解

CS234 第一讲把价值函数定义成一个无穷项的加权和，然后一句带过：折扣因子在 0 和 1 之间；官方 slides 连这句都没写。可是「V^π 等于某个无穷和」本身是有前提的——无穷多项相加未必等于任何一个数。整门课后面的一切（比较策略、Bellman 方程、样本复杂度界）都建立在「V^π 是良定义的有界函数」之上，而这件事在第一讲里从未被验证。这一集补这个洞。

59 / 87

很自然的读法：γ 是一把耐心旋钮，0 和 1 是它的两端 —— 一端极端近视，另一端一视同仁。

讲解

于是很自然地这样读它：γ 是一个偏好旋钮。调到 0，智能体只在乎眼前这一步；往上调，未来越来越算数；调到 1，未来和现在同等重要——每一项的权重都是 1，谁也不吃亏。按这个读法，[0,1] 是一把均匀的刻度，两端各是一种极端偏好：极端近视与极端远视。γ=1 听上去甚至更公平，因为它不歧视未来。多数人第一次学 MDP 时就是这么理解的，而闭区间的写法本身也在鼓励这种理解。

60 / 87

三件东西，先只命名不使用：模型 p(s′|s,a)、r(s,a)（智能体自己的，可以是错的）· 策略 π(s)=a 或 π(a|s) · 价值 V^π(s)。要用到的量：γ 折扣因子 · R_max 奖励的一致上界（|r| ≤ R_max）· Σγᵏ 几何级数 · S_K 前 K 项部分和。

讲解

三件东西，先只命名不使用。模型是智能体自己的表示：转移 p(s′|s,a) 与奖励 r(s,a)=E[r_t|s,a]——它可以是错的，rover 那页的智能体就相信奖励处处为 0。【补课】「错模型仍可用」的定量版本是 simulation lemma，误差按 1/(1−γ) 的幂放大。策略是 π(s)=a 或 π(a|s)。价值是本集主角。还要两个符号：γ，以及奖励的一致上界 R_max。【记号】CS234 的回报从 r_t 起算，Sutton&Barto 从 R_{t+1} 起算，下标差一位。

61 / 87

最坏情形，真实数字：r ≡ R_max = 1，γ = 0.8 —— 1 + 0.80 + 0.64 + 0.51 + 0.41 + 0.33 + 0.26 + 0.21 + 0.17 + 0.13 + ⋯。每项都在缩小，但每项缩小并不保证和有限（调和级数就是反例）。

讲解

先给一个能算的具体情形，而且是最坏的那个：每一步的奖励都顶到上限 1，γ 取 0.8，于是第 k 项恰好是 0.8ᵏ。前十项是 1、0.80、0.64、0.51、0.41、0.33、0.26、0.21、0.17、0.13。单看每一项都在缩小——但「每项都在缩小」并不保证它们的和有限：调和级数 1+1/2+1/3+… 每项也在缩小，和却发散。所以真正要看的不是项，是部分和。

62 / 87

部分和 S_K（横轴 = 加到第 K 项）：同一台机器，只换 γ。左边被一条线卡住在 5，右边~~没有任何东西拦它~~。

讲解

看什么：盯住每一根比前一根高出多少：左边这个增量一根比一根小，最后三根几乎一样高，且始终没顶到那条线；右边的增量永远是同一格，第 10 根之后还会照这个步子一直走下去。　—— 这就是全集的那一步。两边都是部分和 S_K，即前 K 项之和，唯一的差别是 γ。γ=0.8 时增量按 0.8 的幂衰减，部分和被一条线卡住——那条线是 5，而且永远够不到；γ=1 时每一项都是 1，增量不衰减，S_K=K 一路线性上升，没有任何东西拦它。收敛不是「打折多打少」的问题，是「这个和存不存在」的问题：γ < 1 让级数绝对收敛，γ=1 连收敛都谈不上。

63 / 87

|V^π(s)| ≤ ∑_k≥0 γ^k |r_t+k| ≤ R_max ∑_k≥0 γ^k

把 0.8 和 1 换成符号。第 1 步逐项取绝对值（三角不等式），第 2 步 |r| ≤ R_max 一致有界、常数提出求和号。到这里为止，还完全没有用到 γ < 1。

讲解

现在把 0.8 和 1 换成符号。第一步：期望的绝对值不超过绝对值的期望，再逐项拆开，得到 |V^π(s)| ≤ Σγᵏ|r_{t+k}|。第二步引入本集唯一的额外假设：奖励一致有界 |r| ≤ R_max，于是这个常数可以提出求和号。这个假设几乎总成立，但必须写出来——它和 γ < 1 是收敛性的两个前提，缺一不可。注意到这里为止还完全没用到 γ < 1：前两步对 γ=1 同样成立。

64 / 87

|V^π(s)| ≤ R_max ∑_k≥0 γ^k = R_max / (1−γ)

第 3 步：几何级数 Σγᵏ = 1/(1−γ) 收尾 —— 这一步要求 γ < 1。得 |V^π| ≤ R_max/(1−γ)，V^π 是良定义的有界函数；奖励恒为 R_max 时取等号，这个界是紧的。5 正是上一镜左边那条天花板。

讲解

第三步才是几何级数：Σ_{k≥0}γᵏ = 1/(1−γ)，于是 |V^π(s)| ≤ R_max/(1−γ)，级数绝对收敛，V^π 是良定义的有界函数。代回具体情形：R_max=1、γ=0.8，上界是 1/0.2=5——正是上一镜左边那条天花板。而且这个界是紧的：奖励恒等于 R_max 时取等号，不能再改进。【补课】这三步课上一句没提，官方 slides 上也没有。

65 / 87

| V^{π} (s) | \leq R_{max} / (1 - γ)

回到那把旋钮：γ=0.9 ⇒ 10 步，γ=0.99 ⇒ 100 步（左端完全短视，右端一视同仁？）。Σγᵏ = 1/(1−γ) 只在 γ < 1 成立。~~「γ=1 只是不打折」~~ —— 它不在这把尺子上，它是尺子的渐近线。

讲解

回到第二镜那把刻度。它断在第三步：Σγᵏ=1/(1−γ) 只在 γ < 1 成立；γ=1 时 Σ1=∞，上界发散，V^π 不再保证是有限数，甚至可能没有定义——于是「哪个策略更好」这个问题本身失去意义。换成 1/(1−γ) 这个坐标就清楚了：0.9 是 10 步，0.99 是 100 步，γ=1 是无穷。γ=1 不是刻度的端点，是刻度的渐近线。安全区间是 [0,1)；γ=1 要能用，必须分幕且以概率 1 终止，或改用平均回报判据。

66 / 87

知识点 7 · 总结

三大部件 + 值函数的良定性

核心结论

|V^π| ≤ R_max/(1−γ)，前提是 γ<1 且奖励一致有界。

底层机制

1/(1−γ) 是有效时域，贯穿全课：值的量级、压缩系数的倒数、样本复杂度里的那个因子。

常见误解

~~课上的口误~~：γ∈[0,1] 含了 γ=1，但那时无穷和可能发散、V^π 未必有定义。安全区间是 [0,1)。

与你的考试

【记号】CS234 回报从 rₜ 起算，Sutton&Barto 从 R_t+1 起算，差一位。

67 / 87

知识点 7 · 检验

一个任务每步奖励恒为 +1（所以 R_max=1）。你把 γ 从 0.99 调到 1，理由是「只是不再打折而已」。先自己推一遍：这一步之后最先出问题的是什么？

知识点 9

8 · Mars rover：γ 是问题定义的一部分

68 / 87

七状态链：左端小奖 +1，右端大奖 +10。π = 一直向右，每次尝试以概率 0.5 成功、否则原地（教学用设定，动力学写死以便精确求解）。这一集只查 γ 的身份。

讲解

一条七状态链，左端 +1、右端 +10，策略固定为一直向右、每次尝试以概率 0.5 成功。动力学在这里明确写死，是为了能精确求解——讲座对细节说得较松，所以本集的数字是按这个设定算出来的，不是讲座数字的逐字复刻。要查的问题只有一个：γ 到底是什么身份的量。

69 / 87

γ 只是尺度它改变多在乎未来，不改变哪个状态更好

V^π(s) = E[r_t + γr_{t+1} + γ²r_{t+2} + ⋯]。理由听起来很硬：奖励结构 r(s) 一个字都没改，γ 调小只是所有值一起缩小 —— 就像把一张图等比缩放，图上各点的高低次序不会因缩放而颠倒。

讲解

这个模型有相当强的说服力，而且它的理由是可以说出口的：奖励结构没变，γ 又只是给未来打折，那它顶多整体拉伸或压缩值函数，不该颠倒次序——就像等比缩放一张图，各点的高低关系保持不变。很多人调 γ 时确实是这么想的：把它和学习率、batch size 摆在同一个格子里，属于「求解器的旋钮」。下面用这条链上的真实数字检验一下。

70 / 87

V (s_{i}) = r (s_{i}) + γ [0.5 V (s_{i + 1}) + 0.5 V (s_{i})]

先命名：Bellman 一致性方程、右端点闭式解（撞墙原地，方程只含自己：V(s₇) = 10 + γV(s₇)）、回代顺序 V(sᵢ) = ( r(sᵢ) + 0.5γV(sᵢ₊₁) ) / ( 1 − 0.5γ )。都还没代入数字。

讲解

在动数字之前，把怎么算的说清楚。每个状态的值等于当步奖励加上折扣后的下一步期望值；因为策略是「向右，成功率 0.5」，下一步期望里一半概率到 sᵢ₊₁、一半留在 sᵢ 自己。右端点撞墙原地，它的方程里只含自己，可以直接解出闭式 10/(1−γ)。其余状态从右往左逐个回代。这个「必须从右往左」的顺序不是技巧，而是方程结构决定的——L2 会把它正式建立成动态规划。

71 / 87

γ = 0

γ = 0：折扣和只剩第一项，于是 V = r = (1, 0, 0, 0, 0, 0, 10)。s₂…s₆ 全是 0 —— 从它们出发确实能走到 +10，但完全短视的智能体看不见。先建立一个基准。

讲解

看什么：看柱子出现的顺序：必须从最右边 s₇ 开始、一个一个往左冒出来，而不是一起出现。看到「从右往左依次」，就等于看见了回代顺序——每个 V(sᵢ) 都依赖 V(sᵢ₊₁)，所以右边那个不算完，左边这个根本无从下手。　—— 先取最极端的 γ=0 当基准。折扣和只剩第一项，于是值就等于当前状态的即时奖励，得到 (1,0,0,0,0,0,10)——这也是讲座里唯一给出的一帧。值得停一下的是中间那五个 0：从 s₂ 到 s₆ 出发明明都能走到 +10，可完全短视的智能体对此视而不见。柱子是按回代顺序从右往左一个个出现的，因为每个值都要等它右边那个算完。

72 / 87

γ : 0.72 \to 0.82

同一个 MDP、同一个策略、同一套 r(s) —— 只有 γ 变了。只画论证涉及的三个状态（s₄…s₇ 与这个论断无关）。γ*≈0.7737 就落在这个窗口内，所以翻转发生在推进过程中。

讲解

看什么：盯住最左两根谁更高：起始 V(s₁)=2.69 明显高于 V(s₂)=2.01，推完之后必须反过来——V(s₁)=7.95 低于 V(s₂)=9.00。看到「两根交换了高低」，就等于看见了 γ 能重排状态的好坏；如果三根只是一起长高而次序不变，那么开头那个「等比缩放」的模型就是对的。　—— 把 γ 从 0.72 推到 0.82。这个窗口是特意选的：临界值 γ*≈0.7737 落在里面，所以翻转会在推进过程中当场发生；而且两端的柱高都在可读范围内，不会出现「论证的前提只有几个像素高」这种情况。只画 s₁、s₂、s₃ 三根，因为这个论断只关于它们——s₄ 到 s₇ 与它无关，画上去只会挤占注意力。起始时 s₁ 比 s₂ 高 0.683，结束时 s₂ 比 s₁ 高 1.052。

73 / 87

把 γ 连续扫过去：两条曲线相交于 V(s₁)=V(s₂)=4.419，交点就是决策易主的临界折扣。左侧守着 +1 更划算，右侧奔向 +10 更划算。

讲解

把刚才那一段放进全局来看。V(s₁) 与 V(s₂) 作为 γ 的函数是两条曲线，它们在 γ*≈0.7737 处相交，交点值 4.419（把递推式解出来后二分求得）。交点左边守着 +1 更划算，右边奔向 +10 更划算。讲座只展示了 γ=0 那一帧，然后口头承诺「下次再看更多」——但整个道理恰恰在这条交叉上：γ 是决定近处小奖与远处大奖谁说了算的旋钮，而且这个转换点是精确的、可以算出来的。

74 / 87

V^{π} (s) = \sum_{k \geq 0} γ^{k} E [r_{t + k}]

所以错的不是「γ 影响远期」，而是~~把它当成一个整体比例因子~~。

讲解

现在指名回去。开头那个模型说 γ 只改变尺度、不改变排序，理由是「奖励结构没变」。奖励结构确实没变——但折扣不是乘一个常数，而是给第 k 项乘 γ^k，**而 k 是到奖励的距离，它因状态而异**。s₁ 离 +10 有六步，s₂ 只有五步，两者被压缩的倍数根本不同，所以这不是等比缩放，次序当然可以翻转。那个「等比缩放不改变次序」的直觉本身是对的，用错了地方：折扣不是等比缩放。结论是 γ 属于**问题设定**，和 R_max、时域放在一起，而不是求解器的调参项——写论文报数字时，改 γ 等于换了一个问题，不是换了一组超参。　回到那句「γ 只是尺度，不改变排序」　关键在指数上那个 k —— 它是到奖励的距离　离奖励越远，压得越狠 —— 于是次序可以翻转　s₁ 离 +10 有六步（γ⁶），s₂ 只有五步（γ⁵）—— 它们受到的压缩根本不同

75 / 87

知识点 8 · 总结

γ 是问题定义的一部分，不是超参数

核心结论

同一 MDP、同一策略、同一套 r(s)：γ=0.72 时 V(s₁)>V(s₂)，γ=0.82 时反过来，临界 γ*≈0.7737。

底层机制

γ^k 的指数 k 是到奖励的距离，因状态而异 —— 所以折扣不是整体比例因子，可以重排好坏。

常见误解

误解：「奖励没改所以排序不变」。这个直觉本身没错，只是折扣不是等比缩放。

与你的考试

求解顺序：V(s₇)=10/(1−γ) 先出，再从右往左回代 —— 这就是动态规划的扫描方向。

76 / 87

知识点 8 · 检验

把本例的 γ 从 0.72 提到 0.82，会发生什么？

知识点 10

9 · 三组分野与有限时域的非平稳性

77 / 87

同一个状态、同样的信息、同一套动作。在完全相同的状态里，最优动作会因为「今天是最后一天」而改变吗？

讲解

这是全讲里唯一一处只用嘴讲、slides 上完全没有的实质性论断。它出现在一个学生追问之后：「如果我只在这城里待五天，算出来的策略和永远住下去一样吗？」Brunskill 的回答是 very different。为什么值得为它单开一集：你做的 workflow 是有限时域的——节点数有限、预算有限。如果这个论断成立，那么一个只看 query 特征、不看还剩几个节点的路由策略，就不是~~调得不够好~~，而是结构性写错了。

78 / 87

π : S \to A, π (s) = a

策略的定义式里本来就没有时间 —— π: S→A，定义域 = S，「学到最优策略」就是把这一行填对。表是有限的、存得下、查得快、梯度也好回传。

讲解

这个模型不是外行的错，它是 slides 第 60 页的定义直接读出来的：π: S→A，从状态映到动作，定义域里既没有 t，也没有「还剩几步」。整个监督学习的直觉都站在它这一边——策略就是一个函数，学习就是把这个函数拟合对。它还有非常实际的好处：表是有限的，存得下、查得快、梯度也好回传。真正微妙的地方是，这张表连「同一个状态在不同时刻可能不同」这句话都无法表达，因为它没有那个格子。

79 / 87

三组分野是整门课的骨架：规划 vs 学习（有没有模型 · L2）· 探索 vs 利用（要不要为信息付代价 · L11–13）· 评估 vs 控制（给定 π 求 V^π / 求最优 π · L3–4、L15）。本集只钻第二条，自变量是 k = 剩余决策步数（steps-to-go，不是绝对时刻 t）。

讲解

三组分野是课程后续的骨架：规划 vs 学习——有没有模型，L2 讲有模型怎么算；探索 vs 利用——要不要为信息付代价，L11–13；评估 vs 控制——给定 π 求 V^π，还是求最优 π，L3–4 与 L15。本集只钻第二条，但结论会反过来改写另外两条。整集只有一个自变量：k，剩余决策步数。【记号】k 是 steps-to-go，不是绝对时刻 t，二者由 k = H − t 换算；Sutton&Barto 的有限时域章节多用 t，且奖励下标比 Brunskill 晚一格。

80 / 87

你在城里待 H 夜，每夜在确定的 A 与未知的 B 之间选一个。状态 s0 =「B 还没试过」· γ = 1。B 的期望 4，尝一次即永久已知；c = 5 − 4 = 1，期权价值 λ = E[max(5,B)] − 5 = 6.5 − 5 = 1.5，信息价值 VOI(k) = λ(k−1)。

讲解

这是课上「只在城里待五天、有五家菜可点」那个例子，收紧成两个动作、给定数字，好让每一笔账都对得上。设定的关键不是 B 的期望更低，而是B 的不确定性一次就能消掉——尝一次，好坏永久已知，于是探索的收益能写成封闭式。6.5 是 E[max(5,B)] = 0.5×8 + 0.5×5：知道 B 之后你每夜都能挑更好的那个。【补课】严格说 s0 是一个信念状态，这问题是 Bayes-adaptive MDP；课上跳过了 POMDP 的信念状态归约，这里正好是它最小的实例。

81 / 87

Δ (k) = - c + λ (k - 1) \Rightarrow Δ (1) = - 1 + 1.5 \times 0 = - 1

Δ(k) ≡ 探索账 − 利用账。最后一夜：今夜之后不再有任何决策 ⇒ 学到的东西无处可用 ⇒ VOI(1) = 0，探索的收益项被 (k−1) = 0 乘掉，账面上只剩下~~探测代价~~。

讲解

把最后一夜的两笔账摆开：利用 A 得 5；试探 B 今夜期望 4，而此后没有任何一夜能用上学到的东西，Δ(1) = −c + λ·0 = −1，严格为负。【补课】课上说这件事「显然」，一般形式的证明也只有一行：k=1 时 Bayes 最优动作是最大化后验期望的即时奖励 max_a E_b[r(s,a)]，观测到什么都不再改变任何决策，所以信息价值恰好是 0，不是「很小」。注意它不等于「最后一夜要选试过的那个」——那是两件事。

82 / 87

把剩余步数 k 从 1 扫到 5：VOI(k) = 1.5(k−1) 递减，而~~探测代价 c = 1~~ 不动。VOI 只在最右这一格低于 c ⇒ 最优动作（前四格探索、最后一格利用）只在这一格翻转。

讲解

看什么：看柱子从最右边那一格（剩 1 夜）开始向左依次出现——这就是后向归纳的方向；最右那根高度是 0、落在珊瑚线以下，而从右数第二根起全都高过珊瑚线，所以翻转点只可能在这两格之间。　—— λ 的含义是「知道 B 之后每夜多赚的期望」，本质上是一个期权的价值：0.5×(8−5) + 0.5×0 = 1.5。它必须乘上还能用上它的夜数 k−1，于是 VOI(k) = 1.5(k−1)，取 6 / 4.5 / 3 / 1.5 / 0；探测代价 c = 5 − 4 = 1 不随 k 变化。一条线性递减的量穿过一条水平线，代数上的穿越点是 k = 5/3；因为 k 只取整数，翻转就恰好落在 k=2 与 k=1 之间。填充方向不是随手挑的：每一格都要等它右边那格算完才有值可依。

83 / 87

V_{k}^{*} (s) = max_{a} [r (s, a) + γ \sum_{s^{'}} p (s^{'} | s, a) V_{k - 1}^{*} (s^{'})], V_{0}^{*} \equiv 0

一般形式是后向归纳：公式里的 k 就是上面这五格的「剩几夜」，每一格只依赖它右边那一格。k=1 这一层里 V*₀ ≡ 0 抹掉第二项、只剩即时奖励 —— 这就是「最后一步探索价值为零」的一般形式。π*_k(s) = 取到 max 的那个 a：一层一张表，共 H 张，不是一张表。

讲解

一般形式就是有限时域 Bellman 递推，课上只说了「非平稳」和「后向归纳」，没写出式子【补课】。看两件事：k 出现在等式两边，所以解出来的是 H 张表而不是一张；k=1 时括号里的第二项因 V*₀≡0 而消失，只剩即时奖励——「最后一步纯利用」于是成了递推的边界条件，不是额外的直觉。再澄清一点：非平稳性与学习无关。把 +10 放在 5 步之外、+1 放在 1 步之外，模型完全已知、什么都不用学，剩 1 步时最优往 +1、剩 5 步时最优往 +10，动作照样翻转。第一组分野在这里显形：规划里就已经有非平稳性，学习只是在它上面再叠一层探索。

84 / 87

同一个状态 s0、同样的信息，唯一的差别是剩余步数。~~「最优策略就是每个状态一个固定动作」~~在最后一步断掉：π* 的定义域是 S × {1,…,H}，不是 S，被漏掉的自变量就是 k。同一漏洞的第二副面孔：覆盖条件里的「状态」也是 (s,k)。

讲解

点名：那个「最优策略就是每个状态一个固定动作」的模型，断在最后一步。同一个 s0，k≥2 时最优是探索、k=1 时最优是利用；两者必须不同，而一张 S→A 的表没有地方安放这个差别——π* 的定义域是 S×{1,…,H}。【补课】同一个漏洞的第二副面孔：离策略评估的覆盖条件常被记成「每个状态都试过每个动作」，可有限时域下这里的状态是 (s,k)；你在 s 上采了海量数据，但若行为策略从未在「剩 1 步」时到达 s，π_e 在那一格就不可识别，加数据也没用。

85 / 87

知识点 9 · 总结

三组分野

核心结论

规划 vs 学习（有无模型）· 探索 vs 利用（要不要为信息付代价）· 评估 vs 控制。

底层机制

有限时域最后一步探索价值为零 ⇒ 最优策略非平稳，须后向归纳；无穷时域折扣则存在最优平稳策略。

常见误解

误解：以为离策略评估「数据够多就行」。真前提是覆盖条件；不满足时估计量无定义。

与你的考试

这三组分野就是后续骨架：L2 规划 · L3–4 评估与控制 · L11–13 探索 · L15 离策略评估。

86 / 87

知识点 9 · 检验

把菜 B 改成等概率 8 或 4（期望 6），菜 A 仍是确定的 5，其余全部不变。最后一夜（k=1）的最优动作是什么？

知识点 11

完

87 / 87

讲解

回头看这九集，每一集都是同一个形状：先抛出一个具体问题，再说出一个你很可能真的持有过的错误模型，然后用一个带真实数字的实例把它撞碎，最后指名回去宣告它错在哪里。如果你读完只记住一件事，记住那九个错误模型 —— 它们比九条正确结论更难得，因为正确结论到处都能查到，而「你原本以为的那样为什么不成立」通常没人写出来。L2 开始就有真正要证的定理了。

CS234 L1 · 强化学习导论 · 全片速览

开场

1 · 三个承重词：序贯 · 好 · 学

三个承重词，与那条真正的分界线

2 · 四要素坐标系

四要素里最贵的是探索，而它看起来最便宜

3 · 用四盏灯划清边界

相邻范式 = RL 减去某几盏灯

4 · 交互回路、历史、智能体状态

回路 → 历史 → 智能体状态：S 是设计出来的

5 · Markov 条件 = 充分统计量

Markov 性是表示的性质，不是世界的性质

6 · MDP / POMDP / 赌博机

三分法与它的两条判据

7 · 三大部件与折扣和的收敛性

三大部件 + 值函数的良定性

8 · Mars rover：γ 是问题定义的一部分

γ 是问题定义的一部分，不是超参数

9 · 三组分野与有限时域的非平稳性

三组分野

完