Multi-Armed Bandits with Best-Action Queries¶

会议: NeurIPS 2026
arXiv: 2605.08287
领域: 其他
关键词: 多臂老虎机, 最佳动作查询, 强盗反馈, 遗憾界, 方差感知在线学习

一句话总结¶

本文全面解决了有限次最佳动作查询在强盗反馈下的理论价值：证明了在动作奖励相关或对抗环境下查询无法打破 \(\Omega(\sqrt{T-k})\) 遗憾下界；而在独立同分布（i.i.d.）环境下，提出前期查询配合 UCB-V 的算法成功达到匹配最优的 \(\widetilde{\mathcal{O}}(\min\{Tn/k, \sqrt{n(T-k)}\})\) 遗憾界。

研究背景与动机¶

多臂老虎机（Multi-Armed Bandit, MAB）是刻画不确定性环境下序贯决策与“探索-利用（Exploration-Exploitation）”权衡的经典理论模型，在推荐系统、临床试验、网络路由和计算广告等领域扮演着基石角色。近年来，随着大模型与外部辅助预测系统的兴起，算法如何在有限昂贵资源介入下超越传统极小化极大性能极限成为研究热点。近期 Russo 等人（NeurIPS 2024）提出了带有“最佳动作查询（Best-Action Queries）”的 MAB 拓展模型：算法在总共 \(T\) 轮交互中拥有至多 \(k\) 次向预言机（Oracle）查询当前轮最优臂的预算。在全反馈（Full-Feedback）模型下，他们证明了不论是随机还是对抗环境，\(k\) 次查询均能将遗憾从经典的 \(\widetilde{\mathcal{O}}(\sqrt{T})\) 戏剧性降低至 \(\widetilde{\mathcal{O}}(\min\{T/k, \sqrt{T}\})\)。

然而，全反馈假设与大多数实际应用场景存在严重脱节。在内容审核、个性化医疗干预或高精度商业决策中，决策者通常仅能获得部分反馈（Bandit Feedback）——即只能观测到其实际拉动臂的瞬时收益，未选择动作的潜在收益完全不可知。在缺少反事实收益反馈的前提下，昂贵的最佳动作查询到底具备多大的信息价值？全反馈下获得的次线性加速结论能否平移至强盗反馈设定？这些关键疑问在理论上均未得到解答，构成了该领域悬而未决的核心公开难题。

解决该问题的关键挑战在于强盗反馈下“查询带来的负遗憾收益”与“信息增益对后续探索的指导能力”之间存在深刻的统计学纠缠。本文切入角度是分别解构相关对抗环境与独立同分布环境下信息论下界和收益方差特性的本质差异。核心 idea：通过构建不可区分且严格压制负遗憾增益的相关分布对，证明强盗反馈下相关/对抗环境存在不可逾越的 \(\Omega(\sqrt{T-k})\) 遗憾下界；同时证明在 i.i.d. 环境下高方差必然带来显著的即时负遗憾收益，从而设计出“前期耗尽查询预算 + 后续执行方差感知 UCB-V”的极简匹配算法，彻底闭合强盗反馈下最佳动作查询的理论图景。

方法详解¶

整体框架¶

本文针对 \(n\) 个臂、时间跨度为 \(T\)、配有 \(k\) 次瞬时最佳动作查询预算的强盗反馈博弈，构建了贯穿下界分析与算法设计的统一理论框架。当允许查询时，预言机显式揭示该轮瞬时收益最大臂 \(i_t^\star \in \arg\max_{i \in [n]} X_{t,i}\)，智能体执行该动作并收取对应收益；在无查询轮次中，智能体仅能依据历史局部收益决策。算法框架分为相关环境下的不可行性下界证明，以及独立同分布环境下的“前期均匀查询（Probing Phase）+ 方差感知极小化（UCB-V Phase）”两阶段高效算法。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["环境奖励设定与查询预算<br/>n 臂时界 T，查询上限 k"] --> B{"环境统计依赖性判断"}
    B -->|臂间相关/对抗环境| C["相关构造与紧界分析<br/>信息掩盖构造证明下界 Omega(sqrt(T-k))"]
    B -->|独立同分布 i.i.d. 环境| D["动态静态遗憾分解<br/>动态与静态最优收益差绑定臂方差"]
    D --> E["前期最优动作查询<br/>前 k 轮查询预言机积累负遗憾收益"]
    E --> F["方差感知 UCB-V 学习<br/>后 T-k 轮独立执行方差缩减探索"]
    F --> G["收敛至匹配遗憾界<br/>达到 O(min{Tn/k, sqrt(n(T-k))})"]

