Graph Sparse Sampling: Breaking the Curse of the Horizon in Continuous MDP Planning
For autonomous systems requiring online planning in continuous domains, GSS provides a principled method to break the curse of horizon, enabling efficient long-horizon planning.
Graph Sparse Sampling (GSS) is proposed to overcome the exponential horizon dependence of tree-based planning in continuous MDPs by sharing sampled futures across decisions, achieving polynomial horizon dependence with finite-sample guarantees. In continuous-control simulations, GSS substantially outperforms tree-based planners on long horizons or achieves near-optimal performance.
Planning under uncertainty in continuous domains is essential for autonomous systems, yet computationally demanding. Tree-based search methods such as Monte Carlo Tree Search (MCTS) remain popular, but their branching structure can require sampling budgets that grow exponentially with lookahead depth in the worst case. From a tree perspective, continuous state or action spaces become especially challenging, since the planner must decide where to search in an infinite branching hierarchy. We propose Graph Sparse Sampling (GSS), an online planning algorithm that shares sampled futures across many candidate decisions, rather than sampling separate successors for each candidate action. This branch-free graph exposes large GPU-friendly batches, while using heuristics to focus computation. We prove finite-sample performance guarantees for GSS covering full-rank or low-rank generative simulators via smoothed backups, and discrete or sampled continuous action spaces. Under suitable overlap, regularity, and action-coverage conditions, these bounds have polynomial dependence on the planning horizon, formalizing when shared futures can avoid the exponential horizon dependence of tree-shaped sparse sampling. We demonstrate continuous-control simulations where GSS substantially outperforms tree-based planners on long horizons or achieves near-optimal performance, supporting no-branching graph planning as a complementary design principle for online control.