loose. In our analysis, ${\mathcal{B}}_{R^{2}}\cap{\mathcal{B}}_{0}$ serves as
the ‘coarse’ event where the concentration results hold with a larger
confidence radius, and ${\mathcal{B}}_{R}\cap{\mathcal{B}}_{V}$ serves as a
‘refined’ event where the confidence radius (that is $\beta_{R}$ and
$\beta_{V}$) is much is tighter. Our first result is that
${\mathcal{B}}_{R^{2}}\cap{\mathcal{B}}_{0}$ holds with high probability as
shown in Lemma C.1 and C.2. Their proofs are collected in Appendix E.1 and
E.2.

######  Lemma C.1.

If we set

$\widetilde{\tau}_{0}=\max\left\\{\frac{\sqrt{2\kappa}\sigma_{R^{2}}}{\sigma_{\min}},2\sqrt{d}\right\\}\bigg{/}\sqrt{\log\frac{2HK^{2}}{\delta}},$
(C.4)

the event ${\mathcal{B}}_{R^{2}}$ holds with probability at least $1-3\delta$.

######  Lemma C.2.

The event ${\mathcal{B}}_{0}$ holds with probability at least $1-3\delta$.

These coarse confidence sets are then used to estimate variance for the reward
functions and value functions. A key step is to show the adapted variance
$\sigma_{h,k}$’s are indeed upper bounds of these variances (that is
$[{\mathbb{V}}_{h}R_{h}](s_{h,k},a_{h,k})+[{\mathbb{V}}_{h}V_{h+1}^{*}](s_{h,k},a_{h,k})$)
for all $h\in[H]$. A frequently used argument is backward induction. That is
given the estimation is optimistic at the stage $h+1$, we then show the
optimistic estimation is maintained at the stage $h$. Induction over the stage
$h$ would complete the proof. The following lemma provides estimation error
bounds for $[{\mathbb{V}}_{h}R_{h}](s_{h,k},a_{h,k})$ and shows that the event
${\mathcal{B}}_{R}$ holds with high probability. Its proof is deferred in
Appendix E.4.

######  Lemma C.3.

If we set

$\tau_{0}=\max\\{\sqrt{2\kappa},2\sqrt{d}\\}\bigg{/}\sqrt{\log\frac{2HK^{2}}{\delta}},$
(C.5)

the event ${\mathcal{B}}_{R}$ holds with probability at least $1-6\delta$.

In Lemma C.4, we show that that our constructed value functions $\overline{V}$
and $\underline{V}$ are indeed optimistic and pessimistic estimators of the
true value functions under the event defined before. Its proof is deferred in
Appendix E.5.

######  Lemma C.4 (Optimism and pessimism).

For any $h\in[H]$, if ${\mathcal{B}}_{R}\cap{\mathcal{B}}_{h}$ holds, for any
$k\in[K]\cup\\{0\\}$,

$\underline{V}_{h}^{k}(\cdot)\leq
V_{h}^{*}(\cdot)\leq\overline{V}_{h}^{k}(\cdot).$

With the established optimism and pessimism, we can establish upper bounds for
the estimation errors of the three terms, namely
$[{\mathbb{V}}_{h}V_{h+1}^{*}](s_{h,k},a_{h,k})$,
$\left[{\mathbb{V}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{*})\right](s_{h,k},a_{h,k})$,
and
$\left[{\mathbb{V}}_{h}(\underline{V}_{h+1}^{k}-V_{h+1}^{*})\right](s_{h,k},a_{h,k})$
in the following lemmas. Their proofs are deferred in Appendix E.6 and E.7.

######  Lemma C.5.

On the event ${\mathcal{B}}_{0}\cap{\mathcal{B}}_{h+1}$, it follows that for
all $k\in[K]$

$\left|\left[{\mathbb{V}}_{h}V_{h+1}^{*}-\widehat{\mathbb{V}}_{h}\overline{V}_{h+1}^{k}\right](s_{h,k},a_{h,k})\right|\leq
U_{h,k}$

where

$U_{h,k}=\min\left\\{{\mathcal{V}}^{2},11{\mathcal{H}}\beta_{0}\cdot\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+4{\mathcal{H}}\cdot\widehat{\mathbb{P}}_{h,k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h,k},a_{h,k})\right\\}$
(4.9)

with
$\widehat{\mathbb{P}}_{h,k}(\cdot|s,a)={\bm{\mu}}_{h,k-1}^{\top}{\bm{\phi}}(s,a)$.

######  Lemma C.6.

On the event ${\mathcal{B}}_{0}\cap{\mathcal{B}}_{R}\cap{\mathcal{B}}_{h+1}$,
it follows that for all $j\leq k\leq K$

$\max\left\\{\left[{\mathbb{V}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{*})\right](s_{h,j},a_{h,j}),\left[{\mathbb{V}}_{h}(\underline{V}_{h+1}^{k}-V_{h+1}^{*})\right](s_{h,j},a_{h,j})\right\\}\leq
E_{h,j}$

where

$E_{h,j}=\min\left\\{{\mathcal{H}}^{2},2{\mathcal{H}}\beta_{0}\|{\bm{\phi}}_{h,j}\|_{{\bm{H}}_{h,j-1}^{-1}}+{\mathcal{H}}\cdot\left[\widehat{\mathbb{P}}_{h,j}(\overline{V}_{h+1}^{j}-\underline{V}_{h+1}^{j})\right](s_{h,j},a_{h,j})\right\\}$
(4.7)

with
$\widehat{\mathbb{P}}_{h,j}(\cdot|s,a)={\bm{\mu}}_{h,j-1}^{\top}{\bm{\phi}}(s,a)$.

With the last four lemmas, one can easily prove $\sigma_{h,k}$ indeed serves
as an upper bound of the true variance of $V_{h+1}^{*}$ at stage $h$.
Therefore, by the backward induction, we can prove the following lemma whose
proof is in Appendix E.8.

######  Lemma C.7.

On the event ${\mathcal{B}}_{0}\cap{\mathcal{B}}_{R}$, the event
${\mathcal{B}}_{V}$ holds with probability at least $1-2\delta$.

###  C.2 Regret Analysis

In the previous subsection, we know that with probability at least
$1-15\delta$, the event ${\mathcal{B}}_{V}\cap{\mathcal{B}}_{R}$ holds. Based
on Lemma C.4, the optimism implies that

$\mathrm{Reg}(K):=\sum_{k=1}^{K}(V_{1}^{*}-V_{1}^{\pi_{k}})(s_{1,k})\leq\sum_{k=1}^{K}(\overline{V}_{1}^{k}-V_{1}^{\pi_{k}})(s_{1,k}).$

We then relate the suboptimality gap
$\sum_{k=1}^{k}(\overline{V}_{1}^{k}-V_{1}^{\pi_{k}})(s_{1,k})$ to the term
$\sum_{k=1}^{K}\sum_{h=1}^{H}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}$ in
Lemma C.8. We emphasize that the bound in Lemma C.8 is much finer than
previous bounds (e.g., Lemma B.1 in [He et al., 2022]) in the sense that the
rest term is $\widetilde{\mathcal{O}}(H{\mathcal{H}})$ instead of previous
$\widetilde{\mathcal{O}}(\sqrt{HK}{\mathcal{H}})$. This is because we adapt a
variance-aware Berinstain inequality to relate the variance of
$\sum_{k=1}^{k}(\overline{V}_{1}^{k}-V_{1}^{\pi_{k}})(s_{1,k})$ with its
expectations and use a recursion argument to simplify the final expression,
while previous work directly apply Azuma-Hoeffding inequality to analyze the
concentration of
$\sum_{k=1}^{k}(\overline{V}_{1}^{k}-V_{1}^{\pi_{k}})(s_{1,k})$, which
inevitably introduces the additional $\widetilde{\mathcal{O}}(\sqrt{K})$
dependence. Its proof is collected in Appendix E.9.

######  Lemma C.8 (Suboptimality gap).

With probability at least $1-\delta$, on the event
${\mathcal{B}}_{R}\cap{\mathcal{B}}_{V}$, it follows that

$\displaystyle\sum_{k=1}^{K}(\overline{V}_{1}^{k}-V_{1}^{\pi_{k}})(s_{1,k})\leq
6\beta\sum_{k=1}^{K}\sum_{h=1}^{H}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+38H{\mathcal{H}}\log\frac{4\lceil\log_{2}HK\rceil}{\delta}\
\text{and}\ $
$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})(s_{h,k},a_{h,k})\leq
8H\beta\sum_{k=1}^{K}\sum_{h=1}^{H}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+38H^{2}{\mathcal{H}}\log\frac{4\lceil\log_{2}HK\rceil}{\delta}.$

Using a similar argument, we provide a finer bound for the gap between
optimistic and pessimistic value functions
$\sum_{k=1}^{K}\sum_{h=1}^{H}{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h,k},a_{h,k})$
in Lemma C.9. Its proof is provided in Appendix E.10.

######  Lemma C.9 (Gap between optimistic and pessimistic value functions).

With probability at least $1-\delta$, on the event
${\mathcal{B}}_{V}\cap{\mathcal{B}}_{R}$, it follows that

$\sum_{k=1}^{K}\sum_{h=1}^{H}{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h,k},a_{h,k})\leq
12H\beta\sum_{k=1}^{K}\sum_{h=1}^{H}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+38H^{2}{\mathcal{H}}\log\frac{4\lceil\log_{2}HK\rceil}{\delta}.$

The following issue is to upper bound the term
$\sum_{k=1}^{K}\sum_{h=1}^{H}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}$.
Since the estimation of reward variance concerns the other term
$\sum_{k=1}^{K}\sum_{h=1}^{H}\|\widetilde{{\bm{\phi}}}_{h,k}\|_{\widetilde{{\bm{H}}}_{h,k-1}^{-1}}$,
we are motivated to analyze them simultaneously via
$\sum_{k=1}^{K}\sum_{h=1}^{H}b_{h,k}$ where
$b_{h,k}=\max\left\\{\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}},\|\widetilde{{\bm{\phi}}}_{h,k}\|_{\widetilde{{\bm{H}}}_{h,k-1}^{-1}}\right\\}$.
Previous works [Hu et al., 2022, He et al., 2022] mainly use Cauchy–Schwarz
inequality to analyze it and obtain

$\sum_{k=1}^{K}\sum_{h=1}^{H}b_{h,k}\leq\sqrt{\left(\sum_{k=1}^{K}\sum_{h=1}^{H}\sigma_{h,k}^{2}\right)\left(\sum_{k=1}^{K}\sum_{h=1}^{H}\max\\{w_{h,k}^{2},\widetilde{w}_{h,k}^{2}\\}\right)}=\widetilde{\mathcal{O}}\left(\sqrt{dH}\cdot\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\sigma_{h,k}^{2}}\right).$

where the last equality uses the elliptical potential lemmas in Lemma F.5. A
standard analysis of the law of total variation would imply
$\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\sigma_{h,k}^{2}}=\widetilde{\mathcal{O}}(\sqrt{H^{2}K})$.
However, this result doesn’t satisfy our target for two reasons. First, due to
the use of adaptive Huber regression, our definition of $\sigma_{h,k}$ is more
complicated than previous algorithms. We need a more elaborate analysis to
handle the additional terms in the definition of $\sigma_{h,k}$’s. Second, the
previous result considers the worst-case scenario, while our target is to
provide a finer variance-aware regret. Therefore, it is imperative to provide
a finer bound for the sum of bonuses $\sum_{k=1}^{K}\sum_{h=1}^{H}b_{h,k}$. We
did it in Lemma C.10.

######  Lemma C.10 (Sum of bonuses).

Set $\lambda=\frac{1}{{\mathcal{H}}^{2}+W^{2}}$. Let ${\mathcal{A}}_{0}$
denote the intersection event of Lemma C.8 and C.9. With probability at least
$1-2\delta$, on the event
${\mathcal{B}}_{R}\cap{\mathcal{B}}_{V}\cap{\mathcal{B}}_{0}\cap{\mathcal{B}}_{R^{2}}\cap{\mathcal{A}}_{0}$,
we have

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}b_{h,k}=$
$\displaystyle\widetilde{\mathcal{O}}\left(\sqrt{dHK{\mathcal{G}}^{*}}+Hd^{0.5}K^{0.5}\sigma_{\min}+\frac{H^{2.5}d^{5.5}{\mathcal{H}}^{2}+Hd^{1.5}\sigma_{R^{2}}}{\sigma_{\min}}\right)$
$\displaystyle\qquad\qquad\widetilde{\mathcal{O}}\left(+H^{3}d^{4.5}{\mathcal{H}}+Hd^{0.5}\sigma_{R}+Hd^{1.5}\right).$

where $\widetilde{\mathcal{O}}(\cdot)$ ignores constant factors and
logarithmic dependence.

We emphasize that Lemma C.10 is perhaps the most technical lemma in our paper.
To address the difficulty mentioned early, we divide the full index set
${\mathcal{I}}:=[H]\times[K]$ into three disjoint subsets
${\mathcal{I}}=\cup_{i=1,2,3}{\mathcal{J}}_{i}$ according to which value
$\sigma_{h,k}$ takes (given $\sigma_{h,k}$ is the maximum value among five
quantities). For those indexes in ${\mathcal{J}}_{1}$ where the bonuses are
small enough, we still use the Cauchy–Schwarz inequality to bound
$\sum_{(h,k)\in{\mathcal{J}}_{1}}b_{h,k}\leq\widetilde{\mathcal{O}}\left(\sqrt{dH}\cdot\sqrt{\sum_{(h,k)\in{\mathcal{I}}}\sigma_{h,k}^{2}}\right)$.
This sum-of-squared-bonus quantity involves
$\sum_{(h,k)\in{\mathcal{I}}}E_{h,k}$ and
$\sum_{(h,k)\in{\mathcal{I}}}J_{h,k}$ which we then pay additional efforts to
analyze. For those indexes in ${\mathcal{J}}_{2}$ or ${\mathcal{J}}_{3}$ where
the bonuses are relatively large, we directly analyze
$\sum_{(h,k)\in{\mathcal{J}}_{2}\cup{\mathcal{J}}_{3}}b_{h,k}$. Thanks to the
particular structure,
$\sum_{(h,k)\in{\mathcal{J}}_{2}\cup{\mathcal{J}}_{3}}b_{h,k}$ contributes to
the non-leading term in the final bound. Putting pieces together, we complete
the proof. A formal proof can be found in Appendix E.11.

At the end of the subsection, we summarize the proof in a few lines.

$\displaystyle\mathrm{Reg}(K)$
$\displaystyle=\sum_{k=1}^{K}(V_{1}^{*}-V_{1}^{\pi_{k}})(s_{1,k})\overset{(a)}{\leq}\sum_{k=1}^{K}(\overline{V}_{1}^{k}-V_{1}^{\pi_{k}})(s_{1,k})$
$\displaystyle\overset{(b)}{\leq}3\beta\sum_{k=1}^{K}\sum_{h=1}^{H}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+38H{\mathcal{H}}\log\frac{4\lceil\log_{2}HK\rceil}{\delta}$
$\displaystyle\overset{(c)}{\leq}3\beta\sum_{k=1}^{K}\sum_{h=1}^{H}b_{h,k}+38H{\mathcal{H}}\log\frac{4\lceil\log_{2}HK\rceil}{\delta}$
$\displaystyle\overset{(d)}{=}\widetilde{\mathcal{O}}\left(d\sqrt{HK{\mathcal{G}}^{*}}+HdK^{0.5}\sigma_{\min}+\frac{H^{2.5}d^{6}{\mathcal{H}}^{2}+Hd^{2}\sigma_{R^{2}}}{\sigma_{\min}}+H^{3}d^{5}{\mathcal{H}}+Hd\sigma_{R}+Hd^{2}\right)$

where $(a)$ follows from the optimism result in Lemma C.4, $(b)$ follows from
the suboptimality gap result in Lemma C.8, $(c)$ uses
$b_{h,k}=\max\left\\{\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}},\|\widetilde{{\bm{\phi}}}_{h,k}\|_{\widetilde{{\bm{H}}}_{h,k-1}^{-1}}\right\\}$,
and $(d)$ follows from sum-of-bonus result in Lemma C.10 and
$\beta=\beta_{R}+\beta_{V}=\widetilde{\mathcal{O}}(\sqrt{d})$.

##  Appendix D Proof of Theorem 4.2

###### Proof of Theorem 4.2.

We consider the two complexities respectively.

##### Space Complexity

First, in order to perform AdaOFUL, VARA needs to store all seen rewards and
feature vectors (i.e., ${\bm{\phi}}_{h,k},\widetilde{{\bm{\phi}}}_{h,k}$),
which is required by all RL/bandit algorithms robust to heavy-tailed rewards
[Shao et al., 2018, Xue et al., 2021, Zhuang and Sui, 2021]. AdaOFUL also
keeps all robustification parameters $\tau_{h,k},\widetilde{\tau}_{h,k}$. It
then incurs ${\mathcal{O}}(HKd)$ space storage in total.

Second, due to the rare-switching technique, one can show that
$\overline{Q}_{h}^{k}$ (or $\underline{Q}_{h}^{k}$) is the minimum (or
maximum) of at most $\widetilde{\mathcal{O}}(dH)$ temporary optimistic (or
pessimistic) functions (see Lemma F.7). It means that we need to store at most
$\widetilde{\mathcal{O}}(dH)$ different versions of
${\bm{\theta}}_{h,k-1},{\bm{\mu}}_{h,k-1}{\bm{V}}_{h+1}^{k},{\bm{H}}_{h,k-1}$’s.
This incurs ${\mathcal{O}}(d^{3}H^{2})$ space cost.

Last, for all $(h,k)\in[H]\times[K]$, we need to trace
$\\{{\bm{\phi}}(s_{h,k},a)\\}_{a\in{\mathcal{A}}}$ to evaluate each
${\bm{\mu}}_{h,k}{\bm{V}}={\bm{H}}_{h,k}^{-1}\sum_{j=1}^{k}\sigma_{h,j}^{-2}{\bm{\phi}}_{h,j}V(s_{h+1,k})$
for
${\bm{V}}\in\\{\overline{{\bm{V}}}_{h+1}^{k},[\overline{{\bm{V}}}_{h+1}^{k}]^{2},\underline{{\bm{V}}}_{h+1}^{k}\\}$,
which takes ${\mathcal{O}}(d|{\mathcal{A}}|HK)$ space.

To sum up, VARA takes ${\mathcal{O}}(d^{3}H^{2}+d|{\mathcal{A}}|HK)$ space.

##### Computational Complexity

First, we use Nesterov accelerated method to compute each
${\bm{\theta}}_{h,k}$. Since the loss function in (4.1) is $\lambda$-strongly
convex and $\left(\lambda+\frac{K}{\sigma_{\min}^{2}}\right)$-smooth, the
computational cost for each ${\bm{\theta}}_{h,k}$ is
$\widetilde{\mathcal{O}}\left(d\sqrt{1+\frac{K}{\lambda(\sigma_{\min}^{*})^{2}}}\right)=\widetilde{\mathcal{O}}(\max\\{d,H^{-3/4}d^{-3/2}K^{3/4}\\})$
and the total cost is
$\widetilde{\mathcal{O}}(HK(d+H^{-3/4}d^{-3/2}K^{3/4}))$. We emphasize that we
don’t need to compute ${\bm{\theta}}_{h,k}$ exactly. It suffices to terminate
at a solution $\widehat{{\bm{\theta}}}_{h,k}$ once its accuracy satisfies
$\|\widehat{{\bm{\theta}}}_{h,k}-{\bm{\theta}}_{h,k}\|_{{\bm{H}}_{h,k}}\leq\sqrt{d}$.
The iteration complexity is proportional to the root of the conditional
number, i.e., $\widetilde{\mathcal{O}}(\max\\{1,d^{-7/4}K^{3/4}\\})$. Since
each iteration takes ${\mathcal{O}}(d)$ operation, the computation complexity
is $\widetilde{\mathcal{O}}(\max\\{d,d^{-3/4}K^{3/4}\\})$.