关键设计¶

1. 相关构造与紧界分析：对偶实例设计封杀查询信息增益与负遗憾累积

为了在随机相关环境及对抗环境下确立严格的遗憾下界，本文通过构造两组精巧的强相关双臂环境 \(\nu_1\) 与 \(\nu_2\) 建立了严密的信息论障碍。设均匀隐变量 \(W_t \sim \mathrm{Unif}\{1,2\}\)，两臂收益基于基准变量 \(U_t \sim \mathrm{Unif}[0,1]\) 通过非线性可逆形变 \(H_c(x) = x - cx(1-x)\) 映射得到的三元有序序列 \(Y_t < Z_t^- < Z_t^+\)。在实例 \(\nu_1\) 中，当 \(W_t=1\) 时收益向量为 \((Z_t^+, Y_t)\)，当 \(W_t=2\) 时为 \((Z_t^-, Z_t^+)\)；而在 \(\nu_2\) 中两臂结构对调。在此构造下，每轮的最佳臂索引恒为 \(W_t\)。

该设计的绝妙之处在于彻底化解了“查询揭示真实全局最优臂”与“负遗憾累积”之间的双重张力。首先，无论在 \(\nu_1\) 还是 \(\nu_2\) 下，预言机在查询轮返回的最优臂索引分布和对应最大收益 \(Z_t^+\) 的边际分布完全恒等（即两实例在查询轮的 KL 散度严格为零），查询根本无法帮助算法分辨到底哪一个臂具有更高的期望收益；其次，通过令扰动参数 \(\eta = b - a = \Theta(a/k)\)，使得每次查询所能产生的“超额动态收益”（即负遗憾）在期望上被严格限制在 \(\eta/12 = \mathcal{O}(a/k)\)，因此全部 \(k\) 次查询累积的负遗憾至多为常数级 \(\mathcal{O}(a)\)。在剩余的 \(m = T-k\) 个非查询轮次中，观测分布的 KL 散度仅为 \(\mathcal{O}(ma^2)\)。通过令 \(a = \Theta(1/\sqrt{m})\)，应用 Bretagnolle–Huber 不等式与 Yao 极小化极大定理，直接证明了任何算法在相关环境下必须承担至少 \(\Omega(\sqrt{T-k})\) 的遗憾：

\[R_{T,k}(\mathfrak{A}) \geq \frac{\Delta m}{4} \exp\bigl(-D_{\mathrm{KL}}(\mathbb{P}_1 \| \mathbb{P}_2)\bigr) - \frac{\eta k}{6} = \Omega(\sqrt{T-k})\]

2. 动态静态遗憾分解：将预言机单轮超额收益显式链接至臂收益方差

针对独立同分布环境，算法能够取得突破的核心机理在于揭示了“动态最优策略”与“静态最优基准”之间的内生收益差 \(\mathrm{OPT}_{\mathrm{d}} - \mathrm{OPT}_{\mathrm{s}}\)。静态最优基准 \(\mathrm{OPT}_{\mathrm{s}} = \mu^\star = \max_{i} \mathbb{E}[X_i]\) 仅拉动期望收益最高的固定臂，而预言机驱动的动态策略则可在每一轮观测到实际实现值后拉动当前最大收益臂 \(\mathrm{OPT}_{\mathrm{d}} = \mathbb{E}[\max_{i} X_i]\)。算法每执行一次查询，即可无偿获取一份 \(\mathrm{OPT}_{\mathrm{d}} - \mathrm{OPT}_{\mathrm{s}}\) 的即时额外收益。

