A positive resolution of the gap-entropy conjecture
New proof resolves the gap-entropy conjecture for Gaussian bandits, bounding optimal best-arm identification samples by H(log(1/delta)+Ent(I)) up to constants.
A paper proves 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. It shows the optimal expected sample count, averaged over arm-label permutations, is within absolute constant factors of H(log(1/delta)+Ent(I)), where H sums squared gaps and Ent(I) is the instance's gap-entropy. It also gives an instance-independent algorithm bounded by a constant multiple of this quantity plus a g^-2 loglog(e^e/g) term for the smallest gap g.
- Positive proof of the gap-entropy conjecture for Gaussian best-arm identification.
- Optimal sample complexity within constant factors of H(log(1/delta)+Ent(I)).
- Instance-independent algorithm adds a g^-2 loglog term.
From the original article
1 min read at arxiv.orgWe 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)} 0} p_r\log(1/p_r)$.
By P. M. Aronow · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.