Scalable First-Order Methods for Robust MDPs
This addresses the scalability issue in robust MDPs for sequential decision-making under uncertainty, representing an incremental improvement with a novel method for a known bottleneck.
The paper tackles the problem of solving robust Markov Decision Processes (MDPs) with model uncertainty by proposing the first first-order framework, achieving an ergodic convergence rate of O(A^2 S^3 log(S) log(ε^{-1}) ε^{-1}) and showing significantly better scalability than state-of-the-art approaches in numerical experiments.
Robust Markov Decision Processes (MDPs) are a powerful framework for modeling sequential decision-making problems with model uncertainty. This paper proposes the first first-order framework for solving robust MDPs. Our algorithm interleaves primal-dual first-order updates with approximate Value Iteration updates. By carefully controlling the tradeoff between the accuracy and cost of Value Iteration updates, we achieve an ergodic convergence rate of $O \left( A^{2} S^{3}\log(S)\log(ε^{-1}) ε^{-1} \right)$ for the best choice of parameters on ellipsoidal and Kullback-Leibler $s$-rectangular uncertainty sets, where $S$ and $A$ is the number of states and actions, respectively. Our dependence on the number of states and actions is significantly better (by a factor of $O(A^{1.5}S^{1.5})$) than that of pure Value Iteration algorithms. In numerical experiments on ellipsoidal uncertainty sets we show that our algorithm is significantly more scalable than state-of-the-art approaches. Our framework is also the first one to solve robust MDPs with $s$-rectangular KL uncertainty sets.