# Exploratory Combinatorial Optimization with Reinforcement Learning

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

## Key facts

- Cited by 82 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Sep 2019.

## Built on by (most cited first, 30 of 82)

- [Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization](https://mlsanity.com/paper/2310.07985/) (2023)
- [Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization](https://mlsanity.com/paper/2205.13209/) (2022)
- [Simulation-guided Beam Search for Neural Combinatorial Optimization](https://mlsanity.com/paper/2207.06190/) (2022)
- [RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark](https://mlsanity.com/paper/2306.17100/) (2023)
- [A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization](https://mlsanity.com/paper/2406.01661/) (2024)
- [A Survey for Solving Mixed Integer Programming via Machine Learning](https://mlsanity.com/paper/2203.02878/) (2022)
- [Combinatorial Optimization with Policy Adaptation using Latent Space Search](https://mlsanity.com/paper/2311.13569/) (2023)
- [One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction](https://mlsanity.com/paper/2208.10227/) (2022)
- [Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimization](https://mlsanity.com/paper/2306.02688/) (2023)
- [AutoShard: Automated Embedding Table Sharding for Recommender Systems](https://mlsanity.com/paper/2208.06399/) (2022)
- [A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization](https://mlsanity.com/paper/2211.03074/) (2022)
- [Distance-aware Attention Reshaping: Enhance Generalization of Neural Solver for Large-scale Vehicle Routing Problems](https://mlsanity.com/paper/2401.06979/) (2024)
- [Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration](https://mlsanity.com/paper/2205.14105/) (2022)
- [DreamShard: Generalizable Embedding Table Placement for Recommender Systems](https://mlsanity.com/paper/2210.02023/) (2022)
- [Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch](https://mlsanity.com/paper/2206.06965/) (2022)
- [Promoting Generalization for Exact Solvers via Adversarial Instance Augmentation](https://mlsanity.com/paper/2310.14161/) (2023)
- [Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning](https://mlsanity.com/paper/2506.02392/) (2025)
- [Are Graph Neural Networks Optimal Approximation Algorithms?](https://mlsanity.com/paper/2310.00526/) (2023)
- [Learning Combinatorial Node Labeling Algorithms](https://mlsanity.com/paper/2106.03594/) (2021)
- [Deep Policies for Online Bipartite Matching: A Reinforcement Learning Approach](https://mlsanity.com/paper/2109.10380/) (2021)
- [LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation](https://mlsanity.com/paper/2205.10106/) (2022)
- [Reversible Action Design for Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/2102.07210/) (2021)
- [State Sequences Prediction via Fourier Transform for Representation Learning](https://mlsanity.com/paper/2310.15888/) (2023)
- [Machine Learning Insides OptVerse AI Solver: Design Principles and Applications](https://mlsanity.com/paper/2401.05960/) (2024)
- [Vulcan: Solving the Steiner Tree Problem with Graph Neural Networks and Deep Reinforcement Learning](https://mlsanity.com/paper/2111.10810/) (2021)
- [Solving Dynamic Graph Problems with Multi-Attention Deep Reinforcement Learning](https://mlsanity.com/paper/2201.04895/) (2022)
- [A Unified Framework for Combinatorial Optimization Based on Graph Neural Networks](https://mlsanity.com/paper/2406.13125/) (2024)
- [Reinforcement learning with combinatorial actions for coupled restless bandits](https://mlsanity.com/paper/2503.01919/) (2025)
- [EFormer: An Effective Edge-based Transformer for Vehicle Routing Problems](https://mlsanity.com/paper/2506.16428/) (2025)
- [Learning for Robust Combinatorial Optimization: Algorithm and Application](https://mlsanity.com/paper/2112.10377/) (2021)

## Abstract (arXiv)

Many real-world problems can be reduced to combinatorial optimization on a graph, where the subset or ordering of vertices that maximize some objective function must be found. With such tasks often NP-hard and analytically intractable, reinforcement learning (RL) has shown promise as a framework with which efficient heuristic methods to tackle these problems can be learned. Previous works construct the solution subset incrementally, adding one element at a time, however, the irreversible nature of this approach prevents the agent from revising its earlier decisions, which may be necessary given the complexity of the optimization task. We instead propose that the agent should seek to continuously improve the solution by learning to explore at test time. Our approach of exploratory combinatorial optimization (ECO-DQN) is, in principle, applicable to any combinatorial problem that can be defined on a graph. Experimentally, we show our method to produce state-of-the-art RL performance on the Maximum Cut problem. Moreover, because ECO-DQN can start from any arbitrary configuration, it can be combined with other search methods to further improve performance, which we demonstrate using a simple random search.