Oracle-Efficient Combinatorial Semi-Bandits¶

会议: NeurIPS 2025
arXiv: 2510.21431
代码: GitHub
领域: 优化
关键词: 组合半老虎机, oracle效率, 遗憾界, 在线学习, 协方差自适应

一句话总结¶

提出两种oracle高效框架（自适应和调度式），将组合半老虎机问题中的oracle调用次数从线性 \(\Theta(T)\) 降低到双对数 \(O(\log\log T)\)，同时保持近最优的遗憾界。

研究背景与动机¶

组合半老虎机（Combinatorial Semi-Bandit）是经典多臂老虎机的推广，智能体在每轮选择一组基臂的子集并获得每个基臂的反馈。该问题在产品推荐、广告分配和网络路由等场景中有广泛应用。

核心痛点：现有算法（如CUCB）虽然能达到近最优的遗憾界 \(\widetilde{O}(\sqrt{mdT})\)，但需要在每一轮都调用一次组合优化oracle。由于组合优化通常是NP-hard的，这导致oracle调用次数为 \(\Theta(T)\)，产生巨大的计算开销。

已有尝试的局限：Cuvelier等人提出基于近似的方法来降低计算复杂度，但引入了遗憾和计算代价之间的权衡——要达到最优遗憾需要越来越精确的近似，导致计算时间可能无界增长。Combes等人虽然启发式地使用 \(O(\log T)\) 次oracle调用，但缺乏理论遗憾保证。

本文切入角度：借鉴批量学习（batch learning）的思想，设计基于epoch的oracle查询策略，使得oracle调用集中在关键时间点，大部分轮次复用上一轮的决策。核心idea是将oracle效率分为自适应复杂度（顺序查询轮数）和查询复杂度（总查询次数）两个维度进行优化。

方法详解¶

整体框架¶

本文提出两类框架来减少oracle调用：

自适应稀有oracle查询（AROQ）：根据臂的选择计数动态触发oracle更新
调度式稀有oracle查询（SROQ）：在预定时间点批量执行oracle查询，支持并行化

两类框架分别适用于三种奖励模型：最坏情况线性奖励、协方差依赖线性奖励和一般（非线性）奖励。

关键设计¶

自适应epoch更新条件（AROQ-CMAB）：使用UCB策略，但只在满足阈值条件时才调用oracle更新。具体地，对每个基臂 \(i\) 维护epoch计数 \(\tau_i\)，当当前epoch中臂 \(i\) 被选中的次数满足

\[|{\mathcal{T}}_i(\tau_i)| \geq 1 + \sqrt{Tm \cdot |{\mathcal{T}}_i(\tau_i - 1)| / d}\]

时触发更新。这个阈值的设计动机是：每个epoch的遗憾被 \(\sqrt{1/|{\mathcal{T}}_i(\tau_i-1)|}\) 约束，乘以epoch长度后整体遗憾可控在 \(\sqrt{Tm/d}\)。不满足更新条件时，直接复用上一轮的动作 \(a_t = a_{t-1}\)，从而避免oracle调用。

调度式批量查询（SROQ-CMAB）：采用基于消除的策略。在预定时间点 \(\mathcal{T} = \{t_1, \ldots, t_M\}\) 执行oracle查询，其中 \(t_\tau = \eta\sqrt{t_{\tau-1}}\)，\(M = \Theta(\log\log T)\)。关键创新是为每个基臂 \(i\) 构建代表性动作 \(a_\tau^{(i)}\)，利用UCB/LCB指标进行消除：

\[r_\tau^{UCB}(a) = \sum_{i \in a}\left(\hat{\mu}_{\tau,i} + \sqrt{\frac{C\log T}{n_{\tau,i}}}\right)\]

如果臂 \(i\) 的最优代表动作的UCB值低于全局最优的LCB值，则该臂被消除。这种设计通过逐步缩小候选集 \(\mathcal{N}_\tau\) 来降低后续oracle查询的搜索空间。

协方差自适应扩展（AROQ-C-CMAB / SROQ-C-CMAB）：引入协方差估计器 \(\hat{\Sigma}_t\)，使用基于置信椭球的UCB指标：

