Conceptio › Archive › arXiv CS

arXiv CSopen access

Projecting Latent RL Actions: Towards Generalizable and Scalable Graph Combinatorial Optimization

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

distributed-systems internet networking protocols

networking, internet, protocols, distributed systems

Projecting Latent RL Actions: Towards Generalizable and Scalable Graph Combinatorial Optimization

arXiv:2605.19721v1 [cs.AI] 19 May 2026

Franco Terranova Université de Lorraine, CNRS, Inria, LORIA [email protected] Albert Cabellos-Aparicio Universitat Politècnica de Catalunya [email protected]

Guillermo Bernardez University of California Santa Barbara [email protected] Nina Miolane University of California Santa Barbara [email protected]

Abdelkader Lahmadi Université de Lorraine, CNRS, Inria, LORIA [email protected]

Abstract Graph combinatorial optimization (GCO) has attracted growing interest, as many NP-hard problems naturally admit graph formulations, yet their combinatorial explosion renders exact methods computationally intractable. Recent advances in Reinforcement Learning (RL) combined with Graph Neural Networks (GNNs) have significantly improved learning-based GCO solvers. However, existing approaches face limitations in both generalization across diverse graph instances and computational scalability as action spaces grow. To address both challenges, we introduce projection agents, a novel RL-GCO approach that operates directly in a continuous GNN-based action embedding space, predicting a desired latent action in a single forward pass and subsequently decoding it into a valid discrete action. Additionally, we enable fair comparison across RL methods through a shared embedding space for both observations and actions. Across diverse benchmarks, our approach achieves up to 16.2× faster inference and up to 40% better generalization than existing solutions using only simple nearest-neighbor decoding, while opening the door to strong RL performance in super-linear decision spaces with multiple interdependent variables. Finally, we release LaGCO-RL, a Python library that automates latent action-space construction and supports existing RL-GCO solutions, promoting reproducibility and adaptation to new GCO benchmarks.

Introduction

Solving graph-based combinatorial optimization (GCO) problems has attracted increasing interest, as many NP-hard problems across several domains can naturally be modeled as graphs [Darvariu et al., 2024]. In the seminal work of Karp [1972] introducing 21 NP-complete problems (e.g., Traveling Salesman Problem [Jünger et al., 1995]), nearly half correspond to versions of graph optimization problems, and most of them can also be formulated on graphs [Cappart et al., 2021a]. However, due to the combinatorial nature of these problems, where the number of possible solutions grows rapidly with graph size, exact methods become computationally intractable [Li et al., 2022]. As a result, heuristic methods are widely employed, trading optimality for computational efficiency [Vesselinova et al., 2020]. However, traditional heuristics typically rely on domain expertise, handPreprint.

crafted rules, and iterative trial-and-error [Li et al., 2018], often demanding substantial human effort to redesign and adapt them for each variation of the problem. More recently, machine learning (ML) approaches have emerged as a promising alternative for data-driven heuristic discovery [Bengio et al., 2021, Cappart et al., 2021a, Mazyavkina et al., 2021]. In particular, reinforcement learning (RL) methods [Cappart et al., 2021b] have attracted increasing attention, as they do not rely on labeled samples—which are costly to obtain for large instances [Peng et al., 2021, Sanokowski et al., 2023]—and construct solutions autoregressively through sequential decision-making, mirroring traditional GCO solvers [Darvariu et al., 2024]. RL has been used both for direct heuristic approximation and to accelerate exact solvers, e.g., by guiding branch-and-bound in constraint programming [Cappart et al., 2021b]. Therefore, improving RL for GCO (RL-GCO) is important to advance both directions. A key advancement of RL-GCO is the use of Graph Neural Networks (GNNs) [Scarselli et al., 2009] to learn fixed-dimensional, transferable representations of graph structures, which have been widely adopted to enhance the encoding of graph-based observation spaces [Li et al., 2024]. However, standard RL-based approaches still rely on discrete action spaces, where actions are tightly coupled to specific graph instances in both semantics and dimensionality–effectively reducing them to nontransferable identifiers [van Hasselt and Wiering, 2009, Chen et al., 2021]. Using discrete actions also reduces scalability as the output dimensionality of function approximators grows with the size of the action space [Dulac-Arnold et al., 2016]. To address these limitations, more recent approaches extend the use of GNNs to the action space by introducing action embeddings, typically derived from the embeddings of graph components. These methods then evaluate each embedded action using a Q-function Q(s, a), iterating over the full set of candidate actions, as exemplified by approaches such as S2V-DQN [Dai et al., 2017]. However, this comes at a significant computational cost, as the number of evaluations increases linearly with the number of actions, making runtime dependent on graph size and leading to scalability challenges [Manchanda et al., 2020a]. In particular, this computational cost is exacerbated in real-world GCO tasks with structured, highdimensional decision variables, where the number of actions can grow super-linearly with graph size. A prominent example is traffic engineering, where decisions over graph paths induce an exponential explosion in the action space [Xiao et al., 2021]. As a result, evaluating a Deep Neural Network (DNN) a number of times proportional to the action space size quickly becomes computationally prohibitive. This issue is amplified in dynamic settings, such as GCO applications in communication networks or data center infrastructures, where graph representations evolve continuously, and decisions must be re-computed repeatedly and under strict latency constraints [Vesselinova et al., 2020]. Contributions. To enhance the applicability of RL-GCO heuristics to large and diverse graphs across a broader range of tasks, we present the following key contributions: (1) Projection agents for scalable and generalizable RL-GCO. We introduce projection agents, which operate directly in a continuous GNN-based action embedding space. Inspired by the Wolpertinger architecture [Dulac-Arnold et al., 2016], the DNN predicts a desired action embedding in a single forward pass, which is mapped to a valid discrete action via Nearest Neighbor (NN) search. This yields up to 16.2× faster inference than iterative methods and improves relative generalization by up to 40% on unseen instances. (2) Unlocking RL-GCO for problems with complex and super-linear decision variables. We introduce a framework for constructing structured action embeddings via (i) semantic representations of individual decision components and (ii) composite embeddings capturing their interactions. This supports realistic super-linear decision spaces involving multiple interdependent variables, as found in modern real-world GCO tasks (e.g., traffic engineering, where selections involve paths and edges). (3) Unsupervised representation learning framework to better compare RL-GCO. We leverage unsupervised GNN representations [Liu et al., 2022] to build aligned observation–action spaces for RL agents. By decoupling representation learning from policy learning, we enable fair comparison across RL methods within a shared embedding space. (4) Unified Python library. We provide LaGCO-RL1 , a modular library for automated Latent actionspace construction in GCO with RL. The data repository, including model checkpoints, generated scenarios, complete experimental results, and hyperparameter configurations, is publicly available and attached to this paper.2 The library enables rapid adaptation to new tasks by requiring only 1 Code: https://github.com/terranovafr/LaGCO-RL 2 Data repository: https://zenodo.org/records/20019625

RL-GCO Solutions

Action Space Complexity Gap

....

Discrete Agent

SEL

GNN

Projection Agent (Ours)

SI VA AS PI OI AI SI VA AS PI OI AI

SEL

....

Iterative Q-Agent

Q Q Q Q

TSP

MinVertex

✔ Classical

OSPF

Traffic

✘ Real-world

SI VA AS PI OI AI

SI: Size Invariance VA: Variable Action-Set AS: Action Semantic PI: Permutation Invariance OI: One-Shot Inference AI: Action Interpolation

Figure 1: Overview of related work across: (1) action-space complexity, where real-world problems require richer decisions beyond node embeddings hi ; and (2) comparison of our projection method and others based on: graph-size invariance, support for dynamic action sets, action semantics (vs. flat indices), permutation invariance, one-shot inference (one forward pass for a decision), and support for action interpolation. ✓, ∼, and × denote full, partial, and no support, respectively. environment-specific logic, while promoting reproducibility of the proposed methodology [Nie et al., 2023]. The implementation natively supports the proposed projection agent alongside existing RL baselines and is built on standardized Stable-Baselines3 (SB3) [Raffin et al., 2021] implementations.

Related work

This section reviews related work along two main axes illustrated in Figure 1: (i) the action space complexity of existing benchmark GCO problems, and (ii) the ability of current RL-based solutions to effectively handle the typical action space challenges of GCO. An extended related work against other ML heuristic approaches (including other paradigms beyond RL) is provided in Appendix A. Action space complexity gap. Prior work on RL-GCO has largely focused on simplified benchmarks with limited decision complexity. Seminal studies [Dai et al., 2017, Manchanda et al., 2020b, Li et al., 2018] consider classical problems such as the Traveling Salesman Problem (TSP) and Minimum Vertex Cover (MinVertex) [Dinur and Safra, 2005] (see Figure 1’s action space instances coming from our experimental study), where graph representations remain basic: edge features are often reduced to scalar weights or ignored, and node features are limited to simple indicators (e.g., visited flags). Moreover, these approaches predominantly treat nodes as the sole decision variables, resulting in action spaces that scale linearly with graph size and exhibit relatively simple structure. Under such settings, GNN-based node embeddings are typically sufficient to produce well-separated manifolds of actions, facilitating efficient RL learning. In contrast, real-world applications such as OSPF engineering [Bernárdez et al., 2023] or Traffic routing [Xiao et al., 2021] involve more complex decision variables (e.g., paths), resulting in action spaces that grow super-linearly not only in size but also in structural complexity. This discrepancy highlights the gap in the resulting action space complexity between commonly used and real-world benchmarks. RL-GCO solutions. Existing RL approaches fall short of key operational requirements for generalization and scalability in real-world GCO (Fig. 1). Discrete methods rely on padding-based action encodings to handle variable graph sizes, assigning one DNN output unit per action and treating graph elements as index-based entities [Terranova et al., 2025]. This yields instance-specific policies that do not capture action semantics and transfer poorly across graphs. Such approaches provide only partial size invariance—limited by the padding dimension—and require invalid action masking for varying actions. While they also lack permutation invariance and interpolation, they remain computationally efficient due to a one-shot inference. On the other hand, iterative latent action-value methods embed both states and actions—typically using GNNs—and evaluate them sequentially via a learned Q-function [Dai et al., 2017, Manchanda et al., 2020a]. This provides 3

semantic representations, permutation and size invariance (from GNN features), and natural support for varying action sets (only valid actions can be iterated). However, this approach requires a separate forward pass per action, resulting in costs that scale with the action space, which itself can grow super-linearly with graph size in some benchmarks. Moreover, the lack of a continuous representation prevents action interpolation. By contrast, our proposed projection approach predicts a target action embedding, and action selection is shifted to a proper decoding strategy. It combines semantic embeddings with size and permutation invariance (via GNNs), naturally handles varying action sets (restricting decoding only to valid ones), and enables one-shot DNN inference followed by a fast decoding (e.g., NN search can be efficiently indexed for sub-linear retrieval [Arya et al., 1998]). Unlike other methods, it supports interpolation by projecting vectors across the entire manifold, enabling smooth interpolation across actions.

Methodology

After a brief introduction of a novel problem formulation, this section introduces our core contributions: the framework for unsupervised embedding learning, the construction of latent spaces, and the design of projection agents. We conclude with an overview of the supporting LaGCO-RL library. 3.1

Problem formulation

We formulate GCO as a sequential learning problem aimed at constructing a solution on a graph G = (V, E, Vf , Ef ), where V and E denote the sets of nodes and edges, Vf ∈ R|V |×dv encodes node features, and Ef ∈ R|E|×de encodes edge features (with |V | and |E| representing the cardinality of the node and edge sets, respectively, and dv and de their corresponding feature dimensions). Let C(G) denote the decision space of admissible graph substructures (e.g., node subsets, edge subsets, paths, or induced subgraphs). This formulation generalizes beyond single-node decisions, enabling the selection of arbitrary substructures and thus yielding a richer and more challenging action space. In the autoregressive setting, a solution is constructed sequentially as S = (S1 , . . . , ST ), where each decision St ∈ C(G) may depend on previous selections. The full sequence S defines a feasible solution to the GCO problem with objective min F (G, S) s.t.

