Statistical inference for Linear Stochastic Approximation with Markovian Noise
Authors: Sergey Samsonov
Marina Sheshukova
Eric Moulines
Alexey Naumov
Venue: NeurIPS 2025 poster ()
Keywords: Markovian LSA
Polyak-Ruppert averaging
Berry-Esseen type bounds
Bootstrap methods
Asymptotic variance estimation
Primary area: theory

Abstract: In this paper we derive non-asymptotic Berry–Esseen bounds for Polyak–Ruppert averaged iterates of the Linear Stochastic Approximation (LSA) algorithm driven by the Markovian noise. Our analysis yields $O(n^{-1/4})$ convergence rates to the Gaussian limit in the Kolmogorov distance. We further establish the non-asymptotic validity of a multiplier block bootstrap procedure for constructing the confidence intervals, guaranteeing consistent inference under Markovian sampling. Our work provides the first non-asymptotic guarantees on the rate of convergence of bootstrap-based confidence intervals for stochastic approximation with Markov noise. Moreover, we recover the classical rate of order $\mathcal{O}(n^{-1/8})$ up to logarithmic factors for estimating the asymptotic variance of the iterates of the LSA algorithm.

Statistical inference for Linear Stochastic Approximation with Markovian Noise
Sergey Samsonov
Marina Sheshukova
HSE University
HSE University msheshukova @ hse.ru
svsamsonov hse.ru
Eric Moulines Ecole Polytechnique, MBZUAI
Alexey Naumov HSE University, Steklov Mathematical Institute of Russian Academy of Sciences anaumov @ hse.ru
ric.mmulinexxpplyecchiqqeee.
Abstract
In this paper we derive non-asympiotic Berry-Esseen bounds for Dolyak-Rupper averaged iterates of the Linear Stochastic Approximation (LSA) algorithm driven by the Markovian noise. Our analysis yields (nn-1/4) convergence rates the Gaussian limit in the Kolmogorov distance. We further establish the non- asymptotic validity of multiplier block bootstrap procedure for constructing the confidence intervals, guaranteeing consistent inference under Markovian sampling. Our work provides the first non-asymptotic guarantees on the rate of convergence of hootstrappbased confidence intervals for stochastic approximation with Markov noise. Moreover, we recover the classical rate of order -1/#) up to logarithmic factors for estimating the asymptotic variance of the iterates of the LSA algorithm.
Introduction
Stochastic approximation (SA) has become foundational to modern machine learning, especially its
reinforcement learning (RL) domain. Many classical RL algorithms, including Q-learning [80] (6).
the actor-critic algorithm (35] and policy evaluation algorithms, such as temporal difference (TD)
learning 766 special instances of SA. Recent research has extensively studied both the asymptotic
14] and non-asymptotic behavior [49 of these algorithms. It is important not only to establish the
convergence of SA estimators, but also to quantify their uncertainty, which typically done through
the asymptotic normality of corresponding estimates, see [57] 46). Recent works have focused on
deriving non-asymptotic convergence rates for SA methods 669 67 82). Notably, most existing results consider settings with independent and identically distributed (i..dd) noise. In contrast, many practical SA applications involve dependent noise, often forming a Markov chain. This additionally complicates the problem. Indeed, even the problem of deriving precise Berry Berry-Esseen type convergence rates for additive functionals of Markov chains challenging compared to i.i.d. setting, where quantitative results are well-established, starting from Bentkus' influential work (7].
Asymptotic normality of SA estimates is particularly important in practice, it allows one to construct approximate confidence intervals for the parameters of interest. Different approaches either directly utilize the asymptotic normality and aim estimate the asymptotic covariance matrix directly (the plug-in in or on the bootstrap [27] 64 When the latter approach is applied to the dependent observations, standard
methods, see [17 [1] 63)), or rely on the non-parametric methods, based
bootstrap methods need to be carefully adjusted to account for the dependence structure, see 29 42
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

