多臂老虎机

一句话总结 · 要点速览

• 多臂老虎机是只有一个状态的强化学习问题，专门用来研究探索（试新动作）与利用（选当前最好动作）之间的权衡。
• 累积懊悔 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 中都会以 ε-贪心、熵奖励、噪声等形式反复出现。可以先在 老虎机交互工具 里亲手试一试，再阅读下面的分析。

问题形式化

• 动作集合 $\mathcal{A}=\{1,\dots ,K\}$，臂 $k$ 的奖励分布为 ${\nu }_k$，期望为 ${\mu }_k$；
• 最优臂的期望 ${\mu }^{\ast }=\underset{k}{max}{\mu }_k$，臂 $k$ 的差距（gap）为 ${\mathrm{\Delta }}_k={\mu }^{\ast }-{\mu }_k$；
• 第 $t$ 步选择 $A_t$，得到奖励 $R_t\sim {\nu }_{A_t}$。

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

累积懊悔

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

$$\mathcal{R}(T)=T{\mu }^{\ast }-\mathbb{E}\left[\sum _{t=1}^T{R}_t\right]=\sum _k{\mathrm{\Delta }}_k\mathbb{E}[N_k(T)]$$

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

两条重要的参照线：

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

动作价值估计

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

$${\hat{\mu }}_k\leftarrow {\hat{\mu }}_k+\frac{1}{N_k}(R-{\hat{\mu }}_k)$$

ε-贪心

固定 ε

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

衰减 ε

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

$${\epsilon }_t=min(1,\frac{cK}{t})$$

前期几乎完全随机，充分了解各臂；后期探索越来越少。只要 ${\epsilon }_t$ 衰减得不太快（$\sum _t{\epsilon }_t=\mathrm{\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({\mu }_k\ge {\hat{\mu }}_{k,n}+u)\le e^{-2n{u}^2}$$

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

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

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

$$A_t=\arg \underset{k}{max}[{\hat{\mu }}_k+\sqrt{\frac{2\ln t}{N_k}}]$$

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

$$\mathcal{R}(T)=O\left(\sum _{k:{\mathrm{\Delta }}_k>0}\frac{\ln T}{{\mathrm{\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 \underset{k}{max}{\theta }_k$。

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

实验：10 臂伯努利老虎机

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

"""多臂老虎机：比较 ε-贪心（固定 / 衰减 ε）、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}")

实际运行输出（平均累积懊悔 ± 标准误，越小越好）：

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 学习 中 $V\leftarrow V+\alpha (\text{目标}-V)$
ε-贪心 / 衰减 ε	Q-learning 与 DQN 的探索策略
UCB 的乐观探索	乐观初始化、基于计数的探索奖励、MCTS 中的 UCT
汤普森采样的后验采样	Bootstrapped DQN 等“对价值不确定性采样”的探索方法
懊悔	在线学习与探索理论中衡量样本效率的标准指标

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

练习题

1. 证明懊悔分解式 $\mathcal{R}(T)=\sum _k{\mathrm{\Delta }}_k\mathbb{E}[N_k(T)]$。
2. 对固定 ε 的 ε-贪心，写出 $T\to \mathrm{\infty }$ 时懊悔斜率 $\underset{T\to \mathrm{\infty }}{lim}\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）——加入状态与延迟奖励，得到完整的强化学习问题。