# Optimal Batched Best Arm Identification

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 45 references that are in the map.
- First posted on arXiv 21 Oct 2023.

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

- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [Gamification of Pure Exploration for Linear Bandits](https://mlsanity.com/paper/2007.00953/) (2020)
- [On Explore-Then-Commit Strategies](https://mlsanity.com/paper/1605.08988/) (2016)
- [An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits](https://mlsanity.com/paper/2006.11685/) (2020)
- [Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1904.03293/) (2019)
- [Top Two Algorithms Revisited](https://mlsanity.com/paper/2206.05979/) (2022)
- [Towards Instance Optimal Bounds for Best Arm Identification](https://mlsanity.com/paper/1608.06031/) (2016)
- [Best arm identification in multi-armed bandits with delayed feedback](https://mlsanity.com/paper/1803.10937/) (2018)
- [A minimax and asymptotically optimal algorithm for stochastic bandits](https://mlsanity.com/paper/1702.07211/) (2017)
- [Double Explore-then-Commit: Asymptotic Optimality and Beyond](https://mlsanity.com/paper/2002.09174/) (2020)
- [Collaborative Top Distribution Identifications with Limited Interaction](https://mlsanity.com/paper/2004.09454/) (2020)
- [Minimax Optimal Algorithms for Fixed-Budget Best Arm Identification](https://mlsanity.com/paper/2206.04646/) (2022)
- [On the Existence of a Complexity in Fixed Budget Bandit Identification](https://mlsanity.com/paper/2303.09468/) (2023)
- [Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits](https://mlsanity.com/paper/2004.04666/) (2020)
- [On the Optimal Sample Complexity for Best Arm Identification](https://mlsanity.com/paper/1511.03774/) (2015)
- [Pure Exploration of Multi-armed Bandit Under Matroid Constraints](https://mlsanity.com/paper/1605.07162/) (2016)
- [Non-Asymptotic Analysis of a UCB-based Top Two Algorithm](https://mlsanity.com/paper/2210.05431/) (2022)
- [An varepsilon-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond](https://mlsanity.com/paper/2305.16041/) (2023)

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

- [FOCUS: Efficient Keyframe Selection for Long Video Understanding](https://mlsanity.com/paper/2510.27280/) (2025)
- [Optimal Batched Linear Bandits](https://mlsanity.com/paper/2406.04137/) (2024)
- [Best Arm Identification with Minimal Regret](https://mlsanity.com/paper/2409.18909/) (2024)
- [The Batch Complexity of Bandit Pure Exploration](https://mlsanity.com/paper/2502.01425/) (2025)
- [Optimal and Practical Batched Linear Bandit Algorithm](https://mlsanity.com/paper/2507.08438/) (2025)
- [Non-Asymptotic Analysis of (Sticky) Track-and-Stop](https://mlsanity.com/paper/2505.22475/) (2025)
- [Sample-Adaptivity Tradeoff in On-Demand Sampling](https://mlsanity.com/paper/2511.15507/) (2025)
- [Breaking the log(1/Delta2) Barrier: Better Batched Best Arm Identification with Adaptive Grids](https://mlsanity.com/paper/2501.17370/) (2025)

## Abstract (arXiv)

We study the batched best arm identification (BBAI) problem, where the learner's goal is to identify the best arm while switching the policy as less as possible. In particular, we aim to find the best arm with probability 1-δ for some small constant δ>0 while minimizing both the sample complexity (total number of arm pulls) and the batch complexity (total number of batches). We propose the three-batch best arm identification (Tri-BBAI) algorithm, which is the first batched algorithm that achieves the optimal sample complexity in the asymptotic setting (i.e., δrightarrow 0) and runs in 3 batches in expectation. Based on Tri-BBAI, we further propose the almost optimal batched best arm identification (Opt-BBAI) algorithm, which is the first algorithm that achieves the near-optimal sample and batch complexity in the non-asymptotic setting (i.e., δ is finite), while enjoying the same batch and sample complexity as Tri-BBAI when δ tends to zero. Moreover, in the non-asymptotic setting, the complexity of previous batch algorithms is usually conditioned on the event that the best arm is returned (with a probability of at least 1-δ), which is potentially unbounded in cases where a sub-optimal arm is returned. In contrast, the complexity of Opt-BBAI does not rely on such an event. This is achieved through a novel procedure that we design for checking whether the best arm is eliminated, which is of independent interest.