# Monte Carlo Policy Gradient Method for Binary Optimization

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 48 references that are in the map.
- First posted on arXiv 3 Jul 2023.

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

- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [SimGNN: A Neural Network Approach to Fast Graph Similarity Computation](https://mlsanity.com/paper/1808.05689/) (2018)
- [Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problems](https://mlsanity.com/paper/1903.04598/) (2019)
- [Experimental performance of graph neural networks on random instances of max-cut](https://mlsanity.com/paper/1908.05767/) (2019)
- [MADAM: A parallel exact solver for Max-Cut based on semidefinite programming and ADMM](https://mlsanity.com/paper/2010.07839/) (2020)
- [Binary MIMO Detection via Homotopy Optimization and Its Deep Adaptation](https://mlsanity.com/paper/2004.12587/) (2020)
- [SDP-based branch-and-bound for non-convex quadratic integer optimization](https://mlsanity.com/paper/1901.10335/) (2019)
- [Tightness and Equivalence of Semidefinite Relaxations for MIMO Detection](https://mlsanity.com/paper/2102.04586/) (2021)

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

- [LMask: Learn to Solve Constrained Routing Problems with Lazy Masking](https://mlsanity.com/paper/2505.17938/) (2025)
- [On the Stochastic (Variance-Reduced) Proximal Gradient Method for Regularized Expected Reward Optimization](https://mlsanity.com/paper/2401.12508/) (2024)
- [Neural Quantile Optimization for Edge-Cloud Networking](https://mlsanity.com/paper/2307.05170/) (2023)
- [Improved Sparse Ising Optimization](https://mlsanity.com/paper/2311.09275/) (2023)
- [Learning to Solve the Quadratic Assignment Problem with Warm-Started MCMC Finetuning](https://mlsanity.com/paper/2604.20109/) (2026)

## Abstract (arXiv)

Binary optimization has a wide range of applications in combinatorial optimization problems such as MaxCut, MIMO detection, and MaxSAT. However, these problems are typically NP-hard due to the binary constraints. We develop a novel probabilistic model to sample the binary solution according to a parameterized policy distribution. Specifically, minimizing the KL divergence between the parameterized policy distribution and the Gibbs distributions of the function value leads to a stochastic optimization problem whose policy gradient can be derived explicitly similar to reinforcement learning. For coherent exploration in discrete spaces, parallel Markov Chain Monte Carlo (MCMC) methods are employed to sample from the policy distribution with diversity and approximate the gradient efficiently. We further develop a filter scheme to replace the original objective function by the one with the local search technique to broaden the horizon of the function landscape. Convergence to stationary points in expectation of the policy gradient method is established based on the concentration inequality for MCMC. Numerical results show that this framework is very promising to provide near-optimal solutions for quite a few binary optimization problems.