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

arXiv: https://arxiv.org/abs/2607.13686 · HTML: https://mlsanity.com/paper/2607.13686/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 53 references that are in the map.
- First posted on arXiv 15 Jul 2026.

## Builds on (most cited first, 29 of 29)

- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Introducing LETOR 4.0 Datasets](https://mlsanity.com/paper/1306.2597/) (2013)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Practical Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/1803.01088/) (2018)
- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously](https://mlsanity.com/paper/1901.08779/) (2019)
- [Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits](https://mlsanity.com/paper/2007.07876/) (2020)
- [On the Complexity of Adversarial Decision Making](https://mlsanity.com/paper/2206.13063/) (2022)
- [Contextual Bandits with Large Action Spaces: Made Practical](https://mlsanity.com/paper/2207.05836/) (2022)
- [Adaptive LLM Routing under Budget Constraints](https://mlsanity.com/paper/2508.21141/) (2025)
- [Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback](https://mlsanity.com/paper/2101.08534/) (2021)
- [Contextual Bandits with Smooth Regret: Efficient Learning in Continuous Action Spaces](https://mlsanity.com/paper/2207.05849/) (2022)
- [Contextual Combinatorial Bandits with Probabilistically Triggered Arms](https://mlsanity.com/paper/2303.17110/) (2023)
- [Combinatorial Neural Bandits](https://mlsanity.com/paper/2306.00242/) (2023)
- [Online Estimation via Offline Estimation: An Information-Theoretic Framework](https://mlsanity.com/paper/2404.10122/) (2024)
- [Contextual Semibandits via Supervised Learning Oracles](https://mlsanity.com/paper/1502.05890/) (2015)
- [Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions](https://mlsanity.com/paper/2101.07957/) (2021)
- [Efficient Rate Optimal Regret for Adversarial Contextual MDPs Using Online Function Approximation](https://mlsanity.com/paper/2303.01464/) (2023)
- [Optimistic Information Directed Sampling](https://mlsanity.com/paper/2402.15411/) (2024)
- [Contextual Combinatorial Beam Management via Online Probing for Multiple Access mmWave Wireless Networks](https://mlsanity.com/paper/2412.10385/) (2024)
- [From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards](https://mlsanity.com/paper/2502.09257/) (2025)
- [Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Bandits](https://mlsanity.com/paper/2602.09456/) (2026)
- [A Contextual Combinatorial Semi-Bandit Approach to Network Bottleneck Identification](https://mlsanity.com/paper/2206.08144/) (2022)
- [Regret Minimization via Saddle Point Optimization](https://mlsanity.com/paper/2403.10379/) (2024)
- [Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Bandits](https://mlsanity.com/paper/2508.18768/) (2025)

## Built on by (most cited first, 1 of 1)

- [Efficient contextual partial monitoring with general function approximation](https://mlsanity.com/paper/2610.19804/) (2026)

## Abstract (arXiv)

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(√m A T log |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 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.