Population-Based Reinforcement Learning for Combinatorial Optimization

Nathan Grinsztajn, Daniel Furelos-Blanco, Thomas D. Barrett

Abstract

Applying reinforcement learning (RL) to combinatorial optimization (CO) problems is attractive as it removes the need for expert knowledge or pre-solved instances. However, it is unrealistic to expect an agent to solve these (often NP-hard) problems in a single shot at inference due to their inherent complexity. Leading approaches often implement additional search strategies, from stochastic sampling and beam-search to explicit fine-tuning. In this paper, we argue for the benefits of learning a population of complementary policies, which can be simultaneously rolled out at inference. To this end, we introduce Poppy, a simple theoretically grounded training procedure for populations. Instead of relying on a predefined or hand-crafted notion of diversity, Poppy induces an unsupervised specialization targeted solely at maximizing the performance of the population. We show that Poppy produces a set of complementary policies and obtains state-of-the-art RL results on three popular NP-hard problems: the traveling salesman (TSP), the capacitated vehicle routing (CVRP), and 0-1 knapsack (KP) problems. On TSP specifically, Poppy outperforms the previous state-of-the-art, dividing the optimality gap by 5 while reducing the inference time by more than an order of magnitude.

Introduction

Combinatorial Optimization (CO) involves finding the best solution from a finite but astronomically large set of possibilities—for instance, determining the shortest route for a delivery truck visiting 100 houses. Because these problems are typically NP-hard, finding the absolute best answer is computationally exhausting.

While Reinforcement Learning has shown promise in learning heuristics to solve these problems, a single neural network (a "policy") often struggles to handle the entire diversity of possible problem instances. It frequently becomes a "jack of all trades, master of none," settling for a safe but suboptimal average solution to avoid high-risk failures.

Specialization vs. Single Policy: A single agent (left) chooses a safe path to avoid risk, while a population (right) can explore risky, high-reward paths by specializing.

To compensate, researchers usually employ expensive search techniques like beam search or massive random sampling at inference time. Poppy proposes a different paradigm: training a population of agents that specialize in different types of problem instances, allowing for a more robust and high-performing collective heuristic.

Methodology

The authors introduce Poppy, a two-phase training procedure designed to foster emergent specialization:

  1. Phase 1 (Pre-training): A single standard RL agent, utilizing an encoder-decoder architecture, is trained until convergence.
  2. Phase 2 (Specialization): The "decoder" part of the network is cloned $K$ times to create a population. Crucially, the "encoder"—which processes the raw problem data—is shared across all agents to minimize memory and computational overhead.
Architecture of Poppy: A shared encoder processes input nodes into embeddings, which are then fed into multiple specialized decoder heads.

The core innovation is the Population-Based Objective. During training, every agent in the population attempts to solve the same problem instance. However, only the agent that performs the best receives a training signal—a "Winner Takes It All" approach. Mathematically, the policy gradient uses the performance of the "second-best" agent as a baseline for the "winner." This forces agents to focus on instances where they can uniquely contribute to the team's overall score, leading to unsupervised specialization without handcrafted diversity metrics.

Experimental Evaluation

Poppy was evaluated on four classic NP-hard combinatorial problems using standard synthetic benchmarks:

  • Traveling Salesman Problem (TSP): Finding the shortest path through $n$ cities.
  • Capacitated Vehicle Routing (CVRP): TSP with added vehicle load limits and a central depot.
  • 0-1 Knapsack (KP): Maximizing item value within a weight limit.
  • Job-Shop Scheduling (JSSP): Minimizing total time for tasks assigned to machines.

Key Results

Poppy consistently outperformed other RL-based approaches across all problem types:

  • TSP100: Poppy-16 achieved an optimality gap of just 0.07%, significantly outperforming the previous best RL method (POMO) which had a 0.41% gap.
  • CVRP100: Poppy-32 halved the optimality gap compared to POMO (1.06% vs 2.00%) while maintaining the same inference time.
  • Generalization: Poppy showed stronger robustness to distribution shifts. When trained on 100 cities but tested on 150, Poppy maintained a much smaller gap than its competitors.
  • Speed: Poppy reaches high performance in just a few minutes of inference, narrowing the gap between fast neural heuristics and slow exact solvers.

Discussion and Conclusion

A fascinating finding of this work is the "individual sacrifice" for collective gain: as the population grows, the average performance of a single random agent actually decreases. However, the population-level performance (the best of the bunch) improves significantly. The agents "give up" on problems they aren't good at to become masters of their specific niches.

While Poppy is a construction-based method, it could be combined with improvement methods (like local search) or active search (fine-tuning at test time) to push results even closer to absolute optimality. Future work will also address scaling limits and training stability to further enhance the robustness of population-based RL for combinatorial optimization.

Summary updated

Abstract

Applying reinforcement learning (RL) to combinatorial optimization problems is attractive as it removes the need for expert knowledge or pre-solved instances. However, it is unrealistic to expect an agent to solve these (often NP-)hard problems in a single shot at inference due to their inherent complexity. Thus, leading approaches often implement additional search strategies, from stochastic sampling and beam-search to explicit fine-tuning. In this paper, we argue for the benefits of learning a population of complementary policies, which can be simultaneously rolled out at inference. To this end, we introduce Poppy, a simple theoretically grounded training procedure for populations. Instead of relying on a predefined or hand-crafted notion of diversity, Poppy induces an unsupervised specialization targeted solely at maximizing the performance of the population. We show that Poppy produces a set of complementary policies, and obtains state-of-the-art RL results on three popular NP-hard problems: the traveling salesman (TSP), the capacitated vehicle routing (CVRP), and 0-1 knapsack (KP) problems. On TSP specifically, Poppy outperforms the previous state-of-the-art, dividing the optimality gap by 5 while reducing the inference time by more than an order of magnitude.
BibTeX
@inproceedings{grinsztajn2023population,
  author = {Nathan Grinsztajn and Daniel Furelos-Blanco and Thomas D. Barrett},
  title = {{Population-Based Reinforcement Learning for Combinatorial Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=v6VpqGcGAR},
}
Figure