10 台老虎机只敢拉 1 台：bandit 把"试几把"压成 6 行代码

为什么"永远只拉最爱"总会在某台老虎机上输掉？

想象你面前摆着 10 台老虎机，每台老虎机的中奖金额服从一个未知的随机分布。机器 3 平均给你 5 块，机器 7 平均只给 1 块，但你现在并不知道这些数字。你只能一台一台拉，每一次只看到选中那台的奖励。如果永远只拉已知奖励最高的那台，你就再也没机会发现还有一台更高奖励的机器在等你。这个"已知最好的（利用）vs 没见过的（探索）"的张力，就是 bandit 问题最核心的矛盾SuttonBarto。

工业上这种问题无处不在。Yahoo! Today Module 想给每个用户从候选文章里挑一篇展示，每篇文章的点击率未知；广告平台要从几十个候选创意里选一个投放，每个创意的转化率未知；LLM serving 系统要从 11 个候选模型里给一个 prompt 选一个推理模型，每个模型在当前 prompt 上的质量和成本都是未知。它们的共同点是：每次决策只能拿到选中那条动作的反馈，其他选项的真实情况你一无所知。这种"信息严重受限"正是 bandit 区别于完整强化学习的核心。

bandit 的边界恰恰是它有用的地方。Sutton-Barto 在《Reinforcement Learning: An Introduction》第 2.9 节明确划了一条线：如果动作只影响当前奖励，那就是 bandit 问题；如果动作会影响下一时刻的状态（就像下棋时下错一步会改变后续棋局），那就进入了完整强化学习（MDP）的领域。这条边界让 bandit 成为强化学习的入门切入口——它把所有探索-利用的核心机制剥到最干净，让你可以集中精力理解算法本身，而不是陷入状态转移和长期信用分配的复杂度SuttonBarto。

看下面这张 Sutton-Barto 教材里 10-armed testbed 的可视化图，每个动作的奖励分布都不一样，有的均值高、有噪声大、有的均值低且稳定。

图注：横轴是 Action 1 到 10，纵轴是奖励分布密度；每个灰色提琴形代表一台老虎机的奖励分布，黑色短线标注它的真实均值 q*(a)；10 台机器各有各的脾气。SuttonBarto。

这就是 bandit 模拟器的标准玩具。在 1000 步内把一个策略跑完，画出累积奖励或 regret 曲线，比较哪个策略在这个静态分布下跑得更好。Sutton-Barto 在 Figure 2.2 上显示了一个反直觉的事实：完全贪婪（永远只拉已知均值最高的）会在大约 33% 的问题实例里永远卡在次优动作——因为它在第一次偶然选到次优机器后就会觉得它不如最优机器，从此再也不碰。而 ε-Greedy（每步以小概率 ε 随机探索）则用线性差距的常数项 regret 保证每台机器被无限次采样到，最终所有估计值都收敛到真实均值SuttonBarto。这个常数项代价就是"浪费在探索上的奖励"——它永远不会消失，但能换来对最优动作的逐步识别。

衡量的统一尺度是 regret。regret = 在 T 步里"事先知道最优臂并永远拉它能拿到的累积奖励"减去"你的算法实际拿到的累积奖励"。它回答的问题是：你的算法比"上帝视角的最优策略"亏了多少。ε-Greedy 的 regret 是 O(K · T · ε)，线性增长；UCB 与 Thompson Sampling 在静态随机（stochastic）环境下能做到 O(log T) 量级，这是 stochastic bandit 的对数渐近率，远好于朴素探索；而在对抗设定（adversarial bandit）下，即使最优算法也只能做到 O(√T)。这个对数增长 vs 线性增长的差距，就是后续 UCB 系列改进的对照基准。

理解 k-armed bandit 之后，下一章要回答的问题是：同样面对这台 10 台老虎机，ε-Greedy、UCB、Thompson Sampling 三种经典算法到底各自在想什么、凭什么做出不同的选择？

三种"谁去试"的工程直觉：ε-Greedy、UCB、Thompson Sampling

