# Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithms

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 45 references that are in the map.
- First posted on arXiv 1 Sep 2023.

## Builds on (most cited first, 20 of 20)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity](https://mlsanity.com/paper/2202.13890/) (2022)
- [Settling the Sample Complexity of Model-Based Offline Reinforcement Learning](https://mlsanity.com/paper/2204.05275/) (2022)
- [On Explore-Then-Commit Strategies](https://mlsanity.com/paper/1605.08988/) (2016)
- [On the Optimality of Batch Policy Optimization Algorithms](https://mlsanity.com/paper/2104.02293/) (2021)
- [Double Explore-then-Commit: Asymptotic Optimality and Beyond](https://mlsanity.com/paper/2002.09174/) (2020)
- [Bridging the gap between regret minimization and best arm identification, with application to A/B tests](https://mlsanity.com/paper/1810.04088/) (2018)
- [Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Sets](https://mlsanity.com/paper/2205.10671/) (2022)
- [Exploration, Exploitation, and Engagement in Multi-Armed Bandits with Abandonment](https://mlsanity.com/paper/2205.13566/) (2022)
- [Risk-Averse Explore-Then-Commit Algorithms for Finite-Time Bandits](https://mlsanity.com/paper/1904.13387/) (2019)
- [Queue Scheduling with Adversarial Bandit Learning](https://mlsanity.com/paper/2303.01745/) (2023)
- [On Low-Complexity Quickest Intervention of Mutated Diffusion Processes Through Local Approximation](https://mlsanity.com/paper/2206.04733/) (2022)

## Built on by (most cited first, 10 of 10)

- [Cost Aware Best Arm Identification](https://mlsanity.com/paper/2402.16710/) (2024)
- [Best Arm Identification with Minimal Regret](https://mlsanity.com/paper/2409.18909/) (2024)
- [Reinforcement Learning from Human Feedback without Reward Inference: Model-Free Algorithm and Instance-Dependent Analysis](https://mlsanity.com/paper/2406.07455/) (2024)
- [On the Low-Complexity of Fair Learning for Combinatorial Multi-Armed Bandit](https://mlsanity.com/paper/2501.00924/) (2025)
- [Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validation](https://mlsanity.com/paper/2506.03062/) (2025)
- [Beyond the Lower Bound: Bridging Regret Minimization and Best Arm Identification in Lexicographic Bandits](https://mlsanity.com/paper/2511.05802/) (2025)
- [An Algorithm for Fixed Budget Best Arm Identification with Combinatorial Exploration](https://mlsanity.com/paper/2502.01429/) (2025)
- [Cost-Aware Optimal Pairwise Pure Exploration](https://mlsanity.com/paper/2503.07877/) (2025)
- [UCB for Large-Scale Pure Exploration: Beyond Sub-Gaussianity](https://mlsanity.com/paper/2511.22273/) (2025)
- [Experimentation and Commitment under Reward Shifts](https://mlsanity.com/paper/2607.23432/) (2026)

## Abstract (arXiv)

This paper considers a stochastic Multi-Armed Bandit (MAB) problem with dual objectives: (i) quick identification and commitment to the optimal arm, and (ii) reward maximization throughout a sequence of T consecutive rounds. Though each objective has been individually well-studied, i.e., best arm identification for (i) and regret minimization for (ii), the simultaneous realization of both objectives remains an open problem, despite its practical importance. This paper introduces Regret Optimal Best Arm Identification (ROBAI) which aims to achieve these dual objectives. To solve ROBAI with both pre-determined stopping time and adaptive stopping time requirements, we present an algorithm called EOCP and its variants respectively, which not only achieve asymptotic optimal regret in both Gaussian and general bandits, but also commit to the optimal arm in O(log T) rounds with pre-determined stopping time and O(log2 T) rounds with adaptive stopping time. We further characterize lower bounds on the commitment time (equivalent to the sample complexity) of ROBAI, showing that EOCP and its variants are sample optimal with pre-determined stopping time, and almost sample optimal with adaptive stopping time. Numerical results confirm our theoretical analysis and reveal an interesting "over-exploration" phenomenon carried by classic UCB algorithms, such that EOCP has smaller regret even though it stops exploration much earlier than UCB, i.e., O(log T) versus O(T), which suggests over-exploration is unnecessary and potentially harmful to system performance.