本文通过分析独立随机变量的绝对差期望，首次建立了该差值与次优臂方差 \(\sigma_i^2\) 及次优差距 \(\Delta_i = \mu^\star - \mu_i\) 之间的理论下界桥梁：

\[\mathrm{OPT}_{\mathrm{d}} - \mathrm{OPT}_{\mathrm{s}} \geq \frac{1}{2n} \sum_{i \in \mathcal{S}} (\sigma_i^2 - \Delta_i)_{+}\]

当面对传统强盗算法最难区分的高方差场景（如 \(\sigma_i^2 = \Theta(1)\) 且 \(\Delta_i = \Theta(1/\sqrt{T})\)）时，每一轮查询均会贡献量级高达 \(\Theta(1/n)\) 的负遗憾，总共 \(k\) 次查询可直接抹除 \(\Theta(k/n)\) 的累积遗憾；反之，若负遗憾贡献极小，则必然要求各臂方差 \(\sigma_i^2\) 接近于 0 或次优差距极大，这直接为后续在线学习提供了极大的方差缩减红利。这一分解公式从数学上完美解释了为何 i.i.d. 设定能打破相关环境的下界壁垒。

3. 前期最优动作查询：在时间序列前端一次性耗尽查询预算

基于上述动态收益分解，本文提出了极为简练但理论严密的查询调度策略。由于在独立同分布环境下各轮奖励分布完全时间同质，将 \(k\) 次查询预算均匀分布、自适应触发或是集中在最开头的 \(k\) 轮消耗，其在数学期望上产生的负遗憾总收益完全相等（恒为 \(-k(\mathrm{OPT}_{\mathrm{d}} - \mathrm{OPT}_{\mathrm{s}})\)）。

因此，算法直接在交互的前 \(k\) 轮（\(t = 1, \dots, k\)）无条件连续向预言机发起查询，直接拉动当轮揭示的最佳臂 \(I_t = i_t^\star\)。更为关键的设计是，算法在此探查阶段结束后完全“遗忘”并丢弃预言机返回的动作标签及其实际观测收益。这一看似激进的丢弃机制保证了后续学习阶段与前期查询数据之间的完全统计独立性，从而允许直接无缝接入无偏的标准在线学习算法，规避了由于适应性过滤导致的极其复杂的后验分布偏差。

4. 方差感知 UCB-V 学习：利用低方差快速收敛实现两极权衡对冲

在消耗完 \(k\) 次查询后的剩余 \(M = T-k\) 轮中，算法从零初始化并执行方差感知在线学习算法 UCB-V。UCB-V 依据每个臂的经验均值与经验方差构建精细置信上界，其对任意次优臂 \(i\) 的期望拉动次数严格受限于其真实方差 \(\sigma_i^2\)：

\[\Delta_i \mathbb{E}[N_i(M)] \leq C \left(\frac{\sigma_i^2}{\Delta_i} + 1\right) \log M\]

将 UCB-V 的理论上界代入整体遗憾分解，结合关键设计 2 中建立的方差下界，次优臂 \(i\) 贡献的有效净遗憾被精确约束为：

\[R_i - \frac{k}{2n} (\sigma_i^2 - \Delta_i)_{+} \leq 2C \log T + \sqrt{C (\sigma_i^2 - \Delta_i)_{+} \mathbb{E}[N_i(M)] \log T} - \frac{k}{2n} (\sigma_i^2 - \Delta_i)_{+}\]

