acceptodds
Under review as a conference paper at ICLR 2027

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

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 GCO methodology built on the Wolpertinger framework and adapted to a shared GNN-based latent space for observations and actions. These agents are trained to solve GCO problems by predicting a desired latent action in a single forward pass, which is subsequently decoded into a valid discrete action in the graph using the latent space. Across diverse benchmarks, our approach achieves up to 6.41 faster inference and up to 75% better generalization than existing solutions using a simple nearest-neighbor decoding, while opening the door to strong RL performance in super-linear decision spaces with multiple interdependent variables. Finally, we release , a Python library that automates latent action-space construction and supports existing RL-GCO solutions, promoting reproducibility and adaptation to new GCO benchmarks.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph combinatorial optimization, reinforcement learning, graph neural networks, latent action spaces

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_RqfGOpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper investigates the impact of using a Wolpertinger-style proto-action in the context of graph combinatorial optimisation (GCO). First, the paper proposes projection agents for actions, which they position as the first application of continuous latent actions in GCO and dynamic action spaces in general. Second, the paper introduces super-linear decision variables, where composite embeddings of multiple graph components can be treated as actions. The paper compares baseline action representations of: fixed padded output, permutation-invariant scoring, and iterative (DQN). The paper uses a fixed embedding across all methods to isolate the impact of the policy method. Finally, the paper introduces a python library implementing their latent action-space method.

Based on the critical weaknesses discussed following, I recommend rejection. There is significant prior work undermining the main novelty claim of the paper, as discussed in [W1], and I believe the paper should be reformulated to remove this contribution claim. Additionally, there is a claim made of "fair comparison" which is not validated in the paper, discussed in [W2].

I believe the second contribution discussed in [S1] to be significant, but largely under-explored in the experimental evaluation of the paper. Previous works implementing the proto-action approach in GCO have typically relied purely on sequential selection of nodes for the action space, with more complex action structures (edges, paths) requiring multiple phased selections. The paper would be greatly strengthened if it compared the scalability of the proposed super-linear decision variable approach against the existing linear proto-action approaches. I would increase my rating if this could be addressed.

Critical strengths
  • [S1]: The composite embedding approach for super-linear decision variables is very useful, and to the best of my knowledge has not been done in GCO before. The approach is important for approaching GCO problems with complex action spaces in a scalable manner.
Critical weaknesses
  • [W1]: The paper makes a central contribution claim of being the first to apply Wolpertinger-style proto-actions to graph combinatorial optimisation (GCO). However, several prior publications have used the proto-action approach in GCO, significantly undermining this claim. The baselines should include at least one of these prior approaches as a comparison.
    • Proto-actions are applied in a graph combinatorial optimisation problem in [1], with proto-actions being compared to node embeddings using a distance function. To my knowledge this is the first explicit use of the proto-action in a GCO problem.
    • A framework for solving GCO problems is introduced in [2], which uses the proto-action approach with a distance function and trains with PPO. This paper includes the TSP and MVC problems. The framework includes a python implementation which uses an extensible environment template based on SB3.
    • The proto-action approach is explicitly discussed as an action framing for graph-based RL in [5].
    • The proto-action approach is also applied to molecular graphs in [3], where the state is represented as the graph's Morgan fingerprint, and the approach uses k-nearest-neighbours of a proto-action.
    • Prior to these works, a similar continuous latent action embedding is introduced in [4], though it is not exactly the same as the proto-action approach. GNN state embeddings are passed through an MLP and interpreted as a mean and standard deviation of a Gaussian. A continuous action is sampled and compared to node embeddings using a similarity function.
  • [W2]: It is unclear that decoupling the learned representation from the policy learning is able to provide a fair comparison. The RL methods may have differing sensitivities to the embedding used, and it is likely that optimising the representation and policy together will result in an embedding space that is favourable for each method. Overall, insufficient evidence is provided for the claim supporting a fair comparison.
    • The ablation in the appendix does not directly address the question of fairness. I would expect to see a small-scale study on a particular domain where the state representation and policy are jointly optimised for all methods. Then their relative performance could be compared to the pre-trained representation setting. If there is no strong disadvantage for any method when using the pre-trained representation, the claim of a fair comparison might be more acceptable.

[1]: Darvariu, Victor-Alexandru, Stephen Hailes, and Mirco Musolesi. ‘Solving Graph-Based Public Goods Games with Tree Search and Imitation Learning’. In Advances in Neural Information Processing Systems 34, 2021.

[2]: Schutz, Alex, Victor-Alexandru Darvariu, Efimia Panagiotaki, Bruno Lacerda, and Nick Hawes. ‘Tackling GNARLy Problems: Graph Neural Algorithmic Reasoning Reimagined through Reinforcement Learning’. Transactions on Machine Learning Research, 2026.

[3]: Yu, Yemin, Ying Wei, Kun Kuang, Zhengxing Huang, Huaxiu Yao, and Fei Wu. ‘GRASP: Navigating Retrosynthetic Planning with Goal-Driven Policy’. In Advances in Neural Information Processing Systems, 2022.

