Substitution of this into (<ref>) leads to the desired result (<ref>).

§.§ Proof of Inequality (<ref>)

Similar to the proof of (<ref>), it suffices to examine the following term in order to prove (<ref>):

\begin{align}
I_4 := \sum_{n = 1}^{N_t} \eta^{N_t}_n\Var_{s_t,a_t}\left({V}^{\rref}_{t_n}\right) - {\sigma}^{\re}_{t_{N_t}+1}(s_t,a_t) + \left({\mu}^{\re}_{ t_{N_t}+1}(s_t,a_t) \right)^2.
\label{eq:I4-def}
\end{align}

In this section, we would like to show an upper bound on $I_4$.

Before we proceed, recall that the update rules of $\mu^{\re}_{t_{n+1}}$ and ${\sigma}^{\re}_{t_{n+1}}$ in Line <ref> and <ref> of Algorithm <ref> are

\begin{align*}
{\mu}^{\re}_{t_{n+1}}(s_t,a_t) &= {\mu}^{\re}_{t_n+1}(s_t,a_t) = \left(1-\frac{1}{n}\right){\mu}^{\re}_{t_n}(s_t,a_t) + \frac{1}{n}{V}^{\rref}_{t_n}(s_{t_n+1}), \\
{\sigma}^{\re}_{t_{n+1}}(s_t,a_t) &= {\sigma}^{\re}_{t_n+1}(s_t,a_t) = \left(1-\frac{1}{n}\right){\sigma}^{\re}_{t_n}(s_t,a_t) + \frac{1}{n}\left({V}^{\rref}_{t_n}(s_{t_n+1})\right)^2,
\end{align*}

We can expand these equations recursively and write

\begin{align}
{\mu}^{\re}_{t_{N_{t}}+1}(s_t,a_t) & = \frac{1}{N_{t}}\sum_{n=1}^{N_{t}}{V}_{t_n}^{\rref}(s_{t_{n}+1}) = \frac{1}{N_{t}}\sum_{n=1}^{N_{t}} P_{t_n}{V}_{t_n}^{\rref}, \label{eq:I4-1.1}\\
{\sigma}^{\re}_{t_{N_{t}}+1}(s_t,a_t) & = \frac{1}{N_{t}}\sum_{n=1}^{N_{t}}\left({V}_{t_n}^{\rref}(s_{t_{n}+1})\right)^2 = \frac{1}{N_{t}}\sum_{n=1}^{N_{t}} P_{t_n}\left({V}_{t_n}^{\rref}\right)^2. \label{eq:I4-1.2}
\end{align}

Noting that $\sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}=1$, we can use Jensen's inequality and reason from (<ref>) and (<ref>) that:

\begin{align}\label{eq:I4-2}
{\sigma}^{\re}_{t_{N_{t}}+1}(s_t,a_t) \geq \left({\mu}^{\re}_{t_{N_{t}}+1}(s_t,a_t)\right)^2.
\end{align}

Recall by the definition of variance in (<ref>), we have

\begin{equation*}
\Var_{s_t,a_t}\left({V}^{\rref}_{t_n} \right)
= P_{s_t,a_t} \left({V}^{\rref}_{t_n}\right)^{2} - \left(P_{s_t,a_t} \left({V}^{\rref}_{t_n} \right) \right)^2.
\end{equation*}

Combined this with (<ref>), we can decompose $I_4$ as follows

\begin{align}
I_4 & = \frac{1}{{N_t}}\sum_{n=1}^{N_t} \left(P_{s_t,a_t} \left({V}^{\rref}_{t_n}\right)^{2} - \left(P_{s_t,a_t} \left({V}^{\rref}_{t_n} \right) \right)^2\right) - \frac{1}{N_{t}}\sum_{n=1}^{N_{t}} P_{t_n}\left({V}_{t_n}^{\rref}\right)^2 + \left(\frac{1}{N_{t}}\sum_{n=1}^{N_{t}} P_{t_n}{V}_{t_n}^{\rref}\right)^2 \nonumber \\
& = \underbrace{ \frac{1}{{N_t}}\sum_{n = 1}^{{N_t}} \left(P_{s_t,a_t} - P_{t_n}\right) \left({V}^{\rref}_{t_n}\right)^2 }_{:= \, I_{4,1}} + \underbrace{ \left(\frac{1}{N_{t}}\sum_{n=1}^{N_{t}} P_{t_n}{V}_{t_n}^{\rref}\right)^2 - \frac{1}{{N_t}}\sum_{n = 1}^{{N_t}} \left(P_{s_t,a_t} {V}^{\rref}_{t_n}\right)^2}_{:=\, I_{4,2}}. \label{eq:I4-3}
\end{align}

It remains to control $I_{4,1}$ and $I_{4,2}$ in (<ref>) separately.

Step 1: controlling $I_{4,1}$.

Now, let us control $I_{4,1}$ defined in (<ref>) by invoking Lemma <ref>. Consider any $N\in[T]$. We set

\begin{align}
W_i := \left({V}^{\rref}_{i} \right)^{ 2}
\qquad \text{and} \qquad
u_i(s,a, N) := \frac{1}{N}.
\label{I41-def1}
\end{align}

Moreover, define

\begin{align}
|u_i(s,a, N)| = \frac{1}{N} := C_{\mathrm{u}}
\qquad \text{and} \qquad \norm{W_i}_\infty \leq  \norm{V_{i}^\rref}_\infty^2
\leq \frac{1}{(1-\gamma)^2}:= C_{\mathrm{w}}. \label{I41-cw-cu}
\end{align}

Clearly, we can verify

\begin{align}
\sum_{n=1}^{N} u_{t_{n}(s,a)}(s,a, N)= \sum_{n=1}^{N}\frac{1}{N}=1
\end{align}

holds for all $(N,s,a) \in [T] \times \cS\times \cA$, and the conditions for Lemma <ref> are satisfied.

Therefore, we can apply Lemma <ref> with (<ref>), (<ref>) and $(N,s,a)=(N_t,s_t, a_t)$ and conclude with probability at least $1-\delta$,

\begin{align}
|I_{4,1}| &= \left|\sum_{n = 1}^{{N_t}} \eta_n^{N_t} \left(P_{t_n}-P_{s_t,a_t} \right)\left({V}^{\rref}_{t_n}\right)^2\right| \notag\\
&= \left|\sum_{i=1}^t X_i(s_t,a_t,N_t)\right| \nonumber\\
&\lesssim \sqrt{C_{\mathrm{u}} \log^2\frac{SAT}{\delta}}\sqrt{\sum_{n = 1}^{N_t} u_{t_n}(s_t,a_t, N_t) \Var_{s_t,a_t} \left(W_{t_n} \right)} + \left(C_{\mathrm{u}} C_{\mathrm{w}} + \sqrt{\frac{C_{\mathrm{u}}}{N}} C_{\mathrm{w}}\right) \log^2\frac{SAT}{\delta} \nonumber \\
&\lesssim  \sqrt{\frac{\log^2 \frac{SAT}{\delta}}{{N_t(1-\gamma)^4}}} + \frac{\log^2\frac{SAT}{\delta}}{{N_t(1-\gamma)^2}}, \label{eq:I41-final}
\end{align}

in which the last inequality results from $\sum_{n = 1}^{N_t} \eta^{N_t}_n \leq 1$ and the fact $\Var_{s_t,a_t}\left(\left(V^{\rref}_{t_n} \right)^2\right)
\leq \norm{\left({V}^{\rref}_{t_n}  \right)^{4}}_\infty
\leq \frac{1}{(1-\gamma)^4}$.

Step 2: controlling $I_{4,2}$.

We can use Jensen's inequality and write $I_{4,2}$ as

\begin{align}
I_{4,2} &= \left(\sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}P_{t_{n}} {V}^{\rref}_{t_n}\right)^2 - \sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}\left(P_{s_t,a_t}{V}^{\rref}_{t_n}\right)^2 \notag\\
&\le \left(\sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}P_{t_{n}}{V}^{\rref}_{t_n}\right)^2 - \left\{\sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}\right\} \left\{ \sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}\left(P_{s_t,a_t}{V}^{\rref}_{t_n}\right)^2\right\} \notag\\
&\le \left(\sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}P_{t_{n}}{V}^{\rref}_{t_n}\right)^2 - \left(\sum_{n=1}^{{N_{t}}}\left(\eta_{n}^{N_{t}}\right)^{1/2} \left(\eta_{n}^{N_{t}}\right)^{1/2}P_{s_t,a_t}{V}^{\rref}_{t_n}\right)^2 \notag\\
&= \left(\sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}P_{t_{n}}{V}^{\rref}_{t_n}\right)^2  - \left(\sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}P_{s_t,a_t}{V}^{\rref}_{t_n}\right)^2 \notag\\
&\le \left\{\sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}\left(P_{t_{n}} - P_{s_t,a_t}\right){V}^{\rref}_{t_n}\right\} \left\{\sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}\left(P_{t_{n}} + P_{s_t,a_t}\right){V}^{\rref}_{t_n}\right\}. \label{eq:I42-1}
\end{align}

With this upper bound on $I_{4,2}$, we now aim to show

\begin{equation} \label{eq:I42-WTS}
I_{4,2} \leq C_{4,2} \left( \sqrt{\frac{1}{{N_t}(1-\gamma)^4}\log^2\frac{SAT}{\delta}} + \frac{1}{{N_t(1-\gamma)^2}} \log^2\frac{SAT}{\delta}\right),
\end{equation}

for some universal constant $C_{4,2}>0$.

Since (<ref>) is trivially true if $I_{4,2}\leq 0$, it suffices to consider the case where $I_{4,2}> 0$ only. To proceed, we use Lemma <ref> on the first factor in the product in (<ref>). Let us abuse the notation and set

\begin{align*}
W_i := {V}^{\rref}_{i} \qquad \text{and} \qquad u_i(s,a, N) := \frac{1}{N},
\end{align*}

as well as

\begin{align*}
|u_i(s,a, N)| =\frac{1}{N} := C_{\mathrm{u}} \qquad \text{and} \qquad
\norm{W_i}_\infty \leq \frac{1}{1-\gamma} := C_{\mathrm{w}}.
\end{align*}

In the same way as our proof for the upper bound on $I_{4,1}$, we Lemma <ref> with $(N,s,a)=(N_t,s_t,a_t)$ and have

\begin{equation}
\left|\frac{1}{{N_t}}\sum_{n = 1}^{{N_t}} \left( P_{t_n} -P_{s_t,a_t}\right) {V}_{t_n}^{\rref}\right| \lesssim  \sqrt{\frac{\log^2\frac{SAT}{\delta}}{{N_t}(1-\gamma)^2}} + \frac{\log^2\frac{SAT}{\delta}}{{N_t}(1-\gamma)}  \label{eq:I42-1.1}
\end{equation}

with probability at least $1-\delta$.

On the other hand, the second factor in the product in (<ref>) can be simply bounded as follows:

\begin{align}
\left|\sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}\left(P_{t_{n}} + P_{s_t,a_t}\right){V}^{\rref}_{t_n}\right|  \le \sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}} \left( \norm{P_{t_n}}_1 + \norm{P_{s_t,a_t}}_1 \right) \norm{{V}^{\rref}_{t_n}}_{\infty} \leq \frac{2}{1-\gamma},
\label{eq:I42-1.2}
\end{align}

in which we use the elementary facts $\sum_{n = 1}^{N_t} \eta^{N_t}_n \leq 1$, $\norm{{V}^{\rref}_{t_n}}_{\infty} \leq \frac{1}{1-\gamma}$ and $\norm{P_{t_n}}_1 = \norm{P_{s_t,a_t}}_1=1$.

Substituting (<ref>) and (<ref>) back into (<ref>), we can obtain the desired bound (<ref>) for the case $I_{4,2}>0$.
Combined this with the trivial case of $I_{4,2}\le 0$, we have established (<ref>).

Step 3: combining the preceding bounds.

Let us bring the bounds (<ref>) and (<ref>) into (<ref>). This gives

\begin{align*}
I_4 \leq |I_{4,1}| + I_{4,2}
\leq C_{4,3}\left\{ \sqrt{\frac{1}{N_t(1-\gamma)^4}\log^2\frac{SAT}{\delta}} + \frac{1}{N_t(1-\gamma)^2}\log^2\frac{SAT}{\delta}\right\}
\end{align*}

for some absolute constant $C_{4,3}>0$. Writing $I_4$ with its definition in (<ref>) and rearranging the inequality results, and taking square root on both sides, we have

\begin{align*}
&\quad\ \left\{\sum_{n = 1}^{N_t} \eta^{N_t}_n\Var_{s_t,a_t}\left({V}^{\rref}_{t_n}\right)\right\}^{1/2}\\
&\leq \left\{ {\sigma}^{\re}_{t_{N_t}+1}(s_t,a_t) - \left({\mu}^{\re}_{t_{N_t}+1}(s_t,a_t) \right)^2\right\}^{1/2} + \sqrt{C_{4,3}} \left(\sqrt{\frac{1}{N_t(1-\gamma)^4}\log^2\frac{SAT}{\delta}} + \frac{1}{N_t(1-\gamma)^2}\log^2\frac{SAT}{\delta}\right)^{1/2}\\
&\leq \left\{ {\sigma}^{\re}_{t_{N_t}+1}(s_t,a_t) - \left({\mu}^{\re}_{t_{N_t}+1}(s_t,a_t) \right)^2\right\}^{1/2} + \frac{1}{\left(N_{t}\right)^{1/4}(1-\gamma)}\log^{1/2}\frac{SAT}{\delta}+\frac{1}{\left(N_t\right)^{1/2}(1-\gamma)}\log\frac{SAT}{\delta},
\end{align*}

in which we also use the result of (<ref>).

Substitution into (<ref>) leads to the desired result (<ref>).

§ PROOF OF LEMMA <REF>

Let us decompose $\zeta_t$ (defined in (<ref>)) into three component terms and examine each of them separately:

\begin{align}\label{eq:zeta-decomposition-def}
\zeta_t := \underbrace{V_{t-1}(s_t) - Q_{t}(s_t,a_t)}_{\zeta_{t,1}} + \gamma\underbrace{\left(P_{s_t,a_t} - P_t\right)\left(V^\star - V^{\pi_{t}}\right)}_{\zeta_{t,2}} + \gamma\underbrace{\left(V^{\pi_{t+1}}(s_{t+1}) - V^{\pi_t}(s_{t+1})\right)}_{\zeta_{t,3}}.
\end{align}

We can find upper bounds for each of these three terms as follows:

\begin{equation}
\sum_{t=1}^T \zeta_{t,1} \lesssim \frac{SA}{1-\gamma}\log T + \frac{(SA)^{3/4}T^{1/4}\log^{5/4}\frac{SAT}{\delta}}{(1-\gamma)^{5/4}} + \sqrt{\frac{SA\log^2 T}{1-\gamma}\sum_{t=1}^T \big(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)}, \label{eq:xi-1}
\end{equation}

