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

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 $\mathcal{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 $\mathcal{O}({\log }^{2}T/\sqrt{T})$. Furthermore, under linear function approximation, TD-AMSGrad with a constant stepsize converges to a neighborhood of the global optimum at the rate of $\mathcal{O}(1/T)$, and with a diminishing stepsize converges exactly to the global optimum at the rate of $\mathcal{O}(\log T/\sqrt{T})$. Our study develops new techniques for analyzing the Adam-type RL algorithms under Markovian sampling.

References in corpus (21)

• Playing Atari with Deep Reinforcement Learning
• Trust Region Policy Optimization
• On the Convergence of Adam and Beyond
• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• Neural Optimizer Search with Reinforcement Learning
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• On the Convergence Proof of AMSGrad and a New Version
• Accelerated Methods for Deep Reinforcement Learning
• Derivative-Free Methods for Policy Optimization: Guarantees for Linear Quadratic Systems
• On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
• Finite-Sample Analysis for SARSA with Linear Function Approximation
• Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples
• Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
• Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies
• Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theory
• Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning
• Non-asymptotic Analysis of Biased Stochastic Approximation Scheme
• Actor-Critic Provably Finds Nash Equilibria of Linear-Quadratic Mean-Field Games
• History-Gradient Aided Batch Size Adaptation for Variance Reduced Algorithms
• Adaptive Temporal Difference Learning with Linear Function Approximation
• Natural Actor-Critic Converges Globally for Hierarchical Linear Quadratic Regulator

Cited by in corpus (6)

• Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms
• Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms
• Momentum Q-learning with Finite-Sample Convergence Guarantee
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality
• Temporal Difference Learning as Gradient Splitting
• Some Limit Properties of Markov Chains Induced by Stochastic Recursive Algorithms