Bandit：简化成单步决策，本质是主动试错

Bandit（老虎机问题）要解决的，是一类很常见的问题：面前有好几个选择，你每次只能试其中一个，试完只能看到这一个的结果，但你得尽快弄清楚哪个选择最好。

举个生活中的例子：你新搬到一个城市，楼下有好几家饭馆。你每天只能吃一顿晚饭，也就是只能去一家；吃完你只知道这一家好不好吃，没去的那几家好不好吃，你完全不知道。可你又不想天天踩雷，想尽快锁定最好吃的那家。这就是 Bandit。

它比完整的强化学习简单：不用管"状态怎么变"，也不用管"功劳该算给谁"。但简单是有代价的——没选的那个选项，结果永远看不到。所以项目的关键从来不是"要不要试一试"，而是"怎么试才不亏"。

为什么只能看到选中的结果，就必须主动去试？

一次体验，猜不出选项的真正价值

设第 $t$ 轮你选了动作 $A_t$，得到奖励 $R_t$。动作 $a$ 的"真实价值"是

$$ q_*(a)=\mathbb E[R_t\mid A_t=a] $$

公式先放着，用大白话说：真实价值 = "这个选项长期平均能给你多少"。但你在每一轮看到的，只是从它附近随机抽出来的一个数。

比如一家饭馆长期很好吃（真实价值高），但某一天你赶上排队两小时、菜也做糊了，你吃到的那一顿（单次奖励）就很差。广告也一样：某个广告的真实点击率是 5%，但每展示一次，结果要么被点、要么没点，都是碰运气。单次的奖励不是价值本身，只是价值附近的一次随机波动。

十臂测试床这张图把这件事画得很清楚：每个动作都有一个真实的平均水平，但实际奖励会在它附近上下晃。

图注：十个动作，每个都有自己的奖励分布，短横线标出真实均值。同一个动作，单次奖励可能明显偏离均值，所以"一次拿高分"不能证明它就是最好的。RL教材

这也解释了为什么普通的"教机器认图"那一套思路不够用。监督学习会把答案（标签）直接交给模型；Bandit 却只告诉你"你选的那个动作的结果"。没去的饭馆今晚会不会更好吃？没展示的广告会不会被点？日志里根本没有答案。Bandit 每轮只返回所选动作的奖励，这叫部分反馈。Sutton 与 Barto 把"选当前看起来最好的"叫利用，把"故意选个不是最好的、去多收集信息"叫探索。RL教材

遗憾：每轮少赚的那点钱，越积越多

如果每个选项的奖励分布一直不变，最优选项的均值记为 $\mu^*$，你这一轮选的选项均值记为 $\mu_{A_t}$。到第 $T$ 轮为止的"伪遗憾"是

$$ \bar R_T=\mathbb E\left[\sum_{t=1}^{T}(\mu^-\mu_{A_t})\right]=\sum_{t=1}^{T}\mathbb E[\mu^-\mu_{A_t}] $$

遗憾不问你最后一轮猜没猜对，它把"之前每一轮没选最优选项、少赚的那一点"全部加起来记账。设次优选项 $i$ 和最优的差距为 $\Delta_i=\mu^*-\mu_i$，它被选过的次数是 $T_i(T)$，那同一个遗憾也可以写成 $\sum_i\Delta_i\mathbb E[T_i(T)]$。

翻译成人话：去试差的选项，要交学费；过早认定一个错的选项然后一直选它，也要持续交学费。所以遗憾分析必须写清楚两件事：奖励是怎么产生的、跟谁比。随机 Bandit 一般跟"均值最高的固定选项"比，上下文 Bandit 则跟"某个策略家族里最好的策略"比，两者不能只看着数字大小就横着排。遗憾综述

所以，Bandit 难的不是算平均值，而是"没选的选项没有反馈"。你必须先吃点眼前的小亏（选可能不是最好的），才能换来长期少亏。接下来的问题是：能不能比"闭着眼平均乱试"更聪明地花这笔钱？

乱试太浪费，怎么按"有多不确定"来分配探索？

ε-贪心：每轮留一小部分随便试

ε-贪心最简单：每轮有 $1-\epsilon$ 的概率选"目前看起来最好的"（利用），有 $\epsilon$ 的概率随便选一个（探索）。得到奖励后，只更新被你选中的那个选项。如果估计值用样本均值，可以写成增量更新：

