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 的新复杂度结果。
正文 · AI 翻译
摘要：多环境 POMDP（ME-POMDP）通过编码一组有限的可能环境来推广 POMDP，从而刻画模型不确定性。ME-POMDP 的有限时域鲁棒奖励最大化问题要求给出一个在最坏环境下最大化奖励的策略，近期工作已证明该问题是 $\mathsf{PSPACE}$-完全的。我们通过确定哪些子类保持这种 $\mathsf{PSPACE}$-完全性，扩展了 ME-POMDP 的复杂性图景。具体而言，我们选取在单环境情形下可高效求解的 POMDP 子类，并研究这些类在扩展到多环境设定时的计算复杂性。我们首先利用某种混合封闭性条件，证明了多环境盲 MDP 和确定性 POMDP 的 $\mathsf{NP}$-完全性。随后，我们对一系列不满足该封闭性条件的子类证明了 $\mathsf{PSPACE}$-完全性，从而得到多观测 POMDP 的新复杂性结果。最后，我们证明了在时间相关马尔可夫策略或有限状态控制器下，众多 ME-POMDP 问题的实数存在理论（$\exists \mathbb{R}$）-完全性，而这些问题在标准 POMDP 下是 $\mathsf{NP}$-完全的。这些结果揭示了 POMDP 与 ME-POMDP 复杂性之间一种微妙的关系，该关系在很大程度上取决于所涉及的子类。
| 评论： | 45 页，9 幅图 |
| 主题： | 人工智能（cs.AI） |
| 引用为： | arXiv:2610.15010 [cs.AI] |
| （或 arXiv:2610.15010v1 [cs.AI] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2610.15010 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Caleb Probine [查看电子邮件]
[v1]
2026 年 10 月 10 日星期六 15:45:16 UTC（90 KB）
来源：arXiv cs.AI · arxiv.org