arXiv · cs.AI· Eline M. Bovy, Caleb Probine, Marnix Suilen, Ufuk Topcu, Nils Jansen·· 8 小时前
多环境POMDP与POMDP之间的复杂度差距
On the Complexity Gap Between POMDPs and Multi-Environment POMDPs
arXiv:2610.15010v1阅读论文 PDF ↗
仅依据论文摘要整理；未读取全文，实验条件、证明与基准细节请核对原文。
作者：Eline M. Bovy, Caleb Probine, Marnix Suilen, Ufuk Topcu, Nils Jansen
研究任务与主要进展
该论文研究了多环境POMDP（ME-POMDP）在有限时域鲁棒奖励最大化问题中的计算复杂度。作者基于论文摘要证明，多环境盲MDP和确定性POMDP在特定闭包条件下具有NP完全性；一批不满足该条件的子类（包括多观测POMDP）具有PSPACE完全性；在时变马尔可夫策略或有限状态控制器下，部分标准POMDP中NP完全的问题在ME-POMDP中达到存在实数理论（∃R）完全性。
阶段、条件与复现 · 深读核对
- 任务输出与输入访问模型是什么？
- 在什么假设、规模与资源条件下成立？
- 与哪种经典基线比较，是否计入编码与读出？
这些是阅读核对问题；材料未说明的条件保留未知。请结合上方论文版本、资料范围与原文核验。
来源：arXiv · cs.AI · arxiv.org