# Statistically Efficient, Polynomial Time Algorithms for Combinatorial Semi Bandits

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2020.

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

- [Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms](https://mlsanity.com/paper/2208.14837/) (2022)
- [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)
- [Pure Exploration and Regret Minimization in Matching Bandits](https://mlsanity.com/paper/2108.00230/) (2021)
- [Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2402.15171/) (2024)
- [Matroid Semi-Bandits in Sublinear Time](https://mlsanity.com/paper/2405.17968/) (2024)
- [Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox](https://mlsanity.com/paper/2410.05441/) (2024)
- [Unimodal Mono-Partite Matching in a Bandit Setting](https://mlsanity.com/paper/2208.01511/) (2022)
- [Oracle-Efficient Combinatorial Semi-Bandits](https://mlsanity.com/paper/2510.21431/) (2025)
- [Tractable Instances of Bilinear Maximization: Implementing LinUCB on Ellipsoids](https://mlsanity.com/paper/2511.07504/) (2025)
- [Offline Local Search for Online Stochastic Bandits](https://mlsanity.com/paper/2604.09423/) (2026)

## Abstract (arXiv)

We consider combinatorial semi-bandits over a set of arms cal X subset 0,1d where rewards are uncorrelated across items. For this problem, the algorithm ESCB yields the smallest known regret bound R(T) = cal OBig( d (ln m)2 (ln T) over Deltamin Big), but it has computational complexity cal O(|cal X|) which is typically exponential in d, and cannot be used in large dimensions. We propose the first algorithm which is both computationally and statistically efficient for this problem with regret R(T) = cal O Big(d (ln m)2 (ln T)over Deltamin Big) and computational complexity cal O(T bf poly(d)). Our approach involves carefully designing an approximate version of ESCB with the same regret guarantees, showing that this approximate algorithm can be implemented in time cal O(T bf poly(d)) by repeatedly maximizing a linear function over cal X subject to a linear budget constraint, and showing how to solve this maximization problems efficiently.