mlsanityData to 7 Oct 2026

A Finite Time Analysis of Two Time-Scale Actor Critic Methods

arXiv 2005.01350 ↗First posted 4 May 2020cs.LG math.OC stat.MLcited by 120

Not on the map. Why?

Abstract (arXiv)

Actor-critic (AC) methods have exhibited great empirical success compared with other reinforcement learning algorithms, where the actor uses the policy gradient to improve the learning policy and the critic uses temporal difference learning to estimate the policy gradient. Under the two time-scale learning rate schedule, the asymptotic convergence of AC has been well studied in the literature. However, the non-asymptotic convergence and finite sample complexity of actor-critic methods are largely open. In this work, we provide a non-asymptotic analysis for two time-scale actor-critic methods under non-i.i.d. setting. We prove that the actor-critic method is guaranteed to find a first-order stationary point (i.e., |nabla J(boldsymbolθ)|22 ≤ ε) of the non-concave performance function J(boldsymbolθ), with mathcaltildeO(ε-2.5) sample complexity. To the best of our knowledge, this is the first work providing finite-time analysis and sample complexity bound for two time-scale actor-critic methods.

Key facts. Cited by 120 papers in the map (data through 7 Oct 2026). First posted on arXiv 4 May 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 26; 2022: 25; 2023: 19; 2024: 17; 2025: 25; 2026: 7.

120 papers.

Sort:

By area:

  1. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 95
  2. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
  3. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 63
  4. 2022FedNest: Federated Bilevel, Minimax, and Compositional Optimizationcited by 60
  5. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
  6. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
  7. 2021Breaking the Deadly Triad with a Target Networkcited by 47
  8. 2021Softmax Policy Gradient Methods Can Take Exponential Time to Convergecited by 46
  9. 2022Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guaranteescited by 42
  10. 2024Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHFcited by 41
  11. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  12. 2022Finite-time analysis of single-timescale actor-criticcited by 30
38 more
  1. 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
  2. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithmcited by 26
  3. 2023When Demonstrations Meet Generative World Models: A Maximum Likelihood Framework for Offline Inverse Reinforcement Learningcited by 26
  4. 2021Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysiscited by 25
  5. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 24
  6. 2021On the Global Optimum Convergence of Momentum-based Policy Gradientcited by 23
  7. 2025Learning to Optimize Multi-Objective Alignment Through Dynamic Reward Weightingcited by 23
  8. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  9. 2022A Small Gain Analysis of Single Timescale Actor Criticcited by 22
  10. 2021Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problemscited by 21
  11. 2021Doubly Robust Off-Policy Actor-Critic: Convergence and Optimalitycited by 20
  12. 2021A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learningcited by 20
  13. 2020Average-reward model-free reinforcement learning: a systematic review and literature mappingcited by 19
  14. 2023Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Criticcited by 18
  15. 2021Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatchcited by 17
  16. 2022Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithmcited by 17
  17. 2022A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequencescited by 17
  18. 2022Oracle-free Reinforcement Learning in Mean-Field Games along a Single Sample Pathcited by 16
  19. 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16
  20. 2022On the Convergence of SARSA with Linear Function Approximationcited by 15
  21. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  22. 2021Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processescited by 14
  23. 2022Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methodscited by 14
  24. 2022Mitigating Gradient Bias in Multi-objective Learning: A Provably Convergent Stochastic Approachcited by 14
  25. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approachcited by 14
  26. 2021Analysis of a Target-Based Actor-Critic Algorithm with Linear Function Approximationcited by 13
  27. 2022Structural Estimation of Markov Decision Processes in High-Dimensional State Space with Finite-Time Guaranteescited by 12
  28. 2025Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Setcited by 11
  29. 2021Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noisecited by 10
  30. 2024Sublinear Regret for a Class of Continuous-Time Linear-Quadratic Reinforcement Learning Problemscited by 10
  31. 2024Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noisecited by 10
  32. 2022Single Time-scale Actor-critic Method to Solve the Linear Quadratic Regulator with Convergence Guaranteescited by 9
  33. 2022Analysis of Stochastic Processes through Replay Bufferscited by 9
  34. 2021Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximationcited by 8
  35. 2022Global Convergence of Two-timescale Actor-Critic for Solving Linear Quadratic Regulatorcited by 8
  36. 2022A policy gradient approach for Finite Horizon Constrained Markov Decision Processescited by 8
  37. 2024Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learningcited by 8
  38. 2021Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexitycited by 7

50 most cited of 120 All 120 (JSON)