Timezone: »

 
Spotlight
First-Order Methods for Wasserstein Distributionally Robust MDP
Julien Grand-Clement · Christian Kroer

Thu Jul 22 06:20 AM -- 06:25 AM (PDT) @
in Learning Theory 14 »
Markov decision processes (MDPs) are known to be sensitive to parameter specification. Distributionally robust MDPs alleviate this issue by allowing for \textit{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(NA^{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.
Keywords: RL, Decisions and Control Theory

Author Information

Julien Grand-Clement (IEOR Department, Columbia University)
Christian Kroer (Columbia University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors