# Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 37 references that are in the map.
- First posted on arXiv 12 Sep 2026.

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

- [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)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [The Lean mathematical library](https://mlsanity.com/paper/1910.09336/) (2019)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [Pure Exploration with Multiple Correct Answers](https://mlsanity.com/paper/1902.03475/) (2019)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [Fixed-Confidence Guarantees for Bayesian Best-Arm Identification](https://mlsanity.com/paper/1910.10945/) (2019)
- [Top Two Algorithms Revisited](https://mlsanity.com/paper/2206.05979/) (2022)
- [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)
- [Information-Directed Selection for Top-Two Algorithms](https://mlsanity.com/paper/2205.12086/) (2022)
- [On the Complexity of A/B Testing](https://mlsanity.com/paper/1405.3224/) (2014)
- [Structured Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1706.05198/) (2017)
- [Non-Asymptotic Analysis of a UCB-based Top Two Algorithm](https://mlsanity.com/paper/2210.05431/) (2022)
- [Open Problem: Best Arm Identification: Almost Instance-Wise Optimality and the Gap Entropy Conjecture](https://mlsanity.com/paper/1605.08481/) (2016)
- [A positive resolution of the gap-entropy conjecture](https://mlsanity.com/paper/2609.10529/) (2026)

## Abstract (arXiv)

In the best-arm identification problem, we are given n stochastic arms with unknown means and wish to identify the arm with the largest mean with probability at least 1-δ, using as few samples as possible. We consider independent Gaussian rewards with unit variance and means in [0,1]. Chen and Li [2016] conjectured that the instance-wise sample complexity of this problem is characterized by the gap entropy, up to an additive term arising from the two-arm problem. In this paper, we resolve their gap-entropy and almost instance-wise optimality conjectures. For an instance I, let Delta[i] be the gap between the largest and the i-th largest mean, let H(I)=sumi=2nDelta[i]-2, and let Ent(I) denote the entropy of the normalized complexities of its dyadic gap groups. For every 0<δ<0.1, we show that the order-oblivious instance-wise lower bound is  Theta (H(I)[log(1/δ)+Ent(I)]).  We also give a single δ-correct algorithm with expected sample complexity  O ( H(I)[log(1/δ)+Ent(I)] +Dlog(e+log(e+D))),D=Delta[2]-2,  without prior knowledge of the gaps. Our lower bound removes the dyadic-gap and monotonicity restrictions of previous work, and our upper bound removes the additional polylogarithmic factor multiplying the two-arm term. Thus, a single algorithm attains the instance-wise lower bound up to an additive two-arm term. The main theorems have been formalized and proved in Lean 4.