Structured Reinforcement Learning:
Decision-Making at the Interface of Machine Learning and Combinatorial Optimization

Heiko Hoppe

The gap between prediction and decision

Consider a delivery company preparing tomorrow’s operations. It faces two very different questions at the same time. The first is a question of prediction: which customers will order tomorrow; how much will they order; what time windows will they demand? The second is a question of decision: how many trucks to send; which route each truck takes; in what order each stop is served. These two tasks demand entirely different methodologies. Prediction is the natural realm of machine learning (ML): observational inputs, noisy data, stochastic dynamics. Decision-making, in contrast, is the natural realm of operations research (OR): discrete choices, hard feasibility constraints, sophisticated combinatorial algorithms built over decades.

For most of their history, these two fields have been separated. In one room, statisticians forecast unknowns from data. In another room, operations researchers treat the forecasts as certainties and design schedules using mixed-integer programming, shortest-path algorithms, and graph flows. The forecasts are sent to the OR-room; the decisions are sent to the ML-room if required. This pipeline – commonly called predict-then-optimize – is computationally efficient and lets each community keep working in its native mathematical idiom. It also has a subtle flaw that becomes increasingly visible as ML and OR are asked to cooperate on harder problems.

A five-percent error is not a five-percent error. Suppose the ML forecast deviates from tomorrow’s true demand of a customer by 5%. To a regression model, 5% underestimation and 5% overestimation are symmetric: both yield an identical mean squared error. To an operations manager, the two can be fundamentally different. A slight overestimate may mean a truck runs a little below capacity – mildly wasteful. A slight underestimate may mean a truck arrives full and the remaining orders cannot be delivered; an emergency vehicle must be dispatched, drivers are rescheduled, customer promises are broken. The cost curve is highly asymmetric, unknown to the statistical training. A “better” prediction in the statistical sense can yield a worse decision in the operational sense. A visualization of this mismatch can be seen in Figure 1.

This loss-cost mismatch is the structural motivation behind a growing research area at the interface of ML and OR, known as Combinatorial Optimization Augmented Machine Learning (COAML). The central idea is straightforward: instead of treating prediction and optimization as two separated, embed the combinatorial solver as a layer inside the neural network, so that the entire pipeline – perception, reasoning, and decision – is trained end-to-end on the final decision. Figure 2 contrasts the two worldviews. For a comprehensive technical treatment of the field, see Schiffer et al. (2026).

Phrased mathematically, COAML parametrizes the policy

in which a neural network φ_w maps a context x to a parameter vector θ, and a combinatorial oracle ŷ solves a (typically linear) surrogate problem over a feasible set 𝒴(x). The oracle maximizes the objective κ(θ, y) parametrized by the scores θ. Importantly, θ does not have to represent “true” quantities such as expected demand or expected delay. It is simply a set of latent coefficients that the network learns to set so that the oracle returns high-quality decisions. This freedom allows COAML to reconcile the scalability of deterministic solvers with contextual stochasticity.

Why is this difficult? The solver at the end of the pipeline is piecewise constant. An argmax over a finite set does not move for slight changes in the parameters θ; it only jumps when θ crosses a boundary. Almost everywhere, standard backpropagation returns zero gradients. A large share of COAML research therefore consists of designing smooth surrogates that enable differentiability without destroying solver structure. Once this problem is solved, a second question appears: what if the decision is not static, but part of a long sequence, and the only signal we get is a scalar reward? This is where the recent method Structured Reinforcement Learning (SRL) enters the scene, and it is the core of this post (Hoppe et al., 2025).

The geometry of a discrete optimization layer

To see why differentiation is delicate, it helps to visualize what a combinatorial oracle really does. Assume, as is common in OR problems, that the surrogate problem is a linear maximization over a feasible set of discrete decisions. Any such problem can be written as 

where 𝒞 =conv(𝒴) is the convex hull of the feasible solution space – a polytope whose vertices are the decisions we are allowed to pick. Maximizing a linear objective over a polytope always returns a vertex. Figure 3 shows a low-dimensional sketch of this principle.

This figure explains both the problem and the solution. The oracle maps every point in the parameter space to one vertex: it is chosen when the oracle is called with that θ. The set of θ that return a given vertex y_i is the vertex's normal cone, and the collection of all these cones tiles the parameter space. Inside a cone, the output of the oracle does not change as θ varies, so the gradient of any loss that depends only on ŷ(θ) is zero. Across a cone boundary, the output jumps, so the gradient is undefined. Panel (b) visualizes a one-dimensional slice of the corresponding training loss – a staircase with flat treads.

