# Locally Optimal Fixed-Budget Best Arm Identification in Two-Armed Gaussian Bandits with Unknown Variances

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 48 references that are in the map.
- First posted on arXiv 20 Dec 2023.

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

- [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)
- [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)
- [Efficient Adaptive Experimental Design for Average Treatment Effect Estimation](https://mlsanity.com/paper/2002.05308/) (2020)
- [Minimax Optimal Algorithms for Fixed-Budget Best Arm Identification](https://mlsanity.com/paper/2206.04646/) (2022)
- [On the Existence of a Complexity in Fixed Budget Bandit Identification](https://mlsanity.com/paper/2303.09468/) (2023)
- [Open Problem: Optimal Best Arm Identification with Fixed Budget](https://mlsanity.com/paper/2303.00950/) (2023)
- [Policy Choice and Best Arm Identification: Asymptotic Analysis of Exploration Sampling](https://mlsanity.com/paper/2109.08229/) (2021)
- [Stratification Trees for Adaptive Randomization in Randomized Controlled Trials](https://mlsanity.com/paper/1806.05127/) (2018)
- [Dealing with Unknown Variances in Best-Arm Identification](https://mlsanity.com/paper/2210.00974/) (2022)
- [Best Arm Identification with Fixed Budget: A Large Deviation Perspective](https://mlsanity.com/paper/2312.12137/) (2023)
- [Rate-optimal Bayesian Simple Regret in Best Arm Identification](https://mlsanity.com/paper/2111.09885/) (2021)
- [Asymptotic Efficiency Bounds for a Class of Experimental Designs](https://mlsanity.com/paper/2205.02726/) (2022)
- [On Universally Optimal Algorithms for A/B Testing](https://mlsanity.com/paper/2308.12000/) (2023)
- [Worst-Case Optimal Multi-Armed Gaussian Best Arm Identification with a Fixed Budget](https://mlsanity.com/paper/2310.19788/) (2023)

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

- [Active Adaptive Experimental Design for Treatment Effect Estimation with Covariate Choices](https://mlsanity.com/paper/2403.03589/) (2024)
- [Adaptive Experimental Design for Policy Learning](https://mlsanity.com/paper/2401.03756/) (2024)
- [Generalized Neyman Allocation for Locally Minimax Optimal Best-Arm Identification](https://mlsanity.com/paper/2405.19317/) (2024)

## Abstract (arXiv)

We address the problem of best arm identification (BAI) with a fixed budget for two-armed Gaussian bandits. In BAI, given multiple arms, we aim to find the best arm, an arm with the highest expected reward, through an adaptive experiment. Kaufmann et al. (2016) develops a lower bound for the probability of misidentifying the best arm. They also propose a strategy, assuming that the variances of rewards are known, and show that it is asymptotically optimal in the sense that its probability of misidentification matches the lower bound as the budget approaches infinity. However, an asymptotically optimal strategy is unknown when the variances are unknown. For this open issue, we propose a strategy that estimates variances during an adaptive experiment and draws arms with a ratio of the estimated standard deviations. We refer to this strategy as the Neyman Allocation (NA)-Augmented Inverse Probability weighting (AIPW) strategy. We then demonstrate that this strategy is asymptotically optimal by showing that its probability of misidentification matches the lower bound when the budget approaches infinity, and the gap between the expected rewards of two arms approaches zero (small-gap regime). Our results suggest that under the worst-case scenario characterized by the small-gap regime, our strategy, which employs estimated variance, is asymptotically optimal even when the variances are unknown.