mlsanityData to 14 Oct 2026

On the Convergence of Single-Timescale Actor-Critic

arXiv 2410.08868 ↗First posted 11 Oct 2024cs.LG stat.MLcited by 3

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

We analyze the global convergence of the single-timescale actor-critic (AC) algorithm for the infinite-horizon discounted Markov Decision Processes (MDPs) with finite state spaces. To this end, we introduce an elegant analytical framework for handling complex, coupled recursions inherent in the algorithm. Leveraging this framework, we establish that the algorithm converges to an ε-close globally optimal policy with a sample complexity of ( O(ε-3) ). This significantly improves upon the existing complexity of O(ε-2) to achieve ε-close stationary policy, which is equivalent to the complexity of O(ε-4) to achieve ε-close globally optimal policy using gradient domination lemma. Furthermore, we demonstrate that to achieve this improvement, the step sizes for both the actor and critic must decay as ( O(k^-frac23) ) with iteration k, diverging from the conventional ( O(k^-frac12) ) rates commonly used in (non)convex optimization.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 22 of its 50 references that are in the map. First posted on arXiv 11 Oct 2024.

Builds on

22 of 50 references.

Closest ancestors · 2

Same direction, newest first

  1. 2024Optimistic Q-learning for average reward and episodic reinforcement learning18 Jul
  2. 2024Elementary Analysis of Policy Gradient Methods4 Apr

Other references · 20

  1. 2015Trust Region Policy Optimizationcited by 2,580
  2. 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,353
  3. 2019Solving Rubik's Cube with a Robot Handcited by 734
  4. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  5. 2018Is Q-learning Provably Efficient?cited by 487
  6. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  7. 2017Equivalence Between Policy Gradients and Soft Q-Learningcited by 173
  8. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
  9. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 150
  10. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 124
  11. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 122
  12. 2022On the Convergence Rates of Policy Gradient Methodscited by 119
8 more
  1. 2021A general sample complexity analysis of vanilla policy gradientcited by 76
  2. 2019An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradientcited by 59
  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. 2022Finite-time analysis of single-timescale actor-criticcited by 32
  6. 2022A Small Gain Analysis of Single Timescale Actor Criticcited by 24
  7. 2019On the Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Costcited by 12
  8. 2022Global Convergence of Two-timescale Actor-Critic for Solving Linear Quadratic Regulatorcited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Refined Analysis of Entropy-Regularized Actor-Criticcited by 1
  2. 2026Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentumcited by 0
  3. 2026An analysis of Mirror-Descent Soft Actor-Criticcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Convergence of an actor-critic gradient flow for entropy regularised MDPs in general spaces
  2. 2025Global Optimality of Single-Timescale Actor-Critic under Continuous State-Action Space: A Study on Linear Quadratic Regulator
  3. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm
  4. 2025Finite-time Convergence Analysis of Actor-Critic with Evolving Reward
  5. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
  6. 2026Global Convergence of Average Reward Constrained MDPs with Neural Critic and General Policy Parameterization
  7. 2024Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation
  8. 2026Achieving ε-2 Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions