Positive Resolution of the Gap-Entropy Conjecture in Best-Arm Identification

A long-standing theoretical open problem in active learning has closed with a positive resolution of the gap-entropy conjecture for fixed-confidence best-arm identification. In the standard unit-variance Gaussian setting, the authors prove that optimal expected sample complexity—averaged over arm label permutations—matches $H(\log(1/\delta) + \mathrm{Ent}(I))$ up to absolute constant factors, where $\mathrm{Ent}(I)$ measures the entropy of gaps across dyadic scales. The work also constructs an instance-independent algorithm matching this bound up to an additive second-order term, establishing tight sample complexity for pure exploration.