acceptodds
Withdrawn from ICLR 2027

Hypervolume-Guided Iterative Reinforcement Learning for Multi-Objective Neural Combinatorial Optimization

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Multi-objective combinatorial optimization requires balancing competing objectives in routing, packing, and other discrete decision problems. Preference-conditioned neural methods commonly use scalarized rewards to train a single policy to construct solutions across different objective trade-offs. However, generating high-quality solution sets remains challenging because scalarized rewards overlook candidates' unique coverage within a group, while using each collected batch for only one policy update limits further quality improvements under a fixed sampling budget. To address this challenge, we propose Hypervolume-Guided Iterative Reinforcement Learning (HGI-RL), a training framework that combines marginal-HV advantage redistribution with repeated trajectory learning to improve solution-set quality. Specifically, exact marginal hypervolume contributions within each instance–preference candidate group redistribute positive advantages, incorporating candidates' unique coverage into the training signal. Moreover, the same trajectories and fixed redistributed advantages support multiple clipped proximal policy optimization (PPO) updates before new candidates are generated, allowing repeated learning from the collected solutions. To evaluate HGI-RL, experiments are conducted on multi-objective traveling salesman, capacitated vehicle routing, and knapsack problems. The results show that HGI-RL achieves competitive solution-set hypervolume.

Primary area:
optimization
Keywords:
Multi-objective Combinatorial Optimization, Deep reinforcement learning, Hypervolume-guided Policy Optimization

Reviews

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

This paper proposes HGI-RL, a training framework for neural multi-objective combinatorial optimization that accounts for both individual solution quality and contribution to set coverage. For candidates generated under the same problem instance and preference, it computes each candidate’s exclusive hypervolume contribution and uses this to redistribute positive scalarized advantages, preserving their total sum and leaving non-positive advantages unchanged. The adjusted advantages remain fixed during multiple PPO updates on the same trajectories. The method requires no additional trainable parameters or changes to inference. Experiments on multi-objective traveling salesman, vehicle routing, and knapsack problems show competitive hypervolume performance, with modest improvements over standard PPO on routing tasks.

Critical strengths
  1. The method distinguishes a solution’s scalarized quality from its unique contribution to set coverage, addressing a relevant limitation of conventional training.
  2. The fixed-backbone PPO comparison isolates the redistribution mechanism, while experiments with WE-CA and CNH demonstrate applicability beyond the proposed backbone.
Critical weaknesses
  1. Hypervolume-guided training, candidate-level advantage reweighting, and trajectory reuse have precedents. The main addition is the specific rule that redistributes positive advantages while preserving their sum.
  2. Insufficient comparison with the closest alternatives. NHDE and CDE are discussed but not evaluated. Comparisons with direct hypervolume rewards and simpler advantage adjustments are also missing, leaving the benefit of the particular formulation unclear.
Questions for authors
  1. Why restrict redistribution to positive advantages and preserve their total sum? How does this compare with directly adding a hypervolume bonus?
  2. How does HGI-RL compare with NHDE and CDE under matched training and inference budgets?
  3. Given the small hypervolume gains over PPO and the tie on knapsack, could the authors report results across multiple independent training seeds, with standard deviations or confidence intervals, to establish whether the improvements are reliable?
Reviewer_UMJAOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes HGI-RL for preference-conditioned multi-objective neural combinatorial optimization. For each instance, it samples a preference vector and generates K POMO trajectories. Within the candidate group for that instance and preference, it computes exact exclusive hypervolume contributions and reweights positive advantages with bounded weights while preserving non-positive advantages, their signs, and the total positive-advantage mass. With trajectories, old-policy probabilities, and reweighted advantages fixed, it performs five clipped PPO updates using full-trajectory probability ratios before sampling a new batch. At inference, it retains the scalarized-best candidate for each preference, applies Pareto filtering, and evaluates HV under a fixed reference point. Experiments use PCAN on bi-objective TSP, CVRP, and knapsack, as well as tri-objective TSP, and also apply the framework to WE-CA and CNH. Same-network ablations show small HV gains over standard PPO on the three routing tasks and a tie on knapsack. The paper distinguishes local training HV from final cross-preference evaluation HV and acknowledges the computational cost at higher objective dimensions.

Critical strengths

1.The paper introduces a fully specified coverage-feedback rule without adding an inference module. Sections 4.2-4.4 and Appendices B/C define the local candidate geometry, exclusive contributions, and positive-advantage reweighting while preserving the original reward and non-positive advantages. The contribution is computed once with gradients stopped, and inference adds no extra search procedure or trainable parameters. The method is therefore easy to integrate into existing preference-conditioned solvers. 2. The same-network comparison and cross-backbone experiments provide preliminary evidence of transferability. In Table 3, HGI-RL and PPO share PCAN, five updates, advantage normalization, and the entropy term; only the reweighting rule is added. In Table 4, WE-CA and CNH improve under Bi-TSP50/Tri-TSP50 settings. Multiple tasks and two additional backbones make the applicability claim more credible, although seed stability remains unverified.

