# A positive resolution of the gap-entropy conjecture

arXiv: https://arxiv.org/abs/2609.10529 · HTML: https://mlsanity.com/paper/2609.10529/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 12 references that are in the map.
- First posted on arXiv 9 Sep 2026.

## Builds on (most cited first, 7 of 7)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime](https://mlsanity.com/paper/1702.05186/) (2017)
- [Towards Instance Optimal Bounds for Best Arm Identification](https://mlsanity.com/paper/1608.06031/) (2016)
- [On the Optimal Sample Complexity for Best Arm Identification](https://mlsanity.com/paper/1511.03774/) (2015)
- [Open Problem: Best Arm Identification: Almost Instance-Wise Optimality and the Gap Entropy Conjecture](https://mlsanity.com/paper/1605.08481/) (2016)

## Built on by (most cited first, 1 of 1)

- [Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification](https://mlsanity.com/paper/2609.13703/) (2026)

## Abstract (arXiv)

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.