mlsanityData to 7 Oct 2026

Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm

arXiv 2101.10506 ↗First posted 26 Jan 2021cs.LGcited by 39

Not on the map. Why?

Abstract (arXiv)

Actor-critic style two-time-scale algorithms are one of the most popular methods in reinforcement learning, and have seen great empirical success. However, their performance is not completely understood theoretically. In this paper, we characterize the global convergence of an online natural actor-critic algorithm in the tabular setting using a single trajectory of samples. Our analysis applies to very general settings, as we only assume ergodicity of the underlying Markov decision process. In order to ensure enough exploration, we employ an ε-greedy sampling of the trajectory. For a fixed and small enough exploration parameter ε, we show that the two-time-scale natural actor-critic algorithm has a rate of convergence of tildeO(1/T1/4), where T is the number of samples, and this leads to a sample complexity of TildeO(1/δ8) samples to find a policy that is within an error of δ from the global optimum. Moreover, by carefully decreasing the exploration parameter ε as the iterations proceed, we present an improved sample complexity of TildeO(1/δ6) for convergence to the global optimum.

Key facts. Cited by 39 papers in the map (data through 7 Oct 2026). Builds on 30 of its 76 references that are in the map. First posted on arXiv 26 Jan 2021.

Builds on

30 of 76 references.

References · 30

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
  3. 2015Trust Region Policy Optimizationcited by 2,503
  4. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,218
  5. 2018Soft Actor-Critic Algorithms and Applicationscited by 1,179
  6. 2018IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architecturescited by 866
  7. 2019A Theory of Regularized Markov Decision Processescited by 279
  8. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  9. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  10. 2016Sample Efficient Actor-Critic with Experience Replaycited by 185
  11. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  12. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 170
18 more
  1. 2016An Actor-Critic Algorithm for Sequence Predictioncited by 158
  2. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  3. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 120
  4. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 113
  5. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 65
  6. 2014Algorithms for multi-armed bandit problemscited by 63
  7. 2019On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximationcited by 54
  8. 2013The Information Geometry of Mirror Descentcited by 53
  9. 2020Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noisecited by 52
  10. 2020Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithmscited by 43
  11. 2019Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policycited by 42
  12. 2020Single-Timescale Actor-Critic Provably Finds Globally Optimal Policycited by 34
  13. 2020Finite-Sample Analysis of Proximal Gradient TD Algorithmscited by 32
  14. 2019Finite-Time Analysis and Restarting Scheme for Linear Two-Time-Scale Stochastic Approximationcited by 18
  15. 2020Mirrorless Mirror Descent: A Natural Derivation of Mirror Descentcited by 18
  16. 2020Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithmscited by 14
  17. 2018Convergent Actor-Critic Algorithms Under Off-Policy Training and Function Approximationcited by 12
  18. 2018Concentration bounds for two time scale stochastic approximationcited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 10; 2022: 5; 2023: 8; 2024: 8; 2025: 7; 2026: 1.

39 papers.

Sort:

  1. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
  2. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
  3. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 44
  4. 2022Finite-time analysis of single-timescale actor-criticcited by 30
  5. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithmcited by 26
  6. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 24
  7. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  8. 2021A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learningcited by 20
  9. 2021Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatchcited by 17
  10. 2021Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processescited by 14
  11. 2023Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noisecited by 14
  12. 2021Actor-critic is implicitly biased towards high entropy optimal policiescited by 13
27 more
  1. 2022Finite-Time Analysis of Natural Actor-Critic for POMDPscited by 12
  2. 2023Policy Mirror Descent Inherently Explores Action Spacecited by 11
  3. 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterizationcited by 11
  4. 2021Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noisecited by 10
  5. 2022Global Convergence of Two-timescale Actor-Critic for Solving Linear Quadratic Regulatorcited by 8
  6. 2024Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applicationscited by 7
  7. 2024Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexitycited by 7
  8. 2024Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximationcited by 7
  9. 2021Wasserstein Flow Meets Replicator Dynamics: A Mean-Field Analysis of Representation Learning in Actor-Criticcited by 5
  10. 2022An Approximate Policy Iteration Viewpoint of Actor-Critic Algorithmscited by 3
  11. 2023Decision-Aware Actor-Critic with Function Approximation and Theoretical Guaranteescited by 3
  12. 2025On the Convergence of Policy Mirror Descent with Temporal Difference Evaluationcited by 3
  13. 2025A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policiescited by 3
  14. 2021Global Convergence of the ODE Limit for Online Actor-Critic Algorithms in Reinforcement Learningcited by 2
  15. 2023Warm-Start Actor-Critic: From Approximation Error to Sub-optimality Gapcited by 2
  16. 2023Finite-Time Analysis of Three-Timescale Constrained Actor-Critic and Constrained Natural Actor-Critic Algorithmscited by 2
  17. 2023Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptionscited by 2
  18. 2025Auto-exploration for online reinforcement learningcited by 2
  19. 2025Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Datacited by 2
  20. 2024Natural Policy Gradient and Actor Critic Methods for Constrained Multi-Task Reinforcement Learningcited by 0
  21. 2024Linear Function Approximation as a Computationally Efficient Method to Solve Classical Reinforcement Learning Challengescited by 0
  22. 2024Heavy-Ball Momentum Accelerated Actor-Critic With Function Approximationcited by 0
  23. 2024Last-Iterate Convergence of General Parameterized Policies in Constrained MDPscited by 0
  24. 2025Context-aware Constrained Reinforcement Learning Based Energy-Efficient Power Scheduling for Non-stationary XR Data Trafficcited by 0
  25. 2025Natural Policy Gradient for Average Reward Non-Stationary RLcited by 0
  26. 2025Finite Time Analysis of Constrained Natural Critic-Actor Algorithm with Improved Sample Complexitycited by 0
  27. 2026A Concentration Bound for Two-Timescale Actor-Critic Algorithmcited by 0