PaperlayerView exact revision on arXiv

Source-linked AI summary

Reward-Weighted Preference Optimization for Selective Combinatorial Optimization Problems

Haohui Zhang, Xinyu Hu, Wouter van Heeswijk, Neil Yorke-Smith, Martijn Mes

arXiv:2610.31239v1cs.AI

TL;DR

In selective combinatorial optimization, sampled solutions can have widely different rewards, yet standard preference optimization reduces comparisons to binary rankings. The paper introduces RWPO, which weights pairwise learning by reward gaps and combines it with scale adaptation; experiments report improvements across SCOP tasks and scales.

  • Problem

    In SCOPs, subset choices can create large differences in solution quality, but standard preference optimization discards reward-gap magnitude by reducing comparisons to binary preferences.

    Source: §1 · p. 2

  • Method

    RWPO weights pairwise preference learning by normalized reward gaps and is combined with scale-specific fine-tuning and tilted sampling for adaptation.

    Source: §1 · p. 2

  • Results

    Across SCOP benchmarks, the resulting solver is reported to achieve state-of-the-art solution quality and robust generalization to larger instance sizes.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Preserving reward-gap information can improve preference-based learning for SCOPs, where subset-selection decisions can yield sharply different solution quality.

    Source: §5 · p. 11

    RWPO relies on exact reward evaluations, which may be difficult to obtain in partially observable or multi-objective environments.

    Source: §5 · p. 11

Abstract

from arXiv · show

Reinforcement learning has emerged as an effective approach for combinatorial optimization, but most existing methods focus on problems such as the Travelling Salesperson Problem (TSP) in which all elements must be served. Selective combinatorial optimization problems (SCOPs), including the Orienteering Problem (OP), Prize-Collecting TSP (PCTSP), Stochastic PCTSP and Knapsack Problem (KP), additionally require selecting which elements to include. This selection creates sampled solutions with substantially different objective values, yet standard preference optimization reduces such comparisons to binary rankings and discards the magnitude of these differences. We introduce Reward-Weighted Preference Optimization (RWPO), a pairwise training objective that incorporates reward-gap information into preference learning. For candidate trajectories sampled from the same instance, RWPO weights each preference loss according to the normalized difference in their rewards, assigning greater training emphasis to comparisons that represent larger improvements in solution quality. We further combine RWPO with scale-specific fine-tuning and reward- and likelihood-weighted tilted sampling to adapt trained policies to larger and shifted instance distributions without relying on local-search post-processing. Experiments on the OP, PCTSP, Stochastic PCTSP, and KP show that RWPO consistently improves over unweighted preference optimization and policy-gradient baselines across a wide range of instance sizes. On the OP, the resulting solver exceeds the mean reward of the Compass metaheuristic at scales from 100 to 2,000 nodes. The results demonstrate that preserving reward-gap information can substantially improve preference-based learning for selective combinatorial optimization and support generalization to large-scale instances.

1 Introduction

Selective combinatorial optimization requires choosing which elements to include, producing candidate solutions with widely varying quality that binary preference labels treat alike. The paper introduces reward-gap-weighted preference learning and combines it with scale adaptation for SCOP solvers.

1 Introduction

  • The framework targets SCOPs such as OP, PCTSP, Stochastic PCTSP, and KP, where selecting elements is part of constructing a feasible solution.Unlike TSP and CVRP, these problems require choosing which elements to include.Source: §1 · pp. 1–2
  • RWPO weights pairwise preference losses by normalized reward gaps, preserving solution-quality differences discarded by standard binary preferences.It retains all sampled rollout pairs and uses a shared inverse-temperature parameter.Source: §1 · p. 2
  • The confidence-regularized all-pair formulation avoids strong separation for small reward differences while giving larger improvements stronger supervision.It combines weighted-reward-gap preference fitting with a symmetric pairwise penalty over sampled rollout pairs.Source: §1 · p. 2
  • Scale-specific fine-tuning and tilted sampling adapt policies to larger and shifted instance distributions without retraining from scratch or local-search post-processing at inference.The pipeline combines these adaptation components with RWPO.Source: §1 · p. 2
  • Across SCOP benchmarks, the resulting solver is reported to achieve state-of-the-art solution quality and robust generalization to larger instance sizes.The paper also evaluates zero-shot cross-scale generalization separately from adaptation gains and compares against preference and policy-gradient baselines.Source: §1 · p. 3

