mlsanityData to 7 Oct 2026

Open Problem: Optimal Best Arm Identification with Fixed Budget

arXiv 2303.00950 ↗First posted 2 Mar 2023cs.LG stat.MLcited by 18

Not on the map. Why?

Abstract (arXiv)

Best arm identification or pure exploration problems have received much attention in the COLT community since Bubeck et al. (2009) and Audibert et al. (2010). For any bandit instance with a unique best arm, its asymptotic complexity in the so-called fixed-confidence setting has been completely characterized in Garivier and Kaufmann (2016) and Chernoff (1959), while little is known about the asymptotic complexity in its "dual" setting called fixed-budget setting. This note discusses the open problems and conjectures about the instance-dependent asymptotic complexity in the fixed-budget setting.

Key facts. Cited by 18 papers in the map (data through 7 Oct 2026). Builds on 4 of its 10 references that are in the map. First posted on arXiv 2 Mar 2023.

Builds on

4 of 10 references.

References · 4

  1. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 280
  2. 2016Optimal Best Arm Identification with Fixed Confidencecited by 233
  3. 2016Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problemcited by 79
  4. 2021Policy Choice and Best Arm Identification: Asymptotic Analysis of Exploration Samplingcited by 15

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 5; 2024: 8; 2025: 1; 2026: 4.

18 papers.

Sort:

  1. 2023On the Existence of a Complexity in Fixed Budget Bandit Identificationcited by 19
  2. 2024On Speeding Up Language Model Evaluationcited by 14
  3. 2023Best Arm Identification with Fixed Budget: A Large Deviation Perspectivecited by 12
  4. 2024Active Preference Learning for Ordering Items In- and Out-of-samplecited by 6
  5. 2023On Universally Optimal Algorithms for A/B Testingcited by 5
  6. 2024Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm Identification in Structured Banditscited by 4
  7. 2023Worst-Case Optimal Multi-Armed Gaussian Best Arm Identification with a Fixed Budgetcited by 3
  8. 2023Locally Optimal Fixed-Budget Best Arm Identification in Two-Armed Gaussian Bandits with Unknown Variancescited by 3
  9. 2024Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budgetcited by 2
  10. 2024Constrained Best Arm Identification in Grouped Banditscited by 2
  11. 2024Adaptive Experimental Design for Policy Learningcited by 1
  12. 2024Generalized Neyman Allocation for Locally Minimax Optimal Best-Arm Identificationcited by 1
6 more
  1. 2024UCB Exploration for Fixed-Budget Bayesian Best Arm Identificationcited by 1
  2. 2025Admissibility of Completely Randomized Trials: A Large-Deviation Approachcited by 1
  3. 2026Fixed-Budget Constrained Best Arm Identification in Grouped Banditscited by 1
  4. 2026Cutting LLM Evaluation Costs with SySRs: A Bandit Algorithm that Provably Exploits Model Similaritycited by 1
  5. 2026Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factorscited by 0
  6. 2026Fundamental Limitations of Fixed-Budget Best-Arm Identificationcited by 0