赌场里的熵：一个困扰了学界多年的猜想，被证明是对的

场景：K 台老虎机前

你站在 K 台老虎机前。每台机器的期望收益不同，但你不知道哪台最好。你只能一台一台地拉杆，每次拉杆立刻看到结果。你的目标很简单：用最少的拉杆次数，以至少 1−δ 的概率找到那台最好的机器。

这就是固定置信度最佳臂识别（fixed-confidence best-arm identification）问题。它是多臂老虎机理论中最经典的设定之一，从临床实验到 A/B 测试，从推荐系统到材料筛选，底层都是同一个数学结构。

这个问题有一个直觉性的难度刻度：间隙（gap）。设最优臂的期望为 μ*，次优臂 i 的期望为 μ_i，间隙 Δ_i = μ* − μ_i。间隙越小，区分起来越难。要把臂 i 和最优臂区分开，大约需要 Δ_i^{-2} log(1/δ) 次采样。把所有次优臂的代价加起来，就得到基线复杂度：

H · log(1/δ)，其中 H = Σ_{i≠*} Δ_i^{-2}

这个公式说了一件直觉的事：间隙越小的臂越难区分，代价按平方反比增长。如果间隙缩小一半，采样量翻四倍。

但这里藏着一个被忽略了半个世纪的问题。

被遗忘的维度：间隙的"分布形状"

H · log(1/δ) 这个公式假设你已经知道每个间隙大致在什么量级。但现实中你不知道。算法必须自己发现间隙的尺度分布，而这个"发现"本身有代价。

想象两种极端情况：

场景 A：K = 100 台机器，其中 99 台的间隙都差不多大（比如都在 0.1 附近）。你知道有一个尺度需要处理，采样集中在那个尺度上。

场景 B：K = 100 台机器，间隙分布在多个尺度上——10 台间隙约 0.5，30 台约 0.1，30 台约 0.01，29 台约 0.001。你需要同时处理四个尺度，采样努力被分散在四个数量级上。

两种场景的 H 值可以完全相同，但场景 B 明显更难——因为算法不知道采样努力应该分配到哪个尺度，必须"搜索"正确的尺度。

Chen 和 Li 在 2022 年提出了一个大胆的猜想：这个额外的代价可以用一个熵来刻画。

间隙熵：把"难度形状"变成一个数

定义很精巧。把所有次优臂按间隙大小分到几何壳层里：第 r 层包含间隙在 (2^{-(r+1)}, 2^{-r}] 之间的臂。每一层对 H 的贡献记为 H_r，占比 p_r = H_r / H。

现在把 {p_r} 当作一个概率分布，算它的香农熵：

Ent(I) = Σ_{r: p_r > 0} p_r log(1/p_r)

这就是间隙熵。

• 场景 A：所有臂在同一层，Ent = 0（确定性分布的熵为零）
• 场景 B：四层各贡献 1/4，Ent = log 4 ≈ 1.386

Chen 和 Li 猜想：最优算法在实例 I 上的期望采样数应该正比于

H · (log(1/δ) + Ent(I))

这个公式把采样代价分成了两项：H · log(1/δ) 是"已知尺度时的区分代价"，H · Ent(I) 是"发现正确尺度的代价"。两项都和 H 成正比，因为每个尺度上的采样量都和 H 成正比。

猜想的精确表述

在严格的数学表述中，猜想涉及两个层面：

实例层面（Conjecture 3.5）：在所有 δ-正确的算法中，实例 I 上的最优期望采样数（对所有臂标签排列取平均）在绝对常数因子内等于 H(log(1/δ) + Ent(I))。注意，这里允许不同的实例有不同的算法达到最优，但每个算法必须在所有实例上都 δ-正确。

算法层面（Conjecture 3.2）：存在一个与实例无关的算法，其期望采样数被 H(log(1/δ) + Ent(I)) 的常数倍加上 g^{-2} log log(e^e/g) 界定，其中 g 是最小间隙。

第二项中的 g^{-2} log log(e^e/g) 是不可避免的——即使只有两台机器，如果间隙可以任意小，算法就必须付出对数对数的代价来适应未知的间隙尺度。

为什么这个猜想难证

难在两个方向都要紧。

下界方向：要证明任何 δ-正确算法在实例 I 上至少需要 Ω(H(log(1/δ) + Ent(I))) 次采样。之前的下界只在两个限制下成立：间隙必须是 2 的幂次，且算法的期望代价在删除次优臂时不增加。真正的下界需要去掉这两个限制。

