On the Convergence of Single-Timescale Actor-Critic
Authors: Navdeep Kumar
Priyank Agrawal
Giorgia Ramponi
Kfir Yehuda Levy
Shie Mannor
Venue: NeurIPS 2025 poster ()
Keywords: Policy Gradient
Reinforcement Learning
Actor-Critic Algorithms
Sample Complexity
Convergence
Primary area: reinforcement_learning
TL;DR: We imrove sample complexity of single time scale actor critic to $O(\epsilon^{-3})$ from $O(\epsilon^{-4})$ for obtaining $\epsilon$-close global optimal policy.

Abstract: We analyze the global convergence of the single-timescale actor-critic (AC) algorithm for the infinite-horizon discounted Markov Decision Processes (MDPs) with finite state spaces. To this end, we introduce an elegant analytical framework for handling complex, coupled recursions inherent in the algorithm. Leveraging this framework, we establish that the algorithm converges to an $\epsilon$-close \textbf{globally optimal} policy with a sample complexity of $ O(\epsilon^{-3}) $. This significantly improves upon the existing complexity of $O(\epsilon^{-2})$ to achieve $\epsilon$-close  \textbf{stationary policy}, which is equivalent to the complexity of $O(\epsilon^{-4})$ to achieve $\epsilon$-close  \textbf{globally optimal} policy using gradient domination lemma. Furthermore, we demonstrate that to achieve this improvement, the step sizes for both the actor and critic must decay as $ O(k^{-\frac{2}{3}}) $ with iteration $k$, diverging from the conventional $O(k^{-\frac{1}{2}}) $ rates commonly used in (non)convex optimization.

On the Convergence of Single-Tinee Timescale Actor-Critic
Navdeep Kumar" Technion
Priyank Agrawal, Columbia University
Giorgia Ramponi University of Zurich
Kfir Levy
Shie Mannor
Technion
Technion
Abstract
We analyze the global convergence of the single-timescale actor-critic (AC) algo- rithm for the infinite-horizon discounted Markov Decision Processes (MDPs) with finite state spaces. To this end, we introduce an elegant analytical framework for handling complex, coupled recursions inherent in the algorithm. Leveraging this framework, we establish that the algorithm converges to an c-close globally opti- mal policy with sample complexity of 3 This significantly improves upon the existing complexity O(c ) to achieve c-close stationary policy, which is equivalent to the complexity of ( to achieve e-close globally optimal policy using gradient domination lemma. Furthermore, we demonstrate that to achieve this improvement, the step sizes for both the actor and critic must decay as O(k 3) with iteration k, diverging from the conventional O(k ((-²) rates commonly used in (non)conve)) optimization.
1 Introduction
Actor-critic algorithm. initially introduced in Konda and Tsitsiklis (1999). consist of two key com- ponents: the actor, which refines the policy towards an optimal solution based on feedback from the critic, and the critic, which evaluates the value of the current policy (specifically the Q-value). has been adapted in various forms (Schulman et al. (2017) and have emerged as one of the most successful methods in reinforcement learning (Miih et al. 2015 Silver et al. 2017: OpenAl et al. 2019 Schrittwieser al. 2020).
Despite their remarkable empirical success, the theoretical convergence of actor-critic algorithms not well understood. One line of research explores a two-time-scale version in which the actor and the critic are effectively decoupled, greatly simplifying the analyses. This can be achieved via double-loop version, where the critic evaluates the policy in the inner loop, and the actor updates the policy in the outer loop (Yang et al. al., (219 Agarwal et al.) 2020 Wang et al. 2022 Kumar et al. / 2023; Wang et al. 2019). or via single-loop structure, but the critic updates much faster than the
actor [Borkar] 2022). In the later setup. the ratio of the learning rates of the actor and critic tends to zero with the number of iterations. Essentially, the critic perceives the actor as nearly stationary, while the actor views the critic as almost converged. Konda and Tsitsiklis (199); Bhhttaggrr et al. (2009); Chen et al.) (2023); Hong et al. (2022); Wu et al. (2022): Xu et al. (2020b). is important note that both frameworks are artificial constructs to ease the analysis, but they often sample-inefffcient and therefore seldom used practical implementations (Olshevsky and Gharesifard] (023).
In this work, we focus on single time-scale actor-critic framework where both the actor and the critic are updated with each sample using similar step sizes Sutton and Barto (018).. While this framework
"corrosponding author email navdeep. kumardzohomail,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

is more versatile and practical, but the theoretical analysis of single-time actor-critic algorithms faces significant challenges due to the strong coupling between the actor and critic. Since both components evolve inseparably together with similar rates, the analytical challenge lies in understanding stable error propagation schedule.
For the first time, Castro and Meir (009) established asymptotic convergence of the single time scale actor critic to a neighborhood of an optimal value. This was followed by the recent works Chen et al. (2 Olshevsky and Gharesifard (223); Chen and Zhao (2024) demonstrating a sample complexity O(c for achieving an c-close stationary policy, where the squared norm of the gradient of the return is less than e, under various settings. This corresponds to a sample complexity of (c +) for achieving an e-close globally optimal policy (see Proposition 3..2... The question of whether this O(E complexity can be further improved remains open, and this paper provides a favorable answer.
In this work, we first formulate the recursions for actor and critic errors which are quite complex. None of the actor and critic errors are monotonically decreasing. We then identify Lyaponov term (sum of actor eтror and squared of critic error), and obtain its recursions independent of all the other terms. This Lyapunov recursion is monotonically decreasing but more challenging than in the exact gradient case found in Xiao 22022; Zhang et al. (2020), due to the presence of a time-dependent learning rate. To address this, we develop an elegant ODE domination methodology for solving these recursions, yielding significantly improved bounds.
Our contributions are summarized as follows:
1. Improved Global Convergence Rate: We establish sharper global convergence result for sinle-timesedd actor actor-critic algorithms in ceftmax-parametten discounted MDPs. Our analysis shows sample complexity of O(e-3) to compute an 6-optimal policy, improving upon the prior best rate of ()
2. ODE-Based Methodology with Direct Global Guarantees: Our core technical innovation is a streamlined ODE-based analysis for resolving the interdependent actor and critic updates. Unlike previous approaches that first bound convergence to stationary points (c.g., O(E-2) for e-stationary policies), we directly bound the global sub-optimality gap J JTN
3. Broad Applicability of Techniques: The techniques developed are concise and modular, and may extend naturally to related settings such as minimax optimization, bi-level opti- mization, robust MDPs, and multi-agens reinforcement learning and could be of independent interest.
1.1 Related works
Policy gradient based methods Sutton and Barto (201 8); Schulman et al. (2015): Mnih et al. (0055) have been well used in practice with empirical success exceeding beyond the val value-brl value-based algo- rithms Auer et al. (2008); Azar al. (2017); Jin et al. (2018) Agrawal and Agrawal 2024); Agrawal ct al. (025). Naturally, its convergence properties of policy gradient has been of a great interests. Only. asymptotic convergence of policy gradient has been well-established in WWlllaas (1922) y, Sutton
ct al.
1999); Kakade
2001); Baxter and Bartlett (2001) until very recently as summarized below.
Projected Policy Gradient (PPG): Given oracle access to gradient, Bhandari and Russo (024);
Agarwal et al. (2020) established global convergence of the projected policy gradient (tabular setting) with an iteration complexity of O(e-3) 2) in discounted reward setting. Following up, an improved recursion analysis, led to complexity of O -1) Xiao (2022). Recently, Liu al. (2024a) obtained an linear convergence was obtained for an large enough learning rate and also for aggressively increasing step sizes. Further, PPG is proven to find global optimal policy finite steps Liu et al. 2024b).
Softmax Parametrized Policy Gradient Often in practice, parametrized policies are used and softmax is an one of the most popular parametrization. Softmax policy gradient (T) enjoys iteration complexity of (1) for global convergence Mei et al. ):22); Liu et al. (2024a). This complexity matching with lower bound of O -() established in Mei al. (2022): Liu et al. (2024a).
Stochastic Policy Gradient Descent Often the gradient is not available in practice, and is es- timated via samples. Vanilla SGD (stochastic gradient descent) and stochastic variance reduced
2

---

