技術要約：数学的強化学習における「二つの丘（Two-Hump）」問題

問題の定義

本論文は、組合せ群論における著名な未解決問題であるアンドリュー・カーティス（AC）予想に強化学習（RL）を適用する際の課題に取り組んでいる。この予想は、自明な群のバランスの取れた提示（balanced presentation）は、特定の操作（AC1：反転、AC2：共役および結合、AC3：巡回置換）の有限個の列挙によって、自明な提示 $\langle x, y \mid x, y \rangle$ へと変形可能であることを主張している。

核心となる困難さは、探索空間の性質にある：

1. 膨大な探索空間: 提示のグラフは無限である。
2. 希薄な報酬: エージェントは、完全に自明化された時にのみ報酬を受け取る。中間的な「早期失敗」のシグナルや、部分的な進捗を示す指標は存在しない。
3. 「二つの丘（Two-Hump）」現象: 著者らは、問題のインスタンスが二峰性に分布するという決定的な構造的障壁を特定した。ほとんどの提示は、容易に解けるもの（単純な貪欲な長さ減少による）か、あるいは実質的に不可能なもの（標準的なヒューリスティックが拒絶するような、一時的に長さを増大させる経路を必要とするもの）のいずれかである。決定的なのは、「困難だが解ける」中間的なインスタンスが極めて乏しく、これがカリキュラム学習を妨げる「谷」を作り出している点である。

手法

この難易度のギャップを埋め、二つの丘の分布を克服するために、著者らはアルゴリズムの革新、アーキテクチャ設計、および標的を絞ったデータ生成を組み合わせた三段構えのアプローチを提案している。

1. 行動空間：置換スーパームーブ（Substitution Supermoves）

原始的なAC操作の代わりに、著者らは**置換操作（substitution moves）**を主要な行動空間として導入している。

• メカニズム: 置換は関係式（relators）を巡回的なシーケンスとして扱い、一方が他方にキャンセルが発生する箇所で挿入される。これにより、複数の原始的な操作（AC1, AC2, AC3）を単一の行動へと統合する。
• 利点: これにより、エージェントはACグラフ内をより大きく意味のあるステップで進むことが可能になり、巡回置換を無視することで実効的な状態空間を大幅に削減できる。
• 理論的根拠: Ivanov (2018) は、もしAC予想が真であれば、置換はすべてのAC変換を実現するのに十分であることを証明している。

2. アーキテクチャ：デュアルリング・トランスフォーマー（Dual-Ring Transformer）

置換による大規模で構造化された行動空間を扱い、かつ問題の数学的な対称性を尊重するために、著者らはデュアルリング・トランスフォーマーを開発した。

• 巡回対称性: 絶対的な位置エンコーディングを使用する標準的なTransformerとは異なり、このアーキテクチャは関係式を巡回的なリングとして扱う。これは、アテンション・スコアが巡回距離 $d(i, j) = (i - j) \mod L$ に依存する巡回相対位置エンコーディングを採用している。
• クロスアテンション: ネットワークは両方の関係式を並列に処理し、クロスアテンションを用いて関係式 $r_1$ と $r_2$ の間の部分文字列の一致を特定する。これは、有効な置換操作を決定するために極めて重要である。
• ポリシー・ヘッド: 出力は有効な置換操作の分布であり、キャンセルが発生する箇所（$r_1[i] = \pm r_2[j]$）に至る行動のみが非ゼロの確率を受け取るようマスクされている。

3. データ生成：谷を埋める（Populating the Valley）

標準的な「スクランブリング（かき混ぜ）」戦略では、困難だが解けるインスタンスを生成できないことを認識し、著者らは二つの新しいデータ生成手法を用いている。

• 自己同型写像による摂動（Automorphism Perturbation）: 知られている自明な提示（例：$AK(2)$）に自己同型写像を適用することで、提示の経路特性を劇的に変化させる。元の提示は容易であっても、その自己同型像は長さを増大させるステップを必要とする可能性があり、これによって「容易な丘」から「谷」へと効果的に移動させることができる。
• 生成器・解決器ゲーム（Generator-Solver Game）: 非対称な二人零和ゲームを定式化する。生成器（PPOエージェント）は自己同型写像を適用して提示の難易度を高め、一方で解決器（貪欲探索）はそれらを自明化しようと試みる。生成器は、特に中間的な難易度領域をターゲットとして、解決器を困難にするインスタンスを作成したときに報酬を得る。
• 生成されるデータセット: このプロセスにより、AC-19（長さ $\le 19$ の125,192個の短いAC自明な提示）およびAC-1M（長さ $\le 30$ の1,136,154個の困難なAC自明な提示）が得られた。これらはこの種の大規模な公開データセットとして初となる。

主な結果

著者らは、1,190個の提示を含むMiller–Schuppベンチマーク・データセットを用いて手法を評価している。

• 性能向上: 置換スーパームーブとデュアルリング・トランスフォーマー（PPO-Sub-DRT）の組み合わせは、610個の提示を解決した（5つのシードの平均）。これは、以前の最良のRLベースラインである457（PPO-AC-ResNet）からの大幅な増加である。
• データのインパクト: 生成されたAC-1Mデータセットを組み込むことで、性能がさらに向上した。これは、標的を絞ったデータ生成が、エージェントが困難な提示に対する一般的な戦略を学習するのを効果的に助けることを示している。
• 経路の効率性: 置換を用いた貪欲探索（GS）は、網羅的な探索により多くのインスタンス（640個）を解決するが、PPOエージェントは特に困難な提示において、実質的に短い解決経路を発見する。PPOは、貪欲なヒューリスティックが拒絶する「長さを増大させる迂回」を見つけ出すことができ、エージェントが非自明な数学的構造を学習していることを証明している。
• アーキテクチャの優位性: 絶対位置エンコーディングを用いた標準的な形式の前処理を用いるバリアントと比較して、デュアルリング・トランスフォーマー（巡回相対エンコーディングを使用）は約25個多くの提示を多く解決しており、対称性を考慮した表現を学習することの重要性を強調している。
• 数学的進展: 著者らは、Miller–Schuppファミリーの中でこれまで未解決であった100個以上の提示の自明化に成功した。残りの未解決の550個の例を261個の異なるAC同値類へと削減しており、将来の研究のための具体的なチェックリストを提供している。

意義と主張

本論文は、アンドリュー・カーティス予想の進展には、単なる計算資源のスケールアップではなく、問題固有の困難さの構造を理解することが必要であると主張している。

• 二つの丘の洞察: 困難さの二峰性分布の特定は、なぜ従来のアプローチが苦戦してきたのかを説明し、アルゴリズムの改善と標的を絞ったデータ生成の組み合わせの必要性を動機づけている。
• 希薄な報酬環境におけるRL: 本研究は、解決のために数百の正確な逐次的決定を必要とする極めて希薄な報酬環境において、RLが成功できることを示しており、ロボティクス、定理証明、プログラム合成への転用可能な知見を提供している。
• 数学的有用性: AC予想が最終的に真であるか偽であるかにかかわらず、本研究は具体的な進展をもたらしている。もし真であれば、新たな自明化のたびに証明に貢献することになり、もし偽であれば、一見反例に見えるものを自明化することで、真の反例の探索範囲を狭めることになる。
• 転用可能性: 「二つの丘」の構造と、開発された技術（置換、巡回アーキテクチャ、生成器・解決器ゲーム）は、二峰性の難易度分布や進捗を阻害する動きが存在する他の数学的探索問題にも一般化可能であるとされる。

著者らは、さらなる進展は古典的な探索の微細な改善からではなく、固定されたヒューリスティックが捉えられない構造を搾取できる学習ベースの手法から得られるであろうと結論づけている。