Convergence of Two-Timescale Markovian Stochastic Approximations with Applications in Reinforcement Learning


Abstract

This work studies the convergence of two-timescale stochastic approximations (SA), a class of iterative algorithms that update two sets of parameters in fast and slow timescales respectively. Notable examples of two-timescale SA in reinforcement learning (RL) include temporal difference learning with gradient correction (TDC) and actor-critic methods. Previously, the stability (i.e., boundedness) and convergence of two-timescale SA were only established under i.i.d. noise. This work instead establishes the stability and convergence of two-timescale SA under Markovian noise, a setup that is more realistic in RL. Notably, we do not need to use any projection operator and the noise does not need to live in a compact space. Our key technical novelty is to control the fast timescale parameter with the running max of the slow timescale parameter, instead of with the current slow timescale parameter, as most prior works do. As a key application, we establish the first almost sure convergence of TDC with eligibility traces under off-policy learning with linear function approximation.

1 Introduction↩︎

Stochastic approximation (SA, [1][4]) concerns algorithms that recursively and randomly update a vector of parameters. Prominent SA algorithms include stochastic gradient descent [5] and temporal difference learning [6]. Many SA algorithms involve computations of two sets of parameters. One set of parameters, referred to as the fast timescale, is updated with a large step size. The other set of parameters, referred to as the slow timescale, is updated with a small step size. A key characteristic is that the smaller step size is asymptotically negligible compared with the larger step size; i.e., asymptotically, the fast timescale parameter is updated as if the slow timescale parameter were static. The two-timescale structure can therefore be regarded as a special implementation of a nested loop, where the fast timescale corresponds to the inner loop while the slow timescale corresponds to the outer loop. The advantage of the two-timescale implementation over a nested loop implementation is that the slow timescale (the outer loop) is continually updated and does not need to wait for the completion of the fast timescale (the inner loop). These SA algorithms are called two-timescale SA [7] and are common in reinforcement learning (RL, [8]). For example, in actor-critic algorithms [9], [10], the fast timescale is the critic that estimates the value of the agent’s policy, and the slow timescale is the actor, which is the policy itself.

Table 1: Comparison between our work and representative works regarding stability and almost sure convergence of SA. Single-timescale is a special case of two-timescale, and i.i.d. noise is a special case of Markovian noise. By “coupled dynamics,” we mean the fast and slow parameters impact each other, rather than only the slow parameters affecting the fast parameters. Notably, our work is the only one that applies to TDC(\(\lambda\)).
Timescale
Timescale
Dynamics
Projection
Noise
Noise
Noise
[4]
[11]
[12]
[13]
[14]
Our Work

A fundamental challenge of the theoretical analysis of two-timescale SA is showing almost sure convergence. The seminal work [7] establishes almost sure convergence when (i) the noise in the two-timescale SA is i.i.d. and (ii) the stability of the two-timescale SA is assumed. Here, by stability, we mean the almost sure boundedness of the parameters. It is well known that stability is usually a prerequisite for establishing almost sure convergence with ODE approaches [3], [4] and in many works on two-timescale SA, e.g., [15], stability is simply assumed. However, for many RL algorithms instantiating two-timescale SA, the noise is a Markov chain, and the stability cannot be assumed directly. Efforts have been made to relax both (i) and (ii). For example, [11] establish the stability of two-timescale SA with i.i.d. noise. [13], [16] establish the stability of single-timescale SA with Markovian noise. However, to our knowledge, no prior work can establish the stability (and thus convergence) of two-timescale SA with Markovian noise, a gap that this work closes. Prior attempts include [12], [14]. However, [12] assume that the two sets of parameters are not coupled and the Markovian noise evolves in a compact space. [14] use additional projections to enforce boundedness (and thus stability). Consequently, none of them applies to representative two-timescale RL algorithms such as temporal difference learning with gradient correction and eligibility traces (TDC(\(\lambda\)), [17], [18]). By contrast, our result requires milder assumptions, as can be seen in Table 1. To summarize, this work makes the following three contributions:

  1. We establish the stability of two-timescale SA with Markovian noise under mild assumptions (Theorem 1) without using additional projections.

  2. Building on the stability, we further establish the almost sure convergence (Theorem 2), where the Markovian noise can evolve in a possibly unbounded and uncountable space.

  3. Applying our new theoretical results, we establish the first almost sure convergence of TDC(\(\lambda\)) under off-policy learning and linear function approximation (Theorem 3).

1.1 Technical Innovation↩︎

This work establishes the stability of two-timescale SA by extending the ODE\(@\infty\) approach in [19]. Essentially, this work can be viewed as a combination of [11] and [13]. Techniques from [11] are used to address (i) and techniques from [13] are used to address (ii). However, to enable this seemingly straightforward combination, we need to introduce a major methodological innovation. Namely, we connect the parameters in the two timescales by bounding the parameter in the fast timescale with the running max of the parameter in the slow timescale. This methodology is a novel contribution to the literature since prior works on two-timescale SA, such as [3], [11], [14], [20][24], either use stronger assumptions or show that the parameter in one timescale is bounded by the parameter in the other timescale at the same step. These requirements cannot be established when combining [11] and [13]. By contrast, we show that a weaker condition is sufficient for combining [11] and [13]. Specifically, the parameter in the fast timescale does not need to be bounded by the parameter in the slow timescale at the same step. Instead, it only needs to be bounded by the maximal parameter in the slow timescale seen so far, as the rescaling scheme in [11] uses the maximal scaling factor seen thus far. Precisely speaking, the methodological innovation is Lemma 1, which tracks the maximal slow parameter previously encountered.

2 Background↩︎

In this work, we study the general two-timescale SA scheme: given an initial \(x_0 \in \mathbb{R}^{d_1}\) and \(y_0 \in \mathbb{R}^{d_2}\), we recursively generate sequences of vectors \(\require{physics} \qty{x_n}\) and \(\require{physics} \qty{y_n}\) by \[\begin{align} x_{n+1} &= x_n + \alpha(n)H(x_n, y_n, W_{n+1}) \tag{1} \\ y_{n+1} &= y_n + \beta(n)G(x_n, y_n, W_{n+1}) \tag{2} \end{align}\] We also define for convenience the concatenation \(z_n \doteq (x_n, y_n)\). Each \(z_n\) is an element of \(\mathbb{R}^{d_1+d_2}\).

In this scheme, \(\require{physics} \qty{\alpha(n)}_{n=0}^\infty\) and \(\require{physics} \qty{\beta(n)}_{n=0}^\infty\) are sequences of deterministic learning rates and \(\require{physics} \qty{W_n}_{n=1}^\infty\) is a sequence of random noise in a general space \(\mathcal{W}\) (not necessarily compact), while \(H:\mathbb{R}^{d_1+d_2} \times \mathcal{W}\to \mathbb{R}^{d_1}\) is a function that maps the current iterate \(z_n\) and noise \(W_{n+1}\) to the actual incremental update of \(x\) (the fast timescale iterate) and \(G:\mathbb{R}^{d_1+d_2} \times \mathcal{W}\to \mathbb{R}^{d_2}\) maps \(z_n\) and \(W_{n+1}\) to the incremental update of \(y\) (the slow timescale iterate).

This is a two-timescale scheme since the stepsizes satisfy \(\lim_{n \rightarrow \infty} \frac{\beta(n)}{\alpha(n)} = 0\). Thus, since we can consider \(y_n\) to remain almost constant relative to \(x_n\) for large \(n\) in the fast timescale, the behavior of \(x_n\) can be studied by analyzing the ordinary differential equation (ODE) \[\begin{align} \dv{x(t)}{t} = h(x(t), y) \label{eq:32intro32ode} \end{align}\tag{3}\] where \(y\) is a fixed constant and \(h(x, y) \doteq \mathbb{E}[H(x, y, \omega)]\) (with respect to a specific probability distribution). In the slow timescale, we can consider \(x_n\) to have already converged to a value that depends on \(y_n\), so we study the ODE \[\begin{align} \dv{y(t)}{t} = g(\lambda(y(t)), y(t)) \label{eq:32intro32ode32y} \end{align}\tag{4}\] where \(\lambda(y)\) denotes the equilibrium of \(\eqref{eq:32intro32ode}\) (i.e., the \(x\) such that \(h(x,y)=0\) for fixed \(y\)) and \(g(x, y) \doteq \mathbb{E}[G(x, y, \omega)]\). The asymptotic behavior of the discrete, stochastic iterates \(\require{physics} \qty{z_n}\) can then be characterized by the continuous, deterministic trajectories of the ODEs 3 and 4 . This is called the ODE method (see [4] for a comprehensive background). For this ODE approximation to be valid, the iterates must be bounded; this is known as stability. One needs to show \[\begin{align} \sup_{n} \norm{z_n} < \infty \qq{a.s.,} \end{align}\] which is widely considered challenging [4], but stability is a critical prerequisite for convergence and many works in the realm of two-timescale SA rely on it [4], [15], [25], [25], [26].

Figure 1: High-level proof roadmap of this work.

3 Main Results↩︎

We begin by giving a structural overview of the rest of the paper (see Figure 1 for a high-level visual). In this section, we will describe our assumptions and present our main results on stability and convergence of two-timescale algorithms. In Section 4, we give a detailed overview of the proof of Lemma 1, which states that the current fast timescale iterate is bounded by the largest slow timescale iterate seen previously. This proof is a fast timescale analysis. In Section 5, we give an overview of the proof of Theorem 1, which establishes stability (boundedness) over all the iterates with probability one. This is a slow timescale analysis. We then utilize the stability results to prove Theorem 2, which shows the convergence of two-timescale SA algorithms under Markovian noise, in Section 6. Finally, in Section 7, we apply our results to prove the convergence of the off-policy RL algorithm TDC(\(\lambda\)).

3.1 Assumptions↩︎

We now briefly discuss our assumptions (the full details are in Appendix 11).

In Assumption 1, we assume that our Markov chain \(\require{physics} \qty{W_n}\) has a unique stationary distribution, a standard assumption in RL.

In Assumption 2, we also assume our learning rates follow standard SA conditions. Importantly, since we are analyzing a two-timescale scheme, we have \(\lim_{n \rightarrow \infty} \frac{\beta(n)}{\alpha(n)} = 0\).

Then, in Assumption 3, we make assumptions about the functions \(H\) and \(G\). For any \(c \in [1, \infty)\), define \[\begin{align} H_c(x, y, w) \doteq \frac{H(cx, cy, w)}{c}, G_c(x, y, w) \doteq \frac{G(cx, cy, w)}{c}. \end{align}\] The functions \(H_c\) and \(G_c\) are rescaled versions of the functions \(H\) and \(G\) and will be used to construct rescaled iterates, a key technique in the ODE method (see, e.g., [4], [19]). Just as in those works, we need the existence of some sort of limiting functions \(H_{\infty}\) and \(G_{\infty}\) for \(H_c\) and \(G_c\) respectively, when \(c \to \infty\).

In Assumption 4, we take \(H_c,G_c,H_{\infty},G_{\infty}\) to be Lipschitz, so that their growth is well-characterized and to guarantee existence and uniqueness of the ODEs of interest, and define their respective expectations \(h_c,g_c,h_{\infty},g_{\infty}\) with respect to the stationary distribution of the Markov chain.

Then, in Assumption 5, we define the limiting ODEs, which are central to the ODE method: \[\begin{align} \frac{dx(t)}{dt} = h_{\infty}(x(t), y), \quad \frac{dy(t)}{dt} = g_{\infty}(\lambda_{\infty}(y(t)), y(t)) \end{align}\] which have the unique globally asymptotically stable equilibria \(\lambda_{\infty}(y)\) (where \(\lambda_{\infty}: \mathbb{R}^{d_2} \rightarrow \mathbb{R}^{d_1}\) is a homogeneous Lipschitz map with \(\lambda_{\infty}(0) = 0\)) and 0 respectively. We define similar objects for \(h\) and \(g\).

Finally, in Assumption 6, we take a natural assumption showing that over long timescales, the average of certain functions is close to the expectation. This regularity assumption about the noise is central to the averaging technique of [3] that we apply.

These assumptions are well-supported in literature that studies stability of SA [4], [11], [13]. We can easily verify that important RL algorithms like TDC(\(\lambda\)) satisfy them rather than simply assuming that stability holds, so our results are widely applicable to general methods.

3.2 Results↩︎

We present our first result, which is a key methodological innovation:

Lemma 1 (Max Slow Iterate Controls Fast Iterate). Let the Assumptions in Appendix 11 hold. Then, there exists a sample path dependent constant \(K\) such that for all \(n\), \[\begin{align} \norm{x_n} \leq K (1 + \norm{y^{\text{max}}_n}) \quad a.s. \end{align}\] where \(y^{\text{max}}_n \doteq y_m\) such that \(m = \arg\max_{i \leq n} \norm{y_i}\) (with ties broken arbitrarily).

We discuss its proof in Section 4. Intuitively, this result tells us that the size of the fast timescale iterates is bounded by the largest slow timescale iterate seen thus far. In the long history of the ODE method, no previous work has attempted to establish and use a result bounding one timescale by the maximum of the other to tie the timescales together (see the introduction for more detail). Having established that the slow timescale iterates control the fast timescale iterates, we are able to prove stability:

Theorem 1 (Stability of Two-Timescale Iterates). The iterates \(\require{physics} \qty{z_n}\) are stable, i.e., \[\begin{align} \sup_n \norm{z_n} < \infty \quad a.s. \end{align}\]

See Section 5 for a discussion of the proof. Once the boundedness of the iterates is established, convergence can be shown. We can now guarantee that the iterates converge to a bounded, nonempty invariant set as the iterates evolve in a compact set, ensuring the existence of subsequential limits.

Theorem 2 (Convergence of Two-Timescale Updates). Let Assumptions 1 - 6 hold. Then the iterates \(\require{physics} \qty{x_n}\) generated by 1 converge almost surely to the equilibrium depending on \(\require{physics} \qty{y_n}\) as follows: \[\begin{align} \lim_{n \rightarrow \infty} \norm{x_n - \lambda(y_n)} = 0 \end{align}\] where \(\lambda: \mathbb{R}^{d_2} \rightarrow \mathbb{R}^{d_1}\) is a Lipschitz map and \(\lambda(y)\) is the globally asymptotically stable equilibrium of \(\dv{x(t)}{t} = h(x(t), y)\). With this convergence established, we can then establish the main two-timescale convergence result: \[\begin{align} \lim_{n \rightarrow \infty} \norm{z_n - (\lambda(y^*), y^*)} = 0. \label{eq:32final32convergence32main32text} \end{align}\tag{5}\]

The discussion of the proof is in Section 6. As with stability, we first establish a convergence result for the fast timescale and then the slow timescale separately. This type of result is the goal of the ODE method. In the proof of Theorem 2, we show convergence to bounded invariant sets, and the assumptions we place on the ODEs (in particular, the existence of unique globally asymptotically stable equilibria) characterize the invariant sets. Since \(\dv{y(t)}{t} = g(\lambda(y(t)), y(t))\) has a unique globally asymptotically stable equilibrium, its invariant set is the singleton set \(\require{physics} \qty{y^*}\), ensuring convergence to the optimal value.

4 Bounding the Fast Timescale Iterates \(x_n\)↩︎

In this section, we will give a discussion of the proof of Lemma 1; see Appendix 12 for the full details. To prove Lemma 1, we conduct analysis in the fast timescale. This allows us to treat the slow timescale iterates as almost constant relative to the fast iterates. Note that the lemmas are derived on an arbitrary sample path \(\require{physics} \qty{x_0,y_0, \qty{W_i}_{i=1}^\infty}\) such that the assumptions in Section 3 hold, so we omit “\(a.s.\)” from the lemma statements for conciseness.

4.1 Setting up the Timeline↩︎

We begin by splitting the positive real axis \([0, \infty)\) into chunks of length \(\require{physics} \qty{\alpha(i)}_{i=0,1,\dots}\). We then collect these segments together into larger intervals \(\require{physics} \qty{[T_n, T_{n+1})}_{n=0,1,\dots}\), where the sequence \(\require{physics} \qty{T_n}\) has the property that as \(n\) grows large, we have \(T_{n+1} - T_n \approx T\). We define \[\begin{align} t(0) \doteq 0, \quad t(n) \doteq \sum_{i=0}^{n-1} \alpha(i) \qq{n=1,2,\dots} \end{align}\] For all \(T > 0\), define \[\require{physics} \begin{align} m(T) = \max\qty{{i | T \geq t(i)}} \end{align}\] as the maximal \(i\) where \(t(i)\) is no greater than \(T\). We define \[\begin{align} T_0 = 0, \quad T_{n+1} = t(m(T_n+T) + 1) . \end{align}\] Intuitively, \(T_{n+1}\) is a little to the right of \(T_n + T\) on the real axis. As \(n\) grows large, the interval \([T_n, T_{n+1})\) contains more time steps as \(\alpha(i)\) is decreasing to \(0\).

4.2 Defining the Scaled Iterates↩︎

We start by fixing a sample path \(\require{physics} \qty{x_0,y_0,\qty{W_i}_{i=1}^\infty}\). We take \(\bar{z}(t)\) to be the piecewise constant interpolation of \(z_n\) at points \(\require{physics} \qty{t(n)}_{n=0,1,\dots}\), i.e., \[\begin{align} \bar z(t) \doteq (\bar{x}(t),\bar y(t)) \doteq \begin{cases} (x_0, y_0) & t \in [0,t(1)) \\ (x_1, y_1) & t \in [t(1),t(2)) \\ (x_2, y_2) & t \in [t(2),t(3)) \\ \ldots & \end{cases} \end{align}\]

Now we describe our rescaling of \(\bar z(t)\).

Definition 1 (Fast Timescale Rescaling). \(\forall n \in \mathbb{N}, t \in [0,T+1)\), define \[\require{physics} \begin{align} r_n &\doteq \max\qty{1, r_{n-1}, \norm{\bar{z}(T_n)}}, r_0 \doteq \max \qty{1, \norm{\bar{z}(0)}}, \\ \tilde{z}_n(t) &\doteq (\tilde{x}_n(t), \tilde{y}_n(t)) \doteq \frac{\bar{z}(T_n + t)}{r_n}. \end{align}\]

This implies \[\begin{align} \forall n \in \mathbb{N}, \norm{\tilde{z}_n(0) } \leq 1. \end{align}\]

Through the definition, we ensure that the sequence \(\require{physics} \qty{r_n}\) is monotonic, forcing the (to be defined) ODE discretization error to diminish over the entire sequence rather than just a subsequence, which is necessary in the two-time scale case.

We can regard \(\tilde{z}_n(t)\) as the Euler discretization of \(z_n(t)\) defined below.

Definition 2. \(\forall n \in \mathbb{N}, t\in [0,T+1)\), define \(z_n(t) = (x_n(t), y_n(t))\) as the solution to the ODE system \[\begin{align} \frac{d x_n(t)}{d t} = h_{r_n}(x_n(t), y_n(t)), \quad \frac{d y_n(t)}{d t} = 0 \end{align}\] with initial condition \(z_n(0) = \tilde{z}_n(0).\)

We want to show that the error of the discretization diminishes asymptotically. Precisely speaking, the discretization error is defined as \(f_n(t) \doteq \tilde{z}_n(t) - z_n(t)\), and we want to show that \(f_n(t)\) diminishes to 0 uniformly in \(t\) as \(n\to\infty\). So, we analyze the following three sequences of functions: \[\require{physics} \begin{align} \label{eq32three32seq32main32text} \qty{\tilde{z}_n(t)}_{n=0}^\infty, \qty{z_n(t)}_{n=0}^\infty, \qty{f_n(t)}_{n=0}^\infty. \end{align}\tag{6}\] In particular, we show that they are all equicontinuous in the extended sense, as this is required to apply the Arzelà-Ascoli theorem (Appendix 8). We defer the relevant definitions, statements, and proofs to the Appendix.

4.3 Selecting a Convergent Subsequence↩︎

To prove stability, we need to show that \(\sup_n \norm{z_n} < \infty.\) Observe the inequality \(\norm{z_{m(T_n)}} = \norm{\bar{z}(T_n)} \leq r_n.\) Therefore, if we had \(\sup_n r_n < \infty\), the result would come instantly. So, we assume that \(\sup_n r_n = \infty\) to show that Lemma 1 holds even in this case. According to the Arzelà-Ascoli theorem in the extended sense (Appendix 8), a sequence of equicontinuous functions always has a subsequence of functions that uniformly converges to a continuous limit. We use this to identify a subsequence of interest.

Lemma 2. Suppose \(\sup_n r_n = \infty\). Take an arbitrary subsequence \(\require{physics} \qty{n_{k,0}}_{k=0}^\infty \subseteq \qty{0, 1, 2, \dots}\). Then there is a subsequence \(\require{physics} \qty{n_k}_{k=0}^\infty \subseteq \qty{n_{k,0}}_{k=0}^\infty\) such that there exist some continuous functions \(f^{\lim}(t)\) and \(\tilde{z}^{\lim}(t)\) such that \(\forall t \in [0, T+1)\), \[\begin{align} \lim_{k \to \infty} f_{n_k}(t) = f^{\lim}(t), \quad \lim_{k \to \infty} \tilde{z}_{n_k}(t) =& \tilde{z}^{\lim}(t), \end{align}\] where both convergences are uniform in \(t\) on \([0, T+1)\). Furthermore, let \(z^{\lim}(t) = (x^{\lim}(t),y^{\lim}(t))\) denote the unique solution to the ODE system \[\begin{align} \frac{d x^{\lim}(t)}{d t} &= h_{\infty}(x^{\lim}(t), y^{\lim}(t)), \quad \frac{d y^{\lim}(t)}{d t} = 0 \end{align}\] with the initial condition \(z^{\lim}(0) = \tilde{z}_n^{\lim}(0).\) Then \(\forall t \in [0, T+1)\), we have \[\begin{align} \lim_{k \to \infty} z_{n_k}(t) = z^{\lim}(t), \end{align}\] where the convergence is uniform in \(t\) on \([0, T+1)\).

Its proof is in Appendix 16.4. We will use the subsequence \(\require{physics} \qty{n_k}\) intensively.

4.4 Diminishing Discretization Error↩︎

We show that \(\lim_{n \to \infty} \norm{f_n(t)} = 0\) for all \(t \in [0, T+1)\). We start by first proving that the discretization error diminishes along the sequence \(\require{physics} \qty{n_k}\), i.e., that \[\begin{align} \lim_{k \rightarrow \infty} \norm{f_{n_k}(t)} = \norm{f^{\lim}(t)} = 0. \end{align}\] This means \(\tilde{z}_{n_k}(t)\) is close to \(z_{n_k}(t)\) as \(k \rightarrow \infty\). From Lemma 46, we have \(\lim_{k \to \infty} \norm{f_{n_k}(t)} = 0\) uniformly in \(t\) on \([0, T+1)\), so the discretization error goes to 0 on \(\require{physics} \qty{n_k}\).

Because we are working with a two-timescale scheme, convergence to 0 along a subsequence will not be sufficient. As we defined \(r_n\) to be monotonic, this enabled us to chose an arbitrary subsequence \(\require{physics} \qty{f_{n_{k,0}}}\) which itself had a subsequence \(\require{physics} \qty{f_{n_k}}\) that converges to \(0\). We can now use Lemma 10 to upgrade to full sequence convergence, confirming that \(\require{physics} \qty{f_n}\) also converges to \(0\). Thus, the discretization error diminishes along the entire sequence. That is, \[\begin{align} \lim_{k \to \infty} \norm{f_n(t)} = 0 \end{align}\] for all \(t \in [0, T+1)\).

4.5 ODEs with External Inputs.↩︎

In the previous section, we showed that the discrete iterates generated by the two-timescale stochastic algorithm approximate the deterministic trajectories of certain ODEs. We now need to show that these trajectories of the ODEs exhibit certain behavior, including approaching their equilibria.

We present some notation concerning ODEs with external inputs. This is useful since, in the limit, we can treat the slow iterates as constant external inputs.

Definition 3 (ODE Trajectory Notation). We use the notation \(\eta^{y(t)}_{c}(t,x)\) to denote the solution of the ODE \[\begin{align} \dv{x(t)}{t} = h_c(x(t), y(t)) \end{align}\]

with the initial condition \(x\). Under this notation, \(x_n(t)\) can be written \(\eta_{r_n}^{\tilde{y}_n(0)}(t, \tilde{x}_n(0))\).

The following lemma shows that within a certain amount of time, the trajectory of the ODE will be pulled close to the equilibrium determined by the external input.

Lemma 3 (Lemma 1 from Chapter 3.2 of [4]). Let \(K \subset \mathbb{R}^{d_1}\) be compact and fix \(y \in \mathbb{R}^{d_2}\). Given any \(\epsilon > 0\), there exists a \(T_{\epsilon} > 0\) such that for all initial conditions \(x \in K\), we have \(\eta^y_{\infty}(t,x) \in B(\lambda_{\infty}(y), \epsilon)\)1 for all \(t \geq T_{\epsilon}\).

The next lemma shows that if the external input is close to some constant \(y\), then the trajectory remains close to the trajectory we would obtain if \(y\) were the external input.

Lemma 4 (Lemma 2 from Chapter 3.2 of [4]). Let \(y \in \mathbb{R}^{d_2}, [0, T]\) be a given time interval, and \(\rho\) be a small positive constant with \(y'(t) \in B(y, \rho)\). Then, \[\begin{align} \norm{\eta^{y'(t)}_{c}(t,x) - \eta^{y}_{\infty}(t,x)} \leq& (L\rho + \epsilon(c))Te^{LT}. \end{align}\] for any initial \(x \in \mathbb{R}^{d_1}\) and for all \(t \in [0, T]\).

4.6 Completing the Proof.↩︎

The most involved result left is Lemma 5, which tells us that if the \(x\) component is too much larger than the \(y\) component, the norm of the iterate at \(T_{n+1}\) cannot be larger than that of the iterate at \(T_n\). We use the results about ODEs with external inputs to ensure that the \(x\) component of the trajectory gets pulled to the equilibrium, which is close to \(0\).

Lemma 5 (Limiting Growth of \(\norm{\bar{z}(T_n)}\)). There exists a \(C_1 > 1\) such that if \(\norm{\bar{x}(T_n)} > C_1(1+\norm{\bar{y}(T_n)})\), then \(\norm{\bar{z}(T_{n+1})} \leq \norm{\bar{z}(T_n)}\). Consequently, \(r_{n+1} = r_n\).

Lemma 6 tells us that the iterate at each \(T_n\) is bounded by the largest \(y\) component seen so far in the sequence of times \(T_n\). To do this, we use an inductive argument. Intuitively, we combine the previous lemma, which prevents \(z\) from growing if the \(x\) component is too much larger than the \(y\) component, with Lemma 61 which prevents \(z\) from growing too much within one period \(T\), ensuring that \(x\) can never get too much larger than \(y\).

Lemma 6 (Boundedness of \(\norm{\bar{z}(T_n)}\)). There exists a constant \(C_2\) such that for all \(n\), \[\begin{align} \norm{\bar{z}(T_n)} \leq C_1C_2(\max_{m\leq n} \norm{\bar{y}(T_m)}+1). \end{align}\]

Finally, while we have ensured that for all \(T_n\), \(\bar{z}(T_n)\) is not too much larger than \(\bar{y}(T_n)\), we need the result to also hold for the iterates that lie in between \(T_n\) and \(T_{n+1}\). Lemma 7 takes care of this.

Lemma 7 (Boundedness of \(\norm{x_n}\)). There exists a constant \(C_3\) such that for all \(n\), \[\begin{align} \norm{x_n} \leq C_1C_2C_3(\norm{y^{\text{max}}_n} + 1), \end{align}\]

By setting \(K\) equal to \(C_1C_2C_3\), this concludes the proof of Lemma 1.

Connecting the Timescales.

We present the following result, showing that eventually, in the fast timescale, the fast iterates will track the equilibria \(\lambda_{\infty}(\tilde{y}_n(t))\). In the fast timescale analysis, the slow iterates were regulated by the fact that the slow step sizes are small. However, in the slow timescale analysis, the fast step sizes can grow large. This result regulates the behavior of the fast iterates.

Lemma 8. For any \(\epsilon > 0\), there is some \(T_{\epsilon}\) and some \(N_{\epsilon}\) such that for all \(n > N_{\epsilon}\), \(\norm{\tilde{x}_n(t) - \lambda_{\infty}(\tilde{y}_n(t))} \leq \epsilon\) for all \(t \in [0, T_{\epsilon}]\).

5 Stability of the Two-Timescale Iterates↩︎

We give the proof of Theorem 1, restated below:

Theorem 1 (1 Restated). The iterates \(\require{physics} \qty{z_n}\) are stable, i.e., \[\begin{align} \sup_n \norm{z_n} < \infty \quad a.s. \end{align}\]

We now conduct analysis in the slow timescale, but the structure is very similar to the fast timescale analysis, so we only highlight the key differences. Note that we are still working with the same sample path \(\require{physics} \qty{x_0,y_0, \qty{W_i}_{i=1}^\infty}\) from the last section.

We again split the positive real axis \([0, \infty)\), but this time into chunks of length \(\require{physics} \qty{\beta(i)}_{i=0,1,\dots}\) instead of \(\require{physics} \qty{\alpha(i)}_{i=0,1,\dots}\). We then redefine the scaled iterates for the slow timescale. This time the scaling factor is defined differently, so that it will be at least as large as the largest iterate seen so far:

Definition 4 (Slow Timescale Rescaling). \[\require{physics} \begin{align} r_n \doteq \max\qty{1, \norm{z^{max}_{m(T_n)}}} \label{def:32slow32r32n32main32text} \end{align}\tag{7}\] where \(z^{max}_n \doteq z_m\) such that \(m = \arg\max_{i \leq n} \norm{z_i}\) (with ties broken arbitrarily).

Defining the scaling factor this way in the slow timescale is an innovation. It ensures that at each time \(T_n\), the iterate, when scaled by the slow timescale’s \(\require{physics} \qty{r_n}\) values, is no larger than when scaled by the appropriate fast timescale’s \(\require{physics} \qty{r_n}\) values. We need this to link the timescales in Lemma 9.

We can regard \(\tilde{y}_n(t)\) as the Euler’s discretization of \(y_n(t)\) defined below.

Definition 5. \(\forall n \in \mathbb{N}, t\in [0,T+1)\), define \(y_n(t)\) as the solution to the ODE \[\begin{align} \frac{d y_n(t)}{d t} = g_{r_n}(\lambda_{\infty}(y_n(t)), y_n(t)) \label{eq:32slow32y32n32main32text} \end{align}\tag{8}\] with initial condition \(y_n(0) = \tilde{y}_n(0).\)

The discretization error is then defined as \(f_n(t) \doteq \tilde{y}_n(t) - y_n(t)\); just considering the slow component. Again, we show equicontinuity (here Lemma 1 plays a big role in controlling the growth of the fast iterates) and apply Arzelà-Ascoli to obtain a convergent subsequence.

To show that the discretization error diminishes, we must prove an involved result. It requires us to work in both timescales to show that although the iterates get rescaled less often in the slow timescale, they still do not grow too much faster than the iterates in the fast timescale. So, we show that even in the slow timescale, the fast timescale iterates converge to the equilibria dependent on the slow timescale iterates, formalizing the intuition that in the slow timescale, we can consider the fast iterates to have converged:

Lemma 9 (Fast Iterates Approach Equilibrium). For all \(\epsilon > 0\), there exists some \(N\) such that for all \(n > N\), \[\begin{align} \norm{\tilde{x}_n(t) - \lambda_{\infty}(\tilde{y}_n(t))} < \epsilon \end{align}\] for all \(t \in [0, T]\).

We can now deal with the error term 93 unique to the slow timescale, and show the discretization error decreases to zero 95 . We then obtain ODE results similar to single-timescale stability results (Chapter 3 of [4]). As the limiting ODE is attracted to its globally asymptotically stable equilibrium, 0, our iterates cannot grow without bound. Thus, the sequence \(r_n\) is bounded, creating a contradiction. We conclude that Theorem 1 holds true.

6 Convergence of the Two-Timescale Iterates↩︎

We discuss the proof of Theorem 2, restated below:

Theorem 2 (2 Restated). Let Assumptions 1 - 6 hold. Then the iterates \(\require{physics} \qty{x_n}\) generated by 1 converge almost surely to the equilibrium depending on \(\require{physics} \qty{y_n}\) as follows: \[\begin{align} \lim_{n \rightarrow \infty} \norm{x_n - \lambda(y_n)} = 0 \end{align}\] where \(\lambda: \mathbb{R}^{d_2} \rightarrow \mathbb{R}^{d_1}\) is a Lipschitz map and \(\lambda(y)\) is the globally asymptotically stable equilibrium of \(\dv{x(t)}{t} = h(x(t), y)\). With this convergence established, we can then establish the main two-timescale convergence result: \[\begin{align} \lim_{n \rightarrow \infty} \norm{z_n - (\lambda(y^*), y^*)} = 0. \end{align}\]

