Research map / Learning theory and algorithms / Combinatorial and search optimization
Left Heavy Tails and the Effectiveness of the Policy and Value Networks in DNN-based best-first search for Sokoban Planning
Dieqiao Feng, Carla P Gomes, Bart Selman
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 |
|---|---|---|---|
| add policy term (1/p) to search evaluation function (ablation) | best-first search · Sokoban test set, 32,000 expansions | solved ratio: 19.6% -> 44.6% | Improved |
| use parent-only probability p instead of cumulative path probability pi (PHS) (ablation) | DBFS (d+h)/p · Sokoban test set, 32,000 expansions | solved ratio: 31.4% -> 50.0% | Improved |
| add depth and value terms to Pure Policy (ablation) | DBFS · Sokoban test set, 32,000 expansions | solved ratio: 44.6% -> 50.0% | Improved |
| increase value weight from 1.0 to 2.0 in (d+h)/p (ablation) | DBFS · Sokoban test set, 32,000 expansions | solved ratio: 50.0% -> 48.1% | Hurt |
| replace Pure Policy with PHS* evaluation (ablation) | DBFS · Sokoban test set, 32,000 expansions | solved ratio: 50.0% -> 46.2% | Hurt |
| use policy network instead of value network for dead-end detection (ablation) | DNN-guided search · Sokoban hard set | dead-end detection accuracy: 37% -> 68% | Improved |
| DBFS with learned networks versus hand-crafted Sokolution | DBFS · Sokoban hard set (10 min) | solved ratio: 0% -> 69% | Improved |
| DBFS vs Sokolution speed per second | DBFS · Sokoban | nodes per sec: 618 -> 37 | Hurt |
| use 30% MC dropout ratio (ablation) | DBFS · Sokoban | solved performance | Improved |
| add random restarts (2 restarts) at budget around 2,000 nodes (ablation) | DBFS · Sokoban test set | unsolved fraction | Improved |
| 5 restarts instead of 2 restarts at around 5,000 nodes (ablation) | DBFS · Sokoban test set | unsolved fraction | Improved |
| restarts for small budgets (ablation) | DBFS · Sokoban test set | unsolved fraction | Hurt |
Closest papers by meaning
- Learning to Search and Searching to Learn for Generalization in Planning (ICML 2026 · similarity 0.86)
- Learning Heuristic Functions with Graph Neural Networks for Numeric Planning (AAAI 2026 · similarity 0.86)
- Single-Agent Policy Tree Search With Guarantees (NeurIPS 2018 · similarity 0.86)
- Fat- and Heavy-Tailed Behavior in Satisficing Planning (AAAI 2018 · similarity 0.85)
- Scaling Value Iteration Networks to 5000 Layers for Extreme Long-Term Planning (ICML 2025 · similarity 0.84)
- Efficient Reinforcement Learning by Discovering Neural Pathways (NeurIPS 2024 · similarity 0.84)
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.
