###  D.1 Key quantities related to learning rates

We find it convenient to define the following quantities (by abuse of
notation)

$\displaystyle\eta_{k}^{(t)}$
$\displaystyle\coloneqq\eta_{k}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\qquad\text{for any }1\leq k<t,$ (118a) $\displaystyle\eta_{0}^{(t)}$
$\displaystyle\coloneqq\prod_{i=1}^{t}\big{(}1-\eta_{i}(1-\gamma p)\big{)},$
(118b) $\displaystyle\eta_{t}^{(t)}$ $\displaystyle\coloneqq\eta_{t}.$ (118c)

It is helpful to establish several basic properties about these quantities. As
can be easily verified,

$\displaystyle\eta_{0}^{(t)}+(1-\gamma
p)\sum_{k=1}^{t}\eta_{k}^{(t)}=\prod_{i=1}^{t}(1-\widehat{\eta}_{i})+\widehat{\eta}_{1}\prod_{i=2}^{t}(1-\widehat{\eta}_{i})+\widehat{\eta}_{2}\prod_{i=3}^{t}(1-\widehat{\eta}_{i})+\cdots+\widehat{\eta}_{t-1}(1-\widehat{\eta}_{t})+\widehat{\eta}_{t}=1,$
(119)

where we denote $\widehat{\eta}_{i}\coloneqq\eta_{i}(1-\gamma p)$ to simplify
notation. Similarly, for any given integer $0\leq\tau<t$ one has

$\displaystyle\prod_{i=\tau+1}^{t}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}+(1-\gamma p)\sum_{k=\tau+1}^{t}\eta_{k}^{(t)}=1.$ (120)

###  D.2 Preliminary calculations

Before moving forward, we record several basic relations as a result of the
Q-learning update rule.

####  D.2.1 Basic update rules and expansion

Given that $Q_{0}=V_{0}=0$ and that state 0 is absorbing, the update rule (4)
gives

$\displaystyle
V_{t}(0)=Q_{t}(0,1)=\big{(}1-\eta_{t}(1-\gamma)\big{)}Q_{t-1}(0,1)=\prod_{i=1}^{t}\big{(}1-\eta_{i}(1-\gamma)\big{)}Q_{0}(0,1)=0$
(121)

for all $t\geq 1$. Regarding state 2, the update rule (4) taken together with
(121) leads to

$\displaystyle V_{t}(2)=Q_{t}(2,1)$
$\displaystyle=\big{(}1-\eta_{t}\big{)}Q_{t-1}(2,1)+\eta_{t}\big{\\{}r(2,1)+\gamma
P_{t}(2\,|\,2)V_{t-1}(2)+\gamma P_{t}(0\,|\,2)V_{t-1}(0)\big{\\}}$
$\displaystyle=\big{(}1-\eta_{t}\big{)}V_{t-1}(2)+\eta_{t}\big{\\{}1+\gamma
P_{t}(2\,|\,2)V_{t-1}(2)\big{\\}},$ (122)

and for state 3,

$\displaystyle V_{t}(3)=Q_{t}(3,1)$
$\displaystyle=\big{(}1-\eta_{t}\big{)}Q_{t-1}(3,1)+\eta_{t}\big{\\{}r(3,1)+\gamma
V_{t-1}(3)\big{\\}}$
$\displaystyle=\big{(}1-\eta_{t}(1-\gamma)\big{)}V_{t-1}(3)+\eta_{t}.$ (123)

Similarly, one also has

$\displaystyle Q_{t}(1,1)$
$\displaystyle=(1-\eta_{t})Q_{t-1}(1,1)+\eta_{t}\big{\\{}1+\gamma
P_{t}(1\,|\,1,1)V_{t-1}(1)\big{\\}},$ (124a) $\displaystyle Q_{t}(1,2)$
$\displaystyle=(1-\eta_{t})Q_{t-1}(1,2)+\eta_{t}\big{\\{}1+\gamma
P_{t}(1\,|\,1,2)V_{t-1}(1)\big{\\}}.$ (124b)

In what follows, we shall first determine a crude range for certain quantities
relates to the learning rates $\eta_{t}$, and then combine this with the above
relations to establish the desired result.

Next, we record some elementary decomposition of $V_{t}(2)$. For any iteration
$t$ and $\tau<t$, one can continue the derivation in (122) to obtain

$\displaystyle V_{t}(2)$ $\displaystyle=\big{(}1-\eta_{t}(1-\gamma
p)\big{)}V_{t-1}(2)+\eta_{t}\big{\\{}1+\gamma\big{(}P_{t}(2\,|\,2)-p\big{)}V_{t-1}(2)\big{\\}}$
$\displaystyle=\prod_{i=\tau+1}^{t}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}V_{\tau}(2)+\sum_{k=\tau+1}^{t}\eta_{k}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\big{\\{}1+\gamma\big{(}P_{k}(2\,|\,2)-p\big{)}V_{k-1}(2)\big{\\}}$
$\displaystyle=\prod_{i=\tau+1}^{t}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}V_{\tau}(2)+\sum_{k=\tau+1}^{t}\eta_{k}^{(t)}+\sum_{k=\tau+1}^{t}\eta_{k}^{(t)}\gamma\big{(}P_{k}(2\,|\,2)-p\big{)}V_{k-1}(2)$
$\displaystyle=\prod_{i=\tau+1}^{t}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}V_{\tau}(2)+\frac{1-\prod_{i=\tau+1}^{t}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}}{1-\gamma
p}+\sum_{k=\tau+1}^{t}\eta_{k}^{(t)}\gamma\big{(}P_{k}(2\,|\,2)-p\big{)}V_{k-1}(2)$
$\displaystyle=\frac{1}{1-\gamma
p}-\prod_{i=\tau+1}^{t}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\left[\frac{1}{1-\gamma
p}-V_{\tau}(2)\right]+\sum_{k=\tau+1}^{t}\eta_{k}^{(t)}\gamma\big{(}P_{k}(2\,|\,2)-p\big{)}V_{k-1}(2),$
(125)

where the penultimate line arises from (120). In particular, in the special
case where $\tau=0$ (so that $V_{\tau}(2)=V_{0}(2)=0$), this simplifies to

$\displaystyle V_{t}(2)=\frac{1-\eta_{0}^{(t)}}{1-\gamma
p}+\sum_{k=1}^{t}\eta_{k}^{(t)}\gamma\big{(}P_{k}(2\,|\,2)-p\big{)}V_{k-1}(2),$
(126)

which relies on the definition of $\eta_{0}^{(t)}$ in (118). With similar
derivation, (123) leads to

$\displaystyle
V_{t}(3)=\frac{1}{1-\gamma}\Big{[}1-\prod_{i=1}^{T}\big{(}1-\eta_{i}(1-\gamma)\big{)}\Big{]}=V^{\star}(3)-\frac{1}{1-\gamma}\prod_{i=1}^{T}\big{(}1-\eta_{i}(1-\gamma)\big{)}.$
(127)

####  D.2.2 Mean and variance of $V^{\star}(2)-V_{T}(2)$

We start by computing the mean $V^{\star}(2)-\mathbb{E}[V_{t}(2)]$. From the
construction (37), it is easily seen that $\mathbb{E}[P_{k}(2\,|\,2)]=p$,
which together with the identity (126) leads to

$\displaystyle\mathbb{E}\big{[}V_{T}(2)\big{]}=\frac{1-\eta_{0}^{(T)}}{1-\gamma
p}\qquad\text{and}\qquad
V^{\star}(2)-\mathbb{E}\big{[}V_{T}(2)\big{]}=\frac{\eta_{0}^{(T)}}{1-\gamma
p}.$ (128)

Similarly, applying the above argument to (125) and rearranging terms, we
immediately arrive at

$\displaystyle
V^{\star}(2)-\mathbb{E}\big{[}V_{T}(2)\big{]}=\prod_{i=\tau+1}^{T}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\left[\frac{1}{1-\gamma
p}-\mathbb{E}\big{[}V_{\tau}(2)\big{]}\right]$ (129)

for any integer $0\leq\tau<T$.

Next, we develop a lower bound on the variance
$\mathsf{Var}\big{(}V_{T}(2)\big{)}$. Towards this end, consider first a
martingale sequence $\\{Z_{k}\\}_{0\leq k\leq T}$ adapted to a filtration
$\mathcal{F}_{0}\subseteq\mathcal{F}_{1}\subseteq\cdots\subseteq\mathcal{F}_{T}$,
namely, $\mathbb{E}[Z_{k+1}\,|\,\mathcal{F}_{k}]=0$ and
$\mathbb{E}[Z_{k}\,|\,\mathcal{F}_{k}]=Z_{k}$ for all $0\leq k\leq T$. In
addition, consider any $0\leq\tau<T$, and let $W_{0}$ be a random variable
such that $\mathbb{E}[W_{0}\,|\,\mathcal{F}_{\tau}]=W_{0}$. Then the law of
total variance together with basic martingale properties tells us that

$\displaystyle\mathsf{Var}\left(W_{0}+\sum_{k=\tau+1}^{T}Z_{k}\right)$
$\displaystyle=\mathbb{E}\left[\mathsf{Var}\left(W_{0}+\sum_{k=\tau+1}^{T}Z_{k}\mid\mathcal{F}_{T-1}\right)\right]+\mathsf{Var}\left(\mathbb{E}\left[W_{0}+\sum_{k=\tau+1}^{T}Z_{k}\mid\mathcal{F}_{T-1}\right]\right)$
$\displaystyle=\mathbb{E}\big{[}\,\mathsf{Var}\left(Z_{T}\mid\mathcal{F}_{T-1}\right)\big{]}+\mathsf{Var}\left(W_{0}+\sum_{k=\tau+1}^{T-1}Z_{k}\right)=\cdots$
$\displaystyle=\sum_{k=\tau+1}^{T}\mathbb{E}\big{[}\,\mathsf{Var}\left(Z_{k}\mid\mathcal{F}_{k-1}\right)\big{]}+\mathsf{Var}\left(W_{0}\right)\geq\sum_{k=\tau+1}^{T}\mathbb{E}\big{[}\,\mathsf{Var}\left(Z_{k}\mid\mathcal{F}_{k-1}\right)\big{]}.$
(130)

Consequently, for any $0\leq\tau<T-1$, it follows from the decomposition (125)
(with $\tau$ replaced by $\tau+1$) that

$\displaystyle\mathsf{Var}\big{(}V_{T}(2)\big{)}$
$\displaystyle\geq\mathbb{E}\left[\sum_{k=\tau+2}^{T}\mathsf{Var}\Big{(}\eta_{k}^{(T)}\gamma\big{(}P_{k}(2\,|\,2)-p\big{)}V_{k-1}(2)\,|\,V_{k-1}(2)\Big{)}\right]$
$\displaystyle=\sum_{k=\tau+2}^{T}\big{(}\eta_{k}^{(T)}\gamma\big{)}^{2}p(1-p)\mathbb{E}\big{[}\big{(}V_{k-1}(2)\big{)}^{2}\big{]}$
$\displaystyle\geq\frac{\left(1-\gamma\right)\left(4\gamma-1\right)}{9}\cdot\frac{1}{4(1-\gamma)^{2}}\sum_{k=\tau+2}^{T}\big{(}\eta_{k}^{(T)}\big{)}^{2}$
$\displaystyle=\frac{4\gamma-1}{36\left(1-\gamma\right)}\sum_{k=\tau+2}^{T}\big{(}\eta_{k}^{(T)}\big{)}^{2},$
(131)

where the first identity relies on the fact that $P_{k}(2\,|\,2)$ is a
Bernoulli random variable with mean $p$, and the inequality comes from the
definition of $\tau$ (see (137)) and the choice of $p$ (see (38)). As an
implication, the sum of squares of $\eta_{k}^{(T)}$ plays a crucial role in
determining the variance of $V_{T}(2)$.

###  D.3 Lower bounds for three cases

####  D.3.1 Case 1: small learning rates ($c_{\eta}\geq\log T$ or
$0\leq\eta\leq\frac{1}{(1-\gamma)T}$)

In this case, we focus on lower bounding
$V^{\star}(2)-\mathbb{E}\big{[}V_{T}(2)\big{]}$. In view of this identity
(128), this boils down to controlling $\eta_{0}^{(T)}$.

Suppose that $c_{\eta}>\log T$ (for rescaled linear learning rates) or
$0\leq\eta<\frac{1}{(1-\gamma)T}$ (for constant learning rates). A little
algebra then gives

$\displaystyle\eta_{t}(1-\gamma p)$
$\displaystyle\leq\begin{cases}\frac{1-\gamma p}{(1-\gamma)t\log
T}=\frac{4}{3t\log T}\leq\frac{1}{2},\qquad&\text{if
}\eta_{t}=\frac{1}{1+c_{\eta}(1-\gamma)t}\\\ \frac{1-\gamma
p}{(1-\gamma)T}=\frac{4}{3T}\leq\frac{1}{2},&\text{if
}\eta_{t}=\eta\end{cases}$ (132)

for any $t\geq 1$, provided that $T\geq 15$. Consequently, one can derive

$\displaystyle\log\eta_{0}^{(T)}=\sum_{i=1}^{T}\log\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\geq-1.5\sum_{i=1}^{T}\eta_{i}(1-\gamma p)\geq-2,$ (133)

where the first inequality holds due to the elementary fact
$\log(1-x)\geq-1.5x$ for all $0\leq x\leq 0.5$, and the last inequality
follows from the following bound (which makes use of (132))

$\sum_{i=1}^{T}\eta_{i}(1-\gamma p)\leq\begin{cases}\frac{3}{4\log
T}\sum_{i=1}^{T}\frac{1}{i}\leq 1,&\text{if
}\eta_{t}=\frac{1}{1+c_{\eta}(1-\gamma)t}\\\
\frac{4}{3T}\sum_{i=1}^{T}1=\frac{4}{3},&\text{if }\eta_{t}=\eta.\end{cases}$

Combining the above result with the properties (128) and (133) then yields

$V^{\star}(2)-\mathbb{E}\big{[}V_{T}(2)\big{]}=\frac{\eta_{0}^{(T)}}{1-\gamma
p}\geq\frac{e^{-2}}{1-\gamma p}=\frac{3}{4e^{2}(1-\gamma)}.$ (134)

This taken together with (40) gives

$\mathbb{E}\big{[}\big{(}V^{\star}(2)-V_{T}(2)\big{)}^{2}\big{]}\geq\big{(}V^{\star}(2)-\mathbb{E}\big{[}V_{T}(2)\big{]}\big{)}^{2}\geq\frac{9}{16e^{4}(1-\gamma)^{2}}.$
(135)

####  D.3.2 Case 2: large learning rates ($c_{\eta}\leq 1-\gamma$ or
$\eta\geq\frac{1}{(1-\gamma)^{2}T}$)

By virtue of (129), the mean gap
$V^{\star}(2)-\mathbb{E}\big{[}V_{T}(2)\big{]}$ depends on two factors: (i)
the choice of the learning rates, and (ii) the gap between $\frac{1}{1-\gamma
p}$ and $\mathbb{E}\big{[}V_{\tau}(2)\big{]}$, where $\tau$ is an integer
obeying $0\leq\tau<T$. To control the factor (ii), we need to choose $\tau$
properly. Let us start by considering the simple scenario with
$\mathbb{E}\big{[}\big{(}V_{T}(2)\big{)}^{2}\big{]}<\frac{1}{4(1-\gamma)^{2}}$,
for which we have

$\displaystyle
V^{\star}(2)-\mathbb{E}\big{[}V_{T}(2)\big{]}\geq\frac{3}{4(1-\gamma)}-\sqrt{\mathbb{E}\big{[}\big{(}V_{T}(2)\big{)}^{2}\big{]}}\geq\frac{1}{4(1-\gamma)}.$
(136)

Here, we have used (39) and the elementary fact
$\mathbb{E}[X]\leq\sqrt{\mathbb{E}[X^{2}]}$. Consequently, it remains to look
at the scenario obeying
$\mathbb{E}\big{[}\big{(}V_{T}(2)\big{)}^{2}\big{]}\geq\frac{1}{4(1-\gamma)^{2}}$,
towards which we propose to set $\tau$ as follows

$\displaystyle\tau\coloneqq\min\left\\{0\leq\tau^{\prime}\leq
T-1\,\,\Big{|}\,\,\mathbb{E}\big{[}\big{(}V_{t}(2)\big{)}^{2}\big{]}\geq\frac{1}{4(1-\gamma)^{2}}\leavevmode\nobreak\
\text{for all }\tau^{\prime}+1\leq t\leq T\right\\}.$ (137)

Clearly, $\tau$ is well-defined in this scenario and obeys (in view of both
(137) and the initialization $V_{0}=0$)

$\displaystyle\mathbb{E}\big{[}\big{(}V_{\tau}(2)\big{)}^{2}\big{]}<\frac{1}{4(1-\gamma)^{2}}.$
(138)

Our analysis for this scenario is divided into three subcases based on the
size of the learning rates.

##### Case 2.1.

Consider the case where

$\displaystyle\prod_{i=\tau+1}^{T}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\geq\frac{1}{2}.$ (139)

Invoke (129) to deduce that

