A Game-Theoretic Approach for Improving Generalization Ability of TSP Solvers
arXiv:2110.15105
Abstract
In this paper, we introduce a two-player zero-sum framework between a trainable \emph{Solver} and a \emph{Data Generator} to improve the generalization ability of deep learning-based solvers for Traveling Salesman Problem (TSP). Grounded in \textsl{Policy 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.
ICLR2022 Gamification and Multiagent Solutions Workshop Spotlight Presentation
References in corpus (9)
- Learning Combinatorial Optimization Algorithms over Graphs
- Attention, Learn to Solve Routing Problems!
- Game-Theoretic Multiagent Reinforcement Learning
- Open-ended Learning in Symmetric Zero-sum Games
- Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances
- A Generalized Training Approach for Multiagent Learning
- Real World Games Look Like Spinning Tops
- Unifying Behavioral and Response Diversity for Open-ended Learning in Zero-sum Games
- Iterative Empirical Game Solving via Single Policy Best Response