# 多臂老虎机

> 来源：https://dqn.cn/basics/bandit ｜ 作者：DQN.CN 编辑部 ｜ 发布：2026-10-30 ｜ 更新：2026-10-30 ｜ 许可：CC BY-NC-SA 4.0（文字）/ MIT（代码）

> **要点速览**
>
> - 多臂老虎机是只有一个状态的强化学习问题，专门用来研究探索（试新动作）与利用（选当前最好动作）之间的权衡。
> - 累积懊悔 R(T) = Σ_t (μ* − μ_{A_t}) 衡量“因为没选最优臂而少拿的奖励”；任何合理算法的懊悔都至少按 log T 增长（Lai–Robbins 下界）。
> - 固定 ε 的 ε-贪心懊悔随 T 线性增长；让 ε 按 1/t 衰减、UCB1（由 Hoeffding 不等式推导出置信上界）和汤普森采样都能做到亚线性增长。
> - 本站实测（10 臂伯努利、200 次重复、5000 步）：汤普森采样累积懊悔 40.3，衰减 ε 132.9，ε=0.1 为 240.6，UCB1 为 276.4。

在进入马尔可夫决策过程之前，先看一个最简单、却已经包含强化学习核心难题的问题：**多臂老虎机**（multi-armed bandit）。面前有 $K$ 台老虎机（$K$ 个“臂”），每次只能拉一个，拉完得到一个随机奖励；各个臂的奖励分布未知。目标是在 $T$ 次尝试中拿到尽可能多的总奖励。

