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

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

TL;DR

Poppy is a novel reinforcement learning (RL) training procedure that creates a population of specialized agents to solve NP-hard combinatorial optimization problems. By optimizing for the performance of the best agent in the population—a "winner-takes-all" approach—the agents naturally develop complementary strategies, achieving state-of-the-art results on benchmarks like the Traveling Salesman Problem without requiring handcrafted diversity metrics.

What Problem Does This Paper Address?

Combinatorial Optimization (CO) involves finding the best solution from a finite but often astronomically large set of possibilities. Classic examples include the Traveling Salesman Problem (TSP) and Job-Shop Scheduling (JSSP). While RL has shown promise in learning heuristics for these tasks, a single agent often struggles to find the global optimum in a "single shot" because the search space is too complex.

Existing methods try to overcome this by using stochastic sampling (running the same policy multiple times with different random seeds) or beam search. However, these methods are limited: sampling from a single policy tends to explore solutions that are very similar to one another. The authors argue that instead of one "jack-of-all-trades" agent, we should train a population of specialists that can be rolled out simultaneously to cover different parts of the solution space.

Methods

The authors introduce Poppy, a two-phase training procedure:

  1. Phase 1 (Pre-training): A standard RL agent (using an encoder-decoder architecture) is trained to solve the problem distribution.
  2. Phase 2 (Specialization): The encoder is frozen and shared across the population, while the decoder is cloned $K$ times to create $K$ distinct agents. The population is then trained using a "winner-takes-all" objective: for any given problem instance, only the agent that achieves the highest reward receives a gradient update.
Figure 2: Phases of the training process with a model using static instance embeddings. Left (Phase 1): the encoder and the decoder are trained from scratch. Right (Phase 2): the decoder is cloned K times, and the whole model is trained using the Poppy training objective (i.e. the gradient is only propagated through the decoder that yields the highest reward).

Crucially, Poppy does not use explicit diversity penalties (like KL-divergence). Instead, diversity emerges as a byproduct of maximizing the population-level objective: $J_{pop} = \mathbb{E}[\max(R_1, \dots, R_K)]$. The authors derive a specific policy gradient for this objective, showing that the reward of the second-best agent serves as a natural baseline for the winner's update, focusing the training signal on the winner's unique contribution to the group.

Datasets

The method was evaluated on four classic NP-hard problems:

  • Traveling Salesman Problem (TSP): Finding the shortest route through $n$ cities.
  • Capacitated Vehicle Routing Problem (CVRP): Routing vehicles with limited capacity to fulfill customer demands.
  • 0-1 Knapsack Problem (KP): Selecting items to maximize value without exceeding weight limits.
  • Job-Shop Scheduling Problem (JSSP): Scheduling jobs on machines to minimize total time.

Training was performed on instances of size $n=100$, and testing included larger instances ($n=125, 150$) to evaluate zero-shot generalization.

Key Insights and Ideas

  • Emergent Specialization: The "winner-takes-all" objective is a powerful unsupervised tool. Because an agent only learns when it is the best, it has no incentive to improve on problems where another agent is already superior. This naturally pushes agents into different "niches" of the problem distribution.
  • The Specialization Trade-off: As the population grows, the average performance of a single random agent actually gets worse, but the collective performance of the population significantly improves. This confirms that agents are becoming highly specialized rather than generally better.
  • Toy Model Intuition: The authors use a "maze" example to show that for a limited-capacity agent, the safest bet is a mediocre reward. However, a population can afford to take risks in opposite directions, ensuring that at least one agent always finds the maximum reward.
Figure 1: In this environment, the upward path always leads to a medium reward, while the left and right paths are intricate such that either one may lead to a low reward or high reward with equal probability. Left: An agent trained to maximize its expected reward converges to taking the safe upward road since acting optimally is too computationally intensive, as it requires solving the maze. Right: A 2-agent population can always take the left and right paths and thus get the largest reward.

Key Results

Poppy consistently outperformed existing RL baselines across all four problem types:

  • TSP100: Poppy with 16 agents achieved an optimality gap of 0.07%, compared to 0.41% for the strong POMO baseline.
  • CVRP100: Poppy 32 reached a 1.06% gap, nearly halving the gap of standard POMO (2.00%).
  • Generalization: Poppy showed superior robustness to distributional shifts, maintaining lower optimality gaps than baselines when tested on larger problem sizes ($n=150$) than those seen during training.
  • Efficiency: Because the heavy encoder is shared, a population of 16 agents only requires about 2.1x the parameters of a single agent, making it computationally feasible.

Limitations and Future Work

  • Population Scaling: The study only went up to 32 agents. It is unclear if much larger populations would eventually lead to a "performance collapse" where new agents fail to find useful niches.
  • Training Cost: While inference is efficient, training a population is more computationally expensive than training a single agent.
  • Active Search Integration: The authors suggest that combining Poppy with "active search" (fine-tuning agents at inference time) could push performance even closer to exact solvers.
  • Broader Applications: The "winner-takes-all" philosophy could potentially be applied to other generative tasks like code generation or protein design, where multiple diverse attempts are often allowed.

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 Shikha Surana and Clément Bonnet and Thomas D. Barrett},
  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