Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise
Authors: Sebastian Allmeier
Nicolas Gast
Venue: NeurIPS 2024 poster (2024)
Keywords: Stochastic approximation; Polyak-Ruppert averaging; Stein's method
Primary area: optimization
TL;DR: We characterize the bias of constant step-size stochastic approximation by using generator techniques close to Stein's method.

Abstract: We study stochastic approximation algorithms with Markovian noise and constant step-size $\alpha$. We develop a method based on infinitesimal generator comparisons to study the bias of the algorithm, which is the expected difference between $\theta_n$ ---the value at iteration $n$--- and $\theta^*$ ---the unique equilibrium of the corresponding ODE. We show that, under some smoothness conditions, this bias is of order $O(\alpha)$. Furthermore, we show that the time-averaged bias is equal to $\alpha V + O(\alpha^2)$, where $V$ is a constant characterized by a Lyapunov equation, showing that $E[\bar{\theta}_n] \approx \theta^*+V\alpha + O(\alpha^2)$, where $\bar{\theta}_n$ is the Polyak-Ruppert average.  We also show that $\bar{\theta}_n$ converges with high probability around $\theta^*+\alpha V$. We illustrate how to combine this with Richardson-Romberg extrapolation to derive an iterative scheme with a bias of order $O(\alpha^2)$.

Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise
Sebastian Allmeier Univ. Grenoble Alpes and Inria F-38000 Grenoble, France.
Nicolas Gast Univ. Grenoble Alpes and Inria F-38000 Grenoble, France.
Abstract
We study stochastic approximation algorithms with Markovian noise and constant step-size We develop method based on infinitesimal generator comparisons to study the bias of the algorithm, which is the expected difference between On -the value at iteration ń- and 0* -the unique equilibrium of the corresponding ODE. We show that, under some smoothness conditions, this bias Furthermore, we show that the time-averaged bias is equal to aV + O(a)), where V is constant characterized by a Lyapunov equation, showing that E [O,] 0 + V a O(a²), where On (1/n) > Og is the Polyak-Ruppert average. We also show that On converges with high probability around 0* + a... We illustrate how to combine this with Sechardson-Rombeee extrapolation to derive an iterative scheme with bias of order ((a²).
order (a)).
Introduction
Stochastic approximation (SA) is a widely used algorithmic paradigm to solve ixxed-point problems under noisy observations. While SA was introduced in the 1950s [30, 6]. it is still widely used today in many applications to solve optimization problems, or to implement machine learning or reinforcement learning algorithms [23, 5]. A typical SA is stochastic recurrence of the form
Oa+1 On + on (f(0,, X,)) Mn+1),
(1)
where On Rd is a vector of parameters, X,, and Ma+1 1 are sources of randomness, and on the step-size. The step-size might be decreasing to 0 grow can be fixed to small constant (in which case we simply call at.
The goal of running a SA algorithm is to obtain a sequence On that gets close to the root 6* of the function f(0) [0,, X) M 0J. the expectation of the iterate (1), n goes to infinity. The SA procedure described in (1) models many algorithms that are used in machine learning, like first-order optimization and stochastic gradient descent [24, 16), and Q-learning or policy gradient algorithms [5, 35].
The theory of stochastic approximation has been studied extensively and is covered by lot of textbooks, e.g., [4, 8, 23]. This theory shows that the limit points of On as n grows are similar to can show that if all solutions of the ODE converge to 8*, then 0, gets close to 8* as n grows large (under technical conditions on f. the step size Ons and the noise Xn, M,+1). The asymptotic behavior of 0,, depends on the nature of the step-size: When the step-size an depends on n and converges to 0 as n goes to infinity, then O, generally converges almost surely 0*, When a, is kept constant and does not depend on n, then 8, will in general not converge to 8* but keeps oscillating around 8*, with fluctuation amplitudes of order O( Va). In this work, we focus on the latter case and propose method to quantify these fluctuations.
the limit points of the ODE + f(x) [3, 9]. In particular,
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

We consider a SA algorithm with Markovian noise. That is, 9₂ evolves as in (1) where the random variable X,, evolves a Markov chain that depends on on. and the random variable Ma+1 is Martingale difference sequence. One thing that sets this paper apart from others is that we allow the Markovian noise to be dependent on 0g. This is particularly valuable in reinforcement learning application such as Q-learning where the exploration policy might depend on 0n (this would for instance be the case for s-greedy). It known that when the step size a is constant, then the expectation of the iterates, EE [. does not converge to 0 [41, 20J. The goal of our paper is to provide a framework to characterize and compute this bias.
goes to infinity but has a bias
Our main contribution is to provide framework based on semi aamiggrouss to quantify the convergence rate of 8, to 8*. This framework is similar to Stein's 's method, that has been recently popularized to obtain accuracy results and refinement terms for fluid limits [10, 17, 18, 40]. It allows us to quantify the distance between the stochastic recurrence (1) and its deterministic counterpart (8) as a function of the distance between the infinitesimal generators of the stochastic and deterministic systems. By using this framework, we obtain two main results. Our first result (Theorem 1) states that, under smoothness conditions on f. there exists constant C > 0 such that for all small enough o:
lim sup IE [0,] 0* Ca
and
lim sup IE [(O, n-
0*) Co.
10
This guarantees that that the bias and variance of f, are of order at most a.
A classical way to reduce the variance of SA is to use Volyak-Ruppen tail averaging [28, 31], Le., to look the convergence of 0,, (1/m) Σx= On instead of 0₂- In this paper, show that, for the constant step-size case, the use of Polyak-Rupperi averaging removes the variance (i.e. lim, var [6,] 0), but not the bias: Theorem shows that there exists vector V and constant
C" > 0 such that:
limsup
IE [0,] 0" -V- Ca?.
This shows that the bias of the averaging is exactly of order a. We also show in Theorem 3 that 8,, converges in probability a point 8" + Va O(a²) as n goes to infinity.
We also provide numerical simulation on a synthetic example that illustrates how to combine the Polyak-Ruppert averaging with tichardson-Rombers extrapolation [19] construct a stochastic approximation algorithm whose bias is of order ((²)). This leads to an algorithm that enjoys both small bias and fast converge rate, compared to using time-step of order a².
Roadmap. The rest of the paper is organized as follows. We describe related work in Section 2. We introduce the model and give assumptions and notations in Section 3. We state the main results and provide numerical illustrations in Section 4. We give the main ingredients of the proofs in Section 5. The appendices contain technical lemmas and additional numerical examples.
2 Related work
Stochastic approximation algorithms were first introduced with decreasing step-size [30, 6]. Since these seminal papers, there has been considerable amount of work aiming at characterizing the asymptotic properties of SA, by relating the asymptotic behavior of 0, with the one of the ODE 0 = [(0) [3, 9J. These topics are today well covered by textbooks such as [4, 8, 23).
In this original theory, the goal was to show that On, is close to the behavior of an ODE but not necessarily to obtain tight rates of convergence. This lead to the development of a new line of research focussing non-asymptotic properties of SA [27]. This paper derives unified framework to study the rate of convergence of stochastic gradient descent by relating it to SA with decreasing step-size, and martingale noise (i.e., where the funccion does not depend on X₃ in (I)). This framework has been extended by a series papers for applications in reinforcement learning, see for instance [11, 15, 29, 26), still in the decreasing step-size case, with the goal of understanding the fluctuations of the algorithm around the equilibrium.
For the decreasing step size, the fluctuations of 0,, around 0* vanish as goes to infinity. This is not the case for constant step-size SA, for which understanding the magnitude of the fluctuations therefore important. To bound the fluctuations, part of the literature seeks to obtain bounds on the

---

mean squared error (MSE), E (0,, ] as a function of the problem's 's parameter and the step- size a. These papers show that the MSE is generally of order O(a), see for instance [33] for the case of linear model plus Markovian noise, or [13, 15, 14] for contractive stochastic approximations (with Markovian or martingale noise).
The case of constant-step size is also interesting because the 8n has bias that does not vanish as n goes to infinity. In particular, the Polyak-Ruppert averaging does not converge to t": generally lim,-z 8n 8t. It is shown in particular in [16, 20, 25, 32, 41, 42] that constant step-size SA has an asymptotic bias of order a, which shows that lim,--x: 8n = 8 + Va + O(a²). Some of these papers, and in particular [16, 20], show that this bias characterization can be coupled with a Richardson-Romber extrapolation to obtain a more accurate algorithm. In our paper, we also study the case of constant-step size SA with Markovian noise and use the same Polyak-Ruppert and Sethardson-Rombaee
analysis. One of the distinguishable property of our model is that we allow the evolution of the Markovian noise X, to depend on On. whereas most of the cited paper consider Xn has an external source of noise. This dependence is particularly interesting when studying asynchronous Q-learning algorithms [37, 36], for which the navigation policy often derived from the current values of the parameter (a popular example is to use an e-greedy policy).
A second distinguishable feature of our paper is the methodology that use. Our main tool is to relate the distance between the expectation of 0n and 0* as a distance between the infinitesimal generators of the stochastic recurrence (1) and of the deterministic recurrence (8). The method that we develop is tightly connected to Stein's 's method [34] and in particular with the line of work that use this method to obtain accuracy bounds for mean-field approximation [17, 22, 39, 40J. In particular, the start of our proof, which is to study a hybrid system composed of a stochastic and a deterministic recurrence in equation (9), can be seen as discrete-time version of what is termed
"classical trick" in [17, 22]. Apart from this difference between discrete and continuous time, one of the major features of our model is to have a Markovian noise. Our model can be viewed as a discrete- version of the recent paper [1]. Some of our results (like our Theorem 1) are analogous to the results of [1] but others (like Theorem 2) are different and require time-averaging, mostly because of the possible periodicity of the discrete-time Markov chains. Also, the model of the current paper slightly more general than the one of [1]. The fact that our methodology directly studies the expectation of fn makes it different from convergence results that use concentration equalities [12].
3 Model and preliminaries
3.1 Model and first assumptions
Throughout the paper (0n,Xx))200 is discrete-time stochastic process adapted to a filtration (Fa)azo- This stochastic process has two components of different nature. The first component that we call the parameter, is continuous and lives in compact subset θ IRd for each n: On E O c RR. The second component X lives in a finite set X, i.c., X. E X.
The evolution of 9 and X are coupled in the following way. The parameter @ evolves according to the recurrence equation given by (1). At every time-step n, the process X makes a Markovian transition according to a Markovian kernel K (0x). More precisely, for all x, x' X and 0 e θ:
P (Xx+1= = L' X. = I, On = 0, F.) P (Xn+1 = x' Xn = I, On = 0) =: Kzz( (0). (2)
To obtain our results, we will make the following assumptions:
(A1) The process M is a martingale difference sequence (that is: for all n: E[M Fr] 0) and its conditional covariance is E [Maa+1MM++ F.l assume that E M Fn A X,+1] = R(O,, X,, X,+1).
== Q(0n.x,)) Moreover, we
(A2) The functions f. K, Q and R are four times differentiable in 0.
(A3) For any given 0 e O, the matrix K(6) is unichain'.
In addition to these three assumptions, we later add an assumption (A4) about the stability of the ODE around its fixed point. We do not state this assumption here as it needs extra definitions.
We call a probability matrix unichain if the corresponding Markov chain has single recurrent class and, possibly, some transient states.
3

---

3.2 Averaged values, average ODE and stability assumption
Assumption (A3) implies that a Markov chain with kernel K(#) has unique stationary measure (0)), and we denote by (0) the stationary probability of x E X for such Markov chain. For any function g defined on X, we call g its averaged version, i.e., the function that associates to 0 E θ the value g(0), defined as:
7(0) = Σ (()))) MEX
(3)
It is shown in [1, Lemma 4], that under Assumption (A3), for each 0 E O the kernel (()) has unique stationary distribution =0). The value g(0) is equal to E [g(0, X)] where X is distributed according to the stationary distribution associated to K()).
Following our notation introduced in (3). we denote by f the averaged version of f. By II, Lemma 4], the function 0 - π (0) is twice differentiable under assumptions (A2) and (A3), which implies that the function f is also twice differentiable. This implies, for an initial (()) 0, the ODE à f(O) has a unique local solution, and we denote the value of this solution at time by (0). In order to prove this result, we will need that this ODE has unique fixed point to which all trajectories converge and that this fixed point is an exponentially stable attractor. This is summarized in the following asusmption:
(A4) There exists 0* such that for any 0, the solution of the ODE à f(() is defined for all t > O and converges to 0*: lim (f) = H for all A e O. Moreover, the derivative of f at 0* is Hurwitz (i.e., the real parts of all of its eigenvalues are negative).
By classical results the stability of ODES, this assumption implies that the convergence to 8* occurs exponentially fast, that is, there exists a, b > O such that for all f E O: (())(0) - 8" < (0 ae-
0+| To prove that, one can use [21, Theorem 4.13), that shows that 0 an exponen- be |@ g*1
neighborhood A of 8*, because Of*(0) is Hurwitz. Then, as θ is compact, there exists T such that (r( e W for all
tially stable point of the ODE, Le.. (l)) 8*| & a'e-be
0 E O The result then follows by choosing a = a' T supsee |00 - 0*| 101/ supeEN 110
0*|
3.3 Discussion on the assumptions and limits
Most of the assumptions used the paper are classical when studying stochastic approximation algorithms with Markovian noise. In this section, we discuss the limits of each assumption (from the most classical one to the most original one). Assumption (A3) is necessary to define the notion of average dynamics [(0) and is therefore present in virtually all papers about Markovian noise stochastic approximation. The originality of our assumption that we allow the transition kernel to depend on O. For assumption (A1), we add to the classical result the existence of co-variance matrix Q, which is needed as it appears in the expression of V. Assumption (A4) imposes that the stochastic approximation has unique exponentially stable attractor. Our results could probably be adapted to a model with multiple attractors (by using large deviation techniques similar to the one of [2, 38] for two time-scale setting ours) but this would be another paper.
One important assumption we make that 0 lives in a compact set + The bounded condition on θ simplifies greatly the proofs because it allows us to use uniform bounds that do not depend on 0 (for instance, the identity function h())) 0 is bounded thanks to this assumption. Similarly, the time taken by the solution of the ODE de (f) to reach 0* is also uniformly bounded independently on 0). This assumption could be relaxed by imposing high probability bounds (for instance, a large deviation result like [2] that would guarantee that 0, stays close to 0*), bound on the higher- order moment or exponential moments of 0n. We left this result for future work as it would greatly impact the readability of the proofs.
The most questionable of our assumption is Assumption (A2) that imposes that all parameters of the problem are four times differentiable in 8. While this assumption might seem as technical, the fact that the parameters are twice differentiable is crucial in our analysis. In particular, the constant V does depend on the first two derivatives of the function f. In general, if the parameters of the systems are not differentiable, then the hias will not be of order O(a) but of order O(va). Treating con-differentiable ff would need completely different methodology. Our assumption of having

---

four times differentiable functions and not just twice has two reasons: it guarantees that the error +V]] O(a²). and it simplifies the proof by allowing us to reuse Theorem obtain the bound O(a²) Theorem We believe that if we only impose twice differentiability. this error would be o(ax) (and in fact probably a as long as all derivatives are Lipschitz-continuuus).
0 -0* +
3.4 Notations
Recall that θ is a compact subset of Rd We suppose that it is equipped with a norm |-||-- For a function h : 3 - R, where & C Re we denote by [h]] supeeg [[](e)]] the supremum of this function. If E & is denoted by Dih(e). It is multi-linear map and we denote by D'h(e)a its value applied to (a,...,a) a) for a given E Rd We denote by D'A the operator norm of its ith derivative, defined as | = suPEEE ( |Dih(e)aS)|]/ [|all" By Taylor remainder theorem, for all e E E and _d" we have: /[(e + -) -- Di
times differentiable. we denote by D'h its ith derivative. Its value evaluated in
< | ||a]].
D* the maximum of the norm of the first ith deriva- tives of h. We denote by I)) the set of functions whose first derivatives are bounded and by C (E, IR) the set of functions whose first i derivatives are bounded by 1: || | & 1. As X' is discrete set, the above notions extend functions h X R. For such a function, by abuse of notation, we call hh the ith derivative with respect to the continuous variable only.
We define by | max([b]] , maxjss
In the paper, the value at time of the solution of the ODE = f(O) starting in 0 is denoted by (0). We will introduce later a quantity fr, that corresponds to a Euler discretization of the ODE with constant step-size a. To lighten notations, we will omit the dependence on in the notation op but should be clear that o depends on a. To help distinguishing between the solutions of the the ODE o and the discrete-time recurrence Pa. we will reserve the index t for a continuous time variable and the indices n, k or N for discrete-time indices.
To ease notations in some part of the proofs, we will sometimes use big-O notations, like O(1) or (a). When using this, we allow the hidden constants to depends on all parameters of the problems defined in Assumptions (A1) to (A4) but they cannot depend on varying quantities likes an index k n or a or norm of functions, like |g]| or [[b]] that are introduced in the proofs. Note that in all of our lemmas, we always consider functions whose norm is bounded by 1. This can, of course. be readily extended to functions not bounded by by adding an extra factor like [ We avoid doing this to lighten the notations.
4 Main results and illustrations
This section presents the main theorems and illustrate their consequence. The proof of the theorems are postponed to the next Section 5,
4.1 Theoretical results
Our first result is Theorem 1 that shows that the expected value of 0, is at distance at most O(a) of the solution of the ODE. This shows that the bias of stochastic approximation of order a with respect to the ODE.
Theorem 1. Assume (A4). Then, there exists constant C and og such that for all n, a & on and all h E (O,RR:
IE (O..) Mi(d (0o))] & aC.
Note that the bound of Theorem is valid independently of n. As we will see in the proof, this a consequence of Assumption (A4). Without the latter assumption, one would naturally obtain constant C that grows exponentially with n. As does not depend on time, a direct consequence of Theorem I is to show that the asymptotic bias of 0, is of order O(a) goes to infinity, that is:
lim sup E [h( h(0*)) ) & aC.
(4)
n=
5

---

Our second result is Theorem 2, that shows that the inequality of (4) is essentially an equality. This theorem provides an asymptotic expansion of the bias term in a.
Theorem 2. Assume (A1). Then, there exists a constant C" 0 and ag such that for all a & ao and h C% R)):
lim sup 70=+00
E [[((6w] -((0))))((6))))))))))))))))))))) aV & a²C'
(5)
An important difference between Theorem and 2 is that the former studies the convergence of the iterates On whereas the latter provides refinement term for the average of the iterates, i.e., On := v E [Ox]. by showing that O,, is essentially equal to (((x))) plus a bias term Va. One may wonder if Theorem 2 would be true for the (non-averaged) iterates 0z- The answer no and a counter-exampe example is provided in Appendix A. This example illustrates that when the Markovian component Xn can be periodic, the (aa) term of E [0,.] does not necessarily stabilize a constant V but can be periodic as well.
Theorem 2 concerns the convergence of the expectation of 6, but not the value of 6,, itself. As we will see in Section 5, this is mostly due to our proof techniques that works with generators and therefore is most suitable obtain precise convergence results for the expectation. In fact, will prove in Section B.2 that we can obtain high-probability convergence result as an almost-direct consequence of Theorem 2, as expressed by the following Theorem.
Theorem 3. Assume (A1)-(A4). Then, there exists constant C" 0 and oig such that for all
a & Og:
lim P (00, (0* + aV)l > C²aa 11 11-000
This result is illustrated on a synthetic example whose parameters are given in Appendix A.2, and for which 8* = 1. We run the stochastic approximation algorithm for various values of a and report the results Figure 1. In all cases, we use the same source of randomness (the values of the Markov chain X, and of the the Martingale noise Mn+1 are the same for all trajectories). We plot sample trajectory of fn. 0n. and 8n/2.0 d as:
12
0 m2/2:n =
OR.
2
11(n22|+1
for (0.001/4, 0.001/8, /8, 0.001/16) (more values of displayed in Appendix A). We observe that if O, is quite noisy, the Polyak-Rupper Ruppert averaging 0, or 0 are much closer to 6* 1, which is a clear advantage for 0//2... in terms of rate of convergence, especially for small values of a.
6.
0.9
50000 100000
40000 GOOD0
63000
(a) 0.0025 (=0.01/4)
(b) 0.00125 (=0.01/8)
(c) 0.000625 (=0.01/1)
Figure 1: Comparison of 0.. 0, and 0,, 0n/2.n for various a.
4.2 The value extrapolation: Illustration of Theorem 2 and
As we will see in the proof, the constant V of Theorem 2 can be expressed as a function of the problem's parameters, which allows one to construct quantity 0* + V that is tight approximation
Note that if theoretical results presented for o.., they be readily extended to 0./2.n.

---

10a
10a
20
80
28
g/0001251
(logscale)
10-1
10
Error
=.002
2- 0.00
10-2
0.0025
10
0.00125
0.000625
theoretical emror
20000
40000
60DDO
BOOOD
100000
20000
40000
60000
80000
100000
(a) Error 0n./2. 0+
(b) Error of the extrapolation (6).
Figure 2: Illustration of the error of 6, NV -nー 0g for various values of a 0.02 2 with
kE (0...5} .5 and of the error of the extrapolation (6) for a 0.01 and = 0.005.
of On. Yet, stochastic approximation algorithms are most used when one does not have access to the problem's parameter. Here, illustrate how step-sizes in order to obtain an algorithm that has both a fast convergence rate and high precision.
two algorithms with two different
Let 0(20) and ((a) be two trajectories of the stochastic recurrence (1) each with respective step- size 2a and By Theorem 2, for large have:
g(2)) 8* 2Va + O(a²)
n/2m
g(0)
n/2mm 0+ Va + O(a²)
We see that we can suppress the term in 2Va and Va by using linear combination of ((2) g(a) n/2nn
n/2nn and
which leads to an equation that has distance to 8 that is of order O(a²):
20
g(2a) 8 O(a3).
(6)
n/2mm
n/2:n
To explore the benefit of using the extrapolation (6), we plot in Figure 2 the error of the averaged it- erate 0 |0./2n 8* and the error of the extrapolation (6) for various values of a 0.01 2-k, with
k (-1 4}. The parameters are the same as the one of Figure and the various as use the same source of randomness. As we expect by the statement of the theorems, the error /./2:n 8t is ap- proximately equal to Va (the stars on the right are theoretical values of limn-x0 0n/2n 0* )- On the right panel, we observe that 20(a) (a closer 0* than the corresponding 0(a) (the scale of the y-axis is the same for both panels). Note that even for n 10 the valus of a are still noisy.
5
Proof overview and generator method
5.1 Proof overview
The first idea of our proof is to construct new random variables (f)).)) that corresponds system where we apply the stochastic recurrence (1) for steps and then apply the deterministic recurrence (8) up time n. By introducing these new variables and comparing their expectation for k and l + 1, we reduce our problem to a comparison of the generators the stochastic and of the deterministic system. This step is done in Section 5.2. In an independent lemma, we use Assumption (A4) to show that the derivatives of the function you converge exponentially fast to 0 as goes to infinity. This leads Lemma 6 whose proof is technical and postponed Section C.
Once these two basic points are obtained, we will use them to prove Proposition which shows that the expectation of 0, is close to the solution of the deterministic ODE. More precisely, this
We only plot the of 0.//... because it has the same limit 0, but converges faster.

---

proposition shows that there exists bounded sequence of constants V.(a) and constant C > 0 such that for all n E N: IB (O.).) K( (0n))] a VV & Ca². A main difficulty is to show that
Vi(a) is bounded. For that we will use Lemmas 7 and that use properties of the Poisson Equation (21) to show that if the functions Ik do not vary too much with k, then they can be replaced by their averaged versions:
Σ (b Xx)
Σ (0)) & C(1+
Σ
1 - 9k
Theorem is a direct consequence of Proposition 4. by using that Vi(a) are bounded.
The next step is to show that the time average versions of Vi(a), Vo(o) n Σx= v!(a) converges a
(as n goes to infinity) to term Va(a), Here, the main technical difficulty is to obtain refinement of the averaging property of (7), which is done in Lemmas 9 and 10. We then use Theorem and Lemma 11 to show that V(a) V+ O(a) where V is given in Proposition This gives Theorem 2. As side-product, Lemma 11 also shows that the constant V can be computed by solving linear system. The high-probability bound (Theorem 3) a consequence Theorem 2.
The proof structure is illustrated in Figure 3 that shows the dependencies between the lemmas.
Exponential decay of (d0):
Generator method (Section 5.2)
as n grows (Lemma 6)
Telescopic sums (Lemma 7)
Poisson Equation and averaging (Lemma 8)
Derivation of V( (Proposition 4)
Bias is ((a) (Theorem 1)
Bias is Va + O (Theorem 2)
Refined averaging (Lemmas 9 and 10)
lima- & V
(Proposition 5)
V is the solution of a linear system (Lemma 11)
High probability bound (Theorem 3)
Figure 3: Overview of the proof. The dashed rectangles indicate the lemmas that are proven in
Appendix
5.2 Deterministic recurrence and comparison of generators
To compare the stochastic variable 02 and the solution of the ODE à = f(0), we introduce deter- ministic recurrence equation, that is first-order discretization of the ODE. This recurrence equation obtained by replacing the sources of randomness of (1) by their expectation. The stochastic ap- proximation (1) contains two sources of randomness: Mn+1 and X,, In our analysis, we will use a deterministic counterpart of (1) that corresponds to setting the noise Mn+1 to and using f(0) instead of f(On, X.). More precisely, for an initial value 0 E θ and & e Z+, we define ynu (f) as:
1 = (.. of ((),
(8)
with the convention that (0) = 0.
Let : e - IR an arbitrary function. By using the definition of the deterministic recurrence, for any le E {0. (0...n), n.., we introduce the variable
kn = E [((
The quantity 2n,k the expected value of recurrence time n if one starts by applying the stochastic recurrence for the first i steps and then the deterministic recurrence for the remaining n-k

---

steps. Our proof method consists in obtaining precise bounds on the difference E [0x]] - E/ P (f))] By using the notation A. this quantity is equal to 2n.n 2n,0- To obtain bound on this quantity, we will use trick, that essentially consists in comparing 2n,k+1 2n,k. This quantity is simpler to analyze because the only modification between the two is to replace one stochastic transition by one deterministic transition. We can then recover the original bound by using that:
E [0.] (0n) Zn.n 0n.0
kn,
An,k.
(10)
2-0
This method is illustrated in Figure 4 on a synthetic example whose parameters are given in Ap- pendix A.3. In the right panel, plot functions (for different values of that are equal to 6 for k & n and to (0k) for k > n.
Gr.. k- 2x-2 lorke 100
12-
1.2
1.0
0.8
0.6
0.5
02-
0.2
0.0
50
150
175
200
25
100
125
175
200
(a) Stochastic vs deterministic recurrences
(b) Impact of changing & in 9pn (0%)
Figure 4: Illustration of the behavior of 0n. Pr (f)) and (f%x)
5.3 Derivation of (a) and of V by comparing the generators
Using the above notations, we are now ready to prove the first proposition.
Proposition 4. Assume (AI) (A4)) Then, there exists a constant C O and org such that for all n, & og and all h C3 R):
E [l(O.)) - (()nn(())))) aV/(a) & Ca?
where the quantity V((a) is given by:
12
v(a)= = D(h F (o-)))))) ((X(()
(2 o pn- ((S(O,, Xx) - f(xx)) + Q(0,, x+))
Moreover, V.(a) is bounded independently of a and n.
Proof. Following the definition of the stochastic and deterministic recurrences. the difference kn, 2n,k+1 that appears (10) is equal
Zn
Zn,k
((xp)-)(00s) - h1
T.. h Pn- (0x + a ()(()))
ho - (0, aff Xx) + Mc+1))]
(11)
Rdd - thrice differentiable function whose third derivative is bounded by | by using a Taylor expansion, we have that g( a) ((x+b) = (g(x)(a-b)) b))+ D2 (=)g()((aa))()))))))) + R. where R. is remainder term that is smaller than E ||a 3/3. In our proof, this Taylor
:

