# CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs

arXiv: https://arxiv.org/abs/2502.18663 · HTML: https://mlsanity.com/paper/2502.18663/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 18 of its 84 references that are in the map.
- First posted on arXiv 25 Feb 2025.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 18 of 18)

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Deep Learning for Symbolic Mathematics](https://mlsanity.com/paper/1912.01412/) (2019)
- [Quantum Circuit Optimization with AlphaTensor](https://mlsanity.com/paper/2402.14396/) (2024)
- [PatternBoost: Constructions in Mathematics with a Little Help from AI](https://mlsanity.com/paper/2411.00566/) (2024)
- [Global Lyapunov functions: a long-standing open problem in mathematics, with symbolic transformers](https://mlsanity.com/paper/2410.08304/) (2024)
- [Cayley Graph Propagation](https://mlsanity.com/paper/2410.03424/) (2024)
- [TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers](https://mlsanity.com/paper/2212.11730/) (2022)
- [Solving the Rubik's Cube Optimally is NP-complete](https://mlsanity.com/paper/1706.06708/) (2017)
- [Machine learning detects terminal singularities](https://mlsanity.com/paper/2310.20458/) (2023)
- [What makes math problems hard for reinforcement learning: a case study](https://mlsanity.com/paper/2408.15332/) (2024)
- [Advancing Geometry with AI: Multi-agent Generation of Polytopes](https://mlsanity.com/paper/2502.05199/) (2025)
- [Puzzle Solving without Search or Human Knowledge: An Unnatural Language Approach](https://mlsanity.com/paper/2109.02797/) (2021)
- [Learning Graph Search Heuristics](https://mlsanity.com/paper/2212.03978/) (2022)
- [Self-Supervision is All You Need for Solving Rubik's Cube](https://mlsanity.com/paper/2106.03157/) (2021)
- [Towards Learning Foundation Models for Heuristic Functions to Solve Pathfinding Problems](https://mlsanity.com/paper/2406.02598/) (2024)
- [A Machine Learning Approach That Beats Large Rubik's Cubes](https://mlsanity.com/paper/2502.13266/) (2025)
- [CubeTR: Learning to Solve The Rubiks Cube Using Transformers](https://mlsanity.com/paper/2111.06036/) (2021)
- [Probabilistic estimates of the diameters of the Rubik's Cube groups](https://mlsanity.com/paper/2404.07337/) (2024)

## Built on by (most cited first, 6 of 6)

- [Flow-based Extremal Mathematical Structure Discovery](https://mlsanity.com/paper/2601.18005/) (2026)
- [Learning Shortest Paths with Generative Flow Networks](https://mlsanity.com/paper/2603.01786/) (2026)
- [CayleyPy Growth: Efficient growth computations and hundreds of new conjectures on Cayley graphs (Brief version)](https://mlsanity.com/paper/2509.19162/) (2025)
- [Lectures on AI for Mathematics](https://mlsanity.com/paper/2604.11504/) (2026)
- [Learning the Graphical Nature of Symmetries](https://mlsanity.com/paper/2607.12026/) (2026)
- [CayleyR: Solving the TopSpin puzzle via cycle intersection](https://mlsanity.com/paper/2607.13219/) (2026)

## Abstract (arXiv)

This paper is the second in a series of studies on developing efficient artificial intelligence-based approaches to pathfinding on extremely large graphs (e.g. 1070 nodes) with a focus on Cayley graphs and mathematical applications. The open-source CayleyPy project is a central component of our research. The present paper proposes a novel combination of a reinforcement learning approach with a more direct diffusion distance approach from the first paper. Our analysis includes benchmarking various choices for the key building blocks of the approach: architectures of the neural network, generators for the random walks and beam search pathfinding. We compared these methods against the classical computer algebra system GAP, demonstrating that they "overcome the GAP" for the considered examples. As a particular mathematical application we examine the Cayley graph of the symmetric group with cyclic shift and transposition generators. We provide strong support for the OEIS-A186783 conjecture that the diameter is equal to n(n-1)/2 by machine learning and mathematical methods. We identify the conjectured longest element and generate its decomposition of the desired length. We prove a diameter lower bound of n(n-1)/2-n/2 and an upper bound of n(n-1)/2+ 3n by presenting the algorithm with given complexity. We also present several conjectures motivated by numerical experiments, including observations on the central limit phenomenon (with growth approximated by a Gumbel distribution), the uniform distribution for the spectrum of the graph, and a numerical study of sorting networks. To stimulate crowdsourcing activity, we create challenges on the Kaggle platform and invite contributions to improve and benchmark approaches on Cayley graph pathfinding and other tasks.