Generalized Neyman Allocation for Locally Minimax Optimal Best-Arm Identification
This study investigates an asymptotically locally minimax optimal algorithm for fixed-budget best-arm identification (BAI). We propose the Generalized Neyman Allocation (GNA) algorithm and demonstrate that its worst-case upper bound on 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 lower and upper bounds are tight, matching exactly including constant terms within the small-gap regime. The GNA algorithm generalizes the Neyman allocation for two-armed bandits (Neyman, 1934; Kaufmann et al., 2016) and refines existing BAI algorithms, such as those proposed by Glynn & Juneja (2004). By proposing an asymptotically minimax optimal algorithm, we address the longstanding open issue in BAI (Kaufmann, 2020) and treatment choice (Kasy & Sautmann, 202) by restricting a class of distributions to the small-gap regimes.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Minimax Optimal Simple Regret in Two-Armed Best-Arm Identification
This study investigates an asymptotically minimax optimal algorithm in the two-armed fixed-budget best-arm identification (BAI) problem. Given two treatment arms, the objective is to identify the arm with the highest exp…
Neyman allocation is minimax optimal for best arm identification with two arms
This note describes the optimal policy rule, according to the local asymptotic minimax regret criterion, for best arm identification when there are only two treatments. It is shown that the optimal sampling rule is the N…
How to sample and when to stop sampling: The generalized Wald problem and minimax policies
We study sequential experiments where sampling is costly and a decision-maker aims to determine the best treatment for full scale implementation by (1) adaptively allocating units between two possible treatments, and (2)…
Experimental DesignMinimax and Bayes Optimal Adaptive Experimental Design for Treatment Choice
We consider an adaptive experiment for treatment choice and design a minimax and Bayes optimal adaptive experiment with respect to regret. Given binary treatments, the experimenter's goal is to choose the treatment with …
Optimal Best Arm Identification in Two-Armed Bandits with a Fixed Budget under a Small Gap
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 matc…
Causal Inference