Critical weaknesses
  1. The most serious issue is that Related Work explicitly identifies POCCO as a state-of-the-art NMOCO model, yet the Experiments do not compare against it. After checking POCCO's reported performance, the proposed model appears to underperform POCCO on nearly all test sets.
  2. Statistical stability and training-resource benefits have not been established. Table 3 reports gains over standard PPO of only 0.0003, 0.0002, and 0.0009 HV on Bi-TSP50, Bi-CVRP50, and Tri-TSP50, respectively, while both methods obtain 0.4533 on Bi-KP100. No mean or variance over independent seeds, per-instance effect intervals, or significance results are given. Two hundred test instances cannot substitute for repeated training seeds, and a four-decimal advantage is not automatically reliable. Table 4 likewise reports no uncertainty.
  3. Section 4.4 acknowledges O(BK^2) and O(BK^3) extra work for two and three objectives, with K=n, but reports neither total training time, the fraction spent on HV computation, nor memory growth. An improvement at the same sampling budget is not an improvement at the same wall-clock time. The fast inference in the main tables is also largely attributable to PCAN, since HGI-RL and PPO use the same inference process. The relationship between stable gains and added training cost is central evidence of practical value.
  4. The mechanism of the local-HV heuristic and its advantage over alternatives are insufficiently validated. Contributions are computed only among K trajectories for one instance and preference, while inference retains only the scalarized-best candidate for each preference. Conserving positive-advantage mass does not guarantee higher final cross-preference HV, nor show that exclusive local contribution is better than other diversity signals. The paper reports no reweighting activation rate, non-zero contribution count, duplicate/dominance rate, or correlation between local contribution and final HV improvement.
  5. The weighting function, modifying only positive advantages, reference-point dependence, and five-update choice lack targeted sensitivity studies or alternative-rule controls. The PPO comparison tests overall reweighting but cannot show that gains specifically come from exact HV geometry. Section 2 discusses NHDE, CDE, and POCCO, yet the main experiments provide no direct comparison, leaving the contribution relative to recent work unclear. A global improvement theorem is unnecessary, but empirical evidence is needed to validate this design.
Questions for authors
  1. Why is there no performance comparison with POCCO, a state-of-the-art NMOCO model? Were NHDE/CDE and other coverage-coordination methods omitted because of budget or implementation incompatibility, or were they not evaluated? Under matched tasks and candidate budgets, how do HGI-RL quality and training cost compare? Were the WE-CA/CNH controls in Table 4 also trained from scratch with the same distribution, seed protocol, and checkpoint rule? This affects attribution of cross-backbone gains.
  2. Do the gains in Tables 3 and 4 persist across independent training seeds? Please report seed count, means, standard deviations, and paired HV-difference intervals on the same test instances. Are the 0.0002-0.0003 gains larger than training variation? Is the knapsack tie caused by rare activation or activation without benefit? This determines whether the gains are reliable contributions.
  3. What fraction of total training time and peak memory is consumed by two- and three-dimensional contribution computation? At equal wall-clock time, how does HGI-RL compare with standard PPO? Please show HV curves against sample count and training time. Since REINFORCE and PPO also differ in normalization, entropy, and update count, is the comparison intended only as an overall training-scheme comparison? Are the gains worth the added training cost?
  4. What fraction of candidate groups satisfies Eq. 28, and what fraction of positive-advantage candidates has non-zero exclusive contribution? How do these ratios vary with scale and training stage? Is local-HV weighting better than equally strong random reweighting or simple diversity/ranking weights? Please provide controlled evidence that the gain comes from precise HV feedback rather than generic advantage perturbation.
  5. Full-trajectory probability ratios are not length-normalized, while entropy is summed over decision steps, so length may affect clipping and regularization. Across five updates, what are clipping rates, KL values, and probability-ratio distributions? Could changes to the weighting function, update count, or local reference point reverse the gains? These diagnostics determine whether the design is stable and transferable.
Reviewer_mKqzOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces HGI-RL, a training framework for preference-conditioned neural multi-objective combinatorial optimization. It redistributes positive policy advantages according to candidates' exclusive hypervolume contributions and reuses collected trajectories via multiple PPO updates. Experimental results on multi-objective TSP, CVRP, and KP demonstrate competitive solution quality, with modest improvements over standard PPO on routing tasks. The method is also applied to WE-CA and CNH, suggesting potential applicability across architectures.

Critical strengths
  1. The proposed advantage redistribution integrates exclusive HV contributions into conventional scalarized reward learning without changing the reward definition or policy architecture, which is easy to implement.
  2. This paper evaluates the method across four MOCO benchmarks and applies it to WE-CA and CNH. The fixed-backbone PPO comparison also provides evidence that HV redistribution offers additional improvements on several routing tasks.
Critical weaknesses
  1. The method mainly combines marginal hypervolume contributions with standard PPO. Although the advantage redistribution is a reasonable design, its novelty is relatively incremental, and the paper provides limited justification for the specific weighting scheme. Moreover, trajectory reuse is already a standard feature of PPO.
  2. HV contributions are computed among candidates sharing the same instance and preference, whereas the final Pareto front is constructed across different preferences. It remains unclear whether improving local candidate diversity translates into better global Pareto coverage, especially since only the best scalarized candidate per preference is retained at inference.
  3. Improvements over PPO are marginal (0.0002–0.0009 HV) and absent on Bi-KP100. Moreover, the cross-backbone experiments lack PPO-only controls, making it difficult to isolate the contribution of HV redistribution.
Questions for authors
  1. Could the authors quantify the relationship between same-preference marginal HV contributions and the marginal HV contributions of the solutions retained in the final cross-preference Pareto set? Would computing HV contributions across preferences provide a stronger training signal?
  2. How does the proposed method compare with simpler alternatives, e.g., Pareto-rank weighting, uniform positive-advantage reweighting, or randomized HV-contribution weights? How frequently is redistribution activated, and what fraction of candidates have nonzero exclusive contributions?
  3. What is the training-time and memory overhead relative to PPO? How do the number of PPO updates, trajectory-level clip fraction, and number of objectives affect performance?

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

Related papers

Discussion (0)

Sign in to comment.