# Simple Combinatorial Algorithms for Combinatorial Bandits: Corruptions and Approximations

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 25 references that are in the map.
- First posted on arXiv 12 Jun 2021.

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

- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Better Algorithms for Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/1902.08647/) (2019)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously](https://mlsanity.com/paper/1901.08779/) (2019)
- [An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits](https://mlsanity.com/paper/1605.08722/) (2016)
- [An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1702.06103/) (2017)
- [Efficient Online Linear Optimization with Approximation Algorithms](https://mlsanity.com/paper/1709.03093/) (2017)
- [Online Improper Learning with an Approximation Oracle](https://mlsanity.com/paper/1804.07837/) (2018)
- [What You See May Not Be What You Get: UCB Bandit Algorithms Robust to ε-Contamination](https://mlsanity.com/paper/1910.05625/) (2019)

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

- [Bayesian Optimization with Inexact Acquisition: Is Random Grid Search Sufficient?](https://mlsanity.com/paper/2506.11831/) (2025)
- [Practical Adversarial Attacks on Stochastic Bandits via Fake Data Injection](https://mlsanity.com/paper/2505.21938/) (2025)
- [Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit](https://mlsanity.com/paper/2310.15681/) (2023)
- [Online Learning to Rank under Corruption: A Robust Cascading Bandits Approach](https://mlsanity.com/paper/2511.03074/) (2025)

## Abstract (arXiv)

We consider the stochastic combinatorial semi-bandit problem with adversarial corruptions. We provide a simple combinatorial algorithm that can achieve a regret of tildeOleft(C+d2K/Deltaminright) where C is the total amount of corruptions, d is the maximal number of arms one can play in each round, K is the number of arms. If one selects only one arm in each round, we achieves a regret of tildeOleft(C+sumDeltai>0(1/Deltai)right). Our algorithm is combinatorial and improves on the previous combinatorial algorithm by [Gupta et al., COLT2019] (their bound is tildeOleft(KC+sumDeltai>0(1/Deltai)right)), and almost matches the best known bounds obtained by [Zimmert et al., ICML2019] and [Zimmert and Seldin, AISTATS2019] (up to logarithmic factor). Note that the algorithms in [Zimmert et al., ICML2019] and [Zimmert and Seldin, AISTATS2019] require one to solve complex convex programs while our algorithm is combinatorial, very easy to implement, requires weaker assumptions and has very low oracle complexity and running time. We also study the setting where we only get access to an approximation oracle for the stochastic combinatorial semi-bandit problem. Our algorithm achieves an (approximation) regret bound of tildeOleft(d√KTright). Our algorithm is very simple, only worse than the best known regret bound by √d, and has much lower oracle complexity than previous work.