# Policy-Guided Heuristic Search with Guarantees

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 32 references that are in the map.
- First posted on arXiv 21 Mar 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Imagination-Augmented Agents for Deep Reinforcement Learning](https://mlsanity.com/paper/1707.06203/) (2017)
- [The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks](https://mlsanity.com/paper/1401.3839/) (2014)
- [An investigation of model-free planning](https://mlsanity.com/paper/1901.03559/) (2019)
- [Single-Agent Policy Tree Search With Guarantees](https://mlsanity.com/paper/1811.10928/) (2018)
- [Iterative Budgeted Exponential Search](https://mlsanity.com/paper/1907.13062/) (2019)

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

- [Hierarchical Imitation Learning with Vector Quantized Models](https://mlsanity.com/paper/2301.12962/) (2023)
- [Proving Theorems using Incremental Learning and Hindsight Experience Replay](https://mlsanity.com/paper/2112.10664/) (2021)
- [Optimize Planning Heuristics to Rank, not to Estimate Cost-to-Goal](https://mlsanity.com/paper/2310.19463/) (2023)
- [Levin Tree Search with Context Models](https://mlsanity.com/paper/2305.16945/) (2023)
- [Hybrid Search for Efficient Planning with Completeness Guarantees](https://mlsanity.com/paper/2310.12819/) (2023)
- [Exploiting Learned Policies in Focal Search](https://mlsanity.com/paper/2104.10535/) (2021)
- [Left Heavy Tails and the Effectiveness of the Policy and Value Networks in DNN-based best-first search for Sokoban Planning](https://mlsanity.com/paper/2206.14298/) (2022)
- [Learning Admissible Heuristics for A*: Theory and Practice](https://mlsanity.com/paper/2509.22626/) (2025)
- [What Matters in Hierarchical Search for Combinatorial Reasoning Problems?](https://mlsanity.com/paper/2406.03361/) (2024)
- [A Training Data Recipe to Accelerate A* Search with Language Models](https://mlsanity.com/paper/2407.09985/) (2024)
- [Exponential Speedups by Rerooting Levin Tree Search](https://mlsanity.com/paper/2412.05196/) (2024)
- [Reinforcement Learning-based Heuristics to Guide Domain-Independent Dynamic Programming](https://mlsanity.com/paper/2503.16371/) (2025)
- [Subgoal-Guided Policy Heuristic Search with Learned Subgoals](https://mlsanity.com/paper/2506.07255/) (2025)
- [Reinforcement Learning with Information-Theoretic Actuation](https://mlsanity.com/paper/2109.15147/) (2021)
- [The (Un)Scalability of Heuristic Approximators for NP-Hard Search Problems](https://mlsanity.com/paper/2209.03393/) (2022)
- [Solving Witness-type Triangle Puzzles Faster with an Automatically Learned Human-Explainable Predicate](https://mlsanity.com/paper/2308.02666/) (2023)
- [Graph Learning for Planning: The Story Thus Far and Open Challenges](https://mlsanity.com/paper/2412.02136/) (2024)
- [Learning to Search and Searching to Learn for Generalization in Planning](https://mlsanity.com/paper/2605.25720/) (2026)
- [Structure-Induced Information for Rerooting Levin Tree Search](https://mlsanity.com/paper/2605.30664/) (2026)
- [Direct Optimization of Generators for Search in Automated Theorem Proving](https://mlsanity.com/paper/2609.25575/) (2026)

## Abstract (arXiv)

The use of a policy and a heuristic function for guiding search can be quite effective in adversarial problems, as demonstrated by AlphaGo and its successors, which are based on the PUCT search algorithm. While PUCT can also be used to solve single-agent deterministic problems, it lacks guarantees on its search effort and it can be computationally inefficient in practice. Combining the A* algorithm with a learned heuristic function tends to work better in these domains, but A* and its variants do not use a policy. Moreover, the purpose of using A* is to find solutions of minimum cost, while we seek instead to minimize the search loss (e.g., the number of search steps). LevinTS is guided by a policy and provides guarantees on the number of search steps that relate to the quality of the policy, but it does not make use of a heuristic function. In this work we introduce Policy-guided Heuristic Search (PHS), a novel search algorithm that uses both a heuristic function and a policy and has theoretical guarantees on the search loss that relates to both the quality of the heuristic and of the policy. We show empirically on the sliding-tile puzzle, Sokoban, and a puzzle from the commercial game `The Witness' that PHS enables the rapid learning of both a policy and a heuristic function and compares favorably with A*, Weighted A*, Greedy Best-First Search, LevinTS, and PUCT in terms of number of problems solved and search time in all three domains tested.