Adaptive Generalized Neyman Allocation: Local Asymptotic Minimax Optimal Best Arm Identification

The open problem

For fixed-budget best-arm identification, worst-case upper and lower bounds on the probability of misidentifying the best arm have not matched. Whether an asymptotically minimax optimal algorithm exists has been a long-standing open question in the bandit literature and in the econometric treatment-choice literature that shares the same structure.

Result

This paper proposes the Generalized Neyman Allocation (GNA) and shows that its worst-case upper bound aligns with the worst-case lower bound in the small-gap regime, where the difference between the expected outcomes of the best and the suboptimal arms is small. Within that regime, the bounds are tight and match exactly, including constant terms.

GNA generalizes the classical Neyman allocation for two-armed problems and refines earlier best-arm identification algorithms. Restricting attention to the small-gap regime is what makes the matching possible: it is the regime in which the identification problem is genuinely hard, and it is also the regime that matters in practice, since large gaps are resolved by almost any reasonable allocation.