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,\qquad 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_{\mathrm{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$.

Main results

Proposition. For every feasible schedule $q$ and every $T$,

$$ p_{\mu,T}(\mathrm{BAE}(q)) \leq\sum_{j=2}^K {K-1\choose j-1} \exp\{-N_jI_j(\mu)\}. $$

If $N_j=0$, its summand is interpreted as one. Consequently,

$$ \Gamma_{\mathrm{BAE}(q)}(\mu) \geq \min_{2\leq j\leq K}q_jI_j(\mu). $$

Theorem. For every $\mu\in\mathcal M_K$ and $j\in\{2,\ldots,K\}$,

$$ \Gamma_{\mathrm{so}}^\star(\mu)\leq a_j I_j(\mu), \qquad a_j=\frac{j}{(j-1)(1+\sqrt{j-1})^2}. $$

The constant is sharp. Equality is approached by instances whose closest $j-1$ challengers have one common gap and whose remaining gaps diverge.

Theorem. The optimized batched elimination design is consistent and satisfies

$$ \Gamma_{\mathrm{BAE}(q^\star)}(\mu) \geq\frac{\Gamma_{\mathrm{so}}^\star(\mu)}{U_K} \quad\text{for every }\mu\in\mathcal M_K. $$

Consequently, $P_K\leq U_K$.

Theorem. For every feasible cumulative schedule $q$,

$$ \sup_{\mu\in\mathcal M_K} \frac{\Gamma_{\mathrm{so}}^\star(\mu)}{\Gamma_{\mathrm{BAE}(q)}(\mu)} = \max_{2\leq j\leq K}\frac{a_j}{q_j}, $$

with either side infinite if some $q_j=0$. Therefore

$$ \inf_{q\text{ feasible}}\sup_\mu \frac{\Gamma_{\mathrm{so}}^\star(\mu)}{\Gamma_{\mathrm{BAE}(q)}(\mu)}=U_K, $$

and $q^\star$ is the unique optimal cumulative schedule.

Keywords

best-arm identification, fixed budget, error exponents, pure exploration, minimax, universality

Files

• main_old_2026-07-30.pdf, the paper as first published, with its OpenTimestamps proof main_old_2026-07-30.pdf.ots.
• main.pdf, the current version.
• supplement_old_2026-07-30.pdf, the supplement as first published, with its OpenTimestamps proof supplement_old_2026-07-30.pdf.ots.
• supplement.pdf, the current version.
• source: aistats2027.sty, main.tex, references.bib, supplement.tex.
• also: main.bbl, supplement.bbl.