---

expansion with the function ho Pn-(n(++ O2 a a(f(Os. Mx+1) and b = af((k))
Applying this to (11) shows that
a² kn, Zn,k aA Br, Ri,ks
(12)
where An, and Br,k are equal to
An, := 1 Bn, == [D2 ( (
Xa) M f(Xx))] X&) + M6+1 f(xx))
and R is a remainder term.
By assumption (A1), the conditional expectation and variance of the martingale term are equal to Q(0,, Xx). By using the total law of expectation, this [M++1] Fi] and E 4+1 Fs [ shows that A,, and &,, can be simplified as:
An,k = E D(h Pn- (f,),,
BR E [D o (n- ((f(O,, - f(Xx)) + Q(O,, X.))]
By definition, (i(0) En=o (An, + aBn,k/ 2). Hence, combining this with (10) shows that
E [h(0m) - 1a (0o)) = V((a) + Σ RA,k-
To complete the proof, it remains to be shown that there exists constant such that Σk=o Rmnk & Ca and that Vy(a) is bounded independently of a and n. There are three terms, corresponding to R. B, and 2k=1 An,
Case of R. In Lemma 6, we show that the norm of the derivatives of h a Pa-k are smaller than cie (x2 As the derivatives of h are bounded by 1, this implies there exists e independent of a and n such that [ pn-x)] & ce -22a(nnk)) Hence, there exists d' > 0 such that:
Σ kl & c'o
e c2a(n-k) & da Σ
czak & desa?.
k-0
Case of B. The proof that Σx=1 aBn,k is bounded independently of n and a is similar since the factor a cancels out with the factor 1/a that comes out of Σk= -2oak
Case of A Showing that Σ An,k is bounded independently of and a is more subtle and uses the fact that f is the "averaged" version of f with respect to the transition kernel K. The proof of this is a consequence of the first point of Lemma that is stated Section
The proof of the main results is then consequence of the next proposition, whose proof is given in Appendix B. This proposition shows that the Cesaro limit of Vi(a) approximately equal to a term V that does not depend on plus a term of order ((a).
Proposition 5. Assume (A44, Then, there exist constant C > 0 and Okp > such that for all C (), there exists vector V such that for all n, a S ooo
V(aa -v|= C(a 1
na
where Vila) == n ER (aa with ((() as in Proposition 4.
6 Conclusion / discussion
In this paper, we presented an analysis of the bias of constant-step size algorithms with Markov noise. We developed novel technic, based on generator comparison, that allows to obtain a very fine comparison between the expectation of the stochastic trajectory and the value of its determin- istic counterpart. This methodology is quite generic and we believe that it could easily be adapted obtain more general results. We are in particularly targeting: relaxing the bounded of O and obtaining non-asymptotic results.
10

---

7 Acknowledgements
The authors would like to thank the three anonymous reviewers for their insightful comments about the paper. This work was supported by the ANR (Agence National de la Recherche), via the project REFINO (ANR-19-CE23-0015),
References
[1] Sebastian Allmeier and Nicolas Gast. Bias and refinement of multiscale mean field models. Proceedings of the ACM Measurement and Analysis of Computing Systems, 7(1):1-29, 2023.
[2] Waiss Azizian, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. What is the long-run distribution of stochastic gradient descent? large deviations analysis. arXiv preprint arXiv:2406.099 092444,,, 2024.
[3] Michel Benaïm. Dynamics of stochastic approximation algorithms. In Seminaire de proba- bilites XXXIII. pages 1-68. Springer. 2006.
[4] Albert Benveniste, Michel Métivier, and Pierre Priouret. Adaptive algorithms and stochastic approximations, volume 22. Springer Science & Business Media, 2012.
[5] Dimitri Bertsekas. Reinforcement learning and optimal control, volume 1. Athena Scientific, 2019.
[6] Julius R Blum. Approximation methods which converge with probability one. The Annals of Mathematical Statistics, pages 382-386, 1954.
[7] Nicoletta Bof, Ruggero Carli, and Luca Schenato. Lyapunov theory for discrete time systems. arXiv preprint 1809:0880005220 2018
[8] Vivek S Borkar. Stochastic approximation: a ddnamiccal systems viewpoint, volume 48. Springer, 2009.
[9] Vivek S Borkar and Sean P Meyn. The ode method for convergence of stochastic approxima- tion and reinforcement learning, SIAM Journal on Control and Optimization, 38(2)44474469 2000.
[10] Anton Braverman, JG Dai, and Xiao Fang. High-order steady-state diffusion approximations. Operations Research, 72(2):004-616 2024.
[11] Siddharth Chandak, Vivek S Borkar, and Parth Dodhia. Concentration of contractive stochastic
approximation and reinforcement learning. Stochastic Systems, 12(4):411-43) 2022.
[12] Hao Chen, Abhishek Gupta, Yin Sun, and Ness Shroff. Hoeffding's ' inequality for markov chains under generalized concentrability condition. arXiv preprint arXiv:2310.029411 2023.
[13) Zaiwei Chen, Siva T Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam. A Iyapunov theory for sinite-sample guarantees of markovian stochastic approximation. Operations Re- search, 2023.
[14] Zaiwei Chen, Siva Theja Maguluri, and Martin Zubeldia. Concentration of contractive stochas- tic approximation: Additive and multiplicative noise. arXiv preprint arXiv:2303. 15740, 2023.
[15] Zaiwei Chen, Sheng Zhang, Thinh T Doan, John-Paul Clarke, and Siva Theja Maguluri. Finite-sample analysis of nonlinear stochastic approximation with applications in reinforce- ment learning. Automatica, 146: 10623, 2022.
[16] 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):pp. 1348-1382, 2020.
[17] Nicolas Gast, Expected values estimated via mean-field approximation are 1/n-accurate. Pro- ceedings of the ACM on Measurement and Analysis of Computing Systems, 1(1):1-26, 2017.
[18] Nicolas Gast and Benny Van Houdt. A refined mean field approximation. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(2):1-28, 2017.
[19] Francis Begnaud Hildebrand. Introduction numerical analysis. Courier Corporation, 1987.

---

[20] Dongyan Huo, Yudong Chen, and Qiaomin Xie. Bias and extrapolation in markovian linear stochastic approximation with constant stepsizes. In Abstract Proceedings of the 2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pages 81 81-82, 2023.
[21] Hassan K Khalil, Nonlinear systems. Prentice Hall, Upper Saddle River, N.J., 2002.
[22] Vassili N. Kolokoltsov, Jiajie Li, and Wei Yang. Mean Field Games and Nonlinear Markov Processes. arXiv: 111..374, April 2012.
[23] H. Kushner and G.G. Yin. Stochastic Approximation and Recursive Algorithms and Applica- lions. Stochastic Modelling and Applied Probability. Springer New York, 2003.
[24] Guanghui Lan. First-order and stochastic optimization methods for machine learning, vol- ume 1. Springer, 2020.
[25] Caio Kalil Lauand and Sean Meyn. The curse of memory in stochastic approximation. In 2023 62nd IEEE Conference on Decision and Control (CDC), pages 7803-7809. IEEE, 2023.
[26] Wenlong Mou, Ashwin Pananjady, Martin Wainwright, and Peter L Bartlett Optimal and instance-dependent guarantees for markovian linear stochastic approximation. arXiv preprint 12. 2021.
[27] Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algo- rithms for machine learning. Advances in neural information processing systems, 24, 2011.
[28] Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal control and optimization, 30(4):838 855, 1992.
[29]
Guannan Qu and Adam Wierman. Finite-time analysis of asynchronous stochastic approxima- tion and q-learning. In Conference on Learning Theory, pages 3185-3205. PMI.R, 2020.
[30] Herbert Robbins and Sutton Monro. A stochastic approximation method, The annals of math- ematical statistics, pages 400-407, 1951.
[31] David Ruppert. Efficient estimations from a slowly convergent robbins monro process. Tech- nical report, Cornell University Operations Research and Industrial Engineering, 1988.
[32] Marina Sheshukova, Denis Belomestny, Alain Durmus, Eric Moulines, Alexey Naumov, and Sergey Samsonov. Nonasymptotic analysis of stochastic gradient descent with the richardson- romberg extrapolation. arXiv preprint arXiv:2410.8 106, 2024.
[33] Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation andtd learning. In Conference on Learning Theory, pages 2803-2830. PMLR, 2019.
[34] Charles Stein. Approximate computation of expectations. Lecture Motes-Monograph Series, 7:i-164, 1986.
[35] Richard Sutton and Andrew G Barto. Reinforcement learning; An introduction. MIT press, 2018.
[36] John N Tsitsiklis. Asynchronous stochastic approximation and q-learming. Machine learning, 16:185-202, 1994.
[37] Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8:279-292, 1992.
[38] Sarath Yasodharan and Rajesh Sundaresan. Large deviations of mean-field interacting particle systems in a fast varying environment. The Annals of Applied Probability, 3263):166611704 2022.
[39] Lei Ying. On the approximation error of mean-field models. In Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science, pages 285-297. ACM, 2016
[40] Lei Ying. Stein's 's method for mean field approximations in light and heavy traffic regimes. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(1): 2017.
[41] Lu Yu, Krishnakumar Balasubramanian, Stanislav Volgushev, and Murat A Erdogdu. An anal- ysis of constant step size sgd in the non-convex regime: Asymptotic normality and bias. Ad- vances in Neural Information Processing Systems, 34:4234-422 4248, 2021.
[42] Yixuan Zhang and Qiaomin Xie. Constant stepsize g-learning: Distributional convergence, bias and extrapolation. arXiv preprint arXiv:2401. 13884, 2024.
12

---

Appendix
A Additional numerical results
A.1
Reproducibility
All parameters given in this section should suffice to reproduce all figures. The total computation time to obtain all figures the paper does not exceeds a few minutes (on a 2018 laptop, imple- mentation being done in Fython/NumpyMMpplotiii to reproduce the paper (including latex, code to rum the simulations and code to plot the figures) is available at https: / //gtttbt..//////////////. cww.coo//aaooaoo conn/gaat//pant wwptttppppr__ae ppaperbbass
To ensure reproducibility, the code necessary
A.2 Parameters for the example of Figure and Figure
For Figure and 2, the state space of the Markovian part is X' = {0, 1}, and the transition matrix is
s)n cos(0)2) cos 0)2 (0)
(())
The drift is f(6,x) =9 - 2r. The martingale noise M,+1 is sequence of i.i.d. random variables
with (Ma+1* = F.)) = [M,+ = -1 Fa) 0.5. One can show that
The initial
value of the algorithm is set to Pu X. = 0.
In Figure 5, we complete the results of Figure by showing more values of a. We observe that in all cases, the averaged values 6n and 0n/2:n are much close to 0* = 1 than the original 0n that is very noisy. This explain why using a Polyak-Ruppert averaging is important, Also, if for large values of (0.02, 0.01, 0.005). the two quantities 0n and 0,/2:n have similar behavior, the situation is quite different when gets smaller. In the latter case, the convergence of 6./2mn is much faster than the one of O, because of the transient behavior of 0₂ the beginning. This is why use 0 n//on in our simulations.
a=
2= 0.01
0= 0.005
2.0
18
3.8
18-
1.6
1.6
1.6
1.0
1.0
1.0
0.8
0.8
0.8
8.6
20000
40000
8cčna
sco0o 1000c0
20c0n 40č0o enooe nodco 1000cn
20áco 43000 econa noázo 1oraco
o= 0. 0.0025
ot 0.00125
am 0. 0.000625
2.0
2.0
2.0
1.8
1.8
8.
1.8
1.6
Aup
3.6
0gg
1.2
1.0
1.0
1.-
0.8
0.8
0.8
0.8
20000 40000 Scc0O 50000 100000
20000 40000 69006 Bo0co 100000
20000 49000 60000 80000 190000
Figure 5: Behavior of 0,, G, and 0,,2.n for various values of a. All y-axis have the same scale.
13

---

A.3 Parameters for Figure
For Figure 4, the state space of the Markovian part X =0, and the transition matrix is
0.5
0.5
((0)
0.5
0.5
The drift is f(0,z) 1 (1 0)x. The initial state 0o Xo and there is no martingale noise". The step-size is set to a = 0.05.
A.4 Why is Theorem for 0, and Theorem and for 0,,
Note that compared (4) of Theorem 1, the result of (5) in Theorem 2 is stated for the averaged iterates Σ E [On] and directly for 0n. In fact, there are many cases for which (5) is also valid for 8n. In particular, if IE [h(6,.) converges goes to infinity, then one necessarily has:
lim sup E [[(0,)] h(0*) aVI & a²C'. n-+
This is for instance the case if (0,, Xn)) ) is an ergodic Markov chain. Yet. there are cases for which the result of (5) only holds for the averaged iterates. This occurs typically when X,, has a periodic behavior, in which case the averaged iterates eliminate eventual oscillations caused by periodic noise sequences. To illustrate this, we consider a one-dimensional model with f(0, .x) 2x 0 Xn+1 = 1 - X,, and Mn+1 = 0. This model satisfies all assumptions of the problems and 6* = 1. The initial conditions are set to 0g = 0.85, and Xo = O. The system is therefore deterministic. In
Figure we plot the trajectories of 6, and of g( & Σn 6, for two stepsize values: 0.05
and a 0.1. We observe that, as stated by Theorem from 0* One can also observe that (f,, 1)/a oscillates and does not converge as goes to infinity, contrary (0,. 1)/a that does converge (to here).
smaller is a, the closer lim, 0n
1.05
1.05
1.00
0.95
8,, 0.1
e... 0.05
0.90
8,, a-
6... a 0.05
Equilibirum 6"
Equilibirum Ø"
25
50
75
100
125
150
25
75
100
125
150
(a)
0.1
(b)
0.05
Figure 6: Example model with a periodic X,, illustrating the necessity of averaging the iterates.
B Proof of the main results
B.1 Proof of Proposition
In this section, we prove Proposition that states, that under((A)-(AA)) there exist a constant and og such that for all h (5, R), there exists vector V such that for all n, & ag:
v C(a +
where V(aa = n ER ((a) with v(() as in Proposition
'Note that because of the form of the matrix K (0). the process X,, is memoryless. Hence, one could build the model with martingale noise instead of the variable X.
14

---

This proposition shows that the Cesaro limit of the constants Vi(a) defined in Proposition 4 converges to limit that equal to V + O(a)) In particular, this result implies that
n = h(00) + aV + O(a² +
E
h(O.)
no
Proof of Proposition S. Recall from the proof of Proposition 4 that Vi(a) Ek=o E [An, + a:B,,t/2.. We first treat the term sentially because it is multiplied by a factor a). g(0, X) = (f(0, X) f(X)) 02 Q(0, X) shows that:
Σr Bunk that is the easiest (es- Applying Lemma 8 to the function
n-
Σ B
Σ E ( Pn (n-((--)))0))0(00
k=0
Σ
B ( 0(1)
k-o
By applying Theorem 1, this shows that
50
lim Σ
[[Ban]]
Σ
D ppx (00)))))))0)))) 0(1),
(13)
where x(0) = Ezex T (U(0,)))
+ 2)).
The treatment of An, requires more work, and in particular one can show that > An, does not necessarily converge as goes to infinity". This is why we study the convergence of AN E ΣR=0 An, and not the one of An,k- By applying Lemma 10 with g f and then applying Theorem 1, it holds that Nim [N + am()")] & Ca, with m(0*) equal to
m(0*)=
Σ Σ D(D(h (0) (')) .x) + R(0", ,I, 2 n=0
(0*)
Note that apply Theorem need to be three times differentiable which is why need to be four times differentiable.
Let ((a)
al a D² (O+) + m((*)). By using Lemma 11, there exists vector V such that [V(a) V Co.
B.2 Proof of Theorem 3 Highh-robability bound)
Fix some i {1...d d} and let Y, (0,, 0* aV).. be the ith component of the vector where the constant V is the one defined in Proposition 5 when applied to the function h(0) - 8". By Proposition 4 and Proposition 5, there exists
0 such that for n large enough:
E Y & C(a²
an
is easy to modify the proofs of those propositions (by adding a conditioning on Funk and starting the summation at mK + 1) to show that for all K and for m large enough:
(m+1)K
1
Σ
E|y E|
Fmn]] & C(a²
1
K
aK
k=mK+1
Let Zm + +=x(m)) Yn- The above result shows that X.M Zn CM 1 is super- martingale. Moreover, θ is bounded, there exists C' > 0 (independent of C and a) such that Znn C(a² + ak) & C' (almost surely). Hence, by using Azuma-Hoeffin inequality, for all e:
P
1 Σ Zm > Cla² + ak a + m==1
E -
M
'This is illustrated by Figure
15

---

By setting K = E/ Ca², and taking the limit as M goes to infinity, this implies that:
M
lim M
Zm
2 3Ca² =0.
3Ca2)=0
M
By using that 1 1 Y2 (I...d):
Zm O(1MM), with M MM/K], it follows that for all 2m
lim P ((O, (0* + aV)); 3Caa) =0. n-000
symmetric proof shows that limm- P ((On - (0* aV)); & -3Co²²) = 0. The theorem then
follows by using union bound all i.
This shows that the constant of Theorem can be chosen C" 3C where C' the constant of Theorem 1. By choosing more carefully the values of K and E, this constant can be reduced to C" (1 5)C for all d > 0.
C Technical lemmas
This section contains the technical lemmas that are used in the proof of the main theorems. This section divided two parts. We first show in Lemma 6 that derivatives of yn are exponen- tially small as goes to infinity. Using this exponential convergence, we then prove Lemma 7 that provides bound for an almost telescopic sum that appears the proof of Lemma 8. The latter shows how to bound the difference between f0,,, X.) and f(,)) by using Poisson approach.
C.1 Exponential decay of the derivatives of PPx
The first lemma is the core of our analysis. It shows that if the ODE has unique attractor (as imposed by (A4)), then for a small enough, the derivatives of the discrete-time recurrence are exponentially small as n goes infinity.
Lemma Assume (A2)-(A4). There exist og > and constants C1 C22 C3 C4 >> such that for all < ag. i 2, and n,
00 (i)
2 - czan & c3/a.
(ii) For all h (O, the ith derivative of h pn satisfies:
| o pP) & cie cie
Proof. The proof of (ii) is just a comparison between sum and an integral. Indeed, as x e- is decreasing, one have:
e
2
dr
e
e2 dr
2
ae Czak
00
(k-1)a
This shows that:
e
1+
Σ
e
Ogakk
14
1
= (a + - )a.
1
C2
k-n
k-
This concludes the proof by setting C3 (og 1/02).
To prove (ii), let us first prove the result for the first derivative (i = 1). By Assumption (A4), all trajectories of the ODE 9 = 7 converge to the fixed point 8" and the Jacobian H := Df(0*) is Hurwitz. By classical results [7] on the discretization of ODE this implies that, for a small enough,
"o see why this true, one should remark that, because Hurwitz, there exists c and that for all a & Ctp the eigenvalues of + aH have modulus smaller than 1 ac. This implies that the recurrence equation l.+1 = 6, + a (0..) is exponentially stable around 6* The uniform bound for all 0 e comes from the fact that O is compact.
such
16

