Overview
- Field: AI
- Authors: Idan Lev-Yehudi, Vadim Indelman
- Published: 2026-07-06
- arXiv: 2607.05359
Summary
Planning in continuous domains under uncertainty is critical for autonomous systems but computationally expensive. Tree-search methods such as MCTS remain popular; however, their branching structure requires, in the worst case, a sampling budget that grows exponentially with the lookahead depth.
This paper introduces Graph Sparse Sampling (GSS), an online planning algorithm that shares sampled futures across multiple candidate decisions rather than sampling independent successors for each candidate action. This branchless graph exposes large GPU-friendly batches while using heuristics to focus computation.
The authors prove finite-sample performance guarantees for GSS. Under suitable overlap, regularity, and action coverage conditions, these bounds depend polynomially on the planning horizon, formally characterizing when shared futures can avoid the exponential horizon dependency of tree-based sparse sampling.
In continuous control simulations, GSS substantially outperforms tree-based planners on long horizons or achieves near-optimal performance.
---
*Auto-collected on 2026-07-06 from zhichai.net.*