POMDP 与多环境 POMDP 之间的复杂性差距

多环境 POMDP（ME-POMDPs）通过编码一组有限的可能环境来推广 POMDP，从而刻画模型不确定性。ME-POMDP 的有限时域鲁棒奖励最大化问题要求寻找一个策略，使其在最差环境中的奖励最大化；近期研究表明，该问题是 $\mathsf{PSPACE}$-完全的。我们通过确定哪些子类仍保持这种 $\mathsf{PSPACE}$-完全性，拓展了 ME-POMDP 的复杂性版图。具体而言，我们选取单环境情形下易处理的 POMDP 子类，并研究这些类别扩展到多环境设置后的计算复杂性。首先，我们利用某种对混合运算封闭的条件，证明了多环境盲 MDP 和确定性 POMDP 的 $\mathsf{NP}$-完全性。随后，我们证明了一系列不满足该闭包条件的子类是 $\mathsf{PSPACE}$-完全的，从而为多观测 POMDP 提供了新的复杂性结果。最后，我们证明，在时变马尔可夫策略或有限状态控制器下，众多对于标准 POMDP 属于 $\mathsf{NP}$-完全的 ME-POMDP 问题是实数存在理论（$\exists \mathbb{R}$）-完全的。这些结果揭示了 POMDP 与 ME-POMDP 复杂性之间一种微妙的关系，而这种关系在很大程度上取决于所涉及的子类。