CS234 L4 · 无模型控制 · 放映厅

1 / 71

讲解

L3 回答的是评估：给定一个策略，没有模型时怎么估它的值。L4 要把回路闭上——怎么把策略改好，而且仍然不许建模型。组织方式是广义策略迭代，把模型从里面摘掉。整讲的全部工作由两次换位完成：第一，评估 Q 而不是 V；第二，把贪心换成 ε-greedy。这一讲真正在板上证明的只有一条定理——ε-greedy 的策略改进仍然单调——其余的收敛性都是断言。本片仍按六拍走：第二拍同情地说出一个貌似合理的错误模型，第五拍回去指名杀掉它。另外这一讲的自动字幕坏得比前几讲厉害，有几处会让推导读不通（比如把更新式渲染成 `Q + (1−α)r + …`，那是数学上不可能的形态）。本片凡是遇到这类地方都会标出来，并以板上写的式子为准。

2 / 71

π^{'} (s) = \arg max_{a} [R (s, a) + γ \sum_{s^{'}} P (s^{'} ∣ s, a) V (s^{'})]

L2 里从 V 贪心是理所当然的。但它要穿过一次 Bellman 回溯 —— 而模型已经没有了。

讲解

L2 的策略迭代里，改进那一步写的是：对每个状态，取那个使「即时奖励加折扣后继值」最大的动作。当时这么写毫无问题，因为 P 和 R 就摆在手上。现在把模型拿走，这一行立刻失效。式子里有两个模型量：R(s,a) 和 P(s′|s,a)。没有它们，你算不出括号里的东西，因此也取不了 argmax。换句话说：无模型控制卡住的地方不是评估，是改进。L3 已经给了三种无模型的评估办法，但那些办法估的是 V，而拿 V 去改进策略，仍然要穿过这一次回溯。

3 / 71

估 V 就够了反正贪心一下就能得到策略

这个直觉在 L2 完全成立 —— 那时 P 和 R 都在手上。

讲解

这个错误模型值得同情，因为它在 L2 里是对的，而且我们刚刚用了一整讲去建立它：值函数是核心对象，策略是从值函数读出来的副产品。而且它在 L3 里也没被挑战过——L3 通篇在估 V^π，从头到尾没有提过 Q。问题出在「读出来」这三个字。在有模型的世界里，从 V 读出策略是一次查表加一次求和；在无模型的世界里，那次求和是做不出来的。

4 / 71

