# Open Problem: Best Arm Identification: Almost Instance-Wise Optimality and the Gap Entropy Conjecture

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 May 2016.

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

- [A positive resolution of the gap-entropy conjecture](https://mlsanity.com/paper/2609.10529/) (2026)
- [Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification](https://mlsanity.com/paper/2609.13703/) (2026)

## Abstract (arXiv)

The best arm identification problem (BEST-1-ARM) is the most basic pure exploration problem in stochastic multi-armed bandits. The problem has a long history and attracted significant attention for the last decade. However, we do not yet have a complete understanding of the optimal sample complexity of the problem: The state-of-the-art algorithms achieve a sample complexity of O(sumi=2n Deltai-2(lnδ-1 + lnlnDeltai-1)) (Deltai is the difference between the largest mean and the ith mean), while the best known lower bound is Omega(sumi=2n Deltai-2lnδ-1) for general instances and Omega(Delta-2 lnln Delta-1) for the two-arm instances. We propose to study the instance-wise optimality for the BEST-1-ARM problem. Previous work has proved that it is impossible to have an instance optimal algorithm for the 2-arm problem. However, we conjecture that modulo the additive term Omega(Delta2-2 lnln Delta2-1) (which is an upper bound and worst case lower bound for the 2-arm problem), there is an instance optimal algorithm for BEST-1-ARM. Moreover, we introduce a new quantity, called the gap entropy for a best-arm problem instance, and conjecture that it is the instance-wise lower bound. Hence, resolving this conjecture would provide a final answer to the old and basic problem.