First-Order Methods for Wasserstein Distributionally Robust MDP

Abstract

Markov decision processes (MDPs) are known to be sensitive to parameter specification. Distributionally robust MDPs alleviate this issue by allowing for \emph{ambiguity sets} which give a set of possible distributions over parameter sets. The goal is to find an optimal policy with respect to the worst-case parameter distribution. We propose a framework for solving Distributionally robust MDPs via first-order methods, and instantiate it for several types of Wasserstein ambiguity sets. By developing efficient proximal updates, our algorithms achieve a convergence rate of $O\left(N{A}^{2.5}{S}^{3.5}\log (S)\log ({\epsilon }^{-1}){\epsilon }^{-1.5}\right)$ for the number of kernels $N$ in the support of the nominal distribution, states $S$, and actions $A$; this rate varies slightly based on the Wasserstein setup. Our dependence on $N,A$ and $S$ is significantly better than existing methods, which have a complexity of $O\left(N^{3.5}{A}^{3.5}{S}^{4.5}{\log }^2({\epsilon }^{-1})\right)$. Numerical experiments show that our algorithm is significantly more scalable than state-of-the-art approaches across several domains.

References in corpus (8)

• Globally Convergent Type-I Anderson Acceleration for Non-Smooth Fixed-Point Iterations
• Efficiently Solving MDPs with Stochastic Mirror Descent
• Two-stage sample robust optimization
• Robust Policies For Proactive ICU Transfers
• Anderson Acceleration for Reinforcement Learning
• Increasing Iterate Averaging for Solving Saddle-Point Problems
• Difference of Convex Functions Programming Applied to Control with Expert Data
• Distributionally Robust Bottleneck Combinatorial Problems: Uncertainty Quantification and Robust Decision Making

Cited by in corpus (2)

• Stochastic Control with Distributionally Robust Constraints for Cyber-Physical Systems Vulnerable to Attacks
• Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving