# Multi-Environment POMDPs: Discrete Model Uncertainty Under Partial Observability

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 53 references that are in the map.
- First posted on arXiv 27 Oct 2025.

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

- [Emergent Complexity and Zero-shot Transfer via Unsupervised Environment Design](https://mlsanity.com/paper/2012.02096/) (2020)
- [RL for Latent MDPs: Regret Guarantees and a Lower Bound](https://mlsanity.com/paper/2102.04939/) (2021)
- [PAC Reinforcement Learning for Predictive State Representations](https://mlsanity.com/paper/2207.05738/) (2022)
- [Robust Finite-State Controllers for Uncertain POMDPs](https://mlsanity.com/paper/2009.11459/) (2020)
- [Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithms](https://mlsanity.com/paper/2209.14990/) (2022)
- [Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet](https://mlsanity.com/paper/2411.11451/) (2024)
- [Distributionally Robust Partially Observable Markov Decision Process with Moment-based Ambiguity](https://mlsanity.com/paper/1906.05988/) (2019)
- [Reinforcement Learning in Reward-Mixing MDPs](https://mlsanity.com/paper/2110.03743/) (2021)
- [Multiple-Environment Markov Decision Processes](https://mlsanity.com/paper/1405.4733/) (2014)
- [Solving Zero-Sum One-Sided Partially Observable Stochastic Games](https://mlsanity.com/paper/2010.11243/) (2020)
- [An Optimisation Framework for Unsupervised Environment Design](https://mlsanity.com/paper/2505.20659/) (2025)
- [Decision-Making Under Uncertainty: Beyond Probabilities](https://mlsanity.com/paper/2303.05848/) (2023)
- [Imprecise Probabilities Meet Partial Observability: Game Semantics for Robust POMDPs](https://mlsanity.com/paper/2405.04941/) (2024)
- [Certifiably Robust Policies for Uncertain Parametric Environments](https://mlsanity.com/paper/2408.03093/) (2024)
- [Pessimistic Iterative Planning with RNNs for Robust POMDPs](https://mlsanity.com/paper/2408.08770/) (2024)
- [Robust Policy Synthesis for Uncertain POMDPs via Convex Optimization](https://mlsanity.com/paper/2001.08174/) (2020)
- [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)
- [Robust Finite-Memory Policy Gradients for Hidden-Model POMDPs](https://mlsanity.com/paper/2505.09518/) (2025)
- [Bridging the Gap between Partially Observable Stochastic Games and Sparse POMDP Methods](https://mlsanity.com/paper/2405.18703/) (2024)
- [Near-Optimal Learning and Planning in Separated Latent MDPs](https://mlsanity.com/paper/2406.07920/) (2024)
- [A PSPACE Algorithm for Almost-Sure Rabin Objectives in Multi-Environment MDPs](https://mlsanity.com/paper/2407.07006/) (2024)

## Built on by (most cited first, 3 of 3)

- [Multi-Environment POMDPs with Finite-Horizon Objectives](https://mlsanity.com/paper/2605.07537/) (2026)
- [Distinguish or Homogenize: Last-Chance Policy Identification and Risk-Budgeted Recovery under Irreversible Resource Depletion](https://mlsanity.com/paper/2609.36741/) (2026)
- [On the Complexity Gap Between POMDPs and Multi-Environment POMDPs](https://mlsanity.com/paper/2610.15010/) (2026)

## Abstract (arXiv)

Multi-environment POMDPs (ME-POMDPs) extend standard POMDPs with discrete model uncertainty. ME-POMDPs represent a finite set of POMDPs that share the same state, action, and observation spaces, but may arbitrarily vary in their transition, observation, and reward models. Such models arise, for instance, when multiple domain experts disagree on how to model a problem. The goal is to find a single policy that is robust against any choice of POMDP within the set, i.e., a policy that maximizes the worst-case reward across all POMDPs. We generalize and expand on existing work in the following way. First, we show that ME-POMDPs can be generalized to POMDPs with sets of initial beliefs, which we call adversarial-belief POMDPs (AB-POMDPs). Second, we show that any arbitrary ME-POMDP can be reduced to a ME-POMDP that only varies in its transition and reward functions or only in its observation and reward functions, while preserving (optimal) policies. We then devise exact and approximate (point-based) algorithms to compute robust policies for AB-POMDPs, and thus ME-POMDPs. We demonstrate that we can compute policies for standard POMDP benchmarks extended to the multi-environment setting.