Id: arxiv/2611.09778 Url: https://arxiv.org/abs/2611.09778 Tags: cs.LG, cs.DS, cs.IT, math.OC, stat.ML Score: 0 Title: Quasipolynomial-Time Planning for Decodable POMDPs Domain: cs.LG Source: arxiv Authors: Oliver Dobson, Varun Jog, Chun Hei Michael Shiu Reviews: 0 Subject: cs.LG Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-06 Page: https://delphi.science/r/arxiv/2611.09778 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 $\ell_1$-observability condition, but notably, no assumptions are required on the transition dynamics. In a similar…