Reinforcement learning is a elegant alternative in the absence of groundtruth solutions, as is often the case for understudied combinatorial problems.
Models can be trained by minimizing problem-specific cost functions (the tour length in the case of TSP) via policy gradient algorithms [1]}, [2]} or Q-Learning [3]}.
We focus on policy gradient methods due to their simplicity, and define the loss for an instance \(s\)  parameterized by the model \(\theta \)  as \(\mathcal {L}(\theta | s) = \mathbb {E}_{p_{\theta }(\pi | s)}\left[L(\pi )\right]\) , the expectation of the tour length \(L(\pi )\) , where \(p_{\theta }(\pi | s)\)  is the probability distribution from which we sample to obtain the tour \(\pi |s\) .
We use the REINFORCE gradient estimator  [4]} to minimize \(\mathcal {L}\) :
\(\nabla \mathcal {L}(\theta | s) = \mathbb {E}_{p_{\theta }(\pi | s)}\left[\left(L(\pi ) - b(s)\right) \nabla \log p_{\theta }(\pi | s)\right],\) 