[4]: Trivedi, Rakshit, Jiachen Yang, and Hongyuan Zha. ‘GraphOpt: Learning Optimization Models of Graph Formation’. In Proceedings of the 37th International Conference on Machine Learning, 2020.

[5]: Schutz, Alex, and Victor-Alexandru Darvariu, "Using Graph Neural Networks in Reinforcement Learning: A Practical Guide", ICLR Blogposts, 2026, https://iclr-blogposts.github.io/2026/blog/2026/rl-with-gnns/#nodes-as-actions-proto-action.

Questions for authors
  • [Q1]: Do you have a definition for "admissible", which is introduced in the problem formulation but not defined?
  • [Q2]: Do you have evidence to justify that pre-training using random valid actions allows "maximal policy-independent exploration"? RL is typically very sensitive to distribution shift, and the states reached by a random policy can be substantially different from states reached by any informed policy. Is the disadvantage incurred by this distribution shift the same across all evaluated methods, or different?
  • [Q3]: Is the use of empirically estimated bounds in the projection agent fundamental to its operation, or is it just to inform the limits of the gym.Box?
  • [Q4]: Have you empirically validated the application of the same hyperparameters across different environments? Experience shows that relative performance can differ substantially with hyperparameters and they are typically sensitive to the particular environment.
  • [Q5]: What are the actual sizes of the S,M,L sets for each environment? Does the evaluation all take place within the same size distribution?
  • [Q6]: Can you explain the performance collapse of the Projection method on MinVertex for M,L and V?
  • [Q7]: There is a stark performance difference of the discrete and iterative methods in revisiting vs non-revisiting settings. Is this purely explained by the larger action space, even at small sizes?
  • [Q8]: In Table 2 you highlight the best result across S,M,L,V. In my opinion it is fairer to compare each column independently. Can you justify this decision?
  • [Q9]: Is the sparsification of the TSP strictly required or could it be omitted?
5 comments
AuthorsOpenReview ↗

Prior Work, Novelty, Representation Design, and Composite Proto-Action Selection (W1-W2, Q1)

Response: Part 1/3

We thank Reviewer RqfG for their thorough and expert review, for pointing us to prior work we had missed, and for recognizing the composite embedding approach for super-linear decision variables as a useful contribution to GCO. Following the review, we have reformulated our novelty claims and replaced the "fair comparison" claim with a more precise one. We address each point below, using the reviewer's labels.

Prior Work on Proto-Actions in GCO and Revised Claims [W1]

The reviewer is correct that our claims of being the first to apply Wolpertinger-style proto-actions to GCO, and to dynamic latent action spaces, were too broad. We have therefore removed this statement from Section 2 of the revised manuscript and now discuss [1–5] as prior applications of proto-action selection to graph problems. We have repositioned our contributions around three aspects: (i) composite action embeddings that allow a single proto-action to select super-linear decision variables (e.g., edges and paths) in one step, whereas, as the reviewer notes in [S1], previous proto-action approaches handle such decisions through sequential node selection; (ii) a controlled comparison of proto-action selection against discrete and iterative parameterizations across seven GCO benchmarks, including real-world problems with high-cardinality action spaces. Unlike prior works [2–5], which adopt proto-actions as a fixed design choice, we systematically evaluate their suitability against alternative parameterizations within a common experimental framework, focusing on scalability and generalization; and (iii) the release of the LaGCO-RL library. We also acknowledge that these relevant works were inadvertently overlooked. One reason is that [1, 2, 4] do not explicitly refer to the Wolpertinger approach or cite its foundational work (Dulac-Arnold et al., Deep Reinforcement Learning in Large Discrete Action Spaces), making their connection to Wolpertinger-style action selection less apparent in our initial literature review. We thank the reviewer for highlighting these connections. We have incorporated the relevant works into the revised related-work discussion and adjusted our novelty claims accordingly.

Shared Fixed Representation and the Comparison Across Methods [W2]

We deliberately keep the pretrained GNN embeddings fixed during RL training rather than jointly fine-tuning them with the policy. We already acknowledge this as a potential limitation on maximum performance (Limitation (4)), but this design choice serves two purposes. First, since our goal is to compare action-selection parameterizations, using a fixed embedding space allows us to isolate how each parameterization maps states to actions from the same representations, rather than conflating action selection with representation learning. The GAE is nevertheless retrained independently for each training strategy and run (Appendix M), so the reported results span multiple independently learned embedding spaces. Second, continuously updating action embeddings would change the mapping between the policy's outputs and the corresponding discrete actions: the same proto-action could map to different discrete actions at different stages of training, making action selection non-stationary from the policy's perspective. Keeping embeddings fixed preserves consistent action semantics, promoting more stable learning and improving sample efficiency, particularly for Projection. Accordingly, in the revised manuscript, Contribution (3), Section 3.2, and Limitation (4) now explicitly frame our results as a controlled comparison under a shared, fixed representation.

Composite versus Sequential Proto-Action Selection [main comment]

We thank the reviewer for highlighting this contribution and agree that a comparison with sequential (phased) action selection would strengthen the evaluation. However, conducting this comparison fairly would require introducing the same action decomposition for the discrete and iterative parameterizations, ensuring that differences are attributable to the selection strategy rather than the action-space formulation. Moreover, the current Stable-Baselines3 implementation does not readily support the required parameterized algorithms. We consider this an interesting direction for future work, but given the implementation effort required, we are unable to include this comparison within the rebuttal period.