$\displaystyle V^{\star}(2)-\mathbb{E}\big{[}V_{T}(2)\big{]}$
$\displaystyle=\prod_{i=\tau+1}^{T}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\Big{[}\frac{1}{1-\gamma
p}-\mathbb{E}\big{[}V_{\tau}(2)\big{]}\Big{]}$
$\displaystyle\geq\prod_{i=\tau+1}^{T}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\Big{[}\frac{3}{4(1-\gamma)}-\sqrt{\mathbb{E}\big{[}\big{(}V_{\tau}(2)\big{)}^{2}\big{]}}\Big{]}$
$\displaystyle\geq\prod_{i=\tau+1}^{T}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\frac{1}{4(1-\gamma)}\geq\frac{1}{8(1-\gamma)},$

where the second line makes use of the definition (38) and the elementary fact
$\mathbb{E}[X]\leq\sqrt{\mathbb{E}[X^{2}]}$, and the last line relies on the
inequalities (138) and (139).

##### Case 2.2.

We now move on to the case where

$\displaystyle 0\leq\prod_{i=\tau+1}^{T}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\leq\frac{1}{2}.$ (140)

We intend to demonstrate that the variance of $V_{T}(2)$ — and hence the
typical size of its fluctuation — is too large. In view of the observation
(131), it boils down to lower bounding
$\sum_{k=\tau+2}^{T}\big{(}\eta_{k}^{(T)}\big{)}^{2}$, which we accomplish as
follows.

  * •

Consider constant learning rates $\eta_{k}=\eta$, and suppose that $\eta$
obeys $\frac{1}{(1-\gamma)^{2}T}<\eta\leq 1<\frac{1}{1-\gamma p}$. It is
readily seen that $\eta_{k}^{(T)}=\eta\big{(}1-\eta(1-\gamma p)\big{)}^{T-k}$
for any $k\geq 1$. We claim that it suffices to focus on the scenario where

$\displaystyle\tau\leq T-2.$ (141)

In fact, if $\tau\geq T-1$, then the definition (137) of $\tau$ necessarily
requires that

$\mathbb{E}\big{[}V_{T-1}(2)\big{]}\leq\sqrt{\mathbb{E}\big{[}\big{(}V_{T-1}(2)\big{)}^{2}\big{]}}<\frac{1}{2(1-\gamma)}.$

In view of (128) (with $T$ replaced by $T-1$), a little algebra shows that
this is equivalent to $\big{(}1-\eta(1-\gamma p)\big{)}^{T-1}\geq 1/3$, and
hence $\big{(}1-\eta(1-\gamma p)\big{)}^{T}\geq 1/9$. In turn, this combined
with (128) leads to

$\displaystyle
V^{\star}(2)-\mathbb{E}\big{[}V_{T}(2)\big{]}=\frac{\big{(}1-\eta(1-\gamma
p)\big{)}^{T}}{1-\gamma p}=\frac{3\big{(}1-\eta(1-\gamma
p)\big{)}^{T}}{4(1-\gamma)}\geq\frac{1}{12(1-\gamma)},$ (142)

which already suffices for our purpose.

Next, assuming that (141) holds, one can derive

$\displaystyle\sum_{k=\tau+2}^{T}\big{(}\eta_{k}^{(T)}\big{)}^{2}$
$\displaystyle=\sum_{k=\tau+2}^{T}\eta^{2}\big{(}1-\eta(1-\gamma
p)\big{)}^{2(T-k)}=\frac{\eta^{2}\big{[}1-\big{(}1-\eta(1-\gamma
p)\big{)}^{2(T-\tau-1)}\big{]}}{1-\big{(}1-\eta(1-\gamma p)\big{)}^{2}}$
$\displaystyle\geq\frac{\eta^{2}/2}{1-\big{(}1-\eta(1-\gamma
p)\big{)}^{2}}\geq\frac{3\eta}{16(1-\gamma)},$ (143)

where the first inequality holds since (from the assumptions (140) and
$\tau\leq T-2$)

$0\leq\big{(}1-\eta(1-\gamma p)\big{)}^{2(T-\tau-1)}\leq\big{(}1-\eta(1-\gamma
p)\big{)}^{T-\tau}=\prod_{i=\tau+1}^{T}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\leq\frac{1}{2},$

and the last inequality follows since

$0\leq 1-\big{(}1-\eta(1-\gamma
p)\big{)}^{2}=1-\Big{(}1-\frac{4\eta(1-\gamma)}{3}\Big{)}^{2}\leq\frac{8\eta(1-\gamma)}{3}.$

Substituting (143) into (131), we obtain

$\displaystyle\mathsf{Var}\big{(}V_{T}(2)\big{)}$
$\displaystyle\geq\frac{4\gamma-1}{36(1-\gamma)}\sum_{k=\tau+1}^{T}\big{(}\eta_{k}^{(T)}\big{)}^{2}\geq\frac{2}{36(1-\gamma)}\cdot\frac{3\eta}{16(1-\gamma)}$
$\displaystyle=\frac{\eta}{96(1-\gamma)^{2}}\geq\frac{1}{96(1-\gamma)^{4}T},$
(144)

provided that $\gamma\geq 3/4$ (so that $4\gamma-1\geq 2$). Here, the last
inequality is valid since either $\eta\geq\frac{1}{(1-\gamma)^{2}T}$.

  * •

We then move on to linearly rescaled learning rates with
$\eta_{t}=\frac{1}{1+c_{\eta}(1-\gamma)t}$ for some $0\leq c_{\eta}<1-\gamma$.
Towards this, we first make the observation that

$\displaystyle\frac{\eta_{k-1}^{(T)}}{\eta_{k}^{(T)}}$
$\displaystyle=\frac{\eta_{k-1}\big{(}1-\eta_{k}(1-\gamma
p)\big{)}}{\eta_{k}}=\frac{1-\frac{4}{3}(1-\gamma)\eta_{k}}{1-\big{(}\frac{1}{\eta_{k}}-\frac{1}{\eta_{k-1}}\big{)}\eta_{k}}=\frac{1-\frac{4}{3}(1-\gamma)\eta_{k}}{1-c_{\eta}(1-\gamma)\eta_{k}}=1-\frac{\big{(}\frac{4}{3}-c_{\eta}\big{)}(1-\gamma)\eta_{k}}{1-c_{\eta}(1-\gamma)\eta_{k}}$
$\displaystyle\leq 1-(1-\gamma)\eta_{k}\leq 1-(1-\gamma)\eta_{T},$ (145)

with the proviso that $c_{\eta}<1-\gamma\leq 1/3$ (as long as $\gamma\geq
2/3$). By defining $\tau^{\prime}\coloneqq T-\frac{1}{(1-\gamma)\eta_{T}}$,
one can deduce that

$\displaystyle\sum_{k=\tau+2}^{T}\big{(}\eta_{k}^{(T)}\big{)}^{2}$
$\displaystyle\geq\sum_{k=\max\\{\tau+2,\tau^{\prime}+1\\}}^{T}\big{(}\eta_{k}^{(T)}\big{)}^{2}\geq\frac{1}{T-\max\\{\tau+1,\tau^{\prime}\\}}\left[\sum_{k=\max\\{\tau+2,\tau^{\prime}+1\\}}^{T}\eta_{k}^{(T)}\right]^{2}$
$\displaystyle\geq(1-\gamma)\eta_{T}\left[\sum_{k=\max\\{\tau+2,\tau^{\prime}+1\\}}^{T}\eta_{k}^{(T)}\right]^{2},$
(146)

where the penultimate inequality comes from the Cauchy-Schwarz inequality. In
addition, recognizing that
$\eta_{k_{1}}^{(T)}\leq\big{(}1-(1-\gamma)\eta_{T}\big{)}^{k_{2}-k_{1}}\eta_{k_{2}}^{(T)}$
for any $k_{2}\geq k_{1}$ (see (145)), one has

$\displaystyle\sum_{k=\tau^{\prime}+1}^{T}\eta_{k}^{(T)}$
$\displaystyle=\sum_{k=\tau^{\prime}+1}^{T}\eta_{k}^{(T)},$
$\displaystyle\sum_{k=\max\\{2\tau^{\prime}-T+1,1\\}}^{\tau^{\prime}}\eta_{k}^{(T)}$
$\displaystyle\leq\big{(}1-(1-\gamma)\eta_{T}\big{)}^{T-\tau^{\prime}}\sum_{k=\tau^{\prime}+1}^{T}\eta_{k}^{(T)},$
$\displaystyle\sum_{k=\max\\{3\tau^{\prime}-2T+1,1\\}}^{2\tau^{\prime}-T}\eta_{k}^{(T)}$
$\displaystyle\leq\big{(}1-(1-\gamma)\eta_{T}\big{)}^{2(T-\tau^{\prime})}\sum_{k=\tau^{\prime}+1}^{T}\eta_{k}^{(T)},$
$\displaystyle\cdots$

Summing these inequalities up and rearranging terms, we reach

$\displaystyle\sum_{k=\tau^{\prime}+1}^{T}\eta_{k}^{(T)}$
$\displaystyle\geq\frac{\sum_{k=1}^{T}\eta_{k}^{(T)}}{1+\big{(}1-(1-\gamma)\eta_{T}\big{)}^{T-\tau^{\prime}}+\big{(}1-(1-\gamma)\eta_{T}\big{)}^{2(T-\tau^{\prime})}+\ldots}\geq\frac{\sum_{k=1}^{T}\eta_{k}^{(T)}}{\frac{1}{1-\big{(}1-(1-\gamma)\eta_{T}\big{)}^{T-\tau^{\prime}}}}$
$\displaystyle=\left(1-\big{(}1-(1-\gamma)\eta_{T}\big{)}^{T-\tau^{\prime}}\right)\sum_{k=1}^{T}\eta_{k}^{(T)}\geq(1-e^{-1})\sum_{k=1}^{T}\eta_{k}^{(T)},$

which relies on the fact
$\big{(}1-(1-\gamma)\eta_{T}\big{)}^{T-\tau^{\prime}}=\big{(}1-1/(T-\tau^{\prime})\big{)}^{T-\tau^{\prime}}\leq
e^{-1}$ (using the definition of $\tau^{\prime}$). Consequently, it is easily
seen that

$\displaystyle\sum_{k=\max\\{\tau+2,\tau^{\prime}+1\\}}^{T}\eta_{k}^{(T)}$
$\displaystyle=\min\left\\{\sum_{k=\tau+2}^{T}\eta_{k}^{(T)},\sum_{k=\tau^{\prime}+1}^{T}\eta_{k}^{(T)}\right\\}\geq(1-e^{-1})\sum_{k=\tau+2}^{T}\eta_{k}^{(T)}$
$\displaystyle\overset{\text{(i)}}{=}(1-e^{-1})\left[1-\prod_{i=\tau+2}^{t}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\right]\frac{1}{1-\gamma p}$
$\displaystyle\overset{\text{(ii)}}{\geq}\left[1-\frac{1}{2\big{(}1-\eta_{\tau+1}(1-\gamma
p)\big{)}}\right]\frac{1-e^{-1}}{1-\gamma
p}\overset{\text{(iii)}}{\geq}\frac{1-e^{-1}}{4(1-\gamma
p)}\geq\frac{3}{32(1-\gamma)}.$

Here, (i) and (ii) follow from (120) and (140), respectively, while (iii)
holds since

$\eta_{\tau+1}(1-\gamma p)\leq 1-\gamma
p=\frac{4(1-\gamma)}{3}\leq\frac{1}{3}$

as long as $\gamma\geq 3/4$. Substitution into (146) yields

$\displaystyle\sum_{k=\tau+2}^{T}\big{(}\eta_{k}^{(T)}\big{)}^{2}$
$\displaystyle\geq\frac{9\eta_{T}}{1024(1-\gamma)}.$ (147)

Substituting the above bound into (131), we obtain

$\displaystyle\mathsf{Var}\big{(}V_{T}(2)\big{)}$
$\displaystyle\geq\frac{4\gamma-1}{36(1-\gamma)}\sum_{k=\tau+1}^{T}\big{(}\eta_{k}^{(T)}\big{)}^{2}\geq\frac{2}{36(1-\gamma)}\cdot\frac{9\eta_{T}}{1024(1-\gamma)}$
$\displaystyle=\frac{\eta_{T}}{2048(1-\gamma)^{2}}\geq\frac{1}{4096(1-\gamma)^{4}T},$
(148)

provided that $\gamma\geq 3/4$ (so that $4\gamma-1\geq 2$). Here, the last
inequality is valid since
$\eta_{T}=\frac{1}{1+c_{\eta}(1-\gamma)T}\geq\frac{1}{1+(1-\gamma)^{2}T}\geq\frac{1}{2(1-\gamma)^{2}T}$
as long as $T\geq\frac{1}{(1-\gamma)^{2}}$.

##### Putting all this together.

With the above bounds in place, it is readily seen that either the bias is too
large (see (142)) or the variance is too large (see (144) and (148)). These
bounds taken collectively with (40) yield

$\displaystyle\mathbb{E}\big{[}\big{(}V^{\star}(2)-V_{T}(2)\big{)}^{2}\big{]}$
$\displaystyle\geq\big{(}V^{\star}(2)-\mathbb{E}\big{[}V_{T}(2)\big{]}\big{)}^{2}+\mathsf{Var}\big{(}V_{T}(2)\big{)}$
$\displaystyle\geq\min\left\\{\frac{1}{144(1-\gamma)^{2}},\frac{1}{96(1-\gamma)^{4}T},\frac{1}{4096(1-\gamma)^{4}T}\right\\}=\frac{1}{4096(1-\gamma)^{4}T},$
(149)

provided $T\geq\frac{1}{(1-\gamma)^{2}}$.

####  D.3.3 Case 3: medium learning rates ($1-\gamma<c_{\eta}<\log T$ or
$\frac{1}{(1-\gamma)T}\leq\eta\leq\frac{1}{(1-\gamma)^{2}T}$)

Throughout this case, we assume that

$\eta_{0}^{(T)}\leq\frac{1}{75}.$ (150)

In fact, if $\eta_{0}^{(T)}>1/75$, then the scenario becomes much easier to
cope with. To see this, applying the previous result (134) and recalling the
choice (38) of $p$ immediately yield

$\displaystyle
V^{\star}(2)-\mathbb{E}\big{[}V_{T}(2)\big{]}\geq\frac{\eta_{0}^{(T)}}{1-\gamma
p}>\frac{1}{100(1-\gamma)},$ (151)

which together with (40) and the assumption $T\geq\frac{1}{(1-\gamma)^{2}}$
yields

$\displaystyle\mathbb{E}\big{[}\big{(}V^{\star}(2)-V_{T}(2)\big{)}^{2}\big{]}$
$\displaystyle\geq\big{(}V^{\star}(2)-\mathbb{E}\big{[}V_{T}(2)\big{]}\big{)}^{2}\geq\frac{1}{10000(1-\gamma)^{2}}\geq\frac{1}{10000(1-\gamma)^{4}T}.$
(152)

We now turn our attention to the dynamics w.r.t. state $1$ and its associated
value function $V_{t}(1)$ under the condition (150).

##### Two auxiliary sequences.

Towards this, we first eliminate the effect of initialization on $Q_{t}(1,a)$
by introducing the following auxiliary sequence

$\displaystyle\widehat{Q}_{t}(a)=(1-\eta_{t})\widehat{Q}_{t-1}(a)+\eta_{t}\big{\\{}1+\gamma
P_{t}(1\,|\,1,a)\widehat{V}_{t-1}\big{\\}},$ (153)

with

$\displaystyle\widehat{V}_{t-1}\coloneqq\max_{a}\widehat{Q}_{t}(a)\qquad\text{and}\qquad\widehat{Q}_{0}(a)\coloneqq
Q^{\star}(1,a)=\frac{1}{1-\gamma p},$

where we recall the value of $Q^{\star}(1,a)$ from Lemma 3. In other words,
$\\{\widehat{Q}_{t}(a)\\}$ is essentially a Q-learning sequence when
initialized at the ground truth. Despite the difference in initialization, we
claim that the discrepancy between $\widehat{Q}_{t}(a)$ and $Q_{t}(1,a)$ can
be well controlled in the following sense:

$\displaystyle
Q_{t}(1,a)\geq\widehat{Q}_{t}(a)-\frac{1}{1-\gamma}\prod_{i=1}^{t}\big{(}1-\eta_{i}(1-\gamma)\big{)},\qquad
a\in\\{1,2\\},$ (154)

which shall be justified in Section D.3.4. As we shall discuss momentarily,
the gap $\frac{1}{1-\gamma}\prod_{i=1}^{t}\big{(}1-\eta_{i}(1-\gamma)\big{)}$
is sufficiently small for this case.

Further, in order to control $\widehat{Q}_{t}(a)$, we find it convenient to
introduce another auxiliary sequence as follows

$\displaystyle\overline{Q}_{t}=(1-\eta_{t})\overline{Q}_{t-1}+\eta_{t}\big{\\{}1+\gamma
P_{t}(1\,|\,1,1)\overline{Q}_{t-1}\big{\\}}\qquad\text{and}\qquad\overline{Q}_{0}=V^{\star}(1)=\frac{1}{1-\gamma
p},$ (155)

which can be interpreted as a Q-learning sequence when there is only a single
action (so that there is no max operator involved). In view of the basic fact
that $\widehat{V}_{t}=\max_{a}\widehat{Q}_{t}(a)\geq\widehat{Q}_{t}(1)$, we
can easily verify that

$\displaystyle\widehat{Q}_{t}(1)\geq(1-\eta_{t})\widehat{Q}_{t-1}(1)+\eta_{t}\big{\\{}1+\gamma
P_{t}(1\,|\,1,1)\widehat{Q}_{t-1}(1)\big{\\}}\geq\overline{Q}_{t},$ (156)

allowing one to lower bound $\widehat{V}_{t}$ by controlling
$\overline{Q}_{t}$.

##### A useful lower bound on the auxiliary sequence (153).

In what follows, let us establish a useful lower bound on the sequence (153)
introduced above. Then we claim that there exists some $\tau\leq T$ (see (170)
and (172)) such that

$\displaystyle\mathbb{P}\Big{\\{}\widehat{V}_{t}\geq\frac{1}{4(1-\gamma)}\Big{\\}}\geq\frac{1}{2},\qquad\text{for}\leavevmode\nobreak\
t\geq\tau.$ (157)

The auxiliary sequence constructed in (155) plays a crucial role in
establishing this claim.

###### Proof of the claim (157).

We intend to employ the sequence $\overline{Q}_{t}$ (cf. (155)) to help
control $\widehat{V}_{t}$. It is first observed that the sequence
$\overline{Q}_{t}$ admits the following decomposition (akin to the derivation
in (126))

$\displaystyle\overline{Q}_{t}$ $\displaystyle=\big{(}1-\eta_{t}(1-\gamma
p)\big{)}\overline{Q}_{t-1}+\eta_{t}\big{\\{}1+\gamma\big{(}P_{t}(1\,|\,1,1)-p\big{)}\overline{Q}_{t-1}\big{\\}}$
$\displaystyle=\prod_{i=1}^{t}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\overline{Q}_{0}+\sum_{k=1}^{t}\eta_{k}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\big{\\{}1+\gamma\big{(}P_{k}(1\,|\,1,1)-p\big{)}\overline{Q}_{k-1}\big{\\}}$
$\displaystyle=\eta_{0}^{(t)}\frac{1}{1-\gamma
p}+\sum_{k=1}^{t}\eta_{k}^{(t)}+\sum_{k=1}^{t}\eta_{k}^{(t)}\gamma\big{(}P_{k}(1\,|\,1,1)-p\big{)}\overline{Q}_{k-1}$
$\displaystyle=\frac{1}{1-\gamma
p}+\sum_{k=1}^{t}\underset{\eqqcolon\,z_{k}}{\underbrace{\eta_{k}^{(t)}\gamma\big{(}P_{k}(1\,|\,1,1)-p\big{)}\overline{Q}_{k-1}}},$
(158)

where the last line results from (119). In order to lower bound
$\overline{Q}_{t}$, it boils down to controlling $\sum_{k}z_{k}$.

Note that the sequence $\\{z_{k}\\}$ defined above is a martingale satisfying

$\displaystyle\mathbb{E}\big{[}z_{k}\,|\,$ $\displaystyle
P_{k-1}(1\,|\,1,1),\ldots,P_{1}(1\,|\,1,1)\big{]}=0$ and
$\displaystyle\qquad|z_{k}|\leq\max_{1\leq k\leq
t}\eta_{k}^{(t)}\cdot\frac{\gamma p}{1-\gamma},$

where the last inequality follows from the basic property
$0\leq\overline{Q}_{k-1}\leq\frac{1}{1-\gamma}$ (akin to Lemma 4) and the fact
that $\big{|}P_{k}(1\,|\,1,1)-p\big{|}\leq\max\\{p,1-p\\}=p$ since
$p=(4\gamma-1)/(3\gamma)$ and $\gamma\geq 3/4$. We intend to invoke Freedman’s
inequality to control (158). Armed with these properties and the fact that
$P_{k}(1\,|\,1,1)$ is a Bernoulli random variable with mean $p$, we obtain

$\displaystyle\sum_{k=1}^{t}\mathsf{Var}\Big{(}z_{k}\,|\,P_{k-1}(1\,|\,1,1),\ldots,P_{1}(1\,|\,1,1)\Big{)}$
$\displaystyle=\sum_{k=1}^{t}\big{(}\eta_{k}^{(t)}\big{)}^{2}p(1-p)\big{(}\gamma\overline{Q}_{k-1}\big{)}^{2}$
$\displaystyle\leq\max_{1\leq k\leq
t}\eta_{k}^{(t)}\cdot\sum_{k=1}^{t}\eta_{k}^{(t)}\cdot\frac{1}{3(1-\gamma)}\leq\frac{\max_{1\leq
k\leq t}\eta_{k}^{(t)}}{4(1-\gamma)^{2}}.$

Here, the penultimate inequality relies on the fact
$0\leq\overline{Q}_{k-1}\leq\frac{1}{1-\gamma}$ (akin to Lemma 4) and the
choice of $p$ (see definition (38)), whereas the last inequality results from
the following condition (derived through (119))

$\sum_{k=1}^{t}\eta_{k}^{(t)}=\big{(}1-\eta_{0}^{(t)}\big{)}\frac{1}{1-\gamma
p}\leq\frac{1}{1-\gamma p}=\frac{3}{4(1-\gamma)}.$

Applying Freedman’s inequality (see (51)) then yields

$\displaystyle\mathbb{P}\left\\{\bigg{|}\sum_{k=1}^{t}z_{k}\bigg{|}\geq\sqrt{\frac{4\max_{1\leq
k\leq
t}\eta_{k}^{(t)}}{(1-\gamma)^{2}}\log\frac{2}{\delta}}+\frac{4\max_{1\leq
k\leq t}\eta_{k}^{(t)}}{3(1-\gamma)}\log\frac{2}{\delta}\right\\}\leq\delta.$
(159)

As an implication of the preceding result, a key ingredient towards bounding
$\sum_{k=1}^{t}z_{k}$ lies in controlling the quantity $\max_{1\leq k\leq
t}\eta_{k}^{(t)}$. To do so, we claim for the moment that there exists some
$\tau\leq T$ such that

$\displaystyle\max_{1\leq k\leq
t}\eta_{k}^{(t)}\leq\frac{1}{50},\qquad\text{for}\leavevmode\nobreak\
t\geq\tau,$ (160)

whose proof is postponed to Section D.3.4. In light of this claim, setting
$\delta=1/2$ in the expression (159) yields

$\sum_{k=1}^{t}z_{k}\geq-\frac{1}{2(1-\gamma)}$

with probably at least $1/2$. Combining this with the decomposition (158) and
the property (156), we arrive at

$\displaystyle\widehat{V}_{t}\geq\widehat{Q}_{t}(1)\geq\overline{Q}_{t}\geq\frac{1}{1-\gamma
p}-\frac{1}{2(1-\gamma)}=\frac{1}{4(1-\gamma)}$

with probability at least $1/2$, where the last identity relies on the choice
of $p$ (see the definition (38)). This establishes the advertised claim (157).
∎

##### Main proof.

With the property (157) in place, we are positioned to prove our main result.
Towards this, we find it convenient to define

$\displaystyle\Delta_{t}(a)$
$\displaystyle\coloneqq\widehat{Q}_{t}(a)-Q^{\star}(1,a),\qquad a=1,2;$ (161a)
$\displaystyle\Delta_{t,\mathsf{max}}$
$\displaystyle\coloneqq\max_{a}\Delta_{t}(a).$ (161b)

The goal is thus to control $\Delta_{T,\mathsf{max}}$; in fact, we intend to
show that $\Delta_{T,\mathsf{max}}$ is in expectation excessively large,
resulting in an “over-estimation” issue that hinders convergence. Towards
this, it follows from the iterative update rule (153) that

$\displaystyle\Delta_{t}(a)$
$\displaystyle=(1-\eta_{t})\Delta_{t-1}(a)+\eta_{t}\big{(}1+\gamma
P_{t}(1\,|\,1,a)\widehat{V}_{t-1}-Q^{\star}(1,a)\big{)}$
$\displaystyle=(1-\eta_{t})\Delta_{t-1}(a)+\eta_{t}\gamma\big{(}P_{t}(1\,|\,1,a)\widehat{V}_{t-1}-pV^{\star}(1)\big{)}$
$\displaystyle=(1-\eta_{t})\Delta_{t-1}(a)+\eta_{t}\gamma\big{(}p\big{(}\widehat{V}_{t-1}-V^{\star}(1)\big{)}+\big{(}P_{t}(1\,|\,1,a)-p\big{)}\widehat{V}_{t-1}\big{)}$
$\displaystyle=(1-\eta_{t})\Delta_{t-1}(a)+\eta_{t}\gamma\Big{(}p\Delta_{t-1,\mathsf{max}}+\big{(}P_{t}(1\,|\,1,a)-p\big{)}\widehat{V}_{t-1}\Big{)}.$

Here, the second line comes from the Bellman equation $Q^{\star}(1,a)=1+\gamma
pV^{\star}(1)$, whereas the last line holds since
$\widehat{V}_{t-1}-V^{\star}(1)=\max_{a}\big{(}\widehat{Q}_{t-1}(a)-V^{\star}(1)\big{)}=\max_{a}\Delta_{t-1}(a)$
(as a consequence of the relation (39)). Applying the above relation
recursively leads to

$\displaystyle\Delta_{t}(a)=\sum_{k=1}^{t}\eta_{k}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\gamma\Big{(}p\Delta_{k-1,\mathsf{max}}+\big{(}P_{k}(1\,|\,1,a)-p\big{)}\widehat{V}_{k-1}\Big{)},$
(162)

where we have used the initialization $\Delta_{0}(a)=0$. Letting

$\displaystyle\xi_{t}(a)$
$\displaystyle\coloneqq\sum_{k=1}^{t}\eta_{k}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\gamma\big{(}P_{k}(1\,|\,1,a)-p\big{)}\widehat{V}_{k-1},$
(163a) $\displaystyle\xi_{t,\mathsf{max}}$
$\displaystyle\coloneqq\max_{a}\xi_{t}(a),$ (163b)

one can express the above relation as follows

$\displaystyle\Delta_{t,\mathsf{max}}=\sum_{k=1}^{t}\eta_{k}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\gamma
p\Delta_{k-1,\mathsf{max}}+\xi_{t,\mathsf{max}}.$

Next, we claim that $\mathbb{E}[\xi_{t,\mathsf{max}}]$ satisfies the following
property

$\displaystyle\mathbb{E}[\xi_{t,\mathsf{max}}]$
$\displaystyle\geq\frac{c}{\sqrt{(1-\gamma)^{2}T}\log T}\qquad\text{for
all}\leavevmode\nobreak\ t\geq\widehat{\tau}$ (164)

for some universal constant $c>0$, where

$\displaystyle\widehat{\tau}\coloneqq\max\Bigg{\\{}\tau^{\prime}\,\,\Big{|}\,\,\prod_{i=\tau^{\prime}}^{T}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\leq\frac{6}{7}\Bigg{\\}},$ (165)

whose existence is ensured under the condition (150). Given the validity of
this claim (which we shall justify in Section D.3.4), we immediately arrive at

$\displaystyle\mathbb{E}[\Delta_{t,\mathsf{max}}]$
$\displaystyle\geq\sum_{k=1}^{t}\eta_{k}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\gamma
p\mathbb{E}[\Delta_{k-1,\mathsf{max}}]+\frac{c}{\sqrt{(1-\gamma)^{2}T}\log
T}\qquad\text{for all}\leavevmode\nobreak\ t\geq\widehat{\tau}.$ (166)

In order to study the above recursion, it is helpful to look at the following
sequence

$\displaystyle x_{t}=(1-\eta_{t})x_{t-1}+\eta_{t}\bigg{(}\gamma
px_{t-1}+\frac{c}{\sqrt{(1-\gamma)^{2}T}\log T}\bigg{)}$ (167)

with $x_{\widehat{\tau}}=0$, where we recall the definition of
$\widehat{\tau}$ in (165). In comparison to the iterative relation (166) which
starts from $\mathbb{E}[\Delta_{0,\mathsf{max}}]=0$ (and hence
$\mathbb{E}[\Delta_{t,\mathsf{max}}]\geq 0$), we let the sequence $x_{t}$
start from $x_{\widehat{\tau}}=0$, where $\widehat{\tau}$ is defined in (165).
It is straightforward to verify that

$\mathbb{E}\big{[}\Delta_{T,\mathsf{max}}\big{]}\geq x_{T},$ (168)

recognizing that

$\displaystyle
x_{t}=\sum_{k=\widehat{\tau}}^{t}\eta_{k}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\gamma
px_{k-1}+\sum_{k=\widehat{\tau}}^{T}\eta_{k}\prod_{i=k+1}^{T}\big{(}1-\eta_{i})\frac{c}{\sqrt{(1-\gamma)^{2}T}\log
T}.$

A little algebra reveals that the sequence (167) obeys

$\displaystyle x_{T}$ $\displaystyle=\frac{c}{\sqrt{(1-\gamma)^{2}T}\log
T}\sum_{k=\widehat{\tau}}^{T}\eta_{k}\prod_{i=k+1}^{T}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}=\frac{c}{\sqrt{(1-\gamma)^{2}T}\log T}\frac{1}{1-\gamma
p}\left[1-\prod_{i=\widehat{\tau}}^{T}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\right]$ $\displaystyle=\frac{3c}{4\sqrt{(1-\gamma)^{4}T}\log
T}\left[1-\prod_{i=\widehat{\tau}}^{T}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\right]\geq\frac{3c}{28\sqrt{(1-\gamma)^{4}T}\log T},$

where the second equality arises from (120), and the last inequality holds as
long as $\prod_{i=\widehat{\tau}}^{T}\big{(}1-\eta_{i}(1-\gamma p)\big{)}\leq
6/7$ (see (180)). This taken together with (168) leads to

$\displaystyle\mathbb{E}\big{[}\Delta_{T,\mathsf{max}}\big{]}\geq
x_{T}\geq\frac{3c}{28\sqrt{(1-\gamma)^{4}T}\log T}.$

Combining the above bound with (154) leads to

$\displaystyle\mathbb{E}\Big{[}V_{T}(1)-V^{\star}(1)\Big{]}$
$\displaystyle\geq\mathbb{E}\Big{[}\Delta_{T,\mathsf{max}}-\frac{1}{1-\gamma}\prod_{i=1}^{T}\big{(}1-\eta_{i}(1-\gamma)\big{)}\Big{]}$
$\displaystyle\geq\frac{3c}{28\sqrt{(1-\gamma)^{4}T}\log
T}-\frac{1}{1-\gamma}\prod_{i=1}^{T}\big{(}1-\eta_{i}(1-\gamma)\big{)}.$

Taking this together with (127), we arrive at

$\displaystyle\max\Big{\\{}$
$\displaystyle\mathbb{E}\Big{[}\big{|}V_{T}(3)-V^{\star}(3)\big{|}\Big{]},\;\mathbb{E}\Big{[}\big{|}V_{T}(1)-V^{\star}(1)\big{|}\Big{]}\Big{\\}}$
$\displaystyle\geq\max\left\\{\frac{1}{1-\gamma}\prod_{i=1}^{T}\big{(}1-\eta_{i}(1-\gamma)\big{)},\leavevmode\nobreak\
\frac{3c}{28\sqrt{(1-\gamma)^{4}T}\log
T}-\frac{1}{1-\gamma}\prod_{i=1}^{T}\big{(}1-\eta_{i}(1-\gamma)\big{)}\right\\}$
$\displaystyle\geq\frac{1}{2}\cdot\frac{1}{1-\gamma}\prod_{i=1}^{T}\big{(}1-\eta_{i}(1-\gamma)\big{)}+\frac{1}{2}\left[\frac{3c}{28\sqrt{(1-\gamma)^{4}T}\log
T}-\frac{1}{1-\gamma}\prod_{i=1}^{T}\big{(}1-\eta_{i}(1-\gamma)\big{)}\right]$
$\displaystyle=\frac{3c}{56\sqrt{(1-\gamma)^{4}T}\log T}.$

This combined with (40) establishes the following desired lower bound:

$\displaystyle\max_{s}\mathbb{E}\Big{[}\big{|}V_{T}(s)-V^{\star}(s)\big{|}^{2}\Big{]}\geq\left(\frac{3c}{56\sqrt{(1-\gamma)^{4}T}\log
T}\right)^{2}=\frac{9c^{2}}{56^{2}(1-\gamma)^{4}T\log^{2}T}.$

####  D.3.4 Proofs of auxiliary results

##### Proof of the inequality (154).

We shall establish this claim by induction. To begin with, the inequality
(154) holds trivially for the base case with $t=0$. Now, let us assume that
the claim holds up to the $(t-1)$-th iteration, and we would like to justify
it for the $t$-th iteration. As an immediate consequence of the claim (154)
for the $(t-1)$-th iteration and the definitions of $V_{t-1}$ and
$\widehat{V}_{t-1}$, we have

$\displaystyle V_{t-1}(1)=\max_{a}Q_{t-1}(1,a)$
$\displaystyle\geq\max_{a}\widehat{Q}_{t-1}(a)-\frac{1}{1-\gamma}\prod_{i=1}^{t-1}\big{(}1-\eta_{i}(1-\gamma)\big{)}$
$\displaystyle=\widehat{V}_{t-1}-\frac{1}{1-\gamma}\prod_{i=1}^{t-1}\big{(}1-\eta_{i}(1-\gamma)\big{)}.$

By virtue of the respective update rules of $Q_{t}(1,a)$ and
$\widehat{Q}_{t}(a)$, we can express their difference as follows:

$\displaystyle Q_{t}(1,a)-\widehat{Q}_{t}(a)$
$\displaystyle=(1-\eta_{t})\big{(}Q_{t-1}(1,a)-\widehat{Q}_{t-1}(a)\big{)}+\eta_{t}\gamma
P_{t}(1\,|\,1,a)\big{(}V_{t-1}(1)-\widehat{V}_{t-1}\big{)}$
$\displaystyle\geq-(1-\eta_{t})\frac{1}{1-\gamma}\prod_{i=1}^{t-1}\big{(}1-\eta_{i}(1-\gamma)\big{)}-\eta_{t}\gamma
P_{t}(1\,|\,1,a)\frac{1}{1-\gamma}\prod_{i=1}^{t-1}\big{(}1-\eta_{i}(1-\gamma)\big{)}$
$\displaystyle\geq-(1-\eta_{t})\frac{1}{1-\gamma}\prod_{i=1}^{t-1}\big{(}1-\eta_{i}(1-\gamma)\big{)}-\eta_{t}\gamma\frac{1}{1-\gamma}\prod_{i=1}^{t-1}\big{(}1-\eta_{i}(1-\gamma)\big{)}$
$\displaystyle=-\frac{1}{1-\gamma}\prod_{i=1}^{t}\big{(}1-\eta_{i}(1-\gamma)\big{)},$

where the first inequality invokes the induction hypothesis for the $(t-1)$-th
iteration. This establishes (154) for the $t$-th iteration, and hence the
proof is complete via an induction argument.

##### Proof of the claim (160).

When taking the constant learning rates
$\eta_{t}\equiv\eta\leq\frac{1}{(1-\gamma)^{2}T}\leq\frac{1}{50}$ (under the
condition $T\geq\frac{50}{(1-\gamma)^{2}}$), one has

$\displaystyle\max_{1\leq k\leq
t}\eta_{k}^{(t)}\leq\eta_{t}=\eta\leq\frac{1}{50},$

thus allowing us to take $\tau=1$ for this case.

It then suffices to look at rescaled linear learning rates (i.e.,
$\eta_{t}=\frac{1}{1+c_{\eta}(1-\gamma)t}$). As already calculated in the
expression (145), the ratio of two consecutive quantities obeys

$\displaystyle\frac{\eta_{k-1}^{(t)}}{\eta_{k}^{(t)}}=\frac{1-\frac{4}{3}(1-\gamma)\eta_{k}}{1-c_{\eta}(1-\gamma)\eta_{k}}.$
(169)

In what follows, we divide into two cases, depending on whether this sequence
is decreasing or increasing.

  * •

The case with $4/3\leq c_{\eta}<\log T$. In this scenario, the ratio in (169)
is larger than 1, and hence the sequence $\\{\eta_{k}^{(t)}\\}$ decreases with
$k$. Let us define

$\displaystyle\tau\coloneqq\min\Bigg{\\{}\tau^{\prime}\,\,\Big{|}\,\,\prod_{i=1}^{\tau^{\prime}}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\leq\frac{1}{50}\Bigg{\\}},$ (170)

which clearly satisfies $\tau\leq T$ (in view of (150)). For all $t\geq\tau$,
one has

$\displaystyle\max_{1\leq k\leq
t}\eta_{k}^{(t)}\leq\prod_{i=1}^{\tau}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\leq\frac{1}{50}.$

At the same time, we claim that one must have

$\displaystyle\prod_{i=\tau}^{T}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\leq\frac{2}{3}.$ (171)

Otherwise, recalling $\eta_{0}^{(T)}=\prod_{i=1}^{T}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}$, we have

$\eta_{0}^{(T)}=\left\\{\prod_{i=1}^{\tau-1}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\right\\}\left\\{\prod_{i=\tau}^{T}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\right\\}>\frac{1}{50}\cdot\frac{2}{3}=\frac{1}{75},$

which contradicts our assumption that $\eta_{0}^{(T)}>1/75$ (cf. (150)).

  * •

The case with $1-\gamma<c_{\eta}<4/3$. In this case, the sequence
$\eta_{k}^{(t)}$ increases with $k$. If we set

$\displaystyle\tau\coloneqq\Big{\lceil}\frac{49}{c_{\eta}(1-\gamma)}\Big{\rceil}<\frac{50}{(1-\gamma)^{2}}<T,$
(172)

then for all $t\geq\tau$ we have

$\displaystyle\max_{1\leq k\leq
t}\eta_{k}^{(t)}=\eta_{t}^{(t)}=\eta_{t}\leq\eta_{\tau}\leq\frac{1}{1+c_{\eta}(1-\gamma)\frac{49}{c_{\eta}(1-\gamma)}}=\frac{1}{50}.$

Under the condition
$T\geq\frac{150}{(1-\gamma)^{2}}\geq\frac{150}{c_{\eta}(1-\gamma)}$ (so that
$T-\tau+1\geq\frac{100}{c_{\eta}(1-\gamma)}\geq\frac{100}{(1-\gamma)4/3}$),
one can show that

$\displaystyle\prod_{i=\tau}^{T}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\leq\Big{(}1-\frac{1-\gamma}{100}\Big{)}^{T-\tau+1}\leq\Big{(}1-\frac{1-\gamma}{100}\Big{)}^{\frac{100}{(1-\gamma)4/3}}\leq\frac{3}{4}.$
(173)

  * •

Putting these two cases together (with $\tau$ specified in (170) and (172)),
we obtain

$\displaystyle\max_{1\leq k\leq t}\eta_{k}^{(t)}\leq\frac{1}{50}$ (174)

for all $t\geq\tau$, thus establishing the desired inequality (160).

##### Proof of the inequality (164).

For every $t$, recalling the definition (163), it is convenient to write

$\displaystyle\mathbb{E}[\xi_{t,\mathsf{max}}]$
$\displaystyle=\mathbb{E}\left[\frac{\xi_{t}(1)+\xi_{t}(2)+|\xi_{t}(1)-\xi_{t}(2)|}{2}\right]=\mathbb{E}\left[\frac{|\xi_{t}(1)-\xi_{t}(2)|}{2}\right]$
$\displaystyle=\frac{1}{2}\mathbb{E}\left[\,\left|\sum_{k=1}^{t}\eta_{k}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\gamma\big{(}P_{k}(1\,|\,1,1)-P_{k}(1\,|\,1,2)\big{)}\widehat{V}_{k-1})\,\right|\right],$

where we have used the fact that $\mathbb{E}[\xi_{t}(a)]=0$. To control the
right-hand side of the above equation, let us define

$\displaystyle\zeta_{t}$ $\displaystyle\coloneqq\sum_{k=1}^{t}z_{k},\qquad
z_{k}\coloneqq\eta_{k}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\gamma\big{(}P_{k}(1\,|\,1,1)-P_{k}(1\,|\,1,2)\big{)}\widehat{V}_{k-1}$

for any $k\geq 1$, where $\\{z_{k}\\}$ also forms a martingale sequence since

$\displaystyle\mathbb{E}\Big{[}z_{k}\,|\,\big{\\{}P_{j}(1\,|\,1,1),P_{j}(1\,|\,1,2)\big{\\}}_{1\leq
j<k}\Big{]}=0.$

As a consequence of Freedman’s inequality, we claim that $\zeta_{t}$ satisfies

$\displaystyle\mathbb{P}\left\\{\big{|}\zeta_{t}\big{|}\geq\sqrt{\frac{8\log\frac{2}{\delta}}{3(1-\gamma)}\sum_{k=1}^{t}\eta_{k}^{2}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}^{2}}+\frac{4\eta_{t}\log\frac{2}{\delta}}{3(1-\gamma)}\right\\}\leq\delta.$
(175)

To verify this relation, we first notice that

$\displaystyle|z_{k}|\leq\max_{1\leq k\leq
t}\eta_{k}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\cdot\frac{1}{1-\gamma}\leq\frac{\eta_{t}}{1-\gamma},$
(176)

provided that
$\max_{k}\eta_{k}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\leq\eta_{t}$. To
verify the condition
$\max_{k}\eta_{k}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\leq\eta_{t}$, one
can check — similar to (145) — that

$\frac{\eta_{k-1}\prod_{i=k}^{t}\big{(}1-\eta_{i}\big{)}}{\eta_{k}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}}=1-\frac{\big{(}1-c_{\eta}(1-\gamma)\big{)}\eta_{k}}{1-c_{\eta}(1-\gamma)\eta_{k}}\leq
1,$ (177)

which indicates that $\eta_{k}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}$ is an
increasing sequence as long as $c_{\eta}\leq\log T\leq\frac{1}{1-\gamma}$ (see
(116)). In addition to the boundedness condition (176), we can further
calculate

$\displaystyle\sum_{k=1}^{t}\mathsf{Var}\big{(}z_{k}\,|\,P_{k-1}(1\,|\,1,1),P_{k-1}(1\,|\,1,2),\ldots,P_{1}(1\,|\,1,1),P_{1}(1\,|\,1,2)\big{)}$
$\displaystyle\qquad=\sum_{k=1}^{t}\eta_{k}^{2}\left[\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\right]^{2}\cdot
2p(1-p)\cdot\big{(}\gamma\widehat{V}_{k-1}\big{)}^{2}\leq\sum_{k=1}^{t}\eta_{k}^{2}\left[\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\right]^{2}\cdot\frac{2}{3(1-\gamma)},$

where the last inequality comes from the facts that
$\widehat{V}_{k-1}\leq\frac{1}{1-\gamma}$ and the choice
$p=\frac{4\gamma-1}{3\gamma}$. These bounds taken together with Freedman’s
inequality (see (51)) validate (175).

By virtue of (175), setting
$\delta=\frac{(1-\gamma)^{2}}{2}\mathbb{E}\big{[}|\zeta_{t}|^{2}\big{]}$
yields that with probability at least $1-\delta$,

$\displaystyle|\zeta_{t}|\leq
B\coloneqq\sqrt{\frac{8\log\frac{2}{\delta}}{3(1-\gamma)}\sum_{k=1}^{t}\eta_{k}^{2}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}^{2}}+\frac{4\eta_{t}\log\frac{2}{\delta}}{3(1-\gamma)}\leavevmode\nobreak\
\leavevmode\nobreak\ \text{ with
}\delta=\frac{(1-\gamma)^{2}}{2}\mathbb{E}\big{[}|\zeta_{t}|^{2}\big{]}.$
(178)

When $T\geq\frac{1}{(1-\gamma)^{2}}$, one can ensure that

$\displaystyle\mathbb{E}[\xi_{t,\mathsf{max}}]$
$\displaystyle=\frac{1}{2}\mathbb{E}\big{[}|\zeta_{t}|\big{]}\geq\frac{1}{2}\mathbb{E}\big{[}|\zeta_{t}|\mathds{1}\big{(}|\zeta_{t}|\leq
B\big{)}\big{]}\geq\frac{1}{2B}\mathbb{E}\big{[}|\zeta_{t}|^{2}\mathds{1}\big{(}|\zeta_{t}|\leq
B\big{)}\big{]}$
$\displaystyle=\frac{1}{2B}\Big{\\{}\mathbb{E}[|\zeta_{t}|^{2}]-\mathbb{E}\big{[}|\zeta_{t}|^{2}\mathds{1}\big{(}|\zeta_{t}|>B\big{)}\big{]}\Big{\\}}$
$\displaystyle\overset{(\mathrm{i})}{\geq}\frac{1}{2B}\Big{\\{}\mathbb{E}[|\zeta_{t}|^{2}]-\frac{1}{(1-\gamma)^{2}}\mathbb{P}\big{\\{}|\zeta_{t}|>B\big{\\}}\Big{\\}}$
$\displaystyle\geq\frac{1}{2B}\Big{\\{}\mathbb{E}[|\zeta_{t}|^{2}]-\frac{\delta}{(1-\gamma)^{2}}\Big{\\}}\overset{(\mathrm{ii})}{\geq}\frac{1}{4B}\mathbb{E}[|\zeta_{t}|^{2}].$
(179)

Here, (i) holds since

$\displaystyle\big{|}\zeta_{t}\big{|}\leq\sum_{k=1}^{t}|z_{k}|\leq\left[\sum_{k=1}^{t}\eta_{k}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\right]\cdot\frac{1}{1-\gamma}\leq\frac{1}{1-\gamma}$

as a consequence of (176) and (62); (ii) holds by the choice of $\delta$. It
is thus sufficient to lower bound $\mathbb{E}[|\zeta_{t}|^{2}]$. Towards this,
let us define

$\displaystyle\widehat{\tau}\coloneqq\max\Bigg{\\{}\tau^{\prime}\,\,\Big{|}\,\,\prod_{i=\tau^{\prime}}^{T}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\leq\frac{6}{7}\Bigg{\\}},$ (180)

which clearly satisfies $\tau\leq\widehat{\tau}\leq T$ (in view of (171) and
(173)). Then, for all $t\geq\widehat{\tau}$ one has (which shall be proved
towards the end of this subsection)

$\displaystyle\sum_{k=\tau}^{t}\eta_{k}^{2}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}^{2}\geq\frac{1}{8}\sum_{k=1}^{t}\eta_{k}^{2}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}^{2}.$
(181)

We now proceed to lower bound $\mathbb{E}[|\zeta_{t}|^{2}]$ for
$t\geq\widehat{\tau}$. We first observe that for any $t\geq\widehat{\tau}$,

$\displaystyle\mathbb{E}\big{[}|\zeta_{t}|^{2}\big{]}$
$\displaystyle\geq\sum_{k=1}^{t}\mathbb{E}\left[\mathsf{Var}\Big{(}\eta_{k}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\gamma\big{(}P_{k}(1\,|\,1,1)-P_{k}(1\,|\,1,2)\big{)}\widehat{V}_{k-1}\,|\,\widehat{V}_{k-1}\Big{)}\right]$
$\displaystyle\geq\frac{1}{2}\sum_{k=\tau}^{t}\mathbb{E}\left[\mathsf{Var}\Big{(}\eta_{k}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\gamma\big{(}P_{k}(1\,|\,1,1)-P_{k}(1\,|\,1,2)\big{)}\widehat{V}_{k-1}\,|\,\widehat{V}_{k-1}\geq\frac{1}{4(1-\gamma)}\Big{)}\right],$

where the first line relies on (130), and the last step makes use of the fact
(157). To further control the right-hand side of the above inequality, we take
$\tau^{\prime}\coloneqq\max\left\\{t-\frac{1}{\eta_{t/2}},1\right\\}$ and show
that

$\displaystyle\mathbb{E}\big{[}|\zeta_{t}|^{2}\big{]}$
$\displaystyle\overset{\text{(i)}}{\geq}\frac{1}{2}\sum_{k=\tau}^{t}\eta_{k}^{2}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}^{2}\gamma^{2}\cdot
2p(1-p)\frac{1}{16(1-\gamma)^{2}}$
$\displaystyle\geq\frac{1}{48(1-\gamma)}\sum_{k=\tau}^{t}\eta_{k}^{2}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}^{2}\overset{\text{(ii)}}{\geq}\frac{1}{400(1-\gamma)}\sum_{k=1}^{t}\eta_{k}^{2}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}^{2}$
$\displaystyle\geq\frac{1}{400(1-\gamma)}\sum_{k=\tau^{\prime}}^{t}\eta_{k}^{2}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}^{2}\overset{\text{(iii)}}{\geq}\frac{\eta_{t}}{9600(1-\gamma)}.$
(182)

Here, (i) makes use of the constraint
$\widehat{V}_{k-1}\geq\frac{1}{4(1-\gamma)}$, while (ii) makes use of (181),
and (iii) are valid if the following property holds (which shall be proved
towards the end of this subsection)

$\displaystyle\sum_{k=\tau^{\prime}}^{t}\eta_{k}^{2}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}^{2}\geq\frac{1}{24}\eta_{t}.$
(183)

We are now well-equipped to control $\mathbb{E}[\xi_{t,\mathsf{max}}]$ using
the property (179). Recall the expression of $B$ in (178), we know that
bounding $\mathbb{E}[|\zeta_{t}|^{2}]/B$ boils down to controlling

$\displaystyle\frac{\mathbb{E}[|\zeta_{t}|^{2}]}{\frac{\eta_{t}}{1-\gamma}\log\frac{2}{\delta}}\qquad\mbox{and}\qquad\frac{\mathbb{E}[|\zeta_{t}|^{2}]}{\sqrt{\frac{\log\frac{2}{\delta}}{1-\gamma}\sum_{k=1}^{t}\eta_{k}^{2}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}^{2}}}.$
(184)

  * •

For the first term in (184), recalling that
$\delta=\frac{(1-\gamma)^{2}}{2}\mathbb{E}\big{[}|\zeta_{t}|^{2}\big{]}$, we
can demonstrate that

$\displaystyle\log\frac{1}{\delta}=-\log\frac{(1-\gamma)^{2}}{2}\mathbb{E}\big{[}|\zeta_{t}|^{2}\big{]}\leq-\log\frac{(1-\gamma)\eta_{t}}{19200}\leq\log\frac{19200(1+(1-\gamma)T\log
T)}{1-\gamma}\lesssim\log T,$ (185)

where the first inequality makes use of the bound (182), and the second
inequality arises from the fact $\eta_{t}\geq\frac{1}{1+(1-\gamma)T\log T}$
(given the range of the learning rates in this case). Combining this with
(182), we can guarantee that

$\frac{\mathbb{E}[|\zeta_{t}|^{2}]}{\frac{\eta_{t}}{1-\gamma}\log\frac{2}{\delta}}\gtrsim\frac{1}{\log
T}.$

  * •

Moving to the second term in (184), one can ensure that

