# On the Convergence of Single-Timescale Actor-Critic

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

## 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.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Solving Rubik's Cube with a Robot Hand](https://mlsanity.com/paper/1910.07113/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Equivalence Between Policy Gradients and Soft Q-Learning](https://mlsanity.com/paper/1704.06440/) (2017)
- [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)
- [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)
- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [A general sample complexity analysis of vanilla policy gradient](https://mlsanity.com/paper/2107.11433/) (2021)
- [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-time analysis of single-timescale actor-critic](https://mlsanity.com/paper/2210.09921/) (2022)
- [A Small Gain Analysis of Single Timescale Actor Critic](https://mlsanity.com/paper/2203.02591/) (2022)
- [Elementary Analysis of Policy Gradient Methods](https://mlsanity.com/paper/2404.03372/) (2024)
- [On the Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Cost](https://mlsanity.com/paper/1907.06246/) (2019)
- [Optimistic Q-learning for average reward and episodic reinforcement learning](https://mlsanity.com/paper/2407.13743/) (2024)
- [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, 3 of 3)

- [Refined Analysis of Entropy-Regularized Actor-Critic](https://mlsanity.com/paper/2605.24357/) (2026)
- [Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentum](https://mlsanity.com/paper/2602.01505/) (2026)
- [An analysis of Mirror-Descent Soft Actor-Critic](https://mlsanity.com/paper/2609.35466/) (2026)

## 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.