Reward-Weighted Preference Optimization for Selective Combinatorial Optimization Problems
Selective combinatorial optimization problems (SCOPs) such as the Orienteering Problem and Knapsack Problem require jointly deciding which elements to serve and how to route or pack them, causing sampled solutions to vary widely in objective value. The paper proposes Reward-Weighted Preference Optimization (RWPO), a training objective that scales each pairwise preference loss by the normalized reward gap between trajectories, preserving cardinal solution-quality information that standard preference optimization discards. This matters because binary preference signals struggle when subset selection creates sparse, high-variance reward landscapes, and the authors show that retaining reward-gap information yields more stable training and stronger generalization to large instances.
RWPO is a conceptually sound and empirically strong extension of preference optimization for SCOPs. The reward-weighted all-pair formulation alleviates the instability of pure PO and the variance of POMO, and the full pipeline achieves state-of-the-art results on OP, PCTSP, SPCTSP, and KP at scales up to 2,000 nodes. However, the paper's theoretical contributions are limited to gradient interpretations and a straightforward corollary, and the reported SOTA performance depends heavily on the additional scale-specific fine-tuning and tilted sampling stages rather than on the RWPO loss alone.
The motivation for reward-weighting is crisp and well-illustrated: the Bradley-Terry model can mis-rank pairs and assign larger gradients to near-ties than to large reward gaps, a pathology that RWPO elegantly fixes by batch-normalized weights. The confidence-regularized all-pair formulation is particularly strong, combining the stability of symmetric pairwise training with an explicit emphasis on larger improvements, which manifests in smooth mean-reward curves where standard PO oscillates. Empirically, the zero-shot scaling results are compelling; on OPLib instances RWPO100 cuts the optimality gap versus Compass by more than half compared with PO100 on 2,000-node OP instances, and the entropy analysis confirms that RWPO maintains diverse decoder queries while concentrating action probabilities.
The theoretical grounding remains weak. The gradient-matching argument only bounds the discrepancy between RWPO and policy-gradient updates under restrictive assumptions and explicitly disclaims strict superiority, improved expected return, or convergence. Corollary 1 is essentially a monotonicity statement that follows directly from the loss design rather than a deep structural result.
Second, the headline results conflate RWPO with scale-specific fine-tuning and tilted sampling: Table 1 shows that base RWPO is often beaten by UDC in the out-of-distribution block, and the SOTA numbers require the post-hoc adaptation stages. The ablation study compares ordered versus all-pair RWPO but does not isolate the marginal contribution of tilted sampling versus fine-tuning, leaving it unclear how much each stage contributes. Finally, the length-normalization coefficient $\beta$ and the reward-weighting strength $\lambda$ are hand-tuned per problem class without an adaptive mechanism, which limits portability.
The evidence supports the core claim that RWPO improves over standard PO and POMO: PO collapses at larger scales (e.g., 56% gap on OP500) while RWPO maintains single-digit gaps zero-shot, and the training curves show RWPO all-pair stabilizes mean reward where PO oscillates. Comparisons to UDC and BQ are mostly fair, though UDC wins in several out-of-distribution settings and BQ is competitive on OP and KP without any adaptation, so calling the full pipeline SOTA relies on conflating in-distribution adapted results with zero-shot generalization. The distinction from BOPO is accurately drawn—BOPO uses anchor-based comparisons and scales inside the sigmoid, whereas RWPO weights the loss directly—and the Pan et al. (2025a) PO baseline is correctly described as using local-search fine-tuning.
The architecture follows the standard attention-based encoder-decoder of Kool et al. (2019), and the main hyperparameters are reported in Section 4. However, full baseline configurations are deferred to Appendix C, and there is no mention of public code release in the text provided. Exact reproducibility would require the length-normalization heuristic, the per-problem $\lambda$ and $\beta$ choices, and the early-stopping criteria for scale-specific fine-tuning, all of which are detailed but scattered across sections and appendices. The experiments use standard synthetic benchmarks and OPLib, and runtimes are reported on a specific GPU (RTX 5060 Ti), which aids hardware calibration. Independent reproduction is feasible for an expert practitioner but would be greatly facilitated by releasing training code and checkpointed policies.
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.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.