A Positive Resolution of the Gap-Entropy Conjecture for Best-Arm Identification (arXiv:2609.10529)

Forum topic · 小凯 · 2026-09-11

Summary

A new paper by P. M. Aronow, Nathan Kallus, and Patrick Lopatto (arXiv:2609.10529) proves the gap-entropy conjecture for fixed-confidence best-arm identification in the bandit setting with independent unit-variance Gaussian arms, means in [0,1], and a unique optimal arm. For each suboptimal arm i with gap Δ_i = μ_* − μ_i, the characteristic scale is H = Σ_{i≠*} Δ_i^{-2}, together with an entropy term Ent(I) built from the fractions p_r of H contributed by arms whose gaps fall in dyadic ranges 2^{-(r+1)} < Δ_i ≤ 2^{-r}. The authors show that among all algorithms identifying the optimal arm with probability at least 1−δ on every instance, the optimal expected number of samples—averaged over permutations of the arm labels—is within absolute constant factors of H(log(1/δ) + Ent(I)). They further construct a single instance-independent algorithm whose expected sample complexity is bounded by a constant multiple of this quantity plus g^{-2} log log(e^e/g), where g is the smallest gap. This settles the sample-complexity characterization of Gaussian best-arm identification up to constants.

Paper Overview

Field: Machine Learning

Authors: P. M. Aronow, Nathan Kallus, Patrick Lopatto

Published: 2026-09-09

arXiv: 2609.10529

English Abstract

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 $$Δ_i=μ_*-μ_i$$ be its gap from the optimal mean, and write $H=\sum_{i\ne *}Δ_i^{-2}$ . Let $$p_r$$ be the fraction of $$H$$ contributed by arms with $2^{-(r+1)}<Δ_i\le2^{-r}$ , and let $\mathrm{Ent}(I)=\sum_{r:p_r>0} p_r\log(1/p_r)$ . 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/δ)+\mathrm{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^{-2}\log\log(e^e/g)$ , where $g=\min_{i\ne *}Δ_i$ is the gap to the closest competitor.

Key Takeaways

The gap-entropy conjecture is now proven for fixed-confidence best-arm identification over Gaussian bandit instances with a unique optimal arm.
The sample complexity is characterized by $H(\log(1/δ)+\mathrm{Ent}(I))$ , where $$H$$ sums inverse squared gaps and $\mathrm{Ent}(I)$ captures the entropy of the dyadic distribution of gaps.
Optimality holds up to absolute constant factors, averaged over permutations of arm labels.
A single instance-independent algorithm achieves this bound up to constants plus an additive $g^{-2}\log\log(e^e/g)$ term, where $$g$$ is the minimum gap.

---

*Auto-collected on 2026-09-11.*