On the Complexity Gap Between POMDPs and Multi-Environment POMDPs

Multi-environment POMDPs (ME-POMDPs) generalize POMDPs by encoding a finite set of possible environments, capturing model uncertainty. The finite-horizon robust reward maximization problem for a ME-POMDP asks for a policy that maximizes reward in the worst environment, and recent work has shown this problem to be mathsfPSPACE-complete. We expand the complexity landscape of ME-POMDPs by identifying which subclasses retain this mathsfPSPACE-completeness. In particular, we take subclasses of POMDPs that are tractable in the single-environment case, and investigate the computational complexity of these classes when extended to the multi-environment setting. We first prove the mathsfNP-completeness of multi-environment blind MDPs and deterministic POMDPs using a certain closure-under-mixture condition. We then prove mathsfPSPACE-completeness for a range of subclasses that do not satisfy that closure condition, yielding new complexity results for multi-observation POMDPs. Finally, we show existential theory of the reals (exists ℝ)-completeness for numerous ME-POMDP problems under time-dependent Markovian policies or finite-state controllers that are mathsfNP-complete for standard POMDPs. These results reveal a subtle relationship between POMDP and ME-POMDP complexity that depends heavily on the subclasses involved.