Population-Based Reinforcement Learning for Combinatorial Optimization Problems
Lists
Only you see this
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...