$$ Q_{n+1}=Q_n+\frac{1}{n}(R_n-Q_n) $$

好处是写起来简单、调试容易，很适合当项目的地基。坏处也很直接：它的"随便试"不看对象——只试过一次的选项，和已经试了一万次、明显很差的选项，被探索的机会一样多。固定 $\epsilon$ 意味着永远有固定比例的实验对象被拿去瞎试，哪怕各选项的好坏已经很清楚。环境不变时可以让 $\epsilon$ 随时间变小；但奖励会漂移时又不能减太快，这时常用常数步长，让很旧的观测慢慢失去分量。

UCB1：没试够的选项，给它一点"好处费"

UCB1 不搞随机旁路。它先让每个选项都被试一次，然后按这个公式打分：

$$ \operatorname{UCB}_j(t)=\bar X_j+\sqrt{\frac{2\ln t}{N_j}} $$

第一项 $\bar X_j$ 是目前的平均成绩，负责"利用"。第二项是"不确定性的奖励"：$N_j$ 越小（试得越少），这一项越大，负责"探索"。一个选项被反复验证后，第二项会按 $1/\sqrt{N_j}$ 收缩；而总轮数 $t$ 一直在涨，会让很久没碰的选项分数慢慢抬起来，避免某个选项因为早期运气差就被永久放弃。

原论文的伪代码把初始化、打分和循环更新放在了一起。

图注：UCB1 先让每个选项得到一次观测，然后选择"平均成绩 + 信心奖励"总分最高的选项。这张图展示的是选择机制，不是算法性能排名。UCB1

可以把这套分数想成一个"带不确定性说明的评分接口"：输入是一个选项的观测历史，输出不只是预测值，还包括"我还没试够，可能被低估了"的上浮量。平均成绩是估计值，根号项是不确定性声明，选总分最高的就是"乐观决策"。这个类比也暴露了它的失效条件：如果奖励没有上界、均值漂移很快、或者样本根本不是这套置信公式假设的过程，那"上浮量"就不再可信。

Auer、Cesa-Bianchi 与 Fischer 的结果针对"条件均值固定、奖励落在 $[0,1]$"的随机 Bandit。在这些条件下，UCB1 对任意有限时域都有 gap-dependent 的对数期望遗憾上界。公式记不记得住不重要，真正重要的是：别把这条结论直接搬到奖励会漂移、反馈会延迟、或者有状态转移的任务上。UCB1

ε-贪心按固定比例预付探索成本，UCB1 把成本集中到证据不足的选项上。后者更有章法，但需要一个可信的不确定性公式。还有第三条路：不构造上界，而是直接对"未知的世界"抽样。

抽签式探索靠谱吗？怎么对比才算数？

Thompson sampling：在"抽出来的世界"里选最好的

Thompson sampling（汤普森采样）的思路是：对每个选项，心里有一个"它到底有多好"的信念（后验分布）。每轮先从信念里抽一个数，当作"假如这是它的真实水平"，然后选抽出来最大的那个；看到真实结果后，更新信念。它实现的是概率匹配：一个选项有多大概率是真正最好的，就大约有多大比例的机会被选中。

拿点击广告举例，最小实现用 Beta–Bernoulli 模型。第 $i$ 个广告目前被点了 $S_i$ 次、没被点 $F_i$ 次，先验用 $\operatorname{Beta}(\alpha,\beta)$，每轮抽取

$$ \theta_i\sim\operatorname{Beta}(S_i+\alpha,F_i+\beta) $$

然后选 $\theta_i$ 最大的广告。观察结果后，只增加这个广告的 $S_i$ 或 $F_i$。数据少的时候，信念很宽，抽到的数偶尔会特别乐观，等于自动多探索；数据多了，信念变窄，选择自然偏向点击率高的广告。它没有固定的乱试比例，随机性随证据自动变化。Chapelle 与 Li 给出的通用循环就是：抽后验 → 在抽出的世界里贪心 → 观察部分反馈 → 更新选中的臂。TS实证

一个可复现的广告点击最小项目

