卷 I · 试错CH 03深度 3/24

一台老虎机，整门学科最小的样本

把上一章那个循环砍到不能再砍：没有状态，没有转移，一局就一步。剩下的东西看起来简单得不像个研究课题——但它里面藏着一个矛盾，那个矛盾会一路跟到最后一章。

探索 vs 利用后悔值ε-greedy / UCB / Thompson

砍到最小

拿掉状态：不管你做什么，下一刻的处境和现在一样。拿掉转移：没有「以后」，这一步就是全部。

剩下的问题长这样：你面前有五台老虎机，每台的中奖概率不同，但你不知道是多少。你有一千次机会。怎么拉，总收益最大？

这叫多臂老虎机（multi-armed bandit）。名字来自赌场——老虎机的拉杆叫「臂」，而它们被称为「独臂强盗」。

它简单到可以在一张餐巾纸上说完，但它是这门学科的最小完整样本：所有关于「学习」的矛盾都在，只是被剥掉了所有干扰。

那个矛盾

你拉了三次第一台，中了两次。估计胜率 67%，不错。

现在第四次。拉第一台，还是试试没碰过的第二台？

  • 拉第一台（利用，exploitation）：稳。按当前掌握的信息，这是最优选择。
  • 试第二台（探索，exploration）：可能更差，浪费一次机会。但也可能发现一台胜率 90% 的，那么剩下的九百多次全都受益。

这就是探索与利用的矛盾。它没有完美解——因为它本质上是在拿确定的当下换不确定的未来，而你永远不知道未来值不值。

◆ 为什么这个矛盾在监督学习里不存在

训练一个图片分类器的时候，你不需要「探索」。数据集摆在那儿，你把每张图都看一遍就行。你的行为不影响你能拿到什么数据。

强化学习不是这样。你只能看见你走过的地方。没拉过的那台机器，你永远不知道它多好；没走过的那条路，Q 表里永远是初始值。

这个性质有个名字，叫数据分布依赖于策略。它是强化学习一切困难的根源，也是它区别于其他机器学习的那一条线。第 10 章那个「有两格从没走到过」，第 21 章那个「六百局都没找到终点」，都是它。

先看最笨的做法有多惨

「就一直拉当前估计最好的那台」——这叫全贪心。听上去很合理，毕竟你就是想赢钱。

下面这台是真的引擎。五台机器的真实胜率是 30%、50%、72%、45%、60%，第三台最好，但 agent 不知道。

▶ 动手 · 先点「全贪心」看那条直线

然后依次点过去。盯住两个数字：「后悔值」（越低越好）和「彻底走丢的实验」（多少次实验最后卡死在错误的臂上）。

全贪心为什么必然完蛋

结果是：后悔值 420，拉中最优臂的比例 0.0%，200 次独立实验里有 100% 彻底走丢了。一次都没找对。

原因很朴素。所有臂的初始估计都是 0，第一次它随便拉一台，假设中了——那台的估计变成 1.0，其他还是 0。于是第二次它还拉那台，第三次还拉那台……

它再也不会去碰别的机器，所以它永远不会知道自己错了。

这是一个自我封闭的循环，而且它看起来完全正常：分数在涨，估计在收敛，一切指标都健康。这是这本书第一次遇到「指标好看但结果是错的」，后面还会遇到很多次。

✎ 后悔值：这门学科的标准尺子

后悔值（regret）的定义是：「如果我从一开始就知道哪台最好、一直拉它」能拿到的，减去「我实际拿到的」。

为什么不直接看总收益？因为总收益和问题难度绑死了——胜率 90% 的机器和胜率 10% 的机器，总收益差十倍，但那和你的算法好不好没关系。后悔值把「问题本身有多好赚」这一项减掉了，剩下的纯粹是「你亏在决策上的部分」。

理论上的好消息：有算法能做到后悔值随时间对数增长（O(log T)），也就是说时间越长，平均每步的损失越接近 0。UCB 就是其中之一，这是它有名的原因。

五种解法，五种思路

① ε-greedy：留一个固定的口子

最简单的修法：大部分时候贪心，但有 ε 的概率完全随机挑一台。ε = 0.1 就是「10% 的步数用来瞎试」。

def choose(Q, eps):
    if random() < eps:
        return randint(len(Q))      # 探索：随便来一台
    return argmax(Q)                # 利用：当前最好的

丑，但有效：后悔值从 420 降到 55.5，走丢率降到 0%。

它丑在哪？探索的时候完全不动脑子。一台你已经拉过三百次、确定它很差的机器，和一台你从没碰过的机器，被同等对待。

顺带看一眼 ε = 0.01：后悔值 182，走丢率 36.5%。探索得太少，三分之一的实验还是卡死了。「留了个口子」和「口子够大」是两回事。

② ε 衰减：开始猛试，后来收手

ε 不固定，随时间往下掉。直觉很对：开局你什么都不知道，值得多试；后期你已经知道了，试就是纯亏。

结果 55.1，比固定 ε 略好一点。这也是实践中最常见的做法——DQN 那篇论文里 ε 从 1.0 线性降到 0.1，花了整整一百万步。

③ 乐观初始值：让失望自己带来探索

一个很漂亮的小技巧：不改算法，只把所有臂的初始估计设成一个高得离谱的值（比如 1.0，而实际最高胜率只有 0.72）。

