mlsanityData to 7 Oct 2026

Finite-time analysis of single-timescale actor-critic

arXiv 2210.09921 ↗First posted 18 Oct 2022cs.LG math.OC stat.MLcited by 30

Not on the map. Why?

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.

Key facts. Cited by 30 papers in the map (data through 7 Oct 2026). Builds on 23 of its 45 references that are in the map. First posted on arXiv 18 Oct 2022.

Builds on

23 of 45 references.

References · 23

  1. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,218
  2. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  3. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 211
  4. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  5. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  6. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 146
  7. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 141
  8. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 120
  9. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 117
  10. 2018Stochastic Variance-Reduced Policy Gradientcited by 103
  11. 2019Finite-Sample Analysis for SARSA with Linear Function Approximationcited by 85
  12. 2019An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradientcited by 58
11 more
  1. 2019Sample Efficient Policy Gradient Methods with Recursive Variance Reductioncited by 58
  2. 2018Derivative-Free Methods for Policy Optimization: Guarantees for Linear Quadratic Systemscited by 56
  3. 2019On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximationcited by 54
  4. 2020Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithmscited by 43
  5. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  6. 2020Single-Timescale Actor-Critic Provably Finds Globally Optimal Policycited by 34
  7. 2022A Small Gain Analysis of Single Timescale Actor Criticcited by 22
  8. 2021A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learningcited by 20
  9. 2020Finite-Time Analysis for Double Q-learningcited by 12
  10. 2022Single Time-scale Actor-critic Method to Solve the Linear Quadratic Regulator with Convergence Guaranteescited by 9
  11. 2022Global Convergence of Two-timescale Actor-Critic for Solving Linear Quadratic Regulatorcited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 5; 2024: 7; 2025: 11; 2026: 6.

30 papers.

Sort:

By area:

  1. 2023Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Criticcited by 18
  2. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approachcited by 14
  3. 2025Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Setcited by 11
  4. 2024Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learningcited by 8
  5. 2024Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximationcited by 7
  6. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approachcited by 6
  7. 2023On the Global Convergence of Natural Actor-Critic with Two-layer Neural Network Parametrizationcited by 5
  8. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterizationcited by 4
  9. 2022On the Global Convergence of Fitted Q-Iteration with Two-layer Neural Network Parametrizationcited by 3
  10. 2024On the Convergence of Single-Timescale Actor-Criticcited by 3
  11. 2024On The Global Convergence Of Online RLHF With Neural Parametrizationcited by 3
  12. 2023Finite-Time Analysis of Three-Timescale Constrained Actor-Critic and Constrained Natural Actor-Critic Algorithmscited by 2
18 more
  1. 2023Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptionscited by 2
  2. 2025Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Datacited by 2
  3. 2025Policy Gradient with Tree Search: Avoiding Local Optimas through Lookaheadcited by 1
  4. 2026Refined Analysis of Entropy-Regularized Actor-Criticcited by 1
  5. 2023A Single-Loop Deep Actor-Critic Algorithm for Constrained Reinforcement Learning with Provable Convergencecited by 0
  6. 2024Heavy-Ball Momentum Accelerated Actor-Critic With Function Approximationcited by 0
  7. 2024Single-Loop Federated Actor-Critic across Heterogeneous Environmentscited by 0
  8. 2025Natural Policy Gradient for Average Reward Non-Stationary RLcited by 0
  9. 2025Global Optimality of Single-Timescale Actor-Critic under Continuous State-Action Space: A Study on Linear Quadratic Regulatorcited by 0
  10. 2025LOD: Latent Objective Discovery in Heterogeneous Multi-Agent Reinforcement Learningcited by 0
  11. 2025Signal attenuation enables scalable decentralized multi-agent reinforcement learning over networkscited by 0
  12. 2025Quantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein Subdifferentialcited by 0
  13. 2025Finite Time Analysis of Constrained Natural Critic-Actor Algorithm with Improved Sample Complexitycited by 0
  14. 2025Finite-time Convergence Analysis of Actor-Critic with Evolving Rewardcited by 0
  15. 2026Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentumcited by 0
  16. 2026Bias-Controlled Primal-Dual Natural Actor-Critic: Optimal Rates for Constrained Multi-Objective Average-Reward RLcited by 0
  17. 2026Hypergradient-based Bilevel Reinforcement Learning with Improved Sample Complexitycited by 0
  18. 2026A Concentration Bound for Two-Timescale Actor-Critic Algorithmcited by 0