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.

本文探讨了在考虑转移概率不确定性时，如何高效地解决具有s-和sa-矩形模糊集定义的鲁棒MDP问题，并提出了一种新的策略迭代方案和快速计算鲁棒Bellman算子的方法。实验结果表明，这些方法比使用线性规划求解器结合鲁棒值迭代的现有方法快得多。

L1-鲁棒马尔可夫决策过程的部分策略迭代