# Policy Gradient Search: Online Planning and Expert Iteration without Search Trees

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Apr 2019.

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

- [Planning Like Human: A Dual-process Framework for Dialogue Planning](https://mlsanity.com/paper/2406.05374/) (2024)
- [Training a Generally Curious Agent](https://mlsanity.com/paper/2502.17543/) (2025)
- [Self-Improved Retrosynthetic Planning](https://mlsanity.com/paper/2106.04880/) (2021)
- [Scalable Online Planning via Reinforcement Learning Fine-Tuning](https://mlsanity.com/paper/2109.15316/) (2021)
- [Improving exploration in policy gradient search: Application to symbolic optimization](https://mlsanity.com/paper/2107.09158/) (2021)
- [Thinker: Learning to Plan and Act](https://mlsanity.com/paper/2307.14993/) (2023)
- [The Update-Equivalence Framework for Decision-Time Planning](https://mlsanity.com/paper/2304.13138/) (2023)
- [ExPoSe: Combining State-Based Exploration with Gradient-Based Online Search](https://mlsanity.com/paper/2202.01461/) (2022)
- [Policy Gradient Algorithms with Monte Carlo Tree Learning for Non-Markov Decision Processes](https://mlsanity.com/paper/2206.01011/) (2022)
- [Spatial Assembly: Generative Architecture With Reinforcement Learning, Self Play and Tree Search](https://mlsanity.com/paper/2101.07579/) (2021)
- [Self-Play Search Distillation for Large Language Model Reasoning](https://mlsanity.com/paper/2609.30936/) (2026)
- [Learning to Play: Reinforcement Learning and Games](https://mlsanity.com/paper/2610.17391/) (2026)

## Abstract (arXiv)

Monte Carlo Tree Search (MCTS) algorithms perform simulation-based search to improve policies online. During search, the simulation policy is adapted to explore the most promising lines of play. MCTS has been used by state-of-the-art programs for many problems, however a disadvantage to MCTS is that it estimates the values of states with Monte Carlo averages, stored in a search tree; this does not scale to games with very high branching factors. We propose an alternative simulation-based search method, Policy Gradient Search (PGS), which adapts a neural network simulation policy online via policy gradient updates, avoiding the need for a search tree. In Hex, PGS achieves comparable performance to MCTS, and an agent trained using Expert Iteration with PGS was able defeat MoHex 2.0, the strongest open-source Hex agent, in 9x9 Hex.