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

Source: arXiv:2607.05359 · Published 2026-07-06 · By Idan Lev-Yehudi, Vadim Indelman

TL;DR

This paper addresses the fundamental challenge of planning under uncertainty in continuous state and action spaces, which is computationally difficult due to the exponential growth of the search tree with planning horizon depth. Existing tree-based methods like Monte Carlo Tree Search (MCTS) struggle because they must sample independent successor states for each candidate action, making long horizon planning infeasible. The authors propose Graph Sparse Sampling (GSS), a novel, branch-free online planning algorithm that constructs a layered graph by sharing sampled successor states across many candidate actions rather than per action. This enables massive batch parallelism on GPUs and avoids the exponential dependence on horizon depth under regularity and overlap conditions. Theoretical analysis provides finite-sample high-probability error guarantees for value estimation with polynomial dependence on the horizon, using self-normalized importance sampling backups and smoothing techniques for low-rank transition models. Empirical evaluation on three continuous control benchmarks—Rotating 4D Double Integrator, Lunar Lander, and Reacher—shows GSS consistently outperforms or matches tree-based baselines like Double Progressive Widening (DPW) and Voronoi Progressive Widening (VPW) at comparable or lower planning runtimes, especially excelling for longer horizons and higher-dimensional states. The results demonstrate that the no-branching layered graph structure combined with heuristic proposals yields scalable online planning with better sample efficiency and GPU utilization than prior tree planners.

Key findings

• GSS achieves polynomial sample complexity in planning horizon T under density-ratio overlap and action-coverage assumptions versus exponential in T for sparse sampling (Corollary 4.3).
• In Rotating DDI domain, GSS outperforms DPW and VPW for all tested time budgets, maintaining robust performance as rotation parameter α increases, unlike tree methods which degrade sharply (Fig 2a).
• In Lunar Lander, GSS achieves higher discounted returns than DPW and VPW at medium to high planning budgets, while DPW/VPW performance declines as runtime increases (Fig 2b).
• In Reacher control with 10D state and 2D action space, GSS consistently improves over a PD controller baseline, with return improving as state layer size and action budgets increase (Fig 2c).
• Graph backup using self-normalized importance sampling (SNIS) with smoothed kernels theoretically guarantees controlled error with polynomial horizon dependence (Theorem 1, Corollary 4.2).
• GSS enables large, fixed-shape batched graph construction for efficient GPU parallelism, achieving up to 512 states per layer and 64 actions per state in experiments.
• Action proposal heuristics ensure sampled candidate action sets are max-close to optimal with quantifiable bounds on suboptimality via coverage and Hölder continuity (Claim 2).
• GSS achieves similar or better performance than computationally heavier tree-based planners in continuous MDPs with stochastic/deterministic transitions.

Methodology — deep read

The authors formulate the problem as finite-horizon discounted Markov Decision Processes (MDPs) with continuous, possibly high-dimensional state and action spaces. Planning aims to find near-optimal root actions from an initial state using only a black-box generative model. The key challenge is that standard tree search methods must sample separate successors per state-action pair, causing exponential sample complexity in horizon length T. GSS instead samples a layered graph of states shared across all candidate actions at each layer, decoupling state sampling from action evaluation. The methodology has two main phases: (1) Forward pass where at each layer t, for each sampled state si_t, Kt actions are drawn iid from an action proposal distribution q^a_t(·|si_t). Then a common state proposal density q^s_t fitted on prior samples is used to sample C_{t+1} next states shared for all actions. (2) Backward pass where generalized graph backups propagate value estimates from the terminal layer back to the root. The graph backup operation estimates Q-values combining the rewards and bootstrapped next-state values weighted via importance sampling or its smoothed variants.

Theoretical analysis assumes controlled graph backup operators satisfying stability and bounded local errors with high probability. Under action proposal coverage conditions ensuring sampled actions are "max-close" to optimal with a radius Γ_t, and smoothness (Hölder continuity) assumptions on Q-functions, the authors derive finite-sample concentration inequalities bounding deviations of estimated Q-values from true optima with polynomial dependence on horizon T. They extend to settings with low-rank generative simulators where transition densities are singular by introducing smoothing kernels on the transition model and proving bounded smoothing bias.

Empirically, GSS is implemented in JAX for GPU batched processing, using domain-specific heuristic proposals for states and actions, leveraging rollout policies for tail value initialization. Three continuous control benchmarks were tested: Rotating 4D Double Integrator (8D state, 4D action) tests robustness to mismatched rollout guides; Lunar Lander (6D state, continuous 3D actions) highlights smoothed SNIS backups and handling singular transitions; Reacher-v5 (10D state, 2D actions) demonstrates scaling to higher dimensional deterministic control. In each case, GSS is compared to tree-based baselines DPW and VPW using the same underlying rollout policies and domain knowledge. Performance metrics focus on discounted or undiscounted returns averaged over multiple runs, with error bars from standard error across seeds. Plots report results across a range of offline planning runtimes to reveal scalability and anytime behavior.

Overall, the methodology systematically replaces branching tree searches with fixed-shape layered graphs, enabling large batched samples shared across candidate actions for improved sample efficiency and parallelism. The analysis rigorously quantifies when this sharing can break the classical exponential horizon dependence in stochastic continuous MDPs. Empirical evaluation confirms practical gains under varied continuous control challenges.

Technical innovations

• Introduction of the Graph Sparse Sampling (GSS) algorithm that constructs branch-free layered planning graphs by sharing successor state samples across all candidate actions at each layer, enabling massive GPU-friendly batch processing.
• Use of self-normalized importance sampling (SNIS) with smoothed kernel densities for graph backups that yield finite-sample performance guarantees with polynomial dependence on planning horizon, even in low-rank/degenerate transition models.
• Formal definition and analysis of max-close sampled action sets that quantify suboptimality due to sampled discrete candidate actions in continuous spaces via proposal coverage and Hölder continuity assumptions.
• A graph recursive concentration inequality (Theorem 1) that converts single-node backup concentration bounds to overall planning graph guarantees with explicit error and failure probability bounds.
• Integration of heuristic action and state proposals tuned from rollout policies to focus expensive sampling budgets on promising regions, balancing exploration and sample reuse.

Baselines vs proposed

• DPW (Double Progressive Widening): returns up to ~40 in Rotating DDI vs GSS: returns up to ~50 (Fig 2a)
• VPW (Voronoi Progressive Widening): returns up to ~40 in Rotating DDI vs GSS: returns up to ~50 (Fig 2a)
• DPW: peak discounted return ~60 in Lunar Lander vs GSS: peak discounted return ~80 (Fig 2b)
• VPW: peak discounted return ~60 in Lunar Lander vs GSS: peak discounted return ~80 (Fig 2b)
• PD baseline controller: return ~5-6 in Reacher vs GSS: return ~7-9 (Fig 2c)

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2607.05359.

Fig 1: GSS builds a layered planning graph from the root state s0. Sampled states are shown as

Fig 2 (page 3).

Fig 3 (page 3).

Fig 4 (page 3).

Fig 5 (page 3).

Fig 6 (page 3).

Fig 7 (page 3).

Fig 8 (page 3).

Limitations

• GSS performance critically depends on quality of action and state proposal distributions; poor proposals can concentrate computation in suboptimal regions.
• Theoretical guarantees require assumptions like density-ratio overlap and max-close action sets which may be hard to verify or satisfy fully in complex domains.
• Experiments are limited to three specific continuous-control benchmarks; more varied or real-world robotics domains were not tested.
• Backup operators rely on self-normalized importance sampling which requires evaluating or approximating transition densities; samples from fully black-box simulators without density access may pose issues.
• GSS as presented is a fixed-horizon offline planner; extensions to adaptive anytime planning or partially observable settings remain future work.
• Implementation tradeoffs between action vs state sampling budgets and smoothing bandwidths require careful tuning and domain expertise.

Open questions / follow-ons

• How to learn or adapt the action and state proposal distributions online to improve GSS performance in unknown or changing environments?
• Can GSS be extended to partially observable MDPs or belief-space planning with similar polynomial horizon sample complexity?
• What are practical approaches to relax the density-ratio overlap or max-close assumptions in high-dimensional continuous domains?
• How to integrate learned approximations into GSS backups (e.g., neural value functions) while preserving theoretical guarantees?

Why it matters for bot defense

While this paper primarily targets continuous control and autonomous planning, the core idea of sharing sampled future states across multiple candidate actions to reduce exponential branching could inspire bot-defense frameworks handling continuous or high-dimensional decision spaces. Captcha systems relying on adaptive challenge generation or sequential decision processes might benefit from batch sampling and shared rollout reuse to improve response evaluations under latency constraints. Moreover, the methodology's emphasis on GPU-friendly batched operations could inform scalable evaluation architectures for real-time interaction. Security practitioners considering online adaptive challenge planners may find the polynomial horizon scaling guarantees helpful to design defenses robust to deeper multi-step attack attempts. However, direct application would require substantial adaptation to the discrete and adversarial nature of captcha challenge-response scenarios.

Cite

@article{arxiv2607_05359,
  title={ Graph Sparse Sampling: Breaking the Curse of the Horizon in Continuous MDP Planning },
  author={ Idan Lev-Yehudi and Vadim Indelman },
  journal={arXiv preprint arXiv:2607.05359},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.05359}
}

Read the full paper

• arXiv:2607.05359 (abstract)
• arXiv:2607.05359 (PDF)