Research map / Reinforcement learning / Visual and representation RL
Subgoal-Guided Policy Heuristic Search with Learned Subgoals
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Learns subgoal-conditioned low-level and high-level policies (VQVAE subgoal generator) for policy tree search (PHS*, LevinTS) online during Bootstrap training, using both solution and failed-search trees, improving sample efficiency on needle-in-haystack search domains.
Problem
Training policies for policy-guided tree search online is sample-inefficient on hard instances because budget-bounded failed searches are discarded and random initial policies waste expansions; existing subgoal methods need precomputed solution datasets and lack completeness.
Approach
Combine a VQVAE subgoal generator with subgoal-conditioned low-level policies mixed geometrically via a high-level subgoal policy (pi^SG), and train them from both solution trajectories and non-solution search trees by clustering the expanded subgraph with the Louvain algorithm to sample subgoal pairs.
Key results
- On hard CraftWorld, PHS*(pi^SG) solved 9,985 of 10,000 training problems with 125M total expansions versus ~325M for PHS*(pi) which solved 54.
- On TSP (Hard) test set, PHS*(pi^SG) solved 100/100 with 41.93 average expansions while WA* solved 1 and LevinTS(pi) and PHS*(pi) solved 0.
- On standard Box-World test set, PHS*(pi^SG) averaged 378.58 expansions versus 767.06 for PHS*(pi).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the single policy with a subgoal-guided policy | PHS* on CraftWorld Hard training · CraftWorld Hard training | Expansions: 324,718,860 -> 125,089,420 | Helped |
| Replace the single policy with a subgoal-guided policy | PHS* on BoulderDash Hard training · BoulderDash Hard training | Expansions: 591,135,427 -> 85,470,564 | Helped |
| Replace the single policy with a subgoal-guided policy | PHS* on TSP Hard training · TSP Hard training | Expansions: 980,928,000 -> 20,593,798 | Helped |
| Use subgoal-guided policies trained on search trees | Policy tree search on hard test domains · CraftWorld, BoulderDash, and TSP Hard test | Solved: 0 -> 100 | Helped |
| Use the subgoal-guided policy | PHS* on Sokoban Standard test · Sokoban Standard test | Expansions: 1,523.38 -> 808.42 | Hurt |
| Use codebook size k=1 instead of k=4 (ablation) | Subgoal-guided search · CraftWorld Standard test | Expansions: 103.23 -> 263.92 | Hurt |
| Use codebook size k=16 instead of k=4 (ablation) | Subgoal-guided search · CraftWorld Standard test | Expansions: 103.23 -> 305.17 | Hurt |
| Sample subgoals from cluster graph G1 instead of G3 (ablation) | Subgoal-guided search · CraftWorld Standard test | Expansions: 103.23 -> 287.24 | Hurt |
| Sample subgoals from cluster graph G5 instead of G3 (ablation) | Subgoal-guided search · CraftWorld Standard test | Expansions: 103.23 -> 110.10 | Hurt |
| Train the subgoal-guided policy using solution trajectories only, rather than both successful and failed searches (ablation) | PHS*(πSG) · BoulderDash training | Search loss | Hurt |
| Use the subgoal-guided policy rather than a single policy | LevinTS on BoulderDash Standard test · BoulderDash Standard test | Expansions: 61.33 -> 65.48 | Hurt |
| Use the subgoal-guided policy rather than a single policy | PHS* on Sokoban Standard test · Sokoban Standard test | Expansions: 1,523.38 -> 808.42 | Hurt |
Surprising findings
- HIPS-epsilon solved only 19 of 100 CraftWorld test problems and 0 BoulderDash problems, attributed to poor VQVAE state reconstruction.
- Sokoban is the one domain where the proposed method underperforms PHS*(pi) early in training.
Limitations
- Performs worse in Sokoban, attributed to clustering not finding useful structure there.
- HIPS-epsilon comparison limited to 8,000 budget at test time and its expansions are not directly comparable.
- Higher computational cost per node expansion due to multiple networks.
Experimental setup
Datasets: Box-World generator CraftWorld generator (psketch) BoulderDash custom generator Boxoban TSP custom generator
Benchmarks: Box-World CraftWorld BoulderDash Sokoban TSP
Metrics: number of node expansions solved problems solution length training search loss time
Baselines: PHS* LevinTS Weighted A* HIPS-epsilon
Builds on: PHS* LevinTS Bootstrap HIPS-epsilon VQ-VAE
Closest papers by meaning
- In Search of Trees: Decision-Tree Policy Synthesis for Black-Box Systems via Search (AAAI 2025 · similarity 0.87)
- Policy Guided Tree Search for Enhanced LLM Reasoning (ICML 2025 · similarity 0.86)
- A Surprisingly Simple Continuous-Action POMDP Solver: Lazy Cross-Entropy Search Over Policy Trees (AAAI 2024 · similarity 0.86)
- SPOT: Scalable Policy Optimization with Trees for Markov Decision Processes (NeurIPS 2025 · similarity 0.85)
- Search Strategy Generation for Branch and Bound Using Genetic Programming (AAAI 2025 · similarity 0.84)
- DGPO: Discovering Multiple Strategies with Diversity-Guided Policy Optimization (AAAI 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.