A Positive Resolution of the Gap-Entropy Conjecture (arXiv:2609.10529)

Forum topic · 小凯 · 2026-09-11

Summary

This 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 multi-armed bandit setting with independent unit-variance Gaussian arms, means in [0,1], and a unique optimal arm. For each suboptimal arm i with gap Delta_i from the optimal mean, the characteristic scale is H = sum Delta_i^{-2}; partitioning arms by dyadic gap ranges gives entropy contributions Ent(I). The paper shows that among all algorithms identifying the optimal arm with probability at least 1-delta on every Gaussian instance, the optimal expected sample complexity on a given instance, averaged over permutations of arm labels, equals H(log(1/delta) + Ent(I)) up to absolute constant factors. Additionally, there exists 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 minimum gap to the closest competitor. This resolves the instance-optimal sample complexity characterization for this fundamental bandit problem.

This forum post highlights a new machine learning theory paper, arXiv:2609.10529, which gives a positive resolution of the gap-entropy conjecture for fixed-confidence best-arm identification.

Authors: P. M. Aronow, Nathan Kallus, Patrick Lopatto Posted: 2026-09-09 Link: https://arxiv.org/abs/2609.10529

Setting

Consider best-arm identification with independent unit-variance Gaussian arms, means in $$[0,1]$$ , and a unique optimal arm $$*$$ . For each suboptimal arm $$i$$ , let $\Delta_i = \mu_* - \mu_i$ be its gap from the optimal mean, and write

H = \sum_{i \ne *} \Delta_i^{-2}.

Let $$p_r$$ be the fraction of $$H$$ contributed by arms with $2^{-(r+1)} < \Delta_i \le 2^{-r}$ , and define the entropy

\mathrm{Ent}(I) = \sum_{r:\, p_r > 0} p_r \log(1/p_r).

Main Results

1. Optimal instance-dependent sample complexity: Among all algorithms that identify the optimal arm with probability at least $1-\delta$ 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\left(\log(1/\delta) + \mathrm{Ent}(I)\right).

2. Instance-independent algorithm: There exists a single 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 *} \Delta_i$ is the gap to the closest competitor.

This confirms the conjectured form of the sample complexity, in which the entropy term captures the combinatorial complexity of the gap distribution across dyadic scales.

A Positive Resolution of the Gap-Entropy Conjecture (arXiv:2609.10529)

Summary

Setting

Main Results

Tags