要比较策略，得让大家共享同一套环境、同一个时长和同一个指标，还要固定随机种子以便复现；如果用共同随机数，应该让各策略面对的环境随机输入保持同步。下面的 NumPy 程序固定三个广告的真实点击率，用累计伪遗憾当指标，跑 100 个随机种子，报告均值和均值的 95% 区间。环境随机数与策略随机数分开，这样算法内部的抽样不会打乱奖励流的随机数顺序。

import numpy as np

CTR = np.array([0.03, 0.04, 0.055])
HORIZON = 10_000
SEEDS = range(100)

def choose(name, t, q, n, success, failure, rng, epsilon=0.1):
    if name == "epsilon":
        if rng.random() < epsilon:
            return rng.integers(len(q))
        return rng.choice(np.flatnonzero(q == q.max()))
    if name == "ucb":
        unseen = np.flatnonzero(n == 0)
        if unseen.size:
            return unseen[0]
        score = q + np.sqrt(2.0 * np.log(t + 1) / n)
        return int(np.argmax(score))
    if name == "thompson":
        samples = rng.beta(success + 1, failure + 1)
        return int(np.argmax(samples))
    raise ValueError(name)

def run(name, seed):
    env_rng = np.random.default_rng(seed)
    policy_rng = np.random.default_rng(seed + 100_000)
    k = len(CTR)
    q = np.zeros(k)
    n = np.zeros(k, dtype=int)
    success = np.zeros(k, dtype=int)
    failure = np.zeros(k, dtype=int)
    regret = 0.0

    for t in range(HORIZON):
        a = choose(name, t, q, n, success, failure, policy_rng)
        reward = int(env_rng.random() < CTR[a])
        regret += CTR.max() - CTR[a]
        n[a] += 1
        q[a] += (reward - q[a]) / n[a]
        success[a] += reward
        failure[a] += 1 - reward
    return regret

for name in ("epsilon", "ucb", "thompson"):
    values = np.array([run(name, seed) for seed in SEEDS])
    half_width = 1.96 * values.std(ddof=1) / np.sqrt(len(values))
    print(f"{name:10s} {values.mean():.2f} ± {half_width:.2f}")

别带着"Thompson sampling 应该最好"的结论再去找曲线证明它。先确认三个实现都只更新被选中的臂；再看结果会不会随 seed 大幅变化；最后改一改点击率间距、时长和先验做敏感性分析。一条轨迹里偶然的几次点击就可能改变早期分流，多个 seed 的区间才是比较的起点。注意：这个模拟器告诉我们所有真实点击率，所以伪遗憾能直接算；真实日志没有这个特权。

Thompson sampling 用"信念"来分配探索，比固定的随机分支更贴合未知结构。但可信的对比来自统一的实验协议和反复运行，而不是一条好看的累计奖励曲线。

没有"对所有人都最好"的选项时，该怎么办？

从"一个最好的"到"看人下菜"

同一个广告，未必对所有人都最好。上下文 Bandit 在做决定前先观察情境 $x_t$（比如用户是谁、什么时段），并为每个候选动作 $a$ 构造联合特征 $x_{t,a}$。学习目标从"找到一个全局最好的选项"变成"学会根据情境选动作"。反馈仍然是 Bandit 式的：只有被展示的那个候选的奖励可见。

disjoint LinUCB 为每个动作单独维护一套线性参数，假设

$$ \mathbb E[r_{t,a}\mid x_{t,a}]=x_{t,a}^{\top}\theta_a^* $$

它对每个候选算两项：预测项 $x^\top\hat\theta_a$ 和不确定性项 $\alpha\sqrt{x^\top A_a^{-1}x}$，选总分最高的动作，然后只更新被选动作的矩阵和向量。候选新闻频繁增删时，新动作可以初始化自己的统计量；hybrid 版本还能通过共享特征在动作之间迁移信息。

下面的算法框展示了这个逐候选的循环。

图注：每轮先读候选特征，为各动作计算线性预测与不确定性奖励，选分数最高的动作；观察奖励后只更新被选动作。该图对应 disjoint LinUCB，不包含长期价值或 hybrid 共享参数。LinUCB

Li 等人在 Yahoo! 新闻场景中，把上下文、动态候选集、点击和部分反馈放进同一个闭环。这个案例证明的是"上下文推荐怎么建模、怎么评估"，不是"点击等于用户的长期价值"。即时点击只是一种代理奖励——如果它和留存、内容质量或多样性对不上，LinUCB 只会更高效地去优化一个错误的目标。LinUCB

