Finite-Time Analysis of Actor-Critic Methods with Deep Neural Network Approximation
Authors: Xuyang Chen
Fengzhuo Zhang
Keyu Yan
Lin Zhao
Venue: ICLR 2026 Poster (2026)
Keywords: finite-time analysis
actor-critic
deep neural network
Primary area: learning theory
TL;DR: This paper provides the first finite-time analysis of single-timescale AC with deep neural network approximation in continuous state–action spaces -- a setting ubiquitous in modern RL.

Abstract: Actor–critic (AC) algorithms underpin many of today’s most successful reinforcement learning (RL) applications, yet their finite-time convergence in realistic settings remains largely underexplored. Existing analyses often rely on oversimplified formulations and are largely confined to linear function approximation. In practice, however, nonlinear approximations with deep neural networks dominate AC implementations, leaving a substantial gap between theory and practice. In this work, we provide the first finite-time analysis of single-timescale AC with deep neural network approximation in continuous state-action spaces. In particular, we consider the challenging time-average reward setting, where one needs to simultaneously control three highly-coupled error terms including the reward error, the critic error, and the actor error. Our novel analysis is able to establish convergence to a stationary point at a rate $\widetilde{\mathcal{O}}(T^{-1/2})$, where $T$ denotes the total number of iterations, thereby providing theoretical grounding for widely used deep AC methods. We substantiate these theoretical guarantees with experiments that confirm the proven convergence rate and further demonstrate strong performance on MuJoCo benchmarks.

Published as a conference paper at ICLR 2026
FINITE- TIME ANALYSIS OF ACTOR-CRITIC METHODS WITH DEEP NEURAL NETWORK APPROXIMATION
Xuyang Chen, Fengzhuo Zhang, Keyu Yan, Lin Zhao Department of Electrical and Computer Engineering
National University of Singapore (xuyang. chen, yky, Ezzhang, e elezhl | @nus. edu.sg
ABSTRACT
Actor-critic (AC) algorithms underpin many of today's most successful reinforce- ment learning (RL) applications. yet their finite-time convergence in realistic set- tings remains largely underexplored. Existing analyses often rely on oversimpli- fied formulations and largely confined to linear function approximation. In practice, however, nonlinear approximations with deep neural networks dominate AC implementations, leaving substantial gap between theory and practice. In this work, we provide the first finite-time analysis of single-timescale AC with deep neural network approximation in continuous state-action spaces. In partic- ular, we consider the challenging time-average reward setting, where one needs simultaneously control three highly-coupled error terms including the reward error, the critic error, and the actor error. Our novel analysis is able to establish convergence stationary point at rate O(T-1/2), where T' denotes the to- tal number of iterations, thereby providing theoretical grounding for widely used deep AC methods. We substantiate these theoretical guarantees with experiments that confirm the proven convergence rate and further demonstrate strong perfor- mance on MuJoCo benchmarks.
INTRODUCTION
Actor-critic (AC) methods have achieved substantial success in many challenging applications Sii- ver et al.) 2017: Vinyals et al.) [201 Lazaridis et al.) 2020). In particular, it becomes instrumental in enabling highly robust and agile robot motion control involving continuous state-action spaces, such as quadruped locomotion control (iiki et al., 2022 Hoeller et al. (024), humanoid whole- body control (Radosavovic et al., 2024), drone racing (Kaufmann al.] [203)] etc. These successes are largely driven by the use of powerful function approximators, such as deep neural networks, to represent control policies (actors) and value functions (critics).
Despite substantial empirical success, the theoretical understanding of AC methods remains under- developed, especially in the most practical settings. Existing studies often restrict attention finite state-action spaces and adopt simplified algorithmic variants to case analysis. For instance, double-
loop methods perform multiple critic updates per fixed actor (Yang al. 2019 Kumar al. 2023 Agarwal et al., 2021 Xu et al.) (220b)), which improves value estimation and thereby yields more accurate policy gradient for that actor. This enables a clean, decoupled analysis of the actor and critic, but at the cost of impractically high sampling complexity. Similarly, two-timescale meth- ods (Wu et al. 2020; Xu et al.) 2020c] Chen et al. 2023) impose a smaller step size on the actor than the critic, with their ratio vanishing as iterations grow (i.e., lim an/3, 0). This asymp- totically decouples the actor and critic, mimicking multiple critic updates per actor. However, this artificial slowing down of the actor is undesirable and rarely adopted in practice.
In contrast, the canonical form widely used in practice is the single-timescale AC algorithm, where both actor and critic updated simultaneously with proportional step sizes at each iteration (i.e., ar/3: = c). However, analyzing its convergence is more challenging than for the aforementioned simplified variants, as the actor and critic updates are strongly coupled. The aforementioned decou- pled analysis is over-conservatio and cannot establish convergence of the tineesale AC.
"Corresoonding author

---

