  Multiple-environment MDPs (MEMDPs) capture finite sets of MDPs that share the
states but differ in the transition dynamics. These models form a proper
subclass of partially observable MDPs (POMDPs). We consider the synthesis of
policies that robustly satisfy an almost-sure reachability property in MEMDPs,
that is, one policy that satisfies a property for all environments. For POMDPs,
deciding the existence of robust policies is an EXPTIME-complete problem. In
this paper, we show that this problem is PSPACE-complete for MEMDPs, while the
policies in general require exponential memory. We exploit the theoretical
results to develop and implement an algorithm that shows promising results in
synthesizing robust policies for various benchmarks.