难点在于：想知道哪个臂好，就得去试（**探索**）；可试的次数越多，花在差臂上的机会也越多，少拿了本该从好臂上拿的奖励（**利用**不足）。这个“探索与利用”（exploration vs. exploitation）的权衡，在后面的 Q-learning、DQN、PPO 中都会以 ε-贪心、熵奖励、噪声等形式反复出现。可以先在 [老虎机交互工具](https://dqn.cn/tools/bandit) 里亲手试一试，再阅读下面的分析。

## 问题形式化

- 动作集合 $\mathcal{A} = \{1, \dots, K\}$，臂 $k$ 的奖励分布为 $\nu_k$，期望为 $\mu_k$；
- 最优臂的期望 $\mu^* = \max_k \mu_k$，臂 $k$ 的**差距**（gap）为 $\Delta_k = \mu^* - \mu_k$；
- 第 $t$ 步选择 $A_t$，得到奖励 $R_t \sim \nu_{A_t}$。

把它放在强化学习的语言里：老虎机就是**只有一个状态**的 MDP，动作不会改变环境，所以不存在“延迟后果”，只剩下“对未知奖励的估计和探索”。

### 累积懊悔

衡量老虎机算法好坏的标准量是**累积懊悔**（cumulative regret）：与“一开始就知道最优臂、一直拉它”相比，少拿了多少期望奖励：

$$
\mathcal{R}(T) = T\mu^* - \mathbb{E}\left[\sum_{t=1}^{T} R_t\right] = \sum_{k} \Delta_k\, \mathbb{E}[N_k(T)]
$$

其中 $N_k(T)$ 是前 $T$ 步中臂 $k$ 被选的次数。第二个等号说明：**懊悔等于“每个差臂被选的次数 × 它的差距”之和**。好的算法应当让差臂被选的次数尽量少，但又不能为零（否则可能永远发现不了自己估计错了）。

两条重要的参照线：

- 只要算法以固定概率随机探索，差臂被选次数就与 $T$ 成正比，懊悔**线性增长** $\mathcal{R}(T) = \Theta(T)$；
- Lai 与 Robbins（1985）证明：对任何在所有问题上都“合理”的算法，懊悔至少按 $\log T$ 增长，常数由各差臂与最优臂奖励分布的 KL 散度决定。能达到 $O(\log T)$ 的算法称为渐近最优（量级上）。

## 动作价值估计

所有方法都要估计每个臂的期望奖励。最简单的是样本均值，可以写成增量形式（和后面 TD 学习的更新式形状完全一样）：

$$
\hat\mu_k \leftarrow \hat\mu_k + \frac{1}{N_k}\left(R - \hat\mu_k\right)
$$

## ε-贪心

### 固定 ε

以概率 $1-\varepsilon$ 选当前估计最好的臂，以概率 $\varepsilon$ 均匀随机选一个臂。实现简单，是 DQN 等算法的默认探索方式。缺点很明显：即使已经非常确定哪个臂最好，每一步仍有 $\varepsilon \cdot \frac{K-1}{K}$ 的概率去拉差臂，所以懊悔线性增长，斜率约为 $\varepsilon \cdot \overline{\Delta}$（$\overline{\Delta}$ 为平均差距）。

### 衰减 ε

让探索率随时间减小，例如

$$
\varepsilon_t = \min\left(1,\ \frac{cK}{t}\right)
$$

前期几乎完全随机，充分了解各臂；后期探索越来越少。只要 $\varepsilon_t$ 衰减得不太快（$\sum_t \varepsilon_t = \infty$，保证每个臂被无限次尝试），估计最终收敛；按 $1/t$ 衰减时随机探索的总次数约为 $cK \ln T$，懊悔变为对数级。代价是需要调参数 $c$：太小会过早“认定”错误的臂，太大则前期浪费。实际训练 DQN 时常用的“从 1 线性降到 0.05”也属于这一类思路。

## UCB：面对不确定性保持乐观

ε-贪心的探索是“盲目”的：随机选臂时，不区分“已经试过很多次、确定很差”的臂和“几乎没试过”的臂。**UCB**（Upper Confidence Bound）的想法是：为每个臂估计一个“真实均值的乐观上界”，然后选上界最大的臂。试得少的臂置信区间宽、上界高，自然会被优先探索；试得多又确实差的臂上界会降下来。

### 从 Hoeffding 不等式推导 UCB1

设奖励在 $[0, 1]$ 内，$\hat\mu_{k,n}$ 是臂 $k$ 的 $n$ 次观测的均值。**Hoeffding 不等式**给出：

$$
\Pr\left(\mu_k \ge \hat\mu_{k,n} + u\right) \le e^{-2 n u^2}
$$

也就是说，真实均值比样本均值高出 $u$ 以上的概率随 $n u^2$ 指数衰减。我们希望这个“上界失效”的概率随时间越来越小，比如取 $\delta_t = t^{-4}$，令 $e^{-2 n u^2} = t^{-4}$，解得

$$
u = \sqrt{\frac{2 \ln t}{n}}
$$

于是得到 **UCB1**（Auer 等，2002）的选择规则：

$$
A_t = \arg\max_k \left[\hat\mu_k + \sqrt{\frac{2 \ln t}{N_k}}\right]
$$

（每个臂先各拉一次，避免 $N_k = 0$。）为什么它的懊悔是对数级？直观推理：差臂 $k$ 一旦被拉了约 $n_k \approx \dfrac{8 \ln T}{\Delta_k^2}$ 次，它的置信半径就小于 $\Delta_k / 2$，此时只要上界没有失效（失效的总概率是可求和的小量），它的上界就低于最优臂的上界，不会再被选中。因此 $\mathbb{E}[N_k(T)] = O\!\left(\dfrac{\ln T}{\Delta_k^2}\right)$，代入懊悔的分解式得到

$$
\mathcal{R}(T) = O\left(\sum_{k:\Delta_k > 0} \frac{\ln T}{\Delta_k}\right)
$$

UCB 的思想后来被推广到树搜索（UCT，AlphaGo 中 MCTS 的选择规则就是它的变体）和深度强化学习中的“基于计数的探索”。

## 汤普森采样

**汤普森采样**（Thompson sampling，1933）走的是贝叶斯路线：为每个臂的均值维护一个后验分布，每一步**从各臂的后验中各采一个样本，选样本最大的臂**，观察到奖励后更新后验。

对伯努利奖励（中或不中），用 Beta 分布作先验最方便，因为 Beta 是伯努利的共轭先验：

- 先验 $\mu_k \sim \text{Beta}(1, 1)$（即均匀分布）；
- 臂 $k$ 中了 $S_k$ 次、没中 $F_k$ 次后，后验为 $\text{Beta}(1 + S_k,\ 1 + F_k)$；
- 每步：对每个 $k$ 采样 $\theta_k \sim \text{Beta}(1 + S_k, 1 + F_k)$，选 $A_t = \arg\max_k \theta_k$。

它等价于“按每个臂是最优臂的后验概率来选它”（probability matching）。不确定的臂后验宽，有机会采到大值而被探索；确定较差的臂后验窄且靠左，几乎不再被选。Agrawal 与 Goyal（2012）证明了它在伯努利老虎机上的懊悔也是对数级，并且常数可以达到 Lai–Robbins 下界。

## 实验：10 臂伯努利老虎机

设置：$K = 10$，每次实验重新抽取各臂中奖概率 $p_k \sim U(0, 1)$；共 200 次独立实验、每次 5000 步，所有方法面对同一批老虎机（固定随机种子）。衰减 ε 取 $c = 5$。

```python
"""多臂老虎机：比较 ε-贪心（固定 / 衰减 ε）、UCB1 与汤普森采样的累积懊悔（regret）。
环境：K=10 臂伯努利老虎机，每次独立实验重新随机抽取各臂的中奖概率 p_k ~ U(0, 1)。
累积懊悔（伪懊悔）：R(T) = Σ_t (p* - p_{a_t})，越小越好。所有实验向量化，一次跑 RUNS 个独立老虎机。"""
import os

import numpy as np

QUICK = os.environ.get("DQN_QUICK") == "1"
K, T, RUNS = 10, (1000 if QUICK else 5000), (50 if QUICK else 200)
SEED = 0

def simulate(choose, rng, p):
    """choose(t, counts, values, wins, rng) -> 每个实验本步要拉的臂（形状 [RUNS]）。返回累积懊悔曲线 [RUNS, T]。"""
    runs = p.shape[0]
    counts = np.zeros((runs, K)); values = np.zeros((runs, K)); wins = np.zeros((runs, K))
    best, regret = p.max(1), np.zeros((runs, T))
    idx = np.arange(runs)
    for t in range(T):
        a = choose(t, counts, values, wins, rng)
        r = (rng.random(runs) < p[idx, a]).astype(float)       # 伯努利奖励
        counts[idx, a] += 1; wins[idx, a] += r
        values[idx, a] += (r - values[idx, a]) / counts[idx, a] # 增量式均值更新
        regret[:, t] = best - p[idx, a]
    return regret.cumsum(1)

def argmax_random_tie(x, rng):
    return (x + 1e-9 * rng.random(x.shape)).argmax(1)           # 随机打破平局

def eps_greedy(eps):
    def choose(t, counts, values, wins, rng):
        explore = rng.random(len(values)) < eps
        return np.where(explore, rng.integers(K, size=len(values)), argmax_random_tie(values, rng))
    return choose

def decaying_eps(c=5.0):
    """ε_t = min(1, c·K / (t+1))：前期大量探索，之后探索率按 1/t 衰减。"""
    def choose(t, counts, values, wins, rng):
        return eps_greedy(min(1.0, c * K / (t + 1)))(t, counts, values, wins, rng)
    return choose

def ucb1(t, counts, values, wins, rng):
    if t < K:                                                   # 先把每个臂各拉一次
        return np.full(len(values), t)
    bonus = np.sqrt(2 * np.log(t + 1) / counts)
    return argmax_random_tie(values + bonus, rng)

def thompson(t, counts, values, wins, rng):
    samples = rng.beta(1 + wins, 1 + counts - wins)             # Beta(1,1) 先验的后验采样
    return samples.argmax(1)

if __name__ == "__main__":
    methods = {
        "ε-贪心 ε=0.01": eps_greedy(0.01),
        "ε-贪心 ε=0.1": eps_greedy(0.1),
        "衰减 ε（c=5）": decaying_eps(5.0),
        "UCB1": ucb1,
        "汤普森采样": thompson,
    }
    p = np.random.default_rng(SEED).random((RUNS, K))           # 所有方法面对同一批老虎机
    checkpoints = [100, 1000, T]
    print(f"K={K} 臂伯努利老虎机，{RUNS} 次独立实验，T={T} 步；表中为平均累积懊悔（± 标准误）")
    for name, fn in methods.items():
        reg = simulate(fn, np.random.default_rng(SEED + 1), p)
        cells = "  ".join(f"T={c}: {reg[:, c - 1].mean():6.1f}±{reg[:, c - 1].std() / np.sqrt(RUNS):4.1f}" for c in checkpoints)
        print(f"{name:14s} {cells}")
```
实际运行输出（平均累积懊悔 ± 标准误，越小越好）：

```text
K=10 臂伯努利老虎机，200 次独立实验，T=5000 步；表中为平均累积懊悔（± 标准误）
ε-贪心 ε=0.01    T=100:   24.8± 1.5  T=1000:  139.0±10.4  T=5000:  250.4±19.1
ε-贪心 ε=0.1     T=100:   17.0± 0.8  T=1000:   67.9± 2.5  T=5000:  240.6± 4.5
衰减 ε（c=5）      T=100:   35.2± 0.6  T=1000:   86.8± 1.5  T=5000:  132.9± 4.0
UCB1           T=100:   27.5± 0.4  T=1000:  130.2± 1.4  T=5000:  276.4± 2.8
汤普森采样          T=100:   13.3± 0.3  T=1000:   28.0± 1.1  T=5000:   40.3± 1.8
```

结果解读：

- **汤普森采样全程最好**，5000 步的累积懊悔只有 40.3，并且从 1000 步到 5000 步只增加了约 12。
- **固定 ε 的懊悔近似线性增长**：ε=0.1 从 1000 步的 67.9 增长到 5000 步的 240.6，每步约多付出 0.043，这正是“永远保留 10% 随机探索”的代价。
- **ε=0.01 探索太少**：标准误很大（±19.1），说明部分实验很早就锁定了一个差臂，长期吃亏。
- **衰减 ε 前期代价最大、后期最省**：前 100 步懊悔 35.2 是所有方法中最高的（几乎全在随机探索），但 5000 步时只有 132.9。
- **UCB1 在这个设置下不如 ε=0.1**，这是一个值得注意的实测现象：UCB1 的置信半径来自较松的 Hoeffding 界，在 $p_k$ 均匀分布、多个臂均值很接近时探索偏多。不过它的增长是亚线性的（1000→5000 步增加约 146，ε=0.1 增加约 173），时间足够长时会反超固定 ε。实践中常用更紧的变体（如 KL-UCB）或把探索系数调小。

## 与完整强化学习的联系

| 老虎机中的概念 | 在后续章节中的对应 |
| --- | --- |
| 样本均值的增量更新 | [TD 学习](https://dqn.cn/basics/td-learning) 中 $V \leftarrow V + \alpha(\text{目标} - V)$ |
| ε-贪心 / 衰减 ε | [Q-learning](https://dqn.cn/basics/q-learning-sarsa) 与 [DQN](https://dqn.cn/advanced/dqn) 的探索策略 |
| UCB 的乐观探索 | 乐观初始化、基于计数的探索奖励、MCTS 中的 UCT |
| 汤普森采样的后验采样 | Bootstrapped DQN 等“对价值不确定性采样”的探索方法 |
| 懊悔 | 在线学习与探索理论中衡量样本效率的标准指标 |

老虎机去掉了“状态”和“延迟奖励”。下一节 [马尔可夫决策过程](https://dqn.cn/basics/mdp) 把这两样加回来：动作会改变状态，今天的选择会影响明天能拿到的奖励。

## 练习题

1. 证明懊悔分解式 $\mathcal{R}(T) = \sum_k \Delta_k\, \mathbb{E}[N_k(T)]$。
2. 对固定 ε 的 ε-贪心，写出 $T \to \infty$ 时懊悔斜率 $\lim_{T\to\infty} \mathcal{R}(T)/T$ 的表达式，并用实验中的数字粗略验证。
3. 在 UCB1 推导中，如果把失效概率取为 $\delta_t = t^{-2}$，置信半径变成什么？修改代码比较两种半径的懊悔。
4. 把奖励改成高斯分布 $\mathcal{N}(\mu_k, 1)$，汤普森采样的先验与后验应当怎样选？实现并与 UCB1 对比。
5. 把衰减 ε 的 $c$ 分别设为 1、5、20，观察前 100 步与 5000 步懊悔的变化，并解释“前期代价”和“后期收益”的权衡。

## 参考文献

- 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.
- Lai, T. L., & Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. *Advances in Applied Mathematics*, 6(1), 4–22.
- Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. *Machine Learning*, 47, 235–256.
- Agrawal, S., & Goyal, N. (2012). Analysis of Thompson sampling for the multi-armed bandit problem. *COLT*.
- Lattimore, T., & Szepesvári, C. (2020). *Bandit Algorithms*. Cambridge University Press.
- Sutton, R. S., & Barto, A. G. (2018). *Reinforcement Learning: An Introduction* (2nd ed.), 第 2 章.

## 下一步

继续阅读：[马尔可夫决策过程（MDP）](https://dqn.cn/basics/mdp)——加入状态与延迟奖励，得到完整的强化学习问题。

## 常见问题速查（FAQ）

**问：多臂老虎机和完整的强化学习问题有什么区别？**

答：老虎机只有一个状态，动作不会改变之后的局面，奖励只取决于当前动作；完整的强化学习（MDP）中动作会影响下一个状态，因此还要处理延迟奖励与信用分配。老虎机把“探索与利用”这一个难点单独拿出来研究。

**问：UCB 的探索项 sqrt(2 ln t / n) 是怎么来的？**

答：由 Hoeffding 不等式：n 次观测的样本均值低估真实均值超过 u 的概率不超过 exp(−2nu²)。令这个概率等于 t^{-4}，解出 u = sqrt(2 ln t / n)，即以很高概率真实均值不超过“样本均值 + u”，于是选上界最大的臂。

**问：汤普森采样为什么效果通常最好？**

答：它按“每个臂是最优臂的后验概率”来分配尝试次数：不确定的臂被采样到较大值的机会多，因而得到探索；确定较差的臂几乎不再被选。它的探索量随证据自动减少，在伯努利老虎机上懊悔可以达到渐近最优的对数级。本站实验中它的累积懊悔最低。

**问：为什么实验里 UCB1 的懊悔比 ε=0.1 还高？**

答：UCB1 的置信半径来自较松的 Hoeffding 界，探索偏保守，在各臂均值较接近时前期探索代价大。但它的懊悔增长是亚线性的：从 1000 步到 5000 步，ε=0.1 的懊悔增加了约 173，UCB1 只增加了约 146，时间更长时 UCB1 会反超固定 ε。

## 如何引用本文

DQN.CN 编辑部. 多臂老虎机[EB/OL]. DQN.CN, 2026-10-30（更新于 2026-10-30）. https://dqn.cn/basics/bandit.