What makes math problems hard for reinforcement learning: a case study

Ali Shehper, Anibal M. Medina-Mardones, Lucas Fagan, Bartłomiej Lewandowski, Angus Gruen +4 more
8/27/2024
cs.LGcs.AImath.CO

No official code found. Best implementation: shehper/AC-Solver (36 stars, MIT, last commit 2025-08-11).

Abstract

Using a long-standing conjecture from combinatorial group theory, we explore, from multiple perspectives, the challenges of finding rare instances carrying disproportionately high rewards. Based on lessons learned in the context defined by the Andrews-Curtis conjecture, we propose algorithmic enhancements and a topological hardness measure with implications for a broad class of search problems. As part of our study, we also address several open mathematical questions. Notably, we demonstrate the length reducibility of all but two presentations in the Akbulut-Kirby series (1981), and resolve various potential counterexamples in the Miller-Schupp series (1991), including three infinite subfamilies.

View on arXivView PDF

Code Implementations(1)

shehper/AC-SolverCommunity100%
MIT

A long-horizon, sparse-reward math environment for reinforcement learning. Official code repo for "What makes Math problems hard for reinforcement learning: A case study".

3617C++, PythonAug 16, 20241 years agoMIT
mathematicsreinforcement-learning-environmentstopological-data-analysis

Similar Papers

Limits of Generalization in RLVR: Two Case Studies in Mathematical Reasoning

80% match2025

Reinforced Generation of Combinatorial Structures: Hardness of Approximation

80% match2025

The complexity of non-stationary reinforcement learning

79% match2023

Finding Kissing Numbers with Game-theoretic Reinforcement Learning

79% match2025

Artifical intelligence and inherent mathematical difficulty

79% match2024

A Systematization of the Wagner Framework: Graph Theory Conjectures and Reinforcement Learning

79% match1 repo32024

Cite this paper

@article{shehper2024what,
  title  = {What makes math problems hard for reinforcement learning: a case study},
  author = {Ali Shehper and Anibal M. Medina-Mardones and Lucas Fagan and Bartłomiej Lewandowski and Angus Gruen and Yang Qiu and Piotr Kucharski and Zhenghan Wang and Sergei Gukov},
  year   = {2024},
  eprint = {2408.15332},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2408.15332v2}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2408.15332.svg)](https://codeofpaper.com/paper/2408.15332)

Discussion