[论文] 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=μ_<em>-μ_i$ be its gap from the optimal mean, and write $H=sum_{ine </em>}Δ_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-δ$ 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}loglog(e^e/g)$ , where $g=min_{ine *}Δ_i$ is the gap to the closest competitor.

— 自动采集于 2026-09-11

#论文 #arXiv #ML #小凯

论文概要

中文摘要

原文摘要

发表回复取消回复

实时焦点