WHAT MAKES MATH PROBLEMS HARD FOR REINFORCEMENT LEARNING: A CASE STUDY
Authors: Ali Shehper
Anibal M. Medina-Mardones
Lucas Fagan
Bartłomiej Lewandowski
Angus Gruen
Yang Qiu
Piotr Kucharski
Zhenghan Wang
Sergei Gukov
Venue: NeurIPS 2025 poster ()
Keywords: reinforcement learning for mathematics
sparse-rewards search
long-horizon tasks
topological data analysis
Primary area: reinforcement_learning

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 analyze how reinforcement learning agents handle problems of varying hardness. We also address many mathematical questions as a part of our study. 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.

What makes math problems hard for reinforcement learning: a case study
Ali Shehper!
Anibal Medina-Mardonee
Lucas Fagan
Bartlomiej Lewandowski
Angus Gruen
Yang Qiu
Piotr Kucharski
Zhenghan Wang*
Sergei Gukov?
Department of Mathematics, California Institute of Technology
'Department of Mathematics, Western University
Department of Mathematics, University of California, Santa Barbara
Institute of Mathematics, University of Warsaw
'Polygon Zero CCernn Institute of Mathematics and LPMC, Nankai University
"Richard N. Merkin Center for Pure and Applied Mathematics, California Institute of Technology correspondence: mshehper@caltech.co edu
Abstract
Using long-standing conjecture from combinatorial group theory, we explore, from multiple perspectives, the challenges of finding rare instances carrying dispro- portionately high rewards. Based on lessons learned in the context defined by the Andrews-Cure conjecture, we analyze how reinforcement learning agents handle problems of varying hardness. We also address many mathematical questions as part of our study. Notably, two presentations in the Kirbl series (1981), and resolve various poten- tial counterexamples in the Miller Hiller-Schupp series (1991), including three infinite subfamilies.
demonstrate the length reducibility of all but
Introduction
In recent years, Artificial Intelligence (AI) systems have demonstrated remarkable success in board games, video games, and other tasks requiring extensive planning and intelligence. Mathematics appears to the next frontier, with increasing advancements
theorem-provers and theorem- provinn assistants (Azerbayev et al., [023] DeepMind, 2024) Yang et al. [2024] Lin et al.) [2024). Mathematical problems can often be framed as search problems, where the goal is to find path from a hypothesis to conclusion through sequence of basic logical steps.
For general mathematical problems, the action space is often mast-sometines infinite and solutions may require long sequences of steps, which may additionally be extremely rare in a large search space. As result, mathematical problems, particularly those the research level, present new challenges for AI systems and demand novel reinforcement learning algorithms.
At the same time, & Curtis 1965), which we study in this paper-off distinct advantages for algorithm development compared to generic mathematical problems. First, the action space in this setting is finite and small, consisting of only a few basic moves, while the state space is infinite. Second, these problems come with a notion of hardness, with diffieulty levels ranging from very easy to those requiring superexponential effort to resolve (Bridson 2015 Lishak 2017). Moreover, the distribution of states with respect to this measure is very non-umioon non-uniform.
mathematical problems such the
conjecture (Andrews)
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

These aspects provide unique opportunities for algorithmic development and may offer insights applicable to other complex problems. both mathematics and beyond. We anticipate that future reinforcement learning algorithms will need to assess problem hardness during training, adapting dynamically to the most challenging instances they encounter.
In this paper, we initiate the study of problem hardness in this context, with the goal of developing novel algorithms. Our contributions include:
Framing the Andrews-Curtis trivialization problem as a reinforcement learning en- vironment characterized by long horizons, sparse rewards, and an intrinsic distribution of problem hardness.
Developing an understanding of the hardness distribution for a large class of examples through intrinsic and path-based measures.
Analyzing how reinforcement learning agents handle problems of varying hardness and using these observations to propose novel reinforcement learning algorithms that dy- namically adapt to difficult challenges.
As byproduct, resolve various potential counterexamples the conjecture that had remained open for more than 25 years (Miller & Schupp, 1999). including three infinite subfamilies, and discover new results for another family that has been open for over 44 years (Akbulut & Kirby 1985). These results emerge from collaboration between human mathematicians and computational systems, forming feedback loop: mathematicians design computational tools; machines generate novel discoveries for specific instances; and mathematicians refine these discoveries into general results for infinite families.
These findings are of significant interest in mathematics and reinforce our belief that, in the coming years, reinforcement learning algorithms will play major role in the discovery of and important mathematical results.
Related Work
Reinforcement Learning, for long-horizon, sparse-rewanl environments. Long-horizon, sparse-rewards problems have been persistent challenge in reinforcement learning (RL), as they require agents to explore efficiently and learn from delayed and infrequent feedback. Atari games such as Montezuma's Revenge (Bellemare al.) 2013), which requires long-term planning collect keys and open doors, and Pitfall! (Machado et al. 2018)) 8) have exemplified these difficulties. Similarly, robotic tasks such as dexterous manipulation (Rajeswaran et al. 2017) require agents to learn complex sequences of actions with little intermediate feedback.
Several approaches have been developed to tackle long-horizon, sparse-reward problems, including intrinsic motivation (Pathak al.] [201], reward shaping (Ng et al.] 1999), and hierarchical reinforce- ment learning (HRL) (Sutton et al., 1999). Intrinsic motivation techniques such curiosity-driven exploration encourage agents to explore novel states even in the absence of external rewards. Reward shaping methods provide additional guidance to help bridge the sparse reward signal but require careful engineering to avoid unintended biases. HRL methods, including options frameworks (Sut) ton et al. 1999). hierarchical abstract machines (Parr & Russell 1997), and feudal reinforcement learning (Daynn Hinton 1992 Vezhnevets et al.) 2017) learn structured policies that decompose complex tasks into smaller sub-problems. More recently, memory- -based approaches (Ecoffet et al.) 2019 Badia et al. 2020 have been employed to improve long-term planning in these challenging environments.
Andrews-Curee Conjecture, Previous studies of the Andrews -urtiis conjecture have used various search algorithms, including genetic algorithms (Miasnikov) (203a)). breadth-first search (Havas & Ramsay 2003), and other more sophisticated algorithms (Bowman & McCaul 2006 Panteleev
Ushakov 2019
Krawiec & Swan 2016).

---

