Revisiting a Design Choice in Gradient Temporal Difference Learning

## Abstract

Abstract Off-policy learning enables a reinforcement learning (RL) agent to reason counterfactually about policies that are not executed
and is one of the most important ideas in RL.
It, however,
can lead to instability when combined with function approximation and bootstrapping,
two arguably indispensable ingredients for large-scale reinforcement learning.
This is the notorious deadly triad.
Gradient Temporal Difference (GTD) is one powerful tool to solve the deadly triad.
Its success results from solving a doubling sampling issue indirectly with weight duplication or Fenchel duality.
In this paper,
we instead propose a direct method to solve the double sampling issue by simply using two samples in a Markovian data stream with an increasing gap.
The resulting algorithm is as computationally efficient as GTD but gets rid of GTD’s extra weights.
The only price we pay is a logarithmically increasing memory as time progresses.
We provide both asymptotic and finite sample analysis,
where the convergence rate is on-par with the canonical on-policy temporal difference learning.
Key to our analysis is a novel refined discretization of limiting ODEs.

## 1 Introduction

Off-policy learning (Watkins, ; Precup et al., ; Maei, ; Sutton et al., ; Li, ) is arguably one of the most important ideas in
reinforcement learning (RL, Sutton and Barto ()).
Different from on-policy learning (Sutton, ),
where an RL agent learns quantities of interest of a policy by executing the policy itself,
an off-policy RL agent learns quantities of interest of a policy by executing a different policy.
Here the policy of interest is called the target policy.
The policy that is actually executed is called the behavior policy.
This flexibility offers additional safety (Dulac-Arnold et al., ) and data efficiency (Lin, ; Sutton et al., ).

Off-policy learning, however, can lead to instability if combined with function approximation and bootstrapping,
two other arguably indispensable techniques for any large-scale RL applications.
The idea of function approximation (Sutton, ) is to represent quantities of interest with parameterized functions instead of look-up tables.
The idea of bootstrapping (Sutton, ) is to construct update targets for an estimator by using the estimator itself recursively.
This instability results from off-policy learning, function approximation, and bootstrapping is called the deadly triad (Baird, ; Sutton and Barto, ; Zhang, ).

Gradient Temporal Difference learning (GTD, Sutton et al. (, ); Maei (); Zhang et al. ()) is a family of algorithms that address the deadly triad via minimizing some objectives with stochastic gradient descent.
Provided that a linear architecture is used for approximation,
the objectives are convex and
the analytical expression of the gradient can be easily computed,
which typically involves a matrix product in the form of $\mathbb{E}\left[\hat{A}_{t}^{\top}\right]\mathbb{E}\left[\hat{A}_{t}\right]$.
Notably, the expectation here is independent of $t$.
At time step $t$,
we do have access to $\hat{A}_{t}$.
However,
we cannot use $\hat{A}_{t}^{\top}\hat{A}_{t}$ as an estimator for $\mathbb{E}\left[\hat{A}_{t}^{\top}\right]\mathbb{E}\left[\hat{A}_{t}\right]$,
since, in general cases,

$$ $\displaystyle\mathbb{E}\left[\hat{A}^{\top}_{t}\hat{A}_{t}\right]\neq\mathbb{E}\left[\hat{A}_{t}^{\top}\right]\mathbb{E}\left[\hat{A}_{t}\right].$ (1) $$

This is the notorious *double sampling* issue (Baird, ; Sutton et al., ), i.e.,
we cannot use $\hat{A}_{t}$ as samples of both expectations.
GTD algorithms address this double sampling issue *indirectly* and can be derived from two different perspectives.
The first is to approximate one expectation with an additional estimator and use $\hat{A}_{t}$ as a sample of the other expectation (Sutton et al., , ).
The second is to transform the original convex optimization problem into a convex-concave saddle-point problem via Fenchel’s duality (Liu et al., ).
Primal-dual methods are then applied to solve this convex-concave saddle-point problem,
which does not involve any double sampling issue.
Those two perspectives result in exactly the same algorithm.
The asymptotic and finite sample analyses of GTD algorithms have been well established (Sutton et al., , ; Liu et al., ; Wang et al., ; Yu, ).
Both perspectives, however, result in an extra weight vector to learn,
making GTD algorithms hard to use in practice (Sutton et al., ).

In this paper,
we propose a new *direct* method to address the double sampling issue.
The fundamental cause of the double sampling issue is that

$$ $\displaystyle\mathbb{E}\left[XY\right]=\mathbb{E}\left[X\right]\mathbb{E}\left[Y\right]$ (2) $$

typically does not hold if $X$ and $Y$ are not independent – clearly $\hat{A}_{t}$ is not independent with itself.
However,
suppose that $\quantity{\hat{A}_{t}}$ is generated by an underlying Markov Decision Process,
the correlation between $\hat{A}_{t}$ and $\hat{A}_{t+\tau}$ diminishes to zero geometrically fast with the increase of $\tau$ under some mild conditions (see, e.g., Vempala ()).
Motivated by this,
we propose to use $\hat{A}^{\top}_{t+\tau}\hat{A}_{t}$ as an estimator for $\mathbb{E}\left[\hat{A}_{t}^{\top}\right]\mathbb{E}\left[\hat{A}_{t}\right]$.
Of course,
we need to keep $\tau$ increasing because the correlation diminishes only asymptotically.
But we prove that $\tau$ does not need to increase so fast.
In fact,
setting $\tau$ to $\Omega\left(\ln^{2}(t)\right)$ is sufficient to guarantee convergence.
We term our new method Direct GTD.
Different from GTD,
Direct GTD does not need the additional weight.
The price we pay is a logarithmically increasing memory as time progresses,
which we argue is a reasonably small overhead.
Our asymptotic analysis of Direct GTD is inspired by the proof structure of Proposition 4.7 in Bertsekas and Tsitsiklis () but is much more involved to work with the increasing gap (i.e., $\tau$).
Key to our analysis is a novel refined discretization of limiting ODEs.
We also provide a finite sample analysis of a variant of Direct GTD,
which involves an additional projection operator at every step like Bhandari et al. (); Zou et al. ().
Our convergence rate is on par with the canonical convergence rate of the on-policy TD with linear function approximation established in Bhandari et al. (),
up to a logarithmic factor.

## 2 Background

In this paper,
all vectors are columns.
A matrix $M$ (not necessarily symmetric) is said to be positive definite (p.d.) if there exists a constant $\lambda>0$ such that $x^{\top}Mx\geq\lambda x^{\top}x$ holds for any $x$.
$M$ is negative definite (n.d.) if and only if $-M$ is p.d.
For a vector $x$ and a p.d. matrix $M$,
we use $\norm{x}_{M}\doteq\sqrt{x^{\top}Mx}$
to denote the vector norm induced by $M$.
We also use $\norm{\cdot}_{M}$ to denote the corresponding induced matrix norm.
We use $\norm{\cdot}$ as shorthand for $\norm{\cdot}_{I}$ where $I$ is the identity matrix,
i.e.,
$\norm{\cdot}$ is the standard $\ell_{2}$-norm.
We use $diag(x)$ to denote a diagonal matrix whose diagonal entry is $x$ and write
$\norm{\cdot}_{x}$ as shorthand for $\norm{\cdot}_{diag(x)}$ when $diag(x)$ is p.d.
We use functions and vectors interchangeably when it does not confuse,
e.g., if $f$ is a function from $\mathcal{S}$ to $\mathbb{R}$,
we also use $f$ to denote a vector in $\mathbb{R}^{|\mathcal{S}|}$,
whose $s$-th element is $f(s)$.

We consider an infinite horizon Markov Decision Process (MDP, Puterman ()) with a finite state space $\mathcal{S}$,
a finite action space $\mathcal{A}$,
a reward function $r:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$,
a transition function $p:\mathcal{S}\times\mathcal{S}\times\mathcal{A}\to[0,1]$,
and a discount factor $\gamma\in[0,1)$.
At time step 0,
a state $S_{0}$ is sampled from some initial distribution $p_{0}$.
At time step $t$,
an agent at a state $S_{t}$ takes an action $A_{t}\sim\pi(\cdot|S_{t})$.
Here $\pi:\mathcal{A}\times\mathcal{S}\to[0,1]$ is the policy being followed.
A reward $R_{t+1}\doteq r(S_{t},A_{t})$ is then emitted, and a successor state $S_{t+1}$ is sampled from $p(\cdot|S_{t},A_{t})$.

The return at time step $t$ is defined as

$$ $\displaystyle G_{t}\doteq\sum_{i=0}^{\infty}\gamma^{i}R_{t+i+1},$ (3) $$

which allows us to define the state value function as

$$ $\displaystyle v_{\pi}(s)\doteq\mathbb{E}_{\pi,p}\left[G_{t}|S_{t}=s\right].$ (4) $$

The value function $v_{\pi}$ is the unique fixed point of the Bellman operator

$$ $\displaystyle\mathcal{T}_{\pi}v\doteq r_{\pi}+\gamma P_{\pi}v.$ (5) $$

Here $r_{\pi}\in\mathbb{R}^{{|\mathcal{S}|}}$ is the reward vector induced by $\pi$, defined as $r_{\pi}(s)\doteq\sum_{a}\pi(a|s)r(s,a)$.
$P_{\pi}\in\mathbb{R}^{{|\mathcal{S}|}\times{|\mathcal{S}|}}$ is the transition matrix induced by $\pi$,
i.e.,
$P_{\pi}(s,s^{\prime})\doteq\sum_{a}\pi(a|s)p(s^{\prime}|s,a)$.

Estimating $v_{\pi}$ is one of the most important tasks in RL and is called policy evaluation.
Temporal Difference learning (TD, Sutton ()) is one of the most powerful tools for policy evaluation.
Let $V$ be our estimate for $v_{\pi}$,
then TD updates $V$ iteratively as

$$ $\displaystyle V(S_{t})\leftarrow V(S_{t})+\alpha_{t}\left(R_{t+1}+\gamma V(S_{t+1})-V(S_{t})\right),$ (6) $$

where $\quantity{\alpha_{t}}$ is a sequence of learning rate.
Under mild conditions,
the estimate $V$ converges to $v_{\pi}$ almost surely (Bertsekas and Tsitsiklis, ).
In TD,
the update target for $V(S_{t})$ is constructed as $R_{t+1}+\gamma V(S_{t+1})$,
which includes the estimate $V$ itself.
This is called bootstrapping.

When the state space $\mathcal{S}$ is too large,
maintaining a look-up table $V$ is impractical, and one thus resorts to approximate methods.
In particular,
consider a feature function $x:\mathcal{S}\to\mathbb{R}^{K}$ that maps a state $s$ to a $K$-dimensional feature $x(s)$.
We then use $x(s)^{\top}w$ to approximate $v_{\pi}(s)$.
Here $w\in\mathbb{R}^{K}$ is the learnable weight, and typically $K$ is much smaller than ${|\mathcal{S}|}$.
Let $X\in\mathbb{R}^{{|\mathcal{S}|}\times K}$ be the feature matrix,
whose $s$-th row is $x(s)^{\top}$.
The goal is then to adapt $w$ such that $Xw\approx v_{\pi}$.
Such approximation architecture is called linear function approximation.
Linear TD (Sutton, ) updates $w$ iteratively as

$$ $\displaystyle w_{t+1}\doteq w_{t}+\alpha_{t}\left(R_{t+1}+\gamma x_{t+1}^{\top}w_{t}-x_{t}^{\top}w_{t}\right)x_{t}.$ (7) $$

