# Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms

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

## Key facts

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

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

- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods](https://mlsanity.com/paper/2211.07937/) (2022)
- [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)
- [First-order Policy Optimization for Robust Markov Decision Process](https://mlsanity.com/paper/2209.10579/) (2022)
- [Policy Optimization over General State and Action Spaces](https://mlsanity.com/paper/2211.16715/) (2022)
- [Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2206.00833/) (2022)
- [Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process](https://mlsanity.com/paper/2110.10351/) (2021)
- [When Will Generative Adversarial Imitation Learning Algorithms Attain Global Convergence](https://mlsanity.com/paper/2006.13506/) (2020)
- [Wasserstein Flow Meets Replicator Dynamics: A Mean-Field Analysis of Representation Learning in Actor-Critic](https://mlsanity.com/paper/2112.13530/) (2021)
- [Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexity](https://mlsanity.com/paper/2401.12764/) (2024)
- [Convergence and Optimality of Policy Gradient Methods in Weakly Smooth Settings](https://mlsanity.com/paper/2111.00185/) (2021)
- [On the Second-Order Convergence of Biased Policy Gradient Algorithms](https://mlsanity.com/paper/2311.02546/) (2023)
- [Stochastic Gradient Descent with Adaptive Data](https://mlsanity.com/paper/2410.01195/) (2024)

## Abstract (arXiv)

The actor-critic (AC) algorithm is a popular method to find an optimal policy in reinforcement learning. In the infinite horizon scenario, the finite-sample convergence rate for the AC and natural actor-critic (NAC) algorithms has been established recently, but under independent and identically distributed (i.i.d.) sampling and single-sample update at each iteration. In contrast, this paper characterizes the convergence rate and sample complexity of AC and NAC under Markovian sampling, with mini-batch data for each iteration, and with actor having general policy class approximation. We show that the overall sample complexity for a mini-batch AC to attain an ε-accurate stationary point improves the best known sample complexity of AC by an order of O(ε-1log(1/ε)), and the overall sample complexity for a mini-batch NAC to attain an ε-accurate globally optimal point improves the existing sample complexity of NAC by an order of O(ε-1/log(1/ε)). Moreover, the sample complexity of AC and NAC characterized in this work outperforms that of policy gradient (PG) and natural policy gradient (NPG) by a factor of O((1-γ)-3) and O((1-γ)-4ε-1/log(1/ε)), respectively. This is the first theoretical study establishing that AC and NAC attain orderwise performance improvement over PG and NPG under infinite horizon due to the incorporation of critic.