Mathematicians solve a key problem in finding the best option efficiently
A positive resolution of the gap-entropy conjecture
Machine Learning
Summary
Finding the best choice from many options is important in areas like testing products or making decisions based on uncertain results. The authors proved a mathematical prediction called the gap-entropy conjecture, which helps understand how many samples or tries are needed to confidently pick the best choice when measurements have some noise. They show the exact relationship between the difficulty of telling options apart and the number of samples required. Their work also describes a strategy that performs nearly as well as the best possible method across all scenarios.
best-arm identificationGaussian distributionsampling complexitygap-entropy conjectureconfidence levelmean rewardalgorithmprobabilitystatistical gap
Authors
P. M. Aronow, Nathan Kallus, Patrick Lopatto
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.