arXiv 23 Dec 2024 · Statistics — Machine Learning
arXiv:2412.17753 · PDF · DOI · OpenAlex · Extracted main text
This study investigates an asymptotically minimax optimal algorithm in the two-armed fixed-budget best-arm identification (BAI) problem. Given two treatment arms, the objective is to identify the arm with the highest expected outcome through an adaptive experiment. We focus on the Neyman allocation, where treatment arms are allocated following the ratio of their outcome standard deviations. Our primary contribution is to prove the minimax optimality of the Neyman allocation for the simple regret, defined as the difference between the expected outcomes of the true best arm and the estimated best arm. Specifically, we first derive a minimax lower bound for the expected simple regret, which characterizes the worst-case performance achievable under the location-shift distributions, including Gaussian distributions. We then show that the simple regret of the Neyman allocation asymptotically matches this lower bound, including the constant term, not just the rate in terms of the sample size, under the worst-case distribution. Notably, our optimality result holds without imposing locality restrictions on the distribution, such as the local asymptotic normality. Furthermore, we demonstrate that the Neyman allocation reduces to the uniform allocation, i.e., the standard randomized controlled trial, under Bernoulli distributions.
appendix boundary found by appendix_command · 100% of the source is main text. Read the extracted text to check this.
The works this paper leans on most, across its whole bibliography — not restricted to papers in our corpus. Ranked by composite intensity, which combines how often a work is mentioned, how many sections mention it, and how much of that falls in the main text rather than the appendix.
| Reference | Intensity | Mentions | Sections | Main text | |
|---|---|---|---|---|---|
| 1 | Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier (2016) On the complexity of best-arm identification in multi-armed bandit models | 1.000 | 8 | 3 | 100% |
| 2 | Masahiro Kato (2024) Locally optimal fixed-budget best arm identification in two-armed gaussian bandits with unknown variances, 2024b self | 0.737 | 3 | 2 | 100% |
| 3 | Maximilian Kasy and Anja Sautmann (2021) Adaptive treatment assignment in experiments for policy choice | 0.644 | 2 | 2 | 100% |
| 4 | Masahiro Kato (2024) Generalized neyman allocation for locally minimax optimal best-arm identification, 2024a self | 0.644 | 2 | 2 | 100% |
| 5 | Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier (2014) On the complexity of a/b testing | 0.644 | 2 | 2 | 100% |
| 6 | Karun Adusumilli (2022) Neyman allocation is minimax optimal for best arm identification with two arms, 2022 | 0.511 | 2 | 1 | 100% |
| 7 | Peter Glynn and Sandeep Juneja (2004) A large deviations perspective on ordinal optimization | 0.511 | 2 | 1 | 100% |
| 8 | Jean-Yves Audibert, Sébastien Bubeck, and Remi Munos (2010) Best arm identification in multi-armed bandits | 0.405 | 1 | 1 | 100% |
| 9 | Sébastien Bubeck, Rémi Munos, and Gilles Stoltz (2011) Pure exploration in finitely-armed and continuous-armed bandits | 0.405 | 1 | 1 | 100% |
| 10 | John Duchi (2023) Lecture notes on statistics and information theory, 2023 | 0.405 | 1 | 1 | 100% |
Showing the top 10 of 22 scored citations.