Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation¶
会议: NeurIPS 2026
arXiv: 2607.13686
OpenReview: https://openreview.net/forum?id=1XBZJBTBc2
领域: 其他
关键词: 上下文组合半老虎机, 一般函数逼近, SquareCB, 决策估计系数, 极小极大最优遗憾
一句话总结¶
针对一般函数逼近下的上下文组合半老虎机问题，提出首个计算高效且遗憾界达到极小极大最优 \(\widetilde{\mathcal{O}}(\sqrt{mAT\log|\mathcal{F}|})\) 的算法 SquareCB.Comb，通过在基础臂参与向量空间求解对数障碍正则化凸优化实现最优探索与利用权衡。
研究背景与动机¶
上下文组合半老虎机（Contextual Combinatorial Semi-Bandits, CCSB）是序列决策与交互学习的核心框架，广泛应用于网络路径规划与瓶颈识别、多大语言模型（LLM）调用路由、个性化组合列表推荐以及无线信道资源分配。在每一轮交互中，学习系统接收环境上下文，并从 \(A\) 个基础臂构成的动作池中挑选出满足特定组合结构约束的子集（组合动作，基数上界为 \(m\)），随后观察所选基础臂各自的回报反馈（半老虎机反馈）。与只能观测标量总收益的经典组合全老虎机（full-bandit）相比，半老虎机反馈提供了细粒度监督信号；然而，如何在包含巨大甚至组合爆炸动作空间的复杂环境下，同时兼顾计算可行性与理论最优的样本效率，始终是该领域的根本挑战。
既有关于函数逼近下 CCSB 的理论研究绝大部分局限在线性回报假设上，即假设基础臂的期望回报是上下文特征的线性函数。然而在实际工业推荐或复杂网络中，上下文与回报之间的映射往往高度非线性且复杂。尽管少数前人工作尝试通过策略搜索（policy search）或将组合动作粗暴退化为单个超臂来应用通用上下文老虎机算法，但前者依赖计算上难以处理的策略枚举或受限的分类预言机，后者则因直接累加反馈而承受额外的 \(\mathcal{O}(m)\) 膨胀系数（遗憾界退化至 \(\widetilde{\mathcal{O}}(m\sqrt{AT\log|\mathcal{F}|})\)）。核心矛盾在于：半老虎机反馈在臂维度展开，而组合动作决策分布定义在指数级空间 \(\Delta(\mathcal{S})\) 上；现有决策估计系数（DEC）及回归规约框架无法直接兼容细粒度观测，导致难以在多项式时间内找到能够有效控制非线性统计估计误差的最优探索分布。
为了打破这一僵局，本文从在线决策的“估计到决策”（Estimation-to-Decisions, E2D）原则出发，创新性地将组合动作层面的统计复杂度下沉到基础臂维度的边缘参与概率空间，进而消除维度灾难并无缝衔接在线平方损失回归预言机。核心 idea：提出定制于半老虎机反馈与平方损失的组合决策估计系数（CS-DEC），将指数级组合动作空间上的最小最大探索问题等价转化为基础臂参与向量空间上的 \(A\) 维对数障碍正则化凸优化，实现计算高效且理论上严格达到极小极大最优界 \(\widetilde{\mathcal{O}}(\sqrt{mAT\log|\mathcal{F}|})\) 的通用在线决策算法。
方法详解¶
整体框架¶
SquareCB.Comb 算法在每一轮 \(t\) 中依序执行四个核心阶段：回归模型预测更新、上下文感知参与向量凸优化、组合动作相容采样、以及半老虎机观测反馈更新。输入为问题元组 \((\mathcal{X}, \mathcal{S}, \mathcal{A})\)、批模式在线回归预言机 \(\mathcal{O}_{\text{batch}}\)、组合采样预言机 \(\mathcal{O}_{\text{sample}}\)、均值回报函数类 \(\mathcal{F}\) 及探索超参数 \(\gamma\)。算法不直接在指数规模的组合动作集合 \(\mathcal{S}\) 或其概率单纯形 \(\Delta(\mathcal{S})\) 上维持分布，而是将探索分布完全参数化为基础臂的边缘参与向量 \(\bar{p}_t \in \bar{\mathcal{S}} \subset [0, 1]^A\)，其中第 \(a\) 维 \(\bar{p}_t(a)\) 表示臂 \(a\) 被选中的边际概率。通过求解一个带对数障碍正则项的 \(A\) 维凹优化问题，算法平衡对当前估计模型的高贪心回报与对全臂集的充分覆盖；随后调用多项式时间的组合采样过程输出满足边际概率的合法组合动作 \(s_t \in \mathcal{S}\)，并在获取半老虎机反馈后将观测批量回传给回归预言机。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["环境上下文 x_t 与历史观测"] --> B["阶段1：批模式在线回归预测<br/>预言机输出均值回报估计"]
B --> C["阶段2：对数障碍凸优化<br/>在参与向量凸包求解边际概率"]
C --> D["阶段3：相容组合采样<br/>相容采样预言机析出离散组合动作"]
D --> E["阶段4：半老虎机反馈更新<br/>收集被选臂回报并批量送入预言机"]关键设计¶
1. 组合平方损失决策估计系数（CS-DEC）：连接半老虎机细粒度反馈与统计复杂度
经典 DEC 理论预设学习者能获取精确的条件似然模型或依赖于全动作标量反馈，无法直接对接半老虎机中多臂平方损失回归误差的累积。为此，本文针对平方损失与半老虎机结构提出了新型复杂度度量 CS-DEC。对于任意回归估计量 \(\hat{g}: \mathcal{A} \to [0, 1]\)、函数类 \(\mathcal{G}\) 和动作集 \(\mathcal{S}\)，定义： $\(\mathsf{dec}_\gamma(\hat{g}, \mathcal{G}) = \min_{p \in \Delta(\mathcal{S})} \max_{q \in \Delta(\mathcal{S}), g^\star \in \mathcal{G}} \mathbb{E}_{s \sim q}[\langle g^\star, s \rangle] - \mathbb{E}_{s \sim p}[\langle g^\star, s \rangle] - \gamma \mathbb{E}_{s \sim p}\left[\sum_{a=1}^A s(a)(\hat{g}(a) - g^\star(a))^2\right]\)$ 该设计的关键创新在于 Proposition 3 揭示的降维等价性：由于目标函数对组合动作指示向量 \(s\) 和 \(q\) 均呈线性，上述定义在组合概率分布空间 \(\Delta(\mathcal{S})\) 上的庞大极小极大博弈，能够严格等价地重写在动作凸包 \(\bar{\mathcal{S}} = \mathsf{Conv}(\mathcal{S})\) 的参与向量（participation vector）空间 \(\bar{p}, \bar{q} \in \bar{\mathcal{S}} \subset [0, 1]^A\) 上。这一性质使得学习者无需探索组合状态爆炸的分布空间，直接在低维线性空间消除冗余。
2. 参与向量空间的对数障碍正则化凸优化：多项式时间探索计算
为了在每一轮高效构造出能够认证 CS-DEC 足够小的探索分布，算法在基础臂参与向量凸包 \(\bar{\mathcal{S}}\) 上构造了一个代理凸规划问题。具体而言，针对当前轮上下文 \(x_t\) 和预测模型 \(\hat{f}_t\)，求解如下 \(A\) 维凸优化： $\(\bar{p}_t = \mathop{\mathrm{arg\,max}}_{\bar{p} \in \bar{\mathcal{S}}} \left\langle \bar{p}, \hat{f}_t(x_t, \cdot) \right\rangle + \frac{1}{\gamma} \sum_{a \in \mathcal{A}} \log \bar{p}(a)\)$ 目标函数第一项直接最大化当前预测回报（利用），第二项对数障碍（log-barrier）则充当探索正则化因子，强力惩罚任何边际被选概率过低的臂，迫使概率质量覆盖整个臂池。理论证明，该目标函数的严格凹性与一阶最优性条件能够严格认证代理极小极大覆盖误差界 \(\max_{\bar{q} \in \bar{\mathcal{S}}} \langle \hat{g}, \bar{q} - \bar{p} \rangle + \frac{1}{\gamma} \sum_{a \in \mathcal{A}} \frac{\bar{q}(a)^2}{\bar{p}(a)} \le \frac{A}{\gamma}\)，进而由引理 6 与引理 7 保证单步遗憾严格受控于 \(\mathcal{O}(A/\gamma + \gamma \|\hat{f}_t - f^\star\|_{\bar{p}_t}^2)\)。
3. 相容组合动作采样预言机与 Frank-Wolfe 无缝统一：实现计算闭环
在获得连续参与向量 \(\bar{p}_t \in \bar{\mathcal{S}}\) 后，学习者必须抽取一个离散组合动作 \(s_t \in \mathcal{S}\)，满足其边际期望恰好等于参与向量，即 \(\mathbb{E}[s_t] = \bar{p}_t\)。对于无序 \(m\) 子集推荐任务，直接利用 Gandhi et al. (2006) 的依赖舍入算法（dependent rounding）在 \(\mathcal{O}(A)\) 时间内完成精确采样；对于有序 \(m\) 列表推荐任务，可调用基于置换矩阵凸分解的多项式采样器；对于 DAG 上的最短路径问题，则采用标准的无环流分解算法。更重要的是，对于任何仅具备线性优化预言机（linear optimization oracle, \(\arg\min_{s \in \mathcal{S}} \langle \ell, s \rangle\)）的通用多面体约束，算法可直接通过 Frank-Wolfe 迭代在求解连续优化的同时自然维持极点组合动作的凸组合权重 \(\bar{p}_n = \sum_i \alpha_i s^i\)，从而直接按权重采样抽取 \(s_t\)，实现了优化与采样的完全统一。
一个完整示例¶
以无序 \(m\)-set 推荐（\(A=10\) 个候选文档，每轮挑选 \(m=3\) 个展示给用户）为例： 1. 回归预言机 \(\mathcal{O}_{\text{batch}}\) 输出 10 个文档的预测相关性分数 \(\hat{f}_t(x_t, \cdot) = [0.9, 0.85, 0.8, 0.4, 0.3, 0.2, 0.1, 0.1, 0.05, 0.05]\)。 2. 求解对数障碍优化：若无正则项，贪心解将集中在最高分的前 3 个臂，其余臂参与概率为 0；加入对数障碍项后，前三名的高分文档获得主要边际概率（如 \(0.65, 0.60, 0.55\)），而低分长尾文档亦获得保底探索概率（如各分得 \(0.15 \sim 0.10\)），各分量之和严格满足 \(\sum_{a=1}^{10} \bar{p}_t(a) = 3\)。 3. 采样预言机调用依赖舍入算法，依据边际概率向量在 \(\mathcal{O}(A)\) 时间内输出合法子集 \(s_t = \{1, 2, 5\}\)（即选中了文档 1、2 及探索文档 5）。 4. 系统展示该 3 篇文档并收集用户的实际点击反馈 \((r_t(1), r_t(2), r_t(5))\)，并将其作为大小为 3 的样本批次送入在线回归预言机更新回归模型。
损失函数 / 训练策略¶
算法依赖在线回归预言机 \(\mathcal{O}_{\text{batch}}\) 处理按批到达的半老虎机样本，回归目标采用标准平方损失： $\(\mathrm{Reg}_{\text{batch}}(T) = \sum_{t=1}^T \sum_{a: s_t(a)=1} (\hat{f}_t(x_t, a) - r_t(a))^2 - \inf_{f \in \mathcal{F}} \sum_{t=1}^T \sum_{a: s_t(a)=1} (f(x_t, a) - r_t(a))^2\)$ 当采用有限函数类时，通过指数加权平均算法（EWA）可保证批回归遗憾满足 \(\mathrm{Reg}_{\text{batch}}(T) \lesssim m \log|\mathcal{F}|\)。选择恒定探索步长参数 \(\gamma = \sqrt{\frac{AT}{m \log|\mathcal{F}|}}\) 平衡利用项 \(\frac{AT}{\gamma}\) 与探索统计项 \(\gamma \mathrm{Reg}_{\text{batch}}(T)\)，最终导出总遗憾界 \(\mathbb{E}[\mathrm{Regret}(T)] \le \mathcal{O}(\sqrt{mAT\log|\mathcal{F}|})\)。对于实际批处理离线场景，亦提出了通过倍增轮次调度的离线回归版本 OE2D.Comb，利用离线经验风险最小化（ERM）预言机实现同样的理论阶数。
实验关键数据¶
主实验¶
实验基于两个公开工业级排序检索评测基准：微软搜索日志数据集 MSLR-WEB30k（\(A=10, m=3, T=30{,}846\)）与雅虎搜索排序挑战赛数据集 Yahoo! LTR Set 1（\(A=6, m=2, T=27{,}630\)）。采用经典的监督数据向老虎机规约方法，将文档相关度等级（0 至 4）映射为半老虎机点击反馈。算法运行单 pass 流式交互，对比在不同回归骨干网络下的终轮平均单步累积回报（Mean \(\pm\) SE，跨 10 个随机种子）。
| 数据集 | 算法 | 线性回归 (lin) | 梯度提升树深度2 (gb2) | 梯度提升树深度5 (gb5) |
|---|---|---|---|---|
| MSLR-WEB30k | SquareCB.Comb (本文) | \(2.024 \pm 0.002\) | \(\mathbf{2.373 \pm 0.002}\) | \(\mathbf{2.404 \pm 0.001}\) |
| MSLR-WEB30k | SquareCB.Lin (Foster et al., 2020) | \(2.028 \pm 0.002\) | \(2.366 \pm 0.002\) | \(2.398 \pm 0.002\) |
| MSLR-WEB30k | VCEE (Krishnamurthy et al., 2016) | \(2.252 \pm 0.002\) | \(2.309 \pm 0.003\) | \(2.366 \pm 0.003\) |
| MSLR-WEB30k | \(\varepsilon\)-greedy (Langford & Zhang) | \(2.030 \pm 0.002\) | \(2.373 \pm 0.001\) | \(2.401 \pm 0.002\) |
| MSLR-WEB30k | LinUCB (Chu et al., 2011) | \(\mathbf{2.330 \pm 0.002}\) | — (仅支持线性) | — (仅支持线性) |
| MSLR-WEB30k | Skyline 监督学习参考上限 | \(2.340 \pm 0.001\) | \(2.402 \pm 0.001\) | \(2.536 \pm 0.001\) |
| MSLR-WEB30k | Uniform-random 随机基线 | \(1.815 \pm 0.002\) | \(1.815 \pm 0.002\) | \(1.815 \pm 0.002\) |
| Yahoo! LTR Set 1 | SquareCB.Comb (本文) | \(3.141 \pm 0.001\) | \(\mathbf{3.187 \pm 0.001}\) | \(\mathbf{3.217 \pm 0.001}\) |
| Yahoo! LTR Set 1 | SquareCB.Lin (Foster et al., 2020) | \(3.138 \pm 0.001\) | \(3.184 \pm 0.001\) | \(3.211 \pm 0.001\) |
| Yahoo! LTR Set 1 | VCEE (Krishnamurthy et al., 2016) | \(3.083 \pm 0.009\) | \(3.132 \pm 0.001\) | \(3.189 \pm 0.002\) |
| Yahoo! LTR Set 1 | \(\varepsilon\)-greedy (Langford & Zhang) | \(3.140 \pm 0.001\) | \(3.186 \pm 0.001\) | \(3.214 \pm 0.001\) |
| Yahoo! LTR Set 1 | LinUCB (Chu et al., 2011) | \(\mathbf{3.168 \pm 0.001}\) | — (仅支持线性) | — (仅支持线性) |
| Yahoo! LTR Set 1 | Skyline 监督学习参考上限 | \(3.209 \pm 0.001\) | \(3.219 \pm 0.001\) | \(3.335 \pm 0.001\) |
| Yahoo! LTR Set 1 | Uniform-random 随机基线 | \(2.591 \pm 0.002\) | \(2.591 \pm 0.002\) | \(2.591 \pm 0.002\) |
消融实验¶
消融重点分析了回归预言机表达能力等级（模型非线性拟合能力）与超参数调节空间对在线学习累积回报的影响。
| 评估维度 / 配置变体 | MSLR-WEB30k 终轮平均回报 | Yahoo! LTR 终轮平均回报 | 说明 |
|---|---|---|---|
| 预言机复杂度: gb5 (树深 5) | \(\mathbf{2.404 \pm 0.001}\) | \(\mathbf{3.217 \pm 0.001}\) | 高容量非线性预言机，拟合能力最强，性能最优 |
| 预言机复杂度: gb2 (树深 2) | \(2.373 \pm 0.002\) | \(3.187 \pm 0.001\) | 浅层树集成，相对 gb5 分别下降 0.031 与 0.030 |
| 预言机复杂度: lin (线性模型) | \(2.024 \pm 0.002\) | \(3.141 \pm 0.001\) | 线性基准，因无法捕捉非线性特征交互而显著落后 |
| 动作选择规约: SquareCB.Lin (全老虎机) | \(2.398 \pm 0.002\) | \(3.211 \pm 0.001\) | 采用标量化汇总全老虎机规约，略逊于半老虎机精细探索 |
| 策略消除基准: VCEE (gb5) | \(2.366 \pm 0.003\) | \(3.189 \pm 0.002\) | 基于代价敏感分类的策略消除法，探索效率低于回归引导 |
关键发现¶
- 在非线性预言机配置下，SquareCB.Comb 全面领先：当预言机从线性换为梯度提升决策树（gb2 与 gb5）时，SquareCB.Comb 在两个数据集上均取得了在线学习算法中的最高回报，且与理想监督上限（Skyline）差距大幅缩窄。
- 细粒度半老虎机探索优于全老虎机粗暴汇总：SquareCB.Comb 无论在均值还是方差上均系统性击败了将半老虎机累加为标量全老虎机反馈的 SquareCB.Lin，这印证了理论中 \(\sqrt{m}\) 因子替代 \(m\) 因子的紧致优势。
- 线性场景下 LinUCB 表现优异：在线性函数限定下，LinUCB 凭借闭式置信椭球更新获得了强劲性能（在 lin 列达到最高），但其天然无法扩展到树集成或神经网络等复杂非线性函数类；而 SquareCB.Comb 能够无缝兼容任意强大的黑盒回归器。
亮点与洞察¶
- 半老虎机 DEC 的降维等价性：将指数级组合动作空间上的极小极大博弈严格降维为 \(A\) 维参与向量上的凸规划，数学上建立了半老虎机细粒度估计误差与凸松弛覆盖误差的无缝对应。
- 理论下界完全闭合：通过构造多上下文嵌入的非上下文 \(m\)-path 难题实例，证明了 \(\widetilde{\Omega}(\sqrt{mAT\log|\mathcal{F}|})\) 极小极大下界，确立了所提算法在动作基数、臂总数、时间跨度及函数类容量上的绝对紧致性。
- 回归与组合优化的模块化解耦：算法完全将统计估计（任意黑盒在线回归预言机）与运筹组合结构（依赖舍入或 Frank-Wolfe）解耦，工程实现极其清爽，极易迁移到路径规划、大模型路由等实际系统。
局限与展望¶
- 独立噪声回报假设的潜在改进空间：正如作者在第 5 节所述，当前的匹配下界依赖于各臂回报之间的强相关性构造；若假设在给定上下文下各臂观测噪声相互独立，极小极大遗憾下界是否能进一步降低至更紧的阶数仍是未解开放问题。
- 对数障碍优化在极大规模臂集下的计算开销：当基础臂规模达到数十万量级时，每一轮求解 \(A\) 维凸优化并投影到任意组合多面体可能成为延迟瓶颈，未来可探索更轻量的一阶近似更新或随机坐标下降。
- 实现模型误设下的鲁棒性泛化：虽然文中给出了针对 \(\varepsilon\)-误设的理论拓展界，但在深度神经网络作为回归主干时的经验表现与泛化理论仍需进一步实证检验。
相关工作与启发¶
- vs Kale et al. (2010): 他们采用策略类指数加权算法处理 slate 问题，计算开销随策略数指数级增长；本文基于回归预言机，计算效率大幅提升且自然推广至任意组合约束。
- vs Krishnamurthy et al. (2016) (VCEE): VCEE 依赖策略消除与代价敏感分类预言机，在工业界黑盒场景下不如回归预言机易用；主实验表明 SquareCB.Comb 在非线性场景下持续大幅超越 VCEE。
- vs SquareCB.Lin (Foster et al., 2020): 后者通过将动作视为整体超臂退化至全老虎机框架，理论遗憾界承受额外的 \(\mathcal{O}(m)\) 放大；本文充分发掘半老虎机分解结构，严格消除此项松弛。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次提出组合平方损失 DEC 概念并将博弈降维至参与向量对数障碍凸优化，理论创新扎实优美。
- 实验充分度: ⭐⭐⭐⭐ 覆盖微软与雅虎两大经典公开工业检索排序基准，设置严谨，对比了 5 种代表性基线与不同模型容量。
- 写作质量: ⭐⭐⭐⭐⭐ 数学证明严谨完整，论文结构层层递进，动机阐述与技术细节交代极为清晰透彻。
- 价值: ⭐⭐⭐⭐⭐ 彻底解决了非线性函数逼近下组合半老虎机极小极大最优界与计算高效性的长期理论难题，指导意义重大。