面对 10 台老虎机，"探索"这件事可以被编进完全不同的位置。ε-Greedy 编在一个超参数 ε 里，UCB 编在 confidence bonus 项里，Thompson Sampling 编在每次抽样的随机性里。三种思路给出三种截然不同的行为。

ε-Greedy：朴素到极致。以 1-ε 的概率选当前均值最高的动作，以 ε 的概率随机选一个动作。直觉上这就像"每周固定一天随机选一家新餐厅吃饭"——简单、能保证遍历所有动作，但常数项探索代价大。Sutton-Barto Figure 2.2 显示，greedy 收敛到平均奖励约 1.0（明显卡在次优，最优约 1.55），ε=0.1 选择最优动作的频率不超过 91%，因此其平均奖励高于 greedy 但受持续随机探索拖累；ε=0.01 在长程上更优但收敛慢。工程上的经验法则是：先大后小，按 schedule 衰减 ε，平衡早期探索和后期利用。

UCB：均值 + 不确定性联合打分。Auer、Cesa-Bianchi 和 Fischer 在 2002 年的论文里给出了第一个有限时（finite-time）上界——不是渐近而是任意步数都成立。他们的关键公式是 UCB1 索引：对每个臂 j 计算 $\bar{x}_j + \sqrt{\frac{2 \ln n}{n_j}}$，选最大的那个动作Auer2002。前一项是经验均值（利用），后一项是置信区间宽度（探索）。直观解释：你对一个臂越没把握（样本少），后一项就越大，算法就越倾向于去碰它。

看下面这张 Sutton-Barto Figure 2.4 的经验曲线：

图注：横轴是步数 1 到 1000，纵轴是平均奖励；蓝色锯齿线是 UCB（c=2），灰色锯齿线是 ε-Greedy（ε=0.1）；UCB 在约 250 步后稳定超过 ε-Greedy，差距持续到 1000 步。SuttonBarto

UCB 为什么稳赢？因为它把"探索"这件事编进了每个动作的分数里——一台老虎机被拉得越少，它的 confidence bonus 越大，迟早会被选到。而 ε-Greedy 是在所有动作上"无差别地随机"，包括对明显很差的机器也照 10% 概率硬拉，浪费大。

UCB1 在论文 Figure 1 的伪代码草图长这样：

图注：伪代码草图，Initialization：每台机器先各拉一次；Loop：选使 $\bar{x}_j + \sqrt{2 \ln n / n_j}$ 最大的机器 j；n 是总步数，n_j 是臂 j 被选次数。Auer2002

这个索引式的精妙在于：随着 n 增长（已拉的总次数变多），confidence bonus 的对数项增长很慢；但分母 n_j 让被频繁拉的臂"冷却"下来。Auer 等人证明 UCB1 的期望 regret 上界是 $8 \sum_{i:\mu_i<\mu^*}\frac{\ln n}{\Delta_i}$，对数增长，远好于 ε-Greedy 的线性Auer2002。这个 8 Σ ln n / Δ_i 成了后续三十年 UCB 系列（UCB-V、KL-UCB、MOSS）改进的对照基准——每篇新论文都要跟自己比。

Thompson Sampling：贝叶斯后验采样换天然探索。另一种选择是给每个臂维持一个"我对它的奖励分布有多不确定"的信念。Beta-Bernoulli 共轭先验是最常见的设置：每个臂的成功率 θ_i 服从 Beta(S_i + α, F_i + β) 后验分布，每次决策都对每个臂从这个后验采一个 θ̃_i，选 θ̃_i 最大的那个臂ChapelleLi2011。直觉：采样结果有随机性，对样本少的臂采出的估计容易偏高（后验方差大），自然倾向被选到——这正是"把探索编进每次抽样的随机性"。

