The Two-Hump Problem: Bridging the Difficulty Gap in Mathematical Reinforcement Learning
For researchers applying RL to mathematical search problems, this work provides a method to overcome data scarcity in hard-but-solvable instances, enabling more effective training.
The paper identifies a 'Two-Hump' difficulty distribution in the Andrews-Curtis conjecture landscape that hinders RL training, and addresses it via novel data generation and algorithmic enhancements (supermoves, Transformers), achieving substantial performance improvements over baselines and releasing large-scale benchmark datasets (AC-19, AC-1M).
Mathematical search problems present a unique challenge for Reinforcement Learning (RL) due to vast search spaces and sparse rewards. In previous works, the Andrews-Curtis (AC) conjecture was established as an illustrative example of such problems. In this work, we identify a critical structural barrier in the AC landscape: a "Two-Hump" distribution, where problem instances are either trivially solvable or effectively impossible, with a scarcity of intermediate "hard-but-solvable" instances required for effective learning. We tackle this challenge through two primary avenues: novel data generation techniques to populate the difficulty gap, and significant algorithmic enhancements including the introduction of supermoves and Transformer-based architectures. We demonstrate substantial performance improvements over previous baselines, and release new comprehensive benchmark datasets including AC-19 (125,192 AC-trivial presentations of varying difficulty with length at most 19) and AC-1M (1,136,154 hard AC-trivial presentations of length at most 30), the first large-scale, publicly available datasets of this kind.