Attention + RL for Traveling salesman problems

I got motivated in using RL to solve combinatorial optimization problems. Found this paper combining transformers/attention with RL to solve Travelling salesman problem. Used Solveit to do close reading of the paper and to understand the details of the algorithm to get reproduction going.

It’s interesting how they represented the TSP as a sequential decision making problem and used attention mechanism to encode the whole spatial graph. They also had this neat idea of using greedy rollout as baseline in REINFORCE algoritm.

One limitation was that their approach didn’t really generalize across problem sizes - they had different models trained for n=20, 50, 100 in TSP.

It would be interesting to see how the field has progressed since and how to use RL for similar problems.