探索与利用

知识栏目里的大多数模型，都从别人收集好的数据集里学习。老虎机算法要自己收集数据。它每一轮选一个选项，只看到这个选项的回报，然后再选下一轮。这一点变化带来了监督学习从来不用面对的选择。学习者可以继续选目前看起来最好的选项，也可以花一轮去试一个还不够了解的选项。这篇笔记讲的就是这个选择。

基本想法

设想你刚搬到一个新街区，附近有四家咖啡店，每家都去过一次。街角那家不错，你可以每天早上都去。可这样一来，你永远不会知道车站旁那家是不是更好，因为你只在它最忙的那天喝过一杯不太好的咖啡。回街角那家是利用，用已经知道的信息换今天的好结果。再去车站那家试一次是探索，放弃一个大概率不错的早上，换一条可能管用好几个月的信息。

只要学习者自己的选择决定了它能看到什么数据，这个权衡就会出现。最干净的版本是多臂老虎机。有若干个臂，每个臂的平均回报都未知。每一轮你拉一个臂，只能看到这个臂的回报。你的选择不会改变这些臂，所以没有状态需要规划，只需要决定每一次拉动花在哪里。老虎机可以看作只有一个状态的马尔可夫决策过程，是强化学习主题里最简单的情形。完整强化学习里让探索变难的大部分因素，在这里已经出现了，而且规模小到可以直接在浏览器里模拟。

探索有代价，代价就是回报。每一次拉了更差的臂，都少拿了一份回报。衡量这个代价的常用指标叫遗憾（regret），也就是和一个从一开始就知道最好臂的人相比，你少拿了多少回报。

数学

设臂 $a$ 的平均回报为 $\mu_a$ ，其中最大的记为 $\mu^{*}$ 。臂 $a$ 被拉了 $N_a$ 次之后，它的估计值 $Q_a$ 就是这些回报的平均数。更新它不需要保存每一次的回报，一行增量公式就够了。

Q_a \leftarrow Q_a + \frac{1}{N_a}\bigl(R - Q_a\bigr)

新估计朝最新回报 R 移动 1/Nₐ 的距离。前几次回报对它影响很大，后面的回报几乎推不动它。

贪心规则每一轮都拉 $Q_a$ 最大的臂。ε-贪心大多数时候也这样做，但以概率 $\varepsilon$ 随机拉一个臂。

A_t = \begin{cases} \arg\max_a Q_a & \text{概率为 } 1-\varepsilon \\ \text{均匀随机选一个臂} & \text{概率为 } \varepsilon \end{cases}

ε-贪心的探索是盲目的。一个已经失败了 200 次的臂，和一个几乎没碰过的臂，被它随机选中的机会一样大。UCB1（置信上界）会把探索花在更值得的地方。它给每个估计值加一个奖励项，臂被拉得越少奖励越大，随着 $N_a$ 增加而缩小，然后拉总分最高的臂。

A_t = \arg\max_a \left[\, Q_a + c\sqrt{\frac{\ln t}{N_a}} \,\right]

每个臂先各拉一次，所以 Nₐ 不会为零。Auer、Cesa-Bianchi 和 Fischer 的 UCB1 在回报介于 0 和 1 之间时取 c = √2。

奖励项里的 $\ln t$ 增长得很慢，所以一个被冷落很久的臂会慢慢重新得到一次机会。估计值低、又被拉过很多次的臂，奖励项很小，会继续被冷落。这种思路叫面对不确定性时保持乐观。先假设每个臂可能和数据还允许的一样好，再让拉动的结果去证明它没那么好。

\operatorname{Regret}(T) = T\mu^{*} - \mathbb{E}\Bigl[\sum_{t=1}^{T} R_t\Bigr] = \sum_{a} \Delta_a\, \mathbb{E}\bigl[N_a(T)\bigr], \qquad \Delta_a = \mu^{*} - \mu_a

每拉一次更差的臂，就损失它的差距 Δₐ。所以遗憾统计的是每个更差的臂被拉了多少次、差了多少。

衡量一个规则，要看遗憾随 $T$ 怎样增长。贪心可能锁定在一个更差的臂上不再离开，遗憾随 $T$ 线性增长。固定 $\varepsilon$ 的 ε-贪心永远以同样的频率探索，遗憾同样线性增长，斜率由 $\varepsilon$ 和各臂的差距决定。UCB1 的遗憾按 $\ln T$ 增长，因为一个更差的臂只会被拉到足以排除它的次数。Lai 和 Robbins 在 1985 年证明，任何在所有老虎机问题上都表现良好的规则，遗憾至少按 $\ln T$ 增长，所以 UCB1 的增长形状已经是最好的。

动手试

下面的模拟器让三种规则在同一个四臂老虎机上比较。每个臂按它隐藏的概率给出 1，否则给出 0。每条曲线是 20 次带种子运行的平均，三种规则用的是同一组随机数，所以曲线之间的差距都来自规则本身。

ε，ε-贪心探索的频率0.10

