mlsanityData to 14 Oct 2026

Simple Combinatorial Algorithms for Combinatorial Bandits: Corruptions and Approximations

arXiv 2106.06712 ↗First posted 12 Jun 2021cs.LGcited by 4

Not on the map. Why?

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.

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

11 of 25 references.

References · 11

  1. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 124
  2. 2018Stochastic bandits robust to adversarial corruptionscited by 119
  3. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 92
  4. 2018Thompson Sampling for Combinatorial Semi-Banditscited by 78
  5. 2016Combinatorial Multi-Armed Bandit with General Reward Functionscited by 56
  6. 2019Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneouslycited by 53
  7. 2016An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial banditscited by 47
  8. 2017An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Banditscited by 43
  9. 2017Efficient Online Linear Optimization with Approximation Algorithmscited by 12
  10. 2018Online Improper Learning with an Approximation Oraclecited by 11
  11. 2019What You See May Not Be What You Get: UCB Bandit Algorithms Robust to ε-Contaminationcited by 6

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 0; 2025: 3.

4 papers.

  1. 2025Bayesian Optimization with Inexact Acquisition: Is Random Grid Search Sufficient?cited by 5
  2. 2025Practical Adversarial Attacks on Stochastic Bandits via Fake Data Injectioncited by 3
  3. 2023Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Banditcited by 1
  4. 2025Online Learning to Rank under Corruption: A Robust Cascading Bandits Approachcited by 0