不同场景，"奖励"的含义不一样

移动健康把边界暴露得更尖锐。Lei 等人的稿件把即时干预写成上下文 Bandit，并用模拟研究随机策略与用户负担。当一次推送会提高未来的脱离、疲劳或"别再打扰我"的程度时，动作已经改变了后续情境，单步目标会忽略这种延迟后果；在那个模拟里，所得策略的长期平均成本劣于最优策略。该工作提供方法、理想假设下的理论分析和数值模拟，但没有真实临床验证，因此不能当作临床有效或安全的证据。移动健康

上下文 Bandit 的核心是"看当下情境选动作、从部分反馈学习"，而不是找一个固定的全局最佳选项。场景风险越高，越要检查：即时奖励是不是只是个很窄的替身？动作是不是已经开始改变未来？

数据又少、又偏、还过期，结论还能信吗？

旧日志不是完整的答案

在线模拟能知道每个选项的真实参数；真实日志通常只有上下文 $x$、已选动作 $a$、观察到的奖励 $r_a$，以及当初的日志策略选这个动作的概率 $p(a\mid x,h)$。新策略如果想选另一个动作，日志里不会凭空出现那个动作的奖励。所以普通测试准确率回答不了"换策略后能值多少"。

工程上，策略学习与离线策略评估 OPE（离线策略评估）应该分开。先看整体模块，再进估计器内部。

图注：流程从 Bandit 数据进入策略学习，再进入 OPE 和 OPE 准确性评估。它只说明工程模块关系，不展示 DM、IPS 或 DR 的公式。OBP

三种估计器，各说一种思路。DM（直接法）用奖励模型预测目标动作的收益，方差较低，但数据没覆盖到的地方只能靠模型瞎猜。IPS（逆倾向评分）只把"日志动作 = 目标动作"的那些样本算进来，再除以日志选它的概率；倾向正确时能校正选择比例，但小概率动作会产生极端权重。DR（双重稳健估计）把两者合起来：

$$ \hat\rho_{\pi(x)}(x)+ \frac{\mathbb I[\pi(x)=a]}{\hat p(a\mid x,h)} \left(r_a-\hat\rho_a(x)\right) $$

大白话：先用奖励模型打个底，遇到"日志动作 = 目标动作"的样本，再用逆倾向加权去修正残差。所谓"双重稳健"是有严格条件的：奖励模型对、或者倾向模型对，就能消掉相应的偏差；两个都错，偏差一般不会消失。还有一条硬约束：目标策略要选的动作，必须在日志策略下有正概率出现过。一个动作从没出现过，再强的估计器也不能从日志里变出它的结果。Dudík、Langford 与 Li 的分析还要求用于求值的样本与固定的辅助模型满足相应的独立性设置。DR

数据过期、查答案要钱、新用户没数据：三种不一样的问题

日志偏差解决之后，环境还可能继续变。如果奖励均值漂移，旧数据会过期；如果查看奖励本身要花钱，策略还得决定什么时候去查。2025 年的 Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits 用变化预算约束各臂均值的总漂移，并给定总查询预算，目标改成和"每轮当时的最优臂"比动态遗憾。HyQue 把查询轮里的学习、查询分配和变化检测组合起来，但理论上界只覆盖论文给出的预算与变化范围，不能当成任意生产环境的通用升级。HyQue

这张流程图适合观察"选哪个动作"之外新增的查询决策。

图注：查询轮中的非平稳 Bandit 学习与查询分配两条流程，共同汇入总体动态遗憾分析。图中流程不表示该方法适用于任意查询预算，也不代表已在生产系统验证。HyQue

冷启动是另一条轴。2026 年预印本 Bootstrap-Conditioned Action Selection with Tabular Foundation Models 冻结表格 ICL 模型，每轮对历史交互做有放回 bootstrap，再用同一份重采样历史给所有动作评分。随机性来自历史重采样，它不等于精确后验，也不等于分类器的 softmax 概率。论文实验限于分类数据转成的上下文 Bandit，也明确承认存在预训练归纳偏置错配、重复条件化计算开销和固定表示等限制。BC-ICL