Chapelle 和 Li 在 2011 年用 Yahoo! 的真实流量做了工业级实证：在 3400 万次随机化推荐事件、7 天的新闻推荐数据上，Thompson Sampling 在 1 小时延迟反馈下显著优于 UCBChapelleLi2011。为什么？因为 TS 是随机的：即便在延迟反馈下选到次优臂，这种"选错"是大量抽样中的小概率事件；而 UCB 是确定性的，会在当前 argmax 上反复下注，一旦 argmax 错了就被套牢。这给了工程读者一个明确启示：在带延迟反馈的真实系统里，TS 比 UCB 更稳。

三种算法的差别本质上不是"谁对谁错"，而是"把探索这件事编进哪一行代码"。ε-Greedy 用一个固定概率 ε 让所有动作平等参与抽奖，浪费在明显差的机器上；UCB 用 confidence bonus 给"被低估的臂"加分；TS 用后验采样的随机性让"不确定性大的臂"天然被频繁试。理解这一点之后，下一章要把这些直觉变成可运行的代码。

可跑的 6 行代码：把三种算法放进同一个 10-armed 模拟器

Sutton-Barto 第 2.4 节给了一个简单 bandit 算法的伪代码模板，全文不到 6 行。我们把这个模板扩展成一个可跑的三算法模拟器，让你今晚就能在自己的机器上看到三种策略在同一 testbed 上的 regret 形态差异。

模拟器的骨架由三件套组成。环境负责生成 10 台老虎机，每台的真实均值 q*(a) 从 N(0,1) 抽样，每次拉它的奖励从 N(q*(a), 1) 抽样。Agent 负责实现策略逻辑：维护每个臂的拉动次数 N[a] 和均值估计 Q[a]，按算法选择动作并更新参数。Runner 把环境与 Agent 串起来，按 Sutton-Barto 的增量更新公式 $Q \leftarrow Q + \frac{1}{n}(R - Q)$ 更新。

import numpy as np

class TenArmedBandit:
    def __init__(self, k=10):
        self.q_true = np.random.normal(0, 1, k)
    def pull(self, a):
        return np.random.normal(self.q_true[a], 1)

class EpsilonGreedyAgent:
    def __init__(self, k, eps=0.1):
        self.Q = np.zeros(k); self.N = np.zeros(k); self.eps = eps
    def select(self):
        if np.random.rand() < self.eps:
            return np.random.randint(len(self.Q))
        return np.argmax(self.Q)
    def update(self, a, r):
        self.N[a] += 1
        self.Q[a] += (r - self.Q[a]) / self.N[a]

class UCBAgent:
    def __init__(self, k, c=2):
        self.Q = np.zeros(k); self.N = np.zeros(k); self.c = c; self.t = 0
    def select(self):
        self.t += 1
        for a in range(len(self.Q)):
            if self.N[a] == 0: return a
        bonus = self.c * np.sqrt(np.log(self.t) / self.N)
        return np.argmax(self.Q + bonus)
    def update(self, a, r):
        self.N[a] += 1
        self.Q[a] += (r - self.Q[a]) / self.N[a]

class ThompsonAgent:
    def __init__(self, k):
        self.S = np.zeros(k); self.F = np.zeros(k)
    def select(self):
        theta = np.random.beta(self.S + 1, self.F + 1)
        return np.argmax(theta)
    def update(self, a, r):
        if r > 0: self.S[a] += 1
        else: self.F[a] += 1

def run(agent, env, steps=1000):
    regret_curve = []
    optimal_a = np.argmax(env.q_true)
    cum_regret = 0
    for t in range(steps):
        a = agent.select()
        r = env.pull(a)
        agent.update(a, r)
        cum_regret += env.q_true[optimal_a] - env.q_true[a]
        regret_curve.append(cum_regret)
    return regret_curve