The proof mirrors the stability proof but is simpler. We first show a convergence result in the fast timescale. Namely, we show that the fast iterates \(x_n\) converge to \(\lambda(y_n)\). Then, we obtain the full convergence result through analysis in the slow timescale. The difference is that we no longer need to use rescaling, since we know that the iterates are bounded by Theorem 1, and we now prove results on \(t \in (-\infty, \infty)\) as this simplifies showing convergence to an invariant set.

First, we show that the discretization error between \(\require{physics} \qty{z_n}\) and the ODE system \[\begin{align} \dv{x(t)}{t} = h(x(t), y(t)), \quad \dv{y(t)}{t} = 0 \label{cor32eq32original32ode32system32main32text} \end{align}\tag{9}\] diminishes in the fast timescale. Then, due to Theorem 1, we argue that since the set of limit points \(Z\) of \(\require{physics} \qty{z_n}\) is bounded and nonempty, it is an invariant set of 9 . We then show that no subsequence of \(\require{physics} \qty{z_n}\) converges to a point not in \(Z\), confirming that \(\require{physics} \qty{z_n}\) converges to \(Z\). Since the invariant set of 9 is \(\require{physics} \qty{(\lambda(y), y): y \in \mathbb{R}^{d_2}}\), we have \[\begin{align} \lim_{n \rightarrow \infty} \norm{x_n - \lambda(y_n)} = 0. \end{align}\] We then pursue the slow timescale argument and show that \(\require{physics} \qty{y_n}\) converges to the invariant set of the ODE \[\begin{align} \label{cor32eq32g32ode32main32text} \dv{y(t)}{t} &= g(\lambda(y(t)), y(t)) \end{align}\tag{10}\] which is the singleton set containing \(y^*\), the equilibrium of the ODE. This, combined with the fast timescale convergence result, yields our desired result: \[\begin{align} \lim_{n \rightarrow \infty} \norm{z_n - (\lambda(y^*), y^*)} = 0. \end{align}\]

7 Applications in Reinforcement Learning↩︎

In this section, we give some context on RL and prove the convergence of an important off-policy RL algorithm, TDC(\(\lambda\)), using our main results (Section 3).

We consider a Markov Decision Process (MDP) with state space \(S\), action space \(A\), reward function \(r: S \times A \rightarrow \mathbb{R}\), transition function \(p: S \times S \times A \rightarrow [0,1]\), and discount factor \(\gamma \in [0, 1)\). At time \(t\), an agent with a control policy \(\pi: S \times A \rightarrow [0,1]\) will, given the current state \(S_t\), sample an action \(A_t \sim \pi(\cdot|S_t)\). Upon taking action \(A_t\), the environment yields the reward \(R_t \doteq r(S_t, A_t)\) to the agent and transitions to the next state \(S_t \sim p(\cdot | S_t,A_t)\). We define the return at time \(t\) as \(G_t \doteq \sum_{i=t}^{\infty} \gamma ^{i-1}R_t\). Based on this, we can define the value function \(v_{\pi}(s) \doteq \mathbb{E}_{\pi,p}[G_t|S_t=s]\). Since the state space \(S\) could be quite large, we wish to approximate \(v_{\pi}(s)\) using a vector of parameters \(\theta \in \mathbb{R}^K\) where \(K \ll |S|\). Specifically, we define \(v_{\theta,\pi}(s) \doteq \phi(s)^\top \theta \approx v_{\pi}(s)\), where \(\phi: S \rightarrow \mathbb{R}^K\) is the function which extracts the features from the state \(s\).

The task of computing or approximating \(v_{\pi}(s)\) is called policy evaluation, and it is one of the most important problems in RL. Temporal Difference (TD) learning methods [6] have been the most effective at this task. They operate through bootstrapping, the practice of updating estimates using other estimates. In the case of TD methods, they update the estimated value of a current state using the estimated value of sampled future states.

Another important technique is off-policy learning, where we estimate the value of a target policy \(\pi\) by using data from a behavior policy \(\mu\). This has many advantages as it enables us to run many policies in parallel and train offline, improve data-efficiency [27][30], and enforce safety by using a safe behavior policy to evaluate a riskier target policy [31], [32].

Unfortunately, when combining bootstrapping and off-policy learning with function approximation (necessary in large state spaces), naive TD methods can diverge. This pitfall is called the deadly triad [8], [33]. Gradient temporal difference learning (GTD) was developed to break the deadly triad [34]. While convergent, it is slow. Temporal Difference learning with gradient correction (TDC) was first proposed in [17] as a modification of GTD that is nearly as fast as standard TD but still convergent. In addition to having the parameter vector \(\theta\) for the linear approximation of the value function, it has a second parameter vector \(\nu\) to estimate one of the expectations in the algorithm. TDC is a two-timescale algorithm as the updates to \(\nu\) run on a faster timescale, which empirically leads to faster convergence of the algorithm. In this work, we study TDC(\(\lambda\)), i.e., TDC with eligibility traces. Eligibility traces are a powerful tool for credit assignment, a critical challenge in RL, and have been a fundamental part of RL since the inception of the field [35]. Although eligibility traces empirically speed up convergence [8], they can introduce difficulties in analysis.

Definition 6 (TDC(\(\lambda\))). \[\begin{align} \label{eq32gtd32main32text} e_t =& \lambda \gamma \rho_{t-1} e_{t-1} + \phi_t, \\ \delta_t =& R_{t+1} + \gamma \phi_{t+1}^\top \theta_t - \phi_t^\top \theta_t, \\ \nu_{t+1} =& \nu_t + \alpha_t \left(\rho_t \delta_t e_t - \phi_t \phi_t^\top \nu_t\right), \\ \theta_{t+1} =& \theta_t + \beta_t(\rho_t \delta_t e_t - \rho_t(1-\lambda)\gamma \phi_{t+1} e_t^\top \nu_t). \end{align}\tag{11}\]

The eligibility trace \(e_t\) is an exponential average of the features \(\phi_t \doteq \phi(S_t)\) (weighted by importance sampling ratio \(\rho_t\), which is necessary in off-policy learning). \(\delta_t\) is the TD error. \(\theta_t\) and \(\nu_t\) parametrize the approximations of the value function and of the gradient correction respectively. The version of TDC(\(\lambda\)) we study in Definition 11 is referred to as GTDb in [18].

Theorem 3. Take the assumptions in Appendix 15. Then, by applying Theorem 2, TDC with eligibility traces converges almost surely.

Remark 4. One can apply Theorem 2 similarly to show that two-timescale GTD with eligibility traces (GTDa in [18]) also converges.

The assumptions are not very strong. We assume the state space \(S\) and the action space \(A\) are finite, the Markov chain \(\require{physics} \qty{S_t}\) is irreducible, and that from any state, all possible actions have a positive probability of being chosen (as this is an off-policy algorithm, this ensures coverage of the target policy we are estimating the value of). These assumptions are well-established in the literature [13], [18]. From this, it is easy to verify that TDC(\(\lambda\)) satisfies all assumptions in Appendix 11, so Theorem 2 applies. Applying Theorem 2, we confirm that TDC with eligibility traces converges (see Appendix 15 for the detailed proof).

8 Related Work↩︎

This work is primarily concerned with the almost sure convergence of two-timescale SA in an asymptotic sense without a rate. For single-timescale SA, almost sure convergence rates are also established for specific algorithms such as \(Q\)-learning [36], linear \(Q\)-learning [37], and linear TD [38], for linear SA [39][41], and for general SA under various noise conditions [42][44]. The most general ones are [45], [46], which establish almost sure convergence rates for general contractive SA under Markovian noise. Extending these results to two-timescale SA is a direction for future work. The asymptotic almost sure convergence of general contractive single-timescale Markovian SA is also recently formally verified in Lean by [47]. Extending this formal verification framework to two-timescale SA is also a direction for future work.

In addition to almost sure convergence, there are many other modes of convergence, e.g., \(L^2\) convergence. The \(L^2\) convergence rates of two-timescale SA are established under various noise and algorithmic conditions [23], [48], [49]. One particularly relevant work is [50]. The main result of [50] is an \(L^2\) convergence rate for two-timescale Markovian SA. But [50] also have a claim about the almost sure convergence of two-timescale Markovian SA, exactly overlapping with our main result. We believe that their claim about almost sure convergence does not hold. Particularly, their proof of almost sure convergence relies crucially on their claim that if the iterates are bounded in expectation, then they are bounded almost surely (i.e., \(\require{physics} \sup_n \mathbb{E}\qty[\norm{x_n}^2] < \infty \implies \sup_n \norm{x_n} < \infty\) a.s.), which is false. A counterexample (e.g., \(x_n = \sqrt{n}\) with probability \(1/n\) and \(0\) otherwise) can be easily constructed by the second Borel-Cantelli lemma.

TDC(\(\lambda\)) is one representative two-timescale RL algorithm. Other two-timescale RL algorithms include actor-critic algorithms [9], [51][53], average-reward gradient TD algorithms [54], and TD with target networks [55]. Investigating whether our results can be applied to these algorithms is a possible future work. Many previous convergence analyses of TDC do not handle eligibility traces [34], [56], i.e., they set \(\lambda = 0\). The only prior work that handles eligibility traces properly for TDC is [18], which, however, only analyzes projected variants of TDC. The fundamental reason is that even if the state space of the Markov chain \(\require{physics} \qty{(S_t, A_t)}\) is finite, with eligibility traces, we must instead consider the chain \(\require{physics} \qty{(S_t, A_t, e_t)}\), which now evolves in an uncountable space. Even worse, off-policy learning makes the trace \(e_t\) unbounded as well, as the product of the importance sampling ratio can be unbounded. Prior works resort to additional projection [18], [57] or truncation [58] to handle the unboundedness of the eligibility traces. This work instead directly handles the unboundedness via averaging following the techniques in [3], [13].

9 Conclusion↩︎

This work establishes the first almost sure convergence results for general two-timescale Markovian SA under mild assumptions. This work can be viewed as a combination of [11] and [13], both of which are extensions of the seminal work [19]. Key to our analysis is a methodological innovation that bounds the faster iterates with the running max of the slower iterates. On the other hand, [19] are recently extended by [16] to include not only Markovian noise but also (functional) central limit theorems. A fruitful direction for future work is thus to investigate whether our methodological innovation can be applied to extend the (functional) central limit theorems of [16] to two-timescale SA.

Acknowledgements↩︎

This work is supported in part by the US National Science Foundation under the awards III-2128019, SLES-2331904, and CAREER-2442098, the Commonwealth Cyber Initiative’s Central Virginia Node under the award VV-1Q26-001, and a Cisco Faculty Research Award. Additionally, we thank the reviewers whose comments and suggestions improved the quality of our work.

Impact Statement↩︎

This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.

10 Mathematical Background↩︎

Theorem 5 (Gronwall Inequality). (Lemma 6 in Section 11.2 in [4])For a continuous function \(u(\cdot) \geq 0\) and scalars \(C,K,T \geq 0\), \[\begin{align} u(t) \leq C+K\int_0^t u(s) ds \quad \forall t \in [0,T] \end{align}\] implies \[\begin{align} u(t) \leq Ce^{tK}, \forall t \in [0,T]. \end{align}\]

Theorem 6 (Gronwall Inequality in the Reverse Time).

For a continuous function \(u(\cdot) \geq 0\) and scalars \(C,K,T \geq 0\), \[\begin{align} u(t) \leq C + K\int_t^0 u(s) ds \quad \forall t \in [-T,0] \label{eq:32reverse32Gronwall32condtion} \end{align}\tag{12}\] implies \[\begin{align} u(t) \leq Ce^{-tK}, \forall t \in [-T,0]. \end{align}\]

For a proof, see Appendix A.2 of [13].

Theorem 7 (Discrete Gronwall Inequality). (Lemma 8 in Section 11.2 in [4])For nonnegative sequences \(\require{physics} \qty{x_n,n\geq 0}\) and \(\require{physics} \qty{a_n, n\geq 0}\) and scalars \(C,L \geq 0\), \[\begin{align} x_{n+1} \leq C + L\sum_{i=0}^n a_i x_i \quad \forall n \end{align}\] implies \[\begin{align} x_{n+1} \leq Ce^{L\sum_{i=0}^n a_i } \quad \forall n. \end{align}\]

Theorem 8 (The Arzelà-Ascoli Theorem in the Extended Sense on \([0,T)\)).

Let \(\require{physics} \qty{t \in [0, T) \mapsto g_n(t)}\) be equicontinuous in the extended sense. Then, there exists a subsequence \(\require{physics} \qty{g_{n_k}(t)}\) that converges to some continuous limit \(g^{\lim}(t)\), uniformly in \(t\) on \([0, T)\).

For a proof, see Appendix A.4 of [13].

Theorem 9 (Moore-Osgood Theorem for Interchanging Limits). If \(\lim_{n\to \infty} a_{n,m} = b_m\) uniformly in \(m\) and \(\lim_{m\to \infty} a_{n,m} = c_n\) for each large \(n\), then both \(\lim_{m \to \infty}b_m\) and \(\lim_{n\to\infty}c_n\) exists and are equal to the double limit, i.e., \[\begin{align} \lim_{m\to\infty} \lim_{n\to \infty} a_{n,m} = \lim_{n\to \infty} \lim_{m\to \infty} a_{n,m} = \lim \limits_{\begin{subarray}{l} n \to \infty\\ m \to \infty \end{subarray}} a_{n,m}. \end{align}\]

Lemma 10 (Sub-subsequence Lemma). Let \(x_n\) be a sequence in some metric space. If every subsequence \(x_{n_k}\) itself has a subsequence \(x_{n_{k_j}}\) that converges to the same limit \(x\), then \(x_n\) converges to \(x\).

Proof. Suppose we have a sequence \(x_n\) where every subsequence \(x_{n_k}\) itself has a subsequence \(x_{n_{k_j}}\) that converges to the same limit \(x\). For contradiction, assume that \(x_n\) does not converge to \(x\), so there is a subsequence \(x_{n_{k,0}}\) that is always at least some distance \(\epsilon\) away from \(x\). By assumption, \(x_{n_{k,0}}\) has a subsequence \(x_{n_{k,1}}\) that converges to \(x\), which contradicts that \(x_{n_{k,0}}\) is always at least some \(\epsilon\) away from \(x\). So, it must be that \(x_n\) converges to \(x\). ◻

11 Main Assumptions↩︎

Assumption 1. The Markov chain \(\require{physics} \qty{W_n}\) has a unique invariant probability measure (i.e., stationary distribution), denoted by \({d_\mathcal{W}}\).

Although the uniqueness and even the existence of the invariant probability measure can be relaxed, we use Assumption 1 for simplification. Additionally, due to the way updates are defined (1 and 2 ), we start counting \(\require{physics} \qty{W_n}\) from \(n = 1\).

Assumption 2. The learning rates \(\require{physics} \qty{\alpha(i)}\), \(\require{physics} \qty{\beta(i)}\) are positive, decreasing, and satisfy \[\begin{align} \tag{13} \sum_{i=0}^{\infty} \alpha(i) = \sum_{i=0}^{\infty} \beta(i) &= \infty, \\ \tag{14} \lim_{i \to \infty} \alpha(i) = \lim_{i \to \infty} \beta(i) &= 0 \\ \tag{15} \frac{\alpha(i)- \alpha(i+1)}{\alpha(i)} =& \mathcal{O}\left(\alpha(i)\right), \\ \tag{16} \frac{\beta(i)- \beta(i+1)}{\beta(i)} =& \mathcal{O}\left(\beta(i)\right), \\ \tag{17} \lim_{i \rightarrow \infty} \frac{\beta(i)}{\alpha(i)} = 0. \end{align}\]

These conditions on the learning rates are quite common in stochastic approximation. The last condition is necessary for the two-timescale formulation we are using.

Remark 10. For any \(\alpha(n) = \frac{B_1}{(n+B_2)^{\gamma_{\alpha}}}, \beta(n) = \frac{B_3}{(n+B_4)^{\gamma_{\beta}}}\) with \(\gamma_{\alpha}, \gamma_{\beta} \in (0.5, 1], \gamma_{\beta} > \gamma_{\alpha}\), and all \(B_i\) positive, one can verify that all the conditions in Assumption \(\ref{assumption:32learning32ratios}\) are satisfied.

Now, we make assumptions about the functions \(H\) and \(G\). For any \(c \in [1, \infty)\), define \[\begin{align} H_c(x, y, w) &\doteq \frac{H(cx, cy, w)}{c} \tag{18} \\ G_c(x, y, w) &\doteq \frac{G(cx, cy, w)}{c} \tag{19}. \end{align}\]

The functions \(H_c\) and \(G_c\) are rescaled versions of the functions \(H\) and \(G\) and will be used to construct rescaled iterates, a key technique in the ODE method (see, e.g., [4], [13], [19]). Just as in those works, we need the existence of some sort of limiting functions for \(H_c\) and \(G_c\) when \(c \to \infty\).

Assumption 3.

There exist measurable functions \(H_{\infty}(x,y,w)\) and \(G_{\infty}(x,y,w)\), functions \(\kappa_H(c), \kappa_G(c): \mathbb{R}\rightarrow \mathbb{R}\), and measurable functions \(b_H(x,y,w), b_G(x,y,w)\) such that for all \(x,y,w\) \[\begin{align} H_c(x,y,w)-H_{\infty}(x,y,w) &= \kappa_H(c)b_H(x,y,w) \tag{20} \\ G_c(x,y,w)-G_{\infty}(x,y,w) &= \kappa_G(c)b_G(x,y,w) \tag{21} \\ \lim_{c\rightarrow \infty} \kappa_H(c) &= \lim_{c \rightarrow \infty} \kappa_G(c) = 0 \tag{22} \end{align}\] There also exists a measurable function \(L_b(w)\) such that for all \(x, x', y, y', w\) \[\begin{align} \norm{b_H(x,y,w) - b_H(x',y',w)} &\leq L_b(w)\norm{(x,y)-(x',y')}, \tag{23} \\ \norm{b_G(x,y,w) - b_G(x',y',w)} &\leq L_b(w)\norm{(x,y)-(x',y')}. \tag{24} \end{align}\] Additionally, the expectation \(L_b \doteq \mathbb{E}_{w \sim d_\mathcal{W}} [L_b(w)]\) is well-defined and finite.

Assumption 3 provides details on how \(H_c\) and \(G_c\) converge to \(H_\infty\) and \(G_\infty\) when \(c \to \infty\).

We now assume that the functions \(H_c\) and \(G_c\) are Lipschitz. This will guarantee that the corresponding ODEs exist and are unique.

Assumption 4. There exists a measurable function \(L(w)\) such that for any \(x,x',y,y',w\), \[\begin{align} \norm{H(x,y,w) - H(x',y',w)} &\leq L(w) \norm{(x,y) - (x',y')}, \tag{25}\\ \norm{H_\infty(x,y,w) - H_\infty(x',y',w)} &\leq L(w) \norm{(x,y) - (x',y')}, \tag{26} \\ \norm{G(x,y,w) - G(x',y',w)} &\leq L(w) \norm{(x,y) - (x',y')}, \tag{27}\\ \norm{G_\infty(x,y,w) - G_\infty(x',y',w)} &\leq L(w) \norm{(x,y) - (x',y')}. \tag{28} \end{align}\] Moreover, the following expectations are well-defined and finite for any \(x, y\): \[\begin{align} h(x,y) &\doteq \mathbb{E}_{w\sim d_\mathcal{W}}[H(x,y,w)], \tag{29} \\ h_\infty(x,y) &\doteq \mathbb{E}_{w \sim d_\mathcal{W}}[H_{\infty}(x,y,w)], \\ g(x,y) &\doteq \mathbb{E}_{w\sim d_\mathcal{W}}[G(x,y,w)], \tag{30} \\ g_\infty(x,y) &\doteq \mathbb{E}_{w \sim d_\mathcal{W}}[G_{\infty}(x,y,w)], \\ L &\doteq \mathbb{E}_{w \sim d_\mathcal{W}}[L(w)]. \end{align}\]

The functions \(x,y \mapsto H_c(x, y, w)\) and \(x,y \mapsto G_c(x, y, w)\) share the same Lipschitz constant \(L(w)\) as the functions \(x,y \mapsto H(x, y, w)\) and \(x,y \mapsto G(x, y, w)\). Similarly to 18 and 19 , we define \[\begin{align} \tag{31} h_c(x, y) &\doteq \frac{h(cx, cy)}{c}, \\ \tag{32}g_c(x, y) &\doteq \frac{g(cx, cy)}{c}. \end{align}\]

The following assumption is necessary to ensure that the rescaled iterates can converge to the trajectory of the limiting ODE.

Assumption 5. The ODE \[\begin{align} \frac{dx(t)}{dt} = h(x(t), y) \end{align}\] has a unique globally asymptotically stable equilibrium \(\lambda(y)\) where \(\lambda: \mathbb{R}^{d_2} \rightarrow \mathbb{R}^{d_1}\) is a Lipschitz map. Additionally, we assume that the ODE \[\begin{align} \frac{dy(t)}{dt} = g(\lambda(y(t)), y(t)) \end{align}\] has a unique globally asymptotically stable equilibrium.

As \(c \rightarrow \infty\), \(h_c(x,y)\) converges to \(h_{\infty}(x,y)\) uniformly in \((x,y)\) on any compact subsets of \(\mathbb{R}^{d_1+d_2}.\) The limiting ODE \[\begin{align} \frac{dx(t)}{dt} = h_{\infty}(x(t), y) \label{eq32h32ode32at32limit} \end{align}\tag{33}\] has a unique globally asymptotically stable equilibrium \(\lambda_{\infty}(y)\) where \(\lambda_{\infty}: \mathbb{R}^{d_2} \rightarrow \mathbb{R}^{d_1}\) is a Lipschitz map. \(\lambda_{\infty}\) is homogeneous, i.e., \(\lambda_{\infty}(cy) = c \lambda_{\infty} (y)\). And \(\lambda_{\infty}(0) = 0\).

As \(c \rightarrow \infty\), \(g_c(x, y)\) converges uniformly to \(g_{\infty}(x, y)\) on compact subsets of \(\mathbb{R}^{d_1+d_2}.\) The limiting ODE \[\begin{align} \frac{dy(t)}{dt} = g_{\infty}(\lambda_{\infty}(y(t)), y(t)) \label{eq32g32ode32at32limit} \end{align}\tag{34}\] has 0 as its unique globally asymptotically stable equilibrium.

The map \(\lambda_\infty\) tells us, for a particular external input \(y\), what \(x\) (the parameters of the inner loop) should converge to. This idea and the notation for it come from Chapter 6 of [4].

Assumption 6. Let \(\gamma\) denote any of the following functions: \[\begin{align} \label{eq32lln32all32g} w \mapsto& H(x, y, w) \quad (\forall x, y), \\ w \mapsto& G(x, y, w) \quad (\forall x, y), \\ w \mapsto& L_b(w), \\ w \mapsto& L(w). \end{align}\tag{35}\] We have, for any initial condition \(W_1\), \[\require{physics} \begin{align} \lim_{n\to\infty} \alpha(n) \sum_{i=1}^n \qty( \gamma(W_i) - \mathbb{E}_{w\sim d_\mathcal{W}}[\gamma(w)]) &= 0 \qq{a.s.} \\ \lim_{n\to\infty} \beta(n) \sum_{i=1}^n \qty( \gamma(W_i) - \mathbb{E}_{w\sim d_\mathcal{W}}[\gamma(w)]) &= 0 \qq{a.s.} \label{eq32stronger32lln} \end{align}\tag{36}\]

The assumption holds for all functions \(\gamma\) on the same probability-one set.

Remark 11. Once more, consider \(\beta(n) = \frac{B_1}{(n + B_2)^ {\gamma_{\beta}}}\) as an example. For \(\gamma_{\beta} = 1\), 36 is implied by the following Law of Large Numbers 37 \[\require{physics} \begin{align} \label{eq32lln32new} \lim_{n\to\infty} \frac{1}{n} \sum_{i=1}^n\qty( \gamma(W_i) - \mathbb{E}_{w\sim{d_\mathcal{W}}}\left[\gamma(w)\right]) = 0 \qq{a.s.} \end{align}\tag{37}\] For \(\gamma_{\beta} \in (0.5, 1]\), 36 is implied by the following Law of the Iterated Logarithm 38 \[\require{physics} \begin{align} \label{eq32lil} \norm{\sum_{i=1}^n\qty( \gamma(W_n) - \mathbb{E}_{w\sim{d_\mathcal{W}}}\left[\gamma(w)\right])} \leq \zeta \sqrt{n \log\log n} \qq{a.s.,} \end{align}\tag{38}\] where \(\zeta\) is a sample path dependent finite constant.

12 Proof of Lemma 1↩︎

This is a more detailed version of Section 4. In this section, we will prove Lemma 1. Section 12.1 sets up the notation and explains our fast timescale analysis. Section 12.2 defines the rescaled iterates and some important functions. Section 12.3 assumes for contradiction that stability does not hold and identifies a resulting subsequence of interest. Section 12.4 demonstrates convergence along this subsequence and uses this to show that the convergence holds for the entire sequence. Section 12.5 defines some notation and provides some results about ODEs with external inputs. Finally, Section 12.6 uses results from the previous sections to complete the proof. Lemmas in this section are derived on an arbitrary sample path \(\require{physics} \qty{x_0,y_0, \qty{W_i}_{i=1}^\infty}\) such that the assumptions in Appendix 11 hold. Thus, we omit “\(a.s.\)” from the lemma statements for conciseness.

12.1 Splitting up the Timeline↩︎

Here, we perform a fast timescale analysis. First, we split the positive real axis \([0, \infty)\) into chunks of length \(\require{physics} \qty{\alpha(i)}_{i=0,1,\dots}\). We then collect these segments together into larger intervals \(\require{physics} \qty{[T_n, T_{n+1})}_{n=0,1,\dots}\), where the sequence \(\require{physics} \qty{T_n}\) has the property that as \(n\) grows large, we have \(T_{n+1} - T_n \approx T\). We define \[\begin{align} t(0) \doteq& 0, \\ t(n) \doteq& \sum_{i=0}^{n-1} \alpha(i) \qq{n=1,2,\dots}. \end{align}\] For all \(T > 0\), define \[\require{physics} \begin{align} m(T) = \max\qty{{i | T \geq t(i)}} \label{def:32m} \end{align}\tag{39}\] to be the maximal \(i\) where \(t(i)\) is no greater than \(T\). To visualize, \(t(m(T))\) is a bit to the left of \(T\) on the real axis. So, \(t(m(T))\) satisfies the following: \[\begin{align} & t(m(T)) \leq T < t(m(T) + 1) = t(m(T)) + \alpha(m(T)) \tag{40}, \\ & t(m(T)) > T -\alpha(m(T))\tag{41}. \end{align}\] Define \[\begin{align} &T_0 = 0, \\ &T_{n+1} = t(m(T_n+T) + 1) \label{def:T}. \end{align}\tag{42}\] Intuitively, \(T_{n+1}\) is a little to the right of \(T_n + T\) on the real axis.

We define \[\begin{align} \alpha(i) = \beta(i) =& 0 \quad \forall i < 0, \tag{43} \\ m(t) =& 0 \quad \forall t \leq 0, \tag{44} \end{align}\] for simplifying notations. For any given function \(f\) with domain \(\mathcal{W}\), its asymptotic rate of change is defined as \[\require{physics} \begin{align} \limsup_n \sup_{-\tau \leq t_1 \leq t_2 \leq \tau} \norm{\sum_{i = m(t(n) + t_1)}^{m(t(n) + t_2) - 1} \alpha(i) [f(W_{i+1}) - \mathbb{E}_{w\sim d_\mathcal{W}}\qty[f(w)]] }. \end{align}\] This asymptotic rate of change helps us to describe the asymptotic regularity of \(\require{physics} \qty{f(W_n)}\) and we lean on its usefulness in studying stochastic approximation. We refer the reader to Sections 5.3.2 and 6.2 of [3] for a detailed exposition of this tool. In this work, we have deferred the contents concerning asymptotic rate of change to Appendices 16.1 and 16.2 since the statements and proofs are very similar to results in [13].

12.2 Defining the Scaled Iterates↩︎

We start by fixing a sample path \(\require{physics} \qty{x_0,y_0,\qty{W_i}_{i=1}^\infty}\). We will take \(\bar{z}(t)\) to be the piecewise constant interpolation2 of \(z_n\) at points \(\require{physics} \qty{t(n)}_{n=0,1,\dots}\), i.e.,

\[\begin{align} \bar z(t) \doteq (\bar{x}(t),\bar y(t)) \doteq \begin{cases} (x_0, y_0) & t \in [0,t(1)) \\ (x_1, y_1) & t \in [t(1),t(2)) \\ (x_2, y_2) & t \in [t(2),t(3)) \\ \vdots & \end{cases} \end{align}\] By 39 , we also have \[\begin{align} \label{def:32bar32z} \bar{z}(t) \doteq z_{m(t)}. \end{align}\tag{45}\]

By 1 , \(\forall n \geq 0\), we have \[\begin{align} &\bar{z}(t(n+1)) = \bar{z}(t(n)) + (\alpha(n)H(\bar{z}(t(n)) ,W_{n+1}), \beta(n)G(\bar{z}(t(n)) ,W_{n+1})). \end{align}\] Now we describe our rescaling of \(\bar z(t)\).

Definition 7. \(\forall n \in \mathbb{N}, t \in [0,T+1)\), define \[\begin{align} \tilde{z}_n(t) \doteq (\tilde{x}_n(t), \tilde{y}_n(t)) &\doteq \frac{\bar{z}(T_n + t)}{r_n} \end{align}\]

where \[\require{physics} \begin{align} r_n \doteq \max\qty{1, r_{n-1}, \norm{\bar{z}(T_n)}} \label{def:32r32n}, r_0 \doteq \max\qty{1, \norm{\bar{z}(0)}}. \end{align}\tag{46}\]

This implies \[\begin{align} \label{eq:32hat-z-norm-1} \forall n \in \mathbb{N}, \norm{\tilde{z}_n(0) } \leq 1. \end{align}\tag{47}\] Moreover3,

\(\forall n \in \mathbb{N}, t \in [0,T+1)\), \[\begin{align} \tilde{z}_n(t) &= \frac{\bar{z}(T_n) + \sum_{i = m(T_n)}^{m(T_n+t) - 1} (\alpha(i) H(\bar{z}(t(i)), W_{i+1}), \beta(i) G(\bar{z}(t(i)), W_{i+1}))}{r_n}\\ &= \tilde{z}_n(0) + \sum_{i = m(T_n)}^{m(T_n+t) - 1} (\alpha(i) H_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1}), \beta(i) G_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1})). \end{align}\]

Remark 12. Note that we depart from [13] in our definition of the rescaling factor \(r_n\) 46 . Through the definition, we ensure that the sequence \(\require{physics} \qty{r_n}\) is monotonic, which enables us to obtain convergence over the entire sequence rather than just a subsequence.

We also depart from prior works by defining the sequence of rescaled functions \(\require{physics} \qty{t \mapsto \tilde{z}_n(t)}\) which share the domain \([0, T+1)\), as opposed to rescaling the function \(\bar{z}(t)\) directly (often denoted as \(\hat{z}\)). This consistent, larger domain greatly simplifies our arguments, while prior works must handle the diminishing excess part \([T, T_{n+1} - T_n)\), which can get messy.

We can regard \(\tilde{z}_n(t)\) as the Euler’s discretization of \(z_n(t)\) defined below.

Definition 8. \(\forall n \in \mathbb{N}, t\in [0,T+1)\), define \(z_n(t) = (x_n(t), y_n(t))\) as the solution to the ODE system \[\begin{align} \frac{d x_n(t)}{d t} = h_{r_n}(x_n(t), y_n(t)) \tag{48} \\ \frac{d y_n(t)}{d t} = 0 \tag{49} \end{align}\] with initial condition \[\begin{align} z_n(0) = \tilde{z}_n(0). \label{def:32z32n32init} \end{align}\tag{50}\]

We can also write \(z_n(t)\) as \[\begin{align} z_n(t) &= \tilde{z}_n(0) + \int_0^t (h_{r_n}(z_n(s)), 0)ds. \label{def:32z32n32integral} \end{align}\tag{51}\] Ideally, we would like to see that the error of the discretization diminishes asymptotically. Precisely speaking, the discretization error is defined as \[\begin{align} f_n(t) \doteq \tilde{z}_n(t) - z_n(t) \label{def:32f} \end{align}\tag{52}\] and we want to show that \(f_n(t)\) diminishes to 0 uniformly in \(t\) as \(n\to\infty\). To accomplish this, we need to analyze the following three sequences of functions \[\require{physics} \begin{align} \label{eq32three32seq} \qty{t \mapsto \tilde{z}_n(t)}_{n=0}^\infty, \qty{z_n(t)}_{n=0}^\infty, \qty{f_n(t)}_{n=0}^\infty. \end{align}\tag{53}\] In particular, we show that they are all equicontinuous in the extended sense. We defer the relevant definitions, statements, and proofs to Appendix 16.3 as they are quite similar to the analogous sections in [13].

