多臂老虎机与Bandit算法

多臂老虎机（Multi-Armed Bandit, MAB）是强化学习最简化的形式：只有一步决策、没有时序状态转移，却完整呈现了”探索与利用”这一 RL 核心矛盾。本页梳理 ε-greedy、UCB、Thompson Sampling 到 Contextual Bandit 的完整谱系。前置阅读：强化学习概览。

核心直觉

把多臂老虎机想象成走进一家陌生的赌场，面前有 K 台老虎机，每台的获胜概率不同且未知：

利用（Exploitation）= 一直玩目前赢钱最多的那台。短期赚得稳，但如果某台还没充分试过，你可能错过了真正最好的那台。
探索（Exploration）= 每台都多试几次，搞清楚真实概率。信息更全，但试错过程中一直在”浪费”硬币。
ε-greedy= 90% 的时间贪心（玩目前最优的），10% 的时间随机试一台——简单粗暴但有效。
UCB（置信上界）= “乐观面对不确定性”——哪台你试得少、不确定性大，就给它加一个”乐观加分”，优先去探明它。
Thompson Sampling= 给每台装一个”概率信念”，每次从信念分布里采样，选采样值最高的那台——贝叶斯思想，效果通常最好。

与完整 RL 的区别：Bandit 没有状态转移（只有一个”状态”），不关心长期回报，只关心当下这一把的收益；但它是 RL 理论的起点，许多结论（如探索策略）直接推广到完整 MDP（马尔可夫决策过程，MDP，一种用状态、动作、转移概率、奖励来建模序贯决策问题的数学框架）。

数学形式化

问题定义

设有 K 台老虎机（臂），每台臂 a 的奖励服从一个未知分布，其期望为 μ(a)。在每一轮 t = 1, 2, …, T，智能体选择一个臂 a_t，观察到奖励 r_t，目标是最大化 T 轮内的累积奖励：

\text{总奖励} = \sum_{t=1}^{T} r_t

遗憾（Regret）：Bandit 的核心评价指标

因为我们不知道哪台臂最好，所以每一步都可能犯错。遗憾衡量的是”如果我一开始就知道最优臂，能多赚多少”：

R(T) = T \cdot \mu^* - \sum_{t=1}^{T} \mu(a_t)

其中 $\mu^* = \max_a \mu(a)$ 是最优臂的期望奖励。注意遗憾用的是期望奖励 μ(a_t) 而非实际观测的 r_t——因为观测值本身有随机性，我们要衡量的是策略选择上的损失，而非运气好坏。

一个好的 Bandit 算法应该让遗憾随时间亚线性增长——即 $R(T) = O(\sqrt{T})$ 或更优 $R(T) = O(\ln T)$ 。直觉是：随着试玩次数增加，我们对每台臂的估计越来越准，“犯错率”越来越低。

各算法的遗憾界

算法	遗憾界 R(T)	直觉含义
ε-greedy（固定 ε）	$O(\sqrt{T})$	始终以固定比例随机探索，浪费不衰减
ε-greedy（ε 衰减）	$O(\ln T)$	探索率随时间递减，收敛后几乎不浪费
UCB1	$O(\ln T)$	对数遗憾界，渐近最优
Thompson Sampling	$O(\ln T)$	与 UCB 同阶，但常数因子通常更小

Lai & Robbins (1985) 证明了对数遗憾 O(ln T) 是任何策略的理论下界（Lai-Robbins 下界），UCB 和 Thompson Sampling 都达到了这个最优率。

原理图解

三大经典算法的决策逻辑

ε-greedy 靠随机、UCB 靠”不确定性加分”、Thompson Sampling 靠贝叶斯采样，三者殊途同归地平衡探索与利用：

Contextual Bandit：带上下文的 Bandit

当决策前能看到用户/物品的特征（上下文 x）时，问题升级为 Contextual Bandit——推荐系统和广告投放的实际模型：

三大经典算法的数学原理

ε-greedy 的增量更新：维护每臂的经验均值 Q(a)，采用增量式更新避免存储所有历史奖励：

Q(a) \leftarrow Q(a) + \frac{1}{n(a)} \cdot (r - Q(a))

