Abstract

Markov decision processes (MDPs) are a standard model for sequentialdecision-making problems and are widely used across many scientific areas,including formal methods and artificial intelligence (AI). MDPs do, however,come with the restrictive assumption that the transition probabilities need tobe precisely known. Robust MDPs (RMDPs) overcome this assumption by insteaddefining the transition probabilities to belong to some uncertainty set. Wepresent a gentle survey on RMDPs, providing a tutorial covering theirfundamentals. In particular, we discuss RMDP semantics and how to solve them byextending standard MDP methods such as value iteration and policy iteration. Wealso discuss how RMDPs relate to other models and how they are used in severalcontexts, including reinforcement learning and abstraction techniques. Weconclude with some challenges for future work on RMDPs.