2 Preliminaries

The preliminaries describe constructive policies, their reinforcement-learning training and the preference-optimization alternative. They motivate within-instance comparisons for SCOPs, where early selections shape feasible regions and reward differences can be substantial.

2.1 Constructive Neural Solvers

  • Constructive neural solvers use a stochastic policy to build feasible solutions sequentially, with masked actions enforcing feasibility and reward assigned to the completed trajectory.An encoder represents the instance, and an autoregressive decoder selects the next feasible node, item, or operation.Source: §2.1 · p. 3

2.2 Reinforcement Learning for COPs

  • Standard policy-gradient training maximizes expected reward, but can suffer high variance, weak trajectory-level credit assignment, unstable updates, and inefficient learning in large decision spaces.These challenges are more pronounced in SCOPs with substantially different feasible-solution rewards.Source: §2.2 · p. 3
  • POMO-style multi-start decoding selects promising first actions and runs parallel rollouts, but SCOP branch heterogeneity makes reward-based policy gradients noisy.Preference comparisons among candidate trajectories from the same instance provide a more stable learning signal.Source: §2.2 · pp. 3–4

2.3 Preference Optimization for COPs

  • Preference optimization models pairwise preference probabilities from policy log-likelihood differences and trains on observed preference pairs rather than scalar-reward policy gradients.Its inverse-temperature parameter controls preference sharpness.Source: §2.3 · p. 4
  • Standard preference optimization treats correctly ordered pairs equally, although exact reward gaps are available and can differ greatly between sampled trajectories.RWPO weights preference loss according to the normalized reward gap; equal-reward pairs are excluded from preference learning.Source: §2.3 · p. 4

3 Methodology

RWPO weights preference updates by reward gaps, including a confidence-regularized all-pair formulation. The method also adapts policies to larger scales through offline fine-tuning and tilted sampling, without local-search inference post-processing.

3.1 Reward-Weighted Preference Optimization

  • RWPO weights pairwise preference log-likelihoods by normalized reward gaps, emphasizing large improvements over near ties while retaining a shared inverse-temperature parameter.Source: §3.1 · pp. 4–5
  • Under bounded gradients and policy-matched pair sampling, RWPO’s update discrepancy from policy gradients is bounded by effective coefficient mismatch, motivating resemblance but not establishing superiority or convergence.Source: §3.1 · p. 5
  • The confidence-regularized all-pair variant evaluates both directions for each rollout pair, retaining likelihood terms while weighting the better trajectory’s direction according to its reward gap.Its symmetric component smooths learning over the rollout set, while the reward-weighted component distinguishes near ties from larger improvements.Source: §3.1 · p. 5

3.2 Training and Adaptation Pipeline for SCOPs

  • For larger target scales, the pipeline uses offline scale-specific fine-tuning and tilted sampling, avoiding local-search post-processing during inference.Source: §3.2 · p. 5
  • Low-learning-rate fine-tuning conservatively refines the RWPO policy for a target distribution, using small batches, reduced multi-start sizes, and early stopping to limit offline adaptation cost.Source: §3.2 · p. 6
  • Tilted sampling adapts from self-generated target-scale rollouts weighted by reward and frozen-policy likelihood, then uses weighted behavioral cloning while preserving structural priors.Source: §3.2 · p. 6

4 Experiments

The experiments evaluate RWPO against neural and heuristic baselines across standard SCOP benchmarks, scale shifts, and decoding behavior. Results cover benchmark performance, cross-scale generalization, entropy patterns, and training stability.

