# On the Complexity Gap Between POMDPs and Multi-Environment POMDPs

arXiv: https://arxiv.org/abs/2610.15010 · HTML: https://mlsanity.com/paper/2610.15010/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 50 references that are in the map.
- First posted on arXiv 10 Oct 2026.

## Builds on (most cited first, 15 of 15)

- [Solving POMDPs by Searching the Space of Finite Policies](https://mlsanity.com/paper/1301.6720/) (2013)
- [Robust Finite-State Controllers for Uncertain POMDPs](https://mlsanity.com/paper/2009.11459/) (2020)
- [Computational Results for Extensive-Form Adversarial Team Games](https://mlsanity.com/paper/1711.06930/) (2017)
- [Multiple-Environment Markov Decision Processes](https://mlsanity.com/paper/1405.4733/) (2014)
- [Robust Almost-Sure Reachability in Multi-Environment MDPs](https://mlsanity.com/paper/2301.11296/) (2023)
- [The Value Problem for Multiple-Environment MDPs with Parity Objective](https://mlsanity.com/paper/2504.15960/) (2025)
- [Dynamic Toolbox for ETRINV](https://mlsanity.com/paper/1912.08674/) (2019)
- [A PSPACE Algorithm for Almost-Sure Rabin Objectives in Multi-Environment MDPs](https://mlsanity.com/paper/2407.07006/) (2024)
- [Multi-Environment POMDPs: Discrete Model Uncertainty Under Partial Observability](https://mlsanity.com/paper/2510.23744/) (2025)
- [Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives](https://mlsanity.com/paper/2412.12063/) (2024)
- [Computational Hardness of Static Distributionally Robust Markov Decision Processes](https://mlsanity.com/paper/2511.02224/) (2025)
- [Revealing POMDPs: Qualitative and Quantitative Analysis for Parity Objectives](https://mlsanity.com/paper/2511.13134/) (2025)
- [Multi-Environment MDPs with Prior and Universal Semantics](https://mlsanity.com/paper/2602.10938/) (2026)
- [Dicey Games: Shared Sources of Randomness in Distributed Systems](https://mlsanity.com/paper/2601.18303/) (2026)
- [Computing the Reachability Value of Posterior-Deterministic POMDPs](https://mlsanity.com/paper/2602.07473/) (2026)

## Abstract (arXiv)

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.