Masahiro Kato, Masaaki Imaizumi, Takuya Ishihara, Toru Kitagawa
arXiv 15 Sep 2022 · Machine Learning
arXiv:2209.07330 · PDF · DOI · OpenAlex · Extracted main text
We study the best-arm identification (BAI) problem with a fixed budget and contextual (covariate) information. In each round of an adaptive experiment, after observing contextual information, we choose a treatment arm using past observations and current context. Our goal is to identify the best treatment arm, which is a treatment arm with the maximal expected reward marginalized over the contextual distribution, with a minimal probability of misidentification. In this study, we consider a class of nonparametric bandit models that converge to location-shift models when the gaps go to zero. First, we derive lower bounds of the misidentification probability for a certain class of strategies and bandit models (probabilistic models of potential outcomes) under a small-gap regime. A small-gap regime is a situation where gaps of the expected rewards between the best and suboptimal treatment arms go to zero, which corresponds to one of the worst cases in identifying the best treatment arm. We then develop the “Random Sampling (RS)-Augmented Inverse Probability weighting (AIPW) strategy,” which is asymptotically optimal in the sense that the probability of misidentification under the strategy matches the lower bound when the budget goes to infinity in the small-gap regime. The RS-AIPW strategy consists of the RS rule tracking a target sample allocation ratio and the recommendation rule using the AIPW estimator.
appendix boundary found by appendix_command · 41% 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 | Carpentier, A. and Locatelli, A (2016) Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem, in | 1.000 | 9 | 3 | 100% |
| 2 | Kato, M., Ariu, K., Imaizumi, M., Uehara, M., Nomura, M., and Qin, C (2022) Best Arm Identification with a Fixed Budget under a Small Gap self | 1.000 | 8 | 5 | 100% |
| 3 | Garivier, A. and Kaufmann, E (2016) Optimal Best Arm Identification with Fixed Confidence, in | 1.000 | 6 | 4 | 100% |
| 4 | Hahn, J., Hirano, K., and Karlan, D (2011) Adaptive experimental design using the propensity score | 1.000 | 6 | 4 | 100% |
| 5 | Kato, M., Ishihara, T., Honda, J., and Narita, Y (2020) Adaptive Experimental Design for Efficient Treatment Effect Estimation: Randomized Allocation via Contextual Bandit Algorithm self | 1.000 | 6 | 3 | 100% |
| 6 | van der Laan, M. J (2008) The Construction and Analysis of Adaptive Group Sequential Designs | 1.000 | 6 | 3 | 100% |
| 7 | Audibert, J.-Y., Bubeck, S., and Munos, R (2010) Best Arm Identification in Multi-Armed Bandits, in | 1.000 | 5 | 3 | 100% |
| 8 | Fan, X., Grama, I., and Liu, Q (2014) A generalization of Cramér large deviations for martingales | 0.961 | 9 | 4 | 89% |
| 9 | Lai, T. and Robbins, H (1985) Asymptotically efficient adaptive allocation rules | 0.941 | 6 | 4 | 83% |
| 10 | Kaufmann, E., Cappé, O., and Garivier, A (2016) On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models | 0.931 | 26 | 5 | 81% |
Showing the top 10 of 102 scored citations.