S∈C(G)T

H(G, S) ≤ 0,

(1)

where F measures the global cost and H encodes optional feasibility constraints. This formulation captures realistic GCO settings in which both F and H may depend on node features, edge features, and higher-order structural interactions. This autoregressive formulation naturally induces a Markov Decision Process (MDP) [Puterman, 1994] with a discrete action space: • Observation. Each observation ot ∈ O represents the intermediate solution at step t, defined as ot = (G, S1 , . . . , St−1 ). • Action. An action at ∈ A(ot ) ⊆ C(G) selects a valid graph substructure that extends the current partial solution. • Transition. The transition deterministically appends the selected substructure to the solution while enforcing constraints H; the episode terminates when a solution is formed, or a cutoff is reached. • Reward. The reward is derived from F (G, S), so maximizing return is equivalent to minimizing the combinatorial objective. For example, in TSP, the observation is a city graph with binary indicators of the current partial tour. The action selects an unvisited city, transitions update the tour, and the reward favors shorter tours. 3.2

Node representation learning

We pre-train a GNN encoder via unsupervised learning to produce node-level embeddings that serve as shared blocks for building both observations and actions of a given RL task. This design (i) decouples representation learning from action selection, enabling fair comparison across RL-GCO methods through shared embeddings; (ii) improves sample efficiency by restricting the policy to observation–action mapping via a lightweight controller [Ha and Schmidhuber, 2018]; and (iii) stabilizes learning by ensuring that action points remain stationary during training so the agent can reliably preserve learned mappings without representational drift. 4

We learn node-level representations using a Graph Auto-Encoder (GAE) [Kipf and Welling, 2016] strategy. A GNN encoder maps each node based on its features and neighborhood to a p-dimensional embedding, forming a matrix Z = hθ (G) ∈ R|V |×p . A feed-forward decoder gϕ reconstructs graph information from Z. The decoder is multi-headed, with separate heads for node features xi ∈ Rdv , edge features eij ∈ Rde when present, and the adjacency matrix A ∈ R|V |×|V | . The encoder–decoder pair is trained jointly (Fig. 2) by minimizing a weighted reconstruction loss over components: 1 X 1 X Lnode (x̂i , xi ) + β Ledge (êij , eij ) + γ Ladj (Â, A), (2) L(θ, ϕ) = α |V | |E| i∈V

(i,j)∈E

where x̂i , êij , and Â are reconstructions produced by gϕ (Z), and α, β, γ control the contribution of each component. Embedding Dimension 2

All terms are normalized by the number of reconstructed elements in order to balance gradient magnitudes across heterogeneous components. Additionally, node and edge features are decomposed by type (binary, categorical, continuous) to enable appropriate normalization and dedicated decoder heads with suitable loss functions (e.g., MSE for continuous features).

Embedding Dimension 1

GAE Encoder

GAE Decoder

We pretrain the GAE on trajectories obtained Valid action by sampling random valid actions, allowing the sampler graph structure to evolve during learning (e.g., trajectories of tours in TSP). This corresponds Figure 2: Joint GNN encoder-decoder framework to maximal valid exploration while remaining leveraging valid action-sampled snapshots for node independent of any learned policy. After conver- representation learning. gence, the decoder is discarded, and the encoder is retained to produce meaningful embeddings. 3.3

Continuous spaces

This subsection describes the solution used to derive proper observation and action spaces from the node embedding set Z derived in Section 3.2. Observation space. We represent each observation as a graph Gt describing the current solution state. A fixed-dimensional observation vector ot is obtained by applying K permutationinvariant graph aggregation operators Pk (e.g., sum, mean, or handcrafted graph statistics) over the node embeddings Zt ∈ R|V |×p , and concatenating the resulting representations: "agent should pick an edge and a node"

GAE Encoder ....

edge

concat

node

identity

subgraph

mean

ot = Φobs (Gt ) =

Pk (Zt ),

(3)

k=1

where Φobs denotesL the observation mapping function and the concatenation operator. This yields a fixed-dimensional, order-invariant graph embedding that summarizes the agent’s observation.

concat

unit -1 0 +1 onehot change

K M

concat

"agent should pick a subgraph and a desired unit change" \

Action space. Actions may target graph components of varying granularity, includFigure 3: Action points’ construction from node embed- ing nodes, edges, paths, subgraphs, or comdings, illustrating two application examples and possi- binations thereof (e.g., edge pairs). An ble operator choices for Φcomb , Φact , and ψ. action a is represented as a set of components C(a) = c1 , . . . , cm , where each component corresponds to a subset of nodes V(ci ) ⊆ V . A component embedding is obtained by aggregating the embeddings of its nodes with a pooling Φcomp : h(ci ) = Φcomp (zj | j ∈ V(ci )). (4) 5

Depending on the application, this operator may be permutation-invariant (e.g., for subgraphs) or permutation-variant (e.g., edges where (i, j) ̸= (j, i)). The action embedding is then obtained by combining embeddings of its components through an aggregation operator Φact (Fig. 3), which again can be permutation-invariant depending on whether component ordering is relevant. u(a) = Φact (h(c1 ), . . . , h(cm )), ci ∈ C(a), (5) In many applications, actions involve not only graph components but also additional non-graph attributes αi , such as discrete options or features associated with graph elements (e.g., in the cybersecurity scenario of Section 4, vulnerabilities are attached to a node and described by text). Depending on the setting, these attributes may either be independent or conditionally determined by previously selected components. These are encoded via a task-specific function ψ(·) and combined as: u(a) = Φact h(c1 ), . . . , h(cm ), ψ(α1 | c1 , . . . , cm ), . . . , ψ(αk | c1 , . . . , αk−1 ) . (6) This unified formulation enables heterogeneous actions typical of real-world applications by embedding both graph components and custom attributes in a shared space. 3.4

Projection agent

The learned action embeddings enable the proposed projection agent by defining a bounded continuous latent action space over all possible action embeddings, onto which the agent projects its decisions. The latent action space U = {u(a1 ), . . . , u(an )} is integrated into the agent through a threestep pipeline: (1) optional preprocessing, such as normalization or dimensionality reduction, while preserving the geometric structure; (2) empirical estimation of the bounds of U across graph instances (min/max per dimension); and (3) alignment of its dimensionality and bounds with the agent’s gym.Box action space (see RL agent in Figure 4). Given an observation ot , the policy π outputs a continuous proto-action in this space ãt = π(ot ) ∈ U, where ãt represents a "desired" target point in latent space rather than a valid discrete action. This proto-action is then decoded by retrieving its k nearest embeddings, forming a candidate set Ak (ot ). A final single action is selected from this set using a proper decoding strategy: e.g., simple NN (k=1), stochastic or rule-based selection, or a learned scoring function over the k-NN candidates. This results in a region-based learning signal in U, where the decoding induces a space partition, and all points within a region map to the same discrete action. As a result, the projection is piecewise constant, and gradients act on the geometry of these regions rather than on individual actions. 3.5

RL-GCO automated framework

This subsection presents our LaGCO-RL library, which imclass LogicEnv(gym.Env) class ContinuousEnv(gym.Env) plements our automated environment construction frameclass ExtendedEnv(LogicEnv, ContinuousEnv) work, and unifies representation learning and latent acget_graphs() tion construction (Sections 3.2-3.4). Users define a stan_node_attributes dard Gym environment encoding the task logic and ex_edge_attributes _action_type tend it via a class inheriting from both ContinuousEnv sample_valid_action() is_valid_action() _observation_type (Fig. 4) and a task-specific base class. The framework class EnvWrapper(gym.Wrapper) is designed to minimize task-specific engineering, requirGAE ing only a small set of high-level attributes and methods Encoder GAE GAE leveraged by a gym.Wrapper module. The graph strucEncoder Decoder ture should be provided through get_graphs(), with stepRL Agent varying attributes, while node and edge encodings are gym.Box defined via _node_attributes and _edge_attributes, enabling automatic construction of decoder heads and loss functions for GNN unsupervised learning, supported by Figure 4: User-defined logic, attributes, sample_valid_action(). Observations are then derived and methods provided for GAE prethrough _observation_type, using pooling-based or cus- training (left) and RL integration (right). tom invariant functions. The action space is specified via _action_type as combinations of proper decision elements; the framework generates the full action set via Cartesian products and optionally filters infeasible actions using is_valid_action(action), allowing time-varying action spaces. The resulting continuous space is exposed as a gym.Box, aligned with the projection agent’s action space, or appropriately wrapped for compatibility in case of other RL strategies. Examples of instantiations are provided in Appendix F. 6

Table 1: Action-space structure across benchmarks, including worst-case growth and the chosen representation function (h denotes the node embedding function). HC indicates benchmarks with hard constraints, where invalid solutions receive a relative score of 0. Benchmark

Action Components

Worst-Case Growth

Representation (h : V → R16 )

TSP (HC) MinVertex (HC) MaxCut

node v (not visited) node v (not visited) node v

O(|V |) O(|V |) O(|V |)

h(v) h(v) h(v)

Placement Cyber-Path

source node u (type=VM) O(|V |2 ) target node v (type=PM) source node u (status=owned) target node v (status=discovered) O(k|V |2 ) vuln α ∈ v

concat(h(u), h(v)) concat(h(u), h(v), BERT(αtext ))

OSPF

edge (u, v) weight change ∆w ∈ {−1, 0, 1}

O(k|V |2 )

Traffic

edge (u, v) (type=traffic) path (u1 , . . . , un ) (type=link)

O(|V |2 2|V | ) pad(concat(h(u), h(v), ..., h(un )))

cmp@3=0.60 cmp@5=0.49 cmp@10=0.28

cmp@3=0.64 cmp@5=0.58 cmp@10=0.48 cmp@3=0.61 cmp@3=0.72 cmp@5=0.52 cmp@5=0.64 cmp@10=0.35 cmp@10=0.44

(a) TSP

concat(h(u), h(v), onehot(∆w))

(b) MinVertex

cmp@3=0.34 cmp@3=0.58 cmp@5=0.26 cmp@5=0.54 cmp@10=0.18 cmp@10=0.47

(d) Placement (e) Cyber-Path

(f) OSPF

cmp@3=0.69 cmp@5=0.65 cmp@10=0.60

(g) Traffic

Figure 5: UMAP projection of benchmark action spaces for a 20-node graph instance, illustrating local geometry and neighborhood proximity with the cmp@k (k ∈ 3, 5, 10) (computed on 20 instances).

Experiments

Benchmark environments. We evaluate our approach on seven GCO benchmarks. This includes three standard problems with node-level decisions and linearly growing action spaces—TSP, MinVertex, and Maximum Cut ( ) [Bodlaender and Jansen, 2000]; the latter is of particular importance, as morer than half of the 21 Karp’s canonical CO problems are reducible to MaxCut [Barrett et al., 2020]. In addition, we consider four application-driven tasks drawn from delay-sensitive domains (networking and cybersecurity): Virtual Machine Placement (Placement) [Caviglione et al., 2021], Cyber-Attack Path Prediction (Cyber-Path) [Terranova et al., 2025], OSPF, and Traffic. Unlike classical benchmarks, these tasks involve structured actions combining graph and non-graph entities, while involving super-linear growth in the action space. Table 1 summarizes their action components, the expected growth of the action space, and the structured action representations used for each benchmark. It also highlights that TSP and MinVertex impose hard validity constraints, requiring sequential selection of previously unvisited nodes; any violation leads to an invalid solution with zero score. Additional details on the logic of each environment, the episode structure, the score function, and the graph features are provided in Appendix B. Observation: Figure 5 shows 2D UMAP [Healy and McInnes, 2024] projections of action spaces for 20-node benchmarks. We quantify complexity using compactness, cmp@K, defined as the ratio of the mean pairwise distance to the k-NN distance (k ∈ 3, 5, 10), averaged over 20 instances. Real-world benchmarks exhibit higher cmp, indicating denser neighborhoods and greater overlap. During scenario generation, we perform an extended empirical sweep inspired by [Dai et al., 2017] (e.g., 10k sweeps for TSP) to approximate worst- and best-case GCO solutions via standard heuristicguided exploration for each instance (see Appendix D for details). This produces a normalized reference score in [0, 1], which mitigates scale effects (e.g., distance-dependent costs in TSP), enables per-step relative rewards to alleviate the challenges of sparse episodic rewards [Barrett et al., 2020] (see Appendix B), and ensures comparability and aggregation across instance scores. 7

