Generalization in Deep RL for TSP Problems via Equivariance and Local Search
This work addresses the scalability issue in deep RL for combinatorial optimization, which is incremental but improves generalization for TSP applications.
The paper tackles the poor generalization of deep reinforcement learning (RL) to larger traveling salesman problem (TSP) instances by proposing a novel approach that uses equivariance and local search to smooth the value landscape, achieving competitive performance against state-of-the-art methods on random and realistic TSP problems.
Deep reinforcement learning (RL) has proved to be a competitive heuristic for solving small-sized instances of traveling salesman problems (TSP), but its performance on larger-sized instances is insufficient. Since training on large instances is impractical, we design a novel deep RL approach with a focus on generalizability. Our proposition consisting of a simple deep learning architecture that learns with novel RL training techniques, exploits two main ideas. First, we exploit equivariance to facilitate training. Second, we interleave efficient local search heuristics with the usual RL training to smooth the value landscape. In order to validate the whole approach, we empirically evaluate our proposition on random and realistic TSP problems against relevant state-of-the-art deep RL methods. Moreover, we present an ablation study to understand the contribution of each of its component