Partial Policy Iteration for L1-Robust Markov Decision Processes
Partial Policy Iteration for L1-Robust Markov Decision Processes
复制标题
DOI：
--
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
C. Ho;Marek Petrik;W. Wiesemann
中科院分区：
文献类型：
--
作者：
C. Ho;Marek Petrik;W. Wiesemann
鲁棒马尔可夫决策过程（MDP）允许计算可靠的动态决策问题的解决方案，其演变是由奖励和部分已知的转移概率建模。不幸的是，占转移概率的不确定性显着增加的计算复杂性，解决强大的MDP，这严重限制了他们的可扩展性。本文描述了求解一类具有加权L_1范数定义的S-和Sa-矩形模糊集的鲁棒MDP的新的有效算法。我们提出了部分政策迭代，一个新的，高效的，灵活的，和一般的政策迭代计划的强大的MDP。我们还提出了快速的方法来计算鲁棒Bellman算子在准线性时间，几乎匹配的线性复杂性的非鲁棒Bellman算子。我们的实验结果表明，所提出的方法是许多数量级的速度比国家的最先进的方法，使用线性规划求解器结合一个强大的值迭代。
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.