Finite-Time Analysis of Single-Timescale Actor-Critic
Authors: Xuyang Chen
Lin Zhao
Venue: NeurIPS 2023 poster (2023)
Keywords: Finite-time analysis
single-timescale actor-critic
TL;DR: This paper provides a finite-time analysis for the single-timescale actor-critic

Abstract: Actor-critic methods have achieved significant success in many challenging applications. However, its finite-time convergence is still poorly understood in the most practical single-timescale form. Existing works on analyzing single-timescale actor-critic have been limited to i.i.d. sampling or tabular setting for simplicity. We investigate the more practical online single-timescale actor-critic algorithm on continuous state space, where the critic assumes linear function approximation and updates with a single Markovian sample per actor step.  Previous analysis has been unable to establish the convergence for such a challenging scenario. We demonstrate that the online single-timescale actor-critic method provably finds an $\epsilon$-approximate stationary point with $\widetilde{\mathcal{O}}(\epsilon^{-2})$ sample complexity under standard assumptions, which can be further improved to $\mathcal{O}(\epsilon^{-2})$ under the i.i.d. sampling. Our novel framework systematically evaluates and controls the error propagation between the actor and critic. It offers a promising approach for analyzing other single-timescale reinforcement learning algorithms as well.

Finite-Time Analysis of Single-Timesee Actor-Critic
Xuyang Chen National University Singapore chenxuyang@u. . edu
Lin Zhao"
National University of Singapore elezhl @nus. .du...edd.... sg
Abstract
Actor-critic methods have achieved significant success in many challenging ap- plications. However, its finite-time convergence is still poorly understood in the most practical single-timescale form. Existing works on analyzing single-timescale actor-critic have been limited to i.i.d. sampling or tabular setting for simplicity. actor-critic algorithm on
We investigate the more practical online dingle-timeseee continuous state space, where the critic assumes linear function approximation and updates with single Markovian sample per actor step. Previous analysis has been unable to establish the convergence for such challenging scenario. We demonstrate that the online single-timescale actor-critic method provably finds an e-approximate stationary point with Ō(e-? sample complexity under standard assumptions, which can be further improved to O under the i.id. sampling. Our novel framework systematically evaluates and controls the error propagation between the actor and critic. It offers a promising approach for analyzing other single-timescale reinforcement learning algorithms as well.
1 Introduction
Actor-critic (AC) methods have achieved great success in solving many challenging reinforcement learning (RL) problems [17 20 24]. AC updates the actor (i.c., the policy) using the estimated policy gradient (PG), which is function of the Q-value under the policy. Meanwhile, it employs
a bootstrapping critic to estimate the Q-value, which often helps reduce variance and accelerates convergence in practice.
27 Despite the empirical success, the non-asymptotic convergence analysis of AC the most practical figle-timescale form remains underexplored. A large body of existing works consider the double- loop variants, where the critic runs many steps to accurately estimate the Q-value for given actor This leads to decoupled convergence analysis of the critic and the actor, which involves a policy evaluation sub-problem the inner loop and a perturbed gradient descent in the outer loop. Its finite-time time convergence is relatively well understood [16] 37 35). Nevertheless, the double-loop setting is mainly for case of analysis, which is barely adopted in practice. Since requires accurate critic estimation, it is typically sample inefficient. In fact, it is unclear whether an inner loop of accurate policy evaluation is really necessary since only corresponds to one transient policy among many iterations.
37
16
where the actor and the critic are updated simultaneously in each iteration with stepsizes of different timescales. The actor stepsize is typically smaller than that the critic, with their ratio converging to zero as the iteration number goes to infinity. Hence, the actor is updated much slower than the critic. The two-timescale allows the critic to approximate the desired Q-value an asymptotic way, which enables a decoupled convergence analysis of the actor and the critic. This variant is occasionally
Another body of works considers the (single-loop) two-timescale variants BI
36
"Corresponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: Comparison with related single-timeseale actor-critic algorithms
Setting
Sampling
Reference
Sample Complexity
State Space
Reward
Actor
Critic
[21
Finite
Discounted
i..d.
i..d.
O
8
Infinite
Discounted
i..d.
i..d.
OlE
This Paper
Infinite
Average
Markovian
Markovian
O(e
adopted to improve learning stability. However, it is still considered inefficient as the actor update is artificially slowed down.
In this paper, we consider the more practical single-timescale AC algorithm, which is the one introduced in many works of literature as well as in [25] as a classic AC algorithm. In single- timescale AC, the stepsizes of the critic and the actor diminish at the same timescale. Unlike the aforementioned variants, which have specialized designs aimed at simplifying the convergence analysis, the analysis of the single-timese errors in critic estimation and the close coupling between the parallel critic update and actor update, the algorithm is more prone to unstable error propagation. remains unclear under what condition consider the challenging undiscounted time-average reward formulation [25] 31 37), which consists of three parallel updates: the (time-average) reward estimator, the critic estimator, and the actor estimator. We keep track of the reward estimation error, the critic error, and the policy gradient norm (which measures the actor error) by deriving an implicit bound for each of them. They are then analyzed altogether as an interconnected system inspired by [2]] to establish the convergence simultaneously. Specifically, we identify the (constant) ratio between the actor stepsize and the critic stepsize. below which all three errors will diminish to zero, despite the inaccurate estimation in all three updates (reward estimation, critic, actor).
AC presents a greater challenge. Due to the substantial
the errors will converge zero. To study its finite-time time convergence,
1.1 Main Contributions
We summarise our main contributions as follows:
We provide finite-time analysis for the single-timescale AC under the Markovian sampling and prove (c)-2) sample complexity, where O(-) hides additional logarithmic terms. We further show that this sample complexity can be improved to (c-²²) under i.i.d. sampling, which matches the state-of-the art performance of SGD general non-convex optimization problems. Our proof clearly shows that the additional logarithmic term under the Markovian sampling is introduced by the mixing time of the underlying Markov chain.
Our result compares favorably to existing works on single-timescale AC. To our knowledge, the only other results of migle-timescale AC in the general MDP (Markov decision process) case from (8] and (21), both of which obtain a sample complexity of O(E=²) under discounted reward setting. However, both [8] and [2I] considered the i.i.d. sampling, where the transition tuples are independently sampled from stationary distribution and discounted state-action visitation distribution. In this paper, consider the more practical Markovian sampling, where the transition tuples generated from single trajectory (see Table
Furthermore, [ follows explicit Lyapunov analysis, where they leave biased term in the critic and eliminated in the actor. Therefore, their proof framework cannot show the convergence of the critic. We instead give neat proof framework to guarantee convergence for both the critic and the actor. Additionally, [2T] only considered the tabular case (finite state-action space) where we allow the state space be infinite (see Table D. It is worth emphasizing that moving from a finite state space to an infinite state space takes sigmificantly non-trivial effort in analysis. The analysis in 21 concatenates all state-action pairs to create finite-dimes mnite-dimensional feature matrix, which however becomes impossible in the infinite state space scenario. Consequently, their analysis technique and established results not applicable in our context.
Technically, we develop a new analysis framework that can establish the finite-time convergence for single-timescale AC under the general setting. The existing analysis for double-loop AC [37 and two-timescale AC BI hinge on decoupling the analysis of actor and critic, which typically establishes We instead investigate the evolution of
the convergence of critic first and then actor 37 31
8).

---

the coupled estimation errors of the time-average reward, the critic, and the policy gradient norm altogether as an interconnected system in a much less conservative way. We emphasize that our analysis framework includes the discounted setting as a simple special case where the interconnected system is only wooddimensional without the time-average reward estimation.
1.2 Related Work
Policy gradient methods. Policy gradient methods 226
25
learn parameterized policy, constituting
a departure from the value-based approach 28
32
40
The asymptotic convergence of policy via stochastic approximation methods
gradient methods has been well established in 29
26
[6] Some recent works have shown that PG methods can find the glohal optimum of some particular class of problems, such LQR II [9] and tabular case problem [ Under general function approximation setting, finite-time convergence Specifically, [T] established the finite-time convergence of PG methods under both tabular policy parameterizations and general parametric policy classes. [38] showed that a variant of PG methods
PG methods was analyzed in [ 38 33 34].
can attain an e-accurate stationary point at sample complexity of ((c 2), where they adopted
Monte-Carlo sampling to find an unbiased estimation of policy gradient. 33 34] studied the variance reduction PG and acceleration PG.
Actor-Critic methods. The AC algorithm was initially proposed by [5] Later, extended it to the natural AC algorithm. The asymptotic convergence of AC algorithms has been well established in [4 5 7 39] under various settings. Many recent works focused on the finite-time convergence of AC methods. Under the double- loop setting, [37] established the global convergence of AC methods for solving linear quadratic regulator (LQR). (27] studied the global convergence of AC methods with both the actor and the critic parameterized by neural networks. [16] studied the finite-time local convergence of few AC variants with linear function approximation.
Under the two- tio-timescale AC setting, 31 established the finite-timm local convergence to stationary point at sample complexity of (Ee-2.5) under the undiscounted time-average reward setting, 36 studied both local convergence and global convergence for two-timescale (natural) AC, with Ō and (e-=)) sample complexity, respectively, under the discounted accumulated reward. The algorithm collects multiple samples to update the critic. [13) proposed two-timescale stochastic approximation algorithm for bilevel optimization and the algorithm was subsequently employed in the context of two-timescale AC. [9] established the global convergence of two-timescale AC methods for solving LQR, where only a single sample is used to update the critic in each iteration.
Under the timesslle setting, [12 considered the least-squares temporal difference (LSTD) update for the critic and obtained the optimal policy within the energy- based policy class for both linear function approximation and nonlinear function approximation using neural networks. [4] studied single-timescale AC on LQR. In addition, S and [21) considered the single-timescale AC in general MDP cases, which have been reviewed and compared in Section T.1
Notation. We use non-bold letters to denote scalars and use lower and upper case bold letters to denote vectors and matrices respectively. Without further specification, exists an absolute positive constant C' such that xn, I C'y.. for two sequences {.n} and {.... We use (-) to hide logarithm factors. The total variation distance of two probability measure and u is defined by dry (1,, v) := 1/2 Sx (m(dx) v(dx)). In addition, we IP to denote generic probability of some random event.
write I,, O if there
2 Preliminaries
In this section, we review the basics of the Markov decision process, policy gradient algorithm, and single-timescale AC with linear function approximation.
2.1 Markov decision process
We consider the standard Markov Decision Process (MDP) characterized by (S, A, P.r,, where the state space and A is the action space. We consider a finite action space |A| < xo, whereas the state
space can be either finite set or an (unbounded) real vector space S C Ra. P(s (8t4 ax) E (0, 1] denotes the transition kernel. We consider bounded reward r : S x A [-Up, Up], which is
3

---

function of the state s and action A policy Te(-|s) E RIAI parameterized by is defined as mapping from given state probability distribution over actions.
The RI. problem of consideration aims to find a policy To that maximizes the infinitehhorizon which is given by
time-average reward 26 25
37
31]
r(st, at)
J(0) =- lim
Eg
E pap-aa
(r(s,a)),
T-000
T
where the expectation Egg is over the Markov chain under the policy To. and hs denotes the stationary state distribution induced by те. The existence of the stationary distribution can be guaranteed by the uniform ergodicity of the underlying MDP, which is a common assumption. Hereafter, we refer to (0) as the time-average reward (or exchangeably, performance function), which can be evaluated by the expected reward over the stationary distribution μe and the policy To.
The state-value function is used to evaluate the overall rewards starting from a state and following policy Te thereafter, which is defined as
(s(s) = Eol Σ
s],
where the action follows the policy at ~ (-(()) and the next state comes from the transition kernel $141 St, at). Similarly, we define the aation-valuee (Q-value) function to evaluate the overall rewards starting from s, taking action a, and following policy Va thereafter:
Qo(s, = Eg Σ (r(st, a.) _[())) s. a)
1=0
@ r(s, ((0) + (VVo
where the expectation in (i) taken over ss ~ P())s.a).
2.2 Policy gradient theorem
The policy gradient theorem [26] provides an analytic expression for the gradient of the performance function (0) with respect to the policy parameter which given by:
Vo)(O) Eerpue (eo a Ve log (e((s))]
(I)
Evaluating this gradient requires the Q-value corresponding to the current policy Ty. The REIN- FORCE 22 is Monte Carlo-based episodic algorithm, which uses all the rewards collected along the sample trajectory (that is, the differential return) as an approximation to the true Q-value.
Note that for any function b S + R that is independent of the action, we have
Σ M8) V = V(8)V( a
To(a)s)) = b(x = 0.
aEA
Therefore, the policy gradient theorem can be written equivalently as:
V = Esrpug -a- [[Qo(s, (s, a) - b(s)) (a]s)]
where b(s) is called the baseline function. A popular choice of baseline the state-value function, which leads to the following advantage-based policy gradient
V ( = Ex-ro..rro A (s, a) Ve log (cls),
where Ag = Qo (o(s) is known as the advantage function. This is the "REINFORCE with baseline" [29]. The baseline function help reduce variance. However, like all Monte Carlo-based methods, it can still suffer from high variance and thus learns slowly. addition, is inconvenient to implement the algorithm online for continuing tasks (25).
AC algorithm instead employs bootstrapping critic to estimate the Q-value, We describe the classic single-time timesclieeccce AC in the next subsection.

---

2.3 The single-timescale actor-critic algorithm
We consider the classic sangle single-timeseale AC method, where the critic is bootstrapping and uses single sampled reward to update in each iteration. This directly accommodates online learning for continuing tasks. We consider the following linear function approximation of the state-value function:
Vo(s: w) (
where ( S - Rd is known feature mapping, which satisfies ||((()) S 1. To drive Vo(s; w) to- wards its true value (s),, the semi-gradient TD(O) update applied to estimate the linear coefficient (hereafter referred to the critic);
W++1 W. + B.((r2 ((0) + (0(+41))
"
(2)
where 9g the step size of the critic w and rı == r(st, at). Since J(0) is unknown, the time-average reward setting introduces additional estimator 77 to estimate it. Hereafter, we simply refer to 7) the reward estimator. The temporal difference error can be defined as
6, =
+ Φ(5++1) w. - x(s.) wr.
Then, the update rule for the critic is given by
1++ 1} (r 11:),
W1+1 = we + (())
where 7/ is the step size the reward estimator 7h-
Since 6, is approximation of the advantage function, similar to REINFORCE with baseline, the corresponding update rule for the actor can be written as:
0++1 0. + ag9; Ve log Te. (aelss),
where a, is the actor stepsize. The above-descrine AC is summarized in Algorithm [ which is introduced in [25] classic online one-step AC algorithm. Algorithm can be efficiently implemented for continuing tasks due to online nature.
Algorithm 1 Single-timescale Actor-Critic
1: Input initial actor parameter Og. initial critic parameter wo, initial reward estimator NJo stepsize ax for actor, 3 for critic, and "/ for reward estimator.
2: Draw so from some initial distribution
3: for t. = 0, 1,
do
4: Take action 0g ~ ne. (-1ss)
5: Observe next state 8++1 P(-|st, az) and reward r(s), 0t)
6:
& rı Tt + (0(++1)) [ (bs{)) Tw.
7:
M++1 = Nt + (r - n7))
8: WI+1 = II (wi + Bidr(((s))
9: 0.+1 = O, + acd; V log ne. (ac(st)
10: end for
Note that the "single-timescabe refers to the fact that the stepsizes at, Se, it are only constantly proportional to each other. In addition, this is a "single-sample" algorithm, since only one sample is needed for the update each iteration. double loop variants. In Line 8 of Algorithm [ projection (Il,,,) is introduced to keep the critic
remark that Algorithm iis more common in practice than
corm-bounded by Uw. which is widely adopted in the literature [3] 37 36 g that the projection can be handled casily, which is relaxed using its non-expansive property in analysis.
for analysis. Note
Main Results
We first present several standard assumptions that are common in the literature of analyzing AC with linear function approximation [12 Insights into these conditions and connections with relevant works are also discussed.
5

---

3.1 Assumptions
By taking the expectation of w141 given w/
with respect to the stationary distribution, we have for any
Bo(wr+ilus wi Be + Aowr),
where
Ag E (o)))) ((s)))
(4)
bg (ooo))((((s {()))
and s (=(()) a s=((-s), s' ~ P(-|s, a) is the subsequent state of the (s, It can be easily shown that [25] the TD limiting point (0) satisfies:
bg Agw (0)
Note that Ag reflects the exploration of the policy. To see this, note that without sufficient exploration, Ag can be rank deficient and (6) be unsolvable. Consequently, the critic update (2) will not converge. Hence, the following assumption is made to guarantee the problem's 's solvability.
Assumption 3.1 (Exploration). For any 0, the matrix Ag defined in 44) negative definite and its maximum eigenvalue can be upper bounded by -X.
Assumption 3.1 42
commonly adopted in analyzing TD learning with linear function approximation 21. In particular, Assumption 3.1 holds if the policy me can explore all state-action
31
23
pairs the tabular case
26% so that all [2T In addition, with this assumption, we can choose Uw = A
w" lie within the projection radius Us because |bba| < 2U, and || s X- which justifies the projection operator introduced in Line 8 of Algorithm [
Assumption& 3.2 (Uniform ergodicity). For any 0, denote ( (-) as the stationary distribution induced by the policy =o(-1s (-Is) and the transition probability measure ((.|s, a). For a Markov chain generated by the policy and transition kernel P, there exists > 0 and p (0, 1) such that
drv((P( E -|so s), (-))) mp" VT 2 0, Vs E S.
Assumption 3.2 assumes the Markov chain is geometrically mixing, which can be implied by the uniform ergodicity. It commonly employed to characterize the noise induced by Markovian sampling in RL algorithmss
4 31 21).
Assumption 3.3 (Lipschitz continuity of policy). Let (als) be a policy parameterized by E R2. There exists positive constants B, L and L,, such that for any 0, 0,, O2 E Rdd 8 S, and A, holds that:
(a) |V ( B
(b) V log ne, (als) V Voog To, (a]s)] - [i 021
(c) Te, (a Te, To, (a|s) L 01
021
Assumption B.3 is standard the literature of policy gradient methods [2 42 38
34 B1
This assumption holds for many policy classes such as Gaussian policy [10,, Boltzmann policy 15) and tabular softmax policy [I.
Assumption 3.4. For any 0, 0' E Rdd there exists constant L, such that || V Vue < L 0 0'1|, where (s) is the stationary distribution under the policy xg.
Assumption 3.4 is introduced in g to show the smoothness of the optimal critic w (0), which is critical to guarantee the convergence of aigle-timescale AC. This assumption holds for the finite state-action space setting [18]
3.2 Finite-Time Analysis
We define the following uniform upper bound for the linear function approximation error of the critie:
Cppp == sup Eanypo Tw vo(s))
9

---

The eπrоr Capp is zero if Ve is indeed a linear function for any 0. Naturally, it can be expected that the learning errors of Algorithm I depend on Capp'
We define the following integer Ty that will be useful in the statement of the theorems, which depends on the number of total iterations T:
= min 2 0 mp v T
where m, are constants defined in Assumption 3.2 Therefore, we choose TT log mp log log p-1 = Ollog T) such that mp"r-1 & vT The integer Ty represents the mixing time of an ergodic Markov chain, which will be used to control the Markovian noise in the analysis.
p-
We quantify the learning errors by defining y/ 1)s J(,),, which is the difference between the reward estimator and the true time-average reward J(O,) at time t. For the critic, we define,
2, == w, W with W (0,) measure the error between the critic and its target value iteration t. The following two theorems summarize our main results.
Theorem 3.5 (Markovian sampling). Consider Algorithm 7 with or = v B
VT VT.
y + where e constant depending on problem parameters. Suppose Assumptions 3.1 3.4 hold, we have for 2 2Tr,
T
log T VT
Byt
0
+ (Capp):
TT
TT
T-1
E1 = 00 log² T
+ (tapp),
T TT b=rr
VT
T-1
log T VT
E []
+ ((app))
TT EETT
We defer the interpretation of the above results bit and present below the analysis results under the i..dd sampling first for better comparison. The major difference of i.i.d. from Markovian sampling that at the t-th iteration, the state 8; is sampled from the stationary distribution μ4a instead of the evolving Markov chain (see Algorithm 2 in Appendix E The i.i.d, sampling simplifies the analysis in the way that many Markovian noise terms reduce to zero effectively. This leads to a tighter sample complexity bound compared to the Markovian sampling by up to logarithmic factors.
Theorem 3.6 (i.idd sampling). Consider Algorithm (see Appendix D with a = a c 3 =
VT: %t 7 F where constant depending on problem parameters. Suppose Assumptions 3.7 3.4 hold, we have for T 2 2TT,
T-1
Σ
Ey² O ( + (capp))
T
VT
t=TT
1
E||2 0(
+ (CEpp),
TT
VT
t=TT
T-1 T
(0))) 0 VT
+ (capp).
If the critic approximation error capp is zero, we see that the reward estimator, the critic, and the actor estimation errors all diminish at a sub-linear rate of Ö The additional logarithmic term hidden by Ō--) is incurred by the mixing time of the Markov chain, which can be get rid of under the i..dd sampling. also hides the polynomials of other problem parameters. They are explicitly characterized in the proofs up the last step of analyzing the overall interconnected emror propagation system. One can easily keep and get the dependence orders of all parameters if needed. Here we focus on the dependence of the iteration number for case of presentation.
7

---

To put the results into perspective, note that 0 is the rate one would obtain from stochastic gradient descent (SGD) on general non-convex functions with unbiased gradient updates. In terms of sample complexity, to obtain an e-approximate stationary point, takes a number Ö samples
for Markovian sampling (Algorithm 1) and 3) for i.id. sampling (Algorithm ( which matches
the state-of-the that performance of SGD on non-convex optimization problems.
The obtained sample complexities are superior to those of other AC variants. Notably, 16 provided finite-time convergence for double-loop variant with a O sample complexity and analysed
two-timescale variant, yielding a (c sample complexity. The sample complexity gap is intrinsic to their inefficient usage of data. In the double-loop setting, the critic starts over to estimate the Q- value for an intermediate policy in the inner loop, ignoring the fact that the consecutive Q-values can be similar given relatively minor policy update. The two-timescale setting artificially slows down the actor update by adopting an actor stepsize that decays faster than the critic. The single-timescale approach updates the critic and actor parallelly with proportional stepsizes and thus learns more efficiently.
Moreover, our result matches the O sample complexity of policy gradient methods such as REINFORCE 22) under the i.i.d sampling. It is previously found in [3 that there is a sample complexity gap between Algorithm [ adopting two-timescale stepsizes and variance-reduced REINFORCE [22]. In this paper, we close this gap by providing a single-timescale analysis for Algorithm which shows that this practical tingle-timescale AC can have the same sample complexity as REINFORCE.
3.3 Proof Sketch
The main challenge in the finite-time analysis lies in that the estimation errors of the time-average reward, the critic, and the policy gradient are strongly coupled. To overcome this difficulty, we view the propagation of these errors as an interconnected system and analyze them holistically. To better appreciate the advantage of our analysis framework over the decoupled methods that are traditionally adopted in analyzing double-loop and two-timescale variants, we sketch the main proof steps of Theorem 3.5 in the following. We also highlight the key challenges and techniques developed correspondingly. All supporting lemmas mentioned below can be found in Appendix.
We first derive implicit (coupled) upper bounds for the reward estimation error yr, the critic error z;. and the policy gradient V (O,),, respectively. Then, we solve system of inequalities to establish finite-time convergence.
Step 1: Reward estimation error analysis. Using the reward estimator update rule (Line 7 of Algorithm D we decompose the reward estimation error into:
v2+1 = (1 - 2%)),² + (r - -(()))
+ (J(O.) - ((0++))) + (J(0,) - J(0++1) + 7u(1= - =
The second term on the right-hand side of (7) is bias term caused by the Markovian sample, which is characterized in CC. As shown in Lemma[F.] [. this bias reduces to O under i.i.d. sampling after taking the expectation. The third term captures the variation of the moving targets J (0.). The doublc-loop variant of AC runs policy evaluation sub-problem in the inner loop for each target (O.) to estimate the policy gradient accurately. This easily ensures the monotonic decreasing of ((,)) and consequently the convergence. The two-timescale variant utilizes the additional property of lim,-roc /r/3t
annihilate this term and consequently can have a decoupled analysis. In the case of tigle-timesccle AC, we do not have the aforementioned special algorithm designs and properties to ease the analysis. Instead, we utilize the smoothness of .()) (see Lemma B.2 and derive an implicit upper bound for this term as function of the norm of ye and ((,).. This bound will be combined with the implicit bounds derived Step 2 and Step 3 below to establish the non-asymptotic convergence altogether. The last term in 7 reflects the variance in reward estimation, which is bounded by O(%)).
Step 2: Critic error analysis. Using the critic update rule (Line 8 of Algorithm I. we decompose the squared error by (we neglect the projection for the time being for the ease of comprehension. The complete analysis can be found in the appendix.)
| 112 =1| 112 + 2,((2., g(w,, 0.)) + 23, (O,, Wi: 0.) 22, Ag(O., ne: 0.)) + 2(z,, w/ - wHt1) + (g,:,g(O,,, wi, 0.) + Ag(O Te, 0.)) + w - -w
(8)
8

---

where O, := (st, dg. St+1) is tuple of observations and the definitions of g. 9, Ag, and y can be found in [2) and (13) in Appendix A Without diving into the detailed definitions, here we focus on illustrating the high-level insights of our proof. First of all. the second term on the right-hand side of (8) can be bounded by || under Assumption 3.1 provides an explicit characterization
of how sufficient exploration can help the convergence of learning. The third term is Markovian noise, which is further bounded implicitly in Lemma C.3 For the i.i.d sampling case, as shown in Lemma E. I this bias reduces to 0 after taking the expectation. The fourth term is caused by inaccurate reward and critic estimations, which can be bounded by the norm of Y/ and 2.. The fifth term tracks both the critic estimation performance 2, and the difference between the drifting critic targets w. Similar to the case of Step I, the double-loop approach bounds this term relying on the accurate policy evaluation sub -ebbbroolemm in the inner loop for each target wf. whereas the two-timescale approach ensures its convergence by additionally requiring lim / = 0. In contrast, we establish an implicit upper bound for this term function of y/2 and 2, by utilizing the smoothness of the optimal critic proved in Lemma B.4 Finally, the last term reflects the variances of various estimations, which is bounded by (()))
Step 3: Policy gradient norm analysis. Using the actor update rule (Line of Algorithm D and the smoothness property of J() (see Lemma B.2 we derive
1 |[,)( - (J(0.+1) - J(0)) O(O,, 0.) - (VJJ(,,), (.((O))A((O.. ne, we, 0.))
ax
(9)
(o; 0,)1) + LJ'
2 ag V log ne, (a, (a.1s))1?:
where O is a shorthand for an independent sample from stationary distribution s ~ μe., a ~ To. s' a)) θ is defined in (33) and L, is a constant. The first term on the right-hand side of ( compares the actor's performances between consecutive updates, which can be bounded via Abel summation by parts. The second term is noise term introduced by Markovian sampling, which is characterized in Lemma|C.o Again, as proven in Lemma E. this bias reduces to under i..d. sampling after taking the expectation. The third term is error introduced by the inaccurate estimations of both the time-average reward and the critic. This term was directly bounded to zero under both the double-loop setting and the two-timescale setting due to their particular algorithm design, to enable a decoupled analysis. We control this term by providing an implicit bound depending on yt, 2t. and ((.).. The fourth term comes from the linear function approximation error. The last term captures the variance of the stochastic gradient update, which is bounded by O(az).
Step 4: Interconnected iteration system analysis. Taking the expectation of and summing
and (9) from Ty to T - 1, respectively, we obtain the following system of inequalities in terms of Yr, Zr, Gr:
log 2 T VT
Yr
Eyt S O
L YrGT,
TT
tm Fr
1
T
log² 2 T
ZT
E Zt 12 < 00
(Eapp) + l2 -o 8ZT),
T TT
VT
t=
| < 0 log 2
T
GT := T
+ (Eepp) + 4. Cr(
t=rr
where 11, 11,12,44 13,4, l4 are positive constants. By solving the above system of inequalities, we further prove that if
4 + 2 + (1 13)) S and 16/s S 1,
then Yr, Zr, GT converge at rate of O log" T VF ). This condition can be easily satisfied by choosing
the stepsize ratio c to be smaller than a threshold identified in Equation (28). Thus, it completes the proof.
The above proof applies to i.i.d sampling straightforwardly, with the corresponding terms pointed out in the above steps reducing to 0 in the analysis. The additional proof can be found in Lemma E.I

---

4 Conclusion and Discussion
In this paper, we establish the finite-time analysis for single-timeseal AC with Markovian sampling. Our work compares favorably to existing works in terms of analyzing online learning and considering the continuous state space. We developed a series of lemmas that characterize the propagation of errors, and establish their convergence simultaneously by solving system of nonlinear inequalities. The proposed framework is general and can be applied to analyze other single-timen timescale stochastic approximation algorithms. Our future work includes further considering the continuous action space problems and developing new proof techniques that require fewer assumptions.
Acknowledgements
This work was supported by the Singapore Ministry Education Tier Academic Research Funds (A0009030-00-00, 22-5460-A0001 The authors would like to thank the timely help from Yue Wu and Quanquan Gu for clarifying the proof of their seminar work on finite-time analysis of two-timescale actor-critic.
References
[1] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approxi- mation with policy gradient methods in markov decision processes. In Conference on Learning Theory, pages 64 66. PMLR, 2020.
[2] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98): 2021.
[3] Jonathan Baxter and Peter Bartlett. Infinite horizznn policy- grrdiiet estimation. Journal of Artificial Intelligence Research, 15:319-350, 2001.
[4] Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference on learning theory, pages 1691- 1692. PMLR, 2018.
[5] Shalabh Bhatnagar, Richard S Sutton, Mohammad Ghavamzadeh, and Mark Lee. Natural actor-critic algorithms. Automatica, 45(11):2471-244 2009.
[6] Vivek S Borkar. Stochastic approximation: a dynamical systems viewpoint, volume 48. Springer, 2009.
[7] Dotan Di Castro and Ron Meir. A convergent online single time scale actor critic algorithm. The Journal of Muchine Learning Research, 1 11:367-410, 2010.
[8] Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. Advances in Neural Information Processing Systems, 44::5294-225307 2021.
[9] Xuyang Chen, Jingliang Duan, Yingbin Liang, and Lin Zhao. Global convergence of two- timescale actor-critic for solving linear quadratic regulator. arXiv preprint 4487:42208.08744, 2022.
[10] Kenji Doya. Reinforcement learning in continuous time and space. Neural computation, 12(1):219-245, 2000.
[11] Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. International Conference on Machine Learning, pages 1467-1476. PMLR, 2018.
[12) Zuyue Fu, Zhuoran Yang, and Zhaoran Wang. Single-timescale actor-critic provably finds globally optimal policy, arXiv preprint 2xXi:20008004483 2020.
10

---

[13] Mingyi Hong, Hoi-To Wai, Zhaoran Wang. and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor- critic. SIAM Journal Optimization, 33(1): 2023.
[14] Sham M Kakade, natural policy gradient. Advances neural information processing systems, 14, 2001.
[15] Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999.
[16] Harshat Kumar, Alec Koppel, and Alejandro Ribeiro. On the sample complexity of actor- critic method for reinforcement learning with function approximation. arXiv preprint arXiv:1910.08412.200. 2019.
[17] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553):436 444, 2015.
[18] Qijun Luo and Xiao Li. Finite-time analysis of fully decentralized single-timescale actor-critic. arXiv preprint arXiv:2206.057.33, 2022.
[19] Dhruv Malik, Ashwin Pananjady, Kush Bhatia, Koulik Khamaru, Peter Bartlett, and Martin Wainwright. Derivative-free methods for policy optimization: Guarantees for linear quadratic systems. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2916-2925. PMLR, 2019.
[20] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforce- ment learning. In International conference on machine learning, pages 1928 1937. PMLR, 2016.
[21] Alex Olshevsky and Bahman Gharesifard. A small gain analysis of single timescale actor critic. SIAM Journal on Control and Optimization, 61()99880-1007 2023.
[22] Matteo Papini, Damiano Bimaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochastic variance-reduced policy gradient. In International conference on machine learning, pages 4026-4035. PMLR, 2018.
[23] Shuang Qiu, Zhuoran Yang, Jieping Ye, and Zhaoran Wang. On finite-time convergence of actor-critic algorithm. IEEE Journal on Selected Areas in Information Theory, 2(2):652-666 664, 2021.
[24] David Silver, Julian Schrittwieser, Karen Simonyan, loannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, al. Mastering the game of go without human knowledge. nature, 55007676):344-55,, 2017.
[25] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
(26) Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
[27] Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. arXiv preprint arXiv:1909.01 150, 2019.
[28] Christopher JCH Watkins and Peter Dayan. Q-learning- Machine learning, 8(3):279-292 1992.
[29] Ronald J Williams. Simple statistical grallinn- algorithms for connectionist reinforce- ment learning. Machine learning, 8(3):229-255 1992.
[30] Yue WI, Weitong Zhang, Pan Xu, and Quanquan Gu. finite time analysis of two time-scale actor critic methods. arXiv preprint arXiv:2005.0133 2020.

---

[31] Yue Frank Wu, Weitong Zhang, Pan Xu, and Quanquan Gu. A finite-time analysis of two time-scale actor-critic methods. Advances in Neural Information Processing Systems, 33:17617- 17628, 2020.
[32] Huaqing Xiong, Lin Zhao, Yingbin Liang, and Wei Zhang. Finite-time analysis for double q-learning. In Advances in Neural Information Processing Systems (NeurIPS), 2020 (spotlight), 2020.
[33] Pan Xu, Felicia Gao, and Quanquan Gu. Sample efficient policy gradient methods with recursive variance reduction. arXiv preprini 1909, 08610, 2019.
[34] Pan Xu, Felicia Gao, and Quanquan Gu. An improved convergence analysis of stochastic variance-reduced policy gradient. In Uncertainty in Artificial Intelligence, pages 541-551. PMLR, 2020.
[35] Tengyu Xu, Zhe Wang, and Yingbin Liang. Improving sample complexity bounds for (natural) actor-critic algorithms. Advances Neural Information Processing Systems, 33:4358 4369, 2020.
[36] Tengyu Xu, Zhe Wang, and Yingbin Liang. Non-asymptotis convergence analysis of two time-scale (natural) actor-critic algorithms. arXiv preprint arX1v:2005.03557, 2020.
[37] Zhuoran Yang, Yongxin Chen, Mingyi Hong, and Zhaoran Wang. Provably global convergence of actor-critic: A case for linear quadratic regulator with ergodic cost. Advances neural information processing systems, 32, 2019.
[38] Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Basar, Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimization. 58(6):38863612, 2020.
[39] Shangtong Zhang, Bo Liu, Hengshuai Yao, and Shimon Whiteson. Provably convergent two- timescale off-policy actor-critic with function approximation. International Conference on Machine Learning, pages 11204-11213. PMLR, 2020.
[40] Lin Zhao, Huaqing Xiong, and Yingbin Liang. Faster non-asymptotic convergence for double q q-learning. In Advances in Neural Information Processing Systems (NeurIPS), 2021, 2021.
[41] Mo Zhou and Jianfeng Lu. Single timescale actor-critic method to solve the linear quadratic regulator with convergence guarantees. Journal of Machine Learning Research, 24(222):1-34, 2023.
[42] Shaofeng Zou, Tengyu Xu, and Yinghin Liang. Finite-sample analysis for sarsa with linear function approximation. Advances in neural information processing systems, 32, 2019.
12

---

Table of Contents
Notation
13
Preliminary Lemmas
14
Proof of Main Theorem
14
C.I
Step I: Reward estimation error analysis
14
Step 2: Critic error analysis
17
Step Policy gradient norm analysis
4 Step 4: Interconnected iteration system analysis
23
Proof of Supporting Lemmas
25
IIII Sample Analysis
32
A
Notation
We make use of the following auxiliary Markov chain to deal with the Markovian noise.
Auxiliary Markov Chain:
P3
P
P. 8t---2
Oe--, ār 01-
P3 3t
Oe-r,
P, 8
8t-7 OT-T St-T+1
0t-741
(10)
For reference, we also show the original Markov chain.
Original Markov Chain:
Ot-T P. 81-
6 0e-r+1 ūr- P. 81-742 0 0
P.
0e
P
(11)
In the sequel, we denote by Ö, = (3e, Ce, 81+1) the tuple generated from the auxiliary Markov chain in (T) while O, = (st, dt, 86+1) denotes the tuple generated from the original Markov chain in (1I)
We define the following functions, which will benefit decompose the errors and simplify the presentation.
Ag(O, n, 0) [J(0) nl0(s),
g(0,w, w. 8) [r(s, a) - J(0) +
g(w.0) 0) = - + (o(s')
(12)
Ah(O, ((O,,,... n, 0) (J(0) - 7 + (0)0== (a)ss)
AN 0)
Vlgs)
h(0,0) = (r(s, (((s)))J((8)11 +(8)+ ((5))((s())))))) (())))) (ss)
(0)) (als).
We also define the following functions, which characterize the Markovian noise.
40O, 0) = (1) - (()
(()),
(O,w,, 0) (w - w/. 90, w. 0) g(w,
(13)
(00,0', 0) (VJ(0), (M 0)) h(O,0)),
E(0,w, w,0,w,0. 0) = (w - wg. (Wwj) (Eo (h(O', 0)] h(,,0))
where O' is shorthand for an independent sample from stationary distribution po, a To.
P. Define Us = 2U, + 2V,, so that we have | S Us. where d, comes from Line 6 Algorithm
Note that from Assumption 3.3 we have 18V log me || I G = U,B.
13

---

B Preliminary Lemmas
Lemma B.1 (311, Lemma C.4). For any 01, 02. we have
J(0:) J(02) - Lu|101 0211: where L, A + [logp m + -
Lemma B.2 (388). Lemma 3.2). For the performance function J J(). there exists a constant Ly >
such that for all 0,, 02 IRd it holds that
[VJ((,)) VJ((2)) 1 L, ||0 0211,
(14)
which further implies
L | 02l1²; 2
((22) 2 ((01) + (VJ(O)), 02 -0))
(15)
L
(02) & J(,)) + (VJ(O,), 02 - 01) + 0 0211? Lemma B.3 (311, Proposition 4.4). There exists constant L. 0 such that
(16)
2
(|w) - . (02) - L. | - 0211. v01 02 E ERA
where I., (2X U, 3X 3 UU) (1 + [logp m '1 - Lemma B.4 [8] Proposition 8). For any 01, O2 E R2d we have
[0 (02)) L. 02l1:
where La a positive constant.
Lemma B.5 (42) 31). For any 0₁ and Oz, it holds that
dTv Mo.) < [A[[[og, m 11 1
)|00 0211.
)|10 021l. drv(ue, 2 no. Ho, 2 To,) 1 |A + [log, m
drv (no, @ ne, @ P. pa. Te, & P) < | + [lgp m
11
)100 021l-
(31 Lemma B.2). Given time indexes and T such that 2 > 0, consider the Lemma B.6
auxiliary Markov chain in (10. Conditioning on st-++1 and 01-7, we have
drv (P E P(5+1 E .) - drv (P(O,, )),(( E E),,, dFv E P( E )) = drv (P(s, 0r) E )),P((s,,, ā.) E E)),
(Pv(((((s, at) E.), ((G., a.) E )) drv drv E P(, e E 1 + |1BBI10 0z-rll].
C Proof of Main Theorem
C.1 Step 1: Reward estimation error analysis
In this subsection, we will establish an implicit bound for estimator.
Lemma C.1. From any 2 we have
E nc. 0.)] <
0.-TI + 2U, 1mc - 17-7
+ +2U21A|L= Σ
E100 0.-Tl + 40,
i=!-
Theorem C.2. Choose at -r = =
1 we have
VI"
log² 2
Yy < 0
) + cG/YyGr.
(17)
VT
14

---

Proof. From the update rule of reward estimator in Line 7 of Algorithm ! we have
M [(0++1) ?/t = -(00.) J(0++1) + +r 7))
Then we have
vi+1 = (yi + ((0,) - I(0+11) 1 71))2
S vi + -(0+,))(((0+))))) + 2 (Tr 17.)
+ + - - + - -11)²
-1122))0 + 2m. - 2y, (J(O.) J(0++1))
+ 2()(O.) (( +1 (7)
Taking expectation up to 8441 (the whole trajectory), rearranging and summing from Ty to 1, we have
Σ
Elvil v
Σ
Ely
vi
Elye(r-- - J(O)))
((++1))
27
I=rr
t=
t=
4
T
T
+
- J(0
1 - mm)
L=TT
I
For term 4, from Abel summation by parts, we have
T-1
Σ
1
sit1)
=
27
1=
T-1
1
Σ
V/1
VT
27
2
YT-
1=r241
2022
Yr-1
2U?
For term Ig. from Lemma
C.I
we have
Elyx(rr J(0.)) < L.y O + 2U, |1 1
2U Σ 0 0.--|1 + 4U,mpp"1 --1
i=(-
AUGL,GTTLL AU?T +
1)Ga + 4U,mpp
< (AU,L,GT + LL, + 1))a,- + 4U? + 4U?mp"
Choose Tr, we have
T-1
1
Σ Elya(r-- - J(O)))
< (AU,L,GTT + 2U | GTT 1))
Σ ai
T--1
T
+ +U,
Σ
7 40
Σ
VT
1=
4U - T- T
VT
15

---

For 13, if ye > 0. from 15 we have
(((((0)) ((0++1)) s yel LJ
|0 - -0+111 + (VJ(O,). 8, - 0
2
I LyU,1188 11 - -0++1l + 10/100 - - []
If yt S 0, from T6). we have
يب 110 - 0++1
vr()(O.) J(0++1)) S ve(
(VJ(O.), + 0(+1))
2
s 1r0,100 -0++1 112 + 10 - 0z+1 VJ
Overall, we get
13 7t
(O,)
BLLL - 0141 12 + +1 [==)
ElCLyUU,''a + clyl VJ.0.)II]
L=
SCLyU,0' T TT
T-1
T-1
+
cG(
Σ
)
+ Σ (=
E| (()))))
VT
1=1T
For term 4, we have
T-1 14 =
-[JJ(O))-
- ((
L3 12+1
7t
Σ L3
L=
= L 2- TT
VT
For term Js, we have
T
15 =
Br - ((0))) ((=)))
1=
<
Σ AU²
4U² T TT
vT
Therefore, get
T-1
Σ
Bbill < (4U,L,GTT + (1L
+ 4U + +2) o² G2 (L.r + L3)) T TT
VT
T-1
+ 2U2VT - cG( Σ
Eyf")
Σ
E [
t=
1=
16

---

Since rr (llog T), we have
/T-
S f for large T. Then we get
T-
T-1 T TT
$ (4U, + 20, L. ATT +
1
+ +4U? [T + 3) 2 C 123))
VT
T-1
T-1
cGI
Eyt
B ((,))
T
TI
1=/T
1=
=0(-)
log T
cG
1
Σ
Eyt
Σ
E
(O.)
T TT
T TT
t=Tr
t=
Thus we finish the proof.
C.2 Step Critic error analysis
In this subsection, will establish implicit upper bound for critic.
Lemma C.3. For any 2 r > O, we have
(Or, 0()] & C1 0: 0 + 60/ W: w: L1 + 1)ai + 203 mp
where C1 20 (1 + [log, m '1 + 111 + 2U8L + 2UgL.
Lemma C.4. Given the definition 5() W1, 0²), for any 1 2 > 0, we have
E|E(O,,, 0.) - C2| - - 2U; B wi wi-T|l
+ 2U3 B L. + 1) 4U3 Bmpp"
where C2 : 3BU A| [log, m 11 - + 3U? L1 + SUsBL..
Theorem C.5. Choose at = 31 = = - we have
Zr 00 log T + (Eapp) 2 VYrZr+ 2cBL.
/Zr + 8ZT).
(18)
Proof. From the update rule of critic in Line of Algorithm !
we have
||0+1 w/+1l
||ااا_ (w, + (s:)) wit1l
||L| (w. + (())) ll (wi+1)l
S || + (e5:((())) - witlll
||w, + Ae(g(Or,w,, 0.) Ag(O Me 0.)) wل-ll ||w w/ + Belg wi, 02) Ag(O,, me 0.)) + w wi+
Therefore, have
|| _|
1|, Be(g(O w., An 0.)) + : wi+1. 2
12, 22, g(0, 03) Ag(0)/ 0:))
+ 2(22,, wi wi [g 0,) + Ag m, 0.)) + w - witil1
= -12,,12 2 (2. g(,, 0,)) 28, (O, 0,) (,, Ag(O,, nr 0,))
+ +2(21, wi w + [0, w., 0,) + Ag 7, 0.)) + w w1
< || 12 28, 0,)) + 28, (O,, w., 0,) + 23, Ag(O,, nr. 0.))
+ 2(z,, : w/-1) + 3 + 2| 11
17

---

Note that we have
(#t. I(w, 0,))
(z,,((w,, 01) g(w; 01))
(1,(((((()) -((s) (wr (wi-w; [w)]((((ss)
z, (( ((8))
2, Azi
>||==|1?
where the first equality is due to the fact that g(wا; 0z) = 0 and the last inequality follows from Assumption 3.1
Taking expectation up to S1+1, we have
= 112 s + J(w, 0.))
+ +
WP, 0.) 23,
2,,, ne. O.))
+ +22(2z, w. wht1 + 20 0 + 2 wi+ 11?
s (1 - 18, 2/ (t,
< (1 - - wi+1l?
+
w u. 2|]] -
2B|
02) 28, At,Or,tt,0.)
+ +2B(2,, - +
+ (Vw,) (0++1 -0))
+ 2Z (Vw?) (0. 0.+1)) 33 2B w wi+1ll 1l
2 - 218)) 2, 2 + 23, O,,, w., 0.) + 28, 2, 111al + L |ca||| 0++1 0.12
+ 2a, - (V 6, V log To. (ar(s:) - 233 + +2L,E 0g 0 0,+111
$ (1 - 218, 2 + 23 (O,, w. 0,) 2 v Fyy 12
+ La
2 11 |100 - 0.1 4 El 0 - 0.13 2 +21,0220
+ +Z0,B(z1, - (Vw,) (a:ls::)))))
L2G² 0z
< <1 218, = 2 + 28,EV 0,) + 23, Eyg E |
E|
L. G 20, (Vw;) 8 V log Te, (acls:))
3U + (2L
$ (1- 18, 1 1| 23, (O,, Wi. 0.) + 23, Eyf 1
La Le G + 20, B(z (V 8e V log Te, (ocls)))
+ 23 + (2T +
(19)
2
where (1) follows from the Lyssmotthness of w in Lemma B.4 (2) uses L.G² at s A3, for large T,
For term E(z,, - (Vw)) 5, V log Ta, (arl (t)))))), we have
E(z,, - (Vw;)) T & V log To, (a+())))
= =E(z,, (Vw;)T T (- Me, wi, 01) - h(O,, 0,))
=-E(z1, (Vw;) Ah((O, ne, Wi, 0:))
+ E(z,, (Vw;) (Eo; (O, 0,)] h(OO, 0.) Eo; Ro, 0.)1))
E| w,, 0,)] - E(z,, (Vw7) Ah(O,, We: 0,)) - E(z,, (Vw;) (Vw?) (h(OO, 0,)))
(20)
Note that from Cauchy- inequalll and L. the Lipschitz constant of w in Lemma B.3 we have
E(Ee, (Vw)) Ah(O,, ne, wi, 0.) < BL, E 2kyy S1
(21)
18

---

Furthermore, it holds that
Eo. (o.l)V'(OO,0))) = Eorl(((((s))) ~- -V(()))))))))))))))))))))))))- - (0(s) ~- -
s Eo ((d(s')) " Vo(ss)) (0(s) ~ - Vo(s)))
S Eo (o())) = Vo(ss)) (6(6)) " Vo(s))
Eo ((0(s)) w" -Vo()))
= Cpp
Therefore, we have
(Ze, (Vw,) Eo ( (oh'' 0,)]) s U,L, E
S UgL. E (),
$ 2BBUsLoEap.
(22)
Substituting 21 and 22 into 20 yields
Biz,, (Vw?) T 8, log Te, (arlse)) < (E Wr, 0.)
(23)
+ BL. v B 2112 22 + 811121112.
Plugging 23
into
19 we have
2 < (1 A3. 1|2 2,, 01) + 20z FE( wi 0.)
+ 23, v Egi E + 2BL 2z 2 8E 21
(24)
L.g G + 4BUGauCcapp
+ 203 + (2L2 +
2
Rearranging and summing from Tr to T gives
B| 2
E 21 21 1) +2 Σ
EV wr, 0.) +.) Σ
We,
BE(Or,,,,,0))
T
+
Ryy
2 2cBL.
V E 2 12
2R
SE| 1
1=
T
Le G) an + 44CBUseap)
La
+
(2 + c(212 +
2
I=TT
In the sequel, will tackle 41, 12, Ia, 14, ls respectively. For term 1,, from Abel summation by parts, we have
T-1 1
h
=
EE 21
3
1=
Σ
1
112
1
El
112
E3
B
3--1
Br
+1
T-1
<U?(
Σ
1
+
31
B
Bar
1=
= =33TT
where the inequality is due to B||2, 1| < U3 and discard the last term.
19

---

For term 1g. from Lemma C.3 choose T
we have
EV (O,, We 0,) S C1 - 0--rl Grr + 1)a-
+ 2 6U/ w. Wi-tell
1-1
20 vT
1-1
S 11
Σ
Gay + , GTr(TT + 1) +
+ 6Ug
Σ
U&Bt
k=t-Ty
k=t-rr
20
s (CiGrr + U/ GTr(Tr 1))04-m7 +
+
GUB TI 9t-
VT
Then we get
2 Σ WV( 0.)
T=T
T-1
20
2 2 Σ
(Ci + U13 + 1))o, +
+ +U3 TT.
VT
T=rr
For term 13. from Lemma
C.4 choose T we have
E EE,,,,,,, 0,)1 02 o |1 + 2U wi-rl
BIA GT + 1)ar 4U3 Bmp--1
C2 k=t--
Σ
Gay + 2UBB Σ
Us3r
k=t-Tr
+ GTT + l)ar, Bmp'r=
403 B
(C2GTr + 20 G 1))o, 2U,
/T
Therefore, we have
= 2c
EE(O,, 0.)
T-1
4UBB
< 2c
Σ
(C2.Gr 2U3 BAIT + 1))o, + 203 Brr +
/T
For term I4 and Is, from Cauchy-Schward inequality, we have
1 2
Byf)
E 19)
t=
T-1
T-1 Σ
T-1 Σ
I5 < 2cBL,
Σ
E| 12
Ey² 8
13)
t=
1=
20

---

Overall, we get
Σ
E| 2 2(
Eyf)*
1
t=
1=
T-1
T-1
T-1
+ 2cBL.
E| (
Σ
Eyt
+8
8
E
E
1=
(CiGTT + GTl + 1))or + 20
+ UB3 +
Σ
vT rr
T=rr
T-1
4U3 B
+ 2c
1))a ([22GT + 203 Grrr ()) + 2U3 2 BT +
VT
1=TT
(20 + c2L2 1 4cBUgcapp)
+
Therefore, we have
(1)
T-1
ZT 2 T -
By.
11
TT 1=TT
T - 1=
2cBL.
E 2zl 11)
Byt + +8
E E| 2, 113)
T TT
TT
T TT 1=Ty
(=Ts
+ 1 2U3
4U3 vT
+ U CTT(T + 1))at+ +
+ 12U3
VT
ScLiB B
+ 2c(C2rr + 20 B A, (Tr + 1))a, + 4cU BT +
GT,
VT
L
+ +2U73. + c22L
+cBUUscap))
2
= 0 log 2
T-1
T-1
) + (Capp)
+
Eyg
E|| z4 113)
VT
1
T
T - TT
1=
t=
2cBL.
E zell ()) (2
Σ
Ry +8
T TT Σ 1 123)
T
TT
T TT
where (1) follows from 7r Olog 7) so that - 2 17 for large T. Therefore, we have
log TT ) (Capp) + x Vr A
2cBT.
Zr S 0(
VZr + +Zrr)
VT
which completes the proof.
C.3 Step 3: Policy gradient norm analysis
In this subsection, we will establish implicit upper bound for policy gradient norm.
Lemma C.6. For any t 2 r > O, it holds that
[i, 0.)1 Dir(T + 1)Ga + D2mp-11,
where D, maxx(U,BLr + 2U, Theorem C.7. We have
and D2 AUsBLs.
log2T VT
Gr S 0
+ O (CCpp)) + Gr +Zzr)
(25)
21

