arXiv 29 May 2024 · Machine Learning
arXiv:2405.19317 · PDF · DOI · OpenAlex · Extracted main text
This study investigates an asymptotically locally minimax optimal algorithm for fixed-budget best-arm identification (BAI). We propose the Generalized Neyman Allocation (GNA) algorithm and demonstrate that its worst-case upper bound on the probability of misidentifying the best arm aligns with the worst-case lower bound under the small-gap regime, where the gap between the expected outcomes of the best and suboptimal arms is small. Our lower and upper bounds are tight, matching exactly including constant terms within the small-gap regime. The GNA algorithm generalizes the Neyman allocation for two-armed bandits (Neyman, 1934; Kaufmann et al., 2016) and refines existing BAI algorithms, such as those proposed by Glynn & Juneja (2004). By proposing an asymptotically minimax optimal algorithm, we address the longstanding open issue in BAI (Kaufmann, 2020) and treatment choice (Kasy & Sautmann, 202) by restricting a class of distributions to the small-gap regimes.
appendix boundary found by appendix_command · 57% 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 | Maximilian Kasy and Anja Sautmann (2021) Adaptive treatment assignment in experiments for policy choice | 1.000 | 13 | 4 | 100% |
| 2 | Peter Glynn and Sandeep Juneja (2004) A large deviations perspective on ordinal optimization | 1.000 | 10 | 4 | 100% |
| 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 | 1.000 | 9 | 3 | 100% |
| 4 | Masahiro Kato, Takuya Ishihara, Junya Honda, and Yusuke Narita (2002) Efficient adaptive experimental design for average treatment effect estimation, 2020 self | 1.000 | 7 | 4 | 100% |
| 5 | Rémy Degenne (2023) On the existence of a complexity in fixed budget bandit identification | 0.971 | 12 | 4 | 92% |
| 6 | Junpei Komiyama, Taira Tsuchiya, and Junya Honda (2022) Minimax optimal algorithms for fixed-budget best arm identification | 0.928 | 5 | 3 | 80% |
| 7 | Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier (2016) On the complexity of best-arm identification in multi-armed bandit models | 0.867 | 23 | 5 | 65% |
| 8 | Aurélien Garivier and Emilie Kaufmann (2016) Optimal best arm identification with fixed confidence | 0.843 | 4 | 3 | 75% |
| 9 | Alexandra Carpentier and Andrea Locatelli (2016) Tight (lower) bounds for the fixed budget best arm identification bandit problem | 0.843 | 3 | 3 | 100% |
| 10 | Jerzy Neyman (1934) On the two different aspects of the representative method: the method of stratified sampling and the method of purposive selection | 0.843 | 3 | 3 | 100% |
Showing the top 10 of 62 scored citations.