# Thompson Sampling for Combinatorial Semi-Bandits

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

## Key facts

- Cited by 78 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Mar 2018.

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

- [A survey on multi-player bandits](https://mlsanity.com/paper/2211.16275/) (2022)
- [Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and Generalization](https://mlsanity.com/paper/2110.14622/) (2021)
- [Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms](https://mlsanity.com/paper/2208.14837/) (2022)
- [Adversarial Combinatorial Bandits with General Non-linear Reward Functions](https://mlsanity.com/paper/2101.01301/) (2021)
- [Towards Scalable and Robust Structured Bandits: A Meta-Learning Framework](https://mlsanity.com/paper/2202.13227/) (2022)
- [Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits](https://mlsanity.com/paper/2206.03520/) (2022)
- [Thompson Sampling for Bandit Learning in Matching Markets](https://mlsanity.com/paper/2204.12048/) (2022)
- [Accelerating Approximate Thompson Sampling with Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2401.11665/) (2024)
- [Online Learning of Network Bottlenecks via Minimax Paths](https://mlsanity.com/paper/2109.08467/) (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)
- [Thompson Sampling with Diffusion Generative Prior](https://mlsanity.com/paper/2301.05182/) (2023)
- [Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond](https://mlsanity.com/paper/2406.01386/) (2024)
- [Combinatorial Bandits under Strategic Manipulations](https://mlsanity.com/paper/2102.12722/) (2021)
- [Multi-layered Network Exploration via Random Walks: From Offline Optimization to Online Learning](https://mlsanity.com/paper/2106.05065/) (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)
- [Offline Learning for Combinatorial Multi-armed Bandits](https://mlsanity.com/paper/2501.19300/) (2025)
- [ATA: Adaptive Task Allocation for Efficient Resource Management in Distributed Machine Learning](https://mlsanity.com/paper/2502.00775/) (2025)
- [Bayesian Optimization with Inexact Acquisition: Is Random Grid Search Sufficient?](https://mlsanity.com/paper/2506.11831/) (2025)
- [On the Suboptimality of Thompson Sampling in High Dimensions](https://mlsanity.com/paper/2102.05502/) (2021)
- [Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time](https://mlsanity.com/paper/2102.07254/) (2021)
- [Censored Semi-Bandits for Resource Allocation](https://mlsanity.com/paper/2104.05781/) (2021)
- [Simple Combinatorial Algorithms for Combinatorial Bandits: Corruptions and Approximations](https://mlsanity.com/paper/2106.06712/) (2021)
- [Pure Exploration and Regret Minimization in Matching Bandits](https://mlsanity.com/paper/2108.00230/) (2021)
- [Thompson Sampling Itself is Differentially Private](https://mlsanity.com/paper/2407.14879/) (2024)
- [Stochastic Bandits for Egalitarian Assignment](https://mlsanity.com/paper/2410.05856/) (2024)
- [FedRTS: Federated Robust Pruning via Combinatorial Thompson Sampling](https://mlsanity.com/paper/2501.19122/) (2025)

## Abstract (arXiv)

In this paper, we study the application of the Thompson sampling (TS) methodology to the stochastic combinatorial multi-armed bandit (CMAB) framework. We first analyze the standard TS algorithm for the general CMAB model when the outcome distributions of all the base arms are independent, and obtain a distribution-dependent regret bound of O(mlog Kmaxlog T / Deltamin), where m is the number of base arms, Kmax is the size of the largest super arm, T is the time horizon, and Deltamin is the minimum gap between the expected reward of the optimal solution and any non-optimal solution. This regret upper bound is better than the O(m(log Kmax)2log T / Deltamin) bound in prior works. Moreover, our novel analysis techniques can help to tighten the regret bounds of other existing UCB-based policies (e.g., ESCB), as we improve the method of counting the cumulative regret. Then we consider the matroid bandit setting (a special class of CMAB model), where we could remove the independence assumption across arms and achieve a regret upper bound that matches the lower bound. Except for the regret upper bounds, we also point out that one cannot directly replace the exact offline oracle (which takes the parameters of an offline problem instance as input and outputs the exact best action under this instance) with an approximation oracle in TS algorithm for even the classical MAB problem. Finally, we use some experiments to show the comparison between regrets of TS and other existing algorithms, the experimental results show that TS outperforms existing baselines.