Solving Robust Markov Decision Processes: Generic, Reliable, Efficient
This addresses the challenge of sequential decision-making under uncertainty for researchers and practitioners in AI and operations research, offering a significant performance improvement over prior methods.
The paper tackles the problem of solving robust Markov decision processes (RMDPs) with uncertainty sets, providing a framework that is generic, reliable, and efficient, resulting in a prototype that outperforms existing tools by several orders of magnitude and solves RMDPs with a million states in under a minute.
Markov decision processes (MDP) are a well-established model for sequential decision-making in the presence of probabilities. In robust MDP (RMDP), every action is associated with an uncertainty set of probability distributions, modelling that transition probabilities are not known precisely. Based on the known theoretical connection to stochastic games, we provide a framework for solving RMDPs that is generic, reliable, and efficient. It is *generic* both with respect to the model, allowing for a wide range of uncertainty sets, including but not limited to intervals, $L^1$- or $L^2$-balls, and polytopes; and with respect to the objective, including long-run average reward, undiscounted total reward, and stochastic shortest path. It is *reliable*, as our approach not only converges in the limit, but provides precision guarantees at any time during the computation. It is *efficient* because -- in contrast to state-of-the-art approaches -- it avoids explicitly constructing the underlying stochastic game. Consequently, our prototype implementation outperforms existing tools by several orders of magnitude and can solve RMDPs with a million states in under a minute.