12.3 A Convergent Subsequence↩︎

The ultimate goal would be to show that \[\begin{align} \sup_n \norm{z_n} < \infty. \end{align}\] Observe the inequality \[\begin{align} \forall n, \quad \norm{z_{m(T_n)}} = \norm{\bar{z}(T_n)} \leq r_n. \label{eq:32z32m32T32n32leq32r32n} \end{align}\tag{54}\] Therefore, if we had \[\begin{align} \label{eq:32slow32sup32r32n32bounded} \sup_n r_n < \infty, \end{align}\tag{55}\] then the result would come easily. So, we assume for contradiction that \(\sup_n r_n = \infty\). However, we can’t obtain a contradiction in this section and must first show Lemma 1.

According to the Arzelà-Ascoli theorem in the extended sense (Theorem 8), a sequence of equicontinuous functions always has a subsequence of functions that uniformly converge to a continuous limit. In the following, we use this to identify a particular subsequence of interest.

Lemma 11 (2 Restated). Suppose \(\sup_n r_n = \infty\). Take an arbitrary subsequence \(\require{physics} \qty{n_{k,0}}_{k=0}^\infty \subseteq \qty{0, 1, 2, \dots}\). Then there is a subsequence \(\require{physics} \qty{n_k}_{k=0}^\infty \subseteq \qty{n_{k,0}}_{k=0}^\infty\) such that there exist some continuous functions \(f^{\lim}(t)\) and \(\tilde{z}^{\lim}(t)\) such that \(\forall t \in [0, T+1)\), \[\begin{align} \lim_{k \to \infty} f_{n_k}(t) =& f^{\lim}(t) \tag{56} , \\ \lim_{k \to \infty} \tilde{z}_{n_k}(t) =& \tilde{z}^{\lim}(t), \tag{57} \end{align}\] where both convergences are uniform in \(t\) on \([0, T+1)\). Furthermore, let \(z^{\lim}(t) = (x^{\lim}(t),y^{\lim}(t))\) denote the unique solution to the ODE system \[\begin{align} \frac{d x^{\lim}(t)}{d t} &= h_{\infty}(x^{\lim}(t), y^{\lim}(t)) \tag{58} \\ \frac{d y^{\lim}(t)}{d t} &= 0 \tag{59} \end{align}\] with the initial condition \[\begin{align} z^{\lim}(0) = \tilde{z}_n^{\lim}(0), \end{align}\] in other words, \[\begin{align} \label{eq:32z32lim32t} z^{\lim}(t) &= \tilde{z}^{\lim}(0) + \int_0^t (h_{\infty}(z^{\lim}(s)),0)ds. \end{align}\tag{60}\] Then \(\forall t \in [0, T+1)\), we have \[\begin{align} \lim_{k \to \infty} z_{n_k}(t) = z^{\lim}(t), \end{align}\] where the convergence is uniform in \(t\) on \([0, T+1)\).

Its proof is in Appendix 16.4. We use the subsequence \(\require{physics} \qty{n_k}\) intensively in the remaining proofs.

12.4 Diminishing Discretization Error↩︎

Recall that \(f_n(t)\) denotes the discretization error between \(\tilde{z}_n(t)\) and \(z_n(t)\). In this section, we will show that \(\lim_{n \to \infty} \norm{f_n(t)} = 0\) for all \(t \in [0, T+1)\). We start by first proving that the discretization error diminishes along the sequence \(\require{physics} \qty{n_k}\), i.e., that \[\begin{align} \lim_{k \rightarrow \infty} \norm{f_{n_k}(t)} = \norm{f^{\lim}(t)} = 0. \end{align}\] This means \(\tilde{z}_{n_k}(t)\) is close to \(z_{n_k}(t)\) as \(k \rightarrow \infty\). For any \(t \in [0, T+1)\), we have \[\begin{align} &\lim_{k \rightarrow \infty} \norm{ f_{n_k}(t)} \\ =& \lim_{k \rightarrow \infty} \Bigg\lVert \sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } (\alpha(i)H_{r_{n_k}}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1}), \beta(i)G_{r_{n_k}} (\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1})) \\ &- \int_0^t (h_{r_{n_k}}(z_{n_k}(s)),0)ds \Bigg\rVert \tag*{(by \eqref{def:32z32n32integral})}\\ \leq&\lim_{k \to \infty} \norm{ \sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \alpha(i)H_{r_{n_k}}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1}) - \int_0^t h_{r_{n_k}}(\tilde{z}^{\lim}(s))ds } \\ &+ \lim_{k \to \infty} \norm{\int_0^t h_{r_{n_k}}(\tilde{z}^{\lim}(s))ds - \int_0^t h_{r_{n_k}}(z_{n_k}(s))ds } \label{eq:32lim32f32k} \\ &+ \lim_{k \to \infty} \norm{ \sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \beta(i)G_{r_{n_k}}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1})}. \end{align}\tag{61}\]

Here, we will bound the last term. This term is a novelty of the two-timescale setting and so there is no analogous result in [13].

Lemma 12. \(\forall t \in [0, T+1)\), \[\begin{align} \lim_{k \to \infty} \norm{ \sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \beta(i)G_{r_{n_k}}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1})} = 0. \label{eq:32third32term32disc32error} \end{align}\tag{62}\]

Its proof is in Appendix 16.5. We defer the rest of the argument to Appendix 16.6 since it is quite similar to the relevant section in [13]. At the end of it all, from Lemma 46, we obtain \[\begin{align} \lim_{k \to \infty} \norm{f_{n_k}(t)} = 0, \end{align}\] for all \(t \in [0, T+1)\) showing that the discretization error goes to 0 along \(\require{physics} \qty{n_k}\).

Now, since we had chosen an arbitrary subsequence \(\require{physics} \qty{f_{n_{k,0}}}\) and it has a subsequence \(\require{physics} \qty{f_{n_k}}\) that converges to \(0\), by Lemma 10 we know that \(\require{physics} \qty{f_n}\) also converges to \(0\). Thus, the discretization error diminishes along the entire sequence. That is, \[\begin{align} \lim_{k \to \infty} \norm{f_n(t)} = 0 \label{eq:32whole32sequence32diminishing32disc32error} \end{align}\tag{63}\] for all \(t \in [0, T+1)\).

12.5 ODEs with External Inputs↩︎

This section contains some notation and results concerning ODEs with external inputs, which we need for the next section. First, we will define some new notation.

Definition 9. We use the notation \(\eta^{y(t)}_{c}(t,x)\) to denote the solution to the ODE \[\begin{align} \dv{x(t)}{t} = h_c(x(t), y(t)) \end{align}\]

with the initial condition \(x\).

Note that under this notation, \(x_n(t)\) \(\eqref{definition:32z32n}\) can be written \(\eta_{r_n}^{\tilde{y}_n(0)}(t, \tilde{x}_n(0))\). This notation (borrowed from [11]) is useful since it identifies a trajectory of an ODE parameterized by the rescaling factor \(c\) and the external input \(y(t)\).

The following lemma shows that within a certain amount of time, the trajectory of the ODE will be pulled close to the equilibrium determined by the external input.

Lemma 13 (Lemma 3 Restated). Let \(K \subset \mathbb{R}^{d_1}\) be compact and fix \(y \in \mathbb{R}^{d_2}\). Given any \(\epsilon > 0\), there exists a \(T_{\epsilon} > 0\) such that for all initial conditions \(x \in K\), we have \(\eta^y_{\infty}(t,x) \in B(\lambda_{\infty}(y), \epsilon)\) for all \(t \geq T_{\epsilon}\).

Its proof is in Appendix 16.7. The next lemma shows that if the external input is close to some constant \(y\), then the trajectory will remain close to the trajectory we would obtain if \(y\) was the external input.

Lemma 14 (Lemma 4 Restated). Let \(y \in \mathbb{R}^{d_2}, [0, T]\) be a given time interval, and \(\rho\) be a small positive constant with \(y'(t) \in B(y, \rho)\). Then, \[\begin{align} \norm{\eta^{y'(t)}_{c}(t,x) - \eta^{y}_{\infty}(t,x)} \leq& (L\rho + \epsilon(c))Te^{LT}. \end{align}\] for any initial \(x \in \mathbb{R}^{d_1}\) and for all \(t \in [0, T]\).

Its proof is in 16.8. Armed with these results, we are ready for the next section.

12.6 Completing the Proof↩︎

We now proceed to complete the proof of Lemma 1. The most involved result in this section is Lemma 15, which tells us that if the \(x\) component is too much larger than the \(y\) component, the norm of the iterate at \(T_{n+1}\) cannot be larger than that of the iterate at \(T_n\). We use the results about ODEs with external inputs to ensure that the \(x\) component of the trajectory gets pulled to the equilibrium, which is close to \(0\).

Lemma 15 (Lemma 5 Restated). There exists a constant \(C_1 > 1\) such that if \(\norm{\bar{x}(T_n)} > C_1(1+\norm{\bar{y}(T_n)})\), then \(r_{n+1}=r_n\).

Proof. Suppose that for some \(n\), \(\norm{\bar{x}(T_n)} > C_1 (1+\norm{\bar{y}(T_n)})\), which implies that \(\norm{\tilde{x}_n(0)} > C_1 (\frac{1}{r_n}+\norm{\tilde{y}_n(0)})\). Since \(1 \geq \norm{\tilde{x}_n(0)}\) and \(\frac{\norm{\tilde{x}_n(0)}}{C_1} > \norm{\tilde{y}_n(0)}\), we have \[\begin{align} \norm{\tilde{y}_n(0)} < \frac{1}{C_1}. \label{eq:32y32less32132over32C} \end{align}\tag{64}\]

We know from Lemma 3 that there exists some \(T_{\frac{1}{4}}\) such that for all \(t \geq T_{\frac{1}{4}}\), \[\begin{align} \norm{\eta^0_{\infty}(t,\tilde{x}_n(0))} \leq \frac{1}{4}. \label{C46832in32ball} \end{align}\tag{65}\] So if we set \(T \doteq T_{\frac{1}{4}}\), then 65 holds for all \(t \in [T, T+1)\).

From Lemma 4 we know that there exist \(\rho_{\frac{1}{4}}\) and \(c_{\frac{1}{4}}\) such that if \(y(t) \in B(0, \rho_{\frac{1}{4}})\) for all \(t \in [0, T+1)\) and \(r_n > c_\frac{1}{4}\) then \[\begin{align} \norm{\eta^{y(t)}_{r_n}(t,\tilde{x}_n(0)) - \eta^{0}_{\infty}(t,\tilde{x}_n(0))} \leq \frac{1}{4} \label{close32external32input} \end{align}\tag{66}\] for all \(t \in [0, T+1)\). Since \(\lim_{n\rightarrow \infty} r_n = \infty\), there is some finite \(n_1\) such that if \(n > n_1\), we can be sure that \(r_n > c_\frac{1}{4}\). By 63 , we know that there exists \(n_2\) such that for \(n > n_2\), the discretization error will diminish enough so that \[\begin{align} \tilde{y}_n(t) \in B \left(\tilde{y}_n(0),\min \left(\frac{\rho_{\frac{1}{4}}}{2}, \frac{1}{8} \right) \right) \label{y32tilde32in32small32ball} \end{align}\tag{67}\] for all \(t \in [0, T+1)\). So, if we choose \(C_1\) large enough so that \(C_1 > 16\) and \(\frac{1}{C_1} < \frac{\rho_{\frac{1}{4}}}{2}\), then we have \(\tilde{y}_n(t) \in B(0, \rho_{\frac{1}{4}})\) (by 64 and 67 ) for all \(t \in [0, T+1)\). So, we know that for all \(n > \max(n_1, n_2)\), 66 holds.

From 63 , we know that there is some finite \(n_3\) such that for \(n > n_3\), \[\begin{align} \norm{\tilde{x}_n(t) - \eta^{\tilde{y}_n(0)}_{r_n}(t,\tilde{x}_n(0))} \leq \frac{1}{4} \label{C46832x32discret32error} \end{align}\tag{68}\] for all \(t \in [0, T+1)\).

By 65 , 66 , and 68 , since \(\tilde{x}_n(T_{n+1}-T_n) = \frac{\bar{x}(T_{n+1})}{r_n}\), we have \(\norm{\frac{\bar{x}(T_{n+1})}{r_n}} \leq \frac{3}{4}\).

For \(n > n_1\), since \(\tilde{y}_n(T_{n+1}-T_n) = \frac{\bar{y}(T_{n+1})}{r_n}\) we also have \(\norm{\frac{\bar{y}(T_{n+1})}{r_n}} \leq \frac{1}{4}\) (by 64 , \(\frac{1}{C_1} < \frac{1}{16}\), and 67 ).

So we conclude \(\norm{\frac{\bar{z}(T_{n+1})}{r_n}} \leq 1\), telling us that \(r_{n+1} = r_n\) as desired. If we let \(n_0 = \max(n_1, n_2, n_3)\) and ensure that \(C_1 > \max_{i \leq n_0} \norm{\bar{x}(T_i)}\), then the result holds for all \(n\). ◻

Lemma 16 tells us that the iterate at each \(T_n\) is bounded by the largest \(y\) component seen so far in the sequence of times \(T_n\). To do this, we use an inductive argument–intuitively, we combine the previous lemma, which prevents \(z\) from growing if the \(x\) component is too much larger than the \(y\) component, with Lemma 61, which prevents \(z\) from growing too much within one period \(T\), ensuring that \(x\) can never get too much larger than \(y\).

Lemma 16 (Lemma 6 Restated). There exists a constant \(C_2\) such that for all \(n\), \[\begin{align} \norm{\bar{z}(T_n)} \leq C_1C_2(\max_{m\leq n} \norm{\bar{y}(T_m)}+1). \end{align}\]

Proof. From Lemma 61, we know that there are some constants \(A, B\) such that for all \(n\), \[\begin{align} \norm{\bar{z}(T_{n+1})} \leq A \norm{\bar{z}(T_n)} + B. \end{align}\]

Our argument is inductive in nature. Let \(C_1, C_2\) and ensure that \(C_1 > A + B\) and \(C_2 > 2A + B + 2\). To make sure the base case \((n=0)\), holds, we also ensure that \(C_1C_2 > \norm{z_0}\). From Lemma 15 we know that if \(\norm{\bar{x}(T_n)} \geq C_1 (1 + \norm{\bar{y}(T_n)})\), then \(r_{n+1} = r_n\). Thus, if the result holds for all \(i\) less than some \(n\), i.e., we have \(\norm{\bar{z}(T_i)} \leq C_1 C_2 (\max_{m \leq i} \norm{\bar{y}(T_m)} + 1)\) for all \(i \leq n\), then we can conclude that \(\norm{\bar{z}(T_{n+1})} \leq C_1 C_2 (\max_{m \leq n} \norm{\bar{y}(T_m)} + 1)\) also.

To address the other case, assume for some \(n\) that \(\norm{\bar{x}(T_{n})} \leq C_1(\norm{\bar{y}(T_n)}+1)\). Then we have \[\begin{align} \norm{\bar{z}(T_{n+1})} &\leq A \norm{\bar{z}(T_n)} + B \\ &\leq A \norm{\bar{x}(T_n)} + A \norm{\bar{y}(T_n)} + B \\ &\leq AC_1\norm{\bar{y}(T_n)} + AC_1 + A \norm{\bar{y}(T_n)} + B \\ &\leq C_1C_2(\norm{\bar{y}(T_n)}+1) \\ &\leq C_1C_2(\max_{m\leq n+1} \norm{\bar{y}(T_m)}+1). \end{align}\] ◻

Finally, while we’ve ensured that for all the \(T_n\) that \(\bar{z}(T_n)\) is not to much larger than \(\bar{y}(T_n)\), we need the result to also hold for all the iterates that lie in between \(T_n\) and \(T_{n+1}\). Lemma 17 takes care of this.

Lemma 17 (Lemma 7 Restated). There exists a constant \(C_3\) such that for all \(n\), \[\begin{align} \norm{x_n} \leq C_1C_2C_3(\norm{y^{\text{max}}_n} + 1), \end{align}\]

Proof. From Lemma 61, we know that for all \(m\) such that \(m(T_n) \leq m \leq m(T_{n+1})\), there exist constants \(A, B\) such that \[\begin{align} \norm{z_m} \leq A \norm{\bar{z}(T_n)} + B. \end{align}\] Let \(C_3 > A + B\). This means that \[\begin{align} \norm{x_m} \leq \norm{z_m} &\leq A C_1C_2(\max_{l\leq n} \norm{\bar{y}(T_l)}+1) + B \\ &\leq C_1C_2C_3 (\max_{l \leq n}\norm{\bar{y}(T_l)} + 1) \\ & \leq C_1C_2C_3(\norm{y^{\text{max}}_n} + 1). \end{align}\] ◻

By setting \(K\) equal to \(C_1C_2C_3\), this concludes the proof of Lemma 1.

12.7 Connecting the Timescales↩︎

Now that we have proved the first major result, Lemma 1, we now have some final tasks in the fast timescale to show that the fast iterates will track the slow iterates in some way. The result at the end of this section will be used in showing the diminishing discretization error in the slow timescale analysis.

In the following result, we show that there is a time period within which we can be such that the ODE trajectory of the fast variable will fall into and stay within a ball around \(\lambda_{\infty}(y)\).

Lemma 18. Let \(K_y \subset \mathbb{R}^{d_2}\) where \(K_y\) is compact. Given any \(\epsilon > 0\), there exists a \(T_{\epsilon} > 0\) such that for all constant external inputs \(y \in K_y\), we have \(\eta^y_{\infty}(t,x) \in B(\lambda_{\infty}(y), \epsilon)\) for any initial condition \(x \in \lambda_{\infty}(K_y)\) and for all \(t \geq T_{\epsilon}\).

Proof. By Lyapunov stability, we know that there is some \(\delta\) with \(\frac{\epsilon}{2} > \delta > 0\) such that if \(\eta_{\infty}^y(t, x) \in B(\lambda_{\infty}(y), \delta)\), then for all \(t' > t\), \(\eta_{\infty}^y(t', x) \in B(\lambda_{\infty}(y), \frac{\epsilon}{2})\). By Lemma 3 we know that there exists some time \(T_{\delta}\) such that for all \(x \in \lambda_{\infty}(K_y)\) (image of a compact set under a continuous map is compact) and \(t \geq T_{\delta}\), we have \[\begin{align} \eta^y_{\infty}(t,x) \in B(\lambda_{\infty}(y), \frac{\delta}{2}). \label{eq:32all32y32ext32inp321} \end{align}\tag{69}\] By Lemma 4, we can select \(\rho_y\) small enough such that for all \(y_1 \in B(y, \rho_y)\), \[\begin{align} \norm{\eta_{\infty}^y(t,x) - \eta_{\infty}^{y_1}(t, x)} \leq \frac{\delta}{2} \label{eq:32all32y32ext32inp322} \end{align}\tag{70}\] for all \(t \in [0, T_{\delta}]\), \(x \in \lambda_{\infty}(K_y)\).

We can split up the timeline into chunks of size \(T_{\delta}\). The insight we will rely on is that if \(\eta_{\infty}^y(T_{\delta}, x) = x_1\), then \(\eta_{\infty}^y(T_{\delta}+t, x) = \eta_{\infty}^y(t, x_1)\) for all \(t \geq 0\). The way our logic proceeds is as follows: By 69 and 70 we have that \[\begin{align} \eta_{\infty}^{y_1}(T_{\delta}, x) \in B(\lambda_{\infty}(y), \delta) \end{align}\]

Let \(x_1 \doteq \eta_{\infty}^{y_1}(T_{\delta}, x)\). For all \(t \in [0, T_{\delta}]\), we know by Lyapunov stability that \[\begin{align} \eta_{\infty}^{y}(t, x_1) \in B(\lambda_{\infty}(y), \frac{\epsilon}{2}), \end{align}\] so by 70 we know (since we can reuse the \(\rho_y\) selected earlier) that \[\begin{align} \eta_{\infty}^{y_1}(t, x_1) \in B(\lambda_{\infty}(y), \frac{3\epsilon}{4}). \end{align}\] for all \(t \in [0, T_{\delta}]\), implying that \[\begin{align} \eta_{\infty}^{y_1}(t, x) \in B(\lambda_{\infty}(y), \frac{3\epsilon}{4}) \label{eq:32all32y32ext32inp323474} \end{align}\tag{71}\] for all \(t \in [T_{\delta}, 2T_{\delta}]\).

By 69 and 70 we know that \[\begin{align} \eta_{\infty}^{y_1}(T_{\delta}, x_1) \in B(\lambda_{\infty}(y), \delta). \end{align}\] We can then define \(x_2 \doteq \eta_{\infty}^{y_1}(T_{\delta}, x_1)\) and repeat the above arguments to see that 71 holds for all \(t \in [2T_{\delta}, 3T_{\delta}]\). We can continue repeating this argument for all \(x_n\) to see that 71 holds for all \(t \geq T_{\delta}\).

Let \(L_{\lambda}\) be the Lipschitz constant for \(\lambda_{\infty}\). Then for all \(y_1 \in B(y, \frac{\epsilon}{4 L_{\lambda}})\) we have \[\begin{align} \norm{\lambda_{\infty}(y) - \lambda_{\infty}(y_1)} \leq \frac{\epsilon}{4}. \label{eq:32all32y32ext32inp323} \end{align}\tag{72}\] To summarize, by 71 and 72 , we know that if \(y_1 \in B(y, \min(\rho_y, \frac{\epsilon}{4L_{\lambda}}))\) then \[\begin{align} \eta^{y_1}_{\infty}(t,x) \in B(\lambda_{\infty}(y_1), \epsilon). \label{eq:32all32y32ext32inp32last} \end{align}\tag{73}\] Each \(y\) gives us such a ball \(B(y, \min(\rho_y, \frac{\epsilon}{4L_{\lambda}}))\) along with a \(T_{\delta}\) and these balls cover \(K\). By compactness, we can obtain a finite subcover and a finite number of times \(T_1, \ldots, T_n\). Taking \(T_{\epsilon}\) to be the maximum of these times completes the proof. ◻

The next lemma shows that if the fast variable starts close enough to the slow variable, it should stay close to it forever.

Lemma 19. Let \(K_y \subset \mathbb{R}^{d_2}\) where \(K_y\) is compact. Given any \(\epsilon > 0\), there exists a \(\delta\) such that for all constant external inputs \(y \in K_y\), if the initial condition \(x \in B(\lambda_{\infty}(y), \delta)\), then \(\eta_{\infty}^y(t,x) \in B(\lambda_{\infty}(y),\epsilon)\) for all \(t \geq 0\).

Proof. Fix \(y\) and \(\epsilon\). From Lemma 18 we know that the result holds for \(t \geq T_{\epsilon}\), so we just need to show that it holds for \(0 \leq t < T_{\epsilon}\). By Lyapunov stability, there exists \(\delta_y\) such that if \(x \in B(\lambda_{\infty}(y), \delta_y)\), then for all \(t \geq 0\), \(\eta^y_{\infty}(t, x) \in B(\lambda_{\infty}(y), \frac{\epsilon}{3})\).

By Lemma 4, there exists \(\rho\) small enough that for all \(y' \in B(y, \rho)\), \[\begin{align} \norm{\eta^y_{\infty}(t, x)-\eta^{y_1}_{\infty}(t, x)} < \frac{\epsilon}{3} \end{align}\] for all \(x \in B(\lambda_{\infty}(y), \delta_y)\), \(t \in [0, T_{\delta}]\). Finally, since \(\lambda_{\infty}\) is Lipschitz, if \(y' \in B(y, \frac{\epsilon}{3L_{\lambda}})\), \[\begin{align} \norm{\lambda_{\infty}(y)-\lambda_{\infty}(y_1)} < \frac{\epsilon}{3}. \end{align}\] Combining these facts, we know that if \(y_1 \in B(y, \min(\rho, \frac{\epsilon}{3L_{\lambda}}))\), then \(\eta_{\infty}^y(t,x) \in B(\lambda_{\infty}(y),\epsilon)\) for all \(t \geq 0\). Each \(y\) comes with such a neighborhood and a distance \(\delta\). By compactness, we can extract a finite subcover and a finite number of distances \(\delta_1, \ldots, \delta_n\), and taking \(\delta\) to be the smallest one gives us our result. ◻

Finally, we repeatedly apply the previous two lemmas every period to show that the fast iterates track the slow iterates.

Lemma 20 (Lemma 8 Restated). For any \(\epsilon > 0\), there is some \(T_{\epsilon}\) and some \(N_{\epsilon}\) such that for all \(n > N_{\epsilon}\), \(\norm{\tilde{x}_n(t) - \lambda_{\infty}(\tilde{y}_n(t))} \leq \epsilon\) for all \(t \in [0, T_{\epsilon}]\).

Proof. By 19, we know that for all \(y \in [-2, 2]^{d_2}\) (chosen since \(\norm{\tilde{y}_n(0)} \leq 1\)) there is some \(\delta\) with \(\frac{\epsilon}{2} > \delta > 0\) such that if \(\eta_{\infty}^y(t, x) \in B(\lambda_{\infty}(y), \delta)\), then for all \(t' > t\), \(\eta_{\infty}^y(t', x) \in B(\lambda_{\infty}(y), \frac{\epsilon}{2})\). By Lemma 18 we know that there exists some time \(T_{\delta}\) such that for all \(x \in \lambda_{\infty}(K_y)\) (image of a compact set under a continuous map is compact) and \(t \geq T_{\delta}\), we have, for all \(y \in [-2, 2]^{d_2}\), \[\begin{align} \eta^y_{\infty}(t,x) \in B(\lambda_{\infty}(y), \frac{\delta}{4}). \label{eq:32close32lambda32asymp32stab} \end{align}\tag{74}\]

By Lemma 4, there exists \(n_1\) such that for all \(n > n_1\), \[\begin{align} \norm{\eta^y_{r_n}(t, x) - \eta^y_{\infty}(t,x)} < \frac{\delta}{4} \label{eq:32close32lambda32e40c41} \end{align}\tag{75}\] for all \(t \in [0, T_{\delta} + 1]\).

By 63 , there exists \(n_2\) such that for all \(n > n_2\), \[\begin{align} \norm{\tilde{x}_n(t) - \eta^{\tilde{y}_n(0)}_{r_n}(t,\tilde{x}_n(0))} < \frac{\delta}{4} \label{eq:32close32lambda32x32discret} \end{align}\tag{76}\] and \[\begin{align} \norm{\lambda_{\infty}(\tilde{y}_n(t)) - \lambda_{\infty}(\tilde{y}_n(0))} \leq L_{\lambda} \norm{\tilde{y}_n(t) - \tilde{y}_n(0)} < \frac{\delta}{4} \label{eq:32close32lambda32y32discret} \end{align}\tag{77}\] for all \(t \in [0, T_{\delta} + 1]\). Combining 74 , 75 , 76 , 77 , and the fact that for \(n\) large enough, \(T_{n+1}-T_n < T + 1\), we have \[\begin{align} \norm{\tilde{x}_n(T_{n+1}-T_n) - \lambda_{\infty}(\tilde{y}_n(T_{n+1} - T_n))} < \delta \end{align}\] for all \(n > \max(n_1, n_2)\). This means that, by homogeneity of \(\lambda_{\infty}\), \[\begin{align} \norm{\tilde{x}_{n+1}(0)-\lambda_{\infty}(\tilde{y}_{n+1}(0))} = \frac{r_n}{r_{n+1}} \norm{\tilde{x}_n(T_{n+1} - T_n) - \lambda_{\infty}(\tilde{y}_n(T_{n+1} - T_n))} < \delta \end{align}\] when \(n > \max(n_1, n_2)\), giving us \[\begin{align} \norm{\tilde{x}_n(0)-\lambda_{\infty}(\tilde{y}_n(0))} < \delta \end{align}\] for all \(n > N_{\epsilon} = \max(n_1, n_2) + 1\). So, \[\begin{align} \norm{\eta^{\tilde{y}_n(0)}_{r_n}(t, \tilde{x}_n(0))-\lambda_{\infty}(\tilde{y}_n(0))} < \frac{\epsilon}{2} \end{align}\] for all \(t \geq 0\). Combining this with 76 and 77 gives us \[\begin{align} \norm{\tilde{x}_n(t) - \lambda_{\infty}(\tilde{y}_n(t))} \leq \epsilon \end{align}\] for all \(t \in [0, T_{\delta}]\), as desired. Taking \(T_{\epsilon} \doteq T_{\delta}\) completes the proof. ◻

13 Proof of Theorem 1↩︎

In this section we will prove Theorem 1.

13.1 Slow Timescale Setup↩︎

Here we are working in the slow timescale. We reuse the notation from Section 12.1 but redefine some things in terms of the slow timescale. We split the positive real axis \([0, \infty)\) into chunks of length \(\require{physics} \qty{\beta(i)}_{i=0,1,\dots}\). We then collect these segments together into larger intervals \(\require{physics} \qty{[T_n, T_{n+1})}_{n=0,1,\dots}\), where the sequence \(\require{physics} \qty{T_n}\) has the property that as \(n\) grows large, we have \(T_{n+1} - T_n \approx T\). We define \[\begin{align} t(0) \doteq& 0, \\ t(n) \doteq& \sum_{i=0}^{n-1} \beta(i) \qq{n=1,2,\dots}. \end{align}\] For all \(T > 0\), define \[\require{physics} \begin{align} m(T) = \max\qty{{i | T \geq t(i)}} \label{def:32slow32m} \end{align}\tag{78}\] to be the maximal \(i\) where \(t(i)\) is no greater than \(T\).

Define \[\begin{align} &T_0 = 0, \\ &T_{n+1} = t(m(T_n+T) + 1) \label{def:32slow32T}. \end{align}\tag{79}\]

For any given function \(f\) with domain \(\mathcal{W}\), its asymptotic rate of change is defined as \[\require{physics} \begin{align} \limsup_n \sup_{-\tau \leq t_1 \leq t_2 \leq \tau} \norm{\sum_{i = m(t(n) + t_1)}^{m(t(n) + t_2) - 1} \beta(i) [f(W_{i+1}) - \mathbb{E}_{w\sim d_\mathcal{W}}\qty[f(w)]] }. \end{align}\]

13.2 Defining the Slow Iterates↩︎

Here, we take \(\bar{z}(t)\) to be the piecewise constant interpolation of \(z_n\) at points \(\require{physics} \qty{t(n)}_{n=0,1,\dots}\), i.e.,

\[\begin{align} \bar z(t) \doteq (\bar{x}(t),\bar y(t)) \doteq \begin{cases} (x_0, y_0) & t \in [0,t(1)) \\ (x_1, y_1) & t \in [t(1),t(2)) \\ (x_2, y_2) & t \in [t(2),t(3)) \\ \vdots & \end{cases} \end{align}\]

Now we describe our rescaling of \(\bar z(t)\).

Definition 10. \(\forall n \in \mathbb{N}, t \in [0,T+1)\), define \[\begin{align} \label{def:32tilde32z} \tilde{z}_n(t) \doteq (\tilde{x}_n(t), \tilde{y}_n(t)) &\doteq \frac{\bar{z}(T_n + t)}{r_n}. \end{align}\tag{80}\]

We will define \(r_n\) differently, such that it will be at least as large as the largest iterate seen so far: \[\require{physics} \begin{align} r_n \doteq \max\qty{1, \norm{z^{max}_{m(T_n)}}} \label{def:32slow32r32n}. \end{align}\tag{81}\] where \(z^{max}_n \doteq z_m\) such that \(m = \arg\max_{i \leq n} \norm{z_i}\) (with ties broken arbitrarily).

We can regard \(\tilde{y}_n(t)\) as the Euler’s discretization of \(y_n(t)\) defined below.

Definition 11. \(\forall n \in \mathbb{N}, t\in [0,T+1)\), define \(y_n(t)\) as the solution to the ODE \[\begin{align} \frac{d y_n(t)}{d t} = g_{r_n}(\lambda_{\infty}(y_n(t)), y_n(t)) \label{eq:32slow32y32n} \end{align}\tag{82}\] with initial condition \[\begin{align} y_n(0) = \tilde{y}_n(0). \label{eq:32y32n32init} \end{align}\tag{83}\]

We can also write \(y_n(t)\) as \[\begin{align} y_n(t) &= \tilde{y}_n(0) + \int_0^t g_{r_n}(\lambda_{\infty}(y_n(t)), y_n(t))ds. \label{def:32y32n32integral} \end{align}\tag{84}\] The discretization error is defined as \[\begin{align} f_n(t) \doteq \tilde{y}_n(t) - y_n(t) \label{def:32slow32f} \end{align}\tag{85}\] and we want to show that \(f_n(t)\) diminishes to 0 uniformly in \(t\) as \(n\to\infty\). To accomplish this, we need to show that the following three sequences of functions are equicontinuous in the extended sense: \[\require{physics} \begin{align} \label{eq32slow32three32seq} \qty{t \mapsto \tilde{y}_n(t)}_{n=0}^\infty, \qty{y_n(t)}_{n=0}^\infty, \qty{f_n(t)}_{n=0}^\infty. \end{align}\tag{86}\] We deferred the relevant definitions to Appendix 16.3 as they are quite similar to the analogous sections in [13], but we will prove it for one of the sequences of functions.

