我们研究有限时域、状态、动作、观测空间均有限的部分可观测马尔可夫决策过程（POMDP）。在此设置下，精确和近似规划已知是计算上困难的，因而已有工作在寻找能简化规划的自然假设。最近的工作[Golowich et al., 2022]在满足 $\ell_1$-可观测性的 POMDP 上给出了准多项式时间的近似规划算法，且对转移动力学没有额外假设。本文在此思路下，对每个固定的 $\rho>0$，提出了针对 $\rho$-可解码 POMDP 的准多项式时间近似规划算法。我们证明，可解码性由 $\ell_1$-和 $\ell_2$-可观测性共同蕴含，且严格弱于可观测性。进一步，我们展示最优可解码常数可以在多项式时间内求得，而最优 $\ell_1$-可观测性常数在最坏情况下是 NP 难的。我们还指出，基于 [Golowich et al., 2022] 的快速滤波遗忘保证不能直接从 $\ell_1$-可观测性推广到常数 $\ell_2$-可观测性。因此，可解码性是一种易于检验、统一的假设，使得在 POMDP 上实现准多项式时间近似规划成为可能。
点评：可解码性提供了比传统可观测性更宽松的条件，同时保持可计算性，为大规模 POMDP 规划提供了新的理论工具。