arXiv cs.AI· Eline M. Bovy, Caleb Probine, Marnix Suilen, Ufuk Topcu, Nils Jansen·· 8 小时前AI 评分12
POMDP 与多环境 POMDP 之间的复杂度差距
On the Complexity Gap Between POMDPs and Multi-Environment POMDPs
AI 导读
研究揭示了 POMDP 与多环境 POMDP（ME-POMDP）之间依赖具体子类的复杂度差距。作者证明了多环境盲 MDP 与确定性 POMDP 的 NP-完全性，并对不满足混合封闭条件的多观测 POMDP 等子类证明了 PSPACE-完全性。此外，在时间相关马尔可夫策略或有限状态控制器下，多个 ME-POMDP 问题被证明为 ∃ℝ-完全，而对应标准 POMDP 问题仅为 NP-完全。
来源：arXiv cs.AI · arxiv.org