← 研踪 PaperTrailarXiv:2607.13686 · v2
Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation
首次提交 2026-07-15 18:28
版本更新 2026-11-04 11:27
雷达观测 2026-11-05 11:10
摘要
We study the contextual combinatorial semi-bandit (CCSB) problem, where at each round, the learner observes a context, selects a combinatorial action consisting of a subset of basic arms, and receives the reward of each selected arm; its goal is to maximize its cumulative reward over time. While many previous works focus on CCSB problems with linear reward function approximation, the design of efficient algorithms for the CCSB problem with general reward function approximation is limited. In this work, we study the realizable setting where the learner has access to a reward function class $\mathcal{F}$ that contains the true reward function, and propose the $\mathrm{SquareCB{.}Comb}$ algorithm. We prove that $\mathrm{SquareCB{.}Comb}$ achieves a minimax optimal regret bound of $O(\sqrt{m A T \log |\mathcal{F}|})$, where $A$ is the number of arms, $m$ is the maximum number of arms in a combinatorial action, and $T$ is the time horizon. In addition, $\mathrm{SquareCB{.}Comb}$ is computationally efficient when we have an online regression oracle that can efficiently predict rewards of all arms given contexts, and the combinatorial action set admits either efficient linear optimization or efficient sampling given any target marginal probability on arms. We empirically verify the effectiveness of our algorithm in webpage recommendation and contextual shortest path problems.
作者备注：44 pages (11 pages main body, 28 pages supplementary materials), accepted by NeurIPS 2026
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-04 11:27 · 最新观测版本
Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation
We study the contextual combinatorial semi-bandit (CCSB) problem, where at each round, the learner observes a context, selects a combinatorial action consisting of a subset of basic arms, and receives the reward of each selected arm; its goal is to maximize its cumulative reward over time. While many previous works focus on CCSB problems with linear reward function approximation, the design of efficient algorithms for the CCSB problem with general reward function approximation is limited. In this work, we study the realizable setting where the learner has access to a reward function class $\mathcal{F}$ that contains the true reward function, and propose the $\mathrm{SquareCB{.}Comb}$ algorithm. We prove that $\mathrm{SquareCB{.}Comb}$ achieves a minimax optimal regret bound of $O(\sqrt{m A T \log |\mathcal{F}|})$, where $A$ is the number of arms, $m$ is the maximum number of arms in a combinatorial action, and $T$ is the time horizon. In addition, $\mathrm{SquareCB{.}Comb}$ is computationally efficient when we have an online regression oracle that can efficiently predict rewards of all arms given contexts, and the combinatorial action set admits either efficient linear optimization or efficient sampling given any target marginal probability on arms. We empirically verify the effectiveness of our algorithm in webpage recommendation and contextual shortest path problems.
查看此版本解读 →查看此版本原文 ↗