Reinforcement Learning for Graph Combinatorial Optimization

Welcome to the webpage for our tutorial at the LoG 2026 Conference.

📍 Location: Northeastern University, Interdisciplinary Science & Engineering Complex (ISEC)
🗓️ Date and time: November 21, 2026 16:00 EST (Boston time)
⏱️ Length: 2.5 hours

Abstract

Graph-based combinatorial optimization (GCO) problems, which involve finding a discrete structure that optimizes a given objective function, play a critical role in many real-world systems.

Read full abstract

Their applications span classic benchmark problems as well as a wide range of real-world scenarios. However, as graph sizes grow, exact optimization quickly becomes computationally prohibitive, motivating the use of heuristic and approximation methods that often require substantial problem-specific expertise.

Machine learning (ML) methods have steadily gained popularity for solving GCO problems. In particular, reinforcement learning (RL) has demonstrated the ability to automatically learn, using a reward signal, heuristics for constructing GCO solutions. Such approaches can achieve competitive solution quality with fast inference, while automating the complex trial-and-error process of heuristic design and retaining applicability across a wide range of problems. However, applying RL to GCO problems is technically complex. It requires understanding concepts from traditionally disjoint communities (RL, graph learning, GCO) that are presented in fragmented resources. This is the gap our tutorial aims to fill.

The first half of our tutorial begins by introducing GCO problems, traditional methods for solving them, and modern ML techniques. We subsequently introduce the Markov Decision Process (MDP) formalism and show how to formulate GCO problems as MDPs. Next, we introduce deep RL and graph representation learning methods and discuss their integration into GCO pipelines. We discuss evaluation methodologies and key challenges, including scalability and generalization. Lastly, we cover some of the many applications of RL for GCO.

Speakers

Franco Terranova

Université de Lorraine, CNRS, INRIA, LORIA

Franco Terranova has recently completed his Ph.D. in Computer Science at the INRIA Center of the Université de Lorraine and is joining University of California, Santa Barbara (UCSB) as an incoming Postdoctoral Research Fellow. His Ph.D. research focused on designing scalable and generalizable deep reinforcement learning (RL) methods for predicting cyber-attack paths, with a particular emphasis on graph learning. During his Ph.D., he completed research visits at the Barcelona Neural Networking Center and the University of Waterloo, where he worked on applying RL methods to several graph combinatorial optimization problems in networking and cloud computing. He previously delivered two RL tutorials at the European Agent Systems Summer School (EASSS) in 2024 and 2025, covering deep RL foundations, practical implementation, and meta-learning for improved agent generalization. He also organized a broad range of AI-related tutorials within the LORIA laboratory through the DeepLorIA network.

Personal Website Google Scholar Email

Victor-Alexandru Darvariu

University of Sheffield

Victor-Alexandru Darvariu is a Lecturer (Assistant Professor) at the University of Sheffield. Prior to this, he was a Postdoctoral Researcher at the Oxford Robotics Institute, University of Oxford. He completed his Ph.D. at University College London (UCL) and The Alan Turing Institute in 2023. His research develops rigorous RL methods for solving decision-making problems in science and engineering, with a particular focus on graph-structured and combinatorial optimization problems. His publications on learning-based approaches to GCO have appeared in venues including NeurIPS, LoG, and TMLR. The applications of his work span robotics, computer and communication systems, operations research, and the physical sciences. Victor is an author of the survey “Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective” (TMLR, 2024) and the recently published “Using Graph Neural Networks in Reinforcement Learning: A Practical Guide” (ICLR Blogposts, 2026). He has delivered lectures and tutorials on RL and GNNs at UCL and the University of Oxford.

Personal Website Google Scholar Email

Resources

📊 Tutorial Slides: [link]
💻 Tutorial Code: https://github.com/terranovafr/RLforGCO-LoG2026
💻 LaGCO Library: https://github.com/terranovafr/LaGCO-RL

📄 Key Publications and Resources

TMLR survey on reinforcement learning for graph combinatorial optimization: Darvariu, Hailes, and Musolesi (2024).
ICLR blogpost on using graph neural networks in reinforcement learning: Schutz and Darvariu (2026).
Paper introducing LaGCO-RL library: Terranova, Bernardez, Cabellos-Aparicio, Miolane, and Lahmadi (2026).

Setup Instructions

Prior to the tutorial, participants should follow the setup instructions at https://github.com/terranovafr/RLforGCO-LoG2026 to install Docker and locally build the container with the appropriate dependencies.

Please note that this requires downloading about 2GB of data, which may be challenging to do during the live tutorial over conference WiFi. Therefore, we advise participants to complete this step before attending.