Partial Policy Iteration for L1-Robust Markov Decision Processes

2020/06/16 by Chin Pang Ho, Ho, Chin Pang, Marek Petrik +3 · 2 citations
Computer Science · #FOS: Computer and information sciences #FOS: Mathematics #Formal Methods in Verification #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2006.09484

openalex publication_date 2020/06/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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₁ 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.

Citations

• Robust Dynamic Programming
• Fast projection onto the simplex and the \pmb l_\mathbf 1 l 1 ball

Cited by

• SPiDR: A Simple Approach for Zero-Shot Safety in Sim-to-Real Transfer
• Convergence of Fast Policy Iteration in Markov Games and Robust MDPs
• Optimizing Percentile Criterion Using Robust MDPs

Related

• An Efficient Solution to s-Rectangular Robust Markov Decision Processes
• Efficient Policy Iteration for Robust Markov Decision Processes via Regularization
• Scalable First-Order Methods for Robust MDPs
• First-order Policy Optimization for Robust Markov Decision Process
• Policy Gradient Algorithms for Robust MDPs with Non-Rectangular Uncertainty Sets