# 多臂老虎机问题及其解法

- 原标题：The Multi-Armed Bandit Problem and Its Solutions
- 类型：博客
- 来源：Lilian Weng 博客
- 发布时间：未知（待核验）
- 首次精选：2026-10-29 23:09
- 分级：值得看
- 学习层级：进阶
- 主题：[reinforcement-alignment](<https://oplearnx.com/md/topics/reinforcement-alignment.md>)（第 2 位）、[business-decision-apps](<https://oplearnx.com/md/topics/business-decision-apps.md>)（第 13 位）
- 原文链接：[https://lilianweng.github.io/posts/2018-01-23-multi-armed-bandit](<https://lilianweng.github.io/posts/2018-01-23-multi-armed-bandit>)
- 本站页面：[https://oplearnx.com/resources/pk\_255eeda241b8](<https://oplearnx.com/resources/pk_255eeda241b8>)

## 摘要

这篇博客以“去哪家餐厅吃饭”等生活化例子说明利用与探索的权衡，界定多臂老虎机问题，并介绍若干策略：ε-贪心、基于 Hoeffding 不等式的置信上界 UCB1、贝叶斯 UCB、汤普森采样，最后附案例研究与总结。作者提到针对伯努利老虎机的算法实现在其 GitHub 仓库 lilianweng/multi-armed-bandit 中。

## 中文精读

### 1. 多臂老虎机问题及其解法（总览）

- 全文目录依次为：利用与探索的权衡、多臂老虎机是什么（定义与策略）、ε-贪心算法、置信上界（Hoeffding 不等式、UCB1、贝叶斯 UCB）、Thompson 采样、案例研究、总结、参考文献。
- 配套代码在 GitHub 仓库 lilianweng/multi-armed-bandit 中，针对伯努利老虎机（Bernoulli bandit）实现了文中各算法。

### 2. 利用与探索（Exploitation vs Exploration）

- 利用与探索的两难出现在生活各方面：每天去熟悉的餐厅能确定吃到什么，却错失发现更好选择的机会；总试新店则免不了时不时吃到难吃的。
- 在线广告场景类似，需要在已知最有吸引力的广告与可能更成功的新广告之间权衡。
- 若已完全掌握环境信息，穷举模拟都能找到最优策略，甚至不需要其他聪明方法；难题来自信息不完整。
- 需要在把风险控制住的同时收集足够信息以做出整体最优决策：利用是采取已知最好的选项，探索是冒风险去了解未知选项。
- 最优长期策略可能包含短期牺牲，例如一次探索彻底失败，但它提醒我们今后不要过多采取该动作。

### 3. 什么是多臂老虎机

- 多臂老虎机是体现利用与探索两难的经典问题：赌场里有多台老虎机，每台单次给奖的概率未知，问题是什么样的策略能获得最高长期回报。
- 文中只讨论试验次数无限的情形；试验次数有限会引入另一类探索问题，例如当试验次数少于机器数量时，连每台机器都试一遍以估计概率都做不到。
- 朴素做法是一直玩同一台机器很多轮，依大数定律估计其"真实"回报概率，但这很浪费，也不能保证长期回报最优。
- 文中配图展示了伯努利多臂老虎机的工作方式：各机器的回报概率对玩家是未知的。

### 4. 定义（Definition）

- 伯努利多臂老虎机可表示成元组 ⟨A, R⟩：共 K 台机器，回报概率为 \{θ1, …, θK\}。
- 每个时间步 t 对某台老虎机采取动作 a 并得到回报 r；动作集合 A 中每个动作对应与一台机器的交互，动作价值即期望回报 Q\(a\)=E\[r\|a\]=θ；若 t 时刻动作作用于第 i 台机器，则 Q\(a\_t\)=θ\_i。
- 回报函数 R 是随机的：t 时刻 r\_t=R\(a\_t\) 以概率 Q\(a\_t\) 返回 1，否则返回 0。
- 它是不含状态 S 的马尔可夫决策过程（Markov decision process）的简化版本。
- 目标是最大化累积回报 Σr\_t；若已知最优动作，目标等价于最小化未选最优动作带来的悔值（regret）。
- 最优动作 a\* 的最优回报概率为 θ\*=Q\(a\*\)=max\_a Q\(a\)=max\_\{1≤i≤K\} θ\_i；损失函数是到时间步 T 为止未选最优动作的总悔值 L\_T=E\[Σ\(θ\*−Q\(a\_t\)\)\]。

### 5. 老虎机策略（Bandit Strategies）

- 按探索方式划分，求解多臂老虎机有若干类做法。
- 第一类是不探索，这是最朴素也最差的做法；第二类是随机探索；第三类是聪明地探索，即偏向不确定性高的选项。

### 6. ε-贪心算法（ε-Greedy Algorithm）

- ε-贪心大部分时间采取最佳动作，偶尔进行随机探索。
- 动作价值按过去经验估计：对截至当前时间步 t 观察到的、与目标动作 a 相关的回报取平均，Q̂\_t\(a\) = \(1/N\_t\(a\)\) Σ r\_τ·1\[a\_τ=a\]，其中 1 为二值指示函数，N\_t\(a\) 是动作 a 迄今被选中的次数。
- 算法以较小概率 ε 采取随机动作，其余（概率 1−ε，即多数时间）选择目前学到的最佳动作 â\*\_t = argmax\_a Q̂\_t\(a\)。
- 文中给出了作者玩具实现（solvers.py）的链接。

```text
Q̂_t(a) = (1/N_t(a)) Σ_{τ=1}^{t} r_τ · 1[a_τ = a]
N_t(a) = Σ_{τ=1}^{t} 1[a_τ = a]
â*_t = argmax_{a ∈ A} Q̂_t(a)
```

### 7. 置信上界（Upper Confidence Bounds）

- 随机探索让我们有机会尝试了解不多的选项，但可能因运气不好而去探索一个过去已确认很差的动作。
- 避免这种低效探索有两种思路：一是随时间减小参数 ε；二是对不确定性高的选项保持乐观，优先选择价值估计还不确定的动作，即倾向于探索有较大概率具有最优价值的动作。
- UCB 算法用回报值的置信上界 Û\_t\(a\) 度量这种潜力，使得真实值以高概率满足 Q\(a\) ≤ Q̂\_t\(a\)\+Û\_t\(a\)；上界 Û\_t\(a\) 是 N\_t\(a\) 的函数，试验次数越多上界越小。
- UCB 总是选择使置信上界最大的动作：a^UCB\_t = argmax\_a Q̂\_t\(a\)\+Û\_t\(a\)。接下来的问题是怎样估计置信上界。

### 8. Hoeffding 不等式（Hoeffding's Inequality）

- 若不想对分布形状作任何先验假设，可借助 Hoeffding 不等式——一个适用于任意有界分布的定理。
- 设 X1,…,Xt 为独立同分布（i.i.d.）且都落在 \[0,1\] 区间的随机变量，样本均值 X̄\_t=\(1/t\)ΣX\_τ，则对 u\>0 有 P\[E\[X\] \> X̄\_t\+u\] ≤ e^\(−2tu²\)。
- 对某个目标动作 a，把 r\_t\(a\) 视为随机变量、Q\(a\) 视为真实均值、Q̂\_t\(a\) 视为样本均值、u 视为置信上界 U\_t\(a\)，则 P\[Q\(a\) \> Q̂\_t\(a\)\+U\_t\(a\)\] ≤ e^\(−2tU\_t\(a\)²\)。
- 希望以高概率让真实均值低于样本均值加上界，即让 e^\(−2tU\_t\(a\)²\) 是一个很小的概率；设定该概率等于阈值 p，可解出 U\_t\(a\)=√\(−log p / \(2N\_t\(a\)\)\)。

### 9. UCB1

- 一种启发式做法是让阈值 p 随时间减小，因为观察到的回报越多，越希望上界估计更有把握。
- 取 p=t^\(−4\) 即得到 UCB1 算法：U\_t\(a\)=√\(2 log t / N\_t\(a\)\)，动作选择为 a^UCB1\_t = argmax\_a Q\(a\)\+√\(2 log t / N\_t\(a\)\)。

### 10. 贝叶斯 UCB（Bayesian UCB）

- UCB1 等方法不对回报分布作先验假设，只能依赖 Hoeffding 不等式做很通用的估计；若能事先知道分布，就能得到更好的上界。
- 例如若预期每台机器的平均回报服从高斯分布，可把置信上界设为标准差的若干倍，从而得到 95% 置信区间；图中 c·σ\(a\_i\) 即上界，常数 c 是可调的（tunable）超参数。
- 文中给出 UCB1 与对 θ 使用 Beta 先验的贝叶斯 UCB 的玩具实现链接。

### 11. Thompson 采样

- Thompson 采样思路简单，但在多臂老虎机上效果很好。
- 每个时间步按动作 a 为最优的概率来选择它：π\(a\|h\_t\)=P\[Q\(a\)\>Q\(a'\), ∀a'≠a \| h\_t\]=E\_\{R\|h\_t\}\[1\(a=argmax\_a Q\(a\)\)\]，即在给定历史 h\_t 下采取动作 a 的概率。
- 对伯努利老虎机，Q\(a\) 本质上是伯努利分布的成功概率 θ，因此自然地假定它服从 Beta 分布；Beta\(α,β\) 取值在 \[0,1\]，α 与 β 分别对应拿到奖励（成功）与没拿到奖励（失败）的计数。
- α、β 可依先验知识初始化，例如 α=1、β=1 表示预期成功率 50% 但把握不大；α=1000、β=9000 表示强烈相信成功率是 10%。
- 每个时间步从各动作的 Beta\(α\_i, β\_i\) 中采样一个期望回报 Q̃\(a\)，选采样值最大的动作 a^TS\_t=argmax\_a Q̃\(a\)；观察到真实回报后更新：α\_i ← α\_i\+r\_t·1\[a^TS\_t=a\_i\]，β\_i ← β\_i\+\(1−r\_t\)·1\[a^TS\_t=a\_i\]，这相当于用已知先验与似然做贝叶斯推断求后验。
- Thompson 采样体现了概率匹配（probability matching）：由于 Q̃ 从后验分布采样，每个概率都等价于在给定历史下该动作最优的概率。

### 12. Thompson 采样（续）

- 许多实际复杂问题中，用贝叶斯推断从观测回报估计后验在计算上不可行；若能用 Gibbs 采样、拉普拉斯近似（Laplace approximation）、自助法（bootstrap）等近似后验，Thompson 采样仍可工作。

### 13. 案例研究（Case Study）

- 上述算法实现在 lilianweng/multi-armed-bandit 仓库中：BernoulliBandit 对象可用一组随机或预先设定的回报概率构造，各算法实现为 Solver 的子类并以 Bandit 对象为目标问题，随时间记录累积悔值。
- 小实验设置 K=10 台老虎机，回报概率为 \{0.0, 0.1, 0.2, …, 0.9\}，每个求解器运行 10000 步。
- 结果图包括三部分：左图为时间步与累积悔值的关系；中图为真实回报概率与估计概率的对比；右图为 10000 步中各动作被选中的比例。

### 14. 总结（Summary）

- 我们需要探索，因为信息是有价值的。
- 探索策略上可以完全不探索、只关注短期回报；也可以偶尔随机探索；还可以更进一步，对探索哪些选项有所挑剔——更偏好不确定性高的动作，因为它们能带来更高的信息增益。

### 15. 参考文献（References）

- CS229 补充讲义：Hoeffding 不等式。
- David Silver 的强化学习课程第 9 讲：探索与利用。
- Olivier Chapelle 与 Lihong Li 的 "An empirical evaluation of Thompson sampling"（NIPS 2011）。
- Russo 等人的 "A Tutorial on Thompson Sampling"（arXiv:1707.02038, 2017）。

## 原文涉及

- [A Tutorial on Thompson Sampling](<https://arxiv.org/abs/1707.02038>)

---
来源：LearnMap · 学径（https://oplearnx.com）