上界方向：要设计一个算法达到 O(H(log(1/δ) + Ent(I)))。之前的最好结果是 Chen、Li 和 Qiao 在 2024 年给出的 O(H(log(1/δ) + Ent(I)) + g^{-2} log log(1/g) · polylog(K, 1/δ))。多了一个 polylog 因子，虽然不大但不是常数。

两个方向都有"多出来的东西"需要去掉。

论文做了什么

Aronow、Kallus 和 Lopatto 在 2026 年 9 月的这篇论文给出了正面解决——两个猜想都对。

下界：对于高斯模型（单位方差、均值在 [0,1] 内、唯一最优臂），任何 δ-正确算法在实例 I 上的期望采样数（排列平均后）至少是 c · H(log(1/δ) + Ent(I))，其中 c 是绝对常数。没有任何对间隙或算法结构的限制。

上界：存在一个与实例无关的算法，其期望采样数被 C · H(log(1/δ) + Ent(I)) + C · g^{-2} log log(e^e/g) 界定，其中 C 是绝对常数，g 是最小间隙。

两个方向匹配，猜想完全解决。

技术核心：尺度逐层剥离

算法的核心思路是逐层剥离（peeling）。把间隙按几何壳层分组，每一层用不同的采样预算来处理。关键在于：算法不需要预先知道哪些臂在哪一层，而是通过自适应采样来"发现"每层的臂。

具体来说，算法维护一个候选集，在每一轮中按估计的间隙大小把臂分到不同的壳层，然后对每个壳层分配与其 H_r 贡献成正比的采样量。当某个壳层的臂被充分区分后，它们被移出候选集，算法集中精力处理更难的层。

这个结构保证了：每一层的采样量正比于 H_r · log(1/δ)，加上发现该层存在的代价 H_r · log(1/p_r)。求和后正好是 H · log(1/δ) + H · Ent(I)。

下界的证明更微妙。核心思路是构造两个"接近"的实例——它们只在某个特定壳层的臂上有差异——然后证明任何算法如果在这两个实例上的行为太相似，就无法区分它们。通过在多个尺度上重复这个论证，可以累积出 H · Ent(I) 的额外代价。排列平均的技巧确保了算法不能利用标签信息来偷工减料。

为什么最小间隙的额外项不可避免

g^{-2} log log(e^e/g) 这一项来自一个微妙的困难：算法不知道最小间隙 g 有多小。

考虑一个两臂问题，间隙为 g。如果 g 已知，只需要 g^{-2} log(1/δ) 次采样。但 g 未知时，算法必须尝试不同的尺度——先假设 g 较大，如果不够就缩小尺度重试。这个"尝试-缩小"的过程会产生 log log(1/g) 的额外代价。

Chen 和 Li 在 2022 年就证明了这一项在两臂情况下不可避免。本文的算法通过精心设计的逐层剥离策略，确保这一项只出现一次（在最细的壳层上），而不是在每个壳层上都出现。

对实际问题的启示

这个结果对实际的最佳臂识别问题有三个直接启示：

第一，间隙分布的形状比臂的数量更重要。 100 个间隙差不多的臂，比 10 个间隙分散在四个尺度上的臂更容易处理。在设计实验时，如果能预先筛选掉明显差的臂（增大间隙），收益是平方级的。

第二，自适应采样的收益取决于间隙熵。 如果间隙熵很低（所有臂差不多难），均匀分配就接近最优；如果间隙熵很高（臂分散在多个尺度），自适应采样的收益巨大——可能差几个数量级。

第三，"不知道自己不知道"的代价是可量化的。 H · Ent(I) 这个项精确刻画了"算法不知道间隙在哪个尺度"的代价。在信息论中，熵度量不确定性；在这里，间隙熵度量"尺度不确定性"的代价。这是一个深层的同构。

一个更深的问题

这篇论文的证明用了一个有趣的声明：作者在致谢中写道，论文使用了大语言模型来建议数学论证、起草和修改表述，以及编写计算验证代码。

这引出一个有趣的问题：如果 gap-entropy 猜想的证明有 LLM 的贡献，那么 LLM 在数学研究中的角色正在从"辅助工具"变成"合作者"。这篇论文本身可能也是"AI 辅助数学证明"这个趋势的一个数据点。

但更本质的问题是：间隙熵这个概念本身——把"难度形状"压缩成一个标量——是否适用于其他自适应决策问题？在主动学习、贝叶斯优化、强化学习的探索-利用权衡中，是否也有类似的"熵代价"？

这个猜想被证明了，但它打开的问题可能比关闭的更多。

---

论文信息

• 标题：A positive resolution of the gap-entropy conjecture
• 作者：P. M. Aronow, Nathan Kallus, Patrick Lopatto
• arXiv：2609.10529
• 发布时间：2026 年 9 月 9 日
• 开源代码：无