{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-06","reactions":{}}