mlsanityData to 14 Oct 2026

Structured Reinforcement Learning for Combinatorial Decision-Making

arXiv 2505.19053 ↗First posted 25 May 2025cs.LG math.OC stat.MLcited by 7

On the map: Deep reinforcement learning methods → RL for games and combinatorial optimization

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.

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.

Builds on

29 of 49 references.

References · 29

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,885
  3. 2018Addressing Function Approximation Error in Actor-Critic Methodscited by 2,417
  4. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 608
  5. 2017OptNet: Differentiable Optimization as a Layer in Neural Networkscited by 599
  6. 2014Convex Optimization: Algorithms and Complexitycited by 575
  7. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  8. 2016The Option-Critic Architecturecited by 448
  9. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 333
  10. 2019Monte Carlo Gradient Estimation in Machine Learningcited by 283
  11. 2022A Survey on Offline Reinforcement Learning: Taxonomy, Review, and Open Problemscited by 231
  12. 2019Differentiation of Blackbox Combinatorial Solverscited by 226
17 more
  1. 2015Deep Reinforcement Learning in Large Discrete Action Spacescited by 161
  2. 2014From Predictive to Prescriptive Analyticscited by 143
  3. 2019Learning with Fenchel-Young Lossescited by 119
  4. 2023A Survey of Contextual Optimization Methods for Decision Making under Uncertaintycited by 82
  5. 2020Learning with Differentiable Perturbed Optimizerscited by 81
  6. 2019Learning Action Representations for Reinforcement Learningcited by 75
  7. 2020Generating Adjacency-Constrained Subgoals in Hierarchical Reinforcement Learningcited by 58
  8. 2024The Elements of Differentiable Programmingcited by 43
  9. 2022Learning with Combinatorial Optimization Layers: a Probabilistic Approachcited by 29
  10. 2018Dynamic Assortment Optimization with Changing Contextual Informationcited by 28
  11. 2022Hybrid Multi-agent Deep Reinforcement Learning for Autonomous Mobility on Demand Systemscited by 18
  12. 2023Learning-based Online Optimization for Autonomous Mobility-on-Demand Fleet Controlcited by 14
  13. 2023Combinatorial Optimization enriched Machine Learning to solve the Dynamic Vehicle Routing Problem with Time Windowscited by 10
  14. 2023Global Rewards in Multi-Agent Deep Reinforcement Learning for Autonomous Mobility on Demand Systemscited by 8
  15. 2025Reinforcement learning with combinatorial actions for coupled restless banditscited by 5
  16. 2025Primal-dual algorithm for contextual stochastic combinatorial optimizationcited by 4
  17. 2024Multi-Agent Soft Actor-Critic with Coordinated Loss for Autonomous Mobility-on-Demand Fleet Controlcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 7.

7 papers.

  1. 2026Combinatorial Optimization Augmented Machine Learningcited by 3
  2. 2026Differentiable Knapsack and Top-k Operators via Dynamic Programmingcited by 1
  3. 2026Latent Spherical Flow Policy for Reinforcement Learning with Combinatorial Actionscited by 1
  4. 2026Breaking the Grid: Distance-Guided Reinforcement Learning in Large Discrete Action Spacescited by 0
  5. 2026Regularized Large Neighborhood Searchcited by 0
  6. 2026Bellman-Taylor Score Decoding for Markov Decision Processes with State-Dependent Feasible Action Setscited by 0
  7. 2026Hard Constraints, Smooth Gradients: Learning Feasible Inventory Policies via Differentiable Projectioncited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Heuristics for Combinatorial Optimization via Value-based Reinforcement Learning: A Unified Framework and Analysis
  2. 2026Offline Decision Transformers for Neural Combinatorial Optimization: Surpassing Heuristics on the Traveling Salesman Problem
  3. 2026Projecting Latent RL Actions: Towards Generalizable and Scalable Graph Combinatorial Optimization
  4. 2026Learning Multi-Timescale Abstractions for Hierarchical Combinatorial Planning
  5. 2022Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch
  6. 2026Improving and Accelerating Offline RL in Large Discrete Action Spaces with Structured Policy Initialization
  7. 2024Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective
  8. 2025Planning in Branch-and-Bound: Model-Based Reinforcement Learning for Exact Combinatorial Optimization