\begin{align}
\sum_{t = 1}^{T}\zeta_{t,2} & \lesssim \sqrt{\frac{SA\log\frac{T}{\delta}}{1-\gamma} \sum_{t=1}^{T}\big(V^{\star}(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)} + \frac{\left(SA\right)^{5/8}T^{1/8}}{(1-\gamma)^{11/8}}\left(\log\frac{SAT}{\delta}\right)^{9/8} \notag\\ & \qquad \qquad + \frac{(SA)^{1/2}T^{1/4}}{(1-\gamma)^{5/4}}\left(\log\frac{T}{\delta}\right)^{3/4} +\frac{SA}{1-\gamma}\log\frac{T}{\delta}, \label{eq:xi-2}
\end{align}

\begin{equation}
\sum_{t=1}^T \zeta_{t,3} \lesssim \frac{SA}{1-\gamma}\log T + \frac{(SA)^{3/4}T^{1/4}\log^{5/4}\frac{SAT}{\delta}}{(1-\gamma)^{5/4}} + \sqrt{\frac{SA\log^2 T}{1-\gamma}\sum_{t=1}^T \big(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)}. \label{eq:xi-3}
\end{equation}

The proofs for these inequalities are deferred to Appendix <ref>, <ref> and <ref>.

Combining (<ref>), (<ref>) and (<ref>), we can obtain the final bound: with probability at least $1-\delta$,

\begin{align}
\sum_{t=1}^T \zeta_{t} &= \sum_{t=1}^T \zeta_{t,1} + \zeta_{t,2} + \zeta_{t,3}\notag\\
&\lesssim \frac{SA}{1-\gamma}\log T + \frac{(SA)^{3/4}T^{1/4}\log^{5/4}\frac{SAT}{\delta}}{(1-\gamma)^{5/4}} + \sqrt{\frac{SA\log^2 T}{1-\gamma}\sum_{t=1}^T \big(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)} \notag\\ & \quad + \sqrt{\frac{SA\log\frac{T}{\delta}}{1-\gamma} \sum_{t=1}^{T}\big(V^{\star}(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)} + \frac{\left(SA\right)^{5/8}T^{1/8}}{(1-\gamma)^{11/8}}\left(\log\frac{SAT}{\delta}\right)^{9/8} \notag\\ & \quad +\frac{(SA)^{1/2}T^{1/4}}{(1-\gamma)^{5/4}}\left(\log\frac{T}{\delta}\right)^{3/4} +\frac{SA}{1-\gamma}\log\frac{T}{\delta} \notag\\
&\overset{(\mathrm{i})}{\lesssim} \frac{SA}{1-\gamma}\log T + \frac{(SA)^{3/4}T^{1/4}\log^{5/4}\frac{SAT}{\delta}}{(1-\gamma)^{5/4}} + \sqrt{\frac{SA\log^2 T}{1-\gamma}\sum_{t=2}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)} \notag\\ & \quad + \sqrt{\frac{SA\log\frac{T}{\delta}}{1-\gamma} \sum_{t=2}^{T}\big(V^{\star}(s_{t}) - V^{\pi_{t}}(s_{t})\big)} + \frac{\left(SA\right)^{5/8}T^{1/8}}{(1-\gamma)^{11/8}}\left(\log\frac{SAT}{\delta}\right)^{9/8} \notag\\ & \quad +\frac{(SA)^{1/2}T^{1/4}}{(1-\gamma)^{5/4}}\left(\log\frac{T}{\delta}\right)^{3/4} +\frac{SA}{1-\gamma}\log\frac{T}{\delta} \notag\\
&\overset{(\mathrm{ii})}{\le} \frac{SA}{1-\gamma}\log T + \frac{(SA)^{3/4}T^{1/4}\log^{5/4}\frac{SAT}{\delta}}{(1-\gamma)^{5/4}} + \sqrt{\frac{SA\log^2 T}{1-\gamma}\sum_{t=1}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)} \notag\\ & \quad + \sqrt{\frac{SA\log\frac{T}{\delta}}{1-\gamma} \sum_{t=1}^{T} \big(V^{\star}(s_{t}) - V^{\pi_{t}}(s_{t})\big)} + \frac{\left(SA\right)^{5/8}T^{1/8}}{(1-\gamma)^{11/8}}\left(\log\frac{SAT}{\delta}\right)^{9/8} \notag\\ & \quad +\frac{(SA)^{1/2}T^{1/4}}{(1-\gamma)^{5/4}}\left(\log\frac{T}{\delta}\right)^{3/4} +\frac{SA}{1-\gamma}\log\frac{T}{\delta} \notag\\
&\overset{(\mathrm{iii})}{\lesssim} \sqrt{\frac{SAT}{1-\gamma}\log\frac{SAT}{\delta}} + \frac{SA\log\frac{SAT}{\delta}}{(1-\gamma)^2} + \frac{SA}{(1-\gamma)^{5/2}}\log^2\frac{SAT}{\delta} + \frac{(SA)^{1/2}}{(1-\gamma)^{2}}\log\frac{T}{\delta} + \frac{SA}{1-\gamma}\log\frac{T}{\delta} \notag\\ & \quad + \sqrt{\frac{SA\log^2 T}{1-\gamma}\sum_{t=1}^T \big(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)} + \sqrt{\frac{SA\log\frac{T}{\delta}}{1-\gamma} \sum_{t=1}^{T}\big(V^{\star}(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)} \notag\\
&\lesssim \sqrt{\frac{SAT}{1-\gamma}\log\frac{SAT}{\delta}} + \frac{SA\log^2\frac{SAT}{\delta}}{(1-\gamma)^{5/2}} + \sqrt{\frac{SA\log^2 T}{1-\gamma}\sum_{t=1}^T \big(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)} \notag\\ & \quad + \sqrt{\frac{SA\log\frac{T}{\delta}}{1-\gamma} \sum_{t=1}^{T}\big(V^{\star}(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)},
\end{align}

in which (i) is by upper-bounding $V_T(s_{T+1}) - V^{\pi_{T+1}}(s_{T+1})$ and $V^{\star}(s_{T+1}) - V^{\pi_{T+1}}(s_{T+1})$ with the addition of $\frac{2}{1-\gamma}$; (ii) is due to $V_0(s_1) - V^{\pi_{1}}(s_{1}) \ge 0$ and $V^\star(s_1) - V^{\pi_{1}}(s_{1}) \ge 0$, which can be obtained from the fact $V_0(s) = \frac{1}{1-\gamma}$ and $V^\star(s) \ge V^{\pi_{1}}(s)$ for all $s\in\cS$; (iii) is by the basic inequality $2ab\leq a^2 + b^2$.

§.§ Bounding $\zeta_{t,1}$

First, we define some quantities to streamline our analysis.

For every $(s,a) \in \cS\times \cA$, let $\tau_i(s,a)$ denote the step index that $\qdiff(s,a) > \frac{1}{1-\gamma}$ for the $i$-th time, that is, Line <ref> in Algorithm <ref> (equivalently, Line <ref> in Algorithm <ref>) is triggered for the $i$-th time. (Note that it is the index of the step in which $\qdiff(s,a) > \frac{1}{1-\gamma}$ occurs and not the time index of the $\theta$ that gets updated in this step. The updated $\theta$ is $\theta_{t+1}$ and the update happens after Line <ref>.) Mathematically, this is

\begin{equation}
\tau_i(s,a) := \min\left\{t > \tau_{i-1}(s,a) ~:~ \qdiff_{t}(s_t,a_t) + Q_{M_{t}(s_t, a_t)}(s_t, a_t) - Q_{t+1}(s_t, a_t) > \frac{1}{1-\gamma}\right\} %\qdiff_t(s,a) > \frac{1}{1-\gamma}
\end{equation}

with $\tau_0(s,a) = 0$.

For every $(s,a) \in \cS\times \cA$, let $K_t(s,a)$ be the total number of times such that $\qdiff(s,a) > \frac{1}{1-\gamma}$ until the end of $t$-th step. Mathematically, this is

\begin{equation}
K_t(s,a) := \max\left\{i ~:~ \tau_i(s,a) \le t\right\}. \label{eq:K-def}
\end{equation}

For notational simplicity, we abbreviate $\tau_i(s,a)$ as $\tau_i$, $K_t(s,a)$ as $K_t$ and $N_t(s,a)$ as $N_t$ when the context is clear.

We can express $\zeta_{t,1}$ with $K_t(s,a)$ after the following manipulation:

\begin{align}
\sum_{t=1}^T \zeta_{t,1} &= \sum_{t=1}^T \big(V_{t-1}(s_t) - Q_{t}(s_t,a_t)\big) \notag\\
&\overset{(\mathrm{i})}{\le} \sum_{t=1}^T \big(Q_{Z_{t-1}}(s_t,a_t) - Q_{t}(s_t,a_t)\big) \notag\\
&\overset{(\mathrm{ii})}{=} \sum_{s,a}\sum_{i=0}^{K_T(s,a)}\sum_{n=N_{\tau_i}}^{N_{\tau_{i+1}}-1}\left(Q_{Z_{t_n-1}}(s,a) - Q_{t_n}(s,a)\right)\notag\\
&= \sum_{s,a}\sum_{i=0}^{K_T(s,a)}\sum_{n=N_{\tau_i}}^{N_{\tau_{i+1}}-1}\left(Q_{Z_{t_n-1}}(s,a) - Q_{Z_{t_n+1}}(s,a) + Q_{Z_{t_n+1}}(s,a) - Q_{t_n}(s,a)\right)\notag\\
&\overset{(\mathrm{iii})}{\le} \sum_{s,a}\sum_{i=0}^{K_T(s,a)}\frac{3}{1-\gamma}\notag\\
&\lesssim \frac{1}{1-\gamma}\sum_{s,a}K_T(s,a). \label{eq:xi-1-1}
\end{align}

In the inequalities above, (i) is because $V_{t-1}(s_t) \le V_{Z_{t-1}}(s_t) = Q_{Z_{t-1}}(s_t,a_t)$ by the monotonicity and $a_t$'s selection rule in Line <ref> of Algorithm <ref>. (ii) is because we can partition the overall length-$T$ trajectory into $K_T(s,a)$ intervals for each $(s,a)$-pair. (iii) is obtained by combining (<ref>) and (<ref>), which are bounds on the two halves of the quantity of interest respectively. Since $Q_{Z_{t_n-1}}(s,a) \neq Q_{Z_{t_n+1}}(s,a)$ at most twice in each interval $N_{\tau_i} \le n \le N_{\tau_{i+1}}-1$, we can use the fact $\norm{Q_{Z_{t_n-1}} - Q_{Z_{t_n+1}}}_\infty \le \frac{1}{1-\gamma}$ at these two points and have

\begin{align}
&\quad\ \sum_{s,a}\sum_{i=0}^{K_T(s,a)}\sum_{n=N_{\tau_i}}^{N_{\tau_{i+1}}-1}\left(Q_{Z_{t_n-1}}(s,a) - Q_{Z_{t_n+1}}(s,a)\right) \notag\\
&\le \sum_{s,a}\sum_{i=0}^{K_T(s,a)}\frac{2}{1-\gamma}. \label{eq:xi-1-1.1}
\end{align}

On the other hand, the condition in Line <ref> of Algorithm <ref> tells us that

\begin{align}
&\quad\ \sum_{s,a}\sum_{i=0}^{K_T(s,a)}\sum_{n=N_{\tau_i}}^{N_{\tau_{i+1}}-1}\left(Q_{Z_{t_n+1}}(s,a) - Q_{t_n}(s,a)\right) \notag\\
&\overset{(\mathrm{a})}{\le}  \sum_{s,a}\sum_{i=0}^{K_T(s,a)}\sum_{n=N_{\tau_i}}^{N_{\tau_{i+1}}-1}\left(Q_{\tau_i+1}(s,a) - Q_{t_n}(s,a)\right) \notag\\
&\overset{(\mathrm{b})}{\le}  \sum_{s,a}\sum_{i=0}^{K_T(s,a)}\sum_{n=N_{\tau_i}}^{N_{\tau_{i+1}}-1}\left(Q_{\tau_i+1}(s,a) - Q_{t_n+1}(s,a)\right) \notag\\
&\overset{(\mathrm{c})}{\le} \sum_{s,a}\sum_{i=0}^{K_T(s,a)}\frac{1}{1-\gamma}, \label{eq:xi-1-1.2}
\end{align}

in which (a) is because $Z$ is updated when Line <ref> of Algorithm <ref> is triggered by any $(s,a)$-pair, which is more often than $\tau_i$ that depends on a specific $(s,a)$-pair. (b) is by the monotonicity of $Q_{t}$. (c) is due to $\qdiff_{\tau_{i+1}} \le \frac{1}{1-\gamma}$. This is because the condition in Line <ref> of Algorithm <ref> is only triggered after the addition of $Q_{M_{t}(s_t, a_t)}(s_t, a_t) - Q_{t+1}(s_t, a_t)$ to $\qdiff_{t}$ when $t = \tau_{i+1}$.

In the following, we switch our focus to bounding $\sum_{s,a}K_T(s,a)$. Let us define a new quantity

\begin{equation}
\rho_i(s,a) := (1-\gamma)\left(Q_{\tau_{i}(s,a)+1}(s,a) - Q^\star(s,a)\right). \label{eq:rho-def}
\end{equation}

We can observe

\begin{equation}
\rho_i(s,a) \ge \rho_{i+1}(s,a) \label{eq:rho-prop1}
\end{equation}

by the monotonicity of $Q_t$. We can obtain another property about $\rho_i(s,a)$, which will be used in later analysis:

\begin{align}
&\quad \left(\rho_i(s,a) - \rho_{i+1}(s,a)\right)\left(N_{\tau_{i+1}} - N_{\tau_i}\right)\notag\\
&= (1-\gamma)\left(Q_{\tau_{i}+1}(s,a) - Q_{\tau_{i+1}+1}(s,a)\right)\left(N_{\tau_{i+1}} - N_{\tau_i}\right)\notag\\
&\ge 1,\label{eq:rho-prop2}
\end{align}

in which the inequality is obtained via the following logic: $\qdiff_{t}(s,a) + Q_{M_{t}(s, a)}(s, a) - Q_{t+1}(s, a)$ in the condition Line <ref> of Algorithm <ref> tells us $\qdiff_{\tau_{i+1}}(s,a) + Q_{M_{\tau_{i+1}}(s, a)}(s, a) - Q_{\tau_{i+1}+1}(s, a) \ge \frac{1}{1-\gamma}$. This quantity can be viewed as a summation of $(N_{\tau_{i+1}} - N_{\tau_i})$ non-negative summands in the form of $Q_{M_{t}(s, a)}(s, a) - Q_{t+1}(s, a)$, with $t$ being every step index when $(s,a)$ is visited between step $\tau_i+1$ and step $\tau_{i+1}$. $Q_{M_{\tau_{i}}(s,a)}(s,a) - Q_{\tau_{i+1}+1}(s,a) = Q_{\tau_{i}+1}(s,a) - Q_{\tau_{i+1}+1}(s,a)$ is the largest among these summands. The product of the largest summand and the total number of summands is larger than the summation itself.

Thus, combining (<ref>) and (<ref>), we have

\begin{align}
&\quad \sum_{s,a}\sum_{i=0}^{K_T(s,a)}\frac{1}{\rho_i(s,a) - \rho_{i+1}(s,a)} \notag\\
&\le \sum_{s,a}\sum_{i=0}^{K_T(s,a)}\left(N_{\tau_{i+1}} - N_{\tau_i}\right) \notag\\
&= \sum_{s,a}\sum_{i=0}^{K_T(s,a)}\sum_{n=N_{\tau_i}}^{N_{\tau_{i+1}-1}} 1 \notag\\
&= T. \label{eq:rho-diff1}
\end{align}

To continue our analysis, we introduce a lemma that provided an upper bound on $Q_t(s_{t},a_{t}) - Q^\star(s_{t},a_{t})$, whose proof is deferred to Appendix <ref>. Notice that Lemma <ref> is just a looser version of Lemma <ref>. The reason that we introduce Lemma <ref> instead of invoking Lemma <ref> is that a looser bound suffices here, and the proof of Lemma <ref> actually relies on Lemma <ref>.

Fix $\delta \in (0,1)$. Suppose that $c_b$ is chosen to be a sufficiently large universal constant in Algorithm <ref>. Then with probability at least $1 - \delta$,

\begin{align}
&\sum_{t=1}^T Q_t(s_{t},a_{t}) - Q^\star(s_{t},a_{t}) \leq \frac{\gamma(3-\gamma)}{2}\sum_{t=1}^T\left(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\right)
+ 8c_b\sqrt{\frac{SAT}{(1-\gamma)^3}\log\frac{SAT}{\delta}} + \frac{SA}{1-\gamma}.
\end{align}

Thus, we can prove

\begin{align}
&\quad \sum_{s,a}\sum_{i=0}^{K_T(s,a)}\frac{\rho_{i+1}(s,a)}{\rho_i(s,a) - \rho_{i+1}(s,a)} \notag\\
&\overset{(\mathrm{i})}{\le} \sum_{s,a}\sum_{i=0}^{K_T(s,a)}\rho_{i+1}(s,a)\left(N_{\tau_{i+1}} - N_{\tau_i}\right) \notag\\
&\overset{(\mathrm{ii})}{=} (1-\gamma)\sum_{s,a}\sum_{i=0}^{K_T(s,a)}\sum_{n=N_{\tau_i}}^{N_{\tau_{i+1}}-1}\left(Q_{\tau_{i+1}+1}(s,a) - Q^\star(s,a)\right)\notag\\
&\overset{(\mathrm{iii})}{\le} (1-\gamma)\sum_{s,a}\sum_{i=0}^{K_T(s,a)}\sum_{n=N_{\tau_i}}^{N_{\tau_{i+1}}-1}\left(Q_{t_n}(s,a) - Q^\star(s,a)\right)\notag\\
&= (1-\gamma)\sum_{t=1}^T \left(Q_{t}(s_t,a_t) - Q^\star(s_t,a_t)\right)\notag\\
&\overset{(\mathrm{iv})}{\lesssim} SA + \sqrt{\frac{SAT\log\frac{SAT}{\delta}}{1-\gamma}} + (1-\gamma)\sum_{t=1}^T\left(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\right).\label{eq:rho-diff2}
\end{align}

Above, (i) is due to (<ref>). (ii) is by the definition of $\rho_{i+1}(s,a)$ in (<ref>). (iii) is by the monotonicity of $Q_t$. (iv) is by Lemma <ref> and the fact $\frac{\gamma(3-\gamma)}{2} \le 1$.

Finally, we are ready to bound $\sum_{s,a}K_T(s,a)$. Define a sufficiently large index set of $\frac{1}{\rho_i(s,a) - \rho_{i+1}(s,a)}$ that are on the same order. Mathematically, this is

\begin{equation}
\cI(s,a) := \left\{i\le K_T(s,a) ~:~ \frac{1}{\rho_i(s,a) - \rho_{i+1}(s,a)} \asymp \kappa(s,a)\right\}, \label{eq:I-set-def}
\end{equation}

in which $\kappa(s,a)$ satisfies $|\cI(s,a)| \gtrsim \frac{K_T(s,a)}{\log T}$. Before continuing, let us explain the reason why there exists such a set $\cI(s,a)$:

By (<ref>), we have

\begin{align}
\frac{1}{\rho_i(s,a) - \rho_{i+1}(s,a)} \le N_{\tau_{i+1}} - N_{\tau_i} \le T.
\end{align}

Moreover, $\norm{Q_{\tau_{i}+1} - Q_{\tau_{i+1}+1}}_\infty \le \frac{1}{1-\gamma}$ , and this implies

\begin{equation}
\rho_i(s,a) - \rho_{i+1}(s,a) \le 1. \label{eq:rho-diff}
\end{equation}

Thus, we can conclude

\begin{equation*}
1 \le \frac{1}{\rho_i(s,a) - \rho_{i+1}(s,a)} \le T.
\end{equation*}

Consider a sequence of sets $\{\cI_m(s,a)\}_{m=1}^{\lceil\log T\rceil}$, each element of which is defined as

\begin{equation}
\cI_m(s,a) := \left\{i\le K_T(s,a) ~:~ \frac{T}{2^m} < \frac{1}{\rho_i(s,a) - \rho_{i+1}(s,a)} \le \frac{T}{2^{m-1}}\right\}.
\end{equation}

By the pigeonhole principle, there exists at least one set in this sequence with cardinality at least $\frac{K_T(s,a)}{\log T}$. Note that $\frac{1}{\rho_i(s,a) - \rho_{i+1}(s,a)}$'s in the same set are within a factor of $2$.

With such set $\cI(s,a)$, we can prove

\begin{align}
&\quad \sum_{s,a}\sum_{i=0}^{K_T(s,a)}\frac{\rho_{i+1}(s,a)}{\rho_i(s,a) - \rho_{i+1}(s,a)}\notag\\
&\ge \sum_{s,a}\sum_{i\in \cI(s,a)}\frac{\rho_{i+1}(s,a)}{\rho_i(s,a) - \rho_{i+1}(s,a)}\notag\\
&\overset{(\mathrm{i})}{\asymp} \sum_{s,a}\sum_{i\in \cI(s,a)} \kappa(s,a)\rho_{i+1}(s,a)\notag\\
&\overset{(\mathrm{ii})}{=} \sum_{s,a}\sum_{\overset{i_n\in \cI(s,a)}{i_1 > i_2 > \cdots > i_{|\cI(s,a)|}}} \kappa(s,a)\rho_{i_n+1}(s,a)\notag\\
&\overset{(\mathrm{iii})}{\ge} \sum_{s,a}\sum_{\overset{i_n\in \cI(s,a)}{i_1 > i_2 > \cdots > i_{|\cI(s,a)|}}} \left(\kappa(s,a)\rho_{i_n}(s,a) - 1\right)\notag\\
&\overset{(\mathrm{iv})}{=} \sum_{s,a}\kappa(s,a)\left(\sum_{j=n}^{|\cI(s,a)|} \rho_{i_j}(s,a) - \rho_{i_{j+1}}(s,a)\right) - \left(\sum_{s,a}\sum_{\overset{i_n\in \cI(s,a)}{i_1 > i_2 > \cdots > i_{|\cI(s,a)|}}}1\right) \notag\\
&\overset{(\mathrm{v})}{\ge} \sum_{s,a}\kappa(s,a)\left(\sum_{j=n}^{|\cI(s,a)|} \rho_{i_j}(s,a) - \rho_{i_{j}+1}(s,a)\right) - \left(\sum_{s,a}\sum_{\overset{i_n\in \cI(s,a)}{i_1 > i_2 > \cdots > i_{|\cI(s,a)|}}}1\right) \notag\\
&\overset{(\mathrm{vi})}{\asymp} \sum_{s,a}\sum_{\overset{i_n\in \cI(s,a)}{i_1 > i_2 > \cdots > i_{|\cI(s,a)|}}} \left(\kappa(s,a)\frac{n}{\kappa(s,a)} - 1\right)\notag\\
&\gtrsim \sum_{s,a}\sum_{i=1}^{|\cI(s,a)|-1} i \notag\\
&\ge \sum_{s,a}\big(\frac{1}{4}|\cI(s,a)|^2 - \frac{1}{4}\big) \notag\\
&\asymp \sum_{s,a}\max\left\{|\cI(s,a)|^2 - 1, 0\right\}.\label{eq:rho-set}
\end{align}

Above, (i) is by the definition of $\cI(s,a)$ in (<ref>). In (ii), we order the elements in $\cI(s,a)$ descendingly and denote the $n$-th largest element with $i_n$. (iii) is due to (<ref>). In (iv), We can let $\rho_{|\cI(s,a)|+1}(s,a) = 0$. (v) is due to the monotonicity of $Q_t$. (vi) is by the definition of $\cI(s,a)$.

By some algebra and (<ref>) and (<ref>), we can conclude

\begin{align}
&\quad\ \sum_{s,a}\big(|\cI(s,a)|-1\big)\notag\\
&\overset{(\mathrm{i})}{\le} \sqrt{SA\sum_{s,a}\big(|\cI(s,a)| - 1\big)^2} \notag\\
&\overset{(\mathrm{ii})}{\lesssim} \sqrt{SA\sum_{s,a}\max\left\{|\cI(s,a)|^2 - 1, 0\right\}} \notag\\
&\overset{(\mathrm{iii})}{\lesssim} \sqrt{SA}\cdot\sqrt{SA + \sqrt{\frac{SAT\log\frac{SAT}{\delta}}{1-\gamma}} + (1-\gamma)\sum_{t=1}^T\left(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\right)} \notag\\
&\overset{(\mathrm{iv})}{\le} SA + \frac{(SA)^{3/4}T^{1/4}\log^{1/4}\frac{SAT}{\delta}}{(1-\gamma)^{1/4}} + \sqrt{(1-\gamma)SA\sum_{t=1}^T \big(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)}. \label{eq:xi-1-2}
\end{align}

Above, (i) and (ii) are by the fact that $(\sum_{i=1}^n a_i)^2 \le n\sum_{i=1}^n a_i^2$. (iii) is obtained by combining (<ref>) and (<ref>). (iv) is by the algebraic fact $\sqrt{a+b} \le \sqrt{a}+\sqrt{b}$.

Finally, by the definition in (<ref>), we have

\begin{align}
&\quad\ \sum_{s,a}K_T(s,a) \lesssim \sum_{s,a}|\cI(s,a)|\log T \notag\\
&\lesssim SA\log T + \frac{(SA)^{3/4}T^{1/4}\log^{5/4}\frac{SAT}{\delta}}{(1-\gamma)^{1/4}} + \log T\sqrt{(1-\gamma)SA\sum_{t=1}^T \big(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)}, \label{eq:K-bound}
\end{align}

and by (<ref>), we can obtain the desired final bound

\begin{align}
\sum_{t=1}^T \zeta_{t,1} \lesssim \frac{SA}{1-\gamma}\log T + \frac{(SA)^{3/4}T^{1/4}\log^{5/4}\frac{SAT}{\delta}}{(1-\gamma)^{5/4}} + \sqrt{\frac{SA\log^2 T}{1-\gamma}\sum_{t=1}^T \big(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)}. \label{eq:xi-1-bound}
\end{align}

§.§.§ Proof of Lemma <ref>

To prove this lemma, it suffices to find an upper bound on $Q^{\UCB}_t(s_t, a_t) - Q^\star(s_t, a_t)$. Let us again adopt the abbreviation $N_t := N_t(s,a)$ when $(s,a)$ is clear from the context. By (<ref>) and (<ref>), for any $(s,a)\in\cS\times\cA$,

\begin{align}
&\quad\ Q^{\UCB}_t(s, a) - Q^\star(s, a) \notag\\
&= \eta_0^{N_{t-1}} \left(Q^{\UCB}_1(s, a) - Q^\star(s, a)\right) + \sum_{n=1}^{N_{t-1}} \eta_n^{N_{t-1}} \left(\gamma\left(V^{t_n}(s_{t_n+1}) - V^\star(s_{t_n+1})\right) + \gamma\left(P_{t_n} - P_{s,a}\right)V^\star + b_n\right) \notag\\
&\le \frac{\eta_0^{N_{t-1}}}{1-\gamma} + \sum_{n=1}^{N_{t-1}} \eta_n^{N_{t-1}} \Big(\gamma\big(V^{t_n}(s_{t_n+1}) - V^\star(s_{t_n+1})\big)+ 2b_n\Big) \notag\\
&\le \frac{\eta_0^{N_{t-1}}}{1-\gamma} + 4c_b\sqrt{\frac{\log\frac{SAT}{\delta}}{(1-\gamma)^3N_{t-1}}} + \sum_{n=1}^{N_{t-1}} \eta_n^{N_{t-1}} \gamma\left(V^{t_n}(s_{t_n+1}) - V^\star(s_{t_n+1})\right) , \label{eq:crude-Q-1}
\end{align}

in which the last inequality is because $\sum_{n=1}^N\frac{\eta_n^N}{\sqrt{N}} \le \frac{2}{\sqrt{N}}$ by (<ref>) in Lemma <ref>.

Now, we are ready to work towards the desired upper bound:

\begin{align}
&\quad\ \sum_{t=1}^T Q_t(s_{t},a_{t}) - Q^\star(s_{t},a_{t}) \notag\\
&\overset{(\mathrm{i})}{\le} \sum_{t=1}^T Q^{\UCB}_t(s, a) - Q^\star(s, a) \notag\\
&\overset{(\mathrm{ii})}{\le} \sum_{t=1}^T\frac{\eta_0^{N_{t-1}(s_t,a_t)}}{1-\gamma} + 4c_b\sqrt{\frac{\log\frac{SAT}{\delta}}{(1-\gamma)^3N_{t-1}(s_t,a_t)}} + \sum_{n=1}^{N_{t-1}(s_t,a_t)} \eta_n^{N_{t-1}(s_t,a_t)} \gamma\left(V^{t_n}(s_{t_n+1}) - V^\star(s_{t_n+1})\right) \label{eq:crude-Q-2}\\
&\overset{(\mathrm{iii})}{\le} \frac{SA}{1-\gamma} + 8c_b\sqrt{\frac{SAT\log\frac{SAT}{\delta}}{(1-\gamma)^3}} + \frac{\gamma(3-\gamma)}{2}\sum_{t=1}^T \big(V_{t}(s_{t+1}) - V^\star(s_{t+1})\big).
\end{align}

In the inequalities above, (i) is because for any $(s,a)\in\cS\times\cA$, $Q^{\UCB}_t(s,a) \ge Q_t(s,a)$ by Line <ref> of Algorithm <ref>. (ii) is by (<ref>). (iii) is obtained by the upper bounds on each of the three terms in (<ref>). These three terms can be bounded as follows:

The first term in (<ref>) can be bounded with $\frac{SA}{1-\gamma}$ due to (<ref>) and the fact that for each $(s,a)\in\cS\times\cA$, $N_{t-1}(s,a) = 0$ for only one instance of $t$ and will become a positive integer thereafter.

For the second term in (<ref>), since $\sum_{(s,a)}N_{T-1}(s,a) \le T$, we have

\begin{equation*}
\sum_{t=1}^T\sqrt{\frac{1}{N_{t-1}(s_t, a_t)}} \leq \sum_{(s,a)}\sum_{n=1}^{N_{T-1}(s, a)}\sqrt{\frac{1}{n}} \le \sum_{(s,a)}2\sqrt{N_{T-1}(s, a)} \le 2\sqrt{SAT}.
\end{equation*}

Lastly, for the third term in (<ref>), we have

\begin{align*}
&\quad \sum_{t=1}^T\sum_{n=1}^{N_{t-1}(s_t,a_t)} \eta_n^{N_{t-1}(s_t,a_t)} \gamma\left(V_{t_n(s_t,a_t)}(s_{t_n(s_t,a_t)+1}) - V^\star(s_{t_n(s_t,a_t)+1})\right)\\
&= \sum_{(s,a)}\sum_{k=1}^{N_{T-1}(s, a)}\sum_{n=1}^k\eta_n^{k}\gamma\left(V_{t_n(s,a)}(s_{t_n(s,a)+1}) - V^\star(s_{t_n(s,a)+1})\right)\\
&= \sum_{(s,a)}\sum_{k=1}^{N_{T-1}(s, a)}\sum_{n=k}^{N_{T-1}(s, a)}\eta_k^{n}\gamma\left(V_{t_k(s,a)}(s_{t_k(s,a)+1}) - V^\star(s_{t_k(s,a)+1})\right)\\
&= \sum_{t=1}^T \sum_{n=N_t(s_t,a_t)}^{N_{T-1}(s_t,a_t)}\eta_{N_t(s_t,a_t)}^{n}\gamma\big(V_{t}(s_{t+1}) - V^\star(s_{t+1})\big)\\
&\le \frac{\gamma(3-\gamma)}{2}\sum_{t=1}^T \big(V_{t}(s_{t+1}) - V^\star(s_{t+1})\big),
\end{align*}

in which the penultimate step is obtained because $t = t_k(s,a)$ implies $k = N_t(s,a)$, and the last step is because $\sum_{n=N_t(s_t,a_t)}^{N_{T-1}(s_t,a_t)}\eta_{N_t(s_t,a_t)}^n \le \frac{3-\gamma}{2}$ by Lemma <ref>.

§.§ Bounding $\zeta_{t,2}$

We will prove (<ref>) with Lemma <ref>. Set

\begin{align*}
W_i \coloneqq V^{\star} - V^{\pi_{i}}
\qquad \text{and} \qquad
u_i(s_i,a_i) \coloneqq 1.
\end{align*}

Since $V^{\rref}_{i}(s),  V^{\star}(s)\in [0,\frac{1}{1-\gamma}]$, it can be seen that

\begin{align*}
\left|u_i(s_i,a_i) \right| = 1 \eqqcolon C_{\mathrm{u}}
\qquad \text{and} \qquad
\norm{W_i}_\infty \leq \frac{1}{1-\gamma} \eqqcolon C_{\mathrm{w}}.
\end{align*}

By Lemma <ref>, with probability at least $1- \delta/2$, one has

\begin{align}
\sum_{t=1}^T \zeta_{t,2} &= \sum_{t = 1}^{T} \left(P_{s_t,a_t} - P_t\right)\left(V^\star - V^{\pi_{t}}\right) \notag\\
& \lesssim \sqrt{C_{\mathrm{u}}^{2}C_{\mathrm{w}}SA\sum_{i=1}^{T}\EE_{i-1}\left[P_{i}W_{i}\right]\log\frac{T}{\delta}} + C_{\mathrm{u}}C_{\mathrm{w}}SA\log\frac{T}{\delta} \notag \\
&= \sqrt{\frac{SA}{1-\gamma}\sum_{i=1}^{T}\EE_{i-1}\left[P_{i}\left(V^{\star} - V^{\pi_{i}}\right)\right]\log\frac{T}{\delta}}+\frac{SA}{1-\gamma}\log\frac{T}{\delta} \notag \\
&= \sqrt{\frac{SA}{1-\gamma} \left\{ \sum_{t=1}^{T}P_{s_{t},a_{t}}\left(V^{\star} - V^{\pi_{t}}\right) \right\} \log\frac{T}{\delta}}+\frac{SA}{1-\gamma}\log\frac{T}{\delta}, \label{eq:xi-2-1}
\end{align}

in which the last step is because $V^{\star} - V^{\pi_{t}}$ is deterministic when conditioned on the $(i-1)$-th step.

In order to obtain the desired bound, more manipulation is needed on $\sum_{t=1}^{T}P_{s_{t},a_{t}}\big(V^{\star} - V^{\pi_{t}}\big)$ in (<ref>). Towards this end, we first invoke the Azuma-Hoeffding inequality (Theorem <ref>), which leads to

\begin{align}
\left|\sum_{t=1}^{T}\left(P_{t}-P_{s_{t},a_{t}}\right)\left(V^{\star} - V^{\pi_{t}}\right)\right| & \lesssim \sqrt{\frac{T}{(1-\gamma)^2}\log \frac{1}{\delta}}, \label{eq:xi-2-2}
\end{align}

with probability at least $1-\delta/2$, because $V^{\star} - V^{\pi_{t}}$ is deterministic when conditioned on the $(i-1)$-th step and $\norm{V^{\star} - V^{\pi_{t}}}_\infty \le \frac{1}{1-\gamma}$.

With (<ref>) established, we can conclude

\begin{align}
&\quad\ \sum_{t=1}^{T}P_{s_{t},a_{t}}\left(V^{\star} - V^{\pi_{t}}\right) \notag\\
&= \sum_{t=1}^{T}P_{t}\left(V^{\star} - V^{\pi_{t}}\right) + \sum_{t=1}^{T}\left(P_{s_{t},a_{t}} - P_{t}\right)\left(V^{\star} - V^{\pi_{t}}\right) \notag\\
&\lesssim \sum_{t=1}^{T}\big(V^{\star}(s_{t+1}) - V^{\pi_{t}}(s_{t+1})\big) + \sqrt{\frac{T}{(1-\gamma)^2}\log \frac{1}{\delta}} \notag\\
&= \sum_{t=1}^{T}\big(V^{\star}(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big) + \sum_{t=1}^{T}\big(V^{\pi_{t+1}}(s_{t+1}) - V^{\pi_{t}}(s_{t+1})\big) + \sqrt{\frac{T}{(1-\gamma)^2}\log \frac{1}{\delta}} \notag\\
&\lesssim \sum_{t=1}^{T}\big(V^{\star}(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big) + \left(SAT\right)^{1/4}\left(\log\frac{SAT}{\delta}\right)^{5/4}\left(\frac{1}{1-\gamma}\right)^{7/4} + \sqrt{\frac{T}{(1-\gamma)^3}\log \frac{T}{\delta}}, \label{eq:xi-2-3}
\end{align}

with probability at least $1-\delta/2$. The last step is obtained by applying (<ref>) and the fact $\norm{V_t - V^{\pi_{t+1}}}_\infty \le \frac{1}{1-\gamma}$.

Finally, substituting (<ref>) into (<ref>) gives the desired bound

\begin{align}
&\quad \ \sum_{t = 1}^{T}\zeta_{t,2} \notag\\
&\lesssim \sqrt{\frac{SA}{1-\gamma} \left\{ \sum_{t=1}^{T}P_{s_{t},a_{t}}\left(V^{\star} - V^{\pi_{t}}\right) \right\} \log\frac{T}{\delta}}+\frac{SA}{1-\gamma}\log\frac{T}{\delta} \notag\\
&\lesssim \sqrt{\frac{SA}{1-\gamma} \left\{ \sum_{t=1}^{T}\big(V^{\star}(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big) + \frac{\left(SAT\right)^{1/4}}{(1-\gamma)^{7/4}}\left(\log\frac{SAT}{\delta}\right)^{5/4} + \sqrt{\frac{T}{(1-\gamma)^3}\log \frac{T}{\delta}}\right\} \log\frac{T}{\delta}}+\frac{SA}{1-\gamma}\log\frac{T}{\delta} \notag\\
&\le \sqrt{\frac{SA\log\frac{T}{\delta}}{1-\gamma} \sum_{t=1}^{T}\big(V^{\star}(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)} + \frac{\left(SA\right)^{5/8}T^{1/8}}{(1-\gamma)^{11/8}}\left(\log\frac{SAT}{\delta}\right)^{9/8} \notag\\ & \qquad \qquad + \frac{(SA)^{1/2}T^{1/4}}{(1-\gamma)^{5/4}}\left(\log\frac{T}{\delta}\right)^{3/4} +\frac{SA}{1-\gamma}\log\frac{T}{\delta} \label{eq:xi-2-final}
\end{align}

with probability at least $1-\delta$.

§.§ Bounding $\zeta_{t,3}$

By the definition of $K_t(s,a)$ in (<ref>), we can write

\begin{align}
\sum_{t=1}^T \zeta_{t,3} &= \gamma\sum_{t=1}^T \big(V^{\pi_{t+1}}(s_{t+1}) - V^{\pi_t}(s_{t+1})\big)\notag\\
&\leq \gamma\sum_{s,a}\sum_{i=0}^{K_T(s,a)} \frac{1}{1-\gamma}\notag\\
&\lesssim \frac{1}{1-\gamma}\sum_{s,a}K_T(s,a), \label{eq:xi-3-1}
\end{align}

in which the inequality is obtained using the total number of times that policy $\pi_t$ in Algorithm <ref> switches over $T$ steps and the fact that $\norm{V^{\pi_{t+1}} - V^{\pi_t}}_\infty \le \frac{1}{1-\gamma}$.

By the upper bound on $\sum_{s,a}K_T(s,a)$ in (<ref>), we can obtain the desired final bound

\begin{align}
\sum_{t=1}^T \zeta_{t,3} \lesssim \frac{SA}{1-\gamma}\log T + \frac{(SA)^{3/4}T^{1/4}\log^{5/4}\frac{SAT}{\delta}}{(1-\gamma)^{5/4}} + \sqrt{\frac{SA\log^2 T}{1-\gamma}\sum_{t=1}^T \big(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)}. \label{eq:xi-3-bound}
\end{align}

§.§ Crude Regret Bound as a Consequence of Lemma <ref>

Note that Lemma <ref> can give rise to a crude bound on $\Regret(T)$, which we will need in the proof of Theorem <ref>. It can be summarized in a lemma as follows:

Choose any $\delta \in (0,1)$. Suppose that $c_b$ is chosen to be a sufficiently large universal constant in Algorithm <ref>. Then there exists some absolute constant $C_0 > 0$ such that Algorithm <ref> achieves

\begin{equation}
\Regret(T) \le \sum_{t=1}^T \big(V_{t-1}(s_t) - V^{\pi_t}(s_t)\big) \lesssim \sqrt{\frac{SAT\log\frac{SAT}{\delta}}{(1-\gamma)^5}} + \frac{SA\log^{2}\frac{SAT}{\delta}}{(1-\gamma)^{7/2}}
\end{equation}

with probability at least $1-\delta$.

By the optimistic property of our value function estimates in Lemma <ref>, we can

\begin{equation*}
\mathrm{Regret}(T) = \sum_{t=1}^T \big(V^\star(s_t) - V^{\pi_t}(s_t)\big) \le \sum_{t=1}^T \big(V_{t-1}(s_t) - V^{\pi_t}(s_t)\big).
\end{equation*}

In the inequality, since $V_0(s)$ is undefined in our algorithm, we can simply let $V_0(s) = \frac{1}{1-\gamma}$ for all $s\in \cS$.

We can follow the regret decomposition in (<ref>) and obtain the following inequality:

\begin{align}
V_{t-1}(s_t) - V^{\pi_t}(s_t) \le \frac{\gamma(3-\gamma)}{2}\left(V^\star(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\right) + Q_{t}(s_t, a_t) - Q^\star(s_t, a_t) + \zeta_t, \label{eq:crude-regret-decomp1}
\end{align}

in which $\zeta_t$ has the same definition as (<ref>):

\begin{equation*}
\zeta_t := V_{t-1}(s_t) - Q_t(s_t,a_t) + \gamma\left(P_{s_t,a_t} - P_t\right)\left(V^\star - V^{\pi_t}\right) + \gamma\left(V^{\pi_{t+1}}(s_{t+1}) - V^{\pi_t}(s_{t+1})\right).
\end{equation*}

Invoking Lemma <ref> and rearranging (<ref>), we obtain a recursion as follows:

\begin{align}
&\quad \left(1 - \frac{\gamma(3-\gamma)}{2}\right)\sum_{t=1}^T \big(V_{t-1}(s_t) - V^{\pi_t}(s_t)\big) \notag\\
&= \sum_{t=1}^T\big(V_{t-1}(s_t) - V^{\pi_t}(s_t)\big) - \frac{\gamma(3-\gamma)}{2}\sum_{t=1}^T\big(V_{t-1}(s_t) - V^{\pi_t}(s_t)\big) \notag\\
&\overset{(\mathrm{i})}{\le} \sum_{t=1}^T\big(V_{t-1}(s_t) - V^{\pi_t}(s_t)\big) - \frac{\gamma(3-\gamma)}{2}\sum_{t=2}^T\big(V_{t-1}(s_t) - V^{\pi_t}(s_t)\big) \notag\\
&= \sum_{t=1}^T\big(V_{t-1}(s_t) - V^{\pi_t}(s_t)\big) - \frac{\gamma(3-\gamma)}{2}\sum_{t=1}^{T-1}\big(V_{t}(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big) \notag\\
&\overset{(\mathrm{ii})}{\le} \sum_{t=1}^T\frac{\gamma(3-\gamma)}{2}\big(V^\star(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big) + Q_{t}(s_t, a_t) - Q^\star(s_t, a_t) + \zeta_t - \frac{\gamma(3-\gamma)}{2}\sum_{t=1}^{T-1}\big(V_{t}(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big) \notag\\
&\overset{(\mathrm{iii})}{\le} 8c_b\sqrt{\frac{SAT}{(1-\gamma)^3}\log\frac{SAT}{\delta}} + \frac{SA}{1-\gamma} + \sum_{t=1}^T\frac{\gamma(3-\gamma)}{2}\big(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big) + \zeta_t \notag\\ & \qquad - \frac{\gamma(3-\gamma)}{2}\sum_{t=1}^{T-1}\big(V_{t}(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big) \notag\\
&= 8c_b\sqrt{\frac{SAT}{(1-\gamma)^3}\log\frac{SAT}{\delta}} + \frac{SA}{1-\gamma} + \frac{\gamma(3-\gamma)}{2}\big(V^\star(s_{T+1}) - V^{\pi_{T+1}}(s_{T+1})\big) + \sum_{t=1}^T \zeta_t\notag\\
&\overset{(\mathrm{iv})}{\le} 8c_b\sqrt{\frac{SAT}{(1-\gamma)^3}\log\frac{SAT}{\delta}} + \frac{SA}{1-\gamma} + \frac{3}{2(1-\gamma)} + \sum_{t=1}^T \zeta_t\notag\\
&\lesssim \sqrt{\frac{SAT}{(1-\gamma)^3}\log\frac{SAT}{\delta}} + \frac{SA}{1-\gamma} + \sum_{t=1}^T \zeta_t. \label{eq:crude-regret-decomp2}
\end{align}

Above, (i) is because by the optimistic property in Lemma <ref>, $V_{t-1}(s_t) \ge V^\star(s_t) \ge V^{\pi_t}(s_t) \ge 0$ and thus $V_{t-1}(s_t) - V^{\pi_t}(s_t) \ge 0$. (ii) is obtained by replacing $\left(V_{t-1}(s_t) - V^{\pi_t}(s_t)\right)$ with (<ref>). (iii) is obtained by invoking Lemma <ref> to replace $\sum_{t=1}^T Q_t(s_{t},a_{t}) - Q^\star(s_{t},a_{t})$. (iv) is due to $V^\star(s_{T+1}) - V^{\pi_{T+1}}(s_{T+1}) \le \frac{1}{1-\gamma}$ and $\gamma\in(0,1)$.

Note $0 < 1 - \frac{\gamma(3-\gamma)}{2} < 1$ since $\gamma\in(0,1)$. Dividing (<ref>) by $1 - \frac{\gamma(3-\gamma)}{2}$, we have

\begin{align}
\sum_{t=1}^T \big(V_{t-1}(s_t) - V^{\pi_t}(s_t)\big) \lesssim \sqrt{\frac{SAT}{(1-\gamma)^5}\log\frac{SAT}{\delta}} + \frac{SA}{(1-\gamma)^2} + \frac{1}{1-\gamma}\sum_{t=1}^T \zeta_t, \label{eq:crude-regret-decomp3}
\end{align}

in which the additional $\frac{1}{1-\gamma}$ factor is due to the fact $1 - \frac{\gamma(3-\gamma)}{2} \ge \frac{1-\gamma}{2}$.

After applying Lemma <ref>, (<ref>) can be written as

\begin{align}
& \quad\ \sum_{t=1}^T \big(V_{t-1}(s_t) - V^{\pi_t}(s_t)\big) \notag\\
&\leq C_5\Bigg(\sqrt{\frac{SAT\log\frac{SAT}{\delta}}{(1-\gamma)^5}} + \frac{SA\log^{2} \frac{SAT}{\delta}}{(1-\gamma)^{7/2}} + \sqrt{\frac{\log^2 T}{(1-\gamma)^3}\sum_{t=1}^T\big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)} \notag\\ & \qquad + \sqrt{\frac{SA\log\frac{T}{\delta}}{(1-\gamma)^3} \sum_{t=1}^{T}\big(V^{\star}(s_{t}) - V^{\pi_{t}}(s_{t})\big)}\Bigg) \notag\\
&\leq C_5\Bigg(\sqrt{\frac{SAT\log\frac{SAT}{\delta}}{(1-\gamma)^5}} + \frac{SA\log^{2} \frac{SAT}{\delta}}{(1-\gamma)^{7/2}} + \sqrt{\frac{\log^2 T}{(1-\gamma)^3}\sum_{t=1}^T\big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)} \notag\\ & \qquad + \sqrt{\frac{SA\log\frac{T}{\delta}}{(1-\gamma)^3} \sum_{t=1}^{T}\big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)}\Bigg) \label{eq:crude-regret-decomp4}
\end{align}

for some absolute constant $C_5 > 0$. The last inequality is by the optimism of $V_{t-1}$ by Lemma <ref>.

Finally, we can invoke Proposition <ref> on (<ref>) by letting

\begin{align*}
x &:= C_5\left(\frac{\log T}{(1-\gamma)^{3/2}} + \sqrt{\frac{SA\log\frac{T}{\delta}}{(1-\gamma)^3}}\right),\\
y &:= C_5\left(\sqrt{\frac{SAT\log\frac{SAT}{\delta}}{(1-\gamma)^5}} + \frac{SA\log^{2} \frac{SAT}{\delta}}{(1-\gamma)^{7/2}}\right),\\
z &:= \sum_{t=1}^T \big(V_{t-1}(s_t) - V^{\pi_t}(s_t)\big)
\end{align*}

in (<ref>). (<ref>) would give

\begin{align}
& \quad\ \sum_{t=1}^T \big(V_{t-1}(s_t) - V^{\pi_t}(s_t)\big) \notag\\
&\leq 2C_5\sqrt{\frac{SAT\log\frac{SAT}{\delta}}{(1-\gamma)^5}} + 2(C_5 + C_5^2)\frac{SA\log^{2} \frac{SAT}{\delta}}{(1-\gamma)^{7/2}} \notag\\
&\lesssim \sqrt{\frac{SAT\log\frac{SAT}{\delta}}{(1-\gamma)^5}} + \frac{SA\log^{2} \frac{SAT}{\delta}}{(1-\gamma)^{7/2}}, \label{eq:crude-regret-decomp-final}
\end{align}

which is as claimed in Lemma <ref>.

§ PROOF OF LEMMA <REF>

§.§ Proof of Inequality (<ref>)

Before proving the pessimism in $V_{t}^{\LCB}$, we focus on proving

\begin{equation}
\label{eq:lcb}
Q^{\LCB}_t(s, a) \le Q^{\star}(s, a) \qquad\text{for all } (s, a, t) \in  \cS \times \cA \times [T] .
\end{equation}

Let us proceed by induction. We start with the base case. By our initialization, we have
$$0 = Q^{\LCB}_1(s, a) \le Q^{\star}(s,a);$$

hence, (<ref>) trivially holds.

For the induction step, let us assume the inductive hypothesis that (<ref>) holds all the way up to $t$ for all $(s,a)\in\cS\times\cA$. We now show the statement holds for the $(t+1)$-th step as well. Recall that only $Q_{t+1}^{\LCB}(s_t,a_t)$ is updated at the $t$-th step with all other entries of $Q_{t}^{\LCB}$ fixed, so it suffices to check

\begin{equation}
Q^{\LCB}_{t+1}(s_t,a_t) \le Q^{\star}(s_t,a_t). \label{eq:pessimism-induction-step}
\end{equation}

Again, we adopt the shorthand notation $N_t := N_t(s_t,a_t)$ and $t_n := t_n(s_t,a_t)$ when it is clear from the context.

Recall $b_n := c_b\sqrt{\frac{\log\frac{SAT}{\delta}}{(1-\gamma)^3 n}}$. We rewrite the subroutine update-q-lcb() in Line <ref> of Algorithm <ref>:

\begin{equation*}
Q^{\LCB}_{t+1}(s_t,a_t) = Q^{\LCB}_{t_N+1}(s_t,a_t) = (1 - \eta_N)Q^{\LCB}_{t_N}(s_t,a_t) + \eta_{N}\left(r(s_t,a_t) + \gamma V_{t_N}^\LCB(s_{t_N+1}) - b_N\right).
\end{equation*}

This recursive relation can be expanded as

\begin{equation}
Q^{\LCB}_{t+1}(s_t,a_t) = \eta_0^N Q^{\LCB}_{1}(s_t,a_t) + \sum_{n=1}^N \eta_n^N \big(r(s_t,a_t) + \gamma V_{t_n}^\LCB(s_{t_n+1}) - b_n\big), \label{eq:QLCB}
\end{equation}

in which $\eta_0^N$ and $\eta_n^N$ are defined in Lemma <ref>.

Using (<ref>), we have

\begin{align}\label{eq:Q_LCB-Q*}
&\quad\ Q^{\LCB}_{t+1}(s_t,a_t) - Q^\star(s_t,a_t) \nonumber\\
&= \eta_0^N \left(Q^{\LCB}_{1}(s_t,a_t) - Q^\star(s_t,a_t)\right) + \sum_{n=1}^N \eta_n^N \left(r(s_t,a_t) + \gamma V_{t_n}^\LCB(s_{t_n+1}) - b_n - Q^\star(s_t,a_t)\right) \nonumber\\
&= \eta_0^N \left(Q^{\LCB}_{1}(s_t,a_t) - Q^\star(s_t,a_t)\right) + \sum_{n=1}^N \eta_n^N \Big(\gamma\left(V_{t_n}^\LCB(s_{t_n+1}) - V^\star(s_{t_n+1})\right) + \gamma\left(P_{t_n} - P_{s_t,a_t}\right)V^\star - b_n\Big),
\end{align}

where the last step is by $Q^\star(s,a) = r(s,a) + \gamma P_{s,a} V^\star$ and $V^\star(s_{t_n+1}) = P_{t_n}V^\star$.

Recall in the proof for optimism (lemma <ref>), by (<ref>), we have with probability at least $1-\delta$,

\begin{equation*}
\left|\sum_{n=1}^N\eta_n^N\gamma\left(P_{t_n} - P_{s_t,a_t}\right)V^\star\right| \le c_b\sqrt{\frac{\log\frac{SAT}{\delta}}{(1-\gamma)^3N}}\sum_{n=1}^N\eta_n^N \le \sum_{n=1}^N\eta_n^N b_n,
\end{equation*}

for all $(N,s,a) \in [T] \times \cS \times \cA$. We can employ this inequality on (<ref>) this time and obtain that with probability at least $1-\delta$,

\begin{align*}
&\quad\ Q^{\LCB}_{t+1}(s_t,a_t) - Q^\star(s_t,a_t)\\
&= \eta_0^N \left(Q^{\LCB}_{1}(s_t,a_t) - Q^\star(s_t,a_t)\right) + \sum_{n=1}^N \eta_n^N \Big(\gamma\left(V_{t_n}^\LCB(s_{t_n+1}) - V^\star(s_{t_n+1})\right) + \gamma\left(P_{t_n} - P_{s_t,a_t}\right)V^\star - b_n\Big)\\
&\le \eta_0^N \left(Q^{\LCB}_{1}(s_t,a_t) - Q^\star(s_t,a_t)\right) + \gamma\sum_{n=1}^N \eta_n^N \left(V_{t_n}^\LCB(s_{t_n+1}) - V^\star(s_{t_n+1})\right)\\
&\le \gamma\sum_{n=1}^N \eta_n^N \left(V_{t_n}^\LCB(s_{t_n+1}) - V^\star(s_{t_n+1})\right),
\end{align*}

where the last step is due to our initialization $Q^{\UCB}_{1}(s, a) = 0 \le Q^\star(s,a)$.

Lastly, the inductive hypothesis gives $V_t^\LCB(s) \le V^\star(s)$ for any $(s,a)\in\cS\times\cA$, so we can conclude

\begin{equation*}
Q^{\LCB}_{t+1}(s, a) - Q^\star(s, a) \le \sum_{n=1}^N \eta_n^N \gamma\left(V_{t_n}^\LCB(s_{t_n+1}) - V^\star(s_{t_n+1})\right) \le 0.
\end{equation*}

At this point, we have finished the proof for the induction step and thus the proof for (<ref>).

Now, let us prove the pessimism in $V^{\LCB}$. Given the pessimism in $Q^{\LCB}$ in (<ref>), we have

\begin{align}
\max_{a}Q_{t}^{\LCB}(s,a)\leq\max_{a}Q^{\star}(s,a)=V^{\star}(s)\qquad\text{for all }(t,s)\in[T]\times\mathcal{S}.
\label{eq:lcb-1}
\end{align}

On the other hand, the construction of $V_{t}^{\LCB}$ in Line <ref> of Algorithm <ref> can be written as

\begin{equation*}
V_{t}^{\LCB}(s) \leq  \max\left\{ \max_{j:j\leq t}  \max_a Q^{\LCB}_j(s, a) ,\ \max_{j:j < t}V_j^{\LCB}(s) \right\}.
\end{equation*}

Combined with the initialization $V_{1}^{\LCB}(s)=0$ for all $s\in\cS$, we can conclude with the desired pessimism of $V^{\LCB}$ via a simple induction:

\begin{align}
V_{t}^{\LCB}(s)\leq V^{\star}(s) \ \text{for all }(t,s)\in[T]\times\mathcal{S}.
\label{eq:lcb-V}
\end{align}

§.§ Proof of Inequality (<ref>)

The proof of (<ref>) essentially follows the result of Lemma <ref>, which provides an upper bound on any weighted sum of our algorithm's value estimates.

Assume there exists a constant $c_b>0$ such that for all $(t,s,a) \in [T]\times\cS\times \cA$, it holds that

\begin{align}
0 &\leq Q_{t+1}(s, a) - Q^{\LCB}_{t+1}(s, a)  \notag\\
& \le \frac{\eta^{N_t (s, a)}_0}{1-\gamma}
+ \gamma\sum_{n = 1}^{N_t(s, a)} \eta^{N_t (s, a)}_n \left(V_{t_n}(s_{t_n+1}) - V^{\LCB}_{t_n}(s_{t_n+1}) \right) + 4 c_b \sqrt{\frac{\log \frac{SAT}{\delta}}{(1-\gamma)^3 N_t(s,a)}},\label{eq:weighted-V-cond}
\end{align}

in which we use the abbreviation $t_n := t_n(s,a)$.

For every sequence $\{w_t\}_{t= 1}^{\infty}$ such that $0\le w_t\le w$ for all $t$ and $\sum_{t=1}^{\infty} w_t \le W$, one has

\begin{align}\label{eq:weighted-V}
\sum_{t=1}^T &w_t\left(V_{t}(s_{t+1})-V_{t}^{\LCB}(s_{t+1})\right) \le C_{\mathrm{v},1}\frac{ew\left(SA\right)^{3/4}T^{1/4}}{(1-\gamma)^{9/4}}\left(\log\frac{SAT}{\delta}\right)^{5/4} + C_{\mathrm{v},1}\frac{eSAw}{(1-\gamma)^2}\log T \notag\\ & \quad + 8ec_b \sqrt{\frac{SAwW\log \frac{SAT}{\delta}}{(1-\gamma)^5}} + C_{\mathrm{v},1}ew\sqrt{\frac{SA\log^2 T}{(1-\gamma)^3}\sum_{t=1}^T \big(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)} + eW
\end{align}

for some absolute constant $C_{\mathrm{v},1} > 0$.

The proof of Lemma <ref> is deferred to Appendix <ref>. We can easily prove (<ref>) with Lemma <ref>. Let us specify

\begin{equation}
w_t = \mathds{1}\left\{V_{t}(s_{t+1}) - V_{t}^{\LCB}(s_{t+1})>3\right\}. \label{eq:wt-def}
\end{equation}

Clearly, this gives us

\begin{align}
3W = 3\sum_{t=1}^T w_t &\le \sum_{t=1}^{T}w_t\left(V_{t}(s_{t+1})-V_{t}^{\LCB}(s_{t+1})\right). \label{eq:weighted-V-4}
\end{align}

If we assume (<ref>) is true, we can bring (<ref>) into the right-hand side of (<ref>). We can rearrange and rescale the inequality to obtain

\begin{align}
\frac{1}{3-e}(3W-eW) &\le \frac{1}{3-e}\Bigg(C_{\mathrm{v},1}\frac{ew\left(SA\right)^{3/4}T^{1/4}}{(1-\gamma)^{9/4}}\left(\log\frac{SAT}{\delta}\right)^{5/4} + C_{\mathrm{v},1}\frac{eSAw}{(1-\gamma)^2}\log T + 8ec_b \sqrt{\frac{SAwW\log \frac{SAT}{\delta}}{(1-\gamma)^5}} \notag\\ &\qquad \qquad \qquad + C_{\mathrm{v},1}ew\sqrt{\frac{SA\log^2 T}{(1-\gamma)^3}\sum_{t=1}^T \big(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)}\Bigg). \label{eq:weighted-V-5}
\end{align}

Invoking Proposition <ref> on (<ref>) with

\begin{align*}
x &:= \frac{8e}{3-e}c_b\sqrt{\frac{SAw\log \frac{SAT}{\delta}}{(1-\gamma)^5}},\\
y &:= \frac{ew}{3-e}C_{\mathrm{v},1}\Bigg(\frac{\left(SA\right)^{3/4}T^{1/4}}{(1-\gamma)^{9/4}}\left(\log\frac{SAT}{\delta}\right)^{5/4} + \frac{SA}{(1-\gamma)^2}\log T + \sqrt{\frac{SA\log^2 T}{(1-\gamma)^3}\sum_{t=1}^T \big(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)}\Bigg),\\
z &:= \sqrt{W},
\end{align*}

we can conclude with the inequality:

\begin{align}
&\quad\ \sum_{t=1}^T \mathds{1}\left\{V_{t}(s_{t+1}) - V_{t}^{\LCB}(s_{t+1})>3\right\} \le W \notag\\
&\lesssim \frac{w\left(SA\right)^{3/4}T^{1/4}}{(1-\gamma)^{9/4}}\left(\log\frac{SAT}{\delta}\right)^{5/4} + \frac{SAw}{(1-\gamma)^5}\log \frac{SAT}{\delta} + w\sqrt{\frac{SA\log^2 T}{(1-\gamma)^3}\sum_{t=1}^T \big(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)} \notag\\
&\overset{(\mathrm{i})}{=} \frac{\left(SA\right)^{3/4}T^{1/4}}{(1-\gamma)^{9/4}}\left(\log\frac{SAT}{\delta}\right)^{5/4} + \frac{SA}{(1-\gamma)^5}\log \frac{SAT}{\delta} + \sqrt{\frac{SA\log^2 T}{(1-\gamma)^3}\sum_{t=1}^T \big(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)} \notag\\
&\overset{(\mathrm{ii})}{\lesssim} \frac{\left(SA\right)^{3/4}T^{1/4}}{(1-\gamma)^{9/4}}\left(\log\frac{SAT}{\delta}\right)^{5/4} + \frac{SA}{(1-\gamma)^5}\log \frac{SAT}{\delta} + \sqrt{\frac{SA\log^2 T}{(1-\gamma)^3}\sum_{t=2}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)} \notag\\
&\overset{(\mathrm{iii})}{\le} \frac{\left(SA\right)^{3/4}T^{1/4}}{(1-\gamma)^{9/4}}\left(\log\frac{SAT}{\delta}\right)^{5/4} + \frac{SA}{(1-\gamma)^5}\log \frac{SAT}{\delta} + \sqrt{\frac{SA\log^2 T}{(1-\gamma)^3}\sum_{t=1}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)}, \label{eq:weighted-V-final}
\end{align}

in which (i) is because $w=1$ by our definition of $w_t$ in (<ref>); (ii) is due to $\norm{V_{T} - V^{\pi_{T+1}}}_\infty \le \frac{1}{1-\gamma}$; (iii) is due to $V_0(s_1) - V^{\pi_{1}}(s_{1}) \ge 0$, which can be obtained from the fact $V_0(s) = \frac{1}{1-\gamma}$ and $V^\star(s) \ge V^{\pi_{1}}(s)$ for all $s\in\cS$.

At this point, we can easily prove (<ref>), as (<ref>) immediately leads to

\begin{align}
&\quad \sum_{t=1}^{T}\left(V_{t}(s_{t+1})-V_{t}^{\LCB}(s_{t+1})\right)\mathds{1}\left\{V_{t}(s_{t+1}) - V_{t}^{\LCB}(s_{t+1})>3\right\} \notag\\
&\leq \frac{1}{1-\gamma}\sum_{t=1}^{T}\mathds{1}\left\{V_{t}(s_{t+1}) - V_{t}^{\LCB}(s_{t+1})>3\right\} \notag\\
&\lesssim \frac{\left(SA\right)^{3/4}T^{1/4}}{(1-\gamma)^{13/4}}\left(\log\frac{SAT}{\delta}\right)^{5/4} + \frac{SA}{(1-\gamma)^6}\log \frac{SAT}{\delta} + \sqrt{\frac{SA\log^2 T}{(1-\gamma)^5}\sum_{t=1}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)},
\end{align}

which is the final result in (<ref>) that we desire.

As the last step of proving (<ref>), we need to return to the justification of (<ref>) that allows for our invocation of Lemma <ref> earlier. The first inequality in (<ref>) is easy to prove, for Lemma <ref> and Lemma <ref> tells us $Q_t(s,a) \geq Q^{\star}(s, a) \geq Q_t^{\LCB}(s,a)$ for all $(t, s, a) \in  [T] \times \cS \times \cA$. Thus, it only remains to prove the second inequality in (<ref>), which is an upper bound on $Q_{t+1}(s, a) - Q^{\LCB}_{t+1}(s, a)$.

Let us abbreviate $N_t := N_t(s,a)$ temporarily. Since the update rule of $Q_{t+1}$ in Line <ref> of Algorithm <ref> implies $Q_{t+1}(s, a) \leq Q^{\UCB}_{t+1}(s,a)$, we can instead focus on finding an upper bound for the following quantity:

\begin{align}
Q_{t+1}(s, a) - Q^{\LCB}_{t+1}(s, a) \le Q^{\UCB}_{t+1}(s, a) - Q^{\LCB}_{t+1}(s, a) = Q^{\UCB}_{t_{N_t}+1}(s, a) - Q^{\LCB}_{t_{N_t}+1}(s, a). \label{eq:Q-QLCB-QUCB-QLCB}
\end{align}

Towards this, the update rules of $Q^{\UCB}_t$ and $Q^{\LCB}_t$ in Line <ref> and <ref> of Algorithm <ref> allow us to write

\begin{align}
&\quad\ Q^{\UCB}_{t_{N_t}+1}(s, a) - Q^{\LCB}_{t_{N_t}+1}(s, a) \notag\\
& =(1-\eta_{N_{t}})Q_{t_{N_t}}^{\UCB}(s,a)+\eta_{N_{t}}\left(r(s,a)+\gamma V_{t_{N_t}}(s_{t_{N_t}+1})+c_b\sqrt{\frac{\log\frac{SAT}{\delta}}{(1-\gamma)^3 N_{t}}}\right) \notag\\
& \qquad-(1-\eta_{N_{t}})Q_{t_{N_t}}^{\LCB}(s,a)-\eta_{N_{t}}\left(r(s,a)+ \gamma V^{\LCB}_{t_{N_t}}(s_{t_{N_t}+1})-c_b\sqrt{\frac{\log\frac{SAT}{\delta}}{(1-\gamma)^3 N_{t}}}\right) \notag\\
&= (1-\eta_{N_{t}})\left(Q_{t_{N_t}}^{\UCB}(s,a)-Q_{t_{N_t}}^{\LCB}(s,a)\right)
+\eta_{N_{t}}\left(\gamma V_{t_{N_t}}(s_{t_{N_t}+1}) - \gamma V^{\LCB}_{t_{N_t}}(s_{t_{N_t}+1}) + 2c_b\sqrt{\frac{\log\frac{SAT}{\delta}}{(1-\gamma)^3 N_{t}}}\right) \notag\\
&= (1-\eta_{N_{t}})\left(Q_{t_{N_t-1}+1}^{\UCB}(s,a) - Q_{t_{N_t-1}+1}^{\LCB}(s,a)\right)
+ \eta_{N_{t}}\left(\gamma V_{t_{N_t}}(s_{t_{N_t}+1}) - \gamma V^{\LCB}_{t_{N_t}}(s_{t_{N_t}+1}) + 2c_b\sqrt{\frac{\log\frac{SAT}{\delta}}{(1-\gamma)^3 N_{t}}}\right) \label{eq:weighted-V-cond-1} \\
& = \eta^{N_t}_0 \left(Q_{1}^{\UCB}(s,a)-Q_{1}^{\LCB}(s,a)\right)
+ \sum_{n = 1}^{N_t} \eta^{N_t}_n \left(\gamma V_{t_{n}}(s_{t_{n}+1}) - \gamma V^{\LCB}_{t_{n}}(s_{t_{n}+1}) + 2c_b\sqrt{\frac{\log\frac{SAT}{\delta}}{(1-\gamma)^3 n}}\right) \notag\\
& \leq \frac{\eta^{N_t}_0}{1-\gamma}
+ \gamma\sum_{n = 1}^{N_t} \eta^{N_t}_n \left(V_{t_{n}}(s_{t_{n}+1}) - V^{\LCB}_{t_{n}}(s_{t_{n}+1})\right) + 4c_b\sqrt{\frac{\log\frac{SAT}{\delta}}{(1-\gamma)^3 N_t}}, \label{eq:weighted-V-cond-2}
\end{align}

in which the penultimate line is obtained by expanding $Q_{t_{N_t-1}+1}^{\UCB}(s,a) - Q_{t_{N_t-1}+1}^{\LCB}(s,a)$ recursively using the recursive relation from (<ref>), and the last line is due to our initialization $0 = Q_{1}^{\LCB}(s,a) \leq Q_{1}^{\UCB} (s,a) = \frac{1}{1-\gamma}$ and the following fact

\begin{equation*}
\sum_{n = 1}^{N_t} \eta^{N_t}_n c_b\sqrt{\frac{\log\frac{SAT}{\delta}}{(1-\gamma)^3 n}}  \leq 2c_b\sqrt{\frac{\log\frac{SAT}{\delta}}{(1-\gamma)^3 N_{t}}},
\end{equation*}

which is an immediate consequence of (<ref>) in Lemma <ref>.

Finally, (<ref>) combined with (<ref>) establishes the second inequality in the condition (<ref>). With (<ref>) proven, we have justified our invocation of Lemma <ref> and thus concluded the proof of the inequality (<ref>).

§.§.§ Proof of Lemma <ref>

We can decompose the quantity of interest into two terms and bound them separately:

\begin{align}
&\quad \sum_{t=1}^{T}w_t\left(V_{t}(s_{t+1})-V_{t}^{\LCB}(s_{t+1})\right) \notag\\
&= \sum_{t=1}^{T}w_t\left(V_{t}(s_{t+1}) - Q_{t+1}(s_{t+1},a_{t+1}) + Q_{t+1}(s_{t+1},a_{t+1}) -V_{t}^{\LCB}(s_{t+1})\right) \notag\\
&\leq \sum_{t=1}^{T}w_t\Big(\left(V_{t}(s_{t+1}) - Q_{t+1}(s_{t+1},a_{t+1})\right) + \left(Q_{t+1}(s_{t+1},a_{t+1}) - Q_{t+1}^{\LCB}(s_{t+1},a_{t+1})\right)\Big), \label{eq:weighted-V-1}
\end{align}

in which the last step is due to $V_{t}^{\LCB}(s) \le V_{t+1}^{\LCB}(s) \le \max_a Q_{t+1}^{\LCB}(s,a)$ for any $s\in\cS$, which can be seen from the update rule of $V^\LCB$.

In the following, let us bound the two halves of the qunatity in (<ref>) separately. Notice that the first half coincides with $\zeta_{t,1}$ in Lemma <ref> (defined in (<ref>)). Thus, there exists some absolute constant $C_{\mathrm{v},1}>0$ such that we have

\begin{align}
&\quad\ \sum_{t=1}^{T}w_t\big(V_{t}(s_{t+1}) - Q_{t+1}(s_{t+1},a_{t+1})\big) \notag\\
&= V_{T}(s_{T+1}) - Q_{T+1}(s_{T+1},a_{T+1}) + \sum_{t=1}^{T-1}w_t\big(V_{t}(s_{t+1}) - Q_{t+1}(s_{t+1},a_{t+1})\big) \notag\\
&\overset{(\mathrm{i})}{\le} \frac{1}{1-\gamma} + \sum_{t=2}^{T}w_{t-1}\big(V_{t-1}(s_{t}) - Q_{t}(s_{t},a_{t})\big) \notag\\
&\overset{(\mathrm{ii})}{\le} \frac{1}{1-\gamma} + \sum_{t=1}^{T}w_{t-1}\big(V_{t-1}(s_{t}) - Q_{t}(s_{t},a_{t})\big) \notag\\
&= \frac{1}{1-\gamma} + \sum_{t=1}^{T}w_t\zeta_{t,1} \notag\\
&\le \frac{1}{1-\gamma} + w\sum_{t=1}^{T}\zeta_{t,1} \notag\\
&\overset{(\mathrm{iii})}{\lesssim} \frac{wSA}{1-\gamma}\log T + \frac{w\left(SA\right)^{3/4}T^{1/4}}{(1-\gamma)^{5/4}}\left(\log\frac{SAT}{\delta}\right)^{5/4} + w\sqrt{\frac{SA\log^2 T}{1-\gamma}\sum_{t=1}^T \big(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)} \notag\\
&\leq C_{\mathrm{v},1}\left(\frac{wSA}{1-\gamma}\log T + \frac{w\left(SA\right)^{3/4}T^{1/4}}{(1-\gamma)^{5/4}}\left(\log\frac{SAT}{\delta}\right)^{5/4} + w\sqrt{\frac{SA\log^2 T}{1-\gamma}\sum_{t=1}^T \big(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)}\right), \label{eq:weighted-V-1-1}
\end{align}

Above, (i) is due to $V_{T}(s_{T+1}) \le \frac{1}{1-\gamma}$ and $Q_{T+1}(s_{T+1},a_{T+1}) \ge Q^\star(s_{T+1},a_{T+1}) \ge 0$. (ii) is due to $V_{0}(s_{1}) - Q_{1}(s_{1},a_{1}) \ge 0$, as we set $V_{0}(s) = \frac{1}{1-\gamma}$ for any $s\in\cS$ in the proof of Lemma <ref>. (iii) is by (<ref>). $C_{\mathrm{v},1}>0$ is some absolute constant.

Adopting the abbreviation $N_t := N_t(s_{t+1},a_{t+1})$ and $t_n := t_n(s_{t+1},a_{t+1})$ hereafter, we can expand the second half of (<ref>) using (<ref>) as follows:

\begin{align}
&\quad\ \sum_{t=1}^{T}w_t\left(Q_{t+1}(s_{t+1},a_{t+1}) - Q_{t+1}^{\LCB}(s_{t+1},a_{t+1})\right) \notag\\
&\le \sum_{t=1}^{T}\frac{w_t\eta^{N_t}_0}{1-\gamma}
+ \gamma w_t\sum_{n = 1}^{N_t} \eta^{N_t}_n \left(V_{t_n}(s_{t_n+1}) - V^{\LCB}_{t_n}(s_{t_n+1}) \right) + 4 c_b w_t \sqrt{\frac{\log \frac{SAT}{\delta}}{(1-\gamma)^3 N_t}} \notag\\
&\le \frac{SAw}{1-\gamma} + \gamma\sum_{t=1}^T \widetilde{w}_t\left(V_{t}(s_{t+1}) - V^{\LCB}_{t}(s_{t+1})\right) + 8c_b \sqrt{\frac{SAwW\log \frac{SAT}{\delta}}{(1-\gamma)^3}}. \label{eq:weighted-V-1-2}
\end{align}

The last step is due to the following two chain of inequalities (<ref>) and (<ref>):

\begin{align}
&\quad\ 4c_b\sum_{t=1}^T w_t\sqrt{\frac{\log \frac{SAT}{\delta}}{(1-\gamma)^3 N_{t}}}\notag\\
&= 4c_b\sum_{(s,a)\in\cS\times\cA}\sum_{n=1}^{N_{T}(s,a)}w_{t_n}\sqrt{\frac{\log \frac{SAT}{\delta}}{(1-\gamma)^3 n}}\notag\\
&\leq 4c_b\sum_{(s,a)\in\cS\times\cA}\sum_{n=1}^{\bar{N}_{T}(s,a)/w}w\sqrt{\frac{\log \frac{SAT}{\delta}}{(1-\gamma)^3 n}}\notag\\
&\leq 4c_b\sum_{(s,a)\in\cS\times\cA}\int_{n=1}^{\bar{N}_{T}(s,a)/w}w\sqrt{\frac{\log \frac{SAT}{\delta}}{(1-\gamma)^3 n}}\notag\\
&\le 8c_b\sum_{(s,a)\in\cS\times\cA}\sqrt{\frac{w\bar{N}_{T}(s,a)\log \frac{SAT}{\delta}}{(1-\gamma)^3}}\notag\\
&\leq 8c_b\sqrt{\sum_{(s,a)\in\cS\times\cA}\frac{w\log \frac{SAT}{\delta}}{(1-\gamma)^3}}\sqrt{\sum_{(s,a)\in\cS\times\cA}\bar{N}_{T}(s,a)}\notag\\
&= 8c_b \sqrt{\frac{SAwW\log \frac{SAT}{\delta}}{(1-\gamma)^3}}, \label{eq:weighted-V-1-2.1}
\end{align}

in which we define $\bar{N}_{T}(s,a) := \sum_{t=1}^T w_t\ind_{(s_{t},a_{t}) = (s,a)}$, and

\begin{align}
&\quad\ \gamma \sum_{t=1}^T w_t\sum_{n = 1}^{N_{t}} \eta^{N_t}_n \left(V_{t_n}(s_{t_n+1}) - V^{\LCB}_{t_n}(s_{t_n+1}) \right)\notag\\
&\leq \gamma \sum_{t=1}^T \left(V_{t}(s_{t+1}) - V^{\LCB}_{t}(s_{t+1}) \right) \sum_{n = N_{t+1}}^{N_{T}} w_{t_n}\eta^n_{N_t}, \label{eq:weighted-V-1-2.2}
\end{align}

in which we define $\widetilde{w}_t := \sum_{n = N_{t+1}}^{N_{T}} w_{t_n}\eta^n_{N_t}$. Note that $\widetilde{w}_t \le \frac{(3-\gamma)}{2}w$ by (<ref>) in Lemma <ref>.

Combining (<ref>) and (<ref>), we have

\begin{align}
&\quad\ \sum_{t=1}^{T}w_t\left(V_{t}(s_{t+1})-V_{t}^{\LCB}(s_{t+1})\right) \notag\\
&\le C_{\mathrm{v},1}\frac{w\left(SA\right)^{3/4}T^{1/4}}{(1-\gamma)^{5/4}}\left(\log\frac{SAT}{\delta}\right)^{5/4} + C_{\mathrm{v},1}\frac{SAw}{1-\gamma}\log T + 8c_b \sqrt{\frac{SAwW\log \frac{SAT}{\delta}}{(1-\gamma)^3}} \notag\\ &\quad + C_{\mathrm{v},1}w\sqrt{\frac{SA\log^2 T}{1-\gamma}\sum_{t=1}^T \big(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)} + \gamma\sum_{t=1}^T \widetilde{w}_t\left(V_{t}(s_{t+1}) - V^{\LCB}_{t}(s_{t+1})\right) \label{eq:weighted-V-2}\\
&\overset{(\mathrm{i})}{\le} C_{\mathrm{v},1}\frac{ew\left(SA\right)^{3/4}T^{1/4}}{(1-\gamma)^{9/4}}\left(\log\frac{SAT}{\delta}\right)^{5/4} + C_{\mathrm{v},1}\frac{eSAw}{(1-\gamma)^2}\log T + 8ec_b \sqrt{\frac{SAwW\log \frac{SAT}{\delta}}{(1-\gamma)^5}} \notag\\ &\quad + C_{\mathrm{v},1}ew\sqrt{\frac{SA\log^2 T}{(1-\gamma)^3}\sum_{t=1}^T \big(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)} + \gamma^{H_{\mathrm{v}}}\frac{eW}{1-\gamma}\notag\\
&\le C_{\mathrm{v},1}\frac{ew\left(SA\right)^{3/4}T^{1/4}}{(1-\gamma)^{9/4}}\left(\log\frac{SAT}{\delta}\right)^{5/4} + C_{\mathrm{v},1}\frac{eSAw}{(1-\gamma)^2}\log T + 8ec_b \sqrt{\frac{SAwW\log \frac{SAT}{\delta}}{(1-\gamma)^5}} \notag\\ &\quad + C_{\mathrm{v},1}ew\sqrt{\frac{SA\log^2 T}{(1-\gamma)^3}\sum_{t=1}^T \big(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)} + eW, \label{eq:weighted-V-3}
\end{align}

where (i) is obtained by applying (<ref>) recursively for $H_{\mathrm{v}} := \lceil\frac{\ln \frac{1}{1-\gamma}}{\ln \frac{1}{\gamma}}\rceil$ times and the fact that $(1+\frac{1-\gamma}{2})^{H_{\mathrm{v}}} < (1+\frac{1-\gamma}{2})^{\lceil\frac{1}{1-\gamma}\rceil} < (1+\frac{1-\gamma}{2})^{\frac{2}{1-\gamma}} < e$, which is true since $\gamma \ge \frac{1}{2}$ and $H_{\mathrm{v}} < \lceil\frac{1}{1-\gamma}\rceil$. We also use the fact $\norm{V_t - V_t^\LCB}_\infty \le \frac{1}{1-\gamma}$.

§ PROOF OF LEMMA <REF>

§.§ Proof of Inequality (<ref>)

In the proof of this lemma, let us adopt the shorthand notation $t_i := t_i(s)$ to denote the index of the time step in which state $s$ is visited for the $i$-th time. We can use this notation for any state $s$ that has been visited at least once during the $T$ steps of our algorithm's execution. Note that for each $s$, both $V^{\rref}_t(s)$ and $V_{t}(s)$ are only updated when $t = t_i + 1$ with indices $i$ from $\{i ~:~ 1\leq t_i\leq T\}$. Thus, to establish (<ref>), it suffices to show that for any $s$ and its corresponding $1\leq t_i \leq T$,

\begin{align}
\left| V_{t_i+1} (s) - V_{t_i+1}^{\rref} (s) \right| \leq 6.
\label{eq:VR-V-proximity1}
\end{align}

In the following, let us fix any $s$ and prove (<ref>) by looking at three partition scenarios separately.

Case 1 of (<ref>). Suppose that $t_i$ satisfies either Line <ref> or Line <ref> of Algorithm <ref>, i.e., either

\begin{align}
&V_{t_i+1} (s) - V_{t_i+1}^{\LCB} (s) > 3  \label{eq:condition-ti-update-1}
\end{align}

\begin{align}
&V_{t_i+1} (s) - V_{t_i+1}^{\LCB} (s) \leq 3 \qquad \text{and} \qquad
u^{\re}_{t_i}(s) = \mathsf{True}.  \label{eq:condition-ti-update-2}
\end{align}

Either of these two conditions would trigger the update of the reference value function and thus result in

$$V_{t_i+1} (s) = V_{t_i+1}^{\rref} (s),$$

which satisfies (<ref>) trivially.

Case 2 of (<ref>).
Suppose that $t_{i_0}$ is the first time such that both (<ref>) and (<ref>) are violated, i.e.,

\begin{align}
{i_0} \coloneqq \min\left\{ j\mid V_{t_{j}+1}(s)-V_{t_j+1}^{\LCB}(s)\leq 3 ~\text{ and }~ u^{\re}_{t_j}(s) = \mathsf{False}\right\}.
\label{eq:def-first-i-violate-condition}
\end{align}

In the following, let us show (<ref>) is true when $i = i_0$.

First, notice that the definition (<ref>) (first time both (<ref>) and (<ref>) are violated) suggests that the reference was updated last time $s$ was visited before the $t_{i_0}$-th step, i.e., $V^{\rref}_{t_{i_0-1}+1}$ was updated in the $t_{i_0-1}$-th step. Notice that since $s$ is not visited during the interval when the step index $t$ satisfies $t_{i_0-1}+1\le t \le t_{i_0}-1$, $V_{t+1}(s)$ is not updated during this period, nor is the block between Line <ref>-<ref> of Algorithm <ref> triggered (which would update the reference $V_{t+1}^\rref(s)$). Thus, we can conclude

\begin{align}
\label{eq:lcb-final-value0}
\end{align}

Furthermore, since the reference $V^{\rref}_{t_{i_0-1}+1}$ was updated in the $t_{i_0-1}$-th step, this indicates either (<ref>) or (<ref>) is satisfied in this step. If (<ref>) is satisfied, then Line <ref> and <ref> of Algorithm <ref> tell us that $\mathsf{True} = u^{\re}_{t_{i_0-1}+1}(s)$ and Line <ref> is never triggered between Step $t_{i_0 -1}+1$ and Step $t_{i_0}-1$, which implies $u^{\re}_{t_{i_0}}(s) = u^{\re}_{t_{i_0-1}+1}(s) = \mathsf{True}$. However, this contradicts with the assumption $u^{\re}_{t_{i_0}}(s) = \mathsf{False}$ in (<ref>). Hence, only (<ref>) is true at the $t_{i_0-1}$-th step, which allows us to conclude

\begin{align}\label{eq:lcb-final-value2}
V_{t_{i_0}} (s) - V_{t_{i_0}}^{\LCB} (s)  = V_{t_{i_0-1}+1} (s) - V_{t_{i_0-1}+1}^{\LCB} (s) \leq 3.
\end{align}

On the other hand, the definition (<ref>) suggests that $V^{\rref}_{t_{i_0} + 1}(s)$ is not updated by the update block between Line <ref>-<ref> at Step $t_{i_0}$, so we have

\begin{align}\label{eq:lcb-final-value}
V_{t_{i_0}+1}^{\rref} (s) = V_{t_{i_0}}^{\rref} (s).
\end{align}

Finally, combining (<ref>), (<ref>) and (<ref>), we can derive that

\begin{align}
V^{\rref}_{t_{i_0}+1}(s) -V_{t_{i_0} + 1 }(s)
&\overset{\mathrm{(i)}}{=}  V^{\rref}_{t_{i_0}}(s) -V_{t_{i_0} + 1 }(s)
\overset{\mathrm{(ii)}}{=}  V_{t_{i_0}}(s) - V_{t_{i_0} + 1 }(s) \label{eq:ref-final-value0}\\
& \overset{\mathrm{(iii)}}{\leq} V_{t_{i_0}}(s) - V^{\LCB}_{t_{i_0}}(s)\overset{\mathrm{(iv)}}{\leq} 3,
\label{eq:ref-final-value1}
\end{align}

where (i) is due to (<ref>); (ii) is due to (<ref>); (iii) holds since $V_{t_{i_0} + 1}(s) \geq V^\star(s) \geq V^{\LCB}_{t_{i_0}}(s)$; (iv) follows from (<ref>).
In addition, let us point out that (<ref>), together with the monotonicity of $V_t(s)$, implies

\begin{align}
V^{\rref}_{t_{i_0}+1}(s) -V_{t_{i_0} + 1 }(s) =  V_{t_{i_0}}(s) - V_{t_{i_0} + 1 }(s) \geq 0. \label{eq:ref-final-value2}
\end{align}

By (<ref>) and (<ref>), we can arrive at the desired bound (<ref>) with $i=i_0$.

Case 3 of (<ref>). For the last case, consider any $i>i_0$ (that does not satisfy Case 1). Then it must be true that $V_{t_{i}+1}(s)-V_{t_i+1}^{\LCB}(s) \leq 3$ and $u^{\re}_{t_i}(s) = \mathsf{False}$, due to the monotonicity of $V$ and $V^{\LCB}$ and our algorithmic design that $u^{\re}(s)$ stays False once set to False.

It then follows that

\begin{align}
V_{t_i+1}^{\rref}(s) & \overset{(\mathrm{i})}{\leq}V_{t_{i_0}+1}^{\rref}(s)\overset{(\mathrm{ii})}{\leq}V_{t_{i_0}+1}(s)+3\overset{(\mathrm{iii})}{\leq}V_{t_{i_0}+1}^{\LCB}(s)+6 \overset{(\mathrm{iv})}{\leq}V^{\star}(s)+6\overset{(\mathrm{v})}{\leq}V_{t_{i}+1}(s)+6. \label{eq:VR-V-proximity1-1}
\end{align}

Here, (i) holds due to the monotonicity of $V_{t}$ and thus the monotonicity of $V^{\rref}_t$ ($V^{\rref}_t$ can only be updated from $V_t$); (ii) is a consequence of (<ref>); (iii) comes from the definition of $i_0$ in (<ref>); (iv) arises from the pessimism of $V^{\LCB}$ to $V^{\star}$ (see Lemma <ref>); (v) is valid since the optimism gives $V_{t_i + 1}(s) \geq V^{\star}(s)$ (see Lemma <ref>).

On the other hand, since $V_{t}$ is non-increasing in $t$ and $V^{\rref}_t$ can only be updated from $V_t$, we have that $V_{t_i+1}(s) \le V_{t_i+1}^{\rref}(s)$, which, combined with (<ref>), gives

$$0\leq V_{t_i+1}^{\rref}(s)- V_{t_i+1}(s) \leq 6$$

and thus justifies (<ref>) for this case.

Overall, taking the three aforementioned cases in conjunction, we can establishe (<ref>) and thus (<ref>) completely.

§.§ Proof of Inequality (<ref>)

First, let us suppose that

\begin{align}
V^{\rref}_{t}(s_{t+1}) - V^{\rref}_{T}(s_{t+1}) \neq 0
\label{eq:claim-Vt-VT}
\end{align}

holds for some $t < T$. Let $t$ be the largest number such that (<ref>) holds. Then it implies two possible scenarios:

Case 1. Suppose the following event is true

\begin{equation}
V_{t+1}(s_{t+1}) - V_{t+1}^{\LCB}(s_{t+1}) \leq 3 \quad \text{ and } \quad u^{\re}_{t}(s_{t+1}) = \mathsf{False}.
\label{eq:claim-Vt-VT-cond1}
\end{equation}

Then for any $t' \ge t + 1$, one necessarily has

\begin{align}
V_{t'}(s_{t+1}) - V_{t'}^{\LCB}(s_{t+1})
\leq V_{t+1}(s_{t+1}) - V_{t+1}^{\LCB}(s_{t+1}) \leq 3 \label{eq:claim-Vt-VT-conclusion1}
\end{align}

by the monotonicity of $V_{t}$ and $V_{t}^{\LCB}$. In addition, (<ref>) and our assumption $u^{\re}_t(s_{t+1}) = \mathsf{False}$ together can imply

\begin{align}
u^{\re}_{t'}(s_{t+1}) = u^{\re}_t(s_{t+1}) = \mathsf{False}, \label{eq:claim-Vt-VT-conclusion2}
\end{align}

because both conditions in Line <ref> and Line <ref> of Algorithm <ref> would be violated at the $(t+1)$-th step and stay so thereafter.

(<ref>) and (<ref>) imply that the reference $V^{\rref}$ will no longer be updated after the $t$-th step, thus indicating that

\begin{align}
V^{\rref}_{t} = V^{\rref}_{t+1} = \cdots = V^{\rref}_{T}.
\end{align}

However, this contradicts with the assumption (<ref>), so by the contrapositive, (<ref>) would imply this case is impossible.

Case 2. As the complement event of Case 1, if the condition in (<ref>) is false, then it implies that either

\begin{equation}\label{eq:claim-Vt-VT-cond2-1}
V_{t+1}(s_{t+1}) - V_{t+1}^{\LCB}(s_{t+1}) > 3,
\end{equation}

\begin{align}\label{eq:claim-Vt-VT-cond2-2}
V_{t+1}(s_{t+1}) - V_{t+1}^{\LCB}(s_{t+1}) \leq 3 \quad \text{and} \quad
u^{\re}_t(s_{t+1}) = \mathsf{True}.
\end{align}

In summary, we have just shown that (<ref>) can only occur if either (<ref>) or (<ref>) holds. In light of this, we can decompose the quantity of interest with respect to these two cases as follows:

\begin{align}
&\quad\ \sum_{t=1}^{T}\left(V_{t}^{\rref}(s_{t+1})-V_{T}^{\rref}(s_{t+1})\right) \notag\\
&= \sum_{t=1}^{T}\left(V_{t}^{\rref}(s_{t+1})-V_{T}^{\rref}(s_{t+1})\right)\ind\left\{V_{t}^{\rref}(s_{t+1})-V_{T}^{\rref}(s_{t+1})\neq 0\right\}\notag\\
&\le \sum_{t=1}^{T}\left(V_{t}^{\rref}(s_{t+1})-V_{T}^{\rref}(s_{t+1})\right)\ind\left\{V_{t+1}(s_{t+1}) - V_{t+1}^{\LCB}(s_{t+1}) \leq 3 \text{ and } u^{\re}_t(s_{t+1}) = \mathsf{True}\right\}\notag\\
& \qquad+ \sum_{t=1}^{T}\left(V_{t}(s_{t+1})-V_{t}^{\LCB}(s_{t+1})\right)\ind\left\{V_{t+1}(s_{t+1}) - V_{t+1}^{\LCB}(s_{t+1})>3\right\},
\label{eq:Vt-VT-1}
\end{align}

where the inequality is because $V_{t}(s_{t+1}) \ge V_{t}^{\rref}(s_{t+1})$, which is due to the monotonicity of $V_t$ and the fact that $V^{\rref}$ can only be updated from $V$, as well as the fact that

\begin{equation*}
V^{\rref}_{T}(s_{t})  \geq V^\star(s_{t}) \geq V^{\LCB}_{t}(s_{t}),
\end{equation*}

which is due to the optimism of $V$ and thus $V^{\rref}$ and the pessimism of $V^{\LCB}_t$ in Lemma <ref> and Lemma <ref> respectively.

The first term in (<ref>) can be easily bounded because for all $s\in \cS$,

\begin{align}
\sum_{t=1}^{T}\ind\left\{V_{t+1}(s) - V_{t+1}^{\LCB}(s) \leq 3 \text{ and }
u^{\re}_t(s) = \mathsf{True}\right\} \leq 1. \label{eq:Vt-VT-1.1}
\end{align}

This is because for each $s\in \cS$, the above condition is satisfied at most once, in view of the monotonicity property of $V_t$ and $V_t^{\LCB}$ (their gap only grows smaller over time) as well as the update rule of $u_{\re}$ in Algorithm <ref>. Consequently, one has

\begin{align*}
&\quad\ \sum_{t=1}^{T}\left(V_{t}^{\rref}(s_{t+1})-V_{T}^{\rref}(s_{t+1})\right)\ind\left\{V_{t+1}(s_{t+1}) - V_{t+1}^{\LCB}(s_{t+1}) \leq 3 \text{ and } u^{\re}_t(s_{t+1}) = \mathsf{True}\right\}\notag\\
& \leq \frac{1}{1-\gamma}\sum_{t=1}^{T}\ind\left\{V_{t+1}(s_{t+1}) - V_{t+1}^{\LCB}(s_{t+1}) \leq 3 \text{ and } u^{\re}_t(s_{t+1}) = \mathsf{True}\right\}\notag\\
& \le \frac{1}{1-\gamma}\sum_{s\in\mathcal{S}}\sum_{t=1}^{T}\ind\left\{V_{t+1}(s) - V_{t+1}^{\LCB}(s) \leq 3 \text{ and } u^{\re}_t(s) = \mathsf{True}\right\} \notag\\
& \leq \frac{1}{1-\gamma}\sum_{s\in\mathcal{S}}1=\frac{S}{1-\gamma},
\end{align*}

where the first inequality holds since $\norm{V_{t}^{\rref}-V_{T}^{\rref}}_\infty\leq \frac{1}{1-\gamma}$.

To complete this proof, it remains to bound the second term in (<ref>). By the monotonicity in $V_t$ and $V_t^\LCB$,

\begin{align}
&\quad\ \sum_{t=1}^{T}\left(V_{t}(s_{t+1})-V_{t}^{\LCB}(s_{t+1})\right)\mathds{1}\left\{V_{t+1}(s_{t+1}) - V_{t+1}^{\LCB}(s_{t+1})>3\right\} \nonumber \\
&\le \sum_{t=1}^{T}\left(V_{t}(s_{t+1})-V_{t}^{\LCB}(s_{t+1})\right)\mathds{1}\left\{V_{t}(s_{t+1}) - V_{t}^{\LCB}(s_{t+1})>3\right\} \nonumber \\
&\lesssim \frac{\left(SA\right)^{3/4}T^{1/4}}{(1-\gamma)^{13/4}}\left(\log\frac{SAT}{\delta}\right)^{5/4} + \frac{SA}{(1-\gamma)^6}\log \frac{SAT}{\delta} + \sqrt{\frac{SA\log^2 T}{(1-\gamma)^5}\sum_{t=1}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)},\label{eq:ref-error-upper-final}
\end{align}

where the last inequality is by (<ref>) in Lemma <ref> and $\norm{V_{t}-V_{t}^{\LCB}}_\infty\leq \frac{1}{1-\gamma}$.

Finally, combining (<ref>) and (<ref>), we can conclude

\begin{align}
&\quad\ \sum_{t=1}^{T}\left(V_{t}^{\rref}(s_{t+1})-V_{T}^{\rref}(s_{t+1})\right) \notag\\
& \lesssim \frac{\left(SA\right)^{3/4}T^{1/4}}{(1-\gamma)^{13/4}}\left(\log\frac{SAT}{\delta}\right)^{5/4} + \frac{SA}{(1-\gamma)^6}\log \frac{SAT}{\delta} + \sqrt{\frac{SA\log^2 T}{(1-\gamma)^5}\sum_{t=1}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)}
\end{align}

as claimed.

§ PROOF OF LEMMA <REF>

For notational simplicity, let us adopt the shorthand notation $t_n := t_n(s_t, a_t)$ throughout this section. Recall the update rule of $Q^{\rref}_{t+1}(s_t, a_t)$ in Line <ref> of Algorithm <ref>. We can derive

\begin{align}
&\quad\ Q^{\rref}_t(s_t,a_t) - Q^{\star}(s_t,a_t) \notag\\
&= Q^{\rref}_{t_{N_{t-1}(s_t,a_t)}+1}(s_t,a_t) - Q^{\star}(s_t,a_t) \notag\\
&= \eta^{N_{t-1}(s_t,a_t)}_0 \left(Q^{\rref}_1(s_t,a_t) - Q^{\star}(s_t,a_t)\right) + \sum_{n = 1}^{N_{t-1}(s_t,a_t)} \eta^{N_{t-1}(s_t,a_t)}_n b^{\rref}_{t_{n}+1} \notag\\
&\qquad+  \gamma\sum_{n = 1}^{N_{t-1}(s_t,a_t)} \eta^{N_{t-1}(s_t,a_t)}_n  \left(V_{t_n}(s_{t_n+1}) - V^{\rref}_{t_n}(s_{t_n+1})+\frac{1}{n}\sum_{i=1}^{n}\Big(V^{\rref}_{t_i}(s_{t_i+1})-P_{s_t,a_t}V^{\star}\Big)\right)\notag\\
&\le \frac{\eta^{N_{t-1}(s_t,a_t)}_0}{1-\gamma} + \sum_{n = 1}^{N_{t-1}(s_t,a_t)} \eta^{N_{t-1}(s_t,a_t)}_n b^{\rref}_{t_{n}+1} \notag\\
&\qquad+  \gamma\sum_{n = 1}^{N_{t-1}(s_t,a_t)} \eta^{N_{t-1}(s_t,a_t)}_n  \left(V_{t_n}(s_{t_n+1}) - V^{\rref}_{t_n}(s_{t_n+1})+\frac{1}{n}\sum_{i=1}^{n}\Big(V^{\rref}_{t_i}(s_{t_i+1})-P_{s_t,a_t}V^{\star}\Big)\right)\notag\\
&\le \frac{\eta^{N_{t-1}(s_t,a_t)}_0}{1-\gamma} + B^{\rref}_{t}(s_t,a_t) + 2c_b\frac{\log^2\frac{SAT}{\delta}}{\left(N_{t-1}(s_t,a_t)\right)^{3/4}(1-\gamma)^2}\notag\\
& \qquad + \gamma\sum_{n = 1}^{N_{t-1}(s_t,a_t)} \eta^{N_{t-1}(s_t,a_t)}_n  \left(V_{t_n}(s_{t_n+1}) - V^{\rref}_{t_n}(s_{t_n+1})+\frac{1}{n}\sum_{i=1}^{n}\Big(V^{\rref}_{t_i}(s_{t_i+1})-P_{s_t,a_t}V^{\star}\Big)\right),\notag
\end{align}

where the penultimate line follows from our initialization $Q^{\rref}_1(s_t, a_t) = \frac{1}{1-\gamma}$ and the last line follows from (<ref>) with $B^{\rref}_{N_{t-1}+1} = B^{\rref}_t$. With the inequality above, we can sum over $1 \le t \le T$ and have

\begin{align}
&\quad\ \sum_{t = 1}^{T} Q^{\rref}_t(s_t, a_t) - Q^{\star}(s_t, a_t) \nonumber \\
&\le \sum_{t = 1}^{T} \left(\frac{\eta^{N_{t-1}(s_t,a_t)}_0}{1-\gamma} + B^{\rref}_{t}(s_t,a_t) + 2c_b\frac{\log^2\frac{SAT}{\delta}}{\left(N_{t-1}(s_t,a_t)\right)^{3/4}(1-\gamma)^2}\right)\nonumber\\
& \qquad + \gamma\sum_{t = 1}^{T} \sum_{n = 1}^{N_{t-1}(s_t,a_t)} \eta^{N_{t-1}(s_t,a_t)}_n \left(V_{t_n}(s_{t_n+1}) - V^{\rref}_{t_n}(s_{t_n+1})+\frac{1}{n}\sum_{i=1}^{n}V^{\rref}_{t_i}(s_{t_i+1})-P_{s_t,a_t}V^{\star}\right)\nonumber\\
&\le \underbrace{\sum_{t = 1}^{T} \left(\frac{\eta^{N_{t-1}(s_t,a_t)}_0}{1-\gamma} + B^{\rref}_{t}(s_t,a_t) + 2c_b\frac{\log^2\frac{SAT}{\delta}}{\left(N_{t-1}(s_t,a_t)\right)^{3/4}(1-\gamma)^2}\right)}_{(\mathrm{I})} \nonumber\\
& \qquad + \underbrace{\gamma\sum_{t = 1}^{T} \sum_{n = 1}^{N_{t-1}(s_t,a_t)} \eta^{N_{t-1}(s_t,a_t)}_n \Big(V_{t_n}(s_{t_n+1}) - V^\star(s_{t_n+1})\Big)}_{(\mathrm{II})} \nonumber\\
& \qquad + \underbrace{\gamma\sum_{t = 1}^{T} \sum_{n = 1}^{N_{t-1}(s_t,a_t)} \eta^{N_{t-1}(s_t,a_t)}_n \left(V^\star(s_{t_n+1}) - V^{\rref}_{t_n}(s_{t_n+1})+\frac{1}{n}\sum_{i=1}^{n}V^{\rref}_{t_i}(s_{t_i+1})-P_{s_t,a_t}V^{\star}\right)}_{(\mathrm{III})}. \label{eq:QR-Q*-1}
\end{align}

To finish the proof of this lemma, we control the three terms in (<ref>) separately.

(I) in (<ref>): We can bound (I) by making two observations. First, we have

\begin{align}\label{eq:QR-Q*-1.1}
\sum_{t = 1}^{T}\eta^{N_{t-1}(s_t,a_t)}_0
\leq \sum_{(s,a) \in \mathcal{S}\times \mathcal{A}} \sum_{n = 1}^{N_{T - 1}(s,a)}\eta^{n}_0 \leq SA ,
\end{align}

where the last inequality follows since $\eta_0^n = 0$ for all $n>0$. Then, we can observe that

\begin{align}\label{eq:QR-Q*-1.2}
\sum_{t = 1}^{T}  \frac{1}{\left(N_{t-1}(s_t, a_t) \right)^{3/4}} &= \sum_{(s,a) \in \mathcal{S}\times \mathcal{A}} \sum_{n=1}^{N_{T-1}(s,a) } \frac{1}{n^{3/4}} \leq \sum_{(s,a) \in \mathcal{S}\times \mathcal{A}} 4 \left(N_{T - 1}(s,a)\right)^{1/4} \notag\\
&\leq 4\left(\sum_{(s,a) \in \mathcal{S}\times \mathcal{A}} 1\right)^{3/4}  \left(\sum_{(s,a) \in \mathcal{S}\times \mathcal{A}}  N_{T - 1}(s,a) \right)^{1/4} \leq 4(SA)^{3/4}T^{1/4},
\end{align}

where the penultimate inequality is due to Hölder's inequality.

Applying the above two bounds to (I) yields

\begin{align}
&\quad\ \sum_{t = 1}^{T} \left(\frac{\eta^{N_{t-1}(s_t,a_t)}_0}{1-\gamma} + B^{\rref}_{t}(s_t,a_t) + 2c_b\frac{\log^2\frac{SAT}{\delta}}{(N_{t-1}(s_t,a_t))^{3/4}(1-\gamma)^2}\right) \notag\\
&\leq \frac{SA}{1-\gamma}+8c_b(SA)^{3/4}T^{1/4}\frac{1}{(1-\gamma)^2}\log^2\frac{SAT}{\delta}+\sum_{t=1}^{T} B^{\rref}_{t}(s_t,a_t) .
\end{align}

(II) in (<ref>): It can be obtained via some algebra that

\begin{align}
&\quad\ \gamma\sum_{t = 1}^{T} \sum_{n = 1}^{N_{t-1}(s_t,a_t)} \eta^{N_{t-1}(s_t,a_t)}_n \big(V_{t_n}(s_{t_n+1}) - V^\star(s_{t_n+1})\big)\notag\\
&= \gamma\sum_{l = 1}^{T} \sum_{N = N_{l}(s_l,a_l)}^{N_{T-1}(s_l,a_l)} \eta_{N_{l}(s_l,a_l)}^N \big(V_{l}(s_{l+1}) - V^\star(s_{l+1})\big)\notag\\
&\le \gamma\left(1 + \frac{1-\gamma}{2}\right)\sum_{t = 1}^{T} \big(V_{t}(s_{t+1}) - V^\star(s_{t+1})\big).
\end{align}

Above, the second line replaces $t_n$ (resp. $n$) with $l$ (resp. $N_l(s_l, a_l)$), and the last line is due to (<ref>) in Lemma <ref>) and replaces $l$ with $t$ again.

(III) in (<ref>): (III) can derived in the following manner:

\begin{align*}
&\quad\ \gamma\sum_{t = 1}^{T} \sum_{n = 1}^{N_{t-1}(s_t,a_t)} \eta^{N_{t-1}(s_t,a_t)}_n  \left(V^\star(s_{t_n+1}) - V^{\rref}_{t_n}(s_{t_n+1})+\frac{1}{n}\sum_{i=1}^{n}\Big(V^{\rref}_{t_i}(s_{t_i+1})-P_{s_t,a_t}V^{\star}\Big)\right)\nonumber \\
&= \gamma\sum_{t = 1}^{T} \sum_{n = 1}^{N_{t-1}(s_t,a_t)} \eta^{N_{t-1}(s_t,a_t)}_n  \left(\left(P_{t_n} - P_{s_t,a_t}\right)\left(V^\star - V^{\rref}_{t_n}\right)+\frac{1}{n}\sum_{i=1}^{n}\Big(V^{\rref}_{t_i}(s_{t_i+1})-P_{s_t,a_t}V^{\rref}_{t_n}\Big)\right)\nonumber \\
&= \gamma\sum_{t = 1}^{T} \sum_{N = N_{t}(s_t,a_t)}^{N_{T-1}(s_t,a_t)} \eta_{N_{t}(s_t,a_t)}^N \left(\left(P_{t} - P_{s_t,a_t}\right)\left(V^\star - V^{\rref}_{t}\right)+ \frac{\sum_{i=1}^{N_t(s_t,a_t)}\left(V^{\rref}_{t_i}(s_{t_i+1})-P_{s_t,a_t}V^{\rref}_t\right)}{N_t(s_t,a_t)}\right).
\end{align*}

Here, the second line is obtained by $V^\star(s_{t_n+1}) - V^{\rref}_{t_n}(s_{t_n+1}) = P_{t_n} \left(V^{\star} - V^{\rref}_{t_n} \right)$, and the third line is by a simple rearrangement of terms and replacement of $t_n$ (resp. $n$) with $t$ (resp. $N_t(s_t, a_t)$).

Furthermore, we can rearrange the terms in (<ref>) and write

\begin{align}
&\quad\ \sum_{t = 1}^{T} \big(Q^{\rref}_t(s_t, a_t) - Q^{\star}(s_t, a_t)\big) \notag\\
&\le  \gamma\left(1 + \frac{1-\gamma}{2}\right)\sum_{t = 1}^{T} \big(V_{t}(s_{t+1}) - V^\star(s_{t+1})\big) + \frac{SA}{1-\gamma} +8c_b(SA)^{3/4}T^{1/4}\frac{1}{(1-\gamma)^2}\log\frac{SAT}{\delta} + \underbrace{\sum_{t=1}^{T} B^{\rref}_{t}(s_t,a_t)}_{\cR_1}\notag\\
&\quad + \underbrace{\gamma\sum_{t = 1}^{T} \sum_{N = N_{t}(s_t,a_t)}^{N_{T-1}(s_t,a_t)} \eta_{N_{t}(s_t,a_t)}^N \left[\left(P_{t} - P_{s_t,a_t}\right)\left(V^\star - V^{\rref}_{t}\right)+ \frac{\sum_{i=1}^{N_t(s_t,a_t)}\left(V^{\rref}_{t_i}(s_{t_i+1})-P_{s_t,a_t}V^{\rref}_t\right)}{N_t(s_t,a_t)}\right]}_{\cR_2},
\label{eq:QR-Q*-2}
\end{align}

where the upper bounds of $\cR_1$ and $\cR_2$ are derived in Appendix <ref> and <ref> respectively.

Overall, taking the obtained upper bounds on $\cR_1$ and $\cR_2$, we can conclude with probability $1-\delta$ that

\begin{align}
&\quad\ \sum_{t = 1}^{T} \big(Q^{\rref}_t(s_t, a_t) - Q^{\star}(s_t, a_t)\big) \notag\\
&\leq \gamma\left(1 + \frac{1-\gamma}{2}\right)\sum_{t = 1}^{T} \big(V_{t}(s_{t+1}) - V^\star(s_{t+1})\big) + C_{\mathrm{r},1}\Bigg(\sqrt{\frac{SAT}{1-\gamma}\log\frac{SAT}{\delta}} + \frac{SA}{(1-\gamma)^{15/4}}\log^{7/2}\frac{SAT}{\delta}\Bigg) \notag\\
&\qquad + \frac{SA}{1-\gamma} +8c_b(SA)^{3/4}T^{1/4}\frac{1}{(1-\gamma)^2}\log\frac{SAT}{\delta}\notag\\
&\qquad + C_{\mathrm{r},2}\Bigg(\sqrt{\frac{SAT}{1-\gamma}\log^{3}\frac{SAT}{\delta}} + \frac{SA}{(1-\gamma)^7}\log^{5/2} \frac{SAT}{\delta} + \sqrt{\frac{SA\log^2 T}{(1-\gamma)^5}\sum_{t=1}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)}\Bigg) \notag\\
&\leq \gamma\left(1 + \frac{1-\gamma}{2}\right)\sum_{t = 1}^{T} \left(V_{t}(s_{t+1}) - V^\star(s_{t+1})\right) + C_{\mathrm{r},1}\Bigg(\sqrt{\frac{SAT}{1-\gamma}\log\frac{SAT}{\delta}} + \frac{SA}{(1-\gamma)^{15/4}}\log^{7/2}\frac{SAT}{\delta}\Bigg) \notag\\
&\qquad + 8c_b\sqrt{\frac{SAT}{1-\gamma}\log\frac{SAT}{\delta}} + 8c_b\frac{SA}{(1-\gamma)^{7/2}}\log^{3/2}\frac{SAT}{\delta}\notag\\
&\qquad + C_{\mathrm{r},2}\Bigg(\sqrt{\frac{SAT}{1-\gamma}\log^{3}\frac{SAT}{\delta}} + \frac{SA}{(1-\gamma)^7}\log^{5/2} \frac{SAT}{\delta} + \sqrt{\frac{SA\log^2 T}{(1-\gamma)^5}\sum_{t=1}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)}\Bigg) \notag\\
&\leq \gamma\left(1 + \frac{1-\gamma}{2}\right)\sum_{t = 1}^{T} \left(V_{t}(s_{t+1}) - V^\star(s_{t+1})\right) + C_1\Bigg(\sqrt{\frac{SAT}{1-\gamma}\log^{3}\frac{SAT}{\delta}} + \frac{SA}{(1-\gamma)^7}\log^{7/2} \frac{SAT}{\delta} \notag\\
&\qquad + \sqrt{\frac{SA\log^2 T}{(1-\gamma)^5}\sum_{t=1}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)}\Bigg), \label{eq:QR-Q*-UB-final}
\end{align}