Lemma 21. \(\require{physics} \qty{\tilde{y}_n(t)}_{n=0}^\infty\) is equicontinuous in the extended sense on \([0, T+1)\).

Its proof is in Appendix [proof:32hat32y32equicontinuous]. Equicontinuity for the other two sequences of functions follows more similarly to the fast timescale arguments.

13.3 A Convergent Subsequence↩︎

The ultimate goal is to show that \[\begin{align} \sup_n \norm{z_n} < \infty. \end{align}\] Once again, observe the inequality \[\begin{align} \forall n, \quad \norm{z_{m(T_n)}} = \norm{\bar{z}(T_n)} \leq r_n. \label{eq:32slow32z32m32T32n32leq32r32n} \end{align}\tag{87}\] Therefore, if we had \[\begin{align} \label{eq:32sup32r32n32bounded} \sup_n r_n < \infty, \end{align}\tag{88}\] then the result would come easily. So, we assume for contradiction from now on that \(\sup_n r_n = \infty\).

According to the Arzelà-Ascoli theorem in the extended sense (Theorem 8), a sequence of equicontinuous functions always has a subsequence of functions that uniformly converge to a continuous limit. In the following, we use this to identify a particular subsequence of interest.

Lemma 22. Suppose \(\sup_n r_n = \infty\). Take an arbitrary subsequence \(\require{physics} \qty{n_{k,0}}_{k=0}^\infty \subseteq \qty{0, 1, 2, \dots}\). Then there is a subsequence \(\require{physics} \qty{n_k}_{k=0}^\infty \subseteq \qty{n_{k,0}}_{k=0}^\infty\) such that there exist some continuous functions \(f^{\lim}(t)\) and \(\tilde{y}^{\lim}(t)\) such that \(\forall t \in [0, T+1)\), \[\begin{align} \lim_{k \to \infty} f_{n_k}(t) =& f^{\lim}(t) \tag{89} , \\ \lim_{k \to \infty} \tilde{y}_{n_k}(t) =& \tilde{y}^{\lim}(t), \tag{90} \end{align}\] where both convergences are uniform in \(t\) on \([0, T+1)\). Furthermore, let \(y^{\lim}(t)\) denote the unique solution to the ODE \[\begin{align} \frac{d y^{\lim}(t)}{d t} &= g_{\infty}(\lambda_{\infty}(y^{\lim}(t)), y^{\lim}(t)) \label{def:32slow32ylim} \\ \end{align}\tag{91}\] with the initial condition \[\begin{align} y^{\lim}(0) = \tilde{y}_n^{\lim}(0), \end{align}\] in other words, \[\begin{align} \label{eq:32y32lim32t} y^{\lim}(t) &= \tilde{y}^{\lim}(0) + \int_0^t g_{\infty}(\lambda_{\infty}(y^{\lim}(s)), y^{\lim}(s)) ds. \end{align}\tag{92}\] Then \(\forall t \in [0, T+1)\), we have \[\begin{align} \lim_{k \to \infty} y_{n_k}(t) = y^{\lim}(t), \end{align}\] where the convergence is uniform in \(t\) on \([0, T+1)\).

Its proof is in Appendix 16.10. We use the subsequence \(\require{physics} \qty{n_k}\) intensively in the remaining proofs.

13.4 Diminishing Discretization Error↩︎

Recall that \(f_n(t)\) denotes the discretization error between \(\tilde{y}_n(t)\) and \(y_n(t)\). In this section, we will show that \(\lim_{n \to \infty} \norm{f_n(t)} = 0\) for all \(t \in [0, T+1)\). We start by first proving that the discretization error diminishes along the sequence \(\require{physics} \qty{n_k}\), i.e., that \[\begin{align} \lim_{k \rightarrow \infty} \norm{f_{n_k}(t)} = \norm{f^{\lim}(t)} = 0. \end{align}\] This means \(\tilde{y}_{n_k}(t)\) is close to \(y_{n_k}(t)\) as \(k \rightarrow \infty\). For any \(t \in [0, T+1)\), we have \[\begin{align} &\lim_{k \rightarrow \infty} \norm{ f_{n_k}(t)} \\ =& \lim_{k \rightarrow \infty} \Bigg\lVert \sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \beta(i)G_{r_{n_k}} (\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1}) - \int_0^t g_{r_{n_k}}(\lambda_{\infty}(y_{n_k}(s)), y_{n_k}(s))ds \Bigg\rVert \tag*{(by \eqref{def:32y32n32integral})}\\ \leq&\lim_{k \to \infty} \norm{ \sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \beta(i)[G_{r_{n_k}}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1}) - G_{r_{n_k}}(\lambda_{\infty}(\tilde{y}_{n_k}(t(i)-T_{n_k})),\tilde{y}_{n_k}(t(i)-T_{n_k}),W_{i+1})]} \tag{93} \\ &+ \norm{\sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \beta(i) G_{r_{n_k}}(\lambda_{\infty}(\tilde{y}_{n_k}(t(i)-T_{n_k})),\tilde{y}_{n_k}(t(i)-T_{n_k}),W_{i+1})-\int_0^t g_{r_{n_k}}(\lambda_{\infty}(y_{n_k}(s)),y_{n_k}(s))ds }. \tag{94} \\ \end{align}\]

Lemma 23 (Lemma 9 Restated). For all \(\epsilon > 0\), there exists some \(N\) such that for all \(n > N\), \[\begin{align} \norm{\tilde{x}_n(t) - \lambda_{\infty}(\tilde{y}_n(t))} < \epsilon \end{align}\] for all \(t \in [0, T].\)

Proof. For clarity, since we will work with both fast and slow timescale objects, we will use \(\alpha\) and \(\beta\) in superscripts to indicate the fast and slow timescale variants respectively. We also define some notation to help in converting between timescales: \[\begin{align} \tau^{\alpha}(t) \doteq t^{\alpha}(m^{\beta}(t)) \\ \tau^{\beta}(t) \doteq t^{\beta}(m^{\alpha}(t)) \end{align}\] By the difference in how the rescaling is defined between the timescales, we know that \(\norm{\tilde{z}^{\beta}_n(0)} \leq \norm {\tilde{z}^{\alpha}_{m}(\tau^{\alpha}(T_n^{\beta})-T_m^{\alpha})}\), where \(m\) is the largest \(v\) such that \(T_v^{\alpha} \leq \tau^{\alpha}(T_n^{\beta})\). Essentially, whenever the slow timescale is rescaled, the iterate has a smaller norm than the fast timescale’s iterate at that index. Now we need to show that for the rest of that period in the slow timescale (i.e. when \(T^{\beta}_n \leq t \leq T^{\beta}_{n+1}\)) the slow timescale iterates, despite not being rescaled during this period, never get too much larger than the fast timescale iterates which may be rescaled many times.

Thus, given \(t \in [0, T^{\beta}]\), we are interested in the ratio \(\frac{r^{\alpha}_l}{r^{\beta}_n}\), where \(l\) is the largest \(v\) where \(T_v^{\alpha} \leq \tau^{\alpha}(T_n^{\beta}+t)\). By Lemma 65 we know that \[\begin{align} r^{\alpha}_l \leq \norm{z^{max}_{m^{\beta}(T^{\beta}_n+t)}} \leq C \norm{z^{max}_{m^{\beta}(T_n^{\beta})}} + D = C \cdot r^{\beta}_n + D \end{align}\] implying that \[\begin{align} \frac{r^{\alpha}_l}{r^{\beta}_n} \leq C + \frac{D}{r^{\beta}_n}. \end{align}\] There exists \(n_1\) such that for all \(n> n_1\), \(\frac{D}{r^{\beta}_n} \leq C\), so for all \(n > n_1\), \[\begin{align} \frac{r^{\alpha}_l}{r^{\beta}_n} \leq 2C. \end{align}\] By Lemma 20, there exist \(n_2\) and \(T_{\epsilon}\) such that for all \(n> n_{\epsilon}\), we have \[\begin{align} \norm{\tilde{x}^{\alpha}_n(t) - \lambda_{\infty}(\tilde{y}^{\alpha}_n(t))} \leq \frac{\epsilon}{2C} \end{align}\] for all \(t \in [0, T_{\epsilon}]\). Now, set \(\require{physics} N = \max \qty{n_1, n_2}\), where \(n_2\) is the smallest \(v\) such that \(T_v^{\beta} \geq \tau^{\beta}(T_{n_{\epsilon}}^{\alpha})\) and \(T^{\alpha}\) is set to \(T_{\epsilon}\). We then have, for all \(t \in [0, T^{\beta}]\), by homogeneity of \(\lambda_{\infty}\), \[\begin{align} \norm{\tilde{x}^{\beta}_n(t) - \lambda_{\infty}(\tilde{y}^{\beta}_n(t))} \leq 2C \norm{\tilde{x}^{\alpha}_l(\tau^{\alpha}(T_n^{\beta}+t)) - \lambda_{\infty}(\tilde{y}^{\alpha}_l(\tau^{\alpha}(T_n^{\beta}+t)))} \leq \epsilon \end{align}\] for all \(n > N\). Since we set \(T^{\alpha}\) to \(T_{\epsilon}\) without modifying \(T^{\beta}\), the result holds for all \(\epsilon\), regardless of what value we set \(T^{\beta}\) to at the start. ◻

Lemma 24. The first error term 93 converges to 0.

Proof. \[\begin{align} \lim_{k \to \infty} &\norm{ \sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \beta(i)[G_{r_{n_k}}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1}) - G_{r_{n_k}}(\lambda_{\infty}(\tilde{y}_{n_k}(t(i)-T_{n_k})),\tilde{y}_{n_k}(t(i)-T_{n_k}),W_{i+1})]} \\ \leq& \lim_{k \to \infty} \sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \beta(i) L(W_i) \norm{\tilde{x}_{n_k}(t(i)-T_{n_k})-\lambda_{\infty}(\tilde{y}_{n_k}(t(i)-T_{n_k}))} \\ \leq& \lim_{k \to \infty} \epsilon(k) \sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \beta(i) L(W_i) \tag*{(Lemma \ref{lemma:32slow4432x32close32lambda32y})} \\ \leq& C \lim_{k \to \infty} \epsilon(k) \tag*{(\ref{eq:32L32property32bounded})} \\ =& 0. \end{align}\] ◻

The rest of the proof, including the verification that the other term diminishes is the same as [13] and the fast timescale’s analogous term.

Now, since we had chosen an arbitrary subsequence \(\require{physics} \qty{f_{n_{k,0}}}\) and it has a subsequence \(\require{physics} \qty{f_{n_k}}\) that converges to \(0\), by Lemma 10 we know that \(\require{physics} \qty{f_n}\) also converges to \(0\). Thus, the discretization error diminishes along the entire sequence. That is, \[\begin{align} \lim_{k \to \infty} \norm{f_n(t)} = 0 \label{eq:32slow32diminishing32disc32error} \end{align}\tag{95}\] for all \(t \in [0, T+1)\).

13.5 Completing the Proof↩︎

Now we finish the proof by first establishing two results about ODEs and then finding the contradiction.

Definition 12. We use the notation \(\chi_{c}(t,y)\) to denote the solution to the ODE \[\begin{align} \dv{y(t)}{t} = g_c(\lambda_{\infty}(y(t)), y(t)) \end{align}\]

with the initial condition \(y\).

Note that under this notation, \(y_n(t)\) \(\eqref{definition:32slow32y32n}\) can be written \(\chi_{r_n}(t, \tilde{y}_n(0))\).

The next result shows us that there is a period within which the trajectory of the slow variable will fall to 0.

Lemma 25. Let \(K \subset \mathbb{R}^{d_2}\) be compact. Given any \(\epsilon > 0\), there exists a \(T_{\epsilon}\) such that for all initial conditions \(y \in K\), \(\chi_{\infty}(t, y) \in B(0, \epsilon)\) for all \(t > T_{\epsilon}\).

Proof. By Lyapunov stability, there is a \(\delta > 0\) such that any trajectory beginning within \(B(0, \delta)\) stays within \(\frac{\epsilon}{2}\) of the equilibrium \(0\).

For an initial condition \(y\), let \(T_y\) be a time at which the trajectory is within \(\frac{\delta}{2}\) of the equilibrium. Let \(y_1\) be some other initial condition. By definition, Lipschitzness, and the Gronwall inequality, we have \[\begin{align} \norm{\chi_{\infty}(t, y) - \chi_{\infty}(t, y_1) } &\leq \norm{y-y_1} + L(L_{\lambda}+1) \int_0^t \norm{\chi_{\infty}(s, y) - \chi_{\infty}(s, y_1)}ds \\ &\leq \norm{y-y_1}e^{L (L_{\lambda}+1) T_y} \end{align}\] for all \(t \leq T_y\).

So there is a neighborhood \(V_y\) such that for all \(y_1 \in V_y\), \(\chi_{\infty}(T_y, y_1)\) is within \(\delta\) of the equilibrium, which by Lyapunov stability implies that it will always be within \(\epsilon\) of the equilibrium after \(T_y\).

By compactness, we can cover the set \(K\) by a finite number of such intervals and obtain a finite number of times \(T_{y_1}, \ldots, T_{y_n}\) and then take the maximum time to be the value of \(T_{\epsilon}\). ◻

The next lemma shows that as \(c\) approaches infinity, the two trajectories remain close within a certain time interval.

Lemma 26. Let \([0, T]\) be a given time interval. Then, \[\begin{align} \norm{\chi_{c}(t,y) - \chi_{\infty}(t,y)} \leq& \epsilon(c) \cdot Te^{L(L_{\lambda}+1)T}. \end{align}\] for any initial \(y \in \mathbb{R}^{d_2}\) and for all \(t \in [0, T]\).

Proof. We have \[\begin{align} \chi_{c}(t,y) &= y + \int_0^t g_c(\lambda_{\infty}(\chi_c(s, y)), \chi_c(s, y)) ds, \\ \chi_{\infty}(t,y) &= y + \int_0^t g_{\infty}(\lambda_{\infty}(\chi_{\infty}(s, y)), \chi_{\infty}(s, y)) ds. \end{align}\] Let us define the error term: \[\begin{align} e(t) = \norm{\chi_{c}(t,y) - \chi_{\infty}(t,y)}. \end{align}\]

We can bound \(e(t)\) by two terms: \[\begin{align} e(t) \leq& \int_0^t \norm{g_c(\lambda_{\infty}(\chi_c(s, y)), \chi_c(s, y)) - g_c(\lambda_{\infty}(\chi_{\infty}(s, y)), \chi_{\infty}(s, y))} ds \\ &+ \int_0^t \norm{g_c(\lambda_{\infty}(\chi_{\infty}(s, y)), \chi_{\infty}(s, y)) - g_{\infty}(\lambda_{\infty}(\chi_{\infty}(s, y)), \chi_{\infty}(s, y))} ds \end{align}\] To bound the first term, we use Lipschitzness: \[\begin{align} &\int_0^t \norm{g_c(\lambda_{\infty}(\chi_c(s, y)), \chi_c(s, y)) - g_c(\lambda_{\infty}(\chi_{\infty}(s, y)), \chi_{\infty}(s, y))} ds \\ &\leq L(L_{\lambda}+1) \int_0^t \norm{\chi_{c}(t,y) - \chi_{\infty}(t,y)} ds \\ &= L \int_0^t e(s) ds. \end{align}\]

To bound the second term, we use Lipschitzness and Assumption 3:

\[\begin{align} \int_0^t &\norm{g_c(\lambda_{\infty}(\chi_{\infty}(s, y)), \chi_{\infty}(s, y)) - g_{\infty}(\lambda_{\infty}(\chi_{\infty}(s, y)), \chi_{\infty}(s, y))} ds \\ \leq& \int_0^t \epsilon(c) ds\\ \leq& T\epsilon(c). \end{align}\]

To conclude, we will use the Gronwall Inequality (Appendix 5): \[\begin{align} e(t) \leq& T \epsilon(c) + L(L_{\lambda}+1) \int_0^t e(s)ds \\ \leq& \epsilon(c) \cdot Te^{L(L_{\lambda}+1)T}. \end{align}\] ◻

Since in this section, \(r_n\) is defined as the largest iterate norm seen so far, if it is bounded, then the iterate norms are bounded, verifying Theorem 1.

Lemma 27. The sequence \(r_n\) is bounded, creating a contradiction.

Proof. By Lyapunov stability there is some \(\delta\) with \(\frac{1}{4(L_{\lambda}+1)} > \delta > 0\) such that if \(\chi_{\infty}(t, y) \in B(0, \delta)\) at some time \(t\), then for all times \(t' > t\), we have \[\begin{align} \chi_{\infty}(t', y) \in B \left(0, \frac{1}{4(L_{\lambda}+1)} \right). \label{eq:32slow32chi32lyapunov} \end{align}\tag{96}\] By Lemma 25 we know that there is a \(T_{\delta}\) such that when we set \(T=T_{\delta}\), for all \(t > T\), \[\begin{align} \chi_{\infty}(t, y) \in B(0, \frac{\delta}{3}) \label{eq:32slow32chi32fall} \end{align}\tag{97}\] for all \(y \in [-2, 2]^{d_2}\).

By Lemma 26 we know that there is an \(n_1\) such that for all \(n > n_1\), \[\begin{align} \norm{\chi_{r_n}(t,y) - \chi_{\infty}(t,y)} < \frac{\delta}{3} \label{eq:32slow32chi32close} \end{align}\tag{98}\] for all \(y \in [-2, 2]^{d_2}\) and \(t \in [0, T+1]\).

By 95 , we know that there is an \(n_2\) such that for all \(n > n_2\), we have \[\begin{align} \norm{\tilde{z}_n(t)-(\lambda_{\infty}(\chi_{r_n}(t, \tilde{y}_n(0))), \chi_{r_n}(t, \tilde{y}_n(0)))} < \frac{\delta}{3} \label{eq:32finishing32slow32disc} \end{align}\tag{99}\] for all \(t \in [0, T+1]\).

From 97 , 98 , and 99 , and the fact that when \(n\) is large enough, \(T_{n+1}-T_n < T + 1\), we have \[\begin{align} \tilde{y}_n(0) \in B(0, \delta) \end{align}\] for all \(\require{physics} n \geq \max\qty{n_1, n_2}+1\). Thus, from 96 , we have \[\begin{align} \chi_{\infty}(t, \tilde{y}_n(0)) \in B \left(0, \frac{1}{4(L_{\lambda}+1)} \right) \end{align}\] for all \(t \in [0, T + 1]\), which implies that \[\begin{align} (\lambda_{\infty}(\chi_{\infty}(t, \tilde{y}_n(0))), \chi_{\infty}(t, \tilde{y}_n(0))) \in B \left(0, \frac{1}{4}\right). \end{align}\] Combining this with 99 gives us \[\begin{align} \tilde{z}_n(t) \in B(0, \frac{1}{2}), \end{align}\] for all \(\require{physics} n \geq \max\qty{n_1,n_2}+1\) and \(t \in [0,T+1]\), which, by definition, prevents the sequence \(r_n\) from increasing, contradicting the assumption that \(r_n\) increases to infinity. ◻

14 Convergence↩︎

14.1 Fast Timescale Convergence↩︎

In this section, we return to the fast timescale definitions.

Corollary 1. Let Assumptions 1 - 6 hold. Then the iterates \(\require{physics} \qty{z_n}\) generated by 1 converge almost surely to a (sample path dependent) bounded invariant set 4 of the ODE system 5 \[\begin{align} \label{cor32eq32original32ode32system} \dv{x(t)}{t} &= h(x(t), y(t)) \\ \dv{y(t)}{t} &= 0. \end{align}\tag{100}\]

Proof. To prove convergence results on \(t \in(-\infty, \infty)\) in Corollary 1, we fix an arbitrary sample path \(\require{physics} \qty{z_0,\qty{W_i}_{i=1}^\infty}\). The stability results from Theorem 1 hold. To prove properties on \(t \in(-\infty, \infty)\), we first fix an arbitrary \(\tau > 0\) and show properties on \(\forall t \in [-\tau, \tau]\).

Definition 13. \(\forall n \in \mathbb{N}\), define \(\bar{z}_n(t)\) as the solution to the ODE 100 in \((-\infty, \infty)\) with an initial condition \[\begin{align} \bar{z}_n(0) = \bar{z}(t(n)). \label{cor-def:32z32n32init} \end{align}\tag{101}\]

\(\bar{z}_n(t)\) can also be written as \[\begin{align} \bar{z}_n(t) &= \bar{z}(t(n)) + \int_0^t (h(\bar{z}_n(s)),0)ds, \quad \forall t \in (-\infty, \infty). \label{cor-def:32z32n32integral} \end{align}\tag{102}\]

We need to show that the error of Euler’s discretization diminishes asymptotically. With 44 and 45 , \(\forall \tau > 0\), \(\forall t \in [-\tau, \tau]\), \[\begin{align} \label{eq:32bar32z32extend} &\bar{z}(t(n) + t) = z_{m(t(n) + t)} \\ &= \begin{cases} \bar{z}(t(n)) + \sum_{i = n}^{m(t(n)+t) - 1} (\alpha(i) H(\bar{z}(t(i)), W_{i+1}),\beta(i)G(\bar{z}(t(i)),W_{i+1})) & \text{if } t \geq 0 \\ \bar{z}(t(n)) - \sum_{i = m(t(n)+t)}^{n - 1} (\alpha(i) H(\bar{z}(t(i)), W_{i+1}),\beta(i)G(\bar{z}(t(i)),W_{i+1})) & \text{if } t < 0. \end{cases} \end{align}\tag{103}\] Notably, the property 44 that \(\forall t<0, m(t) = 0\) in 103 ensures \(\bar{z}(t(n) + t)\) is well-defined when \(t(n) + t < 0\). Precisely speaking, \(\forall \tau > 0\), \(\forall t \in [-\tau, \tau]\), the discretization error is defined as \[\begin{align} \bar{f}_n(t) \doteq \bar{z}(t(n) + t) - \bar{z}_n(t). \label{cor-def:32f} \end{align}\tag{104}\] and we need \(\bar{f}_n(t)\) to diminish to 0 as \(n\to\infty\). To this end, we study the following three sequences of functions \[\require{physics} \begin{align} \label{cor-eq32three32seq} \qty{ \bar z(t(n) + t)}_{n=0}^\infty, \qty{\bar{z}_n(t)}_{n=0}^\infty, \qty{\bar{f}_n(t)}_{n=0}^\infty. \end{align}\tag{105}\] Equicontinuity in the extended sense on the domain \((-\infty, \infty)\) is defined as following (Section 4.2.1 in [3]).

Definition 14. A sequence of functions \(\require{physics} \qty{{\gamma}_n: (-\infty, \infty) \to \mathbb{R}^K }\) is equicontinuous in the extended sense on \((-\infty, \infty)\) if \(\sup_n \norm{{\gamma}_n(0)} < \infty\) and \(\forall \tau > 0\), \(\forall \epsilon > 0\), \(\exists \delta > 0\) such that \[\begin{align} \label{eq:32equicontinuity32inf32inf32epsilon} \limsup_n \sup_{0\leq \abs{t_1-t_2} \leq \delta, \abs{t_1} \leq \tau,\abs{t_2} \leq \tau } \norm{{\gamma}_n(t_1) - {\gamma}_n(t_2)} \leq \epsilon. \end{align}\tag{106}\]

We show \(\require{physics} \qty{\bar{z}(t(n)+t)}\), \(\require{physics} \qty{\bar{z}_n(t)}\) and \(\require{physics} \qty{\bar{f}_n(t)}\) are all equicontinuous in the extended sense.

Lemma 28. The three sequences of functions \(\require{physics} \qty{\bar{z}(t(n)+t)}_{n = 0}^{\infty}\), \(\require{physics} \qty{\bar{z}_n(t)}_{n = 0}^{\infty}\), and \(\require{physics} \qty{\bar{f}_n(t)}_{n = 0}^{\infty}\) are all equicontinuous in the extended sense on \(t \in (-\infty, \infty)\).

To prove those lemmas, we need the Gronwall inequality in the reverse time in Appendix 6. Compared to lemmas in the main text which have the domain \(t \in [0,T+1)\), lemmas in this section have similar proofs because we first fix an arbitrary \(\tau\) and prove properties on the domain \(t \in [-\tau, \tau]\). We omit proofs for Lemma 28 because they are extremely similar to the proofs of equicontinuity in the fast timescale. Similar to Lemma 2, we now construct a particular subsequence of interest.

Lemma 29. There exists a subsequence \(\require{physics} \qty{n_k}_{k=0}^\infty \subseteq \qty{0, 1, 2, \dots}\) and some continuous functions \(\bar{f}^{\lim}(t)\) and \(\bar{z}^{\lim}(t)\) such that \(\forall \tau\), \(\forall t \in [-\tau, \tau]\), \[\begin{align} \lim_{k \to \infty} \bar{f}_{n_k}(t) =& \bar{f}^{\lim}(t) \tag{107} , \\ \lim_{k \to \infty} \bar{z}(t(n_k)+t) =& \bar{z}^{\lim}(t), \tag{108} \end{align}\] where both convergences are uniform in \(t\) on \([-\tau, \tau]\). Furthermore, let \(z^{\lim}(t)\) denote the unique solution to the ODE 100 with the initial condition \[\begin{align} z^{\lim}(0) = \bar{z}^{\lim}(0), \end{align}\] in other words, \[\begin{align} \label{cor-eq:32z32lim32t} z^{\lim}(t) &= \bar{z}^{\lim}(0) + \int_0^t (h(\bar{z}^{\lim}(s)), 0)ds. \end{align}\tag{109}\] Then \(\forall \tau\), \(\forall t \in [-\tau, \tau]\), we have \[\begin{align} \lim_{k \to \infty} \bar{z}_{n_k}(t) = z^{\lim}(t), \label{cor-eq:32z32lim32converge} \end{align}\tag{110}\] where the convergence is uniform in \(t\) on \([-\tau, \tau]\).

Its proof is very similar to the proof of Lemma 2 and is omitted. We use the subsequence \(\require{physics} \qty{n_k}\) intensively in the remaining proofs. Recall that \(\bar{f}_n(t)\) denotes the discretization error between \(\bar z(t(n) + t)\) and \(\bar{z}_n(t)\). We now proceed to prove that this discretization error diminishes along \(\require{physics} \qty{n_k}\). In particular, we aim to prove that \(\forall \tau\), \(\forall t \in [-\tau, \tau]\),

\[\begin{align} \lim_{k \rightarrow \infty} \norm{\bar{f}_{n_k}(t)} = \norm{\bar{f}^{\lim}(t)} = 0. \end{align}\] This means \(\bar{z}(t(n_k) + t)\) is close to \(\bar{z}_{n_k}(t)\) as \(k \rightarrow \infty\). For \(t \in (0,\tau]\), the proof for this part is the same as the proof we have done in Section 12.4. Thus, we only discuss the proof for \(t \in [-\tau, 0]\). \(\forall \tau\), \(\forall t \in [-\tau, 0]\), \[\begin{align} &\lim_{k \rightarrow \infty} \norm{ \bar{f}_{n_k}(t)} \\ =& \lim_{k \rightarrow \infty} \norm{ \bar{z}(t(n_k)) -\sum_{i = m(t(n_k)+t)}^{n_k - 1} (\alpha(i)H(\bar{z}(t(i)),W_{i+1}), \beta(i)G(\bar{z}(t(i)),W_{i+1})) - \bar{z}_{n_k}(t)} \tag*{(by \eqref{eq:32bar32z32extend} and \eqref{cor-def:32f})}\\ =& \lim_{k \rightarrow \infty} \norm{ -\sum_{i = m(t(n_k)+t)}^{n_k - 1} (\alpha(i)H(\bar{z}(t(i)),W_{i+1}), \beta(i)G(\bar{z}(t(i)),W_{i+1})) - \int_0^t (h(\bar{z}_{n_k}(s)),0)ds} \tag*{(by \eqref{cor-def:32z32n32integral})}\\ \leq&\lim_{k \to \infty} \norm{ -\sum_{i = m(t(n_k)+t)}^{n_k - 1} \alpha(i)H(\bar{z}(t(i)),W_{i+1}) - \int_0^t h(\bar{z}^{\lim}(s))ds } \\ &+ \lim_{k \to \infty} \norm{ -\sum_{i = m(t(n_k)+t)}^{n_k - 1} \beta(i)G(\bar{z}(t(i)),W_{i+1}) } \\ &+ \lim_{k \to \infty} \norm{\int_0^t h(\bar{z}^{\lim}(s))ds - \int_0^t h(\bar{z}_{n_k}(s))ds } . \label{cor-eq:32lim32f32k} \\ \end{align}\tag{111}\]

The second term in the RHS of 111 is 0.

Lemma 30. \(\forall \tau\), \(\forall t \in [-\tau, 0]\), \[\begin{align} \lim_{k \to \infty} \norm{ -\sum_{i = m(t(n_k)+t)}^{n_k - 1} \beta(i)G(\bar{z}(t(i)),W_{i+1}) } =0. \end{align}\]

The proof is very similar to the proof of Lemma 12 so is omitted.

The first term in the RHS of 111 is also 0.

Lemma 31. \(\forall \tau\), \(\forall t \in [-\tau, 0]\), \[\begin{align} \lim_{k \to \infty} \norm{ -\sum_{i = m(t(n_k)+t)}^{n_k - 1} \alpha(i)H(\bar{z}(t(i)),W_{i+1}) - \int_0^t h(\bar{z}^{\lim}(s))ds } = 0. \end{align}\]

Its proof is very similar to the proof of Lemma 44 and is omitted. This convergence is also simpler than 148 because here we have only a single \((H, h)\). But in 148 , we have a sequence \(\require{physics} \qty{(H_{n_k}, h_{n_k})}\), for which we have to split it to a double limit 149 and then invoke the Moore-Osgood theorem to reduce it to the single \((H, h)\) case.

Lemma 31 confirms that the first term in the RHS of 111 is 0. Moreover, it also enables us to rewrite \(\bar{z}^{\lim}(t)\) from a summation form to an integral form. \(\forall \tau\), \(\forall t \in [-\tau, 0]\) \[\begin{align} &\bar{z}^{\lim}(t) \\ =& \lim_{k \to \infty} \bar{z}(t(n_k)) -\sum_{i = m(t(n_k)+t)}^{n_k - 1} (\alpha(i)H(\bar{z}(t(i)),W_{i+1}), \beta(i)G(\bar{z}(t(i)),W_{i+1})) \\ =& \makebox[0.85\textwidth]{\displaystyle\lim_{k \to \infty} \bar{z}(t(n_k)) + \int_0^t (h (\bar{z}^{\lim}(s)),0)ds.\hfill(by Lemma \ref{cor-lemma:32double32limit322})} \label{cor-eq:32z32lim32definition322} \end{align}\tag{112}\] Thus, we can show the following diminishing discretization error.

Lemma 32. \(\forall \tau\), \(\forall t\in [-\tau, \tau],\) \[\begin{align} \lim_{k \to \infty} \norm{\bar{f}_{n_k}(t)} = 0. \end{align}\] Moreover, the convergence is uniform in \(t\) on \([-\tau,\tau]\).

Its proof is very similar to the proof of Lemma 46 and is omitted. This immediately implies that for any \(t \in (-\infty, \infty)\) \[\begin{align} \label{eq32corollary32ode32convergence} \lim_{k \to \infty} \bar{z}(t(n_k) + t) = z^{\lim}(t). \end{align}\tag{113}\] Theorem 1 then yields that \[\begin{align} \sup_{t \in (-\infty, \infty)} \norm{ z^{\lim}(t)} < \infty. \end{align}\]

Let \(Z\) be the set of limit points of \(\require{physics} \qty{z_n}\). By Theorem 1, \(\sup_n \norm{z_n} < \infty\), so \(Z\) is bounded and nonempty. We now prove \(Z\) is an invariant set of the ODE 100 . For any \(z \in Z\), there exists a subsequence \(\require{physics} \qty{z_{n_k}}\) such that \[\begin{align} \lim_{k\to\infty} z_{n_k} = z. \end{align}\] Since \(\require{physics} \qty{\bar z(t(n_k) + t)}\) is equicontinuous in the extended sense, following the way we arrive at 113 , we can construct a subsequence \(\require{physics} \qty{n'_k} \subseteq \qty{n_k}\) such that \[\begin{align} \label{eq:32z32n32k3932limit} \lim_{k\to\infty} \bar z(t(n_k') + t) = z_*^{\lim}(t), \end{align}\tag{114}\] where \(z_*^{\lim}(t)\) is a solution to the ODE 100 and \(z_*^{\lim}(0) = z\). The remaining is to show that \(z_*^{\lim}(t)\) lies entirely in \(Z\). For any \(t \in (-\infty, \infty)\), by the piecewise constant nature of \(\bar z\) in 103 , the above limit 114 implies that there exists a subsequence of \(\require{physics} \qty{z_n}\) that converges to \(z_*^{\lim}(t)\), indicating \(z_*^{\lim}(t) \in Z\) by the definition of the limit set. We now have proved \(\forall z \in Z\), there exists a solution \(z_*^{\lim}(t)\) to the ODE 100 such that \(z_*^{\lim}(0) = z\) and \(\forall t \in (-\infty, \infty), z_*^{\lim}(t) \in Z\). This means \(Z\) is an invariant set, by definition. In particular, \(Z\) is a bounded invariant set.

