A Survey on Reinforcement Learning for Combinatorial Optimization

This paper gives a detailed review of reinforcement learning in combinatorial optimization, introduces the history of combinatorial optimization starting in the 1960s, and compares with the reinforcement learning algorithms in recent years. We explicitly look at a famous combinatorial problem known as the Traveling Salesman Problem. We compare the approach of the modern reinforcement learning algorithms on Traveling Salesman Problem with the approach published in the 1970s. Then, we discuss the similarities between these algorithms and how the approach of reinforcement learning changes due to the evolution of machine learning techniques and computing power.