A positive resolution of the gap-entropy conjecture

arXiv:2609.10529v1 Announce Type: new 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 Delta_i=mu_*-mu_i be its gap from the optimal mean, and write H=sum_{ine *}Delta_i^{-2}. Let p_r be the fraction of H contributed by arms with 2^{-(r+1)}0} p_rlog(1/p_r). Among all algorithms that identify the optimal arm with probability at least 1-elta 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/elta)+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}loglog(e^e/g), where g=min_{ine *}Delta_i is the gap to the closest competitor.

Where Does the Union Bound Go? Best-Arm Identification and Strong FWER Control
On the Power of Adaptivity for arepsilon-Best Arm Identification in Linear Bandits
Algorithmic and Minimax Complexities in Kernel Bandits

Source: arXiv cs.LG | 2026-09-10

Related