Analyzing RL Components for Wagner's Framework via Brouwer's Conjecture

Abstract

In this work, we continue the study and systematization started in our previous work (Angileri et al. in: Lecture notes in computer science 15243 LNAI, 2025, pp 325–338. https://doi.org/10.1007/978-3-031-78977-9_21 ) of Wagner’s Reinforcement Learning framework to investigate graph conjectures. After identifying three main directions that impact the framework’s performance (the environment dynamics, the RL algorithm and the neural network used as a function approximator), we conduct an ablation study to evaluate the effectiveness of each component, analyzing several variations of them. The experiments compare three environment dynamics, implemented as Gym spaces ( Linear , Local and Global ), two algorithms [PPO and the Cross-Entropy method (Wagner in Constructions in combinatorics via neural networks, 2021, https://arxiv.org/abs/2104.14516 )], different neural network structures (Multi-Layer Perceptron and Graph Neural Networks) and reward systems. This study was intended not only to test the framework’s capabilities, but also to identify a configuration of environment, algorithm, and neural network that can be effective when exploring graph spaces, even with a complex target. For this reason, all the experiments were executed on Brouwer’s Conjecture. We also present the data collected with the various trained models, as these interesting configurations can be used in the inference process on the problem. Our analysis shows that a proper calibration of the individual components of the framework can significantly improve its performance, suggesting effective settings for addressing complex problems and contributing to the study of Brouwer’s Conjecture. All the codes and data are open source and available at https://github.com/CuriosAI/graph_conjectures .