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 $\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 $\math...
| Authors | Eline M. Bovy, Caleb Probine, Marnix Suilen et al. |
|---|---|
| Primary category | cs.AI |
| Published | 10 October 2026 |
| Last updated at source | 10 October 2026 |
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 14 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.