这段代码完整覆盖了 Sutton-Barto 第 2.4 节的核心要素。EpsilonGreedyAgent 走的是"先均值判断再小概率随机"的朴素路径。UCBAgent 实现的是 Sutton-Barto 2.7 节介绍的 UCB1 形式（c 在 sqrt 外的 $Q[a] + c \cdot \sqrt{\ln t / N[a]}$），c=2 与 Sutton-Barto fig 2.4 一致；该算法源自 Auer-Cesa-Bianchi-Fischer 2002 论文 Figure 1 / Theorem 1（Auer 的字面公式为 $\bar{x}_j + \sqrt{2 \ln n / n_j}$，常数 2 在 sqrt 内）——两种形式算法归属相同，但代码采用 c 外置的参数化形式而非 Auer 论文字面公式Auer2002。ThompsonAgent 走的是 Chapelle-Li 2011 实证过的 Beta-Bernoulli 后验采样路径：每次采样按后验 Beta(S[a]+1, F[a]+1) 给每个臂抽一个估计，选最大的那个拉ChapelleLi2011。

跑完 2000 个随机生成的 testbed、每个跑 1000 步后，把三种算法的累积 regret 画在同一张图上：ε-Greedy 是一条稳定上升的直线（常数项探索代价），UCB 在早期因为强制遍历每个臂而有一波小跳跃、之后增速放缓（对数增长），Thompson Sampling 在小样本时波动大（每次采样的随机性）但长程收敛稳。

这个模拟器是你这个工具的最小可用版本。后面的所有工程应用——推荐系统、广告投放、LLM 路由——都可以看作是在这个模板上换环境、换奖励分布、换上下文。下一章就要做这件事：怎么判断你自己的项目能塞进这个框架？

怎么判断你的项目能塞进多臂老虎机？四元组 + 判别清单

业务问题能不能用 bandit 解，关键看能不能把它映射成四个槽位：臂、奖励、上下文、时间步。Li、Chu、Langford、Schapire 在 2010 年 WWW 上发表的 Yahoo! Today Module 工作是第一次把这套抽象在工业级流量上跑通的范式LinUCB2010。

四个槽位的含义非常具体：

• 臂（Arm） = 一次决策的候选动作。在 Yahoo! Today Module 里就是候选文章池 A_t 里每一篇文章；在广告投放里就是每一个创意；在 LLM 路由里就是每一个候选大模型。
• 奖励（Reward） = 选中那条动作后观察到的标量信号。在推荐里就是用户是否点击（0/1）；在广告里就是是否转化；在 LLM 路由里就是质量分减去成本。
• 上下文（Context） = 决策时可用的特征向量。在推荐里是用户特征 + 文章特征；在 LLM 路由里是 prompt 编码 + 用户偏好向量。LinUCB 把上下文 x_{t,a} 喂进期望 reward 的线性假设 E[r_{t,a}|x_{t,a}] = x_{t,a}^T θ_a*，得到闭式解LinUCB2010。
• 时间步（Time step） = 一次决策的边界。每次用户访问、每次请求、每次广告曝光都是一个时间步。

把这四槽对完一遍，你立刻会撞到四个判别问题。能用 bandit 解的项目都得满足：

1. 奖励是秒级反馈吗？如果是分钟级甚至小时级（如新闻点击反馈延迟），bandit 还能用但要小心 UCB 的确定性下注被套牢，Thompson Sampling 更稳ChapelleLi2011。
2. 奖励可以被定义成一个标量吗？多目标场景（如既要高分又要低成本）需要加权或 Pareto 前沿，BaRP 的 preference vector 就是为此设计BaRP2025。
3. 臂数是有限的吗？臂数过大（几万以上）会让标准 LinUCB 跑不动，需要用 Lipschitz 共享学习器（如 bayesianbandits 库的 LipschitzContextualAgentBayesianBandits2026）或稀疏建模。
4. 上下文是可用的吗？没有上下文就退化成标准 k-armed bandit，仍然可用但失去对不同 context 自适应的能力。

这四个判别问题的"是/否"决定了你的项目该不该走 bandit 路线。

