← All papers

The Universal Price of Best-Arm Identification

Abstract

The static oracle for fixed-budget best-arm identification knows the arm means and selects the allocation with the best error exponent. No adaptive algorithm can match this oracle on every instance when there are at least three arms. How large must the worst-case loss be? For unit-variance Gaussian arms, we determine this price to within an additive constant below $0.2$ for every number $K$ of arms. If $P_K$ is the smallest possible worst-case ratio between the oracle and algorithmic error exponents, then $C_K\leq P_K\leq U_K, 0<U_K-C_K<0.2,$ where both endpoints are explicit sequences and equal $\log K+O(1)$. Thus the exact leading constant in the price of universality is one. The lower bound strengthens a recent impossibility result using a translated equal-gap hard family. The upper bound is constructive. We optimize the batch lengths of a successive-elimination design and prove that its exponent is at least $\Gamma_{so}^\star/U_K$ on every instance. The schedule is exactly minimax within the full class of fixed-weight, one-at-a-time batched elimination designs. The key is a sharp information inequality relating the static oracle to the large-deviation cost of incorrectly eliminating the best arm. Equal-gap active sets are the unique extremizers. The optimized design strictly improves the classical Successive Rejects worst-case ratio for every $K\geq3$.

Keywords: best-arm identification, fixed-budget, pure exploration, multi-armed bandits, successive rejects, minimax

Full text (PDF) · source repository · doi:10.5281/zenodo.21698597