# Structured Reinforcement Learning for Combinatorial Decision-Making

arXiv: https://arxiv.org/abs/2505.19053 · HTML: https://mlsanity.com/paper/2505.19053/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 29 of its 49 references that are in the map.
- First posted on arXiv 25 May 2025.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 29 of 29)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Addressing Function Approximation Error in Actor-Critic Methods](https://mlsanity.com/paper/1802.09477/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [OptNet: Differentiable Optimization as a Layer in Neural Networks](https://mlsanity.com/paper/1703.00443/) (2017)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [The Option-Critic Architecture](https://mlsanity.com/paper/1609.05140/) (2016)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Monte Carlo Gradient Estimation in Machine Learning](https://mlsanity.com/paper/1906.10652/) (2019)
- [A Survey on Offline Reinforcement Learning: Taxonomy, Review, and Open Problems](https://mlsanity.com/paper/2203.01387/) (2022)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Deep Reinforcement Learning in Large Discrete Action Spaces](https://mlsanity.com/paper/1512.07679/) (2015)
- [From Predictive to Prescriptive Analytics](https://mlsanity.com/paper/1402.5481/) (2014)
- [Learning with Fenchel-Young Losses](https://mlsanity.com/paper/1901.02324/) (2019)
- [A Survey of Contextual Optimization Methods for Decision Making under Uncertainty](https://mlsanity.com/paper/2306.10374/) (2023)
- [Learning with Differentiable Perturbed Optimizers](https://mlsanity.com/paper/2002.08676/) (2020)
- [Learning Action Representations for Reinforcement Learning](https://mlsanity.com/paper/1902.00183/) (2019)
- [Generating Adjacency-Constrained Subgoals in Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2006.11485/) (2020)
- [The Elements of Differentiable Programming](https://mlsanity.com/paper/2403.14606/) (2024)
- [Learning with Combinatorial Optimization Layers: a Probabilistic Approach](https://mlsanity.com/paper/2207.13513/) (2022)
- [Dynamic Assortment Optimization with Changing Contextual Information](https://mlsanity.com/paper/1810.13069/) (2018)
- [Hybrid Multi-agent Deep Reinforcement Learning for Autonomous Mobility on Demand Systems](https://mlsanity.com/paper/2212.07313/) (2022)
- [Learning-based Online Optimization for Autonomous Mobility-on-Demand Fleet Control](https://mlsanity.com/paper/2302.03963/) (2023)
- [Combinatorial Optimization enriched Machine Learning to solve the Dynamic Vehicle Routing Problem with Time Windows](https://mlsanity.com/paper/2304.00789/) (2023)
- [Global Rewards in Multi-Agent Deep Reinforcement Learning for Autonomous Mobility on Demand Systems](https://mlsanity.com/paper/2312.08884/) (2023)
- [Reinforcement learning with combinatorial actions for coupled restless bandits](https://mlsanity.com/paper/2503.01919/) (2025)
- [Primal-dual algorithm for contextual stochastic combinatorial optimization](https://mlsanity.com/paper/2505.04757/) (2025)
- [Multi-Agent Soft Actor-Critic with Coordinated Loss for Autonomous Mobility-on-Demand Fleet Control](https://mlsanity.com/paper/2404.06975/) (2024)

## Built on by (most cited first, 7 of 7)

- [Combinatorial Optimization Augmented Machine Learning](https://mlsanity.com/paper/2601.10583/) (2026)
- [Differentiable Knapsack and Top-k Operators via Dynamic Programming](https://mlsanity.com/paper/2601.21775/) (2026)
- [Latent Spherical Flow Policy for Reinforcement Learning with Combinatorial Actions](https://mlsanity.com/paper/2601.22211/) (2026)
- [Breaking the Grid: Distance-Guided Reinforcement Learning in Large Discrete Action Spaces](https://mlsanity.com/paper/2602.08616/) (2026)
- [Regularized Large Neighborhood Search](https://mlsanity.com/paper/2606.02294/) (2026)
- [Bellman-Taylor Score Decoding for Markov Decision Processes with State-Dependent Feasible Action Sets](https://mlsanity.com/paper/2606.10979/) (2026)
- [Hard Constraints, Smooth Gradients: Learning Feasible Inventory Policies via Differentiable Projection](https://mlsanity.com/paper/2608.02343/) (2026)

## Abstract (arXiv)

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.