4.2 Analysis of Generalization

  • RWPOcross achieves the lowest OPLib optimality gaps across problem sizes, including 4.23% on the smallest scale and 22.82% on the largest.The zero-shot evaluation uses Euclidean 2D OPLib Generation 3 instances; combining scale-specific models adds only a modest inference-time increase.Source: Table 2 · p. 8, §4.2 · p. 8

4.1 Comparison with Existing Algorithms on Standard Benchmarks

  • RWPO+TS establishes a new state of the art across OP, PCTSP, SPCTSP, and KP, including a 4.92% improvement at OP2000 on Compass.It consistently outperforms UDC and regularly matches or exceeds OR-Tools and Compass while requiring seconds to minutes of computation.Source: §4.1 · p. 8, Table 1 · p. 9

4.2 Analysis of Generalization

  • Across OP sizes and travel budgets, RWPO has smaller objective gaps against Compass than standard PO and POMO, with a stronger advantage on larger instances.As travel budgets increase and OP shifts toward dense routing, RWPO maintains strong performance.Source: §4.2 · pp. 8–9, Figure 2 · p. 10

4.3 Entropy Analysis

  • RWPO variants combine lower early-stage policy entropy with maintained or recovered decoder-query diversity over substantial late-decoding intervals.Fine-tuned variants can retain high query diversity despite concentrated action distributions, especially RWPO-FT500 on OP500 and RWPO-FT1k on OP1000.Source: Figure 3 · p. 10, §4.3 · p. 10

4.4 Ablation Study

  • On OP100, PO and RWPO variants have similar best rewards, but standard PO’s mean reward is oscillatory and fails to stabilize while RWPO all-pair remains smooth and stable.The stability pattern also appears in OP500 OOD evaluation and PCTSP, with SPCTSP and KP results reported in the appendix.Source: §4.4 · pp. 10–11, Figure 5 · p. 11

5 Discussion and Conclusion

RWPO combines reward-gap preference learning with an adaptation pipeline and is reported to achieve state-of-the-art performance across four SCOP benchmarks. The discussion situates this objective alongside neural construction and divide-and-conquer approaches, while noting limitations and open questions.

5 Discussion and Conclusion

  • RWPO with top-k selective decoding, scale-specific fine-tuning, and tilted sampling achieves state-of-the-art performance across four SCOP benchmarks.The discussion also reports stronger out-of-distribution generalization than PO and greater training stability than standard POMO.Source: §5 · p. 11
  • RWPO relies on exact reward evaluations, which may be difficult to obtain in partially observable or multi-objective environments.The authors also note that reward-weighting strength and length-normalization are fixed, and that the proposed link between representation diversity and generalization remains observational.Source: §5 · p. 11

A.1 RL-based Neural Network Solvers

  • Neural solver research has addressed scaling through changes to policy architecture, action representation, search, conditioning, and training distribution; RWPO instead changes the optimization objective.The paper describes the approaches as complementary.Source: §A.1 · p. 15

A.2 Neural Divide-and-Conquer Methods

  • Divide-and-conquer methods partition large instances, solve subproblems, and combine partial solutions, but unfavorable early splits can restrict later improvements.The discussion highlights SCOPs as especially vulnerable because localized partitions can fragment the global budget and block globally dispersed subsets.Source: §A.2 · p. 15

A.3 Preference-based Reinforcement Learning Methods

Preference-based methods learn from comparisons, but standard pairwise optimization can discard reward-gap information and summed trajectory log-probabilities can create length bias. The section motivates reward-weighted comparisons as a way to emphasize pairs with larger quality differences.

A.3 Preference-based Reinforcement Learning Methods

  • Preference-based RL learns from trajectory comparisons, while direct preference-optimization methods avoid a separate reward-model stage and include likelihood-based reweighting in WPO.WPO’s weights reflect policy likelihood rather than the reward gap between solutions.Source: §A.3 · p. 16

