Efficiently Solving MDPs with Stochastic Mirror Descent

2020/08/28 by Jin, Yujia, Sidford, Aaron · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2008.12776

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 ε-optimal policy with an expected \widetildeO(t_mix² A_tot ε^-2) samples from the state-transition matrix, removing the ergodicity dependence of prior art. When applied to a γ-discounted MDP with A_tot total state-action pairs our method computes an ε-optimal policy with an expected \widetildeO((1-γ)^-4 A_tot ε^-2) samples, matching the previous state-of-the-art up to a (1-γ)^-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.

Cited by

• Shuffling Heuristic in Variational Inequalities: Establishing New Convergence Guarantees
• Stochastic Decentralized Optimization of Non-Smooth Convex and Convex-Concave Problems over Time-Varying Networks

Related

• Primal-Dual Stochastic Mirror Descent for MDPs
• Sample Complexity Bounds for Linear Constrained MDPs with a Generative Model
• Towards Tight Bounds on the Sample Complexity of Average-reward MDPs
• Stochastic first-order methods for average-reward Markov decision processes
• Efficiently Solving Discounted MDPs with Predictions on Transition Matrices