CayleyPy RL: Pathfinding and reinforcement learning on Cayley graphs

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., $10^{70}$ nodes) focusing 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: neural network architectures, random walk generators, 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. We examine the Cayley graph of the symmetric group with cyclic shift and transposition generators as a particular mathematical application. We strongly support the OEIS-A186783 conjecture that the diameter equals 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-1$ 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 the Gumbel distribution), the uniform distribution for the spectrum of the graph, and a numerical study of sorting networks. We create challenges on the Kaggle platform to stimulate crowdsourcing activity and invite contributions to improve and benchmark approaches to Cayley graph pathfinding and other tasks.