B.1 Decoding-Length Bias of Summed Log-Probabilities in SCOPs

  • Summed per-step log-probabilities can make longer trajectories more negative and cause PO to favor shorter routes beyond the intended preference for higher reward.The appendix introduces a length-adjusted trajectory score; its β parameter is set to 0.3 for OP and KP and 0.1 for PCTSP and SPCTSP.Source: §B.1 · p. 16

B.2 Motivation for Reward-Weighted Preference Optimization

  • In the illustrative pairs, PO’s larger gradient can prioritize correcting a negligible reward-gap misranking over a comparison with a much larger reward gap.The stated structural issue is that PO’s update magnitude depends on model probability error rather than reward-gap size.Source: §B.2 · p. 17
  • RWPO scales pairwise logistic comparisons by a function of reward gap, so pairs with larger solution-quality differences receive greater emphasis.The appendix describes this weighting as preserving the preference direction while incorporating cardinal reward information.Source: §B.2 · p. 17

B.3 Gradient Analysis of RWPO Objectives

The appendix analyzes how RWPO’s reward-dependent weights affect pairwise gradients and preference margins, then relates weighted preference updates to policy gradients. It also describes tilted sampling as a reward- and likelihood-guided adaptation procedure and lists the comparison baselines.

B.3 Gradient Analysis of RWPO Objectives

  • For ordered pairs, larger reward gaps produce larger RWPO gradient magnitudes at the same current margin; the confidence-regularized all-pair objective instead induces finite optimal margins that grow with reward gap.Near-tie pairs can remain weakly separated, while the symmetric baseline regularizes pairwise confidence.Source: §B.3 · pp. 17–18

B.4 Gradient-Matching Interpretation of Reward-Weighted Preference Optimization

  • The gradient-matching analysis holds sampled trajectories and reward-dependent weights fixed during differentiation, with a fixed sampling support mask.It notes this condition for top-k selective decoding when the selected support mask remains fixed during the backward pass.Source: §B.4 · p. 19

B.4.1 Pairwise Representation of the Policy Gradient

  • The policy-gradient update can be represented using pairwise trajectory differences, with positive and negative reward-gap pairs contributing equally before restricting to preferred-direction pairs.The representation assumes the reward function is independent of policy parameters.Source: §B.4.1 · p. 20

B.4.2 Policy-Score Update Induced by Weighted Preference Optimization

  • The weighted preference-loss gradient uses the pairwise policy-score direction multiplied by a reward- and margin-dependent coefficient.The appendix gives this gradient for a fixed pair-sampling distribution.Source: §B.4.2 · p. 20, §B.4.3 · p. 21

B.4.3 Coefficient-Matching Bound

  • Under a bounded-gradient assumption, the difference between the policy-gradient and preference-learning updates is bounded by their scalar-coefficient mismatch.The RL coefficient is the reward gap, while the preference coefficient depends on the pair weight and current margin; the authors frame this as a gradient-matching motivation, not a convergence guarantee.Source: §B.4.3 · p. 21

B.5 Tilted Sampling

  • Tilted sampling combines task reward with base-policy likelihood, using a finite candidate set because the full trajectory-space normalizer is intractable.The likelihood term anchors the adapted policy to trajectories plausible under the pretrained model, while reward favors higher-quality trajectories.Source: §B.5 · p. 22

C.1 Baselines

  • The appendix lists LKH3 and OR-Tools as classical baselines, Compass for OP, and neural constructive and divide-and-conquer comparison methods.The neural baselines include AM, POMO, ICAM, MDAM, Sym-NCO, PO, GLOP, and UDC.Source: §C.1 · p. 23

C.2 Dataset

The appendix describes the OPLib benchmark setup, hyperparameter reporting, and a soft-entropy estimator for hidden representations. It distinguishes representation diversity from decoder action uncertainty and reports an association between RWPO and richer representations.

C.2 Dataset

  • The OPLib evaluation focuses on Generation 3 instances, whose reward-generation rule is closest to training and supports testing transfer to benchmark geometry and budget structures.This choice avoids an additional reward-distribution shift that would confound the comparison.Source: §C.2 · p. 23

