# Worst-Case Optimal Multi-Armed Gaussian Best Arm Identification with a Fixed Budget

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 86 references that are in the map.
- First posted on arXiv 30 Oct 2023.

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

- [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)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Improving the Expected Improvement Algorithm](https://mlsanity.com/paper/1705.10033/) (2017)
- [Fixed-Confidence Guarantees for Bayesian Best-Arm Identification](https://mlsanity.com/paper/1910.10945/) (2019)
- [Review on Ranking and Selection: A New Perspective](https://mlsanity.com/paper/2008.00249/) (2020)
- [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)
- [Efficient Online Estimation of Causal Effects by Deciding What to Observe](https://mlsanity.com/paper/2108.09265/) (2021)
- [Variance-Dependent Best Arm Identification](https://mlsanity.com/paper/2106.10417/) (2021)
- [Asymptotic Efficiency Bounds for a Class of Experimental Designs](https://mlsanity.com/paper/2205.02726/) (2022)
- [Risk and optimal policies in bandit experiments](https://mlsanity.com/paper/2112.06363/) (2021)
- [Fixed-Budget Best-Arm Identification with Heterogeneous Reward Variances](https://mlsanity.com/paper/2306.07549/) (2023)
- [On Universally Optimal Algorithms for A/B Testing](https://mlsanity.com/paper/2308.12000/) (2023)

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

- [Locally Optimal Fixed-Budget Best Arm Identification in Two-Armed Gaussian Bandits with Unknown Variances](https://mlsanity.com/paper/2312.12741/) (2023)
- [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)

This study investigates the experimental design problem for identifying the arm with the highest expected outcome, referred to as best arm identification (BAI). In our experiments, the number of treatment-allocation rounds is fixed. During each round, a decision-maker allocates an arm and observes a corresponding outcome, which follows a Gaussian distribution with variances that can differ among the arms. At the end of the experiment, the decision-maker recommends one of the arms as an estimate of the best arm. To design an experiment, we first discuss lower bounds for the probability of misidentification. Our analysis highlights that the available information on the outcome distribution, such as means (expected outcomes), variances, and the choice of the best arm, significantly influences the lower bounds. Because available information is limited in actual experiments, we develop a lower bound that is valid under the unknown means and the unknown choice of the best arm, which are referred to as the worst-case lower bound. We demonstrate that the worst-case lower bound depends solely on the variances of the outcomes. Then, under the assumption that the variances are known, we propose the Generalized-Neyman-Allocation (GNA)-empirical-best-arm (EBA) strategy, an extension of the Neyman allocation proposed by Neyman (1934). We show that the GNA-EBA strategy is asymptotically optimal in the sense that its probability of misidentification aligns with the lower bounds as the sample size increases infinitely and the differences between the expected outcomes of the best and other suboptimal arms converge to the same values across arms. We refer to such strategies as asymptotically worst-case optimal.