mlsanityData to 7 Oct 2026

A Small Gain Analysis of Single Timescale Actor Critic

arXiv 2203.02591 ↗First posted 4 Mar 2022math.OC cs.LG cs.SYcited by 22

Not on the map. Why?

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.

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

Builds on

15 of 37 references.

References · 15

  1. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  2. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  3. 2016Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphscited by 149
  4. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 141
  5. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 120
  6. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 117
  7. 2019An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradientcited by 58
  8. 2019On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximationcited by 54
  9. 2020Policy Gradient Methods for the Noisy Linear Quadratic Regulator over a Finite Horizoncited by 43
  10. 2020Single-Timescale Actor-Critic Provably Finds Globally Optimal Policycited by 34
  11. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithmcited by 26
  12. 2020Temporal Difference Learning as Gradient Splittingcited by 21
3 more
  1. 2021Analysis of a Target-Based Actor-Critic Algorithm with Linear Function Approximationcited by 13
  2. 2019Online Reinforcement Learning of Optimal Threshold Policies for Markov Decision Processescited by 7
  3. 2020Optimal Lockdown for Pandemic Controlcited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 4; 2023: 3; 2024: 6; 2025: 6; 2026: 3.

22 papers.

Sort:

By area:

  1. 2022Finite-time analysis of single-timescale actor-criticcited by 30
  2. 2022A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequencescited by 17
  3. 2025Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Setcited by 11
  4. 2022Global Convergence of Two-timescale Actor-Critic for Solving Linear Quadratic Regulatorcited by 8
  5. 2024Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learningcited by 8
  6. 2024Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximationcited by 7
  7. 2023On the Second-Order Convergence of Biased Policy Gradient Algorithmscited by 5
  8. 2024One-Shot Averaging for Distributed TD(λ) Under Markov Samplingcited by 4
  9. 2023Decision-Aware Actor-Critic with Function Approximation and Theoretical Guaranteescited 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. 2023Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptionscited by 2
10 more
  1. 2025Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Datacited by 2
  2. 2022Finite-Time Analysis of Fully Decentralized Single-Timescale Actor-Criticcited by 1
  3. 2025Stabilizing Policy Gradient Methods via Reward Profilingcited by 1
  4. 2026Refined Analysis of Entropy-Regularized Actor-Criticcited by 1
  5. 2024Heavy-Ball Momentum Accelerated Actor-Critic With Function Approximationcited by 0
  6. 2025Global Optimality of Single-Timescale Actor-Critic under Continuous State-Action Space: A Study on Linear Quadratic Regulatorcited by 0
  7. 2025Finite Time Analysis of Constrained Natural Critic-Actor Algorithm with Improved Sample Complexitycited by 0
  8. 2025Finite-time Convergence Analysis of Actor-Critic with Evolving Rewardcited by 0
  9. 2026Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentumcited by 0
  10. 2026An analysis of Mirror-Descent Soft Actor-Criticcited by 0