# Policy-Based Self-Competition for Planning Problems

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 51 references that are in the map.
- First posted on arXiv 7 Jun 2023.

## Builds on (most cited first, 30 of 31)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Gaussian Error Linear Units (GELUs)](https://mlsanity.com/paper/1606.08415/) (2016)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [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)
- [Self-critical Sequence Training for Image Captioning](https://mlsanity.com/paper/1612.00563/) (2016)
- [Implicit Quantile Networks for Distributional Reinforcement Learning](https://mlsanity.com/paper/1806.06923/) (2018)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Learning Deep Transformer Models for Machine Translation](https://mlsanity.com/paper/1906.01787/) (2019)
- [Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement](https://mlsanity.com/paper/1903.06059/) (2019)
- [Intrinsic Motivation and Automatic Curricula via Asymmetric Self-Play](https://mlsanity.com/paper/1703.05407/) (2017)
- [Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning](https://mlsanity.com/paper/2010.12367/) (2020)
- [Emergent Complexity via Multi-Agent Competition](https://mlsanity.com/paper/1710.03748/) (2017)
- [Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning](https://mlsanity.com/paper/2004.01608/) (2020)
- [Deep Policy Dynamic Programming for Vehicle Routing Problems](https://mlsanity.com/paper/2102.11756/) (2021)
- [Learning values across many orders of magnitude](https://mlsanity.com/paper/1602.07714/) (2016)
- [Learning and Planning in Complex Action Spaces](https://mlsanity.com/paper/2104.06303/) (2021)
- [Monte-Carlo Tree Search as Regularized Policy Optimization](https://mlsanity.com/paper/2007.12509/) (2020)
- [Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learning](https://mlsanity.com/paper/2106.01086/) (2021)
- [Observe and Look Further: Achieving Consistent Performance on Atari](https://mlsanity.com/paper/1805.11593/) (2018)
- [ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learning](https://mlsanity.com/paper/2106.03051/) (2021)
- [MuZero with Self-competition for Rate Control in VP9 Video Compression](https://mlsanity.com/paper/2202.06626/) (2022)
- [Ranked Reward: Enabling Self-Play Reinforcement Learning for Combinatorial Optimization](https://mlsanity.com/paper/1807.01672/) (2018)
- [A Reinforcement Learning Environment For Job-Shop Scheduling](https://mlsanity.com/paper/2104.03760/) (2021)
- [Automated Synthesis of Steady-State Continuous Processes using Reinforcement Learning](https://mlsanity.com/paper/2101.04422/) (2021)
- [Solve Traveling Salesman Problem by Monte Carlo Tree Search and Deep Neural Network](https://mlsanity.com/paper/2005.06879/) (2020)
- [Tackling Morpion Solitaire with AlphaZero-likeRanked Reward Reinforcement Learning](https://mlsanity.com/paper/2006.07970/) (2020)
- [Reinforcement Learning Enhanced Quantum-inspired Algorithm for Combinatorial Optimization](https://mlsanity.com/paper/2002.04676/) (2020)

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

- [Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement](https://mlsanity.com/paper/2403.15180/) (2024)
- [Deep reinforcement learning uncovers processes for separating azeotropic mixtures without prior knowledge](https://mlsanity.com/paper/2310.06415/) (2023)
- [TSS GAZ PTP: Towards Improving Gumbel AlphaZero with Two-stage Self-play for Multi-constrained Electric Vehicle Routing Problems](https://mlsanity.com/paper/2502.15777/) (2025)

## Abstract (arXiv)

AlphaZero-type algorithms may stop improving on single-player tasks in case the value network guiding the tree search is unable to approximate the outcome of an episode sufficiently well. One technique to address this problem is transforming the single-player task through self-competition. The main idea is to compute a scalar baseline from the agent's historical performances and to reshape an episode's reward into a binary output, indicating whether the baseline has been exceeded or not. However, this baseline only carries limited information for the agent about strategies how to improve. We leverage the idea of self-competition and directly incorporate a historical policy into the planning process instead of its scalar performance. Based on the recently introduced Gumbel AlphaZero (GAZ), we propose our algorithm GAZ 'Play-to-Plan' (GAZ PTP), in which the agent learns to find strong trajectories by planning against possible strategies of its past self. We show the effectiveness of our approach in two well-known combinatorial optimization problems, the Traveling Salesman Problem and the Job-Shop Scheduling Problem. With only half of the simulation budget for search, GAZ PTP consistently outperforms all selected single-player variants of GAZ.