A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging
Authors: Sajad Khodadadian
Martin Zubeldia
Venue: NeurIPS 2025 poster ()
Keywords: Stochastic Approximation
Polyak-Ruppert Averaging
high-probability bound
Primary area: theory
TL;DR: This paper introduces a unified method that converts high-probability bounds for individual Stochastic Approximation iterates into tight concentration bounds for their Polyak–Ruppert averages.

Abstract: Polyak–Ruppert averaging is a widely used technique to achieve the optimal asymptotic variance of stochastic approximation (SA) algorithms, yet its high-probability performance guarantees remain underexplored in general settings. In this paper, we present a general framework for establishing non-asymptotic concentration bounds for the error of averaged SA iterates. Our approach assumes access to individual concentration bounds for the unaveraged iterates and yields a sharp bound on the averaged iterates. We also construct an example, showing the tightness of our result up to constant multiplicative factors. As direct applications, we derive tight concentration bounds for contractive SA algorithms and for algorithms such as temporal difference learning and $Q$-learning with averaging, obtaining new bounds in settings where traditional analysis is challenging.

A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging
Sajad Khodadadian"
Grado Department Industrial and Systems Engineering Virginia Polytechnic Institute and State University Blacksburg, VA 24061 sa
Martin Zubeldia"
Department of Industrial and Systems Engineering University of Minnesota Minneapolis, MN 55455 subeldia@umg edu
Abstract
Polyak-Ruppert averaging is widely used technique to achieve the optimal asymp- totic variance of stochastic approximation (SA) algorithms, yet its high probbbrobyyility performance guarantees remain underexplored in general settings. In this paper, present a general framework for establishing non-asymptotic concentration bounds for the еrror of averaged SA iterates. Our approach assumes access individual concentration bounds for the unaveraged iterates and yields sharp bound on the averaged iterates. We also construct example, showing the tightness of our result up to constant multiplicative factors. As direct applications, we derive tight concentration bounds for contractive SA algorithms and for algorithms such temporal difference learning and Q-learning with averaging, obtaining new bounds in settings where traditional analysis is challenging.
Introduction
Stochastic approximation (SA) algorithms are central to modern machine learning and optimization. serving as the foundation for methods ranging from stochastic gradient descent to Reinforcement Learning (RL) algorithms such as temporal difference (TD) learning and Q-learning. The general form of an SA algorithm is given by
Th+ (1 ax). + agF Wx+1),
(1.1)
where a% = a/(k + 7.)5 for some h > 1, a > 0, and & E [0, 1] is the step size, and W1+11 represents random noise, possibly arising from sampling or environmental interactions. A significant body of work has been devoted to analyzing the convergence of such algorithms, providing both mean-square
and high-probability error bounds under various assumptions (e.g., 49
"Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

A key technique for improving the asymptotic variance and robustness of SA algorithms is Polyak- Ruppert averaging, where instead of using the iterates 2y. directly, one uses the averaged sequence
yk
ZE.
(1.2)
This averaging has been shown to achieve optimal asymptotic behavior in a variety of settings, including stochastic gradient descent (7] M. contractive SA [10], and RL algorithms [36] [3]. Despite its empirical and theoretical effectiveness, sharp finite-time high-probability bounds for averaged SA in general settings remain underexplored.
1.1 Our Contributions
In this paper, we develop general-purpose framework for deriving finite-time high--roobbbility bounds for averaged SA iterates. Specifically, we assume that the base SA iterates 24, with probability least 1 8', satisfies a high-probability bound of the form ||:; 2"12 S f k) for all 8' E (0, 1) and 0 S i S k; where x is the limit point (e.g., the fixed point or optimum), and f is known function of 8' and k. Building on this assumption, we establish that for any 8 E (0, 1). with probability at least 1 - 6, the averaged iterates satisfy the bound
Ilye 11 1og(1/6) -d 0² + o (1og(1/0) 1e +
k
where d is the dimension of the variables, x² is variance proxy, and e is universal constant. We also construct an example to show that our result is tight up to the constant factor
Our general theorem has several important consequences. First, we provide a principled way to select the step size schedule {au to optimize the concentration of averaged SA under a variety of operators F. Second, we apply our framework to contractive SA algorithums, establishing sharp concentration bounds in these settings. Third, leverage our results to derive new high-probabilltyy bounds on the convergence of averaged TD-lcarning improving upon the prior result. Furthermore, we establish concentration bounds on the convergence of averaged Q-learning and off- off-policy TD- learning, which to the best of our knowledge are the first in the literature. Finally, the general nature of our framework allows it to used obtain high-probability bounds of averaged SA iterates based on future refinements of non-average SA bounds (e.g., if high-probability bounds for SA under more general assumptions are developed in the future).
2 Related Work
Finite-Sample Guarantees for Contractive SA. Recent advances have significantly improved
finite-time analyses of SA algorithms in contractive and strongly-monotone settings, often driven by applications in RL and optimization. Early finite-sample mean-square error bounds were established
for specific SA instances such as TD-learning 66 15
16
26
34
32 17 (35) and Q-learning [20 3],
but lacked tail probability guarantees. Subsequent work provided nigh-probability concentration results. For instance, (49 introduced non-asymptotic bounds for unprojected linear SA, and [1
analyzed asynchronouu Q-learning. Using martingale concentration techniques [1] 23 51 obtained
an O(k-1/2) tail bound, while [12 utilized Lyapunov methods with convex envelopes achieve finite-time results. This research culminated in general frameworks for Markovian SA: [13] provides polynomial tail bounds applicable nonlinear contractive SA with Markovian noise. particular, [14] (also [9] (8) showed subgaussian concentration under minimal noise assumptions via exponential supermartingales. extending results beyond the i.i.d. setting. Sharper concentration bounds emerged for linear SA (LSA). [9] derived tight (1//k) error rates for constant step size LSA. In nonlinear SA, notably Q-learning, averaging enhances performance. [53] established exponential tail bounds for averaged Q-learning, while (88 (also (30) derived functional CLTs and optimal non-asympiotic error bounds for synchronous averaged Q-learning. Similarly, (55) demonstrated minimax-optima complexity using averaging in variance-reduced Q-learning. Addressing practical concerns, [45 showed universal step sizes combined with tail- aail-averaging yield near-optimal gaaamaaaggguunnnnn guarantees for linear TD- learnnnn without projections or feature knowledge.

---

-uppertt Averaging in Stochastic Approximation. Averaging is a classical variance- reduction technique in SA, known to improve the asymptotic efficiency of iterates [40]. For TD- learning with linear function approximation, [1] provide finite-time high-probability bounds for averaging, albeit their step size depends on the confidence bound. [39 46 strengthen this by showing that tail-averaged TD-eearning with constant step sizes achieves optimal-order bias and variance, without requiring step size tuning. Furthermore, B6 [8] establish similar results for linear SA, which generalizes TD-leamning with linear function approximation. In addition, via simulation, (24] provides a negative result on the convergence of averaged TD-learning In Q-learning and other nonlinear SA settings, [29] establish tight sample complexity bounds. Follow-up work shows bolyak-averaged 33
also provides a statistical analysis showing convergence to the minimax lower bound for tabular Q-learning.
Q-learning achieves asymptotic efficiency 33
48 derive -syymmtpto CLT using Stein's 's method, applied to TD-learning. 44 prove Berry-Fsseed bounds and establish bootstrap validity for linear SA. These enable rigorous confidence intervals in reinforcement learning. In actor-critic and other two-time-scale SA, (5 prove the first non-asymptotic CLT under averaging. 7 and [0] obtain finite-time bounds, showing that averaging improves rates from -k-3) to O
High probability bounds vs bound on the distribution: Most of the prior work on the concentration of SA considers a step size which depends on the target probability 5 33 46 29). Such analysis only provides a bound on a single point the distribution of error. In contrast, this paper, our step size does not depend on 5, and we establish a bound on the entire distribution of the error.
3 Stochastic Approximation and Polyak- Averaging
In this section we review the classical SA framework, and the averaging technique.
Classical Stochastic Approximation: Let F; I2d Rd be a (deterministic) operator, which has at least one fixed point x" (i.e., F(z*)= = x²".. The goal is to find this fixed point. If we have access to the deterministic operator F, under certain conditions (for instance, contractiveness of F or F(z) = Vh(z) for some non-convex function h)) the iteration 2k++1 F(xx)) converges to a fixed point.
However, in many applications we do not have access to the deterministic operator F, and we only have access to noisy evaluations F(., WK++1) ) of this operator such that F(.) = TE [[ wx+1) Fx where Fx is the sigma algebra generated by [ur;; W2...., wx]. The Robbins recursion [42 defines sequence [zx] as in Equation (I.I). where {au J220 is a step size sequence. Under some regularity conditions on the operator and the noise, and with the step size conditions > Qg = oo
and Ek=n o² < oo, is known that the iterates converge to x= almost surely 4 SA recursions of
the form of Equation [1.1 underpin a large class of algorithms in RL 500 54 and optimization [22].
This method was proposed independently by Ruppert and by Polyak and Juditsky 43 40 to sharpen the statistical performance of SA. Given the raw iterates {xx }k20 defined by Equation [I.].. Dalyak-Rupper averaging defines the averaged iterates { k as in
Polyak-Rupper Averaging:
Equation 1.2p. It can be shown that vk(y - x²) converges asymptotically to normal distribution which has covariance matrix that matches the Cramér-Rao lower bound [40]. An advantage of this averaging technique is that we can achieve the best asymptotic covariance with a robust choice of step size ag [38). Besides the asymptotic results, there has been long literature on the finite time analysis of SA algorithms, some of which are described in Section 2 Generally speaking, finite time bounds can be categorized into moment bounds (i.e., for some m 2 1, finding a bound on E[[|æ x= [[[]]]] or Eillyk
x [[m]] as a function of k) and high-probabilityy bounds (i.e., finding a bound on IP( [| x=ll E) P( x"I E) as function of 0 and k).
4 Main Result
In this section, we present our main result. Throughout this section, we fix a given norm || lle which satisfies the following assumption.
Assumption 4.1. The function a, b E Rd, we have
|| - 1|2: is M-smooth with respect to the lle norm, i.c., for all
||a + +bbl < ||al|2 + (Vila b) + M |6122
2
3

---

Remark. If the function -- 1 is non-smooth (e.g.. if || ||- loo)), we can employ the machinery of the Moreau envelope
12 obtain arbitrarily close smooth approximations of l|a. Therefore,
Assumption 4.1 is without loss of generality.
Next, we impose an assumption on the operator F and its noisy version F, and on their Jacobians Jz(2) (a) == (F(z) and Jr., (I,, w) == (F(x,w)
Assumption 4.2. We assume the following.
(i): The operator F admits at least one fixed point x², ii..,, F(x*) x²
(ii: The operator F is differentiable, and the matrix (x*) is invertible. Hence, we have
[[Jx(x*) D) >
= min ZERd
| le
(iii): The operator F(a,, w) x (N; Ri-locally psuedo smooth with respect to || -lom-morm. That is, there exists radius R >> 0 such that, for all x satisfying || xx lle S R. we have:
[[Jr (x" w) - (xx - x²) (F(x, w) x) (F(x", w) - x "lle N 11 xl/2
Note that Assumption 4.2( relatively weak and is satisfied for a wide range of operators. For instance, this assumption is satisfied for any contractive operator. Moreover, Lemma C.3 Cimppieess that Assumption 4.2(1) is also satisfied for contractive operators. Furthermore, it can be readily verified that the linear operator ((r) = Ar + b satisfies Assumption 4.2 provided that A is Hurwitz. Also, note that Assumption 4.2(1)) generalizes the notion of smoothness (2). In fact, any smooth operator satisfies this assumption with R = co.
Next, we impose an assumption on the noise of the operator any fixed point x².
Assumption 4.3. For any d-dimensional, Fe-measurable random vector v, and for any fixed point x², we have
1200 2
E exp (X(F(z", ( - F(xx), - < exp
AA20. 0.
(4.1)
Moreover, for any d-dimensional, meamsaurablle random vectors and b, have
b)) S exp (X20=) 1
E E/exp A((J (x",
AA (4.2)
2
Remark. Assumption 4.3 is equivalent to assuming the noise in the operator and the Jacobian are subgaussian [53] An example that satisfies Assumption 4.3 is when F(FR, Wk+1) F((xx) + Wk+1. where {w;} ha are i.i.d. subgaussian random variables. Moreover, note that this assumption only needs to be satisfied at the fixed points æ", and not for every x e IRd.
Next, we state the main result of our paper.
Theorem 4.1. Fix k 2 and & < 1. Consider the SA 1.1 and suppose that for any 8' E (0, 1), with probability at least 1 - 8', we have |ar; x² g S oaJelo .k) for all 0 S i S k, for some function Sc. Then, under assumptions 4.1 and 4.3 for all (o, 1), with probability at least 8, we have
2
ki 5
h: 0
liuk x² 112 5
+1
where
g(6,k) k) log (2)
12(k +1 + C2fs (5,
22
(k+ + + C2 (fs (2. k))²
C.do² fs (5, (k: + 1114E
hi
+
2
22(k +
2²(k + 1)25
6
Csfgl5, ko (k) 1) (ko (g, 1 h) (h- 1
c
hi
2
(k: + 1)2

---

with
σ² a(1 + M)00 -5 (2.
g(0, k) 24 max
-1=)(((: + 1)s
aafe (g:
1/8
+
8
ko
= min
- h
k + 1
2
R
and
9h + M)
<²
C3 3h2 26 22 M)
3
C1 =3u
C2
3+
20
(1 E/2)2
2(1 -)²
C2 3h full
+ MM
a
C3
(1-E)
(1 E/2)²
The proof is given in Appendix B.1
Unlike the case of SA without averaging, where concentration bounds are obtained by establishing a one step recursion [14], here we need to take a more holistic approach and consider all the averaged iterates at once. This involves the added challenge of dealing with sums of noises directly, instead of tackling the noise of each iterate one at a time.
Theorem 4.1 provides a aonmsttti high-pro bigh-probbbility bound for the SA iterates 1.1 with av- eraging. Our bound consists of two terms: č(k: 8/2) and č(k, 5/2). For small enough i such that kn(6/2, k) = k 1, the term ē(k:, 8/2) decays of k. For this range of time. the operator F is not assumed to be smooth, and thus our bound decays slower than the expected 1/k rate. However, for all & large enough, with high probability, the iterates Iy remain in the neighborhood where F is smooth. Theorem [4..]stttee that from that point on, the term ε(k, 8/2) decays as 1 1/k2, and hence not leading term anymore Furthermore, for the SA with a globally smooth operator, Assumption 4.2(ii)) is satisfied with R oc, and Theorem 4.1 simplifies as follows.
1/k5, and thus it is the leading term as a function
Corollary 4.1. Under assumptions 4.1 4.2 with R = oc, and 4.3 for all 8 (0, 1), with probability ((K 6).
least 8, we have 11y x=
In the following subsections, we explore various implications of our main result.
4.1 Tail of the Leading and Higher Order Terms
We first look the tail behavior in our bound. Throughout this discussion assume that fe(ō,) +) is non-increasing in and fe (5, E (log((18)). and that (t k) E (polylog(kk)). Note that this assumption is reasonable as the rate of convergence of the eтror || x= 11 is typically Ō(ax), and the tail of the error ||ara- - x= | is typically sub-exponential or heavier [14]. In this case, our result implies that, if f > 1/2 or N = 0, then the error of the average variable yı is upper bounded as follows
| x 21 O(1/))0((ogg + +oLKk)) (f((0)))))
leading lern
higher order term
Note that the leading term is nab-exxonential, and the higher order term has a tail that is potentially heavier than exponential, depending fs. In particular, this implies that there exists sequence of random variables } such that Vkllyx x=1 S Z5 for all l: 2 O, and such that Z converges to subgaussian as k + oo, although for every < ac, the error / Vkillux - =I could be heavier than subgaussian. Specifically,
have the following proposition.
Proposition 4.1. There exists an operator F and a sequence of random variables (w2).21 which satisfy assumptions 4.2 and 4.3 such that Vkllys x²1| has a heavier tail than any Gaussian for all k while
lim sup P (Vklju - x= 20) <((1-<(be),,
k000
where a, b > O, and (-) is the CDF of the standard normal distribution.
GGiven two norms I|o and I|. we detine the constants lab and uas such that Easll S 1lll S <uelll-le.
5

---

This is consistent with CLT-style results on the limiting distribution of the error x². However, this also suggests that Gaussian can be a poor approximation for the distribution of yv for finite k, as the distribution of the error could even be heavy-tailed.
Note that in Theorem 4. while we assume that the distribution of the squared error | x² ll is upper bounded by fe. the distribution of the squared error of the average 1l - x= 112 is bounded by fg. which heavier. Since the average of random variables cannot have a heavier tail than the original random variables, this must be an artifact of our proof. However, one can easily establish a high-probability bound which, for every finite k, the bound on the distribution of the squared error of the average has the same tail as the non-averss non-averaged iterates. Such a bound is given in the following lemma.
Lemma 4.1. Fix k 2 1. Assume that for any 8' E (0, 1) with probability at least - 8', we have ||0 x= 11 os k) for all 0 S is k. Then with probability at least 1 6, have
ah2-c f(o,k
1y -
x= -x01=
{/2)²
(k 1)E
This result implies that that ||yk xx= 112 has at worst the same tail as || x². However, such tighter tail comes at the expense of sup-optimal convergence rate of (11/k)) instead of (11/k).
x12
Taking the minimum of the result in Theorem 4.1 and Lemma 4.1 we get the best of both worlds, as in the following corollary.
Corollary 4.2. Under the same assumptions as Theorem 4.1 with probability at least 1 - 6, we have
11 x² 11 S min {o ( O (log(1/6)) + + 2mmin
δ (1E(8,0)9) o
ò Ō
Corollary 4.2 shows that for any fixed time step k. as 6 - O. we have 1184- x² E Off( 0)).
while for fixed as k xc, we have Il - = This shows that employing averaging will improve the convergence rate in k, while maintaining the same nigh-probability tail bound as the original iterates. We defer more detailed comparison of averaged SA pure SA to Section
4.2 Tightness of the Leading Term
Next, we discuss how tight the leading term in ē(k, 8) is. For that, we construct an example of a SA where the error is only a constant factor away from our leading term.
Suppose that the dimension is even. Consider a 2-dimensional i.i.d. sequence of random variables (2 such that 2 (O0 (o2 /). Using these, we construct d-dimensional sequence of i.i.d. random variables (wi such that the j j'th element w; is equal to the first element of 2; when odd, i.e., Wij 2i and it is equal to the second element of 2; when j even is even, i.e., we have Wi, = 24,2- Consider the operator F(z, w) = w, and the step sizes ag a for all k 2 O. This setting satisfies assumptions 4.2 and 4.3 for lle = || l12, with 1 and R co. In addition, have the unique fixed point x² 0. The following proposition bounds the error for this case.
Proposition 4.2. For the example above, for all even dimensions d, and for any (0, 1), we have
o lovk
k log(1))
|| 2 luk - x² x=112 $ 115 5.
P
k ++1
Recall that for large small 8, and lle || l12. the leading term in Theorem 4.1 is 2 2/65/Vk
Proposition 4.2 implies that that this upper bound is at most factor of 2.6 away from the error for this example. Thus, Theorem 4.1 is at most this universal constant away from the tightest possible bound.
4.3 Linear versus Non-Linear Operators
We now discuss how our bound depends on the linearity or non-linearity of the operators, and on whether the noise additive or not. particular, this has an important effect on what choice of g maximizes the convergence rate of the higher order terms in upper bound.

---

1. Linear Operator + Additive Noise: Suppose that F( wx) Azy + wk. It is easy to
see that Assumption 4.2 is satisfied with N and that Assumption 4.3 is satisfied with ④ = 0. Hence, with probability at least 6, we have )
(12- )
lly 2= 0 ((1/)))((og((0)))
In this case smaller & achieves better convergence rate for the higher order terms. Furthermore, the tail of the higher order term is the same as the tail of the errors || x= for i 2 O, which could be heavier than subgaussian.
2. Linear Operator Non Additive Noise: Suppose that N = and 6² > Then, we have
1 1ly =I ((1/)))((og((/)) + + (AI+E A x2-s) ) (110((100)(((000))
Here the best choice of g is 1/2, and the tail of the higher order term is heavier than the error | 112 by factor of log(1/6). For instance, if |ay - 11 is Weibull with shape parameter m, then the higher order term is sub-Weibull with shape parameter m + 1.
3. Nonlinear Operator: N O, we have
(1e(0.00))
1l x IIa -
- -0
1:
12-2
Our result suggest that the best choice of is 2/3. In this case, the tail the higher order term is twice as heavy the tail of ||,, x²
In general, we observe that for nonlinear operators, we get the same rate of convergence for higher- order terms, regardless of whether the noise is additive or not, and this rate is worse than in the case of linear operators.
Remark, For the case of constant step sizes, i.e., for { = 0, our high- gigh-probability bound is order O(N2a + o(1) when the operator is non-linear. This is in line with (27] where they show that the bias of a SA with constant step size a and a non- non-linear operator is proportional to a. On the other hand, if the operator linear, we have N 0, and the bias disappears. This is consistent with (36]
5 Application to Contractive Operators
In this section we will apply our results for the important class contractive operators F, which is specified as follows.
Assumption 5.1. There exists a constant % E [0, 1) and a norm || such that
[(())) - F(x2)le S Tel|x1 x2lles
V 222 E Rdd.
Recall that in Theorem 4.1 we require a figh-probbbility bound on the SA iterates {=x]=20- To obtain such brobbbbobability bound, we the prior work [14] that differentiates between two cases, additive and multiplicative noise, which will be studied in sections and 5.2 respectively.
5.1 Additive Noise
We first study the additive noise setting (as it was defined in 14 which is specified in the following assumption.
Assumption 5.2. The random vector F' w++1) - F(x) is subgaussian, i..., there exist and (possibly dimension- deeendeent constant ca such that for any h 2 0 and -e-muauurable random vector v, the following two inequalities hold:
E [exp (A(F(zz, wk+1) - F(zx), [F]] S eexp
AY O,
(5.1)
where || ll. is the dual of the norm || lle. and
Tep (a] (fT wh+1) F ((xr))l))) 5 22o 2
AYA (0,1/20?). (5.2)
7

---

Employing [14 Theorem 2.4] in Theorem
4.1 we get the following result.
Proposition 5.1. Under assumptions
4.1
4.2
4.3
5.1
and
5.2 using
< and
2
((1
28
1/(1-5) with probability at least
8, we have
2 log(2/6) + 3du の²
1
1 kits o (log(1/6))
yk x'112
+ O(M)
11-7)) (A: +
h2-5
O
O (108))
(5.3)
1:25
Next, we aim comparing the high-probabiliig bound achieved by averaging vs the hygh-rrobbbility bound achieved through Theorem 2.4 in [14] with Ç = 1. For the sake of comparison, we assume that - || ||l- In that case we have u,2 and M 1. By Proposition 5.1 with probability least 1 - 6, we have (up to the leading term)
24 log 1/0) + 3(d + 8 (lg(())
J²
lik
112
(k: + 1)
(I (o-7
Moreover, applying 14 Theorem 2.4] with { = and k K, we obtain
32a Lorllog(//// (/0) + 32aa"ccc p)/l0-1aa00000
| x lla 2
(k: + h)
(1 76)2"
for any μ and > (refer Appendix A for caleulations). Here, o² is the variance of the subgaussian noise only at x", while o² is a uniform bound on the variance over all x E IRd. Hence, have 6² < 2²
Our results suggest that for SA with additive noise, averaging could improve the constant in the leading term. In particular, in the first term, SA has 32ad² which is at least 32o Averaging improves this term 2472. In the second term SA has 32 ec + p)o? which the case that ca Rs d (which happens when the noise A(, Iaxa)), averaging improves this term to 3(d + 8 lo2 We will do more specific comparison of SA with and without averaging for RL algorithms in Section 6
least 128ecao². For
Remark. It can be shown that, even if we use a smaller value of h than the lower bound 1/(1-() in Proposition 5.1 concentration bound similar to the one of Equation (.3 (1-%)
28
still holds, albeit with larger constants in the higher-order terms.
5.2 Multiplicative Noise
Next, we examine the multiplicative noise scenario (as was defined in (14). which characterized by the following assumption:
Assumption 5.3 (14)). There exists >> 0 such that
[[ Wk+1) F(xx)le S a(1 [[x]l)),
A 2 0,
where || Ile is the norm from Assumption 5.1
Utilizing 12 Corollary 2.2], Markov's inequality, and Theorem 4.1 we derive the following result:
Theorem 5.1. Under assumptions probubility at least - 8, we have
5.7 and E 1/2, for any 8 (0, 1), with
log( 1og(1/0) 1/0) +
d
N
18k
+
O
8z +
0
k +
AminnI 11-E
Theorem 5.1 provides a heavy-tailed upper bound for the error. Although this is merely upper bound, the actual distribution of the error is indeed heavy-tailed, as demonstrated by the following impossibility result:

---

Theorem 5.2. Under assumptions 5.7 and 5.3 when & (0, 1), there does not exist any > 0 and m such that for all 5 (0, with probability at least
live x I1a 1 Co 1 (log(1/6))
k + 1
The above result highlights a fundamental difference between multiplicative and additive noise scenarios. Specifically, while Theorem 2.1 from [4] shows that simple SA with step size ay = a/(k + h) attains aui-Weibulll distribution, our Theorem 5.2 demonstrates that averaging applied to general SA under multiplicative noise yields a heavier tail than any sub- Weibull distribution. This contrasts sharply with the additive noise scenario, where averaging maintains subexponential tail similar to standard SA, while improving the constant factor of the leading term.
Application to Reinforcement Learning
In this section, we study the application of our result to TD-learning and Q-learning algorithms.
Consider finite Markov Decision Process characterized by state space S, action space A, reward function R(s, a) S x A + [0, Rmax]] and transition probability matrix P. We assume [S] 2 2. The objective of TD-learning is to estimate the value function associated with policy т, defined as (*(s) = o RS,, S.) s]. We focus on asynchronous (D))
TD-Learning:
with i. noise, given by
k+n-1
v((st)) -v((s)))))))(())))))))))))))))))
(i++(s)== = Vi((s) + 0
Σ
R(S) A1) + - (
(6.1)
for all s e S. Here, Sg: ST.... Rid n=, where ft¹ denotes the stationary distribution of the induced Markov chain under policy For each k, {(S) Jo.)ooni represents trajectory following policy æ, with transitions AG T(-SS)), and si+1 P(.S At). We assume that the initial point of the algorithm satisfies (o()) E [0, Bmax] for all s E S and that as = a/Vk l with a/ Vh S We 1-
denote V + Ei= V4.
Theorem 6.1. Under the asynchronous TD(n) algorithm 6. for any 5 E (0, 1), with probability at least 5, the following bound holds:
[14 12 S (1 7) 7rh ) (4 )2
R2
24 log(2/0) + 3d
+ +6
1 k5/4 (llo((1/8).
(k+1)
To the best of knowledge, Theorem 6. establishes the first bound the entire distribution of the error for averaged TD-learning In particular, prior works such as [19 44 36) provide bounds for the raw iterates or use step sizes that depend on fixed confidence level and thus only give pointwise control (i.c., one quantile of the error distribution). In contrast, since our step size is independent of 8, we obtain bounds that control the entire tail of the error distribution for the averaged iterates.
Q-Learning: Next, we study the asynchronous Q-learning algorithm with i..d. noise, given by
Qu+1(S, = Qu(s,a) an ((s.0)))) RR(S,, A&) + max max (Qx - Qu(SR, As)).
for all as) E S x A. where Sa ~ ~ As ~ ( Sx), Sy ~ P(.|Sk,.AA As) and my is some fixed sampling policy. We denote Pb min,,a a nº (s) m) (a|s). We assume that the initial point of the algorithm satisfies Qu(s, a) E [0, Rmax] for all (s, a) E S A and aj = a le + h with a/ e/vh Without loss of generality, this section we also assume |A| 2 2. We denote the optimal Q-function assumption on Q'.
1-7
as Q' and Q K+I Σ Qi We further impose the following common
56
Assumption 6.1. Q" is greedily unique, i.c. for every s S, (s) arg max (s,a') is unique

---

Theorem 6.2. For asynchronous Q-learning with i...d. noise and & = 1/2, under Assumption 6.1
for any 8 E (0, 1), with probability least 1 5, we have
12R
8 log (2/62/1)) |S||A]
1Q - Q' - (1-7)tp
+
(llog(1/8).
p) (k: +
A-544
To the best of our knowledge, Theorem 6.2 establishes the first bound on the entire distribution the error for averaged Q-learning.
We observe that, since the noise structure in tabular TD-learning and Q- Q-learning is the same (both corresponding to additive noise), the bounds are of the same order of k and 6.
Off-ppolicy TD-learning: Theorems 6.1 and 6.2 two instances of RL algorithms which can be modeled with SA with additive noise, as in both these settings the noise is bounded. Next, we study off-policy TD-learning with linear function approximation which has multiplicative noise. In this setting assume have access to matrix 4 E R |i and we denote the s-th row of this matrix by (ss). The goal to find y* E R that estimates the value function as V*(s) (s) RS 0" (osss Here, T
through the solution of the following fixed point equation ty TT ((T")) TT (( () - I is a linear function that projects into the subspace spanned by the matrix 4, and 1 is diagonal matrix, with diagonal entries equal to the stationary distribution of the behavior policy ma. Furthermore, T is the Bellman operator. We employ TD(n) as follows:
(4)))) T
Uk+1 Uk an (S
Σ 1=
[R(S). A + - Tm]]
where S Su. s..... add nh and nT is the stationary distribution over states of the induced Markov chain by following policy wa, and for every k. {(S) A is single trajectory of state-action We assume that
pairs following policy we Ai To(-1S),, St+ P(I Ag). 0 s
ag = a/(1: + h... We denote Ük = E+I Ei=o"
Theorem 6.3. For large enough n, there exists constant probability at least 8, we have
O such that, for any 5 E (0, with
1| - 17 log(1/6) +
++1 + +0
To the best of our knowledge, Theorem 6.3 establishes the first bound on the entire distribution of the error for the averaged off oollcy (D(n) with linear function approximation.
Note that for TD-lcarning with linear function approximation, the tail has ((1/8) dependence, which a sub-Parets distribution. Moreover, TD-learnng with linear function approximation is example of SA with multiplicative noise, and as shown in Theorem 5.2 the tail has Q (((log(1/ (1/5))*) for all 2 1. In partieular, this means that the tail of TD-learning with linear function approximation is heavier than any sub-weibull, but it is at most as heavy as sub-paret In contrast, shown in Theorems 6.1 and 6.2 tabular TD-learning and Q-learning have (log((16)) tail, which is sub-exponential.
References
[1] F. Bach and E. Moulines. Non-stronglyyconwal smooth stochastic approximation with con- vergence rate O(1/n). In Proceedings of the International Conference on Neural Information Processing Systems (NeurIPS), page 773-781, 2013.
[2] A. Beck. First-order methods in optimization. SIAM, 2017.
[3] C. Beck and R. Srikant. Error bounds for constant step-size Q-learning. Systems Control Letters, 12032):10031200 2012.
[4] D. Bertsekas and J. N. Tsitsiklis. Neuro-dynamic programming. Athena Scientific, 1996.
10

---

[5] D. P. Bertsekas, P. Bertsekas, D. P. Bertsekas, and D. P. Bertsekas. Dynamic programming and optimal control, volume 2. Athena scientific, 1995.
[6] J. Bhandari, D. Russo, and R. Singal. A finite-time analysis of temporal-difference learning with linear function approximation. Operations Research, 69(3):550-973, 2021.
[7] S. Chandak. O(1/k Finite-Time Bound for Non-Linear Sro--Tme-Secte Stochastic Approxima- tion. arXiv preprint arXiv2254.19377 2024.
[8] S. Chandak and S. Borkar. A Concentration Bound for TD(0) with Function Approximation. arXiv preprint arXiv:2312 10424, 2023.
[9] S. Chandak, V. S. Borkar, and P. R. Dodhia. Concentration of Contractive Stochastic Approxi- mation and Reinforcement Learning. Stochastic Systems, 12(4):41 1-430, 2022.
[10] S. Chandak, S. U. Haque, and N. Bambos, Finite-Time Bounds for Too-Time-Seeee Stochas- tic Approximation with Arbitrary Norm Contractions and Markovian Noise. arXiv preprint arXiv:2503.18391, 2025.
[11] 7. Chen, S. Khodadadian, and S. T. Maguluri. Finite-Sample Analysis of Off-Policy Natural Actor-Critic With Linear Function Approximation. IEEE Control Systems Letters, 6:2611-2611 2022.
[12] Z. Chen, S. T. Maguluri, S. Shakkottai, and K. Shanmugam. Finite-sample analysis of contractive stochastic approximation using smooth convex envelopes. Advances in Neural Information Processing Systems, 33:8223-8234, 2020.
[13] Z. Chen, S. T. Maguluri, S. Shakkottai, and K. Shanmugam. A Lyapunov theory for finite-sample guarantees of Markovian stochastic approximation. Operations Research, 71(1):147-164, 2023.
[14] Z. Chen, S. T. Maguluri, and M. Zubeldia. Concentration of contractive stochastic approxima- tion: Additive and multiplicative noise. The Annals of Applied Probability, 35, 2025.
[15] G. Dalal, B. Szörényi, G. Thoppe, and Mannor. Finite sample analyses for TD(0) with function approximation. In Proc. AAAI, volume 32, 2018.
[16] G. Dalal, G. Thoppe, B. Szörényi, and Mannor. Finite sample analysis of two-time-ss scale stochastic approximation with applications to reinforcement learning. In Proceedings of the Conference on Learning Theory (COLT), pages 1199 1233, 2018.
[17] R. Dorfman and K. Y. Levy. Adapting mixing time in stochastic optimization with markovian data. In International Conference on Machine Learning, pages 5429-5446. PMLR, 2022.
[18] A. Durmus, E. Moulines, A. Naumov, and S. Samsonov. Finite-time high-probability bounds for
averaged iterates of linear stochastic approximation. Mathematics of Operations Research, :9(1):4544444 478, 2024.
[19] A. Durmus, E. Moulines, A. Naumov, S. Samsonov, K. Scaman, and H.-T. Wai. Tight high probability bounds for linear stochastic approximation with fixed stepsize. Advances in Neural Information Processing Systems, 34:30063-30044, 2021.
[20] E. Even-Dar and Y. Mansour. Learning rates for Q-learning. Journal of Machine Learning Research, 5:1-25, 2003.
[21] D. A. Freedman. On tail probabilities for Martingales. The Annals of Probability, pages 100-118, 1975.
[22] Harold, G. Kushner, and G. Yin. Stochastic approximation and recursive algorithm and applications. Application of Mathematics, 35(10), 1997.
[23] W. Hoeffding. Probability inequalities for sums of bounded random variables. The Collected Works of Wassily Hoeffding, pages 409-426. Springer, 1994.

---

[24] K. Khamaru, A. Pananjady, F. Ruan, M. Wainwright, and M. I. Jordan. Is temporal difference learning optimal? an instance-dependent analysis. SIAM Journal on Mathematics of Data Science, 3(4): 1013:1013-1040, 2021.
[25] S. T. Kong, S. Zeng, T. T. Doan, and R. Srikant. Nonasympiotic CLT and Error Bounds for Two-Time Tcme- Stochastic Approximation. arXiv preprint arXXi:2502.00888 2024.
[26] C. Lakshminarayanan and C. Szepesvári. Linear stochastic approximation: How far does constant step-size and iterate averaging go? In Proc. AISTATS, pages 1347-1355, 2018.
[27] C. K. Lauand and S. Meyn. Bias in stochastic approximation cannot be eliminated with averaging. In Proceedings of the Annual Allerton Conference on Communication, Control, and Computing, pages 1-4, 2022.
[28] G. Li, C. Cai, Y. Chen, Y. Gu, Y. Wei, and Y. Chi. Tightening the dependence on horizon in the sample complexity of Q-learning. In Pruceedings of the Conference on Learning Theory (COLT), 2021. Extended version: arXiv:2102.0654
[29] G. Li, C. Cai, Y. Chen, Y. Wei, and Y. Chi. Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis. Operations Research, 72(1):222-236, 2024.
[30] G. Li, Wei, Y. Chi, Gu, and Chen. Sample complexity of asynchronous Q-learning: Sharper analysis and variance reduction. IEEE Transactions on Information Theeoy, 68(1 68(1):448- 473, 2022.
[3]] G. Li, W. Wu, Chi, C. Ma, A. Rinaldo, and Y. Wei. High-probability sample complexities for policy evaluation with linear function approximation. IEEE transactions on information theory, 70(8):5969-599 59999,999999900 2024.
[32] Li, G. Lan, and A. Pananjady. Accelerated and instance-optimal policy evaluation with linear function approximation. arXiv preprint arXiv:21 /2. 13109, 2021.
[33] X. Li, W. Yang, J. Liang, Z. Zhang, and M. I. Jordan. A Statistical Analysis of Averaged Q-Learning. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), volume 206, pages 2207-2261, 2023.
[34] R. Liu and A. Olshevsky. Temporal difference learning as gradient splitting. In International Conference on Machine Learning, pages 6905-6913, PMLR, 2021.
[35] A. Mitra. simple finite-time analysis of td learning with linear function approximation. IEEE Transactions on Automatic Control, 2024.
[36] W. Mou, C. J. Li, M. J. Wainwright, P. L. Bartlett, and M. I. Jordan. On linear stochastic approximation: Fine-grained Golyak-Ruppert and non-asymptotic concentration. In Proceedings of the Conference Learning Theory (COLT), pages 2947-2997, 2020.
[37] E. Moulines and F. Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Advances in neural information processing systems, 24, 2011.
[38] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximatinn approach to stochastic programming. SIAM Journal on optimization, 19(4):1574-169 2009.
[39] G. Patil, L. Prashanth, D. Nagaraj, and D. Precup. Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisation. International Conference Artificial Intelligence and Statistics, pages 5438-5448. PMLR, 2023.
[40] B. T. Polyak and A. B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and optimization, 30(4))838-855, 1992.
[41] G. Qu and Wierman. Finite-time analysis of asynchronous stochastic approximation and Qelaarning. In Proceedings of the Conference on Learning Theory (COLT), pages 3185-3205. 2020.
[42] H. Robbins and S. Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951.
12

---

[43] D. Ruppert. Efficient estimations from a slowly convergent Cobbins-Mome process. Technical report, Cornell University Operations Research and Industrial Engineering, 1988.
[44] Samsonov, Moulines, Q.-M. Shao, Z.-. Zhang, and A. Naumov. Gaussian Approximation and Multiplier Bootstrap for Polyak-Rupper Averaged Linear SA with Applications to TD Learning. In Advances in Neural Information Processing Systems, 2024.
[45] S. Samsonov, D. Tiapkin, A. Naumov, and E. Moulines. Finite-sample analysis of the temporal difference learning. In Proceedings of the Conference on Learning Theory (COLT), 2024.
[46] S. Samsonov, Tiapkin, A. Naumov, and E. Moulines. Improved High-Probabilie Bounds for the TD Learning Algorithm via Exponential Stability. In Proceedings of the Conference on Learning Theory (COLT). PMLR, 2024.
[47] Shalev-Shwartz et Online learning and online convex optimization. Foundations and Trendso in Machine Learning, 4(2):107-194, 2012.
[48] R. Srikant. Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning. arXiv preprint arXiv:2401.15711 2024.
[49] R. Srikant and L. Ying. Finite-time time error bounds for linear stochastic approximation and TD learning. In Proceedings of the Conference on Learning Theory (COLT), pages 2803-2830. PMLR, 2019.
[50] R. S. Sutton. Learning to predict by the methods of temporal differences. Machine learning, 3:9 44, 1988.
[51] G. Thoppe and V. S. Borkar. A concentration bound for stochastic approximation via Alekseev's formula. Stochastic Systems, 9(1): 2019.
[52] J. Tsitsiklis and B. Van Roy. An analysis of cemporal-differeet learning with function approxi- mation. IEEE Transactions on Automatic Control, 1265):674-690, 1997.
[53] M. J. Wainwright, High-Dimensional Statistics: A Non-Asymplotic Viewpoint. Cambridge University Press, 2019.
[54] C. J. Watkins and P. Dayan. Q-learning. Machine learning, 8:279-292, 1992.
[55] E. Xia, Khamaru, M. Wainwright, and M. Jordan. Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning. IEEE Transactions on Information Theory, page 1, 2024.
[56] Y. Zhang and Q Xie. Constant stepsize Q-learning: Distributional convergence, bias and extrapolation. Reinforcement Learning Journal, 3: 1210-120,, 2024.
13

---

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

---

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

---

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

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper is pure theory, and it does not include any experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htt.l//www...e.eo.....ooooooooca
Answer: [Yes]
Justification: We have reviewed the NeurlPS Code of Ethics and our research conforms in all aspects with this document.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is pure theory, and we are only analyzing already known algorithms. Hence, it does not have any societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

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

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper is pure theory, and does not include any new asset.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question:
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This paper is pure theory, and does not include any experiments.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper is pure theory, and it does not involve any crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
19

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standale components.
cc/ Please refer to our LLM policy (https: :itps://ae /ttess:///uurpipe http///errsscccoooeeeeeeee ccc/oonfeeences/////ocoooooccss/ 2025/ LLM) for what should should not be described.
20

---

A Analysis of the case study in Section 5
The generalized Moreau envelope norm
|| Il was introduced in [1]. and it is defined as
|
inf "ERd
|ull + 1 || u|l
By choosing |
Il is M-smooth. Furthermore, we have || Ilm = ||. /le/vI n. Hence, Vem lom VI+ μ. Also, choose a a/(1 7e) with > 1. Note that Umer = Ume Uler / /vI++ + Moreover, the contraction factor under the norm ||- ml is Ye.
lle. as shown in [14].
B Proofs of main results
B.1 Proof of Theorem 4.1
For ease of notation, we drop & from fe(ō,k).
We define the event
(8) = f||2; x² 11: S (;,(( k) for all 0 0 k).
which we assumed to have P(Fs)) 2 For ease of notation, we use Eg instead of (x.
In order to obtain a tight high probability bound, we need to exploit Assumption 4.2 4.2(i which only holds whenever |.0g x=" le S R. We can ensure that with high probability, the SA is within the local smooth range the operator after a certain time. Define ku 6, k) 2 to be the smallest number such that (6.A)) (6, k)) < R²2. Solving for the smallest ki k) we have
ko(5, k) = max {o.
(
[o k)
1/5
}
1
R2
We define (0,5, kt) == min [Ro(6, k),, 1: + For ease of notation, unless otherwise stated, we
denote (o, k) by kg-
For any lo 2 0. we have
1
Uk
T2
1:
+
t=0
Ro
1
1
+
34.
+
4:
+
define
ko
k
Th = k
(x:
x²)
and
0k:
(x:
x²).
k +
=
Ao
It is clear that Wh Uk Ut. Applying
both sides, and using triangle inequality, we get
llve x ||e. < || + ||
(B.1)
We study [[ lle as follows. For every sample path in the event FL we have
1 lle
x²
b
1=0
kg
x" ||e
(triangle inequality)
21

---

kg-1
Vas
( - 110===11== S Vasfeld', in Eko)
k+1
==
ku
Vaf(ō, ko)
(x: + 1)552 dx
k+1
Vaf(ō, Ku) (
1 + h1) 1-122 (h - 1)?-
(1 {/2 + 1)
Hence, for any k 2 with probability at least 8 we have
U 112 (f( [(ko + 1-22 (h - 11-1)
E(k,0).
(B.2)
(1 - {/2)² 1)2
Next, we study 11 We have
(Jf(x") (xx - x²) (F(#k, wk+1) - xK) (F(x", wk+11 -x")
+ [[Jr.. wk+1) (xx - x²) (F( wk+1) -xx) + (F(x", x²)]
[Jr(x") - -rr (s", (6 ((k++)) x²).
Hence,
b
(k: + 1) -I)
-I) (0x) = Σ (1F(2,))411) xz)l
ho
Σ (F(x", (F(x",1411 -xx)
Rn
(JJr (x",wi4)) - [) x²) (F(xs, (141) - xx)) + (F(x", - xx]]
Ka
+
[Jp(")) [ x*)
k=
k
Ti+1
D4
O4i
kp
Σ (F(2", ( xx")
+
(J (2", wi+1) - [)(2 - x²) -FF(a,, w:41) xx) + (F(x",,;+1))
w:+11 -
x*)]
2 Kg
+
[Jp(x') - JFn (x", (1)1))(00 x²).
(B.3)
Rm
By Assumption 4.1 we have
+ M
aa + b1l < ||al12 + (V |V| 12, b)
|b11
2
||bllc + M
||all2
la 1
2 |aa
(Hölder's inequality)
< ||a||2 + |||||_|66| + M |111
Lemma 2.6])
M |bb|2
< ||a||2
+ 11112
(Young's inequality)
22

---

3
1 M
2 ||lle +
|1bll
(B.4)
Hence, we have
(k 1) 1ūv =x'llc Exss
s (k + 1)² [1[ (2-) 1) 1-xx x²))l" Ex+1
(Assumption 4.2 ii
3
Σ (F(x", wi+1) - -x*)
1 1x
2
k=
1 M
Σ 2i+1
a2
+ [[J (x", w6+11 I)(x; x²) - (F(z, w[+1) - 23) + (F(x", w(+11 - x²)
+ [Jr(x*) JF. (x*,, ((+1)((x;; x²)) 1 Bess
(Eq. (B. and B.4
3
(F(x", wi=-1) (001)-x")) -x")
1 Ex41
2
b
3(1 + +M)
Σ
Fi+1 Zi
1 E74s
2
ki=ko
3(1 + M)
Σ
[J (r",
(++11) - 1)(x; - xx))
2
k=
2
[F(xx, xx,) + (F(x", wH+1 (F(x*, -x")]
1 Extz
3(1 + +M)
Σ [p(+*) - JR. (x", (x+)))((; -x))
L 1
2
ki=ko
(triangle inequality and (a + b c)2 S 30² +312 + 36
3
(F(x", (w--1) x²))
1 Ex41
3(1 + +M
Σ
Fi+1 Di
1 Ev4r
2
No
3(1 + M)
[[[[Fr. (x", - [x - x²)
2
k=k
(F Wi+1) - x;) + (F(x", w.+1) - x² )11_] 1
(triangle inequality)
3(1 M)
Σ [Jx(x*) Jr (x", we wx)1)) x²) 1 1
i=ko
3
k (F(x",un w)+1) -xx)
| |
<
1 Ex+1
2
k=
23

---

3(1 + M)
Ti41
Fx
3(1 + +M)
h
2
N2
||:: x² z²11²
1 Ex4s
(Assumption 4.2 (ii))
k=
3(1 + M)
Σ
[J+(x*) - JFw (x", (x1z1)(xx (alla--x)) x²)
E
ko
Let us define
k: +
()- + 1)5
dE
min u2 a + M) k)h
We have
elepp
1 =2'll B141)l
A
3
EI
exp
(F w141) - xx")
E
(k - 1)22
k=
.exp
A
3(1 + M)
Σ
Titl Ij.
1 F
(A: 1)2
2
k=ku
0s
A
3(1 + M)
.exp
N2
Σ
||0 x x²112²
.1 1e
(k: 112
2
1=
A
3(1 + M)
k
]
exp
Σ (Jp(²") (x" w++1)((ss - xx")
1 Extt
(A: 1)2
2
2
6ÅR
cxp
Σ (F(x", wi+1) - -x*))
11 Ex41
(I + 1)
k=kko
T
1/4
E
exp
(1 M)
Σ
2i+1 Iz
1 Ex41
(k: + 1)2
k=ko
22
2
1/4
E
exp
(1 +MN2
Σ
| x²11
.1 E
(k: + 1)2
km
1/4
E
exp
(1 M)
Σ ()((²) JF, (x", w1+1)((2, x²)
1 Er+s
(k: + 1)2
(B.5)
where in the last inequality we use Cauchy-Schwanl three times. We study each of the terms above separately.
24

---

The term Ti: By Assumption 4.3 and Lemma C.1 it follows that Σ (F(x" (k- - ko + subgaussasssin Furthermore, by Lemma
,002",25---0 (0--1) x²) is
C.2 we have
1/4
6Λ (k + 1)2
T1
E
exp
Σ (F(x" (1(x",w;+1) w++1)
x²)
LEEtt
ii=ko
h Σ (F(x", (F(x",w++1) -x")
2
1/1
6Λx
exp
U22
.1 Ex+1
(k: + 1)2
limko
k Σ (F(x*, w(+1) x²))
21
1/4
Exp
(k - 1)2 42
k=
1/4
1
a2 0²
d/2
R++11
4/8
12 62
k+1
3ddx 1 02
exp
++1
(we use d
22ug
k+1
where in last inequality we use that 1/(1 - x) S exp(2r) for all x S 1/2.
The term Ty:
1/4
T3 =
E
exp
6Λ
(1+ M)
34
xx
I++1
E
(A: + 1)2
i=
5
exp
(1 + (M)
Iko
Tk+1
(k: + 1)2
Okko
O
]
1/4
1
1
+
(I
x²)
1 1
a1+1
ai
No
(a)
18Ax
|
x=1 1
||
x=112
E
exp
M)
(k: + 1)2
2
ag
1/4
+
Σ
(x: - x²)
11
0++1
04
(8)
18Ax
I -
x 11
|
E
exp
(k + 1)2
(1 + M)
0
o
k
]
1
+
||, x=1lo
0641
(c)
[(6
25(8, k)
1
-
S exp
(1 1++1 M)
+
+ f(8,k)
Σ Va
2(k + 1)2
a.ko
ay
ai+1
a;
L+=
25

---

(d)
f (1+ M)
1
Σ
exp
2(k + 1)2
Okko
+
Voili+
Li
(6, 2(k + 1)²
1
2
22
1
exp
(1 (1+M)
akk
0
(i h)) h
Li
1o+1
(c)
exp
(,, k)
M)
1
2
2
1
(k + 11)5/2
2(k: 1)2
OKkg
O
(1
E/2)
(6, k)
1
2
<²
exp
2(k 1)2
(1+ M)
O4k
a
+
(1
E/2)
(6, k)
6
S exp
2(k: + 1)aa (1+ M)
3+
(k: 2 ko)
(1 E/2)²
(1 + 1
5²
S exp
3+ + (1- - E/2
20(k + 1)2-3
where (a) and (b) are by triangle inequality and (a + b + c)² S 30² + 312 + 3c2, (c) is by the
assumption of the theorem, (d) is by (x + 1)s x s E/ for x > 0, and (e) is by integral upper bound of summation.
The term T3:
2
1/4
6Λt
T3
E
exp
(1 + +
Σ
||: - x 112
. Ex+1
(k+ 1)2
1=
2)
1/4
E
exp
(1+ 2
Σ (6,
(k: - 1)2
ko
(1
x=112 S aufe(8', k) in Ex41)
3 (A,,N((((6,k)) 2(k: + 112
exp
(1 + M)
Σ
ai
(
3a N² (2((, (1+M)
1 (a + his dz
S exp
2(k + 1)²
Wo-1
3a 3a N (f((,)))
(k (k+ - (Ko + h 1)2-8
exp
(1+M) M)
2(k: + +1²
5-1
3a N2 (F(O, k))2
(k + 1)2226
S exp
(1 + M)
(using 1)
2(k + 1)²
(E 1)²
9h 28 (22 No. 2 + ()( k))2
exxp
2(k +
where in the last inequality we used the fact that (k + h)2-25 26 < (k: +
The term Tı: It is easy to see that, almost surely, we have
k
1 Ba+3
[J Jr., (x", w141))(as-17 1m
[J (x", (0))))(( -x") 1")
Amm Ro
8
Hence, we have
1 Ea+1 [j - (x", ( x²)
=
1 Ext1
Σ k=
[Jx(x*) - Jr, (2", w - x² =0)1E
k=
26

---

Ex41
[1 - JF. (x", wi+1)l(a; - x x")1E.
1=
(Jz(x*) Ju w3 w;+w))(2a; x²)1E,
i=ko
We now show that Assumption 4.3 implies that
[xJp(x") - Jr.. (x", wk+1)) =0.
Indeed, by Taylor expansion of the inequality 44. we get
E[1 + (((J)((')) JF (x", wk+1))a, ((A s1+ 12021aa1216111 + OO*).
If we had (()p(z*)-JJp (x", [ + O, then we would have (2(A) < ( which is a con-
tradiction. It follows that the sequence of random variables given by (x(x)) JP., (x wit (
x" LE,,, is Martingale difference and, conditioned on F; they are [ x E1 |l=-ubgauussian Hence, by the definition of the event E,, the random variable [Jp(x*) JF.
Witt))(m;
L (6, k)),,-uugaausiann Jr. (x", (iit)) (x: - x²) is 82, k)) Ei ar-subgaussian. Furthermore, by Lemma
Thus, Lemma C.1 implies that 1 E Ei=ko [Ja(x")
C.2
we
have
1/4
67A
T1
E
exp
(1 + M)
Σ (Jr("*) JF. (x" w.+1)((( xx))
1 Ee+z
(k: 1)2
k=
1/4
d/2
12a Ax(+MM (1+1))²
82 f(5 k)
k Σ
as
k=
1
d/8
12 Ac f(8,k) (k+1)²
Σ
ai
3u Bud + M)
k
& exp
(2)((,))
Σ 04 ki=ko
(A: + 112
aud M)
(A: ( (1+1))1- h)1-5
S exxp
0² 0²](5,kk k)
(integral upper bound)
(k 112 3h Bug + M) (2))))((88)) ((8,k)
1-E
< exp
(k 1) - E
where in the second to last inequality we use the fact that 1/(1 - x) S exp(2xx for all x S 1/2, and it holds when
a2uggan((1+ M)
(I + h)
(ko + h 1)2
f(5,k)
<
(k + 1)2
1-
2
which is satisfied because we have
() + 1)2
A < 24 al + M)02 k) h)2-
Finally, putting everything together, we get
P( Ers. 2) s - [exp(A<0> 11ix Ex4r)] )]
27

---

S -
exp
++1
9h f(o.)
5²
exp
3+ (1 - E222)3
2a + 1)2-
3/2 26 a² A () + +M)
exp
2(k +1) -0----)) E)²
3h Su add M)02 f(,,k)
exp
(k: E11
Making the right hand side equal to 6, and solving for we get that, with probability at least 8,
3u
1 1| 1 1x++
I
log (1/6) + (2 +)
AuUZ
9h + MM)(O k))
6²
3
2k + 1)2-3
E/-2/
3h a 2 (1)
2v + (1-
3h E (k + 1) -
+ M))² ((8)) k)
=: E).
(B.6)
Note that, for any two events and B, we have
P(AnB) = 1 - PPA B²) 2 1- 11111(A7 P(A9) P(B)) = P(A) +P(B) - 1.
Define
okk,))= = (Ve(N:, 8) + V 2
Then,
P( 1=' S c(k, 2 PP (11xxxll [1l || S E(ki; 6))
(Eq. (B.1
2 PP (11lxa11 [(k; 0)} n {lluele s o(k))))) 2 Pf - E(ks 5)} n Ex+1) (Ex+1 C AllTelle S E(k,, 5)} due to Eq. B.2
11 R211 S [kk,8)} n Ex+1) (for all w E F 1l Ex (w) = 1)
2 IP (1 12 LE S E(k, 6)) + ((E++))) - (Eq. B.6 and definition of E
(union bound)
2 8 - 5.
Hence, with probability at least 8 (with abuse of notation for substituting 28 by 8), we have
1/ - x =1 < (VE(k, + VE(K,
ε(K, 8/2) + E(,, 8/2) + ((2
9(8,
du
22 +1) log (2/8) u2 +1)
9h + ()5()/2,k)
g2
3 (1- 2/2
2a(k + 1)2-E
3/2 28--2,00 25 N2 (() + M)
2k + +1)25(1 - 5)2
31 1 3h--5 ad + M)62 (5/2,))
(k+1))+E(1-9 g)
a/(0, (8))
(h 1)2-2/2
(1-E/2)2(k+1))
28

---

2/af 1) ()(((6///2))) h) 1-22 (h 1-'
(1- +
g(6,h)
3u22dō²
x
log(2/6) + v2 + +1) ( + 1)
9/5 + M) k)
5²
20 1)2-
(1- E/2)3
3h 26 a N2 (f(0/2, M)
2v² + 1) E)²
1/2
3h u ad + M) f(6/2, (A: 1
where the last inequality follows from BB. and (B.6). and
24 max x2 a:1 + 1)
g k))
(1 {) + +18
B.2 Proof of Proposition 4.1
Consider the recursion
Tb+1 (1 ax) + 0ggh+12k
where wk ~ (N( 1). It follows that
Ik = (1 - Ck-1 + -
k-1
(1 a; 0,w1+1).
i=0
Hence,
K-1
F0
II
(1
a,w441).
K= 2=0
Without loss generality, we assume that va > 0. Consider the event Eg = (w; 2 0, 1, 1.....k]. and suppose that k > 2. For any > O, we have
exp(tyn) 2 E,, exp(tyx)
tx²
2 1 Fg exp
k +
(1 ao + an (1 ai + k1
1 E, exp
Fnl
h: +
2 1 E. exp
k+1
Then,
100K0 W1
E[exp(tyx)]
E
1x, exp
k Koagan W2
E
1 E, exp
P(wy 2 0, = 00.=3.4.. kk).
We also have
exp
Zoogaatwy W2
1E, exp
Tgagattus W2
]
| + L [(0 exp
zoagattuy W2
k ++
1: k+1
4 +
29

---

10 W22
+
(an mez <0) exp
k: + 1
Eu0na W2
To t20 W02
21
1 E, exp
+ EE
(we.ar2<0) exp
k+1
h +
Ti000a1 tuy u22 k+1 1
S 21
1 Eg exp
+ 1.
Hence,
Toagartu102
Blexp(tyx)] 2 E
exp
P(w; 2 0, 3,4, 2,,,,...kk) ,k)
P(w; 2 0, = =3,4, ..4,...,
k ++1
Fg00g0r w2
]
(62)
E exp
++1 1
which is infinity for 1 > (k + 1)/ (=g0ga1))
Next, consider a, =a/6 + h)d such that og < 1/2. By Markov's inequality, we have
P[[2; > t) <
2²
2
B[(1 a, + +
1-1
- (1-a))2+00
+
==
2aj + 20²
exp
exp
aj
1=
a
a
exp
2
(1 - (i - 1 h)s
(1- (1-))h--1) 1)5-1
a
2
exp
(1 (i - hyε-1
where the last inequality holds for some constant e > 0. Then, for h > 2, we have
P(|z.| S for all 0 I i = k)
P(1 > for some 0 i < k)
21 Σ P( > c)
k Σ
C
a
2
exp
2
(1- E) - + h-5-1
1=0
21 C
2
exp
[1 {) 1 1)--T
a
dr
21 d
(x - + h3s+I dx
2
d 0k
2 1
2
30

---

Hence, with probability at least 1 - 8, for all 0 S i S k, we have |o;|² - c' a/// This means that f(ó, k) c0/8. Therefore, by Theorem 4.1 with probability least 6, we have
1y 2 S log(1/8)+ +1 (1//k).
The result follows.
B.3 Proof of Lemma 4.1
The proof follows from Equation (B.2). and by assuming ko In particular, with probability at least 1 - 6, we have
llyk 21133 af(ō,k - 1) ()) (h 1) --2-))
(1- + 1)2
af(6, k + +)(k+)))++
(1 - ( (k + 1)2
al 5 k + 1)
E/2)a(k 1)$
B.4 Proof of Proposition 4.2
First, note that
3D 10
Wk
1/x
k
In addition, this example satisfies Assumption
as
[exp (X(F(a", wx+1) F(x") o)) [x] = E (exp (W]+1,0))]
= E exp
A
Σ
E
exp
A Σ
Wh+ + Σ
WK+1J12
j odd
even
exp
A
Σ
Us + A24+1.2
Σ
add
j even
E
exp
\
Σ Mi
exp
AER+1.2
E Bj
odd
j even
x X2
X2
E
exp
Σ Ui
E'
exp
Σ Ui
2d
x3 32>2l11113
< E
exp
2d
x02>2
< E
exp
2
For the sake of simplicity, we assume Zo = 0. Then, we have
V 1oo2 log 1/8)
| l| > 11y x=112
k: ++
PP ( (Vko² log(1/))(1)))) - || 2 (k: + 1))l
31

---

k 1 +
P
V koo log(1/1(1/5) ||z0|l2 2
P
koo log(1/0)
|| |2o0|22
-|/20ll2 +
Σ
(triangle inequality)
P
Vho² 1og(1/0) 2
W
2
P
v /ko22 log(1/6) N
Wi.j
2
+
24,2
P
v 2 log (gg(1/)) 2 V
2
d
Σ 24
P
v 2 (og()1 2
2
o²k k:
2x
2 1og(1/8)
"2 2/ drdd -
re
B.5 Proof of Theorem 5.1
Since the c-norm can be non-smooth, prove concentration result on the error we use the generalized Moreau envelope
M (z) min WERd
214 | u1l
where || |ls an arbitrary smooth norm. Then, we have that (-) (-) is an L/μ smooth function with respect to || ||s- Moreover, the Moreau envelope defines the norm || || / (-)... For a more detailed discussion about this function, please refer to [12].
Since Assumptions 5.1 and 5.2 are satistied, and a; a/li + h)s, where & (0, 1). Then, by choosing a 0 and (2E/ (e)a)) for any d and K 0, using the result from 14 Theorem 2.4], we know that with probability at least 8, we have for all i 2 K that
T log(1/8)
Da((i + h)--5 - --
|2:
x 112
+ E22l x=* exp
(i h-s
2(1 )
0s + E log (i + 1/2
+
(B.7)
+ hhE
where
160 2 M.cx 2 0
9o
U
02
f2
cM
32

---

32ec,o Lui aa
63 ((1 70)a 1ulc
2 a
C
16eu CM Ca La
pl (1 9ic)
32u 2
c.M 0 U 25,
C6
with 9. (1 [1 + pm j4/2 (1 + )1/2 and D 2(1 4c). Next, choosing K 1, we get that Equation (B.7) holds for all 2 1. In addition, since 02 2 and t 2 0 for = 1,4, this bound
1/2
holds well. Hence, for all i k, we have
t log(1/6)
E2 22 x² 12 + his exp
Da((i + - C + Eo log + +1)
| x² 11 < ai
+
2(1 ()
E log(1/0)
ê + èa log + +1)
ai
+ d1 +
(B.8)
fc(6,))
where
02
20
211 + h)
exp (- Da(li (()((it))---- 1-1---11²0 (2-hh-1-) (o00)((-----))))
(1-31)/ <0c.
d = sup 120
a
2(1 (1)
We get the result by directly applying Theorem 4.1
B.6 Proof of Theorem
5.1
From the proof of Theorem in 37 for h large enough, we have
E
Fi] S (1 B1os) + 320
(B.9)
where u, = || - x a=1l + 8zas;
xi+1 - x²12 1|2 for some positive constants 31, 32, and Bg. Define
# + 4,2 Σラ aj
4
is k i k.
M,
Mr
Next, we prove that (M, 120 is supermatringale:
(1 320;) + B.0g
B[M <E
4,4 Σ Gj
(by Eq. B.9
a1+1
j=i+1
(1 320ks Wu
<
+ +43
aj
(by a./a 4)
1+
==i
U1
< E
+ 4
aj
z=1
-M,.
In the last inequality, we used the following
af 1 - 32ar))
( 1i+h (ith+1)s
(1 1
B2
=
it h
( + h)s
i h
28
3za
exp
ith
(i + h)s
33

---

i+h 20/(++1)
82a
exp
+ h
(i + h.5
2
B2cx
S exp
i h
< 1.
(for h large enough.)
Hence, by Ville's maximal inequality, we have
E MM
P sup
M, 2 e
120
e
ua/ağ + 4,34 Σソ Oj
Hence,
a0/a + 481 Σ j= ag
P sup Mj <e >
120
By change of variables, get
Uo/ + 4/4 Σ 25=
P
sup
M4 i20
11-5. 8.
6
Hence,
40/a + 4,1 Σx Zj=0 aj
1 <P
Mi <
Vi 2
1
u + 48 =0=000 S3
x² l1:
44 siss
1
un/ a + 4,4 Σx 0i
P
||2; x² 1122 <
44 Sisk
/
0(61/2-6/3)
Applying Theorem
4.1 with fe(d,k)
get the result.
B.7 Proof of Theorem 5.2
The idea of this proof is borrowed from the example in [14 Example 2.2].
Consider the SA presented in Equation 1.1) for a 1-dimensional linear setting with F(x, w) = wa. In this case, let (wk+1 1220 be an i.i.d. sequence of real-valued random variables such that
P (wx- = a + N) = 1/(N + +1 and P (wx = a - 1) = N/(N 1), where a E (0, 1) and N 2 1 are be equivalently written
tunable parameters. Note that the update equation
Tk+1 (1 + (WK+1 1)0a)
(B.
In this example, have 24 E IR+ for all & 2 and x- 0. To begin with, there exists ko 0 such that
aalaa + N -N11) 1)
< 1 <1+a
ko.
(B.11)
2
As result, we have for any À > O and & large enough that
Tep (A(A: + 1)81 v/2 1)(²}{²
34

---

E
cxp
Xay (A: + 1)88
k+1 1=0
18
j-1
E
exp
Xxo 11)
Σ
II
(1 + an(w5+1 -1))
k+1
j=0 2=
Xay (k+ 1)8²
k+1 EII
a - -1)) 1))
(N + 1)ee
exp
1 0
1
Xu (k - 1)88
k+1 Σ II
a
(N + 1)8
exp
Kiy +1 im
W3
1
Xuo 3 (k++ +1)8"
2
1
ailaa N Oola+N-1))
(N + 1)8
exp
k+1
exp
2
b=
i=ko
xog (k+1))
1
Σ
a(a+NN-1)
2(1-E) ((i+h) ((++)))-(())))))-)))
-kl((N+1)
exp
exp
k+1
j kg
+1
Ak-(k
1
exp
(k 1) 2/(0(1 E))
((++h)=-5 (ko -k) [2/(((-)))] 3
k
a(a+NN1)
Σ
- k: ln (eln(N+1) +1)
x
2(1-E)
8
Aar (k+133)
exp
(A: (k+1) 12/(3(1 E))
2/(311-5)) 3
Na(++N-1)
-kIn(N+1)
x
2(1-E)
J=kI
(g)
da (K+))0))
1
2 exp
(k++) 2//((11 5))
8
(o(atN-1)
( -h)))) 2/(8(1-E))
x
du
II -1)
2(1-E)
(b)
2 exp
Ae (k
(k (k+ 1) 2/(((1 (2((((1-5)) =0) /
(clat-N21 ((++1)32/8
2(1-5)
33
- -(210011- - E))) (u (u+h)2/8-1++ 1+ (i) 15) du - -kD(N+
35

---

IV exp h
LnN(N + 1)) -
exp (0(A2+3))).
where (a) is by lower bounding expectation with of its terms, (b) by a + - >>>>>>> 0, (c) is by Equation (B.II). (d) follows from
k-1
Σ i=
04
a dx
1- ((k: + +1) - (Ni + h))
(B.12)
(o h)e
kp
(e) is due to the fact that for any r > 0, E" 2 p. /ml for m E N, (f) is due to picking k 2 Ko + such that
a(a+N-11 1 (ko 2(1-
1,
(g) is due to an integral lower bound similar to Equation (B.12) and (h) is due to Bernoulli's inequality. Therefore, for any 3 > 0 and 3r > O, we have
lim inf E exp A(k
Ux - oc, AY > 0.
20000
As result, according to Lemma
14 Lemma 4.1]. there do not exist K K2 > 0 such that
+ 1)
2 k
s Ki exp (-Rge"), Ve 0, 2 0.
A change of variables finishes the proof.
B.8 Proof of Theorem 6.1
First, we verify that the assumptions of Theorem 5.1 are satisfied.
Assumption 5.1 Firstly, for tabular TD(n) algorithm assumed that (s(s) < Rmax/(1 7) for all s E S and 2 O. Furthermore, TD(n) can be written in the form of (L.] with
(F(V,, wx+1)),
(s=sp}
Σ
(R(S)) A (e(( va(SEt) Vi(
("V(((S)) Vi(() + n-1
=1(==SP)
Σ r'R(S + Vi((),,
(B.13)
where Wh+11 [(S) Aplosssn In addition, we have
(F(V))), = Σ ?"(P") Va(s) Σ (PT) ER(S +1--
where the matrix pr is the transition probability of the Markov chain following policy ा i.c., have
PS. Σ P(s' (,)))((aa))
Furthermore, we have
F(V) (1
where M is diagonal matrix with diagonal entries μr,,, and T is the Bellman operator. Hence, we can write
(1 --0)=(---U~>( +
Moreover, we have
A Σ 160,0' - -
A
36

---

8 Σ [M -1- (Por)))))o))))
> 80.8' Σ 1000 (s) - 7thh (P=))
Σ 100,0' (s)
1 (s) + 7"h (s(
1 (s) + (s)
(1 7" (*).
(B.14)
Now, consider the matrix 8= E | where B = (1 (1))))((())1111 Note that C AA + B= is stochastic matrix, and its corresponding stationary distribution is vt such that (N*)T (TT) = (F*)T Further, we have
V/ Σ VyzC
Σ
U (A + )
(s))
|S]
(1 7"h Plinn
(B.15)
|S]
where Pminn min, (u" (s)) Let pick an arbitrary p 2 2, and denote weighted p-norm with weights Da= We then have
|| -llur.p as the
[[F(V)) - F(V2)
AA 12)llE=
Σ vJ (s) 12))
Σ (s)
Σ A (V1 v2)(s')
Σ (s)
Σ
A
Σ
Age
(V1 - -V2)(')) )r
"
ax!"
nd A
p
Ev
Σ
ATT
A
88'
((V2 - (s'))
38'"
AT
(Jensen's 's inequality)
PP11
Σ (s)
Σ
A
Σ A ((V - (z)
Σ (s) [1 (1 7"hh (}
Σ Abr ((V1 (s'())
(by (B.14)
Σ (T) (1- (s))
Σ CT, ((V - V2)
$ - (1 - ) Wmmm p-11 Σ (1) Σ C ((V) - V2)())))
= [1 - (1 - 7xh m
p-1 Σ v (d') ((V 1=)()'))
(I is stationary distribution)
37

---

= =1- (1 P
=
10 [[1 - V2ll==
p-1
Therefore, F(V) is contraction with respect to I|ut,p with contraction factor %
(1-111100 (1-7") Min! 1/11/p, and hence Assumption 5.1 is satisfied.
Assumption 5.2 Since the state and action space are both bounded, the noise in the update
of TD-lcarning is also bounded. Hence, Equation (5.1) is satisfied for some o > 0 by
Hoeffding's lemma. In addition, Equation (5.2) is satisfied due to Lemma C.2
Assumption 4.1
This assumption is satisfied with M p due Lemma C.4
Assumption 4.2 Since F is a contraction, Banach's fixed point theorem implies it has unique fixed point, and Lemma C.3 implies that Jx(x*) is invertible. Moreover, since F is linear, it is (0, -o)ccllyy psuedo smooth.
Assumption
4.3
We have
I(F(V", (k+11 - F(V"))( Riax 1 (s=af))-
7
Hence,
KF(V", wx+1) F(V*),,)) |I[("* wk+1) - F(V*) lplllbe
(Hölder's inequality)
1/p Rmax |,llur
S (wmin)
where in the last inequality we used the fact the
|| ECOT()) 1/9
where is such that 1/p + 1/4 = 1, and - = min. (x)) It follows that
X² R2 Ranax111/1 1|011 uullu
exp (A(F(V", w.411) - (a-1))F(V")))) -VV)), S exp
2/p 2(1 2y2
(Hoffding's lemma)
R 1/0113 1//2/2 2/v
I exp
X²
2(1 7) ( )2)
(Eq. B.15))
Therefore, the first part of Assumption 4.3 is satisfied with
R S/222
0²_
(1 ( )22/
On the other hand, by the definition in (B.13) we have F(V, wk-1) = A(wa+1V b(wx+1). Hence, Jr., (V*, Wk+1) = A A(wk+1)- Since assume finite state and action spaces, and wk+1 can only take finitely many values, therefore, by Hoeffding's 's lemma there exist ô < such that the second part of Assumption 4.3 holds.
Since | < ||~ p & ||0||,, we have 422 = 1. By a direct application of Theorem 5.1 with probability at least 8.
we have
| S//2/p
24 log(2/8) 3d
1
[|Ve V
Op))
(log(116))
(1
tin (1 (
2/pp 70)2 (k: (k +1
13/2
Moreover, we have
11 x² 11 2 (Vit /2/p - 1/2
(1 7"1 Mimn
2/p
11
x= 11
S
38

---

Hence, with probability 6, we have
R (1 7)2
[S]
4/P 24 log(2/6) + 3d 7c)3 (k: 1)
|[V
V 1
+ O
O (1))).
M (1 - 7m))
/3/2
(B.16)
This result holds for any p. In particular, by choosing
p 4 log (1 (1 (") log
|8| U (1 711)
(K + 1)2/4
(1 7 (m)
we have
[S]
4/p
4 log
8 M (1 - -²)
exp
Mmin (1 1 7m))
$ exp
(-log(1 - -11-7") pm)m) (1 Piiin)
(I: + 1)2/4
2
< 1 +
(B.17)
(k + 1)1/4"
In addition, we have
1
To
(1 7n) (m))iinn 1
1 (1 7" Pmin
(B.18)
(1 7mth M
2(1 - 7mh 1 log
[8]
(k+ + 1)2/4"
Mmin (I-)")
where in the last inequality we used the fact that for all 0 < < 1, we have
1 1-a - a + (oog(L//))
1
(1 a)² x
for all a < (1 a)/(2 (2 (1/g)))))))) and we take x 1/p and a = >
Substituting
equations (B.17) and (8.18) in Equation [B.6)). we obtain
R22 1
log(2/8) + 3d
[ - V- <
1
[1 - 7)2
(k 1)2/4
(I: 1)
(1 M)mia
k1/4
+ ④
O(log(1/6)
A-/4
R2
24 log(2/0) + 3d
max
+ +6
(llg((16))
(1 21 )2 (M
}2
(k: + 1)
15/4
B.9 Proof of Theorem 6.2
First, we verify that the assumptions of Theorem 5.1 are satisfied.
Assumption 5.1 Firstly, for Q-learning algorithm it is known that Qu (s, a) < Rmaxx(111 for all and & 2 0. Furthermore, Q-learning can be written in the form of Equation
1.I with
(F(Qk, (e++)))) = -1 L(==St,=AAl (R(Se, Ax) + max (Qu(S, Qu(S,, An)) + Qu(s,a),
where Wh+1 = (Sk, Ac, St). addition, we have
(F(Q)))s. T (s)
R(s,a) + > P(s max (a (1-"" ())
Furthermore, we have
= + O
39

---

where M is a diagonal matrix with diagonal entries (=)(s)) s), and H is the Bellman optimality operator.
Next, we have
H(Q2)) (F(Q)) - F(Q2)),,a = (s) ( + (1- (1)))(
(s)m))) (Q1) H(Q2) 30 + (1 (s) s)) Q21loc
S nr (s) s) -221a + (1 -= (s)(s) 8)) - Q211m
(1 (5) s))]lQ Q2
S (1 (1 - Pb) 1Q: Q2
where in the second inequality we used that the Bellman optimality operator is a γ- contraction. follows that
[1((1)) F(Q2)lla E (1 (1-7)9b) 11Q1 - Q211
Hence, we can write
| - F(Q2)) s (P( F(Q2)
s (1)) (1 (1 p)) 11Q: Q21loo
S (18)|AA)) 1/2 (1 (1 7)b) 11Q: - Q2lla-
Then, for any
In ((S)(A))
p > Pmin
2 2,
1 In 1-(1->)m
Assumption 5.1
is satisfied with % (IS) (/) (1 (1-7)p))
Assumption 5.2 Since the state and action space are both bounded, the noise in the update of Q-learning is also bounded. Then, Equation (5.1) is satisfied for some by
Hoeffding's s lemma. In addition, Equation (52)) is satisfied due to Lemma
Assumption 4.1
This assumption satisfied with M = p due Lemma
Assumption 4.2 Since F is contraction, Banach's fixed point theorem implies it has unique fixed point Q", and Lemma C.3 implies that Jx(x*) - T is invertible. Moreover, Assumption 6.1 implies that F is linear in neighborhood of Q", and thus there exists R > 0 such that F' is (0, Rt)-ocallly psuedo smooth with respect to the || Ip norm.
Assumption 4.3
We have
2Rmax
[F((Q", ,6411) - F(Q")),,al I
1- 7 [s=s[]
Hence,
(6+1) S [|F(V" -((=)) (Hölder's inequality)
2Rmax ||1||--
5
Then,
22 (x2
max ||0 12 (1
E exp (X(F(Q", wk+1) - -(Q"),))))) < exp
7)
(Hoffding's 's lemma)
Therefore, the first part of Assumption 4.3 is satisfied with x² = 4R22 / (1 (1-~)) 7)2 On the other hand, since assume finite state and action spaces, and Wk+1 only take finitely many values, therefore, by Hoeffding's lemma there exist ā < oo such that the second part of Assumption 4.3 holds.
Furthermore, since p 2 and ||=r||p < || we have uez = 1. By a direct application Theorem 5.I we have that, with probability at least 1 - 8,
4R2 24 log(2/6) + 3|
+ O 1
1lQx - Q-11 < (1 71- (1-76) 2 (k + 1)
Olog
k-32
40

---

Furthermore, we have
1 - Q11 2 1Q, I
Hence, with probability we have
4R max 24 log(2/6) + + O 1
1Qx - - -
(1og((16))
(B.19)
7)² (1 (1-%) (k+))(
k3/2
This result holds for any In particular, by choosing Pmin (k + 1)4/4, we have
1
1
Te
1- (|S|| (1-7))p)
2(1 -
p)pb) In In((S|(AA)
S 7)pb
(B.20)
7)
where in the last inequality we used the fact that
2a lnbb 1 +
1- ab
(1 (1-a)²
for 0 (1- (1-a)/2a
and b 1, and we take = 1/p,a -1 (1- (1-(1-7)) p))
and b = A| Substituting Equation B.20 in Equation (B.19), we get
4R2 max
24 1og((/0) + 3|
1
) 11/4
||Q 10 <
+
(log(116))
7)
+
(1 7)pb
1-/4
4R max
24 log(2/0 + 3|
1
+ Ō
(log(1/)))
p)
k 1
1-54
B.10 Proof of Theorem 6.3
The update of off-policy (D(n) can be written as follows:
(A,IS)
Ut+1 =0k a2R(S
[R(S), +70(5)))))))))) -x(t) vk]
To (A)))))
x (A(1))
Uk + a2o(55)
- Uk
To (12(5))
π (44 S
+010(50)
R(S A1)
(
= -1 -1- + CA + bz).
where
x (AZ1SK)
A₃ = I+ -0(5
&
To (A(((S)
1=0
n-1
(A ( n
(SS)
R(S A().
1= 2 (AA
1=0
and a4 Eag. Hence, off-policy TD(n) with linear function approximation can be written in the form of Equation (I.I) with F F(vk, wk+1) = A + be, where w = [(S), A8)ossinn.
Next, we verify that the assumptions of Thcorem 5.1 are satisfied
41

---

Assumption 5.1 As shown in [T] Proposition 3.1] we have
F(vx) = on + K ((yP*)" - DoE),
and for large enough n, we have that
1 ((7 ((>P=)" +))
is Hurwitz matrix. Hence, by [5] Page 46 footnote] there exists large enough such that
F(-) is contraction with respect to some weighted 2-norm. We denote this norm as || lle-
Assumption 5.3
(i) As mentioned earlier, || lle a weighted 2-norm.
Since F is linear, and the state-action space is bounded, this assumption is satisfied for some L >
iiii This assumption holds due to 52 Lemma 9]
(iv) Since F is linear, and the state-action space is bounded, this assumption is satisfied for
some T >
(v) Since F is linear, and the state-action space bounded, this assumption satisfied for some Σ 0.
Assumption 4.1
Since the norm || I1a is weighted 2-norm, then it is smooth.
Assumption 4.2 Since F is a contraction, Banach's fixed point theorem implies it has unique fixed point, and Lemma C.3 implies that Jp(x*) / is invertible. Moreover, since F is linear, it is (0, oo)-locally psuedo smooth.
Assumption
4.3
Since the noise is bounded, this assumption is satisfied for some ō and ō.
Applying Theorem
5.1 yields the result.
C
Technical lemmas
Lemma C.1. Assume X1, X2.... is a series of martingale difference random vectors in Rd. In addition, assume X; to be 1ī, -ssuuauussaan conditioned on filtration Fi-1 generated by the random variables x
Then Xx X,, is E 17. -subgausssian random vector.
Proof: We prove this by induction in the number of terms n. The case n is immediate. Now suppose that, for any d-dimensional vector v, we have
X ))
v
E
exp
< exp
1
Σ
(C.I)
2
i=1
1=1
Then,
Xi, 1)
exp
A
Σ
E
E
exp
A
Σ
Xinu
Fn-1
1=1
E
exp
A
IF
exp
(A (A u))
F
1=1
<
E
exp
A
Σ
X
exp
[22110112 7/ (Xn, is subgaussian)
< exx
1//110112
Σ
(Inductive hypothesis)
1=1
42

---

Lemma C.2. Suppose we have random vector X R which is s susbgaussiann Then, for all
12(2)) we have
E exp (AII
S (1 22r d//2
Proof:
Since X is subgaussian, we have
11a 11/22
E[exp((X,,)) (x, exp
S exp
2
2
Hence, for any À E (0, 1), we have
(X, u)
222 1111 )1)))
)
1|
E
exp
S exp
(C.2)
2A
2
We now integrate both sides with respect to the vector v. Integrating the left-hand side, we get
00
o)
E
exp
duadva-1... ...ddvai...doy
2X
00
D0
00
(X,
w22 |1012111
exp
duadva- ... dei
2X
00
80
|0)
2
11
Xava - u220311²) du'd
EXp
du
exp
2A
2A
30
V2TÀ
AX?
VTT
XX2
EE
174,2
exp
2n/2u22
17Ul22
exp
207222
V2T>
X||X|]
2
EE
exp
2r
(C.3)
120,2
where (a) is due to Fubini's theorem for non negative functions.
Integrating the right-hand side of Equation (C.2). we get
8
80
x
4 11 1) 1) du doadva-1...ddu
cxp
21
00
22 17 mp () -1)
1)
duz f
u 222))222( (112
cxp
cxp
dud
21
2A
d
(C.4)
(1
-jd//2
Combining equations CC.3
and
we obtain
E
exp
S (1 A)d/2
2n
By change of variable, get the result.
Lemma C.3. Consider differentiable operator F 12d - Rdd that is ne-pssendo-commraactonn with respect to some norm Ilo. with fixed point x.. Then, we have
[[]p(()))
T)2lle
min Z
2 1 Ne-
|
43

---

Proof: We have
F Fxx + +3) F(2*)
No 2
(Pseudo-contraction property)
lly/le
Jx(x*) llylle h(y)
(definition of Jacobian matrix)
o (llyllle)
JF((")
y
1.
(triangle inequality)
Itv/le
llllle
where by the definition of the Jacobian, we used the fact that [[(())]le o(Iulla)/llllle By taking the supremum over all vectors y R we have
(llB)lla)
2 sup wERd
13yle
Note that
olly)le) lylll
I max MERR
TBlll
which is attained at some ý (because it is equivalent to maximizing continuous function over compact set). Moreover, note that for every constant of O, the vector rÿ also attains the maximum above. Let j/n. Then,
o (lBmulle) max 1yalle
o(1/n)
lim 1-000
JpC (x("
(x*)
Jx(x²)
lim
18 llc
1lvlle
1/n
11
{J
{
2/ Tsylle
max wERd
It follows that
{
(p(("))
y
ol lbylle
[Ivllaa)
(115(00)
1lylle }
sup wERd
llvlle l
max yERR
and thus
Jo(("")
21
Yo 2 max yERd
(C.5)
Hence,
[1 (xx*
D)2lle
min
sERd
121le lc
|| (((()))211
min
(triangle inequality)
||
2E3d
|| (x )elle )
max zER4
||
Ye-
EEq.
C.5
Lemma C.4. Let 2 2, P/ 1), and consider the weights w (wi,... wa) E Rd Define the weighted norms
1/r
1/9
| =
Σ wi |
and
[ully
Σ wxt |eel
where w.t = w. 11(0-1)) Les f(x: = 1/10011..m Then, for all x. E TRd,, we have
[V)()) 100---fie V.(e))la I (p- 1) || vlpp.w.
44

---

Proof:
Introduce the diagonal map T' : F + R such that T(x) := Wz, where W is diagonal
matrix with that i-th diagonal entry equal w, 1/2 Then, we have
|>l|,, = (T( p. and ||ullq. = (w)
(C.6)
Let g(2) =11=1|>- Since - g T and W is diagonal, by the chain rule, we have
vf(z) x = (VV))
(C.7)
On the other hand, shown in Example 5.11], for p 2 2 we have
[[v((=) - Vg((')lla S (p - 1)1| z'1pp:
V2, E Rdd.
(C.8)
Fix x, y, and T(x), = Tw)). We have
[v: VV(())l 11l N
())) Vl(=')]ll..or 7,00
(Eq. CC.7
[Vg(z) Vg(22)) (laa)
(Eq. (C.6
S (p 1)[[= =/Ipp
(Eq. (C.8)
= (p- - 1)}[ yllp.w-
(Eq. CC.6
The chain above yields the desired Lipschitz constant L = p - 1:
[Vf(x) Vf(y)ll S (p 1) |- y p.p.
45


Reviews:
[{"review_id": "o6C0CtykFq", "reviewer": "Reviewer_Mrqo", "summary": "The paper presents a general framework to derive finite-time and high-probability performance bounds for Polyak-Ruppert Averaging (an averaged sequence of iterates in a stochastic approximation algorithm). While the paper makes some key assumptions, the utility of SA-based algorithms is immense; therefore, the results are potentially useful in a wide variety of ML and optimization applications. The crucial point is that the paper does not present new algorithms (or motivate new applications) but provides a tight and general framework for analysis that has wide utility.", "questions": "please see above", "limitations": "The paper is hugely limited by the presentation and planning of the technical content. Perhaps, the good goal would be to make the primary theorems readable.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "S:\n\n1)The results in the paper are significant, especially since they establish a general performance guarantee of the SA-based algorithm and explain its successes.\n\nW:\n\n1) The paper is technically dense and largely theoretical. My personal opinion is that NeurIPS may not be the best venue for this work (given the reviewing timelines and reviewer load).\n\n2) My primary concern is how Theorem 4.1 (the main technical result ) is presented. While Lines 139 to 147 are too dense and hard to parse, Lines 28 to 35 are too vague and leave more doubts. A strong suggestion is that (in order to make the results more readable and hence usable) the authors may consider replacing the constants in lines 142-144 with symbols and explaining the symbols later. I was hoping to understand how the main bound degrades with f(\\delta,k) (iterate-wise concentration). \n\n3)In most SA algorithms f(\\delta,k) would be fairly large for small k. As a result, it is not clear what the guarantee would mean as a function of k.\n\n4) It is also surprising that the right-hand side of the result in Theorem 4.1 does not depend on f(\\delta, k'), where k'< k (i.e., point-wise errors in the older iterates). Can the authors comment on this?\n\n5)In my opinion, the most usable applications are in section 5, but they are based on additional assumptions. On its own, Assumption 5.3 is confusing, and it is not clear what it means.  e.g. what is \"c\"?\n\n6)Can the authors explain what \"the first\" is in Theorem 6.1? I thought the finite time error bounds for TD learning had been established already. It is likely I am missing something. What does \"the entire distribution mean\" A similar claim is made for Theorem 6.2", "was_revised": true, "final_justification": "i raised by score to 4. \nThe only concern with the paper is that it requires quite a bit of rewriting, as described in the author's rebuttal, to become more readable and accessible. I do not have other strong concerns if this paper is going to be accepted as it is overall a good contribution.", "rebuttal": "We thank the reviewer for their thoughtful evaluation and recognition of the technical significance and generality of our results. We address the concerns and suggestions below in order:\n \n(1) [Clarity of Theorem 4.1: Dense presentation vs vague summary]\nWe appreciate the suggestion to improve the clarity of Theorem 4.1. In the camera-ready version, we will revise the presentation of the bound by replacing multi-line constants (lines 142–144) with concise symbolic expressions and deferring detailed definitions and decompositions to a subsection immediately following the theorem. We agree that this will make the result easier to digest, especially for readers less familiar with high-probability bounds.\nRegarding the dependency of the upper bound on f (\\delta, k) function, we have a detailed discussion in section 4.3 of the paper. We will also enhance this section with additional clarifications to further aid the reader.\n \n(2) [Interpretation of dependence on f(δ, k)]\nAs noted in line 159, in most SA algorithms the function $f(\\delta, k)$ typically grows at most polylogarithmically in $k$. Consequently, its impact on the higher-order terms in our bound affects the $k$-dependence only logarithmically.\nIn Theorem 4.1, we assume $||x_i-x^*||^2\\leq \\alpha_i f(\\delta’,k) \\forall i\\leq k$. Therefore, while the function $f(\\delta', k)$ is uniform across the iterates, the dependence on $i \\leq k$ appears through the decreasing step sizes $\\alpha_i$. We will include a more detailed explanation of this point in the revised version.\n\n \n(3) [Usability of applications; clarification of Assumption 5.3]\nThank you for raising this point. Assumption 5.3 is a standard condition in the literature on SA with multiplicative noise (e.g., see [10], [12]). The constant “c” refers to the norm $||\\cdot||_c$ used throughout the paper. We will revise the phrasing of Assumption 5.3 to make this clearer and add an illustrative example, such as off-policy TD learning with linear function approximation, to highlight when this assumption applies.\n \n(4) [Clarification on “the first” in Theorem 6.1 and 6.2]\nWe appreciate the opportunity to clarify. There do exist prior finite-time bounds for TD and Q-learning in various settings. Our claim in Theorems 6.1 and 6.2 is not about being the first to provide finite-time bounds in general, but rather about establishing the first non-asymptotic high-probability bounds on the entire distribution (i.e., for all $\\delta \\in (0,1)$) of the error of the averaged iterates. \n(a)\tPrior works such as [18], [42] provide bounds for the raw iterates or use step sizes that depend on a fixed confidence level $\\delta$, and thus only give pointwise control (i.e., one quantile of the error distribution).\n(b)\tIn contrast, our bounds are uniform in $\\delta$, as our step size is independent of $\\delta$, and we obtain bounds that control the entire tail of the error distribution for the averaged iterates. We will revise the phrasing in Theorems 6.1 and 6.2 to clarify this distinction.\n \n(5) [Overall presentation and accessibility]\nWe thank the reviewer for acknowledging the technical depth and generality of our results. We are actively working on restructuring Section 4 and its subsections for improved readability."}, {"review_id": "lSMIupW5AR", "reviewer": "Reviewer_RYGS", "summary": "This paper considers the problem of finding fixed-points with\nstochastic approximation. This general mathematical framework\nencompasses a multitude of practical AI settings, including\nreinforcement learning. I should note that stochastic approximation is\noutside my core research area.\n\nPolyak-Ruppert (PR) averaging was major development in stochastic\napproximation, improving on the Robbins-Monro algorithm. It has been\nknown for a long time that Polyak averaging can achieve asymptotic\noptimal convergence rates, usually on the form O(log(1/delta)/k) where\n1-delta is the probability of exceeding the error bound and k is the\nnumber of iterations of the algorithm. Recent research has shown\nnon-asymptotic, finite-time results for the expectation. However, in\npractical applications, rather than knowing the expected error, it is\nmore useful to know the probability that a run of the algorithm will\ndeviate far from the optimum, i.e., to prove tail-inequalities on the\nerror distribution of Polyak-Ruppert averaging.", "questions": "The proofs are rather involved. I have checked most proofs in detail\nwithout spotting any errors. I have a few suggested changes below.\n\nMinor comments:\n\nIn a few places, the paper multiplies big-Oh expressions, e.g., in\nline 163. I am not sure if this is conventional in this community,\nhowever, in other places, one would write O(log(1/delta)/k) rather\nthan O(1/k)O(log(1/delta)).\n\nThere are frequent typographic issues with multiplication, where the\ncdot is on the baseline, e.g., in the latex environment below\nline 220.\n\nLine 778: Replace \"easy to see that\" with an explanation.\n\nLine 790: Would it be easier to set the \\varrho variable directly to 1\nhere, rather than later?\n\nLine 810: I do not see why O(lambda) \\le O(lambda^2) is a\ncontradiction, even if lambda \\lt 1. \n\nLine 826: Add some explanations to these derivations.\n\nLine 842: By Markov's inequality\n\nLine 1004: Explain why the assumptions of Fubini's theorem are\nsatisfied.", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Based on my limited knowledge of stochastic approximation, this paper\nmakes a breakthrough in this direction. The main result (Theorem 4.1)\nis a fixed-time, non-asymptotic upper bound on the error made by the\nalgorithm. With an accompanying lower bound for a special case, the\nauthors show that the bound is tight up to a constant factor. The\nassumptions for the upper bound are quite relaxed. Several example\napplications are made, including the first bound on the error\ndistributions of averaged TD-learning, averaged Q-learning, and\nothers.\n\nIn overall, the paper is very well presented, including a sufficient\ndiscussion of related work. I have only spotted a few grammatical\nissues.", "was_revised": true, "final_justification": "I am satisfied with the rebuttal and remain confident that this is strong result that deserves to be published.", "rebuttal": "We thank the reviewer for their careful reading, detailed engagement with the technical content, and generous assessment of the paper's significance, clarity, and originality. We are encouraged by your recognition of Theorem 4.1 as a breakthrough result in establishing high-probability, non-asymptotic guarantees for Polyak–Ruppert averaging, and for noting the value of our contributions to reinforcement learning applications such as TD and Q-learning.\nWe respond below to your comments and suggestions:\n \n(1) Use of multiplicative $\\mathcal{O}(\\cdot)$ notation (e.g., line 163):\nThank you for pointing this out. We intentionally wrote the upper bound in this format to split the dependency on $\\delta$ and $k$ and make them more clear. Mathematically there is no mistake in our notation. If the reviewer thinks it is confusing, we can change it to just one $\\mathcal{O}(\\cdot)$ term.\n \n(2) Typographic issues with multiplication:\nWe appreciate your careful reading. We will fix them in the next version of the paper.\n \n(3) Line 778 (“easy to see that”):\nWe will revise this line to include a brief justification instead of relying on the phrase “easy to see,” which can be opaque to readers. We agree that this will improve clarity and accessibility.\n \n(4) Line 790: Choice of $\\varrho$:\nWe thank the reviewer for this suggestion. We will update the exposition accordingly to streamline the argument.\n \n(5) Line 810: Clarification on contradiction:\nHaving $\\mathcal{O}(\\lambda) \\leq \\mathcal{O}(\\lambda^2)$ for all $\\lambda>0$ is indeed a contradiction. In particular, as $\\lambda\\rightarrow 0, \\mathcal{O}(\\lambda^2)$ converges to zero faster than $\\mathcal{O}(\\lambda)$. \n \n(6) Line 826: Add explanation to derivation:\nWe will expand this step with intermediate calculations and justification to help the reader follow the derivation more easily.\n \n(7) Line 842 (“By Markov’s inequality”):\nThank you for catching this. We will fix it in the next version.\n \n(8) Line 1004: Use of Fubini’s theorem:\nWe will add a justification for the application of Fubini’s theorem here, including verification of the integrability condition that allows the interchange of expectation and integral.\n \nWe greatly appreciate your feedback and suggestions, which will be incorporated into the revised version to further enhance clarity and rigor."}, {"review_id": "fa8nuaIKrQ", "reviewer": "Reviewer_KhvA", "summary": "This paper provides concentration bounds for general stochastic approximation (SA) algorithms under Markov noise, accounting for both linear and nonlinear function approximators. The paper assumes a high-probability bound for the iterate sequence of the stochastic approximation algorithm, and uses this bound to derive high-probability bounds for the Polyak-Ruppert averaged iterate. The derived bounds are then specialized to contractive SA algorithms, including TD and Q-learning. Lower bounds are also derived that nearly match the leading terms in the upper bounds (up to universal constants).", "questions": "My main questions and comments are as listed above under \"Strengths and Weaknesses\". Without a more detailed comparison with the prior art, the significance of the contributions remains unclear to me.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n- Although there has been a lot of recent interest in establishing finite-time rates for SA algorithms, most rates are derived in the mean-squared sense. In contrast, this work establishes high-probability bounds for a fairly general class of SA algorithms, accounting for both linear and nonlinear function approximation, and both additive and multiplicative noise. \n\n- While most papers only provide upper bounds, this work also establishes nearly matching lower bounds. \n\n- The paper is very well structured, and provides a detailed treatment of various special cases (e.g., TD and Q learning) that follow as corollaries of the main result. \n\n**Weaknesses and Comments**\n\n- To derive their general result on the averaged iterate sequence $y_k$, this paper assumes a high-probability bound on the basic iterate sequence $x_k$ to begin with. However, given the generality of the setting considered in this paper, it was quite unclear to me how challenging it would be to obtain high-probability bounds on the $x_k$ sequence to begin with. For instance, say one considers the special case of TD learning with linear function approximation under Markov noise. Obtaining high-probability bounds for the basic iterate sequence $x_k$ seems quite non-trivial in the first place, especially without the assumption of a projection step. \n\nThus, my main concern is whether the difficulty of obtaining tight concentration bounds for $x_k$ might dominate that for $y_k$. \n\n- Some recent papers have, in fact, established finite-time high probability bounds for TD learning. See References [R1] and [R2] below that are not currently discussed in the paper. Each of these papers establish concentration bounds under Markov noise. As such, I would like a clear discussion of how the results in this paper compare with those in [R1] and [R2]. \n\n[R1] Adapting to mixing time in stochastic optimization with Markovian data, Dorfman and Levy, ICML 2022. \n\n[R2]  Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisation, Patil et al., AISTATS 2023. \n\n- Related to the above point, the paper does not do a good job of precisely pin-pointing how their results improve upon/generalize those in the long list of papers reviewed in the Related Works section. In particular, I would like a more transparent comparison with references [18], [32], and [R3] below, all of which do establish high-probability bounds for linear SA. \n\n[R3] High-probability sample complexities for policy evaluation with linear function approximation, Li et al., TIT, 2024.\n\nAs far as I can tell, the main (and perhaps the only) difference with the above papers seems to be that the current work allows for nonlinear function approximators. However, the extension from linear to nonlinear SA schemes has also been explored in a variety of works, under suitable regularity conditions on the nonlinearity. Thus, the paper would benefit from a discussion of the new technical challenges that arise in their analysis, relative to what has not appeared before in prior work. \n\n- The results in Theorems 6.1. and 6.2. seem to be for tabular TD and Q-learning, respectively. Aren't these results already subsumed by those in References [28], [29], and [37]? In particular, References [28] and [29] have already established tight upper and lower bounds for tabular Q-learning, while accounting for asynchronous Markov sampling. As such, how does Theorem 6.2. in this paper compare with the results in these references? \n\n- In addition to References [R1]-[R3] above (that are highly relevant for this paper), some other relevant references on TD learning/linear SA that are missing are as follows: \n\n[R4] Temporal Difference Learning as Gradient Splitting, Liu and Olshevsky, ICML 2021. \n\n[R5] Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis, Khamaru et al., SIMODS 2021. \n\n[R6] Accelerated and instance-optimal policy evaluation with linear function approximation, Li et al., SIMODS 2023.\n\n[R7] A Simple Finite Time Analysis of TD Learning with Linear Function Approximation, Mitra, TAC 2024. \n\nThe authors should add and discuss the missing references [R1] - [R7] in their revised version.", "was_revised": true, "final_justification": "My initial primary concern was in terms of the specific nature of the contribution in relation to a bunch of other papers (that I pointed to) that also establish finite-time rates. The authors have adequately at least explained the key differences in the settings w.r.t. to these papers. As a result, I have raised my score to '4'.\n\nI did not raise my score any further since the authors did not quite explain why the techniques used to establish high-probability bounds for base iterates cannot be adapted to *averaged* iterates, the latter being the focus of their paper.", "rebuttal": "We thank the reviewer for the careful reading and thoughtful comments. We are encouraged by the recognition that our results provide general high-probability bounds for stochastic approximation (SA) algorithms under broad assumptions---particularly accounting for nonlinearity and multiplicative noise---and for the appreciation of our structural clarity and treatment of special cases. Below, we address the main concerns:\n\n(1) On the assumption of high-probability bounds for the base SA iterates.\n\nWe agree that deriving high-probability bounds for general SA iterates, especially under Markovian noise and without projection, is a challenging task. However, the focus of our work is not to re-establish such bounds, but to provide a \\emph{general framework} that transfers existing high-probability bounds on raw iterates into high-probability guarantees for the \\emph{averaged} sequence.\n\nOur framework is \\emph{modular}: any bound of the form $\\mathbb{P}(\\|x_i - x^*\\|^2_c \\leq \\alpha_i f(\\delta, k)) \\geq 1 - \\delta \\quad \\text{for all } 0 \\leq i \\leq k$\ncan be used as input to our main result (e.g., as derived in [15, 27]). Section 5 demonstrates this instantiation for both additive and multiplicative noise settings.\n\nIn the context of reinforcement learning (RL), many works have established high-probability bounds for TD and Q-learning algorithms. Our Section 6 builds directly upon these results to derive \\emph{new distribution-level bounds for the averaged iterates}.\n\nIt is worth emphasizing that \\emph{analyzing the average of SA iterates is fundamentally more delicate} than analyzing the raw iterates. While the base SA sequence with step size $\\alpha_k = \\alpha / (k + h)^\\xi$ achieves an $\\mathcal{O}(1/k^\\xi)$ rate, the averaged sequence resembles an SA with step size $1/k$, and achieving a tight $\\mathcal{O}(1/k)$ concentration requires new analysis techniques.\n\nFinally, we note that our current work focuses on the \\emph{martingale noise setting}. While we believe our ideas extend naturally to the \\emph{Markovian noise setting}, that is beyond the current scope and will be addressed in a future work. Importantly, our result acts as a \\emph{black-box averaging layer} that can be applied to any future high-probability bound on the base iterates, which is where the generality of our approach lies. We will clarify this point in Section 4 of the revised version.\n\n(2) Comparison with [18, 28, 29, 32, 37] and [R1]--[R7].\n\nWe thank the reviewer for highlighting these important references. Below, we outline how our work differs from each:\n\n    (a) [28, R4, R1, R6, R7]: These works provide bounds on the \\emph{mean squared error}, rather than \\emph{high-probability guarantees}.\n    \n    (b) [R2]: Studies TD-learning with a \\emph{projection step}. In contrast, our results apply to TD-learning without any projection.\n    \n    (c) [18, 29, 32, R3, R5]: These works provide \\emph{$\\delta$-dependent high-probability bounds}, where the step size is explicitly tuned to the fixed $\\delta$ level. As a result, they do \\emph{not provide a bound on the entire tail} of the distribution. In contrast, our framework supports \\emph{$\\delta$-independent step sizes}, yielding a bound that holds for \\emph{all} $\\delta \\in (0, 1)$---a much stronger and more flexible guarantee.\n    \n    (d) [37]: Analyzes Q-learning without averaging. To compensate for the lack of averaging, it requires step sizes that depend on \\emph{unknown problem parameters} such as $\\mu_{\\min}$. Our result avoids this by focusing on \\emph{Polyak–Ruppert averaging}, which permits robust choice of step sizes and yields better high-probability bounds.\n\nIn short, the goal and scope of our paper---namely, providing \\emph{tight, high-probability, distribution-level bounds for the averaged SA iterates}---are fundamentally different from those of the prior works listed above. Our analysis requires a \\emph{new technical machinery} to handle the subtle interplay between averaging and concentration, especially in the presence of nonlinear dynamics and multiplicative noise.\n\nIn the next version of the paper we will incorporate [R1]--[R7] into the Related Work section and include a detailed comparison table to more explicitly position our results within the literature."}, {"review_id": "TqZLkzxdQ9", "reviewer": "Reviewer_VkGz", "summary": "For stochastic approximation algorithms, given a high probability bound for (unaveraged) iterates, this paper turn it into a high probability bound for the Polyak-Ruppert average. Various implications of the bound are discussed in detail, including tightness, simplifications in different scenarios, and applications to \"abstract\" contractive operators as well as concrete RL algorithms.", "questions": "See ''Strengths And Weaknesses''.", "limitations": "See ''Strengths And Weaknesses''.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This is a solid theory paper. Although the main result looks complicated, at the end (Section 5) it brings clear insights on the performance difference between iterates and the average (improving constants in additive noise case and making tails heavier in the multiplicative noise case). The presentation can still be improved (e.g., to let non-SA-expert readers learn more from the paper). Here are some suggestions and questions.\n\nWhat motivates the generalization of the notion of smoothness in Assumption 4.2 (iii)?\n\nMay add an insightful/informal version of Theorem 4.1 that reflects the discussion (between Theorem 4.1 and Corollary 4.1) without giant expressions, to highlight some takeaway about the main result itself, before exploring various implications.\n\nWhat is $u_{c2}$?\n\nMay briefly explain why Assumption 5.2 and 5.3 correspond to additive and multiplicative noise, respectively.\n\nFor Section 6, instead of rushing through three settings without discussion, it may be better to focus on one of them, to let readers know what insights these bounds bring in the RL setting.\n\nThe last question is a \"philosophical\" one. This paper treat bounds for $x_t$ as given (first step) and transform them into bounds for $y_t$ (second step), resulting in two completely separate steps. What is the price of this separation? Is it possible to partially merge the two steps to generate better result?", "was_revised": true, "final_justification": "I think this is a solid theoretical paper. My concerns (mainly about the presentation) are well-addressed in the rebuttal. I keep my score 5 and recommend acceptance.", "rebuttal": "We thank the reviewer for their positive evaluation and thoughtful feedback. We are encouraged by your recognition of the technical strength of our results and the insights conveyed in Section 5. We address your specific suggestions and questions below:\n \n(1) Motivation for the generalized notion of smoothness in Assumption 4.2(iii):\n\nThank you for this important question. The generalization of smoothness in Assumption 4.2(iii) is motivated by the need to analyze the averaged sequence when the operator is not globally smooth. Many practically relevant SA problems (e.g., Q-learning) involve operators that are only locally smooth in a neighborhood of the solution. Our assumption allows for such cases, while still enabling tight control of the error under averaging. We will elaborate on this motivation more clearly in the revised version.\n \n(2) Suggestion for an informal or takeaway version of Theorem 4.1:\n\nWe appreciate this suggestion. While Theorem 4.1 is stated in full generality to maximize applicability, we agree it would be valuable to include an informal version or visual summary highlighting key insights. In the revision, we will add a short paragraph immediately following Theorem 4.1 summarizing the takeaways in plain language.\n \n\n(3) What is $u_{c2}$? \n\nAs described at the end of page 4, $u_{c2}$ is the constant that relates the 2-norm and the c-norm as follows: $||.||_c\\leq u_{c2}||.||_2$.\n \n\n(4) Clarification on Assumption 5.2 and 5.3 (additive vs multiplicative noise):\n\nThank you for pointing this out. Assumption 5.2 corresponds to additive noise, where the variance of the noise is uniformly bounded regardless of the variable $x$. In contrast, Assumption 5.3 models multiplicative noise, where the noise grows linearly with the magnitude of the iterate. The additive/multiplicative terminology comes from the simple linear SA. In particular, suppose $F(x,w)=Ax+ b(w)$ for a fixed matrix $A$ and a random vector $b(w)$. This corresponds to additive noise since the noise $b(w)$ is added. However, if we have $F(x,w)=A(w)x+ b(w)$, we have the multiplicative noise, as the noisy matrix $A(w)$ is multiplied with the variable x.\nWe will make this correspondence explicit in the exposition to aid readers less familiar with SA theory.\n \n\n(5) Suggestion to focus Section 6 more narrowly:\n\nWe appreciate this perspective. The current version of Section 6 includes three settings to demonstrate the generality of our framework, but we agree that a deeper discussion of  the results would better illustrate the implications of our bounds in RL. In the revision, we will use the extra page to expand our discussion of the results in this section.\n \n(6) Philosophical question: Can the two-step analysis (base bounds → averaged bounds) be merged?\n\nThank you for the insightful question. As shown in Proposition 4.2, the leading term of our high probability bounds are tight up to a universal constant. However, one might be able to get better higher order terms by a joint analysis of the two variables $x_k$ and $y_k$. We leave this direction for future research."}]

Author rebuttal:

Meta-review: The paper provides a general-purpose theoretical framework for turning high-probability bounds about convergence of individual iterates in stochastic approximation algorithms to high-probability bounds for convergence of average iterates. The paper presents both upper and lower bounds, which are nearly matching. There was uniform support for accepting the paper, with comments and suggestions primarily directed at improving clarity of presentation, which the authors have committed to addressing in a revision.
Decision: Accept (poster)