其中 n(a) 是臂 a 被选中的次数。这个增量公式在数值上等价于 $Q(a) = (r_1 + r_2 + \dots + r_n) / n$ ，但只需 O(1) 空间，是强化学习中反复出现的模式。

UCB1 的置信上界：UCB1 选择使以下指标最大的臂：

a_t = \arg\max_a \left[ Q(a) + c \cdot \sqrt{\frac{\ln(t)}{n(a)}} \right]

第一项 Q(a) 是利用——选目前看起来最好的。
第二项 $c \cdot \sqrt{\ln(t) / n(a)}$ 是探索奖励——臂被试得越少（n(a) 小），加分越多；时间 t 越长，ln(t) 增大，迫使所有臂都至少被试一定次数。c 通常取 $\sqrt{2}$ 。
“ln(t)” 保证了算法不会过早停止探索——这是一种数学上的”好奇心机制”。

Thompson Sampling 的贝叶斯更新：对伯努利奖励（0/1），假设每臂的获胜概率 θ_a 的先验为 Beta(1, 1)（均匀分布），每观察到一次奖励后：

\text{奖励 } r = 1: \quad \alpha \leftarrow \alpha + 1 \quad \text{（成功次数加一）}

\text{奖励 } r = 0: \quad \beta \leftarrow \beta + 1 \quad \text{（失败次数加一）}

\text{后验: } \text{Beta}(\alpha, \beta)

每轮从每臂的 Beta(α, β) 中各采样一个 θ，选 θ 最大的臂。直觉是：如果某臂的后验分布很窄（试了很多次），采样值几乎确定在其均值附近；如果后验很宽（试得少），采样值有可能远大于均值，从而被选中去探索。

动手实践

numpy 实现 ε-greedy 与 UCB

一个 10 臂老虎机：每臂真实获胜概率未知，用三种算法（ε-greedy、UCB、Thompson Sampling）在 1000 步内找到最优臂并对比总奖励：

import numpy as np

np.random.seed(42)
K = 10                                    # 老虎机臂数
true_probs = np.random.rand(K)            # 每台真实概率（未知）
T = 1000                                  # 总步数

def bandit_run(algo):
    counts = np.zeros(K)                  # 每台试玩次数
    values = np.zeros(K)                  # 每台经验均值
    successes = np.zeros(K)               # 每台成功（奖励=1）次数，Thompson 采样用
    total_reward = 0
    for t in range(1, T + 1):
        if algo == "epsilon":             # ε-greedy：以 ε 概率随机探索，否则贪心
            epsilon = 0.1
            a = np.random.randint(K) if np.random.rand() < epsilon else np.argmax(values)
        elif algo == "ucb":               # UCB：均值 + 置信上界，试得少的臂有"乐观加分"
            ucb = values + 2.0 * np.sqrt(np.log(t) / (counts + 1e-5))
            a = np.argmax(ucb)
        else:                             # Thompson Sampling：从每臂的 Beta 后验采样
            # Beta(成功+1, 失败+1) 是伯努利奖励的共轭后验，天然平衡探索与利用
            samples = np.random.beta(successes + 1, counts - successes + 1)
            a = np.argmax(samples)
        r = 1.0 if np.random.rand() < true_probs[a] else 0.0  # 拉摇臂
        counts[a] += 1                    # 更新次数
        successes[a] += r                 # 更新成功次数（r 为 0 或 1）
        values[a] += (r - values[a]) / counts[a]  # 增量均值
        total_reward += r
    return total_reward

print("ε-greedy 总奖励:", bandit_run("epsilon"))
print("UCB 总奖励:", bandit_run("ucb"))
print("Thompson 总奖励:", bandit_run("thompson"))
print("真实最优概率:", true_probs.max())
# 三种算法中 Thompson Sampling 通常最快锁定最优臂，总奖励最高

LinUCB：推荐系统的主力算法

LinUCB（线性上置信界）是 Contextual Bandit 最经典的算法，假设奖励是上下文特征的线性函数：

E[r \mid x, a] = \theta_a^{\top} \cdot x

其中 x 是 d 维上下文特征向量（如用户画像），θ_a 是臂 a 的未知参数向量。LinUCB 用岭回归（Ridge Regression）估计 θ_a，并加上一个基于置信椭球的探索项：

