# A Game-Theoretic Approach for Improving Generalization Ability of TSP Solvers

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 42 references that are in the map.
- First posted on arXiv 28 Oct 2021.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [Learning Improvement Heuristics for Solving Routing Problems](https://mlsanity.com/paper/1912.05784/) (2019)
- [Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances](https://mlsanity.com/paper/2012.10658/) (2020)
- [Open-ended Learning in Symmetric Zero-sum Games](https://mlsanity.com/paper/1901.08106/) (2019)
- [Game-Theoretic Multiagent Reinforcement Learning](https://mlsanity.com/paper/2011.00583/) (2020)
- [Deep Policy Dynamic Programming for Vehicle Routing Problems](https://mlsanity.com/paper/2102.11756/) (2021)
- [Real World Games Look Like Spinning Tops](https://mlsanity.com/paper/2004.09468/) (2020)
- [A Generalized Training Approach for Multiagent Learning](https://mlsanity.com/paper/1909.12823/) (2019)
- [α-Rank: Multi-Agent Evaluation by Evolution](https://mlsanity.com/paper/1903.01373/) (2019)
- [Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games](https://mlsanity.com/paper/2006.08555/) (2020)
- [Modelling Behavioural Diversity for Learning in Open-Ended Games](https://mlsanity.com/paper/2103.07927/) (2021)
- [Diverse Auto-Curriculum is Critical for Successful Real-World Multiagent Learning Systems](https://mlsanity.com/paper/2102.07659/) (2021)
- [On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games](https://mlsanity.com/paper/2109.01795/) (2021)
- [Unifying Behavioral and Response Diversity for Open-ended Learning in Zero-sum Games](https://mlsanity.com/paper/2106.04958/) (2021)
- [Iterative Empirical Game Solving via Single Policy Best Response](https://mlsanity.com/paper/2106.01901/) (2021)
- [Measuring the Non-Transitivity in Chess](https://mlsanity.com/paper/2110.11737/) (2021)
- [Learning to Play against Any Mixture of Opponents](https://mlsanity.com/paper/2009.14180/) (2020)

## Built on by (most cited first, 14 of 14)

- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time](https://mlsanity.com/paper/2312.08224/) (2023)
- [Towards Omni-generalizable Neural Methods for Vehicle Routing Problems](https://mlsanity.com/paper/2305.19587/) (2023)
- [Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation](https://mlsanity.com/paper/2210.07686/) (2022)
- [ASP: Learn a Universal Neural Solver!](https://mlsanity.com/paper/2303.00466/) (2023)
- [CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention](https://mlsanity.com/paper/2412.00346/) (2024)
- [Policy Space Response Oracles: A Survey](https://mlsanity.com/paper/2403.02227/) (2024)
- [Efficient Training of Multi-task Neural Solver for Combinatorial Optimization](https://mlsanity.com/paper/2305.06361/) (2023)
- [General Method for Solving Four Types of SAT Problems](https://mlsanity.com/paper/2312.16423/) (2023)
- [Beyond the Heatmap: A Rigorous Evaluation of Component Impact in MCTS-Based TSP Solvers](https://mlsanity.com/paper/2411.09238/) (2024)
- [Game-Theoretic Co-Evolution for LLM-Based Heuristic Discovery](https://mlsanity.com/paper/2601.22896/) (2026)
- [NeuroPrim: An Attention-based Model for Solving NP-hard Spanning Tree Problems](https://mlsanity.com/paper/2210.12453/) (2022)
- [LRM-1B: Towards Large Routing Model](https://mlsanity.com/paper/2507.03300/) (2025)

## Abstract (arXiv)

In this paper, we introduce a two-player zero-sum framework between a trainable Solver and a Data Generator to improve the generalization ability of deep learning-based solvers for Traveling Salesman Problem (TSP). Grounded in textslPolicy Space Response Oracle (PSRO) methods, our two-player framework outputs a population of best-responding Solvers, over which we can mix and output a combined model that achieves the least exploitability against the Generator, and thereby the most generalizable performance on different TSP tasks. We conduct experiments on a variety of TSP instances with different types and sizes. Results suggest that our Solvers achieve the state-of-the-art performance even on tasks the Solver never meets, whilst the performance of other deep learning-based Solvers drops sharply due to over-fitting. To demonstrate the principle of our framework, we study the learning outcome of the proposed two-player game and demonstrate that the exploitability of the Solver population decreases during training, and it eventually approximates the Nash equilibrium along with the Generator.