The paper concerns convergence and asymptotic statistics for stochastic approximation driven by Markovian noise.    This is the  $d$-dimensional recursion,

\[
\theta_{n+1}= \theta_n + \alpha_{n + 1} f(\theta_n, \Phi_{n+1})
\,,\quad n\ge 0,
\]

in which each $\theta_n\in\Re^d$,
$\bfPhi \eqdef \{ \Phi_n \}$ is a Markov chain on a general state space $\state$
with stationary distribution $\pi$,
and $f:\Re^d\times\state\to\Re^d$.
In addition to standard Lipschitz bounds on $f$, and conditions on the vanishing step-size sequence $\{\alpha_n\}$, it is assumed that the associated ODE,
$ \ddt \odestate_t = \barf(\odestate_t)$, is globally asymptotically stable
with stationary point denoted $\theta^\ocp$,
where $\barf(\theta)=\Expect[f(\theta,\Phi)]$ with $\Phi\sim\pi$.
Moreover, the  ODE@$\infty$
defined with respect to the vector field,

\[
\barfinf(\theta)\eqdef \lim_{r\to\infty} r^{-1}   \barf(r\theta)  \,,\qquad \theta\in\Re^d,
\]

is asymptotically stable.
The main contributions are summarized as follows:

* The sequence  $\{ \theta_n\}$  is convergent if $\bfPhi$ is geometrically ergodic, and subject to compatible bounds on $f$.

The remaining results are established under a stronger assumption on the
Markov chain. Under a slightly weaker version
of the Donsker-Varadhan
Lyapunov drift condition
known as (DV3):

* A Lyapunov function is constructed for the joint process $\{\theta_n,\Phi_n\}$ that implies convergence of  $\{ \theta_n\}$ in

* A functional CLT is established,  as well as the usual
one-dimensional CLT for the normalized
error $z_n\eqdef (\theta_n-\theta^*)/\sqrt{\alpha_n}$.
Moment bounds combined with the CLT imply convergence of the normalized

\[
\lim_{n \to \infty} \Expect [ z_n z_n^\transpose  ] = \Sigma_{\theta},
\]

where  $\Sigma_\theta$ is the asymptotic covariance appearing in the CLT.

* An example is provided where the Markov chain $\bfPhi$
is geometrically ergodic but it does not satisfy (DV3).

While the algorithm is convergent,  the second moment is unbounded:
$ \Expect [ \| \theta_n \|^2  ] \to \infty$ as $n\to\infty$.

§ INTRODUCTION

The stochastic approximation (SA) method of Robbins and Monro <cit.> was designed to solve  the $d$-dimensional    root-finding problem $\barf(\theta^\ocp) = \Zero$,  where $\barf\colon\Re^d\to\Re^d$ is defined as an expectation
$\barf(\theta)\eqdef \Expect[f(\theta, \Phi)]$, $\theta\in\Re^d$,  with $\Phi$ a vector-valued random variable.  Interest in SA has grown over the past decade with increasing interest in reinforcement learning and other “stochastic algorithms”  <cit.>.

Motivation for the basic SA algorithm and approaches to analysis are now well developed.
A starting point is to recognize that $\theta^\ocp $ is a stationary point of the ordinary differential equation (ODE):

\begin{equation}
\ddt \odestate_t = \barf(\odestate_t).
\label{e:ODESA1}
\end{equation}

A standard assumption is that this ODE is globally asymptotically stable, so that in particular solutions converge to $\theta^\ocp$ from each initial condition $\odestate_0\in\Re^d$.    In applications, the first step in the “ODE method” is to construct the function $f$ that determines $\barf$ so that stability and other desirable properties are satisfied.

Subject to standard Lipschitz conditions, the
ODE (<ref>) can be approximated using an Euler scheme:
With step-size sequence denoted $\{\alpha_n\}$, this is given by:

\begin{equation}
\bartheta_{n+1} = \bartheta_n +\alpha_{n+1}  \barf(\bartheta_n)     \,,\quad n\ge 0.
\label{e:succA}
\end{equation}

The next step is to recognize that the Euler method is robust to “measurement noise”,  which motivates the SA recursion,

\begin{equation}
\theta_{n+1}= \theta_n + \alpha_{n + 1} f(\theta_n, \Phi_{n+1}),
\label{e:SAa}
\end{equation}

where the distribution of $\Phi_{n}$ converges to that of $\Phi$ as $n\to\infty$.
Writing $ \Delta_{n+1} \eqdef f(\theta_n, \Phi_{n+1}) - \barf(\theta_n) $,  the interpretation as a noisy Euler approximation is made explicit:

\begin{equation}
\theta_{n+1} = \theta_n +\alpha_{n+1} [ \barf(\theta_n) + \Delta_{n+1} ]\,,\quad n\ge 0.
\label{e:SAintro}
\end{equation}

Comparison of (<ref>) with
(<ref>)   begins with the definition of sampling times for the ODE:
Take, $\SAtime_0=0$ and define:

\begin{equation}
\SAtime_{k+1}  = \SAtime_k + \alpha_{k+1},\qquad k\ge 0.
\label{eq:tau}
\end{equation}

The ODE approximation for SA is then based on a comparison of two processes in continuous time:

(i) Interpolated parameter process:

\begin{equation}
\text{$ \ODEstate_t  = \theta_k$   when $t=\SAtime_k$, for each $k\ge 0$,    }
\label{e:ODEstate}
\end{equation}

and defined for all $t$ through piecewise linear interpolation.
(ii)  Re-started ODE:   For each $n\ge 0$,   let
$\{ \odestate^{(n)}_t :  t\ge \SAtime_n \}$ denote the solution to  (<ref>),  initialized according to the current parameter estimate:

\begin{equation}
\ddt \odestate^{(n)}_t  =\barf(\odestate^{(n)}_t )\,,  \quad  t\ge \SAtime_n\,,\qquad   \odestate^{(n)}_{\SAtime_n}  =\theta_n.
\label{e:ODEn}
\end{equation}

Iteration of (<ref>) gives,   for any $0<n<K$,

\begin{equation}
\begin{aligned}
\ODEstate_{\SAtime_K}  &  =   \theta_n   +   \sum_{i=n}^{K-1}   \alpha_{i+1}  \barf( \theta_i)  +   \sum_{i=n}^{K-1} \alpha_{i+1} \Delta_{i+1}
\\
& =     \ODEstate_{\SAtime_n}    +    \int_{\SAtime_n}^{\SAtime_K} \barf(\ODEstate_\tau )\, d\tau + \clE_{K}^{(n)} ,
\end{aligned}
\label{e:InterationOfSAintro}
\end{equation}

where $\clE_{K}^{(n)}  $ is the sum of cumulative disturbances and the error resulting from the Riemann-Stieltjes  approximation of the integral.
The disturbance term $\clE_{K}^{(n)}  $ will vanish with $n$ uniformly in $K$ subject to conditions on $\{\Delta_i\}$ and the step-size.  This is by definition the ODE approximation of $\{\theta_n\}$  <cit.>.

A closer inspection of the theory shows that two ingredients are required to
establish convergence of SA:  The first is stability of the ODE (<ref>), as previously noted.   The second requirement is that the sequence $\{ \theta_n\}$ obtained from the SA recursion is bounded with probability one.    Subject to moment bounds on the sequence it is also possible to establish rates of convergence through the central limit theorem (CLT) and the law of the iterated logarithm

The goal of the present paper is to expand the Borkar-Meyn theorem  of <cit.> to provide more readily verifiable conditions for both convergence and asymptotic statistics.   The stability criterion in this prior work is based on the “ODE@$\infty$” with vector field:

\begin{equation}
\barfinf(\theta)\eqdef
\lim_{r\to\infty} r^{-1}   \barf(r\theta).
\label{e:barfinfty}
\end{equation}

If the ODE with this vector field is globally asymptotically stable, then the sequence $\{ \theta_n\}$  is bounded with probability one.  Relaxations of the assumptions of   <cit.> are given in   <cit.>.   A common assumption in all of this prior work is that the sequence $\{\Delta_n\}$ appearing in (<ref>) is a martingale difference sequence.   This strong assumption holds in the tabular Q-learning algorithm of Watkins and a few other very special cases.

Reference <cit.> presents an extension of  <cit.> in which the
sequence $\bfPhi=\{\Phi_n\}$ appearing in (<ref>) is parameter dependent, which can be
realized by  $\Phi_{n+1} = \upxi_{n+1}(\Phi_n, \theta_n )$ in which
$\{\upxi_n : n\ge 1\}$ is an independent and identically distributed (i.i.d.) sequence
of functions.
Boundedness of the parameter sequence is obtained based on a more complex ODE@$\infty$, defined as a differential inclusion.
The setting is adversarial: The ODE@$\infty$ is stable under the worst-case noise sequence.  Once boundedness is established,  convergence of parameter estimates follows from arguments in <cit.>.

The present paper provides alternative assumptions on the “noise” that are valid in a broad range of applications, and lead to far stronger conclusions than anticipated in prior research.    Specially, it is assumed that the Markov chain appearing in (<ref>) satisfies (DV3):
a slightly weaker version of the well-known Donsker-Varadhan
Lyapunov drift condition <cit.>,  which is
used in <cit.>
to establish exact large deviations asymptotics for the partial sums of functions of a Markov chain.    Details and connections with other drift conditions are discussed in the next section.

The main results we obtain are the following.

* <Ref>:
Subject to Lipschitz bounds on $f$ and $\barf$ we construct a
Lyapunov function for the joint process $\{\theta_n,\Phi_n\}$.     It satisfies a drift condition that implies boundedness of $\{ \theta_n\}$  almost surely and in $L_4$.

* <Ref>:
Convergence of $\{\theta_n\}$ to $\theta^*$ is established, and it shown that
the fourth moment bound implies the CLT (and a functional CLT) for $\{\theta_n\}$,
provided the linearization of $\barf$ at $\theta^\ocp$ satisfies assumptions that are well known in the case of martingale-difference noise.   We also obtain convergence of the normalized covariance,

\[
\lim_{n \to \infty} \frac{1}{\alpha_n}
\Expect [ \tiltheta_n\tiltheta_n^\transpose  ] = \Sigma_{\theta},
\]

where  $\tiltheta_n:=\theta_n-\theta^*$
and $\Sigma_\theta$ is the asymptotic covariance appearing in the CLT.

The preceding conclusions hold under the combination of condition (DV3) and
the assumption that
the ODEs with vector fields $\barf$ and $\barfinf$ are stable.
Stability of the ODE@$\infty$ is equivalent to the existence of a Lipschitz continuous
function $V\colon\Re^d\to\Re_+$ satisfying a weak Lyapunov drift condition
for the ODE (<ref>) <cit.>.

Condition (DV3) is natural for this setting, and it is not overly restrictive.
It holds for linear state space models with disturbance whose marginal has Gaussian tails,  and the continuous-time version holds for the Langevin diffusion under mild conditions  <cit.>.
However, (DV3) often fails for skip-free Markov chains if the state space is not finite.
For example, the M/M/1 queue in discrete time is geometrically ergodic under the standard load
assumption, but it does not satisfy (DV3). This motivates a third contribution:

* <Ref>:   (DV3) cannot be relaxed without imposing stronger assumptions elsewhere.
The M/M/1 queue is used to define $\bfPhi$ in a scalar SA example for which $\barf(\theta)=-\theta$.
The assumptions of <Ref> hold, so that $\lim_{n\to\infty} \theta_n = \theta^\ocp =0$ with probability one.

This example is geometrically ergodic and satisfies all the assumptions of <Ref>,
except that $\bfPhi$ does not satisfy (DV3). Nevertheless,
borrowing ideas from <cit.>, it is shown in <Ref> that the CLT variance
$ \Expect [ \| \tiltheta_n \|^2  ] \to \infty$ as $n\to\infty$ whenever a “load parameter” is larger than $1/2$, where $\|\cdot\|$ denotes the Euclidean 2-norm.

This paper is intended to be, in part,
pedagogical – we hope to make the theory more accessible by conveying the
main ideas in the body of the paper, and leaving tedious calculations
to the Appendix.

See <Ref> for a glossary of notation with references to where they are introduced.

Prior work

The roots of the ODE@$\infty$ can be traced back to the fluid model techniques
for stability of networks <cit.>, which were extended to
skip-free  Markov chains in <cit.>; see <cit.> for further
history since <cit.>.
The reader is also referred to <cit.> and <cit.>
for the substantial literature on asymptotic statistics for SA.

Much of the recent literature on convergence rates for SA
is motivated by applications to
reinforcement learning (RL), and seeks finite-$n$ error bounds rather than asymptotic
results of the form considered here.
The article <cit.> treats temporal difference (TD) learning
(a particular RL algorithm) with Markovian noise, which justifies the linear
SA recursion of the form $f(\theta,\Phi) = A(\Phi)\theta + b(\Phi)$.
The primary focus is on the fixed step-size setting, with parallel results
for vanishing step-size sequences.
The uniform bounds assumed in <cit.> will hold under uniform
ergodicity and boundedness
of $A$ and $b$ as functions of $\Phi$.
Improved bounds are obtained in <cit.>, but subject to i.i.d. noise;
this paper also contains a broad survey of results in this domain.
Bounds are obtained in  <cit.> for linear SA recursions
under slightly
weaker conditions.   While not precisely finite-$n$ bounds as
in <cit.>, they are asymptotically tight since they
are presented as refinements of the CLT.

More closely related to the present paper is the research program of Moulines and co-authors.
Finite-$n$ bounds are obtained in <cit.>
for stochastic gradient descent,
under the assumption of martingale difference noise.
The results in <cit.> are obtained
under condition (DV3),
along with assumptions on the functions $A$ and $b$ that
are related to the bounds imposed here.
But the spirit of the results is quite
different, since the main focus is the linear SA recursion
and most  of the effort is devoted to fixed step-size.

§ NOTATION AND BACKGROUND

This section contains some of the main assumptions that will
remain in effect for most of our result, and an outline
of important background material. A glossary of some of
the most frequently used notation is given at the end of the

§.§ Markov chains

Let $\bfPhi=\{\Phi_n\}$ be a Markov chain with general state space $\state$
and transition kernel $P$. It is assumed that $\bfPhi$ is geometrically
ergodic (see below for the precise definition) with unique invariant
measure $\pi$. Given $f:\Re^d \times \state \to \Re^d$ in (<ref>), we denote $\barf(\theta) \eqdef \Expect_{\pi}[f(\theta, \Phi_k)]$,   where the subscript indicates that the expectation is taken in steady-state:  $\Phi_k\sim \pi$ for each $k$.
We also use the compact notation $\pi(g) \eqdef\int g(x)\, \pi(dx)$ whenever the integral is well defined.

We assume that $\state $ is equipped with a sigma-algebra $\bx$; typically $\bx$
is the Borel sigma-algebra when $\state$ is a topological space.
A pair $(C,\nu)$ are called small if $C\in\bx$ and $\nu$ is a
probability measure on $(\state,\bx)$, such that,
for some $\epsy>0$ and $n_0\ge 1$,

\[
P^{n_0}(x,A)  \ge \epsy \nu(A) \,, \qquad  \textit{for $A\in\bx$ and   $x\in C$};
\]

If the particular $\nu$ is not of interest, then we simply say that the set $C$ is small.
It is sometimes convenient to   replace the set $C$ by a function $s\colon\state\to\Re_+$.  In this case, we say that $s$ is small if,

\[
P^{n_0}(x,A)  \ge  \epsy s(x)  \nu(A) \,, \qquad  \textit{for $A\in\bx$ and all $x\in\state$}.
\]

The Markov chain is called aperiodic if there exists a probability measure $\nu$ and $\epsy>0$ such that the following hold:  For each $x\in\state$ there is $n(x)\ge 1$ such that:

\[
P^{n}(x,A)  \ge \epsy \nu(A) \,, \qquad   \textit{for all $n\ge n(x)$  and $A\in\bx$}.
\]

For any measurable function $g:\state\to [1,\infty)$, the Banach space $L_\infty^g$ is defined to be the set of measurable functions $\phi\colon\state\to\Re$ satisfying:

\[
\| \phi\|_g  \eqdef\sup_x \frac{1}{g(x)}  |\phi(x)| < \infty
\]

For a pair of functions $g,h:\state\to [1,\infty)$,  and  any
linear operator $\haP\colon L_\infty^{g}  \to  L_\infty^{h}$,
the induced operator norm is denoted:

\begin{equation}
\lll \haP \lll_{g, h}
\eqdef   \sup \Bigl\{ \frac{\|\haP \phi\|_{h}}{\|\phi\|_{g}}
:  \phi\in L^{g}_\infty,\ \|\phi\|_{g}\neq 0\Bigr\}.
\label{e:Vnorm}
\end{equation}

We write $	\lll \haP \lll_{g}$ instead of $	\lll \haP \lll_{g, h}$ when $g=h$.

Suppose that $\pi(g)  <\infty $.   Then the rank-one operator $\mathbbm{1} \otimes \pi$ has finite induced operator norm,
$\lll \mathbbm{1} \otimes \pi \lll_{g, h} <\infty$, for any choice of $h$,  where,

\[
[ \mathbbm{1} \otimes \pi] \phi \, (x)    = \pi(\phi)  \,, \qquad \textit{for   $x\in\state$ and $\phi\in  L_\infty^{g} $}.
\]

Consider the centered semigroup $\{\tilP^n = P^n -\mathbbm{1} \otimes \pi  : n\ge 0\}$, with  $\tilP = P -\mathbbm{1} \otimes \pi$.
The chain $\bfPhi$ is called $g$-uniformly ergodic if $\pi(g)$ is finite,
and  $\lll \tilP^n \lll_g\to 0$ as $n\to\infty$.  Necessarily the rate of convergence is geometric, and it is known that seemingly weaker definitions of geometric ergodicity are equivalent to the existence of $g$ for which
$g$-uniform ergodicity holds <cit.>.
We say $\bfPhi$ is geometrically ergodic if it is $g$-uniformly
ergodic for some $g$.

We say that the Lyapunov drift criterion (V4)
holds with respect
to the Lyapunov function $v:\state\to[1,\infty]$, if:

