# Single-Agent Policy Tree Search With Guarantees

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Nov 2018.

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

- [Policy-Guided Heuristic Search with Guarantees](https://mlsanity.com/paper/2103.11505/) (2021)
- [Hierarchical Imitation Learning with Vector Quantized Models](https://mlsanity.com/paper/2301.12962/) (2023)
- [Optimize Planning Heuristics to Rank, not to Estimate Cost-to-Goal](https://mlsanity.com/paper/2310.19463/) (2023)
- [AI Agents as Universal Task Solvers](https://mlsanity.com/paper/2510.12066/) (2025)
- [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)
- [Contrastive Representations for Temporal Reasoning](https://mlsanity.com/paper/2508.13113/) (2025)
- [Exploiting Learned Policies in Focal Search](https://mlsanity.com/paper/2104.10535/) (2021)
- [Policy-Guided Lazy Search with Feedback for Task and Motion Planning](https://mlsanity.com/paper/2210.14055/) (2022)
- [Beyond Training: Optimizing Reinforcement Learning Based Job Shop Scheduling Through Adaptive Action Sampling](https://mlsanity.com/paper/2406.07325/) (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)
- [Alphazzle: Jigsaw Puzzle Solver with Deep Monte-Carlo Tree Search](https://mlsanity.com/paper/2302.00384/) (2023)
- [Unveiling Options with Neural Decomposition](https://mlsanity.com/paper/2410.11262/) (2024)
- [Policy-Guided Search on Tree-of-Thoughts for Efficient Problem Solving with Bounded Language Model Queries](https://mlsanity.com/paper/2601.03606/) (2026)
- [PAC-CF: Calibrating Irreversible Frontier Pruning in LLM-Guided Search](https://mlsanity.com/paper/2604.14345/) (2026)
- [Pseudocode-Guided Structured Reasoning for Automating Reliable Inference in Vision-Language Models](https://mlsanity.com/paper/2605.19663/) (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)

We introduce two novel tree search algorithms that use a policy to guide search. The first algorithm is a best-first enumeration that uses a cost function that allows us to prove an upper bound on the number of nodes to be expanded before reaching a goal state. We show that this best-first algorithm is particularly well suited for `needle-in-a-haystack' problems. The second algorithm is based on sampling and we prove an upper bound on the expected number of nodes it expands before reaching a set of goal states. We show that this algorithm is better suited for problems where many paths lead to a goal. We validate these tree search algorithms on 1,000 computer-generated levels of Sokoban, where the policy used to guide the search comes from a neural network trained using A3C. Our results show that the policy tree search algorithms we introduce are competitive with a state-of-the-art domain-independent planner that uses heuristic search.