🤖 machine learning

Stabilized Best-of- $K$ Training for Neural Combinatorial Optimization

本文提出了一种用于神经组合优化的稳定化 Best-of- $K$ 训练扩展方案，该方案通过使用基于排名的信号取代二元领导者奖励（Leader Reward），在 TSP-100 的 Best-of-8 性能上展示了适度的提升，同时明确拒绝声称具有普遍优越性或达到最先进水平。

原作者： Melveena Jolly, Midhun Xavier

发布于 2026-08-04

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Melveena Jolly, Midhun Xavier

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图解开一个巨大的、缠绕在一起的绳结，但你无法一次看到全貌。你必须拉动一端，看看它会走向何方，然后再尝试。这就是“神经组合优化”（Neural Combinatorial Optimization）领域的日常挣扎——在这个领域，计算机科学家正在教人工智能解决复杂的谜题，比如旅行商问题（寻找访问许多城市的最短路径）。目标很简单：找到完美的路径。但路径是隐藏的，计算机必须进行猜测。

为了提高猜测的准确性，这些计算机使用了一种名为“强化学习”（Reinforcement Learning）的技术。这就像训练一只狗。如果狗坐下了，它会得到奖励（零食）；如果它跳起来，它什么也得不到。随着时间的推移，狗会学会更多地坐下。在人工智能的世界里，“狗”是神经网络，而“零食”是基于其解法质量的分数。一种被称为 POMO（多最优策略优化）的流行方法，通过让 AI 同时从许多不同的起点尝试解谜来工作，就像派出十个不同的探险家去寻找最短路径一样。通常，AI 会从所有这些探险家的平均表现中学习。然而，一种被称为“领袖奖励”（Leader Reward）的新想法提出，AI 应该额外关注这组中的单个最佳探险家，将这位“领袖”视为主角。

现在，想象你正在雇佣一支探险队来解决一个谜题，但你有一个严格的规则：你只会保留他们带回的最好的那张地图。一项新的实验提出了一个引人入胜的问题：如果你知道你只会从 100 张地图中保留最好的 8 张，那么你应该训练你的团队仅仅成为其中最强的一个，还是应该训练他们成为任何一个“潜在可能进入前 8 名”的人？这正是独立研究员 Melveena Jolly 和 Midhun Xavier 最近研究的核心。他们没有发明一种新型的探险者或一种新的谜题；相反，他们调整了现有 AI 的训练规则，以观察这种“前 8 名”的心态是否会让团队在实际部署时变得更聪明。

实验：为“前八名”进行训练

研究人员使用了一个针对经典谜题 TSP-100（访问 100 个城市）进行训练的标准 AI 设置，并运行了一项特定的测试。他们想看看改变 AI 从错误中学习的方式，是否有助于当 AI 被要求生成多个解并从中挑选最佳解时。

在旧的方法（称为“领袖奖励”）中，AI 被训练去痴迷于它在 100 次尝试中找到的单个最佳解。这就像一个教练在喊：“只有第一名才重要！其他人，回家吧！”新方法（作者称之为“稳定化的 K 最佳”，Stabilized Best-of-K）改变了教练的声音。新教练不再忽略除赢家之外的所有人，而是说：“如果你进入了前 8 名，你就能得到零食！如果你排在第 9 名或更后，你就什么也得不到。”这里的“K”代表这个数字 8。研究人员还添加了一个“稳定器”，这是一个数学上的安全网，以确保训练数值不会变得过于疯狂或产生太多噪声。

他们的发现：取决于游戏规则

结果既有“好消息”，也体现了“视情况而定”。

首先，研究人员检查了他们的系统是否能在玩标准游戏时匹配旧系统。当他们使用特定的解码方式（一种读取 AI 答案的方式）配合旧的“1-百次开始，选出最佳”方法时，新系统表现得几乎完全一样。它得到了 7.7662 的分数，与之前的记录 7.766 持平。这证明了他们在遵循相同的规则，并没有破坏原有机制。

