多臂老虎机理论中的“差距-熵猜想”获正向解决

我们针对具有独立单位方差高斯臂、均值在 $[0,1]$ 内且存在唯一最优臂的固定置信度最佳臂识别问题，证明了差距-熵猜想（gap-entropy conjecture）。对于每个次优臂 $i$，设 $Δ_i=μ_*-μ_i$ 为其与最优均值的差距，并记 $H=\sum_{i\ne *}Δ_i^{-2}$。设 $p_r$ 为满足 $2^{-(r+1)}<Δ_i\le2^{-r}$ 的臂对 $H$ 的贡献比例，并设 $\mathrm{Ent}(I)=\sum_{r:p_r>0} p_r\log(1/p_r)$。在所有能在每个高斯实例上以至少 $1-δ$ 的概率识别出最优臂的算法中，对臂标签的所有置换取平均后，在给定实例上的最优期望采样次数与 $H(\log(1/δ)+\mathrm{Ent}(I))$ 仅相差绝对常数因子。此外，还存在一个与实例无关的算法，其期望采样次数受限于该量的常数倍加上 $g^{-2}\log\log(e^e/g)$，其中 $g=\min_{i\ne *}Δ_i$ 是与最接近竞争者的差距。