# On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximation

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

## Key facts

- Cited by 54 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Oct 2019.

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

- [Recent Advances in Reinforcement Learning in Finance](https://mlsanity.com/paper/2112.04553/) (2021)
- [Online Robust Reinforcement Learning with Model Uncertainty](https://mlsanity.com/paper/2109.14523/) (2021)
- [A general sample complexity analysis of vanilla policy gradient](https://mlsanity.com/paper/2107.11433/) (2021)
- [Reinforcement Learning for Selective Key Applications in Power Systems: Recent Advances and Future Challenges](https://mlsanity.com/paper/2102.01168/) (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)
- [A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning](https://mlsanity.com/paper/2109.14756/) (2021)
- [A Small Gain Analysis of Single Timescale Actor Critic](https://mlsanity.com/paper/2203.02591/) (2022)
- [Learning to Optimize Multi-Objective Alignment Through Dynamic Reward Weighting](https://mlsanity.com/paper/2509.11452/) (2025)
- [Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximation](https://mlsanity.com/paper/2105.12540/) (2021)
- [Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2206.00833/) (2022)
- [Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Critic](https://mlsanity.com/paper/2301.12083/) (2023)
- [Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatch](https://mlsanity.com/paper/2111.02997/) (2021)
- [A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequences](https://mlsanity.com/paper/2206.10414/) (2022)
- [Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilities](https://mlsanity.com/paper/2305.17568/) (2023)
- [Analysis of a Target-Based Actor-Critic Algorithm with Linear Function Approximation](https://mlsanity.com/paper/2106.07472/) (2021)
- [When Will Generative Adversarial Imitation Learning Algorithms Attain Global Convergence](https://mlsanity.com/paper/2006.13506/) (2020)
- [Distributed TD(0) with Almost No Communication](https://mlsanity.com/paper/2305.16246/) (2023)
- [Global Convergence of Two-timescale Actor-Critic for Solving Linear Quadratic Regulator](https://mlsanity.com/paper/2208.08744/) (2022)
- [A Cubic-regularized Policy Newton Algorithm for Reinforcement Learning](https://mlsanity.com/paper/2304.10951/) (2023)
- [Efficient Reinforcement Learning for Routing Jobs in Heterogeneous Queueing Systems](https://mlsanity.com/paper/2402.01147/) (2024)
- [Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles](https://mlsanity.com/paper/2403.11925/) (2024)
- [Convergence and Optimality of Policy Gradient Methods in Weakly Smooth Settings](https://mlsanity.com/paper/2111.00185/) (2021)
- [Data Sampling Affects the Complexity of Online SGD over Dependent Data](https://mlsanity.com/paper/2204.00006/) (2022)
- [On the Second-Order Convergence of Biased Policy Gradient Algorithms](https://mlsanity.com/paper/2311.02546/) (2023)
- [Reusing Historical Trajectories in Natural Policy Gradient via Importance Sampling: Convergence and Convergence Rate](https://mlsanity.com/paper/2403.00675/) (2024)
- [An Approximate Policy Iteration Viewpoint of Actor-Critic Algorithms](https://mlsanity.com/paper/2208.03247/) (2022)

## Abstract (arXiv)

Reinforcement learning, mathematically described by Markov Decision Problems, may be approached either through dynamic programming or policy search. Actor-critic algorithms combine the merits of both approaches by alternating between steps to estimate the value function and policy gradient updates. Due to the fact that the updates exhibit correlated noise and biased gradient updates, only the asymptotic behavior of actor-critic is known by connecting its behavior to dynamical systems. This work puts forth a new variant of actor-critic that employs Monte Carlo rollouts during the policy search updates, which results in controllable bias that depends on the number of critic evaluations. As a result, we are able to provide for the first time the convergence rate of actor-critic algorithms when the policy search step employs policy gradient, agnostic to the choice of policy evaluation technique. In particular, we establish conditions under which the sample complexity is comparable to stochastic gradient method for non-convex problems or slower as a result of the critic estimation error, which is the main complexity bottleneck. These results hold in continuous state and action spaces with linear function approximation for the value function. We then specialize these conceptual results to the case where the critic is estimated by Temporal Difference, Gradient Temporal Difference, and Accelerated Gradient Temporal Difference. These learning rates are then corroborated on a navigation problem involving an obstacle and the pendulum problem which provide insight into the interplay between optimization and generalization in reinforcement learning.