Research map / Reinforcement learning / Policy gradient and actor-critic
Structured Reinforcement Learning for Combinatorial Decision-Making
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Structured Reinforcement Learning (SRL), an actor-critic method that embeds a combinatorial optimization layer in the actor and trains it end-to-end with Fenchel-Young losses using critic-weighted sampled target actions, evaluated on six combinatorial MDP environments.
Problem
Reinforcement learning in combinatorial Markov decision processes with large structured action spaces (routing, scheduling, assortment planning), where standard RL struggles to scale, generalize, and exploit structure.
Approach
Embed a combinatorial optimization layer into the actor and train it with Fenchel-Young losses toward a softmax-weighted target action built from sampled perturbed solutions scored by a critic, avoiding offline expert demonstrations; the update is interpreted as a sampling-based primal-dual method over the moment polytope.
Key results
- SRL improves over PPO by 16% (DVSP), 77% (DAP) and 92% (GSPP) on dynamic problems.
- SRL outperforms SIL by 8% on DAP and 78% on GSPP, and matches SIL on DVSP.
- PPO variance is up to 80x higher than SRL's across environments; SRL requires about 30 minutes of training per environment.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SRL instead of SIL | Dynamic Assortment Problem · DAP | performance: 8% | Helped |
| Use SRL instead of SIL | Gridworld Shortest Paths Problem · GSPP | performance: 78% | Helped |
| Use SRL instead of PPO | Dynamic Vehicle Scheduling Problem · DVSP | performance: 16% | Helped |
| Use SRL instead of PPO | Dynamic Assortment Problem · DAP | performance: 77% | Helped |
| Use SRL instead of PPO | Gridworld Shortest Paths Problem · GSPP | performance: 92% | Helped |
| Use SRL instead of PPO | Dynamic Vehicle Scheduling Problem · DVSP | test reward standard deviation: 5.6 -> 0.3 | Helped |
| Use SRL instead of PPO | Dynamic Assortment Problem · DAP | test reward standard deviation: 13.5 -> 1.9 | Helped |
| Use SRL instead of PPO | Gridworld Shortest Paths Problem · GSPP | test reward standard deviation: 47.0 -> 0.6 | Helped |
| Use SRL instead of SIL | Dynamic Vehicle Scheduling Problem · DVSP | training time: 12m -> 31m | Hurt |
Surprising findings
- On GSPP, SRL surpasses the online optimum (expert) by 79%, which imitation learning cannot do because it is bounded by the expert.
- SRL matches SIL on static tasks despite requiring no expert supervision.
Limitations
- SRL's computational cost scales with CO-layer complexity and is higher than PPO and SIL.
- Hyperparameter tuning used grid searches, and the Q-function is not decomposable so direct argmax over actions is infeasible.
- Multiple design choices, such as SAC comparison, are left to future work; entropy regularization for combinatorial actions is not addressed.
Experimental setup
Datasets: Warcraft Shortest Paths Problem Single Machine Scheduling Problem Stochastic Vehicle Scheduling Problem Dynamic Vehicle Scheduling Problem Dynamic Assortment Problem Gridworld Shortest Paths Problem
Benchmarks: Warcraft Shortest Paths Problem Single Machine Scheduling Problem Stochastic Vehicle Scheduling Problem Dynamic Vehicle Scheduling Problem Dynamic Assortment Problem Gridworld Shortest Paths Problem
Metrics: test reward validation reward standard deviation across seeds training time
Baselines: Structured Imitation Learning (SIL) PPO expert policy greedy policy
Builds on: Fenchel-Young losses PPO structured imitation learning perturbed optimizers double Q-learning
Closest papers by meaning
- Reinforcement learning with combinatorial actions for coupled restless bandits (ICLR 2025 · similarity 0.90)
- Preference Optimization for Combinatorial Optimization Problems (ICML 2025 · similarity 0.87)
- Overcoming Slow Decision Frequencies in Continuous Control: Model-Based Sequence Reinforcement Learning for Model-Free Control (ICLR 2025 · similarity 0.87)
- Symmetric Replay Training: Enhancing Sample Efficiency in Deep Reinforcement Learning for Combinatorial Optimization (ICML 2024 · similarity 0.87)
- Combinatorial Reinforcement Learning with Preference Feedback (ICML 2025 · similarity 0.87)
- Sequential Stochastic Combinatorial Optimization Using Hierarchal Reinforcement Learning (ICLR 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.