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

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

## Key facts

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

## Builds on (most cited first, 30 of 30)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Soft Actor-Critic Algorithms and Applications](https://mlsanity.com/paper/1812.05905/) (2018)
- [IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures](https://mlsanity.com/paper/1802.01561/) (2018)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Sample Efficient Actor-Critic with Experience Replay](https://mlsanity.com/paper/1611.01224/) (2016)
- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [An Actor-Critic Algorithm for Sequence Prediction](https://mlsanity.com/paper/1607.07086/) (2016)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs](https://mlsanity.com/paper/1909.02769/) (2019)
- [On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration](https://mlsanity.com/paper/2004.04719/) (2020)
- [Algorithms for multi-armed bandit problems](https://mlsanity.com/paper/1402.6028/) (2014)
- [The Information Geometry of Mirror Descent](https://mlsanity.com/paper/1310.7780/) (2013)
- [On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/1910.08412/) (2019)
- [Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2002.01268/) (2020)
- [Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy](https://mlsanity.com/paper/1906.10306/) (2019)
- [Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms](https://mlsanity.com/paper/2005.03557/) (2020)
- [Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy](https://mlsanity.com/paper/2008.00483/) (2020)
- [Finite-Sample Analysis of Proximal Gradient TD Algorithms](https://mlsanity.com/paper/2006.14364/) (2020)
- [Finite-Time Analysis and Restarting Scheme for Linear Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/1912.10583/) (2019)
- [Mirrorless Mirror Descent: A Natural Derivation of Mirror Descent](https://mlsanity.com/paper/2004.01025/) (2020)
- [Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms](https://mlsanity.com/paper/2004.12956/) (2020)
- [Convergent Actor-Critic Algorithms Under Off-Policy Training and Function Approximation](https://mlsanity.com/paper/1802.07842/) (2018)
- [Concentration bounds for two time scale stochastic approximation](https://mlsanity.com/paper/1806.10798/) (2018)

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

- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [On the Linear convergence of Natural Policy Gradient Algorithm](https://mlsanity.com/paper/2105.01424/) (2021)
- [Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies](https://mlsanity.com/paper/2210.01400/) (2022)
- [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)
- [Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processes](https://mlsanity.com/paper/2310.11677/) (2023)
- [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)
- [Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes](https://mlsanity.com/paper/2110.11383/) (2021)
- [Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatch](https://mlsanity.com/paper/2111.02997/) (2021)
- [Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2401.00364/) (2023)
- [Actor-critic is implicitly biased towards high entropy optimal policies](https://mlsanity.com/paper/2110.11280/) (2021)
- [Finite-Time Analysis of Natural Actor-Critic for POMDPs](https://mlsanity.com/paper/2202.09753/) (2022)
- [Policy Mirror Descent Inherently Explores Action Space](https://mlsanity.com/paper/2303.04386/) (2023)
- [Sample-Efficient Constrained Reinforcement Learning with General Parameterization](https://mlsanity.com/paper/2405.10624/) (2024)
- [Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noise](https://mlsanity.com/paper/2104.01627/) (2021)
- [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)
- [Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applications](https://mlsanity.com/paper/2401.09339/) (2024)
- [Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexity](https://mlsanity.com/paper/2401.12764/) (2024)
- [Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximation](https://mlsanity.com/paper/2402.01371/) (2024)
- [A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies](https://mlsanity.com/paper/2510.16132/) (2025)
- [An Approximate Policy Iteration Viewpoint of Actor-Critic Algorithms](https://mlsanity.com/paper/2208.03247/) (2022)
- [Decision-Aware Actor-Critic with Function Approximation and Theoretical Guarantees](https://mlsanity.com/paper/2305.15249/) (2023)
- [On the Convergence of Policy Mirror Descent with Temporal Difference Evaluation](https://mlsanity.com/paper/2509.18822/) (2025)
- [Auto-exploration for online reinforcement learning](https://mlsanity.com/paper/2512.06244/) (2025)
- [Global Convergence of the ODE Limit for Online Actor-Critic Algorithms in Reinforcement Learning](https://mlsanity.com/paper/2108.08655/) (2021)
- [Warm-Start Actor-Critic: From Approximation Error to Sub-optimality Gap](https://mlsanity.com/paper/2306.11271/) (2023)
- [Finite-Time Analysis of Three-Timescale Constrained Actor-Critic and Constrained Natural Actor-Critic Algorithms](https://mlsanity.com/paper/2310.16363/) (2023)
- [Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptions](https://mlsanity.com/paper/2312.08008/) (2023)

## 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.