mlsanityData to 7 Oct 2026

Baseline-Free Policy Optimization for Neural Combinatorial Optimization

arXiv 2606.10321 ↗First posted 9 Jun 2026cs.LG cs.AI cs.ROcited by 0

On the map: LLM reasoning → Reinforcement learning for reasoning

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Placed in Reinforcement learning for reasoning, one of 17 directions in LLM reasoning. Builds on 19 of its 24 references that are in the map. First posted on arXiv 9 Jun 2026.

Builds on

19 of 24 references.

Closest ancestors · 1

Same direction, newest first

  1. 2017Proximal Policy Optimization Algorithms20 Jul

Other references · 18

  1. 2017Attention Is All You Needcited by 59,932
  2. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 8,851
  3. 2015Pointer Networkscited by 882
  4. 2018Attention, Learn to Solve Routing Problems!cited by 646
  5. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 600
  6. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 341
  7. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 327
  8. 2020Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problemscited by 100
  9. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 70
  10. 2020Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routingcited by 61
  11. 2023Pairwise Proximal Policy Optimization: Harnessing Relative Feedback for LLM Alignmentcited by 57
  12. 2021Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problemcited by 31
6 more
  1. 2024Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspectivecited by 16
  2. 2025Preference Optimization for Combinatorial Optimization Problemscited by 11
  3. 2020Deep R-Learning for Continual Area Sweepingcited by 5
  4. 2022Fields2Cover: An open-source coverage path planning library for unmanned agricultural vehiclescited by 5
  5. 2023Learning Coverage Paths in Unknown Environments with Deep Reinforcement Learningcited by 5
  6. 2019Riverine Coverage with an Autonomous Surface Vehicle over Known Environmentscited by 4

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Constrained Group Relative Policy Optimization
  2. 2026Holder Policy Optimisation
  3. 2025GTPO: Stabilizing Group Relative Policy Optimization via Gradient and Entropy Control
  4. 2025Composing Policy Gradients and Prompt Optimization for Language Model Programs
  5. 2025TIC-GRPO: Provable and Efficient Optimization for Reinforcement Learning from Human Feedback
  6. 2025Learning Without Critics? Revisiting GRPO in Classical Reinforcement Learning Environments
  7. 2026Demystifying Group Relative Policy Optimization: Its Policy Gradient is a U-Statistic
  8. 2026GDPO: Group reward-Decoupled Normalization Policy Optimization for Multi-reward RL Optimization