C.3 Hyperparameters Setting

  • Table 3 reports hyperparameter settings for POMO, PO, and RWPO, with RWPO’s attention layer matching those of POMO and PO.The supplied caption identifies the table’s scope as hyperparameter settings.Source: §C.3 · p. 23, Table 3 · p. 24

D.1 Soft Entropy Estimation

  • The soft-entropy estimator softly quantizes hidden representations against reference directions and computes Shannon entropy over the resulting categorical distribution.The estimator is presented as a differentiable alternative to hard binning or clustering-based approaches for continuous neural representations.Source: §D.1 · pp. 23, 25
  • The estimator averages layer-wise soft entropy and applies separately to encoder and decoder representations, with normalized values in [0, 1].Values near 1 indicate representation mass spread relatively evenly across anchor directions; smaller values indicate concentration around fewer directions.Source: §D.1 · pp. 24–25

D.2 Interpretation of Representation and Policy Entropy

  • Policy entropy measures decoder-action uncertainty, whereas soft entropy measures hidden-representation diversity; the authors report that RWPO preserves richer encoder representations and structured decoder-query representations.They describe this representation finding as suggesting improved generalization, while cautioning that high decoder-query soft entropy is not behavioral uncertainty.Source: §D.2 · pp. 25–26

D.3 Mutual-Information Analysis

The mutual-information analysis distinguishes task-relevant representations from merely diffuse features. Additional CVRP experiments report that RWPO mitigates zero-shot degradation and that scale-specific adaptation with tilted sampling improves larger-scale performance.

D.3 Mutual-Information Analysis

  • The mutual-information analysis uses static instance labels for encoder representations and dynamic decision-state labels for decoder-query representations.The labels include reward and geometry as well as accumulated reward, remaining budget, feasible actions, and trajectory membership.Source: §D.3 · p. 26
  • Higher decoder-query mutual information with feasibility- and preference-related labels indicates that representation diversity captures structured decision information rather than unstructured randomness.Source: §D.3 · p. 26

E.1 Comparison with Existing Algorithms on CVRP

  • At N = 500 and 1,000, RWPO reduces CVRP optimality gaps versus standard PO from 17.53% to 14.10% and from 45.78% to 38.35%, respectively.Source: §E.1 · p. 26
  • RWPO+TS limits CVRP optimality gaps to 2.45%, 4.40%, and 7.21% at N ∈{500, 1000, 2000}, respectively, and remains competitive with specialized methods in-distribution.The authors attribute this adaptation pattern to RWPO providing a robust initialization that tilted sampling subsequently refines.Source: §E.1 · p. 26

E.2.1 Comparison Between Local Search Fine-tuning with Scale-specific Finetuning and Tilted Sampling

The section compares adaptation strategies through likelihood–quality frontiers, larger-scale generalization results, and route-level representation visualizations. Scale-specific fine-tuning followed by tilted sampling yields the strongest reported transfer gains, while the visual analyses describe how adaptation redistributes trajectory quality and representation diversity.

E.2.1 Comparison Between Local Search Fine-tuning with Scale-specific Finetuning and Tilted Sampling

  • At N = 500, RWPO-FT samples occupy a higher objective region despite lower base-policy likelihood, and tilted sampling slightly improves the binned quality curve.At N = 100, adapted policies remain concentrated in relatively high-likelihood regions; the section defines likelihood as length-normalized log-likelihood and objective value as the vertical axis.Source: §E.2.1 · pp. 26–28
  • RWPO-FT-TS stays closer to the base policy’s high-likelihood region, whereas LS-guided fine-tuning explores trajectories farther from that region.The authors describe tilted sampling as reward-guided redistribution anchored by base likelihood, while noting that LS guidance may entail a larger policy shift requiring further robustness evaluation.Source: §E.2.1 · p. 28