Models & baselines. We compare the three RL-GCO approaches from Section 2. Discrete baselines are evaluated with two observation encodings—padding (P-, permutation-variant) and GNNbased (G-, permutation-invariant pooling)—with (-M) and without action masking, using PPO and MaskablePPO from SB3 respectively. Our projection method uses PPO for fair comparison, operating in a z-score–normalized action space with (K=1)-NN decoding, corresponding to the most challenging high-precision setting in which exact actions must be recovered through accurate latent-space projections alone. We also include the iterative solution, implemented via the extension of SB3’s fitted Q-iteration DQN (re-implemented due to lack of availability of this solution in existing Python RL libraries). Both latent methods are evaluated over valid actions only (masking strategy). Observation: We restrict comparisons to RL-based baselines to evaluate performance in a purely auto-regressive, data-driven setting, excluding supervised and relaxation-based methods that rely on existing labels or struggle with feasibility constraints typical of the studied benchmarks (see Appendix A). However, to contextualize solution quality, we report scores normalized against heuristic solutions obtained through exhaustive iterative search over thousands of iterations for each scenario. Hyperparameter tuning. Solution-specific hyperparameters, along with those governing the GAE and its architecture, are optimized using the Tree-structured Parzen Estimator (TPE) [Watanabe, 2025] for 25 trials each. The objective is task-specific performance evaluated on a held-out validation set, considering only the TSP benchmark for simplicity. The complete search spaces, details of the lightweight neural controller used for the agent, random seeds, and all hyperparameter configurations are provided in Appendix C, while the design of the observation spaces is presented in Appendix G. 4.1

How well do RL-GCO approaches generalize across graph distributions?

Experimental design. For each benchmark, we generate 101 diverse scenario instances by sampling key parameters from the typical distributions of each benchmark, in order to evaluate the out-ofdistribution generalization capabilities [Kumar et al., 2020] of the methods across varying instance sizes and training configurations. Scenarios are then ordered by size and evaluated under four transfer-oriented training strategies. In the first three, agents train on a single scenario based on their size—smallest (S), medium (M), or largest (L)—and are tested on all remaining instances; each strategy is repeated K = 5 times with different seeds and scenarios (removing those already selected from the selection pool). The fourth, varied (V), adopts a K-fold-inspired approach: agents are trained on five non-overlapping subsets of scenarios (20%), with training instances rotated every 100 episodes. For each run, performance is assessed over 5 episodes per unseen instance (80% for V, 100 instances for S, M, and L), with the best result retained; aggregated outcomes across 20 runs per solution–benchmark pair are reported in Table 2. We report the Interquartile Mean (IQM) over these 100 best scores, following the guidelines on suitable RL indicators from Agarwal et al. [2021]. Additionally, the ∆ columns report the test-to-training gap (averaged across strategies) for each method. The training times associated with the methods are also reported and discussed in Appendix H. Analysis. Table 2 shows that, on hard-constrained classical tasks, discrete-action methods consistently underperform relative to both projection (ours) and iterative approaches, highlighting the advantage of GNN-based semantic embeddings for action selection. The iterative framework achieves the best performance on TSP, reaching empirical maxima comparable to those obtained with 10k heuristic sweeps, despite using only five trials per instance. This highlights the ability of RL agents to match strong heuristic baselines under limited evaluation budgets (5 trials). On MinVertex and MaxCut, projection outperforms iterative, and the limitations of the latter become dramatically more pronounced in realistic benchmarks. As action spaces grow superlinearly, the method struggles to produce reliable Q-value estimates, leading to degraded performance that falls even below discrete baselines. In contrast, the projection agent remains stable across settings, achieving the strongest performance on applied benchmarks while remaining competitive on classical ones. The projection approach shows the best overall trade-off between test performance and ∆ values, which capture transfer capability (through low magnitude values), particularly on realistic benchmarks. Finally, the impact of training scale reveals a consistent pattern. On classical benchmarks, the optimal regime is typically S when using the projection agent, with no clear benefit from more dense or varied action spaces. In contrast, V emerges as the most effective regime for real-world benchmarks, suggesting that projection can support improvements from the exposure to diverse and heterogeneous 8

Table 2: IQM of the normalized generalization score across test benchmarks and training strategies (S: small, M: medium, L: large, V: varied). ∆ denotes the average train–test generalization gap. Underlined bold values indicate the best-performing method per benchmark, with projection (ours) achieving the strongest performance on most benchmarks. Method

TSP L V

∆

MinVertex M L V

∆

MaxCut L V

∆

P-Discrete 0.00 0.00 0.00 0.00 +0.00 0.00 0.00 0.00 0.21 -0.63 0.90 0.89 0.85 0.34 +0.07 P-Discrete-M 0.50 0.47 0.47 0.48 -0.05 0.00 0.05 0.16 0.36 -0.54 0.91 0.90 0.39 0.27 +0.09 G-Discrete 0.00 0.00 0.00 0.00 -0.05 0.00 0.00 0.06 0.02 -0.29 0.00 0.89 0.90 0.89 -0.26 G-Discrete-M 0.51 0.50 0.50 0.50 -0.19 0.00 0.07 0.16 0.11 -0.24 0.00 0.90 0.91 0.90 -0.25 Iterative 0.90 0.79 0.97 0.99 -0.04 0.39 0.07 0.00 0.15 -0.19 0.92 0.85 0.80 0.82 +0.00 Projection (ours) 0.78 0.76 0.60 0.71 -0.13 0.63 0.00 0.03 0.08 -0.22 0.95 0.95 0.92 0.94 -0.01 Method

Placement M L V

∆

Cyber-Path M L V

∆

OSPF L V

∆

Traffic L V

∆

P-Discrete 0.55 0.52 0.38 0.55 -0.36 0.19 0.18 0.19 0.18 -0.05 0.20 0.04 0.00 0.07 -0.31 0.26 0.49 0.10 0.20 -0.30 P-Discrete-M 0.64 0.65 0.66 0.65 -0.29 0.61 0.63 0.61 0.67 -0.20 0.07 0.39 0.25 0.01 -0.16 0.41 0.73 0.74 0.76 -0.10 G-Discrete 0.11 0.40 0.49 0.34 -0.49 0.18 0.19 0.18 0.17 -0.05 0.16 0.13 0.14 0.52 -0.63 0.24 0.57 0.49 0.62 -0.39 G-Discrete-M 0.07 0.36 0.60 0.51 -0.53 0.45 0.45 0.51 0.50 -0.28 0.26 0.38 0.64 0.67 -0.41 0.73 0.73 0.78 0.78 -0.15 Iterative 0.39 0.12 0.03 0.15 -0.10 0.34 0.24 0.19 0.24 -0.22 0.00 0.03 0.00 0.00 -0.20 0.00 0.00 0.00 0.00 -0.20 Projection (ours) 0.85 0.88 0.86 0.91 -0.10 0.60 0.64 0.60 0.67 -0.17 0.68 0.78 0.84 0.88 -0.12 0.80 0.80 0.81 0.83 -0.05

action spaces (not always seen for V with other approaches). An extended analysis of generalization, including additional indicators and variability measures, is provided in Appendix J. 4.2

How does inference time scale with graph size?

TSP

20 10600 140 180 220 260 300 340 380 420 460 500

Action Time (s)

Experimental design. We study computational Iterative TSP Placement Projection (ours) 10 1 scalability by analyzing how action-selection time scales with graph size for both the proposed GNN10 2 based projection method—using a FAISS Flat In10 3 dex for NN lookup with linear retrieval complexity [Johnson et al., 2019]—and iterative methods, Graph Size Graph Size on a benchmark machine.3 Specifically, we fit a power-law model T (n) = c · nα where T (n) is Figure 6: Evolution of inference-time actionthe median action-selection time for a graph of selection latency across graph sizes for the repsize n, and α is the scaling exponent. The discrete resentative TSP and Placement benchmarks. baselines perform a single DNN inference without additional operations, resulting in near-constant Projection runtime as graph size increases; they are therefore (ours) Iterative omitted from this analysis. Env α R2 α R2 0.17 0.85

0.25 0.94

MinVertex 0.30 0.88 0.32 0.95 Analysis. Table 3 reports the estimated exponent MaxCut 0.22 0.94 0.25 0.92 2 α (with corresponding R values) across benchPlacement 0.22 0.85 1.81 0.99 marks, providing a concise characterization of how Cyber-Path 0.09 0.76 1.46 0.95 inference cost increases with problem size, alongOSPF 0.49 0.94 1.44 0.99 side two full example curves (TSP and Placement) Traffic 0.73 0.71 4.68 0.99 in Figure 6; the rest can be found in Appendix I. The results highlight the computational advantage Table 3: Scaling of action-selection time with of the projection approach (ours) with a simple fitted power-law exponent α. Lower α indicates NN search rather than evaluating a DNN over all better scaling with graph size. Bold values decandidate actions. This distinction becomes critnote the best scaling behavior of our projection ical in the proposed delay-sensitive benchmarks, method across benchmarks. where the action space grows superlinearly; in such settings, the iterative method quickly reaches practical limits even at moderate scales, while the projection agent can better handle their challenges. 3 Benchmark Machine: AMD Ryzen 7 PRO 7840U w/ Radeon 780M Graphics, 30Gi RAM, Ubuntu 22.04.4

Discussion

Conclusion. We introduce an end-to-end framework for learning latent action spaces for RL-GCO, along with a projection-based approach to navigate them, improving generalization and scalability. We also design a suite of benchmarks that capture more realistic action-space structures, reflecting realworld conditions. Experimental results show that the proposed approach has consistent generalization improvements in these real-world benchmarks. To support reproducibility and future research, we release LaGCO-RL, a modular library that facilitates the integration of new GCO benchmarks. Limitations. (1) We restrict our design to a single encoding per action-space component and a single decoding strategy for the projection agent, selected empirically from a limited set of alternatives. (2) The unsupervised embeddings are not fine-tuned for downstream RL, ensuring fair comparison but potentially limiting peak performance. (3) Our evaluation, while representative, is not exhaustive (101 scenarios and 20 runs each), and we focus only on RL-based methods, reporting scores normalized against strong exhaustive heuristics rather than comparing to the full range of non-RL approaches.

Acknowledgments This work has been partially supported by the French National Research Agency under the France 2030 label (Superviz ANR-22-PECY-0008). The views reflected herein do not necessarily reflect the opinion of the French government. This work was supported partly by the French PIA project "Lorraine Université d’Excellence", reference ANR-15-IDEX-04-LUE.

References Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron Courville, and Marc G. Bellemare. Deep reinforcement learning at the edge of the statistical precipice. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NeurIPS ’21, Red Hook, NY, USA, 2021. Curran Associates Inc. ISBN 9781713845393. doi: 10.48550/arXiv.2108.13264. Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, and Angela Y. Wu. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. J. ACM, 45(6):891–923, November 1998. ISSN 0004-5411. doi: 10.1145/293347.293348. Thomas D. Barrett, William R. Clements, Jakob N. Foerster, and Alex I. Lvovsky. Exploratory combinatorial optimization with reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), volume 34, pages 3243–3250. Association for the Advancement of Artificial Intelligence, 2020. doi: 10.1609/aaai.v34i04.5723. Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: A methodological tour d’horizon. European Journal of Operational Research, 290(2):405–421, 2021. ISSN 0377-2217. doi: 10.1016/j.ejor.2020.07.063. Guillermo Bernárdez, José Suárez-Varela, Albert López, Xiang Shi, Shihan Xiao, Xiangle Cheng, Pere Barlet-Ros, and Albert Cabellos-Aparicio. Magnneto: A graph neural network-based multiagent system for traffic engineering. IEEE Transactions on Cognitive Communications and Networking, 9(2):494–506, 2023. doi: 10.1109/TCCN.2023.3235719. Hans L. Bodlaender and Klaus Jansen. On the complexity of the maximum cut problem. Nordic J. of Computing, 7(1):14–31, March 2000. ISSN 1236-6064. doi: 10.5555/640044.640046. Quentin Cappart, Didier Chételat, Elias B. Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pages 4348–4355. International Joint Conferences on Artificial Intelligence Organization, 2021a. doi: 10.24963/ijcai.2021/595. Survey Track. Quentin Cappart, Thierry Moisan, Louis-Martin Rousseau, Isabeau Prémont-Schwarz, and Andre A. Cire. Combining reinforcement learning and constraint programming for combinatorial optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 35(5):3677–3687, May 2021b. doi: 10.1609/aaai.v35i5.16484. 10

Luca Caviglione, Mauro Gaggero, Massimo Paolucci, and Roberto Ronco. Deep reinforcement learning for multi-objective placement of virtual machines in cloud datacenters. Soft Comput., 25 (19):12569–12588, October 2021. ISSN 1432-7643. doi: 10.1007/s00500-020-05462-x. Yu Chen, Yingfeng Chen, Zhipeng Hu, Tianpei Yang, Changjie Fan, Yang Yu, and Jianye Hao. Learning action-transferable policy with action embedding. 2021. doi: 10.48550/arXiv.1909.02291. Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NeurIPS’17, page 6351–6361, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964. doi: 10.48550/arXiv.1704.01665. Victor-Alexandru Darvariu, Stephen Hailes, and Mirco Musolesi. Graph reinforcement learning for combinatorial optimization: A survey and unifying perspective. 2024. doi: 10.48550/arXiv.2404. 06492. Irit Dinur and Samuel Safra. On the hardness of approximating minimum vertex cover. Annals of mathematics, pages 439–485, 2005. doi: 10.4007/annals.2005.162.439. Gabriel Dulac-Arnold, 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. 2016. doi: 10.48550/arXiv.1512.07679. Andoni I. Garmendia, Josu Ceberio, and Alexander Mendiburu. Neural improvement heuristics for graph combinatorial optimization problems. IEEE Transactions on Neural Networks and Learning Systems, 35(12):18300–18312, 2024. doi: 10.1109/TNNLS.2023.3314375. Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. Curran Associates Inc., Red Hook, NY, USA, 2019. doi: 10.5555/3454287.3455683. David Ha and Jürgen Schmidhuber. Recurrent world models facilitate policy evolution. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. doi: 10.48550/ arXiv.1809.01999. John Healy and Leland McInnes. Uniform manifold approximation and projection. Nature Reviews Methods Primers, 4(1):82, 2024. doi: 10.21105/joss.00861. Nasimeh Heydaribeni, Xinrui Zhan, Ruisi Zhang, Tina Eliassi-Rad, and Farinaz Koushanfar. Distributed constrained combinatorial optimization leveraging hypergraph neural networks. Nature Machine Intelligence, 6(6):664–672, 2024. ISSN 2522-5839. doi: 10.1038/s42256-024-00833-7. Ahmed Hussein, Mohamed Medhat Gaber, Eyad Elyan, and Chrisina Jayne. Imitation learning: A survey of learning methods. ACM Comput. Surv., 50(2), April 2017. ISSN 0360-0300. doi: 10.1145/3054912. Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3):535–547, 2019. doi: 10.1109/TBDATA.2019.2921572. Michael Jünger, Gerhard Reinelt, and Giovanni Rinaldi. Chapter 4 the traveling salesman problem. In Network Models, volume 7 of Handbooks in Operations Research and Management Science, pages 225–330. Elsevier, 1995. doi: 10.1016/S0927-0507(05)80121-5. Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NeurIPS ’20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546. doi: 10.48550/arXiv.2006.10643. Richard M. Karp. Reducibility among Combinatorial Problems, pages 85–103. Springer US, Boston, MA, 1972. ISBN 978-1-4684-2001-2. doi: 10.1007/978-1-4684-2001-2_9. Elias B. Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI’16, page 724–731. AAAI Press, 2016. doi: 10.5555/3015812.3015920. 11

Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308, 2016. doi: 10.48550/arXiv.1611.07308. Saurabh Kumar, Aviral Kumar, Sergey Levine, and Chelsea Finn. One solution is not all you need: Few-shot extrapolation via structured maxent rl. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 8198–8210. Curran Associates, Inc., 2020. doi: 10.48550/arXiv.2010.14484. Kaiwen Li, Tao Zhang, Rui Wang, Yuheng Wang, Yi Han, and Ling Wang. Deep reinforcement learning for combinatorial optimization: Covering salesman problems. IEEE Transactions on Cybernetics, 52(12):13142–13155, 2022. doi: 10.1109/TCYB.2021.3103811. Zhi-Peng Li, Si-Guo Wang, Qin-Hu Zhang, Yi-Jie Pan, Nai-An Xiao, Jia-Yang Guo, Chang-An Yuan, Wen-Jian Liu, and De-Shuang Huang. Graph pooling for graph-level representation learning: a survey. Artificial Intelligence Review, 58(2):45, 2024. doi: 10.1007/s10462-024-10949-2. Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NeurIPS’18, page 537–546, Red Hook, NY, USA, 2018. Curran Associates Inc. doi: 10.5555/3326943.3326993. Yixin Liu, Yu Zheng, Daokun Zhang, Hongxu Chen, Hao Peng, and Shirui Pan. Towards unsupervised deep graph structure learning. In Proceedings of the ACM Web Conference 2022, WWW ’22, page 1392–1403, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450390965. doi: 10.1145/3485447.3512186. Sahil Manchanda, Akash Mittal, Anuj Dhawan, Sourav Medya, Sayan Ranu, and Ambuj Singh. Gcomb: Learning budget-constrained combinatorial algorithms over billion-sized graphs. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 20000–20011. Curran Associates, Inc., 2020a. doi: 10.5555/3495724.3497403. Sahil Manchanda, Akash Mittal, Anuj Dhawan, Sourav Medya, Sayan Ranu, and Ambuj Singh. Learning heuristics over large graphs via deep reinforcement learning. 2020b. doi: 10.48550/arXiv. 1903.03332. Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research, 134:105400, 2021. ISSN 0305-0548. doi: 10.1016/j.cor.2021.105400. Mingshuo Nie, Dongming Chen, and Dongqi Wang. Reinforcement learning on graphs: A survey. IEEE Transactions on Emerging Topics in Computational Intelligence, 7(4):1065–1082, 2023. doi: 10.1109/TETCI.2022.3222545. Yifan Peng, Byungki Choi, and Jun Xu. Graph learning for combinatorial optimization: A survey of state-of-the-art. Data Science and Engineering, 6:119–141, 2021. doi: 10.1007/ s41019-021-00155-3. Martin L. Puterman. Markov decision processes: Discrete stochastic dynamic programming. USA, 1994. John Wiley & Sons, Inc. ISBN 0471619779. doi: 10.5555/528623. Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dormann. Stable-baselines3: Reliable reinforcement learning implementations. Journal of Machine Learning Research, 22(268):1–8, 2021. doi: 10.5555/3546258.3546526. Sebastian Sanokowski, Wilhelm Berghammer, Sepp Hochreiter, and Sebastian Lehner. Variational annealing on graphs for combinatorial optimization. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NeurIPS ’23, Red Hook, NY, USA, 2023. Curran Associates Inc. doi: 10.5555/3666122.3668914. Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61–80, 2009. doi: 10.1109/TNN.2008.2005605. 12

Martin J. A. Schuetz, J. Kyle Brubaker, and Helmut G. Katzgraber. Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence, 4(4):367–377, 2022. ISSN 2522-5839. doi: 10.1038/s42256-022-00468-6. Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimization. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 3706–3731. Curran Associates, Inc., 2023. doi: 10.5555/3666122.3666286. Franco Terranova, Abdelkader Lahmadi, and Isabelle Chrisment. Scalable and generalizable rl agents for attack path discovery via continuous invariant spaces. In 2025 28th International Symposium on Research in Attacks, Intrusions and Defenses (RAID), pages 440–457, 2025. doi: 10.1109/RAID67961.2025.00029. Hado van Hasselt and Marco A. Wiering. Using continuous action spaces to solve discrete problems. In 2009 International Joint Conference on Neural Networks, pages 1149–1156, 2009. doi: 10. 1109/IJCNN.2009.5178745. Natalia Vesselinova, Rebecca Steinert, Daniel F. Perez-Ramirez, and Magnus Boman. Learning combinatorial optimization on graphs: A survey with applications to networking. IEEE Access, 8: 120388–120416, 2020. doi: 10.1109/ACCESS.2020.3004964. Haoyu Wang, Nan Wu, Hang Yang, Cong Hao, and Pan Li. Unsupervised learning for combinatorial optimization with principled objective relaxation. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NeurIPS ’22, Red Hook, NY, USA, 2022. Curran Associates Inc. ISBN 9781713871088. doi: 10.5555/3600270.3602550. Runzhong Wang, Zhigang Hua, Gan Liu, Jiayi Zhang, Junchi Yan, Feng Qi, Shuang Yang, Jun Zhou, and Xiaokang Yang. A bi-level framework for learning to solve combinatorial optimization on graphs. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NeurIPS ’21, Red Hook, NY, USA, 2021a. Curran Associates Inc. ISBN 9781713845393. doi: 10.5555/3540261.3541902. Runzhong Wang, Tianqi Zhang, Tianshu Yu, Junchi Yan, and Xiaokang Yang. Combinatorial learning of graph edit distance via dynamic embedding. In IEEE Conference on Computer Vision and Pattern Recognition, 2021b. Shuhei Watanabe. Tree-structured parzen estimator: Understanding its algorithm components and their roles for better empirical performance. 2025. doi: 10.48550/arXiv.2304.11127. Yang Xiao, Jun Liu, Jiawei Wu, and Nirwan Ansari. Leveraging deep reinforcement learning for traffic engineering: A survey. IEEE Communications Surveys & Tutorials, 23(4):2064–2097, 2021. doi: 10.1109/COMST.2021.3102580.

Related work: beyond RL solutions