$\displaystyle\frac{\mathbb{E}\big{[}|\zeta_{t}|^{2}\big{]}}{\sqrt{\frac{\log\frac{2}{\delta}}{1-\gamma}\sum_{k=1}^{t}\eta_{k}^{2}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}^{2}}}$
$\displaystyle\overset{\mathrm{(i)}}{\gtrsim}\sqrt{\frac{1}{(1-\gamma)\log
T}\sum_{k=1}^{t}\eta_{k}^{2}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}^{2}}$
$\displaystyle\overset{\mathrm{(ii)}}{\gtrsim}\sqrt{\frac{\eta_{t}}{(1-\gamma)\log
T}}\overset{\mathrm{(iii)}}{\gtrsim}\frac{1}{\sqrt{(1-\gamma)^{2}T}\log T}.$

Here, (i) follows from (182) and (185) since

$\mathbb{E}\big{[}|\zeta_{t}|^{2}\big{]}\gtrsim\frac{1}{1-\gamma}\sum_{k=1}^{t}\eta_{k}^{2}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}^{2}\qquad\text{and}\qquad\log\frac{2}{\delta}\lesssim\log
T;$

(ii) arises from (183); and (iii) relies on the fact
$\eta_{t}\gtrsim\frac{1}{(1-\gamma)T\log T}$ (given the range of the learning
rates in this case).

Substituting the above relations into (179) and using the expression of $B$ in
(178), we reach at

$\displaystyle\mathbb{E}[\xi_{t,\mathsf{max}}]\geq\frac{1}{4B}\mathbb{E}\big{[}|\zeta_{t}|^{2}\big{]}$
$\displaystyle\geq\frac{c}{\sqrt{(1-\gamma)^{2}T}\log T},$

for some constant $c>0$. Thus, this validates the inequality (164).

###### Proof of the claim (181).

By the definition of $\widehat{\tau}$ in (180), we have
$\prod_{i=\widehat{\tau}}^{T}\big{(}1-\eta_{i}(1-\gamma p)\big{)}\leq 6/7$. An
important observation is that

$\displaystyle\sum_{k=\tau}^{t}\eta_{k}\left[\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\right]\stackrel{{\scriptstyle\mathrm{(i)}}}{{=}}1-\prod_{i=\tau}^{t}\big{(}1-\eta_{i}\big{)}\stackrel{{\scriptstyle\mathrm{(ii)}}}{{\geq}}\frac{1}{8}\stackrel{{\scriptstyle\mathrm{(iii)}}}{{\geq}}\frac{1}{8}\sum_{k=1}^{t}\eta_{k}\left[\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\right].$
(186)

Here, the relations (i) and (iii) arise from (63), and the inequality (ii)
follows since

$\displaystyle\prod_{i=\tau}^{t}\big{(}1-\eta_{i}\big{)}\leq\prod_{i=\tau}^{\widehat{\tau}}\big{(}1-\eta_{i}\big{)}\leq\prod_{i=\tau}^{\widehat{\tau}}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}=\frac{\prod_{i=\tau}^{T}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}}{\prod_{i=\widehat{\tau}+1}^{T}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}}\leq\frac{\,3/4\,}{6/7}\leq\frac{7}{8},$ (187)

where $\tau$ is defined in (170) and (172) for linearly rescaled learning
rates and $\tau=1$ for constant learning rates, and we have also made use of
(150), (171) and (173) in the penultimate inequality in (187).

With (186) in place, we can continue to prove the claim (181). Recognizing
that $\eta_{k}\big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\big{]}$ is
increasing in $k$ (see (177)), we can obtain

$\displaystyle\sum_{k=1}^{\tau-1}\eta_{k}^{2}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}^{2}$
$\displaystyle\leq\max_{1\leq
k<\tau}\left\\{\eta_{k}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}\right\\}\sum_{k=1}^{\tau-1}\eta_{k}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}$
$\displaystyle\leq\eta_{\tau}\Big{[}\prod_{i=\tau+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}\sum_{k=1}^{\tau-1}\eta_{k}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}$
$\displaystyle\leq
7\eta_{\tau}\Big{[}\prod_{i=\tau+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}\sum_{k=\tau}^{t}\eta_{k}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]},$
(188)

where the last inequality comes from (186). With the preceding inequality in
place, the claim (181) then follows by observing that

$\displaystyle\sum_{k=\tau}^{t}\eta_{k}^{2}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}^{2}$
$\displaystyle\geq\min_{\tau\leq k\leq
t}\left\\{\eta_{k}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}\right\\}\sum_{k=\tau}^{t}\eta_{k}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}$
$\displaystyle\geq\eta_{\tau}\Big{[}\prod_{i=\tau+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}\sum_{k=\tau}^{t}\eta_{k}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]},$

where we make use of the monotonicity of
$\eta_{k}\big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\big{]}$ again. ∎

###### Proof of the claim (183).

Note that for
$\tau^{\prime}\coloneqq\max\left\\{t-\frac{1}{\eta_{t/2}},1\right\\}$, one has

$\eta_{k}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}\geq\eta_{t}\big{(}1-\eta_{t/2}\big{)}^{t-\tau^{\prime}}\geq\eta_{t}\big{(}1-\eta_{t/2}\big{)}^{1/\eta_{t/2}}\geq\frac{1}{3}\eta_{t},\qquad\text{for
all}\leavevmode\nobreak\ \tau^{\prime}\leq k\leq t,$

as long as the following condition holds (recalling the definition of
$\widehat{\tau}$ in (180))

$\eta_{t/2}\leq 2\eta_{t}\leq 2\eta_{\widehat{\tau}}\leq 1/10.$ (189)

In addition, similar to (120), we can derive

$\displaystyle\sum_{k=\tau^{\prime}}^{t}\eta_{k}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}$
$\displaystyle=1-\prod_{i=\tau^{\prime}}^{t}\big{(}1-\eta_{i}\big{)}\geq
1-\max\left\\{\big{(}1-\eta_{t}\big{)}^{1/\eta_{t/2}+1},\,\prod_{i=1}^{t}\big{(}1-\eta_{i}\big{)}\right\\}$
$\displaystyle\geq
1-\max\left\\{e^{-1/2},\,\prod_{i=1}^{\widehat{\tau}}\big{(}1-\eta_{i}\big{)}\right\\}\geq\frac{1}{8},$

where we once again use the condition (189), and the last inequality comes
from the derivation in (187). Putting these two bounds together yields

$\displaystyle\sum_{k=\tau^{\prime}}^{t}\eta_{k}^{2}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}^{2}$
$\displaystyle\geq\min_{k:\,\tau^{\prime}\leq k\leq
t}\left\\{\eta_{k}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}\right\\}\sum_{k=\tau^{\prime}}^{t}\eta_{k}\Big{[}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}\big{)}\Big{]}$
$\displaystyle\geq\frac{1}{3}\eta_{t}\cdot\frac{1}{8}\geq\frac{1}{24}\eta_{t}.$

To finish up, it remains to justify (189). This condition is obvious for
constant learning rates. As for rescaled learning rates, one can see that

$\eta_{i}=\frac{1}{1+(1-\gamma)c_{\eta}i}\geq\frac{19}{20c_{\eta}(1-\gamma)i}\qquad\text{for
all }i\geq\overline{\tau},$

where $\overline{\tau}\coloneqq\lceil\frac{19}{c_{\eta}(1-\gamma)}\rceil$.
This allows one to obtain

$\log\Big{[}\prod_{i=\overline{\tau}}^{T}\big{(}1-\eta_{i}(1-\gamma
p)\big{)}\Big{]}\leq-\sum_{i=\overline{\tau}}^{T}\eta_{i}(1-\gamma
p)\leq-\sum_{i=\overline{\tau}}^{T}\frac{19}{15c_{\eta}i}\leq-\frac{19\log\frac{\,T\,}{\overline{\tau}}}{15c_{\eta}}\leq-\frac{19\log\frac{c_{\eta}(1-\gamma)T}{20}}{15c_{\eta}}\leq-\frac{1}{5},$

provided that $T\geq\frac{c_{1}}{(1-\gamma)^{2}}$ for some sufficiently large
constant $c_{1}>0$ and $1-\gamma<c_{\eta}<\log T$. Taking this together with
(180) implies that $\widehat{\tau}\geq\overline{\tau}$ and hence
$\eta_{\widehat{\tau}}\leq\eta_{\overline{\tau}}=\frac{1}{1+(1-\gamma)c_{\eta}\overline{\tau}\,}=1/20$.
∎

###  D.4 Proof of Lemma 3

Given that state $0$ is an absorbing state with zero immediate reward, it is
easily seen that

$V^{\pi}(0)=0\qquad\text{for all }\pi\qquad\Longrightarrow\qquad
V^{\star}(0)=Q^{\star}(0,1)=0.$

Moreover, by construction, taking action 1 and taking action 2 in state 1
result in the same behavior (in terms of both the reward function and the
associated transition probability), and as a consequence,

$Q^{\star}(1,1)=Q^{\star}(1,2)=V^{\star}(1).$ (190)

From Bellman’s equation, we can thus deduce that

$Q^{\star}(1,1)=r(1,1)+\gamma P(0\,|\,1,1)V^{\star}(0)+\gamma
P(1\,|\,1,1)V^{\star}(1),$

which in conjunction with (190) and a little algebra leads to

$V^{\star}(1)=\frac{r(1,1)+\gamma P(0\,|\,1,1)V^{\star}(0)}{1-\gamma
P(1\,|\,1,1)}=\frac{1}{1-\gamma p}=\frac{3}{4(1-\gamma)}.$

Here, the second identity follows since $V^{\star}(0)=0$, and the third
identity makes use of (38). The calculation for $V^{\star}(2)$ and
$Q^{\star}(2,1)$ follows from an identical argument and is hence omitted.

Turning to state $3$, by Bellman’s equation, we have

$V^{\star}(3)=Q^{\star}(3,1)=r(3,1)+\gamma P(3\,|\,3,1)V^{\star}(3)=1+\gamma
V^{\star}(3),$

which leads to $V^{\star}(3)=\frac{1}{1-\gamma}$.

##  Appendix E Analysis for asynchronous Q-learning (Theorem 4)

###  E.1 Notation and preliminary facts

##### Vector and matrix notation.

We shall adopt the vector notation
$\bm{Q}_{t}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$,
$\bm{V}_{t}\in\mathbb{R}^{|\mathcal{S}|}$,
$\bm{r}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$ in the same way as in
Section 4.1. The sample transition matrix
$\bm{P}_{t}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times|\mathcal{S}|}$ in
the asynchronous case is defined such that

$\bm{P}_{t}\big{(}(s,a),s^{\prime}\big{)}=\begin{cases}1,\quad&\text{if
}(s,a,s^{\prime})=(s_{t-1},a_{t-1},s_{t});\\\ 0,\quad&\text{else}.\end{cases}$
(191)

It is also handy to introduce the diagonal matrix
$\bm{\Lambda}_{t}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times|\mathcal{S}||\mathcal{A}|}$
such that

$\bm{\Lambda}_{t}\big{(}(s,a),(s,a)\big{)}=\begin{cases}\eta,\qquad&\text{if
}(s,a)=(s_{t-1},a_{t-1});\\\ 0,&\text{otherwise.}\end{cases}$ (192)

Armed with the above notation, the asynchronous Q-learning update rule (42)
can be conveniently expressed as follows:

$\displaystyle\bm{Q}_{t}=\big{(}\bm{I}-\bm{\Lambda}_{t}\big{)}\bm{Q}_{t-1}+\bm{\Lambda}_{t}\big{(}\bm{r}+\gamma\bm{P}_{t}\bm{V}_{t-1}\big{)}.$
(193)

##### Range of $V_{t}$ and $Q_{t}$.

Similar to the synchronous counterpart, we have the following elementary
properties.

######  Lemma 7.

Suppose that $0<\eta_{t}\leq 1$ for all $t\geq 0$. Assume that
$\bm{0}\leq\bm{Q}_{0}\leq\frac{1}{1-\gamma}\bm{1}$. Then for any $t\geq 0$,
one has

$\displaystyle\bm{0}\leq\bm{Q}_{t}\leq\frac{1}{1-\gamma}\bm{1}\qquad\text{and}\qquad\bm{0}\leq\bm{V}_{t}\leq\frac{1}{1-\gamma}\bm{1}.$
(194)

###### Proof.

The proof is the same as that of Lemma 4, and is hence omitted for brevity. ∎

###  E.2 Main steps for proving Theorem 4

We are now in a position to outline the main steps for the proof of Theorem 4.

##### Step 1: deriving basic recursions.

According to the update rule (193), we can derive the following elementary
decomposition

$\displaystyle\bm{\Delta}_{t}\coloneqq\bm{Q}_{t}-\bm{Q}^{\star}$
$\displaystyle=\big{(}\bm{I}-\bm{\Lambda}_{t}\big{)}\bm{Q}_{t-1}+\bm{\Lambda}_{t}\big{(}\bm{r}+\gamma\bm{P}_{t}\bm{V}_{t-1}\big{)}-\bm{Q}^{\star}$
$\displaystyle=\big{(}\bm{I}-\bm{\Lambda}_{t}\big{)}\big{(}\bm{Q}_{t-1}-\bm{Q}^{\star}\big{)}+\bm{\Lambda}_{t}\big{(}\bm{r}+\gamma\bm{P}_{t}\bm{V}_{t-1}-\bm{Q}^{\star}\big{)}$
$\displaystyle=\big{(}\bm{I}-\bm{\Lambda}_{t}\big{)}\big{(}\bm{Q}_{t-1}-\bm{Q}^{\star}\big{)}+\gamma\bm{\Lambda}_{t}\big{(}\bm{P}_{t}\bm{V}_{t-1}-\bm{P}\bm{V}^{\star}\big{)}$
$\displaystyle=\big{(}\bm{I}-\bm{\Lambda}_{t}\big{)}\bm{\Delta}_{t-1}+\gamma\bm{\Lambda}_{t}\big{(}\bm{P}_{t}-\bm{P}\big{)}\bm{V}_{t-1}+\gamma\bm{\Lambda}_{t}\bm{P}\big{(}\bm{V}_{t-1}-\bm{V}^{\star}\big{)},$
(195)

where the penultimate identity follows from the Bellman optimality equation
$\bm{Q}^{\star}=\bm{r}+\bm{P}\bm{V}^{\star}$. Combining (195) with the
inequalities (24) and using the definition (18) of $\pi_{t}$ result in

$\displaystyle\bm{\Delta}_{t}$
$\displaystyle\leq\big{(}\bm{I}-\bm{\Lambda}_{t}\big{)}\bm{\Delta}_{t-1}+\gamma\bm{\Lambda}_{t}\big{(}\bm{P}_{t}-\bm{P}\big{)}\bm{V}_{t-1}+\gamma\bm{\Lambda}_{t}\bm{P}^{\pi_{t-1}}\bm{\Delta}_{t-1},$
(196a) $\displaystyle\bm{\Delta}_{t}$
$\displaystyle\geq\big{(}\bm{I}-\bm{\Lambda}_{t}\big{)}\bm{\Delta}_{t-1}+\gamma\bm{\Lambda}_{t}\big{(}\bm{P}_{t}-\bm{P}\big{)}\bm{V}_{t-1}+\gamma\bm{\Lambda}_{t}\bm{P}^{\pi^{\star}}\bm{\Delta}_{t-1}.$
(196b)

Apply the above two relations recursively to obtain

$\displaystyle\bm{\Delta}_{t}$
$\displaystyle\leq\gamma\sum_{i=1}^{t}\prod_{j=i+1}^{t}\big{(}\bm{I}-\bm{\Lambda}_{j}\big{)}\bm{\Lambda}_{i}\big{(}\bm{P}_{i}-\bm{P}\big{)}\bm{V}_{i-1}+\gamma\sum_{i=1}^{t}\prod_{j=i+1}^{t}\big{(}\bm{I}-\bm{\Lambda}_{j}\big{)}\bm{\Lambda}_{i}\bm{P}^{\pi_{i-1}}\bm{\Delta}_{i-1}+\prod_{j=1}^{t}\big{(}\bm{I}-\bm{\Lambda}_{j}\big{)}\bm{\Delta}_{0},$
(197a) $\displaystyle\bm{\Delta}_{t}$
$\displaystyle\geq\gamma\sum_{i=1}^{t}\prod_{j=i+1}^{t}\big{(}\bm{I}-\bm{\Lambda}_{j}\big{)}\bm{\Lambda}_{i}\big{(}\bm{P}_{i}-\bm{P}\big{)}\bm{V}_{i-1}+\gamma\sum_{i=1}^{t}\prod_{j=i+1}^{t}\big{(}\bm{I}-\bm{\Lambda}_{j}\big{)}\bm{\Lambda}_{i}\bm{P}^{\pi^{\star}}\bm{\Delta}_{i-1}+\prod_{j=1}^{t}\big{(}\bm{I}-\bm{\Lambda}_{j}\big{)}\bm{\Delta}_{0}.$
(197b)

By defining the following diagonal matrices

$\bm{\Lambda}_{i}^{(t)}\coloneqq\begin{cases}\prod_{j=1}^{t}(\bm{I}-\bm{\Lambda}_{j}),&\text{if
}i=0,\\\ \bm{\Lambda}_{i}\prod_{j=i+1}^{t}(\bm{I}-\bm{\Lambda}_{j}),&\text{if
}0<i<t,\\\ \bm{\Lambda}_{t},&\text{if }i=t,\end{cases}$ (198)

and setting

$\beta=\frac{c_{3}(1-\gamma)}{\log T}$ (199)

for some constant $c_{3}>0$, we can rearrange terms in the upper bound (197a)
to reach

