mlsanityData to 7 Oct 2026

Rate-optimal Bayesian Simple Regret in Best Arm Identification

arXiv 2111.09885 ↗First posted 18 Nov 2021cs.LG stat.MLcited by 11

Not on the map. Why?

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.

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

Builds on

10 of 41 references.

References · 10

  1. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 280
  2. 2014Learning to Optimize via Information-Directed Samplingcited by 168
  3. 2016Simple Bayesian Algorithms for Best Arm Identificationcited by 116
  4. 2016Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problemcited by 79
  5. 2017Improving the Expected Improvement Algorithmcited by 54
  6. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 52
  7. 2019Fixed-Confidence Guarantees for Bayesian Best-Arm Identificationcited by 38
  8. 2020Review on Ranking and Selection: A New Perspectivecited by 28
  9. 2016On Sequential Elimination Algorithms for Best-Arm Identification in Multi-Armed Banditscited by 12
  10. 2019A Note on the Equivalence of Upper Confidence Bounds and Gittins Indices for Patient Agentscited by 2

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 6; 2025: 3.

11 papers.

  1. 2024Efficient Prompt Optimization Through the Lens of Best Arm Identificationcited by 35
  2. 2024Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm Identification in Structured Banditscited by 4
  3. 2023Locally Optimal Fixed-Budget Best Arm Identification in Two-Armed Gaussian Bandits with Unknown Variancescited by 3
  4. 2023Best Arm Identification in Batched Multi-armed Bandit Problemscited by 1
  5. 2024Adaptive Experimental Design for Policy Learningcited by 1
  6. 2024Generalized Neyman Allocation for Locally Minimax Optimal Best-Arm Identificationcited by 1
  7. 2024UCB Exploration for Fixed-Budget Bayesian Best Arm Identificationcited by 1
  8. 2024Fixed Confidence Best Arm Identification in the Bayesian Settingcited by 0
  9. 2025An Algorithm for Fixed Budget Best Arm Identification with Combinatorial Explorationcited by 0
  10. 2025No-regret incentive-compatible online learning under exact truthfulness with non-myopic expertscited by 0
  11. 2025Minimax and Bayes Optimal Adaptive Experimental Design for Treatment Choicecited by 0