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

arXiv: https://arxiv.org/abs/2508.08718 · HTML: https://mlsanity.com/paper/2508.08718/

## 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.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 19 of 19)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Domain Randomization for Transferring Deep Neural Networks from Simulation to the Real World](https://mlsanity.com/paper/1703.06907/) (2017)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Emergent Complexity and Zero-shot Transfer via Unsupervised Environment Design](https://mlsanity.com/paper/2012.02096/) (2020)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances](https://mlsanity.com/paper/2012.10658/) (2020)
- [Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1911.04936/) (2019)
- [Unsupervised Learning for Solving the Travelling Salesman Problem](https://mlsanity.com/paper/2303.10538/) (2023)
- [Environment Generation for Zero-Shot Compositional Reinforcement Learning](https://mlsanity.com/paper/2201.08896/) (2022)
- [Learning to Solve Travelling Salesman Problem with Hardness-adaptive Curriculum](https://mlsanity.com/paper/2204.03236/) (2022)
- [How Good Is Neural Combinatorial Optimization? A Systematic Evaluation on the Traveling Salesman Problem](https://mlsanity.com/paper/2209.10913/) (2022)
- [On the Generalization of Neural Combinatorial Optimization Heuristics](https://mlsanity.com/paper/2206.00787/) (2022)
- [Learning to Cooperate with Humans using Generative Agents](https://mlsanity.com/paper/2411.13934/) (2024)
- [CLUTR: Curriculum Learning via Unsupervised Task Representation Learning](https://mlsanity.com/paper/2210.10243/) (2022)
- [Evaluating Curriculum Learning Strategies in Neural Combinatorial Optimization](https://mlsanity.com/paper/2011.06188/) (2020)
- [A Novel Automated Curriculum Strategy to Solve Hard Sokoban Planning Instances](https://mlsanity.com/paper/2110.00898/) (2021)
- [Generalization in Deep RL for TSP Problems via Equivariance and Local Search](https://mlsanity.com/paper/2110.03595/) (2021)

## 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.