Baseline-Free Policy Optimization for Neural Combinatorial Optimization

• URL: http://arxiv.org/abs/2606.10321v1
• Date: Tue, 09 Jun 2026 02:18:30 GMT
• Title: Baseline-Free Policy Optimization for Neural Combinatorial Optimization
• Abstract summary: Group Relative Policy Optimization eliminates the baseline entirely by normalizing advantages within groups of sampled trajectories.<n> GRPO achieves solution quality within 2% of POMO, a strong AM-based multi-start baseline, while requiring no external baseline.<n>These results identify GRPO as a promising baseline-free alternative for NCO, particularly in settings where baseline-dependent training becomes fragile.
• Score: 1.2891210250935148
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Accelerating Reinforcement Learning via MPC Solver-Gradient Guidance for Weights-varying MPC [17.152519147246842]
  We propose a solver-sensitivity augmentation for RL-based online MPC cost-weight adaptation.<n>We instantiate SG-RL in Proximal Policy Optimization (PPO) with four modular algorithms that inject solver-gradient guidance into actor-update scaling, policy loss, advantage estimation, and value-function learning.<n>On two full-scale autonomous racing platforms with intentional model mismatch, SG-RL reaches PPO's best closed-loop return with up to 70.6% fewer samples, outperforms GB-PL baselines by at least 54% in closed-loop return, and generalizes zero-shot to unseen environments.
  arXiv  Detail & Related papers  (2026-09-01T10:55:18Z)
• SSPO: Structure-Aware Similarity-Weighted Preference Optimization for Neural Combinatorial Optimization [7.503926194234302]
  Preference-optimization methods anchor on the single best solution and discard fine-grained quality and structural signal from all other peers.<n>We propose SSPO (Structure-Aware Similarity-Weighted Preference Optimization), which scores all $B$ sampled solutions jointly through a dissimilarity-weighted leave-one-out baseline.
  arXiv  Detail & Related papers  (2026-08-12T16:04:54Z)
• Ratio-Variance Regularized Policy Optimization [64.95520246570446]
  We show that explicitly constraining the policy ratio variance provides a principled local approximation to trust-region constraints.<n>We introduce $bf R2bf VPO$ (Ratio-Variance Regularized Policy Optimization), which implements this constraint via a primal-dual optimization framework.
  arXiv  Detail & Related papers  (2026-05-26T09:53:42Z)
• Advantage Collapse in Group Relative Policy Optimization: Diagnosis and Mitigation [13.272542054938258]
  We introduce the Advantage Collapse Rate (ACR), the first metric quantifying the proportion of training batches with ineffective gradients.<n>We then propose Adaptive Virtual Sample Policy Optimization (AVSPO), a lightweight extension of GRPO that injects virtual reward samples.<n>AVSPO reduces advantage collapse by 58-63% relative to GRPO and yields consistent accuracy gains of 4-6 percentage points across all model scales.
  arXiv  Detail & Related papers  (2026-05-20T12:57:37Z)
• Too Correct to Learn: Reinforcement Learning on Saturated Reasoning Data [55.84428098924793]
  We propose Constrained Uniform Top-K Sampling (CUTS), a parameter-free decoding strategy enforcing structure-preserving exploration.<n>We integrate this into Mixed-CUTS, a training framework synergizing exploitative and exploratory rollouts to amplify intra-group advantage variance.<n> Notably, Mixed-CUTS improves Pass@1 accuracy on the challenging AIME25 benchmark by up to 15.1% over standard GRPO.
  arXiv  Detail & Related papers  (2026-04-20T16:43:28Z)
• Unbiased Dynamic Pruning for Efficient Group-Based Policy Optimization [60.87651283510059]
  Group Relative Policy Optimization (GRPO) effectively scales LLM reasoning but incurs prohibitive computational costs.<n>We propose Dynamic Pruning Policy Optimization (DPPO), a framework that enables dynamic pruning while preserving unbiased gradient estimation.<n>To mitigate the data sparsity induced by pruning, we introduce Dense Prompt Packing, a window-based greedy strategy.
  arXiv  Detail & Related papers  (2026-03-04T14:48:53Z)
• Rethinking the Trust Region in LLM Reinforcement Learning [72.25890308541334]
  Proximal Policy Optimization (PPO) serves as the de facto standard algorithm for Large Language Models (LLMs)<n>We propose Divergence Proximal Policy Optimization (DPPO), which substitutes clipping with a more principled constraint.<n>DPPO achieves superior training and efficiency compared to existing methods, offering a more robust foundation for RL-based fine-tuning.
  arXiv  Detail & Related papers  (2026-02-04T18:59:04Z)
• Ratio-Variance Regularized Policy Optimization for Efficient LLM Fine-tuning [48.34492357368989]
  We propose a primal-dual framework that supports stable on-policy learning and enables principled off-policy data reuse.<n>$R2VPO$ achieves superior performance with average relative gains of up to 17% over strong clipping-based baselines.
  arXiv  Detail & Related papers  (2026-01-06T14:01:42Z)
• BAPO: Stabilizing Off-Policy Reinforcement Learning for LLMs via Balanced Policy Optimization with Adaptive Clipping [69.74252624161652]
  We propose BAlanced Policy Optimization with Adaptive Clipping (BAPO)<n>BAPO dynamically adjusts clipping bounds to adaptively re-balance positive and negative contributions, preserve entropy, and stabilize RL optimization.<n>On AIME 2024 and AIME 2025 benchmarks, our 7B BAPO model surpasses open-source counterparts such as SkyWork-OR1-7B.
  arXiv  Detail & Related papers  (2025-10-21T12:55:04Z)
• Single-stream Policy Optimization [21.214853668053234]
  We introduce Single-stream Policy Optimization (SPO)<n>SPO replaces per-group baselines with a persistent, KL-adaptive value tracker and normalizes advantages globally across the batch.<n>Being group-free, SPO enables higher throughput and scales effectively in long-horizon or tool-integrated settings.
  arXiv  Detail & Related papers  (2025-09-16T16:39:11Z)
• On-Policy RL with Optimal Reward Baseline [109.47676554514193]
  On-Policy RL with Optimal reward baseline (OPO) is a novel and simplified reinforcement learning algorithm.<n>OPO emphasizes the importance of exact on-policy training, which empirically stabilizes the training process and enhances exploration.<n>Results demonstrate OPO's superior performance and training stability without additional models or regularization terms.
  arXiv  Detail & Related papers  (2025-05-29T15:58:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.