Open-loop POMDP Simplification and Safe Skipping of Replanning with Formal Performance Guarantees

Da Kong; Vadim Indelman

cs.ROApr 1, 2026

Open-loop POMDP Simplification and Safe Skipping of Replanning with Formal Performance Guarantees

Authors: Da Kong, Vadim Indelman

Organizations: Technion - Israel Institute of Technology

Abstract

Partially Observable Markov Decision Processes (POMDPs) provide a principled mathematical framework for decision-making under uncertainty. However, the exact solution to POMDPs is computationally intractable. In this paper, we address the computational intractability by introducing a novel framework for adaptive open-loop simplification with formal performance guarantees. Our method adaptively interleaves open-loop and closed-loop planning via a topology-based belief tree, enabling a significant reduction in planning complexity. The key contribution lies in the derivation of efficiently computable bounds which provide formal guarantees and can be used to ensure that our simplification can identify the immediate optimal action of the original POMDP problem. Our framework therefore provides computationally tractable performance guarantees for macro-actions within POMDPs. Furthermore, we propose a novel framework for safely skipping replanning during execution, supported by theoretical guarantees on multi-step open-loop action sequences. To the best of our knowledge, this framework is the first to address skipping replanning with formal performance guarantees. Practical online solvers for our proposed simplification are developed, including a sampling-based solver and an anytime solver. Empirical results demonstrate substantial computational speedups while maintaining provable performance guarantees, advancing the tractability and efficiency of POMDP planning.

Figures & tables

Figure 1: A hybrid belief tree demonstrating the computational advantage of open-loop planning. The left branch employs open-loop action sequences, while the right branch utilizes traditional closed-loop planning.

Panel of Figure 2 — Figure 2: Illustration of two cases for performance guarantees: (a) overlapping bounds necessitating topology refinement, and (b) non-overlapping bounds allowing for optimal action determination.

Figure 3: The process of skipping replanning based on the allowed observation set

\bar{\mathcal{Z}}_{1}

. The agent executes the action

a^{*}_{0}

and checks if the observation

z_{1}

belongs to the set

\bar{\mathcal{Z}}_{1}

. If it does, the agent skips replanning; otherwise, it triggers replanning. The process to skip replanning with performance guarantee is shown in dotted lines, which can be conducted in parallel with the execution of action and observation, thus reducing the replanning overhead.

Figure 4: Distribution of estimated bounds. The upper and lower bounds are computed using our proposed method with open-loop simplification, AT-SparsePFT. The yellow triangle denotes the

Q

-value estimated by the standard SparsePFT.

Method	Returns	Runtime (s)	Speedup Ratio
SparsePFT	$12.64$	$345.9$	$1.0\times$
AT-SparsePFT (ours)	$12.50$	$\mathbf{20.66}$	$\mathbf{16.7\times}$

Table 1: Cumulative rewards and runtime of the baseline SparsePFT method and our proposed method, AT-SparsePFT. The speedup ratio is computed as the ratio of baseline to proposed runtime. Results are averaged over 100 independent 10-step simulations.

Time Budget	50ms	80ms	100ms	300ms	500ms	1.0s
POMCP	$6.988\pm 0.352$	$7.082\pm 0.270$	$7.030\pm 0.165$	$7.14\pm 0.229$	$7.15\pm 0.284$	$7.347\pm 0.277$
AT-POMCP(ours)	$\textbf{7.533}\pm 0.481$	$\textbf{7.566}\pm 0.533$	$\textbf{7.698}\pm 0.494$	$\textbf{7.825}\pm 0.655$	$\textbf{7.883}\pm 0.353$	$\textbf{8.018}\pm 1.526$
Improvement	7.80%	6.84%	9.52%	9.57%	10.24%	9.12%

Table 2: Cumulative reward comparison across computational budgets. Results are reported as mean

\pm

standard deviation over 20 trials.

Method	Returns	Runtime (s)	Speedup Ratio
POMCP	$7.456\pm 0.276$	$2.5$	$1.0\times$
AT-POMCP(ours)	$7.533\pm 0.481$	$\mathbf{0.05}$	$\mathbf{50\times}$

Table 3: Runtime comparison between the baseline POMCP and the proposed AT-POMCP when operating at the same performance level (average cumulative reward). The speedup ratio is computed as the baseline runtime divided by the proposed method runtime; returns are averaged over 20 independent trials.

Panel of Figure 5 — Figure 5: Skipping replanning with guarantees: (a) Planning with the proposed adaptive open-loop simplification at $t=0$ . It shows $ub(\tau,b_{0},a_{0})$ and $lb(\tau,b_{0},a_{0})$ for different $a_{0}$ . $a_{0}^{*}$ is identified. (b) Bounding $Q^{*}(b_{1},a_{1})$ at $t=0$ for any posterior belief $b_{1}$ that corresponds to future observations in $\bar{\mathcal{Z}}_{1}$ . The figure shows $\bar{ub}^{1}$ and $\bar{lb}^{1}$ defined in Theorem 5.2 . Here $a_{1}^{*}$ can be provably determined at $t=0$ for all realizations of the future observation $z_{1}$ in $\bar{\mathcal{Z}}_{1}$ .