Second, each time when updating the value function, we take the minimum over
at most $\widetilde{\mathcal{O}}(dH)$ quadratic functions. Moreover, the
Sherman-Morrison formula computes ${\bm{H}}_{h,k}^{-1}$ and its products with
any vectors, which takes ${\mathcal{O}}(d^{2})$ operations. As a result, it
needs $\widetilde{\mathcal{O}}(d^{3}H)$ to evaluate the updated $Q_{h,k}(s,a)$
for a given pair $(s,a)$. Hence, computing $Q_{h,k}(s_{h,k},\cdot)$, choosing
$a_{h,k}=\mathop{\rm argmax}_{a\in{\mathcal{A}}}Q_{h,k}(s_{h,k},a)$, and
estimating the variance $\sigma_{h,k}$ lead to
$\widetilde{\mathcal{O}}(d^{3}H^{2}|{\mathcal{A}}|)$ computational complexity
for each episode.

Last, note
${\bm{\mu}}_{h,k}{\bm{V}}={\bm{H}}_{h,k}^{-1}\sum_{j=1}^{k}\sigma_{h,j}^{-2}{\bm{\phi}}_{h,j}V(s_{h+1,k})$
for any value function $V(\cdot)$. If $V$ remains unchanged, we only need to
compute the new term $\sigma_{h,k}^{-2}{\bm{\phi}}_{h,k}V(s_{h+1,k})$, which
has an $\widetilde{\mathcal{O}}(d^{3}H|{\mathcal{A}}|)$ complexity each time.
If $V$ changes to $V^{\prime}$, we need to recalculate
${\bm{\mu}}_{h,k}{\bm{V}}^{\prime}$, which has an
$\widetilde{\mathcal{O}}(d^{3}H|{\mathcal{A}}|K)$ complexity each time.
Combining the computational complexity for all horizons and noticing that the
number of episodes that trigger the updating criterion is at most
$\widetilde{\mathcal{O}}(dH)$, VARA has a running time of
$\widetilde{\mathcal{O}}(d^{4}|{\mathcal{A}}|H^{3}K+HK(d+H^{-3/4}d^{-3/2}K^{3/4}))$.
In terms of the dependence on $K$, it is slightly worse than LSVI-UCB++’s
$\widetilde{\mathcal{O}}(d^{4}|{\mathcal{A}}|H^{3}K)$ since the adaptive Huber
regression doesn’t have a closed-form solution, but is better than LSVI-UCB’s
$\widetilde{\mathcal{O}}(d^{2}|{\mathcal{A}}|HK^{2})$ due to the rare-
switching mechanism. ∎

##  Appendix E Omitted lemmas in Section C

###  E.1 Proof of Lemma C.1

###### Proof of Lemma C.1.

The proof idea of Lemma C.1 is similar to that of Theorem 3.1 except for the
following changes. First,
$\widetilde{{\bm{\phi}}}_{h,k}=\widetilde{{\bm{\phi}}}(s_{h,k},a_{h,k})\in{\mathbb{R}}^{d}$
is instead the feature vector. Second, in the particular setting, we should
respectively replace $L,B,T,\delta$ therein with $1,W,K,\delta/H$ defined here
and redefine $c_{0},c_{1}$ as
$c_{0}=\frac{1}{6\sqrt{3\log\frac{2HK^{2}}{\delta}}},c_{1}=\frac{1}{42\cdot\frac{2HK^{2}}{\delta}}$
respectively. Third, by the choice of $\sigma_{h,k}$, we have
$\sigma_{h,k}^{2}\geq\left(\frac{W}{\sqrt{c_{1}d}}+{\mathcal{H}}d^{2.5}H\right)b_{h,k}\geq\frac{W}{\sqrt{c_{1}d}}{\|\widetilde{{\bm{\phi}}}_{h,k}\|}_{\widetilde{{\bm{H}}}_{h,k-1}^{-1}}$,
which implies that $\frac{W^{2}\widetilde{w}_{h,k}^{2}}{\sigma_{h,k}^{2}}\leq
c_{1}d$. Similarly, due to $\sigma_{h,k}^{2}\geq
c_{0}^{-2}\|\widetilde{{\bm{\phi}}}_{h,k}\|^{2}_{\widetilde{{\bm{H}}}_{h-1,k}^{-1}}$,
we have $\widetilde{w}_{h,k}^{2}\leq c_{0}^{2}$. Last, for simplicity, we
define
$\varepsilon_{h,k}=\frac{r_{h,k}^{2}-\langle\widetilde{{\bm{\phi}}}_{h,k},{\bm{\psi}}_{h}^{*}\rangle}{\sigma_{h,k}}$
and
${\mathcal{G}}_{h,k}=\sigma({\mathcal{F}}_{h-1,k}\cup\left\\{s_{h,k},a_{h,k}\right\\})$.
Then, we have $\varepsilon_{h,k}\in{\mathcal{F}}_{h,k}$,
${\mathbb{E}}[\varepsilon_{h,k}|{\mathcal{G}}_{h,k}]=0$ and
$\operatorname{{\rm
Var}}[\varepsilon_{h,k}|{\mathcal{G}}_{h,k}]\leq\left(\frac{\sigma_{R^{2}}}{\sigma_{\min}}\right)^{2}:=b^{2}$.
Theorem 3.1 concerns the case where $b=1$, however, its proof considers the
general case where $b$ can be arbitrary. As a result, by a similar argument in
Appendix B (which is doable due to the four conditions mentioned above), once
setting
$\widetilde{\tau}_{0}\sqrt{\log\frac{2HK^{2}}{\delta}}=\max\left\\{\sqrt{2\kappa}b,2\sqrt{d}\right\\}$,
with probability at least $1-3\delta$, we have for all $h\in[H]$ and
$k\in[K]$,
$\|{\bm{\psi}}_{h,k}-{\bm{\psi}}_{h}^{*}\|_{\widetilde{{\bm{H}}}_{h,k}}\leq\beta_{R^{2}}$,
that is the event ${\mathcal{B}}_{R^{2}}$ holds. ∎

###  E.2 Proof of Lemma C.2

We will make use of the following general result frequently. The proof is
quite standard [Jin et al., 2020b, Wagenmaker et al., 2022a, Hu et al., 2022].
We provide proof in Appendix E.3 for completeness.

######  Lemma E.1.

Fix any $h\in[H]$. Consider a specific value function $f(\cdot)$ which
satisfies

  1. (i)

$\sup_{s\in{\mathcal{S}}}|f(s)|\leq C_{0}$;

  2. (ii)

$f\in{\mathcal{V}}$ where ${\mathcal{V}}$ is a class of functions with
${\mathcal{N}}({\mathcal{V}},\varepsilon)$ the $\varepsilon$-covering number
of ${\mathcal{V}}$ with respective to the distance
$\mathrm{dist}(f,f^{\prime}):=\sup_{s\in{\mathcal{S}}}|f(s)-f^{\prime}(s)|$.

We assume there exists a deterministic $C_{\sigma}>0$ and
${\mathcal{A}}_{h,k}$ (which is ${\mathcal{F}}_{h,k}$-measurable) such that
${\mathcal{A}}_{h,k}\subseteq\left\\{\sigma_{h,k}^{2}\geq({\mathbb{V}}_{h}f)(s_{h,k},a_{h,k})/C_{\sigma}^{2}\right\\}$
for all $k\in[K]$. Let ${\bm{\mu}}_{h,k}$ be defined (4.2) and
$\sigma_{h,k},{\bm{H}}_{h,k}$ be defined in our algorithm. Under any of the
following conditions, with probability at least $1-\delta/H$, it follows for
all $k\in[K]\cup\\{0\\}$,

${\bm{\mu}}_{h}^{*}\in\left\\{{\bm{\mu}}:\left\|({\bm{\mu}}-{\bm{\mu}}_{h,k}){\bm{f}}\right\|_{{\bm{H}}_{h,k}}\leq\beta\right\\}.$
(E.1)

  1. (i)

If $f(\cdot)$ is a deterministic function and
$\cap_{k\in[K]}{\mathcal{A}}_{h,k}$ is true, (E.1) holds with

$\beta=8C_{\sigma}\sqrt{d\log\left(1+\frac{K}{\sigma_{\min}^{2}d\lambda}\right)\log\frac{4HK^{2}}{\delta}}+\frac{8C_{0}}{d^{2.5}H}\log\frac{4HK^{2}}{\delta}+\sqrt{d\lambda}C_{0}.$

  2. (ii)

If $f(\cdot)$ is a random function and $\cap_{k\in[K]}{\mathcal{A}}_{h,k}$ is
true, (E.1) holds with

$\beta=8C_{\sigma}\sqrt{d\log\left(1+\frac{K}{\sigma_{\min}^{2}d\lambda}\right)\log\frac{4HK^{2}N_{0}}{\delta}}+\frac{8C_{0}}{d^{2.5}H{\mathcal{H}}}\log\frac{4HK^{2}N_{0}}{\delta}+3\sqrt{d\lambda}C_{0}$

where $N_{0}=|{\mathcal{N}}({\mathcal{V}},\varepsilon_{0})|$ and
$\varepsilon_{0}=\min\left\\{C_{\sigma}\sigma_{\min},\frac{\lambda
C_{0}\sqrt{d}}{K}\sigma_{\min}^{2}\right\\}$.

  3. (iii)

If $f(\cdot)$ is a random function, (E.1) holds with

$\displaystyle\beta=\frac{2C_{0}}{\sigma_{\min}}\sqrt{d\log\left(1+\frac{K}{\sigma_{\min}^{2}d\lambda}\right)+\log\frac{N_{1}}{\delta}}+3\sqrt{d\lambda}C_{0}.$

where $N_{1}=|{\mathcal{N}}({\mathcal{V}},\varepsilon_{1})|$ and
$\varepsilon_{1}=\frac{\lambda C_{0}\sqrt{d}}{K}\sigma_{\min}^{2}$.

Using the last item suffices to prove Lemma C.2.

###### Proof of Lemma C.2.

Let ${\mathcal{V}}^{+}$ denote the class of optimistic value functions mapping
from ${\mathcal{S}}$ to ${\mathbb{R}}$ with the parametric form given in (F.1)
and ${\mathcal{V}}^{-}$ the class of pessimistic value functions with the
parametric form given in (F.2). By Lemma F.8 and Lemma F.7,

$\displaystyle\log{\mathcal{N}}({\mathcal{V}}^{\pm},\varepsilon)$
$\displaystyle\leq\left[d\log\left(1+\frac{4L}{\varepsilon}\right)+d^{2}\log\left(1+\frac{8d^{1/2}B^{2}}{\lambda\varepsilon^{2}}\right)\right]$
(E.2)

where $B\geq\beta_{0}$ and $L=W+{\mathcal{H}}\sqrt{\frac{dK}{\lambda}}$.

  1. (i)

Let ${\bm{f}}=\overline{{\bm{V}}}_{h+1}^{k}$. One can find that
${\bm{f}}\in{\mathcal{V}}_{f}^{+}$ with parameter
$L=W+\frac{K{\mathcal{H}}}{\lambda\sigma_{\min}^{2}}$. To plug in Lemma E.1,
we first specify the parameters defined therein. We have
$\|{\bm{f}}\|_{\infty}\leq C_{0}={\mathcal{H}}$ and
$\varepsilon_{1}=\frac{\lambda{\mathcal{H}}\sqrt{d}}{K}\sigma_{\min}^{2}$. By
(E.2), it follows that

$\displaystyle\log{\mathcal{N}}({\mathcal{V}}^{+},\varepsilon_{1})$
$\displaystyle\leq\left[d\log\left(1+\frac{4LK}{\lambda{\mathcal{H}}\sqrt{d}\sigma_{\min}^{2}}\right)+d^{2}\log\left(1+\frac{8B^{2}K^{2}}{\sqrt{d}\lambda^{3}{\mathcal{H}}^{2}\sigma_{\min}^{4}}\right)\right]\cdot
dH\log_{2}\left(1+\frac{K}{\lambda\sigma_{\min}^{2}}\right)$
$\displaystyle\leq\frac{2}{\log 2}d^{3}H\iota_{0}^{2}\leq
3d^{3}H\iota_{0}^{2},$

By the third condition of Lemma E.1, with probability at least
$1-\frac{\delta}{2H}$,
$\left\|({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,k-1})\widehat{{\bm{V}}}_{h+1}^{k}\right\|\leq\beta_{0}$
for all $k\in[K]$. Similarly, we can also show that with probability at least
$1-\frac{\delta}{2H}$,
$\left\|({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,k-1})\widecheck{{\bm{V}}}_{h+1}^{k}\right\|\leq\beta_{0}$
for all $k\in[K]$. Putting them together finishes the proof.

  2. (ii)

The analysis on $\underline{{\bm{V}}}_{h+1}^{k}$ is similar to (i).

  3. (iii)

The analysis on $[\overline{{\bm{V}}}_{h+1}^{k}]^{2}$ is similar to (i) except
for the following two changes. First, $C_{0}={\mathcal{H}}^{2}$ and
$\varepsilon_{1}^{\prime}=\frac{\lambda{\mathcal{H}}^{2}\sqrt{d}}{K}\sigma_{\min}^{2}$.
Second, with $[{\mathcal{V}}^{+}]^{2}=\\{f^{2}:f\in{\mathcal{V}}^{+}\\}$, we
have $[\overline{V}_{h+1}^{k}]^{2}\in[{\mathcal{V}}^{+}]^{2}$ and

$\displaystyle\log{\mathcal{N}}([{\mathcal{V}}^{+}]^{2},\varepsilon_{1}^{\prime})$
$\displaystyle\overset{(a)}{\leq}\log{\mathcal{N}}({\mathcal{V}}^{+},\frac{\varepsilon_{1}^{\prime}}{2{\mathcal{H}}})\leq\log{\mathcal{N}}({\mathcal{V}}^{+},\frac{\varepsilon_{1}}{2})\leq
3d^{3}H\iota_{0}^{2}.$

Here $(a)$ uses the fact that the
$\frac{\varepsilon_{1}^{\prime}}{2{\mathcal{H}}}$-cover of ${\mathcal{V}}^{+}$
is a $\varepsilon_{1}$-cover of $[{\mathcal{V}}^{+}]^{2}$ (which is also
supported by Lemma F.9).

∎

###  E.3 Proof of Lemma E.1

###### Proof of Lemma E.1.

Since the case of $k=0$ is trivial, we focus on $k\in[K]$. By definition,

$\displaystyle{\bm{\mu}}_{h,k}$
$\displaystyle={\bm{H}}_{h,k}^{-1}\sum_{j=1}^{k}\sigma_{h,j}^{-2}{\bm{\phi}}_{h,j}{\bm{\delta}}(s_{h+1,j})^{\top}={\bm{H}}_{h,k}^{-1}\sum_{j=1}^{k}\sigma_{h,j}^{-2}{\bm{\phi}}_{h,j}\left({\bm{\phi}}_{h,j}^{\top}{\bm{\mu}}_{h}^{*}-{\bm{\varepsilon}}_{h,j}\right)^{\top}$
$\displaystyle={\bm{\mu}}_{h}^{*}-\lambda{\bm{H}}_{h,k}^{-1}{\bm{\mu}}_{h}^{*}-{\bm{H}}_{h,k}^{-1}\sum_{j=1}^{k}\sigma_{h,j}^{-2}{\bm{\phi}}_{h,j}{\bm{\varepsilon}}_{h,j}^{\top}.$

By the triangle inequality, it follows that

$\displaystyle\left\|({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,k}){\bm{f}}\right\|_{{\bm{H}}_{h,k}}$
$\displaystyle\leq\lambda\|{\bm{H}}_{h,k}^{-1}{\bm{\mu}}_{h}^{*}{\bm{f}}\|_{{\bm{H}}_{h,k}}+\left\|{\bm{H}}_{h,k}^{-1}\sum_{j=1}^{k}\sigma_{h,j}^{-2}{\bm{\phi}}_{h,j}{\bm{\varepsilon}}_{h,j}^{\top}{\bm{f}}\right\|_{{\bm{H}}_{h,k}}$
$\displaystyle=\lambda\|{\bm{\mu}}_{h}^{*}{\bm{f}}\|_{{\bm{H}}_{h,k}^{-1}}+\left\|\sum_{j=1}^{k}\sigma_{h,j}^{-2}{\bm{\phi}}_{h,j}{\bm{\varepsilon}}_{h,j}^{\top}{\bm{f}}\right\|_{{\bm{H}}_{h,k}^{-1}}$
$\displaystyle\leq\sqrt{d\lambda}C_{0}+\left\|\sum_{j=1}^{k}\sigma_{h,j}^{-2}{\bm{\phi}}_{h,j}{\bm{\varepsilon}}_{h,j}^{\top}{\bm{f}}\right\|_{{\bm{H}}_{h,k}^{-1}}$

where the last inequality uses
$\|{\bm{\mu}}_{h}^{*}{\bm{f}}\|\leq\sqrt{d}C_{0}$.

  * •

Assume $f(\cdot)$ is a deterministic function. To evoke Lemma F.3, we set
${\mathcal{G}}_{j}={\mathcal{F}}_{h,j},{\bm{x}}_{j}=\sigma_{h,j}^{-1}{\bm{\phi}}_{h,j},\eta_{j}=\sigma_{h,j}^{-1}{\bm{\varepsilon}}_{h,j}^{\top}{\bm{f}}\cdot
1_{{\mathcal{A}}_{h,j}}$ and
${\bm{Z}}_{k}=\lambda{\bm{I}}+\sum_{j=1}^{k}\sigma_{h,j}^{-2}{\bm{\phi}}_{h,j}{\bm{\phi}}_{h,j}^{\top}={\bm{H}}_{h,k}$.
Here $1_{{\mathcal{A}}}$ is the indicator function of the event
${\mathcal{A}}$.

Clearly
${\bm{x}}_{j}\in{\mathcal{G}}_{j},{\mathbb{E}}[\eta_{j}|{\mathcal{G}}_{j}]=0$
and ${\mathbb{E}}[\eta_{j}^{2}|{\mathcal{G}}_{j}]\leq C_{\sigma}^{2}$. We also
have $\|{\bm{x}}_{j}\|\leq\sigma_{\min}^{-1},|\eta_{j}|\leq
2C_{0}\sigma_{h,j}^{-1}$ and $\|{\bm{x}}_{j}\|_{{\bm{Z}}_{j-1}}=w_{h,j}$. As a
result,
$|\eta_{j}|\min\left\\{1,\|{\bm{x}}_{j}\|_{{\bm{Z}}_{j-1}}\right\\}\leq
2C_{0}\frac{w_{h,j}}{\sigma_{h,j}}\leq\frac{2C_{0}}{{\mathcal{H}}d^{2.5}H}$
where the last inequality uses
$\sigma_{h,j}^{2}\geq{\mathcal{H}}d^{2.5}H\|{\bm{\phi}}_{h,j}\|_{{\bm{H}}_{h,k-1}^{-1}}$
(which is equivalent to
$\frac{w_{h,j}}{\sigma_{h,j}}\leq(d^{2.5}H{\mathcal{H}})^{-1}$). By Lemma
Lemma F.3, it follows that with probability $1-\frac{\delta}{H}$, for all
$k\in[K]$,

$\displaystyle\left\|\sum_{j=1}^{k}\sigma_{h,j}^{-2}{\bm{\phi}}_{h,j}{\bm{\varepsilon}}_{h,j}^{\top}{\bm{f}}1_{{\mathcal{A}}_{h,j}}\right\|_{{\bm{H}}_{h,k}^{-1}}=\left\|\sum_{j=1}^{k}{\bm{x}}_{j}\eta_{j}\right\|_{{\bm{Z}}_{k}^{-1}}$
$\displaystyle\leq
8C_{\sigma}\sqrt{d\log\left(1+\frac{K}{\sigma_{\min}^{2}d\lambda}\right)\log\frac{4HK^{2}}{\delta}}+\frac{8C_{0}}{{\mathcal{H}}d^{2.5}H}\log\frac{4HK^{2}}{\delta}.$

Finally, on the event $\cap_{k\in[K]}{\mathcal{A}}_{h,k}$, we will have all
the indicator functions equal to one.

  * •

If $f(\cdot)$ is a random function, we would use a covering argument to handle
the possible correlation between $f(\cdot)$ and history data, which would
unfortunately enlarge $\beta$.

Denote the $\varepsilon_{0}$-net of ${\mathcal{V}}$ by
${\mathcal{N}}({\mathcal{V}},\varepsilon_{0})$ where
$\varepsilon_{0}=\min\left\\{C_{\sigma}\sigma_{\min},\frac{\lambda
C_{0}\sqrt{d}}{K}\sigma_{\min}^{2}\right\\}$. Hence, for any
$f\in{\mathcal{V}}$, there exists
$\bar{{\bm{f}}}\in{\mathcal{N}}({\mathcal{V}},\varepsilon_{0})$ such that
$\|\bar{{\bm{f}}}-{\bm{f}}\|_{\infty}=\sup_{s\in{\mathcal{S}}}|f(s)-\bar{f}(s)|\leq\varepsilon_{0}$.
Then,

