# Multiple-Environment Markov Decision Processes

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 May 2014.

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

- [Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet](https://mlsanity.com/paper/2411.11451/) (2024)
- [Decision-Making Under Uncertainty: Beyond Probabilities](https://mlsanity.com/paper/2303.05848/) (2023)
- [Certifiably Robust Policies for Uncertain Parametric Environments](https://mlsanity.com/paper/2408.03093/) (2024)
- [Robust Finite-Memory Policy Gradients for Hidden-Model POMDPs](https://mlsanity.com/paper/2505.09518/) (2025)
- [Reinforcement Learning Methods for Wordle: A POMDP/Adaptive Control Approach](https://mlsanity.com/paper/2211.10298/) (2022)
- [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)
- [A Finite-State Controller Based Offline Solver for Deterministic POMDPs](https://mlsanity.com/paper/2505.00596/) (2025)
- [Computing the Reachability Value of Posterior-Deterministic POMDPs](https://mlsanity.com/paper/2602.07473/) (2026)
- [VeRecycle: Reclaiming Guarantees from Probabilistic Certificates for Stochastic Dynamical Systems after Change](https://mlsanity.com/paper/2505.14001/) (2025)
- [Multi-Environment POMDPs with Finite-Horizon Objectives](https://mlsanity.com/paper/2605.07537/) (2026)
- [Probing the Impact of Scale on Data-Efficient, Generalist Transformer World Models for Atari](https://mlsanity.com/paper/2605.08578/) (2026)
- [On the Complexity Gap Between POMDPs and Multi-Environment POMDPs](https://mlsanity.com/paper/2610.15010/) (2026)

## Abstract (arXiv)

We introduce Multi-Environment Markov Decision Processes (MEMDPs) which are MDPs with a set of probabilistic transition functions. The goal in a MEMDP is to synthesize a single controller with guaranteed performances against all environments even though the environment is unknown a priori. While MEMDPs can be seen as a special class of partially observable MDPs, we show that several verification problems that are undecidable for partially observable MDPs, are decidable for MEMDPs and sometimes have even efficient solutions.