mlsanityData to 14 Oct 2026

Generative Modeling for Robust Deep Reinforcement Learning on the Traveling Salesman Problem

arXiv 2508.08718 ↗First posted 12 Aug 2025cs.LG cs.AIcited by 0

On the map: Deep reinforcement learning methods → RL for games and combinatorial optimization

Abstract (arXiv)

The Traveling Salesman Problem (TSP) is a classic NP-hard combinatorial optimization task with numerous practical applications. Classic heuristic solvers can attain near-optimal performance for small problem instances, but become computationally intractable for larger problems. Real-world logistics problems such as dynamically re-routing last-mile deliveries demand a solver with fast inference time, which has led researchers to investigate specialized neural network solvers. However, neural networks struggle to generalize beyond the synthetic data they were trained on. In particular, we show that there exist TSP distributions that are realistic in practice, which also consistently lead to poor worst-case performance for existing neural approaches. To address this issue of distribution robustness, we present Combinatorial Optimization with Generative Sampling (COGS), where training data is sampled from a generative TSP model. We show that COGS provides better data coverage and interpolation in the space of TSP training distributions. We also present TSPLib50, a dataset of realistically distributed TSP samples, which tests real-world generalization ability without conflating this issue with instance size. We evaluate our method on various synthetic datasets as well as TSPLib50, and compare to state-of-the-art neural baselines. We demonstrate that COGS improves distribution robustness, with most performance gains coming from worst-case scenarios.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods. Builds on 19 of its 32 references that are in the map. First posted on arXiv 12 Aug 2025.

Builds on

19 of 32 references.

References · 19

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,576
  3. 2017Domain Randomization for Transferring Deep Neural Networks from Simulation to the Real Worldcited by 1,498
  4. 2018Attention, Learn to Solve Routing Problems!cited by 656
  5. 2020Emergent Complexity and Zero-shot Transfer via Unsupervised Environment Designcited by 275
  6. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 269
  7. 2020Reinforcement Learning for Combinatorial Optimization: A Surveycited by 236
  8. 2020Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instancescited by 162
  9. 2019Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learningcited by 78
  10. 2023Unsupervised Learning for Solving the Travelling Salesman Problemcited by 58
  11. 2022Environment Generation for Zero-Shot Compositional Reinforcement Learningcited by 32
  12. 2022Learning to Solve Travelling Salesman Problem with Hardness-adaptive Curriculumcited by 27
7 more
  1. 2022How Good Is Neural Combinatorial Optimization? A Systematic Evaluation on the Traveling Salesman Problemcited by 27
  2. 2022On the Generalization of Neural Combinatorial Optimization Heuristicscited by 24
  3. 2024Learning to Cooperate with Humans using Generative Agentscited by 24
  4. 2022CLUTR: Curriculum Learning via Unsupervised Task Representation Learningcited by 20
  5. 2020Evaluating Curriculum Learning Strategies in Neural Combinatorial Optimizationcited by 19
  6. 2021A Novel Automated Curriculum Strategy to Solve Hard Sokoban Planning Instancescited by 9
  7. 2021Generalization in Deep RL for TSP Problems via Equivariance and Local Searchcited by 9

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Leveraging Structural Constraints for Diffusion-based Neural TSP Solvers
  2. 2025ASAP: Exploiting the Satisficing Generalization Edge in Neural Combinatorial Optimization
  3. 2025Diversity Optimization for Travelling Salesman Problem via Deep Reinforcement Learning
  4. 2025A Unified Deep Reinforcement Learning Approach for Close Enough Traveling Salesman Problem
  5. 2025LocalEscaper: A Weakly-supervised Framework with Regional Reconstruction for Scalable Neural TSP Solvers
  6. 2024IDEQ -- Improving Diffusion Models for the Traveling Salesman Problem (TSP) by Leveraging the Structure of the Solution Space
  7. 2022Travel the Same Path: A Novel TSP Solving Strategy
  8. 2026Offline Decision Transformers for Neural Combinatorial Optimization: Surpassing Heuristics on the Traveling Salesman Problem