Several ML paradigms have been proposed for data-driven heuristic discovery in GCO. This section reviews the most relevant approaches according to their underlying learning paradigm. Supervised learning. Supervised approaches have been extensively studied in the literature, with recent advances including end-to-end methods that directly generate complete solutions—for example, diffusion-based models [Sun and Yang, 2023]—as well as neural improvement heuristics [Garmendia et al., 2024]. The latter departs from full solution construction by adopting an iterative refinement strategy, where existing solutions are progressively improved through local decisions. This shift simplifies the learning problem while still achieving competitive performance. However, these methods inherently rely on labeled solutions, which are often costly or infeasible to obtain with exact methods for large-scale instances [Wang et al., 2021a]. As a consequence, in practice, labels are typically generated using existing manually defined heuristics, introducing an inherent performance ceiling: models are trained to mimic potentially suboptimal solutions and cannot surpass this upper bound [Cappart et al., 2021a, Sanokowski et al., 2023]. Unsupervised learning. Unsupervised methods, similar to RL, do not require labeled data and instead optimize the problem objective directly [Peng et al., 2021]. A common strategy is to relax these discrete optimization problems into continuous formulations via concave surrogate losses, which are optimized in an unsupervised manner [Sanokowski et al., 2023, Wang et al., 2022]. These approaches have been explored using various architectures, including GNNs [Karalias and Loukas, 2020], hypergraph neural networks [Heydaribeni et al., 2024], physics-informed neural networks [Schuetz et al., 2022], and variational annealing [Sanokowski et al., 2023]. Despite their promise, unsupervised approaches face several challenges. Their generalization capabilities remain insufficiently explored, complex constraints are difficult to incorporate [Wang et al., 2021a], and models may converge to suboptimal local minima [Heydaribeni et al., 2024]. Additionally, reliance on continuous relaxations introduces approximation gaps that can degrade solution quality and complicate optimization [Cappart et al., 2021a]. Reinforcement learning. In contrast to other approaches, RL optimizes the objective through sequential decision-making, relying on step-wise evaluative feedback rather than fixed supervision over entire trajectories, as in supervised learning or imitation learning [Hussein et al., 2017]. Instead of using static labels for complete solutions, RL leverages reward signals to assess the quality of actions over time. This framework enables agents to go beyond the limitations imposed by predefined datasets and known reference solutions. However, the key challenge of RL lies in the inherently sparse reward structure of GCO problems, where meaningful evaluations are typically only available at the end of an episode, making training difficult [Sanokowski et al., 2023, Wang et al., 2021a]. Prior work has addressed this limitation by introducing intermediate reward signals to alleviate sparsity and improve learning efficiency [Barrett et al., 2020]. A similar idea is adopted in this work, which leverages the worst- and best-known solutions to compute step-wise improvement signals, thereby providing a denser reward for more effective learning. Hybrid approaches. Hybrid methods have been proposed to combine learning-based and classical optimization techniques for solving GCO problems. In learning-assisted optimization, several works have proposed neural models able to guide traditional solvers, such as learning heuristics for A* search [Wang et al., 2021b] or branching strategies in branch-and-bound [Gasse et al., 2019, Khalil et al., 2016]. Similar ideas have also been explored using RL [Cappart et al., 2021b]. Another study proposed a bi-level framework in which RL reduces the problem space before applying a fast heuristic for refinement [Wang et al., 2021a]. More recently, hybrid learning approaches combine multiple ML paradigms to further improve the learning-based solution. For instance, supervised learning can be used to prune the search space explored by RL policies [Manchanda et al., 2020a], improving scalability to large graphs. However, such methods reintroduce the limitations of supervised learning, as their effectiveness depends on the quality of the initial labels. Nevertheless, these approaches remain complementary and can be naturally integrated into all RL-based frameworks, including the one proposed in this work. 14

Benchmark environments

This section describes the benchmark environments used in the experimental study (Section 4) in terms of logic and dynamics, their graph representations, and the score used for solution evaluation. The reward function structure is shared across the benchmarks and defined based on empirically estimated worst-case and best-case scores for each instance as the relative improvement with respect to these strategies, normalized in [0,1]. This normalization provides a consistent learning signal across benchmarks, guiding the agent toward higher-quality solutions. The resulting reward is not strictly bounded and may exceed 1. During training, the best-known score is additionally used as a termination criterion to accelerate convergence. However, this mechanism is removed at test time to avoid drawbacks of supervised solutions (as explained in Appendix A). B.1

Traveling salesman problem

Logic: Construct a minimum-length tour that visits each city exactly once (hard constraint). • Parameters: Number of cities N and coordinate range defining (x, y) positions. • Graph: Nodes represent cities, and edges encode distances. The graph is fully connected but sparsified by retaining the K = 10 NNs per node to avoid a fully connected graph that would find issues with GNN embeddings. • Node features: Visited flag ∈ {0, 1} and spatial coordinates (x, y). • Edge features: Euclidean distances between cities. • Reset: A starting city is randomly selected and marked as visited, while all others remain unvisited. • Step helper: The selected next city is appended to the tour, removed from the action space, and marked as visited. • Termination: The episode ends once all N cities have been visited. • Reward: Total length of the constructed tour in terms of the sum of Euclidean distances, normalized as a relative score. If incomplete, remaining cities are inserted (padding) using a worst-case heuristic (e.g., farthest insertion with respect to last city) to estimate final cost, ensuring the agent prioritizes the completion of the tour. • Score: Zero if the tour does not cover all cities exactly once; otherwise, the score is the tour length normalized between best and worst (empirically) known solutions. B.2

Minimum vertex cover

Logic: Select the smallest subset of nodes such that every edge is incident to at least one selected node (hard constraint). • Parameters: Number of nodes N and edge probability p. • Graph: Erdős–Rényi random graph where edges must be covered by selected nodes. • Node features: Binary selected flag ∈ {0, 1}. • Edge features: Binary covered flag ∈ {0, 1}. • Reset: All nodes are initialized as unselected and all edges as uncovered. • Step helper: Selecting a node marks it as used, removes it from the action space, and updates newly incident edges as covered. • Termination: The episode ends when all edges are covered or a predefined cutoff is reached. • Reward: Number of newly covered edges, with a penalty proportional to the size of the selected covered nodes (normalized to a relative score). • Score: Zero if coverage is incomplete; otherwise, normalized cover size relative to best and worst (empirically) known solutions. 15

B.3

Maximum cut

Logic: Partition nodes into two sets to maximize the total weight of edges crossing between partitions. • Parameters: Number of nodes N and edge weight range. • Graph: Weighted graph with weights randomly sampled across every pair of nodes. The graph is sparsified by retaining K = 10 NN per node to avoid a fully connected graph that would find issues with GNN embeddings. • Node features: Partition assignment ∈ {0, 1}. • Edge features: Edge weight as scalar value. • Reset: All nodes are initially assigned to partition 0. • Step helper: A node is moved to the complementary partition (inspired by Barrett et al. [2020]), updating the cut structure accordingly. • Termination: The episode ends when the (empirically) known best cut is reached (only during training) or a cutoff is exceeded. • Reward: Incremental change in cut value based on whether edges become crossing or internal (normalized to a relative score). • Score: Normalized cut value between best and worst (empirically) known solutions. B.4

Virtual machine placement

Logic: Assign virtual machines (VMs) to physical machines (PMs) to jointly optimize utilization, energy efficiency, packing efficiency, load balancing, and security risk (representing the attack surface), all under capacity constraints. • Parameters: Number of VMs, PMs, tenants; VM resource demands (CPU, MIPS, RAM, storage); PM capacities; traffic, latency, energy, and security characteristics. • Graph: Nodes represent VMs and PMs; edges encode allocation (VM → PM), VM-to-VM traffic, and PM-to-PM latency. • Node features: VM nodes encode resource requirements, while PM nodes encode utilization and power consumption. • Edge features: Traffic demands and latency values. • Reset: System initialized with the (empirically) known worst allocation to ensure the exploration of a large set of positive action sequences. • Step helper: A (VM, PM) assignment is validated against capacity constraints and applied if feasible. • Termination: Episode ends when an (empirically) known optimal allocation is reached (only during training) or a cutoff is exceeded. • Reward: Weighted variation of normalized metrics plus migration cost. • Score: Weighted sum of the final normalized metric values. B.5

OSPF engineering

Logic: Adjust link weights to minimize congestion by reducing maximum link utilization under routing constraints. • Parameters: Number of nodes, capacity range, traffic range, weight bounds, graph distribution, and Equal-cost multi-path routing (ECMP) routing flag. • Graph: Spanning graph with undirected communication edges and directed traffic flows. • Node features: Aggregated incoming and outgoing traffic (to avoid an empty feature vector, needed for GNNs). • Edge features: Capacity, utilization, weight, and traffic load. 16

• Reset: Initialized with the (empirically) known worst-case weight configuration to ensure the exploration of a large set of positive action sequences. • Step helper: Modify a link weight within bounds and recompute routing and utilization (according to ECMP usage). • Termination: Episode ends when the (empirically) known optimal configuration is reached (only during training) or a cutoff is exceeded. • Reward: Change in maximum link utilization. • Score: Reduction in maximum link utilization relative to the initial configuration. B.6

Traffic engineering

Logic: Route traffic demands through feasible paths to minimize congestion while respecting capacity constraints. This represents a variant of OSPF engineering without relying on OSPF as an intermediary helper. • Parameters: Number of nodes, capacity range, traffic characteristics, graph distribution, and maximum path length (filtering set of communication paths to be used as solutions to a maximum, and avoiding solutions unlikely to be optimal). • Graph: Spanning graph with communication and traffic edges. • Node features: Aggregated incoming and outgoing traffic (to avoid an empty feature vector, needed for GNNs). • Edge features: Capacity, utilization, and traffic load. • Reset: Initialized with the (empirically) known worst-case allocation configuration to ensure the exploration of a large set of positive action sequences. • Step helper: Assign traffic demands to feasible paths while respecting capacity constraints. • Termination: Episode ends when (empirically) known optimal routing is achieved (only during training) or a cutoff is exceeded. • Reward: Change in maximum link utilization. • Score: Reduction in maximum link utilization relative to the initial configuration. B.7

Cyber-attack path prediction

Logic: Predict critical multi-step attack paths in a networked environment by sequentially exploiting vulnerabilities distributed across interconnected host nodes. The agent models an attacker operating under partial observability, incrementally discovering the network topology as it progresses. Formulated as a Partially Observable MDP, this setting captures the uncertainty inherent to real-world reconnaissance and lateral movement. • Parameters: Number of nodes, vulnerabilities per node, communication probability distribution (modeling possible remote exploitation), visibility probability distribution, detection probability distribution (modeling failure rates), and attack-related parameters. • Graph: Dynamic attack graph with progressively discovered nodes and edges representing already executed attack actions (attack history representation). • Node features: Aggregated service/vulnerability BERT embeddings (order- and sizeinvariant poolings), visibility, compromise status, privilege level, data presence, exfiltration status, persistence, DoS, and defense evasion flags. • Edge features: Vulnerability BERT embeddings encoded to represent actions selected. Pooled under the same edge if multiple vulnerabilities are used between the same sourcetarget pair. • Reset: Start from a randomly compromised node with partial visibility of its neighborhood. • Step helper: Given a (source, target, vulnerability) action, validate exploitability constraints, update node states, and expand the graph and the action space when new nodes are discovered. 17

• Termination: Episode ends when all nodes are compromised, or a cutoff is reached. • Reward: Outcome-driven rewards aligned with attacker objective representing a "control" threat model (i.e., credential access positive, detection, or DoS negative). • Score: Total percentage of compromised nodes.

Hyper-parameter optimization Learning Rate

Batch γ Size

Discrete PPO

0.00001, 0.0001, 0.001

32, 64, 128

Projection PPO

0.00001, 0.0001, 0.001

Iterative IDQN

0.00001, 0.00005, 0.0001

GAE

0.00005, 16, – 0.0001, 32, 64 0.001, 0.01, 0.05

N Steps

Ent Coef

Max Grad Norm

Tau

Target Update Interval

Num Layers

NN Channels

Out Channels

Activation

0.9, 0.95, 0.99

512, 1024, 2048

0.01, 0.1, 0.2

0.1, 0.3, 0.5

–

32, 64, 128

0.9, 0.95, 0.99

512, 1024, 2048

0.01, 0.1, 0.2

0.1, 0.3, 0.5

–

32, 64, 128

0.9, 0.95, 0.99

1, 3, 5

–

0.01, 2000, 0.05, 5000, 0.1 10000

–

2, 3

16, 32

16, 64

–

32, LeakyReLU, ReLU, null

Table 4: Hyperparameter ranges explored for each method with best configurations in bold. Table 4 reports the hyperparameter search space explored for each optimized model, along with the best configuration identified. The hyperparameter optimization was conducted exclusively on the TSP benchmark for simplicity, using 25 trials for each model. Regarding discrete solutions, this process has been performed only on the P-Discrete-M variant for simplicity, and hyperparameters were used across all other discrete variants. The following additional hyperparameters were tuned manually and selected based on empirical evaluation: • Node embeddings dimensionality: 16 • Nearest neighbor search (action space): FAISS Flat Index • Distance metric (action space search): Cosine similarity • Action vector processing: – No normalization in the iterative approach – Z-score normalization in the projection approach (ensures projection outputs remain within a suitable range for policy-based methods) • Action space bounds: Extended by a margin of (−1, +1) (to the z-score bounds) relative to the empirical latent space range discovered across the training instances per benchmark • Episode length: To maintain consistency across varying problem scenarios, the episode length is scaled proportionally to the instance complexity. Concretely, it is defined as a coefficient multiplied by the number of decision variables (e.g., number of VMs in Placement), ensuring that agents are given sufficient interaction steps with respect to scenario size: – Default: 1× scenario size – Cyber-Path / traffic scenarios: 3× scenario size – OSPF engineering scenarios: 2× scenario size – Maxcut scenarios: 2× scenario size • Reward normalization: Min-max normalization (Stable-Baselines3 default) • Feature normalization: 18

