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 Deltai=μ_*-μi be its gap from the optimal mean, and write H=sumine *Deltai-2. Let pr be the fraction of H contributed by arms with 2-(r+1)<Deltai≤2-r, and let Ent(I)=sumr:pr>0 prlog(1/pr). 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-2loglog(ee/g), where g=minine *Deltai is the gap to the closest competitor.