# Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms

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

## Key facts

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

## Built on by (most cited first, 30 of 43)

- [Recent Advances in Reinforcement Learning in Finance](https://mlsanity.com/paper/2112.04553/) (2021)
- [An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods](https://mlsanity.com/paper/2211.07937/) (2022)
- [Softmax Policy Gradient Methods Can Take Exponential Time to Converge](https://mlsanity.com/paper/2102.11270/) (2021)
- [On the Linear convergence of Natural Policy Gradient Algorithm](https://mlsanity.com/paper/2105.01424/) (2021)
- [Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2101.10506/) (2021)
- [Finite-time analysis of single-timescale actor-critic](https://mlsanity.com/paper/2210.09921/) (2022)
- [Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2102.09318/) (2021)
- [Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis](https://mlsanity.com/paper/2109.03699/) (2021)
- [On the Global Optimum Convergence of Momentum-based Policy Gradient](https://mlsanity.com/paper/2110.10116/) (2021)
- [A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning](https://mlsanity.com/paper/2109.14756/) (2021)
- [Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximation](https://mlsanity.com/paper/2105.12540/) (2021)
- [Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality](https://mlsanity.com/paper/2102.11866/) (2021)
- [Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes](https://mlsanity.com/paper/2110.11383/) (2021)
- [Analysis of a Target-Based Actor-Critic Algorithm with Linear Function Approximation](https://mlsanity.com/paper/2106.07472/) (2021)
- [Actor-critic is implicitly biased towards high entropy optimal policies](https://mlsanity.com/paper/2110.11280/) (2021)
- [Provably Robust Temporal Difference Learning for Heavy-Tailed Rewards](https://mlsanity.com/paper/2306.11455/) (2023)
- [Global Convergence of Two-timescale Actor-Critic for Solving Linear Quadratic Regulator](https://mlsanity.com/paper/2208.08744/) (2022)
- [Wasserstein Flow Meets Replicator Dynamics: A Mean-Field Analysis of Representation Learning in Actor-Critic](https://mlsanity.com/paper/2112.13530/) (2021)
- [Value Improved Actor Critic Algorithms](https://mlsanity.com/paper/2406.01423/) (2024)
- [Learning to Coordinate in Multi-Agent Systems: A Coordinated Actor-Critic Algorithm and Finite-Time Guarantees](https://mlsanity.com/paper/2110.05597/) (2021)
- [On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correction](https://mlsanity.com/paper/2106.00993/) (2021)
- [On the Global Convergence of Natural Actor-Critic with Two-layer Neural Network Parametrization](https://mlsanity.com/paper/2306.10486/) (2023)
- [On the Second-Order Convergence of Biased Policy Gradient Algorithms](https://mlsanity.com/paper/2311.02546/) (2023)
- [Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2409.12135/) (2024)
- [How to Find the Exact Pareto Front for Multi-Objective MDPs?](https://mlsanity.com/paper/2410.15557/) (2024)
- [Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2505.21391/) (2025)
- [Decision-Aware Actor-Critic with Function Approximation and Theoretical Guarantees](https://mlsanity.com/paper/2305.15249/) (2023)
- [On the Convergence of Single-Timescale Actor-Critic](https://mlsanity.com/paper/2410.08868/) (2024)
- [On the Convergence of Policy Mirror Descent with Temporal Difference Evaluation](https://mlsanity.com/paper/2509.18822/) (2025)
- [Global Convergence of the ODE Limit for Online Actor-Critic Algorithms in Reinforcement Learning](https://mlsanity.com/paper/2108.08655/) (2021)

## Abstract (arXiv)

As an important type of reinforcement learning algorithms, actor-critic (AC) and natural actor-critic (NAC) algorithms are often executed in two ways for finding optimal policies. In the first nested-loop design, actor's one update of policy is followed by an entire loop of critic's updates of the value function, and the finite-sample analysis of such AC and NAC algorithms have been recently well established. The second two time-scale design, in which actor and critic update simultaneously but with different learning rates, has much fewer tuning parameters than the nested-loop design and is hence substantially easier to implement. Although two time-scale AC and NAC have been shown to converge in the literature, the finite-sample convergence rate has not been established. In this paper, we provide the first such non-asymptotic convergence rate for two time-scale AC and NAC under Markovian sampling and with actor having general policy class approximation. We show that two time-scale AC requires the overall sample complexity at the order of O(ε-2.5log3(ε-1)) to attain an ε-accurate stationary point, and two time-scale NAC requires the overall sample complexity at the order of O(ε-4log2(ε-1)) to attain an ε-accurate global optimal point. We develop novel techniques for bounding the bias error of the actor due to dynamically changing Markovian sampling and for analyzing the convergence rate of the linear critic with dynamically changing base functions and transition kernel.