E.2.2 Fine-tuning does not degrade generalization ability.

  • 6.71% average improvement transfers from N = 200 to N = 500 and N = 1000, while N = 500 fine-tuning improves transfer to N = 1000 by 9.42%.Applying tilted sampling after N = 500 fine-tuning adds 1.54% improvement with no degradation; RWPO-TS also has a 100% better/equal rate.Source: Table 6 · p. 28, §E.2.2 · p. 29

E.3 Representation Diversity under Scale Generalization

  • Route-level visualizations associate RWPO’s richer early decoder-query representations with route shaping, while RWPO-FT500 maintains diversity into high-reward regions before concentrating near route completion.The authors report fewer crossings and better geometric route quality for RWPO-FT500.Source: §E.3 · p. 29

E.4 Mutual Information Between Hidden Representations and Task-Relevant Labels on OP

The analysis finds a scale-dependent division of information between encoder and decoder representations, and examines how task-relevant decoder information changes over route-construction stages.

E.4 Mutual Information Between Hidden Representations and Task-Relevant Labels on OP

  • Encoder representations carry strongest mutual information with static instance attributes, especially depot distance and node reward, while decoder queries carry more information about dynamic route-construction variables.The decoder variables include budget–feasibility, feasible actions, remaining budget, and current distance.Source: §E.4 · pp. 29–30
  • At N = 500, PO shows attenuated decoder information for accumulated reward and constraint-related variables, while RWPO retains strong information about budget–feasibility, feasible actions, remaining budget, and current distance.POMO remains comparable to RWPO on some labels, so the heatmaps do not establish uniform RWPO superiority over POMO.Source: §E.4 · p. 30
  • At N = 500, RWPO retains feasibility and budget signals during middle decoding stages before shifting toward distance and trajectory-quality signals later.PO becomes more narrowly focused on distance and outcome-related signals; RWPO-FT500-TS variants amplify the staged pattern.Source: §E.4 · p. 30

E.5 Training Curves

Across OP, PCTSP, KP, and CVRP training curves, RWPO is generally more stable across sampled rollouts than PO. The authors connect this pattern to RWPO’s all-pair updates scaled by reward differences.

E.5 Training Curves

  • On KP200, RWPO has substantially lower variance than PO despite similar final mean values, while on CVRP100 it maintains lower objective cost for nearly all training and a small best-objective advantage.On SPCTSP100, RWPO improves mean objective smoothly while PO remains oscillatory; on OP, RWPO also has less noisy batch-wide mean performance despite competitive best-rollout results.Source: §E.5 · p. 30

F Ablation Study of Hyperparameters

The sensitivity analysis finds reward-gap weighting beneficial at moderate strength and stronger length normalization helpful at larger OP scales.

F Ablation Study of Hyperparameters

  • The reduced-budget OP50 and OP100 analysis screens reward-weighting and length-normalization settings for configurations intended to transfer across scales.The authors do not exhaustively tune the hyperparameters.Source: F Ablation Study of Hyperparameters · p. 30
  • Moderate reward-gap weighting consistently improves final validation objectives over the ordinal baseline, while excessive weighting adds no gains and risks destabilizing updates.The authors adopt λ = 0.5 as a conservative default for the main OP experiments.Source: F Ablation Study of Hyperparameters · p. 30, Table 7 · p. 31, Table 8 · p. 31
  • OP100 benefits from stronger length normalization than OP50 because larger instances produce longer trajectories with greater variance in cumulative log-likelihood.The experiments fix β = 0.3 across OP scales.Source: F Ablation Study of Hyperparameters · pp. 30–31
  • On N = 100, fine-tuning and tilted sampling shift solutions toward higher quality while retaining relatively high base-policy likelihood; at N = 500, adaptation raises the upper quality envelope.Local-search fine-tuning produces a significantly larger distribution shift than fine-tuning or tilted sampling at N = 100.Source: Figure 6 · p. 32
  • RWPO optimization is smoother and more stable than PO on SPCTSP100, KP200, and CVRP100, with lower training variance on KP200 despite similar final values.The clearest final improvements occur on SPCTSP100 and CVRP100.Source: Figure 12 · p. 37

Related papers

Loading 2610.31239v1…