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

arXiv: https://arxiv.org/abs/2201.04469 · HTML: https://mlsanity.com/paper/2201.04469/

## Key facts

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

## Builds on (most cited first, 26 of 26)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Confidence Intervals for Policy Evaluation in Adaptive Experiments](https://mlsanity.com/paper/1911.02768/) (2019)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [Improving the Expected Improvement Algorithm](https://mlsanity.com/paper/1705.10033/) (2017)
- [An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits](https://mlsanity.com/paper/2006.11685/) (2020)
- [Off-Policy Evaluation via Adaptive Weighting with Data from Contextual Bandits](https://mlsanity.com/paper/2106.02029/) (2021)
- [Fixed-Confidence Guarantees for Bayesian Best-Arm Identification](https://mlsanity.com/paper/1910.10945/) (2019)
- [The Influence Function of Semiparametric Estimators](https://mlsanity.com/paper/1508.01378/) (2015)
- [Post-Contextual-Bandit Inference](https://mlsanity.com/paper/2106.00418/) (2021)
- [Online Multi-Armed Bandits with Adaptive Inference](https://mlsanity.com/paper/2102.13202/) (2021)
- [Doubly robust Thompson sampling for linear payoffs](https://mlsanity.com/paper/2102.01229/) (2021)
- [Sequential Nonparametric Testing with the Law of the Iterated Logarithm](https://mlsanity.com/paper/1506.03486/) (2015)
- [A/B/n Testing with Control in the Presence of Subpopulations](https://mlsanity.com/paper/2110.15573/) (2021)
- [Policy Choice and Best Arm Identification: Asymptotic Analysis of Exploration Sampling](https://mlsanity.com/paper/2109.08229/) (2021)
- [On the Complexity of A/B Testing](https://mlsanity.com/paper/1405.3224/) (2014)
- [Stratification Trees for Adaptive Randomization in Randomized Controlled Trials](https://mlsanity.com/paper/1806.05127/) (2018)
- [Sample complexity of partition identification using multi-armed bandits](https://mlsanity.com/paper/1811.05654/) (2018)
- [Efficient Online Estimation of Causal Effects by Deciding What to Observe](https://mlsanity.com/paper/2108.09265/) (2021)
- [The Role of Contextual Information in Best Arm Identification](https://mlsanity.com/paper/2106.14077/) (2021)
- [Dynamically Aggregating Diverse Information](https://mlsanity.com/paper/1910.07015/) (2019)

## Built on by (most cited first, 4 of 4)

- [Bayesian Fixed-Budget Best-Arm Identification](https://mlsanity.com/paper/2211.08572/) (2022)
- [On Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Bandits](https://mlsanity.com/paper/2210.00895/) (2022)
- [Optimizing Sharpe Ratio: Risk-Adjusted Decision-Making in Multi-Armed Bandits](https://mlsanity.com/paper/2406.06552/) (2024)
- [RouteGuard: Certifying Routing Gain in LLM Multi-Agent Systems When Complementarity Is Not Enough](https://mlsanity.com/paper/2608.07583/) (2026)

## 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.