# Reversible Action Design for Combinatorial Optimization with Reinforcement Learning

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 44 references that are in the map.
- First posted on arXiv 14 Feb 2021.

## Builds on (most cited first, 18 of 18)

- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Deep Reinforcement Learning in Large Discrete Action Spaces](https://mlsanity.com/paper/1512.07679/) (2015)
- [On the Limitations of Representing Functions on Sets](https://mlsanity.com/paper/1901.09006/) (2019)
- [Exploratory Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1909.04063/) (2019)
- [Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1911.04936/) (2019)
- [Q-Learning in enormous action spaces via amortized approximate maximization](https://mlsanity.com/paper/2001.08116/) (2020)
- [Revised Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks](https://mlsanity.com/paper/1706.07450/) (2017)
- [Learning Heuristics over Large Graphs via Deep Reinforcement Learning](https://mlsanity.com/paper/1903.03332/) (2019)
- [D'ej`a vu: A Contextualized Temporal Attention Mechanism for Sequential Recommendation](https://mlsanity.com/paper/2002.00741/) (2020)
- [Deep Perm-Set Net: Learn to predict sets with unknown permutation and cardinality using deep neural networks](https://mlsanity.com/paper/1805.00613/) (2018)
- [PiNet: A Permutation Invariant Graph Neural Network for Graph Classification](https://mlsanity.com/paper/1905.03046/) (2019)

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

- [One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction](https://mlsanity.com/paper/2208.10227/) (2022)
- [LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation](https://mlsanity.com/paper/2205.10106/) (2022)
- [Meta Policy Learning for Cold-Start Conversational Recommendation](https://mlsanity.com/paper/2205.11788/) (2022)
- [Meta-Reinforcement Learning via Exploratory Task Clustering](https://mlsanity.com/paper/2302.07958/) (2023)
- [Accelerating Diffusion-based Combinatorial Optimization Solvers by Progressive Distillation](https://mlsanity.com/paper/2308.06644/) (2023)
- [A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization](https://mlsanity.com/paper/2406.11897/) (2024)
- [RELS-DQN: A Robust and Efficient Local Search Framework for Combinatorial Optimization](https://mlsanity.com/paper/2304.06048/) (2023)

## Abstract (arXiv)

Combinatorial optimization problem (COP) over graphs is a fundamental challenge in optimization. Reinforcement learning (RL) has recently emerged as a new framework to tackle these problems and has demonstrated promising results. However, most RL solutions employ a greedy manner to construct the solution incrementally, thus inevitably pose unnecessary dependency on action sequences and need a lot of problem-specific designs. We propose a general RL framework that not only exhibits state-of-the-art empirical performance but also generalizes to a variety class of COPs. Specifically, we define state as a solution to a problem instance and action as a perturbation to this solution. We utilize graph neural networks (GNN) to extract latent representations for given problem instances for state-action encoding, and then apply deep Q-learning to obtain a policy that gradually refines the solution by flipping or swapping vertex labels. Experiments are conducted on Maximum k-Cut and Traveling Salesman Problem and performance improvement is achieved against a set of learning-based and heuristic baselines.