利用基本代数不等式 \(\sqrt{a x} - b x \leq a / (4b)\)，令 \(x = (\sigma_i^2 - \Delta_i)_{+}\)，未知项被完美对消，右端直接转化为 \(\frac{Cn}{2k} \mathbb{E}[N_i(M)] \log T\)。对所有次优臂求和并利用总拉动次数 \(\sum_i \mathbb{E}[N_i(M)] \leq T\)，立即推导出极度紧致的 \(\mathcal{O}(\frac{nT \log T}{k})\) 界；再结合 UCB-V 固有的无分布极小化极大界 \(\mathcal{O}(\sqrt{nT \log T})\)，最终在整体 \(T\) 轮上封闭达成统一的最优速率：

\[R_{T,k}(\mathfrak{A}) \leq \mathcal{O}\left(\min\left\{\frac{nT\log T}{k}, \sqrt{nT\log T}\right\}\right)\]

实验关键数据¶

主实验¶

本文是一篇纯理论论文，其核心贡献在于解决开放理论问题并给出严格的上下界证明。为了系统展现本文结论在各种环境设定下的完整图景，并与全反馈基线及无查询经典设定进行定量对比，下表汇总了不同反馈模型和环境统计特性下的最优可达累积遗憾界（省略对数因子 \(\widetilde{\mathcal{O}}\)）。

环境反馈与统计特性	传统无查询基准 (\(k=0\))	全反馈+最佳查询 (Russo et al., 2024)	本文理论上界 (Ours Upper Bound)	本文理论下界 (Ours Lower Bound)	渐近匹配性
随机独立同分布 (Stoc. i.i.d.)	\(\Theta(\sqrt{nT})\)	\(\widetilde{\mathcal{O}}(\min\{T/k, \sqrt{T}\})\)	\(\widetilde{\mathcal{O}}(\min\{Tn/k, \sqrt{n(T-k)}\})\)	\(\Omega(\min\{Tn/k, \sqrt{n(T-k)}\})\)	严格匹配 (Tight up to \(\log\))
随机臂间相关 (Stoc. Correlated)	\(\Theta(\sqrt{nT})\)	\(\widetilde{\mathcal{O}}(\min\{T/k, \sqrt{T}\})\)	\(\widetilde{\mathcal{O}}(\sqrt{n(T-k)})\)	\(\Omega(\sqrt{T-k})\)	严格匹配 (Tight up to \(\sqrt{n}\))
对抗任意环境 (Adversarial)	\(\Theta(\sqrt{nT})\)	\(\widetilde{\mathcal{O}}(\min\{T/k, \sqrt{T}\})\)	\(\widetilde{\mathcal{O}}(\sqrt{n(T-k)})\)	\(\Omega(\sqrt{T-k})\)	严格匹配 (Tight up to \(\sqrt{n}\))

消融实验¶

为深入理解算法各组成部分在不同方差与差距区间的理论表现，下表对所提出框架的模块剥离、查询分配方式以及底层极小化器的选择进行了理论性质分析与消融对比。

策略与算法配置	对应理论遗憾阶数	在低方差区间的表现 (\(\sigma^2 \to 0\))	在高方差区间的表现 (\(\sigma^2 \to 1/4\))	机制说明
完整模型 (全预算查询 + UCB-V)	\(\widetilde{\mathcal{O}}(\min\{Tn/k, \sqrt{n(T-k)}\})\)	\(\widetilde{\mathcal{O}}(n \log T)\) 极速收敛	依靠负遗憾抹平 \(\Theta(k/n)\) 误差	理论最优，完美对冲高低方差两极态
均匀分散查询 + UCB-V	\(\widetilde{\mathcal{O}}(\min\{Tn/k, \sqrt{n(T-k)}\})\)	\(\widetilde{\mathcal{O}}(n \log T)\) 极速收敛	依靠负遗憾抹平 \(\Theta(k/n)\) 误差	期望收益相同，但引入跨轮调度复杂度
仅查询无方差感知 (前期查询 + UCB1)	\(\mathcal{O}(\sqrt{n(T-k)\log T})\)	退化至 \(\mathcal{O}(\sqrt{nT \log T})\)	无法抵消未知低方差情况下的劣势	无法利用低方差场景，不能达到 \(Tn/k\)
零查询对照组 (\(k=0\) 纯 UCB-V)	\(\mathcal{O}(\sqrt{nT \log T})\)	\(\widetilde{\mathcal{O}}(n \log T)\)	退化至最坏情况 \(\mathcal{O}(\sqrt{nT})\)	缺失查询红利，无法超越 \(\sqrt{T}\) 界
纯贪心查询 (遇疑即问)	\(\Omega(\sqrt{T-k})\) (在相关环境下)	极易受欺骗陷入局部次优	预算极早耗尽	缺乏理论下界防御能力

