Baseline-Free Policy Optimization for Neural Combinatorial Optimization

📄 arXiv: 2606.10321v1 📥 PDF

作者: Carlos S. Sepúlveda, Gonzalo A. Ruz

分类: cs.LG, cs.AI, cs.RO, math.OC

发布日期: 2026-06-09

💡 一句话要点

提出无基线策略优化以解决神经组合优化问题

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 神经组合优化 无基线策略 强化学习 路径优化 算法比较

📋 核心要点

  1. 现有的REINFORCE算法依赖基线来减少方差，但在困难实例中，劣质基线会导致训练不稳定。
  2. 本文提出的GRPO算法通过在采样轨迹组内标准化优势，完全消除了基线的需求。
  3. 实验结果显示，GRPO在TSP-100上避免了训练崩溃，并在解质量上与POMO相当，且无需外部基线。

📝 摘要（中文）

神经组合优化（NCO）通过训练自回归策略来解决路由问题。传统的训练算法REINFORCE依赖于基线来减少方差，但在困难实例中，劣质基线会导致训练不稳定。本文评估了无基线的Group Relative Policy Optimization（GRPO）算法，发现其在TSP和CVRP基准测试中表现优异，避免了REINFORCE在TSP-100上训练崩溃的问题，并在不依赖外部基线的情况下，达到了与强基线POMO相近的解质量。这些结果表明GRPO在基线依赖训练变得脆弱的情况下是一个有前景的替代方案。

🔬 方法详解

问题定义：本文旨在解决神经组合优化中的训练不稳定性问题，现有的REINFORCE算法依赖于基线来减少方差，但在处理困难实例时，劣质基线会导致梯度估计噪声，从而影响训练效果。

核心思路：论文提出的GRPO算法通过在采样轨迹组内标准化优势，消除了对基线的依赖。这种设计旨在提高训练的稳定性，尤其是在面对复杂问题时。

技术框架：GRPO的整体架构包括采样轨迹的生成、优势的计算与标准化，以及策略的更新。通过对多个轨迹组的优势进行归一化，GRPO能够有效减少训练过程中的方差。

关键创新：GRPO的主要创新在于完全消除了基线的使用，这与传统方法形成了鲜明对比。通过这种方式，GRPO在处理困难实例时表现出更好的稳定性和性能。

关键设计：在GRPO中，关键参数包括轨迹的采样数量和优势的计算方式。损失函数设计上，GRPO采用了基于优势的更新策略，确保了训练过程的有效性。

🖼️ 关键图片

fig_0
fig_1

📊 实验亮点

实验结果表明，GRPO在TSP-100上避免了REINFORCE的训练崩溃，性能从成本9.8降至52.1后无法恢复。同时，在相同的梯度更新下，GRPO的解质量与强基线POMO相差不超过2%。

🎯 应用场景

该研究的潜在应用领域包括物流调度、交通路由优化和网络流量管理等。通过提高神经组合优化的训练稳定性，GRPO能够在实际应用中提供更高效的解决方案，具有重要的实际价值和未来影响。

📄 摘要（原文）

Neural combinatorial optimization (NCO) trains autoregressive policies to solve routing problems. The standard training algorithm, REINFORCE with a rollout baseline, requires maintaining and periodically updating a frozen copy of the policy for variance reduction. This baseline introduces a structural vulnerability: on harder instances, a poor baseline produces noisy gradient estimates that can destabilize training. We evaluate Group Relative Policy Optimization (GRPO), an algorithm from large language model alignment that eliminates the baseline entirely by normalizing advantages within groups of sampled trajectories. In a controlled comparison of five RL algorithms on TSP and CVRP benchmarks within the RL4CO framework, we find that: (i) GRPO avoids the training collapse observed with REINFORCE on TSP-100, where performance degrades from cost 9.8 to 52.1 immediately after the warmup phase and does not recover under extended training; (ii) at matched gradient updates, GRPO achieves solution quality within 2% of POMO, a strong AM-based multi-start baseline, while requiring no external baseline; and (iii) P3O, a pairwise preference algorithm also from the alignment literature, is competitive on TSP but shows higher variability on CVRP. These results identify GRPO as a promising baseline-free alternative for NCO, particularly in settings where baseline-dependent training becomes fragile.