Masahiro Kato, Kaito Ariu, Masaaki Imaizumi, Masahiro Nomura, Chao Qin
arXiv 12 Jan 2022 · Statistics — Machine Learning
arXiv:2201.04469 · PDF · DOI · OpenAlex · Extracted main text
We consider fixed-budget best-arm identification in two-armed Gaussian bandit problems. One of the longstanding open questions is the existence of an optimal strategy under which the probability of misidentification matches a lower bound. We show that a strategy following the Neyman allocation rule (Neyman, 1934) is asymptotically optimal when the gap between the expected rewards is small. First, we review a lower bound derived by Kaufmann et al. (2016). Then, we propose the "Neyman Allocation (NA)-Augmented Inverse Probability weighting (AIPW)" strategy, which consists of the sampling rule using the Neyman allocation with an estimated standard deviation and the recommendation rule using an AIPW estimator. Our proposed strategy is optimal because the upper bound matches the lower bound when the budget goes to infinity and the gap goes to zero.
appendix boundary found by appendix_command · 38% 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 | Glynn, P. and Juneja, S (2004) A large deviations perspective on ordinal optimization | 0.950 | 7 | 6 | 86% |
| 2 | Garivier, A. and Kaufmann, E (2016) Optimal best arm identification with fixed confidence | 0.928 | 5 | 3 | 80% |
| 3 | Fan, X., Grama, I., and Liu, Q (2014) A generalization of cramér large deviations for martingales | 0.920 | 9 | 4 | 78% |
| 4 | Fan, X., Grama, I., and Liu, Q (2013) Cramér large deviation expansions for martingales under bernstein’s condition | 0.860 | 11 | 4 | 64% |
| 5 | Kaufmann, E., Cappé, O., and Garivier, A (2016) On the complexity of best-arm identification in multi-armed bandit models | 0.852 | 34 | 8 | 62% |
| 6 | Neyman, J (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% |
| 7 | Hahn, J., Hirano, K., and Karlan, D (2011) Adaptive experimental design using the propensity score | 0.811 | 5 | 2 | 80% |
| 8 | Lai, T. and Robbins, H (1985) Asymptotically efficient adaptive allocation rules | 0.737 | 4 | 4 | 50% |
| 9 | Carpentier, A. and Locatelli, A (2016) Tight (lower) bounds for the fixed budget best arm identification bandit problem | 0.737 | 3 | 3 | 67% |
| 10 | Audibert, J.-Y., Bubeck, S., and Munos, R (2010) Best arm identification in multi-armed bandits | 0.693 | 6 | 3 | 33% |
Showing the top 10 of 93 scored citations.