多臂老虎机：探索与利用的平衡艺术
什么是多臂老虎机问题
多臂老虎机（Multi-Armed Bandit，简称 MAB）是强化学习中一个经典的问题模型，用于描述在不确定环境下如何进行序列决策。这个名字来源于赌场里的老虎机（俗称“独臂强盗”），假设你面前有一排老虎机，每台机器的中奖概率不同且未知。你的目标是通过一定的尝试次数，最大化累计奖励。每一次你只能选择拉动其中一台机器的拉杆，核心矛盾在于：是应该利用（Exploit）当前已知表现最好的机器，还是探索（Explore）那些你还不了解的机器以寻找可能更好的选项？
这一模型已广泛用于推荐系统、在线广告投放、临床试验设计、A/B 测试及动态定价等场景。
核心思想：探索与利用的权衡
多臂老虎机问题的本质是 探索（Exploration）与利用（Exploitation）的平衡。
- 利用：根据已有的经验，选择当前估计奖励最高的动作，短期收益可能最大。
- 探索：尝试那些次数较少或不确定性较高的动作，采集更多信息，即使短期内奖励较低，但可能发现更优选择，从而获得更高的长期收益。
如果一味利用，可能困在次优解；如果过度探索，会浪费机会在明显更差的选项上。因此，设计算法时需要量化这种权衡。
问题形式化定义
设有 $K$ 台老虎机（即 $K$ 个臂）。在每一轮 $t = 1, 2, \dots, T$：
- 算法选择一个臂 $a_t \in {1, 2, \dots, K}$。
- 环境根据该臂的真实奖励分布 $P_a$ 返回一个奖励 $r_t$，通常假设 $r_t \in [0,1]$ 且期望为 $\mu_a$。
- 我们无法直接知道各臂的真实期望 $\mu_1, \dots, \mu_K$。
目标是最大化累计奖励 $\sum_{t=1}^T r_t$，等价于最小化 悔值（Regret）：
$$ R_T = T \cdot \mu^* - \mathbb{E}\left[ \sum_{t=1}^T r_t \right] $$
其中 $\mu^* = \max_a \mu_a$ 是最优臂的期望奖励。悔值衡量了由于没有一直选择最优臂而造成的期望损失。一个好的算法应使悔值随 $T$ 增长速度尽可能低（理论下界约为 $O(\log T)$）。
经典 Bandit 算法
1. ε-贪婪算法（Epsilon-Greedy）
最直观的策略：以概率 $\epsilon$ 进行探索（随机均匀选择一个臂），以概率 $1-\epsilon$ 进行利用（选择当前估计平均奖励最高的臂）。
- 优点：实现简单，容易理解。
- 缺点：探索概率固定，随着时间积累仍会以恒定比例尝试明显较差的臂，导致线性悔值；对非平稳环境适应性差。
- 改进：可让 $\epsilon$ 随时间衰减，如 $\epsilon_t = 1/t$，使得探索逐渐减少，可获得对数悔值。
2. 乐观初始值（Optimistic Initial Values）
将所有臂的估计值初始化为一个较高的数值（例如 $+\infty$ 或明显大于实际可能奖励的值），然后纯利用地选择估计值最高的臂。由于初始估计过高，每个臂在被尝试足够多次之前都可能被选中，未被充分尝试的臂会因为其“乐观”估计而继续获得探索机会。这是一种通过“乐观面对不确定性”鼓励探索的方法。
- 优点：实现简单，无需额外参数，初期自动探索性强。
- 局限：对非平稳问题不友好，且初始值的设定需要领域知识。
3. 上置信界算法（Upper Confidence Bound，UCB）
核心思想：为每个臂的估计奖励构建一个置信区间，每次选择置信上界最大的臂。这样，既有高估计值的臂会被选中，那些尝试次数少、不确定性大的臂同样会因为其上界较高而获得探索机会。典型的 UCB1 算法选择臂的依据为：
$$ a_t = \arg\max_a \left[ \bar{r}_a + \sqrt{\frac{2 \ln t}{n_a}} \right] $$
其中 $\bar{r}_a$ 是臂 $a$ 的平均奖励，$n_a$ 是臂 $a$ 被选中的次数，$t$ 是当前总轮数。右侧的奖励项就是 探索奖励（Exploration Bonus），随次数增加而减小，随时间增加而增大，保证了每个臂最终都会被充分尝试。
- 优点：理论上悔值具有对数上界，均衡性好，无需调参（标准UCB1）。
- 缺点：对奖励假设较敏感，通常要求奖励有界；对非平稳环境需变体算法（如滑动窗口UCB）。
4. 汤普森采样（Thompson Sampling）
采用贝叶斯推断：为每个臂的奖励分布维护一个后验分布，每次行动时，从各臂的后验分布中采样，并选择采样值最高的臂。这自然实现了“根据当前不确定性按概率探索”：如果一个臂的真实奖励可能很高但不确定性大，则其采样值有时会很高，从而获得尝试机会。
例如，对于二元奖励（0/1），常使用 Beta 分布作为共轭先验：假设臂 $a$ 的成功次数为 $S_a$，失败次数为 $F_a$，后验为 $\text{Beta}(S_a+1, F_a+1)$。每次采样一个 $\theta_a$，选择 $\max \theta_a$。
- 优点：性能极佳，在实践中常优于 UCB；能灵活利用先验知识；可以处理复杂奖励模型。
- 缺点：后验更新需分布假设，计算采样代价稍高。
拓展变体与应用
上下文赌博机（Contextual Bandits）
当每个臂的期望奖励还依赖于用户的特征或上下文信息 $x$ 时，即为上下文赌博机。算法需学习一个映射 $f_a(x)$ 来预测奖励，典型方法有 LinUCB（基于线性模型）和神经网络 Bandit。广泛应用于个性化新闻推荐、广告点击率预估。
对抗性赌博机（Adversarial Bandits）
奖励不是从固定分布中产生，而是由对手事先设定（可自适应选择使算法损失最大）。这类设定下常用指数加权算法（如 EXP3），悔值界为 $O(\sqrt{T \ln K})$。适用于不可预测或非平稳的竞争环境。
实际应用场景
- 在线广告：选择不同的广告创意，最大化点击率或转化率。
- 推荐系统：在新物品冷启动阶段，平衡利用已知热榜内容和探索新内容。
- A/B 测试：自适应地调整流量分配，减少在较差变体上的损失。
- 医疗试验：在治疗中，根据患者反应动态调整治疗方案。
- 游戏AI与蒙特卡洛树搜索：用于选择最有希望的动作节点。
如何选择合适的算法？
- 简单需求、快速原型：ε-贪婪衰减版或乐观初始值往往够用。
- 理论保证、稳定环境：UCB1 是不错的选择，无超参数。
- 最优实践经验：汤普森采样在绝大多数非上下文场景中表现突出，且容易推广。
- 包含用户特征/上下文：必须使用上下文赌博机框架，LinUCB 简单高效。
- 不确定环境，激烈变化：考虑滑动窗口UCB或对抗性Bandit算法。
总结
多臂老虎机算法解决的核心问题是如何在信息不完全的情况下，优雅地平衡探索与利用。从最简单的 ε-贪婪，到具备坚实理论基础的 UCB 家族，再到灵活强大的汤普森采样，这些算法为现代推荐与决策系统提供了轻量且高效的在线学习方案。理解其原理，能帮助构建更加智能和自适应的数据驱动应用。