acceptodds
Under review as a conference paper at ICLR 2027

Structured Value Function Parameterization for Neural Routing Solvers

Abstract

Learning heuristics for combinatorial optimization problems through reinforcement learning and deep neural networks has seen a surge of interest in recent years. We revisit the use of value functions in this setting, as many implementations still rely on simple average reward baselines, computed from multiple samples of the same instance. For the class of binary programs with linear objectives, we formulate a Markov decision process, where the policy sequentially assigns the decision variables, and show that its value function decomposes exactly into the cost-weighted sum of the marginal inclusion probabilities of the undecided variables. We utilize this insight as an architectural prior by parameterizing the critic to predict those probabilities rather than a scalar directly. Our experiments show that the structured parameterization improves policy performance and reduces sensitivity to the critic learning rate, achieving state-of-the-art results on the challenging multi-task vehicle routing problem environment, consisting of 16 routing variants. Additionally, we show that the learned value function can be used at inference time to guide a truncated rollout search, which produces favorable results on the pareto front for longer time budgets. Finally, our MDP framework also reveals that some states can be automatically stepped through, when the constraints of the problem imply a single legal action. Such states contribute no policy gradient and, especially during early training, account for a substantial share of all states, leading to considerable efficiency gains.

Primary area:
optimization
Keywords:
Neural Combinatorial Optimization, Vehicle Routing, Reinforcement Learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_nDGmOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

Almost every modern RL-based neural solver for combinatorial optimization is trained with REINFORCE. This work represents a step forward and uses PPO with a learned per-state value estimate. Although PPO with a per-state critic is not new, even in the domain of NCO, this work proposes a new way of building the critic. Instead of predicting the value directly, it predicts the probability of each edge being used and computes the value as the distance-weighted sum of those probabilities. Apart from that, this work combines best practices from recent efficient architectures for NCO, and the final result looks impressive: exhaustive experiments show that the proposed method outperforms existing state-of-the-art models for solving VRPs. However, it is not completely clear whether the gain comes from the architectural design or from the learned per-state value estimate, which is supposed to be the main contribution of this paper. Also, scalability may limit the value of this method.

Critical strengths
  1. The idea is simple and elegant and represents a new way of designing value functions for training NCO policies.

  2. The experiments are carefully performed: all baselines are rerun in their own settings, and the strongest decoding is reported. Even so, under the same decoding, the proposed method clearly outperforms the SOTA baselines.

Critical weaknesses
  1. A central motivation of the paper is that the shared baseline is the main limitation of existing methods, and I strongly share that view. The paper claims to address this limitation through a better value estimate, but this is not clear from the results. This work uses a more powerful model that re-encodes the state at every step, so it is not clear whether the gain comes from better value estimation or from the architecture. Table 1 shows that the generic mean-pool critic already strongly outperforms existing baselines, which suggests that the gain comes from the architectural design. I suggest an additional set of experiments (Q1) that could answer this question.

  2. The existing experiments are limited to instances of size 50 and 100. The proposed heavy-decoder architecture is very costly and much slower than other baselines (up to 20x on VRPs100). A comparison of the results for VRPs50 and VRPs100 shows that inference time increases by about 5x. This raises concerns about scalability, both in time and memory, which I consider the main limitation of this work. The additional experiments requested in Q2 and Q3 could address my concerns.

Questions for authors

Q1. My main concern is whether the paper’s main contribution, the structured value function, is really responsible for the performance gain, or whether this claim is overstated. The proposed method uses a very powerful NCO model combined with modern add-ons (RMSNorm, squared-ReLU MLPs, and the Muon optimizer). It is unclear whether the gains come from this architecture and these recipes or from the novel structured value function. In addition, your mean-pool variant already beats every baseline by a wide margin, which suggests that the gain does not come from the structured critic. The cleanest way to separate the impact of all these factors is to evaluate all four possible combinations of architectures and training methods.

Your work already covers:

  1. An encoder-decoder POMO-style architecture trained with REINFORCE (existing baselines)
  2. A decoder-only architecture trained with PPO and the structured critic (your model)

The following combinations are missing:

  1. A POMO-like architecture trained with PPO and the structured critic
  2. A decoder-only architecture trained with REINFORCE

I believe that configurations 3 and 4 can support the paper’s main claim by showing whether per-state value learning really helps, independently of the underlying architecture.

