A positive resolution of the gap-entropy conjecture

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=∑_{i≠ *}Δ_i⁻². Let p_r be the fraction of H contributed by arms with 2^−(r+1)<Δ_i≤2^−r, and let Ent(I)=∑_{r:p_r>0} p_rlog(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/δ)+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⁻²loglog(e^e/g), where g=min_{i≠ *}Δ_i is the gap to the closest competitor.

The Wehrl-type entropy conjecture for symmetric SU(N) coherent states: Cases of equality and stability
Fabio Nicola, Federico Riccardi, Paolo Tilli
Duke Mathematical Journal25 Aug 2026Peer-reviewedLicence not statedFull text11 citedMathematical physicsOpenAlex
A Proof of the Analytic Entropy Conjecture
Xiaoyang Chen, Xiang Jiang
arXiv7 Oct 2026PreprintCC BY 4.0Full textGeometry & topologyarXiv
Quantum entropy and the Bannai--Ito multiplicity conjecture
Gary Greaves, Haoran Zhu
arXiv11 Sep 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Strong Positive Recurrence for Strongly Entropy Expanding Maps
Alexandre Delplanque, Hengyi Li
arXiv21 Oct 2026PreprintarXiv licenceFull textDynamical systemsarXiv
Poisson actions of noncompact locally compact sofic groups have completely positive sofic entropy
Zhuowei Liu
arXiv7 Oct 2026PreprintCC BY 4.0Full textDynamical systemsarXiv

Cite

BibTeX RIS

BibTeX

@misc{aronow2026positive,
  title = {{A positive resolution of the gap-entropy conjecture}},
  author = {P. M. Aronow and Nathan Kallus and Patrick Lopatto},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.10529},
  eprint = {2609.10529},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.10529},
}

RIS

TY  - UNPB
TI  - A positive resolution of the gap-entropy conjecture
AU  - P. M. Aronow
AU  - Nathan Kallus
AU  - Patrick Lopatto
PY  - 2026
DA  - 2026/09/09
PB  - arXiv
DO  - 10.48550/arxiv.2609.10529
UR  - https://arxiv.org/abs/2609.10529
AB  - 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=∑_i≠ *Δ_i^−2. Let p_r be the fraction of H contributed by arms with 2^−(r+1)<Δ_i≤2^−r, and let Ent(I)=∑_r:p_r>0 p_rlog(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/δ)+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(e^e/g), where g=min_i≠ *Δ_i is the gap to the closest competitor.
ER  -

Abstract

Related

Cite