\hat{\theta}_a = (X_a^{\top} X_a + \lambda I)^{-1} X_a^{\top} y_a \quad \text{← 岭回归估计}

\text{UCB}(a) = \hat{\theta}_a^{\top} \cdot x + \alpha \cdot \sqrt{x^{\top} (X_a^{\top} X_a + \lambda I)^{-1} x} \quad \text{← 置信上界}

第一项是预测奖励，第二项是不确定性（方差越大说明对该上下文越不确定，给探索加分）。
α 是探索强度超参数，α 越大越偏探索。
每个臂维护独立的 $(X_a^{\top} X_a + \lambda I)$ 矩阵，可用 Sherman-Morrison 公式做 $O(d^2)$ 在线更新，无需重新训练。

LinUCB 的优势在于：可解释（θ_a 直接告诉你哪些特征重要）、高效（线性时间更新）、理论保证（ $O(\sqrt{T})$ 遗憾界）。Yahoo! 2010 年的新闻推荐、Google 的广告系统都用过 LinUCB 的变体。

神经网络 Contextual Bandit（Neural Contextual Bandits）

当奖励与上下文呈复杂非线性关系时，线性假设不够用。NeuralUCB（Zhou et al., NeurIPS 2020）和 NeuralTS（Zhang et al., 2020）用神经网络替代线性回归来估计奖励，探索项则基于网络参数的神经正切核（NTK，Neural Tangent Kernel，描述宽网络训练动力学的高斯过程近似）来量化不确定性。2024-2025 年的研究趋势包括：

Transformer-based Bandit：用注意力机制自动捕获上下文间的时序依赖，适用于用户行为序列场景。
LLM-as-Bandit：直接让大语言模型充当 Bandit 策略——给 LLM 输入历史奖励摘要，由 LLM 推理下一步该探索哪个臂。2024 年的研究表明，LLM 在小规模 Bandit 问题上展现出接近 UCB 的零样本探索能力，但在大规模臂空间下仍需与传统算法结合。
Foundation Model + Bandit：利用预训练模型提取高质量上下文特征（embedding），再用 LinUCB 或 Thompson Sampling 做决策——兼顾表征能力和理论保证。

Bandit 与大语言模型

Bandit 框架与大语言模型（LLM）的对齐训练有着深刻联系，是 2024-2025 年最活跃的研究方向之一。

Best-of-N 采样：最简单的 LLM Bandit

Best-of-N（BoN）是 RLHF 中最基础的对齐方法：对同一个 prompt，从 LLM 中采样 N 个回答，用奖励模型（Reward Model）给每个回答打分，选最好的一个用于训练或直接输出。这本质上就是一个 N 臂 Bandit——每次采样 N 个”臂”（候选回答），观察奖励（模型评分），选最优的。BoN 虽然简单，但至今仍是衡量 RLHF 方法的基线（baseline）。

RLHF 作为 Contextual Bandit

RLHF（基于人类反馈的强化学习，Reinforcement Learning from Human Feedback）的标准流程（InstructGPT / GPT-3.5 / Claude）中的 PPO 阶段，可以重新表述为一个巨大的 Contextual Bandit：

上下文 x = 用户输入的 prompt
动作 a = 模型生成的完整回答
奖励 r = 奖励模型对该回答的评分
策略 π(a|x) = 语言模型的生成分布

与传统 Bandit 不同的是，这里的”动作空间”是所有可能的回答序列，维度极高且离散。这也是为什么 PPO（而非传统 Bandit 算法）成为主流——它能处理如此巨大的动作空间。

RAFT 与 Rejection Sampling：Bandit 式微调

RAFT（Reward rAnked FineTuning，Dong et al., 2023）将 LLM 微调显式地建模为 Bandit 问题：每轮让模型生成一批回答（探索），用奖励模型排序（评估），选高奖励回答做监督微调（利用）。这种”采样-排序-微调”的循环在 2023-2024 年被广泛使用（如 LLaMA-2 的 rejection sampling 微调），因为比 PPO 更简单稳定。

Dueling Bandit 与偏好学习

