🤖 machine learning

The Two-Hump Problem: Bridging the Difficulty Gap in Mathematical Reinforcement Learning

本文通过引入新颖的数据生成技术和算法增强，旨在解决数学强化学习中的“双峰”难度分布问题，以弥合平凡实例与不可能实例之间的差距，从而实现了显著的性能提升，并发布了用于安德鲁斯-柯蒂斯猜想的大规模基准数据集（AC-19 和 AC-1M）。

原作者： Lucas Fagan, Michele Tarquini, Ali Shehper, Maksymilian Manko, Angus Gruen, Coco Huang, Giorgi Butbaia, Davide Passaro, Sergei Gukov

发布于 2026-06-23

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Lucas Fagan, Michele Tarquini, Ali Shehper, Maksymilian Manko, Angus Gruen, Coco Huang, Giorgi Butbaia, Davide Passaro, Sergei Gukov

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

大局观：数学迷宫

想象一下，你正在试图解开一个巨大的、无限大的迷宫。你的目标是将一团复杂、缠绕在一起的绳结（数学上的“表示法”）解开，直到它变成一条简单的直线（“平凡”解）。

几十年来，数学家们一直试图弄清楚是否每一个可能的绳结都能通过这种方式被解开。这就是所谓的安德鲁斯-柯里西猜想（Andrews-Curtis Conjecture）。

最近，科学家们尝试使用人工智能（具体来说是强化学习，简称 RL）来解决这个问题。把这个 AI 想象成一个试图寻找出口的机器人探险家。但这个机器人总是被困住。它能轻松解决简单的绳结，但一旦遇到困难的绳结，它就会撞上一堵墙。它不知道如何从“简单”过渡到“困难”。

这篇论文解释了为什么机器人会被困住，以及他们是如何解决这个问题的。

问题所在：“两峰”景观

作者发现，这些数学问题的难度并不是均匀分布的。相反，它看起来像是一个拥有两座巨型山丘且中间夹着一个深邃空谷的地形。

易行之丘（左侧）： 这些是容易解开的绳结。机器人可以通过一步步缩短绳结长度的方法快速解决它们。
不可能之丘（右侧）： 这些是极其复杂的绳结，目前的计算机和机器人根本无法解决它们。它们会陷入死循环。
空虚之谷（中间）： 这就是问题所在。几乎不存在“中等难度”的绳结。

为什么这对 AI 很不利？
想象你在教一个孩子爬山。如果你只展示一座小山丘（太容易）和一道垂直峭壁（太难），他们永远学不会如何攀爬陡峭的坡度。他们需要中间的“垫脚石”。因为这些数学问题缺乏这些垫脚石，AI 无法学习应对那些真正困难的绳结所需的通用技能。

解决方案：三种新工具

为了填补这一差距，团队构建了三种新工具来帮助 AI 攀登这座大山。

1. “超级移动”（代换/Substitutions）

在旧的方法中，机器人只能进行微小的、单步的操作（比如只移动一根绳子的一小段）。这太慢了。
作者意识到，机器人可以进行**“超级移动”**。机器人不再只是移动一小块绳子，而是学会了抓取一整块绳结，将其旋转，然后一次性将其卡入另一个位置。

类比： 想象你在整理一个乱七八糟的房间。旧的方法是一次搬一只袜子。新方法是抓起一整堆衣服，折叠好，然后通过一个巨大的、高效的动作一次性放入衣柜。这让机器人能够通过迷宫进行大跨步跳跃，而不是小碎步挪动。

2. “双环”大脑（新架构）

这些数学问题有一个特殊的属性：它们是循环的。如果你有一个珠子项链，无论从哪里开始计数，模式都是一样的。
旧的 AI 大脑（神经网络）将绳子视为一条直线，这让它们感到困惑。作者构建了一个名为**双环 Transformer（Dual-Ring Transformer）**的新大脑。

类比： 想象你在看一个时钟。普通的大脑看到的是 1 到 12 的直线排列。而新的大脑看到了一个圆圈。它明白 12 和 1 是紧挨着的。这有助于 AI 理解绳结的“全局观”，并找到旧大脑错过的捷径。

