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

תקציר מקורי באנגליתarXiv:2609.13703v1 Announce Type: cross 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 entrop