RLHF 中人类标注者做的是成对比较（“回答 A 和 B 哪个更好？”），而非绝对评分。这恰好对应 Dueling Bandit（对决老虎机）——每轮选择两个臂，只获得相对偏好反馈（哪个更好），而非绝对奖励值。Dueling Bandit 的算法（如 Double Thompson Sampling、RUCB）为偏好学习和 DPO（Direct Preference Optimization，直接偏好优化）提供了理论框架。

实践要点

Thompson Sampling 是默认首选：理论和实验都表明，TS 在大多数场景下优于或等于 UCB 和 ε-greedy，且实现简单（Beta 分布共轭更新），Google、Netflix 的 A/B 测试平台大量采用。
ε 衰减比固定 ε 好：初期多探索（ε=0.3），后期多利用（ε=0.01），能在保证信息量的同时最大化累积收益。
UCB 的 c 值要调：c 越大越偏探索，通常取 2（对应 95% 置信度的理论推导）；若奖励方差大，适当增大 c。
Contextual Bandit 用 LinUCB 起步：当上下文特征维度不高（几十到几百）时，LinUCB 简单高效且可解释；高维或非线性场景再上神经网络策略。
A/B 测试 vs Bandit：传统 A/B 测试是”先纯探索 N 天，再纯利用”——这在 N 天内浪费了大量流量；Bandit 在整个过程中持续平衡探索与利用，累积收益更高，尤其适合短期指标（如点击率）。
奖励信号要即时：Bandit 假设动作后立刻得到奖励；如果奖励有延迟（如用户次日留存），需要设计补偿机制或改用完整 RL。

典型应用

推荐系统冷启动：Netflix 用 Contextual Bandit 为新用户推荐内容，在”推已知热门内容”和”试探新用户偏好”之间自动平衡；字节跳动、快手的推荐召回层也广泛使用 Bandit 变体。
广告投放与竞价：Yahoo! 的新闻推荐、Google 的广告系统在 2010 年代就用 LinUCB 做在线广告选择，比静态规则提升显著点击率。
A/B 测试平台：微软、Google 的实验平台提供”多臂老虎机”模式——逐步把流量从表现差的实验组导向表现好的组，减少实验期间的损失。
临床试验自适应设计：在多治疗组试验中，Bandit 逐步把更多患者分配给疗效更好的组，既符合伦理又加速结论——美国 FDA 已批准相关自适应试验设计。
游戏内测与内容优化：Supercell 等游戏公司用 Bandit 快速测试不同游戏内活动的效果，自动淘汰表现差的活动配置。详见强化学习概览。

典型类库与工具

类库	语言	说明
Vowpal Wabbit	C++/Python	微软赞助的高性能在线学习框架，内置 Contextual Bandit（CB）、LinUCB 等
Contextual	Python	专注于 Contextual Bandit 的开源库，提供多种策略与离线评估工具
MABWiser	Python	轻量级多臂老虎机库，支持 ε-greedy、UCB、Thompson Sampling 等
Bayesian Bandits	Python	极简的贝叶斯 Bandit 实现，适合快速原型
Keras-RL / Stable-Baselines3	Python	通用 RL 库中也包含 Bandit 相关实验接口

术语表

术语	英文	解释
多臂老虎机	Multi-Armed Bandit (MAB)	K 台概率不同的老虎机，目标是在有限步内最大化累积奖励
探索与利用	Exploration vs Exploitation	尝试未知动作以获取信息 vs 重复已知最优动作的权衡
ε-greedy	Epsilon-Greedy	以 ε 概率随机探索、1-ε 概率贪心利用的简单策略
置信上界	Upper Confidence Bound (UCB)	给尝试次数少的臂一个乐观加分，基于”面对不确定性保持乐观”原则
Thompson Sampling	Thompson Sampling	从每臂的后验分布中采样来选择动作的贝叶斯策略
上下文老虎机	Contextual Bandit	每次决策前能看到上下文特征（用户/物品属性）的 Bandit
遗憾	Regret	当前策略累积奖励与最优策略累积奖励的差距，是 Bandit 的核心评价指标
LinUCB	LinUCB	假设奖励是上下文线性函数的 UCB 变体，推荐系统中最常用的 Contextual Bandit
共轭先验	Conjugate Prior	使后验与先验同分布的先验选择，如伯努利似然配 Beta 先验