in which the penultimate step uses $2ab \le a^2+b^2$, which follows from Cauchy-Schwarz. $C_1 > 0$ is a sufficiently large absolute constant.

At this point, we have proven the desired result.

§.§ Bounding $\cR_1$

By the definition of $B^{\rref}_t(s_t, a_t)$ in Line <ref> of Algorithm <ref>, we can decompose $\mathcal{R}_1$ as follows:

\begin{align}
\cR_1 &= \underbrace{c_b\sqrt{\frac{1}{1-\gamma}\log\frac{SAT}{\delta}}\sum_{t=1}^{T}\sqrt{\frac{\sigma^{\mathrm{adv}}_{t}(s_t, a_t) - \left(\mu^{\mathrm{adv}}_{t}(s_t, a_t)\right)^2}{N_t(s_t,a_t)}}}_{\cR_{1,1}} \nonumber\\
&\qquad\qquad\qquad\qquad\qquad + \underbrace{c_b\sqrt{\log\frac{SAT}{\delta}}\sum_{t=1}^{T}\sqrt{\frac{\sigma^{\re}_{t}(s_t, a_t) - \left(\mu^{\re}_{t}(s_t, a_t)\right)^2}{N_t(s_t,a_t)}}}_{\cR_{1,2}}. \label{eq:R1-def1}
\end{align}

We proceed by bounding the two terms in (<ref>) separately.

Step 1: bounding $\cR_{1,1}$.
Some manipulation on the summation part of $\cR_{1,1}$ gives

\begin{align}
&\quad\ \sum_{t=1}^{T}\sqrt{\frac{\sigma^{\mathrm{adv}}_{t}(s_t, a_t) - \left(\mu^{\mathrm{adv}}_{t}(s_t, a_t)\right)^2}{N_t(s_t,a_t)}} \nonumber \\
&\le \sum_{t=1}^{T}\sqrt{\frac{\sigma^{\mathrm{adv}}_{t}(s_t, a_t)}{N_t(s_t,a_t)}} \nonumber \\
&= \sum_{t=1}^{T}\sqrt{\frac{\sum_{n=1}^{N_{t}(s_t,a_t)}\eta_{n}^{N_{t}(s_t,a_t)}\left(V_{t_n}(s_{t_n+1}) - V^{\rref}_{t_n}(s_{t_n+1})\right)^{2}}{N_t(s_t, a_t)}} \nonumber\\
&\le \sum_{t = 1}^T\sqrt{\frac{81}{N_t(s_t,a_t)}} \nonumber\\
&\le 18\sqrt{SAT}, \label{eq:R11-1}
\end{align}

in which the first inequality follows from the update rule of $\sigma_t^{\adv}$ in Line <ref> of Algorithm <ref>, and the second inequality uses the relation
$ |V_t(s_t) - V^{\rref}_{t}(s_t) | \le 9$ (cf. (<ref>)) and the property $\sum_{n = 1}^{N_t(s_t, a_t)} \eta^{N_t(s_t, a_t)}_n \leq 1$ (cf. (<ref>) in Lemma <ref>). The last inequality holds due to the following series of inequalities:

\begin{align}
\sum_{t = 1}^T\sqrt{\frac{1}{N_t(s_t,a_t)}} &= \sum_{(s, a)\in \cS\times \cA} \sum_{n = 1}^{N_t(s, a)} \sqrt{\frac{1}{n}} \notag\\
&\le 2 \sum_{(s, a)\in \cS\times \cA} \sqrt{N_t(s, a)} \notag \\
& \le  2  \sqrt{ \sum_{(s, a)\in \cS\times \cA} 1 } \cdot \sqrt{\sum_{(s,a)\in \cS\times \cA}N_t(s, a)}  =  2\sqrt{SAT}, \label{eq:sqrt-N-sum}
\end{align}

where the last line is obtained by Cauchy-Schwarz and the fact that $\sum_{(s,a)}N_t(s, a) = T$.

Overall, we have

\begin{equation}
\cR_{1,1} \le 9c_b\sqrt{\frac{SAT}{1-\gamma}\log\frac{SAT}{\delta}}. \label{eq:R11-final}
\end{equation}

Step 2: bounding $\cR_{1,2}$.

By the update rules of $\mu_t^{\re}$ and $\sigma_t^{\re}$ in (<ref>) and (<ref>), we can write the summation part of $\cR_{1,2}$ as

\begin{align}
&\quad\ \sum_{t=1}^{T}\sqrt{\frac{\sigma^{\re}_{t}(s_t, a_t) - \left(\mu^{\re}_{t}(s_t, a_t)\right)^2}{N_t(s_t,a_t)}} \nonumber \\
&= \sum_{t = 1}^T\sqrt{\frac{1}{N_t(s_t,a_t)}} \sqrt{ \frac{\sum_{n=1}^{N_{t}(s_t,a_t)}\left(V^{\rref}_{t_n}(s_{t_n+1}) \right)^2}{N_t(s_t,a_t)} - \left(\frac{\sum_{n=1}^{N_{t}(s_t,a_t)}V^{\rref}_{t_n}(s_{t_n+1})}{N_t(s_t,a_t)}\right)^2 }. \label{eq:R12-1}
\end{align}