Method	Returns	Skipping Replanning Ratio
AT-SparsePFT w/o Skipping Replanning	$235.7$	$0\%$
AT-SparsePFT w/ Skipping Replanning	$231.3$	$\mathbf{24\%}$

Table 4: Comparison of cumulative rewards and the ratio of steps where replanning can be safely skipped with performance guarantees. Results are averaged over 100 independent 5-step simulations.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 6: Beacon navigation problem.

Figure 7: Cumulative rewards at each step for the baseline, SparsePFT, and our proposed method, AT-SparsePFT. Results are averaged over

100

simulations.

Method	Returns	Runtime (s)	Speedup Ratio
Baseline (SparsePFT)	$12.64\pm 6.02$	$345.9\pm 6.4$	$1.0\times$
AT-SparsePFT	$12.50\pm 5.42$	$\mathbf{20.66\pm 5.0}$	$\mathbf{16.7\times}$

Appendix

Table 5: Cumulative rewards and runtime of the baseline SparsePFT method and our proposed method. The speedup ratio represents the ratio of baseline runtime to proposed method runtime. Results report mean values and standard deviations (std) computed over 100 independent 10-step simulation trials.

Figure 8: cumulative reward comparison between the baseline POMCP and the proposed method. The plot shows mean cumulative rewards for budgets ranging from

50\,\text{ms}

1\,\text{s}

, highlighting consistent performance gains for the proposed method.

Method	Planning Time (s)	Replanning Time (s)	Execution Time (s)	Total Time (s)
Skip Replanning (Ours)	220.64	80.70	150	230.70
Baseline (Always Replan)	90.58	90.58	150	240.58

Appendix

Table 6: Runtime comparison between our replanning skip method and baseline approach over 100 trials. Execution and observation time per time-step:

1.5

Partially Observable Markov Decision Processes

Partially Observable Markov Decision Processes study sequential decisions when agents must act from incomplete, noisy observations of hidden states.

See all 88 papers

Think Fast and Far: Long-Horizon Online POMDP Planning via Rapid State Sampling
Jun 3, 2026Yuanchu Liang, Edward Kim, J. Arden Knoll +4Belief-Space Planning Partially Observable Markov Decision Processes
Australian National University, Canberra ACT 2601, Australia. · Rice University, Houston TX 77005, USA.
Leveraging the Value of Information in POMDP Planning
Apr 1, 2026Zakariya Laouar, Qi Heng Ho, Zachary SunbergPartially Observable Markov Decision Processes Belief-Space Planning
Department of Aerospace Engineering Sciences, University of Colorado Boulder · Kevin T. Crofton Department of Aerospace and Ocean Engineering, Virginia Tech
POMDPPlanners: Open-Source Package for POMDP Planning
Feb 24, 2026Yaacov Pariente, Vadim IndelmanPartially Observable Markov Decision Processes Decision-Making under Uncertainty
Faculty of Mathematics, Technion - Israel Institute of Technology, Haifa 3200003, Israel · Stephen B. Klein Faculty of Aerospace Engineering, Faculty of Data and Decision Sciences, Technion - Israel Institute of Technology, Haifa 3200003, Israel

Jun 3, 2026J/K move · Enter open · S save

Think Fast and Far: Long-Horizon Online POMDP Planning via Rapid State Sampling

Yuanchu Liang, Edward Kim, J. Arden Knoll, Wil Thomason+3

Australian National University, Canberra ACT 2601, Australia. · Rice University, Houston TX 77005, USA.

Belief-Space Planning Partially Observable Markov Decision Processes

Open paper AskPDF arXiv

Partially Observable Markov Decision Processes (POMDPs) are a general and principled framework for motion planning under uncertainty. Despite tremendous improvement in the scalability of POMDP solvers, long-horizon POMDPs remain difficult to solve. To alleviate the difficulty, this paper proposes a new approximate online POMDP solver, called Reference-Based Online POMDP Planning via Rapid State Space Sampling (ROP-RAS3). ROP-RAS3 uses novel extremely fast sampling-based motion planning techniques to sample the state space and generate a diverse set of macro actions online, which are then used to bias belief-space sampling and infer high-quality policies without requiring exhaustive enumeration of the action space -- a fundamental constraint for modern online POMDP solvers. ROP-RAS3 converges to a near-optimal reference-based solution at a rate that depends on the number of sampled actions, rather than the size of the action space. ROP-RAS3 is evaluated on various long-horizon POMDPs with up to 3000 lookahead steps and 35-dimensional state spaces, where the state, action and observation spaces can be continuous, discrete, or a hybrid of discrete and continuous. Although the reference-based optimal solution may not be the same as the optimal POMDP solution, empirical results indicate that in all of these problems, in terms of success rate, ROP-RAS3 outperforms other state-of-the-art methods by up to multiple folds. We also demonstrate the capability of our approach on a physical robot demonstration. This work extends the theory and empirical results of our ISRR24 paper. Code can be found at https://github.com/RDLLab/ROPRAS3.

Abstract

Partially Observable Markov Decision Processes

Explore similar work

Think Fast and Far: Long-Horizon Online POMDP Planning via Rapid State Sampling

Leveraging the Value of Information in POMDP Planning

POMDPPlanners: Open-Source Package for POMDP Planning