来看 Yahoo! 在 2010 年前后遇到的真实问题：Today Module 每天要给上千万用户展示"你可能感兴趣的文章"模块，每位用户访问时从几百到几千篇候选文章里挑一篇展示。这件事难在三处——其一，每篇文章的真实点击率事先不知道（内容是新鲜的、用户口味在变），bandit 的核心假设恰好命中；其二，反馈是延迟的（用户点不点要等几秒到几分钟），且只观察被展示那一篇的反馈，没展示的完全没数据；其三，用户兴趣差异巨大——同篇文章给一个体育迷和一个宝妈看，点击率可能差一个数量级，必须用上下文把不同用户分开处理。Yahoo! 团队为这件事准备的实验素材是：33M 条随机化推荐事件、1193 维用户特征、83 维文章特征，并先用 K-means 把用户聚成 5 个群体（segment）以便观察群体级别的偏好迁移。下面这张图展示了用户对所属最大 segment 的隶属度分布。

图注：横轴是用户对所属最大 segment 的隶属度（0 到 1），纵轴是用户数；分布形态非平凡，部分用户集中在 0.6 到 0.8 之间，说明 5 个 segment 划分是有意义的，少数用户横跨多 segment。LinUCB2010

5 个 segment 不是拍脑袋选出来的——它是 K-means 在 1193 维特征上自动学到的聚类，对应 5 类不同的用户行为偏好。LinUCB 在 Yahoo! 上的最终成绩：相比 ε-Greedy 基线，部署桶取得 12.5% CTR 提升，稀疏用户段（hybrid 变体）最高拿到 27%LinUCB2010。这个数字背后的工程洞察是：当某个用户群体样本很少时，特征维度上的知识迁移是免费的——一个被其他用户验证有效的文章-特征组合，可以直接迁移到这个稀疏用户身上。

更关键的是工程方法论。Yahoo! 团队第一次系统化了"用随机桶流量做 offline bandit 评估"的方法论：把 5% 流量随机分到一个桶里，对桶里的用户展示随机文章（不做任何算法逻辑），这个桶的事件被当作 replay 流，离线评估任何新 bandit 算法LinUCB2010。这意味着你不需要等到真正 A/B test 完才能评估新算法——只要过去有一桶 uniform random 的日志，就能 offline replay。这套方法论是 bandit 在工业里能安全迭代的工程基础。

工程接口方面，一个好的 Python 微框架能把 pull/update 两步抽象成直觉的 API。bayesianbandits 库（MIT 协议，v1.4.0 发布于 2026 年 8 月）就是一个直接能 pip install 跑起来的例子：每个 Agent 由 Learner（后验）和 Policy（选臂策略）组成，user-facing loop 就两个调用——agent.pull(context) 选臂，agent.update(context, reward) 反馈奖励BayesianBandits2026。Thompson Sampling、UCB、ε-Greedy、Bayesian UCB、EXP3A 几个经典策略都内置，ContextualAgent 支持 LinUCB，LipschitzContextualAgent 用一个共享 learner 覆盖 100+ 个臂。

映射四元组和判别清单不是抽象定义，是上线 bandit 系统的接口设计清单。你今晚就能在自己的项目里按这四个槽位对一遍：能填满就是 bandit 能解的项目，跑 bayesianbandits 跑起来就能拿到 baseline。下一章要沿着 contextual bandit → LLM 路由这条 2025-2026 工业前沿验证它真的在 production 上跑赢。

从 LinUCB 到 LLM 路由：2025-2026 的 contextual bandit 工程三角

2010 年的 Yahoo! LinUCB 范式在 2025-2026 年被推到 LLM serving 这个新场景，产生了三个代表性工作：BaRP 走算法范式，ParetoBandit 走系统级运维，CABS-D 走算法鲁棒性。它们都建在同一个核心论点之上：路由决策是 single-step 即时反馈，bandit 的假设恰好命中。

BaRP：把多目标偏好编进 bandit 反馈训练。Wei 等人 2025 年 10 月发的 BaRP 论文（arXiv 2510.07429）解决了一个具体痛点：现有 LLM router（RouterDC、GraphRouter）都是离线 full-information 监督——训练时能看到所有候选 LLM 的标签，但部署时只能看到被选中的那一个模型的反馈，这就是 bandit feedbackBaRP2025。train/test 失配导致这些 router 没法继续在线学习。BaRP 的修正式是：训练时也模拟 bandit environment，对每个训练样本按当前 policy 采样一个动作 a_t，只用 a_t 的 (q_t, c_t) 计算奖励 r_t，再做 policy gradient 更新。