---

Proof. From the update rule of actor in Line 9 of Algorithm
and we have
15
J(0(+1) 2 J(0,) + (VJ(O,), 0++1 - 02) 2 110 -021l
= + (V.(0)). 6, log no, (aelse)) I. ažllo log ne, (aels:))l
-((,)) + + We 0.)) at (V), 0.)) L LL" V
=J(0,) [ Wi 01)) 0r O1) 2
+ +o.(V//000,E000((0000000 يا 01 60 V log म.. (ar [s)]]
=J(0.) ( Wi: 0z)) ar ( 0,) (()))1
L,
+ +.. (O) 0,)]]
2 16 (e
2
where the last equality is due to the fact
Bor [O 0) - AO' 0)] Ro [(r(s, (0) + Vo((') Voggs))logTo(( = VJ(O).
Rearranging the above inequality and taking expectation, we have
1 (E[J(0:+1) - J(e))) - - Ah(O,. wi 0.)) + E[O(O,, 0,)
B| < at
E.V 0.)1) + L V, To. To, (.
2
Note that from Cauchy-Schwartzz inequality, inequally, we have
E (V))( (O,, Tt. wr, 0.)) s B E VJ
2Fyy + 21
From Lemma C.6 and choosing Tr, we have
E[e(O,, - (T 1)
Σ
B 0 + D2mp=
k=1-77+1
1-1
< Di(Tr + 1)G
Σ
Ok + D2mp
k=t--
1
- GDi(TT + a)7 + D2
'T'
has been shown that
(V', Eo ((((((((())))))))))))))))(())))) w- Vo(5)) (o(s) -- Vog
s Bo ((b(s))))) w - Vo((s)) - (p(s) T w - Vo(s))) T S (6) w- Vo(s'))²++ (0(s) w - Vo(+))
Eo w Vo(s))
2
Therefore, we have
(VJ(O.), Eo (O)) - LJ |Eo (O,
< L LLVBEA Ia 0))
2BLL
where we use |[)] < Ly which comes from Lemma B.I Plugging the three terms yields
E| < [E[ - + B E (..
2Ey? + 21
1
+ L aaa
2Bpp + GDD + a) + D2
VT
22

---

Summing over t from Tr to T 1 gives
I (E[J(0(=)) B[J(O.)) +B Σ V
T-1
2Eyf
8E112111
at
T -
(GDi(Tr + 1)² + D2)
2BLJ Capp (T - TT).
VT
For term 4, from Abel summation by parts, we have
11
(B[](O(+1) BF)(O,))
1
1
[B]) (() arr
[[J(0T)]
0t-1
at
ar-1
T-1
1 Ur
)U, + arr
U, +
04-1
ar-1
+1
20,
01-1
20, VT.
Overall, we have
2,,
VT (GD 1)2 D2) - TT
E
[J <
2apL (T - TT)
c
VT
T-1
+
Σ
2Ey; + 81112111 E VJ
t=
<
20,
VT + (GD + +)² + +D)
TT
2BLL Cupp (T - TT)
VT
T
T-1
T-1
+ B
B B
Σ
Esi +
E| 112) Σ
t=
1=TT
I=
Therefore, we get
AU, GT GD, (TT + 11) + D2) + 2BLp + BV GT 82T)
1
VT
= =0 log² T
+ (Eapp) + Bv GT (2Y, + 8ZT),
VT
which concludes the proof.
C.4 Step 4: Interconnected iteration system analysis
In this subsection, we perform an interconnected iteration system analysis to prove Theorem 3.5
Proof of Theorem 3.5
23

