On the Complexity Gap Between POMDPs and Multi-Environment POMDPs

arXiv:2610.15010v1 Announce Type: new Abstract: 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 mathsf{PSPACE}-complete. We expand the complexity landscape of ME-POMDPs by identifying which subclasses retain this mathsf{PSPACE}-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 mathsf{NP}-completeness of multi-environment blind MDPs and deterministic POMDPs using a certain closure-under-mixture condition. We then prove mathsf{PSPACE}-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 R)-completeness for numerous ME-POMDP problems under time-dependent Markovian policies or finite-state controllers that are mathsf{NP}-complete for standard POMDPs. These results reveal a subtle relationship between POMDP and ME-POMDP complexity that depends heavily on the subclasses involved.

Related

• Multi-Environment POMDPs with Finite-Horizon Objectives
• Synthesizing POMDP Policies: Sampling Meets Model-checking via Learning
• EnvACE: Internalizing Environment Dynamics via World Rehearsal for Agentic Reinforcement Learning

Source: arXiv cs.AI | 2026-10-15