Masahiro Kato, Masaaki Imaizumi, Takuya Ishihara, Toru Kitagawa
arXiv 6 Feb 2023 · Machine Learning · 1 citations (OpenAlex)
arXiv:2302.02988 · PDF · DOI · OpenAlex · Extracted main text
We investigate the problem of fixed-budget best arm identification (BAI) for minimizing expected simple regret. In an adaptive experiment, a decision maker draws one of multiple treatment arms based on past observations and observes the outcome of the drawn arm. After the experiment, the decision maker recommends the treatment arm with the highest expected outcome. We evaluate the decision based on the expected simple regret, which is the difference between the expected outcomes of the best arm and the recommended arm. Due to inherent uncertainty, we evaluate the regret using the minimax criterion. First, we derive asymptotic lower bounds for the worst-case expected simple regret, which are characterized by the variances of potential outcomes (leading factor). Based on the lower bounds, we propose the Two-Stage (TS)-Hirano-Imbens-Ridder (HIR) strategy, which utilizes the HIR estimator (Hirano et al., 2003) in recommending the best arm. Our theoretical analysis shows that the TS-HIR strategy is asymptotically minimax optimal, meaning that the leading factor of its worst-case expected simple regret matches our derived worst-case lower bound. Additionally, we consider extensions of our method, such as the asymptotic optimality for the probability of misidentification. Finally, we validate the proposed method's effectiveness through simulations.
appendix boundary found by appendix_command · 22% 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 | Hahn, J., Hirano, K., and Karlan, D (2011) Adaptive experimental design using the propensity score | 0.794 | 10 | 6 | 50% |
| 2 | Bubeck, S., Munos, R., and Stoltz, G (2011) Pure exploration in finitely-armed and continuous-armed bandits | 0.780 | 19 | 8 | 47% |
| 3 | Kaufmann, E., Cappé, O., and Garivier, A (2016) On the complexity of best-arm identification in multi-armed bandit models | 0.737 | 15 | 6 | 40% |
| 4 | Lai, T. and Robbins, H (1985) Asymptotically efficient adaptive allocation rules | 0.737 | 5 | 4 | 40% |
| 5 | Hirano, K., Imbens, G., and Ridder, G (2003) Efficient estimation of average treatment effects using the estimated propensity score | 0.737 | 3 | 3 | 67% |
| 6 | Audibert, J.-Y., Bubeck, S., and Munos, R (2010) Best arm identification in multi-armed bandits | 0.659 | 7 | 4 | 29% |
| 7 | Kaufmann, E (2020) Contributions to the Optimal Solution of Several Bandits Problems | 0.644 | 2 | 2 | 100% |
| 8 | van der Vaart, A (1998) Asymptotic Statistics | 0.630 | 8 | 3 | 25% |
| 9 | Hahn, J (1998) On the role of the propensity score in efficient semiparametric estimation of average treatment effects | 0.511 | 3 | 2 | 33% |
| 10 | Ariu, K., Kato, M., Komiyama, J., McAlinn, K., and Qin, C (2021) Policy choice and best arm identification: Asymptotic analysis of exploration sampling, 2021 self | 0.511 | 2 | 2 | 50% |
Showing the top 10 of 75 scored citations.