– Node features are normalized independently using min-max scaling based on their respective ranges within the graph, ensuring feature scale independence – L1 normalization applied to language model embeddings when used as features, as ranges can hardly be determined • Scenario switching during training (only for V experiments): – Interval: every 50 episodes – Strategy: random selection • Policy architecture: – Hidden layers: [128, 64] – Subsequent output layer proportional to the action space and agent formulation used – Activation: LeakyReLU – Optimizer: Adam (ϵ = 10−7 , weight decay = 10−4 , AMSGrad disabled) • Graph Autoencoder (GAE): – Final layer: no activation function, with normalization enabled to ensure properly scaled embeddings – Loss functions (all adjusted to have the same scale, and weights all set to 1): * Continuous features: Mean Squared Error (MSE) * Adjacency matrix: Contrastive loss (τ = 0.5) * Binary features: Binary Cross-Entropy with logits * Multi-categorical features: Cross-Entropy loss Seeds. The random seeds used in the experiments are defined as follows. A seed of 42 is used for the scenario generation, initial experimental setup, and splitting strategies. For the generalization study, five independent runs per strategy and RL solution are performed with the following seeds used during training: 42, 100, 123, 200, and 300. For the testing phase, seeds are generated based on the number of episodes per scenario instance, ensuring a one-to-one correspondence and symmetry across test episode identifiers of several scenario instances. The resulting sequence of test seeds is: 42, 100, 123, 200, followed by increments of 100 up to 5000 (i.e., 400, 500, 600, . . . , 5000). The same sequence is used for assessing the distribution of action-selection time. All other hyperparameters were set to their respective library default values and are provided in the accompanying configuration files.

Scenario generation

As described in Section 4.1, the generalization study relies on 101 generated instances obtained by randomly sampling the parameters of the environment within predefined ranges. These ranges are designed to induce variability across instances and are reported below; all other parameters are held constant as indicated. Traveling Salesman Problem num_cities:[10,100] max_coord:[100,1000]

Maximum Cut num_nodes:[10,100] max_weight:[10,100]

OSPF Engineering num_nodes:[10,30] communication_edge_ratio:[0.1,0.3] non_zero_traffic_ratio:[0.1,0.3] min_capacity:[10,100] max_capacity:[500,1000] max_traffic:[25,50] graph_distribution: spanning tree min_weight: 1 max_weight: 5

Minimum Vertex Cover num_nodes:[10,50] edge_prob:[0.1,0.4]

Traffic Engineering num_nodes:[10,25] communication_edge_ratio:[0.1,0.2] non_zero_traffic_ratio:[0.1,0.2] min_capacity:[10,100] max_capacity:[500,1000] max_traffic:[25,50] max_path_len: 4 graph_distribution: spanning tree

Cyber-Attack Path Prediction n_nodes:[10,20] n_vulns_per_node:5 vulns_overlap:[0.0,0.1] p_data_present:[0.6,0.9] p_feature_visible:[0.5,0.7] p_recon:[0.2,0.4] p_detection:[0.05,0.2] goal: control fully_connected: true outcome_selection: false

Virtual Machine Placement n_vms:[10,50] n_pms:[10,50] n_tenants:[2,5] vm_vuln_prob_min:[0.01,0.1] vm_vuln_prob_max:[0.2,1.0] pm_escape_prob_min:[0.01,0.1] pm_escape_prob_max:[0.2,0.33] pm_capacity_memory_min:[32,64] pm_capacity_memory_max:[128,512] vm_demand_memory_min:[1,8] vm_demand_memory_max:[16,24] pm_capacity_storage_min:[100,500] pm_capacity_storage_max:[1000,5000] vm_demand_storage_min:[10,50] vm_demand_storage_max:[60,100] pm_capacity_pe_min:[8,16] pm_capacity_pe_max:[32,128] vm_demand_pe_min:[2,4] vm_demand_pe_max:[8,16] pm_capacity_mips_min:[1000,5000] pm_capacity_mips_max:[10000,50000] vm_demand_mips_min:[100,500] vm_demand_mips_max:[750,1000] latency_min:[0.1,1.0] latency_max:[2,8] p_idle:[50,100] p_peak:[150,300] coefficients: 1 min_traffic: 1 max_traffic: 10 traffic_density: 0.8

Scalability experiments present an evolving set of values for the main dimension (number of nodes) and the same ranges for secondary features. Scenario instances are exhaustively evaluated using heuristic-based exploration to estimate empirical upper and lower bounds. The number of sweeps is set based on preliminary experiments (10000 for TSP, 2000 for MaxCut, 10000 for MVC, 5000 for Placement, 2000 for OSPF, and 2000 for Traffic). The Cyber-Path scenario is omitted as its bounds can be directly inferred from the number of nodes (which becomes the maximum relative score). The heuristics guiding exploration were designed using a language model (gpt-5.4) and refined through manual validation. • TSP: We generate random tours and iteratively refine them using stochastic 2-opt moves. Improvements (or degradations) are sampled from candidate swaps, biased by their impact on tour length. This allows simultaneous estimation of both best and worst-case tour costs. • MinVertex: A greedy-stochastic strategy is used to iteratively select nodes covering the largest number of uncovered edges. At each step, selection is randomized among the topk candidates to maintain diversity. A pruning phase removes redundant nodes to refine solutions. The best cover size is tracked across multiple sweeps. The worst is set to the overall number of nodes. • MaxCut: Random graph partitions are initialized and improved via stochastic local search. Node flips that increase the cut value are identified, and one is selected probabilistically based on gain. This process continues until no further improvements are possible. The maximum cut value observed across samples defines the upper bound. The worst value is set to 0. • Placement: Allocations are constructed using heuristics that either maximize or balance resource utilization across physical machines. Initial solutions are built by prioritizing 20

high-demand VMs, followed by local refinements through stochastic reassignment. Both best and worst allocations are identified through repeated sweeps. • OSPF: OSPF link-weight settings are explored through stochastic search over candidate configurations. Each sweep starts either from a random solution or from a perturbed elite solution sampled from small best/worst pools, allowing intensified search without losing diversity. Neighboring configurations are obtained by randomly modifying a subset of link weights, and are selected with a bias toward lower and higher utilization to estimate both worst and best. Previously explored configurations are excluded. • Traffic: Same idea as OSPF but optimizing path allocations and not edge weights.

Embedding action space plots

Figure 7 presents the UMAP projection of the latent action spaces for seven representative 20-node scenarios from each real-world benchmark, highlighting both their variability and the common structural patterns that emerge in the action space manifolds. The scenarios were manually selected as the most representative manifolds based on exploratory analysis. Classical benchmarks were excluded due to their limited diversity in terms of manifolds, with respect to the already provided plots in Section 4. Virtual Machine Placement

Cyber Attack Path Prediction

OSPF Engineering

Traffic Engineering

Figure 7: UMAP projections of action spaces for seven 20-node graph instances across the four realworld benchmarks, with up to 300 actions (sampled by maintaining a representative approximation of the underlying action distribution).

Library and data

The LaGCO-RL library will be released under the MIT License alongside this paper, with a public GitHub repository to be made available upon acceptance. The associated data repository contains the simulated graph instances, trained models, dataset splits, and hyperparameter configurations. The data is distributed under the CC BY 4.0 open license. To facilitate reproducibility, the repository includes detailed README and REPRODUCIBILITY documents describing how to use the tool, reproduce the experiments, and access the data. Figures 8 and 9 illustrate two concrete instantiations of the framework enabled by the LaGCO-RL library, showcasing two examples, respectively cyber-attack path prediction and traffic engineering, and how the corresponding environments can be instantiated in our framework. These examples 21

Cyber-Path class CyberAttackExt(CyberAttack, ContinuousEnv): def get_graphs (...) : G = ... return {" attack_G ": G } self . _ o b s e r v a t i o n _ t y p e = { " graph ": Graph ( poolings =[ Mean , Sum ] , graph =" attack_G ") , " nodes_num ": Function ( get_num_nodes , graph =" attack_G ") , ... } self . _action_type = { " source ": Node ( graph =" attack_G " , spec ={" controlled ": true }) , " target ": Node ( graph =" attack_G ") , " vuln ": Object ( extractor = ’ bert ’ , reference =" target " , key =" vulns ") } self . _ n o d e _ a t t r i b u t e s = { " vulns ": Attribute ( extractor = ’ bert ’ , type = ’ continuous ’) ... } self . _ e d g e _ a t t r i b u t e s = { ... } def s a m p l e _ v a l i d _ a c t i o n (...) : ... def i s_ va l id _ ac ti o n (...) : ...

Figure 8: An instantiation of the automated framework with an example of the definition of the observation and action space, attribute specification, and proper methods to support the cyber-attack path prediction benchmark.

complement Section 3.5 by providing pseudo-code demonstrating how to define key components, including graph construction, observation and action spaces, attribute specifications, and supporting functions. Figure 8 presents a potential choice of framework instantiation for the cybersecurity benchmark. The observation space combines graph-level representations with auxiliary features (e.g., number of nodes), while the action space is compositional, involving the selection of a source node, a target node, and an associated vulnerability. This example highlights the framework’s ability to support structured actions over graph elements and its components in a conditional manner, as well as the integration of learned feature extractors (e.g., BERT-based embeddings) for semantic attributes such as vulnerabilities. In contrast, Figure 9 demonstrates a more complex setting in which multiple graph views are used to represent different aspects of the same environment instance. Specifically, a communication graph and a traffic graph are jointly defined, enabling the agent to reason over both topological connectivity and traffic flow dynamics from different graph representations. The observation space aggregates information independently from each graph, while the action space combines elements from both representations to form each action (i.e., selecting traffic links and communication paths). This highlights the flexibility of the framework in handling multi-graph environments and cross-graph interactions. Additionally, the traffic engineering example illustrates the use of pooling operators for different graph components, as well as normalization strategies (e.g., min–max scaling) applied to node attributes to ensure consistent feature scaling across different instances.

Observation space

Latent observation. The observation vector used in Section 4 for latent observation agents (GDiscrete, G-Discrete-M, Projection, Iterative) is defined as a fixed-dimensional representation that combines graph-level information and, for the projection agent, a summarized view of the action space. This design ensures sufficient expressiveness while maintaining a compact representation of both the environment structure and the decision space. The observation is constructed as follows: • Graph embedding: Node embeddings are aggregated using multiple pooling strategies to capture complementary structural information: – Mean pooling 22

Traffic Engineering class TrafficEngineeringExt(TrafficEngineering, ContinuousEnv): def get_graphs (...) : comm_G = ... traffic_G = ... return {" comm_G ": comm_G , " traffic_G ": traffic_G }

self . _ o b s e r v a t i o n _ t y p e = { " comm ": Graph ( poolings =[ Mean ] , graph =" comm_G ") , " traffic ": Graph ( poolings =[ Mean ] , graph =" traffic_G ") , ... } self . _action_type = { " traffic_link ": Edge ( graph =" traffic_G " , pooling = Concat ) , " c o m m u n i c a t i o n _ p a t h ": Path ( graph =" comm_G " , pooling = Concat ) ... }

