mlsanityData to 14 Oct 2026

Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem

arXiv 1605.09004 ↗First posted 29 May 2016stat.ML cs.LGcited by 79

Not on the map. Why?

Abstract (arXiv)

We consider the problem of textitbest arm identification with a textitfixed budget T, in the K-armed stochastic bandit setting, with arms distribution defined on [0,1]. We prove that any bandit strategy, for at least one bandit problem characterized by a complexity H, will misidentify the best arm with probability lower bounded by expBig(-fracTlog(K)HBig), where H is the sum for all sub-optimal arms of the inverse of the squared gaps. Our result disproves formally the general belief - coming from results in the fixed confidence setting - that there must exist an algorithm for this problem whose probability of error is upper bounded by exp(-T/H). This also proves that some existing strategies based on the Successive Rejection of the arms are optimal - closing therefore the current gap between upper and lower bounds for the fixed budget best arm identification problem.

Key facts. Cited by 79 papers in the map (data through 14 Oct 2026). First posted on arXiv 29 May 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 8; 2022: 14; 2023: 21; 2024: 11; 2025: 11; 2026: 14.

79 papers.

Sort:

By area:

  1. 2021Minimax Optimal Fixed-Budget Best Arm Identification in Linear Banditscited by 32
  2. 2022Revisiting Simple Regret: Fast Rates for Returning a Good Armcited by 25
  3. 2021Fixed-Budget Best-Arm Identification in Structured Banditscited by 22
  4. 2022Minimax Optimal Algorithms for Fixed-Budget Best Arm Identificationcited by 20
  5. 2023On the Existence of a Complexity in Fixed Budget Bandit Identificationcited by 20
  6. 2023Open Problem: Optimal Best Arm Identification with Fixed Budgetcited by 18
  7. 2021Bandits with many optimal armscited by 17
  8. 2021Policy Choice and Best Arm Identification: Asymptotic Analysis of Exploration Samplingcited by 15
  9. 2024Hyperparameter-Free Approach for Faster Minimum Bayes Risk Decodingcited by 15
  10. 2023Bandit Pareto Set Identification: the Fixed Budget Settingcited by 14
  11. 2021Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Banditscited by 13
  12. 2022Bayesian Fixed-Budget Best-Arm Identificationcited by 13
38 more
  1. 2024Cost Aware Best Arm Identificationcited by 13
  2. 2023Best Arm Identification with Fixed Budget: A Large Deviation Perspectivecited by 12
  3. 2021Rate-optimal Bayesian Simple Regret in Best Arm Identificationcited by 11
  4. 2022Constrained Pure Exploration Multi-Armed Bandits with a Fixed Budgetcited by 9
  5. 2022On Elimination Strategies for Bandit Fixed-Confidence Identificationcited by 8
  6. 2022On Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Banditscited by 8
  7. 2023Optimal Batched Best Arm Identificationcited by 8
  8. 2022Parallel Best Arm Identification in Heterogeneous Environmentscited by 6
  9. 2023Best Arm Identification for Stochastic Rising Banditscited by 6
  10. 2023Fixed-Budget Best-Arm Identification with Heterogeneous Reward Variancescited by 6
  11. 2023On Universally Optimal Algorithms for A/B Testingcited by 6
  12. 2023On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidencecited by 6
  13. 2022Approximate Top-m Arm Identification with Heterogeneous Reward Variancescited by 5
  14. 2024Best Arm Identification with Minimal Regretcited by 5
  15. 2022Optimal Best Arm Identification in Two-Armed Bandits with a Fixed Budget under a Small Gapcited by 4
  16. 2023Price of Safety in Linear Best Arm Identificationcited by 4
  17. 2024Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm Identification in Structured Banditscited by 4
  18. 2026Multi-Drafter Speculative Decoding with Alignment Feedbackcited by 4
  19. 2021Learning the Optimal Recommendation from Explorative Userscited by 3
  20. 2022Best Arm Identification with Contextual Information under a Small Gapcited by 3
  21. 2023Asymptotically Optimal Fixed-Budget Best Arm Identification with Variance-Dependent Boundscited by 3
  22. 2023Optimal Best Arm Identification with Fixed Confidence in Restless Banditscited by 3
  23. 2023Worst-Case Optimal Multi-Armed Gaussian Best Arm Identification with a Fixed Budgetcited by 3
  24. 2023Locally Optimal Fixed-Budget Best Arm Identification in Two-Armed Gaussian Bandits with Unknown Variancescited by 3
  25. 2024Best Arm Identification with Resource Constraintscited by 3
  26. 2025Optimal Arm Elimination Algorithms for Combinatorial Banditscited by 3
  27. 2022Adaptive Identification of Populations with Treatment Benefit in Clinical Trials: Machine Learning Challenges and Solutionscited by 2
  28. 2023Adaptive Experimentation at Scale: A Computational Framework for Flexible Batchescited by 2
  29. 2024Adaptive Experimental Design for Policy Learningcited by 2
  30. 2024Fixed-Budget Differentially Private Best Arm Identificationcited by 2
  31. 2024Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budgetcited by 2
  32. 2024Optimizing Sharpe Ratio: Risk-Adjusted Decision-Making in Multi-Armed Banditscited by 2
  33. 2025Evolution of Information in Interactive Decision Making: A Case Study for Multi-Armed Banditscited by 2
  34. 2025Bandit Pareto Set Identification in a Multi-Output Linear Modelcited by 2
  35. 2026Cutting LLM Evaluation Costs with SySRs: A Bandit Algorithm that Provably Exploits Model Similaritycited by 2
  36. 2021Sequential Community Mode Estimationcited by 1
  37. 2022Suboptimal Performance of the Bayes Optimal Algorithm in Frequentist Best Arm Identificationcited by 1
  38. 2022UB3: Best Beam Identification in Millimeter Wave Systems via Pure Exploration Unimodal Banditscited by 1

50 most cited of 79 All 79 (JSON)