Search papers, labs, and topics across Lattice.
The authors resolve the longstanding gap-entropy conjecture in multi-armed bandit theory, establishing the minimax sample complexity of fixed-confidence best-arm identification for unit-variance Gaussian arms. Classical sample complexity bounds scaling purely as $H \log(1/\delta)$ break down in the moderate-confidence regime where permutation invariance forces algorithms to discover the instance's multi-scale structure. They prove that the permutation-averaged optimal sample complexity is tightly bounded within absolute constants by $\Theta(H(\log(1/\delta) + \mathrm{Ent}(I)))$, and provide an instance-independent algorithm matching this bound up to an additive $g^{-2}\log\log(e^e/g)$ term.
Classical hardness measures miss an entire dimension of bandit exploration: best-arm identification complexity is fundamentally dictated by the Shannon entropy of gap distributions across dyadic scales.
We prove the gap-entropy conjecture for fixed-confidence best-arm identification with independent unit-variance Gaussian arms, means in $[0,1]$, and a unique optimal arm. For each suboptimal arm $i$, let $螖_i=渭_*-渭_i$ be its gap from the optimal mean, and write $H=\sum_{i\ne *}螖_i^{-2}$. Let $p_r$ be the fraction of $H$ contributed by arms with $2^{-(r+1)}<螖_i\le2^{-r}$, and let $\mathrm{Ent}(I)=\sum_{r:p_r>0} p_r\log(1/p_r)$. Among all algorithms that identify the optimal arm with probability at least $1-未$ on every Gaussian instance, the optimal expected number of samples on a given instance, averaged over all permutations of the arm labels, is within absolute constant factors of $H(\log(1/未)+\mathrm{Ent}(I))$. Moreover, there is an algorithm, independent of the instance, whose expected number of samples is bounded by a constant multiple of this quantity plus $g^{-2}\log\log(e^e/g)$, where $g=\min_{i\ne *}螖_i$ is the gap to the closest competitor.