self . _ n o d e _ a t t r i b u t e s = { " o u t g o i n g _ t r a f f i c ": Attribute ( norm =" min_max ") , ... } self . _ e d g e _ a t t r i b u t e s = { ... } def s a m p l e _ v a l i d _ a c t i o n (...) : ... def i s_ va l id _ ac ti o n (...) : ...

Figure 9: An instantiation of the automated framework with an example of the definition of the observation and action space, attribute specification, and proper methods to support the traffic engineering benchmark. – Max pooling – Min pooling – Sum pooling • Structural descriptors: Additional invariant features are included to explicitly encode global graph properties: – Number of nodes – Number of edges – Average node degree – Graph density • Action-space summarization (projection agent only): For benchmarks with structured action spaces that cannot be fully captured through node embeddings alone (which are already aggregated in the graph embedding), the action space is further embedded and aggregated using: – Mean pooling – Max pooling – Min pooling – Sum pooling The resulting pooled representation is concatenated to the observation vector, providing a compact summary of the latent action space. This additional vector is provided only to the projection agent, as the iterative agent inherently iterates over all embeddings, resulting in inherent visibility over the latent action space. Padding observation. For the padding-based discrete baselines, observations are explicitly constructed to encode all relevant information in a fixed-size vector. These representations are benchmark23

specific and capture features at the node, edge, graph, or path level, depending on the task, and are chosen to align with the graph features used for GNN-based embeddings. The observation design for each benchmark is detailed below: • TSP. The observation concatenates: – Flattened node coordinates – Binary visited status for each city – Flattened upper-triangular distance matrix (pairwise distances) • MinVertex. The observation includes: – Node-level binary indicators specifying whether each node is selected – Edge-level binary indicators (flattened upper triangle) denoting whether edges are covered • MaxCut. The observation consists of: – Node partition assignments – Flattened upper-triangular edge weights This representation captures both the graph structure and the current partitioning. • Placement. The observation concatenates: – Physical machine (PM) features (e.g., resource capacities and usage) – Virtual machine (VM) features (e.g., resource demands) • Cyber-Path: The observation is constructed as a concatenation of per-node feature vectors, encoding: – Visibility status (feature-level and graph-level) – Compromise state and privilege level – Service and vulnerability counts – Security-relevant flags (e.g., persistence, defense evasion, data exfiltration) – Aggregated vulnerability outcomes – Privilege requirements Features are partially masked depending on visibility, reflecting a partially observable setting, which is also done in the graph representation of the latent approaches. • OSPF. The observation is built from edge-level features: – For communication links: capacity, routing weight, and used capacity – For traffic demands: traffic volume on each demand edge • Traffic. The observation encodes: – Communication edge features: capacity and used capacity – Traffic demand values for each traffic edge

Training time

We report the computational training cost of the considered approaches on the most demanding benchmark, Traffic. We report the comparison using the most demanding training strategy, the varied (V) training strategy, in which agents are exposed to multiple training environments, resulting in the most costly strategy in terms of training time. Results computed on the benchmark machine used for the generalization study4 are reported in Table 5 over 5 independent runs, each using 20 training environments and 81 test environments. In general, projection methods consistently exhibit the highest computational cost at training time, followed by the iterative approach, while discrete baselines remain significantly more efficient in the training stage, as expected. 4 Benchmark Machine (generalization study): Dual Intel Xeon Gold 6258R (2 × 28 cores, 112 threads total) @ 2.70 GHz,

503 GiB RAM, NVIDIA RTX A6000 GPU, Ubuntu 22.04.3 LTS.

Table 5: Training time (seconds) across 5 runs on the traffic engineering benchmark.

Method

Run 1

Run 2

Run 3

Run 4

Run 5

Mean ± Std

P-discrete P-discrete-M G-discrete G-discrete-M Iterative Projection

671 779 1198 1738 3776 5844

678 778 1084 1614 2717 3384

675 805 3998 5393 6718 13417

675 783 1300 1759 2570 5788

684 792 1239 1739 5095 4869

676 ± 5 787 ± 10 1764 ± 1100 2449 ± 1600 4175 ± 1500 7460 ± 3800

Scalability curves

0.0006

Projection Iterative

0.0006 0.0004

0.0004

Projection Iterative

10 3

20 60 100 140 180 220 260 300 30

(f) OSPF

Instance Size

(e) Cyber-Path

Instance Size

(d) Placement

Instance Size

Projection Iterative

10 2 10 3

20 50 80 110 140 170 200

10 3

Projection Iterative

10 2

Instance Size

10 30 50 70 90 110 130 150

Projection Iterative

10 2

20 10600 140 180 220 260 300 340 380 420 460 500

10 3

(b) MinVertex Action Time (s)

10 2

Instance Size

(a) TSP Action Time (s)

Action Time (s)

10 1

0.0002

20 60 100 140 180 220 260 300

20 10600 140 180 220 260 300 340 380 420 460 500

0.0002

Instance Size

Projection Iterative

Action Time (s)

0.0005

Projection Iterative

Action Time (s)

0.0010

Action Time (s)

Figures 10 present the full evolution of the action-selection time experiments in Section 4.2 (evaluation time), including boxplots of the action time distribution across different graph sizes. The figures also indicate the sampled graph sizes for each benchmark, including the maximum size considered to perform the power-law estimation.

Instance Size

(g) Traffic

Figure 10: Scalability curve for seven experimental settings.

Extended generalization study

This section extends the generalization study by reporting additional statistical metrics in Tables 6–9. These include the mean performance, asymmetric spread estimates based on percentiles (lower spread: mean - 16th percentile; upper spread: 84th percentile - mean), Shapiro–Wilk normality test results, and bootstrapped confidence intervals (BCIs) of the normalized scores. These metrics provide a more reliable and robust estimate of performance across benchmarks and training strategies. The observed variability reflects differences in policy initialization, scenario splits, and the retraining of the GAE, which is performed independently for each training strategy. In addition, the attached files provide further analysis logs with the complete evaluation setting without the best selection per environment, aggregating the results for all five runs to highlight the differences induced by the evaluation protocol when this selection step is removed, as well as the same scores on the training environment.

Regime

Metric

P-Discrete

P-Discrete-M

G-Discrete

G-Discrete-M

Iterative

Projection (ours)

TSP

Mean Std IQM BCI Normal

0.02 -0.02/+-0.02 0.00 [0.01, 0.03] ×(p=0.00)

0.51 -0.06/+0.06 0.51 [0.50, 0.51] ×(p=0.01)

0.00 -0.00/+0.00 0.00 [0.00, 0.00] ✓ (p=1.00)

0.51 -0.06/+0.05 0.51 [0.51, 0.52] ×(p=0.00)

0.92 -0.26/+0.28 0.91 [0.90, 0.94] ×(p=0.00)

0.79 -0.18/+0.18 0.79 [0.78, 0.81] ×(p=0.00)

Mean Std IQM BCI Normal

0.00 -0.00/+0.00 0.00 [0.00, 0.00] ✓ (p=1.00)

0.48 -0.07/+0.06 0.48 [0.48, 0.49] ×(p=0.00)

0.00 -0.00/+-0.00 0.00 [0.00, 0.00] ×(p=0.00)

0.51 -0.06/+0.06 0.51 [0.50, 0.51] ×(p=0.00)

0.97 -0.26/+0.25 0.98 [0.95, 0.99] ×(p=0.00)

0.62 -0.11/+0.12 0.61 [0.61, 0.63] ×(p=0.00)

Mean Std IQM BCI Normal

0.00 -0.00/+0.00 0.00 [0.00, 0.00] ✓ (p=1.00)

0.48 -0.07/+0.07 0.48 [0.47, 0.49] ×(p=0.01)

0.00 -0.00/+0.00 0.00 [0.00, 0.00] ✓ (p=1.00)

0.51 -0.06/+0.06 0.51 [0.51, 0.52] ×(p=0.00)

0.86 -0.32/+0.39 0.80 [0.83, 0.89] ×(p=0.00)

0.76 -0.22/+0.20 0.76 [0.74, 0.78] ×(p=0.00)

Mean Std IQM BCI Normal

0.00 -0.00/+0.00 0.00 [0.00, 0.00] ✓ (p=1.00)

0.49 -0.07/+0.06 0.48 [0.48, 0.49] ×(p=0.00)

0.00 -0.00/+0.00 0.00 [0.00, 0.00] ✓ (p=1.00)

0.51 -0.05/+0.04 0.51 [0.51, 0.52] ×(p=0.00)

1.01 -0.26/+0.26 1.00 [0.98, 1.03] ✓ (p=0.07)

0.73 -0.17/+0.16 0.72 [0.71, 0.74] ×(p=0.00)

MinVertex

Mean Std IQM BCI Normal

0.01 -0.01/+-0.01 0.00 [0.00, 0.01] ×(p=0.00)

0.06 -0.06/+-0.06 0.00 [0.05, 0.08] ×(p=0.00)

0.01 -0.01/+-0.01 0.00 [0.00, 0.02] ×(p=0.00)

0.01 -0.01/+-0.01 0.00 [0.01, 0.02] ×(p=0.00)

0.54 -0.54/+0.46 0.40 [0.50, 0.58] ×(p=0.00)

0.58 -0.38/+0.35 0.64 [0.55, 0.61] ×(p=0.00)

Mean Std IQM BCI Normal

0.06 -0.06/+-0.06 0.00 [0.05, 0.08] ×(p=0.00)

0.27 -0.27/+0.29 0.16 [0.24, 0.29] ×(p=0.00)

0.20 -0.20/+0.35 0.06 [0.18, 0.23] ×(p=0.00)

0.27 -0.27/+0.29 0.17 [0.24, 0.29] ×(p=0.00)

0.14 -0.14/+0.31 0.00 [0.11, 0.16] ×(p=0.00)

0.17 -0.17/+0.33 0.04 [0.15, 0.20] ×(p=0.00)

Mean Std IQM BCI Normal

0.00 -0.00/+-0.00 0.00 [0.00, 0.01] ×(p=0.00)

0.19 -0.19/+0.31 0.05 [0.16, 0.21] ×(p=0.00)

0.11 -0.11/+0.29 0.00 [0.09, 0.13] ×(p=0.00)

0.21 -0.21/+0.34 0.07 [0.19, 0.24] ×(p=0.00)

0.28 -0.28/+0.62 0.07 [0.25, 0.32] ×(p=0.00)

0.18 -0.18/+0.44 0.01 [0.15, 0.21] ×(p=0.00)

Mean Std IQM BCI Normal

0.29 -0.29/+0.26 0.21 [0.27, 0.32] ×(p=0.00)

0.35 -0.35/+0.22 0.37 [0.32, 0.37] ×(p=0.00)

0.17 -0.17/+0.38 0.03 [0.15, 0.20] ×(p=0.00)

0.22 -0.22/+0.33 0.11 [0.20, 0.25] ×(p=0.00)

0.35 -0.35/+0.54 0.15 [0.30, 0.39] ×(p=0.00)

0.23 -0.23/+0.39 0.08 [0.20, 0.26] ×(p=0.00)

Table 6: Extended generalization results with confidence intervals and Shapiro-Wilk normality checks for TSP and MinVertex.

Regime

Metric

P-Discrete

P-Discrete-M

G-Discrete

G-Discrete-M

Iterative

Projection (ours)

MaxCut

Mean Std IQM BCI Normal

0.90 -0.03/+0.03 0.91 [0.90, 0.90] ×(p=0.00)

0.91 -0.02/+0.02 0.91 [0.90, 0.91] ×(p=0.00)

0.07 -0.07/+0.07 0.01 [0.06, 0.09] ×(p=0.00)

0.11 -0.11/+0.01 0.00 [0.09, 0.13] ×(p=0.00)

0.93 -0.03/+0.03 0.93 [0.92, 0.93] ×(p=0.01)

0.95 -0.03/+0.02 0.96 [0.95, 0.95] ×(p=0.00)

Mean Std IQM BCI Normal

0.67 -0.59/+0.24 0.85 [0.64, 0.70] ×(p=0.00)