$\displaystyle\left\|\sum_{j=1}^{k}\sigma_{h,j}^{-2}{\bm{\phi}}_{h,j}{\bm{\varepsilon}}_{h,j}^{\top}{\bm{f}}\right\|_{{\bm{H}}_{h,k}^{-1}}$
$\displaystyle\leq\underbrace{\left\|\sum_{j=1}^{k}\sigma_{h,j}^{-2}{\bm{\phi}}_{h,j}{\bm{\varepsilon}}_{h,j}^{\top}\bar{{\bm{f}}}\right\|_{{\bm{H}}_{h,k}^{-1}}}_{(I)}+\underbrace{\left\|\sum_{j=1}^{k}\sigma_{h,j}^{-2}{\bm{\phi}}_{h,j}{\bm{\varepsilon}}_{h,j}^{\top}({\bm{f}}-\bar{{\bm{f}}})\right\|_{{\bm{H}}_{h,k}^{-1}}}_{(II)}.$

For the term $(II)$, due to $\|{\bm{\phi}}_{h,j}\|\leq 1$ and
$|{\bm{\varepsilon}}_{h,j}^{\top}({\bm{f}}-\bar{{\bm{f}}})|\leq\|{\bm{\varepsilon}}_{h,j}\|_{1}\|{\bm{f}}-\bar{{\bm{f}}}\|_{\infty}\leq
2\varepsilon_{0}$, we have

$\left\|\sum_{j=1}^{k}\sigma_{h,j}^{-2}{\bm{\phi}}_{h,j}{\bm{\varepsilon}}_{h,j}^{\top}({\bm{f}}-\bar{{\bm{f}}})\right\|_{{\bm{H}}_{h,k}^{-1}}\leq\frac{2K\varepsilon_{0}}{\sigma_{\min}^{2}\sqrt{\lambda}}\leq
2\sqrt{d\lambda}C_{0}.$

For the term $(I)$, we define
${\mathcal{V}}_{h,k}=\left\\{f^{\prime}\in{\mathcal{V}}:4C_{\sigma}^{2}\sigma_{h,k}^{2}\geq({\mathbb{V}}_{h}f^{\prime})(s_{h,k},a_{h,k})\right\\}$.
Since the definition of ${\mathcal{V}}_{h,k}$ involves only
$\sigma_{h,k},s_{h,k},a_{h,k}\in{\mathcal{F}}_{h,k}$, for any fixed function
$f\in{\mathcal{V}}$, $1_{f\in{\mathcal{V}}_{h,k}}$ is
${\mathcal{F}}_{h,k}$-measurable. On the event ${\mathcal{A}}_{h,k}$, by
definition of $\varepsilon_{0}$,

$({\mathbb{V}}_{h}\bar{f})(s_{h,k},a_{h,k})\leq
2({\mathbb{V}}_{h}f)(s_{h,k},a_{h,k})+2({\mathbb{V}}_{h}(\bar{f}-f))(s_{h,k},a_{h,k})\leq
2C_{\sigma}^{2}\sigma_{h,k}^{2}+2\varepsilon_{0}^{2}\leq
4C_{\sigma}^{2}\sigma_{h,k}^{2}.$

Hence,
${\mathcal{A}}_{h,k}\subseteq\left\\{\sigma_{h,k}^{2}\geq({\mathbb{V}}_{h}f)(s_{h,k},a_{h,k})/C_{\sigma}^{2}\right\\}\subseteq\\{\exists\bar{f}\in{\mathcal{N}}({\mathcal{V}},\varepsilon_{0})\cap{\mathcal{V}}_{h,k}\\}$
for all $k\in[K]$.

In the following, we will evoke Lemma F.3 to analyze the term $(I)$. For any
fixed $f^{\prime}\in{\mathcal{V}}$, we set
${\mathcal{G}}_{j}={\mathcal{F}}_{h,j},{\bm{x}}_{j}=\sigma_{h,j}^{-1}{\bm{\phi}}_{h,j},\eta_{j}=\sigma_{h,j}^{-1}{\bm{\varepsilon}}_{h,j}^{\top}{\bm{f}}^{\prime}\cdot
1_{f^{\prime}\in{\mathcal{V}}_{h,k}}$ and
${\bm{Z}}_{k}=\lambda{\bm{I}}+\sum_{j=1}^{k}\sigma_{h,j}^{-2}{\bm{\phi}}_{h,j}{\bm{\phi}}_{h,j}^{\top}={\bm{H}}_{h,k}$.
Moreover, due to the choice of $\sigma_{h,j}$, it follows that

$\displaystyle\left|\eta_{j}\min\left\\{1,\|{\bm{x}}_{j}\|_{{\bm{Z}}_{j-1}^{-1}}\right\\}\right|\leq\left|\frac{C_{0}}{\sigma_{h,j}}\right|\cdot\left\|\frac{{\bm{\phi}}_{h,j}}{\sigma_{h,j}}\right\|_{{\bm{H}}_{h,j-1}^{-1}}\leq
C_{0}\frac{b_{h,j}}{\sigma_{h,j}^{2}}\leq\frac{C_{0}}{d^{2.5}H{\mathcal{H}}}.$

By Lemma F.3 and the union bound, it follows that with probability
$1-\frac{\delta}{H}$, for all $k\in[K]$,

$\displaystyle\sup_{f^{\prime}\in{\mathcal{N}}({\mathcal{V}},\varepsilon_{0})}\left\|\sum_{j=1}^{k}\sigma_{h,j}^{-2}{\bm{\phi}}_{h,j}{\bm{\varepsilon}}_{h,j}^{\top}{\bm{f}}^{\prime}1_{f^{\prime}\in{\mathcal{V}}_{h,k}}\right\|_{{\bm{H}}_{h,k}^{-1}}$
$\displaystyle\leq
8C_{\sigma}\sqrt{d\log\left(1+\frac{K}{\sigma_{\min}^{2}d\lambda}\right)\log\frac{4HK^{2}N_{0}}{\delta}}+\frac{8C_{0}}{d^{2.5}H{\mathcal{H}}}\log\frac{4HK^{2}N_{0}}{\delta}.$

where $N_{0}=|{\mathcal{N}}({\mathcal{V}},\varepsilon_{0})|$.

As a result, we know that
$\left\|\sum_{j=1}^{k}\sigma_{h,j}^{-2}{\bm{\phi}}_{h,j}{\bm{\varepsilon}}_{h,j}^{\top}\bar{{\bm{f}}}1_{\bar{f}\in{\mathcal{V}}_{h,k}}\right\|_{{\bm{H}}_{h,k}^{-1}}$
is no more than the RHS of the last inequality. On the event
$\cap_{k\in[K]}{\mathcal{A}}_{h,k}$, we have
$\bar{f}\in\cap_{k\in[K]}{\mathcal{V}}_{h,k}$ and thus all the indicator
functions equal to one, completing the proof.

  * •

The proof is almost similar to the second item except that we use Lemma F.4 to
analyze the term $(I)$. Noticing we also have
$|\eta_{j}|=|\sigma_{h,j}^{-1}{\bm{\varepsilon}}_{h,j}^{\top}{\bm{f}}^{\prime}|\leq\frac{2C_{0}}{\sigma_{\min}}$.
By Lemma F.4 and the union bound, it follows that with probability
$1-\frac{\delta}{H}$, for all $k\in[K]$,

$\displaystyle\sup_{f^{\prime}\in{\mathcal{N}}({\mathcal{V}}_{f},\varepsilon_{1})}\left\|\sum_{j=1}^{k}\sigma_{h,j}^{-2}{\bm{\phi}}_{h,j}{\bm{\varepsilon}}_{h,j}^{\top}{\bm{f}}^{\prime}1_{f^{\prime}\in{\mathcal{V}}_{h,k}}\right\|_{{\bm{H}}_{h,k}^{-1}}\leq\frac{2C_{0}}{\sigma_{\min}}\sqrt{d\log\left(1+\frac{K}{\sigma_{\min}^{2}d\lambda}\right)+\log\frac{N_{1}}{\delta}}.$

Pay attention that here we don’t utilize the variance information so that we
change $N_{0}:=|{\mathcal{N}}({\mathcal{V}},\varepsilon_{0})|$ to
$N_{1}:=|{\mathcal{N}}({\mathcal{V}},\varepsilon_{1})|$ and don’t require
$\cap_{k\in[K]}{\mathcal{A}}_{h,k}$ is true.

∎

###  E.4 Proof of Lemma C.3

###### Proof of Lemma C.3.

The proof idea of Lemma C.3 is similar to that of Lemma C.1 except that we pay
more attention on the reward variance.

Given that ${\mathcal{B}}_{R^{2}}$ holds, we have
${\bm{\psi}}_{h}^{*}\in\widetilde{\mathcal{R}}_{h,k}$ for all $h\in[H]$ and
$k\in[K]\cup\\{0\\}$.

We will prove the lemma by induction over $k$. When $k=0$, we have
${\bm{\theta}}_{h,0}=0,{\bm{H}}_{h,0}=\lambda{\bm{I}}$ and
$\|{\bm{\theta}}_{h,0}-{\bm{\theta}}_{h}^{*}\|_{{\bm{H}}_{h,0}}=\sqrt{\lambda}\|{\bm{\theta}}_{h}^{*}\|\leq\sqrt{\lambda}W\leq\beta_{R}$
for all $h\in[H]$. If we suppose ${\bm{\theta}}_{h}^{*}\in{\mathcal{R}}_{h,j}$
holds for all $h\in[H]$ and $j\in[k-1]$, we are going to prove
${\bm{\theta}}_{h}^{*}\in{\mathcal{R}}_{h,k}$ uniformly for $h\in[H]$. The
first thing we will show is

$\sigma_{h,j}^{2}\geq[\widehat{\mathbb{V}}_{h}R_{h}](s_{h,j},a_{h,j})+R_{h,j}\quad\text{for
all}\quad h\in[H]\ \text{and}\ j\in[k].$ (E.3)

Notice that
$[{\mathbb{V}}_{h}R_{h}](s_{h,k},a_{h,k})=\langle\widetilde{{\bm{\phi}}}_{h,k},{\bm{\psi}}_{h}^{*}\rangle-\langle{\bm{\phi}}_{h,k},{{\bm{\theta}}}_{h}^{*}\rangle^{2}$.
We then have for all $h\in[H],j\in[k]$,

$\displaystyle|[\widehat{\mathbb{V}}_{h}R_{h}-{\mathbb{V}}_{h}R_{h}](s_{h,j},a_{h,j})|$
$\displaystyle\leq\left|\langle\widetilde{{\bm{\phi}}}_{h,j},{\bm{\psi}}_{h,j-1}\rangle-\langle\widetilde{{\bm{\phi}}}_{h,j},{\bm{\psi}}_{h}^{*}\rangle\right|+\left|\langle{\bm{\phi}}_{h,j},{{\bm{\theta}}}_{h}^{*}\rangle^{2}-\langle{\bm{\phi}}_{h,j},{{\bm{\theta}}}_{h,j-1}\rangle_{[0,{\mathcal{H}}]}^{2}\right|$
$\displaystyle\leq|\langle\widetilde{{\bm{\phi}}}_{h,k},{\bm{\psi}}_{h,k-1}-{\bm{\psi}}_{h}^{*}\rangle|+2{\mathcal{H}}|\langle{\bm{\phi}}_{h,k},{\bm{\theta}}_{h,j-1}-{\bm{\theta}}_{h}^{*}\rangle|$
$\displaystyle\leq\|\widetilde{{\bm{\phi}}}_{h,j}\|_{\widetilde{{\bm{H}}}_{h,j-1}^{-1}}\|{\bm{\psi}}_{h,j-1}-{\bm{\psi}}_{h}^{*}\|_{\widetilde{{\bm{H}}}_{h,j-1}}+2{\mathcal{H}}\|{\bm{\phi}}_{h,j}\|_{{\bm{H}}_{h,j-1}^{-1}}\|{\bm{\theta}}_{h,j-1}-{\bm{\theta}}_{h}^{*}\|_{{\bm{H}}_{h,j-1}}$
$\displaystyle\leq\beta_{R^{2}}\|\widetilde{{\bm{\phi}}}_{h,j}\|_{\widetilde{{\bm{H}}}_{h,j-1}^{-1}}+2{\mathcal{H}}\beta_{R}\|{\bm{\phi}}_{h,j}\|_{{\bm{H}}_{h,j-1}^{-1}}=R_{h,j}$

where the last inequality uses the hypothesis and the condition that
${\mathcal{B}}_{R^{2}}$ holds. As a result, we establish (E.3).

Let
${\mathcal{G}}_{h,j}=\sigma({\mathcal{F}}_{h-1,j}\cup\left\\{s_{h,j},a_{h,j}\right\\})$.
One can show that both $R_{h,j}$ and $\sigma_{h,j}^{2}$ are
${\mathcal{G}}_{h,j}$-measurable. As a result, the event
${\mathcal{E}}_{h,j}:=\left\\{\sigma_{h,j}^{2}\geq[{\mathbb{V}}_{h}R_{h}](s_{h,j},a_{h,j})\right\\}$
is also ${\mathcal{G}}_{h,j}$-measurable. On the event
${\mathcal{B}}_{R^{2}}$, it is obvious that
$\cap_{h\in[H]}\cap_{j\in[k]}{\mathcal{E}}_{h,j}$ is true since (E.3) is true.

On the other hand, we set
$\varepsilon_{h,j}=\frac{r_{h,j}-\langle{\bm{\phi}}_{h,j},{\bm{\theta}}_{h}^{*}\rangle}{\sigma_{h,j}}1_{{\mathcal{E}}_{h,j}}$
as the standardized reward. We then have
$\varepsilon_{h,j}\in{\mathcal{F}}_{h,j}$,
${\mathbb{E}}[\varepsilon_{h,j}|{\mathcal{G}}_{h,j}]=0$ and
$\operatorname{{\rm Var}}[\varepsilon_{h,j}|{\mathcal{G}}_{h,j}]\leq 1$. We
define $\widehat{{\bm{\theta}}}_{h,k}$ as the solution of adaptive Huber
regression to the response $\\{r_{h,j}1_{{\mathcal{E}}_{h,j}}\\}_{j\in[k]}$
and the feature $\\{{\bm{\phi}}_{h,j}1_{{\mathcal{E}}_{h,j}}\\}_{j\in[k]}$. We
also define $\widehat{{\bm{H}}}_{h,k-1}$ as the counterpart matrix of
${\bm{H}}_{h,k}$ obtained by replacing ${\bm{\phi}}_{h,k}$ with
${\bm{\phi}}_{h,k}1_{{\mathcal{E}}_{h,k}}$. We then apply Theorem 3.1 to
analyze the concentration of $\widehat{{\bm{\theta}}}_{h,k}$. With probability
at least $1-3\delta$, it follows that
$\|\widehat{{\bm{\theta}}}_{h,k}-{\bm{\theta}}_{h}^{*}\|_{\widehat{{\bm{H}}}_{h,k-1}}\leq\beta_{R}$
for all $h\in[H]$ and $k\in[K]$ . Because ${\mathcal{B}}_{R^{2}}$ is true, all
indicator functions equal to one. Therefore, we have
$\widehat{{\bm{\theta}}}_{h,k}={\bm{\theta}}_{h,k}$ and
$\widehat{{\bm{H}}}_{h,k-1}={\bm{H}}_{h,k-1}$, implying
${\bm{\theta}}_{h}^{*}\in{\mathcal{R}}_{h,k}$ uniformly for $h\in[H]$. ∎

###  E.5 Proof of Lemma C.4

###### Proof of Lemma C.4.

By symmetry, we only prove the RHS inequality, or say, the optimism
inequality. We prove it by induction. The statement is true for $h=H+1$ since
both $V_{H+1}^{*}(\cdot)=\overline{V}_{H+1}^{k}(\cdot)=0$ for all $k\in[K]$.
Assume the statement is also true for $h+1$, implying
$V_{h+1}^{*}(\cdot)\leq\overline{V}_{h+1}^{k}(\cdot)$ for all $k\in[K]$. We
assume there exists a sequence of updating episodes $1\leq
k_{1}<\cdots<k_{N_{k}}\leq K$ such that

$\overline{Q}_{h}^{k}(\cdot,\cdot)=\min_{i\in[N_{k}]}\left\\{\langle{\bm{\phi}}(\cdot,\cdot),{\bm{\theta}}_{h,k_{i}-1}+{\bm{\mu}}_{h,k_{i}-1}\overline{{\bm{V}}}_{h+1}^{k_{i}}\rangle+\beta\|{\bm{\phi}}(\cdot,\cdot)\|_{{\bm{H}}_{h,k_{i}-1}^{-1}},{\mathcal{H}}\right\\}.$
(E.4)

Using
$Q_{h}^{*}(s,a)=\langle{\bm{\phi}}(s,a),{\bm{\theta}}_{h}^{*}+{\bm{\mu}}_{h}^{*}{\bm{V}}_{h+1}^{*}\rangle$,
we have for any $(s,a)\in{\mathcal{S}}\times{\mathcal{A}}$ and $k\in[K]$,

$\displaystyle\langle{\bm{\phi}}(\cdot,\cdot),{\bm{\theta}}_{h,k-1}+{\bm{\mu}}_{h,k-1}\overline{{\bm{V}}}_{h+1}^{k}\rangle+\beta\|{\bm{\phi}}(\cdot,\cdot)\|_{{\bm{H}}_{h,k-1}^{-1}}-Q_{h}^{*}(\cdot,\cdot)$
$\displaystyle=\langle{\bm{\phi}}(\cdot,\cdot),{\bm{\theta}}_{h,k-1}-{\bm{\theta}}_{h}^{*}\rangle+\langle{\bm{\phi}}(\cdot,\cdot),{\bm{\mu}}_{h,k-1}\overline{{\bm{V}}}_{h+1}^{k}-{\bm{\mu}}_{h}^{*}{\bm{V}}_{h+1}^{*}\rangle+\beta\|{\bm{\phi}}(\cdot,\cdot)\|_{{\bm{H}}_{h,k-1}^{-1}}$
$\displaystyle\overset{(a)}{\geq}\langle{\bm{\phi}}(\cdot,\cdot),{\bm{\theta}}_{h,k-1}-{\bm{\theta}}_{h}^{*}\rangle+\langle{\bm{\phi}}(\cdot,\cdot),({\bm{\mu}}_{h,k-1}-{\bm{\mu}}_{h}^{*})\overline{{\bm{V}}}_{h+1}^{k}\rangle+\beta\|{\bm{\phi}}(\cdot,\cdot)\|_{{\bm{H}}_{h,k-1}^{-1}}$
$\displaystyle\overset{(b)}{\geq}\|{\bm{\phi}}(\cdot,\cdot)\|_{{\bm{H}}_{h,k-1}^{-1}}\left[-\|{\bm{\theta}}_{h,k-1}-{\bm{\theta}}_{h}^{*}\|_{{\bm{H}}_{h,k-1}}-\|({\bm{\mu}}_{h,k-1}-{\bm{\mu}}_{h}^{*})\overline{{\bm{V}}}_{h+1}^{k}\|_{{\bm{H}}_{h,k-1}}+\beta\right]\overset{(c)}{\geq}0$

where $(a)$ uses
$\langle{\bm{\phi}}(s,a),{\bm{\mu}}_{h}^{*}(\overline{{\bm{V}}}_{h+1}^{k}-{\bm{V}}_{h+1}^{*})\rangle={\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{*})(s,a)\geq
0$ from the hypothesis, $(b)$ follows from Cauchy-Schwarz inequality and $(c)$
uses
$\|{\bm{\theta}}_{h,k-1}-{\bm{\theta}}_{h}^{*}\|_{{\bm{H}}_{h,k-1}}+\|({\bm{\mu}}_{h,k-1}-{\bm{\mu}}_{h}^{*})\overline{{\bm{V}}}_{h+1}^{k}\|_{{\bm{H}}_{h,k-1}}\leq\beta_{R}+\beta_{V}=\beta$
on the event ${\mathcal{B}}_{R}\cap{\mathcal{B}}_{h}$.

