Gap-entropy conjecture

Let $n\ge 2$ independent arms have distributions $X_i\sim\mathcal{N}(\mu_i,1)$ , with $\mu_i\in[0,1]$ and a unique optimal arm $*$ . Write $\Delta_i=\mu_*-\mu_i$ for $i\ne *$ , $H=\sum_{i\ne *}\Delta_i^{-2}$ , and, for each integer $r\ge 0$ , let $p_r=H^{-1}\sum_{i\ne *:\,2^{-(r+1)}<\Delta_i\le 2^{-r}}\Delta_i^{-2}$ . Define $\operatorname{Ent}(I)=\sum_{r:p_r>0}p_r\log(1/p_r)$ . The gap-entropy conjecture asserts that the optimal expected sample complexity of any algorithm that identifies $*$ with probability at least $1-\delta$ on every such instance is, up to universal constant factors and the unavoidable closest-gap term, $H\bigl(\log(1/\delta)+\operatorname{Ent}(I)\bigr)$ ; equivalently, the instance-dependent lower and upper bounds should match at this order.

References

Primary source

arXiv

Additional references

A positive resolution of the gap-entropy conjecture — arXiv

Posted 3 weeks ago · edited 3 weeks ago

Progress summary

Refreshed 3 weeks ago

Claimed solved

A September 2026 preprint claims to settle the conjecture for Gaussian best-arm identification, but nobody has independently checked the proof.

Chen and Li posed the conjecture in 2016: optimal best-arm identification should depend on both confidence and the entropy of the gaps, up to the unavoidable closest-gap cost.

Known results

Chen, Li, and Qiao obtained an upper bound with the main term $H\bigl(\log(1/\delta)+\operatorname{Ent}(I)\bigr)$ , but with an additional polylogarithmic closest-gap loss.
For dyadic gaps, the conjectured lower bound was proved for monotone algorithms; for arbitrary algorithms, only a suitable sub-instance lower bound was known.
These results did not resolve the full conjecture.

September 2026 claimed resolution

A September 2026 arXiv preprint claims matching bounds of order $H\bigl(\log(1/\delta)+\operatorname{Ent}(I)\bigr)$ for Gaussian best-arm identification, plus a closest-gap overhead for one instance-independent algorithm. This would settle the stated Gaussian case, but the claim is unrefereed and unverified.

Current status (as of September 2026): The stated Gaussian conjecture is claimed solved by an unverified preprint; independent verification is absent.

Sources

No solutions have been posted yet.