Population-Based Reinforcement Learning for Combinatorial Optimization Problems

Nathan Grinsztajn, Daniel Furelos-Blanco, Thomas D BarrettICLR 2023 · OpenReview

Abstract

Applying reinforcement learning to combinatorial optimization problems is attractive as it obviates 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 are often augmented with 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 agents, 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 whole population. We show that Poppy leads to a set of complementary heuristics, and obtain state-of-the-art results on three popular NP-hard problems: the traveling salesman (TSP), the capacitated vehicle routing (CVRP), and 0-1 knapsack (KP). On TSP specifically, Poppy divides by 5 the optimality gap while reducing the inference time by more than 10 compared to previous state-of-the-art reinforcement learning approaches.
BibTeX
@inproceedings{grinsztajn2023population,
  author = {Nathan Grinsztajn and Daniel Furelos-Blanco and Thomas D Barrett},
  title = {{Population-Based Reinforcement Learning for Combinatorial Optimization Problems}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=JRFSLFyYAII},
}

Loading related content...

Figure