Q2. Decoder-only architectures have a very good ability to generalize across different problem sizes, including larger instances, but they are trained by imitation learning or self-improvement rather than RL. Since your 100-node model is fine-tuned from the 50-node model, does this mean that this nice property of decoder-only models is not preserved by your training? Could you report how the model trained on 50 nodes performs on 100-node instances?

Q3. Could you evaluate your 100-node model on larger instances (e.g., 200, 500, and 1000 nodes), showing how much performance degrades and how running time scales? Additionally, could you try the reverse direction, i.e., applying your model trained on 100 nodes to instances with 50 nodes?

Q4. Your PPO uses generalized advantage estimation, but its parameters are not mentioned: Table 5 lists neither γ\gamma nor λ\lambda. Since the introduction motivates your work partly through bootstrapped advantage estimation, could you report these parameters? If λ=1\lambda = 1, there is no bootstrapping; the critic then serves only as a per-state baseline. An ablation on \lambda would show whether bootstrapping contributes to the performance gain.

1 comment

Thank you very much for your answers.

I accept your point about training a decoder-only model with REINFORCE, since you refer to the LEHD paper. However, that paper mentions this only briefly and does not study it in detail. I also still believe your method could be applied to models with static embedding computation (AM, POMO-based). This would make your contribution more useful.

Scalability. It is a legitimate choice to focus on in-distribution performance and not on scalability. However, I think this is a significant limitation of the work. We know that other baselined do not scale well because they use POMO-like architectures, which are known for poor generalization. The main idea of models with dynamic embedding computation is scalability. They are usually slow, but they generalize better and this message is missing here. In the current setting, your model has roughly the same performance as other models with greedy decoding, while with multi-start decoding it is slightly better, but at a high cost. In this second case, I doubt that the proposed method would still be better than the baselines with the same time budget.

Generalization. I agree that it is unclear what level of generalization to expect, but this is easy to check. I am surprised that these experiments were not run, because you already have pretrained models and only need cheap inference on larger instances. The cross-size evaluation between n=50 and n=100 is helpful, but a 2× change in size says little about the regime where decoder-only models are known to vary. I strongly encourage you to evaluate on larger sizes (for example n=200, 500 and 1000, even on some problems). BQ-NCO and LEHD lose about 2× in performance on CVRP, so this can be a reference for what we should expect. It would be useful to show that your model has similar behavior.

Since, many of my concerns are not properly addressed, I will keep my score.

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

This paper studies value estimation for constructive neural routing. Instead of predicting a scalar value directly, the critic predicts edge inclusion probabilities and combines them with the known edge costs. The method is evaluated with PPO on 16 vehicle-routing variants, together with an auto-step mechanism and a value-guided truncated rollout at inference time.

Critical strengths

The critic design is simple and well motivated. The overall results are strong across the 16 routing variants.

Critical weaknesses
  1. The discussion of per-state value learning should better acknowledge prior work. RLOR [1], for example, already used PPO with a critic that estimates values at intermediate routing states. More importantly, while Table 1 isolates the effect of the critic head within PPO, it does not directly test the paper's motivation for moving away from shared rollout baselines. A comparison using the same actor trained with a shared-baseline REINFORCE method would help clarify this benefit.

  2. The structured critic is only tested with light decoder based architecture. It would be useful to see whether it also improves other heavy-decoder methods, such as LEHD [2] or BQ-NCO [3]. This would help establish whether the improvement transfers to different decoder architectures.

[1] RLOR: A Flexible Framework of Deep Reinforcement Learning for Operation Research.

[2] Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization.

[3] BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization.

Questions for authors

See weakness.

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

The paper proposes to substitute the scalar value function in reinforcement learning with a different function.

The paper describes the notation and the problem.

Experimental validation is performed on MTVRP (Multi-task vehicle routing), CVRP, VRPTW, OVRP, VRPL.

Critical strengths

Proposing a different way to represent the value function is a potentially very interesting contribution.

Extensive experimentation on VRP problems.

Why not compare with standard value-function RL methods and potentially to other RL methods (PPO for examplel)?

Critical weaknesses

It is not clear how, from Equation (3), which is the core of the approach, we can derive a non-scalar value function.

The method is suppose to be generic, why only VRP are considered?

Why not compare with other RL methods?

Questions for authors

see weakness

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.