然后就用纯贪心。会发生什么？它拉第一台，实际胜率 30%，估计从 1.0 掉下来；于是第二台变成「最好的」，它去拉第二台，也掉下来……它会被迫把每台都试一遍，仅仅因为现实总是让它失望。

后悔值 85.9——比 ε-greedy 差一点，但代码量是零。它的问题是走丢率还有 42.5%：一旦所有估计都掉到真实值附近，探索就彻底停了，运气不好就锁死。这个技巧只在开局有效，撑不了长跑。

④ UCB：给「不确定」明码标价

前面几种都在拍脑袋决定探索多少。UCB 换了个思路：把不确定性算出来，直接加到估计上去。

选 argmax [ Q(a)  +  c · √( ln t / N(a) ) ]
                     └──── 不确定性加成 ────┘

那一项的行为很符合直觉：N(a) 是这台机器被拉过多少次，拉得越少，加成越大；t 是总步数，时间越久，所有没拉的臂加成都在缓慢上涨（「好久没试了，说不定我记错了」）。

这叫面对不确定性时保持乐观——一个在整个领域反复出现的原则。UCB 的后悔值 56.1（c=1），走丢率 0%。

注意那个 c：demo 里 c=2 的后悔值是 109.8，比 c=1 差了将近一倍。它把「探索多少」这个问题从「ε 设多少」变成了「c 设多少」——问题没有消失，只是换了个形状。这种事在强化学习里非常常见，值得早点习惯。

⑤ Thompson 采样：按「它是最好的」的概率去抽

最优雅的一个，而且是 1933 年提出来的——比这个领域本身还老。

思路是贝叶斯的：不维护一个点估计，维护一个分布。拉了 3 次中 2 次的机器，它的胜率不是「67%」，而是一条以 0.67 为中心、比较宽的概率曲线。拉了 300 次中 200 次，同样是 67%，但曲线窄得多。

然后每一步：从每台机器的分布里各抽一个样，选抽中最大的那台。

妙在哪？没试过的机器分布很宽，抽出高值的概率不小，所以它自然会被试到；试了很多次确认很差的机器分布很窄，几乎不可能抽出高值。探索和利用不是两个模式，它们从同一个动作里自然长出来。

结果：后悔值 28，最优臂占比 84.9%——本章最好的成绩，而且好得不止一点。

⚠ 一次跑出来的结果没有意义

上面每个数字，都是 200 次独立实验的平均。这不是为了图表好看，是因为单跑一次的结论完全不可信。

我做这个 demo 的时候，随手用种子 7 跑了一次 ε=0.1，结果它一头扎进第五台（胜率 60%）再也没出来，最优臂占比 2.0%——比 ε=0.01 那次还惨。如果我拿这一次的结果写进书里，会得出「ε=0.1 不如 ε=0.01」这个完全错误的结论。

强化学习是出了名的方差大。你在论文和博客里看到的那些漂亮曲线，几乎都是几十上百次独立实验的平均加上置信区间。Sutton & Barto 书里那些经典图是 2000 次。

所以这本书立一条规矩，也建议你立：凡是给统计量，至少 5 个种子，报中位数和区间，不报最好那次。第 24 章那张排障表里，「每次跑结果都不一样」被明确归类为「RL 的正常状态」，不是 bug。

一张对照表

策略后悔值最优臂占比走丢率它的思路
全贪心4200.0%100%相信当前估计
ε = 0.0118236.6%36.5%留个小口子（太小了）
ε = 0.155.572.9%0%留个固定口子
ε 衰减55.176.7%0%先猛试，后收手
UCB（c=1）56.171.6%0%给不确定性加价
乐观初始85.955.5%42.5%用失望驱动探索
Thompson2884.9%0%按后验概率抽样
⌗ 换成真机：老虎机不只是玩具

这一章看起来最像玩具，实际上是本书里直接落地最多的一章。多臂老虎机是工业界用得最广的强化学习——比 DQN、PPO 加起来还广：

  • A/B 测试的升级版：传统 A/B 测试把流量对半分，直到实验结束。老虎机算法会动态把流量往表现好的版本倾斜，同样的结论、更少的损失。这叫自适应实验设计。
  • 推荐系统的冷启动：新内容没人点过，估计值是 0，纯贪心会让它永远不被推荐——这就是本章开头那个自我封闭的循环。所有推荐系统都得处理这个，用的多半是 Thompson 或 UCB 的变体。
  • 超参数搜索：Hyperband、BOHB 这些方法的底子是「连续减半」，本质上是老虎机。

如果你只想从这本书里拿走一样能明天就用上的东西，那就是这一章。

↩ 回到那个视频

你可能会想：老虎机和 QWOP 差太远了吧。

但那个学走路的小人，在每一帧都面对同一个矛盾：按当前策略走（利用），还是随机试一个没试过的动作组合（探索）？区别只是它面对的不是 5 台机器，而是「在这个状态下的所有可能动作」，而且状态还在变。

更直接的联系：DQN 的 ε 退火，就是这一章 ε-greedy 的原样搬运。一个能打通 49 个 Atari 游戏的算法，它的探索机制就是本章第一个、也是最丑的那个。

这一章的一句话

纯贪心必然完蛋，因为它没有机会发现自己错了。而探索不是浪费——是买保险，保的是「我现在相信的东西可能是错的」。

下一章：ε 到底该设多少？答案会告诉你一件不太舒服的事——这个数没有正确答案，它取决于你还剩多少局可以玩。