arXiv 30 Oct 2023 · Mathematics — Statistics Theory
arXiv:2310.19788 · PDF · DOI · OpenAlex · Extracted main text
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.
appendix boundary found by appendix_command · 69% 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 | Jerzy Neyman (1934) On the two different aspects of the representative method: the method of stratified sampling and the method of purposive selection | 1.000 | 7 | 4 | 100% |
| 2 | Rémy Degenne (2023) On the existence of a complexity in fixed budget bandit identification | 0.991 | 39 | 6 | 97% |
| 3 | Kaito Ariu, Masahiro Kato, Junpei Komiyama, Kenichiro McAlinn, and C… (2021) Policy choice and best arm identification: Asymptotic analysis of exploration sampling, 2021 self | 0.974 | 13 | 5 | 92% |
| 4 | Junpei Komiyama, Taira Tsuchiya, and Junya Honda (2022) Minimax optimal algorithms for fixed-budget best arm identification | 0.961 | 9 | 4 | 89% |
| 5 | Emilie Kaufmann (2020) Contributions to the Optimal Solution of Several Bandits Problems | 0.956 | 8 | 4 | 88% |
| 6 | Peter Glynn and Sandeep Juneja (2004) A large deviations perspective on ordinal optimization | 0.952 | 22 | 7 | 86% |
| 7 | Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier (2016) On the complexity of best-arm identification in multi-armed bandit models | 0.926 | 29 | 7 | 79% |
| 8 | Aurélien Garivier and Emilie Kaufmann (2016) Optimal best arm identification with fixed confidence | 0.874 | 9 | 5 | 67% |
| 9 | Jinyong Hahn, Keisuke Hirano, and Dean Karlan (2011) Adaptive experimental design using the propensity score | 0.874 | 6 | 5 | 67% |
| 10 | Chun-Hung Chen, Jianwu Lin, Enver Yücesan, and Stephen E. Chick (2000) Simulation budget allocation for further enhancing theefficiency of ordinal optimization | 0.843 | 4 | 3 | 75% |
Showing the top 10 of 89 scored citations.