Definition of Admissible Substructures [Q1]

In the revised manuscript, we explicitly define admissible substructures in Section 3.1 as substructures that satisfy the problem-specific constraints of the considered GCO problem.

AuthorsOpenReview ↗

Pretraining, Action-Space Design, Hyperparameter Transfer, and Regimes' Performance (Q2-Q6)

Response: Part 2/3

Random Valid-Action Pretraining and Distribution Shift [Q2]

We agree that the term "maximal" was not supported by empirical evidence; accordingly, Section 3.2 of the revised manuscript now describes the pretraining as policy-independent. Random valid-action trajectories avoid coupling the representation to a specific policy, although we acknowledge that the states they visit may differ from those encountered by a trained policy. The motivation is precisely to avoid making representation learning dependent on a particular optimization policy: trajectories generated by an optimal policy would be ideal, but such a policy is precisely what the downstream RL agent is intended to learn and is therefore unavailable a priori. Random valid-action trajectories thus provide a practical, policy-independent way to expose the GNN to the structural diversity of feasible partial solutions. A self-supervised reconstruction objective is therefore a natural choice for learning these representations independently of the downstream policy.

Role of the Empirical Action Bounds [Q3]

The bounds are not intrinsic to the projection mechanism; they simply define the bounded continuous action space (gym.Box) of the policy. They are estimated from the range of action embeddings across the training instances of each benchmark and extended by a margin (Appendix C). This keeps policy exploration within the region containing the action embeddings, thereby improving sample efficiency.

Hyperparameter Transfer Across Environments [Q4]

We clarify that hyperparameter optimization was not performed separately for each environment. Instead, each method was tuned independently using 25 TPE trials on TSP only, and the resulting configurations were then used across all benchmarks (Appendix C). Tuning six methods independently on seven benchmarks would require 42 separate searches, so we adopted shared configurations to keep the comparison controlled and computationally tractable. Notably, TSP is the benchmark on which Projection does not achieve the best performance, so this choice does not appear to favor Projection. Nevertheless, we cannot rule out that per-benchmark tuning could change some of the relative rankings. This limitation is now explicitly acknowledged in the revised manuscript.

Sizes of the S, M and L Regimes [Q5]

The S, M, and L labels represent benchmark-specific complexity levels rather than a simple ranking of graph sizes by number of nodes. Scenario complexity is determined by considering all sampled features and their respective ranges, which differ across benchmarks (e.g., TSP and Traffic). Thus, an S instance represents a lower-complexity scenario, but not necessarily the graph with the fewest nodes. This distinction is particularly important for more complex benchmarks such as Traffic, where complexity cannot be characterized by graph size alone. All sampling features and their corresponding ranges are detailed in Appendix D, and we have clarified this distinction in Section 4 of the revised manuscript.

Projection on MinVertex in the M, L and V Regimes [Q6]

Projection achieves the best performance in the S regime (0.70), but its scores drop sharply to 0.01–0.03 in M, L, and V. Iterative exhibits a similar pattern (0.40 in S, falling to 0.00–0.16), whereas the masked discrete baselines remain relatively stable at 0.32–0.39. Notably, G-Discrete-M uses the same embeddings as observations without exhibiting this degradation, suggesting that the issue is specific to using node embeddings as action representations rather than to the embeddings themselves. The MinVertex score is zero whenever no feasible vertex cover is produced (Appendix B.2). Moreover, Table 12 reports means of 0.17–0.20, substantially above the corresponding IQMs of 0.02–0.04, indicating that most test episodes yield zero scores. A plausible explanation is that MinVertex node features reduce to a binary flag, leaving the action embeddings to rely primarily on graph structure. This may make individual node representations less discriminative and harder to separate as the size and structural complexity of random graphs increase.

AuthorsOpenReview ↗

Revisiting Settings, Performance Reporting, and Graph Sparsification (Q7-Q9)

Response: Part 3/3

Revisiting versus Non-Revisiting Settings [Q7]

In the revisiting setting, previously selected elements remain available, so the action set is larger at every step and does not shrink throughout the episode, even for small graphs. Revisiting also fundamentally changes the task: actions can undo previous decisions, and episodes terminate either at a cutoff or upon reaching a target quality, rather than when a constructive solution is completed (Appendix B). The degradation of Discrete and Iterative therefore reflects both the larger, persistent action space and the longer, non-constructive nature of these episodes. In contrast, Projection remains comparatively stable, highlighting another important advantage of this parameterization in settings where actions can be repeatedly selected or reversed (Table 3).

Highlighting in Table 2 [Q8]

We agree that per-column comparisons provide a fairer assessment of performance across settings. However, our intention was to highlight both the best action parameterization and the best training configuration for each benchmark, i.e., which combination of training choices generalizes best without requiring size-specific retraining. In the revised manuscript, Table 2 now bolds the best result in each column while retaining underlining to indicate the best-performing configuration per benchmark. Under the per-column comparison, Projection achieves the best or tied-best result in 15 of the 28 settings, while under the per-benchmark comparison, it ranks best or tied-best on six of the seven benchmarks.