The COAML toolbox contains two families of remedies. The first, entropic regularization, adds a strictly convex penalty on the simplex of probability distributions over vertices, which softens the argmax into a softmax-like distribution; the resulting Fenchel–Young loss is smooth and convex in θ, with a gradient equal to the difference between the softened prediction and the target decision (Blondel et al., 2020). The second, stochastic perturbation, adds Gaussian noise to θ before calling the oracle and averages over several calls; this replaces the step function by a smooth surrogate that can be differentiated by sampling (Berthet et al., 2020). Both are attractive because they require no bespoke solver – they reuse the fast, deterministic oracles that OR has spent decades perfecting (Dalle et al., 2022).

With static problems under control, one last piece of the puzzle remains: what about settings where decisions must be taken in sequence, and their consequences are only revealed through simulation?

Structured Reinforcement Learning

Many important operational problems are inherently dynamic. An ambulance dispatcher chooses where to park idle vehicles and adapts the plan as new calls come in. A ride-hailing platform rebalances cars across neighbourhoods as demand shifts. An inventory manager commits to shipments while demand materializes over weeks. In all these cases, the setting is a Markov decision process: a state x_t is observed, a decision y_t is taken, a new state x_t+1 and a cost c_t are revealed, and the whole horizon is tied together by a cumulative objective. The natural algorithmic framework for such problems is reinforcement learning (RL), in which policies are trained by interacting with a simulator rather than by minimizing a supervised loss.

Off-the-shelf RL algorithms such as Proximal Policy Optimization or Soft Actor-Critic, however, fit poorly. They assume that the policy emits a probability distribution over actions, but in combinatorial settings the action space is exponentially large: the set of routes through a city, the set of matchings between requests and vehicles, the set of schedules compatible with a timetable. Simply enumerating the actions at a state may be infeasible. Worse, naive relaxations tend to produce infeasible suggestions – a route that violates a time window, an assignment that double-books a vehicle – which then have to be repaired by expensive post-processing. Approaches like multi-agent RL can mitigate these problems, but at the cost of of unstable convergence and goal misalignment between agents (Hoppe et al., 2024).

Structured Reinforcement Learning (SRL), resolves this tension by replacing the stochastic policy with a COAML policy (Hoppe et al., 2025). The actor is exactly the differentiable architecture of Equation 1. A neural encoder 𝜑_w maps the state x to a score vector θ, and a combinatorial oracle returns the action y = ŷ(θ, x) = arg max_{y′∈𝒴(x)}⟨θ, y′⟩. Every action produced by the actor is therefore feasible by construction, regardless of how poorly trained the network is. This is a departure from ordinary RL, where feasibility is enforced through reward penalties or post-hoc projection.

The challenging problem is how to train such an actor. Because the CO-layer is piecewise constant in θ, naïve policy gradients provide no useful signal. SRL's key idea is to borrow the Fenchel–Young loss from supervised COAML and apply it inside an actor–critic loop. Figure 4 shows the pipeline.

At each update step, the actor first produces scores θ = φ_w(x). A handful of Gaussian perturbations η ∼ 𝒩(θ, σ) are drawn around θ, and each perturbed score vector is pushed through the CO-layer to produce a candidate action y'. Because perturbations of θ can land in different normal cones (Figure 3), the candidates genuinely differ from one another – the mechanism gives us structured exploration over the feasible polytope. A critic network Q_ψ(x, y') evaluates each candidate's long-term value, and a temperature-controlled softmax over the Q-values assigns each candidate a weight. Averaging the candidates using these weights produces a target action ȳ that lies inside the convex hull of feasible actions. Finally, the actor is updated by minimizing the Fenchel–Young loss L_Ω(θ; ȳ), which has smooth, informative gradients as introduced above. Figure 5 displays this update mechanism. The critic is updated in parallel by standard temporal-difference learning on transitions (x, y, r, x') collected in a replay buffer.

