A positive resolution of the gap-entropy conjecture

Abstract

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 ${\Delta }_i={\mu }_{\ast }-{\mu }_i$ be its gap from the optimal mean, and write $H={\sum }_{i\ne \ast }{\Delta }_i^{-2}$. Let $p_r$ be the fraction of $H$ contributed by arms with $2^{-(r+1)}<{\Delta }_i\le 2^{-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-\delta$ 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/\delta )+\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 \ast }{\Delta }_i$ is the gap to the closest competitor.