Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification

Abstract:In the best-arm identification problem, we are given $n$ stochastic arms with unknown means and wish to identify the arm with the largest mean with probability at least $1-\delta$, using as few samples as possible. We consider independent Gaussian rewards with unit variance and means in $[0,1]$. Chen and Li [2016] conjectured that the instance-wise sample complexity of this problem is characterized by the gap entropy, up to an additive term arising from the two-arm problem. In this paper, we resolve their gap-entropy and almost instance-wise optimality conjectures. For an instance $I$, let $\Delta_{[i]}$ be the gap between the largest and the $i$-th largest mean, let $H(I)=\sum_{i=2}^{n}\Delta_{[i]}^{-2}$, and let Ent$(I)$ denote the entropy of the normalized complexities of its dyadic gap groups. For every $0<\delta<0.1$, we show that the order-oblivious instance-wise lower bound is $ {\Theta} (H(I)[\log(1/\delta)+Ent(I)]). $ We also give a single $\delta$-correct algorithm with expected sample complexity $ O ( H(I)[\log(1/\delta)+Ent(I)] +D\log(e+\log(e+D))),D=\Delta_{[2]}^{-2}, $ without prior knowledge of the gaps. Our lower bound removes the dyadic-gap and monotonicity restrictions of previous work, and our upper bound removes the additional polylogarithmic factor multiplying the two-arm term. Thus, a single algorithm attains the instance-wise lower bound up to an additive two-arm term. The main theorems have been formalized and proved in Lean 4.

Computational Complexity (cs.CC); Artificial Intelligence (cs.AI); Machine Learning (cs.LG)

arXiv:2609.13703 [cs.CC]

(or arXiv:2609.13703v1 [cs.CC] for this version)

https://doi.org/10.48550/arXiv.2609.13703 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.