Research map / Probabilistic and scientific modeling / Molecules and proteins
Provably Efficient Long-Horizon Exploration in Monte Carlo Tree Search through State Occupancy Regularization
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.
Derives Volume-MCTS, a tree search that regularizes the state occupancy measure of tree expansions, recovering RRT Voronoi bias and count-based exploration as special cases, and outperforms AlphaZero variants on robot maze navigation.
Problem
MCTS and AlphaZero struggle with long-horizon exploration in continuous state and action spaces, where sampling-based motion planning methods like RRT explore more efficiently.
Approach
Formulates tree search as policy optimization with f-divergence regularization of the state occupancy measure over expanded nodes; shows that for trees the convex objective decomposes into per-node policy optimality, yielding a closed-form tree policy with Voronoi (RRT-like) volume weighting and a k-d tree value sharing across branches.
Key results
- On geometric mazes before training, Volume-MCTS reaches 49 on size 2 and 7 on size 9 while AlphaZero falls to 0 by size 5 (5000 rollouts per episode).
- After training on Dubins car mazes, Volume-MCTS scores 26.0 on size 6 versus 0 for AlphaZero and AlphaZero w/ CBE.
- On the quadcopter task, Volume-MCTS significantly outperforms HER and POLY-HOOT and performs better than SST at longer search times.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Volume-MCTS instead of AlphaZero and its reported variants | Geometric maze navigation · Geometric maze size 9, no training | average reward: 0.0 $\pm$ 0.0 -> 7.0 $\pm$ 3.0 | Helped |
| use Volume-MCTS instead of AlphaZero and its reported variants | Geometric maze navigation · Geometric maze size 9, after training | average reward: 0.0 $\pm$ 0.0 -> 26.0 $\pm$ 4.0 | Helped |
| use Volume-MCTS instead of AlphaZero variants | Dubins car maze navigation · Dubins car maze size 6, after training | average reward: 0.0$\pm$0.0 -> 26.0$\pm$3.0 | Helped |
| add reward guidance to Volume-MCTS (ablation) | Volume-MCTS · Geometric maze sizes 2–8, no training | average reward: 47.7 $\pm$ 0.3 -> 49.0 $\pm$ 0.0; 43.9 $\pm$ 0.1 -> 46.0 $\pm$ 0.0; 40.0 $\pm$ 0.8 -> 43.0 $\pm$ 1.0; 33.5 $\pm$ 4.4 -> | Helped |
| add reward guidance to Volume-MCTS (ablation) | Volume-MCTS · Geometric maze size 9, no training | average reward: 9.1 $\pm$ 7.7 -> 7.0 $\pm$ 3.0 | Mixed |
| add policy regularization for action-dependent rewards (ablation) | Volume-MCTS · Long-horizon exploration | exploration efficiency | Hurt |
Surprising findings
- Adding a regularization offset for action-dependent rewards was found detrimental to long-horizon exploration and was not used.
- Ablating reward guidance (all rewards set to zero, equivalent to Kinodynamic-RRT) yields a noticeably lower average reward on mazes, though the gap is not uniform.
Limitations
- Volume-MCTS is most applicable to deterministic navigation environments; stochastic dynamics only sketched via double progressive widening without analysis.
- Consistency of the k-d tree value estimator is conjectured but not proven.
- The policy network is trained with ordinary f-divergence regularization rather than the derived state-occupancy objective.
Experimental setup
Benchmarks: geometric maze navigation (2-9) Dubins car maze (2-6) quadcopter navigation
Metrics: average reward standard error reward vs environment interactions
Baselines: AlphaZero AlphaZero w/ CBE Open-loop AlphaZero POLY-HOOT SAC with HER SST Kinodynamic-RRT
Builds on: AlphaZero regularized policy optimization MCTS RRT Never Give Up POLY-HOOT
Closest papers by meaning
- Graph Sparse Sampling: Breaking the Curse of the Horizon in Continuous MDP Planning (NeurIPS 2026 · similarity 0.88)
- Graph-Based Stochastic-Power-UCT: Monte-Carlo Graph Search with Power Mean Estimation (NeurIPS 2026 · similarity 0.87)
- Compositional Monte Carlo Tree Diffusion for Extendable Planning (NeurIPS 2025 · similarity 0.86)
- Monte-Carlo Tree Search with Uncertainty Propagation via Optimal Transport (ICML 2025 · similarity 0.86)
- Decoupling Exploration and Policy Optimization: Uncertainty Guided Tree Search for Hard Exploration (NeurIPS 2026 · similarity 0.86)
- Power Mean Estimation in Stochastic Continuous Monte-Carlo Tree Search (ICML 2025 · similarity 0.86)
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.