Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation

Research Question and Approach

The paper addresses the contextual combinatorial semi-bandit (CCSB) problem, where a learner must repeatedly select a subset of base arms (a combinatorial action) based on observed context to maximize cumulative reward. Unlike standard contextual bandits, the learner receives semi-bandit feedback—observing rewards only for the specific arms chosen. The authors seek an algorithm that is both computationally efficient and theoretically optimal under general reward function approximation, moving beyond the restrictive linear-reward models common in prior literature.

To solve this, the authors propose SquareCB.Comb. The algorithm operates by maintaining an estimate of the reward function using a batch-mode online regression oracle. At each round, it computes a participation vector—a probability distribution over arms—by solving a log-barrier regularized convex optimization problem. This step balances the 'greediness' of the current reward estimate with an exploration term that prevents the algorithm from prematurely focusing on a narrow set of arms. Finally, a sampling oracle converts this participation vector into a specific combinatorial action.

The primary contribution is the proof that SquareCB.Comb achieves a minimax optimal regret bound of O(sqrt(mAT log|F|)). Here, 'm' is the maximum size of a combinatorial action, 'A' is the number of arms, 'T' is the time horizon, and 'F' is the reward function class. This result is significant because it matches the state-of-the-art regret guarantees for more restricted settings (like linear rewards or specific slate recommendations) while generalizing to arbitrary combinatorial structures and arbitrary reward function classes.

This work provides a unified, efficient framework for complex sequential decision-making tasks where rewards are non-linear and combinatorial constraints exist. By reducing the problem to a convex optimization step followed by a sampling procedure, the algorithm avoids the computational burden of enumerating large policy classes. This makes it highly applicable to real-world scenarios such as online personalized recommendation, multi-LLM routing, and network path planning, where the relationship between context and reward is often too complex for linear models.