mlsanityData to 7 Oct 2026

Policy-Based Self-Competition for Planning Problems

arXiv 2306.04403 ↗First posted 7 Jun 2023cs.LGcited by 3

Not on the map. Why?

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.

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

Builds on

31 of 51 references.

References · 31

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  4. 2016Gaussian Error Linear Units (GELUs)cited by 3,431
  5. 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,327
  6. 2018Attention, Learn to Solve Routing Problems!cited by 646
  7. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 600
  8. 2016Self-critical Sequence Training for Image Captioningcited by 544
  9. 2018Implicit Quantile Networks for Distributional Reinforcement Learningcited by 362
  10. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 341
  11. 2019Learning Deep Transformer Models for Machine Translationcited by 309
  12. 2019Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacementcited by 205
19 more
  1. 2017Intrinsic Motivation and Automatic Curricula via Asymmetric Self-Playcited by 139
  2. 2020Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learningcited by 139
  3. 2017Emergent Complexity via Multi-Agent Competitioncited by 117
  4. 2020Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learningcited by 100
  5. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  6. 2016Learning values across many orders of magnitudecited by 80
  7. 2021Learning and Planning in Complex Action Spacescited by 76
  8. 2020Monte-Carlo Tree Search as Regularized Policy Optimizationcited by 59
  9. 2021Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learningcited by 52
  10. 2018Observe and Look Further: Achieving Consistent Performance on Ataricited by 42
  11. 2021ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learningcited by 31
  12. 2022MuZero with Self-competition for Rate Control in VP9 Video Compressioncited by 27
  13. 2018Ranked Reward: Enabling Self-Play Reinforcement Learning for Combinatorial Optimizationcited by 25
  14. 2021A Reinforcement Learning Environment For Job-Shop Schedulingcited by 21
  15. 2021Automated Synthesis of Steady-State Continuous Processes using Reinforcement Learningcited by 10
  16. 2020Solve Traveling Salesman Problem by Monte Carlo Tree Search and Deep Neural Networkcited by 7
  17. 2020Tackling Morpion Solitaire with AlphaZero-likeRanked Reward Reinforcement Learningcited by 6
  18. 2020Reinforcement Learning Enhanced Quantum-inspired Algorithm for Combinatorial Optimizationcited by 4
  19. 2019Self-Play Learning Without a Reward Metriccited by 3

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 1; 2025: 1.

3 papers.

  1. 2024Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvementcited by 32
  2. 2023Deep reinforcement learning uncovers processes for separating azeotropic mixtures without prior knowledgecited by 0
  3. 2025TSS GAZ PTP: Towards Improving Gumbel AlphaZero with Two-stage Self-play for Multi-constrained Electric Vehicle Routing Problemscited by 0