Sparsification of the TSP Graph [Q9]

It is not strictly required. We retain the K = 10 nearest neighbors per node (Appendix B.1) for two reasons: to avoid the degraded GNN embeddings associated with fully connected graphs and to prevent quadratic growth in memory usage and message passing costs. The restriction could be removed at the expense of these drawbacks.

We thank the reviewer again for a review that has materially improved the positioning of our work. We hope that the reformulated claims address the two grounds for rejection and the condition the reviewer set for raising their rating, and we remain glad to discuss any remaining concern.

Reviewer_NaF1OpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes projection agents, a way to use RL to solve graph combinatorial optimization (GCO) problems. The key insight is to avoid parameterizing the entire discrete action space, which scales poorly in the size of the graph for standard problems. Instead, an extension of the Wolpertinger framework is developed, which encodes the graph nodes and action space into a fixed-dimensional vector from a pretrained GNN encoder and a policy that takes this vector in as input and outputs a continuous action parametrization, which is subsequently decoded into a discrete action using a nearest neighbor. Experiments on seven different GCO problems show that this framework scales favorably compared to iterative methods and also has improved solution quality on problems where the action space is large.

Critical strengths
  1. The idea of parameterizing the policy to output a continuous action, which is subsequently projected onto a valid discrete action using nearest-neighbor search, is elegant and well motivated. This approach provides a promising way to handle large and variable action spaces, an important challenge for scalable graph combinatorial optimization. While the underlying idea builds on the existing Wolpertinger framework, adapting it to GCO problems with dynamic, graph-structured action spaces appears to be a meaningful contribution.

  2. The experimental evaluation is extensive, covering seven benchmarks with varying action-space complexity and several training configurations. The results are encouraging, particularly on problems with large action spaces. For these problems, the proposed projection approach often achieves better solution quality and more favorable inference-time scaling than iterative Q-learning methods.

Critical weaknesses
  1. The pretrained GNN embeddings are learned through a graph reconstruction objective that is agnostic to the downstream GCO optimization objective. Thus, it does not seem that the geometry needs to respect that closeby actions are still favorable to the downstream GCO problem. Why is L2 distance in embedding space the correct metric to identify good actions?
Questions for authors
  1. My main question is the one above about the justification of the nearest neighbors approach. While the experimental results seem still convincing, I think this warrants some discussion in the paper. This is the main reason why my current score is 3 instead of 4.
3 comments
AuthorsOpenReview ↗

Nearest-Neighbor Decoding and the Role of Learned Action Embeddings

We thank Reviewer NaF1 for the positive assessment of our work, for describing the projection idea as elegant and well motivated, and for raising the precise question regarding nearest-neighbor decoding. We agree that this aspect warrants an explicit discussion in the paper. Accordingly, we have added this discussion to Section 3.4 of the revised manuscript and provide further details in our response below.

To address this question, the distance metric captures similarity in the embedding space rather than similarity in objective value, and serves solely to map the continuous proto-action produced by the policy to the closest available discrete action. The GAE provides a structured embedding space that captures similarities among graph elements, while the RL policy learns, through reward feedback, which regions of this space correspond to desirable actions in each state. As explained in Section 3.4, 1-NN decoding partitions the latent space into regions associated with individual valid actions, and the policy learns to target the regions corresponding to high-reward actions. Consequently, the embedding geometry does not need to place actions with similar objective values close to one another; rather, it should provide a meaningful and consistent representation of graph elements. Importantly, the GAE is pretrained using graph topology, node and edge features, and neighborhood information, which jointly characterize graph elements and their structural roles as partial solutions. A self-supervised reconstruction objective is therefore a natural choice for learning these representations independently of the downstream policy.

We nevertheless emphasize that the resulting geometry does matter for learnability and, ultimately, solution quality, as quantified in Appendix F. With random action embeddings, the projection agent scores only 0.36 on TSP, MinVertex, and MaxCut, compared with 0.78, 0.70, and 0.93, respectively, using GAE embeddings (Table 6). The same appendix also reports reconstruction-loss ablations to assess the contribution of individual components, as well as comparisons against raw feature-vector embeddings, highlighting the additional value of incorporating graph topology and edge information through the GAE. We also clarify that retrieval uses cosine similarity rather than Euclidean (L2) distance, selected empirically as a more suitable choice for handling high-dimensional action spaces (Appendix C).

Finally, alternative retrieval strategies, such as distance-weighted stochastic K-NN sampling [1], could yield different mappings between policy outputs and discrete actions. We are therefore conducting an ablation comparing this approach with deterministic 1-NN on selected benchmarks and training regimes, and will share the results in a follow-up comment as soon as they are available, before the rebuttal period ends.

We thank the reviewer again for this constructive question. We hope that this response, together with the additional discussion in the revised manuscript, addresses the underlying concern, and we would be happy to clarify any remaining questions.

References

[1] Darvariu et al., "Solving Graph-Based Public Goods Games with Tree Search and Imitation Learning," NeurIPS, 2021.

AuthorsOpenReview ↗

Additional Ablation on Stochastic K-NN Action Selection

