A Concentration Bound for Two-Timescale Actor-Critic Algorithm

Prashansa Panda; Shalabh Bhatnagar

cs.LGSep 24, 2026

A Concentration Bound for Two-Timescale Actor-Critic Algorithm

Authors: Prashansa Panda, Shalabh Bhatnagar

Organizations: Department of Computer Science and Automation IISc Bangalore

Abstract

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 $O\left(\frac{n_0^{3/4}}{k}\frac{1}{\sqrt{ε_2}}+\left(\frac{1}{n_0}\right)^{1/4}\log^{1/4}\left(\frac{1}{ε_1}\right)+\left(\frac{1}{n_0}\right)^{1/4}\right)$ for all $k\geq n_0$ and sufficiently large $n_0$ . We also present experimental results demonstrating that the aforementioned actor error diminishes with the number of actor-parameter updates.

Figures & tables

Figure 1: Dependency of errors in the analysis of actor critic algorithm for concentration bound

Figure 2: Convergence of $\|\theta_{t}-\theta^{*}\|$ averaged over ten independent runs

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

	CartPole-v1	FrozenLake-v1	Blackjack-v1
Actions $\|A\|$	2 (push left / right)	4 (up/down/left/right)	2 (stick / hit)
Actor parameterization	binary logistic: $\pi(a{=}0\|s)=\sigma(\theta^{\top}\phi(s))$ $\theta\in\mathbb{R}^{11}$	tabular softmax, one logit anchored per state $\theta\in\mathbb{R}^{3\times 16}$	binary logistic $\theta\in\mathbb{R}^{7}$
Critic parameter $v$	$v\in\mathbb{R}^{11}$	$v\in\mathbb{R}^{16}$	$v\in\mathbb{R}^{7}$
Feature map $\phi(s)$	bias, 4 normalized state dims, their squares, 2 cross terms	exact one-hot over the 16 discrete states	bias, normalized player sum, dealer card, ace indicator, their squares, 1 cross term
Approximation	linear FA	tabular	linear FA
Critic step-size $\alpha_{t}$	$5.0/(t+50)^{0.5}$	$5.0/(t+50)^{0.5}$	$1.0/(t+1)^{0.5}$

Appendix

Table 1: Actor and critic architecture and step-size (learning-rate) schedule used in each environment.

Explore similar work

Convergence of Two-Timescale Markovian Stochastic Approximations with Applications in Reinforcement Learning
May 29, 2026Vagul Mahadevan, Claire Chen, Shuze Daniel Liu +1Stochastic Approximation Temporal Difference
Metron, Reston, VA, USA · Division Office Physics, Math and Astronomy, California Institute of Technology, Pasadena, CA, USA · Data Science Lab, MIT, Cambridge, MA, USA +2
Refined Analysis of Entropy-Regularized Actor-Critic
May 23, 2026Safwan Labbi, Paul Mangold, Daniil Tiapkin +1Entropy Regularized Reinforcement Learning Soft Actor-Critic
CMAP, CNRS, École Polytechnique, Institut Polytechnique de Paris, 91120 Palaiseau, France · Université Paris-Saclay, CNRS, LMO, 91405, Orsay, France · Google DeepMind +2
Deconstructing Actor-Critic: A Large-scale Empirical Study of Design Components for Practitioners
Jul 14, 2026Haseeb Shah, Lingwei Zhu, Adam White +1Soft Actor-Critic Gaussian Primitives
Department of Computing Science, University of Alberta, Canada · Alberta Machine Intelligence Institute (amii), Canada · Great Bay University, China +1

May 29, 2026, cs.LGJ/K move · Enter open · S save

Convergence of Two-Timescale Markovian Stochastic Approximations with Applications in Reinforcement Learning

Vagul Mahadevan, Claire Chen, Shuze Daniel Liu, Shangtong Zhang

Metron, Reston, VA, USA · Division Office Physics, Math and Astronomy, California Institute of Technology, Pasadena, CA, USA · Data Science Lab, MIT, Cambridge, MA, USA+2

Stochastic Approximation Temporal Difference Soft Actor-Critic Convergence Timescale

Open paper AskPDF arXiv

This work studies the convergence of two-timescale stochastic approximations (SA), a class of iterative algorithms that update two sets of parameters in fast and slow timescales respectively. Notable examples of two-timescale SA in reinforcement learning (RL) include temporal difference learning with gradient correction (TDC) and actor-critic methods. Previously, the stability (i.e., boundedness) and convergence of two-timescale SA were only established under i.i.d. noise. This work instead establishes the stability and convergence of two-timescale SA under Markovian noise, a setup that is more realistic in RL. Notably, we do not need to use any projection operator and the noise does not need to live in a compact space. Our key technical novelty is to control the fast timescale parameter with the running max of the slow timescale parameter, instead of with the current slow timescale parameter, as most prior works do. As a key application, we establish the first almost sure convergence of TDC with eligibility traces under off-policy learning with linear function approximation.

Abstract

Explore similar work

Convergence of Two-Timescale Markovian Stochastic Approximations with Applications in Reinforcement Learning

Refined Analysis of Entropy-Regularized Actor-Critic

Deconstructing Actor-Critic: A Large-scale Empirical Study of Design Components for Practitioners