Three methodological moves in this construction are worth highlighting. First, SRL transplants the Fenchel–Young loss of supervised COAML into reinforcement learning, exploiting that, once you have a way to differentiate through a solver, there is no good reason to restrict it to settings with labelled targets. Second, SRL avoids a step that is usually prohibitive in multi-stage stochastic optimization: solving an anticipative problem with incomplete knowledge about future uncertainty. Instead, it uses the critic to score a small number of perturbed candidates and lets the softmax turn the scores into a smooth target. Third, SRL exploits a structural asymmetry that most industrial problems exhibit: even when finding an optimal action is computationally hard, evaluating a proposed action is cheap. SRL leans heavily on this asymmetry, repeatedly proposing plausible candidates and letting the critic tell it which ones look promising.

Benefits of SRL. Four concrete advantages emerge from this design. Actions are feasible by construction, which eliminates a large class of engineering workarounds that plague unstructured RL in industrial applications. Gradient variance is reduced because the Fenchel–Young loss targets a smooth interior point rather than a one-hot vertex, mitigating a common source of instability in actor–critic training. Exploration simply comes from the perturbation of θ, without the practitioner having to hand-design action-space noise. Finally, the construction inherits the mathematical link between Fenchel–Young updates, Bregman divergences, and mirror descent, enabling principled convergence analyses.

The trade-off is computational. Each actor update requires several calls to the CO-layer – one per perturbation – making wall-clock training time slower than vanilla actor–critic learning. In practice this is usually acceptable: the surrogate oracle inside the CO-layer is far cheaper than the anticipative problem one would have to solve for supervised learning, and the perturbation calls can be parallelized across workers trivially.

Where COAML and SRL sit in the decision-making landscape

It is useful to place COAML and SRL in context with the other approaches a practitioner might consider. A purely deterministic solver treats the uncertainty as a single point estimate; it is fast but brittle. Stochastic optimization explicitly integrates over the uncertainty via sampling; it is principled but computationally demanding, and scaling it to large combinatorial problems is an open struggle. Predict-then-optimize (PTO) combines a point forecast with a deterministic solver; it is the industry default but suffers from the loss-cost mismatch we highlighted in the opening. Smart PTO trains the forecast using a decision-focused surrogate such as the SPO+ loss (Elmachtoub & Grigas, 2022); this aligns prediction with decision quality but works only in settings where the cost function is linear in the uncertainty and the true cost vector is known. COAML extends this logic to genuinely non-linear cost structures and, with SRL, to multi-stage stochastic settings with implicit uncertainty. For broader surveys of the landscape, see Mandi et al. (2024) on decision-focused learning and Sadana et al. (2025) on contextual optimization.

