# Rate-optimal Bayesian Simple Regret in Best Arm Identification

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 41 references that are in the map.
- First posted on arXiv 18 Nov 2021.

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

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [Improving the Expected Improvement Algorithm](https://mlsanity.com/paper/1705.10033/) (2017)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [Fixed-Confidence Guarantees for Bayesian Best-Arm Identification](https://mlsanity.com/paper/1910.10945/) (2019)
- [Review on Ranking and Selection: A New Perspective](https://mlsanity.com/paper/2008.00249/) (2020)
- [On Sequential Elimination Algorithms for Best-Arm Identification in Multi-Armed Bandits](https://mlsanity.com/paper/1609.02606/) (2016)
- [A Note on the Equivalence of Upper Confidence Bounds and Gittins Indices for Patient Agents](https://mlsanity.com/paper/1904.04732/) (2019)

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

- [Efficient Prompt Optimization Through the Lens of Best Arm Identification](https://mlsanity.com/paper/2402.09723/) (2024)
- [Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm Identification in Structured Bandits](https://mlsanity.com/paper/2402.05878/) (2024)
- [Locally Optimal Fixed-Budget Best Arm Identification in Two-Armed Gaussian Bandits with Unknown Variances](https://mlsanity.com/paper/2312.12741/) (2023)
- [Adaptive Experimental Design for Policy Learning](https://mlsanity.com/paper/2401.03756/) (2024)
- [Best Arm Identification in Batched Multi-armed Bandit Problems](https://mlsanity.com/paper/2312.13875/) (2023)
- [Generalized Neyman Allocation for Locally Minimax Optimal Best-Arm Identification](https://mlsanity.com/paper/2405.19317/) (2024)
- [UCB Exploration for Fixed-Budget Bayesian Best Arm Identification](https://mlsanity.com/paper/2408.04869/) (2024)
- [Fixed Confidence Best Arm Identification in the Bayesian Setting](https://mlsanity.com/paper/2402.10429/) (2024)
- [An Algorithm for Fixed Budget Best Arm Identification with Combinatorial Exploration](https://mlsanity.com/paper/2502.01429/) (2025)
- [No-regret incentive-compatible online learning under exact truthfulness with non-myopic experts](https://mlsanity.com/paper/2502.11483/) (2025)
- [Minimax and Bayes Optimal Adaptive Experimental Design for Treatment Choice](https://mlsanity.com/paper/2512.08513/) (2025)

## Abstract (arXiv)

We consider best arm identification in the multi-armed bandit problem. Assuming certain continuity conditions of the prior, we characterize the rate of the Bayesian simple regret. Differing from Bayesian regret minimization (Lai, 1987), the leading term in the Bayesian simple regret derives from the region where the gap between optimal and suboptimal arms is smaller than √fraclog TT. We propose a simple and easy-to-compute algorithm with its leading term matching with the lower bound up to a constant factor; simulation results support our theoretical findings.