Published as a conference paper at ICLR 2026
Table 1: Comparison of related works on single-timescale actor-critic algorithm analysis.
MDP
Sampling
Approxination
Comeerence
Reference
Continoous
Coniinnuus
Markovian
Markovian
Neural Network
Experimens
Convergence
Stote Spacee
Action Space
Actor
For Critie
Fanction Class
Validation
Rote
x
x
o(r 0.6)
Olshersky Gharesfard 2023
x
o(r 0.6)
Zhan 2024
1
x
Tiun
x
1
O(T 0.5 m 0.6)
O 0.69
Recent efforts to study the convergence of the single-timescale AC algorithm include Chen et al. (2021), Olshevsky & Gharesifard (2023). Chen & Zhao (2024), and Tian et al. (2024), with their respective settings summarized in Table Among these works, only TTin al. (2024) considers single-timescale AC with neural network approximation. Nevertheless, it suffers from two funda- mental limitations. First, restricted finite state-action spaces, where linear function approx- imation already suffices, This renders the neural network perspective redundant and undermines the practical significance of the analysis. In contrast, real-world reinforcement learning problems typically involve continuous state state-action spaces and rely on neural networks for expressive func- tion approximation. Second, as shown in Table [ the convergence rate in Tian et al. (2024) is Ö + m -0.5, where denotes the number of iterations and y the neural network width. While the T-dependence is natural for finite-time analysis, the m-dependence is problematic. In practice, m is fixed during training and does not scale with T, leaving a constant O( error term that fails to capture the true convergence behavior. Moreover, neural tangent kernel theory (Ja-) cot et al. 2018) shows that neural networks become increasingly linear m + co, thereby degrad- ing their representational power. Intuitively, the convergence of the algorithm should not hinge on such m- mn-limiting behavior. The observed dependence on m in prior results is merely consequence of analytical technicalities, rather than a fundamental property of the algorithm.
Motivated by these gaps, we provide the first finite-time convergence guarantee for single-ting timesclle AC in continuous state-action spaces under the time-average reward setting. Our analysis rigorously incorporates both deep neural network approximation and Markovian sampling for the actor and the critic. We prove the convergence of the reward error (Eq. (Sa)), critic error (Eq. (8b)), and actor error (Eq. (cc) at rate ( without requiring the network width to diverge. As summarized in Table I our results compare favorably with prior studies across key dimensions that are critical for practical applicability.
From a technical perspective, this improvement is enabled by a series of technical innovations. To sharpen the convergence rate, we show that the smoothness-ndduced error-arising uniquely from neural networks and absent the linear setting-is intertwined with the critic error. Unlike Tian et al. (2024). which conservatively bound the critic error by constant, path diminishes, thereby removing the prior requirement of m - oo (see the mean-path update analysis in Eq. (26)). To address the challenges of continuous state-action spaces, introduce an operator-based framework (see Eq. (T)) capable of handling uncountable domains. To mitigate error propagation caused by deep neural networks (DNNs) approximation of the value function, we establish a set of important regularity properties of DNNs in Lemma | Moreover, the interplay between DNN approximation error and Markovian sampling noise poses greater challenges than those encountered in the linear function approximation (Chen & Zhao 2024) or the i.i.d. sampling setting (Oshhvvky & Gharesifard 2023 Tian al. (024). To control such complex error dynamics, we develop refined analyses in Lemma 7 Lemma 10 (Markovian noises). A high-level overview of
prove that its mean
our proof ideas and newly developed techniques provided in the Proof Sketch in Appendix C
This work is further distinguished by extensive empirical validation that corroborates our theoretical results (see Section 5). Although all prior studies listed in Table jattempt to bridge the gap between theory and practice, none included empirical evaluations. A key reason is that many of their assump- tions are unrealistic for practical deployment. For instance, the algorithms analyzed in prior works cannot even be applied to simple tasks such as gymnas i um since they are restricted to finite action spaces and depend on sampling from the stationary state distribution. Moreover, AC with linear function approximation is generally incapable of controlling
(oowerrsss et al.) (024),
2

---

Published as a conference paper at ICLR 2026
standard benchmarks. In particular, our experiments show that the linear critic fails to approximate the value function even for the simple pendulum (Figure [.. These observations highlight the sub- stantial gap between the simplifying assumptions underlying existing theoretical analyses and the complexities inherent in practical RI. applications. In contrast, we empirically verify both the con- vergence and the proven convergence rate of our algorithm on pendulum, and further demonstrate its effectiveness on more challenging Gym MuJoCo benchmarks, where neural AC consistently out- performs its linear approximation counterpart. This underscores the importance of analyzing neural AC algorithms, which are both practically relevant and theoretically more challenging.
Notation. We use san-serif letters denote scalars and use lower and upper case bold letters to denote vectors and matrices respectively. For two sequences of real numbers (z,) and (yr,), we write d'n = (y., if there exists C' < oo such that |aa| S Cly,, for all n sufficiently large. We use (.) to further hide logarithmic factors. The total variation distance of two probability measure μ and is defined by drv(u, v) == 1/2 xx lu(dx) v(dx)).
2 PRELIMINARIES
Markoy Decision Process. We consider the standard Markov Decision Process (MDP) character- ized by (S, P.r), where S is the state space and A the action space. The spaces and A allowed to be either finite sets or real vector spaces, i.e., S C Rdd and A C Rd,, The transition kernel denoted by P(s 0z) E Rz0 and the reward function r
A + [- uy]. A policy Te parameterized by 0 E Xe maps given state to a probability distribution over the action space, i.e., ar ( [8))) In this work, we consider the time-average reward setting (Sutton al.) 1999 Yang et al. 2019] Wu et al.) 2020) Chen & Zhao 2024), which aims to find policy mo that maximizes the following Mhiite-horiion aieereeeraee reward:
T-1 (st, at)
J(0) == lim F. T-000
Σ t=0
= E(e [r(s,a]]
T
In the above equation, the expectation Eg is taken over the states and actions generated by following the policy To and the transition kernel P. Additionally, P4 denotes the stationary state distribution induced by zy and P. The existence of this stationary distribution is guaranteed by the uniform ergodicity of the underlying MDP, which is common assumption (See Assumption Giin the sequel). Hereafter, we refer to (() as the time-average reward (and exchangeably, performance function), which can be evaluated by the expected reward over the stationary distribution μg and the policy To. The state-value function is used to evaluate the overall rewards starting from a state s, following policy me and transition kernel P thereafter, which defined as
(e(s) = Ee
Σ (r(se, oz) J(O) s0 = t=0
Similarly, we define the action-value (Q-value) function to evaluate the overall rewards starting from 8, taking action a, and following transition kernel P and policy To thereafter:
Qo(s,a) Ee
(r(s), - -()))))))(())))))))))))))))))) so 0,
+ ((O)
t=
where the last expectation is taken over s' a()
To tackle the technical challenges associated with neural network function approximation over con- tinuous state and action spaces, we introduce two auxiliary operators. Let J == {s I S R) denote the class of real-valued functions on S. For a policy no, define the operators Do : F - F
and Pg F F as
(Do(ss)= = (({). (s)n())=//
J(6')P(8' 8, s,a)oo(a s)dads'.
(1)
Here, Do multiplies function f by the stationary distribution μa, whereas Po maps f to its one-step look-ahead under the Markov chain induced by me and P, i.., (P) (olf(s)+1) st s). The inner product on F is given by
(f.g) / f(s) g(s)
3

---

Published as a conference paper at ICLR 2026
and the induced norm of function is |lf (f.
Actor-Critic. In AC, the actor corresponds to the policy, while the critic typically estimates the actor's value function via lemporal-difference learning. The actor then updates its policy parame- ters through stochastic gradient ascent to maximize the performance function. The policy gradient theorem (Sutton et al. 1999) offers closed-form expression for the gradient of the performance function J(Ø) with respect to the policy parameters 0, which is given by
VoJ H (Q((s,)) a) Vo log To (als)]
Equivalently, the policy gradient can be written as
VJ(0) Es- [QQa(, a) b())) Va log (a(a)))]
where b(s) is called the baseline function, which is employed to reduce the variance of the gradient estimate. A popular choice of baseline is the state-value function, which leads the following so-called advantage-based policy gradient
I = -Er-pp ( (s, Vo o log (o(a)))]
where Ae = Qo(s.a) (s) is known as the advantage function.
In deep RL, the policy (actor) and value functions (critic) are typically parameterized by deep neural networks due to their strong representation capabilities (Mnih et al.) 2015; Lillicrap et al. 2015). However, the convergence of training deep neural networks are less understood, especially in RL. In this paper, establish conditions and provide finite-time analysis for dingle-timeseed AC algorithms utilizing deep neural network approximations for both the actor and the critic.
THE SINGLE-TIMESCAL NEURAL ACTOR-CRITIC ALGORITHM
In this section, we present the single-timescale neural AC algorithm to be analyzed in the sequel, incorporating key components commonly found in practical implementations.
3.1 PARAMETERIZATTION OF THE VALUE FUNCTION AND POLICY
We consider deep neural network for estimating the true state-value function (s(s) under a policy
gg. The network (ww; 8) has a general form deep neural network with a linear output layer:
8 (0) 8, (k)
g (k-))) 1,2, K, V(w;)) = Vmxx 6 & (R))
(5)
Vm
where K is the total number hidden layers, state & E Rdd is the input the neural network, o an element-wist activation function, b is a fixed coefficient vector for the output layer, and w E Xn stands for the trainable parameter of the neural network. The latter is column vector formed by stacking the weights of different layers, w == (W E m x 1 'j==1' where my N is the width of the k-th layer and mo de is the input dimension. Without loss of generality, we assume all the hidden layers have the same width m,, i.e., my = m for E {1,2, K}. ease of presentation only. As shown in the proof, our analysis also applies to my m. Note that the above definition is general enough to encompass standard multilayer perceptrons (MLPs), convolutional neural networks (CNNs), and residual networks (ResNets) special cases (Liu al. 2020).
for the
The policy me is allowed have a general parameterization, including linear functions (Yang al., 2019), deep neural networks (Wang et al.) 2019), and energy-based policies (Fu et al.. 2020). For the deep neural network approximation case, the actor be parameterized similarly to Eq. (5) where all the trainable parameters will be stacked into the column vector 0 E Xg.
3.2 ALGORITIM DESIGN
In this subsection, we first aim to update the parameter of the neural network (the critic) w so that ((w; 8) can approximate the true value function (s) of policy no. Concretely, at step
4

---

Published as a conference paper at ICLR 2026
Algorithm Single-Timescale Neural Actor-Critic
1: Input initial actor parameter On. initial critic parameter wh, initial reward estimator yoo, stepsizes a for actor, /3 for critie, and y for reward estimator.
2: Draw So from some initial distribution
3: for = 0, 0, 2, ... T do
4: Take action a, To, (-] (t)
5: Observe next state St+1 ~ PP 8t, az) and reward r. = r(8t, az)
6:
&
1/: + (wr 81++) (ww 8t)
7:
T = TIt 7 - 71))
8:
Wh+1 = projonm (wi + 36, v (Wrr
9: 01+1 O, ad, Ve log Te, (as st)
10: end for
we implement Stochastic Gradient Descent (SGD) methods to adjust the critic in the direction that would most reduce the mean square value error [V(s:) V (ww;;
Wh+1 =w [V(((()) - ((wes 8t]]
(6)
=w =w = Viw st)] Vi (wi:s.).
where 3 is the stepsize (learning rate). Since V(s;) is unknown, the semi-gradient TD(O) method approximates it by replacing ((s:) with the current target ((0) + V(w 8141). To further estimate the unknown time-average reward J()), we use the following exponential moving average update of T/-
7h+1 = + 7(r, 7T))
where is the stepsize. Hereafter, we will refer to it as the reward estimator. This additional estimation of the time-average reward (() introduces more analysis complexity compared the discounted setting (Olshevsky & Gharesifard 2023 Tian et al. 2024). Now, by denoting the TD error as
: ri Th + V (Wi 84+1) V (W;;
can rewrite the update of the critic in Eq. (6)
W++1 = w. 36, V 8t).
For the neural network specified Section 3.1 we require its width m to be a large constant such that the neural network is in the overparameterizztion regime. In this regime, the optimal solution typically resides in the neighborhood of the initialization (Du et al. 2019 Chen et al.) 2021 Tian al.) 2024). Therefore, in Line 8 of Algorithm [ constrain the update of the critic parameter within a ball of constant radius around its initial condition, which ensures the boundedness without overlooking the optimal solution. Specifically, proj stands for the projection onto a ball with
constant radius around the initial condition of the critic, i.e., Bun, = [w|]|w - woll I uw } where Ww is constant.
For the actor update, it is standard to use the TD error (5,) as an approximation of the advantage function (Sutton & Barto] (2088). Therefore, based on the policy gradient theorem, the corresponding update rule for the actor can be written as
0,+1 = 0, + ad, Va log Ta. To, (arls:).
where 6, Ve log ma, (arls:) is an approximation the policy gradient defined in Eq. (4). The parallel updates of the critic and actor in Lines 8 and 9 aim to drive the actor towards the direction that increases the time-average reward J(Ø).
We summarize the described AC algorithm in Algorithm I which follows the classic AC chitecture studied in prior works under various settings, as listed in Table The "single-timescale" refers to the fact that the stepsizes a, 3, only constantly proportional to each other. We consider
5

---

Published as a conference paper at ICLR 2026
the more challenging neural network approximation for both the actor and the critic, which is ferred to as the "neural actor-critic". Moreover, we consider the more practical Markovian sampling, starting from initial state so, with subsequent states and actions generated according to the tran- sition kernel and the policy, respectively. The consecutive transition tuples (8o, 4n, 81, (1, ,2,82, form single trajectory, thereby circumventing the time-consuming re-sampling procedure (i.i.d. sampling) mandated in prior works (Chen et al., 2022]] Tian et al. 2024). More importantly, we aim address the challenging settings of continuous state and action spaces that are prevalent in applications (see Table | for a detailed comparison). The finite- timee-time&e convergence in such contexts of significant interest the community but remains unresolved.
ANALYSIS OF SINGLE-TIMESCAN NEURAL ACTOR-CRITIE
In this section, we begin by outlining several standard assumptions and then present our main finite- time convergence results for the algorithm.
4.1 ASSUMPTIONS
Assumption (Neural architecture and initialization). The neural network defined Eq. 5 satis-
fies the following properlies:
(a) (Input assumption) Any input to the neural network satisfies |0 1.
(b) (Activation assumption) a is Ly-Lipschitz and ha-smooth. i.e. VII,I2 E RR (i) (o(1)) a (x-)) S 1,|01 Iz2l; (ii) |o' (a'( o' (xx2)) S ha|æ1 - xz| where o' is the derivative of
(c) (Initialization assumption) Each entry of the vector satisfies [ba] S 1, and the weights of the neural network w(()) are randomly initialized from normal distribution N(0, 1), with each entry being independently sampled.
This assumption mainly states the initialization and analytic properties of the neural network. We note that these assumptions are widely satisfied in various applications. For the input norm con- straint, could normalize the state space guarantee this assumption. Regarding the activation function, we emphasize that many commonly used activation functions, such as sigmoid and GeLu, satisfy this condition. The initialization assumption, furthermore, can be easily implemented during neural network training. We also note that the above assumptions are common in the theoretical
analysis of neural networks (Liu et al. 2020 Tian al. 2024).
As shown in Lemma F.4 of (Liu et al., 2020). with Assumption I the following assumption holds with high probability, which we state as an assumption in our work for ease of presentation.
Assumption 2. The absolute value of each entry of ((k) (the output of layer of the neural network) is (1) at initialization. The initial weights satisfy || [| < O(ym) for all k.
For the value function Vs(s) of given policy 0, its best approximation using the neural network (Eq. 5 is defined via
Eapp (w" (w)( inf Es-pp [([(w) s) (s()))
where w (00) is referred to as the optimal critic that yields the minimal (optimal) approximation error Capp (wo (0)). In this paper, we assume the optimal approximation errors for all potential policies are uniformly bounded, that is,
v0, fapp (w)(0)) S capp:
for some constant Eapp 2 O. The error Eapp is zero if Ve can be exactly approximated by the neural network (Eq. (5). Naturally, it is expected that the learning errors of Algorithm I depend Capp. which represents the approximation capacity of the critic.
The assumption of uniformly bounded approximation error is common in the literature (Chen et al.
2021 Zhang et al.) 20236] Olshevsky & Gharesifard 20233 Chen & Zhao 20224] Tian et al.) (024). It more restrictive for the linear function approximation than for the neural network setting. If

---

Published as a conference paper at ICLR 2026
the true value function is not linear, which is typically the case in practice, the approximation error Eapp can be significantly large. In contrast, the neural network upproximation can arbitrarily closely approximate any continuous function according to the universal Approximation Theorem (Homiik 1991]. and therefore can potentially keep the approximation error arbitrarily small.
We then make the following assumption for the optimal critic.
Assumption (Smoothness of optimal critic). For any 01, 02 E Xe, we have
|| (0:) - w² S lwl 0211,
V - (w2(02)) S h 0 - 02l1:
where Lا and ,is are finite positive constants.
The above assumption states that the optimal critic is lu--Lisschizz and hu-omooth. This assumption is commonly employed for the single-timescale AC with neural network approximation TTan et al.) 2024). In the case of linear function approximation. the above assumption is trivially implied by the linearity of the value function (Olshevsky & Gharesifard 2023 Chen & Zhao 2024).
Furthermore, we specify the regularity of the neural network.
Assumption 4 (Regularity of the neural network). For the neural network defined in Eq. exists some constant A > 0 such that
5 there
[[( - (w (0))l ~ (0))l, 40 Xo.w E Xn.
where the norm of function is defined based on the inner product given in Eq. (2), which involves the product of function values integrated over 8. Assumption 4 states the regularity of the neural network in terms of learning the optimal value. Intuitively, it requires that the perturbation of the critic parameter around the optimal one will cause a non-zero change of the critic neural network output. From the point of view of the optimization landscape of the neural network, it merely assumes that optimal and suboptimal points are distinguished. This is also a standard assumption of other analysis of AC methods with neural network approximation (Tian et al. 2024).
The next assumption pertains to the exploration of the policy To in continuous settings.
Assumption 5 (Exploration). There exists a constant X2 > such that (v (w), Do(I-Po)(ww)) >
X2 [ww) for any 0 E Xe and neural network (ww E F, where Do Po are operators defined in Eq. 77). denotes the identity operator, and the inner product is defined in Eq. (2)
To demonstrate its connection to exploration, we show that if exploration is insufficient, the assump- tion fails to hold. First note that the operator Dg essentially multiplics the stationary distribution μi to the function on its left (see the definition in Eq. (T). If the policy тo does not sufficiently explore, there exists a subset of the state space A C S such that (A) = O. Furthermore, we can choose (ww) such that (ww;)) = 0, Vs E S ) A and ((w;)) 8) > 0, Vs E A. With this choice, the left- hand side of the inequality evaluates to O, while the right-hand side becomes positive. This violates the condition stated in Assumption 5 Thus, the contrapositive holds: if Assumption is satisfied, it ensures sufficient exploration of the state space under the policy a This sufficient exploration assumption is standard in the literature of analyzing the convergence of AC algorithms (Wu et al.
2020 Chen et al. 2021 Chen & Zhao 2024| Tian et al., 2024).
Assumption 6 (uniform ergodicity). For a Markov chain generated by the policy no and transition kernel P, let P denote the corresponding state transition probability. Then there exists k >> 0 and p (0, 1) such that the total variation distance between the state distribution stationary distribution μi satisfies: drv (P E -l|uu =-))Ho()) S kp" forr all T 2 0, E S.
time and the
Assumption assumes the Markov chain geometrically mixing, which implied by the uniform ergodicity of the chain. It is commonly employed to characterize the noise induced by Markovian sampling RL algorithms (Bhandari et al. 2018 Zou et al.. 2019 Wu et al.) 2020 Chen et al.)
2021 Zhang et al. 2022 Olshevsky & Gharesifard 2023 Chen & Zhao 2025).
Assumption 7 (Regularity of the policy). Let To (als)) be a bounded policy parameterized by O E Xe. There exists positive constants ur hr and lp such that for any O, and it holds that: (i) || log To (a]s)] < uni (ii) V log To, (a]s) V log To, (a|s)]l I h 0 ; - 0211: (iii (To (als)
To, (a|s) & 1p 0 02]l.
7

---

Published as a conference paper at ICLR 2026
Assumption 7 states the regularity of the policy, which is standard in the literature of actor-critic
methods (Wu et al. 2020] Chen et al. 2021 Chen & Zhao 2024 Tian et al! (024). These condi- tions sufficiently general to be satisfied by wide range of distributions, including the uniform distribution, the truncated Gaussian distribution, and the Beta distribution with a, B 1.
4.2 FINITE-TIME ANALYSIS
0| We define the integer rr == min 0 1xp--1 < T-1/2). where T is the total number of iterations, k and are the same constants defined in Assumption O The integer Ty represents a certain mixing time of an ergodic Markov chain, which will be used to control the Markovian noise in the analysis. In our main results, we require that I" 2 2Tr to ensure that the Markov chain is well-mixed and the
Markovian noise is effectively bounded. We can estimate that 7T which results in kp"
log log T Olog T)
log p 2log
We quantify the learning errors by defining y/ :- 7)e J(,)). which is the difference between the reward estimator and the true time-average reward J(O,) at time t. For the critic, we define 2, == Wi - W with wi := w- (O,) to measure the error between the critic and its target value at iteration i. The following theorem summarizes our main results.
Theorem 1. Consider Algorithm with a = f 3 T
VT where e is a constant depend-
ing on problem parameters. Suppose Assumption hold, for T 2 2TT, we have
log" T
Elyil O
(CCpp))
(8a)
T TT
VT
1=TT
T-1
log" T VT
E| o
+ (Capp))
(8b)
T
1=
log²2 T VT
(Capp).
(8c)
T TT
Theorem [ establishes the finite-time convergence of Algorithm Given that the problem is in- herently non-convex in general, it is common prove convergence stationary point. The error term (Eapp) represents the critic approximation error that commonly appears in the analysis of AC methods (Wu et al., 2020 Chen & Zhao 2024 Tian al., 2024 If the critic approximation error Capp is zero, the critic and the actor errors all vanish at a rate of (T-1/2). The Ô notation hides the polynomials of all other problem parameters that do not depend on T and Capp- The additional logarithmic term with respect to T arises from the mixing time of the Markov chain, which can be further eliminated if considering the i.i.d. sampling scheme (Chen & Zhao 2024). As summarized we establish convergence of single- tigeellle AC under the most practical settings.
in Table I
The main challenge of our analysis lies in controlling the coupled reward error (Eq. (8a) ) the critic error (Eq. (8b),, and the actor eтror (Eq. (8c). We begin by deriving implicit and coupled bounds for the time-average reward error, the critic error, and the actor error, respectively. We then view the propagation of these errors as an interconnected system (Chen & Zhao 2024) and analyze them holistically. To better appreciate the merit of our analysis, sketch the main proof steps of Theo- rem in the Proof Sketch in Appendix C
EXPERIMENTS
5.1 APPROXIMATION CAPABILITY OF THE NEURAL CRITIC
We evaluate Algorithm on the Gymnasium um Pendul umm v11 task. This is a canonical control task with a continuous state space described by 8 = (cos 0, sin 0, 0) (minimal coordinates (0, 0)) and a continuous torque action. The critic is parameterized by DNN of the form Eq. (5), and the actor is a Gaussian policy whose mean and variance are produced by DNN with the same architecture. For comparison, we employ linear critic parameterized by a fixed 6-term RBF feature map, V(s) w T ((s) with w E IR. The feature vector consists of Gaussian RBFs defined on (cos 0, sin 6, A): (1(s) = exp
||s-c//1 i = 1,...,6, 6, where the centers (c+ E RR3 are placed uniformly and 20
8

---

Published as a conference paper at ICLR 2026
Linear Cricc
Neumi Crtc
Optinal V
Slope:
-1
250
500
1000
2000
4000
8000
16000
pad)
(aad] (8) Visualizations
(red)
(b) Empirical Convergence Rate (log-log) log)
Figure (a) Comparison of learned value functions: (left) linear critic, (middle) neural critic, and (right) optimal V obtained via time-average reward relative value iteration. Heatmaps are rendered with the Viridis colormap, where blue indicates low values, green intermediate values, and yellow high values. (b) Log-log plot of Er == T- Er-1 ((O,)l (Eq. (8c versus T, with Tr 125 (Theorem holdd for 2 2Ty). Colored markers represent five independent runs, and the dashed line shows their mean with a linear regression fit.
Table 2: Final average reward under different configurations (mean std over seeds). Width sweep uses fixed depth 2; depth sweep uses fixed width = 128.
Config
Ant
HalfCheetah
Hopper
Humanoid
Swimmer
Walker2d
Linear
797.1
299.2261.9
61.4+25.2
186.9=14.7
35.924.7
810.94290.6
Width-64
1120.0=140.3
190.6
108.5+16.3
264.0=56.1
132.5#78.4
1215.3+192.6
Width-128
1587.4=183.
1425.8+161.7
533.8+64.7
291.1 9
220.5=41.. 1.88
1400,9+461. ..2
Width-
1245.2:: 1245.2=126.7
2250.1=187.9
725.3:165.0
365.2164.3
251.3+8,8
1390.91324,9
Width-512
949.2+75.4
1691.64245.8
749.3+304.6
448.9+48.4
222.7+22.7
996.5+180.99
Depth-1
961.228.0
1205.84293.5
174.6434.4
219.0424.3
173.64101.1
4139,5
Depth-2
1587.4=183.2
1425.8+381.
533.8+64.7
291.1#63.9
201.2+54.2
1400.9 1.2
Depth-4
1824.9:147.0
2144.2+229.6
465. 6495.6
385.0=50.0
182.6#26.8
865. 1966.
Depth-8
1021,0+58.3
1699.24285.4
210.8+68.2
546.4163.7
230.9457.7
1136.9445.0
is determined by standard width rule (Konidaris et al., 2011). For visualization, the ground-truth baseline is computed via time-average reward relative value iteration (RVI) (Bertsekas 1998). As illustrated in Figure aa), the neural critic aligns more closely with the ground-truth value.
5.2 EMPIRICAL VALIDATION OF THEORETICAL CONVERGENCE RATE.
In this experiment, we follow the same setting as in Section 5.1 We empirically estimate the
convergence rate of Algorithm (Eq. (8c)) to examine its consistency with the theoretical rate of O(T-1/2). As shown in Figure after an initial warm-up period of about 250 iterations (recall that Theorem applies to T 2 2Tr), the curve exhibits a clear linear trend. Fitting single slope the mean trajectory yields -0.51, which aligns closely with the theoretical value of -0.5. This agreement provides direct empirical support for our theoretical convergence rate.
5.3 ALGORITHM EVALUATION ON MuJoCo BENCHMARKS
We further evaluate Algorithm on challenging continuous-comtre benchmarks from Gym Mu- JoCo, including Ant, HalfCheetah, Hopper, Hu-
2250
Lieer beanl
Depth-l
2000
2020
Depth-1
manoid, Swimmer, and Walker2d. We conduct ablations along three axes: (i) linear critic, (ii) neural critic with varying depths, and (iii) neu- ral critic with varying widths. The linear critic
1750
500
identical to that used in Section 5. Table 2 reports the final average rewards over five seeds, while Figure 2 illustrates the learning curves of two selected entries from the table. Overall, the linear critic underperforms substantially across all tasks. These experiments validate the effec- tiveness of our considered algorithm on practical tasks and also reinforce the importance of analyzing realistic neural AC settings.
0.0
3.2
0.6.
0.5
03
1.0
0.0
0.2
0.6
0.6
0.8
1.0
Optirssttenn Suep (Miliar))
Optimication Step (Milkinna
(a) Effect of width on reward.
(b) Efffcct of depth on reward.
Figure Reward curves under different capaci- ties: HalfCheetah (width sweep) and Anf (depth sweep). Mean + std over seeds; dashed = lin- car baseline.

---

Published as a conference paper at ICLR 2026
CONCLUSION AND DISCUSSION
In this paper, we provide the first finite-time analysis of single-timescale AC with deep neural net- work approximation in continuous state-action spaces under the time-average reward setting. Our results surpass those of existing works by effectively addressing continuous state and action spaces, utilizing Markovian sampling, and employing deep neural network approximations for both critic and actor. We also conduct extensive experiments validate the convergence guarantees of the analyzed algorithm.
ACKNOWLEDGEMENTS
This work was supported by the Singapore Ministry of Education Tier Academic Research Fund 11-8001174-00-000 and Tier 2 Academic Research Funds (12EP20123-0037, T2EP20224-0035).
REFERENCES
Alekh Agarwal, Sham M Kakade, Jason D Lee. and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research. 22(98))1-76, 2021.
Dimitri P Bertsekas. A new value iteration method for the average cost dynamic programming problem. SIAM journal on control and optimization, 36(2):742-759, 1998.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference on learning theory, pp. 1691-1692. PMLR, 2018.
Shalabh Bhatnagar, Richard S Sutton, Mohammad Ghavamzadeh, and Mark Lee. Natural actor- critic algorithms. Automatica,
2009.
Dotan Di Castro and Ron Meir. convergent online single time scale actor critic algorithm. The Journal of Machine Learning Research, 11:367-410, 2010.
Semih Cayci, Niao He, and R Srikant. Finite-time analysis of entropy-regularized neural natural actor-critic algorithm. arXiv preprint wwxiv:2206.00833 2022.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. Advances Neural Information Processing Systems, 34: 25294-25307, 2021.
Xuyang Chen and Lin Zhao. Finite-time analysis of single-timescale actor-critic. Advances in Neural Information Processing Systems, 36, 2024.
Xuyang Chen and Lin Zhao On the convergence of continuous single-timesee actor-critic. In Forty-second International Conference Machine Learning. PMLR, 2025.
Xuyang Chen, Jingliang Duan, Yingbin Liang, and Lin Zhao. Global convergence of two-timescale actor-critic for solving linear quadratic regulator. In Proceedings the AAAI Conference on Artificial Intelligence, volume 37, pp. 7087-7095, 2023.
Ziyi Chen, Yi Zhou, Rong-Roo Rong Chen, and Shaofeng Zou. Sample and communication-efficle decentralized actor-critic algorithms with finite-time analysis. In International Conference on Machine Learning, pp. 3794-3834. PMLR, 2022.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. International conference on machine learning, pp. 1675- 1685. PMLR 2019.
Zuyue Fu, Zhuoran Yang, and Zhaoran Wang. Single-timescale actor-critic provably finds globally optimal policy. arXiv preprint arXiv:2008.00483 2020.
10

---

Published as a conference paper at ICLR 2026
Mudit Gaur, Amrit Singh Bedi, Di Wang, and Vaneet Aggarwal. Closing the gap: Achieving global convergence (last iterate) of actor-critic under markovian sampling with neural network parametrization. arXiv preprint arXiv:2405.01843, 2024.
David Hoeller, Nikita Rudin, Dhionis Sako, and Marco Hutter. Anymal parkour: Learning ag- ile navigation for quadrupedal robots. Science Robotics, 9(8))eadd7756, 2024. doi: 10.1126/
acirobo
Mingyi Hong. Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33(1):147-180, 2023.
Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, (2)2551-257, 1991.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemel: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, 31, 2018.
Sham M Kakade. A natural policy gradient. Advances in neural information processing systems, 14, 2001.
Elia Kaufmann, Leonard Bauersfeld, Antonio Loquercio, Matthias Müller, Vladlen Koltun, and Davide Scaramuzza. Champion-level drone racing using deep reinforcement learning. Nature, 620(7976):982-985 2023. ISSN 1476-4687. doi:
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999.
George Konidaris, Sarah Osentoski, and Philip Thomas. Value function approximation in rein- forcement learning using the fourier basis. In Proceedings of the AAAI conference on artificial intelligence, volume 25, pp. 380-385, 2011.
Harshat Kumar, Alec Koppel, and Alejandro Ribeiro. On the sample complexity of actor- critic method for reinforcement learning with function approximation. arXiv preprint arXiv:1910.08442. 2019.
Harshat Kumar, Alec Koppel, and Alejandro Ribeiro. On the sample complexity of actor-critic method for reinforcement learning with function approximation. Machine Learning, 112(7): 2433-2467, 2023.
Aristotelis Lazaridis, Anestis Fachantidis, and Toannis Vlahavas. Deep reinforcement learning: A state-of-the-art walkthrough. Journal of Artificial Intelligence Research, 69: 1921-1114 2020.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv: 029701291, 2015.
Chaoyue Liu, Libin Zhu, and Misha Belkin. On the linearity of large non-linear models: when and why the tangent kernel is constant. Advances in Neural Information Processing Systems, 33: 15954,15964, 2020.
Takahiro Miki, Joonho Lee, Jemin Hwangbo, Lorenz Wellhausen, Vladlen Koltun, and Marco Hut- Learning robust perceptive locomotion for quadrupedal robots in the wild. Science Robotics, 7(62)xeabk2822, 2022. doi: 10. 126/sccirbooticcsaa2228..
A Yu Mitrophanov. Sensitivity and convergence of uniformly ergodic markov chains. Journal of Applied Probability, 42(4):1033-0014 2005.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 5 518(7540):529553 2015.
Alex Olshevsky and Bahman Gharesifard. A small gain analysis of single timescale actor critic. SIAM Journal on Control and Optimization, 1002) 2023.
11

---

Published as a conference paper at ICLR 2026
Iiija Radosavovic, Tete Xiao, Bike Zhang, Trevor Darrell, Jitendra Malik, and Koushil Sreenath. Real-world humanoid locomotion with reinforcement learning. Science Robotics, 9:eadi9579, 2024. doi: 10.1 00.11
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354-3333 259,,0177 2017.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
Haoxing Tian, Alex Olshevsky, and Yannis Paschalidis. Convergence of actor-critic with multi-layer neural networks. Advances in Neural Information Processing Systems, 36, 2024.
Mark Towers, Ariel Kwiatkowski, Jordan Terry, John U Balis, Gianluca De Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Markus Krimmel, Arjun KG, et al. Gymnasium: A standard interface for reinforcement learning environments. arXiv preprint arXiv:2407.17032, 2024.
Oriol Vinyals, Igor Babuschkin, Wojeiech Czamnekki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(778223350-334, 2019.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. arXiv preprint arXiv: 1909: 01 0500, 2019.
Weichen Wang, Jiequn Han, Zhuoran Yang, and Zhaoran Wang. Global convergence of policy gradi- ent for linear-quadratic mean-field control/game in continuous time. In International Conference on Machine Learning, pp. 10772-10782. PMLR, 2021.
Yue Frank Wu, Weitong Zhang, Pan Xu, and Quanquan Gu. A finite-time analysis of two time-scale actor-critic methods. Advances in Neural Information Processing Systems, 33:17617-17628, 2020.
Pan Xu, Felicia Gao, and Quanquan Gu. An improved convergence analysis of stochastic variance- reduced policy gradient. In Uncertainty in Artificial Intelligence, pp. 541-551. PMLR, 2020a.
Tengyu Xu, Zhe Wang, and Yingbin Liang. Improving sample complexity bounds for (natural) actor- critic algorithms. Advances in Neural Information Processing Systems, $3:4358-4369 2020b.
Tengyu Xu, Zhe Wang, and Yingbin Liang. Non-asymptotic convergence analysis of two time-scale (natural) actor-critic algorithms. arXiv preprint arXiv:2005.03557. 2020c.
Zhuoran Yang. Yongxin Chen, Mingyi Hong, and Zhaoran Wang. Provably global convergence of actor-critic: A case for linear quadratic regulator with ergodic cost. Advances in neural informa- tion processing systems, 32, 2019.
Fengzhuo Zhang, Boyi Liu, Kaixin Wang, Vincent Tan, Zhuoran Yang, and Zhaoran Wang. Rela- tional reasoning via set transformers: Provable efficiency and applications to marl. Advances in Neural Information Processing Systems, 35:35825-35836 2022.
Fengzhuo Zhang, Vincent Tan. Zhaoran Wang, and Zhuoran Yang. Learning regularized mono- tone graphon mean-field games. Advances in Neural Information Processing Systems, 36:67297- 67308, 2023a.
Fengzhuo Zhang, Vincent YF Tan, Zhaoran Wang, and Zhuoran Yang. Learning regularized graphon mean-field games with unknown graphons. Journal of Machine Learning Research, 25(372):1- 95, 2024.
Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Basar. Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimization, 58(6): 3586-3612, 2020a.
12

---

Published as a conference paper at ICLR 2026
Shangtong Zhang, Bo Liu, Hengshuai Yao, and Shimon Whiteson. Provably convergent two- timescale off off-po actor-critic with function approximation. International Conference on Machine Learning, pp. 11204-11213. PMLR. 2020b.
Yufeng Zhang, Fengzhuo Zhang, Zhuoran Yang, and Zhaoran Wang. What and how does in-context learning learn? bayesian model averaging, parameterization, and generalization. arXiv preprint arXiv:2305.19420, 2023b.
Zhiyao Zhang, Myeung Suk Oh, FNU Hairi, Ziyue Luo, Alvaro Velasquez, and Jia Liu. Finite-time global optimality convergence in deep neural actor-critic methods for decentralized multi-agent reinforcement learning. arXiv preprint arXiv:2505. 18433, 2025.
Mo Zhou and Jianfeng Lu. Single timescale actor-critic method to solve the linear quadratic regula- tor with convergence guarantees. Journal of Machine Learning Research, 24(222):1 2023.
Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis for sarsa with linear function approximation. Advances in neural information processing systems, 32, 2019.
13

---

Published as a conference paper at ICLR 2026
Supplementary Material
Table of Contents
Related Work
14
Additional Notations
15
Proof Sketch
16
D Preliminary Lemmas
16
Proof of Main Theorem
18
Step I: Reward error analysis
18
E.2
Step 2: Critic error analysis
21
Step Actor error analysis
26
Step 4: Interconnected iteration system analysis
28
Proof of Preliminary Lemmas
30
Proof of Markovian noises
34
Declaration
A RELATED WORK
Actor-Critic methods. The AC algorithm was initially proposed by Konda & Tsitsiklis (1999)
Subsequently, [akade (2001) extended the natural AC algorithm. The asymptotic convergence of AC algorithms has been well established under various settings, as demonstrated in works by Kakade (2001). Bhatnagar al. (2009). Castro Meir (2010), and /Zhang et al. (2020b). More recently. many studies have focused the finite-time convergence of AC methods. Under the double-loop setting, Kumar al. (2019) investigated the finite-time local convergence of several AC variants with linear function approximation. Wang et al. (2019) explored the global convergence of AC methods with both the actor and the critie parameterized by neural networks with single hidden layers. Cayci al. (2022) improved upon the work of Wang al. (2019) by considering Markovian sampling and reducing sample complexity. Xu et al. (2020a) analyzed natural AC under Markovian sampling, while Chen al.) (2022) studied decentralized AC and decentralized natural AC in the same setting. More recently, Gaur et al. (2024) and Zhang et al. (2025) established global optimality convergence for double-loop AC methods.
Under the two-timescale AC setting,, Wu at 2020 established the finite-time local convergence to stationary point at sample complexity of O(E 2.5) under the undiscounted time-average reward setting. [uu et al. (2020c) studied both local convergence and global convergence for two-timescale (natural) AC, with 2-55 and ( sample complexity, respectively, under the discounted accumulated reward. The algorithm collects multiple samples to update the critic. |Hong et al. (2023) proposed a two-timescale stochastic approximation algorithm for bilevel optimization and the algorithm subsequently employed in the context of two-timescale AC, serving as basis
14

---

Published as a conference paper at ICLR 2026
for wide range of multi-agent reinforcement learning analyses (Wang al. 2021 Zhang al, 2023a 2024). Chen et al. (2023) established the global convergence of wwo-timescale AC methods for solving linear quadratic regulator (LQR), where only single sample is used update the critic in each iteration. However, none of these previous results utilized neural network approximation for the value function (the critic).
Under the most challenging single-timeseat setting, Fu et al. 2020) considered the least-squares temporal difference (LSTD) update for the critic and obtained the optimal policy within the energy- based policy class for both linear function approximation and neural network approximation. Zhou
Lu (2023) studied single-timescal AC on LQR. In addition, Chen al. (202T): Olshevsky & Gharesifard (2023): [Cenn & Zhao (2024) considered the single-timescale AC in general MDP cases with linear function approximation. Recently, Tian et al. (2024) built upon the results of Olssevsky & Gharesifard (2023) and improved to neural network approximation. A comprehensive review and comparison of all existing results on single-timescale AC in general MDP settings are presented in
Table 0
B ADDITIONAL NOTATIONS
We make of the following auxiliary Markov chain which was introduced in Zou et al. deal with the Markovian noise.
2019 to
Auxiliary Markoy Chain:
P 81-7+1
P
Pg
6:
P
8t Oe-
0
-+1
8
r-2
de 7+2
at
81+1- (9)
For reference, we also show the original Markov chain. Original Markov Chain:
O
a Pg 86-+11
0 0c-rt1, a1-++1 S1-7+2
0 0.-r12
24
0 at
P
81-7
a 06-
S1+1- (10)
In the sequel, we denote by Ō = (Ft. 0e, 1141) the tuple generated from the auxiliary Markov chain Eq. while O. = (8t, de, 8241) denotes the tuple generated from the original Markov chain in Eq. 10
In our work, we use the term Markovian sampling to refer to the setting where all samples are drawn from Markov chain. Concretely, the samples follow
(P.ma))
(P.ros), (82, 02) ... (P.Fo.) (8t, az),
(80, ao)
(81, a1)
(11)
forming one trajectory (su, ag, 81, .1..... 8t, az).
Remark. Note that in Table I we label the actor sampling in Tian et al. (2024) as not Markovian. This arises from the fact that Tian et al. (2024) adopts a sampling scheme that fundamentally different from the Markovian sampling Eq. (TT. For each update at timestep t, the statc-action pair (8t, àz) used the actor update in Tian et al. 2024) is obtained by sampling random horizon
~ Geom - 7),
rolling out trajectory (5o, ag, $1, a1 di..... ST, ar), and using only the terminal pair (ō âz) (sr,ar) Each (&t, âz) therefore arises from an independent rollout, and successive samples do not satisfy any Markovian dependency:
(8c, at) A 6e41,00+1)
Because this sampling is based independent aanomm-horzzon rollouts, Markovian noise arises in this part. In practice, this is also less sample-efficient than single-trajectory Markovian sampling.
For this reason, although Tian et al. (2024) refer to their scheme "Markovian sampling", view as fundamentally different from the standard usage of the term and label it as "not Markovian" in Table 1. Notably, this same sampling mechanism has been used in Zhang al. (2020a). who
15

---

Published as a conference paper at ICLR 2026
explicitly refer to it as random-horizon policy gradient. Following this terminology, we believe "random-horizon sampling" a more accurate description for this type of sampling.
We define the following functions, which will benefit decompose the errors and simplify the presentation.
Ag(O, 17 0) [J(0) - 1/ (V)sss
g(O, w. 0) = [r(s,a) - -
(w: [
g(w,0) 0) == ((c.==""~dovarr.,))((11..... J(6) (w: - -V(:
Ah(O, n, (, 0) = (J(O) - 7 ((:))))))) -/:: 5) |
(0)))
(0) h(0,0) ((s.a) | Vlogs)m(((l)
A 8) = -0) (V (V): Vo(s)) Vog
(12)
We also define the following functions, which characterize the Markovian noise.
$00, 0) = (1) (0)))r(s,a))-((0)) - (0O,w, 0) (w -(.. 0)).
(13)
5(0,w,0) 0) (w - wg. (Vw)) (Bo; 1000 0)] h(O,)))) ( = (V.(0), (h(0,, 0)] h(O,)))
where O is shorthand for an independent sample from stationary distribution 140, ~ no P.
To demonstrate the main ideas of the proof of Theorem we use the notations Yr, Zr and GT for the three errors that we seek to bound, namely,
T-1 B| g(V)
T-1 E
g(0) = T TT
Eyi g(z) = T
= T
(14)
Here (()),g(() and (V) represent the reward error, critic error, and actor error (policy gradient norm), respectively. Our proof of Theorem primarily involves analyzing and bounding these three errors relative to one another. The difficulty of this work lies in the continuous state and action spaces and the neural network approximation.
To ease the presentation,
define max(u, the Mpy ur ) as uniform upper bound for 77, 2, V and V log no (a) s), where u, defined in Lemma Then we have |8V log Tell S 4u2. The norm of w is defined by ||س||| =: (K [W))))1 1/2, where || ||r is the Frobenius norm of a matrix.
C PROOF SKETCH
In this section, outline the error-term analysis of Theorem After bounding each component, the convergence follows by solving the interconnected iteration incqualities (E.4). The key challenges and new techniques developed correspondingly emphasized.
Reward error analysis. using the reward estimator update rule (Line 7 of Algorithm T.. we decom- pose the reward error into:
Vin S (1 (1-27) + 2mM (T J(0.)) 2y, J(O++1))
(15)
+2(((0.) - 1( 2.
The second on the right-hand side of Eq. (15) corresponds sampling in MDP with continuous state-action spaces under neural network function approxima- tion, which we addressed in Lemma 7 The third term captures the variation of the moving actor
bias induced by Markovian
performance targets J(0,) tracked by the reward error. Leveraging the smoothness of J(0) (see
Lemma 6 and the boundedness of V (see Lemma [] derive implicit upper bound for this
16

---

Published as a conference paper at ICLR 2026
term expressed as function of [yu and VJ())). The fourth term represents the difference between the moving actor target, which can be controlled due to its Lipschitz continuity shown in Lemma The last term in Eq. (15) reflects the variance in reward estimation, which is bounded by (
Critic error analysis. using the critic update rule (Line of Algorithm Dr we decompose the squared error by:
E| 21|++11 1| < E| 23 (ww, 0.)) + 23EV wi, 0e) + (z, Ag(O,, me. 0.)) 2B( wi w(+1) > + w wit 112 2BI1 wr, 0.) + Ag(O Tr. 0z)) (16)
The definitions of 9.9. Ag. O2, and vi can be found in Appendix B First of all, the second term on the right-hand side of Eq. (16) is the inner product between the critic error 2; and the critic's mean-path update g(w., 0z), which serves the key the convergence. Our analysis for this term is distinct from all previous results since considering continuous spaces and deep neural networks substantially complicate the bounding process. we employ the Bellman equation to manage error propagation and control the error by leveraging the approximation capability of the neural net- work (Eq. 77), the regularity of neural network (Lemma D. and sufficient policy exploration (see Eq. (27 It provides an explicit characterization of how sufficient exploration can help the conver- gence of learning. The third term is a Markovian noise, which we bounded in Lemma S The fourth term is caused by inaccurate reward and critic estimations, which can be bounded by the norm of y and 2, after applying the Lipschitzness of V shown in Lemma ! The fifth term tracks both the critic error 2; and the difference between the drifting critic targets w We establish an implicit upper bound for this term moving critic target, which can be controlled due to its Lipschitz continuity stated in Assumption 3 Finally, the last term reflects the variances of various estimations, which is bounded by O(3).
function of yr and z,. The sixth term represents the difference between the
Actor error analysis. using the actor update rule (Line 9 of Algorithm D and the smoothness property of ((0) (see Lemma 6). we derive
[( < (B(J(0.+)) J(O.)) - ((O)) nr wr, 0.)) + E(e(O,, 0.)]
(17)
hj aE 6, log ne, (a [112.
- EEV.J(),). AN (O' 0.)1)
2
where the definitions Ah, Ah' and O₂ can be found in Appendix B The first term on the right- hand side of Eq. (17) compares the actor's performances between consecutive updates, which can be bounded after summation. The second term is an error introduced by the inaccurate estimations of both the time-average reward and the critic. After employing the Lipschitzness of V. we control this term by providing an implicit bound depending on Vt: 2t. and (O,). The third term a noise term introduced by Markovian sampling, which we handled in Lemma TO The fourth term comes from the linear function approximation error. The final term represents the variance of the stochastic gradient update, which is controlled by Oaa) due to the boundedness of V, a result we specifically derived in Lemma
D PRELIMINARY LEMMAS
Lemma 1. There exists sealars Uh Lus and by such that for any s E S and wi E Xq.
[[ S uu.
[wwis V(wz s)ll < |,11wa - w2ll,
|V vi s)]l S ho holll w2
where 0(1), O()) and h, h.= - with respect to width m.
Lemma 2. There exists positive constant by such that for any 0,, 02 E Xe, it holds that
drv (.1s), T. (1)s) s L |00 62ll.
(18)
17

---

Published as a conference paper at ICLR 2026
Lemma 3 (Distance between stationary distributions). For any 01 and 02, it holds that
drv (Ho, - 17 ( Ai
$1 +
1 0100 - -221,
dr no. ulg & mo,) - 4 (1 [logp -1 + 1
#1 + 1 p )110 0211.
drv (No, no, & P.Po. Po2 no, P) S 1 + [lo
p 0|00 0211-
Lemma (Distance between distributions induced by the original and auxiliary chains). Given time indexes and such that 2 T O, consider the auxiliary Markov chain in Eq. (9. Conditioning on St-r+1 and O.-T. we have
dTV E P(5+1 E E dTv E P(O E
drv(P(O; 1) P(O, e) = (Pv(((((s)) E ((5t, āe) E E),,
drv (I(((s a:) E ) P(3,, ā.) E )) - drv E P(3r E -) + 2
11 0--
Lemma
( Wu et al. 2020 For any 01, 0z. we have
(((0,) - 2(02) S 1 - 0211,
where
1 = 2ul (1 [log, x $1
(19)
Lemma ( (Zang et al. (2000a)). For the performance function J()), there exists a constant h such that for all 0,, 02 IR", il holds that
VV((0)) VJ((al s hhy100
02l1:
(20)
which further implies
J(02) 2 J(0,) + (VJ(())) 01) hi 10: 0, 0,12,
(21)
2
(02) S (())) (VJ(0))))) 01) + h 00 02 021
(22)
2
E PROOF OF MAIN THEOREM
In this section, we aim show the proof of Theorem We decompose the whole proof into four steps.
E. STEP 1: REWARD ERROR ANALYSIS
In this subsection, we will establish an implicit bound for estimator.
Lemma (Markovian noise). From any t 2 r >> O, we have
Ei nr. 0,) S 16u2ral, ral, + 4u
4u2rx ry + 4u²r(r 1)ads + 4u2xp"
Theorem 2. Choose v = y v we have
log T
((v) < <0(
+ 4cu 4cuV
(23)
VT
Proof. From the update rule of reward estimator in Line of Algorithm we have
M8+1 -((++1) ?) -((,)) J(,,) J(0++1) + +7(r= mt),
18

---

Published as a conference paper at ICLR 2026
which implies
vi+ (y: J(0.) - J(O++)) +( - n1))
S vi
- 2)((((()) J(O++1))
27gr (T+ T1))
+2(J(0,) ((0++))) 2r, -1:())=) -11²²
(24)
-1- (1-27)Js, 27)u² + (7 - -((0)) + ( - J(0
+ (O.) - -(0++1)) -](0,=)))++++ -
Taking expectation up to 8141 (the whole trajectory). rearranging and summing from Tr to have
1,
T-1
Σ
Blull &
Σ t=
Elui
v
E Elye(r: J(O.))
(J(O.) - ((0+1))
2y
1a
1g
T
T-1
[((((O,) - -(0++1))
B - -n))
10.
For term 11 by direct computation, we have
4
Elyi
vit1)
27
1=
2u²
2u 22² VT.
For term I2, from Lemma
7 we have
Elye(r: - J(O.)) < 16u2 + Ty + 4u² + 1)al + 4u2xp"
Choose T == Tr, we have
T-1 1 = Σ Elye(r: -(0.)
T-1
< (16u (16u2llTT + 4u 1x Tr((T + +1))
Σ a
T-1
T-1
4u TT Σ 7 4u
Σ
VT
t=
T rT
(16cu21, deu2t=Tr(ne + 1) 4u
+ 4u2)
VT
For Tz, if ye 0, from Eq. (T have
()())))) ((0++))) S y/( h4
10 01+1112 (VJ(O.)) 0, - 0.+1))
2
S uhg O: 0 11 + 13r11 0.+1 V
If y < 0. from Eq. (22 we have
hj 10 0 +VV.((())))) 6, 0(+1))
(J())) ((0+1))) s vel
2
s why 0, 0 112 + 1: 0.+1 [++1
19

---

Published as a conference paper at ICLR 2026
Overall, get
13
Ely (J - ((
Wluh, 110 - 0.+111++ Belll0, 0z+1 (O.)0I
E E|16cu 116cu"hja + 16cu |B [((+)lII
T-1
T TT S 116c2u²h
+ 16cu 2
Eyp)
E
(()))))
VT
1=
For term 4, we have
14
B((((O)) -(
E 0, 02+1ll
162 7
166 u2 22 T TT VT
For term 45. we have
T-1 I5 Σ
BB(r:- - ((0.))
I=TT
T-1
4u²²
t=
T
4u
VT
Therefore, we get
Σ Blyl s 11 + 12- 13 + 14 + ls
$ (16cu2lyTr + 4cu2l (Tr + 1)
+ + 2) + 16c222
+ 17))
TT
VT
T-1
T
+ 2u2 + 4cu(
Σ
Eyi )
E (J(
1=TT
t=
20

---

Published as a conference paper at ICLR 2026
Since πт- Olog T), we have v T-
S
3 for large T. Then we get
VT
1 Elvil (16cu 4cu 2 TT (Tr + 1)
T 7T
+ 4u²(Tz +3) + 16c" (uh, +1]))
vT
T-1
4cu( 1
1
Byi)
(0))
E
TT tm
TT
0 log T
+ 4cu(
1
T-1
Eyf)
E (())))1
T
T
T=
t
Thus we finish the proof.
E.2 STEP 2: CRITIC ERROR ANALYSIS
In this subsection, we will establish an implicit upper bound for critic.
Lemma 8 (Markovian noise). For any t O, we have
Ei 0,) & 4c, u + 4 + 16 + 1)a + sup
where
1 - + 2udz4 + 4ulaho
C1 = 4u 41211(1 + [log, A "1
1-p
= 2u(Suh, + +[, + 2.
Lemma (Markovian noise). For any 2 O, we have
B|E(O,, 0,)] < 4czu ra + 4u T + Su + 1)a + Su Sup
where := 8u2 + Su - (2uh + ul, + ulybw).
Theorem 3. Choose fj, B = VT have
g(=) 0 log" 2 T
2u V g((gg())
2culs
v ((()) 8RE8W) + 2chu Vgwggg ((Cpp))
+
VT
(25)
Proof. From the update rule of critic in Line of Algorithm we have
||++1 - w/+1l || = Ilproj (w, + 36, V (ws; s:)) - wit1ll
Ilproj Ww (wi + 35, V (W 8t)) - proje (wi+1))
S ||اا + B5, vi (w) 8t) wi+1ll
I|m, w w wi+1 + 35, (i(w;;
Therefore, we have
|x41 2
| + ((g(0, 0,) + Ag(O 0.)) + w wi |=0 0.)) (g 0,))
+ [40
w w/
= |1
nr 0,))
+ +2222,, w/ w/+n) + ||](g wi, 0.) Ag 0)) w w/
< || + 23(22 0.)) - 20 (O,, w;, 0.) 23(z, Ag 0.))
+ 2(21, w/ wit1) 2||W; witH 211 02) me, 0.) 1
21