We now prove that \(\require{physics} \qty{z_n}\) converges to \(Z\). Let \(\require{physics} \qty{z_{n_k}}\) be any convergent subsequence of \(\require{physics} \qty{z_n}\) with its limit denoted by \(z\). We must have \(z \in Z\) by the definition of the limit set. So we have proved that all convergent subsequences of \(\require{physics} \qty{z_n}\) converge to a point in the bounded invariant set \(Z\). If \(\require{physics} \qty{z_n}\) does not converge to \(Z\), there must exist a subsequence \(\require{physics} \qty{z_{n_k'}}\) such that \(\require{physics} \qty{z_{n_k'}}\) is always away from \(Z\) by some small \(\epsilon_0 > 0\), i.e., \(\forall k\), \[\begin{align} \inf_{z\in Z} \norm{z_{n_k'} - z} \geq \epsilon_0. \label{eq:32z32n32k32epsilon320} \end{align}\tag{115}\] But \(\require{physics} \qty{z_{n_k'}}\) is bounded, so by the Bolzano-Weierstrass Theorem, it must have a convergent subsequence, which, by the definition of the limit set, converges to some point in \(Z\). This contradicts 115 . So we must have \(\require{physics} \qty{z_n}\) converge to \(Z\), which is a bounded invariant set of the ODE 100 . This completes the proof. ◻

Since the invariant set of (100 ) is \(\require{physics} \qty{(\lambda(y), y): y \in \mathbb{R}^{d_2}}\), we have \[\begin{align} \lim_{n \rightarrow \infty} \norm{x_n - \lambda(y_n)} = 0. \label{eq:32real32fast32convergence} \end{align}\tag{116}\] We will use this fact to now establish convergence to the unique equilibrium.

14.2 Slow Timescale Convergence↩︎

Returning to slow timescale definitions here.

Corollary 2. Let Assumptions 1 - 6 hold. Then the iterates \(\require{physics} \qty{y_n}\) generated by 1 converge almost surely to a (sample path dependent) bounded invariant set of the ODE \[\begin{align} \label{cor32eq32g32ode} \dv{y(t)}{t} &= g(\lambda(y(t)), y(t)) \end{align}\tag{117}\]

Proof. To prove convergence results on \(t \in(-\infty, \infty)\) in Corollary 2, we fix an arbitrary sample path \(\require{physics} \qty{z_0,\qty{W_i}_{i=1}^\infty}\). The stability results from Theorem 1 hold. To prove properties on \(t \in(-\infty, \infty)\), we first fix an arbitrary \(\tau > 0\) and show properties on \(\forall t \in [-\tau, \tau]\).

Definition 15. \(\forall n \in \mathbb{N}\), define \(\bar{y}_n(t)\) as the solution to the ODE 117 in \((-\infty, \infty)\) with an initial condition \[\begin{align} \bar{y}_n(0) = \bar{y}(t(n)). \label{cor-def:32slow32y32n32init} \end{align}\tag{118}\]

\(\bar{y}_n(t)\) can also be written as \[\begin{align} \bar{y}_n(t) &= \bar{y}(t(n)) + \int_0^t g(\lambda(\bar{y}_n(s)),\bar{y}_n(s))ds, \quad \forall t \in (-\infty, \infty). \label{cor-def:32slow32y32n32integral} \end{align}\tag{119}\]

We need to show that the error of Euler’s discretization diminishes asymptotically. With 44 and 45 , \(\forall \tau > 0\), \(\forall t \in [-\tau, \tau]\), \[\begin{align} \label{eq:32slow32bar32z32extend} &\bar{z}(t(n) + t) = z_{m(t(n) + t)} \\ &= \begin{cases} \bar{z}(t(n)) + \sum_{i = n}^{m(t(n)+t) - 1} (\alpha(i) H(\bar{z}(t(i)), W_{i+1}),\beta(i)G(\bar{z}(t(i)),W_{i+1})) & \text{if } t \geq 0 \\ \bar{z}(t(n)) - \sum_{i = m(t(n)+t)}^{n - 1} (\alpha(i) H(\bar{z}(t(i)), W_{i+1}),\beta(i)G(\bar{z}(t(i)),W_{i+1})) & \text{if } t < 0. \end{cases} \end{align}\tag{120}\] Notably, the property 44 that \(\forall t<0, m(t) = 0\) in 120 ensures \(\bar{z}(t(n) + t)\) is well-defined when \(t(n) + t < 0\). Precisely speaking, \(\forall \tau > 0\), \(\forall t \in [-\tau, \tau]\), the discretization error is defined as \[\begin{align} \bar{f}_n(t) \doteq \bar{y}(t(n) + t) - \bar{y}_n(t). \label{cor-def:32slow32f} \end{align}\tag{121}\] and we need \(\bar{f}_n(t)\) to diminish to 0 as \(n\to\infty\). To this end, we study the following three sequences of functions \[\require{physics} \begin{align} \label{cor-eq32slow32three32seq} \qty{ \bar y(t(n) + t)}_{n=0}^\infty, \qty{\bar{y}_n(t)}_{n=0}^\infty, \qty{\bar{f}_n(t)}_{n=0}^\infty. \end{align}\tag{122}\]

We show \(\require{physics} \qty{\bar{y}(t(n)+t)}\), \(\require{physics} \qty{\bar{y}_n(t)}\) and \(\require{physics} \qty{\bar{f}_n(t)}\) are all equicontinuous in the extended sense on the domain \((-\infty, \infty)\).

Lemma 33. The three sequences of functions \(\require{physics} \qty{\bar{y}(t(n)+t)}_{n = 0}^{\infty}\), \(\require{physics} \qty{\bar{y}_n(t)}_{n = 0}^{\infty}\), and \(\require{physics} \qty{\bar{f}_n(t)}_{n = 0}^{\infty}\) are all equicontinuous in the extended sense on \(t \in (-\infty, \infty)\).

To prove those lemmas, we need the Gronwall inequality in the reverse time in Appendix 6. Compared to lemmas in the main text which have the domain \(t \in [0,T+1)\), lemmas in this section have similar proofs because we first fix an arbitrary \(\tau\) and prove properties on the domain \(t \in [-\tau, \tau]\). We omit proofs for Lemma 33 because they are extremely similar to the proofs of equicontinuity in the slow timescale. Similar to Lemma 22, we now construct a particular subsequence of interest.

Lemma 34. There exists a subsequence \(\require{physics} \qty{n_k}_{k=0}^\infty \subseteq \qty{0, 1, 2, \dots}\) and some continuous functions \(\bar{f}^{\lim}(t)\) and \(\bar{y}^{\lim}(t)\) such that \(\forall \tau\), \(\forall t \in [-\tau, \tau]\), \[\begin{align} \lim_{k \to \infty} \bar{f}_{n_k}(t) =& \bar{f}^{\lim}(t) \tag{123} , \\ \lim_{k \to \infty} \bar{y}(t(n_k)+t) =& \bar{y}^{\lim}(t), \tag{124} \end{align}\] where both convergences are uniform in \(t\) on \([-\tau, \tau]\). Furthermore, let \(y^{\lim}(t)\) denote the unique solution to the ODE 117 with the initial condition \[\begin{align} y^{\lim}(0) = \bar{y}^{\lim}(0), \end{align}\] in other words, \[\begin{align} \label{cor-eq:32slow32y32lim32t} y^{\lim}(t) &= \bar{y}^{\lim}(0) + \int_0^t g(\lambda(\bar{y}^{\lim}), \bar{y}^{\lim}(s)) ds. \end{align}\tag{125}\] Then \(\forall \tau\), \(\forall t \in [-\tau, \tau]\), we have \[\begin{align} \lim_{k \to \infty} \bar{y}_{n_k}(t) = y^{\lim}(t), \label{cor-eq:32slow32y32lim32converge} \end{align}\tag{126}\] where the convergence is uniform in \(t\) on \([-\tau, \tau]\).

Its proof is very similar to the proof of Lemma 22 and is omitted. We use the subsequence \(\require{physics} \qty{n_k}\) intensively in the remaining proofs. Recall that \(\bar{f}_n(t)\) denotes the discretization error between \(\bar y(t(n) + t)\) and \(\bar{y}_n(t)\). We now proceed to prove that this discretization error diminishes along \(\require{physics} \qty{n_k}\). In particular, we aim to prove that \(\forall \tau\), \(\forall t \in [-\tau, \tau]\), \[\begin{align} \lim_{k \rightarrow \infty} \norm{\bar{f}_{n_k}(t)} = \norm{\bar{f}^{\lim}(t)} = 0. \end{align}\] This means \(\bar{y}(t(n_k) + t)\) is close to \(\bar{y}_{n_k}(t)\) as \(k \rightarrow \infty\). For \(t \in (0,\tau]\), the proof for this part is the same as the proof we have done in Section 13.4. Thus, we only discuss the proof for \(t \in [-\tau, 0]\). \(\forall \tau\), \(\forall t \in [-\tau, 0]\), \[\begin{align} &\lim_{k \rightarrow \infty} \norm{ \bar{f}_{n_k}(t)} \\ =& \lim_{k \rightarrow \infty} \norm{ \bar{y}(t(n_k)) -\sum_{i = m(t(n_k)+t)}^{n_k - 1} \beta(i)G(\bar{z}(t(i)),W_{i+1}) - \bar{y}_{n_k}(t)} \tag*{(by \eqref{eq:32slow32bar32z32extend} and \eqref{cor-def:32slow32f})}\\ =& \lim_{k \rightarrow \infty} \norm{ -\sum_{i = m(t(n_k)+t)}^{n_k - 1} \beta(i)G(\bar{z}(t(i)),W_{i+1}) - \int_0^t g(\lambda(\bar{y}_{n_k}),\bar{y}_{n_k})ds} \tag*{(by \eqref{cor-def:32slow32y32n32integral})}\\ \leq&\lim_{k \to \infty} \norm{ -\sum_{i = m(t(n_k)+t)}^{n_k - 1} \beta(i)G(\bar{z}(t(i)),W_{i+1}) + \sum_{i = m(t(n_k)+t)}^{n_k - 1} \beta(i)G(\lambda(\bar{y}(t(i))), \bar{y}(t(i)),W_{i+1}) } \\ &+ \lim_{k \to \infty} \norm{- \sum_{i = m(t(n_k)+t)}^{n_k - 1} \beta(i)G(\lambda(\bar{y}(t(i))), \bar{y}(t(i)),W_{i+1}) - \int_0^t g(\lambda(\bar{y}_{n_k}),\bar{y}_{n_k})ds } . \label{cor-eq:32slow32lim32f32k} \\ \end{align}\tag{127}\]

The first term in the RHS of 127 is 0.

Lemma 35. \(\forall \tau\), \(\forall t \in [-\tau, 0]\), \[\begin{align} \lim_{k \to \infty} \norm{ -\sum_{i = m(t(n_k)+t)}^{n_k - 1} \beta(i)G(\bar{z}(t(i)),W_{i+1}) + \sum_{i = m(t(n_k)+t)}^{n_k - 1} \beta(i)G(\lambda(\bar{y}(t(i))), \bar{y}(t(i)),W_{i+1}) } =0. \end{align}\]

Its proof is very similar to the proof of Lemma 24 (except that we use 116 instead of Lemma 23) and is omitted. This convergence is also simpler than 148 because here we have only a single \((G, g)\).

Lemma 36. \(\forall \tau\), \(\forall t\in [-\tau, \tau],\) \[\begin{align} \lim_{k \to \infty} \norm{\bar{f}_{n_k}(t)} = 0. \end{align}\] Moreover, the convergence is uniform in \(t\) on \([-\tau,\tau]\).

Its proof is very similar to the proof of the diminishing discretization error in the slow timescale. This immediately implies that for any \(t \in (-\infty, \infty)\) \[\begin{align} \label{eq32corollary32slow32ode32convergence} \lim_{k \to \infty} \bar{z}(t(n_k) + t) = (\lambda(y^{\lim}(t)), y^{\lim}(t)). \end{align}\tag{128}\] Theorem 1 then yields that \[\begin{align} \sup_{t \in (-\infty, \infty)} \norm{ (\lambda(y^{\lim}(t)), y^{\lim}(t))} < \infty. \end{align}\]

Let \(Y\) be the set of limit points of \(\require{physics} \qty{y_n}\). By Theorem 1, \(\sup_n \norm{y_n} < \infty\), so \(Y\) is bounded and nonempty. We now prove \(Y\) is an invariant set of the ODE 117 . For any \(y \in Y\), there exists a subsequence \(\require{physics} \qty{y_{n_k}}\) such that \[\begin{align} \lim_{k\to\infty} y_{n_k} = y. \end{align}\] Since \(\require{physics} \qty{\bar y(t(n_k) + t)}\) is equicontinuous in the extended sense, following the way we arrive at 128 , we can construct a subsequence \(\require{physics} \qty{n'_k} \subseteq \qty{n_k}\) such that \[\begin{align} \label{eq:32slow32y32n32k3932limit} \lim_{k\to\infty} \bar y(t(n_k') + t) = y_*^{\lim}(t), \end{align}\tag{129}\] where \(y_*^{\lim}(t)\) is a solution to the ODE 117 and \(y_*^{\lim}(0) = y\). The remaining is to show that \(y_*^{\lim}(t)\) lies entirely in \(Y\). For any \(t \in (-\infty, \infty)\), by the piecewise constant nature of \(\bar y\) in 120 , the above limit 129 implies that there exists a subsequence of \(\require{physics} \qty{y_n}\) that converges to \(y_*^{\lim}(t)\), indicating \(y_*^{\lim}(t) \in Y\) by the definition of the limit set. We now have proved \(\forall y \in Y\), there exists a solution \(y_*^{\lim}(t)\) to the ODE 117 such that \(y_*^{\lim}(0) = y\) and \(\forall t \in (-\infty, \infty), y_*^{\lim}(t) \in Y\). This means \(Y\) is an invariant set, by definition. Additionally, \(Y\) is a bounded invariant set.

We now prove that \(\require{physics} \qty{y_n}\) converges to \(Y\). Let \(\require{physics} \qty{y_{n_k}}\) be any convergent subsequence of \(\require{physics} \qty{y_n}\) with its limit denoted by \(y\). We must have \(y \in Y\) by the definition of the limit set. So we have proved that all convergent subsequences of \(\require{physics} \qty{y_n}\) converge to a point in the bounded invariant set \(Y\). If \(\require{physics} \qty{y_n}\) does not converge to \(Y\), there must exist a subsequence \(\require{physics} \qty{y_{n_k'}}\) such that \(\require{physics} \qty{y_{n_k'}}\) is always away from \(Y\) by some small \(\epsilon_0 > 0\), i.e., \(\forall k\), \[\begin{align} \inf_{y\in Y} \norm{y_{n_k'} - y} \geq \epsilon_0. \label{eq:32slow32y32n32k32epsilon320} \end{align}\tag{130}\] But \(\require{physics} \qty{y_{n_k'}}\) is bounded, so by the Bolzano-Weierstrass Theorem, it must have a convergent subsequence, which, by the definition of the limit set, converges to some point in \(Y\). This contradicts 130 . So we must have \(\require{physics} \qty{y_n}\) converge to \(Y\), which is a bounded invariant set of the ODE 117 . This completes the proof. ◻

Since the invariant set of (117 ) is the singleton containing \(y^*\), the equilibrium of the ODE, we have \[\begin{align} \lim_{n \rightarrow \infty} \norm{y_n - y^*} = 0. \label{eq:32real32slow32convergence} \end{align}\tag{131}\] Combined with the fast convergence, we have \[\begin{align} \lim_{n \rightarrow \infty} \norm{z_n - (\lambda(y^*), y^*)} = 0. \label{eq:32final32convergence} \end{align}\tag{132}\]

15 Convergence of TDC with Eligibility Traces↩︎

TDC was first proposed in [34] as a modification of gradient temporal difference learning (GTD) [34]. GTD was developed to break the deadly triad, divergence that can arise when combining off-policy learning, function approximation, and bootstrapping, each of which are critical components in successful RL algorithms. While GTD mitigates the deadly triad, it is slow. TDC, on the other hand, is nearly as fast as regular TD learning and converges. It is also a two-timescale algorithm, as the gradient correction runs on a faster timescale. Although vanilla TDC is known to converge, the best prior work was only able to establish the convergence of projected variants of TDC with eligibility traces [18].

We must also explain the important of eligibility traces: they are a powerful tool for credit assignment, a critical challenge in RL, and have been a fundamental part of RL since the inception of the field [35]. Although eligibility traces are useful, they introduce difficulties in analysis. Even if the state space of the Markov chain \(\require{physics} \qty{(S_t, A_t)}\) is finite, with eligibility traces, we have to instead consider the chain \(\require{physics} \qty{(S_t, A_t, e_t)}\), which now evolves in an uncountable space. And, in the case of off-policy learning, the importance sampling ratio can cause the state space to be unbounded as well. Our results, therefore, are the first to be able to handle the important case of off-policy RL algorithms with eligibility traces. We demonstrate this with TDC.

Assumption 1. Both the state space \(\mathcal{S}\) and the action space \(\mathcal{A}\) are finite. The Markov chain \(\require{physics} \qty{S_t}\) induced by the behavior policy \(\mu\) is irreducible, and \(\mu(a|s) > 0\) for all \(s,a\).

Assumption 2. The feature matrix \(\Phi\) is of full rank.

Assumption 2 is standard in RL with linear function approximations to guarantee existence and uniqueness of the solution. Additionally, any feature matrix that is not full rank can be converted into one that is by finding a linearly independent basis for the space spanned by the column vectors, so in practice, this is a very weak assumption [59].

TDC with eligibility traces is defined as follows: \[\begin{align} \label{eq32gtd} e_t =& \lambda \gamma \rho_{t-1} e_{t-1} + \phi_t, \\ \delta_t =& R_{t+1} + \gamma \phi_{t+1}^\top \theta_t - \phi_t^\top \theta_t, \\ \nu_{t+1} =& \nu_t + \alpha_t \left(\rho_t \delta_t e_t - \phi_t \phi_t^\top \nu_t\right), \\ \theta_{t+1} =& \theta_t + \beta_t(\rho_t \delta_t e_t - \rho_t(1-\lambda)\gamma \phi_{t+1} e_t^\top \nu_t). \end{align}\tag{133}\]

We can more compactly express the updates with the following equations:

\[\begin{align} \nu_{t+1} &= \nu_t + \alpha_t \left(\mqty[-\phi_t\phi_t^\top & \rho_t e_t(\gamma \phi_{t+1} - \phi_t)^\top] \mqty[\nu_{t} \\ \theta_{t}] + \mqty[\rho_t R_{t+1} e_t]\right) \\ \theta_{t+1} &= \theta_t + \beta_t \left(\mqty[ -\rho_t(1-\lambda)\gamma \phi_{t+1} e_t^{\top} & \rho_t e_t(\gamma \phi_{t+1} - \phi_t)^\top]\mqty[\nu_{t} \\ \theta_{t}] + \mqty[\rho_t R_{t+1} e_t]\right ). \end{align}\]

Now we define the augmented Markov chain \(\require{physics} \qty{W_t}\) as \[\begin{align} W_{t+1} \doteq (S_t, A_t, S_{t+1}, e_t), \quad t=0,1,\dots. \end{align}\] We also define shorthands \[\begin{align} x \doteq& \nu, x_t \doteq \nu_t, y \doteq \theta, y_t \doteq \theta_t \\ w \doteq& (s, a, s', e), \\ A(w) \doteq& \rho(s, a) e (\gamma \phi(s') - \phi(s))^\top, \tag{134}\\ b(w) \doteq& \rho(s, a) r(s, a) e, \tag{135}\\ C(w) \doteq& \phi(s) \phi(s)^\top, \tag{136}\\ D(w) \doteq& e\rho(s,a)(1-\lambda)\gamma \phi(s')^{\top}, \tag{137} \\ H(x, y, w) \doteq& \mqty[-C(w) & A(w) ] \mqty[x \\ y] + b(w), \\ G(x, y, w) \doteq& \mqty[ -D^\top(w) & A(w)] \mqty[x \\ y] + b(w). \\ \end{align}\]

Then TDC can be expressed as \[\begin{align} \label{eq:32TDC32update} x_{t+1} &= x_t + \alpha_t H(x_t, y_t, W_{t+1}), \\ y_{t+1} &= y_t + \beta_t G(x_t, y_t, W_{t+1}), \end{align}\tag{138}\] which reduces to the form of 1 and 2 .

Lemma 37. (Theorem 2.1 from [18]) If Assumption 1 holds, then

(i) \(\require{physics} \qty{W_t}\) has a unique invariant probability measure, \(d_{\mathcal{W}}\).

(ii) The expectation with respect to the stationary distribution, \(\mathbb{E}_{w \sim d_{\mathcal{W}}}[\gamma(w)] < \infty\) when \(\gamma(w)\) is a function which is Lipschitz in the trace variable \(e\). Additionally, 37 holds for \(\gamma\).

[18] also shows that \[\begin{align} A \doteq& \mathbb{E}_{w\sim{d_\mathcal{W}}}\left[ A(w)\right] = \Phi^\top D_\mu ( P_{\pi, \lambda} - I) \Phi, \\ b \doteq& \mathbb{E}_{w\sim{d_\mathcal{W}}}\left[ b(w)\right] = \Phi^\top D_\mu r_{\pi, \lambda}, \\ C \doteq& \mathbb{E}_{w\sim{d_\mathcal{W}}}\left[ C(w)\right] = \Phi^\top D_\mu \Phi, \\ D \doteq& \mathbb{E}_{w\sim{d_\mathcal{W}}}\left[ D(w)\right] = \Phi^\top D_\mu P_{\pi,\lambda} \Phi, \end{align}\] where we use \(D_\mu\) to denote the diagonal matrix whose diagonal entry is \(d_\mu\), the invariant distribution of the underlying Markov chain \(\require{physics} \qty{S_t}\).

Theorem 3 (Theorem 3 Restated). Assume \(A\) is invertible (without this assumption, there is no solution so the algorithm itself would be ill-posed as the solution point involves \(A^{-1}\)). Then, TDC with eligibility traces converges.

Proof. We show that all the assumptions are satisfied such that Theorem 2 applies.

Assumption 1 follows immediately from Lemma 37.

The assumption 2 follows immediately from the choice of appropriate learning rates.

For Assumption 3, define \[\begin{align} H_\infty(x, y, w) \doteq& \mqty[-C(w) & A(w)] \mqty[x \\ y], \\ G_\infty(x, y, w) \doteq& \mqty[-D^\top(w) & A(w)] \mqty[x \\ y]. \end{align}\] Then we have \[\begin{align} H_c(x, y, w) - H_\infty(x, y, w) =\frac{b(w)}{c} , \\ G_c(x, y, w) - G_{\infty}(x, y, w) = \frac{b(w)}{c} \end{align}\] After noticing \[\begin{align} \norm{b((s, a, s', e)) - b((s, a, s', e'))} = \rho(s, a) \abs{r(s, a)} \norm{e - e'}, \quad \forall s, a, s', e, e', \end{align}\] Assumption 3 follows immediately from Lemma 37.

For Assumption 4, it can be easily verified that \(H(x, y, w), G(x, y, w), H_\infty(x, y, w),\) and \(G_\infty(x, y, w)\) are Lipschitz continuous in \((x,y)\) for each \(w\), with the Lipschitz constant being \[\require{physics} \begin{align} L(w) =& \max \qty{\norm{\mqty[-C(w) & A(w) ]},\norm{\mqty[-D^\top(w) & A(w) ]}} \end{align}\]

Since \(A(w), b(w), C(w), D(w)\) are Lipschitz continuous in \(e\) for each \((s, a, s')\), Lemma 37 implies that \[\require{physics} \begin{align} h(x, y) =& \mqty[-C & A ] \mqty[x \\ y] + b, \\ h_\infty(x, y) =& \mqty[-C & A ] \mqty[x \\ y], \\ g(x, y) =& \mqty[-D^\top & A ] \mqty[x \\ y] + b \\ g_\infty(x, y) =& \mqty[-D^\top & A ] \mqty[x \\ y], \\ L =& \max \qty{\norm{\mqty[-C & A ]},\norm{\mqty[-D^\top & A ]}} . \end{align}\] Assumption 4 then follows.

For Assumption 5, we have \[\begin{align} \norm{h_c(x, y) - h_\infty(x, y)} =& \frac{1}{c}\norm{b}, \\ \norm{g_c(x, y) - g_\infty(x, y)} =& \frac{1}{c}\norm{b}, \end{align}\] so the uniform convergence of \(h_c\) to \(h_\infty\) and \(g_c\) to \(g_\infty\) follow immediately.

Since \(\Phi\) has full column rank and \(D_{\mu}\) is positive definite (due to irreducibility of \(\require{physics} \qty{S_t}\)), \(C=\Phi^\top D_{\mu} \Phi\) is positive definite, so \(-C\) is negative definite. This implies the global asymptotic stability of these two ODEs: \[\begin{align} \dv{x(t)}{t} = h(x(t),y) = -Cx(t) +Ay+ b, \quad \dv{x(t)}{t} = h_{\infty}(x(t),y)= -C x(t) + Ay. \end{align}\] The unique globally asymptotically stable equilibrium of the first is \(C^{-1}(Ay+b)\), and of the second is \(C^{-1}Ay\). This means that we can define \(\lambda(y) = C^{-1}(Ay+b)\) and \(\lambda_{\infty}(y) = C^{-1}Ay\). Note that \(\lambda_{\infty}(cy) = c\lambda_{\infty}(y)\) as required.

Now we will analyze two ODEs: \[\begin{align} \dv{y(t)}{t} =& g(\lambda(y(t)), y(t)) \\ =& -D^\top \lambda(y(t))+Ay(t)+b\\ =& -D^\top (C^{-1}(Ay(t)+b))+Ay(t)+b \\ =& (I-D^\top C^{-1})(Ay(t)+b) \\ =& (I-(A^\top + C)C^{-1})(Ay(t)+b) \tag*{(by A+C=D, C=C^\top)} \\ =& -A^\top C^{-1} (Ay(t)+b), \end{align}\]

\[\begin{align} \dv{y(t)}{t} =& g_{\infty}(\lambda_{\infty}(y(t)), y(t)) \\ =& -D^\top \lambda_{\infty}(y(t))+Ay(t)\\ =& -D^\top C^{-1} Ay(t)+Ay(t) \\ =& (I-D^\top C^{-1})Ay(t) \\ =& (I-(A^\top + C)C^{-1})Ay(t) \tag*{(by A+C=D, C=C^\top)} \\ =& -A^\top C^{-1} Ay(t), \end{align}\]

Since \(A\) is nonsingular and \(C\) is positive definite, \(-A^\top C^{-1} A\) is negative definite. This implies the global asymptotic stability of the previous two ODEs. The unique globally asymptotically stable equilibrium of the first is \(-A^{-1}b\), and of the second is \(0\). Assumption 5 then follows.

Assumption 6 follows immediately from Lemma 37 and Assumption 2.

Theorem 2 then implies that \[\begin{align} \lim_{t\to\infty} x_t &= 0 \qq{a.s.} \\ \lim_{t\to\infty} y_t &= -A^{-1}b \qq{a.s.} \end{align}\] which completes the proof. ◻

16 Technical Lemmas↩︎

16.1 Asymptotic Rate of Change of Functions in Assumption 6↩︎

Lemma 38. Let Assumptions 12, 4, and 6 hold. Then the asymptotic rate of change of the functions that could be represented by \(\gamma\) in Assumption 6 is 0, i.e., for any fixed \(\tau > 0\) and \(x\), it holds that \[\begin{align} \limsup_n \sup_{-\tau \leq t_1 \leq t_2 \leq \tau} \norm{ \sum_{i = m(t(n) + t_1)}^{m(t(n) + t_2) - 1} \alpha(i) \left[H(x, y, W_{i+1}) - h(x, y) \right] } & = 0 \quad a.s., \tag{139}\\ \limsup_n \sup_{-\tau \leq t_1 \leq t_2 \leq \tau} \norm{ \sum_{i = m(t(n) + t_1)}^{m(t(n) + t_2) - 1} \alpha(i) \left[G(x, y, W_{i+1}) - g(x, y) \right] } & = 0 \quad a.s., \tag{140}\\ \limsup_n \sup_{-\tau \leq t_1 \leq t_2 \leq \tau} \norm{\sum_{i = m(t(n) + t_1)}^{m(t(n) + t_2) - 1} \alpha(i) [L_b(W_{i+1}) - L_b] } &= 0 \quad a.s., \tag{141}\\ \limsup_n \sup_{-\tau \leq t_1 \leq t_2 \leq \tau} \norm{\sum_{i = m(t(n) + t_1)}^{m(t(n) + t_2) - 1} \alpha(i) [L(W_{i+1}) - L] } &= 0 \quad a.s. \tag{142} \end{align}\] and we can replace \(\alpha(i)\) with \(\beta(i)\) in any of the above.

The proofs of these results are very similar to the proof of Lemma 9 in [13] and so are omitted due to their length.

16.2 A Uniform Convergence of \(H_c, G_c\) to \(H_{\infty}, G_{\infty}\)↩︎

Lemma 39. Let Assumptions 12, 4, and 6 hold. It then holds that \[\begin{align} &\lim_{c \to \infty} \sup_{z \in \mathcal{B}} \sup_n \sup_{t \in [0,T]} \norm{ \sum_{i=m(T_n)}^{m(T_n+t) - 1} \alpha(i) \left[H_c(z, W_{i+1}) - H_\infty(z, W_{i+1}) \right] } = 0 \qq{a.s.,} \\ &\lim_{c \to \infty} \sup_{z \in \mathcal{B}} \sup_n \sup_{t \in [0,T]} \norm{ \sum_{i=m(T_n)}^{m(T_n+t) - 1} \alpha(i) \left[G_c(z, W_{i+1}) - G_\infty(z, W_{i+1}) \right] } = 0 \qq{a.s.,} \end{align}\] where \(\mathcal{B}\) denotes an arbitrary compact set of \(\mathbb{R}^{d_1+d_2}\). Again, \(\alpha(i)\) can be replaced with \(\beta(i)\).

Proof. Fix an arbitrary sample path \(\require{physics} \qty{x_0,y_0, \qty{W_i}_{i=1}^\infty}\). Use \(\mathcal{B}\) to denote an arbitrary compact subset of \(\mathbb{R}^{d_1+d_2}\). \[\begin{align} &\lim_{c \to \infty} \sup_{z \in \mathcal{B}} \sup_n \sup_{t \in [0,T]} \norm{ \sum_{i=m(T_n)}^{m(T_n+t) - 1} \alpha(i) \left[H_c(z, W_{i+1}) - H_\infty(z, W_{i+1}) \right] } \\ =&\lim_{c \to \infty} \sup_{z \in \mathcal{B}} \sup_n \sup_{t \in [0,T]} \norm{\sum_{i=m(T_n)}^{m(T_n+t) - 1} \alpha(i) \kappa(c) b(z, W_{i+1})} \tag*{(by \eqref{eq:32H32c32H32inf32kappa})} \\ =&\lim_{c \to \infty} \kappa(c) \sup_{z \in \mathcal{B}} \sup_n\sup_{t \in [0,T]} \norm{\sum_{i=m(T_n)}^{m(T_n+t) - 1} \alpha(i) b(z,W_{i+1})} \\ =& 0 \sup_{z \in \mathcal{B}} \sup_n \sup_{t \in [0,T]} \norm{\sum_{i=m(T_n)}^{m(T_n+t) - 1} \alpha(i) b(z, W_{i+1})} \label{eq:32H32c32H32inf32032finite} \end{align}\tag{143}\] We now show that the function \[\begin{align} \label{eq32a32function32of32x} z \mapsto \sup_n \sup_{t \in [0,T]} \norm{\sum_{i=m(T_n)}^{m(T_n+t) - 1} \alpha(i) b(z, W_{i+1})} \end{align}\tag{144}\] is Lipschitz continuous. \(\forall z, z'\),

\[\begin{align} &\abs{\sup_n \sup_{t \in [0,T]} \norm{\sum_{i=m(T_n)}^{m(T_n+t) - 1} \alpha(i) b(z, W_{i+1})} - \sup_n \sup_{t \in [0,T]} \norm{\sum_{i=m(T_n)}^{m(T_n+t) - 1} \alpha(i) b(z', W_{i+1})}} \\ \leq&\sup_n \sup_{t \in [0,T]} \abs{\norm{\sum_{i=m(T_n)}^{m(T_n+t) - 1} \alpha(i) b(z, W_{i+1})} - \norm{\sum_{i=m(T_n)}^{m(T_n+t) - 1} \alpha(i) b(z', W_{i+1})}} \tag*{(by \abs{\sup_z f(z) - \sup_z g(z)} \leq \sup_z \abs{f(z) - g(z)} )} \\ \leq&\sup_n \sup_{t \in [0,T]} \norm{\sum_{i=m(T_n)}^{m(T_n+t) - 1} \alpha(i) b(z, W_{i+1}) - \sum_{i=m(T_n)}^{m(T_n+t) - 1} \alpha(i) b(z', W_{i+1})} \\ \leq&\sup_n \sup_{t \in [0,T]} \sum_{i=m(T_n)}^{m(T_n+t) - 1} \alpha(i) \norm{ b(z, W_{i+1}) - b(z', W_{i+1})} \\ \leq& \sup_n \sup_{t \in [0,T]} \left(\sum_{i=m(T_n)}^{m(T_n+t) - 1} \alpha(i) L_b(W_{i+1})\right) \norm{z - z'} \end{align}\] By Lemma 38 and 180 , \[\begin{align} \sup_n \sup_{t \in [0,T]} \left(\sum_{i=m(T_n)}^{m(T_n+t) - 1} \alpha(i) L_b(W_{i+1})\right) < \infty \end{align}\] can be viewed as the Lipschitz constant. Thus, 144 is a continuous function. Since \(\mathcal{B}\) is compact, the extreme value theorems asserts that the supremum of 144 in \(\mathcal{B}\) is attainable at some \(z_{\mathcal{B}}\) and is finite. This means the RHS of 143 is 0, so

\[\begin{align} &\lim_{c \to \infty} \sup_{z \in \mathcal{B}} \sup_n \sup_{t \in [0,T]} \norm{ \sum_{i=m(T_n)}^{m(T_n+t) - 1} \alpha(i) \left[H_c(z, W_{i+1}) - H_\infty(z, W_{i+1}) \right] } = 0. \label{eq:32b32e32b320} \end{align}\tag{145}\] The proofs for the other statements follow similar arguments and so are omitted. ◻

16.3 Definitions and Proofs Relating to Equicontinuity↩︎

Definition 16. A sequence of functions \(\require{physics} \qty{\gamma_n: [0, T) \to \mathbb{R}^K }\) is equicontinuous on \([0, T)\) if
\(\sup_n \norm{\gamma_n(0)} < \infty\) and \(\forall \epsilon > 0\), \(\exists \delta > 0\) such that \[\begin{align} \sup_n \sup_{0\leq \abs{t_1-t_2} \leq \delta, \, 0 \leq t_1 \leq t_2 < T} \norm{\gamma_n(t_1) - \gamma_n(t_2)} \leq \epsilon. \end{align}\]

A standard example of a family of equicontinuous functions is a sequence of bounded Lipschitz continuous functions with a common Lipschitz constant. Clearly, if \(\require{physics} \qty{\gamma_n}\) is equicontinuous, each \(\gamma_n\) must be continuous. However, the functions of interest in this work, i.e., \(\tilde{z}_n(t), f_n(t)\), are not continuous, so equicontinuity cannot apply. We, therefore, define the following equicontinuity in the extended sense.

Definition 17. A sequence of functions \(\require{physics} \qty{\gamma_n: [0, T) \to \mathbb{R}^K }\) is equicontinuous in the extended sense on \([0, T)\) if \(\sup_n \norm{\gamma_n(0)} < \infty\) and \(\forall \epsilon > 0\), \(\exists \delta > 0\) such that \[\begin{align} \limsup_n \sup_{0\leq \abs{t_1-t_2} \leq \delta, \, 0 \leq t_1 \leq t_2 < T } \norm{\gamma_n(t_1) - \gamma_n(t_2)} \leq \epsilon. \end{align}\]

The following lemmas establish the desired equicontinuity, where Lemma 38 plays a key role.

Lemma 40. \(\require{physics} \qty{\tilde{z}_n(t)}_{n=0}^\infty\) is equicontinuous in the extended sense on \([0, T+1)\).

Proof. By 47 , \[\begin{align} \sup_n \norm{\tilde{z}_n(0)} \leq 1 . \end{align}\]

Without loss of generality, let \(t_1 \leq t_2\). \[\begin{align} &\limsup_n \sup_{ 0\leq t_2-t_1 \leq \delta } \norm{ \tilde{z}_n(t_1) - \tilde{z}_n(t_2)} \\ =& \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} (\alpha(i) H_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1}), \beta(i) G_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1})) }\\ \leq& \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) H_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1})} \\ &+ \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \beta(i) G_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1})}. \end{align}\]

