Structured Reinforcement Learning for Combinatorial Decision-Making

2025/05/25 by Heiko Hoppe, Hoppe, Heiko, Léo Baty +7 · 2 citations
Engineering · #Advanced Research in Systems and Signal Processing #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2505.19053

openalex publication_date 2025/05/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Reinforcement learning (RL) is increasingly applied to real-world problems involving complex and structured decisions, such as routing, scheduling, and assortment planning. These settings challenge standard RL algorithms, which struggle to scale, generalize, and exploit structure in the presence of combinatorial action spaces. We propose Structured Reinforcement Learning (SRL), a novel actor-critic paradigm that embeds combinatorial optimization-layers into the actor neural network. We enable end-to-end learning of the actor via Fenchel-Young losses and provide a geometric interpretation of SRL as a primal-dual algorithm in the dual of the moment polytope. Across six environments with exogenous and endogenous uncertainty, SRL matches or surpasses the performance of unstructured RL and imitation learning on static tasks and improves over these baselines by up to 92% on dynamic problems, with improved stability and convergence speed.

Citations

• Primal-dual algorithm for contextual stochastic combinatorial optimization
• Multi-Agent Soft Actor-Critic with Coordinated Loss for Autonomous Mobility-on-Demand Fleet Control
• The Elements of Differentiable Programming
• Global Rewards in Multi-Agent Deep Reinforcement Learning for Autonomous Mobility on Demand Systems
• A Survey of Contextual Optimization Methods for Decision Making under Uncertainty
• Combinatorial Optimization enriched Machine Learning to solve the Dynamic Vehicle Routing Problem with Time Windows
• Learning-based Online Optimization for Autonomous Mobility-on-Demand Fleet Control
• Hybrid Multi-agent Deep Reinforcement Learning for Autonomous Mobility on Demand Systems
• Learning with Combinatorial Optimization Layers: a Probabilistic Approach
• Generating Adjacency-Constrained Subgoals in Hierarchical Reinforcement Learning
• Learning with Differentiable Perturbed Optimizers
• Monte Carlo Gradient Estimation in Machine Learning
• Learning Action Representations for Reinforcement Learning
• Learning with Fenchel-Young Losses
• Dynamic Assortment Optimization with Changing Contextual Information
• Addressing Function Approximation Error in Actor-Critic Methods
• Reinforcement Learning for Solving the Vehicle Routing Problem
• Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor
• Proximal Policy Optimization Algorithms
• Learning Combinatorial Optimization Algorithms over Graphs
• OptNet: Differentiable Optimization as a Layer in Neural Networks
• Neural Combinatorial Optimization with Reinforcement Learning
• The Option-Critic Architecture
• Deep Reinforcement Learning in Large Discrete Action Spaces
• From Predictive to Prescriptive Analytics
• A Note on Two Problems in Connexion with Graphs

Cited by

• Reproducibility in the Control of Autonomous Mobility-on-Demand Systems
• Hard Constraints, Smooth Gradients: Learning Feasible Inventory Policies via Differentiable Projection

Related

• Reinforcement Learning for Combinatorial Optimization: A Survey
• Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch
• Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routing
• Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization
• Heuristics for Combinatorial Optimization via Value-based Reinforcement Learning: A Unified Framework and Analysis