Research map / Learning theory and algorithms / Combinatorial and search optimization
Single-Agent Policy Tree Search With Guarantees
Laurent Orseau, Levi Lelis, Tor Lattimore, Theophane Weber
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LevinTS guided by an A3C policy instead of LAMA | Sokoban solver · Sokoban, 1,000 levels | Avg. length: 51.6 -> 39.8 | Improved |
| Use LevinTS guided by an A3C policy instead of LAMA | Sokoban solver · Sokoban, 1,000 levels | Total expansions: 3,151,325 -> 6,602,666 | Hurt |
| Add 1% noise to the policy used by LevinTS (ablation) | LevinTS · Sokoban, 1,000 levels | Total expansions: 6,602,666 -> 5,026,200 | Improved |
| Add 1% noise to the policy used by LevinTS (ablation) | LevinTS · Sokoban, 1,000 levels | Solved: 1,000 -> 1,000 | No clear effect |
| Use LubyTS(256, 32) instead of LubyTS(256, 1) (ablation) | LubyTS · Sokoban, 1,000 levels | Solved: 753 ± 5 -> 870 ± 2 | Improved |
| Use LubyTS(256, 32) instead of LubyTS(256, 1) (ablation) | LubyTS · Sokoban, 1,000 levels | Total expansions: 63,8481 ± 2,434 -> 6,246,293 ± 73,382 | Mixed |
| Add 1% noise to the policy used by LubyTS(512, 32) (ablation) | LubyTS(512, 32) · Sokoban, 1,000 levels | Solved: 884 ± 4 -> 896 ± 2 | Improved |
| Add 1% noise to the policy used by MultiTS(200, 200) (ablation) | MultiTS(200, 200) · Sokoban, 1,000 levels | Solved: 881 ± 1 -> 895 ± 3 | Improved |
| Use MultiTS(200, 200) instead of MultiTS(1, 200) (ablation) | MultiTS · Sokoban, 1,000 levels | Solved: 669 ± 5 -> 881 ± 1 | Improved |
| Use policy-guided search instead of sampling a single trajectory | Policy tree search · Sokoban, 1,000 levels | Solved: The text reports more than 20% improvement | Improved |
Closest papers by meaning
- Subgoal-Guided Policy Heuristic Search with Learned Subgoals (ICML 2025 · similarity 0.91)
- In Search of Trees: Decision-Tree Policy Synthesis for Black-Box Systems via Search (AAAI 2025 · similarity 0.89)
- Structure-Induced Information for Rerooting Levin Tree Search (ICML 2026 · similarity 0.88)
- SPOT: Scalable Policy Optimization with Trees for Markov Decision Processes (NeurIPS 2025 · similarity 0.86)
- A Surprisingly Simple Continuous-Action POMDP Solver: Lazy Cross-Entropy Search Over Policy Trees (AAAI 2024 · similarity 0.85)
- Search Strategy Generation for Branch and Bound Using Genetic Programming (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
