mlsanityData to 7 Oct 2026

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

arXiv 2210.03475 ↗First posted 7 Oct 2022cs.AI cs.LGcited by 57

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 57 papers in the map (data through 7 Oct 2026). Builds on 39 of its 57 references that are in the map. First posted on arXiv 7 Oct 2022.

Builds on

39 of 57 references.

References · 39

  1. 2017Attention Is All You Needcited by 59,932
  2. 2020Language Models are Few-Shot Learnerscited by 32,199
  3. 2016WaveNet: A Generative Model for Raw Audiocited by 1,710
  4. 2015Pointer Networkscited by 882
  5. 2018Diversity is All You Need: Learning Skills without a Reward Functioncited by 734
  6. 2018Attention, Learn to Solve Routing Problems!cited by 646
  7. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  8. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  9. 2015Illuminating search spaces by mapping elitescited by 406
  10. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 341
  11. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 327
  12. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 265
27 more
  1. 2020Reinforcement Learning for Combinatorial Optimization: A Surveycited by 235
  2. 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 183
  3. 2019Skew-Fit: State-Covering Self-Supervised Reinforcement Learningcited by 171
  4. 2019Learning Improvement Heuristics for Solving Routing Problemscited by 162
  5. 2020Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instancescited by 161
  6. 2020Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learningcited by 139
  7. 2018Meta-Reinforcement Learning of Structured Exploration Strategiescited by 128
  8. 2020Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhoodcited by 122
  9. 2022Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimizationcited by 118
  10. 2019Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problemcited by 117
  11. 2020Effective Diversity in Population Based Reinforcement Learningcited by 116
  12. 2017Quality and Diversity Optimization: A Unifying Modular Frameworkcited by 111
  13. 2020Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learningcited by 100
  14. 2020Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problemscited by 100
  15. 2021Efficient Active Search for Combinatorial Optimization Problemscited by 99
  16. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  17. 2021Learning Collaborative Policies to Solve NP-hard Routing Problemscited by 86
  18. 2022Simulation-guided Beam Search for Neural Combinatorial Optimizationcited by 84
  19. 2018Evolution-Guided Policy Gradient in Reinforcement Learningcited by 78
  20. 2018Diversity-Driven Exploration Strategy for Deep Reinforcement Learningcited by 65
  21. 2019Dynamical Distance Learning for Semi-Supervised and Unsupervised Skill Discoverycited by 65
  22. 2018CEM-RL: Combining evolutionary and gradient-based methods for policy searchcited by 53
  23. 2020Diversity Policy Gradient for Sample Efficient Quality-Diversity Optimizationcited by 53
  24. 2019Collaborative Evolutionary Reinforcement Learningcited by 36
  25. 2020Population-Guided Parallel Policy Search for Reinforcement Learningcited by 20
  26. 2019Attraction-Repulsion Actor-Critic for Continuous Control Reinforcement Learningcited by 5
  27. 2022Fast Population-Based Reinforcement Learning on a Single Machinecited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 21; 2025: 17; 2026: 19.

57 papers.

Sort:

By area:

  1. 2024MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Expertscited by 69
  2. 2024RouteFinder: Towards Foundation Models for Vehicle Routing Problemscited by 54
  3. 2024Ant Colony Sampling with GFlowNets for Combinatorial Optimizationcited by 53
  4. 2025Rethinking Light Decoder-based Solvers for Vehicle Routing Problemscited by 36
  5. 2024PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimizationcited by 35
  6. 2024Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvementcited by 32
  7. 2024Learning to Handle Complex Constraints for Vehicle Routing Problemscited by 29
  8. 2024Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectivescited by 23
  9. 2025Neural Deconstruction Search for Vehicle Routing Problemscited by 15
  10. 2025BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimizationcited by 14
  11. 2025Preference Optimization for Combinatorial Optimization Problemscited by 11
  12. 2024Collaboration! Towards Robust Neural Methods for Routing Problemscited by 9
38 more
  1. 2024PARCO: Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimizationcited by 7
  2. 2025Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDPcited by 7
  3. 2024Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and Morecited by 6
  4. 2025Machine learning interatomic potential can infer electrical responsecited by 6
  5. 2025VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problemscited by 6
  6. 2024Moco: A Learnable Meta Optimizer for Combinatorial Optimizationcited by 5
  7. 2024Leader Reward for POMO-Based Neural Combinatorial Optimizationcited by 5
  8. 2024Neural Solver Selection for Combinatorial Optimizationcited by 5
  9. 2025Reinforcement learning with combinatorial actions for coupled restless banditscited by 5
  10. 2024A Unified Framework for Combinatorial Optimization Based on Graph Neural Networkscited by 4
  11. 2024Memory-Enhanced Neural Solvers for Routing Problemscited by 4
  12. 2024Learning Multiple Initial Solutions to Optimization Problemscited by 4
  13. 2026Expected Return Causes Outcome-Level Mode Collapse in Reinforcement Learning and How to Fix It with Inverse Probability Scalingcited by 4
  14. 2024Continuous Parallel Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problemscited by 3
  15. 2024MARCO: A Memory-Augmented Reinforcement Framework for Combinatorial Optimizationcited by 3
  16. 2024Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptationcited by 2
  17. 2025TuneNSearch: a hybrid transfer learning and local search approach for solving vehicle routing problemscited by 2
  18. 2025UniCO: Towards a Unified Model for Combinatorial Optimization Problemscited by 2
  19. 2025Breaking the Performance Ceiling in Reinforcement Learning requires Inference Strategiescited by 2
  20. 2026Towards Efficient Constraint Handling in Neural Solvers for Routing Problemscited by 2
  21. 2026Chain-of-Context Learning: Dynamic Constraint Understanding for Multi-Task VRPscited by 2
  22. 2025USPR: Learning a Unified Solver for Profiled Routingcited by 1
  23. 2025VAGPO: Vision-augmented Asymmetric Group Preference Optimization for Graph Routing Problemscited by 1
  24. 2025Empowering Targeted Neighborhood Search via Hyper Tour for Large-Scale TSPcited by 1
  25. 2026Rethinking Constraint Awareness for Efficient State Embedding of Neural Routing Solvercited by 1
  26. 2026Leveraging Structural Constraints for Diffusion-based Neural TSP Solverscited by 1
  27. 2024Model-based reinforcement learning for protein backbone designcited by 0
  28. 2024Simultaneous Training of First- and Second-Order Optimizers in Population-Based Reinforcement Learningcited by 0
  29. 2025Latent Guided Sampling for Combinatorial Optimizationcited by 0
  30. 2025Synergizing Reinforcement Learning and Genetic Algorithms for Neural Combinatorial Optimizationcited by 0
  31. 2025Multi-Action Self-Improvement for Neural Combinatorial Optimizationcited by 0
  32. 2026Enabling Population-Based Architectures for Neural Combinatorial Optimizationcited by 0
  33. 2026Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Schedulingcited by 0
  34. 2026Enhancing Cross-Problem Vehicle Routing via Federated Learningcited by 0
  35. 2026Learning to Solve the Quadratic Assignment Problem with Warm-Started MCMC Finetuningcited by 0
  36. 2026FiLMMeD: Feature-wise Linear Modulation for Cross-Problem Multi-Depot Vehicle Routingcited by 0
  37. 2026LINC: Decoupling Local Consequence Scoring from Hidden Matching in Constructive Neural Routingcited by 0
  38. 2026Rethinking Positional Encoding for Neural Vehicle Routingcited by 0

50 most cited of 57 All 57 (JSON)