Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper evaluates Group Relative Policy Optimization (GRPO), a baseline-free algorithm for neural combinatorial optimization (NCO), which addresses the instability issues of the standard REINFORCE method that relies on a frozen policy baseline. By normalizing advantages within groups of sampled trajectories, GRPO demonstrates resilience against training collapse on challenging instances, specifically on the Traveling Salesman Problem (TSP). The findings reveal that GRPO not only avoids performance degradation seen with REINFORCE but also achieves competitive solution quality compared to established methods without the need for external baselines.
GRPO eliminates the structural vulnerabilities of baseline-dependent training, achieving robust performance in neural combinatorial optimization tasks without the need for a frozen policy.
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.