about
What makes math problems hard for reinforcement learning (arxiv.org)
3 points by chbint on Aug 29, 2024 | hide | past | pdf | discuss on HN

In plain words: They used an unsolved question about rewriting group presentations to see why trial-and-error learning struggles to find the few cases that give big rewards. Their fixes and a new hardness score helped, and all but two of a known counterexample family can be shortened.

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

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.

Ali Shehper, Anibal M. Medina-Mardones, Lucas Fagan, Bartłomiej Lewandowski, Angus Gruen, Yang Qiu, Piotr Kucharski, Zhenghan Wang, Sergei Gukov
arXiv:2408.15332 · cs.LG, cs.AI, math.CO, math.GR, math.GT · submitted Aug 27, 2024 · updated Feb 11, 2025
abstract · pdf · html · 58 pages, 25 figures, 1 table. Try it: https://github.com/shehper/AC-Solver

add comment on HN
Also discussed: Feb 2025 (2 points, 0 comments)