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

• URL: http://arxiv.org/abs/2607.13686v1
• Date: Wed, 15 Jul 2026 10:28:05 GMT
• Title: Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation
• Abstract summary: We show that SquareCB.Comb achieves a minimax optimal regret bound of $O(sqrtm A T log |mathcalF|)$, where $A$ is the number of arms, $m$ is the maximum number of arms in an action, and $T$ is the time horizon.<n>In the realizable setting, this bound matches the state-of-the-art regret guarantees achieved by policy search-based algorithms.
• Score: 17.2911371867411
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the contextual combinatorial semi-bandit (CCSB) problem with general reward function approximation. 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; the goal is to maximize the cumulative reward over time. We propose SquareCB.Comb, a computationally efficient algorithm that, at each round, solves a convex optimization problem to sample a combinatorial action that balances exploration and exploitation. SquareCB.Comb scales to large arm sets and imposes no structural assumptions on the action set beyond a cardinality bound of $m$ on each combinatorial action. We prove that 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, $T$ is the time horizon, and $\mathcal{F}$ is the reward function class. In the realizable setting, this bound matches the state-of-the-art regret guarantees achieved by policy search-based algorithms in the more restricted slate recommendation settings, while simultaneously generalizing to arbitrary combinatorial action structures and general reward function approximation.

Related papers

• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  We aim to identify an approximately optimal policy from a given class based on bandit feedback.<n>Motivated by bandit multiclass classification with zero-one rewards, we focus on the emph$s$-sparse setting.<n>We show that, with $s$-sparse rewards, the induced model class admits a sharp DEC bound that scales with $s$ and directly yields the optimal rate.
  arXiv  Detail & Related papers  (2026-05-28T09:12:20Z)
• Multiple-play Stochastic Bandits with Prioritized Arm Capacity Sharing [52.124267908936396]
  The model is composed of $M$ arms and $K$ plays.<n>Each arm has a number of capacities, and each unit of capacity is associated with a reward function.<n>When multiple plays compete for the arm capacity, the arm capacity is allocated in a larger priority weight first manner.
  arXiv  Detail & Related papers  (2025-12-25T11:19:09Z)
• Multi-Play Combinatorial Semi-Bandit Problem [8.922365714546162]
  In the semi-bandit (CSB) problem, a player selects an action from a action set and observes feedback from the base arms included in the action.<n>We propose the multi-play semi-bandit (MP-CSB), where a player can select a non-negative integer action and observe multiple feedbacks from a single arm in each round.
  arXiv  Detail & Related papers  (2025-09-12T02:46:59Z)
• Batched Stochastic Matching Bandits [43.651070266360954]
  We introduce a novel bandit framework for matching based on the Multi-nomial Logit (MNL) choice model.<n>In our setting, $N$ agents on one side are assigned to $K$ arms on the other side, where each armally selects an agent from its assigned pool according to an unknown preference.<n>The objective is to minimize regret by maximizing the cumulative revenue from successful matches across all agents.
  arXiv  Detail & Related papers  (2025-09-04T13:16:32Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
  We study the real-valued pure exploration problem in the multi-armed bandit (R-CPE-MAB)<n>We introduce an algorithm named the gap-based exploration (CombGapE) algorithm, whose sample complexity upper bound matches the lower bound up to a problem-dependent constant factor.<n>We numerically show that the CombGapE algorithm outperforms existing methods significantly in both synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2023-06-15T15:37:31Z)
• Contextual Combinatorial Bandits with Changing Action Sets via Gaussian Processes [8.919345630832366]
  We consider a contextual bandit problem with a action set and time-varying base arm availability.<n>We propose an algorithm called Optimistic Combinatorial Learning and Optimization with Kernel Upper Confidence Bounds (O'CLOK-UCB)<n>To dramatically speed up the algorithm, we also propose a variant of O'CLOK-UCB that uses sparse GPs.
  arXiv  Detail & Related papers  (2021-10-05T18:02:10Z)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  We study the top-$k$ extreme contextual bandits problem, where the total number of arms can be enormous. We first propose an algorithm for the non-extreme realizable setting, utilizing the Inverse Gap Weighting strategy. We show that our algorithm has a regret guarantee of $O(ksqrt(A-k+1)T log (|mathcalF|T))$.
  arXiv  Detail & Related papers  (2021-02-15T19:10:52Z)
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
  Combinatorial bandits generalize multi-armed bandits, where the agent chooses sets of arms and observes a noisy reward for each arm contained in the chosen set. We focus on the pure-exploration problem of identifying the best arm with fixed confidence, as well as a more general setting, where the structure of the answer set differs from the one of the action set. Based on a projection-free online learning algorithm for finite polytopes, it is the first computationally efficient algorithm which is convexally optimal and has competitive empirical performance.
  arXiv  Detail & Related papers  (2021-01-21T10:35:09Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
  arXiv  Detail & Related papers  (2021-01-20T04:29:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.