Reward-Weighted Preference Optimization for Selective Combinatorial Optimization Problems

📄 arXiv: 2610.31239v1 📥 PDF

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

分类: cs.AI

发布日期: 2026-10-22

备注: 37 pages, 12 figures

💡 一句话要点

提出奖励加权偏好优化以解决选择性组合优化问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 选择性组合优化 奖励加权 偏好优化 强化学习 定向问题 背包问题 策略梯度

📋 核心要点

  1. 现有的组合优化方法多集中于必须服务所有元素的问题，忽视了选择性组合优化问题中的元素选择和目标值差异。
  2. 论文提出奖励加权偏好优化（RWPO），通过根据奖励差异加权偏好损失，强调更大改进的比较，从而提升学习效果。
  3. 实验结果显示，RWPO在OP、PCTSP、随机PCTSP和KP等问题上均优于传统方法，尤其在OP上表现出色，超越了Compass算法。

📝 摘要（中文）

强化学习已成为组合优化的有效方法，但现有方法多集中于所有元素必须服务的问题，如旅行商问题（TSP）。选择性组合优化问题（SCOPs），如定向问题（OP）、奖金收集TSP（PCTSP）、随机PCTSP和背包问题（KP），需要选择包含哪些元素。标准偏好优化将这些比较简化为二元排名，忽略了目标值的差异。本文提出奖励加权偏好优化（RWPO），通过将奖励差异信息纳入偏好学习，提升了选择性组合优化的效果。实验表明，RWPO在多个实例上均优于无权重偏好优化和策略梯度基线，尤其在OP上，其求解器在100到2000节点的规模上超越了Compass元启发式算法的平均奖励。

🔬 方法详解

问题定义：本文旨在解决选择性组合优化问题（SCOPs），如定向问题（OP）和背包问题（KP），现有方法在处理这些问题时，往往将目标值差异简化为二元比较，导致信息损失。

核心思路：论文提出的RWPO方法通过引入奖励差异信息，赋予不同偏好比较不同的权重，从而更有效地学习偏好，提升解决方案的质量。

技术框架：RWPO的整体框架包括样本生成、奖励差异计算、偏好损失加权和策略更新等模块。通过这些模块的协同作用，RWPO能够在训练过程中更好地捕捉到重要的比较信息。

关键创新：RWPO的核心创新在于将奖励差异信息纳入偏好学习中，强调了在选择性组合优化中，比较的幅度比简单的二元比较更为重要。这一设计与传统方法的根本区别在于信息利用的深度。

关键设计：在RWPO中，损失函数根据奖励差异进行归一化处理，确保更大改进的比较在训练中占据更大权重。此外，结合了规模特定的微调和倾斜采样等技术，以适应更大和变化的实例分布。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，RWPO在多个选择性组合优化问题上均显著优于传统的无权重偏好优化和策略梯度基线。在定向问题（OP）上，RWPO求解器在100到2000节点的规模上超越了Compass元启发式算法的平均奖励，展示了其在大规模实例上的优越性。

🎯 应用场景

该研究的潜在应用领域包括物流调度、资源分配和智能决策等场景，能够有效提升选择性组合优化问题的求解效率。随着大规模实例的普遍存在，RWPO方法的推广将对实际应用产生深远影响，推动相关领域的技术进步。

📄 摘要（原文）

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.