arXiv 20 Dec 2023 · Machine Learning
arXiv:2312.12741 · PDF · DOI · OpenAlex · Extracted main text
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.
appendix boundary found by none_found · 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 | 31 | 9 | 100% |
| 2 | Peter Glynn and Sandeep Juneja (2004) A large deviations perspective on ordinal optimization | 1.000 | 7 | 4 | 100% |
| 3 | Masahiro Kato, Takuya Ishihara, Junya Honda, and Yusuke Narita (2002) Efficient adaptive experimental design for average treatment effect estimation, 2020 self | 1.000 | 6 | 3 | 100% |
| 4 | Aurélien Garivier and Emilie Kaufmann (2016) Optimal best arm identification with fixed confidence | 1.000 | 5 | 4 | 100% |
| 5 | Mark J. van der Laan (2008) The construction and analysis of adaptive group sequential designs, 2008 | 0.928 | 4 | 3 | 100% |
| 6 | Jinyong Hahn, Keisuke Hirano, and Dean Karlan (2011) Adaptive experimental design using the propensity score | 0.874 | 13 | 2 | 100% |
| 7 | Keisuke Hirano, Guido Imbens, and Geert Ridder (2003) Efficient estimation of average treatment effects using the estimated propensity score | 0.874 | 8 | 2 | 100% |
| 8 | 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% |
| 9 | Rémy Degenne (2023) On the existence of a complexity in fixed budget bandit identification | 0.737 | 3 | 2 | 100% |
| 10 | Jinyong Hahn (1998) On the role of the propensity score in efficient semiparametric estimation of average treatment effects | 0.737 | 3 | 2 | 100% |
Showing the top 10 of 48 scored citations.