To further bound the summation in (<ref>), we focus on a part of each summand, which can be decomposed into two terms as follows:

\begin{align}
&\quad\ \frac{\sum_{n=1}^{N_{t}(s_t,a_t)}\left(V^{\rref}_{t_n}(s_{t_n+1}) \right)^2}{N_t(s_t,a_t)} - \left(\frac{\sum_{n=1}^{N_{t}(s_t,a_t)}V^{\rref}_{t_n}(s_{t_n+1})}{N_t(s_t,a_t)}\right)^2 \nonumber\\
&\leq \frac{\sum_{n=1}^{N_{t}(s_t,a_t)}\left(V^{\rref}_{t_n}(s_{t_n+1}) \right)^2 - \left(V^\star(s_{t_n+1}) \right)^2}{N_t(s_t,a_t)} + \frac{\sum_{n=1}^{N_{t}(s_t,a_t)}\left(V^\star(s_{t_n+1}) \right)^2}{N_t(s_t,a_t)} - \left(\frac{\sum_{n=1}^{N_{t}(s_t,a_t)}V^\star(s_{t_n+1})}{N_t(s_t,a_t)}\right)^2\nonumber\\
&= \frac{\sum_{n=1}^{N_{t}(s_t,a_t)}\left(V^{\rref}_{t_n}(s_{t_n+1})+V^\star(s_{t_n+1})\right)\left(V^{\rref}_{t_n}(s_{t_n+1})-V^\star(s_{t_n+1})\right)}{N_t(s_t,a_t)} + \frac{\sum_{n=1}^{N_{t}(s_t,a_t)}\left(V^\star(s_{t_n+1}) \right)^2}{N_t(s_t,a_t)} - \left(\frac{\sum_{n=1}^{N_{t}(s_t,a_t)}V^\star(s_{t_n+1})}{N_t(s_t,a_t)}\right)^2\nonumber\\
&\le \underbrace{ \frac{\sum_{n=1}^{N_{t}(s_t,a_t)}\frac{2}{1-\gamma}\left(V^{\rref}_{t_n}(s_{t_n+1})-V^\star(s_{t_n+1})\right)}{N_t(s_t,a_t)}}_{=:\cR_{1,2,1}^{(t)}}+ \underbrace{ \frac{\sum_{n=1}^{N_{t}(s_t,a_t)}\left(V^\star(s_{t_n+1}) \right)^2}{N_t(s_t,a_t)} - \left(\frac{\sum_{n=1}^{N_{t}(s_t,a_t)}V^\star(s_{t_n+1})}{N_t(s_t,a_t)}\right)^2}_{=: \cR_{1,2,2}^{(t)}}. \label{eq:R12-J}
\end{align}

Above, the last line is obtained due to the fact $\frac{1}{1-\gamma}\geq \norm{V^{\rref}_{t_n}}_\infty \ge \norm{V^{\star}}_\infty \geq 0$ for all $t_n \leq T$.

In order to arrive at a bound on (<ref>), we shall bound $\cR_{1,2,1}^{(t)}$ and $\cR_{1,2,2}^{(t)}$ separately.

Define $J_t(s_t, a_t)$ as

\begin{equation} \label{eq:Phi-def}
J_t(s_t, a_t) := \sum_{n=1}^{N_{t}(s_t,a_t)}\left(V^{\rref}_{t_n}(s_{t_n+1})-V^\star(s_{t_n+1})\right)\ind\left(V^{\rref}_{t_n}(s_{t_n+1})-V^\star(s_{t_n+1}) > 12\right).
\end{equation}

$\cR_{1,2,1}^{(t)}$ can be simply decomposed as follows

\begin{align}
\cR_{1,2,1}^{(t)} &= \frac{2}{(1-\gamma)N_{t}(s_t,a_t)} \left( \sum_{n=1}^{N_{t}(s_t,a_t)}\left(V^{\rref}_{t_n}(s_{t_n+1})-V^\star(s_{t_n+1})\right)\ind\left(V^{\rref}_{t_n}(s_{t_n+1})-V^\star(s_{t_n+1}) \le 9\right) + J_t(s_t, a_t) \right) \nonumber \\
&\le \frac{24}{1-\gamma} + \frac{2}{(1-\gamma)N_{t}(s_t,a_t)} J_t(s_t, a_t). \label{eq:J1}
\end{align}

On the other hand, we claim

\begin{align} \label{eq:J2}
\cR_{1,2,2}^{(t)} \lesssim \Var_{s_t, a_t}(V^{\star}) + \frac{1}{(1-\gamma)^2}\sqrt{\frac{\log\frac{SAT}{\delta}}{N_t(s_t,a_t)}},
\end{align}

which will be justified in Appendix <ref>.

Substituting (<ref>) and (<ref>) back into (<ref>) and (<ref>) allows us to have

\begin{align}
&\quad\ \sum_{t=1}^{T}\sqrt{\frac{\sigma^{\re}_{t}(s_t, a_t) - \left(\mu^{\re}_{t}(s_t, a_t)\right)^2}{N_t(s_t,a_t)}}  \nonumber \\
& \lesssim \sum_{t = 1}^T\sqrt{\frac{1}{N_t(s_t,a_t)}} \sqrt{\frac{1}{1-\gamma}+\frac{J_t(s_t, a_t)}{(1-\gamma)N_{t}(s_t,a_t)} + \Var_{s_t, a_t}(V^{\star}) + \frac{1}{(1-\gamma)^2}\sqrt{\frac{\log\frac{SAT}{\delta}}{N_t(s_t,a_t)}}} \nonumber\\
&\leq \sum_{t = 1}^T \Bigg( \sqrt{\frac{1}{(1-\gamma)N_{t}(s_t,a_t)}}  + \frac{\sqrt{J_t(s_t, a_t)}}{N_{t}(s_t,a_t)\sqrt{1-\gamma}} + \sqrt{ \frac{ \Var_{s_t, a_t}(V^{\star})}{N_{t}(s_t,a_t)}}  + \frac{\log^{1/4}\frac{SAT}{\delta}}{(1-\gamma) \big(N_{t}(s_t,a_t) \big)^{3/4}} \Bigg) \nonumber\\
& \lesssim \sqrt{\frac{SAT}{1-\gamma}} +\sum_{t=1}^T \frac{\sqrt{J_t(s_t, a_t)}}{N_{t}(s_t,a_t)\sqrt{1-\gamma}} + \sum_{t = 1}^T\sqrt{ \frac{ \Var_{s_t, a_t}(V^{\star})}{N_{t}(s_t,a_t)}} + \frac{(SA)^{3/4} }{1-\gamma}\left(T\log\frac{SAT}{\delta} \right)^{1/4} ,
\label{eq:R12-final}
\end{align}

in which the last line follows from (<ref>) and (<ref>).

Step 3: combining the preceding bounds.

Finally, substituting (<ref>) and (<ref>) back into (<ref>) leads to

\begin{align*}
\cR_1 &\lesssim \sqrt{\frac{SAT}{1-\gamma}\log\frac{SAT}{\delta}} + \sqrt{\log\frac{SAT}{\delta}}\sum_{t=1}^{T}\sqrt{\frac{\sigma^{\mathrm{ref}}_{t}(s_t, a_t) - \left(\mu^{\mathrm{ref}}_{t}(s_t, a_t)\right)^2}{N_t(s_t,a_t)}}\\
&\lesssim \sqrt{\frac{SAT}{1-\gamma}\log\frac{SAT}{\delta}} + \frac{(SA)^{3/4} }{1-\gamma}T^{1/4}\log^{3/4}\frac{SAT}{\delta}  + \sqrt{\log\frac{SAT}{\delta} }\sum_{t = 1}^T\sqrt{ \frac{ \Var_{s_t, a_t}(V^{\star})}{N_{t}(s_t,a_t)}} +\sqrt{\frac{\log\frac{SAT}{\delta}}{1-\gamma}}\sum_{t=1}^T \frac{\sqrt{J_t(s_t, a_t)}}{N_{t}(s_t,a_t)}\\
&\overset{\mathrm{(i)}}{\lesssim} \sqrt{\frac{SAT}{1-\gamma}\log\frac{SAT}{\delta}}  + \frac{(SA)^{3/4} }{1-\gamma}T^{1/4}\log^{3/4}\frac{SAT}{\delta}  + \frac{SA}{(1-\gamma)^{15/4}}\log^{7/2}\frac{SAT}{\delta}\\
&\overset{\mathrm{(ii)}}{\lesssim} \sqrt{\frac{SAT}{1-\gamma}\log\frac{SAT}{\delta}} + \frac{SA}{(1-\gamma)^{15/4}}\log^{7/2}\frac{SAT}{\delta}.
\end{align*}

Here, (i) is true due to the following two inequalities

\begin{align}
\sum_{t = 1}^T\sqrt{ \frac{ \Var_{s_t, a_t}(V^{\star})}{N_{t}(s_t,a_t)}} & \lesssim \sqrt{\frac{SAT}{1-\gamma}} + \frac{SA}{(1-\gamma)^{3}}\log\frac{SAT}{\delta},\label{eq:R1-1}  \\
\sum_{t=1}^T \frac{\sqrt{J_t(s_t, a_t)}}{N_{t}(s_t,a_t)} & \lesssim \sqrt{SAT} + \frac{SA}{(1-\gamma)^{13/4}}\log^3\frac{SAT}{\delta}, \label{eq:R1-2}
\end{align}

whose proofs are deferred to Appendix <ref> and Appendix <ref>, respectively. In addition, (ii) uses $2ab \le a^2 + b^2$ and is obtained via the following logic:

\begin{align*}
\frac{(SA)^{3/4} }{1-\gamma}T^{1/4}\log^{3/4}\frac{SAT}{\delta} &=\left(\frac{SA}{(1-\gamma)^2}\log\frac{SAT}{\delta}\right)^{1/2}\left(SAT\log\frac{SAT}{\delta}\right)^{1/4}\\
&\lesssim \frac{SA}{(1-\gamma)^2}\log\frac{SAT}{\delta} + \sqrt{\frac{SAT}{1-\gamma}\log\frac{SAT}{\delta}}.
\end{align*}

This concludes the proof of the advertised upper bound on $\mathcal{R}_1$ that leads to (<ref>).

§.§.§ Proof of Inequality (<ref>)

We begin by constructing the necessary notation and verify the conditions for Lemma <ref>. Consider any $N \in [T]$. Let

\begin{align}
W_i := ({V}^{\star})^{2} \qquad \text{and} \qquad u_i(s,a, N) := \frac{1}{N}. \label{J2-Wu}
\end{align}

Clearly, $W_i$ and $u_i(s,a,N)$ are deterministic at the end of the $(i-1)$-th step. Moreover, define

\begin{align}
C_{\mathrm{u}} := \frac{1}{N} \qquad \text{and} \qquad \norm{W_i}_\infty \leq \frac{1}{(1-\gamma)^2} =: C_{\mathrm{w}}. \label{J2-cw-cu}
\end{align}

Lastly, it is obvious that

\begin{align}
0 \leq \sum_{n=1}^N u_{t_n(s,a)}(s,a, N) = 1 \label{eq:J2-cond-u}
\end{align}

holds for all $(N,s,a) \in [T] \times \cS\times \cA$.

By the definition (<ref>)

$$\Var_{s_t, a_t}(V^{\star}) = P_{s_t, a_t}(V^{\star})^2 -  \left(P_{s_t, a_t} V^{\star} \right)^2,$$

we have that with probability at least $1-\delta$,

\begin{align*}
&\quad\  \left|\frac{1}{{N_t}}\sum_{n = 1}^{{N_t}}  V^{\star}(s_{t_n+1})^2 - \left(\frac{1}{{N_t}}\sum_{n = 1}^{{N_t}} V^{\star}(s_{t_n+1}) \right)^2 - \Var_{s_t, a_t}(V^{\star})\right|\\
&\leq \left|\frac{1}{{N_t}}\sum_{n = 1}^{{N_t}}  V^{\star}(s_{t_n+1})^2 - P_{s_t, a_t}(V^{\star})^2 \right|
+ \left| \left(\frac{1}{{N_t}}\sum_{n = 1}^{{N_t}} V^{\star}(s_{t_n+1}) \right)^2 - (P_{s_t, a_t}V^{\star})^2 \right| \\
&\lesssim \frac{1}{(1-\gamma)^2}\sqrt{\frac{\log\frac{SAT}{\delta}}{{N_t}}} + \left| \left(\frac{1}{{N_t}}\sum_{n = 1}^{{N_t}} V^{\star}(s_{t_n+1}) \right)^2 - (P_{s_t, a_t}V^{\star})^2 \right| \\
&= \frac{1}{(1-\gamma)^2}\sqrt{\frac{\log\frac{SAT}{\delta}}{{N_t}}} + \left| \frac{1}{{N_t}}\sum_{n = 1}^{{N_t}} V^{\star}(s_{t_n+1}) - P_{s_t, a_t}V^{\star}  \right| \cdot  \left| \frac{1}{{N_t}}\sum_{n = 1}^{{N_t}} V^{\star}(s_{t_n+1}) + P_{s_t, a_t}V^{\star} \right| \\
&\lesssim \frac{1}{(1-\gamma)^2}\sqrt{\frac{\log\frac{SAT}{\delta}}{{N_t}}},
\end{align*}

where the first inequality is by the definition (<ref>):

\begin{equation*}
\Var_{s_t, a_t}(V^{\star}) = P_{s_t, a_t}(V^{\star})^2 -  \left(P_{s_t, a_t} V^{\star} \right)^2,
\end{equation*}

and the second inequality is obtained through the application of Lemma <ref> with (<ref>), (<ref>) and $(N,s,a)=(N_t,s_t, a_t)$, which allows us to conclude that with probability at least $1-\delta$,

\begin{align*}
\left| \frac{1}{{N_t}}\sum_{n = 1}^{{N_t}} \big( V^{\star}(s_{t_n+1}) \big)^2 - P_{s_t, a_t}(V^{\star})^2 \right| = \left| \frac{1}{{N_t}}\sum_{n = 1}^{{N_t}} \left(P_{t_n} - P_{s_t, a_t} \right) \left(V^{\star} \right)^2  \right|
\lesssim \frac{1}{(1-\gamma)^2}\sqrt{\frac{\log\frac{SAT}{\delta}}{{N_t}}},
\end{align*}

and similarly the last line is obtained with the fact $\norm{V^{\star}}_{\infty} \leq \frac{1}{1-\gamma}$ and an application of Lemma <ref>, which allows us to conclude that with probability at least $1-\delta$,

\begin{align*}
\left| \frac{1}{{N_t}}\sum_{n = 1}^{{N_t}} V^{\star}(s_{t_n+1}) - P_{s_t, a_t}V^{\star} \right|
= \left| \frac{1}{{N_t}}\sum_{n = 1}^{{N_t}} \left(P_{t_n} - P_{s_t, a_t} \right) V^{\star} \right|
\lesssim \frac{1}{1-\gamma}\sqrt{\frac{\log\frac{SAT}{\delta}}{{N_t}}}.
\end{align*}

§.§.§ Proof of Inequality (<ref>)

Let us begin with the following manipulation

\begin{align}
\sum_{t = 1}^T\sqrt{ \frac{ \Var_{s_t, a_t}(V^{\star})}{N_{t}(s_t,a_t)}} &= \sum_{(s, a)\in\cS\times\cA} \sum_{n = 1}^{N_t(s, a)} \sqrt{\frac{\Var_{s, a}(V^{\star})}{n}} \notag\\
&\overset{\mathrm{(i)}}{\le} 2\sum_{(s, a)\in\cS\times\cA}   \sqrt{N_t(s, a)\Var_{s, a}(V^{\star})} \notag\\
&\overset{\mathrm{(ii)}}{\le} 2\sqrt{\sum_{(s, a)\in\cS\times\cA} 1}  \cdot \sqrt{ \sum_{(s, a)\in\cS\times\cA}   N_t(s, a)\Var_{s, a}(V^{\star})} \notag \\
&= 2 \sqrt{SA}\sqrt{\sum_{t = 1}^T \Var_{s_t, a_t}(V^{\star})}, \label{eq:R1-1.1}
\end{align}

in which (i) is due to $\sum_{n = 1}^{N} 1/{\sqrt{n}} \leq 2\sqrt{N}$; (ii) is by the Cauchy-Schwarz inequality.

It only remains to bound the variance term in (<ref>). To this end, let us decompose it further into

\begin{align}
\sum_{t = 1}^T \Var_{s_t, a_t}(V^{\star}) &\leq
\underbrace{\sum_{t = 1}^T \Var_{s_t, a_t} \big( V^{\pi_t}\big)}_{\alpha_1} + \underbrace{\sum_{t = 1}^T \left|\Var_{s_t, a_t}(V^{\star}) - \Var_{s_t, a_t}(V^{\pi_t})\right|}_{\alpha_2} \notag \\
&\lesssim \frac{T}{1-\gamma} + \sqrt{\frac{SAT\log\frac{SAT}{\delta}}{(1-\gamma)^7}} + \frac{SA\log^2\frac{SAT}{\delta}}{(1-\gamma)^{9/2}} + \frac{1}{(1-\gamma)^2}\sqrt{T\log\frac{SAT}{\delta}} + \frac{\log T}{(1-\gamma)^2}\sqrt{SAT}\notag\\
&\lesssim \frac{T}{1-\gamma} + \sqrt{\frac{SAT\log\frac{SAT}{\delta}}{(1-\gamma)^7}} + \frac{SA\log^2\frac{SAT}{\delta}}{(1-\gamma)^{9/2}} + \frac{\log T}{(1-\gamma)^2}\sqrt{SAT}.\label{eq:R1-1.2}
\end{align}

The above inequality can be obtained with an upper bound on $\alpha_1$ and $\alpha_2$ respectively. Let us use $e_{s}$ to denote the $S$-dimensional canonical basis vector whose entry is $1$ in the $s$-th dimension. To bound $\alpha_1$ in (<ref>), we can first write $\alpha_1$ as follows:

