Idan Lev-Yehudi, Vadim Indelman
To address the exponential complexity of tree-based search in continuous MDP planning, this paper proposes Graph Sparse Sampling (GSS), an algorithm that shares sampled futures across decisions, and provides theoretical performance guarantees.
Online planning under uncertainty in continuous state/action spaces is computationally demanding. Tree-based methods like MCTS can require sampling budgets that grow exponentially with lookahead depth, especially challenging in continuous spaces with infinite branching.
Graph Sparse Sampling (GSS) is an online planning algorithm that shares sampled futures across many candidate decisions, rather than sampling separate successors for each action. This branch-free graph structure enables large, GPU-friendly batches and uses heuristics to focus computation. Finite-sample performance guarantees are formally proven.
In continuous-control simulations, GSS substantially outperforms tree-based planners on long horizons or achieves near-optimal performance. The work formalizes when shared futures can avoid the exponential horizon dependence of tree-shaped sparse sampling, supporting no-branching graph planning as a complementary design principle for online control.