---

Published as a conference paper at ICLR 2026
Taking expectation up to 81+1. have = < Bl|z,1' + 2,3 (z Ilw,, 01)) +2 (O,, 0,) +2)+23B((4 Ag(Or. 0z))
18
2 (2,, wh+1) w wht1 2 +2 22 B(g wi 0.) + Ag(OO, M1. 0.) 0.))
(26)
For term 11, we first analyse the mean-path update g(w,, 0t). From the definition in Eq. (12 we have
g(wr, 0.) = Be [(r(s), ar) (O,) V (wii sc+1)
(V
@ E. Be [(V(s)) - (($++1) + (w0s; P(we: 8t) (
E.,((V(s)) (Ww,, Es (V
814 (1)
where (1) comes from the Bellman equation. For Es (V(++11) - ((W,, it can be shown that
Es4 as (V(++1) - Vusr, s1+1)|s{]
1 ( Te. ((4ts))) (a:)))-V((w:s)))) (w(s)d)))ddddds...
(V)( ((w,))) 8)),
where (I) follows from the definition of Po in Eq. (2).
Then for g(w,, 0c), it follows that
g(w., 0.) = E,,1(T Po. (VV(s) - (ww 8)), (i)
where I is the identity operator. Therefore, have (ze, gw., 0:))
=E(21, (I (v.)(((s)) V $t))
=((z,, (I (V - V(w): + V(w 8t) - (wi (ww
-E(z,, (I (V (st) [(W]: st)) (w)::)))))))
+ EZzz (1 Po. (V (w]is) 81) V (1) 8, VV (w)
Caul,Capp + (2, V (w)s 8, (I Pe.) (V. (2) (( sx))]
E(( (i(W;: st) + (V( st) - V(w,, st - (V.) (ww 8c))
E[((V(w[;ss) V(w,, st)) - Po. (V (V V(w:: Eap--
(27)
For term J1, from mean-value theorem, we get
JI B[ (Vi 8t) vV (Wmidi sI)) Po. (V. (ww))))
S 4uh || | 1|
where Wmid = pمل; + (1 (1) w with in E [0, 1] and the inequality follows from Lemma
For term Jz, it can be shown that
J2 (V(w)) - V(w.)), (I -Po))((())) ((w))))
(1)
S (el(V(w))) ((w2)))1
(2)
S >
111
22

---

Published as a conference paper at ICLR 2026
where (I) comes from Assumption 4 (2) is due Assumption 5 (3) holds since define
À == Af
Overall, obtain
1 S 4uh, 1| XBI| 112 + Fapp
(28)
From Lemma that
we know that he O(1 (011vm)) mm). Therefore, choosing m large constant such
4uh, S A
(29)
it follows that
4 S B1 2e|1 + 2ul Eapp
For term Iz, it can be analyzed by Lemma 8
For term /3, it follows that
13 B(z,, Ag(Ot, T/, 0.))
I uull ||
For term 44, have
14 E(2,, w wi+l)
B(zi, wi+1 + (Vw,) (VW,))((011 - 0())
E(z,, -(Vw)) (0, 0,)
J4
For J3, from the hu.-smoothness of w in Assumption we obtain
J3 < -= 0.112.
For J4, it follows that
Ja
B(zz, (Vw?) 6 V log To, (arls:))
E( (Vwi) ( (- nhi we 0,) - h(O,,,,)))
EE(z, (Vw?) A Thi wr, 0c))
(30)
-E(z, (Vw7) (Eo; [M(O', 0.)] h(,,, 0.) Eo; Soo, 0,))))
E[E(O,, wi, 0.)] B(z,, (Vwi) Bo, (M, 0.)))
-(2,, (Vw;) Ah(O,, Th, wi. 0,))
Note that from Cauchy-Schward inequality and lu the Lipschitz constant of wt Assumption 3
we have
B(zz, (Vw;) (ACt),Dh(O,,...... Ne 0.)) S ul, v 22 / 2Ey?
81ZR 12
(31)
From the fact that
Eoy [h(O', 0.) - (', Eo;1((((), J(O.) + Vo, Vo, (s))) no, (als)]
v.,(),),
we obtain
Ez,, (Vw?) (OO)TEO Eo; [h(O),, 0.)] = E(Z,, (Vw,) TVJ(B.) E(z,, (Vw)) (V::))/T::AA(" (o,,A''(O',,,))) follows that
-B(zi, Tw))TT((())) VEE
23

---

Published as a conference paper at ICLR 2026
Furthermore, it holds that
Eo (O,
= (
(V(s)
- Bo ((V(W((0)) vo(5))) -v(o)))))(((()))))
4u Eo
vo(s))
4u Cap
(32)
Therefore, we have
(z), (Vwi) ( Bo,1h(O, I ulw A4
S ulw v Eo HoN.s
S 2u + V 1
(33)
Substituting Eq.
331 and Eq.
(33 into Eq. 30 yields
J4 < (BE wi 0.) + 2c B Bulw
aul /1| 2EEy + 8/
(34)
+ +al v B 1 E
Overall, obtain
14 = J3 + J4 < /w]l 0,+1 - 0,11 + + wi: O.)
aul |. 12 2
2Ryy + =
+ al
2z 12
E
(()))l + 2xxu tae
For term I5 it holds that
13 = Blw; - 1|
< PE 0, 0.+1l
< 16u2?aa3
For term Ig. it follows that
Is E]|B(g(O wi, 0.) (c,
Plugging I Ig into Eq. 26 we obtain
E| 1 2 < E|12, A
2, 2,EEN w, 02) 2,3uEE U/ ||| 2hh || - -0,11
221BE We, 0₂) + 2arul. B1 12 2Ey? + 8/111
20l
(0:)) + 4om 4 4upl +321 =21 2u2
24

---

Published as a conference paper at ICLR 2026
Rearranging and summing from Ty to T 1 gives
Σ 21
11
EV 0,) +
EE wi; 0s)
K1
K2
K3
T-1
T-1
+ 2u
Eyg v El
2cul
v [R]
2 + 8/1 2e 12
ty
K4
T-1
+ 2cl
K1
(3 - 32cu 2 (4cu² + 4ul,))ap))
In the sequel, will tackle K,, K2, K3, Ka, K5, Kg respectively. For term K1, we have
1
Σ
[E 2112 E1+ VTVT.
For term K2, from Lemma 8 choose T = Ty, we have
Su24g
(O,, 0.) S Tea 402u21 + 16u 16 TylTT + 1)a +
VT
Then get
T-1
T-1 Σ
(4c urraarra Tra + 4c2u2 (ol 1)a+ Su²1,
K₂ Σ
EN EV, We, 01) 2
vT
TEeT
T=rr
For term K3, from Lemma choose 7 = TT, we have
Suibe /T
EE,,,,, 0.)] S 4cgu2 Pra Pra + Bulta (r 1)a + 1
Therefore, have
K3 = 2c
B3 0,)
t=
T-1
Su3t,
< 2c
Σ
(4czu2 pra Su (Tr(r + +1)a + 1
VT
1=17
For term K4, Ks. and Kg, from Sauuchy-Schwarte inequality, we have
T-1
K4 S 2u(
Σ
E 13)
i=Tr
1=
T-1
T-1
K3 < 2cul
B8] | 11 12)2((2 (2 Σ
Eyb 81?
Σ
Ell 11)
1=72
T-1
T-1
K6 < 2clw
Σ
11)
Σ
E [
1=
1=TT
25

---

Published as a conference paper at ICLR 2026
Overall, get
Bl 2 < 2u(
Byi)
+
B| B|
1=TT
t=ry
(=7y
T-1
T-1
T-1
+ 2cul
I8| E|
13)$(2 (2
Σ
Eyg + 8
Σ t=
1=
(=
T-1
T-1
+ 2clw
Σ
E 11122111))
E J
t=
t=
T-1
8u²
+ 2² VT +2
Σ
(4ctuFra + 4egu2lor + 16 LelnTrrT + 1)a +
VT
T=rr
(40zu T + Su Bull 1)a + 4u B W Sn
+ 2c
T-1
+
(2u (2 + 38a + (4cu? + capp))
1=
Therefore, we have
c(t)
(1)
S 0
log 2
T
+
(Capp)
+
2u
T-1
Ey:
T-1
Σ B1
VT
A
T -
T - TT
1=
1=TT
2culy
T-1
133
1 T-1
Eyy + 87
1
Σ B| 113)
A
T TT
T- TT
"T TT
L=
1=TT
2ch
T-1
T-1
+
Σ
11
T TT
T-
1=
where (1) follows from ny Ollg T) that T TT 2 T for large T. Therefore, have
log* 2 2u Ve(wigta) + 2culu / ((()) + 8888(11) + 2chw VEW)))VV)+((ppp
g(z) 50
+ ((Eapp)
VT
X
A
which completes the proof.
E.3 STEP 3: ACTOR ERROR ANALYSIS
In this subsection, we will establish an implicit upper bound for actor error (policy gradient norm).
Lemma 10 (Markovian noise). For any 2 r > 0, it holds that
E(O(O,, < 4u (Su?h hy + 3Ia,k)aa++ + Su Su"1g/=(TT + 1)a + 4u21,mp=
Theorem 4. We have
log" T VT
((V) 5
+ ((Epp)) + uy ((V)(2 + 8(8g())).
(35)
26

---

Published as a conference paper at ICLR 2026
Proof. From the update rule of actor in Line 9 of Algorithm
and Eq. 21 have
h4
J(O++1) 2 J(O.) + (VJ(0.), 0,- 0,)
10, - 0c+1112
2
h a 26 Vog To, To, (agls))]?
= =J(0))+ + + 6.V log no. (atl
2
= = + Me, We 0())
+a(V:/(0),M(O;,00)) hi a² (6 log Te, To, (as1s))12
Tr, We (1 +o(V7/0)),E,;1K000,.). h (4g
a
-[00))==([[(00)))())) Mr. We 01)) - 0a) h3 a [o
(o; 0,)]
where the last equality is due to the fact Bor [h(O', 0) AO' 0)] Eo [( a) ((0) + Vo(s') Ve(s)) logzoals)) = VJ(()..
Rearranging the above inequality and taking expectation, we have
E [(.)) < (B(J(0.+1) I(O))) E E(VJ(())), Ah(Or, Me, wi 0.)) + E(O(O, 0.)l
(36)
hy 2 alE 6, V log (a)ls))
((VJ | (O,, 0,)])
Note that from Cauchy-Schwartz inequality, we have
E(V)(( Ah(O 7/,, wi, 0,)) S EVEE
2Eyf + 22
From Lemma 10 and choosing Tr. we have
4n²1
E[O(O,, 0.)] S 4u²( h, + 31 (Tra BulI,/TT((Tr + 1)a +
VT
From Eq. 32 it has been shown that
Eo.lAA''(O, & 4u2
Therefore, we have
Eo; 0.))) <
$ 1 Eo AN' 0.)
< 2ul Capp:
where we use |J](0]| 1 which comes from Lemma 5 Plugging the three terms yields
BIIVJ(0.)1 < 1 (E[ -[ + uy
2Ryy + 8/3///22.12
4uu?( h + 31,l1 Su Su + 1)a + Au²l,
+ Su Suth3a + 2ulzeapp-
VT
Summing over I from 7r to T - 1 gives
B[))) <
([((()))) [(,()) + /EI[ 2Eyf + 81
T- FT VT
+ (log* T)
+ 22l (T TT)
T-1
T-1
2u VT ul
Σ
Eyi + 812
Σ
E E|| 11
T TT
+ Olog" 27)
+ 2ul kapp TT)-
VT
27

---

Published as a conference paper at ICLR 2026
Therefore, get
((1) < 0 log" T
+ 2 + -uy (( + 8/gel1))
VT
0 log 2 T
+ (Eapp) +
81281=)),
VT
which concludes the proof.
E.4 STEP 4: INTERCONNECTED ITERATION SYSTEM ANALYSIS
In this subsection, we perform an interconnected iteration system analysis prove Theorem
Proof of Theorem
Proof. Combining Eq.
23
Eq.
and Eq. (35 we have
glv) < < log 2
T
4cuv g()
VT
g(z) < O
log 2
+ (EAPP)
+ glugg(=) + 2cul ((=)) + 8138(=)) + 2clw v g(=)g(v))
2u
VT
x
X
log" 2 T
g(V) < (
+ (EEpp) + uuy ((V) + 813g())).
VT
Denote
2u
1a == 2culw
2cl
4 := 4cu,12 == X
,4 = 81,, ls
lo ==
(37)
X
Then we have
log2 T
(v0
0
+ 11V E(vigi))
0 log" T
g(s)
O 1a 12 gl)g(()) + ls (28)) + 4E0) + (
VT
log² T
s 0
+ O (eap)) la ((V) + 148()))
VT
For g(V), we get
log T /T
g(v) + 1g(((()) 1 2 ((g())))
g(V) <
+ (Capp)
2
follows that
log 2 T VT
g(V) < 0
+ (Eepp) + (2(((())) 4g(z)).
(38)
For g(=), have
g(=) < <0 log" T
1 g(=) + (zg(o) + 1 + (4)g)(())) + +(g(()) + _
1 g(s)) + (gg(T)
+ (EEpp) ) + 1
VT
2
If it satisfics (1) 1444/= < I. we further have
g(*) < O log"1 T
O(cap)) + (212 + 21z) + 21(8(1))
(39)
VT
Plugging Eq. 388
into Eq.
39
it holds that
log² 2 T
((=) < <
O(Capp) + (212 + 21g + 4131)) + +21.1(18g(=)
VT
28

---

Published as a conference paper at ICLR 2026
If it satisfies 24413 - 2, we have
log 2
T
g(3)
I 0
+ (Cspp) + +(12+ + + 2
(40)
VT
For E(v), we get
log" T
1 (E E(T)).
g(v)
< 0
+
(41)
VT
Plugging Eq. (38) and Eq. (40)
into Eq. (41 gives
log T
11 (E(W) + +2gg(() + +147)(0))
gl3) S 0
+ (<app)
VT
2
0 log T
+ (Eapp)
11
4
(E(() 2128(0) + +1111(11 + 21(()
VT
2
0 log" T
1
+ (Eapp)
+ 2
(1 + 21g
41166113 + - 2()
VT
2
Therefore, (f + 21 + 1 + 1/ + 21((1)
-
1 2
we have
log 2 T
g(u) < 0
(capp).
VT
Overall, we require
+ 4'
1
1
24,23 S 2' 41 + 20 + 4116/ + 2(5()) s 2
According to the definition of h 12, 1a, 14, 1s, 16. it can be shown that
2cul X
1
2 + 112)
c
4
4ul (1 + 812)
64c² 2222
1
=
c
(42)
X
2
8 2ulld
4cu(1 + 2u² + 321 2
2u² X2
2culu
862 u
1
1
X2
2
8u( + -6u2 +
128 a x²
From the fact that for positive constants t, we have
Σ, 1/t, I mint..
Thus we choose
128 1,
L 1/2 + 41 + v22..)
c c Su 1+ Gu +
(43)
X2
which satisfies the three inequalities of e shown in Eq. 42). Therefore, have
g(v) = 0 -000og
log² T
+ (CCap)):
VT
and consequently,
(=)) 0 log² T
+ ((eap))
VT
g(V) = 0 log T
) + (Capp).
VT
Thus conclude our proof.
29

---

Published as a conference paper at ICLR 2026
F PROOF OF PRELIMINARY LEMMAS
Proof of Lemma
Proof. We will divide the proof of this lemma into four steps.
Step 1: show that for all k {1,2, ... , we have
W || S O(vm).
(44)
can be shown that
[| 1 [[
W (1))
W
(K)
S Mww + l
< O(vm).
where the last inequality id due to Assumption 2 and the fact that uw is constant to m.
Step 2: show that for all & f1,2, K}. have
(| || = O(vm).
(45)
From Assumption we have || < 1. From Eq. (44), it holds that
||
W
(0)
mm
11 + ||]
m
$ (m).
By induction, suppose ||= - (m). We have
|| o (k+2))
((( 1211s (|)
Om),,
which coneludes the proof. Therefore, from Eq. 45 can be shown that
(i(W;)) 8)]l = || m
b (k)) < O(1).
Step show that for all 21,2, ... K}. we have
(k) (K) || < 01)..
(46)
From the chain rule, we have
0 (N) ( (i.j)
1 Vm
d' W
(K) ())
Therefore, we get
V (8))
12
*st 1) (k) (i, (1,))
sup ||
Σ W (1) 2/|
sup
|||||=|
| (
m
O())
30

---

Published as a conference paper at ICLR 2026
where E' is diagonal matrix with (i, o'(z, d'(z,
E(d).
Step 4: show that for all E {1,2, .. }. we have
| WW || < 011,
(47)
where V ((k) is defined to be matrix whose (I, - i)m + h) 'tth entry V (W [r, h) is given by
(x(
V (w = aw
holds that
1 ( (i.1.5))
_ 1 -io'd / (1)))
Vm
which can be written
Wiyys ( (i,j,') = f li = j}E(1)s(A (1)
Therefore, we get
V w0 12 2
sup
V w
w (() (i.
IIV 1==1
1 sup
m
(''V
m
|Vll==
i=1
3.1
1 sup
Σ -}E(0i s 11))
M.
[V]l==1
3.
1 sup
m
(ii) (k 111
m [V[[==1
1=1 (
sup
IIV |==1
|E [|s(k-1) 12
m
MN (())
where the last inequality follows Eq.
(45
We then show the Lipschitzness of the neural network. Since each entry of b satisfies |b,| S it is easy to see that
| (K) (ww; s)1l
|b| S 1.
Vm
By Eq.
46 Eq. 47). and the chain rule, we have
V W( ((w;s) II wix V(w;s) V
wik (k(
V (k()) V wayss(0111 < 0(1).
It can be shown that
K Σ k=1
[V = sup
((w S0(),
which concludes the proof of Lipschitzness.
The proof of smoothness property has been shown in (Liu et al. 2020).
Proof of Lemma 2
31

---

Published as a conference paper at ICLR 2026
Proof. From the definition of the total variation distance, have
drv(TO, (-15) - To. To (-13)) = /
Fo. (a - -m (al 8)] da
A
1
|To, (a| - (a {) da
A
< 2 A 1 - -02l da
< Alp1(0, 0211:
where A is the bounded support of ne(a|s (s) which satisfies SA da A. Define 4 = 1/2Alp. which completes the proof.
Proof of Lemma 3
Proof. For any 0 and 02, define the transition kemnlss respectively follows:
ds(s, / P(ds'lo (ala 1-
Following from Theorem 3.1 in (Mitrophanov 2005),
obtain
drv (mor, S (Nog, $1 + |1 P2llop:
where lop is the operator norm defined in (Mitrophanov) 2005 |||]| sup |
and lr denotes the total-variation norm. Then we have
P| - Pollop = sup 1 q(ds)(PI ((ds)((I-P)))ss P2) I
sup 1
1allr==1 S ((ds)(P) Pa)(s,
< sup /
1 a(ds)](P: Ps) ds')l
/ (dss)) / P(ds' |s, as, (dals) - no, =0, (dals))
sup
= sup / g(ds) / P(ds'ls, ()) (dals) - To, (dals))
/ g(ds) / ((To, (dals) (da(da)s))
sup
< 1- 10 0211-
The first equation results from the definition of the operation norm, the second equation results from the definition of total variation. Therefore, have
drv (Hor, S ([log, K. $1
1 - )|0 0.11
32

---

Published as a conference paper at ICLR 2026
For the second inequality, have
1s / Iuo, (do) (als) - (o,(ds)Ta
drv(ue @ To, No, @ mo2)
(a|s)]
/ / Iuo, (ds) (als) To. (a|s))
+ / /A (Ho, (ds) - noz (ds))
TTo, (a|s))
=drv (TT1 mo2) + drv (10gg M02)
1
1,1101 02ll + C(1logp
11
+
1101
02l
1 p
1
= [1 + [log, A -=1 +
1110 - 0211-
For the third inequality, we have
drv(ue,
@ no, X P. & Te @ P)
1
no, (o ne, (als) 0, no, (ds) (dds |s,a)
2
s
1
p0o, (ds)TO, (a|s) no, (ols))
2 S A
drv (Mo, To: no, 8 )
which concludes the proof.
Proof of Lemma 4
Proof. From the fact that
P(s E-) E P(st = ds, at 8141 E :),
we have
2d (P((41 E E. P),4(1111 .))
P(s = ds, at da, 8141 = ds') - -1 P(3: = dd, ā. = da, 3141 ds')l
JS JSJ A
P(s ds,a; a, da, 8141 = ds') PP(5: ās da, 80t1 = ds')l
J
IP(O: (ds, da, ds')) POO, (ds, da, ds')) ds'))l
5 JS
2d (P(O, E .))
where the last equality requires the exchange of integral which is guaranteed by Fubini's theorem since P is an absolute integrable function.
For the second equality, we have
2drr (POO, E P(, -))
= -S.AA [POO, = (ds, da, ds')) - P(Ō = (ds, da, ds'))
[ [ IP(ds')s, a))d),,))(((ss,))))))))) 0:) (ds, da)) P(ds' |s, a) ()) āz) (ds, da))
[ ()P(s) = (ds, da)) - (P( āz) = (ds, da))
[ [P((se, a1) (ds, da)) P(( az) = (ds, da))
2drv (P(((es ar) E P(( āz) :)).
33

---

Published as a conference paper at ICLR 2026
For the third inequality, since 0, is dependent 8t shown in Eq. (00). it holds that
2dTv (IP(s; 0+) ) ((5,, ā+) -))
[ P(s: ds, da) P( = ds, 0z da)l
P(st = ds Ps): = d0 = P( = dalst = 8, s, -0) - P((; = ds, a. = da)
/
P(s: =ds) / P( d0 8t STT, (da) (s (p ds dSS (dals) 8)
/
P((s = ds) (dals)) 8e - P(3, = do) (dals)]
A
(
P(s: ds) Jo. (dals))s s] P( ds) To._. (dals))
[P((t = do)TT
(dals) ddalse.. P(5: d -r (dals))
A
P(s+ = ds) /1 (B = s) - _ - (dals)
2d (IP(s: E E), E.)
$ 1, - 0.-rl + 2drv .), E E)),
where the last inequality holds due to the Lipschitz continuity of policy made in Assumption 7
Proof of Lemma S
Proof. By definition, we have
J(0:) J(02) = Bir(s", a²) r(s= a²²)]
where s¹ ~ Mo, a' ~ To. Therefore, it holds that
J(O,) J(02) FR(rst r(sttaa) < 2udrv @ To. Ho. @ To²)
< 2ul (1 + [log, x '1 |100 -02l
01 02ll
Proof of Lemma 6
Proof. The proof of this lemma can be found in Lemma 3.2 of (Zhang et 2020a
G PROOF OF MARKOVIAN NOISES
The following four lemmas deal with the Markovian noise.
Proof of Lemma
Proof. We will divide the proof this lemma into four steps.
Step 1: show that for any 0,, O2, 77, O (s, a, 8'), we have
@OO, 01) (0O0 n, 02) 4ud,110: 02
(48)
34

---

Published as a conference paper at ICLR 2026
By the definition of ((O, 0) in Eq. 13 have
(0 01) ((0,0,02) = [1
- J(01)) (1 - J(2))) ( ((02)))
< (nn ((01))(r - (n ((-))) [(02))
(r - - - -
< (0)
v Aul, |0, -22ll.
Step 2: show that for any 0, 7/1 72, O. we have
(00, m. 0) 4(0, m2. 0) S 2u m 72l-
(49)
By definition, we have
| m0 0) 4(O, 0)1 = [mm (r - - J(O))
- 2u(7) 722-
Step 3: show that for original tuple O₂ and the auxiliary tuple Ö, conditioned on 8t-r+1 and O,-rs we have
- n-r: 0 S ud, Σ
BI0 O 02-
(50)
1mm--
By definition, we have
E{ Me- 02-r) E(D(O,, n/-, -1-- -r(5,,
By definition of total variation norm, have
B/r(st, 0x) r(,,, (+)] S ( E - (51)
By Lemma get
drv E (st-r 1s1--11, 11 0(-r))
d))r((((s),)))
- 0.-r))
s drvv(P(s E 11 0.-)) P(s, E (1- 0-- 0--r)) + - 1, 1 0: - 0.--ll
1
ddrv(P(O:-1 E 01-))
P p( - 11-+11 0c-r) + 1,,,, 0.--11-
Repeat the above argument from / T, we have
1
drv (PP(O, 181-- 0,.)), 0,,, P(O, E -18c- 2
Σ
El 0--
(52)
Plugging Eq.
52 into Eq. 51 we have
E (O,, m--, A.-)) E[ m--r. P-T( 0--r))l ul Σ
0
0.-711
Step 4: show that conditioned on st-741 and 0z-7, we have
B nh-,, 0.-1) S 4u 4u²xpp
(53)
Note that according to definition, we have
E (0O Th- O 0
where 0 (s/_ a/ ) is the tuple generated by s pe--r:
Te, me, 8/-441 ~ P. From the uniform ergodicity in Assumption 6 it shows that
drv (P((e -181-+1, 0e-r), (o...) -1
35

---

Published as a conference paper at ICLR 2026
Then we have
E nt-,, 0r-r]] = -
0--]
= E (000((00)1)))) ( a1) - - d/
I 4u dTv (P(O,- 1 1 0, Po... no... 8 P)
Combining Eq. 48
Eq. 49
Eq. 50 and Eq. 53 we have
(O, nc. 0.)] (l T/,, 0₂) 4OO,, Tc. 02 ) + (0 0r-r) +0 - T, 0c-r))
+ E[( 7/ Or 0.-r) ( 1/--, 0r- + Bl0(O,, T/ 0t-r)
S E1 02 - 0.- + 2ulB - 77- 1 + ul Σ
B110; 02-51 + 4u kip 7-1
:=--
< 16u2ralj + 4u + Tu² + 1)llx + 4u²xp=
which concludes the proof.
Proof of Lemma
Proof. We will divide the proof of this lemma into four steps.
Step I: show that for any 0,, 02, w and tuple O = (s, a, s'), we have
(0, w. 01) - V0 w. 02) S cil111 - 0211. where = 4u [log, K '1 + 1-p)) + 2ulzle- + Auluhe.
(54)
By definition of (0 w. 0) in Eq. 13
have
(0, w. 01) (0, 02)1
(/ W0, 01) g(w. 0(), (w w 900,w, 02) g(w. 02)
(w : w, 01) - g(w, 01)) - (ww - 9 02) - g w 02))
+ 1ww 10, 02) g(w, o(w: (w 10, glw, 02))
For term 41, we have
I1 1(w wi, g 01) O(w, wi. 02) g(w, 0z))
= 1(w w w, 01 - g(0, 0z) + ( wi olw. O1) g(w. 02)
1(w wi, (J(O1) J ((O:)) (w:
1! w (w 01) g(w. 02))
S 2ulzlu1101 021 + 2u] 01) g(w, 02)1
I 2ulz/u1101 02ll + 4u drv (wo, Te, @ P, Nog X ne & P)
I (2ulz1, + 4 (,(11 + [lg, x $1
|) 02ll.
For term 12, from Cauchy-Schwartz inequality have
1 k( wi. 9(0,9(0,uu 02) -p(w, 02)) - (w w/, g(0, w. 02) - g(w, 0z))
= (ww w6,g(0, w. 02) - g(w, g(w,O2))l
4ul, - will
S 4ul,1u1101- - 02ll-
Combining the results from 1n and Iz. we get
(O, 01) - V(O,w, 02) S c: c 021l.
36

---

Published as a conference paper at ICLR 2026
where 0 = [1++1x1++ + [log, x '1 1-p)) 2ulzle + Aulwhu.
Step show that for any 0, w1, w2 and tuple ((s, a, 5'), we have
|V(O, WI, 0) - w2, 0)1 S 02|lwi w2l1,
(55)
where C2 = 2u(8uhe + 412 + 2-
By definition, we have
w1, [v w1, 0) (0 0)
(w-1 w" 19(09 w1, 0) [(,, (1: 0)) (w2 w 900 w2 0) g(w2, 0))
S 1w-2 - w", 0000 wr, 0) g(w), 0)) - (wh - w 0(0, W2, 0) g(w,, 0))
+ l!w1 w" 0000 w2 0) g(w2, 0)) - (w2 w' (0, 0) g(w2.
1 2ull(g(O, w1, g00 W2 0)) (0(w). 0) g(w2, 0\\| + 4ul, ||] well
It holds that
(I((O, w1, 0) - g(0, 0))1 = =I((((,,)) - J(0) (Wi 8))
+ -i(mis'>Vi( (wae)) ((w2;s') VV (w2i 8)
+ V(wyi 8) VV (wy;8) - V (wwi 8) / (wi;
$ (Wiis 8') V (w):s) ((wiss) VV (w2;s) s)
+ V(Wii V (w2;s) R) V(w2is V V (w2; s)ll
+ [V 8) V (w2; s) - i(wii 8) V (w2: 8)
+ ((wi; 8) V V (w2; 8) ((wi;)) (1):)))
+ 2uh,, ||w1 w2ll
22hholwws w2yl + 2/ [: well 2uh ||w] w2
= (4uh, 2(?)| w2ll.
follows that
(l](o(O w1, 0) - 900,w,, 0)) (o(w), g(w2, 0))1 (8uh, B1() well
Therefore, we obtain
E VO W1, 0) (0 w2, 0)1 S c2llwl well.
where C2 = 2u(Suh, + 413 + 2l
Step 3: show that for tuples O (st, at, 86+1) and Ō. (Ft, De, 1. Conditioning on 8 and 0.-7, we have
ElD 0,-r) - (,, 0 16 I + 1)a.
(56)
By the definition of total variation norm, we have
E[V (, ( wrr 0,-]]
- g Wi W 0--)))] s Su2ldd (P(Or E 181- 0_r), PO, E -18 0 0.-7)
00 El(Wur )
②2 4421ul Σ h=
O - 0--
<16444,,76 + 1)a,
where (1) follows from Eq. 52).
Step 4: show that conditioning on 8,-41 and 0
E @V w0 0rr)] Su 1up
(57)
37

---

Published as a conference paper at ICLR 2026
From the definition of (O, 0), we have
E| E[ W 0 0--l
where , is the tuple generated by s/-- 1o.-.,, ay- To. 8 ~ P. From Assumption 6 we have
drv drv((P(5 = 00r)) Ho._.) S =kp"-
Then, it holds that
([V 0,--)) [( ,, V/
0.-r)]
RiWi- w/-n 9 01, Wi 0(-r) - g0 Wi 0(-r)) duv (P(O, 18 - P Ho:-, 8 -. P)
duv (P a4) -11 θ -._ Ho:-, To.-,)
Subl,drv (IP(r 118 0r- 10. Ho.
I 11p
Combining Eq. (4
Eq. 55 Eq. (6). and Eq. (77 we have
(),,(, E O:)
wi + (,, 0 (00, 01-;
+ (O, 0,--) (O, Wt 0r-r]] (E, 0r-7)l
S c 0 - 0, c2 + - we- 16 T(T + 1)er Luppp 7-1
< 4c 2 Ta + 4c2 2 + 16u 1,, + 1)e + su² 1,,pp"
where = =1 + [log, xt '1 1-p) + 2ulz4e - 4ulwho and 2u(8uhe + 41? 21,).
Proof of Lemma 9
Proof. We will divide the proof of this lemma into four steps.
Step 1: show that for any O, w, 01, O2. we have
|E(Ow, 01) =(0, 02)1l S ca cal10, 02ll.
(58)
where C3 : 8u²( + / + Gul (2uh, + ul, + ulol)).
Since E(0,w, w. 0) = (w w-, (Vwg)) (Too,(h(O', (h(O''))) Eor [h[O', 0)], where Eg is the shorthand of _o'~<(o. In the following, we will show that each term in E(O, w. 0) Lipschitz with respect to O.
h(O, 0))). we define Eo (o 0) =
Term w is not related to 0, term w := (0) is L Lipschitz, and term Vwg is h Lipschitz.
For term hO,, 0), denote 8(0, 0) := -rss ((0) (0); s') - (ww s), we have || 01) h(O,02))
(5(0,,))V] tog
(a|s) (l(0.,.VVlog
- ||6(0, me (1000:/08_1ooo.00333030000011110 (c|s)]
+ 10000 (a|s))
< 4uh,|10: 021 000000000
8(0,02)
S 4uh, 0, 021 + - -((2)) | ( (01): (02):)))
+ ( ())
< (4uh, 2ul ) 01 021 2ul, w (01) w/ (0.))l
$ 11 0z|l.
Hence we have h(O, 0) is I Lipshhizz where
b, 4uh 2ul, 2ul
(59)
38

---

Published as a conference paper at ICLR 2026
For term Eolh(O', 0)), we have
[a, [h(O', 01)] Bo, (M(O', 02)]l
< BB, [a(OO((0))) - Es, [h(0', ,02)]l + || [2)] 1,,', 02)1
s Es, []]a(O',)) 01) - ,()'',0))ll + ||Be, [h(O', 02)] Be, (00,0)0)]]]
I 1n|00: - 021 + || [k100, (2)) - Ro [10', 02)]
S 4n|01 021 + 4u drv (me, 2 To. mo_ @ m
S (44 + 4u21=(1 + Mogp 27 + 01 021
(4n + -2ull) 2ul;)]101 02ll
21,1 - 0211.
where (1) follows from Eq. 19 and (2) comes from the definition of 4, in Eq. (59)
Then have w w is u-bounded and Lu-Lipschitz; Vwg is bo-bounded and h hasLipschitz; Eo (O,', 0) - 1(0,0 0) is -u -bounded and 3lp--iischiiz. By the triangle inequality, we have
|E(0, w. 01) - 3(0, 02)1l I (8u2 + Su²h hw + 31ll())101 02ll S ca 0a 02l1.
where c3 8u + Su hw + Gul (2uhx + uly + ulohw).
Step 2: show that
|3(0,1,,)) - -E(O, 0)1 s 4wlww - well
(60)
Actually, we have
|E(O,,,, 0) - w2,,w2,,0 0)1 = 1| - w2, (Vwg) T Eo (M(',, 0)] M(0,
< 4u 1 || - w2l.
Step 3: show that for tuples O₂ = (st, at, 8 and Ō. = (5t. 0c $411). Conditioning on 8t-7+1 and Or-r, we have
s 8u Su8 ( E w,,,, - 0...
Or
1)a.
(61)
By definition of E(0, w. 0), w, we have
[ w: -0 0(-))]
[| win, (Vw, (h((0) 6.-r) - hh(O,, 0 0,-r))ll s Lu (P(O, -|s--r1,, 0,-,), P(OO E -188-++11 0.-r)),
(62)
where the inequality comes from the definition of total variation distance. The total variation norm between O, and Ö has been computed in Eq. (5)) Plugging Eq. (2) into Eq. (62). we get
E EE,,,, wi, - =(Ō,, wi 0r-r)ll < 21dte
El 0.-
1= < Su T + 1)a.
Step 4: Show that conditioning on $t-7-1 and 0.-r, we have
[EE 01 8n Suppppppp
(63)
It can be shown that
BB [ wi-r, 0.,))ll I|I
E w,,,) - -E( -, 0 0,r)]]
] Su (P(Ōr E -18t-r-1, 0 8 no._, P),
39

---

Published as a conference paper at ICLR 2026
where (1) is due to the fact that O is from the stationary distribution which satisfies _, (wl-,,0(-)) 1 8t-++1 = and (2) follows from the definition of total variation we know that
distance. From Assumption 6
drv E (0,-)) S kpp
Therefore, we have
[ wi 0c-r)l - Su lu (P(O,
01-)),,---), @ To.-- @ P) Su drv (P ((5,, (+) E -11 ;, 0,-r),110-- TO.-.)
Su LTV (P(3) -|s 0 p.
8u'
Combining Eq. 58
Eq. 63
can decompose the Markovian bias
B[ Wr. 0.) = (E, Wr; 0.) E(Or, wr, 0:- B| wi, Oe- E(00 w1,,, 0[-]]
+ (8) 0.-T) W0 0:
B[= :
$ 0 0 1, El wirrl Su Lu + 1)a + Su kupp"
S 4e 4u LTB + T + 1)x + 8u kup
Thus we conclude our proof.
Proof of Lemma 10
Proof. We will divide the proof of this lemma into three steps.
Step 1: show that
(O,00:) - ((0,00) < (2uBh, + 31,44) 0211.
(64)
where 4, = 4uh, + 2ul, + 2 is defined in the proof of Lemma 9
Since @ () (VJJ(),,o,,h(())) 100% 0)] h(O, 0)), will show that each term in 8)0,0) is Lipschitz.
For the term (O), we know it's I, bounded and h, Lipishhhitz. For term Eg (O'' 0)] 1(00 0). we have shown in the proof of Lemma 9 that it's 2 --o-ddddd and 31, -ipshhip By the triangle inequality, we have
10 0,) - 6(0, < (8uthy + 31144)1101 - 02l
Step show that conditioning on 8t-r+1 and 0,_ we have
2 2gg Σ
10 0.-
(65)
By definition of @(0,0) 0), we have
[E(((O,, -(0
0,-1)
S 1P E (0. -1 E -118--++1,
O,-r)),
(66)
where the inequality comes from the definition of total variation distance. The total variation dis- tance between O, and Ö, has been computed Eq. (2).. Plugging Eq. (52) into Eq. (66), we get
E -
- O 0,-))l s 2u
0 0.-ll
k=t-r
Step 3: show that conditioning on 81-441 and 0.-r. we have
E TE@OO,, 0.0 4u 1sp
(67)
40

---

Published as a conference paper at ICLR 2026
From the definition of @(O,0) 0), we have
[E 0--r) -(0 )I1 = (u (0-r) To.-, @ P)
8.-r)))
Au'lddrv( (PP((e, (e) E -4 50 =o.-.)
1u1l,drv((e (P -18--t11 0c.)) po...)
S ,up
where the last inequality follows from Assumption Therefore, we have
BiO(O,, 0.-r)
Combining Eq.
Eq. 665 and Eq. 67 we can decompose the Markovian bias as
E3 (0 0.)] E[O(O,, 0.) 01-7!!
+ + 0.-,) - 0,-r)] ((,(0,,, - 0c-)), + +E 0,-r)
where O₂ is from the auxiliary Markovian chain defined in Eq. 99 and O is from the stationary distribution which satisfies E(0(O, 0
Then we have
(l, 0:)1 s (8u2h + 31,11)111 0. 0.--|1 2u2 Σ E E 0.- + 4u lyxp"
k=t-r
< 4uu2(Su²h, h3 + 31,4))Ta + TI + 1)a + 4u 1ymp"
Therefore, we conclude the proof.
H DECLARATION
I declare that Large Language Models (LLMs) were used solcly for language polishing in this paper. No other usage of LLMs involved.
41


Reviews:
[{"review_id": "TYLJehcspT", "reviewer": "Reviewer_VBtF", "summary": "The paper studies single-timescale actor--critic (AC) with deep neural network function approximation in continuous state--action spaces under the average-reward objective. It analyzes a practical AC loop that jointly updates a reward estimator, a TD(0)-style critic, and a policy-gradient actor with Markovian on-policy samples. The main theoretical result is a finite-time convergence guarantee to a stationary point at a $\\tilde{O}(T^{-1/2})$ rate (up to logarithmic factors), simultaneously controlling reward-estimation, critic, and actor errors. Experiments (Pendulum, MuJoCo-style tasks) illustrate empirical trends, including a measured slope near $-1/2$ on log--log plots and improvements from neural critics over linear baselines.", "questions": "Is projection onto a radius constraint essential for the analysis, or could similar guarantees hold for unconstrained (Adam/SGD) updates with weight decay?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Realistic setting: single-timescale updates with Markovian sampling in continuous spaces---closer to practice than idealized double-loop or two-timescale analyses.\n\n2.  Finite-time $\\tilde{O}(T^{-1/2})$ rate: matches the best known dependence on $T$ (up to logs) for this setting; jointly tracks three coupled sources of error.\n\n3. Empirical checks: (i) Pendulum results where the neural critic better aligns with an RVI baseline than a linear/RBF critic; (ii) empirical slope $\\approx -0.51$ consistent with theory; (iii) MuJoCo ablations show depth/width benefits over linear critics.\n\n4. Assumptions documented and motivated: geometric mixing/ergodicity, an exploration inequality, and smoothness/Lipschitz properties for policy and dynamics, with discussion of when exploration can fail.", "weaknesses": "1.  The theory assumes sufficiently wide networks and projects critic updates to remain near initialization. It is unclear how necessary/tight this is or how it maps to common unconstrained training with Adam/weight decay.\n\n2. Guarantees include an $O(\\varepsilon_{\\text{app}})$ term from critic approximation, but there is limited guidance for architectures/regularization that make $\\varepsilon_{\\text{app}}$ small in practice; experiments do not quantify this floor or test misspecification.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "s1xQbcoril", "reviewer": "Reviewer_Duep", "summary": "This paper provides the first finite-time convergence analysis for single-timescale actor-critic (AC) algorithms utilizing deep neural network approximation in continuous state-action spaces under the time-average reward setting. The authors prove convergence to a stationary point at a rate of  $\\tilde{O}({T}^{-1/2})$ for the coupled reward, critic, and actor errors. The theoretical claims are substantiated with experiments on the Pendulum task and MuJoCo benchmarks, demonstrating the superior approximation capability of neural critics over linear ones and empirically validating the predicted convergence rate.", "questions": "1. How is $m$ avoided in the convergence result? Does it depend on the assumption that the network is wide enough?\n2. What is the convergence rate guarantee for the discounted reward setting, as it is more common in RL formulation?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper  provides a finite-time analysis for the challenging single-timescale neural AC setting, with continuous spaces and Markovian sampling, is a substantial theoretical advance.\n2. The paper goes beyond pure theory by including comprehensive experiments. The empirical confirmation of the $\\tilde{O}({T}^{-1/2})$ convergence rate on Pendulum and the demonstration of strong performance on MuJoCo benchmarks provide crucial support for the theoretical results and highlight the practical relevance of the analyzed algorithm.\n3. The paper is well-structured and easy to follow.", "weaknesses": "The analysis operates in the neural tangent kernel (NTK) or overparameterized regime, where the network is wide enough to be well-approximated by its linearization around initialization. This regime, while theoretically fruitful, does not fully capture the feature learning dynamics that are believed to be crucial for the success of deep learning in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WXUheQXLnr", "reviewer": "Reviewer_8pXP", "summary": "This work proposes an actor–critic algorithm with finite-time analysis under a neural network function approximation setting. Compared with previous studies, the paper establishes a sample convergence rate for environments with continuous action spaces. In addition, the authors present simulation results to demonstrate the effectiveness of the proposed approach.", "questions": "See weaknesses, please.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "The study derives theoretical guarantees by establishing the sample convergence rate of the Actor-Critic algorithm for MDP with continuous action spaces. \n\nIn addition, the authors include simulation experiments that demonstrate the empirical validity of the theoretical results.", "weaknesses": "1. For Table 1, I am confused whether the comparison is fair, especially for the (Tian et.al. 2024). \n(a) Firstly, the sampling process is Markovian, both in Actor and Critic part. The restart setting is just to achieve different distribution for policy gradient under the discount finite horizon setting.  Please carefully check this part and correct the table.\n(b) Besides, the width of the Neural Network is for the $\\epsilon$-order approximation error of the value function. Your work choose to avoid this width but will lead to approximation error.   Finally, previous works with neural approximation will converge to $ \\mathcal{O}(\\epsilon)$ accurate set but your work will converge to $ \\mathcal{O}(\\epsilon+\\epsilon_{approx})$. \n\n2. Compared with (Tian et.al. 2024) and other previous works, could the author detailed  explain where are the techique novelty or improvement. I went through the proof sketch but analysis looks like standard.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "l0YX0Hu4qs", "reviewer": "Reviewer_qM9u", "summary": "This paper established a finite-time convergence result for a proposed DNN-based actor-critic reinforcement learning algorithm.\n\nSpecifically, the authors considered a challenging RL setting with 1) continuous state and action spaces, 2) Markovian samplings, and 3) average reward model. To address this problem, they developed a *single-timescale DNN-based* actor-critic algorithm, and, under some assumptions, proved a convergence rate of $\\tilde{\\mathcal{O}}(T^{-0.5})$. Finally, this paper presented some numerical results to corroborate their theoretical findings.", "questions": "**Please try to answer the following questions:**\n\n1. While the single-timescale method offers practical advantages, its convergence rate is inferior to some two-timescale algorithms [1,2]. This raises a question of potential tradeoff: could the noisier observations inherent in strongly coupled actor-critic methods contribute to this performance disparity?\n\n2. I disagree with the claim regarding $m$-dependence in Lines 70~78. Numerous studies, including [3-4], present $m$-dependent (and depth-dependent) convergence results to emphasize the influence of DNNs. Actually, this paper's findings also connect to the width $m$, though it is implicitly contained within $\\epsilon_{app}$. (To some extent, the authors are encouraged to better characterize the $\\epsilon_{app}$ with the parameters of the DNNs.) Thus, I think the $m$-dependence is supposed to be a strength rather than a drawback.\n\n3. Can the authors provide the key differences in the analysis among MLP, CNN and ResNet? It could have been interesting, but it is regrettable that the authors do not elaborate on it in sufficient detail.\n\n4. The authors state that a \"stationary policy\" is optimal due to non-convexity. However, given that numerous studies demonstrate global convergence results [1,2,5,6], should this also be acknowledged by the authors?\n\n5. The numerical experiments are kind of limited in two ways: 1) No other baselines are included; 2) The impact of depth and width remains unclear.\n\n[1] Closing the gap: Achieving global convergence (last iterate) of actor-critic under markovian sampling with neural network parametrization. ICML’24.\n\n[2] Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized Multi-Agent Reinforcement Learning. ICML’25.\n\n[3] Neural Temporal-Difference Learning Converges to Global Optima. NeurIPS’19.\n\n[4] Convergence of Actor-Critic Methods with Multi-Layer Neural Networks. NeurIPS’23.\n\n[5] Sample and Communication-Efficient Decentralized Actor-Critic Algorithms. ICML’22.\n\n[6] Improving sample complexity bounds for (natural) actor-critic algorithms. NeurIPS’20.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "**The general RL setting is impressive.** As most works on RL theory focus on tackling the discount reward model and discrete (even if can be infinite) state and action spaces, this paper extends the results to a more general setup.\n\n**The theoretical analysis is concrete.** Even though some of their techniques and analytical methods are similar to those found in existing research, the authors demonstrate commendable effort in handling a more practical and challenging scenario. I appreciate this theory-driven work, particularly in an era where empirical performance usually overshadows theoretical significance.\n\nIn addition, the paper is well-organized and the writing is pretty good.", "weaknesses": "My main concern is: **The contributions and insights are not highlighted.** For example, the authors claim that the \"single-timescale\" design is a primary contribution, yet their analysis lacks a discussion of the associated challenges and the techniques employed to resolve them. Likewise, for continuous spaces, the difficulties introduced by this setup and the authors' solutions remain unexplained.\n\nWhile these points could represent the main contributions, the authors merely enumerate their findings without offering in-depth discussion or critical analysis.\n\nBesides, I find some claims could be incorrect or inaccurate. (See Questions 2,4.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)