Following up on our previous response, we have now completed the ablation comparing distance-weighted stochastic K-NN sampling (used in studies like [1,2]) against our original deterministic 1-NN selection. Specifically, we evaluate stochastic sampling with K = 10 at two temperatures (T=0.1, corresponding to low exploration, and T=0.5, corresponding to higher exploration), where (T=1) corresponds to uniform random sampling within the K-NN neighborhood. We evaluate the two most relevant training strategies (S and L) across three classical benchmarks: TSP, MinVertex, and MaxCut. The results are reported below, together with those obtained using our original deterministic 1-NN configuration, and are also provided in Appendix N of the revised manuscript.

Action selectionTravel (S/L)MinVertex (S/L)MaxCut (S/L)
K-NN, T=0.50.72 / 0.600.14 / 0.350.93 / 0.91
K-NN, T=0.10.75 / 0.570.65 / 0.490.93 / 0.90
Original 1-NN0.78 / 0.600.70 / 0.030.93 / 0.91

Overall, the results show that distance-weighted stochastic K-NN sampling remains competitive with deterministic 1-NN across different benchmarks and sampling temperatures. In particular, performance on Travel and MaxCut remains relatively stable across action-selection strategies, suggesting that the learned GAE embedding spaces capture meaningful action-space structure that supports different effective projection mechanisms. In contrast, MinVertex exhibits greater sensitivity to the sampling strategy and temperature, potentially indicating that the additional stochasticity introduced during action selection has a more pronounced impact on this benchmark. These findings suggest that, although the choice of action-selection mechanism can influence performance, the benefits of our approach primarily stem from the structured action representations learned by the GAE. In other words, the learned embedding space provides the underlying structure that enables effective mapping from continuous policy outputs to discrete actions, while the retrieval mechanism determines how this structure is exploited. The fact that our approach remains effective under alternative retrieval strategies further supports the robustness of the learned representations. Moreover, deterministic 1-NN provides a strong decoding baseline, demonstrating that our approach already uses a simple yet more stable and effective projection mechanism compared with alternative action-selection strategies explored in prior work.

[1]: Darvariu, Victor-Alexandru, Stephen Hailes, and Mirco Musolesi. ‘Solving Graph-Based Public Goods Games with Tree Search and Imitation Learning’. In Advances in Neural Information Processing Systems 34, 2021.

[2]: Schutz, Alex, Victor-Alexandru Darvariu, Efimia Panagiotaki, Bruno Lacerda, and Nick Hawes. ‘Tackling GNARLy Problems: Graph Neural Algorithmic Reasoning Reimagined through Reinforcement Learning’. Transactions on Machine Learning Research, 2026.

I thank the reviewer for their comments. It answers my clarification and thus I am happy to raise my score to a 4.

Reviewer_QeyeOpenReview ↗
Rating
1
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes projection agents for graph combinatorial optimization (GCO), adapting the Wolpertinger framework to graph-based reinforcement learning. The method uses a self-supervised graph autoencoder to learn node embeddings and constructs shared continuous representations for observations and structured actions. A policy predicts a continuous proto-action in the latent action space, which is decoded into a valid discrete action through nearest-neighbor search. The framework supports actions involving heterogeneous graph components and additional attributes, including composite decisions with super-linear or exponential worst-case action-space growth.

The authors evaluate the approach on seven benchmarks: TSP, Minimum Vertex Cover, MaxCut, Virtual Machine Placement, Cyber-Attack Path Prediction, OSPF engineering, and Traffic engineering. The evaluation compares projection agents with discrete-action and iterative Q-value approaches under several training and generalization settings. The paper reports competitive or superior generalization performance on most benchmarks and improved action-selection latency over iterative methods, with particularly substantial gains on structured action spaces. The authors also release LaGCO-RL, a library intended to facilitate reproducible experiments and adaptation to new GCO tasks.

The principal questions are whether the nearest-neighbor projection mechanism remains computationally advantageous when the full valid action set is expensive to construct, whether the reported generalization results adequately represent deployment performance, and whether the learned embedding geometry reliably preserves the task-relevant structure of combinatorial actions.

Critical strengths
  1. A meaningful approach to structured and variable action spaces. The paper addresses an important limitation of conventional RL-GCO methods: their action representations and output dimensions often depend on the particular graph instance. Constructing semantic action embeddings from graph components and combining them for composite actions provides a flexible alternative to flat action indexing. This is particularly relevant to Virtual Machine Placement, OSPF engineering, and Traffic engineering, where decisions involve multiple interdependent components.

  2. Broad empirical coverage and explicit generalization evaluation. The seven benchmarks cover both classical graph optimization problems and application-driven tasks with more complex action structures. The authors evaluate transfer across graph sizes and scenario distributions rather than restricting the analysis to training instances. In Table 2, the projection method achieves the best or competitive normalized generalization scores on several application-oriented benchmarks, including Placement, Cyber-Path, and OSPF. The comparison among discrete, iterative, and projection policies also helps isolate the effects of different action parameterizations.

  3. An attempt to measure computational scaling directly. Section 4.2 measures action-selection latency across graph sizes and fits power-law scaling models. Table 4 reports lower fitted scaling exponents for projection than for iterative methods across the listed benchmarks. For example, the reported exponents are 0.22 versus 1.81 on Placement and 0.73 versus 4.68 on Traffic. Although these measurements do not establish end-to-end scalability, they provide useful evidence that avoiding a separate Q-network evaluation for every candidate can reduce the cost of action selection.

  4. A useful reproducibility contribution. The LaGCO-RL library, experiment configurations, checkpoints, and scenario data are presented as part of the contribution. The authors also report ablations of graph autoencoder loss variants and compare learned representations against alternative observation encodings. This makes the framework potentially useful beyond the specific policy architecture evaluated in the paper.

