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

Researchers identify a critical structural problem in reinforcement learning for mathematical search tasks, specifically the Andrews-Curtis conjecture, characterized by a 'two-hump' distribution where instances are either trivial or unsolvable. The team addresses this through novel data generation techniques, algorithmic enhancements including supermoves and Transformer architectures, and releases two large-scale benchmark datasets (AC-19 and AC-1M) to advance the field.

This research tackles a fundamental challenge in applying reinforcement learning to mathematical problems: the sparsity of appropriately-difficult training examples. The 'two-hump' problem represents a critical discovery in RL landscape analysis, demonstrating that many real-world problem distributions contain insufficient intermediate-difficulty instances needed for effective model training. Traditional RL assumes a smooth difficulty gradient, but mathematical search spaces often violate this assumption, creating optimization obstacles.

The Andrews-Curtis conjecture serves as a concrete testbed for this broader phenomenon affecting formal mathematics, combinatorial optimization, and constraint-satisfaction problems. By identifying this structural barrier, the researchers provide both diagnostic clarity and practical solutions. Their approach of synthetically generating hard-but-solvable instances directly addresses the root cause rather than simply applying more compute or larger models. The introduction of supermoves and Transformer-based architectures represents architectural innovation tailored to the problem space.

The release of AC-19 and AC-1M datasets carries significant value for the research community, establishing reproducible benchmarks where none existed at scale. This enables systematic progress measurement and comparison across future approaches. For the broader AI field, this work highlights how problem structure, not just algorithmic sophistication, constrains learning performance—a lesson applicable to other domains with sparse reward or bimodal difficulty distributions.

Looking forward, researchers should investigate whether the two-hump phenomenon appears in other mathematical domains and whether the supermove and Transformer techniques generalize. The methodological framework for identifying and bridging difficulty gaps could inform curriculum learning strategies in other challenging domains.

• →The 'two-hump' distribution in mathematical RL problems creates a critical bottleneck where most instances are either trivial or unsolvable, with few intermediate examples for effective learning.
• →Novel data generation techniques successfully populate the difficulty gap, enabling RL models to train on appropriately-challenging instances.
• →Supermoves and Transformer-based architectures show substantial performance improvements over previous approaches in the AC conjecture domain.
• →Release of AC-19 (125,192 instances) and AC-1M (1,136,154 instances) provides the first large-scale public benchmarks for this problem class.
• →This work demonstrates that problem structure, not just algorithmic innovation, fundamentally constrains RL performance in mathematical search tasks.