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
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-observability condition, but notably, no assumptions are required on the transition dynamics. In a similar vein, for every fixed ρ>0, we give quasipolynomial-time approximate planning algorithms for ρ-decodable POMDPs. We show that decodability is implied by both ℓ1- and ℓ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-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-observability to constant ℓ2-observability. Thus, decodability is an easy-to-check, unifying assumption under which quasipolynomial-time approximate planning for POMDPs is possible.
Department of Aerospace Engineering Sciences, University of Colorado Boulder · Kevin T. Crofton Department of Aerospace and Ocean Engineering, Virginia Tech