\begin{align}
\Var_{s_t, a_t} \big( V^{\pi_t}\big) & =P_{s_t,a_t}\left(V^{\pi_t}\right)^2-\left(P_{s_t,a_t}V^{\pi_t}\right)^2\nonumber \\
& =P_{s_t,a_t}\left(V^{\pi_t}\right)^2 -\frac{1}{\gamma^{2}}\left(r(s_t,a_t)-V^{\pi_t}(s_t)\right)^2\nonumber \\
& = P_{s_t,a_t}\left(V^{\pi_t}\right)^2-\frac{1}{\gamma^{2}}r^2(s_t,a_t)-\frac{1}{\gamma^{2}}\left(V^{\pi_t}(s_t)\right)^2 +\frac{2}{\gamma^{2}}V^{\pi_t}(s_t)\cdot r(s_t,a_t)\nonumber \\
& \leq\frac{1}{\gamma^{2}}\left(\gamma^{2}P_{s_t,a_t}-e_{s_t}^\top\right)\left(V^{\pi_t}\right)^2 +\frac{2}{\gamma^{2}}V^{\pi_t}(s_t)\cdot r(s_t,a_t).
\label{eq:v-bound}
\end{align}

Here, the second line follows from the Bellman optimality equation
$V^{\pi_t}(s_t) = Q^{\pi_t}(s_t,a_t) =r(s_t, a_t)+\gamma P_{s_t,a_t}V^{\pi_t}$. Now, we are ready to bound $\alpha_1$ under two partition cases. If $\gamma < \frac{1}{2}$, then

\begin{align*}
\alpha_1 &= \sum_{t = 1}^T \Var_{s_t, a_t} \big( V^{\pi_t}\big)\\
&= \sum_{t = 1}^T \left(P_{s_t,a_t}\left(V^{\pi_t}\right)^2-\left(P_{s_t,a_t}V^{\pi_t}\right)^2\right)\\
&\le \frac{T}{(1-\gamma)^2}\\
&\le \frac{2T}{1-\gamma}.
\end{align*}

If $\gamma \ge \frac{1}{2}$, by (<ref>), we can write

\begin{align*}
\alpha_1 &= \sum_{t = 1}^T \Var_{s_t, a_t} \left( V^{\pi_t}\right)\\
&\le \sum_{t = 1}^T\left(\frac{1}{\gamma^{2}}\left(\gamma^{2}P_{s_t,a_t}-e_{s_t}^\top\right)\left(V^{\pi_t}\right)^2 +\frac{2}{\gamma^{2}}V^{\pi_t}(s_t)\cdot r(s_t,a_t)\right)\\
&\le \sum_{t = 1}^T\left(\frac{1}{\gamma^{2}}\left|\left(\gamma^{2}P_{s_t,a_t}-e_{s_t}^\top\right)\left(V^{\pi_t}\right)^2\right| +\frac{2}{\gamma^{2}}V^{\pi_t}(s_t)\cdot r(s_t,a_t)\right)\\
&= \sum_{t = 1}^T\left(\frac{1}{\gamma^{2}}\left|\left[(1-\gamma)e_{s_t}^\top + \gamma (e_{s_t}^\top - \gamma P_{s_t,a_t})\right]\left(V^{\pi_t}\right)^2\right| +\frac{2}{\gamma^{2}}V^{\pi_t}(s_t)\cdot r(s_t,a_t)\right)\\
%&= \sum_{t = 1}^T\frac{1}{\gamma^{2}}\left|\left[(1-\gamma)e_{s_t}^\top + \gamma e_{s_t}^\top(I - \gamma P_{\pi_t})\right]\left(V^{\pi_t}\right)^2\right| +2V^{\pi_t}(s_t)\cdot r(s_t,a_t)\\
&\overset{(\mathrm{i})}{\leq} \sum_{t = 1}^T\left(\frac{1-\gamma}{\gamma^2}\norm{e_{s_t}^\top}_1\norm{V^{\pi_t}}^2_\infty + \frac{1}{\gamma}\left|(e_{s_t}^\top - \gamma P_{s_t,a_t})V^{\pi_t}\right|\norm{V^{\pi_t}}_\infty + \frac{2}{\gamma^{2}}V^{\pi_t}(s_t)\right)\\
&\overset{(\mathrm{ii})}{=} \sum_{t = 1}^T\left(\frac{1-\gamma}{\gamma^2}\norm{e_{s_t}^\top}_1\norm{V^{\pi_t}}^2_\infty + \frac{1}{\gamma}\left|r(s_t,a_t)\right|\norm{V^{\pi_t}}_\infty + \frac{2}{\gamma^{2}}V^{\pi_t}(s_t)\right)\\
&\overset{(\mathrm{iii})}{\leq} \sum_{t = 1}^T\left(\frac{1}{2\gamma^2(1-\gamma)} + \frac{1}{\gamma(1-\gamma)} + \frac{2}{\gamma^2(1-\gamma)}\right)\\
&\overset{(\mathrm{iv})}{\leq} \frac{12T}{1-\gamma},
\end{align*}

where (i) is due to the Hölder inequality and $\norm{r}_\infty \le 1$; (ii) is due to the Bellman optimality equation $V^{\pi_t}(s_t) = Q^{\pi_t}(s_t,a_t) =r(s_t, a_t)+\gamma P_{s_t,a_t}V^{\pi_t}$ and thus $(e_{s_t}^\top - \gamma P_{s_t,a_t})V^{\pi_t} = r(s_t,a_t)$; (iii) is due to $\norm{V^{\pi_t}}_\infty \le \frac{1}{1-\gamma}$ and $\norm{e_{s_t}}_1 = 1$ and $\norm{r}_\infty \le 1$; (iv) is due to $\gamma \ge \frac{1}{2}$.

On the other hand, $\alpha_2$ in (<ref>) can be bounded as follows

\begin{align}
\alpha_2 &= \sum_{t = 1}^T \left|\Var_{s_t, a_t}(V^{\star}) - \Var_{s_t, a_t}(V^{\pi_t})\right|\nonumber\\
& =\sum_{t=1}^{T}\left|P_{s_{t},a_{t}}(V^{\star})^{2}-\left(P_{s_{t},a_{t}}V^{\star}\right)^{2}-P_{s_{t},a_{t}}(V^{\pi_{t}})^{2}+\left(P_{s_{t},a_{t}}V^{\pi_{t}}\right)^{2}\right| \notag\\
& \leq\sum_{t=1}^{T}\left(\left|P_{s_{t},a_{t}}\left(\left(V^{\star}-V^{\pi_{t}}\right) \circ\left(V^{\star}+V^{\pi_{t}}\right)\right)\right|+\left|\left(P_{s_{t},a_{t}}V^{\star}\right)^{2}-\left(P_{s_{t},a_{t}}V^{\pi_{t}}\right)^{2}\right|\right) \notag\\
&\overset{(\mathrm{i})}{\leq} \frac{4}{1-\gamma}\sum_{t=1}^{T}P_{s_{t},a_{t}}\left(V^{\star}-V^{\pi_{t}}\right)  \notag\\
& =\frac{4}{1-\gamma}\sum_{t=1}^{T}\left\{ V^{\star}(s_{t+1})-V^{\pi_{t}}(s_{t+1})+\left(P_{s_{t},a_{t}}-P_{t}\right)\left(V^{\star}-V^{\pi_{t}}\right)\right\}  \nonumber\\
& \overset{(\mathrm{ii})}{=} \frac{4}{1-\gamma} \sum_{t=1}^{T}\left(\Delta_{t}+\phi_{t}\right) \nonumber\\
& \overset{(\mathrm{iii})}{\lesssim} \sqrt{\frac{SAT\log\frac{SAT}{\delta}}{(1-\gamma)^7}} + \frac{SA\log^2\frac{SAT}{\delta}}{(1-\gamma)^{9/2}} + \frac{1}{(1-\gamma)^2}\sqrt{T\log\frac{SAT}{\delta}} + \frac{\log T}{(1-\gamma)^2}\sqrt{SAT},
\label{eq:R1-1.3}
\end{align}

Above, (i) is obtained by observing that $V^{\star}-V^{\pi_{t}}\geq 0$ and

\begin{align*}
\left|P_{s_{t},a_{t}}\left(\left(V^{\star}-V^{\pi_{t}}\right)^\top\left(V^{\star}+V^{\pi_{t}}\right)\right)\right| & \leq P_{s_{t},a_{t}}\left(V^{\star}-V^{\pi_{t}}\right)\left(\norm{ V^{\star}}_{\infty}+\norm{V^{\pi_{t}}}_{\infty}\right)\\
& \leq \frac{2}{1-\gamma}P_{s_{t},a_{t}}\left(V^{\star}-V^{\pi_{t}}\right),\\
\left|\left(P_{s_{t},a_{t}}V^{\star}\right)^{2}-\left(P_{s_{t},a_{t}}V^{\pi_{t}}\right)^{2}\right| & \leq\left|P_{s_{t},a_{t}}\left(V^{\star}-V^{\pi_{t}}\right)\right| \cdot \left|P_{s_{t},a_{t}}\left(V^{\star}+V^{\pi_{t}}\right)\right|\\
& \leq \frac{2}{1-\gamma}P_{s_{t},a_{t}}\left(V^{\star}-V^{\pi_{t}}\right).
\end{align*}

In (ii) of (<ref>), we define

\begin{align}
\Delta_t := V^{\star}(s_{t+1})-V^{\pi_{t}}(s_{t+1}),  \qquad \phi_t := \left(P_{s_{t},a_{t}}-P_{t}\right)\left(V^{\star}-V^{\pi_{t}}\right).
\end{align}

(iii) in (<ref>) results from the following two bounds:

\begin{align}
\sum_{t=1}^{T}\Delta_{t} & \lesssim \frac{SA\log^2\frac{SAT}{\delta}}{(1-\gamma)^{7/2}} + \sqrt{\frac{SAT\log\frac{SAT}{\delta}}{(1-\gamma)^5}} + \frac{\log T}{1-\gamma}\sqrt{SAT}, \label{eq:R1-1.3-delta}\\
\sum_{t=1}^{T}\phi_{t} & \lesssim \frac{1}{1-\gamma}\sqrt{T\log\frac{SAT}{\delta}}\label{eq:R1-1.3-phi}.
\end{align}

Now, we show how (<ref>) and (<ref>) are obtained. For (<ref>), we decompose it into two terms as follows:

\begin{align}
\sum_{t=1}^T \Delta_{t} &= \sum_{t=1}^T \big(V^{\star}(s_{t+1})-V^{\pi_{t}}(s_{t+1})\big) = \sum_{t=1}^T \big(\underbrace{V^{\star}(s_{t+1})-V^{\pi_{t+1}}(s_{t+1})}_{=: \Delta_{t,1}} + \underbrace{V^{\pi_{t+1}}(s_{t+1}) - V^{\pi_{t}}(s_{t+1})}_{=: \Delta_{t,2}}\big).
\end{align}

Notice $\sum_{t=1}^T\Delta_{t,1}$ is the regret, so we can bound it with our crude regret bound in Lemma <ref>, which gives

\begin{align}
\sum_{t=1}^T \Delta_{t,1} &\lesssim \frac{SA\log^2\frac{SAT}{\delta}}{(1-\gamma)^{7/2}} + \sqrt{\frac{SAT\log\frac{SAT}{\delta}}{(1-\gamma)^5}}.\label{eq:delta-t1-bound}
\end{align}

On the other hand, notice $\Delta_{t,2}$ coincides with $\xi_{t,3}$ (cf. (<ref>)) in the proof of Lemma <ref>. Thus, we can invoke (<ref>) and have

\begin{align}
\sum_{t=1}^T \Delta_{t,2} &= \sum_{t=1}^T \big(V^{\pi_{t+1}}(s_{t+1}) - V^{\pi_t}(s_{t+1})\big)\notag\\
&\lesssim \frac{SA}{1-\gamma}\log T + \frac{(SA)^{3/4}T^{1/4}\log^{5/4}\frac{SAT}{\delta}}{(1-\gamma)^{5/4}} + \sqrt{\frac{SA\log^2 T}{1-\gamma}\sum_{t=1}^T \big(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big)} \notag\\
&\lesssim \frac{SA}{1-\gamma}\log T + \frac{(SA)^{3/4}T^{1/4}\log^{5/4}\frac{SAT}{\delta}}{(1-\gamma)^{5/4}} + \frac{\log T}{1-\gamma}\sqrt{SAT} \notag\\
&\lesssim SA\log^2\frac{SAT}{\delta} + \sqrt{\frac{SAT\log\frac{SAT}{\delta}}{(1-\gamma)^5}} + \frac{\log T}{1-\gamma}\sqrt{SAT},
\end{align}

in which the penultimate step is due to $\norm{V_t - V^{\pi_{t+1}}}_\infty \le \frac{1}{1-\gamma}$ and the last step is due to $2ab \le a^2 + b^2$.

For (<ref>), we can directly invoke the Azuma-Hoeffding inequality (Theorem <ref>) and obtain that with probability $1-\delta$,

\begin{align*}
\sum_{t=1}^{T}\phi_{t} = \sum_{t=1}^{T}\big(P_{s_{t},a_{t}}-P_{t}\big)\big(V^{\star}-V^{\pi_{t}}\big) \lesssim \frac{1}{1-\gamma}\sqrt{T\log\frac{SAT}{\delta}}.
\end{align*}

Consequently, substituting (<ref>) into (<ref>) gives us

\begin{align*}
&\quad \sum_{t=1}^{T}\sqrt{\frac{\Var_{s_{t},a_{t}}(V^{\star})}{N_{t}(s_{t},a_{t})}}\\
& \lesssim \sqrt{SA}\sqrt{\frac{T}{1-\gamma} + \sqrt{\frac{SAT\log\frac{SAT}{\delta}}{(1-\gamma)^7}} + \frac{SA\log^2\frac{SAT}{\delta}}{(1-\gamma)^{9/2}} + \frac{\log T}{(1-\gamma)^2}\sqrt{SAT}}\\
& \lesssim \sqrt{\frac{SAT}{1-\gamma}} + \frac{(SA)^{3/4}}{(1-\gamma)^{7/4}}\left(T\log\frac{SAT}{\delta}\right)^{1/4} + \frac{SA}{(1-\gamma)^{9/4}}\log\frac{SAT}{\delta} + \frac{(SA)^{3/4}}{1-\gamma}T^{1/4}\sqrt{\log T}\\
&= \sqrt{\frac{SAT}{1-\gamma}} + \left(\frac{SAT}{1-\gamma}\right)^{1/4}\left(\frac{SA}{(1-\gamma)^3}\right)^{1/2}\log^{1/4}\frac{SAT}{\delta} + \frac{SA}{(1-\gamma)^{9/4}}\log\frac{SAT}{\delta} + \left(\frac{SAT}{1-\gamma}\right)^{1/4}\left(\frac{SA}{(1-\gamma)^{3/2}}\right)^{1/2}\sqrt{\log T}\\
&\lesssim \sqrt{\frac{SAT}{1-\gamma}} + \frac{SA}{(1-\gamma)^{3}}\log\frac{SAT}{\delta},
\end{align*}

where we have applied the basic inequality $2ab\leq a^2 + b^2$ for any $a,b\geq 0$.

§.§.§ Proof of Inequality (<ref>)

Let us begin with the following manipulation

\begin{align}
\sum_{t = 1}^T\frac{\sqrt{J_t(s_t, a_t)}}{N_t(s_t, a_t)} & =\sum_{(s, a)\in\cS\times\cA} \sum_{n = 1}^{N_T(s, a)} \frac{\sqrt{J_{t_n(s, a)}(s, a)}}{n} \nonumber \\
&\le\sum_{(s, a)\in\cS\times\cA}  \sqrt{J_{N_T(s,a)}(s, a)}\log T \nonumber \\
&\le\sqrt{SA \sum_{(s, a)\in\cS\times\cA} J_{N_T(s,a)}(s, a)}\log T .\label{eq:R1-2.1}
\end{align}

Here, the first inequality holds using the harmonic number and the monotonicity of $J_{t}(s_t, a_t)$ with respect to $t$ (cf. (<ref>)) due to the monotonicity of $V_{t}^{\rref}$, while the second inequality comes from Cauchy-Schwarz.

We can continue by writing out $J_{N_t(s,a)}(s, a)$ with its definition explicitly:

\begin{align}
\sqrt{\sum_{(s,a)\in\cS\times\cA}J_{N_{T}(s,a)}(s,a)} &=\sqrt{\sum_{t=1}^{T}\Big(V^{\rref}_{t}(s_{t+1})-V^\star(s_{t+1})\Big)\ind\Big(V^{\rref}_{t}(s_{t+1})-V^\star(s_{t+1}) > 9\Big)}\nonumber\\
& \leq\sqrt{\sum_{t=1}^{T}\Big(V_t(s_{t+1})+6-V_{t}^{\mathrm{LCB}}(s_{t+1})\Big)\ind\Big(V_t(s_{t+1})+6-V_{t}^{\mathrm{LCB}}(s_{t+1})>9\Big)}\nonumber\\
& =\sqrt{\sum_{t=1}^{T}\Big(V_t(s_{t+1})+6-V_{t}^{\mathrm{LCB}}(s_{t+1})\Big)\ind\Big(V_t(s_{t+1})-V_{t}^{\mathrm{LCB}}(s_{t+1})>3\Big)}\nonumber\\
& \leq\sqrt{\sum_{t=1}^{T}3\Big(V_t(s_{t+1})-V_{t}^{\mathrm{LCB}}(s_{t+1})\Big)\ind\Big(V_t(s_{t+1})-V_{t}^{\mathrm{LCB}}(s_{t+1})>3\Big)}, \label{eq:R1-2.2}
\end{align}

where the first inequality follows from Lemma <ref> (cf. (<ref>)) and the pessimism of $V^\LCB$ in Lemma <ref>, which implies

$$V^{\rref}_{t}(s_{t+1})-V^\star(s_{t+1}) \leq V_t(s_{t+1})+6-V^\star(s_{t+1})\leq V_t(s_{t+1})+6-V_{t}^{\mathrm{LCB}}(s_{t+1}),$$

and the last inequality holds since $3 < V_t(s_{t+1})-V_{t}^{\mathrm{LCB}}(s_{t+1})$ when $\ind\Big(V_t(s_{t+1})-V_{t}^{\mathrm{LCB}}(s_{t+1})>3\Big) \neq 0$.

Furthermore, invoking (<ref>) from Lemma <ref> in (<ref>) gives

\begin{align*}
&\quad\ \sqrt{\sum_{(s,a)\in\cS\times\cA}J_{N_{T}(s,a)}(s,a)}\\
&\lesssim \sqrt{\frac{\left(SAT\right)^{1/4}}{(1-\gamma)^{13/4}}\left(\log\frac{SAT}{\delta}\right)^{5/4} + \frac{SA}{(1-\gamma)^6}\log \frac{SAT}{\delta} + \sqrt{\frac{\log^2 T}{(1-\gamma)^5}\sum_{t=1}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)}} \notag\\
&\lesssim \left(SAT\right)^{1/8}\left(\log\frac{SAT}{\delta}\right)^{5/8}\left(\frac{1}{1-\gamma}\right)^{13/8} + \frac{\sqrt{SA\log \frac{SAT}{\delta}}}{(1-\gamma)^3} + \frac{T^{1/4}\sqrt{\log T}}{(1-\gamma)^{3/2}}\\
&= T^{1/8}\left(SA\right)^{1/8}\left(\log\frac{SAT}{\delta}\right)^{5/8}\left(\frac{1}{1-\gamma}\right)^{13/8} + \frac{\sqrt{SA\log \frac{SAT}{\delta}}}{(1-\gamma)^3} + \frac{T^{1/4}}{\sqrt{\log T}}\frac{\log T}{(1-\gamma)^{3/2}}\\
&\lesssim \frac{\sqrt{T}}{\log T} + \log T + \left(SA\right)^{1/4}\left(\log\frac{SAT}{\delta}\right)^{5/4}\left(\frac{1}{1-\gamma}\right)^{13/4} + \frac{\sqrt{SA\log \frac{SAT}{\delta}}}{(1-\gamma)^3} + \frac{\sqrt{T}}{\log T} + \frac{\log^2 T}{(1-\gamma)^{3}}\\
&\lesssim \frac{\sqrt{T}}{\log T} + \frac{\sqrt{SA}}{(1-\gamma)^{13/4}}\log^2\frac{SAT}{\delta},
\end{align*}

where the second inequality is by $V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t}) \le \frac{1}{1-\gamma}$, and the penultimate inequality is by $2ab \le a^2 + b^2$.

Finally, substitution into (<ref>) gives

\begin{align*}
\sum_{t = 1}^T\frac{\sqrt{J_t(s_t, a_t)}}{N_t(s_t, a_t)} &\lesssim \left(\sqrt{SA}\log T\right)\left(\frac{\sqrt{T}}{\log T} + \frac{\sqrt{SA}}{(1-\gamma)^{13/4}}\log^2\frac{SAT}{\delta}\right)\\
&\le \sqrt{SAT} + \frac{SA}{(1-\gamma)^{13/4}}\log^3\frac{SAT}{\delta},
\end{align*}

which concludes this proof.

§.§ Bounding $\cR_2$

In this section, let us again adopt the shorthand notation $t_i := t_i(s_t, a_t)$. Also define

\begin{equation}
\label{eq:lambda_t_bound}
\lambda_t := \sum_{N = N_{t}(s_t,a_t)}^{N_{T-1}(s_t,a_t)} \eta_{N_{t}(s_t,a_t)}^N.
\end{equation}

We can decompose $\mathcal{R}_2$ in (<ref>) as follows:

\begin{equation*}
\mathcal{R}_2:= \underbrace{\gamma\sum_{t = 1}^{T} \lambda_t \left(P_{t} - P_{s_t,a_t}\right)\left(V^* - V^{\rref}_{t}\right)}_{\eqqcolon \mathcal{R}_{2,1}} + \underbrace{\gamma\sum_{t = 1}^{T} \lambda_t\frac{\sum_{i=1}^{N_t(s_t,a_t)}\left(V^{\rref}_{t_i}(s_{t_i+1})-P_{s_t,a_t}V^{\rref}_t\right)}{N_t(s_t,a_t)}}_{\eqqcolon \mathcal{R}_{2,2}}.
\end{equation*}

Note that $\lambda_t \le 1 + \frac{1-\gamma}{2}$ because of the property $\sum_{N = n}^{\infty} \eta_n^N \le 1+ \frac{1-\gamma}{2}$ in (<ref>) of Lemma <ref>. In the following, we shall control these two terms separately.

Step 1: bounding $\mathcal{R}_{2,1}$.

We begin by constructing the necessary notation and verify the conditions for Lemma <ref>. Let

\begin{align}
W_i \coloneqq V^{\rref}_{i} - V^{\star}
\qquad \text{and} \qquad
u_i(s_i,a_i) \coloneqq \lambda_i, \label{R21-Wu}
\end{align}

where $\lambda_i$ is as defined in (<ref>). Clearly, $W_i$ and $u_i(s_i,a_i)$ are deterministic at the end of the $(i-1)$-th step, given $N(s_i,a_i)$. Moreover, define

\begin{align}
\left|u_i(s_i,a_i) \right| \leq 1+\frac{1-\gamma}{2} \eqqcolon C_{\mathrm{u}}
\qquad \text{and} \qquad
\norm{W_i}_\infty \leq \frac{1}{1-\gamma} \eqqcolon C_{\mathrm{w}}. \label{R21-cw-cu}
\end{align}

Hence, we can apply Lemma <ref> with (<ref>) and (<ref>) and conclude that with probability at least $1- \delta/2$,

\begin{align}
\cR_{2,1} &\le \gamma\left|\sum_{t = 1}^{T} \lambda_t \left(P_{t} - P_{s_t,a_t}\right)\left(V^* - V^{\rref}_{t}\right)\right|\nonumber\nonumber \\
& \lesssim \gamma\sqrt{C_{\mathrm{u}}^{2}C_{\mathrm{w}}SA\sum_{i=1}^{T}\mathbb{E}_{i-1}\left[P_{i}W_{i}\right]\log\frac{T}{\delta}}+C_{\mathrm{u}}C_{\mathrm{w}}SA\log\frac{T}{\delta}\nonumber\nonumber \\
& \lesssim \gamma\sqrt{\frac{SA}{1-\gamma}\sum_{i=1}^{T}\mathbb{E}_{i-1}\left[P_{i}\big(V^{\rref}_i-V^{\star}\big)\right]\log\frac{T}{\delta}}+\frac{SA}{1-\gamma}\log\frac{T}{\delta}\nonumber\nonumber \\
&= \gamma\sqrt{\frac{SA}{1-\gamma} \bigg\{ \sum_{t=1}^{T}P_{s_{t},a_{t}}\big(V^{\rref}_t-V^{\star}\big) \bigg\} \log\frac{T}{\delta}}+\frac{SA}{1-\gamma}\log\frac{T}{\delta}.
\label{eq:R21-1}
\end{align}

To finish the upper bound on $\cR_{2,1}$, it remains to control

\begin{equation}\label{eq:R21-1.5}
\sum_{t=1}^{T}P_{s_{t},a_{t}}\left(V^{\rref}_t-V^{\star}\right) = \sum_{t=1}^{T}P_{t}\left(V^{\rref}_t-V^{\star}\right) + \sum_{t=1}^{T}\left(P_{s_{t},a_{t}} - P_t\right)\left(V^{\rref}_t-V^{\star}\right),
\end{equation}

