# A Small Gain Analysis of Single Timescale Actor Critic

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 37 references that are in the map.
- First posted on arXiv 4 Mar 2022.

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

- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [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)
- [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)
- [Policy Gradient Methods for the Noisy Linear Quadratic Regulator over a Finite Horizon](https://mlsanity.com/paper/2011.10300/) (2020)
- [Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy](https://mlsanity.com/paper/2008.00483/) (2020)
- [Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2102.09318/) (2021)
- [Temporal Difference Learning as Gradient Splitting](https://mlsanity.com/paper/2010.14657/) (2020)
- [Analysis of a Target-Based Actor-Critic Algorithm with Linear Function Approximation](https://mlsanity.com/paper/2106.07472/) (2021)
- [Online Reinforcement Learning of Optimal Threshold Policies for Markov Decision Processes](https://mlsanity.com/paper/1912.10325/) (2019)
- [Optimal Lockdown for Pandemic Control](https://mlsanity.com/paper/2010.12923/) (2020)

## Built on by (most cited first, 24 of 24)

- [Finite-time analysis of single-timescale actor-critic](https://mlsanity.com/paper/2210.09921/) (2022)
- [A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequences](https://mlsanity.com/paper/2206.10414/) (2022)
- [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)
- [Global Convergence of Two-timescale Actor-Critic for Solving Linear Quadratic Regulator](https://mlsanity.com/paper/2208.08744/) (2022)
- [Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximation](https://mlsanity.com/paper/2402.01371/) (2024)
- [On the Second-Order Convergence of Biased Policy Gradient Algorithms](https://mlsanity.com/paper/2311.02546/) (2023)
- [One-Shot Averaging for Distributed TD(λ) Under Markov Sampling](https://mlsanity.com/paper/2403.08896/) (2024)
- [Decision-Aware Actor-Critic with Function Approximation and Theoretical Guarantees](https://mlsanity.com/paper/2305.15249/) (2023)
- [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)
- [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)
- [Finite-Time Analysis of Fully Decentralized Single-Timescale Actor-Critic](https://mlsanity.com/paper/2206.05733/) (2022)
- [Stabilizing Policy Gradient Methods via Reward Profiling](https://mlsanity.com/paper/2511.16629/) (2025)
- [Refined Analysis of Entropy-Regularized Actor-Critic](https://mlsanity.com/paper/2605.24357/) (2026)
- [Heavy-Ball Momentum Accelerated Actor-Critic With Function Approximation](https://mlsanity.com/paper/2408.06945/) (2024)
- [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)
- [An analysis of Mirror-Descent Soft Actor-Critic](https://mlsanity.com/paper/2609.35466/) (2026)
- [Towards Understanding the Training of GFlowNets: A Theoretical Perspective](https://mlsanity.com/paper/2610.13711/) (2026)

## Abstract (arXiv)

We consider a version of actor-critic which uses proportional step-sizes and only one critic update with a single sample from the stationary distribution per actor step. We provide an analysis of this method using the small-gain theorem. Specifically, we prove that this method can be used to find a stationary point, and that the resulting sample complexity improves the state of the art for actor-critic methods to O left(μ-2 ε-2 right) to find an ε-approximate stationary point where μ is the condition number associated with the critic.