3. “生成器-求解器”博弈（填补山谷）

由于“中等难度”问题的“山谷”是空的，团队不得不亲手创造它们。他们设置了一个两个 AI 之间的游戏：

生成器（Generator）： 它的任务是拿走一个简单的绳结，并对其进行适度的扭转，使其变得更难，但又不至于无法解决。它就像一位谜题大师，创造出一个既具挑战性又可解的谜题。
求解器（Solver）： 它的任务是尝试解开这个新的、更难的绳结。
结果： 通过进行数百万次的这种游戏，他们创建了一个庞大的“金发姑娘”级问题库——既不太难，也不太易。这为山谷填满了垫脚石，让 AI 能够学习如何攀登陡峭的山坡。

研究结果

有了这三种工具，AI 取得了巨大的进步：

解决更多： 新的 AI 比之前的最优方法多解决了 153 个 困难绳结。
更聪明的路径： 即使在旧方法也能解决某个绳结的情况下，新的 AI 也能找到更短、更高效的解决路径。它学会了采取“绕路”策略，即暂时让绳结看起来变得更大，以便稍后能更快地解开它。
新数据集： 他们发布了两个包含超过一百万个样本的大型数学问题库（AC-19 和 AC-1M），其他科学家现在可以使用这些数据来训练更好的 AI。

核心结论

这篇论文证明了 AI 在处理这个数学问题时之所以挣扎，并不是因为 AI “笨”，而是因为问题本身的地形结构出了问题（即“两峰”现象）。通过修复地形（创造垫脚石）并赋予 AI 更好的工具（超级移动和环形大脑），他们成功解决了数百个此前未解的数学谜题。

他们还没有证明整个猜想（那座山依然巨大），但他们建造了一把更完美的梯子来攀登它。

技术摘要：数学强化学习中的“双峰问题”

问题定义

本文探讨了将强化学习（RL）应用于 Andrews–Curtis (AC) 猜想的挑战，这是一个组合群论中著名的开放问题。该猜想认为，任何平凡群的平衡演示（balanced presentation）都可以通过一系列特定的变换（AC1：求逆，AC2：共轭/拼接，AC3：循环置换）转化为平凡演示 $\langle x, y \mid x, y \rangle$ 。

其核心难点在于搜索空间的特性：

巨大的搜索空间：演示的图结构是无限的。
稀疏奖励：智能体只有在完全实现平凡化时才会获得奖励；不存在中间的“早期失败”信号或进度指标。
“双峰”现象：作者发现了一个关键的结构性障碍，即问题实例呈现双峰分布。大多数演示要么是平凡可解的（通过简单的贪婪长度缩减即可），要么是实际上不可解的（需要经过暂时增加长度的路径，而标准启发式算法会拒绝此类路径）。至关重要的是，中间状态的“困难但可解”实例非常稀缺，这种“数据谷底”阻碍了有效的课程学习。

方法论

为了弥补难度差距并克服“双峰”分布，作者提出了一种结合算法创新、架构设计和定向数据生成的综合方案。

1. 动作空间：替换超移动（Substitution Supermoves）

作者不再操作原始的 AC 移动，而是引入了替换移动作为主要的动作空间。

机制：替换操作将关系子（relators）视为循环序列，并在发生抵消的点将一个关系子插入到另一个之中。这把多个原始移动（AC1, AC2, AC3）合并为一个单一动作。
优势：这允许智能体在 AC 图中采取更大、更有意义的步长，并通过忽略循环置换，显著降低了有效状态空间。
理论基础：Ivanov (2018) 证明，如果 AC 猜想成立，则替换足以实现所有的 AC 变换。

2. 架构：双环 Transformer（Dual-Ring Transformer）

为了处理具有大规模、结构化替换动作空间的复杂性，同时尊重问题的数学对称性，作者开发了 Dual-Ring Transformer。