---

the discretization (f) converges exponentially fast to 8", that is: there exists > 0 and a, b such that for all a < ag and 9 E O: lp,,()) #* & ae -g Using this and the fact that is twice continuously differentiable in 0* implies the existence of a' such that:
Df(px H|| < a'e -aan and (I + aH) & ae
czan
(14)
Recall that the definition of fr in Equation (8) implies that ( (n( = of (0) with (P((0) Hence, as f is differentiable with respect its initial condition, by using the chain rule, the derivative of fn+1 exists and satisfies:
D (0) (0pn(0) = (D),,
(15)
To simplify notation, let use denote by Xa+1 == 1 (0) (the above equation is X,+1 X,, Df,,)(((()))) and let us compute" Xn+1(I aH) (m+1), By adding substracting the term Xn(II + aH) -", it holds that:
Xn+1 (I+1(I+all) +HH) (n+1) = +
X,, (x + Xn( + aH)
= -XnII-Xn([++ ( ( + X aH)
= =aX,(Df(e,(()) - H)
aH) + X, [I + aH) "
where we used (15) for the last line.
By using that the last term (1 + all) corresponds to the XI+1(I + all) - (n+1) where we replace + 1 by n, a direct induction shows that
XI+1 + all aI (1+1) Σ Xx(Df(px(0)) HI(1 + alf)
Multiplying this equation by (I + aH) implies that:
X = a (x((x((xx()) - H) + -H)
(16)
By using (15), and denoting In+1 |x+tIl= it holds that
In+1 & a
Iya'e a -oaak -zz((nk)) = a(a')² c2an
Tk-
(17)
To conclude, let Un+1 == a(aa)²)>)) 2
2n-1 Uae - with y/ Fo. It can be shown by induction on k:
thate,, & ecaak yk. Moreover, we have:
12 I[ + (elaa)2--czo k-1
On++ ala')"yne yn czan + Yn yn + a
-xam)
By using the concavity of the log, we have that:
log (1 a(a')e rank) Σ log(1 ala')2e-
h-1
2e czak
By using the point (i), the last quantity is bounded by some quantity d. This shows that x. de-ogan -gan
The proof of the higher derivatives (case > 2) are very similar to the proof for the first derivative i and we only give an overview. For the second derivative, differentiating (15) with respect to gives:
P - -0D
+ (DDp Dp.,()) D2 (())
We compute this quantity to solve (15) by using technique similar to the change of variable method.
17

---

This equation is very close to (15) with an additional term Zn == a a(Dpn D (0)) D2 (0)) Indeed, denoting by X (2),(0), one can reapply the steps used to obtain (16) and get instead:
X n+1 (X((D((x)O)) H) + ZT)(T + aH)
One can then use our result for the first derivative show that (D))()()) H) 2 < a rgal and obtain an equation similar to (17) but for T'+11 == DP)( The proof can be modified mutatis-mutandee for higher derivatives.
C.2 Bound on the almost-telescopit sum
In this section, we prove a lemma that we will later use the proof of Lemma This lemma concerns a summation that is cdmost-teleccopic: the first (18) is of the form Σx= uy (Ux+1 - 2%). If it would hold that ug Uk-1, then the sum would be telescopic and there would be no need for lemma. Here, we show that the difference ||ug ux-1| is small and use this to prove our result. In the second lemma, make second round of summation.
Lemma 7. Assume (AA). Then, there exists constant C and on such that for all a & on and all i e (1,2,3), 3). h (0, and g e C R),
I
D' pn- (0(0x+1, Xa+1) g(On. Xx))
C.
(18)
0
Proof. Let us denote uk
and u == g(Ok. Xs). The quantity (18) is equal to By shifting the indices of the sum (which corresponds discrete-time
E Ex uc(U++1 vx))
integration by part), we get:
n-1
uu(u 0k) =
Uk
Uk+1
Ug Vk
Σ
uk-12k
2k U/
(19)
4920 + = un 10a-11p. 12p
(uk-1 ug Uk-
(20)
As the norm g and h are bounded by 1l ugval and [ are bounded independently of
a. Hence, the result follows if we can show that n- [4-11 Ug is bounded regardless of a. To
show this, by adding and subtracting the term D (0(s) have:
fk- uk = D(ho Gn x)0x)((m D(h (00))
+ D(h pn-
D(h (n-
By Lemma 6, the function D(h Pp-+) is Lipschitz continuous with constant ce (x-Kk)oo, As the difference between 0g and 0x-1 of order a, this shows that the first line is bounded by d'ae d'ae-(n-kaan (n-k)acz, For the second line, the definition of the function PP- in (8) implies that for any 0:
( 9n- (0) = (f((n-((+1))0)))
This shows that difference between D kn and D(h pn (k+ is of order c" de (n (n-k)oce
The two facts combined imply that:
- uxl & (c' + c²)
Σ ae ca (d + d") Σ
ae -2ka ozka (c' + c" c33
18

---

C.3
Poisson equation and treatment of the averaging term
For given g equation if it satisfies
X' - IR, we say that the function Gg O X R is solution of the Poisson
Σ
(0, Go v)) -(0,x))-((0) g(0),
(21)
yEA
with g(0) = E (0) x) as before.
It is shown [1, Lemma that under assumption (A3), for each g. there exists such function Gg- Moreover, under the regularity assumption (A2), this same lemma shows that the function G can be chosen to be four times differentiable and that is derivatives satisfy | O gl)).
Lemma Assume (A1). Then, there exists constant C and oxp such that for all n,
a & oo and all i E (1,2,3). 3), h (O, RR) and E C2 (0, R):
n-
Σ R-O
IE
D'(h Pn (n-((+)))(O))) (0(0s, Xx) [(0) <C
(22)
Proof. To lighten the notations, we consider the case 1, the proof holds for i by replacing D(h o p) by Di(h o sp). By adding and subtracting some terms, the quantity (22) is equal to the
expectation of
D(h o pn-xx))((m) (000,, (1)0e, -x)) g(0n) + Gy(On, Xx) (0, XR+1)
(23)
R=
+ G Xx+1) ( Xx+1)
(24)
+ Gg(0 (0b,
(25)
We examine the three lines separately:
By using the fact that Xk+1 makes a Markovian transition (2), and by using the definition of GA(E, v), we get:
(0, Xn) Gy(Ok, Xx+1) FF] = Σ
(g Xx) (0x))
from which follows that the expectation of (23) is equal to zero.
To bound Equation (24), we use the definition (1) of f to implies that there exists constant C >> 0 Ouch that [0k+1 0u1 & Co. By using that Gy Lipschitz-continnous (see [1, Lemma 4]) and that the norm of the derivative of fn-k is bounded by eie -2 (Lemma 6), this shows that there exists e' < co such that:
x c'a
E
[ (n- (Gy( X Gy(OktI. X++1))Il
egka & csc'.
The fact that the expectation of (25) is bounded is direct consequence of Lemma applied with Gg and the fact that |DG Dgll)
This conclude the proof.
C.4 Refined treatment of the averaging term
The next two lemmas prove properties of the average sums that refine the analysis of Lemma 8. They are used study the term A, in the proof of Proposition 5.
19

---

Lemma 9. Assume (A4))A4), Then, there exists constant C' 0 and such that for all a & or::
VÉE C2 (O,R)
1
E Xt) - C( =(=
(26)
VEE (O,R):
1
[|((0, Xx) - -((0k) + am((+)) & <c n
a
(27)
k=
where m Lx, DG. x' (f(0,)) R(0,x,,))) Kz (0)
Proof. By applying the same trick as for (23)-(25) in the one of Lemma 8 but replacing Di Pn Pn-((x+1) by 1/n, the left-hand-side of (26) is equal to the expectation of
Σ Ge(O2, ((+1) - X Xet1)
Σ
(28)
O(xx DG,l) because DG,, bounded.
O(1) because sum is telescopie.
where there is no equivalent of (23) because we already use that the expectation of this term is O.
In (28), each element of the first sum is O(a)) by using Taylor expansion of G. and using that |DDG DEj). Hence the first term is of order ((a). The second sum is telescopic. As is
multiplied by 1/n, this leads to the term (L/n)) of (26). Combining both leads (26).
To obtain (27), we refine the analysis of the first term of (28). By using Taylor expansion on the function 8 - XX), the quantity Ge(OR, Xx+1) Ge(0++1 is equal to
(G, X (0x 1x+1) 1) + | 00++1 0x1
(29)
By definition, |10++1 0z1 is of order a
Let m00 = Ewex (GG((0,z'))((())) + R(0, x, K (0). By using the law of total expec-
tation,
EE L (0 = aB (O,, Xx+1) X&) + Mc+1)]
=- [E [E [DG Xx+1)(f(0R+ Xx) + Mx+1) Fs Xx+1] Fill
= =aaB [m[[ O2, Xx)]
By using (26) with the function m instead of f, we obtain that -ーー E [m( X2) m(x))] &
C(a + 1/n). This shows that the first term of (28) is equal to a = m(ak) plus term of order C(a² + a/n). As the term ((1nn) from the telescopic sum of the second term of (28) dominates the term a/n, this implies (27).
Lemma 10. Assume (AI) Then, there exists a constant C > and on such that for all n. ap h E C22 (G,R) and g C3 (O,
N n-1
N
o(ho pn (0-((+)) N НΣΣ
g(0x))
m0x) < $0 a Na
where the function mn is equal to
m(0) Σ Σ D(D(000.)011;0:-)))(0000 ((002x22)) 2'), (0)
M. X,Z'EX
20

---

Proof. Let us denote by 1k- (02) == D(h e (x-((++)) and let us study the sum S ==
N D n-1 -k-0 D(h Pn- (n-((+1))OO)) By reordering the sum, this is equal to:
N N
N-
N
(k+1)
Σ
Un (k)))) Xx) =
1
Σ Σ
Un (O)))
N
n=*++
k=
N-1
N-1
Σ un (0x)) Xx) n
Un (n(())g((p X2)
(30)
N
N
k=0
n=N
By Lemma 6, there exists CI, > such that |/u, ll & Cre Cpecnon, This shows that the second term of the previous sum (30) is bounded (in absolute value) by
(N
(31)
2
for suitable constant c' This term goes to when N goes to infinity.
To treat the first term of (30), we apply Lemma with the function ((0,X) = Σx Di (O))())(0 X) Im= Un (f)g(0)))))) ().
C.5
Characterization of
The next Lemma show how an approximate computable expression of the bias term V can be ob- tained. Recall that by definition, V dependent on yp with step-size a. The subsequently defined and computable expression V is resolves this dependence on and is further justified as it admits an accurate of order a with respect to V.
Lemma 11 (Approximate Computable Expression of V). Assume (A1) Define
= (D(0*))(HH))) (( (2)) W) + D²h((*)) W
(32)
with H = 50,
2i (0+) the Jacobien matrix of at 0*, H!!g) = 20,20;
ot.
(0*) ) is the second
derivative of J in 0* In the above notation, ( W = (Eg, n H1(2) Wi,k)i where W is
T
the unique solution the Sylvester equation H ((H)) +0 0 and where O and S are defined by
O G (0(00*x')))(() (')( ,0) + R(0", x,, xx,²1) K(8*) n (1* + g(0*),
(00",,,'')
(33)
S Σ (f(0*, xx) R(0* x, x,) DG, (0" K() )( 7
(34)
with g(0") = Σx T (0*) (
8(00)) =(0%, is defined in the proof of
Proposition 5.
There exists constant C > 0 and on such that for all op:
V - vioa| & Ca.
where V(a) = alLin D² (0))(0*)((0)) + m(0*)) is defined as in the proof of Proposi- tion 5.
Note that the constant V does not depend on
Proof. Using the definitions (33) and (34) for O and S respectively, and the definition of g and in the proof of Proposition 5, we can rewrite ((aa) as:
v(a) al Σ D(h (0)
Σ D² (0+h)
(35)
k
k=O
21

---

Using that (x((0)) = 0r yields the identity
v(a) =aDh(0*)
(0))
(36)
Σ - 0+a0)))0)))))) DD((0)00(<((0)
+ aDD(0*))
(37)
k=
where the first line corresponds to the first term of (35) and the second line to the second term of D*xpx (M(0*)DAApouu (2:
(35). The notations correspond to Dh(0*)
80, d0m.0, ) and denotes the sum
2h dep
over the element wise product between the matrices.
From hereon out, suppress the dependence of the therms l* in order ease the notation. As said before, is shown [1, Lemma 4], under assumptions (A2) and (A3), that Gy is computable and four times differentiable, which implies that the terms S and O are computable, Therefore, in the rest of the proof we are concerned with obtaining computable expressions for the terms
DoLODof
> D2 O.
(38)
k=0
We recall that by definition D+1 = 1 + (1), Using the chain rule, we have Dyp = D
(P--1) = (1 + ( D = (1 + (1) By assumption of exponential stability, ( is Hurwitz and thus, for small enough a, all its eigenvalues have negative real parts. This implies that for such a, ( + aH(W)= (a=H()))-11 This gives the first term Dh(0*) (H(U))
-'s of (32).
Define ((() as the second sum of (38) which is equal to
w(o) = OD
k=0
= Σ (I aHW) + ((
As (1)) is Hurwitz, W(a) well-defined for a small enough and is solution to the discrete-time Sylvester equation (I (zH("))((' aH())T- (( + aO 0. To obtain computable expression independent of we consider the corresponding continuous-time Sylvester equation
0 for which the Hurwitz property of (1)) ensures the existence of a unique solution W. By definition of the two Sylvester equations, we then have that W/a) = W + (1) ((H())) i.e., the difference between the two solutions is of order a. This gives the second term Dh(0*) D((0*)(II()) H2) (2). W of (32).
given by W ((H)))+++
For the last sum of (38), apply the chain rule and substitute Dip aH and D2 aH (2) to obtain the identity
Ōipk 06 m 20 i,mn
D2Pp
Σ (II (1+)) in YaH
a,be ((I + aH(W))) bmm ((I aHHP)) am
b.c
i,m
Therefore,
D2rg -0= Σ
Ōep
O Oz.k)=zI.dd
00
j.k
k
Σ
(I + ( (++oH")OO+++((0))
1-1
22

---

with H(2), (I+a (( Em. H ((I+ aHHOoo +
Consequently, for Σk= p² O the above yields
* (I+ (T+ k-
8 [I aHH) (I+ aH ( a(HW))
j= k=j
30 8
[1 + all al1 (1+ (O(+ a(
j=1k-0
(aH())
+(()))())))))))))
(aHl al aHl +0 (I+
-aHH)))a11 (T a ( (T+H0)))) ((H
- w(() + aC",
with C" = (1 (HO) + (H)) (( which is bounded by assumption. Using the previously discussed difference between W and W( we clude that (11))-11( W is approximate solution to Σt D& O with error of order a.
23

---

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 purpose of the paper is to obtain bounds the accuracy of constant
step-size stochastic approximation. This is directly reflected by the title and abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
fine to include aspirational goals as motivation as long as it 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 limits of the assumptions are discussed separate subsection 3.3.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specificattin, asymptotic approximations only holding locally). The au- thors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
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 i acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [es]]

---

Justification:
The proofs of the main results are given in the main body of the paper while some more technical lemmas are give the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
The paper does not contain important experimental results but only nu- merical illustrations of the theorems (with small synthetic examples). All parameters of the examples are provided in the appendix and the code of all simulation is available at https: htt//ggtttut com Saan//gast/paaee_Daee biapeerrbbas___eeeeeeeeeeeeeeeee wwwtthhtticaaaprrotttteeeeeeeeee Guidelines:
Justification:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can accomplished various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
also be provided via
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results way produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case thors are welcome to 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 (c.g., to registered users), but it should be possible for other researchers have some path to reproducing verifying the results.
25

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The paper is fully reproducible (code to produce simulation, figures and latex)
at sttps://githhe com/ngast/paageeeeeaaaaaaasss paper_biaa httrr_baaaa__scta_eeeee www.satttttttoo wttpssssohttttcaappoooooo wttpaaa.p.ppoooimiio22222222
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines pettpa://nips.coo cc/
wublice/uiide//odeSSiie www.ammiisiooooocicoi.. 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 including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.. cc/
wttpcccpppcccccccccccccccccccccc public/ heoollccguuieeee hwtp//uddes//eeeee SaaeeeesCoooeSbbbaa ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
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?
Question:
Answer: [NA]
Justification:
There is no dataset used.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
The paper does not contain numerical experiments but only small numerical illustrations of theorems.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
26

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative еπτor rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The numerical illustration are very limited (less than a few minutes of com- putation time in total). This mentioned in the text.
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 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 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //teurip///urip.... htt.o//icc/hhiccccccieeeeeeeee
Answer: [Yes]
Justification:
The paper is theoretical paper and its direct ethical implications seem lim-
ited.
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., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
The paper is a theoretical paper and there no direct broader impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
27

---

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 spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility 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: [Yes]
Justification:
There are no models or data released.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines restrictions to access the model or implementing safery filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we 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 the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: There is no significant code, data or model used.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI.
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.
28

---

If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswith thcode www.coo///ao/oo candsataeets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
There are no new assets released.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and sereenshots, applicable, well as details about compensation (if any)?
Question:
Answer: [NA]
Justification: Not applicable
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, 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 deseribe 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 the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Not applicable
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
29

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere 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.
30


Reviews:
[{"review_id": "kJ3zLaERd8", "reviewer": "Reviewer_xFdD", "summary": "The paper studies non-linear stochastic approximation scheme ($\\theta_n$) driven by a uniformly geometrically ergodic MC $(X_n)$. Moreover, it is allowed the evolution of the Markovian noise $X_n$ to depend on $\\theta_n$.  The authors study the asymptotic behaviour of the last iterate, Polyak-Ruppert and Richardson-Romberg procedures for differentiable test functions. The result generalizes recent result of 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):pp. 1348–1382, 2020.", "questions": "- I think it is better to give a definition of a unichain.\n- Is it possible to relax conditions of the theorems? For example, what will be if we reduce the number of derivatives in Th 2? Is it true that in this case one will obtain \\alpha^{3/2} in the remainder term? Is it possible to achieve this using the suggested technique?", "limitations": "-", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Novel technique based on infinitesimal generator comparison", "weaknesses": "- It would be good to provide non-asymptotic results rather than asymptotic\n- I think that the result of theorem 3 is very weak since it is obtained using Chebyshev’s inequality. Could you please comment on $\\alpha^{5/4}$ term?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4H50E2ahA7", "reviewer": "Reviewer_Mbpd", "summary": "This paper studies the asymptotic bias in non-linear stochastic approximation algorithms with Markovian noise and fixed step-size. Upon applying the averaging technique of Polyak and Ruppert, the authors identify that, in general, the bias is of the same order of the step-size. The main source of bias is characterized, and an extrapolation technique is employed so that bias is attenuated. Finally, a few numerical studies are presented for illustration of the theoretical contributions.", "questions": "- Is it possible to relax the assumption that the parameters remain within the compact set \\Theta with probability one?   It seems likely that the authors can obtain their results subject to a moment bound, which I believe is more realistic based upon standard SA stability theory.\n\n- One thing that sets this paper apart from others is that they allow Markovian noise that is parameter dependent.   This is extremely valuable in RL applications such as Q-learning (for example, epsilon-greedy policies induce such a model), and actor-critic methods.  Could the authors provide more discussion regarding applications in which the Markovian noise is parameter dependent?\n\n-Could the authors clarify whether the experiments display in Figure 1 (a) and (b) pertain to the same run? It is hard to identify the improvement between RR exploration and the regular algorithm for the choice of \\alpha =0.01. I encourage the authors to include sample paths for \\alpha =0.01 and \\alpha =0.005 instead of the \\alpha =0.0025 for visualization.", "limitations": "The authors discuss the limitations of their work and assumptions in section 3.3.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "I find the overall contribution of the paper to be very interesting. As far as the reviewer is aware, the characterization of bias for nonlinear SA with parameter dependent Markovian noise is novel and original. \n\nThe analysis seems sound. The reviewer did not have time to look over every single proof carefully, but haven't found egregious errors in the proofs revised.\n\nThe problem setup, assumptions and approach to analysis are clearly stated. The paper is well-written, but some polishing is needed.", "weaknesses": "In particular, there have been recent papers, achieving similar bias characterizations and higher order error bounds for stochastic approximation with Markovian noise (see for example [R1] and [R2] which both deal with linear recursions). The approach to analysis in [R2] is similar to the present paper in the sense that the bias characterization is also given in terms of solutions to Poisson's equations. Moreover, this is not the first time that Richardson-Romberg extrapolation is used for bias attenuation in stochastic approximation: it was previously proposed in [R1] to kill the dominant term of order O(\\alpha) just like the present paper.\n\nThe authors do cite [R1] in the present work, but the reviewer feels that a deeper discussion is needed on how the present paper improves upon [R1] and [R2]. I encourage the authors to include a citation on previous uses of this technique as well.\n\n\n[R1] Huo, Dongyan, Yudong Chen, and Qiaomin Xie. \"Bias and extrapolation in Markovian linear stochastic approximation with constant stepsizes.\" Abstract Proceedings of the 2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems. 2023.\n\n[R2] Lauand, Caio Kalil, and Sean Meyn. \"The curse of memory in stochastic approximation.\" 2023 62nd IEEE Conference on Decision and Control (CDC). IEEE, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "S2ZPbSppIQ", "reviewer": "Reviewer_Hzq1", "summary": "This paper studies stochastic approximation with constant stepsize and Markovian noise. The authors provide a characterization of the bias (i.e., the difference between the expectation of the iterate and the desired limit), show that Polyak-Ruppert averaging can help reduce the variance but not the bias, and numerically demonstrate that Richardson-Romberg extrapolation helps reduce the bias.", "questions": "Both theorems require $h$ to be uniformly bounded by a constant. This is not true even for $h(\\theta)=\\theta$, which corresponds to bounding the expectation of $\\theta_n$. Am I missing something?", "limitations": "The results are mostly asymptotic. A characterization of the stochastic approximation algorithm behavior for a finite $n$ would be preferred for practical purposes.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The writing is mostly clear and the proof is written with high quality. The result is an extension of [17,36] to the case where the Markov chain can have its transition probability matrix as a function of the stochastic iterate, which enables the authors to apply the results to RL algorithms with time-varying behavior policies (though the results are not formally presented in this paper). Overall, this is a strong theoretical work and the techniques developed in this work are quite novel.", "weaknesses": "(1) Assumption (A2) is relatively strong and difficult to verify in practice.\n\n(2) The authors claim that Assumption (A4) implies the global exponential stability of the ODE, but did not provide a reference for the claim. Also, the claim in lines 466-471 needs formal justification.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
The authors would like to thank all reviewers for their detailed and constructive reviews. All reviews are correct and suggest interesting improvements that will be invluded in the final version.

Most of the comments or questions are answered below each review.

Meta-review: This paper considers stochastic approximation (SA) under Markovian noise and constant step-size, which is commonly employed in practice. Authors rely on
the generator of the process to study the bias of SA algorithm, and derive its order
under smoothness conditions. Authors also provide bias orders for the Polyak averaged iterates, and extensions involving Richardson-Romberg extrapolation.


This paper was reviewed by three expert reviewers w/ the following Scores/Confidence: 5/3, 7/4, 5/4. I think the paper is studying an interesting topic and the results are relevant to NeurIPS community. The following concerns were brought up by the reviewers:

- The main results in this paper are asymptotic. The non-asymptotic versions should be clearly stated in discussion/conclusion section as future work.
  
- Better discussion connecting this work to the existing literature is needed.
  
- Authors should discuss how restrictive their conditions are.


Authors should carefully go over reviewers' suggestions and address any remaining concerns in their final revision. Based on the reviewers' suggestion, as well as my own assessment of the paper, I recommend including this paper to the NeurIPS 2024 program.
Decision: Accept (poster)