As a result, by the last inequality and (E.4), it follows that for all
$k\in[K]$, $\overline{Q}_{h}^{k}(\cdot,\cdot)-Q_{h}^{*}(\cdot,\cdot)\geq 0$.
Taking maximum over actions, we have $\overline{V}_{h}^{k}(\cdot)\geq
V_{h}^{*}(\cdot)$ for all $k\in[K]$, which implies the case of $h$ is also
true. ∎

###  E.6 Proof of Lemma C.5

###### Proof of Lemma C.5.

The proof technique has been used in Lemma C.13 in [Hu et al., 2022] and Lemma
7.2 in [He et al., 2022]. We include the proof for completeness. By
definition,

$\displaystyle[{\mathbb{V}}_{h}V_{h+1}^{*}](s_{h,k},a_{h,k})=\langle{\bm{\mu}}_{h}^{*}[{\bm{V}}_{h+1}^{*}]^{2},{\bm{\phi}}_{h,k}\rangle-\langle{\bm{\mu}}_{h}^{*}{\bm{V}}_{h+1}^{*},{\bm{\phi}}_{h,k}\rangle^{2}$
$\displaystyle[\widehat{\mathbb{V}}_{h}\overline{V}_{h+1}^{k}](s_{h,k},a_{h,k})=\langle{\bm{\mu}}_{h,k-1}[\overline{{\bm{V}}}_{h+1}^{k}]^{2},{\bm{\phi}}_{h,k-1}\rangle_{[0,{\mathcal{H}}^{2}]}-\langle{\bm{\mu}}_{h,k-1}\overline{{\bm{V}}}_{h+1}^{k},{\bm{\phi}}_{h,k}\rangle_{[0,{\mathcal{H}}]}^{2}.$

Therefore, it follows that

$\displaystyle\left|\left[{\mathbb{V}}_{h}V_{h+1}^{*}-\widehat{\mathbb{V}}_{h}\overline{V}_{h+1}^{k}\right](s_{h,k},a_{h,k})\right|$
$\displaystyle\leq\left|\left[{\mathbb{V}}_{h}\overline{V}_{h+1}^{k}-\widehat{\mathbb{V}}_{h}\overline{V}_{h+1}^{k}\right](s_{h,k},a_{h,k})\right|+\left|\left[{\mathbb{V}}_{h}V_{h+1}^{*}-{\mathbb{V}}_{h}\overline{V}_{h+1}^{k}\right](s_{h,k},a_{h,k})\right|.$

We then bound the two terms in the RHS of the last inequality as follows.

$\displaystyle\left|\left[{\mathbb{V}}_{h}\overline{V}_{h+1}^{k}-\widehat{\mathbb{V}}_{h}\overline{V}_{h+1}^{k}\right](s_{h,k},a_{h,k})\right|$
$\displaystyle\leq\left|\langle{\bm{\mu}}_{h}^{*}[\overline{{\bm{V}}}_{h+1}^{k}]^{2},{\bm{\phi}}_{h,k}\rangle-\langle{\bm{\mu}}_{h,k-1}[\overline{{\bm{V}}}_{h+1}^{k}]^{2},{\bm{\phi}}_{h,k}\rangle_{[0,{\mathcal{H}}^{2}]}\right|$
$\displaystyle\qquad+\left|\langle{\bm{\mu}}_{h}^{*}\overline{{\bm{V}}}_{h+1}^{k},{\bm{\phi}}_{h,k}\rangle^{2}-\langle{\bm{\mu}}_{h,k-1}\overline{{\bm{V}}}_{h+1}^{k},{\bm{\phi}}_{h,k}\rangle_{[0,{\mathcal{H}}]}^{2}\right|$
$\displaystyle\leq\left|\langle({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,k-1})[\overline{{\bm{V}}}_{h+1}^{k}]^{2},{\bm{\phi}}_{h,k}\rangle\right|+2{\mathcal{H}}\cdot\left|\langle{\bm{\mu}}_{h}^{*}\overline{{\bm{V}}}_{h+1}^{k},{\bm{\phi}}_{h,k}\rangle-\langle{\bm{\mu}}_{h,k-1}\overline{{\bm{V}}}_{h+1}^{k},{\bm{\phi}}_{h,k}\rangle_{[0,{\mathcal{H}}]}\right|$
$\displaystyle\leq\left\|({\bm{\mu}}_{h,k-1}-{\bm{\mu}}_{h}^{*})[\overline{{\bm{V}}}_{h+1}^{k}]^{2}\right\|_{{\bm{H}}_{h,k-1}}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+2{\mathcal{H}}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}\left\|({\bm{\mu}}_{h,k-1}-{\bm{\mu}}_{h}^{*})\overline{{\bm{V}}}_{h+1}^{k}\right\|_{{\bm{H}}_{h,k-1}}$

where the second inequality uses the fact that both
$\langle{\bm{\mu}}_{h}^{*}\overline{{\bm{V}}}_{h+1}^{k},{\bm{\phi}}_{h,k}\rangle$
and
$\langle{\bm{\mu}}_{h,k-1}\overline{{\bm{V}}}_{h+1}^{k},{\bm{\phi}}_{h,k}\rangle_{[0,{\mathcal{H}}]}$
lie between $0$ and ${\mathcal{H}}$. Similarly, it follows that

$\displaystyle\left|\left[{\mathbb{V}}_{h}V_{h+1}^{*}-{\mathbb{V}}_{h}\overline{V}_{h+1}^{k}\right](s_{h,k},a_{h,k})\right|$
$\displaystyle\leq\left|{\mathbb{P}}_{h}[[V_{h+1}^{*}]^{2}-[\overline{V}_{h+1}^{k}]^{2}](s_{h,k},a_{h,k})\right|+\left|[{\mathbb{P}}_{h}V_{h+1}^{*}]^{2}(s_{h,k},a_{h,k})-[{\mathbb{P}}_{h}\overline{V}_{h+1}^{k}]^{2}(s_{h,k},a_{h,k})\right|$
$\displaystyle\leq\left|{\mathbb{P}}_{h}[(\overline{V}_{h+1}^{k}-V_{h+1}^{*})(\overline{V}_{h+1}^{k}+V_{h+1}^{*})](s_{h,k},a_{h,k})\right|$
$\displaystyle\qquad+\left|[{\mathbb{P}}_{h}\overline{V}_{h+1}^{k}-{\mathbb{P}}_{h}V_{h+1}^{*}][[{\mathbb{P}}_{h}\overline{V}_{h+1}^{k}+{\mathbb{P}}_{h}V_{h+1}^{*}]](s_{h,k},a_{h,k})\right|$
$\displaystyle\leq
4{\mathcal{H}}\cdot{\mathbb{P}}_{h}[\overline{V}_{h+1}^{k}-V_{h+1}^{*}](s_{h,k},a_{h,k})$
$\displaystyle\leq
4{\mathcal{H}}\cdot{\mathbb{P}}_{h}[\overline{V}_{h+1}^{k}-\underline{V}_{h+1}](s_{h,k},a_{h,k})$
$\displaystyle\leq
4{\mathcal{H}}\cdot\widehat{\mathbb{P}}_{h,k}[\overline{V}_{h+1}^{k}-\underline{V}_{h+1}](s_{h,k},a_{h,k})$
$\displaystyle\quad+4{\mathcal{H}}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}\cdot\left[\left\|({\bm{\mu}}_{h,k-1}-{\bm{\mu}}_{h}^{*})\overline{{\bm{V}}}_{h+1}^{k}\right\|_{{\bm{H}}_{h,k-1}}+\left\|({\bm{\mu}}_{h,k-1}-{\bm{\mu}}_{h}^{*})\underline{{\bm{V}}}_{h+1}^{k}\right\|_{{\bm{H}}_{h,k-1}}\right]$

where the third and forth inequality we use the optimism and pessimism in
Lemma C.4 and the last inequality uses the following result.

$\displaystyle\left|[{\mathbb{P}}_{h}\overline{V}_{h+1}^{k}-\widehat{\mathbb{P}}_{h,k}\overline{V}_{h+1}^{k}](s_{h,k},a_{h,k})\right|$
$\displaystyle=\left|\langle({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,k-1})\overline{{\bm{V}}}_{h+1}^{k},{\bm{\phi}}_{h,k}\rangle\right|$
$\displaystyle\leq\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}\left\|({\bm{\mu}}_{h,k-1}-{\bm{\mu}}_{h}^{*})\overline{{\bm{V}}}_{h+1}^{k}\right\|_{{\bm{H}}_{h,k-1}}.$

A similar inequality can be derived for
$\left|[{\mathbb{P}}_{h}\underline{V}_{h+1}^{k}-\widehat{\mathbb{P}}_{h,k}\underline{V}_{h+1}^{k}](s_{h,k},a_{h,k})\right|$.
Finally, we have

$\displaystyle\left|\left[{\mathbb{V}}_{h}V_{h+1}^{*}-\widehat{\mathbb{V}}_{h}\overline{V}_{h+1}^{k}\right](s_{h,k},a_{h,k})\right|$
$\displaystyle\leq\left\|({\bm{\mu}}_{h,k-1}-{\bm{\mu}}_{h}^{*})[\overline{{\bm{V}}}_{h+1}^{*}]^{2}\right\|_{{\bm{H}}_{h,k-1}}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+4{\mathcal{H}}\widehat{\mathbb{P}}_{h,k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h,k},a_{h,k})$
$\displaystyle\qquad+{\mathcal{H}}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}\cdot\left[6\left\|({\bm{\mu}}_{h,k-1}-{\bm{\mu}}_{h}^{*})\overline{{\bm{V}}}_{h+1}^{k}\right\|_{{\bm{H}}_{h,k-1}}+4\left\|({\bm{\mu}}_{h,k-1}-{\bm{\mu}}_{h}^{*})\underline{{\bm{V}}}_{h+1}^{k}\right\|_{{\bm{H}}_{h,k-1}}\right].$

We complete the proof by noting that on the event ${\mathcal{B}}_{0}$, we have

$\displaystyle\max\left\\{\left\|({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,k-1})\overline{{\bm{V}}}_{h+1}^{k}\right\|_{{\bm{H}}_{h,k-1}},\left\|({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,k-1})\underline{{\bm{V}}}_{h+1}^{k}\right\|_{{\bm{H}}_{h,k-1}}\right\\}\leq\beta_{0},$
$\displaystyle\left\|({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,k-1})[\overline{{\bm{V}}}_{h+1}^{k}]^{2}\right\|_{{\bm{H}}_{h,k-1}}\leq{\mathcal{H}}\beta_{0}.$

∎

###  E.7 Proof of Lemma C.6

###### Proof of Lemma C.6.

For any $j\leq k$, we have

$\displaystyle\left[{\mathbb{V}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{*})\right](s_{h,j},a_{h,j})$
$\displaystyle\overset{(a)}{\leq}\left[{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{*})^{2}\right](s_{h,j},a_{h,j})$
$\displaystyle\overset{(b)}{\leq}{\mathcal{H}}\left[{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})\right](s_{h,j},a_{h,j})$
$\displaystyle\overset{(c)}{\leq}{\mathcal{H}}\left[{\mathbb{P}}_{h}(\overline{V}_{h+1}^{j}-\underline{V}_{h+1}^{j})\right](s_{h,j},a_{h,j})$

where $(a)$ uses the fact that $\operatorname{{\rm
Var}}(X)\leq{\mathbb{E}}X^{2}$ for any random variable $X$, $(b)$ uses
$0\leq\underline{V}_{h+1}^{k}(\cdot)\leq
V_{h+1}^{*}(\cdot)\leq\overline{V}_{h+1}^{k}(\cdot)\leq{\mathcal{H}}$ on the
event ${\mathcal{B}}_{R}\cap{\mathcal{B}}_{h+1}$ from Lemma C.4, and $(c)$
uses that $\overline{V}_{h+1}^{j}(\cdot)\geq\overline{V}_{h+1}^{k}(\cdot)$ and
$\underline{V}_{h+1}^{j}(\cdot)\leq\underline{V}_{h+1}^{k}(\cdot)$ by
definition. On the other hand, on the event ${\mathcal{B}}_{0}$, we have

$\displaystyle\max\left\\{\left\|({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,j-1})\overline{{\bm{V}}}_{h+1}^{j}\right\|_{{\bm{H}}_{h,j-1}},\left\|({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,j-1})\underline{{\bm{V}}}_{h+1}^{j}\right\|_{{\bm{H}}_{h,j-1}}\right\\}\leq\beta_{0}.$

As a result,

$\displaystyle\left[\left({\mathbb{P}}_{h}-\widehat{\mathbb{P}}_{h,j}\right)\overline{V}_{h+1}^{j}\right](s_{h,j},a_{h,j})$
$\displaystyle=\langle{\bm{\phi}}_{h,j},({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,j-1})\overline{{\bm{V}}}_{h+1}^{j}\rangle$
$\displaystyle\leq\|{\bm{\phi}}_{h,j}\|_{{\bm{H}}_{h,j-1}^{-1}}\|({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,j-1})\overline{{\bm{V}}}_{h+1}^{j}\|_{{\bm{H}}_{h,j-1}}\leq\beta_{0}\|{\bm{\phi}}_{h,j}\|_{{\bm{H}}_{h,j-1}^{-1}}.$

Similarily, we have
$\left[\left({\mathbb{P}}_{h}-\widehat{\mathbb{P}}_{h,j}\right)\underline{V}_{h+1}^{j}\right](s_{h,j},a_{h,j})\leq\beta_{0}\|{\bm{\phi}}_{h,j}\|_{{\bm{H}}_{h,j-1}^{-1}}$.
Therefore,

$\displaystyle\left[{\mathbb{V}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{*})\right](s_{h,j},a_{h,j})$
$\displaystyle\leq{\mathcal{H}}\left[2\beta_{0}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,j-1}^{-1}}+\left[\widehat{\mathbb{P}}_{h,j}(\overline{V}_{h+1}^{j}-\underline{V}_{h+1}^{j})\right](s_{h,j},a_{h,j})\right]=:E_{h,j}$

Repeating the above argument, we have a similar inequality for
$\overline{V}_{h+1}^{k}$ due to symmetry. ∎

###  E.8 Proof of Lemma C.7

###### Proof of Lemma C.7.

Due to the backward recursion structure, we will use induction (over horizon
$h$) to prove this lemma. First, (C.2) is true for $h=H$ since
$\overline{V}_{H+1}^{k}(\cdot)=\underline{V}_{H+1}^{k}(\cdot)=0$ for all
$k\in[K]$. Therefore, we have ${\mathcal{B}}_{H}$ holds. Assume (C.2) holds
for horizons no smaller than $h+1$, i.e., ${\mathcal{B}}_{h+1}$ holds with
$h+1\leq H$. In the following, we will show, once
${\mathcal{B}}_{h+1}\cap{\mathcal{B}}_{0}$ holds, ${\mathcal{B}}_{h}$ holds
with probability at least than $1-\frac{2\delta}{H}$. Repeating the argument,
we have, given ${\mathcal{B}}_{H}\cap{\mathcal{B}}_{0}$ holds, with
probability at least $1-2\delta$, ${\mathcal{B}}_{1}\cap{\mathcal{B}}_{0}$
holds. Hence, ${\mathbb{P}}({\mathcal{B}}_{0}\cap{\mathcal{B}}_{1})\geq
1-5\delta$.

Note that

$\displaystyle\max$
$\displaystyle\left\\{\left\|({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,k-1})\overline{{\bm{V}}}_{h+1}^{k}\right\|_{{\bm{H}}_{h,k-1}},\left\|({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,k-1})\underline{{\bm{V}}}_{h+1}^{k}\right\|_{{\bm{H}}_{h,k-1}}\right\\}\leq\left\|({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,k-1}){\bm{V}}_{h+1}^{*}\right\|_{{\bm{H}}_{h,k-1}}$
$\displaystyle+\max\left\\{\left\|({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,k-1})(\overline{{\bm{V}}}_{h+1}^{k}-{\bm{V}}_{h+1}^{*})\right\|_{{\bm{H}}_{h,k-1}},\left\|({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,k-1})(\underline{{\bm{V}}}_{h+1}^{k}-{\bm{V}}_{h+1}^{*})\right\|_{{\bm{H}}_{h,k-1}}\right\\}.$

we would analyze the two terms in the RHS separately to proceed with the
proof.

##### For the first term

Since ${\bm{V}}_{h+1}^{*}$ is a deterministic function, we apply the first
item in Lemma E.1 to bound it. In the following, we specify the parameters
defined therein. First, we have $C_{0}={\mathcal{H}}$ and
${\mathcal{A}}_{h,k}=\left\\{\sigma_{h,k}^{2}\geq({\mathbb{V}}_{h}V_{h+1}^{*})(s_{h,k},a_{h,k})\right\\}$
is ${\mathcal{F}}_{h,k}$-measurable. By Lemma C.5, on the event
${\mathcal{B}}_{0}\cap{\mathcal{B}}_{h+1}$, we have for all $k\in[K]$,
$\left|\left[{\mathbb{V}}_{h}V_{h+1}^{*}-\widehat{\mathbb{V}}_{h}\overline{V}_{h+1}^{k}\right](s_{h,k},a_{h,k})\right|\leq
U_{h,k}$ with $U_{h,k}$ defined in (4.9). Hence,
$\sigma_{h,k}^{2}\geq[\widehat{\mathbb{V}}_{h}\widehat{V}_{h+1}^{k}](s_{h,k},a_{h,k})+U_{h,k}\geq[{\mathbb{V}}_{h}V_{h+1}^{*}](s_{h,k},a_{h,k})$
for all $k\in[K]$, implying $\cap_{k\in[K]}{\mathcal{A}}_{h,k}$ holds under
${\mathcal{B}}_{0}\cap{\mathcal{B}}_{h+1}$ and $C_{\sigma}=1$. By Lemma E.1,
with probability at least $1-\frac{\delta}{H}$,
$\left\|({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,k-1}){\bm{V}}_{h+1}^{*}\right\|_{{\bm{H}}_{h,k-1}}\leq\beta_{1}$
for all $k\in[K]$ with $\beta_{1}$ defined in the following. Finally, we
simplify $\beta_{1}$ as

$\displaystyle\beta_{1}$
$\displaystyle:=8\sqrt{d\log\left(1+\frac{K}{\sigma_{\min}^{2}d\lambda}\right)\log\frac{4HK^{2}}{\delta}}+\frac{8}{d^{2.5}H}\log\frac{4HK^{2}}{\delta}+\sqrt{d\lambda}{\mathcal{H}}$
$\displaystyle\leq
8\sqrt{d}\iota_{1}+\frac{8\iota_{1}}{d^{2.5}H}+\sqrt{d\lambda}{\mathcal{H}}\leq
16\sqrt{d}\iota_{1}+\sqrt{d\lambda}{\mathcal{H}}.$

##### For the second term

Since both $\overline{{\bm{V}}}_{h+1}^{k}-{\bm{V}}_{h+1}^{*}$ and
$\underline{{\bm{V}}}_{h+1}^{k}-{\bm{V}}_{h+1}^{*}$ are
${\mathcal{F}}_{H,k-1}$-measurable random functions, we apply the second item
in Lemma E.1 to analyze the second term. In the following, we specify
parameters defined therein. First, $C_{0}={\mathcal{H}}$ and
${\mathcal{A}}_{h,k}=\left\\{\sigma_{h,k}^{2}\geq d^{3}H\cdot
E_{h,k}\right\\}$ is ${\mathcal{F}}_{h,k}$-measurable. By Lemma C.6, on the
event ${\mathcal{B}}_{0}\cap{\mathcal{B}}_{R}\cap{\mathcal{B}}_{h+1}$, we have
simultaneously
$\left[{\mathbb{V}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{*})\right](s_{h,j},a_{h,j})\leq
E_{h,j}$ and
$\left[{\mathbb{V}}_{h}(\underline{V}_{h+1}^{k}-V_{h+1}^{*})\right](s_{h,j},a_{h,j})\leq
E_{h,j}$ for all $j\leq k\leq K$ with $E_{h,j}$ defined in (4.7). As a result,
for all $j\leq k$,

$\displaystyle\sigma_{h,j}^{2}$ $\displaystyle\geq d^{3}H\cdot E_{h,j}\geq
d^{3}H\cdot\max\left\\{\left[{\mathbb{V}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{*})\right](s_{h,j},a_{h,j}),\left[{\mathbb{V}}_{h}(\underline{V}_{h+1}^{k}-V_{h+1}^{*})\right](s_{h,j},a_{h,j})\right\\}.$

