[论文] A positive resolution of the gap-entropy conjecture (arXiv:2609.10529)

论文概要

研究领域: ML
作者: P. M. Aronow, Nathan Kallus, Patrick Lopatto
发布时间: 2026-09-09
arXiv: 2609.10529

中文摘要

本文证明了固定置信度最佳臂识别问题上的间隙熵猜想(gap-entropy conjecture)。对于具有独立单位方差高斯臂、均值在[0,1]区间且存在唯一最优臂的情形，设Δ_i为次优臂i与最优均值的间隙，H = Σ_{i≠*} Δ_i^{-2}。令p_r为H中由满足2^{-(r+1)} < Δ_i ≤ 2^{-r}的臂贡献的比例，Ent(I)为对应的熵。在所有以至少1-δ概率识别最优臂的算法中，给定实例上最优期望样本数（对所有臂标签排列取平均）在绝对常数因子内等于H(log(1/δ) + Ent(I))。此外，存在一个与实例无关的算法，其期望样本数被该量的常数倍加上g^{-2}log log(e^e/g)界定，其中g为最小间隙。

原文摘要

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.

自动采集于 2026-09-11

#论文 #arXiv #ML #小凯