mlsanityData to 14 Oct 2026

Single-Agent Policy Tree Search With Guarantees

arXiv 1811.10928 ↗First posted 27 Nov 2018cs.AIcited by 22

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 3; 2022: 2; 2023: 5; 2024: 3; 2025: 4; 2026: 5.

22 papers.

Sort:

By area:

  1. 2021Policy-Guided Heuristic Search with Guaranteescited by 20
  2. 2023Hierarchical Imitation Learning with Vector Quantized Modelscited by 15
  3. 2023Optimize Planning Heuristics to Rank, not to Estimate Cost-to-Goalcited by 10
  4. 2025AI Agents as Universal Task Solverscited by 9
  5. 2023Levin Tree Search with Context Modelscited by 7
  6. 2023Hybrid Search for Efficient Planning with Completeness Guaranteescited by 6
  7. 2025Contrastive Representations for Temporal Reasoningcited by 6
  8. 2021Exploiting Learned Policies in Focal Searchcited by 3
  9. 2022Policy-Guided Lazy Search with Feedback for Task and Motion Planningcited by 1
  10. 2024Beyond Training: Optimizing Reinforcement Learning Based Job Shop Scheduling Through Adaptive Action Samplingcited by 1
  11. 2024Exponential Speedups by Rerooting Levin Tree Searchcited by 1
  12. 2025Reinforcement Learning-based Heuristics to Guide Domain-Independent Dynamic Programmingcited by 1
10 more
  1. 2025Subgoal-Guided Policy Heuristic Search with Learned Subgoalscited by 1
  2. 2021Reinforcement Learning with Information-Theoretic Actuationcited by 0
  3. 2022The (Un)Scalability of Heuristic Approximators for NP-Hard Search Problemscited by 0
  4. 2023Alphazzle: Jigsaw Puzzle Solver with Deep Monte-Carlo Tree Searchcited by 0
  5. 2024Unveiling Options with Neural Decompositioncited by 0
  6. 2026Policy-Guided Search on Tree-of-Thoughts for Efficient Problem Solving with Bounded Language Model Queriescited by 0
  7. 2026PAC-CF: Calibrating Irreversible Frontier Pruning in LLM-Guided Searchcited by 0
  8. 2026Pseudocode-Guided Structured Reasoning for Automating Reliable Inference in Vision-Language Modelscited by 0
  9. 2026Structure-Induced Information for Rerooting Levin Tree Searchcited by 0
  10. 2026Direct Optimization of Generators for Search in Automated Theorem Provingcited by 0