On the Existence of Uniformly Optimal Policies in MDPs under Epistemic Uncertainty

We study the existence of uniformly optimal stationary policies, which are optimal for any starting distribution in Markov Decision Processes (MDPs) under epistemic (parameter) uncertainty within two complementary frameworks. For robust MDPs, we establish that (s- and sa-) rectangular models are equivalent to the existence of uniformly optimal stationary policies and provide several interesting counterexamples, including a simple r-rectangular instance with only history-dependent optimal policies. For ambiguity-averse MDPs where the uncertain transition kernel is a random variable, and the return is evaluated via a law-invariant risk measure, we show that uniformly optimal stationary policies can only exist for the essential supremum or essential infimum (under mild monotone continuity assumptions), thus excluding other risk measures such as CVaR, VaR, and the Entropic Risk Measure. We conclude our work by relating dynamic programming and the existence of uniformly optimal policies. One of the main takeaways of our impossibility results is the need for new models to go beyond uniformly optimal stationary policies.