# Efficient Learning in Large-Scale Combinatorial Semi-Bandits

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jun 2014.

## Built on by (most cited first, 30 of 36)

- [No Regrets for Learning the Prior in Bandits](https://mlsanity.com/paper/2107.06196/) (2021)
- [An Analysis of Ensemble Sampling](https://mlsanity.com/paper/2203.01303/) (2022)
- [Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback](https://mlsanity.com/paper/2101.08534/) (2021)
- [Multinomial Logit Contextual Bandits: Provable Optimality and Practicality](https://mlsanity.com/paper/2103.13929/) (2021)
- [Combinatorial Neural Bandits](https://mlsanity.com/paper/2306.00242/) (2023)
- [Towards Scalable and Robust Structured Bandits: A Meta-Learning Framework](https://mlsanity.com/paper/2202.13227/) (2022)
- [Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions](https://mlsanity.com/paper/2101.07957/) (2021)
- [A Map of Bandits for E-commerce](https://mlsanity.com/paper/2107.00680/) (2021)
- [Incentivizing Combinatorial Bandit Exploration](https://mlsanity.com/paper/2206.00494/) (2022)
- [Effective Off-Policy Evaluation and Learning in Contextual Combinatorial Bandits](https://mlsanity.com/paper/2408.11202/) (2024)
- [Online Learning of Energy Consumption for Navigation of Electric Vehicles](https://mlsanity.com/paper/2111.02314/) (2021)
- [The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oracle](https://mlsanity.com/paper/2111.04295/) (2021)
- [Budgeted Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2202.03704/) (2022)
- [When Combinatorial Thompson Sampling meets Approximation Regret](https://mlsanity.com/paper/2302.11182/) (2023)
- [Fixed-Budget Best-Arm Identification with Heterogeneous Reward Variances](https://mlsanity.com/paper/2306.07549/) (2023)
- [Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time](https://mlsanity.com/paper/2102.07254/) (2021)
- [From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards](https://mlsanity.com/paper/2502.09257/) (2025)
- [Multiplier Bootstrap-based Exploration](https://mlsanity.com/paper/2302.01543/) (2023)
- [Matroid Semi-Bandits in Sublinear Time](https://mlsanity.com/paper/2405.17968/) (2024)
- [Distributional Off-Policy Evaluation for Slate Recommendations](https://mlsanity.com/paper/2308.14165/) (2023)
- [A Contextual Combinatorial Bandit Approach to Negotiation](https://mlsanity.com/paper/2407.00567/) (2024)
- [Neural Combinatorial Clustered Bandits for Recommendation Systems](https://mlsanity.com/paper/2410.14586/) (2024)
- [Adaptive Prior Selection in Gaussian Process Bandits with Thompson Sampling](https://mlsanity.com/paper/2502.01226/) (2025)
- [Adversarial Combinatorial Semi-bandits with Graph Feedback](https://mlsanity.com/paper/2502.18826/) (2025)
- [CAE: Repurposing the Critic as an Explorer in Deep Reinforcement Learning](https://mlsanity.com/paper/2503.18980/) (2025)
- [Learning Peer Influence Probabilities with Linear Contextual Bandits](https://mlsanity.com/paper/2510.19119/) (2025)
- [Reliability-Aware Determinantal Point Processes for Robust Informative Data Selection in Large Language Models](https://mlsanity.com/paper/2602.00885/) (2026)
- [Adaptive Bandit Algorithms for Contextual Matching Markets](https://mlsanity.com/paper/2605.28290/) (2026)
- [The Sample Complexity of Multiclass and Sparse Contextual Bandits](https://mlsanity.com/paper/2605.29645/) (2026)
- [Generalized Linear Bandits with Memory](https://mlsanity.com/paper/2608.15848/) (2026)

## Abstract (arXiv)

A stochastic combinatorial semi-bandit is an online learning problem where at each step a learning agent chooses a subset of ground items subject to combinatorial constraints, and then observes stochastic weights of these items and receives their sum as a payoff. In this paper, we consider efficient learning in large-scale combinatorial semi-bandits with linear generalization, and as a solution, propose two learning algorithms called Combinatorial Linear Thompson Sampling (CombLinTS) and Combinatorial Linear UCB (CombLinUCB). Both algorithms are computationally efficient as long as the offline version of the combinatorial problem can be solved efficiently. We establish that CombLinTS and CombLinUCB are also provably statistically efficient under reasonable assumptions, by developing regret bounds that are independent of the problem scale (number of items) and sublinear in time. We also evaluate CombLinTS on a variety of problems with thousands of items. Our experiment results demonstrate that CombLinTS is scalable, robust to the choice of algorithm parameters, and significantly outperforms the best of our baselines.