On the Convergence of Continuous Single-timescale Actor-critic
Authors: Xuyang Chen
Lin Zhao
Venue: ICML 2025 poster (2025)
Keywords: single-timescale actor-critic
continuous state-action space
Markovian sampling
Primary area: theory->learning_theory
TL;DR: This paper establishes convergence guarantees for single-timescale actor-critic methods in continuous state-action spaces with Markovian sampling.

Abstract: Actor-critic algorithms have been instrumental in boosting the performance of numerous challenging applications involving continuous control, such as highly robust and agile robot motion control. However, their theoretical understanding remains largely underdeveloped. Existing analyses mostly focus on finite state-action spaces and on simplified variants of actor-critic, such as double-loop updates with i.i.d. sampling, which are often impractical for real-world applications.
We consider the canonical and widely adopted single-timescale updates with Markovian sampling in continuous state-action space. Specifically, we establish finite-time convergence by introducing a novel Lyapunov analysis framework, which provides a unified convergence characterization of both the actor and the critic. Our approach is less conservative than previous methods and offers new insights into the coupled dynamics of actor-critic updates.

On the Convergence of Continuous Single-timescale Actor-critic
Xuyang Chen
Lin Zhao
Abstract
to simplify the analysis, including the double-loop updates and the two-timescale updates. The doublc-loop updates perform multiple critic updates for a fixed actor (Yang et al., 2019; Kumar et al., 2023; Agarwal et al., 2021; Xu et al., 2020b). This facilitates more accurate value function estima- tion, which in turn enables a more precise policy gradient estimation for the fixed actor. It allows simple decou- pled analysis of the actor and the critic. However, such implementation is impractical due to the high sampling complexity. Another variant is the two-timescale actor-critic method (Wu et al., 2020; Xu et al., 2020c; Chen et al., 2023; Shen et al., 2023; Hong et al., 2023), which assigns a smaller step size for the actor than that of the critic, with their ratio converging to zero as the number of iterations approaches in- finity (i.e., lime az/ 3r = 0). allows an asymptotically decoupling of the actor and the critic in the convergence analysis, similar to performing multiple critic updates at fixed actor. However, such artificial slowing down of the critic update is often not desired in practice.
Actor-critic algorithms have been instrumental in boosting the performance of numerous chal- lenging applications involving continuous control, such as highly robust and agile robot motion con- trol. However, their theoretical understanding re- mains largely underdeveloped. Existing analyses mostly focus on finite state-action spaces and on simplified variants of actor-critic, such as double- loop updates with i.i.d. sampling, which are of- ten impractical for real-world applications. We consider the canonical and widely adopted single- timescale updates with Markovian sampling in continuous state-action space. Specifically, we establish finite-time convergence by introducing novel Lyapumov analysis framework, which pro- vides unified convergence characterization of both the actor and the critic. Our approach is less conservative than previous methods and of- fers new insights into the coupled dynamics of actor-critic updates.
The canonical and more practical implementation of actor- critic is the single-timescale update, where the actor and the critic are updated simultaneously with proportional step sizes at each iteration (i.e., a2/ Br c). However, analyz- ing its convergence is significantly more challenging than for the aforementioned simplified variants, as the actor and critic updates are strongly coupled. The aforementioned de- coupled analysis is over-conservative and cannot establish the convergence of the cent efforts to study the convergence of the single-timescale actor-critic algorithm include Chen et al. (2021), Olshevsky & Gharesifard (2023), and Chen & Zhao (2024). However, these works are limited to finite action spaces with i.i.d. sam- pling and do not extend to the more practical yet complex setting of Markovian sampling in continuous state-action spaces under the single-timeseale update scheme (See the comparison in Table 1). In particular, Chen al. (2021) and Olshevsky & Gharesifard (2023) assume i.i.d. sampling directly from the stationary distribution for the critic and from the discounted stale visitation distribution for the ac- tor. However, both of these distributions are unknown for real-time online learning and hence are impractical. Addi- tionally, Chen & Zhao (2024) considers the simpler undis- counted time aveeage reward setting rather than the widely adopted discounted reward setting. The key difference
1. Introduction
Actor-critic methods have achieved substantial success in many challenging applications (Mnih et al., 2016; Silver et al., 2017; Vinyals et al., 2019; Lazaridis et al., 2020). In particular, it becomes instrumental in enabling highly robust and agile robot motion control involving contin- uous state-action spaces, such quadruped locomotion control (Hoeller et al., 2024), humanoid whole-body con- trol (Radosavovic et al., 2024), drone racing (Kaufmann et al., 2023), etc.
actor-critic. Re-
Despite substantial empirical success, the theoretical anal- ysis of actor-critic is significantly behind. Most prior theo- retical studies of actor-critic methods consider only finite state-action spaces and focus on their impractical variants
'Department of Electrical and Computer Engineering, National University Singapore, Singapore. Correspondence to: Lin Zhao <elezhli@ nus.cdu.sg>.
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