这三类问题不能混成一句"换个更大的模型"。OPE 处理"历史选择造成的偏差"，非平稳方法处理"数据过期"，冷启动方法利用表示或先验减少早期对样本的需求。任何方法都无法自动补回日志里从没出现过的动作结果。

环境会"记住"你的动作后，Bandit 还够用吗？

动作会改变未来，评价标准就变了

普通上下文 Bandit 可以看到很丰富的 $x_t$，甚至用神经网络打分，但它仍把每轮当成单步决策。MDP（马尔可夫决策过程）多了一个关键闭环：agent 在状态 $S_t$ 选动作 $A_t$，环境返回奖励 $R_{t+1}$ 和下一个状态 $S_{t+1}$。当前动作会改变未来会遇到的状态，评价对象因而从 $q_(a)$ 或即时 $q_(x,a)$，变成包含未来奖励的状态动作价值。

图注：Agent 向 Environment 发送动作，环境返回下一时刻的奖励和状态，二者进入下一轮形成闭环。与单步 Bandit 相比，新增的下一状态意味着当前动作要对未来负责。RL教材

可以把 Bandit 看作把决策时长截成 1 步，但这不要求必须显式建模世界。对应关系很明确：Bandit 只评价本轮动作的即时奖励；MDP 保留 $S_t\to A_t\to S_{t+1}$ 的状态后果；回报 $G_t$ 再把后续奖励算进当前动作的价值。model-free RL 也可以在不显式预测环境的情况下学长期价值，所以"步数大于 1"和"必须有 world model"不是一回事。

移动健康里的干预负担是一个具体判例。如果今天多推一条消息，只改变本轮那一下的近端奖励，上下文 Bandit 可能够用；如果它让用户明天更容易关掉通知，动作就已经改变了未来状态。推荐系统也类似：一次推荐若显著塑造后续的兴趣、库存或创作者供给，只优化本轮点击就会漏掉序列后果。

换更大的模型，也不能自动解决探索

把线性奖励模型换成深网，问题可能仍然只是上下文 Bandit。Deep Bayesian Bandits Showdown 把多种近似后验接进同一个 Thompson sampling 外循环，指出在线的不确定性估计会反过来决定后续采到什么数据。一个静态预测误差还行、但后验收敛慢的模型，可能因为早期错误而一直选偏斜的动作。NeuralLinear 因而把表示学习和可解析更新的贝叶斯线性头分开。论文的实验没有状态转移或延迟回报，所以它说明的是"深度上下文 Bandit 的探索风险"，不是完整深度 RL 的性能结论。深度Bandit

选型时先问两个问题

先问两个问题。第一，当前动作会不会系统地改变下一个状态？第二，当前动作要不要为"改变未来状态后产生的多步回报"负责？只要有一个答案是"是"，普通 Bandit 通常就不够了；如果只是单步奖励晚到，仍可以先考虑延迟反馈 Bandit。两个都是"否"，再根据上下文、漂移、反馈成本和安全约束去选具体变体。

做项目原型时，先从"能被验证的最小抽象"开始。Bandit 够用时，它能用更少的状态假设换来一个清楚的在线学习闭环；一旦环境会记住动作，继续坚持单步抽象就不是简化，而是漏掉因果后果。模型用了上下文或神经网络，并不能改变这条边界：是"动作对未来状态的影响"以及由此产生的多步信用分配，才会把问题推进到完整强化学习；单步奖励晚到不必然如此。

参考文献

本专题引用的核心资料如下，建议深入学习时阅读原文：

1. Reinforcement Learning: An Introduction, Second Edition — 官方书页
2. Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems — arXiv:1204.5721
3. Finite-time Analysis of the Multiarmed Bandit Problem — Springer
4. An Empirical Evaluation of Thompson Sampling — NeurIPS Proceedings
5. A Contextual-Bandit Approach to Personalized News Article Recommendation — arXiv:1003.0146
6. Doubly Robust Policy Evaluation and Learning — arXiv:1103.4601
7. An Actor-Critic Contextual Bandit Algorithm for Personalized Mobile Health Interventions — arXiv:1706.09090
8. Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling — arXiv:1802.09127
9. Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits — arXiv:2509.15073
10. Bootstrap-Conditioned Action Selection with Tabular Foundation Models — arXiv:2608.06559