有限反馈下的LLM专家在线学习 Online Learning with LLM Experts from Limited Feedback
反馈预算受限时，回溯选取信息增益最大的历史提示获取反馈，实现次线性遗憾的LLM在线路由
前置知识
上下文老虎机（Contextual Bandit）
老虎机问题的扩展：每一轮系统先观察一个上下文向量（本文中是用户提示的嵌入 $x_t$），再从 $K$ 个动作（本文中是 $K$ 个 LLM 专家）中选择一个执行，并获得该动作在该上下文下的随机奖励。由于每轮只观察被选动作的结果，算法必须平衡探索（试探不确定的动作）与利用（选当前估计最优的动作）。经典做法是用线性模型 $\mathbb{E}[r_{t,a}]=\langle\theta_a,x_t\rangle$ 建模奖励并配合置信上界决策。
本文把 LLM 提示路由整个形式化为 $K$ 个专家上的上下文老虎机，两种算法本质上都是线性老虎机算法在有限反馈约束下的变体，不理解这一框架就无法读懂算法设计与遗憾分析。
累积遗憾（Regret）
衡量在线策略优劣的标准指标：$\mathrm{Reg}(T)=\sum_{t=1}^{T}\langle\theta_{a_t^\star},x_t\rangle-\langle\theta_{a_t},x_t\rangle$，即每轮最优专家与实际所选专家的期望奖励之差的累积。若遗憾是次线性的（如 $O(\sqrt{T})$），则平均每轮损失趋于零，说明算法渐近学到了最优路由策略。
论文的全部理论结果（定理3.2、3.3、4.1、4.2）都是遗憾的上界与下界，实验的纵轴也是累积遗憾随轮数的变化曲线，它是贯穿全文的统一评价语言。
线性奖励模型与正则最小二乘（OLS）估计
假设奖励关于上下文线性：$r_{t,a}=\langle\theta_a,x_t\rangle+\eta_{t,a}$，噪声为 1-次高斯（sub-Gaussian）。这对应奖励建模中“冻结的 transformer 嵌入 + 线性头”的标准做法（嵌入不微调）。算法为每个专家维护协方差矩阵 $V_t=\lambda I_d+\sum_s x_sx_s^\top$ 与岭回归估计 $\hat\theta_{t,a}=V_t^{-1}y_{t,a}$，估计误差由以 $\|x\|_{V_t^{-1}}$ 度量的置信椭球刻画。
专家选择规则、置信宽度 $\beta$ 的取值以及所有遗憾证明都建立在该线性模型与 OLS 置信椭球之上；反馈选择准则也通过 $V_t$ 的行列式来定义。
UCB（置信上界）探索原则
面对不确定性时保持乐观：给每个动作估计一个“乐观奖励”，即均值估计加上与不确定性成正比的探索项。线性老虎机中形如 $\langle\hat\theta_a,x_t\rangle+\beta\|x_t\|_{V_a^{-1}}$。某方向上数据越多，$\|x\|_{V^{-1}}$ 越小，探索项自动收缩，从而实现先探索、后利用的自适应切换，无需手工调度。
bandit 设定的算法 LimBanFeed 正是用 UCB 公式选择专家；本文的关键新意是让“不确定性”同时决定第二件事——回溯观察哪一条历史反馈，两者共用同一套置信几何。
信息增益与最优实验设计（G-optimal design）
统计学中的实验设计研究：在测量预算内选哪些数据点能使参数估计最准。对线性模型，信息量由 Fisher 信息矩阵 $V=\sum x x^\top$ 刻画，$\det V$ 越大说明各方向上整体不确定性越小；G-optimal design 使最大预测方差最小，可证明用 $m$ 个精选点能达到 $O(\sqrt{d/m})$ 的最大置信宽度。
本文反馈选择的核心准则就是在未评估的历史提示中挑使 $\det(V+x x^\top)$ 增量最大的那条；论文关于预算 $m$ 最优性的讨论（遗憾对 $m$ 的 $m^{-1/2}$ 依赖不可改进）也直接由 G-optimal design 论证得出。
研究动机
不同 LLM 的成本与能力差异巨大，且没有一个模型在所有提示上都占优。作者用 Nectar 数据集（约 18.3 万条提示，由 GPT-4 担任裁判）量化这一点：GPT-3.5-Turbo、GPT-3.5-Turbo-Instruct、GPT-4、GPT-4-0613、LLaMA-2-7B-Chat、Mistral-7B-Instruct 的胜率分别为 0.182、0.091、0.203、0.319、0.073 和 0.132——没有任何模型的胜率超过三分之一，因此“按提示动态路由到最擅长的模型”有明确收益。但在线部署时存在根本障碍：用户通常不会评价模型响应，奖励天然不可观察；只能通过人工标注或 LLM-as-a-judge（用更强模型当裁判）补充反馈，而这要么耗费人力要么耗费算力，成本还随 token 数量和服务商定价（如 Azure Databricks）浮动，导致反馈次数 $m$ 远小于交互轮数 $T$。现有 LLM 路由工作大多在离线设定下训练路由器，或以“预测各模型对某查询的输出质量”为目标，没有在“反馈本身就是稀缺资源”的硬约束下直接在线优化响应质量；而经典的标签高效（label-efficient）学习理论又只处理无上下文的对抗式设定。
本文的目标是本文的目标可以精确表述为：给定 $K$ 个 LLM 专家和 $T$ 轮交互流，每轮提示嵌入 $x_t$（$\|x_t\|_2\le L$）到达后必须实时选择一个专家生成响应，期望奖励服从线性模型 $\langle\theta_a,x_t\rangle$；算法在整个时间范围内总共只能获得 $m\ll T$ 次反馈（全信息设定下每次反馈是全部 $K$ 个专家的奖励向量，bandit 设定下只是被选中专家的标量奖励），并且可以在事后回溯选择“给哪一条历史提示补反馈”。在此硬预算约束下最小化累积遗憾 $\mathrm{Reg}(T)=\sum_t\langle\theta_{a_t^\star},x_t\rangle-\langle\theta_{a_t},x_t\rangle$。作者刻意把预算建成硬约束而非“奖励减去评估成本”的线性组合，因为反馈的贵在于人力或算力，与响应质量不可通约相减；同时坚持纯在线设定——提示分布未知、逐条顺序到达，离线批量方案不可行。论文为全信息、bandit 两种反馈模式以及非均匀评估成本的扩展分别给出算法和近优遗憾保证。
与已有工作不同的是，本文的独特切入点在于对“有限反馈”的重新刻画：与部分监控（partial monitoring，只能看到被选动作的部分信息）、延迟反馈（延迟不受算法控制）不同，这里算法每轮都能完整执行动作，但自主决定“何时、对哪一轮历史”去换取昂贵反馈——观察的对象和时机都由算法控制。这带来两个此前未被同时研究的设计自由度：一是回溯能力，反馈触发时可以挑选任何未评估过的过去提示；二是预算作为硬约束而非效用函数的一部分。与最接近的 Tucker et al. (2023)（代价高昂的奖励观察）相比，后者把观察成本与奖励直接相减且没有理论分析，不适用于“反馈成本与奖励不可比”的场景。与 LLM 侧的 RouteLLM、MetaLLM、FrugalGPT、Tryage 等相比，它们要么做级联推理、要么离线学习质量预测器，都不做带理论保证的在线反馈获取。论文自我定位为“标签高效学习走进上下文线性世界”，填补 Helmbold & Panizza (1997)、Cesa-Bianchi et al. (2005)（$T\sqrt{\log K/m}$）、Audibert & Bubeck (2010)（$T\sqrt{K\log K/m}$）等无上下文的对抗式结果与随机线性老虎机之间的空白。
核心方法
先说直觉：反馈稀缺，那么每一次花钱买反馈都必须“物有所值”——买回来的信息要尽可能压缩对所有专家参数的不确定性，而不是机械地评估“当下这条提示”。技术上沿用线性奖励建模：提示用冻结的嵌入模型编码为 $x_t$（实验中用 bge-small-en-v1.5 生成 384 维嵌入再经 PCA 降到 40 维），每个专家配一个线性头参数 $\theta_a$，$r_{t,a}=\langle\theta_a,x_t\rangle+\eta_{t,a}$。算法骨架分三层：每轮按当前估计选择专家——全信息设定用贪心均值 $a_t=\arg\max_a\langle\hat\theta_{t-1,a},x_t\rangle$，bandit 设定用置信上界 $\arg\max_a\langle\hat\theta_{t-1,a},x_t\rangle+\beta\|x_t\|_{V_{t-1,a}^{-1}}$；反馈按固定节奏触发（全信息设定每 $T/m$ 轮一次，bandit 设定在每个专家被使用 $z=\lceil T/m\rceil$ 次后触发），平凡保证预算 $m$ 不超支；触发时不评估当前提示，而是回溯在未评估的历史提示中挑行使协方差矩阵行列式增量 $\det(V_{t-1}+x_\ell x_\ell^\top)$ 最大者，购买其奖励并更新统计量。全信息版本 LimFullFeed 一次反馈揭示所有 $K$ 个专家的奖励向量，全体共享一个协方差矩阵；bandit 版本 LimBanFeed 只揭示被选专家的标量奖励，因此为每个专家独立维护 $V_{t,a}$ 与计数器。工程上借助 Sherman-Morrison 公式与矩阵行列式引理把每轮复杂度从 $O(d^3)$ 降到 $O(d^2)$。
核心创新是把“主动学习式的样本选择”嫁接到“bandit 回溯观察”上，形成定时触发、信息贪心的反馈策略，并证明其近优性。与标准线性老虎机的本质区别在于：标准算法每轮用 $x_tx_t^\top$ 更新 $V_t$，误差项 $\log\det(V_t+x_tx_t^\top)-\log\det V_t$ 随时间逐轮伸缩相消（telescoping）；本文的 $V_t$ 只在反馈时刻更新，常规的 self-normalized martingale 论证直接失效。作者的解法极其巧妙：回溯挑选使行列式增量最大的提示，恰好保证在两次反馈之间的任意轮次有 $\log\det(V_t+x_tx_t^\top)-\log\det V_t\le\log\det(V_{t+1})-\log\det V_t$，伸缩求和得以恢复，只是额外乘上区间长度 $T/m$ 的因子，最终遗憾多出 $\sqrt{T/m}$ 型代价。第二个新意是解耦设计：反馈“定时定量”（每 $T/m$ 轮一次）平凡满足硬预算，而“信息贪心”决定买哪个样本，两件事互不干扰、各司其职。bandit 版本进一步按专家分别记账：哪个专家被用得多、其协方差积累的不确定性就增长得快，就为它买反馈——反馈分配与使用频率成正比，既守住总预算又让高频专家先收敛。变成本扩展（Section A）中，评估价为 $z_j$ 的专家每被使用 $z_j\cdot e_z$ 次后才评估一次，即“贵的少评、便宜的多评”。
方法步骤详情
以较复杂的 bandit 版本 LimBanFeed（Algorithm 2）为例逐步描述。输入：专家数 $K$、轮数 $T$、反馈预算 $m$、正则系数 $\lambda$、置信宽度 $\beta$。初始化：每个专家独立维护 $V_{0,a}=\lambda I_d$、累加向量 $y_{0,a}=0_d$、估计 $\hat\theta_{0,a}=0_d$，反馈间隔 $z=\lceil T/m\rceil$，使用计数器 $n_a=0$。每轮 $t$ 执行三步。第一步（路由）：收到提示嵌入 $x_t$，为每个专家计算置信上界并选择 $a_t=\arg\max_a\langle\hat\theta_{t-1,a},x_t\rangle+\beta\|x_t\|_{V_{t-1,a}^{-1}}$，将该专家的响应返回给用户，计数器 $n_{a_t}$ 加一。第二步（按需购买反馈）：若 $n_{a_t}\ge z$，在该专家服务过的所有未评估历史轮中选 $s_t=\arg\max_s\det(V_{t-1,a_t}+x_sx_s^\top)$，向裁判（人工或 LLM judge）购买 $r_{s_t,a_t}$，然后更新 $V_{t,a_t}\leftarrow V_{t-1,a_t}+x_{s_t}x_{s_t}^\top$、$y_{t,a_t}\leftarrow y_{t-1,a_t}+r_{s_t,a_t}x_{s_t}$、$\hat\theta_{t,a_t}=V_{t,a_t}^{-1}y_{t,a_t}$，并把计数器清零。第三步（否则冻结）：所有统计量保持不变。由于每轮恰有一个专家被使用，$\sum_a|S_{T,a}|=T$，故总反馈次数 $\sum_a\lfloor|S_{T,a}|/z\rfloor\le T/z\le m$，预算平凡满足。全信息版本 LimFullFeed（Algorithm 1）是其简化：当 $\lfloor b(t-1)\rfloor<\lfloor bt\rfloor$（$b=m/T$，即约每 $T/m$ 轮）时触发，从全体历史未评估提示中选 $s_t=\arg\max_\ell\det(V_{t-1}+x_\ell x_\ell^\top)$，观察完整奖励向量 $r^{s_t}$ 并同时更新所有专家共享的 $V_t$ 与各 $\hat\theta_{t,a}$。实验中反馈由基准数据集预存的 GPT-4 评估模拟。
技术新颖性
技术新颖性体现在四个层面。第一，新问题设定：这是“由 agent 控制观察什么、何时观察”的上下文线性 bandit，介于全信息与 bandit 之间且带硬预算；此前标签高效学习的结果只在对抗式、无上下文设定下成立，无法直接迁移。第二，新分析技术：遗憾证明必须处理“协方差矩阵非逐轮更新”导致的伸缩求和断裂——作者利用信息贪心选择的性质，把两次反馈之间每轮的 $\log\det$ 增量用一次反馈时的最大增量封顶，再把 $\lceil T/m\rceil$ 的区间长度吸收成 $\sqrt{T/m}$ 因子，完整重建了置信椭球宽度到遗憾的链条。第三，下界构造：用 Bretagnolle–Huber 不等式在 $\{-1,+1\}^d$ 的 Hamming 球上做假设检验，取 $\delta=(md)^{-1/2}$，证明全信息设定遗憾至少 $T\sqrt{d\,e^{-4}/(8\sqrt m)}$，说明遗憾对预算的依赖在 $m=\Theta(T)$ 量级下已近最优；这与“若预知全部提示则可选 $m$ 个 G-optimal 点、遗憾 $O(T\sqrt{d/m})$”的论证互相印证。第四，与线性 bandit 的 lazy 更新看似相似（都是周期性更新模型）但有实质区别：lazy 更新最终利用全部历史观测，而本文只使用 agent 主动挑选的子集，这正是遗憾界中出现 $\sqrt{T/m}$ 代价的根源。整体上算法保持 $O(d^2)$ 每轮复杂度，理论与实现均高效。
实验结果
理论结果：全信息设定下 LimFullFeed 的遗憾为 $O(dTm^{-1/2}\log(TL))$，当 $m=\Omega(T)$ 时退化为 $\tilde O(d\sqrt T)$，与标准线性老虎机一致；下界为 $T\sqrt{d\,e^{-4}/(8\sqrt m)}$，上下界相差约 $\sqrt d$（若提前知道提示序列可消除）。bandit 设定下 LimBanFeed 遗憾为 $O(dTK^{1/2}m^{-1/2}\log(TL))$，多出的 $\sqrt K$ 因为每条反馈的信息量只有全信息的 $1/K$；$m=T$ 时为 $O(d\sqrt{TK}\log(TL))$，下界为 $T\sqrt{K e^{-4}/(8\sqrt m)}$。变成本扩展的遗憾为 $O(dTm^{-1/2}(\sum_j z_j)^{1/2}\log T)$，所有 $z_j=1$ 时退化为 Theorem 4.1。实验在两个基准上进行：RouterBench（约 40.5 万条提示中抽 1 万条，$K=11$ 个模型，bge-small-en-v1.5 嵌入 384 维经 PCA 降到 40 维、保留约 50% 方差，奖励由 GPT-4 判定的最佳模型 one-hot 指示构造）与 Nectar（$K=6$、$d=40$、$T=60000$）。Figure 1（RouterBench）显示 LimFullFeed 全程优于 NoLookBack，且到 $T=60000$ 时差距显著，说明“回溯挑信息增益大的提示买反馈”比“到点就买当前提示”犯的次优决策更少；AllFeedback（每轮都反馈）遗憾和方差都最小，作为性能上界。Figure 2（Nectar）趋势相同。Table 1 给出精确数字：bandit 设定 LimBanFeed 一致更优且优势随 $m$ 扩大——$m=1000$ 时 3583.4±68.0 对 3789.6±30.4，$m=20000$ 时 1567.9±13.4 对 2090.7±21.2（约降 25%）；全信息设定小预算时 NoLookBack 略优（$m=1000$：672.9±37.4 对 631.6±22.1），$m\ge 5000$ 后 LimFullFeed 追平并略优（$m=20000$：73.6±6.0 对 75.8±6.1），作者解释为每条全信息反馈已揭示全部 $K$ 个专家、两者的边际信息差变小。Table 2 验证计算效率：运行时间随 $T$ 线性（LimBanFeed 从 $T=500$ 的 0.41 秒到 $T=15000$ 的 14.35 秒），LimBanFeed 随 $K$ 线性（$K=2$ 的 2.67 秒到 $K=20$ 的 9.97 秒），LimFullFeed 几乎与 $K$ 无关（约 1.5 秒），与共享协方差结构的理论分析吻合。遗憾随 $m$ 增大按 $\sqrt{T/m}$ 速率下降，与理论预测一致。
局限与改进
作者在 Limitations 一节承认两点：其一，回溯反馈假设可以为过去提示补做评估，这要求存储全部历史模型输出，并依赖可能带噪声的人工或 LLM 判断；其二，实验用静态基准模拟在线路由，无法完全刻画非平稳的用户行为与真实部署约束。我自己的观察还有六点。第一，线性奖励假设是硬伤：实验把 384 维嵌入 PCA 压到 40 维且只保留约 50% 方差，说明线性头在低维空间的拟合能力有限，真实质量信号（尤其推理类任务的细粒度差异）很可能非线性。第二，实验的奖励由 GPT-4 的 one-hot 最佳判定构造、再用 OLS 反推 $\theta_a$，裁判即真值，形成了循环依赖，LLM judge 自身的噪声、位置偏差和与人类偏好的一致性都未被建模。第三，bandit 版本按使用频率分配反馈，弱专家因早期不被选中可能长期得不到评估，存在“富者愈富”的冷启动公平性问题。第四，反馈被假设为即时可得，而真实 judge 服务有秒级到小时级的延迟，算法未处理反馈延迟。第五，均匀定时调度只是“平凡可行”的选择，自适应触发（如在不确定性峰值或分布漂移时）可能更优但未被探索。第六，目标函数未纳入各 LLM 的推理成本与延迟差异，而成本感知恰是 LLM 路由应用（MetaLLM、FrugalGPT 等）的核心诉求；Section A 只处理了评估成本不对称，推理成本仍缺席。
独立分析的弱点
弱点一：线性模型表达瓶颈。40 维嵌入加线性头难以刻画提示与模型能力的复杂交互（如代码、数学任务的细粒度差异）；改进方向是换用广义线性或神经网络奖励头（如小型 MLP 配合 ensemble 或频采样不确定性），并研究对应的有限反馈遗憾界。弱点二：平稳性假设。真实流量存在主题漂移与新任务类型，$\theta_a$ 并非恒定；改进方向是引入滑动窗口或折扣因子的遗忘机制，并配合漂移检测在检测到漂移时动态追加反馈预算。弱点三：裁判噪声与偏差。LLM judge 与人类偏好一致率有限，且对冗长、自信的回答有系统性偏好，而本文把反馈当作无偏 sub-Gaussian 观测；改进方向是把 judge 噪声显式建模进方差代理、对关键样本做重复评估降方差，或设计人类与 judge 混合预算、按“每单位预算的信息量”分配。弱点四：bandit 设定的反馈-使用耦合。反馈次数与使用次数成正比，早期表现差的专家会陷入“不被使用→不被评估→无法翻案”的循环；改进方向是设置每个专家的最低评估配额或强制轮转探索（如各保证 $\Omega(\sqrt{T\log K})$ 次使用），或改用 Thompson sampling 缓解过度悲观。弱点五：目标单一。改进方向是把 token 定价与延迟纳入目标函数，做带背包约束的多目标遗憾分析——Section A 的变评估成本框架（ regret $O(dTm^{-1/2}(\sum_j z_j)^{1/2}\log T)$）可以自然延伸为“评估成本+推理成本”双预算。弱点六：理论缺口未闭合。上界中的 $\sqrt d$（union bound 于全空间所致）及 bandit 设定与下界之间的差距仍开放；改进方向是在提示分布各向同性等假设下收紧，或借助在线 G-optimal design 技术消除对未知提示的保守性。
未来方向
作者在结论中明确点名三个方向：动态专家可用性（模型上下线、API 限流）、变化的提示分布（非平稳上下文流）、以及 bandit 设定更紧的下界以改进遗憾最小化策略。基于本文成果还可以延伸出多条路线。其一，异步与批量反馈：真实 LLM judge 服务有延迟且可批量计价，可研究带反馈延迟的有限反馈 bandit，把延迟变量纳入遗憾分析。其二，与级联推理结合：FrugalGPT 式级联关心“便宜模型够不够用”，本文的反馈恰好能在线校准各模型的质量分布，可构建“级联+路由”的在线学习版本，让反馈同时服务于路由与升级判定。其三，动态预算定价：按信息增益的边际价值决定是否花费预算，而非固定每 $T/m$ 轮触发，可借鉴 knapsack bandit 的对偶方法。其四，多裁判体系：不同成本、不同一致性水平的 judge 组合，主动学习“该信谁的判断”，并在遗憾分析中处理裁判间相关噪声。其五，隐式弱信号：在真实部署中用点赞/点踩、复访率、采纳率等稀疏隐式反馈替代显式购买，研究代理遗憾。其六，探索性保证与模型治理：给每个专家最低评估次数以支持“是否下线某模型”的可靠决策，把路由器输出与置信区间一起上报。其七，上下文扩展：多轮对话状态、任务元特征聚类路由，以及把嵌入换成任务自适应编码器。这些方向都不改变本文“反馈是受控稀缺资源”的核心框架，属于自然的外延。
复现评估
复现评估：论文未提供官方开源代码链接（文中未见代码仓库声明），但可复现性整体较好。算法本身是约 30 行伪代码的线性 bandit，只涉及岭回归、行列式增量计算与贪心选择，借助 Sherman-Morrison 公式和矩阵行列式引理每轮 $O(d^2)$，CPU 即可运行——Table 2 显示 Nectar 上 $T=15000$ 全程仅需约 4.5 至 14.4 秒，无需任何 GPU 训练。数据全部公开：RouterBench（约 40.5 万条提示、11 个模型的归一化质量评估，论文抽取 1 万条子集、$K=11$）与 Nectar（GPT-4 裁判的多模型响应数据，实验配置 $K=6$、$d=40$、$T=60000$）；嵌入用开源模型 bge-small-en-v1.5（384 维）加 PCA 至 40 维。两个需要注意的非平凡环节：一是专家参数的构造——附录 D 描述对 1 万×40 的嵌入矩阵与 GPT-4 最佳模型的 one-hot 指示矩阵（1 万×11）做 OLS 得到各 $\theta_a$，这一构造对结果影响较大但论文描述较简略，复现者需自行确认 PCA 方差比例、正则系数 $\lambda$ 等细节；二是论文只说明结果为 5 次运行平均、未公布随机种子与完整超参表。若要迁移到自己的场景，还需自备 LLM judge 预算或用预存评估模拟。总体难度评估为中等偏低：算法与算力门槛都很低，主要工作量在重建数据管线，一台普通机器一天内可完成核心实验。
论文图表