On the Existence of Uniformly Optimal Policies in MDPs under Epistemic Uncertainty
Abstract
We investigate the existence of uniformly optimal stationary policies in Markov Decision Processes (MDPs) under epistemic (parameter) uncertainty that are optimal for any initial distribution. Our study is conducted 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 exist only 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.