Critical weaknesses
  1. The scalability claim does not fully account for action-set construction and retrieval costs. The projection method replaces repeated Q-value evaluations with a single policy inference followed by nearest-neighbor decoding. However, the main experiments use a FAISS Flat Index, which performs exact search and has linear retrieval complexity in the number of indexed action embeddings. Thus, the decoding cost still depends on the size of the valid action set. More importantly, for structured decisions such as paths, the set of candidate actions may itself be extremely expensive to enumerate, construct, and embed. Table 1 identifies exponential worst-case action-space growth for Traffic, but the paper does not sufficiently establish how the proposed pipeline avoids this bottleneck in the most challenging settings. The reported inference-time gains are therefore evidence of faster action selection under the evaluated implementation, rather than a general demonstration that the overall method scales efficiently to exponentially large action spaces.

  2. The generalization evaluation protocol may overstate expected deployment performance. Section 4.1 evaluates five episodes per unseen instance and retains the best score, with the resulting scores aggregated using the interquartile mean. This protocol measures best-of-five performance rather than the expected performance of a single execution. Although the paper mentions supplementary evaluation without best-per-environment selection, the headline generalization claims should be interpreted in light of this distinction. It would be useful to report mean and median performance over all evaluation episodes, variability across training seeds, and confidence intervals for the differences between methods. In addition, five independent training runs provide only limited evidence about statistical uncertainty, particularly when the reported gains are modest.

  3. The relationship between self-supervised embedding quality and optimization performance is insufficiently characterized. The graph autoencoder is pretrained on trajectories generated using random valid actions and is not jointly fine-tuned with the RL policy. This design improves modularity and facilitates comparisons in a shared representation space, but graph reconstruction does not necessarily preserve the distinctions that determine action utility. In particular, semantically similar actions may have very different objective consequences, while geometrically nearby action embeddings need not have similar values. Since the default decoder selects the nearest action (k=1), errors in the learned embedding geometry directly constrain which discrete actions can be selected. The current experiments do not fully establish when the embedding space preserves task-relevant action structure, or how sensitive performance is to embedding dimension, pooling choices, and the pretraining distribution.

  4. The comparison with existing methods does not fully establish the practical advantage across all problem classes. The results are mixed rather than uniformly favorable. For example, the iterative method performs particularly well on TSP, matching the reported heuristic reference performance under the specified evaluation budget. The projection method is more competitive on several other benchmarks, especially those with structured actions. This is a useful result, but it suggests that the advantage depends on the problem and action-space structure. The paper would benefit from a clearer analysis of the conditions under which projection is preferable to masked discrete policies, iterative Q-value selection, or strong problem-specific heuristics. Moreover, the comparison focuses primarily on RL policy parameterizations, which limits the strength of claims about overall GCO solver quality.

  5. Inference speed does not capture the complete computational trade-off. The paper's primary scalability metric is action-selection latency, but the complete pipeline also includes graph autoencoder pretraining, repeated GNN recomputation as the partial solution evolves, action embedding construction, and policy training. The discussion acknowledges that projection has higher training cost than the discrete baselines and that evolving partial solutions require repeated GNN computation. These costs may be material for dynamic environments or applications requiring frequent retraining. A more complete analysis should report end-to-end runtime and amortized cost under realistic deployment assumptions, including the number of decisions required to offset the additional representation-learning and indexing overhead.

Questions for authors
  1. Action-space scalability: For the Traffic benchmark, Table 1 reports exponential worst-case action-space growth, while the default decoder uses a FAISS Flat Index. How are valid actions enumerated and embedded in this setting, and what are the memory and runtime costs of maintaining the action index? Can the authors demonstrate end-to-end scaling when the candidate set becomes too large to materialize explicitly?

  2. Generalization evaluation: How do the main results change when all five test episodes per instance are aggregated using their mean or median rather than retaining the best score? Can the authors provide uncertainty estimates across training seeds and establish whether the reported improvements remain statistically meaningful under this evaluation protocol?

  3. Representation quality: Can the authors quantify whether distances between action embeddings correlate with differences in objective value, Q-values, or regret? How sensitive are the results to the graph autoencoder's embedding dimension, reconstruction-loss design, and random-action pretraining distribution?

  4. Comparison with stronger alternatives: Under what conditions does projection outperform a masked discrete policy or an iterative Q-value method? Can the authors characterize the relationship between action-space size, action-embedding geometry, and the performance gap between these methods? In addition, how does projection compare with strong problem-specific heuristics under equal wall-clock budgets?

  5. End-to-end computational cost: Can the authors report total training time, inference latency including graph encoding and action decoding, and memory consumption for representative benchmarks? How many decisions or deployment episodes are needed for the projection method's improved action-selection speed to offset its higher training and representation-construction costs?

  6. Robustness to unseen graph structures: The generalization study varies graph sizes and selected instance parameters. How well does the method transfer to substantially different graph topologies, feature distributions, or action-component combinations that were not represented during training? Does the fixed pretrained encoder remain reliable under such structural distribution shifts?

