Ivan Damnjanović: Reinforcement learning meets graph theory: A new framework

Reinforcement learning (RL) is a branch of machine learning concerned with designing models that can learn effective decision-making strategies through interaction and experience. In a recent influential paper, Wagner showed that the Deep Cross-Entropy method from RL can be used to address problems in extremal graph theory by reformulating them as combinatorial optimization tasks. This idea sparked growing interest in the community, leading to a range of refinements and extensions of Wagner’s original framework, as well as the development of RL environments specialized for graph theory. As a result, several problems in extremal graph theory have already been successfully approached using RL techniques.

In this work, we introduce Reinforcement Learning for Graph Theory (RLGT), a new framework that unifies and organizes these previous efforts. RLGT is designed to handle both undirected and directed graphs, optionally allowing loops and supporting an arbitrary number of edge colors. The framework provides efficient graph representations and is intended to support future research in RL-based extremal graph theory through improved computational efficiency and a modular architecture.

(This is a joint work with Uroš Milivojević, Irena Ðorđević and Dragan Stevanović.)

Join Zoom Meeting HERE!