---

Proof. Combining
17 18
and 25
we have
Yr 0 log 2 T
VT
log² T
+ (Capp) + 2r 2eBI.
Zr - O
Vzr + +Zr),
VT
A
log 2
T
Gr S 0
(<app) + By CVVTT(2Y + 877))
VT
Denote
4 == cGG
2 4 X
1 = 2cBL.
X
4 = B.
Then we have
2og2 T
Yr S O
1 SIIIVYYGE YIGT,
VT
log" 2 T
ZT $ 0
+ ((Eap)) + l2v 2o
log 2 T
GT < 0
VT
For Gr, get
log 2 T
1 ((Capp) + Gr + 12 42r),
Gr S 0
VT
2
log 2
Gr < 0
+ (Eapp) + 21 + 1Zr).
(26)
VT
For Zr, we have
2T < 0 log T
+ O (Eapp) + 7 Z BYT + 4122r + 1/ Yr.
1
2
If it satisfies 41s s 1. we further have
log T
Zr S 0
+ (Ccpp) + (21g + Yr)
(27)
TT
For Yr, we get
Yy
0
log 2 T
h
2 (Y Gr).
VT
2
Plugging
26 and
27 into the above inequality gives
log² 2 T
4 _/2 (Yr++ + +2221 +
Yr < 0
+ (Espp) +
VT
log 2
T
4
< <011
+ (Copp)
+ (Yr + + + +))))
1
+
/T
2
log 2 T
4
0
+ O
+
(1 + 21
+ 8 +2)Y
VT
24

