Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization

Nathan Grinsztajn, Daniel Furelos-Blanco, Thomas D. Barrett, Bonnet, Clément, Barrett, Thomas D.

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 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 four popular NP-hard problems: traveling salesman, capacitated vehicle routing, 0-1 knapsack, and job-shop scheduling.

Introduction

Combinatorial Optimization (CO) problems, such as routing delivery trucks (CVRP) or scheduling factory jobs (JSSP), are notoriously difficult search tasks. While Reinforcement Learning has shown promise in learning heuristics for these tasks, a single "generalist" policy often struggles to navigate the immense search space of complex problem instances. To compensate, researchers usually rely on "search" at inference time—sampling a single policy hundreds of times or using slow fine-tuning for every new problem.

Conceptual comparison: A single agent (left) tends toward safe, sub-optimal paths, whereas a population (right) can explore diverse, risky paths to find better solutions.

We argue that instead of relying on a single generalist, we should employ a population of "specialists." The core challenge lies in inducing diversity: how do you force a group of agents to become complementary without manually defining what "diversity" looks like? We introduce Poppy, a training procedure that utilizes a "winner-takes-all" objective to naturally evolve a population of specialists.

The Poppy Framework

Poppy utilizes a two-phase training approach to build a high-performing collective:

  1. Phase 1 (Pre-training): A standard encoder-decoder RL model (based on the POMO architecture) is trained to act as a competent generalist. This provides a stable baseline for the population.
  2. Phase 2 (Specialization): The decoder "head" is cloned $K$ times to create a population. During training, every agent attempts the same problem instance. Crucially, we apply a Population-Based Objective: only the agent that achieves the highest reward on a specific instance receives a training signal via backpropagation.

Mathematically, the optimal gradient for a population involves a baseline of the second-best agent’s reward. Essentially, an agent only learns if it can provide a solution better than what the rest of the group can already achieve. This naturally pushes agents into different "niches" of the problem distribution without any handcrafted diversity metrics.

Architectural comparison: Standard single-decoder RL model (left) vs. the Poppy architecture (right) with a shared encoder and multiple specialized decoders.

To maintain computational efficiency, all agents share a single large encoder that processes the problem input, while only the lightweight decoders are specialized. Since decoders typically represent less than 10% of total parameters, a population of 16 agents only increases the total model size by approximately 2x.

Experimental Evaluation

We evaluated Poppy on four classic NP-hard CO problems using standard synthetic distributions:

  • Traveling Salesman Problem (TSP): Finding the shortest route through $n$ cities (tested up to $n=1000$).
  • Capacitated Vehicle Routing Problem (CVRP): Delivering goods with limited vehicle capacity.
  • 0-1 Knapsack Problem (KP): Selecting the most valuable items that fit in a bag.
  • Job-Shop Scheduling Problem (JSSP): Minimizing completion time across multiple machines.

Key Results

Poppy consistently outperformed existing RL baselines across all tasks:

  • State-of-the-Art Accuracy: Poppy-16 achieved an optimality gap of just 0.07% on TSP100, significantly better than previous RL methods. On CVRP100, Poppy-32 halved the optimality gap compared to the POMO baseline.
  • Significant Gains in Knapsack: Poppy-16 reduced the optimality gap by a factor of 12x compared to standard stochastic sampling.
  • Superior Generalization: Poppy showed excellent "zero-shot" generalization. A population trained on 100-city TSPs performed better on 150-city TSPs than many models specifically designed for scaling.

Discussion

Our results highlight the power of emergent specialization. Diversity is not forced; it is a byproduct of the objective. If Agent A is already proficient at "circular" TSP routes, Agent B receives no signal for those instances and is forced to find other types of routes to "win" its share of the training data.

Interestingly, as the population grows, the average performance of a random agent in the group actually declines. However, the population-level performance (the best of the group) improves significantly. The agents become true specialists—less effective on their own but formidable as a collective.

While rolling out 32 agents is computationally heavier than rolling out one, this is easily mitigated by modern parallel hardware. Future work may involve combining Poppy with "active search" (fine-tuning at test time) to determine if specialist populations provide a superior starting point for further 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 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 four popular NP-hard problems: traveling salesman, capacitated vehicle routing, 0-1 knapsack, and job-shop scheduling.
BibTeX
@inproceedings{grinsztajn2023winner,
  author = {Nathan Grinsztajn and Daniel Furelos-Blanco and Thomas D. Barrett and Bonnet, Clément and Barrett, Thomas D.},
  title = {{Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=v6VpqGcGAR},
}
Figure