Partial policy iteration for L1-robust Markov decision processes
File(s)
Published version
OA Location
Author(s)
Ho, Chin Pang
Petrik, Marek
Wiesemann, Wolfram
Type
Journal Article
Abstract
Robust Markov decision processes (MDPs) compute reliable solutions for dynamic decision problems with partially-known transition probabilities. Unfortunately, accounting for uncertainty in the transition probabilities significantly increases the computational complexity of solving robust MDPs, which 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 L1 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 ordinary Bellman operator's linear complexity. 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.
Date Issued
2021-10-01
Date Acceptance
2021-03-01
Citation
Journal of Machine Learning Research, 2021, 22 (275), pp.1-46
ISSN
1532-4435
Publisher
Microtome Publishing
Start Page
1
End Page
46
Journal / Book Title
Journal of Machine Learning Research
Volume
22
Issue
275
Copyright Statement
© 2021 Chin Pang Ho, Marek Petrik, and Wolfram Wiesemann. License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided
at http://jmlr.org/papers/v22/20-445.html.
at http://jmlr.org/papers/v22/20-445.html.
License URL
Subjects
Artificial Intelligence & Image Processing
08 Information and Computing Sciences
17 Psychology and Cognitive Sciences
Publication Status
Published