mlsanityData to 7 Oct 2026

Optimal Best Arm Identification with Fixed Confidence

arXiv 1602.04589 ↗First posted 15 Feb 2016math.ST cs.LG stat.MLcited by 233

Not on the map. Why?

Abstract (arXiv)

We give a complete characterization of the complexity of best-arm identification in one-parameter bandit problems. We prove a new, tight lower bound on the sample complexity. We propose the `Track-and-Stop' strategy, which we prove to be asymptotically optimal. It consists in a new sampling rule (which tracks the optimal proportions of arm draws highlighted by the lower bound) and in a stopping rule named after Chernoff, for which we give a new analysis.

Key facts. Cited by 233 papers in the map (data through 7 Oct 2026). First posted on arXiv 15 Feb 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 28; 2022: 35; 2023: 37; 2024: 39; 2025: 46; 2026: 48.

233 papers.

Sort:

By area:

  1. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  2. 2024Efficient Prompt Optimization Through the Lens of Best Arm Identificationcited by 35
  3. 2021Minimax Optimal Fixed-Budget Best Arm Identification in Linear Banditscited by 32
  4. 2021Navigating to the Best Policy in Markov Decision Processescited by 28
  5. 2022Revisiting Simple Regret: Fast Rates for Returning a Good Armcited by 25
  6. 2022Minimax Optimal Algorithms for Fixed-Budget Best Arm Identificationcited by 20
  7. 2021Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedbackcited by 19
  8. 2023On the Existence of a Complexity in Fixed Budget Bandit Identificationcited by 19
  9. 2022Near-Optimal Collaborative Learning in Banditscited by 18
  10. 2023Open Problem: Optimal Best Arm Identification with Fixed Budgetcited by 18
  11. 2021A/B/n Testing with Control in the Presence of Subpopulationscited by 17
  12. 2022Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPscited by 17
38 more
  1. 2022Almost Optimal Variance-Constrained Best Arm Identificationcited by 16
  2. 2022Optimal Clustering with Bandit Feedbackcited by 15
  3. 2022Information-Directed Selection for Top-Two Algorithmscited by 15
  4. 2024On Speeding Up Language Model Evaluationcited by 14
  5. 2021Pure Exploration in Kernel and Neural Banditscited by 13
  6. 2022Bregman Deviations of Generic Exponential Familiescited by 13
  7. 2022Dealing with Unknown Variances in Best-Arm Identificationcited by 13
  8. 2023Adaptive Algorithms for Relaxed Pareto Set Identificationcited by 13
  9. 2023Bandit Pareto Set Identification: the Fixed Budget Settingcited by 13
  10. 2025Sequential Learning of the Pareto Front for Multi-objective Banditscited by 13
  11. 2023Best Arm Identification with Fixed Budget: A Large Deviation Perspectivecited by 12
  12. 2024Cost Aware Best Arm Identificationcited by 12
  13. 2024Active Adaptive Experimental Design for Treatment Effect Estimation with Covariate Choicescited by 12
  14. 2021Dealing With Misspecification In Fixed-Confidence Linear Top-m Identificationcited by 11
  15. 2022Non-Asymptotic Analysis of a UCB-based Top Two Algorithmcited by 11
  16. 2021Vector Optimization with Stochastic Bandit Feedbackcited by 10
  17. 2023Pure Exploration in Bandits with Linear Constraintscited by 10
  18. 2023Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithmscited by 10
  19. 2023Practical Bandits: An Industry Perspectivecited by 9
  20. 2024Optimizing Adaptive Experiments: A Unified Approach to Regret Minimization and Best-Arm Identificationcited by 9
  21. 2021The Role of Contextual Information in Best Arm Identificationcited by 8
  22. 2021Best-Arm Identification in Correlated Multi-Armed Banditscited by 8
  23. 2021Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffscited by 8
  24. 2022On Elimination Strategies for Bandit Fixed-Confidence Identificationcited by 8
  25. 2022On Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Banditscited by 8
  26. 2022Federated Best Arm Identification with Heterogeneous Clientscited by 8
  27. 2023Best Arm Identification with Fairness Constraints on Subpopulationscited by 8
  28. 2023Optimal Batched Best Arm Identificationcited by 8
  29. 2024Optimal Multi-Fidelity Best-Arm Identificationcited by 8
  30. 2021Diffusion Approximations for a Class of Sequential Testing Problemscited by 7
  31. 2021A Non-asymptotic Approach to Best-Arm Identification for Gaussian Banditscited by 7
  32. 2021Bandit Quickest Changepoint Detectioncited by 7
  33. 2021On Slowly-varying Non-stationary Banditscited by 7
  34. 2021Max-Min Grouped Banditscited by 7
  35. 2022Residual Bootstrap Exploration for Stochastic Linear Banditcited by 7
  36. 2024Query-Efficient Correlation Clustering with Noisy Oraclecited by 7
  37. 2024Optimal Batched Linear Banditscited by 7
  38. 2024A General Framework for Clustering and Distribution Matching with Bandit Feedbackcited by 7

50 most cited of 233 All 233 (JSON)