# Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Aug 2020.

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

- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning](https://mlsanity.com/paper/2108.08812/) (2021)
- [Recent Advances in Reinforcement Learning in Finance](https://mlsanity.com/paper/2112.04553/) (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)
- [Mean-Field Multi-Agent Reinforcement Learning: A Decentralized Network Approach](https://mlsanity.com/paper/2108.02731/) (2021)
- [On the Global Optimum Convergence of Momentum-based Policy Gradient](https://mlsanity.com/paper/2110.10116/) (2021)
- [A Small Gain Analysis of Single Timescale Actor Critic](https://mlsanity.com/paper/2203.02591/) (2022)
- [Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problems](https://mlsanity.com/paper/2106.13781/) (2021)
- [Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality](https://mlsanity.com/paper/2102.11866/) (2021)
- [Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2206.00833/) (2022)
- [Stochastic Control for Fine-tuning Diffusion Models: Optimality, Regularity, and Convergence](https://mlsanity.com/paper/2412.18164/) (2024)
- [A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequences](https://mlsanity.com/paper/2206.10414/) (2022)
- [Single Time-scale Actor-critic Method to Solve the Linear Quadratic Regulator with Convergence Guarantees](https://mlsanity.com/paper/2202.00048/) (2022)
- [On The Sample Complexity Bounds In Bilevel Reinforcement Learning](https://mlsanity.com/paper/2503.17644/) (2025)
- [Global Convergence of Two-timescale Actor-Critic for Solving Linear Quadratic Regulator](https://mlsanity.com/paper/2208.08744/) (2022)
- [Wasserstein Flow Meets Replicator Dynamics: A Mean-Field Analysis of Representation Learning in Actor-Critic](https://mlsanity.com/paper/2112.13530/) (2021)
- [On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correction](https://mlsanity.com/paper/2106.00993/) (2021)
- [Towards Global Optimality in Cooperative MARL with the Transformation And Distillation Framework](https://mlsanity.com/paper/2207.11143/) (2022)
- [Policy Gradient Converges to the Globally Optimal Policy for Nearly Linear-Quadratic Regulators](https://mlsanity.com/paper/2303.08431/) (2023)
- [On the Global Convergence of Natural Actor-Critic with Two-layer Neural Network Parametrization](https://mlsanity.com/paper/2306.10486/) (2023)
- [On the Second-Order Convergence of Biased Policy Gradient Algorithms](https://mlsanity.com/paper/2311.02546/) (2023)
- [Decision-Aware Actor-Critic with Function Approximation and Theoretical Guarantees](https://mlsanity.com/paper/2305.15249/) (2023)
- [On The Global Convergence Of Online RLHF With Neural Parametrization](https://mlsanity.com/paper/2410.15610/) (2024)
- [Warm-Start Actor-Critic: From Approximation Error to Sub-optimality Gap](https://mlsanity.com/paper/2306.11271/) (2023)
- [Improved Sample Complexity For Diffusion Model Training Without Empirical Risk Minimizer Access](https://mlsanity.com/paper/2505.18344/) (2025)
- [Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Data](https://mlsanity.com/paper/2512.24056/) (2025)
- [Finite-Time Analysis of Fully Decentralized Single-Timescale Actor-Critic](https://mlsanity.com/paper/2206.05733/) (2022)
- [Understanding Inverse Reinforcement Learning under Overparameterization: Non-Asymptotic Analysis and Global Optimality](https://mlsanity.com/paper/2503.17865/) (2025)
- [Global Convergence of Average Reward Constrained MDPs with Neural Critic and General Policy Parameterization](https://mlsanity.com/paper/2603.07698/) (2026)

## Abstract (arXiv)

We study the global convergence and global optimality of actor-critic, one of the most popular families of reinforcement learning algorithms. While most existing works on actor-critic employ bi-level or two-timescale updates, we focus on the more practical single-timescale setting, where the actor and critic are updated simultaneously. Specifically, in each iteration, the critic update is obtained by applying the Bellman evaluation operator only once while the actor is updated in the policy gradient direction computed using the critic. Moreover, we consider two function approximation settings where both the actor and critic are represented by linear or deep neural networks. For both cases, we prove that the actor sequence converges to a globally optimal policy at a sublinear O(K-1/2) rate, where K is the number of iterations. To the best of our knowledge, we establish the rate of convergence and global optimality of single-timescale actor-critic with linear function approximation for the first time. Moreover, under the broader scope of policy optimization with nonlinear function approximation, we prove that actor-critic with deep neural network finds the globally optimal policy at a sublinear rate for the first time.