然而，真正的魔力发生在他们根据新训练规则改变游戏规则的时候。当他们要求 AI 生成 8 个独立的解并从中挑选最佳解（即“Best-of-8”场景）时，新的“稳定化 K 最佳”方法胜出了。在他们进行的每一次测试运行中，新方法都找到了比旧方法更短的路径。平均而言，新方法减少了约 0.25% 的成本（路径长度）。虽然这听起来很小，但在这些谜题的世界里，哪怕只缩减一点点距离也是一件大事。它使 AI 的性能更接近理论上的“完美”解。

但这里有一个转折：新方法并不是适用于所有情况的灵丹妙药。

如果你只选一个： 如果 AI 只能选择一个单一的解（Best-of-1），那么旧的“领袖奖励”方法实际上更好。
如果你选择大量方案： 如果你让 AI 从 128 个解中进行选择，新方法仍然略好一些，但随着选择数量的增加，这种优势也在缩小。
如果你使用不同的解码器： 当他们使用另一种读取 AI 答案的方式（称为“增强贪婪算法”，augmented greedy）时，旧的方法再次略占优势。

总结

那么，这一切意味着什么？研究人员发现，如果你计划使用一种会生成一小批选项（如 8 个）并从中挑选最佳解的 AI，那么训练 AI 去瞄准“前 8 名”而不是仅仅瞄准“第一名”是一个明智之举。这就像是训练一支强大的阵容，而不仅仅是培养一个超级巨星。

然而，作者非常谨慎，并未过度宣传。他们明确指出，这并不是一个解决了所有问题的“最先进”（state-of-the-art）突破。它是一个针对特定设置的特定改进。他们仅在三个不同的“种子”（随机起始点）上进行了测试，这足以观察到模式，但不足以证明其永远有效。他们也承认，他们的方法是一个“工程配方”，而非完美的数学证明。

简而言之，这项研究表明，如果你正在构建一个用于解决路径规划谜题的 AI，并且你打算在挑选赢家之前让它尝试几次，那么你应该教它成为一名“顶尖竞争者”，而不仅仅是一个“冠军”。但如果你只有一次机会，或者你有大量的尝试次数，旧的方法可能仍然是你的最佳选择。对于人工智能世界的某个特定角落来说，这是一个细微且有帮助的优化，而不是一场改变一切的革命。

技术摘要：用于神经组合优化的稳定化 Best-of-K 训练

问题陈述
神经组合优化（NCO）模型（如 POMO, Kwon et al., 2020）通常在由多个起始节点生成的轨迹批次上进行训练，并使用共享基准（shared-baseline）的策略梯度。然而，标准的训练更新会对整个批次进行赋权，而部署时通常仅保留在特定推理预算内找到的最佳解。Leader Reward (Wang et al., 2024) 通过修改训练过程来解决这一问题，它强调单个“领导者”（batch 中的最佳轨迹）并降低其他轨迹的权重。

本文研究了是否应该不仅区分当前的领导者，还要区分那些在部署时抽取恰好 $K$ 个独立轨迹的情况下，有潜力成为该 $K$ 规模组内最佳成员的轨迹。其动机目标是优化 $K$ 个独立样本的期望最大奖励：
$J_K(\theta) = \mathbb{E}_{\tau_1, \dots, \tau_K \sim \pi_\theta} \left[ \max_{1 \le j \le K} R(\tau_j) \right]$
本研究重点关注使用 POMO 架构的旅行商问题 (TSP-100)。

方法论
作者提出了一个“稳定化 Best-of-K”作为 Leader Reward 框架的扩展。与仅为单个最佳轨迹分配特殊角色的 Leader Reward 不同，该方法根据排名和固定的采样预算 $K$ 来分配信用（credit）。