π^{'} (s) = \arg max_{a} Q (s, a)

换成 Q：贪心改进变成一次查表取最大，模型整个消失了。

讲解

解法是换一个被估的对象：不估 V，估 Q。从 Q 贪心只需要 argmax_a Q(s,a)——在一行里把所有动作比一遍，取最大的那个。没有求和，没有 P，没有 R。这就是无模型控制的第一次换位，而它便宜得有点不像话：你什么新算法都没发明，只是把被估的函数从 V 换成了 Q，改进那一步的模型依赖就整个消失了。原因也不神秘——Q 本来就把「第一步取哪个动作」这件事预先算进去了，而那正是 V 缺的、需要靠模型临时补出来的那部分信息。

5 / 71

Q^{π} (s, a) = E_{π} [G_{t} ∣ s_{t} = s, a_{t} = a]

Q 比 V 多记一件事：第一步的动作由你指定，从第二步起才交给 π。

讲解

把 Q 的定义摊开看：从状态 s 出发，第一步强制取动作 a，之后才按策略 π 走，回报的期望就是 Q^π(s,a)。 V^π(s) 则是从第一步起就按 π 走。所以两者差的正是「第一步的动作由谁决定」这一件事。这解释了为什么换成 Q 就不需要模型了：V 要靠 P 和 R 临时算出「如果第一步改走 a 会怎样」，而 Q 把这件事预先存下来了。模型依赖没有消失，它被搬进了表里，而那张表可以直接从数据估。

6 / 71

代价只是把表撑大 |A| 倍。火星车上：7 个数变 14 个数，换掉整个模型。

讲解

看什么：看第二根比第一根高出多少：那一截就是 Q 表多存的 7 个数。它只有一倍，而换掉的是整个模型。　—— 代价是存储：V 表有 |S| 个数，Q 表有 |S||A| 个数。火星车是 7 个状态、2 个动作，所以从 7 个数变成 14 个数。多存 7 个数，换掉整个模型——这个交易在表格世界里划算得没有悬念。但请记住这个比例是 |A| 倍，不是常数倍。动作空间一大它就不划算了；而动作连续时 argmax 本身都不再是一次查表。这正是后面几讲要处理的问题，也是策略梯度那一类方法存在的理由之一。

7 / 71

指名反驳：V 不是精度不够，是贪心那一步本身需要模型。

讲解

指名回去：「估 V 就够了」错在哪儿——不是 V 估得不准，而是从 V 到策略的那一步本身需要模型。这是一个结构性的障碍，再多数据也绕不过去。把账记清楚。从 V 贪心：要 P 和 R。从 Q 贪心：只要查表。代价：表大 |A| 倍。这是无模型控制的第一次换位。下一集是第二次：即使有了 Q，确定性的贪心策略仍然学不到东西——而那个问题比这一个更麻烦。

8 / 71

知识点 1 · 总结

控制要用 Q，不是因为 Q 更准，是因为从 V 贪心要穿过模型

核心结论

从 V 改进：argmax_a[R(s,a)+γΣP(s′|s,a)V(s′)]，式子里有两个模型量；从 Q 改进：argmax_a Q(s,a)，一次查表。

底层机制

Q 把「第一步取哪个动作」预先存进了表里 —— 那正是 V 缺的、要靠模型临时补出来的信息。

常见误解

误解：「估 V 就够了，贪心一下就有策略」。在 L2 成立（模型在手），在无模型世界不成立。

与你的考试

代价是 |A| 倍存储（火星车 7→14 个数），不是常数倍；动作空间大或连续时这笔交易就不划算了。

9 / 71

知识点 1 · 检验

无模型控制为什么必须估 Q 而不是 V？

10 / 71

确定性贪心策略跑一万个回合，向左那个动作一次都没被试过。

讲解

有了 Q 之后，最自然的做法是对 Q 贪心：每个状态取当前 Q 最大的那个动作。但这里有一个致命的循环。策略是确定性的，所以在每个状态上它永远只会采到那一个动作。跑一个回合是这样，跑一万个回合还是这样。于是另一个动作的 Q 值永远拿不到任何数据——它会一直停在你给的初值上。而下一轮的贪心又要拿这个没更新过的 Q 去比较。

11 / 71

按当前最优走反正 Q 会慢慢收敛到对的

这句话在有模型的策略迭代里是对的 —— L2 的策略迭代正是这么做的。

讲解

这个错误模型有一个很硬的来源：L2 的策略迭代就是这么做的，而且它被证明收敛到全局最优。所以「一直按当前最优走」看上去是一条已经被验证过的路。差别在于 L2 的策略评估是对所有 (s,a) 全算一遍的——有模型的时候，你不需要真的走过某个动作就能知道它的值。无模型时这个前提没了。你只能从走过的转移里学，而确定性策略保证了你永远不会走那些当前看起来不好的动作。

12 / 71

Q (s, a) \leftarrow Q (s, a) + α [target - Q (s, a)]

更新只发生在被采样到的 (s,a) 上。没走过的动作，Q 永远停在初值。

讲解

把更新式摊开：Q(s,a) 只在这个 (s,a) 对被实际采样到时才被改写一次。没被采到，它一个字节都不会动。这不是某个算法的缺陷，是无模型这件事本身的定义——数据只能来自你真的走过的地方。顺带说明一处字幕坏损：本讲的自动字幕反复把这条更新式渲染成 `Q + (1−α)r + …`，那是数学上不可能的形态。合法的写法只有两种，`Q ← Q + α[目标 − Q]` 与 `Q ← (1−α)Q + α·目标`，两者等价。她在课上明确请学生帮她抓板书笔误，本片一律以板上的式子为准。

13 / 71

Q 表 14 个格子，确定性贪心只会碰到 7 个。另外 7 个是盲区。

讲解

把它量出来。火星车的 Q 表有 7×2 = 14 个格子。确定性策略在每个状态上只指定一个动作，所以只有 7 个格子会收到数据，另外 7 个从头到尾是盲区。注意这不是「那 7 个格子估得差一点」，是它们一个样本都没有。而危险在于贪心又是拿整张表去比较的。如果初值恰好把某个坏动作设得偏高，策略就会一直选它，于是好动作永远得不到数据来翻案——错误的初值会把自己锁死。

14 / 71

指名反驳：不是收敛慢，是那半张表根本没有数据。

讲解

指名回去：问题不是「收敛得慢」，而是那半张表根本没有数据。没有数据就不存在收敛这回事。三步锁死的链条是：确定性贪心 ⟹ 每个状态只采一个动作 ⟹ 另一半 Q 永远停在初值 ⟹ 而贪心又基于这张表，于是坏初值把自己锁死。所以探索不是工程细节，是收敛的前提。这是无模型控制的第二次换位：把贪心换成 ε-greedy。下一集会看到，这个换位本身还藏着一个连讲座都说错过好几次的细节。

15 / 71

知识点 2 · 总结

确定性贪心策略学不到它没试过的动作

核心结论

火星车 Q 表 14 格，确定性贪心只碰得到 7 格；另外 7 格一个样本都没有，永远停在初值。

底层机制

无模型意味着数据只能来自走过的地方。确定性策略保证了你永远不走当前看起来差的动作。

常见误解

误解：「按当前最优走，Q 会慢慢收敛」。在 L2 成立，因为有模型时不必走过就能算出动作的值。

与你的考试

真正的危险是自我锁死：坏的初值让策略一直避开好动作，好动作因而永远拿不到翻案的数据。

16 / 71

知识点 2 · 检验

对 Q 做确定性贪心，在无模型设定下的根本问题是什么？

17 / 71

ε-greedy 的定义只有一句话。问题在「随机」那一支到底包不包括贪心动作。

讲解

ε-greedy 的想法一句话就说完：以 ε 的概率随机选一个动作，否则选贪心动作。这样每个动作都有正概率被采到，上一集那个「一半的表是盲区」的问题就解决了。但把它写成精确的概率分布时，有一个地方特别容易写错，而且讲座里写错了不止一次。问题是：那个「随机」分支，是在所有动作里均匀抽，还是在非贪心动作里均匀抽？

18 / 71

P(贪心) = 1 − ε幻灯片和口述里好几处就是这么写的

这个写法在讲座里出现了不止一次 —— 而且它把概率加不到 1。

讲解

最顺手的写法是：贪心动作概率 1−ε，其余每个动作概率 ε/|A|。讲座的幻灯片和口述里好几处就是这么写的。它错在哪里，一算就知道。|A|=2、ε=0.1 时：0.9 + 0.05 = 0.95，加不到 1。少掉的那 0.05 正好是「随机分支恰好抽中贪心动作」的那一份。这个细节在课上被两个学生先后提出，才被说清楚。它值得单独占一集，因为它不是笔误——写错的人心里的模型是「随机分支只在其他动作里抽」，而标准定义不是那样。

19 / 71

π (a^{*} ∣ s) = (1 - ε) + \frac{ε}{| A |}

随机分支是在所有动作里均匀抽，贪心动作也在里面 —— 那一份要加回去。

讲解

标准定义是：先掷一枚偏心硬币，以 1−ε 的概率直接走贪心动作；以 ε 的概率进入随机分支，而随机分支是在全部 |A| 个动作里均匀抽——贪心动作也在其中。所以贪心动作的总概率是两条路径之和：(1−ε) + ε/|A|。非贪心动作各自是 ε/|A|。验算：(1−ε) + ε/|A| + (|A|−1)·ε/|A| = 1−ε+ε = 1。这次加得上了。

20 / 71

ε=0.1、|A|=2：真实的贪心概率是 0.950，不是 0.900。

讲解

看什么：看第二根比第一根高出的那一小截：那就是被漏掉的 ε/|A|。它不大，但它是让概率加到 1 的那一份。　—— 代进常用的一组数：ε=0.1、|A|=2。错误写法给 0.900，正确值是 0.950。差了 0.05，看起来不大。但请注意它偏的方向：真实的策略比你以为的更贪心。如果你按 0.9 去做理论分析或者估探索量，会系统性地高估探索、低估利用。在推导里这个差更要命：ε-greedy 改进定理的代数正是围绕这些权重展开的，权重写错定理就推不出来。

21 / 71

ε=0.5 时差得离谱：真实值 0.750，错写成 0.500 —— 相对误差 50%。

讲解

看什么：还是看高出的那一截 —— 这次它占了整根柱子的三分之一。ε 越大、动作越少，漏掉的那一份就越显眼。　—— 把 ε 推大，错误就藏不住了。ε=0.5、|A|=2 时，错误写法给 0.500，正确值是 0.750——相对误差 50%。直觉上也对得上：ε=0.5、两个动作时，你有一半概率直接走贪心，另一半概率里又有一半抽中贪心，合计四分之三。再看一组：ε=0.2、|A|=5 时正确值是 0.840 而不是 0.800。差值 ε/|A| 随动作数增多而缩小——所以动作越少，这个错误越严重，而教学例子恰恰都是两个动作的。

22 / 71

指名反驳：随机分支包含贪心动作。两个学生先后提出，才被说清楚。

讲解

指名回去：随机分支是在所有动作里抽，贪心动作也在里面。差的就是 ε/|A| 那一份。判别办法永远是同一个，而且不需要记公式：把所有动作的概率加起来，看是不是 1。加不到 1 就说明漏了一支。这一集之所以值得单独占一格，是因为下一集的 ε-greedy 改进定理整个建立在这些权重上——它的代数核心是把 max_a Q 写成权重为 (π(a|s) − ε/|A|)/(1−ε) 的凸组合的上界。那个 −ε/|A| 正是这里加回去的那一份。权重写错，定理就推不出来。

23 / 71

知识点 3 · 总结

ε-greedy 的贪心概率是 1−ε+ε/|A|，不是 1−ε

核心结论

随机分支在全部 |A| 个动作里均匀抽，贪心动作也在其中。实测：ε=0.1,|A|=2 → 0.950；ε=0.5,|A|=2 → 0.750（不是 0.500）。

底层机制

判别不用记公式：把所有动作的概率加起来看是不是 1。0.9+0.05=0.95，加不到 1 就说明漏了一支。

常见误解

误解：「贪心概率 = 1−ε」。讲座幻灯片与口述多处如此，课上两个学生先后提出才说清。

与你的考试

动作越少这个错越严重（差值是 ε/|A|），而教学例子恰恰都是两个动作；下一集的改进定理正建立在这些权重上。

24 / 71

知识点 3 · 检验

ε = 0.5、|A| = 2 的 ε-greedy 策略，贪心动作被选中的概率是多少？

25 / 71

π_{i + 1} = ε -greedy (Q^{π_{i}})

L2 的策略改进定理要求贪心。现在贪心被换掉了 —— 改进还成立吗？

讲解

L2 的策略改进定理证明的是：对 Q^π 取 argmax 得到的新策略不劣于旧策略。那条证明的每一步都用到了「新策略在每个状态取最大的那个动作」。现在为了探索，我们把 argmax 换成了 ε-greedy。新策略有 ε 的概率故意去走一个当前看起来更差的动作。那条定理的前提被破坏了。所以必须重新问一遍：这样改出来的策略，还保证不劣于旧的吗？这是本讲唯一一条真正在板上证明了的定理。

26 / 71

随机化会拖累改进毕竟有 ε 的概率在做蠢事

这个担心很具体：新策略确实有 ε 的概率去走更差的动作。

讲解

这个错误模型比大多数都更有说服力，因为它的前半段是事实：ε-greedy 策略确实会以 ε 的概率走一个 Q 值更低的动作。那不是错觉，是设计。由此推出「所以整体可能变差」几乎是自动的。而且直觉上还有一个佐证：上一集刚说过，固定的 ε 会让你跟随的策略永远达不到最优。两件事必须分开。「ε-greedy 的策略不是最优的」是真的；「ε-greedy 的改进步骤不再单调」是假的。下面证明后者。

27 / 71

Q^{π} (s, π^{'} (s)) = \frac{ε}{| A |} \sum_{a} Q^{π} (s, a) + (1 - ε) max_{a} Q^{π} (s, a)

先把新策略下的 Q 拆成两支：随机那一支求平均，贪心那一支取最大。

讲解

要证的是 Q^π(s, π′(s)) ≥ V^π(s)——新策略在旧的 Q 下至少不比旧策略差。有了这一条，L2 的策略改进定理就能原样接上，给出 V^{π′} ≥ V^π。第一步是把新策略按它的两支拆开。随机那一支以 ε 的概率进入，在所有动作里均匀抽，所以贡献的是 Q 的平均值乘 ε；贪心那一支以 1−ε 的概率进入，贡献的是 Q 的最大值乘 (1−ε)。难点全在第二项：怎么把那个 max 换成和旧策略 π 有关的东西。她把这一步称作这段推导里唯一的「窍门」。

28 / 71

max_{a} Q^{π} (s, a) \geq \sum_{a} \frac{π (a ∣ s) - ε / | A |}{1 - ε} Q^{π} (s, a)

窍门：最大值不小于任何一个凸组合。关键是证出这组权重确实是凸组合。

讲解

窍门是一条几乎显然的不等式：一组数的最大值，不小于它们的任何一个凸组合。凸组合的意思是权重非负、加起来等于 1。所以只要能构造出一组这样的权重，就能把 max 往下放成一个求和式——而求和式里可以带上旧策略 π。她选的权重是 (π(a|s) − ε/|A|) / (1 − ε)。这个权重不是凭空来的：它正好是「把 π 里属于随机分支的那一份 ε/|A| 剥掉，剩下的重新归一化」。下一镜验证它确实是凸组合——这一步必须验，否则整个不等式不成立。

29 / 71

\sum_{a} (π (a ∣ s) - \frac{ε}{| A |}) = 1 - ε ⟹ \sum_{a} w_{a} = 1

两条都成立：ε-greedy 保证每个动作的概率都 ≥ ε/|A|，所以权重非负。

讲解

验两条。非负：权重的分子是 π(a|s) − ε/|A|。而 π 本身是 ε-greedy 的，所以每个动作的概率至少是 ε/|A|（那正是上一集算出来的那一份）。分子非负，分母 1−ε 为正，权重非负。 和为 1：Σ_a π(a|s) = 1，Σ_a ε/|A| = ε，所以分子加起来是 1−ε；除以 1−ε 正好是 1。两条都成立，所以那确实是一个凸组合，不等式成立。注意这里用到了上一集那个被写错过的概率——如果按「贪心概率 = 1−ε」来算，非贪心动作的概率就不是 ε/|A|，权重的非负性就没有保证。那个细节在这里变成了承重的。

30 / 71

Q^{π} (s, π^{'} (s)) \geq \sum_{a} π (a ∣ s) Q^{π} (s, a) = V^{π} (s)

代回去，ε/|A| 的两项正好抵消，剩下的恰好是 V^π(s)。改进成立。

讲解

把不等式代回两支的和，剩下的是纯代数。(1−ε) 乘上权重里的 1/(1−ε) 约掉，展开后得到 Σ_a π(a|s)Q^π(s,a) 减去 (ε/|A|)Σ_a Q^π(s,a)；而前面随机那一支恰好贡献了 +(ε/|A|)Σ_a Q^π(s,a)，两项精确抵消。剩下的正是 Σ_a π(a|s)Q^π(s,a)，也就是 V^π(s)。于是 Q^π(s, π′(s)) ≥ V^π(s) 对每个状态成立。接上 L2 的策略改进定理——那条定理只要求这个不等式，不要求 π′ 是贪心的——就得到 V^{π′} ≥ V^π。单调改进保住了。

31 / 71

指名反驳：改进不受随机化影响。但这条证明有两个没被点名的前提。

讲解

指名回去：随机化不破坏单调改进。「有 ε 概率走差动作」是真的，但它被随机那一支的平均项精确补偿掉了——这正是那两项抵消的含义。但这条证明有两个前提没有被点名，而它们都不是小事。第一，Q^{π_i} 必须是精确的。定理比较的是真实的 Q^π，而算法手里只有一个估计。估计有误差时，argmax 可能选错动作，单调性就不再保证——这也是为什么后面所有的收敛性都只能写成「在 GLIE 加上合适步长之下渐近成立」。第二，证明是对固定的 ε 做的，而算法里 ε 随 k 衰减。变动的 ε 意味着每一轮比较的是不同的策略类，这条证明没有覆盖那种情形，而讲座没有标出这个缺口。下一集讲的 GLIE 正是在衰减 ε，所以这个缺口就在紧接着的那一页上。

32 / 71

知识点 4 · 总结

ε-greedy 的策略改进仍然单调 —— 随机化被平均项精确补偿

核心结论

拆两支后，窍门是 max ≥ 任何凸组合，取权重 w_a=(π(a|s)−ε/|A|)/(1−ε)；代回去 ε/|A| 两项精确抵消，剩下 V^π(s)。

底层机制

权重是凸组合的两条依据：ε-greedy 保证 π(a|s) ≥ ε/|A|（非负）；Σ 分子 = 1−ε（和为 1）。

常见误解

误解：「有 ε 概率走差动作，所以整体会变差」。前半句是事实，后半句被平均项抵消掉了。

与你的考试

两个没被点名的前提：Q^π 必须精确（算法只有估计）；证明是对固定 ε 做的（而算法在衰减 ε）。

33 / 71

知识点 4 · 检验

ε-greedy 改进定理的证明里，权重 (π(a|s) − ε/|A|)/(1−ε) 为什么非负？

34 / 71

ε 看起来像个超参数 —— 调一个值就完事。它不是。

讲解

上一集证明了 ε-greedy 的改进是单调的，于是一个很实际的问题浮上来：ε 到底取多少？直觉上这像个超参数——大了探索多学得全，小了利用多回报高，调一个折中值就行。但这一集会看到，ε 的取法不是调参，是收敛性的前提。固定任何一个正的 ε，你跟随的策略都永远达不到最优；而衰减得太快，又可能永远探索不够。

35 / 71

ε 是个超参数取个 0.1 之类的折中值就好

固定 ε 在实践里到处都是 —— 而它保证了你拿不到最优策略。

讲解

把 ε 当超参数固定住，是实践里最常见的做法：取 0.1，跑完，收工。这个做法不是没有道理——它简单，而且在只关心「学到一个还不错的策略」时够用了。但它有一个确定性的代价，而且这个代价不随训练时间减小：只要 ε 固定为正，你跟随的那个策略就永远带着 ε 的随机性，因此永远不是最优的。下面把这个代价量出来。

36 / 71

GLIE = Greedy in the Limit with Infinite Exploration。两条同时要。

讲解

正确的条件叫 GLIE：Greedy in the Limit with Infinite Exploration。两条：第一，无限探索——每一个 (s, a) 对都被访问无穷多次。这一条保证每个格子都有数据，是第二集那个「盲区」问题的直接解药。第二，渐近贪心——策略最终要收敛到贪心策略。这一条保证你最后跟随的是最优策略，而不是一个带噪声的版本。顺带一提：自动字幕把 GLIE 渲染成了「greedy in the limit of infinity exploration」和「greedy in the limit of information」两种形态，都是同一个词的坏损。

37 / 71

火星车实测：固定 ε 的策略永远比最优差这么多，训练多久都不变。

讲解

看什么：看三根柱子一根比一根高多少：ε 每加大一档，代价就往上跳一截。这个高度不随训练时间下降 —— 它是策略本身的损失。　—— 在火星车上把这个代价算出来。对每个固定的 ε，计算 ε-greedy 策略（对最优动作贪心）的真实值函数，和最优值函数比。 ε=0.1 时最大差距 5.082；ε=0.3 时 15.976；ε=0.5 时 27.573。作为参照，V*(s₇)=100。关键不是数字大小，是这个差距不随训练时间减小。哪怕 Q 已经精确收敛到 Q*，只要你还按固定 ε 行动，这个损失就一直在。它不是估计误差，是策略本身的结构性损失。这就是为什么「渐近贪心」必须是条件之一。

38 / 71

ε_{k} = \frac{1}{k} : \sum_{k} ε_{k} = \infty and ε_{k} \to 0

ε_k = 1/k 同时满足两条：调和级数发散（无限探索），且 1/k → 0（渐近贪心）。

讲解

看什么：看柱子有没有停下来：K 每涨十倍，Σ1/k 只多涨两点多，但它一直在涨。慢，却永远不停 —— 这正是「无限探索」要的。　—— 最简单的满足 GLIE 的取法是 ε_k = 1/k。它同时满足两条，而且理由分别是两个不同的性质。 无限探索来自调和级数发散：Σ 1/k 在 K=10 时是 2.929，K=100 时 5.187，K=10⁴ 时 9.788——涨得很慢，但永远不停。探索的总量是无穷，所以每个 (s,a) 会被访问无穷多次。 渐近贪心来自 1/k → 0：K=10⁴ 时 ε 已经是 10⁻⁴，策略实质上就是贪心的。柱子涨得慢正是它的巧妙之处：它衰减得刚好够慢，慢到探索总量仍然发散。

39 / 71

指名反驳：ε 不是超参数，是收敛条件。衰减太慢太快都不行。

讲解

指名回去：ε 不是超参数，它是收敛条件的一部分，而且两个条件方向相反，所以衰减快慢是一个真正的两难。 衰减太慢（比如根本不衰减）：探索足够，但策略永远不贪心，实测差 5.082 到 27.573。 衰减太快：比如 ε_k = 1/k²。它确实趋于 0，渐近贪心没问题；但 Σ 1/k² 收敛到 π²/6 ≈ 1.645，探索的总量是有限的。有限的探索量不能保证每个 (s,a) 被访问无穷多次，于是可能有格子永远拿不够数据——第二集那个盲区问题又回来了。 ε_k = 1/k 恰好卡在两者之间：衰减到 0，但慢到总量发散。这和 L3 第八集的 Robbins–Monro 条件是同一个形状的要求——Σα=∞ 且 Σα²<∞——这不是巧合，两者都是「走得到任何地方，又最终停下来」这一对要求的表达。

40 / 71

知识点 5 · 总结

ε 不是超参数，是收敛条件的一半

核心结论

GLIE 两条：无限探索（每个 (s,a) 访问无穷多次）+ 渐近贪心（策略最终收敛到贪心）。ε_k=1/k 同时满足。

底层机制

两条方向相反，所以衰减快慢是两难：太慢则永不贪心，太快（如 1/k²，Σ 收敛到 1.645）则探索总量有限。

常见误解

误解：「ε 取个 0.1 就好」。固定 ε 的代价不随训练时间减小 —— 实测差 5.082（ε=0.1）到 27.573（ε=0.5）。

与你的考试

与 L3 的 Robbins–Monro（Σα=∞ 且 Σα²<∞）是同一形状的要求：走得到任何地方，又最终停下来。

41 / 71

知识点 5 · 检验

ε_k = 1/k² 满足 GLIE 吗？

42 / 71

两条更新式，只有方括号里的目标不同。看起来像实现细节。

讲解

两个 TD 控制算法的更新式长得几乎一样：Q(s,a) ← Q(s,a) + α[目标 − Q(s,a)]。差别只在那个「目标」。 SARSA 的目标是 r + γQ(s′, a′)，其中 a′ 是实际采取的下一个动作——也就是 ε-greedy 抽出来的那个，可能是探索动作。名字就是这么来的：state-action-reward-state-action。 Q-learning 的目标是 r + γ max_a Q(s′, a)，用的是下一状态里最好的那个动作，不管你实际走了哪个。看起来只是取不取 max 的区别。下面用一笔具体的转移看看差多少。

43 / 71

差别只是写法反正都收敛到 Q*

两者确实都收敛到 Q*。但它们在收敛前学的不是同一个东西。

讲解

这个错误模型有一条正确的依据：在表格设定下，SARSA（配 GLIE）和 Q-learning 都收敛到 Q*。既然终点一样，中途的差别听起来就像实现细节。这和 L2 第七集犯的是同一类错误——用终点相同推出中途相同。那一集已经给过一次教训：策略迭代和值迭代都收敛到 V*，但中途手里拿的是完全不同的东西。这里的差别更硬：两者学的是两个不同策略的值。下面先看数字，再说这意味着什么。

44 / 71

SARSA: r + γ Q (s^{'}, a^{'}) Q-learning: r + γ max_{a} Q (s^{'}, a)

SARSA 的目标取决于你实际怎么走；Q-learning 的不取决于。

讲解

把两个目标并排写。 SARSA 的目标里有 a′，而 a′ 是由当前正在执行的策略（ε-greedy）抽出来的。所以目标取决于你实际怎么走——包括你探索时走的那些坏动作。这叫 on-policy：学的是你正在跟随的那个策略的值。 Q-learning 的目标里是 max，和你实际走了哪个动作完全无关。所以它学的是「假如从下一步起完全贪心」的值。这叫 off-policy：行动用一个策略，学习的是另一个策略的值。顺带记一处记号变化：从 SARSA 开始，讲座把 Q 的上标 π 去掉了。这不是笔误——在证明里 Q^{π_i} 是一个固定策略的值，而在算法里 Q 是一个不断移动的估计，目标策略一直在变。

45 / 71

r = 0, γ = 0.9, Q (s^{'}, a_{greedy}) = 10, Q (s^{'}, a_{taken}) = 2

同一笔数据，两个目标差 7.2。这不是写法差别。

讲解

看什么：看右边那根比左边高出多少：同一笔数据，Q-learning 的目标是 SARSA 的五倍。差的 7.2 就是「假设不再犯错」值多少。　—— 取一笔具体的转移：奖励 0，γ=0.9，下一状态里贪心动作的 Q 是 10，而 ε-greedy 这次恰好抽中了一个探索动作，它的 Q 是 2。 SARSA 的目标是 0 + 0.9×2 = 1.8。Q-learning 的目标是 0 + 0.9×10 = 9.0。同一笔数据，两个目标相差 7.2——在 Q 的量级只有 10 的情况下。这不是精度差别，是两个算法在问两个不同的问题。 SARSA 在问：「按我现在这个会犯错的策略继续走下去，值是多少？」Q-learning 在问：「假如从下一步起我再也不犯错，值是多少？」

46 / 71

指名反驳：不是写法，是 on-policy 与 off-policy —— 学的是两个策略的值。

讲解

指名回去：差别不是写法，是学谁的值。SARSA 学的是「包含探索在内的那个策略」的值；Q-learning 学的是贪心策略的值，而它自己走的却是 ε-greedy。这个差别有一个经典的可观察后果，就是悬崖行走（cliff walking）：一条最短路紧贴悬崖边，旁边有一条绕远但安全的路。Q-learning 会学出贴边的最短路——因为它评估的是「假如不犯错」的值，而贴边在不犯错时确实最优。SARSA 会学出绕远的安全路——因为它评估的是「带着 ε 探索」的值，而贴边时一次探索就会掉下去。两个答案都对，只是在回答不同的问题。如果你的智能体在训练时就要承担代价（真实机器人、线上系统），SARSA 的答案才是你要的；如果探索是免费的、只关心最终部署的贪心策略，Q-learning 更直接。最后提示一个记号陷阱：学生在课上问 SARSA 目标的下标时，字幕把它转成了「Q ST one A be plus one be ST plus one」这种完全读不出来的形态。它指的是 Q(s_{t+1}, a_{t+1})。

47 / 71

知识点 6 · 总结

SARSA 与 Q-learning 差的不是写法，是学谁的值

核心结论

同一笔转移（r=0, γ=0.9, 贪心 Q=10, 实走 Q=2）：SARSA 目标 1.8，Q-learning 目标 9.0，差 7.2。

底层机制

SARSA 的目标含实际采取的 a′ ⟹ on-policy，学含探索的策略；Q-learning 用 max ⟹ off-policy，学贪心策略。

常见误解

误解：「都收敛到 Q*，所以差别是实现细节」。这是 L2 第七集同一类错误：用终点相同推中途相同。

与你的考试

悬崖行走：Q-learning 学贴边最短路，SARSA 学绕远安全路。训练时要承担代价就选 SARSA。

48 / 71

知识点 6 · 检验

悬崖行走里，为什么 SARSA 学出绕远的安全路而 Q-learning 学出贴边的最短路？

49 / 71

Q-learning 的收敛，讲座明确分成了两条，而且要求不同。

讲解

Q-learning 的收敛性在讲座里被拆成了两条陈述，而且她特意强调了这两条的要求不一样。这是本讲少有的、被明确点名的不对称。第一条：Q 收敛到 Q*。第二条：你实际跟随的那个策略收敛到最优策略。它们听起来几乎是同一件事——既然 Q 对了，贪心读出来的策略不就最优了吗？下面会看到，第二条需要一个第一条不需要的额外条件。

50 / 71

Q 对了，策略就最优贪心读一下不就行了

「Q 对了策略就对」在读出来的意义上成立 —— 但你走的不是那个策略。

讲解

这个错误模型的依据是第一集：从 Q 贪心只要 argmax，不需要模型。既然 Q 已经等于 Q*，那 argmax_a Q*(s,a) 当然就是最优策略。这一步推理本身没错。错在它偷换了「策略」这个词的所指。从 Q* 贪心读出来的策略确实是最优的。但在学习过程中，你实际执行的是 ε-greedy 策略——它以 ε 的概率故意走别的动作。你拿到的回报由后者决定，不由前者决定。

51 / 71

两条的门槛不同：Q 收敛不需要 GLIE，策略最优需要。

讲解

把两条的条件摊开。 Q → Q* 需要两件事：每个 (s,a) 被访问无穷多次，以及步长满足 Robbins–Monro（Σα=∞ 且 Σα²<∞）。注意没有 GLIE——不要求策略最终变贪心。这正是 off-policy 的红利：Q-learning 的目标里是 max，和你实际怎么走无关，所以只要你走得足够杂、每个格子都能拿到数据，Q 就会收敛到最优值。 跟随的策略 → 最优 在上面之外还要 GLIE。因为「跟随」指的是你实际在走的那个 ε-greedy 策略，而只要 ε 不趋于 0，它就永远带着随机性。这个不对称是讲座明确说出来的，值得记住——它是 off-policy 这件事最实用的一个推论。

52 / 71

哪怕 Q 已经精确等于 Q*，固定 ε 的策略仍然差这么多。

讲解

看什么：看这三根柱子 —— 它们和第五集那张一模一样。因为这个损失和 Q 准不准完全无关：这里的 Q 已经精确等于 Q* 了，差距照样在。　—— 把第五集那组数字原样搬过来，但这次的设定不同：这里假设 Q 已经精确等于 Q*，一点估计误差都没有。差距还是 5.082、15.976、27.573，一个字都没变。这正是要点：这个损失不来自 Q 估得不准，来自你执行的是一个带 ε 随机性的策略。把 Q 学到完美也消不掉它。所以「Q 收敛了」和「我拿到最优回报了」是两件必须分开说的事。

53 / 71

指名反驳：Q-learning 学的是贪心策略，走的是 ε-greedy。两个策略。

讲解

指名回去：「Q 对了策略就最优」混淆了学的策略和走的策略。 Q-learning 是 off-policy 的，这意味着它故意让两者分开：目标里的 max 让它学贪心策略的值，而行为上它按 ε-greedy 走。分开是它的设计，不是缺陷——正因为分开，它才能用任意杂乱的数据学到最优值。但代价就是这一集的主题：Q 收敛不蕴含你拿到最优回报。要让后者也成立，必须额外要求 GLIE，把行为策略逐渐收拢到贪心。这个区分在离线强化学习里会被放到最大：那里行为策略是别人留下的日志，你完全无法控制，于是「学到的策略好」和「能不能真的去执行它」彻底脱钩。

54 / 71

知识点 7 · 总结

Q 收敛到 Q*，不等于你跟随的策略是最优的

核心结论

Q → Q* 只要「每个 (s,a) 无限次访问 + Robbins–Monro 步长」，不要 GLIE；跟随的策略 → 最优 还要 GLIE。

底层机制

off-policy 让学的策略（贪心）与走的策略（ε-greedy）分开。分开是设计，代价就是这条不对称。

常见误解

误解：「Q 对了，贪心读一下就最优」。读出来的确实最优，但你执行的不是那个策略。

与你的考试

实测：即使 Q 已精确等于 Q*，固定 ε 的策略仍差 5.082（ε=0.1）到 27.573（ε=0.5）。

55 / 71

知识点 7 · 检验

Q-learning 保证 Q → Q*，需要 GLIE 吗？

56 / 71

E [r ∣ a_{1}] = E [r ∣ a_{2}] = 0 ⟹ V^{*} = 0

单状态、两动作，奖励都是零均值。所以 V* = 0，没有悬念。

讲解

最后两集讲一个在深度强化学习里影响极大、而在表格世界里就已经存在的现象。构造一个尽可能干净的环境：只有一个状态，两个动作，两个动作的奖励都服从零均值分布（比如标准正态）。两个动作一样好，而且都是零。所以 V* = 0，这一点没有任何悬念。现在用有限的样本去估它：每个动作抽 n 个样本，Q̂ 取样本均值，然后按 max_a Q̂ 报告这个状态的值。问题是：这个报告出来的数，期望是多少？

57 / 71

无偏的 max 还是无偏每个 Q̂ 都无偏，取个最大值而已

每个 Q̂ 确实无偏。这个前提是对的 —— 结论不是。

讲解

这个错误模型的前提完全正确：Q̂(a₁) 和 Q̂(a₂) 都是样本均值，都是各自真值的无偏估计。实测二十万次，两者的期望都是 0.00 上下（±0.003）。由此推出「那 max 也无偏」几乎不需要思考——取最大值看起来只是从两个无偏的数里挑一个。但「挑最大的那个」不是一个线性操作。而期望只对线性操作可交换。下面先用不等式说清，再用数字验。

58 / 71

E [max_{a} \hat{Q} (a)] \geq max_{a} E [\hat{Q} (a)] = V^{*}

max 是凸函数，所以 Jensen 给出「先取 max 再求期望」不小于反过来。

讲解

机制是 Jensen 不等式。max 是一个凸函数，而对凸函数 φ 有 E[φ(X)] ≥ φ(E[X])。代进来就是：E[max_a Q̂(a)] ≥ max_a E[Q̂(a)]。右边因为每个 Q̂ 无偏，等于 max_a Q(a) = V*。所以 E[max Q̂] ≥ V*，而且只要 Q̂ 有随机性、两个动作有可能互换名次，这个不等号就是严格的。直觉上也说得通：取最大值这个操作会系统性地挑中那些运气好、噪声偏高的估计。噪声本身被当成了信号。

59 / 71

20 万次模拟， \hat{Q} 取 n 个样本的均值

实测 E[max Q̂]：n=10 时是 +0.178，而真值是 0。

讲解

看什么：看柱子往下掉得有多慢：样本从 1 个加到 100 个，偏差只从 0.565 降到 0.056。每一根都在零线之上 —— 而正确答案就是零。　—— 二十万次模拟。每个动作抽 n 个样本，取均值得到 Q̂，然后记录 max。 n=1 时 E[max Q̂] = +0.565；n=10 时 +0.178；n=100 时 +0.056。真值始终是 0。这些数和理论值 1/√(πn) 吻合到小数点后三位（0.564 / 0.178 / 0.056），说明模拟没有出错。请注意衰减速度：它按 n^(−1/2) 走，和蒙特卡洛的误差率同阶——也就是说，要把这个偏差减半，需要四倍的样本。而在强化学习里，那些访问次数最少的状态，恰恰是偏得最狠的。

60 / 71

同一批数据：单个估计无偏（0.001），取了 max 就偏成 0.178。

讲解

看什么：看左边那根几乎看不见——那是单个 Q̂ 的偏差，实测 0.001，本来就该贴着地面。右边那根是同一批数据取了 max 之后的偏差。偏差是 max 这个操作造出来的。　—— 把两件事放在同一张图上，因为它们同时成立，而这正是最反直觉的地方。左边：单个 Q̂ 的期望是 0.001——无偏，误差只是模拟噪声。右边：同一批数据取 max 之后，期望是 0.178。偏差不是从数据里来的，是 max 这个操作造出来的。你没有换估计器、没有换数据，只是多做了一次「挑最大的」。这解释了为什么它在 Q-learning 里无处不在：Q-learning 的目标里就有一个 max，每一步更新都在做这件事，而且偏差会通过自举往回传播到前面的状态。

61 / 71

指名反驳：max 不是线性的，所以期望不能穿过它。

讲解

指名回去：「每个无偏所以 max 无偏」错在把期望当成可以穿过任何操作。期望只与线性操作可交换；max 是凸的、不是线性的，Jensen 给的是不等号而不是等号。实用的推论有两条。第一，样本越少偏得越狠，而强化学习里访问次数最少的状态往往正是你最需要判断的那些（稀有但重要的状态）。第二，这个偏差会累积。Q-learning 每一步都在取 max，而自举又把值往回传，于是乐观的估计会一路传染到前面的状态，形成系统性的高估。最后按约定披露两处引文问题：讲座把最大化偏差的出处念成了「Johnson Tsitsiklis and Shie Mannor」，几乎可以肯定指的是 Mannor、Simester、Sun 与 Tsitsiklis 关于值函数估计中偏差与方差的工作；而下一集要讲的 Double Q-learning，它的实际出处（van Hasselt, 2010）在整讲里一次都没有被点名。

62 / 71

知识点 8 · 总结

每个估计无偏，取 max 就系统性乐观

核心结论

单状态两动作、奖励零均值（V*=0）。实测 20 万次：单个 E[Q̂]=0.001（无偏），而 E[max Q̂] 在 n=10 时是 +0.178。

底层机制

max 是凸函数，Jensen 给 E[max Q̂] ≥ max E[Q̂] = V*。取最大值会系统性挑中噪声偏高的那个 —— 噪声被当成了信号。

常见误解

误解：「每个无偏所以 max 无偏」。期望只与线性操作可交换，max 不是线性的。

与你的考试

偏差按 1/√(πn) 衰减（实测 n=1→0.565，n=100→0.056）：减半要四倍样本；而自举会把乐观往回传播。

63 / 71

知识点 8 · 检验

单状态两动作，两个动作真实期望奖励都是 0，每个动作抽 10 个样本取均值。E[max_a Q̂(a)] 约等于多少？

64 / 71

偏差的来源可以说得更准：同一批样本既选了动作，又报了它的值。

讲解

上一集把偏差归给了「max 是凸函数」。这个解释是对的，但还可以说得更有操作性。看看 max 到底做了什么：它先挑出估计值最大的那个动作，然后报告那个估计值。两件事用的是同一批样本。于是一个动作能被挑中，部分原因就是它这批样本的噪声偏高；而你接着又把这个偏高的数报了出去。挑选和报告之间有了共谋。一旦这么说，修法就摆在眼前了。

65 / 71

两张表求个平均多估几次取平均，方差不就小了

平均确实能压方差 —— 但这里的毛病是偏差，平均压不掉。

讲解

听说要用两张 Q 表，最自然的猜想是：估两次取平均，减小方差。这个直觉在别处几乎总是对的——集成方法、重复测量、批量平均，都是靠平均压方差。但这里的毛病不是方差，是偏差。而平均两个同样有偏的估计，得到的还是一个同样有偏的估计：如果两张表都用「自己选、自己报」的方式算 max，各自都偏 +0.178，平均之后还是 +0.178。所以关键不可能是平均。下一镜说清关键是什么。

66 / 71

a^{*} = \arg max_{a} Q_{A} (a) report Q_{B} (a^{*})

关键不是平均，是解耦：用 A 表选动作，用 B 表报它的值。

讲解

Double Q 的做法是解耦：维护两张独立更新的 Q 表。用 A 表挑出动作，再用 B 表报告那个动作的值。为什么这就管用：a* 是按 A 表的噪声挑出来的，而 B 表的样本和 A 表独立。所以对 B 来说，a* 只是一个「外面指定的动作」，不是从自己的估计里挑出来的最大值——B 对它的估计仍然无偏。挑选的偏好和报告的数值，来自两批互不相干的噪声。共谋断了。实现上两张表轮流更新：每一步随机选一张作为「选动作」的表，另一张作为「报值」的表，然后只更新前者。

67 / 71

同样 n=10：单 Q 偏 +0.178，双 Q 只剩 −0.002。

讲解

看什么：看右边那根几乎不存在：左边是自选自报的 +0.178，右边是解耦之后的 −0.002。同样的数据量、同样的 n，差别只在「谁选、谁报」。　—— 同一个实验，同样每个动作 10 个样本。单 Q（自己选、自己报）：+0.178。双 Q（A 表选、B 表报）：−0.002——已经落在模拟噪声里。数据量完全没变，n 也没变。唯一的改动是「挑动作的那批样本」和「报数值的那批样本」不再是同一批。这也反过来确认了上一集的诊断：偏差确实来自挑选与报告的共谋，而不是来自样本太少。样本少会让方差大，但偏差是结构造成的。

68 / 71

指名反驳：两张表有用不是因为平均，是因为它们互相独立。

讲解

指名回去：两张表有用不是因为平均，是因为它们互相独立，从而切断了挑选与报告之间的共谋。如果两张表用同一批数据更新，它们就不独立，偏差一点也不会少。代价要说清楚：每张表只拿到大约一半的数据，所以各自的方差更大。这是一次典型的偏差–方差交换——而 L3 第四集已经建立过判据：看的是总 MSE，不是有没有偏差。在最大化偏差很重的问题上（动作多、噪声大、访问稀疏），这笔交换划算；反之未必。最后补两处出处，因为讲座这里的引文都坏了。最大化偏差被念成「Johnson Tsitsiklis and Shie Mannor」，几乎可以肯定指的是 Mannor、Simester、Sun 与 Tsitsiklis 关于值函数估计中偏差与方差的工作。而 Double Q-learning 本身出自 van Hasselt (2010)，这个名字在整讲里一次都没出现过；后来的 Double DQN（van Hasselt、Guez、Silver, 2016）把它搬进了深度网络，是 Atari 上最有效的改动之一。

69 / 71

知识点 9 · 总结

Double Q 有效不是因为平均，是因为把「选」和「评」解耦

核心结论

a* = argmax Q_A(a)，但报 Q_B(a*)。实测 n=10：单 Q 偏 +0.178，双 Q −0.002。

底层机制

a* 是按 A 的噪声挑的，而 B 的样本与 A 独立 ⟹ 对 B 而言 a* 只是外部指定的动作，估计仍无偏。共谋断了。

常见误解

误解：「两张表求平均减小方差」。毛病是偏差不是方差；平均两个同样有偏的估计还是有偏。

与你的考试

代价：每张表只拿到约一半数据，方差更大。判据仍是总 MSE（L3 第四集）。出处：van Hasselt (2010)，讲座未点名。

70 / 71

知识点 9 · 检验

Double Q-learning 为什么能消掉最大化偏差？

71 / 71

讲解

回头看这九集，承重的是三件事。第一，控制要用 Q 不用 V。从 V 贪心必须穿过一次 Bellman 回溯，那一步要 P 和 R；从 Q 贪心只要 argmax。代价只是把表从 |S| 撑到 |S||A|——火星车上是从 7 个数变成 14 个数，换掉了整个模型。第二，探索不是工程细节，是收敛的前提。确定性贪心每个状态只采一个动作，别的动作的 Q 永远不更新；而固定的 ε 又保证你跟随的策略永远不是最优的（实测 ε=0.1 时差 5.082，ε=0.5 时差 27.573）。GLIE 的两个条件正是为了同时避开这两个坑。第三，取 max 会把无偏的估计变成有偏的。每个 Q̂ 都无偏，但 E[max Q̂] ≥ max E[Q̂] —— 实测 n=10 时真值 0 被估成 +0.178。Double Q 的修法不是平均，是把「用哪张表选动作」和「用哪张表报它的值」拆开。下一讲把表格拿掉。状态多到存不下时 Q 表要换成函数逼近，而这一讲所有的收敛性保证会在那里失效——不是收敛到错的值，是可能根本不收敛。

CS234 L4 · 无模型控制 · 全片速览

开场

1 · 控制必须估 Q，不是 V —— 因为从 V 贪心要穿过模型

控制要用 Q，不是因为 Q 更准，是因为从 V 贪心要穿过模型

2 · 确定性贪心策略，学不到它没试过的动作

确定性贪心策略学不到它没试过的动作

3 · ε-greedy 的贪心概率是 1−ε+ε/|A|，不是 1−ε

ε-greedy 的贪心概率是 1−ε+ε/|A|，不是 1−ε

4 · ε-greedy 策略改进定理：加了随机性，单调改进仍然成立

ε-greedy 的策略改进仍然单调 —— 随机化被平均项精确补偿

5 · GLIE 的两个条件：无限探索 + 渐近贪心

ε 不是超参数，是收敛条件的一半

6 · SARSA 与 Q-learning：同一笔数据，两个目标

SARSA 与 Q-learning 差的不是写法，是学谁的值

7 · Q 收敛到 Q*，不等于你跟随的策略是最优的

Q 收敛到 Q*，不等于你跟随的策略是最优的

8 · 最大化偏差：每个估计无偏，取 max 就系统性乐观

每个估计无偏，取 max 就系统性乐观

9 · Double Q：关键不是平均，是把「选」与「评」解耦

Double Q 有效不是因为平均，是因为把「选」和「评」解耦

完