关键发现¶

相关性彻底摧毁查询增益：在全反馈模型下，不论奖励是否相关，查询均能提供 \(\mathcal{O}(T/k)\) 的显著加速；但在强盗反馈下，只要臂间引入轻微随机相关性，任何算法均无法跨越 \(\Omega(\sqrt{T-k})\) 的下界墙，直接证伪了全反馈结论向强盗设定的通用平移。
方差是化解两难的双刃剑：在 i.i.d. 设定下，迫使两环境统计不可区分必须要求环境具备极高方差，而高方差恰好赋予了每次最佳动作查询极大的负遗憾回报（\(\mathrm{OPT}_{\mathrm{d}} - \mathrm{OPT}_{\mathrm{s}} \gg 0\)）；反之，在低方差下查询虽无额外收益，但方差感知学习器（UCB-V）本身已具备近对数级的极快收敛速度。
信息丢弃反而促进极简最优性：算法在前 \(k\) 轮消耗查询后完全忽略其反馈数据，仅在后 \(T-k\) 轮冷启动运行 UCB-V，却在理论上严格达成了上下界匹配，揭示了在稀疏预言机场景下“利用即时负遗憾”远比“费力挖掘历史相关性”更为根本。

亮点与洞察¶

彻底终结开放科学问题：全面解决了 Russo 等人在 NeurIPS 2024 中悬置的核心猜想，完整给出了强盗反馈下带最佳动作查询的充要特征。
极致精巧的反例实例构造：构造了基于非线性概率积分变换 \(H_c(x)\) 的双臂耦合环境，巧妙实现了在两分布间使得查询反馈的 KL 散度严格归零、同时将累积负遗憾精确压制在常数阶，展示了极高水平的理论下界构造技巧。
以简驭繁的算法哲学：无需设计繁复的置信度阈值或动态规划调度，仅凭“前端盲查 + 后端方差自适应”的模块化组合，便化解了深刻的方差对立矛盾并达成理论极值。

局限与展望¶

理论常数因子较松：为了兼顾证明的普适性，上界与下界在臂数 \(n\) 与对数因子上仍保留了微小的多项式差距（如上界含有 \(\log T\)，下界在相关环境下与臂数 \(n\) 的依赖未完全紧致）。
完全忽略查询历史信息的次优性直觉：虽然在理论渐近阶数上匹配，但实际场景中将前 \(k\) 轮的观测数据直接丢弃略显浪费；如何在保证严格无偏的前提下复用查询阶段收集到的边际样本仍值得探索。
仅限未受污染的无噪预言机：模型假设预言机绝对诚实可靠，未来工作可拓展至带有噪声反馈、对抗性污染或置信度衰减的弱预言机查询环境。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 彻底解决顶级会议悬而未决的公开难题，首次揭示强盗反馈下最佳动作查询的相变现象。
实验充分度: ⭐⭐⭐⭐⭐ 作为纯理论工作，严格给出了相关下界、i.i.d. 匹配上下界的闭式数学证明，推导严丝合缝。
写作质量: ⭐⭐⭐⭐⭐ 概念界定清晰，从全反馈落差切入，动机环环相扣，数学证明结构工整优美。
价值: ⭐⭐⭐⭐⭐ 为稀缺昂贵大模型/专家介入在强化学习与在线决策中的资源分配奠定了扎实的信息论理论基础。