\[r_t^{UCB}(a) = \langle a, \hat{\mu}_t \rangle + f_t \|D_{n_t}^{-1} a\|_{\bar{G}_t}\]

其中 \(\bar{G}_t\) 是基于协方差上界构建的Gram矩阵。初始阶段通过均匀探索来稳定协方差估计器，然后进入基于置信椭球的主阶段。在独立奖励情况下（\(\Sigma = I\)），遗憾界可从 \(\widetilde{O}(\sqrt{mdT})\) 改进到 \(\widetilde{O}(\sqrt{dT})\)，紧了 \(\sqrt{m}\) 倍。

损失函数 / 训练策略¶

本文为在线学习框架，核心优化目标是最小化累积遗憾：

\[\mathcal{R}(T) = \mathbb{E}\left[\sum_{t=1}^{T}(\bar{r}(a^*) - \bar{r}(a_t))\right]\]

所有算法通过精心设计的epoch更新条件或时间调度来平衡探索与利用。

实验关键数据¶

主实验¶

在线性奖励设定下，\(d=20\), \(m=3\) 的合成数据实验：

算法	遗憾界	自适应复杂度	查询复杂度	运行时间
CUCB	\(\widetilde{O}(\sqrt{mdT})\)	\(\Theta(T)\)	\(\Theta(T)\)	最慢
AROQ-CMAB	\(\widetilde{O}(\sqrt{mdT})\)	\(O(d\log\log T)\)	\(O(d\log\log T)\)	较快
SROQ-CMAB	\(\widetilde{O}(m\sqrt{dT})\)	\(\Theta(\log\log T)\)	\(O(d\log\log T)\)	最快

消融实验¶

框架类型	自适应复杂度	遗憾额外因子	并行友好性
自适应 (AROQ)	\(O(d\log\log T)\)	\(\log\log T\)	一般
调度式 (SROQ)	\(\Theta(\log\log T)\)	\(\sqrt{m} \cdot \sqrt{\log\log T}\)	强
协方差自适应-AROQ	\(O(d^2\log(Tm))\)	近最优	一般
协方差自适应-SROQ	\(\Theta(\log\log T)\)	\(\sqrt{d}\) 因子	强

关键发现¶

AROQ-CMAB的遗憾略高于CUCB，但oracle调用次数从线性降至双对数，运行时间显著减少
SROQ-CMAB虽然遗憾多一个 \(\sqrt{m}\) 因子，但因更低的自适应复杂度支持高效并行，实际运行最快
调度式框架在消除过程中逐步缩小候选臂集合，进一步降低每轮oracle查询的实际计算量

亮点与洞察¶

区分自适应复杂度和查询复杂度：这种双维度的oracle效率度量更准确地反映了实际计算开销，尤其是在并行环境下自适应复杂度往往才是瓶颈
双对数级别：\(O(\log\log T)\) 的oracle调用在实际中几乎可以忽略不计（例如 \(T=10^6\) 时 \(\log\log T \approx 3\)），是理论上的重大突破
框架的通用性：同一思想无缝扩展到协方差自适应和一般奖励函数两种变体，展示了良好的理论统一性

局限与展望¶

SROQ框架的遗憾比AROQ多一个 \(\sqrt{m}\) 因子，说明更低的自适应复杂度需要付出遗憾代价
协方差自适应版本需要 \(O(d^2)\) 级别的oracle复杂度，在臂数量 \(d\) 较大时可能成为瓶颈
实验仅使用合成数据集，缺少真实应用场景的验证
近似oracle的使用场景（\(\alpha\)-approximation）虽有讨论，但缺乏实证评估

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次将oracle调用复杂度降至双对数级别，理论贡献突出
实验充分度: ⭐⭐⭐ 仅有合成数据实验，缺少真实应用
写作质量: ⭐⭐⭐⭐ 理论推导清晰，但多算法变体较难跟踪
价值: ⭐⭐⭐⭐ 对组合在线学习的计算效率有重要推进