This paper investigates multi‑environment partially observable Markov decision processes (ME‑POMDPs), which extend standard POMDPs by encoding a finite set of possible environments to capture model uncertainty. The finite‑horizon robust reward maximization problem seeks a policy that maximizes expected reward in the worst‑case environment, a problem known to be $\\mathsf{PSPACE}$‑complete. The authors examine several subclasses that are tractable for single‑environment POMDPs and analyze their complexity when lifted to the multi‑environment setting. First, using a closure‑under‑mixture condition, they prove that the decision problems for multi‑environment blind MDPs and deterministic POMDPs are $\\mathsf{NP}$‑complete. Then, for subclasses that do not satisfy this condition (e.g., multi‑observation POMDPs), they establish $\\mathsf{PSPACE}$‑completeness. Finally, for time‑dependent Markovian policies or finite‑state controllers, they show that many ME‑POMDP problems become $\\exists \\mathbb{R}$‑complete, whereas the corresponding standard POMDP problems are only $\\mathsf{NP}$‑complete. The results reveal a subtle and subclass‑dependent relationship between the complexities of POMDPs and ME‑POMDPs.
Review