看下面 BaRP 的训练管线图：

图注：左侧 Query x_t + Preference w_t 双输入汇入 Router；Router 选一个 LLM 推理；反馈路径 Score q_t + Cost c_t 计算 Reward r_t = w^q q_t − w^c c̃_t；底部标注 learning algorithm 通道（policy gradient / LinUCB / Thompson Sampling / ε-greedy 多选项）。BaRP2025

这张图的标准 contextual bandit 闭环长得很像 LinUCB，但多了 preference 向量 w_t = (w^q, w^c) 这个旋钮。算子想在"高分高价 vs 低分低价"之间调整时，调一个数字 w^c 就行，不用 retraining 模型。在 RouterBench 上的实证：把 w^c 从 0.2 调到 0.8，平均成本从 $0.074 单调下降到 $0.015（约 5× 缩减），同时质量分在多数任务上保持平稳BaRP2025。

这里有个来自软件工程领域的类比：feature flag 控制流量切分比例。线上推一个新功能时，不改代码，只是按一个百分比开关把一部分流量切到新路径；想切回老逻辑就把开关拉回原值。BaRP 的 preference knob w^c 在结构上跟这个完全对应：不动模型权重（不改代码），按一个运行时调好的旋钮（feature flag）把 trade-off 曲线（流量比例）平滑调整。算子想重质就调高 w^q，想省钱就调高 w^c，模型本身不用动。

BaRP 在 RouterBench 的整体成绩：in-distribution 5 任务均值 73.57%（超越 Largest LLM 的 70.87% 和 GraphRouter 的 65.42%），同时货币成本相对 GraphRouter 减半BaRP2025。看下面这张 preference knob 的 trade-off 曲线：

图注：左半 Performance Score（0-1），5 任务曲线随 w^c 0.2→0.8 整体平稳；右半 Cost（USD），同样 w^c 区间显著下移（All 平均从 $0.074 到 $0.015）。BaRP2025

调一个旋钮，5× 的成本曲线就走出来了。这就是 multi-objective bandit 在 LLM serving 上跑赢的根本机制。

ParetoBandit：把美元预算编进 Lagrangian pacing。Taberner-Miller 2026 年 4 月发的 ParetoBandit（arXiv 2604.00136）从另一个角度切进同一应用：把"per-request 美元上限"作为硬约束，在 closed-loop 里实时 pacingParetoBandit2026。它的三机制是：

1. Online primal-dual 预算 pacer——每个臂的打分在 UCB 基础上减去 Lagrangian 项 (λ_c + λ_t) · c̃_a，λ_t 按 EMA 平滑后的 dual ascent 更新。
2. 几何遗忘（γ=0.997）——足够长记忆（effective memory 约 333 步）的同时允许模型价格或质量漂移时及时适配。
3. Hot-swap model registry——支持运行时 add_arm / delete_arm 不重启，新模型给 20 步强制探索 burn-in。

看下面这张 stationary 条件下的 quality-cost Pareto frontier：

图注：(a) ParetoBandit 蓝色曲线在三个固定 LLM（Llama/Mistral/Gemini）之间画连续 quality-cost frontier；(b) realized cost vs ceiling 合规带 ±5%；(c) model allocation 从 Llama-dominant（紧预算）到 Gemini-heavy（松预算）的混合切换。ParetoBandit2026

这就是"在一个具体预算下找到最佳质量-成本混合点"的标准答案。固定单模型只能是离散点（每颗星），bandit 用 Lagrangian pacing 在它们之间画了连续曲线。

hot-swap 模型注册表是另一个亮点。看 K=3→K=4 的 cold-start onboarding：

图注：三面板 cold-start Gemini-2.5-Flash selection fraction over time × 4 budget tiers：(a) Good&Cheap → 全部预算采纳；(b) Good&Expensive → BudgetPacer 紧预算抑制；(c) Bad&Cheap → 每个 seed 拒绝。ParetoBandit2026

