mlsanityData to 7 Oct 2026

Explore no more: Improved high-probability regret bounds for non-stochastic bandits

arXiv 1506.03271 ↗First posted 10 Jun 2015cs.LG stat.MLcited by 120

Not on the map. Why?

Abstract (arXiv)

This work addresses the problem of regret minimization in non-stochastic multi-armed bandit problems, focusing on performance guarantees that hold with high probability. Such results are rather scarce in the literature since proving them requires a large deal of technical effort and significant modifications to the standard, more intuitive algorithms that come only with guarantees that hold on expectation. One of these modifications is forcing the learner to sample arms from the uniform distribution at least Omega(√T) times over T rounds, which can adversely affect performance if many of the arms are suboptimal. While it is widely conjectured that this property is essential for proving high-probability regret bounds, we show in this paper that it is possible to achieve such strong results without this undesirable exploration component. Our result relies on a simple and intuitive loss-estimation strategy called Implicit eXploration (IX) that allows a remarkably clean analysis. To demonstrate the flexibility of our technique, we derive several improved high-probability bounds for various extensions of the standard multi-armed bandit framework. Finally, we conduct a simple experiment that illustrates the robustness of our implicit exploration technique.

Key facts. Cited by 120 papers in the map (data through 7 Oct 2026). First posted on arXiv 10 Jun 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2019: 1; 2020: 0; 2021: 19; 2022: 21; 2023: 25; 2024: 24; 2025: 15; 2026: 15.

120 papers.

Sort:

By area:

  1. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  2. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
  3. 2021A Simple Approach for Non-stationary Linear Banditscited by 54
  4. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  5. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  6. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  7. 2022On-Demand Sampling: Learning Optimally from Multiple Distributionscited by 39
  8. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 35
  9. 2021Leveraging Good Representations in Linear Contextual Banditscited by 29
  10. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  11. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 28
  12. 2022Near-Optimal Learning of Extensive-Form Games with Imperfect Informationcited by 26
38 more
  1. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  2. 2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
  3. 2021Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recallcited by 21
  4. 2021Nonstochastic Bandits and Experts with Arm-Dependent Delayscited by 18
  5. 2023Importance-Weighted Offline Learning Done Rightcited by 15
  6. 2024Learning Adversarial MDPs with Stochastic Hard Constraintscited by 15
  7. 2021Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structurecited by 14
  8. 2021Bandit Algorithms for Precision Medicinecited by 12
  9. 2022No-Regret Learning in Dynamic Stackelberg Gamescited by 12
  10. 2021No Weighted-Regret Learning in Adversarial Bandits with Delayscited by 11
  11. 2022Best of Both Worlds Model Selectioncited by 11
  12. 2022Adapting to game trees in zero-sum imperfect information gamescited by 11
  13. 2023A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delayscited by 11
  14. 2024Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyondcited by 11
  15. 2019Contextual Multi-armed Bandit Algorithm for Semiparametric Reward Modelcited by 10
  16. 2023Practical Contextual Bandits with Feedback Graphscited by 10
  17. 2024Multi-Armed Bandits with Interferencecited by 10
  18. 2024Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraintscited by 10
  19. 2024No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraintscited by 9
  20. 2023Meta-Learning Adversarial Bandit Algorithmscited by 8
  21. 2024Beyond Worst-case Attacks: Robust RL with Adaptive Defense via Non-dominated Policiescited by 8
  22. 2021Model Selection for Generic Contextual Banditscited by 7
  23. 2023Delayed Bandits: When Do Intermediate Observations Help?cited by 7
  24. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  25. 2023Bandits with Replenishable Knapsacks: the Best of both Worldscited by 6
  26. 2023Anytime Model Selection in Linear Banditscited by 6
  27. 2023Near-Optimal Pure Exploration in Matrix Games: A Generalization of Stochastic Bandits & Dueling Banditscited by 6
  28. 2024Efficient Contextual Bandits with Uninformed Feedback Graphscited by 6
  29. 2024Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transitioncited by 6
  30. 2024No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimizationcited by 6
  31. 2022Meta-Learning Adversarial Banditscited by 5
  32. 2022Nested banditscited by 5
  33. 2022Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphscited by 5
  34. 2023Online Learning under Budget and ROI Constraints via Weak Adaptivitycited by 5
  35. 2023Adversarial Rewards in Universal Learning for Contextual Banditscited by 5
  36. 2023Bandit Submodular Maximization for Multi-Robot Coordination in Unpredictable and Partially Observable Environmentscited by 5
  37. 2024Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraintscited by 5
  38. 2024Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsitycited by 5

50 most cited of 120 All 120 (JSON)