$\displaystyle\bm{\Delta}_{t}$
$\displaystyle\leq\underset{\eqqcolon\,\bm{\zeta}_{t}}{\underbrace{\bm{\Lambda}_{0}^{(t)}\bm{\Delta}_{0}+\gamma\sum_{i=1}^{(1-\beta)t}\bm{\Lambda}_{i}^{(t)}\Big{[}\big{(}\bm{P}_{i}-\bm{P}\big{)}\bm{V}_{i-1}+\bm{P}^{\pi_{i-1}}\bm{\Delta}_{i-1}\Big{]}}}$
$\displaystyle\qquad+\underset{\eqqcolon\,\bm{\xi}_{t}}{\underbrace{\gamma\sum_{i=(1-\beta)t+1}^{t}\bm{\Lambda}_{i}^{(t)}\big{(}\bm{P}_{i}-\bm{P}\big{)}\bm{V}_{i-1}}}+\gamma\sum_{i=(1-\beta)t+1}^{t}\bm{\Lambda}_{i}^{(t)}\bm{P}^{\pi_{i-1}}\bm{\Delta}_{i-1}.$
(200)

In the subsequent steps, we shall first develop bounds on the sizes of the
terms $\bm{\zeta}_{t}$ and $\bm{\xi}_{t}$ in (200) separately, and then
combine these bounds with (200) recursively in order to derive the advertised
upper bound on $\bm{\Delta}_{t}$.

##### Step 2: bounding the terms $\bm{\zeta}_{t}$ and $\bm{\xi}_{t}$.

The terms $\bm{\zeta}_{t}$ and $\bm{\xi}_{t}$ defined in (200) can be bounded
with high probability by the following lemmas.

######  Lemma 8.

With probability at least $1-\delta$, we have

$\displaystyle\|\bm{\zeta}_{t}\|_{\infty}\leq\frac{4}{(1-\gamma)T}$ (201)

for all $t$ obeying $\frac{T}{c_{4}\log T}\leq t\leq T$. Here, $c_{4}>0$ is
some constant obeying $c_{4}\leq c_{1}c_{3}/4$, where the constants $c_{1}$
and $c_{3}$ appear in (46a) and (199), respectively.

###### Proof.

See Section E.3.1. ∎

######  Lemma 9.

Suppose that $0<\eta\leq\frac{\log^{3}T}{(1-\gamma)T\mu_{\mathsf{min}}}$. With
probability at least $1-\delta$, one has

$\displaystyle|\bm{\xi}_{t}|\leq\sqrt{\frac{16\big{(}\log^{3}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)T\mu_{\mathsf{min}}}\Big{(}\max_{(1-\beta)t\leq
i<t}\mathsf{Var}_{\bm{P}}(\bm{V}_{i})+\bm{1}\Big{)}}+\frac{6\big{(}\log^{3}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)^{2}T\mu_{\mathsf{min}}}\bm{1}$
(202)

for all $t$ obeying $\frac{T}{c_{4}\log T}\leq t\leq T$ for some constant
$c_{4}>0$.

###### Proof.

See Section E.3.2. ∎

##### Step 3: controlling $\bm{\Delta}_{t}$.

Consider any $t$ obeying $\frac{T}{c_{4}\log T}\leq t\leq T$ and any $k$
obeying $2t/3\leq k\leq t$. Under the sample size condition (46b), Lemmas 8-9
together with a little algebra lead to

$|\bm{\zeta}_{k}|+|\bm{\xi}_{k}|\leq\sqrt{\frac{32\big{(}\log^{3}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)T\mu_{\mathsf{min}}}\bigg{(}\max_{(1-\beta)k\leq
i\leq
k}\mathsf{Var}_{\bm{P}}(\bm{V}_{i})+\bm{1}\bigg{)}}\leq\sqrt{\bm{\varphi}_{t}},$

where we define

$\bm{\varphi}_{t}\coloneqq\frac{32\big{(}\log^{3}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)T\mu_{\mathsf{min}}}\bigg{(}\max_{\frac{t}{2}\leq
i\leq t}\mathsf{Var}_{\bm{P}}(\bm{V}_{i})+\bm{1}\bigg{)}.$ (203)

Combining this inequality with (200) allows us to obtain

$\displaystyle\bm{\Delta}_{k}$
$\displaystyle\leq\sqrt{\bm{\varphi}_{t}}+\sum_{i=(1-\beta)k+1}^{k}\bm{\Lambda}_{i}^{(k)}\gamma\bm{P}^{\pi_{i-1}}\bm{\Delta}_{i-1}=\sqrt{\bm{\varphi}_{t}}+\sum_{i=(1-\beta)k}^{k-1}\bm{\Lambda}_{i+1}^{(k)}\gamma\bm{P}^{\pi_{i}}\bm{\Delta}_{i}\qquad\text{for
all }\leavevmode\nobreak\ 2t/3\leq k\leq t.$ (204)

Similar to the quantity $\alpha_{i}^{(t)}$ defined in (69), let us define

$\displaystyle\bm{D}_{i}^{(t)}\coloneqq\bigg{(}\sum_{j=(1-\beta)t}^{t-1}\bm{\Lambda}_{j+1}^{(t)}\bigg{)}^{-1}\bm{\Lambda}_{i+1}^{(t)},$
(205)

which, according to (62) and the definition (192), clearly satisfies

$\bm{D}_{i}^{(t)}\geq\bm{\Lambda}_{i+1}^{(t)}\geq\bm{0}\qquad\text{and}\qquad\sum_{i=(1-\beta)t}^{t-1}\bm{D}_{i}^{(t)}=\bm{I}.$
(206)

Set $i_{0}=t$ for notational convenience. With this set of notation and the
property (206) in mind, we can derive the following bound

$\displaystyle\bm{\Delta}_{t}$
$\displaystyle\leq\sum_{i_{1}=(1-\beta)t}^{t-1}\Big{(}\bm{D}_{i_{1}}^{(t)}\sqrt{\bm{\varphi}_{t}}+\bm{\Lambda}_{i_{1}+1}^{(t)}\gamma\bm{P}^{\pi_{i_{1}}}\bm{\Delta}_{i_{1}}\Big{)}$
$\displaystyle\leq\sum_{i_{1}=(1-\beta)t}^{t-1}\Bigg{[}\bm{D}_{i_{1}}^{(t)}\sqrt{\bm{\varphi}_{t}}+\bm{\Lambda}_{i_{1}+1}^{(t)}\gamma\bm{P}^{\pi_{i_{1}}}\sum_{i_{2}=(1-\beta)i_{1}}^{i_{1}-1}\Big{(}\bm{D}_{i_{2}}^{(i_{1})}\sqrt{\bm{\varphi}_{t}}+\bm{\Lambda}_{i_{2}+1}^{(i_{1})}\gamma\bm{P}^{\pi_{i_{2}}}\bm{\Delta}_{i_{2}}\Big{)}\Bigg{]}$
$\displaystyle\leq\sum_{i_{1}=(1-\beta)t}^{t-1}\bm{D}_{i_{1}}^{(t)}\sqrt{\bm{\varphi}_{t}}+\sum_{i_{1}=(1-\beta)t}^{t-1}\bm{D}_{i_{1}}^{(t)}\sum_{i_{2}=(1-\beta)i_{1}}^{i_{1}-1}\big{(}\gamma\bm{P}^{\pi_{i_{1}}}\bm{D}_{i_{2}}^{(i_{1})}\big{)}\sqrt{\bm{\varphi}_{t}}$
$\displaystyle\qquad\qquad+\sum_{i_{1}=(1-\beta)t}^{t-1}\sum_{i_{2}=(1-\beta)i_{1}}^{i_{1}-1}\prod_{k=1}^{2}\big{(}\bm{\Lambda}_{i_{k}+1}^{(i_{k-1})}\gamma\bm{P}^{\pi_{i_{k}}}\big{)}\bm{\Delta}_{i_{2}}$
$\displaystyle=\sum_{i_{1}=(1-\beta)t}^{t-1}\bm{D}_{i_{1}}^{(t)}\Bigg{\\{}\bm{I}+\sum_{i_{2}=(1-\beta)i_{1}}^{i_{1}-1}\gamma\bm{P}^{\pi_{i_{1}}}\bm{D}_{i_{2}}^{(i_{1})}\Bigg{\\}}\sqrt{\bm{\varphi}_{t}}+\sum_{i_{1}=(1-\beta)t}^{t-1}\sum_{i_{2}=(1-\beta)i_{1}}^{i_{1}-1}\prod_{k=1}^{2}\big{(}\bm{\Lambda}_{i_{k}+1}^{(i_{k-1})}\gamma\bm{P}^{\pi_{i_{k}}}\big{)}\bm{\Delta}_{i_{2}}.$
(207)

Here, the first relation makes use of the second property in (206), the second
relation further expands $\bm{\Delta}_{i_{1}}$ in the same way as in the first
line of (207), whereas the third inequality relies on the first property in
(206).

Next, we intend to invoke the above relation multiple times to reach a simpler
relation. Set

$\displaystyle H\coloneqq\frac{\log T}{1-\gamma}.$ (208)

Similar to the way we derive (77), we can apply the relation (207) recursively
and use the basic relation $|\bm{\Delta}_{k}|\leq\frac{1}{1-\gamma}\bm{1}$ for
any $k$ to show that

$\displaystyle\bm{\Delta}_{t}$
$\displaystyle\leq\sum_{\left(i_{1},\cdots,i_{H}\right)\in\mathcal{I}_{t}}\Bigg{\\{}\bm{D}_{i_{1}}^{(t)}\bigg{(}\bm{I}+\sum_{h=1}^{H-1}\gamma^{h}\prod_{k=1}^{h}\big{(}\bm{P}^{\pi_{i_{k}}}\bm{D}_{i_{k+1}}^{(i_{k})}\big{)}\bigg{)}\sqrt{\bm{\varphi}_{t}}+\gamma^{H}\prod_{k=1}^{H}\big{(}\bm{\Lambda}_{i_{k}+1}^{(i_{k-1})}\bm{P}^{\pi_{i_{k}}}\big{)}\big{|}\bm{\Delta}_{i_{H}}\big{|}\Bigg{\\}},$
(209)

where $\mathcal{I}_{t}$ has been defined in (75). To further simplify (209),
we need to control the two terms on the right-hand side of (209) separately.

  * •

We shall begin with the first term on the right-hand side of (209). Towards
this end, let us define a collection of policies $\\{\widehat{\pi}_{k}\\}$
recursively and backward as follows:

$\displaystyle\widehat{\pi}_{k}\coloneqq\begin{cases}\arg\max_{\pi\in\Pi}\bm{\Pi}^{\pi}\sqrt{\bm{\varphi}_{t}},&\text{if
}k=H-1,\\\
\arg\max_{\pi\in\Pi}\bm{\Pi}^{\pi}\Big{(}\bm{I}+\sum_{h=k+1}^{H-1}\gamma^{h}\prod_{j=1}^{h}\bm{P}^{\widehat{\pi}_{j}}\Big{)}\sqrt{\bm{\varphi}_{t}},\quad&\text{if
}k=H-2,\cdots,1,\end{cases}$ (210)

or alternatively (in view of the definition (15) of $\bm{P}^{\pi}$),

$\displaystyle\widehat{\pi}_{k}\coloneqq\begin{cases}\arg\max_{\pi\in\Pi}\bm{P}^{\pi}\sqrt{\bm{\varphi}_{t}},&\text{if
}k=H-1;\\\
\arg\max_{\pi\in\Pi}\bm{P}^{\pi}\Big{(}\bm{I}+\sum_{h=k+1}^{H-1}\gamma^{h}\prod_{j=1}^{h}\bm{P}^{\widehat{\pi}_{j}}\Big{)}\sqrt{\bm{\varphi}_{t}},\quad&\text{if
}k=H-2,\cdots,1.\end{cases}$ (211)

Here, $\Pi$ is a policy set satisfying

$\displaystyle\begin{aligned}
\Pi\coloneqq\big{\\{}\pi=[\pi(s)]_{s\in\mathcal{S}}\,\big{|}\,\pi(s)\in\Pi_{s},\forall
s\in\mathcal{S}\big{\\}},\qquad\Pi_{s}\coloneqq\big{\\{}\pi_{i}(s)\mid
i\in[t/2,t)\big{\\}};\end{aligned}$ (212)

in words, for any policy $\pi$ belonging to $\Pi$, each $\pi(s)$ coincides
with one of the policy iterates $\pi_{i}(s)$ during the latest $\beta t$
iterations, although we do not require all $\\{\pi(s)\\}$ across different
states to be associated with the same time stamp $i$. With this collection of
policies in place, we can deduce that

$\displaystyle\sum_{i_{1},\cdots,i_{H}}\bm{D}_{i_{1}}^{(t)}\bigg{(}\bm{I}+\sum_{h=1}^{H-1}\prod_{k=1}^{h}\big{(}\gamma\bm{P}^{\pi_{i_{k}}}\bm{D}_{i_{k+1}}^{(i_{k})}\big{)}\bigg{)}\sqrt{\bm{\varphi}_{t}}$
$\displaystyle=\sum_{i_{1},\cdots,i_{H-1}}\sum_{i_{H}}\bm{D}_{i_{1}}^{(t)}\bigg{(}\bm{I}+\sum_{h=1}^{H-2}\prod_{k=1}^{h}\big{(}\gamma\bm{P}^{\pi_{i_{k}}}\bm{D}_{i_{k+1}}^{(i_{k})}\big{)}+\prod_{k=1}^{H-2}\big{(}\gamma\bm{P}^{\pi_{i_{k}}}\bm{D}_{i_{k+1}}^{(i_{k})}\big{)}\Big{(}\gamma\bm{P}^{\pi_{i_{H-1}}}\bm{D}_{i_{H}}^{(i_{H-1})}\Big{)}\bigg{)}\sqrt{\bm{\varphi}_{t}}$
$\displaystyle=\sum_{i_{1},\cdots,i_{H-1}}\bm{D}_{i_{1}}^{(t)}\bigg{(}\bm{I}+\sum_{h=1}^{H-2}\prod_{k=1}^{h}\big{(}\gamma\bm{P}^{\pi_{i_{k}}}\bm{D}_{i_{k+1}}^{(i_{k})}\big{)}+\prod_{k=1}^{H-2}\big{(}\gamma\bm{P}^{\pi_{i_{k}}}\bm{D}_{i_{k+1}}^{(i_{k})}\big{)}\Big{(}\gamma\bm{P}^{\pi_{i_{H-1}}}\sum_{i_{H}}\bm{D}_{i_{H}}^{(i_{H-1})}\Big{)}\bigg{)}\sqrt{\bm{\varphi}_{t}}$
$\displaystyle\overset{(\mathrm{i})}{=}\sum_{i_{1},\cdots,i_{H-1}}\bm{D}_{i_{1}}^{(t)}\bigg{(}\bm{I}+\sum_{h=1}^{H-2}\prod_{k=1}^{h}\big{(}\gamma\bm{P}^{\pi_{i_{k}}}\bm{D}_{i_{k+1}}^{(i_{k})}\big{)}+\prod_{k=1}^{H-2}\big{(}\gamma\bm{P}^{\pi_{i_{k}}}\bm{D}_{i_{k+1}}^{(i_{k})}\big{)}\gamma\bm{P}^{\pi_{i_{H-1}}}\bigg{)}\sqrt{\bm{\varphi}_{t}}$
$\displaystyle\overset{(\mathrm{ii})}{\leq}\sum_{i_{1},\cdots,i_{H-1}}\bm{D}_{i_{1}}^{(t)}\bigg{(}\bm{I}+\sum_{h=1}^{H-2}\prod_{k=1}^{h}\big{(}\gamma\bm{P}^{\pi_{i_{k}}}\bm{D}_{i_{k+1}}^{(i_{k})}\big{)}+\prod_{k=1}^{H-2}\big{(}\gamma\bm{P}^{\pi_{i_{k}}}\bm{D}_{i_{k+1}}^{(i_{k})}\big{)}\gamma\bm{P}^{\widehat{\pi}_{H-1}}\bigg{)}\sqrt{\bm{\varphi}_{t}}$
$\displaystyle=\sum_{i_{1},\cdots,i_{H-2}}\bm{D}_{i_{1}}^{(t)}\bigg{(}\bm{I}+\sum_{h=1}^{H-3}\prod_{k=1}^{h}\big{(}\gamma\bm{P}^{\pi_{i_{k}}}\bm{D}_{i_{k+1}}^{(i_{k})}\big{)}+\prod_{k=1}^{H-3}\big{(}\gamma\bm{P}^{\pi_{i_{k}}}\bm{D}_{i_{k+1}}^{(i_{k})}\big{)}\gamma\bm{P}^{\pi_{i_{H-2}}}\bigg{(}\sum_{i_{H-1}}\bm{D}_{i_{H-1}}^{(i_{H-2})}\bigg{)}\big{(}\bm{I}+\gamma\bm{P}^{\widehat{\pi}_{H-1}}\big{)}\bigg{)}\sqrt{\bm{\varphi}_{t}}$
$\displaystyle\overset{(\mathrm{iii})}{=}\sum_{i_{1},\cdots,i_{H-2}}\bm{D}_{i_{1}}^{(t)}\bigg{(}\bm{I}+\sum_{h=1}^{H-3}\prod_{k=1}^{h}\big{(}\gamma\bm{P}^{\pi_{i_{k}}}\bm{D}_{i_{k+1}}^{(i_{k})}\big{)}+\prod_{k=1}^{H-3}\big{(}\gamma\bm{P}^{\pi_{i_{k}}}\bm{D}_{i_{k+1}}^{(i_{k})}\big{)}\gamma\bm{P}^{\pi_{i_{H-2}}}\big{(}\bm{I}+\gamma\bm{P}^{\widehat{\pi}_{H-1}}\big{)}\bigg{)}\sqrt{\bm{\varphi}_{t}}$
$\displaystyle\overset{(\mathrm{iv})}{\leq}\sum_{i_{1},\cdots,i_{H-2}}\bm{D}_{i_{1}}^{(t)}\bigg{(}\bm{I}+\sum_{h=1}^{H-3}\prod_{k=1}^{h}\big{(}\gamma\bm{P}^{\pi_{i_{k}}}\bm{D}_{i_{k+1}}^{(i_{k})}\big{)}+\prod_{k=1}^{H-3}\big{(}\gamma\bm{P}^{\pi_{i_{k}}}\bm{D}_{i_{k+1}}^{(i_{k})}\big{)}\gamma\bm{P}^{\widehat{\pi}_{H-2}}\big{(}\bm{I}+\gamma\bm{P}^{\widehat{\pi}_{H-1}}\big{)}\bigg{)}\sqrt{\bm{\varphi}_{t}},$