排名间隙加权（Rank-Gap Weighting）： 对于一个包含 $n=100$ 个 POMO 起始点的批次，其排序后的奖励为 $R_{(1)} \le \dots \le R_{(n)}$ ，该方法为排名 $i \ge K$ 的轨迹分配权重。权重计算为当前轨迹的奖励与较低排名轨迹之间的间隙之和，并由组合系数加权。这取代了二元的领导者/非领导者区分，转而使用由 $K$ 指示的连续信号。
稳定化（Stabilization）： 为了防止训练不稳定，应用了两种变换：
- 间隙底限（Gap Flooring）： 在权重计算中，将求和后的间隙通过一个微小的 $\delta = 0.01(R_{(n)} - R_{(1)})$ 进行下限限制（flooring）。
- 标准化（Standardization）： 在每个实例内对生成的权重向量进行标准化处理。
实现细节： 研究使用了 RL4CO 的 POMO 实现，每个实例包含 100 个起始点，批次大小为 64，固定调度周期为 3,050 个 epoch。采样预算固定为 $K=8$ 。训练种子采用配对方式 {0, 1, 2}。

核心贡献

受控扩展： 这是一项针对 Leader Reward 的复现与扩展研究，而非提出新的架构或推理搜索方法。它隔离了将二元领导者信号替换为稳定化排名间隙信号的效果。
工程配方（Engineering Recipe）： 作者明确指出，“稳定化 Best-of-K”是一个工程配方（涉及底限处理和标准化），而非公式 (1) 的无偏估计量。
评估协议： 研究引入了一个严格的评估协议，对于每个检查点（checkpoint），抽取 2,048 条独立轨迹。这些轨迹被划分为大小为 $K$ 的不相交块，用以衡量实际实现的 Best-of- $K$ 代价。

结果
实验在欧几里得 TSP-100 上进行，测试实例共 10,000 个。

基准复现： Leader Reward 的重新实现实现了 7.7662 的平均代价（在 100-start, 8-augmentation greedy 解码条件下），与 Wang et al. (2024) 报告的 7.766 相匹配。
在采样 Best-of-8 中的改进： 在 $K=8$ 的独立采样下，稳定化 Best-of-K 方法实现的平均代价（7.7944）低于 Leader Reward（7.8136），涵盖所有三个训练种子。相对于 Leader Reward，这代表了 0.247% 的代价降低。
预算依赖性： 稳定化方法的优势取决于采样预算 $K$ 。当 $K \in \{2, \dots, 128\}$ 时，它优于 Leader Reward，但在 $K=1$ （单条轨迹）以及原始的增强贪婪（augmented-greedy）协议下，Leader Reward 表现更好。
解码器特异性： 这种改进并非普遍适用。虽然稳定化策略改善了采样 Best-of-8 的表现，但在单条采样轨迹（ $K=1$ ）以及 100-start, 8-augmented greedy 解码协议下，其表现略逊于 Leader Reward。

主张与意义
本文对其主张保持了谨慎的范围：

无普遍优越性： 作者明确表示并未声称达到了最先进水平（SOTA）。在特定场景下（例如 $K=1$ 和增强贪婪模式），Leader Reward 仍然更优。
仅为估计： 结果基于三个训练种子，作者指出这低于进行确认性统计检验所需的六个种子的阈值。观察到的改进属于描述性观察，而非经过统计学证实的显著性提升。
特定适用性： 研究结果特定于 POMO 架构和欧几里得 TSP-100。论文并未声称其可推广至其他问题（如 CVRP）或其他 NCO 系列。
结论： 当部署涉及抽取适量数量的独立候选者时，稳定的 $K=8$ 排名间隙信号是 Leader Reward 一个“有前景的扩展”。它并不代表一种更通用的、更好的 POMO 策略。

实验：为“前八名”进行训练

他们的发现：取决于游戏规则

总结

技术摘要：用于神经组合优化的稳定化 Best-of-K 训练

类似论文