Entropic Regularization and Reinforcement Learning: Rethinking Neural Architectures for the Traveling Salesman Problem

Introduction

The Traveling Salesman Problem remains the canonical testbed for combinatorial optimization algorithms. Despite decades of research producing exact solvers such as Concorde and LKH that can optimally solve instances with thousands of nodes, these methods rely on branch and bound techniques that scale exponentially. As problem instances grow to tens of thousands of cities, exact approaches fail to provide solutions in reasonable time. This limitation has driven interest in neural network based heuristics that trade optimality guarantees for computational tractability.

Recent deep learning approaches have achieved impressive results by framing TSP as a sequence generation task, using autoregressive architectures like Pointer Networks or Transformer based models to construct tours node by node. However, these methods suffer from a fundamental bottleneck: their autoregressive nature requires serial computation. Generating a tour for n cities demands n sequential forward passes through the network, making inference prohibitively slow for large scale applications.

The paper Combining Reinforcement Learning and Optimal Transport for the Traveling Salesman Problem offers a compelling alternative. By integrating entropic regularized optimal transport as a differentiable layer within a reinforcement learning framework, the authors demonstrate that neural networks can learn to construct TSP solutions without autoregressive decoding. This architectural choice enables parallel computation of assignment constraints and yields inference speeds orders of magnitude faster than sequential methods.

From Sequential Decoding to Parallel Assignment

Traditional neural approaches to TSP treat the problem as analogous to machine translation: they generate a permutation of nodes through an autoregressive decoder that selects one city at a time conditioned on previous choices. While this mirrors the sequential nature of a path, it ignores the underlying geometric structure of the problem. Each decoding step requires a full forward pass through the network, and masking mechanisms must explicitly prevent revisiting cities.

The authors instead leverage entropic regularized optimal transport, specifically the Sinkhorn algorithm, to transform the learning problem from sequence generation to optimal assignment. In this framework, the neural network learns to output a cost matrix representing the affinity between pairs of nodes, or between nodes and positions in the tour. The Sinkhorn layer then converts this cost matrix into a doubly stochastic matrix approximating a permutation through iterative matrix scaling.

The key technical insight involves entropic regularization. Standard optimal transport is a linear programming problem with hard constraints; it is not differentiable and produces sparse solutions. By adding an entropic penalty term weighted by a parameter epsilon, the problem becomes strictly convex and smooth. The resulting Sinkhorn iterations, which alternate between row and column normalization of the exponential of the cost matrix, provide a differentiable approximation to the assignment problem. This allows gradients to flow back from the final tour cost to the neural network parameters during end to end training.

The architectural implications are significant. Rather than generating the tour sequentially, the model predicts all edges or assignments simultaneously, with the Sinkhorn layer enforcing that the solution respects the assignment constraints. This reduces inference from O(n) serial steps to O(1) parallel computation (plus the logarithmic iterations of Sinkhorn), with the matrix operations being highly optimized for GPU acceleration.

End-to-End Learning with Geometric Constraints

The training methodology deserves particular attention. The