Reinforcement Learning for Hard Mathematical Search: Lessons from the Andrews-Curtis Conjecture

Many mathematical problems ask for a concrete object or sequence of transformations whose correctness is easy to verify but whose discovery requires a long search. Such problems are natural candidates for reinforcement learning, yet they can be substantially harder than standard game environments: the state space may be infinite, rewards extremely sparse, and useful training instances difficult to generate. This article summarizes lessons from applying reinforcement learning to the Andrews–Curtis conjecture, a long-standing problem in combinatorial group theory. The central obstacle is a “two-hump” difficulty distribution in which instances are usually either easy for a greedy heuristic or beyond the reach of current methods. Three domain-guided interventions—substitution supermoves, a symmetry-aware Dual-Ring Transformer, and adversarial generation of hard-but-solvable data—substantially improve both learned and classical solvers. The case study illustrates a broader principle: in mathematical reinforcement learning, choosing the right actions, symmetries, and data distribution can matter as much as scaling the learning algorithm.