It implies $C_{\sigma}=\frac{1}{\sqrt{d^{3}H}}$ and for any $j\in[k]$,

${\mathcal{A}}_{h,j}\subseteq\left\\{\sigma_{h,j}^{2}\geq
C_{\sigma}^{-2}\max\left\\{\left[{\mathbb{V}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{*})\right](s_{h,j},a_{h,j}),\left[{\mathbb{V}}_{h}(\underline{V}_{h+1}^{k}-V_{h+1}^{*})\right](s_{h,j},a_{h,j})\right\\}\right\\}.$

Finally, with by Lemma F.8 and F.7, the covering entropy for
$\varepsilon_{0}=\min\left\\{\frac{\sigma_{\min}}{\sqrt{d^{3}H}},\frac{\lambda{\mathcal{H}}\sqrt{d}}{K}\sigma_{\min}^{2}\right\\}$
and the function class to which $\overline{V}_{h+1}^{k}-V_{h+1}^{*}$ and
$\underline{V}_{h+1}^{k}-V_{h+1}^{*}$ belong is

$\displaystyle\log N_{0}$
$\displaystyle=|{\mathcal{N}}({\mathcal{V}}^{\pm},\varepsilon_{0})|\leq\left[d\log\left(1+\frac{4L}{\varepsilon_{0}}\right)+d^{2}\log\left(1+\frac{8\sqrt{d}B^{2}}{\lambda\varepsilon_{0}^{2}}\right)\right]\cdot
dH\log_{2}\left(1+\frac{K}{\lambda\sigma_{\min}^{2}}\right)$
$\displaystyle={\mathcal{O}}(d^{3}H\iota_{1}^{2})$

By Lemma E.1, with probability at least $1-\frac{\delta}{H}$,

$\max\left\\{\left\|({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,k-1})(\overline{{\bm{V}}}_{h+1}^{k}-{\bm{V}}_{h+1}^{*})\right\|_{{\bm{H}}_{h,k-1}},\left\|({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,k-1})(\underline{{\bm{V}}}_{h+1}^{k}-{\bm{V}}_{h+1}^{*})\right\|_{{\bm{H}}_{h,k-1}}\right\\}\leq\beta_{2}$

for all $k\in[K]$ with $\beta_{2}$ defined in the following. Finally, we
simplify $\beta_{2}$ as

$\displaystyle\beta_{2}$
$\displaystyle=\frac{8}{\sqrt{d^{3}H}}\sqrt{d\log\left(1+\frac{K}{\sigma_{\min}^{2}d\lambda}\right)\log\frac{4N_{0}HK^{2}}{\delta}}+\frac{8}{d^{2.5}H}\log\frac{4N_{0}HK^{2}}{\delta}+\sqrt{d\lambda}{\mathcal{H}}$
$\displaystyle\leq
8\sqrt{\frac{\iota_{1}}{d^{2}H}\cdot\left(\iota_{1}+{\mathcal{O}}(d^{3}H\iota_{1}^{2})\right)}+\frac{8}{d^{2.5}H}\left(\iota_{1}+{\mathcal{O}}(d^{3}H\iota_{1}^{2})\right)+\sqrt{d\lambda}{\mathcal{H}}$
$\displaystyle={\mathcal{O}}\left(\sqrt{d}\iota_{1}^{1.5}+\iota_{1}+\sqrt{d}\iota_{1}^{2}+\sqrt{d\lambda}{\mathcal{H}}\right)={\mathcal{O}}\left(\sqrt{d}\iota_{1}^{2}+\sqrt{d\lambda}{\mathcal{H}}\right).$

##### Putting pieces together

we have shown that given ${\mathcal{B}}_{h+1}\cap{\mathcal{B}}_{0}$ is true,
with probability at least $1-2\delta$, for all $h\in[H]$ and $k\in[K]$,

$\max\left\\{\left\|({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,k-1})\overline{{\bm{V}}}_{h+1}^{k}\right\|_{{\bm{H}}_{h,k-1}},\left\|({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,k-1})\underline{{\bm{V}}}_{h+1}^{k}\right\|_{{\bm{H}}_{h,k-1}}\right\\}\leq\beta_{1}+\beta_{2}={\mathcal{O}}\left(\sqrt{d}\iota_{1}^{2}+\sqrt{d\lambda}{\mathcal{H}}\right).$

Therefore, ${\mathcal{B}}_{V}:={\mathcal{B}}_{1}$ holds. ∎

###  E.9 Proof of Lemma C.8

###### Proof of Lemma C.8.

For a given $k$, let $k_{\mathrm{last}}$ denote the latest update episode
before episode $k$, that is $k_{\mathrm{last}}\leq k<k_{\mathrm{last}}+1$. By
Lemma F.6, due to ${\bm{H}}_{h,k-1}\succeq{\bm{H}}_{h,k_{\mathrm{last}}-1}$
and $\det({\bm{H}}_{h,k-1})\leq 2\det({\bm{H}}_{h,k_{\mathrm{last}}-1})$, it
follows that for any ${\bm{x}}\in{\mathbb{R}}^{d}$,

$\|{\bm{x}}\|_{{\bm{H}}_{h,k_{\mathrm{last}}-1}^{-1}}\leq
2\|{\bm{x}}\|_{{\bm{H}}_{h,k-1}^{-1}}.$ (E.5)

By definition,
$\overline{Q}_{h}^{k}(\cdot,\cdot)\leq\langle{\bm{\phi}}(\cdot,\cdot),{\bm{\theta}}_{h,k_{\mathrm{last}}-1}+{\bm{\mu}}_{h,k_{\mathrm{last}}-1}\overline{{\bm{V}}}_{h+1}^{k_{\mathrm{last}}}\rangle+\beta\|{\bm{\phi}}(\cdot,\cdot)\|_{{\bm{H}}_{h,k_{\mathrm{last}}-1}^{-1}}$
and
$Q_{h}^{\pi_{k}}(s,a)=\langle{\bm{\phi}}(s,a),{\bm{\theta}}_{h}^{*}+{\bm{\mu}}_{h}^{*}{\bm{V}}_{h+1}^{\pi_{k}}\rangle$.
Using $a_{h,k}=\pi_{h}^{k}(s_{h,k})=\mathop{\rm
argmax}_{a\in{\mathcal{A}}}\overline{Q}_{h}^{k}(s_{h,k},a)$, we then have

$\displaystyle($
$\displaystyle\overline{V}_{h}^{k}-V_{h}^{\pi_{k}})(s_{h,k})\leq(\overline{Q}_{h}^{k}-Q_{h}^{\pi_{k}})(s_{h,k},a_{h,k})$
$\displaystyle\leq\langle{\bm{\phi}}_{h,k},{\bm{\theta}}_{h,k_{\mathrm{last}}-1}+{\bm{\mu}}_{h,k_{\mathrm{last}}-1}\overline{{\bm{V}}}_{h+1}^{k_{\mathrm{last}}}-({\bm{\theta}}_{h}^{*}+{\bm{\mu}}_{h}^{*}{\bm{V}}_{h+1}^{\pi_{k}})\rangle+\beta\|{\bm{\phi}}(s_{h,k},a_{h,k})\|_{{\bm{H}}_{h,k_{\mathrm{last}}-1}^{-1}}$
$\displaystyle\overset{(a)}{\leq}\langle{\bm{\phi}}_{h,k},({\bm{\theta}}_{h,k_{\mathrm{last}}-1}-{\bm{\theta}}_{h}^{*})+({\bm{\mu}}_{h,k_{\mathrm{last}}-1}-{\bm{\mu}}_{h}^{*})\overline{{\bm{V}}}_{h+1}^{k_{\mathrm{last}}}\rangle+\langle{\bm{\phi}}_{h,k},{\bm{\mu}}_{h}^{*}(\overline{{\bm{V}}}_{h+1}^{k_{\mathrm{last}}}-{\bm{V}}_{h+1}^{\pi_{k}})\rangle+2\beta\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}$
$\displaystyle\overset{(b)}{\leq}4\beta\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+\langle{\bm{\phi}}_{h,k},{\bm{\mu}}_{h}^{*}(\overline{{\bm{V}}}_{h+1}^{k}-{\bm{V}}_{h+1}^{\pi_{k}})\rangle$
$\displaystyle\overset{(c)}{=}4\beta\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})(s_{h,k},a_{h,k})$
$\displaystyle\overset{(d)}{=}4\beta\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+(\overline{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})(s_{h+1,k})+X_{h,k}.$

Here $(a)$ uses (E.5), $(b)$ uses

$\displaystyle|\langle{\bm{\phi}}_{h,k},({\bm{\theta}}_{h,k_{\mathrm{last}}-1}-{\bm{\theta}}_{h}^{*})+({\bm{\mu}}_{h,k_{\mathrm{last}}-1}-{\bm{\mu}}_{h}^{*})\overline{{\bm{V}}}_{h+1}^{k_{\mathrm{last}}}\rangle|$
$\displaystyle\leq\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k_{\mathrm{last}}-1}^{-1}}\|({\bm{\theta}}_{h,k_{\mathrm{last}}-1}-{\bm{\theta}}_{h}^{*})+({\bm{\mu}}_{h,k_{\mathrm{last}}-1}-{\bm{\mu}}_{h}^{*})\overline{{\bm{V}}}_{h+1}^{k_{\mathrm{last}}}\|_{{\bm{H}}_{h,k_{\mathrm{last}}-1}}$
$\displaystyle\leq\beta\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k_{\mathrm{last}}-1}^{-1}}\leq
2\beta\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}$

on ${\mathcal{B}}_{R}\cap{\mathcal{B}}_{V}$, $(c)$ uses
$\langle{\bm{\phi}}_{h,k},{\bm{\mu}}_{h}^{*}(\overline{V}_{h+1}^{k_{\mathrm{last}}}-V_{h+1}^{\pi_{k}})\rangle={\mathbb{P}}_{h}(\overline{{\bm{V}}}_{h+1}^{k_{\mathrm{last}}}-{\bm{V}}_{h+1}^{\pi_{k}})(s_{h,k},a_{h,k})={\mathbb{P}}_{h}(\overline{{\bm{V}}}_{h+1}^{k}-{\bm{V}}_{h+1}^{\pi_{k}})(s_{h,k},a_{h,k})$,
and $(d)$ uses the notation

$X_{h,k}:={\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})(s_{h,k},a_{h,k})-(\overline{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})(s_{h+1,k}).$

The last inequality implies

$\displaystyle(\overline{V}_{h}^{k}-V_{h}^{\pi_{k}})(s_{h,k})\leq(\overline{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})(s_{h+1,k})+X_{h,k}+4\beta\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}.$

Iterating the above inequality over $h$ and using
$\overline{V}_{H+1}^{k}(\cdot)=V_{H+1}^{\pi_{k}}(\cdot)=0$, we have

$(\overline{V}_{h}^{k}-V_{h}^{\pi_{k}})(s_{h,k})\leq\sum_{i=h}^{H}\left[X_{i,k}+4\beta\|{\bm{\phi}}_{i,k}\|_{{\bm{H}}_{i,k-1}^{-1}}\right].$
(E.6)

Therefore, setting $h=1$ and summing (E.6) over $k\in[K]$, we have

$\sum_{k=1}^{K}(\overline{V}_{1}^{k}-V_{1}^{\pi_{k}})(s_{1,k})\leq\sum_{k=1}^{K}\sum_{h=1}^{H}\left[X_{h,k}+4\beta\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}\right].$
(E.7)

We then need to analyze $\sum_{k=1}^{K}\sum_{h=1}^{H}X_{h,k}$. Since
$s_{h+1,k}$ is ${\mathcal{F}}_{h+1,k}$-measurable,
$\pi_{k}=\\{\pi_{h}^{k}\\}_{h\in[H]},\overline{V}_{h+1}^{k}$ is
${\mathcal{F}}_{H,k-1}$-measurable, we have $X_{h,k}$ is
${\mathcal{F}}_{h+1,k}$-measurable. We also have
${\mathbb{E}}[X_{h,k}|{\mathcal{F}}_{h,k}]=0$, $|X_{h,k}|\leq 2{\mathcal{H}}$
and

$\displaystyle{\mathbb{E}}[X_{h,k}^{2}|{\mathcal{F}}_{h,k}]$
$\displaystyle\leq{\mathbb{E}}[(\overline{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})^{2}(s_{h+1,k})|{\mathcal{F}}_{h,k}]\overset{(a)}{\leq}{\mathcal{H}}{\mathbb{E}}[|\overline{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}}|(s_{h+1,k})|{\mathcal{F}}_{h,k}]$
$\displaystyle\overset{(b)}{=}{\mathcal{H}}{\mathbb{E}}[(\overline{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})(s_{h+1,k})|{\mathcal{F}}_{h,k}]={\mathcal{H}}{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})(s_{h,k},a_{h,k})$

where $(a)$ uses
$|\overline{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}}|(\cdot)\leq{\mathcal{H}}$ and $(b)$
uses the optimism in Lemma C.4. By the variance-aware Freedman inequality in
Lemma F.2, with probability at least $1-\frac{\delta}{2}$, it follows that

$\left|\sum_{k=1}^{K}\sum_{h=1}^{H}X_{h,k}\right|\leq
3\sqrt{\iota}\cdot\sqrt{{\mathcal{H}}\cdot\sum_{k=1}^{K}\sum_{h=1}^{H}{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})(s_{h,k},a_{h,k})}+10{\mathcal{H}}\cdot\iota$
(E.8)

where $\iota=\log\frac{4\lceil\log_{2}HK\rceil}{\delta}$. On the other hand,
it follows that

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}$
$\displaystyle{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})(s_{h,k},a_{h,k})=\sum_{k=1}^{K}\sum_{h=2}^{H}(\overline{V}_{h}^{k}-V_{h}^{\pi_{k}})(s_{h,k})+\sum_{k=1}^{K}\sum_{h=1}^{H}X_{h,k}$
$\displaystyle\overset{(a)}{\leq}\sum_{k=1}^{K}\sum_{h=2}^{H}\sum_{i=h}^{H}\left[X_{i,k}+4\beta\|{\bm{\phi}}_{i,k}\|_{{\bm{H}}_{i,k-1}^{-1}}\right]+\sum_{k=1}^{K}\sum_{h=1}^{H}X_{h,k}$
$\displaystyle=\sum_{k=1}^{K}\sum_{h=2}^{H}(H-h+1)\left[X_{h,k}+4\beta\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}\right]+\sum_{k=1}^{K}\sum_{h=1}^{H}X_{h,k}$
$\displaystyle\overset{(b)}{\leq}4H\beta\sum_{k=1}^{K}\sum_{h=2}^{H}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+\sum_{k=1}^{K}\sum_{h=1}^{H}X_{h,k}b_{h}$

where $(a)$ uses (E.6) and $(b)$ uses the notation $b_{h}=1$ if $h=1$;
otherwise $=H-h+2$ for $2\leq h\leq H$. Clearly, we have $|b_{h}|\leq H$ for
all $h\in[H]$. By the variance-aware Freedman inequality in Lemma F.2, with
probability at least $1-\frac{\delta}{2}$, it follows that

$\left|\sum_{k=1}^{K}\sum_{h=1}^{H}X_{h,k}b_{h}\right|\leq
3H\sqrt{\iota}\cdot\sqrt{{\mathcal{H}}\cdot\sum_{k=1}^{K}\sum_{h=1}^{H}{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})(s_{h,k},a_{h,k})}+10H{\mathcal{H}}\cdot\iota.$

As a result, we have

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})(s_{h,k},a_{h,k})$
$\displaystyle\leq
3H\sqrt{\iota}\cdot\sqrt{{\mathcal{H}}\cdot\sum_{k=1}^{K}\sum_{h=1}^{H}{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})(s_{h,k},a_{h,k})}$
$\displaystyle\qquad+4H\beta\sum_{k=1}^{K}\sum_{h=2}^{H}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+10H{\mathcal{H}}\iota.$

Using the inequality that $x\leq 2(a^{2}+b^{2})$ for any
$x\leq|a|\sqrt{x}+b^{2}$, we have

$\sum_{k=1}^{K}\sum_{h=1}^{H}{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})(s_{h,k},a_{h,k})\leq
8H\beta\sum_{k=1}^{K}\sum_{h=1}^{H}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+38H^{2}{\mathcal{H}}\iota.$
(E.9)

Putting pieces together, we have

$\displaystyle\sum_{k=1}^{K}$
$\displaystyle(\overline{V}_{1}^{k}-V_{1}^{\pi_{k}})(s_{1,k})\overset{\eqref{eq:final0}}{\leq}\sum_{k=1}^{K}\sum_{h=1}^{H}\left[X_{h,k}+4\beta\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}\right]$
$\displaystyle\overset{\eqref{eq:final1}}{\leq}4\beta\sum_{k=1}^{K}\sum_{h=1}^{H}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+3\sqrt{\iota}\cdot\sqrt{{\mathcal{H}}\cdot\sum_{k=1}^{K}\sum_{h=1}^{H}{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})(s_{h,k},a_{h,k})}+10{\mathcal{H}}\cdot\iota$
$\displaystyle\overset{\eqref{eq:final-expect-
sum}}{\leq}4\beta\sum_{k=1}^{K}\sum_{h=1}^{H}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+3\sqrt{\iota}\cdot\sqrt{{\mathcal{H}}\cdot\left[8H\beta\sum_{k=1}^{K}\sum_{h=1}^{H}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+38H^{2}{\mathcal{H}}\iota\right]}+10{\mathcal{H}}\cdot\iota$
$\displaystyle\leq
6\beta\sum_{k=1}^{K}\sum_{h=1}^{H}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+38H{\mathcal{H}}\iota$

where the last inequality uses $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ and
$2\sqrt{ab}\leq a+b$ for non-negative numbers $a,b\geq 0$. ∎

###  E.10 Proof of Lemma C.9

###### Proof of Lemma C.9.

The proof main idea is similar to that in Lemma C.8. For a given $k$, let
$k_{\mathrm{last}}$ denote the latest update episode before episode $k$, that
is $k_{\mathrm{last}}\leq k<k_{\mathrm{last}}+1$. By definition,
$\overline{Q}_{h}^{k}(\cdot,\cdot)\leq\langle{\bm{\phi}}(\cdot,\cdot),{\bm{\theta}}_{h,k_{\mathrm{last}}-1}+{\bm{\mu}}_{h,k_{\mathrm{last}}-1}\overline{{\bm{V}}}_{h+1}^{k_{\mathrm{last}}}\rangle+\beta\|{\bm{\phi}}(\cdot,\cdot)\|_{{\bm{H}}_{h,k_{\mathrm{last}}-1}^{-1}}$
and
$\underline{Q}_{h}^{k}(\cdot,\cdot)\geq\langle{\bm{\phi}}(\cdot,\cdot),{\bm{\theta}}_{h,k_{\mathrm{last}}-1}+{\bm{\mu}}_{h,k_{\mathrm{last}}-1}\underline{{\bm{V}}}_{h+1}^{k_{\mathrm{last}}}\rangle-\beta\|{\bm{\phi}}(\cdot,\cdot)\|_{{\bm{H}}_{h,k_{\mathrm{last}}-1}^{-1}}$.
Using

$a_{h,k}=\pi_{h}^{k}(s_{h,k})=\mathop{\rm
argmax}_{a\in{\mathcal{A}}}\overline{Q}_{h}^{k}(s_{h,k},a),$

we then have

