<?xml-model href='http://www.tei-c.org/release/xml/tei/custom/schema/relaxng/tei_all.rng' schematypens='http://relaxng.org/ns/structure/1.0'?><TEI xmlns="http://www.tei-c.org/ns/1.0">
	<teiHeader>
		<fileDesc>
			<titleStmt><title level='a'>Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive SA</title></titleStmt>
			<publicationStmt>
				<publisher>ACM SIGMETRICS Performance Evaluation Review, Volume 52, Issue 1</publisher>
				<date>06/11/2024</date>
			</publicationStmt>
			<sourceDesc>
				<bibl> 
					<idno type="par_id">10569489</idno>
					<idno type="doi">10.1145/3673660.3655076</idno>
					<title level='j'>ACM SIGMETRICS Performance Evaluation Review</title>
<idno>0163-5999</idno>
<biblScope unit="volume">52</biblScope>
<biblScope unit="issue">1</biblScope>					

					<author>Yixuan Zhang</author><author>Dongyan Lucy Huo</author><author>Yudong Chen</author><author>Qiaomin Xie</author>
				</bibl>
			</sourceDesc>
		</fileDesc>
		<profileDesc>
			<abstract><ab><![CDATA[<p>Motivated by Q-learning, we study nonsmooth contractive stochastic approximation (SA) with constant stepsize. We focus on two important classes of dynamics: 1) nonsmooth contractive SA with additive noise, and 2) synchronous and asynchronous Q-learning, which features both additive and multiplicative noise. For both dynamics, we establish weak convergence of the iterates to a stationary limit distribution in Wasserstein distance. Furthermore, we propose a prelimit coupling technique for establishing steady-state convergence and characterize the limit of the stationary distribution as the stepsize goes to zero. Using this result, we derive that the asymptotic bias of nonsmooth SA is proportional to the square root of the stepsize, which stands in sharp contrast to smooth SA. This bias characterization allows for the use of Richardson-Romberg extrapolation for bias reduction in nonsmooth SA.</p>]]></ab></abstract>
		</profileDesc>
	</teiHeader>
	<text><body xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink">
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1">Introduction</head><p>Stochastic Approximation (SA) is a fundamental algorithmic paradigm for solving fixed-point problems iteratively based on noisy observations. SA procedures have been widely used in many application domains, including reinforcement learning (RL), stochastic control and optimization <ref type="bibr">[Ber19,</ref><ref type="bibr">SB18,</ref><ref type="bibr">KY03,</ref><ref type="bibr">MB11]</ref>. A typical SA algorithm is of the form</p><p>where {w t } t&#8805;0 represent the noise sequence and &#945; &gt; 0 is a constant stepsize. The SA procedure (1) aims to approximately find the solution &#952; * to the fixed-point equation H(&#952; * ) = &#952; * , where H(&#8226;) := E w [ H(&#8226;, w)] is the expectation of the operator H(&#8226;, w) with respect to the noise. Equation (1) covers many popular algorithms, such as the prevalent stochastic gradient descent (SGD) algorithm for minimizing an objective function <ref type="bibr">[Lan20]</ref>, and variants of TD-learning algorithms for policy evaluation in RL <ref type="bibr">[SB18]</ref>.</p><p>In this work, we focus on nonsmooth contractive SA, where the operator H(&#8226;, w) may be nondifferentiable (in its first argument) and H(&#8226;) is a contractive mapping with respect to a norm &#8741; &#8226; &#8741; c . One prominent example of nonsmooth contractive SA is the celebrated Q-learning algorithm for optimal control in RL <ref type="bibr">[WD92]</ref>, where H corresponds to the noisy optimal Bellman operator involving a max function. Other common nonsmooth mappings include the largest eigenvalue of a matrix, &#8467; 1 -norm regularized functions, and their composition with smooth functions <ref type="bibr">[Sag13,</ref><ref type="bibr">Sha03]</ref>. It is of fundamental interest to gain a complete understanding of the evolution and long-run behavior of the iterates {&#952; (&#945;) t } t&#8805;0 generated by nonsmooth contractive SA. Under suitable conditions on the operator H and the noise sequence {w t } t&#8805;0 , the SA iterates {&#952; (&#945;) t } t&#8805;0 form a time-homogeneous Markov chain and quickly converge to some limit random variable &#952; (&#945;)  <ref type="bibr">[DDB20,</ref><ref type="bibr">YBVE21]</ref>. Recent work has developed a suite of results for smooth SA [DDB20, HCX23b, DJMS21], including the geometric convergence of the chain, finite-time bounds on the higher moments, as well as properties of the limit &#952; (&#945;) . It has been observed that often E[&#952; (&#945;) ] &#824; = &#952; * , due to the use of constant stepsize. The difference E[&#952; (&#945;) ] -&#952; * is referred to as the asymptotic bias. In particular, for SA with differentiable dynamic, the work <ref type="bibr">[DDB20,</ref><ref type="bibr">HCX23b]</ref> makes use of Taylor expansion of H to establish that the asymptotic bias is proportional to the stepsize &#945; (up to a higher order term), i.e.,</p><p>where c is some vector independent of &#945; and o(&#945;) denotes a term that decays faster than &#945;. Such a fine-grained characterization of SA iterates gives rise to variance and bias reduction techniques that lead to improved estimation of the target solution &#952; * , as well as efficient statistical inference procedures <ref type="bibr">[DDB20,</ref><ref type="bibr">HCX23b,</ref><ref type="bibr">HCX23a]</ref>.</p><p>For nonsmooth SA, far little is known. Existing analysis based on the linearization / Taylor expansion of H is no longer applicable. Hence, distributional convergence and bias characterization results like (2) have not been established for nonsmooth SA procedures like Q learning. In fact, it is not even clear whether equation (2) remains valid for nonsmooth SA, and if not, what is the correct characterization.</p><p>Our Contributions: To investigate the above questions, we consider two important classes of nonsmooth contractive SA algorithms:</p><p>1. Nonsmooth SA with additive noise, where H(&#952;, w) &#8801; T (&#952;) + w. Our results cover operators T that are g &#8226; F decomposable, which is a rich class of smooth and nonsmooth functions <ref type="bibr">[Sha03]</ref>. See Section 2 for the formal description of the model.</p><p>2. A general form of Q-learning dynamics, which are nonsmooth SA with both additive and multiplicative noise. The model covers both synchronous Q-learning and asynchronous Q-learning as special cases. See Section 3 for the formal description of the model.</p><p>The first main result of the paper establishes the weak convergence of the Markov chain {&#952; (&#945;)</p><p>t } t&#8805;0 to a unique stationary distribution in W 2 -the Wasserstein distance of order 2 with respect to the contraction norm &#8741; &#8226; &#8741; c -for both the additive noise setting and Q-learning. Moreover, we characterize the geometric convergence rate. As a by-product of our analysis, we derive finite-time upper bounds on E&#8741;&#952; (&#945;) t -&#952; * &#8741; 2n c , the 2n-th moments of the estimation errors, generalizing the mean-square error (MSE) bound (i.e. E&#8741;&#952; (&#945;) t -&#952; * &#8741; 2 c &#8804; . . . ) in <ref type="bibr">[CMSS20,</ref><ref type="bibr">CMSS23]</ref> to higher moments and the smooth SA results in <ref type="bibr">[DDB20,</ref><ref type="bibr">SY19]</ref> to nonsmooth SA.</p><p>We next turn to the characterization of the stationary distribution of {&#952; (&#945;) t } t&#8805;0 . As existing techniques, which are based on linearizing H(&#952;, w) as &#952; &#8594; &#952; * , are not applicable for nonsmooth SA, we take an alternative approach by studying the limiting behavior of the properly rescaled iterates as the constant stepsize &#945; approaches 0. Since the MSE of &#952; (&#945;) t is of order O(&#945;) <ref type="bibr">[CMSS20]</ref>, the proper choice of scaling is by &#8730; &#945;, the diffusion scaling. In particular, we consider the centered and &#8730; &#945;-scaled iterates Y (&#945;) t</p><p>. The weak convergence of &#952; (&#945;) t to a limit &#952; (&#945;) implies that Y (&#945;) t converges weakly to the limit Y (&#945;) := &#952; (&#945;) -&#952; * &#8730; &#945; as t &#8594; &#8734;. Therefore, to understand the stationary distribution &#952; (&#945;) and its scaled version Y (&#945;) , we are interested in characterizing steady-state convergence, i.e., the convergence of Y (&#945;) as &#945; &#8594; 0 and the limit Y (if exists). This limit is illustrated by the red solid path in Fig. <ref type="figure">1</ref>. As we argue in Section 1.1, existing approaches to steady-state convergence face severe challenges in the nonsmooth SA setting. In this work, we develop a new prelimit coupling technique, which allows us to establish the weak convergence of Y (&#945;) in W 2 to a unique limiting random variable Y as &#945; &#8594; 0. Importantly, our technique can handle both additive noise and multiplicative noise, and provide an explicit rate of convergence. An overview of our technique is provided in Section 1.2. We remark that our technique can be potentially applied to the study of steady-state convergence in other stochastic dynamical systems and hence may be of its own interest.</p><p>Since convergence in W 2 implies convergence of the first two moments of Y (&#945;) , we obtain the following characterization of the asymptotic bias of the SA iterates:</p><p>We further provide a fine-grained characterization of the expectation E[Y ], which appears above in (3), and relate it to the structure of the SA update (1). Our results show that E[Y ] &#824; = 0 precisely when the operator H is truly nonsmooth, in which case the asymptotic bias is of order &#8730; &#945;. This result stands in sharp contrast to the &#945;-order bias of smooth SA in equation (2).</p><p>Finally, we explore the implications of the above results for iterate averaging and extrapolation. In particular, we consider applying Polyak-Ruppert (PR) tail averaging [Rup88, PJ92, JKK + 18] and Richardson-Romberg (RR) extrapolation <ref type="bibr">[Hil87]</ref> to the iterates generated by contractive SA algorithms. We investigate the resulting estimation errors and biases in the presence of nonsmoothness. In particular, thanks to the bias characterization in (3), we can employ the RR extrapolation technique to eliminate the leading term</p><p>&#945; and reduce the asymptotic bias to a higher order of &#8730; &#945;.</p><p>1.1 Challenges of Applying Existing Techniques to Nonsmooth SA Steady-state convergence, i.e., showing Y (&#945;) &#8594; Y in Figure <ref type="figure">1</ref>, is a problem of fundamental interest in stochastic dynamical systems, such as queueing networks <ref type="bibr">[GZ06]</ref>. One well-known approach to proving steady-state convergence in queueing networks is via justifying the interchange of limits, i.e., equivalence of the solid and dashed paths in Figure <ref type="figure">1</ref> [GZ06, Gur14, YY16, YY18]. Doing so is well recognized to be technically challenging, often requiring sophisticated "hydro-dynamic limits" methodology <ref type="bibr">[Bra98]</ref> as well as a well-defined stochastic differential equation (SDE) &#562;t with a stationary distribution. In our setting, it is unclear whether nonsmooth SA is associated with such an SDE, let alone the validity of interchanging the limits.</p><p>An alternative approach to the steady-state convergence is based on the Basic Adjoint Relationship (BAR) for the generator of the stochastic process. By using BAR with an exponential test function, one may be able to prove convergence of the moment generating function and in turn weak convergence of the corresponding random variables <ref type="bibr">[BDM17,</ref><ref type="bibr">BDM24,</ref><ref type="bibr">CMM22]</ref>. In our setting, however, the BAR of moment generating functions does not always lead to a straightforward solution. In fact, even for smooth SA dynamics with only additive noise (i.e., H(&#952; , w) = H(&#952;) + w), steady-state convergence is proved in the work <ref type="bibr">[CMM22]</ref> only when the limit random variable Y is Gaussian and under the assumption that the following equation from BAR has a unique solution in Y :</p><p>Verifying this assumption is challenging in general; in <ref type="bibr">[CMM22]</ref> this is done only when d = 1 or under some restricted conditions when d &#8805; 2. This difficulty is only exacerbated in the broader nonsmooth contractive SA setting, which covers the smooth SA setting considered in <ref type="bibr">[CMM22]</ref>. The &#8730; &#945;-scaling in our problem suggests a potential connection to the Langevin diffusion SDE and the literature on the Unadjusted Langevin Algorithm (ULA) <ref type="bibr">[DM17,</ref><ref type="bibr">DM19]</ref>. ULA corresponds to the Euler-Maruyama discretization of the Langevin diffusion and is given by</p><p>where U : R d &#8594; R is a potential function and {w t } t&#8805;0 are i.i.d. Gaussian noise. However, by comparing ULA with the SA update (1) scaled by &#8730; &#945;, one sees that the latter reduces to ULA only when the noise is additive and Gaussian and H is a gradient field and positive homogeneous at &#952; * .</p><p>We complement the above discussion with a simple example of nonsmooth contractive SA:</p><p>where w t i.i.d.</p><p>&#8764; N (0, 1) and b &#8712; R. The above dynamic is a special case of (1) with H(&#952;, w) = -|&#952;|/2 -b + w, which is nondifferentiable at &#952; = 0. Despite its apparent simplicity, this example already demonstrates some of the complexity in understanding the steady-state behavior of nonsmooth SA. For example, it is unclear how to follow the BAR approach to obtain a functional equation like (4) for the limit Y . The derivation of (4) in <ref type="bibr">[CMM22]</ref> relies on the continuous differentiability of the contraction operator H(&#952;, w).<ref type="foot">foot_0</ref> Also, incidentally, when b = 0, the dynamic (5) becomes an ULA update. The results in <ref type="bibr">[DM17,</ref><ref type="bibr">DM19]</ref> on ULA suggest that the limit Y is not Gaussian as its density function e U (x) involves a non-quadratic U . This contrasts to smooth SA, for which the BAR approach shows that Y is Gaussian <ref type="bibr">[CMM22]</ref>. As we soon see, the techniques in this paper bypass the need of working directly with and imposing assumptions on equations like (4).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1.2">Prelimit Coupling Technique</head><p>To overcome the challenges discussed in the previous subsection, we develop a prelimit coupling technique that can be used to establish the desired steady-state convergence without restrictive assumptions. We establish this result by proving convergence in Wasserstein distance W 2 , i.e., lim &#945;&#8594;0 W 2 (L(Y (&#945;) ), L(Y )) = 0 for a random variable Y , where L(Y ) denotes the distribution of Y . Our approach applies coupling arguments to the prelimit random variables Y (&#945;) t with &#945; &gt; 0, t &lt; &#8734; and consists of three steps.</p><p>Step 1: Gaussian Noise and Rational Stepsize First, we assume that the noise sequence {w t } t&#8805;0 is i.i.d. Gaussian. Consider two stepsizes &#945; and &#945; &#8242; = &#945;/k, where k &#8712; N + . We have the corresponding scaled iterates Y (&#945;) t and Y (&#945; &#8242; ) t generated by equation (1). The main idea is to couple these two sequences in such a way that one step of Y (&#945;) t corresponds to k steps of Y</p><p>Note that (w kt + &#8226; &#8226; &#8226; + w kt+k-1 )/ &#8730; k and w t are identically distributed under the Gaussian noise assumption. Under this coupling, we establish convergence of the squared distance E&#8741;Y</p><p>c under some appropriate norm &#8741; &#8226; &#8741; c . Sending t to infinity gives W 2 L(Y (&#945;) ), L(Y (&#945; &#8242; ) ) &#8712; o(1). Generalizing this argument to rational stepsizes &#945; and &#945; &#8242; , we conclude that (Y (&#945;) ) &#945;&#8594;0,&#945;&#8712;Q + is a Cauchy sequence with respect to W 2 . Consequently, there exists a limit Y such that lim</p><p>Step 2: General Stepsize Still assuming Gaussian noise, we prove that L(Y (&#945;) ) is continuous in &#945; with respect to W 2 . To this end, we consider two real-valued stepsizes &#945; and &#945; &#8242; and couple the sequences Y</p><p>(&#945;) t and Y (&#945; &#8242; ) t</p><p>, this time by letting them share the same noise:</p><p>We again control the squared distance E&#8741;Y</p><p>&#8741; 2 c , and then set t &#8594; &#8734; followed by &#945; &#8242; &#8594; &#945;, thus establishing the continuity property lim &#945; &#8242; &#8594;&#945; W 2 L(Y (&#945;) ), L(Y (&#945; &#8242; ) ) = 0. Since Q + is dense in R + , together with the result from step 1, we obtain</p><p>Step 3: General Noise In this step, we relax the Gaussian noise assumption. Suppose the sequence</p><p>is driven by some general noise w &#8242; t , and let Y (&#945;) t be driven by Gaussian noise w t with matching first two moments. Setting &#954; = &#8970;&#945; -1/2 &#8971;, we use a multivariate Berry-Esseen bound in Wasserstein distance <ref type="bibr">[Bon20]</ref> to show that there exists a coupling between w &#8242; t and w t such that</p><p>Under this noise coupling, we bound</p><p>) , thereby establishing that Y &#8242; (&#945;) and Y (&#945;) have the same distributional limit as &#945; &#8594; 0.</p><p>Following the above three-step procedure, the majority of the technical work goes into obtaining tight estimates for squared distances of the form E&#8741;Y</p><p>c , with potentially mismatched stepsizes (&#945;, &#945; &#8242; ) and time indices (t, t &#8242; ). Doing so under the nonsmooth SA dynamics requires carefully analyzing the multi-step dynamics and leveraging the contractive property via a generalized Moreau envelope argument.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1.3">Notations</head><p>We use B d (&#952;, &#1013;) to denote an open ball centering at &#952; with radius &#1013; &gt; 0 with respect to &#8467;</p><p>A function h is called L-smooth w.r.t. some norm &#8741; &#8226; &#8741; if &#8741;&#8711;h(x) -&#8711;h(y)&#8741; * &#8804; L&#8741;x -y&#8741;, &#8704;x, y, where &#8741; &#8226; &#8741; * is the dual norm of &#8741; &#8226; &#8741;.</p><p>Let P 2 (R d ) denote the space of square-integrable distributions on R d . For a random vector &#952;, let L(&#952;) denote the distribution of &#952; and Var(&#952;) its covariance matrix. The Wasserstein 2-distance between two distributions &#181; and &#957; in P 2 (R d ) is defined as</p><p>where &#928;(&#181;, &#957;) is the set of joint distributions in P 2 (R d &#215; R d ) with marginal distributions &#181; and &#957;.</p><p>For a finite set S, we use &#8710;(S) to denote the probability simplex over S. Given &#960; &#8712; &#8710;(S), we denote by Multi (&#960;, n) the multinomial distribution with event probabilities &#960; and number of trials n.</p><p>For two real valued functions f (x), g(x) :</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Paper organization.</head><p>The remainder of the paper is organized as follows. In Section 2 we present the model and the main results for SA with additive noise. In Section 3 we extend these results to Q-learning. In Section 4 we explore the implications of our results for Polyak-Ruppert averaging and Richardson-Romberg extrapolation. We outline the proofs of our main results in Section 5. We provide numerical experiments that corroborate our theoretical results in Section 6. We discuss additional related work in Section 7.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2">Nonsmooth Stochastic Approximation with Additive Noise</head><p>In this section, we consider contractive nonsmooth stochastic approximation with additive noise.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.1">Model Setup</head><p>We consider the following stochastic approximation iteration with additive noise:</p><p>where T : R d &#8594; R d is an operator, &#945; &gt; 0 is a constant stepsize and {w t } t&#8805;0 is a sequence of i.i.d zero-mean noise.</p><p>Stochastic approximation subsumes many important iterative algorithms. For example, if T (&#952;) = -&#8711;U (&#952;) + &#952; for some function U : R d &#8594; R that is twice continuously differentiable, L-smooth and &#963;-strongly convex, then the update (7) corresponds to Stochastic Gradient Descent (SGD) for minimizing U <ref type="bibr">[Lan20]</ref>. If T (&#952;) = A&#952; + b, where A &#8712; R d&#215;d is a Hurwitz matrix, then (7) becomes Linear SA, which in turn covers the TD-learning algorithm in reinforcement learning <ref type="bibr">[HCX23b,</ref><ref type="bibr">SY19]</ref>. In both examples, the operator T is at least C 1 -smooth and contractive in &#8741; &#8226; &#8741; 2 (or its weighted version).</p><p>In this work, we consider a more general class of SA algorithms with a potentially nonsmooth operator T . We only assume that T is contractive with respect to an arbitrary norm.</p><p>Assumption 1 (Contractive T ). The operator T : R d &#8594; R d is &#947;-contractive for some &#947; &#8712; (0, 1) with respect to some norm &#8741; &#8226; &#8741; c .</p><p>By Banach fixed point theorem, the fixed point equation T (&#952;) = &#952; has a unique solution &#952; * &#8712; R d . We consider the following moment assumption for the additive noise w t , indexed by n &#8805; 1.</p><p>Assumption 2 (n). The random variables {w t } t&#8805;0 have finite (2n)-th moments.</p><p>Such moment assumptions, for example with n = 1 or 2, are standard in prior work on the analysis of SGD and SA[DDB20, <ref type="bibr">KY03,</ref><ref type="bibr">SY19]</ref>. In general, under Assumption 2(n) we can control the 2n-th moment of the SA iterates {&#952;</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.2">Moments Bounds and Convergence to Stationary Distribution</head><p>We first derive finite-time upper bounds on E&#8741;&#952;</p><p>c , the 2n-th moments of the estimation errors, generalizing the results in [CMSS20, CMSS23] to higher moments and those in <ref type="bibr">[DDB20]</ref> to nonsmooth SA.</p><p>Proposition 1 (Moment Bounds). For each integer n &#8805; 1, under Assumption 1 and Assumption 2(n), there exists &#8113; &gt; 0 such that for any &#945; &#8804; &#8113;, there exists t &#945;,n &gt; 0 and</p><p>where c n and c &#8242; n are constants that are independent with &#945; and t. Moreover, t &#945;,1 = 0.</p><p>In subsequent analysis, we mostly use Assumption 2(n) and Proposition 1 with n &#8712; {1, 2}. In particular, Proposition 1 with n = 1 provides a finite-time mean-square error (MSE) bound. Using this bound, we can establish our first main theorem, which proves the weak convergence of the stochastic process {&#952; (&#945;) t } t&#8805;0 to a unique stationary distribution in W 2 ; moreover, we characterize its geometric convergence rate.</p><p>Theorem 1 (Distributional Convergence). Under Assumption 1 and Assumption 2(1), there exists &#8113;&#8242; &gt; 0 such that for any stepsize &#945; &#8804; &#8113;&#8242; and any initial distribution of &#952; (&#945;) 0 , the sequence {&#952;</p><p>where c is a constant that is independent of &#945; and t.</p><p>A key step in proving Proposition 1 and Theorem 1 is to construct a proper smooth Lyapunov function for the nonsmooth dynamics. Previous works on higher moments bounds and convergence in W 2 focus on linear SA and smooth SGD <ref type="bibr">[DDB20,</ref><ref type="bibr">HCX23b]</ref>. These dynamics are smooth and contractive in the &#8467; 2 norm &#8741; &#8226; &#8741; c = &#8741; &#8226; &#8741; 2 , the square of which can be used as a smooth Lyapunov function. However, for general contractive SA, the norm &#8741; &#8226; &#8741; c may be nondifferentiable, e.g., &#8741; &#8226; &#8741; &#8734; . To handle this general setting, we make use of the generalized Moreau envelope of &#8741; &#8226; &#8741; c , a technique that has been used in <ref type="bibr">[CMSS20,</ref><ref type="bibr">CMSS23]</ref> to study the MSE (i.e., n = 1) of contractive SA. To further establish the weak convergence result in Theorem 1, we develop a careful coupling argument using the Moreau envelope, going beyond the &#8467; 2 norm based anaysis in <ref type="bibr">[HCX23b,</ref><ref type="bibr">DDB20]</ref>. The proofs of Proposition 1 and Theorem 1 are outlined in Section 5 and given in full in Appendices A and B.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.3">Steady-State Convergence and Bias Characterization</head><p>Sometimes we restrict to a more specific but still quite general class of SA dynamics. In particular, we consider operators T that are defined by the so-called g &#8226; F decomposable functions, a class of nonsmooth functions first introduced in the work <ref type="bibr">[Sha03]</ref>. We extend the definition in <ref type="bibr">[Sha03]</ref> to multi-dimensional functions.</p><p>Definition 1. We say that the function</p><p>for some mappings g : R m &#8594; R d and F : B d (0, &#1013;) &#8594; R m that satisfy: (i) g is positively homogeneous<ref type="foot">foot_2</ref> of degree 1 and continuous; (ii) F is differentiable at B d (0, &#1013;), &#8711;F is continuous at 0 and F (0) = 0.</p><p>The g &#8226; F decomposable function class is a rich class that contains max-functions, largest eigenvalue functions, and &#8467; 1 -norm regularized functions, as well as their composition with smooth functions. See <ref type="bibr">[Sha03,</ref><ref type="bibr">Sag13]</ref> for other special cases of g &#8226; F decomposable functions and their connection to other nonsmooth classes [Mif77, Wri93, LOS00, Lew02, DL14, DDJ23]. Note that the requirement of &#8711;F (&#8226;) continuous at 0 is used for the steady-state convergence result.</p><p>With Definition 1, we consider potentially nonsmooth SA updates (7) with an operator T satisfying the following assumption.</p><p>Assumption 3 (Nonsmooth Class). The operator T is g &#8226; F decomposable at its fixed point &#952; * . Explicitly, there exists &#1013; &gt; 0 such that</p><p>for some mappings g : R m &#8594; R d and F : B d (0, &#1013;) &#8594; R m satisfying the requirements in Definition 1.</p><p>Under Assumption 3, the operator T is at least locally C 0 at &#952; * . By setting m = d and g as the identity mapping, this assumption covers all locally C 1 and contractive T , including SGD and Linear SA discussed earlier. In addition, this model covers operators T that are not differentiable at &#952; * , such as the example in (5) with b = 0 (corresponding to g(&#952;) = -|&#952;| 2 and F (&#952;) = &#952;), as well as the optimal Bellman operator that defines the Q learning algorithms (see Section 3).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Define the centered and rescaled iterate</head><p>as t &#8594; &#8734;. Focusing on SA satisfying the g &#8226;F decomposability Assumption 3, our next theorem establishes steady-state convergence, that is, the convergence of {Y (&#945;) } &#945;&#8712;(0, &#8113;&#8242; ) as &#945; &#8594; 0.</p><p>Theorem 2 (Steady-State Convergence). Suppose that Assumption 1, Assumption 2(2) and Assumption 3 hold. There exists a unique random variable Y , depending only on T and Var(w 0 ), such that</p><p>Consequently, we have</p><p>Among other consequences, Theorem 2 implies that the steady-state bias, E[&#952; (&#945;) ] -&#952; * , is generally on the order of O( &#8730; &#945;) for small stepsizes &#945;. This result stands in sharp contrast to existing work on smooth SA, which has an order-wise smaller bias linear in &#945;. This &#8730; &#945;-bias property, which arises precisely due to the nonsmoothness of the SA dynamic, is further characterized in our next theorem. We highlight that Theorem 2 is a universality result: the limit Y depends on the (zero-mean) noise {w t } t&#8805;0 only through its variance and is otherwise independent of the noise distribution.</p><p>Note that Theorem 2 applies to any contractive SA within the g &#8226; F decomposable class. In this generality, the convergence result in the theorem is asymptotic. The convergence rate and the specific order of the o( &#8730; &#945;) term depend on how fast &#8711;F (&#952;) converges to &#8711;F (0); see equation (45) in our proof. It is possible to obtain explicit, nonasymptotic bounds on the convergence rate for specific SA dynamics and T operators. For example, in the next section, we establish an O(&#945; 1 4 ) convergence rate for Q-learning. The work <ref type="bibr">[CMM22]</ref> also provides a steady-state convergence result but requires a strong uniqueness assumption, which is difficult to verify in most cases. Our results are established using a different technique, by directly proving the weak convergence of Y (&#945;) in W 2 using prelimit coupling. We outline the proof of Theorem 2 in Section 5.2, deferring the complete proof to Appendix C.</p><p>The following theorem provides a more fine-grained characterization of the expectation of the limit Y , which appears in the expression (9) for the steady-state bias.</p><p>Theorem 3 (Bias Characterization). Under the same setting as in Theorem 2, we have</p><p>Roughly speaking, the premise in Part (2) of the theorem implies that T is not differentiable at &#952; * (otherwise its sub/supdifferential would be a singleton consisting of its gradient). In this case, provided that the noise w 0 is non-degenerate, we have E[Y ] &#824; = 0. Hence, equation (9) implies that the bias is on the order of &#920;( &#8730; &#945;). We conjecture that this result holds under more general settings of nonsmooth T where its sub/supdifferential may not exist. This &#8730; &#945; order of the bias has important implications for bias reduction via the Richardson-Romberg extrapolation, which we discuss in Section 4.</p><p>Part (1) of Theorem 3, on the other hand, implies that for any smooth SA where T is continuously differentiable at &#952; * , the asymptotic bias is order-wise smaller than &#8730; &#945;. This result is consistent with those in <ref type="bibr">[DDB20,</ref><ref type="bibr">HCX23b]</ref>, which show that the asymptotic biases of SGD and Linear SA with i.i.d. noise are of order &#920;(&#945;) and 0, respectively.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3">Q-learning: Nonsmooth Stochastic Approximation with Multiplicative Noise</head><p>In this section, we extend our results to Q-learning algorithms, which are nonsmooth SA procedures with multiplicative noise.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.1">Model Setup</head><p>Consider a discounted Markov decision process (MDP) defined by the tuple (S, A, P, r, &#947;), where S and A are respectively the (finite) state and action spaces, P : S &#215; A &#8594; &#8710;(S) is the transition kernel, r : S &#215; A &#8594; R is the stochastic reward function, and &#947; &#8712; (0, 1) is the discount factor. Given a policy &#960; : S &#8594; &#8710;(A), the Q-function q &#960; : S &#215; A &#8594; R is defined as</p><p>and r k is an independent copy of r. The goal is to find an optimal policy &#960; * that maximizes the Q-function. Below we often view P as an |S||A|-by-|A| matrix, r as a random vector in R |S||A| , and q &#960; as a vector in R |S||A| .</p><p>Q-learning <ref type="bibr">[WD92]</ref> is a popular class of reinforcement learning methods that approximate the optimal Q-function q * = q &#960; * , from which one can recover the optimal policy as &#960; * (s) &#8712; arg max a&#8712;A q * (s, a), &#8704;s &#8712; S.</p><p>We consider a general form of Q-learning that iteratively generates a sequence of Q-function estimates, {q t : S &#215; A &#8594; R} t&#8805;0 , according to the following recursion:</p><p>where the function f : R |S||A| &#8594; R |S| is given by</p><p>a), &#8704;s &#8712; S, and {(D t , P t , r t )} t&#8805;0 are i.i.d. random matrices/vectors satisfying: (i) D = E[D 0 ] is a |S||A|-by-|S||A| diagonal matrix with D ii &#8712; (0, 1], &#8704;i &#8712; S &#215; A; (ii) E[P 0 ] = P ; (iii) {r t } t&#8805;0 are independent copies of r. Here D t , P t and r t correspond to the empirical state-action distribution, empirical transition and empirical reward function, respectively, observed at the t-th iteration. We discuss two important special cases of the above model. &#8226; Synchronous Q-learning [Wai19]: At each time step t and for each state-action pair (s, a), we observe a reward r t (s, a) d = r(s, a) and a next state x t (s, a) drawn from the transition kernel P (&#8226;|s, a). The Q-function estimates are updated as</p><p>Synchronous Q-learning corresponds to the update rule (10) where D t &#8801; I and P t is a binary random matrix whose (s, a)-th row is independently distributed as Multi (P (&#8226;|s, a) , 1).</p><p>&#8226; Asynchronous Q-learning <ref type="bibr">[CMZ23]</ref>: At each time step t, we observe a state-action pair (s t , a t ) &#8764; &#954; b , where the distribution &#954; b &#8712; &#8710;(S &#215; A) can be the stationary state-action distribution of some behavior policy. Conditioned on (s t , a t ), we observe the reward r t (s t , a t ) d = r(s t , a t ) and the next state s &#8242; t+1 drawn according to P (&#8226;|s t , a t ). The Q-function estimates are updated as</p><p>t (s, a), &#8704;(s, a) &#824; = (s t , a t ). Asynchronous Q-learning corresponds to the update rule (10) with diag(D t ) &#8764; Multi (&#954; b , 1) and the same P t before. Note that only the (s t , a t ) entry of q (&#945;) t is updated at iteration t, with D t acting as the corresponding mask matrix.</p><p>With other choices of (D t , P t , r t ), the update rule (10) can capture other forms of Q-learning with different sampling models.</p><p>The Q-learning update (10) can be cast as contractive SA. To this end, define a random operator H by H(q; {D 0 , P 0 , r 0 }) = &#947;D 0 P 0 f (q) + (I -D 0 )q + D 0 r 0 , &#8704;q &#8712; R |S||A| .</p><p>Denote by H : R |S||A| &#8594; R |S||A| the expected operator, where H(q) := E {D0,P0,r0} H(q, {D 0 , P 0 , r 0 }) = &#947;DP f (q) + (I -D)q + Dr, with r := E[r 0 ]. It can be verified that H is a &#947; 0 -contractive operator with respect to the infinity norm &#8741; &#8226; &#8741; &#8734; , where</p><p>Moreover, the optimal Q-function q * is the unique solution to the fixed point equation H(q * ) = q * , which can be seen to be equivalent to the optimal Bellman equation. To be consistent with the additive noise setting, below we use</p><p>With the above notations, the Q-learning update (10) can rewritten as a contractive SA iteration:</p><p>Note that the iteration (11) is nonsmooth due to the max operation in the function f in (10); moreover, it involves multiplicative noise due to multiplication with the random matrices D t and P t , which are viewed as noisy versions of D and P .</p><p>For the noise we consider the following moment assumption, indexed by an integer n &#8805; 1:</p><p>Assumption 4 (n). The random variables {(D t , P t , r t )} t&#8805;0 have finite (2n)-th moments.</p><p>Below we analyze Q-learning. Our results parallel those in the additive noise setting, but the analysis is significantly more challenging because of the multiplicative noise.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.2">Moments Bounds and Convergence to Stationary Distribution</head><p>We first derive finite-time upper bounds on E[&#8741;q (&#945;) t -q * &#8741; 2n c ], the 2n-th moments of the estimation errors.</p><p>Proposition 2 (Moment Bounds). For each integer n &#8805; 1, under Assumption 4(n), there exists &#945; n &gt; 0 such that for any &#945; &#8804; &#945; n , there exists t &#945;,n &#8805; 0 such that</p><p>where c n and c &#8242; n are constants that are independent of &#945; and t. Moreover, t &#945;,1 = 0.</p><p>Similarly to the additive noise setting, we mostly use Proposition 2 with n &#8712; {1, 2} for the subsequent analysis. In particular, using Proposition 2 with n = 1, we can establish the weak convergence in W 2 of the stochastic process {q (&#945;) t } t&#8805;0 to a unique stationary distribution, and further characterize its geometric convergence rate. This is done in the following theorem.</p><p>Theorem 4 (Distributional Convergence). Under Assumption 4(1), there exists &#8113;&#8242; 0 &gt; 0 such that for &#8704;&#945; &#8804; &#8113;&#8242; 0 and all initial distribution of q (&#945;) 0 , the sequence {q</p><p>t } t&#8805;0 converges geometrically fast in W 2 to a random variable q (&#945;) with W 2 2 L(q</p><p>where c is a constant independent of &#945; and t.</p><p>The proofs of Proposition 2 and Theorem 4 use the generalized Moreau envelop of the contraction norm &#8741; &#8226; &#8741; c , similarly to those of Proposition 1 and Theorem 1 for the additive noise setting. However, the multiplicative noise makes the analysis more involved. We discuss the key difference in Section 5.1. The complete proofs of Proposition 2 and Theorem 4 can be found in Appendix E and Appendix F, respectively.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.3">Steady-State Convergence and Bias Characterization</head><p>Consider the centered/rescaled iterate Y (&#945;) t = (q (&#945;) t -q * )/ &#8730; &#945;. Theorem 4 implies that the sequence {Y (&#945;) t } t&#8805;0 converges weakly to a steady-state random variable Y (&#945;) = (q (&#945;) -q * )/ &#8730; &#945;. In the following theorem, we establish the steady-state convergence for {Y (&#945;) } as &#945; &#8594; 0.</p><p>Theorem 5 (Steady-State Convergence). Suppose Assumption 4(2) holds. There exists a unique random variable Y such that lim</p><p>), which implies that</p><p>A few remarks are in order. Similar to the additive noise setting, Theorem 5 indicates that the steady-state bias of Q-learning, E[q (&#945;) ] -q * , is in general of order O( &#8730; &#945;) for small stepsize &#945;. Again, this distinctive &#8730; &#945;-bias result is due to the nonsmooth nature of the Q-learning dynamic; cf. function f in equation (10). Our next theorem provides a more precise characterization on the bias.</p><p>The proof of Theorem 5 also uses our prelimit coupling technique, which can handle the multiplicative noise. On the contrary, the work <ref type="bibr">[CMM22]</ref> only considers the additive noise setting and it is unclear how to generalize their analysis to the multiplicative noise case. Moreover, as a byproduct of our prelimit coupling, for the explicit Q-learning dynamic, we can obtain an O(&#945; 1 4 ) convergence rate of Y (&#945;) to the limit Y . The proof of Theorem 5 is provided in Appendix G.</p><p>To discuss further properties of the limit Y , we need some definitions. We say that a state s &#8242; &#8712; S is rooted if P (s &#8242; |s, a) = 0, &#8704;(s, a) &#8712; S &#215; A.</p><p>Intuitively, a state s &#8242; is rooted if it is not accessible from any other state in the MDP. Using the optimal Q-function q * , we define A * (s) := arg max a&#8712;A q * (s, a) as the optimal action set for each state s &#8712; S. Note that the action distribution &#960; * (&#8226;|s) of the optimal policy is supported on the set A * (s) for each s &#8712; S. We say that a state s &#8712; S is tied if |A * (s)| &gt; 1, i.e., there is a tie among multiple optimal actions for s.</p><p>We classify all MDPs into two types:</p><p>&#8226; Type A: There exists at least one state that is tied and not rooted.</p><p>&#8226; Type B (i.e., not Type A): There is no tied state, or all tied states are rooted.</p><p>For each type of MDPs, we provide a more fine-grained characterization for the expectation of the limit Y in the following theorem. Recall that E[Y ] determines the order of the steady-state bias by equation (13).</p><p>Theorem 6 (Bias Characterization). Under the same setting as Theorem 5, we have 1. E[Y ] &#824; = 0 if the underlying MDP is in Type A and Var( H(q * , {D 0 , P 0 , r 0 })) is positive definite.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.">E[Y</head><p>3. If the underlying MDP is in Type B and Assumption 4(n) holds for n &#8805; 2, then E[q (&#945;) ] = q * + O(&#945; n ).</p><p>Note that for a Type-A MDP, the optimal policy is not unique due to the existence of multiple optimal actions for at least one state. In this case, Part (1) of the theorem implies E[Y ] &#824; = 0. Consequently, the asymptotic bias E[q (&#945;) ] -q * of Q-learning is of &#8730; &#945; order. As we will see in Section 4, the precise characterization of order-&#8730; &#945; bias allows one to use the Richardson-Romberg extrapolation for bias reduction. Parts (2) and (3) of the theorem imply that for Type-B MDPs (i.e., those with a unique optimal policy), the asymptotic bias can be controlled by the n-th order of the stepsize, as long as the noise has finite 2n-th moment. For Q-learning, the random matrices {D t , P t } t&#8805;0 are bounded and thus all their moments are finite. If the rewards {r t } t&#8805;0 also have finite arbitrary moments (e.g., they are Gaussian distributed or bounded), then the asymptotic bias is O(&#945; n ) for any n &#8805; 1, that is, the bias decays superpolynoimally with respect to the stepsize.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4">Polyak-Ruppert Averaging and Richardson-Romberg Extrapolation</head><p>In this section, we study the implications of our theoretical results for iterate averaging and extrapolation. In particular, we consider applying Polyak-Ruppert (PR) tail averaging [Rup88, PJ92, JKK + 18] and Richardson-Romberg (RR) extrapolation <ref type="bibr">[Hil87]</ref> to the iterates generated by contractive SA algorithms, and investigate the resulting estimation errors and biases in the presence of nonsmoothness.</p><p>To this end, we will first state two general results for PR averaging and RR extrapolation, respectively. We remark that these general results cover settings broader than those considered in this paper and may be of independent interest. We then apply these results to the contractive SA and Q-learning procedures studied in Section 2 and Section 3.</p><p>Let {&#952;</p><p>t } t&#8805;0 be a sequence of (raw) iterates in R d generated by an SA procedure of the form</p><p>with a constant stepsize &#945; &gt; 0. We assume that the noise sequence {w t } t&#8805;0 is a uniformly ergodic Markov chain defined on a general state space W with transition kernel p and stationary distribution &#181; W , and let &#964; &#945; denote its &#945;-mixing time, i.e., &#964; &#945; := min{t &#8805; 0 : max x&#8712;X &#8741;p t (x, &#8226;) -&#181; X &#8741; TV &#8804; &#945;}, where &#8741; &#8226; &#8741; TV denotes the total variation norm. Note that a sequence of i.i.d. noise {w t } t&#8805;0 is a uniformly ergodic Markov chain with &#964; &#945; = 1 for all &#945; &gt; 0.</p><p>We introduce two conditions on the raw SA iterates {&#952; (&#945;) t } t&#8805;0 , which allow us to quantify the performance of PR averaging and RR extrapolation with respect to a target vector &#952; * .</p><p>Condition 1 (Distributional convergence). There exist constants C 0 , C 1 , &#8113; &gt; 0 satisfying 0 &lt; 1 -&#8113;C 1 &lt; 1 such that for some random variable &#952; (&#945;) it holds that</p><p>Condition 2 (Asymptotic bias and variance). There exist constants &#946; &gt; 0 and &#948; &#8805; 0 such that</p><p>where B &#8712; R d is a vector independent of t and &#945;. Moreover, E[&#8741;&#952; (&#945;) -&#952; * &#8741; 2 2 ] &#8712; O(&#945;&#964; &#945; ). Note that as the stepsize &#945; gets larger, we have a faster geometric convergence in Condition 1 but a greater bias in Condition 2. We later verify these conditions under our contractive SA and Q-learning settings.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.1">Polyak-Ruppert Tail Averaging</head><p>Polyak-Ruppert (PR) averaging procedure [Rup88, PJ92, JKK + 18] is a popular procedure for reducing the variance of the SA iterates and accelerating the convergence. Specifically, given a burn-in period k 0 &#8805; 0, we compute the tail-averaged iterates as:</p><p>The following proposition provides non-asymptotic bounds for the first two moments of the tailed-averaged iterate &#952;(&#945;) k0,k .</p><p>Proposition 3. Under Conditions 1 and 2, we have for all k 0 &#8805; 2 &#945;C1 log 1 &#945;&#964;&#945; and k &#8805; k 0 + &#964; &#945; :</p><p>The proof is provided in Section I, generalizing the arguments from <ref type="bibr">[HCX23b]</ref> on Linear SA. As a typical application of the above result, let us set the burn-in parameter as k 0 = k/2 and consider the second moment bound in Equation (17). The first two terms on the right-hand side of (17) correspond to the squared asymptotic bias, which is the same as the bias of the raw iterates in Condition 2 and cannot be reduced by averaging. The third term captures the optimization error, which decays geometrically in k due to the geometric distributional convergence in Conditions 1. The last right hand side term of (17) corresponds to the variance of averaged iterate &#952;k/2,k , which decays at a rate O(1/k) due to averaging over k/2 raw iterates that are geometrically mixed.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.2">Richardson-Romberg Extrapolation</head><p>With the fine-grained characterization of the asymptotic bias in Condition 2, one can use the RR extrapolation technique <ref type="bibr">[Hil87]</ref> to reduce the bias to a higher order term of the stepsize &#945;. In particular, we consider first-order RR extrapolation, where we run two SA recursions (14) in parallel under two different stepsizes &#945; and 2&#945;, under the same sequence of noise {w t } t&#8805;0 . The resulting tail-averaged iterates &#952;(&#945;) k0,k and &#952;(2&#945;) k0,k are defined as before. The RR extrapolated iterates are then computed as follows as a linear combination of the two averaged iterates:</p><p>The coefficients of the above linear combination are chosen such that we cancel out the dominating terms &#945; &#946; and (2&#945;) &#946; in the biases.</p><p>Proposition 4. Under Conditions 1 and 2, the RR extrapolated iterates defined in (18) satisfy the following bounds for all k 0 &#8805; 2 &#945;C1 log 1 &#945;&#964;&#945; and k &#8805; k 0 + &#964; &#945; :</p><p>The proof is provided in Section J. Again focusing on the second moment bound (20) with k 0 = k/2, we see that the squared bias is reduced to o(&#945; 2&#946;+2&#948; ), whereas we retain the geometric convergence of the optimization error (second right hand side term) and the 1/k rate of the variance (third right hand side term).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.3">Applications to Contractive SA with Additive Noise and Q-Learning</head><p>First consider the contractive SA dynamic (7) with additive noise from Section 2. By Theorem 1, Condition 1 holds with</p><p>2 and &#948; = 0. Hence, Proposition 4 with k 0 = k/2 implies the following MSE bound:</p><p>Similarly, for the Q-learning dynamic (10) in Section 3, Condition 1 holds with C 1 = 1 -&#8730; &#947; 0 and &#964; &#945; = 1 by Theorem 4; Condition 2 holds with &#964; &#945; = 1, B = E[Y ], &#946; = 1 2 and &#948; = 1/4 by Theorem 5. Consequently, we have the following MSE bound:</p><p>In both cases, the asymptotic bias of the raw iterate is on the order of</p><p>) by RR extrapolation. We emphasize that the order of the bias here is different from the O(&#945;) bias typically seen in smooth SGD/SA dynamics <ref type="bibr">[DDB20,</ref><ref type="bibr">HCX23b]</ref>. Knowledge of the correct bias order, as provided by our theoretical results, is crucial for the RR extrapolation to be effective. We note that if E[Y ] = 0, the bias of the raw iterate is already o( &#8730; &#945;), in which case the above RR extrapolation scheme may not lead to further improvement but it does not hurt the performance either (up to constants). In Section 6, we provide numerical experiments demonstrating bias reduction by RR extrapolation.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5">Proof Outline</head><p>In this section, we outline the proofs of our main theoretical results. We focus on the additive noise setting and discuss how to generalize to the Q-learning setting with multiplicative noise. Without additional explanation, we default iterates are in</p><p>is not necessarily differentiable, our analysis makes use of its generalized Moreau envelope [CMSS23, CMSS20], which can be thought of as a smooth surrogate of &#981;. In particular, let h <ref type="bibr">[Fol99]</ref>, there exist two positive constants l cs and u cs such that</p><p>The basic properties of M &#951; are summarized below. The proof can be found in [CMSS23, Proposition 1] and [CMSS20, Lemma A.1].</p><p>Proposition 5. M &#951; has the following properties: (1) M &#951; is convex and 1 &#951; -smooth with respect to &#8741; &#8226; &#8741; 2 ; (2) there exists a norm</p><p>In this section, we omit the subscript in &#952; (&#945;) t</p><p>when the dependence on the stepsize &#945; is clear.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.1">Proof Outline for Proposition 1 (Moment Bounds) and Theorem 1 (Distributional Convergence)</head><p>Moment Bounds. To bound the (2n)-th moment E&#8741;&#952; (&#945;) t -&#952; * &#8741; 2n c , we use the generalized Moreau envelope M &#951; as a Lyapunov function and generalize the arguments in [CMSS20, CMSS23] to higher moments by induction on n. In particular, using the contractive property of T and the properties of M &#951; , we can obtain</p><p>Taking the n-th moment of both sides gives</p><p>Expanding the right hand side and noting that w t is zero mean, we derive</p><p>. A careful calculation using the induction hypothesis shows that the cross terms satisfy</p><p>from which the desired moment bounds follow in light of part (c) of Proposition 5. Distributional Convergence. Similarly to [DDB20, HCX23b, ZX24], the key step in proving Theorem 1 is establishing the convergence of W 2 2 L(&#952;</p><p>t } t&#8805;0 and {&#952; &#8242; (&#945;) t } t&#8805;0 with different initialization. Coupling these two sequences by sharing the noise sequence {w t } t&#8805;0 , we further reduce the problem to bounding E&#8741;&#952;</p><p>. The latter can be done using an argument similar to equation ( <ref type="formula">22</ref>).</p><p>Proof for Q-learning: Due to multiplicative noise, the error term w t depends on the iterate q (&#945;) t itself. A more involved analysis using the structure of Q-learning allows us to control resulting additional error terms, thereby proving Proposition 2 and Theorem 4.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.2">Proof Outline for Theorem 2 (Steady State Convergence)</head><p>The proof consists of three steps and employs coupling arguments applied to the prelimit rescaled random variables</p><p>&#8730; &#945; with &#945; &gt; 0 and t &lt; &#8734;.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.2.1">Step 1: Gaussian Noise and Rational Stepsize</head><p>In this step, we assume that the noise w t is Gaussian. We prove that {L(Y (&#945;) )} &#945;&#8712;Q + form a Cauchy sequence with respect to W 2 , thus converging to a unique limit L(Y ), i.e., lim &#945;&#8594;0,&#945;&#8712;Q</p><p>To this end, we first consider two stepsizes &#945; and &#945;/k, where k &#8712; N + and study the rescaled iterates</p><p>generated by equation ( <ref type="formula">7</ref>). As discussed in Section 1.2, we couple these two sequences such that one step of</p><p>. We take the generalized Moreau envelope of the difference sequence, {Y</p><p>where r 1 is a constant. The proof of Equation (24) makes use of the g &#8226; F decomposibility of the operator T and is the most critical sub-step in Step 1. Consequently, we have</p><p>Combining with the distributional convergence result in Theorem 1, we obtain that</p><p>2 ).</p><p>Next we consider stepsizes &#945; &gt; 0 and &#945;/k with k = p/q &#8712; Q + , where p, q &#8712; N + and p &gt; q. By triangle equality for the W 2 metric, we have</p><p>Therefore, for any rational sub-sequence {&#945; j } &#8734; j=0 with &#945; j &#8594; 0, {L(Y (&#945;j ) )} &#8734; j=0 is a Cauchy sequence with respect to W 2 . Consequently, a limit L(Y ) exists. Since two rational sub-sequences can be merged into one rational sub-sequence by staggered placement, the limit is unique.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.2.2">Step 2: General Stepsize</head><p>Still assuming Gaussian noise, we generalize the result in Step 1 to general stepsize. To this end, we prove that Y (&#945;) is continuous in &#945; with respect to W 2 . More specifically, we consider two real-valued stepsizes &#945; and &#945; &#8242; , and couple the corresponding two sequences Y (&#945;) t and Y (&#945; &#8242; ) by letting them share the same noise {w t } t&#8805;0 , as detailed in Section 1.2. We then obtain the following equation by applying the generalized Moreau envelope on the difference sequence {Y</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Following similar arguments as in</head><p>Step 1, we have lim</p><p>is continuous in &#945; with respect to W 2 . Since the real numbers have the rational numbers as a dense subset, we obtain the desired convergence result lim &#945;&#8594;0 W 2 L(Y (&#945;) ), L(Y ) = 0.</p><p>To obtain an explicit convergence rate to the above limit, we observe that</p><p>Sending k &#8594; &#8734; on both sides and applying the bound (25), we obtain the desired rate:</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.2.3">Step 3: General Noise</head><p>Steps 1 and 2 above complete the proof of Theorem 2 for Gaussian noise. In this step, we consider general noise. To this end, we consider two sequences</p><p>, where Y &#8242; t (&#945;) is driven by some general noise</p><p>is driven by Gaussian noise w t whose first two moments match those of w &#8242; t . The crucial idea in this step is to use a multivariate Berry-Esseen bound in Wasserstein distance <ref type="bibr">[Bon20]</ref>, which allows us to show that there exists a coupling between w &#8242; t and w t such that for</p><p>Under this noise coupling, we apply the generalized Moreau envelope on the difference sequence, {Y</p><p>Here, the O(&#945;) term comes from the Berry-Esseen bound <ref type="bibr">[Bon20]</ref>. It follows that for some constant r 2 , we have lim</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Following the same line of arguments in</head><p>Step 1, we conclude that</p><p>). Combining with the convergence rate result from Step 2 on Y (&#945;) with Gaussian noise, we obtain</p><p>).</p><p>This establishes that Y &#8242; (&#945;) with general noise converges in W 2 at a rate O(&#945; min(2r 1 ,1) 4</p><p>), which completes the proof of Theorem 2.</p><p>Proof for Q-learning: To prove Theorem 5, we need to couple the multiplicative noise for two sequences</p><p>in a similar manner as the additive noise case, with potentially mismatched stepsizes (&#945;, &#945; &#8242; ) and time indices (t, t &#8242; ). Importantly, in Step 3, in order to use the multivariate Berry-Esseen bound, we need to judiciously couple the general noisy sequence {(D &#8242; t , P &#8242; t , r &#8242; t )} with a carefully chosen Gaussian-distributed noisy sequence {(D t , P t , r t )} with matching joint covariance. Moreover, to obtain tight estimates for the squared distance of the form E&#8741;Y</p><p>c , we need to isolate the expected operator H from the noisy update (11). Doing so leads to more error terms that need to be carefully controlled.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.3">Proof Outline for Theorem 3 (Bias Characterization)</head><p>Theorem 1 implies that the stochastic process {Y (&#945;) t } t&#8805;0 converges weakly in W 2 to a random variable Y (&#945;) corresponding to its stationary distribution. At stationarity we have the following equation in distribution:</p><p>Taking the expectation on both sides of the above equation yields</p><p>Recall that the operator T is g &#8226; F decomposable in a local neighborhood B d (&#952; * , &#1013;) of &#952; * . We decompose the right-hand side of the above equation into two parts:</p><p>For the term T 1 , we make use of the contraction property of T and a concentration inequality to show that lim &#945;&#8594;0 T 1 = 0. To analyze the term T 2 , we consider two cases.</p><p>Case 1: If g is smooth, then T is smooth on B d (&#952; * , &#1013;). By Taylor expansion of T and an argument similar to the proof of lim &#945;&#8594;0 T 1 = 0, we have lim &#945;&#8594;0</p><p>By smoothness and contraction properties of T , we can argue that E[Y ] = 0. Case 2: If g is nonsmooth, then by Taylor expansion of F and continuity of g, we have</p><p>We further consider two sub cases. (a) If &#8711;F (0) = 0, we have</p><p>By equation (26), we obtain</p><p>Taking &#945; &#8594; 0 to both sides of the above equation, we can finally obtain</p><p>Proof for Q-learning: In Theorem 6 we distinguish two types of MDP. When the MDP is Type A, the analysis is similar to Case 2(b) above. When MDP is Type B, the dynamic of Q-learning is locally linear around &#952; * . Therefore, the T 2 term above is almost proportional to E[Y (&#945;) ]. For T 1 , since the noise has finite (2n)-th moment, we can prove</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="6">Numerical Experiments</head><p>In this section, we provide numerical experiments for SA with additive noise and Q-learning.</p><p>For SA with additive noise, we consider the example in Section 1.1 with b = 0. We run the update (7) initialized at &#952; (&#945;) 0 = 1, with stepsize &#945; &#8712; {0.05, 0.1, 0.2, 0.4}. <ref type="foot">3</ref> In Fig. <ref type="figure">2</ref>(a), we plot the &#8467; 1 error &#8741;&#952; -&#952; * &#8741; 1 for the tail-averaged (TA) iterates &#952;(&#945;) 0,k , and the RR extrapolated iterates &#952;(&#945;) 0,k with &#946; = 1 2 . Theorems 2 and 3 show that the asymptotic bias of the TA iterates is &#920;( &#8730; &#945;), which can be reduced by RR extrapolation o( &#8730; &#945;). This bias reduction effect can be observed in Fig <ref type="figure">2(a</ref>) by comparing the final errors for TA and RR iterates.</p><p>For Q-learning, we randomly generate an MDP with 3 states and 2 actions. The expected reward function r is sampled uniformly from [0, 1] |S||A| , and the rows of the transition kernel P are sampled from Dirichlet(1), where 1 is the all-one vector. This random MDP is almost surely in Type B. We then generate Type A MDP by having the first two actions of the first state share the same transition and expected reward. The observed rewards are Gaussian: r t &#8764; N (r, 0.3I). We run Synchronous Q-learning initialized at q (&#945;) 0 = 1 with stepsize &#945; &#8712; {0.02, 0.04, 0.08, 0.16}. Theorem 5 and 6 show that for Type A MDP, the bias for TA is &#8730; &#945; and can be order-wise reduced by RR extrapolation. This prediction is consistent with Fig <ref type="figure">2(b)</ref>. By Theorem 6 and the discussion in Section 4.3, for Type B MDP the bias is already small and of order O(&#945; 3 4 ), for which RR extrapolation may not lead to obvious improvement. This is consistent with the result in Fig <ref type="figure">2(c)</ref>.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="7">Additional Related Work</head><p>In this section, we discuss the existing results that are most relevant to our work.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="7.1">Results on SA and SGD</head><p>The study of SA and SGD traces its origins to the seminal work by Robbins and Monro <ref type="bibr">[RM51]</ref>. Classical works focus on diminishing stepsize regime <ref type="bibr">[RM51,</ref><ref type="bibr">Blu54]</ref> and have established almost sure asymptotic convergence for SA and SGD algorithms. Subsequent works <ref type="bibr">[Rup88,</ref><ref type="bibr">Pol90]</ref> propose the iterate averaging technique, now known as Polyak-Ruppert (PR) averaging, to accelerate convergence. The asymptotic convergence theory of SA and SGD is well-developed and extensively addressed in many exemplary textbooks [KY03, BMP12, WR22].  Some recent works [CZD + 22, CBD22] study the non-asymptotic convergence with diminishing stepsize. The recent work [CMZ23] establishes the high probability bound on the estimation error of contractive SA with diminishing stepsize. Recently, the study of constant stepsizes in SA and SGD has gained popularity. Many works in this line assume i.i.d. data. When using constant stepsize, one loses the almost sure convergence guarantee in the diminishing stepsize sequence regime, and at best can achieve distributional convergence, as shown in [DDB20, YBVE21, CMM22, HCX23b, ZX24]. Furthermore, a recurrent observation in the literature is the presence of asymptotic bias when using constant stepsize in SA, i.e., E[&#952; (&#945;) ] &#824; = &#952; * . When the SA update is locally smooth, the asymptotic bias has been demonstrated to be of &#920;(&#945;) order in [DDB20, HCX23b, ZX24]. The work [YBVE21] considers nonsmooth SA but only provides an upper bound for the asymptotic bias, i.e. |E[&#952; (&#945;) ]-&#952; * | &#8804; c &#8730; &#945;. Many papers provide non-asymptotic MSE upper bounds. The work in [LS18, MLW + 20] studies linear SA under i.i.d. data and provides an upper bound on the MSE. There are also works that analyze the MSE with Markovian data, such as [SY19, MPWB21, DMN + 21, DMNS22]. The work in [CMSS23, CMSS20] introduce the generalized Moreau envelope (GME) to analyze the MSE of general contractive SA. In our work, we make use of the GME, but we extend this technique to analyze different and more general problems, specifically, generalizing to obtain upper bounds for any 2n-th moment, proving weak convergence of SA iterates and proving steady-state convergence as stepsize &#945; diminishes to 0.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="7.2">Applications in Reinforcement Learning</head><p>Many widely employed iterative algorithms in reinforcement learning (RL) can be reformulated as SA problems <ref type="bibr">[SB18,</ref><ref type="bibr">Ber19]</ref>. Among those, the two most well-known algorithms are the temporal-difference (TD) learning for policy evaluation [Sut88, DS94] and Q-learning for optimal policy learning <ref type="bibr">[WD92]</ref>. The TD algorithms when incorporating linear function approximation can be cast into the framework of linear SA. Q-learning is a nonsmooth and nonlinear contractive SA, and has also been studied extensively in both classical works [Tsi94, Sze97, EDMB03] and recent works [CZD + 22, CMSS23]. The work <ref type="bibr">[ZX24]</ref> studies the stationary distribution of asynchronous Q-learning with Markovian data and characterizes the asymptotic bias under the assumption that MDP has no tied state.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="7.3">Nonsmooth Function Class</head><p>Nonsmooth functions have been studied in many works, such as semi-smoothness in <ref type="bibr">[Mif77]</ref>, identifiable surfaces in <ref type="bibr">[Wri93]</ref>, UV-structures in [LOS00, MS05], partly smoothness in <ref type="bibr">[Lew02]</ref>, g &#8226; F decomposition in <ref type="bibr">[Sha03,</ref><ref type="bibr">Sag13]</ref> and minimal identifiable sets in <ref type="bibr">[DL14,</ref><ref type="bibr">DDJ23]</ref>. In our work, we adopt the definition in <ref type="bibr">[Sha03]</ref> and extend it to a multidimensional function space to define the nonsmooth SA.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="7.4">Results on Steady-State Convergence</head><p>The steady-state convergence is commonly studied in the realm of stochastic processes, with one well-known application being the steady-state convergence in queueing networks. As discussed, the classical method is through justifying the interchange of limits, as seen in [GZ06, Gur14, YY16, YY18]. An alternative approach is through the basic adjoint relationship (BAR) approach, which studies the generator of the Markov process, i.e., E[Gf (Y (&#945;) )] = 0 as &#945; &#8594; 0 [BDM17, <ref type="bibr">BDM24,</ref><ref type="bibr">CMM22]</ref>. Another line of work related to steady-state convergence focuses on the unadjusted Langevin algorithm (ULA) <ref type="bibr">[DM17,</ref><ref type="bibr">DM19]</ref>. These works take an approach similar to the justification of limit interchange in queueing networks, in which they first demonstrate the convergence of ULA to the corresponding stochastic differential equation (SDE), and then relate the convergence to the stationary distribution of the SDE.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="8">Conclusion</head><p>In this work, we studied nonsmooth contractive SA with a constant stepsize. We developed prelimit coupling techniques for establishing steady-state convergence and characterizing the asymptotic bias, highlighting the impact of nonsmoothness on steady-state behavior. Our coupling techniques also bear potential for other nonsmooth dynamical systems such as piecewise smooth diffusion, stochastic differential equations and their discretization. Of immediate interest are to obtain more refined characterization of the steady-state distribution Y (&#945;) and its limit Y , such as higher moment results and other functionals of the distribution and obtain non-asymptotic results as a function of &#945; and the level of nonsmoothness. Generalizing our results to general noise settings is another interesting future direction. For additive martingale difference noise, we believe the current analysis can be combined with an appropriate martingale Berry-Esseen Central Limit Theorem to establish similar distributional and steady-state convergence results. For more general multiplicative Markovian noise, however, establishing such results would require a better understanding of Markovian nonlinear SA and new coupling arguments.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>A Proof of Proposition 1</head><p>Proposition 1 follows from combining the following lemma and the property (3) in Proposition 5.</p><p>Lemma 1. For each integer n &#8805; 1, under Assumption 1 and Assumption 2(n), there exists &#951;, &#8113; such that for any &#945; &#8804; &#8113;, there exist t &#945;,n such that</p><p>holds for all t &#8805; t &#945;,n , where M &#951; (&#8226;) is defined in (21) and {c n } n&#8805;0 are universal constants that are independent with &#945; and t. Moreover, t &#945;,1 = 0.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>A.1 Proof of Lemma 1</head><p>We use induction on n to prove Lemma 1 Base Case: n = 1. By subtracting &#952; * from both side of equation ( <ref type="formula">7</ref>), we obtain</p><p>where the second equality holds because T (&#952; * ) = &#952; * . Applying the generalized Moreau envelope M &#951; (&#8226;) defined in equation ( <ref type="formula">21</ref>) to both sides of equation ( <ref type="formula">27</ref>) and by property (1) in Proposition 5, we obtain</p><p>The term in (28) can be bounded as follows:</p><p>where (i) holds because of property (4) of Proposition 5, (ii) holds because of property (3) of Proposition 5 and &#947;-contraction of T (&#8226;), and (iii) holds because of property (2) of Proposition 5.</p><p>The term in (29) can be bounded as follows:</p><p>Combining the above bounds, we obtain</p><p>cs by property (3) in Proposition 5. We can always choose a sufficient small &#951; &gt; 0</p><p>there always exists &#8113; &gt; 0 such that &#8113; &lt; 1 and 1</p><p>when &#945; &#8804; &#8113;. Therefore, for &#8704;&#945; &#8804; &#8113; and t &#8805; 0, we obtain</p><p>Taking expectation on both sides of equation ( <ref type="formula">30</ref>), we obtain</p><p>where c w = E[&#8741;w t &#8741; 2 c ] and the first inequality holds because w t is zero mean and independent with &#952; t -&#952; * . Therefore, we complete the proof for the base case.</p><p>Induction Step: Given positive integer k &#8805; 2, assume Lemma 1 holds for all n &#8804; k -1. When n = k, take k-th moment to both side of equation (30) and we obtain</p><p>We next analyze S 1 and S 2 . For S 1 we have</p><p>where (i) holds by induction hypothesis and taking t to be sufficiently large. For S 2 we have</p><p>.</p><p>By induction hypothesis and taking t to be sufficiently large, we conclude that S 2 &#8712; O(&#945; k+1 ).</p><p>Combining the bound of S 1 , S 2 with equation (31), we obtain</p><p>Therefore, for &#8704;&#945; &#8804; &#8113;, there exist t &#945;,k &gt; 0 such that</p><p>, where c k are universal constants that are independent with &#945; and t.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>B Proof of Theorem 1</head><p>We prove the three properties stated in Theorem 1 in the next three subsections, respectively.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>B.1 Unique Limit Distribution</head><p>We consider a pair of coupled , {&#952;</p><p>t } t&#8805;0 and {&#952;</p><p>[2]</p><p>t } t&#8805;0 , defined as</p><p>Here {&#952;</p><p>[1]</p><p>t } t&#8805;0 and {&#952;</p><p>[2]</p><p>t } t&#8805;0 are two iterates coupled by sharing {w t } t&#8805;0 . We assume that the initial iterates &#952;</p><p>[1] 0 and &#952; [2]</p><p>0 may depend on each other. Taking the difference of the two equations in (32), we obtain</p><p>Applying the generalized Moreau envelope M &#951; (&#8226;) defined in equation ( <ref type="formula">21</ref>) to both side of above equation and by property (1) in Proposition 5, we obtain</p><p>Taking expectation to both side of above equation, we obtain</p><p>.</p><p>When &#945; &#8804; 1, we obtain</p><p>where </p><p>Combining the bound for T 1 and T 2 , there exists &#8113;&#8242; &#8804; &#8113; such that</p><p>t )], for &#8704;&#945; &#8804; &#8113;&#8242; . Therefore, we have</p><p>decays geometrically. Note that equation (33) always holds for any joint distribution of initial iterates (&#952;</p><p>-1 to denote a random variable that satisfies &#952; -1 is independent of {x t } t&#8805;0 . Finally, we set &#952;</p><p>Given that &#952;</p><p>-1 is independent with {w t } t&#8805;-1 , we can prove &#952;</p><p>t+1 for all t &#8805; 0 by comparing the dynamic of (&#952;</p><p>t ) t&#8805;0 as given in equations ( <ref type="formula">32</ref>) and (34). We thus have</p><p>where the second inequality follows from equation (33). It follows that</p><p>Consequently, {L(&#952;</p><p>t )} t&#8805;0 forms a Cauchy sequence with respect to the metric W 2 . Since the space P 2 (R d ) endowed with W 2 is a Polish space, every Cauchy sequence converges [Vil09, Theorem 6.18]. Furthermore, convergence in Wasserstein 2-distance also implies weak convergence [Vil09, Theorem 6.9]. Therefore, we conclude that the sequence {L(&#952;</p><p>t )} t&#8805;0 converges weakly to a limit distribution &#956; &#8712; P 2 (R d ). Next, we show that &#956; is independent of the initial iterate distribution of &#952;</p><p>[1] 0 . Suppose there exists another sequence { &#952; [1]</p><p>t } t&#8805;0 with a different initial distribution that converges to a limit &#181;. By triangle inequality, we have</p><p>Note that the last step holds since</p><p>-&#8594; 0 by equation (58). We thus have W 2 (&#956;, &#181;) = 0, which implies the uniqueness of the limit &#956;.</p><p>Finally, the following lemma bounds the second moment of the limit random vector &#952; (&#945;) .</p><p>Lemma 2. Under Assumption 2(1), when &#945; &#8804; &#8113;&#8242; , we obtain</p><p>. Proof for Lemma 2. We have shown that the sequence {&#952; t } t&#8805;0 converges weakly to &#952; (&#945;) in P 2 (R d ). It is well known that weak convergence in P 2 (R d ) is equivalent to convergence in distribution and the convergence of the first two moments. As a result, we have</p><p>Taking t &#8594; &#8734; on both sides of equation (8) in Proposition 1 with n = 1 and combining with equation ( <ref type="formula">35</ref>) yields</p><p>Therefore, we have</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>B.2 Invariance</head><p>Moreover, we will show that the unique limit distribution &#956; is also a stationary distribution for the Markov chain {&#952; t } t&#8805;0 , as stated in the following lemma.</p><p>Lemma 3. Let {&#952; t } t&#8805;0 and {&#952; &#8242; t } t&#8805;0 be two trajectories of iterates in equation (32), where L (&#952; 0 ) = &#956; and</p><p>where the quantity &#961; :=</p><p>In particular, for any t &#8805; 0, if we set</p><p>Proof of Lemma 3. We couple the two processes {&#952; t } t&#8805;0 and {&#952; &#8242; t } t&#8805;0 such that</p><p>Since W 2 is defined by infimum over all couplings, we have</p><p>where &#961; =</p><p>By triangle inequality, we obtain</p><p>where the second inequality holds by Lemma 3 and last step comes from the weak convergence result. Therefore, we have proved that {&#952; t } t&#8805;0 converges to a unique stationary distribution &#956;.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>B.3 Convergence rate</head><p>Consider the coupled processes defined as equation (32). Suppose that the initial iterate &#952;</p><p>[2] 0 follows the stationary distribution &#956;, thus L(&#952;</p><p>t ) = &#956; for all t &#8805; 0. By equation (33), we have for all t &#8805; 0 :</p><p>Lemma 2 states that the second moment of &#952; (&#945;) is bounded by a constant. Combining this bound with above equation, we obtain the desired bound</p><p>, where c is a universal constant that is independent with &#945; and t.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>C Proof of Theorem 2</head><p>In this section, we prove Theorem 2, which establishes steady-state convergence under the additive noise setting. We follow the three-step strategy outlined in Section 1.2. We start by using equation ( <ref type="formula">7</ref>) to obtain the following dynamic for Y t :</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>C.1 Step 1: Gaussian Noise and Rational Stepsize</head><p>We consider a pair of coupled {Y t } t&#8805;0 and {Y &#8242; t } t&#8805;0 , defined as</p><p>where {w &#8242; t } t&#8805;0 are i.i.d noise with normal distribution, zero mean and the same variance as {w t } t&#8805;0 and k &#8805; 1 is an integer. Because {w &#8242; t } t&#8805;0 are i.i.d noise with normal distribution,</p><p>has the same distribution as w &#8242; t . Direct calculation gives</p><p>Combining equations ( <ref type="formula">38</ref>) and (39), we obtain</p><p>where A collects all but the first term on the RHS. Applying the generalized Moreau envelope M &#951; (&#8226;) defined in equation ( <ref type="formula">21</ref>) to both sides of above equation and by property (1) in Proposition 5, we obtain</p><p>The following lemmas, proved in Sections C.1.1 and C.1.2 to follow, control the T 1 and T 2 terms above.</p><p>Lemma 4. Under the setting of Theorem 2, we have</p><p>Lemma 5. Under the setting of Theorem 2, we have</p><p>Plugging the above bounds for T 1 and T 2 into equation (40), we obtain</p><p>By the similar argument as in the proof of Lemma 1, we can always choose proper &#951;, &#8113; such that for &#8704;&#945; &#8804; &#8113;, there exist t &#945; such that for all t &#8805; t &#945; , we obtain</p><p>By triangle inequality, we have</p><p>where (i) follows from Theorem 1, (ii) holds by the definition of W 2 distance, and (iii) is true by Proposition 5. Therefore, we have that for all k &#8712; N + and &#945; &gt; 0,</p><p>When k &#8712; Q + , k &gt; 1 and &#945; &gt; 0, let k = p q . We have</p><p>where (i) holds because &#945; p = &#945; k q and &#945; k &#8804; &#945;. Then, for any rational sub-sequence {&#945; j } &#8734; j=0 , &#945; j &#8594; 0, {L(Y (&#945;j ) )} &#8734; j=0 is a Cauchy sequence with respect to W 2 , therefore has a limit. Assume we have two different rational sub-sequence {&#945; j } &#8734; j=0 and {&#946; j } &#8734; j=0 such that the limits of {L(Y (&#945;j ) )} &#8734; j=0 and {L(Y (&#946;j ) )} &#8734; j=0 are different with respect to W 2 . Let L( &#562; ) be the limit of {L(Y (&#945;j ) )} &#8734; j=0 and L( &#374; ) be the limit of {L(Y (&#946;j ) )} &#8734; j=0 . Then, there exists &#1013; &gt; 0, such that W 2 L( &#562; ), L( &#374; ) &gt; &#1013;. Let &#947; 2j = &#945; j , &#947; 2j+1 = &#946; j . Then, {&#947; j } &#8734; j=0 forms a rational sequence and &#947; &#8594; 0. Then, we obtain</p><p>which contradicts with the fact that {L(Y (&#947;j ) )} &#8734; j=0 is a Cauchy sequence with respect to W 2 . Therefore, for any rational sub-sequence {&#945; j } &#8734; j=0 , &#945; j &#8594; 0, {L(Y (&#945;j ) )} &#8734; j=0 converge to a unique limit with respect to W 2 . That is, there exists a unique random variable Y such that</p><p>This completes the first step of the proof of Theorem 2.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>C.1.1 Proof of Lemma 4 on T 1</head><p>By property (4) in Proposition 5 and {w &#8242; kt+k-1-j } k-1 j=0 being i.i.d. zero mean noise and independent with Y t and Y &#8242; kt , we obtain</p><p>Below, we bound the terms T 11 &#8764; T 15 separately.</p><p>The T 11 Term: We begin with</p><p>x increases monotonically when x &#8805; &#945;. Therefore, when &#945; &#8804; 1, we obtain</p><p>By Cauchy-Schwarz inequality, we obtain</p><p>where (i) holds by the following Corollary 1(1) and choosing a sufficiently large t (note that Corollary 1 is parameterized by an integer n &#8805; 1). Therefore, we conclude that T 11 &#8712; O(&#945; 2 ).</p><p>Corollary 1 (n). For integer n &#8805; 1, under Assumption 2(n), there exists &#8113; such that for any &#945; &#8804; &#8113;, there exists t &#945;,n &gt; 0 and</p><p>where &#8741; &#8226; &#8741; is an arbitrary norm and {c n } n&#8805;1 and {c &#8242; n } n&#8805;1 are universal constants that are independent with &#945; and t. Moreover, t &#945;,1 = 0.</p><p>Proof of Corollary 1. By the equivalence of all norms on R d , we can obtain the Corollary 1(n) by dividing &#945; n to both sides of equation (8) in Proposition 1(n).</p><p>The T 12 Term: Turning to T 12 , we have</p><p>The T 13 Term: For T 13 , by Cauchy-Schwarz inequality, we obtain</p><p>For the second expectation term on above RHS, we have</p><p>where (i) holds because of Assumption 3. By Taylor expansion, when &#945; &#8804; 1, there always exist random variable &#955; 1 , &#955; 2 &#8712; [0, 1] n such that</p><p>, where we use &#8711;F (&#955; i , &#8730; &#945;Y &#8242; kt ) to denote the vector that [&#8711;F (&#955; i ,</p><p>For &#8704;&#1013; 0 &gt; 0, by continuity of g(&#8226;), &#8707;&#948; 0 &gt; 0, such that &#8741;g(&#952;) -g(&#8711;F (0))&#8741; 2 &#8804; &#1013; 0 when &#8741;&#952; -&#8711;F (0)&#8741; 2 &#8804; &#948; 0 . By the continuity of &#8711;F (&#8226;) at 0, &#8707;&#948; 1 &gt; 0, such that &#8741;&#8711;F (&#952;) -&#8711;F (0)&#8741; 2 &#8804; &#948; 0 when &#8741;&#952;&#8741; &#8804; &#948; 1 . Therefore, we obtain &#8741;g(&#8711;F (&#952;)) -g(&#8711;F (0))&#8741; 2 &#8804; &#1013; 0 when &#8741;&#952;&#8741; &#8804; &#948; 1 . Given &#945;</p><p>Therefore, the variables within the term T 131 are always bounded, which implies lim &#945;&#8594;0 T 131 = 0. Therefore, we have</p><p>For the term in (46), by Cauchy-Schwarz inequality and Markov inequality, we obtain</p><p>where the last step follows from</p><p>. Combining all the analysis together, we obtain that (44) &#8712; o(&#945;), which in turn implies T 13 &#8712; o(&#945;).</p><p>The T 14 Term: For T 14 , we have</p><p>where (i) holds by equation (42).</p><p>The T 15 Term: Finally, we turn to T 15 :</p><p>By equation (38), we obtain</p><p>Therefore, we obtain</p><p>We analyze three terms T 151 , T 152 , T 153 separately. Note that</p><p>where (i) holds by equation (42). For T 152 , we have</p><p>Lastly, we have</p><p>where (i) holds because Y t and Y &#8242; kt are independent with w &#8242; kt+k-1-j-l for j = 0, . . . , k-1 and l = 1, . . . , k-1-j, (ii) follows as</p><p>, and (iii) holds because</p><p>2 ). Putting the bounds of T 151 , T 152 and T 153 together, we obtain T 15 &#8712; O(&#945; 3 2 ). Finally, combining our bounds for T 11 &#8764; T 15 , we have</p><p>thereby completing the proof of Lemma 4.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>C.1.2 Proof of Lemma 5 on T 2</head><p>By Cauchy-Schwarz inequality, we obtain</p><p>Below, we bound T 21 &#8764; T 25 separately.</p><p>The T 21 Term: We begin with T 21 :</p><p>where (i) holds by equation (42).</p><p>The T 22 Term: For T 22 , we have</p><p>The T 23 Term: Using the bound (44) &#8712; o(&#945;) and the equivalence of all norms in R d , we obtain that T 23 &#8712; o(&#945; 2 ).</p><p>The T 24 Term: By Cauchy-Schwarz inequality, we obtain</p><p>where (i) holds because</p><p>, and (ii) holds by equation ( <ref type="formula">42</ref>).</p><p>The T 25 Term: For T 25 , we have</p><p>where the last step holds because</p><p>Combining pieces, we conclude that</p><p>which completes the proof of Lemma 5.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>C.2 Step 2: General Stepsize</head><p>In this subsection, we aim to prove that there exists an &#945; 0 such that L(Y (&#945;) ) is continuous in &#945; when &#945; &#8712; (0, &#945; 0 ) with respect to W 2 . Let us consider two stepsizes &#945; &gt; 0 and &#945; &#8242; &gt; 0. For simplicity, we will let {Y t } t&#8805;0 and {Y &#8242; t } t&#8805;0 denote the sequence associated with stepsize &#945; and &#945; &#8242; , respectively. We couple the two sequences {Y t } t&#8805;0 and {Y &#8242; t } t&#8805;0 by letting them share the same noise {w &#8242; t } t&#8805;0 :</p><p>Applying the generalized Moreau envelope M &#951; (&#8226;) defined in equation ( <ref type="formula">21</ref>) to both side of above equation and by property (1) in Proposition 5, we obtain</p><p>Below we separately bound the T 1 and T 2 terms.</p><p>Bounding the T 1 Term: By property (4) in Proposition 5 and w &#8242; t being i.i.d zero mean noise and independent with Y t and Y &#8242; t , we obtain</p><p>Below, we bound T 11 &#8764; T 13 separately, beginning with T 11 :</p><p>where (i) holds because we can always choose a proper &#951; such that ucm lcm &#8804;<ref type="foot">foot_4</ref> &#8730; &#947; . We next have</p><p>, where we use</p><p>. Similarly, we have</p><p>, where the last inequality holds because &#948; &#8804; min((</p><p>Bounding the T 2 Term: We next have</p><p>Below, we bound T 21 &#8764; T 24 separately. We begin with</p><p>where the last inequality holds because &#948; &#8804; min(( 1 &#8730; &#947; -1)&#945;, 1 2 &#945;). The next three terms satisfy</p><p>Combining the above bounds for T 1 and T 2 and using the fact that there exist an &#945; 0 such that 0 &lt; 1 -2(1 -&#947; 1 4 )&#945; 0 + O(&#945; 2 0 ) &lt; 1, we see that for any &#945; &#8804; &#945; 0 , there exist t &#945; such that for any t &#8805; t &#945; , we obtain</p><p>.</p><p>Then, we obtain</p><p>Hence,</p><p>, where c is a universal constant that is independent with &#945;, &#945; &#8242; . Then, given &#945; &gt; 0, for &#8704;&#1013; &gt; 0, we can choose a sufficient small &#948; &#1013; such that</p><p>Then, when &#945; &#8242; is selected with |&#945; -&#945; &#8242; | &#8804; &#948; &#1013; , we obtain</p><p>Therefore, we complete the proof of continuity of L(Y (&#945;) ) with respect to W 2 . Recall that lim &#945;&#8594;0,&#945;&#8712;Q</p><p>Thus, for &#8704;&#1013; &gt; 0, there exist &#948; &gt; 0, such that for all rational &#945; &#8804; &#948;, W 2 L(Y (&#945;) ), L(Y ) &#8804; &#1013; 2 . Given arbitrary real number r such that 0 &lt; r &#8804; &#948; 2 , there exist q(r)</p><p>where the second inequality holds because q(r) &#8804; &#948; 2 + &#948; 2 = &#948;. We conclude that there exist a unique limit L(Y ) such that lim</p><p>This completes the second step of the proof of Theorem 2.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>C.3 Step 2.5: Convergence Rate under Gaussian Noise</head><p>By triangle inequality, we obtain the desired convergence rate:</p><p>C. <ref type="bibr">4</ref> Step 3: General Noise</p><p>By Section C.1, C.2 and C.3, we prove that under the noise with Gaussian distribution, there exist a unique random variable Y such that Y (&#945;) converge to Y with respect to W 2 . In this subsection, we aim to prove that under general i.i.d zero mean noise with the same variance, the convergence result still holds and the limit is still Y . Fix the stepsize &#945; &gt; 0. We consider two sequences {Y (&#945;) t } t&#8805;0 and {Y &#8242; t (&#945;) } t&#8805;0 , where {Y (&#945;) t } t&#8805;0 is associated with general noise {w t } t&#8805;0 , and {Y &#8242; t (&#945;) } t&#8805;0 is associated with Gaussian distributed noise {w &#8242; t } t&#8805;0 . When the context is clear, we drop the supperscript (&#945;) for the ease of exposition. We will couple {Y t } t&#8805;0 and {Y &#8242; t } t&#8805;0 as follows:</p><p>where w t , w &#8242; t have zero mean and the same variance. Here w t and w &#8242; t are not necessarily independent of each other, and we assume that w t has finite fourth moment. The specific coupling between {w &#8242; t } t&#8805;0 and {w t } t&#8805;0 will be specified later.</p><p>Let &#954; = &#8970;&#945; -1 2 &#8971;. Direct calculation gives</p><p>(1 -&#945;) j-1 w &#954;t+&#954;-j .</p><p>and</p><p>Taking the difference of the last two equations, we get</p><p>where we collect in A all but the first term on the RHS. Applying the generalized Moreau envelope M &#951; (&#8226;) defined in equation ( <ref type="formula">21</ref>) to both side of above equation and by property (1) in Proposition 5, we obtain</p><p>The following lemmas, proved in Sections C.4.1 and C.4.2 to follow, control the T 1 and T 2 terms above.</p><p>Lemma 6. Under the setting of Theorem 2, we have</p><p>Lemma 7. Under the setting of Theorem 2 and some proper couplings between {w t } t&#8805;0 and {w &#8242; t } t&#8805;0 , we have</p><p>Plugging the above bounds for T 1 and T 2 into equation ( <ref type="formula">50</ref>), there exist an &#945; 0 such that for any &#945; &#8804; &#945; 0 , there exist t &#945; such that for any t &#8805; t &#945; , we obtain</p><p>Therefore, we obtain lim</p><p>By triangle inequality, we have</p><p>Therefore, by equation (48), we obtain</p><p>This completes the last step of the proof of Theorem 2. We have proved Theorem 2.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>C.4.1 Proof of Lemma 6 on T 1</head><p>By property (4) in Proposition 5 and w &#954;t+&#954;-j and w &#8242; &#954;t+&#954;-j being zero mean noise and independent with Y &#954;t and Y &#8242; &#954;t , we obtain</p><p>Below, we bound terms T 11 &#8764; T 14 separately.</p><p>where the last inequality holds because we can always choose a proper &#951; such that ucm lcm &#8804; 1 &#8730; &#947; .</p><p>By equation ( <ref type="formula">49</ref>), we obtain</p><p>Therefore, we obtain</p><p>Observe that</p><p>where (i) holds by equation ( <ref type="formula">43</ref>). We also have</p><p>where (i) follows as <ref type="formula">1</ref>) for all t &#8805; 0. Lastly, for term T 123 , we have</p><p>where (i) holds because Y &#954;t and Y &#8242; &#954;t are independent with w &#954;t+&#954;-j-l , (ii) follows as ). For T 14 , we have</p><p>where in (i) we use</p><p>. Combining the bound for T 11 &#8764; T 14 together, we obtain</p><p>thereby completing the proof of Lemma 6.</p><p>Below, we bound T 21 &#8764; T 25 separately. For T 21 :</p><p>Next, for T 22 , we have</p><p>Continuing, we have</p><p>Lastly, we have</p><p>We restate Theorem 1 in <ref type="bibr">[Bon20]</ref> in the following lemma.</p><p>Lemma 8 (Theorem 1 in <ref type="bibr">[Bon20]</ref>). Let X 1 , . . . , X n be n i.i.d random variables taking values in R d with zero mean and identity variance matrix. Let &#957; be the d-dimensional standard Gaussian measure and X &#8242; 1 , . . . , X &#8242; n be n i.i.d random variables distributed as &#957;.</p><p>Then, we have</p><p>where W 2,2 denotes the Wasserstein distances of order 2 with &#8467; 2 -norm.</p><p>We can always choose a coupling between w t and w &#8242; t such that</p><p>Because C is positive semidefinite, by [HJ12, Theorem 7.2.6], there always exists a symmetric matrix</p><p>. Then, by Lemma 8, we obtain</p><p>where all the infimums are took by considering all the joint distributions with the same marginal distribution.</p><p>Recall that &#954; = &#8970;&#945; -1 2 &#8971;, we obtain</p><p>thereby completing the proof of Lemma 7</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>D Proof of Theorem 3</head><p>By equation (37) and Theorem 1, we obtain the following equation in distribution:</p><p>After taking expectation to both sides of the above equation, we obtain</p><p>By Cauchy-Schwarz inequality, we obtain</p><p>where (i) holds because the equivalence of all norms in R d , Fatou's lemma [Dur19, Exercise 3.2.4] and Corollary 1(1). Therefore, we obtain lim &#945;&#8594;0 T 1 = 0. Below, we discuss two cases.</p><p>Case 1: If g(&#8226;) is smooth, because F (&#8226;) is also smooth, we conclude that T (&#8226;) is smooth in B d (&#952; * , &#1013;) by chain rule. Therefore, we obtain</p><p>By Cauchy-Schwarz inequality, we obtain</p><p>&#8712; o(1),</p><p>P(&#945;</p><p>Therefore, we obtain lim &#945;&#8594;0</p><p>Taking &#945; &#8594; 0 to both sides of equation (51), we obtain</p><p>, where &#1013; 1 &lt; 1. Then, we have &#563;&#1013;1 &#8712; B d (0, &#1013;). Therefore, we obtain</p><p>By the smoothness of T (&#8226;) in B d (&#952; * , &#1013;), we can always have an efficiently small &#1013; 1 such that</p><p>which contradicts with the fact that T (&#8226;) is a contraction. Therefore, we know y = 0 and</p><p>is not smooth, by equation (51), we obtain</p><p>For the first term, we have</p><p>=0.</p><p>Therefore, we have</p><p>P(&#945;</p><p>Therefore, we obtain</p><p>By [Dur19, Exercise 3.2.5], we obtain</p><p>If &#8711;F (0) = 0, we obtain E[Y ] = 0. Now suppose that &#8711;F (0) &#824; = 0. Let h(Y ) := g(&#8711;F (0)Y ). If there exists i &#8712; [d] such that the subdifferential or supdifferential of h i (&#8226;) at 0 is not singleton. Without loss of generality, the subdifferential of h 1 (&#8226;) at 0 is not singleton. Then, there exists</p><p>Because h 1 (Y ) -z T j Y = 0 are always nonnegative for j = 1, 2. We have h 1 (Y ) -z T j Y = 0 almost surely for j = 1, 2. Therefore, we have z</p><p>By equation (37) and Theorem 1, we obtain the following equation in distribution.</p><p>Taking second moment to both sides of the above equation, we obtain</p><p>) 2 ] and dividing &#945; to both sides of the above equation, we obtain</p><p>By equation ( <ref type="formula">52</ref>) and Theorem 2, we obtain lim &#945;&#8594;0 T 1 = 0. By Cauchy-Schwarz inequality, we can bound T 2 and T 3 as follows</p><p>= 0.</p><p>Because Var(w) is positive definite, we obtain</p><p>However, we have T 4 = 0 by letting &#945; &#8594; 0, which contradicts with the fact that T 4 &gt; 0. Therefore, we have E[Y ] &#824; = 0.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>E Proof of Proposition 2</head><p>We first present the following lemma, whose proof is given at the end of this subsection Lemma 9. Consider iterates {q t } t&#8805;0 generated by equation (10). For integer n &#8805; 1, under assumption 4(n), there exists &#951;, &#945; n such that for any &#945; &#8804; &#945; n , there exist t &#945;,n such that</p><p>holds for all t &#8805; t &#945;,n , where M &#951; (x) is constructed by equation (21) and {c n } n&#8805;1 are constants that are independent with &#945; and t. Moreover, t &#945;,1 = 0.</p><p>Then, by the property (3) in Proposition 5, we complete the proof of Proposition 2</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>E.1 Proof of Lemma 9</head><p>We use the induction to give the proof of Lemma 9 Base Case: n = 1. By subtracting q * to both side of equation (10), we obtain</p><p>where (i) holds by &#947;DP f (q * ) + Dr = Dq * and denoting</p><p>) holds by denoting A t = &#947;D t P t -&#947;DP , B t = D -D t and C t = D t r t -Dr, thereby {(A t , B t , C t )} t&#8805;0 are i.i.d. zero mean random variables and (A t , B t , C t ) is independent with q t . By [CMZ23, Proposition 3.3],</p><p>we obtain that T (&#8226;) is a &#947; 0 -contraction with respect to &#8741; &#8226; &#8741; c , where</p><p>Applying the generalized Moreau envelope M &#951; (&#8226;) defined in equation ( <ref type="formula">21</ref>) to both sides of equation ( <ref type="formula">53</ref>) and by property (1) in Proposition 5, we obtain</p><p>For T 1 we have</p><p>where (i) follows from property (4) of Proposition 5, (ii) follows from property (3) of Proposition 5 and &#947; 0 -contraction of T (&#8226;), and (iii) follows from property (2) of Proposition 5. For T 2 we have</p><p>Combining the bound for T 1 , T 2 , we obtain</p><p>Recall that ucm lcm = 1+&#951;u 2 cs 1+&#951;l 2 cs by property (3) in Proposition 5. We can always choose a sufficient small</p><p>Furthermore, there always exists</p><p>Therefore, for &#8704;&#945; &#8804; &#945; 0 and t &#8805; 0, we obtain</p><p>Taking expectation to equation (55), there exist &#945; 1 &#8804; &#945; 0 such that for &#8704;&#945; &#8804; &#945; 1 , we obtain</p><p>where (i) holds because the second moment of (A t , B t , C t ) is finite and there exist &#945; 1 such that (ii) holds for &#8704;&#945; &#8804; &#945; 1 . Induction Step: Given positive integer k &#8805; 2, assume Proposition 2 holds for all n &#8804; k -1. When n = k, we let</p><p>Take k-th moment to both sides of equation (55) and we obtain</p><p>For S 1 we have</p><p>where (i) holds by induction and taking t to be sufficiently large and &#945; &#8804; min(&#945; 1 , . . . , &#945; k-1 ).</p><p>For S 2 we have</p><p>), where (i) holds by induction and taking t to be sufficiently large and &#945; &#8804; min(&#945; 1 , . . . , &#945; k-1 ).</p><p>Combining the bound of S 1 , S 2 with equation (56), we obtain</p><p>Therefore, there exist &#945; k &#8804; min(&#945; 1 , . . . , &#945; k-1 ) and for &#8704;&#945; &#8804; &#945; k , there exist t &#945;,k such that</p><p>, where c k is a constant that is independent with &#945; and t.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>F Proof of Theorem 4 F.1 Unique Limit Distribution</head><p>We consider a pair of coupled , {q</p><p>[1]</p><p>t } t&#8805;0 and {q</p><p>[2]</p><p>t } t&#8805;0 , defined as</p><p>t + &#945; &#947;D t P t f (q</p><p>Here {q</p><p>[1]</p><p>t } t&#8805;0 and {q</p><p>[2]</p><p>t } t&#8805;0 are two coupled by sharing {(D t , P t , r t )} t&#8805;0 . We assume that the initial iterates q</p><p>[1] 0 and q</p><p>[2] 0 may depend on each other. Taking difference to equation (57), we obtain</p><p>Applying the generalized Moreau envelope M &#951; (&#8226;) defined in equation ( <ref type="formula">21</ref>) to both sides of above equation and by property (1) in Proposition 5, we obtain</p><p>Taking expectations to both sides of above equation, we obtain</p><p>For T 1 we have</p><p>where (i) holds because of the property (4) of Proposition 5, (ii) and (iii) holds because of the property (2) and (3) of Proposition 5 and (iv) holds because ucm lcm = 1+&#951;u 2 cs 1+&#951;l 2 cs by property (3) in Proposition 5 and we can always choose a sufficient small &#951; &gt; 0 such that ucm lcm &#8804; 1 &#8730; &#947;0 . It is easy to verify that f (&#8226;) is a non-expansion with respect to &#8741;&#8741; c , by Cauchy-Schwarz inequality and the equivalence of all norms on R |S||A| , we obtain</p><p>Combining the bound for T 1 and T 2 , there exists &#8113;&#8242; &#8804; &#945; 1 such that</p><p>for &#8704;&#945; &#8804; &#8113;&#8242; . Therefore, we have</p><p>Therefore, W 2 2 L q</p><p>[1] t , L q</p><p>[2] t decays geometrically. Similarly to the argument in Section B.1, we see that the sequence {L(q</p><p>t )} t&#8805;0 converges weakly to a unique limit distribution &#956; &#8712; P 2 (R |S||A| ) that is independent of the initial iterate distribution of q</p><p>[1] 0 . Finally, we establish the following lemma to bound the second moment of the limit random vector q (&#945;) . Lemma 10. Under Assumption 4, when &#945; &#8804; &#8113;&#8242; 0 , we obtain</p><p>Proof for Lemma 10. We have shown that the sequence {q t } t&#8805;0 converges weakly to q (&#945;) in P 2 (R |S||A| ). It is well known that weak convergence in P 2 (R |S||A| ) is equivalent to convergence in distribution and the convergence of the first two moments. As a result, we have</p><p>Taking t &#8594; &#8734; on both sides of equation ( <ref type="formula">12</ref>) in Proposition 2 with n = 1 and combining with equation ( <ref type="formula">59</ref>) yields</p><p>Since 2&#8741;q * &#8741; 2 2 &#8712; O(1), it follows that</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>F.2 Invariance</head><p>Moreover, we will show that the unique limit distribution &#956; is also a stationary distribution for the Markov chain {q t } t&#8805;0 , as stated in the following lemma.</p><p>Lemma 11. Let {q t } t&#8805;0 and {q &#8242; t } t&#8805;0 be two trajectories of iterates in equation (57), where L (q 0 ) = &#956; and L(q &#8242; 0 ) &#8712; P 2 (R |S||A| ) is arbitrary. we have</p><p>where the quantity &#961; :=</p><p>In particular, for any t &#8805; 0, if we set L(q &#8242; 0 ) = L(q t ), then W 2 2 (L (q 1 ) , L(q t+1 )) &#8804; &#961;W 2 2 (&#956;, L(q t )) .</p><p>Proof of Lemma 11. We prove this lemma by coupling the two processes {q t } t&#8805;0 and {q &#8242; t } t&#8805;0 such that</p><p>Since W 2 is defined by infimum over all couplings, we have</p><p>By triangle inequality, we obtain W 2 (L (q 1 ) , &#956;) &#8804; W 2 (L (q 1 ) , L (q t+1 )) + W 2 (L (q t+1 ) , &#956;)</p><p>where the second inequality holds by Lemma 11 and last step comes from the weak convergence result. Therefore, we have proved that {q t } t&#8805;0 converge to a unique stationary distribution &#956;.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>F.3 Convergence rate</head><p>Consider the coupled processes defined as equation ( <ref type="formula">57</ref>). Suppose that the initial iterate q</p><p>[2] 0 follows the stationary distribution &#956;, thus L(q</p><p>[2] t ) = &#956; for all t &#8805; 0. By equation (58), we have for all t &#8805; 0 :</p><p>Lemma 10 states that the second moment of q (&#945;) is bounded by a constant. Combining this bound with above equation, we obtain</p><p>where c is a universal constant that is independent with &#945; and t.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>G Proof of Theorem 5</head><p>We can obtain the following dynamic for Y t by equation ( <ref type="formula">53</ref>)</p><p>where {(A t , B t , C t )} t&#8805;0 are zero mean variables. Define g(x) : R |S||A| &#8594; R |S| such that g s (x) := max a&#8712;A * (s)</p><p>x(s, a), and h(x, y) := f (x + y) -f (y) -g(x). Therefore, g(x) is a non-expansion mapping with respect to &#8741; &#8226; &#8741; c by [CMZ23, Proposition 3.3]. We define T 0 (q) := &#947;DP g(q) + (I -D)q and it is easy to verify that T 0 (&#8226;) is a &#947; 0 -contraction with respect to &#8741;&#8741; c . By definition of g(x) and h(x, y), we can reformulate equation (61) as</p><p>where (i) holds because we denote E t := A t f (q * ) + B t q * + C t . Furthermore, we have the following lemma to bound the second moment of h(Y t , q * &#8730; &#945; ). Lemma 12. Consider iterates {Y t } t&#8805;0 generated by equation (62) with stepsize &#945;, under the same setting as Proposition 2 with n = 2, we obtain</p><p>Proof of Lemma 12. By definition, for &#8704;s &#8712; S, we obtain</p><p>where the last inequality holds because A * (s) = arg max a&#8712;A q * (s, a).</p><p>We can easily observe that h s (Y t , q * &#8730; &#945; ) &#8805; 0. We define</p><p>Then, we can observe that when</p><p>where &#8710; = min s&#8712;S &#8710;(s). By Cauchy-Schwarz inequality, we obtain</p><p>where (i) holds because the non-expansion of f (&#8226;) and g(&#8226;) with respect to &#8741; &#8226; &#8741; c and (ii) and (iii) hold because of the following Corollary 2 with n = 2.</p><p>Corollary 2. For integer n &#8805; 1, under Assumption 4(n), there exists &#945; n &gt; 0 such that for any &#945; &#8804; &#945; n , there exist t &#945;,n &gt; 0 such that</p><p>, where &#8741; &#8226; &#8741; is an arbitrary norm and {c n } n&#8805;1 and {c &#8242; n } n&#8805;1 are universal constants that are independent with &#945; and t. Moreover, t &#945;,1 = 0.</p><p>Proof of Corollary 2. By the equivalence of all norms on R d , we can obtain the Corollary 2(n) by dividing &#945; n to both sides of equation ( <ref type="formula">12</ref>) in Proposition 2.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>G.1 Step 1: Gaussian Noise and Rational Stepsize</head><p>We consider a pair of coupled {Y t } t&#8805;0 and {Y &#8242; t } t&#8805;0 , defined as</p><p>where {(A &#8242; t , B &#8242; t , E &#8242; t )} t&#8805;0 are i.i.d. noise with normal distribution, zero mean and the same variance as {(A t , B t , E t )} t&#8805;0 and k &#8805; 1 is an integer. Therefore, (</p><p>) has the same distribution as (A &#8242; t , B &#8242; t , E &#8242; t ). Therefore, we have</p><p>where (i) holds by equation (42).</p><p>Combining equation ( <ref type="formula">64</ref>) and (65), we obtain</p><p>where R collects all but the first terms on the right hand side.</p><p>Applying the generalized Moreau envelope M &#951; (&#8226;) defined in equation ( <ref type="formula">21</ref>) to both sides of the above equation and by property (1) in Proposition 5, we obtain</p><p>The following lemmas, proved in Sections G.1.1 and G.1.2 to follow, control the T 1 and T 2 terms above.</p><p>Lemma 13. Under the setting of Theorem 5, we have</p><p>2 ).</p><p>Lemma 14. Under the setting of Theorem 5, we have</p><p>Plugging the above bounds for T 1 and T 2 into equation (66), we obtain</p><p>By the similar argument as in the proof of Lemma 1, we can always choose proper &#951;, &#8113; such that for &#8704;&#945; &#8804; &#8113;, there exist t &#945; such that for all t &#8805; t &#945; , we obtain</p><p>.</p><p>By triangle inequality, we have</p><p>Then, we can say for all k &#8712; N + and &#945; &gt; 0,</p><p>.</p><p>When k &#8712; Q + , k &gt; 1 and &#945; &gt; 0, let k = p q . Therefore, we obtain</p><p>, where (i) holds because &#945; p = &#945; k q and &#945; k &#8804; &#945;. Then, by the same argument at the end of Section C.1, there exists a unique random variable Y such that lim &#945;&#8594;0,&#945;&#8712;Q + W 2 L(Y (&#945;) ), L(Y ) = 0, thereby completing the proof of the first step of Theorem 5.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Proof of Lemma 13 on T 1</head><p>By property (4) in Proposition 5, we obtain</p><p>Below, we bound T 11 &#8764; T 16 separately.</p><p>The T 11 Term:</p><p>The T 12 Term:</p><p>By equation ( <ref type="formula">62</ref>), we obtain</p><p>Therefore, we have</p><p>By Corollary 2 with n = 2 and the equivalence of all norms on R |S||A| , we obtain</p><p>where (i) holds by equation (42). Turning to the next two terms, we have</p><p>Similarly, we have</p><p>where (i) holds because Y t and Y &#8242; kt are independent with E &#8242; kt+k-j-i for j = 1, . . . , k and i = 1, . . . , k -j. Combining the bounds for T 121 , T 122 and T 123 together, we obtain T 12 &#8712; O(&#945; 3<ref type="foot">foot_5</ref> ).</p><p>The T 13 &#8764; T 16 Terms: By Corollary 2 with n = 2, Lemma 12 and the equivalence of all norms on R |S||A| , we obtain</p><p>where (i) holds by equation (42).</p><p>.</p><p>Therefore, we obtain the bound for E[T 1 ]:</p><p>By Cauchy-Schwarz inequality, we obtain</p><p>By Corollary 2(2), Lemma 12 and the equivalence of all norms on R |S||A| , we obtain</p><p>where (i) holds by equation (42). This completes the proof of Lemma 14.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>G.2 Step 2: General Stepsize</head><p>In this subsection, we aim to prove that there exists an &#945; 0 such that L(Y &#945; ) is continuous when &#945; &#8712; (0, &#945; 0 ) with respect to W 2 . Here we use another coupling as follows:</p><p>Then, we obtain</p><p>Applying the generalized Moreau envelope M &#951; (&#8226;) defined in equation ( <ref type="formula">21</ref>) to both sides of above equation and by property (1) in Proposition 5, we obtain</p><p>Below we separately bound the T 1 and T 2 terms.</p><p>Bounding the T 1 Term: By property (4) in Proposition 5 and equation (54), we obtain</p><p>By Corollary 2 with n = 2, Lemma 12 and the equivalence of all norms on R |S||A| , we obtain</p><p>where the last inequality holds because we can always choose a proper &#951; such that ucm lcm &#8804;</p><p>.</p><p>Bounding the T 2 Term: By Cauchy-Schwarz inequality, we obtain</p><p>.</p><p>By Corollary 2 with n = 2, Lemma 12 and the equivalence of all norms on R |S||A| , we obtain</p><p>Combining the above analysis together, there exist an &#945; 0 such that 0 &lt; 1 -2(1 -&#8730; &#947; 0 )&#945; 0 + O(&#945; 2 0 ) &lt; 1 and for any &#945; &#8804; &#945; 0 , there exist t &#945; such that for any t &#8805; t &#945; , we obtain</p><p>).</p><p>Then,</p><p>, where c is a universal constant that is independent with &#945;, &#945; &#8242; . Then, for &#8704;&#1013; &gt; 0, given &#945; &gt; 0, we can choose a sufficient small &#948; &#1013; such that</p><p>Then, when &#945; &#8242; is selected with |&#945; -&#945; &#8242; | &#8804; &#948; &#1013; , we obtain</p><p>Therefore, we complete the proof of continuity of L(x &#945; ) w.r.t W 2 . Then, by the same argument at the end of Section C.2, we obtain lim &#945;&#8594;0 W 2 L(Y (&#945;) ), L(Y ) = 0, thereby completing the second step of the proof of Theorem 5.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>G.3 Step 2.5: Convergence Rate under Gaussian Noise</head><p>By triangle inequality, we obtain</p><p>which gives the convergence rate.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>G.4 Step 3: General Noise</head><p>By Section G.1, G.2 and G.3, we prove that under the noise with normal distribution, there exists a unique random variable Y such that Y (&#945;) converge to Y with respect to W 2 . In this subsection, we aim to prove that under general i.i.d zero mean noise with the same variance, the convergence result still holds and the limit is still Y .</p><p>By equation (61), we consider the following coupling:</p><p>where</p><p>{(A t , B t , H t )} t&#8805;0 and {(A &#8242; t , B &#8242; t , H &#8242; t )} t&#8805;0 have zero mean and the same variance. Here (A t , B t , H t ) and (A &#8242; t , B &#8242; , H &#8242; t ) are not necessary independent with each other, {(A &#8242; t , B &#8242; t , H &#8242; t )} t&#8805;0 are normal distributed and we assume that {(A t , B t , H t )} t&#8805;0 have finite fourth moments.</p><p>Let &#954; = &#8970;&#945; -1 2 &#8971;. We obtain</p><p>and</p><p>Taking the difference of the last two equations, we get</p><p>A &#954;t+&#954;-j f (q * ) -A &#8242; &#954;t+&#954;-j f (q * ) + H &#954;t+&#954;-j -H &#8242; &#954;t+&#954;-j -&#8730; &#945; &#954; j=1</p><p>(1 -(1 -&#945;) j-1 ) (A &#954;t+&#954;-j f (q * ) + H &#954;t+&#954;-j ) + &#8730; &#945; &#954; j=1</p><p>(1 -(1 -&#945;) j-1 ) A &#8242; &#954;t+&#954;-j f (q * ) + H &#8242; &#954;t+&#954;-j</p><p>Applying the generalized Moreau envelope M &#951; (&#8226;) defined in equation ( <ref type="formula">21</ref>) to both sides of above equation and by property (1) in Proposition 5, we obtain</p><p>The following lemmas, proved in Sections G.4.1 and G.4.2 to follow, control the T 1 and T 2 terms Lemma 15. Under the setting of Theorem 5, we have</p><p>Lemma 16. Under the setting of Theorem 5 and some proper couplings between {(A t , B t , H t )} t&#8805;0 and {(A &#8242; t , B &#8242; t , H &#8242; t )} t&#8805;0 , we have</p><p>Plugging the above bounds for T 1 and T 2 into equation ( <ref type="formula">68</ref>), there exist an &#945; 0 such that for any &#945; &#8804; &#945; 0 , there exist t &#945; such that for any t &#8805; t &#945; , we obtain</p><p>Therefore, we obtain lim where</p><p>((1 -&#945;) j-1 -1)(T (Y &#954;t+&#954;-j + q * &#8730; &#945; ) -T (Y &#8242; &#954;t+&#954;-j +</p><p>Below, we bound T 11 &#8764; T 13 separately. By Corollary 2(2), Lemma 12 and the equivalence of all norms on R |S||A| , we obtain</p><p>where the last inequality holds because we can always choose a proper &#951; such that ucm lcm &#8804; 1 &#8730; &#947;0 . Similarly to the bound for T 12 in Section G.1, we obtain</p><p>where (i) holds by equation (42).</p><p>Combining the bound for T 11 &#8764; T 13 together, we obtain</p><p>thereby completing the proof of Lemma 15.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>G.4.2 Proof of Lemma 16 on T 2</head><p>By Cauchy-Schwarz inequality, we obtain</p><p>A &#954;t+&#954;-j f (q * ) -A &#8242; &#954;t+&#954;-j f (q * ) + H &#954;t+&#954;-j -H &#8242; &#954;t+&#954;-j &#8741; 2 2 (T 26 ) + &#945;E&#8741; &#954; j=1</p><p>(1 -(1 -&#945;) j-1 )(A &#954;t+&#954;-j f (q * ) + H &#954;t+&#954;-j )&#8741; 2 2 (T 27 ) + &#945;E&#8741; &#954; j=1</p><p>(1 -(1 -&#945;) j-1 )(A &#8242; &#954;t+&#954;-j f (q * ) + H &#8242; &#954;t+&#954;-j )&#8741; 2 2 . (T 28 ) By Corollary 2(2), Lemma 12 and equivalence of norms in R |S||A| , we obtain the following bounds:</p><p>(1 -(1 -&#945;) j-1 ) 2 ) &#8712; O(&#945; 3 &#954; 3 ), T 24 &#8804; O(&#945; 2 &#954; &#954; j=1</p><p>(1 -&#945;) 2j-2 ) &#8712; O(&#945; 2 &#954; 2 )</p><p>(1 -&#945;) 2j-2 ) &#8712; O(&#945; 2 &#954; 2 ), T 27 &#8804; O(&#945; &#954; j=1</p><p>(1 -(1 -&#945;) j-1 ) 2 ) &#8712; O(&#945; 2 &#954; 2 )</p><p>(1 -(1 -&#945;) j-1 ) 2 ) &#8712; O(&#945; 2 &#954; 2 ).</p><p>For T 26 , we can notice that (A &#8242; &#954;t+&#954;-j f (q * ), H &#8242; &#954;t+&#954;-j ) is normal distributed. Then, similarly to the analysis of T 24 in Section C.4, we can find a coupling between {A t , B t , H t } t&#8805;0 and {A &#8242; t , B &#8242; t , H &#8242; t } t&#8805;0 such that T 26 &#8712; O(&#945;).</p><p>Recall that &#954; = &#8970;&#945; -1 2 &#8971;, we obtain</p><p>, thereby completing the proof of Lemma 16.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>H Proof of Theorem 6</head><p>By Theorem 4 and equation (62), we have the following equalities in distribution:</p><p>= (1 -&#945;)Y (&#945;) + &#945;T 0 (Y (&#945;) ) + &#945;&#947;DP h(Y (&#945;) , q * &#8730; &#945; ) + &#945;A 0 h(Y (&#945;) , q * &#8730; &#945; )</p><p>+ &#945;A 0 g(Y (&#945;) ) + &#945;B 0 Y (&#945;) + &#8730; &#945;E 0 ,</p><p>where T 0 (q) = &#947;DP g(q) + (I -D)q.</p><p>Taking expectation to both sides of the above equation, we obtain</p><p>Rearranging terms, we obtain the equality</p><p>By Fatou's lemma [Dur19, Exercise 3.2.4] and Lemma 12, we obtain</p><p>It is well known that weak convergence in P 2 (R |S||A| ) is equivalent to convergence in distribution and the convergence of the first two moments. By [Dur19, Exercise 3.2.5] and the Lipschitz continuity of T 0 (&#8226;), we obtain lim Because (Y (s &#8242; , a 1 ) -Y (s &#8242; , a 2 )) 2 &#8804; 2Y (s &#8242; , a 1 ) 2 + 2Y (s &#8242; , a 2 ) 2 , by dominated convergence theorem, we have E[(Y (s &#8242; , a 1 ) -Y (s &#8242; , a 2 )) 2 ] = 0.</p><p>By equation (69), Corollary 2(2), Lemma 12 and equivalence of norms in R |S||A| , we obtain</p><p>Rearranging terms, we obtain the equality (2 -&#945;)E[(Y (&#945;) (s &#8242; , a 1 ) -Y (&#945;) (s &#8242; , a 2 )) 2 ] = o(1) + E[(E 0 (s &#8242; , a 1 ) -E 0 (s &#8242; , a 2 )) 2 ].</p><p>Letting &#945; go to 0, we obtain 2E[(Y (s &#8242; , a 1 ) -Y (s &#8242; , a 2 )) 2 ] = E[(E 0 (s &#8242; , a 1 ) -E 0 (s &#8242; , a 2 )) 2 ].</p><p>Recall that E 0 = A 0 f (q * ) + B 0 q * + C 0 = &#947;D 0 P 0 f (q * ) + D 0 r 0 -D 0 q * Therefore, have Var(E 0 ) is positive definite, which implies E[(Y (s &#8242; , a 1 )-Y (s &#8242; , a 2 )) 2 ] &gt; 0 and contradicts with the fact E[(Y (s &#8242; , a 1 )-Y (s &#8242; , a 2 )) 2 ] = 0. Then, we can conclude that E[Y ] &#824; = 0.</p><p>Case 2: If there is no tied state, by definition, g(&#8226;) will be a linear function. Recall that</p><p>For n &#8805; 2, by equation (63) in Lemma 12, Assumption 4(n) and the above equation, we obtain</p><p>2n-1 2n</p><p>By the above bounds and applying Jensen's inequality twice, we obtain that</p><p>We thus have</p><p>For the second moment, by [HCX23b, Equation A.28], we obtain</p><p>(71) Meanwhile, we have</p><p>(1 -&#945;C 1 ) t and E &#952; (&#945;) -&#952; * 2 2 &#8712; O(&#945;&#964; &#945; ).</p><p>Substituting the above bounds into the right-hand side of inequality (71) yields</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>I.1 First Moment</head><p>First, we have</p><p>To bound the sum on the right hand side, we use Lemma 17 to obtain</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>It follows that</head><p>where (i) follows from the inequality that (1 -u) m &#8804; exp(-um) for 0 &lt; u &lt; 1. Together with Condition 2 we have</p><p>thereby finishing the proof of Proposition 3 for the first moment.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>I.2 Second Moment</head><p>In this subsection, we follow the proof technique in [HCX23b, Section A.6.2] to bound the second moment of the tail-averaged iterate. Here we use the same decomposition:</p><p>For T 2 , we have</p><p>The term T 3 is similar to T 2 and obeys the same bound.</p><p>For T 4 , we have</p><p>For T 1 , we have</p><p>By Lemma 17, we have</p><p>Therefore, for the term in (72), we have</p><p>(1 -&#945;C 1 )</p><p>We then restate the following claim, whose proof is almost the same as the proof of Claim 4 in <ref type="bibr">[HCX23b]</ref>.</p><p>Claim 1. For t &#8805; 2 &#945;C1 log 1 &#945;&#964;&#945; and l &#8805; t + &#964; &#945; , we have</p><p>.</p><p>Then, by [HCX23b, Claim 4], we have term (73) &#8712; O &#964;&#945; k-k0 . Similarly, we have term (74)&#8712; O &#964;&#945; k-k0 . Therefore, we have</p><p>By adding T 1 &#8764; T 4 together, we obtain</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>J Proof of Proposition 4</head><p>We prove the first and second moment bounds in Proposition 4.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>J.1 First Moment</head><p>By equation (16), we obtain</p></div><note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="1" xml:id="foot_0"><p>In particular, for deriving the limit of the T</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="2" xml:id="foot_1"><p>term in [CMM22, Page 15].</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="2" xml:id="foot_2"><p>A function g : R m &#8594; R d is homogeneous of degree 1 if g(cx) = cg(x) for all c &#8805; 0 and x &#8712; R m</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="3" xml:id="foot_3"><p>The code can be found in https://colab.research.google.com/drive/1b2RVEhC5gMmtxgL7SOdekp-25UM2q2hV?usp= sharing.</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="1" xml:id="foot_4"><p>4 E[M &#951; (Y t -Y &#8242; t )],</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="2" xml:id="foot_5"><p>), thereby completing the proof of Lemma 13.</p></note>
		</body>
		</text>
</TEI>