The range of applications where COAML has already been demonstrated is extensive. On static problems, COAML pipelines have produced scalable heuristics for stochastic vehicle scheduling (including aircraft routing), single-machine scheduling, fixed-charge transportation, and two-stage stochastic network design (e.g., Parmentier, 2022; Parmentier and T'kindt, 2023). On contextual problems, they have been used for facility location, traffic equilibrium prediction, dynamic inventory routing, and resource allocation in security games (e.g., Jungel et al., 2024; Bouvier et al., 2025). On multi-stage problems, they have won the 2022 EURO-meets-NeurIPS vehicle routing competition and have been deployed for ride-hailing dispatch, autonomous mobility-on-demand rebalancing, and emergency ambulance redeployment (e.g., Baty et al., 2024; Jungel et al., 2025; Rautenstrauß and Schiffer, 2025). SRL specifically has shown strong results on stochastic vehicle scheduling, dynamic assortment, and shortest-path problems at scales where unstructured RL fails to converge (Hoppe et al., 2025).

Open challenges and outlook

Despite significant progress, several recurring challenges remain unresolved. First, gradient propagation through non-differentiable CO-layers remains difficult, often requiring perturbation-based methods that introduce bias or variance. Second, scalability is a central bottleneck: SRL requires repeated calls to CO-oracles during training, which can be computationally prohibitive in large-scale or highly combinatorial settings. Third, generalization under distributional shift, partial observability, and scarce data remains poorly understood; most current methods assume that training and deployment distributions coincide. Fourth, the lack of standard benchmarks and evaluation protocols makes it difficult to compare methods across studies, hindering reproducibility and cumulative progress. These challenges cut across paradigms and represent fundamental obstacles to the wider adoption of COAML and SRL.

COAML and SRL are still in their early stages, but their potential to transform decision-making under uncertainty is considerable. By uniting the traditions of OR and ML, they have the opportunity to produce algorithms which are both theoretically grounded and practically applicable. Future progress will require bridging learning paradigms, advancing architectures and losses, developing systematic benchmarks, and deepening theoretical understanding.

References

Léo Baty, Kai Jungel, Patrick S. Klein, Axel Parmentier, and Maximilian Schiffer. Combinatorial optimization-enriched machine learning to solve the dynamic vehicle routing problem with time windows. Transportation Science, 58(4):708–725, 2024. doi: 10.1287/trsc.2023.0107🔙

Quentin Berthet, Mathieu Blondel, Olivier Teboul, Marco Cuturi, Jean-Philippe Vert, and Francis Bach. Learning with differentiable perturbed optimizers. In Advances in Neural Information Processing Systems, volume 33, pages 9508–9519. Curran Associates, Inc., 2020.🔙

Mathieu Blondel, André F. T. Martins, and Vlad Niculae. Learning with Fenchel–Young losses. Journal of Machine Learning Research, 21(35):1–69, 2020🔙

Louis Bouvier, Thibault Prunet, Vincent Leclère, and Axel Parmentier. Primal–dual algorithm for contextual stochastic combinatorial optimization. arXiv preprint arXiv:2505.04757, 2025🔙

Guillaume Dalle, Léo Baty, Louis Bouvier, and Axel Parmentier. Learning with combinatorial optimization layers: A probabilistic approach. arXiv preprint arXiv:2207.13513, 2022🔙

Adam N. Elmachtoub, Paul Grigas. Smart “Predict, then Optimize”. Management Science 68(1):9-26, 2022. doi: 10.1287/mnsc.2020.3922🔙

Heiko Hoppe, Tobias Enders, Quentin Cappart, and Maximilian Schiffer. Global rewards in multi-agent deep reinforcement learning for autonomous mobility on demand systems. In Proceedings of the 6th Annual Learning for Dynamics & Control Conference (L4DC), volume 242 of Proceedings of Machine Learning Research, pages 260–272. PMLR, 2024🔙

Heiko Hoppe, Léo Baty, Louis Bouvier, Axel Parmentier, and Maximilian Schiffer. Structured reinforcement learning for combinatorial decision-making. In Advances in Neural Information Processing Systems, volume 38. Curran Associates, Inc., 2025🔙🔙🔙

Kai Jungel, Dario Paccagnan, Axel Parmentier, and Maximilian Schiffer. WardropNet: Traffic flow predictions via equilibrium-augmented learning. arXiv preprint arXiv:2410.06656, 2024🔙

Kai Jungel, Axel Parmentier, Maximilian Schiffer, and Thibaut Vidal. Learning-based online optimization for autonomous mobility-on-demand fleet control. INFORMS Journal on Computing, 2025. doi: 10.1287/ijoc.2024.0637 Online first.🔙

Jayanta Mandi, James Kotary, Senne Berden, Maxime Mulamba, Víctor Bucarey, Tias Guns, and Ferdinando Fioretto. Decision-focused learning: Foundations, state of the art, benchmark and future opportunities. Journal of Artificial Intelligence Research, 80:1623–1701, 2024. doi: 10.1613/jair.1.15320🔙

Axel Parmentier. Learning to approximate industrial problems by operations research classic problems. Operations Research, 70(1):606–623, 2022. doi: 10.1287/opre.2020.2094🔙

Axel Parmentier and Vincent T’kindt. Structured learning based heuristics to solve the single machine scheduling problem with release times and sum of completion times. European Journal of Operational Research, 305(3):1032–1041, 2023. doi: 10.1016/j.ejor.2022.06.020🔙

Maximiliane Rautenstrauß and Maximilian Schiffer. Optimization-augmented machine learning for vehicle operations in emergency medical services. arXiv preprint arXiv:2503.11848, 2025🔙

Utsav Sadana, Abhilash Chenreddy, Erick Delage, Alexandre Forel, Emma Frejinger, and Thibaut Vidal. A survey of contextual optimization methods for decision-making under uncertainty. European Journal of Operational Research, 320(2):271–289, 2025. doi: 10.1016/j.ejor.2024.03.020🔙

Maximilian Schiffer, Heiko Hoppe, Yue Su, Louis Bouvier, and Axel Parmentier. Combinatorial optimization augmented machine learning: Technical foundations, applications, and research frontiers. arXiv preprint arXiv:2601.10583, 2026🔙