A positive resolution of the gap-entropy conjecture

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 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/δ)+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.