# A Survey on Reinforcement Learning for Combinatorial Optimization

arXiv: https://arxiv.org/abs/2008.12248 · HTML: https://mlsanity.com/paper/2008.12248/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Aug 2020.

## Built on by (most cited first, 10 of 10)

- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2106.04927/) (2021)
- [ToupleGDD: A Fine-Designed Solution of Influence Maximization by Deep Reinforcement Learning](https://mlsanity.com/paper/2210.07500/) (2022)
- [Reinforcement Learning-assisted Evolutionary Algorithm: A Survey and Research Opportunities](https://mlsanity.com/paper/2308.13420/) (2023)
- [PARCO: Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimization](https://mlsanity.com/paper/2409.03811/) (2024)
- [Optimizing Tensor Network Contraction Using Reinforcement Learning](https://mlsanity.com/paper/2204.09052/) (2022)
- [Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods](https://mlsanity.com/paper/2310.05309/) (2023)
- [RedAHD: Reduction-Based End-to-End Automatic Heuristic Design with Large Language Models](https://mlsanity.com/paper/2505.20242/) (2025)
- [Hybridising Reinforcement Learning and Heuristics for Hierarchical Directed Arc Routing Problems](https://mlsanity.com/paper/2501.00852/) (2025)

## Abstract (arXiv)

This paper gives a detailed review of reinforcement learning (RL) in combinatorial optimization, introduces the history of combinatorial optimization starting in the 1950s, and compares it with the RL algorithms of recent years. This paper explicitly looks at a famous combinatorial problem-traveling salesperson problem (TSP). It compares the approach of modern RL algorithms for the TSP with an approach published in the 1970s. By comparing the similarities and variances between these methodologies, the paper demonstrates how RL algorithms are optimized due to the evolution of machine learning techniques and computing power. The paper then briefly introduces the deep learning approach to the TSP named deep RL, which is an extension of the traditional mathematical framework. In deep RL, attention and feature encoding mechanisms are introduced to generate near-optimal solutions. The survey shows that integrating the deep learning mechanism, such as attention with RL, can effectively approximate the TSP. The paper also argues that deep learning could be a generic approach that can be integrated with any traditional RL algorithm to enhance the outcomes of the TSP.