Efficiently Solving MDPs with Stochastic Mirror Descent

Abstract

We present a unified framework based on primal-dual stochastic mirror descent for approximately solving infinite-horizon Markov decision processes (MDPs) given a generative model. When applied to an average-reward MDP with $A_{tot}$ total state-action pairs and mixing time bound $t_{mix}$ our method computes an $\epsilon$-optimal policy with an expected $\tilde{O}(t_{mix}^2{A}_{tot}{\epsilon }^{-2})$ samples from the state-transition matrix, removing the ergodicity dependence of prior art. When applied to a $\gamma$-discounted MDP with $A_{tot}$ total state-action pairs our method computes an $\epsilon$-optimal policy with an expected $\tilde{O}((1-\gamma {)}^{-4}{A}_{tot}{\epsilon }^{-2})$ samples, matching the previous state-of-the-art up to a $(1-\gamma {)}^{-1}$ factor. Both methods are model-free, update state values and policies simultaneously, and run in time linear in the number of samples taken. We achieve these results through a more general stochastic mirror descent framework for solving bilinear saddle-point problems with simplex and box domains and we demonstrate the flexibility of this framework by providing further applications to constrained MDPs.

ICML 2020

Cited by in corpus (5)

• Quantum Algorithms for Reinforcement Learning with a Generative Model
• Near-Optimal Decentralized Algorithms for Saddle Point Problems over Time-Varying Networks
• Towards Tight Bounds on the Sample Complexity of Average-reward MDPs
• Near Optimal Policy Optimization via REPS
• Optimal Analysis of Method with Batching for Monotone Stochastic Finite-Sum Variational Inequalities