Research map / Reinforcement learning / Visual and representation RL
Structure-Induced Information for Rerooting Levin Tree Search
Jake Tuero, Michael Buro, Laurent Orseau, Levi Lelis
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 a rerooter (√LTS-LH) instead of plain LTS during online bootstrap training | LTS · BoulderDash hard test | problems solved: 10 -> 100 solved | Improved |
| add heuristic-based rerooting (√LTS-H) in place of subgoal-conditioned policy (PHS*(πSG)) when dirt reaches 20% | BoulderDash training · BoulderDash 20% dirt | training expansions: 299,672,516 -> 19,866,165 | Improved |
| increase dirt fraction in BoulderDash to 30% or more | PHS*(πSG) · BoulderDash training | training problems solved: 10,000 -> 11 (30%), no progress at 40%/50% | Hurt |
| increase dirt fraction to 50% | √LTS-L · BoulderDash training | training problems solved: 9,998 -> 605 (10% -> 50%) | Hurt |
| add heuristic signal to clustering rerooter (√LTS-LH vs √LTS-L) (ablation) | √LTS-L · CraftWorld hard test | expansions: 8,802.62 -> 1,347.52 | Improved |
| add clustering signal to heuristic rerooter (√LTS-LH vs √LTS-H) (ablation) | √LTS-H · CraftWorld hard test | expansions: 2,514.62 -> 1,347.52 | Improved |
| add clustering signal to heuristic rerooter (√LTS-LH vs √LTS-H) (ablation) | √LTS-H · Sokoban test | expansions: 2,626.82 -> 1,736.03 | Improved |
| add clustering signal to heuristic rerooter (√LTS-LH vs √LTS-H) (ablation) | √LTS-H · BoulderDash 30% dirt training | training expansions: 27,965,657 -> 57,780,467 | Hurt |
| add clustering signal to heuristic rerooter (√LTS-LH vs √LTS-H) (ablation) | √LTS-H · BoulderDash hard test | expansions: 92.37 -> 92.68 | No clear effect |
| replace subgoal generation with clustering-based rerooting (√LTS-L vs LTS(πSG)) | LTS(πSG) · BoulderDash hard test | expansions: 202.38 -> 131.18 | Improved |
| use rerooting instead of PHS*(πSG) on TSP and Sokoban test | PHS*(πSG) · TSP (GridWorld) test | expansions: 46.31 -> 55.44 (√LTS-H) | Hurt |
| use heuristic rerooter instead of WA* | WA*(1.5) · Sokoban test | expansions: 1,201.03 -> 2,626.82 | Hurt |
Closest papers by meaning
- Subgoal-Guided Policy Heuristic Search with Learned Subgoals (ICML 2025 · similarity 0.89)
- A Surprisingly Simple Continuous-Action POMDP Solver: Lazy Cross-Entropy Search Over Policy Trees (AAAI 2024 · similarity 0.86)
- Decoupling Exploration and Policy Optimization: Uncertainty Guided Tree Search for Hard Exploration (NeurIPS 2026 · similarity 0.86)
- SPOT: Scalable Policy Optimization with Trees for Markov Decision Processes (NeurIPS 2025 · similarity 0.86)
- PAIR: Prefix-Aware Internal Reward Model for Multi-Turn Agent Optimization (NeurIPS 2026 · similarity 0.85)
- Policy Guided Tree Search for Enhanced LLM Reasoning (ICML 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.