where we abbreviate $\sum_{(i_{1},\cdots,i_{H})\in\mathcal{I}_{t}}$ as
$\sum_{i_{1},\cdots,i_{H}}$ as long as it is clear from the context. Here, (i)
and (iii) arise from the second property in (206), while (ii) and (iv) are due
to the construction (211). Continuing the derivation of the above inequality
recursively, we arrive at

$\displaystyle\sum_{i_{1},\cdots,i_{H}}\bm{D}_{i_{1}}^{(t)}\bigg{(}\bm{I}+\sum_{h=1}^{H-1}\prod_{k=1}^{h}\big{(}\gamma\bm{P}^{\pi_{i_{k}}}\bm{D}_{i_{k+1}}^{(i_{k})}\big{)}\bigg{)}\sqrt{\bm{\varphi}_{t}}$
$\displaystyle\leq\bigg{(}\bm{I}+\sum_{h=1}^{H-1}\gamma^{h}\prod_{k=1}^{h}\bm{P}^{\widehat{\pi}_{k}}\bigg{)}\sqrt{\bm{\varphi}_{t}}.$

  * •

We now turn attention to the second term on the right-hand side of (209). It
is seen that

$\displaystyle\sum_{i_{1},\cdots,i_{H}}\prod_{k=1}^{H}\gamma^{H}\big{(}\bm{\Lambda}_{i_{k}+1}^{(i_{k-1})}\bm{P}^{\pi_{i_{k}}}\big{)}\big{|}\bm{\Delta}_{i_{H}}\big{|}$
$\displaystyle\leq\frac{\gamma^{H}}{1-\gamma}\sum_{i_{1},\cdots,i_{H}}\prod_{k=1}^{H}\big{(}\bm{D}_{i_{k}}^{(i_{k-1})}\bm{P}^{\pi_{i_{k}}}\big{)}\bm{1}$
$\displaystyle=\frac{\gamma^{H}}{1-\gamma}\sum_{i_{1},\cdots,i_{H-1}}\prod_{k=1}^{H-1}\big{(}\bm{D}_{i_{k}}^{(i_{k-1})}\bm{P}^{\pi_{i_{k}}}\big{)}\bigg{(}\sum_{i_{H}}\bm{D}_{i_{H}}^{(i_{H-1})}\big{(}\bm{P}^{\pi_{i_{H}}}\bm{1}\big{)}\bigg{)}$
$\displaystyle=\frac{\gamma^{H}}{1-\gamma}\sum_{i_{1},\cdots,i_{H-1}}\prod_{k=1}^{H-1}\big{(}\bm{D}_{i_{k}}^{(i_{k-1})}\bm{P}^{\pi_{i_{k}}}\big{)}\bigg{(}\sum_{i_{H}}\bm{D}_{i_{H}}^{(i_{H-1})}\bigg{)}\bm{1}$
$\displaystyle=\frac{\gamma^{H}}{1-\gamma}\sum_{i_{1},\cdots,i_{H-1}}\prod_{k=1}^{H-1}\big{(}\bm{D}_{i_{k}}^{(i_{k-1})}\bm{P}^{\pi_{i_{k}}}\big{)}\bm{1}$
$\displaystyle=\cdots=\frac{\gamma^{H}}{1-\gamma}\bm{1}=\frac{\gamma^{\frac{\log
T}{1-\gamma}}}{1-\gamma}\bm{1}$
$\displaystyle\leq\frac{1}{(1-\gamma)T}\bm{1},$

where the first line follows from the first property in (206), the third line
is due to the fact $\bm{P}^{\pi}\bm{1}=\bm{1}$ for any $\pi$, and the fourth
line arises from the second property in (206).

Substituting the above two bounds into (209) yields

$\displaystyle\bm{\Delta}_{t}$
$\displaystyle\leq\underbrace{\bigg{(}\bm{I}+\sum_{h=1}^{H-1}\gamma^{h}\prod_{k=1}^{h}\bm{P}^{\widehat{\pi}_{k}}\bigg{)}\sqrt{\bm{\varphi}_{t}}}_{\eqqcolon\,\bm{\beta}}+\frac{1}{(1-\gamma)T}\bm{1}.$
(213)

##### Step 4: putting all pieces together.

Repeating our analysis for the term $\bm{\beta}_{1}$ in Section B.2 (i.e.,
Step 5 of Section B.2 with Lemma 5 replaced by Lemma 6), we arrive at

$\displaystyle|\bm{\beta}|^{2}$
$\displaystyle\leq\frac{320\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}\Big{(}1+2\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\Big{)}\bm{1}$

with probability at least $1-\delta$. Substitution into (213) then yields

$\displaystyle\bm{\Delta}_{t}$
$\displaystyle\leq\sqrt{\frac{320\big{(}\log^{3}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T\mu_{\mathsf{min}}}\Big{(}1+\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\Big{)}}\ \bm{1}+\frac{1}{(1-\gamma)T}\bm{1}$
$\displaystyle\leq
30\sqrt{\frac{\big{(}\log^{3}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T\mu_{\mathsf{min}}}\Big{(}1+\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\Big{)}}\ \bm{1}$ (214)

holds simultaneously for all $t\geq\frac{T}{c_{4}\log T}$, provided that the
sample size condition (46b) is satisfied. Similarly, we can also establish the
following lower bound on $\bm{\Delta}_{t}$ (which we omit the details for the
sake of brevity)

$\displaystyle\bm{\Delta}_{t}\geq-30\sqrt{\frac{\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T\mu_{\mathsf{min}}}\Big{(}1+\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\Big{)}}\ \bm{1}$

with probability at least $1-\delta$. To summarize, it is seen that with
probability exceeding $1-2\delta$,

$\displaystyle\|\bm{\Delta}_{t}\|_{\infty}\leq
30\sqrt{\frac{\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T\mu_{\mathsf{min}}}\Big{(}1+\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\Big{)}}.$ (215)

This resembles the relation (35) derived for the synchronous case, except that
$T$ in the denominator is replaced with $\mu_{\mathsf{min}}T$. As a result, we
can readily repeat the argument in Appendix B.4 to reach

$\displaystyle\|\bm{\Delta}_{T}\|_{\infty}\leq
O\bigg{(}\sqrt{\frac{\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)^{4}T\mu_{\mathsf{min}}}}+\frac{\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)^{4}T\mu_{\mathsf{min}}}\bigg{)},$
(216)

which in turn establishes the claimed result in Theorem 4.

###  E.3 Proofs of technical lemmas

####  E.3.1 Proof of Lemma 8

In view of the definition of $\bm{\zeta}_{t}$ in (200) and the fact that
$\bm{\Lambda}_{0}^{(t)}$ is a diagonal matrix, we can deduce that

$\displaystyle\|\bm{\zeta}_{t}\|_{\infty}$
$\displaystyle\leq\|\bm{\Lambda}_{0}^{(t)}\|\|\bm{\Delta}_{0}\|_{\infty}+t\max_{1\leq
i\leq(1-\beta)t}\|\bm{\Lambda}_{i}^{(t)}\|\max_{1\leq
i\leq(1-\beta)t}\big{(}\|\bm{P}^{\pi_{i-1}}\bm{\Delta}_{i-1}\|_{\infty}+\|\bm{P}_{i}\bm{V}_{i-1}\|_{\infty}+\|\bm{P}\bm{V}_{i-1}\|_{\infty}\big{)}$
$\displaystyle\leq\|\bm{\Lambda}_{0}^{(t)}\|\|\bm{\Delta}_{0}\|_{\infty}+t\max_{1\leq
i\leq(1-\beta)t}\|\bm{\Lambda}_{i}^{(t)}\|\max_{1\leq
i\leq(1-\beta)t}\Big{\\{}\|\bm{P}^{\pi_{i-1}}\|_{1}\|\bm{\Delta}_{i-1}\|_{\infty}+\big{(}\|\bm{P}_{i}\|_{1}+\|\bm{P}\|_{1}\big{)}\|\bm{V}_{i-1}\|_{\infty}\Big{\\}}$
$\displaystyle\overset{(\mathrm{i})}{=}\|\bm{\Lambda}_{0}^{(t)}\|\|\bm{\Delta}_{0}\|_{\infty}+t\max_{1\leq
i\leq(1-\beta)t}\|\bm{\Lambda}_{i}^{(t)}\|\max_{1\leq
i\leq(1-\beta)t}\big{(}\|\bm{\Delta}_{i-1}\|_{\infty}+2\,\|\bm{V}_{i-1}\|_{\infty}\big{)}$
$\displaystyle\overset{(\mathrm{ii})}{\leq}\frac{1}{T^{2}}\cdot\frac{1}{1-\gamma}+\frac{1}{T^{2}}\cdot
t\cdot\frac{3}{1-\gamma}$ $\displaystyle\leq\frac{4}{(1-\gamma)T}.$

Here, (i) holds true since
$\|\bm{P}^{\pi_{i-1}}\|_{1}=\|\bm{P}_{i}\|_{1}=\|\bm{P}\|_{1}=1$. To verify
(ii), we first define

$t_{k}(s,a)\coloneqq\text{the time stamp when }\text{the trajectory visits
}(s,a)\text{ for the }k\text{-th time}$ (217)

and

$K_{t}(s,a)\coloneqq\Big{|}\big{\\{}k\geq 1\mid t_{k}(s,a)<t\big{\\}}\Big{|},$
(218)

namely, the total number of times — before the $t$-th iteration — that the
sample trajectory visits $(s,a)$. Then Li et al., 2021b (, Lemma 8) tells us
that with probability at least $1-\delta$,

$\displaystyle
K_{t_{1}}(s,a)-K_{t_{2}}(s,a)\geq\frac{1}{2}(t_{1}-t_{2})\mu_{\mathsf{min}},$
(219)

holds uniformly for all $(s,a)\in\mathcal{S}\times\mathcal{A}$ and $0\leq
t_{2}\leq t_{1}\leq T$ obeying

$t_{1}-t_{2}\geq\frac{886t_{\mathsf{mix}}}{\mu_{\mathsf{min}}}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}.$

This in turn implies that: if $\beta
t\geq\frac{886t_{\mathsf{mix}}}{\mu_{\mathsf{min}}}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}$
and $i\leq(1-\beta)t$, then one has

$\displaystyle\|\bm{\Lambda}_{0}^{(t)}\|$
$\displaystyle=\bigg{\|}\prod_{j=1}^{t}\big{(}\bm{I}-\bm{\Lambda}_{j}\big{)}\bigg{\|}=\max_{(s,a)\in\mathcal{S}\times\mathcal{A}}(1-\eta)^{K_{t}(s,a)}\leq(1-\eta)^{\frac{1}{2}t\mu_{\mathsf{min}}}\leq\frac{1}{T^{2}}$
(220a) $\displaystyle\|\bm{\Lambda}_{i}^{(t)}\|$
$\displaystyle=\bigg{\|}\bm{\Lambda}_{i}\prod_{j=i+1}^{t}(\bm{I}-\bm{\Lambda}_{j})\bigg{\|}\leq\max_{(s,a)}(1-\eta)^{K_{t}(s,a)-K_{i}(s,a)}\leq(1-\eta)^{\frac{1}{2}\beta
t\mu_{\mathsf{min}}}\leq\frac{1}{T^{2}}$ (220b)

with probability at least $1-\delta$, provided that $\eta\beta
t\mu_{\mathsf{min}}>4\log T$. In other words, (220) holds with probability at
least $1-\delta$, as long as

$t>\max\left\\{\frac{4\log
T}{\eta\beta\mu_{\mathsf{min}}},\,\frac{886t_{\mathsf{mix}}}{\beta\mu_{\mathsf{min}}}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\right\\}=\max\left\\{\frac{4T}{c_{1}c_{3}\log
T},\,\frac{886t_{\mathsf{mix}}}{c_{3}(1-\gamma)\mu_{\mathsf{min}}}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\log
T\right\\}.$

This taken together with the sample size assumption (46b) concludes the proof
of Lemma 8.

####  E.3.2 Proof of Lemma 9

Fix any state-action pair $(s,a)\in\mathcal{S}\times\mathcal{A}$, and let us
look at the $(s,a)$-th entry of $\bm{\xi}_{t}$, i.e., $\xi_{t}(s,a)$. For
notational simplicity, let $\bm{\Lambda}_{j}(s,a)$ denote the $(s,a)$-th
diagonal entry of the diagonal matrix $\bm{\Lambda}_{j}$, and
$\bm{P}_{t}(s,a)$ (resp. $\bm{P}(s,a)$) the $(s,a)$-th row of $\bm{P}_{t}$
(resp. $\bm{P}$).

Using the definition of $\bm{\xi}_{t}$ in (200) and the above notation, we can
derive

$\displaystyle\xi_{t}(s,a)$
$\displaystyle=\gamma\sum_{i=(1-\beta)t+1}^{t}\prod_{j=i+1}^{t}\big{(}1-\bm{\Lambda}_{j}(s,a)\big{)}\bm{\Lambda}_{i}(s,a)\big{(}\bm{P}_{i}(s,a)-\bm{P}(s,a)\big{)}\bm{V}_{i-1}.$
(221)

Equipped with the definitions of $t_{k}(s,a)$ (cf. (217)) and $K_{t}(s,a)$
(cf. (218)), we can further rewrite (221) as

$\displaystyle\xi_{t}(s,a)$
$\displaystyle=\gamma\sum_{k=K_{(1-\beta)t+1}}^{K_{t}(s,a)}(1-\eta)^{K_{t}(s,a)-k}\eta\big{(}\bm{P}_{t_{k}+1}(s,a)-\bm{P}(s,a)\big{)}\bm{V}_{t_{k}}.$
(222)

In what follows, we shall suppress the notation and write $t_{k}=t_{k}(s,a)$
and $K_{t}=K_{t}(s,a)$ to streamline notation.

The main step thus boils down to controlling (222). Towards this, we claim
that: with probability at least $1-\delta$,

$\displaystyle\Bigg{|}\sum_{k=K_{\beta}}^{K}(1-\eta)^{K-k}\eta\big{(}\bm{P}_{t_{k}+1}(s,a)-\bm{P}(s,a)\big{)}\bm{V}_{t_{k}}\Bigg{|}$
$\displaystyle\qquad\leq\sqrt{\frac{16\big{(}\log^{3}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)T\mu_{\mathsf{min}}}\Big{(}\max_{t_{K_{\beta}}\leq
i\leq
t_{K}}\mathsf{Var}_{\bm{P}(s,a)}(\bm{V}_{i})+1\Big{)}}+\frac{6\big{(}\log^{3}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)^{2}T\mu_{\mathsf{min}}}$
(223)

holds simultaneously for all $(s,a)\in\mathcal{S}\times\mathcal{A}$ and all
$1\leq K_{\beta}\leq K\leq T$, provided that
$0<\eta\leq\frac{\log^{3}T}{(1-\gamma)T\mu_{\mathsf{min}}}$. If this claim
were true, then taking $K_{\beta}=K_{(1-\beta)t+1}$ and $K=K_{t}$ and
substituting the bound (223) into the expression (222) would lead to

$\displaystyle|\bm{\xi}_{t}|\leq\sqrt{\frac{16\big{(}\log^{3}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)T\mu_{\mathsf{min}}}\Big{(}\max_{(1-\beta)t\leq
i<t}\mathsf{Var}_{\bm{P}}(\bm{V}_{i})+\bm{1}\Big{)}}+\frac{6\big{(}\log^{3}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)^{2}T\mu_{\mathsf{min}}}\bm{1},$
(224)

thus concluding the proof of this lemma. To finish up, it is sufficient to
justify the claim (223), which forms the content of the remainder of this
proof.

###### Proof of the claim (223).

Let us use the notation in (57) to express
$\eta_{k}^{(K)}=(1-\eta)^{K-k}\eta$. For any fixed integer $K>0$, the
following vectors

$\left\\{\bm{P}_{t_{k}+1}(s,a)\mid 1\leq k\leq K\right\\}$

are identically and independently distributed; see Li et al., 2021b (, Section
B.1). We can then express the term

$X_{K}\coloneqq\sum_{k=K_{\beta}}^{K}(1-\eta)^{K-k}\eta\big{(}\bm{P}_{t_{k}+1}(s,a)-\bm{P}(s,a)\big{)}\bm{V}_{t_{k}},$

as follows:

$X_{K}=\sum_{k=K_{\beta}}^{K}z_{k}\qquad\text{with
}z_{k}\coloneqq\eta_{k}^{(K)}\big{(}\bm{P}_{t_{k}+1}(s,a)-\bm{P}(s,a)\big{)}\bm{V}_{t_{k}},$

