# Finite-time analysis of single-timescale actor-critic

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 45 references that are in the map.
- First posted on arXiv 18 Oct 2022.

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

- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [Global Optimality Guarantees For Policy Gradient Methods](https://mlsanity.com/paper/1906.01786/) (2019)
- [A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic](https://mlsanity.com/paper/2007.05170/) (2020)
- [Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies](https://mlsanity.com/paper/1906.08383/) (2019)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1806.05618/) (2018)
- [Finite-Sample Analysis for SARSA with Linear Function Approximation](https://mlsanity.com/paper/1902.02234/) (2019)
- [Derivative-Free Methods for Policy Optimization: Guarantees for Linear Quadratic Systems](https://mlsanity.com/paper/1812.08305/) (2018)
- [Sample Efficient Policy Gradient Methods with Recursive Variance Reduction](https://mlsanity.com/paper/1909.08610/) (2019)
- [An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1905.12615/) (2019)
- [On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/1910.08412/) (2019)
- [Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms](https://mlsanity.com/paper/2005.03557/) (2020)
- [Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2101.10506/) (2021)
- [Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy](https://mlsanity.com/paper/2008.00483/) (2020)
- [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)
- [Single Time-scale Actor-critic Method to Solve the Linear Quadratic Regulator with Convergence Guarantees](https://mlsanity.com/paper/2202.00048/) (2022)
- [Finite-Time Analysis for Double Q-learning](https://mlsanity.com/paper/2009.14257/) (2020)
- [Global Convergence of Two-timescale Actor-Critic for Solving Linear Quadratic Regulator](https://mlsanity.com/paper/2208.08744/) (2022)

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

- [Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Critic](https://mlsanity.com/paper/2301.12083/) (2023)
- [A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach](https://mlsanity.com/paper/2407.18878/) (2024)
- [Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Set](https://mlsanity.com/paper/2501.19254/) (2025)
- [Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learning](https://mlsanity.com/paper/2405.09660/) (2024)
- [Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximation](https://mlsanity.com/paper/2402.01371/) (2024)
- [Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach](https://mlsanity.com/paper/2505.19986/) (2025)
- [On the Global Convergence of Natural Actor-Critic with Two-layer Neural Network Parametrization](https://mlsanity.com/paper/2306.10486/) (2023)
- [Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterization](https://mlsanity.com/paper/2602.08000/) (2026)
- [On the Global Convergence of Fitted Q-Iteration with Two-layer Neural Network Parametrization](https://mlsanity.com/paper/2211.07675/) (2022)
- [Learning in Herding Mean Field Games: Single-Loop Algorithm with Finite-Time Convergence Analysis](https://mlsanity.com/paper/2408.04780/) (2024)
- [On the Convergence of Single-Timescale Actor-Critic](https://mlsanity.com/paper/2410.08868/) (2024)
- [On The Global Convergence Of Online RLHF With Neural Parametrization](https://mlsanity.com/paper/2410.15610/) (2024)
- [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)
- [Global Optimality of Single-Timescale Actor-Critic under Continuous State-Action Space: A Study on Linear Quadratic Regulator](https://mlsanity.com/paper/2505.01041/) (2025)
- [Finite-time Convergence Analysis of Actor-Critic with Evolving Reward](https://mlsanity.com/paper/2510.12334/) (2025)
- [Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Data](https://mlsanity.com/paper/2512.24056/) (2025)
- [Policy Gradient with Tree Search: Avoiding Local Optimas through Lookahead](https://mlsanity.com/paper/2506.07054/) (2025)
- [Refined Analysis of Entropy-Regularized Actor-Critic](https://mlsanity.com/paper/2605.24357/) (2026)
- [A Single-Loop Deep Actor-Critic Algorithm for Constrained Reinforcement Learning with Provable Convergence](https://mlsanity.com/paper/2306.06402/) (2023)
- [Heavy-Ball Momentum Accelerated Actor-Critic With Function Approximation](https://mlsanity.com/paper/2408.06945/) (2024)
- [Single-Loop Federated Actor-Critic across Heterogeneous Environments](https://mlsanity.com/paper/2412.14555/) (2024)
- [Natural Policy Gradient for Average Reward Non-Stationary RL](https://mlsanity.com/paper/2504.16415/) (2025)
- [LOD: Latent Objective Discovery in Heterogeneous Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2505.09756/) (2025)
- [Signal attenuation enables scalable decentralized multi-agent reinforcement learning over networks](https://mlsanity.com/paper/2505.11461/) (2025)
- [Quantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein Subdifferential](https://mlsanity.com/paper/2510.02735/) (2025)
- [Finite Time Analysis of Constrained Natural Critic-Actor Algorithm with Improved Sample Complexity](https://mlsanity.com/paper/2510.04189/) (2025)
- [Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentum](https://mlsanity.com/paper/2602.01505/) (2026)
- [Bias-Controlled Primal-Dual Natural Actor-Critic: Optimal Rates for Constrained Multi-Objective Average-Reward RL](https://mlsanity.com/paper/2606.25012/) (2026)
- [Hypergradient-based Bilevel Reinforcement Learning with Improved Sample Complexity](https://mlsanity.com/paper/2607.28849/) (2026)

## Abstract (arXiv)

Actor-critic methods have achieved significant success in many challenging applications. However, its finite-time convergence is still poorly understood in the most practical single-timescale form. Existing works on analyzing single-timescale actor-critic have been limited to i.i.d. sampling or tabular setting for simplicity. We investigate the more practical online single-timescale actor-critic algorithm on continuous state space, where the critic assumes linear function approximation and updates with a single Markovian sample per actor step. Previous analysis has been unable to establish the convergence for such a challenging scenario. We demonstrate that the online single-timescale actor-critic method provably finds an ε-approximate stationary point with widetildeO(ε-2) sample complexity under standard assumptions, which can be further improved to O(ε-2) under the i.i.d. sampling. Our novel framework systematically evaluates and controls the error propagation between the actor and critic. It offers a promising approach for analyzing other single-timescale reinforcement learning algorithms as well.