3 comments
AuthorsOpenReview ↗

Scalability, Evaluation Robustness, and Representation Quality (W1-W3, Q1-Q3)

Response: Part 1/2

We thank Reviewer Qeye for the thoughtful review and positive assessment of our approach, empirical evaluation, and reproducibility contributions.

Action-Space Scalability and Nearest-Neighbor Retrieval (W1, Q1)

Our use of a FAISS Flat Index (exact search with linear retrieval) is a deliberately conservative choice, representing a worst-case setting for Projection in terms of retrieval cost and index size. Nevertheless, Projection scales substantially better than Iterative (Table 4), with scaling exponents of 0.73 vs. 4.68 on Traffic and 0.22 vs. 1.81 on Placement. Importantly, enumerating action embeddings is not a limitation specific to Projection: Iterative also scans the entire action space to score every candidate. For Traffic, the exponential worst-case growth in Table 1 is mitigated in practice by imposing a maximum path length (max_path_len = 4; Appendix D), which bounds candidate paths per demand by excluding longer paths that are rarely optimal. Our claim concerns the relative scalability of action selection across parameterizations, not support for candidate sets too large to materialize, which is beyond our scope. We have clarified this in Section 4.2 of the revised manuscript. Nevertheless, two complementary directions could extend our approach to larger action spaces. First, approximate search can reduce retrieval costs; Appendix L.1 already provides preliminary evidence: on TSP with 500 nodes, an IVF index reduces average action selection time from 0.49 to 0.40 ms/action. Second, action-elimination techniques [1, 2], applicable to all parameterizations, could prune candidates before selection, reducing the effective action-space cardinality to a range closer to that explored in our experiments.

Evaluation Protocol and Statistical Robustness (W2, Q2)

Selecting the best episode among a small number of rollouts from a stochastic policy is a widely adopted practice, including in prior work on graph combinatorial optimization [3, 4]. We deliberately restrict this selection to just five episodes, rather than relying on extensive sampling, to demonstrate that strong performance can already be achieved with a very small number of trials. This is particularly noteworthy given that the heuristic references used for normalization are obtained using up to 10,000 sweeps per instance (Appendix D). Importantly, five episodes do not represent the total evaluation sample size. Each of the 100 test scenarios is evaluated over five episodes, yielding 500 rollout scores per training run and 2,500 across five independent runs per method and setting. Thus, although best-of-five selection is deliberately modest, the overall evaluation covers a substantially larger number of outcomes than five trials. Moreover, results without best-of-five selection are already reported in Tables 16–19 (Appendix M). Tables 12-15 already provide statistical analyses, including mean, percentile-based spread, IQM, bootstrapped confidence intervals, and Shapiro–Wilk tests. Across both evaluation protocols, the top-ranked method remains unchanged in 27 of 28 settings; the only exception is OSPF-S, where Iterative outperforms Projection without best-of-five selection. This confirms that the overall ranking is robust to the selection protocol.

Embedding Geometry and Representation Quality (W3, Q3)

This concern is also raised by Reviewer NaF1, and we refer to our response there for a more detailed discussion. In brief, nearest-neighbor NN decoding measures similarity in the embedding space, not similarity in objective value. The GAE provides a structured representation of graph elements, while the policy learns through reward feedback which regions correspond to desirable actions in each state. Thus, we neither expect nor require embedding distances to correlate with differences in objective value. Regarding sensitivity to the learned representation, our experiments demonstrate that its geometry matters. Table 6 (Appendix F) shows that replacing GAE embeddings with random embeddings substantially degrades performance, yielding scores of 0.36 on TSP, MinVertex, and MaxCut, compared with 0.78, 0.70, and 0.93, respectively, with GAE embeddings. The same table shows further improvements over embeddings based solely on graph features. Table 7 additionally ablates the individual reconstruction losses, while Table 5 reports the selection of the embedding dimension from {16, 32, 64}. Furthermore, the GAE is retrained independently for each training strategy and run (Appendix M), so our results span multiple independently learned embedding spaces. Finally, pretraining on trajectories of randomly sampled valid actions ensures that the representation is not tailored to any particular policy. We also refer the reviewer to our response to Reviewer RqfG for further discussion of the representation-learning procedure and its rationale.

AuthorsOpenReview ↗

Comparative Performance, Computational Cost, and Generalization Robustness (W4-W5, Q4-Q6)

Response: Part 2/2

Comparison Across Action Parameterizations and Problem Classes (W4, Q4)

