Research map / Reinforcement learning / Visual and representation RL
WHAT MAKES MATH PROBLEMS HARD FOR REINFORCEMENT LEARNING: A CASE STUDY
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Uses the Andrews–Curtis conjecture as a testbed for RL hardness, comparing greedy search, BFS and PPO on Miller–Schupp presentations, proposing adaptive action-space (supermove) ideas, and proving new AC-triviality and length-reduction results.
Problem
Finding rare, very long solution paths with sparse rewards is hard for RL and search; the Andrews–Curtis conjecture provides a finite-action, long-horizon testbed for studying what makes instances hard and for resolving potential counterexamples (AK(n), Miller–Schupp family).
Approach
Treats AC trivialization as an RL environment and compares greedy search, BFS and PPO, adds supermoves and variable horizon schedules, and uses path-length-based hardness to motivate adaptive action spaces; mathematically, it shows AK(n) is AC-equivalent to a shorter one-parameter family and that whole Miller–Schupp subfamilies are AC-trivial.
Key results
- Greedy search solved 533 of 1190 Miller–Schupp presentations versus 278 for breadth-first search; best fixed-horizon PPO (T=200) solved 431, below greedy search.
- Variable-horizon PPO (horizon 200 to 1200) solved two previously unsolved Miller–Schupp presentations, with AC paths of lengths 195 and 381.
- AK(n) is shown AC-equivalent to a presentation of length n+11, shorter than the original 2n+7 for n>=5.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use greedy search instead of breadth-first search | AC trivialization on the Miller–Schupp series · Miller–Schupp series (1190 presentations) | presentations solved: 278 -> 533 | Helped |
| Use PPO with constant horizon T=200 instead of breadth-first search | AC trivialization on the Miller–Schupp series · Miller–Schupp series (1190 presentations) | presentations solved: 278 -> 431 | Helped |
| Use PPO with constant horizon T=200 instead of greedy search | AC trivialization on the Miller–Schupp series · Miller–Schupp series (1190 presentations) | presentations solved: 533 -> 431 | Hurt |
| Increase constant horizon from T=200 to T=400 | PPO on the Miller–Schupp series · Miller–Schupp series (1190 presentations) | presentations solved: 431 -> 402 | Hurt |
| Increase constant horizon from T=200 to T=2000 | PPO on the Miller–Schupp series · Miller–Schupp series (1190 presentations) | presentations solved: 431 -> 219 | Hurt |
| Vary horizon from 200 to 400, 800, then 1200 during training | PPO on the Miller–Schupp series · Two presentations unsolved by greedy search | new presentations solved: two | Helped |
| Add supermoves selected from frequently occurring PPO path subsequences | PPO action space for AC trivialization · Andrews–Curtis trivialization | agent performance | Helped |
| Introduce too few supermoves initially or too many over training | PPO action space for AC trivialization · Andrews–Curtis trivialization | agent performance | Hurt |
Surprising findings
- Greedy search path lengths rarely increased beyond the initial length (maximum increase around 5), contrary to the generous relator length bound used.
- A misprint in a previously published Wirtinger presentation of an unknot diagram, unnoticed for over 20 years, undermines a claimed stable AC-triviality result.
Limitations
- PPO with fixed small horizons underperformed greedy search; only small 512-unit networks were tested due to compute limits.
- Supermove gains were modest and the adaptive action-space method is proposed as an idea rather than fully implemented.
Experimental setup
Datasets: Miller–Schupp presentations MS(n,w) with n<=7 and length(w)<=7 Akbulut–Kirby presentations AK(n)
Benchmarks: Miller–Schupp dataset (1190 presentations)
Metrics: number of presentations trivialized AC path length
Baselines: breadth-first search greedy search
Builds on: PPO Generalized Advantage Estimation Andrews–Curtis conjecture AC-moves Miller–Schupp series Akbulut–Kirby series
Closest papers by meaning
- Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contexts (NeurIPS 2025 · similarity 0.85)
- DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models (ICML 2025 · similarity 0.85)
- Computational Hardness of Reinforcement Learning with Partial $q^{\pi}$-Realizability (NeurIPS 2025 · similarity 0.84)
- Greedy Algorithms for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure (NeurIPS 2025 · similarity 0.84)
- DISCOVER: Automated Curricula for Sparse-Reward Reinforcement Learning (NeurIPS 2025 · similarity 0.84)
- PUZZLES: A Benchmark for Neural Algorithmic Reasoning (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.