mlsanityData to 7 Oct 2026

Optimal Best Arm Identification in Two-Armed Bandits with a Fixed Budget under a Small Gap

arXiv 2201.04469 ↗First posted 12 Jan 2022stat.ML cs.LG econ.EMcited by 4

Not on the map. Why?

Abstract (arXiv)

We consider fixed-budget best-arm identification in two-armed Gaussian bandit problems. One of the longstanding open questions is the existence of an optimal strategy under which the probability of misidentification matches a lower bound. We show that a strategy following the Neyman allocation rule (Neyman, 1934) is asymptotically optimal when the gap between the expected rewards is small. First, we review a lower bound derived by Kaufmann et al. (2016). Then, we propose the "Neyman Allocation (NA)-Augmented Inverse Probability weighting (AIPW)" strategy, which consists of the sampling rule using the Neyman allocation with an estimated standard deviation and the recommendation rule using an AIPW estimator. Our proposed strategy is optimal because the upper bound matches the lower bound when the budget goes to infinity and the gap goes to zero.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 26 of its 111 references that are in the map. First posted on arXiv 12 Jan 2022.

Builds on

26 of 111 references.

References · 26

  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. 2018Time-uniform, nonparametric, nonasymptotic confidence sequencescited by 220
  4. 2013lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Banditscited by 148
  5. 2016Simple Bayesian Algorithms for Best Arm Identificationcited by 116
  6. 2019Confidence Intervals for Policy Evaluation in Adaptive Experimentscited by 95
  7. 2016Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problemcited by 79
  8. 2018Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervalscited by 76
  9. 2019Non-Asymptotic Pure Exploration by Solving Gamescited by 62
  10. 2017Improving the Expected Improvement Algorithmcited by 54
  11. 2020An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Banditscited by 45
  12. 2021Off-Policy Evaluation via Adaptive Weighting with Data from Contextual Banditscited by 40
14 more
  1. 2019Fixed-Confidence Guarantees for Bayesian Best-Arm Identificationcited by 38
  2. 2015The Influence Function of Semiparametric Estimatorscited by 36
  3. 2021Post-Contextual-Bandit Inferencecited by 32
  4. 2021Doubly robust Thompson sampling for linear payoffscited by 21
  5. 2021Online Multi-Armed Bandits with Adaptive Inferencecited by 21
  6. 2015Sequential Nonparametric Testing with the Law of the Iterated Logarithmcited by 19
  7. 2021A/B/n Testing with Control in the Presence of Subpopulationscited by 17
  8. 2021Policy Choice and Best Arm Identification: Asymptotic Analysis of Exploration Samplingcited by 15
  9. 2014On the Complexity of A/B Testingcited by 14
  10. 2018Stratification Trees for Adaptive Randomization in Randomized Controlled Trialscited by 14
  11. 2018Sample complexity of partition identification using multi-armed banditscited by 12
  12. 2021Efficient Online Estimation of Causal Effects by Deciding What to Observecited by 11
  13. 2021The Role of Contextual Information in Best Arm Identificationcited by 8
  14. 2019Dynamically Aggregating Diverse Informationcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 0; 2024: 1; 2025: 0; 2026: 1.

4 papers.

  1. 2022Bayesian Fixed-Budget Best-Arm Identificationcited by 12
  2. 2022On Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Banditscited by 8
  3. 2024Optimizing Sharpe Ratio: Risk-Adjusted Decision-Making in Multi-Armed Banditscited by 2
  4. 2026RouteGuard: Certifying Routing Gain in LLM Multi-Agent Systems When Complementarity Is Not Enoughcited by 1