$\displaystyle($
$\displaystyle\overline{V}_{h}^{k}-\underline{V}_{h}^{k})(s_{h,k})\leq(\overline{Q}_{h}^{k}-\underline{Q}_{h}^{k})(s_{h,k},a_{h,k})$
$\displaystyle\leq\langle{\bm{\phi}}_{h,k},{\bm{\mu}}_{h,k_{\mathrm{last}}-1}(\overline{{\bm{V}}}_{h+1}^{k_{\mathrm{last}}}-\underline{{\bm{V}}}_{h+1}^{k_{\mathrm{last}}})\rangle+2\beta\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k_{\mathrm{last}}-1}^{-1}}$
$\displaystyle\overset{(a)}{\leq}\langle{\bm{\phi}}_{h,k},({\bm{\mu}}_{h,k-1}-{\bm{\mu}}_{h}^{*})(\overline{{\bm{V}}}_{h+1}^{k_{\mathrm{last}}}-\underline{{\bm{V}}}_{h+1}^{k_{\mathrm{last}}})\rangle+\langle{\bm{\phi}}_{h,k},{\bm{\mu}}_{h}^{*}(\overline{{\bm{V}}}_{h+1}^{k_{\mathrm{last}}}-\underline{{\bm{V}}}_{h+1}^{k_{\mathrm{last}}})\rangle+4\beta\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}$
$\displaystyle\overset{(b)}{\leq}6\beta\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+\langle{\bm{\phi}}_{h,k},{\bm{\mu}}_{h}^{*}(\overline{{\bm{V}}}_{h+1}^{k_{\mathrm{last}}}-\underline{{\bm{V}}}_{h+1}^{k_{\mathrm{last}}})\rangle$
$\displaystyle\overset{(c)}{=}6\beta\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h,k},a_{h,k})$
$\displaystyle\overset{(d)}{=}6\beta\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h+1,k})+X_{h,k}.$

Here $(a)$ uses (E.5), $(b)$ uses

$\displaystyle|\langle{\bm{\phi}}_{h,k},({\bm{\mu}}_{h,k_{\mathrm{last}}-1}-{\bm{\mu}}_{h}^{*})(\overline{{\bm{V}}}_{h+1}^{k_{\mathrm{last}}}-\underline{{\bm{V}}}_{h+1}^{k_{\mathrm{last}}})\rangle|$
$\displaystyle\leq\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k_{\mathrm{last}}-1}^{-1}}\|({\bm{\mu}}_{h,k_{\mathrm{last}}-1}-{\bm{\mu}}_{h}^{*})(\overline{{\bm{V}}}_{h+1}^{k_{\mathrm{last}}}-\underline{{\bm{V}}}_{h+1}^{k_{\mathrm{last}}})\|_{{\bm{H}}_{h,k_{\mathrm{last}}-1}}$
$\displaystyle\leq
2\beta\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k_{\mathrm{last}}-1}^{-1}}\leq
2\beta\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}$

on ${\mathcal{B}}_{V}\cap{\mathcal{B}}_{R}$, $(c)$ uses
$\langle{\bm{\phi}}_{h,k},{\bm{\mu}}_{h}^{*}(\overline{V}_{h+1}^{k_{\mathrm{last}}}-\underline{V}_{h+1}^{k_{\mathrm{last}}})\rangle={\mathbb{P}}_{h}(\overline{V}_{h+1}^{k_{\mathrm{last}}}-\underline{V}_{h+1}^{k_{\mathrm{last}}})(s_{h,k},a_{h,k})={\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h,k},a_{h,k})$,
and $(d)$ uses the notation

$X_{h,k}:={\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h,k},a_{h,k})-(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h+1,k}).$
(E.10)

The last inequality implies

$\displaystyle(\overline{V}_{h}^{k}-\underline{V}_{h}^{k})(s_{h,k})\leq(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h+1,k})+X_{h,k}+6\beta\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}.$

Iterating the above inequality over $h$ and using
$\overline{V}_{H+1}^{k}(\cdot)=\underline{V}_{H+1}^{k}(\cdot)=0$, we have

$(\overline{V}_{h}^{k}-\underline{V}_{h}^{k})(s_{h,k})\leq\sum_{i=h}^{H}\left[X_{i,k}+6\beta\|{\bm{\phi}}_{i,k}\|_{{\bm{H}}_{i,k-1}^{-1}}\right].$
(E.11)

Using the last inequality, it follows that

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}$
$\displaystyle{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h,k},a_{h,k})=\sum_{k=1}^{K}\sum_{h=2}^{H}(\overline{V}_{h}^{k}-\underline{V}_{h}^{k})(s_{h,k})+\sum_{k=1}^{K}\sum_{h=1}^{H}X_{h,k}$
$\displaystyle\overset{(a)}{\leq}\sum_{k=1}^{K}\sum_{h=2}^{H}\sum_{i=h}^{H}\left[X_{i,k}+8\beta\|{\bm{\phi}}_{i,k}\|_{{\bm{H}}_{i,k-1}^{-1}}\right]+\sum_{k=1}^{K}\sum_{h=1}^{H}X_{h,k}$
$\displaystyle=\sum_{k=1}^{K}\sum_{h=2}^{H}(H-h+1)\left[X_{h,k}+6\beta\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}\right]+\sum_{k=1}^{K}\sum_{h=1}^{H}X_{h,k}$
$\displaystyle\overset{(b)}{\leq}6H\beta\sum_{k=1}^{K}\sum_{h=2}^{H}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+\sum_{k=1}^{K}\sum_{h=1}^{H}X_{h,k}b_{h}$
(E.12)

where $(a)$ uses (E.6) and $(b)$ uses the notation $b_{h}=1$ if $h=1$;
otherwise $=H-h+2$ for $2\leq h\leq H$. Clearly, we have $|b_{h}|\leq H$ for
all $h\in[H]$.

We then need to analyze $\sum_{k=1}^{K}\sum_{h=1}^{H}X_{h,k}b_{h}$ with
$X_{h,k}$’s defined in (E.10). Since $s_{h+1,k}$ is
${\mathcal{F}}_{h+1,k}$-measurable,
$\overline{V}_{h+1}^{k},\underline{V}_{h+1}^{k}$ is
${\mathcal{F}}_{H,k-1}$-measurable, we have $X_{h,k}$ is
${\mathcal{F}}_{h+1,k}$-measurable. We also have
${\mathbb{E}}[X_{h,k}|{\mathcal{F}}_{h,k}]=0$, $|X_{h,k}|\leq 2{\mathcal{H}}$
and

$\displaystyle{\mathbb{E}}[X_{h,k}^{2}|{\mathcal{F}}_{h,k}]$
$\displaystyle\leq{\mathbb{E}}[(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})^{2}(s_{h+1,k})|{\mathcal{F}}_{h,k}]$
$\displaystyle\overset{(a)}{\leq}{\mathcal{H}}{\mathbb{E}}[|\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k}|(s_{h+1,k})|{\mathcal{F}}_{h,k}]={\mathcal{H}}{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h,k},a_{h,k})$

where $(a)$ uses
$|\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k}|(\cdot)\leq{\mathcal{H}}$. By
the variance-aware Freedman inequality in Lemma F.2, with probability at least
$1-\delta$, it follows that

$\left|\sum_{k=1}^{K}\sum_{h=1}^{H}X_{h,k}b_{h}\right|\leq
3H\sqrt{\iota}\cdot\sqrt{{\mathcal{H}}\cdot\sum_{k=1}^{K}\sum_{h=1}^{H}{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h,k},a_{h,k})}+10H{\mathcal{H}}\cdot\iota$
(E.13)

where $\iota=\log\frac{4\lceil\log_{2}HK\rceil}{\delta}$. As a result,
plugging (E.13) into (E.10), we have

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h,k},a_{h,k})$
$\displaystyle\leq
3H\sqrt{\iota}\cdot\sqrt{{\mathcal{H}}\cdot\sum_{k=1}^{K}\sum_{h=1}^{H}{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h,k},a_{h,k})}$
$\displaystyle\qquad+6H\beta\sum_{k=1}^{K}\sum_{h=2}^{H}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+10H{\mathcal{H}}\iota.$

Using the inequality that $x\leq 2(a^{2}+b^{2})$ for any
$x\leq|a|\sqrt{x}+b^{2}$, we have

$\sum_{k=1}^{K}\sum_{h=1}^{H}{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h,k},a_{h,k})\leq
12H\beta\sum_{k=1}^{K}\sum_{h=1}^{H}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+38H^{2}{\mathcal{H}}\iota.$

∎

###  E.11 Proof of Lemma C.10

###### Proof of Lemma C.10.

Recall that
$b_{h,k}=\max\\{\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}},\|\widetilde{{\bm{\phi}}}_{h,k}\|_{\widetilde{{\bm{H}}}_{h,k-1}^{-1}}\\},w_{h,k}=\sigma_{h,k}^{-1}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}$
and
$\widetilde{w}_{h,k}=\sigma_{h,k}^{-1}\|\widetilde{{\bm{\phi}}}_{h,k}\|_{\widetilde{{\bm{H}}}_{h,k-1}^{-1}}$.
As a result, we have
$\sigma_{h,k}^{-1}b_{h,k}=\max\left\\{w_{h,k},\widetilde{w}_{h,k}\right\\}$.
On the other hand,

$\sigma_{h,k}^{2}=\max\left\\{\sigma_{\min}^{2},d^{3}H\cdot
E_{h,k},J_{h,k},c_{0}^{-2}b_{h,k}^{2},\left(\frac{W}{\sqrt{c_{1}d}}+{\mathcal{H}}d^{2.5}H\right)b_{h,k}\right\\}.$
(4.5)

Based on what value $\sigma_{h,k}$ takes, we compose the full index set
${\mathcal{I}}:=[H]\times[K]$ into three disjoint sets with ties broken
arbitrarily:

$\displaystyle{\mathcal{J}}_{1}=\left\\{(h,k)\subseteq[H]\times[K]:\sigma_{h,k}^{2}\in\left\\{\sigma_{\min}^{2},d^{3}H\cdot
E_{h,k},U_{h,k}\right\\}\right\\},$
$\displaystyle{\mathcal{J}}_{2}=\left\\{(h,k)\subseteq[H]\times[K]:\sigma_{h,k}^{2}=c_{0}^{-2}b_{h,k}^{2}\right\\},$
$\displaystyle{\mathcal{J}}_{3}=\left\\{(h,k)\subseteq[H]\times[K]:\sigma_{h,k}^{2}=\left(\frac{W}{\sqrt{c_{1}d}}+{\mathcal{H}}d^{2.5}H\right)b_{h,k}\right\\}.$

For simplicity, we denote
$z_{h,k}:=\frac{b_{h,k}}{\sigma_{h,k}}=\max\\{w_{h,k},\widetilde{w}_{h,k}\\}$.
Therefore,

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}b_{h,k}=\sum_{(h,k)\in{\mathcal{I}}}\sigma_{h,k}z_{h,k}=\sum_{i=1}^{3}\sum_{(h,k)\in{\mathcal{J}}_{i}}\sigma_{h,k}z_{h,k}.$
(E.14)

Recall that $\kappa=d\log\left(1+\frac{K}{d\lambda\sigma_{\min}^{2}}\right)$,
we have $\sum_{(h,k)\in{\mathcal{I}}}z_{h,k}^{2}\leq 4H\kappa$. This is
because

$\displaystyle\sum_{(h,k)\in{\mathcal{I}}}z_{h,k}^{2}$
$\displaystyle\leq\sum_{(h,k)\in{\mathcal{I}}}\left(w_{h,k}^{2}+\widetilde{w}_{h,k}^{2}\right)\overset{(a)}{=}\sum_{k=1}^{K}\sum_{h=1}^{H}\min\left\\{1,w_{h,k}^{2}\right\\}+\sum_{k=1}^{K}\sum_{h=1}^{H}\min\left\\{1,\widetilde{w}_{h,k}^{2}\right\\}$
$\displaystyle\overset{(b)}{\leq}4Hd\log\left(1+\frac{K}{d\lambda\sigma_{\min}^{2}}\right)=4H\kappa.$

where $(a)$ uses $z_{h,k}\leq c_{0}\leq 1$ due to $\sigma_{h,k}\geq
c_{0}^{-1}b_{h,k},c_{0}\leq 1$ and $(b)$ uses Lemma F.5. We will frequently
use the above inequality.

Now, we are ready to analyze the three terms in the RHS of (E.14)
respectively.

  * •

For the first term, it follows that

$\displaystyle\sum_{(h,k)\in{\mathcal{J}}_{1}}\sigma_{h,k}z_{h,k}$
$\displaystyle\leq\sqrt{\sum_{(h,k)\in{\mathcal{J}}_{1}}\sigma_{h,k}^{2}}\sqrt{\sum_{(h,k)\in{\mathcal{J}}_{1}}z_{h,k}^{2}}$
$\displaystyle\leq\sqrt{\sum_{(h,k)\in{\mathcal{J}}_{1}}(\sigma_{\min}^{2}+d^{3}H\cdot
E_{h,k}+J_{h,k})}\sqrt{\sum_{(h,k)\in{\mathcal{J}}_{1}}z_{h,k}^{2}}$
$\displaystyle\leq\sqrt{\sum_{(h,k)\in{\mathcal{I}}}(\sigma_{\min}^{2}+d^{3}H\cdot
E_{h,k}+J_{h,k})}\sqrt{\sum_{(h,k)\in{\mathcal{I}}}z_{h,k}^{2}}$
$\displaystyle\leq\sqrt{HK\sigma_{\min}^{2}+\sum_{(h,k)\in{\mathcal{I}}}(d^{3}H\cdot
E_{h,k}+J_{h,k})}\cdot\sqrt{4H\kappa}.$

We provide a upper bound for $\sum_{k=1}^{K}\sum_{h=1}^{H}E_{h,k}$ in Lemma
E.2 whose proof is deferred in Appendix E.11.1.

######  Lemma E.2 (Sum of $E_{h,k}$).

On the event ${\mathcal{B}}_{0}\cap{\mathcal{A}}_{0}$,

$\sum_{k=1}^{K}\sum_{h=1}^{H}E_{h,k}={\mathcal{O}}\left((\beta_{0}+H\beta){\mathcal{H}}\cdot\sum_{k=1}^{K}\sum_{h=1}^{H}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+H^{2}{\mathcal{H}}^{2}\log\frac{4\lceil\log_{2}HK\rceil}{\delta}\right).$

where ${\mathcal{O}}(\cdot)$ hides universal positive constants.

We also provide a upper bound for $\sum_{k=1}^{K}\sum_{h=1}^{H}J_{h,k}$ in
Lemma E.3 whose proof is deferred in Appendix E.11.2.

######  Lemma E.3 (Sum of $J_{h,k}$).

Recall that
$J_{h,k}=[\widehat{\mathbb{V}}_{h}R_{h}+\widehat{\mathbb{V}}_{h}\overline{V}_{h+1}^{k}](s_{h,k},a_{h,k})+R_{h,k}+U_{h,k}$
with $R_{h,k},U_{h,k}$ defined in (4.8) and (4.9) respectively. On the event
${\mathcal{B}}_{R}\cap{\mathcal{B}}_{V}\cap{\mathcal{B}}_{0}\cap{\mathcal{A}}_{0}$,
with probability at least $1-2\delta$,

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}J_{h,k}={\mathcal{O}}\left({\mathcal{G}}^{*}K+[(\beta_{0}+H\beta){\mathcal{H}}+\beta_{R^{2}}]\sum_{k=1}^{K}\sum_{h=1}^{H}b_{h,k}+H^{2}{\mathcal{H}}^{2}\log\frac{4\lceil\log_{2}HK\rceil}{\delta}+H\sigma_{R}^{2}\log\frac{1}{\delta}\right).$

where ${\mathcal{G}}^{*}$ is defined in (4.11) and ${\mathcal{O}}(\cdot)$
hides universal positive constants.

Putting pieces together and using
$\sqrt{a+b+c}\leq\sqrt{a}+\sqrt{b}+\sqrt{c}$, we have

$\displaystyle\begin{split}\sum_{(h,k)\in{\mathcal{J}}_{1}}b_{h,k}&=\sum_{(h,k)\in{\mathcal{J}}_{1}}\sigma_{h,k}z_{h,k}={\mathcal{O}}\left(\sqrt{H\kappa}\cdot\sqrt{K\left(H\sigma_{\min}^{2}+{\mathcal{G}}^{*}\right)}\right)\\\
&\quad+{\mathcal{O}}\left(\sqrt{H\kappa}\cdot\sqrt{H^{3}d^{3}{\mathcal{H}}^{2}\log\frac{4\lceil\log_{2}HK\rceil}{\delta}+H\sigma_{R}^{2}\log\frac{1}{\delta}.}\right)\\\
&\quad+{\mathcal{O}}\left(\sqrt{H\kappa}\cdot\sqrt{[(\beta_{0}+H\beta){\mathcal{H}}d^{3}H+\beta_{R^{2}}]\sum_{(h,k)\in{\mathcal{I}}}b_{h,k}}\right).\end{split}$
(E.15)

  * •

For the second term, due to $\sigma_{h,k}=c_{0}^{-1}b_{h,k}$, we have
$z_{h,k}=b_{h,k}/\sigma_{h,k}=c_{0}\leq 1$ for all
$(h,k)\in{\mathcal{J}}_{2}$. Hence,

$\displaystyle\sum_{(h,k)\in{\mathcal{J}}_{2}}b_{h,k}$
$\displaystyle=\sum_{(h,k)\in{\mathcal{J}}_{2}}\sigma_{h,k}z_{h,k}=\frac{1}{c_{0}}\sum_{(h,k)\in{\mathcal{J}}_{2}}\sigma_{h,k}z_{h,k}^{2}\leq\frac{\sup_{(h,k)\in{\mathcal{I}}}\sigma_{h,k}}{c_{0}}\sum_{(h,k)\in{\mathcal{J}}_{2}}z_{h,k}^{2}$
$\displaystyle\leq\sup_{(h,k)\in{\mathcal{I}}}\frac{\max\\{\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}},\|\widetilde{{\bm{\phi}}}_{h,k}\|_{\widetilde{{\bm{H}}}_{h,k-1}^{-1}}\\}}{c_{0}^{2}}\cdot\sum_{(h,k)\in{\mathcal{I}}}z_{h,k}^{2}\leq\frac{4H\kappa}{c_{0}^{2}\sqrt{\lambda}}$
(E.16)

where the last inequality uses
$\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}\leq\frac{1}{\sqrt{\lambda}}\|{\bm{\phi}}_{h,k}\|\leq\frac{1}{\sqrt{\lambda}}$
and
$\|\widetilde{{\bm{\phi}}}_{h,k}\|_{\widetilde{{\bm{H}}}_{h,k-1}^{-1}}\leq\frac{1}{\sqrt{\lambda}}\|\widetilde{{\bm{\phi}}}_{h,k}\|\leq\frac{1}{\sqrt{\lambda}}$
for any $(h,k)\in{\mathcal{I}}$.

  * •

For the third term,
$\sigma_{h,k}^{2}=\left(\frac{W}{\sqrt{c_{1}d}}+{\mathcal{H}}d^{2.5}H\right)b_{h,k}$
and thus
$\sigma_{h,k}=\left(\frac{W}{\sqrt{c_{1}d}}+{\mathcal{H}}d^{2.5}H\right)z_{h,k}$.
Hence,

$\displaystyle\sum_{(h,k)\in{\mathcal{J}}_{3}}b_{h,k}$
$\displaystyle=\sum_{(h,k)\in{\mathcal{J}}_{3}}\sigma_{h,k}z_{h,k}=\left(\frac{W}{\sqrt{c_{1}d}}+{\mathcal{H}}d^{2.5}H\right)\sum_{(h,k)\in{\mathcal{J}}_{3}}z_{h,k}^{2}$
$\displaystyle\leq\left(\frac{W}{\sqrt{c_{1}d}}+{\mathcal{H}}d^{2.5}H\right)\sum_{(h,k)\in{\mathcal{I}}}z_{h,k}^{2}\leq
4H\kappa\cdot\left(\frac{W}{\sqrt{c_{1}d}}+{\mathcal{H}}d^{2.5}H\right).$
(E.17)

Combing (E.15), (• ‣ E.11) and (• ‣ E.11), we have

$\sum_{(h,k)\in{\mathcal{I}}}b_{h,k}={\mathcal{O}}\left(C+\sqrt{H\kappa}\sqrt{[(\beta_{0}+H\beta){\mathcal{H}}d^{3}H+\beta_{R^{2}}]\cdot\sum_{(h,k)\in{\mathcal{I}}}b_{h,k}}\right)$

where

$\displaystyle C$
$\displaystyle=\sqrt{H\kappa}\cdot\sqrt{K\left(H\sigma_{\min}^{2}+{\mathcal{G}}^{*}\right)}+H\kappa\cdot\left(\frac{W}{\sqrt{c_{1}d}}+\frac{1}{c_{0}^{2}\sqrt{\lambda}}+{\mathcal{H}}d^{2.5}H\right)$
$\displaystyle\quad+\sqrt{H\kappa}\cdot\sqrt{H^{3}d^{3}{\mathcal{H}}^{2}\log\frac{4\lceil\log_{2}HK\rceil}{\delta}+H\sigma_{R}^{2}\log\frac{1}{\delta}}.$