Background: The AC Conjecture
3.1
Mathematical statement
The Andrews Curtis conjecture is long- bong-standing conjecture in combinatorial group theory (Andrews
& Curtis 1965) concerning balanced presentations of the trivial group.
(.i....,, Fm (r,...., . consists of list of generators (the x; ') and list of relators (the rj (), where each relator is a word over the alphabet xx ... "m The length of x, denoted ((T), is the sum of the word lengths of all the relators, and x is said to be balanced if m As we only consider balanced presentations here, we will usually omit the adjective.
group presentation
The Andrews-Curtis (AC) conjecture states that any balanced presentation of the trivial group is AC-equivalent to the trivial presentation: (x) ( Zm .3....,mm.? That is, any such presentation can be transformed into the trivial one through a sequence of operations known as AC-moves:
1. Substitute some by rsTyy for i
2. Replace some r; by r;
3. Change some r; to 23 T,07
such a sequence of moves exists, we say that the starting presentation can be trivialized. In this work, also consider modified set of moves, which call AC'-moves.
1. Replace some r; by r,rj for + j.
2. Change some to 5 r.at".
The system of balanced presentations with AC-moves is equivalent the system of balanced presentations with AC'-moved as we show in Appendix F The Andrews-Curtis conjecture may be studied for any m. Here, focus on the case 2 and denote the generators 2, y instead of T2.
3.2 Potential counterexamples
Any presentation of length less than 13 is known to be consistent with the conjecture (Miasnikov 2003b Havas & Ramsay| 2003}. The shortest potential counterexample is the element AK(3) the Tollowing infinite family of potential counterexamples known as the Akbulut-Kirby series (Akbulut)
Kirby 1985):
AK(n) (,, y x" =," syr = yry)).
Another infinite family containing many potential counterexamples of interest is known the Miller-Schupp series (Miller & Schupp 1999):
MS(n, w) (x, y x "--""""= = n+1
x ===w. w)-
Here, 2 1 and is word in and y with
exponent
The two families are known
yryy be related: AK(n) is AC-equivalent to MS(n, y- -- for all n MMasnikov et al. 2002).
3.3 AC graph and path-based hardness measures
The AC graph consists of nodes and edges labeled respectively by presentations and AC moves. In this language, the conjecture states that, for any node, there path connecting it to the node representing the trivial presentation. Such path is called trivialization.
To measure how hard a presentation is to trivialize, choose cost function for paths and minimize over all trivializations of the given presentation. natural cost function the number of edges in path, called the path length. Another option is l-increase, which is defined for path y (To...., N by (o..g( E(TT)) {(TO).
Methods
4.1 Benchmark dataset
We evaluate our methods by counting the number of presentations solved from the benchmark dataset
D. We consider Miller-Schupp presentations MS(n, w) with n < 7 and Length(w) < up to

---

trivial identifications (see Appendix D). The resulting dataset contains 1 199 presentations. with maximal presentation length of 25. The methodology for constructing the dataset and the full list of presentations are provided in Appendix B
4.2 Classical search algorithms
We use two classical search brerithms-bbeedtt-ffin search (BFS) and greedy search (nd)-and we use -Cv-moves to search for AC trivializations. + In GS, the state with the smallest presentation length l is chosen, with ties being broken by the path length from the current state to the initial state.
Since the AC graph is infinite, an unconstrained search impractical. We restrict the search to presentations whose relators have word lengths at most 512. Despite this restriction, the search space remains vast. To prevent memory outages, we limit each algorithm visiting maximum of million nodes.
4.3 Reinforcement learning
The AC trivialization problem can be framed as sequential decision secision-making task within the Markov Decision Process (MDP) framework, enabling the application of reinforcement learning algorithms to solve it.
An MDP is characterized by five key components: the state space, action space, transition probability function, initial state distribution, and reward function. We now outline the specific choices made in formalizing the Andrews-Curtee problem an MDP and empirically evaluating the performance of reinforcement learning agents on this problem.
State space. The space of balanced presentations of the trivial group. As this state space is infinite, we impose an upper limit of 512 on the word length of each relator to make it finite.
Action spuce. We consider two choices for the action space: either the set of AC or AC' moves.
Transition probabilities. The transition probability function is deterministic. The trivial presentation, which has the shortest possible length f 2, is a terminal state of the MDP. Reaching a terminal trajectory and ends the episode.
state successfully solves the initial presentation
Initial state distribution, When attempting to solve presentations from the benchmark dataset D, we randomly sample from D following a uniform distribution.
Reward function. The AC conjecture does not come with a fixed reward function. One choice is to assign -1 to transition into a terminal state, indicating that presentation has been successfully solved, and 0 to every other transition. This reward function, denoted R₁ extremely sparse. We experiment with providing intermediate rewards that penalize transitions into long presentations,
{ (((44) if ((s(+1) > 2,
R2( Or, 81+1)
10244 Tmax otherwise.
The reward for the terminal transition 1024 . Tmax is chosen to counteract the accumulated penalties from long paths. Specifically, when the discount factor = 1, the lowest bound on the total return of any given trajectory is 10--100 10024 T as each of the two relators is allowed maximum word length of
'We tested few underwhelming.
search algorithms including A search and MCTS search but the results
A scarch is a half-way option between breadth first and greedy search, where the priority queue is sorted by the sum of the path length and presentation length 1. We tested family of search algorithms that sorted the priority queue using rp+11 for variety of choices of = 0, 1, 1... 10 and measured how many MS presentations each search algorithm solved. We found that decreasing improved the number of presentations solved with the maximum being at r 0 which corresponds to greedy search.
As for MCTS, we observed that spends meaningful amount of time exploring different paths which do not lead to trivialization solution. In contrast, the length heuristic function of greedy search helps find AC trivializations much faster, and with much smaller usage of system memory.
ACC moves provide an advantage over AC-moves in GS when nodes are ordered using presentation length f. Each AC' move affects f, providing signal to the search process. In contrast, the inversion move (AC2) leaves l invariant.

---

512. The large terminal reward precisely cancels out this worst-case sum, thereby ensuring that successful trajectory achieves a positive total return.
We also consider a third reward function Rg that clips the negative rewards at -10 and positive rewards 1000.
Maximum horizon length. Solving a Markov Decision Process requires specifying a maximum horizon length Tmxx and discount factor y. The horizon length Tmax is a key variable in our problem as presentations requiring AC paths of lengths longer than Tma would necessarily remain unsolved by any agent. Simultameously, there exist presentations for which the path length is superexponential function of the presentation length (Bridson 2013 Lishak 2017), ensuring that Andrews MDP is long- Long-horizon problem
The efficacy our algorithms depends on our choice of Taax- Hence, we experiment with different schedules for it.
1. Constant Schedule: We keep Taa a constant value throughout the training of a reinforce- ment learning agent, using Tmax = 200 and Tmaxx 400.
2. Piecewise Constant Schedule: We vary Tmax during training as follows. For agent trained for 100M environment interactions, we start T max at 200, increase to 400 after 10M interactions, 800 after 25M, and 1200 after 50M. We anticipate that the gradual increase in Tmax in the latter case will allow the agent to first master solving simpler presentations before progressively tackling more complex ones its abilities develop.
On the surface, these values seem much smaller than horizon lengths for various video game environments that reinforcement learning algorithms are known to excel at. However, difference between games and math environments is that there is no way to fail early during an episode and hence for an agent to learn what steps not to take.
Algorithms. We use Deep Q-Learning (DQN) Mnih al. 2015). Synchronous Actor-Critic (A2C) (Mnih 2016 Schulman et al. 2017), Proximal Policy Optimization (PPO) (Schulman et al. 2017). and A AlphaZero Silver et al. 2 to solve the andrews-Curtt MDPs.
State encoding. We encode each relator of a presentation as an array of length 512. The generators and their inverses - I. y. x=1 and y- are represented by integers 1, -1, and -2 respectively. If the length of the relator is less than 512, the array padded to the right with zeros. A balanced presentation of two relators is represented by an array of length 1024. AC and AC' moves implemented as functions on such arrays. If a move results in a presentation with a relator of length more than 512, is taken to act trivially instead.
Training setup. In our preliminary experiments of A2C, PPO and AlphaZero (discussed in Section we use feedforward neural networks with two hidden layers of 512 neurons each for both the actor and critic networks. The actor and critic networks do not share any parameters. In DQN experiments, feed-forward neural networks with two hidden layers of 842 neurons so that the number of parameters is roughly the same. A2C, PPO and DQN agents are trained for 100M environment interactions. AlphaZero agents are trained for approximately 5.7M environment steps with 32 simulations per environment step, taking approximately the same amount of wall-clock time as PPO training runs. We use reward-normalizatte
for on-policy algorithms (i.e. A2C and PPO).
In later experiments (see Section 5.2), we use residual networks consisting of six residual layers to train PPO agents for 1B environment interactions. Additional details the network architectures and experimental setup are provided in Appendix C For each training configuration, we train three agents with different random seeds and report the mean, minimum, and maximum performance.
'Roughly speaking, for these presentations, the numher of AC-moves required to trivialize the presentation at least A[olo { where A: N + N is defined recursively as A(j) 2 for j 2 1 and A(0) 2. For considerabyy small value f = 13, A( log, (13)]) 65536.
5

---

AlphaZero
350
MDP
AC,
290
200
AC, R4
AC, Rg
R
100
1039
Figure Comparison of RL agents across AC MDPs. Number of presentations solved from the benchmark dataset ID (Y-axis) versus number of environment steps (X-axis).
Results
5.1 RL: Comparing algorithms, rewards, and actions
For the two choices of action spaces and three choices of reward functions, we plot the performance of DQN, PPO and AlphaZero agents in Figure T The best choice of action space and reward function depends the choice of algorithm.
For either choice of action space, DQN struggles with sparse rewards (R1). Introducing intermediate rewards (R2) helps the performance, while clipping rewards (Rt) hurts the performance compared to dense and un-clipped rewards. This indicates that the agent benefits from distinguishing between presentations with total length greater than 10. Overall, the best DQN agent solves 303 presentations.
PPO agents do not benefit from intermediate rewards the same way as DQN. Sparse and dense rewards lead to comparable levels of performance when training with AC' action space. Clipping rewards (Rz) reduces variance training curves across different seeds, but does affect the mean performance. Over the entire training period, four out of six PPO agents perform approximately at the same level with the two exceptions being agents trained with AC moves and reward functions Ri and R3. These reward functions depend on the length of the presentation, which the inversion move (AC2) leaves invariant. these cases, agents settle early into a suboptimal policy, making repeated use of the AC2 move, and hence not fully exploring the state space. We also note that agents trained with AC moves and R₁ reward function are most sample-efficiens The best PPO agent solves 353 presentations.
As with DQN, AlphaZero performs poorly with sparse reward function (R1). The y-intercept in Figure (right) specifies the number of presentations solved by MCTS with randomly initialized policy and value networks. When training with dense reward function R2, the search process is able to identify actions that give shorter presentations, resulting in larger values of y-intercept. Overall, the best AlphaZero agent solves 242 presentations.
Finally, we remark that performances of A2C agents follows the same pattern across AC MDPs as the PPO agents. This is explained by previous observation that A2C is a special case of PPO Huang et al. (2022c). We present comparison of the best-performing A2C and PPO agents, both trained with sparse reward function R₁ and AC action space, in Appendix C
Our preliminary results indicate that PPO outperforms DQN, A2C, and AlphaZero on the AC problem. Coupled with the AC environment's low computational cost, which makes it well-suited to large-scale on-policy training, we therefore concentrate on PPO in the remainder of this paper.
5.2
BFS vs. GS vs. PPO
We compare the performance of BFS, GS, and PPO on the task of solving presentations in the benchmark dataset 'D Out of the 1190 presentations the dataset, BFS and GS solve 278 and 533 presentations respectively.

---

For PPO with constant horizon length schedule, the best agent with Tmax = 200 solved 457 presenta- tions, and the best agent with max 400 solved subset of these presentations size 402. With smaller horizon length, the agent spends less time exploring unpromising directions.
The PPO agent with max 200 solves five presentations that GS fails to solve. These cases require a substantial increase in l along the trivialization path-ssmething GS cannot accommodate due to its greedy behavior with respect to f. In contrast, PPO learns an effective exploration strategy over the AC state space, enabling it to discover these non-greedy trivialization paths.
When varying horizon length with the piecewise- constat schedule described above, the best PPO agent solved two new presentations from D that all other algorithms (including PPO with constant T max) are unable to solve. We provide complete list of all presentations solved by all algorithms in Appendix B The AC trivialization paths for all presentations solved by our algorithms are included in the supplementary material, which also includes the code to verify the correctness of these paths and to conduct the experiments discussed here.
5.3 Theoretical results
Our agents made two significant mathematical contributions: first, they discovered paths that resolved long-standing potential counterexamples to the Andrews- Curtis conjecture, and second, they revealed patterns in these paths that led us to formulate and subsequently prove new conjectures about infinite families of presentations. We state these results here, detailing their proofs Appendix [A] Theorem A. The following infinite subfamilies of Miller-Schupp presentations are AC-trivial:
1. MS(1, w) for all
2. MS(n, y 'yyx"= for all
3. MS(2, y 10002,"~r"0
for all k.
Theorem B. For every n 2 2, (K(n) is AC-equivalent to the presentation
(x,y) x yr zyæ zyz='y 'y xy"-'= = yzy), of length + 11. This gives reduction in length of (K for all 2 5.
6 Hardness distribution
In this section, we study the distribution of hardness for presentations in the dataset D using various measures.
6.1 Intrinsic measures: l and n
The goal state in the AC trivialization problem, i.e. the trivial presentation, has the shortest possible length. Hence, a natural intrinsic hardness measure for presentation its length é.
Figure
provides evidence that longer presentations are harder to trivialize. The relationship. however, is not predictive; MS(2, yx²yx yæ: 2) with & = 14 not trivialized by any of our algorithms, with = 23 is trivialized by both GS and PPO.
2a
but MS(6, y -
In the case of infinite families MS(n, w) and AK(n). another natural hardness measure is the integer n. The dataset DD contains 170 presentations for each n E (1,2,.... 7). Figure 2b shows that as n increases, the performance of our algorithms consistently declines.
6.2 Path-based measures
We two path-based measures-path length and ê-increase-to study hardness distributions of presentations solved by GS and PPO. In the case of PPO, we study the agent with Tmux 200 from Section 5.2 which solved 457 presentations.
6.2.1 Path length
We plot the distribution of path lengths for AC trivializations discovered by GS and PPO in Figure 3a and Figure 3b) respectively. In both cases, the distributions appear nearly continuous. Presentations
7

---

100
GS
160
GS
PPO
PPO
80
140
BFS
BFS
120
60
100
40
20
7
11
13
15
17
19
21
23
25
3
6
(a) Percentage presentations solved versus length (M, w)).
(b) Number of presentations solved versus of MS(n, w).
Figure 2: Distributions of the number of presentations solved by BFS, GS, and PPO with constant horizon length schedule as functions of lengths of the presentations and n.
300
200
275
290
150
300
100
300
79
(a) Bar plot of path lengths discov- Bar plot of path lengths discov- ered by GS. Path length (Y-axis) ered by PPO. Path length (Y-axis)
(c) Path lengths discovered by PPO (Y-axis) against (X-axis) for pre- against problem instances (X-axis). against problem instances (X-axis). sentations solved by both.
Figure Distributions of path lengths discovered by GS and PPO, and their comparison.
requiring longer indiiaivd higher complexity-an are highlighted red, while a long tail of casier presentations is shown in other colors.
comparison of path lengths for presentations solved by both PPO and GS is shown Figure 3c For many easy presentations, PPO learns shorter paths compared to GS. However, as presentations become more difficult, the paths discovered by PPO tend be longer than those found by GS reflecting that while our agents are trained to find trivialization paths, they are not trained to find the shortest paths possible.
6.2.2 E-increase
We plot the distribution of Ê-increase for AC trivializations discovered by GS and PPO in Figure 4a and Figure 4bl respectively.
400
300
200
100
distrbution pulhs.
(b) distribution paths.
Figure 4: Distributions of (-increase values in paths discovered by GS and PPO. Number of presenta- tions (Y-axis) against Ê-increase (X-axis).

---

500
200-
150-
50
Figure 5: Path lengths of trivializations found by GS (Y-axis) function of ê-increase (X-axis) for Schler-Schupppp presentations (n, w).
ensuring that it discovers paths with minimal f-increase values. As shown in Figure 4a GS paths exhibit an é-increase of zero in most cases, with maximum value of only 5. In contrast, PPO paths span much wider range of e-increase values ranging from to 27, as depicted in Figure 44b] Thus, we observe that path- based hardness measures may rely heavily on the choice of the algorithm.
GS prioritizes states based on the pair (e,4) (cf. Section 4.2
6.2.3 Relationship between path length and f-increase.
For presentations solved by GS we plot the solutions' path length as function of f-increase (Fig- ure 5). Path lengths increase proportionally with f-increase, indicating the presence of a correlation between the two hardness measures. While this trend is visible in the case of GS due to its greedy selection with respect there does not exist a similar pattern for paths discovered by PPO.
7 The cure: new algorithms
In this section, we summarize our insights and present new ideas for RI. algorithm development based on the lessons learned in the case study at hand. Specifically, argue that the following two elements can be useful Andrews- Curtis MDPs and in other long-horizon problems with sparse rewards and hardness distribution of problem instances:
Supermoves,
Adaptive action spaces.
The former refers actions that are compositions of basic moves. These appear to be a necessary, unavoidable tool to overcome superexponential lengths of sought-after solutions. Indeed, if the solution length is superexponential in the presentation length, E, the only way to turn into a polynomial sequence of steps is to allow steps grow in size, aggregating certain sequences of actions into new actions. We call these new actions growing size "supermoves".
Supermoves are closely related to the ideas of compound actions and options often studied in the subject of hierarchical reinforcement learning. Our proposal, however, that in long- mor-horizon, sparse- reward problems where problem instances follow distribution with respect certain hardness measures, we may use the understanding hardness itself to select new actions (supermoves) dynamically during training.
practical implementation can be as follows. Consider one the standard RL algorithms such as PPO with fixed action space, such that some of the actions are initially masked. In the process of training, we gradually unmask these actions and replace them with supermoves at 1 epochs, with N 1,, 3. During the intervals between the changes, we effectively train an RL model with fixed action space. For the training history at previous stages be useful at stage N. the changes to the action space at each stage must not be too large. The fraction of the action space that undergoes change a hyperparameter of the proposed algorithm, and it may suitable keep
range 5 - 15%. At each stage, labeled by N, one can take n hardest presentations solved by the RL agent with the action space A and add their successful solutions some subsequences of these successful solutions supermoves to the action space. This process is illustrated by diagram in Figure 6a

---

Environment
200
aclion d2
state reward
Agent
new actions
new hard
Aw
Upgrade policy/ / schedule
(a) A schematic representation of a model with an adaptive action space.
(b) Path length distributions of newly solved in- stances; hard instances are shown in red.
Figure 6: Visualizations of key concepts for supermoves and adaptive action spaces.
The implementation relies heavily on the notion of hardness with respect to very specific underlying RL model at hand. Thus, if the standard part of the RL cycle in Figure Galis based on a PPO algorithm with a particular choice of hyperparameters, then we need hardness with respect to this particular model.
As discussed in the previous sections, a good proxy for hardness can be the length of the solution path measured in basic elementary steps. In fact, we observe in preliminary experiments that at given stage N, typical distribution of this measure among solved examples often looks like Figure 6b with hard instances shown in red. (See Figure [3 for the distribution of path lengths in an actual PPO agent, and Figure in Appendix D for evidence that this behavior persists across scale, even as the total number of environment interactions vary.) For this hardness measure, we propose choosing sebbnceuss of AC paths for paths shown in red (hard), expecting that in the space of all sequences of actions of fixed length, these subsequences are both harder and more useful for the agent to learn.
Empirical evidence. While leave complete empirical investigation of these ideas to future work, we will describe some experiments that exhibit the utility of dynamic action spaces. Our setup is follows: we enhance the action space of 12 AC' moves to include all conjugations of the form + wrww-1 for i = 1, 2, where w is any word of length at most L. All actions are initially masked except for the original 12 AC' moves.
As the agent trained, we look for sub-sequences of actions its discovered solutions which of the type -ryw and unmask actions corresponding to these supermoves. We repeat this process after every 100 epochs. Further details and hyperparameters of the training setup are described in Appendix [
The agent solves 495 presentations including 13 new presentations that had eluded greedy search and PPO agents of Section We highlight these presentations in the table provided in Appendix B and provide a more detailed analysis of the discovered paths Appendix [
Limitations
This study has two primary limitations. First, the training dataset limited to 1190 presentations of the Miller-Schupp series. We expect that larger and more diverse set of balanced presentations would yield more capable agents. Second, our work is focused on the Andrews- -urttss conjecture. While we believe the lessons learned are broadly applicable, the generalizability of our findings to other mathematical problems requires further empirical investigation.
Acknowledgments and Disclosure of Funding
We would like to thank Danil Akhtiamov, Anna Beliakova, Jessica Craven, Michael Douglas, Konstantin Korovin, Miriam Lipniacka, Alexei Lisitsa, Maksymilian Manko, Ciprian Manolescu,
' is new hyperparameter, which we set to 6, For general L, there are 2 x 3 - 2 choices of w. The new action space thus has x 3 -4+ 4 = 3 actions. For L 6, this amounts 2916.
10

---

Fabian Ruehle, Michele Tarquini, Josef Urban, Richard Wedeen, and Tony Yue Yu for insightful discussions and comments. We especially want thank Anna Beliakova for igmiting our interest in the Andrews-Cuus Curttss conjecture as a framework for exploring problems with long and rare sequences of moves that an RI. agent must discover.
A.M.'s work is supported by NSERC grants RES000678 and R7444A03. The work of P.K. and B.L. has been supported by the Polish National Science Centre through Sonata grant (2022447/D/ST22020555, Y.Q. is supported by National Key R&D Program of China (2024FFA1012202) and Nankai Zhide Foundation.
References
Selman Akbulut and Robion Kirby. A potential smooth counterexample in dimension 4 to the Poincaré conjecture, the Schoenflies conjecture, and the Andrews-Curti conjecture. Topology, 24 (4):375-390, 1985.
James J. Andrews and Morton L. Curtis. Free groups and handlebodies. Proceedings of the American Mathematical Society, 16(2):122-195, 1965.
Zhangir Azerbayev, Bartosz Piotrowski, Hailey Schoelkopf, Edward W Ayers, Dragomir Radev, and Jeremy Avigad. Proofnet: Autoformalizing and formally proving undergraduate-leve mathematics. arXiv preprint arXiv:2302./2433 2023.
Adrià Puigdomènech Badia, Pablo Sprechmann, Alex Vitvitskyi. Daniel Guo, Bilal Piot, Steven Kapturowski, Olivier Tieleman, Martín Arjovsky, Alexander Pritzel, Andew Bolt, and Charles Blundell. Never give up: Learning directed exploration strategies, 2020. URL https://arxiv
org/ abs/ abs/a//2.....2///////22/2222222/ 06038.
Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253-279, 2013.
Jean-Daniel Boissonnat and Clément Maria. The simplex tree: An efficient data structure for general simplicial complexes. Algorithmica, 70:406-427, 2014.
R. Sean Bowman and Stephen B. McCaul. Fast searching for andrews-curtis trivializations. Experi- mental Mathematics, 1932)1993-197, 2006.
Martin R. Bridson. The complexity of balanced presentations and the Andrews-Curtis conjecture. arXiv preprini arXiv: 10.. 54050444444.... 2015.
Robert Burns and Olga Macedonska. Balanced presentations of the trivial group. Bulletin of the
London Mathematical Society, 25:513-526, 1993.
Gunnar Carlsson and Mikael Vejdemo-Johansson. Topological data analysis with applica- tions. Cambridge University Press, Cambridge, 2022. ISBN 978-1-108-83865 8386588. DOI: 10.1017/9781 108977704, URL https:://oi.org::: htt.///o..orr//// 1
Peter Dayan and Geoffrey E Hinton. Feudal reinforcement learning. In S. Hanson, Cowan, and C. Giles (eds.). Advances in Neural Information Processing Systems, volume 5. Morgan-
Kaufmann, 1992. URL httpss//pprrceeedingg htwp://eeeediinnnn..uueueeeeeeee neurips httpppppccccpppppp.ttffii.
pdff
DeepMind. Ai solves imo problems silver-medal level, 2024. URL Utthttp::/deppnndd..o
Hiscover/blogg www.b/loogaaillloeeaeeeee solves- imo pwoboooroommmm-oeoeoeo at silver medal -onddal-evve]] level/ Accessed: 2025-
01-30.
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. Go-explore: a new approach for hard-exploration problems. arXiv preprint arXiv:1901.1099 2019.
Logan Engstrom, Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Firdaus Janoos, Larry Rudolph, and Aleksander Madry. Implementation matters in deep policy gradients: A case study on PPO and TRPO. In International Conference Learning Representations, 2019.
11

---

George Havas and Colin Ramsay. Breadth-firs search and the Andrews-Curtis conjecture. Interna- tional Journal of Algebra and Computation, 13(1):61-68, 2003.
Shengyi Huang, Rousslan Fernand Julien Dossa, Antonin Raffin, Anssi Kanervisto, and Weixun Wang. The 37 implementation details of proximal policy optimization. In International Conference on Learning Representations Blog Track, 2022a.
Shengyi Huang, Rousslan Fernand Julien Dossa, Chang Ye, Jeff Braga, Dipam Chakraborty, Kinal Mehta, and Joo G.M. Arajo. Cleanrl: High-quality single-file implementations of deep reinforce- ment learning algorithms. Journal of Machine Learning Research, 23(274):1-18, 2022b. URL
http://jmlr. httpa//rrrrppppe////aeae http//aapaas////// 1342. html
Shengyi Huang, Anssi Kanervisto, Antonin Raffin, Weixun Wang, Santiago Ontañóón, and Rousslan Fernand Julien Dossa. A2c is a special case of ppo, 2022c. URL /ttts::///axx org./.v..rr/// abs/ 2205. 09123
Krzysztof Krawiec and Jerry Swan. Distance metric ensemble learning and the andrews-curtis conjecture, 2016.
Haohan Lin, Zhiqing Sun, Yiming Yang, and Sean Welleck. Lean-star: Learning to interleave thinking and proving. arXiv preprint arXiv:2407. 10040, 2024.
Boris Lishak. Balanced finite presentations of the trivial group. Journal of Topology and Analysis, 9 (2):363-378, 2017.
Alexei Lisitsa. New Andrews Curtis trivializations for Miller Schupp group presentations. Examples and Counterexumples, 6, 2024.
Marlos C. Machado, Marc G. Bellemare, Erik Talvitie, Joel Veness, Matthew Hausknecht, and Michael Bowling. Revisiting the arcade learning environment: evaluation protocols and open problems for general agents. J. Artif. Int. Res., 61(1):52335555 -622 January 2018. ISSN 1076-9757.
Clément Maria, Jean-Daniel Boissonnat, Marc Glisse, and Mariette Yvinec. The gudhi library: Simplicial complexes and persistent homology. In Mathematical Software-ICMS, pp. 167-174, 2014.
Alexei D. Miasnikov. Genetic algorithms and the andrews-curtis conjecture. arXiv preprint math/0304306, 2003a.
Alexei D Miasnikov. Genetic algorithms and the andrews-curtis conjecture. arXiv preprint math/0304306, 2003b.
Charles Miller and Paul Schupp. Some presentations of the trivial group. In Groups, Languages and Geometry, pp. 113-115, 1999.
Volodymyr Mnih. Asynchronous methods for deep reinforcement learning. arXiv:1602.01788, 2016.
arXiv preprint
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare G. Belle- mare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 51807540):599-33,, 2015. DOI: 10. 1038/nature142336
Alexei D. Myasnikov, Alexei G. Myasnikov, and Vladimir Shpilrain. On the Andrews-Curtis equivalence. Contemporary Mathematics, 296: 183-198, 2002.
Andrew Y. Ng, Daishi Harada, and Stuart J. Russell. Policy invariance under reward transformations: Theory and application reward shaping. Proceedings of the Sixteenth International Conference on Machine Learning, ICML '99, pp. 278-287, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc. ISBN 1558606122.
Dmitry Panteleev and Alexander Ushakov. Conjugacy search problem and the andrews-curtis conjecture. Groups Complexity Cryptology, 11(1):43-60, 2019.
12

---

Ronald Parr and Stuart Russell. Reinforcement learning with hierarchies of machines. In M. Jordan, M. Kearns, and S. Solla (eds.), Advances in Neural Information Processing Systems, volume 10. MIT Press, 1997. URL htttps:/pproceeddinge www.wepc.c..ppppreeeeooc Sttpaa/fiiee//ppee/eee////
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self-superrised prediction. In International conference machine learning, pp. 77877.777.
PMLR, 2017.
Aravind Rajeswaran, Vikash Kumar, Abhishek Gupta, Giulia Vezzani, John Schulman, Emanuel Todorov, and Sergey Levine. Learning complex dexterous manipulation with deep reinforcement learning and demonstrations. arXiv preprint arXiv: 709.. 10087, 2017.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
David Silver, Julian Schritwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lillicrap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. Mastering the game of go without human knowledge. Nature, 550(7676):554339) 2017. DOI: 10. nature24270.
David Silver, Thomas Hubert, Julian Schrittwieser, loannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, and Demis Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419): 140-1144, 2018. DOI: 10. 166sscinne. aar6404.
Richard S. Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 112(():181- 111118122111 1999. 1. URL https: :/wp:://ww
ISSN 0004-3702. DOI: https://doi.org/001011100 ssciencedirect.
Guillaume Tauzin, Umberto Lupo, Lewis Tunstall, Julian Burella Pérez, Matteo Caorsi, Anibal M. Medina-Mardones, Alberto Dassatti, and Kathryn Hess. giotto-rda: A topological data analysis toolkit for machine learning and data exploration. Journal of Machine Learning Research, 22(39):
1-6, 2021.
Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. In International conference on machine learning, pp. 3540-3549, PMLR, 2017.
Kaiyu Yang. Aidan Swope, Alex Gu, Rahul Chalamala, Peiyang Song, Shixing Yu, Saad Godil, Ryan Prenger, and Animashree Anandkumar. Leandojo: Theorem proving with cetrieval-augmennn language models. Advances Neural Information Processing Systems, 36, 2024.
13

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. or [NA]-
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because would be too computationally expensive" " or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
the checklist one of the factors in their evaluation.
"[No] " or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, so please just use your best judgment and write justification elaborate, All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The abstract and introduction claim that the paper explores the application of reinforcement learning to the Andrews-Curtis conjecture; studies hardness distribution of problems through intrinsic and path-based measures; and proposes algorithmic enhance- ments for long-horizer sparse-reward problems. They also claim that the paper solves several open mathematical problems. Section 4.3 frames the Andrews -Crtis conjecture MDP. Section 5.1 and Section 5.2 report the results of studying this MDP through reinforcement learning a algorithms. Section stsudiess the distribution of hardness of problems solved by various algorithms with respect to measures which are intrinsic problems as well as those that depend on AC paths. Appendix G also discusses a topological hardness measure for the AC graph. Section discusses algorithm enhancements, and Section 5.3 and Appendix A discuss the mathematical contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
14

---

The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings. is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of our work in Section g
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknow judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Section 5.3 summarizes the theoretical results that came from the empirical
exploration. Appendix A provides the precise mathematical statements with complete justification.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
15

---

4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
The detailed description of the Andrews- Curtis conjecture and the two types of moves use are explained in Section 3.1 The benchmark dataset on which experiments are based described in Section 4.1 with explicit construction given in Appendix [B] The discussion of the BFS and GS algorithms is discussed in Section 4.2 and comprehensive explanation of the RI. experiments including the architecture, state and action spaces, initial state distribution, reward function, network architecture, and hyperparameters can be found in Section 5.1 and Appendix C The paper also provides code for search algorithms as well PPO agents in supplementary materials. It also provides complete AC paths for all the presentations it claims to have solved, along with code to verify the correctness of those paths.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (c.g., s. a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g.. registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The paper provides the data and code, with sufficient instructions to faithfully reproduce the main experimental results supplementary material. This includes the code for search algorithms well as PPO agents. The supplementary materials also contain AC
16

---

reproducible, they paths for all the presentations the paper claims to have solved in Appendix B along with code to verify the correctness of these results. Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All data used is described in Section 4.1 and Appendix B Hyperparameters are found in Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: When comparing different reinforcement learning algorithms the perfor- mance of a single reinforcement learning algorithm on MDPs, we conducted experiments with 3 different seeds and reported their mean, min and max performance. See Figure
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
17

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
show in tables
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Information regarding the computational resources used for experiments is provided Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httppp////arrpss.cc/oo/////aaaat
Answer: [Yes]
Justification: The paper does not involve human subjects, personal data, or direct societal applications that would come into conflict with the ethical guidelines.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
The paper discusses how its contributions advance AI for mathematics and other sparse reward problems. But it does not address any potential negative societal impact of the work as the authors do not believe this work to have any such impact.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
18

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e-g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
The paper involves RL agents trained to solve instances of a group theoretic conjecture. This poses no obvious risk for misuse.
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We properly credit the CleanRL library (Huang et al.) 2022b). which was used for our PPO implementation. The library is distributed under the MIT License, as mentioned
in Appendix C
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
19

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta
latasets.papersstt
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The paper introduces a new benchmark dataset (detailed in Section 4. and Appendix B and RL agents/models (described in Section [5.]] and Appendix [ Code for classical search algorithms, RL agents, and the benchmark dataset are provided supplementary material. These new assets are released under the MIT License, and the documentation for their understanding and use is provided alongside the supplementary materials.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for rescarch with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
20

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM for what should or should not be described.
21

---

A Proofs of Mathematical Results
In this appendix, we provide proofs of all mathematical results discovered in this work. We re-state main results two theorems.
Theorem C. The following infinite subfamilies of Miller-Schupp presentations are AC-trivial:
1. MS(L, w) for all
2. MS(n, y Aay for n.
3. y - for all k.
Theorem D. For every n 2 2, AK(n) is AC-equivalent to the presentation
(x. y r = zyz -y. y. zy" r = yzy),
of length n + 11. This gives reduction in length of (K for all 2 5.
The three parts of Theorem are proven respectively as Theorems A.2 and A.3 and Corollary A.9 Theorem Dis proven as Theorem A.4
A.1 The Substitution Move
Our proofs rely on the following substitution move which comes from Burns Macedonska (1993).
Definition A.1 (Substitution). Let .m Fis.... ......,Te Ti-1, w -'',, ('tt1.... Tmm) be a balanced presentation of the trivial group with some words w, w' in generators. By sequence of AC-moves, we may replace any occurrence of relator ry (where j * i) with w'.
Substitution move is sequence of simple AC-moves. Consider by means of an example substituting w' for w in the relator wi ww2: first, conjugate to get w;; then multiply by w w--w' to write w2. For relator of the form Wi Ww2 W1-1 WWW,, we may similarly substitute any number of occurences of w with w'.
wyw,y w': and finally, conjugate again get the required result wi w'w2.
A.2 AC-triviality of two MS families
Theorem A.2. MS(1, w) is AC-trivial for all w.
Proof. We have
MS(1, w) (I, x yx --,,,== w)
where w has exponent sum in r. We can re-write the first relator in the following four ways:
1. yr xy²
2. x yy x1
3. x 1 1 = x1
4. y y x = ry -2
We can substitute these equations in the second relator to move around all occurrences of and x =1 relations (i) and (iv) move x to the left, relations (ii) and (iii) move x to the right. We continue until the second relator becomes z-- "/=x=" for some a, b Z. Through conjugation, this simplifies to yh, which when substituted into the first relator leads to trivialization of the presentation. D
The following result follows from this theorem.
Theorem A.3. MS(n, w.) for w. y1 -xyz is AC-trivial for all
22

---

Proof. In the presentation,
MS w.) (z. x x=-y"== x==,,==y
y- -==
we can rewrite the second relation y xy x², and apply the automorphism Z + to get (n, w.) (x. y x yr y² x" x ==+1).
This presentation is the same as MS(1, zz ")) which is AC-trivial by Theorem A.2
AC-trivializations of MS(n, w.) for n 3, 4, 7,8 were recently obtained using automated theorem proving in Lisitsa (202)) Here, we have obtained AC-trivialization of this family for all n.
A.3 Length reduction for AK(n)
Theorem A.4. For every 2 2, AK(n) is AC-equivalent to the presentation
(z.y y x yr zyz xy zyy=11a yzy),
of length n 11. This gives reduction in length of AK (n) ) for all n 2 5.
To prove this theorem, we will use the following result due to Myasnikov et al. (2002), and prove two additional theorems (Theorem A.6 and Theorem A.7). From these results, Theorem A.4 follows immediately.
Proposition A.S (Myasnikov, Myasnikov, and Shpilrain, (Myasnikov et al. 2002 ). For all n 2 2, AK(n) (n) is AC-equivalent MS(n, w1) where w1 = y -'xx "zy..
Theorem A.6. For euch fixed n. O, the 1-parameter family of presentations MS(n, wx) are all AC-equivalent. Here, Wp xx yry is parameterized by k E Z.
Proof. Starting with the presentation,
MS(n, wx) (1r, y -='1v" y 5 y Rx yry):
we will show that for any fixed n and k. MS(n, wx) is AC-equivalent to MS(n,, wx+1).
First, note that the first relation in MS wa) can be rearranged in the following three ways:
Multiplying by y =="2 from the left and by y from the right gives
y² aay = y k- "xy".
2. Multiplying by y1 from the left and by by from the right, and inverting the relation gives
(n- ry yry
3. Multiplying by y- from the left and by k from the right, and inverting the relation gives
p-- (n-1) yy+(k+) (k+1)
Now, we can rearrange the second relation to get y xaay"" = x yz. Substituting (i) gives
y zy" - - yx, which can rewrite yzy zy Now substituting (ii gives (n-1)
---11) zy k", which we may rewrite - (-- = ry x Finally, substitut-
ing (iil) gives y (b+1) - = zy- -1,,, which is equivalent to x = y (k+1 1) x- 2 yzy wh+1-
Theorem A.7. For each n > 0 and lo E Z, MS(n, wx) AC-equivalent to the presentation
P(n, k) = (x. y n k- n ' yo xyæ "1" n-k x = y k yry), of total length [k] + kl In n 11 + 11. For each fixed this length is minimum when = n which gives the presentation
P(n, n - 1) = (x, x yx = xyxx y = 1 -m (n-1) 1) -1 yay),
of length 11.
23

---

100
60
15
20
Figure 7: Number of presentations (Y-axis) versus (X-axis) for presentations in D.
Proof. Starting with the presentation,
MS(n, wx) (x. 1x=yy"" y= ya+! y xxx yyyy,
the second relation may be equivalently expressed as
1. xy xx-1zz
2. y xyy xyæ
Multiplying the first relation by y from the left and by y from the right, we get y- lxy", which may rewrite as yn-k-1 (y"my-") (v-lxy") y"-*, Substituting from (i) the LHS and from (ii) on the RHS gives the required result.
Combining the previous three results shows that, for each fixed n. AK(n) is AC-equivalent to all members of the infinite families MS(n, w&) and P(n, k). From this, Theorem A.4 follows immediately from setting & = n
Remark A.8. While P(n, 1) is always the shortest presentation from the P family, other P(n, k) may also give reductions in length of AK()). . To find which presentations of P-family are shorter than (K( we compare the length of AK (K),,,i,. i.e. 2n + 7, with the length of P(n, k) given by:
2n + 10 k,
if & n 1-1,
3k + 12 2n.
if 2 n.
This is less than 2n + 7 when 5 k or n S
(4n - 5).
We also note that the AC-triviality of AK(2), when combined with Theorem A.6 gives the following result.
Corollary A.9. Each member of the families MS(2, wx) and P(2, k) is AC-trivial.
B Benchmark Dataset
In this appendix, we describe the methodology used to obtain the benchmark dataset ' in Section 4.1
We start with larger dataset of all presentations from the Miller-Schupp series MS(n, w) with (nn < 7. This dataset contains AC-equivalent presentations which are related to each other through simple sequences of conjugation (AC3) moves. Consider, for example, the presentations and MS(n, 1
MS(n, x -1 the first presentation by and y gives the second presentation. When evaluating the performance of an algorithm on the task of solving potential counterexamples, it is easy to obtain inflated numbers (say 80 90%) by solving presentations that are related by small sequences AC-moves.
for a fixed n. Conjugating the second relator in
We make, therefore, the following reduction to our dataset: if x w and x: 'ww are related through a sequence of conjugation (AC3) moves, keep only 2 'w'). After this simplification, there are 170 choices of x: ww with f(w) I 7 as listed in the table below. With < 7, benchmark dataset D consists of 7 170 1190 presentations.
of the two presentations MS(n. x= ww) and
As discussed Section an intrinsic measure of hardness for presentation is length f. We plot the distribution of lengths in our dataset D in Figure 7

---

In the table below, we specify the status of each presentation as "solved" or "unsolved" by our algorithms (cf. Section (52)). 533 presentations solved by the greedy search are all mentioned in black; five presentations solved by PPO agent with max 200 are mentioned in blue; and the two presentations solved by PPO agent with piecewise-consaal horizon length are mentioned in red. Lastly, presentations solved by PPO agent trained with dynamic action spaces and supermoves (cf. Section 7 shown in orange.
It may be easy to solve many more presentations in the dataset by simply scaling the techniques presented in this paper-fo for example, by using larger neural networks for PPO or by increasing the number of nodes visited during greedy search. However, what should be considered true success for an algorithm is its ability solve hard presentations, for which the shortest AC trivialization path may have thousands, if not hundreds of thousands, of moves. We expect that MS(n, y x yyzy) presentation known to be AC-equivalent to AK(n) (Myasnikov et al. 2002 may be one such example.
n 3
5
7
g
solved solved solved solved solved solved solved
y
solved solved solved solved solved solved solved
y
solved solved solved solved solved solved solved
solved solved solved solved solved solved solved
g
solved solved solved solved solved solved solved
solved solved solved solved solved solved solved
yryz
solved solved unsolved unsolved unsolved unsolved unsolved
yoy 1
solved solved solved solved solved unsolved unsolved
x. y²
solved solved solved solved solved solved solved
xy
solved solved solved solved solved unsolved unsolved
x y my
solved solved unsolved unsolved unsolved unsolved unsolved
y
solved solved solved solved solved solved solved
yry x-
solved solved solved unsolved unsolved unsolved unsolved
youge y)
solved solved unsolved unsolved unsolved unsolved unsolved
yzyz
solved solved unsolved unsolved unsolved unsolved unsolved
yoy x y
solved solved solved solved solved
unsolved unsolved
yoy x y
solved solved solved solved solved unsolved unsolved
yoy 2x
solved solved solved unsolved unsolved unsolved unsolved
y xyyx
solved solved solved unsolved unsolved unsolved unsolved
yx
solved solved unsolved solved unsolved unsolved unsolved
solved solved solved solved solved solved solved
ya y xzy
solved solved solved solved solved unsolved unsolved
yx y x4
solved solved unsolved unsolved unsolved unsolved unsolved
xz²²
solved solved solved unsolved unsolved unsolved unsolved
x ry
solved solved solved unsolved unsolved unsolved unsolved
x y 2xy
solved solved unsolved solved unsolved unsolved unsolved
x- y my
solved solved solved solved unsolved unsolved unsolved
y 1 wyyx
solved solved solved solved solved unsolved unsolved
xy
"
solved solved unsolved unsolved unsolved unsolved unsolved
y
solved solved solved solved solved solved solved
yx yx
solved unsolved unsolved unsolved unsolved unsolved unsolved
yx y 1 -2
solved unsolved unsolved unsolved unsolved unsolved unsolved
yry
solved solved solved solved solved unsolved unsolved
yary" y
solved solved solved unsolved unsolved unsolved unsolved
yry x
"
solved solved solved unsolved unsolved unsolved unsolved
yorge 'y²
solved solved unsolved unsolved unsolved unsolved unsolved
y
solved solved unsolved unsolved unsolved unsolved unsolved
x
solved solved solved solved
unsolved unsolved unsolved
yzy x 9
solved solved solved solved unsolved unsolved unsolved
yoy 2
solved solved solved unsolved unsolved
unsolved
unsolved
25

---

w
n
n
yey x
solved solved solved
unsolved unsolved
unsolved
unsolved
yry x
solved solved unsolved unsolved solved
unsolved
unsolved
solved solved solved
solved
unsolved
unsolved
unsolved
y² vyy y
solved solved solved
unsolved
unsolved
unsolved
unsolved
y xzzx y
solved solved solved solved
unsolved unsolved
unsolved
solved solved unsolved solved unsolved unsolved unsolved
ay x y
solved solved unsolved solved unsolved unsolved unsolved
y ry
solved solved solved solved solved solved solved
yaayx"
solved solved solved unsolved unsolved unsolved unsolved
y'ry"" -x'
solved solved solved unsolved unsolved solved unsolved
solved solved solved solved solved solved solved
x y xy
solved solved solved solved unsolved unsolved unsolved
y²x xz
solved solved unsolved unsolved unsolved unsolved unsolved
yx y xy
solved solved solved unsolved unsolved unsolved unsolved
yz y zy
solved solved solved unsolved unsolved unsolved unsolved
ya y Yxy
solved solved unsolved solved unsolved unsolved unsolved
yx y 2 2x
solved solved solved solved unsolved unsolved unsolved
x 2 x
solved unsolved unsolved unsolved unsolved unsolved unsolved
y x
solved unsolved unsolved unsolved unsolved unsolved unsolved
y xy
solved solved unsolved unsolved solved unsolved solved
x= xy
solved solved solved unsolved solved unsolved unsolved
x xxy
solved solved solved solved solved solved solved
x y xT
solved solved solved solved unsolved unsolved unsolved
x y xy
solved solved solved unsolved unsolved solved unsolved
y Sry
solved solved solved unsolved unsolved unsolved unsolved
xyy xr
solved solved solved unsolved unsolved unsolved unsolved
xzæ
solved solved solved solved
unsolved
unsolved
unsolved
xy x y
solved solved unsolved unsolved unsolved unsolved unsolved
xy x y
solved solved solved unsolved unsolved unsolved unsolved
y
y xy
solved solved unsolved solved unsolved unsolved unsolved
y 2xy
solved solved solved solved unsolved unsolved unsolved
solved solved solved solved solved solved solved
yx y²
solved unsolved unsolved unsolved unsolved unsolved unsolved
yx yr yr
solved unsolved unsolved unsolved unsolved unsolved unsolved
ya yo y
solved unsolved unsolved unsolved
unsolved unsolved unsolved
yx 1xr-zz yx y
solved unsolved unsolved
unsolved
unsolved unsolved unsolved
yr
x
solved unsolved unsolved
unsolved
unsolved unsolved unsolved
yr" x brlyy
solved unsolved unsolved
unsolved
unsolved unsolved unsolved
yx
2y
solved unsolved unsolved
unsolved
unsolved unsolved unsolved
y y 2
solved unsolved unsolved
unsolved
unsolved unsolved unsolved
yx 4 y r y
solved unsolved unsolved
unsolved
unsolved unsolved unsolved
yx"y y
solved unsolved unsolved
unsolved
unsolved unsolved
unsolved
yoytye
solved unsolved unsolved
unsolved
unsolved
unsolved
unsolved
yryar x
solved unsolved
unsolved unsolved unsolved unsolved unsolved
yry
solved solved
solved unsolved unsolved unsolved unsolved
yay" y
solved solved solved unsolved unsolved unsolved unsolved
yaud w x
solved solved solved unsolved solved
unsolved unsolved
guu. x
y
solved solved solved unsolved unsolved unsolved unsolved
" x
solved solved solved unsolved unsolved unsolved unsolved
yzyx y"
solved solved unsolved unsolved unsolved unsolved unsolved
yoyz
solved solved unsolved unsolved unsolved unsolved unsolved
yry ryx
solved unsolved unsolved unsolved
unsolved
unsolved unsolved
yey ry 12
solved unsolved unsolved unsolved
unsolved
unsolved
unsolved
26

---

w
n
n
yay x
solved
solved solved
unsolved unsolved
unsolved
unsolved
yzy x y
solved solved solved solved unsolved
unsolved
unsolved
yay x 11
solved solved solved
unsolved
unsolved
unsolved
unsolved
yor x y
solved solved solved unsolved
unsolved
unsolved
unsolved
yay y
solved solved unsolved unsolved
solved
unsolved
unsolved
yey x
solved solved unsolved unsolved
solved
unsolved
unsolved
yey x
solved solved solved
unsolved
unsolved
unsolved unsolved
y² yo yxr
solved solved unsolved unsolved unsolved unsolved unsolved
1/ y x==
solved solved unsolved unsolved
unsolved unsolved unsolved
solved solved unsolved solved
unsolved unsolved unsolved
y"
solved solved solved solved
unsolved unsolved unsolved
y y'ay"x x:
solved solved solved solved unsolved unsolved unsolved
y² y2²
solved solved solved unsolved unsolved unsolved unsolved
y' y
solved solved solved solved unsolved unsolved unsolved
y-yy
solved solved unsolved solved unsolved unsolved unsolved
yxzy y
solved solved unsolved solved unsolved unsolved unsolved
y xz 2x
solved solved solved solved solved solved unsolved
y xy
solved solved solved solved solved solved unsolved
ya 3x
solved solved solved solved solved unsolved unsolved
y'
solved solved solved unsolved unsolved unsolved unsolved
yyyy
solved solved solved unsolved unsolved unsolved unsolved
ary
solved solved solved unsolved unsolved unsolved
unsolved
y' y
solved solved solved unsolved unsolved
unsolved
unsolved
solved solved solved unsolved unsolved solved
unsolved
yay 2
solved solved solved unsolved unsolved solved unsolved
y baayx
solved solved unsolved solved unsolved unsolved unsolved
yxy 1x
solved solved solved solved unsolved unsolved unsolved
y
solved solved solved solved solved solved solved
y' y xy
solved solved solved unsolved unsolved unsolved unsolved
y y xy
solved solved unsolved unsolved unsolved unsolved unsolved
y² y xy²
solved solved solved unsolved unsolved unsolved unsolved
x y xy
solved solved solved unsolved unsolved unsolved unsolved
3 x y Fxy
solved solved unsolved solved
unsolved unsolved unsolved
4² x y xy
solved solved solved solved unsolved unsolved unsolved
ya y 1 2
solved unsolved unsolved unsolved unsolved unsolved unsolved
yx xty
solved unsolved unsolved unsolved unsolved unsolved unsolved
x²yx
solved unsolved unsolved unsolved unsolved unsolved unsolved
yx y x
solved unsolved unsolved unsolved unsolved unsolved unsolved
yo y xz
solved solved unsolved unsolved solved unsolved unsolved
yo
y xny
solved solved solved unsolved solved unsolved unsolved
yx y 2 xxy²
solved solved solved solved solved solved unsolved
2 zz yx
solved solved solved solved unsolved unsolved unsolved
ya y Bay
solved solved solved unsolved unsolved solved unsolved
yx y xxy
solved solved solved unsolved unsolved unsolved unsolved
y
xx y2
solved unsolved unsolved unsolved unsolved unsolved
unsolved
solved unsolved unsolved unsolved
unsolved unsolved unsolved
wyyay
solved unsolved unsolved
unsolved
unsolved
unsolved
unsolved
y ryoy
solved unsolved unsolved
unsolved
unsolved
unsolved
unsolved
2 xy xy
solved unsolved unsolved
unsolved
unsolved unsolved unsolved
y xy xy
solved unsolved unsolved
unsolved
unsolved unsolved unsolved
solved solved unsolved
unsolved
unsolved unsolved unsolved
- 2 x
solved solved unsolved
unsolved
unsolved
unsolved unsolved
x x1y y 22 yx
solved unsolved unsolved unsolved
unsolved
unsolved
unsolved
27

---

N
n
solved unsolved unsolved
unsolved unsolved
unsolved
unsolved
x my
solved solved solved unsolved unsolved
unsolved
unsolved
x xy
solved solved
solved
unsolved
unsolved
unsolved
unsolved
x
yj yf x
solved unsolved unsolved
unsolved
unsolved
unsolved
unsolved
y xxy
solved unsolved unsolved
unsolved
unsolved
unsolved
unsolved
my
solved solved
solved
solved
solved
unsolved
unsolved
x
xy
solved solved unsolved solved solved unsolved unsolved
x. y ry
solved solved solved unsolved unsolved solved unsolved
y xy
solved solved solved unsolved unsolved unsolved unsolved
x y xy
solved solved solved solved unsolved unsolved unsolved
x
xy
solved solved unsolved solved unsolved unsolved unsolved
xy x
solved solved unsolved unsolved solved unsolved unsolved
1 xy x
solved solved solved unsolved unsolved unsolved unsolved
y zy
y
solved solved solved unsolved unsolved unsolved unsolved
y xy
y
solved solved unsolved unsolved unsolved unsolved unsolved
xy
y
solved solved solved unsolved unsolved unsolved unsolved
1 xy 3 x
1 x y xz
solved solved solved unsolved solved unsolved unsolved
solved solved solved solved solved solved unsolved
x y xz
solved solved solved solved unsolved unsolved unsolved
y y kxy
solved solved solved unsolved unsolved unsolved unsolved
1 y -xy
solved solved solved unsolved unsolved unsolved unsolved
y ayy
solved solved unsolved unsolved unsolved unsolved unsolved
xy x
solved solved solved solved unsolved
unsolved
unsolved
y
solved solved solved solved solved
solved
solved
C Experimental Setup
In this appendix, we provide details of the experimental setup for various reinforcement learning agents discussed in the main text.
PPO and A2C
We trained agents using Synchronous Actor-Critic (A2C) (Mnih 2016 Schulman et al. 2017) and Proximal Policy Optimization (PPO) (Schulman al. 2017 algorithms. Both of these algorithms use an actor network to learn the policy function and a critic network to learn the value function. We used unshared networks in both cases. For the experiments of Section 5.1 all neural networks are chosen to be feed-forward neural networks with 2 hidden layers of 512 neurons. For the experiments
of Section 5.2 both actor and critic networks are residual neural networks with six residual layers, where each residual block consists of two feed-forward layer with 512 neurons. We used Adam optimizer for training in all cases.
The performance of PPO is known to be highly sensitive to various implementation details in addition the choice of hyperparameters (Huang al. 2022a Engstrom al. 2019). Following (Engstrom et al., 2019), we used advantage normalization and clipped value loss. We also used reward normalization in all experiments. the KL divergence between the old and the updated policy exceeded the target KL divergence in a mini-batch, we skipped the remaining mini-batches in the optimization phase to avoid large jump in policy.
The A2C and PPO agents discussed in Section 5.1 are trained for 100M environment interactions. Both algorithms achieve the best performance when trained with sparse rewards and AC action space. With this setup, their performance is compared in Figure
The agents discussed in Section 5.2 are all trained for 1B environment interactions. The full list of hyperparameters for agents of Section 5.1 and Section 5.2 are given in Table and Table respectively.
28

---

250
Agent
300
A2C
250
200
100
40M
8CM
150M
Figure 8: PPO vs. A2C
Table 2: Hyperparameters of PPO agents discussed Section 5.1
Hyperparameter
Value
Rollout Length
200
Number of Parallel Actors
28
Total Number of Environment Interactions
10a
Learning rate
1.0 10 10-4
Number of Epochs
1
Number Mini-batches
Discount (7)
0.999
GAE Parameter (A)
0.95
Clipping Parameter (c)
0.2
Value Loss Coefficient (ci)
0.5
Entropy Loss Coefficient (c2)
0.01
Adam Epsilon Parameter
10-5
Target KL Divergence
0.01
Our implementation of PPO is based the CleanRI. library (Huang et. 2022b), which is distributed under the MIT License.
DQN
We trained our Deep Q-Network (DQN) agents using the Adam optimizer with a constant learning rate of 2.5e-4. We employed replay buffer with capacity of 500, 000 transitions, and training began
Table 3: Hyperparameters of PPO agents discussed in Section 5.2
Hyperparameter
Value
Rollout Length
200
Number of Parallel Actors
1190
Total Number Environment Interactions
10a
Learning Rate
10-1
Number of Epochs
Number of Mini-batches
Discount (7)
0,999
GAE Parameter (A)
0.95
Clipping Parameter (c)
0.2
Value Loss Coefficient (c1)
0.5
Entropy Loss Coefficient (c2)
0.01
Adam Epsilon Parameter
10
Target KL Divergence
0.01
29

---

after an initial 20, 000 timesteps of data collection. Updates were performed after every environment step by sampling 64 mini-bate nini-batches; each of 256 transitions. For exploration, an epsilon greedyy strategy was used, with linearly annealed from 1.0 to 0.05 over the first 5 million timesteps. A target network was used for stability, with its weights being hard-copied from the online network every 1, 000updates (r = 1.0). The discount factor (7) was set to 0.999. Each agent was trained for total of 100 million timesteps across 1190 parallel environments.
AlphaZero
We trained all AlphaZero agents for roughly 5.7M iterations using the Adam optimizer with a learning rate of le 4. In each iteration, data generated via self-play across 1190 parallel environments, with each episode lasting a maximum of 200 steps. At each step of self-play, Monte Carlo Tree Search (MCTS) was conducted with 32 simulations search process was guided by the PUCT formula, with exploration parameters set to 1.25 and co set to 19652. The training phase utilized mini-batches of 2048 samples, optimizing combined loss function of softmax cross-entropy for the policy and mean squared error for the value. Value targets were computed as the undiscounted Monte Carlo returns from the elff-play games.
determine the next action. The
PPO with dynamic action spaces
The agent described Section iis is trained with the same hyperparameters as the ones described in Table 3 with a few small changes which we describe now. As in the table, the agent is trained for total billion environment interactions. As we use 1 199 parallel environments and each rollout consists of 200 timesteps, training consists of total of 109 /11990 200) 4200 iterations. We unmasked new actions every 100 iterations. Hence, the action space is modified 42 times. After each modification of the action space, we temporarily increased and then annealed the co-efficient of entropy loss from 0.01 to 0.05 over the next 20 epochs through a piecewise-linear schedule. This is encourage the agent from exploring the state space with the help of new unmasked actions. By the end of training, total of 405 actions were unmasked. Most of the unmasked actions corresponded to words of lengths and
D Path Analysis
In this appendix, we provide analysis of paths discovered by the agent of Section 7 As described there, the new agent, trained with dynamic action space and supermoves, solved 495 presentations. 478 of these 495 presentations were also solved by greedy search, and presentations were previously solved by the PPO agents described in Section 5.2 The 13 new presentations with their values of n. w and path lengths (in terms of supermoves as well as elementary AC' moves) are shown in Table 4
72
W
i = 2n + Length(w)
Naupermoves
NAC moves
E-increase
5
19
196
284
12
5
yor y rz
19
192
277
8
5
yzy x y
19
182
248
11
5
yoy x
19
172
231
14
4
xyx
18
156
210
21
4
you x y²
18
156
210
5
y xy x y
21
104
137
7
y xny
25
90
115
13
3
yey x
17
81
101
7
6
y'ay" -1a
22
72
94
6
6
x " "y
22
8
4
y²my"" x
19
62
82
4
y²wy "x "y
19
53
74
7
Table 4: Path lengths and (-increase for various words w and parameters n.
We observe that in 6 out of cases, path lengths are less than our maximum horizon length of 200, but they exceed 200 when interpreted in terms of elementary AC' moves. In these cases, expanding
30

---

the action space has helped us discover AC-iiivialisatios with paths longer than the maximum horizon length (200) of the original best agent from Section 5.2 as well.
E
Dependence of hardness measures on scale
The PPO agent analyzed in Section 6.2 was trained with Tmx 200 for approximately 1 billion environment interactions. We observed that the lengths of trivialization paths discovered by the agent follow an almost continuous distribution, shown in Figure 3b
We hypothesize that at each scale of computation-mmasuree by the total FLOPs used train an agent-a similar distribution of path lengths emerges. A few presentations exhibit significantly long path lengths, making them the hard cases at that scale, while many others have short path lengths and can be considered easy. Here, we provide evidence supporting this hypothesis.
Keeping the actor and critic network sizes fixed at three-layer feed-forward neural network with 512 neurons per hidden layer, we varied the total number of environment interactions used to train the PPO agent from 1 million to 80 million. For each fixed number of interactions, we trained agents with three different seeds and tuned the learning rate to maximize the number of solved presentations. The resulting scaling trend shown on log-log scale in Figure
300
200
100
MM
10w
10oM
Figure 9: Number of presentations solved (Y-axis) against the total number of environment interac- tions used train a PPO agent (X-axis).
In Figure 10
we plot the distributions of path lengths discovered by the most capable agent, which was trained for 80 million environment interactions. We color the bar of presentation with respect the first scale, in terms of total number of environment interactions, at which the presentation is solved. We make two observations about our results:
1. The overall distribution of path lengths closely resembles that of the agent trained with billion environment interactions shown in Figure 3b
2. Agents trained for longer amounts of time discover paths of longer lengths, indicating that agents trained for longer amounts of time are capable of solving harder presentations.
38
Figure 10: Bar plot of path lengths discovered by PPO agent trained for 80 million environment interactions. Path length (Y-axis) against problem instances (X-axis). Bars are colored with respect to the minimum number of total environment interactions at which the presentation first solved.
F Equivalence of AC and AC' Moves
In the main text of this paper, we defined AC-moves and AC'-moves. We will prove here that two presentations are AC-equivalent if and only if they are AC' -Cu-equivalent.
31

---

First, we recall the definitions of Ao-moses:
1. Substitute some by vary for i j.
2. Replace some r; by ;
3. Change some ry to 2j raa
We also recall the definitions of Aooves.s:
1. Replace some r; by r:rj for +
2. Change some to 2- (i
The difference between the two sets lies in how the inversion (AC2) of relator is handled. We always follow an inversion (AC2) by a concatenation (ACI) in AC'I, while the original AC-moves allow for standalone inversion.
We can show that two presentations are AC-equivllen if and only they are AC' equiivalll by prov- ing that AC2 can be recovered from AC' moves. To this end, consider two-generator presentation (I1, T2 r1, r2). The sequence AC' moves.
22 T2
r1 - 1172
12 + 1211
12 rir2ri
results in the presentation (01. 22 r2 rI), which the same as 72 up to swapping the two relators. A similar argument also holds for any pairs of relators in an m-relator presentation.
Strictly speaking, swapping two relators changes the presentation. However, consider the two
presentations (21.02 r1, r2) and (I1,T2 Tt) to be the same. When using AC' to find
AC-triviality of m-generator presentations, enhance the notion of terminal states in reinforcement learning and goal states in classical search to include all presentations with = m. When m = 2, there eight such states:
(01,002 29 2/) | a,2;a, =1;1 (1;i1)
G A topological hardness measure for AC-trivialization problem
In Section we studied hardness of presentations solved by our algorithms with respect to intrinsic as well as path- aath- measures. Here, we study global hardness measure for the AC trivialization problem.
G.1 Definition
natural approach define global hardness measure for the AC graph is by aggregating the E-increase values across all presentations. However, this method suffers from overcounting: certain paths have an é-increase of O, meaning that trivializing one endpoint automatically trivializes the other, incurring no additional cost.
We consider instead the following approach. Let I' be the induced subgraph containing all presenta- tions with length at most k. Let us compare the components of T3 and Tx+1
Consider node of length 1: - 1. If u cannot be joined to component of T in I then v belongs to new component that said to be born at k + 1. u can be joined a component of TE, then its hardness needs not be considered since the path is of ê-increase O and trivializing any presentation in the component with smaller length is more costly. If e connects two distinct components, say born at k; < f2, then the component born at h2 is said die at À + 1. By similar reasoning, this component contributes (A + 1) k2 to the overall hardness of the problem, the difference between its death and birth values. If a component does not die, we set its death value to
We propose that the multiset consisting of all such pairs (birth, death) serves a principled hardness measure for the AC trivialization problem and any other nath-to-the-base search problem on graph equipped with weights on its nodes. For any such problem, this multiset coincides with a key invariant
'Recall that the components of a graph refer to the equivalence classes of its nodes under the relation that identifies two if there is path between them.
32

---

Table 5: Global hardness approximation for the AC- and AC' AC'-trivializztion problems. For each approximation depth L, h; represents the number of pairs (b, d) in the hardness multiset satisfying
b
AC moves
L
Nodes
Edges
h1
h2
h3
11
350,356
1,002,439
4
791,140 12
2,251,375
16
0
0
3,238,052 13
9,321,629
72
14
7,199,908
20,573,343
144
4
0
15
29,243,812
84,391,763
508
52
8
16
64,623,652
185,162,236
1034
88
20
AC' moves
L
Nodes
Edges
h1
h2
h3
350,356 11
655,928
19
791,140 12
1,467,080
67
0
0
3,238,052 13
6,107,112
243
16
14
7,199,908
13.414,744
483
16
0
15
29,243,812
55,306,744
1819
136
32
16
64,623,652
120,824,232
3923
208
80
from topological data analysis: the barcode the persistent reduced homology degree 0 of the associated filtered based graph 6
G.2 Analysis
Let us now approximate the global ê-increase hardness of the AC-trivialization problem. We will consider both sets of moves: AC and AC'.
We first need to specify a finite approximation to the problem. For L E {1l, , 16). we take the induced subgraph containing all nodes admitting trivialization of max length most L. The upper bound was imposed by our computational resources, whereas the lower bound was chosen to highlight non-trivial behavior.
For each such approximation we compute its hardness multiset (as defined in Appendix G. using giotto-TDA (Tauzin et al. 2021 We then count the number h; of pairs (b, d) with d b The results of our analysis for AC graph and AC' graph are given in Table
Taking the quotient of the values of both tables, we observe that, expected, the number of nodes remains unchanged. Perhaps unsurprisingly, the number of edges scales consistently by approximately 1.5. More unexpectedly, other columns. This suggests that the overall complexity of the problem is preserved under the reformulation, albeit consistently scaled.
find that the scaling factor remains fairly constant across
In the future, we aim to gather more data from other path-to- math-to-the-bart search problems, such as those defined on the Reidemeister graph of knot presentations, and compare their hardness multisets systematically, using the bottleneck distance and other techniques from TDA.
In Appendix G.3
we investigate the extent to which similar topological invariants, computed on filtered graph neighboring presentation in D, can predict its PPO-solved/unsolved label.
"We refer any textbook the subject for these concept, for example, Chapter 5 of'Carlson & Vejdemo Johansson (2022).
"Specifically, its binding of the SimplexTree data structure introduced in Boissonnat & Maria 2014 and
implemented in GUDHI (Maria al. 2014).
33

---

Table Quotient between corresponding values in the AC and AC' tables in Table
L
Nodes
Edges
h1
h2
hs
11
1,5283
0.2105
12
1
1,5346
0.2388
13
1
1.5264
0.2963
0.2500
14
1
1,5336
0.2981
0.2500
15
1,5259
0.2793
0.3824
0.25
16
1
1.5325
0.2636
0.4231
0.25
Pesture Incerbance
Barodd
kr
Figure 1I: Feature importance measured by SHAP values for each feature, caleulated in general setting, for the test set.
G.3 Predicting hardness from local and topological features
We trained an XGBoost classifier on the data set 'D (Appendix B predict the label PPO-(unJsolved, obtained by an RI. agent. The data set consists of 417 PPO-solved and 773 PPO-unsolved presenta- tions. The data set was randomly split into training and test subsets in 4:1 ratio.
We use barcodes (defined the end of Appendix G.2 as the numbers h4 in the form of vector) as the main source of local, topological features. The barcodes were calculated for the graph of 5-step neighborhood, which is the set of presentations achievable using five or fewer AC-moves. The considered features include the number of vertices, the number of edges, the barcode vector, the maximal length of a bar, the sum of the barcode vector entries, persistence entropy, and basic features of the presentation, such as the lengths of each relator and the total length of the presentation.
We compared F1 scores the test subset for classifiers trained with different feature subsets. Here is a brief summary. The length of the presentations, represented as three numbers (the lengths of each relator separately and their sum), achieved an Fl score of 0.885. The singular feature, the size of the neighborhood, achieved an Fl score of 0.930. Using the barcode vector as a single feature resulted in an Fl score of 0.943. An exhaustive search over all feature subsets enabled the selection of the optimal set of features based on the Fl score of the corresponding classifier. The selected subset includes the size of the neighborhood, its barcode vector, and the sum of the barcode entries. This classifier achieves an Fl score of 0.962.
We used the tree explainer technique and SHAP values analyze the importance of each of considered features when building a modeled with all of them (number of vertices, number of edges, barcode vector, maximal length of bar, sum of the barcode vector entries, persistence entropy, length of each relator, and length of the presentation). The lower entries of the barcode vector stood out as the most influential. Aggregated SHAP values are presented in the Figure [I The feature 'barcode' inluces full barcode vector and the feature 'lengths' includes accumulated values of three features: length of each relator and length of the presentation.
34


Reviews:
[{"review_id": "fArghnvJBi", "reviewer": "Reviewer_wqtT", "summary": "The paper presents a reinforcement learning program to find solutions and counterexamples to several long-standing conjectures from combinatorial group theory. The paper goes into detail about the Andrews–Curtis trivialization problem (conjecture), framing it as a reinforcement learning task. The corresponding environment is characterized by long horizons, sparse rewards, and also an intrinsic distribution of ``problem hardness'', which is native to the framing of the conjecture. For a large class of examples, through intrinsic and path-based measures, the distribution of problem hardness is characterized and finally various RL agents are deployed on problems of varying hardness and the resulting observations are used to improve these agents to dynamically adapt to problem difficulty.\n\n### Problem description\nA group presentation, $\\pi = \\langle x\\_1, x\\_2, \\dots, x\\_n \\mid r\\_1, r\\_2, \\dots, r\\_m \\rangle$, consists of a set of generators $\\\\{ x\\_i \\\\}\\_{i=1}^n$ and a set of relators $\\\\{r\\_j\\\\}\\_{j=1}^m$, where each relator $r_j$ is a word in the alphabet $\\\\{x\\_i^{\\pm1} \\\\}\\_{i=1}^n$. Consider the set of balanced presentations where $n = m$. The length of a presentation is the sum of the word lengths, $\\sum\\_i |r_i|$.\n\n**AC conjecture.**\nEvery balanced presentation of the trivial group is *AC‐equivalent* to the trivial presentation, $\\langle x\\_1, \\dots, x\\_m \\mid x\\_1, \\dots, x\\_m \\rangle$. That is, starting from any balanced presentation of the trivial group, one can obtain the trivial presentation by a finite sequence of the following *AC‐moves*:\n- $r\\_i \\;\\mapsto\\; r\\_i\\,r\\_j$, for $i\\neq j$ (Nielsen–type move),\n- $r\\_i \\;\\mapsto\\; r\\_i^{-1}$,\n- $r\\_i \\;\\mapsto\\; x\\_j^{\\pm1} r\\_i x\\_j^{\\mp1}$.\n\nThe paper focuses on the case $m=2$.\n\nWith this presentation, ``checking'' whether a balanced presentation is AC-equivalent to the trivial presentation is by itself not an easy problem. This involves checking through all possible sequences of AC-moves as to whether the two presentations may be equivalent. This search problem can be formulated as checking whether two nodes are connected on a combinatorially large graph where two nodes are connected if they are equivalent up to a single AC move.\n\nProblem difficulty is nicely captured by the length of the final path that connects a balanced presentation to the trivial presentation. Another measure of difficulty is the length of the longest presentation along the path that connects the candidate presentation to the trivial presentation.\n\nThe PPO agent trained by the paper aim to solve the connectivity problem and are trained on a dataset of ~1200 datapoints, with an accuracy of approximately 40%. However, since the RL environment is verifiable, i.e., a candidate path can be checked for whether it is correct or not, presumably this accuracy can be improved by considering even larger datasets.\n\nThe authors also present some cool theoretical results which are apparently guided by the empirical observations made in the experiments. However, the connection between these two was a little less clear to me.", "questions": "N/A", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The paper presents a very interesting use of RL for solving search problems on graphs in the context of the AC conjecture. The paper uses relatively simple algorithm (A2C / PPO) on relatively small sized datasets and already shows promising performance.\n\nI think the writing of the paper can be improved a little bit. It isn't clear until the results section of the paper, which appears much later than I would have liked, the actual contributions of the paper. Some details are spelled out in the introduction, but not nearly enough to get a sense of what is going on until the results section. I like the description of the main results on page 12 of the appendix - the two theorems stated here need to be made just as clear in the main paper, and the implications of these results to those not familiar with the AC conjecture need to be spelled out more clearly. I would invest more effort into stating the problem very clearly once the AC conjecture and other abstractions are spelled out - that of certifying whether plausible counterexamples to the AC conjecture are indeed counterexamples, or whether they are trivializable. These are small things which may not need to be stated explicitly for someone familiar with the problem, but would really help someone from the broader audience understand the paper.\n\nFrom a technical point of view, I think the paper is quite nice. I have three constructive criticisms:\n\n1. I did not exactly understand how the empirical results in the paper laid the foundations for the theorems in the paper to be proved. It would be helpful to spell this out for the sake of bridging the two ``halves'' of the paper in a better fashion.\n\n2. I really think the results in the paper would be supremely interesting if scaled up further. Perhaps there are computational bottlenecks that I don't understand as clearly, but running PPO / A2C on a 1e3 sized dataset of horizon length 200 seems like a fairly small setup. It should be clarified to a reader, or to someone intending to build upon these results what is the bottleneck in the current approaches: is it that it is hard to construct more synthetic examples, or is it an issue with scaling RL, or is it compute?\n\n3. Furthermore, I did not fully understand why an *actual* search algorithm like MCTS or A* was not a part of the family of algorithms being trialed. These algorithms are really good at solving such search problems (as evidenced by a number of examples in the literature) and also they have the intrinsic ability of being scalable with more access to compute at test-time (i.e., just run longer depth searches).\n\nI like the problem that was tackled in this paper, I think there are some suggestions above the authors can work on / clarifications to be made in the rebuttal that I would be open to hearing and revising my score on the basis of.", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer,\n\nThank you for your thoughtful and constructive review. We appreciate the time you took to engage with our work and are pleased you liked the problem and overall direction of the paper. Moreover, you raise some excellent concerns, fixes for which we would be happy to edit into the final camera-ready version.\n\n\n1. First, we would be happy to add the following new paragraph at the end of Section 3.1 to clarify the problem statement for a broader audience as you suggested.\n\n*The conjecture has been open for several decades. Many potential counterexamples of the conjecture have been proposed in the literature, often in the form of infinite families of presentations of the trivial group. In order to study whether a presentation is consistent with the conjecture, one aims to find its trivialization. Previous studies have used breadth-first search and genetic algorithms to find trivializations for some presentations, while the status of many presentations still remains open. In this work, we explore the question of finding trivializations for these open cases --- the so-called potential counterexamples, using reinforcement learning techniques.*\n\n\n2. Next, we turn our attention to your following comment. \n\n*I did not exactly understand how the empirical results in the paper laid the foundations for the theorems in the paper to be proved. It would be helpful to spell this out for the sake of bridging the two `halves' of the paper in a better fashion.*\n\nWe have edited Section 5.3 and Appendix A to convey this connection better. Indeed, the empirical results in the paper were crucial to the discovery of theorems in the more mathematical part of the paper. When our agents discovered any paths for specific presentations of Miller--Schupp or Akbulut-Kirby series, we first re-analyzed their solution paths of elementary AC-moves, in terms of substitution moves. Then we identified any patterns and generalized them to find new results for infinite families. \n\nApplying this procedure to our agents' solution paths for $MS(1,w)$ with $\\text{length}(w) \\leq 7$ led to the general result of Theorem 5.1. Similarly, analyzing the path connecting $\\text{AK}(5)$ to a length-16 presentation led to length reduction of $\\text{AK}(n)$ for all $n \\geq 5$.\n\nWe have added the following paragraph to Section 5.3.\n\n*The mathematical contributions of our agents fall into two categories. First, the agents discovered explicit paths that trivialized hundreds of previously-open presentations in the Miller--Schupp series. Second, we analyzed some paths of AC moves in terms of substitution moves (defined in Appendix A.1) to discover new patterns, which we then generalized to find results for infinite families. We emphasize that these results would not have been possible without the empirical results reported in this work. Here, we present a summary of our results, with a more detailed example of this process given in Appendix A.*\n\nIn Appendix A, we have added a more detailed example of our workflow showing how it was used to obtain the result regarding length reduction of $AK(n)$. We have also included how the intermediate step of interpreting our agents' paths in terms of substitution moves is crucial as identifying patterns in the raw sequences of AC paths discovered by the agent is certainly more difficult. Hence, our appendix reflects a good example of how AI agents and human mathematicians can work together towards the goal of scientific discovery.\n\n\n3. Now we discuss the issue related to scaling data, horizon length, and compute. We turn our attention first to the issue of dataset size.\n\n- The natural approach to creating a large dataset would be to sample random balanced presentations $\\langle x_1, x_2 \\mid r_1, r_2 \\rangle$ and check if the given presentation is a presentation of the trivial group. There are two obstacles in following approach. First, as the length of the presentation increases, the percentage of presentations that present the trivial group drops substantially. The second and more problematic issue is that, given a random presentation, it is in general not possible to determine if it is a presentation of the trivial group. (Practically, this means that while there are algorithms to determine this, they are inefficient and do not terminate on some inputs.) \n\n- Another natural approach would have been to include more examples from the Miller--Schupp with larger $n$ and $w$. Amongst Miller--Schupp presentations, we notice a trend in Figure 2b. All algorithms start to struggle as the value of n is increased from 1 to 7. (A similar pattern also exists as a function of length($w$). The current manuscript does not have this plot, but we will be happy to include it, if needed.) We have noted in our experiments that this trend continues as the values of $n$ and $\\text{length}(w)$ are increased further. Hence most of the presentations of Miller--Schupp series with larger values of n and $\\text{length}(w)$ will require extremely long paths and so, given our agent was already struggling with easier presentations, adding more difficult presentations seemed unlikely to help.\n\n- A third natural strategy to increase the dataset size could be to start from a presentation of the trivial group, and apply a random sequences of AC moves to obtain a large dataset of presentations. In our observation, this technique ends up mostly producing uninteresting presentations. They are either identical to the initial representation except that the relations have been rotated and/or inverted or extremely long with an easy-to-discover path back to the starting presentation. We also expect that these presentations will be encountered by an RL agent in its rollouts in any case, and hence, adding them provides no significant advantages.\n\n- We also remark that in the case of Andrews--Curtis environment, the hardest cases are millions of times harder than generic cases, as shown by Bridson and Lishak in the case of 3 and higher number of generators. We have recently made progress in creating a 2-generator analogue of their families of presentations. This could serve as an excellent benchmark for the development of novel reinforcement learning algorithms in the future. In the current paper, however, we avoided training datasets of easy presentations, (such as those that are close to the goal state), as gaining high levels of performance on such a dataset could be misleading.  \n\nWe appreciate your feedback that we should communicate the issues around dataset creation in the paper. We will be happy to include a paragraph in the Limitations section, with more detailed accounting in an appendix. \n\nWe now turn our attention to the issue of small value of horizon length. We experimented with a wide range of horizon length values, observing the following scaling trend: at a fixed level of performance in terms of the number of presentations solved, the number of environment interactions required to train an agent scales linearly with horizon length. The slope of the trend is positive and depends on the level of performance. This indicates that as we increase the horizon length, we need larger amounts of compute time to solve the same number of presentations. As we are a small academic lab, we circumvented the requirements of larger compute for training at longer horizon length by varying the horizon length during training. As reported in the paper, this modification helped us find some new trivializations. \n\nFinally, we trained models of different sizes for varying amounts of number of environment interactions. The largest model whose result is reported in Section 5.2 is a six layer residual network actor-critic agent, trained for 1 billion environment interactions. If recommended, we will be able to train much larger models for much longer amounts of time. However, we suspect that the main limitations in the agents' performance comes from the current algorithms' struggles with sparse-rewards, long-horizon environments. For these reasons, we turned our focus to developing new algorithms involving supermoves and dynamic action spaces, which we describe in Section 7.\n\nWe understand that we did not discuss these issues satisfactorily in the submitted draft. As the camera-ready version allows for one more page, we will be able to incorporate your feedback quite comfortably in the paper.\n\n\n4. Regarding the testing of other search algorithms, we did some experimentation involving other algorithms but found them universally less successful than greedy search.\n\nLooking at $A^*$ search as a specific example, this is essentially a half-way option between breadth first and greedy search, where the priority queue is sorted by the sum of the path length $p$ and presentation length $l$. We tried a search algorithm that sorted the priority queue using $r * p + l$ for a variety of choices of $r \\geq 0$ and tested how many MS presentations the search algorithm solved. What we found was that, in all cases, decreasing $r$ improved the number of presentations solved and so we ended up just setting $r = 0$ at which point we end up back with greedy search.\n\nAs for MCTS, we observed that MCTS spends a meaningful amount of time exploring different paths which do not lead to a trivialization solution. In contrast, the length heuristic function of greedy search helps find AC trivializations much faster, and with a much smaller usage of system memory.\n\nWe will be happy to incorporate comments on these findings in the camera-ready version of the draft, providing more clarity for the preference of breadth-first search (which finds the shortest paths) and greedy search (which solves the most presentations) in our plots showing comparison with reinforcement learning techniques."}, {"review_id": "sHm4hahg9v", "reviewer": "Reviewer_nQDy", "summary": "This paper studies using RL for resolving or disproving math conjectures (e.g., by finding counterexamples). In particular they study the Andrews-Curtis conjecture from group theory. They focus on the case with 2 variables and length 1,..,7. They show that specific RL approaches can confirm some instances of the conjecture, which were known to be true, in roughly 200 out of 1000 cases.\n\nBased on their first empirical results they propose some ideas/directions for future work.", "questions": ".", "limitations": "Limitations are addressed but see points above.", "rating": 3, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 1, "clarity": 2, "significance": 1, "originality": 2, "strengths_and_weaknesses": "The studied problem is important and in the long run RL methods could become an important tool for resolving math conjectures. The tackled conjecture seems to yield an interesting benchmark to track progress on the usefulness of RL for proving/disproving conjcetures. However this study has various limitations\n\nWeaknesses:\n* Limited scope. The conjecture is tested only for two variables and length up to 7. Previous work already confirmed the conjecture for length up to 13. Even in this limited scenario the proposed approaches can only confirm roughly 20% of the instances.\n* Besides the experimental results the paper is rather hypothetical and conceptual (as the authors themselves admit in the limitations). It is unclear if these proposals will actually lead to further improvements.", "was_revised": true, "final_justification": "The authors clarified the setup and contributions. This makes indeed the paper more interesting and stronger, and I slightly raised my score. However the contributions were not communicated well in the original submission. Also I cannot judge added experiments concerning additional techniques, which were only discussed during the rebuttal. I recommend to fully rewrite the paper and then submit it to the next conference.", "rebuttal": "Dear reviewer,\n\nWe appreciate the time you took to engage with our work and for highlighting both its strengths and areas for improvement. Below, we respond to your comments and clarify the points you raised.\n\n1. We note in your summary the following statement: \n\n*They focus on the case with 2 variables and length $1,\\dots,7$. Previous work already confirmed the conjecture for length up to 13.* \n\nThis likely arises from a miscommunication regarding the role of the parameter $n$ in Miller--Schupp presentations. Specifically, $n$ is not the length of a presentation but rather appears in the exponent of a relator. Our dataset---up to certain trivial identifications described in Appendix~D---contains all presentations of the form\n\n$$MS(n, w) = \\langle x, y \\mid x^{-1} y^n x = y^{n+1},\\ x = w \\rangle,$$\n\nwith $n \\leq 7$ and $\\mathrm{length}(w) \\leq 7$. The length of the presentation $MS(n, w)$ is $2n + 4 + \\mathrm{length}(w)$, which is greater than $12$ for 92% of the presentations in the dataset. The distribution of lengths is shown in Figure 7 in the appendix. \n\nThat a large number of presentations have lengths greater than $12$ is quite meaningful to us. As you commented, the conjecture is known to hold true for all presentations with length less than or equal to $12$. We wanted our dataset to be in the regime where it largely consists of previously-open problems in the field, and finding a trivialization for any of these presentations would be recognized as a valuable mathematical result. Here, we have managed to do so using classical search and reinforcement learning techniques.\n\nTo preempt this potential misunderstanding, we have included the following clarifying sentences to Section 4.1:\n\n*This dataset contains Miller–Schupp presentations, $MS(n, w)$, with  $n \\leq 7$ and $\\text{length}(w) \\leq 7$, and includes a total of 1190 presentations. The lengths of these presentations lie in the range $[7, 25]$ and, for the vast majority of them, their AC-triviality was previously unknown.*\n\nWe also note that while we only discuss the case of $m=2$ generators in the paper, this was mainly to keep the paper as focused as possible. In our experiments, we also studied a family of presentations with $m=3$, which is of interest in mathematics. Here, we also solved presentations that are previously open. If you suggest, we will be able to include these results in an appendix in the camera-ready version of the paper. Below, we have written a small rough draft of this new addition.\n\n\n**Balanced presentations with 3 generators**\n\nIn addition to the well-known Akbulut–Kirby and Miller–Schupp families in the case of two-generators, we also explored the question of AC-triviality for a 3-parameter family of presentations.\n\n$$P \\left( 2k+1, 2; \\frac{2n}{2nm+1} \\right) = \\left\\langle x, y \\mid x^{2k+1} = y^2, y x^{-k} \\left( (y x^{-k})^n (y^{-1} x^k)^n \\right)^m \\right\\rangle$$\n\nThis family has a geometric origin, with the presentations being trivial implied by the corresponding R-links having Generalized Property R \\cite{Gompf, Robert E. and Scharlemann, Martin and Thompson, Abigail}. \nOur reinforcement learning agents trivialized the following presentation, which was previously a potential counterexample to Andrews--Curtis conjecture.\n\n$$P (5,2; \\tfrac{4}{5} ) = \\langle x,y \\mid x^5 = y^2, y x^{-2} (y x^{-2})^2 (y^{-1} x^2)^2 \\rangle$$\n\nThe discovered AC path is of length $49$:\n\n$$ h_{11} \\cdot h_{11} \\cdot h_{1} \\cdot h_{11} \\cdot h_{11} \\cdot h_{11} \\cdot h_{6} \\cdot h_{8} \\cdot h_{8} \\cdot h_{6} \\cdot $$ \n$$ h_{0} \\cdot h_{8} \\cdot h_{8} \\cdot h_{9} \\cdot h_{11} \\cdot h_{1} \\cdot h_{9} \\cdot h_{11} $$\n$$ h_{5} \\cdot h_{7} \\cdot h_{1} \\cdot h_{9} \\cdot h_{11} \\cdot h_{8} \\cdot h_{3} \\cdot h_{5} \\cdot h_{4} \\cdot h_{4} \\cdot h_{2} $$\n$$\\cdot h_{8} \\cdot h_{10} \\cdot h_{4} \\cdot h_{9} \\cdot h_{0} \\cdot h_{5} \\cdot h_{4} $$\n$$ h_{4} \\cdot h_{1} \\cdot h_{9} \\cdot h_{10} \\cdot h_{4} \\cdot h_{3} \\cdot h_{7} \\cdot h_{5} \\cdot h_{2} \\cdot h_{2} \\cdot h_{1} \\cdot h_{5} \\cdot h_{1} $$\n \nThe sequence should be read from left to right, e.g. we first apply $h_{11}$ twice, then $h_{1}$, and so on. $h_i$ are AC$'$-moves defined as follows.\n\n$$ h_1 = \\ r_2 \\rightarrow r_2 r_1,  \\quad h_5 = \\ r_2 \\rightarrow x^{-1} r_2 x, \\quad h_9 = \\ r_2 \\rightarrow x r_2 x^{-1}, $$\n$$h_2 = \\ r_1 \\rightarrow r_1 r_2^{-1},  \\quad h_6 = \\ r_1 \\rightarrow y^{-1} r_1 y,  \\quad h_{10} = \\ r_1 \\rightarrow y r_1 y^{-1}, $$\n$$ h_3 = \\ r_2 \\rightarrow r_2 r_1^{-1},  \\quad h_7 = \\ r_2 \\rightarrow y^{-1} r_2 y,  \\quad h_{11} = \\ r_2 \\rightarrow y r_2 y^{-1}, $$\n$$h_4 = \\ r_1 \\rightarrow r_1 r_2,  \\quad h_8 = \\ r_1 \\rightarrow x r_1 x^{-1},  \\quad h_{12} = \\ r_1 \\rightarrow x^{-1} r_1 x, $$\n\n2. We now turn our attention to the following statement. \n\n*Even in this limited scenario the proposed approaches can only confirm roughly 20\\% of the instances.*\n\nAs we described above, most of the presentations in our benchmark dataset are of length greater than 12, and were previously unknown to be solvable. Thus, we are already in the regime of solving *long-standing open research-level* problems in mathematics. From our dataset of 1190 presentations, we solved approximately 600, which is close to 50%. In addition, we used our empirical results to solved certain *infinite* subfamilies as described in Section 5.3 and Appendix A. \n\n3. The second weakness listed is the following:\n\n*Besides the experimental results the paper is rather hypothetical and conceptual (as the authors themselves admit in the limitations). It is unclear if these proposals will actually lead to further improvements.*\n\nWe understand that this comment is in regards to the contents of Section 7. During the rebuttal period, we have performed new experiments with super-moves and dynamic action spaces, which show improvement over the baseline results reported in the manuscript. \n\nOur setup of dynamic action spaces looks as follows. We note that in many sequences of AC paths, a common strategy that the agent employs is to select several conjugation moves (AC$'$2) in a row followed by a single concatenation move (AC$'$1). We increased the size of the action space to include actions that perform conjugations by arbitrary words of generators and their inverses, followed by a single concatenation. This significantly enhances the size of the action space from the original $12$ to several thousands. In the beginning, however, we keep all of these new actions masked, letting the agent play the game with the original AC moves. \n\nAs the agent solves any new presentation, we scan through the path it found, look for the sub-sequences of moves of the type described above and unmask only the actions corresponding to these sub-sequences. We repeat this process after every 100 rollout phases of the PPO training loop. With this approach, the agent solves $13$ new presentations from the Miller--Schupp dataset that were previously unsolved by greedy search and our reinforcement learning agents with static action spaces. \n\nThese results provide empirical evidence on the usefulness of dynamic action spaces and supermoves. We commit to adding these results to Section 7 of the camera-ready version of the paper, along with providing paths for the $13$ newly solved presentations. We will also include the JAX code used for these experiments along with our submission."}, {"review_id": "5roLQozVtP", "reviewer": "Reviewer_eKhC", "summary": "This paper studies why reinforcement learning (RL) struggles with solving certain mathematical problems by analyzing the Andrews–Curtis (AC) conjecture—a long-standing problem in group theory. The authors frame the AC trivialization task as a long-horizon, sparse-reward RL environment with an intrinsic distribution of problem hardness. They analyze how RL agents like PPO perform compared to classical algorithms, and identify limitations in greedy approaches. Notably, their methods solve previously open instances in the Miller–Schupp and Akbulut–Kirby series, proving new infinite families are AC-trivial. Based on these insights, they propose novel RL techniques using supermoves and adaptive action spaces to better tackle hard problem instances.", "questions": "1. In Theorem A.2, you proved that $\\text{MS}(1, w)$ is AC-trivial for all $w$ by applying substitution and conjugation identities derived from the relators. Can you formalize the conditions under which these substitution steps are guaranteed to terminate for arbitrary $w$, especially given that $w$ only needs to have zero exponent sum in $x$? Is there a provable upper bound on the number of AC-moves required?\n\n2. Theorem A.4 showed that for all $n \\geq 2$, $\\text{AK}(n)$ is AC-equivalent to a length-$n + 11$ presentation \n  $\\langle x, y \\mid x^{-1}yx = xyx^{-1}y,\\ x y^{n-1} x = y x y \\rangle$. Can you clarify whether this equivalence is minimal in the number of AC-moves required, or just in presentation length? Additionally, is this reduction provably optimal in terms of minimal length among all AC-equivalent presentations?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- Frames the Andrews–Curtis trivialization problem as a long-horizon, sparse-reward RL task and evaluates PPO vs A2C with controlled variations in reward and horizon schedules.\n- Classical baselines (BFS, greedy search) are implemented fairly, enabling a rigorous comparison showing RL solves harder, non-monotonic paths.\n- RL-guided exploration leads to new mathematical results, including full AC-triviality proofs for $\\text{MS}(1, w)$, $\\text{MS}(n, y^{-1} x y x^{-1})$, and length reduction in $\\text{AK}(n)$.\n\nWeaknesses\n- Only on-policy methods (PPO, A2C) are tested; no search-guided or off-policy RL approaches are explored.\n- Supermoves and adaptive action spaces are proposed but not empirically validated.\n- Problem scale is limited to short presentations ($n \\leq 7$), leaving generalization to harder instances uncertain.", "was_revised": true, "final_justification": "The authors’ openness to refining their work in response to reviewer feedback, coupled with the new experiments they conducted and shared during the rebuttal, leads me to believe this paper merits an opportunity for acceptance, and I am inclined to place trust in their ability to deliver a strong final version.", "rebuttal": "Dear reviewer,\n\nThank you for your thoughtful and constructive review. We appreciate the time you took to engage with our work and think you raised some interesting questions and concerns regarding potential areas of improvement of our paper.\n\n1. We begin by clarifying a potential misunderstanding, and which we have now taken care of to prevent in the revised manuscript. In the weaknesses section, you write:\n\n*Problem scale is limited to short presentations ($n \\leq 7$), leaving generalization to harder instances uncertain.*\n\nThis likely arises from a miscommunication regarding the role of the parameter $n$ in Miller--Schupp presentations. Specifically, $n$ is not the length of a presentation but rather appears in the exponent of a relator. Our dataset---up to certain trivial identifications described in Appendix~D---contains all presentations of the form\n    \n$$MS(n, w) = \\langle x, y \\mid x^{-1} y^n x = y^{n+1},\\ x = w \\rangle, $$\n\nwith $n \\leq 7$ and $\\mathrm{length}(w) \\leq 7$. The length of the presentation $MS(n, w)$ is $2n + 4 + \\mathrm{length}(w)$, which is greater than $12$ for 92% of the presentations in the dataset. The distribution of lengths is shown in Figure 7 in the appendix. \n\nThe importance of having a large number of presentations with lengths greater than $12$ is that the conjecture is known to hold true for any presentation with length less than or equal to $12$. In this paper, we wanted our dataset to be in the regime where we use reinforcement learning to find new results in mathematics. For most of these presentations, a trivialization found by purely mathematical techniques would be recognized as a valuable mathematical result. Here, we have managed to do so using classical search and reinforcement learning techniques.\n\nTo preempt this potential misunderstanding, we have included the following clarifying sentences to Section 4.1:\n\n*This dataset contains Miller–Schupp presentations, $MS(n, w)$, with  $n \\leq 7$ and $\\text{length}(w) \\leq 7$, and includes a total of 1190 presentations. The lengths of these presentations lie in the range $[7, 25]$ and, for the vast majority of them, their AC-triviality was previously unknown.*\n\n\nWe observe in Figure 2(a) that as the length of presentation increases, the efficacy of classical search as well as reinforcement learning algorithms declines significantly. We experimented with presentations of even longer lengths and observed that this trend continues, which indicates the inherent difficulty of solving such presentations. If you suggest, we will be happy to include more presentations in the camera-ready version of the paper, significantly expanding the values of $n$ and $\\mathrm{length}(w)$. \n\n2. We now turn our attention to the following remark.\n\n*Only on-policy methods (PPO, A2C) are tested; no search-guided or off-policy RL approaches are explored.*\n\nWe appreciate your feedback. Indeed, in the manuscript, we only discuss on-policy methods, which is an oversight on our part. We have experimented with an off-policy RL algorithm (DQN with soft target network updates) and a search-guided method (AlphaZero) during the rebuttal period.\n\nWe observed that a well-tuned DQN under-performs compared to PPO, solving only 150 presentations from our dataset, when trained for 100 million environment interactions. In contrast, the best PPO agents solved 300+ presentations for the same amount of training period, as shown in Figure 1(a) of the paper.\n\nAlphaZero performs search-based reinforcement learning, and hence, training it for 100 million environment interactions does not provide a fair comparison to PPO. For the purpose of comparing it with PPO, we trained for equal amount of wall-clock time, i.e. 24 hours. We observed that the performance of a well-tuned AlphaZero agent is comparable to PPO, and hence, it can serve as a good alternative for further experimentation and scaling of the model.\n\nWe have edited Sections 4 and 5 in the manuscript to include the comparison of these algorithms with policy-gradient algorithms. We will also include the code used to run these experiments along with the camera-ready version of the paper.\n\n3. We will now address your feedback regarding the contents of Section 7.\n\n*Supermoves and adaptive action spaces are proposed but not empirically validated.*\n\nDuring the rebuttal period, we have performed new experiments with super-moves and dynamic action spaces, which show improvement over the baseline results reported in the manuscript. \n\nOur setup of dynamic action spaces looks as follows. We note that in many sequences of AC paths, a common strategy that the agent employs is to select several conjugation moves (AC'2) in a row followed by a single concatenation move (AC'1). We increased the size of the action space to include actions that perform conjugations by arbitrary words of generators and their inverses, followed by a single concatenation. This significantly enhances the size of the action space from the original $12$ to several thousands. In the beginning, however, we keep all of these new actions masked, letting the agent play the game with the original AC moves. \n\nAs the agent solves any new presentation, we scan through the path it found, look for the sub-sequences of moves of the type described above and unmask only the actions corresponding to these sub-sequences. We repeat this process after every 100 rollout phases of the PPO training loop. With this approach, the agent solves $13$ new presentations from the Miller--Schupp dataset that were previously unsolved by greedy search and our reinforcement learning agents with static action spaces. \n\nThese results shine a new light on the usefulness of dynamic action spaces and supermoves. We commit to adding these results to Section 7 of the camera-ready version of the paper, along with providing paths for the $13$ newly solved presentations. We will also include the JAX code used for these experiments along with our submission. \n\n4. We now turn our attention to your questions.\n\n- *In Theorem A.2, you proved that ${MS}(1, w)$ is AC-trivial for all $w$ by applying substitution and conjugation identities derived from the relators. Can you formalize the conditions under which these substitution steps are guaranteed to terminate for arbitrary $w$, especially given that $w$ only needs to have zero exponent sum in $x$? Is there a provable upper bound on the number of AC-moves required?*\n\nThese substitution steps are guaranteed to terminate for arbitrary $w$. Indeed, for each $x$, the proof moves it past each $y$ and $y^{-1}$ that appear to the left of it, and for each $x^{-1}$, the proof moves it past each $y$ and $y^{-1}$ that appear to the right of it. Then we conjugate by $x^{-1}$, each time canceling an $x$ and $x^{-1}$ pair. As there are finitely many $x^{\\pm 1}$ and $y^{\\pm 1}$ appearances, this will always terminate. \n    \nA rough upper bound on the number of AC-moves required in the substitution algorithm described is $|w|2^{|w|}$ where $|w|$ is the length of $w$. To see this, we note that the first $x^{\\pm 1}$ requires at most $|w|$ moves to get it to the correct position. Whenever it passes a $y^{\\pm 1}$, we replace that by $y^{\\pm 2}$ and so the second $x^{\\pm 1}$ requires at most $2|w|$ moves to get it to the right position. Continuing on, the $i^\\text{th}$ $x^{\\pm 1}$ moved requires at most $2^{i - 1}|w|$ moves and so, as the number of $x^{\\pm 1}$s is at most $|w|$, the number of moves required is less than $(1 + 2 + \\cdots + 2^{|w| - 1})|w| < |w|2^{|w|}$. In practice the true upper bound is much smaller than this but this suffices for showing that an upper bound exists.\n\n- *Theorem A.4 showed that for all $n \\geq 2$, ${AK}(n)$ is AC-equivalent to a length $n + 11$ presentation $\\langle x, y \\mid x^{-1}yx = xyx^{-1}y,\\ x y^{n-1} x = y x y \\rangle$. Can you clarify whether this equivalence is minimal in the number of AC-moves required, or just in presentation length? Additionally, is this reduction provably optimal in terms of minimal length among all AC-equivalent presentations?*\n\nThe equivalence of $\\text{AK}(n)$, which is of length $2n+7$, with the length $n+11$ presentation $\\langle x, y \\mid x^{-1}yx = xyx^{-1}y,\\ x y^{n-1} x = y x y \\rangle$, is the shortest presentation currently known to be AC-equivalent to $\\text{AK}(n)$. In other words, this is the ``current best,\" and moreover is the first example of any length reduction for $n \\geq 3$.\n\nIt is possible that there exist even shorter presentations that are AC-equivalent to $\\text{AK}(n)$ (if the AC conjecture is true, they are AC-equivalent to presentations of length 2). However, we would like to take this opportunity to emphasize the importance of our result: $\\text{AK}(n)$ were introduced as potential counterexamples of AC conjecture more than 4 decades ago. A lot of research had been done on these presentations, and it was unknown before our paper whether they admit length reduction at all. Our results create a new opening towards finding solutions for these presentations by showing that a significant reduction in length is possible.\n\nWe did not investigate whether the AC-equivalence we find is minimal in terms of the number of AC-moves required, and we do not expect them to be. We are primarily interested in the existence of any AC-triviality paths as opposed to finding the most optimal ones, especially in the cases of long-standing potential counterexamples of the Akbulut--Kirby series."}, {"review_id": "txYaHJoLKM", "reviewer": "Reviewer_Lzhs", "summary": "\"What makes math problems hard for reinforcement learning: a case study\" is an interesting paper that provide a case study of using RL (mostly A2C and PPO agents) to address math problems. The exploration of the Andrews-Curtis conjecture as a reinforcement learning (RL) environment, combined with your mathematical contributions—such as resolving potential counterexamples in the Miller-Schupp series and demonstrating length reducibility in the Akhlutr-Kirby series—is intellectually compelling. The interdisciplinary approach, blending combinatorial group theory with RL, offers valuable insights into problem hardness and algorithmic challenges.\n\nHowever, there are several reasons that I think this paper is not suitable for publication at NeurIPS 2025. The primary reason for this decision is that the paper's core contributions are more closely aligned with mathematical advancements in combinatorial group theory than with RL techniques, such as the use of A2C and PPO (Section 5). These are applied as tools to address these mathematical problems rather than introducing broadly applicable innovations in RL algorithms. While the authors argue that the introduction of \"supermoves\" (Section 6.23) might address the problem, it seems more like a conjecture at the moment that would require further study. \n\nI believe this work would be exceptionally well-suited for a workshop or venue focused on the intersection of mathematics and machine learning, where the mathematical contributions and the application of RL to solve complex group-theoretic problems would be of primary interest.", "questions": "Can you elaborate more on how supermoves could be achieved?", "limitations": "The paper's core contributions are more closely aligned with mathematical advancements in combinatorial group theory than with RL techniques, such as the use of A2C and PPO (Section 5). These are applied as tools to address these mathematical problems rather than introducing broadly applicable innovations in RL algorithms. While the authors argue that the introduction of \"supermoves\" (Section 6.23) might address the problem, it seems more like a conjecture at the moment that would require further study.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Stregnths -  Very interesting topics and the exploration of using RL to solve math problems is a promising direction\nWeakness - More like a \"case study\" of a summary of a study which not yet at the point of being published as a conference paper.", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer,\n\nThank you for taking the time to study our work. We are delighted to hear you found our RL exploration of the Andrews--Curtis conjecture combined with its mathematical contributions intellectually compelling. We are especially glad you appreciated the insights into hardness and algorithmic challenges. Hopefully we can alleviate some of the concerns you raised. From our perspective, your main concern seems to be: \n\n\n- *The paper's core contributions are more closely aligned with mathematical advancements in combinatorial group theory than with RL techniques, such as the use of A2C and PPO (Section 5). These are applied as tools to address these mathematical problems rather than introducing broadly applicable innovations in RL algorithms.*\n\n\nIn particular, we see how one could reach the conclusion: *I believe this work would be exceptionally well-suited for a workshop or venue focused on the intersection of mathematics and machine learning, where the mathematical contributions and the application of RL to solve complex group-theoretic problems would be of primary interest.* The interdisciplinary math-ML workshops, though, focus on applications of ML to math problems, as you point out, or, in the opposite direction, on math applications to ML with a goal of either laying ML foundations or making ML more explainable. These workshops rarely tackle the problem of developing new RL techniques for which NeurIPS seems like a perfect venue.\n\nWhile we focused on the specific case of the Andrews-Curtis conjecture, many of the features which make RL challenging to apply to this problem are typical of most open mathematical research problems. It is these RL challenges that we hope to bring to the surface and discuss with experts like yourself at this NeurIPS meeting.\n\nThe key feature of the AC-problem which (as far as we know) differentiates it from previously studied RL problems is that the gap between generic (average) case and the hardest case is not merely 10x or 100x, but rather many more orders of magnitude apart. This is why we believe the solution to this challenge can only come from RL community, and not from a typical math-ML workshop.\n\nPast RL success stories are, in a combinatorial sense, easier than the challenge described here: in board games like Go and Chess, even hand-made puzzles never require more than $100$ steps of foresight to solve. The 10-year history of achieving expert human performance on the infamous ``Montezuma's Revenge\" also falls far short of the challenge above, and so are many RL environments that involve autonomous vehicles, etc.\n\nThe Andrews-Curtis environment of this paper is a new kind of game, where an RL agent *must* make a super-exponential number of moves in a small number of important states. The question we tackle is: How can it do this?\n\nThe only way to turn the super-exponential number of actions to a sequence of exponential or polynomial length is to allow the action space to be dynamic. Admitting to it new types of moves that progressively combine large chunks of actions from the previous iteration of the action space.\n\nThis brings us to your companion remark:\n\n- *While the authors argue that the introduction of ``supermoves\" (Section 6.23) might address the problem, it seems more like a conjecture at the moment that would require further study.*\n\nWe want to clarify that the use of super-moves is unavoidable, it is a must in these kind of games where the distribution of hard and easy instances is extremely non-uniform and spans many orders of magnitude. The main challenge then lies in the algorithmic design that implements action changes in the most optimal case. We realize we should have stressed this point more in the paper, and will be happy to do so in the camera-ready version.\n\nIn other words, one of the main points of our paper is that *none* of the traditional RL techniques can handle environments with super-exponential hierarchy of hardness of the state space. While we discussed the performance of only policy-gradient methods in the manuscript, we have also experimented with off-policy and search-based algorithms. In all cases, these algorithms struggle with the extremely hard set of presentations. (We will include the performance levels of these algorithms in Section 4 of the camera-ready version of the paper.) We hope this aspect alone merits sufficient novelty for the RL community.\n\nAnd, as for concrete experiments with dynamic action spaces, we also want to share some details to elevate this from the conceptual --- and, in our opinion, important --- discussion to practical study. We have performed some experiments with super-moves and dynamic action spaces, which have shown improvement over the baseline results reported in the manuscript. \n\nSpecifically, our setup of dynamic action spaces looks as follows. We note that in many sequences of AC paths, a common strategy that the agent employs is to select several conjugation moves (AC$'$2) in a row followed by a single concatenation move (AC$'$1). We increased the size of the action space to include actions that perform conjugations by arbitrary words of generators and their inverses, followed by a single concatenation. This significantly enhances the size of the action space from the original $12$ to several thousands. In the beginning, however, we keep all of these new actions masked, letting the agent play the game with the original AC moves. \n\nAs the agent solves any new presentation, we scan through the path it found, look for the sub-sequences of moves of the type described above and unmask only the actions corresponding to these sub-sequences. We repeat this process after every 100 rollout phases of the PPO training loop. With this approach, the agent solves $13$ new presentations from the Miller--Schupp dataset that were previously unsolved by greedy search and our reinforcement learning agents with static action spaces. \n\nThese results provide some empirical evidence for the usefulness of dynamic action spaces and supermoves. We intend to add these results to Section 7 of the camera-ready version of the paper, along with providing paths for the $13$ newly solved presentations . We will also include the JAX code used for these experiments along with our submission. \n\nHopefully we managed to address all primary concerns. If not, please ask us for further clarifications."}, {"review_id": "AD4asFVrrt", "reviewer": "Reviewer_zK73", "summary": "The paper presents a RL framework for finding trivialization paths of the Andrews–Curtis conjecture, a mathematical problem involving search in a large state space, but where solutions are easy to verify.\nThe authors define the problem as a RL environment with sparse rewards and train PPO and A2C agents to find solutions to some yet-unsolved instances. Comparing to two search benchmarks (breadth-first and greedy) the authors find the RL approach to be roughly equivalent, with RL solving a handful of problem instances that search methods failed to solve.\nThe authors analyze hardness measures for the problem and propose some ideas on how to tackle this problem for future study.", "questions": "- Can you present any results that indicate the new methods suggested in section 7 are useful? If you can, this would upgrade section 7 from a speculative discussion to a concrete contribution.\n\n- I would suggest making a clearer separation between results related to deep learning and results that are not related to the field. In my opinion, the latter group of results should then be moved to the appendix, or published separately in a more relevant venue.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1) Identifying the AC conjecture as a good test bed for RL, together with the dataset and clear problem definition, is a useful addition for the field.\n\n2) The results show that the RL approach can solve a few instances where the benchmarks fail, even if only a few.\n\n3) The paper is clearly written and easy to follow.\n\n**Weaknesses**\n\n1) The paper dedicates a significant portion to discussing the use case, but the scope of this paper is a bit small when looking only at the parts relevant to RL.\nThe novelties related to RL are: the cost function and environment definition, the performance analysis of PPO and A2C, hardness & path length distributions, and the dataset release.\nOn the other hand, things like the alternative AC' moves, theoretical results (5.3) and GS trivialization length analysis (6.2.3) might be novel, but are more of interest for mathematicians than for the RL/ML research community. Several parts of the main paper discuss use-case specific information or results obtained only using the search benchmarks. In a NeurIPS paper, I would expect the non-ML mathematical results to appear in the appendix rather than in the results section.\n\n2) While the new algorithm suggestions in section 7 are indeed related to RL, they are not verified and are only presented as a promise of future study. These suggestions could very well be a crucial part of a future study, but in this paper they do not add much to the discussion without presenting an attempt to test them.\nSection 7 is presented in the introduction as one of the paper's 3 main contributions, while in my opinion it is too speculative and would fit better as a note on future study in a 'Discussion'/'Conclusion' section, or in the appendix.\n\n\nTo conclude, my main concern about this paper is the relatively small amount of results that are relevant for RL practitioners.", "was_revised": true, "final_justification": "The authors provided new results using the techniques suggested in section 7, proving that these techniques are actually useful. Together with their promise of adding new RL benchmarks to the main results (DQN and AlphaZero), the paper is significantly improved in my opinion.\n\nI do maintain some of my concern that the paper focuses too much on math novelties and not enough on RL related discoveries. If the paper is not accepted in its current form, I would suggest to the authors to revise it to better fit an ML/RL practitioners crowd, who care less about the problem solved and more about the method used to solve it.", "rebuttal": "Dear reviewer,\n\nThank you for your thoughtful and constructive review. We appreciate the time you took to engage with our work, in particular to note the analysis of the hardness measure, which is central to this work. We are also glad to hear you like the AC conjecture as a test bed for RL. We wish to return the favor and clarify your remaining concerns. (Please, do ask us for further clarifications if we fell short in this iteration.)\n\nWhile we agree that some parts of the paper are less focused on RL, this is primarily due to the fact that the paper is trying to accomplish a few different goals (which all revolve around RL, though).\n\nThe first is to introduce the AC environment to the RL community, for its super-exponential hierarchy of hardness across the state space. As far as we know, such environments have *never* been discussed in the RL literature before. We are proud to be the first, and hope other RL researchers will find this type of new RL environments interesting.\n\nThe second goal is our attempt to answer the question: *What would it take for an RL model to perform well in such types of environments with super-exponential hierarchy of sparse-reward long-horizon games?*\n\nNeither classical search algorithms nor any of the existing RL methods are suited for this challenging task. Therefore, one of our key messages in the paper was not so much the comparison of the performance between classical search algorithms and current RL tools, but rather the fact that neither performs well on these types of problems which are ubiquitous among long-standing research math problems.\n\nTo underscore the novelty of the RL research required to address the above question, we should point out that at the present time we are not aware of any strong reason to believe that RL can solve such problems in the first place. In other words, the answer may simply be ``This is impossible for RL.''\n\nWe hope this is not the case. And, the goal of the paper is to make first steps into RL research for such environments with super-exponential hierarchy of hardness. Specifically,\n\n- Multiple angles of attack --- classical search algorithms as well as existing RL algorithms --- for us are merely vehicles that led us to the notion of a new heuristic that we call ``hardness''.\n- We then study this notion of hardness from multiple vantage points and argue that an RL model must learn this hierarchy of scales of hardness in a dynamic way, through dynamic changes to the action space.\n\nIn other words, all parts of our work are different ``supporting characters'' for the lead actor, the above mentioned question: What would it take for RL to learn how to find super-exponential sequences of actions required for a tiny fraction of the states?\n\nBased on your feedback, we realize the connection between different parts of the paper and the ``supporting'' roles of various parts could have been made stronger, something we will try and improve on in the camera-ready version of the work.\n\nHopefully, this resolves one of your questions:\n\n*I would suggest making a clearer separation between results related to deep learning and results that are not related to the field. In my opinion, the latter group of results should then be moved to the appendix, or published separately in a more relevant venue.*\n\nTo address the other question:\n\n*Can you present any results that indicate the new methods suggested in section 7 are useful?*\n\nFirst, we want to clarify that super-moves and dynamic action spaces are unavoidable, and the only question (which we do not attempt to address in this paper) is what novel RL algorithms implement these dynamic changes in the most optimal way. Secondly, below we present explicit examples of such implementations that show performance improvements in our AC environment; we will be happy to include these implementations into a camera-ready version of the paper or provide further details in this exchange.\n\nTo start with a former, the key feature of the novel AC environment is that, unlike many well-studied RL environments, achieving the goal from some states requires a super-exponential number of steps compared to the polynomial number of steps for the majority of states. In fact, the number of such ``hard'' states is a tiny fraction of all states, which is why most of the standard RL models overfit on the generic states.\n\nThe only way to convert the super-exponential length of the sequence of actions into a polynomial sequence is to allow the action space to admit new actions, that we call ``super-moves,'' which combine a number of actions from current iteration of the action space. For example, if one such super-move $S_1$ combines $N$ basic actions, then the next iteration may admit a new action $S_2$ that combines $O(N)$ such super-moves $S_1$, so that the total length of $S_2$ expressed in basic actions will be $\\sim N^2$.  Repeating this process gives $|S_N| \\sim N^N$ and allows to drastically reduce the super-exponential sequences of basic actions to only exponential or, with more efficient choices of super-moves, even further to just polynomial length sequences.\n\nOnce we realize that super-moves are unavoidable in such exceptionally problems, the next question is how to best guide the RL model to make such dynamic changes. While we hope to open this question to a wider community of RL researchers, here we can offer concrete evidence based on a recent implementation. We have performed experiments with super-moves and dynamic action spaces, which show improvement over the baseline results reported in the manuscript. \n\nOur setup of dynamic action spaces looks as follows. We note that in many sequences of AC paths, a common strategy that the agent employs is to select several conjugation moves (AC$'$2) in a row followed by a single concatenation move (AC$'$1). We increased the size of the action space to include actions that perform conjugations by arbitrary words of generators and their inverses, followed by a single concatenation. This significantly enhances the size of the action space from the original $12$ to several thousands. In the beginning, however, we keep all of these new actions masked, letting the agent play the game with the original AC moves. \n\nAs the agent solves any new presentation, we scan through the path it found, look for the sub-sequences of moves of the type described above and unmask only the actions corresponding to these sub-sequences. We repeat this process after every 100 rollout phases of the PPO training loop. With this approach, the agent solves $13$ new presentations from the Miller--Schupp dataset that were previously unsolved by greedy search and our reinforcement learning agents with static action spaces. \n\nThese results shine a new light on the usefulness of dynamic action spaces and supermoves. We hope to add these results to Section 7 of the camera-ready version of the paper, along with providing paths for the $13$ newly solved presentations . We will also include the JAX code used for these experiments along with our submission. \n\nWe also wish to remark that while techniques may seem extremely specific to the Andrews--Curtis environment at first, this is far from the truth. Many problems in mathematics come with examples that vary super-exponentially in hardness. Such problems arise in topology (e.g. in the problem of unknotting a knot), graph theory (e.g. in identifying the Ramsey numbers), and so on. If RL systems of the future are to help humanity solve these challenging problems, the introduction of supermoves and dynamic action spaces seems inevitable."}]

Author rebuttal:

Meta-review: This paper presents an ambitious case study on applying reinforcement learning (RL) techniques to a long-standing mathematical problem—the Andrews–Curtis conjecture. It frames this as a sparse-reward, long-horizon RL environment and analyzes the difficulty of solving instances using PPO and A2C agents. The authors contribute novel mathematical results, including resolving previously open instances, and propose techniques such as supermoves and dynamic action spaces to address problem hardness.

This was a borderline case. Initially, reviewers leaned toward rejection, noting that while the setting is intriguing, the RL contributions felt limited and the focus was more on mathematical outcomes. However, the authors engaged seriously during the rebuttal, providing additional experiments, comparisons to other baselines (e.g., DQN, AlphaZero), and empirical support for their proposed techniques. These additions shifted reviewer opinion, and several now support acceptance.

We recommend acceptance, trusting in good faith that the authors will revise the paper accordingly. If the review process allowed for conditional acceptance, we would have required these revisions as part of the final decision.
Decision: Accept (poster)