c，UCB1 奖励项的权重0.5

轮数

种子 7

显示真实均值

UCB1
ε-贪心
贪心

读取第几轮的数值500

到第 500 轮为止，臂 A 到 D 各自被拉的比例和遗憾，取 20 次带种子运行的平均。
规则	Aμ ?	Bμ ?	Cμ ?	Dμ ?	遗憾
UCB1	4%	1%	77%	17%	15.5
ε-贪心	6%	3%	60%	31%	27.9
贪心	16%	5%	34%	45%	48.6

到第 500 轮，UCB1 的平均遗憾为 15.5，ε-贪心为 27.9，贪心为 48.6。UCB1 把 77% 的拉动给了最好的臂，ε-贪心是 60%，贪心是 34%。

合成数据模拟，带随机种子，同样的设置每次结果都一样。把鼠标移到图上，或拖动轮次滑块，可以读出任意一轮的数值。

把 ε 调到 0。ε-贪心的曲线会和贪心完全重合，因为没有随机拉动时，两条规则完全一样。
把 c 调到 0。UCB1 也会和贪心重合。
把 c 调到 1.4，接近原论文里的 √2。到 500 轮时，UCB1 反而落后于 ε-贪心。√2 来自一个对 0 到 1 之间任何回报都必须成立的界，在这个问题上，这么谨慎得不偿失。
切到 2,000 轮，看曲线的形状。贪心和 ε-贪心一直沿直线往上爬，UCB1 的曲线逐渐变平。
多按几次“换一组臂”。在一些问题上贪心运气好，看起来还不错。把很多问题平均起来，它就落后了。

我在哪用到它

COMP90051 · 多臂老虎机实验室

我 2023 年在 COMP90051 做的项目就是一个老虎机问题。我实现了能应对延迟或丢失反馈的逐次淘汰算法、Thompson 采样和 Doubly-Adaptive Thompson Sampling，并通过回放 30 万条真实新闻点击日志来评估。2026 年我把它重建成多臂老虎机实验室，最多七个算法在带种子的合成日志上同场比较，延迟分布也可以自己调。ε-贪心和 UCB1 是那里的基线，所以这篇笔记是入门，实验室是完整版。这场ε-贪心、UCB1 与 Thompson 采样的比赛会直接打开逐轮展示各算法内部判断的视图。

A/B 测试背后也是同一个权衡。固定五五分流的测试在整个周期里都在探索，直到宣布赢家才开始利用。老虎机会在测试进行中就把流量移向表现更好的版本，过程中损失更少，但最后的估计更难解读，因为看到哪些数据是算法自己选的。如果目标是干净地估计两个版本的差别，普通的随机化测试仍然是更合适的工具（见因果推断）。

容易出错的地方

五个陷阱，其中一个出自我自己的笔记

把探索的代价算成计算量。我 2023 年的 wiki 页面说探索很耗计算。可无论拉哪个臂，一次拉动的计算成本都一样。探索的代价是少拿的回报，遗憾就是用来衡量它的。
让 ε 永远固定。固定的 ε 会一直为探索付费，遗憾一直沿直线增长。让 ε 随时间衰减可以改变增长的形状，但衰减速度要针对每个问题去调，UCB1 不需要这一步。
把 c = √2 当成定律。它来自回报在 0 到 1 之间时的最坏情况界。如果回报在别的尺度上，要先缩放回报或重新调 c，否则奖励项要么小到不起作用，要么大到压过估计值。
凭一次运行评价规则。老虎机的单次运行噪声很大，贪心也会赢下其中一些。比较时要用多次带种子、共享随机数的运行，上面的模拟器和实验室都是这样做的。
假设各个臂不会变。增量平均给第 1 轮和第 1,000 轮的回报同样的权重。如果臂会漂移，比如点击率，就改用固定步长或滑动窗口，让旧的回报逐渐淡出。

参考资料

Reinforcement Learning: An IntroductionSutton 与 Barto，第 2 版，MIT Press，2018。第 2 章。最友好的入门。第 2 章用一个十臂的测试问题，从零讲到 ε-贪心、乐观初始值和 UCB，整本书都可以免费在线阅读。
Bandit AlgorithmsLattimore 与 Szepesvári，Cambridge University Press，2020。需要证明时查这本，UCB 的遗憾界和下面的下界都在里面。作者提供免费 PDF。
Finite-time analysis of the multiarmed bandit problemAuer、Cesa-Bianchi 与 Fischer，Machine Learning 第 47 卷，2002，第 235–256 页。UCB1 的出处。它证明了对任意有限轮数都成立的对数遗憾界，此前的结果只在轮数趋于无穷时成立。
Asymptotically efficient adaptive allocation rulesLai 与 Robbins，Advances in Applied Mathematics 第 6 卷第 1 期，1985，第 4–22 页。下界的出处。一个在所有老虎机问题上都表现良好的规则，遗憾不可能一直低于 ln T 的某个倍数。

最早写在我的 UOM-DS wiki（2023）里，2026 年从头重写。