arXiv cs.AI· Eline M. Bovy, Caleb Probine, Marnix Suilen, Ufuk Topcu, Nils Jansen·· 3 天前AI 评分12
POMDP 与多环境 POMDP 之间的复杂度差距
On the Complexity Gap Between POMDPs and Multi-Environment POMDPs
AI 导读
研究扩展了多环境 POMDP（ME-POMDP）的复杂度图谱，识别出哪些 POMDP 子类在扩展到多环境设定后仍保持 PSPACE 完全性。作者证明了多环境盲 MDP 和确定性 POMDP 的 NP 完全性，并为不满足混合封闭条件的子类证明了 PSPACE 完全性，还给出了多观测 POMDP 的新复杂度结果。
正文 · 原文
Abstract:Multi-environment POMDPs (ME-POMDPs) generalize POMDPs by encoding a finite set of possible environments, capturing model uncertainty. The finite-horizon robust reward maximization problem for a ME-POMDP asks for a policy that maximizes reward in the worst environment, and recent work has shown this problem to be $\mathsf{PSPACE}$-complete. We expand the complexity landscape of ME-POMDPs by identifying which subclasses retain this $\mathsf{PSPACE}$-completeness. In particular, we take subclasses of POMDPs that are tractable in the single-environment case, and investigate the computational complexity of these classes when extended to the multi-environment setting. We first prove the $\mathsf{NP}$-completeness of multi-environment blind MDPs and deterministic POMDPs using a certain closure-under-mixture condition. We then prove $\mathsf{PSPACE}$-completeness for a range of subclasses that do not satisfy that closure condition, yielding new complexity results for multi-observation POMDPs. Finally, we show existential theory of the reals ($\exists \mathbb{R}$)-completeness for numerous ME-POMDP problems under time-dependent Markovian policies or finite-state controllers that are $\mathsf{NP}$-complete for standard POMDPs. These results reveal a subtle relationship between POMDP and ME-POMDP complexity that depends heavily on the subclasses involved.
| Comments: | 45 pages, 9 figures |
| Subjects: | Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2610.15010 [cs.AI] |
| (or arXiv:2610.15010v1 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2610.15010 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Caleb Probine [view email]
[v1]
Sat, 10 Oct 2026 15:45:16 UTC (90 KB)
来源：arXiv cs.AI · arxiv.org