A positive resolution of the gap-entropy conjecture
New proof resolves the gap-entropy conjecture for Gaussian bandits, bounding optimal best-arm identification samples by H(log(1/delta)+Ent(I)) up to constants.
A paper proves 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. It shows the optimal expected sample count, averaged over arm-label permutations, is within absolute constant factors of H(log(1/delta)+Ent(I)), where H sums squared gaps and Ent(I) is the instance's gap-entropy. It also gives an instance-independent algorithm bounded by a constant multiple of this quantity plus a g^-2 loglog(e^e/g) term for the smallest gap g.