Research map / Probabilistic and scientific modeling / Molecules and proteins

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

NeurIPS 2026 · Probabilistic and scientific modeling › Molecules and proteins · approach: Machine learning for physical simulation · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes Graph Sparse Sampling, an online continuous-MDP planner that shares sampled next-state layers across candidate actions (branch-free graph with SNIS/smoothed SNIS backups), with finite-sample guarantees polynomial in horizon and experiments vs DPW/VPW on continuous control.

Problem

Online planning in continuous MDPs with generative simulators: tree-based sparse sampling needs budgets exponential in lookahead depth, and tree planners struggle to decide where to search in infinite branching.

Approach

Replace per-action sampled subtrees with a shared layered graph: sample one successor state layer per depth, evaluate all candidate actions against it via self-normalized importance sampling (or KDE/NN) backups, and use smoothed transition densities to handle singular low-rank simulators; proves horizon-polynomial error bounds for this graph.

Key results

• On Rotating DDI, GSS achieves better or comparable performance to DPW/VPW at all tested time budgets, while LQR and LQG degrade sharply from alpha=0.9 onward.
• On Lunar Lander, GSS reaches high discounted return by the medium budget and stays stable as budgets grow, whereas tree planners' mean performance declines at longer time budgets.
• Theory: under bounded d_infinity overlap, sample complexity is N_GSS = O~(R_max^2 (d_max)^2 T^5 / eps^2), polynomial in horizon versus exponential for Sparse Sampling.

Surprising findings

• Tree planners' mean performance on Lunar Lander declines as time budgets increase, despite more compute.

Limitations

• GSS is proposal-limited: poor action or state proposals waste computation in wrong regions.
• Guarantees rely on overlap (bounded density ratio), action-coverage and smoothing-bias assumptions; the bounds are not tight.
• Analysis is for fully specified finite-horizon settings; partially observable and anytime settings are left to future work.

Experimental setup

Benchmarks: Rotating 4D-Double-Integrator Lunar Lander Reacher

Metrics: discounted return undiscounted return planning runtime

Baselines: DPW VPW LQR feedback LQG/Riccati PD controller

Builds on: Sparse Sampling Monte Carlo Tree Search Double Progressive Widening Weighted Stochastic Mesh Voronoi optimistic optimization

Closest papers by meaning

• Graph-Based Stochastic-Power-UCT: Monte-Carlo Graph Search with Power Mean Estimation (NeurIPS 2026 · similarity 0.88)
• Provably Efficient Long-Horizon Exploration in Monte Carlo Tree Search through State Occupancy Regularization (ICML 2024 · similarity 0.88)
• Tree-Guided Diffusion Planner (NeurIPS 2025 · similarity 0.87)
• Resisting Stochastic Risks in Diffusion Planners with the Trajectory Aggregation Tree (ICML 2024 · similarity 0.87)
• Power Mean Estimation in Stochastic Continuous Monte-Carlo Tree Search (ICML 2025 · similarity 0.87)
• Compositional Monte Carlo Tree Diffusion for Extendable Planning (NeurIPS 2025 · similarity 0.86)