We agree that the results are mixed rather than uniformly favorable. Nevertheless, across the 28 settings in Table 2, Projection achieves the best or tied-best performance in 15 (strictly best in 12), and reaches the best or tied-best score on six of the seven benchmarks. Its only clear weakness is TSP, where Iterative performs better. As discussed in Section 4.1, action-space cardinality (Table 1) emerges as the primary factor explaining when Projection outperforms alternative parameterizations, with its ability to project higher-dimensional proto-actions being particularly beneficial for handling larger action spaces. The revised manuscript makes this analysis more explicit by reporting the per-setting counts. Our study aims to isolate the effect of action parameterization within a common RL pipeline, rather than claim state-of-the-art solver quality. Nevertheless, Appendix G provides two external reference points under the same instances and evaluation protocol: on MaxCut, Projection outperforms a tuned PI-GNN (0.95/0.95/0.92 vs. 0.92/0.91/0.92 for S/M/L); on TSP, it remains below POMO (0.67 vs. 0.81).

End-to-End Computational Cost (W5, Q5)

GNN pretraining and embedding construction are not overheads exclusive to Projection: they are also required by G-Discrete and Iterative, with only P-Discrete avoiding them. Table 10 (Appendix K) already reports the requested total training time, including GNN pretraining and embedding construction, in the most demanding setting (Traffic, V regime). Projection has the highest training cost (7,460 s on average), compared with 4,175 s for Iterative, 2,449 s for G-Discrete-M, and 787 s for P-Discrete-M (approximately 1.8×, 3×, and 9.5×, respectively). Since GNN pretraining and embedding construction are shared with G-Discrete and Iterative, they explain only part of this difference; the remaining overhead comes from the projection methodology itself. However, this additional cost should be considered alongside the substantial generalization advantages demonstrated in Section 4.1 and the improved inference scalability. Compared with Iterative, Projection scales markedly better in action selection (Table 4) and achieves higher scores in 19 of the 28 settings in Table 2. Compared with the strongest discrete baseline, P-Discrete-M, it performs better in 21 of 28 settings (24 of 28 without best-of-5 selection; Tables 16–19), albeit at higher training and action-selection costs. Importantly, given their more limited generalization, particularly for P-Discrete, discrete methods may require retraining to adapt to changes in the environment, whereas this is not required Projection. Thus, evaluating training costs in isolation overlooks the potential need for repeated retraining.

Robustness to Structural and Feature Distribution Shifts (Q6)

In the S, M, and L regimes, each agent is trained on a single instance and evaluated on 100 unseen instances, whose sizes and parameters are sampled from the ranges specified in Appendix D (e.g., 10–100 cities for TSP and 10–50 nodes with edge probabilities of 0.1–0.4 for MinVertex). Appendix D already details the features varied for each benchmark, illustrating the broad range of scenario characteristics explored. Moreover, in Section 4.1, both the GAE and the RL agent are retrained on each individual training scenario and evaluated on 100 unseen scenarios with substantially different feature distributions. We believe this provides a meaningful assessment of the generalization of both components, including the pretrained GAE. The choice of S and L as training regimes was deliberate: these represent opposite extremes of the feature space and expose the methods to the widest possible structural variations. We therefore believe that these experiments provide a substantial assessment of robustness to both structural and feature-distribution shifts.

We sincerely thank the reviewer again for their time and for the strengths highlighted in the review. Given these strengths, their assessment of the soundness concerns as minor or fixable, and the fact that most of the requested analyses are part of the submitted manuscript (Appendices D, F, G, K, L.1 and M), we respectfully ask the reviewer to reconsider whether the current rating reflects their overall evaluation of our work. We remain happy to address any further questions during the discussion.

References

[1] S. Manchanda et al., "GCOMB: Learning Budget-constrained Combinatorial Algorithms over Billion-sized Graphs," NeurIPS, 2020.

[2] T. Zahavy et al., "Learn What Not to Learn: Action Elimination with Deep Reinforcement Learning," NeurIPS, 2018.

[3] I. Bello et al., "Neural Combinatorial Optimization with Reinforcement Learning," ICLR, 2017.

[4] J. Choo et al., "Simulation-guided Beam Search for Neural Combinatorial Optimization," NeurIPS, 2022.

AuthorsOpenReview ↗

Follow-up on Our Response and Remaining Concerns

Dear Reviewer Qeye,

As the discussion period closes on November 18, we would like to kindly follow up on our response. We made an effort to address each of your points in detail, and we would be grateful to know whether it resolves your concerns.

We are encouraged that your review finds the paper informative and its soundness concerns fixable, and that it values both the breadth of the evaluation and the open-source LaGCO-RL library. We believe this is precisely where the work can benefit the community: a controlled analysis of action parameterizations across seven benchmarks, from classical problems to challenging real-world tasks, and a framework others can build upon. In this light, and with Reviewers NaF1 and RqfG having since updated their assessments, we would sincerely appreciate your considering whether your current rating still reflects your evaluation of our work. We remain at your disposal, and thank you again for your time.

Comments on the paper

1 comment
Area_Chair_M2GwOpenReview ↗

Reminder: Please Review Authors’ Rebuttal and Provide Feedback

Dear Reviewers,

Thank you for your reviews. If you have not already done so, please read the authors' rebuttal and share your feedback in the discussion thread at your earliest convenience. Your timely responses would be greatly appreciated.

Best,
AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.