这里可以用版本控制的工作流来类比。加新模型 = 开一个新 branch；20 步 burn-in = 灰度发布，让新模型在小流量上证明自己；BudgetPacer 决定采纳 = merge 到主分支。三个工程动作在结构上完全对应——开源项目里加新特性必须经过这三步，bandit 系统里加新模型也必须经过这三步，区别在于 bandit 用数据自动化了"merge 决策"这一步。

CABS-D：把 surrogate reward 编进 hedge 解耦。Sridhar 等人 2026 年 7 月发的 CABS-D（arXiv 2607.09015）关心的是另一类鲁棒性：当离线 ML 预测器能给出未选中臂的 surrogate 奖励时，怎么用好这个 side information 而不被它误导CABS-D2026。它的解法是 decouple：把标准 contextual bandit（SquareCB）和 CABS-C 当作两个 expert，用自适应 Hedge 聚合，保证最坏情况自动回退到标准 bandit 速率。

看 CABS-D 的架构图：

图注：左半 LLM routing 任务（context embedding / model pool / cost sensitivity ρ 输入，accuracy-cost trade-off 输出）；右半 CABS-C/CABS-D 在线学习管线，AO（affinity oracle）/ RO（reward oracle）/ RS（regression solver）三 oracle 通道汇入主闭环。CABS-D2026

surrogate 不可信时 R_D 自动退到 R_S = Õ(√(dKT))，surrogate 可信时切到 R_C 加速分支。在三个 LLM routing benchmark（Open LLM LB v2、RouterBench、SPROUT）上的实证：utility 提升 8% / 3% / 1%，低-中-高 cost regime 分别 +15% / +9% / +7%CABS-D2026。看 accuracy-cost Pareto frontier 对比：

图注：三面板（Open LLM LB v2 / RouterBench / SPROUT）linear online models Pareto frontier；CABS-D 曲线在三个数据集上整体落在比 LinUCB / LinTS / ε-greedy 更优的"低成本-高准确率"侧；full-feedback 曲线为 upper bound 标记。CABS-D2026

三件套串成一条线：BaRP 把多目标偏好编进 bandit 反馈（算法范式），ParetoBandit 把美元约束编进 Lagrangian（系统级），CABS-D 把离线 surrogate 编进 hedge（算法鲁棒性）。2025-2026 的 LLM serving 几乎都在 bandit 这条线上，因为路由决策是 single-step 即时反馈，bandit 的假设恰好命中。下一章要划清这条假设的边界——什么时候你必须爬到完整 RL 而不是停在 bandit。

bandit 不能用的那天：状态转移与长期信用分配的边界

读完上面五章，你已经会写 bandit 模拟器、会映射业务问题到四元组、会读 2025-2026 的 LLM 路由三角工作。但有一个根本问题没回答：什么时候 bandit 不够用？

答案藏在 Sutton-Barto 第 2.9 节的最后一段：当前动作只影响即时奖励 → bandit；影响下一状态 → MDPSuttonBarto。具体判别方法：如果你的项目里，下一次决策的可用信息会因为这次决策而改变（比如下棋时下错一步会改变棋盘局面，比如客服对话里这次回答错了用户会带着负面情绪进入下一轮），那 bandit 的无状态假设就不成立。你需要的不是更好的 bandit，而是 MDP 上的完整强化学习（Q-learning、policy gradient、actor-critic）。

bandit 与 RL 的边界之外，还有 bandit 内部的非平稳挑战。现实推荐系统里用户口味在变、广告主出价在变、季节性波动——这些都能用"按 schedule 衰减 α"或"滑动窗口估计"在 bandit 框架内处理，但这是 UCB 的 Sutton-Barto 第 2.5 节就指出过的代价：当 α 不收敛（Robbins-Monro 第二个条件违反）时算法对历史样本的依赖会永远存在，ParetoBandit 的几何遗忘（γ=0.997）是这个方向的工业实现ParetoBandit2026。

如果想继续深入，下一步该读什么？两条主线教材：

