外观
多臂老虎机（Multi-Armed Bandit）
一句话定位：这一页讲清楚多臂老虎机（Multi-Armed Bandit）问题——它把 RL 中最核心的矛盾"探索与利用"压缩成一个单步决策问题；读完后你能形式化遗憾（regret），推导并实现 ε-greedy、UCB1、Thompson Sampling，并理解它为什么是推荐、广告、A/B 测试的工程基石。
一、问题形式化：一台"贪心"的机器
1. 名字的由来与直觉
"老虎机"是赌场里拉一下手柄就出结果的老虎机（slot machine），"多臂"指有 K 台不同的老虎机摆在面前，每台的赢钱概率不同。你只能有限次地去拉，目标是最大化总收益。
text
┌─────────────────────────────────────────────┐
│ 多臂老虎机：K 个选项，一次选一个，立即拿奖励 │
│ │
│ 臂 1 臂 2 臂 3 ... 臂 K │
│ ? ? ? ? │
│ 每个臂背后有一个未知的奖励分布 │
│ │
│ 你的钱 = 有限 T 步 │
│ 每步：选一个臂 a → 从它的分布抽一个奖励 r │
│ 目标：最大化 Σ r │
└─────────────────────────────────────────────┘用数学语言写：有 K 个"臂"，第 $a$ 个臂每次被选时给出奖励 $r \sim \nu_a$（未知分布），期望奖励 $\mu_a = \mathbb{E}[r]$。智能体一共做 $T$ 次选择，目标最大化 $\sum_{t=1}^T r_t$。
2. 与完整 RL 的关系：去掉"状态"与"时序"
多臂老虎机是 MDP 的特例：只有一个状态（或者没有状态），动作不改变状态，奖励立即给出。也就是说，它是"单步决策"问题。
| 维度 | 多臂老虎机 | 完整 RL（见马尔可夫决策过程） |
|---|---|---|
| 状态 | 没有 / 单一状态 | 每个时刻的状态 s |
| 动作是否影响未来 | 不影响（一步一结） | 影响后续所有状态 |
| 信用分配 | 不需要（奖励即时） | 困难（延迟奖励、稀疏奖励） |
| 核心难点 | 探索 vs 利用 | 探索 vs 利用 + 信用分配 |
| 价值估计 | 估计每个臂的均值 $\hat\mu_a$ | 估计 $Q(s,a)$ |
所以 bandit 常被称为"RL 的简化实验室"：所有 RL 算法都内含一个 bandit 子问题——"在状态 s 下，选哪个动作"。理解了 bandit 的探索策略，就理解了 RL 探索的一半。
3. 遗憾（regret）：探索与利用的量化代价
仅看"总奖励"不够客观，因为问题难度不同。标准指标是遗憾：
$$ \text{Regret}(T) = T \cdot \mu^* - \mathbb{E}\left[\sum_{t=1}^T r_t\right] $$
其中 $\mu^* = \max_a \mu_a$ 是最优臂的期望奖励。遗憾 = "如果你每一步都知道最优臂，能拿到的总收益" − "你实际拿到的总收益"。遗憾为 0 意味着每步都选了最优臂（现实中不可能，因为一开始不知道哪个臂最优）。
为什么遗憾是正确指标
遗憾把"学习成本"和"决策质量"统一成一个数字：它同时惩罚"探索太多"（浪费在次优臂上）和"利用太早"（锁定在次优臂上）。最优算法的目标是让遗憾尽可能慢地增长。
理论上的下界：任何算法在 $T$ 步后的期望遗憾至少是 $\Omega(\sqrt{KT})$（minimax 下界；对固定实例则是对数下界 $\frac{\ln T}{\Delta}$）。也就是说，线性遗憾是平庸的，$\sqrt{T}$ 量级的遗憾是理论可达的。这也是 UCB、Thompson Sampling 的论文里反复出现的量级。
二、ε-greedy：最简单也最重要的基线
1. 算法
每一步以概率 $\varepsilon$ 随机选一个臂（探索），以概率 $1-\varepsilon$ 选当前均值最高的臂（利用）：
python
import numpy as np
class EpsilonGreedy:
def __init__(self, n_arms, eps):
self.n_arms = n_arms
self.eps = eps
self.counts = np.zeros(n_arms) # 每个臂被拉的次数
self.values = np.zeros(n_arms) # 每个臂的均值估计
def select(self):
if np.random.rand() < self.eps: # 探索：随机选
return np.random.randint(self.n_arms)
return np.argmax(self.values) # 利用：选均值最高的
def update(self, arm, reward):
self.counts[arm] += 1
# 增量式均值更新：新均值 = 旧均值 + (新奖励 - 旧均值) / 次数
self.values[arm] += (reward - self.values[arm]) / self.counts[arm]注意 update 用的是增量式均值更新：$Q_{n+1} = Q_n + \frac{1}{n}(r_n - Q_n)$，等价于 $\frac{1}{n}\sum r_i$，但不用存全部历史，且天然适配流式数据。
2. 优点与致命缺点
| 优点 | 缺点 |
|---|---|
| 实现 10 行以内 | ε 是常量：探索概率永远不变，已经确认最优臂后还在浪费 |
| 无需任何分布假设 | 线性遗憾：$O(\varepsilon T)$，T 越大越不可接受 |
| 是绝大多数 RL 算法的内置探索器 | ε 怎么选？小则探索不足，大则浪费 |
3. 改进：衰减 ε
可以让 ε 随时间衰减（如 $\varepsilon_t = 1/t$），先多探索、后多利用。但衰减速度又是新的超参，且对"最优臂何时被发现"过于敏感。工程上 ε-greedy 的定位是"基线"：任何新探索方法都得先打赢它，再谈别的。
三、UCB1：乐观面对不确定性
1. 直觉：对"样本少的臂"开绿灯
ε-greedy 的探索是"瞎试"——均匀随机选臂，没考虑"哪个臂更值得试"。更好的思路是系统性探索：优先选"上界高的"臂。
每个臂的均值估计 $\hat\mu_a$ 是一个统计量，它带不确定度。被拉过 100 次的臂，$\hat\mu_a$ 很可信；只拉过 2 次的臂，$\hat\mu_a$ 可能远低于真实值。乐观原则（optimism in the face of uncertainty）：把每个臂的上界（上限）当它的"潜在价值"，选上界最高的。
text
μ 轴（奖励均值）
▲
│ ┌───┐ ┌───────────┐
│ │最佳│ │ 上界高 → │
│ │上界│ │ 选它！ │
│ ┌─────┘ │ └───┬───────┘
│ │ 臂A │ │ 臂B
│ └─────────┘ └─────────┘
│ 拉了很多次 → 拉得少 →
│ 上界紧贴均值 上界高高在上
└──────────────────────────────────────►2. UCB1 公式
$$ a_t = \arg\max_a \left( \hat\mu_a + c \sqrt{\frac{\ln t}{n_a}} \right) $$
- $\hat\mu_a$：臂 a 的经验均值（利用项）；
- $n_a$：臂 a 被拉的次数；$t$：总步数（$t = \sum_a n_a$）；
- $c\sqrt{\frac{\ln t}{n_a}}$：置信上界（探索项）。
3. 公式的直觉：为什么是 $\sqrt{\ln t / n_a}$
- 分母 $n_a$：被拉得越少，不确定度越大 → 探索项越大 → 越容易被选中；
- 分子 $\ln t$：增长极慢，保证"每个臂都会被无限次地拉"（最终遗憾对数增长）但不会过度探索；
- 这是 Chernoff-Hoeffding 不等式的自然结果：以高概率，真实均值 $\mu_a$ 落在 $\hat\mu_a \pm \sqrt{\frac{2\ln(1/\delta)}{n_a}}$ 内。取 $\delta = 1/t^2$ 代入整理即得上式。
4. 为什么 UCB 能把遗憾压到对数
关键性质：每个次优臂的探索次数有对数上界。当最优臂与次优臂的差距为 $\Delta$ 时，次优臂大概只会被拉 $O(\frac{\ln T}{\Delta^2})$ 次。于是总遗憾 $\approx \sum_{\Delta} \frac{\ln T}{\Delta}$，远好于 ε-greedy 的线性遗憾。
UCB 的实际坑
- UCB1 假设奖励有界（通常归一化到 [0,1]）。奖励范围未知时要先缩放，否则公式的"上界"不再成立。
- 每个臂必须至少先拉一次（$n_a=0$ 时公式除零）。实现上先各拉一轮。
- 公式的 $c$ 是乐观系数：标准 UCB1 的探索项为 $\sqrt{2\ln t ,/, n}$（常数 $\sqrt{2}$），写成 $\mu + c\sqrt{\ln t/n}$ 时 $c=\sqrt{2}$；实践中 $c$ 可调（对应"乐观程度"），$c=1$ 是常见简化。
- 真实分布有重尾/大方差时，Hoeffding 界失效，UCB1 会退化——此时该用 UCB-V 或 Thompson Sampling。
四、Thompson Sampling：贝叶斯视角
1. 直觉：与其算上界，不如采一个"可能的真实值"
UCB 是频率学派：构造置信区间，取上界。Thompson Sampling（汤普森采样）是贝叶斯学派：对每个臂维护一个后验分布，每次按后验采样一个值，选采样值最大的臂。
text
后验分布（奖励均值的信念）
▲
│ ╱╲ ╱╲
│ ╱ ╲ ╱ ╲ ← 采样
│ ╱ ╲ ╱ ╲
│╱ 臂A ╲ ╱ 臂B ╲
└────────╳──────────►
│
└── 这次采样 B 更大 → 选 B直觉：后验分布"宽"的臂（样本少）每次采样可能落在很远的右边 → 被选中 → 得到更多样本 → 后验变窄 → 慢慢沉淀为真实均值。探索自动发生，且自动衰减——不需要 ε、不需要调 UCB 的 $c$。
2. 伯努利奖励的闭式实现
假设奖励 $r \in {0,1}$（点击/不点击），对臂 a 维护 Beta 后验：先验 $\text{Beta}(1,1)$（均匀），每观察到一次成功 $\alpha_a{+}{+}$，失败 $\beta_a{+}{+}$。后验仍为 Beta 分布（共轭性），采样即从 $\text{Beta}(\alpha_a, \beta_a)$ 抽一个值。
python
import numpy as np
from scipy.stats import beta as beta_dist
class ThompsonSampling:
def __init__(self, n_arms):
self.alphas = np.ones(n_arms) # 成功次数 + 1（先验）
self.betas = np.ones(n_arms) # 失败次数 + 1（先验）
def select(self):
# 从每个臂的后验采样一个"可能的真实均值"，选最大的
samples = beta_dist.rvs(self.alphas, self.betas)
return int(np.argmax(samples))
def update(self, arm, reward):
if reward == 1:
self.alphas[arm] += 1
else:
self.betas[arm] += 13. UCB vs Thompson Sampling 对比
| 维度 | UCB1 | Thompson Sampling |
|---|---|---|
| 学派 | 频率学派（置信区间） | 贝叶斯（后验采样） |
| 需要超参 | c（乐观系数） | 先验（通常无感） |
| 计算 | O(K) 均值+上界 | O(K) 分布采样 |
| 奖励分布假设 | 有界（Hoeffding） | 灵活（可换分布族） |
| 理论遗憾 | $O(K \ln T / \Delta)$ | 同量级（渐近最优） |
| 工程友好度 | 极高 | 极高，天然支持上下文 |
工程现实：Thompson Sampling 是工业界（推荐、广告、A/B 测试）最常用的选择——它好实现、无需调 ε、对非平稳分布也更容易扩展（加滑动窗口/衰减）。
4. 非平稳环境的变体
真实世界（广告 CTR、新闻热度）里臂的均值随时间漂移。两种常见处理：
- 滑动窗口：只统计最近 W 个样本的均值/后验；
- 折扣因子：更新均值时用 $\hat\mu \leftarrow \hat\mu + \alpha (r - \hat\mu)$，$\alpha$ 控制遗忘速度（类似 TD 的步长）。
面试高频追问
"如果最优臂的奖励均值随时间漂移，UCB 会怎样？"答：UCB 的 $\ln t$ 上界增长太慢，一旦锁定某个臂就不愿再探索，会错过漂移后的新最优臂。这就是为什么工业界常用折扣 TS。
五、contextual bandit：从"只看臂"到"看人下菜"
1. 问题升级
多臂老虎机假设所有用户的"臂均值"相同——但现实中，不同用户对同一个广告的点击率完全不同。contextual bandit 在每一步多给一个上下文特征 $x_t$（用户画像、时间、页面内容），目标变成：根据 $x_t$ 选臂，最大化期望奖励。
$$ a_t = \arg\max_a , \mathbb{E}[r \mid x_t, a] $$
它介于 bandit 与完整 RL 之间：有状态（上下文），但动作不改变状态。
2. 线性模型：LinUCB
最经典的 contextual bandit 算法是 LinUCB（Li et al., 2010，雅虎新闻推荐）。假设期望奖励是特征的线性函数：$\mathbb{E}[r|x,a] = \theta_a^\top x$，对每个臂维护岭回归参数 $\theta_a$ 及其协方差矩阵 $A_a$，置信上界变为：
$$ a_t = \arg\max_a \left( \hat\theta_a^\top x_t + c \sqrt{x_t^\top A_a^{-1} x_t} \right) $$
直觉：利用项是"预测的点击率"，探索项是"对这个预测有多不确定"。特征空间里探索过的地方（$x_t$ 靠近已有样本）不确定度小，没探索过的方向不确定度大。
3. 与完整 RL 的衔接
- contextual bandit 是推荐系统的主战场：见推荐与广告中的 RL；
- 完整 RL = contextual bandit + 动作影响未来状态（信用分配）。RL 的核心新增难点正是后者；
- 很多 RL 系统落地第一步是"先上 contextual bandit 跑通数据回路"，再逐步升级到带时序的 RL。
六、三方法对比实验直觉表
在一个"2 个臂、最优臂均值 0.9、次优臂 0.6、T=1000"的模拟中，典型结果：
| 方法 | 前 100 步 | 前 500 步 | 1000 步遗憾 | 特点 |
|---|---|---|---|---|
| ε=0.1 greedy | 大量随机浪费 | 仍在浪费 | ~100+ | 平稳线性增长 |
| ε=0.01 greedy | 探索不足，可能锁错臂 | 同上 | 看运气 | 方差极大 |
| UCB1 | 前几十步密集探索 | 快速收敛到最优 | ~10-20 | 对数增长，稳定 |
| Thompson Sampling | 与 UCB 相近 | 略快于 UCB（方差小时） | ~10 上下 | 最省探索 |
别只信一张图
这类对比对问题实例极其敏感：臂均值差距大时 ε-greedy 也够用；臂均值相近（Δ 小）时 UCB/TS 优势巨大。自己跑模拟时务必扫多组 (Δ, K, T)，别用一个案例下结论。
七、落地：推荐、广告、A/B 测试
1. 三个典型场景
| 场景 | 臂是什么 | 奖励是什么 | 上下文 |
|---|---|---|---|
| 内容推荐 | 候选文章/商品 | 点击、完读、购买 | 用户画像、历史行为 |
| 广告出价/选择 | 广告创意/广告位 | CTR、转化 | 用户 + 页面 + 时段 |
| A/B 测试 | 各变体 | 业务指标 | （无上下文 → 纯 bandit） |
2. Bandit 与 A/B 测试的关系：一场"动态实验"
传统 A/B 测试：流量按固定比例分给各变体，跑够样本再统计。Bandit：流量按实时表现动态分配——表现好的变体分到更多流量。好处是"边实验边赚钱"，坏处是统计功效下降、容易过早收敛到次优（尤其在非平稳流量下）。
工程上常用多层 Bandit + 护栏：
- 冷启动阶段多探索（TS 先验设宽）；
- 对商业指标（收入、CTR）设置最小流量保护（避免表现差的臂饿死）；
- 定期重新评估，允许"召回已淘汰的臂"（处理非平稳）。
3. 与 RLHF 的联系
你可能想不到：人类偏好数据本身就是一只"上下文老虎机"。RLHF 训练奖励模型时，需要对比两个回答哪个更好——这在理论上可以形式化为"在给定上下文（提示词）下选更优臂"的偏好学习问题；而 Bradley-Terry 模型正是把"二选一偏好"转成奖励的桥梁。详见RLHF 与人类反馈对齐中的奖励模型一节。
八、常见坑与工程师建议
坑 1：奖励不归一化就用 UCB
UCB 假设奖励有界。奖励是 0~1 的点击率可以直接用；如果是"金额"（0~500 元），必须先归一化或改用不依赖界的变体（如 UCB-V、TS）。
坑 2：忘了每个臂至少拉一次
UCB 公式里 $n_a=0$ 会除零；TS 若先验选 $\text{Beta}(0,0)$ 也无定义。实现里先做一轮"每臂各拉一次"。
坑 3：探索参数不随时间衰减
ε-greedy 用固定 ε 在长线任务里线性浪费。要么衰减，要么换 UCB/TS。
坑 4：把 bandit 直接当推荐系统用而忽略反馈延迟
广告转化往往滞后数小时到数天。延迟反馈会让均值估计偏差（此时高估近期臂）。解法：延迟修正、生存分析、或把"点击"作为即时代理奖励、"转化"作为延迟最终奖励（对应 RL 的延迟奖励概念）。
工程师建议表
| 需求 | 推荐方案 |
|---|---|
| 快速基线/教学 | ε-greedy（固定 0.1 起步） |
| 简单但高效 | Thompson Sampling（伯努利奖励用 Beta） |
| 理论面子/小臂数 | UCB1 |
| 有用户特征、要做个性化 | LinUCB 或 neural TS（contextual bandit） |
| 非平稳环境 | 折扣 TS / 滑动窗口 TS |
| 业务敏感（钱、体验） | 加流量护栏 + 离线回放（off-policy evaluation）先验证 |
延伸阅读
- 探索与利用 —— 从 bandit 的最小舞台扩展到深度 RL 的熵正则、curiosity、Go-Explore
- 推荐与广告中的 RL —— contextual bandit 如何在淘宝、阿里妈妈、YouTube 落地
- RLHF 与人类反馈对齐 —— 偏好采样与 Bradley-Terry 奖励模型，bandit 思想的 LLM 版本
- 数学基础速查 —— 期望、方差与 Hoeffding 不等式背后的数学
- 马尔可夫决策过程（MDP） —— bandit 是 MDP 在"无时序"时的特例
参考资料
- Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press. 第 2 章 "Multi-armed Bandits"：ε-greedy、UCB、梯度 bandit 的完整介绍与模拟实验。
- Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning, 47(2-3), 235-256. UCB1 的原始论文。
- Thompson, W. R. (1933). On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples. Biometrika, 25(3-4), 285-294. Thompson Sampling 的开山之作。
- Li, L., Chu, W., Langford, J., & Schapire, R. E. (2010). A Contextual-Bandit Approach to Personalized News Article Recommendation. WWW 2010. LinUCB 论文。
- Russo, D., Van Roy, B., Kazerouni, A., Osband, I., & Wen, Z. (2018). A Tutorial on Thompson Sampling. Foundations and Trends in Machine Learning. arXiv:1707.02038