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

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

## Key facts

- Cited by 79 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2016.

## Built on by (most cited first, 30 of 79)

- [RL for Latent MDPs: Regret Guarantees and a Lower Bound](https://mlsanity.com/paper/2102.04939/) (2021)
- [Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/2107.01264/) (2021)
- [On the Existence of a Complexity in Fixed Budget Bandit Identification](https://mlsanity.com/paper/2303.09468/) (2023)
- [Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environments](https://mlsanity.com/paper/2301.13446/) (2023)
- [Near-Optimal Collaborative Learning in Bandits](https://mlsanity.com/paper/2206.00121/) (2022)
- [Bandits with many optimal arms](https://mlsanity.com/paper/2103.12452/) (2021)
- [The Fragility of Optimized Bandit Algorithms](https://mlsanity.com/paper/2109.13595/) (2021)
- [Bridging Distributional and Risk-sensitive Reinforcement Learning with Provable Regret Bounds](https://mlsanity.com/paper/2210.14051/) (2022)
- [A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs](https://mlsanity.com/paper/2106.13013/) (2021)
- [Reinforcement Learning in Reward-Mixing MDPs](https://mlsanity.com/paper/2110.03743/) (2021)
- [Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Risk](https://mlsanity.com/paper/2204.00706/) (2022)
- [Regret Bounds for Markov Decision Processes with Recursive Optimized Certainty Equivalents](https://mlsanity.com/paper/2301.12601/) (2023)
- [Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations](https://mlsanity.com/paper/2106.11519/) (2021)
- [Cost Aware Best Arm Identification](https://mlsanity.com/paper/2402.16710/) (2024)
- [Confidence-Budget Matching for Sequential Budgeted Learning](https://mlsanity.com/paper/2102.03400/) (2021)
- [Best Arm Identification with Fixed Budget: A Large Deviation Perspective](https://mlsanity.com/paper/2312.12137/) (2023)
- [A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits](https://mlsanity.com/paper/2108.11345/) (2021)
- [When is Agnostic Reinforcement Learning Statistically Tractable?](https://mlsanity.com/paper/2310.06113/) (2023)
- [The Role of Contextual Information in Best Arm Identification](https://mlsanity.com/paper/2106.14077/) (2021)
- [On Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Bandits](https://mlsanity.com/paper/2210.00895/) (2022)
- [Regret Bounds for Risk-sensitive Reinforcement Learning with Lipschitz Dynamic Risk Measures](https://mlsanity.com/paper/2306.02399/) (2023)
- [Optimal Best-Arm Identification in Bandits with Access to Offline Data](https://mlsanity.com/paper/2306.09048/) (2023)
- [Be Greedy in Multi-Armed Bandits](https://mlsanity.com/paper/2101.01086/) (2021)
- [Fast Rate Learning in Stochastic First Price Bidding](https://mlsanity.com/paper/2107.01835/) (2021)
- [Bandit Quickest Changepoint Detection](https://mlsanity.com/paper/2107.10492/) (2021)
- [On Slowly-varying Non-stationary Bandits](https://mlsanity.com/paper/2110.12916/) (2021)
- [Statistical Complexity and Optimal Algorithms for Non-linear Ridge Bandits](https://mlsanity.com/paper/2302.06025/) (2023)
- [On Stopping Times of Power-one Sequential Tests: Tight Lower and Upper Bounds](https://mlsanity.com/paper/2504.19952/) (2025)
- [On Preemption and Learning in Stochastic Scheduling](https://mlsanity.com/paper/2205.15695/) (2022)
- [Multi-Fidelity Multi-Armed Bandits Revisited](https://mlsanity.com/paper/2306.07761/) (2023)

## 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.