We bound each term individually. We start with the first term.

\(\forall \xi > 0\), by 172 , \(\exists \delta_0,\) such that \(\forall 0< \delta \leq \delta_0\), \[\begin{align} \sup_{c\geq 1} \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{ \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) H_c(0, W_{i+1}) } \leq \xi. \label{eq:32lemma32hat32x32equicontinuous32xi321} \end{align}\tag{146}\] By 179 , \(\exists \delta_1,\) such that \(\forall 0< \delta \leq \delta_1\), \[\begin{align} \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) L(W_{i+1}) \leq \xi. \label{eq:32lemma32hat32x32equicontinuous32xi322} \end{align}\tag{147}\] Without loss of generality, let \(t_1 \leq t_2\). Then \(\require{physics} \forall \delta \leq \min \qty{\delta_0,\delta_1}\), we have \[\begin{align} &\limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) H_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1}) }\\ \leq& \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) H_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1}) } - \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) H_{r_n}(0, W_{i+1}) } \\ &+ \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) H_{r_n}(0, W_{i+1}) } \\ \leq& \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) H_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1}) } - \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) H_{r_n}(0, W_{i+1}) } \\ &+ \sup_{c\geq 1} \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) H_c(0, W_{i+1}) } \\ \leq& \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) H_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1}) } - \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) H_{r_n}(0, W_{i+1}) } \\ &+ \xi \tag*{(by \eqref{eq:32lemma32hat32x32equicontinuous32xi321})}\\ \leq& \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) H_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1}) - \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) H_{r_n}(0, W_{i+1}) } \\ &+ \xi \\ \leq& \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) \norm{H_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1}) - H_{r_n}(0, W_{i+1}) } + \xi\\ \leq& \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) L(W_{i+1})\norm{\tilde{z}_n(t(i)-T_n)} + \xi \\ \leq& (C_{\hat{x}}+C_{\hat{y}}) \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) L(W_{i+1}) + \xi \tag*{(by Lemma~\ref{lemma:32bound32z32hat})} \\ \leq& (C_{\hat{x}}+C_{\hat{y}}) \xi + \xi. \tag*{(by \eqref{eq:32lemma32hat32x32equicontinuous32xi322})} \end{align}\] A similar argument bounds the other term, implying that \(\require{physics} \qty{\tilde{z}_n(t)}\) is equicontinuous in the extended sense. ◻

Lemma 41. \(\require{physics} \qty{z_n(t)}\) is equicontinuous on \([0, T+1)\).

Proof. By 47 and 50 , \[\begin{align} \sup_n \norm{z_n(0)} \leq 1. \end{align}\] Without loss of generality, let \(t_1 \leq t_2\). Then \(\forall \delta > 0\), we have \[\begin{align} & \sup_n \sup_{0\leq \abs{t_1-t_2} \leq \delta, \, 0 \leq t_1 \leq t_2 < T} \norm{z_n(t_1) - z_n(t_2)} \\ =&\sup_n \sup_{0\leq \abs{t_1-t_2} \leq \delta, \, 0 \leq t_1 \leq t_2 < T} \norm{ \int_{t_1}^{t_2} h_{r_n}(z_n(s))ds }\\ =& \sup_n \sup_{0\leq \abs{t_1-t_2} \leq \delta, \, 0 \leq t_1 \leq t_2 < T} \norm{\int_{t_1}^{t_2} \left[ h_{r_n}(z_n(s)) - h_{r_n}(0) \right]ds + \int_{t_1}^{t_2} h_{r_n}(0) ds }& \\ \leq &\sup_n \sup_{0\leq \abs{t_1-t_2} \leq \delta, \, 0 \leq t_1 \leq t_2 < T} \int_{t_1}^{t_2}\norm{h_{r_n}(z_n(s)) - h_{r_n}(0) }ds + \sup_n \sup_{0\leq \abs{t_1-t_2} \leq \delta, \, 0 \leq t_1 \leq t_2 < T} \int_{t_1}^{t_2} \norm{ h_{r_n}(0) }ds & \\ \leq & \sup_n \sup_{0\leq \abs{t_1-t_2} \leq \delta, \, 0 \leq t_1 \leq t_2 < T} \int_{t_1}^{t_2}L\norm{z_n(s)} ds + \sup_n \sup_{0\leq \abs{t_1-t_2} \leq \delta, \, 0 \leq t_1 \leq t_2 < T} \int_{t_1}^{t_2} \norm{ h_{r_n}(0) }ds& \tag*{(by Lemma \ref{lemma:32h32Lipschitz})} \\ \leq & \delta LC_{\hat{x}} + \sup_n \sup_{0\leq \abs{t_1-t_2} \leq \delta, \, 0 \leq t_1 \leq t_2 < T} \int_{t_1}^{t_2} \norm{ h_{r_n}(0) }ds& \tag*{(by Lemma~\ref{lemma:32bound32z})} \\ \leq & \delta (L C_{\hat{x}} + C_H),& \tag*{(by \eqref{eq:32h32c32c95H})} \end{align}\] which implies that \(\require{physics} \qty{z_n}\) is equicontinuous. ◻

Lemma 42. \(\require{physics} \qty{f_n(t)}\) is equicontinuous in the extended sense on \([0, T+1)\).

Proof. \[\begin{align} \sup_n f_n(0) = \sup_n \tilde{z}_n(0) - z_n(0) = \sup_n \tilde{z}_n(0) - \tilde{z}_n(0) = 0 < \infty. \end{align}\] By Lemma 40 and Lemma 41, \(\forall \epsilon > 0\), \(\exists \delta\) such that \[\begin{align} \limsup_n \sup_{0\leq t_2-t_1 \leq \delta} \norm{\tilde{z}_n(t_1) - \tilde{z}_n(t_2)} & \leq \frac{\epsilon}{2},\\ \sup_n \sup_{0\leq t_2-t_1 \leq \delta} \norm{ z_n(t_1) - z_n(t_2)} &\leq \frac{\epsilon}{2}. \end{align}\] Without loss of generality let \(t_1 \leq t_2\). Then \(\forall \epsilon\), \(\exists \delta\) such that \[\begin{align} &\limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{f_n(t_1) - f_n(t_2)} \\ =&\limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{\tilde{z}_n(t_1) - \tilde{z}_n(t_2) - (z_n(t_1) - z_n(t_2))} \\ \leq& \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{\tilde{z}_n(t_1) - \tilde{z}_n(t_2)} + \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{ z_n(t_1) - z_n(t_2)} \\ \leq& \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{\tilde{z}_n(t_1) - \tilde{z}_n(t_2)} + \sup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{ z_n(t_1) - z_n(t_2)} \\ \leq& \epsilon, \end{align}\] which implies that \(\require{physics} \qty{f_n}\) is equicontinuous in the extended sense. ◻

16.4 Proof of Lemma 2↩︎

Proof. Since \(\sup_n r_n = \infty\) and \(r_n\) is monotonic, \(\lim_{n \rightarrow \infty} r_n = \infty\), and every subsequence also converges to infinity.

Since \(\{f_{n_{k,0}}\}\) is equicontinuous, by the Arzelà-Ascoli theorem (see Appendix 8), there exists a subsequence \(n_{k,1} \subseteq n_{k,0}\) such that \(\{f_{n_{k,1}}\}\) converges uniformly to a continuous limit \(f^{\text{lim}}\). Similarly, since \(\require{physics} \qty{\tilde{z}_{n_{k,1}}(t)}\) is equicontinuous, there is a subsequence \(n_k \subseteq n_{k,1}\) such that \(\require{physics} \qty{\tilde{z}_{n_k}(t)}\) converges uniformly in \(t\) to a continuous limit \(\tilde{z}^{\text{lim}}(t)\).

The proof that \(\lim_{n \rightarrow \infty} z_{n_k}(t) = z^{\text{lim}}(t)\) uniformly is by lemma 57. ◻

16.5 Proof of Lemma 12↩︎

Proof. \[\begin{align} &\lim_{k \to \infty} \norm{ \sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \beta(i)G_{r_{n_k}}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1})} \\ \leq& \lim_{k \to \infty} \sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \beta(i)\norm{G_{r_{n_k}}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1})} \\ \leq& \lim_{k \to \infty} \sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \beta(i)L(W_{i+1})\norm{\tilde{z}_{n_k}(t(i)-T_{n_k})} \\ \leq& C_{\hat{z}} \lim_{k \to \infty} \sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \beta(i)L(W_{i+1}) \tag*{(by Lemma \ref{lemma:32bound32z32hat})} \\ \leq& 0. \tag*{(\ref{eq:32beta32L32property32bounded})} \end{align}\] ◻

16.6 Bounding the Discretization Error↩︎

We will now prove that the first term in the RHS of 61 is 0. We need to show that \(\forall t \in [0,T+1)\), \[\begin{align} \label{eq:32single32limit} \lim_{k \to \infty} \norm{\sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \alpha(i)H_{r_{n_k}}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1}) - \int_0^t h_{r_{n_k}}(\tilde{z}^{\lim}(s))ds} = 0. \end{align}\tag{148}\]

To evaluate the above, we first fix any \(t \in [0, T+1)\) and then compute the following stronger double limit, which implies that the above limit holds. \[\begin{align} \label{eq:32double32limit} \lim \limits_{\begin{subarray}{l}j \to \infty\\k \to \infty \end{subarray}} \norm{\sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \alpha(i)H_{r_{n_j}}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1}) - \int_0^t h_{r_{n_j}} (\tilde{z}^{\lim}(s))ds}. \end{align}\tag{149}\] The Moore-Osgood theorem (Appendix 9) will help us compute this double limit by turning it into iterated limits. To invoke the Moore-Osgood theorem, we first prove the uniform convergence in \(k\) when \(j \to \infty\).

Lemma 43. \(\forall t \in [0,T+1)\), \[\begin{align} &\lim_{j \to \infty}\norm{\sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \alpha(i)H_{r_{n_j}}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1}) - \int_0^t h_{r_{n_k}} (\tilde{z}^{\lim}(s))ds} \\ =&\norm{\sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \alpha(i)H_{\infty}(\tilde{z}_{n_k}(t(i) - T_{n_k}),W_{i+1}) - \int_0^t h_{\infty} (\tilde{z}^{\lim}(s))ds} \end{align}\] uniformly in \(k\).

Proof. \(\forall j\), \(\forall k\), \(\forall t \in [0,T+1)\), \[\begin{align} & \delimitershortfall=-1pt \left \vert \norm{\sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \alpha(i)H_{r_{n_j}}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1}) - \int_0^t h_{r_{n_j}} (\tilde{z}^{\lim}(s))ds} \right. \\ & \delimitershortfall=-1pt \left. -\norm{\sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \alpha(i)H_{\infty}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1}) - \int_0^t h_{\infty} (\tilde{z}^{\lim}(s))ds} \right \vert \\ \leq& \Bigg\lVert\sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \alpha(i)H_{r_{n_j}}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1}) - \int_0^t h_{r_{n_j}} (\tilde{z}^{\lim}(s))ds \\ &-\sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \alpha(i)H_{\infty}(\tilde{z}_{n_k}(t(i)),W_{i+1}) + \int_0^t h_{\infty} (\tilde{z}^{\lim}(s))ds \Bigg\rVert \tag*{(by \abs{\norm{a} - \norm{b}} \leq \norm{a-b})} \\ \leq& \norm{\sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \alpha(i)(H_{r_{n_j}}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1}) - H_{\infty}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1}))} \\ &+ \norm{\int_0^t h_{r_{n_j}} (\tilde{z}^{\lim}(s)) - h_{\infty} (\tilde{z}^{\lim}(s))ds }\\ \leq& \norm{ \sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \alpha(i)(H_{r_{n_j}}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1}) - H_{\infty}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1}))} \\ &+ \int_0^t \norm{ h_{r_{n_j}} (\tilde{z}^{\lim}(s)) - h_{\infty} (\tilde{z}^{\lim}(s))} ds \label{eq:32H32h32j32H32h32inf321} \end{align}\tag{150}\] By Lemma 52, \(\tilde{z}_{n_k}(t(i)-T_{n_k})\) is in a compact set \(\mathcal{B}_{\hat{z}}\). By Lemma 39, for the compact set \(\mathcal{B}_{\hat{z}}\), \(\forall \epsilon>0\), \(\exists j_1\) such that \(\forall j \geq j_1\), \(\forall k\), \(\forall z \in \mathcal{B}\), \(\forall t \in [0,T+1)\), \[\begin{align} \norm{\sum_{i=m(T_{n_k})}^{m(T_{n_k}+t) - 1} \alpha(i) \left[H_{r_{n_j}}(z, W_{i+1}) - H_{\infty}(z, W_{i+1})\right]} \leq \epsilon \label{eq:32H32y95123k95012532delta32T}. \end{align}\tag{151}\]

Similar to the proof of Lemma 56, we have \[\begin{align} \label{eq:32h32hat32z32uniform} \lim_{j \to \infty}h_{r_{n_j}}(\tilde{z}_k(t)) = h_{\infty}(\tilde{z}_k(t)) \end{align}\tag{152}\] uniformly in \(k\) and \(t \in [0,T+1)\). By 152 , \(\forall \epsilon>0\), \(\exists j_2\) such that \(\forall j > j_2\), \(\forall k\), \(\forall t \in [0,T+1)\), \[\begin{align} \norm{h_{r_{n_j}}(\tilde{z}_k(t)) - h_{\infty}(\tilde{z}_k(t))} \leq \epsilon. \label{eq:32uniform32k32h32epsilon} \end{align}\tag{153}\] Define \(\require{physics} j_0 \doteq \max \qty{j_1, j_2}\). \(\forall j \geq j_0\), \(\forall k\), \(\forall t \in [0,T+1)\), \[\begin{align} & \delimitershortfall=-1pt \left \vert \norm{\sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \alpha(i)H_{r_{n_j}}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1}) - \int_0^t h_{r_{n_j}} (\tilde{z}^{\lim}(s))ds} \right. \\ & \delimitershortfall=-1pt \left. -\norm{\sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \alpha(i)H_{\infty}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1}) - \int_0^t h_{\infty} (\tilde{z}^{\lim}(s))ds} \right \vert \\ \leq& \norm{\sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \alpha(i)(H_{r_{n_j}}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1}) - H_{\infty}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1}))} + (T+1) \epsilon \tag*{(by \eqref{eq:32H32h32j32H32h32inf321}, \eqref{eq:32uniform32k32h32epsilon})} \\ \leq& \epsilon + (T+1) \epsilon \tag*{(by \eqref{eq:32H32h32j32H32h32inf321}, \eqref{eq:32H32y95123k95012532delta32T})} \\ \leq& (T+2) \epsilon. \end{align}\] This completes the proof of uniform convergence. ◻

Now, we prove, for each \(j\), the convergence with \(k\to\infty\).

Lemma 44. \(\forall t \in [0,T+1)\), \(\forall j\), \[\begin{align} \lim_{k \to \infty} \norm{\sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \alpha(i)H_{r_{n_j}}(\tilde{z}_{n_j}(t(i)-T_{n_j}),W_{i+1}) - \int_0^t h_{r_{n_j}} (\tilde{z}^{\lim}(s))ds} = 0. \end{align}\]

The proof of Lemma 44 is very similar to the proof of Lemma 18 in [13] and is omitted here due to its length.

We are now ready to compute the limit in 148 .

Lemma 45. \(\forall t\in [0,T+1)\), \[\begin{align} \lim_{k \to \infty} \norm{\sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \alpha(i)H_{r_{n_k}}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1}) - \int_0^t h_{r_{n_k}}(\tilde{z}^{\lim}(s))ds} = 0. \end{align}\]

Proof. It follows immediately from Lemmas 4344, the Moore-Osgood theorem, and Lemma 58. ◻

Lemma 45 confirms that the first term in the RHS of 61 is 0. Moreover, it also enables us to rewrite \(\tilde{z}^{\lim}(t)\) from a summation form to an integral form. \[\begin{align} &\tilde{z}^{\lim}(t) \\ =& \lim_{k \to \infty} \tilde{z}_{n_k}(0) + \sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \alpha(i)H_{r_{n_k}}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1}) \\ =& \makebox[0.85\textwidth]{\displaystyle\lim_{k \to \infty} \tilde{z}_{n_k}(0) + \int_0^t h_{r_{n_k}} (\tilde{z}^{\lim}(s))ds.\hfill(by Lemma \ref{lemma:32single32limit})} \label{eq:32z32lim32definition322} \end{align}\tag{154}\] This, together with a few Gronwall’s inequality arguments, confirms that the discretization error indeed diminishes along \(\require{physics} \qty{n_k}\).

Lemma 46. \(\forall t\in [0,T+1),\) \[\begin{align} \lim_{k \to \infty} \norm{f_{n_k}(t)} = 0. \end{align}\]

Proof.

\(\forall t\in [0,T+1)\), \[\begin{align} &\lim_{k \to \infty} \norm{f_{n_k}(t)} \\ \leq&\lim_{k \to \infty} \norm{ \sum_{i = m(T_{n_k})}^{m(T_{n_k} +t) -1 } \alpha(i)H_{r_{n_k}}(\tilde{z}_{n_k}(t(i)-T_{n_k}),W_{i+1}) - \int_0^t h_{r_{n_k}}(\tilde{z}^{\lim}(s))ds } \\ &+\lim_{k \to \infty} \norm{\int_0^t h_{r_{n_k}}(\tilde{z}^{\lim}(s))ds - \int_0^t h_{r_{n_k}}(z_{n_k}(s))ds } + 0 \tag*{(by \eqref{eq:32lim32f32k} and Lemma {\ref{lemma:32third32term32disc32error}})} \\ =& \lim_{k \to \infty} \norm{ \int_0^t h_{r_{n_k}} (\tilde{z}^{\lim}(s))ds - \int_0^t h_{r_{n_k}}(z_{n_k}(s))ds } \\ =& \makebox[0.85\textwidth]{\displaystyle\norm{\int_0^t h_{\infty} (\tilde{z}^{\lim}(s))ds - \int_0^t h_{\infty}(z^{\lim}(s))ds}.\hfill(by Lemma \ref{lemma:32h32k32x32lim32h32inf32x32lim32uniform} and Lemma \ref{lemma:32h32k32z32k32h32inf32z32lim32uniform})} \label{eq:32reduce32f32limit321} \end{align}\tag{155}\] We now show the relationship between \(\tilde{z}^{\lim}(t)\) and \(z^{\lim}(t)\). \[\begin{align} &\norm{\tilde{z}^{\lim}(t) - z^{\lim}(t)} \tag{156} \\ =& \norm{\lim_{k \to \infty} \left[\tilde{z}_{n_k}(0) + \int_0^t h_{r_{n_k}} (\tilde{z}^{\lim}(s))ds \right] - \left[\tilde{z}^{\lim}(0) + \int_0^t h_{\infty}(z^{\lim}(s))ds\right] } \tag*{(by \eqref{eq:32z32lim32t} and \eqref{eq:32z32lim32definition322})} \\ =& \norm{\tilde{z}^{\lim}(0) + \int_0^t h_{\infty} (\tilde{z}^{\lim}(s))ds - \left[\tilde{z}^{\lim}(0) + \int_0^t h_{\infty}(z^{\lim}(s))ds\right] } \tag*{(by Lemma \ref{lemma:32h32k32x32lim32h32inf32x32lim32uniform})}\\ =& \norm{ \int_0^t h_{\infty} (\tilde{z}^{\lim}(s))ds - \int_0^t h_{\infty}(z^{\lim}(s))ds } \tag{157}\\ \leq & \int_0^t L \norm{ \tilde{z}^{\lim}(s) - z^{\lim}(s)}ds \tag*{(by Lemma \ref{lemma:32h32Lipschitz})} \\ \leq& 0. \tag*{(by Gronwall inequality in Theorem \ref{theorem:32Gronwall})} \end{align}\] Thus, \[\begin{align} &\norm{\lim_{k \to \infty} f_{n_k}(t) } \\ \leq& \norm{\int_0^t h_{\infty} (\tilde{z}^{\lim}(s))ds - \int_0^t h_{\infty}(z^{\lim}(s))ds} \tag*{(by \eqref{eq:32reduce32f32limit321})} \\ =& \norm{\tilde{z}^{\lim}(t) - z^{\lim}(t)} \tag*{(by \eqref{eq:32f32limit32construct32Gronwall321})} \\ \leq& 0. \tag*{(by \eqref{eq:32norm32z32lim32z32lim})} \end{align}\] ◻

16.7 Proof of Lemma 3↩︎

The proof is similar to Lemma 1 from Chapter 3.2 of [4].

Proof. By Lyapunov stability, there is a \(\delta > 0\) such that any trajectory beginning within \(B(\lambda_{\infty}(y), \delta)\) stays within \(\frac{\epsilon}{2}\) of the equilibrium \(\lambda_{\infty}(y)\).

For an initial condition \(x\), let \(T_x\) be a time at which the trajectory is within \(\frac{\delta}{2}\) of the equilibrium. Let \(x_1\) be some other initial condition. By definition, Lipschitzness, and the Gronwall inequality, we have \[\begin{align} \norm{\eta^y_{\infty}(t, x) - \eta^y_{\infty}(t, x_1) } &\leq \norm{x-x_1} + L \int_0^t \norm{\eta^y_{\infty}(s, x) - \eta^y_{\infty}(s, x_1)}ds \\ &\leq \norm{x-x_1}e^{L T_x} \end{align}\] for all \(t \leq T_x\).

So there is a neighborhood \(V_x\) such that for all \(x_1 \in V_x\), \(\eta^y_{\infty}(T_x, x_1)\) is within \(\delta\) of the equilibrium, which by Lyapunov stability implies that it will always be within \(\epsilon\) of the equilibrium after \(T_x\).

By compactness, we can cover the set \(K\) by a finite number of such intervals and obtain a finite number of times \(T_{x_1}, \ldots, T_{x_n}\) and then take the maximum time to be the value of \(T_{\epsilon}\). ◻

16.8 Proof of Lemma 4↩︎

The proof is similar to Lemma 2 from chapter 3.2 of [4].

Proof. We have \[\begin{align} \eta^{y'(t)}_{c}(t,x) &= x + \int_0^t h_c(\eta^{y'(s)}_c(s, x), y'(s)) ds, \\ \eta^{y}_{\infty}(t,x) &= x + \int_0^t h_{\infty}(\eta^{y}_{\infty}(s, x), y) ds. \end{align}\] Let us define the error term: \[\begin{align} e(t) = \norm{\eta^{y'(t)}_{c}(t,x) - \eta^{y}_{\infty}(t,x)}. \end{align}\]

We can bound \(e(t)\) by two terms: \[\begin{align} e(t) \leq& \int_0^t \norm{h_c(\eta_c^{y'(s)}(s, x), y'(s)) - h_c(\eta_{\infty}^{y}(s, x), y'(s))} ds \\ &+ \int_0^t \norm{h_c(\eta_{\infty}^{y}(s, x), y'(s)) - h_{\infty}(\eta^{y}_{\infty}(s, x), y)} ds \end{align}\] To bound the first term, we use Lipschitzness: \[\begin{align} \int_0^t \norm{h_c(\eta_c^{y'(s)}(s, x), y'(s)) - h_c(\eta_{\infty}^{y}(s, x), y'(s))} ds &\leq L \int_0^t \norm{\eta^{y'(t)}_{c}(t,x) - \eta^{y}_{\infty}(t,x)} ds \\ &= L \int_0^t e(s) ds. \end{align}\]

To bound the second term, we use Lipschitzness and Assumption 3:

\[\begin{align} \int_0^t \norm{h_c(\eta_{\infty}^{y}(s, x), y'(s)) - h_{\infty}(\eta^{y}_{\infty}(s, x), y)} ds \leq& \int_0^t \norm{h_c(\eta_{\infty}^{y}(s, x), y'(s)) - h_{\infty}(\eta^{y}_{\infty}(s, x), y'(s))} ds \\ &+ \int_0^t \norm{h_{\infty}(\eta_{\infty}^{y}(s, x), y'(s)) - h_{\infty}(\eta^{y}_{\infty}(s, x), y)} ds \\ \leq& \int_0^t \epsilon(c) ds + L\int_0^t \norm{y'(s)-y}ds \\ \leq& T\epsilon(c) + TL\rho. \end{align}\]

To conclude, we will use the Gronwall Inequality (Appendix 5): \[\begin{align} e(t) \leq& T \epsilon(c) + TL \rho + L \int_0^t e(s)ds \\ \leq& (L \rho + \epsilon(c))T e^{LT}. \end{align}\] ◻

16.9 Proof of Lemma 21↩︎

Proof. We know that \[\begin{align} \sup_n \norm{\tilde{y}_n(0)} \leq 1 . \end{align}\]

Without loss of generality, let \(t_1 \leq t_2\). \[\begin{align} &\limsup_n \sup_{ 0\leq t_2-t_1 \leq \delta } \norm{ \tilde{y}_n(t_1) - \tilde{y}_n(t_2)} = \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \beta(i) G_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1}) }\\ \end{align}\] \(\forall \xi > 0\), by 172 , \(\exists \delta_0,\) such that \(\forall 0< \delta \leq \delta_0\), \[\begin{align} \sup_{c\geq 1} \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{ \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \beta(i) G_c(0, W_{i+1}) } \leq \xi. \label{eq:32lemma32hat32y32equicontinuous32xi321} \end{align}\tag{158}\] By 179 , \(\exists \delta_1,\) such that \(\forall 0< \delta \leq \delta_1\), \[\begin{align} \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \beta(i) L(W_{i+1}) \leq \xi. \label{eq:32lemma32hat32y32equicontinuous32xi322} \end{align}\tag{159}\] Without loss of generality, let \(t_1 \leq t_2\). Then \(\require{physics} \forall \delta \leq \min \qty{\delta_0,\delta_1}\), we have \[\begin{align} &\limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \beta(i) G_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1}) }\\ \leq& \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \beta(i) G_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1}) } - \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \beta(i) G_{r_n}(0, W_{i+1}) } \\ &+ \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \beta(i) G_{r_n}(0, W_{i+1}) } \\ \leq& \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \beta(i) G_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1}) } - \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \beta(i) G_{r_n}(0, W_{i+1}) } \\ &+ \sup_{c\geq 1} \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \beta(i) G_c(0, W_{i+1}) } \\ \leq& \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \beta(i) G_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1}) } - \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \beta(i) G_{r_n}(0, W_{i+1}) } \\ &+ \xi \tag*{(by \eqref{eq:32lemma32hat32y32equicontinuous32xi321})}\\ \leq& \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{\sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \beta(i) G_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1}) - \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \beta(i) G_{r_n}(0, W_{i+1}) } \\ &+ \xi \\ \leq& \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \beta(i) \norm{G_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1}) - G_{r_n}(0, W_{i+1}) } + \xi\\ \leq& \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \beta(i) L(W_{i+1})\norm{\tilde{z}_n(t(i)-T_n)} + \xi \\ \leq& E \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \beta(i) L(W_{i+1}) + \xi \tag*{(by Lemma~\ref{lemma:32slow32gronwall})} \\ \leq& E \xi + \xi. \tag*{(by \eqref{eq:32lemma32hat32y32equicontinuous32xi322})} \end{align}\] ◻

16.10 Proof of Lemma 22↩︎

Proof. Since \(\sup_n r_n = \infty\) and \(r_n\) is monotonic, \(\lim_{n \rightarrow \infty} r_n = \infty\), and every subsequence also converges to infinity.

Since \(\{f_{n_{k,0}}\}\) is equicontinuous, by the Arzelà-Ascoli theorem (see Appendix 8), there exists a subsequence \(n_{k,1} \subseteq n_{k,0}\) such that \(\{f_{n_{k,1}}\}\) converges uniformly to a continuous limit \(f^{\text{lim}}\). Similarly, since \(\require{physics} \qty{\tilde{y}_{n_{k,1}}(t)}\) is equicontinuous, there is a subsequence \(n_k \subseteq n_{k,1}\) such that \(\require{physics} \qty{\tilde{z}_{n_k}(t)}\) converges uniformly in \(t\) to a continuous limit \(\tilde{y}^{\text{lim}}(t)\).

The proof that \(\lim_{n \rightarrow \infty} y_{n_k}(t) = y^{\text{lim}}(t)\) uniformly is by lemma 64. ◻

17 Auxiliary Lemmas↩︎