Here we use $x_{t}\doteq x(S_{t})$ as shorthand.
Under mild conditions,
the iterates $\quantity{w_{t}}$ in ([7](#S2.E7)) converge to $w_{\infty}$ (Tsitsiklis and Roy, ),
the minimizer of the Mean Squared Projected Bellman Error (MSPBE) defined as

$$ $\displaystyle\text{MSPBE}(w)\doteq\norm{\Pi_{d_{\pi}}\left(\mathcal{T}_{\pi}Xw-Xw\right)}_{d_{\pi}}^{2}.$ (8) $$

Here $d_{\pi}$ denotes the stationary state distribution of the Markov chain induced by $\pi$.
$\Pi_{d_{\pi}}$ is a projection operator that projects any vector in $\mathbb{R}^{|\mathcal{S}|}$ to $\text{col}(X)$,
the column space of $X$,
i.e.,

$$ $\displaystyle\Pi_{d_{\pi}}v\doteq\arg\min_{v^{\prime}\in\text{col}(X)}\norm{v^{\prime}-v}_{d_{\pi}}^{2}.$ (9) $$

The update in ([7](#S2.E7)) can be rearranged as

$$ $\displaystyle w_{t+1}=w_{t}+\alpha_{t}\left(x_{t}\left(\gamma x_{t+1}^{\top}-x_{t}^{\top}\right)w_{t}+x_{t}R_{t+1}\right).$ (10) $$

If $\quantity{w_{t}}$ converges,
the expected update must diminish.
The limiting point $w_{\infty}$
therefore,
must satisfy

$$ $\displaystyle\!\!\!\!\!\!\!\!\mathbb{E}_{s\sim d_{\pi}(\cdot),a\sim\pi(\cdot|s),s^{\prime}\sim p(\cdot|s,a)}\left[x(s)\left(\gamma x(s^{\prime})-x(s)\right)^{\top}\right]w_{\infty}+\mathbb{E}_{s\sim d_{\pi}(\cdot),a\sim\pi(\cdot|s)}\left[r(s,a)x(s)\right]=0.$ (11) $$

See Tsitsiklis and Roy () for formal proof.

It is common the case that we want to estimate $v_{\pi}$ without actually sampling actions from $\pi$,
due to various concerns, e.g.,
safety (Dulac-Arnold et al., ), data efficiency (Lin, ; Sutton et al., ).
Off-policy learning makes this possible.
In particular,
instead of sampling $A_{t}$ according $\pi(\cdot|S_{t})$,
off-policy method samples $A_{t}$ according to another policy $\mu$.
Here,
the policy $\pi$ is called the target policy and the policy $\mu$ is called the behavior policy.
*For the rest of the paper,
we always consider the off-policy setting*,
i.e.,

$$ $\displaystyle A_{t}\sim\mu(\cdot|S_{t}),R_{t+1}=r(S_{t},A_{t}),S_{t+1}\sim p(\cdot|S_{t},A_{t}).$ (12) $$

Since the behavior policy $\mu$ is different from the target policy $\pi$,
importance sampling ratio is used to account for this discrepancy,
which is defined as

$$ $\displaystyle\rho(s,a)\doteq\frac{\pi(a|s)}{\mu(a|s)}.$ (13) $$

In particular, we use as shorthand $\rho_{t}\doteq\rho(S_{t},A_{t})$.
In the off-policy setting,
the TD update ([6](#S2.E6)) becomes

$$ $\displaystyle V(S_{t})\leftarrow V(S_{t})+\alpha_{t}\rho_{t}\left(R_{t+1}+\gamma V(S_{t+1})-V(S_{t})\right).$ (14) $$

Under mild conditions,
the $V$ in off-policy TD converges to $v_{\pi}$ almost surely (Bertsekas and Tsitsiklis, ).
Correspondingly,
linear TD ([7](#S2.E7)) in the off-policy setting becomes

$$ $\displaystyle w_{t+1}\doteq w_{t}+\alpha_{t}\rho_{t}\left(R_{t+1}+\gamma x_{t+1}^{\top}w_{t}-x_{t}^{\top}w_{t}\right)x_{t}.$ (15) $$

Unfortunately,
the possible divergence of off-policy linear TD ([15](#S2.E15)) is well documented (Baird, ; Sutton et al., ; Sutton and Barto, ).
This divergence exercises the deadly triad.

Similar to ([11](#S2.E11)),
if off-policy linear TD ([15](#S2.E15)) converged,
it would converge to a $w_{*}$ (Sutton et al., ) satisfying

$$ $\displaystyle Aw_{*}+b=0,$ (16) $$

where

$$ $\displaystyle A\doteq$ $\displaystyle\mathbb{E}_{s\sim d_{\mu}(\cdot),a\sim\pi(\cdot|s),s^{\prime}\sim p(\cdot|s,a)}\left[x(s)\left(\gamma x(s^{\prime})-x(s)\right)^{\top}\right]=X^{\top}D_{\mu}(\gamma P_{\pi}-I)X$ (17) $\displaystyle b\doteq$ $\displaystyle\mathbb{E}_{s\sim d_{\mu}(\cdot),a\sim\pi(\cdot|s)}\left[r(s,a)x(s)\right]=X^{\top}D_{\mu}r_{\pi}.$ (18) $$

Here $d_{\mu}$ is the stationary distribution of the Markov chain induced by the behavior policy $\mu$,
and $D_{\mu}\doteq diag(d_{\mu})$.

Instead of using off-policy linear TD ([15](#S2.E15)),
one natural approach for policy evaluation in the off-policy setting is then to solve

$$ $\displaystyle Aw+b=0$ (19) $$

directly,
probably with stochastic gradient descent on the objective

$$ $\displaystyle L(w)\doteq\norm{Aw+b}^{2}.$ (20) $$

The objective $L(w)$ dates back to Yao and Liu () and is termed as *the norm of the expected TD update* (NEU) in Sutton et al. ().
The gradient of $L(w)$ can be easily computed (Yao and Liu, ; Sutton et al., ) as

$$ $\displaystyle\nabla L(w)=2A^{\top}(Aw+b).$ (21) $$

One can, therefore, update $w$ as

$$ $\displaystyle w_{t+1}\doteq w_{t}-\alpha_{t}A^{\top}(Aw_{t}+b).$ (22) $$

Since we do not know $A$ and $b$,
we need to estimate $A^{\top}(Aw_{t}+b)$ with samples.
According to the convergence theorem (Levin and Peres, ) or the strong law of large number on stationary processes (Doob, ),

$$ $\displaystyle\hat{A}_{t}\doteq$ $\displaystyle\rho_{t}x_{t}\left(\gamma x_{t+1}-x_{t}\right)^{\top},$ (23) $\displaystyle\hat{b}_{t}\doteq$ $\displaystyle\rho_{t}R_{t+1}x_{t}$ (24) $$

are good estimates of $A$ and $b$ respectively since they are unbiased asymptotically.
However,
$\hat{A}_{t}^{\top}\hat{A}_{t}$ is *not* a good estimator for $A^{\top}A$
due to the aforementioned double sampling issue.

Sutton et al. () attack this issue by introducing a second approximator.
Namely,
since

$$ $\displaystyle\nabla L(w)=A^{\top}(Aw+b)=A^{\top}X^{\top}D_{\mu}\left(\mathcal{T}_{\pi}(Xw)-Xw\right),$ (25) $$

Sutton et al. () use $\nu\in\mathbb{R}^{K}$ to approximate $X^{\top}D_{\mu}\left(\mathcal{T}_{\pi}(Xw)-Xw\right)$.
For a given $w$,
the learning of $\nu$ reduces to a weighted least square.
Sutton et al. () then use $\hat{A}_{t}^{\top}\nu_{t}$ as an estimate of $\nabla L(w)$.
The resulting GTD algorithm makes the following iterative updates in the off-policy setting with the sequential data $\quantity{S_{0},A_{0},R_{1},S_{1},\dots}$:

$$ $\displaystyle\delta_{t}\doteq$ $\displaystyle R_{t+1}+\gamma x_{t+1}^{\top}w_{t}-x_{t}^{\top}w_{t},$ (26) $\displaystyle\nu_{t+1}\doteq$ $\displaystyle\nu_{t}+\alpha_{t}\left(\rho_{t}\delta_{t}x_{t}-\nu_{t}\right),$ (27) $\displaystyle w_{t+1}\doteq$ $\displaystyle w_{t}+\alpha_{t}\rho_{t}(x_{t}-\gamma x_{t+1})x^{\top}_{t}\nu_{t}.$ (28) $$

Following Liu et al. (),
we can also apply Fenchel’s duality

$$ $\displaystyle u^{\top}u=\max_{\nu}2u^{\top}\nu-\nu^{\top}\nu$ (29) $$

to $L(w)$ and get

$$ $\displaystyle L(w)=\max_{\nu}2(Aw+b)^{\top}\nu-\nu^{\top}\nu.$ (30) $$

The original convex optimization problem of minimizing $L(w)$ now reduces to finding the saddle-point of the convex-concave function

$$ $\displaystyle L(w,\nu)\doteq 2(Aw+b)^{\top}\nu-\nu^{\top}\nu.$ (31) $$

Applying primal-dual methods (Nemirovski et al., ) then leads to the same GTD update ([26](#S2.E26)).
The convergence and finite sample analysis of GTD in ([26](#S2.E26)) is well established (Sutton et al., , ; Liu et al., ; Wang et al., ; Yu, ).

## 3 Direct Gradient Temporal Difference Learning

GTD algorithms address the double sampling issue indirectly by employing an additional weight vector.
We instead use two samples directly.
As discussed in Section [1](#S1),
we use $\hat{A}_{t+f(t)}^{\top}\left(\hat{A}_{t}w_{t}+\hat{b}_{t}\right)$ as an estimate for $A^{\top}\left(Aw+b\right)$,
yielding the Direct GTD algorithm:

$$ $\displaystyle w_{t+1}\doteq$ $\displaystyle w_{t}+\alpha_{t}\rho_{t+f(t)}\left(x_{t+f(t)}-\gamma x_{t+f(t)+1}\right)x^{\top}_{t+f(t)}\rho_{t}\left(R_{t+1}+\gamma x_{t+1}^{\top}w_{t}-x_{t}^{\top}w_{t}\right)x_{t},$ (32) $$

where the data stream ([32](#S3.E32)) operates on is described in ([12](#S2.E12)) and $f:\mathbb{N}\to\mathbb{N}$ is the *gap function*.
We require $f$ being monotonically increasing.
In Direct GTD ([32](#S3.E32)),
the term $\rho_{t+f(t)}\rho_{t}\left(R_{t+1}+\gamma x_{t+1}^{\top}w_{t}-x_{t}^{\top}w_{t}\right)$ is a scalar,
the computational complexity of which is only $\mathcal{O}\left(K\right)$.
If we compute the remaining term $\left(x_{t+f(t)}-\gamma x_{t+f(t)+1}\right)x^{\top}_{t+f(t)}x_{t}$ from right to left,
the computational complexity is still $\mathcal{O}\left(K\right)$.
In other words,
the computational complexity of Direct GTD is the same as existing GTD methods.
The price we pay here is that we cannot start Direct GTD until the $\left(f(0)+1\right)$-th step, and we need to maintain a memory storing

$$ $\displaystyle x_{t},\rho_{t},x_{t+1},\rho_{t+1},\dots x_{f(t)},\rho_{f(t)},x_{f(t)+1}.$ (33) $$

The size of this memory is $\mathcal{O}\left(f(t)\right)$.
We will soon prove that the memory can be as small as $\Omega(\ln^{2}(t))$.
We argue that this memory overhead is reasonably small.
The gain is that we now do not need an additional weight vector,
making the algorithm easy to use.

## 4 Asymptotic Convergence Analysis

In this section,
we provide an asymptotic convergence analysis of Direct GTD ([32](#S3.E32)).
The major technical challenge lies in the increasing gap function.
If $f(t)$ was a constant function, say $f(t)\equiv t_{0}$,
then one would be able to easily analyze Direct GTD via constructing an augmented Markov chain with states

$$ $\displaystyle Y_{t}\doteq\quantity{S_{t},A_{t},\dots,S_{t+t_{0}},A_{t+t_{0}},S_{t+t_{0}+1}}$ (34) $$

evolving in a finite space $(\mathcal{S}\times\mathcal{A})^{t_{0}+1}\times\mathcal{S}$.
Suppose the origin Markov chain $\quantity{S_{t}}$ is ergodic,
this new chain $\quantity{Y_{t}}$ would also be ergodic.
Classical convergence results (e.g., Proposition 4.7 of Bertsekas and Tsitsiklis ()) can then take over.
When $f(t)$ is increasing,
the augmented chain, however, would be

$$ $\displaystyle Y_{t}\doteq\quantity{S_{t},A_{t},\dots,S_{t+f(t)},A_{t+f(t)},S_{t+f(t)+1}}$ (35) $$

which evolves in an infinite space

$$ $\displaystyle\cup_{i=1}^{\infty}(\mathcal{S}\times\mathcal{A})^{i}\times\mathcal{S}.$ (36) $$

Even if the origin chain $\quantity{S_{t}}$ is ergodic,
the new chain $\quantity{Y_{t}}$ still behaves poorly in that it never visits the same augmented state twice.
This rules out the possibility of applying most,
if not all,
existing convergence results in the stochastic approximation community (e.g., Benveniste et al. (); Kushner and Yin (); Borkar ()).
*Our main technical novelty lies in a refined discretization of ordinary differential equations (ODEs) to deal with this increasing gap.*

To better understand our technical novelty,
we first give a holistic view of standard ODE-based convergence analysis,
following Bertsekas and Tsitsiklis ().
Consider a general stochastic approximation algorithm

$$ $\displaystyle w_{t+1}=w_{t}+\alpha_{t}h(w_{t},Y_{t}).$ (37) $$

Consider a sequence $\quantity{t_{m}}_{m=0,1,\dots}$ of increasing time steps.
Expanding the right-hand side of ([37](#S4.E37)) yields

$$ $\displaystyle w_{t_{m+1}+1}=w_{t_{m}}+\sum_{i=t_{m}}^{t_{m+1}}\alpha_{i}h(w_{i},Y_{i}).$ (38) $$

Assuming the learning rates $\quantity{\alpha_{i}}$ are small enough,
then $w_{i}$ changes little for $i\in[t_{m},t_{m+1}]$
and the randomness in $\quantity{Y_{i}}$ is averaged out.
This leads to the following approximation

$$ $\displaystyle h(w_{i},Y_{i})\approx\bar{h}(w_{t_{m}}),$ (39) $$

where $\bar{h}$ is the expectation of $h$ w.r.t. some proper distribution.
Consequently,

$$ $\displaystyle w_{t_{m+1}+1}\approx w_{t_{m}}+h(w_{t_{m}})\sum_{i=t_{m}}^{t_{m+1}}\alpha_{i}.$ (40) $$

In the standard analysis (e.g., Benveniste et al. (); Bertsekas and Tsitsiklis (); Kushner and Yin (); Borkar ()),
the sequence $\quantity{t_{m}}$ is selected such that $\forall m,$

$$ $\displaystyle\sum_{i=t_{m}}^{t_{m+1}}\alpha_{i}\approx T,$ (41) $$

where $T$ is some *fixed* constant.
So we have

$$ $\displaystyle w_{t_{m+1}+1}\approx w_{t_{m}}+h(w_{t_{m}})T.$ (42) $$

This corresponds to Euler’s discretization of the ODE

$$ $\displaystyle\derivative{w(t)}{t}=h(w(t))$ (43) $$

with an interval $T$.
The behavior of the stochastic and discrete iterates $\quantity{w_{t}}$ generated by ([37](#S4.E37)) can then be associated
with a deterministic and continuous trajectory of ([43](#S4.E43)).
This approach has dominated existing ODE-based convergence analysis for more than twenty years (see, e.g., Benveniste et al. (); Bertsekas and Tsitsiklis (); Kushner and Yin (); Borkar ()).
However,
such a discretization cannot help analyze our Direct GTD,
mostly because we have an increasing gap function and
the augmented Markov chain (cf. ([36](#S4.E36))) is much more complicated than standard ones (cf. ([35](#S4.E35))).
We address this challenge by conducting a refined discretization.
Instead of performing discretization w.r.t. a fixed interval $T$ (cf. ([41](#S4.E41))),
we perform a refined discretization w.r.t. a sequence of intervals $\quantity{T_{m}}$,
namely,

$$ $\displaystyle\sum_{i=t_{m}}^{t_{m+1}}\alpha_{i}\approx T_{m}.$ (44) $$

This is the most important ingredient in our convergence analysis.
Designing a proper $\quantity{T_{m}}$ according to $f(t)$ and $\quantity{\alpha_{t}}$ is the major challenge here.
On the one hand, $\quantity{T_{m}}$ has to diminish fast enough such that the noise can average out properly.
On the other hand, $\quantity{T_{m}}$ has to diminish slowly enough such that the gap between $t_{m}$ and $t_{m+1}$ actually increases to account for the increase of $f(t)$.
Carefully balancing the learning rates $\quantity{\alpha_{t}}$, the endpoints $\quantity{t_{m}}$,
and the intervals $\quantity{T_{m}}$ is the major technical challenge.

Besides the refined discretization, another important ingredient is the mixing of joint state distributions in Markov chains.
Consider a general Markov chain $\quantity{Y_{t}}$.
Assume the chain is ergodic and let $d_{\mathcal{Y}}$ denote its invariant distribution.
Then the convergence theorem (see, e.g., Levin and Peres ()) yields

$$ $\displaystyle\lim_{t\to\infty}\Pr(Y_{t}=y)\to d_{\mathcal{Y}}(y).$ (45) $$

This convergence is uniform in $y$ and is geometrically fast.
Exploiting this convergence,
we are able to prove the convergence of joint state distributions, i.e.,

$$ $\displaystyle\lim_{t\to\infty}\Pr(Y_{t}=y,Y_{t+f(t)}=y^{\prime})\to d_{\mathcal{Y}}(y)d_{\mathcal{Y}}(y^{\prime}).$ (46) $$

Intuitively,
this means the dependence between $Y_{t}$ and $Y_{t+f(t)}$ diminishes as $t$ goes to infinity (cf. Lemma 7.1 in Vempala ()).
In Direct GTD,
this means
the bias resulting from estimating $A^{\top}A$ with $\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}$ diminishes gradually.

Having introduced the two main ingredients in our analysis,
we are now ready to formally describe our main results.
We start with (standard) assumptions we make.

###### Assumption 4.1

The Markov chain induced by the behavior policy $\mu$ is finite, irreducible, and aperiodic.
The behavior policy $\mu$ covers the target policy $\pi$, i.e., $\forall(s,a),\pi(a|s)>0\implies\mu(a|s)>0$.

###### Assumption 4.2

The feature matrix $X$ has a full column rank.
The matrix $A$ defined in ([17](#S2.E17)) is nonsingular.

Assumptions [4.1](#S4.assu_counter1) and [4.2](#S4.assu_counter2) are standard in the analysis of linear TD methods (see, e.g., Tsitsiklis and Roy (); Wang et al. ()).

###### Assumption 4.3

The learning rates $\quantity{\alpha_{t}}$ have the form of

$$ $\displaystyle\alpha_{t}=\frac{C_{\alpha}}{(t+1)^{-\nu}}$ (47) $$

for some $\nu\in(\frac{2}{3},1]$

Assumption [4.3](#S4.assu_counter3) considers learning rates of a specific form.
This is mostly for ease of presentation.

###### Assumption 4.4

The gap function $f(t):\mathbb{N}\to\mathbb{N}$ is monotonically increasing and satisfies $\forall\chi\in[0,1)$,

$$ $\displaystyle\sum_{t=0}^{\infty}\chi^{f(t)}<\infty.$ (48) $$

Moreover, there exist constants $\tau\in(0,\frac{3\nu-2}{2\nu})$ and $C_{\tau}>0$ such that $\forall t$,

$$ $\displaystyle f(t)\leq C_{\tau}\alpha_{t}^{-\tau}.$ (49) $$

Assumption [4.4](#S4.assu_counter4) is the most “unnatural” assumption we make and prescribes how the gap function should be chosen.
Intuitively,
those conditions prevent the gap function from growing too fast.
Despite seemingly complicated,
Lemma [15](#Thmtheorem15) confirms that simply setting

$$ $\displaystyle f(t)=\lfloor h(t)\ln(t+1)\rfloor$ (50) $$

with some non-negative increasing function $h(\cdot)$ converging to $\infty$ as $t\to\infty$
fulfills the first condition of Assumption [4.4](#S4.assu_counter4).
Here $\lfloor x\rfloor$ is the floor function denoting the largest integer that is smaller than $x$.
A concrete example satisfying Assumption [4.3](#S4.assu_counter3) and [4.4](#S4.assu_counter4) is

$$ $\displaystyle\nu=$ $\displaystyle 1,h(t)=\ln(t+1),f(t)=\lfloor\ln^{2}(t+1)\rfloor,\tau=0.1.$ (51) $$

We are now ready to present our main results.

###### Theorem 1

Let Assumptions [4.1](#S4.assu_counter1), [4.2](#S4.assu_counter2), [4.3](#S4.assu_counter3), & [4.4](#S4.assu_counter4) hold.
Then the iterates $\quantity{w_{t}}$ generated by Direct GTD ([32](#S3.E32)) satisfies

$$ $\displaystyle\lim_{t\to\infty}w_{t}=w_{*}\mbox{\quad almost surely,\quad}$ (52) $$

where $w_{*}$ is the TD fixed point defined in ([16](#S2.E16)).

The proof of Theorem [1](#Thmtheorem1) is provided in Section [A.2](#A1.SS2).
Theorem [1](#Thmtheorem1) confirms that asymptotically,
Direct GTD finds the same solution as the canonical GTD methods.

###### Assumption 4.1

###### Assumption 4.2

###### Assumption 4.3

###### Assumption 4.4

###### Theorem 1

## 5 Finite Sample Analysis

Theorem [1](#Thmtheorem1) confirms the asymptotic convergence of Direct GTD.
The price we pay is a memory of size $\Omega\left(\ln t\right)$ (cf. ([33](#S3.E33))).
If the convergence is fast, e.g., $\mathcal{O}\left(\frac{1}{t}\right)$,
the memory increases reasonably slowly, and we argue that the memory overhead is acceptable.
If,
however,
the convergence is too slow,
the memory may still become too large.
To make sure that Direct GTD is a practical algorithm,
therefore,
requires performing a finite sample analysis.
To this end,
we, in this section, perform finite sample analysis of a variant of Direct GTD,
which adopts an additional projection operator and updates $\quantity{w_{t}}$ iteratively as

$$ $\displaystyle\!\!\!\!\!\!\!\!\!\!\!w_{t+1}\doteq$ $\displaystyle\Gamma\left(w_{t}+\alpha_{t}\rho_{t+f(t)}\left(x_{t+f(t)}-\gamma x_{t+f(t)+1}\right)x^{\top}_{t+f(t)}\rho_{t}\left(R_{t+1}+\gamma x_{t+1}^{\top}w_{t}-x_{t}^{\top}w_{t}\right)x_{t}\right),$ (53) $$

where $\Gamma:\mathbb{R}^{K}\to\mathbb{R}^{K}$ is a projection operator onto a ball of a radius $B$, i.e.,

$$ $\displaystyle\Gamma(w)\doteq\begin{cases}w,&\norm{w}\leq B\\ \frac{B}{\norm{w}}w,&\norm{w}>B\end{cases}.$ (54) $$

The update ([53](#S5.E53)) differs from Direct GTD ([32](#S3.E32)) only in that it adopts an additional projection operator $\Gamma$.
We, therefore, call it *Projected Direct GTD*.
We show that the convergence rate of our off-policy Projected Direct GTD is on-par with the convergence rate of the canonical on-policy linear TD in Bhandari et al. (),
up to a few logarithm terms.

Notably, adding a projection operator is a common practice in finite sample analysis of TD algorithms (see, e.g., Liu et al. (); Wang et al. (); Bhandari et al. (); Zou et al. ()) to simplify the presentation.
Techniques from Srikant and Ying () can indeed be used to perform finite sample analysis of the original Direct GTD directly.
This, however, complicates the presentation, and we, therefore, leave it for future work.
We now present our main results.

###### Theorem 2

Let $B$ in ([54](#S5.E54)) be large enough such that $\norm{w_{*}}\leq B$.
Consider learning rates in the form of

$$ $\displaystyle\alpha_{t}=\frac{C_{\alpha}}{t+1}.$ (55) $$

Let Assumptions [4.1](#S4.assu_counter1), [4.2](#S4.assu_counter2), & [4.4](#S4.assu_counter4) hold.
Then there exists a constant $C_{0}$ such that as long as $C_{\alpha}\geq C_{0}$,
the iterates $\quantity{w_{t}}$ generated by Projected Direct GTD ([53](#S5.E53)) satisfy

$$ $\displaystyle\mathbb{E}\left[\norm{w_{t}-w_{*}}^{2}\right]=\mathcal{O}\left(\frac{f(t)\ln(t)}{t}\right).$ (56) $$

The proof of Theorem [2](#Thmtheorem2) is provided in Section [A.3](#A1.SS3) and is a refined analysis of Bhandari et al. ().
Theorem [2](#Thmtheorem2),
together with ([50](#S4.E50)),
together confirms that the convergence rate of Projected Direct GTD is reasonably fast.
In particular,
if the configuration in ([51](#S4.E51)) is used,
the convergence rate of Direct GTD is on-par with the on-policy linear TD (Bhandari et al., ) up to logarithmic factors.

###### Theorem 2

## 6 Direct GTD with I.I.D. Data

So far, we consider only Markovian data ([12](#S2.E12)).
Most GTD works,
however,
start with i.i.d. data (Sutton et al., , ).
In other words,
we are presented with a data stream

$$ $\displaystyle\quantity{(S_{k},A_{k},R_{k},S_{k}^{\prime})}_{k=0,1,\dots},$ (57) $$

where

$$ $\displaystyle S_{k}\sim d_{\mu},A_{k}\sim\mu(\cdot|S_{k}),R_{k}\doteq r(S_{k},A_{k}),S_{k}^{\prime}\sim p(\cdot|S_{k},A_{k}).$ (58) $$

Direct GTD with i.i.d. data is trivial.
Starting from ([22](#S2.E22)),
one can use $\iota_{k}\doteq(S_{k},A_{k},R_{k},S_{k}^{\prime})$ to estimate $A^{\top}$ and
use $\iota_{k+1}\doteq(S_{k+1},A_{k+1},R_{k+1},S_{k+1}^{\prime})$ to estimate $A$.
The product of the two estimates is an unbiased estimation of $A^{\top}A$ since $\iota_{k}$ and $\iota_{k+1}$ are independent of each other.
In particular,
this would lead to the following update:

$$ $\displaystyle k=$ $\displaystyle 2t,$ (59) $\displaystyle\Delta_{t,1}=$ $\displaystyle\frac{\pi(A_{k}|S_{k})}{\mu(A_{k}|S_{k})}\left(x(S_{k})-\gamma x(S_{k}^{\prime})\right)x^{\top}(S_{k}),$ (60) $\displaystyle\Delta_{t,2}=$ $\displaystyle\frac{\pi(A_{k+1}|S_{k+1})}{\mu(A_{k+1}|S_{k+1})}\left(R_{k+1}+\gamma x^{\top}(S_{k+1}^{\prime})w_{t}-x^{\top}(S_{k+1})w_{t}\right)x(S_{k+1}),$ (61) $\displaystyle w_{t+1}=$ $\displaystyle w_{t}+\alpha_{t}\Delta_{t,1}\Delta_{t,2}.$ (62) $$

This idea here has also been explored in Zhang et al. () to address a similar double sampling issue.
Thanks to the i.i.d. nature of the data,
the asymptotic convergence and finite sample analysis of ([59](#S6.E59)) is a straightforward copy of those in Liu et al. (); Sutton et al. (, ); Zhang et al. ().
We, therefore, omit them to avoid verbatim repetition.

The most common criticism is that it is not clear where to get those i.i.d. data
since, after all, the canonical RL framework is Markovian (Sutton and Barto, ).
We, therefore, mainly focus on the Markovian setting in this work,
which is much more practical than the i.i.d. setting.
Notably, if the i.i.d. data is indeed available,
the Direct GTD algorithm can be easily extended to the more broad Preconditioned TD (Yao and Liu, ) algorithms.
Namely,
we can add a preconditioner $M$
in the update ([22](#S2.E22)),
yielding

$$ $\displaystyle w_{t+1}\doteq w_{t}-\alpha_{t}MA^{\top}(Aw_{t}+b).$ (63) $$

There are multiple choices for this $M$.
We refer the reader to Yao and Liu () for more details.
Estimating $MA^{\top}A$ is now a triple sampling problem,
solving, which remains trivial if i.i.d. data is available.
Different $M$ may result in different performances,
which is out of the scope of this work and is left for future work.

## 7 Experiments

Figure: Figure 1: Baird’s counterexample from Chapter 11.2 of Sutton and Barto (). The figure is taken from Zhang et al. (). There are 7 states, and for each state, there are 2 actions: dashed and solid. The solid action always leads to state 7, whereas the dashed actions lead to state 1-6 with equal probability. The reward is 0 throughout, and the discount factor is 0.99. The initial state is chosen at random with equal likelihood, and the initial weight vector is set to $(1,1,1,1,1,1,10,1)^{\top}$.
Refer to caption: /html/2308.01170/assets/img/baird.png

Figure: Figure 2: The NEU of Direct GTD compared with those of TD and GTD. The curves are averaged over 30 independent runs, and the shaded areas correspond to the standard errors.
Refer to caption: /html/2308.01170/assets/img/convergence1.png

Figure: Figure 3: The NEUs of Direct GTD with different gap functions. The curves are averaged over 30 independent runs, and the shaded areas correspond to the standard errors.
Refer to caption: /html/2308.01170/assets/img/convergence2.png

We now empirically compare Direct GTD ([32](#S3.E32)) with naive off-policy linear TD ([15](#S2.E15)) and GTD ([26](#S2.E26)) on the notorious Baird’s counterexample (Baird, ),
illustrated in Figure [1](#S7.F1).
We use a constant learning rate for each algorithm,
tuned from $\quantity{0.001,0.005,0.01,0.05}$,
minimizing the NEU ($\text{NEU(w)}\doteq\norm{Aw+b}$) at the end of the training,
which is $10^{4}$ steps.
We found the best-performing learning rate is always $0.001$.
The results are reported in Figure [2](#S7.F2) and [3](#S7.F3).

In Figure [2](#S7.F2),
the gap function in Direct GTD is set to $f(t)=\lfloor\ln^{2}(t+1)\rfloor$ as suggested in ([51](#S4.E51)).
The naive off-policy linear TD diverges as expected (Baird, ; Sutton and Barto, ).
Both GTD and Direct GTD converge as expected.
It is, however, worth mentioning that
the NEU of Direct GTD drops faster than that of GTD at the beginning, and the learning curve of Direct GTD has less oscillation.
We conjecture that the advantages of Direct GTD in Baird’s counterexample result from the elimination of the secondary weight vector.
Notably,
we do not mean to claim that Direct GTD is winning GTD in all cases.
Instead,
this case study of Direct GTD and GTD in Baird’s counterexample only serves as initial evidence to initiate a more ambitious and thorough empirical comparison in more benchmark tasks,
which we leave for future work.

In Figure [3](#S7.F3), we additionally test other choices of the gap function to investigate empirically how slow the gap function can grow without incurring divergence.
The gap functions we test include

$$ $\displaystyle f(t)=$ $\displaystyle\lfloor\ln(t+1)\rfloor,$ (64) $\displaystyle f(t)=$ $\displaystyle\lfloor\ln(\ln(t+1)+1)\rfloor,$ (65) $\displaystyle f(t)=$ $\displaystyle\lfloor\ln(\ln(\ln(t+1)+1))\rfloor.$ (66) $$

Notably, none of the gap functions in ([64](#S7.E64)) satisfies Assumption [4.4](#S4.assu_counter4).
It turns out that even if the gap function grows as slow as $\ln(\ln(t+1)+1)$,
Direct GTD still converges in Baird’s counterexample.
This suggests that the requirement in Assumption [4.4](#S4.assu_counter4) is only sufficient but not necessarily necessary.
In practice,
the memory overhead incurred by the gap function can be much smaller than that prescribed by Assumption [4.4](#S4.assu_counter4).
For example, in Baird’s counterexample,
the memory overhead is only

$$ $\displaystyle\lfloor\ln(\ln(10^{4}+1)+1)\rfloor=2.$ (67) $$

Pushing Assumption [4.4](#S4.assu_counter4) to its limit and finding the slowest gap function is an interesting and rewarding future work.
We conjecture that if certain knowledge of the transition function of the MDP can be incorporated into the design of the gap function,
the gap function can be greatly slowed down.

## 8 Related Work

In this paper,
we propose a new method to implement the idea of GTD.
The family of GTD algorithms has been widely studied,
including Sutton et al. (, ); Maei et al. (); Maei and Sutton (); Maei et al. (); Maei (); Liu et al. (); Du et al. (); Wang et al. (); Yu (); Xu et al. (); Wang and Zou (); Wai et al. (); Zhang et al. ().
Those works cover both prediction and control problems,
both asymptotic and finite sample analysis,
both discounted and average rewards,
and both linear and nonlinear function approximation.
All existing works are indirect in the sense that they introduce an additional weight vector to solve the double sampling issue.
By contrast,
this work is the first in the GTD family that does not require an additional weight vector.
This work considers only the prediction problem with the discounted total rewards.
The idea in this work can be easily extended to control problems,
to average rewards,
to nonlinear function approximation,
and to eligibility traces,
all of which are, however, saved for future work.

GTD is originally invented to solve the deadly triad.
Besides GTD,
other possible solutions include
emphatic weighting (Yu, ; Zhang and Whiteson, ),
density ratio learning (Nachum et al., ; Zhang et al., ),
and target networks (Zhang et al., ).
Those different solutions have their own pros and cons.
There is not a constant winner, and the best-performing one is usually problem-dependent.
We refer readers to Zhang () for a more detailed discussion about all those different solutions to the deadly triad issue.
Here we only briefly discuss emphatic weighting in Emphatic Temporal Difference learning (ETD) to future elaborate on our technical novelty.
To address the possible divergence of ([15](#S2.E15)),
ETD, in its simplest form,
re-weights the incremental update in ([15](#S2.E15)) with a scalar $F_{t}$ called the followon trace.
Specifically,
ETD makes the following iterative update

$$ $\displaystyle F_{t}\doteq$ $\displaystyle 1+\gamma\rho_{t-1}F_{t-1},$ (68) $\displaystyle w_{t+1}\doteq$ $\displaystyle w_{t}+\alpha_{t}F_{t}\rho_{t}\left(R_{t+1}+\gamma x_{t+1}^{\top}w_{t}-x_{t}^{\top}w_{t}\right)x_{t}.$ (69) $$

This followon trace $F_{t}$ is recursively defined, and it can be easily seen that $F_{t}$ is a function of $S_{0},A_{0},\dots,S_{t-1},A_{t-1}$.
To analyze ETD,
one naive way is then to consider an augmented chain $\quantity{Y_{t}}$ defined as

$$ $\displaystyle Y_{t}\doteq(S_{0},A_{0},\dots,S_{t},A_{t}).$ (70) $$

This chain evolves in an increasing space

$$ $\displaystyle\cup_{i=1}^{\infty}(\mathcal{S}\times\mathcal{A})^{i}$ (71) $$

and is, in general, very hard to analyze.
One common practice for analyzing TD with traces is to include the trace itself into states, see, e.g., Tsitsiklis and Roy ().
In particular,
Yu () considers an augmented chain $\quantity{F_{t},S_{t},A_{t}}$ evolving in $\mathbb{R}\times\mathcal{S}\times\mathcal{A}$ for analyzing ETD and confirms its asymptotic convergence.
If we compare ETD ([68](#S8.E68)) with Direct GTD ([32](#S3.E32)),
it can be seen that we essentially replace the random scalar $F_{t}$ with a random matrix $\rho_{t+f(t)}\left(x_{t+f(t)}-\gamma x_{t+f(t)+1}\right)x^{\top}_{t+f(t)}$.
So in principle,
it might also be possible to analyze Direct GTD on an augmented chain in $\mathbb{R}^{K\times K}\times\mathcal{S}\times\mathcal{A}$.
This, however,
turns out to be very hard since analyzing the transition function of the augmented chain for Direct GTD is very challenging.
This work, instead, uses a refined discretization of ODE to account for the increasing state space,
which appears to be novel.
Another approach to working with the increasing state space in ETD is truncation (Zhang and Whiteson, ; Guan et al., ).
Instead of computing $F_{t}$ using all previous records,
Guan et al. () compute $F_{t}$ using only a finite history of length $f(t)$,
with $f(t)$ being an increasing function.
In other words,
instead of computing $F_{t}$ using $S_{0},A_{0},\dots,S_{t-1},A_{t-1}$,
Guan et al. () compute a truncated version of $F_{t}$ using only $S_{t-f(t)},A_{t-f(t)},\dots,S_{t-1},A_{t-1}$.
This is the closest work to our method.
We, however,
want to highlight three key differences.
First,
though sharing some technical similarity,
this work and Guan et al. () solve two different problems.
This work aims to eliminate the additional weight vector in GTD,
while Guan et al. () aims to reduce the variance of ETD.
Second,
all the analysis in Guan et al. () relies on the presence of the projection operator.
And Guan et al. () establish convergence only in expectation.
By contrast,
our asymptotic analysis does not assume the presence of a projection operator and establishes the stability with the supermartingale convergence theorem.
And our asymptotic convergence is almost sure convergence.
As remarked in Borkar (),
establishing stability is usually the most challenging part of analyzing a stochastic approximation algorithm.
Third, our Direct GTD is more data efficient.
Though both this work and Guan et al. () consider a sliding window of an increasing size $f(t)$,
how the sliding window moves are different.
In this work,
our sliding window always moves by 1 step.
In other words,
Direct GTD makes updates *every* step.
By contrast,
the sliding windows in Guan et al. () never overlap.
In other words,
Guan et al. () makes updates every $f(t)$ steps.
To summarize,
from the technical perspective,
both our finite sample analysis and Guan et al. () use a projection operator, so they have similar difficulty.
Our asymptotic analysis does not have a projection operator and is much more challenging.
It is possible that Guan et al. () could benefit from our refined discretization of ODEs to establish asymptotic convergence without projection,
which we, however, save for future work.

## 9 Conclusion

In this paper,
we propose a new method to solve the double sampling issue in implementing the idea of Gradient TD,
setting up a new agenda for defeating the notorious deadly triad.
The key advantage of our approach is that we do not introduce additional weights as existing GTD methods do.
Key to our convergence analysis is a novel refined discretization of the limiting ODE.
Though we do not abstract our analysis into a new convergence theorem for general stochastic approximation algorithms,
we do believe the insights therein can be easily transferred to analyzing other stochastic approximation algorithms with a similar structure.

Acknowledgments and Disclosure of Funding

SZ is part of the Link Lab at the University of Virginia.

## Appendix A Proofs

### A.1 Markovian Setting and Shorthands

We first recall our Markovian setting ([12](#S2.E12)) and define a few shorthands.
We work on an infinite trajectory

$$ $\displaystyle S_{0},A_{0},R_{1},S_{1},A_{1},R_{2},\dots$ (72) $$

where

$$ $\displaystyle S_{0}\sim p_{0},A_{t}\sim\mu(\cdot|S_{t}),R_{t+1}=r(S_{t},A_{t}),S_{t+1}\sim p(\cdot|S_{t},A_{t}).$ (73) $$

We use $\hat{A}_{t}$ to denote the stochastic estimate of the matrix $A$ ([17](#S2.E17)) at time $t$,
i.e.,

$$ $\displaystyle\hat{A}_{t}\doteq\rho_{t}x_{t}(\gamma x_{t+1}-x_{t})^{\top}.$ (74) $$

Similarly, we define

$$ $\displaystyle\hat{b}_{t}\doteq\rho_{t}R_{t+1}x_{t}.$ (75) $$

The finiteness of the MDP and Assumptions [4.1](#S4.assu_counter1) & [4.2](#S4.assu_counter2) ensure the existence of a constant $H<\infty$ such that

$$ $\displaystyle\sup_{t}\max\quantity{\norm{\hat{A}_{t}},\norm{\hat{b}_{t}},\norm{A},\norm{b},\norm{\hat{A}_{t}A^{-1}b}}\leq H.$ (76) $$

Let $\mathcal{F}_{t}$ denote the $\sigma$-algebra until time $t$,
i.e.,

$$ $\displaystyle\mathcal{F}_{t}\doteq\sigma\quantity(w_{0},S_{0},A_{0},\dots,S_{t-1},A_{t-1},S_{t}).$ (77) $$

The stochastic approximates then have the following property.

###### Lemma 3

Let Assumption [4.1](#S4.assu_counter1) hold.
Then there exists a constant $C_{M}>0$ and $\chi\in[0,1)$ such that

$$ $\displaystyle\norm{\mathbb{E}\left[\hat{A}_{t}\right]-A}\leq C_{M}\chi^{t},$ (78) $\displaystyle\norm{\mathbb{E}\left[\hat{A}_{t+k}^{\top}\hat{A}_{t}\right]-\mathbb{E}\left[\hat{A}_{t+k}\right]^{\top}\mathbb{E}\left[\hat{A}_{t}\right]}\leq C_{M}\chi^{k},$ (79) $\displaystyle\norm{\mathbb{E}\left[\hat{A}^{\top}_{t+k}\hat{A}_{t}|\mathcal{F}_{l}\right]-A^{\top}A}\leq C_{M}\begin{cases}1&t<l\\ \chi^{k}+\chi^{t-l}&t\geq l\end{cases}.$ (80) $$

Similarly,

$$ $\displaystyle\norm{\mathbb{E}\left[\hat{b}_{t}\right]-A}\leq C_{M}\chi^{t},$ (81) $\displaystyle\norm{\mathbb{E}\left[\hat{A}_{t+k}^{\top}\hat{b}_{t}\right]-\mathbb{E}\left[\hat{A}_{t+k}\right]^{\top}\mathbb{E}\left[\hat{b}_{t}\right]}\leq C_{M}\chi^{k},$ (82) $\displaystyle\norm{\mathbb{E}\left[\hat{A}^{\top}_{t+k}\hat{b}_{t}|\mathcal{F}_{l}\right]-A^{\top}b}\leq C_{M}\begin{cases}1&t<l\\ \chi^{k}+\chi^{t-l}&t\geq l\end{cases}.$ (83) $$

The proof is provided in Section [A.5.1](#A1.SS5.SSS1).

For discretizing the ODE,
we define a sequence $\quantity{T_{m}}_{m=0,1,\dots}$ as

$$ $\displaystyle T_{m}=\frac{16\max(C_{\alpha},1)}{(\eta+1)(m+1)^{\eta}},$ (85) $$

where $C_{\alpha}$ is defined in Assumption [4.3](#S4.assu_counter3) and $\eta$ is some constant such that

$$ $\displaystyle\frac{1}{2(1-\tau)}<\eta<\frac{\nu}{2-\nu},$ (86) $$

where $\nu$ and $\tau$ are defined in Assumption [4.3](#S4.assu_counter3) and [4.4](#S4.assu_counter4) respectively.
We now divide the real line into intervals with approximate length $\quantity{T_{m}}$.
To this end,
we define a sequence $\quantity{t_{m}}$ as

$$ $\displaystyle t_{0}\doteq$ $\displaystyle 0,$ (87) $\displaystyle t_{m+1}\doteq$ $\displaystyle\min\quantity{k|\sum_{t=t_{m}}^{k-1}\alpha_{t}\geq T_{m}},\,m=0,1,\dots$ (88) $$

For simplicity,
define

$$ $\displaystyle\bar{\alpha}_{m}\doteq\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t},\,m=0,1,\dots$ (89) $$

Now the real line has been divided into intervals of lengths $\quantity{\bar{\alpha}_{m}}_{m=0,1,\dots}$.
The following properties of this segmentation will be used repeatedly.
Notably, if the interval $\quantity{T_{m}}$ is constant,
as considered in Bertsekas and Tsitsiklis (),
Lemma [4](#Thmtheorem4) would be trivial.
It is the decreasing nature of our discretization that makes Lemma [4](#Thmtheorem4) challenging.

###### Lemma 4

For all $m\geq 0$ and $t\geq t_{m}$, we have $\alpha_{t}\leq T_{m}^{2}$.

The proof is provided in Section [A.5.2](#A1.SS5.SSS2).

###### Lemma 5

For all $m\geq 0$, we have $\bar{\alpha}_{m}\leq 2T_{m}$.

The proof is provided in Section [A.5.3](#A1.SS5.SSS3).

###### Lemma 3

###### Lemma 4

###### Lemma 5

### A.2 Proof of Theorem 1

Proof
We now investigate the iterates $\quantity{w_{t}}$ interval by interval.
Telescoping ([32](#S3.E32)) yields

$$ $\displaystyle w_{t_{m+1}}=w_{t_{m}}+\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}(-\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}w_{t}-\hat{A}_{t+f(t)}^{\top}\hat{b}_{t}).$ (90) $$

For ease of presentation,
we define for all $m>0$,

$$ $\displaystyle q_{m}=w_{t_{m}}+A^{-1}b.$ (91) $$

Then our goal is to show that $\quantity{q_{m}}$ converges to 0.
Plugging in ([91](#A1.E91)) into ([90](#A1.E90)) yields

$$ $\displaystyle q_{m+1}$ $\displaystyle=q_{m}+\sum_{t=t_{m}}^{k_{m+1}-1}\alpha_{t}(-\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}w_{t}-\hat{A}_{t+f(t)}^{\top}\hat{b}_{t})$ (92) $\displaystyle=q_{m}+\sum_{t=t_{m}}^{k_{m+1}-1}\alpha_{t}\left[-\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}\left(w_{t}+A^{-1}b\right)-\hat{A}_{t+f(t)}^{\top}\left(\hat{b}_{t}-\hat{A}_{t}A^{-1}b\right)\right]$ (93) $\displaystyle=q_{m}+g_{1,m}+g_{2,m}+g_{3,m}+g_{4,m},$ (94) $$

where

$$ $\displaystyle g_{1,m}=$ $\displaystyle\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}(-A^{\top}Aq_{m})=-\bar{\alpha}_{m}A^{\top}Aq_{m},$ (95) $\displaystyle g_{2,m}=$ $\displaystyle\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\left(A^{\top}A-\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}|\mathcal{F}_{t_{m}+f(t_{m})}\right]\right)q_{m}$ (96) $\displaystyle-\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\left(\hat{b}_{t}-\hat{A}_{t}A^{-1}b\right)|\mathcal{F}_{t_{m}+f(t_{m})}\right],$ (97) $\displaystyle g_{3,m}=$ $\displaystyle\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\left(\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}|\mathcal{F}_{t_{m}+f(t_{m})}\right]-\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}\right)q_{m}$ (98) $\displaystyle+\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\left(\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\left(\hat{b}_{t}-\hat{A}_{t}A^{-1}b\right)|\mathcal{F}_{t_{m}+f(t_{m})}\right]-\hat{A}_{t+f(t)}^{\top}\left(\hat{b}_{t}-\hat{A}_{t}A^{-1}b\right)\right),$ (99) $\displaystyle g_{4,m}=$ $\displaystyle\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}\left[q_{m}-\left(w_{t}+A^{-1}b\right)\right].$ (100) $$

We use the following lemmas to bound each term above.
One technical challenge is that due to the dependence on $\hat{A}_{t+f(t)}$,
$w_{t+1}$ is *not* adapted to $\mathcal{F}_{t}$ and is adapted to $\mathcal{F}_{t+f(t)}$.
This greatly complicates the analysis, and we will repeatedly use Lemma [3](#Thmtheorem3) to address this challenge.
Moreover, Assumption [4.2](#S4.assu_counter2) implies that the matrix $A^{\top}A$ is positive definite, i.e.,
there exists a constant $\beta>0$ such that for all $w$,

$$ $\displaystyle w^{\top}A^{\top}Aw\geq\beta\norm{w}^{2}.$ (101) $$

This $\beta$ plays a key role in the following bounds.

###### Lemma 6

If $e^{2T_{m}H^{2}}\leq 2$, then for all $t$ such that $t_{m}\leq t<t_{m+1}$, we have

$$ $\displaystyle\norm{q_{m}-\left(w_{t}+A^{-1}b\right)}\leq 8T_{m}H^{2}(\|q_{m}\|+1).$ (102) $$

The proof is provided in Section [A.5.4](#A1.SS5.SSS4).

###### Lemma 7

If $2H^{4}T_{m}\leq\beta$, then $\|q_{m}+g_{1,m}\|^{2}\leq(1-\beta T_{m})\|q_{m}\|^{2}$.

The proof is provided in Section [A.5.5](#A1.SS5.SSS5).

###### Lemma 8

If $T_{m}\leq 1$, then

$$ $\displaystyle\norm{g_{2,m}}\leq C_{M}T_{m}^{2(1-\tau)}(H+1)\left(C_{\tau}+L(f,\chi)+\frac{1}{1-\chi}\right)(\norm{q_{m}}+1),$ (103) $$

where $L(f,\chi)=\sum_{t=0}^{\infty}\chi^{f(t)}$, $C_{\tau}$ is defined in Assumption [4.4](#S4.assu_counter4),
and $C_{M}$ is defined in Lemma [3](#Thmtheorem3).
Notably, $L(f,\cdot)$ is finite due to Assumption [4.4](#S4.assu_counter4).

The proof is provided in Section [A.5.6](#A1.SS5.SSS6).

###### Lemma 9

$\|g_{3,m}\|\leq 8T_{m}H^{2}(\|q_{m}\|+1)$ and $\mathbb{E}\left[g_{3,m}|\mathcal{F}_{t_{m}+f(t_{m})}\right]=0$.

The proof is provided in Section [A.5.7](#A1.SS5.SSS7).

###### Lemma 10

If $e^{2T_{m}H^{2}}\leq 2$, then $\|g_{4,m}\|\leq 8T_{m}^{2}H^{4}(\|q_{m}\|+1)$.

The proof is provided in Section [A.5.8](#A1.SS5.SSS8).

Putting all the bounds together,
the following lemma shows that
the sequence $\quantity{\norm{q_{m}}}_{m\geq 0}$ is a supermartingale sequence.

###### Lemma 11

If $T_{m}\leq\min\left(\frac{\beta}{2H^{4}},1,\frac{\ln(2)}{2H^{2}}\right)$,
then there exists a scalar $D$ such that

$$ $\displaystyle\mathbb{E}\left[\norm{q_{m+1}}|\mathcal{F}_{t_{m}+f(t_{m})}\right]\leq\left(1-\beta T_{m}+DT_{m}^{2(1-\tau)}\right)\|q_{m}\|^{2}+DT_{m}^{2(1-\tau)},$ (104) $$

where $\tau$ is defined in Assumption [4.4](#S4.assu_counter4).
In particular, when $DT_{m}^{2(1-\tau)}\leq\frac{1}{2}\beta T_{m}$, we have

$$ $\displaystyle\mathbb{E}\left[\norm{q_{m+1}}|\mathcal{F}_{t_{m}+f(t_{m})}\right]\leq\left(1-\frac{1}{2}\beta T_{m}\right)\|q_{m}\|^{2}+DT_{m}^{2(1-\tau)}.$ (105) $$

The proof is provided in Section [A.5.9](#A1.SS5.SSS9).
The supermartingale convergence theorem can then take over to show the convergence of $\quantity{q_{m}}$.

###### Lemma 12

$\lim_{m\to\infty}\norm{q_{m}}=0$ a.s.

The proof is provided in Section [A.5.10](#A1.SS5.SSS10).

With all the established lemmas,
we can draw our final conclusion using Lemma [6](#Thmtheorem6).
Since both $T_{m}$ and $q_{m}$ converges to 0 almost surely,
the difference between $w_{t}+A^{-1}b$ and $q_{m}$ converges to 0 almost surely.
As a result, we can conclude that $\quantity{w_{t}+A^{-1}b}_{t=0,1,\dots}$ converges to 0, i.e.,
$\quantity{w_{t}}$ converges to $-A^{-1}b$ almost surely,
which completes the proof.

###### Lemma 6

###### Lemma 7

###### Lemma 8

###### Lemma 9

###### Lemma 10

###### Lemma 11

###### Lemma 12

### A.3 Proof of Theorem 2

Proof
We first define a few shorthands. We use $\bar{g}(w)$ and $g_{t}(w)$ to denote the true gradient and its stochastic estimate at time $t$, respectively, i.e.,

$$ $\displaystyle\bar{g}(w)=$ $\displaystyle-A^{\top}(Aw+b),$ (106) $\displaystyle g_{t}(w)=$ $\displaystyle-\hat{A}_{t+f(t)}^{\top}(\hat{A}_{t}w+\hat{b}_{t}).$ (107) $$

We further define

$$ $\displaystyle\Lambda_{t}(w)=\langle w-w_{*},g_{t}(w)-\bar{g}(w)\rangle,$ (108) $$

where we recall that $w^{*}$ is defined in ([16](#S2.E16)).
The following lemma states several useful properties of the functions defined above.

###### Lemma 13

There exist constants $C_{g}$ and $C_{Lip}$ such that for all $w$, $w^{\prime}$ with $\norm{w},\norm{w^{\prime}}\leq B$, we have

$$ $\displaystyle\max\quantity{g_{t}(w),\bar{g}(w),\Lambda_{t}(w)}\leq C_{g},$ (109) $\displaystyle\langle w-w^{\prime},\bar{g}(w)-\bar{g}(w^{\prime})\rangle\leq-\beta\norm{w-w^{\prime}}^{2},$ (110) $\displaystyle\max\quantity{\norm{g_{t}(w)-g_{t}(w^{\prime})},\norm{\bar{g}(w)-\bar{g}(w^{\prime})},|\Lambda_{t}(w)-\Lambda_{t}(w^{\prime})|}\leq C_{Lip}\norm{w-w^{\prime}}.$ (111) $$

We recall that $\beta$ is defined in ([101](#A1.E101)).

The proof is provided in section [A.5.11](#A1.SS5.SSS11).

###### Lemma 14

For all time $t$ and $0<k<t$, we have the following bound

$$ $\displaystyle\norm{\mathbb{E}\left[\Lambda_{t}(w_{t})\right]}\leq C_{g}C_{\alpha}C_{Lip}\ln\left(\frac{t}{t-k}\right)+2B(B+1)C_{M}\begin{cases}1&k<f(t-k)\\ \chi^{f(t)}+\chi^{t-(t-k+f(t-k))}&k\geq f(t-k)\end{cases}.$ (112) $$

The proof is provided in section [A.5.12](#A1.SS5.SSS12).

We are now ready to decompose the error as

$$ $\displaystyle\mathbb{E}\left[\norm{w_{t+1}-w_{*}}^{2}\right]$ (113) $\displaystyle\leq$ $\displaystyle\mathbb{E}\left[\norm{\Gamma(w_{t}+\alpha_{t}g_{t}(w_{t}))-w_{*}}^{2}\right]$ (114) $\displaystyle\leq$ $\displaystyle\mathbb{E}\left[\norm{\Gamma(w_{t}+\alpha_{t}g_{t}(w_{t}))-\Gamma(w_{*})}^{2}\right]$ (115) $\displaystyle\leq$ $\displaystyle\mathbb{E}\left[\norm{w_{t}+\alpha_{t}g_{t}(w_{t})-w_{*}}^{2}\right]$ (116) $\displaystyle=$ $\displaystyle\mathbb{E}\left[\norm{w_{t}-w_{*}}^{2}+\alpha_{t}^{2}\norm{g_{t}(w_{t})}^{2}+2\alpha_{t}\langle w_{t}-w_{*},g_{t}(w_{t})\rangle\right].$ (117) $$

Since $\bar{g}(w_{*})=0$,
we have

$$ $\displaystyle\langle w_{t}-w_{*},g_{t}(w_{t})\rangle$ (118) $\displaystyle=$ $\displaystyle\langle w_{t}-w_{*},g_{t}(w_{t})-\bar{g}(w_{t})+\bar{g}(w_{t})-\bar{g}(w_{*})\rangle$ (119) $\displaystyle=$ $\displaystyle\Lambda_{t}(w_{t})+\langle w_{t}-w_{*},\bar{g}(w_{t})-\bar{g}(w_{*})\rangle,$ (120) $$

yielding

$$ $\displaystyle\mathbb{E}\left[\norm{w_{t+1}-w_{*}}^{2}\right]$ (121) $\displaystyle\leq$ $\displaystyle\mathbb{E}\left[\norm{w_{t}-w_{*}}^{2}+\alpha_{t}^{2}\norm{g_{t}(w_{t})}^{2}+2\alpha_{t}\langle w_{t}-w_{*},g_{t}(w_{t})\rangle\right]$ (122) $\displaystyle\leq$ $\displaystyle\mathbb{E}\left[\norm{w_{t}-w_{*}}^{2}+\alpha_{t}^{2}\norm{g_{t}(w_{t})}^{2}+2\alpha_{t}\Lambda_{t}(w_{t})+2\alpha_{t}\langle w_{t}-w_{*},\bar{g}(w_{t})-\bar{g}(w_{*})\rangle\right].$ (123) $$

Applying Lemma [13](#Thmtheorem13), we get

$$ $\displaystyle\mathbb{E}\left[\norm{w_{t+1}-w_{*}}^{2}\right]$ (124) $\displaystyle\leq$ $\displaystyle\mathbb{E}\left[\norm{w_{t}-w_{*}}^{2}+\alpha_{t}^{2}C_{g}^{2}+2\alpha_{t}\Lambda_{t}(w_{t})-2\alpha_{t}\beta\norm{w_{t}-w_{*}}^{2}\right]$ (125) $\displaystyle=$ $\displaystyle(1-2\alpha_{t}\beta)\mathbb{E}[\norm{w_{t}-w_{*}}^{2}]+\alpha_{t}^{2}C_{g}^{2}+2\alpha_{t}\mathbb{E}[\Lambda_{t}(w_{t})].$ (126) $$

Plugging in $\alpha_{t}=\frac{C_{\alpha}}{t+1}$ and multiplying both sides by $(t+1)$, we have

$$ $\displaystyle(t+1)\mathbb{E}\left[\norm{w_{t+1}-w_{*}}^{2}\right]$ (127) $\displaystyle\leq$ $\displaystyle(t+1)\left(1-2\beta\frac{C_{\alpha}}{t+1}\right)\mathbb{E}[\norm{w_{t}-w_{*}}^{2}]+(t+1)\left(\frac{C_{\alpha}}{t+1}\right)^{2}C_{g}^{2}+(t+1)\cdot 2\frac{C_{\alpha}}{t+1}\mathbb{E}[\Lambda_{t}(w_{t})]$ (128) $\displaystyle\leq$ $\displaystyle\left(t+1-2\beta C_{\alpha}\right)\mathbb{E}[\norm{w_{t}-w_{*}}^{2}]+\frac{C_{\alpha}^{2}C_{g}^{2}}{t+1}+2C_{\alpha}\mathbb{E}[\Lambda_{t}(w_{t})].$ (129) $$

Let $C_{0}=\frac{1}{2\beta}$. Then as $C_{\alpha}\geq C_{0}$, $2\beta C_{\alpha}\geq 2\beta C_{0}=1$. Hence, $t+1-2\beta C_{\alpha}\leq t$. Since $\mathbb{E}\left[\norm{w_{t+1}-w_{*}}^{2}\right]\geq 0$, we have

$$ $\displaystyle(t+1)\mathbb{E}\left[\norm{w_{t+1}-w_{*}}^{2}\right]\leq t\mathbb{E}\left[\norm{w_{t+1}-w_{*}}^{2}\right]+\frac{C_{\alpha}^{2}C_{g}^{2}}{t+1}+2C_{\alpha}\mathbb{E}[\Lambda_{t}(w_{t})]$ (130) $$

Applying the inequality recursively,

$$ $\displaystyle T\mathbb{E}\left[\norm{w_{T}-w_{*}}^{2}\right]$ (131) $\displaystyle\leq$ $\displaystyle\sum_{t=0}^{T-1}\left(\frac{C_{\alpha}^{2}C_{g}^{2}}{t+1}+2C_{\alpha}\mathbb{E}[\Lambda_{t}(w_{t})]\right)$ (132) $\displaystyle=$ $\displaystyle C_{\alpha}^{2}C_{g}^{2}\sum_{t=1}^{T}\frac{1}{t}+2C_{\alpha}\sum_{t=0}^{k}\mathbb{E}[\Lambda_{t}(w_{t})]+2C_{\alpha}\sum_{t=k+1}^{T-1}\mathbb{E}[\Lambda_{t}(w_{t})]$ (133) $\displaystyle\leq$ $\displaystyle C_{\alpha}^{2}C_{g}^{2}[\ln(T)+1]+2C_{\alpha}\sum_{t=0}^{k}\mathbb{E}[\Lambda_{t}(w_{t})]+2C_{\alpha}\sum_{t=k+1}^{T-1}\mathbb{E}[\Lambda_{t}(w_{t})],$ (134) $$

where the last inequality comes from the bound for harmonic numbers.
Applying Lemma [13](#Thmtheorem13) again yields

$$ $\displaystyle T\mathbb{E}\left[\norm{w_{T}-w_{*}}^{2}\right]$ (135) $\displaystyle\leq$ $\displaystyle C_{\alpha}^{2}C_{g}^{2}[\ln(T)+1]+2C_{\alpha}\sum_{t=0}^{k}C_{g}+2C_{\alpha}\sum_{t=k+1}^{T-1}\mathbb{E}[\Lambda_{t}(w_{t})]$ (136) $\displaystyle=$ $\displaystyle C_{\alpha}^{2}C_{g}^{2}[\ln(T)+1]+2kC_{\alpha}C_{g}+2C_{\alpha}\sum_{t=k+1}^{T-1}\mathbb{E}[\Lambda_{t}(w_{t})].$ (137) $$

Now, we will use Lemma [14](#Thmtheorem14) to bound the last summation.
Firstly, we take

$$ $\displaystyle k\doteq 2f(T).$ (138) $$

Secondly, Assumption [4.4](#S4.assu_counter4) suggests that for some $\tau\in(0,\frac{3\nu-2}{\nu})$,

$$ $\displaystyle f(t)\leq C_{\tau}\alpha_{t}^{-\tau}=C_{\tau}\left(\frac{C_{\alpha}}{(t+1)^{\nu}}\right)^{-\tau}=\frac{C_{\tau}(t+1)^{\tau\nu}}{C_{\alpha}^{\tau}}.$ (139) $$

Since $\nu\leq 1$, $\tau\nu<\frac{3\nu-2}{\nu}=3\nu-2\leq 1$. Hence, there exists a constant $T_{0}$ such that for all $T\geq T_{0}$, we have

$$ $\displaystyle 2f(T)\leq\frac{2C_{\tau}(T+1)^{\tau\nu}}{C_{\alpha}^{\tau}}<T.$ (140) $$

For the rest of the argument, we will assume that $T\geq T_{0}$ and we will then have $2f(T)<T$.

As $f$ is increasing,
for all $t\in(k,T)$,
we have

$$ $\displaystyle k=2f(T)\geq 2f(t)\geq f(t-k).$ (141) $$

So for $t>k$,

$$ $\displaystyle\mathbb{E}[\Lambda_{t}(w_{t})]$ $\displaystyle\leq C_{g}C_{\alpha}C_{Lip}\ln\left(\frac{t}{t-k}\right)+2B(B+1)C_{M}\left(\chi^{f(t)}+\chi^{k-f(t-k)}\right)$ (Lemma 14 ) $\displaystyle\leq C_{g}C_{\alpha}C_{Lip}\ln\left(\frac{t}{t-k}\right)+4B(B+1)C_{M}\chi^{f(t)},$ (142) $$

where the last inequality uses the fact that for all $t\in(k,T)$,

$$ $\displaystyle k-f(t-k)=2f(T)-f(t-k)>2f(t)-f(t)=f(t).$ (143) $$

Summing them up then yields

$$ $\displaystyle\sum_{t=k+1}^{T-1}\mathbb{E}[\Lambda_{t}(t)]$ (144) $\displaystyle\leq$ $\displaystyle\sum_{t=k+1}^{T-1}\left(C_{g}C_{\alpha}C_{Lip}\ln\left(\frac{t}{t-k}\right)+4B(B+1)C_{M}\chi^{f(t)}\right)$ (145) $\displaystyle\leq$ $\displaystyle C_{g}C_{\alpha}C_{Lip}\sum_{t=k+1}^{T-1}(\ln(t)-\ln(t-k))+4B(B+1)C_{M}\sum_{t=k+1}^{T}\chi^{f(t)}$ (146) $\displaystyle\leq$ $\displaystyle C_{g}C_{\alpha}C_{Lip}\left(\sum_{t=k+1}^{T-1}\ln(t)-\sum_{t=k+1}^{T-1}\ln(t-k)\right)+4B(B+1)C_{M}\sum_{t=0}^{\infty}\chi^{f(t)}$ (147) $\displaystyle\leq$ $\displaystyle C_{g}C_{\alpha}C_{Lip}\left(\sum_{t=k+1}^{T-1}\ln(t)-\sum_{t=1}^{T-k-1}\ln(t)\right)+4B(B+1)L(f,\chi)$ (148) $\displaystyle\leq$ $\displaystyle C_{g}C_{\alpha}C_{Lip}\left(\sum_{t=T-k}^{T-1}\ln(t)-\sum_{t=1}^{k}\ln(t)\right)+4B(B+1)L(f,\chi)$ (149) $\displaystyle\leq$ $\displaystyle C_{g}C_{\alpha}C_{Lip}\left(\sum_{t=T-k}^{T-1}\ln(t)-\ln[t-(T-k-1)]\right)+4B(B+1)L(f,\chi)$ (150) $\displaystyle\leq$ $\displaystyle C_{g}C_{\alpha}C_{Lip}\sum_{t=T-k}^{T-1}\log\left[\frac{t}{t-(T-k-1)}\right]+4B(B+1)L(f,\chi)$ (151) $\displaystyle\leq$ $\displaystyle C_{g}C_{\alpha}C_{Lip}\sum_{t=T-k}^{T-1}\log(T)+4B(B+1)L(f,\chi)$ (152) $\displaystyle\leq$ $\displaystyle C_{g}C_{\alpha}C_{Lip}k\log(T)+4B(B+1)L(f,\chi),$ (153) $$

where second last inequality holds because

$$ $\displaystyle\log\left[\frac{t}{t-(T-k-1)}\right]\leq\log(T)$ (154) $$

holds for all $T-k-1<t<T$
and $L(f,\chi)=\sum_{t=0}^{\infty}\chi^{f(t)}<\infty$ due to Assumption [4.4](#S4.assu_counter4).

Plugging ([153](#A1.E153)) into ([137](#A1.E137)) then yields

$$ $\displaystyle T\mathbb{E}[\norm{w_{T}-w_{*}}^{2}]$ (155) $\displaystyle\leq$ $\displaystyle C_{\alpha}^{2}C_{g}^{2}[\ln(T)+1]+2kC_{\alpha}C_{g}+2C_{\alpha}[C_{g}C_{\alpha}C_{Lip}k\log(T)+4B(B+1)L(f,\chi)]$ (156) $\displaystyle=$ $\displaystyle C_{\alpha}^{2}C_{g}^{2}[\ln(T)+1]+2kC_{\alpha}C_{g}+2C_{g}C_{\alpha}^{2}C_{Lip}k\log(T)+8C_{\alpha}B(B+1)L(f,\chi),$ (157) $$

Since we have defined $k\doteq 2f(T)$,
we have that for $T\geq T_{0}$,

$$ $\displaystyle\mathbb{E}[\norm{w_{T}-w_{*}}^{2}]$ (158) $\displaystyle\leq$ $\displaystyle\frac{C_{\alpha}^{2}C_{g}^{2}[\ln(T)+1]}{T}+\frac{4f(T)C_{\alpha}C_{g}}{T}+\frac{4C_{g}C_{\alpha}^{2}C_{Lip}f(T)\log(T)}{T}+\frac{8C_{\alpha}B(B+1)L(f,\chi)}{T}.$ (159) $$

Thus, for all $T$, we have

$$ $\displaystyle\mathbb{E}[\norm{w_{T}-w_{*}}^{2}]=\mathcal{O}\left(\frac{f(T)\ln(T)}{T}\right),$ (160) $$

which completes the proof.

###### Lemma 13

###### Lemma 14

### A.4 Auxiliary Lemmas

###### Lemma 15

If the gap function $f(t)=\lfloor h(t)\ln(t)\rfloor$ where $h$ is a non-negative, increasing function tending to infinity,
then $\sum_{t=0}^{\infty}\chi^{f(t)}$ for all $\chi\in(0,1)$.

Proof
Firstly, we should note that for all $t$, $\lfloor h(t)\ln(t)\rfloor>h(t)\ln(t)-1$.
Therefore, take arbitrary $\chi\in(0,1)$,

$$ $\displaystyle\sum_{t=0}^{\infty}\chi^{f(t)}\leq\sum_{t=0}^{\infty}\chi^{h(t)\ln(t)-1}=\frac{1}{\chi}\sum_{t=0}^{\infty}e^{\ln(\chi)h(t)\ln(t)}=\frac{1}{\chi}\sum_{t=0}^{\infty}t^{\ln(\chi)h(t)}.$ (161) $$

Since $h$ is increasing in $t$ and tending to infinity, there exists a $T$ such that got all $t\geq T$, $f(t)\geq-\frac{2}{\ln(\chi)}$. Then, for all $t\geq T$, $t^{\ln(\chi)h(t)}\leq t^{-2}$. Thus, by comparison test and p-test, we can conclude that $\sum_{t=0}^{\infty}\chi^{f(t)}\leq\sum_{t=0}^{\infty}t^{-2}<\infty$.

###### Lemma 15

### A.5 Proof of Technical Lemmas

#### A.5.1 Proof of Lemma 3

Proof
For the simplicity of display,
we include the proof only for the first half of the lemma.
The second half is identical up to change of notations and is, therefore, omitted to avoid verbatim.

Define an augmented chain $\quantity{Y_{t}}$ evolving in

$$ $\displaystyle\mathcal{Y}\doteq\quantity{(s,a,s^{\prime})\in\mathcal{S}\times\mathcal{A}\times\mathcal{S}\mid d_{\mu}(s)>0,\mu(a|s)>0,p(s^{\prime}|s,a)>0}$ (162) $$

as

$$ $\displaystyle Y_{t}\doteq(S_{t},A_{t},S_{t+1}).$ (163) $$

According to the definition of $\mathcal{F}_{t}$,
it can be easily seen that $Y_{t}$ is adapted to $\mathcal{F}_{t+1}$.
Assumption [4.1](#S4.assu_counter1) immediately ensures that $\quantity{Y_{t}}$ is also ergodic with a stationary distribution

$$ $\displaystyle d_{Y}(y)=d_{\mu}(s)\mu(a|s)p(s^{\prime}|s,a).$ (164) $$

Here we have used $y$ as shorthand for $(s,a,s^{\prime})$.
Define functions

$$ $\displaystyle\hat{A}(y)\doteq$ $\displaystyle\rho(s,a)x(s)\left(\gamma x(s^{\prime})-x(s)\right)^{\top},$ (165) $\displaystyle\hat{b}(y)\doteq$ $\displaystyle\rho(s,a)x(s)r(s,a).$ (166) $$

It can then be easily computed that

$$ $\displaystyle\hat{A}_{t}=$ $\displaystyle\hat{A}(Y_{t}),$ (167) $\displaystyle A=$ $\displaystyle\sum_{y}d_{Y}(y)\hat{A}(y).$ (168) $$

Assumption [4.1](#S4.assu_counter1) ensures that the chain $\quantity{Y_{t}}$ mixes geometrically fast.
In other words,
there exist constants $\chi\in[0,1)$ and $C_{0}>0$ such that for any $t$ and $k$,

$$ $\displaystyle\max_{y}\sum_{y^{\prime}}\absolutevalue{\Pr(Y_{t+k}=y^{\prime}|Y_{t}=y)-d_{Y}(y^{\prime})}\leq C_{0}\chi^{k}.$ (169) $$

This is a well-known result, and we refer the reader to Theorem 4.7 of Levin and Peres () for detailed proof.
Then we have

$$ $\displaystyle\norm{\mathbb{E}\left[\hat{A}_{t}\right]-A}$ (170) $\displaystyle=$ $\displaystyle\norm{\sum_{y}\Pr(Y_{t}=y)\hat{A}(y)-\sum_{y}d_{Y}(y)\hat{A}(y)}$ (171) $\displaystyle\leq$ $\displaystyle\sum_{y}\norm{\Pr(Y_{t}=y)-d_{Y}(y)}\norm{\hat{A}(y)}$ (172) $\displaystyle\leq$ $\displaystyle\max_{y}\norm{\hat{A}(y)}\sum_{y}\norm{\Pr(Y_{t}=y)-d_{Y}(y)}$ (173) $\displaystyle\leq$ $\displaystyle HC_{0}\chi^{t},$ (174) $$

which completes the proof of ([78](#A1.E78)).
Similarly, we have

$$ $\displaystyle\norm{\mathbb{E}\left[\hat{A}_{t+k}^{\top}\hat{A}_{t}\right]-\mathbb{E}\left[\hat{A}_{t+k}\right]\mathbb{E}\left[\hat{A}_{t}\right]}$ (175) $\displaystyle=$ $\displaystyle\norm{\sum_{y^{\prime}}\sum_{y}\Pr(Y_{t+k}=y^{\prime},Y_{t}=y)\hat{A}(y^{\prime})^{\top}\hat{A}(y)-\left(\sum_{y^{\prime}}\Pr(Y_{t+k}=y^{\prime})\hat{A}(y^{\prime})\right)^{\top}\left(\sum_{y}\Pr(Y_{t}=y)\hat{A}(y)\right)}$ (176) $\displaystyle=$ $\displaystyle\norm{\sum_{y^{\prime}}\sum_{y}\left(\Pr(Y_{t+k}=y^{\prime},Y_{t}=y)-\Pr(Y_{t+k}=y^{\prime})\Pr(Y_{t}=y)\right)A(y^{\prime})^{\top}\hat{A}(y)}$ (177) $\displaystyle\leq$ $\displaystyle\max_{y^{\prime}}\norm{\hat{A}(y^{\prime})^{\top}}\max_{y}\norm{\hat{A}(y)}\norm{\sum_{y^{\prime}}\sum_{y}\left(\Pr(Y_{t+k}=y^{\prime},Y_{t}=y)-\Pr(Y_{t+k}=y^{\prime})\Pr(Y_{t}=y)\right)}$ (178) $\displaystyle\leq$ $\displaystyle H\cdot H\sum_{y^{\prime}}\sum_{y}\absolutevalue{\Pr(Y_{t+k}=y^{\prime},Y_{t}=y)-\Pr(Y_{t+k}=y^{\prime})\Pr(Y_{t}=y)}$ (179) $\displaystyle\leq$ $\displaystyle H^{2}\sum_{y^{\prime}}\sum_{y}\absolutevalue{\Pr(Y_{t+k}=y^{\prime}|Y_{t}=y)\Pr(Y_{t}=y)-\Pr(Y_{t+k}=y^{\prime})\Pr(Y_{t}=y)}$ (180) $\displaystyle\leq$ $\displaystyle H^{2}\sum_{y^{\prime}}\sum_{y}\absolutevalue{\Pr(Y_{t+k}=y^{\prime}|Y_{t}=y)-\Pr(Y_{t+k}=y^{\prime})}\Pr(Y_{t}=y)$ (181) $\displaystyle\leq$ $\displaystyle H^{2}\sum_{y^{\prime}}\sum_{y}\absolutevalue{\Pr(Y_{t+k}=y^{\prime}|Y_{t}=y)-\Pr(Y_{t+k}=y^{\prime})}$ (182) $\displaystyle\leq$ $\displaystyle H^{2}\sum_{y^{\prime}}\sum_{y}\absolutevalue{\Pr(Y_{t+k}=y^{\prime}|Y_{t}=y)-d_{Y}(y^{\prime})|+|d_{Y}(y^{\prime})-\Pr(Y_{t+k}=y^{\prime})}$ (183) $\displaystyle\leq$ $\displaystyle H^{2}\sum_{y}\left(\sum_{y^{\prime}}|\Pr(Y_{t+k}=y^{\prime}|Y_{t}=y)-d_{Y}(y^{\prime})|+\sum_{y^{\prime}}|\Pr(Y_{t+k}=y^{\prime})-d_{Y}(y^{\prime})|\right)$ (184) $\displaystyle\leq$ $\displaystyle H^{2}\sum_{y}\left(C_{0}\chi^{k}+C_{0}\chi^{t+k}\right)$ (185) $\displaystyle\leq$ $\displaystyle 2H^{2}|\mathcal{Y}|C_{0}\chi^{k},$ (186) $$

which proves ([79](#A1.E79)).
This also suggests $\forall l$,

$$ $\displaystyle\norm{\mathbb{E}\left[\hat{A}_{t+k}^{\top}\hat{A}_{t}\mid\mathcal{F}_{l}\right]-\mathbb{E}\left[\hat{A}_{t+k}\mid\mathcal{F}_{l}\right]^{\top}\mathbb{E}\left[\hat{A}_{t}\mid\mathcal{F}_{l}\right]}\leq 2H^{2}\absolutevalue{\mathcal{Y}}C_{0}\chi^{k}.$ (187) $$

To see this, we consider the two cases of whether $l<t$ separately.

Case 1: $l<t$. Then, by the Markov property,

$$ $\displaystyle\norm{\mathbb{E}\left[\hat{A}_{t+k}^{\top}\hat{A}_{t}\mid\mathcal{F}_{l}\right]-\mathbb{E}\left[\hat{A}_{t+k}\mid\mathcal{F}_{l}\right]^{\top}\mathbb{E}\left[\hat{A}_{t}\mid\mathcal{F}_{l}\right]}$ (188) $\displaystyle=$ $\displaystyle\norm{\mathbb{E}\left[\hat{A}_{t+k}^{\top}\hat{A}_{t}\mid Y_{l}\right]-\mathbb{E}\left[\hat{A}_{t+k}\mid Y_{l}\right]^{\top}\mathbb{E}\left[\hat{A}_{t}\mid Y_{l}\right]}$ (189) $\displaystyle\leq$ $\displaystyle 2H^{2}|\mathcal{Y}|C_{0}\chi^{k}.$ (190) $$

Case 2: $l\geq t$. Then $\hat{A}_{t}$ is deterministic given $\mathcal{F}_{l}$. and

$$ $\displaystyle\norm{\mathbb{E}\left[\hat{A}_{t+k}^{\top}\hat{A}_{t}\mid\mathcal{F}_{l}\right]-\mathbb{E}\left[\hat{A}_{t+k}\mid\mathcal{F}_{l}\right]^{\top}\mathbb{E}\left[\hat{A}_{t}\mid\mathcal{F}_{l}\right]}$ (191) $\displaystyle=$ $\displaystyle\norm{\mathbb{E}\left[\hat{A}_{t+k}^{\top}\mathbb{E}\left[\hat{A}_{t}\mid\mathcal{F}_{l}\right]\mid\mathcal{F}_{l}\right]-\mathbb{E}\left[\hat{A}_{t+k}\mid\mathcal{F}_{l}\right]^{\top}\mathbb{E}\left[\hat{A}_{t}\mid\mathcal{F}_{l}\right]}$ (192) $\displaystyle=$ $\displaystyle\norm{\mathbb{E}\left[\hat{A}_{t+k}\mid\mathcal{F}_{l}\right]^{\top}\mathbb{E}\left[\hat{A}_{t}\mid\mathcal{F}_{l}\right]-\mathbb{E}\left[\hat{A}_{t+k}\mid\mathcal{F}_{l}\right]^{\top}\mathbb{E}\left[\hat{A}_{t}\mid\mathcal{F}_{l}\right]}$ (193) $\displaystyle=$ $\displaystyle 0.$ (194) $$

Lastly, combining the geometrical convergence suggested in ([78](#A1.E78)) and the geometrically decaying correlation implied by ([79](#A1.E79)), we can prove ([80](#A1.E80)) in the following manner.
First,

$$ $\displaystyle\norm{\mathbb{E}\left[\hat{A}^{\top}_{t+k}\hat{A}_{t}|\mathcal{F}_{l}\right]-A^{\top}A}$ (195) $\displaystyle\leq$ $\displaystyle\norm{\mathbb{E}\left[\hat{A}^{\top}_{t+k}\hat{A}_{t}|\mathcal{F}_{l}\right]-\mathbb{E}\left[\hat{A}_{t+k}|\mathcal{F}_{l}\right]^{\top}\mathbb{E}\left[\hat{A}_{t}|\mathcal{F}_{l}\right]+\mathbb{E}\left[\hat{A}_{t+k}|\mathcal{F}_{l}\right]^{\top}\mathbb{E}\left[\hat{A}_{t}|\mathcal{F}_{l}\right]-A^{\top}A}$ (196) $\displaystyle\leq$ $\displaystyle\norm{\mathbb{E}\left[\hat{A}^{\top}_{t+k}\hat{A}_{t}|\mathcal{F}_{l}\right]-\mathbb{E}\left[\hat{A}_{t+k}|\mathcal{F}_{l}\right]^{\top}\mathbb{E}\left[\hat{A}_{t}|\mathcal{F}_{l}\right]}+\norm{\mathbb{E}\left[\hat{A}_{t+k}|\mathcal{F}_{l}\right]^{\top}\mathbb{E}\left[\hat{A}_{t}|\mathcal{F}_{l}\right]-A^{\top}A}$ (197) $\displaystyle\leq$ $\displaystyle 2H^{2}|\mathcal{Y}|C_{0}\chi^{k}+\norm{\mathbb{E}\left[\hat{A}_{t+k}|\mathcal{F}_{l}\right]^{\top}\mathbb{E}\left[\hat{A}_{t}|\mathcal{F}_{l}\right]-\mathbb{E}\left[\hat{A}_{t+k}|\mathcal{F}_{l}\right]^{\top}A+\mathbb{E}\left[\hat{A}_{t+k}|\mathcal{F}_{l}\right]^{\top}A-A^{\top}A}$ (198) $\displaystyle\leq$ $\displaystyle 2H^{2}|\mathcal{Y}|C_{0}\chi^{k}+\norm{\mathbb{E}\left[\hat{A}_{t+k}|\mathcal{F}_{l}\right]^{\top}(\mathbb{E}\left[\hat{A}_{t}|\mathcal{F}_{l}\right]-A)}+\norm{(\mathbb{E}\left[\hat{A}_{t+k}|\mathcal{F}_{l}\right]-A)^{\top}A}$ (199) $\displaystyle\leq$ $\displaystyle 2H^{2}|\mathcal{Y}|C_{0}\chi^{k}+\norm{\mathbb{E}\left[\hat{A}_{t+k}|\mathcal{F}_{l}\right]^{\top}}\norm{\mathbb{E}\left[\hat{A}_{t}|\mathcal{F}_{l}\right]-A}+\norm{(\mathbb{E}\left[\hat{A}_{t+k}|\mathcal{F}_{l}\right]-A)^{\top}}\norm{A}$ (200) $\displaystyle\leq$ $\displaystyle 2H^{2}|\mathcal{Y}|C_{0}\chi^{k}+H\norm{\mathbb{E}\left[\hat{A}_{t}|\mathcal{F}_{l}\right]-A}+H\norm{\mathbb{E}\left[\hat{A}_{t+k}|\mathcal{F}_{l}\right]-A}$ (201) $\displaystyle\leq$ $\displaystyle 2H^{2}|\mathcal{Y}|C_{0}\chi^{k}+H\left(\norm{\mathbb{E}\left[\hat{A}_{t}|\mathcal{F}_{l}\right]-A}+\norm{\mathbb{E}\left[\hat{A}_{t+k}|\mathcal{F}_{l}\right]-A}\right).$ (202) $$

We now bound the last term.
For $t<l$, we use the trivial bound

$$ $\displaystyle\norm{\mathbb{E}\left[\hat{A}_{t}|\mathcal{F}_{l}\right]-A}+\norm{\mathbb{E}\left[\hat{A}_{t+k}|\mathcal{F}_{l}\right]-A}$ $\displaystyle\leq 4H.$ (203) $$

For $t\geq l$, both $Y_{t}$ and $Y_{t+k}$ are not adapted to $\mathcal{F}_{l}$.
We, therefore, have

$$ $\displaystyle\norm{\mathbb{E}\left[\hat{A}_{t}|\mathcal{F}_{l}\right]-A}+\norm{\mathbb{E}\left[\hat{A}_{t+k}|\mathcal{F}_{l}\right]-A}$ $\displaystyle\leq HC_{0}\chi^{t-l}+HC_{0}\chi^{t+k-l}\leq 2HC_{0}\chi^{t-l}.$ (204) $$

Combining the results, we obtain

$$ $\displaystyle\norm{\mathbb{E}\left[\hat{A}^{\top}_{t+k}\hat{A}_{t}|\mathcal{F}_{l}\right]-A^{\top}A}$ $\displaystyle\leq 2H^{2}|\mathcal{Y}|C_{0}\chi^{k}+\begin{cases}4H^{2}&t<l\\ 2H^{2}C_{0}\chi^{t-l}&t\geq l\end{cases}$ (205) $\displaystyle=\begin{cases}2H^{2}|\mathcal{Y}|C_{0}+4H^{2}&t<l\\ 2H^{2}|\mathcal{Y}|C_{0}\chi^{k}+2H^{2}C_{0}\chi^{t-l}&t\geq l\end{cases},$ (Since $\chi\leq 1$ ) $$

which completes the proof of ([80](#A1.E80)).

#### A.5.2 Proof of Lemma 4

Proof
We proceed via induction on $m$.
In particular,
we prove the following two inequalities for all $m$:

$$ $\displaystyle t_{m}\geq$ $\displaystyle\frac{m^{\eta+1}}{16\max(C_{\alpha},1)},$ (206) $\displaystyle\alpha_{t}\leq$ $\displaystyle T_{m}^{2},\forall t\geq t_{m}.$ (207) $$

Base Case m=0: Obviously we have

$$ $\displaystyle t_{0}=0=\frac{0^{\eta+1}}{16\max(C_{\alpha},1)},$ (208) $$

so ([206](#A1.E206)) holds for $m=0$.
Since $\eta\in(0,1]$,
we have

$$ $\displaystyle T_{0}=\frac{16\max(C_{\alpha},1)}{\eta+1}\geq 8\max(C_{\alpha},1).$ (209) $$

Hence, for all $t\geq t_{0}=0$,

$$ $\displaystyle\alpha_{t}=\frac{C_{\alpha}}{(t+1)^{\nu}}\leq C_{\alpha}\leq 8\max(C_{\alpha},1)^{2}\leq T_{0}^{2}.$ (210) $$

So ([207](#A1.E207)) holds.

Induction Step: Suppose ([206](#A1.E206)) and ([207](#A1.E207)) hold for $m=k$.
We now verify them for $m=k+1$.
Letting $m=k$ in ([207](#A1.E207)) yields

$$ $\displaystyle T_{k}\leq$ $\displaystyle\sum_{t=t_{k}}^{t_{k+1}-1}\alpha_{t}$ (Defintion of $\quantity{t_{m}}$ in ( 88 )) $\displaystyle\leq$ $\displaystyle\sum_{t=t_{k}}^{t_{k+1}-1}T_{k}^{2}=(t_{k+1}-t_{k})T_{k}^{2}.$ (211) $$

Dividing both sides by $T_{k}$ yields

$$ $\displaystyle t_{k+1}-t_{k}\geq\frac{1}{T_{k}}=\frac{(\eta+1)(k+1)^{\eta}}{16\max(C_{\alpha},1)}.$ (212) $$

Consequently, we have

$$ $\displaystyle t_{k+1}\geq$ $\displaystyle t_{k}+\frac{(\eta+1)(k+1)^{\eta}}{16\max(C_{\alpha},1)}$ (213) $\displaystyle\geq$ $\displaystyle\frac{k^{\eta+1}}{16\max(C_{\alpha},1)}+\frac{(\eta+1)(k+1)^{\eta}}{16\max(C_{\alpha},1)},$ (214) $$

where the last inequality results from inductive hypothesis ([206](#A1.E206)).
Since $\frac{(\eta+1)(k+1)^{\eta}}{16\max\quantity{C_{\alpha},1}}$ is monotonically increasing in $k$,
we have

$$ $\displaystyle\frac{(\eta+1)(k+1)^{\eta}}{16\max(C_{\alpha},1)}\geq\int_{k}^{k+1}\frac{(\eta+1)(k+1)^{\eta}}{16\max(C_{\alpha},1)}=\frac{(k+1)^{\eta+1}}{16\max(C_{\alpha},1)}-\frac{k^{\eta+1}}{16\max(C_{\alpha},1)}.$ (215) $$

We have thus verified ([206](#A1.E206)) for $m=k+1$, i.e.

$$ $\displaystyle t_{k+1}\geq\frac{k^{\eta+1}}{16\max(C_{\alpha},1)}+\frac{(k+1)^{\eta+1}}{16\max(C_{\alpha},1)}-\frac{k^{\eta+1}}{16\max(C_{\alpha},1)}=\frac{(k+1)^{\eta+1}}{16\max(C_{\alpha},1)}.$ (216) $$

To verify ([207](#A1.E207)) for $m=k+1$,
we will make use of our just proven ([206](#A1.E206)) with $m=k+1$.
Take arbitrary $t\geq t_{k+1}$.
As $\alpha_{t}=\frac{C_{\alpha}}{(t+1)^{\nu}}$ is a monotonically decreasing in $t$, we have

$$ $\displaystyle\alpha_{t}\leq\alpha_{t_{k+1}}=\frac{C_{\alpha}}{(t_{k+1}+1)^{\nu}}\leq\frac{C_{\alpha}}{t_{k+1}^{\nu}}.$ (217) $$

Using ([206](#A1.E206)) with $m=k+1$, we get

$$ $\displaystyle\alpha_{t}\leq\frac{C_{\alpha}}{t_{k+1}^{\nu}}\leq\frac{C_{\alpha}}{\left(\frac{1}{16\max(C_{\alpha},1)}(k+1)^{\eta+1}\right)^{\nu}}\leq\frac{16^{\nu}C_{\alpha}\max(C_{\alpha},1)^{\nu}}{(k+2)^{(\eta+1)\nu}}\left(\frac{k+2}{k+1}\right)^{(\eta+1)\nu}.$ (218) $$

As $\frac{k+2}{k+1}\leq 2$ for $k\geq 0$ and $\eta,\nu\in(0,1]$, we have

$$ $\displaystyle\left(\frac{k+2}{k+1}\right)^{(\eta+1)\nu}\leq 2^{(\eta+1)\nu}.$ (219) $$

Moreover, since $C_{\alpha}\leq\max(C_{\alpha},1)$,
we have

$$ $\displaystyle C_{\alpha}\max(C_{\alpha},1)^{\nu}\leq\max(C_{\alpha},1)^{1+\nu}.$ (220) $$

Thus we have

$$ $\displaystyle\alpha_{t}\leq\frac{16^{\nu}C_{\alpha}\max(C_{\alpha},1)^{\nu}}{(k+2)^{(\eta+1)\nu}}\left(\frac{k+2}{k+1}\right)^{(\eta+1)\nu}\leq\frac{2^{(\eta+5)\nu}\max(C_{\alpha},1)^{1+\nu}}{(k+2)^{(\eta+1)\nu}}.$ (221) $$

Using $\eta,\nu\in(0,1]$,
we have

$$ $\displaystyle 0\leq$ $\displaystyle(\eta+5)\nu\leq 6,$ (222) $\displaystyle\max(C_{\alpha},1)^{1+\nu}\leq$ $\displaystyle\max(C_{\alpha},1)^{2}.$ (223) $$

The definition of $\eta$ in ([86](#A1.E86)) implies

$$ $\displaystyle 2\eta<(\eta+1)\nu.$ (224) $$

Hence, we get

$$ $\displaystyle\alpha_{t}\leq\frac{2^{(\eta+5)\nu}\max(C_{\alpha},1)^{1+\nu}}{(k+2)^{(\eta+1)\nu}}\leq\frac{64\max(C_{\alpha},1)^{2}}{(k+2)^{2\eta}}.$ (225) $$

The second inequality in ([86](#A1.E86)) together with the fact that $\nu\in(0,1]$ implies that $\eta<1$.
Consequently, we have $(\eta+1)^{2}<4$.
Therefore, $64<\frac{256}{(1+\eta)^{2}}$ and

$$ $\displaystyle\alpha_{t}\leq\frac{64\max(C_{\alpha},1)^{2}}{(k+2)^{2\eta}}\leq\frac{256\max(C_{\alpha},1)^{2}}{(\eta+1)^{2}(k+2)^{2\eta}}=\left(\frac{16\max(C_{\alpha},1)}{(\eta+1)(k+2)^{\eta}}\right)^{2}=T_{k+1}^{2}.$ (226) $$

We have now verified that ([207](#A1.E207)) holds for $m=k+1$,
which completes the induction.

#### A.5.3 Proof of Lemma 5

Proof
The fact that $\nu\in(0,1)$ and ([86](#A1.E86)) implies

$$ $\displaystyle\eta<\frac{\nu}{2-\nu}\leq\nu.$ (227) $$

The fact that $\eta\in[0,1]$ implies

$$ $\displaystyle\frac{16}{\eta+1}>8.$ (228) $$

Consequently, we have

$$ $\displaystyle T_{m}=\frac{16}{\eta+1}\frac{\max(C_{\alpha},1)}{(m+1)^{\eta}}>8\frac{C_{\alpha}}{(m+1)^{\nu}}=8\alpha_{m}.$ (229) $$

The definition of $\quantity{t_{m}}$ in ([88](#A1.E88)) implies that $t_{m+1}-t_{m}\geq 1$ for all $m\geq 0$,
so we have

$$ $\displaystyle t_{m}\geq m.$ (230) $$

Moreover, because $\alpha_{t}=\frac{C_{\alpha}}{(t+1)^{\nu}}$ is decreasing in $t$, for all $t\geq t_{m}\geq m$,
we have

$$ $\displaystyle\alpha_{t}\leq\alpha_{m}\leq\frac{T_{m}}{8}.$ (231) $$

The definition of $\quantity{t_{m}}$ in ([88](#A1.E88)) also implies that $\sum_{t=t_{m}}^{t_{m+1}-2}\alpha_{t}<T_{m}$.
Then we have

$$ $\displaystyle\bar{\alpha}_{m}=\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}=\sum_{t=t_{m}}^{t_{m+1}-2}\alpha_{t}+\alpha_{t_{m+1}-1}\leq T_{m}+\frac{T_{m}}{8}=\frac{9T_{m}}{8}\leq 2T_{m},$ (232) $$

which completes the proof.
Note here we have used the convention that $\sum_{t=i}^{j}\alpha_{t}\doteq 0$ if $i>j$.

#### A.5.4 Proof of Lemma 6

Proof
For all $t\geq 0$,

$$ $\displaystyle\norm{w_{t+1}+A^{-1}b}$ (233) $\displaystyle=$ $\displaystyle\norm{\left(w_{t}+A^{-1}b\right)+\alpha_{t}\hat{A}_{t+f(t)}^{\top}\left(\hat{A}_{t}(w_{t}+A^{-1}b)-\hat{A}_{t}A^{-1}b+\hat{b}_{t}\right)}$ (234) $\displaystyle\leq$ $\displaystyle\norm{w_{t}+A^{-1}b}+\alpha_{t}\norm{\hat{A}_{t+f(t)}^{\top}}\left(\norm{\hat{A}_{t}}\norm{w_{t}+A^{-1}b}+\norm{\hat{A}_{t}A^{-1}b}+\|\hat{b}_{t}\|\right)$ (235) $\displaystyle\leq$ $\displaystyle\norm{w_{t}+A^{-1}b}+\alpha_{t}H\left(H\norm{w_{t}+A^{-1}b}+H+H\right)$ (236) $\displaystyle=$ $\displaystyle\norm{w_{t}+A^{-1}b}+\alpha_{t}H^{2}\left(\norm{w_{t}+A^{-1}b}+2\right)$ (237) $$

Therefore, adding $2$ to both sides, we get

$$ $\displaystyle\norm{w_{t+1}+A^{-1}b}+2\leq(1+\alpha_{t}H^{2})\left(\norm{w_{t}+A^{-1}b}+2\right).$ (238) $$

Applying the inequality iteratively, we have that for all $t$ satisfying $t_{m}\leq t\leq t_{m+1}$

$$ $\displaystyle\norm{w_{t}+A^{-1}b}+2\leq\left(\norm{w_{t_{m}}+A^{-1}b}+2\right)\prod_{j=t_{m}}^{t_{m+1}}(1+\alpha_{t}H^{2})\leq e^{\bar{\alpha}_{m}H^{2}}\left(\norm{w_{t_{m}}+A^{-1}b}+2\right),$ (239) $$

where for the last two inequality, we used the fact that

$$ $\displaystyle\prod_{j=t_{m}}^{t_{m+1}-1}(1+\alpha_{t}H^{2})\leq\exp\left(\sum_{j=t_{m}}^{t_{m+1}-1}\alpha_{t}H^{2}\right)=\exp\left(\bar{\alpha}_{m}H^{2}\right).$ (240) $$

As $\bar{\alpha}_{m}\leq 2T_{m}$ (Lemma [5](#Thmtheorem5)) and $e^{2T_{m}H^{2}}\leq 2$,

$$ $\displaystyle\norm{w_{t}+A^{-1}b}+2$ $\displaystyle\leq e^{\bar{\alpha}_{m}H^{2}}\left(\norm{w_{t_{m}}+A^{-1}b}+2\right)$ (241) $\displaystyle\leq e^{2T_{m}H^{2}}\left(\norm{w_{t_{m}}+A^{-1}b}+2\right)$ (242) $\displaystyle\leq 2\left(\norm{w_{t_{m}}+A^{-1}b}+2\right).$ (243) $$

Hence,

$$ $\displaystyle\norm{w_{t}+A^{-1}b}\leq 2\left(\norm{w_{t_{m}}+A^{-1}b}+1\right).$ (244) $$

Therefore, for all $t_{m}\leq t\leq t_{m+1}$, we have

$$ $\displaystyle\norm{\left(w_{t}+A^{-1}b\right)-q_{m}}$ (245) $\displaystyle=$ $\displaystyle\norm{\left(w_{t}+A^{-1}b\right)-\left(w_{t_{m}}+A^{-1}b\right)}$ (246) $\displaystyle\leq$ $\displaystyle\norm{\sum_{j=t_{m}}^{t-1}\left(w_{j+1}+A^{-1}b\right)-\left(w_{j}+A^{-1}b\right)}$ (247) $\displaystyle\leq$ $\displaystyle\sum_{j=t_{m}}^{t-1}\norm{\left(w_{j+1}+A^{-1}b\right)-\left(w_{j}+A^{-1}b\right)}$ (248) $\displaystyle=$ $\displaystyle\sum_{j=t_{m}}^{t-1}\norm{\alpha_{j}\hat{A}_{j+f(j)}^{\top}\left(\hat{A}_{j}(w_{t}+A^{-1}b)-\hat{A}_{j}A^{-1}b+\hat{b}_{j}\right)}$ (249) $\displaystyle\leq$ $\displaystyle\sum_{j=t_{m}}^{t_{m+1}-1}\alpha_{t}H^{2}\left(\norm{w_{t}+A^{-1}b}+2\right)$ (Similar to ( 237 )) $\displaystyle\leq$ $\displaystyle\sum_{j=t_{m}}^{t_{m+1}-1}\alpha_{t}H^{2}\left(2\norm{w_{t_{m}}+A^{-1}b}+4\right)$ (Using ( 244 )) $\displaystyle=$ $\displaystyle 2\bar{\alpha}_{m}H^{2}\left(\norm{w_{t_{m}}+A^{-1}b}+2\right)$ (250) $\displaystyle\leq$ $\displaystyle 4T_{m}H^{2}\left(\norm{w_{t_{m}}+A^{-1}b}+2\right)$ (Using Lemma 5 ) $\displaystyle\leq$ $\displaystyle 8T_{m}H^{2}\left(\norm{w_{t_{m}}+A^{-1}b}+1\right)$ (251) $\displaystyle=$ $\displaystyle 8T_{m}H^{2}\left(\norm{q_{m}}+1\right),$ (252) $$

which completes the proof.

#### A.5.5 Proof of Lemma 7

Proof

$$ $\displaystyle\|q_{m}+g_{1,m}\|^{2}$ $\displaystyle=\|q_{m}-\bar{\alpha}_{m}A^{\top}Aq_{m}\|^{2}=\norm{\left(I-\bar{\alpha}_{m}A^{\top}A\right)q_{m}}^{2}$ (253) $\displaystyle=q_{m}^{\top}\left(I-\bar{\alpha}_{m}A^{\top}A\right)^{\top}\left(I-\bar{\alpha}_{m}A^{\top}A\right)q_{m}$ (254) $\displaystyle=\|q_{m}\|^{2}-2\bar{\alpha}_{m}q_{m}^{\top}A^{\top}Aq_{m}+\bar{\alpha}_{m}^{2}\norm{A^{\top}Aq_{m}}^{2}$ (255) $\displaystyle\leq\|q_{m}\|^{2}-2\bar{\alpha}_{m}\beta\|q_{m}\|^{2}+\bar{\alpha}_{m}^{2}\norm{A^{\top}}^{2}\|A\|^{2}\|q_{m}\|^{2}$ (256) $\displaystyle\leq\|q_{m}\|^{2}-2\bar{\alpha}_{m}\beta\|q_{m}\|^{2}+\bar{\alpha}_{m}^{2}H^{4}\|q_{m}\|^{2}$ (257) $\displaystyle\leq\|q_{m}\|^{2}-2\bar{\alpha}_{m}\beta\|q_{m}\|^{2}+2\bar{\alpha}_{m}T_{m}H^{4}\|q_{m}\|^{2}$ (Lemma 5 ) $\displaystyle\leq\|q_{m}\|^{2}-2\bar{\alpha}_{m}\beta\|q_{m}\|^{2}+\bar{\alpha}_{m}\beta\|q_{m}\|^{2}$ (Assumption of this Lemma) $\displaystyle\leq\left(1-\beta\bar{\alpha}_{m}\right)\|q_{m}\|^{2}$ (258) $\displaystyle\leq\left(1-\beta T_{m}\right)\|q_{m}\|^{2}.$ (Definition of $T_{m}$ in ( 88 )) $$

#### A.5.6 Proof of Lemma 8

Proof

$$ $\displaystyle\norm{g_{2,m}}\leq$ $\displaystyle\norm{\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\left(A^{\top}A-\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}|\mathcal{F}_{t_{m}+f(t_{m})}\right]\right)q_{m}}$ (259) $\displaystyle+\norm{\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\left(\hat{b}_{t}-\hat{A}_{t}A^{-1}b\right)|\mathcal{F}_{t_{m}+f(t_{m})}\right]}$ (260) $\displaystyle\leq$ $\displaystyle\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\norm{A^{\top}A-\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}|\mathcal{F}_{t_{m}+f(t_{m})}\right]}\norm{q_{m}}$ (261) $\displaystyle+\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\norm{\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\left(\hat{b}_{t}-\hat{A}_{t}A^{-1}b\right)|\mathcal{F}_{t_{m}+f(t_{m})}\right]}$ (262) $\displaystyle\leq$ $\displaystyle\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\norm{A^{\top}A-\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}|\mathcal{F}_{t_{m}+f(t_{m})}\right]}\norm{q_{m}}$ (263) $\displaystyle+\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\norm{\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{b}_{t}-A^{\top}b|\mathcal{F}_{t_{m}+f(t_{m})}\right]}$ (264) $\displaystyle+\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\norm{\mathbb{E}\left[A^{\top}b-\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}A^{-1}b|\mathcal{F}_{t_{m}+f(t_{m})}\right]}$ (265) $\displaystyle=$ $\displaystyle\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\norm{A^{\top}A-\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}|\mathcal{F}_{t_{m}+f(t_{m})}\right]}\norm{q_{m}}$ (266) $\displaystyle+\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\norm{\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{b}_{t}-A^{\top}b|\mathcal{F}_{t_{m}+f(t_{m})}\right]}$ (267) $\displaystyle+\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\norm{\mathbb{E}\left[A^{\top}A-\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}|\mathcal{F}_{t_{m}+f(t_{m})}\right]A^{-1}b}$ (268) $\displaystyle\leq$ $\displaystyle\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\norm{A^{\top}A-\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}|\mathcal{F}_{t_{m}+f(t_{m})}\right]}\norm{q_{m}}$ (269) $\displaystyle+\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\norm{\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{b}_{t}-A^{\top}b|\mathcal{F}_{t_{m}+f(t_{m})}\right]}$ (270) $\displaystyle+\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\norm{\mathbb{E}\left[A^{\top}A-\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}|\mathcal{F}_{t_{m}+f(t_{m})}\right]}\norm{A^{-1}b}.$ (271) $$

To bound the last three terms, we will consider separately whether $t_{m}+f(t_{m})<t_{m+1}$.
If $t_{m}+f(t_{m})\geq t_{m+1}$, then applying Lemma [3](#Thmtheorem3) yields

$$ $\displaystyle\norm{g_{2,m}}\leq$ $\displaystyle\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}C_{M}\norm{q_{m}}+\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}C_{M}+\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}C_{M}H$ (272) $\displaystyle=$ $\displaystyle C_{M}(\norm{q_{m}}+H+1)\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}.$ (273) $$

Since $\alpha_{t}=\frac{C_{\alpha}}{(1+t)^{\nu}}$ is a decreasing function in $t$, we have

$$ $\displaystyle\norm{g_{2,m}}$ $\displaystyle\leq C_{M}(\norm{q_{m}}+H+1)\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t_{m}}$ (274) $\displaystyle=C_{M}(\norm{q_{m}}+H+1)(t_{m+1}-t_{m})\alpha_{t_{m}}$ (275) $\displaystyle\leq C_{M}(\norm{q_{m}}+H+1)f(t_{m})\alpha_{t_{m}}.$ (276) $$

Assumption [4.4](#S4.assu_counter4) suggests $f(t)\leq C_{\tau}\alpha_{t}^{-\tau}$, so

$$ $\displaystyle\norm{g_{2,m}}$ $\displaystyle\leq C_{M}(\norm{q_{m}}+H+1)C_{\tau}\alpha_{t}^{-\tau}\alpha_{t_{m}}$ (277) $\displaystyle\leq C_{M}C_{\tau}(\norm{q_{m}}+H+1)\alpha_{t}^{1-\tau}.$ (278) $$

Because $\alpha_{t}\leq T_{m}^{2}$ for $t\geq t_{m}$ (Lemma [4](#Thmtheorem4)),

$$ $\displaystyle\norm{g_{2,m}}$ $\displaystyle\leq C_{M}C_{\tau}(\norm{q_{m}}+H+1)T_{m}^{2(1-\tau)}$ (279) $\displaystyle\leq C_{M}C_{\tau}(H+1)T_{m}^{2(1-\tau)}(\norm{q_{m}}+1).$ (280) $$

For the general case where $t_{m}+f(t_{m})<t_{m+1}$, we break the summation $\sum_{t=t_{m}}^{t_{m+1}-1}$ into two parts,
i.e. $\sum_{t=t_{m}}^{t_{m}+f(t_{m})-1}$ and $\sum_{t=t_{m}+f(t_{m})}^{t_{m+1}-1}$ and apply Lemma [3](#Thmtheorem3) separately.
We have

$$ $\displaystyle\norm{g_{2,m}}\leq$ $\displaystyle\sum_{t=t_{m}}^{t_{m}+f(t_{m})-1}\alpha_{t}\norm{A^{\top}A-\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}\mid\mathcal{F}_{t_{m}+f(t_{m})}\right]}\norm{q_{m}}$ (281) $\displaystyle+\sum_{t=t_{m}+f(t_{m})}^{t_{m+1}-1}\alpha_{t}\norm{A^{\top}A-\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}\mid\mathcal{F}_{t_{m}+f(t_{m})}\right]}\norm{q_{m}}$ (282) $\displaystyle+\sum_{t=t_{m}}^{t_{m}+f(t_{m})-1}\alpha_{t}\norm{\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{b}_{t}-A^{\top}b\mid\mathcal{F}_{t_{m}+f(t_{m})}\right]}$ (283) $\displaystyle+\sum_{t=t_{m}+f(t_{m})}^{t_{m+1}-1}\alpha_{t}\norm{\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{b}_{t}-A^{\top}b\mid\mathcal{F}_{t_{m}+f(t_{m})}\right]}$ (284) $\displaystyle+\sum_{t=t_{m}}^{t_{m}+f(t_{m})-1}\alpha_{t}\norm{\mathbb{E}\left[A^{\top}A-\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}\mid\mathcal{F}_{t_{m}+f(t_{m})}\right]}\norm{A^{-1}b}$ (285) $\displaystyle+\sum_{t=t_{m}+f(t_{m})}^{t_{m+1}-1}\alpha_{t}\norm{\mathbb{E}\left[A^{\top}A-\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}\mid\mathcal{F}_{t_{m}+f(t_{m})}\right]}\norm{A^{-1}b}$ (286) $\displaystyle\leq$ $\displaystyle\sum_{t=t_{m}}^{t_{m}+f(t_{m})-1}\alpha_{t}C_{M}\norm{q_{m}}+\sum_{t=t_{m}+f(t_{m})}^{t_{m+1}-1}\alpha_{t}C_{M}\left(\chi^{f(t)}+\chi^{t-[t_{m}+f(t_{m})]}\right)\norm{q_{m}}$ (287) $\displaystyle+\sum_{t=t_{m}}^{t_{m}+f(t_{m})-1}\alpha_{t}C_{M}+\sum_{t=t_{m}+f(t_{m})}^{t_{m+1}-1}\alpha_{t}C_{M}\left(\chi^{f(t)}+\chi^{t-[t_{m}+f(t_{m})]}\right)$ (288) $\displaystyle+\sum_{t=t_{m}}^{t_{m}+f(t_{m})-1}\alpha_{t}C_{M}H+\sum_{t=t_{m}+f(t_{m})}^{t_{m+1}-1}\alpha_{t}C_{M}\left(\chi^{f(t)}+\chi^{t-[t_{m}+f(t_{m})]}\right)H$ (289) $\displaystyle\leq$ $\displaystyle C_{M}(\norm{q_{m}}+H+1)\left[\sum_{t=t_{m}}^{t_{m}+f(t_{m})-1}\alpha_{t}+\sum_{t=t_{m}+f(t_{m})}^{t_{m+1}-1}\alpha_{t}\left(\chi^{f(t)}+\chi^{t-[t_{m}+f(t_{m})]}\right)\right].$ (290) $$

Because $\alpha_{t}=\frac{C_{\alpha}}{(1+t)^{\nu}}$ is a decreasing function in $t$ and $\alpha_{t}\leq T_{m}^{2}$ for $t\geq t_{m}$ (Lemma [4](#Thmtheorem4)), we get

$$ $\displaystyle\norm{g_{2,m}}$ $\displaystyle\leq C_{M}(\norm{q_{m}}+H+1)\left[\sum_{t=t_{m}}^{t_{m}+f(t_{m})-1}\alpha_{t_{m}}+T_{m}^{2}\sum_{t=t_{m}+f(t_{m})}^{t_{m+1}-1}\left(\chi^{f(t)}+\chi^{t-[t_{m}+f(t_{m})]}\right)\right]$ (291) $\displaystyle\leq C_{M}(\norm{q_{m}}+H+1)\left[f(t_{m})\alpha_{t_{m}}+T_{m}^{2}\left(\sum_{t=t_{m}+f(t_{m})}^{t_{m+1}-1}\chi^{f(t)}+\sum_{t=t_{m}+f(t_{m})}^{t_{m+1}-1}\chi^{t-[t_{m}+f(t_{m})]}\right)\right]$ (292) $\displaystyle\leq C_{M}(\norm{q_{m}}+H+1)\left[f(t_{m})\alpha_{t_{m}}+T_{m}^{2}\left(\sum_{t=0}^{\infty}\chi^{f(t)}+\sum_{t=0}^{\infty}\chi^{t}\right)\right]$ (293) $$

Assumption [4.4](#S4.assu_counter4) suggests that $f(t)\leq C_{\tau}\alpha_{t}^{-\tau}$ and $L(f,\chi)=\sum_{t=0}^{\infty}\chi^{f(t)}<\infty$. Therefore,

$$ $\displaystyle\norm{g_{2,m}}$ $\displaystyle\leq C_{M}(\norm{q_{m}}+H+1)\left[C_{\tau}\alpha_{t_{m}}^{-\tau}\alpha_{t_{m}}+T_{m}^{2}\left(L(f,\chi)+\sum_{t=0}^{\infty}\chi^{t}\right)\right]$ (294) $\displaystyle\leq C_{M}(\norm{q_{m}}+H+1)\left[C_{\tau}\alpha_{t_{m}}^{1-\tau}+T_{m}^{2}\left(L(f,\chi)+\frac{1}{1-\chi}\right)\right]$ (295) $\displaystyle\leq C_{M}(\norm{q_{m}}+H+1)\left[C_{\tau}T_{m}^{2(1-\tau)}+T_{m}^{2}\left(L(f,\chi)+\frac{1}{1-\chi}\right)\right].$ (296) $$

When $T_{m}\leq 1$,
we then have

$$ $\displaystyle\norm{g_{2,m}}\leq C_{M}T_{m}^{2(1-\tau)}(H+1)\left(C_{\tau}+L(f,\chi)+\frac{1}{1-\chi}\right)(\norm{q_{m}}+1),$ (297) $$

which completes the proof.

#### A.5.7 Proof of Lemma 9

Proof
Firstly, we have

$$ $\displaystyle\|g_{3,m}\|\leq$ $\displaystyle\norm{\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\left(\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}|\mathcal{F}_{t_{m}+f(t_{m})}\right]-\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}\right)q_{m}}$ (298) $\displaystyle+\norm{\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\left(\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\left(\hat{b}_{t}-\hat{A}_{t}A^{-1}b\right)|\mathcal{F}_{t_{m}+f(t_{m})}\right]-\hat{A}_{t+f(t)}^{\top}\left(\hat{b}_{t}-\hat{A}_{t}A^{-1}b\right)\right)}$ (299) $\displaystyle\leq$ $\displaystyle\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\left(\norm{\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}|\mathcal{F}_{t_{m}+f(t_{m})}\right]}+\norm{\hat{A}_{t+f(t)}^{\top}}\|\hat{A}_{t}\|\right)\|q_{m}\|$ (300) $\displaystyle+\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\left(\norm{\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\left(\hat{b}_{t}-\hat{A}_{t}A^{-1}b\right)|\mathcal{F}_{t_{m}+f(t_{m})}\right]}+\norm{\hat{A}_{t+f(t)}^{\top}}\left(\|\hat{b}_{t}\|+\norm{\hat{A}_{t}A^{-1}b}\right)\right)$ (301) $\displaystyle\leq$ $\displaystyle\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\left(\mathbb{E}\left[\norm{\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}}|\mathcal{F}_{t_{m}+f(t_{m})}\right]+H\cdot H\right)\|q_{m}\|$ (302) $\displaystyle+\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\left(\mathbb{E}\left[\norm{\hat{A}_{t+f(t)}^{\top}\left(\hat{b}_{t}-\hat{A}_{t}A^{-1}b\right)}|\mathcal{F}_{t_{m}+f(t_{m})}\right]+H(H+H)\right)$ (303) $\displaystyle\leq$ $\displaystyle\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\left(\mathbb{E}\left[\norm{\hat{A}_{t+f(t)}^{\top}}\norm{\hat{A}_{t}}|\mathcal{F}_{t_{m}+f(t_{m})}\right]+H^{2}\right)\|q_{m}\|$ (304) $\displaystyle+\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\left(\mathbb{E}\left[\norm{\hat{A}_{t+f(t)}^{\top}}\left(\norm{\hat{b}_{t}}+\norm{\hat{A}_{t}A^{-1}b}\right)|\mathcal{F}_{t_{m}+f(t_{m})}\right]+2H^{2}\right)$ (305) $\displaystyle\leq$ $\displaystyle\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\left(H^{2}+H^{2}\right)\|q_{m}\|+\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\left(H(H+H)+2H^{2}\right)$ (306) $\displaystyle\leq$ $\displaystyle 2\bar{\alpha}_{m}H^{2}(\norm{q_{m}}+2)$ (307) $\displaystyle\leq$ $\displaystyle 4T_{m}H^{2}(\norm{q_{m}}+2)$ (Lemma 5 ) $\displaystyle\leq$ $\displaystyle 8T_{m}H^{2}(\norm{q_{m}}+1).$ (308) $$

Secondly,

$$ $\displaystyle\mathbb{E}\left[g_{3,m}|\mathcal{F}_{t_{m}+f(t_{m})}\right]=0$ (309) $$

holds trivially,
which completes the proof.

#### A.5.8 Proof of Lemma 10

Proof

$$ $\displaystyle\|g_{4,m}\|$ $\displaystyle=\norm{\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}\left[q_{m}-\left(w_{t}+A^{-1}b\right)\right]}$ (310) $\displaystyle\leq\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}\norm{\hat{A}_{t+f(t)}^{\top}}\|\hat{A}_{t}\|\norm{q_{m}-\left(w_{t}+A^{-1}b\right)}.$ (311) $$

Then, by Lemma [6](#Thmtheorem6), we have

$$ $\displaystyle\|g_{4,m}\|$ $\displaystyle\leq\sum_{t=t_{m}}^{t_{m+1}-1}\alpha_{t}H\cdot H\cdot 8T_{m}H^{2}(\|q_{m}\|+1)$ (312) $\displaystyle=8\bar{\alpha}_{m}T_{m}H^{4}(\|q_{m}\|+1),$ (313) $$

which completes the proof.

#### A.5.9 Proof of Lemma 11

Proof

$$ $\displaystyle\norm{q_{m+1}}^{2}=$ $\displaystyle\norm{q_{m}+g_{1,m}+g_{2,m}+g_{3,m}+g_{4,m}}^{2}$ (314) $\displaystyle=$ $\displaystyle\norm{q_{m}+g_{1,m}}^{2}+\norm{g_{2,m}+g_{3,m}+g_{4,m}}^{2}+2(q_{m}+g_{1,m})^{\top}(g_{2,m}+g_{3,m}+g_{4,m})$ (315) $\displaystyle\leq$ $\displaystyle\norm{q_{m}+g_{1,m}}^{2}+\norm{g_{2,m}+g_{3,m}+g_{4,m}}^{2}$ (316) $\displaystyle+2(q_{m}+g_{1,m})^{\top}g_{3,m}+2\norm{q_{m}+g_{1,m}}\norm{g_{2,m}+g_{4,m}}.$ (317) $$

Lemma [7](#Thmtheorem7) implies that $\norm{q_{m}+g_{1,m}}^{2}\leq(1-\beta T_{m})\norm{q_{m}}^{2}$ and $\norm{q_{m}+g_{1,m}}=\mathcal{O}(\norm{q_{m}})$,
Lemma [8](#Thmtheorem8) suggests that $\norm{g_{2,m}}=\mathcal{O}\left(T_{m}^{2(1-\tau)}(\|q_{m}\|+1)\right)$,
Lemma [9](#Thmtheorem9) suggests that $\norm{g_{3,m}}=\mathcal{O}(T_{m}(\|q_{m}\|+1))$, and Lemma [10](#Thmtheorem10) suggests that $\norm{g_{4,m}}=\mathcal{O}\left(T_{m}^{2}(\|q_{m}\|+1)\right)$. Hence,

$$ $\displaystyle\norm{g_{2,m}+g_{3,m}+g_{4,m}}\leq\norm{g_{2,m}}+\norm{g_{3,m}}+\norm{g_{4,m}}=\mathcal{O}(T_{m}(\|q_{m}\|+1)),$ (318) $$

and

$$ $\displaystyle\norm{g_{2,m}+g_{4,m}}=\mathcal{O}\left(T_{m}^{2(1-\tau)}(\|q_{m}\|+1)\right).$ (319) $$

Moreover,
both $q_{m}$ and $g_{1,m}=-\bar{\alpha}_{m}A^{\top}Aq_{m}$ are adapted to $\mathcal{F}_{t_{m}+f(t_{m})}$ and [9](#Thmtheorem9) implies that $\mathbb{E}\left[g_{3,m}|\mathcal{F}_{t_{m}+f(t_{m})}\right]=0$.
We, therefore, have

$$ $\displaystyle\mathbb{E}\left[(q_{m}+g_{1,m})^{\top}g_{3,m}|\mathcal{F}_{t_{m}+f(t_{m})}\right]=0.$ (320) $$

Lastly, putting everything together, we have

$$ $\displaystyle\mathbb{E}\left[\norm{q_{m+1}}^{2}|\mathcal{F}_{t_{m}+f(t_{m})}\right]$ (321) $\displaystyle\leq$ $\displaystyle(1-\beta T_{m})\norm{q_{m}}^{2}+\mathcal{O}(T_{m}(\|q_{m}\|+1))^{2}+\mathcal{O}(\norm{q_{m}})\mathcal{O}\left(T_{m}^{2(1-\tau)}(\|q_{m}\|+1)\right)$ (322) $\displaystyle\leq$ $\displaystyle(1-\beta T_{m})\norm{q_{m}}^{2}+\mathcal{O}\left(T_{m}^{2(1-\tau)}(\|q_{m}\|+1)^{2}\right)$ (323) $\displaystyle\leq$ $\displaystyle(1-\beta T_{m})\norm{q_{m}}^{2}+\mathcal{O}\left(T_{m}^{2(1-\tau)}(\|q_{m}\|^{2}+1)\right),$ (324) $$

where the last inequality comes from the fact that $(\norm{q_{m}}+1)^{2}\leq 2(\|q_{m}\|^{2}+1)$.
In conclusion, there exists a constant $D$ such that

$$ $\displaystyle\mathbb{E}\left[\norm{q_{m+1}}^{2}|\mathcal{F}_{t_{m}+f(t_{m})}\right]\leq\left(1-\beta T_{m}+DT_{m}^{2(1-\tau)}\right)\norm{q_{m}}^{2}+DT_{m}^{2(1-\tau)},$ (325) $$

which completes the proof.

#### A.5.10 Proof of Lemma 12

Proof
To prove the lemma,
we will invoke a supermartingale convergence theorem stated as follows.

###### Theorem 16

(Proposition 4.2 in Bertsekas and Tsitsiklis ())
Let $Y_{m}$, $X_{m}$, and $Z_{m}$, $m\geq 0$ be three sequences of random variables and let $\bar{\mathcal{F}}_{m}$, $m\geq 0$, be sets of random variables such that $\bar{\mathcal{F}}_{m}\subseteq\bar{\mathcal{F}}_{m+1}$ for all $m$. Suppose that

- 1.
The random variables $Y_{m}$, $X_{m}$, and $Z_{m}$ are non-negative and are functions of the random variables in $\bar{\mathcal{F}}_{m}$,
- 2.
For each $m$, we have $\mathbb{E}\left[Y_{m+1}|\bar{\mathcal{F}}_{m}\right]\leq Y_{m}-X_{m}+Z_{m}$,
- 3.
There holds $\sum_{m=0}^{\infty}Z_{m}<\infty$.

Then, we have $\sum_{m=0}^{\infty}X_{m}<\infty$ almost surely, and the sequence $Y_{m}$ converges almost surely to a non-negative random variable $Y$.

In our case, we let

$$ $\displaystyle Y_{m}=$ $\displaystyle\|q_{m}\|^{2},$ (326) $\displaystyle X_{m}=$ $\displaystyle\frac{1}{2}\beta T_{m}\|q_{m}\|^{2},$ (327) $\displaystyle Z_{m}=$ $\displaystyle DT_{m}^{2(1-\tau)},$ (328) $\displaystyle\bar{\mathcal{F}}_{m}=$ $\displaystyle\mathcal{F}_{t_{m}+f(t_{m})}.$ (329) $$

The first condition of Theorem [16](#Thmtheorem16) holds trivially.
For the second condition of Theorem [16](#Thmtheorem16) to hold,
we rely on ([105](#A1.E105)) in Lemma [11](#Thmtheorem11).
According to the definition of $T_{m}$ in ([85](#A1.E85)),
we have

$$ $\displaystyle\lim_{m\to\infty}T_{m}=0.$ (330) $$

As a result,
the condition

$$ $\displaystyle T_{m}\leq\min\left(\frac{\beta}{2H^{4}},1,\frac{\ln(2)}{2H^{2}}\right)$ (331) $$

in Lemma [11](#Thmtheorem11) holds for sufficiently large $m$.
Moreover, since

$$ $\displaystyle\tau<$ $\displaystyle\frac{3}{2}-\frac{1}{\nu}$ (Assumption 4.4 ) $\displaystyle\leq$ $\displaystyle\frac{3}{2}-\frac{1}{1}$ (Assumption 4.3 ) $\displaystyle=$ $\displaystyle\frac{1}{2},$ (332) $$

we have

$$ $\displaystyle 2(1-\tau)>1.$ (333) $$

Consequently,
the condition

$$ $\displaystyle DT_{m}^{2(1-\tau)}\leq\frac{1}{2}\beta T_{m},$ (334) $$

which is equivalent to

$$ $\displaystyle T_{m}^{2(1-\tau)-1}\leq\frac{\beta}{2D},$ (335) $$

also holds for sufficiently large $m$ as $\lim_{m\to\infty}T_{m}=0$.
Crucially, $D$ is deterministic because $D$ only depends on $H$, $\beta$, $C_{\tau}$, $C_{M}$, $L(f,\chi)$, and $\chi$, which are all deterministic quantities.
Therefore,
there always exists a finite and deterministic $m_{0}$ such that the subsequence $\quantity{X_{m},Y_{m},Z_{m}}_{m\geq m_{0}}$ verifies the second condition.
Since $\eta>\frac{1}{2(1-\tau)}$, i.e. $2(1-\tau)\eta>1$, by p-test, we can deduce that

$$ $\displaystyle\sum_{m=0}^{\infty}Z_{m}$ $\displaystyle=\sum_{m=0}^{\infty}DT_{m}^{2(1-\tau)}=D\sum_{m=0}^{\infty}\left(\frac{16\max(C_{\alpha},1)}{(\eta+1)(m+1)^{\eta}}\right)^{2(1-\tau)}$ (336) $\displaystyle=\frac{(16\max(C_{\alpha},1))^{2(1-\tau)}D}{(\eta+1)^{2(1-\tau)}}\sum_{m=0}^{\infty}\frac{1}{(\eta+1)^{2(1-\tau)\eta}}<\infty.$ (337) $$

The third condition of Theorem [16](#Thmtheorem16),
therefore, also holds.
All the conditions of Theorem [16](#Thmtheorem16) are now verified for the subsequence $\quantity{X_{m},Y_{m},Z_{m}}_{m\geq m_{0}}$,
which implies that the sequence $\quantity{\norm{q_{m}}^{2}}_{m\geq 0}$ converges
and

$$ $\displaystyle\frac{1}{2}\beta\sum_{m=0}^{\infty}T_{m}\norm{q_{m}}^{2}<\infty.$ (338) $$

As $\eta<1$, we have

$$ $\displaystyle\sum_{m=0}^{\infty}T_{m}=\sum_{m=0}^{\infty}\frac{16\max(C_{\alpha},1)}{(\eta+1)(m+1)^{\eta}}=\frac{16\max(C_{\alpha},1)}{\eta+1}\sum_{m=0}^{\infty}\frac{1}{(m+1)^{\eta}}=\infty.$ (339) $$

Thus, $\norm{q_{m}}^{2}$ must converge to zero.
Otherwise, $\sum_{m=0}^{\infty}X_{m}=\frac{1}{2}\beta\sum_{m=0}^{\infty}T_{m}\norm{q_{m}}^{2}$ diverges to infinity.
Thus, $q_{m}$ converges to 0 almost surely,
which completes the proof.

###### Theorem 16

#### A.5.11 Proof of Lemma 13

Proof
First, we prove the bounds for each function.

Bound for $g_{t}(\cdot)$:

$$ $\displaystyle\|g_{t}(w)\|$ $\displaystyle=\norm{-\hat{A}_{t+f(t)}^{\top}(\hat{A}_{t}w+\hat{b}_{t})}\leq\norm{\hat{A}_{t+f(t)}^{\top}}(\|\hat{A}_{t}\|\|w\|+\|\hat{b}_{t}\|)$ (340) $\displaystyle\leq H(HB+H)=H^{2}(B+1).$ (341) $$

Bound for $\bar{g}(\cdot)$:

$$ $\displaystyle\norm{\bar{g}(w)}=\norm{A^{\top}(Aw+b)}\leq\norm{A^{\top}}(\norm{A}\norm{w}+\norm{b})\leq H(HB+B)=H^{2}(B+1).$ (342) $$

Bound for $\Lambda_{t}(\cdot)$:

$$ $\displaystyle|\Lambda_{t}(w)|$ $\displaystyle=|\langle w-w_{*},g_{t}(w)-\bar{g}(w)\rangle|\leq\|w-w_{*}\|\|g_{t}(w)-\bar{g}(w)\|$ (343) $\displaystyle\leq(\|w\|+\|w_{*}\|)(\|g_{t}(w)\|-\|\bar{g}(w)\|)\leq(B+B)[H^{2}(B+1)+H^{2}(B+1)]$ (344) $\displaystyle=4H^{2}B(B+1).$ (345) $$

Hence, by taking $C_{g}=\max\{H^{2}(B+1),4H^{2}B(B+1)\}$, we have the result stated.
Second, we prove the functions are Lipschitz.

$g_{t}(\cdot)$ is $H^{2}$-Lipschitz:

$$ $\displaystyle\norm{g_{t}(w)-g_{t}(w^{\prime})}$ $\displaystyle=\norm{-\hat{A}_{t+f(t)}^{\top}(\hat{A}_{t}w+\hat{b}_{t})+\hat{A}_{t+f(t)}^{\top}(\hat{A}_{t}w^{\prime}+\hat{b}_{t})}=\norm{\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}(w-w^{\prime})}$ (346) $\displaystyle\leq\norm{\hat{A}_{t+f(t)}^{\top}}\norm{\hat{A}_{t}}\norm{w-w^{\prime}}\leq H^{2}\norm{w-w^{\prime}}$ (347) $$

$\bar{g}(\cdot)$ is $H^{2}$-Lipschitz:

$$ $\displaystyle\norm{\bar{g}(w)-\bar{g}(w^{\prime})}$ $\displaystyle=\norm{-A^{\top}(Aw+b)+A^{\top}(Aw^{\prime}+b)}=\norm{A^{\top}A(w^{\prime}-w)}$ (348) $\displaystyle\leq\norm{A^{\top}}\norm{A}\norm{w^{\prime}-w}\leq H^{2}\norm{w^{\prime}-w}.$ (349) $$

$\Lambda_{t}(\cdot)$ is $2H^{2}(3B+1)$-Lipschitz:

$$ $\displaystyle|\Lambda_{t}(w)-\Lambda_{t}(w^{\prime})|$ (350) $\displaystyle=$ $\displaystyle|\langle w-w_{*},g_{t}(w)-\bar{g}(w)\rangle-\langle w^{\prime}-w_{*},g_{t}(w^{\prime})-\bar{g}(w^{\prime})\rangle|$ (351) $\displaystyle=$ $\displaystyle|\langle w-w_{*},g_{t}(w)-\bar{g}(w)-(g_{t}(w^{\prime})-\bar{g}(w^{\prime}))\rangle+\langle w-w_{*}-(w^{\prime}-w_{*}),g_{t}(w^{\prime})-\bar{g}(w^{\prime})\rangle|$ (352) $\displaystyle\leq$ $\displaystyle|\langle w-w_{*},g_{t}(w)-\bar{g}(w)-(g_{t}(w^{\prime})-\bar{g}(w^{\prime}))\rangle|+|\langle w-w^{\prime},g_{t}(w^{\prime})-\bar{g}(w^{\prime})\rangle|$ (353) $\displaystyle\leq$ $\displaystyle\|w-w_{*}\|\|g_{t}(w)-\bar{g}(w)-(g_{t}(w^{\prime})-\bar{g}(w^{\prime}))\|+\|w-w^{\prime}\|\|g_{t}(w^{\prime})-\bar{g}(w^{\prime})\|$ (354) $\displaystyle\leq$ $\displaystyle(\|w\|+\|w_{*}\|)(\|g_{t}(w^{\prime})-g_{t}(w)\|+\|\bar{g}(w)-\bar{g}(w^{\prime})\|)+(\|g_{t}(w^{\prime})\|+\|\bar{g}(w^{\prime})\|)\|w-w^{\prime}\|$ (355) $\displaystyle\leq$ $\displaystyle(B+B)(\|g_{t}(w^{\prime})-g_{t}(w)\|+\|\bar{g}(w)-\bar{g}(w^{\prime})\|)+[H^{2}(B+1)+H^{2}(B+1)]\|w-w^{\prime}\|$ (356) $\displaystyle\leq$ $\displaystyle 2B(\|g_{t}(w^{\prime})-g_{t}(w)\|+\|\bar{g}(w)-\bar{g}(w^{\prime})\|)+2H^{2}(B+1)\|w-w^{\prime}\|$ (357) $\displaystyle\leq$ $\displaystyle 2B(H^{2}\|w^{\prime}-w\|+H^{2}\|w^{\prime}-w\|)+2H^{2}(B+1)\|w-w^{\prime}\|$ (358) $\displaystyle=$ $\displaystyle 2H^{2}(3B+1)\|w-w^{\prime}\|.$ (359) $$

Therefore, by taking $C_{Lip}=\max\{H^{2},2H^{2}(3B+1)\}$, we have the result stated.

Lastly, we prove the following inequality regarding the inner product.

$$ $\displaystyle\langle w-w^{\prime},\bar{g}(w)-\bar{g}(w^{\prime})\rangle$ $\displaystyle=\left\langle w-w^{\prime},-A^{\top}(Aw+b)+A^{\top}(Aw^{\prime}+b)\right\rangle$ (360) $\displaystyle=-(w-w^{\prime})^{\top}A^{\top}A(w-w^{\prime})\leq-\beta\|w-w^{\prime}\|^{2},$ (361) $$

where the last inequality holds due to ([101](#A1.E101)).

#### A.5.12 Proof of Lemma 14

Proof
For any $i\geq 0$, since $w_{i}$ lies in the ball for projection,
we have

$$ $\displaystyle\norm{w_{i+1}-w_{i}}$ $\displaystyle=\norm{\Gamma(w_{i}+\alpha_{i}g_{i}(w_{i}))-w_{i}}$ (362) $\displaystyle=\norm{\Gamma(w_{i}+\alpha_{i}g_{i}(w_{i}))-\Gamma(w_{i})}$ (363) $\displaystyle\leq\norm{\Gamma(w_{i}+\alpha_{i}g_{i}(w_{i})-w_{i})}$ ( $\Gamma(\cdot)$ is non-expansive) $\displaystyle=\norm{\Gamma(\alpha_{i}g_{i}(w_{i}))}$ (364) $\displaystyle\leq\norm{\alpha_{i}g_{i}(w_{i})}$ (365) $\displaystyle=\alpha_{i}\norm{g_{i}(w_{i})}$ (366) $\displaystyle\leq\alpha_{i}C_{g}.$ (Lemma 13 ) $$

Therefore, by telescoping, we can deduce that for all $0<k<t$,

$$ $\displaystyle\norm{w_{t}-w_{t-k}}\leq\sum_{i=t-k}^{t-1}\norm{w_{i+1}-w_{i}}\leq\sum_{i=t-k}^{t-1}C_{g}\alpha_{i}=C_{g}\sum_{i=t-k}^{t-1}\alpha_{i}.$ (367) $$

Because $\frac{1}{t+1}$ is a decreasing function in $t$, for all $i\in[t,t+1]$, $\frac{1}{t+1}\leq\frac{1}{i}$.
As a consequence,
$\frac{1}{t+1}\leq\int_{t}^{t+1}\frac{1}{i}$, and

$$ $\displaystyle\sum_{i=t-k}^{t}\frac{1}{i+1}\leq\sum_{i=t-k}^{t}\int_{i}^{i+1}\frac{1}{j}\leq\int_{t-k}^{t}\frac{1}{i}=\ln(t)-\ln(t-k)=\ln\left(\frac{t}{t-k}\right).$ (368) $$

In addition, given that $\alpha_{t}=\frac{C_{\alpha}}{t+1}$,
we have

$$ $\displaystyle\norm{w_{t}-w_{t-k}}$ $\displaystyle\leq C_{g}\sum_{i=t-k}^{t-1}\alpha_{i}=C_{g}\sum_{i=t-k}^{t-1}\frac{C_{\alpha}}{i+1}\leq C_{g}C_{\alpha}\ln\left(\frac{t}{t-k}\right).$ (369) $$

Applying Lemma [13](#Thmtheorem13) again, we get

$$ $\displaystyle|\Lambda_{t}(w_{t})-\Lambda_{t}(w_{t-k})|\leq C_{g}C_{\alpha}C_{Lip}\ln\left(\frac{t}{t-k}\right)$ (370) $$

and hence

$$ $\displaystyle\Lambda_{t}(w_{t})\leq\Lambda_{t}(w_{t-k})+C_{g}C_{\alpha}C_{Lip}\ln\left(\frac{t}{t-k}\right).$ (371) $$

We now bound the expectation of $\Lambda_{t}(w_{t-k})$ conditioning on $\mathcal{F}_{t-k+f(t-k)}$.
In particular, we have

$$ $\displaystyle\mathbb{E}\left[\Lambda_{t}(w_{t-k})|\mathcal{F}_{t-k+f(t-k)}\right]$ (372) $\displaystyle=$ $\displaystyle\mathbb{E}\left[\langle w_{t-k}-w_{*},g_{t}(w_{t-k})-\bar{g}(w_{t-k})\rangle|\mathcal{F}_{t-k+f(t-k)}\right]$ (373) $\displaystyle=$ $\displaystyle\mathbb{E}\left[\left\langle w_{t-k}-w_{*},\hat{A}_{t+f(t)}^{\top}(\hat{A}_{t}w_{t-k}+\hat{\hat{b}}_{t})-A^{\top}(Aw_{t-k}-b)\right\rangle|\mathcal{F}_{t-k+f(t-k)}\right]$ (374) $\displaystyle=$ $\displaystyle\mathbb{E}\left[\left\langle w_{t-k}-w_{*},\left(\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}-A^{\top}A\right)w_{t-k}-\left(\hat{A}_{t+f(t)}^{\top}\hat{b}_{t}-A^{\top}b\right)\right\rangle|\mathcal{F}_{t-k+f(t-k)}\right].$ (375) $$

As expectation and dot product are linear and $w_{t-k}$ is adapted to $\mathcal{F}_{t-k+f(t-k)}$,
we can further reduce our expectations as

$$ $\displaystyle\mathbb{E}\left[\Lambda_{t}(w_{t-k})|\mathcal{F}_{t-k+f(t-k)}\right]$ (377) $\displaystyle=$ $\displaystyle\left\langle w_{t-k}-w_{*},\left(\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}|\mathcal{F}_{t-k+f(t-k)}\right]-A^{\top}A\right)w_{t-k}-\left(\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{b}_{t}|\mathcal{F}_{t-k+f(t-k)}\right]-A^{\top}b\right)\right\rangle$ (378) $\displaystyle\leq$ $\displaystyle\norm{w_{t-k}-w_{*}}\norm{\left(\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}|\mathcal{F}_{t-k+f(t-k)}\right]-A^{\top}A\right)w_{t-k}-\left(\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{b}_{t}|\mathcal{F}_{t-k+f(t-k)}\right]-A^{\top}b\right)}$ (379) $\displaystyle\leq$ $\displaystyle(\norm{w_{t-k}}+\norm{w_{*}})\left(\norm{\left(\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}|\mathcal{F}_{t-k+f(t-k)}\right]-A^{\top}A\right)w_{t-k}}+\norm{\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{b}_{t}|\mathcal{F}_{t-k+f(t-k)}\right]-A^{\top}b}\right)$ (380) $\displaystyle\leq$ $\displaystyle(\norm{w_{t-k}}+\norm{w_{*}})\left(\norm{\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}|\mathcal{F}_{t-k+f(t-k)}\right]-A^{\top}A}\norm{w_{t-k}}+\norm{\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{b}_{t}|\mathcal{F}_{t-k+f(t-k)}\right]-A^{\top}b}\right)$ (381) $\displaystyle\leq$ $\displaystyle(B+B)\left(\norm{\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}|\mathcal{F}_{t-k+f(t-k)}\right]-A^{\top}A}B+\norm{\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{b}_{t}|\mathcal{F}_{t-k+f(t-k)}\right]-A^{\top}b}\right)$ (382) $\displaystyle\leq$ $\displaystyle 2B\left(\norm{\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{A}_{t}|\mathcal{F}_{t-k+f(t-k)}\right]-A^{\top}A}B+\norm{\mathbb{E}\left[\hat{A}_{t+f(t)}^{\top}\hat{b}_{t}|\mathcal{F}_{t-k+f(t-k)}\right]-A^{\top}b}\right).$ (383) $$

Applying Lemma [3](#Thmtheorem3),
we get

$$ $\displaystyle\mathbb{E}[\Lambda_{t}(w_{t-k})|\mathcal{F}_{t-k+f(t-k)}]\leq$ $\displaystyle 2B(B+1)C_{M}\begin{cases}1&t<t-k+f(t-k)\\ \chi^{f(t)}+\chi^{t-(t-k+f(t-k))}&t-k+f(t-k)\leq t\\ \end{cases}.$ (384) $$

Taking total expectations then yields

$$ $\displaystyle\mathbb{E}[\Lambda_{t}(w_{t-k})]\leq 2B(B+1)C_{M}\begin{cases}1&k<f(t-k)\\ \chi^{f(t)}+\chi^{t-(t-k+f(t-k))}&k\geq f(t-k)\\ \end{cases}.$ (385) $$

Plugging ([385](#A1.E385)) into the expectation of ([371](#A1.E371)) yields

$$ $\displaystyle\mathbb{E}[\Lambda_{t}(w_{t})]\leq$ $\displaystyle C_{g}C_{\alpha}C_{Lip}\ln\left(\frac{t}{t-k}\right)+2B(B+1)C_{M}\begin{cases}1&k<f(t-k)\\ \chi^{f(t)}+\chi^{t-(t-k+f(t-k))}&k\geq f(t-k)\end{cases},$ (386) $$

which completes the proof.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: Is it necessary to take an increasing function f(t)? Besides removing the dependence between data at step t and t+f(t) to establish the convergence proof, is there any other reason to use an increasing function?
soundness: 3
strengths: The problem to tackle is well stated, which is to stabilize off-policy learning and improve the previous algorithm ATD and GTD: the proposed algorithm saves memory compared to the ATD algorithm and increases the convergence rate compared to GTD. Also, the paper is clearly written and easy to follow, with rigorously stated assumptions and lemmas.
summary: The paper aims to develop a convergent algorithm for off-policy temporal difference learning under linear function approximation. The proposed algorithm directly minimizes the L2-norm of expected TD updates (NEU) $||Aw+b||^2$, improving the memory requirement of estimating matrix $A$ from the previous ATD algorithm. Meanwhile, the proposed algorithm reduces the number of learning rates from two to one compared to GTD, another NEU minimization algorithm. It maintains the convergent property with a convergent rate $\tilde{O}(1/t)$. Moreover, the algorithm is tested on Baird’s counterexample and is shown to avoid divergence in the deadly triad.
weaknesses: The approach needs to be more motivated. GTD is known to suffer from a low convergent rate compared to TD. More experiments to compare the convergence speed and some intuition on why the proposed algorithm can fasten the learning would be great.

Also, the algorithm needs to fit better into the literature. ETD, introduced by Mahmood and colleagues (2015), is another stable off-policy algorithm. Also, a target network is suggested to help convergence (Zhang et al., 2021; Fellows et al., 2023; Che et al., 2024). Che et al. (2024) compare their TD algorithm with GTD on Baird’s counterexample, showing much faster convergence.

Reference

Mahmood, A. R., Yu, H., White, M., & Sutton, R. S. (2015). Emphatic temporal-difference learning. arXiv preprint arXiv:1507.01569.

Zhang, S., Yao, H., & Whiteson, S. (2021, July). Breaking the deadly triad with a target network. In International Conference on Machine Learning (pp. 12621-12631). PMLR.

Fellows, M., Smith, M. J., & Whiteson, S. (2023, July). Why target networks stabilise temporal difference methods. In International Conference on Machine Learning (pp. 9886-9909). PMLR.

Che, F., Xiao, C., Mei, J., Dai, B., Gummadi, R., Ramirez, O. A., ... & Schuurmans, D. (2024). Target Networks and Over-parameterization Stabilize Off-policy Bootstrapping with Function Approximation. arXiv preprint arXiv:2405.21043.

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 2
questions: Here are a few questions that might affect the evaluation:
1. Do the choices of $f(t)$ depend on the induced Markov chain’s mixing time? If yes, where is it in the result? If not, why?
2. What is the convergence rate for GTD? Is it the same as the canonical on-policy TD as well?
3. In Line 182, when $f(t)$ was a constant function, what would happen by following the classical convergence results mentioned in Line 186? What’s the consequence of using such a $f(t)$?
4. In Line 227, the paper claims the technique of using a variable interval $T_m$ has not been used in any stochastic approximation and RL literature. Has it been used or studied in other fields? If yes, then it is worth mentioning the relevant literature.
5. In Line 482, the paper claims that the finite sample analysis **confirms** that the proposed algorithm converges reasonably fast, but this analysis is based on a variant of the proposed algorithm with a projection step. Does the efficiency of the variant with the projection step guarantee or generally suggest the efficiency of the base algorithm?
6. Is the proposed algorithm more or less sensitive to the learning rate compared to GTD? Since GTD has two hyperparameters, comparison methods like those in Ghiassian & Sutton, 2021 might be useful here.
soundness: 3
strengths: The strengths of the paper include its originality, quality, and clarity:
1. The idea in this paper is novel to the best of my knowledge. It’s neat to use two samples distanced away from each other to estimate the terms involving two $A$ matrices, which are independent if their gap is large. The sublinear memory requirement also renders this idea a practical approach.
2. The quality of the paper is also a strength. The asymptotic convergence of the proposed algorithm is novel and may bring value to the community.
3. The paper is very well written and easy to follow.
summary: This paper proposes a new variant of the gradient temporal difference (GTD) learning algorithm for online off-policy policy evaluation with linear function approximation. The idea is to use two samples distanced away from each other to address the double sampling issue encountered during the derivation of GTD. The paper shows that when the distance between the two samples $f(t)$ used to estimate the gradient increases with a proper rate (e.g., $f(t)=\ln^2(t+1)$), the new algorithm converges asymptotically, while its variant with a projection operator has a convergent rate comparable to on-policy TD. The consequence of this new GTD variant is that 1) it reduces the need for an additional set of weights and step size, and 2) it requires an additional memory of size $O(\ln^2(t))$. Preliminary experiment results on Baird’s counterexample show the effectiveness of the proposed algorithm.
weaknesses: The paper has weaknesses in its significance and relevant work discussion:
1. The paper may be limited in its significance. 
  - On the theory side, the finite time analysis is based on a variant of the proposed algorithm with a projection step, which is absent in the actual algorithm. Thus, the comparison between its convergence rate in this case with that of on-policy TD may not be very valuable. Note that finite sample analysis of the actual algorithm is possible, as also pointed out in the paper. Obtaining such a result can strengthen the paper.
  - On the empirical side, the experiments presented in this paper only focus on Baird’s counterexample and are rather limited. Having more experiments, even in simple environments like FourRoom (Ghiassian & Sutton, 2021; Ghiassian et al., 2024), would help strengthen the claim that the proposed algorithm is effective. In addition to testing the proposed algorithm in environments like FourRoom, a comparison with other GTD algorithms can also make the paper stronger. Other researchers may find it useful to know how the proposed algorithm compares to others in terms of sample efficiency, stability, and hyperparameter sensitivity.
2. The paper also lacks a thorough related work discussion on off-policy policy evaluation (OPPE) with linear function approximation. There have been many follow-up works on the GTD algorithm (Mahadevan et al., 2014; Ghiassian et al., 2020; Yao, 2023). While some of them are cited in the paper, the relationship between these later ideas building on GTD and the proposed method is not thoroughly discussed, which could be useful and inspire future research. Note that Yao (2023) also introduces a GTD variant with one step-size, so it may be necessary to clarify its distinction with your approach. In addition, the paper may also benefit from discussing another line of work that addresses the deadly triad, the ETD family (Sutton et al., 2016; Hallak et al., 2016, 2017; He et al., 2023). Specifically, how does the proposed approach compare to these methods in terms of the optimality of the fixed point and the convergence property? Having a more thorough discussion of these relevant works would strengthen the paper’s positioning.

Ghiassian, S., Patterson, A., Garg, S., Gupta, D., White, A., & White, M. (2020). Gradient temporal-difference learning with regularized corrections. ICML.

Ghiassian, S., & Sutton, R. S. (2021). An empirical comparison of off-policy prediction learning algorithms in the four rooms environment. arXiv preprint arXiv:2109.05110.

Ghiassian, S., Rafiee, B., & Sutton, R. S. (2024). Off-Policy Prediction Learning: An Empirical Study of Online Algorithms. IEEE Transactions on Neural Networks and Learning Systems.

Hallak, A., Tamar, A., Munos, R., & Mannor, S. (2016). Generalized emphatic temporal difference learning: Bias-variance analysis. AAAI.

Hallak, A., & Mannor, S. (2017). Consistent on-line off-policy evaluation. ICML.

He, J., Che, F., Wan, Y., & Mahmood, A. R. (2023). Loosely consistent emphatic temporal-difference learning. UAI.

Mahadevan, S., Liu, B., Thomas, P., Dabney, W., Giguere, S., Jacek, N., ... & Liu, J. (2014). Proximal reinforcement learning: A new theory of sequential decision making in primal-dual spaces. arXiv preprint arXiv:1405.6757.

Sutton, R. S., Mahmood, A. R., & White, M. (2016). An emphatic approach to the problem of off-policy temporal-difference learning. JMLR.

Yao, H. (2023). A new Gradient TD Algorithm with only One Step-size: Convergence Rate Analysis using $ L $-$\lambda $ Smoothness. arXiv preprint arXiv:2307.15892.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: Please see my comments in Weaknesses section.
soundness: 3
strengths: The paper expand the idea from $A^TTD$ and proposed a new method to solve double sampling issue in off-policy learning. Compared with $A^TTD$, this methods required less memory. The authors also provided the convergence analysis of their method.
summary: This paper proposed a new solution to solve double sampling issue in off-policy reinforcement learning. Specifically, this paper provided another method to estimate $A^T A$ and $A^T b$ by introducing a function $f(t)$. The authors also provided finite-time analysis for their method as well as some numerical results.
weaknesses: This paper is really interesting to me. However, I have several questions. 

1. The advantage of selecting $f(t)$ as an increasing function over a constant one is not immediately clear. The authors state in lines 186–187 that classical convergence analysis can be applied to establish the convergence rate. Thus, it seems that a constant $f(t)$ could also ensure convergence. Additionally, the experimental results suggest that setting $f(t)=2$ is sufficient to resolve Baird’s counterexample, which further supports the idea of choosing $f(t)$ as a constant.

2. Relying on samples from several steps prior may introduce additional errors during policy improvement. Although this paper focuses exclusively on policy evaluation, it is important to mark that policy evaluation serves the purpose of policy improvement. In cases where the policy is continuously updated, the samples used to estimate $A^T$ may become inaccurate, introducing further errors.

3. A minor issue appears in lines 206–207, where I believe the correct notation should be $\bar{h}(\omega_{t_m})$ instead of $h(\omega_{t_m})$

Meta-review: In this paper, the authors derive a convergent algorithm for off-policy TD learning with linear function approximation. The idea is to use two samples away from each other to address the double sampling issue of GTD. The resulting algorithm directly minimizes the L2-norm of expected TD updates (NEU), thus improves the memory requirement of estimating the term with matrices and reduces the number of learning rates from two to one compared to GTD. The authors prove the asymptotic convergence of their algorithm, and test it on Baird’s counterexample and show that it does not diverge.

The reviewers found the work original, high quality, and easy to read. They found the idea of using two samples distanced away from each other to estimate the term with two matrices novel. They also found memory requirement and smaller number of tunable hyper-parameter (learning rate) desirable in practice. 

The reviewers raised some issues, some addressed by the authors during the rebuttals, and some remained that would be good if they are addressed in the final version of the paper. 
(-) The paper can benefit from a more thorough discussion of the related work (off-policy policy evaluation with linear function approximation).
(-) Comparing the proposed algorithm with GTD2, TDRC, and target network based approaches.

Decision: Accept (Poster)