Slivkins 2019/2024《Introduction to Multi-Armed Bandits》（Foundations and Trends in ML，arXiv 1904.07272）的 11 章正文按"先 IID → 再 adversarial → 再 structured → 最后 economics"组织Slivkins2019。第 1 章 Stochastic Bandits 巩固前面学的 UCB，第 3 章 Bayesian Bandits 深入 Thompson Sampling 理论，第 8 章 Contextual Bandits 把 LinUCB 推到 Lipschitz / linear / policy class 三个变体。每一章都是一周可教化的自包含单元，是 Sutton-Barto 与 Lattimore-Szepesvári 之间的中间形态。

Lattimore & Szepesvári 2020《Bandit Algorithms》（Cambridge UP，38 章 / 8 Parts）则是现代坐标系BanditAlgorithms2020。Stochastic bandits 在 Ch 6-10（UCB1 / optimism principle 在 Ch 7、KL-UCB 在 Ch 10），Adversarial 在 Ch 11-12（Exp3 / Exp3-IX），Linear Bandits 在 Ch 19，Thompson Sampling 在 Ch 36，MDP 衔接在 Ch 38。如果你需要做论文级的 regret bound 推导，这本书是唯一权威的参考文献。

读完这两本教材之后，你的下一个工程动作很明确：找到你项目里最像"每次只看到选中动作反馈"的子决策，跑一次 bayesianbandits（MIT 协议、pip install 即可BayesianBandits2026），用 β-Bernoulli + Thompson Sampling 当 baseline 跑 1000 步，看累积 reward 是不是比 random / ε-Greedy 显著好。如果是，你的项目就在 bandit 能用的范围内；如果不是，看一眼是不是因为决策之间有状态转移——是的就走 MDP，不是的话调一下臂 / 奖励 / 上下文的定义再跑一次。bandit 不是终点，是完整 RL 的"信息最低位"——读懂它之后你才能判断自己的项目是该停在 bandit 还是必须爬到 MDP。

参考文献

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

1. Sutton & Barto《Reinforcement Learning: An Introduction》(2nd ed., MIT Press 2018) — http://incompleteideas.net/sutton/book/the-book-2nd.html
2. Auer, Cesa-Bianchi, Fischer《Finite-time Analysis of the Multiarmed Bandit Problem》(Machine Learning, 2002) — https://homes.di.unimi.it/~cesabian/Pubblicazioni/ml-02.pdf
3. Chapelle & Li《An Empirical Evaluation of Thompson Sampling》(NIPS 2011) — https://papers.nips.cc/paper/2011/file/e53a0a2978c28872a4505bdb51db06dc-Paper.pdf
4. Slivkins《Introduction to Multi-Armed Bandits》(Foundations and Trends in ML, 2019 / arXiv 2024 rev.) — https://arxiv.org/abs/1904.07272
5. Li, Chu, Langford, Schapire《A Contextual-Bandit Approach to Personalized News Article Recommendation》(WWW 2010) — https://arxiv.org/abs/1003.0146
6. Wei et al.《Learning to Route LLMs from Bandit Feedback》(BaRP, arXiv 2510.07429, 2025-10) — https://arxiv.org/abs/2510.07429
7. Taberner-Miller《ParetoBandit: Budget-Paced Adaptive Routing for Non-Stationary LLM Serving》(arXiv 2604.00136, 2026-04) — https://arxiv.org/abs/2604.00136
8. Lattimore & Szepesvári《Bandit Algorithms》(Cambridge University Press, 2020) — https://www.cambridge.org/core/books/bandit-algorithms/8E39FD004E6CE036680F90DD0C6F09FC
9. Sridhar et al.《Correlation-Aware Contextual Bandits with Surrogate Rewards for LLM Routing》(CABS-D, arXiv 2607.09015, 2026-07) — https://arxiv.org/abs/2607.09015
10. Kulkarni《bayesianbandits: Bayesian Multi-Armed Bandits for Python》(GitHub, 2026-08) — https://github.com/bayesianbandits/bayesianbandits