Adaptive Generalized Neyman Allocation: Local Asymptotic Minimax Optimal Best Arm Identification
<|reference_start|>Adaptive Generalized Neyman Allocation: Local Asymptotic Minimax Optimal Best Arm Identification: This study investigates a local asymptotic minimax optimal strategy for fixed-budget best arm identification (BAI). We propose the Adaptive Generalized Neyman Allocation (AGNA) strategy and show that its worst-case upper bound of 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 strategy corresponds to a generalization of the Neyman allocation for two-armed bandits (Neyman, 1934; Kaufmann et al., 2016) and a refinement of existing strategies such as the ones proposed by Glynn & Juneja (2004) and Shin et al. (2018). Compared to Komiyama et al. (2022), which proposes a minimax rate-optimal strategy, our proposed strategy has a tighter upper bound that exactly matches the lower bound, including the constant terms, by restricting the class of distributions to the class of small-gap distributions. Our result contributes to the longstanding open issue about the existence of asymptotically optimal strategies in fixed-budget BAI, by presenting the local asymptotic minimax optimal strategy.<|reference_end|>
@article{kato2024adaptive,
    title={Adaptive Generalized Neyman Allocation: Local Asymptotic Minimax Optimal
  Best Arm Identification},
    author={Masahiro Kato},
    journal={arXiv preprint arXiv:2405.19317},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.19317},
    primaryClass={cs.LG cs.AI econ.EM stat.ME stat.ML}
}