A Concentration Bound for Two-Timescale Actor-Critic Algorithm
On the map: Deep reinforcement learning methods → RL theory and sample complexity
Abstract (arXiv)
Significant research effort has been directed in recent years towards establishing both asymptotic and non-asymptotic convergence guarantees for two-timescale actor--critic algorithms, where the actor recursion is run on a slower timescale than the critic recursion. This work derives a uniform all-time concentration bound for the actor--critic algorithm with function approximation in the long-run average-reward setting. This bound helps us analyze the behavior of the actor parameter with high probability. We show that, after some finite time, the actor parameter enters a safe region and remains within it thereafter with high probability. Specifically, with probability at least 1-ε1-ε2, the actor error Vert θk-θ*Vert is Oleft(fracn03/4kfrac1√ε2+left(frac1n0right)1/4log1/4left(frac1ε1right)+left(frac1n0right)1/4right) for all k≥ n0 and sufficiently large n0. We also present experimental results demonstrating that the aforementioned actor error diminishes with the number of actor-parameter updates.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 9 of its 21 references that are in the map. First posted on arXiv 24 Sep 2026.
Builds on
9 of 21 references.
References · 9
- 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 122
- 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
- 2022Finite-time analysis of single-timescale actor-criticcited by 32
- 2014On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergencecited by 22
- 2015A Concentration Bound for Stochastic Approximation via Alekseev's Formulacited by 16
- 2023A Concentration Bound for TD(0) with Function Approximationcited by 10
- 2022Actor-Critic or Critic-Actor? A Tale of Two Time Scalescited by 7
- 2024Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximationcited by 7
- 2023Finite-Time Analysis of Three-Timescale Constrained Actor-Critic and Constrained Natural Actor-Critic Algorithmscited by 2
Built on by
Not cited yet.
Similar, not cited
Close in wording, no citation either way
- 2025Finite Time Analysis of Constrained Natural Critic-Actor Algorithm with Improved Sample Complexity
- 2025Finite-time Convergence Analysis of Actor-Critic with Evolving Reward
- 2024On the Convergence of Single-Timescale Actor-Critic
- 2024Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation
- 2024Closing the Gap: Achieving Global Convergence (Last Iterate) of Actor-Critic under Markovian Sampling with Neural Network Parametrization
- 2025Global Optimality of Single-Timescale Actor-Critic under Continuous State-Action Space: A Study on Linear Quadratic Regulator
- 2025Actor-Critics Can Achieve Optimal Sample Efficiency
- 2026Refined Analysis of Entropy-Regularized Actor-Critic