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

CardsList
  1. Leveraging the Value of Information in POMDP Planning

    Apr 1, 2026Zakariya Laouar, Qi Heng Ho, Zachary SunbergPartially Observable Markov Decision ProcessesBelief-Space Planning

  2. Scaling Observation-aware Planning in Uncertain Domains

    May 21, 2026Adrian Zvizdenco, Arthur Conrado Veiga Bosquetti, Alberto Lluch Lafuente +1Partially Observable Markov Decision Processes