Graph Sparse Sampling: Breaking the Curse of the Horizon in Continuous-Domain Planning under Uncertainty

Summary

This paper introduces Graph Sparse Sampling (GSS), an online planning algorithm for continuous domains where decision-making under uncertainty is computationally expensive. Tree-search methods such as MCTS remain popular, but their branching structure requires, in the worst case, a sampling budget that grows exponentially with lookahead depth. GSS instead shares sampled futures across multiple candidate decisions rather than sampling independent successors for each candidate action. This branchless graph structure exposes large GPU-friendly batches while using heuristics to focus computation. The authors prove finite-sample performance guarantees: under suitable overlap, regularity, and action coverage conditions, these bounds depend only polynomially on the planning horizon, formalizing when sharing futures can avoid the exponential horizon dependence of tree-based sparse sampling. In continuous control simulations, GSS substantially outperforms tree-based planners over long horizons or achieves near-optimal performance. Preprint: arXiv:2607.05359.