Using the inequality that $x\leq 2(a^{2}+b^{2})$ for any
$x\leq|a|\sqrt{x}+b^{2}$, we have

$\sum_{(h,k)\in{\mathcal{I}}}b_{h,k}={\mathcal{O}}\left(C+H^{2}{\mathcal{H}}\kappa
d^{3}\left(\beta_{0}+H\beta\right)+H\kappa\beta_{R^{2}}\right).$

In the following, we are going to simplify the last inequality. We will use
$\widetilde{\mathcal{O}}(\cdot)$ to hide logarithmic factors for simplicity.
Notice that $\kappa=\widetilde{\mathcal{O}}(d)$. By setting
$\lambda=\frac{1}{{\mathcal{H}}^{2}+W^{2}}$, we have
$\beta_{R}=\beta_{V}=\widetilde{\mathcal{O}}(\sqrt{d})$ and thus
$\beta=\beta_{V}+\beta_{R}=\widetilde{\mathcal{O}}(\sqrt{d})$. Moreover,
$\beta_{R^{2}}=\widetilde{\mathcal{O}}\left(\sqrt{d}+\sqrt{d}\frac{\sigma_{R^{2}}}{\sigma_{\min}}+\sqrt{\lambda}W\right)=\widetilde{\mathcal{O}}\left(\sqrt{d}+\sqrt{d}\frac{\sigma_{R^{2}}}{\sigma_{\min}}\right)$
and
$\beta_{0}=\widetilde{\mathcal{O}}\left(\frac{\sqrt{d^{3}H}{\mathcal{H}}}{\sigma_{\min}}+\sqrt{d\lambda}{\mathcal{H}}\right)=\widetilde{\mathcal{O}}\left(\frac{\sqrt{d^{3}H}{\mathcal{H}}}{\sigma_{\min}}+\sqrt{d}\right)$.
Therefore,

$\displaystyle\sum_{(h,k)\in{\mathcal{I}}}b_{h,k}$
$\displaystyle={\mathcal{O}}\left(C+H^{2}{\mathcal{H}}\kappa
d^{3}\left(\beta_{0}+H\beta\right)+H\kappa\beta_{R^{2}}\right)$
$\displaystyle={\mathcal{O}}(C)+\widetilde{\mathcal{O}}\left(\frac{H^{2.5}d^{5.5}{\mathcal{H}}^{2}+Hd^{1.5}\sigma_{R^{2}}}{\sigma_{\min}}+H^{3}d^{4.5}{\mathcal{H}}+Hd^{1.5}\right).$

We then analyze $C$. Using $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for non-negative
numbers $a,b\geq 0$, we have

$\displaystyle
C=\widetilde{\mathcal{O}}\left(\sqrt{dHK{\mathcal{G}}^{*}}+Hd^{0.5}K^{0.5}\sigma_{\min}+H^{2}d^{3.5}{\mathcal{H}}+H^{2}d^{2}{\mathcal{H}}+Hd^{0.5}\sigma_{R}+Hd\right).$

Putting the results together, we have

$\displaystyle\sum_{(h,k)\in{\mathcal{I}}}b_{h,k}=\widetilde{\mathcal{O}}\left(\sqrt{dHK{\mathcal{G}}^{*}}+Hd^{0.5}K^{0.5}\sigma_{\min}+\frac{H^{2.5}d^{5.5}{\mathcal{H}}^{2}+Hd^{1.5}\sigma_{R^{2}}}{\sigma_{\min}}+H^{3}d^{4.5}{\mathcal{H}}+Hd^{0.5}\sigma_{R}+Hd^{1.5}\right).$

∎

####  E.11.1 Proof of Lemma E.2

###### Proof of Lemma E.2.

By the definition of $E_{h,k}$ in (4.7), it follows that

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}E_{h,k}$
$\displaystyle\leq\sum_{k=1}^{K}\sum_{h=1}^{H}\left[2{\mathcal{H}}\beta_{0}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+{\mathcal{H}}\cdot\left[\widehat{\mathbb{P}}_{h,k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})\right](s_{h,k},a_{h,k})\right]$
$\displaystyle\overset{(a)}{\leq}\sum_{k=1}^{K}\sum_{h=1}^{H}\left[4{\mathcal{H}}\beta_{0}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+{\mathcal{H}}\cdot\left[{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})\right](s_{h,k},a_{h,k})\right]$
$\displaystyle\overset{(b)}{\leq}(4\beta_{0}+16H\beta){\mathcal{H}}\cdot\sum_{k=1}^{K}\sum_{h=1}^{H}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+38H^{2}{\mathcal{H}}^{2}\log\frac{4\lceil\log_{2}HK\rceil}{\delta}$
$\displaystyle={\mathcal{O}}\left((\beta_{0}+H\beta){\mathcal{H}}\cdot\sum_{k=1}^{K}\sum_{h=1}^{H}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+H^{2}{\mathcal{H}}^{2}\log\frac{4\lceil\log_{2}HK\rceil}{\delta}\right)$

where $(a)$ uses
$\left|[(\widehat{\mathbb{P}}_{h,k}-{\mathbb{P}}_{h})\overline{V}_{h+1}^{k}](s_{h,k},a_{h,k})\right|=|\langle{\bm{\phi}}_{h,k},({\bm{\mu}}_{h,k-1}-{\bm{\mu}}_{h}^{*})\overline{V}_{h+1}^{k}\rangle|\leq\beta_{0}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}$
on ${\mathcal{B}}_{0}$ and $(b)$ follows from Lemma C.9. ∎

####  E.11.2 Proof of Lemma E.3

###### Proof of Lemma E.3.

By Lemma C.3, on the event ${\mathcal{B}}_{R}$, we have
$\left|[\widehat{\mathbb{V}}_{h}\widehat{R}_{h}-{\mathbb{V}}_{h}R_{h}](s_{h,k},a_{h,k})\right|\leq
R_{h,k}$ for all $h\in[H]$ and $k\in[K]$. By Lemma C.5, on the event
${\mathcal{B}}_{0}\cap{\mathcal{B}}_{V}$,
$[\widehat{\mathbb{V}}_{h}\overline{V}_{h+1}^{k}](s_{h,k},a_{h,k})\leq[{\mathbb{V}}_{h}V_{h+1}^{*}](s_{h,k},a_{h,k})+U_{h,k}$
for all $h\in[H]$ and $k\in[K]$. Therefore,

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}J_{h,k}$
$\displaystyle\leq\sum_{k=1}^{K}\sum_{h=1}^{H}[{\mathbb{V}}_{h}R_{h}+{\mathbb{V}}_{h}V_{h+1}^{*}](s_{h,k},a_{h,k})+2\sum_{k=1}^{K}\sum_{h=1}^{H}R_{h,k}+2\sum_{k=1}^{K}\sum_{h=1}^{H}U_{h,k}$
$\displaystyle:=(I)+(II)+(III).$

For the term $(III)$, we have

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}U_{h,k}$
$\displaystyle=\sum_{k=1}^{K}\sum_{h=1}^{H}\left[11{\mathcal{H}}\beta_{0}\cdot\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+4{\mathcal{H}}\cdot\widehat{\mathbb{P}}_{h,k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h,k},a_{h,k})\right]$
$\displaystyle\overset{(a)}{\leq}\sum_{k=1}^{K}\sum_{h=1}^{H}\left[19{\mathcal{H}}\beta_{0}\cdot\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+4{\mathcal{H}}\cdot{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h,k},a_{h,k})\right]$
$\displaystyle\overset{(b)}{\leq}(19\beta_{0}+64H\beta){\mathcal{H}}\cdot\sum_{k=1}^{K}\sum_{h=1}^{H}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+152H^{2}{\mathcal{H}}^{2}\log\frac{4\lceil\log_{2}HK\rceil}{\delta},$
(E.18)

where $(a)$ uses
$\left|[(\widehat{\mathbb{P}}_{h,k}-{\mathbb{P}}_{h})\overline{V}_{h+1}^{k}](s_{h,k},a_{h,k})\right|=|\langle{\bm{\phi}}_{h,k},({\bm{\mu}}_{h,k-1}-{\bm{\mu}}_{h}^{*})\overline{V}_{h+1}^{k}\rangle|\leq\beta_{0}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}$
on ${\mathcal{B}}_{0}$; and $(b)$ follows from Lemma C.9.

For the term $(II)$, we have

$\sum_{k=1}^{K}\sum_{h=1}^{H}R_{h,k}=\beta_{R^{2}}\sum_{k=1}^{K}\sum_{h=1}^{H}\|\widetilde{{\bm{\phi}}}_{h,k}\|_{\widetilde{{\bm{H}}}_{h,k-1}^{k-1}}+2{\mathcal{H}}\beta_{R}\sum_{k=1}^{K}\sum_{h=1}^{H}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}.$
(E.19)

We provide two ways to analyze the term $(I)$.

  * •

On one hand, we denote
$X_{k}=\sum_{h=1}^{H}[{\mathbb{V}}_{h}R_{h}+{\mathbb{V}}_{h}V_{h+1}^{*}](s_{h,k},a_{h,k})$
for simplicity. Let ${\mathcal{G}}_{k}:={\mathcal{F}}_{H,k}$ be the
$\sigma$-field generated by all the random variables over the first $k$
episodes. Then $\pi_{k}$ is ${\mathcal{G}}_{k-1}$-measurable, $X_{k}\geq 0$ is
${\mathcal{G}}_{k}$-measurable, and $|X_{k}|\leq
H(\sigma_{R}^{2}+{\mathcal{H}}^{2})$. Therefore,
$|X_{k}-{\mathbb{E}}[X_{k}|{\mathcal{G}}_{k-1}]|\leq
H(\sigma_{R}^{2}+{\mathcal{H}}^{2})$ and $\operatorname{{\rm
Var}}[X_{k}|{\mathcal{G}}_{k-1}]\leq
H(\sigma_{R}^{2}+{\mathcal{H}}^{2})\cdot{\mathbb{E}}[X_{k}|{\mathcal{G}}_{k-1}]$.
By the variance-aware Freedman inequality in Lemma F.2, with probability at
least $1-\delta$, we have

$\displaystyle\sum_{k=1}^{K}X_{k}$
$\displaystyle\leq\sum_{k=1}^{K}{\mathbb{E}}[X_{k}|{\mathcal{F}}_{k-1}]+3\sqrt{H(\sigma_{R}^{2}+{\mathcal{H}}^{2})\sum_{k=1}^{K}{\mathbb{E}}[X_{k}|{\mathcal{G}}_{k-1}]\log\frac{2\lceil\log_{2}K\rceil}{\delta}}$
$\displaystyle\qquad+5H(\sigma_{R}^{2}+{\mathcal{H}}^{2})\log\frac{2\lceil\log_{2}K\rceil}{\delta}$
$\displaystyle\leq
3\sum_{k=1}^{K}{\mathbb{E}}[X_{k}|{\mathcal{F}}_{k-1}]+7H(\sigma_{R}^{2}+{\mathcal{H}}^{2})\log\frac{2\lceil\log_{2}K\rceil}{\delta}.$

Notice that

$\displaystyle{\mathbb{E}}[X_{k}|{\mathcal{F}}_{k-1}]$
$\displaystyle={\mathbb{E}}\left[\sum_{h=1}^{H}[{\mathbb{V}}_{h}R_{h}+{\mathbb{V}}_{h}V_{h+1}^{*}](s_{h,k},a_{h,k})\bigg{|}{\mathcal{G}}_{k-1}\right]$
$\displaystyle=\sum_{h=1}^{H}\sum_{(s,a)}d_{h}^{\pi_{k}}(s,a)[{\mathbb{V}}_{h}R_{h}+{\mathbb{V}}_{h}V_{h+1}^{*}](s,a)$

where
$d_{h}^{\pi_{k}}(s,a)={\mathbb{P}}^{\pi_{k}}(s_{h}=s,a_{h}=a|s_{0}=s_{1,k})$
is the probability reaching $(s_{h,k},a_{h,k})=(s,a)$ at the $h$-th step when
the agent starts from $s_{1,k}$ and follows the policy $\pi_{k}$. Therefore,
we have

$\displaystyle(I)$ $\displaystyle\leq
3\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{(s,a)}d_{h}^{\pi_{k}}(s,a)[{\mathbb{V}}_{h}R_{h}+{\mathbb{V}}_{h}V_{h+1}^{*}](s,a)+7H(\sigma_{R}^{2}+{\mathcal{H}}^{2})\log\frac{2\lceil\log_{2}K\rceil}{\delta}$
$\displaystyle\leq
3{\mathcal{G}}_{0}^{*}K+7H(\sigma_{R}^{2}+{\mathcal{H}}^{2})\log\frac{2\lceil\log_{2}K\rceil}{\delta}$

where

${\mathcal{G}}_{0}^{*}=\frac{1}{K}\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{(s,a)}d_{h}^{\pi_{k}}(s,a)[{\mathbb{V}}_{h}R_{h}+{\mathbb{V}}_{h}V_{h+1}^{\pi_{k}}](s,a).$

  * •

On the other hand, we have

$\displaystyle(I)$
$\displaystyle=\sum_{k=1}^{K}\sum_{h=1}^{H}\left[{\mathbb{V}}_{h}V_{h+1}^{*}-{\mathbb{V}}_{h}V_{h+1}^{\pi_{k}}\right](s_{h,k},a_{h,k})+\sum_{k=1}^{K}\sum_{h=1}^{H}[{\mathbb{V}}_{h}R_{h}+{\mathbb{V}}_{h}V_{h+1}^{\pi_{k}}](s_{h,k},a_{h,k})$
$\displaystyle\overset{\eqref{eq:var-
diff}}{\leq}2{\mathcal{H}}\cdot\sum_{k=1}^{K}\sum_{h=1}^{H}{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})(s_{h,k},a_{h,k})+\sum_{k=1}^{K}\sum_{h=1}^{H}[{\mathbb{V}}_{h}R_{h}+{\mathbb{V}}_{h}V_{h+1}^{\pi_{k}}](s_{h,k},a_{h,k})$
$\displaystyle\leq
2{\mathcal{H}}\cdot\sum_{k=1}^{K}\sum_{h=1}^{H}{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})(s_{h,k},a_{h,k})+2{\mathcal{V}}^{2}K+2H(\sigma_{R}^{2}+{\mathcal{H}}^{2})\log\frac{1}{\delta}$
$\displaystyle\leq
2{\mathcal{V}}^{2}K+2H(\sigma_{R}^{2}+{\mathcal{H}}^{2})\log\frac{1}{\delta}+16H\beta{\mathcal{H}}\sum_{k=1}^{K}\sum_{h=1}^{H}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+76H^{2}{\mathcal{H}}^{2}\log\frac{4\lceil\log_{2}HK\rceil}{\delta}$
$\displaystyle\leq
2{\mathcal{V}}^{2}K+16H\beta{\mathcal{H}}\sum_{k=1}^{K}\sum_{h=1}^{H}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+78H^{2}{\mathcal{H}}^{2}\log\frac{4\lceil\log_{2}HK\rceil}{\delta}+2H\sigma_{R}^{2}\log\frac{1}{\delta}$

where the first inequality uses (• ‣ E.11.2), the second inequality uses Lemma
E.4, and the third inequality uses Lemma C.8.

$\displaystyle\left[{\mathbb{V}}_{h}V_{h+1}^{*}-{\mathbb{V}}_{h}V_{h+1}^{\pi_{k}}\right](s_{h,k},a_{h,k})$
$\displaystyle={\mathbb{P}}_{h}[V_{h+1}^{*}]^{2}(s_{h,k},a_{h,k})-[{\mathbb{P}}_{h}V_{h+1}^{*}(s_{h,k},a_{h,k})]^{2}$
$\displaystyle\quad-\left({\mathbb{P}}_{h}[V_{h+1}^{\pi_{k}}]^{2}(s_{h,k},a_{h,k})-[{\mathbb{P}}_{h}V_{h+1}^{\pi_{k}}(s_{h,k},a_{h,k})]^{2}\right)$
$\displaystyle\overset{(a)}{\leq}{\mathbb{P}}_{h}[V_{h+1}^{*}]^{2}(s_{h,k},a_{h,k})-{\mathbb{P}}_{h}[V_{h+1}^{\pi_{k}}]^{2}(s_{h,k},a_{h,k})$
$\displaystyle\overset{(b)}{\leq}2{\mathcal{H}}\cdot{\mathbb{P}}_{h}(V_{h+1}^{*}-V_{h+1}^{\pi_{k}})(s_{h,k},a_{h,k})$
$\displaystyle\overset{(c)}{\leq}2{\mathcal{H}}\cdot{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})(s_{h,k},a_{h,k})$
(E.20)

where $(a)$ uses $V_{h+1}^{*}(\cdot)\geq V_{h+1}^{\pi_{k}}(\cdot)$, $(b)$ uses
$V_{h+1}^{\pi_{k}}(\cdot)\leq V_{h+1}^{*}(\cdot)\leq{\mathcal{H}}$, and $(c)$
uses Lemma C.4.

Finally, we are going to put pieces together. In order to simplicity notation,
we use
$b_{h,k}=\max\\{\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}},\|\widetilde{{\bm{\phi}}}_{h,k}\|_{\widetilde{{\bm{H}}}_{h,k-1}^{-1}}\\}$
and $\beta=\beta_{V}+\beta_{R}$. From the first bullet point, we have

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}J_{h,k}={\mathcal{O}}\left({\mathcal{G}}_{0}^{*}\cdot
K+[(\beta_{0}+H\beta){\mathcal{H}}+\beta_{R^{2}}]\cdot\sum_{k=1}^{K}\sum_{h=1}^{H}b_{h,k}+H^{2}{\mathcal{H}}^{2}\log\frac{4\lceil\log_{2}HK\rceil}{\delta}+H\sigma_{R}^{2}\log\frac{1}{\delta}\right).$

From the second bullet point, we have

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}J_{h,k}={\mathcal{O}}\left({\mathcal{V}}^{2}K+[(\beta_{0}+H\beta){\mathcal{H}}+\beta_{R^{2}}]\sum_{k=1}^{K}\sum_{h=1}^{H}b_{h,k}+H^{2}{\mathcal{H}}^{2}\log\frac{4\lceil\log_{2}HK\rceil}{\delta}+H\sigma_{R}^{2}\log\frac{1}{\delta}\right).$

Taking minimum of the last two inequalities and using
$\min\left\\{{\mathcal{G}}_{0}^{*},{\mathcal{V}}^{2}\right\\}\leq{\mathcal{G}}^{*}$
complete the proof. ∎

####  E.11.3 Proof of Lemma E.4

######  Lemma E.4 (Total variance lemma).

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

$\sum_{k=1}^{K}\sum_{h=1}^{H}[{\mathbb{V}}_{h}R_{h}+{\mathbb{V}}_{h}V_{h+1}^{\pi_{k}}](s_{h,k},a_{h,k})\leq
2{\mathcal{V}}^{2}K+2H(\sigma_{R}^{2}+{\mathcal{H}}^{2})\log\frac{1}{\delta}.$

###### Proof of Lemma E.4.

The proof uses a similar argument as Lemma C.5 in [Jin et al., 2018]. Notice
that the first state $s_{1,k}$ is fixed and $a_{h,k}=\pi_{h}^{k}(s_{h,k})$.
Therefore, $(s_{2,k},\cdots,s_{H,k})$ is a sequence generated by following
policy $\pi_{k}$ starting at $s_{1,k}$. Let ${\mathcal{G}}_{k}$ be the
$\sigma$-field generated by all the random variables over the first $k$
episodes.
$X_{k}=\sum_{h=1}^{H}[{\mathbb{V}}_{h}R_{h}+{\mathbb{V}}_{h}V_{h+1}^{\pi_{k}}](s_{h,k},a_{h,k})$.
We have the following properties about $X_{k}$. Clearly $\pi_{k}$ is
${\mathcal{G}}_{k-1}$-measurable, $X_{k}\geq 0$ is
${\mathcal{G}}_{k}$-measurable, and $|X_{k}|\leq
H(\sigma_{R}^{2}+{\mathcal{H}}^{2})$.

Let ${\mathbb{E}}_{k}(\cdot):={\mathbb{E}}[\cdot|{\mathcal{G}}_{k}]$ for
simplicity.