On the Convergence of Continuous Single-timescale Actor-critic
Table Comparison of existing works on single-timescale actor-critic methods in discounted reward setting with linear function approximation. Our work is the first to address the continuous state-action spaces and Markovian sampling.
References
State Space
Action Space
Sampling for Critic
Sampling for Actor
Complexity
i..d. from
i..d. from state visitation distribution
Chen al. (2021)
Infinite
Finite
(c
stationary distribution
i..d. from
i..d. from state
Olshevsky & Gharesifard (2023)
Finite
Finite
O(c
stationary distribution
visitation distribution
This paper
Infinite
Infinite
Markovian
Markovian
Ö
that, in the former, the policy gradient only requires sta- tionary distribution, whereas in the latter, it depends on the visitation distribution. How to accurately approximate the visitation distribution in the single-timescale update scheme with Markovian sampling remains an open question. To tackle the aforementioned challenges, specifically,
Actor-Critic methods. The actor-critic algorithm, initially proposed by (Konda & Tsitsiklis, 1999), was later extended to the natural actor-critic variant by (Kakade, 2001). The asymptotic convergence of actor-critic algorithms has been well established under various settings, as demonstrated in works by Kakade (2001), Bhatnagar et al. (2009), and Zhang al. (2020b). More recently, many studies have focused on the finite-time convergence of actor-critic methods, They primarily focus on two variants for the ease of analysis: (I) double loop update, and (2) two-timescale update. For the double-loop variants, Kumar et al. (2023) investigated the finite-time local convergence of several actor-critic variants with linear function approximation. Wang et al. (2019) explored the global convergence of actor-critic methods with both the actor and the critic parameterized by neural networks with single hidden layers. Moreover, Gaur et al. (2024) established the last iterate convergence for actor-critic with neural networks.
1.
We introduce the intricacies arising from the uncountable continuous space. In particular, it enables us to generalize many important bounds to the continuous space successfully (see Appendix B).
operator- based analysis to handle
2. For the Markovian samples used update the actor, we prove that the resulted state distribution converges to the discounted state vivitation distribution (see Propo- sition 3.2). We further utilize it to accurately estimate the policy gradient in the analysis.
3. We propose a Lyapunov-based convergence analy- sis framework, where novel Lyapunov function is constructed specifically for the single-timescale actor- critic algorithm. We also establish a variety of new properties (see, for example, Proposition 3.1, Proposi- tion 4.4), which enable us to demonstrate finite-time convergence for both the actor and the critic simultane- ously, with a less conservative analysis.
For the two-timescale variants, Wu et al. (2020) estab- lished finite-time local convergence in the undiscounted time-average reward setting. Xu et al. (2020c) analyzed both local and global convergence for two- -im-timme (nat- ural) actor-critic under the discounted reward setting, re- spectively, with multiple samples used for critic updates. Shen et al. (2023) investigated finite-time convergence for asynchronous actor-critic, while Hong et al. (2023) intro- duced two-timescale stochastic approximation algorithm for bilevel optimization and two-timescale actor-critic.
Moreover, we highlight that our analysis builds on the same set of common assumptions that are widely adopted in many literature (Wu al., 2020; Chen al., 2021; Olshevsky & Gharesifard, 2023; Chen & Zhao, 2024). In particular, Assumptions 4.1 and 4.2 are about the regularity of the problem of interest, and Assumption 4.3 can be easily sat- isfied by many common policy parametrizations. Overall, our work takes a significant step toward a more practical analysis of actor-critic.
There are only few works considering the canonical and most widely adopted single-timescale variant. Fu et al. (2020) explored the least-squares temporal difference (LSTD) update for the critie, achieving the optimal pol- icy within the energy-based policy class for both linear function approximation and neural network approximation. Zhou & Lu (2023) and Chen et al. (2024) established the global convergence of actor-critic methods for solving linear quadratic regulator. Recently, Chen et al. (2021); Olshevsky & Gharesifard (2023); Chen & Zhao (2024) investigated single-timescale actor-critic methods in general Markov
1.1. Related Work
In this section, we review the existing works on actor-critic methods.
2

---

On the Convergence of Continuous Single-timescale Actor-critic
Decision Processes (MDPs) with linear function approxima- tion, aligning with the focus of this work. Specifically, Chen al. (2021) and Olshevsky & Gharesifard (2023) addressed the commonly used discounted reward setting, while Chen & Zhao (2024) improved upon (Wu et al., 2020) by advanc- ing from the two-timescale to the single-timescale approach under the undiscounted time-average reward setting. de- tailed review and comparison of these results can be found in Table and the introduction.
objective function:
((0) n(s)Vo(s)
(3)
where n1ss) is fixed initial distribution.
We denote the density at state s' after transitioning for one time step from state s by Po {s, which is defindd as
Po(s' 88) - / P(s' (,,))o((a [s) (8) da.
Notation, We use san-serif letters to denote scalars and use lower and upper case bold letters to denote vectors and ma- trices respectively. We also use ||س||| to denote the 22-mrmm of a vector w and || to denote the spectral norm of a ma- trix A. Without further specification, we write Zn = (yn) if there exists an absolute positive constant such that In S Cyn: for two sequences {zn) and {yn}- We use (()) to hide logarithm factors. The total variation dis-
The corresponding state density after transitioning for time steps can be acquired by recursively applying (' [s) i.c.
(8(6110)=1 (s x))
de,
tance of two probability measure and is defined by drv (u, = 1/2 &x [u(dz)= - v(dx)]-
Consequently, we define the discounted state visitation dis- tribution under policy no
2. Preliminaries
vo(8') = (1 1
nn(s) (
(4)
==
Markov Decision Process. In this paper, consider discrete-time Markov Decision Process (MDP) defined by tuple M (S,A,, A, P. 7), where S is the state space and A is the action space. The spaces S and A are allowed to be either finite sets or real vector spaces, i.e., S C R.d. and A c RRd. The transition kernel is denoted by P(5 Sts az) E R20. the reward function is r S A + F). and y (0, 1) is the discounted factor. We also assume that the initial state is sampled from fixed initial distribution 17.
It is worth noting that previous works (Chen et al., 2021; Olshevsky & Gharesifard, 2023) rely on sampling from this distribution, which is infeasible. In this work, we propose a practical sampling scheme to circumvent this impediment.
With the discounted state visitation distribution, the objec- tive function can be reformulated as (Sutton al., 1999)
1
((0) = 1 vo(s)
Ta(a s)r(s, a) dads
A policy To parameterized by O E Xe maps given state to a probability distribution over the action space, i.c., a₂ ~ T st). We denote the stationary distribution in- duced by the policy Te and the transition kernel P by μa. The value function of state under a policy me is the ex-
E Eenvo awoo r(s,a)
Policy Gradient Theorem. Policy gradient algorithms are among the most widely used approaches in continuous- action reinforcement learning. Their core concept involves adjusting the policy parameter @ in the direction of the performance gradient V VoJ( These algorithms are built upon the foundational result known as the policy gradient theorem (Sutton et al., 1999):
pected cumulative return when starting and following Te thereafter. It is defined as
(s(s) = Eaa-rTo
Σ (rrrs) ( so s 1=0
(1)
where the expectation takes over the randomness of the policy no and the transition function P. The correspond- ing action-value function is the expected cumulative return when starting from state s, taking action and following To thereafter, which is defined as
/ Qo a) Vozola dads
Vo)
vo(s)
1
E Eenvo anri Qo(s,a) a) Ve To
20
Qo(s. a)
Σ
('r(s), ( 8, 0g a)
(2)
Computing this gradient necessitates the Q-value associated with the current policy тØ. The REINFORCE algorithm (Williams, 1992), an episodic Monte Carlo-based method, approximates the true Qavalue by utilizing the cumulative rewards gathered along the sampled trajectory.
where we simplified the expectation notation when there is no confusion. The reinforcement learning (RL) tasks typi- cally aim find policy no that maximizes the following
3

---

On the Convergence of Continuous Single-timescale Actor-critic
Note that for any function b: 8 - IR that is independent of the action, have
where O₂ (8t, Ct St-1) denotes the I-th transition tuple for the critic, generated via Markovian sampling under the policy To and transition kernel P. such that
J b(s) (()) = b())V / [o(a|s) b(s)V1 = 0.
O = St az ~ ne. (-] 8141 ~ P(: ((:15e: se, se.)))... (7)
Therefore, the policy gradient theorem can be written equiv- alently as:
Since ò is an approximation of the advantage function, sim- ilar to REINFORCE with a baseline, the corresponding update rule for the actor can be written as:
-I--E_, Ea (Qo(s, a) b(s)) Ve log To (a]s)],
JO( = 1-7
D 0. aao( wi) Vo log ne, (āg (t):
(8)
where b(s) is called the baseline function. A popular choice of baseline is the state-value function, which leads to the following advantage-base bbsed policy gradient
where is the step size of the actor and Ō = ($;, âe, $1+1)
denotes the t-th transition tuple for the actor. Specifically, Ö is also generated via the following Markovian sampling (Konda& & Tsitsiklis, 2003; Shen et al., 2023)
1 9 where Go(s, .) Qo(s, a) (s) is known as the advan- tage function. This is the "REINFORCE with a baseline".
(o)
Bonug a (o a) Vo (als) amto
Ô, = (5t, ag ~ To. (-) 8c+1 ~ P(.16c.0)))
(9)
where P=yP- + (1 7))
Here the transition kernel P defined as with probability 7, the next state follows the original transition kernel P: Otherwise, with probability -, the next state is sampled from the initial distribution ry. Note that the above Marko- vian sampling generally requires a simulator whose state can be arbitrarily reset. It has few nice properties that will be discussed shortly, which facilitate an accurate estimation of the policy gradient.
The baseline function can help reduce variance. However, like all Monte Carlo-based methods, it can still suffer from high variance and thus learns slowly. An alternative ap- proach involves introducing an additional trainable model to approximate the value function, a method typically known as actor-critic methods.
3. Actor-Critii Methods
Denote the class of real-valued functions on the state space S by F == {f I S + R}. We define the operator P: F. + F acts on state distribution f E F by
In this work, we analyze the classic single-sample single- timescale actor-critic method, where the critic employs boot- strapping by using a single sampled reward to update its value estimate at each iteration. We consider the following linear function approximation of the state-value function:
(PD(s') / (())To(a))))
|s, dads. (10)
We further define reset operator & F F such that it reset any state distribution to the initial distribution
(o(s;w) = ((s) w,
(ff) (()))
where (+)): Rd is a known feature mapping, which satisfies [|((-)]| < 1. To align Vø(s; w) with its true value Vo(s), the semi-gradient TD(O) update employed to es- timate the linear coefficient w (hereafter referred to as the critic):
Therefore, the operator P that acts on a state distribution, describing how the distribution evolves after a single step of
the Markov chain induced by the policy To and the transition kernel P, can be written compactly as:
Wi+1= = W: + 3 (re++r 7765441) wi - ((s))² T wi) ((st),
P ア=ッP + (1 E)
where 3 is the step size of the critic w and rt == r(st, at). Denote the transition tuple O = as) and we define the following temporal difference enror
We show in the following proposition that the discounted state visitation distribution Pe defined in Eq. (4) is the sta- tionary distribution of the Markov chain induced by policy To and transition kernel P by showing that up is the unique fixed point of the operator P.
8(0. w) r(s, a) " ((s)
Proposition 3.1. vo(s) the unique fixed point of the oper- ator P. that is.
and the update rule for the critic is then given by
W1+1 w. + (,03000,,, (s))
(6)
(Pvo)(s) =vo(s),

---

On the Convergence of Continuous Single-timescale Actor-critic
Algorithm Continuous Single-sample Single-timescale Actor-Critic with Markovian Sampling
which is more challenging. To this end, the Markovian sam- pling strategy introduced in Eq. (9) becomes necessary to track this distribution. Consequently, Algorithm 1 inher- ently supports online learning and applies to continuous control tasks.
1: Initialize: actor parameter 8g. critic parameter wo, ini- tial states 80, $o ~ 77, stepsizes a for actor, (3 for critic.
2: for t = 0, 1, 2,
T 1 do
3: Markovian sampling:
As shown in Line 4 and Line 5 of Algorithm 1, we adopt Markovian sampling for both the critic and the actor. Specif- ically, the transition tuple for the critic is generated by the following Markoy chain
4:
O₂ = (St. ag ~ Te, (- [t); S1+1 ~ P(-1 St, at))
Ô = (šz, a, ~ To. (- 8,). S ~ P(- $2, a.)).
5:
6:
Critic and actor update:
7:
We+1 = proja (w,, + 35((0, w2) (s)))
( 8: 0.+1 = 0. + ad aō(Or, wi) w log no, (a+l 8x).
(Te,
(No, 1 .P)
(To.
80
8t
81+1-
9: end for
(12)
while the actor's transition tuple is generated by the Markov chain
and therefore the stationary distribution of the following Markov chain induced by and P.
(Teg 81 (xo, .P) (5o, 1 ..P) 8t
(5o, Bag... P)
8g
$1+1-
(13)
(To.P)
(Ta.P)
(Ta.P)
(Ta.P)
80
81+1- (11)
Note that the above Markov chains -imeeiiboooogeeouus differ from the one defined in Eq. (11) (time- homogenomoenn
The above proposition justifies the actor's sampling scheme in Eq. (9), as O2 effectively approximates the discounted state visitation distribution, which is required by the pol- icy gradient theorem (Eq. (5)) following the actor update formula in Eq. (8).
as they involve a varying policy тT. This poses a major challenge for analyzing Algorithm 1, since a single sample is insufficient accurately approximate the stationary dis- tribution of the state under fixed policy. Previous studies simplified their analysis by assuming i.i.d. samples drawn from the stationary distribution for the critic and from the visitation distribution for the actor. However, such sampling is infeasible in practice because both of them are unknown. In contrast, our approach is more practical since samples can be drawn directly from the Markov chain.
Proposition 3.2. For the Markov chain defined in Eq. (11), we have
drv (F(, E 150 -00 (6);s),,ol so)) 5 14 2 S.
Proposition 3.2 states that the distribution of 3, converges to ve geometrically with rate y, crucial property for manag- ing the Markovian noise arising from the actor's Markovian sampling in Eq. (9).
In Algorithm 1 Line 7, projection (proj(-)) )) is introduced to keep the critic norm- norn-bounded by W, which is widely adopted in the literature (Wu et al., 2020; Chen et al., 2021; Olshevsky & Gharesifard, 2023; Chen & Zhao, 2024) for analysis. Note that the projection can be handled easily, relaxed using its non-expane non-expansive property in our analysis.
We summarize the above-describedd actor-critic algorithm in Algorithm 1. The "continuous" refers to the general set- ting of continuous state-action spaces. 'single-timesenn refers to the fact that the stepsizes a and B are kept in constant proportion. In addition, the terminology "single- sample" follows Olshevsky & Gharesifard (2023), which refers to the fact that at each iteration, the critic and the actor are each updated using single sample. Note that Olshevsky & Gharesifard (2023), who consider the discounted reward setting, assume access to samples from the discounted state visitation distribution and the stationary distribution for up- dating the actor and critic, respectively. This assumption requires simulator capable of resetting arbitrary states. In the simpler time-averee average reward setting (Wu et al., 2020; Chen & Zhao, 2024), the policy gradient depends solely on the stationary distribution, allowing the actor to utilize the
4. Assumptions
Before presenting the main results, we will discuss several standard assumptions that are common in the literature of analyzing actor-critic with linear function approximation (Wu et al., 2020; Xu et al., 2020b; Shen et al., 2023; Chen et al., 2021; Olshevsky & Gharesifard, 2023; Chen & Zhao, 2024).
By taking the expectation of wi+1 in Eq, (6) with respect to the stationary distribution, and conditioning on w,. we have
Eglwe+1 | = we + 3(be - Aows),
where
same samples as the critic. In contrast, discounted reward setting requires the policy gradient to be computed with respect to the visitation distribution, as shown in Eq. (5),
As = (lssaao)/<(s)((())) 7p(5')) ",,
(14)
bg (Ts,))((s
(15)
5

---

On the Convergence of Continuous Single-timescale Actor-critic
and s ( a mT(- (1) ~ P(||s, is the subse- quent state of the (s, a). It can be easily shown that (Sutton & Barto, 2018) the TD limiting point w (0) satisfies:
L such that for any 0, 0,01.00 02 Xx, 8, and E A, it holds that:
(a) | log m 8) = B
Agw (0) = -ba-
(16)
(b) V log me, (a) (a|s) - v log no, (a |)ll - L 0211.
Assumption 4.1. For any 0, the matrix Ag defined in Eq. (14) is positive definite and its minimal eigenvalue can be lower bounded by X.
(c) Too (a (a|s) no, (a $) - L||0 - 02ll-
Assumption 4.3 states the regularity of the policy which is standard in the literature of actor-critic methods (Xu et al., 2020a; Wu et al., 2020; Chen et al., 2021; Olshevsky & Gharesifard, 2023; Chen & Zhao, 2024). These conditions are sufficiently general to be satisfied by a wide range of distributions, including the uniform distribution, the trun- cated Gaussian distribution, and the Beta distribution with a, B > 1.
Assumption 4.1 is commonly adopted in analyzing actor- critic (TD learning) with linear function approximation (Bhandari et al., 2018; Wu et al., 2020; Qiu et al., 2021; Chen et al., 2021; Olshevsky & Gharesifard, 2023; Chen & Zhao, 2024). It is explained as exploration since Ag can be rank deficient without sufficient exploration (Olshevsky & Gharesifard, 2023; Chen & Zhao, 2024). Assumption 4.1 further guarantees the problem's solvability since with this assumption, we have (0) Ag by. In addition, we can choose W F so that all w" lie within the pro- jection radius @ because ||bø|| S f and ||A,'|| < X-1 which justifies the projection operator introduced in Line 7 of Algorithm!! 1.
With Assumption 4.3, we show in the following proposition that the policy Te is Lipschitz continuous with respect to its parameter terms of the total variation distance.
Proposition 4.4. There exists a positive constant Lx such that for any 0, 02 E Xe, holds that
Assumption 4.2 (Uniform ergodicity). For any 0, denote (e(+) as the stationary distribution induced by the policy To(. 8) and the transition kernel P(- | a). For the follow- ing Markov chain (augmented with action) generated by the policy To and transition kernel i.e.
drv (To, (118), mo, (-18) s T. - 02l1-
(18)
We observed that Proposition 4.4 plays key ingredient in the overall proof. With this proposition, we establish a bound on the distance between stationary distributions, as detailed in Lemma B.1 within Preliminary Lemmas in Appendix B, extending previous results from the tabular case to the continuous setting. This further facilitates the derivation of corresponding results for the discounted state visitation distribution, as presented in Lemma B.3.
(To. P)
(Fo.P)
(To. P)) St
90
81
St+1: (17)
there exist m and p E 1) 1) such that
(P E -.150= = s), mo())) I mp", " Vr 2 V.
Assumption 4.2 assumes the Markov chain is geometrically mixing. It is commonly employed to characterize the noise induced by Markovian sampling in RL algorithms (Bhan- dari et al., 2018; Wu al., 2020; Chen et al., 2021: Chen & Zhao, 2024). This is the counterpart of Proposition 3.2 (which is proved for analyzing the induced Markovian noise associated with the actor update). It is assumed since P is a general transition kernel that lacks the y-contraction prop- erty of the transition kernel P established in Proposition 3.2.
5. Main Results
We define the following uniform upper bound for the linear function approximation error of the critic:
Capp := sup V (p(s) 0
Vo(s)) (19)
The error Eapp is zero if Ve is indeed a linear function for any 9. Naturally, it can be expected that the learning errors of Algorithm depend on capp.
To justify this assumption in the continuous space, we note that all the distributions specified by the Omn- Stein-Uhlenbeck (OU) process satisfy this property. The OU process converges to a Gaussian distribution with the exponential mixing time. Moreover, it can also be shown that this property holds for more general diffusion pro- cesses (Del Moral & Villemonais, 2018).
We define the following integer Tmix that will be useful in the statement of the theorems:
mp 1 1
1 VT
Tmix min
where m, p are constants defined in Assumption 4.2 and y is the discounted factor. Therefore, we choose
Assumption 4.3 (Lipschitz continuity of policy). Let Te(a| s) be a policy parameterized by E Xe with bounded support. There exist positive constants B, Ia and
Tmix
Olog
6

---

On the Convergence of Continuous Single-timescale Actor-critic
such that "T < 1/vT and - < 1/vTT. The integer Tmix represents the mixing time of the ergodic Markov chain defined in Eq. (1I) and Eq. (17), which will be used to control the Markovian noise in the analysis.
5.1. Proof Sketch
To better illustrate our technical contribution, we provide a proof sketch to elucidate the significance of each error term and offer insights into the methods used to address them.
We define A = - with - = w (0:) to measure the critic error while (.)()) serves as a measure of the actor error since for a general non-convex problem, our objective to demonstrate that (O,) converges to zero.
The key difference between single-timescale and two- timescale (double-loop) actor-critic lies in the strong cou- pling of the critic and actor errors. Unlike the two-timescale approach, which sequentially analyzes the convergence of critic error and actor error, the single-timescale setting re- quires simultaneous treatment of both errors. To address this, we propose novel Lyapunov analysis framework and outline the proof of Theorem 5.1 in three steps. Step 1 de- rives an implicit upper bound for the critic error, treating it as an intermediate result. Step 2 performs a similar implicit analysis for the actor error. Step 3 combines these results into a novel Lyapunov function, whose convergence implies the simultaneous convergence of the critic and actor.
Theorem 5.1. Consider Algorithm 1 with a c/ c/VT,B
1/VT, where is constant depending on problem pa- rameters. Suppose Assumptions 4.1.4.3 hold, we have for T 2 mixx
log"! T VT
E| = O
+ (eapp),
T Tmix Amm Tmix
1
Σ BI
6log²
logg" T VT
(Eapp)-
An implicit bound for critic error. Using the critic update rule, we decompose the squared critic error by (see Eq. (27))
Step I:
T Tmix Tmix
Theorem 5.1 establishes the finite-time convergence of AI- gorithm 1. If the critic approximation error Eapp is zero, we see that both the critic error and the actor error diminish at sub-linear rate of 0/3)) The additional logarithmic term (log² 7) is incurred by the mixing time of the Markov chain, which can be eliminated under i.i.d. sampling as will be shown in Proof Sketch. In terms of sample com- plexity, to obtain an e-approximate stationary point, it takes number of Ō(c-?) samples, which is typically the sam- ple complexity of single-timescale actor-critic (Chen al., 2021; Olshevsky & Gharesifard, 2023; Chen & Zhao, 2024).
B| 1 2 S 11 + (f
+ 2E | - w 11 + 2,3TE (e, F(wr, 0.))
12
13
+ 2 De. f(Or, wi) - flwe,
+ 2 (A,, wi+t)
where f(0,w) 8(0,w) is the update term of the critic and ff is its mean value defined in Eq. (20).
The vanilla version of Algorithm is introduced in the classic textbook (Sutton& & Barto, 2018) 8) as a canonical actor-
I reflects the variance of the critic update which can be bounded by O(1/VT) due to its bounded update.
critic algorithm with linear function approximation. As a canonical algorithm, its convergence has been a focal point of research, extensively studied across diverse set- tings, e-g., two-timescale (Wu et al., 2020), single-timesens (Chen et al., 2021; Olshevsky & Gharesifard, 2023; Chen & Zhao, 2024), time-average reward setting (Wu et al., 2020; Chen & Zhao, 2024). discounted setting (Chen et al., 2021; Olshevsky & Gharesifard, 2023). Notably, among all the aforementioned studies, this work is the first to address the important yet challenging setting of continuous state and action spaces. Among the widely used discounted single- timescale approaches considered, our method is the first to employ Markovian sampling for both the critic and the actor in contrast to the artificial i.i.d. sampling (Chen et al., 2021; Olshevsky& & Gharesifard, 2023). Therefore, our work compares favorably by closing two significant gaps left by prior studies.
I2 represents the difference between the moving critic target wp, which can be controlled due to its Lipschitz continuity shown in Lemma B.6.
Is is the inner product between the critic error A and its mean-path update f. It can be bounded by -2A,3E A, |2 under Assumption 4. since w' is the solution of Eq. (16). Note that this bound combined with first term A| 1| is (1 2A || || which implies a contraction of the critic error because the coefficient is less than 1.
1 represents the Markovian noise term, capturing the devi- ation between the critic's 's actual update f and its mean-path f. To analyze this deviation, we aim to show that the sample
O2 is close to its stationary distribution, as the error term
I3 vanishes when O₂ is drawn from the stationary distri-
7

---

On the Convergence of Continuous Single-timescale Actor-critic
bution. First, we demonstrate that the sample O2 from the original Markov chain defined in Eq. (12) is close to the sample from the auxiliary Markov chain in Eq. (21), as their differences are limited to the last T steps. The total variation distance between these samples is controlled by the actor's change, i.c., 100 - 01- as established in Lemma B.2. By choosing t = Tmix = Olog T) and noting that the actor's 's update speed (L/vT),, the distance between O, and - is bounded by (Tmixx/ /T). Consequently, the
where 1(0,,,, w. 0) 8(0, W[O, ( is the update term of the actor, h is its mean value, and gww;, 0t) de- fined in Eq. (20) represents the approximation error of the optimal critic w The first term on the right- hand side of the above inequality compares the actor's performances between consecutive updates, which can be eliminated by telescoping.
1 reflects the variance of the actor update which can be controlled by O(1/VT) due to its bounded update.
accumulated deviation over the last Tmix steps is bounded by Or /vT) = Ollog" 2 T T//T), explaining the loga- rithmic term in the convergence rate, Next, we show that the Markov noise of the sample from the auxiliary Markov chain approaches its stationary distribution after Tmix steps under a fixed policy, leveraging the uniform ergodicity assumption in Assumption 4.2. This highlights the role of Assump- tion 4.2 in analyzing single-sample hingle/to-ttmessli algorithms with Markovian sampling. The complete analy- sis of this Markovian noise is shown in Lemma C.I.
Iz is the inner product between actor error and the approxi- mation error of the optimal critic wf This term is control by the approximation error O (Capp) defined in Eq. (19).
I3 represents the Markovian noise term, capturing the devi- ation between the actor's actual update h and its mrean-path h. Similar to the critic analysis, this noise is controlled by showing that the original Markov chain defined in Eq. (13) is close to the auxiliary Markov chain in Eq. (22). Addi- tionally, samples from the auxiliary Markov chain approach their stationary distribution after Fiix steps, leveraging the uniform ergodicity property established in Proposition 3.2. This error term is bounded in Lemma C.3.
Is tracks both the critic error A and the difference be- tween the drifting critic targets w.. It can be bounded by the critic error A and the actor error (O,) after error decomposition. In contrast, the two-timescale setting can prove that L converges zero. To see why this is the case, note that from the Lipschitz continuity of the critic target of shown in Lemma B.6, error term w/ wi+1 can be bounded by the update of the actor 0, i.c., 0, - 0 Since the update step size for the actor is a while the contraction of the critic error is at a rate 1 2AB, a ratio term a/B appears by moving the term - A to the left side of the above inequality and dividing its coefficient. There- fore, one can leave other terms in /4 as constant and bound it by (a)33). Since lim / B, = 0 in two-timescale approach, thereby directly establish the convergence of the critic. However, lim /+/3 A. = e in single-timescale approach which why we can only bound 14 by A, and (0) and make an implicit upper bound for the critic error. The final bound is summarized in Theorem D.I.
I tracks the inner product between the actor enror (o)
and the critic error (A, = w -w,). In two-timescale actor-critic, this term goes to zero due to the convergence of the critic. However, in single-timescale approach, we can only bound this term by (O.) and A, which will be treated together later. This give an implicit upper bound for the actor error. The final result of the above inequality is summarized in Theorem D.2.
Step 3: A novel Lyapunov analysis. From Step I and Step 2, we get two inequalities about the coupled critic error and actor error. Here we bring them together by defining the following Lyapunov function
2B L. = 1-7 B1 +
1 1-7 E (0,))1
2B
An implicit bound for actor error. Using the actor update rule and the smoothness property of (()) (Lemma B.8), we decompose the squared actor error by (see Eq. (31))
Step 2:
where 2B/(1- ()) is the scaling coefficient which balances the contribution of the critic error and the actor error. Com- bine the results in Step and Step 2 (Eq. (26) and Eq, (30)) gives an unified inequality of L. We then define the total error as L == 1/(T Tmix) ET= LL. Telescoping from T Tmix to T 1, it can be shown that (see Eq. (33))
(1 - JJ- a [B[
alg g E (a(( wi 02) - (V.J(()),g(ee) 0.))
2
(2 X
+ 1 c++
log" ' VT
L
0
+ O(Eapp);
+ E(V h(w, 0,) h(O,, we, 0,))
where c = at/ is is the stepsize ratio between the actor and the critic, 7 is the discounted factor, À is the maximum eigenvalue of Ag defined in Assumption 4.1, and Le is the Lipschitz constant characterized in Lemma B.6. Therefore,
1o E(VJ(O,) hiW 0.) -h(w., 0.)).
14
8

---

On the Convergence of Continuous Single-timescale Actor-critic
choosing 2/4BLe (see Eq. (34)), have
problems. Advances in Neural Information Processing Systems, 34:25294-25300 2021.
(log" L -=
( VT + (Capp),
log T
Chen, X. and Zhao, L. Finite-time analysis of single- timescale actor-critic, Advances in Neural Information Processing Systems, 36, 2024.
which implies the convergence of the critic error and the actor error simultaneously. Therefore, we finish the proof of Theorem 5.1.
Chen, X., Duan, J., Liang, Y., and Zhao, L. Global con- vergence of two-timescale actor-critic for solving linear quadratic regulator. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 37, pp. 7087-7095, 2023.
6. Conclusion
In this paper, provide finite-time convergence analysis for the single-sample, in continuous state-action spaces. We propose novel Lya- punov analysis framework, which allows a less conservative analysis under the same set of assumptions adopted exist- ing studies. Our analysis offers new insights into the coupled dynamics of actor-critic updates. Unlike prior works that assume artificial decoupling between the actor and critic, our results capture the interdependencies that arise naturally in practical implementations. Moreover, our framework and analytical techniques can serve as a foundation for studying other single-timescal reinforcement learning algorithms in continuous domains.
timescale actor-critt algorithm
Chen, X., Duan, J., and Zhao, L. Global optimality of single- timescale actor-critic under continuous state-action space: a study on linear quadratic regulator. In Proceedings of the Thirty- Third International Joint Conference on Artificial Intelligence, pp. 3886-33224, 2024.
Del Moral, P. and Villemonais, D. Exponential mixing properties for time inhomogeneous diffusion processes with killing. 2018.
Fu, Z., Yang, Z., and Wang. Z. Single-timescal actor-critic provably finds globally optimal policy. arXiv preprint urXiv:2008.004: 2020.
Acknowledgements
Gaur, M., Bedi, A., Wang, D., and Aggarwal, V. Closing the gap: Achieving global convergence (last iterate) of actor- critic under markovian sampling with neural network parametrization. In International Conference on Machine Learning, pp. 15153-15179, PMLR, 2024.
This work was supported by the Singapore Ministry of Edu- cation Tier I Academic Research Fund (A-8001174)00-00) and Tier 2 Academic Research Funds (T2EP20123-0037, T2EP20224-0035).
Impact Statement
Heidergott, B. and Hordijk, A. Taylor series expansions for stationary markov chains. Advances in Applied Probabil- ity, 35(4):1046- 1070, 2003.
This paper presents work whose goal is to advance the field of Machine Learning. There are potential societal conse- quences of our work.
Hoeller, D., Rudin, N., Sako, D., and Hutter, M. Any- mal parkour: Learning agile navigation for quadrupedal robots. Science Robotics, 9(88)ca 2024. doi: 10. 10.1126/scirobotics.a77755
References
Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021.
Hong. M. Wai, H.-T., Wang, Z., and Yang. Z. two- timescale stochastic algorithm framework for bilevel op- timization: Complexity analysis and application actor- critic. SIAM Journal on Optimization, 33(1):147-180 2023.
Bhandari, J., Russo, D., and Singal, R. A finite time anal- ysis of temporal difference learning with linear function approximation. In Conference on learning theory, pp. 1691-1692. PMLR, 2018.
Kakade, S. M. A natural policy gradient. Advances in neural information processing systems, 14, 2001.
Bhatnagar, S., Sutton, R. S., Ghavamzadeh, M., and Lee, M. Natural ccttic algorithms. Automatica, 45(11): 2471-2482. 2009.
Kaufmann, E.,, Bauersfeld, I.,, Loquercio, A., Müller, M.,
Koltun, V., and Scaramuzza, D. Champion-level drone racing using deep reinforcement learning. Nature, 620 (7976) 2023. ISSN 1476-4687. 0415866-023-06419944
Chen, T., Sun, Y., and Yin, W. Closing the gap: Tighter anal- ysis of alternating stochastic gradient methods for bilevel
doi: 10.1038/

---

On the Convergence of Continuous Single-timescale Actor-critic
Konda, V. and Tsitsiklis, J. Actor-critic algorithms. Ad- vances in neural information processing systems, 12, 1999.
Vinyals, O., Babuschkin, I., Czamnekki W. M., Mathieu, M., Dudzik, A., Chung, J., Choi, D. H., Powell, R., Ewalds, T., Georgiev, P., et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. nature, 575 (7782):350-34, 2019.
Konda, V. R. and Tsitsiklis, J. N. Onactor-critic algorithms. SIAM journal on Control and Optimization, 42(4):1143- 1166, 2003.
Wang, L.,, Cai, Q. Yang. Z., and Wang. Z. Neural policy gradient methods: Global optimality and rates of conver- gence. arXiv preprint arXiv: 0000900//500 2019.
Kumar, H., Koppel, A., and Ribeiro, A. On the sample com- plexity of actor-critic method for reinforcement learning with function approximation. Machine Learning. 112(7): 2433-2467, 2023.
Williams, R. J. Simple statistical gradient-folowwing algo-
rithms for connectionist reinforcement learning. Machine learning, 8(3):229-255 256,, 1992.
Lazaridis, A., Fachantidis, A., and Vlahavas, I. Deep rein- forcement learning: A state-of-the-ar walkthrough. Jour- nal of Artificial Intelligence Research, 69:1421-1471, 2020.
Wu, Y. F. Zhang, W. Xu, P., and Gu, Q. finite-time analysis of two time-scale actor-critic methods. Advances in Neural Information Processing Systems, 33:17617- 17628, 2020.
Mitrophanov, A. Y. Sensitivity and convergence of uni- formly ergodic markov chains. Journal of Applied Proba- bility, 1003-1010 2005.
Xu, P., Gao, F., and Gu, Q. An improved convergence analysis of stochastic variance-reduced policy gradient. In Uncertainty in Artificial Intelligence, pp. 541-551. PMLR, 2020a.
Mnih, V., Badia, P., Mirza, M., Graves, A., Lillicrap, T., Harley, T., Silver, D., and Kavukcuoglu, K. Asyn- chronous methods for deep reinforcement learning. In International conference machine learning, pp. 1928- 1937. PMLR, 2016.
Xu, T., Wang, Z., and Liang, Y. Improving sample com- plexity bounds for (natural) actor-critic algorithms. Ad- vances in Neural Information Processing Systems, 33: 4358-4366 2020b.
Olshevsky, A. and Gharesifard, small gain analysis of single timescale actor critic. SIAM Journal on Control and Optimization, 61(2):980-1007 2023.
Xu, T., Wang, Z., and Liang, Y. Non-asymptotic conver- gence analysis of two time-scat scale (natural) actor-critic algorithms. arXiv preprint arXiv:2005.0355 2020c.
Qiu, S., Yang, Z., Ye, and Wang, Z. On finite-time conver- gence of actor-critic algorithm. IEEE Journal on Selected Areas in Information Theory, 2(2):652 224, 2021.
Yang, Z., Chen, Y., Hong, M., and Wang, Z. Provably global convergence of actor-critic: case for linear quadratic regulator with ergodic cost. Advances neural informa- tion processing systems, 32, 2019.
Radosavovic, I. Xiao, T., Zhang, B., Darrell, T., Malik, J.. and Sreenath, K. Real-world humanoid locomotion with reinforcement learning- Science Robotics, 9(9)): cadi9579, 2024. doi: 10.1 11126ssiioootiicsad9959999
Zhang, K., Koppel, A., Zhu, H., and Basar, T. Global con- vergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimiza- tion, 3866)3358 12, 2020a.
Shen, H., Zhang, K., Hong, M., and Chen, T. Towards derstanding asynchronous advantage actor-critic: Conver- gence and linear speedup. IEEE Transactions on Signal Processing, 71:2579-2555 2023.
Zhang, S., Liu, B., Yao, H., and Whiteson, S. Provably con- vergent two-ttwoweeeeeee woo-immeccale off- off-policy actor-critic with function approximation. In International Conference on Machine Learning, pp. 11204-11213. PMLR, 2020b.
Silver, D., Schritwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al. Mastering the game of go without human knowledge. nature, 550(7676) 2017.
Zhou, M. and Lu, J. Single timescale actor-critic method to solve the linear quadratic regulator with convergence guarantees. Journal of Machine Learning Research, 24 (222):1-34, 2023.
Sutton, R. and Barto, A. G. Reinforcement learning: An introduction. MIT press, 2018.
Zou, S., Xu, T., and Liang, Y. Finite-sample analysis for sarsa with linear function approximation. Advances in neural information processing systems, 32, 2019.
Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
10

---

On the Convergence of Continuous Single-timescale Actor-critic
Supplementary Material
Table of Contents
A Notation
11
B Preliminary Lemmas
12
C Markovian Noise
13
D Proof of Main Theorem
14
D.1 An implicit bound for critic error
14
D.2 An implicit bound for actor error
16
D.3 novel Lyapunov analysis
17
Proof of Propositions
19
Proof of Preliminary Lemmas
21
Proof of Markovian Noise
25
A. Notation
In the following, we will analyze the convergence of the above algorithm. We define the following notations:
f(0,w) == (r(s,a) + + Φ(s) T w) ((s)
f(w. 0) == fF [w),
h(O,w, w. (r(s,a) + T w o(s) T w) V log s)
(20)
h(w.0) 0) Eo-(vu.TO. [h(O,,, w, 0.
gO, w, 0) = ((76(6') - ((s)) - (s') Vo(s)) V (a(a|s)
g(w, 0) = Eo-(ve.TO. [g(0, w, 0)].
We make use the following auxiliary Markov chain to deal with the Markovian noise. Auxiliary Markov Chain for the Critie:
St-7 ar- P, St-t+1
1 8 81-742
P.
0: 0 0
Py St O āi
P
8
(21)
Auxiliary Markov Chain for the Actor:
S Be-r, àz-7 $6-
P
B o a1-++1 - 5
O 01-
P 3t
P 0 āi - $1+1-
(22)
In the sequel, we denote by Ō, (š,, āe, 1c-1) the tuple generated from the auxiliary Markov chain in Eq. (21) and Ö : (St, ae, Se+1) the tuple generated from the auxiliary Markov chain in Eq. (22). In comparison, Oz (st, 4, 8141) and Ô, = (8e, de, 8 denotes the tuple generated by Algorithm We use O' shorthand for independent sample

---

On the Convergence of Continuous Single-timescale Actor-critic
from stationary distribution Me, ne, s' P and O" shorthand for independent sample from discounted state visitation distribution vo, T0, 8 P.
Throughout the proof, we define 6, == b(0,, wi), and = F + 2 is the uniform upper bound for 8. We also define filtration F& = (S0, So, Co, Co, $1, $1, a1 Ø1, St, 3t), where a--) denotes the o-algebra generated by the random variables.
B. Preliminary Lemmas
In this section, we present several preliminary lemmas, encompassing three aspects: extending previous work continuous settings (Lemma B. Lemma B.2, Lemma B.5, Lemma B.6), establishing the corresponding statistical properties for actor samples (Lemma B.3, Lemma B.4), and stating previously established results (Lemma B.7, Lemma B.8, Lemma B.9). Lemma B.1. For any 01 and 0z, it holds that
1
drv (uo, [o,,) S 2
[log, m -1
10, - 0211.
1 p- /
dIv (po, @ ne P0, X To.) S 2
1 [logp m
'1
+
||0] 0211,
1
drv (ue, & me, @ P.p @ To @ P) < 2L
1 [log, m
11
|10|
0211
1
Lemma B.2. Given time indexes and such that t 2 0, consider the auxiliary Markov chain in Eq. (21). Conditioning on Ft-r, we have
drv E.), P(Ee4 E E.) S drv (P(O, E ), E ))) dFv E P), E .) = drv (P((s), E -)), ā.) E E)), drv (P(((s,, ar) E P((s), E )) < drv (P((t E P(r E :) + La 0, 0
Lemma B.3. For any 02 and 02 it holds that
2L x
vo,)
| 0211,
?
dvo, X No, @ mo,) S 2L
1
|10:
021l.
7
(ve @ me, s8 P. vo, s me & P) < 2
1
(-
110
02ll-
Lemma B.4. Given time indexes and T such that t 2 T > 0, consider the auxiliary Markov chain in Eq. (22). Conditioning on Fi we have
(Pv(1(S E P(541 e) S drv (P(Ō, E.)((() E)),
(P(O E P(O .)) drv (P((St, E e.), ā.) E),, drv (P(((,, E P(),,, a.) E .)) S drv (P((e E P(s, E .)) + I,EE 0 0.--11]
Lemma B.5, For any 0₁, Oz. we have
((())) J(62) L -02ll.
where L, 4F (1-
Lemma B.6. There exists a constant Le such that
(0,) w" (02))l S L.] 0, 0211, v0,, 02 E Rd
where T= (8X- 4A 41-1-p7 -IF) (1+ [lgg m -1 1/(1 p)).
12

---

On the Convergence of Continuous Single-timescale Actor-critic
Lemma B.7. For any O' IRd, there exists constant Ln such that |V Vuee || Lu110 0'I,, where He(()) is the stationary distribution under the policy no-
Lemma B.8 ((Zhang et al., 2020a), Lemma 3.2). For the performance function J(O), there exists a constant Lg > 0 such that for all 0,, O2 E Rd, holds that
- - Lg 0211.
(23)
which further implies
J(02) ((0)) (VJ(O.), 01) Lg 110 02l1² Lemma B.9 (CChn et al., 2021), Proposition 8). For any 01, 02 E IR. we have
(24)
(0,) V (02)) - La 0211.
where La a positive constant.
C. Markovian Noise
We then the following Markovian noise term
A(O, w. 0) =(w w², w' f(0,w) f(w, 0)),
r(0, w, 0) -ww ww-w" w² (Vw") (V (h(w"" -h(Oww w" ,))),,
(25)
E00,w, (0,w,0) =(VJ(0), h(w, 0) - h(),w,))).
Lemma C.1. For any t 2 Tmix the Markovian noise in the critic update, denoted by A(O,, wi, 02), satisfies
wi 01)] M1 1 E [[iO,,, wi
VT
where M1 (, + [log, m 11 p)- (BL.))BBTice (8W + 28) 28)ormix + L,, B 4wd.
Lemma C.2. For any 2 Tmix > 0, holds that
(iT wi, < M2
1 VT
where
M2 (25BL3 480BL, + LE) 3Bc 28 + 4 LL. 7n δBe
Ig = 8L, + 2BL. 48 (1
Lemma C.3. For any 2 Tmix > 0, it can be shown that
1 VT
E
[[( wi, 0.)] M3
where
M3 = (2āBL, + L2L + 4BL + 28 B²2 L Ly CT mix + 28BL
1
Li 3L, + 2BL. 48BL (1
7
13

---

On the Convergence of Continuous Single-timescale Actor-critic
D. Proof of Main Theorem
D.I. An implicit bound for critic error
Theorem D.1. Choose a; = c/VT, Br = 1/VT. for any Tmix St < T, we have
1 [B 121 2c(1 À L.
7)
log T
E BIA AB
vT ) (Capp).
(26)
Proof. From the update rule of the critic in Line 6 of Algorithm 1, we have
||+++1 wi+1l = proja (w, + (.,.)()))) wi+1ll proja (w: +
proja (wi+
Wi + ((t) wi+zll ww wi + 36, (s:)) + + 11
where (1) holds because the projection function (-) is 1-Lipschitz continuous. It follows that
A441 2| =14 + (5() + w - wi+1ll
- =I + (156 - w/ wi+1ll 11? + ((, + 2/4, w - ww++)
=||4.11*+|33f(00 + w - -wi+
+ J(),,.) [(w,, 01))
23, f(w,, 0,)) 2(4,, W w(+1)
A.1l + 2,3 (0 w/)1 + 2|1w - w
+ f( - f(W, 0())
+ 23 flw;, 0,)) + 2(4,, wi - -wit1)
where f and f are defined in Eq. (20). Taking expectation up to S1+1, have
A| 2 < 21 2 w1)1 + wi+1 +23E(Ar.
flwe, 0.)
17
(27)
+ 2 (Ai, wi) flwe, 01)) + 22/ wf wr+1)
In the sequel, we will tackle /1, I2, Ia, 14, Is respectively.
For term 41, since [If(Or, wI < 8, we have
1 = 23= < 28222.
For term 12, from Lemma B.6, it be shown that
1/ = 2|] -w $ -0211 s 2028B222
For term T3. we have
(A., f(w,, 0.)) =(Ar, f(wr, 01) - f(w;,
= =A,, (((Tc((s') (bs))) (wr -()(((())))
= =(((s))))))) a())AA
AT AoA.
14

---

On the Convergence of Continuous Single-timescale Actor-critic
follows that
Is S 21 |
For term 4, according to Lemma C.1, it holds that
4 = 2 (OO,,[A 0.)] - 2 VT
For term 1s. we will instead give an implicit upper bound. It can be shown that
W; w1+1) E(Ar, wi wi (Vw!) (0.+1 0.)) (E(A,,((WW]) 0.))
(1) Li E E| 1 - 0:11 aE(,,, -(VW)) ((TW)))T(OO.... Wi, 0.))
-
o B² L., + - (VW))=((O,,,, 0.))
n(O
- (V ((h)))))))))),,....))) W/ 0i) -
+ h/ h(,, w,
< T,
OE - (Vw;) (aanhhh(,,, wi, 0.); 13 Lg5 20 a B( (Vw)) ( (hiww, 0,) - to n1 wi 0.)))
a IE (Vwi) (g(w,, 0.) h(w 0.))) +a B( (Vwi) g(w, 0.)).
where (1) follows from the smoothness of the optimal critic shown in Lemma B.9. We will analyze J1, J2. and J3 individually.
For term J1, from the Markovian noise analysis in Lemma C.2, we have
J1 E(T w, 0.) s M2 /T
For term Jz, from the policy gradient theorem in Eq. (5), we obtain
h(w; 0.) g(w,, 0,) = E(xaa,') me =
Vo,
= =(1 - ()),)) (28)
It follows that
J/2 = B --
For term J3. we first show that
g(w;, 0,) 11.0 0,)1
< E (2(()()))))) - Vo, (+') - (d)))
- vo(+)))2
() Vo, (c(ss) Tw - Vo, (x))
(29)
SBB
[i(((s) /
wi Vo. (
2Bappp
Then we have
J3 4 Losap-
15

---

On the Convergence of Continuous Single-timescale Actor-critic
Combining J1, 12, and J3. get
4s s 2a L. + IoBL.B|A|1" Bapp + 20(1=1)22334/11111(000) +2aM2 1 VT
Plugging 11, 12, Ia, 14 and Is into Eq. (27), we obtain
E 9111 & E|| + 233 22 23M
2A A.11 + B228BBBL.a
VT
+ABLLEIIA SapBL + 2a -1) | +2aM2 VT
(1)
$ (1- 11-AB)E|A4 A 1 2a [1100-1))[48]||(|||1
+28 + 26 80 B² L3 + 26 B LgW 2cM2) 1 + 8ac L. 26
where (1) holds as the step size ratio c is chosen to satisfy 4aBLe S A3. Rearranging the above inequality, obtain
1
20(1 -
E
||
A 2 E A
I I.
X
A
+ (20 + 20 B L.
+
202 L2 + 2cM2) VT
+ ScT B Loeap.
By leveraging the O()) notation, we can further summarise our implicit analysis for the critic
1 (BIAN E|44+1 2c(1 - 7)
log 2
EI 2 AB
A LEEA)
VT + (CCup))
where the term log² 2 I arises from the presence of mix in Mj and M2. Therefore, finish the proof of Theorem D.I.
D.2. An implicit bound for actor error
Theorem D.2, Choose a c/ VT, 11/B-11// 1/VT. for any Tmix S. T, we have
O( log² T VT + (Capp).
(1 (1->)
(30)
Proof. From the update rule of actor in Line 8 of Algorithm and Lemma B.8, we have
Lg
(V) -,)
00 - 1.+112
2
wi 0.)) Lg a 2 0,)
= = ((0.)+<(VJ((.)) h(O,,
=((0,) +((v)++))) ,O,, 0,) h(w, 0,)) + + h(w,, 0,)) Ly 2 0,) 0,) h(w, 0.)) + +v h(w,, -h(w;,
= =J(0,) =J(0,) (((0))=(VV]())))))))
+ (o(VJ(()), g(: 0,)) a (VJ((.)) 0.)) - Ly - wi, 0,)
①1 J(0.) +(( 0.) h (w:, 0.)) + (V)()) h(w,, 0.) - -h(w 0.)) Lg a 22 wi. 0:)133
+ ((( +100 " 0.)) 2
where (1) follows from Eq. (28).
16

---

On the Convergence of Continuous Single-timescale Actor-critic Rearranging the above inequality and taking expectation, have
- ((0))) aLg - (B[) (1 (1=>)=
B Blln(Or, Wr, 0.)1 (V())((,), g(w;, 0.))
2
11
(31)
+ HVVJ h( 0.) h(Or, wi, 0z)) + E(VJ((.) h(w], 0.) -(w,, 01))
In the sequel, we will analyze 11, 12, 13, 14 one by one.
For term 41, since h(,,, wi, 0,) _ ,B, we have
aly E hO.,, 0,)13 ad L.g. 2
1
For term 12, from Eq. (29), we have
2 === 0.)) S 2B
For term 13, from Lemma C.3, obtain
13 E(E 0.)] S Ms VT
For term 4, it holds that
4 = ((. h(w] h(w,, 0.)) 2BE
Plugging J, T2, Ja and I into Eq. (31), we have
(1 [=))) 1 (E(J(0.+1) J(e.)) + ad² B² Lg 2BL + M3 VT (B)
a
By leveraging the (-)) notation, we can further summarise our implicit analysis for the actor as
1 [B[ J(O)) - - + O log T + (CCpp))
- =
where the term log" T' arises from the presence of 7 in M3. Therefore, complete the proof of Theorem D.2.
D.3. A novel Lyapunov analysis
Theorem D.3. Choose a c/VT,B,- L/VT, for any T 2Tmix have
log2
E A
0
+ (Capp)::
T Tuix
VT
t=mmix
(32)
T-1
log* (log²*
T
Σ E(
0
+ (Capp))
Tmix
/T
Taaix
Proof. Define
2B
1-2
L1 1-7
+
E (J))))
2B
17

