Partial Policy Iteration for L1-Robust Markov Decision Processes
This work addresses scalability issues for robust MDPs, which are used in dynamic decision problems with uncertain transition probabilities, offering incremental improvements in computational efficiency.
The paper tackles the high computational complexity of solving robust Markov decision processes (MDPs) with L1 ambiguity sets, proposing partial policy iteration and fast methods that achieve many orders of magnitude speedup over state-of-the-art approaches.
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. We also propose fast methods for computing the robust Bellman operator in quasi-linear time, nearly matching the linear complexity the non-robust Bellman operator. Our experimental results indicate that the proposed methods are many orders of magnitude faster than the state-of-the-art approach which uses linear programming solvers combined with a robust value iteration.