在本文中，作者研究了多环境部分可观测马尔可夫决策过程（ME‑POMDP），它在普通 POMDP 的基础上加入了一个有限的环境集合，用以刻画模型不确定性。有限视野下的鲁棒奖励最大化问题要求在最坏环境中仍能获得最大期望奖励，已知该问题是 $\\mathsf{PSPACE}$‑complete。作者进一步考察了若干在单环境下可多项式求解的 POMDP 子类，分析它们在多环境扩展后的复杂度。首先，利用一种“闭合于混合”条件，证明了多环境盲 MDP 和确定性 POMDP 的决策问题是 $\\mathsf{NP}$‑complete。随后，对不满足该闭合条件的子类（如多观测 POMDP）给出 $\\mathsf{PSPACE}$‑complete 的硬度结果。最后，针对时间依赖的马尔可夫策略或有限状态控制器，展示了许多问题在 ME‑POMDP 中达到 $\\exists \\mathbb{R}$‑complete，而在标准 POMDP 中仅为 $\\mathsf{NP}$‑complete。整体结论表明，POMDP 与 ME‑POMDP 的复杂度关系极其细致，取决于具体子类的结构特性。
点评