---

On the Convergence of Continuous Single-timescale Actor-critic
the sum of Eq. (26) and Eq. (30) yields
2B
Bc
L -
13 [E 2
2
B| (2)
E A [
log 2 T
+ 2Ba
(B[J((r+1) J(O))) E (())) 0
+ (capp)
VT
2 Be
2B
11
A3(1 - (B) |BI 1|2 (+113) 113)
(E[J(0r+1) - J(O))) - o log² 2
+
+ ((app))
2Ba
VT
T-1
where the last inequality follows from E VJ.))) S 1/2 Since ;=
= 1/(T - -Tmix)
Σ
Lr. it can shown that
Fmix
Bc
c+
2B
L
(E|JA/12 - E|| 1114++113)
A3(1 (T - Tmix)) T=
log² T VT
+ 2 2Ba
- J(O,))
+ (CCpp))
Tmixx t=
BC
8B3²
F
llog* 2 T VT
C+
+
+ +0
+ (Capp))
A
A3(1 (T - m
Ba(T - -mix)
Choose T' 2 2mmix we have T - Tmix 2 1/211, which implies
BC
16B
2F
1
log" T
c
C+
+
+ +
(Capp)
2
A(1 7)
Be
VT
VT
2L,BC
log" T
+ 2
C +
+ ((app))
VT
Overall, we have
22oBc
1 L + O
log" T
S
+ 2
+ (Capp))
(33)
A
To make L convergence, need Bc.Bc/> X+ + 1/2 < 1, which can be achieved by choosing
A
<
(34)
4BLe
follows that
log² T /T
2 (Capp))
L
which implies
T
log T
A
2 0
+ 0 (Capp):
T Taixx I=Tmnx
VT
E|VJ((0)) o (lgg" (l08²
T VT
+ (Capp).
T Tmix
Therefore, we complete our proof.
18

---

On the Convergence of Continuous Single-timescale Actor-critic
E. Proof of Propositions
Proof of Proposition 3.1.
Proof. We show that ve is the stationary distribution of the Markov chain induced by P. by showing that ve a fixed point of the operator P, i.e.,
Pvo vg.
Define operator Pt by iterative application of the operator P:
(P' ()() = / Tolaal))((s (aaaat"-1(0) das)
From the definition of the operator pt, we can rewrite By in Eq. (4) as
vo(s) = (1 -) y (P)))ss)
0=
Then we have For term (s)(s), it holds that
Pvo(s) = -1-7)n(s)) + (Po((s)
(35)
8
Pvo(s) = (1 - (1)))
*pt+1 (())))(())))))))
(1 7)
k- ph (ss)
1
pppp((s)
k=1
1 - Vp (x))) ()))
γ 7
vo(s) 1 7 (s).
7
Plugging the above result to Eq. (35), we obtain
Pvo(s) = (1 - 7)m(s) + +7( vo(() 1-7, n(s))
= - ()sss)
3) + vo(s) - (1 ())
(s).
Suppose P has two fixed points f and then we have
Ps= Pg=9 =
Recall that for two probability distributions μ and v/ on S, the total variation distance defined as
drv(u, v) = 2 / (m(s) - v(s) ds.
Since we have
P Pg -PP Pg))
19