which can be further decomposed into two terms. Let us first examine the first term:

\begin{align}
\sum_{t=1}^{T}P_{t}\big(V^{\rref}_t-V^{\star}\big) &\overset{\mathrm{(i)}}{\leq} \sum_{t=1}^{T}P_{t}\big(V_t + 9 -V^{\star}\big) \nonumber \\
&\leq 9T + \sum_{t=1}^{T}\big(V_t(s_{t+1}) -V^{\star}(s_{t+1})\big) \notag\\
&\overset{\mathrm{(ii)}}{\lesssim} T + \frac{SA\log^2\frac{SAT}{\delta}}{(1-\gamma)^{7/2}} + \sqrt{\frac{SAT\log\frac{SAT}{\delta}}{(1-\gamma)^5}} \label{eq:R21-2}
\end{align}

with probability at least $1-{\delta}/{4}$. Above, (i) holds according to (<ref>), and (ii) is valid since

\begin{align*}
\sum_{t=1}^{T}\big(V_t(s_{t+1}) -V^{\star}(s_{t+1})\big) &\leq \sum_{t=1}^{T}\big(V_t(s_{t+1})-V^{\pi_{t+1}}(s_{t+1})\big) \lesssim \frac{SA\log^2\frac{SAT}{\delta}}{(1-\gamma)^{7/2}} + \sqrt{\frac{SAT\log\frac{SAT}{\delta}}{(1-\gamma)^5}},
\end{align*}

where the first inequality follows since $V^{\star}\geq V^{\pi_{t+1}}$, and the second inequality comes from (<ref>) in Lemma <ref>.

Additionally, for the second term in (<ref>), the Azuma-Hoeffding inequality (Theorem <ref>) directly leads to

\begin{align*}
\left|\sum_{t=1}^{T}\left(P_{t}-P_{s_{t},a_{t}}\right)\left(V^{\rref}_t-V^{\star}\right)\right| & \lesssim \sqrt{\frac{T}{(1-\gamma)^2}\log \frac{1}{\delta}}
\end{align*}

with probability at least $1-\delta/4$.

Together, we have that

\begin{align}
\sum_{t=1}^{T}P_{s_{t},a_{t}}\left(V^{\rref}_t-V^{\star}\right) & \leq \sum_{t=1}^{T}P_{t}\left(V^{\rref}_t-V^{\star}\right)+\left|\sum_{t=1}^{T}\left(P_{t}-P_{s_{t},a_{t}}\right)\left(V^{\rref}_t-V^{\star}\right)\right| \notag\\
& \lesssim T + \frac{SA\log^2\frac{SAT}{\delta}}{(1-\gamma)^{7/2}} + \sqrt{\frac{SAT\log\frac{SAT}{\delta}}{(1-\gamma)^5}} \label{eq:R21-3}
\end{align}

with probability at least $1-\delta/2$.

Finally, substituting this inequality into (<ref>) allows us to conclude with

\begin{align}
&\quad\ \gamma\left|\sum_{t = 1}^{T} \lambda_t \left(P_{t} - P_{s_t,a_t}\right)\left(V^* - V^{\rref}_{t}\right)\right| \nonumber \\
&  \lesssim \gamma\sqrt{\frac{SA}{1-\gamma} \bigg\{ \sum_{t=1}^{T}P_{s_{t},a_{t}}\big(V^{\rref}_t-V^{\star}\big) \bigg\} \log\frac{T}{\delta}}+\frac{SA}{1-\gamma}\log\frac{T}{\delta}\nonumber \\
& \lesssim \gamma\sqrt{\frac{SA}{1-\gamma} \left(T + \frac{SA\log^2\frac{SAT}{\delta}}{(1-\gamma)^{7/2}} + \sqrt{\frac{SAT\log\frac{SAT}{\delta}}{(1-\gamma)^5}}\right) \log\frac{T}{\delta}}+\frac{SA}{1-\gamma}\log\frac{T}{\delta}\nonumber\\
&\lesssim \sqrt{\frac{SA}{1-\gamma}\left(T + \frac{SA\log^2\frac{SAT}{\delta}}{(1-\gamma)^{7/2}} + \frac{SA}{(1-\gamma)^5}\log\frac{SAT}{\delta}\right)\log\frac{T}{\delta}}+\frac{SA}{1-\gamma}\log\frac{T}{\delta}\nonumber\\
& \lesssim\sqrt{\frac{SAT}{1-\gamma}\log\frac{SAT}{\delta}} + \frac{SA}{(1-\gamma)^3}\log^{3/2}\frac{SAT}{\delta} \label{eq:R21-final}
\end{align}

with probability at least $1-\delta$. Above, the penultimate line holds due to $2ab \le a^2 + b^2$.

Step 2: bounding $\mathcal{R}_{2,2}$.

We can start by decomposing $\mathcal{R}_{2,2}$ into three terms as follows:

\begin{align}
\mathcal{R}_{2,2} &\leq \gamma\sum_{t = 1}^{T} \frac{\lambda_t}{N_t(s_t,a_t)}\sum_{i=1}^{N_t(s_t,a_t)}\left(V^{\rref}_{t_i}(s_{t_i+1})-P_{s_t,a_t}V^{\rref}_T\right)\nonumber\\
& = \gamma\sum_{t = 1}^T \sum_{n = N_t(s_t, a_t)}^{N_{T}(s_t, a_t)} \frac{\lambda_t}{n} \left(V^{\rref}_{t}(s_{t+1}) - V^{\rref}_{T}(s_{t+1}) + \left(P_{t} - P_{s_t, a_t} \right)V^{\rref}_{T} \right) \nonumber \\
& \leq  \left(1+\frac{1-\gamma}{2}\right)\log T \sum_{t = 1}^T \big(V^{\rref}_{t}(s_{t+1}) - V^{\rref}_{T}(s_{t+1})\big) + \sum_{t = 1}^T \sum_{n = N_t(s_t, a_t)}^{N_{T}(s_t, a_t)} \frac{\lambda_t}{n}\big(P_{t} - P_{s_t, a_t} \big)V^{\star} \nonumber\\
&\qquad + \sum_{t = 1}^T \sum_{n = N_t(s_t, a_t)}^{N_{T}(s_t, a_t)} \frac{\lambda_t}{n}\big(P_{t} - P_{s_t, a_t} \big)\big( V^{\rref}_{T} -V^\star \big), \label{eq:R22-1}
\end{align}

in which the first inequality is due to the monotonicity $V^{\rref}_{t} \ge V^{\rref}_{t+1} \ge \cdots \geq V^{\rref}_{T}$, and the last inequality is due to the facts that $\sum_{n = N_t(s_t, a_t)}^{N_{T}(s_t, a_t)} \frac{1}{n} \leq \log T$ (harmonic number) and $\lambda_t \leq 1+\frac{1-\gamma}{2}$ (cf. (<ref>)). To proceed, we shall control the three terms in (<ref>) separately.

The first term in (<ref>) can be controlled with Lemma <ref> (cf. (<ref>)) as follows:

\begin{align}
&\quad\ \sum_{t = 1}^T \big(V^{\rref}_{t}(s_{t+1}) - V^{\rref}_{T}(s_{t+1})\big) \notag\\
&\lesssim \frac{\left(SA\right)^{3/4}T^{1/4}}{(1-\gamma)^{13/4}}\left(\log\frac{SAT}{\delta}\right)^{5/4} + \frac{SA}{(1-\gamma)^6}\log \frac{SAT}{\delta} + \sqrt{\frac{SA\log^2 T}{(1-\gamma)^5}\sum_{t=1}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)} \notag\\
&\lesssim \sqrt{\frac{SAT}{1-\gamma}\log^{2}\frac{SAT}{\delta}} + \frac{SA}{(1-\gamma)^6}\log^{3/2} \frac{SAT}{\delta} + \sqrt{\frac{SA\log^2 T}{(1-\gamma)^5}\sum_{t=1}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)} \label{eq:R22-1-1}
\end{align}

with probability at least $1- {\delta}/{3}$. Above, the last inequality is by $2ab \le a^2 + b^2$.

For the second term in (<ref>), let us first construct the necessary notation and verify the conditions for Lemma <ref>. We can set

\begin{align}
W_i \coloneqq V^{\star},
\qquad \text{and} \qquad
u_i(s_i,a_i) \coloneqq \sum_{n = N_i(s_i, a_i)}^{N_T(s_i,a_i)} \frac{\lambda_{i}}{n}. \label{R22-Wu}
\end{align}

Clearly, $W_i$ and $u_i(s_i,a_i)$ are deterministic at the end of the $(i-1)$-th step, given $N_T(s_i,a_i)$. Furthermore, let

\begin{align}
\left| u_i(s_i,a_i) \right|
\leq \left(1+\frac{1-\gamma}{2}\right)\sum_{n = N_i(s_i, a_i)}^{N_T(s_i,a_i)} \frac{1}{n}\leq \left(1+\frac{1-\gamma}{2}\right)\log T \eqqcolon C_{\mathrm{u}} \label{R22-cu}
\end{align}

due to the facts that $\sum_{n = N_t(s_t, a_t)}^{N_{T}(s_t, a_t)} \frac{1}{n} \leq \log T$ (harmonic number) and $\lambda_t \leq 1+\frac{1-\gamma}{2}$ (cf. (<ref>)), and

\begin{align}
\norm{W_i}_\infty \leq \frac{1}{1-\gamma} \eqqcolon C_{\mathrm{w}}. \label{R22-cw}
\end{align}

Hence, we can apply Lemma <ref> with (<ref>), (<ref>) and (<ref>) and conclude that with probability at least $1-{\delta}/{3}$,

\begin{align}
&\quad\ \left|\sum_{t = 1}^T \sum_{n = N_t(s_t, a_t)}^{N_T(s_t, a_t)} \frac{\lambda_t}{n}\left(P_{t} - P_{s_t, a_t} \right)V^{\star}\right| = \left|\sum_{t = 1}^T X_{t} \right| \nonumber\\
& \lesssim \sqrt{ C_{\mathrm{u}}^{2} SA \sum_{i=1}^{T}\mathbb{E}_{i-1}\left[\left|(P_{i}-P_{s_{i},a_{i}})W_{i}\right|^{2}\right] \log\frac{T}{\delta} }  + C_{\mathrm{u}} C_{\mathrm{w}} SA  \log\frac{T}{\delta}  \notag\\
& \overset{\mathrm{(i)}}{\asymp} \sqrt{\sum_{t=1}^{T} \Var_{s_t, a_t}(V^{\star}) \cdot SA\log^3\frac{T}{\delta} }  + \frac{SA}{1-\gamma} \log^2\frac{T}{\delta}  \notag\\
& \overset{\mathrm{(ii)}}{\lesssim} \sqrt{SA\left(\frac{T}{1-\gamma} + \sqrt{\frac{SAT\log\frac{SAT}{\delta}}{(1-\gamma)^7}} + \frac{SA\log^2\frac{SAT}{\delta}}{(1-\gamma)^{9/2}}\right)\log^3\frac{SAT}{\delta}} + \frac{SA}{1-\gamma}\log^2\frac{T}{\delta} \notag\\
&  \lesssim \sqrt{\frac{SAT}{1-\gamma}\log^{3}\frac{SAT}{\delta} + \sqrt{\frac{SAT}{(1-\gamma)^7}}\log^{7/2}\frac{SAT}{\delta}} + \frac{SA}{(1-\gamma)^{9/4}}\log^{5/2}\frac{SAT}{\delta} \notag\\
& \overset{\mathrm{(iii)}}{\lesssim} \sqrt{\frac{SAT}{1-\gamma}\log^{3}\frac{SAT}{\delta} + \frac{\log^{4}\frac{SAT}{\delta}}{(1-\gamma)^6}} + \frac{SA}{(1-\gamma)^{9/4}}\log^{5/2}\frac{SAT}{\delta} \notag\\
&\lesssim \sqrt{\frac{SAT}{1-\gamma}\log^3\frac{SAT}{\delta}} + \frac{SA}{(1-\gamma)^{3}}\log^{2}\frac{SAT}{\delta}, \label{eq:R22-2-1}
\end{align}

in which (i) comes from the definition of variance in (<ref>); (ii) holds due to (<ref>); (iii) is valid since

\begin{equation*}
\sqrt{\frac{SAT}{(1-\gamma)^7}}\log^{7/2}\frac{SAT}{\delta} = \sqrt{\frac{SAT}{1-\gamma}}\log^{3/2}\frac{SAT}{\delta}\cdot\frac{\log^{2}\frac{SAT}{\delta}}{(1-\gamma)^3} \lesssim \frac{SAT}{1-\gamma}\log^{3}\frac{SAT}{\delta} + \frac{\log^{4}\frac{SAT}{\delta}}{(1-\gamma)^6}
\end{equation*}

due to $2ab \le a^2 + b^2$ (by Cauchy-Schwarz).

Finally, for the third term in (<ref>), in order to get a tight bound in the presence of the dependency between $P_t$ and $V_{T}^{\mathrm{R}}$, we use the standard epsilon-net argument (see, e.g., 40), whose details are deferred to Appendix <ref>. The final bound on this term is

\begin{align}
& \left|\sum_{t = 1}^T \sum_{n = N_t(s_t, a_t)}^{N_{T}(s_t, a_t)} \frac{\lambda_t}{n}\big(P_{t} - P_{s_t, a_t} \big)\big( V^{\rref}_{T} -V^\star \big)\right| \lesssim \frac{SA}{(1-\gamma)^{3}} \log^{5/2}\frac{SAT}{\delta} + \sqrt{\frac{SAT}{1-\gamma}\log^{3}\frac{SAT}{\delta}}.
\label{eq:R22-3}
\end{align}

Bringing (<ref>), (<ref>) and (<ref>) into (<ref>), with a union bound argument, we can demonstrate

\begin{align}
\mathcal{R}_{2,2} &\leq  C_{2,2} \Bigg\{ \sqrt{\frac{SAT}{1-\gamma}\log^{3}\frac{SAT}{\delta}} + \frac{SA}{(1-\gamma)^6}\log^{5/2} \frac{SAT}{\delta} + \sqrt{\frac{\log^2 T}{(1-\gamma)^5}\sum_{t=1}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)}\Bigg\}
\label{eq:R22-final}
\end{align}

with probability at least $1-\delta$, where $C_{3,2}>0$ is some constant.

Step 3: combining the preceding bounds.

Taking (<ref>) and (<ref>) together, we immediately arrive at

\begin{align}
\mathcal{R}_2 \leq \left| \mathcal{R}_{2,1} \right|  +  \mathcal{R}_{2,2} &\leq  C_{\mathrm{r},2} \left\{ \sqrt{\frac{SAT}{1-\gamma}\log^{3}\frac{SAT}{\delta}} + \frac{SA}{(1-\gamma)^7}\log^{5/2} \frac{SAT}{\delta} + \sqrt{\frac{SA\log^2 T}{(1-\gamma)^5}\sum_{t=1}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)}\right\}
\end{align}

with probability at least $1-2\delta$, where $C_{\mathrm{r},2}>0$ is some constant.
This immediately concludes the proof.

§.§.§ Proof of (<ref>): An Epsilon-Net Argument

Step 1: concentration on a fixed vector.

Let us establish a concentration bound over a fixed vector, the choice of which we will later specify when we introduce our epsilon net. Consider a fixed vector $V^{\mathrm{d}} \in \mathbb{R}^{S}$ satisfying:

\begin{align}
V^{\star} \leq V^{\mathrm{d}} &\leq \frac{1}{1-\gamma}.
\label{eq:Vd-assumption}
\end{align}

We intend to derive a bound on the following quantity as in (<ref>):

\begin{equation*}
\sum_{t = 1}^T \sum_{n = N_t(s_t, a_t)}^{N_{T}(s_t, a_t)} \frac{\lambda_t}{n}\big(P_{t} - P_{s_t, a_t} \big)\big( V^{\mathrm{d}} -V^\star \big).
\end{equation*}

Let us first construct the necessary notation and verify the conditions for Lemma <ref>. We can set

\begin{align}
W_i \coloneqq V^{\mathrm{d}} - V^{\star}
\qquad \text{and} \qquad
u_i(s_i,a_i) \coloneqq \sum_{n = N_i(s_i, a_i)}^{N_T(s_i,a_i)} \frac{\lambda^{i}_h}{n}. \label{Vd-Wu}
\end{align}

Clearly, $W_i$ and $u_i(s_i,a_i)$ are deterministic at the end of the $(i-1)$-th step, given $N_T(s_i,a_i)$. Furthermore, let

\begin{align}
\left| u_i(s_i,a_i) \right|
\leq \left(1 + \frac{1-\gamma}{2}\right)\sum_{n = N_i(s_i,a_i)}^{N_T(s_i,a_i)} \frac{1}{n} &\leq \left(1 + \frac{1-\gamma}{2}\right)\log T \eqqcolon C_{\mathrm{u}} \label{Vd-cu}
\end{align}

due to the facts that $\sum_{n = N_t(s_t, a_t)}^{N_{T}(s_t, a_t)} \frac{1}{n} \leq \log T$ (harmonic number) and $\lambda_t \leq 1+\frac{1-\gamma}{2}$ (cf. (<ref>)), and

\begin{align}
\norm{W_i}_\infty \leq \frac{1}{1-\gamma} \eqqcolon C_{\mathrm{w}}. \label{Vd-cw}
\end{align}

Hence, we can apply Lemma <ref> with (<ref>), (<ref>) and (<ref>) and conclude that with probability at least $1-\delta_0$,

\begin{align}
&\quad\ \left|\sum_{t = 1}^T \sum_{n = N_t(s_t, a_t)}^{N_{T}(s_t, a_t)} \frac{\lambda_t}{n}\left(P_{t} - P_{s_t, a_t} \right)\left( V^{\mathrm{d}} -V^\star \right)\right|=\left|\sum_{t=1}^{T}X_{t}\right|\nonumber\\
& \lesssim\sqrt{C_{\mathrm{u}}^{2}C_{\mathrm{w}}\left\{\sum_{i=1}^{T}\mathbb{E}_{i-1}\left[P_{i}W_{i}\right]\right\}\log\frac{T^{SA}}{\delta_{0}}}+C_{\mathrm{u}}C_{\mathrm{w}}\log\frac{T^{SA}}{\delta_{0}}\nonumber\\
& \lesssim \sqrt{\frac{\log^2 T}{1-\gamma}\left\{\sum_{t=1}^{T}P_{s_{t},a_{t}}\left(V^{\mathrm{d}}-V^{\star}\right)\right\}\log\frac{T^{SA}}{\delta_{0}}} + \frac{\log T}{1-\gamma} \log\frac{T^{SA}}{\delta_{0}}.\label{eq:Vd-concentration}
\end{align}

The choice of $\delta_0$ will be specified momentarily.

Step 2: constructing an epsilon net.

In this step, we construct a properly-sized epsilon net that can cover the space of $V^\rref_T$. Specifically, we will construct an epsilon net $\cN_{\alpha}$ (the parameter $\alpha$ will be specified shortly) such that:

* For any $V \in [0,\frac{1}{1-\gamma}]^S$, one can find a point $V^{\mathrm{net}} \in \cN_{\alpha}$ such that
$$0\leq V (s) - V^{\mathrm{net}} (s) \leq \alpha \qquad \text{for all }s\in \cS;$$

* The cardinality of $\cN_{\alpha}$ satisfies the following bound:

\begin{equation}
\left| \mathcal{N}_{\alpha} \right| \leq \left( \frac{1}{(1-\gamma)\alpha} \right)^S.
\label{eq:N-cardinality}
\end{equation}

Clearly, such epsilon net exists by letting it be all intersection points in a grid on $[0,\frac{1}{1-\gamma}]^S$ with interval length $\alpha$. Now, we extend the concentration bound (<ref>) in Step 1 to all members of this epsilon net $\cN_\alpha$. Set $\delta_0 = \frac{\delta}{6} / \left( \frac{1}{(1-\gamma)\alpha} \right)^S$. Taking a union bound over all vectors in $\cN_\alpha$, (<ref>) gives that with probability at least $1- \delta_0 \left( \frac{1}{(1-\gamma)\alpha} \right)^S = 1-\delta/6$,

\begin{align}
&\quad\ \left|\sum_{t = 1}^T \sum_{n = N_t(s_t, a_t)}^{N_{T}(s_t, a_t)} \frac{\lambda_t}{n}\left(P_{t} - P_{s_t, a_t} \right)\left(V^{\mathrm{net}}-V^{\star}\right)\right|\nonumber\\
& \lesssim \sqrt{\frac{\log^2 T}{1-\gamma}\sum_{t=1}^{T}P_{s_{t},a_{t}}\left(V^{\mathrm{net}}-V^{\star}\right)\log\frac{T^{SA}}{\delta_{0}}}+ \frac{\log T}{1-\gamma} \log\frac{T^{SA}}{\delta_{0}} \notag\\
& \le \sqrt{\frac{SA\log^2 T}{1-\gamma}\sum_{t=1}^{T}P_{s_{t},a_{t}}\left(V^{\mathrm{net}}-V^{\star}\right)\log\frac{T}{(1-\gamma)^S\alpha^S\delta}}+ \frac{SA\log T}{1-\gamma} \log\frac{T}{(1-\gamma)^S\alpha^S\delta}
\label{eq:N-concentration}
\end{align}

simultaneously for all elements $V^{\mathrm{net}} \in \mathcal{N}_{\alpha} $.

Step 3: obtaining a uniform bound.

Now, we are ready to establish a uniform bound over the entire space of $V^\rref_T$, which is just all optimistic vectors in $[0,\frac{1}{1-\gamma}]^S$. Consider an arbitrary vector
$V^{\mathrm{u}}\in \RR^S$ satisfying $V^{\star} \leq V^{\mathrm{u}} \leq \frac{1}{1-\gamma}$. By the construction of $\cN_\alpha$, one can find a point $V^{\mathrm{net}} \in \mathcal{N}_{\alpha}$
such that

\begin{align}
0\leq  V^{\mathrm{u}}(s) - V^{\mathrm{net}}(s) \leq \alpha \qquad \text{for all }s\in \cS.
\label{eq:Vd-Vnet-proximity}
\end{align}

Setting $\alpha = \frac{1}{(1-\gamma)T^{1/S}}$, we can deduce that

\begin{align}
&\quad\ \left|\sum_{t = 1}^T \sum_{n = N_t(s_t, a_t)}^{N_{T}(s_t, a_t)} \frac{\lambda_t}{n}\left(P_{t} - P_{s_t, a_t} \right)\left(V^{\mathrm{u}}-V^{\star}\right)\right|\nonumber\\
&\leq \left|\sum_{t = 1}^T \sum_{n = N_t(s_t, a_t)}^{N_{T}(s_t, a_t)} \frac{\lambda_t}{n}\left(P_{t} - P_{s_t, a_t} \right)\left(V^{\mathrm{net}}-V^{\star}\right)\right|+\left|\sum_{t = 1}^T \sum_{n = N_t(s_t, a_t)}^{N_{T}(s_t, a_t)} \frac{\lambda_t}{n}\left(P_{t} - P_{s_t, a_t} \right)\left(V^{\mathrm{u}} - V^{\mathrm{net}}\right)\right|\nonumber\\
&\overset{(\mathrm{i})}{\lesssim} \left|\sum_{t = 1}^T \sum_{n = N_t(s_t, a_t)}^{N_{T}(s_t, a_t)} \frac{\lambda_t}{n}\left(P_{t} - P_{s_t, a_t} \right)\left(V^{\mathrm{net}}-V^{\star}\right)\right|+T\alpha\log T\nonumber\\
& \lesssim \sqrt{\frac{SA\log^2 T}{1-\gamma}\sum_{t=1}^{T}P_{s_{i},a_{i}}\left(V^{\mathrm{net}}-V^{\star}\right)\log\frac{T}{(1-\gamma)^S\alpha^S\delta}}+ \frac{SA\log T}{1-\gamma} \log\frac{T}{(1-\gamma)^S\alpha^S\delta}+T\alpha\log T \notag\\
& \overset{(\mathrm{ii})}{\asymp} \sqrt{\frac{SA\log^2 T}{1-\gamma}\sum_{t=1}^{T}P_{s_{i},a_{i}}\left(V^{\mathrm{net}}-V^{\star}\right)\log\frac{T}{\delta}}+ \frac{SA\log T}{1-\gamma} \log\frac{T}{\delta},
\label{eq:uniform-bound-all-Vd}
\end{align}

in which (i) is due to

\begin{align}
&\quad\ \left|\sum_{t = 1}^T \sum_{n = N_t(s_t, a_t)}^{N_{T}(s_t, a_t)} \frac{\lambda_t}{n}\left(P_{t} - P_{s_t, a_t} \right)\left(V^{\mathrm{u}} - V^{\mathrm{net}}\right)\right|\nonumber\\
&\leq \left|\sum_{t = 1}^T \sum_{n = N_t(s_t, a_t)}^{N_{T}(s_t, a_t)} \frac{\lambda_t}{n}\left(\norm{P_{t}}_1 + \norm{P_{s_t, a_t}}_1 \right)\norm{V^{\mathrm{u}} - V^{\mathrm{net}}}_\infty\right|\nonumber\\
& \leq 2\left(1 + \frac{1-\gamma}{2}\right)T \alpha\log T
\end{align}