0.52 -0.52/+0.38 0.39 [0.49, 0.56] ×(p=0.00)

0.90 -0.02/+0.02 0.91 [0.90, 0.90] ×(p=0.00)

0.91 -0.02/+0.02 0.91 [0.90, 0.91] ×(p=0.00)

0.79 -0.07/+0.08 0.81 [0.79, 0.80] ×(p=0.00)

0.92 -0.02/+0.02 0.93 [0.92, 0.92] ×(p=0.00)

Mean Std IQM BCI Normal

0.89 -0.04/+0.03 0.90 [0.88, 0.89] ×(p=0.00)

0.78 –0.07/+0.15 0.90 [0.75, 0.80] ×(p=0.00)

0.89 -0.03/+0.03 0.90 [0.89, 0.89] ×(p=0.00)

0.90 -0.02/+0.02 0.91 [0.90, 0.91] ×(p=0.00)

0.84 -0.05/+0.05 0.86 [0.83, 0.84] ×(p=0.00)

0.95 -0.02/+0.02 0.95 [0.95, 0.95] ×(p=0.00)

Mean Std IQM BCI Normal

0.49 -0.49/+0.42 0.35 [0.45, 0.53] ×(p=0.00)

0.43 -0.43/+0.47 0.27 [0.39, 0.47] ×(p=0.00)

0.89 -0.03/+0.03 0.90 [0.89, 0.89] ×(p=0.00)

0.90 -0.02/+0.02 0.91 [0.90, 0.91] ×(p=0.00)

0.80 -0.08/+0.08 0.83 [0.79, 0.81] ×(p=0.00)

0.94 -0.02/+0.02 0.94 [0.94, 0.94] ×(p=0.00)

Placement

Mean Std IQM BCI Normal

0.55 -0.17/+0.16 0.56 [0.53, 0.56] ×(p=0.00)

0.61 -0.17/+0.20 0.65 [0.59, 0.63] ×(p=0.00)

0.15 -0.12/+0.12 0.12 [0.14, 0.16] ×(p=0.00)

0.11 -0.11/+0.10 0.08 [0.10, 0.13] ×(p=0.00)

0.40 -0.28/+0.27 0.39 [0.38, 0.42] ×(p=0.00)

0.83 -0.25/+0.22 0.86 [0.81, 0.85] ×(p=0.00)

Mean Std IQM BCI Normal

0.38 -0.32/+0.28 0.39 [0.36, 0.40] ×(p=0.00)

0.66 -0.14/+0.14 0.66 [0.65, 0.67] ×(p=0.00)

0.48 -0.20/+0.18 0.49 [0.47, 0.50] ×(p=0.01)

0.59 -0.22/+0.19 0.61 [0.57, 0.60] ×(p=0.00)

0.07 -0.08/+0.08 0.03 [0.06, 0.08] ×(p=0.00)

0.85 -0.19/+0.17 0.86 [0.84, 0.87] ×(p=0.03)

Mean Std IQM BCI Normal

0.51 -0.17/+0.19 0.52 [0.49, 0.53] ×(p=0.00)

0.65 -0.17/+0.15 0.66 [0.63, 0.66] ×(p=0.00)

0.41 -0.22/+0.24 0.40 [0.39, 0.43] ×(p=0.00)

0.38 -0.25/+0.26 0.36 [0.36, 0.40] ×(p=0.00)

0.17 -0.21/+0.27 0.12 [0.15, 0.19] ×(p=0.00)

0.87 -0.19/+0.18 0.88 [0.85, 0.89] ×(p=0.02)

Mean Std IQM BCI Normal

0.56 -0.16/+0.15 0.56 [0.54, 0.57] ×(p=0.04)

0.65 -0.16/+0.14 0.65 [0.64, 0.66] ✓ (p=0.11)

0.36 -0.27/+0.25 0.35 [0.33, 0.38] ×(p=0.00)

0.51 -0.23/+0.23 0.52 [0.49, 0.53] ×(p=0.00)

0.22 -0.21/+0.25 0.16 [0.20, 0.24] ×(p=0.00)

0.90 -0.15/+0.16 0.92 [0.88, 0.92] ×(p=0.00)

Table 7: Extended generalization results with confidence intervals and Shapiro-Wilk normality checks for MaxCut and Placement.

Regime

Metric

P-Discrete

P-Discrete-M

G-Discrete

G-Discrete-M

Iterative

Projection (ours)

Cyber-Path

Mean Std IQM BCI Normal

0.21 -0.10/+0.10 0.19 [0.20, 0.22] ×(p=0.00)

0.62 -0.12/+0.13 0.61 [0.61, 0.63] ×(p=0.03)

0.19 -0.09/+0.08 0.18 [0.18, 0.20] ×(p=0.00)

0.47 -0.17/+0.18 0.45 [0.45, 0.48] ×(p=0.00)

0.36 -0.23/+0.20 0.35 [0.34, 0.38] ×(p=0.00)

0.61 -0.11/+0.11 0.61 [0.60, 0.62] ✓ (p=0.23)

Mean Std IQM BCI Normal

0.21 -0.09/+0.09 0.19 [0.20, 0.22] ×(p=0.00)

0.61 -0.11/+0.14 0.61 [0.60, 0.62] ×(p=0.00)

0.21 -0.10/+0.09 0.18 [0.20, 0.21] ×(p=0.00)

0.52 -0.15/+0.15 0.51 [0.50, 0.53] ✓ (p=0.13)

0.30 -0.22/+0.39 0.20 [0.27, 0.32] ×(p=0.00)

0.61 -0.11/+0.11 0.61 [0.60, 0.62] ✓ (p=0.09)

Mean Std IQM BCI Normal

0.21 -0.10/+0.09 0.19 [0.20, 0.21] ×(p=0.00)

0.64 -0.11/+0.11 0.64 [0.62, 0.65] ×(p=0.01)

0.20 -0.09/+0.08 0.19 [0.19, 0.20] ×(p=0.00)

0.47 -0.17/+0.17 0.46 [0.45, 0.48] ×(p=0.00)

0.31 -0.20/+0.29 0.25 [0.29, 0.33] ×(p=0.00)

0.64 -0.09/+0.10 0.64 [0.63, 0.65] ×(p=0.00)

Mean Std IQM BCI Normal

0.20 -0.10/+0.11 0.18 [0.19, 0.22] ×(p=0.00)

0.68 -0.13/+0.13 0.68 [0.67, 0.69] ✓ (p=0.07)

0.19 -0.09/+0.10 0.18 [0.18, 0.20] ×(p=0.00)

0.51 -0.18/+0.15 0.51 [0.49, 0.52] ×(p=0.01)

0.28 -0.12/+0.12 0.25 [0.27, 0.29] ×(p=0.00)

0.68 -0.10/+0.10 0.68 [0.67, 0.69] ×(p=0.00)

OSPF

Mean Std IQM BCI Normal

0.35 -0.35/+0.40 0.20 [0.32, 0.38] ×(p=0.00)

0.25 -0.25/+0.43 0.08 [0.23, 0.28] ×(p=0.00)

0.31 -0.31/+0.37 0.17 [0.28, 0.34] ×(p=0.00)

0.41 -0.41/+0.41 0.26 [0.38, 0.44] ×(p=0.00)

0.17 -0.17/+0.49 0.00 [0.14, 0.20] ×(p=0.00)

0.61 -0.48/+0.34 0.69 [0.58, 0.64] ×(p=0.00)

Mean Std IQM BCI Normal

0.11 -0.11/+0.19 0.00 [0.09, 0.13] ×(p=0.00)

0.42 -0.42/+0.45 0.26 [0.38, 0.45] ×(p=0.00)

0.28 -0.28/+0.32 0.15 [0.26, 0.31] ×(p=0.00)

0.58 -0.42/+0.32 0.64 [0.56, 0.61] ×(p=0.00)

0.01 -0.01/+-0.01 0.00 [0.01, 0.02] ×(p=0.00)

0.83 -0.12/+0.13 0.85 [0.82, 0.84] ×(p=0.00)

Mean Std IQM BCI Normal

0.19 -0.19/+0.34 0.05 [0.17, 0.22] ×(p=0.00)

0.43 -0.43/+0.44 0.40 [0.40, 0.46] ×(p=0.00)

0.28 -0.28/+0.34 0.14 [0.25, 0.30] ×(p=0.00)

0.40 -0.40/+0.36 0.39 [0.37, 0.43] ×(p=0.00)

0.21 -0.21/+0.46 0.04 [0.18, 0.24] ×(p=0.00)

0.71 -0.33/+0.24 0.79 [0.68, 0.73] ×(p=0.00)

Mean Std IQM BCI Normal

0.22 -0.22/+0.37 0.07 [0.19, 0.25] ×(p=0.00)

0.16 -0.16/+0.22 0.01 [0.13, 0.18] ×(p=0.00)

0.52 -0.31/+0.29 0.52 [0.49, 0.55] ×(p=0.00)

0.66 -0.24/+0.23 0.67 [0.64, 0.68] ×(p=0.00)

0.09 -0.09/+-0.09 0.00 [0.07, 0.12] ×(p=0.00)

0.87 -0.08/+0.12 0.89 [0.86, 0.88] ×(p=0.00)

Table 8: Extended generalization results with confidence intervals and Shapiro-Wilk normality checks for Cyber-Path and OSPF.

Regime

Metric

P-Discrete

P-Discrete-M

Mean Std IQM BCI Normal

0.30 -0.26/+0.29 0.26 [0.28, 0.32] ×(p=0.00)

0.42 -0.37/+0.35 0.42 [0.39, 0.45] ×(p=0.00)

Mean Std IQM BCI Normal

0.22 -0.22/+0.29 0.10 [0.20, 0.24] ×(p=0.00)

Mean Std IQM BCI Normal

G-Discrete

G-Discrete-M

Iterative

Projection (ours)

0.31 -0.27/+0.32 0.25 [0.28, 0.33] ×(p=0.00)

0.69 -0.15/+0.15 0.73 [0.68, 0.71] ×(p=0.00)

0.04 -0.04/+0.08 0.01 [0.04, 0.05] ×(p=0.00)

0.81 -0.09/+0.09 0.81 [0.80, 0.82] ×(p=0.00)

0.61 -0.59/+0.23 0.74 [0.59, 0.64] ×(p=0.00)

0.50 -0.15/+0.18 0.50 [0.49, 0.51] ✓ (p=0.06)

0.79 -0.09/+0.08 0.78 [0.78, 0.79] ×(p=0.00)

0.04 -0.04/+0.07 0.01 [0.03, 0.04] ×(p=0.00)

0.82 -0.08/+0.08 0.82 [0.81, 0.83] ×(p=0.00)

0.48 -0.24/+0.25 0.49 [0.46, 0.50] ×(p=0.00)

0.68 -0.19/+0.17 0.74 [0.66, 0.70] ×(p=0.00)

0.55 -0.26/+0.22 0.57 [0.53, 0.57] ×(p=0.00)

0.70 -0.17/+0.14 0.73 [0.68, 0.72] ×(p=0.00)

0.04 -0.04/+0.08 0.01 [0.04, 0.05] ×(p=0.00)

0.81 -0.08/+0.09 0.81 [0.80, 0.81] ×(p=0.00)

0.33 -0.33/+0.33 0.20 [0.30, 0.36] ×(p=0.00)

0.71 -0.10/+0.15 0.76 [0.69, 0.74] ×(p=0.00)

0.60 -0.21/+0.19 0.63 [0.58, 0.62] ×(p=0.00)

0.79 -0.09/+0.09 0.79 [0.78, 0.80] ×(p=0.00)

0.04 -0.04/+0.07 0.01 [0.03, 0.05] ×(p=0.00)

0.84 -0.07/+0.07 0.83 [0.83, 0.84] ×(p=0.00)

Traffic

Table 9: Extended generalization results with confidence intervals and Shapiro-Wilk normality checks for Traffic.

Record · ID 204743 · SHA-256 4d3e9458e94a952a
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.