Convergence Rates of Accelerated Markov Gradient Descent with Applications in Reinforcement Learning

Abstract

Motivated by broad applications in machine learning, we study the popular accelerated stochastic gradient descent (ASGD) algorithm for solving (possibly nonconvex) optimization problems. We characterize the finite-time performance of this method when the gradients are sampled from Markov processes, and hence biased and dependent from time step to time step; in contrast, the analysis in existing work relies heavily on the stochastic gradients being independent and sometimes unbiased. Our main contributions show that under certain (standard) assumptions on the underlying Markov chain generating the gradients, ASGD converges at the nearly the same rate with Markovian gradient samples as with independent gradient samples. The only difference is a logarithmic factor that accounts for the mixing time of the Markov chain. One of the key motivations for this study are complicated control problems that can be modeled by a Markov decision process and solved using reinforcement learning. We apply the accelerated method to several challenging problems in the OpenAI Gym and Mujoco, and show that acceleration can significantly improve the performance of the classic temporal difference learning and REINFORCE algorithms.

References in corpus (5)

• Adam: A Method for Stochastic Optimization
• Trust Region Policy Optimization
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Accelerating SGD with momentum for over-parameterized learning
• Approximate Temporal Difference Learning is a Gradient Descent for Reversible Policies

Cited by in corpus (6)

• Finite-Time Analysis of Stochastic Gradient Descent under Markov Randomness
• Local Stochastic Approximation: A Unified View of Federated Learning and Distributed Multi-Task Reinforcement Learning Algorithms
• Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noise
• A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning
• Measuring Progress in Deep Reinforcement Learning Sample Efficiency
• Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs