mlsanityData to 7 Oct 2026

Explore First, Exploit Next: The True Shape of Regret in Bandit Problems

arXiv 1602.07182 ↗First posted 23 Feb 2016math.ST cs.LG stat.THcited by 78

Not on the map. Why?

Abstract (arXiv)

We revisit lower bounds on the regret in the case of multi-armed bandit problems. We obtain non-asymptotic, distribution-dependent bounds and provide straightforward proofs based only on well-known properties of Kullback-Leibler divergences. These bounds show in particular that in an initial phase the regret grows almost linearly, and that the well-known logarithmic growth of the regret only holds in a final phase. The proof techniques come to the essence of the information-theoretic arguments used and they are deprived of all unnecessary complications.

Key facts. Cited by 78 papers in the map (data through 7 Oct 2026). First posted on arXiv 23 Feb 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 17; 2022: 11; 2023: 20; 2024: 6; 2025: 14; 2026: 10.

78 papers.

Sort:

By area:

  1. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
  2. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 33
  3. 2023On the Existence of a Complexity in Fixed Budget Bandit Identificationcited by 19
  4. 2022Near-Optimal Collaborative Learning in Banditscited by 18
  5. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17
  6. 2021Bandits with many optimal armscited by 16
  7. 2022Bridging Distributional and Risk-sensitive Reinforcement Learning with Provable Regret Boundscited by 16
  8. 2021A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPscited by 15
  9. 2021The Fragility of Optimized Bandit Algorithmscited by 15
  10. 2021Reinforcement Learning in Reward-Mixing MDPscited by 15
  11. 2022Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Riskcited by 14
  12. 2023Regret Bounds for Markov Decision Processes with Recursive Optimized Certainty Equivalentscited by 14
38 more
  1. 2021Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observationscited by 13
  2. 2023Best Arm Identification with Fixed Budget: A Large Deviation Perspectivecited by 12
  3. 2024Cost Aware Best Arm Identificationcited by 12
  4. 2021Confidence-Budget Matching for Sequential Budgeted Learningcited by 11
  5. 2021A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Banditscited by 9
  6. 2021The Role of Contextual Information in Best Arm Identificationcited by 8
  7. 2022On Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Banditscited by 8
  8. 2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 8
  9. 2021Fast Rate Learning in Stochastic First Price Biddingcited by 7
  10. 2021Bandit Quickest Changepoint Detectioncited by 7
  11. 2021On Slowly-varying Non-stationary Banditscited by 7
  12. 2023Statistical Complexity and Optimal Algorithms for Non-linear Ridge Banditscited by 7
  13. 2023Regret Bounds for Risk-sensitive Reinforcement Learning with Lipschitz Dynamic Risk Measurescited by 7
  14. 2021Be Greedy in Multi-Armed Banditscited by 6
  15. 2022On Preemption and Learning in Stochastic Schedulingcited by 6
  16. 2023Multi-Fidelity Multi-Armed Bandits Revisitedcited by 6
  17. 2023Optimal Best-Arm Identification in Bandits with Access to Offline Datacited by 6
  18. 2023Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendationcited by 6
  19. 2021Problem Dependent View on Structured Thresholding Bandit Problemscited by 5
  20. 2022Instance-Dependent Regret Analysis of Kernelized Banditscited by 5
  21. 2022Reward-Mixing MDPs with a Few Latent Contexts are Learnablecited by 5
  22. 2023On Universally Optimal Algorithms for A/B Testingcited by 5
  23. 2025On Stopping Times of Power-one Sequential Tests: Tight Lower and Upper Boundscited by 5
  24. 2023Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewardscited by 4
  25. 2023Prospective Side Information for Latent MDPscited by 4
  26. 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
  27. 2022Square-root regret bounds for continuous-time episodic Markov decision processescited by 3
  28. 2024Sample Complexity Bounds for Linear System Identification from a Finite Setcited by 3
  29. 2025Pure Exploration with Feedback Graphscited by 3
  30. 2022Near-Optimal Algorithms for Autonomous Exploration and Multi-Goal Stochastic Shortest Pathcited by 2
  31. 2022On the Complexity of Representation Learning in Contextual Linear Banditscited by 2
  32. 2023Communication-Efficient Collaborative Regret Minimization in Multi-Armed Banditscited by 2
  33. 2023Sharp Deviations Bounds for Dirichlet Weighted Sums with Application to analysis of Bayesian algorithmscited by 2
  34. 2023CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruptioncited by 2
  35. 2023Anytime-valid t-tests and confidence sequences for Gaussian means with unknown variancecited by 2
  36. 2024Replicability is Asymptotically Free in Multi-armed Banditscited by 2
  37. 2024Stable Matching with Ties: Approximation Ratios and Learningcited by 2
  38. 2025Evolution of Information in Interactive Decision Making: A Case Study for Multi-Armed Banditscited by 2

50 most cited of 78 All 78 (JSON)