循环对称性：不同于使用绝对位置编码的标准 Transformer，该架构将关系子视为循环环结构。它采用了循环相对位置编码，其注意力分数取决于循环距离 $d(i, j) = (i - j) \mod L$ 。
交叉注意力：网络并行处理两个关系子，利用交叉注意力识别它们之间的匹配子串，这对于确定有效的替换移动至关重要。
策略头：输出是有效替换移动的分布，并通过掩码确保只有导致抵消（即 $r_1[i] = \pm r_2[j]$ ）的动作能获得非零概率。

3. 数据生成：填充“谷底”

由于意识到标准的“打乱”（scrambling）策略无法生成“困难但可解”的实例，作者采用了两种新型数据生成技术：

自同构扰动（Automorphism Perturbation）：对已知的平凡演示（如 $AK(2)$）应用自同构，将其转化为具有截然不同路径特征的演示。虽然原始演示可能很简单，但其自同构像可能需要增加长度的步骤，从而有效地从“容易”的一峰移动到“谷底”。
生成器-求解器博弈（Generator-Solver Game）：构建了一个非对称的双人博弈，其中生成器（一个 PPO 智能体）通过应用一系列自同构来增加演示的难度，而求解器（贪婪搜索）则尝试将其平凡化。生成器的奖励在于创造出能够挑战求解器的实例，特别针对中间难度区域。
生成的数据集：这一过程产生了 AC-19（125,192 个短长度 AC 平凡演示，长度 $\le 19$ ）和 AC-1M（1,136,154 个硬核 AC 平凡演示，长度 $\le 30$ ），这是首个此类大规模公开数据集。

关键结果

作者在包含 1,190 个演示的 Miller–Schupp 基准数据集上评估了其方法。

性能提升：结合了替换超移动和 Dual-Ring Transformer 的方法（PPO-Sub-DRT）解决了 610 个演示（5 个种子实验的平均值），相比之前表现最好的 RL 基准（PPO-AC-ResNet，解决 457 个）有了显著提升。
数据影响：引入生成的 AC-1M 数据集进一步提升了性能，证明了定向数据生成能有效帮助智能体学习处理困难演示的通用策略。
路径效率：虽然使用替换操作的贪婪搜索（GS）因其穷举探索能力解决了更多实例（640 个），但 PPO 智能体发现了显著更短的解路径，尤其是在处理较难的演示时。PPO 能够识别出贪婪启发式算法会拒绝的“增长长度”绕行路径，证明了智能体学习到了非显而易见的数学结构。
架构优越性：使用循环相对编码的 Dual-Ring Transformer 比使用规范形式预处理加绝对编码的变体多解决了约 25 个演示，凸显了学习对称感知表示的重要性。
数学进展：作者成功使 Miller–Schupp 系列中超过 100 个此前未解的演示变得平凡。他们将剩余的 550 个未解示例减少到了 261 个不同的 AC 等价类，为未来的研究提供了具体的清单。

意义与主张

本文声称，取得 Andrews–Curtis 猜想的进展需要理解问题内在的难度结构，而非仅仅增加计算规模。

双峰洞察：对双峰难度分布的识别解释了为何以往的方法难以奏效，并阐明了将算法改进与定向数据生成相结合的必要性。
稀疏奖励环境下的 RL：这项工作展示了强化学习如何在需要数百个精确连续决策的极端稀疏奖励环境中取得成功，其研究结论可迁移至机器人、定理证明和程序合成等领域。
数学效用：无论 AC 猜想最终被证明是否成立，这项工作都取得了实质性的进展。如果猜想成立，每一次新的平凡化过程都是对证明的贡献；如果猜想不成立，将看似反例的演示平凡化则有助于缩小寻找真实反例的范围。
可迁移性：作者认为，“双峰”结构以及开发的各种技术（替换、循环架构、生成器-求解器博弈）可以推广到其他存在双峰难度分布和违反进度移动（progress-violating moves）的数学搜索问题中。

作者总结道，进一步的进展不会来自于对经典搜索的边际改进，而需要能够利用超越固定启发式算法所能捕捉到的结构的学习型方法。