Partial Policy Iteration for L1-Robust Markov Decision Processes

Understand

Robust Markov decision processes (MDPs) allow to compute reliable solutions for dynamic decision problems whose evolution is modeled by rewards and partially-known transition probabilities.

• Unfortunately, accounting for uncertainty in the transition probabilities significantly increases the computational complexity of solving robust MDPs, which severely limits their scalability.
• This paper describes new efficient algorithms for solving the common class of robust MDPs with s- and sa-rectangular ambiguity sets defined by weighted $L_1$ norms.
• We propose partial policy iteration, a new, efficient, flexible, and general policy iteration scheme for robust MDPs.