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

• URL: http://arxiv.org/abs/2604.01352v1
• Date: Wed, 01 Apr 2026 20:06:29 GMT
• Title: Open-loop POMDP Simplification and Safe Skipping of Replanning with Formal Performance Guarantees
• Abstract summary: Partially Observable Markov Decision Processes (POMDPs) provide a principled mathematical framework for decision-making under uncertainty.<n>The exact solution to POMDPs is computationally intractable.<n>We introduce a novel framework for adaptive open-loop simplification with formal performance guarantees.
• Score: 9.578783083599621
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Conditional Timed Partial Orders: An Expressive and Interpretable Framework for Robot Task Specification and Planning [9.370068250965433]
  Conditional TPOs (cTPOs) provide an interpretable framework for robot task specification with planning algorithms based on mixed-integer linear programming (MILP)<n>We show that planning for cTPOs also reduces to an MILP problem; however, the added expressivity results in significantly larger MILPs that can become computationally intractable.<n>We propose a decomposition algorithm that partitions a cTPO into smaller sub-TPOs, yielding a sequence of smaller MILP problems.
  arXiv  Detail & Related papers  (2026-09-07T19:18:17Z)
• Accelerated Online Risk-Averse Policy Evaluation in POMDPs with Theoretical Guarantees and Novel CVaR Bounds [9.269394037577177]
  This work introduces a theoretical framework for accelerating Conditional Value-at-Risk evaluation in partially observable domains.<n>We establish upper and lower bounds on the CVaR value function computable from a simplified belief-MDP.<n>We develop estimators for these bounds within a particle-belief MDP framework with probabilistic guarantees.
  arXiv  Detail & Related papers  (2026-02-26T15:01:40Z)
• Interaction-Grounded Learning for Contextual Markov Decision Processes with Personalized Feedback [59.287761696290865]
  We propose a computationally efficient algorithm that achieves a sublinear regret guarantee for contextual episodic Markov Decision Processes (MDPs) with personalized feedback.<n>We demonstrate the effectiveness of our method in learning personalized objectives from multi-turn interactions through experiments on both a synthetic episodic MDP and a real-world user booking dataset.
  arXiv  Detail & Related papers  (2026-02-09T06:29:54Z)
• Constrained and Robust Policy Synthesis with Satisfiability-Modulo-Probabilistic-Model-Checking [4.064849471241967]
  This paper contributes the first approach to effectively compute robust policies subject to arbitrary structural constraints.<n> Experiments on a few hundred benchmarks demonstrate the feasibility for constrained and robust policy synthesis.
  arXiv  Detail & Related papers  (2025-11-11T10:28:42Z)
• Self-Guided Process Reward Optimization with Redefined Step-wise Advantage for Process Reinforcement Learning [48.426139299991604]
  We present textbfSPRO, a novel framework that enables process-aware RL through two key innovations.<n>SPRO outperforms vaniila GRPO with 3.4x higher training efficiency and a 17.5% test accuracy improvement.<n> Notably, SPRO incurs no additional computational overhead compared to outcome-supervised RL methods such as GRPO, which benefit industrial implementation.
  arXiv  Detail & Related papers  (2025-07-02T10:05:14Z)
• Finite-Sample-Based Reachability for Safe Control with Gaussian Process Dynamics [35.79393879150088]
  We present a sampling-based framework that efficiently propagates the model's uncertainty while avoiding conservatism.<n>We show that our method highlights accurate reachable set over-approximation and safe closed-loop performance.
  arXiv  Detail & Related papers  (2025-05-12T14:20:20Z)
• Non-stationary Reinforcement Learning under General Function Approximation [60.430936031067006]
  We first propose a new complexity metric called dynamic Bellman Eluder (DBE) dimension for non-stationary MDPs. Based on the proposed complexity metric, we propose a novel confidence-set based model-free algorithm called SW-OPEA. We show that SW-OPEA is provably efficient as long as the variation budget is not significantly large.
  arXiv  Detail & Related papers  (2023-06-01T16:19:37Z)
• Making Linear MDPs Practical via Contrastive Representation Learning [101.75885788118131]
  It is common to address the curse of dimensionality in Markov decision processes (MDPs) by exploiting low-rank representations. We consider an alternative definition of linear MDPs that automatically ensures normalization while allowing efficient representation learning. We demonstrate superior performance over existing state-of-the-art model-based and model-free algorithms on several benchmarks.
  arXiv  Detail & Related papers  (2022-07-14T18:18:02Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  We propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF. We extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver.
  arXiv  Detail & Related papers  (2020-12-04T15:36:29Z)
• Oracle-Efficient Regret Minimization in Factored MDPs with Unknown Structure [57.90236104782219]
  We study regret in non-episodic factored Markov decision processes (FMDPs) All existing algorithms make the strong assumption that the factored structure of the FMDP is known to the learner in advance. We provide the first algorithm that learns the structure of the FMDP while minimizing the regret.
  arXiv  Detail & Related papers  (2020-09-13T12:30:35Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• Formal Controller Synthesis for Continuous-Space MDPs via Model-Free Reinforcement Learning [1.0928470926399565]
  A novel reinforcement learning scheme to synthesize policies for continuous-space Markov decision processes (MDPs) is proposed. A key contribution of the paper is to leverage the classical convergence results for reinforcement learning on finite MDPs. We present a novel potential-based reward shaping technique to produce dense rewards to speed up learning.
  arXiv  Detail & Related papers  (2020-03-02T08:29:36Z)

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.