- 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
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.
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.
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.