arXiv Artificial Intelligence· Eline M. Bovy, Caleb Probine, Marnix Suilen, Ufuk Topcu, Nils Jansen·· 19 小时前AI 评分12
POMDP 与多环境 POMDP 之间的复杂度差距
On the Complexity Gap Between POMDPs and Multi-Environment POMDPs
AI 导读
研究扩展了多环境 POMDP（ME-POMDP）的复杂度图谱，识别出哪些子类在扩展至多环境设定后仍保持 PSPACE 完全性。作者证明了多环境盲 MDP 与确定性 POMDP 的 NP 完全性，并对不满足混合封闭条件的子类证明了 PSPACE 完全性，还给出多观测 POMDP 的新复杂度结果。
来源：arXiv Artificial Intelligence · arxiv.org