Structured Reinforcement Learning for Combinatorial Decision-Making
Authors: Heiko Hoppe
Léo Baty
Louis Bouvier
Axel Parmentier
Maximilian Schiffer
Venue: NeurIPS 2025 poster ()
Keywords: deep reinforcement learning
combinatorial action spaces
structured learning
Primary area: reinforcement_learning

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.

Structured Reinforcement Learning
for Combinatorial Decision-Making
Heiko Hoppe'
Léo Baty² Louis Bouvier² Axel Parmentier
Maximilian Schiffer!
Technical University Munich "éooe des Ponts
(heiko hoppe,schifferz, schiffer)etum........ de (leo. baty, louis. bouvier, axel, peee...arrentieeeeepp...c
Abstract
Reinforcement learning (RI.) is increasingly applied to real-world problems involy- ing complex and structured decisions, such as routing, scheduling, and assortment planning. These settings challenge standard RL algorithms, which struggle scale, generalize, and exploit structure in the presence of combinatorial action spaces. We propose Structured Reinforcement Learning (SRL), novel actor-critic paradigm that embeds combinatorial optimization-lan work. We enable end-to-end learning of the actor via Fenchel- Young losses and provide a geometric interpretation of SRL as a primal-dus algorithm in the dual the moment polytope. Across six environments with exogenous and endogenous uncertainty, SRI. matches or surpasses the performance unstructured RI and imitation learning static tasks and improves over these baselines by up to 92% on dynamic problems, with improved stability and convergence speed
into the actor neural net-
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 real-world industrial problems, such as vehicle routing, inventory planning, machine scheduling, and assortment optimization [e.g.. Nazari et al.) 2018 Kool et al.) 2019 Hottung and Lierney, 2022]. Unlike traditional RL applications, these industrial problems often involve large-scale combinatorial decision makinn, which challenges classical RL algorithms [cf., Hildebrandt et al.) 2023). In particular, existing algorithms struggle with: 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 [cf., Yuan et al.) (022). From 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 (Combinatorial Markov Decision Process). We consider MDPs with states S, actions a E A(s) C (d)(s), rewards r, and transition probabilities P(s', 8, a) with next state s'. In combinatorial MDPs. A(s) the set of feasible solutions of a combinatorial problem. We denote its convex hull as the moment polytope C(s) == conv(A(ss) As in stochastic optimization [Bertsekas) and Shreve, [ we use a latent noise variable & E with probability p(E s, s.a). such that (s',r" rr) given (s.a, {) is deterministic. We distinguish exogenous noise, where the distribution of does not depend on a, and endogenous noises, where the distribution of E depends on
the transition to (s'
Our code is available httpppp//ggttbb..ooo////////stss
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Given unknown P(ss,r|s,0 we aim to find the reward meximiina policy
π E arg max Kg.P
Σ n'r
over [0, T, given a discount factor We further define Q-values, satisfying the Bellman equation
(=(,,, Ep (re] + 7 Ee
max Q" (5t+1. art1)
a6-1
using expectations with respect P(s', s.a).
The limitations of standard RL algorithms in solving such Combinatorial MDPs (C-MDPs) render them insufficient solve many industrial problems. To overcome these drawbacks, we propose Struc- tured 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 pecision-making over [e.g..Nowozzn
structured spaces, including structured prediction [e.g.. Nowozin and Lampert 2011), differentiable optimization layers [e.g.. (Amos and Kolter [017]. and hierarchical reinforcement learning [e.g.. Bacon et al., 2017]. 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 [e.g.. Liyanage and Shan-
thikumar 2005 Huber et al.) [209 and ceedict-and-optinne
algorithms [c.g.. Alonso-Mora et al. 2017 Bertsimas and Kallus, 2020J. 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 [cf., Enders al. 2023 In contrast, CO CO-augmented Machine integrate combinatorial optimization directly into model architectures, allowing end-to-end learning (arrmenter 2022 Dalle et al., 2022]. Here, the key challenge is to differentiate through the CO-layer. Existing approaches include problem-specific relaxation schemes [e.g.. Vlastelica al., 2020)] and more general strategies, e.g., using Fenchel-Ye Young losses [e.g.. Blondel et al. 2020 Berthet et al. 2020). The latter allow continuous training over discrete structures and are increasingly used for differentiating COAML-pippelines [e.g.. Dalle al.
Learning (COAML)-pipelingg
2022 In C-MDPs,
prior work either uses offline expert imitation [e.g.. Baty et al. [2224] J Jungel et al.
2024 or treats the
CO-layer as an action mask in unstructured RL ie.g..(Hppp al. 2024 Woywood al. 2025 The
former requires access to expert solutions, while the latter oiten leads to unstable gradients. Imitation approaches also suffer from insufficient exploration in multi-stage problems.
SRL builds on classical policy-gradieds algorithms, e.g.. REINFORCE, PPO, and SAC [cf., Williams 1992 Haarnoja al. 2018), which perform well in conventional MDPs but challenged by the size and structure of C-MDP action spaces [Hildebrandt et al.) 2023) Problem-specifie neural network designs often lack generalizability across applications and struggle in dynamic contexts [e.g..Bello et al.) 2017 Dai et al., 2017]. while neural improvement methods rely on existing initial solutions [c.g.. Yuan et al. 2022 Hottung and Tiemnyy 2022]. Value-based methods often assume decomposable critics [e.g.. Xu et al.) [018 Liang et al.) 2022], limiting applicability in structured domains. Alternative approaches transform task-specific Q-network into mixed-integer linear program, which potentially increases solution time and limits the range of usable network architectures [e.g.. Xu et al. 2023). SRL is also related to offline RL. which frequently relies on imitation learning [e.g., |Figueiredo Prudencio et al. 2024], but differs by operating online and updating from on- onlpolicy targets.
Contribution To address the challenges outlined above, we propose 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 train- ing of COAML-pipelines using only collected experience. SRL replaces the neural actor with a combinatorial policy defined by score-gent poore-genraatigg network and CO-layer. To enable end-to-end learning despite the non-differentiabiiiy of the CO-layer, SRL combines stochastic perturbation and Fenchel- Young losses to construct smooth actor updates, enabling stable policy improvement. We further provide geometric analysis that interprets SRI as a sampling-bas 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. SRI. 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 to 78% and unstructured deep reinforcement learning baselines (i.e.. PPO) by up to 92%, while exhibiting lower variance and faster convergence across all settings.
2 Methodology
In the following, we introduce Structured Reinforcement Learning, a novel actor-critic framework tailored to environments with combinatorial action spaces. The main rationale of SRL is the em- bedding of a CO-layer in the actor architecture, which turns the actor from plain neural network into a COAML-pipeline. This allows us to map high- sigh-dimensional states score vectors via neural networks, while leveraging combinatorial optimization to determine the best actions with respect to the score vectors. Establishing this algorithmic paradigm while ensuring end-to-end learning for the new actor requires additional changes, specifically i) identifying a loss function that allows to differentiate through the CO-layer when learning by experience, and ii) rethinking the policy evaluation scheme.
In the following, we first detail the foundations of the resulting new algorithmic paradigm. Afterward, we provide geometric analysis that formalizes our learning scheme, which can be interpreted as sampling-bass based primal-dual algorithm.
2.1 Structured Reinforcement Learning
Figure 1 sketches the elements of our SRL agent, which extends the standard actor-critic paradigm by integrating CO-layer into the actor, replacing the conventional neural network policy representation. The black elements illustrate the actor pipeline during inference: a neural network maps the current state s to score vector 6, which is then passed into the CO-layer f. This CO-layer selects a feasible action E A(s) by solving a combinatorial problem, ensuring that selected actions are both scalable in the dimension of A(s) and valid with respect the problem domain. The blue elements illustrate the architecture used during training: we sample perturbed versions of the score vector to generate candidate actions via the CO-layer. We then evaluate these actions using a critic network, and utilize softmax-base
aggregation choose target action à for the actor update. We train the actor end-to-end by minimizing a Fenchel-Young Young loss between 0 and à, which enables end-to-end backpropagation. The following details each of our algorithmic components.
Combinatorial Actor
Consider a C-MDP as detailed in Problem 1 where A(s) denotes the feasible action set in state s. Deep RL algorithms typically use neural networks to represent the policy distribution over the action space. In combinatorial settings, a neural network may struggle to encode distribution on the exponentially-Large action space A(s). To overcome this challenge, we adopt a CO-augmented Machine searning-piielling as the actor architecture. As illustrated in Figure I this architecture combines statistical model you with combinatorial optimizer f. The statistical model Pa. usually a neural network parameterized by weights w, observes contextual information
Actor x(s)
Statistical model PPw
Scores
O'-layer [0,
Action A(s)
Feuchel- Young loss
Target
La(O; ()
Gaussian \(0, + 7
Rackpropagation
State
CO-layer 8(
Actions
Critic R
Q-values
Softmax of (v,
Qsy(a',s)
Black: inference
Blue: training
Figure 1: Overview of the Structured Reinforcement Learning algorithm.
3

---

Fas
F
83
(1
03
012
F mi
04
Fus
Fos
Fon
055
Action polytope
Normal cone
Cone in dual space
Figure 2: Left: action polytope C(s) conv (A(s)). Middle: normal cone for which _(0, 8) = 01 right: normal cone Fas in dual space.
provided by the C-MDP state Using this information, the model estimates latent score vector with dimension d. The combinatorial optimizer uses as coefficients of a linear objective function and generates action by solving the CO problem
f(0, s)
argmax (fla)
&EA(s)
given problem-specifie constraints that define the feasible action set A(s). Formally, the resulting combinatorial actor reads (s), such that we define the respective actor policy as (- := (()((()),))) Intuitively, one interpret this policy Dirac distribution the output of f.
In the COAML-pipellnee, the statistical model fou encodes contextual information, which enables generalizing across states, capturing variable dependencies, and anticipating C-MDP dynamics. The CO-layer f enforces combinatorial feasibility, facilitates a structured exploration of the action space, and improves scalability by mapping score vectors 0 to potentially high-dimensional action spaces A(s). COAML-pipelines have been used successfully to address combinatorial problems using imitation learning, highlighting their suitability for C-MDPs [e.g.. Parmentier [202 Baty al. 2024]. For a detailed introduction to COAMI-pipelines and motivating example, we refer to Appendix(A]
End-to-end actor learning Training the actor parameters w using gradient-based methods poses significant challenges. The CO-layer f piecewise constant with respect to the action space, resulting in uninformative (i.e., zero) derivatives almost everywhere. Geometrically, this behavior can be understood by considering the convex hull of the action space, C(s) conv (s)). which forms polytope depicted in Figure [ The score vector 0 determines the direction of the objective function, and each vertex C(s) corresponds to normal cone, defined as the set all mapped to the same vertex by f. These cones partition the dual space of C(s), forming the normal fan of C(s). When 0 crosses cone boundary, the mapping f exhibits an abrupt change, assigning 0 to a different action, thereby illustrating the piecewise constant nature of f(0, s). Since f0) deterministically maps scores / to actions a, it can be viewed as an action post-processing step within the environment. Under this perspective, one may interpret 0 as the action space and parameterize distribution over 0 using Pu. enabling the use standard RL policy gradient methods via score-function estimators [Mohamed et all 2020). However, treating f as part of the environment effectively induces a piecewise constant and highly non- non-smooth reward function, which exacerbates gradient variance and leads to substantial difficulties in practice, e.g., by deteriorating or prohibiting convergence.
To address these limitations, we propose Structured Reinforcement Leurning, a primal-dual RL algorithm that employs Fenchel-Young losses to update the actor. Fenchel- Young losses define surrogate objective that is convex in the output of the statistical model and allows for smooth gradient propagation. Differentiating this surrogate objective reduces to solving convex optimization problem via stochastic gradient descent. We estimate these gradients using a pathwise estimator, which is known for its low variance [Blondel and Roulet 2024].
Following the workflow illustrated Figure we outline SRL in Algorithm [ After collecting experience and sampling transitions from the replay buffer, we perturb the score vector 0 using Gaussian distribution to generate set of perturbed vectors 1). pass each r) through the CO-layer to obtain candidate actions a', which are evaluated by the critic. We then compute softmax-weighted target action based on their Q-values. Finally, we update the actor by minimizing the Fenchel- Young loss between 0 and ã; and update the critic using standard temporal- -iffrree-difffrence errors.

---

Algorithm Structured Reinforcement Learning
Initialize actor with model (P,, critic 1/s and target critic 10 networks for episodes do
Generate trajectories, store and sample transitions j for j transitions do
Perturb 8) = Pw (w()) using Z ~ N(0,, sample m nh solve f(ns: for cach
Calculate target action ūj [softmax,, Quy (t..
Update actor using Lo (0;0 a)
P using a second perturbation
Update critic by one step of gradient descent using J(bba) = (Q (3), v)) end for end for
Originally proposed for imitation learning [Blondel et al. 2020) Berthet et al. 2020 the Fenchel- Young loss has become established loss function for the end-to-end training -iiplepspellnes [e.g.. Parmentier and T Kinddt 2023 Baty et al. 2024]. We adopt it in SRL since it is convex in the output of the statistical model 0 = Pou (s) and differentiable with respect to the latter, while leveraging the structure of the CO-layer f. The Fenchel-
loss (o(0; @) compares the difference between the objective values of the estimated action under the parameterization @ and the target action
Ln(O:ā)=
max OJ O"a A(s(s)
We aim to find statistical model fou that predicts to minimize the Fenchel- Young loss ming (a 2). Due the piecewise constant CO-layer f. the loss in this form is neither smooth or convex in 0. To address this problem, we introduce Gaussian perturbation Z ~ N(0,s) such that the loss reads
(0; a)
E max (0 + (0+Z)T (EEA(s))
TT O
Using an alternative definition, given regularization function Q 12d + R U {+oo} and its Fenchel conjugate 52*, the Penchel-Young loss (n @) generated by Q is defined over dom x dom as
Co(e: @) = S2" (0) + ((@) (8
sup
((0)a) 2(a)) ((0 s?(ā))
(3)
agdom((2)
For given 0 E dom()2"), we introduce the regularized prediction as sup (ddmm)) Fenchel- loss measures the non-optimality of dom(s?) as a solution of the regularized prediction problem. It is nonnegative and convex in 0. addition Q is proper, convex, and lower semi-continuoon La reaches zero if and only if is solution of the regularized prediction problem.
(0la) - M(a). The
The Fenchel- Fenchel-Young loss requires a target action which SRL estimates online without relying on offline expert demonstrations. As visualized in Figure 3 SRL explores the action space around the deterministic action a using a perturbation, and leverages the critic to compute softmax- softmax-weighted local target action a. To construct ā SRL perturbs the score vector 0 using a Gaussian distribution Z (0, 0b) with standard deviation ds and samples m perturbed scores 17. Each r) yields a candidate action a' = fπ,, which is evaluated by the critic v/.. We then compute
( 0
Ed' exp ! Quy (s,aa) E. exp ( (v,())))))
ā softmax
with temperature parameter 7, controlling the sharpness of the softmax. If we decrease r, â approaches the greedy action argmax, (Qua (s, a') d')). we increase т, approaches the uniform average 1 Ea. a'. Note that à E A(s) does not have to hold, as it is not executed in the environment, but only serves as a training signal for the Fenchel-Young loss.
The softmax-bast based estimator for à provides key benefits in structured action spaces. First, it promotes exploration by distributing credit across multiple actions. Second, it reduces critic overestimation bias via value averaging [cf.. van Hasselt 2010 Fujimoto et al.] [0118). Third, it avoids selecting edge actions, thereby enhancing stability and preventing premature convergence suboptimal policies.
To ensure sufficient exploration of the state space S, we introduce stochasticity into the forward pass during training: perturb the score vector 9 using Gaussian noise Z ~ N((, with exploration
5

---

02g
0g
04
perturb 04
(1)
minimuise
04
softmax
Ca(0:a)
Figure 3: Schematic representation of SRL update step: unperturbed action a (left), perturbed actions and target action (middle), Fenchel- Young loss (0; (right).
standard deviation o,, sample one perturbed vector y, and select an action a = (m) s). Overall, we use three Gaussian perturbations of 0, distinguished by their standard deviations: as to facilitate exploration of S in the forward pass, d to ensure exploration of the combinatorial action space A(s) during target action selection, and regularize the CO-layer f for the Fenchel-Young loss.
Critic architecture and stability SRL employs a critic network ths parameterized by weights B which estimates Q-values QT difference (TD) learning: given observed transitions (st, Oz, Ft. St+1), the critic minimizes the TD loss (Q (St, a4) - yt)², with target value y/ = 9t + + (st-1, 0t+1). As common in RL, we update the target network weights 3 slowly stabilize training, i.e., setting 3 +- 1/3 the end of each episode. To mitigate the critic's overestimation bias, which is especially prevalent in large combinatorial spaces, we adopt double Q-learning techniques in complicated environments [cf., van Fujimoto al. 2018), computing Q-values using the average of two critics.
(8, a) Qr (s, a). We update the critic using standard temporal-
Hasselt 2010
While SRL follows standard actor-critic architecture, combinatorial actions introduce unique challenges. Notably, SRI. does not require the Q-function to be decomposable in the same dimension as the score vector 6, unlike methods relying on linear or factored critics. This flexibility supports complex environments, e.g., industrial settings, but prevents direct optimization particular, computing argmax, Q (s, a) is generally infcasible for large combinatorial A(s), as requires solving a hard optimization problem for each evaluation during training. This complexity increase further precludes the direct use of primal-dual techniques [cf., [Bouvier et al. 2005 which require critic-dependent optimization over actions. Instead, SRL adopts sampling- based approach, which enables a tractable estimate of the best update direction, without requiring explicit optimization over the critic.
actions. In
2.2 Geometrical insights
We focus our geometrical discussion on the static case (T = 1) of contextual stochastic combinatorial optimization. While this may appear as a simplification compared the general multi-stage stage case (T' > 1), it serves two purposes. First, it allows us to establish direct connections to the well-studied class of contextual stochastic combinatorial optimization problems [Sadana et al.) [2025] and recent findings primal-dual optimization schemes in this context (Bouvier et al. 2025]. J. Second, when learning critic function via RI., the multi-stage decision problem effectively reduces to a single-stage problem with respect to the critic, since the critic approximates the expected cumulative return from any given state or state-action pair. Studying the static case thus not only clarifies the structure of our problem but also aligns with how value functions typically learned and analyzed.
In this setting, we introduce latent noise variable [Bertsekas and Shreve, 1996 E E with conditional distribution P(E s, a), such that the transition to (s', r)) given (s, {) is deterministic. We distinguish between exogenous noise, where the distribution of & is independent of the action a, and endogenous noise, where p({ s, a) explicitly depends on The objective of finding an optimal policy can then be formulated as
E argmaxX,,.ao [r(s, a,
(5)
In this context, [Bouvier et al. 2025 introduced a primal-dual algorithm for empirical risk mini-
mization, making connections with mirror descent ([Nemirovsky et al.) 1983 Bubeck 2015). This algorithm has nice theoretical and practical properties. However, it relies on the following: i) A
combinatorial optimizer to solve A(x, (9la) for any 0 E ds)) ii) A reward based ogenous noise variable &. This random variable is not observed when choosing the action A(s).

---

distribution simplex A the dual of this score space, and we can use Q2 to create mappings between them. More precisely, a policy maps state S to distribution over the corresponding combinatorial action set E A-A(e) To define such policies, we map state to direction but posteriori. iii) A combinatorial optimizer to solve m²X r(s, a, + (fla) when & is observed.
In an RI. setting, point i) typically holds, but points ii) and iii) do not stand. Indeed, the transition probability IP is general, and the noise may be endogenous and not observed at all. Besides, the reward function is typically a black-box. One could think of replacing the black-bor bbo objective function of Equation (5) by a learned critic max, E,, [2 (s, a)]. However, in combinatorial optimization, the non-linearity of the critic function makes its optimization with respect to a intractable. The key idea of Algorithm I to sample few atoms (az)ie[m). and compute an expectation (softmax) involving critic function Qu In Proposition 2 bebloo, we highlight that in the static case, and with fixed critic, this approach can be seen as a primal-dual algorithm, leveraging an additional sampling step. We show that it leads to tractable updates in our RL setting. To formalize this, we need to introduce a few definitions and background on optimization over the distribution simplex.
Policies as solutions of regularized optimization over the distribution simplex For given state 8 E S, let A(*) be the probability simplex over A(s). We recall that C(s) is the convex hull of the action space, also called moment polytope. Let A(s) (d)aE.A(s) be the wide matrix having one column per action. We introduce 52 {2 A - R U {+00) regularization function, [Rockafellar 1970 From this regularization over the simplex, we define a regularization over the moment polytope C(s) as follows. Let ja E C(s), Po(e) (J)) == min A (q). Every function c(-) on the combinatorial (exponentially large but finite) space A(s) can be seen long vector (c(a)) E RAA()), The
such that its restriction to the affine hull of A+)) is Legendre-tyye
vector (s); then lift to the score space "o A(s) a ((0la)) A()) and finally distribution q (o) (70). Our regularized actor policy parameterized by w is defined
AER 4(4)
(-Is) argmax gEad(e)
(A(s)
Pw
9))
= V22a (A(s) (w((s).
(6)
In Equation (6 we use the results of convex duality to write the argmax as gradient of the Fenchel conjugate (A4())) The learning problem is to find the w that maximizes F...... [r(s, a, E). In practice, during inference, we do not regularize (see Section 2.1 thus obtaining a Dirac policy.
sampling-baseer primal-dual algorithm for the actor update We consider fixed state S leading to a fixed action space A, and thus drop the latter from the notation of spaces and regularization functions, and omit the neural network from the policy defined in Equation (6). Given fixed critic
function Qws we introduce the score vector 7 = (Qua (a)) ae E R.A. Bouvier et al. 22025 introduce the following algorithm and show its convergence in restricted setting.
((++1) AV (AT)0) 770) +
1
(7a)
@1++1) E (-11)
(7b)
Here, Ω* is the Fenchel-conjugate of Ω. VΩ the gradient of Ω², and 82 the sub-differential of Ω.
The following proposition, proved in Appendix B shows that the static version of Algorithm can be seen variant of the primal-dual algorithm presented in Bouvier et al. 2025], enhancing it with an additional sampling step.

---

Proposition 2. The actor update in the static version of Algorithm can be written as
(a
1++ 2)
Ne(m) rid. V
(AT (AT(0)))
(8a)
(1- 5) 1 m
m Σ (
Qm
(8b)
(1- E 022 (92 (1tt))).
Ym
(8c)
((42) AVD's (1 (0+
-18):
(8d)
g(++2 E @llec(ulltt))..
(8e)
where da is the Dirac distribution on St is the negentropy, and Ω2 is the conjugate of the sparse perturbation, both detailed in Appendix Since 112+ is sparse by design, discuss the definition of gradients and sub- gradiendsents at the (relative) boundary of the domains in Appendix B
In Equations 18) for convenience in the implementation, we involve two distinct regularization
functions on the distribution simplex AA, detailed in Appendix B The main difference between Equations 7 and Equations (8) is the sampling step for the primal update. Recall that involving the critic in Equation 77) may be intractable. Indeed, the critic function may be highly nonlinear, and the resulting nonlinear combinatorial optimization problem may be intractable. Instead, Equation (8) based on a sampling step, which only requires m evaluations of the critic, which is tractable even when optimizing it with respect
E A(s)) is not. In both primal-dual algorithms, the dual update (of 6) is equivalent to solving a convex optimization problem, precisely minimizing a Fenchel- Young loss generated by Ωe. It is very convenient in practice, since the weights of actor policy be updated via stochastic gradient descent, although it relies on piecewise constant CO-layer f-
3 Numerical studies
Studied environments We evaluate SRL across six environments that reflect industrial applications with large combinatorial action spaces. Enpeeniix[deeerrbess the experimental setup, and Appendix D details the environments. We first consider three static environments common industrial benchmarks
from Dalle et al. [2022]- namely, a Warcraft Shortest Paths Problem, Single Machine Scheduling Problem, and a Stochastic Vehicle Scheduling Problem. As discussed in Appendix E SRL matches the performance of SIL, while relying solely on access to a (black-box cost function and without requiring the expert knowledge necessary for SIL. These results underline the versatility and broader potential of SRL, even though we designed it primarily for dynamic settings. We now discuss our findings for the dynamic environments in more detail.
The dynamic enviromments model online decision-making in C-MDPs. We consider: i) a Dynamic Vehicle Scheduling Problem (DVSP), based the Dynamic Vehicle Routing Problem introduced by Kool et al. [2022). [Baty et al. [204]]. This problem with exogenous uncertainty requires serving spatio-temporally distributed requests that are revealed over time. The goal is to find cost-minimizing routes while fulfilling all requests. ii) A Dynamic Assortment Problem (DAP), adapted from Dulac- Arnold et all (2016) ancChen et al. (2020). This problem with endogenous uncertainty involves selecting item assortments that are shown to customers, whose choices follow a multinomial logit model. Item features evolve based on past decisions, the goal is overall revenue maximization. iii) Gridworld Shortest Paths Problem (GSPP), inspired by gridworld and robotic control tasks [Chandak] atal, 2019 Zhang et al.) 2020). This problem with endogenous uncertainty requires the agent find cost-minimizing paths to targets, which move to new locations when being reached. The costs of paths are influenced by prior paths.
Experimental setup We compare SRL against two baselines: SIL, structured imitation learning approach, and Proximal Policy Optimization (PPO). an unstructured RL algorithm. All algorithms use identical COAML-pipelines; SRL and PPO also share the same critic architectures to ensure fair comparison. We select SIL due to its methodological proximity to SRL and its strong performance in combinatorial settings [Baty et al. 2024,] Jungel et al. 2024]. We include PPO for its stability and compatibility with our pipeline architecture [Schulman et al. 2017). Alternatives such as Soft Actor-Critis would require substantial modifications to the actor and critic architectures, as would
8

---

neural CO-methode [e.g..Beell et al. 2017 and Q-value-based optimization [e.g., Xu et al. 2025] To keep this analysis concise, we concentrate on comparing COAML-iipelines using different learning paradigms and leave an in-depth comparison of architectures to future work. As performance references, we include two additional baselines: an expert policy and a greedy policy. the static DVSP, the expert has access to the complete problem instance and thus represents the offline optimum. In contrast, the dynamic DAP and GSPP, traceability constraints limit information access, and the expert corresponds to the best possible online policy, given the sequential nature of the decision process. We train all algorithms using the same number of episodes, employing enviroument-specific train/validdationneestt splits. We tune hyperparameters per algorithm and environment, using the PPO-optimized episode numbers consistently across methods. Each algorithm retrained using ten random seeds. Appendix C provides further details the experimental setup and baselines.
Numerical results We present results for the dynamic environments in Figure 4 and Figure 5 We display the performance of final models on the train and test-datasets to measure algorithmic performance, and the development of validation rewards during training to highlight convergence behavior. While SRL performs comparably to SIL in the DVSP, it outperforms SIL in the DAP by 8% and in the GSPP by 78%, even surpassing the online optimum by 79% in the latter. In the DAP, the online optimum remains above the performance of SRL and SIL. These results highlight two key limitations of imitation learning: i) its performance is bounded by that of the expert policy; and ii) it lacks exploration to learn policies that enable escape from suboptimal states. In contrast, PPO consistently underperforms across environments, struggling to reach greedy policies SRL outperforms it by 16% in the DVSP, 77% in the DAP, and 92% in the GSPP. This poor performance highlights the challenges faced by unstructured RI. combinatorial action spaces. Overall, these performance gains show the superiority of SRL over SIL and PPO.
We observe notable differences in convergence speed. PPO converges slowest, requiring approxi- mately 200 episodes in the DVSP and 160 in the GSPP to reach a performance plateau. In contrast, SRL and SIL converge at similar rates the DVSP, while SIL converges approximately 150 episodes earlier in the DAP and 10 episodes earlier in the GSPP. This delay for SRL is expected, as it learns purely from interaction, without access to expert demonstrations.
Stability metrics in Table further explain these trends. PPO shows the highest variance across all environments up 80x higher than SRI. and 40x higher than SIL reflecting known limitations [e.g.,[Enders
of unstructured RI. in combinatorial settings [e.g.. [Enders et al. 2023 Hoppe et al. 2024]. In contrast, SRL and SIL exhibit consistently low variance, underscoring the robustness of structured approaches.
Discussion This robustness comes at a computational cost. SRL requires about 30 minutes of training per environment, compared to shorter runtimes for SIL and PPO. The difference arises from CO-layer usage: PPO invokes it only twice per update, versus 20x in SIL and up to 61 in SRL. Runtime also varies with CO-layer complexity e.g., GSPP has simple layer, leading to similar runtimes, while the more complex layer in DVSP increases SRLs runtime. The DAP runtime is further impacted by expensive simulation and the use of two Q-networks. Although early stopping could mitigate this, the findings highlight a core limitation: SRLs computational cost scales with CO-layer complexity.
DVSP
train
test
Arreely (%)
10
-28
rew
-30
-32
SIL PPO SRL
34
-10
-36
SIL
PPO
SRL
expert
SIL
PPO
SRI
apprtt
100
200
300
400
training episode
Figure 4: DVSP results. Left: final train and fest-performance compared to greedy (Agreddy); right: validation performance during training; averaged over 10 random model initializations.

---

DAP
GSPP
train
test
train
test
1000-
1000
1000
1000
2000y (%)
100)
100
(%)
100
100
10
10-
10
0-
-10
10
10
1100
100
1000
100
SIL
PPO
SRL
expert
SiL
PPO
SRL
expert
SI
PPO
SRL
expert
SIl
PPO
SRL
expert
val. rew. (10')
50
rew. (10?)
-20
40
660
30-
SIL PPO
-80
SIL
PPO
20
SRI.
-100
SRLL
100
200
200
training episode
training episode
Figure 5: DAP and GSPP results. Left: final train and test-performance compared to greedy (A (Agrodyy); right: validation performance during training; averaged over 10 random model initializations.
Table I:
Standard deviation of validation rewards during training, final testing rewards over 10
random model initializations, and training time of algorithms in the DVSP, DAP and GSPP.
DVSP
DAP
GSPP
Algorithm
train
test
time
train
test
time
train
test
time
SIL
0.3
0.4
12m
0.8
11.9
3m
39.3
1.1
11m
PPO
5.8
5.6
3m
5.4
13.5
5m
105.8
47.0
10m
SRL
0.3
0.3
31m
1.8
1.9
31m
72.1
0.6
34m
Overall, the observations for our dynamic experiments align with our static experiments (Appendix E SRL consistently matches SIL in performance and convergence, while PPO underperforms across all metries. Runtimes follow the same pattern, increasing with CO-layer complexity.
In summary, our results yield three takeaways for real-world deployments: i) unstructured RL lacks the stability required for practical use. SIL is limited settings with simple dynamics and access to expert demonstrations. iii) Given the expected model and layer complexity in real-world settings, SRL offers scalable and effective alternative solution approach at the price of (reasonable) computational overhead when comparing it to SIL.
4 Conclusion
In this paper, we address combinatorial MDPs (C-MDPs), which present substantial challenges to current RI algorithms, despite being common in many industrial applications. Utilizing the framework of COAML-pipelines, we propose Structured Reinforcement Learning (SRL). a primal- dual algorithm using Fenchel-Yone Young losses train COAML-pipeling in end-to-end fashion, thereby learning policies for C-MDPs using collected experience only. We compare SRL to Structured Imitation Learning (SIL) and unstructured RL in three static and three dynamic environments, representing typical industrial problem settings with combinatorial action spaces. The performance of SRL is competitive to SIL in the static environments and up 78% better in the dynamic environments. SRL consistently outperforms unstructured RL by up to 92%, additionally being more stable and converging quicker, the cost of higher computational effort.
Acknowledgments and Disclosure of Funding
We thank the BAIS research group at TUM for valuable comments and discussions. The work of Heiko Hoppe was supported by the Mumich Data Science Institute with Linde/MDSI PhD Fellowship.
10

---

References
Javier Alonso-Mora, Alex Wallar, and Daniela Rus. Predictive routing for autonomous mobility- on-demand systems with ride-sharing. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 3583-3590, September 2017. doi: 10.1 10.1109//ROS.00 2010 7.82262033
Brandon Amos and J. Zico Kolter. OptNet: Differentiable Optimization as a Layer in Neural Networks. In Proceedings of Machine Learning Research, volume 70, pages 136-145, 2017.
Pierre-Luc Bacon, Jean Harb, and Doina Precup. The Option-Critic Architecture. In Proceedings of the Thirty- Firrst AAAI Conference on Artificial Intelligence, volume 31, February 2017. doi: 10.1609/aaai. 111.10916.....
Léo Baty, Kai Jungel, Patrick S. Klein, Axel Parmentier, and Maximilian Schiffer. Combinatorial Optimization Optimization-Enrichedd Machine Learning to Solve the Dynamic Vehicle Routing Problem with Time Windows. Transportation Science, 58(4):708 702, July 2024. ISSN 0041-1655, 1526-5447. doi: 10. 10.1287/sse.2223.0107
Irwan Bello, Hieu Pham, Quoe V. Le, Mohammad Norouzi, and Samy Bengio. Neural Combi- natorial Optimization with Reinforcement Learning. In International Conference Learning Representations 2017 (ICLR)- - Workshop Track, 2017.
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 33 (NeurIPS 2020), 2020.
Dimitri Bertsekas and Steven F. Shreve. Stochastic Optimal Control: The Discrete-Tine Case. Athena Scientific, December 1996. ISBN 978-1-886529-03-8
Dimitris Bertsimas and Nathan Kallus. From Predictive Prescriptive Analytics. Management Science, 66(3):1025-1044, March 2020. ISSN 0025-1909, 1526-5501. 3253.
doi: 10. 10.1287/mns..201 8.
Mathieu Blondel and Vincent Roulet. The Elements of Differentiable Programming, July 2024.
Mathieu Blondel, André F.T. Martins, and Vlad Niculae. Learning with Fenchel- Young Losses Journal of Machine Learning Research, 21(35): 2020.
Louis Bouvier, Thibault Prunet, Vincent Leclère, and Axel Parmentier. Primal-dual algorithm for contextual stochastic combinatorial optimization, May 2025.
Sébastien Bubeck. Convex Optimization: Algorithms and Complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-33 -357,, November 2015. ISSN 1935-8237, 1935-8245. doi:
10.1561/22000000500.
Yash Chandak, Georgios Theocharous, James Kostas, Scott Jordan, and Philip Thomas. Learning Action Representations for Reinforcement Learning. In Proceedings of Machine Learning Research, volume 97, pages 941 19500 2019.
Xi Chen, Yining Wang, and Yuan Zhou. Dynamic Assortment Optimization with Changing Contextual Information. Journal of Machine Learning Research, 21(216):1-44, 2020.
Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning Combinatorial Optimization Algorithms over Graphs. Advances in Neural Information Processing Systems 31 (NIPS 2017), volume 31. Curran Associates, Inc., 2017.
Guillaume Dalle, Léo Baty, Louis Bouvier, and Axel Parmentier. Learning with Combinatorial Optimization Layers: A Probabilistic Approach, December 2022.
Edsger Wybe Dijkstra. A Note on Two Problems Connexion with Graphs. Numerische Mathematik, 1:269- 2716 1959.
Gabriel Dulac-Arnoid, Richard Evans, Hado van Hasselt, Peter Sunehag, Timothy Lillicrap. Jonathan Hunt, Timothy Mann, Theophane Weber, Thomas Degris, and Ben Coppin. Deep Reinforcement Learning in Large Discrete Action Spaces, April 2016.

---

Tobias Enders, James Harrison, Marco Pavone, and Maximilian Schiffer. Hybrid Multi- Deep Reinforcement Learning for Autonomous Mobility on Demand Systems. In Proceedings of Machine Learning Research, volume 211, pages 1284-1296. PMLR, June 2023.
Rafael Figueiredo Prudencio, Marcos R. O. A. Maximo, and Esther Luna Colombini. A Survey on Offline Reinforcement Learning: Taxonomy, Review, and Open Problems. IEEE Transactions on Neural Networks and Learning Systems, 15237100277- August 2024, ISSN 2162-237X, 2162-2388. doi: 10.1 10109//NN.S.2023....
Scott Fujimoto, Herke Hoof, and David Meger. Addressing Function Approximation Error Actor- Critic Methods. In Proceedings of Machine Learning Research, volume 80, pages 1587-1596, 2018.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft Actor- Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor. In Proceedings of Machine Learning Research, volume 80, pages 1861-1870, 2018.
Tuomas Haarmoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Ku- mar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, and Sergey Levine. Soft Actor-Critic Algorithms and Applications, January 2019.
Florentin D. Hildebrandt, Barrett W. Thomas, and Marlin W. Ulmer. Opportunities for reinforcement learning in stochastic dynamic vehicle routing. Computers Operations Research, 150:106071, February 2023. ISSN 0305-0548. doi: .0016,..co:202221100071
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 Machine Learning Research, volume 242, pages 260-272. PMLR, July 2024.
André Hottung and Kevin Tierney. Neural large neighborhood search for routing problems. Artificial Intelligence, 103786,,,, December 2022. ISSN 00043702, doi: a..1016...rtint.2222. 202...037228
Jakob Huber, Sebastian Müller, Moritz Fleischmann, and Heiner Stuckenschmidt. A data-driven newsvendor problem: From data to decision. European Journal of Operational Research, 278(3): 904-915, November 2019. ISSN 03772217. doi: 10.1016fj.eoor2219..44.. 204.04..33.
Kai Jungel, Axel Parmentier, Maximilian Schiffer, and Thibaut Vidal. Learning based Online Optimization for Autonomous Mobillty-on-Demand Fleet Control, February 2024.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, Learn to Solve Routing Problems! In International Conference Learning Representations 2019 (ICLR), 2019.
Wouter Kool, Laurens Bliek, Danilo Numeroso, Yingqian Zhang, Tom Catshoek, Kevin Tierney, Thibaut Vidal, and Joaquim Gromicho. The EURO Meets NeurIPS 2022 Vehicle Routing Compe- tition. In Proceedings of Machine Learning Research, volume 220, pages 25-49, 2022.
Enming Liang, Kexin Wen, William H. K. Lam, Agachai Sumalee, and Renxin Zhong. An Integrated Reinforcement Learning and Centralized Programming Approach for Online Taxi Dispatching. IEEE Transactions on Neural Networks and Learning Systems, 4344-447424 September 2022.
ISSN 2162-237X, 2162-2388. doi: 10. 10.1109/TNNL.... 2021.30011111 33060187
Liwan H. Liyanage and J. J.orge Shanthikumar. A practical inventory control policy using operational statistics. Operations Research Letters, 33(4):341-348 July 2005. ISSN 01676377. doi: 1011016/
jorr.2004.08.003.
Shakir Mohamed, Mihaela Rosca, Michael Figurnov, and Andriy Mnih. Monte Carlo Gradient Estimation in Machine Learning. Journal of Machine Learning Research, 21(132):1 2020.
ISSN 1533-7928.
MehammadReza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takac. Reinforcement Learning for Solving the Vehicle Routing Problem. In Advances in Neural Information Processing Systems 32 (NIPS 2018), 2018.
12

---

A.S. Nemirovsky, D.B. Yudin, and E.R. Dawson. Wiley- indersintereeeencc series in discrete mathematics, 1983.
Sebastian Nowozin and Christoph H. Lampert. Structured Learning and Prediction in Computer Vision. Foundations and Trends@ in Computer Graphics and Vision, 6(3-4):185-365, 2011. ISSN 1572-2740, 1572-2759. doi: 10. 00.151/0600000033.
Axel Parmentier. Learning to Approximate Industrial Problems by Operations Research Classic Problems. Operations Research, 70(1):606-622 January 2022. ISSN 0030-364X. 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, March 2023. ISSN 0377-2217. doi: 10.1016/j.ejor. 0022.06.040.
Ralph Tyrell Rockafellar. Convex Analysis. Princeton University Press, Princeton, 1970. ISBN 978-1-4008-7311-3, doi: 1111111111977110007777
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, January 2025. doi: 10. 10.1016/j.ejor. 2024.03.020.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal Policy Optimization Algorithms, August 2017.
Lei Shang. Vincent ('Kindt, and Federico Della Croce. Branch Memorize exact algorithms for sequencing problems: Efficient embedding of memorization into search trees. Computers & Operations Research, 128:105171, 2021.
Hado van Hasselt. Double Q-learning. Advances in Neural Information Processing Systems 23 (NIPS 2010), 2010.
Marin Vlastelica, Anselm Paulus, Vít Musil, Georg Martius, and Michal Rolínek. Differentiation of Blackbox Combinatorial Solvers. In International Conference on Learning Representations 2020 (ICLR), 2020.
Ronald Williams, Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning, 8(3-4):229-256, May 1992. ISSN 0885-6125, 1573-0565. doi: 10.1007/BF00992266.
Zeno Woywood, Jasper Wiltfang, Julius Luy, Tobias Enders, and Maximilian Schiffer. Multi-Agent Soft Actor-Critic with Coordinated Loss for Autonomous Sobilitt-onn-eemaaee Fleet Control, In Proceedings of the 19th Learning and Intelligent Optimization Conference, 2025.
Lily Xu, Bryan Wilder, Elias B. Khalil, and Milind Tambe. Reinforcement learning with combinatorial actions for coupled restless bandits. In International Conference on Learning Representations 2025 (ICLR), March 2025. doi: 104445550arxxx.2553.01999
Zhe Xu, Zhixin Li, Qingwen Guan, Dingshui Zhang, Qiang Li, Junxiao Nan, Chunyang Liu, Wei Bian, and Jieping Ye. Large-Scale Order Dispatch in On-Demand Ride-Hailing Platforms: A Learning and Planning Approach. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 905-913, London United Kingdom, July 2018. ACM. ISBN 978- 978-1-4503-5552-44 doi:
Enpeng Yuan, Wenbo Chen, and Pascal Van Hentenryck. Reinforcement Learning from Optimiza- tion Proxy for Ride-Hailing Vehicle Relocation. Journal of Artificial Intelligence Research, 75: 985-1002, November 2022. ISSN 1076-9757. doi: (0.1613/jair.. 1.
Tianren Zhang, Shangqi Guo, Tian Tan, Xiaolin Hu, and Feng Chen. Generating Adjacency- Constrained Subgoals in Hierarchical Reinforcement Learning. In Advances in Neural Information Processing Systems 33 (NeurIPS 2020), 2020.
13

---

A Combinatorial Optimization-aggmenti Machine Learning pipelines
In C-MDP, we are usually confronted with high-dimensional state space S and a high-dimensional and combinatorial action space A(s). Processing the former requires architecture capable of generalizing well across states and inferring information from contextual information. Neural networks, or generally statistical models, are known to have these properties, which rule-based decision systems or combinatorial optimization methods commonly lack. In contrast, addressing combinatorial action spaces is challenging for statistical models: Using traditional approaches, every feasible action would have to correspond to one output node of the neural network, which then estimates probability of choosing that action given the state. Such network design is already challenging due to the state-dependent action space A(s), and furthermore impractical due to the large dimensionality of A(s). While the use of problem-specific neural networks of multi-agent approaches is possible, it is far easier to employ a combinatorial optimization to select feasible action. Optimization methods have three advantages for this setting: i) they ensure feasibility of the selected action; ii) they scale to nigh-dimensional action spaces far better than plain neural network architectures; and iii) they naturally explore the action space by searching for an optimal solution iteratively.
Since we have established methods for handling both high-dimensional state spaces and high- dimensional, combinatorial action spaces, we can integrate these methods to leverage their combined strengths. This is the core idea behind CO-augmented Machine cearning-pipelingg In such pipelines, a statistical model Par, typically implemented as a neural network with parameters w, encodes the state s to estimate a score vector 0 (s). A combinatorial optimization solver then uses these scores as coefficients in a linear objective function to compute an action by solving the following combinatorial optimization:
f(0, 8)
argmax (0, a).
aEA(ss
Through this integration, f effectively becomes part of the actor model, commonly referred to as the CO-layer f. Importantly, the score vector 0 is latent, i.e., it is not observed directly, nor are its true values typically known. When training a COAML-pipeling in an end-to-end fashion, we rely solely on observed outcomes, without explicit supervision on O. The resulting policy of such pipeline can be formalized as (-Is) = ((())()))))) representing a Dirac distribution centered on the action output by f.
As a motivating example, consider the Warcraft Shortest Paths Problem |Vastelica et al. 2020). illustrated in Figure 6 and detailed in Appendix D In this setting, the state is given by a map image with dimensions 96 x 96 3 pixels. The task is to find the cost-minimizing path from the top-left to the bottom-right corner of the map, which corresponds to the action a. The path cost is determined by the terrain the agent traverses, with terrain types encoded by specific color codes. To solve this task, the state must first be encoded into a structured representation. We employ convolutional neural network to estimate scores for each cell in a 12 x 12 grid. These scores are then used by Dijkstras algorithm to compute the path that minimizes the cumulative cell costs. Notably, neither the convolutional network nor Dijkstras algorithm alone can solve the raw WSPP map image. However, the COAML-pipellnee efficiently learns to find cost-minimal paths through end-to-end training, combining the strengths of both components.
E
Map image:
Conv. Neur, Net. ((s)
Cell scores:
Dijkstra's algor. f(0,s)
Path: a
Figure 6: COAML-pipeline for the Warcraft Shortest Paths Problem: a convolutional neural network estimates cell scores based on image pixels. The CO-layer applies Dijkstra's algorithm the scores to create a path between the top left and the bottom right corner.
14

---

B Proofs
In Algorithm| I we use two different regularization functions from the literature on the distribution simplex A-, We start by introducing these regularizations. The literature considers (sub)gradients of these functions only in the (relative) interior of the probability simplex. In order to be able to work with sampled distributions, we extend them to the boundary of the simplex. We can then prove Proposition 2
B.1
Two regularizations: negentropy and sparse perturbation.
The first regularization the negentropy
[Blondel et al. 2020
aa
(1)
Σ Ya log(1a) + Ta4 (g),
aEA
where TA is the characteristic function of the set A leading to the distribution
(7) (mmm=A aEA
)aEA
where
Aa(t) = log Σ
exp(7a))
(9)
a'EA
The second is the Fenchel conjugate of the sparse perturbation 22,4 = F with
Bouvier et
2025
(7,(77) = EEz[maxx Ta + +Z a] = []]=>[[nng max (7 + EA TTTgl 9EA
aEA
where Z Rd is random variable, typically standard Gaussian. The resulting distribution is
( = V = EE (argmax(1 + eA e)T22)To T)Tg)
(10)
Recall that the negentropy can be expressed as a variant of the conjugate of the sparse perturbation, when we take Z distributed according Gumbel law.
B.2 Extension the boundary
The expectation in the right-hand side of Equation (TO) naturally extends VΩ in (-o(-))
Indeed, for any 7 E (R (-o0)) and irrespective of the perturbation Z E R², any action satisfying 7a = -o will never appear in the argmax. This observation allows us formally define the effective support of y as Å(7) = {a E A 7a -00], we get
0. VΩ Am (P)a: for a E Å(7),
for E A A(()),
(7
(11)
where (R())) is the vector of finite components of y, and VΩ2 Am (f) the component indexed
by of the vector VΩ* A A (9) which belongs to A(r)) In the other way round, we extend 0 the relative boundary of the simplex A as follows. Let E A be sparse distribution (with some
null components). In a similar way, we introduce the set A(g) {a A > 0}. and define
f -o0 Ha, E an a
for E A \ A(q) for E Å(g).
02s(1) 97=
(12)
where á E A(o) is the sparse distribution seen as a dense distribution in the distribution simplex corresponding to its support.
15

---

B.3 Proof of Proposition 2
Proof of Proposition We go through the steps of Equations and show that we indeed recover the actor update of Algorithm
For step Baj, let g(t) be given vector in R.d the distribution we sample from involves the gradient of the conjugate of the sparse perturbation
V (AT)O) Ez argmax((A g(t) +AA Zla] EEz argmax(((( ++Z)* a) aEA))))
0EA4
4EA
Note that the argmax in the right-hand side is almost surely Dirac because + (g(t) =Z) TTZTaaa is almost surely injective. Since the argmax returns a Dirac almost surely, we can equivalently rewrite the expectation as a probability for A:
V2 (A = E2 argmaax gEAt
T awee)llll))))
= Pz arrmaa a'EA
+ = =
Therefore, (a: (1+2)
computations above, the step 8a of sampling )igim] rid. Vl (ATO )(t)) is equivalent to sampling (Z)) and computing for (1+
using
the
each 0g
a. (0 + eZ,) a. This is precisely the first step in the actor update in
Algorithm
8b is explicit. The (empirical) sparse distribution (f+ = - ò (++b) lies the (relative) boundary of the simplex, as it assigns zero probability to actions not selected among the samples. For each in A, let kg denote the number of samples such that d;
Step
((+))
In step (8c), we use the negentropy regularization function Ωa over the distribution simplex A (e+t)
((+b)) b)) is such that there exists a E IR, such that
Using the extension defined above, Ti for a A.
E &NNA (4m
(+++) (7m
1 73) =a In(aa + (a)
7
where In(0) is taken equal to -00
In step 8d using again the extension of VS2 in (RU normalization constant Zm,9 EoEA exp (In(k:.) + 4: (a)).
Equation (9. and defining the
A + (a)
(((1)) AV22
(1++) (m + 73) = Σ
softmax EE m
Quy (ea(((tttt
Zm,
aEAA
We thus recover the target action à defined by Equation
Last, step (8e) can be written using Fenchel duality results [Blondel et al. 2020
((++1) E B.R (00,.c( = g((+1) E argmin Los (0; ((+1)),
0
where Cp.e is the Fenchel- Mouchel-Youngaa loss generated by Pg,c. This is precisely the last step in the actor update in Algorithm]] [] using the perturbed optimizer framework to define the regularization function, as detailed in Berthet et al. 2020).
This completes the proof that the primal-dual updates recover the actor update steps in Algorithm
16

---

C
Experiments
In the following, we outline the setup and design of our experiments and explain the benchmark algorithms we used in all environments.
C.1 Experimental setup
We conduct all experiments the same hardware and use the same general method of conducting experiments across environments. We use the same results metrics for all algorithms and environments, ensuring comparability of the algorithms. In general, our experiments reproducible using modest hardware equipment.
C.1.1 Hardware setup
We conduct all experiments MacBook Air M3, using the Julia programming language. Given the usually small neural networks required for COAML-pipelines in our environments, the experiments take between and 90 minutes. No external computing resources required for running the experiments. This setup is the same as the one we used for all algorithmic development.
C.1.2 Hyperparameters
We present overview over the hyperparameters of the algorithms in Table For the RL algorithms, an episode consists of testing the algorithm's performance, collecting experience in the environment, and performing number of updates, specified as iterations. For SII., episodes usually correspond to epochs, an epoch being a complete pass of the training dataset.
C.1.3 Experiment conduction
We separate all instances into train, validation, and test dataset. We create the training dataset for SII. by applying the expert policy to the training instances and storing the solutions. To tune the hyperparameters,
the same random model initialization for SII., PPO, and SRL. We tune the number of episodes and the number of iterations per episode using PPO, as it is typically the most constrained terms of iterations and requires the largest number of episodes due its on-policy, unstructured nature. This setup favors the baselines particularly PPO - since SRL often converges more quickly but incurs higher computational cost per episode. As a result, PPO holds natural advantage in runtime comparisons.
We then use the same number of episodes and iterations to train both PPO and SRL, and adjust the number of epochs for SIL to ensure that all methods perform approximately the same number of update steps overall. In most cases, this results in equal number of episodes and epochs. For the DAP and GSPP, however, we reduce the number epochs to account for the large size of the training
Table 2: Overview over hyperparameters included in the algorithms. Not all hyperparameters are used in all environments.
Hyperparameter
SIL
PPO
SRL
Episode number
Yes
Yes
Yes
Iterations number
Yes
Yes
Yes
Batch size
Yes
Yes
Yes
Learning rate actor (incl. schedule)
Yes
Yes
Yes
Leamiing rate critic(s) (inel. schedule) Episodes training critic only Replay buffer size
No
Yes
Yes
No
Yes
Yes
No
Yes
Yes
Exploration standard dev. of (incl. schedule) No. samples for â Standard dev. σn for (incl. schedule)
No
Yes
Yes
No
No
Yes
No
No
Yes
Temperature param. (incl. schedule)
No
No
Yes
No. samples for Lo(0; à) Standard dev. for Lo
Yes
No
Yes
Yes
No
Yes
17

---

dataset. We tune the exploration standard deviation d,, the perturbation standard deviation the temperature parameter т, and the learning rate - typically shared between actor and critic, or set slightly higher for the critic- using a grid search for each algorithm. Each grid search involves between 3 and 30 training runs, All other hyperparameters do not require detailed tuning.
Once the optimal hyperparameters are identified, we run each algorithm with ten randomly initialized actor (and, where applicable, critic) models. After each episode or epoch, the actor is evaluated on the training and validation datasets- or a subset thereof to improve efficiency, We save the actor model whenever it achieves the best perfonmance observed so far. At the end of training, the best- pest-performing actor model is restored and used for final evaluation on the training and test datasets.
C.1.4 Results metries
To compare performance, we run the best saved model of each algorithm after each run with different random model initializations on the train and the test dataset. We calculate the mean over the ten models per instance of the train and test dataset, using these mean per-instance rewards in the results boxplots. To compare convergence speed, we store the validation rewards over the course of training and calculate the mean across the ten runs per algorithm and environment per episode. the lineplots, we display the highest mean validation reward achieved by the model so far for each training episode. We report the mean of the standard deviations across the validation and final test rewards the ten runs in the tables. We further measure the time to run algorithm in minutes, reporting that number in the tables as well. Finally, we calculate the overall mean reward of the final tests on the train and test dataset per algorithm and environment and display it in Appendix B
C.2 Algorithm specification
For training COAML-pipelines, we compare SRL to two benchmark algorithms: SIL and PPO. SIL uses Fenchel- losses like SRL, but relies on expert imitation instead of reinforcement learning. Due to its methodological proximity and empirical performance [e.g.. |Bayy et al.) 2024] Jungel et al.) 2024), it is natural benchmark for SRL. PPO is unstructured RL algorithm, which well-known for its stability and performance. Therefore, is the most sensible RL-benchmark for SRL. We also show why PPO is better suited than Soft Actor-Criti for training the COAMI--ippelnes used in our experiments.
C.2.1 Structured Imitation Learning
Structured Imitation Learning is imitation learning algorithm successfully applied in recent works such as Baty et al. [2024] and Jungel et al. [2024]. As an imitation learning approach, SIL requires a pre-collected training dataset consisting of states and corresponding expert actions a. Since the algorithm has direct access to these expert actions, it does not rely on a critic to generate learning
targets.
Training the actor model using SIL proceeds by iterating over the training dataset and updating the model using the Fenchel- Young loss Lo(0; a). which compares the models unperturbed score vector to the expert action a. This update step is structurally identical to that used SRL, and we apply the same hyperparameters for the Fenchel- Fenchel-Young loss in both algorithms. The critical distinction is the source of the target action: while SRL derives its target action from critic, SIL directly uses the expert action à from the provided training dataset. In practice, SIL can be trained using mini-batches, though it often suffices to perform updates with individual state-action pairs.
Unlike online reinforcement learning methods, SIL does not interact with the environment during training and, accordingly, does not require an exploration standard deviation 0y. This offline setup enhances sample efficiency and improves training stability. However, it introduces limitation in multi-stage environments: since SIL exclusively observes expert trajectories, cannot learn effective policies for situations outside the demonstrated paths. Consequently, if the agent deviates from the expert path during deployment, it may struggle to recover, potentially leading to sub-optimal decisions.
18

---

C.2.2 Proximal Policy Optimization
PPO is a classical RL algorithm proposed by Schulman et (2017). to whom we refer for details. In the context of COAML-pipelines, PPO selects actions by perturbing the score vector using a Gaussian distribution Z ~ No, of), sampling single perturbed score vector 7,, and calculating its training, PPO considers the CO-layer f to part of the environment and treats the perturbed score vector 7i as its action. It then calculates the loss function
a = f(pw
T. 11) A5)) clip
Yw (1/113) 1 - c.1+c) A((3. (155)m))
[(Pw) Ejnn min
Tipe (77 85))
T (1g (m)ls))
for transitions j in replay buffer D.
Given the of observing vector given state s under the Gaussian distribution Z ~ N(6,, oy). In practise, the probability density function of 77 given Z is used. If we update using batches that contain transitions collected with different values for o,, we average o to improve stability. A key element of PPO is the policy ratio, which should ensure proximity between and old policies via clipping
action, PPO considers the policy T.. (n7s), which is the probability of
(n|s) (n|s)
The policy ratio is the probability of observing given the current actor fou divided by the probability of observing 7) given the old actor fa. The old actor ya the network used to collect the experience considered in the current update.
PPO clips the policy ratio using the clipping ratio to ensure that the new policy does not deviate into untrusted regions far away from the old policy. Constrained by the clipping, the target of a PPO update is the maximization of the advantage A(s, 1) = Q(+, 7) V(s). Since V(s) Q(s, 0), the advantage is the difference in value gained by executing the action corresponding to instead of the action corresponding to 0 given the old policy pPo Finally, PPO calculates and applies the gradients
VwiPw (s) to PP..
For estimating the Q-values and V-values, we use the same critic architectures as for SRL. Despite being an on- on-policy algorithm, PPO can use replay buffer, although that is usually smaller than for off offppolicy algorithms.
C.2.3 Benchmark reasoning
We choose PPO over Soft Actor-Critic (SAC) |Haamoja et al. 2018 2019 for the following reasons:
Actor Network Structure SAC requires the actor output both the mean and the standard deviation continuous action distribution in order to perform entropy regularization. This would necessitate neural networks with outputs-46 and oz.. In contrast, PPO allows to manually set f, avoiding the need for separate network head or specialized actor architecture. This ensures consistency across algorithms and avoids introducing additional sources of divergence.
Critic Differentiability Constraints SAC requires the critic to be differentiable with respect to the actor. However, our critic takes the form Qw (s, a) and operates directly actions a, making such differentiation infeasible. Adapting the critic to work with 0 or to be decomposable would require fundamentally different architectures, which, in early experiments, led significantly worse performance. Moreover, directly differentiating through Q (s, a) would require specialized structured loss functions, which are not yet available and remain open problem for future work.
Entropy Regularization in Combinatorial Action Spaces SAC inherently relies on entropy regularization of the action distribution. In our setting, this would regularize the distribution of 0, while regularization over the combinatorial actions is actually needed, which is not directly feasible given our pipeline. Relying on entropy to adjust of in this setup could lead to instability or poor local optima. We thus avoid this risk by setting o manually and leave the development of suitable entropy regularization schemes for combinatorial action spaces future work.
19

---

D Environment specification
In the following. provide description of the six environments we test SRL. For each environment, we explain the environment specification, the design of the expert and the greedy policies, how the COAML-pipeline is specified, how the critic specified, and what hyperparameters we use for each algorithm in the environment, We will start with the static environments, followed by the dynamic environments.
D.1 Warcraft Shortest Paths Problem
The Warcraft Shortest Path Problem is popular benchmark in the literature on COAMi-pipellnes, introduced Vlassellca et al. [020].
Environment specification The goal to find the shortest path between the top left and the bottom right corners of a map. The observed state is a map image of 96 96 x 3 pixels representing the map as a 3D array of pixels. Each map is decomposed into a 12 12 grid of cells, with each cell having cost. The cost depends the difficulty of the associated terrain. Each terrain has specific color, allowing for the inference from pixels to costs. The costs themselves are not observed in the state, but hidden from the agent. The action space is the set of all paths from the top left corner the bottom right corner of the map. The reward is the negative total cost of the path, i.e. the sum of the hidden costs of all cells in the path.
Expert policy Using full knowledge of cell costs, the optimal path is computed using Dijkstra's algorithm on the cell costs (Dijkstra 1959].
Greedy policy The greedy policy is a straight path from the top left to the bottom right corner of the map, disregarding all cell costs.
COAML-pipeline We use similar pipeline in Dalle al. [022]: : the actor model you is convolutional neural network, based on the logic of truncated ResNet18, with output dimension 12 12 The CO-layer f is Dijkstra's algorithm [Dijkstra 1959.. which computes the shortest path between the two corners of the map.
Critic specification Since the problem is static and the rewards are deterministic given an action, we do not employ a critic neural network in the WSPP. We assume access to the black-box cost function and use this function as our critic.
Hyperpan perparaareetrrs We present the hyperparameters utilized for the WSPP in Table 3 The number of iterations correspondents to the size of the train dataset.
Table Overview over hyperparameters in the WSPP
Hyperparameter
SIL.
PPO
SRL
Episode number
200
200
200
Iterations number
120
120
120
Batch size
60
20
60
Learning rate actor (incl. schedule)
le-3
5e-4 - le4
2e-3 + 1e-3
Exploration standard dev. o, (incl. schedule)
0.1 0.05
No. samples for à Standard dev. a, for (incl. schedule) Temperature param. (incl. schedule)
40
0.1 - 0.05
0.1 + 0.01
No. samples for La a) Standard dev. for (o a)
20
20
0.05
0.05
20

---

D.2 Single Machine Scheduling Problem
The Single Machine Scheduling Problem that we consider static industrial problem setting with large combinatorial action space, introduced by Parmentier and T Kindt [0233]
Environment specification An instance of the single machine scheduling problem requires schedul- ing a total of n E [50, 100] jobs single machine. Each job j [ni] has given processing time Pj and an release time rj. prior to which job cannot be initiated. The machine is limited to processing exactly one job any given moment. Once processing of a job begins, it must run completion without interruption, as preemption is prohibited. The objective is the determination of an optimal scheduling sequence as a permutation
(JI..... jn) of the jobs in [n] that minimizes the total completion time Σ; (s), with (s(s) being the completion time of job j. Specifically, for the first job in the sequence, we have Cj (s) = rjj + Pri while for subsequent jobs where k >> 1, the completion time is calculated as Cj (8) max (Tia. Cj (8)) Pje
Expert policy For instances with up to n = 110 jobs a Franch-ande and-memorize algorithm [Shang all 2021] is used exact algorithm to compute optimal solutions.
Greedy policy The greedy policy builds a greedy sequence by sorting jobs by increasing release times. Ties are broken by processing jobs with lower processing times first.
The actor model Pou simple generalized linear model with input dimension 27 and output dimension 1. For each job j E [n] we compute the corresponding feature vector Iy E R22 The features used in this model taken from Parmentier and T Kindt (2023) J. This allows to compute (0) =
COAML-pipeline
by applying the linear model in parallel to every job. The CO-layer f is the ranking operator, which can be formulated as linear optimization problem:
f: 0 ranking (0) argmax 0T,
yEa(n)
where (n) is the set of permutations of [n].
Critic specification In this static environment, again do not employ critic neural networks, but assume having access to the black-box cost function. This assumption is realistic, since evaluating the duration of a schedule is easier than finding schedule.
Hyperparameters We present the hyperparameters utilized for the Single Machine Scheduling Problem (SMSP) in Table The number iterations correspondents to the size of the train dataset.
D.3 Stochastic Vehicle Scheduling Problem
The Stochastic Vehicle Scheduling Problem that we consider is static, stochastic problem setting with a large combinatorial action space, introduced by |Parmentier 2022
Table 4: Overview over hyperparameters in the SMSP.
Hyperparameter
SIL.
PPO
SRL
Episode number
2000
2000
2000
Iterations number
420
420
420
Batch size
20
20
Learning rate actor (inel. schedule) Exploration standard dev. a, (incl. schedule)
1e-3
5e-4
2e-3 + 1e-3
0.01
No. samples for à Standard dev. an for à (inel. schedule) Temperature param. т (inel. schedule)
40
2.0
le3
No. samples for (n(0, Standard dev. for ()(
20
20
1.0
1.0
21

---

Environment specification The Stochastic Vehicle Scheduling Problem focuses on optimizing vehicle routes across time-constrained tasks in environments with stochastic delay. Each task v V is characterized by its scheduled start time lo and end time l (where > 12). Vehicles can only perform tasks sequentially, with travel time (I..) required between the completion of task u and start of task v.
Tasks can only be sequentially assigned to the same vehicle when timing constraints are satisfied:
+ 2 ty + fr (u,0)
The problem can be represented as a directed acyclic graph = A), where V V fo.d) includes all tasks plus two dummy origin and destination nodes. Arcs exist between consecutive feasible tasks, with every task connected to both origin and destination.
A feasible decision for this problem is therefore set of disjoint paths such that all tasks are covered.
What distinguishes the stochastic variant is the introduction of random delays that propagate through task sequences. The objective becomes minimizing the combined cost of vehicle routes and expected delay penalties. The cost of vehicle is denoted by Ceehicle and the cost of unit of delay Caelay- We consider multiple scenarios 8 E S. where each task experiences an intrinsic delay 7y in scenario 8. The total delay de of a task v accounts for both intrinsic delays and propagated delays from preceding task u on the route, calculated as:
d; = +max(d - 52,00 0)
Here, 8 represents the time buffer between consecutive tasks and v.
We train and test using V 25 tasks.
For more details about this environment specifications, we refer Dalle al. 2022
Table 5: Overview over hyperparameters in the SVSP.
Hyperparameter
SIL
PPO
SRL
Episode number
200
200
200
Iterations number
50
50
50
Batch size
Learning rate actor (inel. schedule) Exploration standard dev. of (incl. schedule) No. samples for â Standard dev. σ,, for à (incl. schedule) Temperature param. (incl. schedule)
1e-3
1e-2
le-2 - 5e-3
0.5
- 0.1
20
0.1 + 0.01
le4
le2
No. samples for La a) Standard dev. for Ln
20
20
1.0
1.0
22

---

Expert policy integer program:
An anticipative solution can be computed by solving the following quadratic mixed
min Caslay d.y
|S|
de + Cvchicle
Σ (EÉ+(O)
ya
(13a)
(o.d)
s.t. Σ
Yo =
Σ
Vo Ho,
(13b)
ató
(v)
agó+()) (v)
Σ
Ya =1
Ve (Yo
(13c)
AEA (v)
d 2 10 +
Σ
(d 82,e) ya
Ve WEV (e. Va
(13d)
a (v)
(m,,))
de 2 T
Ve Wo 4s
(13e)
Yo E {0
Va E A
(13l)
This assumes knowledge of delay scenarios in advance; therefore it cannot be used in practical deployment, but serves as a perfect-information bound.
Greedy policy The greedy policy for this problem is solving the deterministic variant of the problem instead, which only minimizes vehicle costs without taking into account delays. In this case, the problem is easily solved using a flow-based linear program formulation.
COAML-pipeline For each in the graph, compute feature vector of size 20, containing information about the are and delay propagation distribution along it. The actor model &ou is a generalized linear model, that is applied in parallel to all ares in the graph. It therefore has input dimension 20 and output dimension 1. The CO-layer f is a linear programming solver, which computes the optimal flow-based solution for the problem, replacing determinsitic costs by estimated scores from the actor model.
Critic specification In this static environment, we employ sample average approximation instead of critic neural networks to evaluate the costs of action. For this evaluation, randomly draw 10 (for 25 tasks) or 50 (for 100 tasks) scenarios per instance, corresponding to delay realizations. We apply the policy to every scenario and estimate the total delay of the scenario. We then calculate the costs as the average delay across all scenarios. Since evaluating an action is considerably easier than generating one, this is reasonable cost evaluation method given contextual information and stochasticity.
We present the hyperparameters utilized for the Stochastic Vehicle Scheduling Problem (SVSP) in Table The number of iterations correspondents to the size of the train dataset.
Hyperparameters
D.4 Dynamic Vehicle Scheduling Problem
The Dynamic Vehicle Scheduling Problem that we consider is a simplified variant of the Dynamic Vehicle Routing Problem with Time Windows introduced in the EURO-NeurIPS challenge 2022 Kooo
all 2022
Environment specification The Dynamic Vehicle Scheduling Problem requires deploying a fleet of vehicles to serve customers that arrive dynamically over a planning horizon. At each time stage, we observe all unserved customers currently in the system, denoted by V4. We then must: i) determine which customers to dispatch vehicles to; and ii) build vehicle routes starting from the depot to serve them. Each customer has specific location and time that must be strictly respected. Vehicle routes must adhere to time constraints, with waiting allowed at customer locations without additional cost. The objective is to minimize the total travel cost across all vehicles. A key operational constraint is that customers approaching their deadline are designated as "must-dispatch" requiring immediate service to ensure fcasibility. We denote by ymnd c. V the set of must-dispatch customer. This mechanism
23

---

ensures all customers receive service within their time windows by the end of the planning horizon. An episode has time steps.
Similarly to the stochastic vehicle scheduling problem described above, a feasible decision at time step / can be viewed as set of disjoint paths in an associated acyclic graph D (V,, At).
Expert policy We compute the anticipative policy that constructs globally optimal routes. Assuming knowledge of all futurre customer arrivals, we obtain this policy by solving the static vehicle scheduling problem, then decomposing the solution into time-step-specet
dispatching decisions.
Greedy policy The greedy policy for this problem is to dispatch all customers soon they appear; and optimize routes at each time step by solving static vehicle scheduling problem.
COAML-pipeling We use similar pipeline introduced Baty et [024]. The actor model is a generalized linear model with input dimension 14 and output dimension 1. This model is applied in parallel to each customer o V,, predict a prize 0, from its feature vector of size 14.
The CO-layer f a static vehicle scheduling MIP solver, with are costs predicted by the actor model:
arg min
Σ
(0p da Yo
(u,
s.t.
Yo
Yor
Ve V3
aEd
aE
f:0
Σ Ya S 1,
Ve E V
(14)
aEd (v)
Σ Va = 1,
Vu E Vima
aEô
Ya E {0, 1],
Va E A,
Critic specification In the DVSP, we use single graph neural network as the critic. The network takes the solution graph input and outputs single value the Q-value, using several graph convolutional layers, global additive pooling layer, and finally several fully connected feedforward layers as its architecture. The solution graph is graphical representation of action in the DVSP, whith all requests being nodes and vehicle routes being edges. For each node, we pass a feature vector into the critic network. These features the same for the actor, plus indicator whether a request is postponable or not. For each edge, we pass the distance into the critic. We train the critic using ordinary Huber losses between Qain, (st, a₂) and yr r, + Q (Se4 (a 1)). For this, we use the same transitions as immediately afterwards for the policy update, which we sample from the replay buffer.
Table 6: Overview over hyperparameters in the DVSP.
Hyperparameter
SIL
PPO
SRL
Episode number
400
400
400
Iterations number
100
100
100
Batch size
4
Learning rate actor (incl. schedule)
le-3
le-3 - 5e-4
1e-3 + 2e-4
Learning rate critic(s) (incl. schedule)
le-2 - 5e-4
2c-3 + 2
Replay buffer size
12000 (2000 eps.)
120000 (20000 eps.)
Exploration standard dev. o, (incl. schedule)
0.5 0.05
0.1
No. samples for
40
Standard dev. σ, for ā (incl. schedule) Temperature param. 7 (incl. schedule)
1.0
0.1
10
No. samples for (0;
20
20
Standard dev. e for (0;
0.01
0.01

---

Hyperparameters
We present the hyperparameters utilized for the DVSP in Table 6
D.5 Dynamic Assortment Problem
The Dynamic Assortment Problem that consider is multi-stage problem with endogenous uncertainty and large combinatorial action space. We use a version adapted from the Dynamic Assortment Optimization problem introduced by Chen al. 2020 The DAP also related to recommender systems, as used by Dulac-Arnold et al. [016]].
Environment specification We have = 20 items i E I. of which we can show an assortment of size K
customer each time step. Each item has features and a price, creating the feature vector u. The uniform customer calculates score θ per item using a hidden linear customer model θ Φ. The customer then estimates purchase probabilities for each item using the multinomial logit model
exp θ
P(iS)) 1+ Ejes exp
which includes the option not buying an item. By sampling from the purchase probabilities. the customer purchases an item or no items. We receive the item's price as reward r(2). After purchasing an item, the third feature of that item increased by a "hype" factor, which is decreased again over the subsequent 4 time steps. The fourth feature is increased by "satisfaction" factor as once-of increment. The other features and the price remain static, having been randomly initialized at the beginning of an episode. The hidden customer model & remains static globally. An episode has 80 time steps.
Expert policy Due to the endogenous feature updates, finding a globally optimal policy is com- putationally intraceable. We therefore resort online optimal policy approximation. Given knowledge of v and Q, we enumerate all possible assortments of size K, calculating P E S and then calculating the expected revenue of S as R(S) Eies r(i) P(jSS). We finally select the assortment S with the highest expected revenue R(S).
Greedy policy The greedy policy sorts items i by their price r(i) and selects the K items with the highest r(1) as S.
The actor model fu. a 2-layer fully connected feedforward neural network with input dimension 10, hidden dimension 5, and output dimension 1. In addition the feature vector v, its input is the current time step relative to the maximum episode length, the one-step change of the endogenous features, and the change of these features since the start of the episode. We perform one pass through &u per i, generating vector of scores 0. The CO-layer f ranks 0 and selects the K items corresponding the highest S.
COAML-pipeling
Table 7: Overview over hyperparameters in the DAP.
Hyperparameter
SIL
PPO
SRL
Episode number
200
200
200
Iterations number
100
100
100
Batch size
1
4
Learning rate actor (incl. schedule) Learning rate critic(s) (incl. schedule)
le-4
5e-3
1e-3 - 5e-4
5e-3
1e-3 - 5e-4
Replay buffer size Exploration standard dev. o, (incl. schedule) No. samples for à
1600 (20 eps.)
8000 (100 eps.)
0.1
0.05
2.0 + 1.0
40
Standard dev. σ, for (incl. schedule) Temperature param. (incl. schedule)
2.0 + 1.0
1.0
No. samples for La(0; a)
20
20
Standard dev. for Lo (o:0:))
1.0
1.0
25

---

Critic specification Given the highly stochastic nature of this environment, we employ two crities: the first critic should approximate R(S): it first processes and the relative time step, which is part of the vector for computational simplicity, using feedforward layer with an output size 3 per S. It then concatenates these intermediate outputs in vector and feeds them through another feedforward layer with output size 1. It is trained by minimizing the Huber loss between the actual reward r(i) of purchased item i and its output. The second critic should approximate Q (st, ae) Tt Q (st+1, (st+1)). It receives all features that (ou receives plus binary indicator whether E as input for all i, using a feedforward layer to estimate hidden scores per i. After concatenating these scores, it estimates Q-values using 2-layer feedforward neural network with hidden dimension 10 and output dimension 1. It is trained by minimizing the Huber loss between the on-policy returns ref, Ek-r+17 7 r and its output. Due to its on-policy nature, it receives shuffled transitions from the last episode instead of sampled transition from the replay buffer. After failing to converge in initial tests using both critics, we only employ the first critic in PPO. Given the good performance of the myopically optimal policy, and comparably good results when training SRL using only the first or both critics, this should not impede the performance PPO can reach substantially. Were to converge properly, it should still display performance similar to that of SII..
Hyperparameters
We present the hyperparameters utilized for the DAP in Table 7
D.6 Gridworld Shortest Paths Problem
The Gridworld Shortest Paths Problem that we consider is a dynamic problem with endogenous uncertainty and a large combinatorial action space. It is related to gridworld problems that are commonly used to investigate the scalability of RL algorithms [c.g., Chandak et al. 2019]. It is furthermore related to robot control tasks in discrete environments [e.g.. Zhang et al. 2020).
Environment specification We control a robot gridworld of size 20 20 with cells (i,j) E JJ. Each time step, we need to find the best path between the current position of the robot and a target, the robot can move to all 8 neighbors of a cell if they exist. Upon reaching the target following the path, the target moves to random new location and we transition to the next state. Each cell (i,j) in the gridworld has six features, P,,y which are randomly initialized the beginning of an episode and which remain constant for the remainder of the episode. The first three features vf,; determine the immediate costs of the cell Cr, via a fixed linear model &h as C. = (ef,)) final three features vf,, determine the change of a cost parameter p via another fixed linear model Φ as Apt.j = (ef,)"Tr The cost of a path C is calculated as the sum of all Ct.j of traversed cells times p. The cost parameter p is subsequently updated by multiplying itself with one plus the sum of all Apt.y of traversed cells. The presence of introduces strong endogencity to the problem: a path minimizing the sum of o.j does not have to be globally optimal, but minimizing the immediate costs has to be balanced with minimizing p. The linear models the and the remain hidden for agents,
"T qr. The
Table 8: Overview over hyperparameters in the GSPP.
Hyperparameter
SIL
PPO
SRL
Episode number
200
200
200
Iterations number
100
100
100
Batch size
1
4
Learning rate actor (incl. schedule)
le-4
5c-4
lc-3 + 5e-4
Learning rate critic(s) (incl. schedule)
5e-4
1e-3 - 5e-4
Episodes training critic only Replay buffer size
40
40
2000 (20 eps.)
10000 (100 eps.)
Exploration standard dev. o, (incl. schedule) No. samples for Standard dev. σb for (incl. schedule) Temperature param. (incl. schedule)
0.05
0.05
40
0.05
0.1
No. samples for [o a)
20
20
Standard dev. for Lo a)
0.01
0.01
26

---

which only know the features v. An episode has 100 time steps, we use 100 train, validation, and test-episodes.
Expert policy Given the endogeneity of the environment, finding globally optimal policy is computationally infeasible. We thus again resort to using a myopically optimal policy as =(s). Using full knowledge of u and 4., we estimate the immediate cell costs Ci = (ef dhe for all (i. We then apply Dijkstra's 's algorithm on these costs to generate the shortest path from the robot's ' current position to its target position [Dijkstra 1959].
Greedy policy The greedy policy estimates straight path from the robot's current position to its target position. Disregarding cell features v, this is a reasonable estimate for the lowest-cost path that the robot can take.
COAML-pipeline The actor model fuu is linear model with input dimension 7 and output dimension 1. It takes Vi,j and the time step relative to the maximum episode length as input and outputs score 0. Via negative absolute activation, PL ensures that all 0 I O. We perform one pass per cell (i, j). We then apply Dijkstra's algorithm on these 0 to generate the best path from the robot's current position its target position given 0 [Dijkstra 1959
Critic specification We employ double Q-learning to mitigate the critic overestimation bias in this endogenous dynamic environment [cf., van Hasselt, (2100] Fujimoto et al., 2018). Both critics 49 k E (1.2) have the same structure and learning paradigm, but are initialized using different
random seeds. We estimate Q a) (s,a) with input dimension 8 and output dimension 1. For each cell (i.j) E they take the time step relative to the maximum episode length, and the current cost parameter p as input, while all inputs are set to zero for (i,j) & After estimating value for each cell, these values are summed to calculate Qua (s, We train both critics by minimizing the Huber loss between Q (se, az) and Y1 rt + 7 Qva.. (S141, x (((+1)) ))- For this, we use the same transitions as immediately previously for the policy update, which we sample from the replay buffer.
(s,a) The critics das are linear models
Hyperparameters
We present the hyperparameters utilized for the GSPP in Table
E
Additional results
E.1 Results for static environments
Environment description The static environments, adopted from Dalle et al. [2022]. are as follows:
i) the Warcraft Shortest Paths Problem (WSPP) [Vlastelica et al. 2020 where the task is compute lowest-cost paths on a map. given the raw map image as input; ii) the Single Machine Scheduling Problem (SMSP) [Parmentier and T Kindt 2023), where the task is to determine job sequence for a single machine that minimizes total completion time; and iii) the Stochastic Vehicle Scheduling Problem (SVSP) [Parmentier] 2022], where the task is to find vehicle routes that minimize random delays while servicing temto-ltemporall distributed tasks.
We adopt the same experimental setup as for the dynamic environments. Expert solutions are computed by solving the problems to optimality. the static environments, we do not use crities; instead, we assume access to a black-box cost function for both the WSPP and the SMSP, and apply sample average approximation to estimate costs in the SVSP.
Figure 7 Figure 8] and Table present results for the static environments. These results are generally similar the results for the dynamic environments. In all environments, SRL performs comparably to SIL, with both algorithms approaching the expert policy. SRL consistently outperforms PPO by at least 5% and up to 54%, which converges to near- -rredy policies in the WSPP and the SMSP; and which struggles to converge in the SVSP, yielding low average performance. SRL and SIL algorithms converge fast in the SVSP, requiring fewer than 10 episodes to reach a performance plateau. Both algorithms converge slower, but with the same speed, in the WSPP. These results highlight the similarity between SRL and SII. in static environments when SRI. able to sufficiently explore the combinatorial action space. They underscore that SRL is competitive with SIL and serves as a strong
27

---

WSPP
train
test
100
100
-33
areddy (%)
vall rew.
-36
10
10-
-39
-42
SIL PPO SRL
-45
-10
-10
SIL
PPO
SRL
expert
SIL
PPO
SRL
expert
50
150
200
training episode
Figure 7: WSPP results. Left: final train and test- cest-peeforaacce compared to greedy (Ascedy); right: validation performance during training; averaged over random model initializations.
SMSP
SVSP
1000
train
1000
test
1000
train
1000
test
Arrody (%)
100
100-
A (%)
100
100
10
10
10
-10
-10
-10
-10
-100
S1L
PPO
SRL
exper
SIL
PP0
SRL
expert
SIL
PPO
SRL
expeat
SIL
PPO
SRL
eapert
val. rew. (104)
-15
vai. rew. (10*)
-9
-20
-12
-25
SIL PPO
-15
SIL
PPO
-RR
-SLL
500
1500
150
training episode
training episode
Figure 8: SMSP and SVSP results. Left: final train and test-performance compared to greedy
(A (eedyyy); y; right: validation performance during training; averaged over 10 random model initializa-
tions.
alternative in settings where an optimal solution is unavailable. In the SMSP, SRL and PPO converge slower than SII., requiring 500 episodes compared to 100.
Stability measures underline the above results: SRL and SIL show low variance, while PPO is up to 400x less stable. This underscores the stabilizing effect of structured learning using Fenchel- losses. The stability and performance gap especially pronounced in the SVSP, where stochasticity and highly combinatorial complexity challenge PPO, in contrast to the simpler and deterministic SMSP and WSPP. These combinatorial complexities impact computational effort: while all methods complete their training in 7-9 minutes in the WSPP and in 1015 minutes in the SMSP, PPO is over 3x faster than SIL and over 7 x faster than SRL in the SVSP, omitting offline solution time for SIL. Again, these differences stem from CO-layer usage. While negligible in simple settings like the WSPP and the SMSP, this overhead becomes substantial in environments with complicated CO-layers like the SVSP. The WSPP presents an interesting case: although it requires the largest neural network of all considered environments, its simple CO-layer reduces performance differences between algorithms. Overall, these results suggest that SRL yields the greatest performance gains in environments with highly combinatorial structure; but these gains come at the cost of increased computational effort.
Table Standard deviation of validation rewards during training and final testing rewards over 10 random model initializations; and training time of algorithms in the WSPP, SMSP, and SVSP.
WSPP
SMSP
SVSP
Algorithm
train
test
time
train
test
time
train
test
time
SIL
0.2
0.6
7m
0,0
0.0
10m
0.2
0.0
11m
PPO
3.8
5.6
9m
1.9
0.3
15m
10.0
10.0
3m
SRL
0.5
1.0
9m
0.1
0.0
12m
0.1
0.0
23m
28

---

E.2 Numerical results for all environments
We display all numerical results of the final tests in Table for the static environments and in Table I1 for the dynamic environments. In all environments except the DAP, costs are to be minimized; the rewards are therefore negative. higher number, indicating lower cost, is therefore better. In the DAP, revenues are to be maximized; the rewards are therefore positive. A higher number, indicating higher revenues, therefore better.
Table 10: Final performance of algorithms on the train and test dataset for the WSPP, SMSP, and SVSP. For SIL., PPO, SRL,, averaged over 10 random model initializations.
WSPP
SMSP
SVSP
Algorithm
train
test
train
test
train
test
Expert
-30.4
-29.8
-177306
-152670
-6885
-6670
Greedy
-43.1
-43.5
-175185
-168738
-7228
-7038
SIL
-30.4
-30.5
-159258
-154399
-6907
-6701
PPO -39.3
-39.1
-168790
-162892
-14735
-14610
SRL -30.5
-30.6
-159135
-154388
-6904
-6695
Table 11: Final performance of algorithms the train and test dataset for the DVSP, DAP, and GSPP. For SII., PPO, SRL,, averaged over 10) random model initializations.
DVSP
DAP
GSPP
Algorithm
train
test
train
test
train
test
Expert
-30.1
-25.5
569.9
583.2
-1293.6
-1284.9
Greedy
-35.1
-30.0
439.6
484.1
-1554.2
-1574.4
SIL
-31.8
-27.2
490.9
519.2
-1257.7
-1253.5
PPO
-37.4
-32.5
308.7
313.1
-3605.0
-3683.9
SRL
-31.9
-27.3
529.8
555.3
-275.5
-280.2
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All claims made in the Abstract, Introduction, and Conclusion grounded either in theoretical or empirical results presented in the main body of the paper or in the appendices. Specifically, theoretical claims are backed by Section 2.2 and Appendix B
while empirical results are backed by Section 3 and Appendix
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss theoretical and empirical limitations separately in the respective
sections: Section for theoretical limitations and Section 3 for empirical limitations.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
30

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We provide proofs for all theoretical results of Section 2.2 either directly there, or in Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide detailed description of our proposed algorithm in Section 2 We provide detailed description of all experiments in Appendix C and of all experimental environments in Appendix These appendices cover the information required to reproduce our experiments. In addition, we provide our source code as supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
31

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We provide all data and code supplementary material. In addition, publish the code to Julia repository on Github. All other Julia packages we used are publicly available. Our code contains instructions reproduce experimental results, as well as comments to understand key concepts. Since the repository is not anonymized, we do not refer to it in the paper befor the camera ready version.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/
aublic//uuldss/odeeuulbssss wtw.oodddsuubssssooooooooc for more details.
While we encourage the release of code and data, we understand that this might not be possible, so No is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.cc/ hta.ps..cc/pbbbicguuuueee https/////.ides//ddeubbbbbisbss htt////ooSSuiiiaaaaeee wwi.bbmmiisiioooooccccccc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide a concise overview over our experiments in Section containing the most important experiment specifications. We provide a comprehensive and detailed description of all relevant details required to understand our experiments Appendix C In adition, our code contains the specifications of all environments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
32

---

Answer: [Yes]
Justification: We present our main results in Section 3add appendix[Eas boxplots, naturally showing the distribution of the underlying data. In these boxplots, we exclude outliers beyond the whiskers, which extend 1.5x the interquartile range from the quartiles in either direction. Early investigations revealed that this excludes only a small fraction of the data, but improves clarity of the plots. All visualized results means over ten training runs with random model initializations. across these ten runs in tables. Assumptions the distribution of c.g., errors are not necessary in our experiments. Overall, these measures show the statistical significance of our results.
addition to that, we report the mean standard deviation
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We outline the compute resources used generate the results in this paper in Appendix C As stated there, these are the same ressources we used for all algorithmic development.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https::///tutiiiie http:://eeriiiss.coeo httpar/ppp..cpppppp/chccccccceee
Answer: [Yes]
33

---

This paper does not violate any part of the NeurIPS Code of Ethics. Neither the algorithm we propose nor the experiments we conduct have caused harm anyone, nor do we expect them to cause harm to anyone.
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Since this paper is pure methodological contribution, we do not expect it to have any direct societal impact. We briefly discuss the the positive impact on research and industry our proposed algorithm may have in Section [ and Section
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not potential for misuse of the algorithm proposed in this paper.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
34

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All external assets used in the paperspecifically environments, packages and benchmarksare properly credited through an extensive list of references. No additional code, data, models requiring license terms of use considerations were used.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, batasetss.pppersiiii shperswithhodde com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information is available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide the code as a supplementary material. The code contains doc- umentation and commenting to explain key concepts. We further upload the code to Github repository, containing all documentation and explanations. Since the repository is not anonymized, we do not refer to it in the paper.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not conduct crowssuuring experiments, nor does it experiment with human subjects.
Guidelines:
35

---

The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation,
or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not conduct with human subjects.
conduct crowdsoureing experiments, nor does it experiment
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs do not constitute an mportant, original, or non-standard component the core methods in this paper. We used LLMs only for minor writing, editing, and formatting purposes. LLMs did not contribute to the core research of this paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM policy http:://nnurrrpsscoooeeeeeeeeeee for what should or should not be described.
36


Reviews:
[{"review_id": "0qsa7f2YeF", "reviewer": "Reviewer_xQoh", "summary": "In this paper the authors introduce a novel framework, called Structured Reinforcement Learning (SRL). SRL is well suited for combinatorial complex optimization tasks e.g. that have a combinatorial action space. In particular, this framework incorporates a combinatorial layer and a statistical model into the actor of the actor-critic framework, which is trained via backpropagation and a Fenchel-Young loss. The proposed framework outperforms PPO and Imitation Learning in six different environments.", "questions": "- While the authors mention that action masking is a commonly used tool in RL for combinatorial problems, is there a particular reason why none of these are included in the benchmarks? For instance, consider the already implemented framework for PPO with invalid action masking in the contrib version of [2].\n\n- Why are reward values used to showcase convergence speeds, while $\\Delta^{greedy}$ is used to report train and test performance? This seems like a rarely used evaluation criterion for proposed RL algorithms. Can the authors provide additional clarifications on why they chose this metric?\n\nReferences:\n\n[1] RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark, Federico Berto et al., 2025\n\n[2] Stable-Baselines3: Reliable Reinforcement Learning Implementations, Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dormann, 2021, JMLR", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths:\n\n- The paper is well motivated and gives an extensive discussion of the state-of-the-art methods, their limitations, and how SRL overcomes these and additional challenges such as the non-differentiability of combinatorial layers. Additionally, the authors provide illustrations (e.g., Figure 1) that make it easy to follow and understand the main ideas of the framework.\n\n- The authors not only provide the code of the experiments but also include all the necessary details to reproduce their results in the paper.\n\n- The authors divide the environments into static and non-static ones and clearly show the limitations of the considered benchmarks in the non-static environments, e.g., that Imitation Learning tends to fail to generalize (problems in the test phase and higher standard deviation in testing). I appreciate that, for transparency and fairness, the static ones are also considered, where Imitation Learning performs equally well while having a lower running time. This allows practitioners to consider different types of algorithms for different environments.\n\n- For additional insights, the authors relate their algorithm to primal-dual algorithms for the simplified setting of contextual problems (T=1), which gives a more theoretical foundation to the proposed framework.\n\n- The proposed algorithm outperforms or matches the benchmarks across six environments. It particularly outperforms in the more complicated non-static environments.\n\n## Weaknesses:\n\n- While the paper is generally well written, I think it would greatly benefit from including not only the sketched version of Combinatorial MDPs in the main text, but also more details, as this is fundamental to understanding the setting of the paper and the foundation of the newly proposed framework.\n\n- The only baselines considered in this paper are Structured Imitation Learning and PPO. While the authors justify in the appendix why they did not include SAC as a benchmark, it seems that they should also consider other algorithms (perhaps even SAC, as its soft update increases exploration, and in this work the authors also consider a soft critic). Additionally, how does the method perform in more environments typically used for combinatorial problems, or against standard solvers for these tasks? See, e.g., [1] for a more extensive benchmark.", "was_revised": true, "final_justification": "After reading the rebuttal and discussion, I believe the authors have addressed my main questions and provided helpful clarifications.\n\nOverall, I find the paper clearly written, well-motivated, and addressing a relevant problem with a sound and implementable solution. Given the current version and the authors’ commitment to extending the evaluation, I lean toward acceptance, while noting that a stronger empirical evaluation would further solidify the contribution.", "rebuttal": "We thank the reviewer for the valuable comments and questions.\n\n## Combinatorial MDPs\nWe will provide the full definition of Combinatorial MDPs in the main paper instead of the appendix for the revised version of the manuscript.\n\n## Additional benchmark (SAC)\nWe acknowledge that other algorithms, especially SAC, would be interesting benchmarks for our experiments. However, we would like to explain the reasons why the application of SAC to the problem settings studied in our paper is currently infeasible. SAC could be used in two ways:\neither with a classic neural network architecture, or with an architecture that includes a CO-layer. Both architectures are impractical for SAC, for the following reasons.\n\nSAC algorithms are generally designed to work with classic neural network architectures that have one output per action.\nSince our problem settings have a combinatorially large number of actions, such architectures are not practical.\nAny practically usable architecture needs to have some postprocessing to decode combinatorial actions from a tractably small prediction.\nWhile some rounding techniques are proposed in the literature, CO-layers currently seem to be the most efficient architectures for the problems we are considering - indeed, we have chosen them for this reason.\n\nOn architectures that include CO-layers, SAC is not a practical algorithm as well. In this setting, there would be two ways to design a critic: a critic on the actions, or a critic on the scores $\\theta$.\nWhen using a critic on the actions, we would have to backpropagate the critic through the actor, and thus through the CO-layer.\nThis requires to differentiate through the argmax over all feasible actions.\nWith the perturbation/regularization approach we have, this may be doable in theory. However, it would require using a very noisy score function (REINFORCE gradient) estimator. We tested several algorithms using this gradient, and all failed to converge due to the high variance. In contrast, the advantage of our approach is that we differentiate through the max instead of the argmax thanks to the Fenchel-Young loss, which enables to use far less noisy pathwise estimators.\n\nUsing a critic on the scores $\\theta$ is equally challenging. In this case, the critic would have to approximate the mapping of scores $\\theta$ to actions $a$ performed by the CO-layer. This mapping is piecewise constant on the normal fan of the polytope $\\mathrm{conv}(\\mathcal{A})$, which is very difficult to approximate. For instance, in many applications, the CO-layer is a MILP-solver, whose output and values are known to be difficult to estimate using a neural network.\n\nWe tried both a critic on scores and a critic on actions on the DVSP. Even after extensive hyperparameter tuning and allowing for more computational effort, the score-based critic could not converge properly, preventing effective actor training. We will include these results in the camera-ready version of the manuscript. Developing efficient SAC for combinatorial multi-stage problems requires new ideas to circumvent these difficulties, and we believe it is an interesting research avenue.\n\n## Additional environments\nWe have investigated the environments and benchmarks in the RL4CO-package thoroughly and compared them to the benchmarks used in our paper. While the RL4CO-package provides an extensive collection of single-stage deterministic problems, it does not contain stochastic problems (like the SVSP we use) or multi-stage problems, which form the main application area of Structured RL. Instead, the RL4CO-package focuses on problem settings for Neural Combinatorial Optimization, in which solutions for combinatorial single-stage problems are constructed iteratively using multiple calls to a neural network. In contrast, COaML-pipelines use CO-layers to construct entire solutions at once.\n\nIn the EURO meets NeurIPS 2022 challenge, a COaML-pipeline outperformed Neural CO-architectures in a combinatorial multi-stage problem setting. The limitation of COaML-pipelines has so far been their reliance on expert trajectories as imitation learning training data. We address this research gap by proposing Structured RL. We therefore concentrate on comparing different learning paradigms for COaML-pipelines in our experiments, these learning paradigms should be capable of addressing combinatorial multi-stage problems without the need for iterations within one stage. We agree that developing well-performing Neural CO algorithms for multi-stage problems is an interesting avenue for future research.\n\n## Action masking\nWithin combinatorial action spaces, employing ordinary action masking is very challenging, if not impossible: the action space $\\mathcal{A}(s)$ depends on the state $s$ and is exponentially large, which makes it hard to encode using neural networks in combination with action masking. Especially in highly combinatorial problem settings (e.g., SVSP and DVSP) the action mask would have to be combinatorial as well. We therefore cannot include RL with ordinary action masking in our experiments.\n\nWhen mentioning action masking in our paper, we are referring to treating the CO-layer as an action mask in the environment. This method has been employed in the past and corresponds to what we call unstructured RL in our paper. By using PPO as a benchmark, we are including this method in our experiments. In the revised version of the manuscript, we will add a clarification about this.\n\n## Results display\nWe are not sure to see which alternative performance metric the reviewer is referring to. Indeed, in such a setting, there is no easy metric beyond evaluating the performance of the policy using rewards obtained in a simulation.\n\nWe use validation rewards during training to graphically show how the compared algorithms converge to their final performance over the course of training. This should allow readers of our paper a quick and easy way of comparing the training behavior and speed of the algorithms visually. We use rewards of the final model on the train and test-datasets to compare performance. Since the rewards can vary substantially between algorithms, we display performance relative to a greedy policy on a log scale to enhance readability. This metric may seem unfamiliar for an RL paper, but is very common for industrial problems, where a greedy baseline is usually readily available. From a practical perspective, the metric provides a visual and easy way to assess the performance benefits of a proposed algorithm over using a greedy heuristic. At the same time, the metric allows for the comparison between the proposed algorithms and benchmark algorithms within the same figure. Based on the reviewer's comment, we will add a brief explanation of our performance metrics in the camera-ready version of the manuscript.\n\n## Conclusion\nWe hope to have addressed all comments and questions of the reviewer and welcome any further discussion. If so, we would kindly ask you to consider raising your scores."}, {"review_id": "KmSgfJqWFm", "reviewer": "Reviewer_YWqy", "summary": "A novel framework (SRL) is proposed to embed a Combinatorial Optimization (CO) layer into the actor neural network. Through the decoupled design of \"generating score vectors via a statistical model + solving for optimal actions via a CO layer\", it breaks through the exploration bottleneck of traditional RL in exponentially large combinatorial action spaces.", "questions": "Q1. In non-convex combinatorial spaces (such as scheduling problems with nonlinear constraints), will the mapping of the CO layer lead to gradient vanishing?\nQ2. The paper treats the CO layer as a black-box solver (such as Dijkstra's algorithm) without considering the approximation errors of the solver itself. When the CO layer returns suboptimal solutions (e.g., heuristic solutions for large-scale TSP), will the SRL end-to-end training amplify such errors?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "S1. The experiments were run on a regular laptop (MacBook Air M3) with training time ranging from 3 to 90 minutes, making it more deployable than unstructured RL that relies on clusters.\nS2. By perturbing the score vector with Gaussian noise to promote exploration of the action space, the number of feasible solutions covered by the policy is tripled in the dynamic vehicle scheduling problem.\nW1. The paper mainly compares with SIL and PPO, and does not compare with other cutting-edge reinforcement learning algorithms for combinatorial optimization problems. With the rapid development of research in this field, new algorithms are emerging continuously. Comparing with few algorithms makes it difficult to comprehensively evaluate the performance advantages and disadvantages of SRL. Compared with some newly proposed algorithms specially designed for complex combinatorial action spaces, the advantages of SRL in terms of convergence speed and solution quality may not be obvious, which makes the evaluation of SRL performance in the paper insufficiently comprehensive.", "was_revised": true, "final_justification": "I have no more concerns. I will maintain my initial score.", "rebuttal": "We thank the reviewer for the valuable comments and questions.\n\n## Benchmark algorithms\nThe field of RL for CO-problems has grown in recent years, but as of now, many algorithms focus on deterministic single-stage problems with combinatorial action spaces.\nIn particular, Neural CO focuses on using reinforcement learning for constructive heuristics to address such problems [1].\nIn contrast, Structured RL and all algorithms we use as benchmarks can address multi-stage combinatorial problems exhibiting contextual stochasticity. We are currently not aware of reinforcement learning algorithms capable of addressing such problem settings. In particular, neural CO algorithms are not designed for such problems. If the reviewer knows a specific algorithm that can address the studied problem settings, we would be happy to include it in our tests for the camera-ready version of the manuscript.\n\n[1] Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, Samy Bengio (2017): Neural Combinatorial Optimization with Reinforcement Learning. International Conference on Learning Representations 2017 (ICLR 2017) – Workshop Track.\n\n## Vanishing gradients\nWe are not sure to see which gradient vanishing the reviewer is referring to.\nGradient vanishing generally occurs when the depth of neural networks becomes very large, which is not the case on our settings, since our neural networks are of moderate depth by modern standards.\nThe reviewer may refer to the fact that the CO-layer, which can be seen as a mapping from scores $\\theta$ to the argmax of the feasible action space $a$, is piecewise constant, leading to zero gradients almost everywhere without regularization.\nPerturbed/regularized CO-layers lead to smoothed piecewise constant mappings, which may have vanishing gradients far away from the boundary between two normal cones. \nFor this reason, differentiating through the regularized argmax, which can be done with a score function (REINFORCE gradient) is very noisy and may indeed lead to vanishing gradients.\nThis is why algorithms that require such gradients in the setting of COaML-pipelines, such as SAC or REINFORCE, do not converge in practice.\nThe strength of our approach is circumventing this difficulty by differentiating through the regularized max of the feasible action space instead of the argmax using Fenchel-Young losses. This leads to gradients that do not vanish (the Fenchel Young loss is convex in $\\theta$) and that are less noisy, since we use a pathwise gradient estimator instead of a score function.\n\n## Non-linear constraints\nOur structured RL approach only requires the CO-layer to be linear in the scores $\\theta$, but neither in the actions $a$ or the constraints of the optimization. The learned scores $\\theta$ form the coefficients of the objective function, while the constraints are given by the problem setting. The restriction to linear objective functions is common in industrial applications, where most problems can be modeled as mixed-integer linear programs. In case of continuous actions, other loss functions, for example SPO+ losses, can be utilized effectively. We will add a clarification on this requirement in the revised version of the manuscript. We believe that the development of structured (reinforcement) learning algorithms for non-linear objective functions or learnable constraints is an interesting and relevant avenue for future research.\n\n## Heuristic CO-layers\nWe can consider this question from a practical and a theoretical perspective: from a practical perspective, heuristic CO-layers are not problematic. The CO-layer used in an imitation learning context to win the EURO meets NeurIPS 2022 challenge is a heuristic, as is the sorting function we use in the DAP. While the CO-layer is theoretically required to return the optimal action with respect to its input scores $\\theta$, this assumption can be relaxed in practice. Due to the decision-focused end-to-end learning paradigm, the statistical model learns to estimate the scores that the CO-layer maps to the right actions, thereby mitigating predictable errors of the CO-layer.\n\nFrom a theoretical perspective, a recent preprint on arXiv investigates the use of local search heuristics as CO-layers [1]. Their findings suggest that the use of a non-deterministic heuristic as a CO-layer amounts to regularizing the problem, which can be used to construct Fenchel-Young losses. We believe that further development of this method and its integration with Structured RL are interesting avenues for future research.\n\n[1] Germain Vivier-Ardisson, Mathieu Blondel, Axel Parmentier (2025): Learning with Local Search MCMC Layers. arXiv preprint on arXiv:2505.14240.\n\n## Conclusion\nWe hope to have addressed all comments and questions of the reviewer and welcome any further discussion. If so, we would kindly ask you to consider raising your scores."}, {"review_id": "zHtZHVlEH2", "reviewer": "Reviewer_N696", "summary": "This paper introduces Structured Reinforcement Learning (SRL), a novel actor-critic framework designed to solve combinatorial Markov Decision Processes (C-MDPs). Standard reinforcement learning algorithms struggle with these problems due to exponentially large action spaces and the difficulty of leveraging combinatorial structures. The core innovation introduced in paper is the integration of a combinatorial optimization (CO) layer into the actor's neural network architecture. In this setup, a neural network maps the current state to a score vector, and the CO-layer solves a combinatorial problem using these scores to select a feasible action. A key challenge in this architecture is the non-differentiable nature of the CO-layer, which typically has zero gradients almost everywhere. To enable end-to-end learning, SRL employs Fenchel-Young losses. It provides a convex and smooth surrogate objective for the actor update. The paper alos provide a geometric interpretation of this process, framing SRL as a sampling-based primal-dual algorithm.", "questions": "None", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "## Strengths\n\n* Impressive results: The biggest strength of the paper is the result. SRL demonstrates significant performance. It matches or surpasses unstructured RL (PPO) and imitation learning in static tasks (SIL). \n\n* Evaluation against strong baseline: The method was evaluated and compared against strong baselines on different static and dynamic environments.\n\n## Weakness\n* It would be interesting to see how the work perform in more extensive benchmarks which provide similar problems e.g. [1] provides a strong benchmark which can provide more insights about robustness and limitation of the current work.\n\n[1] https://arxiv.org/abs/2205.15659", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments and questions.\n\n## Benchmark tests\nWe are grateful for the proposed benchmark collection. Upon careful examination of the collection, we believe it addresses a different kind of problem setting than we cover using Structured RL. Specifically, the benchmark collection aims at testing algorithmic reasoning by imitating classical computer science algorithms using machine learning, while Structured RL aims to solve industrial problems. These are usually multi-stage combinatorial problems with contextual stochasticity, which are not covered by the collection. Furthermore, Structured RL can use all algorithms of the benchmark collection as a CO-layer, e.g., we use sorting and Dijkstra's algorithm. This blurs the distinction between the benefits of the Structured RL training principle and the chosen CO-layer, hindering a proper evaluation.\n\n## Conclusion\nWe hope to have addressed all comments and questions of the reviewer and welcome any further discussion. If so, we would kindly ask you to consider raising your scores."}, {"review_id": "Oxu7zWOV63", "reviewer": "Reviewer_vr8p", "summary": "The paper introduces Structured Reinforcement Learning (SRL), a framework for solving combinatorial Markov decision processes (C-MDPs). SRL replaces the standard actor network with a score-generating network followed by a combinatorial-optimization (CO) solver that turns those scores into a feasible action. Existing methods either backprop  high variance gradients through the solver or embed the solver inside the environment. The authors instead propose a training scheme that uses stochastic perturbations and Fenchel–Young losses. This leads to low-variance gradients and smoother policy improvement. Experiments on six benchmarks show SRL matches Structured Imitation Learning (SIL) on static tasks, outperforms it on dynamic tasks. It also outperforms unstructured PPO as well.", "questions": "- Please refer to the weakness section. In particular, the paper could benefit from a sharper distinction from existing methods to show what's new and unique.\n\n- While I didn't base my score based on writing, I think it would be easier to read and follow if the paper is a bit restructured (for example, adding a little bit about the formulations, details about the experiments etc to the main paper)\n\n- Citation to this recent paper [1] is missing. It might be worth seeing if some of the datasets from this paper can be used for your setting.  \n\n**References**  \n[1] Xu, Lily, et al. \"Reinforcement learning with combinatorial actions for coupled restless bandits.\" arXiv preprint arXiv:2503.01919 (2025).", "limitations": "Yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The methodology (the perturb-and-project exploration, combined with a Fenchel–Young loss, provides low-variance, end-to-end differentiable updates through the combinatorial-optimisation (CO) layer) and empirical results are the biggest strengths. The proposed approach outperforms SIL on dynamic tasks while matching it on static ones, which is a huge advantage when expert data is expensive.\n\n\nWeaknesses:\n- The paper brings together established techniques such as scoring networks, CO solvers, stochastic perturbations, and Fenchel–Young losses to the RL setting. While this integration is useful, it feels a bit incremental. \n- Writing could be improved. I had to jump back and forth between the appendix and the main paper. I would encourage the author to restructure the paper a little bit.", "was_revised": true, "final_justification": "I read all the other reviews and responses\n- I personally found the paper hard to follow (Reviewer YWqy also mentions improving organization and clarity of the writing in their reply). I however, didn't base my score on the writing (and I have stated this in my review. I think this can be easily fixed before camera ready if this paper is accepted. The authors have also stated how they would reorganize the paper and I'm happy with this response.\n\n- I didn't see any new methodological contributions. The authors do agree in their response that structured RL is indeed based on several previous methodologies. This is okay since the results look promising and the contributions are mainly in terms of application. For this reason, I'm okay if this paper is accepted.", "rebuttal": "We thank the reviewer for the valuable comments and questions.\n\n## Significance of the contribution\nAs stated by the reviewer, Structured RL is based on several previously developed methodologies. Especially COaML-pipelines and Fenchel-Young losses have been used in previous work, usually in the context of Structured Imitation Learning. While Structured IL has achieved notable successes in the past [1], it relies on expert trajectories for training. This prevents the application of this very promising architecture to settings where expert data is unavailable or expensive. In particular, there is no algorithm to train architectures with a CO-layer in typical reinforcement learning settings, where an expert may not be available, and where we do not have access to full information a posteriori, which is needed to apply Structured IL methods.\n\nTo the best of our knowledge, our Structured RL algorithm is the first algorithm that enables to train a COaML-pipeline architecture via learning by experience. It therefore opens the field to apply COaML approaches to many further industrial applications, which can profit from its expert-free structured training.\n\nAdditionally, Structured RL provides a principled way to use COaML-pipelines for exploration in combinatorial settings, which has so far not been available.\n\nConcerning the individual components of Structured RL, the primal-dual RL update step using sampling-based target actions is a novel concept. We do not know of any algorithm utilizing such an update step in a general or combinatorial setting. In addition, the Softmax regularization of the target action is a new approach to generate target actions, which - to the best of our knowledge - has not been used in any RL or imitation learning setting so far. The benefits generated by this method are another contribution of our paper. In fact, these two methodological components are crucial to enable the use of Structured Learning for combinatorial actions in an RL setting. For the camera-ready version of our manuscript, we will rework our contribution statement to reemphasize and clarify these points to better distinguish our contribution from previous work.\n\n[1] Léo Baty, Kai Jungel, Patrick S. Klein, Axel Parmentier, Maximilian Schiffer (2024): Combinatorial Optimization-Enriched Machine Learning to Solve the Dynamic Vehicle Routing Problem with Time Windows. Transportation Science, 58(4):708–725.\n\n## Writing improvements\nWe acknowledge that the appendix of the paper contains information that is beneficial to overall understanding. In the revised version of the manuscript, we will therefore\n* move the full definition of the Combinatorial MDPs to the main body of the paper.\n* move the full definition of the Fenchel-Young loss to the main body of the paper.\n* extend the description of our experiments in the main body of the paper.\n\nAfter these adjustments, the appendix will mainly contain proofs, a detailed description of our experiments to enable reproducibility, and additional results (e.g., full results tables) that facilitate deeper understanding of our results but would not fit into the main body of the paper.\n\n## Added reference\nWe will add a reference to the relevant proposed paper in the literature section of the camera-ready version of the manuscript. After careful consideration of the datasets used in the proposed paper, we believe that they address a different kind of problem setting than we study for Structured RL: while the proposed paper considers combinatorial bandit problems, we focus on combinatorial multi-stage problem settings. An extension of Structured RL to the setting of the proposed paper would therefore change the scope of our experiments away from the problem settings we currently address.\n\n## Conclusion\nWe hope to have addressed all comments and questions of the reviewer and welcome any further discussion. If so, we would kindly ask you to consider raising your scores."}]

Author rebuttal:

Meta-review: This paper introduces Structured Reinforcement Learning that is a domain-specific approach to solve combinatorial Markov Decision Processes. The paper is well-written and provides significant improvements over reasonable baselines. 

The paper does not appear to have major weaknesses. The recommendation is to accept the paper.
Decision: Accept (poster)