$\displaystyle{\mathcal{V}}^{2}$
$\displaystyle\geq{\mathbb{E}}_{k-1}\left[\sum_{h=1}^{H}R_{h}(s_{h,k},a_{h,k})-V_{1}^{\pi_{k}}(s_{1,k})\right]^{2}$
$\displaystyle\overset{(a)}{=}{\mathbb{E}}_{k-1}\left[\sum_{h=1}^{H}\left(R_{h}(s_{h,k},a_{h,k})+V_{h+1}^{\pi_{k}}(s_{{h+1},k})-V_{h}^{\pi_{k}}(s_{h,k})\right)\right]^{2}$
$\displaystyle\overset{(b)}{=}\sum_{h=1}^{H}{\mathbb{E}}_{k-1}\left[R_{h}(s_{h,k},a_{h,k})+V_{h+1}^{\pi_{k}}(s_{{h+1},k})-V_{h}^{\pi_{k}}(s_{h,k})\right]^{2}$
$\displaystyle\overset{(c)}{=}\sum_{h=1}^{H}{\mathbb{E}}_{k-1}\left[[R_{h}-r_{h}]^{2}(s_{h,k},a_{h,k})+\left[r_{h}(s_{h,k},a_{h,k})+V_{h+1}^{\pi_{k}}(s_{{h+1},k})-V_{h}^{\pi_{k}}(s_{h,k})\right]^{2}\right]$
$\displaystyle\overset{(d)}{=}{\mathbb{E}}_{k-1}\sum_{h=1}^{H}[{\mathbb{V}}_{h}R_{h}+{\mathbb{V}}_{h}V_{h+1}^{\pi_{k}}](s_{h,k},a_{h,k})={\mathbb{E}}[X_{k}|{\mathcal{F}}_{k-1}]$

where $(a)$ uses $V_{H+1}^{\pi_{k}}(\cdot)=0$, $(b)$ uses the independence due
to the Markov property, $(c)$ holds since $R_{h}(s_{h,k},a_{h,k})$ is
independent with $s_{h+1,k}$ conditioning on $(s_{h,k},a_{h,k})$, and $(d)$
uses
$V_{h}^{\pi_{k}}(s_{h,k})=r_{h}(s_{h,k},a_{h,k})+{\mathbb{E}}_{s_{h+1,k}\sim{\mathbb{P}}_{h}(\cdot|s_{h,k},a_{h,k})}[V_{h+1}^{\pi_{k}}(s_{h+1,k})]$.
Using $\operatorname{{\rm Var}}[X_{k}|{\mathcal{G}}_{k-1}]\leq
H(\sigma_{R}^{2}+{\mathcal{H}}^{2})\cdot{\mathbb{E}}[X_{k}|{\mathcal{G}}_{k-1}]$,
we have

$\displaystyle\sum_{k=1}^{K}\operatorname{{\rm
Var}}[X_{k}|{\mathcal{G}}_{k-1}]\leq
H(\sigma_{R}^{2}+{\mathcal{H}}^{2})\cdot\sum_{k=1}^{K}{\mathbb{E}}[X_{k}|{\mathcal{G}}_{k-1}]\leq(\sigma_{R}^{2}+{\mathcal{H}}^{2}){\mathcal{V}}^{2}HK.$

By the Freedman inequality in Lemma F.1, with probability at least $1-\delta$,
we have

$\displaystyle\sum_{k=1}^{K}$
$\displaystyle\sum_{h=1}^{H}[{\mathbb{V}}_{h}R_{h}+{\mathbb{V}}_{h}V_{h+1}^{\pi_{k}}](s_{h,k},a_{h,k})$
$\displaystyle=\sum_{k=1}^{K}X_{k}\leq\sum_{k=1}^{K}{\mathbb{E}}[X_{k}|{\mathcal{F}}_{k-1}]+\sqrt{2(\sigma_{R}^{2}+{\mathcal{H}}^{2}){\mathcal{V}}^{2}HK\log\frac{1}{\delta}}+\frac{2}{3}H(\sigma_{R}^{2}+{\mathcal{H}}^{2})\log\frac{1}{\delta}$
$\displaystyle\leq{\mathcal{V}}^{2}K+2\sqrt{{\mathcal{V}}^{2}K\cdot
H(\sigma_{R}^{2}+{\mathcal{H}}^{2})\log\frac{1}{\delta}}+\frac{2}{3}H(\sigma_{R}^{2}+{\mathcal{H}}^{2})\log\frac{1}{\delta}$
$\displaystyle\leq
2{\mathcal{V}}^{2}K+2H(\sigma_{R}^{2}+{\mathcal{H}}^{2})\log\frac{1}{\delta}.$

∎

##  Appendix F Auxiliary Lemmas

###  F.1 Concentration Inequalities

######  Lemma F.1 (Freedman inequality [Freedman, 1975]).

Let $\\{X_{t}\\}_{t\in[T]}$ be a stochastic process that adapts to the
filtration ${\mathcal{F}}_{t}$ so that $X_{t}$ is
${\mathcal{F}}_{t}$-measurable, ${\mathbb{E}}[X_{t}|{\mathcal{F}}_{t-1}]=0$,
$|X_{t}|\leq M$ and
$\sum_{t=1}^{T}{\mathbb{E}}[X_{t}^{2}|{\mathcal{F}}_{t-1}]\leq V$ where $M>0$
and $V>0$ are positive constants. Then with probability at least $1-\delta$,
we have

$\sum_{t=1}^{T}X_{t}\leq\sqrt{2V\ln\frac{1}{\delta}}+\frac{2M}{3}\ln\frac{1}{\delta}.$

######  Lemma F.2 (Variance-aware Freedman inequality).

Let $\\{X_{t}\\}_{t\in[T]}$ be a stochastic process that adapts to the
filtration ${\mathcal{F}}_{t}$ so that $X_{t}$ is
${\mathcal{F}}_{t}$-measurable, ${\mathbb{E}}[X_{t}|{\mathcal{F}}_{t-1}]=0$,
$|X_{t}|\leq M$ and
$\sum_{t=1}^{T}{\mathbb{E}}[X_{t}^{2}|{\mathcal{F}}_{t-1}]\leq V^{2}$ where
$M>0$ and $V>0$ are positive constants. Then with probability at least
$1-\delta$, we have

$\left|\sum_{t=1}^{T}X_{t}\right|\leq
3\sqrt{\sum_{t=1}^{T}{\mathbb{E}}[X_{t}^{2}|{\mathcal{F}}_{t-1}]\cdot\log\frac{2K}{\delta}}+5M\log\frac{2K}{\delta}$

where $K=1+\lceil 2\log_{2}\frac{V}{M}\rceil$.

###### Proof of Lemma F.2.

By Theorem 5 in [Li et al., 2021], we have for any positive integer $K\geq 1$,

${\mathbb{P}}\left(\left|\sum_{t=1}^{T}X_{t}\right|\leq\sqrt{8\max\left\\{\sum_{t=1}^{T}{\mathbb{E}}[X_{t}^{2}|{\mathcal{F}}_{t-1}],\frac{V^{2}}{2^{K}}\right\\}\cdot\ln\frac{2K}{\delta}}+\frac{4M}{3}\ln\frac{2K}{\delta}\right)\geq
1-\delta.$

By setting $K=1+\lceil 2\log_{2}\frac{V}{M}\rceil$, we have
$\frac{V^{2}}{2^{K}}\leq M^{2}$. Using $\max\\{a,b\\}\leq a+b$,
$\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for any $a,b\geq 0$ and
$\ln\frac{2K}{\delta}\geq 1$, we complete the proof. ∎

The following two lemmas are the counterpart lemmas of Theorem 3.1 under
light-tail assumption.

######  Lemma F.3 (Bernstein inequality for self-normalized martingales, Lemma
F.4 in [Hu et al., 2022]).

Let $\\{{\mathcal{G}}_{t}\\}_{t\geq 0}$ be a filtration and
$\\{{\bm{x}}_{t},\eta_{t}\\}_{t\geq 0}$ be a stochastic process so that
${\bm{x}}_{t}\in{\mathbb{R}}^{d}$ is ${\mathcal{G}}_{t}$-measurable and
$\eta_{t}\in{\mathbb{R}}$ is ${\mathcal{G}}_{t+1}$-measurable.. If
$\|{\bm{x}}_{t}\|\leq L$ and $\\{\eta_{t}\\}_{t\geq 1}$ satisfies that
${\mathbb{E}}[\eta_{t}|{\mathcal{G}}_{t}]=0$,
${\mathbb{E}}[\eta_{t}^{2}|{\mathcal{G}}_{t}]\leq\sigma^{2}$ and
$|\eta_{t}\min\left\\{1,\|{\bm{x}}_{t}\|_{{\bm{Z}}_{t-1}^{-1}}\right\\}|\leq
M$ for all $t\geq 1$. Then, for any $\delta\in(0,1)$, with probability at
least $1-\delta$, we have for all $t\geq 1$,

$\left\|\sum_{j=1}^{t}{\bm{x}}_{j}\eta_{j}\right\|_{{\bm{Z}}_{t}^{-1}}\leq
8\sigma\sqrt{d\log\left(1+\frac{tL^{2}}{d\lambda}\right)\log\frac{4t^{2}}{\delta}}+4M\log\frac{4t^{2}}{\delta}$

where
${\bm{Z}}_{t}=\lambda{\bm{I}}+\sum_{j=1}^{t}{\bm{x}}_{j}{\bm{x}}_{j}^{\top}$
for $t\geq 1$ and ${\bm{Z}}_{0}=\lambda{\bm{I}}$.

######  Lemma F.4 (Hoeffding inequality for self-normalized martingales,
Theorem 1 in [Abbasi-Yadkori et al., 2011]).

Let $\\{{\mathcal{G}}_{t}\\}_{t\geq 0}$ be a filtration and
$\\{{\bm{x}}_{t},\eta_{t}\\}_{t\geq 0}$ be a stochastic process so that
${\bm{x}}_{t}\in{\mathbb{R}}^{d}$ is ${\mathcal{G}}_{t}$-measurable and
$\eta_{t}\in{\mathbb{R}}$ is ${\mathcal{G}}_{t+1}$-measurable.. If
$\|{\bm{x}}_{t}\|\leq L$ and $\\{\eta_{t}\\}_{t\geq 1}$ satisfies that
${\mathbb{E}}[\eta_{t}|{\mathcal{G}}_{t}]=0$ and $|\eta_{t}|\leq M$ for all
$t\geq 1$. Then, for any $\delta\in(0,1)$, with probability at least
$1-\delta$, we have for all $t\geq 1$,

$\left\|\sum_{j=1}^{t}{\bm{x}}_{j}\eta_{j}\right\|_{{\bm{Z}}_{t}^{-1}}\leq
M\sqrt{d\log\left(1+\frac{tL^{2}}{d\lambda}\right)+\log\frac{1}{\delta}}$

where
${\bm{Z}}_{t}=\lambda{\bm{I}}+\sum_{j=1}^{t}{\bm{x}}_{j}{\bm{x}}_{j}^{\top}$
for $t\geq 1$ and ${\bm{Z}}_{0}=\lambda{\bm{I}}$.

###  F.2 Elliptical Lemmas

######  Lemma F.5 (Lemma 11 in [Abbasi-Yadkori et al., 2011]).

Let $\\{{\bm{x}}_{t}\\}_{t\geq 1}\subset{\mathbb{R}}^{d}$ and assume
$\|{\bm{x}}_{t}\|\leq L$ for all $t\geq 1$. Set
${\bm{Z}}_{t}=\sum_{s=1}^{t}{\bm{x}}_{t}{\bm{x}}_{t}^{\top}+\lambda{\bm{I}}$.
Then it follows that

$\sum_{t=1}^{T}\min\left\\{1,\|{\bm{x}}_{t}\|^{2}_{{\bm{Z}}_{t-1}}\right\\}\leq
2d\log\left(\frac{d\lambda+TL^{2}}{d\lambda}\right).$

######  Lemma F.6 (Lemma 12 in [Abbasi-Yadkori et al., 2011]).

Suppose ${\bm{A}},{\bm{B}}\in{\mathbb{R}}^{d\times d}$ are two positive
definite matrices satisfying that ${\bm{A}}\succeq{\bm{B}}$, then for any
${\bm{x}}\in{\mathbb{R}}^{d}$,

$\|{\bm{x}}\|_{{\bm{B}}^{-1}}\leq\|{\bm{x}}\|_{{\bm{A}}^{-1}}\sqrt{\frac{\mathrm{det}({\bm{A}})}{\mathrm{det}({\bm{B}})}}.$

###  F.3 Function Class and Covering Number

This subsection collects important lemmas in [He et al., 2022]. Let
${\mathcal{K}}=\left\\{k_{1},k_{2},\cdots\right\\}$ denote the set of episodes
where the algorithm updates the value function in Algorithm 2. For a given
total number of episodes $K$, it definitely follows that $|{\mathcal{K}}|\leq
K$. Furthermore, due to the mechanism of rare-switching value function
updates, $|{\mathcal{K}}|$ is actually much smaller than $K$.

######  Lemma F.7.

$|{\mathcal{K}}|\leq
dH\log_{2}\left(1+\frac{K}{\lambda\sigma_{\min}^{2}}\right).$

###### Proof of Lemma F.7.

The proof is almost identical to Lemma E.1 in [He et al., 2022] except that we
maintain the dependence on $\sigma_{\min}$. According to the determinant-based
criterion, for each episode $k_{i}$, there exists a stage $h^{\prime}\in[H]$
such that $\mathrm{det}({\bm{H}}_{h^{\prime},k_{i}-1})\geq
2\mathrm{det}({\bm{H}}_{h^{\prime},k_{i-1}-1})$. Since we always have
${\bm{H}}_{h,k_{i}-1}\succeq{\bm{H}}_{h,k_{i-1}-1}$ for all $h\in[H]$, it then
follows that

$\prod_{h\in[H]}\mathrm{det}({\bm{H}}_{h,k_{i}-1})\geq
2\prod_{h\in[H]}\mathrm{det}({\bm{H}}_{h,k_{i-1}-1}).$

By induction, it follows that

$\prod_{h\in[H]}\mathrm{det}({\bm{H}}_{h,k_{|{\mathcal{K}}|}-1})\geq
2^{|{\mathcal{K}}|}\prod_{h\in[H]}\mathrm{det}({\bm{H}}_{h,k_{1}-1})\geq
2^{|{\mathcal{K}}|}\prod_{h\in[H]}\mathrm{det}(\lambda{\bm{I}})=2^{|{\mathcal{K}}|}\lambda^{dH}$

On the other hand, due to
${\bm{H}}_{h,k_{|{\mathcal{K}}|}-1}\preceq{\bm{H}}_{h,K}$ the determinant
$\mathrm{det}({\bm{H}}_{h,k_{|{\mathcal{K}}|}-1}$ is upper bounded by

$\prod_{h\in[H]}\mathrm{det}({\bm{H}}_{h,k_{|{\mathcal{K}}|}-1})\leq\prod_{h\in[H]}\mathrm{det}({\bm{H}}_{h,K})\leq\left(\lambda+\frac{K}{\sigma_{\min}^{2}}\right)^{dH}.$

Combining the last two inequalities, we have

$|{\mathcal{K}}|\leq
dH\log_{2}\left(1+\frac{K}{\lambda\sigma_{\min}^{2}}\right).$

∎

The optimistic value function $\overline{V}_{h}^{k}(\cdot)=\min_{k_{i}\leq
k}\max_{a}\overline{Q}_{h}^{k_{i}}(\cdot,a)$ belong to the function class
${\mathcal{V}}^{+}$

${\mathcal{V}}^{+}=\left\\{f|f(\cdot)=\max_{a\in{\mathcal{A}}}\min_{i\leq|{\mathcal{K}}|}\min\left\\{{\bm{w}}_{i}^{\top}{\bm{\phi}}(\cdot,a)+\beta\|{\bm{\phi}}(\cdot,a)\|_{{\bm{H}}_{i}^{-1}},{\mathcal{H}}\right\\},\beta\in[0,B],\|{\bm{w}}_{i}\|\leq
L,{\bm{H}}_{i}\succeq\lambda{\bm{I}}\right\\}.$ (F.1)

while the pessimistic value function
$\underline{V}_{h}^{k}(\cdot)=\max_{k_{i}\leq
k}\max_{a}\underline{Q}_{h}^{k_{i}}(\cdot,a)$ belong to the function class
${\mathcal{V}}^{-}$,

${\mathcal{V}}^{-}=\left\\{f|f(\cdot)=\max_{a\in{\mathcal{A}}}\max_{i\leq|{\mathcal{K}}|}\max\left\\{{\bm{w}}_{i}^{\top}{\bm{\phi}}(\cdot,a)-\beta\|{\bm{\phi}}(\cdot,a)\|_{{\bm{H}}_{i}^{-1}},{\mathcal{H}}\right\\},\beta\in[0,B],\|{\bm{w}}_{i}\|\leq
L,{\bm{H}}_{i}\succeq\lambda{\bm{I}}\right\\}.$ (F.2)

Here $B$ upper bounds $\beta$ and $L=W+{\mathcal{H}}\sqrt{\frac{dK}{\lambda}}$
is a uniformly bound for
${{\bm{\theta}}}_{h,k-1}+{\bm{\mu}}_{h,k-1}\overline{{\bm{V}}}_{h+1}^{k}$
because

$\|{{\bm{\theta}}}_{h,k-1}+{\bm{\mu}}_{h,k-1}\overline{{\bm{V}}}_{h+1}^{k}\|\leq\|{{\bm{\theta}}}_{h,k-1}\|+\|{\bm{\mu}}_{h,k-1}\overline{{\bm{V}}}_{h+1}^{k}\|\leq
W+{\mathcal{H}}\sqrt{\frac{dK}{\lambda}}$

where the last inequality uses the boundedness of ${\bm{\theta}}_{h,k-1}$’s
and the inequality
$\|{\bm{\mu}}_{h,k-1}\overline{{\bm{V}}}_{h+1}^{k}\|\leq{\mathcal{H}}\sqrt{\frac{dK}{\lambda}}$
(whose proof can be found in Lemma E.2 of He et al. [2022]).

######  Lemma F.8 (Covering number of value functions).

Let ${\mathcal{V}}^{\pm}$ denote the class of optimistic or pessimistic value
functions with definition in (F.1) and (F.2) respectively. Assume
$\|{\bm{\phi}}(s,a)\|\leq 1$ for all $(s,a)$ pairs, and let
${\mathcal{N}}({\mathcal{V}},\varepsilon)$ be the $\varepsilon$-covering
number of ${\mathcal{V}}$ with respective to the distance
$\mathrm{dist}(f,f^{\prime}):=\sup_{s\in{\mathcal{S}}}|f(s)-f^{\prime}(s)|$.
Then,

$\log{\mathcal{N}}({\mathcal{V}}^{\pm},\varepsilon)\leq\left[d\log\left(1+\frac{4L}{\varepsilon}\right)+d^{2}\log\left(1+\frac{8d^{1/2}B^{2}}{\lambda\varepsilon^{2}}\right)\right]\cdot|{\mathcal{K}}|.$

###### Proof of Lemma F.8.

The result about ${\mathcal{V}}_{f}^{+}$ follows from Lemma E.6 in [He et al.,
2022]. The result about ${\mathcal{V}}_{f}^{-}$ follows from Lemma E.7 in [He
et al., 2022]. ∎

######  Lemma F.9 (Covering number of squared functions, Lemma E.8 in [He et
al., 2022]).

For the squared function class
$[{\mathcal{V}}^{+}]^{2}:=\left\\{f^{2}|f\in{\mathcal{V}}^{+}\right\\}$, let
${\mathcal{N}}([{\mathcal{V}}^{+}]^{2},\varepsilon)$ be the
$\varepsilon$-covering number of $[{\mathcal{V}}^{+}]^{2}$ with respective to
the distance
$\mathrm{dist}(f,f^{\prime}):=\sup_{s\in{\mathcal{S}}}|f(s)-f^{\prime}(s)|$.
Then

$\log{\mathcal{N}}([{\mathcal{V}}^{+}]^{2},\varepsilon)\leq\left[d\log\left(1+\frac{8HL}{\varepsilon}\right)+d^{2}\log\left(1+\frac{32d^{1/2}H^{2}B^{2}}{\lambda\varepsilon^{2}}\right)\right]\cdot|{\mathcal{K}}|.$