---

Therefore, 1 213 812(212 - 13) _ 1, we have
Yr - 0 log T
+ (Eapp).
Overall, we require
1
41 $
4'
(1 + 2 + 8/ 4))
< 1.
According to the definition of [1, 12, 13, 4, we have
ScBL.
X
4'
8
2cBL.
cG + 22 +B2
Thus we choose
À 32BL, G( + X2 + 64B2) }
X²
c min(
(28)
which satisfies the above two inequalities. Therefore, we have
Yr = 00 log 2og2T T
+ ((app))
T
and consequently,
log 2 T
ZT 0
+ ((app))
VT
GT = 0 log
+ (Espp).
Thus conclude our proof.
D Proof of Supporting Lemmas
The following three lemmas only deal with the Markovian noise, which are originally proved in and updated in (30.. We include the proof with slight modifications for proving Theorem 3.5
Proof of Lemma
Proof. We will divide the proof of this lemma into four steps.
Step 1: show that for any 01, 02 77, O as,a,s'), s'), we have
(00,,, 17, 01) 40., n, 02) S 4U,L,|10 - 0211-
(29)
By the definition of (00, 7), 0) in (00, 01) (00,0,0.)
we have
(nn - ((0,)) - J(O))) - (n - ((-)((0)) (r J(02))
<
[(n (O:))(r J(0I)) (n J(01))(r J(02))
+ +1(7 - J(O:)) - ((0))) - (r
- -(0)))
< AU,)J(011) - J(02))
< |U,L, - 0211-
Step 2: show that for any 0, 71, 72, O, we have
| m. 0) ((O, 12, 0) < 2U. -72
(30)
By definition, we have
(0, m. 0) - $00, 0)1 = 1(m J(())(r - J(O)) (12 - J(0))(r J(O))
< 2U 1/l-
25

---

Step 3: show that for original tuple O, and the auxiliary tuple O,, conditioned on 81-7-1 and 0,-r. we have
Σ kmt-r
B 02- (31)
By definition, have
[[,(O;, Me- 0z-r)
Th-r, 0t-
-T(6,,
By definition total variation norm, we have
E|r(st, az) - r();, 2U, (P E -,, E (55-++1,00-1)) (32)
By Lemma B.6 get
drv (PPOr E 0e- E ,,, 0
= drv ( ((( āe) E E,|s)-++1, 0(-r))
S drv (TP(s E (1- IP(rr 18- -4, 0c-r)) 1,,1E 0--r|
<drv E
E 1s 0, 0.-r)) + 22"
1, -.-
Repeat the above argument from t to 7 1, we have
(P E 0e-r), P -10---ss--1111 1,,,,11,,,,,) 0l-+)) AA Σ
E Pe-rl (33)
k=l-T
Plugging 33 into 32 we have
( Mt
- -1-;; 20
Σ
E 0, 0--
k=t-r
Step 4: show that conditioned on 8t-r+1 and 02-7, we have
([ th 0t-r)] S 40?mp" Note that according to definition, we have
(34)
where O (s/_r: di 1 is the tuple generated by s/- de- ~
To.... 8 From the uniform ergodicity in Assumption (3. it shows that
drv (P 18 0.-r), Ho..) S mp-
Then we have
E( 0.-r) E[ n1 - $10 -1- 0.-7) E[( - (0, (r 0.) -
4U (P(ii//PPO.,,. 11
0 0r-r), 100, @ no. 8 P)
mpm
Combing
29
30
31
and
34
have
El n1 0,)
d (O,, Mh. 0,) (OO,, m/, , ((00 0.-7) - (OO,, mt- θ 0.->)
+ EE0
(0, 0, E (O,, 7u- 0,-7)
< 0, 0.- 20 7/ 7- 20 A Σ E 0
+ 4U?mp"
which concludes the proof.
26

---

Proof of Lemma C33
Proof. We will divide the proof of this lemma into four steps.
Step I: show that for any 0,, 02, w and tuple O = a,,,a, 8'), we have
|V w. 01) (O) S 0i 0211,
(35)
where C - 20 + flogp m 11 + T + 2U8 + 20gL.
By definition of (0, -. 0) in we have
(0, 01) - W., 02)1
(w (0,,(0,,.0)) - g(w, 01)) (w 90,,,, g(w, 02)
(w wi. 01) g(w, 01)) - (w (w-wij 90, - g(w, 02))
+ 1w w0 02) - g(w. 02)) -w-- 950, F(w. 02))1
For term I1 we have
1 1w (0,0 01) g(w, 01)) - (w - -i
w, 02) - g(w, 02))l
1(w- (0, 01) 9(0, w. 02)) + k( wi.g(w. 01) g(w. 02))
-1W - wi, (J)() - -((2)))) + +|W - - 01) glw, 02))
22 |0 021l + 2U~1g(w, 01) g(w, 02)l
S 22 01 021 + 2U_ 2U5drV (ue. @ no. @ P. @ me @ P)
1. 0211 + 2U (ne, @ _o, & P, M40 @ _o 0 P)
$ (2UgL) + 2U L. (1 + flogp m +
0 0211
where we use the fact that Us- 2U, + 20 and the last inequality comes from Lemma B.5 For term /2, from
inequality, we have
1 kw wf, (t,9(0,,u w, 02) g(w, 02)) (w w2. g(0, w. 02) - g(w, 02))
= (w w (0, w,0,,,n. 02) - g(w,O2))1
2 will
S 2UgL. 110 021
Combining the results from In and Iz, we get
(0,0w, 01) V0,,w, 1, 02) S 01 021l, where C = 203 + [log, m -1 + + + 2U I., + 2U I...
Step 2: show that for any 0, Wi, W2 and tuple O(s, a, 8'), we have
[0,, 0) V0 w2, 0) < GUs||w] -22l-
(36)
By definition, we have
VO(O, wi, 0) V/O w2 0)
(w)) w " ,( W/, 0) (( 0)) (w2 w² 9(0 0) g(w2, 0))
< <uw - w ,00 wi, 0) ((w), 0)) (w)) - : (00 w2, 0) g(w2 0))
[(w w², "000 W2, 0) g(w2, 0)) (w22 w", (0 w2 0) g( 0))
S 20 (g wi) - (0, w2)) - (g(w), 0) g(w2, 0))1 + 2U wi well
< 6Us Wi will
where the last inequality due to |lg(O, wi, 0) - g(0 w2 0) = [(((')) (bs)) (wi - w2)l S 2| 2||w1 W |1ō( 0) g(wr, 0) < 2 2| w2 ll. and 20 Us.
27

---

Step 3: show that for tuples O₂ = (st, agg st41) and Ö. = (5t. De, $1+1). Conditioning on st-r+1
and d.-r, we have
E
-, U0
Σ k=t-7
B|00, - 01- (37)
By the definition of total variation norm, we have
E (1) wr 01-7)
W wi 900 W 0 g Wt.r: 0z-r))
s dTV (P(O, E 11 0 P(O, E -18--7+1, 0.-r))
E 0.-
k=t--
LU 1))
where (I) follows from
33
Step show that conditioning on st-++1 and P.-
W1, 0,-)) s 2m
(38)
From the definition of (OO, w, 0), we have
Bl Wi-r,
0z-1==00
where O²,, is the tuple generated by 8/-, ~ M0, .s ,/ ~ Tee 1,86-141 P. From Assumption
we have
drv 0 mp--1
Then, it holds that
E V (O, Wi-r. 0,-,)
)-- (V() 0,-))
B(Wi-, 9 ( wi w; 0 ,0,,,,,0,,, 0,-r))
UU (P((, 1/8 -18
0 (--)) ), 1O,-, 0 no 8 P)
S 2U7drv (P(O; -ss 18 02 p0.. 2 To. & P) To.
2U3dTV (P((E,, T.) E 1,
2U (PP(3, 0 00.r)
< 203mp=*1
Combining 335
36
37
and (38). we have
E V (O,, Wt, 0.)]
(O,, 0.) 0.-])
+ (1,, - 10 10,,,, Wi- Q.-7)l
(O, w,r; 1 10,,, 0..
+ ( WT-,, 0, 0,-r)
<1 0; - 0,- || + 3 L GT(T + 1)a-7
+ mp
mp -1 + 6U% ||ا w-rl|,
where Ci 2
[log, m
+ 1-1p) 2U [L, + T..).
Proof of Lemma C.4
Proof. We will divide the proof of this lemma into four steps.
28

---

Step 1: show that
|E{(s, Wi, 0.) - =(0r, wi, 0,--)1 < (3UgLn. + BU,BL.)00-00 - Since E( O2)
(39)
(wi - wi, Eo [0' 0) h(0,0), 0)), define Eg ( 0)
Eor ()), where Eg is the shorthand of Bor~(we. In the following, we will show that each term in (O,,, Wi, 0,) is Lipschitz.
Term W, is not related to f and term w = w- (0,) is L. Lipschitz.
For term h(,, 0), denote 8(0, 0) == r(s, a) r(0) (Ø(s') x(s)) T w", we have
|/(O,, 01) h(O, 02)1
|,(00, 0:) log ne, (a|s) - 8(0,, 02) To. (clss)
< |]8(0, 0;),,00)// log ne, (d0,0 To (a|s)]
+
6(0,0,V log To. (a|s)]
< UsLil10 02l + B)((0,0)) -
< UsLil10, 021 + B((r(0)) r(02)) + [(((8)) ((5) (|w) - (02)ll
$ (UgL4+ + +2BL.))(1 ||0: 021 + B B s0mt0 [r(s.a) a)] Ey-mo, JaNto, [r(s. a)l
$ (UgLi + +BBL.) 02 + 2BU,dT (no, @ TeL 1.,0 2 )e₂)
1
S (U&L+ + 2BL, + 2BU, |A + [ogp m '1 +
p 1) 0211
Hence we have h) is La Li-iscchiit, where La denotes the above coefficient. For term Eg (O 0)), we have
Ee [h(O', 01)] Eo, (,'O0',0 02)]l
- |[E,, [h(O', 0,)] Ee, [h(O', 02)]ll + | [b(0', 02) - Es, [h(O', 0>)1l
S Ee, [llh(O',,) 01) hhOO,, .0,) + ||E,, [h(O', 02)] - [h,(,(O', 02)]1
< TA ||0 - 02|| + [Re, (m(0', 02)] - -o,, (N(O', 02)]ll
< Ln |0 0211 + 2BV (ro no, 102 @ To₂)
$ [L, + 2BB, + [logp m '1 T ]]| 021l
2 02l1-
Then we have Wi w is U bounded and L, LipLishchit;; k((00) - Es(h(O', 00] is 3Lx and 20, B-bounded By the triangle inequality, we have
[E(O,, w;, 02) 5(O,, wi. -.-r)1l S (3U, Ln + 27, (L.) 01 0,--1 S C2l 0-- where C22 : 3BU | (1 llogp m 21 ) + 3U L. + SU,
Step 2: show that
|E wr. 8) =(O,w,,,>> 0) < Bww - wi-rll-
(40)
Actually, we have
||E(O,w,, 0) E(0, w2, 0) = ||(] w2, Eo O', 0) - ((0.0)>1 S BUgBll w2ll Step 3: show that for tuples O (st, az 8141) and Ō. = (5t. āe 5142). Conditioning on St-rt1 and 0.-r, we have
Σ k=t-r
(E Wr 0z-,)
EI - 01- (41)
By definition of E(0, 0), we have
[B| we O - Wi 0,
|B((wrr 3 h:(O,, 0,-r) 1(,0,, O 0.-))]
|B w; 0--)) 0())) E[( - -w M(,,, 0+-1))
S 4U3 Bdrv (P(O, E -18 0,r)) P(O,, E 0,-)),
(42)
29

---

where the inequality comes from the definition of total variation distance. The total variation norm between O2 and O2 has been computed in 33 Plugging
33 into
42
get
W0, - WT- 0r 0--r)11 S 203 B|A L
Σ E 0--rll
k=
S BA + 1)04-7
Step 4: Show that conditioning on 8t-r-1 and 0.- we have
(E) - 40? Bmp
(43)
It can be shown that
(l. 02-,)l |||| ( W 0 5(0 w 0.-))ll
[ wi 01-)) (Wi w/ h(O, 0r-1))111
4U3 Bd (P(O, E -18 0,--,,,0-- M0. X TO.-. s P):
where (1) is due to the fact that O is from the stationary distribution which satisfies E[3 wi-r (r-r)] and (2) follows from the definition of total variation distance. From
Assumption 3.2 we know that
dFv Po.... mp"
We also have the fact that
P(O, -1st-141, 01-7) PP(8. 1188-r441, 0.-r) no. @ P.
Therefore, we have
E E[E wI,;, 0,-,)l S 4U3 Bmp
Combining 39
43
we can decompose the Markovian bias as
E E(,, wi 0.)]
B[E(O,, w,, [00,, 0,-)
+ LB| wi, 0,, - 0 E(0,, Wr 0r-r] 3(0 Wi Or-r]
+ IB|E(O,, W 0,_7) wrr,,
+ EE w,r0 0,-)]
s C2| 1,00,-0_,, 0, 2Us Bl wi-Fl
+ 203 A GT + 1)a 4U3 Bmp"
Thus we conclude our proof.
Proof of Lemma C.6
Proof. We will divide the proof of this lemma into three steps.
Step 1: show that
(2U,BLy 3L. - 0,-7|1
(44)
where L2 Ug + (2 22 +2--222--2 + [log, m m- 1/(1 - p)).
Since (O0,0) JVJ E,(h((', M(O, 0)), will show that each term in O(0, is Lipschitz.
For the term v by Lemma B.3 we know it's L. Lipschitz.
30

---

For term h(O, 0), denote 6(0,0) 0) :- r(s,a) r(0) + (0(s') - =T(s)) Tw", we have
[|([O, h(,, 0:)]l
(000,0))V ne, - 8(0,, 02) V log ni, (c|ss]
- ( log Te, (a|s)]
+ [16(0,,0:VVVogge 0(0,01)
6(0, 02) log To (a|s)]
< UsLz/10 02) + B(5(0,01) 8(0,02) 02)
$ UgL1100: 02 -
1000-r(000 r(02))
( Φ(s)) (0) -w:)) (02)l)
1 (UgL4 + -2BLB)), 02 + B B a [r(s, a)] BBnuuo amoto [r(
1 (U + +BL, - 02 + -
@ TB 14 @ To,)
S (UsLi + 2BL. + +BBU, + flog, m m= '1 1 |0: 0211.
Hence we have h(0,0) is Ln-Lisschitz, where La denotes the above coefficient. For term Ee (O 0)), have
[ [N(O', 01)] Eo, (o,]
$ Eo [M(O', 01)] Eo, (M(',, 02)]l + ||E,, [h(O', 02)] Eo, [h(O', 02)]
S Ee, [1] 01) h(O', .0,) + ||e, [h[O', 02)] Ee, (N(O',02)11
T. |00 02l + |E (M(O', 02)] Es, [h(O', 02)]l
< La | 02ll + 2BU, d 8 To 100 8 m8₂)
1
S [L, + 2BU, (1+ + [logp m '1+
01 021
S |L - -22l--
Then we have (@) L.- bounded and -ipssshhh h(0,0) EE[h(O', 0)] is 3L, -ipscchtt and 2U; B-bunded. By the triangle inequality, we have
(O,, 0.) OOO,, 0.--) (2U, I.. 0.--1 Step 2: show that for 2 t > 0, we have
Σ 1 0.
(45)
By definition of (O,,)), we have
(((0(O,.0,--)) ,(,,, -10
-E((VV/(0,--), h(O,,, 0,--) - h(O,,
-B((VJ(()--)) 0,-r)) EV 0,--))]1 < dL (15-r+t,,0--),P E - (
(46)
where the inequality comes from the definition of total variation distance. The total variation norm between O2 and O has been computed in 333 Plugging (3) into (46). we get
[B 0.-r) - 0,-,)] BU,BL
1 0--rll
k=t-
Step 3: show that for t >>>>00 0, we have
[E 0.-)) -(0',,,--)) S mmp'L.
(47)
From the definition of @(O,0), we have
[,, 0--r) -00%, -LV 0,
< AUU:LL,dry(P(O) E 100 no... @ P).
31

---

The inequality is due to the definition of total variation distance. From Assumption 3.2 drv (P -), (o,,,)) S mp--1
we know that
We also have the fact that
P(O, E $ - P E -,, 0K-T) TO, OPP
Therefore, we have
[ - -
S 4U, BU
Combining (44 45
and
477, we can decompose the Markovian bias as ( 0.)] E[o(O,, 0.) @ 0z-r)
[E(OOO, 0,_,) 0,,,, 0,-) -
OO0,, E(O 0,--),
where Ö₂ is from the auxiliary Markovian chain defined in 10 and O is from the stationary distribution which satisfies E[O(O,, 0.-r]] =0.
Then we have
E(@(O,, 0.)] s (2U&BL, + 3L, I
0 O. 0.--1
+ +2
Σ
1 0.- BUmpL
k=t-r
- (2UgBLy + 3Ly Inn
E - 02-1l
k=t-++1
+ +2ggBI,|ATT
B1 0 11 4Ug Bl.
< (2UrBLy + LT)
E E - 02-1ll
k=
+ +Ug
Σ
B110, 0j-1ll+ AUs
+1-s BUmpL
/=1-++1
< D1(T+1)
E 02-1ll D2mp"-1
Amt-r+1
< D 1) + D2mp"
where Dj = max + 3L, BU, A and D2 = 4U3BL, Thus we conclude the proof.
E IID Sampling Analysis
Algorithm 2 Single-tine Single-timescale Actor-Critic (i.i.d. sampling)
1: Input initial actor parameter Oo. initial critic parameter Wo. initial reward estimator yjo stepsize a₁ for actor, 8, for critic and 7 for reward estimator. 1 do
2: for = 0, ... T
3: Sample St ~ μio.
4: Take the action at To, (-1s;)
5: Observe next state sy ~ p--(ss at) and the reward r. = r(5,, 04)
6: 8, = Vt '/t + (0(()) Tw: ((+x))TT
7:
T
+ *r(t-- 11))
8:
W1+1 TT (wo (w+++A (.8)((((1))
9:
0.11 O, acd, Vo log Te, (0r(st)
10: end for
32

---

Note that under ii.d. sampling in Algorithm 2 we denote by the samples from the stationary distribution and 5/ the subsequent state following transition kernel s P(- 0z). Correspondingly. we redefine the observation tuple O2 (st, dz, 8() (in contrast to O₂ = (8t, 04, 81+1) in the Markovian sampling case). This modification implies the decoupling of O₂ and O++1 since $+41 1 in tuple O4+1 is new state sampled from the stationary distribution rather than inherited from Oz. This intuitively elucidates the vanishment of Markovian noise under i.idd sampling.
Lemma E.1. Under i.i sampling, have
E[ T1, 0.)] 0, (O, wi, 0,) O,
(O,, O2 0,) = O,
B 0,)] O.
Proof. Note that the expectation is taken over all the random variables. We use the notation O₂ to denote the tuple (st, oe, s() and vo.: to denote the sequence (st, as st), (st, ae, s(). (5s, at 8().
By definition in (3). it can be shown that
E ( The 0,)] = Evo.. ( (O,, 1/1, 0:)1
Emo.: Ero. [( ((r.)) [(0)))loox-11)
where is second equality is due law of total expectation. Once we know V0:--1, Te and J(O)) a random variable any more. It holds that
[E, Tc. 0:)]
Bvo.e- Boo [[n (ro))) (((()))(r==(())))leaa J(O)))
= Eve.- (1) [(e))) [(r: J(0,))
Bupie- (1) J(,)) [oo
-0,
where the last equation is due to Eo, -(0)))))))))111 = under i.d. sampling. By similar argument, we have
(Ov, Tr, 0.)l
Exin [(w, wf,9(0,w 0) g(w., 0.))1
Evo. Bro. [(w; - g0,, w. 0,) g(wr, 02) (Vor-1)
Exer- (wo w E... (g(O,, Wr ) g(wi. 0:)) [0:t-1)
Ever- (w: Eo. (g(O,, Wi 0,) g(w,, 0,)) 10:2-11
0,
where the fact that Eo, we, 0.) g(we,
=
Similarly, we have
ElO(O,, 02 0.)]
Evnn
0,)) [ N(O, 0:))
Evp Begr
h(O,, (o:c-1l
Evg. (V)) Ro (00,, In(O,, (o))\/ooor-1) 1h 0.)] h(OO, 0:))
Exnee
0,
where we use fact that O = O₂ under i.i.d. sampling.
The proof of TE( 0.)] is the same the above argument, which concludes the proof. 17
Proof of Theorem 3.6
Proof. The proof follows similarly the Markovian sampling case. Specifically, all the Markovian noises (see the definitions in (13) present in the former analysis reduce to zero after taking expec- tations. The detailed results and proof presented in Lemma E.T Then, replacing Lemma C.I
Lemma C.3 and Lemma C.6 Lemma E. will get the desired - convergence rate
and thus an O sample complexity accordingly.
33


Reviews:
[{"review_id": "aqQh0a6EKs", "reviewer": "Reviewer_bt4a", "summary": "This works provides finite sample analysis for single timescale actor critic.", "questions": "See above", "limitations": "See above", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "A finite sample analysis for single timescale actor critic under Markovian noise and infinite state space is definitely a notable contribution to the community.", "weaknesses": "My biggest concern is the correctness of this work. This work is a resubmission from ICML 2023. In the ICML round, all reviewers agree that this is a good paper until one expert reviewer that seems to really be in the field pointed out one critical technical error in the proof, leading to the rejection. But I unfortunately do not have access to the ICML reviews now so I will recommend \"rejection\" for now. If the authors provide the following information in the rebuttal, I am more than happy to evaluate the work again.\n\n1. What errors did the reviewer pointed out in the ICML round (it would help a lot if a copy of the original review can be provided, assuming the authors still have access to it)?\n2. Was the reviewer wrong or the authors were wrong?\n3. If the authors were wrong, how is the bug fixed in this version? If the reviewer was wrong, what mistake did the reviewer make?\n\n\nIt would help a lot if the authors could answer the above questions in details and in a self-contained way.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Thanks for reviewing our paper!\n**(Q1: What error was pointed out in the ICML submission)** Thanks for reviewing our work again. We are glad to show our refined results. The original comment in the ICML round is: \"However, the authors utilize a very quick but wrong inequality to extend the analysis technique in [1] to inifite state space case: When analyzing the interconnected system (line 1122), the term \"$bZ_T$\" should be corrected to \"$b\\sqrt{Z_T}$\" according to equation (18)\n. This is a quite nontrivial mistake. Since the term \"b\" is of constant order (line 1112) under the infinite state space setting, the convergence rate of \n will NOT be $\\widetilde{\\mathcal{O}}(1/\\sqrt{T})+\\mathcal{O}(T)$ \n. Instead, it will be an absolute constant independent of $T$\n if we apply the authors' trick of Young's inequality. As a consequence, the whole remaining proof should be wrong.\" So the error occurred at Line 1122 (now is fixed at Line 557), where according to equation (18) (now still equation (18)), the correct term should be $\\sqrt{Z_T}$ but we wrongly took it as $Z_T$ and performed the subsequential analysis. Now we have fixed this careless mistake and proved the results correctly.\n\n**(Q2: Who was wrong)** We were wrong. During the rebuttal, we realized that simply choosing appropriate stepsizes cannot fix the bug. We then have done a major revision after the rebuttal.\n\n**(Q3: How we fixed the bug in NeurIPS submission)** We have developed a new proof under an additional Assumption 3.4 of the $L_s$-smoothness property of the critic target $\\omega^\\ast(\\theta)$, where a different and tighter system of inequalities was developed. The smoothness property is used to bound the term $\\langle z_t, \\omega^\\ast(\\theta_t)-\\omega^\\ast(\\theta_{t+1})\\rangle$, which tracks both the critic estimation performance $z_t$ and the difference between the drifting critic targets $\\omega^\\ast(\\theta_t)$. In particular, we bound it by $\\sqrt{Z_T(2Y_T+8Z_T)}$ (see Theorem C.5). Then we were able to derive a solvable interconnected system, the solution of which leads to our main results. In the ICML version, we erroneously applied a crude bound of $\\sqrt{Z_T}$ to bound the same term. However, we mistakenly treated $\\sqrt{Z_T}$ as $Z_T$ in our attempts to solve the interconnected system. Indeed, if it were $Z_T$, the system is unsolvable and cannot show convergence as pointed out by the ICML reviewer."}, {"review_id": "lTOXZssOPV", "reviewer": "Reviewer_fvvv", "summary": "This paper provides a finite-time analysis of single-timescale, single-sample, average-reward actor-critic with a linear critic under Markovian sampling. It is established that the standard scheme achieves $\\epsilon$-approximate stationarity with $\\widetilde{O}(\\epsilon^{-2})$ sample complexity. The analysis is achieved by extending the small-gain analysis of [A. Oleshevsky & B. Gharesifard, _A small-gain analysis of single-timescale actor-critic_. SICON 2023], which was for the discounted setting, to the average reward setting. This is accomplished by leveraging a uniform ergodicity assumption (Assumption 3.2, line 202) and associated analysis (like, e.g., that of [Y. F. Wu, W. Zhang, P. Xu, Q. Gu, _A finite-time analysis of two time-scale actor-critic methods_. NeurIPS, 2020]) to handle the Markovian sampling that becomes particularly important in the average-reward setting. It is furthermore claimed that the results apply to problems with continuous state spaces. The sample complexity achieved matches the state of the art for finite-time analyses of actor-critic methods, yet applies to the single-timescale, single-sample, average-reward, Markovian sampling setting, which was previously an open question.", "questions": "* What is the key innovation required in the analysis?\n* What is the effort required in accommodating continuous state spaces?\n* Under what conditions do Assumptions 3.1 and 3.4 hold for continuous state spaces?\n* Why is Assumption 3.2 necessary? Or can it be eliminated?\n* How do we choose the stepsize ratio $c$ in practice?", "limitations": "Aside from the weaknesses and questions described above, the authors have adequately addressed the limitations of the work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "As stated in the summary, this work establishes that single-timescale, single-sample, average-reward actor-critic under Markovian sampling achieves $\\epsilon$-stationarity with $\\widetilde{O}(\\epsilon^{-2})$ sample complexity. This shows that this version of actor-critic matches the state of the art, resolving what was a previously an open question. Despite the analysis presented in the appendix being notation-heavy and somewhat difficult to follow, and though there are issues in the exposition and assumptions that need to be addressed (see weaknesses and questions below), the main steps in the theoretical results appear to be sound. The analysis appears to build off of the small-gain analysis of [Oleshevsky & Gharesifard, 2023], combined with elements of previous two-timescale analyses for average-reward actor-critic with the uniform ergodicity assumption such as [Wu et al., 2020], as well as some algebraic manipulations of inequalities. Though of uncertain practical utility, this contribution is definitely of interest to the theoretical reinforcement learning community.", "weaknesses": "I have some concerns about: (i) clarity about the innovation required in the analysis; (ii) the satisfiability of the assumptions made; and (iii) the dependence of the main result presented in Step 4 in lines 331-339 on having access to potentially unknown problem-specific constants when designing stepsizes. Addressing these issues or being clear about any limitations will likely strengthen the paper.\n\n(i) As stated above, the analysis appears to build off of [Oleshevsky & Gharesifard, 2023] to handle the interconnectedness of the single-timescale analysis, elements of two-timescale analyses like [Wu et al., 2020] to handle Markovian sampling, as well as algebraic manipulations of inequalities to combine it all together. However, it is unclear from the main body whether the analysis is a straightforward (albeit complicated) combination of these existing methods, or if some critical new insight and innovation are required. If the former, the significance of the contribution is weakened. If the latter, it should be stated more clearly. Also, the abstract claims that the analysis applies to continuous state spaces, and on lines 73-74 it is stated that achieving this requires \"significantly non-trivial effort in the analysis\". It is not clear where in the analysis this non-trivial effort takes place, however. If serious additional effort was required, it should be clearly stated exactly where it occurs.\n\n(ii) Two of the assumptions call into doubt the applicability of the result to continuous state spaces. On lines 198-199, it is stated that Assumption 3.1 holds under certain conditions in the tabular case, but applicability to the continuous state space case is not mentioned. The reader wonders: does Assumption 3.1 hold when $|S| = \\infty$? In addition, lines 220-221 state that Assumption 3.4 holds for the finite state-action space setting. Again: what about when $|S| = \\infty$? Since the analysis relies on these assumptions, it must be shown that they hold in the continuous state space setting for the corresponding claims in the abstract and introduction to be true. Finally, though uniform ergodicity (Assumption 3.2) is commonly assumed in average-reward analyses, the recent two-timescale analysis of [W. A. Suttle, A. S. Bedi, B. Patel, B. M. Sadler, A. Koppel, D. Manocha, _Beyond exponentially fast mixing in average-reward reinforcement learning via multi-level monte carlo actor-critic_. ICML 2023] removes the need for this assumption. It would be helpful to see a discussion of why Assumption 3.2 is still required in the single-timescale analysis or how it might be eliminated.\n\n(iii) On lines 334-337, it is pointed out that, for Step 4 (cf. lines 331-339) to work, a certain set of inequalities (line 335) needs to be satisfied. It is stated that this condition can be satisfied by choosing the stepsize ratio $c$ to be smaller than some threshold. On line 556 in the appendix, this threshold is given, but it involves the problem-specific constants $\\lambda, L_*, G, B$. It thus appears necessary that we have oracle knowledge or that an additional estimation procedure is required for the specific stepsize scheme to be operable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Thanks for reviewing our paper!\n**(Q1: Key innovation in the analysis)**\nThanks for seeking clarification. The key innovation lies in conducting a comprehensive analysis of each error term. In two-timescale actor-critic [Wu et al., 2020], convergence is deduced relying on multiplying the error term by the diminishing stepsize ratio $\\frac{\\alpha_t}{\\beta_t} \\rightarrow 0$ as $t\\rightarrow \\infty $. However, in the single-timescale setting, this ratio is constant $\\frac{\\alpha_t}{\\beta_t}=c$, requiring a more in-depth investigation and tighter analysis of each error term to establish convergence. These lead to non-trivial proofs that are distinct from the two main references, and we highlighted them in the proof sketch.\n\nTaking the error term $y_t(J(\\theta_t)-J(\\theta_{t+1}))$ for example, the two-timescale work bounds it using the $L_J$-Lipschitz continuity of $J(\\theta)$. In the single-timescale approach, solely relying on Lipschitz continuity is still too loose. To overcome this, we delve deeper and discover that the gradient of $J(\\theta)$ also possesses Lipschitz continuity (Lemma B.2), which means $J(\\theta)$ is $L_{J'}$-smoothness. With this new insight, we successfully bound the term $y_t(J(\\theta_t)-J(\\theta_{t+1}))$ with $\\sqrt{Y_TG_T}$, thereby establishing a solvable interconnected system. Together with many other careful analyses, we achieve much tighter bounds and are able to establish convergence of the more challenging single time-scale algorithm.\n\n**(Q2: On the effort required in accommodating continuous state spaces)**\nWe note that moving from a finite state space to an infinite state space takes significant and nontrivial efforts in analysis. This is due to the fact that some established results need to rely on intrinsic problem constants such as many Lipschitz constants that rely on the finite size of the state space ($|\\mathcal{S}|$), which however becomes infinite in the infinite state space scenario. Additionally, existing analysis concatenates all state-action pairs to create a finite-dimensional feature matrix and often requires summation over all states [Oleshevsky $\\And$ Gharesifard, 2023]. These analyses will not be possible when the state space is uncountable. Moreover, some convenient properties no longer exist in the continuous state space setting. For example, the uniform boundedness of Hessian of the problem matrix $A_\\theta$ no longer holds ([Oleshevsky $\\And$ Gharesifard, 2023], Lemma 4.8). These fundamental challenges require completely different analysis techniques.\n\n**(Q3: On Assumptions 3.1 and 3.4)** In fact, Assumption 3.1 is a fundamental regularity condition, which is often made to guarantee the problem’s solvability in the linear function approximation case and on continuous state space [Wu et al., 2020].\n\nFor Assumption 3.4, $\\nabla_\\theta \\mu_\\theta(s)$ is a Jacobian matrix such that its $d$th column is the gradient of the $d$th action dimension of the policy with respect to the policy parameters $\\theta$. Assumption 3.4 is equivalent to $L_\\mu$-smoothness of the stationary state distribution. It's difficult to characterize a general condition under which this assumption holds. But there are cases for which it holds, for example, linear systems with linear state feedback policy. \n\n**(Q4: On Assumption 3.2)** Assumption 3.2 can not be eliminated for the analyzed algorithm. The provided reference analyzes a multi-level Monte Carlo actor-critic which notably samples $2^{j_t}$ state-action pairs for each policy $\\pi_{\\theta_t}$ update. Taking the average of these multi-samples effectively reduces the statistical error (deviation from stationary distribution). However, we analyze the most general and fundamental **single-sample** single-timescale online actor-critic, which means for each policy update, we only sample one state-action pair. Consequently, the introduction of Assumption 3.2 becomes imperative in order to characterize the disparity between the distribution of the Markovian sample and its corresponding stationary distribution.\n\n**(Q5: On choosing the stepsize ratio in practice)** Due to the theoretical nature of the work, we characterize an upper bound of the stepsize ratio $c$ depending on unknown problem-specific constants, which is a sufficient condition for convergence. In practice, one can choose a relatively small $c$ to guarantee convergence, just like in solving many machine learning problems using SGD methods, people typically choose a small stepsize to have a better convergence guarantee and performance."}, {"review_id": "1QUJM6jn7v", "reviewer": "Reviewer_9Zts", "summary": "This paper studies the actor-critic algorithm with linear function approximation. The authors provide a single-time-scale analysis for the AC and achieve $\\epsilon^{-2}$ sample complexity.", "questions": "My concerns are listed in the weakness part.", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is overall well written and easy to follow\n- The single-time-scale analysis with markovian noise for actor-critic is new in the literature, to my best knowledge.\n- The policy gradient norm error analysis is interesting", "weaknesses": "- I'm confused about Assumption 3.4, I wonder how $L_\\mu$ contributes to the final results.\n- Assumption 3.1, though the authors mentioned a few paper using the same assumption, sounds pretty strong for me. It basically requires even the optimal policy should visit all state-action pairs, which is quite uncommon in practice. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Thanks for reviewing our paper!\n**(Q1: On the contribution of $L_\\mu$ to the final results)** Thanks for seeking clarification. In the current analysis, our final results are linear to the parameter $L_\\mu$. To keep $L_\\mu$ in the final results, the convergence rate in Theorem 3.5 can be kept as $\\mathcal{O}(L_\\mu\\frac{\\log^2 T}{\\sqrt{T}})$.\n\n**(Q2: On Assumption 3.1)** Although Assumption 3.1 is standard in theoretical analysis, we do understand that it may not be satisfied easily in practice. Note that the insight on full state-action exploration is a sufficient condition that guarantees Assumption 3.1. The converse may not be true. In addition, here the condition is presented as stronger than necessary for the sake of convenience: we actually only need the condition holds for those $\\theta$ that are actually visited during learning, not for all. But such more accurate conditions are difficult to characterize analytically."}, {"review_id": "UZfZl8RGGJ", "reviewer": "Reviewer_2T31", "summary": "The work studies the actor-critic algorithm’s convergence under the single-timescale update where the step-size of actor and critic variables are only proportional by a  constant.  Authors suggest the epsilon-optimal solution with a sample complexity $\\tilde{O}(\\epsilon^{-2})$  under standard assumptions and $O(\\epsilon^{-2})$ under i.i.d. sampling.", "questions": "The author asserts that their methods are capable of addressing continuous state situations, even when the state space is infinite. However, it is unclear whether the analyses can also be extended to infinite action spaces. Could the author provide some clarification and analyses on this aspect? \n\nSince the paper obtain the same results of  $O(\\epsilon^{-2})$  with previous works, could the author discuss and compare their results more specifically? (e.g., the constant comparison or simple control experiments)", "limitations": "The paper still needs many strong assumptions to analyze the problem and it is very understandable due to the theoretical nature of the work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper tries to analyze the sample complexity of the AC method under more practical Markovian sampling, where the transition tuples are generated from a single trajectory. The theoretical problem is well-motivated.\n\nThe paper proposes a new analysis framework for the algorithm and establishes the sample complexity of  $O(\\epsilon^{-2})$ which matches the best existing sample complexity for the single-timescale AC algorithm, and a sample complexity of  $\\tilde{O}(\\epsilon^{-2})$ without i.i.d. assumption.", "weaknesses": "After removing the assumption of independence and identically distributed (i.i.d.) data, the author introduces a new assumption, namely that the Markov chain is geometrically mixing and the rollout state distribution rapidly approximates the stationary distribution (assumption 3.2). I am curious whether this assumption, although slightly weaker than the i.i.d. assumption, can still be considered strong, as it may not be commonly applicable in practical scenarios. Furthermore, this assumption appears to conflict with the statement \"the transition tuples are generated from a single trajectory.\"\n\nIn the final results, the author requires a condition of $T>2\\tau$ to ensure that the obtained samples are sufficiently close to samples from an i.i.d. stationary distribution.\n\nNumerous studies have already examined actor-critic methods and achieved the same sample complexity of $O(\\epsilon^{-2})$. The author claimed that their proposed methods can be utilized without relying on the i.i.d. assumption and achieve a slightly inferior complexity of $\\tilde{O}(\\epsilon^{-2})$ under alternative assumptions. It is hard to judge the contribution in this situation since it is natural to obtain a worse result under milder assumptions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Thanks for reviewing our paper!\n**(W1: On single trajectory and condition $T>2\\tau_T$)** Thanks for your comment. We are afraid that there is a misunderstanding concerning our work. Assumption 3.2 does not conflict with the statement \"the transition tuples are generated from a single trajectory.\" As shown in Algorithm 1, all transition tuples are generated from a single trajectory. In the final results, $T$ is the total iteration number and $T>2\\tau_T$ means that the theorem holds for large $T$. Each state-action pair $(s_t,a_t)$ is sampled from a single trajectory online consecutively rather than waiting for at least $2\\tau_T$. One of the challenges in our analysis is exactly due to such a parsimonious online sampling, because it does not guarantee the sample distributes sufficiently close to the stationary distribution.\n\n**(Q1: On infinite action space)**  Our work is capable of addressing continuous state space but not infinite action space. We stated in Line 123 that \"We consider a finite action space, whereas the state\nspace can be either a finite set or an (unbounded) real vector space\". To the best of our efforts, it remains challenging to investigate the infinite action space setting. One of the key obstacles we have identified is that if the action space is infinite, one cannot ensure the target critic $\\omega^\\ast(\\theta)$ is still Lipschitz continuous (Lemma B.3). We leave this challenge setting for our future work.\n\n**(Q2: On the comparison with previous works)** We compare our work with two important previous results. We improve the work of [Chen et al., 2021] to the Markovian sample and we additionally can show convergence for the critic. We improve the work of [Oleshevsky $\\And$ Gharesifard, 2023] to the infinite state space setting and Markovian sample setting. The reader is referred to the second part of Main Contribution for a detailed comparison."}, {"review_id": "qcRj5FnDug", "reviewer": "Reviewer_JDcB", "summary": "The paper studies finding the optimal policy in an infinite-horizon average-reward MDP with an online, sample-based algorithm. The state-of-the-art algorithm in this setting uses two different timescales and is known to have a sample complexity of $\\widetilde{\\mathcal{O}}(\\epsilon^{-2.5})$. This paper shows that a single-timescale version of the actor-critic algorithm enjoys an improved complexity of $\\widetilde{\\mathcal{O}}(\\epsilon^{-2})$, up to a logarithm factor. If we were always able to sample according to the stationary distribution under the current policy, the logarithm factor can be removed.", "questions": "- Related work section is somewhat limited. The connection of the paper to existing works on single-loop AC algorithms including the following ones should be discussed.\n\nHong, M., Wai, H.T., Wang, Z. and Yang, Z., 2023. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33(1), pp.147-180.\n\nZeng, S., Doan, T.T. and Romberg, J., 2021. A two-time-scale stochastic optimization framework with applications in control and reinforcement learning. arXiv preprint arXiv:2109.14756.\n\nKhodadadian, S., Doan, T.T., Romberg, J. and Maguluri, S.T., 2022. Finite sample analysis of two-time-scale natural actor-critic algorithm. IEEE Transactions on Automatic Control.\n\nZhou, M. and Lu, J., 2022. Single Time-scale Actor-critic Method to Solve the Linear Quadratic Regulator with Convergence Guarantees. arXiv preprint arXiv:2202.00048.\n\n\n- I do not feel that the discussion of i.i.d. sampling case and the theorem adds much to the paper. The claimed contribution on Markovian sampling also seems a bit oversold. Many existing works have shown how Markovian samples can be handled at the cost of introducing a log factor, which does not appear if the samples are i.i.d.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Being able to improve the convergence rate from $\\widetilde{\\mathcal{O}}(\\epsilon^{-2.5})$ to $\\widetilde{\\mathcal{O}}(\\epsilon^{-2})$ is a pretty significant contribution. As the authors noted, this rate already matches the rate of standard SGD for non-convex functions. The paper is also well-written.", "weaknesses": "While the presentation of the paper is mostly clear, more discussion how exactly the authors improved the convergence rate and why previous works failed to do that is needed for the audience to appreciate the technical contribution. In fact, many existing works on two-timescale AC do not start off trying to the make updates two-timescale. Making the step sizes for the actor and critic decay at the same rate is allowed, but doing so hurts their convergence rates. Do the authors take advantage of any other structure of the MDP beyond general non-convexity to make a single timescale more favorable?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Thanks for reviewing our paper!\n**(W1: On general MDP)** Thanks for your comments. In this paper, we only consider the general MDP with a non-convex objective function. The single-timescale approach is superior to the two-timescale approach because the latter updates the actor slower than the critic. Therefore, there is a delay in learning and inefficient usage of data in the two-timescale approach. Considering other structures of MDP to validate the superiority of single-timescale actor-critic would be interesting future work.\n\n**(Q1: On related reference)** Thanks for sharing the relevant references. We will discuss them adequately.\n\n**(Q2: On the discussion of i.i.d. sampling)** Thanks for your comments. We agree that the discussion of the i.i.d. sampling case does not add much to the paper. The i.i.d. case is included for comparison to show that the log factor is caused by the Markovian samples. "}]

Author rebuttal:

Meta-review: This paper offers a finite-time analysis of the actor-critic algorithm in the context of single-timescale, single-sample, average-reward settings with Markovian sampling. The work extends previous small-gain analyses from discounted to average-reward settings by leveraging a uniform ergodicity assumption. The paper achieves state-of-the-art sample complexity of actor-critic methods. The authors have addressed the concerns raised by the reviewers and all of the reviewers have recommended acceptance for the work.
Decision: Accept (poster)