gradient descent (SVRGD) has sample complexity of O and O 3) respectively, for achieving | I E (where J is return of the policy T) Xu al. (2020a). This local convergence yields global convergence of iteration complexity of ((e ) ( 3 ) for SGD and SVRGD respectively us- ing Proposition 3.2 Further. SGD achieves second order stationary point with an iteration complexity of O(e
Zhang et al. (020))
Single Time Scale Actor-critic Algorithm: It is class of algorithms where critic (gradient, value function) and actor (policy) updated simultaneously. This is arguably the most popular algorithms used in many variants in practice Konda and Tiitsiklis (1999); [Bhatnagar et al. (2009); |Schulman (ct al. (2015) 2017). Castro and Meir (2009) first established asymptotic convergence of the single time scale actor-critic algorithm. Later, Olshevsky and Charesifard (2023); ; Chen and Zhao (2024); Olshevsky and Gharesifard (2023) established the local convergence of single time-scale actor-critic algorithm with ( see Table 1) sample complexity of () for achieving V S E. This yields
global convergence (J) J= I c, where J optimal return) with sample complexity of O(e
using Gradient Domination Lemma shown in Proposition 3.2 Olshevsky and Gharesifard (2023)
The main limitation of the analysis in Chen and Zhao (2024) that it treats the policy optimization objective as generic smooth non-convex function and follows the standard approach of bounding the average squared gradient norm. This ignores the gradient domination structure, which, if applied only at the end, yields a weaker rate of O(e=)). Our key innovation is to explicitly exploit this structure when constraining the iteration-wise drift of the actor. Doing so required developing new techniques to bandle the resulting interdependent recursions, leading to stronger results. In summary, our analysis is more tailored to RL by effectively leveraging the gradient domination property, unlike the standard smooth optimization approach used in prior work.
Two Time Scale (/Double Loop) Actor Critic Algorithm. First, Konda and Tsitsiklis (1999) showed convergence of actor-critic algorithm to stationary point using two time scale analysis of Borkar (2022). The work Gaur et al. (2024) establishes (c-²3) sample complexity of a actor-critic algorithm variant (see Algorithm 1Gaur et al. (2024)). The algorithm uses O(e-3) new samples for the global convergence. However, it maintains the buffer of O(c-?) samples at each iteration. For achieving E-close global optimal policy, the algorithm requires O iteration, and each iteration repeatedly uses the samples from the buffer, O(e many times. In conclusion, the algorithm uses O(--)) new samples, using them (c=5)) times in total, thereby significantly inflating the memory requirements and computational complexity. In comparison, our algorithm does not use any buffer and use new sample in each iteration.
Natural Actor Critic (NAC) Algorithms. NAC algorithm is another class of algorithms Amari ; Kakade (2001); y; Bagnell and Schneider (2003); Peters and Schaal (008): Bhatnagar et al.
(1998)
(2009) proposed to make the gradient updates independent of different policy parameterizations. has
linear convergence rate (iteration complexity of O e ')) under exact gradient setting Bhatnagar
ct al. (2009) which much faster the vanilla gradient descent. Similarly, the sample based NAC algorithms Ganesh et al. (2024) also enjoys better sample complexity of O()-2). Xu et al. 22020b) establishes the global convergence of the natural actor-critic algorithm with a sample complexity of
O(E-1) in discounted reward MDPs However, the natural actor-critic algorithm demands additional computations, which can be challenging. (Yuan et al. (022) too establishes global convergence with sample complexity of O(E however, it requires additional structural assumption on the problem which is highly restrictive. However, NAC requires the inversion of the Fisher Information Matrix (FIM) in the update rule. This inverse computation makes the implementation difficult and sometimes unfeasible (for an instance, FIM is not invertible in direct parametrization, if ds((s) = 0 for some s). We note that actor-critic is a very different algorithm than NAC, arguably the most useful and versatile, hence deserving its own independent study.
2 Preliminaries
We consider the class of infinite horizon discounted reward MDPs with finite state space S and finite action space A with discount factor 7 E [o, 1) Sutton and Barto (0118): Puterman (1944). The underlying environment is modeled as probability transition kernel denoted by P E (A A A We consider the class of randomized policies II = (N : S - A A). where a policy и maps each state to probability vector over the action space. The transition kernel corresponding to a policy
3

---

Table 1: Related Work: Sample Complexity of Single Time Scale Actor Critic
Work
Convergence
Sample Complexity
Actor
Critic Step size 5
Sampling
Step size T)
Olshevsky
and
| S
O(e
h
i.id.
Gharesifard
(0233
Chen et al.
2021
Chen
and Zhao
| E
O(E
k
k-
Markovian
(2024)
Ours
J" << O(c-3)
i..dd.
| < J cc for some constant c, see Proposition 3.2 These works are for different settings such average reward, discounted reward, finite state space, and infinite state space, please refer to the individual work for more details.
denotes the single step probability of moving from state to s' under policy т. Let R(s, a) E [-1, denote the single step reward obtained by taking action policy т at state E S is defined as R = Eas s) R(s, a). The discounted average reward (or return) J" associated with policy defined as:
is represented by Pa S - S, where (" (s) = ((ss)
A in state S. The single-step reward associated with
o
===
E
7
RR
P,80 - (1-77--""
where je E AS denotes the initial state distribution. can be alternatively expressed as p-) is the stationary measure under the transition kernel pa, Value function e = (1 - R satisfies the following Bellman
(1 - -1--))1 Eees d" Rs) where d' = 01 -1-
equation 8º = Rº + (PPutrrmnn 1994 Bertsekas 2007 The Q-value function Q E R x
associated with policy is defined Qa (s. a) = R(s. a)
Eves P(s'ls, as" for all
(s, a) E x A. For simplicity, we will also assume || S 1.
In this paper, we consider soft-max policy parameterized by 0 E S as (a(a))) = Σ, clees Mei al. 2022). The objective is obtain optimal policy '² that maximizes the return 'T We denote J shorthand for the optimal return _ The exact policy gradient update is given
0x+1 02 + "
where is the learning rate, in most vanilla form Sutton and Barto 2018). The policy gradient can be derived as
0.
= (1 71) (s)TT( (1)
a)
20 (, a)
where (s, := := vd (s) is advantage function Mei et al. (0022). The return _ is a highly non-concave function, making global convergence guarantees for the above policy gradient method very challenging. However, the return _
[T-pp -smooth with respect to Mei et al.
(002)).
Lemma 2.1. (Gradient Domination Lemma, Mei al. 2022 The sub-optimality is upper bounded by the norm of the gradient as
| 112
J
J
V3CPL
d' where CPL max; f 1o is mismatch coefficient and ming min, Te. (a)(s))
The result states that the norm of the gradient vanishes only when the sub-optimality is zero. In other words, the gradient is zero only at the optimal policies. This, combined with the Sufficient Increase Lemma, directly leads to the global convergence of the policy gradient update rule in (

---

However, the above lemma requires the mismatch coefficient Opy to be bounded, which can be ensured by setting the initial distribution pu(s) for all states. Unfortunately, failure ensure 0 may lead to local solutions Kumar et al. (2024). Additionally, the result requires the constant c to be strictly greater than zero. This condition can be satisfied by initializing the parameterization with 8g 0 or by ensuring it remains bounded. Furthermore, as the iterates progress towards an optimal policy, the constant remains bounded away from zero.
3 Main
In this work, we focus on the convergence of the widely used single time-scale actor-critic algorithm (T). where the actor (policy) and critic (value function) are updated simultaneously Konda and Tsitsiklis (1999); Sutton and Barto (2018); Chen et al. (2021) Olshevsky and Gharesifard (2023);
Chen and Zhao 2024). Notably, this algorithm operates with a single sample per iteration, without relying on batch processing or maintaining an experience replay buffer.
Algorithm 1 Single Time Scale Actor Critic Algorithm
Input: Stepsizes Tik, Ak
while not converged; k == k + do
2:
Sample ~ d ~ no, x=,(-1s) (-|s) and get the next state-action s' ~ P(-(s,a,, d' ~ (-1s'.
3: Policy update:
Ok+1 (s, a) = (x(s,)) + mm - --))- where A(s, a) Q(s, v(s) and v(s) = En To, (als))((ssaa)
4: Q-value update:
Q(s,a) Q(s, a) + 3x (((5)))+(((5.))-0000 Q(s,
5: end while
Our objective is to derive policy ı that maximizes the expected discounted return J using sampled data. However, due to the stochastic nature of Algorithm I focus analyzing the expected return [[ at each iteration k.
Note that the algorithm requires samples 8ą d from the occupation measure at each iteration, which is a common assumption in most works on the discounted reward setting Zhang et al. (2020) :
Konda and Tsitsiklis (1999); Bhatnagar et al. (2009); Chen et al.] (202T): Kumar et al. (023) )
Olshevsky and Gharesifard (2023). This can be achieved by initializing the Markov chain with so μ. and at each step continuing the chain with probability by sampling 8141 p0 (-Is.),
or terminating the chain with probability (1 7)). Once the chain terminates, we randomly select state uniformly Sg. This process ensures that the state Sy is sampled from d= However, this approach increases the average computational complexity by a factor of 1 - There are potentially more efficient approaches to achieve this sampling, and several studies Ww et al. (2022); Xu et al. (2020b) have investigated convergence analysis using Markovian sampling. However, omit these considerations here for simplicity.
Assumption 3.1. [Sufficient Exploration Assumption] There exists a such that:
(Q" - Q, D -1- - Q) 2 AllQT - Q11
where Pa((s, d²), a)) P(s' ((s')s, a) and D= (F(((s, ( a'), a)) 1 ( (('',a') (s, dt (s)m())s).
Throughout this paper, we adopt the exploration assumption mentioned above, which is standard and, to the best of our knowledge, has been made in all prior works Olshevsky and Gharesifard (2023);
Chen al. (202T); Chen and Zhao (2024); [Bhatngarr et al. (2009); Konda and Tsitsiklis (199))
Zhang et al. (2020). Note that the both actor and critic evolving simultaneously. with actor updating the policy with the imprecise critic's feedback (Q-value) and critic tracking the Q-value of the changing policies. This complex interdependent analysis of error is the core subject of investigation
5

---

of this paper. However, the above assumption provides the bare minimum condition that the critic convergence to the Q-value of any fixed policy pppeccation.Specfficalll for any fixed policy n, the Q-value update given by (line 4 of Algorithm I:
Qm+1(s, a) am(s,a) + Be [(ssaa) + =mm((m,mm)))))m) -
(2)
where 8 d=, a (-1s)) P(((s,a), ~ (-16'),, Qm converges to the true Q-value Q" in expectation, under this exploration assumption, More precisely, || Q"I S c for some < 1 (see Lemma A.T The The above assumption satisfied if all the coordiantes of Q-values are updated often enough. This can be ensured by having strictly positive support of initial bate-distribution all the states (min, u(s) > 0) and having sufficient exploratory policies.
Local Convergence To Global Convergence. Convergence single time-scale actor-critic (Al- gorithm TD has been studied for long time,,Konda and T' Tiissiklss (1999); Bhhtnagar et al. (200));
Zhang et al. (2020): (Olshevsky and Gharesifard (2023); Chen al. (2021); Chen and Zhao (2024).
These works establish local convergence bounding the average expected square of gradient of the return, with following state-of-the-ar rate
K
F
K
This local sample complexity of O(e translates to global sample complexity of O(e as shown in the result below.
Proposition 3.2. A local e-close stationary policy is equivalent to Ve-close global optimal policy. That is
V O(k-t) = J-- <0k
Proof. The proof follows directly from Gradient Domination Lemma 2.1 and Jensen's inequality, with more details in the appendix.
Now we present below the main result of the paper that proves the convergence of the Algorithm with sample complexity of (c--3) to achieve e-close global optimal policy.
Theorem 3.3 (Main Result), For step size 3k. MJ- = O(k 3) in Algorithm
we have
E. < O(k $),
Vk 2 0.
The above result significant improves upon the existing sample complexity of (c-4)) Olshevsky and Gharesifard] ):023); Chen al. (202T); Chen and Zhao 2024) as summarized in Table Additionally. the convergence is established on the last iterate the result above. If we follow the analysis in Chen and Zhao (2024) and plug in the gradient domination condition at the end as shown in the Proposition 3.2, the convergence in value function space will be on the best iterate (in addition to having inferior rate).
The convergence analysis consists of following three main components, discussed details in the section next.
1. Deriving Recursions for Actor and Critic Errors:
The first step involves formulating the recursions for the actor and critic errors, which are inherently complex and interconnected. This step inspired by the approach outlined in Chen and Zhao (2024).
2. Identifying well behaved Lyapunov Term: While prior works utilize the standard contex-ott technique to rearrange the recursion, expressing the "norm of the gradient" through telescoping sum to establish local convergence Chen and Zhao (022)). this work takes a novel direction. Specifically, leverages the additional problem structure, encapsulated in the Gradient Domination Lemma, to identify a Lyapunov term ferm-defined as the sum of the actor error and the square of the critic error- and derive Lyapunov recursion.

---

3. Developing an elegant ODE domination Method to Bound the Lyapunov Recursion: The derived Lyapunov recursion poses sigmificant challenges compared to the exact gradient case studied in Xiao (022), primarily due to the presence of time-decaying learning rates. To address this, we develop an elegant ODE domination methodology that enables to establish bounds on the Lyapunov recursion. These bounds, in turn, yield precise characterizations of both the actor and critic errors.
4 Convergence Analysis
In this section, we present the convergence analysis of Algorithm 1 but first, we introduce some shorthand notations for clarity. Throughout the paper, we use the following conventions:
J T R, A = A IR S
Q- ===Q=0 E R =d E ER..
Additionally, we define ag, 2k, yk E IR as
== E|J Jk,, which represents the expected sub-optimality.
V Ex - Q+T,2 which denotes the expected critic tracking error.
yk = V which denotes the expected norm of the gradient.
summarize all useful constants in the Table We begin by deriving an actor recursion, which is essentially sufficient increase lemma for noisy and biased gradient ascent (Line 3 of Algorithm|] [ This recursion arises from the smoothness properties of the return and serves as an extension of its non-noisy version presented in Mei et al. (2022).
Lemma 4.1. [Actor Recursion] Let 0g be the iterates from Algorithm ! then sub-optimality decreases
ak+1 S 0g - CI e211 + Call
The recursion above illustrates the dependence of sub-optimality progression on various terms. The Tus indicates that the sub-optimality decreases proportionally to the square of the second term, I->²t
gradient norm and the learning rate, which is consistent with the expected behavior of gradient ascent smooth function in standard optimization. The term 24ave represents the bias arising from 1-7
the error in Q-value estimation (critic error), implying that higher critic estimation error reduces the improvement in the policy. Finally, the term the updates.
accounts for the variance (second moment) of 2L
Now, we shift our focus the critic error. The exploration Assumption 3.J ensures the evaluation of the policy (Q-value estimation in expectation) through samples with respect to a fixed policy. However, in Algorithm 1 the policy changes every iteration, which makes the derivation of the result below somewhat more challenging.
Lemma 4.2. [Critic Recursion] In Algorithm
7 critic error follows the following recursion 2 I (1 c43x)² + c + cotl + c7T%3lk<kk
where constants e; are defined the appendix.
The term (1 - c3 represents the geometric decrease of the critic error, as the Q-value is a contraction operator. The terms 35 and c arise from the variance in the critic and policy updates. Finally, the term U7. reflects the effect of the "moving goalpost," where the critic evaluates policy that changes in each iteration by an amount proportional to yk-
Lemma 4.3 (Gradient Domination). The sub-optimality is upper bound by gradient as
ag S Caffk-
The result above upper bounds the sub subooptimality with the gradient, which follows Lemma 2.1 and Jensen's 's inequality. In summary, we have the following set of simplified recursions:
Actor: d++1 aa CiTR + =2 + cavi
Critic:
2 2 ca + ca + can + c7n.
GDL:
S calk.

---

(Actert (cnte)
2.44 (Lyapunow;
30
25-
C=2.653,
10-
05-
foratin
Figure 1: Actor- Critic recursion in Random C₁ 107j = 33x = (1+b)) k) 00. 20 = 2.
Solving these interdependent recursions highly challenging and forms the core technical contribu- tion of this paper. Notably, we cannot guarantee monotonic decrease in either the sub-optimality ag or the critic error 25 across iterations, since 0*+1 tends decrease while 2 increases with
the growth yk- A crucial observation that the Lyapunov term 2k+1 := ax+1 + 2 exhibits a consistent decrease y& increases, shown in Figure [ This highlights the stability and utility of the Lyapunov term characterizing the system's behavior. Now to formally prove this, we combine the actor and critic recursions, assume 3g C and apply additional algebraic manipulations (detailed in the appendix). This leads to the following recursion:
ak+1 + 2 S ax + ot C1277k Us + 2i. + CL1TE
Using the Gradient Domination Lemma (GDL), we derive the Lyapunov recursion:
Fk+1 S Ty C13m- + en
which can be solved as stated following result.
Lemma 4.4 (ODE Domination Lemma). Given mp cial teisk )3, the recursion 2k+1 T C137p-4 + en vn satisfies the bound:
of
Cisk
23
Proof. The detailed steps of the proof are provided the appendix. The key idea solving the recursion is to establish that Fa lies below the trajectory of the following ODE:
duk dk
C137/ uk + cm
We simplify this by appropriately choosing cra43, leading to the reduced ODE: duk - -15
whose solution is: uy
w tc1sk)
Using the above result, we conclude that a; = (kk-)) and mı. f= 0k-- thus completing the convergence analysis. Although. we retrospectively chose the best learning rates 3k. 7> = O(k appendix that
for the presentation simplifications. But we have developed a general framework gives the rates for different possible step-sizes schedules.
Additionally, the result below shows that our critic error follows O(k-$), 5),, as compared to the Okk-1) 11) rate achieved in Chen and Zhao 2024).

---

Corollary 4.5. The critic enoor decreases similar to the actor enor
5
C16 + C17k
Proof. From Lemma 4.2
wc have
+1 S (1
2x) + C + comh + 2
Constant
Definition
Remark
J* E RR
J
Return at iterate
A E ERSA A
A T
Advantage value at iterate k:
Qh RSSA
Q
Q-value at iterate k
de ERS
T
Occupation measure at iterate
Og ER
E|J - JMl
out-optimality at iterate &
Z4 ER
V EE Q+1
Critic mean squared error at iterate k
ER
V V
Expected squared norm of the return at iterate k
26 e R
ak + #
Lyapunov value at iterate
Ug E
dus Solution to the ODE dk
C15
tess
G E IR
Place holder constants
See appendix
Table 2:
Definitions of cseful constants: Iterate k generated from Algorithm]
5
Discussion
We establish the global convergence of actor-critic algorithms with a significantly improved sample complexity of Ole 3) for obtaining e-close global optimal policy, compared to the existing rate of O derived from O ()) complexity for e-close stationary policy Chen and Zhao (2024). This brings us closer to the lower bound complexity of ((r-2) for reinforcement learning Auer al. (2008). The framework we propose is quite general and could potentially be extended to other settings, such average reward, function approximation, or Markovian noise. We leave these extensions for future work.
Moreover, this framework for addressing the two-time-scale coupling, combined with our novel and elegant methodology for bounding the recursions, can serve as a foundation for analyzing other two-time-scale algorithms.
Can we improve the complexity further? Our work proposes a learning rate schedule for both the critic and actor, decaying as k with iteration k which we believe through our investigation, achieves the optimal sample complexity of O(E-3) that these recursions can possible yield. Conse- quently, we need to shift our approach in deriving these recursions for improvement in the sample complexity. All prior approaches, including our own, focus on bounding the variance of the critic error /BII - 12. However, for the analysis of the actor's recursion, suffices to bound the bias |Q TE I]. Through careful investigation, we have come to believe that our current analysis, which relies variance bounds, has reached the best possible sample complexity limit of O

---

In contrast, an analysis based on bias has the potential to achieve further improvements, possibly reducing the complexity to the theoretical lower bound of O(E ?).
key insight lies in the fundamental difference between variance and bias: even for a fixed policy, variance remains non-zero, whereas bias vanishes. Specifically, current variance-based approaches necessitate diminishing learning rates for both the actor and the critic to ensure decreasing variance. In contrast, the bias term can tend zero even with a constant critic learning rate, requiring only diminishing learning rate for the actor. This observation suggests that focusing on bias may be more promising direction, but it also presents significant analytical challenges that remain unexplored.
In summary, we hypothesize that the current sample complexity of O(e could be improved to ((c-3) by focusing on bias rather than variance. This shift in focus may allow for constant (or very slowly decaying) critic step size, only requiring diminishing actor step size. In addition, we believe new methodology for solving recursions may play a crucial role in unlocking these research directions and opportunities.
Extension to continuous spaces. Our analysis is limited to the tabular setting and does not extend to large or continuous state spaces (e.g., robotics) due to the vS dependence in the Gradient Dominant Lemma (GDL) 2.1 Intuitively, vS reflects the diameter of the policy space (max, xx π x (|2). which could be replaced by parameter space diameter (max,, e 0 0' 22))2), in function approximation. This extencion directly enables the non-tabular versions of the exact gradient convergence results in Xiao 2022);; Mei et al. (2022) and consequently our actor-critic complexity results, with minor modifications in the current analysis.
Using multiple samples for critic estimation. While many double-loop actor-critic methods use (too) many critic samples per actor update, our work takes the opposite extreme- only one. Exploring whether an optimal trade-off exists between these two extremes is an interesting future direction.
Re-use of samples. We believe that re-using samples could reduce the total number of new samples needed to below (). This direction is particularly interesting for bridging offline and online RL, which we leave for future work.
Acknowledgments and Disclosure of Funding
This research was partially supported by Israel PBC- VATAT, by the Technion Artificial Intelligent
Hub (Tech.Al) and by the Israel Science Foundation (grant No. 447/20).
Additionally, part of this work supported by the Israel Science Foundation (grant No. 3019/24).
References
Agarwal, A., Kakade, S. M.. Lee, J. D., and Mahajan, G. (2020). On the theory of policy gradient methods: Optimality, approximation, and distribution shift.
Agrawal, P. and Agrawal. S. (2024). Optimistic q-learning for average reward and episodic reinforee- ment learning. arXiv preprint arXiv:2407.133. 13743..
Agrawal, P., Agrawal, S., and Azati, (2025). Q-learning with posterior sampling. arXiv preprint arXiv:2506..009/7
Amari, (1998). Natural gradient works efficiently in learning. Neural Computation, 10:251-276.
Auer, P., Jaksch, T., and Ortner, R. (2008). Near-optimal regret bounds for reinforcement learning. In Koller, D., Schuurmans, D., Bengio, Y., and Bottou, I.,, editors, Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc.
Azar, M. G., Oshand, I., and Munos, (2017). Minimax regret bounds for reinforcement learning. In Precup, D. and Teh, Y. W., editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 263-272, PMLR
Bagnell, J. A. and Schneider, J. (2003). Covariant policy search.
10

---

Baxter, J. and Bartlett, P. L. (2001). Infinite-horizon policy-gradiene gradient estimation. journal of artificial intelligence research, 15:319-350.
Bertsekas, D. P. (2007). Dynamic Programming and Optimal Control, Vol. II. Athena Scientific, 3rd edition.
Bhandari, J. and Russo, D. (2024). Global optimality guarantees for policy gradient methods. Operations Research.
Bhatnagar, S., Sutton, R. S., Ghavamzadeh, M., and Lee, M. (2009). Natural actor-critic algorithms. Automatica,
Borkar, V. S. (2022). Stochastic Approximation: Dynamical Systems Viewpoint. Hindustan Book Agency.
Castro, D. D. and Meir, R. (2009). A convergent online single time scale actor critic algorithm.
Chen, T., Sun, Y., and Yin, W. (2021). Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. In Ranzato, M., Beygelzimer, A., Dauphin, Liang, P., and Vaughan, J. W., editors, Advances in Neural Information Processing Systems, volume 34, pages 25294-222222 -23307. Curran Associates, Inc.
Chen, X., Duan, J., Liang, Y., and Zhao, L. (2023). Global convergence of two-timescale actor-critic for solving linear quadratic regulator.
Chen, X. and Zhao, L. (2024). Finite-time analysis of single-timescale actor-critic. Advances in Neural Information Processing Systems, 36.
Ganesh, S., Mondal, W. U., and Aggarwal, V. (2024). Order-optimal global convergence for average reward reinforcement learning actor-critic approach.
Gaur, M., Bedi, A., Wang, D., and Aggarwal, V. (2024). Closing the gap: Achieving global conver- gence (Last iterate) of actor-critic under Markovian sampling with neural network parametrization. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F,, editors, Proceedings of the 41st International Conference Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 15153-15179. PMLR.
Hong, M., Wai, H.-T., Wang, Z., and Yang, Z. (2022). A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic.
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. (2018). Is q-learning provably efficient? Advances in neural information processing systems, 31.
Kakade, S. (2001). A natural policy gradient. volume 14, pages 1531-1538.
Konda, V. R. and Tsitsiklis, N. (1999), Actor-critic algorithms. Neural Information Processing Systems.
Kumar, H., Koppel, A., and Ribeiro, A. (2023). On the sample complexity of actor-critic method for reinforcement learning with function approximation.
Kumar, N., Agrawal, P., Levy, K. Y., and Mannor, S. (2024). Policy gradient with tree search (PGTS) in reinforcement learning evades local maxima. In The Second Tiny Papers Track at ICLR 2024.
Liu, J., Li, W., and Wei, K. (2024a). Elementary analysis of policy gradient methods.
Liu, J., Li, W., and Wei, K. (2024b). Projected policy gradient converges in a finite number of iterations.
Mei, J., Xiao, C., Szepesvari, C., and Schuurmans, (2020). On the global convergence rates of softmax policy gradient methods. In III, H. D. and Singh, A., editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6829- PMLR.

---

Mei, J., Xiao, C.. Szepesvari, C., and Schuurmans, D. (2022). On the global convergence rates of softmax policy gradient methods.
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D., Legg. S., and Hassabis, D. (2015). Human-level control through deep reinforcement learning. Nature, 518(7540):529-535
Olshevsky, A. and Gharesifard, B. (2023). A small gain analysis of single timescale actor critic.
OpenAl, Akkaya, I., Andrychowicz. M., Chociej, M., Litwin, M., McGrew, B., Petron, A., Paino, A., Plappert, M., Powell, G., Ribas, R., Schneider, J., Tezak, N., Tworek, J., Welinder, P., Weng. L., Yuan, Q. Zaremba, W., and Zhang, L. (2019). Solving rubik's s cube with robot hand.
Peters, J. and Schaal, S. (2008). Natural actor-critic. Neuroccmputting, 71:1180-111 110-890-
Puterman, M. L. (1994). Markov decision processes: Discrete stochastic dynamic programming. In Wiley Series in Probability and Statistics.
Schrittwieser, J., Antonoglou, I., Hubert, T., Simonyan, K., Sifre. L.., Schmitt, S., Guez, A., Lockhart, E., Hassabis, D., Graepel, T., Lillicrap, T., and Silver, D. (2020). Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839):604-619)
Schulman, J., Chen, X., and Abbeel, P. (2017). Equivalence between policy gradients and soft q-learning.
Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. (2015). Trust region policy optimiza- tion. In International conference on machine learning, pages 1889-1897. PMLR.
Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., Chen, Y., Lillicrap. T. P., Hui, F., Sifre, L., van den Driessche, G., Graepel, T., and Hassabis, D. (2017). Mastering the game of go without human knowledge. Nat., 55007676):354-35,,
Sutton, R. and Barto, A. G. (2018). Reinforcement Learning: An Introduction. The MIT Press, second edition.
Sutton, R. S., McAllester, D. A., Singh, S. P., Mansour, Y., et al. (1999). Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, volume 99, pages 1057-1063. Citeseer.
Wang, I.,, Cai, Q. Yang, Z., and Wang, 7. (2019). Neural policy gradient methods: Global optimality and rates of convergence.
Wang, Q., Ho, C. P., and Petrik, M. (2022). On the convergence of policy gradient in robust mdps.
Williams, R. J. (1992). Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine learning, 8:229-256.
Wu, Y., Zhang, W. Xu, P., and Gu, Q. (2022). A finite time analysis of two time-scale actor critic methods.
Xiao, L. (2022). On the convergence rates of policy gradient methods.
Xu, P., Gao, F. and Gu, Q. (2020a). An improved convergence analysis of stochastic variance-reduced policy gradient. In Uncertainty in Artificial Intelligence, pages 541-551 PMLR.
Xu, T., Wang, Z., and Liang, Y. (2020b). Non-asymptotic convergence analysis of two time-scale (natural) actor-critic algorithms.
Yang, Z.,, Chen, Y., Hong, M., and Wang, Z. (2019). On the global convergence of actor-critic: A case for linear quadratic regulator with ergodic cost.
Yuan, R., Gower, R. M., and Lazaric, A. (2022). general sample complexity analysis of vanilla policy gradient.
Zhang, K., Koppel, A., Zhu, H., and Başar, (2020). Global convergence of policy gradient methods to (almost) locally optimal policies.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Claim of the paper is theoretical improvement of the sample complexity, highlited abstract and in the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Yes, our approach requires sufficient exploration Assumption work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification:
Yes, assumption in the main text and the proof in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper is purely theoretical in nature.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer:
[NA]
Justification:
The paper is purely theoretical in nature.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
coiiiooooolcyyll for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppp.ccppulli//uuuii wwwtc//ggue////eeeeceoocc CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper is purely theoretical in nature.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper is purely theoretical in nature.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
15

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper is purely theoretical in nature.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /tte::://euuis...eeee cwterrissccppuuuu hwtpp/ubiic/cccccccuueeeeeeeeeee
Answer: [Yes]
Justification: The paper is purely mathematical, we don't see any ethical concern.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is purely theoretical in nature.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
16

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper is purely theoretical in nature.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper is purely theoretical in nature.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppswppteeeee www.rrewwthhhe....c. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
17

---

Answer: [NA]
Justification:
The paper is purely theoretical in nature.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper is purely theoretical in nature.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper is purely theoretical in nature.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [Yes]
18

---

Justification:
LLM was used only for grammer, par par-phrasing and proper sentencing.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to LLM policy hettap///aaaarrssscc////o/eereee for what should or should not be described.
19

---

Contents
1
Introduction
Related works
2
Preliminaries
3
Main
4
Convergence Analysis
5
Discussion
Supporting Results
20
Sufficient Exploration Assumption 3.1
20
A.2
Local Convergence to Global Convergence: Proof of Proposition
3.2
21
B Deriving Recursions
22
Useful Constants
22
Actor Recursion: Proof of Lemma 4.1
24
B.3 GDL Recursion: Proof of Lemma 4.3
25
Critic Recursion: Proof of Lemma
26
Solving Recursions
28
Proof of Lemma
28
C.2 Proof of main theorem
30
D Numerical Simulations
31
A Supporting Results
A.1 On Sufficient Exploration Assumption
3.1
Lemma A.1. Under the Assumption 3.1 the update rule 2 converges as
|EQx Q7 > a IBI 17
where a /
x 2
taking Bx
Proof. From Proposition A.3 we have |EQx+] Q=1 aal - Q=I1, from which the result follows.
We define Pa((s', u'), (s, P ((d()s and D ((s', ((s',a') = (s)
(1 - 7) E 7th (P))
Proposition A.2. Cy max=,Q
(T-
+1+
20

---

Proof.
(5)
< || +
(as Σ (B,(( =
(6)
1QQ11 +7
Σ (dis,
< ||Q1 +7
(8)
S 11 +
Σ (d(s,a) (Pss((((
99)
|| +
Σ [(dssa))PPa((((ee)))
(10)
(1 (1+7))Q1)
(11)
Proposition A.3. For any policy n, given - 3D= -
Q]. we have
X2
- < 1- 2
11Q - -Q112.
Proof.
U D
R (I - 7P=)Q]
(12)
= D
( -P=0" - -I--
(using === -
(13)
= D"
(I- QQ -Q)
(14)
Lets look
1 1Q - 2 8 -00T Q - BUI
(definition of T = Q+
= ||Q" - Q11 1111 - - QU
$ !|Q" - Q11 + 1/11 - Q Q11,,
(from Assumption 3.1
< (1 + 2/8² - 2B Q12
(from Proposition A.2
X²
A (taking B 2
S (1 )1QQ= - -Q12
2
A.2 Local Convergence to Global Convergence: Proof of Proposition 3.2
Proposition A.4. If E < O(k- then J - EJ < OK-
Proof. From Gradient Domination Lemma 2.1 and Jensen's inequality, we have
V E
J Jb
[ J [--EJ]
E2J =E-=
SCP
Hence F* < (k--)) then [ [ E.
2 < O(k-b) -)), implying J" E.Jx < 2).
0
21

---

B Deriving Recursions
Notations.
Recall that J J AA = A Q* = = d d= a = J
v V 1 2 = / 2x - Q=12 are used as shorthands. Further Qu.AA are iterates from Algorithm and 1, E {0. 11.5 x A is indicator for (sk: ax) in the Algorithm We refer Hadamard product by o, defined as (a @ (1) a(i)b(i).
Constant
Definition
Remark
Sufficient Exploration constant
L
8 (1-7)3
Smoothness constant
Cy
VSCCL
GDL constant
Li =2
T0 -T 11 1 Li |0 - 0&1
Lipschitz constant of policy w.r.t. 0
0q = (1-7)²
2/SA
11Q - Qu+11| S cG
Lipschitz constant, see Proposition B.3
Cu S 1-
|ux1 S cu
Proposition B.1
F7 8/54
11Qt QK+11 (0x+1 lI0 128100+ 0x112
Smoothness of Q, Proposition B.6
2457 (1-7)
max - Q+11 c=
Upper bound on 2k. see Proposition B.5
C3 7
8.
2(1 2(1-
95.22
Actor-critic scale ratio
2 + (1-7)*
4L.
+ 20 + 213a.
(1-7)
8185² 4 (1-
7 min
2Aca
ODE constant
DAS SCP, 4(1 (1-7))1
4(1
Table 3: Constants
In this section, we derive the following recursions:
T]k
2 +
27m
4L
a S 0k
=k +
1
(1 (1-7)-
0% S Cgl/k
2
27/5A
+ (1 - 2A +22, 3222+222 22
(1 7)
(1 - 73
where the constants described in Table B
B.1 Useful Constants
The constants appears in upcoming sub-sections while deriving and solving the recursions. Reader may skip and come back this subsection later. Proposition B.1.
R(s,a) + +~Qu(d,a') - Qu(s,a)) 1-7
3
Co =
max 110 , ES E
22

---

Proof.
Qu(s,a)] - [R(s,)) a)] + + + (Qx(s,a)
(15)
S 1 - - 1 --
(16)
Proposition B.2. [Lipschitz constant of value function]
VA
- - 10 S (1 11-79 7)4 nh-
Proof.
||u 2x 1100 S - R + 7(px - pm )un J1o
(17)
I-9 [| RT
11 rll (PT p )uT 11o0).
(18)
|| n,lli + | Ralll
max
(19)
1-? ?
1
1 nz|li
(20)
(1 7)²
VA
VA
< max
2(1 7/2 (s)(ss -((s)ll
(as ([(()) x(s)ol12 s
2 110 (())l1)
(21)
Hence
VA
11 - 1011000 S
(1 - 7)) Th.
as |10++1 - 0x =
2np [1-
Proposition B.3.
11 2 S co
2/33 where Gq (1-7)²
Proposition B.4.
11Q" @ || + PP R pPottlll
(22)
Pu & Py 100
(23)
~11l0 - 11
(24)
VĀYK
S 7 (1 7)
(from Proposition B.2
(25)
Proposition B.5,
max max|IQu -Q+11 S Cz.
where c 2v3A
Proof.
1Q: - Q S VSAlQ: -011 < 2/5A
(26)
(1-9)*
23

---

Proposition B.6.
pQ da²
87
15 (1 - 7/3
and
4VSA
110 - -Qht + (0+11 - -8x)11 v (1-7)² 110x+1 0x
Proof.
d da?
- |=1
d²
R(s,a) + Σ (() )1
(27)
da²
d²
2 Σ
P(s'|s, ())
u (s')
(28)
da?
=
(29)
Hence,
110 - Qht11= (0=+1 - -wall S SSAI Qht1 + VQ= (0k+1 0x)
(30)
S v SA 7
|102+1 0xl1
(31)
2
4VSA
7)3 |10x+1 0x112.
(32)
(1 - 7)3
Proposition B.7.
8185² A Co - (1 21-7)12
Proof. From definition, we have
4L
2L9cz
= 2c +
+
20 +
(33)
(1 - 7)4
(1 7)
72
32
8SA2
32S
5 2(1 77)22
+
(as L
(34)
(1- 7
(1-7)* 7)
(1- (1-7)8²
(1 7-)
81852 A"
- (1 7112
(35)
B.2 Actor Recursion: Proof of Lemma 4.1
Lemma B.8 (Sufficient Increase Lemma). Let Og be the iterate obtained Algorithm 7 Then,
E| JM
7 1 [1VJ* + (VJh, d @ (Aa
mh E
-A*)) (1 - 7)
2LTT/
where L 8
(I-7)T
Proof.
From the smoothness of the return, we have
L -
F [ - J
J>
F
( Jh
Okt1
0k)
$10k+1 0xll3)
E
T
A
3 1x)
Lo
Af
(from update rule Algorithm
2(1 7)²
2T
2
E
A+)
(as (sk, 0x) d o and || -
1 7
(1 -)
I--
>
7
E
||
+ ( th 3 (Ax A)
2LTT
(as J = dx o A*).
1 7
(1-7)3
24

---

Proposition B.9. We have
- 1h1) / ElI F FIQu Q+12 E (J. d @ (Ac-AAA
Proof. We have
v Jk a (Ax A²)) $ [|V.J*Illa* @ (Ax Al
(from Cauchy inequlaity)
(36)
V [1|(A - 11o0s
(as "(a,bi) S (max at E b
(37)
<|V 10, (as 1= = ||d 2 ||a (2)
(38)
(39)
Additionally, from definition, we have
as(s,a) as) = (2,(s,a) E -=lalo)n((s.0)-@' + Σ r(als) a)l (40)
$ <1Q((s,a) - (s) + E x(als)(Q(ss.)) E T(als)Qu(s,a))
(Triangle inequality)
(41)
$ $1Q0x - 1o + Σ ((lss)) - Qu(s,a)),
(42)
$ 2 1=1
(43)
Putting this back, we get
E' (at A dt (As A s |2E [ [I -f
(44)
$ 2E [[] 11| - 1],
(as || 2 1o0))
(45)
s 2/ 1 F Q*
(from Cauchy (F(x, w))² s F||x/|/
(46)
Lemma B.10. [Actor Recursion] We have
2TTT 2y
(1 7)3 ].
ag ab+t 1 7
where L
8 (1-ry33
Proof.
From Sufficient Increase Lemma B.8 we have
El - JMl スー 7k
|| JvJ dh o (AR-A
2.LTTI
(1 7733
El| -
El (VJ d (Ax At)i (1 - 73) ).
2LT
(as Ela] 2 -[(aa)
2L11
2
EE 2 EI
BlIQu 111 - (1 7)3
(from Lemma B.9
1
B.3
GDL Recursion: Proof of Lemma 433
Proposition B.11. [Gradient Domination] We have
VSCPL
ag <
yk
c
25

---

Proof. From GDL, we have
J - J VSC |
(47)
E[J - JJy 1 VSCTL E
(48)
VSCFL E 1
(49)
where the last inequality comes from the Jensen's inequality (E[z))² - El>*].
B.4 Critic Recursion: Proof of Lemma 4.2
Recall that in the Algorithm I we have the following updates: (8,a) ~ do 8 ~ (=),,
T& (+(ss, and
QK+1(S, +
where
[T641 T&l
2L (1~1)a Te. ak O. and U241 = R(s,a) +
-
Lemma B.12 (Critic Recursion). In Algorithm] 7 the critic ervor follows the following recursion
21 (1 - 7)a Th
2YV
24 S (1- 2A 22, +2 +
(1 - 7)3 2k
Proof. We have
= E Ox + +1U0++1 - Qh+1 I|: (from update rule of Qs)
- 112 -
11 1|2 (plus-minus Q+)
=E Qk Qt + -.Uk++1 + Q² - Q++1
=E (109 - 0²12 + 13 + 11@ - 1122 + (3 -
+ - Q³ U2+1) + 2(u - Q² Q² - x ))
(expansion of (a+ b + c)
SF (11 23x 11 - 0²122 + B U 2| + 11 - 1 + 23
Q
+2 -² - -Q++1)
(using sufficient exploration assumption)
<E' ((1 (1))2 - Q²11² + U + 2
- 11 2 +2
Q*, 1* -4+1))
(using |al| + ||b]] 2 b)a
(1-11-8AA <E (11 -28xA)llQx (11-2BAA]IQQ= - Q* 112 + 288c8 + 2n2 + 2(Qu -², Q Q
(as 1QQ - 11 S c and || cc)
<E (11 (1-22a - 0²1 + (1 -1-7) 7
1833
+ 2 + 2(Qu - ,², - Qbt2)) )
(from Proposition B.1
26

---

Now, we only focus on
BiQu - 0r, Q - Q
<B(Qn - 0+, Q Qh + (Q* + E(Qu Q², (0+10 0s)),
(plus-minus)
<
1Q: Q" 111@" - Qhtt1
- -x]1 (Qx - Q², (0 -0b)) ].
(Cauchy Schwartz)
ΣE
1B @*1110A++ - 0x11 (Qx - Ør VQ* 8k))
(smoothness of Q", see Table 3)
2
2 2n
<B
11Qu Q-11
(Qx Q², V0 (1s 3 As))
(from Algorithm I
2
<
11Qu 2²1 +
(Qx Q², VQ (d o Ax))
(Conditional expectation, (sk, (x) d")
<
2
2
11Qu Q11
U q 1Q 1111 A+)l
(Cauchy Schwartz)
7)
2L2n
B1QQu Q+12
1
BIIQ= Q²12 V @ As)I
(Jensen and Cauchy inequalities) )
7)
1 1-
2L
27v SAm
Bl 2
ElIQ= 1012--Qh12-0 EI
(using Proposition B.13
7171
(1-7)3
To summarize, we have the following recursion:
2L
24VSA
+1 S (1 2x +22 +2e +
(1 7) Ti
(1 7)3 Tk
Proposition B.13.
(d" o Ab) < 4,2SA²
(1 (1- /
Proof. From definition, we have
(=( = R(s, + Σ ())
(50)
Q" (s,a) ? Σ p()'(s, d0 a") o
(51)
d0( a²)
P(s ad (s" (s")A (s" (s". a²).
(52)
7
27

---

This implies that
IIQ (dt
An)ll= E
d3,(
d' (f", (1)3)))))))))))
(53)
d0 d0(s",
Σ
(putting back the value
(1 - 7)
5,0
a"
(54)
72 (1 7)3
(
(taking absolute values)
5" .a"
(55)
(" (s",""))) ,a')))
(56)
(1 71-
8" '8'
SA2
Σ a)d11s (d"(" (d'("","'AA"("
(57)
(1 (1-7)a
(from Jensen, as Σ (( = A)
(58)
SA2
$ (1 71) 8".a"
Σ (d(("".0")4"(("""")
(as (())).)))
(59)
SA2 (1 71- /.p.
(60)
C Solving Recursions
In this section, we solve the recursions derived above.
C.1 Proof of Lemma
Lemma C.1. The following recursions
T]
2 7
4Lab
0k+1 S 0k
2/ +
=k +
1
(1 71
Og Cgllk
2L9
2/V
22 S (1 - -1A3x)== + +22,82 + +2 2 +
The zk +
(1 7)
(1 7/3
implies
S. 3 (max(c,,2cfff 267 )2((2))
(²+
) $ ( maxfc
1 c/ 200 } )
21:
1
23:
0g
with constants ag, Ct2 02 defined in Table
3
28

---

Proof. Adding the first and last recursions, and using 24 S from Table 3. we get
1&+1 + 2k+1
<az + 2/
MAVE
2A3x2 + 22 ( ((I-))) + +22g + 2L3c,
(1- )
n
22V/A
+
2
1-7
(1 (1-
7)3
1-7
< ag + 2/
2
21 + +222 ( (1 (1-7)1
4L
+ +22g + (1-
2Liee
)
1/6
2 3/5A
+
(1 - 7)3 7kl
(simplifying)
1 7
yk
3/SA
I ag + 2/ 1,
+ 22C
(1 - -7)3 2
1 7
4L
2L3cz
Bx = cz)
+
26 2
+
+ +20g +
11k
(as
u
(1 - 7)
71-
S 0%
+
2/
2
1jk
2
(1 7)
2
+ 22cØ22 ]
2
(1 - 7)
uk
+ 2\c33* 2
(1- Uk 2k
(1 - 7)
6VSA
+G 2
(plus-minus)
0kk
+
T]k:
2
+ 2Xc32
-Tps [V (1 (1) (1-
2XcB
3VSA
2k C
(as b 2 2v
2
(1 77)
.2242 2(1-535
Uas cp
aq.
+ 2/
2
T]k
yk
2
+ 22cge?
(
22)2
+o 2
(divide-multiply)
2
(1 7)
C2
0g
+ 24
1/k
y
2
+ 2Acgo
2 to
Fk (as C₁
< by defn of cz, see Table 3
2
(1
7)
C2
< a4 + 2
2
1]
of
2AC3
+Gn 2
(using ak S (g
2
cg(1
7)
1
2d03 }
$ (4 + 2x 27
a + 2k
(as c : 4
min
2g( - 7)
cz
2
S Sag + 2 GTT
(gs z
th
(using (a + b)² < 2(a² + 121).
Taking uh= ak + =2, Wk
/m, the above recursion is of the form:
u4 S ux - -onk uz +
2 2c
(61)
-
Taking 01 = ct and 02 = max (cy, 2c to ensure ag = ci
C2
un
S 22- in Lemma
C.2 we get
uk < G -3 (max(cn, 20 )²
1
(62)
T
+
2k
a
Note that a < 2k as 2 2 0, yielding the desired result.
Lemma C.2. !ODE domination for Recursion] Given da. - a ag =(
I
+2k
and
o8
?i = c cg of the recursion,
uk+1 I up
c17744 +
2 c2T
-- un 2-
then uk Sc c2 as for all k 2 0. where ag
29

---

Proof. Let ug c/( - ui and as = =f VTk- Then, multiplying both sides with of
C2 we get
q } ux+1 S c2 up ct cf t ( (of _
2 -
)² + 2221111
(63)
= Ux+1 S up - u + 2
(64)
Now let fx(V)) = V - ozzv² and assume, V Or2, then
1
Pk+1 S fe((K)) +
(65)
2
S Se((x)
+
4
(as [a(v) is increasing for S 20
and us S on
S
201
1
2
S
201
7
(66)
1
= 0%
(putting the value back of f)
(67)
2
x+1
0k
a
(dummy integral)
(68)
0%
a
dx,
(as ag is decreasing)
(69)
k+1
< al..
dr,
4
(dummy integral)
(70)
2
k+1
da
(as dag dr
ak
dx, (basic calculus).
a 1
(71)
dx
< 01++11
(72)
From induction arguments, get Vs ag for all k 2 satisfied. In other words.
0 given the base condition 1o I Ogg is
2 b S az =
(73)
+ 2k
C.2 Proof of main theorem
Theorem C.3 (Main Result). For step size 7k = O(k - 3) and Bk = C3M in Algorithm
1
we have
T-EJaa S max {
s A4 PL
A$
1
vk 0.
c² (
1 (1 7)
where C' is some numerical constant.
Proof. From Lemma C.1 we have
J - T as < - ( (max(cn 26 (g) )²(
ag 2k
3 c mo}
< C max C
(re-arranging, ap 0, C1 numerical constant).
Putting the values from Table
3 we have
105 A
(1 (1-
30

---

and
3
1
c²
9YS
9
4(1 - 7)
min
SC
4(1 7)2
(74)
S C
28 (1 7)
23 (1 7) max
PL
(75)
3
Hence, we get
$ 9 cp s C1
5#
max
SiC
PL
(1 (1-7) 7)
}
(76)
(1 7))
A3s
C3
S (1
A
}
S C max
(77)
cdt
7) 16
A3 7)
and Ug (117)))² hence the complexity
A PL (1
A
{
0% Σ C1 max
A
where C2 is some numerical constant. For comparision, the iteration complexity for the exact gradient case is ( (1-)))))) as shown in Theorem Mei et al. 2020).
SC3,
Notably, actor-critic dependence little better in mis mis-match coefficient C'LL (yes, we double checked), and only slightly expensive state space and horizon.
D Numerical Simulations
This section numerically illustrate with convergence rate of single-time-scale Algorithm with different step size schedule. All MDPs have randomly generated transition kernel and reward function, with codes available at https:: / //w::////ooommussmm/ 4open. acience/r/AC. C43E/ For simplicity, the samples are generated uniformly instead discounted occupation measure.
Figure illustrates that the learning rate 7Js: = Bg = - has the best performance. Notably, slow decaying learning rates such as 7 = By 0.01 k- 3, -- have better performance in the starting,
and eventually they surpassed by 17x 8x = 3. In addition, 7 = 3 = k- has the worst performance.
31

---

Return the Current Policy for Different Learning Rates
0.2
112
2/3
0.58
0.50
052
8.0
20000
20000
30000
00000
50000
lleration (2100)
Figure Convergence Rate Algorithm 1 on random MDP with state space =50, action space learning rate 7 8x k-a
Return the Current Policy Different Learning Rates
0.60
20000
46000
60000
00000
200000
Tee siiiion (x100)
Figure 3: Convergence Rate of Algorithm I on random MDP with state space =5, action space learning rate 107p = .g. k
32

---

Return the Current Policy for Different Learning Rates
122
2/3
0.00
0.50
3000
2000
2000
4000
5000
He ootion (x100)
Figure 4: Convergence Rate of Algorithm learning rate mh 3B a
1 on random MDP with state space =20, action space
33


Reviews:
[{"review_id": "SxAW80apGL", "reviewer": "Reviewer_FxH5", "summary": "This paper studies the global convergence of single-timescale actor-critic algorithms in reinforcement learning, for infinite-horizon, discounted Markov Decision Processes  with finite state and actions spaces. In a single-timescale setting, both the actor and critic are updated simultaneously using the same step-size schedule, which contrasts with the more commonly analyzed two-timescale methods that separate actor and critic updates across different learning rates or loops. This makes the analysis more challenging but brings it closer to the practically implemented. The paper achieves a sample complexity of $\\mathcal{O}(\\epsilon^{-3})$ which matches that of state of the art results but does so with less assumptions as compared to other works.", "questions": "My questions are related to the weaknesses I pointed out. \n1. Is there any path to extend the analyses to infinite state/action spaces?\n2. What challenges do you anticipate if any in extending your analysis to bilevel RL setup?", "limitations": "Limitations are that the analysis is restricted to tabular state/action setup.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths \n1. The paper proves that a single-timescale AC algorithm achieves an ϵ-optimal policy with a sample complexity of $\\epsilon^{-3}$. This improves upon the previous best-known  $\\epsilon^{-4}$ result for such algorithms.\n2. The paper achieves this under single timescale setup which makes the setup more realistic and applicable to real world applications.\n3. The paper does not require the extra memory requirements for works such as Gaur et. al 2024. Making it more efficient.\n4. Achieves global convergence using Lyapunov related analyses. Improving upon previous results which only got local convergence.\n\nWeaknesses.\n1. The paper is restricted to tabular setups. This means not applicable to environments such as robotics.\n2. In certain situations, using multiple samples to estimate the critic can be beneficial such as DDPG. A discussion of these would be good.\n3. The authors claim that the analysis may be extended to bilvel RL setup. More discussion on that would be good.", "was_revised": true, "final_justification": "I have gone over the replies of the reviewers. They have answered the questions to my satisfaction, and I maintain my positive score.", "rebuttal": "We thank the reviewer for the encouranging feedback. We appreciate the time and effort spent on reviewing this paper. We are glad that the reviewer finds that the paper provides state-of-the-art complexity result to a challenging and more practical single-time scale algorithm.\n\nWe answer the questions below.\n\n ***Q1) The paper is restricted to tabular setups. This means not applicable to environments such as robotics.***\n > The reviewer is correct in noting that the current setting is not directly applicable to large-state problems such as those in robotics. The main limitation lies in the square-root state dependence of Gradient Dominant Lemma (GDL) 2.1. However, we agree that extending this lemma to continuous state spaces—potentially through embedding or an approximate version—is a promising direction for future research. Such an extension would also facilitate a non-tabular generalization of the exact gradient convergence results in Xiao et al. (2022) and Mei et al. (2022). As a result, our actor-critic complexity bounds could be extended to the non-tabular setting, with minor modifications to account for function approximation errors and other approximations. We thank the reviewer for this insightful question, which we intend to pursue in future work.\n\n***Q2) In certain situations, using multiple samples to estimate the critic can be beneficial such as DDPG. A discussion of these would be good.***\n>We thank the reviewer for this insightful question. While many existing works on double-loop actor-critic methods rely on using a large number of critic updates per actor update, our work lies at the other extreme—using a single critic update per actor update. It is quite possible that the optimal balance lies somewhere between these two extremes, either generally or in specific contexts such as DDPG. We will include a discussion of this point in the final version and explore it further as part of our future work.\n\n\n***Q3) The authors claim that the analysis may be extended to bilvel RL setup. More discussion on that would be good.***\n>Our work proposes a high-level approach for tackling bi-level problems such as min-max optimization, robust MDPs, and two- (or multi-) agent reinforcement learning:\n\n>>**Step 1:** Formulate the interdependent recursions, as illustrated in Equation (3), for the relevant quantities.  \n>>**Step 2:** Identify a suitable Lyapunov function, as demonstrated in Line 274 — often the most creative and critical part of the analysis.  \n>>**Step 3:** Solve the Lyapunov recursion, as done in Lemma 4.4, to obtain the desired bound.\n\nLemma 4.4 can be extended to handle more general recursion structures , which we chose to omit for clarity. Additionally, we uncovered several useful insights during this process — for example, that such recursions often track the behavior of the corresponding ODE, and that appropriate learning rates can be chosen using a _power-matching_ technique.\n\nWe will be glad to include a dedicated section in the appendix (along with a more general ODE-tracking lemma) in the final version.\n\n***Q4) Is there any path to extend the analyses to infinite state/action spaces?***\n> As discussed in Q1, the key step in extending the analysis to infinite state-action spaces is to establish a Gradient Domination Lemma (either exact or approximate), since this is the only component that exhibits state dependence.\n\n> The rest of the analysis—such as applying a sufficient increase lemma under function approximation—is standard in the literature. One can derive the corresponding recursion and solve it with minor modifications to the existing framework.\n\n> Loosely speaking, the $\\sqrt{S}$ term in GDL Lemma 2.1 corresponds to the diameter of the policy space, i.e., $\\max_{\\pi, \\pi' \\in \\Pi} \\lVert \\pi - \\pi' \\rVert_2$. In the function approximation setting, it may be possible to replace this with the diameter of the parameter space, i.e., $\\max_{\\theta, \\theta' \\in \\Theta} \\lVert \\theta - \\theta' \\rVert_2$. However, this substitution requires careful investigation, which we leave for future work.\n\n***Q5) What challenges do you anticipate if any in extending your analysis to bilevel RL setup?***\n> We briefly outlined a possible approach for bi-level problems in Q3. We believe the first step—deriving the recursions—is likely to be straightforward, though potentially laborious. Identifying a suitable Lyapunov function, however, is likely the most challenging part. Once obtained, the recursion can be solved using techniques similar to our ODE tracking lemma.\n\n> That said, finding a Lyapunov function may not always be feasible or straightforward. Fortunately, it is possible to bypass this step by directly solving multiple recursions using an extended ODE tracking lemma. This would require applying the same methodology multiple times—essentially the same arguments used to prove the Lyapunov recursion. In fact, this was our original approach before we discovered the elegant Lyapunov function presented here.\n\n> We will gladly include a detailed section on this alternative route, along with the extended ODE tracking lemma, in the appendix of the final version."}, {"review_id": "WW1QbuTTFn", "reviewer": "Reviewer_EEab", "summary": "This paper studies the convergence of actor-critic algorithm, under the setting of infinite-horizon discounted MDPs. The paper considers single-timescale setting, where the actor and the critic are updated simultaneously. The paper develop a new analysis technique, which first modeling the evolution of the actor error and the critic error with a dynamic system. To bypass the difficulty incurred by the hard-to-estimate gradient norm term, the paper considers an Lyapunov term of the dynamic system. Analysis shows that the Lyapunov term is evolved according to a relative simple single-variable ODE. The solution to the ODE gives a sample complexity of $O(\\epsilon^{-3})$, which strictly improves the previous $O(\\epsilon^{-4})$ result.", "questions": "Here are my questions:\n\n1. How does the analysis techniques compared to the analysis in previous works and why previous analysis cannot achieve the rate obtained in this paper?\n\n2. Is there a sample-complexity lower bound for this kind of actor-critic algorithm?", "limitations": "The author discussed the limitations in the last section.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. This paper consider single-timescale actor-critic algorithm. Compared to two-timescale actor-critic, this setting is more practically relevant and hard-to-analysis.\n\n2. The result of this paper strictly improved upon the previous results, which is new to me.\n\n3. The technique introduced in this paper is also interesting to me. To overcome the difficulty in solving the dynamic system depicting the evolution of the errors, the paper consider the sum of actor and critic error and largely simplified the system. This technique might be inspiring to solve other similar problems.\n\nWeakness:\n\nI don't see any major weakness in this paper. Some part of the presentation are not clear enough. Here are some examples.\n\n1. The 2nd and 3rd row of Table 1 looks the same.\n\n2. In equation (3), the $z_k$ at the end of the first line seems redundant.\n\n3. The dimension of variables is obscure. Something like $A^k \\in \\mathbb{R}^{|S||A|}$ might make it clearer.\n\n4. Some references looks ill-formated. For example, it looks like that line 342-347 are referring to the same paper.", "was_revised": true, "final_justification": "I do not have major concerns about this paper and think that the results introduced by this paper is an important one", "rebuttal": "We thank the reviewer for the positive and thoughtful feedback.\n\nWe are glad that the reviewer finds our focus on the single-timescale actor-critic setting both practical and meaningful. We appreciate the recognition of our improved sample complexity and the Lyapunov-based analysis technique. We agree with the reviewer that this approach can inspire further work in similar settings.\n\n\n***Q1) The 2nd and 3rd row of Table 1 looks the same.***\n> Thank you for pointing this out. We will merge the two in the final version.\n\n***Q2) In equation (3), the $z_k$ at the end of the first line seems redundant.***\n> Thank you for noticing this. It is indeed a typo, and we will correct it in the final version.\n\n***Q3) The dimension of variables is obscure. Something like $A^k \\in \\mathbb{R}^{|S||A|}$ might make it clearer.***\n> Thank you for the suggestion. We will include the dimensions of all variables in the final version.\n\n***Q4) Some references looks ill-formated. For example, it looks like that line 342-347 are referring to the same paper.***\n> Thank you for pointing this out. We will fix it in the final version.\n\n***Q5) How does the analysis techniques compared to the analysis in previous works and why previous analysis cannot achieve the rate obtained in this paper?***\n\n> The main limitation of the previous analysis by Chen and Zhao [2024] is that they treat the policy optimization objective as a general smooth non-convex function. Moreover, they follow the standard approach of bounding the *average squared norm of the gradient*. Their analysis does not leverage the gradient domination structure, or if used, it is only plugged in at the end—leading to a suboptimal convergence rate.\n\n> In contrast, the core innovation of our work is to exploit this structure directly when analyzing the iteration-wise drift of the actor.\n\n> Leveraging this additional structure required us to develop a novel methodology for solving the interdependent recursions, which in turn led to stronger results.\n\n> In summary, our analysis is more tailored to reinforcement learning, as it effectively incorporates the gradient domination structure—unlike the standard smooth optimization techniques used in the prior work.\n\n***Q6) Is there a sample-complexity lower bound for this kind of actor-critic algorithm?***\n> The sample complexity lower bound for reinforcement learning is $O(\\epsilon^{-2})$, as shown by Auer et al. (2008). However, to the best of our knowledge, there is no known lower bound specifically for single-time-scale actor-critic algorithms. Nonetheless, it is widely believed that the same lower bound applies in this setting as well."}, {"review_id": "wxqe8X88vl", "reviewer": "Reviewer_ZGMW", "summary": "The paper considers the sample-complexity for the problem of finding a $\\varepsilon$-optimal policy for softmax-parameterised infinite-horizon discounted Markov decision processed. They focus on the sample-complexity’s dependence on $\\varepsilon$ and establish that a single-timescale actor-critic aglorithm achieves a sample-complexity of $O(\\varepsilon^{-3})$ improving upon the best known results of $O(\\varepsilon^{-4})$ from prior work. This is achieved by an analysis that directly bounds the sub-optimality gap (instead of convergence to stationary points) and combines recursions for the actor and the critic simultaneously (the Lyapunov term).", "questions": "- See weaknesses for some suggestions on improving presentation. This paper has interesting results but suffers from the quality of the presentation. If the presentation of the paper was improved, it would have a higher score.\n- In the  discussion following Lemma 4.1, it is not clear to me why the last term “accounts for the variance in the stochastic update of the policy” since in the analysis this term arises from the smoothness of the value and not from the stochasticity of the update ?\n- You mention that you believe that a bias analysis may lead to the optimal $O(\\varepsilon^{-2})$ sample-complexity. Do you believe this is achievable without any modification to the algorithm ? Is there perhaps a slight adaptation of the algorithm that could improve your variance analysis ?", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The problem considered is of practical relevance: the single-timescale version of actor-critic more closely resembles algorithms used in practice than the two-timescale version.\n- The sample-complexity of the single-timescale actor-critic algorithm is improved from $O(\\varepsilon^{-4})$ to $O(\\varepsilon^{-3})$.\n- The provided analysis and key idea is novel, fairly simple, insightful and general.\n- The work generally does a good job of presenting the setting and contextualising their results within prior work.\n\nWeaknesses:\n- The sample-complexity does not match the lower-bound whose dependence in $O(\\varepsilon^{-2})$. The dependence on quantities other than $\\varepsilon$ are ignored. In particular, the dependence on the effective horizon $1/(1-\\gamma)$ and the size of the state-action space $SA$, which are hidden within constants, appears like it could be quite poor. While I understand that it could be argued that until the optimal dependence on $\\varepsilon$ is achieved, the dependence on these other quantities is of secondary importance, having a discussion on the explicit dependence on these in the final bound would be helpful for the reader.\n- Presentation: the writing / clarity of presentation is below the standard expected. The appendix has quite a few repeated entries (one reference even appears three identical times), some references are missing their publication venues… etc. There are many typos and grammatical errors (e.g. l.70, l.78, l.81-84, l.266… etc). Table 4 referenced at l.242 does not exist or points to the wrong thing – I guess Table 2 was meant. At the top of page 7, $Q_k$ has not been formally defined - I guess it is the update in Algo 1 but then would be clearer to write in Algo 1 with this notation. In the Convergence Analysis section, it would be useful to have pointers to where the specific sub-results are proved in the appendix. Some of the discussions are a bit unclear / hard to follow. In particular, the discussion l.268-272 is not easy to understand.", "was_revised": true, "final_justification": "The work presents an interesting and significant set of results that I believe are worthy of acceptance. My main concern is the quality of presentation, which in the current version is below the standard expected. The authors have responded that they will improve this - it is hard to assess how much it will actually be improved. I recommend acceptance conditioned on substantial work being done to improve presentation quality.", "rebuttal": "We thank the reviewer for the encouraging reviews. We are glad that the reviewer finds key ideas and analysis to be novel, fairly simple, and insightful. We're also happy to hear that the presentation of the setting and positioning within prior work were clear.\n\n\n\n***Q1) The sample-complexity does not match the lower-bound whose dependence in $O(\\varepsilon^{-2}).$***\n> The reviewer is correct in noting that our $O(\\epsilon^{-3})$ complexity does not match the lower bound of $O(\\epsilon^{-2})$. However, our result significantly improves upon the existing complexity of $O(\\epsilon^{-4})$, thereby narrowing the gap. To the best of our knowledge, this represents the current state-of-the-art for single-time-scale actor-critic algorithms.\n\n***Q2) The dependence on quantities other than $\\varepsilon$ are ignored. In particular, the dependence on the effective horizon $1/(1-\\gamma)$ and the size of the state-action space $SA$, which are hidden within constants, appears like it could be quite poor.***\n> All prior works report complexity only in terms of $\\epsilon$, and we followed the same for consistency and clarity. Nonetheless, the sample complexity for our actor-critic algorithm is:\n>\n> $$\n> O\\left(\\frac{S^{4/3} A^{2/3} C_{PL}^{4/3}}{\\lambda^{2/3} (1 - \\gamma)^{16/3} \\, k^{1/3}}\\right).\n> $$\n>\n> For comparison, the iteration complexity for the exact gradient case is:\n>\n> $$\n> O\\left(\\frac{S \\, C_{PL}^2}{c^2 (1 - \\gamma)^6 \\, k}\\right),\n> $$\n>\n> as shown in Theorem 4 of Mei et al. (2022). We outline the high-level computation below:\n\n>> From Lemma C.1, we have:\n $$a_k \\leq c_l^{-\\frac{2}{3}}\\Bigm(\\max\\{c_\\eta, 2c_l^2u^3_0\\}\\Bigm)^{\\frac{1}{3}}\\Bigm(\\frac{1}{\\frac{1}{\\alpha^3_0}+ 2k}\\Bigm)^{\\frac{1}{3}}\n\\leq \\frac{\\max\\{2^{-\\frac{1}{3}}c_l^{-\\frac{2}{3}}c_\\eta^{\\frac{1}{3}}, u_0\\}}{ k^{\\frac{1}{3}}}.$$\n Substituting $c_l$ and $c_\\eta$ from Table 3:\n $$c_l^{-2/3} c_\\eta^{1/3} = O\\left( \\frac{S^{4/3} A^{2/3} C_{PL}^{4/3}}{c^{4/3} \\lambda^{2/3} (1 - \\gamma)^{16/3}} \\right), \\quad\n u_0 = O\\left( \\frac{S A}{(1 - \\gamma)^2} \\right). $$\n Hence, the overall complexity becomes:\n $$\n a_k \\leq C \\cdot \\frac{S^{4/3} A^{2/3} C_{PL}^{4/3}}{\\lambda^{2/3} (1 - \\gamma)^{16/3} \\, k^{1/3}},\n $$\n where $C$ is a numerical constant.\nAdditionally, using our ODE tracking method, the iteration complexity for the exact gradient case (as in Theorem 4 of Mei et al. 2022) can be improved to:\n $$ O\\left( \\frac{S \\, C_{PL}^2}{c^2 (1 - \\gamma)^3 \\, k} \\right). $$\n \n>Notably, the actor-critic complexity shows slightly *better* dependence on the mismatch coefficient $C_{PL}$ (we double-checked, decreasing step sizes improves the dependence on $C_{PL}$), and only slightly *worse* dependence on the state space size and discount horizon.  \n\n> We thank the reviewer for raising this important point and will include this discussion in the final version.\n\n***Q2) Presentation issues , typos, ... And Line 268-272 not clear.***\n> We appreciate the reviewer’s feedback on the presentation. We will address these presentation issues and revise the text to improve clarity.\n\n> Lines 268–272 highlight the challenge in ensuring a monotonic decrease in the critic error in Equation (3). Specifically, the gradient norm $y_k$ is *lower bounded* by $a_k$ due to the Gradient Domination Lemma (GDL). This lower bound on $y_k$ is useful for *upper bounding* $a_{k+1}$ in the actor recursion of Equation (3).\n\n> However, to *upper bound* the critic error $z_{k+1}^2$ in the critic recursion (also in Equation 3), we require an *upper bound* on $y_k$, which we do not have. This asymmetry presents a challenge in establishing a monotonic decrease in critic error.\n\n> We will revise this paragraph in the final version to make the reasoning clearer.\n\n***Q3) In the discussion following Lemma 4.1, it is not clear to me why the last term “accounts for the variance in the stochastic update of the policy” since in the analysis this term arises from the smoothness of the value and not from the stochasticity of the update ?***\n> Yes, the reviewer is correct in observing that Lemma 4.1 follows from the smoothness of the return function. However, upon closer inspection of its proof in Lemma B.1, the last term is:\n>\n> $$\n> c_3 \\eta_k^2 = \\frac{L}{2} \\, \\mathbb{E}[\\lVert \\theta_{k+1} - \\theta_k \\rVert^2],\n> $$\n>\n> which corresponds to the variance (more precisely, the second moment) of the update steps.  \n>\n> We thank the reviewer for noticing this subtle point. We will revise the text to state that the term “accounts for the variance (second moment) of the updates” in the final version.\n\n***Q4) You mention that you believe that a bias analysis may lead to the optimal $O(\\varepsilon^{-2})$ sample-complexity. Do you believe this is achievable without any modification to the algorithm ? Is there perhaps a slight adaptation of the algorithm that could improve your variance analysis ?***\n> This is indeed an intriguing question. Based on our recursion analysis, we believe that the current complexity is difficult to improve—our use of the ODE tracking method appears to be the most effective approach for solving the given recursion.\n\n> We also explored the use of batching, but it did not lead to an improvement in the overall complexity. However, we believe that if sample reuse were allowed, the total number of *new* samples required could potentially be reduced below the current $O(\\epsilon^{-3})$ bound.\n\n> This is a promising direction, particularly from the perspective of combining offline and online reinforcement learning. We consider this an interesting avenue for future research."}, {"review_id": "2Y96cae1de", "reviewer": "Reviewer_ZXNM", "summary": "The paper studies the standard actor-critic algorithm with the step sizes for the policy updates and value function updates on the same timescale, and shows that the algorithm's last iterate converges with rate $\\mathcal{O}(1/k^{1/3})$ (measured in the function value space). This is the best complexity derived so far in the literature.", "questions": "1) Can the authors clarify if I correctly understand the innovation of the paper in my comments above (in Strengths & Weaknesses)? Specifically, the limitation in prior works like Chen and Zhao [2024] is that they disregard the gradient domination structure and treat the policy optimization objective as a standard smooth non-convex function, but the current paper leverages the structure in the analysis of the actor. From this perspective, the key novelty of the paper lies in Lemma 4.1. To my knowledge, Lemma 4.2 is a standard result (namely, showing the approximate iteration-wise critic convergence up to gradient norm of the actor). The fact that Lemma 4.2 is standard does not undermine the contribution of the paper. For clarity, I strongly encourage the authors to be precise and transparent in communicating to the audience which parts of the analysis are novel and which rely on established results. If this is indeed the case, the authors should consider substantially revising the paper to place more emphasis on Lemma 4.1 and its analysis in the main paper.\n\n2) The authors state \"Additionally, when this ODE tracking method is applied to the recursion for the exact gradient case, it produces better results compared to existing bounds, such as those in Mei et al. (2022).\" in line 52-54, but never establish anything along this line.\n\n3) In line 119-121, the authors make the comment \"Yuan et al. (2022) too establishes global convergence with sample complexity of $\\mathcal{O}(\\epsilon^{-3})$, however, it requires an additional structural assumption on the problem which is highly restrictive.\" The sentence is written in a way that makes the audience want to know the exact assumption. Please provide more detail here.\n\n4) In line 150-151, \"However, the return ... leading to the following result.\" -- the gradient domination lemma is not a direct consequence of $J$ being smooth.\n\n5) I suggest that the authors re-organize the appendix and add proper linkage between lemmas/propositions and their proofs, to make it easier to the audience to locate the proofs.\n\n6) Something nice about the result in this paper is that the convergence is established on the last iterate. If we follow the analysis in Chen and Zhao [2024] and plugs in the gradient domination condition at the end, the convergence in value function space will be on the best iterate (in addition to having an inferior rate). The authors should consider mentioning this additional advantage of their analysis.", "limitations": "I do not foresee any negative societal impact.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The strength lies in the result itself. The convergence rate $\\mathcal{O}(1/k^{1/2})$ measured by gradient norm squared has been the best-known result and this paper establishes $\\mathcal{O}(1/k^{1/3})$ convergence in function value space, which is highly significant. I believe many researchers in the RL theory will find the result and analysis interesting.\n\nOn the flip side, the paper is badly written, not in terms of the language, but in delivering a clear message on what specific technique/analysis enables the improved rate. The authors The authors repeatedly emphasize the challenges arising from coupled actor and critic variables and from using single-loop single-timescale updates. I do not believe these are the actual challenges. As the authors themselves noted, Chen and Zhao [2024] analyzes the same single-loop single-timescale algorithm and establishes convergence. Moreover, in broader settings of stochastic approximation/optimization, under structures like non-convexity with Lipschitz gradients, PL condition, and strong convexity, many other papers consider a similar single-timescale algorithm and show that the algorithm achieves the optimal convergence rates. \n\nThe weakness in the analysis from Chen and Zhao [2024] is that they treat the policy optimization objective as a general smooth non-convex function without using the gradient domination structure (or one may plug in the inequality at the end). In my understanding, the core innovation of the current paper is to exploit this structure when bounding the iteration-wise drift of the actor. A more thorough discussion of this aspect should be the actual focus of the presentation.\n\nOverall, I believe that the results derived in the paper are very much worth being known to the community, but significant additional work is needed to improve the presentation and to help the audience understand the core contribution and technical innovation.\n\nReferences\n\n[1] Shen, H. and Chen, T., 2022. A single-timescale analysis for stochastic approximation with multiple coupled sequences. Advances in Neural Information Processing Systems, 35, pp.17415-17429.\n\n[2] Zeng, S. and Doan, T., 2024, June. Fast two-time-scale stochastic gradient method with applications in reinforcement learning. In The Thirty Seventh Annual Conference on Learning Theory (pp. 5166-5212). PMLR.\n\n[3] Huang, Y., Wu, Z., Ma, S. and Ling, Q., 2024. Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applications. arXiv e-prints, pp.arXiv-2410.", "was_revised": true, "final_justification": "Raising score as the authors' response provides more clarity on the technical innovation", "rebuttal": "We sincerely thank the reviewer for their thorough and insightful feedback. We are encouraged that they find our results and analysis both significant and of interest to the reinforcement learning theory community. We also greatly appreciate the constructive criticism and thoughtful suggestions, which will help us improve the final version of the paper.\n\n***Q1) The weakness in the analysis from Chen and Zhao [2024] is that they treat the policy optimization objective as a general smooth non-convex function without using the gradient domination structure (or one may plug in the inequality at the end). In my understanding, the core innovation of the current paper is to exploit this structure when bounding the iteration-wise drift of the actor. A more thorough discussion of this aspect should be the actual focus of the presentation.*** \n> We thank the reviewer for this insightful observation. The comment is indeed correct in noting that our analysis leverages the Gradient Domination Lemma (GDL) structure from the outset, using it as a foundation to derive and solve the core recursion. We will emphasize this point more clearly in the final version.\n\n> This approach stands in contrast to that of Chen and Zhao [2024], who rely on standard smooth optimization techniques and employ a telescoping sum to upper bound the gradient norm. In their analysis, the GDL is applied only at the end, yielding a best-iterate guarantee but leading to a weaker overall convergence rate.\n\n> We will incorporate this comparison into the introduction, main text, and discussion sections of the final version.\n\n***Q2) Can the authors clarify if I correctly understand the innovation of the paper in my comments above (in Strengths & Weaknesses)? Specifically, the limitation in prior works like Chen and Zhao [2024] .... more emphasis on Lemma 4.1 and its analysis in the main paper.***\n> Yes, the reviewer is correct in understanding both the novelty and the techniques used in the paper. Indeed, Lemma 4.2 is derived using standard techniques that are well-established in the literature. We appreciate the suggestion to emphasize Lemma 4.1 more prominently, and we will incorporate this in the final version.\n\n***Q3) The authors state \"Additionally, when this ODE tracking method is applied to the recursion for the exact gradient case, it produces better results compared to existing bounds, such as those in Mei et al. (2022).\" in line 52-54, but never establish anything along this line.***\n> We apologize for this omission. By applying our techniques, we can improve the iteration complexity by a factor of $\\frac{1}{(1 - \\gamma)^3}$ compared to Mei et al. (2022), along with better dependence on the initial sub-optimality. A brief explanation follows:\n\n>> In the exact gradient case, from the sufficient increase lemma and using a step size $\\eta_k = \\frac{1}{L}$, where $L = \\frac{8}{(1 - \\gamma)^3}$ is the smoothness coefficient, we have:\n$$ a_{k+1} - a_k \\geq \\frac{\\lVert \\nabla J^{\\pi_{\\theta_k}} \\rVert_2^2}{2L}. $$\nFrom the Gradient Domination Lemma (GDL), we also have: $$ a_k \\leq \\frac{\\sqrt{S} C_{PL}}{c} \\lVert \\nabla J^{\\pi_{\\theta_k}} \\rVert_2.\n $$ Combining the two gives the recursion: $$\n a_{k+1} - a_k \\geq \\frac{c^2}{2 L S C_{PL}^2} a_k^2. $$\n Using ODE tracking, it follows that:\n $$ a_k \\leq \\frac{1}{\\frac{1}{a_0} + \\frac{c^2}{2 L S C_{PL}^2} k}\n = \\frac{1}{\\frac{1}{a_0} + \\frac{c^2 (1 - \\gamma)^3}{16 S C_{PL}^2} k}, \\qquad \\forall k \\geq 0.$$\n\n> In comparison, Mei et al. (2022) report:$$\n a_k \\leq \\frac{16 S C_{PL}^2}{c^2 (1 - \\gamma)^6 k}. $$\n Our result offers improvements in two important aspects:\n1. **Improved horizon dependence:**  \n     Our bound improves the dependence on the discount factor from $(1 - \\gamma)^{-6}$ to $(1 - \\gamma)^{-3}$:\n     $$a_k \\leq \\frac{16 S C_{PL}^2}{c^2 (1 - \\gamma)^3 k}.$$\n 2. **Tighter behavior in early iterations:**  \n     The bound from Mei et al. (2022),  \n     $$\\frac{16 S C_{PL}^2}{c^2 (1 - \\gamma)^6 k}, $$  \n     can be larger than the maximum possible sub-optimality (which is upper bounded by $\\frac{2}{1 - \\gamma}$), especially when the initial iterate is far from optimal. This results in a vacuous bound for early iterations. In contrast, our result yields a meaningful and tighter upper bound starting from the very first iteration.\n\n> We have incorporated this discussion, along with the corresponding ODE tracking lemma and its proof, into the appendix of the final version.\n\n***Q4) In line 119-121, the authors make the comment \"Yuan et al. (2022) too establishes global convergence with sample complexity of $\\mathcal{O}(\\epsilon^{-3})$, however, it requires an additional structural assumption on the problem which is highly restrictive.\" The sentence is written in a way that makes the audience want to know the exact assumption. Please provide more detail here.***\n> The results in Yuan et al. (2022) consider stochastic policy gradient descent under various assumptions, using a batch size $m$ and horizon length $H$. Their analysis applies to a setting with only an actor parameter (i.e., no critic).\n\n> **Corollary 4.11** (under ABC Assumption 3.3):  \n> The most basic global convergence result yields a sample complexity of   $ O(\\epsilon^{-6})$   with horizon length $H = \\frac{\\log(\\epsilon^{-1})}{1 - \\gamma}$.\n\n> **Corollary 3.7** (under ABC Assumption 3.3 and Assumption 3.6 with slackness $\\epsilon'$):  \n> - *Limiting case:* When $\\epsilon' = 0$, corresponding to the infinite-horizon case, the policy converges to within $O(\\epsilon)$ sub-optimality in $O(\\epsilon^{-3})$ iterations. However, this requires infinite-length trajectories at each iteration, making the total sample complexity essentially unbounded.  \n> - *General case:* When $\\epsilon' > 0$, the policy converges to within $O(\\epsilon + \\epsilon')$ sub-optimality in   $ O(\\epsilon^{-1} (\\epsilon')^{-2})$   iterations. This means the algorithm cannot be guaranteed to converge to arbitrarily small sub-optimality unless $\\epsilon' \\to 0$ (i.e., infinite-horizon setting).\n\n> In summary, the stochastic policy gradient algorithm in Yuan et al. (2022) is substantially different from ours, which focuses on single time-scale actor-critic methods. Our results either achieve better sample complexity or require fewer/less restrictive assumptions. We will clarify this comparison more precisely in the final version.\n\n***Q5) In line 150-151, \"However, the return ... leading to the following result.\" -- the gradient domination lemma is not a direct consequence of $J$ being smooth.***\n> Thank you for pointing this out. This line is indeed misplaced, and we will remove it in the updated version.\n\n***Q6) I suggest that the authors re-organize the appendix and add proper linkage between lemmas/propositions and their proofs, to make it easier to the audience to locate the proofs.***\n> Thank you very much for the helpful suggestion. We will include an appendix outline and clearly indicate the correspondence between technical results in the appendix and their counterparts in the main text in the updated version.\n\n***Q7)Something nice about the result in this paper is that the convergence is established on the last iterate.... The authors should consider mentioning this additional advantage of their analysis.***\n> Thank you for the suggestion. We will include this point following our main result, Theorem 3.3, in the updated version."}]

Author rebuttal:

Meta-review: The paper improves the state-of-the-art sample complexity bound for actor-critic algorithm in tabular MDPs from $\epsilon^{-4}$ to $\epsilon^{-3}$. Besides, the algorithm is single time-scale, more practical than many previous works that rely on double time-scale. All reviewers agree this is a significant contribution on a fundamental question. 

Please improve the clarity of the paper according to the discussions with the reviewers.
Decision: Accept (poster)