The next lemma establishes some results about the relationship between the step sizes and \(T\). It applies to the fast timescale, but a similar result to 160 holds for \(\beta(i)\) in the slow timescale.

Lemma 47. \[\begin{align} \forall n, \, T_{n+1} - T_n \geq& T, \\ \lim_{n\to\infty} T_{n+1} - T_n =& T. \end{align}\]

Moreover, \(\forall \tau > 0, t_1, t_2\) such that \(-\tau \leq t_1 \leq t_2 \leq \tau\), we have \[\begin{align} \lim_{n \to \infty} \sum_{i = m(t(n)+t_1)}^{m(t(n)+t_2) - 1} \alpha(i) &= t_2 - t_1 \tag{160}, \\ \lim_{n \to \infty} \sum_{i = m(t(n)+t_1)}^{m(t(n)+t_2) - 1} \beta(i) &= 0. \tag{161} \end{align}\]

Proof. \(\forall n\), \[\begin{align} &T_{n+1} - T_n \\ =&t(m(T_n+T) + 1) - T_n \\ \geq&T_n + T - T_n \\ \geq&T. \end{align}\] Thus, \[\begin{align} &\lim_{n\to\infty} T_{n+1} - T_n \geq T. \end{align}\] With \[\begin{align} &\lim_{n\to\infty} T_{n+1} - T_n \\ =&\lim_{n\to\infty} t(m(T_n+T) + 1) - T_n \\ =&\lim_{n\to\infty} t(m(T_n+T)) + \alpha(m(T_n+T)) - T_n \\ \leq&\lim_{n\to\infty} T_n + T + \alpha(m(T_n+T)) - T_n \\ =& T, \end{align}\] by the squeeze theorem, we have \(\lim_{n\to\infty} T_{n+1} - T_n = T\).

To prove 160 , \(\forall \tau\), \(\forall -\tau \leq t_1 \leq t_2 \leq \tau\), it suffices to only consider large \(n\) such that \(t(n) - \tau \geq 0\). We have \[\begin{align} &\lim_{n \to \infty} \sum_{i = m(t(n)+t_1)}^{m(t(n) + t_2) - 1 } \alpha(i) \\ =& \lim_{n \to \infty} t(m(t(n)+t_2)) - t(m(t(n)+t_1)) \\ \leq& \lim_{n \to \infty} t(n)+t_2 - t(m(t(n)+t_1)) \\ \leq& \lim_{n \to \infty} t(n)+t_2 - ( t(n)+t_1 - \alpha(m(t(n)+t_1)) ) \\ =& t_2 - t_1 + \lim_{n \to \infty} \alpha(m(t(n)+t_1)) \\ =& t_2 - t_1 \tag*{(by \eqref{eq32147n32alpha})} \end{align}\] and \[\begin{align} &\lim_{n \to \infty} \sum_{i = m(t(n)+t_1)}^{m(t(n) + t_2) - 1 } \alpha(i) \\ =& \lim_{n \to \infty} t(m(t(n)+t_2)) - t(m(t(n)+t_1)) \\ \geq& \lim_{n \to \infty} t(n)+t_2 - \alpha(m(t(n)+t_2)) - t(m(t(n)+t_1)) \\ \geq& \lim_{n \to \infty} t(n)+t_2 - \alpha(m(t(n)+t_2)) - (t(n)+t_1) \\ =& \lim_{n \to \infty} t_2 - t_1 - \alpha(m(t(n)+t_2)) \\ =&t_2 - t_1 \tag*{(by \eqref{eq32147n32alpha})} . \end{align}\] By the squeeze theorem, we have \[\begin{align} \lim_{n \rightarrow \infty} \sum_{i = m(t(n)+t_1)}^{m(t(n)+t_2) - 1} \alpha(i) = t_2 - t_1. \end{align}\]

To prove 161 , fix \(\epsilon > 0\). By 17 , there exists \(N_1 \in \mathbb{N}\) such that for all \(n > m(t(N_1)+t_1)\), \[\begin{align} \frac{\beta(n)}{\alpha(n)} < \epsilon. \label{ineq32ratio326032eps} \end{align}\tag{162}\] By 160 , there exists \(N_2 \in \mathbb{N}\) such that for all \(n > N_2\), \[\begin{align} \sum_{i = m(t(n)+t_1)}^{m(t(n)+t_2) - 1} \alpha(i) < t_2 - t_1 + \epsilon. \label{lim32t95132t95232eps} \end{align}\tag{163}\] Let \(\require{physics} N = \max \qty{N_1, N_2}\). Then for all \(n > N\), \[\begin{align} &\sum_{i = m(t(n)+t_1)}^{m(t(n)+t_2) - 1} \beta(i) \\ <& \epsilon \sum_{i = m(t(n)+t_1)}^{m(t(n)+t_2) - 1} \alpha(i) \tag*{(by \eqref{ineq32ratio326032eps})} \\ <& \epsilon(t_2-t_1 + \epsilon) \tag*{(by \eqref{lim32t95132t95232eps})}. \end{align}\] Since \(t_2 - t_1\) is a constant and \(\epsilon\) can be made arbitrarily small, we have \[\begin{align} \lim_{n \to \infty} \sum_{i = m(t(n)+t_1)}^{m(t(n)+t_2) - 1} \beta(i) &= 0. \end{align}\] ◻

This lemma establishes Lipschitzness for a few classes of functions.

Lemma 48. For any \(x, x', y, y', w, c \geq 1\), including \(c = \infty\), \[\begin{align} \norm{H_c(x,y,w) - H_c(x',y',w)} &\leq L(w) \norm{(x,y) - (x',y')}, \tag{164}\\ \norm{h_c(x,y) - h_c(x',y')} &\leq L \norm{(x,y) - (x',y')}. \tag{165} \\ \norm{G_c(x,y,w) - G_c(x',y',w)} &\leq L(w) \norm{(x,y) - (x',y')}, \tag{166}\\ \norm{g_c(x,y) - g_c(x',y')} &\leq L \norm{(x,y) - (x',y')}. \tag{167} \end{align}\]

Proof. To prove 164 , we first consider \(1 \leq c < \infty\), \[\begin{align} &\norm{H_c(x,y,w) - H_c(x',y',w)} \\ =& \norm{\frac{H(cx,cy,w)}{c} - \frac{H(cx',cy,w)}{c}} \tag*{(by \eqref{def:32H32c})}\\ \leq& \frac{\norm{H(cx,cy, w)- H(cx',cy',w)}}{c}\\ \leq& L(w) \frac{\norm{(cx,cy) - (cx',cy')}}{c} \tag*{(by \eqref{eq:32H32L})} \\ =& L(w)\norm{(x,y) - (x',y')}. \label{eq:32H32c32L32x32x39} \end{align}\tag{168}\] By 26 , \[\begin{align} \norm{H_\infty(x,y,w) - H_\infty(x',y',w)} &\leq L(w) \norm{(x,y) - (x',y')}. \end{align}\]

To prove 165 , \(\forall x,x',y,y'\), \(\forall c \geq 1\) including \(c= \infty\), \[\begin{align} &\norm{h_c(x,y) - h_c(x',y')} \\ =& \norm{ \mathbb{E}_{w\sim \omega}\left[H_c(x,y,w) - H_c(x',y',w)\right]} \\ \leq& \mathbb{E}_{w\sim \omega}\left[\norm{ H_c(x,y,w) - H_c(x',y',w) } \right] \\ \leq& \mathbb{E}_{w\sim \omega}\left[ L(w) \norm{(x,y) - (x',y')}\right] \\ \leq& L \norm{(x,y) - (x',y')}. \end{align}\]

By similar arguments, 166 and 167 also follow. ◻

The following lemma gives some regularity results in the fast timescale.

Lemma 49. \(\forall x, y\), \[\begin{align} \sup_{c\geq 1} \norm{ h_c(0) } <\infty, \sup_{c\geq 1} \norm{ g_c(0) } &<\infty, \tag{169}\\ \sup_{c\geq 1} \limsup_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \norm{ \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) \left[H_c(x,y, W_{i+1}) - h_c(x,y) \right] } & = 0 \quad a.s., \tag{170} \\ \sup_{c\geq 1} \sup_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \norm{ \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) H_c(0, W_{i+1}) } &< \infty \quad a.s., \tag{171}\\ \lim_{\delta \to 0^+} \sup_{c\geq 1} \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{ \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) H_c(0, W_{i+1}) } & = 0 \quad a.s. \tag{172}\\ \end{align}\] By the same arguments, we can show the last three results with the substitutions of \(G\) for \(H\) and \(\beta(i)\) for \(\alpha(i)\).

Proof. Proof of 169 : \[\begin{align} \sup_{c\geq 1} \norm{h_c(0)} = \sup_{c\geq 1} \norm{ \frac{h(0)}{c} } \leq \sup_{c\geq 1} \norm{h(0)} = \norm{h(0)} < \infty \tag{173}, \\ \sup_{c\geq 1} \norm{g_c(0)} = \sup_{c\geq 1} \norm{ \frac{g(0)}{c} } \leq \sup_{c\geq 1} \norm{g(0)} = \norm{g(0)} < \infty \tag{174}. \end{align}\] Proof of 170 : \(\forall x\), \[\begin{align} &\sup_{c\geq 1} \limsup_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \norm{ \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) \left[H_c(x,y,W_{i+1}) - h_c(x,y) \right] } \\ =&\sup_{c\geq 1} \limsup_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \norm{ \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) \left[\frac{H(cx,cy,W_{i+1})}{c} - \frac{h(cx,cy)}{c} \right] }\\ =& \sup_{c\geq 1} \frac{1}{c} \limsup_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \norm{ \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) \left[H(cx, cy,W_{i+1}) - h(cx,cy) \right] }\\ \leq& \sup_{c\geq 1} \frac{1}{c} \limsup_n \sup_{0\leq t_1 \leq t_2 \leq T + \sup_j \alpha(j)} \norm{ \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) \left[H(cx, cy,W_{i+1}) - h(cx,cy) \right] } \tag*{(\forall n, T_{n+1} - T_n \leq T + \sup_j \alpha(j))} \\ =& \sup_{c\geq 1} \frac{1}{c} \cdot 0 \\ =& 0 . \label{eq:32lim32H32h32t320}\\ \end{align}\tag{175}\] Proof of 171 : \[\begin{align} &\limsup_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \norm{ \sum_{i = m(T_n + t_1)}^{m(T_n+t_2) - 1} \alpha(i) H(0, W_{i+1}) } \\ =& \limsup_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \norm{ \sum_{i = m(T_n + t_1)}^{m(T_n+t_2) - 1} \alpha(i) [H(0, W_{i+1}) - h(0) + h(0)] } \\ \leq& \limsup_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \norm{ \sum_{i = m(T_n + t_1)}^{m(T_n+t_2) - 1} \alpha(i) [H(0, W_{i+1}) - h(0)] } \\ &+ \limsup_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \norm{ \sum_{i = m(T_n + t_1)}^{m(T_n+t_2) - 1} \alpha(i) h(0) } \\ \leq& \limsup_n \sup_{0\leq t_1 \leq t_2 \leq T + \sup_j \alpha(j)} \norm{ \sum_{i = m(T_n + t_1)}^{m(T_n+t_2) - 1} \alpha(i) [H(0, W_{i+1}) - h(0)] } \\ &+ \limsup_n \sup_{0\leq t_1 \leq t_2 \leq T + \sup_j \alpha(j)} \norm{ \sum_{i = m(T_n + t_1)}^{m(T_n+t_2) - 1} \alpha(i) h(0) } \tag*{(\forall n, T_{n+1} - T_n \leq T + \sup_j \alpha(j))} \\ =& \limsup_n \sup_{0\leq t_1 \leq t_2 \leq T + \sup_j \alpha(j)} \norm{ \sum_{i = m(T_n + t_1)}^{m(T_n+t_2) - 1} \alpha(i) h(0) } \\ =&\norm{h(0) } \limsup_n \sup_{0\leq t_1 \leq t_2 \leq T+\sup_j \alpha(j)} \sum_{i = m(T_n + t_1)}^{m(T_n+t_2) - 1} \alpha(i) \\ =&\norm{h(0) } (T + \sup_j \alpha(j)) \tag*{(by Lemma~\ref{lemma:32T-minus})} \\ <& \infty. \label{eq:32bounded-h032inf32y32sample32path} \end{align}\tag{176}\] We now consider \(c\) in the above bounds. We first get \[\begin{align} &\sup_{c\geq 1}\sup_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \norm{ \sum_{i = m(T_n + t_1)}^{m(T_n+t_2) - 1} \alpha(i) H_c(0, W_{i+1}) } \\ =&\sup_{c\geq 1}\sup_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \norm{ \sum_{i = m(T_n + t_1)}^{m(T_n+t_2) - 1} \alpha(i) \frac{H(0, W_{i+1}) }{c}} \tag*{(by \eqref{def:32H32c})} \\ =&\sup_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \norm{ \sum_{i = m(T_n + t_1)}^{m(T_n+t_2) - 1} \alpha(i) H(0, W_{i+1})} \tag*{(by c\geq 1)} \\ <& \infty. \tag*{(by \eqref{eq:32bounded-h032inf32y32sample32path})} \end{align}\] Proof of 172 : \[\begin{align} &\lim_{\delta \to 0^+} \sup_{c\geq 1} \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{ \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) H_c(0, W_{i+1}) } \\ \leq &\lim_{\delta \to 0^+} \sup_{c\geq 1} \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{ \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) \left[ H_c(0, W_{i+1}) -h_c(0)\right] } \\ &+ \lim_{\delta \to 0^+} \sup_{c\geq 1} \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{ \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) h_c(0) } \\ \leq & 0 + \lim_{\delta \to 0^+} \sup_{c\geq 1} \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{ \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) h_c(0) } \tag*{(by \eqref{eq:32lim32H32h32t320})} \\ \leq & 0 + \lim_{\delta \to 0^+} \sup_{c\geq 1} \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{ \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) \frac{h(0)}{c} } \\ \leq & 0 + \norm{ h(0)} \lim_{\delta \to 0^+} \sup_{c\geq 1} \frac{1}{c} \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) \\ \leq& \norm{ h(0)} \lim_{\delta \to 0^+} \sup_{c\geq 1} \frac{1}{c} \delta \tag*{(by \eqref{eq:32lim32lr32t95132t952})} \\ =& \norm{ h(0)} \lim_{\delta \to 0^+} \delta \\ =& 0. \end{align}\] ◻

We now have some more regularity results in the fast timescale.

Lemma 50. \[\begin{align} \sup_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \norm{ \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) L(W_{i+1}) } &< \infty \quad a.s., \tag{177}\\ \lim_{n \to \infty} \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \norm{ \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \beta(i) L(W_{i+1}) } &= 0 \quad a.s., \tag{178} \\ \lim_{\delta \to 0^+} \limsup_n \sup_{0\leq t_2-t_1 \leq \delta } \norm{ \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) L(W_{i+1}) } & = 0 \quad a.s., \tag{179}\\ \sup_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \norm{ \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) L_b(W_{i+1}) } &< \infty \quad a.s. \tag{180}\\ \end{align}\]

These proofs are similar to the proofs of Lemma 49 and are thus omitted, except for the proof of 178 (since this is a two-timescale novelty and we need it for Lemma 12). For the other statements, we can also replace \(\alpha(i)\) with \(\beta(i)\).

Proof. Here we show 178 : \[\begin{align} &\lim_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \norm{ \sum_{i = m(T_n + t_1)}^{m(T_n+t_2) - 1} \beta(i) L(W_{i+1}) } \\ =& \lim_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \norm{ \sum_{i = m(T_n + t_1)}^{m(T_n+t_2) - 1} \beta(i) [L(W_{i+1}) - L + L] } \\ \leq& \lim_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \norm{ \sum_{i = m(T_n + t_1)}^{m(T_n+t_2) - 1} \beta(i) [L(W_{i+1}) - L] } \\ &+ \lim_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \norm{ \sum_{i = m(T_n + t_1)}^{m(T_n+t_2) - 1} \beta(i) L } \\ \leq& \lim_n \sup_{0\leq t_1 \leq t_2 \leq T + \sup_j \alpha(j)} \norm{ \sum_{i = m(T_n + t_1)}^{m(T_n+t_2) - 1} \beta(i) [L(W_{i+1}) - L] } \\ &+ \lim_n \sup_{0\leq t_1 \leq t_2 \leq T + \sup_j \alpha(j)} \norm{ \sum_{i = m(T_n + t_1)}^{m(T_n+t_2) - 1} \beta(i) L } \tag*{(\forall n, T_{n+1} - T_n \leq T + \sup_j \alpha(j))} \\ =& \lim_n \sup_{0\leq t_1 \leq t_2 \leq T + \sup_j \alpha(j)} \norm{ \sum_{i = m(T_n + t_1)}^{m(T_n+t_2) - 1} \beta(i) L } \\ =&\norm{L } \lim_n \sup_{0\leq t_1 \leq t_2 \leq T+\sup_j \alpha(j)} \sum_{i = m(T_n + t_1)}^{m(T_n+t_2) - 1} \beta(i) \\ =&0. \tag*{(by Lemma~\ref{lemma:32T-minus})} \\ \end{align}\] ◻

We now show that several different quantities are bounded in the fast timescale.

Lemma 51. Fix a sample path \(\require{physics} \qty{x_0,y_0, \qty{W_i}_{i=1}^\infty}\), there exist constants \(C_H, C_G\) such that \[\begin{align} &LT \leq C_H, LT \leq C_G \tag{181} \\ &\sup_{c\geq 1} \norm{ h_c(0) } \leq \frac{C_H}{T}, \sup_{c\geq 1} \norm{ g_c(0) } \leq \frac{C_G}{T} \tag{182} \\ &\sup_{c\geq 1} \sup_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \norm{ \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) H_c(0, W_{i+1}) } \leq C_H, \tag{183}\\ &\sup_{c\geq 1} \sup_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \norm{ \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \beta(i) G_c(0, W_{i+1}) } \leq C_G, \tag{184}\\ &\sup_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) L(W_{i+1}) \leq C_H. \tag{185} \end{align}\] We can replace \(\alpha(i)\) with \(\beta(i)\) in the last statement. Moreover, for convenience of presentation, we denote \[\begin{align} C_{\hat{x}} \doteq \left[1 + C_H\right] e^{C_H}, C_{\hat{y}} \doteq \left[1 + C_G\right] e^{C_G}, C' \doteq C_G + C_H, C_{\hat{z}} \doteq [1+C']e^{C'} \label{def:32C32hat32x} \end{align}\tag{186}\]

Proof. Fix a sample path \(\require{physics} \qty{x_0,y_0,\qty{W_i}_{i=1}^\infty}\), \[\begin{align} &\makebox[0.85\textwidth]{\displaystyle LT < \infty,\hfill(L and T are constants)} \\ &\makebox[0.85\textwidth]{\displaystyle\sup_{c\geq 1} \norm{ h_c(0) }T < \infty,\hfill(by \eqref{eq:32h32c32bound})} \\ &\makebox[0.85\textwidth]{\displaystyle\sup_{c\geq 1} \sup_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \norm{ \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) H_c(0, W_{i+1}) } < \infty,\hfill(by \eqref{eq:32h32property32H32bounded})} \\ &\makebox[0.85\textwidth]{\displaystyle\sup_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) L(W_{i+1}) < \infty.\hfill(by \eqref{eq:32L32property32bounded})} \end{align}\] Thus, there exists a constant \(C_H\) such that \[\begin{align} &LT \leq C_H \\ &\sup_{c\geq 1} \norm{ h_c(0) } \leq \frac{C_H}{T}, \\ &\sup_{c\geq 1} \sup_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \norm{ \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) H_c(0, W_{i+1}) } \leq C_H,\\ &\sup_n \sup_{0\leq t_1 \leq t_2 \leq T_{n+1} - T_n} \sum_{i = m(T_n+t_1)}^{m(T_n+t_2) - 1} \alpha(i) L(W_{i+1}) \leq C_H. \end{align}\] ◻

We show that the scaled iterates are bounded in the fast timescale.

Lemma 52. \(\sup_{n, t \in [0, T+1)} \norm{\tilde{z}_n(t)} \leq C_{\hat{z}}\).

Proof. \(\forall n \in \mathbb{N}, t \in [0, T+1)\), \[\begin{align} &\norm{\tilde{z}_n(t)} & \\ =& \norm{ \tilde{z}_n(0) + \sum_{i = m(T_n)}^{m(T_n+t) - 1} (\alpha(i) H_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1}), \beta(i) G_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1}))} & \\ \leq& \norm{\tilde{z}_n(0)} + \norm{\sum_{i = m(T_n)}^{m(T_n+t) - 1} \alpha(i) \left[ H_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1}) - H_{r_n}(0, W_{i+1}) \right] + \sum_{i = m(T_n)}^{m(T_n+t) - 1} \alpha(i) H_{r_n}(0, W_{i+1}) } & \\ &+ \norm{\sum_{i = m(T_n)}^{m(T_n+t) - 1} \beta(i) \left[ G_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1}) - G_{r_n}(0, W_{i+1}) \right] + \sum_{i = m(T_n)}^{m(T_n+t) - 1} \beta(i) G_{r_n}(0, W_{i+1}) } \\ \leq & \norm{\tilde{z}_n(0)} + \sum_{i = m(T_n)}^{m(T_n+t) - 1} \alpha(i)\norm{H_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1}) - H_{r_n}(0, W_{i+1}) } + C_H & \\ &+ \sum_{i = m(T_n)}^{m(T_n+t) - 1} \beta(i)\norm{G_{r_n}(\tilde{z}_n(t(i)-T_n), W_{i+1}) - G_{r_n}(0, W_{i+1}) } + C_G \\ \leq & \norm{\tilde{z}_n(0)} + \sum_{i = m(T_n)}^{m(T_n+t) - 1} (\alpha(i)+\beta(i))L(W_{i+1})\norm{\tilde{z}_n(t(i)-T_n)} + C' & \tag*{(by \eqref{eq:32H32c32c95H})}\\ \leq &1 + \sum_{i = m(T_n)}^{m(T_n+t) - 1} (\alpha(i)+\beta(i))L(W_{i+1})\norm{\tilde{z}_n(t(i)-T_n)} + C' & \tag*{(by \eqref{eq:32hat-z-norm-1})}\\ \leq &\left[1 + C' \right] e^{\sum_{i = m(T_n)}^{m(T_n+t) - 1} (\alpha(i)+\beta(i))L(W_{i+1})} \tag*{(by \tilde{z}_n(t) = \tilde{z}_n(t(m(T_n + t)) - T_n) and discrete Gronwall inequality in Theorem \ref{theorem:32discrete32Gronwall})} & \\ \leq &\left[ 1 + C' \right] e^{C'} \tag*{(by \eqref{eq:32alpha32L32bound32C95H})} & \\ = & C_{\hat{z}}.\tag*{(by \eqref{def:32C32hat32x})} \end{align}\] ◻

We show that the trajectories of these ODEs are bounded in the fast timescale.

Lemma 53. \(\sup_{n, t \in [0, T+1)} \norm{z_n(t)} \leq C_{\hat{x}}\).

Proof. \(\forall n, t \in [0, T+1)\), \[\begin{align} &\norm{z_n(t)}& \\ =& \norm{ z_n(0) + \int_0^t (h_{r_n}(z_n(s)),0)ds}& \\ \leq & \norm{z_n(0)} + \norm{\int_0^t h_{r_n}(z_n(s))ds}& \\ \leq & \norm{z_n(0)} + \int_0^t \norm{h_{r_n}(z_n(s)) - h_{r_n}(0) }ds + \int_0^t \norm{ h_{r_n}(0) }ds & \\ \leq & \norm{z_n(0)} + \int_0^t L\norm{z_n(s)} ds + \int_0^t \norm{ h_{r_n}(0) }ds& \tag*{(by Lemma \ref{lemma:32h32Lipschitz})} \\ \leq & \norm{z_n(0)} + \int_0^t L\norm{z_n(s)} ds + (T+1) \norm{ h_{r_n}(0)} & \\ \leq & \norm{z_n(0)} + \int_0^t L\norm{z_n(s)} ds + (T+1) \frac{C_H}{T+1} \tag*{(by \eqref{eq:32h32c32c95H})} \\ \leq & 1 + \int_0^t L\norm{z_n(s)} ds + C_H \tag*{(by \eqref{eq:32hat-z-norm-1}, \eqref{def:32z32n32init})} \\ \leq &\left[1 + C_H \right] e^{L(T+1)}& \tag*{(by Gronwall inequality in Theorem \ref{theorem:32Gronwall})}\\ \leq &\left[1 + C_H \right] e^{C_H}& \tag*{(by \eqref{eq:32LT32C95H})}\\ =& C_{\hat{x}} \tag*{(by \eqref{def:32C32hat32x})} \end{align}\] ◻

We show that applying \(h_{r_n}\) to the ODE trajectories still is bounded.

Lemma 54. \(\sup_{n, t \in [0, T+1)} \norm{h_{r_n}(z_n(t))} < \infty\).

Proof. \(\forall n, \forall t \in [0, T+1)\), \[\begin{align} &\norm{h_{r_n}(z_n(t))} \\ \leq& \norm{h_{r_n}(z_n(t)) - h_{r_n}(0)} + \norm{h_{r_n}(0)}\\ \leq& L\norm{z_n(t)} + \norm{h_{r_n}(0)} \tag*{(by Lemma \ref{lemma:32h32Lipschitz})} \\ \leq& L C_{\hat{x}} + \norm{h_{r_n}(0)} \tag*{(by Lemma~\ref{lemma:32bound32z})} \\ \leq& L C_{\hat{x}} + \frac{C_H}{T}. \tag*{(by \eqref{def:32r32n} and \eqref{eq:32h32c32c95H})} \end{align}\] Thus, because \(C_{\hat{x}}, C_H\) are independent of \(n,t\), \(\sup_{n, t \in [0, T+1)} \norm{h_{r_n}(z_n(t))} < \infty\). ◻

In the fast timescale, we show that the limiting trajectory is bounded.

Lemma 55. \(\sup_{t \in [0, T+1)} \norm{z^{\lim}(t)} \leq C_{\hat{x}}\).

Proof. \(\forall t \in [0, T+1)\), \[\begin{align} &\norm{z^{\lim}(t)}& \\ =& \norm{ z^{\lim}(0) + \int_0^t (h_{\infty}(z^{\lim}(s)), 0)ds}& \\ \leq & \norm{z^{\lim}(0)} + \norm{\int_0^t h_{\infty}(z^{\lim}(s))ds}& \\ =& \norm{z^{\lim}(0)} + \norm{\int_0^t \left[ h_{\infty}(z^{\lim}(s)) - h_{\infty}(0) \right]ds + \int_0^t h_{\infty}(0) ds }& \\ \leq & \norm{z^{\lim}(0)} + \int_0^t \norm{h_{\infty}(z^{\lim}(s)) - h_{\infty}(0) }ds + \int_0^t \norm{ h_{\infty}(0) }ds & \\ \leq & \norm{z^{\lim}(0)} + \int_0^t L\norm{z^{\lim}(s)} ds + \int_0^t \norm{ h_{\infty}(0) }ds& \tag*{(by Lemma \ref{lemma:32h32Lipschitz})} \\ \leq &1 + \int_0^t L\norm{z^{\lim}(s)} ds + \int_0^t \norm{ h_{\infty}(0) }ds& \tag*{(by \eqref{eq:32hat-z-norm-1}, \eqref{def:32z32n32init})} \\ \leq &1 + \int_0^t L\norm{z^{\lim}(s)} ds + (T+1)\norm{ h_{\infty}(0) } \\ \leq &1 + \int_0^t L\norm{z^{\lim}(s)} ds + C_H \tag*{(by Assumption \ref{assumption:32lim32h44g32uniformly32convergent} and \eqref{eq:32h32c32c95H})} \\ \leq &\left[1 + C_H \right] e^{\int_0^t L ds }& \tag*{(by Gronwall inequality in Theorem \ref{theorem:32Gronwall})}\\ \leq &\left[1 + C_H \right] e^{L(T+1)} & \\ \leq& C_{\hat{x}}. \tag*{(by \eqref{eq:32LT32C95H}, \eqref{def:32C32hat32x})}& \end{align}\] ◻

Lemma 56. \(\lim_{k \to \infty}h_{r_{n_k}}(z^{\lim}(t)) = h_{\infty}(z^{\lim}(t))\) uniformly in \(t\in [0, T+1)\).

Proof. By Assumption 5, \(\lim_{k \to \infty}h_{r_{n_k}}(v) = h_{\infty}(v)\) uniformly in a compact set \(\require{physics} \qty{v \vert v\in \mathbb{R}^d, \norm{v}\leq C_x }\). By Lemma 55, \(\require{physics} \qty{z^{\lim}(t) \vert t \in [0,T+1)} \subseteq \qty{v \vert v\in \mathbb{R}^d, \norm{v}\leq C_x }\). Therefore, \(\lim_{k \to \infty}h_{r_{n_k}}(z^{\lim}(t)) = h_{\infty}(z^{\lim}(t))\) uniformly in \(\require{physics} \qty{z^{\lim}(t) \vert t \in [0,T+1)}\) and in \(t \in [0,T+1)\). ◻

Lemma 57. \(\forall t \in [0, T+1)\), we have \[\begin{align} \lim_{k \to \infty} z_{n_k}(t) = z^{\lim}(t). \end{align}\] Moreover, the convergence is uniform in \(t\) on \([0, T+1)\).

Proof. By 57 , \(\forall \delta > 0\), there exists a \(k_1\) such that \(\forall k \geq k_1\), \(\forall t \in [0,T+1)\), \[\begin{align} \norm{\tilde{z}_{n_k}(t) - \tilde{z}^{\lim}(t)} \leq \delta .\label{eq:32z32lim32epsilion321} \end{align}\tag{187}\] By Lemma 56, there exists a \(k_2\) such that \(\forall k \geq k_2\), \(\forall t \in [0,T+1)\), \[\begin{align} \norm{h_{r_{n_k}}(z^{\lim}(t)) - h_{\infty}(z^{\lim}(t))} \leq \delta. \label{eq:32z32lim32epsilion322} \end{align}\tag{188}\] \(\require{physics} \forall k \geq \max\qty{ k_1, k_2}\), \(\forall t \in [0,T+1)\) \[\begin{align} & \norm{z_{n_k}(t) - z^{\lim}(t) } \\ =& \norm{\tilde{z}_{n_k}(0) + \int_0^t (h_{r_{n_k}}(z_{n_k}(s)),0)ds - \tilde{z}^{\lim}(0) - \int_0^t (h_{\infty}(z^{\lim}(s)),0)ds} \\ \leq& \norm{\tilde{z}_{n_k}(0) - \tilde{z}^{\lim}(0)} + \norm{\int_0^t h_{r_{n_k}}(z_{n_k}(s))ds - \int_0^t h_{\infty}(z^{\lim}(s))ds} \\ \leq& \delta + \norm{\int_0^t h_{r_{n_k}}(z_{n_k}(s)) - h_{\infty}(z^{\lim}(s))ds} \tag*{(by \eqref{eq:32z32lim32epsilion321})} \\ \leq& \delta + \int_0^t \norm{h_{r_{n_k}}(z_{n_k}(s)) - h_{r_{n_k}}(z^{\lim}(s)) }ds + \int_0^t \norm{ h_{r_{n_k}}(z^{\lim}(s)) - h_{\infty}(z^{\lim}(s))} ds \\ \leq& \delta + L \int_0^t \norm{z_{n_k}(s) -z^{\lim}(s) }ds + \int_0^t \norm{ h_{r_{n_k}}(z^{\lim}(s)) - h_{\infty}(z^{\lim}(s))} ds \tag*{(by Lemma \ref{lemma:32h32Lipschitz})} \\ \leq& \delta + t\delta + L \int_0^t \norm{z_{n_k}(s) -z^{\lim}(s) }ds \tag*{(by \eqref{eq:32z32lim32epsilion322})} \\ \leq& (\delta + t\delta)e^{Lt} \tag*{(by Gronwall inequality in Theorem \ref{theorem:32Gronwall})}\\ \leq& (\delta + (T+1)\delta)e^{L(T+1)}, \label{eq:32z32z32lim32difference} \end{align}\tag{189}\] which completes the proof. ◻

Lemma 58. For any function \(f: \mathbb{R}\times \mathbb{R}\to \mathbb{R}\), if \(\lim \limits_{\begin{subarray}{l} a \to \infty\\ b \to \infty \end{subarray}} f(a,b) = L\) then \(\lim \limits_{c \to \infty} f(c,c) = L\) where \(L\) is a constant.

Proof. By definition, \(\forall \epsilon > 0, \exists a_0, b_0\) such that \(\forall a > a_0, b > b_0\), \(\norm{f(a,b) - L } < \epsilon\). Thus, \(\require{physics} \forall \epsilon > 0, \exists c_0 = \max \qty{a_0, b_0}\) such that \(\forall c > c_0\), \(\norm{f(c,c) - L } < \epsilon\). ◻

Here we are pulling the limit into the integral.

Lemma 59. \(\forall t \in [0,T+1)\), \[\begin{align} \lim_{k \to \infty} \int_0^t h_{r_{n_k}}(\tilde{z}^{\lim}(s))ds = \int_0^t h_{\infty}(\tilde{z}^{\lim}(s))ds. \label{eq:32f32limit32interchange32limit32int321} \end{align}\tag{190}\]

Proof. From Lemma 52, it is easy to see that \[\begin{align} \sup_{t\in[0, T+1)} \norm{\tilde{z}^{\lim}(t)} < \infty, \end{align}\] which, similar to Lemma 54, implies that \[\begin{align} \sup_{k, t\in[0, T+1)} \norm{h_{r_{n_k}}\left(\tilde{z}^{\lim}(t)\right)} < \infty. \end{align}\]

By the dominated convergence theorem, \(\forall t\in [0,T+1)\), \[\begin{align} & \lim_{k \to \infty} \int_0^t h_{r_{n_k}} (\tilde{z}^{\lim}(s))ds = \int_0^t \lim_{k \to \infty} h_{r_{n_k}} (\tilde{z}^{\lim}(s))ds = \int_0^t h_{\infty} (\tilde{z}^{\lim}(s))ds, \end{align}\] which completes the proof. ◻

Finally, we put all the previous lemmas together and get convergence.

Lemma 60. \(\forall t \in [0,T+1)\), \[\begin{align} \lim_{k \to \infty} \int_0^t h_{r_{n_k}}(z_{n_k}(s))ds = \int_0^t h_{\infty}(z^{\lim}(s))ds. \label{eq:32f32limit32interchange32limit32int322} \end{align}\tag{191}\]

Proof. \(\forall \epsilon>0\), by Lemma 56, \(\exists k_0\) such that \(\forall k \geq k_0\), \(\forall t \in [0,T)\), \[\begin{align} \norm{ h_{r_{n_k}}(z^{\lim}(s)) - h_{\infty}(z^{\lim}(s)) } \leq \epsilon. \label{eq:32f32k32032k950} \end{align}\tag{192}\] By Lemma 57, \(\exists k_1\) such that \(\forall k \geq k_1\), \(\forall t \in [0,T+1)\), \[\begin{align} \norm{ z_{n_k}(t)- z^{\lim}(t) } \leq \epsilon. \label{eq:32f32k32032k951} \end{align}\tag{193}\] Thus, \(\require{physics} \forall k \geq \max \qty{k_0,k_1}\), \(\forall t \in [0,T+1)\), \[\begin{align} & \norm{ \int_0^t h_{r_{n_k}}(z_{n_k}(s))ds - \int_0^t h_{\infty}(z^{\lim}(s))ds } \\ \leq& \norm{ \int_0^t h_{r_{n_k}}(z_{n_k}(s))ds - \int_0^t h_{r_{n_k}}(z^{\lim}(s))ds} + \norm{ \int_0^t h_{r_{n_k}}(z^{\lim}(s))ds - \int_0^t h_{\infty}(z^{\lim}(s))ds } \\ \leq& \int_0^t \norm{h_{r_{n_k}}(z_{n_k}(s)) - h_{r_{n_k}}(z^{\lim}(s))}ds + \int_0^t \norm{h_{r_{n_k}}(z^{\lim}(s)) - h_{\infty}(z^{\lim}(s)) }ds \\ \leq& \int_0^t \norm{h_{r_{n_k}}(z_{n_k}(s)) - h_{r_{n_k}}(z^{\lim}(s))} ds + (T+1)\epsilon \tag*{(by \eqref{eq:32f32k32032k950})} \\ \leq& \int_0^t L\norm{z_{n_k}(s) - z^{\lim}(s)} ds + T\epsilon \tag*{(by Lemma \ref{lemma:32h32Lipschitz})}\\ \leq& L (T+1)\epsilon + (T+1)\epsilon. \tag*{(by \eqref{eq:32f32k32032k951})} \end{align}\]

Thus, \(\forall t \in [0,T+1)\), \[\begin{align} \lim_{k \to \infty} \int_0^t h_{r_{n_k}}(z_{n_k}(s))ds = \int_0^t h_{\infty}(z^{\lim}(s))ds. \end{align}\] ◻

This lemma uses the Gronwall inequality to show that in the fast timescale, the iterates can’t grow too much in one period \(T\).

Lemma 61. \(\forall n, \forall t \in [0, T_{n+1} - T_n]\), \[\begin{align} \norm{ \bar{z}(T_{n} + t)} &\leq \left(\norm{ \bar{z}(T_n)} C' + C' \right) e^{C'} + \norm{ \bar{z}(T_n)}, \end{align}\] and in particular, \[\begin{align} \norm{ \bar{z}(T_{n+1})} &\leq \left(\norm{ \bar{z}(T_n)} C' + C' \right) e^{C'} + \norm{ \bar{z}(T_n)} \end{align}\] where \(C'\) is a positive constant defined in Lemma 51.

Proof. We first show the difference between \(\bar{z}(T_{n+1})\) and \(\bar{z}(T_n)\) by the following derivations. \(\forall n\), \(\forall t \in [0, T_{n+1} - T_n]\), \[\begin{align} &\norm{\bar{z}(T_n + t) - \bar{z}(T_n)} \\ =& \norm{\bar{z}(t(m(T_n + t))) - \bar{z}(T_n)} \\ =& \norm{ \bar{z}(T_n) + \sum_{i = m(T_n)}^{m(T_n+t) - 1} (\alpha(i) H(\bar{z}(t(i)), W_{i+1}), \beta(i) G(\bar{z}(t(i)), W_{i+1})) - \bar{z}(T_n)} \\ = &\norm{\sum_{i = m(T_n)}^{m(T_n+t) - 1} (\alpha(i) H(\bar{z}(t(i)), W_{i+1}), \beta(i) G(\bar{z}(t(i)), W_{i+1}))} \\ \leq &\sum_{i = m(T_n)}^{m(T_n+t) - 1} \alpha(i)\norm{H(\bar{z}(t(i)), W_{i+1}) - H( \bar{z}(T_n), W_{i+1}) } + \beta(i)\norm{G(\bar{z}(t(i)), W_{i+1}) - G( \bar{z}(T_n), W_{i+1}) } \\ &+ \norm{\sum_{i = m(T_n)}^{m(T_n+t) - 1} \alpha(i) H( \bar{z}(T_n), W_{i+1}) } + \norm{\sum_{i = m(T_n)}^{m(T_n+t) - 1} \beta(i) G( \bar{z}(T_n), W_{i+1}) } \\ \leq &\sum_{i = m(T_n)}^{m(T_n+t) - 1} (\alpha(i) + \beta(i))L(W_{i+1})\norm{\bar{z}(t(i)) - \bar{z}(T_n)} \\ &+ \norm{\sum_{i = m(T_n)}^{m(T_n+t) - 1} \alpha(i) H( \bar{z}(T_n), W_{i+1}) } + \norm{\sum_{i = m(T_n)}^{m(T_n+t) - 1} \beta(i) G( \bar{z}(T_n), W_{i+1}) } \\ \leq &\sum_{i = m(T_n)}^{m(T_n+t) - 1} (\alpha(i) + \beta(i) )L(W_{i+1})\norm{\bar{z}(t(i)) - \bar{z}(T_n)} + \sum_{i = m(T_n)}^{m(T_n+t) - 1} (\alpha(i) + \beta(i)) L(W_{i+1}) \norm{ \bar{z}(T_n)} \\ &+ \norm{ \sum_{i = m(T_n)}^{m(T_n+t) - 1} \alpha(i) H(0, W_{i+1}) } + \norm{ \sum_{i = m(T_n)}^{m(T_n+t) - 1} \beta(i) G(0, W_{i+1}) } \tag*{(by Assumption \ref{assumption:32H32Lipschitz})}\\ = &\sum_{i = m(T_n)}^{m(T_n+t) - 1} (\alpha(i) + \beta(i))L(W_{i+1})\norm{\bar{z}(t(i)) - \bar{z}(T_n)} + \norm{ \bar{z}(T_n)} \sum_{i = m(T_n)}^{m(T_n+t) - 1} (\alpha(i) + \beta(i)) L(W_{i+1}) \\ &+ \norm{ \sum_{i = m(T_n)}^{m(T_n+t) - 1} \alpha(i) H(0, W_{i+1}) } + \norm{ \sum_{i = m(T_n)}^{m(T_n+t) - 1} \beta(i) G(0, W_{i+1}) } \\ \leq &\sum_{i = m(T_n)}^{m(T_n+t) - 1} (\alpha(i) + \beta(i))L(W_{i+1})\norm{\bar{z}(t(i)) - \bar{z}(T_n)} + \norm{ \bar{z}(T_n)} C' + \norm{ \sum_{i = m(T_n)}^{m(T_n+t) - 1} \alpha(i) H(0, W_{i+1}) } \\ &+ \norm{ \sum_{i = m(T_n)}^{m(T_n+t) - 1} \beta(i) G(0, W_{i+1}) } \tag*{(by \eqref{eq:32alpha32L32bound32C95H})} \\ \leq & \sum_{i = m(T_n)}^{m(T_n+t) - 1} (\alpha(i) + \beta(i))L(W_{i+1})\norm{\bar{z}(t(i)) - \bar{z}(T_n)} + \left[\norm{ \bar{z}(T_n)} C' + C' \right] \tag*{(by \eqref{eq:32H32c32c95H})} \\ \leq &\left[\norm{ \bar{z}(T_n)} C' + C' \right] e^{\sum_{i = m(T_n)}^{m(T_n+t) - 1} (\alpha(i) + \beta(i))L(W_{i+1})} \tag*{(by discrete Gronwall inequality in Theorem \ref{theorem:32discrete32Gronwall})}\\ \leq & \makebox[0.85\textwidth]{\displaystyle\left[\norm{ \bar{z}(T_n)} C' + C' \right] e^{C'}\hfill(by \eqref{eq:32alpha32L32bound32C95H})} \label{eq:32bar32x32bound} \end{align}\tag{194}\]  ◻

The following lemmas are in the slow timescale.

The next lemma shows the boundedness of \(\norm{y^{\lim}(t)}\) where \(C, C_0\) are arbitrary constants.

Lemma 62. \(\sup_{t \in [0, T+1)} \norm{y^{\lim}(t)} \leq C\).

Proof. \(\forall t \in [0, T+1)\), \[\begin{align} &\norm{y^{\lim}(t)}& \\ =& \norm{ y^{\lim}(0) + \int_0^t g_{\infty}(\lambda_{\infty}(y^{\lim}(s)), y^{\lim}(s))ds}& \\ \leq & \norm{y^{\lim}(0)} + \norm{\int_0^t g_{\infty}(\lambda_{\infty}(y^{\lim}(s)), y^{\lim}(s))ds}& \\ =& \norm{y^{\lim}(0)} + \norm{\int_0^t \left[ g_{\infty}(\lambda_{\infty}(y^{\lim}(s)), y^{\lim}(s)) - g_{\infty}(0) \right]ds + \int_0^t g_{\infty}(0) ds }& \\ \leq & \norm{y^{\lim}(0)} + \int_0^t \norm{g_{\infty}(\lambda_{\infty}(y^{\lim}(s)), y^{\lim}(s)) - g_{\infty}(0) }ds + \int_0^t \norm{ g_{\infty}(0) }ds & \\ \leq & \norm{y^{\lim}(0)} + \int_0^t L\norm{\lambda_{\infty}(y^{\lim}(s))} + L\norm{y^{\lim}(s)} ds + \int_0^t \norm{ g_{\infty}(0) }ds& \tag*{(by Lemma \ref{lemma:32h32Lipschitz})} \\ \leq &1 + \int_0^t L \cdot L_{\lambda} \norm{y^{\lim}(s)} + L\norm{y^{\lim}(s)} ds + \int_0^t \norm{ g_{\infty}(0) }ds& \\ \leq &1 + \int_0^t L(L_{\lambda}+1)\norm{y^{\lim}(s)} ds + (T+1)\norm{ g_{\infty}(0) } \\ \leq &1 + \int_0^t L(L_{\lambda}+1)\norm{y^{\lim}(s)} ds + C_0 \\ \leq &\left[1 + C_0 \right] e^{\int_0^t L(L_{\lambda}+1) ds }& \tag*{(by Gronwall inequality in Theorem \ref{theorem:32Gronwall})}\\ \leq &\left[1 + C_0 \right] e^{L(L_{\lambda}+1)(T+1)} & \\ \leq& C. & \end{align}\] ◻

The following shows a uniform convergence on the sequence \(g_{r_{n_k}}\).

Lemma 63. \(\lim_{k \to \infty}g_{r_{n_k}}(\lambda_{\infty}(y^{\lim}(t)), y^{\lim}(t)) = g_{\infty}(\lambda_{\infty}(y^{\lim}(t)), y^{\lim}(t))\) uniformly in \(t\in [0, T+1)\).

Proof. By Assumption 5, \(\lim_{k \to \infty}g_{r_{n_k}}(v) = g_{\infty}(v)\) uniformly in a compact set \(\require{physics} \qty{v \vert v\in \mathbb{R}^{d_1+d_2}, \norm{v}\leq C }\). By Lemma 62, \(\require{physics} \qty{y^{\lim}(t) \vert t \in [0,T+1)} \subseteq \qty{v \vert v\in \mathbb{R}^d, \norm{v}\leq C }\). Additionally, \(\lambda_{\infty}\) is Lipschitz, so \(\require{physics} \qty{(\lambda_{\infty}(y^{\lim}(t)), y^{\lim}(t)) \vert t \in [0,T+1)} \subseteq \qty{v \vert v\in \mathbb{R}^{d_1+d_2}, \norm{v}\leq C }\).

Therefore, \(\lim_{k \to \infty}g_{r_{n_k}}(\lambda_{\infty}(y^{\lim}(t)), y^{\lim}(t)) = g_{\infty}(\lambda_{\infty}(y^{\lim}(t)), y^{\lim}(t))\) uniformly in \(\require{physics} \qty{y^{\lim}(t) \vert t \in [0,T+1)}\) and in \(t \in [0,T+1)\). ◻

The next lemma gives us the uniform convergence of \(y_{n_k}\) we desire.

Lemma 64. \(\forall t \in [0, T+1)\), we have \[\begin{align} \lim_{k \to \infty} y_{n_k}(t) = y^{\lim}(t). \end{align}\] Moreover, the convergence is uniform in \(t\) on \([0, T+1)\).

Proof. By 90 , \(\forall \delta > 0\), there exists a \(k_1\) such that \(\forall k \geq k_1\), \(\forall t \in [0,T+1)\), \[\begin{align} \norm{\tilde{y}_{n_k}(t) - \tilde{y}^{\lim}(t)} \leq \delta .\label{eq:32y32lim32epsilion321} \end{align}\tag{195}\] By Lemma 63, there exists a \(k_2\) such that \(\forall k \geq k_2\), \(\forall t \in [0,T+1)\), \[\begin{align} \norm{g_{r_{n_k}}(\lambda_{\infty}(y^{\lim}(t)), y^{\lim}(t)) - g_{\infty}(\lambda_{\infty}(y^{\lim}(t)), y^{\lim}(t))} \leq \delta. \label{eq:32y32lim32epsilion322} \end{align}\tag{196}\] \(\require{physics} \forall k \geq \max\qty{ k_1, k_2}\), \(\forall t \in [0,T+1)\) \[\begin{align} & \norm{y_{n_k}(t) - y^{\lim}(t) } \\ =& \norm{\tilde{y}_{n_k}(0) + \int_0^t g_{r_{n_k}}(\lambda_{\infty}(y_{n_k}(s)),y_{n_k}(s))ds - \tilde{y}^{\lim}(0) - \int_0^t g_{\infty}(\lambda_{\infty}(y^{\lim}(s)),y^{\lim}(s))ds} \\ \leq& \norm{\tilde{y}_{n_k}(0) - \tilde{y}^{\lim}(0)} + \norm{\int_0^t g_{r_{n_k}}(\lambda_{\infty}(y_{n_k}(s)),y_{n_k}(s))ds - \int_0^t g_{\infty}(\lambda_{\infty}(y^{\lim}(s)), y^{\lim}(s))ds} \\ \leq& \delta + \norm{\int_0^t g_{r_{n_k}}(\lambda_{\infty}(y_{n_k}(s)),y_{n_k}(s)) - g_{\infty}(\lambda_{\infty}(y^{\lim}(s)), y^{\lim}(s))ds} \tag*{(by \eqref{eq:32y32lim32epsilion321})} \\ \leq& \delta + \int_0^t \norm{g_{r_{n_k}}(\lambda_{\infty}(y_{n_k}(s)),y_{n_k}(s)) - g_{r_{n_k}}(\lambda_{\infty}(y^{\lim}(s)), y^{\lim}(s)) }ds \\ &+ \int_0^t \norm{ g_{r_{n_k}}(\lambda_{\infty}(y^{\lim}(s)), y^{\lim}(s)) - g_{\infty}(\lambda_{\infty}(y^{\lim}(s)), y^{\lim}(s))} ds \\ \leq& \delta + L\int_0^t \norm{(\lambda_{\infty}(y_{n_k}(s)),y_{n_k}(s)) - (\lambda_{\infty}(y^{\lim}(s)), y^{\lim}(s)))}ds \\ &+ \int_0^t \norm{ g_{r_{n_k}}(\lambda_{\infty}(y^{\lim}(s)), y^{\lim}(s)) - g_{\infty}(\lambda_{\infty}(y^{\lim}(s)), y^{\lim}(s))} \tag*{(by Lemma \ref{lemma:32h32Lipschitz})} \\ \leq& \delta + t\delta + L (L_{\lambda}+1) \int_0^t \norm{y_{n_k}(s) - y^{\lim}(s) }ds \tag*{(by \eqref{eq:32y32lim32epsilion322})} \\ \leq& (\delta + t\delta)e^{ L (L_{\lambda}+1)t} \tag*{(by Gronwall inequality in Theorem \ref{theorem:32Gronwall})}\\ \leq& (\delta + T\delta)e^{ L (L_{\lambda}+1)T}, \label{eq:32y32y32lim32difference} \end{align}\tag{197}\] which completes the proof. ◻

The next lemma applies the Gronwall inequality to control the growth of the iterates in the slow timescale.

Lemma 65. There are some constants \(A, B\) such that \[\begin{align} \norm{y^{\text{max}}_l} \leq A \norm{y^{\text{max}}_{m(T_n)}} + B \end{align}\] where \(m(T_n) \leq l \leq m(T_{n+1})\). As a consequence, there are constants \(C\) and \(D\) such that \[\begin{align} \norm{z^{max}_l} \leq C \norm{z^{max}_{m(T_n)}} + D. \label{eq:32slow32gronwall32z} \end{align}\tag{198}\] This implies that \(\norm{\tilde{z}_n(t)}\) is bounded since for all \(n\), \(\norm{\tilde{z}_n(0)} \leq 1\).

Proof. We know that \[\begin{align} \norm{y_l} &= \norm{y_{m(T_n)} + \sum_{i=m(T_n)}^l \beta(i)G(x_i, y_i, W_{i+1})} \\ &\leq \norm{y^{\text{max}}_n} + \sum_{i = m(T_n)}^l \beta(i)\norm{G(x_i, y_i, W_{i+1})} \label{eq:32ymax32broken32up} \end{align}\tag{199}\] Since the second term of 199 is monotonically increasing in \(l\), we know that the following holds: \[\begin{align} \norm{y^{\text{max}}_l} &\leq \norm{y^{\text{max}}_{m(T_{n})}}+ \sum_{i = m(T_n)}^l \beta(i)\norm{G(x_i, y_i, W_{i+1})} \\ &\leq \norm{y^{\text{max}}_{m(T_{n})}}+\sum_{i = m(T_n)}^l \beta(i)L(W_{i+1})(\norm{x_i}+\norm{y_i}) + \sum_{i = m(T_n)}^l \beta(i) G(0, W_{i+1}) \\ &\leq \norm{y^{\text{max}}_{m(T_{n})}}+\sum_{i = m(T_n)}^l \beta(i)L(W_{i+1})(\norm{x_i}+\norm{y_i}) + E \tag*{(\ref{eq:32h32property32H32bounded})} \\ &\leq \norm{y^{\text{max}}_{m(T_{n})}}+ \sum_{i = m(T_n)}^l \beta(i)L(W_{i+1})( K(1+\norm{y^{\text{max}}_i})+\norm{y^{\text{max}}_i}) + E \tag*{(Lemma \ref{thm:32x32stability})} \\ &\leq \norm{y^{\text{max}}_{m(T_{n})}}+\sum_{i = m(T_n)}^l \beta(i)L(W_{i+1})( K+(K+1)\norm{y^{\text{max}}_i}) + E \\ &\leq \norm{y^{\text{max}}_{m(T_{n})}}+K \sum_{i = m(T_n)}^l \beta(i)L(W_{i+1}) + (K+1) \sum_{i = m(T_n)}^l \beta(i)L(W_{i+1})\norm{y^{\text{max}}_i} + E \\ &\leq \norm{y^{\text{max}}_{m(T_{n})}} + K C' + (K+1) \sum_{i = m(T_n)}^l \beta(i)L(W_{i+1})\norm{y^{\text{max}}_i} \tag*{(\ref{eq:32alpha32L32bound32C95H})} + E \\ &\leq \left(\norm{y^{\text{max}}_{m(T_{n})}}+KC' \right)e^{(K+1) \sum_{i = m(T_n)}^l \beta(i)L(W_{i+1})} \tag*{(by discrete Grownwall inequality in Appendix \ref{theorem:32discrete32Gronwall})} + E\\ &\leq \left(\norm{y^{\text{max}}_{m(T_{n})}} + KC' \right)e^{(K+1)C'} \tag*{(\ref{eq:32alpha32L32bound32C95H})} + E \end{align}\]

Now we show 198 : \[\begin{align} \norm{z^{max}_l} &\leq \norm{y^{\text{max}}_l} + K (1+\norm{y^{\text{max}}_l}) \tag*{(Lemma \ref{thm:32x32stability})} \\ &\leq K + (K+1)(A \norm{y^{\text{max}}_{m(T_n)}} + B) \\ &\leq K + (K+1)(A \norm{z^{max}_{m(T_n)}} + B) \end{align}\] ◻

References↩︎

[1]
Robbins, H. and Monro, S. A stochastic approximation method. The Annals of Mathematical Statistics, 1951.
[2]
Benveniste, A., Métivier, M., and Priouret, P. Adaptive Algorithms and Stochastic Approximations. Springer, 1990.
[3]
Kushner, H. and Yin, G. G. Stochastic approximation and recursive algorithms and applications. Springer, 2003.
[4]
Borkar, V. S. Stochastic Approximation: A Dynamical Systems Viewpoint. Hindustan Book Agency, 2009.
[5]
Kiefer, J. and Wolfowitz, J. Stochastic estimation of the maximum of a regression function. Annals of Mathematical Statistics, 1952.
[6]
Sutton, R. S. Learning to predict by the methods of temporal differences. Machine Learning, 1988.
[7]
Borkar, V. S. Stochastic approximation with two time scales. Systems & Control Letters, 1997.
[8]
Sutton, R. S. and Barto, A. G. Reinforcement Learning: An Introduction (2nd Edition). MIT press, 2018.
[9]
Sutton, R. S., McAllester, D. A., Singh, S. P., and Mansour, Y. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, 1999.
[10]
Konda, V. R. Actor-Critic Algorithms. PhD thesis, Massachusetts Institute of Technology, 2002.
[11]
Lakshminarayanan, C. and Bhatnagar, S. A stability criterion for two timescale stochastic approximation schemes. Automatica, 2017.
[12]
Karmakar, P. and Bhatnagar, S. Stochastic approximation with iterate-dependent markov noise under verifiable conditions in compact state space with the stability of iterates not ensured. IEEE Transactions on Automatic Control, 2021.
[13]
Liu, S., Chen, S., and Zhang, S. The ODE method for stochastic approximation and reinforcement learning with markovian noise. Journal of Machine Learning Research, 2025.
[14]
Panda, P. and Bhatnagar, S. Two-timescale critic-actor for average reward mdps with function approximation. In Proceedings of the AAAI Conference on Artificial Intelligence, 2025.
[15]
Karmakar, P. and Bhatnagar, S. Two time-scale stochastic approximation with controlled markov noise and off-policy temporal-difference learning. Mathematics of Operations Research, 2018.
[16]
Borkar, V., Chen, S., Devraj, A., Kontoyiannis, I., and Meyn, S. The ODE method for asymptotic statistics in stochastic approximation and reinforcement learning. The Annals of Applied Probability, 2025.
[17]
Sutton, R. S., Maei, H. R., Precup, D., Bhatnagar, S., Silver, D., Szepesvári, C., and Wiewiora, E. Fast gradient-descent methods for temporal-difference learning with linear function approximation. In Proceedings of the International Conference on Machine Learning, 2009.
[18]
Yu, H. On convergence of some gradient-based temporal-differences algorithms for off-policy learning. arXiv Preprint, 2017.
[19]
Borkar, V. S. and Meyn, S. P. The O.D.E. method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization, 2000.
[20]
Mokkadem, A. and Pelletier, M. Convergence rate and averaging of nonlinear two-time-scale stochastic approximation algorithms. The Annals of Applied Probability, 2006.
[21]
Dalal, G., Szörényi, B., Thoppe, G., and Mannor, S. Finite sample analyses for TD(0) with function approximation. In Proceedings of the AAAI Conference on Artificial Intelligence, 2018.
[22]
Yaji, V. G. and Bhatnagar, S. Stochastic recursive inclusions in two timescales with nonadditive iterate-dependent markov noise. Mathematics of Operations Research, 2020.
[23]
Doan, T. T. Finite-time convergence rates of nonlinear two-time-scale stochastic approximation under markovian noise. arXiv Preprint, 2021.
[24]
Zeng, S., Doan, T. T., and Romberg, J. A two-time-scale stochastic optimization framework with applications in control and reinforcement learning. SIAM Journal on Optimization, 2024.
[25]
Borkar, V. S. Stochastic approximation with two time scales: The general case. Stochastic Processes and their Applications, 2025.
[26]
Hu, J., Doshi, V., and Eun, D. Y. Central limit theorem for two-timescale stochastic approximation with markovian noise: Theory and applications. In Proceedings of the International Conference on Artificial Intelligence and Statistics, 2024.
[27]
Sutton, R. S., Modayil, J., Delp, M., Degris, T., Pilarski, P. M., White, A., and Precup, D. Horde: a scalable real-time architecture for learning knowledge from unsupervised sensorimotor interaction. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 2011.
[28]
Liu, S. and Zhang, S. Efficient policy evaluation with offline data informed behavior policy design. In Proceedings of the International Conference on Machine Learning, 2024.
[29]
Liu, S., Chen, C., and Zhang, S. Doubly optimal policy evaluation for reinforcement learning. In Proceedings of the International Conference on Learning Representations, 2025.
[30]
Liu, S. D., Chen, C., and Zhang, S. Efficient multi-policy evaluation for reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2025.
[31]
Dulac-Arnold, G., Mankowitz, D., and Hester, T. Challenges of real-world reinforcement learning. arXiv Preprint, 2019.
[32]
Chen, C., Liu, S., and Zhang, S. Efficient policy evaluation with safety constraint for reinforcement learning. In Proceedings of the International Conference on Learning Representations, 2025.
[33]
Zhang, S. Breaking the deadly triad in reinforcement learning. PhD thesis, University of Oxford, 2022.
[34]
Sutton, R. S., Szepesvári, C., and Maei, H. A convergent \(O (n)\) algorithm for off-policy temporal-difference learning with linear function approximation. In Advances in Neural Information Processing Systems, 2008.
[35]
Barto, A. G. and Sutton, R. S. Landmark learning: An illustration of associative search. Biological Cybernetics, 1981.
[36]
Szepesvári, C. The asymptotic convergence-rate of Q-learning. In Advances in Neural Information Processing Systems, 1997.
[37]
Liu, X., Xie, Z., and Zhang, S. Extensions of Robbins-Siegmund theorem with applications in reinforcement learning. arXiv Preprint, 2025.
[38]
Tadić, V. B. On the almost sure rate of convergence of temporal-difference learning algorithms. IFAC Proceedings Volumes, 2002.
[39]
Chong, E. K., Wang, I.-J., and Kulkarni, S. R. Noise conditions for prespecified convergence rates of stochastic approximation algorithms. IEEE Transactions on Information Theory, 1999.
[40]
Tadic, V. B. On the almost sure rate of convergence of linear stochastic approximation algorithms. IEEE Transactions on Information Theory, 2004.
[41]
Kouritzin, M. A. and Sadeghi, S. Convergence rates and decoupling in linear stochastic approximation algorithms. SIAM Journal on Control and Optimization, 2015.
[42]
Koval, V. and Schwabe, R. A law of the iterated logarithm for stochastic approximation procedures in d-dimensional euclidean space. Stochastic Processes and Their Applications, 2003.
[43]
Vidyasagar, M. Convergence of stochastic approximation via martingale and converse lyapunov methods. Mathematics of Control, Signals, and Systems, 2023.
[44]
Karandikar, R. L. and Vidyasagar, M. Convergence rates for stochastic approximation: Biased noise with unbounded variance, and applications. Journal of Optimization Theory and Applications, 2024.
[45]
Qian, X., Xie, Z., Liu, X., and Zhang, S. Almost sure convergence rates and concentration of stochastic approximation and reinforcement learning with markovian noise. arXiv Preprint, 2024.
[46]
Liu, X., Xie, Z., and Zhang, S. Almost sure convergence rates of stochastic approximation and reinforcement learning via a Poisson-Moreau drift. arXiv Preprint, 2026.
[47]
Zhang, S. Towards formalizing reinforcement learning theory. arXiv Preprint, 2025.
[48]
Doan, T. T. Finite-time analysis and restarting scheme for linear two-time-scale stochastic approximation. SIAM Journal on Control and Optimization, 2021.
[49]
Doan, T. T. Nonlinear two-time-scale stochastic approximation: Convergence and finite-time performance. IEEE Transactions on Automatic Control, 2022.
[50]
Chandak, S., Haque, S. U., and Bambos, N. Finite-time bounds for two-time-scale stochastic approximation with arbitrary norm contractions and markovian noise. In Proceedings of the IEEE Conference on Decision and Control, 2025.
[51]
Konda, V. and Tsitsiklis, J. Actor-critic algorithms. In Advances in Neural Information Processing Systems, 1999.
[52]
Zhang, S., Liu, B., Yao, H., and Whiteson, S. Provably convergent two-timescale off-policy actor-critic with function approximation. In Proceedings of the International Conference on Machine Learning, 2020.
[53]
Zhang, S., Tachet des Combes, R., and Laroche, R. Global optimality and finite sample analysis of softmax off-policy actor critic under state distribution mismatch. Journal of Machine Learning Research, 2022.
[54]
Zhang, S., Wan, Y., Sutton, R. S., and Whiteson, S. Average-reward off-policy policy evaluation with function approximation. In Proceedings of the International Conference on Machine Learning, 2021.
[55]
Zhang, S., Yao, H., and Whiteson, S. Breaking the deadly triad with a target network. In Proceedings of the International Conference on Machine Learning, 2021.
[56]
Xu, T., Zou, S., and Liang, Y. Two time-scale off-policy TD learning: Non-asymptotic analysis over markovian samples. In Advances in Neural Information Processing Systems, 2019.
[57]
Yu, H. On convergence of emphatic temporal-difference learning. In Proceedings of the Conference on Learning Theory, 2015.
[58]
Zhang, S. and Whiteson, S. Truncated emphatic temporal difference methods for prediction and control. Journal of Machine Learning Research, 2022.
[59]
Tsitsiklis, J. N. and Van Roy, B. An analysis of temporal-difference learning with function approximation. IEEE Transactions on Automatic Control, 1997.

  1. \(B(x, r)\) denotes the open ball centered at \(x\) with radius \(r\).↩︎

  2. It also works if we consider a piecewise linear interpolation following [4]. The piecewise linear interpolation, however, will significantly complicate the presentation. We, therefore, follow [3] and [13] and use the piecewise constant interpolation.↩︎

  3. In this paper, we use the convention that \(\sum_{k=i}^j \alpha(k) = \sum_{k=i}^j \beta(k) = 0\) when \(j < i\).↩︎

  4. A set \(X\) is an invariant set of the ODE system 100 if and only if for every \(z \in Z\), there exists a solution \(z(t)\) to the ODE 100 such that \(z(0) = z\) and \(z(t) \in Z\) for all \(t \in (-\infty, \infty)\). If the ODE 100 is globally asymptotically stable, the only bounded invariant set is \(\require{physics} \qty{(\lambda(y), y): y \in \mathbb{R}^{d_2}}\).↩︎

  5. By \(\require{physics} \qty{z_n}\) converges to a set \(Z\), we mean \(\lim_{n \to \infty} \inf_{z\in Z} \norm{z_n - z} = 0\).↩︎