\left.
\mbox{\parbox{.85\hsize}{\raggedright
For a small function $s$,   and constants $\Vdrift >0$, $b <\infty$,
\[
\Expect[v(\Phi_{k+1}) - v(\Phi_k) \mid \Phi_k =x] \leq -\Vdrift v(x) + bs(x)\,, \qquad x\in\state .
\]
\right\}
\eqno{\hbox{\bf (V4)}}

If this condition holds and the chain is aperiodic, then the Markov chain is $v$-uniformly ergodic <cit.>.

We establish almost sure (a.s.) boundedness and convergence of $\{\theta_n\}$ in (<ref>) under (V4) and suitable conditions on the step-size sequence and $\barf$.
A stronger drift condition is imposed to establish moment bounds:

\left.
\mbox{\parbox{.85\hsize}{\raggedright
For functions $V\colon\state\to\Re_+$,  $ W\colon\state\to [1, \infty)$,
a small function $s\colon\state\to [0,1]$, and $b>0$:\,
\[
\Expect\bigl[  \exp\bigr(  V(\Phi_{k+1})      \bigr) \mid \Phi_k=x \bigr]
\le  \exp\bigr(  V(x)  - W(x) +  b s(x)  \bigl) \,, \qquad x\in\state.\]
\right\}
\eqno{\hbox{\bf (DV3)}}

The bound (DV3) implies (V4) with $v=e^V$
(see <cit.>  or <cit.>).

Suppose that the Markov chain $\bfPhi$ is aperiodic.  Then:

* Under (V4), there exists $\varrho \in (0, 1)$ and $b_v<\infty$ such that for each $g \in \Lv$, $x\in \state$:

\begin{equation}
\bigl| \Expect[g(\Phi_n) \mid \Phi_0= x] - \pi(g) \bigr| \leq b_v \|g\|_v v(x) \varrho^n  \,, \qquad n \geq 0.
\label{e:v-uni-w}
\end{equation}

* If (DV3) holds   then the conclusion in (i) holds with $v=e^V$.    Consequently,  for each $g\in L_\infty^{V+1}$ and $\kappa>0$, we can find $b_{\kappa, g}<\infty$ such that for all $n\geq 0$ and $x\in\state$:

\begin{equation}
\begin{aligned}
\Expect[ |g(\Phi_n)|^\kappa \mid \Phi_0= x]   \leq b_{\kappa,g} v(x)  .
\end{aligned}
\label{e:v-uni-w-alpha}
\end{equation}

The geometric convergence (<ref>) follows from <cit.>.
The proof of (<ref>) follows from $v$-uniform ergodicity and the fact that $\| |g|^\kappa\|_v<\infty$ under the given assumptions

§.§ Disturbance Decomposition

We assume $f:{\mathbb R}^d\times\state\to{\mathbb R}^d$ in (<ref>) is Lipschitz continuous in $\theta$ for each $x\in\state$: There exists a measurable function $L :\state \to \posRe$ such that for each $x\in\state$,

\begin{equation}
\label{e:lip-f}
\begin{aligned}
\| f(0, x)\| &\leq L(x), \\
\|f(\theta,x) - f(\theta', x)\| &\leq L(x)\|\theta - \theta'\| \,, \qquad \theta, \theta'\in \Re^d,
\end{aligned}
\end{equation}

where $\|\cdot\|$ denotes the Euclidean norm on ${\mathbb R}^d$.
Under these assumptions,  $\barf$ is also Lipschitz continuous with Lipschitz constant $\barL =  \pi(L)$.

A crucial representation for $\{ \Delta_{n+1} \eqdef f(\theta_n,\Phi_{n+1}) - \barf(\theta_n) \}$ in (<ref>)  begins with a representation for $\tilf(\theta,x) := f(\theta,x) - \barf(\theta)$.
Let $\haf:\Re^d\times \state \to \Re^d$ solve Poisson's equation:

\begin{equation}
\label{e:fish-f}
\Expect[\haf(\theta, \Phi_{n+1}) - \haf(\theta, \Phi_{n})\mid \Phi_n = x] = - \tilf(\theta, x)  \,, \qquad  \theta \in \Re^d\,, x \in \state .
\end{equation}

Existence of solutions is guaranteed under (V4) if the function $L$ defined in (<ref>) satisfies $L\in \Lv$ <cit.>.
More properties of $\haf$ under (V4) and (DV3) are established in <Ref>.

We obtain the following representation of
$\Delta_{n+1}$ via (<ref>):

We have,

\Delta_{n+1} = \MD_{n+2} - \clT_{n+2} + \clT_{n+1} + \clE^{\haf}_{n+2},

\begin{equation}
\label{e:noise-decomp}
\begin{aligned}
\MD_{n+2} &\eqdef \haf(\theta_n, \Phi_{n+2}) - \Expect[\haf(\theta_n, \Phi_{n+2})  \mid \clF_{n+1}],  \\
\clT_{n+1} &\eqdef  \haf(\theta_{n}, \Phi_{n+1}), \\
\clE^{\haf}_{n+2} &\eqdef \haf(\theta_{n+1}, \Phi_{n+2}) - \haf(\theta_n,  \Phi_{n+2}).
\end{aligned}
\end{equation}

Moreover, $\{\MD_{n}\}$ is a martingale difference sequence, so that
the sequence $\{M_{\tau_K}\}$ is a martingale,

\[
\Mart_{\SAtime_{K}} \eqdef \sum_{k=2}^K  \alpha_{k-1} \MD_k\,,    \qquad 2\le K <\infty;\quad \Mart_{\SAtime_1} =\Mart_{\SAtime_0} =0,
\]

where $\{\SAtime_k\}$ are defined in (<ref>).

The lemma implies a representation for the cumulative disturbance
For each $K>n$,

\begin{equation}
\label{e:sum-by-parts}
\begin{aligned}
\sum_{i = n}^{K-1} \alpha_{i+1} \Delta_{i+1}
& = \sum_{i=n}^{K-1} \alpha_{i+1} \bigl[ \MD_{i+2} + \clE^{\haf}_{i+2}  - \clT_{i+2}  + \clT_{i+1} \bigr] \\
& =  \Mart_{\SAtime_{K+1}} -\Mart_{\SAtime_{n+1}} +   \clE_{n,K},
\end{aligned}
\end{equation}

where, using summation by parts, we can express:

\[ \clE_{n,K} \eqdef
\sum_{i=n}^{K-1}\alpha_{i+1}\clE^{\haf}_{i+2}     + \alpha_{n+1}\clT_{n+1}	- \alpha_K\clT_{K+1}
-  \sum_{i=n}^{K-2}[\alpha_{i+1} - \alpha_{i+2}] \clT_{i+2}.
\]

§.§ ODE solidarity

This representation  	(<ref>)  allows for application of standard arguments to establish convergence of   (<ref>),  provided the sequence $\{\theta_n\}$ is bounded, and it also leads to a criterion for
boundedness itself.

An ODE approximation is defined by comparison of of the two continuous time processes: $\bfODEstate=\{\Theta_t\}$, defined in (<ref>),  and
the solution $\bfodestate^{(n)}=\{\odestate^{(n)}_t\}$
to the re-started ODE (<ref>).   The two processes are compared over
time blocks of length approximately $T$,  with $T>0$ fixed and chosen “sufficiently large”.  Let  $T_0=0$ and $T_{n+1} = \min \{\SAtime_k: \SAtime_k \geq T_n + T\}$.
The $n$-th time block is $[T_n, T_{n+1}]$ and $\displaystyle T\leq T_{n+1} - T_{n} \leq T+ \bar{\alpha} $ by construction, where   $\bar{\alpha} \eqdef \sup_k \alpha_k  $ is assumed bounded by unity in Assumption (A1) below. The following notation is required throughout:

\begin{equation}
\textit{$m_0\eqdef 0$,
and $m_n$ denotes the integer satisfying $\SAtime_{m_n} = T_n$ for each $n\geq1 $. }
\label{e:mofn}
\end{equation}

Boundedness of the parameters and other mild assumptions lead
to ODE approximation,

\begin{equation}
\lim_{n\to\infty} \sup_{T_n\le t\le T_{n+1} }  \|  \ODEstate_t   -  \odestate^{(n)}_t \| =0 \,,\qquad \mbox{a.s.},
\label{e:ode-method}
\end{equation}

and this combined with global asymptotic stability of
(<ref>) quickly leads to convergence of $\{\theta_n\}$.

The approximation (<ref>)
relies crucially on the  representation  	(<ref>).  This representation of the “noise” also leads to a criterion for boundedness of the parameter estimates, as explained in the next subsection.

§.§ ODE@$\infty$

The ODE@$\infty$ technique for establishing stability of SA is based on the
scaled vector field, denoted $\barf_{c}(\theta) \eqdef \barf({c}\theta)/{c},$ for any ${c} \geq 1$,   and requires the existence of a continuous limit:   $\barf_{\infty}(\theta)  \eqdef \lim_{c\to\infty} \barf_{c}(\theta) $ for any $\theta\in\Re^d$.

The  ODE@$\infty$ is then denoted:

\begin{equation}
\label{e:ode-infty}
\ddt \odestate_t = \barf_{\infty}(\odestate_t).
\end{equation}

We always have $\barf_{\infty}(\Zero) = \Zero$, and asymptotic stability of this equilibrium is equivalent to global asymptotic stability  <cit.>.

An ODE approximation is obtained for the scaled parameter estimates:
On  denoting $c_n \eqdef \max\{1, \| \theta_{m_n}\|\}$,
and  $ \hattheta_k  =  \theta_k /{c_n}$  for  each $n$ and $m_n \leq k < m_{n+1}$,  we compare two processes in continuous time:

\begin{align}
\hatODEstate_t  &=  \frac{1}{c_n}\ODEstate_t ,
\label{e:rescaled-traj}
\\
\ddt  \hatodestate_t &= \barf_{c_n}( \hatodestate_t)\,, \qquad \hatodestate_{T_n} = \hatODEstate_{T_n} = \tfrac{1}{ c_n}   \theta_{m_n }, \,   \ &&  t\in [T_n, T_{n+1}) .
\label{e:rescaled-ode}
\end{align}

The scaled iterates $\{\hattheta_k\}$ satisfy

\begin{equation}
\label{e:hat-theta-sa}
\begin{aligned}
\hattheta_{k+1}
&= \hattheta_k + \alpha_{k+1}f_{c_n}(\hattheta_k, \Phi_{k+1}) \\
&= \hattheta_k + \alpha_{k+1}\bigl[\barf_{c_n}(\hattheta_k) + \hatDelta_{k+1} \bigr], \qquad m_n \leq k < m_{n+1} \,,
\end{aligned}
\end{equation}

where $f_{c_n}(\theta_k, \Phi_{k+1}) \eqdef f(c_n\theta_k, \Phi_{k+1})/c_n$ and $\hatDelta_{k+1} \eqdef \Delta_{k+1}/c_n$.

The representation (<ref>) motivates an ODE analysis similar to what is performed to establish (<ref>).
The analysis is simplified since $\{\hattheta_k \}$ is a bounded sequence by
construction, and by assuming appropriate Lipschitz bounds on $f$ and $\barf$.
A tight approximation is established in <Ref>:

\begin{equation}
\lim_{n\to\infty} \sup_{T_n\le t\le T_{n+1} }  \|  \hatODEstate_t  - \hatodestate_t \| =0 \,,\qquad\mbox{a.s.}
\label{e:ode-method-infty}
\end{equation}

§ MAIN RESULTS

Most of our results will depend on assumptions (A1)-(A3) below.
Assumption (A1) is standard in the SA literature,  and (A3) is the starting point for analysis based on the ODE@$\infty$.  The special assumptions on $\bfPhi$ in (A2) are less common;  especially the introduction of (DV3).

(A1) The non-negative gain sequence $\{\alpha_n\}$ satisfies:

\begin{equation}
\textit{$0 \leq \alpha_n \leq 1$, for all $n$,}
\qquad
\sum_{n=1}^{\infty} \alpha_n = \infty,
\qquad \sum_{n=1}^{\infty} \alpha_n^2 < \infty.
\label{e:stepsize-cond}
\end{equation}

Moreover, with $\diffalpha_n \eqdef  \alpha_{n+1}^{-1} - \alpha_n^{-1}$,   $\diffalpha = \lim_{n \to \infty} \diffalpha_n$ exists and is finite.

(A2) The function $f(\theta,x)$ satisfies the bounds in (<ref>),  with $L\colon\state\to\posRe$.   The remaining parts of (A2) depend on the drift condition imposed:

$\circ$  Under (V4) it is assumed that  $L^8\in \Lv$.

$\circ$  Under (DV3) it is assumed that $\delta_L \eqdef \|L\|_W < \infty$ (so that
$L\in L_\infty^W$).   In addition,

\begin{align}
\!   \!   \!   \!   \!
S_W(r)  &:= \{ x :  W(x)\le r \}  \quad   && \textit{is either small or empty for each $r>0$. }
\label{e:Wunbdd}
\\
b_V(r) & \eqdef \sup\{ V(x) :  x\in S_W(r) \}  <\infty   \  && \textit{for each $r>0$. }
\label{e:V-bounded-level}
\end{align}

(A3) The scaled vector field $\barfinf(\theta)$ exists:
$\barf_c(\theta) \to \barfinf(\theta)$ as $c \to \infty$, for each $\theta\in \Re^d$.  Moreover, the ODE (<ref>) is globally asymptotically stable.

Equation (<ref>) is similar to what is used
in  <cit.>
to obtain a discrete spectrum for $\bfPhi$.

The function $\barfinf$ is  Lipschitz continuous when $f$
satisfies (<ref>), which is assumed throughout. Also,
all our results are valid when the Markov chain
$\bfPhi$ starts at an arbitrary initial
state $\Phi_0=x\in\state$.

§.§ Convergence and moment bounds

<Ref> is anticipated from established   theory <cit.>.
The main challenge in the proof  is establishing boundedness of the parameter sequence: This is based on the ODE approximation (<ref>) obtained in

If (V4) and (A1)-(A3) hold, then the parameter sequence  $\{\theta_k\}$ converges a.s. to the invariant set of $\ddt \odestate_t = \barf(\odestate_t)$.

Moment bounds require (DV3) and a relationship between the solution to
this drift inequality and stability of the ODE@$\infty$.

Given $c \geq 1$, let $\phi_c(t,\theta)$ denote the solution to,

\begin{equation}
\ddt \odestate_t = \barf_c(\odestate_t)\,, \qquad  \odestate_0=\theta\,,
\label{e:scaledODEsemigroup}
\end{equation}

and define $\phi_\infty(t, \theta)$ accordingly,
so that it solves
with initial condition $  \odestate_0=\theta$. Recall
$\delta_L \eqdef \| L \|_W$ was defined in (A2).
We say that $L = o(W)$ if the following limit holds:

\[
\lim_{r\to\infty}  \sup_{x\in\state}  \frac{ |L(x)|}{\max\{r,W(x)\}} =0.
\]

That is,  $\lim_{r\to\infty}  \| L \|_{W_r} =0$,
with $W_r (x):= \max\{r,W(x)\}$ for   $x\in\state$.

(A4) There exists $ \Trelax >0$   such that $\| \phi_\infty(t, \theta)\| \leq \half$ for   $t\geq \Trelax$ whenever $\|\theta\|=1$.  In addition, one of the following two conditions hold:
(a)   $ \Trelax < 1/(4\delta_L)$  or (b)   $L = o(W)$.

The subscript `r' in $\Trelax$ stands for “relaxation time” for the ODE@$\infty$.  The value of $\half$ is arbitrary;
any fixed number in $(0,1)$ will do.

The following hold under (A4):

* There exist positive constants $b$ and $\delta$ such that,
for any $\theta\in\Re^d$ and $t\ge 0$,

\[
\| \phi_\infty(t, \theta)\|  \le b  \| \theta \|  e^{-\delta t}.
\]

* There exists $c_0>0$ and $\half < \Crelax < 1$ such that,
for each initial condition satisfying $\|\theta\|=1$,

\[
\| \phi_c(t, \theta) \| \leq \Crelax < 1\,, \qquad \text{for all } t\in [\Trelax, \Trelax + 1]\,, \  c\geq c_0.
\]

Part (i) is  <cit.>  and (ii) is

Suppose that (DV3) and (A1)-(A3)  hold.    Assume in addition
that   (A4) holds in form (a) or (b).    Then:

\[
\sup_{k \geq 0}\Expect\bigl[( \| \theta_k \| + 1)^4   \exp\bigl( V(\Phi_{k +1 }) \bigr) \bigr] < \infty .
\]

The bound  $ \Trelax < 1/(4\delta_L)$ assumed in Assumption (A4a) appears difficult to validate.  It is included because it is what is essential in the proof 	of <Ref>.
Assumption (A4b) implies (A4a) provided we modify the function $W$ used in (DV3).   The proof of <Ref> follows from the definitions.

Suppose that (DV3) holds, subject to the bounds (<ref>).  Then:

* (DV3) holds and the bounds (<ref>) continue to hold for the pair $(V,W_r)$ for any $r\ge 1$.

* If in addition (A4b) holds, then
(A4a) also holds with $W$ replaced by $W_{r_0}$ for   $r_0\ge 1$ sufficiently large.

§.§ Asymptotic statistics

We now turn to rates of convergence, and for this it is assumed that the ODE (<ref>) is globally asymptotically stable with unique equilibrium denoted  $\theta^\ocp \in\Re^d$.
The accent `tilde'  is used to represent error: We write $\tilODEstate_{\SAtime_k}^{(n)}   \eqdef \ODEstate_{\SAtime_k}  - \odestate^{(n)}_{\SAtime_k}$ and   $\tiltheta_k \eqdef \theta_k - \theta^\ocp$.
Two normalized error sequences are considered:

\begin{align}
z_k & \eqdef \frac{1}{\sqrt{\alpha_k}}  \tiltheta_k
\label{e:zk}
\\
\scerror{\SAtime_k}{n}  & \eqdef\frac{1}{\sqrt{\alpha_k}}  \tilODEstate_{\SAtime_k}^{(n)}  \,,\qquad k\ge n\,,
\label{e:scerror}
\end{align}

The domain of the latter is extended to  all $\SAtime\ge   \SAtime_n  $  by piecewise linear interpolation.
It is convenient to move the origin of the time axis as follows:

\begin{equation}
\scerrorpull{\SAtime}{n} \eqdef \scerror{\SAtime_n +\SAtime}{n}     \,, \qquad \SAtime \ge  0.
\label{e:scerror_norm}
\end{equation}

The two fundamental approximations of interest here are:

Central Limit Theorem (CLT):  For any bounded continuous function $g\colon\Re^d\to\Re$,

\begin{equation}
\lim_{k\to\infty} \Expect[ g( z_k ) ]  =\Expect[g(\sclim)],
\label{e:CLT}
\end{equation}

where $\sclim$ is a Gaussian random vector,   $X\sim N(0,\Sigma_\theta)$.

Functional Central Limit Theorem (FCLT):  The sequence
of stochastic processes $\{\scerrorpull{\varble}{n} : n\ge 1 \}$ converges in distribution to the solution of the Ornstein-Uhlenbeck equation,

\begin{equation}
d\sclim_{t} = F \sclim_t \,dt+ D\,dB_{t} \,, \qquad \sclim_0 =\Zero\, ,
\label{e:FCLT}
\end{equation}

in which $\bfmB=\{B_t\}$ is standard $d$-dimensional Brownian motion,  and $F,D$ are $d\times d$ matrices.

The marginal distribution of the solution to  (<ref>)
is a zero-mean Gaussian random variable with covariance:

\[
\Sigma_{X_t}  = \int_0^t   e^{F s} D   [  e^{F s} D ]^\transpose \, ds
\]

This is convergent as $t\to\infty$ provided $F$ is Hurwitz.

The martingale difference sequence $\{ \MD_{n} \}$ in (<ref>) motivates the introduction of a family of martingale difference sequences, parametrized by $\theta$,

\begin{equation}
\MD_{n+1} (\theta) \eqdef \haf(\theta, \Phi_{n+1}) - \Expect[\haf(\theta, \Phi_{n+1})  \mid \clF_{n}],
\label{e:MD}
\end{equation}

and the  covariance matrices,

\begin{equation}
\label{e:def-Q}
%	Q(\theta_n, \Phi_{n+1})  \eqdef \Expect[\MD_{n+2}\MD_{n+2}^\transpose \mid \clF_{n+1}]\,,
%	\qquad
\begin{aligned}
\Sigma_{\MD}(\theta)  &\eqdef \Expect_\pi [ \MD_{n+1}(\theta)   \MD_{n+1}(\theta) ^\transpose]  \,,
\quad &  \Sigma_{\MD}^\ocp& =  \Sigma_{\MD}(\theta^\ocp)
%	\\
%	\SMSigma_{\MD \mid x} (\theta)  & \eqdef  \Expect[\MD_{n+1}(\theta)   \MD_{n+1}(\theta) ^\transpose \mid \Phi_n =x]  \quad
%	&   	\SMtilSigma_{\MD \mid x} (\theta)  & = 	\SMSigma_{\MD \mid x} (\theta)   -  \Sigma_{\MD}(\theta) .
\end{aligned}
\end{equation}

In <Ref> it is assumed that the ODE is globally exponentially asymptotically stable:  For some     $\bexp< \infty$, and $\rhoexp>0$,

\begin{equation}
\| \phi(t;\theta)  -\theta^\ocp \|   \le \bexp\| \theta -\theta^\ocp \| e^{ -\rhoexp t  } \,,  \qquad    \theta\in\Re^d\,, \   t\ge 0
\label{e:EAS}
\end{equation}

The motivation comes from consideration of bias,  which is assumed to approximate the solution to the ODE.  So,  for large $n$ and all $k\ge n$,

\[
\Expect[\theta_k -\theta^\ocp] \approx
\phi(\SAtime_{k-n};  \theta_n) - \theta^*.
\]

For the CLT to hold, the bias must decay faster than $1/\sqrt{\alpha_k}$.  Assumption (A5b) is introduced to ensure this, by imposing (<ref>) and further restrictions on the step-size.

The following assumptions are imposed along with (A1)-(A4):

(A5a) $\barf:\Re^d \to \Re^d$ is continuously differentiable in $\theta$, and the Jacobian matrix $A = \partial \barf$ is  uniformly bounded and uniformly Lipschitz continuous.

(A5b)    The step-size is $\alpha_n = 1/n^\rho$ with $\half <\rho\le 1$,   and   (<ref>) holds.
It is furthermore assumed that  $\rhoexp>1/2$ in the special case   $\rho=1$;  otherwise,     $\rhoexp>0$ is sufficient.

Suppose (DV3), (A1)-(A4) and (A5a) hold.
Assume moreover that  $ \tfrac{\diffalpha}{2}I + A^\ocp $ is Hurwitz, where $A^\ocp \eqdef
A(\theta^\ocp)$ with $A=A(\theta)$ given in (A5a)
and $\diffalpha$ as defined in (A1).
Then,  the FCLT  (<ref>) holds with $F = \tfrac{\diffalpha}{2}I + A^\ocp$,   $D$ any solution to $ \Sigma_{\MD}^\ocp = D D^\transpose$,  and $\Sigma_{\theta}>0$  is the unique solution to the Lyapunov equation:

\begin{equation}
[\tfrac{1}{2} \diffalpha I+A^\ocp] \Sigma_{\theta} + \Sigma_{\theta} [\tfrac{1}{2} \diffalpha I+A^\ocp]^\transpose +  \Sigma_{\MD}^\ocp = 0.
\label{e:Sigmatheta}
\end{equation}

For functions $g:\Re^d\to\Re$ and $\varpi:\Re^d\to\Re_+$, we
write $g =o( \varpi)$ if:

\[
\lim_{r\to\infty}  \sup_{\theta \in \Re^d}  \frac{ |g(\theta )|}
{\max\{r,\varpi (\theta)\}} =0  .
\]

Suppose the assumptions of <Ref> hold, and in addition (A5b) holds.
Then   the CLT (<ref>) holds,  with asymptotic covariance is given in (<ref>).
Moreover, the set of functions for which (<ref>) holds  includes any continuous function $g\colon\Re^d\to\Re$ satisfying $g=o(\varpi)$ with $\varpi(\theta) = \|\theta\|^4$ for $\theta\in\Re^d$.
In particular, the following limit holds:

\[
\lim_{n \to \infty} \frac{1}{\alpha_n} \Expect\bigl[ \tiltheta_n\tiltheta_n^\transpose \bigr] = \Sigma_{\theta}
\]

Motivation for (A5a) has already been explained in terms of bias.   In particular,
with step-size $\alpha_n=1/n$ we have $\SAtime_k\le \log(k+1)$, and hence under (<ref>),

\[
\| \phi(\SAtime_k; \theta) - \theta^\ocp \|    \le \bexp\| \theta -\theta^\ocp \| e^{ -\rhoexp  \SAtime_k }
\le \bexp\| \theta -\theta^\ocp  \|  \bigl( k+1 \bigr)^{-\rhoexp}.
\]

The bound $\rhoexp>1/2$ is imposed to ensure that the right hand side converges to zero faster than $1/\sqrt{k}$.
We do not know if this is essential to obtain the CLT.

Objective function and its negative gradient.

For illustration, consider an application to stochastic gradient descent,   with objective  $\Obj(\theta) = \half \theta^2 - 3[\cos(\theta) -1]$,   $\theta\in\Re$.  This function and the negative of its gradient    $-\nabla \Obj(\theta) =  -(\theta+3\sin(\theta))   $  are shown in  <Ref>,    where we see that the objective is quasi-convex and coercive,  and $-\nabla \Obj$ is Lipschitz continuous.
We have $\theta^\ocp =0$ and $A^\ocp= -4$.

Consider the corresponding SA recursion with additive zero-mean disturbance,

\[
\begin{aligned}
\theta_{n+1} &= \theta_n +\tfrac{g}{(n+1)^\rho}  \{ -\nabla \Obj\, (\theta_n)  +  W_{n+1} \}
\\
& = \theta_n +\tfrac{1}{(n+1)^\rho}  \{ \barf (\theta_n)  +  gW_{n+1} \}     \,,\quad n\ge 0,
\end{aligned}
\]

where we adopt the notation $ \barf =  -g\nabla \Obj$ so that the step-size is of the form assumed in (A5a).    It will be assumed below that
$\bfmW=\{W_n\}$ is i.i.d. It follows that (DV3) holds for any function $V$ for which $\Expect[e^{V(W_k)}] <\infty$ and with $W=V$.

The example is designed so that  the value of $g$ minimizing the solution to (<ref>) is $g^\ocp =1/4$ when $\rho=1$.  However, in consideration of (A5a),
the ODE of interest is:

\[
\ddt \odestate =  -g\nabla \Obj\, (\odestate).
\]

The ODE@$\infty$ is linear, with vector field $\barf_\infty(\theta) = - g\theta$.     Based on the solidarity between the two ODEs for large $\|\theta\|$,    the best we can hope for in the exponential stability bound (<ref>)  is $ \rhoexp = g$.   Consequently, the value $g^\ocp=1/4$  violates the assumption $ \rhoexp >1/2$.

[Comparing SA and Euler approximations, and illustrating the CLT for SA]The first row shows a comparison of the parameter estimates from SA and the ODE solution,  with common initial condition $\theta_0 = 100$.   The columns are distinguished by the value of $\rho$ indicated, which determines the time axis $\SAtime_k$.
The second row  illustrates the
CLT for these three values of $\rho$.

While the assumption fails, we find that the CLT appears to hold in some experiments.    The numerical results that follow are based on simulations using an i.i.d. disturbance, in which the distribution of each $W_n$ is Gaussian, $N(0,\sigma_W^2)$  with $\sigma_W=10$.    In this scalar example we adopt the notation $\sigma_\theta^2 = \Sigma_\theta$,  and (<ref>) becomes,

\[
2[\tfrac{1}{2} \diffalpha - 4g] \sigma_\theta^2  + \sigma_W^2 g^2 = 0,
\]

where $\diffalpha = 1$ for $\rho=1$, and $\diffalpha$ is zero otherwise.

The top row of <Ref>
illustrates the   transient behavior using the step-size $\alpha_n= g^\ocp/n^\rho$.
As always,  $\ODEstate_{\SAtime_k} = \theta_k$, and we used the approximation $\odestate_{\SAtime_k} =
\bartheta_k$   obtained from the deterministic Euler scheme (<ref>).
The first plot illustrates the very slow convergence when $\rho =1$,  where the horizon $N=10^5$ corresponds to $\SAtime_N\approx 2.8$.
Very little variability is observed because of the large initial condition combined with small gain, $g^\ocp=1/4$.

The histograms shown in   the second row were obtained based on 500 independent runs,  time horizon $N=10^6$,   and with initial condition sampled independently $\theta_0\sim N(0,1)$ (a small variance so that the transient behavior has less impact).
The normalized error at the end of the run appears approximately Gaussian,   and the empirical asymptotic variance is consistent with   (<ref>) in all cases.

Histogram  with $\theta_0\sim N(0,50^2)$, time horizon $N=10^8$, and $\rho=1$.

When this experiment is repeated with $\theta_0\sim N(0,\sigma^2)$ and $\sigma=50$,      the histograms obtained using $\rho=0.8$ or $0.9$ appear nearly the same.   However, with $\rho=1$ the empirical asymptotic variance is massively larger than predicted  for  any $N \le 10^8$.
<Ref> shows a histogram obtained with  $N=10^8$, for which  $\SAtime_N\approx 4.6$.
The empirical asymptotic covariance   is approximately $2.4\times 10^7$, while the theoretical value is $\sigma^2_\theta = (5/2)^2$.

The situation is far different when $g$ is increased.  For example,  Assumption (A5b) can be verified for $g=3$,  and in this case the empirical asymptotic variance closely matches theory for $N\ge10^4$ with identical initial conditions.

§.§ Counterexample

Consider the M/M/1 queue with uniformization: A countable state space Markov chain  $\bfmQ =\{Q_n\}$ on $\state=\{0,1,2,\dots\}$ with:

\[
Q_{n+1} =
\begin{cases}    Q_n+1   &   \text{prob.\ $\alpha$},
\\
\max\{Q_n-1, 0\}  &   \text{prob.\ $\mu = 1-\alpha$}.
\end{cases}
\]

This is a reversible, geometrically ergodic Markov chain when $\rho=\alpha/\mu<1$, with geometric invariant measure and $\displaystyle \eta \eqdef \Expect_{\pi}[Q_n] = \rho/(1-\rho)$.   However, the stronger drift inequality (DV3) fails to hold.

Consider the following stochastic approximation recursion with initial condition $\theta_0\in\Re$,

\begin{equation}
\theta_{n+1} = \theta_n + \tfrac{1}{n+1} \{ (Q_{n+1} - \eta-1)\theta_n + \CEdist_{n+1} \},
\label{e:sa-mm1}
\end{equation}

where $\bfW=\{ \CEdist_{n} \}$ is i.i.d. and independent of $\bfQ$, with Gaussian marginal $N(0,1)$.
The mean vector field associated with (<ref>) is linear:

\[
\barf(\theta) \eqdef \Expect_\pi\bigl[(Q_{n+1} - \eta -1)\theta + \CEdist_{n+1} \bigr] = -\theta.
\]

While <Ref> implies convergence,
it is impossible to obtain moment bounds:

The following hold for the  SA recursion  (<ref>):

* If $\rho   < 1$, then
\lim_{n\to \infty}  \theta_n =\theta^\ocp = 0$ a.s.

* If $\rho > 1/2$, then
\lim_{n\to \infty} \Expect[\theta_n^2] = \infty$.

Constraint region for scaled queue length process.

A crucial component in the proof of <Ref> is large deviations theory for the  reflected random walk $\bfmQ$.    A standard object of study is the scaled process  $q^n_t = \frac{1}{n} Q_{\lfloor n t \rfloor}$.   As $n\to\infty$ this converges to zero for each $t$ with probability one.   The large deviations question of interest is the probability of a large excursion over a finite time-window as illustrated in <Ref>.  There is an elegant theory for estimating this probability (e.g. <cit.>),  which leads to a short proof of <Ref>.

<Ref> does not say that the CLT fails.   Given the form (<ref>) and the fact that $\{\theta_n\}$ converges to zero,  we might establish the CLT by comparison with the simpler recursion,

\[
\theta_{n+1}^\circ = \theta_n^\circ +\alpha_{n+1}
[\barf(\theta_n^\circ ) + \CEdist_{n+1}]= \theta_n^\circ
+\alpha_{n+1} [ - \theta_n^\circ + \CEdist_{n+1}],
\]

for which
the CLT does hold with asymptotic variance equal to one.

Histograms  of the normalized error for the scalar SA recursion 	(<ref>)
with Markovian multiplicative disturbance, and its Gaussian density approximation.
obtained using Matlab's “hist” command.
The time horizon was $10^4$ for the smaller load, and $10^5$ for $\rho= 6/7$.

<Ref> shows histograms of the normalized error $ \sqrt{n} \theta_n$ for two values of load.   In each case the Gaussian density approximation is approximately $N(0,1)$.   What is missing from these plots is outliers that were removed before plotting the histograms.   For load  $\rho = \alpha/\mu= 3/7$ the outliers were few and not large.    For   $\rho= 6/7$,  nearly 1/3 of the samples were labeled as outliers,  and in this case the outliers were massive:   values exceeding $10^{20}$ were observed in  about 1/5 of runs.

§ CONCLUSION

This paper provides simple criteria for convergence and asymptotic statistics
for stochastic approximation and reinforcement learning.   There are of course
many important avenues for future research:

* Extensions to two time-scale SA is of interest in many domains.   The ideas in this paper will admit extension to this more complex setting, combined with ideas from  <cit.>.

* Is there any hope for finer asymptotic statistics,
such as an Edgeworth expansion or finite-$n$ bounds of
Berry-Esséen type?

* The assumptions are general but rule out the setting of <cit.> in
which $\bfPhi$ is parameter dependent as, for example,

\[
\Phi_{n+1}  =  g(\Phi_n,\theta_n,W_{n+1}),
\]

in which $\bfmW$ is an i.i.d. sequence.   Motivation comes from off-policy TD-learning and actor-critic methods <cit.>.
It is hoped that the conclusions of  <cit.> can be obtained using an extension of the assumptions in this paper. This would require (DV3) for each Markov chain with parameter frozen,

\[
\Phi_{n+1}^\theta  :=  g(\Phi_n^\theta,\theta,W_{n+1}),
\]

along with continuity assumptions on the family of Lyapunov functions.

* Many practitioners in reinforcement learning opt for constant step-size algorithms.  When $\alpha_n\equiv \alpha_0$ is fixed but sufficiently small, it is possible to obtain the drift condition (<ref>) under the assumptions of <Ref> (with (A1) abandoned).   This implies that the fourth moment of $\tiltheta_n$ is uniformly bounded.   A remaining question is
whether bounds on bias and variance can be obtained,  perhaps through analysis of the scaled error $Z_n = \tiltheta_n/\sqrt{\alpha_0}$.  Open questions also include:

$\circ$  Is the joint process $\{ (\theta_n,\Phi_n) : n\ge 0\}$  geometrically ergodic?
Geometric ergodicity will hold under  (<ref>), provided any set of the form $R\times S$ is small,  in which $R\subset\Re^d$ is bounded and $S$ is a sublevel set of $W$ (of the form (<ref>)).

Can we instead establish a topological formulation of geometric ergodicity, as in the prior work
<cit.>, perhaps by applying recent ideas in

Once we have established some form of ergodicity, does it follow that $\{z_k\}$ converges in distribution as $n\to\infty$?
Is the limit approximately Gaussian for small $\alpha_0$?

§ APPENDIX

§.§ Markov chain bounds

Recall the constant $b_v$ was introduced in <Ref> in the ergodic theorem (<ref>), which is equivalently expressed:

\[
\lll P^n -\One\otimes\pi\lll _v  \le b_v   \varrho^n  \,, \qquad n \geq 0.
\]

In this Appendix we will increase this constant if necessary so that the following hold under either (V4) or (DV3):

\begin{equation}
\lll P^n -\One\otimes\pi\lll_v   \le b_v
\quad
\textit{and}
\quad
\lll P^n\lll_v \le b_v    \,, \qquad n \geq 0,
\label{e:bv}
\end{equation}

with $v\eqdef e^V$ under (DV3).

The following holds under (DV3):    For any $n$ and any non-negative sequence $\{\delta_k : 1\le k\le n-1 \}$ satisfying $\sum \delta_k\le 1$,

\begin{equation}
\Expect_x\Bigl[\exp\Bigl( V(\Phi_n) +\sum_{k=0}^{n-1}   \delta_k W(\Phi_k)  \Bigr)  \Bigr]
\le  b_v^2  e^{b} v(x) .
\label{e:DV3multBdd+}
\end{equation}

Let $\Gamma(\delta)$ denote the expectation in (<ref>):

\[
\Gamma(\delta) =
\Expect_x\Bigl[\exp\Bigl( V(\Phi_n) +\sum_{k=0}^{n-1}   \delta_k W(\Phi_k)  \Bigr)  \Bigr].
\]

Viewed as a function $\Gamma\colon\Re^n_+\to\Re_+ \cup \{\infty\}$, this is strictly convex.  To obtain the desired bound we consider the nonlinear program:

\[
\max\{ \Gamma(\delta) :   \delta\in \Re^n_+\,,  \   \sum \delta_k\le 1 \}.
\]

The maximum of a strictly convex function on a polyhedron is attained at an extreme point,  meaning that the optimizer $\delta^*$  is a vector with all entries but one equal to zero.  Consequently,

\[
\Gamma(\delta^*) = \max_{0\le k < n}   \Expect_x\bigl[\exp\bigl( V(\Phi_n) +  W(\Phi_k)  \bigr)  \bigr].
\]

To establish (<ref>) we will obtain the bound:

\begin{equation}
\Expect_x\bigl[\exp\bigl( V(\Phi_n) +  W(\Phi_k)  \bigr)  \bigr]
\le  b_v^2  e^{b} v(x)    \,,\qquad 0\le k\le n-1\,,\ \  x\in\state.
\label{e:DV3multBdd+Extreme}
\end{equation}

For each $k$ we have,

\[
\Expect\bigl[\exp\bigl( V(\Phi_n) +  W(\Phi_k)  \bigr) \mid  \clF_{k+1} \bigr]  =  v_{n-k+1} (\Phi_{k+1}) \exp\bigl(    W(\Phi_k)  \bigr) ,
\]

with $v_{n-k+1} = P^{n-k+1}v$.  By (<ref>)  we have $  \| v_{n-k+1} \|_v   \le b_v $,  so that  $v_{n-k+1} (x)   \le b_v \exp(V(x))$ for all $x$.   Hence by the smoothing property of conditional expectation,

\begin{equation}
\begin{aligned}
\Expect_x\bigl[\exp\bigl( V(\Phi_n) +  W(\Phi_k)  \bigr)  \bigr]
& \le  b_v  \Expect_x\bigl[\exp\bigl( V(\Phi_{k+1}) +  W(\Phi_k)  \bigr)  \bigr]
\\
& \le  b_v   \Expect_x\bigl[\exp\bigl( V(\Phi_k)  + s(\Phi_k)   \bigr)  \bigr],
\end{aligned}
\label{e:n2kPV}
\end{equation}

where the second inequality is via (DV3) in the form,

\[
\Expect\bigl[\exp\bigl( V(\Phi_{k+1}) +  W(\Phi_k)  \bigr) \mid \clF_k  \bigr] \le  \exp\bigl( V(\Phi_k)  + s(\Phi_k)    \bigr) .
\]

Finally, apply the uniform bound $s(x)\le b$   to obtain,

\[
\Expect_x\bigl[\exp\bigl( V(\Phi_k)  + s(\Phi_k)   \bigr)  \bigr]  \le e^b    \Expect_x\bigl[\exp\bigl( V(\Phi_k)      \bigr)  \bigr]  \le  e^b  b_v v(x)     .
\]

This combined with (<ref>)
completes the proof of (<ref>).

The fundamental kernel is defined as the inverse:

\begin{equation}
\label{e:fundamental-z}
\clZ \eqdef  [I - P + \mathbbm{1} \otimes \pi]^{-1} = \sum_{k=0}^\infty [P  - \mathbbm{1}\otimes \pi]^k = I + \sum_{k=1}^\infty [P^k - \mathbbm{1}\otimes \pi].
\end{equation}

When (<ref>) holds we have by the triangle inequality,

\[
\lll \clZ \lll_v \le \sum_{k=1}^\infty \lll P^k - \mathbbm{1}\otimes \pi \lll_v \le  \frac{1}{1-\varrho}b_v .
\]

We require bounds outside of the Banach space $\Lv$:

Under (V4):

* $\clZ$ is a bounded linear operator from $L_\infty^{v^\epsy}$ to $L_\infty^{v^\epsy}$ for each $\epsy\in (0,1]$.

* If (DV3) holds, $\clZ$ is a bounded linear operator from $L_\infty^{W}$ to $L_\infty^{V+1}$.

The first claim follows from Jensen's inequality:   If (V4) holds,  then the same drift condition holds for $v^\epsy$ using $P v^\epsy \le (Pv)^\epsy$ (see  <cit.> or <cit.>).
Part (ii) also follows from Jensen's inequality:  Taking logarithms on both sides of (DV3) gives,

\[
\log\Bigl( \Expect\bigl[\exp\bigl( V(\Phi_{k+1}) + W(\Phi_k) - bs(\Phi_k) \bigr)   \mid \clF_k \bigr] \Bigr)  \leq V(\Phi_k),
\]

and hence by concavity of the logarithm,

\[
\Expect[V(\Phi_{k+1}) + W(\Phi_k) - s(\Phi_k) \mid \clF_k ]  \leq V(\Phi_k) .
\]

This is  the drift condition (V3) of <cit.>.
The conclusion of (ii) then follows from <cit.>.

The following is an example of application of the fundamental kernel and <Ref>.  An $L_2$ version of this result appears as   <cit.>.

Suppose that 	  (V4) and (A1) hold.  Then,
for any function $g\colon\state\to\Re$ satisfying $g^2\in\Lv$ and $\pi(g) =0$, the partial sums converge: For each initial condition $x$, there is a square-integrable random variable $S^g_\infty$ such that:

\[
\lim_{n\to\infty}  \sum_{i= 1}^n \alpha_i  g(\Phi_i)   =  S^g_\infty  \qquad
\mbox{a.s.}
\]

Let $\hag = \clZ g $.  <Ref> tells us that $\hag^2\in\Lv$, and by definition this is a solution to Poisson's equation: $P\hag =\hag -g$.    On denoting $ \MD_i^g  = \hag(\Phi_i) - P\hag\, (\Phi_{i-1})$   and $ \clT^g_i=P\hag\, (\Phi_{i})$,  the partial sum can be expressed as a martingale plus a scaled telescoping series:

\[
S^g_n \eqdef
\sum_{i= 1}^n \alpha_i  g(\Phi_i)   =  M^g_n -      \sum_{i= 1}^n   \alpha_i \{ \clT^g_i -  \clT^g_{i-1} \}\,, \qquad
M^g_n =
\sum_{i= 1}^n   \alpha_i  \MD_i^g  .
\]

The martingale is square integrable:

\[
\Expect[ ( M^g_n )^2] =        \sum_{i= 1}^n   \alpha_i^2 \Expect[( \MD_i^g  )^2 ]
\le \bigl( 2 \sup_{i\ge 0} \Expect[(  \hag(\Phi_i)   )^2 ]\bigr)  \sum_{i= 1}^\infty  \alpha_i^2 .
\]

Hence it is convergent to a square-integrable random variable, denoted $ M^g_\infty $.

To complete the proof we establish convergence of the second term using summation by parts:

\[
\sum_{i= 1}^n   \alpha_i \{ \clT^g_i -  \clT^g_{i-1} \}
\alpha_n \clT^g_n  -
\alpha_1 \clT^g_0  -
\sum_{i= 1}^{n-1}  \clT^g_i    \{ \alpha_{i+1} -\alpha_i \} .
\]

From this we obtain a candidate expression for the limit:

\begin{equation}
S_\infty^g = M_\infty^g  + R_\infty  + \alpha_1 \clT^g_0  \,,\qquad   \textit{with} \quad
R_\infty = \sum_{i= 1}^\infty  \clT^g_i    \{ \alpha_{i+1} -\alpha_i \}   .
\label{e:Sg_def}
\end{equation}

Justification requires two limits:  $\lim_{n\to\infty}  \alpha_n \clT^g_n  = 0$ a.s.,   and the existence of the  sum in (<ref>)
as a square integrable random variable.

The first limit is obtained as follows:

\[
\Expect\Bigl[  \sum_{n=1}^\infty \{  \alpha_n \clT^g_n \}^2 \Bigr]
\le \Bigl(\sup_{n\ge0}    \Expect [   \{   \clT^g_n \}^2  ] \Bigr) \sum_{n=1}^\infty  \alpha_n^2 <\infty.
\]

This implies that $ \alpha_n \clT^g_n\to0$ as $n\to\infty$ a.s.

The second limit is   more challenging.   Denote:

\[
R_n \eqdef \sum_{i= 1}^n  \clT^g_i    \{ \alpha_{i+1} -\alpha_i \}
\,,
\qquad
R_n^+ \eqdef \sum_{i= 1}^n | \clT^g_i |  | \alpha_{i+1} -\alpha_i |  .
\]

The second series converges a.s. and in $L_2$  because it is non-decreasing, with bounded $L_2$ norm:

\[
\| R_n^+  \|_2^2  \le \Bigl(\sup_{i\ge0}   \| \clT^g_i \|_2 \Bigr)^2 \sum_{i=1}^\infty  | \alpha_{i+1} -\alpha_i |    <\infty .
\]

The proof that the sum on the right hand side is finite under (A1) is postponed to <Ref>.   In summary, the following limit exists,

\[
R_\infty^+  = \lim_{n\to\infty} R_n^+ ,
\]

and the limit satisfies $\| R_\infty^+ \|_2<\infty$.

The series $\{ R_n\}$ is absolutely convergent and hence convergent with probability one.
The limit is square-integrable since  $\| R_\infty \|_2 \le \| R_\infty^+ \|_2<\infty$.

The martingale difference sequence defined in (<ref>) is based on the solution to Poisson's equation, $\haf(\theta,\varble)$.
The martingale is not uniquely defined because $\haf$ is only unique up to an additive constant under the assumptions we impose on $\bfPhi$.   However, we now require Lipschitz bounds on $\haf$, which means we must settle on a representation.  Throughout the Appendix we take the solution of the form used in the proof of <Ref>:

\begin{equation}
\haf(\theta, x) \eqdef  \int \clZ(x,dy)  f(\theta,y)\,,\qquad  \theta\in\Re^d  \,,  \  x\in\state .
\label{e:hafZ}
\end{equation}

proposition]t:bounds-H	Suppose that the Lipschitz bounds (<ref>) hold.  We then obtain a Lipschitz bound on  $\haf$ defined in (<ref>) under one of the following conditions:

If (V4) holds and $L^4\in \Lv$, then  there exists a constant $b_{\haf} < \infty$ such that:

\begin{align}
\| \haf(\theta, x)\| & \leq b_{\haf} v(x)^{\fourth} \bigl[1+\|\theta\| \bigr] \,,
\label{e:growth-L} \\
\| \haf(\theta, x) - \haf(\theta', x)\| & \leq b_{\haf} v(x)^{\fourth} \|\theta - \theta'\|\,, \qquad \theta,\theta'\in\Re^d\,,   x\in\state. \label{e:lip-L}
\end{align}

* If (DV3) holds and $L\in L_\infty^W$, then  there exists a constant $b_{\haf} < \infty$ such that:

\begin{align}
\| \haf(\theta, x)\| & \leq b_{\haf}\bigl(1+V(x) \bigr) \bigl[ 1+\|\theta\| \bigr]\,,  \label{e:growth-H} \\
\| \haf(\theta, x) - \haf(\theta', x)\| & \leq b_{\haf} \bigl(1+V(x) \bigr) \|\theta - \theta'\|\,, \qquad \theta,\theta'\in\Re^d\,,   x\in\state.%
\label{e:lip-H}%
\end{align}

Under either (i) or (ii),  the function $\haf$ solves Poisson's equation in the form (<ref>).

To establish Poisson's equation we let $g= f_i(\theta,x)$ for any fixed $i$ and $\theta$.   We have
$g\in L_\infty^{v^\fourth}$ under either (i) or (ii), and  $\hag \eqdef \clZ g$ solves Poisson's equation.   To see this write $ [I - P + \mathbbm{1} \otimes \pi]  \hag  = g$, or equivalently,

\[
P\hag =\hag - g + \pi(\hag).
\]

That is, $\hag$ solves Poisson's equation with $ \pi(\hag) = \pi(g) $,   and $ \| \hag \|_{v^\fourth} <\infty$.

We turn next to the Lipschitz bounds.    Using equivalence of norms on $\Re^d$,  there exists a universal constant $b_d< \infty$ such that,

\begin{equation}
\label{e:bound-growth-L}
\frac{1}{v(x)^{\fourth}}\|\haf(\theta, x)\|
\leq b_d \lll \clZ \lll_{v^\fourth} \sup_{x\in\state} \frac{  1}{v(x)^{\fourth}}  \|f(\theta,x) \|\,, \qquad \theta\in\Re^d\,, x\in\state.
\end{equation}

It follows from (<ref>) that
\|f(\theta,x)\| \leq L(x)[1+\|\theta\|]\leq \|L\|_{v^\fourth} v(x)^{\fourth} \bigl[1+\|\theta\| \bigr]
and hence:

\[
\frac{1}{v(x)^{\fourth}}\|\haf(\theta, x)\| \leq b_d   \|L\|_{v^\fourth}   \lll \clZ \lll_{v^\fourth} \bigl[1+\|\theta\| \bigr] \,, \qquad \theta\in\Re^d\,, x\in\state.
\]

The arguments leading to the bound in (<ref>)  can be applied to $\haf(\theta, x) - \haf(\theta', x)  =   \int \clZ(x,dy) \{  f(\theta,y)- f(\theta',y)\} $ to obtain:

\[
\begin{aligned}
\frac{1}{v(x)^\fourth}\|\haf(\theta, x) - \haf(\theta', x)\|
&\leq b_d  \lll \clZ \lll_{v^\fourth} \sup_{x\in\state} \frac{\|f(\theta,x) - f(\theta',x)\|}{v(x)^\fourth}  \\
& \leq b_d  \lll \clZ \lll_{v^\fourth} \| L\|_{v^\fourth} \|\theta-\theta'\| \,, \qquad x\in\state.
\end{aligned}
\]

This proves (<ref>) and part (i).

The proof of part (ii) 	is identical,  since under the given assumptions $\clZ$ is a bounded linear operator from $L_\infty^W \to L_{\infty}^{V+1}$.

Under (A2) we obtain bounds on the terms in 	the decomposition of $\Delta_{n+1}$ in <Ref>:

* Under (V4):

\begin{align}
\| \MD_{n+2} \| & \leq b_{\haf}\bigl(\Expect[v(\Phi_{n+2})^\fourth \mid \clF_{n+1}] + v(\Phi_{n+2})^\fourth \, \bigr) \bigl[1  + \|\theta_n\| \bigr]  \label{e:lip-md-L}
\\
\|\clT_{n+2}\|    & \leq  b_{\haf} v(\Phi_{n+2})^\fourth \bigl[1 + \|\theta_{n+1}\| \bigr] \label{e:lip-tele-L} \\
\|\clE^{\haf}_{n+2}\| & \leq \alpha_{n+1} b_{\haf} \|L\|_{v^\fourth} v(\Phi_{n+2})^\fourth v(\Phi_{n+1})^\fourth \bigl[1 + \|\theta_n\| \bigr]. \label{e:lip-epsy-L}%
\end{align}

* Under (DV3):

\begin{align}
\| \MD_{n+2} \| & \leq b_{\haf} \bigl(2 + \Expect[V(\Phi_{n+2}) \mid \clF_{n+1}] + V(\Phi_{n+2}) \bigr) \bigl[1  + \|\theta_n\| \bigr]  \label{e:lip-md}\\
\|\clT_{n+2}\|    & \leq b_{\haf}(1+ V(\Phi_{n+2}) ) \bigl[1 + \|\theta_{n+1}\| \bigr] \label{e:lip-tele} \\
\|\clE^{\haf}_{n+2}\| & \leq \alpha_{n+1} b_{\haf} (1+V(\Phi_{n+2})) L(\Phi_{n+1})  \bigl[1 + \|\theta_n\| \bigr].
\label{e:lip-epsy}%
\end{align}

§.§ Almost Sure Convergence

§.§.§ Overview of Proof

We show in <Ref> that the scaled iterates $\{\hattheta_k\}$ defined in <Ref> are uniformly bounded in an
a.s. sense.  From this we   obtain the ODE approximation of $\{\hattheta_k\}$ in <Ref> . Then the asymptotic stability of the origin for the ODE@$\infty$   in Assumption (A3) leads to $\sup_k \|\theta_k\| < \infty$  a.s.  These arguments follow closely  <cit.> and <cit.>.

Convergence of $\{\theta_k\}$ to the invariant set of the ODE follows from standard arguments
<cit.>,  subject to uniform bounds on the terms in  <Ref>.

§.§.§ Details of Proof

A few properties on the step-size sequence $\{\alpha_n\}$ will be used repeatedly.
Recall that   $m_n$ is defined in (<ref>), which can be used to define the starting point of the $n$th   block $T_n$ defined in <Ref>.

Under (A1), the following hold:

\[
\text{\rm (i)} \
\lim_{n \to \infty} \frac{ \alpha_n}{ \alpha_{n+1} } =1
\qquad
\text{\rm (ii)} \
\sum_{n=1}^{\infty} |\alpha_{n+1} - \alpha_{n}| <\infty
\qquad
\text{\rm (iii)} \
\lim_{n \to \infty} \sum_{k=m_n}^{m_{n+1}-1} |\sqrt{\alpha_{k+1}} - \sqrt{\alpha_{k+2}}|= 0.
\]

For (i), write,

\[
\frac{\alpha_{n}}{\alpha_{n+1}} - 1
=   \alpha_n \Bigl(  \frac{1}{ \alpha_{n+1}} -  \frac{1}{ \alpha_{n}} \Bigr) =\alpha_{n} \gamma_n .
\]

This converges to 0 as $n\to\infty$, given that $\gamma_n$ converges to $\gamma$.

For (ii) write,

\[
\sum_{n=1}^{\infty} |\alpha_{n+1} - \alpha_{n}|  =\sum_{n=1}^{\infty} |\gamma_n| \alpha_n\alpha_{n+1}.
\]

The right hand side is finite due to  (i) and (<ref>).

Part (iii) is based on similar manipulations:

\[
\begin{aligned}
\sum_{k=m_n}^{m_{n+1}-1} |\sqrt{\alpha_{k+1}} - \sqrt{\alpha_{k+2}}| = \sum_{k=m_n}^{m_{n+1}-1} \frac{|\alpha_{k+1} - \alpha_{k+2}|}{\sqrt{\alpha_{k+1}} + \sqrt{\alpha_{k+2}}}
& = \sum_{k=m_n}^{m_{n+1}-1} |\diffalpha_{k+1}|\frac{\alpha_{k+1}  \alpha_{k+2}}{\sqrt{\alpha_{k+1}} + \sqrt{\alpha_{k+2}}} \\
& \leq \sup_j |\gamma_j| \sum_{k=m_n}^{m_{n+1}-1}\frac{\alpha_{k+2}}{\sqrt{\alpha_{k+1}}+\sqrt{\alpha_{k+2}}}\alpha_{k+1}.
\end{aligned}
\]

Using $\alpha_k/\alpha_{k+1}\to 1$ as $k\to \infty$ gives,

\[
\lim_{k \to \infty} \frac{\alpha_{k+2}}{\sqrt{\alpha_{k+1}}+\sqrt{\alpha_{k+2}}}
\half \lim_{k \to \infty}  \sqrt{\alpha_{k+2}} =0.
\]

These bounds combined with the fact that $\sum_{k = m_n}^{m_{n+1}-1}\alpha_{k+1} \leq T+1$ for all $n\geq 0$ imply (iii).

Under (A1) there is a constant $b_0$ such that for each $n \ge 1$,   $m_n<k\le m_{n+1}$ and  $t\in [\SAtime_{k-1},\SAtime_k]$,

\[
\begin{aligned}
\| \ODEstate_t - \odestate^{(n)}_t \|  &  \le  \max \{ \| \ODEstate_{\SAtime_k} - \odestate^{(n)}_{\SAtime_k}  \|     ,\| \ODEstate_{\SAtime_{k-1}} - \odestate^{(n)}_{\SAtime_{k-1}}  \|     \}
+ b_0   \max\{   \| \odestate^{(n)}_{\SAtime_k}  \| ,  \|\odestate^{(n)}_{\SAtime_{k-1}}  \| \}\alpha_k
\\
\| \hatODEstate_t - \hatodestate_t \|  &  \le  \max \{ \| \hatODEstate_{\SAtime_k} - \hatodestate_{\SAtime_k}  \|     ,\| \hatODEstate_{\SAtime_{k-1}} - \hatodestate_{\SAtime_{k-1}}  \|     \}
+ b_0   \max\{   \| \hatodestate_{\SAtime_k}  \| ,  \|\hatodestate_{\SAtime_{k-1}}  \| \}\alpha_k.
\end{aligned}
\]

The proofs are identical, so we include only  the proof of the first bound.

Write $t = (1-\delta) \SAtime_k + \delta \SAtime_{k-1}$ with $\delta\in [0,1]$, so that
$\ODEstate_t  =    (1-\delta) \ODEstate_{ \SAtime_k } + \delta \ODEstate_{ \SAtime_{k-1}}$, and hence,

\[
\| \ODEstate_t - \odestate^{(n)}_t \|  =  \|  (1-\delta) \{ \ODEstate_{ \SAtime_k }  - \odestate^{(n)}_t \} + \delta \{\ODEstate_{ \SAtime_{k-1}} - \odestate^{(n)}_t\} \|.
\]

Then by the triangle inequality,

\[
\| \ODEstate_t - \odestate^{(n)}_t \|
\le (1-\delta)  \|  \ODEstate_{ \SAtime_k }  - \odestate^{(n)}_t \| + \delta \|  \ODEstate_{ \SAtime_{k-1}} - \odestate^{(n)}_t \|
\le \max  \{   \| \ODEstate_{ \SAtime_k }  - \odestate^{(n)}_t \| , \| \ODEstate_{ \SAtime_{k-1}}  - \odestate^{(n)}_t \|  \}.
\]

The proof is completed by applying Lipschitz continuity of $\barf$, which implies that for some $b_0<\infty$,

\[
\max  \{   \|  \odestate^{(n)}_t  - \odestate^{(n)}_{ \SAtime_k }  \| , \|  \odestate^{(n)}_t  - \odestate^{(n)}_{ \SAtime_{k-1}}  \| \}
\le    b_0   \max\{   \| \odestate^{(n)}_{\SAtime_k}  \| ,  \|\odestate^{(n)}_{\SAtime_{k-1}}  \| \}\alpha_k.
\]

The first step to prove <Ref> is to show that the scaled iterates $\{\hattheta_k\}$ are bounded a.s.

Under (V4) and (A1)-(A2),

\[
\sup_{k\geq 0} \|\hattheta_k\| < \infty \,, \qquad \mbox{a.s.}
\]

Fix $n$ and recall that $	\hattheta_{k+1} = \hattheta_k + \alpha_{k+1} f_{c_n}(\hattheta_k, \Phi_{k+1})$ for each $m_n \leq k < m_{n+1}$.
The Lipschitz bound for $f$ is inherited by $f_{c_n}$, giving $\|f_{c_n}(\hattheta_k, \Phi_{k+1})\| \leq L(\Phi_{k+1})(1 + \|\hattheta_k\|)$. By the triangle inequality,

\[
\| \hattheta_{k+1} \| \leq  \|\hattheta_k\| + \alpha_{k+1} L(\Phi_{k+1})(1 + \|\hattheta_k\|).
\]

Adding $1$ to each side gives the recursive bound,

\begin{equation}
\label{e:exp-bound-hat-as}
\begin{aligned}
1 + \| \hattheta_{k+1} \| & \leq  \bigl(1 +  \alpha_{k+1} L(\Phi_{k+1})\bigr)(1 + \|\hattheta_k\|) \\
& \leq \exp\bigl(\alpha_{k+1} L(\Phi_{k+1})\bigr) (1 + \|\hattheta_k\|),
\end{aligned}
\end{equation}

and then by iteration we obtain for each $m_n < k \leq m_{n+1}$,

\[
1 + \| \hattheta_k \| \leq (1 + \|\hattheta_{m_n}\|) \exp\Bigl(\sum_{i=m_n}^{k-1} \alpha_{i+1} L(\Phi_{i+1})\Bigr) \leq 2 \exp\Bigl(\sum_{i=m_n}^{k-1} \alpha_{i+1} L(\Phi_{i+1})\Bigr),
\]

which leads to,

\[
\begin{aligned}
\sup_{m_n\leq k \leq m_{n+1}} \|\hattheta_k\|
& \leq 2 \exp\Bigl(\sum_{i=m_n}^{m_{n+1}-1} \alpha_{i+1} L(\Phi_{i+1})\Bigr) \\
& \leq 2 \exp\bigl(\pi(L) T \bigr) \exp\Bigl(\sum_{i=m_n}^{m_{n+1}-1} \alpha_{i+1} [L(\Phi_{i+1}) - \pi(L)]\Bigr),
\end{aligned}
\]

where we used  $ \|\hattheta_{m_n}\|\le 1$ and $T_{n+1} - T_n\leq T+1 $.   The desired result then follows from <Ref>.

Finer bounds are obtained based on the representation of $\Delta_{k+1}$ in (<ref>).   Denote the scaled variables by:

\[
\begin{aligned}
\hatDelta_{k+1}  &\eqdef   \haMD_{k+2} - \haclT_{k+2} + \haclT_{k+1} + \haepsy_{k+2}
\\
& \eqdef  [  \MD_{k+2}   - \clT_{k+2} + \clT_{k+1} + \clE^{\haf}_{k+2} ]/c_n, \qquad m_n \leq k < m_{n+1}.
\end{aligned}
\]

Substitution into (<ref>)  gives $	\hattheta_{k+1} = \hattheta_k + \alpha_{k+1} [\barf_{c_n}(\hattheta_k) +\hatDelta_{k+1}  ]$,  and applying (<ref>) gives,

\begin{align}
\label{e:hat-theta-cumu}
&	\hattheta_K
=  \hattheta_{m_n} + \sum_{k=m_n}^{K-1} \alpha_{k+1} \barf_{c_n}(\hattheta_k) +
\haMart_{\SAtime_{K+1}}  +   \haclE_{K},
\\
\textit{where}\qquad
\haclE_{K} &\eqdef
\sum_{k=m_n}^{K-1}\alpha_{k+1}\haepsy_{k+2}     + \alpha_{m_n+1}\haclT_{m_n+1}	- \alpha_K\haclT_{K+1}
-  \sum_{k=m_n}^{K-1}[\alpha_{k+1} - \alpha_{k+2}] \haclT_{k+2}
\\
\haMart_{\SAtime_{K} +1 } & \eqdef \sum_{k=m_n}^{K-1}   \alpha_{k+1}  \haMD_{k+2},   \qquad \qquad    m_n<K\le m_{n+1}.
\end{aligned}
\label{e:hat-theta-cumu-clE}
\end{align}

On scaling the bounds in <Ref> we obtain,

\begin{align}
\| \haMD_{k+2} \| & \leq b_{\haf}\bigl(\Expect[v(\Phi_{k+2})^\fourth \mid \clF_{k+1}] + v(\Phi_{k+2})^\fourth \, \bigr) \bigl[1  + \|\hattheta_k\| \bigr]  \label{e:lip-md-L-hat}\\
\|\haclT_{k+2}\|    & \leq  b_{\haf} v(\Phi_{k+2})^\fourth  \bigl[1 + \|\hattheta_{k+1}\| \bigr] \label{e:lip-tele-L-hat} \\
\|\haepsy_{k+2}\| & \leq \alpha_{k+1} b_{\haf} \|L\|_{v^\fourth} v(\Phi_{k+2})^\fourth v(\Phi_{k+1})^\fourth \bigl[1 + \|\hattheta_k\| \bigr]. \label{e:lip-epsy-L-hat}%
\end{align}

Under (V4) and (A1)-(A2),

* The martingale   $\displaystyle \Bigl\{ \sum_{k=1}^n \alpha_{k+1} \haMD_{k+2} : n\ge 1\Bigr\}$ converges a.s.  as $n \to \infty$.

* $\displaystyle \lim_{n\to \infty} \sup_{m_n\leq k < m_{n+1}} \alpha_{k+1} \| \haclT_{k+2} \| = 0$ a.s.

* $\displaystyle\lim_{n\to \infty} \sum_{k=m_n}^{m_{n+1}-1} |\alpha_{k+1} - \alpha_{k+2}| \| \haclT_{k+2} \|= 0$ a.s.

* $\displaystyle \lim_{n\to \infty} \sum_{k=m_n}^{m_{n+1}-1} \alpha_{k+1} \| \haepsy_{k+2}\| = 0$ a.s.

We begin with (i).
By Doob's martingale convergence theorem <cit.>,  it suffices to check,

\[
\sum_{k=1}^{\infty} \alpha_{k+1}^2 \Expect[\|\haMD_{k+2}\|^2 \mid \clF_{k+1}] <\infty \,, \qquad \mbox{a.s.}
\]

<Ref> tells us that    $b_{\hattheta}  \eqdef \sup_{k\ge 1}  \|\hattheta_k\|   <\infty $ a.s.
Given (<ref>), for each $k\geq 1$,

\[
\Expect[\|\haMD_{k+2}\|^2 \mid \clF_{k+1}]  \leq 4 b_{\haf}^2 \Expect[v(\Phi_{k+2})^\half\mid \clF_{k+1}](1 + \|\hattheta_k\|)^2 \leq 4 b_{\haf}^2 (1 + b_{\hattheta})^2 \Expect[v(\Phi_{k+2})^\half \mid \clF_{k+1}].
\]

\[
\sum_{k=1}^{\infty} \alpha_{k+1}^2 \Expect[\|\haMD_{k+2}\|^2 \mid \clF_{k+1}]  \leq 4 b_{\haf}^2 (1 + b_{\hattheta})^2 \sum_{k=1}^\infty \alpha_{k+1}^2 \Expect[v(\Phi_{k+2})^\half \mid \clF_{k+1}]\,, \qquad \mbox{a.s.}
\]

The right hand side is finite a.s. since for each $x=\Phi_0\in\state$,

\[
\Expect_x\Bigl[ \sum_{k=1}^\infty \alpha_{k+1}^2 \Expect[v(\Phi_{k+2})^\half \mid \clF_{k+1}] \Bigr]
\le b_v v(x)^\half 	 \sum_{k=1}^\infty \alpha_{k+1}^2
< \infty.
\]

For (ii), it follows from (<ref>) that for each $n\geq 1$,

\begin{equation}
\label{e:sup-tele-m_n}
\sup_{m_n \leq k < m_{n+1}} \alpha_{k+1}\|\haclT_{k+2} \| \leq b_{\haf}(1+b_{\hattheta}) \sup_{m_n \leq k < m_{n+1}} \alpha_{k+1} v(\Phi_{k+2})^\fourth.
\end{equation}

Since $1+b_{\hattheta}$ is finite a.s., it suffices to show the supremum converges to 0 a.s. as $m_n\to \infty$.
On denoting $g = v^\fourth - \pi(v^\fourth)$ the convergence result  <Ref> implies
that $\{  \sum_{k=0}^n \alpha_{k+1}  g(\Phi_{k+2}) \}$ is convergent, and hence a Cauchy sequence.  Consequently,

\[
\lim_{n\to\infty} \sup_{m_n \leq k < m_{n+1}}  |  \alpha_{k+1} g(\Phi_{k+2})  |   =0,
\]

and by definition of $g$,

\[
\begin{aligned}
\lim_{n\to\infty}
\sup_{m_n \leq k < m_{n+1}} & \alpha_{k+1} v(\Phi_{k+2})^\half
\\
& \le   \lim_{n\to\infty} \sup_{m_n \leq k < m_{n+1}}  |  \alpha_{k+1} g(\Phi_{k+2})  |
\pi(v^\fourth)
\lim_{n\to\infty} \sup_{m_n \leq k < m_{n+1}}     \alpha_{k+1}    =0 .
\end{aligned}
\]

Part   (iii) follows from <Ref> (ii) and <Ref>, and arguments similar to the proof of (ii).

Part (iv)  follows from the fact that $ \| \haepsy_{k+2}\| $ itself is vanishing as $k\to\infty$: it is square summable in $L_2$ and almost surely due to <Ref>
and  (<ref>).

<Ref> is based on (<ref>) and the representation:

\begin{equation}
\label{e:hat-ode-integral}
\hatodestate_{\SAtime_{k+1}}  = \hattheta_{m_n}  + \int_{T_n}^{\SAtime_{k+1}} \barf_{c_n}( \hatodestate_t) \, dt.
\end{equation}

For $m_n\le k<m_{n+1}$,

\begin{align}
\hattheta_{k+1} - \hatodestate_{\SAtime_{k+1}}
& =   \sum_{i=m_n}^k\alpha_{i+1} \barf_{c_n}(\hattheta_i)
-  \int_{T_n}^{\SAtime_{k+1}} \barf_{c_n}( \hatodestate_t) \, dt +\haclE_{k+1}
\label{e:hat-ode-error-1}
\\
& =   \sum_{i=m_n}^k\alpha_{i+1} \{  \barf_{c_n}(\hattheta_i)
-    \barf_{c_n} (\hatodestate_{\SAtime_i} )\}
+\haclE_{k+1}  +\haclE_{k+1}^D,
\label{e:hat-ode-error-2}
\end{align}

where $\{ \haclE_k:  m_n\le k<m_{n+1} \}$ is given in (<ref>), and   $\haclE_{k+1}^D $ is the discretization error resulting from the Riemann-Stieltjes approximation of the integral (<ref>).   It vanishes uniformly with $k$, in the sense that $b^D(n)\to 0$ as $n\to\infty$, with,

\begin{equation}
\label{e:discrete-error-O}
b^D(n) \eqdef\sup_{m_n \leq k < m_{n+1}} \|\haclE_{k+1}^D \|   \le  \bdd{t:pre-hat-ode}  \sum_{i=m_n}^{m_{n+1}-1} \alpha_{i+1}^2,
\end{equation}

and with $ \bdd{t:pre-hat-ode} $ a deterministic constant.

The first two equations (<ref>, <ref>) follow from  (<ref>) and (<ref>).
The bound (<ref>) follows from uniform Lipschitz continuity of $  \barf_{c_n}$.

The previous lemma implies the desired ODE approximation for the scaled parameter sequence:

Under (V4) and (A1)-(A2), $\displaystyle \lim_{n \to \infty} \sup_{t\in[T_n, T_{n+1}]} \|\hatODEstate_t -  \hatodestate_t \| = 0$ a.s.

The following bound follows from    Lipschitz continuity of $\barf_{c_n}$,

\[
\sum_{i=m_n}^k\alpha_{i+1} \{  \barf_{c_n}(\hattheta_i)
-    \barf_{c_n} (\hatodestate_{\SAtime_i} )\}
\le
\barL \sum_{i=m_n}^k \alpha_{i+1} \| \hattheta_{i} - \hatodestate_{\SAtime_{i}}  \|,
\]

where $\barL  $ is the common Lipschitz constant for  any of the scaled functions $ \{ \barf_{c} : c>0\}  $.
Applying (<ref>) and the triangle inequality gives, for $m_n\leq k<m_{n+1}$,

\[
\begin{aligned}
\| \hattheta_{k+1} - \hatodestate_{\SAtime_{k+1}}\|
&\leq \barL \sum_{i=m_n}^k \alpha_{i+1} \| \hattheta_{i} - \hatodestate_{\SAtime_{i}} \|
+b^D(n)  + b^{\clN}(n),
\end{aligned}
\]

with $b^D(n)$ defined in 	(<ref>), and
$b^{\clN}(n) \eqdef \sup_{m_n \leq k < m_{n+1}} \| \haclE_{k+1}\|$.
By the definition of $\haclE_{k+1}$ in (<ref>),

\begin{equation}
\label{e:disturbance-bound}
\begin{aligned}
b^{\clN}(n) \leq \sup_{m_n \leq j < m_{n+1}} & \| \sum_{i = m_n}^{j} \alpha_{i+1} \haMD_{i+2}\| +  \alpha_{m_n+1}\|\haclT_{m_n+1 }\| +  \sup_{m_n \leq j < m_{n+1}} \alpha_{j+1}\|\haclT_{j+2}\|   \\
& + \sum_{i=m_n}^{m_{n+1}-1} |\alpha_{i+1} - \alpha_{i+2}| \|\haclT_{i+2}\|  +   \sum_{i = m_n}^{m_{n+1}-1} \alpha_{i+1} \|\haepsy_{i +2}\|.
\end{aligned}
\end{equation}

The right hand side converges to 0 a.s. as $n\to\infty$ by <Ref>.

\begin{equation}
\label{e:hat-ode-error-2x}
\begin{aligned}
\sup_{m_n \leq j \leq k+1} \| \hattheta_j - \hatodestate_{\SAtime_j} \|
&  \leq  \barL \sum_{i=m_n}^k \alpha_{i+1} \sup_{m_n \leq j \leq i} \| \hattheta_j - \hatodestate_{\SAtime_j} \|  + b(n),
\end{aligned}
\end{equation}

where $b(n) =b^D(n)  + b^{\clN}(n) $ is a vanishing sequence.
By the discrete Gronwall's inequality, it follows from (<ref>) that,

\[
\sup_{m_n \leq j \leq m_{n+1}} \| \hattheta_j - \hatodestate_{\SAtime_j} \| \leq b(n) \exp\bigl( \barL  T \bigr),
\]

from which we obtain the desired result, but only at the  discrete time points $\SAtime_k$:

\[
\lim_{n\to\infty} \sup_{m_n\leq k < m_{n+1}} \| \hattheta_k - \hatodestate_{\SAtime_k} \| = 0\,, \qquad \mbox{a.s.}
\]

This together with <Ref>   completes the proof.

§.§ $L_p$ Bounds

§.§.§ Overview of Proof

The proof of <Ref> is similar to the proof of <Ref>, but more challenging. Starting with the scaled iterates $\{\hattheta_k\}$, we first show in  <Ref> that the conditional fourth moment of $\hattheta_k$ is uniformly bounded in $k$.   <Ref> establishes an ODE approximation of $\{\hattheta_k\}$ in the $L_4$ sense, based on the almost sure ODE approximation <Ref>. The ODE approximation of $\{\hattheta_k\}$ combined with Assumption (A3) leads to the recursive “contraction inequality”  in <Ref> for the conditional expectation of $ \| \theta_{m_{n+1}}\|^4 $  given $ \clF_{m_n+1}$,
which is a crucial step in the proof of <Ref>.

§.§.§ Details of Proof

Recall that $T>0$ specifies the length of time blocks used in the ODE method described in <Ref>. We fix $T=\Trelax$ throughout this section with $\Trelax$ defined in (A4).  All of the bounds obtained in this Appendix are for “large $n$”:
Let $n_g\ge 1$ denote a fixed integer satisfying,

\begin{equation}
\bar{\alpha} \eqdef \sup \{  \alpha_n :  n\ge n_g \} \leq \frac{3}{4}\Bigl(\frac{1}{4\delta_L} - \Trelax\Bigr),
\label{e:ng}
\end{equation}

where $\delta_L \eqdef \|L\|_W$.
For $n\ge n_g$ we obtain under (A4),

\begin{equation}
4\delta_L\sum_{k=m_n}^{m_{n+1}-1}  \alpha_{k+1}
\leq 4\delta_L (\Trelax + \bar{\alpha}) \leq 4\delta_L \Bigl(\Trelax + \frac{3}{4}\Bigl(\frac{1}{4\delta_L} - \Trelax\Bigr) \Bigr) = \frac{3}{4} + \frac{1}{4}\Trelax \cdot 4\delta_L < 1.
\end{equation}

Recall  the definition $\hattheta_k \eqdef \theta_k / c_n$ for $m_n \leq k \leq m_{n+1}$, where $c_n = \max\{1, \|\theta_{m_n}\|\}$.

Under (DV3) and (A1)-(A4), for each $n \ge n_g$ and $m_n \le k <   m_{n+1} $:

* $\displaystyle
\Expect[\exp\bigl( V(\Phi_{k+1}) \bigr)(1 + \|\hattheta_k\|)^{4} \mid \clF_{m_n+1}]  \leq 16b_v^2 e^b \exp\bigl( V(\Phi_{m_n+1}) \bigr) ;

* $\displaystyle
(\|\theta_k\|+1)^4 \leq 16 \exp\bigl(4\delta_L \sum_{j=m_n}^{m_{n+1}-1} \alpha_{j+1}W(\Phi_{j+1})  \bigr) (\|\theta_{m_n}\| + 1)^4.

We restrict to $k>m_n$, since the bounds are trivial in the   special case  $k=m_n$.

The bound $L \le \delta_L W$ combined with (<ref>) gives,

\[
\begin{aligned}
1 + \| \hattheta_{k+1} \| 		& \leq \exp\bigl(\alpha_{k+1} L(\Phi_{k+1})\bigr) (1 + \|\hattheta_k\|) \\
& \leq  \exp\bigl(\delta_L \alpha_{k+1} W(\Phi_{k+1})\bigr) (1 + \|\hattheta_k\|).
\end{aligned}
\]

Iterating this inequality, we obtain for each $m_n \leq k < m_{n+1}$,

\begin{equation}
\label{e:exp-bound-hat}
\begin{aligned}
1 + \| \hattheta_{k+1} \|
&\leq \exp\Bigl(\delta_L \sum_{i=m_n}^k \alpha_{i+1} W(\Phi_{i+1})\Bigr) (1 + \|\hattheta_{m_n}\|).
\end{aligned}
\end{equation}

Multiplying $c_n$ on both sides gives

\[
\begin{aligned}
c_n + \| \theta_{k+1} \|
&\leq \exp\Bigl(\delta_L \sum_{i=m_n}^k \alpha_{i+1} W(\Phi_{i+1})\Bigr) (c_n + \|\theta_{m_n}\|).
\end{aligned}
\]

Then (ii) follows from the facts that $c_n \geq 1$ and $c_n\geq 1 + \|\theta_{m_n}\|$.

Since  $1 + \|\hattheta_{m_n}\| \leq 2$ by construction, (<ref>) also gives,

\[
\begin{aligned}
\exp\bigl(V(\Phi_{k+2})\bigr)(1 + \| \hattheta_{k+1} \|)^4
& \leq 16\exp\Bigl( V(\Phi_{k+2}) +4\delta_L \sum_{i=m_n}^k \alpha_{i+1}  W(\Phi_{i+1})\Bigr)
\\
\Expect\bigl[ \exp(V(\Phi_{k+2})) (1 + \| \hattheta_{k+1} \|)^4 \mid \clF_{m_n+1} \bigr]
&\leq 16\Expect\bigl[ \exp\Bigl( V(\Phi_{k+2}) + 4\delta_L\sum_{i=m_n}^k \alpha_{i+1}  W(\Phi_{i+1})\Bigr) \mid \clF_{m_n+1}  \bigr] \\
&\leq 16b_v^2 e^b \exp\bigl(V(\Phi_{m_n+1}) \bigr),
\end{aligned}
\]

where the final inequality follows from <Ref> and (<ref>). This establishes  (i).

For any random vector $X$, we denote $\|X\|_4^{(n)}\eqdef \Expect \bigl[\|X\|^4 \mid \clF_{m_n+1} \bigr]^{\frac{1}{4}}$, and obtain bounds for various choices of $X$.

Under (DV3) and (A1)-(A4), there exists a constant $\bdd{t:hat-noise-bounds} < \infty$ such that for all $n \geq n_g$ and $m_n\le k< m_{n+1} $,

\begin{align}
\| \haMD_{k+2}\|_4^{(n)} &\leq \bdd{t:hat-noise-bounds}   \exp(\fourth V(\Phi_{m_n+1}))
\label{e:hat-bound-md}
\\
\| \haclT_{k+1} \|_4^{(n)} &\leq \bdd{t:hat-noise-bounds}  \exp(\fourth V(\Phi_{m_n+1}))
\label{e:hat-bound-tele}
\\
\| \haepsy_{k+2}\|_4^{(n)} & \leq \bdd{t:hat-noise-bounds}  \alpha_{k+1}\exp(\fourth V(\Phi_{m_n+1})), \label{e:hat-bound-epsy}
\end{align}

Bounds identical to (<ref>) hold for the scaled noise components:

\[
\begin{aligned}
\| \haMD_{k+2} \| & \leq b_{\haf} \bigl(2 + \Expect[V(\Phi_{k+2}) \mid \clF_{k+1}] + V(\Phi_{k+2}) \bigr) \bigl[1  + \|\hattheta_k\| \bigr] \\
\|\haclT_{k+2}\|    & \leq b_{\haf}\bigl(1+  V(\Phi_{k+2}) \bigr) \bigl[1 + \|\hattheta_{k+1}\| \bigr] \\
\|\haepsy_{k+2}\| & \leq \alpha_{k+1} b_{\haf} \bigl(1+  V(\Phi_{k+2}) \bigr) L(\Phi_{k+1})  \bigl[1 + \|\hattheta_k\| \bigr] .
\end{aligned}
\]

Consider first the martingale difference term $\haMD_{k+2}$:

\[
\|\haMD_{k+2}\|^4 \leq  b_{\haf}^4 \bigl(2 + \Expect[V(\Phi_{k+2}) \mid \clF_{k+1}] + V(\Phi_{k+2}) \bigr)^4(1 + \|\hattheta_k\|)^4,
\]

Taking conditional expectations gives,

\[
\begin{aligned}
\Expect\bigl[\|\haMD_{k+2}\|^4 \mid \clF_{m_n+1} \bigr]
& \leq b_{\haf}^4 \Expect\Bigl[\bigl(2 + \Expect[V(\Phi_{k+2}) \mid \clF_{k+1}] + V(\Phi_{k+2}) \bigr)^4(1 + \|\hattheta_k\|)^4\mid \clF_{m_n+1} \Bigr] \\
& = b_{\haf}^4  \Expect\Bigl[ (1 + \|\hattheta_k\|)^4\Expect\bigl[\bigl(2 + \Expect[V(\Phi_{k+2}) \mid \clF_{k+1}] + V(\Phi_{k+2}) \bigr)^4\mid \clF_{k+1} \bigr] \mid \clF_{m_n+1} \Bigr] .
\end{aligned}
\]

Given $\bigl(2 + \Expect[V(\Phi_{k+2}) \mid \clF_{k+1}] + V(\Phi_{k+2}) \bigr)^4 \leq 32 + 16\Expect[V(\Phi_{k+2})^4 \mid \clF_{k+1}] + 16V(\Phi_{k+2})^4 $, we have:

\[
\Expect\Bigl[\bigl(2 + \Expect[V(\Phi_{k+2}) \mid \clF_{k+1}] + V(\Phi_{k+2}) \bigr)^4\mid \clF_{k+1} \Bigr] \leq 32 + 32\Expect[V(\Phi_{k+2})^4 \mid \clF_{k+1}] .
\]

Applying <Ref> and 	  (<ref>), we can find a constant $b_{4, V} < \infty$ such that,

\Expect[V(\Phi_{k+2})^4 \mid \clF_{k+1}]  \leq  b_{4, V} \exp(V(\Phi_{k+1})),

from which we obtain,

\[
\begin{aligned}
\Expect\Bigl[\bigl(2 + \Expect[V(\Phi_{k+2}) \mid \clF_{k+1}] + V(\Phi_{k+2}) \bigr)^4\mid \clF_{k+1} \Bigr]
&\leq 32 + 32 b_{4, V} \exp\bigl(V(\Phi_{k+1}) \bigr)\\
& \leq [32 + 32 b_{4, V}] \exp\bigl(V(\Phi_{k+1}) \bigr).
\end{aligned}
\]

\[
\begin{aligned}
\Expect\bigl[ \|\haMD_{k+2}\|^4 \mid \clF_{m_n+1} \bigr]
\leq [32 + 32 b_{4, V}] \Expect\bigl[\exp\bigl( V(\Phi_{k+1}) \bigr)(1 + \|\hattheta_k\|)^4 \mid \clF_{m_n+1}  \bigr].
\end{aligned}
\]

The desired result then follows from <Ref> (i).

Consider next the telescoping term $\haclT_{k+1}$, for which,

\[
\|\haclT_{k+1}\|^4 \leq  b_{\haf}^4 \bigl(1+V(\Phi_{k+1})\bigr)^4 (1 + \|\hattheta_k\|)^4.
\]

The fact $\|(1+ V)^4\|_v < \infty$ gives the second bound.

Turning to the final term:

\begin{equation}
\begin{aligned}
\Expect\bigl[ \|\haepsy_{k+2}\|^4 \mid \clF_{m_n+1} \bigr]
&\leq \alpha_{k+1}^4 b_{\haf}^4 \Expect\bigl[ [1+V(\Phi_{k+2})]^4 L(\Phi_{k+1})^4\bigl(1 + \|\hattheta_k\|\bigr)^4 \mid \clF_{m_n+1} \bigr] \\
&\leq \alpha_{k+1}^4 b_{\haf}^4  \Expect\Bigl[ \bigl(1 + \|\hattheta_k\|\bigr)^4 L(\Phi_{k+1})^4 \Expect\bigl[ (1+V(\Phi_{k+2}))^4  \mid \clF_{k+1} \bigr]  \mid \clF_{m_n+1} \Bigr].
\end{aligned}
\label{e:turning-final}
\end{equation}

By Jensen's inequality,

\[
\Expect\bigl[ [1+V(\Phi_{k+2})]^4 \mid \clF_{k+1}\bigr]
\leq \Expect\bigl[ \bigl(1+V(\Phi_{k+2})\bigr)^8 \mid \clF_{k+1} \bigr]^\frac{1}{2}.
\]

Given $\|(1+ V)^8\|_v < \infty$ and $\|L^8\|_v<\infty$ under (A2), we can find constant $b_0 <\infty$ such that,

\[
\begin{aligned}
\Expect\bigl[  \bigl(1+V(\Phi_{k+2})\bigr)^8  \mid \clF_{k+1} \bigr]^\half &\leq b_0^\half \exp(\half V(\Phi_{k+1})) \\
L(\Phi_{k+1})^4 & \leq  b_0^\half \exp(\half V(\Phi_{k+1})).
\end{aligned}
\]

\[
L(\Phi_{k+1})^4 \Expect\bigl[ [1+V(\Phi_{k+2})]^4 \mid \clF_{k+1} \bigr]  \leq b_0 \exp(V(\Phi_{k+1})),
\]

and combining this with (<ref>),

\[
\Expect\bigl[ \|\haepsy_{k+2}\|^4 \mid \clF_{m_n+1} \bigr] \leq \alpha_{k+1}^4 b_{\haf}^4 b_0 \Expect\bigl[ (1 + \|\hattheta_k\|)^4 \exp(V(\Phi_{k+1}))  \mid \clF_{m_n+1} \bigr].
\]

The desired bound in (<ref>) follows from another application of  <Ref> (i).

Let $\{X_k\}$ be a martingale difference sequence satisfying $\Expect[\| X_k\|^4] < \infty$ for each $k$. There exists a constant $\bdd{t:bound-md}<\infty$ such that for any non-negative scalar sequence $\{\delta_k\}$ and $m>0, n > m$,

\[
\Expect[\sup_{m\leq k\leq n} \| \sum_{i=m}^k \delta_i X_i \|^4 ] \leq \bdd{t:bound-md} \bigl(\sum_{i=m}^n \delta_i^2\bigr)^2 \sup_{m\leq k\leq n} \Expect[\|X_k\|^4].
\]

Burkholder's inequality <cit.> implies the desired bound:  For a constant $\bdd{t:bound-md}<\infty$,

\[
\begin{aligned}
\Expect\bigl[ \sup_{m \leq k \leq n} \bigl\| \sum_{i = m}^k \delta_{i} X_{i} \bigl\|^4 \bigr]
\leq \bdd{t:bound-md} \Expect\bigl[ \Bigl(\sum_{i = m}^{n} \delta_{i}^2 \|X_{i}\|^2 \Bigr)^2 \bigr]
& \leq \bdd{t:bound-md} \Expect\bigl[ \Bigl(\sum_{i = m}^{n} \delta_{i}^2\Bigr) \Bigl(\sum_{i = m}^{n}\delta_{i}^2 \|X_{i}\|^4 \Bigr) \bigr] \\
& \leq \bdd{t:bound-md} \bigl(\sum_{i=m}^n \delta_i^2\bigr)^2 \sup_{m\leq k\leq n} \Expect[\|X_k\|^4],
\end{aligned}
\]

where the second inequality follows from the Cauchy-Schwarz inequality.

<Ref> allows us to establish an ODE approximation of the scaled iterates $\{\hattheta_k\}$ in the $L_4$ sense:

Under (DV3) and (A1)-(A4),  there is a vanishing deterministic sequence $\{\bdds{t:hat-ode-approx}_n : n\ge 1\}$ such that:

\begin{equation}
\label{e:hat-ode-approx}
\Expect[\sup_{t\in [T_n, T_{n+1}]} \| \hatODEstate_t -  \hatodestate_t\|^4 \mid \clF_{m_n+1} ]^\fourth \leq \bdds{t:hat-ode-approx}_n\exp(\fourth V(\Phi_{m_n+1})).
\end{equation}

The bound (<ref>) continues to hold,

\begin{equation}
\begin{aligned}
\sup_{m_n \leq j \leq k+1} \| \hattheta_j - \hatodestate_{\SAtime_j} \|
&  \leq  \barL \sum_{i=m_n}^k \alpha_{i+1} \sup_{m_n \leq j \leq i} \| \hattheta_j - \hatodestate_{\SAtime_j} \| + b(n),
\end{aligned}
\label{e:e:hat-ode-error-2x-RepeatingOurselves}
\end{equation}

with $b(n) = b^D(n)  + b^{\clN}(n) $.   The first sequence is bounded by a deterministic vanishing sequence   (recall (<ref>)).

To complete the proof we obtain bounds for  $\| b^{\clN}(n) \|_4^{(n)}$, which requires that we revisit the almost sure bound    (<ref>).
Applying <Ref> to the sum of martingale difference terms in (<ref>) gives,

\[
\begin{aligned}
\Expect\bigl[ \sup_{m_n \leq j \leq k} \bigl\| \sum_{i = m_n}^{j} \alpha_{i+1} \haMD_{i+2} \bigl\|^4 \mid \clF_{m_n+1} \bigr]
&\leq \bdd{t:bound-md}  \Bigl(\sum_{i = m_n}^{m_{n+1}-1} \alpha_{i+1}^2\Bigr)^2 \sup_{m_n\leq k <m_{n+1}} \Expect\bigl[ \|\haMD_{k+2}\|^4 \mid \clF_{m_n+1} \bigr] \\
& \leq \bdd{t:bound-md} \{\bdd{t:hat-noise-bounds}\}^4 \exp(V(\Phi_{m_n+1})) \Bigl(\sum_{i = m_n}^{m_{n+1}-1} \alpha_{i+1}^2\Bigr)^2 ,
\end{aligned}
\]

where the second inequality follows from (<ref>) in <Ref>.

Consider next the supremum involving $\{\haclT_i\}$:

\[
\begin{aligned}
\Expect[\sup_{m_n \leq j \leq k} \alpha_{j+1}^4 \|\haclT_{j+2}\|^4 \mid \clF_{m_n+1} ]
& \leq \sum_{j = m_n}^{m_{n+1}-1} \alpha_{j+1}^4 \Expect[\|\haclT_{j+2}\|^4 \mid \clF_{m_n+1} ] \\
& \leq \{\bdd{t:hat-noise-bounds}\}^4 \exp\bigl(V(\Phi_{m_n+1})\bigr)\sum_{j = m_n}^{m_{n+1}-1} \alpha_{j+1}^4.
\end{aligned}
\]

By the triangle inequality and (<ref>) of <Ref>,

\[
\begin{aligned}
\Bigl\|  \sum_{i=m_n}^{k-1} |\alpha_{i+1} - \alpha_{i+2}| \|\haclT_{i+2}\|   \Bigr\|_4^{(n)}
& \leq  \sum_{i=m_n}^{k-1} |\alpha_{i+1} - \alpha_{i+2}| \|\haclT_{i+2}\|_4^{(n)}\\
& \leq \bdd{t:hat-noise-bounds} \exp\bigl(\fourth V(\Phi_{m_n+1})\bigr)\sum_{j = m_n}^{m_{n+1}-1}|\alpha_{i+1} - \alpha_{i+2}| .
\end{aligned}
\]

<Ref> (ii) asserts that the sum vanishes as $n\to\infty$.

Similarly,  it follows from (<ref>) of <Ref> that,

\[
\begin{aligned}
\Bigl\| \sum_{i = m_n}^k \alpha_{i+1} \|\haepsy_{i +2}\|\Bigr\|_4^{(n)}
& \leq \bdd{t:hat-noise-bounds} \exp(\fourth V(\Phi_{m_n+1})) \sum_{i=m_n}^k \alpha_{i+1}^2
\\
& \leq \bdd{t:hat-noise-bounds} \exp(\fourth V(\Phi_{m_n+1})) \sum_{i=m_n}^{m_{n+1}-1} \alpha_{i+1}^2 .
\end{aligned}
\]

This is also vanishing, which establishes that  $\| b^{\clN}(n) \|_4^{(n)}\to 0$ as $n\to\infty$ as claimed.

Returning to (<ref>), it follows that we  can find a deterministic vanishing sequence $\{\barb(n) \}$ such that for all $m_n\leq k < m_{n+1}$,

\[
\begin{aligned}
\Expect\bigl[  \sup_{m_n \leq j \leq k+1} & \| \hattheta_j - \hatodestate_{\SAtime_j} \|^4 \mid \clF_{m_n+1} \bigr]^{\frac{1}{4}}
\\
&  \leq   \barL\sum_{i=m_n}^k \alpha_{i+1} \Expect\bigl[ \sup_{m_n \leq j \leq i} \| \hattheta_j - \hatodestate_{\SAtime_j} \|^4 \mid \clF_{m_n+1} \bigr]^{\frac{1}{4}} +  \barb(n) \exp(\fourth V(\Phi_{m_n+1})).
\end{aligned}
\]

By the discrete Gronwall's inequality,

\[
\Expect\bigl[  \sup_{m_n \leq j \leq m_{n+1}} \| \hattheta_j - \hatodestate_{\SAtime_j} \|^4 \mid \clF_{m_n+1} \bigr]^{\frac{1}{4}} \leq \barb(n) \exp(\fourth V(\Phi_{m_n+1}))\exp(\barL[T+ 1]).
\]

This combined with <Ref> completes the proof.

Under (DV3) and (A1-A4), we can find a constant $\bdd{t:contract-1/4}<\infty$ such that for all $n\ge n_g$,

\begin{equation}
\label{e:contract-1/4}
\Expect \bigl[\| \theta_{m_{n+1}}\|^4 \mid \clF_{m_n+1}\bigr]^{\frac{1}{4}} \leq \Bigl( \Crelax +  \bdds{t:hat-ode-approx}_n \exp(\fourth V(\Phi_{m_n+1})) \Bigr)(\|\theta_{m_n}\| + 1)  + \bdd{t:contract-1/4},
\end{equation}

where $0 < \Crelax < 1$ is defined in <Ref>.

We begin with <Ref>, which states that:

\begin{equation}
\label{e:c0-contract}
\|\phi_c(t,\theta_0)\| \leq \Crelax < 1\,, \text{ for all } t\in [\Trelax, \Trelax+1] \,,   \ \ c \geq c_0.
\end{equation}

By the triangle inequality, for each $n\ge n_g$,

\[
\begin{aligned}
\Expect \bigl[\| \theta_{m_{n+1}}\|^4 \mid \clF_{m_n+1}\bigr]^{\frac{1}{4}}
& =   \Expect\bigl[\| \hattheta_{m_{n+1}}\|^4 \mid \clF_{m_n+1}\bigr]^{\frac{1}{4}} (\|\theta_{m_n}\| \vee 1) \\
&  \leq  \Expect \bigl[\| \hatODEstate_{T_{n+1}}- \hatodestate_{T_{n+1}}\|^4  \mid \clF_{m_n+1}\bigr]^{\frac{1}{4}} (\|\theta_{m_n}\| \vee 1) \\
& \qquad + \Expect\bigl[\| \hatodestate_{T_{n+1}}\|^4 \mid \clF_{m_n+1}\bigr]^{\frac{1}{4}} (\|\theta_{m_n}\| \vee 1)  \\
&  \leq \Expect\bigl[\| \hatODEstate_{T_{n+1}}- \hatodestate_{T_{n+1}}\|^4  \mid \clF_{m_n+1}\bigr]^{\frac{1}{4}} (\|\theta_{m_n}\| \vee 1) \\
& \qquad + \Expect\bigl[\| \hatodestate_{T_{n+1}}\|^4 \, \ind\{\|\theta_{m_n}\|\geq c_0\} \mid \clF_{m_n+1}\bigr]^{\frac{1}{4}} (\|\theta_{m_n}\| \vee 1)  \\
& \qquad + \Expect\bigl[\| \hatodestate_{T_{n+1}}\|^4 \, \ind\{\|\theta_{m_n}\| < c_0\}  \mid \clF_{m_n+1}\bigr]^{\frac{1}{4}} (\|\theta_{m_n}\| \vee 1).
\end{aligned}
\]

This combined with <Ref> gives:

\[
\Expect\bigl[ \| \hatODEstate_{T_{n+1}}- \hatodestate_{T_{n+1}}\|^4  \mid \clF_{m_n+1} \bigr]^{\frac{1}{4}} \leq \bdds{t:hat-ode-approx}_n  \exp(\fourth V(\Phi_{m_n+1})).
\]

It follows from (<ref>) that,

\[
\Expect\bigl[\| \hatodestate_{T_{n+1}}\|^4 \, \ind\{\|\theta_{m_n}\|\geq c_0\} \mid \clF_{m_n+1} \bigr]^{\frac{1}{4}} (\|\theta_{m_n}\| \vee 1) \leq \Crelax (\|\theta_{m_n}\| \vee 1).
\]

The third term is uniformly bounded :

\[
\sup_{n\geq 0} \Expect\bigl[ \| \hatodestate_{T_{n+1}}\|^4\, \ind\{\|\theta_{m_n}\| < c_0\}  \mid \clF_{m_n+1} \bigr]^{\frac{1}{4}} (\|\theta_{m_n}\| \vee 1) < \infty.
\]

Given the three bounds above, we can find a constant $b < \infty$ such that for all $n\ge n_g$,

\[
\begin{aligned}
\Expect \bigl[\| \theta_{m_{n+1}}\|^4 \mid \clF_{m_n+1}\bigr]^{\frac{1}{4}}
& \leq \Bigl( \Crelax +  \bdds{t:hat-ode-approx}_n \exp(\fourth V(\Phi_{m_n+1})) \Bigr) (\|\theta_{m_n}\| \vee 1) +  b \\
& \leq \Bigl( \Crelax +  \bdds{t:hat-ode-approx}_n \exp(\fourth V(\Phi_{m_n+1})) \Bigr) (\|\theta_{m_n}\| + 1) +  b.
\end{aligned}
\]

The following lemma helps us replace $\| \theta_{m_{n+1}}\|^4$ with $(1+\| \theta_{m_{n+1}}\|)^4$ on the left hand side of (<ref>), which is the term appearing in <Ref>.

For any positive constants $c, \epsy $ we have $\displaystyle	b_{c,\epsy} \eqdef \sup_x \{ (x+c)^4 - (1+\epsy) x^4 \}< \infty$.

(x+c)^4 - (1+\epsy) x^4 = x^4\bigl[(1+ {c}/{x})^4 - (1+\epsy) \bigr] <0
$, for $x>0$ sufficiently large.

The ODE approximation in (<ref>) combined with  the asymptotic stability of the origin for $\ddt \odestate_t = \barf_{\infty}(\odestate_t)$ (see (A3)) leads to the following “contraction bound”:

Under (DV3) and (A1)-(A4), there exists constants $0 < \bdde{t:contract-4} < 1$, $\bdd{t:contract-4} < \infty$,    and a deterministic and vanishing sequence $\{ \bdds{t:contract-4}_n  : n\ge n_g\}$	 such that  for all $n\ge n_g$,

\begin{equation}
\label{e:contract-4}
\Expect \bigl[ \bigl(\| \theta_{m_{n+1}}\| + 1 \bigr)^4 \mid \clF_{m_n+1}\bigr]\leq \Bigl( \bdde{t:contract-4} +  \bdds{t:contract-4}_n \exp(V(\Phi_{m_n+1})) \Bigr) \bigl(\|\theta_{m_n}\| + 1 \bigr)^4  + \bdd{t:contract-4}.
\end{equation}

By <Ref>, for any $\epsy>0$, we have,

\begin{equation}
\label{e:contract-1-epsy}
\Expect[\| (\theta_{m_{n+1}}\| + 1)^4 \mid \clF_{m_n+1}] \leq (1+\epsy)	\Expect[\|\theta_{m_{n+1}}\|^4 \mid \clF_{m_n+1}] + b_{1,\epsy}.
\end{equation}

It follows from (<ref>) that,

\[
\Expect \bigl[\| \theta_{m_{n+1}}\|^4 \mid \clF_{m_n+1}\bigr] \leq \Bigl\{
\bigl( \Crelax +  \bdds{t:hat-ode-approx}_n \exp(\fourth V(\Phi_{m_n+1})) \bigr)(\|\theta_{m_n}\| + 1)  + \bdd{t:contract-1/4} \Bigr\}^4.
\]

By <Ref> once more, for any $\epsy_0 >0$,

\begin{equation}
\label{e:contract-2-epsy}
\begin{aligned}
\Bigl\{
\bigl( \Crelax +  \bdds{t:hat-ode-approx}_n \exp(\fourth &V(\Phi_{m_n+1})) \bigr) (\|\theta_{m_n}\| + 1)  + \bdd{t:contract-1/4}
\Bigr\}^4 \\
&\leq (1+\epsy_0)\Bigl( \Crelax +  \bdds{t:hat-ode-approx}_n \exp(\fourth V(\Phi_{m_n+1})) \Bigr)^4(\|\theta_{m_n}\| + 1)^4  + b_1,
\end{aligned}
\end{equation}

with $b_1$ a   constant that depends on $\bdd{t:contract-1/4}$ and $\epsy_0$.
The following bound holds because   $0<\Crelax<1$ and $V(x)\geq 0$ for $x\in\state$,

\begin{equation}
\label{e:contract-3-epsy}
\begin{aligned}
\bigl( \Crelax +  \bdds{t:hat-ode-approx}_n \exp(\fourth V(\Phi_{m_n+1})) \bigr)^4 \leq  \Crelax^4 +  \clE_0(n) \exp(V(\Phi_{m_n+1})),
\end{aligned}
\end{equation}

where  $ \clE_0(n) \eqdef [\bdds{t:hat-ode-approx}_n]^4 + 4\bdds{t:hat-ode-approx}_n + 6[\bdds{t:hat-ode-approx}_n]^2+ 4[\bdds{t:hat-ode-approx}_n]^3$  is a non-negative vanishing sequence.

We arrive at the bounds,

\[
\begin{aligned}
\Expect \bigl[\| \theta_{m_{n+1}}\|^4 \mid \clF_{m_n+1}\bigr] & \leq \Bigl\{ (1+\epsy_0)  \Crelax^4 +  (1+\epsy_0)  \clE_0(n)\exp(V(\Phi_{m_n+1}))\Bigr\}(\|\theta_{m_n}\| + 1)^4 + b_1
\\
\Expect[\| (\theta_{m_{n+1}}\| + 1)^4 \mid \clF_{m_n+1}]
&  \leq   (1+\epsy)	\Bigl\{ (1+\epsy_0)  \Crelax^4 +  (1+\epsy_0)  \clE_0(n)\exp(V(\Phi_{m_n+1}))\Bigr\}(\|\theta_{m_n}\| + 1)^4\\
&\qquad\qquad\qquad + b_\epsy + (1+\epsy)  b_1,
\end{aligned}
\]

where the first inequality is obtained on combining (<ref>) and (<ref>), and the second follows from the first and   (<ref>).

Since $\epsy$ and $\epsy_0$ can be taken arbitrarily small, we can find $\bdde{t:contract-4}< 1$ and $\bdd{t:contract-4} <\infty$ such that the desired bound holds for all $n\ge n_g$,

\[
\Expect \bigl[(\| \theta_{m_{n+1}}\| + 1)^4 \mid \clF_{m_n+1}\bigr] \leq \Bigl\{ \bdde{t:contract-4} +  \bdds{t:contract-4}_n \exp(V(\Phi_{m_n+1}))\Bigr\}(\|\theta_{m_n}\| + 1)^4 + \bdd{t:contract-4},
\]

with $ \bdds{t:contract-4}_n= (1+\epsy)(1+\epsy_0) \clE_0(n)$.

<Ref>  inspires us to construct a Lyapunov function of the form $L_{m_n} =  \La_{m_n}  + \beta \Lb_{m_n} $, with:

\begin{equation}
\La_{m_n}  = (\| \theta_{m_n} \| + 1)^4  \,,\qquad
\Lb_{m_n} =   ( \| \theta_{m_n} \| + 1)^4 \Expect[    \exp\bigl( V(\Phi_{m_n +1 }) + \epsy^\circ  W(\Phi_{m_n })  \bigr)     \mid \clF_{m_n }   ]   .
\label{e:BigPairDrift}
\end{equation}

It is assumed throughout that  $0 < \beta < 1$ and  $\epsy^\circ \eqdef \frac{1}{4} - \delta \Trelax > 0$. It follows from the identity in (<ref>) that for all $n \geq 0$,

\begin{equation}
\epsy^\circ + 4\delta \sum_{k = m_n+1}^{m_{n+1}}  \alpha_k \leq \frac{1}{4} - \delta \Trelax + \frac{3}{4} + \frac{1}{4}\Trelax \cdot 4\delta \leq 1.
\label{e:block-length-epsy}
\end{equation}

The desired contraction is described as follows:  For 	constants $ \varrho_0 <1$  $b_0<\infty$ and integer $n_0\ge 1$,

\begin{equation}
\Expect[ L_{m_{n+1}}    \mid \clF_{m_n  }   ]   \le  \varrho_0  L_{m_n}    +b_0    \,,  \quad  n\ge n_0.
\label{e:Lcontraction}
\end{equation}

It will follow that the mean of $L_{m_n}$ is uniformly bounded, and
then the proof of  <Ref> is completed by invoking <Ref> (ii) and <Ref>.

Most of the work involves establishing the bound (<ref>).

Applying (DV3) and (<ref>),  the following simple bound holds with probability one,

\begin{equation}
\label{e:LaLbComparison}
\Lb_{m_n}   \le      \exp\bigl( V(\Phi_{m_n }) + b \bigr)   \La_{m_n},
\end{equation}

and hence $\Lb_{m_n}   \le     \exp ( b_V(r) + b  )   \La_{m_n}    $  when $W(\Phi_{m_n })  \le r$,  for any $n$ and $r$.

The bound (<ref>) combined with the definitions gives:

\begin{equation}
\begin{aligned}
\Expect [  \La_{m_{n+1}}   \mid \clF_{m_n }   ]
& \le
\bdde{t:contract-4}  \La_{m_n}  +\bdds{t:contract-4}_n( \| \theta_{m_n} \| + 1)^4   \Expect\bigl[  \exp\bigl( V(\Phi_{m_n + 1} ) \bigr )  \mid \clF_{m_n }  \bigr]  + \bdd{t:contract-4}   \\
& =    \bdde{t:contract-4}  \La_{m_n}
+ \bdds{t:contract-4}_n  \exp\bigl( -\epsy^\circ W(\Phi_{m_n } )    \bigr )    \Lb_{m_n} + \bdd{t:contract-4} .
\end{aligned}
\label{e:gem1}
\end{equation}

By definition and the smoothing property of conditional expectation,

\[
\Expect[ \Lb_{m_{n+1}}    \mid \clF_{m_n  }   ] \\
=   \Expect[ (1 + \|\theta_{m_{n+1}}\|)^4\exp\bigl(V(\Phi_{m_{n+1}+1}) + \epsy^\circ W(\Phi_{m_{n+1}}) \bigr)    \mid \clF_{m_n  }   ]
\]

Using <Ref> (ii) implies
that $ \Expect[ \Lb_{m_{n+1}}     \mid \clF_{m_n  }   ] $
is bounded above by:

\[
16(\|\theta_{m_n}\|+1)^4\Expect\Bigl[ \exp\bigl( V(\Phi_{m_{n+1}+1}) + \epsy^\circ W(\Phi_{m_{n+1}}) + 4\delta \sum_{k=m_n+1}^{m_{n+1}} \alpha_k W(\Phi_k)  \bigr)    \mid \clF_{m_n  }   \Bigr] .
\]

Recall that by construction $\displaystyle \epsy^\circ + 4\delta \sum_{k=m_n+1}^{m_{n+1}} \alpha_k \leq 1$ for each $n\ge n_g$ from (<ref>). <Ref> then implies,

\begin{equation}
\begin{aligned}
\Expect[ \Lb_{m_{n+1}}    \mid \clF_{m_n  }   ]  &  \le   16  (\| \theta_{m_n} \| + 1)^4    b_v^2  e^{b}
\Expect[ \exp\bigl( V(\Phi_{m_n +1 })  \bigr)    \mid \clF_{m_n  }   ]
\\
&  =   16    b_v^2  e^{b}\exp\bigl( -\epsy^\circ W(\Phi_{m_n   })  \bigr)   \Lb_{m_n},
\end{aligned}
\label{e:gem2}
\end{equation}

and hence from (<ref>),

\[
\begin{aligned}
\Expect[ L_{m_{n+1}}    \mid \clF_{m_n  }   ]  \le  \bdde{t:contract-4}  \La_{m_n}
+  \bigl( \bdds{t:contract-4}_n  + 16  \beta       b_v^2  e^{b} \bigr)\exp\bigl( -\epsy^\circ W(\Phi_{m_n   })  \bigr)   \Lb_{m_n}+  \bdd{t:contract-4} .
\end{aligned}
\]

We are close to the desired bound (<ref>),   on considering two cases.  If the coefficient of $ \Lb_{m_n} $ satisfies,

\[
\bigl( \bdds{t:contract-4}_n    +  16 \beta  b_v^2  e^{b} \bigr)\exp\bigl( -\epsy^\circ W(\Phi_{m_n   })  \bigr)      \le  \bdde{t:contract-4},
\]

then we obtain the desired bound with $\varrho_0 = \bdde{t:contract-4} $ and $b_0= \bdd{t:contract-4}$.

In the contrary case, we   have,

\[
\exp\bigl( \epsy^\circ W(\Phi_{m_n   })  \bigr) <  \bigl( \bdds{t:contract-4}_n    +  16 \beta  b_v^2  e^{b} \bigr) /\bdde{t:contract-4} <  \bigl( \bdds{t:contract-4}_n    +  16  b_v^2  e^{b} \bigr) / \bdde{t:contract-4}.
\]

We apply (<ref>), which implies that we can find a constant $b_V^\ocp$ that is independent of $\beta$, such that $  \Lb_{m_n}   \le  b_V^\ocp   \La_{m_n} $, giving (note that $\exp\bigl( -\epsy^\circ W(\Phi_{m_n   })  \bigr) < 1$):

\[
\Expect[ L_{m_{n+1}}    \mid \clF_{m_n  }   ]  \le  \bdde{t:contract-4} \La_{m_n}
+  \bigl(  \bdds{t:contract-4}_n   +  \beta   16      b_v^2  e^{b} \bigr) b_V^\ocp \La_{m_n} + \bdd{t:contract-4} .
\]

Choose $0 < \beta < 1$ so that $  16 \beta  b_v^2  e^{b} b_V^\ocp< 1- \bdde{t:contract-4}$,  and define,

\[
\varrho_0 =  \bdde{t:contract-4} +  \max_{n\ge n_0}
\bigl\{  \bdds{t:contract-4}_n  +  16  \beta  b_v^2  e^{b} \bigr\} b_V^\ocp .
\]

We can choose $n_0\ge 1$ large enough so that $\varrho_0<1$.   Choosing  $b_L=b_0$ we obtain the desired result

\[
\Expect[ L_{m_{n+1}}    \mid \clF_{m_n  }   ]  \le  \varrho_0  \La_{m_n}    +b_0 \le  \varrho_0  L_{m_n}    +b_0    \,,  \quad  n\ge n_0.
\]

Iterating this inequality gives,

\[
\sup_{n\geq 0} \Expect[L_{m_n}] < \infty.
\]

<Ref> (ii) combined with <Ref> finishes the proof.

Suppose the conditions of <Ref> hold. Then, there exists a finite constant $\bdd{t:noise-bound-l4}$ such that for all $n\ge n_g$,

\begin{equation}
\label{e:noise-bound-l4}
\| \MD_{n+2}\|_4 \leq \bdd{t:noise-bound-l4}\,, \qquad \|\clT_{n+1}\|_4\leq \bdd{t:noise-bound-l4} \,, \qquad \|\clE^{\haf}_{n+2}\|_4 \leq \alpha_{n+1}\bdd{t:noise-bound-l4}.
\end{equation}

§.§ Asymptotic statistics

Recall that the FCLT is concerned with the continuous time process defined in  (<ref>),   and the CLT  concerns the discrete time stochastic process defined in  (<ref>).   Most of the work here concerns the FCLT, with the CLT obtained as a corollary.

For the FCLT it  is convenient to introduce the notation:

\begin{equation}
\begin{aligned}
y_k^{(n)} &\eqdef  \tilODEstate_{\SAtime_k}^{(n)}  = \theta_k - \odestate_{\SAtime_k}^{(n)}        &&
\\
z_k^{(n)} &\eqdef     \scerror{\SAtime_k}{n} =\frac{y_k^{(n)}}{\sqrt{\alpha_k}}    \,,   && \qquad k\ge n.
\end{aligned}
\label{e:scaled-error-def}
\end{equation}

Analysis is based on familiar comparisons:
For $k\ge n$,

\begin{align}
\odestate^{(n)}_{\SAtime_{k+1}}  & = \odestate^{(n)}_{\SAtime_k} + \alpha_{k+1}[\barf(\odestate^{(n)}_{\SAtime_k}) - \clE_k^D]
\label{e:resj-disc}
\\
\theta_{k+1} & = \theta_k + \alpha_{k+1}[\barf(\theta_k) + \Delta_{k+1}],
\label{e:SA-theta-noisedecomp}
\end{align}

where $ \clE_k^D$ in (<ref>)
denotes discretization error: Replacing   the integral $\int_{\SAtime_k}^{\SAtime_{k+1}} \barf(\odestate^{(n)}_t)\, dt$  by $\alpha_{k+1}\barf(\theta_k) $.

§.§.§ Overview of proofs of the CLT and FCLT

Define $w_n = \min\{k: \SAtime_k \geq \SAtime_n + T\}$.  If $n=m_{n_0}$ for some integer $n_0$, then   $w_n = m_{n+1}$ follows from (<ref>).
We obtain an update for the scaled error sequence $\{z_k^{(n)}  :  n\le k\le w_n \}$ in order to  establish tightness
of the family of stochastic processes: $\{\scerrorpull{t}{n} :    t\in[0,T] \}_{n=1}^\infty $,
and also identify the limit.

The proof of <Ref> is found in <Ref>.

Under (A2)–(A5a) we have  the approximation,

\begin{equation}
\label{e:SA-y}
y_{k+1}^{(n)} = y_k^{(n)} + \alpha_{k+1}[ A_k y_k^{(n)} + \clE_k^T + \clE_k^D + \Delta_{k+1} ] \,,\quad k\ge n,
\end{equation}

where $A_k= A(\odestate^{(n)}_{\SAtime_k} )$, and
the error terms are interpreted and bounded as follows:

* $\clE_k^T  $ is the error in the Taylor expansion:

\begin{equation}
\clE_k^T  \eqdef  \barf(\theta_k)-
\barf(\odestate^{(n)}_{\SAtime_k})  -A  (\odestate^{(n)}_{\SAtime_k})   (\theta_k -\odestate^{(n)}_{\SAtime_k}    ).
\label{e:clET}
\end{equation}

It admits the bound:  $\clE_k^T = O(\|y_k^{(n)}\|^2 \wedge \|y_k^{(n)}\|)$.

* $\| \clE_k^D\|  = O(\alpha_k \| \theta_k\| )$
(defined below; cf. (<ref>)).

* $\Delta_{k+1} = \MD_{k+2} - \clT_{k+2} + \clT_{k+1} + \clE^{\haf}_{k+2}$, in which $\{\MD_{k}\}$ is a martingale difference sequence.  The remaining terms
$\clT_{k+1} =   \haf(\theta_k, \Phi_{k+1}) $,  and $\clE^{\haf}_{k+2} = \haf(\theta_{k+1}, \Phi_{k+2}) - \haf(\theta_k,  \Phi_{k+2})$ satisfy,

\[
\| \clT_{k+1} \| \le b_{\haf}  \bigl(1+V(\Phi_{k} ) \bigr)   \|   \theta_k \| \,,
\qquad \|\clE^{\haf}_{k+2} \| \le b_{\haf}   \bigl(1+V(\Phi_{k+2} ) \bigr)    \| \theta_{k+1} - \theta_k \|,
\]

with $b_{\haf}$ a finite constant.

Dividing each side of  (<ref>) by $\sqrt{ \alpha_{k+1} }$ gives,

\[
z_{k+1}^{(n)}    = \sqrt{\tfrac{\alpha_k}{ \alpha_{k+1} }}z_k^{(n)} + \alpha_{k+1}[ \sqrt{\tfrac{\alpha_k}{ \alpha_{k+1} }} A_k z_k^{(n)}] + \sqrt{\alpha_{k+1}}[ \clE_k^T + \clE_k^D + \Delta_{k+1} ].
\]

<Ref> provides the approximation $\sqrt{\tfrac{\alpha_k}{\alpha_{k+1}}}  = 1 + \tfrac{\diffalpha}{2} \alpha_k  + O(\alpha_k^2)$, from which we obtain the following:

For $k\ge n$,

\begin{align}
& =   z_k^{(n)} + \alpha_{k+1}[  \tfrac{\diffalpha}{2} I+  A_k ] z_k^{(n) }  + \sqrt{\alpha_{k+1}} \MD_{k+2}
+  \sqrt{\alpha_{k+1}}\bdds{e:SA-z}_k,
\label{e:SA-z}
\\[1em]
& \quad \textit{where} \ \  \bdds{e:SA-z}_k  \eqdef
- \clT_{k+2} + \clT_{k+1}  + \clE_k^T + \clE_k^D +  \clE^{\haf}_{k+2}    + \sqrt{\alpha_{k+1}} \clE_k^\alpha,
\label{e:SA-z-errors}
\end{align}

with   $  \clE_k^\alpha$ the error due to the approximation of $\tfrac{\alpha_k}{ \alpha_{k+1} }$:

\[
\clE_k^\alpha  =  \tfrac{1}{\alpha_{k+1}} \Bigl(  \sqrt{\tfrac{\alpha_k}{ \alpha_{k+1} }}  -\{ 1 + \tfrac{\diffalpha}{2} \alpha_k  \}   \Bigr) z_k^{(n)}
+    \Bigl(  \sqrt{\tfrac{\alpha_k}{ \alpha_{k+1} }}     -1  \Bigr)A_k z_k^{(n)}.
\]

It  satisfies $ \|  \clE_k^\alpha \| = O(\alpha_k)  \|z_k^{(n)}\|$.

The analysis that follows may be regarded as a coupling of (<ref>)  with the time-varying system with martingale-difference disturbance:

\begin{equation}
\cz^{(n)}_{k+1}   =  \cz^{(n)}_k + \alpha_{k+1}[ \tfrac{\diffalpha}{2} I+  A_k]\cz^{(n)}_k + \sqrt{\alpha_{k+1}  } \MD_{k+2}
\,,
\qquad  \cz^{(n)}_n =z_n^{(n)}
\,,
\quad k\ge n .
\label{e:cz}
\end{equation}

The approximation is justified almost surely and  and in $L_2$, by applying the theory in the preceding sections.

The following summarizes the bounds obtained in this subsection.
It will be seen that these bounds combined with standard arguments complete the proof of <Ref>.

The following hold under the assumptions of <Ref>, for any $T>0$:
There exists a constant $\bdd{t:tight}<\infty$ such that:

\[
\begin{aligned}
\Expect\bigl[\|z_k^{(n)} - z_l^{(n)}\|^4 \bigr] & \leq \bdd{t:tight} |\SAtime_k - \SAtime_{l}|^2
\\
\Expect\bigl[\|z_k^{(n)}\|^4 \bigr] &\leq \bdd{t:tight}, &&  \text{ for all }  n\ge  n_g \text{ and } n\leq l < k\leq w_n
\end{aligned}
\]

We next explain why  (A5b) combined with the conclusions of <Ref> and <Ref> imply the CLT.
Let $\{m_n\}$ be any increasing sequence satisfying the assumptions in the convergence theory:   $\SAtime_{m_{n+1} } \ge \SAtime_{m_n} +T$ for each $n$,   and $\lim_{n\to\infty}  [ \SAtime_{m_{n+1} } - \SAtime_{m_n}] =T$.     The FCLT implies the following limit for any continuous and bounded function $g\colon\Re^d\to\Re$:

\begin{equation}
\lim_{n\to\infty}  \Expect[ g( z^{(m_n)}_{m_{n+1}}) ]   =  \Expect[g(X_T)];
\label{e:preFCLTgivesCLT}
\end{equation}

here $\sclim_T$ is Gaussian: The solution to  (<ref>) with initial condition $X_0=\Zero$.
<Ref>  implies that we can go beyond bounded functions.  The following uniform bound holds,

\[
\max_{m_n\le k\le m_{n+1}}  \|z_k^{(m_n)} \|_4  \le b_z,
\]

where $b_z$ grows exponentially with $T$, but independent of $n$.    It follows that (<ref>) holds for any function  satisfying $g=o(\varpi)$, with $\varpi$ the quartic function introduced in <Ref>.
The extension to unbounded functions is via uniform integrability.

The challenge then is to replace  $z^{(m_n)}_{m_{n+1}}$ by $z_n \eqdef (\theta_n - \theta^*)/  \sqrt{\alpha_n} $ in this limit,  which amounts to bounding bias:

\[
z^{(m_n)}_{m_{n+1}}  =  \frac{1}{\sqrt{\alpha_{m_{n+1}}}} \{  \theta_{m_{n+1}}  - \odestate^{(m_n)}_{\SAtime_{m_{n+1}}} \}
z_{m_{n+1}}  +  \frac{1}{\sqrt{\alpha_{ m_{n+1} } }}   \{   \theta^\ocp    - \odestate^{(m_n)}_{\SAtime_{m_{n+1}}} \}.
\]

It is here that we require  the stability condition (<ref>), which provides the     bound,

\[
\begin{aligned}
\|   \theta^\ocp    - \odestate^{(m_n)}_{\SAtime_{m_{n+1}}} \|
\|   \theta^\ocp -   \phi( \SAtime_{m_{n+1}} - \SAtime_{m_n} ;   \theta_{m_n}) \|
\\
&  \le   \bexp e^{ -\rhoexp T } \| \tiltheta_{m_n} \|
=\sqrt{\alpha_{ m_{n} } }   \bexp e^{ -\rhoexp T } \| z_{m_n} \|,
\end{aligned}
\]

and hence from the prior identity,

\begin{equation}
\begin{aligned}
\| z_{m_{n+1}}   \|  &  \le  \|  z^{(m_n)}_{m_{n+1}} \|    +  \xi_{m_n}(T)   \|  z_{m_n}  \|
\\
\| z_{m_{n+1}}   -  z^{(m_n)}_{m_{n+1}} \|   &  \le     \xi_{m_n}(T)   \|  z_{m_n}  \|   \,,
\qquad\qquad
\textit{where}
\quad
\xi_{m_n}(T) =   \sqrt{ \tfrac{\alpha_{ m_n} }{  \alpha_{ m_{n+1} }}} \bexp e^{ -\rhoexp T }.
\end{aligned}
\label{e:c-contract}
\end{equation}

It will be seen that $\xi_{m_n}(T) $ is vanishing with $T$, uniformly in $n$.

It is convenient here to flip the window backwards in time:
For each $k\ge w_1$ denote $w^-_k = \max\{ n  :  w_n \le k \}$,   and

\begin{equation}
\xi^-_k(T) =  \Bigl( \sqrt{  \alpha_{ w_k^-}  /  \alpha_k }  \Bigr)  \bexp e^{ -\rhoexp T } .
\label{e:xi-k}
\end{equation}

<Ref> tells us  that $\{\xi^-_k(T)  \}$ vanishes with $T$,  uniformly in $k$,
from which we obtain the following:

Suppose that the conclusions of <Ref> and <Ref> hold.   If in addition  (A5b) is satisfied, then:

* For any continuous function satisfying $g=o( \varpi)$,

\[
\lim_{k\to\infty}  \Expect[ g( z^{(w^-_k)}_k ) ]   =  \Expect[g(X_T)].
\]

* The error $L_4$ norm    $  \|  z_k   \|_4 $  is uniformly bounded in $k$, and moreover,

\[
\limsup_{k\to\infty}  \|  z_k  - z^{(w^-_k)}_k\|_4   \le \bdds{t:zCLTbdd}_T,
\]

where the right hand side vanishes as $T\to\infty$.

The proof is presented here with the understanding that
<Ref>, <Ref> and <Ref> have been established.
Full details of their proofs are found below.

We first establish  (<ref>) for bounded and continuous functions, and for this it is sufficient to restrict to characteristic functions
<cit.>.     That is, it is sufficient to establish  the family of limits,

\[
\lim_{k\to\infty} \Expect[ \phi_v( z_k ) ]  =\Expect[\phi_v(\sclim)]  \,, \qquad v\in\Re^d,
\]

where $\phi_v(z) = \exp(j v^\transpose z)$ for $z\in\Re^d$ and $j=\sqrt{-1}$. Letting $L_{\phi_v}$ denote a Lipschitz constant for $\phi_v$,  <Ref> (ii) and Jensen's inequality give,

\[
\limsup_{k\to\infty}  | \Expect[\phi_v(z_k)]  -  \Expect[ \phi_v( z^{(w^-_k)}_k ) ]  |
\le L_{\phi_v}  \limsup_{k\to\infty}   \Expect [ \| z_k -  z^{(w^-_k)}_k \| ]
\le L_{\phi_v} \{    \bdds{t:zCLTbdd}_T \}^{1/4}.
\]

Combining this with  <Ref> (i) gives,

\[
\limsup_{k\to\infty}  | \Expect[\phi_v(z_k)]  -  \Expect[\phi_v(X)] |
\le  L_{\phi_v} \{    \bdds{t:zCLTbdd}_T \}^{1/4}   +  |  \Expect[\phi_v(X_T)] -  \Expect[\phi_v(X)] |.
\]

The right hand side vanishes as $T\to\infty$ for any $v$, from which we conclude that   (<ref>) holds for bounded and continuous functions.

<Ref>   imply that $\{ g(z_k) : k\ge 1\}$ are uniformly integrable when  $g=o(\varpi)$,  which justifies extension of  (<ref>) to  unbounded and continuous functions satisfying this bound.

§.§.§ Tightness and the FCLT

We begin with a proof of tightness of the distributions of the two families of stochastic processes $\{ \scerrorpull{t}{n}\,, t\in[0,T]\}_{n=1}^\infty$ and $\{ \odestatepull{t}{n} \,, t\in[0,T]\}_{n=1}^\infty$, along with $L_p$ bounds required for refinements of the FCLT.

Using a well-known criterion for tightness of probability measure over $C([0, T];\Re^d)$ in <cit.>, we establish a form   of uniform continuity: There exists a constant $\bdd{t:tight}<\infty$ such that for all $n\ge n_g$ and $n \leq   l<  k \leq w_n$,

\begin{align}
\Expect\bigl[\|\odestate_{\SAtime_k}^{(n)} - \odestate_{\SAtime_{l}}^{(n)}\|^4 \bigr] \leq \bdd{t:tight} |\SAtime_k - \SAtime_{l}|^2  \label{e:conti-vt} \\
\Expect\bigl[\| \scerrorpull{\SAtime_k}{n} - \scerrorpull{\SAtime_l}{n}\|^4 \bigr] \leq \bdd{t:tight} |\SAtime_k - \SAtime_{l}|^2.
\label{e:conti-zt}
\end{align}

The bound (<ref>) follows directly from  <Ref>.
The bound (<ref>) is the major part of <Ref> that is the main outcome of this subsection, whose proof requires the proof of
<Ref> and another  simple lemma.

Part (ii)  follows from Lipschitz continuity of $\barf$,   and part (iii) follows from <Ref> and
(<ref>) of

For part (i)  we begin with the definition (<ref>), written in the form,

\[
\clE_k^T = R( \odestate^{(n)}_{\SAtime_k}  ,  \theta_k )  \,,  \qquad R(\theta^\circ, \theta) = \barf(\theta) - \barf(\theta^\circ) - A(\theta^\circ)(\theta - \theta^\circ)  \quad \textit{ for $\theta,\theta^\circ\in\Re^d$,}
\]

with $A(\theta^\circ) =  \partial \barf\,  ( \theta^\circ )$.
The bound $\|R(\theta^\circ, \theta) \| = O(\|\theta^\circ- \theta\|^2)$ follows from (A5a).
Also, $R(\theta^\circ, \theta)$  is Lipschitz continuous in $\theta$  with  Lipschitz constant $2\barL$, giving,

\[
\|R(\theta^\circ, \theta) \| \leq b_0 \min(\|\theta^\circ- \theta\|, \|\theta^\circ- \theta\|^2).
\]

The desired bound in (i) then follows from the definition $\clE_k^T = R( \odestate^{(n)}_{\SAtime_k}  ,  \theta_k ) $ and the definition   $y_k^{(n)} = \theta_k - \odestate_{\SAtime_k}^{(n)}   $.

The following bounds hold for each $k\ge 1$,

\begin{equation}
\begin{aligned}
\sqrt{\frac{\alpha_k}{\alpha_{k+1}}} & = 1 + \frac{\diffalpha_k}{2} \alpha_k  + O(\alpha_k^2)\
\\
| \alpha_k - \alpha_{k+1} |  & =
\diffalpha \alpha_k^2  + O(\alpha_k^3),
\end{aligned}
\label{e:sqrtalphas}
\end{equation}

with $\diffalpha_k$ defined in (A1).
Moreover, for a constant $b$ and every $n$ satisfying  $n\ge n_g$
we have:

\begin{align}
\prod_{i=l}^{k-1}(1+ \gamma_i \alpha_i)^\half &\leq  \exp(\half \sum_{i=n}^{w_n} \gamma_i \alpha_i)   &&
\label{e:simpleExpBdd}
\\
\prod_{i=l}^{k-1} \frac{\sqrt{\alpha_{i}}}{\sqrt{\alpha_{i+1}}}    & \le 1+ b   [\SAtime_k - \SAtime_l  ],  \quad
&&  n \leq   l<  k \leq w_n.
\label{e:sqrtProdExpBdd}
\end{align}

The first bound in (<ref>)
follows from the Taylor approximation,

\[
\sqrt{\frac{\alpha_k}{\alpha_{k+1}}}  =\sqrt{1 +\frac{\alpha_k -\alpha_{k+1}}{\alpha_{k+1}}}  = \sqrt{1 + \diffalpha_k \alpha_k} = 1+\frac{\diffalpha_k}{2} \alpha_k  + O(\alpha_k^2).
\]

The second appeared in the proof of <Ref>: From the definitions, $ \alpha_k - \alpha_{k+1}  =  \diffalpha_k \alpha_k   \alpha_{k+1}  $.

The bound (<ref>) follows directly from $1+x\le e^x$ for $x\in\Re$.

Observe that by concavity of the square root we have the strict bound:

\[
\sqrt{\frac{\alpha_i}{\alpha_{i+1}}}
= \sqrt{1 + \diffalpha_i \alpha_i} \le 1+\frac{\diffalpha_i}{2} \alpha_i.
\]

Letting $\bardiffalpha$ denote an upper bound on $\{ \diffalpha_i : i\ge n_g\}$, and using the bound $1+x\le e^x$ gives,

\[
\prod_{i=l}^{k-1} \frac{\sqrt{\alpha_{i}}}{\sqrt{\alpha_{i+1}}}
\le \exp\Bigl( \tfrac{\bardiffalpha }{2} \sum_{i=l}^{k-1}  \alpha_i   \Bigr)
=   \exp\bigl( \tfrac{\bardiffalpha }{2}  [\SAtime_{k-1} - \SAtime_l  ]  \bigr).
\]

Convexity of the exponential also implies the upper bound $e^x  \le 1 + ( e^{\barx} /\barx ) x $,  for any $\barx>0$ and  $0\le x\le \barx$.   With $\barx = \bardiffalpha T/2$ we obtain,

\[
\prod_{i=l}^{k-1} \frac{\sqrt{\alpha_{i}}}{\sqrt{\alpha_{i+1}}}
\le 1+  \bigl( e^{ \barx } /\barx \bigr)  \tfrac{\bardiffalpha }{2}    [\SAtime_{k-1} - \SAtime_l  ]
\le 1+  \tfrac{1 }{T}  e^{  \bardiffalpha T/2 }   [\SAtime_k - \SAtime_l  ]   \,, \qquad   n \leq   l<  k \leq w_n.
\]

This establishes
(<ref>) using $b=  e^{  \bardiffalpha T/2 }/T $.

We next iterate (<ref>).

For each $n$, and $n\leq l < k \leq w_n$,

\begin{equation}
\label{e:zn-acc-sum}
\begin{aligned}
z_k^{(n)} = \Upsilon_{l, k-1}^{(n)} z_{l}^{(n)}  +  \sum_{j=l}^{k-1}\sqrt{\alpha_{j+1}} & \Upsilon_{j+1, k-1}^{(n)}[\clE_j^T  + \clE_j^D +   \Delta_{j+1}], \\
\text{where } \Upsilon_{j+1, k-1}^{(n)} \eqdef &
\begin{cases}
\prod_{i=j+1}^{k-1}[I+\alpha_{i+1}A(\odestate^{(n)}_{\SAtime_{i}})]\frac{\sqrt{\alpha_{i}}}{\sqrt{\alpha_{i+1}}}, & j < k-1 \\
I, & j = k-1.
\end{cases}
\end{aligned}
\end{equation}

Moreover, there exists a deterministic constant $b_{\Upsilon}<\infty$ such that for all $n>0$:

* $\displaystyle
\max_{n< l < k < w_n} \|\Upsilon_{l, k}^{(n)}\| \leq b_{\Upsilon} $.

* $\|\Upsilon_{l, k-1}^{(n)}-I\| \leq b_\Upsilon (\SAtime_k - \SAtime_{l})$.

Let $n>0$ and $l \geq n$ be fixed. Iterating (<ref>) for $k > l$,  gives,

\[
\begin{aligned}
y_k^{(n)} =
\, \prod_{i=l}^{k-1}[I + & \alpha_{i+1}A(\odestate^{(n)}_{\SAtime_{i}})] y_l^{(n)} \\
\, &+ \sum_{j=l}^{k-1}  \alpha_{j+1} \Bigl\{
\prod_{i=j+1}^{k-1}[I+\alpha_{i+1}A(\odestate^{(n)}_{\SAtime_{i}})]\Bigr\} [\clE_j^T + \clE_j^D +  \Delta_{j+1}].
\end{aligned}
\]

Dividing both sides   by $\sqrt{\alpha_k}$ gives (<ref>):

\[
\begin{aligned}
z_k^{(n)} = \Upsilon_{l, k-1}^{(n)} z_{l}^{(n)}+  \sum_{j=l}^{k-1} & \sqrt{\alpha_{j+1}}  \Upsilon_{j+1, k-1}^{(n)}[\clE_j^T  + \clE_j^D +   \Delta_{j+1}].
\end{aligned}
\]

Note that,

\[
\|\Upsilon_{j+1, k-1}^{(n)} \| \leq  \prod_{i=j+1}^{k-1}\|I+\alpha_{i+1}A(\odestate^{(n)}_{\SAtime_{i}})\| \prod_{i=j+1}^{k-1}\frac{\sqrt{\alpha_{i}}}{\sqrt{\alpha_{i+1}}}.
\]

Since $\|A(\theta)\|\leq \barL$ for all $\theta\in\Re^d$, we apply <Ref> to obtain the pair of bounds:

\begin{equation}
\begin{aligned}
\prod_{i=j+1}^{k-1}\|I+\alpha_{i+1}A(\odestate^{(n)}_{\SAtime_{i}}) \|
& \leq \prod_{i=j+1}^{k-1}(1+\alpha_{i+1}\barL) \leq \exp(\barL T)
\\
\prod_{i=j+1}^{k-1}\frac{\sqrt{\alpha_{i}}}{\sqrt{\alpha_{i+1}}}         &  \le 1 + b  [\SAtime_k - \SAtime_l  ]  \le  1+ b  T
\,, \qquad n\leq j < k \leq w_n.
\end{aligned}
\label{e:RecallLemmaProdBdds}
\end{equation}

Therefore, $\Upsilon_{j, k}^{(n)}$ is uniformly bounded for all $n$ and $n\leq j <k \leq w_n$.

We next establish (ii).   The case  $\Upsilon_{k, k-1}^{(n)} \equiv I$ is trivial, so we consider   $\Upsilon_{l, k-1}^{(n)}$ with $l \leq  k-1$, starting with the expression,

\[
\begin{aligned}
\Upsilon_{l, k-1}^{(n)}
&= \Upsilon_{l, k-1}^{(n)} -\prod_{i=l}^{k-1}[I +  \alpha_{i+1}A(\odestate^{(n)}_{\SAtime_{i}})] + \prod_{i=l}^{k-1}[I +  \alpha_{i+1}A(\odestate^{(n)}_{\SAtime_{i}})]
\\
&= \bigl[\prod_{i=l}^{k-1} \frac{\sqrt{\alpha_{i}}}{\sqrt{\alpha_{i+1}}}-1\bigr]
\prod_{i=l}^{k-1}[I +  \alpha_{i+1}A(\odestate^{(n)}_{\SAtime_{i}})] + \prod_{i=l}^{k-1}[I +  \alpha_{i+1}A(\odestate^{(n)}_{\SAtime_{i}})].
\end{aligned}
\]

Applying (<ref>) gives,

\[
\begin{aligned}
\| \Upsilon_{l, k-1}^{(n)}  - I \|
&\le  \| \bigl[\prod_{i=l}^{k-1} \frac{\sqrt{\alpha_{i}}}{\sqrt{\alpha_{i+1}}}-1\bigr]  \|
\|\prod_{i=l}^{k-1}[I +  \alpha_{i+1}A(\odestate^{(n)}_{\SAtime_{i}})] \| + \| I-\prod_{i=l}^{k-1}[I +  \alpha_{i+1}A(\odestate^{(n)}_{\SAtime_{i}})] \|
\\
&\le b   [\SAtime_k - \SAtime_l  ]  \exp(\barL T)   +   \| I-\prod_{i=l}^{k-1}[I +  \alpha_{i+1}A(\odestate^{(n)}_{\SAtime_{i}})] \|.
\end{aligned}
\]

It remains to establish that the second term is bounded by a constant times $\SAtime_k - \SAtime_l  $.
For this we write  for $k\ge l$,

\[
W_k -I \eqdef \prod_{i=l}^{k-1}[I +  \alpha_{i+1}A(\odestate^{(n)}_{\SAtime_{i}})]   -  I
= [ W_{k-1} -I ]+ \alpha_k A(\odestate^{(n)}_{\SAtime_{k-1}})  W_{k-1}.
\]

Applying (<ref>) once more gives  $\| W_{k-1}\| \le 1 +  \exp(\barL T)  $ for $l < k \le w_n$, and hence on applying the triangle inequality,

\[
\| W_k -I \|  \le \| W_{k-1} -I \|  + \alpha_k \barL   \| W_{k-1} \|    \le
\| W_{k-1} -I \|  + \alpha_k    \barL  ( 1 +  \exp(\barL T) ).
\]

This establishes (ii)  with  $b_\Upsilon= \barL  ( 1 +  \exp(\barL T) ) $.

Next we establish bound for each disturbance term on the right hand side of (<ref>).
The bound (i) in <Ref> is far from tight.   Once we obtain $L_4$ bounds on $\{z_k^{(n)}  :  n\le k\le w_n \}$,  we can expect that the left hand side of (i) will vanish as $n\to\infty$.   Our immediate goal   is only to establish   $L_4$ bounds.

The following hold under the assumptions of <Ref>:   There exist a constant $\bdd{t:tight-noise-l4}<\infty$
and a vanishing sequence $\{  \bdds{t:tight-noise-l4}_n : n\ge 1\}$
such that for all $n>0$ and $n\leq l < k \leq w_n$:

* $\displaystyle  \bigl\| \sum_{j=l}^{k-1}\sqrt{\alpha_{j+1}}\Upsilon_{j+1, n+i-1}^{(n)} \clE_j^T \bigr\|_4 \leq \bdd{t:tight-noise-l4} \sum_{j=l}^{k-1} \alpha_{j+1} \|z_j^{(n)}\|_4$.

* $ \displaystyle  \bigl\|  \sum_{j=l}^{k-1}\sqrt{\alpha_{j+1}}\Upsilon_{j+1, k-1}^{(n)}[\clE_j^D  + \clE^{\haf}_{j+2}] \bigr\|_4 \leq \bdds{t:tight-noise-l4}_n \bigl(\SAtime_k - \SAtime_l \bigr)^\half$.

* $\displaystyle  \bigl\|
\sum_{j=l}^{k-1}\sqrt{\alpha_{j+1}}\Upsilon_{j+1, k-1}^{(n)}[\clT_{j+2}-\clT_{j+1}]
\bigr\|_4 \leq    \min\bigl \{  \bdds{t:tight-noise-l4}_n  ,   \bdd{t:tight-noise-l4}  \bigl(\SAtime_k - \SAtime_l \bigr)^\half \bigr\}$.

* $\displaystyle \bigl\|\sum_{j=l}^{k-1}\sqrt{\alpha_{j+1}}\Upsilon_{j+1, k-1}^{(n)}\MD_{j+2} \bigr\|_4 \leq \bdd{t:tight-noise-l4} \bigl(\SAtime_k - \SAtime_l \bigr)^\half $.

The following bounds are required in (i)–(iii): For a finite constant $b_0$:

\begin{equation}
\begin{aligned}
\| \clE_j^T \|_4 \le  b_0 \sqrt{\alpha_j}  \|z_j^{(n)}\|_4
\,, \qquad
\|\clE_j^D\|_4  \leq \alpha_j b_0
\,, \qquad
\|\clE^{\haf}_{j+2}\|_4 \leq \alpha_{j+1}b_0\,, \qquad \|\clT_{j+1}\|_4 \leq b_0
\end{aligned}
\label{e:bounds-O}
\end{equation}

The first bound follows from $\clE_j^T = O(\|y_j^{(n)}\|^2 \wedge \|y_j^{(n)}\|)  \le  O(\sqrt{\alpha_j} \|z_j^{(n)}\|)$.
The remaining bounds follow from <Ref> combined with  <Ref> and

Since $\Upsilon_{j, k}^{(n)}$ is uniformly bounded (recall <Ref>) we have, for a possibly larger constant $b_0$,

\[
\bigl\| \sum_{j=l}^{k-1}\sqrt{\alpha_{j+1}}\Upsilon_{j+1, k-1}^{(n)}\clE_j^T \bigr\| \leq b_0 \sum_{j=l}^{k-1}\alpha_{j+1}\|z_j^{(n)}\|.
\]

The bound in (i) then follows from the triangle inequality.
Part (ii) also follows from the triangle inequality.

Applying summation by parts to the objective in (iii) gives,

\[
\begin{aligned}
\sum_{j=l}^{k-1}\sqrt{\alpha_{j+1}}\Upsilon_{j+1, k-1}^{(n)}[\clT_{j+2}-\clT_{j+1}]
& = \sqrt{\alpha_k} \clT_{k+1} - \sqrt{\alpha_{l+1}} \Upsilon_{l+1, k-1}^{(n)} \clT_{l+1}
\\
&   				\qquad+ \sum_{j=l+1}^{k-1}\sqrt{\alpha_{j+1}}\alpha_j\Bigl\{
\diffalpha_j I +A(\odestate^{(n)}_{\SAtime_j})\Bigr\}\Upsilon_{j+1, k-1}^{(n)}\clT_{j+1},
\end{aligned}
\]

which leads to,

\[
\begin{aligned}
\bigl\| \sum_{j=l}^{k-1}\sqrt{\alpha_{j+1}}\Upsilon_{j+1, k-1}^{(n)}[\clT_{j+2}-\clT_{j+1}] \bigr\| &  \leq  \sqrt{\alpha_k} \|\clT_{k+1}\| + \sqrt{\alpha_{l+1}} \|\Upsilon_{l+1, k-1}^{(n)} \clT_{l+1}\|  \\
&+ \sum_{j=l+1}^{k-1}\sqrt{\alpha_{j+1}}\alpha_j \Bigl\|\bigl\{
\diffalpha_j I +A(\odestate^{(n)}_{\SAtime_j})\bigr\}\Upsilon_{j+1, k-1}^{(n)}\clT_{j+1}\Bigr\| .
\end{aligned}
\]

Using (<ref>) and the inequality $(a+b+c)^4\leq 16 \{ a^4 + b^4+c^4\}$, we may increase the constant $b_0$ once more to obtain,

\[
\begin{aligned}
\Expect\Bigl[\bigl\| \sum_{j=l}^{k-1}\sqrt{\alpha_{j+1}}\Upsilon_{j+1, k-1}^{(n)} & [\clT_{j+2}- \clT_{j+1}] \bigr\|^4\Bigr] \\
&  \leq  b_0\alpha_k^2 \Expect[\|\clT_{k+1}\|^4] + b_0\alpha_{l+1}^2 \Expect[\|\clT_{l+1}\|^4] 	+b_0 \Expect\Bigr[ \Bigr( \sum_{j=l+1}^{k-1}\sqrt{\alpha_{j+1}}\alpha_j \bigl\| \clT_{j+1}\bigr\|  \Bigr)^4 \Bigr].
\end{aligned}
\]

To complete the proof we bound the right hand side:

\begin{equation*}
\alpha_k^2 \Expect[\|\clT_{k+1}\|^4] + \alpha_{l+1}^2 \Expect[\| \clT_{l+1}\|^4]  \leq b_0^4 \sum_{j=l}^{k-1} \alpha_{j+1}^2 \leq b_0^4 \bigl(\sum_{j=l}^{k-1} \alpha_{j+1}\bigr)^2.
\end{equation*}

The left hand side is thus is vanishing with $n$,  and also bounded by a constant times    $\bigl(\SAtime_k - \SAtime_l \bigr)^2$.

Next consider,

\[
\begin{aligned}
\Expect\Bigr[ \Bigr( \sum_{j=l+1}^{k-1}\sqrt{\alpha_{j+1}}\alpha_j \bigl\|\clT_{j+1}\bigr\| \Bigr)^4 \Bigr]
& =  \bigl(\sum_{j=l+1}^{k-1}\alpha_j\bigr)^4 \Expect\Bigr[\Bigr(\frac{1}{\sum_{j=l+1}^{k-1}\alpha_j}  \sum_{j=l+1}^{k-1}\sqrt{\alpha_{j+1}}\alpha_j  \|\clT_{j+1}\| \Bigr)^4 \Bigr] \\
&  \leq  \bigl(\sum_{j=l+1}^{k-1}\alpha_j\bigr)^3 \sum_{j=l+1}^{k-1}\alpha_{j+1}^2\alpha_j \Expect\bigl[\|\clT_{j+1}\|^4\bigr] \\
&  \leq  T^3 b_0^4\sum_{j=l+1}^{k-1}\alpha_{j+1}^2\alpha_j   \le   \bigl(\SAtime_k - \SAtime_l \bigr)^2\clE_n,
\end{aligned}
\]

where the first inequality follows from Jensen's inequality,   and the final inequality holds with $\displaystyle \clE_n \eqdef  T^3 b_0^4 \max_{j\ge n} \{ \alpha_{j+1}^2/ \alpha_j \}$, which vanishes as $n\to\infty$.
Combining these bounds   gives   (iii).

Denote for each $n$, $l \geq n$, and $k > l$,

\[
\Gamma_{l,k}^{(n)} \eqdef \sum_{j=l}^k\sqrt{\alpha_{j+1}}\Upsilon_{j+1, k}^{(n)}\MD_{j+2}.
\]

Setting $\Gamma_{l,l}^{(n)} = 0$, we obtain the recursive representation,

\[
\begin{aligned}
\Gamma_{l,k}^{(n)}
& = \frac{\sqrt{\alpha_{k-1}}}{\sqrt{\alpha_k}}[I+\alpha_kA(\odestate^{(n)}_{\SAtime_{k-1}})]\Gamma_{l,k-1}^{(n)}  + \sqrt{\alpha_k} \MD_{k+1} \\
& =\Gamma_{l,k-1}^{(n)} +  \bigl[(\frac{\sqrt{\alpha_{k-1}}}{\sqrt{\alpha_k}} - 1)I+\sqrt{\alpha_{k-1}}\sqrt{\alpha_k}A(\odestate^{(n)}_{\SAtime_{k-1}})\bigr]\Gamma_{l,k-1}^{(n)}  + \sqrt{\alpha_k} \MD_{k+1} \,,
\end{aligned}
\]

and summing each side then gives,

\[
\begin{aligned}
\Gamma_{l,k}^{(n)}  = \sum_{j=l}^{k-1}\bigl[(\frac{\sqrt{\alpha_j}}{\sqrt{\alpha_{j+1}}} - 1)I+\sqrt{\alpha_j}\sqrt{\alpha_{j+1}}A(\odestate^{(n)}_{\SAtime_j})\bigr]\Gamma_{l,j}^{(n)} +  \sum_{j=l}^{k-1} \sqrt{\alpha_{j+1}} \MD_{j+2} .
\end{aligned}
\]

Applying <Ref>
once more we obtain, with a possibly larger constant $b_0<\infty$,

\[
\bigl\| (\frac{\sqrt{\alpha_j}}{\sqrt{\alpha_{j+1}}} - 1)I+\sqrt{\alpha_j}\sqrt{\alpha_{j+1}}A(\odestate^{(n)}_{\SAtime_j})\bigr\| \leq \alpha_{j+1} b_0 \,, \qquad j>0.
\]

Then, by the triangle inequality,

\[
\begin{aligned}
\| \Gamma_{l,k}^{(n)} \|_4
&\leq b_0 \sum_{j=l}^{k-1} \alpha_{j+1} \| \Gamma_{l,j}^{(n)}\|_4 +  \bigl\|
\sum_{j=l}^{k-1} \sqrt{\alpha_{j+1}} \MD_{j+2} \bigr\|_4 .
\end{aligned}
\]

The discrete Gronwall's inequality then gives,

\[
\| \Gamma_{l,k}^{(n)} \|_4  \leq \exp(b_0\sum_{j=l}^{k-1}\alpha_{j+1})b_0\bigl(\SAtime_k - \SAtime_l \bigr)^\half\leq \exp(b_0 T)b_0\bigl(\SAtime_k - \SAtime_l \bigr)^\half\,, \qquad n\leq l < k\leq w_n.
\]

By <Ref>,

\[
\begin{aligned}
\Expect\bigl[ \sup_{l \leq j \leq k-1} \bigl\| \sum_{i = l}^{j} \sqrt{\alpha_{i+1}} \MD_{i+2} \bigl\|^4  \bigr]
& \leq \bdd{t:bound-md} \sup_{i} \Expect[\|\MD_{i+2}\|^4 ] \bigl(\sum_{i = l}^{k-1} \alpha_{i+1}\bigr)^2 \leq \bdd{t:bound-md} \sup_{i} \Expect[\|\MD_{i+2}\|^4 ] \bigl(\SAtime_k - \SAtime_l \bigr)^2.
\end{aligned}
\]

This and   <Ref>  establishes (iv) since $ \Expect[\|\MD_{i+2}\|^4 ]$ is uniformly bounded by $\{\bdd{t:noise-bound-l4}\}^4$.

Applying the triangle inequality to (<ref>) in <Ref> gives,

\[
\begin{aligned}
\|z_k^{(n)}\|_4  &  \leq  \bigl\| \sum_{j=n}^{k-1}\sqrt{\alpha_{j+1}}\Upsilon_{j+1, k-1}^{(n)}\clE_j^T \bigr\|_4\
+\bigl\| \sum_{j=n}^{k-1}\sqrt{\alpha_{j+1}}\Upsilon_{j+1, k-1}^{(n)}\MD_{j+2}\bigr\|_4 \\
&  +  \bigl\|\sum_{j=n}^{k-1}\sqrt{\alpha_{j+1}}\Upsilon_{j+1, k-1}^{(n)}[\clE_j^D  + \clE^{\haf}_{j+2} - \clT_{j+2}  + \clT_{j+1} ]\bigr\|_4 \,, \qquad n<k \leq w_n.
\end{aligned}
\]

With <Ref>, the above inequality becomes,

\[
\|z_k^{(n)}\|_4  \leq   \bdd{t:tight-noise-l4} \sum_{j=n}^{k-1} \alpha_{j+1} \|z_j^{(n)}\|_4 + 3 \bdd{t:tight-noise-l4}[\SAtime_k - \SAtime_n]^\half \leq \bdd{t:tight-noise-l4} \sum_{j=n}^{k-1} \alpha_{j+1} \|z_j^{(n)}\|_4 +  3\bdd{t:tight-noise-l4} T^\half .
\]

The discrete Gronwall's inequality gives:

\begin{equation}
\label{e:z-bounded-l4}
\sup_n \sup_{n\leq k\leq w_n} \|z_k^{(n)}\|_4 <\infty.
\end{equation}

Another application of the triangle inequality to (<ref>) in <Ref>, for arbitrary $n\leq l < k \leq w_n$, gives,

\[
\begin{aligned}
\| z_k^{(n)}  - z_{l}^{(n)}\|_4
\leq    \|\Upsilon_{l, k-1}^{(n)} -I\|       \|z_{l}^{(n)}\| _4
& +  \Bigl\| \sum_{j=l}^{k-1}\sqrt{\alpha_{j+1}}\Upsilon_{j+1, k-1}^{(n)}\clE_j^T \Bigr\|_4 + \Bigl\| \sum_{j=l}^{k-1}\sqrt{\alpha_{j+1}}\Upsilon_{j+1, k-1}^{(n)}\MD_{j+2} \Bigr\|_4 \\
&  + \Bigl\|  \sum_{j=l}^{k-1}\sqrt{\alpha_{j+1}}\Upsilon_{j+1, k-1}^{(n)}[\clE_j^D  + \clE^{\haf}_{j+2} - \clT_{j+2} + \clT_{j+1}] \Bigr\|_4.
\end{aligned}
\]

The proof of is completed on combining this bound with (<ref>), <Ref> (ii) and <Ref>.

Now that we have established tightness of the sequence of stochastic processes $\{  \scerrorpull{\varble}{n}   :   n\ge 1\}$, the next step in the proof of the FCLT is to characterize any sub-sequential limit.  The following variant of <Ref> will be used in this step.

The following hold under the assumptions of <Ref>:
There exists a vanishing sequence $\{  \bdds{t:tight-noise-l2}_n : n\ge 1\}$
such that for all $n>0$ and $n\leq l < k \leq w_n$:

* $\displaystyle
\Expect\Bigl[
\max_{l \le \ell < k}
\bigl\| \sum_{j=l}^{\ell}
\sqrt{\alpha_{j+1}}   \clE_j^T \bigr\|^2 \Bigr] \leq \bdds{t:tight-noise-l2}_n$.

* $ \displaystyle
\Expect\Bigl[
\max_{l \le \ell < k}
\bigl\| \sum_{j=l}^{\ell}
\sqrt{\alpha_{j+1}}  [\clE_j^D  + \clE^{\haf}_{j+2}]  \bigr\|^2 \Bigr]
\leq \bdds{t:tight-noise-l2}_n  $.

* $ \displaystyle
\Expect\Bigl[
\max_{l \le \ell < k}
\bigl\| \sum_{j=l}^{\ell}
\sqrt{\alpha_{j+1}}  [\clT_{j+2}-\clT_{j+1}] \bigr\|^2 \Bigr]
\leq \bdds{t:tight-noise-l2}_n  $.

The proofs of (ii) and (iii) are identical to the corresponding bounds in <Ref>.

Part (i) requires the tighter bound
$\clE_j^T = O(\|y_j^{(n)}\|^2 \wedge \|y_j^{(n)}\|) $, so that for some constant $b_0$,

\[
\|\clE_j^T  \|^2  \le b_0^2
\min\{  \alpha_j^2 \| z_j^{(n)}\|^4, \alpha_j  \| z_j^{(n)}\|^2\}
\,
\qquad
\Expect[  \|\clE_j^T  \|^2 ]  \le b_0^2
\min\bigl\{  \alpha_j^2 \Expect[   \| z_j^{(n)}\|^4]  , \alpha_j  \Expect[   \| z_j^{(n)}\|^2] \bigr\} .
\]

Applying the triangle inequality in $L_2$ gives,

\[
\begin{aligned}
\Expect\Bigl[
\max_{l \le \ell < k}
\bigl\| \sum_{j=l}^{\ell}
\sqrt{\alpha_{j+1}}  \clE_j^T  \bigr\|^2 \Bigr]^{\half}
\Expect\Bigl[   \Bigl(
\sum_{j=l}^{k-1}
\sqrt{\alpha_{j+1}} \|  \clE_j^T  \bigr\| \Bigr)^2 \Bigr]^{\half}
\\
& \le
\sum_{j=n}^{w_n-1}
\sqrt{\alpha_{j+1}} \Expect\bigl[
\bigl\|  \clE_j^T  \bigr\|^2 \bigr]^{\half}
\\
\sum_{j=n}^{w_n-1}
\sqrt{\alpha_{j+1}}
\min\{  \alpha_j \| z_j^{(n)}\|^2_4, \sqrt{ \alpha_j}  \| z_j^{(n)}\|_2\} .
\end{aligned}
\]

Choose $n_0\ge 1$ so that
$  \alpha_j^2 \Expect [ \| z_j^{(n)}\|^4] \le  \alpha_j  \Expect[ \| z_j^{(n)}\|^2  ] $ for $j\ge n_0$.
The preceding then gives, for all $n\ge n_0$, $ l \ge n$ and $l\le k \le w_n$,

\[
\begin{aligned}
\Expect\Bigl[
\max_{l \le \ell < k}
\bigl\| \sum_{j=l}^{\ell}
\sqrt{\alpha_{j+1}}  \clE_j^T  \bigr\|^2 \Bigr]^{\half}
\sum_{j=n}^{w_n-1}
\sqrt{\alpha_{j+1}}
\alpha_j
\| z_j^{(n)}\|_4^2
\le b_0 T \{ \max_{j\ge n} \sqrt{\alpha_{j+1}}  \| z_j^{(n)}\|_4^2 .
\}
\end{aligned}
\]

The right hand side vanishes as $n\to\infty$.

We next place the problem in the setting of <cit.>,  which requires a particular decomposition.   As motivation, first write  (<ref>)  (with $F = \tfrac{\diffalpha}{2} I+A^\ocp$) as,

\[
\sclim_{\SAtime} =   D_\SAtime  +   M_\SAtime\,,   \qquad 0\le \SAtime\le T \,,\quad \textit{where} \ \   D_\SAtime
= \int_0^\SAtime  [\tfrac{\diffalpha}{2} I+A^\ocp]  \sclim_t \,dt   \,,
\]

and $\{ M_\SAtime \}$ is Brownian motion.  The required decomposition is,

\begin{equation}
\scerrorpull{\SAtime}{n} =   \scerrorpullD{\SAtime}{n} + \scerrorpullMart{\SAtime}{n}   \,,\qquad 0\le \SAtime\le T\,, \  n\ge 1,
\label{e:ethkur-decomposition}
\end{equation}

in which $\{\scerrorpullMart{\varble}{n} \}$ is a martingale for each $n$,   and the first term approximates $ \int_0^\SAtime  [\tfrac{\diffalpha}{2} I+A^\ocp]   \scerrorpull{t}{n}  \,dt  $.

The representation  (<ref>) suggests the choice of martingale,

\[
\scerrorpullMart{\SAtime}{n}  =   \sum_{j=n}^{k-2}   \sqrt{\alpha_{j+1}}\MD_{j+2}   \,, \qquad
\SAtime_k \le \SAtime  <  \SAtime_{k+1} \,,
\]

valid for $\SAtime\ge \SAtime_{n+2}$,  with $ \scerrorpullMart{\SAtime}{n} \eqdef 0$ for  $\SAtime< \SAtime_{n+2}$.
Its covariance   is denoted $\Sigma^{(n)}_\SAtime \eqdef  \Expect[  \scerrorpullMart{\SAtime}{n} (\scerrorpullMart{\SAtime}{n})^\transpose]$.
The representation  (<ref>) combined with
<Ref> then gives us (<ref>) and a useful bound:

\begin{equation}
\begin{aligned}
\scerrorpullD{\SAtime}{n}
&=   \int_0^{\SAtime }[\tfrac{\diffalpha}{2} I   + A ( \odestatepull{t}{n} )]\scerrorpull{t}{n}    \, dt
+ \clE_{\SAtime}^{\scerrorSymbol}(n)   	 	 \,, \qquad
\SAtime_k \le \SAtime  <  \SAtime_{k+1},
\\
\textit{in which }\qquad
& \lim_{n \to \infty}  \Expect\bigl[  \sup_{    0 \le \SAtime \le T }
\|  \clE_{\SAtime}^{\scerrorSymbol}(n)  \|^2 \bigr]  =0.
\end{aligned}
\label{e:SA-approx-z}
\end{equation}

We apply  Theorem 4.1 of  <cit.> to obtain the FCLT.  It is sufficient to establish the following bounds:

\begin{align}
0  &=   \lim_{n\to\infty}   \Expect\bigl[  \sup_{0\le \SAtime\le T} \bigl\|   	\scerrorpull{\SAtime}{n}  -	\scerrorpull{\SAtime-}{n}
\bigr\|^2\bigr]
\label{e:ethkur43}
\\
0  &=   \lim_{n\to\infty}   \Expect\bigl[  \sup_{0\le \SAtime\le T} \bigl\|   	\scerrorpullD{\SAtime}{n}  -	\scerrorpullD{\SAtime-}{n}
\bigr\|^2\bigr]
\label{e:ethkur44}
\\
0  &=   \lim_{n\to\infty}   \Expect\bigl[  \sup_{0\le \SAtime\le T} \bigl\|  \Sigma^{(n)}_\SAtime  - \Sigma^{(n)}_{\SAtime-}
\bigr\|  \bigr]