mlsanityData to 7 Oct 2026

Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously

arXiv 1901.08779 ↗First posted 25 Jan 2019cs.LG stat.MLcited by 53

Not on the map. Why?

Abstract (arXiv)

We develop the first general semi-bandit algorithm that simultaneously achieves O(log T) regret for stochastic environments and O(√T) regret for adversarial environments without knowledge of the regime or the number of rounds T. The leading problem-dependent constants of our bounds are not only optimal in some worst-case sense studied previously, but also optimal for two concrete instances of semi-bandit problems. Our algorithm and analysis extend the recent work of (Zimmert & Seldin, 2019) for the special case of multi-armed bandit, but importantly requires a novel hybrid regularizer designed specifically for semi-bandit. Experimental results on synthetic data show that our algorithm indeed performs well uniformly over different environments. We finally provide a preliminary extension of our results to the full bandit feedback.

Key facts. Cited by 53 papers in the map (data through 7 Oct 2026). First posted on arXiv 25 Jan 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 11; 2022: 6; 2023: 11; 2024: 8; 2025: 10; 2026: 7.

53 papers.

Sort:

  1. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  2. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  3. 2021Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimizationcited by 40
  4. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
  5. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 29
  6. 2022Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphscited by 26
  7. 2021On Optimal Robustness to Adversarial Corruption in Online Decision Problemscited by 20
  8. 2022Best-of-Both-Worlds Algorithms for Partial Monitoringcited by 19
  9. 2021An Algorithm for Stochastic and Adversarial Bandits with Switching Costscited by 18
  10. 2022A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphscited by 17
  11. 2023Best of Both Worlds Policy Optimizationcited by 17
  12. 2021Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptionscited by 15
38 more
  1. 2023A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPscited by 15
  2. 2023Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Boundscited by 13
  3. 2022Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Boundscited by 12
  4. 2023Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithmcited by 11
  5. 2024Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worldscited by 11
  6. 2023Best-of-Both-Worlds Algorithms for Linear Contextual Banditscited by 10
  7. 2023Banker Online Mirror Descent: A Universal Approach for Delayed Online Bandit Learningcited by 7
  8. 2024Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyondcited by 7
  9. 2021Combinatorial Bandits under Strategic Manipulationscited by 6
  10. 2024Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecificationcited by 6
  11. 2023Learning and Collusion in Multi-unit Auctionscited by 5
  12. 2025Offline Learning for Combinatorial Multi-armed Banditscited by 5
  13. 2025Efficient Near-Optimal Algorithm for Online Shortest Paths in Directed Acyclic Graphs with Bandit Feedback Against Adaptive Adversariescited by 5
  14. 2021Simple Combinatorial Algorithms for Combinatorial Bandits: Corruptions and Approximationscited by 4
  15. 2021Best-of-All-Worlds Bounds for Online Learning with Feedback Graphscited by 4
  16. 2022Linear Combinatorial Semi-Bandit with Causally Related Rewardscited by 4
  17. 2024LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Banditscited by 4
  18. 2026Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularizationcited by 4
  19. 2023Understanding the Role of Feedback in Online Learning with Switching Costscited by 3
  20. 2024Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoringcited by 3
  21. 2024A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of Theta(T2/3) and its Application to Best-of-Both-Worldscited by 3
  22. 2024Optimism in the Face of Ambiguity Principle for Multi-Armed Banditscited by 3
  23. 2025Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations in Bandit Problemscited by 3
  24. 2022Simultaneously Learning Stochastic and Adversarial Bandits under the Position-Based Modelcited by 2
  25. 2025Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problemscited by 2
  26. 2025Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Banditscited by 2
  27. 2023Non-stationary Delayed Combinatorial Semi-Bandit with Causally Related Rewardscited by 1
  28. 2025Last-Iterate Analyses of FTRL with the 1/2-Tsallis Entropy in Stochastic Banditscited by 1
  29. 2021Learning-based decentralized offloading decision making in an adversarial environmentcited by 0
  30. 2023Master-slave Deep Architecture for Top-K Multi-armed Bandits with Non-linear Bandit Feedback and Diversity Constraintscited by 0
  31. 2024Adversarial Combinatorial Bandits with Switching Costscited by 0
  32. 2025A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyondcited by 0
  33. 2025Note on Follow-the-Perturbed-Leader in Combinatorial Semi-Bandit Problemscited by 0
  34. 2025Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Banditscited by 0
  35. 2025Multi-Play Combinatorial Semi-Bandit Problemcited by 0
  36. 2026Best-of-Both-Worlds Multi-Dueling Bandits: Unified Algorithms for Stochastic and Adversarial Preferences under Condorcet and Borda Objectivescited by 0
  37. 2026Efficient Online Conformal Selection with Limited Feedbackcited by 0
  38. 2026Learning to Bid in FCR Markets: A Best-of-Both-Worlds Approachcited by 0

50 most cited of 53 All 53 (JSON)