多臂老虎机

老虎机是探索问题的最纯净形式。本章介绍 $\epsilon$ -greedy、UCB1、Thompson 采样及其遗憾界，上下文老虎机与推荐系统的联系，以及它作为 RLHF 中偏好学习基础的角色。

问题设定

多臂老虎机（multi-armed bandit）是 RL 去掉状态转移后的残骸：没有状态（或状态恒定），每一步从 $K$ 个动作（臂）中选一个，得到一个来自未知分布的奖励 $r \sim R(a)$ 。它剥离了 RL 的时间结构，把纯粹的探索与利用权衡留下来：了解差的臂有价值吗？还是应该一直拉目前最好的臂？

衡量探索策略的标准是遗憾（regret）：到时刻 $T$ 为止，与"每一步都拉最优臂"相比少赚的部分：

$\mathrm{Regret}(T) = T\, \mu^* - \mathbb{E}\Big[\, \sum_{t=1}^{T} \mu_{a_t} \Big],$

其中 $\mu^* = \max_a \mu_a$ 是最优臂的均值。好策略的遗憾随 $T$ 增长得越慢越好，理想是 $O(\log T)$ ——意味着探索总量随时间增长得非常慢。

$\epsilon$ -greedy 及其遗憾

$\epsilon$ -greedy 在这里暴露出根本缺陷：它对每个臂都永久保留 $\epsilon$ 的探索概率，包括已经确认很差的臂。结果遗憾随 $T$ 线性增长——探索预算不随信息增加而收缩。只要让 $\epsilon$ 随时间衰减（ $\epsilon_t \propto 1/t$ ），配合适当的初始化，遗憾可以降到 $O(\log T)$ ，但这要求知道奖励分布的范围等先验。

UCB1

UCB（Upper Confidence Bound）把"探索"翻译成"置信区间宽的臂优先"：选上置信界最高的臂，

$a_t = \arg\max_a \left[\, \hat{\mu}_t(a) + \sqrt{\frac{2 \log t}{N_t(a)}}\ \right].$

直觉：被访问少的臂置信项大，"可能被低估"的臂自动获得探索机会；访问多了，置信项收缩，回到均值比较。UCB1 的遗憾为 $O(\log T)$ ，且不依赖奖励范围的先验——** optimism in the face of uncertainty**（面对不确定保持乐观）是它的设计哲学：把"不确定"当作"可能更好"的理由。

Thompson 采样

Thompson 采样走贝叶斯路线：维护每个臂奖励的后验分布（如 Bernoulli 奖励配 Beta 分布），每轮从各后验中各采一个样本、选样本最大者。它把不确定性翻译成行为：不确定的臂偶尔会采出很高的样本而被选中，确认差的臂几乎不再被选。理论上同样有 $O(\log T)$ 遗憾界；实践中通常与 UCB 相当甚至更好，且更容易推广（复杂奖励模型、上下文设定），代价是需要一个可采样的后验。

上下文老虎机

真实推荐场景中，"哪个内容好"取决于用户特征——把奖励分布改为依赖上下文 $x$ 的 $r \sim R(a \mid x)$ ，就是上下文老虎机（contextual bandit）。它在"每步都是独立的一次决策"与"完整 RL"之间：保留了探索问题，去掉了时间耦合（本步选择不影响下一步的分布）。代表方法 LinUCB、 Thompson 采样的线性版本。工业界推荐与广告系统大量使用这个模型（→ 推荐与广告），因为：

探索的代价可以用遗憾量化并控制在真实流量可承受的范围内；
不需要建模用户状态的长期转移，工程上简单可靠。

与 RLHF 的联系

RLHF 的偏好学习在结构上就是上下文老虎机：上下文 = 提示，动作 = 回复，奖励 = 人类偏好。InstructGPT 之后的主流做法是用偏好数据先离线训练奖励模型、再用 PPO 优化——这把探索从"在线试错"变成了"离线拟合"，回避了在线探索的代价（→ RLHF 全流程）。理解老虎机因此对理解"RLHF 为什么可以不要完整 RL"很有帮助。

本章要点

UCB 的遗憾为 $O(\log T)$
Thompson 采样在实践中常优于 UCB
上下文老虎机是推荐/广告的主力模型