Graph Sparse Sampling: Breaking the Curse of the Horizon in Continuous MDP Planning

• URL: http://arxiv.org/abs/2607.05359v1
• Date: Mon, 06 Jul 2026 17:36:28 GMT
• Title: Graph Sparse Sampling: Breaking the Curse of the Horizon in Continuous MDP Planning
• Abstract summary: Planning under uncertainty in continuous domains is essential for autonomous systems.<n>Tree-based search methods such as Monte Carlo Tree Search (MCTS) remain popular.<n>We propose Graph Sparse Sampling (GSS), an online planning algorithm that shares sampled futures across many candidate decisions.
• Score: 10.558515062670692
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Power Mean Estimation in Stochastic Continuous Monte Carlo Tree Search [0.6903929927172916]
  We propose a novel Monte Carlo Tree Search (MCTS) algorithm for continuous Markov Decision Processes (MDPs)<n>Our theoretical analysis establishes that Algname converges at a rate of $mathcalO(n-)$, $in (0,1/2)$, where ( n) is the number of visited trajectories, thereby extending the non-asymptotic convergence guarantees.
  arXiv  Detail & Related papers  (2026-09-06T09:04:39Z)
• Dispersive Forward Tree Search for Optimal Control: Coverage, Complexity, and Computation [15.03677748041754]
  This paper develops a propagation-based kinodynamic planner with deterministic finite-sample near-optimality guarantees.<n>We show that a forward tree of locally dispersive control commands contains a near-optimal trajectory at a certified tree size.<n>We implement the resulting search algorithm, Dispersive Forward Tree search (DFT*), as breadth-first expansion of the forward tree.
  arXiv  Detail & Related papers  (2026-08-26T18:46:17Z)
• Optimizing Trajectory-Trees in Belief Space: An Application from Model Predictive Control to Task and Motion Planning [12.236092368066332]
  This paper explores the benefits of computing arborescent trajectories (trajectory-trees) instead of commonly used sequential trajectories for partially observable robotic planning problems.<n>Unlike sequential trajectories, which model a single forward evolution of the system, trajectory-trees capture multiple possible contingencies.
  arXiv  Detail & Related papers  (2026-05-03T13:06:20Z)
• SGA-MCTS: Decoupling Planning from Execution via Training-Free Atomic Experience Retrieval [74.1918709002557]
  We introduce textbfSGA-MCTS, a framework that casts LLM planning as non-parametric retrieval.<n>Online, a retrieval-augmented agent employs a hybrid symbolic-semantic mechanism to fetch relevant State-Goal-Action atoms.<n>By effectively amortizing the heavy computational cost of search, SGA-MCTS achieves System 2 reasoning depth at System 1 inference speeds, rendering autonomous planning both scalable and real-time feasible.
  arXiv  Detail & Related papers  (2026-04-16T07:22:36Z)
• Decoupling Geometric Planning and Execution in Scalable Multi-Agent Path Finding [44.79409119345322]
  Multi-Agent Path Finding (MAPF) requires collision-free trajectories for multiple agents on a shared graph.<n>We propose a hybrid prioritized framework that separates geometric planning from execution-time conflict resolution.
  arXiv  Detail & Related papers  (2026-03-11T11:04:54Z)
• Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach [57.788675205519986]
  We learn high-quality traces from POMDP executions generated by any solver. We exploit data- and time-efficient Indu Logic Programming (ILP) to generate interpretable belief-based policy specifications. We show that learneds expressed in Answer Set Programming (ASP) yield performance superior to neural networks and similar to optimal handcrafted task-specifics within lower computational time.
  arXiv  Detail & Related papers  (2024-02-29T15:36:01Z)
• Tree-Planner: Efficient Close-loop Task Planning with Large Language Models [63.06270302774049]
  Tree-Planner reframes task planning with Large Language Models into three distinct phases. Tree-Planner achieves state-of-the-art performance while maintaining high efficiency.
  arXiv  Detail & Related papers  (2023-10-12T17:59:50Z)
• Continuous Monte Carlo Graph Search [61.11769232283621]
  Continuous Monte Carlo Graph Search ( CMCGS) is an extension of Monte Carlo Tree Search (MCTS) to online planning. CMCGS takes advantage of the insight that, during planning, sharing the same action policy between several states can yield high performance. It can be scaled up through parallelization, and it outperforms the Cross-Entropy Method (CEM) in continuous control with learned dynamics models.
  arXiv  Detail & Related papers  (2022-10-04T07:34:06Z)
• Visual Learning-based Planning for Continuous High-Dimensional POMDPs [81.16442127503517]
  Visual Tree Search (VTS) is a learning and planning procedure that combines generative models learned offline with online model-based POMDP planning. VTS bridges offline model training and online planning by utilizing a set of deep generative observation models to predict and evaluate the likelihood of image observations in a Monte Carlo tree search planner. We show that VTS is robust to different observation noises and, since it utilizes online, model-based planning, can adapt to different reward structures without the need to re-train.
  arXiv  Detail & Related papers  (2021-12-17T11:53:31Z)
• Efficient and Stable Graph Scattering Transforms via Pruning [86.76336979318681]
  Graph scattering transforms ( GSTs) offer training-free deep GCN models that extract features from graph data. The price paid by GSTs is exponential complexity in space and time that increases with the number of layers. The present work addresses the complexity limitation of GSTs by introducing an efficient so-termed pruned (p) GST approach.
  arXiv  Detail & Related papers  (2020-01-27T16:05:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.