In this paper, we study a linear stochastic approximation (LSA) procedure. This setting covers several important scenarios, such as the classical TD learning algorithm [76] with linear function approximation, while allowing for sharper theoretical analysis. The LSA procedure aims to find an approximate solution the linear system A = b with unique solution 0', based on obser- vations {(A (Zx), b(Z+))) REN, Here A Z + Rdxd and b Z + IR4 are measurable functions, and KEN is a sequence of noise variables taking values in a measurable space (Z, 2) with a distribution satisfying [E, [Ax)]] = A and Exx [bx]]] = b. We focus on the setting where KEN is an ergodic Markov chain. Given a sequence decreasing step sizes {aREKEN and an initial point 8 E Rd, we consider the estimates {nn]NeN given by
fx = = au (A
b(Zx)) 221,
8, = =n 0s: n21.
(I)
The sequence kon corresponds to the standard LSA iterates, while [nnJNEN corresponds to the Polyak-Ruppe Ruppert (PR) averaged iterates [65] [57. It is known that, under appropriate technical conditions on the step sizes {ay} and the noisy observations
{Zx} (see [57] and [3]] for discussion),
Vn(O, 0*) 9 (0(
Here the asymptotic covariance matrix Ex is defined in Section see Recent works have provided number of non-asymptotic guarantees for the averaged LSA iterates of 0... particular, 33
25 48 24, which study the mean-squared error, high-order moment bounds, and concentration bounds for (n(0,, - 0*). However, these results are not enough to establish explicit convergence rates in ( in some appropriate probability metric d:
74
47
d(vn((,, 0*), );
where Y ~ (0, Notable exceptions are recent papers 67 82
70
83 which study non-
asymptotic convergence rates in the LSA and stochastic gradient descent (SGD) algorithms, well as in the specific setting of the TD learning algorithm. Our paper aims to complement these findings by providing both non-asymptotic analysis of the convergence rate in 2 and analysis of an appropriate procedure for constructing confidence sets for 0" Our primary contributions are as follows:
We derive a novel non-asymptotic bound for normal approximation for projected Polyak-Ruppert averaged LSA iterates /nu" (0,, 0*) under Markovian noise in (2). Here u is a vector on the unit sphere S2-1- Precisely, we establish a convergence rate of order On-11/1 Kolmogorov distance. The rate O(n matches the recent result of [83] which considered the particular setting of the TD learning algorithm, and improves over the previous results from 773. Our proof strategy differs from that of [83] and is based on a Poisson decomposition for Markov chains, combined with an appropriate version of the Berry-Esseen bound for martingales, building on the results of Fan (28 and Bolthausen [2] We provide non-asymptotic analysis of the multiplier subsample bootstrap approach 48 for the LSA algorithm under Markovian noise. Our bounds imply that the coverage probabilities of the true parameter 0* can be approximated at a rate of O (n where n is the number of samples used in the procedure. To the best of our knowledge, this is the first non-asymptotic bound on the accuracy of bootstrap approximation for SA algorithms with Markov noise. As a byproduct of our analysis, we also recover the rate of O(n 1/8) (up to logarithmic factors) for estimating the asymptotic variance of projected LSA iterates using the overlapping batch means (OBM) estimator, previously obtained [17 79.
We apply the proposed methodology to the temporal difference learning (TD) algorithm for policy evaluation in reinforcement learning.
The rest of the paper is organized as follows. In Section 2 we review the literature on Berry-Esscen type results for stochastic approximation (SA) algorithms and methods for constructing confidence intervals for the parameter 8* in these settings. In Section 3 we obtain a quantitative version of the Berry-Esseer Esseen theorem for the projected error of the Polyak-Ruppert averaged LSA under the Kolmogorov distance. In Section 4 we discuss the multiplier subsample bootstrap approach (as proposed in (33) for LSA and provide non-asymptotic bounds on the accuracy of approximating the exact distribution of /nu² (0.. 00)) with its bootstrap counterpart. Then in Section 5 we apply the proposed methodology to the temporal difference learning (TD) algorithm, based on the sequence of states, which form geometrically ergodic Markov chain. Proofs are postponed to appendix.

---

Notations. We denote by P(Z) the set of probability measures on measurable space (Z, 2). For probability measures μ and y on (z, 2) we denote by d,v (H. 2) the total variation distance between them jl and v, that is, (v, v) supcez ju(C) - =(()). For matrix A [xd we denote by || its operator norm. Given a sequence of matrices (AE) Ae E Rdddd we use the following convention for matrix products: II A = A Am where m - k. For the matrix Q E Rd which is symmetric and desitive-definite and x E R", we define the corresponding norm
|B | Vz x Qr, and define the respective matrix Q-norm of the matrix B Raxd by sup | ll/ /|/ll// For sequences on and bn. we write On X bn if there exist (numeric) constant > 0 such that On S. cb,, For simplicity of presentation, we state the main results of the paper up to absolute constants. We also use a notation On Slog Un if there exist 3 > 0 and e > O, such that an I c(1 + log n) for any n. Additionally, we use the standard abbreviations "i..d." for "independent and identically distributed" and "w.r.t." for "with respect to". We use index k to present results which hold true for any intermediate iteration, and index denotes the total number of iterations of the algorithm.
2 Related works
The analysis of linear stochastic approximation (LSA) algorithms under Markovian noise has a long history, with classical works establishing almost sure convergence and asymptotic normality under broad conditions [57 [4 38 g
These asymptotic results, however, lack explicit finite-sample error bounds. Recently, non-asymptotic performance analysis of stochastic approximation and gradient methods has gained attention. In the i.i.d. setting of stochastic gradient descent (SGD), finite-time error bounds were provided by [51, 58). For Markovian LSA contexts, convergence rates were analyzed by [10 (3. focusing
learning, and instance-dependent bounds were derived by [48] and [24]. These studies establish guarantees on mean-square square error or high- probability deviations but do not address the distributional approximation of the estimator.
remporal-different
Rates of convergence in CLT are widely studied in probability theory (7), primarily for sums of random variables univariate martingale difference sequences [25] Berry-Esseen bounds and Edgeworth expansions for Markov chains under various ergodicity assumptions are also available [13] 11 9 34], though typically restricted to the 1-dimensional case. Our analysis leverages recent concentration results on quadratic forms of Markov chains [50]. building upon martingale decomposition techniques for U U-statisties developed in [5).
Recent studies have analyzed convergence rates of SA iterates their limiting normal distributions. 667 derived an On -1/4) convergence rate in (2 in convex distance for TD learning under i.i.d. noise, improved to On (1/) by [82] specifically for TD learning.
[3] applied Stein's method to averaged SGD and LSA iterates in smooth Wasserstein distance, again under i.i.d. conditions. Recently, [73] analyzed rates for martingale CLT in 1-st order Wasserstein distance with Markovian samples but achieved slower convergence than our result (see Theorem D provided last-iterate bounds for SGD for nigh-dimensional linear regression, also with i.i.d. noise.
and discussion after it). Lastly, M
Originally introduced for i.i.d. data 27 the bootstrap method has been adapted to complex settings, including high-dimensional tests 18 19 and linear regression (72). For SA methods, online bootstrap for SGD was proposed in 29 with recent non-asymptotic analysis showing approximation rates up to (n/2/2) for coverage probabilities in case of strongly convex objectives with independent noise 770] A similar analysis for linear stochastic approximation (LSA) yields rates of order Onn
677 Extensions to Markovian settings by (59) proved inconsistent, as demonstrated in Proposition 1]. Mcanwhile, (42) proposed consistent mini-batch SGD estimators for 4--mixing noise. They also suggested consistent procedure for constructing the confidence intervals, but studied only its asymptotic propertics using the independent block trick [84). Lastly, multiplier bootstrap techniques for online non-convex SGD were considered by [85].
42
Among other approaches for constructing confidence intervals for dependent data, we mention methods based on (asymptotically) pivotal statistics [40] [1]. The authors of [41] considered the Polyak-Ruppert averaged Q-learning algorithm under the i.i.d. noise assumption (generative model), while 40 generalized this approach to nonlinear stochastic approximation under Markov noise. Another group of methods are based on estimating the asymptotic covariance matrix Exec appearing in the central limit theorem (2) Among these approaches we mention the plug-in estimator of
3

---

17] and batch-mean estimators, see e.g. [13 79 63 Specifically, 63 treats SGD with Markov
noise, contrasted with the independent-noise SGD analyses in [77 T5 and [85 investigates both multiplier bootstrap and batch-mean estimators for nonconvex objectives. These methods yield non-asymptotic error bounds in expectation, E'|l", Exo II but do not study convergence rates in (2) A notable exception is [82], which delivers a non-asympiotic analysis of TD-learnin under i.i.d.
noise, using plug-in covariance estimates to achieve an O(n 1/33 approximation rate for coverage probabilities of 0*
3 Accuracy of Gaussian approximation for LSA with Markov noise
3.1 Gaussian approximation for non-linear statistics
We first discuss a general scheme for proving quantitative normal approximation bounds for non-linear statisties. Consider the statistic T(X1..... Xn.) Rd, which can be written as
T=
where W is linear statistic of the random variables Xj...., Xn. and D is nonlinear term, which is typically small. Multidimensional versions of CLT based on the decomposition (3 are well-studied when XI,...,X, Xx, are i.i.d. random variables [16 [69] In this case, one can follow the randomized concentration approach [69], which requires only a finite 2-nd moment of the term D. To our knowledge, there are no such results readily available for Markov chains or martingales. Moreover, the Berry-EEsecde type result for d-dimensional linear statistics of Markov chains or martingale- differences with explicit dependence on d remains an interesting and open question. There is no affirmative result comparable to the one of [7] for i.idd random vectors. This is the primary reason why we focus on the setting of 1-dimensional statistics and use the following proposition to obtain the rates of Gaussian approximation for T given in (3):
Proposition 1. Let ((x), x E R. be the c.d.f. of the standard normal law. Then for any random variables W and D and any 2 1,
SUPER [P(W + D & x) {xx)| S SUPRER [P(W S $x) - (x)) + 2E (
This result is classical and can be found c.g. in [ For completeness, we provide the proof in Appendix FF] The most involved part of applications of Proposition i the proper bound on [P] This requires to select large values of p. which later requires to introduce additional assumptions on the step size choice in the LSA procedure, AB in Section 3.2
3.2 Gaussian approximation for LSA with Markov noise
When there is no risk of ambiguity, we use the simplified notations A, = A(x)) and b, = -b(zx). Starting from the definition (I). we get with elementary transformations that
0n -- 0- = (I- (6n - 8*) an
(4)
where we have set En = e(Z)) with E(2) (2))0- b(2). A(z) A. = b(2) b.
Here the random variable a e(Z,) can be viewed as noise, measured at the optimal point 0-, We also define the noise covariance matrix under the stationary distribution .:
Σ, = E. (s + Be(()))eee
+2
(5)
We now impose the following conditions:
A1. The sequence (Zu ke) is a Markov chain taking values in a Polish space (Z, 2) with Markov kernel P. Moreover, P admits ergodic, that is, there exists Imix E N, such that for any k E N, it holds that
unique invariant distribution and is uniformly geometrically
A(P*) == sup (P* P*, 1) S (1/4)/kttmnl)
Parameter mmix in 6 referred to as mixing time, see on the noise variables e(2):
54
We also impose the following assumptions

---

A2. Jz A(2)dT(()) = A and 1z ((2)dT()))) b, with the matrix - A being Hurwitz. Moreover, || = suppez ||=()]] < +oc, and the mapping + A(2) is bounded, that is,
CA sup [z) V sup [z)]l <000
=EZ
=EZ
Moreover, for Σg defined in 5 assume that Amin (Ee) > 0.
To motivate the introduction of Mg in this particular form, note that under assumption A
E [=o)] = O, the following central limit theorem holds (see e.g. [23] Chapter 21D):
1 Σ -N0,
The fact that the matrix - A is Hurwitz implies that the linear system A b has unique solution 8". Moreover, this fact is sufficient to show that the matrix - aA a contraction in an appropriate matrix Q-norm for small enough >> 0. Preciscly, the following result holds:
Proposition (Proposition 1 in 667 Let A be a Hurwitz matrix. Then for any PT > there exists a unique matrix Q Moreover, setting
>
O, satisfying the Lyapunov equation A T QA = P.
a
Amin
2
and 0xec Amin (P)
Aman
1411
(7)
where KQ Amax (Q)/ Amin (Q), it holds for any a E [0, am)
that aa S 1/2, and
a- 11
ox.
For completeness we provide the proof of this result in Appendix D Now, we make an assumption about the form of step sizes a4 4 and the total number of observations nt:
3. Step sizes {ar Jken have a form ag = co (k + ko)", where y E [1/2; and the constant co 1/a)).. Moreover, we assume that sufficiently large and
Ko > g(a, bmix, Co2 CA Kig a0 (log)))))) 1) Precise expressions for g(a, tuixx Co: CA KQ; (tec)) and for given in Appendix A (see A A
The main aim of lower bounding is to ensure that the &o becomes small enough. Note also that our bound of A requires to known the number of observations n in advance and adjust accordingly. The same problem can be traced in the existing high-probability results for LSA [7 24 82). in the regime when the confidence parameter d in high-probability bounds scales with the number of iterations n..
related to the choice of initial condition
A guarantee that the sequence 8, is asymptotically normal, that is, vn(Onn - 0r) 4 NO, E. where the covariance matrix Ex has form
is known (see e.g. B11, that the assumptions A
Σx =
(8)
For a fixed u E gd-1 we consider projection of (n -0)) on and quantify the rate of convergence in the Kolmogorov distance, i.c., we consider the quantity
dx (Vruu (0.. (') ssup IP(Viuu (0, 0))o((u) <) 2(x)
(9)
=cR
where (z)) is the c.d.f. of the standard normal law NO, 1), and d²(u) TT A A -T To
control the quantity (9). we will first present an auxiliary result. Define
k
Gmskk
II (I - A.)) Qi at
GHILK
En = Σ Q.E.T (.)u)) = u E,u. (10) E=2
8=12
k=
Theorem 1. Assume A 2 and A3 (z, 2), it holds that
Then for any a S On Rdd and initial distribution on
dk (Vru"" (0,
s Bn
where we set
log.log3//
Ck.2logn n n22
cP 110
8
CD
(logn)² C
(log 1lggn)5/2 5/2 (11)
B₁ =
n/-1/2 + cP
n1/4
n
n²-1/2
where CK,1 and CK.2 are defined in Appendix
and (CPpL Nen defined in Appendix B
5

---

Proof. We provide below the main elements of the proof and refer the reader to Appendix B for complete derivations. We use the expansion (35 and (39). detailed in the appendix:
O2 0* l (0g 0*) + J + H
where we set mick II (1 a,Al (z)) and for m S k.
k
J =0
(12)
k
H
Σ
- AWJ H =0
t=1
Taking average and changing the order of summation we get that vn(On - -07) = W +
D1, with
1 n-1
R VT Σ T (bo 0*) 1 n-1
W
Vn E QiE(Ze),
DI=
Σ H 0
(13)
vn
Note that W is linear statistic of the Markov chain {Ze)EEN. We further expand it into sum of martingale -iffineee-diffeeeness and remainder terms. Note that under Al function É(2) Σx= (=)(2) a solution to Poisson equation É(2) Pε(z) E(2). We rewrite the term in the following way
W 1/2 M/3M- D2, with
n-1
M = Σ
AM, 2
=M- = Qe(E(z)) PÊ(((-1))
D2 vn
Qi6(Z))
vn 2n Qn
((ec-Q+t)PP(())
8=1
Note that (AM) 1n-1 is martingale-differrnee sequence w.r.t. oZ k S (). Note that Ex [[MMAMM]] QrE(Zz-1) Furthermore, we have T (E) = E. The term M is martingale, whose quadratic characteristic is given by (M), Σm_ @4+1ē(Z))QTT With these notations, we get
8(z) P P Pé(=)PET(s))
(14)
Vn(O, 8*) = n 1/2 D
where denote D DI + D2. Applying Proposition with X -n- 11/2 M/on(u) and Y = u D/on (u),, we obtain for any p 2,
dk ynn" (7,, -0") (O, 1)) S dk ( (n), NO, 1)) + 2
JTD (.( [1] 2/(p+1)
(15)
(u)
To obtain the rate of Gaussian approximation for V (0. 0*)/a,(u) it remains to con- trol the moments of the term |u (w), which is done in Proposition and to control dx (u M/(Vnon martingale-differenee sequences, which builds upon the arguments of [12) and (28 Proposition applied with p = log n.
To bound the latter term we use normal approximation result for sums of
Note that the result of Theorem 1 yields an approximation of Vreul (0,, 0*) with N/ o (w)). and not the limiting quantity o² from the CLT (2). In order to complete the result, we need an additional result on the Gaussian comparison between (O, of (u)) and (0 o² (u)). This result is based is based on the quantitative estimates provided first in [6], and then revised in (21]. Corollary 1. Under assumptions of Theorem holds, with Bn, given in that dx (Vnu" (0, - (0)//ou), 1)) < B, + Coon
where Cro is defined in (30).
Remark 1. The bound of Corollary prredicss the optimal error of normal approximation for Polyak-
Ruppert averaged estimates of order n. 1/4 up to a logarithmic factors n, which achieved with the step size an =co/ (k ko) 3/4 that is, when setting 7 = 3/4 in In this case obtain the optimized bound:
co/(k
dx dx(vnnu (0,, (0) (O, Spr
(log (logn) 2/2
ni74
where Spr stands for inequality up to absolute and problem-specific constants (such as CA. Kiq a, tmix), but not

---

Discussion. The proof of Corollary 1 is given in Appendix B.3 Results similar to the one of Corollary [ have been recently obtained in the literature in 67 and [3] [67 considered the LSS algorithm based on i.i.d. noise variables h<knn and randomized concentration approach based on [69. This result was later refined in [82]. However, this technique does not extend to Markovian noise { (7 ( Jssnn While preparing this manuscript, we became aware of a recent paper [83]. which provides a quantitative d-dimensional CLT for martingales. Given this work, a natural direction for further research is to use this result and generalize Theorem [ to the d-dimensional setting. The authors [83] applied their findings to the particular setting of the TD learning algorithm with Markov noise and obtained bound of the form
do(vn 0*), Ex n)
log
where 17 (O, Ta). and and dx(X, BeCn IP(X B) P(Y B) denotes the convex distance. The authors in [73] obtained the convergence rate for the general LSA procedure with Markov noise
dw (v 0+), E.K Vlogg n
where dw is the 1-st order Wasserstein distance. This result implies, due to the classical relations of between Kolmogorov and Wasserstein distance (see (62)., the final rate approximation on Kolmogorov distance of order (nn-1/12), which is slower compared to the rate of Theorem 1 On the other hand, the result of [73] holds in d-dimensional setting, whereas our analysis is restricted to one-dimensional projections of the estimation error. Nevertheless, the essential part of our analysis, namely controlling the remainder term in (15), can be generalized to the d-dimensional case through bounds on E [|] D|I"), following an approach similar to that presented in Appendix B
4 Multiplier subsample bootstrap for LSA
We will apply the multiplier subsample bootstrap (MSB) procedure, a block-based approach that constructs the bootstrap statistic via a blockwise scheme: see [7 43). Below we describe in details the MSB approach, closely following 43). Let b, be the length of block, and for each O,..., n bn-
+t,,- Or, the "scale 6n," " version of 0n. To imitate On. the MSB estimator define Ob..,= = (1/b,) Et= of 0n is given by
Vbn
bn
On (u) = Vn - bn +
wy(
0n) u,
(16)
where E, [Ze)%-1. and (weJosesn-ber the multiplier weights, are i.i.d. (N 1) random variables, which are independent of E We write, respectively, Po P(- and E. = E..)EE.)) for the corresponding conditional probability and expectation. For simplicity, we do not "subsample" the blocks: the theory extends readily, but we do not want add another layer of notations. The key idea of the MSB procedure (16) is that the "bootstrap world" distribution μal (On.s, (u) S x) should be close to their "real world" counterparts P( Vn(O,.
0*) S 2)) for any E R. Formally, the procedure (6) said to be asymptoticully valid, if the quantity
sup [P(Vn((,, =ER
) - x) (0 (u) x)]
(17)
converges to in P-probability. Typically the authors consider the asymptotic validity of the procedures for constructing the confidence intervals (either with multiplier bootstrap (29 43 or with
direct estimation of the asymptotic covariance 17 (7)). Our aim in this section to provide fully
non-asymplotic bounds on the rate at which the supremum in (17) decays as a function of n.
The MSB estimator (16) On, (u) is normally distributed w.r.t. Ib, that is,
Bn,b., (u) ~ NN0, (1))
with the variance (u) given by
bn
0g (u)
Σ ((Ob.,.- 0m) T
(18)
n bn +
The parameter by commonly referred to as lag window, or bandwidth (see 30 and references therein). Under the bootstrap probability pb, On.b.. (u) (see (66) is Gaussian approximation of 0,,
7

---

with estimated variance (u). Up to a multiplicative factor tending to 1 as n goes to oc, the variance formula in (T8) coincides with the overlapping batch mean estimator (OBM), a well-known technique for estimating the asymptotic variance of the Markov chain, suggested in 455 The properties of
OBM estimator are studied, see e.g.
[81 20 30 In particular, known (see GO), that the OBM
is consistent estimator of the asymptotic variance of Markov chain under suitable ergodicity
assumptions, provided that b, + 00 as 71 - 00.
Note that even if [Z JEEN is a Markov chain, the iterates {0k alone do not form a Markov chain (one must rather consider the joint process (0g, Zz)). Consequently, the classical consistency results for overlapping-batch batth-hhahmmss variance estimators do not apply directly to (18). Fortunately, we show below that applying the block bootstrap for the sequence {0e]. is equivalent, up to a suitable correction, to the block bootstrap procedure applied to the non non-observable random variables {=(Z,)) To make this precise, we define for each block start E {0,..... , bn) the quantities:
E+b
W
A (Z)e
W. Σ 8=1
A (o()),
bn
f=t+1
On
n-b
(u) n2 b
(WWbrtt - Wn) u)²
Then the following proposition holds:
Proposition 3. Assume A7 A2 and AD Then for any u Sd-1, it holds that
dz((w) = (w) + Roar (u).
where (u) is a remainder term defined in Appendix E. (see log and any initial distribution & on (Z, 2). it holds that
63
Moreover, for any S p S
[ (R)var(()) (1) & / n + Map* (log /6/2
(19)
+ Mapbb 1/2 + MaP (log n)n + Mspm 21-2
and the constants M, are defined in Appendix
equation (66)
The proof of Proposition is given in Appendix E. The bound of Proposition 3 has some noteworthy properties. First, our bound requires that the block size bn to grow at least like nz to ensure that the residual term Rear(u) (u) is small. Careful inspection of the bootstrap estimator On,s, (u) from (16) explains this dependence. Indeed, one can expect that the decay rate of the covariance between 0g and
0x+b, depends on the quantity Ek+h Oc see e.g. [22] At the same time, for bn = n n,, < B < 1,
and ag = co/ + k)),, which is set according to AB we obtain that
Elth Ek=t+1 Og S bn,/t"
Hence, if b, < n,, the sequence }0x} does not mix within each block t S S
Given that the remainder term Rear(u) in 199 is negligible, it remains analyze the concentration properties of (u). Indeed, under All and A the (normalized) linear statistic n 1/2 Di=o u e(z)
is asymptotically normal with the asymptotic variance equal o² (u) defined in ( Moreover, 6² (u) coincides with the overlapping batch mean estimator of (²().. In order to prove concentration bounds for (u) around (u), we apply the result of (50] Theorem 1].
Proposition 4. Assume AT and Al Then any 2 2, and n 2 2b,, 1, and any initial distribution & on (Z, 2), it holds that
pt3
EE Vn
p2r2 mix Vb 11
f 1E
o2 (2 B -
Vn
Vbn
The result above is based on martingale decomposition, associated with the Poisson equation for quadratic forms of Markov chains, as introduced in [5]. Now, combining the estimates of Proposi- tions and and applying Markov's inequality with p = log n, we obtain the following result:
Corollary 2. Let n be large enough. Set bn
3/3/47, 1, E (0; 1/ log n)) and let ag co/(ko +
1///2+e, Then, with probability at least 1 n1 holds that
[0](u) o² ou( Slog n 1/8tt//2
(20)
8

---

Discussion. The version of Corollary 2 with explicit constants and explicit power of log n is provided Appendix(E.3] together with the proof of Corollary [ Note that the fastest decay rate the r.h. of 20 is achieved when we set 6, = (n4) and aggressive step sizes ay co/ (kg + +) 1/2+t The same choice of hyperparameters appears to be optimal in the recent work of [63] for batch-mean estimators of the asymptotic variance for the SGD algorithm, even in case of controlled Markov chain. We also recover the rate -1/8 (up to logarithmic factors), that previously appeared in [63]
The authors of [7 [9 also considered the batch mean estimators Σ, of the asymptotic variance Moc in case of SGD algorithms with independent noise and obtained the same (up to logarithmic factors) convergence rate E| EI - Exe |I] S 11/8__ Morcover, the optimal rate for recovering Eg in [17 Corollary 4.5] and [79] Corollary 3.4] is attained for the step sizes aj = 1/k? with y + 1/2. This is on par with findings of Corollary 2 At the same time, should note that this choice of step sizes yields extremely slow convergence rates in the CLT in Theorem [] This introduces an additional trade-off, that needs be taken into account when considering the decay rate of (17). Namely, one needs to balance not only the right-hand sides of Corollary and Proposition]
3 but also to take into
account the convergence rate in Theorem
[
The respective trade-off yields
bn 11,, OAk co/ (ho k))3/5
(21)
The corresponding main theorem writes as follows:
Theorem 2. Assume A A2 and A3 let be large enough, set bn = [n4/3,, oz = co/ + k)3/5.
Then for any u E Sa-1, and any initial distribution & on (Z, 2), it holds with --pobbability at least 1 1/n that
sup PP(vn(B, - 8¹) 5xx) x) (b (4) S 2²) Slogn n -1/10 ERR
Proof. We provide the detailed proof of Theorem 2 of condition on n. The proof is based on the following scheme:
in Appendix
E.4 together with the explicit form
Real world: (0n 0*)
Gaussian approximation. Cor.
E N(, o(O,0²(
Gaussian comparison
(22)
Bootstrap world:
(n,
exactly matches distribution
gb ~N(,00(()))
Due to Corollary D it holds that
dx (Vn -0,
).) Stogn n 1/4 + 1//2-2 n²
where { ~ (N, 1). This result allows for the first horizontal bar above. We now the Gaussian
comparison (see 6 (21), which states that for & ~ NN(0, of),, i= 1, are such that lo7/o? - <
8, for some 2 O, suP=ER [PP(E1 S x) - P(E2 I x)) I 5. We apply the Gaussian comparison
between the limiting Gaussian & ~ NO00, o² (w)) and gh ~ (0) For this purpose, we need to obtain a high probability bound for (u) o² (o))(. Combining Proposition 3 Proposition
and Markov's inequality, we get that with probability at least 1/n,
(w) (2()))/o02 (u) Stogn 0/22 + b2/2n bn 7/2 + 2 /2/2 1/2
Now note that by construction 0n.b ~ -N(0, (u)) under the bootstrap probability. Hence, with probability least 1 1/n, it holds that
1/2
1/2
b
1
1
dx (Vru (0n, - 0²), Om..) Stogo
+
1--1/2
12/2
1/2
n1/4 12-1//2
n2--7
To complete the proof, it remains to optimize our choice of y and b,, which yields to 21
Discussion. Non-asymptotic analysis of coverage probabilities has been carried out for the modifi- cations of multiplier bootstrap approach of [2 in recent papers 70). These approaches showed that coverage probabilities of 8" can be approximated by their bootstrap counterparts with the order up to (nnn1/3) Yet for this bootstrap approach is crucial to work in the independent noise setting. The attempt of [59] to generalize it for the case of Markovian noise yields inconsistent procedure, as

---

shown in 42 Proposition 1]. That is why we prefer to start from the asymptotically consistent MSB Our bootstrap validity proof relies on direct approximation of /nu (0n 8*) by the limiting Gaussian distribution (00, a² (u)). At the same time, it is known (see 70 that under i.i.d. conditions, may more advantageous in the proof scheme 22 of the non-asymptotic validity of the bootstrap procedure for /nuu (0n, 0*) using another Gaussian distribution (0, of (u)) and its "bootstrap" analogue. It remains an open question if this reasoning can be applied in case of dependent random variables.
procedure 43
5 Application to the TD learning
We illustrate our findings via the temporal-difference (TD) learning algorithm 75
76 for policy
evaluation in discounted Markov Reward Process (MRP) (S, R. A). Here, S is complete metric space with its Borel o-algebra; P(- 8) denotes the state transition kernel; R :: S + [0, 1] is the scalar reward function; À [0, is the discount factor. The value function is given by
V(8)
= E
x R(S))) So = s] where Sk+1
k=
We approximate (ss) in linear feature space: Vo(s) = ( where yp S Rd. We impose two standard assumptions:
TD1. P is uniformly geometrically ergodic with unique invariant distribution and mixing time T.
We also define the design matrix Eg [s) and require that non-degenerate:
TD Eg non-degenerate, i.e. Amin(EEp)) 0. Moreover, supses [|{(()) < 1.
Then TD learning is an instance of LSA with
A = ( Xx((S++1) E, by = (($a) R(5x).
Detailed derivations are given in Appendix H Refining constants following [53 68 one shows:
Proposition 5. Under TD and TD the TD updates satisfy the noise level condition A2 with
CA = 2(1++) A) and 0o 2(1+A)( it holds that [ aA
aa, where (11). Moreover, for step size a S ax = (1- x)/ A)?. X) Aminn (F.p)
By 67 Proposition 2]. this ensures that Proposition 2 holds with Q = and hence Theorem 2 applies directly to the TD scheme. We provide numerical simulations in Appendix H
6 Conclusion
We presented the non-asympiotic Berry-Esseen bounds for Polyak-Rupperr averaged iterates of linear stochastic approximation algorithm under Markovian noise, achieving convergence rates of order up to n- 1/4 -14 in Kolmogorov distance. Additionally, we established the theoretical validity of a multiplier subsample bootstrap procedure, enabling reliable uncertainty quantification in the setting of the LSA algorithm with Markovian noise. Our paper suggest number of further research directions. One of them is related with the generalizations of Theorem to the setting of non-linear SA algorithms, as well with obtaining multivariate version of it. It is also an interesting and important question if our non-asymptotic bounds on coverage probabilities provided in Theorem 2 can be further improved.
10

---

Acknowledgment
The work was supported by the grant for research centers in the field of Al provided by the Ministry of Economic Development of the Russian Federation in accordance with the agreement 10000CC31332SS4400000 and the agreement with HSE University No 139-15-2025-009, This research was supported in part through computational resources of HPC facilities at HSE University [36].
References
[1] Bhavya Agrawalla, Krishnakumar Balasubramanian, and Promit Ghosal. High-dimensional central limit theorems for linear functionals of online least-squares sgd. arXiv preprint arXiv:2302.09727, 2023.
[2] Rafik Aguech, Eric Moulines, and Pierre Priouret. On a perturbation approach for the analysis of stochastic tracking algorithms. SIAM Journal on Control and Optimization, 39(3):872-899 2000.
[3] Andreas Anastasiou, Krishnakumar Balasubramanian, and Murat A. Erdogdu. Normal ap- proximation for stochastic gradient descent via non-asymptotic rates of martingale CLT. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 115-137.
PMLR, 25-28 Jun 2019.
[4] TW Archibald, KIM McKinnon, and LC Thomas. On generation of markov decision processes. Journal of the Operational Research Society, 46(3):354-361, 1995.
[5] Yves F Atchadé and Matias D Cattaneo. A martingale decomposition for quadratic forms of Markov chains (with applications). Stochastic Processes and their Applications, 124(1):646, 677, 2014.
[6] S. Barsov and V. Ulyanov. Estimates for the closeness of Gaussian measures. Dokl. Akad. Nauk SSSR, 291(2):273-277 1986.
[7] V. Bentkus. On the dependence of the Berry-Esseen bound on dimension. Journal of Statistical Planning and Inference, 113(2):385-40)) 2003.
[8] A. Benveniste, M. Métivier, and P. Priouret. Adaptive algorithms and stochastic approximations, volume 22. Springer Science & Business Media, 2012.
[9] Patrice Bertail and Stéphan Clémençon. Edgeworth expansions of suitably normalized sample mean statistics for atomic markov chains. Probability Theory and Related Fields, 130(3):388- 414, 2004.
[10] J. Bhandari, D. Russo, and R. Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference On Learning Theory, pages 1691-1692, 2018.
[11] E. Bolthausen. The berry-esseén theorem for strongly mixing harris recurrent markov chains. Zeitschrift für Wahrecheiniccheeissheerr und Verwandte Gebiete, 60(3):283-289, 1982.
[12] E. Bolthausen. Exact Convergence Rates in Some Martingale Central Limit Theorems. The Annals of Probability, 10(3):672 688, 1982.
[13] Erwin Bolthausen. The berry-esseen theorem for functionals of discrete markov chains. Zeitschrift für Wahnscheenlicckeesstheerrr und verwandte Gebiete, 54(1):59-73, 1980.
[14] Vivek S Borkar. Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press, 2008
[15] Haoyu Chen, Wenbin Lu, and Rui Song. Statistical inference for online decision making via stochastic gradient descent. Journal of the American Statistical Association, 116(53))708-719, 2021.
[16] Louis H.Y. Chen and Qi-Man Shao. Normal approximation for nonlinear statistics using concentration inequality approach. Bernoulli, 13(2):581 599, 2007.

---

[17] Xi Chen, Jason D. Lee, Xin T. Tong, and Yichen Zhang. Statistical inference for model parameters stochastic gradient descent. The Annals of Statistics, 48(1):251 223,, 2020.
[18] Victor Chernozhukov, Denis Chetverikov, and Kengo Kato. Gaussian approximations and multiplier bootstrap for maxima of sums of high-dimensional random vectors. Ann. Statist., 41(6):2786- 2819, 2013.
[19] Victor Chernozhukov, Denis Chetverikov, and Kengo Kato. Central limit theorems and bootstrap in high dimensions. Annals of Probability, 45(4):2309-234) 2017.
[20] Halim Damerdji. Strong consistency and other properties of the spectral variance estimator.
Management Science, 37(11):1424-1440 1991.
[21] Luc Devroye, Abbas Mehrabian, and Tommy Reddad. The total variation distance between high-dimensional gaussians with the same mean. arXiv preprint arXiv:1810.08663 2018.
[22] Aymeric Dieuleveut, Alain Durmus, and Francis Bach. Bridging the gap between constant step size stochastic gradient descent and Markov chains. The Annals of Statistics, 48(3):1348 1382, 2020.
[23] R. Douc, F. Moulines, P. Priouret, and P. Soulier. Markov chains. Springer Series in Operations Research and Financial Engineering. Springer, 2018.
[24] Alain Durmus, Eric Moulines, Alexey Naumov, and Sergey Samsonov. Finite-time High- Probability Bounds for
averaged iterates of Linear Stochastic Approximation. Mathematics of Operations Research, 50(2):935-964, 2025.
[25] Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Samsonov, Kevin Scaman, and Hoi-To Wai. Tight high probability bounds for linear stochastic approximation with fixed stepsize. In M. Ranzato, A. Beygelzimer, K. Nguyen, P. S. Liang, J. W. Vaughan, and Y. Dauphin, editors, Advances in Neural Information Processing Systems, volume 34, pages 30063-30074. Curran Associates, Inc., 2021.
[26] Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Samsonov, and Ho Wai. On the stability of random matrix product with markovian noise: Application to linear stochastic approximation and td learning. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 1711-1752. PMLR, 15-19 Aug 2021.
[27] Bradley Efron. Bootstrap methods: another look at the jackknife. In Breakthroughs in statistics: Methodology and distribution, pages 569-593. Springer, 1992.
[28] Xiequan Fan. Exact rates of convergence in some martingale central limit theorems. Journal of Mathematical Analysis and Applications, 469(2):1028-1044 2019.
[29] Yuan Fang, Jing Xu, and Lijun Yang. Online bootstrap confidence intervals for the stochastic gradient descent estimator. Journal of Machine Learning Research, 19(78):1-21, 2018. 2018.
[30] James M. Flegal and Galin L. Jones. Batch means and spectral variance estimators in Markov chain Monte Carlo. Ann. Statist., 38(2):1034-1070 04 2010.
[31] G. Fort. Central limit theorems for stochastic approximation with controlled Markov chain dynamics, ESAIM: PS, 19:60-80, 2015.
[32] Matthiu Geist, Bruno Scherrer, et al. Off- learning with eligibility traces: survey. J. Mach. Learn, Res., 15(1):289-333 2014.
[33] De Huang, Jonathan Niles-Weed, Joel A Tropp, and Rachel Ward. Matrix concentration for products. Foundations of Computational Mathematics, pages 1-33, 2021.
[34] Benoît Kloeckner. Effective Berry-Essecn and concentration bounds for Markov chains with spectral gap. Ann. Appl. Probab., 2977)1178-18077, 2019.
[35] Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999.
12

---

[36] PS Kostenetskiy. RA Chulkevich, and VI Kozyrev. Hpc resources of the higher school of economics. In Journal of Physics: Conference Series, volume 1740, page 012050. IOP Publishing, 2021.
[37] Hans R Kunsch. The jackknife and the bootstrap for general stationary observations. The annals 1989.
of Statisties,
[38] Harold Kushner and G George Yin. Stochastic approximation and recursive algorithms and applications, volume 35. Springer Science Business Media, 2003.
[39] C.r Lakshminarayanan and Csaba Szepesvari. Linear stochastic approximation: How far does constant step-size and iterate averaging go? In Amos Storkey and Fernando Perez-Cruz, editors, Proceedings of the Twenty-Firsh International Conference Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 1347-1355, PMLR, 2018.
[40] Xiang Li, Jiadong Liang, and Zhihua Zhang. Online statistical inference for nonlinear stochastic approximation with Markovian data, arXiv preprint arXiv:2302.0700 2023.
[41] Xiang Li, Wenhao Yang, Jiadong Liang, Zhihua Zhang, and Michael Jordan. A statistical analysis of Polyak-Ruppert averaged Q-learning. In International Conference on Artificial Intelligence and Statistics, pages 2207-2261. PMLR, 2023.
[42] Ruiqi Liu, Xi Chen, and Zuofeng Shang. Statistical inference with Stochastic Gradient Methods under o-mixing Data. arXiv preprint arXiv:2302. 12717, 2023.
[43] Ruru Ma and Shibin Zhang. Multiplier subsample bootstrap for statistics of time series. J. Statist. Plann. Inference, 233:Paper No. 106183, 83, 15, 2024.
[44] Mohamed El Machkouri and Lahcen Ouchti. Exact convergence rates in the central limit theorem for a class of martingales. Bernoulli, 13(4),981-999, 2007.
[45] Marc S Meketon and Bruce Schmeiser. Overlapping batch means: Something for nothing? Technical report, Institute of Electrical and Electronics Engineers (IEEE), 1984.
[46] Abdelkader Mokkadem and Mariane Pelletier. Convergence rate and averaging of nonlinear two- time-scale stochastic approximation algorithms. The Annals of Applied Probability, 16(3):1671- 1702, 2006.
[47] Wenlong Mou, Chris Junchi Li, Martin Wainwright, Peter Bartlett, and Michael I Jordan. On linear stochastic approximation: Fine-grained polyak-ruppert and non-asymptotic concentration. In Conference on Learning Theory, pages 2947-2997. PMIR, 2020.
[48] Wenlong Mou, Ashwin Pananjady, Martin J Wainwright, and Peter I. Bartlett. Optimal and instance-dependent guarantees for markovian linear stochastic approximation. arXiv preprint 122172211 2021.
[49] Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algo- rithms for machine learning. Advances neural information processing systems, 24:451-455 2011.
[50] Eric Moulines, Alexey Naumov, and Sergey Samsonov. A note concentration inequali- ties for the overlapped batch mean variance estimators for Markov chains. arXiv preprint arXiv:2505.088 008556,, 2025.
[51] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 1974 1609, 2009.
[52] A. Osekowski. Sharp Martingale and Semimartingale Inequalities. Monografie Matematyczne 72. Birkhäuser Basel, 1 edition, 2012.
13

---

[53] Gandhary Patil, LA Prashanth. Dheeraj Nagaraj, and Doina Precup. Finite time analysis of tem- poral difference learning with linear function approximation: Tail averaging and regularisation. In International Conference on Artificial Intelligence and Statistics, pages 3438-5448. PMLR,
2023.
[54] Daniel Paulin. Concentration inequalities for Markov chains by Marton couplings and spectral methods. Electronic Journal of Probability, 20(none): 32, 2015.
[55] V. Petrov, Sums of Independent Random Variables. Ergebnisse der Mathematik und ihrer Grenzgebiete. 2. Folge. Springer Berlin Heidelberg, 1975.
[56] Iosif Pinelis. Optimum Bounds for the Distributions of Martingales in Banach Spaces. The Annals of Probability, 22(4):1679 - 1706, 1994.
[57] Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal control and optimization, 30(4):838 855, 1992.
[58] Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 1571-1578, 2012.
[59] Pratik Ramprasad, Yuantong Li, Zhuoran Yang, Zhaoran Wang, Will Wei Sun, and Guang Cheng. Online bootstrap inference for policy evaluation in reinforcement learning. J. Amer. Statist. Assoc., 1 118(544):201-299) 2023.
[60] E. Rio. Asymptotic Theory of Weakly Dependent Random Processes. Springer, 2017.
[61] H. Rosenthal. On the subspaces of L (p 2) spanned by sequences of independent random variables. Israel J. Math., 8:273-303, 1970.
[62] Nathan Ross. Fundamentals of Stein's method. Probah. Surv., 8:210-293, 2011.
[63] Abhishek Roy and Krishnakumar Balasubramanian. Online covariance estimation for stochastic gradient deseent under Markovian sampling. arXiv preprint vrXiv:2308.01481, 2023.
[64] Donald B Rubin. The bayesian bootstrap. The annals of statistics, pages 130-134, 1981.
[65] David Ruppert. Efficient estimations from a slowly convergent robbins-monro process. Techni- cal report, Cornell University Operations Research and Industrial Engineering, 1988.
[66] Adrian Röllin. On quantitative bounds in the mean martingale central limit theorem. Statisties & Probability Letters, 138:171-1741 2018.
[67] Sergey Samsonov, Eric Moulines, Qi-Man Shao, Zhuo-Song Zhang, and Alexey Naumov. Gaus- sian Approximation and Multiplier Bootstrap for Volyak-Ruuper Averaged Linear Stochastic Approximation with Applications to TD Learning. In Advances in Neural Information Process- ing Systems, volume 37, pages 12408-1240 Curran Associates, Inc., 2024.
[68] Sergey Samsonov, Daniil Tiapkin, Alexey Naumov, and Eric Moulines. Improved High- Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 1551-4 PMLR, 30 Jun 00 Jul 2024.
[69] Qi-Man Shao and Zhuo-Song Zhang. Berre-Esseen bounds for multivariate nonlinear statis- ties with applications to M-estimators and stochastic gradient descent algorithms. Bernoulli, 28(3):1548 1576, 2022.
[70] Marina Sheshukova, Sergey Samsonov, Denis Belomestny, Eric Moulines, Qi-Man Shao, Zhuo-Song Zhang, and Alexey Naumov. Gaussian approximation and multiplier bootstrap for stochastic gradient descent. arXiv preprint arXiv:2502.06719 2025.
[71] Galen R. Shorack. Probability for Statisticians. Springer Texts Statisties. Springer, edition, 2017.
14

---

[72] Vladimir Spokoiny and Mayya Zhilova. Bootstrap confidence sets under model misspecificatiio. The Annals of Statistics, 43(6):2653 2675, 2015.
[73] Srikant. Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning. arXiv preprint vrXiv:2401.15711 2024.
[74] R. Srikant and L. Ying. Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning. In Conference on Learning Theory, 2019.
[75] R. S Sutton. Learning to predict by the methods of temporal differences. Machine learning. 3(1):9-44, 1988.
[76] R. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018.
[77] J. N. Tsitsiklis and B. Van Roy. An analysis of temporal-differennce learning with function approximation. IEEE Transactions on Automatic Control, 42(5):674-690, May 1997.
[78] Ramon Van Handel. Probability in High Dimension. APC 550 Lecture Notes, Princeton University, 2016.
[79] Xi Chen Wanrong Zhu and Wei Biao Wu. Online Covariance Matrix Estimation in Stochastic Gradient Descent. Journal of the American Statistical Association, 118(541):393-404, 2023,
[80] C.topher J.C.H. Watkins and P. Dayan. Technical note: Q-learning. Machine Learning. 8(3):279-222, May 1992.
[81] Peter Welch. the relationship between batch means, overlapping means and spectral estimation. In Proceedings of the 19th conference on Winter simulation, pages 320-323, 1987.
[82] Weichen Wu, Gen Li, Yuting Wei, and Alessandro Rinaldo. Statistical Inference for Temporal Difference Learning with Linear Function Approximation. arXiv preprint arXiv:2410.161066 2024.
[83] Weichen Wu, Yuting Wei, and Alessandro Rinaldo. Uncertainty quantification for Markov chains with application to temporal difference learning. arXiv preprint vrXiv:2502.13822 2025.
[84] Bin Yu. Rates of convergence for empirical processes of stationary mixing sequences. The Annals of Probability, pages 94-11, 1994.
[85] Yanjie Zhong, Todd Kuffner, and Soumendra Lahiri. Online Bootstrap Inference with Noncon- vex Stochastic Gradient Descent Estimator. arXiv preprint arXiv:2306.02200 2023.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly and accurately enumerate the paper's core theoretical contributions-namelll (i) non-asymptotic Berry-Esseen bounds order (n/1/) for the Dolyak-Rupper averaged iterates under Markovian noise (formalized in Theorem and detailed in Corollary 1) and (ii) multiplier block bootstrap procedure with provable non-asymptotie validity (stated in Theorem 2) that yields consistent confidence intervals and recovers the classical O ((nn1/8) rate (up to logarithmic factors) for variance estimation These claims match exactly the main results presented in Sections 3 and 4 (and their appendices), and each supported by complete proofs the supplementary material Main results are, respectively, the ones of Theorem [ T and Corollary Corollary their statements are complete and supported by the proofs the Appendix section.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
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 other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The paper explicitly addresses limitations, such the focus linear stochastic approximation (LSA) and one-dimensional projections of estimation errors, as well as the challenges of extending Berry-Esseen bounds to higher-dimensional settings and nonlinear SA problems (see Section Section Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are 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 on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should 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 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 faimess.
16

---

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 a complete (and correct) proof?
Answer: [Yes]
Justification: All theoretical results in the paper are given with references to the assumptions
stated in Section All results are given with detailed proofs, provided in the appendix. The proofs are correctly referenced for each theorem and corollary.
Guidelines:
The answer NA means that the paper does 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 in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if 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.
Thcorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Numerical results are stated with complete description of the environments that are used, as well the precise sets of hyperparameters that we used. The code (in Python) is provided as supplementary with the paper, making easy for one to reproduce our numerical 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 perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access 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 replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate 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.
17

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is 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 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
All code is open source, link to to an anonymous GitHub repository is included.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://niis.ccm cc/
cablic/guides/// Sotaass/oooSSunnsssioooooooooo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results, See the NeurlPS code and data submission guidelines (https
/ //nips.ccppulic//gne
www.issssiniiiiiiiocooii for more details.
The authors should provide instructions 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, to 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 (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The algorithm used in the numerical experiments are exactly the algorithms described in the paper. The Garnet environements are given with the parameters used for generation, and with reference to the original problem (see Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
18

---

Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We provides error bars.
Guidelines:
The answer NA means that the paper does 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 main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialisation, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of 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 range (c.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
All necessary information to reproduce experiments is provided Section
Guidelines:
The answer NA means that the paper does not 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 http:://hheorrppscppppppc///eeea
Answer: [Yes]
Justification: This paper is of purely theoretical nature, and the proposed methods do not deal with sensitive attributes that could induce unfairness or privacy issues.
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 deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
19

---

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 purely theoretical in nature and has no societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a 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 intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper contains no models or datasets with potential for misuse.
Guidelines:
The answer NA means that the paper poses 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 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 encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [NA]
Justification:
No existing assets used.
Guidelines:
20

---

The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (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 in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should provided.
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:
No new assets were introduced this research.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/mooel 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 is used.
At submission time, remember 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 to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper doesn't 't involve crowdsourcing or human research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, 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 or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve either crowdsourcing human subjects research.
21

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question:
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The paper does not involve the of LLMs related methods.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our L.LM policy for what should or should not be described.
22

---

Contents
Introduction
2
Related works
Accuracy of Gaussian approximation for LSA with Markov noise
3.1
Gaussian approximation for non-linear statistics
3.2 Gaussian approximation for LSA with Markov noise
Multiplier subsample bootstrap for LSA
Application the TD learning
10
6
Conclusion
10
Extended version of A3
24
Proof of Section
24
B.J
Gaussian approximation for sums of ceattingale-differemee sequences
25
2 Bound for the remainder term
28
B.3 Proof of Corollary
29
B.4 Technical bounds
30
Last iterate bound
34
Proof of Proposition
36
C,2 Proof of !! bound
36
C.3 Technical bounds related J
40
D Proofs for stability of matrix products
41
D.1 Stability
D.2 Proof of Proposition
44
D.3 Proof of Proposition]
45
Proof' of Section|4]
46
E. Proof of Proposition
46
Technical hounds
47
E.3 Proof of Corollary
54
Detailed version of the proof of Theorem
54
Probability inequalities
55
Rosenthal and Burkholder inequalities
56
Auxiliary results on the sequences of step sizes
[0g KEN under A3
57
23

---

Applications to the TD learning algorithm
62
Extended version of A
In this section, we present the full version of with explicit constants.
A' 3. The sequence of step sizes {ay MEN has a form as cu/(k: + ko), where [1/2; and, with
1/2 CA
16x
(23)
a
holds that
1
Co
S
(24)
2a
Moreover, the number of observations n and parameter kg satisfy
n. 1 2 max( 20% 00
0
20(111)).
Amiu
(E0))
1/(1-1/
(co(t + 1) max( KQ
1/2 CA. benq CA c2/aa) 1/7
ko 2 max
aco
(25)
1/2 CA 8lmix
12(h + 1)(log Co
1/7
a
2 cab b(27 1)27 + log
logt
co
Discussion. The lower bound on the sample size n in (25) is required to guarantee the non- degeneracy of the empirical covariance matrix Σ, (see its definition in (TO) and Lemmal IO). This condition ensures that Amin (E,) remains bounded away from zero, which is crucial for the proof of rate of convergence in CLT for LSA problem.
Furthermore, the constraint on ko, which scales as ko Z (logn) is imposed to control higher- order moments the product of random matrices appearing the recursion (see Proposition [2]. In particular, this ensures that moments up to order ~ log remain finite, which is necessary for establishing the Gaussian approximation bounds used in the main result.
While this assumption could, in principle, be relaxed, doing so would lead to a degradation in the Gaussian approximation rate from n 1// to -1/4+<(p) where the function spp) depends on the number of finite moments available for the random matrix product.
B Proof of Section 3
Recall that in the proof of Theorem (see 15 obtained that
dx Vnuu" T (0n 0*)
ou,(u) .N(0.1)) dx( u M Vnan
.N((,,)) + 2 u D
1r1 1/(0-1) an(u)
Hence, to conclude with the proof it remains to
(i) control the Kolmogorov distance dx (no)(())
iii bound the moments of [u]
We present the required result for item (i) in Appendix Appendix B.] below.
B.1 (see Proposition 6 and for (ii) in

---

B.1 Gaussian approximation for sums of martingale-differenn sequences
In this section we establish rate of convergence sums of martingale-diffrrnne to the gaussian limit. We follow the approach of (28), which builds upon the work [12]. Recall that
M Σ AMe AM, = (e(e(z)) - Pε(Z)-1))
Note that the quadratic characteristic
Blju A AMP Ze-1] u Qr 6(z) PεE (z) Pé(=) (z)
is not constant a.s.. Hence, one can not directly apply the results on martingale CLT due to 12 Theorem 2]. Below we first formulate this result, and then demonstrate how to mitigate the problem of time-varying quadratic characteristic following the approach of 66 28
CLT for martingales with constant quadratic characteristic. Let X = (X....., Xn.) be
sequence of real valued random variables which are square integrable and satisfy |EX; [Fi = 0, a.s. for S i S n, where F; = o(.i..... X.). We denote the class of such sequences of length n by M, Denote
of = 1111
=
" = Σ
j=1
|X||, = max 15j5n
|Xilmm sSpso,
and, with 1 S k I n, we have
k
V22 = Σ
/s/
S
Σ x,
n
j=1
Theorem 3 (Theorem 2 in (12). Leto < oo. There exists a constant 0 < L(x) oc depending only on x, such that for all X MM, n 2 2, salisfying
|| S x,
V²2 =22 las.,
the following bound holds
dx (Sn//n) S L(x)m l/gn/s.
The constant L(x) can be quantified following the work of Adrian Röllin, see [66]. but exact calculations are beyond the scope of this paper. Now we adapt the arguments from [28] based on
[12] to provide the counterpart of this result with time-varying quadratic characteristic. We specify the constants and dependence on p since we need to have possibility take p of logarithmic order with respect to
Lemma 1. Let 0 < x < co. Then, with L(x) defined in Theorem for all X E Mn, 2 2,
satisfying || | x0 S x,, the following bound holds for any p Z
dx (Sn/8n)) (2x + 1) lon(2n + 1)
83
+ C1 Ciyps
E
Σ i-l of - - 2/(2p+1) - + C2sn
2p41
3p
px 2p/ 2n/ (2p+1)
where we have defined the constants C₁ 2 CRm.1 C2 = 4(CRm,1 + CRm.2).
Proof. Consider the following stopping time sup(0 S k 5 n: V2 < 1). Denote
L( Σ 13
25

---

Note that r S n. Let N = 2n + 1. Construct the following sequence X' = (X1, [X])...,xx)):
X =
X 20 T X (s of - T/s +
and X 0,
+ 2. Here d are Rademacher random variables, which independent of all other r.v's. Then X' is a vector of martingale increments w.r.t. an extended filtration Fi (Xx, Nj. S i), and, by construction
Σ E(())) PFLL11
Σ oi rz + sn
Eo rz sn.
Applying Proposition 14 with X S and Y S Sn. get
2y
dx (Sn/8n) S dx (S'x/6n) + 28n 2p+1 (BBlIs, - S/x PP111/22011)
(26)
We control the term dx (s/) with [2 Theorem 2]:
dx (8///n) S L(x) log
In order to control the second term in the right-hand side of 26 notice that
S. Sy
Σ (x,
-X)
Σ
L X²)
12++1
1=1
Since is stopping time, condition on it and get by the Rosenthal's inequality
N
S| - S |2 < C
R
BB
Σ
B - -X) +
Rm.
P
max
[X; - 2
+ISISN
i=
It is easy to see that
NN
N Σ
-(XX,X)) =
Σ
E[
B(Xx)
0 1
0
1=1
Note that
$ - <
im
Hence, it holds that
Σ
B[(X, - x() 5 Σ
0, 9 2x
Finally,
n
E S. - 121 20
Ci2 Rm,
pd (E) Σ o.
22 + 2P
+ C2p
Rm, (2p))22)) (00))t))))
Substituting the above bound into 26
obtain
dx (Sn/sn) s dx (s)
2r + 2sn (2p-1)
T
22p Rm.1
pd
(E Σ
of
2 + 2P) + C2p 22p))(2p)2) 200g
and the statement follows.
We now state lemma that allows us specify the result of Lemma I to the martingale M and its quadratic characteristic (M),. given in (14)
26

---

Lemma 2. Assume A Then for any u E S probability measure on (Z, 2), and p 2 2:
E 1 ( - (oo 32n /2p/ fl 5/2
Proof. Using the definition (1). we get:
n-2
((, Σ (he(Ze) m(he)} where he(z) = u (Q++1(())
Em1
Note that using Lemma 3. for any 2, 2' E Z and any LE m 2] we have
= 4c311<())11 22 - h=(('))()))
Scc Σ A(P
k=
Ami--1
Σ
2(8/3) (ole
k=0
We then apply [54 (Corollary 2.11], showing that for all 1 0,
( n-1
t2
(he( - (bo)) 2 t) - exxp
where
Up = (64/3) mix" ///2n1/2 1/2
2n
We conclude by using 24 Lemma 7].
By combining Lemma D and Lemma
we finally get the following result:
Proposition 6. Assume A7
A2 and Then for any u E Sd-1 and 2 1:
u TMM
L(x (2x 1) log 2n + 1)02
dx(
v Vrian(u)
33/2
2p
2p
+ +4v201 ( (CollelloO&s
2p+1
mix 3/1 n 1(2p+1) C2n 2p+1 P.
6/4
(16Coleells(ss
Os
2p+1
pfmix
3
where x (16//)||s||| fo folmix constants C1 C2 are defined in Lemma | LQ is defined in Lemmal and Cx. is defined Lemma 10 Moreover, setting = log n, we obtain that
u TTM
CK.1 3/1
CK. logn
dx
n²/4 +
Vno,
n//2
where the constants CK,1 and CK,2 are given by
CK,1 = 4V2. C 5/1 folell
1/c C2Co 20
CK.2
+ 3L(xx) + 3L(x) log 3C
Proof of Proposition
Using Lemma with s = no (u), we obtain
2
T
M
L(x)(2n 1) log
dx(
VTa (u)
n3/20 (u)
2y (Elu² (M) no (u))))))) 2/(2+11)
(2() i 20/
#P41
where the particular form of follows from 70p To complete the proof, it remains to control the p-th moment of u (M), (u), which is established in Lemma 2 Finally, we note that कr is bounded, follows from Lemma 10 which concludes the argument.
27

---

B.2 Bound for the remainder term D
Recall that
D1 + D2, where
n-1 1
1 n-1
D1 =
r r (Bu -8") +
vn Σ H 00) e(ee)
km0
kml
(27)
1 Q)E(Zz)+
1
D2 vn
vn Qn-
and " are defined in 12 Then we obtain the following bound on the moments of D:
Proposition 7. Assume Al A2 and A3 and Ko 2 max( dcc ( )) Then for any 2 S p S
log n,, S and any mitial distribution on (Z, 2), holds that
E 1/++t) (w) & (CP, |10 1 + cp P.2)) + CP (22
+ CC, tr? Vlog nn 12-3po(ott)
where
kg aco(1 7)
CP, C2Crdd/logn
C²2 Cs.llE Cot
C² Crcolmix
kō (Go2llelloo + v Vlog (
1-7
co
CP, CDDS cotmixy/
(M)
Moreover setting p log we have
E 1=/(++1] [[u ((uTD)//n(w))) i (cP 100 0-1 + c2)m-1/2 (gog (n
+ c 55/3 1/277
and
= Veck fori [1,2,3,4]
Proof.
We first note that ., (u) is bounded, follows from Lemma 10 that is,
E [[ T (0) < CL
// [lu
DP]
In order to bound E [1u T DPP. we bound the terms D₁ and D2 from 27 separately. Note that
u D1 Dn1 + D12, Dn1
1
T1: -²). D12
u H (0)
Now we use the result of Proposition
12 to bound Eg [[[[TTi IPs. and obtain that
1/p / D11 11 S E
/logn
exp
(a/122)
a 1100 1-
k=
Applying Lemma 24 and Lemmal 31
EE 1 1 $ Ordg/logn
aCp
((k + ko) ko) -1k))
-k3) 100 -0 (28)
exp
24(1 7)
k=0
X /logn
1
kj
1100 0-
Vn aco
77)
28

---

C It follows from Minkowski's inequality and Proposition 10 that
D3 (M mmixp
11111
E
1/p
- H
(0)
1p vn
Σ an V log (1/ox)
k=1
k=1
(M) log
co
(n + hio
1)7 ((n
-
1i))
kn -)
(29)
vn
D3 co
Kg In 1/2
yog
co
Similarly, T D2 = D21 + D22 + D32, where
D21 - (1&())))))
Vn
1
D22
u Qnn-PE((Zn11)
Vn
D32 = Σ
u (Q: (e(1))
t=1
For D21 and D22 we use Lemma 3 to bound (8/3)mii/|/e/// Then obtain
||Qzll together with the upper bound [|ě(z)] s
m 1mxxll/llec&
B D2n Pl B ((22)
x
vn
It remains to bound D2 p] Using Lemma to bound the difference Qt Qe+1, and Minkowski's inequality, we get
Lo.2tmix || R-1
Lo.etmix ( n 1/2-7
E D2 "
ar x 1-7
vn
remains combine the above bounds.
B.3 Proof of Corollary 1
Proof. Let (xx) is the c.d.f. of the standard normal law (/ 1), (x))) is the c.d.f. of the normal
law NO, (u)) and T (x) is the c.d.f. of the normal law (/00 a, (u)). Then have
dx (Vru" (0, 0²) (/)()
sup [P(vnu" (0,, - 00)oo(u s [z)
zER
sup
IP( (i (0,, 8²) $ x) - (z))
FER
sup [PV/nu (0, 00) < x) 4o, (z)l sup P (z)
Po (x)
zER
zER
dx (VTu" (0,, - 0*) (0))/an(())))) (u)) + sup c { $.. (x)
zE
Using Lemma to bound
(o²(u) (u)) and Lemma 10 to bound o; 2u) we obtain
1 (2(())/2(()) -1/5
n 1-
Setting
30% where C² is defined in 31
C.c Amin (2xx)
(30)
and applying the Gaussian comparison inequality 68 we conclude the proof.
29

---

B.4 Technical bounds
Lemma 3. Assume A
A2
and A3
Then for any E N it holds that
11Qell - Lo
where
4 Lg - kQ (co + a(1 - 7
1/2
and Ko is defined in Proposition
Proof. Using the definition of Qe from (T0 and Proposition
we get
1/2 1Qell S Ki at
Ge+taall S
1/2 ki a6
Σ II
aaj
k-
n-1
1/2 S kg 00
(1-2))))) S La,
k=t
where in the last bound we applied Lemma
23 with b a/2.
Lemma 4. The following identity holds
n-1
Qe-A-L St A- -GGGmm-- where St
Σ 5=
(at
G1)Gi111-11
and
n-1
n-1
Σ (Q. A-1 =
G
Proof. See 82 pp. 26-30].
Lemma 5. Let co (0, acol and l E N. Then under AT A2 and A3
it holds
|| S /Fi
((9) 7.8
(e ko)²
where
C(S) 7.a
2cp exp
aco 2
27/(1-7)
2
123 1
2
a0o
a60
Proof. For simplicity define m = Ei -ko 7 and B a/2. Note that
n-2
((5 +1) -1 exp(-
(a: -a--up ay) VnQ
CD
(j + ko + 1)7
i ko
j=H
Following the proof of 82 Lemma A.7], we have
2/(1->)
+ ko + 1 1)
1 (i+ (c)+ 2-1
1 (1 7)mm
i ko
30

---

Hence, we obtain
|| VKQ
1
(1+ (1 -mmm? (1+(1-))mn)) 2/10-)
S co + ko)
expl-
(j ko + 1)7
n-
7/(1-7)
1 culi + 10)
Σ
(+ - ?mml? (1)mmm)
exp1Beo + +1 -
- Baam
+ (o)
=
30g <ceexpl
n-2 [i --1
1iammmp- - (0--)(111))) (1+(1-))))) 7)mm (1+)))
7/(1--)
Σ
(mg - m
Scomm))
kg
5=1
3co Kg
10 t.00
(1+ 7/(2->)
$ 200 exp(
(1 + 10)
expl Sepl-Scom)dm
< 200 exp(
3eo
(i + ko)
27/((1->)
1
+
)1/111-0)1
1/(1
1/(1->)T(
kg
Boo
Beo
Lemma 6. Let co (0, atoo] and l N. Then under A7
A2 and A3
holds
1Qu41 - Qell < LQ2 ac+1,
where
4 a(1 )
LQ2 VKQ 2 (2CA +a/4)(co +
Proof. Using the definition of Qe have
R-1
n-1
a-1
Qe+1 - Q==
= 006+1 Σ
Ge+2sk - 0z Σ G = 0441
G4224+11 -
Σ
G - ae
k=l+1
k=1
k=|+1
=0
G14z4 arT o1410;A)
Hence, using Lemma 27 with r = a/4 and Lemma 3 we get
11Qe+1 Qell s az
(2 Co(2CA +a/4))/44)
(2
km1+1
Lemma 7. Let co E (0, acol kb > boo and E Then under Al A2 and A3 holds
||S Sell S VFQ
7,0
0141
where
((S2) (co + a(1 1a/2 + 3CA)
4
Proof. Using Lemma 4 we obtain
Se+1 - St = Q++1 - Q - (Ge41m-1- -GEn-1)
a-1 Ge+2i 04 Σ
G + A- - -(1 Getmm)
= 0141
k=H+1
n-2
n-2
-044
G442 ap
Σ
G
k=l
n-2
= - a4)l+
Σ
(ae+1 - (x+1A) - arl! - -a++ A))-1A)
k=l+1
31

---

Hence, using Lemma 27 with r = a/4 we get
n-2
||S Sell s (a/4)a441
Σ
((a/4)02+1 + CA 0²21 2 CA 0[4422)
k=1+1
< (L/(( + CA +2" CA) + (a/4))as41,
where in the last inequality we applying lemma proof.
3 Since La 2 and 27 < we complete the
Lemma 8. Let co E az)) Then under 1 for any m E N it holds
m2
| mm--11 11
Q
(1-co(a/2)] - ko - -)
Proof. Note that
|G 11
RiQ
m
(1 (a/2)as)
1=1
i=!
m2/
n-1
R-1
KiQ
(1- (1 (a/2)at111)1" )M)
(a/2)a:,)
(1 - (1
(0/ 22/ m
m22
RQQ
(a/ (2)
Lemma 9, Let on E (0, Oroa]. Then under A7 A2 and A3 holds
(0)(2) 0² [u) S n2-1-11
where
C² = |E&l|
KQ
7,a
+ || |
22+
kg +
4CA KQ (1
1. 1
(31)
27
aco - 7)
a00
Proof. Note that
1o o 12n - Ecoll
Then, we express the En Exo in the following form:
n-1
n-1
Σn Ex
(Q: - A
+
Σ
A
- (Q. - A-1
t=2
R
カ-1
2 Exx
(Q:
-
EE - A
n t=2
n
R2
First, we bound R1, using Lemma 23 we obtain
R-1 I Σ GTy.AA
1 Σ (q-
1
1=2
n-1
< nn y
Giyll S n -2
GG11
j=2
S n -n 1 (1 +
aco(1 - 7) (1 + ko)
4
< 2n 7 1 (1 + aco 7) 16ō
32

---

Hence, we get that
4
[R || 2 n== -11=01=011]]]]
(1
aco(1 7) )k10
Now, we rewrite term R2 as follows:
Σ QQ:
[
A
AZ, - A
2
T
S
A 1
A)
Eg
S - A
- a1
k=
k=
n=1
S
+
A
A
A.
1=2
t=2
k=t
k=t
R21
R22
n-1
n=
A) E.ST
S A
Rag
H22
To bound R21l we use Lemma
and obtain
n
S.ESS snn n-1
Raill = In
|E S/
n-1
In <|Ell
Σ
niQ (c(s)
(t + ko) k 2(
(n + Ko 1)2
(Kip + 1)2
S -1Eel
(C(s)
7,0
27 2
)
||E
ki
7,a
$ n 2(7-)
27 -1
where the last inequality holds since (n + kip The bound for R22 follows from Lemma g and simple inequality (n ki- 2) (kon)
1)20 S n + (Nip + 1)22-1 for y E (1/2, 1).
n-1
n-1
Real = ||n
Gin A -
A GT - S 1n EEx
| c-m- 1|
|>x
+ (n 27 S 2 Eoo 1k 71-1
In
cna(n + hip - 2)- eg (n)(n
cya
Since Roa- RTg, concentrate
|2a|l Lemma g jimeedittely imply
|aall S nn- "1EA Σ
S Gin
1ig (S) n-1
70
I In n |
(2 + Ko) 7-1
aco
7.a
2(k + kn)
A=
I
S n |
110
(S) 7.a
(i + 27
(1 + ko)
(1
aco
2(k + ko) 7
k=++1
1
S CA || Ki (1) 7,0
x2-
aco
By combining all the inequalities, complete the proof.
33

---

Lemma 10. Lo E (0, aze and Co S Amin (Exo/2. Then under 1 A2 and A 3 it holds
on (u) S Cr.
where Cx V
2 Amin )
Proof. Note that of (u) > Amin (2n). Using Lidskii's inequality, we obtain
Amiu (En) 2 Amin (Eoo) |_n, E Amia 1/2, where in the last inequality we use C² S Amiu ( (2x)
C Last iterate bound
The main result of this section is the following bound on the p-th moment of the LSA iterate 02 - -
Proposition 8. Assume AT A2 and AB Then for any 2 S p S log n, k 2 S and any initial distribution on (Z, 2), it holds that
1/PP 1 102=- (0x- 00)1 & (M))
mixx /pek + Ord log exp { (aa112) Σ at 1100 0' (32)
where the constant (( is given by ((M) -d//2+1/ log (Cr CA D /a) [elloo (H 4 4Ca
and D (M) is defined in 37
We provide the result above only for 1-dimensional projections of the error u (f,, 8*), as previously considered in [47]. Note that the scaling of the right-hand side of (32) with a mix factor can be suboptimal. However, this scaling corresponds to the second-order (in ni) terms. Tighter analysis of this term using the Rosenthal-type inequality should reveal /imix dependence of the leading term, however, we leave this improvement for future work.
Our proof of the last iterate bound is based on the perturbation-exxaasioo framework 2 see also 24
Within this framework, expand the error recurrence (4) using the notation p(a] for the product random matrices:
I pla)
a1 (LL-aA((Z)). m,kEN, m S k
(33)
with the convention that p(o) decomposition of the LSA error:
= for m > k. Using the recurrence 4 we arrive at the following
mik
u T(O 0*) u TT( + u
0
(34)
where we have defined
g(tr)
(a) (0o 0*} 1
(0t)
Σ
r(o) p ((z))))())))
Here ((t)) is transient term (reflecting the forgetting of the initial condition) and 0(n) is fluctuation term (reflecting misadjustement noise). We treat the ((tr) and 0( terms separately. In particular, we control ((t))) using Proposition 12 For estimating j((1) we use the decomposition
u ( = u T 1 + u H1
(35)
where the latter terms are defined by the following pair of recursions
J(()) (T A) 1 - aks(Zx))
J[( 0,
H (1-axA(Zh) (1 - au A Zz) 2
H 0.
34

---

For notation convenience we introduce, for m S k, the deterministic counterpart of the product of random matrices (3). that is,
Grick
II (T a;A), 1m
keeping the convention
Gmik lif m k. Thus we obtain that
k
Σ
ag
H
Σ
AZz)
(36)
j=1
==1
and we analyze these terms above separately. We first bound the term Jn
Proposition 9. Assume 1 2 and A Let ko 2 { 1177 1/1-,,
Then, for any 2 2, initial
ang
probability measure & on 2 2), and k 2 2, it holds that
E [u" 1
[n] S D2 Emix
where
D 1
(37)
Proof.
Note that ( is an additive functional of {e(Z))] Using the representation (36) we
obtain that
J
(0) = Σ
ayu T ()z)
1=1
Applying Proposition 2 we get that
|G]--:k||| S RiQ
1/2
II
v1 a04
(=++1
Using Lemma 20 with A, = afGG+1ı we obtain that
B B1/P p
lr] < (16/3)p mix |||| a G[1GH+11113 1/2
+ (8/3)/mix ( + oz
-aalik-aj---ee - -a---aa)))lll.
1=1
Using Lemma 28 with b = a, we get
k Σ a3
LfIGH+1 2S SKQ RQ
II (1 aos) S A(Ko/a)ax
j=1
E=$+1
Applying Lemma 26 with 6 a/2, we get ai G2.kl S ax. Moreover, using Lemma 27 with r = a/4, we get that
||ay Gjtik Gj- 11 s a0ll) (2 +a/4)
Then, applying Lemma
28 with = a/2, we get
a1||G2 as +
GayG +
$ 2ah
1/2 1/2 Ri (a/ ACA)
Σ
a
2
II (1 aal/2)
j=1
1mj+1
$ au (2 (2+ 1/2 (a/4 4 2a)
Combining the above results and using that p > 2 yields
37
35

---

C.1 Proof of Proposition 8
Proceeding as (3) and 35
we obtain that
E// [u (0x 0*) I|]
E 1/P r
1ik 10o
0-31-] +
|u
p
+
EL/P
|u" H2 (0)
The first two terms bounded using Proposition 12 and Proposition 9 respectively. In order to
bound the term, corresponding to H we apply Minkowski's inequality together with Hölder's inequlity to (3):
E
Ju
H
1
S Σ
oj CA
Be
j+ 10
(a) |||
1/2p { || pr]]
1/2p
Note that
E ||| 20 1/8 = (Be
|0 p)111 1/1
1=1 Σ
(38)
[Ec[ 1 20 1/8
Using Proposition 9 and proposition 12 with simple inequality x S 1 x/2, valid for [0,1]. we get
E 1/p [ 11
(M) Cr CA D lell 1/211 //d log
3/2
II (=j+1
(1 aax 224
S // log CA (2) /a)l ppac
where in the last inequality we use Lemma 28
C.2 Proof of " bound
In order to proceed further, we need to obtain the tighter bound on (0), which requires a tighter moment bound the quality J(
Proposition 10. Assume A7 AΣ and A3
Then, for any 2 2, initial probability measure & on
(Z, 2), and ls 2 1, it holds that
E 1/p
H (0)
"
S D
(M)
tmixp an log (1/ax),
where
/2411/ log log CA
D
D
(M) (1
a
and the constant (M) is defined in 42
Proof. It is known (see e.g. and that the term H! can be further decomposed as follows:
1 (0)
(6) + H (L)
(39)
8=1
Here the parameter L 2 1 control the depth of expansion, and the terms the following recurrences:
(( and H are given by
( (I 1/ A
1 = =0,
(40)
(0) = (L--aA((Z))) (Z+)) H a (Z
H = 0.
The expansion depth L here controls the desired approximation accuracy. For our further results enough to take L 1 and estimate the respective terms e( and H Now the rest of
the proof follows from Proposition 11 (see the bounds (41h and (43 for B 1/1 []u J( ["] [[u /2/0[lu
and
(1))) respectively), and Minkoski's inequality.
36

---

Proposition 11. Assume A7 A2 and A3 (z, 2), and & 1, it holds that
Then, for any 2 2. initial probability measure & on
B [
J
11
E D4
mixp an log (1/ax),
(41)
where
D (M)
3/2 NQ
CA |Elloo
+
AQ
3/2
Ca
g2/2 + #Q 1|5
3/2 CA || 3
8%
7/(1->)
(42)
a3/2
aco
Moreover,
E 1I 0
1
S t mixx ax log (1/ax)
(43)
where
d1/241/loRDD (M)) Cr D )m)
(44)
a
Proof. Solving the recursion in 40 yields the double summation:
- Σ A
00 Σ 0GGemnAA222(GHHueeeeee
t=1
Changing the order of summation yields
1 - -a Σ
(E(2)) ) =
Σ a (3S
ビ=
where for j S l have defined
Sj.k Σ AG)
Fix constant m E m S & be determined later). Then we can rewrite SJ+1,
tmm
SJ+1kk = Σ A
( (=j-++
Σ
8=1t1
= =Gjtmthh$/415tt + +
Let N = [k/m]. In these notations, we can express
I( as a sum of three terms:
m(N-1)
m(N
Σ
S.StmtiaGGttjttmmmm (zz)
T2
k-1
Σ
ar a, (1S
j=m N
1)+1
T3
Consider the first term Ti. Applying Minkowski's inequality, Lemma and Lemma 28
we get that
(a) nQ
(m-1)) 1)N
E E/PP|ju T Ti 11
3/2 pappl
CA
1/221/22 1/2
mix
||l|
a
1/2
aae
r=j+1
E=++1
I kg
3/2 CA /mptmixllell
vI aat
Emj+1
2 C1 / Vmpptmixa
37

---

where we set
C (x22/aa) /a) CA |
In the line (a) above we used Lemma and in (b) we used Lemma 28 lemmas, we bound the term 73:
Similarly, using the same
1/p T3 S C1 /mplmix*k
Note that the second term T2 is non-zero only for N 2 2 and it can be rewritten as T2 = T21 + T22. where
N 2 m
T21 =
ajm
(Zim+t))
1=
N-2 m
T22 = Σ
aim+
E( f(i]))+))
The set of random variables Tim+s is constructed for each E [1, with (ijm+s)3=0 N-2 having the following properties:
Tjm+s is independent of 3h (j+1)m+t == ol2 Zz}:
2. Pe(Zimmt # Zim++) S 2 (1/4) [m/tuixa;
(45)
3. Mjm+s and Zjm+: have the same distribution,
The existence of the random variables 2jm+s is guaranteed by Berbee's lemma, see e.g [60
Lemma
5.1J, together with the fact that uniformly geometrically ergodic Markov chains are a special instance
of f-mixxig processes. We control 3-mixing coefficient via total variation distance, see (23 Theorem
F.3.3]. In order to analyze the term T21 we use Minkowski's and Burkholder's s inequality [52 Theorem 8.6], and obtain that:
N-
E /2/p T21 1
ajm+iu
(Zjjntt))
t=1
1=0
2
1/2
$ p
a a (otp
1=0
( (yymmauaG)HHttnm(((2))) 1/2
$ pym
Σ
Applying now Lemma 111 we arrive at the bound
(1 (1-aaaa) ) 1/2 (46)
Eg /"[" T21
T 1
3/2 ri
Ca ||e] oo /
1/2 3/2
vm
Σ oo
Σ
of) II
{=j+m+1
(=j+1
In order to bound the term T22 first note that
- {(fjm+i))11)
S R [Il [100mm/44uA44mmm((1111 (( (im++)))1* u.vE8a-1.8'
sup
Egr "oll" S 1m
Hence, using Minkowski's inequality for T22, we obtain that
m Ojm+i sup w.
E B//PlIn T22 19] < VRQ
E B//Pllu SU+Dm+H4
1a ([lm+))))))) - =(Zmm++))1)
j=0
(++)m++
x
(V1 - aga)
t=fm+it1
38

---

Using the definition of kkm++ and the Cauchy- Souchy-Schwartz inequality,
E (1l - E << I EE "1l (L km++ # Zkm++ell?
|| (1/4)m/(eppuiw))
where in (a) used (55)
The last two inequalities together with Lemma 11 imply
E 1
T2e T22l 1 S
3/2
CA
1/2 ( (2plmix)
Σ
as
a
1/2
vI
aag
j=1
E=j+1
E=j+1
(47)
Combining now 46 and (47)
obtain
E E1/P
1 1 < C₁
/mpt
mix
1/2
liQ
3/2 CA 1eElloo vm
II Emj+1
vI aça
Emj+1
ke CA (elEElooo 112
3/2
aas
Σ
at) 1/2
II
V1
adg.
(=j+1+m
E=j+1
Applying now Lemma 29 we arrive at the bound:
E
[ J PT & C1 v /mpt 1/2
muix Oik
7/(1->)
+ (m2² CA |1e1 la)lloo 1/2
mis 3/2 m3
8y
aco
(m@@
3/2 Ca ||ells/ 3/2 Winse
/2 (1 1/4) m)) (1ppmm/m
Vok
Hence, it remains to set the block size m as
2ptmix log( (og(1/az)
(1/ (4/4)m/((phmmx)) I Valks ie. m
log
With this choice m we obtain from the above inequality that
B [u p & C1 plmix / Tog(1 (1/ok)o
7/(1->)
3/2 + (m CA || /mixp2 /og(1//x
88
O
aco
3/2 CA /e/loo/a3/2 1/2
1
+ (
S Ca p² tmix log(1///g 1//x)aa
where we have defined
C3 KO CA 1|
3/2
3/2 KQ
CA 1|
3/2
Ca ||ello
8y
7/(1->)
32/2 +
3r
a/2
aco
and the bound 41 holds. To estimate
H we rewrite it as follows
H
Σ a C ( AZ))),
j=1
Using Minkowski's inequality together with Hölder's inequlity, we get
E //1l/ H (1
CA az (
[e
[[r
s+1sk 1 1/2p [EE (1 1 1/2p
1//0
39

---

Applying similar argument to (38) together with Proposition 12 and an elementary inequality e S 1 2/2, valid for a E [0, 1], we obtain the bound 411 we get
k II (1 - ace/24)
E 1
H 11 S d2/2-1/ log "Cr CA
emixP
log (1/az)
Emj+1
A:
11/2-1/log Cr CA (M mixi log (1/ak)
(1 00xe/24)
(=1+1
2 D 1 "mixp"a ork v log (1/ox)
where in (a) we have additionally used Lemma 28 and used the definition of D (M) from 444
C.3 Technical bounds related to 1
Recall that S1+1:8+m is defined, for L, E N. as
*+m
SE+1:E-= = Σ Or (aL)) with (x GR+ne+m GE
(48)
k=t+1
Lemma 11. Under the assumptions of Proposition 1 it holds for any vector E Sd-1, l,m N. and any initial distribution on (Z, 2), that
t+m Σ
8+m
E
1/ [[u" Setretme ( [Z) < Cs(
a.)
1/2
II
vI aak
r=f+1
k=(+1
where
=s= = CA p 1/2 1/2,1/221/ ||
Proof. We first prove the auxiliary inequality for deterministic vectors u, E S Indeed, using we obtain that
(48)
4+m
w SE+1i+m
Σ (x())) k=#+1
where hx(2) = agu Bx(Z)u.
is easy check that u Se41.44m satisfies the bounded differences property, since for any 2, x' E Z. and E {E+ 1,... + m). it holds that
k+m
t+
< 2nQ Ca
II
V1- aan 2 CA
II k=(+1
V1 aok.
k=(+1kkr
the last inequality we have additionally used the fact that axa S 1/2 for any h N. Applying the bounded differences inequality from [54][Coryllary 2.11], we get that for any 2 0,
2( - |1E S1+1:4tm u|)²
Pe Sjttstmu 20)= < 2 2
[ aax)
72 C 1Et+m1 a²)
+
It remains to upper bound Be(uT. S 1m)
Note that
1+m
1+m
1+m [-m-1
(Eş[u S)+1;f+mu)) Eg[( Σ (zx))))
Σ
(Z)))(Zz))11 +2
Eg [hp (h))ha
Using that x(bx) = and A we obtain
/ hn (= - ((P
[Eg (7
1+m
< 2axakt 22 (2C))
(1 - al))
t=1+1
40

---

and
1+m
Eg (Zx))
II a0r)
Combining inequalities above, we obtain
++m
++m
32 (EEll' Sy11)+mbu)& ki
C
Σ
ag
II (1 oa.)
km1+1
tm|+1
Note that for 1.2 [ Sj+1:tmm we have
t² Er=4 aZ) h+m
PE([ Sj+1i++m 2) S 2 exp
mi C
(1 aag)
And for t S [Eglu' S w.]. the right side of the inequality is greater than 1, so this inequality also true fort < [Eşlu' Sj+1:+mtm Hence, using [24
Lemma 7], we obtain that
E+m
8+m
E [ S S5+1:f+m " & 7p CA
E//P
1/2
miix
Σ
1/2
aok
(49)
r=t+1
1m++1
Now, with Fz Z _ f}, it holds that
El/1|u" Se+1.e (Ze) = E [[=(())
[ St+ee+m [1=((((]))
$ ||=|| loc
sup
E E//2 [1u" Set1:4tm=|[]
M (Z))
Combining the above bounds with 49 and A2 yields the statement.
D Proofs for stability of matrix products
D.1 Stability
We first provide result on the product of dependent random matrices, Our proof technique is based
on the approach of [33 and the results, previously obtained in [24]. Let (2,, 3, (3e JeE. PP) be filtered probability space. For the matrix
dRd we denote by (B)( its singular values. For 2 1, the Shatten q-norm is denoted by |BlBg = {E (B)) For 9. and random matrix X we write | = [
1/P The main result of this section is stated below:
Proposition 12. Assume A7 Al and A3 Then, for any S p S log n, N, and probability distribution & on (Z, 2), it holds that
E
1/r
[
(a) jin
[P]
< C/dn/logn exp (a/112)
Σ Am
0kk
where
Cr -== /Kqe²
The proof is given in Appendix D.2 It is based on simplification of the arguments in [26] together with a new result about the matrix concentration for the product of random matrices, using a proof method introduced in (33]. We first state result from (24):
Proposition (Proposition 15 (44). Let (Y,) dees be sequence of random matrices adapted to the filtration (3eTEN HEN and P be positive definite matrix. Assume that for euch & E No there exist me (0, 1] and 0e such that
| [Ye]l < 1- me and I|Y, - 3 1 "Yelllp S ae P-a.s.
Define Zn T Y, Y Zn
Then, for any 2 < p and 2 1,
12,,122,p S kp (1 m + (q - 1)o?)|| p1/2 2 P-122 1/ 4.p
where Kp Amax (P)/>min( P) and Amax (P), Amin (P) correspond to the largest and smallest eigen- values of P.
41

---

Now we fix some N E N, block size h N defined in 23 and a sequence 0 = jo < < <... < JN 2n, where jr hl, N Note that is possible that JN In-1 h. Now we
de-1
Y = II (1 (1- (.,))
Then the following lemma holds:
Lemma 12. Assume A7 A2 and A3 Then for any & E {l...., N - 1}, and any probability measure
E on (Z, 2), it holds that
| Yelllo S 1
Σ
ax)a/6
k=ft-1
Proof. We decompose the matrix product Ye as follows:
Ye = I (Eke an) S
(50)
Here S. = as (Z²) A} linear statistics in {A (Z)z [ (A(Z))
and the remainder
term Rg is defined
R = th 2- E (6im.ne)) II tai, A(Z.))
where I, = (ii,...., .,) E fl....,,." h3 is < tr}. Since || = =IQQ//2QQ is straightforward check that IP-a.s. holds
|Relle S
EE anl'ng C
exp
liQ
1/2 CA Lk=je ax) =: =:
Sir1
(51)
On the other hand, using AD and Al we have for any ls E N, that [[E]|A(Z))
A]l
sup
Eglu A(Za)u) u Ao) S C(P(
Hence, with the triangle inequality we obtain that
je-1
E& (Sell I
1/2 liQ
Σ
ag
(Zc]A(Z)) - All S skq 1/2 CA Σ A(*)
k=je-1
k=
$ (4/3) mixk 1/2
CA Ti
Q
This result combined with 51 in 50) implies that
E Yelllo <
Σ
ajAllo + + +Tz.
k=ft-1
First, by definition 23 of h (see details in Lemma
13
we have
Ti <
ax)a/6.
(52)
k=je-1
Second, with the definition of cp in 24
we obtain that
je-l
je-1
Tr S (RQ
1/2 CA
Σ
Σ az)a/6.
(53)
k=jt-1
k=jt-1
Finally, Proposition implies that, for 54-1 on S (1oo, it holds that
|| - (E 50-
k an Alle < - (1((a/2) Eie O0k
(54)
Combining 522
53 and (54) yield that
Jc-
| (Ellll $1 Σ
ax)a
b=tt-1
and the statement follows.
42

---

Lemma 13. Assume A3 Then, for the block size h defined in holds that
23
and any E f1..... 2n -h}, it
8+h
6+h
i+h a/6,
Σ ag S aco k=t
RiQ
1/2
CA
Σ ak s1.
ka C
Σ k=t
ak
k=t
f+h
(4/3)arllmixti
1/2 CA S
ax) at)a//6
(55)
k=!
8+h
(log n) C
Σ
okk S
a
(56)
12
kmF.
Proof. First three inequalities above are easy to check, since
8-h
+h dr
cui(1 + h h 1 ko) 1-7 kg m
O
(k+
ko)²
S co
x7
1-7
k= k=
cuko 7(1 +
-11
h+1
Kg
co (h + +1)
7
hence, in order to satisfy these inequalities, it is enough to choose h in such manner that
h 2 ch + 1) max(( QQ
1/2 CA. Gero C /a),
which is guaranteed by our choice of cp in AB and 23 Now note that
+ dæ
col(e+ ko + h + +)
(E + ko)
C&k
Co
E+
x7
1-7
hence, in order check (55),
we need ensure that
4cutmixki 1/2 CA
coal(e + ko + h + - ko)
3(e + 77)
6(1 77)
Equivalently, it is enough to set such a way, that
Ci (f+ ko)
(e ko + + + -(e+ (e+
where we set C 8(1 miix 1/2 Ca /a. Hence,
55
will be satisfied if
C1 1/(1->)
h > (e + ko)
1 e ko
-( Ko + 1).
Note that, with > 1, it holds that (1 + a < 1 + 200 for 0 < x S 1/a. Hence, provided that
kn C1/(1 - 7), or, equivalently,
St 1/2 CA
Ko
it is enough set
201 h 2 (1) (e + ko) (1)
16/mix CA -1.
(E Ri + +)
a
Now it remains check (56 that is,
8th
(logn)
Co
17 12
43

---

Since
E+
A+1
h+ dx
(h Ko + +1)
2-
k=
kk
ko)
(k + ko)
kp
x²
1 1-
it is enough to choose ko such a way that
(h + ko + 1)1 -koo)
(logn) C co
a
1 1-7
12
or, equivalently,
(ko) (60)²~((11 + h - 1)
a(1 - 7)
(57)
ko
12 n) C2 Co
Since (1 51+ 7)0 ) for x 2 -1, 57)
holds if
a(1
2 (1-7)(h 1) v
12(log n) C
or, equivalently,
12(h 1)og n) C² 1/7
kg 2
a
which is guaranteed by the condition 25
Lemma 14. Assume A7 A2 and
Then, for any probability & on (Z, 2), and any fl....,
1}. we have
fe-1
Y Ee (Y]lle C.
Σ
as)
where C. 2(x 1/2 CA +a/6),
(58)
k=je-1
and h is given in 23
Proof. Using the dccomposition 50 we obtain
Y Eş Yelll - E Ek=je, ax - -E([A + |R. Ee|Re]lQq
Applying the definition of R₃ in 51), the definition of (M)) and Tr in (3 we get from the above inequalities that
Y E. & 1/2 CA CA an) + (a/3) Σ EE -kji--1 ax)
and the statement follows.
We have now all ingredients required to prove Proposition 12
D.2 Proof of Propasition 12
Denote by E N block length, the value of which is determined later. Define the sequence jo j. de+1 = min(je + h, n). By construction jet1 - je S h. Let N = [[n j)/h]. Now we introduce the decomposition
N Ye, 1=1
P (I (1- ée {1, (N 1} [ aI)A(())) N=N.
(a) jim
where Y
(59)
The last block, Yv. can be of smaller size than Now we apply the bound
N Σ
|Y < II (1 aa CA) & exp
k=jN-1
k=jN-1
44

---

where the last bound follows from the relation 24 Hence, substituting into (59 bound:
we get the following
[P] I c
I Yell").
N-1
jmm
[=1 Y ||) using the results from Proposition 13 To do so, we define, for l E {l,.... N - 1}. the filtration Hr a (Zx S je) and establish almost sure bounds on I He-1 [Ye] llq and ||Y; - [Ye] llQ for & E {l..... N - 1}. More precisely, by the Markov property, it is sufficient to show that there exist m E (0, 1] and >> 0 such that for any probabilities E on 22,
Now we bound E 1 N
g Y ell S 51-me me and Y Bg: Yellle oe, Pç-a...
(60)
Such bounds require the blocking procedure, since (60) not necessarily holds with h = 1. Setting as in equation (23 and applying Lemma 12 and Lemma 14 we show that (60) hold with
je-
je
m
ox)a/6,
oe oe= Co
Σ
xx)
Se
kmje 1
where C₂ is given in
(88 Then, applying Proposition 13 with q log n. we get
E
| [Irfir
|p]
- E
1/9
|| 1
[s]
N-1
S Vkod//
e
II
as)a/66 + (logn) C2
Σ an)
E=1
k=je-1
k=jí-1
N-1
/kQdd e
exp
a C.¹
Σ ax)
2
kmse
km
(0)
12 <
2/4
1/
k=j
Here in (a) we used the fact that
ji-1 (log n) C2(
Σ
ok) S a
12
k=jt-1
which holds due to AB
D.3 Proof of Proposition]
2
First part of the statement (existence of Q) follows from note that for any non-zero vector E Rd we have
67
Proposition
1]. For the second part, we
(I AA TQ(I AAJr a
TATQ+ + QA)z
2222 T A AQQA
x Qx
x TQQ
x Qx
r Pr
x TATQA
a
x Qx
xTQu
$ Amin (P)
a² ||Al|a
||Q]|
aa
where we set
Amin (P)
a 2 |Q]
and used the fact that S acs. where a is defined in
45

---

E Proofs of Section 4
E.1 Proof of Proposition
For completeness, recall the setting considered in the main text. Even though the sequence {Z hEN forms Markov chain, the iterates {6x JeE do not form the Markov chain. As a conse- quence, the standard consistency results for overlapping batch means variance estimators cannot be applied directly to (T8). In this appendix, we provide the detailed derivations underlying the statement that applying the block bootstrap to the sequence {0z] is asymptotically equivalent, up to a suitable correction, to applying the same procedure to the latent variables {e (=(Z)))
Note that for any t S bas unroll the LSA recursion only up to 0, A,, rather than all the way to the initial iterate Oo 0,:
0kth 0- (1+1 0*)
Σ og oeT441240(77) E=1
(61)
While one could also unroll the recursion fully to 0o - O., leading to an alternative representation suitable for the multiplier subsample bootstrap and yielding the same convergence rate, we adopt the form in ( as it simplifies subsequent analysis and notation.
Using (61). similarly to 1 { and get
we extract from the MSB estimate linear statistic that depends
Vbn
1- bn
(n,b,(u) Vn bn +
W/ WrOOb,,t 0n) 0n)Tu Tu
(62)
Vbn
12 bn
Vbn
n n- bp
wc WWo... -Wn) WW)Tuu uu- u
We WDbD...t - Dn)) u
Vn On +
vn bn
1=0
where we have set
6
n-1 Qx=(Zx),
Won.t
Wn
bn k=1
b
Donett
Te+reta00 -0* +
k.t.b, E {Zzttz)
bn k=11
k=1
D Σ
(10 0++ H e(Zr),
(0)
n
and Qk.e.b.. (0) defined as follows
J are analogues of Qs, H (0) (0) for the bootstrap procedure and are
k.t.br
Que..h = akitt
Ge44+184t
ktt
(0)
Σ
A (Ze))
k.L.b
fat+1
ket
Σ
aeGe41e4HE(Zi).
t=++1
Since existing results on the concentration of overlapping batch means variance estimators for Markov chains do not consider weighted sums, replace the leading terms W and W with expressions
46

---

involving the constant matrix A 11 and obtain
bR
hn
Bn (2) = vn
W/ We(Obmn,t - -0,) u
bn
0=0
/b
v bn
n n-hn
We (Wb... Wn)Ju u+
Wi (Donit Da) u.
vn
bn
+
vn
bn
t=0
where we have set
1 Bg
1 n-1
Won.t
A 1-1e ((Zxt))
W - Σ
A 1--- (Zz),
On
11 k=1
ba ba-1
by -1
b.-1
Don
T 24110+4(0g) -8*) +
H
1
Σ
(Qkit - A A)
bn
bn
ktt,bn
bn k=1
k=1
k=1
+ 1 (0)
1 Σ
D,
(00 0*)
1Q--A - A (2(2))
k=
Then can decompose the variance w.r.t db of 6,,b, (u) and extract the variance of block bootstrap procedure applied to the non-observable random variables {e()))
bn (10b... 0n) Tn)T=) u)²
bn
(u)
= n bn
+
1=0
bb-b
bn
((Wo..t bm.tt Wn) (2)
n1 bp
1=U
(2(x)
where we define the remainder term as follows
Rvar(u) D2 + D2 on
bn
D
(Don.t - -Dn) u)²
n b +
(63)
2bn
D2 bn
(W Wx)(D Dm)
1=
To bound Rear(u (u) it remains to bound E [1PP) and E [1DDD...). Hence, from Lemma 18 and
Lemma 19 we obtain the following bound for the residual term (w)
E
(w) - pb// / 1/22-1 + plog n)6b//n
(64)
+ pb, 1/2 p (logn)n + pm 27-2
The version of this results with constants, you can see in (65). Below we present some technical lemmas that are necessary in order to bound the residual term (w).
E.2 Technical bounds
Bounds for Dr... and D.. First, we establish bounds for Do... and D... The argument follows the same reasoning as in the proof of the bound for D2 in (27). The main difference lies in the appearance of additional terms arising from the modification of the linear component in the decomposition 62)
Lemma 15. Assume A7 A2 and AB
Then it holds
D.b pl2
D.b
Σ bn+t-1 k=1++
E. 1l :
C
C... 2 Vlog(1 1000110.,,t +1-1)
bn bav
bn
bn
+ D.b 1/2 by
CD.b p 1/2bmn
(kin + 11-11 -17-1
(ht + ko + 2)21-221122
+ 1,0
bn
014b,
b
2=
47

---

where
C.. Crd//lognt//20 (M
miix
a(1 -7)
Kg
CD.
CR.P/ ht////onn+////// - 00 + (mixllelll + / 'I + (8/a))
aco(1 -7)
CD.b
(M) D2 Imix truix fmixx|elloo /aeeeelloo/// C
tmix
47,4 = tmixx/e || 1
CD. || 1 tm Ell /RQ
a
D.b = tmix/|= C 7
1,6
Proof.
We split Do into three parts:
Ti
u I (14 -0),
bn
k=
b
T2
1
H,t.b..
(0)
bn
b
T3
(Qk.1. A (=))e(Z(te)
k=1
We start from Ti. Using Minkowski's and Hölder's inequality, we obtain
Bl/p| TiP [TP) S
(E [[] (((m) (E 1/2 [[[(] 0²) (27)) ((2))
Applying similar arguments as in 38 together with Proposition 12 and Proposition we get
E E//11u TiP1
Crd log 1-/2+1/2
exp
-aa/12)
ay
D
M)
mix
(=++1
b+k
+ bn
c.d log 1/2
exp ((a/12) Σ
at y 100 - 1001-011
Using Lemma 24 Lemma
31
and that kin -
24 acp
we get
E B./P[
T:Pl
S
Crd Cogg//ogt Imix D
bn /a,a(1 7)
aca kg expl
24(1-7)²
CRd2/log log n 1/2 100 0
bl (1-
For T2 we use Proposition 10 and Minkowski's inequality and get
6
(M))
mmixp"
b +1-1
E//1[T//]]
<
b
E
[|]
k.e.b.
[P]] < bn
Ok I log (1/ax)
k=1+
b k=1++
D
M)
tmixp² log(1/ (1/b +8-1)
Oak
bn
We first use Lemma 4 to show that
1 b--1
T3 u S (Zete) +
Σ u -GGttstttt-1(ZZee)) = T9i + Txz
bn 8=1
P=1
48

---

where St,.b.. = Ejneth (ak+e az+t G1441:46-- It is easy to see that T3ı is weighed linear statistics of MC. We apply Markov property together with Lemma 20 and obtain
1
bn 1n
||/3 P]] x
1 113/1/2
bn
/mix||s|loo
b h
+
(1SS ll + ||Sb 1,t,ba +
|| Sk+1.t.. -kk,tbbll))
bn
Applying Lemma
and Lemma
we get
1mixP /2
::ll00 /NO ((s)) (S)
b -1
B1/P P3/P|IT3/1 [2]3
(k + ko 1)30-2/1/22
on
k=2
mix 1E
(VEQQ ((ko + + 1)>-1 + (b, + ko + 1)7-1)
bn
b
+ v
(S.2) liQ
a14141)
For term T32 also apply Lemma 20 and get
||-
"mixpp
E TT 11
bn
mix
|Elloo [|AA-1[[[[]44aa, +1-1l| +0 +t-1l)
b 2
+
A - +G1+14 Gk+
on
Using Lemma
8 Lemma 26 and Lemma 28 with b = =a/2 we get
'11
miixp /2 || RQ
E
/P (
(bn + ho 2)7/22
Vacobn
mix |Elloo
b
by +
(IIA -1 11 +1- + VkQ(1 - (a/2)ao,+t-1)) + vhQ
(1 - (a)2).)..))
ak+t
On
k=
i=k+1+1
A
I/miip 1/2 /////eloc
Vaba v +t,
tmix
|slloe /kQ
(IA -1 + (8/a))
On
Lemma 16. Assume A7 A2 and A3
Then it holds
C..bb
E
/Plu|u
D
S
+
p2
2,2
D.b
D.b
2,3 1/2 n22 3/2
+ C
p 1/2 1/2
D.b p²
Vlog nn ?
2,4
49

---

where
22 = Crdd/logn ki
aco(1 - 7) 1000 - 10 + fmix ( + 1/a) + VROC
D g/ mix
log Ag
/ /lelsl//el//ooee C/,00// c0
DD
2.2
co(1 7)
7
mmxx |1
0 (1) 7:a
Ri
C2
227 |A
/mix/|e/lax /rak 1/22
C.
/000
(M)
CD.
3 mmix
C
1-y
Proof.
Using
(28) and 29
we get
Eg
11
T 1s (00
1 8*)
12
H
00) |P] 2 Crd
kg
1100 0-1
n
n
n
D (M)
mmxxpp co
Kg
+
/logn
log
)n >
?
Co
For simplicity we define
n-1
T4 =
Σ
(Qr A- )((()))
t=1
We first use Lemma 4 to show that
n- Σ T A
T4 E=1
u
See(Z)
G =T41 + T42
n
It is easy to see that Tan is weighed linear statistics of MC. We apply Lemma 20
E E//TI[P
4mixp' |/
8o
S 1
7
Imxx |Ellac
n 2
(1|S: + 1|
+
Σ
||
k=1
Applying Lemma 5 and Lemma 7 get
El/P|/Ta| 19] $
1mixp 1/ 2/1ee1l Ae
/iQ 7.a 7-3222
(S)
V27
(8,2)
+ fmix/|/lla
((Ko (1ho + 1)> + (n + Ko - 1) +
VnQ
7,a 3.a
co
1-7
7.0
?
mixxp
/2
00 /riq C,aa (S)
n 3/2 + loo 7,0 k3 --
22
RQ RQ
mixx
T.a | loc
Co
1-7
For term T42 also apply Lemma
20
and get
| |mip /2
|| 12)1/22
n
2
/ || loo (IIA [||A- [I[ + 11 + Σ
n-2
| -'--((0 'G - Gknn1)l]
Rm
50

---

Using Lemma 8 Lemma
26 and Lemma 28
with b = =a/2 we get
A
t /
ES
(n + ko - 2)7/2
v Vacon
/ ||
mixx
(IIA (An- + VFO( - (a/2)an-1)) + VFQ(8/a))
11
A f /2 /311=1100 Fi@ko 1 12/12-1
Vaco
|0 (bo[ viq)
Bounds for W..,, and W., Note that the terms Wha, and Wn are linear statistics of Markov chain. Their moments can therefore be bounded directly using our Rosenthal-type inequality (see Lemma 20).
Lemma 17. Assume A
2 and A3
Then in holds
C.Db
Eg l Wnl
12n 1/2
n
and
C322
E
2 3,1 p
1/2
bn
where
C mix A 11
cDb tmix A -1
Proof. Using Lemma 20
we get
/2
-1
1111llloo
mix || IIl
E I WWlTTWWi'
1/
W
S
Vn
The boundary for W is obtained similarly.
Bounds for D and D In this section, the previously obtained bounds for Wo.. Donnes W,, and D, are combined to establish corresponding bounds for D and D2 in (u). Lemma 18. Assume A7 A2 and A3 Then it holds
m 1/1/1 [PPP) S M b- + Mi.2b + M1 (log (logn)n -1 + M 21-4
+ M2, 22 b, (log n + M2 M2,spb,n 27-3 Ma
where
+ (P)))
M1,
<o(7 +1)
M1, = (CP.)) + (C
ky
M1.3 (CD.)) + log
Co 27
227
M1.4 = (CD.)
27 -1
M2,1 (CD,))
M2 = (CD.)) + (CD.b))
M = (CD.b)2
M2,4 (OD.b)2
51

---

Proof. Note that using Minkowski's inequality and Hölder's inequality, we have
E
bn
n
n-bo
E
Don.. 12 + E / Dol
12
bn
+
2=0
+ 2
In Donnel (PEE/(20)) 11u T Dol2rr)
2b
B2/P11 D + / D21
E
bn
2=
Using Lemma and Lemma 24 we obtain
n-
(CL,1)
(CT:2)
2bn
b
B
2p
n bn
+
11
bn
+
bg.0t
ax)²
+ (C),)))p' (olg))/
R=llt
12
+ (CP.)) P
Bn -1
(k + ko + +1)2:-2+
D.b.y
+ (CD,b) (Ko + +
Otth,
2 M1,1 + 2 + M1,33" lognn + Mp, 21-2
Using Lemma
16
we get
26n
n-b. b..
E
12/Pllu I|u Dolar z M2n1an + M2,22 bn (logn)n 2" + M2 2:-3 + n2
bn +
1=0
Lemma 19. Assume A7 A2 and A3 Then it holds
E ///1IDP'11 x Ma.1P 1/2///2 + Mb /2 --2
3/2 + Ma.spb) /2 2/2-1 + Ma,a 5/2 Vlog nn 1/22
+ M3.sp 1/ 1/2 M3.63 5/2 Vog /2 ~ x M3,7pb, 1/2nn - 1/2 Ma 1/2
where
M3 C2,( C..
M3.2 = 2,3 C
M3.3 = C2 +
M3.4 (C2,) +C.2) CD.b) CD,b)
M3.5 (c + +1,6 3,1 + 3,2
1 log
M3.6 = 1 (VF +
0
(C + C
CD.b (2ka) 1+1/2
Ms.7 /2a T(7 + 1/2) (Co.) Co.b)
(26)) + CD.b)
M3.8
(C + c0.b)
[0ol//2+1]
Proof. Note that using Minkowski's inequality together with Hölder's incquality we get
n n-b by
E 1'/"IDD'11
S
b,
E p/p())
T.., [ / (Pp) [|u Do.. [2] + Ey (22) T (PP)
bn
1=0
+ bn
E 1/(2p)
| T W.
[B Dr,,, [2]] E 1//122)) u|u D, (2)
t=
52

---

Note that bound on [2/(2p)
[|
ThTTWW W [l.). E B2/(2P) [ W [p) 1221 [Iu D does not depend
upon i, hence, we can rewrite formula above as follows
E
D
bn
2/ (2/12) [| T Don. (EE 121(22) Wo.. (0 + E 121(22))
[| wn((.r)
bn
1=0
+ by E (2p) [| T Dn 2 ( (22 [|u Won.e! [1 E
/2/1200 [Iu Wn (*1)
Applying Lemma 15 and Lemma 24 we get
D.b p1/2
CD, bn
on
E 1/(2))
[1(u'
$2 n bn +
bn
n1 bn
bn o0t
0=0
x=
bntt11 1++
C2, p² //og(1 (og(L//anntii +1-1)
+
bn
p2/2
CD.b p//2bm/
D.b (ko + 1- 1-17-1
C
(k ko 2/20-
vatbb--2
bn
Using Lemma 16 and Lemma 17
we get
Ex 1/ 1 x
2,1 nn + C22, p bnn 3-22 +C2 p
D.b
CD.b
1/2
bn 7/2-11
CDDb C,,22 +
kg
+ (C2, + C2 Vlo
lognn nn b, bm
p²
+
log
log nbn,
CD
(2kg) ) +12 +
(2ko) / (C + C.,1 ppppppp /2 bn + 1)7/2
1/2
/2y 167 + 1/2)
voul7/2
/2 1/2 b, 1/2) 3,1 3,2
C DD.b
Version of (64) with constants. Finally, from Lemma 18 and Lemma 19 we obtain the following bound for the residual term Rear(u);
W [[ (w) S Mipbb/22n/22 +
(65)
+ 1/22 + Map Map (logn)n" + 2s
where
Mj M3,1 + M3 + M3.3 + M2,3 + M2,1
M2 M3.4 + M3. M2
M3 = M3.5 + M3.7 + M3.8 + M1, + M1
(66)
M4 M13 + M21
M; MLA
53

---

E.3
Proof of Corollary 2
The proof of Corollary that
2 follows directly from From Proposition 3 and Proposition Indeed, note
El/p1 [[/2118(2)) o2(u))(1 = Eg 110 - -2 ESg ///
Rear (u) !
mi |1 + p vbn 1=122
prmixllels
Vn
vn
VOn
+ Mipbl 11/2///200/2-111 + M2og 1)6l//21
Mapb, 1/2 / Map' (Mog(loogi n n)n 11
Mspn
1/22
+ pt (mixllello + M2) n212
(Cni 1l + M2 (log n)
vn
von
+ (t + M4) (log n))
+ + M
Hence, applying Lemma
with
= log n we obtain that with probability 1 1 it holds
1/2
(6ğ(u) (2()] s (l + M2 Mi) n)
vn
n2/2
+ (log n) ") (1 + Ma)
Vbn
(67)
(log (logn) n)
+ (f Isc + Ma)
vn.
+ (log n)* M
By setting bn bb, we can optimize the inequality above by y and B. And by putting 3 = 3/4 and 7 =122+ + where e < 1/ log we finally get that with probability - holds
(0)(u) - o2]
11 + M2 M1 +
1 + M3 le M1 + 11/84e//
E.4 Detailed version of the proof of Theorem 2
We preface the proof with Gaussian comparison inequality due to 21 Theorem 1.3). It states that for & (0, (0, 1,2,
sup [P(EI < x) - P(62 < x) < (3/2)lo7/o3 zER
1/.
(68)
Now we proceed with the proof of Theorem //miin (Exo) we get that with probability I/n it holds
Using 67
together with the inequality o -2((u) S
61/2
(bb(u) - -
(nillllll + M2 + M1 (1)glogn n))
Vn
n7/2
e
(logn)*( (t + M3)
Amin (Eoo)
Vbn
(log n)
( 1l Ma)
Amiu (Eoo)
Vn
llogn** (oggn) 2
Amin (Eoo)
54

---

Now we apply (68) and obtain that with probability 1 - 1/n it holds
6//2
dx (N0.68()).
1
( (f + M2 + (log n)
Amin (2ic0)
Vn
n2/2
(logn)* ( + Ms)
Amiu (Eoo)
Vbn
1
( 1 + Ma) (logn))
Amin (Eoo
vn
Amin (2o0) (log (logn)* 3 M
Combining this inequality with Corollary
we obtain with probability 1/n2
log n n 1/4
sup |P(VT((,, - -0") a x) (0n,6. S x)1 S (CK,1 + CK,2+ + CP 0' + CP)
zER
(log 15/2
+ (C² + Cgg)
n 11/2
5 6//2
(mmixll:123 + M2 + Mi) n)
+ Amin (Exo)
Vn
no/
+
(log (f 11113 + Mz)
Amin (Doo)
Vbn
(logn)s Vn
+ Xmiin (Eso)
( (1 + Ma)
(log n) 2
Amin (Eno)
To complete the proof, it remains to optimize the bound above. Setting bn = =[n4/0] and 7 = =3/5, we obtain with probability 1 - 1/n
log n
sup [P(v - TT)TTTT S x) - pb pb (u) S 2x)) S (Ck,1 + CK22 + cP 1100 - 0*1 + C/2 ZER
1//4
1
( (Catxllel 1111 + M1) (logn)
Amin (Erge)
Vn
13 1 111133 + Mi + M2 + M3 + Ms
CP
C2
+
(log ) -1/10
Amin (Exc)
F Probability inequalities
Denote by & the c.d.f. of a standard Gaussian random variable and set dx dx(x) = sup [P I x) 4(x))-
æER
Proposition 14. For any random variables X, Y, and any p Z 1,
dx dx + S dx (X) // 1) P|
(69)
Proof. Let t 2 0. By Markov's incquality
P(X Y <z) +Y Y + x., |Y| E|
< P(X < t + + Φ(x + t) 3 1
+ 1
5 (xx) + /Pp < x) - +xx) +
-2
18
55

---

Choosing t = [|/)+ we obtain
sup + v 2) (xx)) sup zER
P(X I 2) ((x)) + 2E / [
=ER
Similarly, we may estimate SuPrER - PP 2)). Hence, (69 holds.
Remark 2. The result similar to Proposition 14 was previously obtained in 44 Lemma 1J. It states
that for random variables X and Y and any p z holds that
dx (x +Y) < 2d (x) + || X
1(2p11))
F.1 Rosenthal and Burkholder inequalities
We begin this section with a version of Rosenthal inequality (see the original paper [61] and the Pinelis version of the Rosenthal incquality [56]). Let ER be bounded function with ll < co and define
n-1
= - -x()))
k=0
Then the following bound holds:
Lemma 20. Assume Al Then for any 2 and f - Rd with II < co, any initial distribution & on 2), and any u E Sa-1, E Baxd, it holds that
E u Ax(x(Z)) - s (16/3) mix? 1/2 11. E
11
A=1
k=2
+ (8/3)tmix (11A1ll + || ll +
Σ
|| - Aflll
Proof. Under the Poisson equation
g(z) Pg(2) = f(2) x(f)
has a unique solution for any bounded f, which given by the formula
g(2) Σ -(=)
Thus, using A we obtain that g(z) also bounded with
+oc - x (\11 < bl
||(())] < Σ [())
S 1//4)///mmm
Lk/mmrl
(70)
k=u
k=0
Hence, we can represent
n
T Ac(((Z))
As (g(x())) P9(Zx-1))
Ti
n
(A411-A: Ao) TT Aig(Zi) TT A,
The term T3 can be controlled using Minkowski's inequality:
EL/P|TTT P < (8/ (1AAll
||A +
Σ A Axl))lffloo
56

---

Now we proceed with Ti Since E* [g(2x)
Pg( x-1) = 0 a.s. and |u' (o(x
Pg(Zx-1))l s (16/3)|| Aal fi fl we get, using the Azuma Hooffdinn inequality 78
Corollary
3.9], that
26
PellT 2 t] - 2 exp
(16/3)2 mix
MM
Lk=
AA
Hence, applying 24
Lemma 7], we get
E " & (16/3)p*/2 2/2 mix ll
||
1///1/2.
2=2
The lemma below a simple technical statement used to switch between p-th moment bounds and High-probabilig bounds.
Lemma 21. Fix 8 e (0, 1/e²) and let Y be a positive random variable, such that
EV/MY> S P'C1
for any 2 p log (1/8) Then it holds with probability at least 1 5, that
Y S eee (log (1/8))*.
Proof. Applying Markov's inequality, for any / we get that
P(Y 1) E[y (Cip")
Now we set p = log (1/6), = eC (log (1/8))", and aim to check that
(Ci (log (1 (1 (cC1 (log (1/8))* Jlog (1/4) 66
Taking logarithms from both sides, the latter inequality is equivalent to
log (1/8) < log 5,
which turns into exact equality.
G Auxiliary results on the sequences of step sizes {ak]KeN under A3
In this section we provide the auxiliary results on the sequences of step sizes {ax JEEN under For simplicity, we denote
m n
Onom
Σ
k
S m
k=n
Lemma 22. Let n S m. Then
(m + 1)1-7 1-
m ml1- 10-11-1
S In.m v
1-
1 1-7
Lemma 23. Let 6, on > 0 and or = coll + Ko) for E (1/2, 1), ko 2 O. Assume that bep < 1
and kg-7 2 2/cco)). Then
n-1
Σ ai II (1 bor,) Lb
jm8++
where we set
2
C, = Co +
b(1 7)
57

---

Proof. Note that
ben (k--7- - (1+ ko))
(1- II- bay) S Σ exp
-b
jjj
exp
2(1 7)
j=(11
k=
j=!+1
f= k=
Applying Lemma
with
kj-> 2 2bcoc, we finish the proof.
Lemma 24. Assume A Then the following bounds holds:
1.
((k: + ko)
1-7 -h
1=1
2. for any p 2 2
k
c
Σ
Φ <
pr
-
1=1
3. for any m E ko
Σ
a4
2
80
((k +
( h0) - (m + 17),
2(1 - 7)
i=
Proof. To proof] note that
k ko dr
Σ
04
S
cu
((k: ko) - - -k0 k)
7
1=1
To proof note that
+00 dx
c
of
S
<
xP'
py
To proof note that for any & 2 we have 2(i ku) -1 (i + ko 1)- Hence,
3
k
k-1
Co
k
dr
co
((k kn) (m + ko) Ao)2-33
03
2
2(1 - 7) x²
i=++11
i=
m+
Lemma 25 (Lemma 24 01 S 1/b. Then
26 ). Let and {ax}k20 be a non-increasing sequence such that
1
Σ aj II
(1- anb)
[[
a1b)
j=1
(=++1
1=1
Proof. The proof is given in 26
Lemma 26. Let b 0 and ag ko 2 { 2bc, }1/(1->) Then it holds
be a non-increasing sequence such that co 1/b and kkT
(1 axb) S a.
[=++1
Proof. Note that
II
(1 oxb) as II
C1-1 (1 ayb)
0j
a1
1=j+1
1=j+1
58

---

It remains to note that,
dl-1 (1-arb) - {
ko + 1 }"
bco
7
beo
S 1+
(ko - S 1-(b/2)aar1
00
kn +
(ki + 1-1-11
No +6+1-1
where the last inequality holds since kip 2
2x 32/(1-1),
hrg
Lemma 27. Let 6 > O, and let an = =co/(k + ko) E (0; 1), such that co S 1/b and ko 2
2z ja/1-7 with some constant > 0. Then il holds that reg
Ok ak+1
< 1 + rak+1
Proof. Note that
O
1
27
S1
rCo
01++1
k Ri
1 +1 kn
(ko
+ 1)?
where the last inequality holds since kip 2 rco
11/1-y,
Lemma 28. Let b > O, and let og co/(k + ko) E 1); such that cob S 1/2 and ko 2
By 11/1-7, Then for any E (1:3), it holds that bog
k II (=1+1
4 9-1
Σ
a1bb))
azb) S
b
Proof. Using Lemma
27 obtain that
9-1
Σ
II
(1 azb) a
a--1
aj
at-1
(1 -abb
Of
j=1
8=j+1
1=1
{=j+1
ak
8-1
jj
(1 (1a)))) (1 axb)
8=j+1
We r
6 2(4-1)-
If (1,2) then Berouuli's inequality and obtain
II (1 beb) s ax
II (1+ baxe2) bra
ajj
j=1
Emj+1
j=1
Emj+1
(0) g-1
$ 1
II (1 - boe
< a
bb"
Emj+1
where in (a) we used Lemma 25
l E [2, 3). using that - laabb S (1 - bb((g - 1)0z) 9-1
we obtain
k
b
9-1
b
9-1
II
(1 bxb) s at
a
2(q 1) at
at
q
Emj+1
j=l
Emj+1
b
9-1
o/t
1
0
1
1) OF
2(q -
(=j+1
b
2(g 1)
a
q-1
1
ag
g-l
2(q 1)
b
-=
i=j+1
and the statement follows.
We conclude with a technical statement the coefficients {ayhEN under A3
59

---

Lemma 29. Let b > O, and ler at = cu/fe+ ho) E (1/2: 1), such that cu S 1/b. Then, for any kn satisfying
kb k
2
logí
6(27 - 1)27 + + logg/oo))
co
(71)
cgb
any s E (1:2), q E (0; 1]. and l E N, it holds that
k
Eaj(>
Σ at)
II (1 - aeb) S C(s,g, b)ak st4-1 1b2
(72)
j=1
E=j+1
{=j+1
27(0-1)/(1-9)
where C(s, q, b) 12 32-30(++0-1)
1(0-1)}
bop
Proof. We denote t
[(k + k2] and split the sum in 72 into two parts:
k
(
Σ
Co
Σ
CD (1
(1
CD
b)
(j
+ ko)7
ko)7
+ ko)
j=1
Emj+1
ko
ko
2
k+
Σ
Co
co
CD b)
8z
j=1+/0
1=j+1
E=j+1
cD
Cn
II
Co
t=j+1
Ti
ko
k+
q
k ko
Co b)
1
E=j+1
T2
For the term T2 we notice that jt S an for j E (1+ I,.... x + ko). hence, we can upper bound T3 as follows:
k+
T2 < 27(++24)
Σ
2 + ko - j] -])9expl expl -b(k + ko j)auk)
ax
j=t+1
/00 x² expl bb
< 27(*+20)+1
+42 a
{ too up expe -ujdu
< 27(++2))+1
/b1 2 ok
S 22(
1 0
+ 1b
where we have used that I(q 1) < 1 for g E (0, 1). Now it remains to provide an upper bound for T,. Since kn satisfies 7II we get that, for j < t,
k+ Kyg
b)
50 6)
(73)
bl
87
E+11
{=j+1
Then, applying 73 we get that
T
II
(1
(0)
s (4/6011) ( [(ss 1)7
(1(s-1)) 27 27(=-1)/(1-))
co
9+s-1
boo
j=1
E=j+1
1((s 1)?
27 (7(s-1)((17))
S (4/6--9)
37
( 1)
bcu
60

---

where in (a) we have additionally used Lemma 30 and in (b) we used the relation (33,, that is, it is enough to obtain an upper bound
S 37 It remains to check
ko
k+
co b)
C0
(74)
Er
bt
2=
t=++1
Since
kg
k- dx
c
2
x22
27
Hence, 74
will follow from
2
(k + ko - t)aub
C0
exp
2
q
17b
which is guaranteed by relations (11..
Lemma 30. Let b > and let ag = co/(k) 7 E (1/2; such that cob S 1/2. Then for any q E [1;2], it holds that
Σ aj II (1) S Cc 9-1
j=1
E=j+1
2719
(1(1-1)/(199)
where C. $
1(g-1)7 bou
Proof. Note that
k
9-1
(1-aab)
-
a
q-1
0jj
08-1
(1
azb)
at
1=1
{=7+1
j=1
t=1+1
1
k
1(8-1)
I 0
1+
- a1
E-1
j=l
(=j+1
k
7/9 - 1)
bco 8r
}}
S 0
aj exp
l
j=1
(=j+1
Define to [[4(g- 137 1/(1-1 ?)
2 2, then for any > to we have 21g-1)
bcg 77
1
bcin 27
Hence, we
bdp
get
bco
7/9 110-1)1 11
Σ 1=1
3 II (1 (1-11-0 azb) S at 1
Σ
aj exp
exp
28
E=j+1
j=1
{=j+1
Therefore, Lemma 25 together with the elementary inequality e * I 1 x/2 for (0: 10:) implies that
Σ 1=1
og II
(1 ard)
S
ak
8-1
Σ aj II (1-
1 as) exp 7(9 () 1) + 11
b
E=-1
(=j+1
8- 1 4 4(q 1)m)
27(9-1)/(11)
< a
b
bco
Lemma 31. For any A > O. any 0 < is - and any y E (1/2, 1) it holds
1 1 cxp 1 } 1110-1 (1- D( 1(11),
if A
- S 1-7
and 2
n-1
exp
-AG
A(j
1 + 1111)120"
if Ail-- > 1-9
1 and 2 1:
j=i
1 X
ifi=0.
Proof.
The proof is given in 70 Lemma 16).
61

---

H
Applications to the TD learning algorithm
Recall that the TD learning algorithm within the framework of linear stochastic approximation (LSA) can be written as
O2 0k-1 ax bk),
(75)
where the matrices A& and vectors by are defined by
A - ((x))(((xx) - {p((R++)3",
b = y (**))R(*=))
Our primary objective is to estimate the agent's value function, defined as
(s) EI R(Sa) So - s]
where S4+1 ~ P(. Sk) for all N. In this context, the TD learning updates (75) correspond to approximating solutions to the deterministic linear system Ag = b (see (77)), where the matrix A and right-hand side b are given by
A E o P(-b) (((())(())) {p(s
E Exna (ss))(ss)]
The rest of the proof of Proposition 5 reduces to checking the properties of A and direct verification of conditions Proposition] 2 which is done by the lines of [67] Proposition 2]
Numerical experiments. We consider the simple instance of the Garnet problem 32 This problem is characterized by the number of states N.. number of actions a, and branching factor Here b corresponds to the number of states s', that can be reached when starting from given state- action pair (s, a). The reward r(s. a) E [0, 1] is a deterministic function. We set the hyperparameter values N₂ 6, 2, 3, feature dimension = 2, and discount factor
0.8. We aim
to evaluate the value function of policy т T--(s), which is given, for any a E A = {1, 2), by the expression
Talss) = Σ 1 U(#)
where the U/(0) are i.dd. observations with 21 1]. In this case we can suppose that R(s) state and some independent random
Ba-- a) is a random variable which depends variable. We consider the problem of policy evaluation in this MDP using the TD learning algorithm with randomly generated feature mapping, that is, we generate the matrix
① E N.xd
{1...., |S]]. to its s-th row, normalized by its euclidean norm: d0s) $ 11. We run the procedure ( with the learning rates ag co/ (ko + 7)7 with 7 = 2/3 with appropriately chosen and ko- We generate random vector form unitary sphere, and compute coverage probabilities for u 0* for confidence levels {0.8, 0.9, 0.95}. The detailed setting of the experiments follows (2).. Results are given in Table and illustrates the consistency of multiplier subsample bootstrap procedure applied on the Gareet problem.
with i.i.d. AN 1) entries, and then take d(s),
Table 1: Coverage probabilities of OBM estimation for the empirical distribution.
0.95
0.9
0.8
stddev x 1
n bn
(u)
(u)
(x)
(?)
03(x)
d²(u)
20480
| 250
0.873
0.881
0.773
0.805
0.641
0.662
10.89
204800
1200
0.935
0.945
0.880
0.892
0.768
0.784
3.49
1024000
3600
0.942
0.948
0.887
0.897
0.769
0.788
1.56
Code to reproduce experiments is given in hattps://githin com wwt..///saaooooo//aaaaaaaaeeeeea sermal_approxiimate Our experiments were conducted on single Intel Xeon Gold 6248R CPU (48 cores, 3.0-4.0 GHz), 768 GB RAM. and 240 GB SSD storage, without GPU accelerators.
1sa
62


Reviews:
[{"review_id": "UUijL2PAzL", "reviewer": "Reviewer_1bdC", "summary": "The authors study the problem of deriving central limit theorems and bootstrap consistency results for iterates in linear stochastic approximation (LSA) problems under Markovian noise.   They derive a Berry-Esseen type result for Polyak–Ruppert averaged iterates projected onto the unit sphere with a fixed vector. The convergence rate $n^{-1/4}$ matches the sharpest available bounds in the literature for TD learning.  They also establish rate of convergence for a Gaussian block-multiplier bootstrap procedure.", "questions": "- If you generalize your approach to avoid a fixed projection vector $u$, would the rate of convergence remain the same?  I expect that this would be the case, but if the authors could explain the main technical difficulty with considering the $d$-dimensional case, it would be appreciated. \n-  Along similar lines, would be possible to consider a growing $d$ regime with appropriate moment bounds?", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The proof of the central limit theorem uses interesting technical tools related to Poisson approximation of Markov chains, and the resulting rate matches other results derived for similar problems. \n- The authors derive a result involving the bootstrap for LSA problems, which appears to be the first such result in the literature. \n- The bootstrap result involves an interesting approximation argument that handles the fact that the iterates are not themselves a Markov chain. \n- The paper is well-written overall and clear.   \n\nWeaknesses\n- Results involving a fixed projection are weaker than those involving the convex distance in $\\mathbb{R}^d$.  The closely related work of Wu, Wei, and Rinaldo (2025) derive such a result, and attain the same rate of convergence.  Moreover, the above result appears to allow $d$ to grow, whereas the arguments in the current paper appear to require $d$ to be fixed.     \n- The rate of convergence for the bootstrap is slightly disappointing.  The authors give some intuition as to why the rate of convergence is slower. It appears to arise from choosing tuning parameters to balance the rate of convergence for the central limit theorem with variance estimation. It also appears to be related to the choice of target variance.", "was_revised": true, "final_justification": "I still have some concerns related to the fixed projection vector and closeness of the results to the existing work of Wu, Wei, and Rinaldo (2025).  However, the authors have pointed out some differences in the conditions between these results, and have elaborated on the difficulty of generalizing to other distances.  I am willing to slightly increase my score.", "rebuttal": "We thank the reviewer for acknowledging the theoretical contribution of the paper and the fact that it is well-written. Below we respond to the weaknesses and questions raised by the reviewer. \n\nWeakness 1. ***Results involving a fixed projection are weaker than those involving the convex distance in $\\mathbb{R}^d$. The closely related work of Wu, Wei, and Rinaldo (2025) [81] derive such a result, and attain the same rate of convergence. Moreover, the above result appears to allow $d$ to grow, whereas the arguments in the current paper appear to require $d$ to be fixed.*** \n\nThe reviewer is correct to mention the paper [81] deals with the convex distance in $\\mathbb{R}^d$. At the same time, we highlight that the results of [81] hold only for specific problem, namely for TD leaning, at the same time we consider general LSA problem. It is not clear if the obtained results can be directly translated to the setting of general LSA, since they rely on a particular properties of the design matrix, which are specific to the TD learning. Moreover, the authors of [81] do not provide an algorithm for inference and constructing the confidence intervals, contrary to our submission.  \n\nAlso, we would like to mention that the results in [81] appeared recently - just about three months before the NeurIPS deadline. It is in fact close to be a concurrent submission according to NeurIPS guidelines, and, to our knowledge, it is not yet published. At the same time, the key element of their analysis involves a non-asymptotic CLT for vector-valued martingales, which is a complicated result, which requires to be carefully checked. In fact, a version of such a martingale CLT has been provided in a recent paper [59], but later the authors of [81] found a missing term in their analysis. This comment is not to criticize the paper [59], but rather to acknowledge that the field of martingale CLTs relies of technically invlved arguments, where it is extremely easy to make a mistake. \n\nOur analysis was carried out independently of [81] and provides a result based on peer-reviewed and well-established results [11] and [27]. We do not claim that the results in [81] are incorrect; rather, due to the recency of the work and the technical complexity of the methods involved, we were not in a position to fully verify their applicability in our setting within the submission timeframe.\n\nFurthermore, applying the results from [81] would require the quadratic characteristic of the  martingale to be almost surely constant, which is not the case of our submission. Extending their approach to our setting would therefore require additional nontrivial modifications, which are similar to those which are incorporated in our paper when building upon the Bolthausen's result [11]. We hope this clarifies our choice of probabilistic tools used in our results.\n\n***Moreover, the above result appears to allow $d$ to grow, whereas the arguments in the current paper appear to require $d$ to be fixed*** We would appreciate if the reviewer could clarify what it means that the dimension $d$ of the parameter $\\theta$ grows during the execution of the algorithm. Typically when considering the LSA problem, the problem dimension is already fixed and it is not clear, how one could interpret adding new lines/columns to the system matrix $\\bar{A}$ or adding new features when considering the TD learning algorithm. \n\nWeakness 2. ***The rate of convergence for the bootstrap is slightly disappointing. The authors give some intuition as to why the rate of convergence is slower. It appears to arise from choosing tuning parameters to balance the rate of convergence for the central limit theorem with variance estimation. It also appears to be related to the choice of target variance.***\n\n We agree that the obtained rate may appear suboptimal. However, to the best of our knowledge, this is the first result providing a fully non-asymptotic analysis for constructing confidence intervals in the linear stochastic approximation (LSA) setting with Markovian noise.  Furthermore, if we focus on the accuracy of the variance approximation—i.e., how well our bootstrap estimator approximates the asymptotic covariance —we achieve a high-probability bound of order $\\mathcal{O}(n^{-1/8})$. This matches the rate established in [63] for a different estimator (batch mean method) in the context of stochastic gradient descent (SGD) with Markovian noise, though their result holds only in expectation, that is for $\\mathbb{E}[\\|\\hat \\Sigma_n - \\Sigma_\\infty\\|]$. The latter rate is, so the best of our knowledge, the best one which is currently in the literature.\n\nQ1. ***If you generalize your approach to avoid a fixed projection vector $u$, would the rate of convergence remain the same? I expect that this would be the case, but if the authors could explain the main technical difficulty with considering the $d$-dimensional case, it would be appreciated.***  \n\nExtending our results to the unprojected algorithm is an important direction, but it introduces several technical challenges. Specifically, two key technical obstacles arise:\n\na. Establishing a Gaussian approximation for sums of martingale-difference sequences;\n\nb. Obtaining concentration bounds for the overlapping batch mean estimator of the covariance matrix.\n\nThe step (a) is especially involved, and associated issues are discussed above in response to Weakness 1. The step (b) is also challenging, and there is no ready-to-use results which can be applied at this point. Both steps involve significant additional complexity, and we leave this extension for future work.\n\nQ2. ***Along similar lines, would be possible to consider a growing $d$ regime with appropriate moment bounds?*** We agree that our theoretical results are obtained under the condition of a fixed parameter dimension $d$. However, we would like to note that it is not clear how to formulate the statement for the LSA algorithm in the case when the dimension $d$ of the parameter $\\theta$ changes during its execution. We would be grateful if the reviewer could clarify or specify this comment.\n\n***References***\n\n[11] E. Bolthausen. Exact Convergence Rates in Some Martingale Central Limit Theorems. The Annals of Probability, 10(3):672 – 688, 1982.\n\n[27] Xiequan Fan. Exact rates of convergence in some martingale central limit theorems. Journal of Mathematical Analysis and Applications, 469(2):1028–1044, 2019.\n\n[59] Pratik Ramprasad, Yuantong Li, Zhuoran Yang, Zhaoran Wang, Will Wei Sun, and Guang Cheng. Online bootstrap inference for policy evaluation in reinforcement learning. J. Amer. Statist. Assoc., 118(544):2901–2914, 2023.\n\n[81] Weichen Wu, Yuting Wei, and Alessandro Rinaldo. Uncertainty quantification for Markov chains with application to temporal difference learning. arXiv preprint arXiv:2502.13822, 2025."}, {"review_id": "hw2qSLw8mY", "reviewer": "Reviewer_3fTA", "summary": "The paper studies the problem of Linear Stochastic Approximation (LSA) where\nthe noise is Markovian. In this setting, the authors focus on establishing\nnon-asymptotic Berry-Essen bounds for estimators that employ Polyak-Ruppert\naveraging. Over the course of the paper, the authors establish $O(n^{-1/4})$\nrates of convergence to the limiting Gaussian distribution w.r.t. the\nKolmogorov distance.\n\nMoreover, the paper studies the block bootstrap for estimating the variance\nof their estimator $\\overline{\\theta}_n$ of interest, showing it is consistent under the\nassumption of Markovian noise. Under mild assumptions, the paper recommends\na bootstrap growth rate $b_n$ and stepsize growth rate $\\alpha_k$ which\nyield a $O(n^{-1/8})$ convergence rate w.r.t. the Kolmogorov distance for\nany projected version of $\\sqrt{n}(\\overline{\\theta}_n - \\theta^*)$.\n\nThe paper concludes by offering a concrete application of their theory for\nthe temporal-difference learning algorithm applied to Markov decision\nprocesses.", "questions": "[Q1] Most of the random quantites studied in the paper are scalars, as they\nusually are the dot product between the estimator and some random vector\n$u$. Can the results here be generalized to the multivariate domain,\neschewing the need to choose these fixed vectors $u$ in advance?", "limitations": "No, the authors should explain whether there is any negative societal impact from doing this theoretical work.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nOriginality:\n\n[+] The approach taken by the paper appears to borrow from many different\nprevious works, e.g., by using the Poisson decomposition of Markov chains to\nhelp derive its non-asymptotic bounds. While the results accord with other\nworks, the proof strategy appears to be unique.\n\n[+] There is accompanying theory on the block bootstrap that can be used\nto estimate the non-asymptotic variance of the desired parameter\n$\\theta$. This proof appears to be novel and the first to do so in the LSA\nsetting with Markov noise.\n\nQuality:\n\n[+] The paper is very thorough and takes great care in defining all\nnotation, salient assumptions and related work. While I have not checked\neverything in the appendix, the paper seems sensible and does not contain\nany obvious flaws.\n\nClarity:\n\n[+] The paper is very clear and detail oriented. Most proofs are pushed to\nthe appendix so that the core ideas can be discussed in the main portion of\nthe text. While there is quite a bit of notation, the general ideas in the\npaper are well conveyed.\n\nSignificance:\n\n[+] The core significance of this paper is mostly\ntheoretical. Its convergence rate of asymptotic variance matches other works\nbut is more general as these techniques apply to Markovian noise rather than\nsimply independent noise samples.\n\n[+] The paper specifies a specific learning rate and bootstrap growth rate\nin the case of the bootstrap. Thus while theoretical, this provides some\npractical input for those practicing with this technique.\n\nWeaknesses:\n\nSignificance:\n\n[-] As discussed in the paper, in order to obtain these non-asymptotic error\nbounds, one must know the final value $n$ in advance. While this is not a\nhuge deal, it does impose some structure on the algorithms for which these\nbounds can be derived.\n\n[-] The work does not improve upon previous bounds; that being said, it does\ngeneralize the previously shown bounds to a non-asymptotic regime with\nMarkovian noise, which does appear novel.", "was_revised": true, "final_justification": "I think the work seems well argued and written. That being said, b/c of the similar work that has already been published, I have slightly reduced my score in significance and overall. I am still in favor of submission.", "rebuttal": "We thank the reviewer for their positive feedback and are happy to provide further details in response to their concerns.\n\nWeakness 1 ***As discussed in the paper, in order to obtain these non-asymptotic error bounds, one must know the final value $n$ in advance. While this is not a huge deal, it does impose some structure on the algorithms for which these bounds can be derived.***  Our proof technique requires to control the $p$-th moment of the last iterate, with $p \\approx \\log n$, in order to derive Theorem 1 about Gaussian approximation. This introduces the dependence of the step size upon the number of iterations $n$. It is known that, at least in case of constant step-size $\\alpha$, bounds on the $p$-th moments of the error require to choose $\\alpha \\approx 1/p$, as shown in [23]. Consequently, the total number of iterations $n$ must be known in advance to set the appropriate step-size. It is not immediately clear, if the same conclusion applies to the products of random matrices with decreasing step sizes, at the same time, there are some evidences, which support this claim. In particular, consider theorem 3.1 in the related paper [80]. The results are derived for the particular setting of TD(0) learning, yet they require to scale $c_0$ in the step size with the confidence parameter $\\delta$, which needs to be known in advance. Since we set $\\delta = 1/n$ in the current paper, this result reveals the same phenomenon about the total number of iterations.\n\nWe also note that if an extension of Theorem 2.1 from [69] were available for dependent sequences, such as Markov chain, then one could potentially avoid bounding high-order moments and rely instead on bounds for the second and fourth moments only. Developing such an extension is an interesting direction for future work.\n\nWeakness 2 ***The work does not improve upon previous bounds; that being said, it does generalize the previously shown bounds to a non-asymptotic regime with Markovian noise, which does appear novel.*** We would like to clarify that our work provides a high-probability bound on\n$$\n|u^\\top \\hat \\Sigma_n u - u^\\top \\Sigma_\\infty u|,\n$$\nwith rate $\\mathcal{O}(n^{-1/8})$, where $\\hat \\Sigma_n$ is multiplier subsample bootstrap estimator for  $\\Sigma_\\infty$. It is ture that similar rate was previously obtained in [63] for batch-mean estimators $\\tilde \\Sigma_n$ in the context of stochastic gradient descent (SGD) with Markovian noise. At the same, we highlight that this result holds only in expectation, that is,\n$$\n\\mathbb{E}[\\| \\tilde \\Sigma_n - \\Sigma_\\infty \\|].\n$$\nOur high-probability bounds are strictly stronger than bounds in expectation. Moreover, expectation-based bounds are insufficient for proving Gaussian comparison results, such as approximating the distribution of $\\mathcal{N}(0, \\hat\\Sigma_n)$ by $\\mathcal{N}(0, \\Sigma_\\infty)$ on events with high probability. Moreover, the authors of [63] do not take into account the rates of normal approximation for the original SGD estimate, which makes their final results purely asymptotic. Contrary, our works establishes the non-asymptotic CLT bounds in Kolmogorov distance for general linear stochastic approximation (LSA) with Markovian noise, and relies on them to show the non-asymptotic error of the suggested bootstrap approximation. Thus, it is not entirely correct to compare this rate with the one derived in [63].\n\nQ1. ***Most of the random quantites studied in the paper are scalars, as they usually are the dot product between the estimator and some random vector $u$. Can the results here be generalized to the multivariate domain, eschewing the need to choose these fixed vectors $u$ in advance?*** \n\nExtending our results to the unprojected algorithm is an important direction, but it introduces several technical challenges. Specifically, two key technical obstacles arise:\n\na. Establishing a Gaussian approximation for sums of martingale-difference sequences;\n\nb. Obtaining concentration bounds for the overlapping batch mean estimator of the covariance matrix.\n\nThe step (a) is especially involved, and associated issues are discussed above in response to  ***Reviewer 1bdC*** (Weakness 1). The step (b) is also challenging, and there are no ready-to-use results which can be applied at this point. Both steps involve significant additional complexity, and we leave this extension for future work. We will add a more comprehensive overview of these difficulties to the revised version of the paper.\n\n***References***\n\n[23] Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Samsonov, Kevin Scaman, and Hoi-To Wai. Tight high probability bounds for linear stochastic approximation with fixed stepsize. In M. Ranzato, A. Beygelzimer, K. Nguyen, P. S. Liang, J. W. Vaughan, and Y. Dauphin, editors, Advances in Neural Information Processing Systems, volume 34, pages 30063–30074. Curran Associates, Inc., 2021.\n\n[63] Abhishek Roy and Krishnakumar Balasubramanian. Online covariance estimation for stochastic gradient descent under Markovian sampling. arXiv preprint arXiv:2308.01481, 2023.\n\n[69] Qi-Man Shao and Zhuo-Song Zhang. Berry–Esseen bounds for multivariate nonlinear statistics with applications to M-estimators and stochastic gradient descent algorithms. Bernoulli, 28(3):1548–1576, 2022.\n\n[80] Weichen Wu, Gen Li, Yuting Wei, and Alessandro Rinaldo. Statistical Inference for Temporal Difference Learning with Linear Function Approximation. arXiv preprint arXiv:2410.16106, 2024."}, {"review_id": "hqlhadwc39", "reviewer": "Reviewer_nTAM", "summary": "The paper studies the statistical inference properties of the projected Polyak-Ruppert averaged iterates in Linear Stochastic Approximation (LSA) algorithms under a Markovian noise model. The authors establish non-asymptotic bounds for the convergence of the averaged iterates to a Gaussian distribution in the Kolmogorov distance, with a rate of $O(n^{-1/4})$. They also validate the multiplier subsample bootstrap (MSB) procedure and demonstrate its consistency, allowing the probabilities for the actual parameter $\\theta^\\star$ to be approximated at a rate of $O(n^{-1/10})$. Furthermore, the paper recovers an $O(n^{-1/8})$ rate (up to logarithmic factors) for estimating the asymptotic variance of the iterates. The theoretical results are finally applied to the TD learning setting, which becomes a specific instance of LSA under appropriate assumptions.", "questions": "The strengths and weaknesses section already provides some suggestions and questions. Here are additional questions:\n- Remark 1 states that \"Corollary 1 predicts the optimal error of ...\" Could the authors clarify what \"optimal\" refers to?\n- On page 6, it is claimed that the essential part of the analysis \"can be generalized to the $d$-dimensional case.\" Given this, what are the main challenges in extending the full result to multi-dimensional settings?\n- Are there technical tools used in the paper that are novel and worth highlighting? Or is the technical contribution mostly about applying existing results and their variants with a new proof strategy?", "limitations": "This is a theoretical paper and does not directly present societal concerns. As mentioned earlier, it is recommended to include a dedicated section that discusses the limitations of the assumptions (for practical applications) and compares them with relevant work.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper provides clear and rigorous theoretical contributions with non-asymptotic bounds for both approximation and bootstrap procedures, an area that has received less attention for Markovian settings compared to IID.\n- The Kolmogorov convergence rate of $O(n^{-1/4})$ seems to be novel and tighter than previous results, such as the Wasserstein bound of $O(n^{-1/6})$ in [72], which is $O(n^{-1/12})$ under Kolmogorov distance.\n- The authors carefully utilize the Poisson equation/decomposition and martingale CLTs for their analysis. The derivation is detailed and appears to be technically interesting.\n- The block bootstrap method is rigorously justified and analyzed non-asymptotically, which is novel within the LSA setting with Markov noise.\n\nWeaknesses:\n- The analysis is limited to one-dimensional projections of the estimation error. While the authors acknowledge this, extending the results to multivariate bounds remains an open question. Additionally, the results of [74] apply in a $d$-dimensional setting.\n- Assumptions such as those related to step size and tuning may be restrictive and impact the significance of the results. It is advisable to include a dedicated section discussing these limitations and comparing them with relevant work.\n- The bootstrap bound of $O(n^{-1/10})$, although novel, does not provide guarantees regarding its tightness or optimality. Could the authors offer insights into the best possible upper bound that might be achieved?\n- The results are primarily theoretical. Although the TD learning application is mentioned, there are few empirical plots or data tables throughout the entire submission (including supplementary materials) to demonstrate empirical convergence rates and algorithm performance. Some technical notations and assumptions may also hinder accessibility for non-expert audiences.", "was_revised": true, "final_justification": "A score of 4 shows my support for accepting the paper. The main points I raised in the initial review and during the rebuttal periods are to understand if the paper's results and methodologies extend to scopes that would interest a much broader community. In particular, I seek confirmation from the authors on the extensions to:\n- Higher dimensions\n- Settings with (much) fewer assumptions\n- More practically relevant bounds, unless the existing rates are not far from optimal.\n\nThough unable to make such extensions, the authors were able to present challenges and difficulties that one might face on the path. Hence, I kept my recommendation.", "rebuttal": "We thank the reviewer for their positive feedback and are happy to provide further details in response to their concerns. Below we provide our responses to weaknesses and questions (Q) raised by the reviewer. \n\nWeakness 1 and Q2 ***The analysis is limited to one-dimensional projections of the estimation error. While the authors acknowledge this, extending the results to multivariate bounds remains an open question. &  On page 6, it is claimed that the essential part of the analysis \"can be generalized to the $d$-dimensional case.\" Given this, what are the main challenges in extending the full result to multi-dimensional settings?*** \n\nExtending our results to the unprojected algorithm is an important direction, but it introduces several technical challenges. Specifically, two key technical obstacles arise:\n\na. Establishing a Gaussian approximation for sums of martingale-difference sequences;\n\nb. Obtaining concentration bounds for the overlapping batch mean estimator of the covariance matrix.\n\nThe step (a) is especially involved, and associated issues are discussed above in response to ***Reviewer 1bdC*** (Weakness 1). The step (b) is also challenging, and there is no ready-to-use which can be applied at this point. Both steps involve significant additional complexity, and we leave this extension for future work. At the same time, in our proofs  we rely on the $p$-th moment bounds on the error terms $\\mathbb{E}[\\|\\theta_k - \\theta^{\\star}\\|]$, which we derive in the current submission, and which are instrumental both for the martingale CLT (when dealing with non-constant quadratic characteristic), and for the subsequent analysis of the bootstrap procedure. \n\nWeakness 2 ***Assumptions such as those related to step size and tuning may be restrictive and impact the significance of the results. It is advisable to include a dedicated section discussing these limitations and comparing them with relevant work.*** We thank the reviewer for this comment and would include a more detailed discussion in the revised paper. We would like to emphasize that the step-size schedule $\\alpha_k = c_0 / (k_0 + k)^\\gamma$ is a standard and widely adopted choice in the stochastic approximation literature (see, e.g., \\[25, 70, 80]). The values of $c_0$ and $k_0$ indeed depend on problem-specific characteristics, and in our work, we provide explicit constraints on these constants to guarantee the validity of the non-asymptotic CLT bound.  The dependence of the parameters upon the total number of iterations $n$ is discussed in more details  in our answer to the reviewer ***3fTA***, see the corresponding Weakness 1. The key conclusion from our bounds is that the parameter $k_0$ needs to be chosen sufficiently large. \n\nWeakness 3 ***The bootstrap bound of $O(n^{-1/10})$ , although novel, does not provide guarantees regarding its tightness or optimality. Could the authors offer insights into the best possible upper bound that might be achieved?*** \n\nTo the best of our knowledge, our work provides the first non-asymptotic rate for constructing confidence intervals in the linear stochastic approximation (LSA) setting with Markovian noise. As such, there are currently no known lower bounds for this problem that would allow us to assess the optimality of the $O(n^{-1/10})$ rate. We believe that this rate may not be optimal, and can be improved.  In particular, we highlight that the available rates for estimating the covariance matrix $\\Sigma_{\\infty}$ in SA with Markov noise are also pessimistic. As stated in the paper, recent work [63] obtained rate $O(n^{-1/8})$ for such a problem, albeit also without lower bounds. At the same time, [63] derive only in-expectation bounds for estimating the error $\\mathbb{E}[\\|\\hat{\\Sigma}_n - \\Sigma_{\\infty}\\|] for the suggested estimator $\\hat{\\Sigma}_n$ for the batch-mean procedure. It is possible, that the same rate can be obtained in our inference problem, yet this would require a different proof strategy. We see this as an interesting direction for future research.\n\nWeakness 4 ***The results are primarily theoretical. Although the TD learning application is mentioned, there are few empirical plots or data tables throughout the entire submission (including supplementary materials) to demonstrate empirical convergence rates and algorithm performance.*** \n\nThe primary aim of the paper is theoretical, and it is true that some additional experimental settings can be added. While it is complicated (if not impossible) to trace numerically the convergence rate $n^{-1/10}$ for our inference procedure, in the revised version of the paper we can incorporate some additional examples for TD learning on more challenging environments, such as the ones from the recent paper [59]. Unfortunately, given the timeline, we are not able to provide these additional results before the rebuttal period ends.  \n\n ***Some technical notations and assumptions may also hinder accessibility for non-expert audiences.***\n\nThank you for this comment, in the revised version of the paper we will do our best to simplify exposition, at the same time, our results demand sophisticated tools for the proofs of the main results, such as martingale concentration inequalities, and given this it is not possible to provide fully elementary exposition. \n\nQ1  ***Remark 1 states that \"Corollary 1 predicts the optimal error of ...\" Could the authors clarify what \"optimal\" refers to? and the best possible upper bound that might be achieved?*** \n\nWe thank the reviewer for pointing out the ambiguity in the use of the term \"optimal error\" in Remark 1. In this context, by “optimal” we means simply the best possible bound, which can be inferred from Corollary 1 after optimizing its right-hand side over $\\gamma$. Through this optimization, we obtain a convergence rate $\\mathcal{O}(n^{-1/4})$ in the Kolmogorov distance. We do not claim that this rate is optimal, as no lower bounds are currently known for the general LSA problem with Markovian noise. However, we would like to note that the $\\mathcal{O}(n^{-1/4})$ rate we obtain in the general LSA setting matches the best-known bound established in [81] for particular instance of the LSA problem, namely, the temporal-difference (TD) learning with Markovian noise. We will revise the statement of Remark 1 to make this point clearer.\n\nQ3 ***Are there technical tools used in the paper that are novel and worth highlighting? Or is the technical contribution mostly about applying existing results and their variants with a new proof strategy?*** \n\nOur work introduces two technical contributions that we believe are of independent interest:\n\na. We show how the bootstrap procedure for LSA iterates with Markovian noise, where the bootstrap iterates themselves do not form a Markov chain, can be effectively reduced to a bootstrap procedure for linear statistics of Markov chains. In particular, we relate the bootstrap variance estimation in LSA to the problem of estimating the asymptotic variance of a certain linear statistic of a Markov chain, which generates noise in the LSA procedure. This reduction allows us to leverage concentration tools developed for the setting of linear statistics.\n\nb. Our proof of Theorem 1 relies on a new version of martingale Central Limit Theorem (CLT) applicable for martingale, which quadratic characteristic is not almost surely constant. This result of Lemma 21, provided in Appendix, provides such a result based on previously established theorems due to Bolthausen [11] and Fan [27]. This result provides a fully non-asymptotic bound in the Kolmogorov distance for scalar-valued martingales with explicit dependence upon $p$ and other problem characteristics.\n\n\n***References****\n\n[11] E. Bolthausen. Exact Convergence Rates in Some Martingale Central Limit Theorems. The Annals of Probability, 10(3):672 – 688, 1982.\n\n[25] Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Samsonov, and Hoi-To Wai. On the stability of random matrix product with markovian noise: Application to linear stochastic approximation and td learning. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 1711–1752. PMLR, 15–19 Aug 2021.\n\n[27] Xiequan Fan. Exact rates of convergence in some martingale central limit theorems. Journal of Mathematical Analysis and Applications, 469(2):1028–1044, 2019.\n\n[59] Pratik Ramprasad, Yuantong Li, Zhuoran Yang, Zhaoran Wang, Will Wei Sun, and Guang Cheng. Online bootstrap inference for policy evaluation in reinforcement learning. J. Amer. Statist. Assoc., 118(544):2901–2914, 2023.\n\n[63] Abhishek Roy and Krishnakumar Balasubramanian. Online covariance estimation for stochastic gradient descent under Markovian sampling. arXiv preprint arXiv:2308.01481, 2023.\n\n[70] Marina Sheshukova, Sergey Samsonov, Denis Belomestny, Eric Moulines, Qi-Man Shao, Zhuo-Song Zhang, and Alexey Naumov. Gaussian approximation and multiplier bootstrap for stochastic gradient descent. arXiv preprint arXiv:2502.06719, 2025.\n\n[80] Weichen Wu, Gen Li, Yuting Wei, and Alessandro Rinaldo. Statistical Inference for Temporal Difference Learning with Linear Function Approximation. arXiv preprint arXiv:2410.16106, 2024.\n\n[81] Weichen Wu, Yuting Wei, and Alessandro Rinaldo. Uncertainty quantification for Markov chains with application to temporal difference learning. arXiv preprint arXiv:2502.13822, 2025."}, {"review_id": "HhmVz27D9Y", "reviewer": "Reviewer_QGKs", "summary": "The paper establishes finite-sample inference for Polyak–Ruppert averaged linear stochastic approximation under uniformly geometrically ergodic Markov noise by (1) proving a non-asymptotic Berry–Esseen bound of order $O(n^{-1/4})$ for one-dimensional projections of $\\sqrt{n}(\\bar\\theta_n - \\theta^*)$, and (2) developing a multiplier block bootstrap with $O(n^{-1/10})$ finite-sample coverage error (up to logs). The analysis, based on Poisson-equation decompositions, martingale Berry–Esseen techniques, and overlapping batch means for variance estimation, is illustrated in the context of temporal-difference learning with linear function approximation.", "questions": "The questions follow the order of the weaknesses listed above.\n\n1. Could the authors clarify how Markovian noise actually arises in real-world SA applications? In particular, could they provide concrete instances to substantiate the statement “many practical SA applications involve dependent noise, often forming a Markov chain” (line 21)? Addressing this would help improve the **clarity** and **significance** scores.\n2. Could the authors provide empirical mean-squared error decay curves (for example, log-log plots of\n   $\\mathbb{E}\\|\\bar\\theta_n - \\theta^*\\|^2$ versus $n$) on a nontrivial benchmark and compare the observed slope to the $O(n^{-1/4})$ rate predicted by Theorem 1? This would directly assess whether the theory captures real-world behavior. Addressing this would help improve the **significance** score.\n\n3. Although the related works section (Section 2) discusses many results under i.i.d. noise, could the authors comment on the key differences between the i.i.d. and Markovian noise settings, particularly regarding the theoretical tools and techniques required for analysis? Addressing this would help improve the **significance** score.", "limitations": "Yes, the authors acknowledge potential limitations.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strengths:\n\n* The paper is very well organized, with thorough background and motivation, a comprehensive related works section, clear motivations before each theorem, and insightful discussions after each result, all of which greatly aid reader comprehension.\n* Provides the first non-asymptotic coverage error bounds for bootstrap methods under dependent (Markovian) SA iterates, which is valuable for online learning and RL applications.\n* The theoretical analysis is rigorous and solid, combining Poisson equation techniques for Markov chains, martingale Berry–Esseen bounds, and batch means/multiplier block bootstrap analysis under dependence, with sound logic and careful handling of technical conditions.\n\n# Weaknesses:\n\nPlease note that the following weaknesses do not undermine the core contributions, but addressing them would make the paper even stronger:\n\n* Since the paper’s central focus is on analysis under Markovian noise, the unsubstantiated claim that “many practical SA applications involve dependent noise, often forming a Markov chain” (line 21) leaves readers without the concrete motivation needed to appreciate why handling this specific dependency structure is both relevant and necessary.\n* The experimental validation in Appendix G is limited to synthetic and relatively small-scale examples, so it is unclear how the proposed theoretical bounds and bootstrap intervals hold up on larger or real-world problems.\n* The related works section (Section 2) reviews many results under i.i.d. noise but does not explain how the theoretical tools and proof techniques must change in the Markovian setting, making it hard to see what new challenges the paper overcomes.", "was_revised": true, "final_justification": "I am satisfied with the authors’ clarifications and am happy to maintain my original score.", "rebuttal": "We thank the reviewer for their  positive  feedback and are happy to provide further details in response to the questions they raised.\n\nQ1  ***Could the authors clarify how Markovian noise actually arises in real-world SA applications?*** \n\nThis setting naturally arises for Reinforcement Learning algorithms, since it is typical that the sequence of agent's states form a Markov chain in this case. Below, we provide concrete examples from RL domain where Markovian noise naturally appears in LSA:\n\n***Temporal-Difference (TD) Learning with linear function approximation***\nTD(0) and its variants are widely used for policy evaluation. These methods update parameters using observed transitions $(s_n, r_n, s_{n+1})$, which are generated by following a fixed policy in a Markov Decision Process (MDP). One can find details about this setting, for example, in the recent paper [68].\n\n**Gradient Temporal Difference Learning (GTD, GTD2):** GTD algorithms, designed for stable off-policy learning, also rely on linear updates based on sequences of transitions $(s_n, a_n, r_n, s_{n+1})$ generated by a behavior policy in an MDP.\nIn all these examples, the data used for parameter updates come from trajectories in an MDP and thus form a Markov chain. Since the update rules are linear in the parameters and the stochastic noise arises from a Markovian process, these algorithms are naturally modeled as instances of LSA with Markovian noise.\n\nQ2 ***Could the authors provide empirical mean-squared error decay curves (for example, log-log plots of $\\mathbb{E}|\\bar\\theta_{n} - \\theta^\\star|^2$ versus $n$) on a nontrivial benchmark and compare the observed slope to the $O(n^{-1/4})$  rate predicted by Theorem 1?***  \n\nWe would like to clarify, that the main focus of our work is not on to bound the mean-squared error $\\mathbb{E}\\|\\bar\\theta_n - \\theta^\\star\\|^2$, but to establish a rate of convergence to the Gaussian limit in the Kolmogorov distance:\n$$\n\\sup_{x \\in \\mathbb{R}} \\| \\mathbb{P} \\left( \\sqrt{n} u^\\top (\\bar\\theta_n - \\theta^\\star) \\leq x \\right) - \\Phi(x) \\|,\n$$\nwhere $\\Phi(x)$ denotes the standard normal cumulative distribution function. This object is significantly more complicated, as it captures distributional convergence rather than second-moment decay. Moreover, empirical estimation of the Kolmogorov distance on a nontrivial benchmark is highly computationally intensive. It requires accurately estimating the distribution of $\\sqrt{n} u^\\top (\\bar\\theta_n - \\theta^*)$, which in turn necessitates a large number of independent trajectories to obtain empirical cumulative distribution function. At the same time, we acknowledge the importance of lower bounds for the rates obtained in Theorem 1. \n\nQ3  ***Although the related works section (Section 2) discusses many results under i.i.d. noise, could the authors comment on the key differences between the i.i.d. and Markovian noise settings, particularly regarding the theoretical tools and techniques required for analysis?*** The works [67] and [80] consider the LSA problem with i.i.d noise. The main  technical difference is that the tools used in [67] and [80], notably the Berry–Esseen type bounds for nonlinear statistics by Shao and Zhang (see [69]), are applicable only for i.i.d. random variables. Our work, as well as [67] and [80], relies on a decomposition of the form\n$$\n\\sqrt{n}(\\bar\\theta\\_k - \\theta^\\star) = W + D\n$$\nwhere $W$ is a linear statistic and $D$ is a nonlinear remainder term. In the i.i.d. setting considered in [67] and [80], it is sufficient to control the second moment of $D$. However, in the Markovian setting, we must instead control higher-order moments, typically up to the $p$-th moment, where $p \\simeq \\log n$. In addition, we would like to highlight that the results of [80] hold only for specific problem, namely for TD leaning, at the same time we consider general LSA problem.\n\nAnother issue with this decomposition arises already from the central limit theorem for the linear statistic $W$. While in the i.i.d. setting, there are considerable number of papers which study this problem and the dependence of convergence upon the problem dimension $d$ (e.g. [6]), setting of Markov chains and martingales if far less studied. Typically published in peer-reviews journals results only cover the 1-dimensional setting, or are not explicit with respect to mixing time of the underlying Markov chain. \n\nOne more methodological difference is that [67] investigates the validity of the multiplier bootstrap procedure for constructing confidence intervals for general LSA problem with i.i.d. noise, which is different from the procedure outlined in our paper. This is due to the fact, that this procedure is not applicable under Markovian noise due to sample dependence. In fact, [41, Proposition 1] shows that the limiting distributions of the multiplier bootstrap SGD and the original SGD can differ, implying that this bootstrap method is not even asymptotically valid. To address this issue, we propose an alternative procedure— multiplier subsample bootstrap —which requires completely different analysis. \n\n***References***\n\n[6] V. Bentkus. On the dependence of the Berry–Esseen bound on dimension. Journal of Statistical Planning and Inference, 113(2):385–402, 2003.\n\n[41] Ruiqi Liu, Xi Chen, and Zuofeng Shang. Statistical inference with Stochastic Gradient Methods under -mixing Data. arXiv preprint arXiv:2302.12717, 2023.\n\n[67] Sergey Samsonov, Eric Moulines, Qi-Man Shao, Zhuo-Song Zhang, and Alexey Naumov. Gaus- sian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning. In Advances in Neural Information Process- ing Systems, volume 37, pages 12408–12460. Curran Associates, Inc., 2024.\n\n[68] Sergey Samsonov, Daniil Tiapkin, Alexey Naumov, and Eric Moulines. Improved High Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 4511–4547. PMLR, 30 Jun–03 Jul 2024.\n\n[69] Qi-Man Shao and Zhuo-Song Zhang. Berry–Esseen bounds for multivariate nonlinear statistics with applications to M-estimators and stochastic gradient descent algorithms. Bernoulli, 28(3):1548–1576, 2022.\n\n[80] Weichen Wu, Gen Li, Yuting Wei, and Alessandro Rinaldo. Statistical Inference for Temporal Difference Learning with Linear Function Approximation. arXiv preprint arXiv:2410.16106, 2024."}, {"review_id": "KeyGBxXRdR", "reviewer": "Reviewer_sZzp", "summary": "This paper derives Berry–Esseen bounds for the averaged iterates of linear stochastic approximation under ergodic Markovian noise. Moreover, the authors obtain non-asymptotic guarantees for the multiplier subsample bootstrap estimator, including explicit error rates for estimating the asymptotic covariance matrix and for the coverage probabilities of $\\theta^*$.", "questions": "I hope the following questions would help the authors improve the paper.\n\nQ1. This paper appears to extend the results of [67] by relaxing the i.i.d. noise assumption to ergodic Markovian noise. It would help readers if the authors could clarify (i) the main technical challenges in moving from the i.i.d. to the Markovian setting and (ii) the key distinctions between this work and [67].\n\nQ2. On line 222 the authors state that [81] derives a Berry–Esseen bound for TD learning under Markov noise with the similar rate $\\tilde{\\mathcal{O}}(1/n^{1/4})$. Could you elaborate on why the techniques in [81] do not carry over directly to the general linear stochastic approximation with Markovian noise?\n\nQ3. In the introduction the authors note two standard approaches for constructing confidence intervals based on asymptotic normality—plug-in and batch-mean estimators. In the i.i.d. setting, [80] employs a plug-in estimator and attains an \\$\\mathcal{O}(n^{-1/3})\\$ approximation rate for \\$\\theta^\\ast\\$ in TD learning, outperforming the \\$\\mathcal{O}(n^{-1/4})\\$ rate typically achieved by batch-mean estimators for general linear SA. In this paper, the authors adopt a batch-mean method and derives an \\$\\mathcal{O}(n^{-1/10})\\$ rate for linear SA with Markovian data. Could you clarify (i) why plug-in methods were not considered for the Markovian setting and (ii) whether the \\$\\mathcal{O}(n^{-1/10})\\$ rate is believed to be optimal?\n\nQ4. In this paper, the results are derived for projected iterates. Could the authors clarify whether analogous guarantees would hold for the unprojected algorithm, and what specific technical obstacles would need to be overcome to establish such an extension?\n\nQ5. The manuscript introduces many definitions—see, for instance, Lines 182 and 266—without offering the intuition behind them. As a result, readers may struggle to recall what each term represents and to follow the authors’ line of reasoning.\n\nQ6. Throughout the paper, the time index alternates between $k$ and $n$. For clarity and consistency, it would be preferable to choose a single symbol and use it uniformly.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nS1. To the best of my knowledge, the Berry–Esseen bounds the authors derive—expressed in Kolmogorov distance—for averaged linear stochastic-approximation iterates under ergodic Markovian noise are novel. The analysis also makes particularly effective use of the Poisson decomposition for Markov chains.\n\nS2. This is a theoretically solid work. The proof seems correct, although I did not check line by line.\n\nWeaknesses:\n\nPlease see questions below.", "was_revised": true, "final_justification": "After reading the rebuttal, I am convinced that extending the analysis from the i.i.d. setting to the Markovian setting introduces substantial technical challenges, which this paper addresses very effectively. However, because the convergence rate of \\$\\mathcal{O}(n^{-1/10})\\$ is not optimal and the results are limited to projected algorithms—as noted in my Q3 and Q4—I am raising my score only from 3 to 4.", "rebuttal": "We thank the reviewer for their feedback. Below we address some points raised as weaknesses and provide responses to the listed questions.\n\nQ1 ***(i) the main technical challenges in moving from the i.i.d. to the Markovian setting and (ii) the key distinctions between this work and [67].*** The detailed answer to this question is given in our reply to Q3 to the reviewer ***QGKs***. We briefly repeat key points here. The main  technical difference is that the tools used in [67], notably the Berry–Esseen-type bounds for nonlinear statistics (see [69]), require independence and are not applicable in our setting. Both our work and \\[67] rely on a decomposition of the form $\\sqrt{n}(\\bar\\theta_n - \\theta^*) = W + D$, where $W$ is a linear statistic and $D$ is a nonlinear remainder term. In the i.i.d. setting considered in [67], it is sufficient to control the second moment of $D$. However, in the Markovian setting, we must instead control higher-order moments, typically up to the $p$-th moment, where $p \\simeq \\log n$.\nMoreover, [67] investigates the validity of the multiplier bootstrap for constructing confidence intervals. This technique, however, is not applicable under Markovian noise due to sample dependence. In fact, [41, Proposition 1] shows that the limiting distributions of the multiplier bootstrap SGD and the original SGD can differ, implying that this bootstrap method cannot be  used for constracting confidence intervals in the Markovian case.\nTo address this issue, we propose an alternative procedure—multiplier subsample bootstrap—which requires a more technically involved analysis.\nIn summary, while both works share the goal of providing non-asymptotic bounds for LSA algorithm, the Markovian setting introduces significant technical challenges. \n\nQ2 ***Could you elaborate on why the techniques in [81] do not carry over directly to the general linear stochastic approximation with Markovian noise?*** \nWe highlight that the results of [81] hold only for specific problem, namely for TD leaning, at the same time we consider general LSA problem. It is not clear if the obtained results can be directly translated to the setting of general LSA, since they rely on a particular properties of the design matrix, which are specific to the TD learning. Moreover, the authors of [81] do not provide an algorithm for inference and constructing the confidence intervals, contrary to our submission.  \n\nAlso, we would like to mention that the results in [81] appeared recently - just about three months before the NeurIPS deadline. It is in fact close to be a concurrent submission according to NeurIPS guidelines, and, to our knowledge, it is not yet published. At the same time, the key element of their analysis involves a non-asymptotic CLT for vector-valued martingales, which is a complicated result, which requires to be carefully checked. In fact, a version of such a martingale CLT has been provided in a recent paper [59], but later the authors of [81] found a missing term in their analysis. This comment is not to criticize the paper [59], but rather to acknowledge that the field of martingale CLTs relies of technically invlved arguments, where it is extremely easy to make a mistake. \n\nOur analysis was carried out independently of [81] and provides a result based on peer-reviewed and well-established results [11] and [27]. We do not claim that the results in [81] are incorrect; rather, due to the recency of the work and the technical complexity of the methods involved, we were not in a position to fully verify their applicability in our setting within the submission timeframe.\n\nFurthermore, applying the results from [81] would require the quadratic characteristic of the  martingale to be almost surely constant, which is not the case of our submission. Extending their approach to our setting would therefore require additional nontrivial modifications, which are similar to those which are incorporated in our paper when building upon the Bolthausen's result [11]. We hope this clarifies our choice of probabilistic tools used in our results.\n\nQ3 ***Could you clarify (i) why plug-in methods were not considered for the Markovian setting & clarifying rates of convergence*** To the best of our knowledge, indeed, there are not result of this type in the literature in Markovain setting. Moreover, a complete non-asymptotic analysis of plug-in methods even for general SGD (not LSA) and linear stochastic approximation (LSA) with Markovian noise does not exist. First of all, this is due to the fact that one needs to estimate the noise covariance matrix $\\Sigma_{\\varepsilon}$ defined in our submission, defined in lines 147-148. This step is computationally intensive, and ,ight require additional nested procedure to estimate covariances. \n\nMoreover, existing results for plug-in or batch-mean methods for SA in the literature typically provide only in-expectation bounds of the form $\\mathbb{E}[\\|\\hat \\Sigma_n - \\Sigma_\\infty\\|],$ which are not sufficient to provide on Gaussian approximation and do not take into account the convergence rate in CLT. In particular, in-expectation bounds do not guarantee accurate distributional approximations between \n$N(0, \\hat \\Sigma_n)$ and \n$N(0, \\Sigma_{\\infty})$ on events with high probability. Such guarantees are essential for establishing a Gaussian comparison bound. In contrast, our work provides a high-probability bound on\n$|u^\\top \\hat \\Sigma_n u - u^\\top \\Sigma_\\infty u|$, with rate $\\mathcal{O}(n^{-1/8})$. Notably, a similar rate appears in [63], which studies batch mean estimators for stochastic gradient descent (SGD) with Markovian noise, though only in expectation. \n\n***(ii) whether the ${\\mathcal{O}}(n^{-1/10})$ rate is believed to be optimal?*** This is a very intersring question, please see our response to the Weakness 3 raised by reviewer ***nTAM***.\n\nQ4 ***Could the authors clarify whether analogous guarantees would hold for the unprojected algorithm, and what specific technical obstacles would need to be overcome to establish such an extension?*** Extending our results to the unprojected algorithm is an important direction, but it introduces several technical challenges. Specifically, two key technical obstacles arise:\n\na. Establishing a Gaussian approximation for sums of martingale-difference sequences;\n\nb. Obtaining concentration bounds for the overlapping batch mean estimator of the covariance matrix.\n\nThe step (a) is especially involved, and associated issues are discussed above in response to ***Reviewer 1bdC*** (Weakness 1). The step (b) is also challenging, and there is no ready-to-use which can be applied at this point. Both steps involve significant additional complexity, and we leave this extension for future work.\n\nQ5  ***The manuscript introduces many definitions—see, for instance, Lines 182 and 266—without offering the intuition behind them. As a result, readers may struggle to recall what each term represents and to follow the authors’ line of reasoning*** Thank you for the suggestion. These notations were introduced primarily to simplify the exposition and streamline the technical arguments. In the final version of the paper, we will do our best to improve clarity by adding more intuition and brief reminders when key definitions are reused. At the same time, our results rely on sophisticated tools for the proofs of the main results, such as martingale concentration inequalities, and given this it is not possible to provide fully elementary exposition.\n\nQ6 ***Throughout the paper, the time index alternates between $k$ and $n$. For clarity and consistency, it would be preferable to choose a single symbol and use it uniformly.*** Thank you for the comment. We use the indices $k$ and $n$ to distinguish between their different roles: $n$ denotes the total number of iterations of the LSA algorithm, while $k$ refers to a generic intermediate iteration index. We use index $k$ to present results which hold true for any intermediate iteration index $k$. We will clarify this in the notation section to avoid confusion.\n\n***References***\n\n[11]E. Bolthausen. Exact Convergence Rates in Some Martingale Central Limit Theorems. The Annals of Probability, 10(3):672 – 688, 1982.\n\n[27]Xiequan Fan. Exact rates of convergence in some martingale central limit theorems. Journal of Mathematical Analysis and Applications, 469(2):1028–1044, 2019.\n\n[41] Ruiqi Liu, Xi Chen, and Zuofeng Shang. Statistical inference with Stochastic Gradient Methods under \u0000$\\phi$-mixing Data. arXiv preprint arXiv:2302.12717, 2023.\n\n[59] Pratik Ramprasad, Yuantong Li, Zhuoran Yang, Zhaoran Wang, Will Wei Sun, and Guang Cheng. Online bootstrap inference for policy evaluation in reinforcement learning. J. Amer. Statist. Assoc., 118(544):2901–2914, 2023.\n\n[63] Abhishek Roy and Krishnakumar Balasubramanian. Online covariance estimation for stochastic gradient descent under Markovian sampling. arXiv preprint arXiv:2308.01481, 2023.\n\n[67] Sergey Samsonov, Eric Moulines, Qi-Man Shao, Zhuo-Song Zhang, and Alexey Naumov. Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning. In Advances in Neural Information Processing Systems, volume 37, pages 12408–12460. Curran Associates, Inc., 2024.\n\n[69] Qi-Man Shao and Zhuo-Song Zhang. Berry–Esseen bounds for multivariate nonlinear statistics with applications to M-estimators and stochastic gradient descent algorithms. Bernoulli, 28(3):1548–1576, 2022.\n\n[81] Weichen Wu, Yuting Wei, and Alessandro Rinaldo. Uncertainty quantification for Markov chains with application to temporal difference learning. arXiv preprint arXiv:2502.13822, 2025."}]

Author rebuttal:

Meta-review: The paper establishes non-asymptotic Berry–Esseen bounds for Polyak–Ruppert averaged Linear Stochastic Approximation (LSA) under Markovian noise, providing convergence rates to the Gaussian limit. It also validates a multiplier block bootstrap for confidence intervals, giving the first non-asymptotic guarantees for bootstrap inference in this setting and recovering classical variance estimation rates up to logarithmic factors.

The contributions of this paper are interesting and makes a significant contributions to the growing area of SGD inference with Markovian data. Hence, the paper is recommend for acceptance.
Decision: Accept (poster)