---

On the Convergence of Continuous Single-timescale Actor-critic
it follows that
drv (
From Eq. (10), we know that P is also a Markov kernel which does not increase the total variation distance. Therefore, can be shown that
(nv(:.))drv(PPp)) = ( (, S (frr((.g))
Therefore, we get
dr (rv(f.g)= = 0,
which means / and y are same distributions. Hence we finish our proof.
Proof of Proposition 3.2.
Proof. Recall that for two probability distributions μ and v on S, the total variation distance is defined as
drv(u, = 2 1/8 (m(s) v(s)] ds.
For two distribution f and we have
Pf- - PPp -Pp)
where the operator and P are defined in the proof of Proposition 3.1.
follows that
dTv(P,, = -ddv((P
From Eq. (10), we know that P is also a Markov kernel which does not increase the total variation distance. Therefore, it can be shown that
(Tv(Pf,Pg) = "drv(Pf,Pp) S {ddTv(f.g)
As shown in Proposition 3.1, ug is the stationary distribution of the Markov chain induced by P. For any initial distribution f, we have
dTv f.vo) =drv (f' f,P'vo)
S 7 drv (f.ve) < %
Thus, it completes the proof.
Proof of Proposition 4.4.
Proof. From the definition of the total variation distance, we have
1
/ |o, (a|s) - -To (a a) da
drv (-18) (.
-mo,
2
1
|Te (a|s) -Te, (a {) da
2 AĀ
/
< 2 A
L||0] - 021l da
1
ALll0 0zll.
where A is the bounded support of (a s) which satisfies SA da = A. Define L, == 1/2AL, which completes the proof.
20

---

On the Convergence of Continuous Single-timescale Actor-critic
F. Proof of Preliminary Lemmas Proof Lemma B.I.
Proof. This is minor adjustment to the proof of Lemma 3 in Zou et al. (2019), extending it to continuous settings. For any 0 and 02, define the transition densities respectively follows:
Po, Po.(s|ds) =/x P(ds' | (), (a|s), i= 1,2
Following from Theorem 3.1 in (Mitrophanov, 2005), we obtain
1
drv (1o, Mo,) s (fog, m #
1 Pl Poo laap.
where || llop is the operator norm defined (Mitrophanov, 2005): ||Allop == suppalllv=all and
|| ||/r denotes the
total-variation norm. Then we have
1 ((d)) -Po2)s
Po. Pozllop
sup lv
1 g(ds)
sup rv
Ps ds')l
( I9(ds)
sup
(Po. Pe.) {sss
l| [vll
sup ( Ig(ds)
/ P(ds' aTe) (da [s) 7d,( s))
l| Iw
sup [ 1g(ds))
/ P(ds' 1s, a))a))(TT (da s) To, (da s))
|| rv
sup / |9(ds)| / (TT (da (s) no, (da s))
rv=l
< 2L |0 -22l.
Therefore, we have
drv (po. S 2Lx 2[oog m #1 + 1-p 1-p'10; ||0,
0211-
For the second inequality, we have
/
(Ho, @ To, Ho, 2 To,)
- / [oo, (ds) (da (da|s) (ds) (da |s)
J / |no, (ds) (dals) = (da |s))
+ J. |(H, (ds) nod (ds) TO. (da) s))
drv (To, To,) + drv (Mo, u1;)
< L, 10 021 2L [lg
17
1 0110, 021
24, (1 + [log, m -1 - 0 - -22l--
1-
21

---

On the Convergence of Continuous Single-timescale Actor-critic
For the third inequality, have
dree
@ To, & P, no 8 P)
1 po, (ds) Te, (da P(ds' s, - no, (ds) (da Pd) |s, a,)
S. A.
/ / Me0, (ds) (da) 8) - po, (ds)To, s)
2 S.
= drv (No, & No. M0₂ 2 T
which concludes the proof.
Proof of Lemma B.2.
Proof. This a slight modification of the proof of Lemma B.2 in Wu et al. (2020), which extends it to continuous settings. From the fact that
P(s4+1 E. = 1 / P(stt = ds, ar = da, s0+1 E :)
E.)=
we have
dTv(P(5 E P,, E))
[ P((s dds at da, 8141 ds') [ J
P(s. ds, ā. da, 8 ds'))
- 2s JS
< / / IP(s: = ds = da, 81+1 = ds'') P(s: ds, = da, 8211 = ds')l
/
/
[P(O; = (ds, du, ds')) POO, (ds, da, ds')))
= dry (P(O,, .,, .)),
where the last equality requires the exchange of integral which is guaranteed by Fubini's theorem since IP is an absolute integrable function.
For the second equality, we have
drv E ),P( .)
-1 [ P(O; = (ds, ds')) P(O. = (ds, da, ds'))]
///
[P(ds' Is, (ssassaa)PPP) a))(((s,(a))) (ds, da)) - P(ds a))ss ā.) (ds, da))
/
2 2
P(ds' 8, (P((S) a:) = (dss, da)) - TP(( āe) = (ds, da))
A
1
2 2 [P(((s,) 0z) (ds, da)) P((5,, ā.) (ds, da))
(Tv(((() E P)), ā.) E e)).
22

---

On the Convergence of Continuous Single-timescale Actor-critic
For the third inequality, since 0g is dependent 86, it holds that
(Tv(( (e) E ) P((,, @+) E -)) = 1 /
2 s. / [s: ds da) PP ds, at da)l
1 2./.
/ 1/ P(s; = ds) = d0 s = s)p(a, = da 1st = s, s, = 0) - PP(5, = ds, ā. = da)
2 2.
1 / 2
[P(s ds) / P(O. do 8t S) (da - P(s dddsTT (da [d)
2
1 ///
[P(s d (da ()) 9t se - P3 = dT (da s)
A
1
[P(s E TO, (da 8) St s) P(t (T) (da s)
S
[P((s: = do) (da 8) P( dTe (da |8
A
1
P(s: = ds) / (dalss) = s) -TO.-- (dals)
2 2
+ dTv (PP( E (), E
0, 02-711 + drv (P( E P(s -))
Therefore, we finish our proof.
Proof of Lemma B.3.
Proof. Following the same proof as shown in Lemma B.1. The final results are derived by substituting the results of Lemma B.1 with 1 and p 7, outlined in Proposition 3.2.
Proof of Lemma B.4.
Proof. By the same proof as shown in Lemma B.2.
Proof of Lemma B.5.
Proof. By definition, have
J(0,) - J((2) ( E(r(s", a-)) r(s?, a²)],
where s¹ vo. a² no,. Therefore, it holds that
J(0,) -(02) B[r(s', ,a') - rrs'', --s''aa)))
s 2Fdrv (Vo, ② no, , ve, 2 To,)
S 4F (1 + - ||0 021
L,](0; -211
Proof of Lemma B.6.
Proof. From Eq. (16), we have
Aow 10) be.
23

---

On the Convergence of Continuous Single-timescale Actor-critic
where Ag ( 76((5)) and by == aa) ())))) The expectation is taken over the stationary distribution no. the action To( 8), and the transition probability kernel s' ~ a,)
Denote wi, w ق as the unique solutions of the following equations respectively:
Ao.wi bor-
Ao.wi bi,
Ao,wi = b2.
First we bound ||wj - Φ1 ||. By definition, we have
| - -611 S 1| - -A,,11 |1,11||b,,1
It can be shown that
A 8,
1
A 0%2
AAo Ao, ) 11
which implies
| ا1 || $ |A
Ao.
Ao, |1| A |1l|||bbg be,
Then we bound ||ا w66
اققا will S | l - bbg 11.
By Assumption 4.1, the eigenvalues of Ao, are bounded from below by À > therefore || || S Also
Also llbo,
due to the assumption that [r(s, a)l S F, and [|<(s)] - To bound | Ae_ll and | bo, ll. we first note that
|| - Ae. s 2 sup ( - 70((8) I11 2drr E .), E E.)
s.S'ES
s (PP P) E -),
and
llbe, -ball S [[[r(s (1)) < 2FdTv(P(O) E E.),P(O² E -)):
where O' is the tuple obtained by s² po. at To, (-1s", and s' P(-lst,a*). And the total variation norm can be bounded by Lemma B.1 as:
1
dTv -)), E .) s 2L, (1+ [log, m #1 +
1110 110
021
1 1-p
Collecting the above results, we have
||w| will < ||w will + ||ا1 will
)
< (8 4A -A--1-)( Tum (1 [og, m
'1+ m=1
10: 0211:
p
and we set Lec = -8X-27 + 41 17) + flog, m 11 + 1/(1 - -p) to obtain the final result.
Proof of Lemma B.7.
Proof. Lemma B.7 is adopted as an assumption Chen et al. (2021) and Chen & Zhao (2024), but it directly follows from Heidergott & Hordijk (2003), as pointed out by Olshevsky & Gharesifard (2023).
Proof Lemma B.8.
Proof. See proof in Lemma 3.2 of Zhang al. (2020a).
Proof of Lemma B.9.
Proof. See the proof in Proposition 8 of Chen al. (2021).
24

---

On the Convergence of Continuous Single-timescale Actor-critic
G. Proof of Markovian Noise
Proof of Lemma C.1.
Proof. We will divide the proof of this lemma into five steps.
Step 1. show that for any 01. 01, w, and tuple (s,, a, 8'), we have
A(O, w, 01) - A(O, w. 02) < (800 (1+ + [logp m m= $1 + 1-p' ) + 28L.)1101 -2111-
(36)
By the definition of A(O w, 0) in Eq. (25), we have A(O,w,0)) w. - A(O, (. 02) = ( wi. w) ((w, - w f(0, - f(w,
< w! wi, [(0,w) - f(w, - -ww I - f(w,02))
11
+ (w wi. ((), - Flw, 02)) - (w (w- w f(), - flw. 02)
For term /, we have
11 (/ flw, 02) f(w,0i))
< 20 f(w 02) - f(w,0[]))
450dTv (wo, 8 _e, @ &P, 100, @ To, & P)
01 + [log, m -1 + 1-p |0 0211
where (1) comes from Lemma B.1.
For term Iz. we have
1 = |w0 wi, f(O,w) f(w,02))
5 20 wi -wil
2 25 0 - 0211.
where (1) follows from Lemma B.6. Combining 1, and I2, we have
1 ) 281. -A2l1
A(O,w, w. 01) A(0,w, w. 02) < (SWōT. + [lgp m mmmm1111111 #1
1 1-pp p
Step 2. show that for any 0, w1, w2, and tuple O(s, a, s'), we have
A1, 0) A(O, w2, 0) S (80 + 25) | - well.
(37)
According to the definition, we have
A(O, w1. 0)- A(O, w2, 0) = (w) w" f(0,ww) w1) - f(w,, 0)) - E(w2 - wn, f((, - f(we, 0)) (wi w/ ((),ww) f(ww, 0)) - (w- w- F(0, w2) f( 0))
+ (wi) w., f(0,wz) - f(w2, 0)) (w2 - w w(0,ww) 5(wz, 0))
Ta
For term 4, we have
1 = (Wi w², .f(0,w)) - f(ws,, - (f(O) w2) f( 0))
< 20) (1) w1) f((0 w2)l [[ 0) f(wr, 0)1)
< 8u 8i||w1 wall.
25

---

On the Convergence of Continuous Single-timescale Actor-critic
For term 12, have
1 = (w2 w1. w(0,w) - f(w2, 01) - 20|lwi w2ll
Combining 1 and 1z, we have
A(O, w1, 0) A(O, w2 0) - (8 28) W1 w2ll.
Step 3: show that for tuples O (st, des S1+1) and Ō2 (5t, ae: Se+1). Conditioning on Fi-7, we have
E -:000:,,
0(-)] 400L Σ
0 01-
(38)
let-r
By the definition of total variation distance, we have
[(A 0c-r) A(Ōr, Wr 0r-r)] - J(0 -(0
(39)
E -(Fi-))).
E
By Lemma B.2, we get
dTv(P(O, E (F:-.,, ((Ft)))
=
E -(FF))))
3 (P(s E F(Fr), E (F+-)) L,E 0:--|
S ddv E (F, E (F L, 0. 01-
Repeat the ahove argument from 1 to f - T, we have
dr (P(O: E (FF-)), E (Fi+)) < T. Σ
E 0.-
(40)
k=t-r
Plugging Eq. (40) into Eq. (39), we get
4WōL 0 S
Σ E 0.-
k=t-r
Step 4: show that conditioning on Fi-T, we have
(1,0 4w0mp=-1
(41)
can be shown that
Then we have
E [[ w, -(-r,
=E[A(O, W, --) A(O W,,
[W( w/ f(O,, w) f(0,_ w/-r]]
< 4w (P(O, = (FF (4,,,,0... 8 _ & P)
2 4wommp--1
where (1) follows from Assumption 4.2.
26

---

On the Convergence of Continuous Single-timescale Actor-critic
Step 5: show that for 2 Tmixx have
E wr, 0.)] M1 1
VT
where M1 = 21 + [lgp m + (1 -1-110 -0) + 4δTmix + 08,,5Br + 25.
Combining Eq. (36), Eq. (37), Eq. (38), and Eq. (41), we have
B[A 0.)] =B [(O,,, wi 0.) A(O,, Wi, O2 + [[A(OE wi, Oc-r) : 0r-r)
+ E A((, WT-, 0.-r) - A(O W1, 0 + (i
<(800L (1 [logp 1
+ 28L.) 0.- + (8w 16)| -
+ 450L
Σ
0 0.- + 4wdmpp-1
k=t-r
(1)
S (8 + flogp m -1 + 1 + 26
Σ
ad + (8W + 26)
Σ k=1-7
k=t-r
+ 4.5L Σ
adB + 4wompp
i=t-
1
+88 25) 1 VT
<(80LL (1 flogp '1
+ 28L.)TÔB
1-p"
VT
+ +458L,728B 4w0mp=-1
VT
(2)
1 1-p)
(180 + flgg, m $1 +
BTT (8w + 28) + 4: 15, m C + 4w0) VT
where (I) comes from the update rule of the critic and the actor, (2) followed by choosing T Tmix- Therefore, we conclude our proof.
Proof of Lemma C.2
Proof. We will divide the proof of this lemma into five steps.
Step 1: show that for any O, w, 0,, O2, we have
[[(0, 0, 01) T(O,w, 02)1 < (25B12 BT + 4g)11) 0211.
(42)
where Lj, = + 46
Since T(O, w. 0) = (w - --, (Vw*) (h(w", 0) ()),)),,,))))
0))), we represent h(w" 0) - -E [,, 0)), where E, the shorthand of Bo~ .P. In the following, we will show that each term in I(O, w, 0) Lipschitz with respect to
Term w is not related to 0, term w' (0) is Lipschit according to Lemma B.6, and term Vw" (0) is L, L--iisschitz according to Lemma B.9.
For term (OO, wt, 0), we have
[h(O0, 01) h(O, 02) < [1(00,i, h(O, 02) + ||(00, 02) h(, (0 0z) < V log mo, (a s) Vlog Te, (a s)ll 2B| w ||
< (ōL BBL,)| 02l1
Hence we have h(O,w", ,.) To -ipsschci where In 8L. 2BL
27

---

On the Convergence of Continuous Single-timescale Actor-critic
For term Eglh(O,,s w 0)} have
Ee [h(O, - 01)] Es, (0,0 02)]l
= Ee, wi. Es, [h(O,, 82)1l + [E, [h(O, wi. 02) Es, [h(O, wj. 02)]l
s Eo, ||h(O,, 01) h(O, 02)1 Ee, [h(O, w/. 02)] Es, (5,
s Ln 100 02ll ||E,, (h( 02) Es, [1 02]]
3 Ln 100 02 + 28BdTv (vo. me, 2 P. v2_ X no 8 P)
2 (Ln - 48 (1
-
Ln 10 022l.
where (1) follows from Lemma B.3 and L, 8L1 + 2BL + 48BL, + (1-
Then we have w w is 2u-bounded and Le-Liscchitz; Vwg is bo-bnddded and Lg-Liscchitz; Eo(h(O, ,), h(O, w 0) is 28 B-bondde and 2I.g. -Lipschitz By the triangle inequality, we have
[T(O, w. 1 I(O, w, 02)1 - (28B13 BL. + Lo -22l-- Step show that for any O, w1, W2, 0, we have
[r( 0) - rr,,,, 0)11 5 22BLL|| -221.
(43)
can be shown that
[T(O,w1,0) 0) - r(0,w,, 0)] = (wi w2, (Vw") (Va""""(""""""
(h(w", h(0,w=",00 - 26BLo - well.
Step 3: show that for tuples Ō, = (5t, âz $141) and O2 (3 ae. St+1). Conditioning on Fi-7, we have
B [ Wi-r, - P. 0r-))]| < LL Σ
E E 0,
(44)
By definition [(O, w. 0) in Eq. (25), we have
[[[[T wi-r; Oc-r) ((0,,
= |B| wi (Vwi (h(O,, (wwi=))((h(,,, 0(-1 0,-r) wi,
(45)
<4wiBL.drv (P(O, (FF-r), -(Fr-))),
where the inequality comes from the definition of total variation distance.
By Lemma B.4, we get
(F--) -(F-r))
= dT) EFFrr), āz) E ((F
I
E ( E (Fr-))) + L, - 0.-
I $ ddiv(P(OL-15 ((F.), (FF 0. 1.-
Repeat the above argument from t to t - T, we have
drv (P(Ō. E (F E (F.F))) < Thp Σ
El 0 0.r
(46)
k=t-T
Plugging Eq. (46) into Eq. (45), we have
E T W:-r, 0.-r) I(O,, w, 0,-r)ll < 400BL.
Σ
E E 0 0.-
k=t-T
28

---

On the Convergence of Continuous Single-timescale Actor-critic
Step 4: show that conditioning on Fe-ri have
(47)
It can be shown that
1 ( 0 - 0r-r, [ wh.,, Oz 02-r)]
AwōBL (P(O, -(Fe-r). 0 no.- P);
where (1) is due to the fact that 0 is from the discounted state visitation distribution which satisfies BIT(O" We-r: Fe-r) = 0 and (2) follows from the definition of total variation distance. From Proposition 3.2, we know that
(PP E 1o..)))) STT1
Therefore, we have
| [T Wi Wi-r, 0c-r)] < E 8 To. P)
E
(P((L, -- M0. @ To...
dTv ((,
S 4W0BLeT
Step show that for 2 Tmixx we have
E B[ wi, 0:)l
0;)] s M2 1
/T
where M2 = (28BL3 + BL, +
+ 25BL. + L BeT + 4DdBLe Combining Eq. (42), Eq. (43), Eq. (44), and Eq. (47), we have
E[T(O,, 0,) = Wi 0₂) - I(O wi O E wi 01-7) -10 0--))
+ ET Wi W - | - 0)) )] ( W 0t.r)]
<(28BL) + 48w BI, + Aw
- 0.- + 28 Wi
+ +W88LLL Σ
0 0,-r|| + 4wd LL
(1)
(25BL2 45WBL. + 45LLLR)
Σ k=t-7
aδB + 28BL
Σ 88
k=l-T
+ 408BL.L Σ
aδB + 4
Rm - 7 t=1-
+ + 45L
+ 28
VT
VT
+ L 28B + 4WōBL
VT
(20B12- 48 + Aw L. 11, Bermix + 25
+ 4wōBLe)
VT
where (I) comes from the update rule of the critic and the actor, (2) followed by choosing T = Tmix- Thus we conclude our proof.
Proof of Lemma C.3
29

---

On the Convergence of Continuous Single-timescale Actor-critic
Proof. We will divide the proof of this lemma into four steps.
Step 1: show that for any O, 01, O2, have
|E w. 01) - E( (2ABL, + 21,14))100 -
(48)
Since [ w. 0) (V) 1h (1 w,, we will show that each term in B(O, 0) Lipschitz.
For the term (J(O), know it's bo-bndde and , -ipiiscchi For term Eg (O, w. 0)] h(O, w. 0), by the same argument shown in the proof of Lemma C.2, it's -bounddd and 2 Lipsschitz. By the triangle inequality, we have
|E w, 01) - E(0, w. 02)1l < (2ABL. + 2L, 1b) 02l1-
Step show that for any O, w1, w2, 0, we have
|=[0, w1, 0) - B(0, 0) < 4BL,||wr w2ll
(49)
follows that
|1 w2,, 0) (1,,)) -2,,,,,,
(V w1, 0)] - Eo (o 0))
2BL, - w2ll 2BL, - well
4BLr|l/- -
Step 3: show that for tuples Ō, (8t, (e, 8641) and O (5t, dee 81+1). Conditioning on Fe-r, we have
- 0,-)11 -(00)
8BL Σ
E|10, - 0.-r11-
(50)
By definition of E(O,w w, 0). we have
B [ w,r 0._r) -10.
-h(O,,, W,,0,,wr-,0000 0r-r]]1 -25BL.jdvvP(()) E (FFFT),, -
where the inequality comes from the definition of total variation distance. The total variation distance between Ô and O has been computed in Eq. (46). Plugging Eq. (46) into the above inequality, we get
| w.,,,, Or-r) -(0-, wr 0z- < 25BL,
O O--rlI- k=t-7
Σ
Step 4: show that conditioning on Fe-r, we have
(51)
holds that
||| W, 0 0rr))]
Wi-T, 0.-r)ll
(F(L, E - :Firr), 8 To.., 8 P)
(P az) E - Vo... 8 T
28BL, E (F,-),
(3) < 28BL
where (1) is due to the fact that O is sampled from the discounted state visitation distribution which satisfies E[E(O"_,, Wi-7, (..,,)r-)lll F = 0, (2) follows from the definition of total variation distance, and (3) comes from Proposition 3.2.
30

---

On the Convergence of Continuous Single-timescale Actor-critic
Step 5: show that for 2 Tmixx have
1
E [( wi, 0.)] S M3 VT
where M3 = (28BL, + 22) + 4BLL5ōmmix + 20 B L. mix + 28BLJ.
Combining Eq. (48), Eq. (49), Eq. (50), and Eq. (51), we can decompose the Markovian bias as
wr, E B| we. 0.)] = B B w. 02) - =(θ wr. 0,-,) )] + [[ wi. P2-r) - Wir, 0(-)) + +E[=(O,, Wi- 02-r) B(O,, W 0 0[] EE Wi.r, 0e-r)]
s (2ABL.g + 11, 0:-r1 + 4BL, W1 w2ll
+ +28
Σ
El 0-- + 28
k=t--
(1) (20BLg + 22,
Σ
adB 4BLJ
Σ
36 + 20BL,Ln E
Σ
adB + 28BL
k=t-T
k=t-T
k=t- i=t-T
_ (20BL, + 2L,Lz))BeTmix + J + 22 La Lo + 22)LJ) 1
where (1) owes to the update rule of the actor and (2) is followed by choosing T = Tmixx Hence we conclude our proof.
31


Reviews:
[{"review_id": "jNM38u8Zy9", "reviewer": "Reviewer_DMy1", "summary": "This paper considers the problem of analyzing actor-critic algorithms for the discounted, continuous spaces setting when the actor and critic updates occur on the same timescale. The key idea in the analysis is to sample from two distinct processes: a \"discounted process\" corresponding to the discounted state occupancy measures of the sequence of policies, and an \"undiscounted process\" corresponding to the undiscounted state occupancy measures of those policies (the \"discounted/undiscounted process\" terminology is mine, not the paper's). Samples from the discounted process are used to perform actor updates, while samples from the undiscounted process are used to perform critic updates in Algorithm 1. Convergence results that recover state-of-the-art rates proved for less general settings are provided for Algorithm 1 under the assumption that linear function approximation is used for the critic.\n\n---\n**Post-rebuttal comment:** after the author rebuttal, I maintain that the proposed approach does not achieve the \"holy grail\" described in **Strengths** below. Nonetheless, after the rebuttal more clearly situated their analysis within that of the literature on discounted AC analyses, I am more convinced that the paper provides a useful, meaningful step in this direction. I am increasing my score accordingly.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**(Weakness \\& Q4: on single-simple)**\n\n1. The terminology ''single-sample\" follows the seminal work [Olshevsky \\& Gharesifard, 2023], where they directly assume sampling from visitation distribution and stationary distribution for updating actor and critic, respectively. It refers to the fact that at each iteration, the critic and the actor are each updated using a single sample. \n2. Our analysis can accommodate the case where ''a single sample generated from the same stochastic process is used to update both the actor and the critic'', as suggested by the reviewer. To achieve this, we can modify the sampling scheme so that the critic is also updated using the same samples from the Markov chain $(\\pi_\\theta, \\hat{P})$ as the actor. We would like to highlight that our theoretical analysis would still apply under this alternative sampling scheme. The current presentation of sampling from $(\\pi_\\theta, P)$ for the critic update simply follows the existing setup in the literature of on-policy actor-critic analysis. The proposed modification can be viewed as an extension to analyze a special off-policy version.\n3. **Sampling from two Markov processes does not force the decoupling or simplify the analysis.** In fact, our analysis directly copes with the coupling between the actor and critic, which can be seen in the Proof Sketch. In particular, the term $I_5$ in the critic error analysis is coupled with the actor error and is ultimately bounded by $\\mathcal{O}(\\mathbb{E}[\\\\|\\Delta_t\\\\| \\\\|\\nabla J(\\theta_t)\\\\|])$ in Eq.(26). Conversely, $ I_4$ in the actor error analysis is coupled with the critic error and simplifies to $\\mathcal{O}(\\mathbb{E}[\\\\|\\nabla J(\\theta_t)\\\\| \\\\|\\Delta_t\\\\|])$ in Eq.(30). Due to this mutual dependence, we define a novel Lyapunov function that captures both the actor and the critic errors, enabling a unified analysis of their convergence. \n4. **Our work is by far the most practical analysis**, in the sense that we address the most widely used single-timescale _discounted reward formulation_, and our analysis does not require sampling from unknown distributions (i.e., the stationary distribution and the discounted state visitation distribution). Moreover, as mentioned in Point 2, our analysis still holds with minor modifications to accommodate the case of using the same samples for updating both critic and actor.\n\n**(Q1: Key innovations for extending previous results to continuous space)**\n\nPrevious results derived for finite action space assume Lipschitz constants that scale with the number of actions ($|\\mathcal{A}|$), which, however, becomes meaningless in the case of the uncountable continuous space. We observe that the dependence on $|\\mathcal{A}|$ stems from the need to bound the evolution of the stochastic processes defined in Eq. (12) and Eq. (13) over the action space. This evolution is mainly governed by the policy $\\pi_{\\theta}$. We demonstrate (formally established in Proposition 4.4) that if the total variation distance between two policies is Lipschitz continuous, then the evolution of the stochastic process in the action space can be effectively controlled without assuming the finiteness of the action set. This novel insight and development allow us to extend several foundation lemmas (Appendix B) to the continuous action setting. Such extension is further enabled by the proposed operator-based analysis, which conveniently handles the continuous distribution throughout the proof, including in the verification of Propositions 3.1 and 3.2.\n\n**(Q2: on the notation)**\n\nThanks for pointing out the typo. It should be $\\hat{P}(\\cdot | \\hat{s}_t, \\hat{a}_t)$.\n\n**(Q3: Relation to existing actor-critic analyzed in the literature)**\n\nYes, it is correct. This is the same sampling scheme also employed in [Shen et al. 2023]. However, their analysis only handles the two-timescale AC algorithm on finite state-action space. In Konda's thesis, this artificial MDP is only constructed to utilize its property that its average reward equals the original MDP's discounted reward induced by $(\\pi_\\theta, P)$. It's not analyzed for convergence. In addition, [Zhang et al. 2020a] employ a different sampling scheme to approximate the discounted occupancy measure. However, their approach relies on a multi-sample procedure.  Moreover, they also require a simulator with a state-reset function. \n\nExisting literature on analyzing AC requires samples from the unknown visitation distribution for updating actor, which requires a simulator as well. [Shen et al. 2023] needs to assume the same simulator as ours. For i.i.d. sampling [Chen et al., 2021; Olshevsky \\& Gharesifard (2023)], one has to run the simulator for sufficiently many steps under the current policy $\\pi_{\\theta_t}$ to approximate the visitation distribution. This inevitably takes a very long time and requires significant modification of the simulator as well. But our setting only requires a reset, which is much simpler and more time-efficient.", "claims_and_evidence": "The claims made are broadly supported by the results provided, with the caveats discussed in the Weaknesses part of **Strengths and Weaknesses** below.", "methods_and_evaluation_criteria": "n/a", "theoretical_claims": "The proof sketch outlined in the main body appears sound. I did not verify the results in the appendix in detail.", "experimental_designs_or_analyses": "n/a", "relation_to_broader_scientific_literature": "The paper proposes and analyzes a single-timescale -- but not single-sample -- actor-critic algorithm for continuous spaces. The related works section adequately situates these results within the relevant context.", "essential_references_not_discussed": "None, to my knowledge.", "other_strengths_and_weaknesses": "**Strengths**\nFinite-time analysis of actor-critic algorithms has seen a great deal of activity over the past several years. The holy grail of such analyses is to establish finite-time convergence of the actor-critic algorithm most common in practice: a single sample generated from the same stochastic process is used to update both the actor and the critic (single-sample), and the actor and critic update stepsizes are constant factor multiples of one another (single-timescale). This has been achieved for the average-reward setting, but to my knowledge has remained open for the discounted setting. This paper partially addresses this gap, and the topic of the paper is therefore definitely of interest to the theoretical reinforcement learning (RL) community. Though the scheme of eq. (9) for sampling from the discounted occupancy measure has long been known (see, e.g., the thesis [Konda, 2002] or more recently [Zhang et al., 2020a]), the \"operator-based analysis\" used to establish the counterpart of the uniform ergodicity property provided in Proposition 3.2 is interesting and the proposition itself is of potentially broader usefulness to the RL researchers interested in policy gradient analyses.\n\n\n**Weaknesses**\nMy primary concern is the nature of sampling procedure introduced in Algorithm 1 to forcibly and artificially \"decouple\" the discounted and undiscounted processes used in the actor and critic estimation procedures. Due to this, the algorithm under consideration is not single-sample, and no longer tracks the \"holy grail\" of finite-time actor-critic analyses described in **Strengths** above. One of the attractive features of the analysis of [Chen & Zhao, 2024] for the average-reward setting is its ability to directly cope with the coupling between the actor and critic in the single-sample regime and not resort to artificial means to force decoupling. The approach of the present work falls short of this, analyzing an impractical algorithm that does not resemble what is used in practice. This negatively impacts the signficance of the contribution and its potential relevance to the community.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "1. The \"new operator-based analysis\" results presented in Appendix B appear to be restatements of existing results (e.g., from [Chen & Zhao, 2024], [Chen et al., 2021], [Zhang et al., 2020a]). What are the key technical innovations that were required in extending these results to the continuous state and action space setting?\n2. If line 5 of Algorithm 1 is correct as is, then the sequence $\\{ \\hat{O}_t \\}$ does not follow the desired discounted process from eq. (13). Should $s_t$ be replaced by $\\hat{s}_t$ in line 5 of Algorithm 1?\n3. Algorithm 1 appears to require that two distinct stochastic processes $\\{ O_t \\}$ and $\\{ \\hat{O}_t \\}$ be simulated in parallel and that the simulator used to generate $\\{ \\hat{O}_t \\}$ allow arbitrary resets. Is this correct? If so, can you comment on how this algorithm relates to others considered in the literature?\n4. If the current work is not \"single-sample\" for the reasons described above, can you elaborate on either (i) how the current work lays important foundations for subsequent development of a \"holy grail\" single-sample, single-timescale analysis, or (ii) why a single-sample analysis is not possible for the discounted setting. If the current work *is* single-sample, can you explain how?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9wkKdMgp0j", "reviewer": "Reviewer_4oXm", "summary": "This paper addresses the theoretical understanding of single-timescale actor-critic (AC) algorithms in continuous state-action spaces, a widely used reinforcement learning (RL) approach for continuous control tasks such as robotics. While actor-critic methods have demonstrated empirical success, existing theoretical analyses largely focus on finite state-action spaces and impractical simplifications like double-loop updates or two-timescale learning, which introduce artificial decoupling between the actor and critic. The paper aims to close this gap by establishing finite-time convergence guarantees for the canonical single-timescale AC algorithm with Markovian sampling, where both the actor and critic update simultaneously.\n\nTo achieve this, the authors use a Lyapunov-based convergence analysis framework, which offers a unified and less conservative characterization of both the actor and the critic.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**(On removing linear function assumption)**\n\nThank you for your suggestion regarding the removal of the linear function approximation assumption for the value function. We are aware of recent works (e.g., Tian et al., 2023; Ke et al., 2024) that employ deep neural networks for value function approximation. However, these approaches often rely on additional assumptions (e.g., Tian et al., 2023) to ensure theoretical tractability. We plan to further investigate these results and explore how to extend our analysis to broader classes of function approximators under milder assumptions.", "claims_and_evidence": "This is a theoretical paper so the claim is that they provide a state of the art sample complexity of the actor critic algorithm with  a single loop, no i.i.d assumption and continuous state action space.", "methods_and_evaluation_criteria": "No methods or evaluations are given as the paper is theoretical in nature.", "theoretical_claims": "The theorteical claims of the paper seem to be sound.", "experimental_designs_or_analyses": "There are no experiments performed as the paper is purely theoretical in nature.", "relation_to_broader_scientific_literature": "The paper is essentially extending the analyses (Olshevsky & Gharesifard, 2023) and  (Chen & Zhao, 2024). it describes a  Lyapunov analysis framework similar to the one in (Tian et al., 2023) to obtain global convergence for a single loop actor critic with continous state action spaces.\n\nConvergence of actor-critic with multi-layer neural networks, H Tian, A Olshevsky, Y Paschalidis , NeurIPS 2023.", "essential_references_not_discussed": "To my knowledge there do not seem to be any significant references missed by the authors.", "other_strengths_and_weaknesses": "The one place I think there can be improvement is in the linear function assumption on the value function. That makes the result in my opinion less relevant than some existing ones where the value function is not restricted to be linear functions.", "other_comments_or_suggestions": "I would suggest the authors to explore removing the linear function assumption on the value function by implementing a local linearization method as laid out in (Ke et al., 2024)\n\nAn improved finite-time analysis of temporal difference learning with deep neural networks, Z Ke, Z Wen, J Zhang: ICML 2024.", "questions_for_authors": "None", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "N1B0qvS2I0", "reviewer": "Reviewer_z7XF", "summary": "The paper analyzes the single-timescale actor-critic with TD(0) updates for the critic and REINFORCE with a baseline for the actor, with linear function approximation for continuous state-action spaces. The samples are taken from a single (Markovian) trajectory, while a generative model that enables an independent sample from the given initial state distribution is assumed. Under standard assumptions on the Lipschitz continuity of the policy parameterization and uniform ergodicity, convergence to a stationary point up to a function approximation error was proved.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**(Q1: challenges in dealing with continuous action space.)**\n\nPrevious results derived for finite action space assume Lipschitz constants that scale with the number of actions ($|\\mathcal{A}|$), which, however, becomes meaningless in the case of the uncountable continuous space. We observe that the dependence on $|\\mathcal{A}|$ stems from the need to bound the evolution of the stochastic processes defined in Eq. (12) and Eq. (13) over the action space. This evolution is mainly governed by the policy $\\pi_{\\theta}$. We demonstrate (formally established in Proposition 4.4) that if the total variation distance between two policies is Lipschitz continuous, then the evolution of the stochastic process in the action space can be effectively controlled without assuming the finiteness of the action set. This novel insight and development allow us to extend several foundational lemmas (Appendix B) to the continuous action setting. Such extension is further enabled by the proposed operator-based analysis, which conveniently handles the continuous distribution throughout the proof, including in the verification of Propositions 3.1 and 3.2.\n\n**(Q2: requirement to have i.i.d. samples from $\\eta$.)**\n\nThank you for your question. Note that existing analysis requires i.i.d. samples from the discounted state visitation distribution for updating the actor, not from the initial distribution. The former is unknown. It is difficult to directly sample it, even approximately, in a simulator given its form. The initial distribution is a predefined distribution over states, and its i.i.d sampling is easy. The key challenge here is how to sample from the unknown discounted state visitation distribution approximately.\nThe assumption of a known initial distribution is standard in the discounted setting. As shown in Eq. (3), the objective function is defined as the integral of the value function $V_\\theta(s)$, weighted by the initial state distribution $\\eta$, over the state space. Accordingly, we assume access to $\\eta$, which allows i.i.d. sampling from this distribution. \nThis requirement might be removed by identifying a class of behavior policies for state sampling that are guaranteed to provide a good approximation to the true value functions and policy gradient estimate. The existing Markov chain $(\\pi_\\theta, \\widehat{P})$ may serve as a special example to examine the desired characteristics that such distributions should satisfy. It will be our future research.\n\n**(Q3: on Assumption 4.3.)**\n\nLog-linear policies satisfy this assumption under the condition that the feature map $\\phi(s,a)$ is bounded and the action space is finite. Moreover, as noted in our manuscript, certain continuous policy classes—such as the uniform distribution, truncated Gaussian distribution, and Beta distribution—can also satisfy this assumption.\n\n**(On other suggestions.)**\n\nThanks for your advice. We will mention the use of linear function approximation to address large state-action spaces earlier. We will fix the time index of the policy parameter $\\theta$, which is $\\theta_t$. \n\nThank you for highlighting this interesting problem. Establishing optimality guarantees for AC or NAC methods typically requires the underlying optimization problem to be convex or to satisfy properties such as gradient domination. We view the convergence of AC and NAC to an optimal policy in continuous action spaces as an important direction for future work.", "claims_and_evidence": "It is a theoretical paper, and the claims are supported with corresponding statements along with their proofs.", "methods_and_evaluation_criteria": "There is no numerical study in the paper.", "theoretical_claims": "I checked the proofs of the main theorems. They seem to be correct.", "experimental_designs_or_analyses": "No experimental designs or analyses in the paper.", "relation_to_broader_scientific_literature": "The paper is complementing the theoretical study of single-timescale actor-critic methods in two directions: (1) continuous/uncountable state-action spaces, and (2) Markovian sampling.\n\nThe main challenges that are inherent to continuous state-action spaces can be more elaborated. In its current form, given the uniform Lipchitz continuity of the parametric policies, linear function approximation and uniform ergodicity, the analysis seems similar to the actor-critic methods for countable state-action spaces. What makes it particularly challenging and different in this particular setting, and how were these challenges addressed? This could be very important.\n\nSecondly, the Markovian sampling for \\widehat{O}_t in (9) requires independent samples from the initial state distribution \\eta with probability (1-\\gamma). If one has access to this mechanism, i.i.d. sampling can also be performed. As such, the need to use such a simulator weakens the sampling argument in this paper. Can this requirement to have i.i.d. samples from \\eta be removed?", "essential_references_not_discussed": "The list of references seems sufficient.", "other_strengths_and_weaknesses": "Please see my previous comments regarding the sampling.\n\nRegarding Assumption 4.3, does a specific class of policies (e.g., log-linear) satisfy these Lipschitz continuity claims?", "other_comments_or_suggestions": "- The use of linear function approximation to address large state-action spaces can be specified earlier. It is mentioned for the first time in Section 3, which is a bit late.\n\n- In (7), (9) and Algorithm 1 (Lines 4 and 5), the time index of the policy parameter \\theta was not given. I guess it should be \\theta_t in these equations.", "questions_for_authors": "The analysis in this paper mainly establishes convergence to a stationary point. The natural policy gradient approach (Kakade, 2001), (Cen et al., 2020), (Agarwal et al., 2021) can provide finite-time optimality guarantees up to the usual function approximation errors. Is it possible to extend this approach to the natural actor-critic (NAC) setting? In those results the iteration complexity grows at a rate O(log|A|), and it would be quite interesting to see whether it can be possible to achieve convergence to an optimal policy in a continuous action space where |A|=\\infty.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Gw1ZARv18P", "reviewer": "Reviewer_R9ou", "summary": "The paper presents a finite time convergence analysis of the single timescale, single loop actor-critic algorithm with Markovian sampling in the discounted reward continuous state action space setting. The main contributions include - (a) extending to continuous state action space using an operator based analysis; (b) Markovian sampling for both actor and critic; and (c) novel Lyapunov function to analyze actor and critic simultaneously.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**(Claim 1: on new operator-based analysis.)**\n\nOperator-based analysis is employed not only to handle the lemmas in Appendix B but also to accommodate the continuous distribution throughout the proof. For instance, it is used in establishing Propositions 3.1 and 3.2.\n\nPrior to our work, it remained unclear how to extend single-timescale actor-critic methods to continuous action spaces. This is precisely why (Chen et al, 2021) and (Chen \\& Zhao, 2024) consider continuous state spaces but restrict the action space to be finite—an uncommon and limiting assumption.\n\nIn analyzing the most challenging case of single-timescale actor-critic methods, one must rely on several previously established lemmas (see Appendix B) that state the regularity of the problem. However, these lemmas are derived for finite action space assume Lipschitz constants that scale with the number of actions ($|\\mathcal{A}|$), which, however, becomes meaningless in the case of the uncountable continuous space. We observe that the dependence on $|\\mathcal{A}|$ stems from the need to bound the evolution of the stochastic processes defined in Eq. (12) and Eq. (13) over the action space. This evolution is mainly governed by the policy $\\pi_{\\theta}$. We demonstrate (formally established in Proposition 4.4) that if the total variation distance between two policies is Lipschitz continuous, then the evolution of the stochastic process in the action space can be effectively controlled without assuming the finiteness of the action set. This novel insight and development allow us to extend several foundational lemmas (Appendix B) to the continuous action setting. Such extension is further enabled by the proposed operator-based analysis, which conveniently handles the continuous distribution throughout the proof, including in the verification of Propositions 3.1 and 3.2.\n\n**(Claim 2: on Markovian sampling in the discounted setting.)**\n\nWe acknowledge that Markovian sampling in the discounted setting has been analyzed in [1]. Nonetheless, this does not weaken our contribution.\n\nFirst, several key propositions essential for our analysis are not presented in [1]. For instance, Proposition 3.1 plays a central role in our framework, yet it is not established in [1]. Even Proposition 3.2, while stated in [1], is assumed without proof. In contrast, we rigorously establish these results within a continuous setting.\n\nFurthermore, our work addresses Markovian sampling under a **single-timescale** formulation, whereas [1] considers the **two-timescale case**. As a result, the treatment of Markovian noise in our analysis is fundamentally different from those in [1]. In fact, our considered setting is significantly more challenging than the two-timescale case and requires the development of new analysis techniques.\n\nWe acknowledge that [1] is a valuable contribution. As emphasized in the Introduction, the analyses of single-timescale and two-timescale actor-critic methods are fundamentally different. Since Table 1 is intended to compare only single-timescale methods, we did not include [1] in the comparison.\n\n**(Claim 3: on Lyapunov function.)**\n\nWe respectfully disagree with the claim that our use of a Lyapunov function is akin to the interconnected system approach. In our analysis, we sum the critic and actor errors into a unified loss function $\\mathcal{L}$ and convert all error terms into a single inequality involving $\\mathcal{L}$, as shown in Eq. (33). In contrast, (Chen \\& Zhao, 2024) track three distinct error terms and construct an interconnected system of three coupled inequalities. It remains unclear whether the latter case admits a Lyapunov-like formulation that combines the three errors into a single function and establishes a unified inequality.\n\nThat said, we agree that from a more abstract mathematical standpoint, all such approaches can be interpreted as sequences of intricate inequality manipulations.", "claims_and_evidence": "While the problem setting (continuous state action space; single timescale; Markovian sampling) considered in this paper is interesting and important to gain a theoretical understanding of, I believe the authors overclaim the novelty of the contributions of the paper in the following ways:\n- new operator based analysis to handle intricacies arising from uncountable state space - the lemmas presented in Appendix B are a very straightforward extension from the discrete to continuous state action space\n- Markovian sampling in the discounted setting has been already analyzed in Section 4 of [1]\n- Lyapunov function to analyze the error of critic and actor together in Theorem D.3 is akin to the interconnected system analysis in Theorem 3.5 of previous work [2]\n\n\\\n[1] Towards Understanding Asynchronous Advantage Actor-critic: Convergence and Linear Speedup. H. Shen, K. Zhang, M. Hong, T. Chen.  IEEE Transactions on Signal Processing, 2023.\n\n[2] Finite-Time Analysis of Single-Timescale Actor-Critic. X. Chen, L. Zhao. NeurIPS, 2023.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "All theoretical claims are sound and are presented with well written proofs.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "While the problem being considered is interesting, I believe the analysis techniques used and the resultant theoretical claims are a combination of methods used in prior literature. See section on Claims and Evidence for further details.", "essential_references_not_discussed": "While Shen et al. 2023 has been discussed in the Introduction, I believe it should also be added to Table 1.", "other_strengths_and_weaknesses": "- Continuous state action spaces are an important problem to consider\n- The paper is well written and easy to follow with appropriate background material presented and proofs well organized", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Please correct me if I am mistaken in my understanding of the contributions of the paper.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}]

Author rebuttal:

Meta-review: This paper presents a finite-time convergence analysis for single-timescale actor-critic algorithms with Markovian sampling in continuous state and action spaces. The analysis leverages a Lyapunov-based framework to jointly analyze the actor and critic updates, enabling a less conservative and more unified treatment of their dynamics.

All reviewers agree on the correctness of the theoretical claims and acknowledge the significance of the problem setting. The authors did a good job clearly situating their analysis in the rebuttal session and resolved most of the reviews' concerns. I would encourage the authors to incorporate the proposed revisions in their camera-ready version
Decision: Accept (poster)