cs.LGNov 6, 2026

Quasipolynomial-Time Planning for Decodable POMDPs

Authors: Oliver Dobson, Varun Jog, Chun Hei Michael Shiu

Organizations: Department of Pure Mathematics and Mathematical Statistics, University of Cambridge · Department of Electrical and Computer Engineering, University of British Columbia

Abstract

We study planning for finite-horizon partially observable Markov decision processes (POMDPs) with finite state, action, and observation spaces. Both exact and approximate planning are known to be computationally hard in this setting, so prior work has explored natural assumptions that make planning easier. Recent work [Golowich et al., 2022] gave quasipolynomial-time approximate planning algorithms for observable POMDPs. These are POMDPs whose observation channels satisfy an ℓ1\ell_1-observability condition, but notably, no assumptions are required on the transition dynamics. In a similar vein, for every fixed ρ>0ρ>0, we give quasipolynomial-time approximate planning algorithms for ρρ-decodable POMDPs. We show that decodability is implied by both ℓ1\ell_1- and ℓ2\ell_2-observability and is strictly weaker than observability. Moreover, we show that the optimal decodability constant can be computed in polynomial time, whereas computing the optimal ℓ1\ell_1-observability constant is NP-hard in the worst case. We also show that the fast filter-forgetting guarantee underlying the approach of [Golowich et al., 2022] does not extend directly from ℓ1\ell_1-observability to constant ℓ2\ell_2-observability. Thus, decodability is an easy-to-check, unifying assumption under which quasipolynomial-time approximate planning for POMDPs is possible.

Explore similar work

Apr 1, 2026

Leveraging the Value of Information in POMDP Planning

Partially observable Markov decision processes (POMDPs) offer a principled formalism for planning under state and transition uncertainty. Despite advances made towards solving large POMDPs, obtaining performant policies under limited planning time remains a major challenge due to the curse of dimensionality and the curse of history. For many POMDP problems, the value of information (VOI) - the expected performance gain from reasoning about observations - varies over the belief space. We introduce a dynamic programming framework that exploits this structure by conditionally processing observations based on the value of information at each belief. Building on this framework, we propose Value of Information Monte Carlo planning (VOIMCP), a Monte Carlo Tree Search algorithm that allocates computational effort more efficiently by selectively disregarding observation information when the VOI is low, avoiding unnecessary branching of observations. We provide theoretical guarantees on the near-optimality of our VOI reasoning framework and derive non-asymptotic convergence bounds for VOIMCP. Simulation evaluations demonstrate that VOIMCP outperforms baselines on several POMDP benchmarks.
Apr 1, 2026

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

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.
May 21, 2026

Scaling Observation-aware Planning in Uncertain Domains

Deciding which sensing capabilities to deploy on an agent in uncertain domains is a fundamental engineering challenge, in which one balances task achievability against the high costs of hardware and processing. This problem has previously been formalized as the Optimal Observability Problem (OOP), based on the well-known Partially Observable Markov Decision Process (POMDP) model for decision-making. This work studies (sub-)symbolic techniques to scale solving of decidable fragments of the OOP, namely the Sensor Selection Problem (SSP) and the Positional Observability Problem (POP). Besides improving the original approach based on parameter synthesis, we develop a new solving method that identifies sensible observation functions via decomposition of POMDPs, improving performance by 3 and 5 orders of magnitude for instance size and runtime, respectively.