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

arXiv: https://arxiv.org/abs/2002.06286 · HTML: https://mlsanity.com/paper/2002.06286/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Feb 2020.

## Built on by (most cited first, 15 of 15)

- [Recent Advances in Reinforcement Learning in Finance](https://mlsanity.com/paper/2112.04553/) (2021)
- [On the Global Optimum Convergence of Momentum-based Policy Gradient](https://mlsanity.com/paper/2110.10116/) (2021)
- [Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality](https://mlsanity.com/paper/2102.11866/) (2021)
- [Deep Policy Gradient Methods Without Batch Updates, Target Networks, or Replay Buffers](https://mlsanity.com/paper/2411.15370/) (2024)
- [TIC-GRPO: Provable and Efficient Optimization for Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2508.02833/) (2025)
- [Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learning](https://mlsanity.com/paper/2405.09660/) (2024)
- [Markov Chain Score Ascent: A Unifying Framework of Variational Inference with Markovian Gradients](https://mlsanity.com/paper/2206.06295/) (2022)
- [Constrained Stochastic Nonconvex Optimization with State-dependent Markov Data](https://mlsanity.com/paper/2206.11346/) (2022)
- [Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reduction](https://mlsanity.com/paper/2401.01084/) (2024)
- [Sample Complexity Characterization for Linear Contextual MDPs](https://mlsanity.com/paper/2402.02700/) (2024)
- [Stochastic Gradient Descent with Adaptive Data](https://mlsanity.com/paper/2410.01195/) (2024)
- [Non-Asymptotic Global Convergence of PPO-Clip](https://mlsanity.com/paper/2512.16565/) (2025)
- [Provably Efficient Convergence of Primal-Dual Actor-Critic with Nonlinear Function Approximation](https://mlsanity.com/paper/2202.13863/) (2022)
- [Resonance in Weight Space: Covariate Shift Can Drive Divergence of SGD with Momentum](https://mlsanity.com/paper/2203.11992/) (2022)
- [On the Stochastic (Variance-Reduced) Proximal Gradient Method for Regularized Expected Reward Optimization](https://mlsanity.com/paper/2401.12508/) (2024)

## Abstract (arXiv)

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(log2 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.