where the $z_{k}$’s satisfy

$\mathbb{E}\left[z_{k}\,|\,t_{k},\cdots,t_{1},\bm{V}_{t_{k}},\cdots,\bm{V}_{t_{1}}\right]=0.$

We intend to invoke the Freedman inequality to control $X_{K}$ for any $K$
obeying $K\leq T$. Similar to the synchronous counterpart, we can see that

$\displaystyle B$ $\displaystyle\coloneqq\max_{1<k\leq
K}\|z_{k}\|_{\infty}\leq\eta_{k}^{K}\big{(}\big{\|}\bm{P}_{t_{k}+1}\|_{1}+\|\bm{P}\|_{1}\big{)}\big{\|}\bm{V}_{t_{k}}\|_{\infty}\leq\frac{2\eta_{k}^{K}}{1-\gamma}\leq\frac{2\eta}{1-\gamma},$
$\displaystyle W$
$\displaystyle\coloneqq\sum_{k=K_{\beta}}^{K}\mathsf{Var}\big{(}z_{k}\,|\,t_{k},\cdots,t_{1},\bm{V}_{t_{k}},\cdots,\bm{V}_{t_{1}}\big{)}=\gamma^{2}\sum_{k=K_{\beta}}^{K}\big{(}\eta_{k}^{(K)}\big{)}^{2}\mathsf{Var}\big{(}(\bm{P}_{t_{k}+1}-\bm{P})\bm{V}_{t_{k}}\mid\bm{V}_{t_{k}}\big{)}$
$\displaystyle\leq\sum_{k=K_{\beta}}^{K}\big{(}\eta_{k}^{(K)}\big{)}^{2}\mathsf{Var}_{\bm{P}(s,a)}\big{(}\bm{V}_{t_{k}}\big{)}\leq\Big{(}\max_{K_{\beta}\leq
k\leq
K}\eta_{k}^{(K)}\Big{)}\bigg{(}\sum_{k=K_{\beta}}^{K}\eta_{k}^{(K)}\bigg{)}\mathsf{Var}_{\bm{P}(s,a)}\big{(}\bm{V}_{t_{k}}\big{)}$
$\displaystyle\leq\eta\max_{K_{\beta}\leq k\leq
K}\mathsf{Var}_{\bm{P}(s,a)}\big{(}\bm{V}_{t_{k}}\big{)}\leq\eta\max_{t_{K_{\beta}}\leq
i\leq t_{K}}\mathsf{Var}_{\bm{P}(s,a)}\big{(}\bm{V}_{i}\big{)},$

where we have made use of (62). In addition, we make note of a trivial upper
bound on $W$ as follows

$\displaystyle\sigma^{2}$
$\displaystyle:=\frac{\eta}{(1-\gamma)^{2}}\geq\eta\max_{t_{K_{\beta}}\leq
i\leq t_{K}}\mathsf{Var}_{\bm{P}(s,a)}\big{(}\bm{V}_{i}\big{)}\geq W_{t}.$

With the preceding bounds in place, applying the Freedman inequality in
Theorem 5 and taking $L=\log_{2}\frac{1}{1-\gamma}$ imply that

$\displaystyle|X_{K}|$
$\displaystyle\leq\sqrt{8\max\bigg{\\{}W,\frac{\sigma^{2}}{2^{L}}\bigg{\\}}\log\frac{4|\mathcal{S}||\mathcal{A}|T^{2}\log_{2}\frac{1}{1-\gamma}}{\delta}}+\frac{8\eta}{3(1-\gamma)}\log\frac{4|\mathcal{S}||\mathcal{A}|T^{2}\log_{2}\frac{1}{1-\gamma}}{\delta}$
$\displaystyle\leq\sqrt{8\eta\max\Big{\\{}\max_{t_{K_{\beta}}\leq i\leq
t_{K}}\mathsf{Var}_{\bm{P}(s,a)}(\bm{V}_{i}),1\Big{\\}}\log\frac{4|\mathcal{S}||\mathcal{A}|T^{2}\log_{2}\frac{1}{1-\gamma}}{\delta}}+\frac{8\eta}{3(1-\gamma)}\log\frac{4|\mathcal{S}||\mathcal{A}|T^{2}\log_{2}\frac{1}{1-\gamma}}{\delta}$
$\displaystyle\leq\sqrt{\frac{16\big{(}\log^{3}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)T\mu_{\mathsf{min}}}\Big{(}\max_{t_{K_{\beta}}\leq
i\leq
t_{K}}\mathsf{Var}_{\bm{P}(s,a)}(\bm{V}_{i})+1\Big{)}}+\frac{6\big{(}\log^{3}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)^{2}T\mu_{\mathsf{min}}}$

with probability at least $1-\frac{\delta}{|\mathcal{S}||\mathcal{A}|T^{2}}$,
provided that $\eta\leq\frac{\log^{3}T}{(1-\gamma)T\mu_{\mathsf{min}}}$. We
can thus conclude the proof by taking the union bound over all
$(s,a)\in\mathcal{S}\times\mathcal{A}$ and all $1\leq K_{\beta}\leq K\leq T$.
∎

## References

  * Agarwal et al., (2020) Agarwal, A., Kakade, S., and Yang, L. F. (2020).  Model-based reinforcement learning with a generative model is minimax optimal.  Conference on Learning Theory, pages 67–83.
  * Azar et al., (2011) Azar, M. G., Munos, R., Ghavamzadeh, M., and Kappen, H. (2011).  Reinforcement learning with a near optimal rate of convergence.  Technical report, INRIA.
  * Azar et al., (2013) Azar, M. G., Munos, R., and Kappen, H. J. (2013).  Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model.  Machine learning, 91(3):325–349.
  * Bai et al., (2019) Bai, Y., Xie, T., Jiang, N., and Wang, Y.-X. (2019).  Provably efficient $q$-learning with low switching cost.  In Advances in Neural Information Processing Systems, pages 8002–8011.
  * Beck and Srikant, (2012) Beck, C. L. and Srikant, R. (2012).  Error bounds for constant step-size Q-learning.  Systems & control letters, 61(12):1203–1208.
  * Bellman, (1952) Bellman, R. (1952).  On the theory of dynamic programming.  Proceedings of the National Academy of Sciences of the United States of America, 38(8):716.
  * Bertsekas, (2017) Bertsekas, D. P. (2017).  Dynamic programming and optimal control (4th edition).  Athena Scientific.
  * Bhandari et al., (2018) Bhandari, J., Russo, D., and Singal, R. (2018).  A finite time analysis of temporal difference learning with linear function approximation.  In Conference On Learning Theory, pages 1691–1692.
  * Bhandari et al., (2021) Bhandari, J., Russo, D., and Singal, R. (2021).  A finite time analysis of temporal difference learning with linear function approximation.  Operations Research.
  * Borkar and Meyn, (2000) Borkar, V. S. and Meyn, S. P. (2000).  The ODE method for convergence of stochastic approximation and reinforcement learning.  SIAM Journal on Control and Optimization, 38(2):447–469.
  * Cai et al., (2019) Cai, Q., Yang, Z., Lee, J. D., and Wang, Z. (2019).  Neural temporal-difference and Q-learning converges to global optima.  In Advances in Neural Information Processing Systems, pages 11312–11322.
  * Chen et al., (2020) Chen, Z., Maguluri, S. T., Shakkottai, S., and Shanmugam, K. (2020).  Finite-sample analysis of stochastic approximation using smooth convex envelopes.  arXiv preprint arXiv:2002.00874.
  * Chen et al., (2021) Chen, Z., Maguluri, S. T., Shakkottai, S., and Shanmugam, K. (2021).  A Lyapunov theory for finite-sample guarantees of asynchronous Q-learning and TD-learning variants.  arXiv preprint arXiv:2102.01567.
  * Chen et al., (2019) Chen, Z., Zhang, S., Doan, T. T., Maguluri, S. T., and Clarke, J.-P. (2019).  Performance of Q-learning with linear function approximation: Stability and finite-time analysis.  arXiv preprint arXiv:1905.11425.
  * Devraj and Meyn, (2020) Devraj, A. M. and Meyn, S. P. (2020).  Q-learning with uniformly bounded variance: Large discounting is not a barrier to fast learning.  arXiv preprint arXiv:2002.10301.
  * Doan et al., (2019) Doan, T., Maguluri, S., and Romberg, J. (2019).  Finite-time analysis of distributed TD(0) with linear function approximation on multi-agent reinforcement learning.  In International Conference on Machine Learning, pages 1626–1635. PMLR.
  * Even-Dar and Mansour, (2003) Even-Dar, E. and Mansour, Y. (2003).  Learning rates for Q-learning.  Journal of machine learning Research, 5(Dec):1–25.
  * Fan et al., (2019) Fan, J., Wang, Z., Xie, Y., and Yang, Z. (2019).  A theoretical analysis of deep Q-learning.  arXiv preprint arXiv:1901.00137.
  * Freedman, (1975) Freedman, D. A. (1975).  On tail probabilities for martingales.  the Annals of Probability, pages 100–118.
  * Gupta et al., (2019) Gupta, H., Srikant, R., and Ying, L. (2019).  Finite-time performance bounds and adaptive learning rate selection for two time-scale reinforcement learning.  In Advances in Neural Information Processing Systems, pages 4706–4715.
  * Hasselt, (2010) Hasselt, H. (2010).  Double Q-learning.  Advances in neural information processing systems, 23:2613–2621.
  * Jaakkola et al., (1994) Jaakkola, T., Jordan, M. I., and Singh, S. P. (1994).  Convergence of stochastic iterative dynamic programming algorithms.  In Advances in neural information processing systems, pages 703–710.
  * Jin et al., (2018) Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. (2018).  Is Q-learning provably efficient?  In Advances in Neural Information Processing Systems, pages 4863–4873.
  * Kakade, (2003) Kakade, S. (2003).  On the sample complexity of reinforcement learning.  PhD thesis, University of London.
  * Kearns et al., (2002) Kearns, M., Mansour, Y., and Ng, A. Y. (2002).  A sparse sampling algorithm for near-optimal planning in large Markov decision processes.  Machine learning, 49(2-3):193–208.
  * Kearns and Singh, (1999) Kearns, M. J. and Singh, S. P. (1999).  Finite-sample convergence rates for Q-learning and indirect algorithms.  In Advances in neural information processing systems, pages 996–1002.
  * Khamaru et al., (2020) Khamaru, K., Pananjady, A., Ruan, F., Wainwright, M. J., and Jordan, M. I. (2020).  Is temporal difference learning optimal? an instance-dependent analysis.  arXiv preprint arXiv:2003.07337.
  * Khamaru et al., (2021) Khamaru, K., Pananjady, A., Ruan, F., Wainwright, M. J., and Jordan, M. I. (2021).  Is temporal difference learning optimal? an instance-dependent analysis.  SIAM Journal on Mathematics of Data Science, 3(4):1013–1040.
  * Lakshminarayanan and Szepesvari, (2018) Lakshminarayanan, C. and Szepesvari, C. (2018).  Linear stochastic approximation: How far does constant step-size and iterate averaging go?  In International Conference on Artificial Intelligence and Statistics, pages 1347–1355.
  * Lee and He, (2018) Lee, D. and He, N. (2018).  Stochastic primal-dual Q-learning.  arXiv preprint arXiv:1810.08298.
  * (31) Li, G., Shi, L., Chen, Y., Gu, Y., and Chi, Y. (2021a).  Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning.  Neural Information Processing Systems (NeurIPS).
  * Li et al., (2020) Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2020).  Breaking the sample size barrier in model-based reinforcement learning with a generative model.  Advances in Neural Information Processing Systems, 33.
  * (33) Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2021b).  Sample complexity of asynchronous Q-learning: Sharper analysis and variance reduction.  IEEE Transactions on Information Theory.
  * Mou et al., (2020) Mou, W., Li, C. J., Wainwright, M. J., Bartlett, P. L., and Jordan, M. I. (2020).  On linear stochastic approximation: Fine-grained Polyak-Ruppert and non-asymptotic concentration.  arXiv preprint arXiv:2004.04719.
  * Murphy, (2005) Murphy, S. (2005).  A generalization error for Q-learning.  Journal of Machine Learning Research, 6:1073–1097.
  * Pananjady and Wainwright, (2020) Pananjady, A. and Wainwright, M. J. (2020).  Instance-dependent $\ell_{\infty}$-bounds for policy evaluation in tabular reinforcement learning.  IEEE Transactions on Information Theory, 67(1):566–585.
  * Paulin, (2015) Paulin, D. (2015).  Concentration inequalities for Markov chains by Marton couplings and spectral methods.  Electronic Journal of Probability, 20.
  * Qu and Wierman, (2020) Qu, G. and Wierman, A. (2020).  Finite-time analysis of asynchronous stochastic approximation and Q-learning.  Conference on Learning Theory, pages 3185–3205.
  * Robbins and Monro, (1951) Robbins, H. and Monro, S. (1951).  A stochastic approximation method.  The annals of mathematical statistics, pages 400–407.
  * Shah and Xie, (2018) Shah, D. and Xie, Q. (2018).  Q-learning with nearest neighbors.  In Advances in Neural Information Processing Systems, pages 3111–3121.
  * Sidford et al., (2018) Sidford, A., Wang, M., Wu, X., Yang, L., and Ye, Y. (2018).  Near-optimal time and sample complexities for solving Markov decision processes with a generative model.  In Advances in Neural Information Processing Systems, pages 5186–5196.
  * Srikant and Ying, (2019) Srikant, R. and Ying, L. (2019).  Finite-time error bounds for linear stochastic approximation and TD learning.  In Conference on Learning Theory, pages 2803–2830.
  * Sutton, (1988) Sutton, R. S. (1988).  Learning to predict by the methods of temporal differences.  Machine learning, 3(1):9–44.
  * Sutton and Barto, (2018) Sutton, R. S. and Barto, A. G. (2018).  Reinforcement learning: An introduction.  MIT press.
  * Szepesvári, (1998) Szepesvári, C. (1998).  The asymptotic convergence-rate of Q-learning.  In Advances in Neural Information Processing Systems, pages 1064–1070.
  * Tropp, (2011) Tropp, J. (2011).  Freedman’s inequality for matrix martingales.  Electronic Communications in Probability, 16:262–270.
  * Tsitsiklis and Van Roy, (1997) Tsitsiklis, J. and Van Roy, B. (1997).  An analysis of temporal-difference learning with function approximation.  IEEE Transactions on Automatic Control, 42(5):674–690.
  * Tsitsiklis, (1994) Tsitsiklis, J. N. (1994).  Asynchronous stochastic approximation and Q-learning.  Machine learning, 16(3):185–202.
  * Tsybakov and Zaiats, (2009) Tsybakov, A. B. and Zaiats, V. (2009).  Introduction to nonparametric estimation, volume 11.  Springer.
  * Wai et al., (2019) Wai, H.-T., Hong, M., Yang, Z., Wang, Z., and Tang, K. (2019).  Variance reduced policy evaluation with smooth function approximation.  Advances in Neural Information Processing Systems, 32:5784–5795.
  * (51) Wainwright, M. (2019a).  High-Dimensional Statistics: A Non-Asymptotic Viewpoint.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press.
  * (52) Wainwright, M. J. (2019b).  Stochastic approximation with cone-contractive operators: Sharp $\ell_{\infty}$-bounds for Q-learning.  arXiv preprint arXiv:1905.06265.
  * (53) Wainwright, M. J. (2019c).  Variance-reduced Q-learning is minimax optimal.  arXiv preprint arXiv:1906.04697.
  * Watkins and Dayan, (1992) Watkins, C. J. and Dayan, P. (1992).  Q-learning.  Machine learning, 8(3-4):279–292.
  * Watkins, (1989) Watkins, C. J. C. H. (1989).  Learning from delayed rewards.
  * (56) Weng, B., Xiong, H., Zhao, L., Liang, Y., and Zhang, W. (2020a).  Momentum Q-learning with finite-sample convergence guarantee.  arXiv preprint arXiv:2007.15418.
  * (57) Weng, W., Gupta, H., He, N., Ying, L., and Srikant, R. (2020b).  The mean-squared error of double Q-learning.  Advances in Neural Information Processing Systems, 33.
  * Wu et al., (2020) Wu, Y., Zhang, W., Xu, P., and Gu, Q. (2020).  A finite time analysis of two time-scale actor critic methods.  arXiv preprint arXiv:2005.01350.
  * Xiong et al., (2020) Xiong, H., Zhao, L., Liang, Y., and Zhang, W. (2020).  Finite-time analysis for double Q-learning.  Advances in Neural Information Processing Systems, 33.
  * Xu and Gu, (2020) Xu, P. and Gu, Q. (2020).  A finite-time analysis of Q-learning with neural network function approximation.  In International Conference on Machine Learning, pages 10555–10565. PMLR.
  * (61) Xu, T., Wang, Z., Zhou, Y., and Liang, Y. (2019a).  Reanalysis of variance reduced temporal difference learning.  In International Conference on Learning Representations.
  * (62) Xu, T., Zou, S., and Liang, Y. (2019b).  Two time-scale off-policy TD learning: Non-asymptotic analysis over Markovian samples.  In Advances in Neural Information Processing Systems, pages 10633–10643.
  * Zhang et al., (2020) Zhang, Z., Zhou, Y., and Ji, X. (2020).  Almost optimal model-free reinforcement learningvia reference-advantage decomposition.  Advances in Neural Information Processing Systems, 33.