Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling

Authors

  • Huaqing Xiong Department of Electrical and Computer Engineering, The Ohio State University
  • Tengyu Xu Department of Electrical and Computer Engineering, The Ohio State University
  • Yingbin Liang Department of Electrical and Computer Engineering, The Ohio State University
  • Wei Zhang Department of Mechanical and Energy Engineering, Southern University of Science and Technology Peng Cheng Laboratory

Keywords:

Optimization

Abstract

Despite the wide applications of Adam in reinforcement learning (RL), the theoretical convergence of Adam-type RL algorithms has not been established. This paper provides the first such convergence analysis for two fundamental RL algorithms of policy gradient (PG) and temporal difference (TD) learning that incorporate AMSGrad updates (a standard alternative of Adam in theoretical analysis), referred to as PG-AMSGrad and TD-AMSGrad, respectively. Moreover, our analysis focuses on Markovian sampling for both algorithms. We show that under general nonlinear function approximation, PG-AMSGrad with a constant stepsize converges to a neighborhood of a stationary point at the rate of O(1/T) (where T denotes the number of iterations), and with a diminishing stepsize converges exactly to a stationary point at the rate of O(log^2 T/√T). Furthermore, under linear function approximation, TD-AMSGrad with a constant stepsize converges to a neighborhood of the global optimum at the rate of O(1/T), and with a diminishing stepsize converges exactly to the global optimum at the rate of O(log T/√T). Our study develops new techniques for analyzing the Adam-type RL algorithms under Markovian sampling.

Downloads

Published

2021-05-18

How to Cite

Xiong, H., Xu, T., Liang, Y., & Zhang, W. . (2021). Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling. Proceedings of the AAAI Conference on Artificial Intelligence, 35(12), 10460-10468. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17252

Issue

Section

AAAI Technical Track on Machine Learning V