Structured Reinforcement Learning for Combinatorial Decision-Making
Heiko Hoppe, Léo Baty, Louis Bouvier, Axel Parmentier, Maximilian Schiffer · 2025
Read Structured Reinforcement Learning for Combinatorial Decision-Making by Heiko Hoppe, Léo Baty, Louis Bouvier, Axel Parmentier, Maximilian Schiffer (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-19053.txt.
Introduction
Heiko Hoppe and four co-authors blend reinforcement learning with combinatorial optimization for hard decision problems, in a paper from twenty twenty-five. Routing, scheduling, and assortment choices explode combinatorially, and plain learning algorithms scale poorly and waste the problems' structure.
Their method, structured reinforcement learning, embeds an optimization layer inside the decision-making network itself. A special loss function makes the whole actor trainable end to end, and the authors give the scheme a geometric reading as a primal-dual algorithm. Across six test settings with outside and self-made uncertainty, the method matched or beat plain learning and imitation on static tasks. On dynamic problems it improved results by up to ninety-two percent, with steadier, faster training.
Catalog record
| CREATOR | Heiko Hoppe, Léo Baty, Louis Bouvier, Axel Parmentier, Maximilian Schiffer |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 97 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-19053
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Structured Reinforcement Learning for Combinatorial Decision-Making Heiko Hoppe, Léo Baty, Louis Bouvier, Axel Parmentier, Maximilian Schiffer 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. 1 1 1 Our code is available at https://github.com/tumBAIS/Structured-RL . 1 Introduction Reinforcement learning has achieved remarkable progress during the last decade, expanding beyond its early success stories of Atari games and robotic control. Recently, increasing attention has been given to real-world industrial problems, such as vehicle routing, inventory planning, machine scheduling, and assortment optimization ( Nazari et al., 2018 ; Kool et al., 2019 ; Hottung and Tierney, 2022 , e.g.,) . Unlike traditional RL applications, these industrial problems often involve large-scale combinatorial decision-making, which challenges classical RL algorithms ( Hildebrandt et al., 2023 , cf.,) . In particular, existing algorithms struggle with: i) the exponential size of the action spaces, which renders action selection computationally intractable and hinders efficient exploration; and ii) leveraging the combinatorial structure of the action spaces using standard neural architectures, often resulting in poor generalization and unstable learning dynamics ( Yuan et al., 2022 , cf.,) . From a methodological perspective, most industrial problems translate into combinatorial Markov Decision Processes (MDPs), i.e., MDPs with combinatorial action spaces, that remain the focus of this paper. Problem 1 (Combinatorial Markov Decision Process) . We consider MDPs with states s\in\mathcal{S} , actions a\in\mathcal{A}(s)\subset\mathbb{R}^{d(s)} , rewards r , and transition probabilities \mathbb{P}(s^{\prime},r\mid s,a) with next state s^{\prime} . In combinatorial MDPs, \mathcal{A}(s) is the set of feasible solutions of a combinatorial problem. We denote its convex hull as the moment polytope \mathcal{C}(s):=\operatorname{conv}(\mathcal{A}(s)) . As in stochastic optimization ( Bertsekas and Shreve, 1996 ) , we use a latent noise variable \xi\in\Xi with probability p(\xi\mid s,a) , such that the transition to (s^{\prime},r) given (s,a,\xi) is deterministic. We distinguish exogenous noise, where the distribution of \xi does not depend on a , and endogenous noises, where the distribution of \xi depends on a . Given unknown \mathbb{P}(s^{\prime},r|s,a) , we aim to find the reward-maximizing policy \bar{\pi}\in\arg\max_{\pi}\mathbb{E}_{\pi,\mathbb{P}}\left[\sum_{t=0}^{T}\gamma^{t}r_{t}\right], over [0,T] , given a discount factor \gamma . We further define Q-values, satisfying the Bellman equation Q^{\pi}(s_{t},a_{t})=\mathbb{E}_{\mathbb{P}}\left[r_{t}\right]+\gamma\>\mathbb{E}_{\mathbb{P}}\left[\max_{\tilde{a}_{t+1}}Q^{\pi}(s_{t+1},\tilde{a}_{t+1})\right], using expectations with respect to \mathbb{P}(s^{\prime},r\mid s,a) . The limitations of standard RL algorithms in solving such Combinatorial MDPs (C-MDPs) render them insufficient to solve many industrial problems. To overcome these drawbacks, we propose Structured Reinforcement Learning (SRL) – a novel actor-critic RL paradigm that embeds combinatorial optimization (CO)-layers into neural actors, enabling to exploit the underlying problem structure. State of the Art Several research communities have studied learning and decision-making over structured spaces, including structured prediction ( Nowozin and Lampert, 2011 , e.g.,) , differentiable optimization layers ( Amos and Kolter, 2017 , e.g.,) , and hierarchical reinforcement learning ( Bacon et al., 2017 , e.g.,) . While these works provide tools for embedding structure, they do not directly tackle end-to-end reinforcement learning in environments with combinatorial action spaces. Prior approaches to solving C-MDPs include handcrafted decision rules ( Liyanage and Shanthikumar, 2005 ; Huber et al., 2019 , e.g.,) and predict-and-optimize algorithms ( Alonso-Mora et al., 2017 ; Bertsimas and Kallus, 2020 , e.g.,) . While the former fail to model complex dynamics or constraints, the latter typically rely on imitation learning and separate prediction from optimization, which impairs performance in dynamic settings ( Enders et al., 2023 , cf.,) . In contrast, CO-augmented Machine Learning (COAML)-pipelines integrate combinatorial optimization directly into model architectures, allowing end-to-end learning ( Parmentier, 2022 ; Dalle et al., 2022 , e.g.,) . Here, the key challenge is to differentiate through the CO-layer. Existing approaches include problem-specific relaxation schemes ( Vlastelica et al., 2020 , e.g.,) , and more general strategies, e.g., using Fenchel-Young losses ( Blondel et al., 2020 ; Berthet et al., 2020 , e.g.,) . The latter allow continuous training over discrete structures and are increasingly used for differentiating COAML-pipelines ( Dalle et al., 2022 , e.g.,) . In C-MDPs, prior work either uses offline expert imitation ( Baty et al., 2024 ; Jungel et al., 2024 , e.g.,) or treats the CO-layer as an action mask in unstructured RL ( Hoppe et al., 2024 ; Woywood et al., 2025 , e.g.,) . The former requires access to expert solutions, while the latter often leads to unstable gradients. Imitation approaches also suffer from insufficient exploration in multi-stage problems. SRL builds on classical policy-gradient algorithms, e.g., REINFORCE, PPO, and SAC ( Williams, 1992 ; Haarnoja et al., 2018 , cf.,) , which perform well in conventional MDPs but are challenged by the size and structure of C-MDP action spaces ( Hildebrandt et al., 2023 ) . Problem-specific neural network designs often lack generalizability across applications and struggle in dynamic contexts ( Bello et al., 2017 ; Dai et al., 2017 , e.g.,) , while neural improvement methods rely on existing initial solutions ( Yuan et al., 2022 ; Hottung and Tierney, 2022 , e.g.,) . Value-based methods often assume decomposable critics ( Xu et al., 2018 ; Liang et al., 2022 , e.g.,) , limiting applicability in structured domains. Alternative approaches transform a task-specific Q-network into a mixed-integer linear program, which potentially increases solution time and limits the range of usable network architectures ( Xu et al., 2025 , e.g.,) . SRL is also related to offline RL, which frequently relies on imitation learning ( Figueiredo Prudencio et al., 2024 , e.g.,) , but differs by operating online and updating from on-policy targets. Contribution To address the challenges outlined above, we propose a novel reinforcement learning paradigm for solving C-MDPs by integrating CO-layers into actor-critic architectures. Specifically, we introduce Structured Reinforcement Learning (SRL), a new framework for the end-to-end training of COAML-pipelines using only collected experience. SRL replaces the neural actor with a combinatorial policy defined by a score-generating network and a CO-layer. To enable end-to-end learning despite the non-differentiability of the CO-layer, SRL combines stochastic perturbation and Fenchel-Young losses to construct smooth actor updates, enabling stable policy improvement. We further provide a geometric analysis that interprets SRL as a sampling-based primal-dual method in the dual of the moment polytope, connecting structured learning and RL from a theoretical lens. We demonstrate the effectiveness of SRL across six representative environments, including both static and dynamic decision problems with exogenous and endogenous uncertainty. On static problems, SRL improves by up to 54% on unstructured deep reinforcement learning baselines, and matches the performance of Structured Imitation Learning (SIL), despite requiring no expert supervision. On dynamic problems, SRL consistently outperforms SIL by up