# Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning
with General Function Approximation

Jiayi Huang Peking University. Email<EMAIL_ADDRESS>Han Zhong Peking
University. Email<EMAIL_ADDRESS>Liwei Wang Peking University.
Email<EMAIL_ADDRESS>Lin F. Yang University of California, Los
Angles. Email<EMAIL_ADDRESS>
###### Abstract

To tackle long planning horizon problems in reinforcement learning with
general function approximation, we propose the first algorithm, termed as
UCRL-WVTR, that achieves both _horizon-free_ and _instance-dependent_ , since
it eliminates the polynomial dependency on the planning horizon. The derived
regret bound is deemed _sharp_ , as it matches the minimax lower bound when
specialized to linear mixture MDPs up to logarithmic factors. Furthermore,
UCRL-WVTR is _computationally efficient_ with access to a regression oracle.
The achievement of such a horizon-free, instance-dependent, and sharp regret
bound hinges upon (i) novel algorithm designs: weighted value-targeted
regression and a high-order moment estimator in the context of general
function approximation; and (ii) fine-grained analyses: a novel concentration
bound of weighted non-linear least squares and a refined analysis which leads
to the tight instance-dependent bound. We also conduct comprehensive
experiments to corroborate our theoretical findings.

##  1 Introduction

Reinforcement Learning (RL) plays a pivotal role in solving complex decision-
making problems, where an agent interacts with the environment to learn a
policy that maximizes cumulative rewards. In the context of time-homogeneous
episodic RL, where the total rewards are bounded by $1$, an open question
arises concerning whether episodic RL is more difficult than bandits problems
(Jiang and Agarwal, 2018). While numerous research endeavors have been
dedicated to the development of algorithms with up to poly-logarithmic
dependence on the planning horizon, thus are _horizon-free_ , these efforts
are restricted to either tabular (Wang et al., 2020a; Zhang et al., 2021a; Li
et al., 2022; Zhang et al., 2022) or linear mixture Markov Decision Processes
(MDPs) (Zhang et al., 2021b; Kim et al., 2022; Zhou and Gu, 2022; Zhao et al.,
2023). Consequently, this open question persists as a formidable challenge,
necessitating further exploration and innovation to address a broader family
of RL problems.

The difficulty of solving RL problems is intrinsically related to complexity
of the underlying model. For instance, the performance of an RL algorithm
typically improves when the stochasticity in unknown transition kernel is
diminished. This observation motivated many works to design algorithms that
achieve _instance-dependent_ regret bounds (Zanette and Brunskill, 2019; Zhou
et al., 2023; Zhao et al., 2023). These bounds depend on fine-grained,
problem-specific quantities, thus providing tighter guarantees than worst-case
regret bounds. Nevertheless, existing research for RL with general function
approximation has primarily focused on minimizing regret in the worst-case
scenario (Ayoub et al., 2020; Foster et al., 2023; Agarwal et al., 2023),
thereby leaving an instance-dependent guarantee still challenging in this
domain.

Thus, a natural question arises:

_Is efficient, horizon-free and instance-dependent learning possible
in RL with general function approximation?_

In this work, we give an affirmative answer to this question by proposing an
algorithm, termed as UCRL-WVTR, for RL with general function approximation.
UCRL-WVTR enjoys an
$\widetilde{O}(\sqrt{\dim_{\mathcal{F}}\log\mathcal{N}_{\mathcal{F}}}\cdot\sqrt{\mathcal{Q}^{*}}+\dim_{\mathcal{F}}\log\mathcal{N}_{\mathcal{F}})$
regret, where $\dim_{\mathcal{F}}$ and $\log\mathcal{N}_{\mathcal{F}}$
respectively denote the generalized Eluder dimension and log-covering number
of the function class $\mathcal{F}$, and $\mathcal{Q}^{*}$ is an instance-
dependent quantity defined in Theorem 4.2. The generalized Eluder dimension is
an extension of Eluder dimension (Russo and Van Roy, 2013) tailored to the
context of weighted regression settings. The derived instance-dependent regret
bound exhibits a log-polynomial dependence on the planning horizon $H$.
Therefore, we simultaneously achieve the best of both worlds: horizon-free and
instance-dependent. For more detailed insights and explanations, we refer
readers to Section 4. The main theoretical contributions of this paper are
summarized as follows:

  * •

Our algorithm utilizes the Value-Targeted Regression (VTR) framework proposed
by Ayoub et al. (2020), which was devised for estimating the unknown
transition kernel. Our refinement of this framework includes a weighted
design, which assigns higher importance to data points with low variance and
uncertainty. Additionally, we adopt a high-order moment estimator to achieve
more accurate estimations of variances. This improved algorithmic design plays
a pivotal role in producing an accurate model estimate. Based on the estimated
model, we further implement an efficient planning approach via a regression
oracle for general function approximation, thus achieving computational
efficiency.

  * •

To theoretically characterize the deviation of the estimated model, we propose
a novel Bernstein-style concentration bound for weighted non-linear regression
and rigorously establish its tightness. This result provides insights for
assigning weights to be both variance-aware and uncertainty-aware in our
algorithm. Despite the inherent complexities posed by the non-linear function
class, we have successfully conducted a refined analysis, resulting in a
regret bound that simultaneously achieves horizon-free and instance-dependent.

  * •

As a special case, our algorithm achieves a first-order regret scaling as
$\widetilde{O}(d\sqrt{V^{*}_{1}K}+d^{2})$ for linear mixture MDPs, where the
transition kernel admits a linear combination of some basis transition models.
This regret bound is sharp since it is reduced to
$\widetilde{O}(d\sqrt{K}+d^{2})$ in the worst case, matching the lower bound
$\Omega(d\sqrt{K})$ (Zhou et al., 2021) when $K\geq d^{2}$ up to logarithmic
factors. Considering this emerges as a direct consequence of a broader result,
it shows that our novel algorithm designs and fine-grained analyses indeed
handle the general RL problems in a sharp manner.

#### Road Map

The rest of this paper is organized as follows. Section 2 provides works that
are closely related to ours. Section 3 introduces the formal definition of RL
with general function approximation. Section 4 states our main theoretical
results. Section 5 presents the experimental results that corroborate our
theoretical findings. We then make conclusions in Section 6. Additional
experiments and detailed theoretical analyses are left in the Appendix.

#### Notations

Let $[n]:=\\{1,2,\dots,n\\}$. Let $\overline{[n]}:=\\{0,1,\dots,n\\}$. For a
collection of elements $\\{X_{t}\\}_{t\geq 1}$, let
$X_{[t]}:=\\{X_{1},\dots,X_{t}\\}$. Denote the $\epsilon$-covering number of
$\mathcal{F}$ w.r.t. $\ell_{\infty}$-norm as
$\mathcal{N}_{\mathcal{F}}(\epsilon)$.

##  2 Related Work

#### Horizon-Free Regret in RL

Jiang and Agarwal (2018) raised an open question regarding the comparative
difficulty of RL in comparison to bandit problems. Specifically, in the
context of time-homogeneous tabular RL and assuming an upper bound of $1$ on
total rewards, they posited that any algorithm seeking to find an
$\epsilon$-optimal policy would need to exhibit a polynomial dependence on the
planning horizon $H$ in the sample complexity. This conjecture has been
challenged by a line of works that have introduced algorithms capable of
achieving horizon-free regret bounds (Wang et al., 2020a; Zhang et al., 2021a;
Li et al., 2022; Zhang et al., 2022). Additionally, a series recent studies
(Zhang et al., 2021b; Kim et al., 2022; Zhou and Gu, 2022; Zhao et al., 2023)
further extended horizon-free learning to linear mixture MDPs. It is
noteworthy that these aforementioned studies are based on the assumption of
either a finite state space or the linear representation of transition
probabilities. Regrettably, such assumptions are often less practical to align
with real-world scenarios.

#### Instance-Dependent Regret in RL

In recent years, there has been a substantial body of research dedicated to
the developingment of algorithms with instance-dependent regret bounds,
therefore providing tighter guarantee than traditional worst-case regret
(Zanette and Brunskill, 2019; Zhou et al., 2023; Wagenmaker et al., 2022; Li
and Sun, 2023; Huang et al., 2023; Zhao et al., 2023). Notably, Zhao et al.
(2023) introduced a variance-adaptive algorithm with a horizon-free and
variance-aware regret bound, but constrained to linear mixture MDPs. To our
best knowledge, hardly few works have explored the concept of instance-
dependent regret in RL with general function approximation. The exception to
this is Wagenmaker and Foster (2023), which developed a non-asymptotic theory
of instance-optimal RL with general function approximation. However, despite
theoretical advancements, their algorithm falls short of practicality since it
deviates significantly from minimax optimality and computational efficiency.

#### RL with General Function Approximation

We study model-based RL with general function approximation, where the agent
learns and employs an explicit model of the environment for planning and
decision-making. This area has witnessed a substantial surge of research
(Osband and Van Roy, 2014; Sun et al., 2019; Ayoub et al., 2020; Wang et al.,
2020b; Foster et al., 2021; Chen et al., 2022b, a; Zhong et al., 2022; Foster
et al., 2023; Wagenmaker and Foster, 2023). Notably, Ayoub et al. (2020) stand
as the closest precursor to our work. They adopted a novel VTR approach, which
evaluates models based on their ability to predict values at the next states.
This VTR framework was subsequently extended and refined, culminating in the
attainment of horizon-free regrets when applied to linear mixture MDPs (Zhou
and Gu, 2022). Concurrently, there exists a separate line of works
concentrated on model-free RL (Jiang et al., 2017; Wang et al., 2020b; Du et
al., 2021; Jin et al., 2021; Kong et al., 2021; Dann et al., 2021; Zhong et
al., 2022; Liu et al., 2023; Agarwal et al., 2023), where the agent directly
learns policies or value functions for decision-making based on their
interactions with the environment. However, it is worth noting that the
algorithms mentioned above either suffer from polynomial dependence on the
planning horizon $H$ or fail to provide a fine-grained instance-dependent
regret guarantee. Our work achieves the best of both worlds for the first time
in RL with general function approximation.

##  3 Preliminaries

#### MDPs with General Function Approximation

We study time-homogeneous episodic MDPs, which can be described by a tuple
$M=(\mathcal{S},\mathcal{A},H,\mathbb{P},\\{r_{h}\\}_{h\in[H]})$. Here,
$\mathcal{S}$ and $\mathcal{A}$ are state space and action space,
respectively, $H$ is the length of planning horizon,
$\mathbb{P}:\mathcal{S}\times\mathcal{A}\to\Delta(\mathcal{S})$ is the
transition dynamics, $r_{h}:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$ is the
$h$-th step deterministic reward function known to the agents111Our result can
be generalized to the unknown-reward cases since learning transition dynamics
is more challenging than learning rewards.. We consider the bounded reward
setting that $\sum_{h=1}^{H}r_{h}(s_{h},a_{h})\leq 1$ for any trajectory
$\\{s_{1},a_{1},\dots,s_{H},a_{H}\\}$. We consider deterministic policy
throughout this paper. A deterministic policy
$\pi=\\{\pi_{h}:\mathcal{S}\to\mathcal{A}\\}_{h\in[H]}$ is a collection of $H$
mappings from state space to action space. For any state-action pair
$(s,a)\in\mathcal{S}\times\mathcal{A}$, we define the action value function
$Q^{\pi}_{h}(s,a)$ and (state) value function $V^{\pi}_{h}(s)$ as follows:

$\displaystyle
Q^{\pi}_{h}(s,a):=\mathbb{E}\Big{[}\sum_{h^{\prime}=h}^{H}r(s_{h^{\prime}},a_{h^{\prime}})\Big{|}s_{h}=s,a_{h}=a\Big{]},\quad
V^{\pi}_{h}(s):=Q^{\pi}_{h}(s,\pi_{h}(s)),$

where the expectation is taken with respect to the transition kernel
$\mathbb{P}$ and the agent’s policy $\pi$. Denote
$V^{*}_{h}(s):=\sup_{\pi}V^{\pi}_{h}(s)$ and
$Q^{*}_{h}(s,a):=\sup_{\pi}Q^{\pi}_{h}(s,a)$ as the optimal value functions.
We introduce the following shorthands for simplicity. At the $h$-th step, for
any value function $V:\mathcal{S}\to\mathbb{R}$, denote

$\displaystyle[\mathbb{P}V](s,a):=\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}[V(s^{\prime})],\quad[\mathbb{V}V](s,a):=[\mathbb{P}V^{2}](s,a)-[\mathbb{P}V]^{2}(s,a)$

as the conditional expectation and variance of $V$, respectively. We aim to
design efficient algorithms for minimizing the $K$-episode regret defined as

$\mathrm{Regret}(K):=\sum_{k=1}^{K}[V^{*}_{1}(s^{k}_{1})-V^{\pi^{k}}_{1}(s^{k}_{1})].$

To tackle problems with large state spaces, we consider MDPs with general
function approximation.

######  Assumption 3.1 (MDPs with general function approximation).

Let $\mathcal{P}$ be a general function class composed of transition kernels
mapping state-action pairs to measures over $\mathcal{S}$. We assume the
transition model $\mathbb{P}$ of the MDP satisfies $\mathbb{P}\in\mathcal{P}$.

To characterize the complexity of the model class $\mathcal{P}$, we further
introduce the function class

$\displaystyle\mathcal{F}:=\\{f:\mathcal{S}\times\mathcal{A}\times\mathcal{V}\to\mathbb{R}\text{
such that }\exists\mathbb{P}\in\mathcal{P},f(s,a,V)=[\mathbb{P}V](s,a)\text{
for any }V\in\mathcal{V}\\},$

where $\mathcal{V}$ encompasses all value functions $V$ such that
$V:\mathcal{S}\to[0,1]$. As is demonstrated by Ayoub et al. (2020), a
bijection denoted as $\phi:\mathcal{P}\rightarrow\mathcal{F}$ exists,
establishing a direct correspondence between $\mathcal{P}$ and $\mathcal{F}$,
such that for any $\mathbb{P}\in\mathcal{P}$, there exists a corresponding
$f=\phi(\mathbb{P})\in\mathcal{F}$ with $f(s,a,V)=[\mathbb{P}V](s,a)$. For
brevity, we denote $f_{\mathbb{P}}:=\phi(\mathbb{P})$. Additionally, we assume
for any $(s,a,V)\in\mathcal{S}\times\mathcal{A}\times\mathcal{V}$,
$f_{\mathbb{P}}(s,a,V)=\sum_{s^{\prime}\in\mathcal{S}}V(s^{\prime})\mathbb{P}(s^{\prime}|s,a)$
can be efficiently evaluated within $\mathcal{O}$ time. Such an assumption
depends on the intrinsic property of the model class and it holds true for
many MDP models. See Ayoub et al. (2020) for more discussions. We use the
covering number and generalized Eluder dimension introduced later to gauge the
complexity of $\mathcal{F}$.

#### Generalized Eluder Dimension

Inspired by Agarwal et al. (2023), we use generalized Eluder dimension as a
complexity measurement for the generalization property of the function class
$\mathcal{F}$. Generalized Eluder dimension is an extension of the Eluder
dimension defined in Russo and Van Roy (2013) to weighted regression settings.
Intuitively, it can be thought of Eluder dimension of a scaling-enlarged
function set.

######  Definition 3.2 (Generalized Eluder dimension).

Let $\lambda>0$, a sequence of random elements $\bm{X}=\\{X_{t}\\}_{t\in[T]}$
and $\bm{\sigma}=\\{\sigma_{t}\\}_{t\in[T]}$ be given. The _generalized Eluder
dimension_ of a function class $\mathcal{F}$ consisting of function
$f:\mathcal{X}\to\mathbb{R}$ is given by

$\displaystyle\dim_{\mathcal{F}}(\sigma_{\mathrm{min}},T):=\sup_{\bm{X},\bm{\sigma}:|\bm{X}|=T,\bm{\sigma}\geq\sigma_{\mathrm{min}}}\sum_{t=1}^{T}\min\left(1,\frac{1}{\sigma_{t}^{2}}D_{\mathcal{F}}^{2}(X_{t};X_{[t-1]},\sigma_{[t-1]})\right),$

where uncertainty $D_{\mathcal{F}}$ is defined by

$\displaystyle
D^{2}_{\mathcal{F}}(X_{t};X_{[t-1]},\sigma_{[t-1]}):=\sup_{f_{1},f_{2}\in\mathcal{F}}\frac{\left(f_{1}(X_{t})-f_{2}(X_{t})\right)^{2}}{\sum_{s=1}^{t-1}\frac{1}{\sigma_{s}^{2}}\left(f_{1}(X_{s})-f_{2}(X_{s})\right)^{2}+\lambda}.$

We also use the notation
$\dim_{\mathcal{F}}:=\dim_{\mathcal{F}}(\sigma_{\mathrm{min}},T)$ when
$\sigma_{\mathrm{min}}$ and $T$ are clear from the context.

######  Remark 3.3.

We remark that the notion of generalized Eluder dimension is initially
introduced by Agarwal et al. (2023), with a primary focus on time-
inhomogeneous MDPs under model-free settings. Furthermore, they require value
closedness222The Bellman projection of any value function lies in the target
function class. (Wang et al., 2020b; Kong et al., 2021). In contrast, we study
time-homogenous MDPs under model-based settings, where we do not need
completeness-type assumptions. More importantly, our work endeavors to pursue
horizon-free learning in the context of general functions, whereas their work
only obtains a near-optimal regret bound with a polynomial dependency on the
planning horizon $H$.

#### Linear Mixture MDPs

We also consider linear mixture MDPs (Modi et al., 2020; Jia et al., 2020;
Ayoub et al., 2020), which is a special case where the transition kernel
admits a linear representation.

######  Assumption 3.4 (Linear mixture MDPs).

There exists an unknown vector $\bm{\theta}^{*}\in\mathbb{R}^{d}$ and a known
feature $\bm{\phi}(\cdot|\cdot,\cdot)\in\mathbb{R}^{d}$ such that

$\mathbb{P}(s^{\prime}|s,a)=\langle\bm{\phi}(s^{\prime}|s,a),\bm{\theta}^{*}\rangle$

for any $(s,a,s^{\prime})\in\mathcal{S}\times\mathcal{A}\times\mathcal{S}$.
Meanwhile, we assume that $\|\bm{\theta}^{*}\|_{2}\leq B$ and
$\|\bm{\phi}_{V}(s,a)\|_{2}\leq 1$ for any bounded value function
$V:\mathcal{S}\to[0,1]$ and any state-action pair
$(s,a)\in\mathcal{S}\times\mathcal{A}$, where

$\displaystyle\bm{\phi}_{V}(s,a):=\sum_{s^{\prime}\in\mathcal{S}}\bm{\phi}(s^{\prime}|s,a)V(s^{\prime}).$

The generalized Eluder dimension and log-covering number of linear mixture
MDPs can be simplified.

######  Proposition 3.5.

For $d$-dimensional, $B$-bounded linear mixture MDPs defined in Assumption
3.4, the generalized Eluder dimension and log-covering number satisfies

$\displaystyle\dim_{\mathcal{F}}(\sigma_{\mathrm{min}},T)=O(d\log(1+TB/(d\lambda\sigma_{\mathrm{min}}^{2})),\quad\log\mathcal{N}_{\mathcal{F}}(\epsilon)=\Theta(d\log(B/\epsilon)).$

###### Proof.

See Appendix D.1 for a detailed proof. ∎

##  4 Main Results

In this section, we propose a new algorithm UCRL-WVTR for MDPs with general
function approximation, as detailed in Algorithm 1. We first give the high-
level idea, then analyze the computational complexity and regret bound.

Algorithm 1 UCRL-WVTR

0: $\lambda$, confidence radius $\\{\widehat{\beta}_{k}\\}_{k\geq 1}$, level
$M$, variance parameters $\sigma_{\mathrm{min}},\gamma$

1: For $m\in\overline{[M]}$, $\widehat{f}_{1,m}\leftarrow 0$,
$D_{1,m},D_{1,0,m}\leftarrow\varnothing$

2: for $k=1,\ldots,K$ do

3: $V_{k,H+1}(\cdot)=0$

4: for $h=H,\dots,1$ do

5:
$Q_{k,h}(\cdot,\cdot)\leftarrow\min\\{r_{h}(\cdot,\cdot)+\widehat{f}_{k,0}(\cdot,\cdot,V_{k,h+1})+\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(\cdot,\cdot,V_{k,h+1};D_{k,0}),1\\}$

6: $V_{k,h}(\cdot)=\max_{a\in\mathcal{A}}Q_{k,h}(\cdot,a)$,
$\pi^{k}_{h}(\cdot)=\mathop{\mathrm{argmax}}_{a\in\mathcal{A}}Q_{k,h}(\cdot,a)$

7: end for

8: Receive $s^{k}_{1}$

9: for $h=1,\dots,H$ do

10: Take action $a_{h}^{k}\leftarrow\pi_{h}^{k}(s_{h}^{k})$, receive
$s_{h+1}^{k}$

11: For $m\in\overline{[M]}$,
$z_{k,h,m}\leftarrow(s^{k}_{h},a^{k}_{h},V_{k,h+1}^{2^{m}})$,
$y_{k,h,m}\leftarrow V_{k,h+1}^{2^{m}}(s^{k}_{h+1})$

12:
$\\{\bar{\sigma}_{k,h,m}\\}_{m\in\overline{[M]}}\leftarrow\text{HOME}(\\{z_{k,h,m},\widehat{f}_{k,m}$,
$D_{k,h-1,m},D_{k,m}\\}_{m\in\overline{[M]}},\widehat{\beta}_{k},\sigma_{\mathrm{min}},\gamma$)

13: For $m\in\overline{[M]}$, $D_{k,h,m}\leftarrow
D_{k,h-1,m}\cup\\{z_{k,h,m},\bar{\sigma}_{k,h,m}\\}$

14: end for

15: For $m\in\overline{[M]}$, $D_{k+1,m},D_{k+1,0,m}\leftarrow D_{k,H,m}$

16: For $m\in\overline{[M]}$,
$\widehat{f}_{k+1,m}\leftarrow\mathop{\mathrm{argmin}}_{f\in\mathcal{F}}$
$\sum_{i=1}^{k}\sum_{h=1}^{H}\frac{1}{\bar{\sigma}_{i,h}^{2}}(f(z_{i,h,m})-y_{i,h,m})^{2}$

17: end for

Algorithm 2 HOME

0:
$\\{z_{k,h,m},\widehat{f}_{k,m},D_{k,h-1,m},D_{k,m}\\}_{m\in\overline{[M]}}$,
$\widehat{\beta}_{k}$, $\sigma_{\mathrm{min}},\gamma$

0: $\\{\bar{\sigma}_{k,h,m}\\}_{m\in\overline{[M]}}$

1: for $m=0,\dots,M-1$ do

2:
$[\bar{\mathbb{V}}_{k,m}V_{k,h+1}^{2^{m}}](s_{h}^{k},a_{h}^{k})\leftarrow\widehat{f}_{k,m+1}(z_{k,h,m+1})-\widehat{f}_{k,m}^{2}(z_{k,h,m})$

3:
$E_{k,h,m}\leftarrow\min\\{1,2\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(z_{k,h,m+1};D_{k,m+1})\\}+\min\\{1,\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(z_{k,h,m};D_{k,m})\\}$

4:
$\bar{\sigma}_{k,h,m}^{2}\leftarrow\max\\{[\bar{\mathbb{V}}_{k,m}V_{k,h+1}^{2^{m}}](s_{h}^{k},a_{h}^{k})+E_{k,h,m},\sigma_{\mathrm{min}}^{2},\gamma^{2}\mathcal{D}_{\mathcal{F}}(z_{k,h,m};D_{k,h-1,m})\\}$

5: end for

6:
$\bar{\sigma}_{k,h,M}^{2}\leftarrow\max\\{1,\sigma_{\mathrm{min}}^{2},\gamma^{2}\mathcal{D}_{\mathcal{F}}(z_{k,h,M};D_{k,h-1,M})\\}$

###  4.1 Algorithm Description

UCRL-WVTR capitalizes on the VTR methodology, which draws inspiration from
UCRL-VTR presented by Ayoub et al. (2020) on estimating transition dynamics.
Furthermore, we employ _weighted_ least squares regression to mitigate sub-
optimality resulting from heterogeneous noise levels, specifically,
differences in variances at each stage. Additionally, we utilize a high-order
moment estimator for accurately estimating variances of the next-state value
functions motivated by Zhang et al. (2021b); Zhou and Gu (2022). We highlight
the primary enhancements of UCRL-WVTR in comparison to UCRL-VTR as follows:

#### Weighted VTR

UCRL-WVTR utilizes a weighted value-targeted regression framework, where the
weights are chosen to take advantage of a novel concentration inequality, as
articulated in Theorem 4.4. Under the guidance of this inequality, at the end
of the $k$-th episode, we estimate the ground truth model
$f_{*}=f_{\mathbb{P}}$ as the solution of weighted least squares

$\widehat{f}_{k+1,0}=\mathop{\mathrm{argmin}}_{f\in\mathcal{F}}\sum_{i=1}^{k}\sum_{h=1}^{H}\frac{1}{\bar{\sigma}_{i,h,0}^{2}}(f(z_{i,h,0})-V_{i,h+1}(s^{i}_{h+1}))^{2}.$

Here, $z_{i,h,0}$ is defined in Line 11 of Algorithm 1. And
$\bar{\sigma}_{i,h,0}^{2}$ is an upper bound for both the conditional variance
of $V_{i,h+1}(s^{i}_{h+1})$ and the uncertainty of $z_{i,h,0}$, defined as
follows:

$\displaystyle\bar{\sigma}_{k,h,0}^{2}=\max\\{[\bar{\mathbb{V}}_{k,0}V_{k,h+1}](s_{h}^{k},a_{h}^{k})+E_{k,h,0},\sigma_{\mathrm{min}}^{2},\gamma^{2}\mathcal{D}_{\mathcal{F}}(z_{k,h,0};D_{k,h-1,0})\\},$

where $[\bar{\mathbb{V}}_{k,0}V_{k,h+1}](s_{h}^{k},a_{h}^{k})$ is the estimate
of $[\mathbb{V}V_{k,h+1}](s_{h}^{k},a_{h}^{k})$, $E_{k,h,0}$ is the error
bound specified in Line 3 of Algorithm 2 that satisfies

$[\bar{\mathbb{V}}_{k,0}V_{k,h+1}](s_{h}^{k},a_{h}^{k})+E_{k,h,0}\geq[\mathbb{V}V_{k,h+1}](s_{h}^{k},a_{h}^{k})$

with high probability, $\sigma_{\mathrm{min}}$ is a small positive constant to
avoid numerical instability, $\gamma$ is a positive constant to be chosen, and
$\mathcal{D}_{\mathcal{F}}(z_{k,h,0};D_{k,h-1,0})$ in Definition 3.2 is the
uncertainty of $z_{k,h,0}$. Then we discuss how to estimate the conditional
variance of $V_{k,h+1}(s_{h+1}^{k})$. Since

$[\mathbb{V}V_{k,h+1}](s_{h}^{k},a_{h}^{k})=[\mathbb{P}V_{k,h+1}^{2}](s_{h}^{k},a_{h}^{k})-[\mathbb{P}V_{k,h+1}]^{2}(s_{h}^{k},a_{h}^{k}),$

we estimate it by $[\bar{\mathbb{V}}_{k,0}V_{k,h+1}](s_{h}^{k},a_{h}^{k})$
defined as

$[\bar{\mathbb{V}}_{k,0}V_{k,h+1}](s_{h}^{k},a_{h}^{k})=\widehat{f}_{k,1}(z_{k,h,1})-\widehat{f}_{k,0}^{2}(z_{k,h,0}),$

where $z_{i,h,1}$ is defined in Line 11 of Algorithm 1 and $\widehat{f}_{k,1}$
will be specified later.

#### Efficient Planning via Point-Wise Bonus Terms

Once obtaining the estimate $\widehat{f}_{k,0}$, we construct action value
functions $\\{Q_{k,h}\\}_{h\in[H]}$ following the Upper Confidence Bound (UCB)
scheme (Azar et al., 2017). More specifically, starting from step $H$ and
proceeding to step $1$, UCRL-WVTR estimates the upper bound of the optimal
value function at each step in a point-wise manner, then takes actions
optimistically:

$\displaystyle
Q_{k,h}(s,a)=r_{h}(s,a)+\widehat{f}_{k,0}(s,a,V_{k,h+1})+\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(s,a,V_{k,h+1};D_{k,0}),$

Here $\widehat{\beta}_{k}=\widetilde{O}(\sqrt{\log\mathcal{N}_{\mathcal{F}}})$
according to Theorem 4.4. However, it is worth noting that in the realm of
non-linear functions, uncertainty $\mathcal{D}_{\mathcal{F}}$ generally lacks
an analytical expression, impeding the computational efficiency of our
algorithm. To address such a challenge, we employ a technique to efficiently
compute uncertainty $\mathcal{D}_{\mathcal{F}}$ via a regression oracle, as
explained later. In contrast, Ayoub et al. (2020) construct value functions
through optimistic planning, which is generally computationally intractable.

#### High-Order Moment Estimator

We utilize the high-order moment estimator in Algorithm 2 to achieve enhanced
precision in estimating the ground truth model $f_{*}$. As previously
discussed, the estimate $\widehat{f}_{k,0}$ necessitates weights
$\bar{\sigma}_{k,h,0}$, which relies on $\widehat{f}_{k,1}$ for estimating
variance of $V_{k,h+1}$. And $\widehat{f}_{k,1}$ can be derived by weighted
least squares with predictors $z_{i,h,1}$, weights $\bar{\sigma}_{i,h,1}$ and
targets $V_{i,h+1}^{2}(s^{i}_{h+1})$. Here $\bar{\sigma}_{k,h,1}$ are in a
similar manner as $\bar{\sigma}_{k,h,0}$, depending on the variance of
$V_{k,h+1}^{2}$. Recursively, we estimate variance of $V_{k,h+1}^{2^{m}}$,
which is the conditional $2^{m+1}$-th central moment of $V_{k,h+1}$ until
$m=M$, where $M$ is chosen to meet the desired level of precision. Last,
variance of $V_{k,h+1}^{2^{M}}$ is estimated with its upper bound $1$. It is
worth noting that this higher-order moment estimator has been previously
utilized in research dedicated to horizon-free learning. However, these works
focused on either tabular (Zhang et al., 2021a, 2022) or linear mixture MDPs
(Zhang et al., 2021b; Zhou and Gu, 2022), while we study general function
approximation.

###  4.2 Computational Complexity

Due to the non-linear nature of the function class $\mathcal{F}$, closed-form
solutions of weighted least squares $\widehat{f}_{k,m}$ in Line 16 and
uncertainty $\mathcal{D}_{\mathcal{F}}$ in Definition 3.2 are not readily
attainable. To assess the computational efficiency of our proposed algorithm
in such a context, we turn to the concept of oracle complexity (Wang et al.,
2020b; Kong et al., 2021), which measures the number of calls to some
optimization oracles.

#### Regression Oracle

We introduce the regression oracle in Assumption 4.1 for solving the weighted
non-linear least squares regression. Inspired by Kong et al. (2021), we
leverage this oracle to compute uncertainty $\mathcal{D}_{\mathcal{F}}$
through a binary search procedure. As detailed in Appendix B, we demonstrate
that this quantity can be estimated efficiently with a mere $\widetilde{O}(1)$
number of calls to the regression oracle.

######  Assumption 4.1 (Regression oracle).

We assume access to a weighted least squares _regression oracle_ , which takes
a function class $\mathcal{G}$ consisting of function
$g:\mathcal{X}\to\mathbb{R}$ and a $t$-sized of weighted examples
$\\{(X_{s},v_{s},Y_{s})\\}_{s\in[t]}\subset\mathcal{X}\times\mathbb{R}^{+}\times\mathbb{R}$
as input, and outputs the solution of weighted least squares $\widehat{g}$
within $\mathcal{R}$ time, where $\widehat{g}$ is defined as

$\widehat{g}=\mathop{\mathrm{argmin}}_{g\in\mathcal{G}}\sum_{s=1}^{t}v_{s}(g(X_{s})-Y_{s})^{2}.$

The availability of a regression oracle is a reasonably mild assumption, which
appeared in many works concerning general function approximation
(Krishnamurthy et al., 2017; Foster et al., 2018; Kong et al., 2021; Agarwal
et al., 2023). It is noteworthy that this regression oracle admits an
analytical solution under linear mixture models (Ayoub et al., 2020). In more
general scenarios, when the function class $\mathcal{F}$ is characterized as a
collection of differentiable functions, such as neural networks, the
implementation of the regression oracle becomes feasible and computationally
efficient through the utilization of gradient-based optimization algorithms
(Bubeck et al., 2015).

#### Computational Complexity of UCRL-WVTR

Recall that $\mathcal{O}$ denotes the evaluation time of any function
$f\in\mathcal{F}$ and $\mathcal{R}$ represents the computational cost of the
regression oracle. We consider the computation cost of the $k$-th episode and
the $h$-th step. First, it takes $\widetilde{O}(\mathcal{O}+\mathcal{R})$ time
to compute the action value function $Q_{k,h}$ in Line 5 for a given state-
action pair $(s,a)$, since it requires the evaluation of $\widehat{f}_{k,0}$
and the computation of $\mathcal{D}_{\mathcal{F}}$. Then, to take actions
based on $\pi^{k}_{h}$, UCRL-WVTR needs to compute the action value functions
$Q_{k,h}$ for $|\mathcal{A}|$ actions, with each to be computed within
$\widetilde{O}(\mathcal{O}+\mathcal{R})$ time. Next,
$\\{\bar{\sigma}_{k,h,m}\\}_{m\in\overline{[M]}}$ in Line 12 can be computed
within $\widetilde{O}(M(\mathcal{O}+\mathcal{R}))$ time since they require the
evaluation of $\widehat{f}_{k,m}$, $\widehat{f}_{k,m+1}$ and the computation
of $\mathcal{D}_{\mathcal{F}}$ for each $\bar{\sigma}_{k,h,m}$. Finally, it
takes $M\mathcal{R}$ time to calculate
$\\{\widehat{f}_{k+1,m}\\}_{m\in\overline{[M]}}$ in Line 16. Therefore, the
total time cost of UCRL-WVTR is
$\widetilde{O}(KHM\mathcal{O}+KHM\mathcal{R}+|\mathcal{A}|KH\mathcal{O}+|\mathcal{A}|KH\mathcal{R})$.

###  4.3 Regret Bound

######  Theorem 4.2 (Regret).

For the episodic MDPs with general function approximation defined in Section
3, we set parameters in Algorithm 1 as follows:
$M=\lceil\log_{2}(3KH)\rceil,\lambda=\log\mathcal{N}_{\mathcal{F}},\sigma_{\mathrm{min}}^{2}=\sqrt{\dim_{\mathcal{F}}\log\mathcal{N}_{\mathcal{F}}}/(KH),\gamma^{2}=\sqrt{\log\mathcal{N}_{\mathcal{F}}},\epsilon=\log\mathcal{N}_{\mathcal{F}}\cdot\sigma_{\mathrm{min}}^{2}/(KH)$
and $\\{\widehat{\beta}_{k}\\}_{k\geq 1}$ as

$\widehat{\beta}_{k}=3\sqrt{\iota_{k}}+2\frac{\iota_{k}}{\gamma^{2}}+\sqrt{\lambda}+\sqrt{6kH\epsilon/\sigma_{\mathrm{min}}^{2}}.$

Then for any $\delta>0$, with probability at least $1-4(M+1)\delta$, the
regret of UCRL-WVTR is bounded by

$\widetilde{O}\left(\sqrt{\dim_{\mathcal{F}}\log\mathcal{N}_{\mathcal{F}}}\cdot\sqrt{\mathcal{Q}^{*}}+\dim_{\mathcal{F}}\log\mathcal{N}_{\mathcal{F}}\right),$
(4.1)

where $\iota_{k}=\widetilde{O}(\log\mathcal{N}_{\mathcal{F}})$,
$\dim_{\mathcal{F}}=\dim_{\mathcal{F}}(\sigma_{\mathrm{min}},KH)$,
$\mathcal{N}_{\mathcal{F}}=\mathcal{N}_{\mathcal{F}}(\epsilon)$, and
$\mathcal{Q}^{*}=\min\\{\mathcal{Q}_{0}^{*},V^{*}_{1}K\\}$ with

$\displaystyle
Q_{m}=\sum_{k=1}^{K}\sum_{h=1}^{H}[\mathbb{V}(V^{*}_{h+1})^{2^{m}}](s^{k}_{h},a^{k}_{h}),\quad\mathcal{Q}_{0}^{*}=\max_{m\in\overline{[M]}}Q_{m},\quad
V^{*}_{1}=\frac{1}{K}\sum_{k=1}^{K}V^{*}_{1}(s^{k}_{1}).$

###### Proof.

The proof features a novel concentration bound and fine-grained analyses on
the higher order expansions of MDPs with general function approximation. See
Section 4.4 for a proof sketch and Appendix F for a detailed proof. ∎

Our instance-dependent result given by Theorem 4.2 successfully eliminates the
dependence on $H$, with the exception of logarithmic factors. This
accomplishment represents a groundbreaking advancement in RL with general
function approximation, as it achieves both _horizon-free_ and _instance-
dependent_ for the first time.

#### The Quantity $\mathcal{Q}^{*}$

Since $\mathcal{Q}^{*}=\min\\{\mathcal{Q}_{0}^{*},V^{*}_{1}K\\}\leq
V_{1}^{*}K$, our regret bound in Theorem 4.2 immediately implies a first-order
regret

$\widetilde{O}\left(\sqrt{\dim_{\mathcal{F}}\log\mathcal{N}_{\mathcal{F}}}\cdot\sqrt{V_{1}^{*}K}+\dim_{\mathcal{F}}\log\mathcal{N}_{\mathcal{F}}\right).$

The quantity $\mathcal{Q}_{0}^{*}$ defined in Theorem 4.2 is the maximum of
$Q_{m}$ over $m\in\overline{[M]}$, with $Q_{m}$ being the sum of the variance
of $2^{m}$-th order of the optimal value function along the $k$-th trajectory
over $k\in[K]$. Thereby, $\mathcal{Q}_{0}^{*}$ quantifies the stochasticity of
the MDP under the optimal policy and it vanishes when the transition kernel is
deterministic. In specific, our results also indicate that the regret of
learning a deterministic MDP is bounded by
$\widetilde{O}(\dim_{\mathcal{F}}\log\mathcal{N}_{\mathcal{F}})$. By
Proposition 3.5, this further implies a $\widetilde{O}(d^{2})$ regret bound
for linear mixture MDPs, matching the result in Zhou and Gu (2022).

To illustrate our theory more, we present implied regret bounds for linear
mixture MDPs.

######  Corollary 4.3 (Regret for Linear Mixture MDPs).

For $d$-dimensional linear mixture MDPs defined in Assumption 3.4, we set
parameters in Algorithm 1 according to Theorem 4.2. Then for any $\delta>0$,
with probability at least $1-4(M+1)\delta$, the regret of UCRL-WVTR is bounded
by

$\widetilde{O}(d\sqrt{\mathcal{Q}^{*}}+d^{2})\leq\widetilde{O}(d\sqrt{V_{1}^{*}K}+d^{2})\leq\widetilde{O}(d\sqrt{K}+d^{2}).$

###### Proof.

We have $\dim_{\mathcal{F}},\log\mathcal{N}_{\mathcal{F}}=\widetilde{O}(d)$ by
Proposition 3.5, then the result follows from Theorem 4.2. ∎

Corollary 4.3 demonstrates that we also achieve a first-order regret guarantee
for linear mixture MDPs, which covers the state-of-the-art worst-case regret
bound $\widetilde{O}(d\sqrt{K}+d^{2})$ by Zhou and Gu (2022), therefore
matching the lower bound $\Omega(d\sqrt{K})$ (Zhou et al., 2021) when $K\geq
d^{2}$ up to logarithmic factors. The outcome presented in Zhou and Gu (2022)
critically depends on the feature $\phi_{V}(s,a)\in\mathbb{R}^{d}$ defined in
Assumption 3.4. This feature endows the value function with a simple linear
structure, rendering it amenable to analyze. Consequently, their proposed
algorithms and analytical methodologies encounter limitations when applied to
broader function classes characterized by intricate non-linear structures. We
refer readers to Appendix C for more explanations.

###  4.4 Proof Sketch

In this section, we provide a proof sketch of the regret bound in Theorem 4.2,
which primarily relies on the following key lemmas.

#### Concentration of the Estimated Model

Our first step is to establish the optimism of the estimated value function as
in Line 5 of Algorithm 1, which hinges on a novel concentration inequality in
Theorem 4.4. Notably, this theorem resembles a Bernstein-style bound that
substantially expands the scope of weighted linear regression (Zhou et al.,
2021; Zhou and Gu, 2022) to non-linear settings, thus accommodating a broader
class of functions. We refer readers to Appendix C for more technical
differences with Zhou and Gu (2022).

######  Theorem 4.4.

Let $\\{\mathcal{G}_{t}\\}_{t\geq 1}$ be a filtration, and $\\{X_{t}\\}_{t\geq
1},\\{Y_{t}\\}_{t\geq 1}$ be stochastic processes such that
$X_{t}\in\mathcal{X}$ is $\mathcal{G}_{t-1}$-measurable and $Y_{t}\in[0,L]$ is
$\mathcal{G}_{t}$-measurable. Let $f_{*}\in\mathcal{F}$ with function class
$\mathcal{F}$ consisting of functions $f:\mathcal{X}\to[0,L]$. Suppose
$\mathbb{E}[Y_{t}|\mathcal{G}_{t-1}]=f_{*}(X_{t})$. Let

$\widehat{f}_{t+1}=\mathop{\mathrm{argmin}}_{f\in\mathcal{F}}\sum_{s=1}^{t}w_{s}^{2}(f(X_{s})-Y_{s})^{2},$
(4.2)

where the $\mathcal{G}_{s-1}$-measurable random variable $w_{s}$ satisfies for
all $s\in[t]$, $|w_{s}|\leq W$, $w_{s}^{2}\operatorname{{\rm
Var}}[Y_{s}|\mathcal{G}_{s-1}]\leq\sigma^{2}$. Then for any
$\delta,\epsilon>0$, with probability at least $1-\delta$, we have for all
$t\geq 1$,

$\displaystyle\sum_{s=1}^{t}w_{s}^{2}(\widehat{f}_{t+1}(X_{s})-f_{*}(X_{s}))^{2}\leq\beta_{t+1}^{2}\text{
with}$
$\displaystyle\beta_{t+1}=3\sqrt{\iota_{t}}\sigma+2\iota_{t}L\max_{s\in[t]}w_{s}^{2}\mathcal{D}_{\mathcal{F}}(X_{s};X_{[s-1]},1/w_{[s-1]})+\sqrt{\lambda}+\sqrt{6Lt\epsilon/\sigma_{\mathrm{min}}^{2}},$

where $\mathcal{D}_{\mathcal{F}}$ is in Definition 3.2 and
$\iota_{t}=\widetilde{O}(\log\mathcal{N}_{\mathcal{F}})$.

###### Proof.

See Appendix E for a detailed proof. ∎

######  Remark 4.5.

Theorem 4.4 provides a variance and uncertainty-aware bound of the deviation
of $\widehat{f}_{t+1}$. In contrast, the bound proposed by Ayoub et al. (2020)
for unweighted regression gives
$\beta^{\prime}_{t+1}=\widetilde{O}(L\sqrt{\log\mathcal{N}_{\mathcal{F}}})$,
which is Hoeffding-type, i.e., it scales with the range of noise. Therefore,
UCRL-VTR deviates from achieving an instance-dependent regret bound.

Recall the estimated model $\widehat{f}_{k+1,m}$ in Line 16 of Algorithm 1 is
the solution of weighted least squares regression. We apply Theorem 4.4 for
all $m\in\overline{[M]}$ with $\\{X_{t},w_{t},Y_{t}\\}_{t\geq
1}=\\{z_{i,h,m},1/\bar{\sigma}_{i,h,m}$, $y_{i,h,m}\\}_{i,h\in[k]\times[H]}$,
which gives the confidence radius

$\widehat{\beta}_{K}=\widetilde{O}(\log\mathcal{N}_{\mathcal{F}}).$

Then the optimism property of the estimated value function in Line 5 can be
proved with high probability.

#### Higher Order Expansion

The regret bound can be related to the summation of bonuses (see Appendix
F.3):

$\mathrm{Regret}(K)\lesssim\sum_{k=1}^{K}\sum_{h=1}^{H}\min\\{1,\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(z_{k,h,0};D_{k,0})\\}+C,$

where $\lesssim$ hides constants and $C$ represents lower order terms. Let
$R_{m},S_{m}$ denote the summation of bonuses and moments with respect to
$m$-th level as follows:

$\displaystyle R_{m}$
$\displaystyle:=\sum_{k=1}^{K}\sum_{h=1}^{H}\min\\{1,\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(z_{k,h,m};D_{k,m})\\},$
$\displaystyle S_{m}$
$\displaystyle:=\sum_{k=1}^{K}\sum_{h=1}^{H}[\mathbb{V}V_{k,h+1}^{2^{m}}](s_{h}^{k},a_{h}^{k}).$

Then we can further bound $R_{m}$ with Lemma 4.6.

######  Lemma 4.6 (Informal).

We have for all $m\in\overline{[M-1]}$,

$R_{m}\lesssim\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{S_{m}+R_{m+1}}+\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}+C,$

Lemma 4.6 establishes relationships between $R_{m}$ and $S_{m}$, the estimated
variance to the higher moment. Such a structure recursively expands for
$M=O(\log KH)$ times, resulting in a regret bound only log-polynomially
dependent on $H$. We further conduct a fine-grained analysis, rendering these
quantities instance-dependent:

######  Lemma 4.7 (Informal).

We have

$R_{0}\lesssim\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}R_{0}}+\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{\mathcal{Q}^{*}}+\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}+C.$

The completion of the proof necessitates in-depth analyses of higher-order
quantities to eliminate lower-order terms. We refer readers to Appendix F for
the formal statements of these critical lemmas, as well as an exhaustive and
comprehensive proof of Theorem 4.2.

##  5 Experiments

In this section, we conduct numerical experiments to demonstrate the
effectiveness of our algorithmic designs. We adopt the episodic RiverSwim
environment (Strehl and Littman, 2008), which is also considered in Ayoub et
al. (2020). Figure 1 shows a $5$-state RiverSwim environment with action space
$\mathcal{A}=\\{a_{1},a_{2}\\}$. We choose $H\in\\{20,100\\}$, where $H=20$ in
consistency with Ayoub et al. (2020), and $H=100$ to demonstrate the
performance on long planning horizon problems. And we set the number of
episodes $K=5000$. We refer readers to Appendix A for implementation details
and additional experimental results.

$s_{1}$ $s_{2}$ $s_{3}$ $s_{4}$ $s_{5}$
$0.1$$0.9$$0.05$$0.05$$0.9$$0.05$$0.05$$0.9$$0.05$$0.05$$0.9$$0.1$$(0.9,r=1)$$(1,r=0.005)$$1$$1$$1$$1$

Figure 1: The transition probabilities and rewards of RiverSwim environment
(Strehl and Littman, 2008). The solid arrow shows the transition kernel of
action $a_{1}$. And the dashed arrow represents that of action $a_{2}$. The
reward is denoted with the transition probabilities, if greater than $0$.

We mainly consider three approaches to solve the episodic MDPs: (i) our
proposed algorithm UCRL-WVTR; (ii) UCRL-WVTR without HOME; (iii) UCRL-VTR
(Ayoub et al., 2020). We generate 10 independent paths for each setting. Their
average regrets with error bars are shown in Figure 2.

(a) A $5$-state RiverSwim with $H=20$. (b) A $5$-state RiverSwim with $H=100$.

Figure 2: Cumulative regret over episodes. Random represents the baseline
where the agent acts uniformly.

As anticipated, UCRL-WVTR demonstrates superior performance compared to UCRL-
VTR for both settings, underscoring the efficacy of weighted regression. It is
noteworthy that the omission of the high-order moment estimator results in a
slightly worse performance, thereby illustrating its practical utility. In
summary, the experimental findings substantiate and reinforce our theoretical
conclusions.

##  6 Conclusion

In this work, we propose a novel algorithm, termed as UCRL-WVTR, for model-
based RL with general function approximation, which features weighted value-
targeted regression and a high-order moment estimator. We theoretically
demonstrate it achieves a horizon-free and instance-dependent regret bound. As
a special case, it matches the lower bound for linear mixture MDPs up to
logarithmic factors, showing its tightness. Furthermore, it is computationally
efficient given a regression oracle. We also conduct numerical experiments to
validate the theoretical findings. To the best of our knowledge, we are the
first to achieve efficient, horizon-free and instance-dependent learning in RL
with general function approximation.

## Acknowledgments

Lin F. Yang is supported in part by NSF #2221871 and an Amazon Faculty Award.

## References

  * Abbasi-Yadkori et al. (2011) Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  _Advances in neural information processing systems_ , 24, 2011.
  * Agarwal et al. (2023) Alekh Agarwal, Yujia Jin, and Tong Zhang.  VO$Q$L: Towards optimal regret in model-free rl with nonlinear function approximation.  In _The Thirty Sixth Annual Conference on Learning Theory_ , pages 987–1063. PMLR, 2023.
  * Ayoub et al. (2020) Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang.  Model-based reinforcement learning with value-targeted regression.  In _International Conference on Machine Learning_ , pages 463–474. PMLR, 2020.
  * Azar et al. (2017) Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos.  Minimax regret bounds for reinforcement learning.  In _International Conference on Machine Learning_ , pages 263–272. PMLR, 2017.
  * Bubeck et al. (2015) Sébastien Bubeck et al.  Convex optimization: Algorithms and complexity.  _Foundations and Trends® in Machine Learning_ , 8(3-4):231–357, 2015.
  * Chen et al. (2022a) Fan Chen, Song Mei, and Yu Bai.  Unified algorithms for rl with decision-estimation coefficients: No-regret, pac, and reward-free learning.  _arXiv preprint arXiv:2209.11745_ , 2022a.
  * Chen et al. (2022b) Zixiang Chen, Chris Junchi Li, Angela Yuan, Quanquan Gu, and Michael I Jordan.  A general framework for sample-efficient function approximation in reinforcement learning.  _arXiv preprint arXiv:2209.15634_ , 2022b.
  * Dann et al. (2021) Christoph Dann, Mehryar Mohri, Tong Zhang, and Julian Zimmert.  A provably efficient model-free posterior sampling method for episodic reinforcement learning.  _Advances in Neural Information Processing Systems_ , 34:12040–12051, 2021.
  * Du et al. (2021) Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang.  Bilinear classes: A structural framework for provable generalization in rl.  In _International Conference on Machine Learning_ , pages 2826–2836. PMLR, 2021.
  * Foster et al. (2018) Dylan Foster, Alekh Agarwal, Miroslav Dudík, Haipeng Luo, and Robert Schapire.  Practical contextual bandits with regression oracles.  In _International Conference on Machine Learning_ , pages 1539–1548. PMLR, 2018.
  * Foster et al. (2021) Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin.  The statistical complexity of interactive decision making.  _arXiv preprint arXiv:2112.13487_ , 2021.
  * Foster et al. (2023) Dylan J Foster, Noah Golowich, and Yanjun Han.  Tight guarantees for interactive decision making with the decision-estimation coefficient.  _arXiv preprint arXiv:2301.08215_ , 2023.
  * Huang et al. (2023) Jiayi Huang, Han Zhong, Liwei Wang, and Lin F Yang.  Tackling heavy-tailed rewards in reinforcement learning with function approximation: Minimax optimal and instance-dependent regret bounds.  _arXiv preprint arXiv:2306.06836_ , 2023.
  * Jia et al. (2020) Zeyu Jia, Lin Yang, Csaba Szepesvari, and Mengdi Wang.  Model-based reinforcement learning with value-targeted regression.  In _Learning for Dynamics and Control_ , pages 666–686. PMLR, 2020.
  * Jiang and Agarwal (2018) Nan Jiang and Alekh Agarwal.  Open problem: The dependence of sample complexity lower bounds on planning horizon.  In _Conference On Learning Theory_ , pages 3395–3398. PMLR, 2018.
  * Jiang et al. (2017) Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire.  Contextual decision processes with low bellman rank are pac-learnable.  In _International Conference on Machine Learning_ , pages 1704–1713. PMLR, 2017.
  * Jin et al. (2021) Chi Jin, Qinghua Liu, and Sobhan Miryoosefi.  Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms.  _Advances in neural information processing systems_ , 34:13406–13418, 2021.
  * Kim et al. (2022) Yeoneung Kim, Insoon Yang, and Kwang-Sung Jun.  Improved regret analysis for variance-adaptive linear bandits and horizon-free linear mixture mdps.  _Advances in Neural Information Processing Systems_ , 35:1060–1072, 2022.
  * Kong et al. (2021) Dingwen Kong, Ruslan Salakhutdinov, Ruosong Wang, and Lin F Yang.  Online sub-sampling for reinforcement learning with general function approximation.  _arXiv preprint arXiv:2106.07203_ , 2021.
  * Krishnamurthy et al. (2017) Akshay Krishnamurthy, Alekh Agarwal, Tzu-Kuo Huang, Hal Daumé III, and John Langford.  Active learning for cost-sensitive classification.  In _International Conference on Machine Learning_ , pages 1915–1924. PMLR, 2017.
  * Li and Sun (2023) Xiang Li and Qiang Sun.  Variance-aware robust reinforcement learning with linear function approximation with heavy-tailed rewards.  _arXiv preprint arXiv:2303.05606_ , 2023.
  * Li et al. (2022) Yuanzhi Li, Ruosong Wang, and Lin F Yang.  Settling the horizon-dependence of sample complexity in reinforcement learning.  In _2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 965–976. IEEE, 2022.
  * Liu et al. (2023) Zhihan Liu, Miao Lu, Wei Xiong, Han Zhong, Hao Hu, Shenao Zhang, Sirui Zheng, Zhuoran Yang, and Zhaoran Wang.  One objective to rule them all: A maximization objective fusing estimation and planning for exploration.  _arXiv preprint arXiv:2305.18258_ , 2023.
  * Modi et al. (2020) Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh.  Sample complexity of reinforcement learning using linearly combined model ensembles.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2010–2020. PMLR, 2020.
  * Osband and Van Roy (2014) Ian Osband and Benjamin Van Roy.  Model-based reinforcement learning and the eluder dimension.  _Advances in Neural Information Processing Systems_ , 27, 2014.
  * Russo and Van Roy (2013) Daniel Russo and Benjamin Van Roy.  Eluder dimension and the sample complexity of optimistic exploration.  _Advances in Neural Information Processing Systems_ , 26, 2013.
  * Strehl and Littman (2008) Alexander L Strehl and Michael L Littman.  An analysis of model-based interval estimation for markov decision processes.  _Journal of Computer and System Sciences_ , 74(8):1309–1331, 2008.
  * Sun et al. (2019) Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford.  Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches.  In _Conference on learning theory_ , pages 2898–2933. PMLR, 2019.
  * Wagenmaker and Foster (2023) Andrew J Wagenmaker and Dylan J Foster.  Instance-optimality in interactive decision making: Toward a non-asymptotic theory.  In _The Thirty Sixth Annual Conference on Learning Theory_ , pages 1322–1472. PMLR, 2023.
  * Wagenmaker et al. (2022) Andrew J Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson.  First-order regret in reinforcement learning with linear function approximation: A robust estimation approach.  In _International Conference on Machine Learning_ , pages 22384–22429. PMLR, 2022.
  * Wang et al. (2020a) Ruosong Wang, Simon S Du, Lin Yang, and Sham Kakade.  Is long horizon rl more difficult than short horizon rl?  _Advances in Neural Information Processing Systems_ , 33:9075–9085, 2020a.
  * Wang et al. (2020b) Ruosong Wang, Russ R Salakhutdinov, and Lin Yang.  Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension.  _Advances in Neural Information Processing Systems_ , 33:6123–6135, 2020b.
  * Zanette and Brunskill (2019) Andrea Zanette and Emma Brunskill.  Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds.  In _International Conference on Machine Learning_ , pages 7304–7312. PMLR, 2019.
  * Zhang et al. (2021a) Zihan Zhang, Xiangyang Ji, and Simon Du.  Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon.  In _Conference on Learning Theory_ , pages 4528–4531. PMLR, 2021a.
  * Zhang et al. (2021b) Zihan Zhang, Jiaqi Yang, Xiangyang Ji, and Simon S Du.  Improved variance-aware confidence sets for linear bandits and linear mixture mdp.  _Advances in Neural Information Processing Systems_ , 34:4342–4355, 2021b.
  * Zhang et al. (2022) Zihan Zhang, Xiangyang Ji, and Simon Du.  Horizon-free reinforcement learning in polynomial time: the power of stationary policies.  In _Conference on Learning Theory_ , pages 3858–3904. PMLR, 2022.
  * Zhao et al. (2023) Heyang Zhao, Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu.  Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency.  In _Proceedings of Thirty Sixth Conference on Learning Theory_ , volume 195 of _Proceedings of Machine Learning Research_ , pages 4977–5020. PMLR, 2023.
  * Zhong et al. (2022) Han Zhong, Wei Xiong, Sirui Zheng, Liwei Wang, Zhaoran Wang, Zhuoran Yang, and Tong Zhang.  Gec: A unified framework for interactive decision making in mdp, pomdp, and beyond.  _arXiv preprint arXiv:2211.01962_ , 2022.
  * Zhou and Gu (2022) Dongruo Zhou and Quanquan Gu.  Computationally efficient horizon-free reinforcement learning for linear mixture mdps.  _Advances in neural information processing systems_ , 35:36337–36349, 2022.
  * Zhou et al. (2021) Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari.  Nearly minimax optimal reinforcement learning for linear mixture markov decision processes.  In _Conference on Learning Theory_ , pages 4532–4576. PMLR, 2021.
  * Zhou et al. (2023) Runlong Zhou, Zhang Zihan, and Simon Shaolei Du.  Sharp variance-dependent bounds in reinforcement learning: Best of both worlds in stochastic and deterministic environments.  In _International Conference on Machine Learning_ , pages 42878–42914. PMLR, 2023.

##  Appendix A Additional Experiments

#### Hyperparameters of Algorithms

We provide more details about the three algorithms considered for the
experiments in Section 5. These approaches share similar structures with
Algorithm 1. (i) UCRL-WVTR: our proposed algorithm in Algorithm 1. (ii) UCRL-
WVTR without HOME: it can be implemented by setting the level $M=1$ in
Algorithm 1. Intuitively, we simply use unweighted regression for solving
$f_{k,h,1}$, which is then used for constructing the variance estimate
$[\bar{\mathbb{V}}_{k,0}V_{k,h+1}](s^{k}_{h},a^{k}_{h})=\widehat{f}_{k,1}(z_{k,h,1})-\widehat{f}_{k,0}^{2}(z_{k,h,0})$.
(iii) UCRL-VTR: it can be implemented by setting the level $M=0$,
$\sigma_{\mathrm{min}}=1$ and $\gamma=0$ in Algorithm 1, since it simply uses
unweighted regression, resulting the variance estimation
$[\bar{\mathbb{V}}_{k,0}V_{k,h+1}](s^{k}_{h},a^{k}_{h})=1$. Specifically, we
list the hyperparameters in Table 1.

Table 1: Hyperparameters of Algorithms Hyperparameters | UCRL-WVTR |  UCRL-WVTR without HOME | UCRL-VTR
---|---|---|---
$\lambda$ | 0.001 | 0.001 | 0.001
$\sigma_{\mathrm{min}}$ | 0.01 | 0.01 | 1
$\gamma$ | 0.5 | 0.5 | 0
$\beta$ | 1 | 1 | 1
$M$ | 3 | 1 | 0

#### Environments

Recall the RiverSwim environment consists of a series of $n$ states organized
in a linear sequence, as shown in Figure 3. The agent’s initial position is on
the far left, and it faces a decision at each state to either swim to the left
or to the right. Notably, there exists a prevailing current that significantly
facilitates leftward swimming while making rightward swimming more
challenging. When swimming with the current, the agent is guaranteed to make
progress to the left. However, swimming against the current predominantly
leads to rightward movement but occasionally results in the agent moving left
or remaining in the current state. The environment offers rewards only at the
extreme ends: a reward of $0.05$ on the far left and a reward of $1$ on the
far right. In essence, the agent is compelled to explore the environment
thoroughly, ultimately weighing the decision of whether to brave the uncertain
prospects of moving against the current for the potentially higher reward, or
simply staying in the original position to secure a relatively smaller reward.
Consequently, intelligent and strategic exploration becomes a fundamental
requirement for acquiring an effective policy in this challenging environment.

$s_{1}$ $s_{2}$ $\cdots$ $s_{n-1}$ $s_{n}$
$0.1$$0.9$$0.05$$0.05$$0.9$$0.05$$0.9$$0.05$$0.05$$0.9$$0.1$$(0.9,r=1)$$(1,r=0.005)$$1$$1$$1$$1$

Figure 3: The transition probabilities and rewards of an $n$-state RiverSwim
environment (Strehl and Littman, 2008). The solid arrow shows the transition
kernel of action $a_{1}$. And the dashed arrow represents that of action
$a_{2}$. The reward is denoted with the transition probabilities, if greater
than $0$.

#### Additional Results

To demonstrate the effectiveness of our proposed algorithm more, we show
additional experimental results. We set $H=100$ to demonstrate the performance
of these algorithms on long planning horizon problems. We will choose a series
of gradually increasing the number of states of RiverSwim, i.e.,
$|S|\in\\{6,8,10\\}$, which will exponentially increase the difficulty of such
an episodic RL problem.

(a) Regret with $|S|=6$ (b) Regret with $|S|=8$ (c) Regret with $|S|=10$ (d)
Average Rewards with $|S|=6$ (e) Average Rewards with $|S|=8$ (f) Average
Rewards with $|S|=10$

Figure 4: Regret and Average Rewards of $1000$ Episodes

As shown in Figure 4, the columns correspond to RiverSwim with $|S|=6,8,10$,
respectively. The first row shows the cumulative regret of each algorithm, and
the second row represents average rewards within a single episode. We generate
$10$ independent paths for each algorithm, and show the average values plus or
minus the standard deviation.

As expected, our proposed algorithm UCRL-WVTR outperforms UCRL-VTR,
highlighting the effectiveness of weighted regression. It is worth noting that
excluding the high-order moment estimator leads to a slightly inferior
performance, thus demonstrating its practical value. While it introduces
additional uncertainty in estimating higher-order moments, as clearly
demonstrated by our results, the extra information from these variance
estimations can leverage historical data more effectively, thereby
accelerating the learning process. In summary, our experimental results
provide strong support for and further reinforce our theoretical conclusions.

##  Appendix B Computing Uncertainty via the Regression Oracle

In this section, we introduce how to efficiently compute uncertainty
$\mathcal{D}_{\mathcal{F}}$ in Definition 3.2. The high-level idea is to
decompose the task into solving a series of weighted least squares regression
problems, whose solutions are directly available by the regression oracle
defined in Assumption 4.1. Recall

$D^{2}_{\mathcal{F}}(X_{t};X_{[t-1]},\sigma_{[t-1]})=\sup_{f_{1},f_{2}\in\mathcal{F}}\frac{\left(f_{1}(X_{t})-f_{2}(X_{t})\right)^{2}}{\sum_{s=1}^{t-1}\frac{1}{\sigma_{s}^{2}}\left(f_{1}(X_{s})-f_{2}(X_{s})\right)^{2}+\lambda}.$
(B.1)

We denote $\mathcal{G}:=\mathcal{F}-\mathcal{F}$. Assuming the optimal value
of (B.1) is attained at $f_{1}^{*},f_{2}^{*}$, let
$g_{*}=f_{1}^{*}-f_{2}^{*}\in\mathcal{G}$, we claim that $g_{*}$ is the
solution to the following constrained optimization problem:

$\max_{g\in\mathcal{G}}g(X_{t})\quad\text{ s.t.
}\sum_{s=1}^{t-1}\frac{1}{\sigma_{s}^{2}}g^{2}(X_{s})\leq\beta^{*},$ (B.2)

where $\beta^{*}=\sum_{s=1}^{t-1}\frac{1}{\sigma_{s}^{2}}g_{*}^{2}(X_{s})$ is
unknown in prior. The claim can be easily proved by contradiction. If the
solution to (B.2) is $\widetilde{g}\neq g_{*}$, then we have
$\widetilde{g}(X_{t})\geq g_{*}(X_{t})$ while
$\sum_{s=1}^{t-1}\frac{1}{\sigma_{s}^{2}}\widetilde{g}^{2}(X_{s})\leq\beta^{*}=\sum_{s=1}^{t-1}\frac{1}{\sigma_{s}^{2}}g_{*}^{2}(X_{s})$,
which yields

$\frac{\widetilde{g}^{2}(X_{t})}{\sum_{s=1}^{t-1}\frac{1}{\sigma_{s}^{2}}\widetilde{g}^{2}(X_{s})+\lambda}\geq\frac{g_{*}^{2}(X_{t})}{\sum_{s=1}^{t-1}\frac{1}{\sigma_{s}^{2}}g_{*}^{2}(X_{s})+\lambda},$

a contradiction. Inspired by Foster et al. (2018), we then transform the
problem (B.2) into solving the following weighted regression problem

$\min_{g\in\mathcal{G}}\sum_{s=1}^{t}v_{s}(g(X_{s})-Y_{s})^{2},$

where $v_{s}=1/\sigma_{s}^{2}$ for $s\in[t-1]$, $v_{t}\in\mathbb{R}^{+}$ is
some constant unknown to the agent, $Y_{s}=0$ for $s\in[t-1]$ and $Y_{t}=1$.
The solution is available with access to a regression oracle. We leverage a
doubling trick for $\beta^{*}$ and a binary search technique for the proper
value of $v_{t}$. See Algorithm 3 for a detailed description.

Algorithm 3 Computing Uncertainty

0: Function class $\mathcal{F}$, dataset $\\{X_{[t]},\sigma_{[t-1]}\\}$,
$\lambda$, upper bound $\mathcal{B}$, precision $\epsilon$ and a regression
oracle

0: The estimated uncertainty $\widetilde{\mathcal{D}}$

1: Denote
$R(g,v):=\sum_{s=1}^{t-1}v_{s}(g(X_{s})-Y_{s})^{2}+v(g(X_{t})-1)^{2}$

2: Set $\mathcal{G}\leftarrow\mathcal{F}-\mathcal{F},\bar{\beta}\leftarrow
2\lambda,\widetilde{\mathcal{D}}\leftarrow 0$

3: while $\bar{\beta}<2\mathcal{B}$ do

4: Set $\beta\leftarrow\bar{\beta}-\lambda$

5: Set $v_{L}\leftarrow 0$, $v_{H}\leftarrow 2\beta/\epsilon$

6: Set $g_{L}\leftarrow 0$,
$g_{H}\leftarrow\mathop{\mathrm{argmin}}_{g\in\mathcal{G}}R(g,v_{H})$

7: Set $z_{L}\leftarrow 0$, $z_{H}\leftarrow g_{H}(X_{t})$

8: Set $\Delta\leftarrow\epsilon\beta/4$

9: while $|z_{H}-z_{L}|>\epsilon$ and $|v_{H}-v_{L}|>\Delta$ do

10: Set $\widetilde{v}\leftarrow(v_{H}+v_{L})/2$

11: Set
$\widetilde{g}\leftarrow\mathop{\mathrm{argmin}}_{g\in\mathcal{G}}R(g,\widetilde{v})$

12: Set $\widetilde{z}\leftarrow\widetilde{g}(X_{t})$

13: if
$\sum_{s=1}^{t-1}\frac{1}{\sigma_{s}^{2}}\widetilde{g}^{2}(X_{s})>\beta$ then

14: $v_{H}\leftarrow\widetilde{v}$, $z_{H}\leftarrow\widetilde{g}(X_{t})$

15: else

16: $v_{L}\leftarrow\widetilde{v}$, $z_{L}\leftarrow\widetilde{g}(X_{t})$

17: end if

18: end while

19: Set
$\widetilde{\mathcal{D}}\leftarrow\max\left\\{\widetilde{\mathcal{D}},\widetilde{g}(X_{t})/\sqrt{\sum_{s=1}^{t-1}\frac{1}{\sigma_{s}^{2}}\widetilde{g}^{2}(X_{s})+\lambda}\right\\}$

20: Set $\bar{\beta}=2\bar{\beta}$

21: end while

######  Proposition B.1.

Consider the following optimization problem for solving the uncertainty

$\max_{f_{1},f_{2}\in\mathcal{F}}\frac{\left(f_{1}(X_{t})-f_{2}(X_{t})\right)^{2}}{\sum_{s=1}^{t-1}\frac{1}{\sigma_{s}^{2}}\left(f_{1}(X_{s})-f_{2}(X_{s})\right)^{2}+\lambda}.$

By definition, the optimal value is
$\mathcal{D}^{2}_{\mathcal{F}}(X_{t};X_{[t-1]},\sigma_{[t-1]})$, and we assume
its solution is $g^{*}=f_{1}^{*}-f_{2}^{*}$. For any $\epsilon>0$, we run
Algorithm 3 to solve the problem above with $\mathcal{B}$ satisfying
$\mathcal{B}\geq\sum_{s=1}^{t-1}\frac{1}{\sigma_{s}^{2}}g_{*}^{2}(X_{s})+\lambda$.
If the function class $\mathcal{F}$ is convex and closed under point-wise
convergence, then Algorithm 3 terminates within
$O(\log(\mathcal{B}/\lambda)\log(1/\epsilon))$ calls to the regression oracle
and returns $\widetilde{\mathcal{D}}$ such that

$\widetilde{\mathcal{D}}-\epsilon/\sqrt{\lambda}\leq
D_{\mathcal{F}}(X_{t};X_{[t-1]},\sigma_{[t-1]})\leq\sqrt{2}\widetilde{\mathcal{D}}+\epsilon/\sqrt{\lambda}.$

###### Proof.

Note $\mathcal{G}=\mathcal{F}-\mathcal{F}$ is convex due to the convexity of
$\mathcal{F}$. Denote $g_{\alpha}$ as the $\epsilon$-precision solution of the
following constrained optimization problem:

$\max_{g\in\mathcal{G}}g(X_{t})\quad\text{ s.t.
}\sum_{s=1}^{t-1}\frac{1}{\sigma_{s}^{2}}g^{2}(X_{s})\leq\lambda
2^{\alpha}-\lambda.$ (B.3)

Then according to Theorem 1 of Foster et al. (2018), $g_{\alpha}$ is computed
within $O(\log(1/\epsilon))$ time, and the estimated uncertainty
$\widetilde{\mathcal{D}}$ returned by Algorithm 3 is actually the maximum of
the following quantities over
$\alpha\in\\{0,1,\dots,\lceil\log_{2}(\mathcal{B}/\lambda)\rceil\\}$, as shown
in (B.4).

$\widetilde{\mathcal{D}}=\max_{\alpha}\frac{g_{\alpha}(X_{t})}{\sqrt{\sum_{s=1}^{t-1}\frac{1}{\sigma_{s}^{2}}g_{\alpha}^{2}(X_{s})+\lambda}}.$
(B.4)

Due to the definition of $\mathcal{B}$, there exists
$\alpha\in\\{0,1,\dots,\lceil\log_{2}(\mathcal{B}/\lambda)\rceil-1\\}$, such
that $\lambda 2^{\alpha}\leq\beta^{*}+\lambda\leq\lambda 2^{\alpha+1}$. On one
hand,

$\displaystyle\mathcal{D}_{\mathcal{F}}(X_{t};X_{[t-1]},\sigma_{[t-1]})$
$\displaystyle=\frac{g_{*}(X_{t})}{\sqrt{\sum_{s=1}^{t-1}\frac{1}{\sigma_{s}^{2}}g_{*}^{2}(X_{s})+\lambda}}=\frac{g_{*}(X_{t})}{\sqrt{\beta^{*}+\lambda}}\leq\frac{g_{*}(X_{t})}{\sqrt{\lambda
2^{\alpha}}}=\sqrt{2}\frac{g_{*}(X_{t})}{\sqrt{\lambda 2^{\alpha+1}}}$
$\displaystyle\overset{(a)}{\leq}\sqrt{2}\frac{g_{\alpha+1}(X_{t})}{\sqrt{\sum_{s=1}^{t-1}\frac{1}{\sigma_{s}^{2}}g_{\alpha+1}^{2}(X_{s})+\lambda}}+\frac{\epsilon}{\sqrt{\lambda
2^{\alpha}}}\overset{(b)}{\leq}\sqrt{2}\widetilde{D}+\frac{\epsilon}{\sqrt{\lambda}},$

where $(a)$ holds due to the definition of $g_{\alpha+1}$ in (B.3) and $(b)$
holds due to (B.4). On the other hand,
$\mathcal{D}_{\mathcal{F}}(X_{t};X_{[t-1]},\sigma_{[t-1]})\geq\widetilde{D}-\epsilon/\sqrt{\lambda}$
due to the definition of $\mathcal{D}_{\mathcal{F}}$. The proof is completed.
∎

######  Corollary B.2.

To invoke Algorithm 3 in UCRL-WVTR, we set
$\mathcal{B}=KH/\sigma_{\mathrm{min}}^{2}+\lambda$,
$\epsilon=\sqrt{\lambda}/(KH)$, then the estimated uncertainty
$\widetilde{\mathcal{D}}$ can be derived within $\widetilde{O}(1)$ calls to
the regression oracle such that
$\widetilde{\mathcal{D}}-1/(KH)\leq\mathcal{D}_{\mathcal{F}}\leq\sqrt{2}\widetilde{\mathcal{D}}+1/(KH)$.
The error in terms of the estimated uncertainty $\mathcal{D}_{\mathcal{F}}$
only enlarges the regret bound by at most constant terms.

######  Remark B.3.

It is noteworthy that Kong et al. (2021) adopted a similar idea to compute the
sensitivity score defined therein via the regression oracle. However, their
approach is not directly applicable to ours, since (i) They consider the
unweighted regression setting, which is a special case of ours by setting
$\sigma_{[t]}={\bm{1}}$. (ii) The sensitivity score in their work is used for
constructing a dataset that approximates historical samples and for applying a
low-switching updating scheme, while we use uncertainty to directly update the
value function.

##  Appendix C Comparisons with Previous Work

We make some comparisons with Zhou and Gu (2022), with emphasis on why their
approaches for linear mixture MDPs defined in Assumption 3.4 can not be
extended to RL with general function approximation.

First, at the core of their analysis is a Bernstein-style concentration bound
(Theorem 4.3 in their work) for the deviation
$\|\bm{\mu}_{t}-\bm{\mu}^{*}\|_{\bm{Z}_{t}}$, where $\bm{\mu}_{t}$ is the
solution of least squares regression with (weighted) data
$\\{\bm{x}_{s}\\}_{s\in[t]}$ and targets $\\{y_{s}\\}_{s\in[t]}$,
$\bm{Z}_{t}=\sum_{s=1}^{t}\bm{x}_{s}\bm{x}_{s}^{\top}+\lambda\bm{I}$. Assuming
a filtration $\\{\mathcal{G}_{t}\\}_{t\geq 1}$, here $\bm{x}_{t}$ is
$\mathcal{G}_{t-1}$-measurable, and
$y_{t}=\langle\bm{\theta}^{*},\bm{x}_{t}\rangle+\eta_{t}$ with noise
$\eta_{t}\in\mathcal{G}_{t}$. Plugging in the analytical form of the estimate
$\bm{\mu}_{t}=\bm{Z}_{t}^{-1}\sum_{s=1}^{t}\bm{x}_{s}y_{s}$, the following
inequality holds

$\|\bm{\mu}_{t}-\bm{\mu}^{*}\|_{\bm{Z}_{t}}\leq\Big{\|}\sum_{s=1}^{t}\bm{x}_{s}\eta_{s}\Big{\|}_{\bm{Z}_{t}^{-1}}+\sqrt{\lambda}\|\bm{\mu}^{*}\|_{2}.$
(C.1)

Denote $\bm{d}_{t}=\sum_{s=1}^{t}\bm{x}_{s}\eta_{s}$,
$Z_{t}=\|\bm{d}_{t}\|_{\bm{Z}_{t}^{-1}}$. They then decompose
$\|\sum_{s=1}^{t}\bm{x}_{s}\eta_{s}\|_{\bm{Z}_{t}^{-1}}^{2}=Z_{t}^{2}$ into
two bounded martingale difference sequences as in (C.2) and apply Freedman’s
inequality for deriving high probability bounds of these two terms separately.

$Z_{t}^{2}\leq\sum_{s=1}^{t}\frac{2\eta_{s}\bm{x}_{s}^{\top}\bm{Z}_{s-1}^{-1}\bm{d}_{s-1}}{1+w_{s}^{2}}+\sum_{s=1}^{t}\frac{\eta_{s}^{2}w_{s}^{2}}{1+w_{s}^{2}},$
(C.2)

where $w_{t}=\|\bm{x}_{t}\|_{\bm{Z}_{t-1}^{-1}}$. Such a self-normalized
expression in (C.1) holds thanks to the analytical solution $\bm{\mu}_{t}$ of
weighted linear regression, and a decomposition in (C.2) heavily depends on
the linear structure of the estimate
$\bm{\mu}_{t}=\bm{Z}_{t}^{-1}\sum_{s=1}^{t}\bm{x}_{s}y_{s}$. Regrettably,
these properties no longer hold in non-linear settings, necessitating a new
approach for providing a tight concentration bound on the solution to least
squares regression as shown in Theorem 4.4. We refer the readers to its proof
in Appendix E for details.

Second, once deriving a tight estimate of model with
$\|\widehat{\bm{\theta}}_{k}-\bm{\theta}^{*}\|_{\widehat{\bm{\Sigma}}_{k}}\leq\widehat{\beta}_{k}$,
given any state-action pair $(s,a)$ and the next-state value function $V$, one
can naturally construct an upper bound of the next-state value function
evaluated on $(s,a)$ by explicitly adding a bonus of the following form

$|\widehat{f}_{k}(s,a,V)-f_{*}(s,a,V)|=\|\langle\bm{\phi}_{V}(s,a),\widehat{\bm{\theta}}_{k}-\bm{\theta}_{*}\rangle\|\leq\widehat{\beta}_{k}\|\bm{\phi}_{V}(s,a)\|_{\widehat{\bm{\Sigma}}_{k}^{-1}},$
(C.3)

where
$\widehat{\bm{\Sigma}}_{k}=\sum_{i=1}^{k-1}\sum_{h=1}^{H}\frac{1}{\bar{\sigma}_{i,h}^{2}}\bm{\phi}_{i,h}\bm{\phi}_{i,h}^{\top}+\lambda\bm{I}$
with $\bm{\phi}_{k,h}=\bm{\phi}_{V_{k,h+1}}(s^{k}_{h},a^{k}_{h})$. Then,
adopting the policy that selecting action with the maximum value function, and
using the standard technique, one can approximately bound the $K$-episode
regret as

$\mathrm{Regret}(K)\lesssim\widehat{\beta}_{K}\sum_{k=1}^{K}\sum_{h=1}^{H}\|\bm{\phi}_{k,h}\|_{\widehat{\bm{\Sigma}}_{k}^{-1}}\lesssim\widehat{\beta}_{K}\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\bar{\sigma}_{k,h}^{2}}\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\left\|\frac{\bm{\phi}_{k,h}}{\bar{\sigma}_{k,h}}\right\|_{\widehat{\bm{\Sigma}}_{k}^{-1}}^{2}}.$
(C.4)

Here
$\sum_{k=1}^{K}\sum_{h=1}^{H}\left\|\frac{\bm{\phi}_{k,h}}{\bar{\sigma}_{k,h}}\right\|_{\widehat{\bm{\Sigma}}_{k}^{-1}}^{2}$
can be easily bounded by $\widetilde{O}(d)$ by elliptical potential lemma
(Abbasi-Yadkori et al., 2011). However, in the realm of RL with general
function approximation, the bonus term does not enjoy such a simple form as in
(C.3), and the elliptical potential lemma is not available. To this end, we
define the bonus as an optimization problem over the general function class,
where an analytical solution is generally not attainable. To overcome this
obstacle, we further introduce a computationally efficient algorithm for
computing uncertainty for the bonus term via a regression oracle, thus
achieving computational efficiency despite the non-linear structure. We then
carefully bound the regret with respect to the generalized Eluder dimension.
Please see our definition of the uncertainty and the generalized Eluder
dimension in Definition 3.2, and computational complexity in Section 4.2.

Furthermore, they leverage a high-moment estimator for a tight upper bound of
$\sum_{k=1}^{K}\sum_{h=1}^{H}\bar{\sigma}_{k,h}^{2}$ in (C.4). More
specifically, they estimate the variances of the $m$-th moment of the next-
state value functions up to $M=O(\log(KH))$ levels, and recursively establish
the relationships between quantities of MDPs of these levels. Consequently,
they obtain an upper bound of the variance term with only log-polynomial
dependence on $H$, thus ultimately achieving a horizon-free regret bound.
However, these lemmas with respect to the higher-order expansions of MDPs may
not hold in the context of general function approximation. Despite the
inherent complexities posed by the non-linear function class, we have extended
these methodologies to achieve a horizon-free regret bound with log-polynomial
dependence on the planning horizon $H$. Significantly, our refined analysis
also establishes a connection with certain problem-specific quantities,
consequently rendering the regret bound of UCRL-WVTR instance-dependent.
Comprehensive elaboration on this achievement is provided in Section 4.3.

##  Appendix D Proofs for Linear mixture MDPs

###  D.1 Proof of Proposition 3.5

###### Proof of Proposition 3.5.

We first bound the covering number, then come to the generalized Eluder
dimension.

#### Covering Number

For any $f\in\mathcal{F}$, we have for any $(s,a,V)$,

$\displaystyle f(s,a,V)$
$\displaystyle=[\mathbb{P}V](s,a)=\sum_{s^{\prime}\in\mathcal{S}}\langle\bm{\theta}^{*},\bm{\phi}(s^{\prime}|s,a)\rangle
V(s^{\prime})$
$\displaystyle=\langle\bm{\theta}^{*},\sum_{s^{\prime}\in\mathcal{S}}\bm{\phi}(s^{\prime}|s,a)V(s^{\prime})\rangle=\langle\bm{\theta}^{*},\bm{\phi}_{V}(s,a)\rangle,$
(D.1)

where $\|\bm{\theta}^{*}\|_{2}\leq B$. This implies $f$ is a linear function
of $\bm{\phi}_{V}(s,a)$ and the $\epsilon$-log-covering number of
$\mathcal{F}$ follows from standard covering-number arguments.

#### Generalized Eluder Dimension

First, we show uncertainty $\mathcal{D}_{\mathcal{F}}$ has an analytic
expression for linear mixture MDPs in the following lemma.

######  Lemma D.1.

For $d$-dimensional, $B$-bounded linear mixture MDPs defined in Assumption
3.4, given any $\bm{X}=\\{(s_{t},a_{t},V_{t})\\}_{t\in[T]}$,
$\bm{\sigma}=\\{\sigma_{t}\\}_{t\in[T]}$, we have

$\mathcal{D}_{\mathcal{F}}(X_{t};X_{[t-1]},\sigma_{[t-1]})=\|\bm{\phi}_{t}\|_{\bm{\Sigma}_{t-1}},$

where $\bm{\phi}_{t}=\bm{\phi}_{V_{t}}(s_{t},a_{t})$ and
$\bm{\Sigma}_{t}=\sum_{s=1}^{t}\frac{1}{\sigma_{s}^{2}}\bm{\phi}_{s}\bm{\phi}_{s}^{\top}+\lambda/B\cdot\bm{I}$
for all $t\in[T]$.

###### Proof.

For any $f_{1},f_{2}\in\mathcal{F}$, let $\bm{\theta}\in\mathbb{R}^{d}$
satisfies for any $X=(s,a,V)$,

$f_{1}(X)-f_{2}(X)=\langle\bm{\theta},\bm{\phi}_{V}(s,a)\rangle,$

where the linear representation of $f_{1}$ and $f_{2}$ follows from (D.1).
Then we have

$\frac{(f_{1}(X_{t})-f_{2}(X_{t}))^{2}}{\sum_{s=1}^{t-1}\frac{1}{\sigma_{s}^{2}}(f_{1}(X_{s})-f_{2}(X_{s}))^{2}+\lambda}\overset{(a)}{\leq}\frac{\langle\bm{\theta},\bm{\phi}_{t}\rangle^{2}}{\sum_{s=1}^{t-1}\frac{1}{\sigma_{s}^{2}}\langle\bm{\theta},\bm{\phi}_{s}\rangle^{2}+\frac{\lambda}{B}\|\bm{\theta}\|_{2}^{2}}\overset{(b)}{=}{}\frac{\langle\bm{\theta},\bm{\phi}_{t}\rangle^{2}}{\|\bm{\theta}\|_{\bm{\Sigma}_{t-1}}^{2}}\overset{(c)}{\leq}\|\bm{\phi}_{t}\|_{\bm{\Sigma}_{t-1}^{-1}}^{2},$

where $(a)$ holds due to $\|\bm{\theta}\|_{2}\leq B$, $(b)$ holds due to the
definition of $\bm{\Sigma}_{t-1}$ and $(c)$ holds due to Cauchy-Schwarz
inequality. Thus
$\mathcal{D}_{\mathcal{F}}(X_{t};X_{[t-1]},\sigma_{[t-1]})=\|\bm{\phi}_{t}\|_{\bm{\Sigma}_{t-1}^{-1}}$
by Definition 3.2. ∎

Next, we come to the generalized Eluder dimension. We further assume for all
$t\in[T]$, $\sigma_{t}\geq\sigma_{\mathrm{min}}$, then it follows that

$\sum_{t=1}^{T}\min\left\\{1,\frac{1}{\sigma_{t}^{2}}\mathcal{D}_{\mathcal{F}}(X_{t};X_{[t-1]},\sigma_{[t-1]})\right\\}=\sum_{t=1}^{T}\min\left\\{1,\frac{1}{\sigma_{t}^{2}}\|\bm{\phi}_{t}\|_{\bm{\Sigma}_{t-1}^{-1}}^{2}\right\\}\leq
2d\log\left(1+\frac{TB}{d\lambda\sigma_{\mathrm{min}}^{2}}\right),$

where the inequality holds due to Lemma H.3. Taking maximum of the LHS over
$|\bm{X}|=T,\bm{\sigma}\geq\sigma_{\mathrm{min}}$ and the proof is completed
by Definition 3.2. ∎

##  Appendix E Proof of Theorem 4.4

###### Proof of Theorem 4.4.

Recall the definition of $\widehat{f}_{t+1}$ in (4.2), which implies

$\sum_{s=1}^{t}w_{s}^{2}(\widehat{f}_{t+1}(X_{s})-f_{*}(X_{s}))^{2}\leq
2\sum_{s=1}^{t}w_{s}^{2}(\widehat{f}_{t+1}(X_{s})-f_{*}(X_{s}))(Y_{s}-f_{*}(X_{s})).$

For any fixed $f\in\mathcal{F}$, denote
$E_{s}(f)=w_{s}^{2}(f(X_{s})-f_{*}(X_{s}))(Y_{s}-f_{*}(X_{s}))$, which is a
martingale difference sequence adapted to the filtration
$\\{\mathcal{G}_{s}\\}_{s\in[t]}$. Inspired by Agarwal et al. (2023), we are
to give a high-probability bound of $\sum_{s=1}^{t}E_{s}(f)$ in terms of
$\sum_{s=1}^{t}w_{s}^{2}(f(X_{s})-f_{*}(X_{s}))^{2}$. Note $|w_{s}|\leq W$ and
$f(X_{s}),f_{*}(X_{s}),Y_{s}$ are bounded in $[0,L]$, thereby the expectation
and summation of variances are upper bounded by

$\displaystyle|E_{s}(f)|\leq
W^{2}L^{2},\qquad\sum_{s=1}^{t}\mathbb{E}[E_{s}^{2}(f)|\mathcal{G}_{s-1}]\leq\sigma^{2}W^{2}L^{2}t.$

Simultaneously, the following problem-specific bounds hold:

$\displaystyle\max_{s\in[t]}|E_{s}(f)|$
$\displaystyle\overset{(a)}{\leq}L\max_{s\in[t]}w_{s}^{2}\mathcal{D}_{\mathcal{F}}(X_{s};X_{[s-1]},1/w_{[s-1]})\sqrt{\sum_{i=1}^{s-1}w_{i}^{2}(f(X_{i})-f_{*}(X_{i}))^{2}+\lambda}$
$\displaystyle\leq
L\max_{s\in[t]}w_{s}^{2}\mathcal{D}_{\mathcal{F}}(X_{s};X_{[s-1]},1/w_{[s-1]})\cdot\sqrt{\sum_{s=1}^{t-1}w_{s}^{2}(f(X_{s})-f_{*}(X_{s}))^{2}+\lambda},$
$\displaystyle\sum_{s=1}^{t}\mathbb{E}[E_{s}^{2}(f)|\mathcal{G}_{s-1}]$
$\displaystyle\leq\sigma^{2}\sum_{s=1}^{t}w_{s}^{2}(f(X_{s})-f_{*}(X_{s}))^{2},$

where $(a)$ holds due to the definition of $\mathcal{D}_{\mathcal{F}}$ in
Definition 3.2. We denote
$\mathcal{D}_{s}=\mathcal{D}_{\mathcal{F}}(X_{s};X_{[s-1]},1/w_{[s-1]})$ for
short. Let $\epsilon>0$ be a constant and $\mathcal{V}$ be a
$\epsilon$-covering net of $\mathcal{F}$. Applying Lemma H.1 with
$m=v=\sigma^{2}$,
$\iota_{t}=16\log\frac{2\mathcal{N}_{\mathcal{F}}(\epsilon)t^{2}(\log(\sigma^{2}W^{2}L^{2}t)+2)(\log(W^{2}L^{2})+2)}{\delta}$,
together with a union bound over $f\in\mathcal{V}$, with probability at least
$1-\delta/(2t^{2})$, we have for any fixed $t\geq 1$ and all
$f\in\mathcal{V}$,

$\displaystyle 2\sum_{s=1}^{t}E_{s}(f)$
$\displaystyle\leq\sqrt{\iota_{t}}\cdot\sqrt{\sigma^{2}\sum_{s=1}^{t}w_{s}^{2}(f(X_{s})-f_{*}(X_{s}))^{2}+\sigma^{4}}$
$\displaystyle\qquad+\iota_{t}\left(L\max_{s\in[t]}w_{s}^{2}\mathcal{D}_{s}\cdot\sqrt{\sum_{s=1}^{t-1}w_{s}^{2}(f(X_{s})-f_{*}(X_{s}))^{2}+\lambda}+\sigma^{2}\right)$
$\displaystyle\overset{(a)}{\leq}\left(\sqrt{\iota_{t}}\sigma+\iota_{t}L\max_{s\in[t]}w_{s}^{2}\mathcal{D}_{s}\right)\sqrt{\sum_{s=1}^{t}w_{s}^{2}(f(X_{s})-f_{*}(X_{s}))^{2}}+\sqrt{\lambda}\iota_{t}L\max_{s\in[t]}w_{s}^{2}\mathcal{D}_{s}+2\iota_{t}\sigma^{2}$
$\displaystyle\overset{(b)}{\leq}\frac{1}{2}\sum_{s=1}^{t}w_{s}^{2}(f(X_{s})-f_{*}(X_{s}))^{2}+\frac{1}{2}\left(\sqrt{\iota_{t}}\sigma+\iota_{t}L\max_{s\in[t]}w_{s}^{2}\mathcal{D}_{s}\right)^{2}$
$\displaystyle\qquad+\frac{1}{2}\left(\iota_{t}L\max_{s\in[t]}w_{s}^{2}\mathcal{D}_{s}\right)^{2}+\frac{1}{2}\lambda+2\iota_{t}\sigma^{2}$
$\displaystyle\overset{(c)}{\leq}\frac{1}{2}\sum_{s=1}^{t}w_{s}^{2}(f(X_{s})-f_{*}(X_{s}))^{2}+\frac{1}{2}\left(\sqrt{\iota_{t}}\sigma+2\iota_{t}L\max_{s\in[t]}w_{s}^{2}\mathcal{D}_{s}\right)^{2}+\frac{1}{2}\lambda+2\iota_{t}\sigma^{2},$

where $(a)$ holds due to $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for any $a,b\geq 0$
and $\iota_{t}\geq 1$, $(b)$ holds due to $\sqrt{ab}\leq a/2+b/2$ for any
$a,b\geq 0$, and $(c)$ holds due to $a^{2}+b^{2}\leq\left(a+b\right)^{2}$ for
any $a,b\geq 0$. Let $g\in\mathcal{V}$ such that
$\|g-\widehat{f}_{t+1}\|_{\infty}\leq\epsilon$, then

$\displaystyle\sum_{s=1}^{t}w_{s}^{2}(\widehat{f}_{t+1}(X_{s})-f_{*}(X_{s}))^{2}$
$\displaystyle\leq{}$ $\displaystyle
2\sum_{s=1}^{t}w_{s}^{2}(\widehat{f}_{t+1}(X_{s})-f_{*}(X_{s}))(Y_{s}-f_{*}(X_{s}))$
$\displaystyle\leq{}$ $\displaystyle
2\sum_{s=1}^{t}w_{s}^{2}(g(X_{s})-f_{*}(X_{s}))(Y_{s}-f_{*}(X_{s}))+\frac{2Lt}{\sigma_{\mathrm{min}}^{2}}\epsilon$
$\displaystyle\leq{}$
$\displaystyle\frac{1}{2}\sum_{s=1}^{t}w_{s}^{2}(g(X_{s})-f_{*}(X_{s}))^{2}+\frac{1}{2}\left(\sqrt{\iota_{t}}\sigma+2\iota_{t}L\max_{s\in[t]}w_{s}^{2}\mathcal{D}_{s}\right)^{2}+\frac{1}{2}\lambda+2\iota_{t}\sigma^{2}+\frac{2Lt}{\sigma_{\mathrm{min}}^{2}}\epsilon$
$\displaystyle\leq{}$
$\displaystyle\frac{1}{2}\sum_{s=1}^{t}w_{s}^{2}(\widehat{f}_{t+1}(X_{s})-f_{*}(X_{s}))^{2}+\frac{1}{2}\left(\sqrt{\iota_{t}}\sigma+2\iota_{t}L\max_{s\in[t]}w_{s}^{2}\mathcal{D}_{s}\right)^{2}+\frac{1}{2}\lambda+2\iota_{t}\sigma^{2}+\frac{3Lt}{\sigma_{\mathrm{min}}^{2}}\epsilon.$

That is for any fixed $t>0$, we have

$\displaystyle\sum_{s=1}^{t}w_{s}^{2}(\widehat{f}_{t+1}(X_{s})-f_{*}(X_{s}))^{2}$
$\displaystyle\leq\left(\sqrt{\iota_{t}}\sigma+2\iota_{t}L\max_{s\in[t]}w_{s}^{2}\mathcal{D}_{s}\right)^{2}+\lambda+4\iota_{t}\sigma^{2}+\frac{6Lt}{\sigma_{\mathrm{min}}^{2}}\epsilon$
$\displaystyle\leq\left(3\sqrt{\iota_{t}}\sigma+2\iota_{t}L\max_{s\in[t]}w_{s}^{2}\mathcal{D}_{s}+\sqrt{\lambda}+\sqrt{\frac{6Lt\epsilon}{\sigma_{\mathrm{min}}^{2}}}\right)^{2},$

where the second inequality holds due to $2\sqrt{ab}\leq a+b$ and
$a+b\leq(\sqrt{a}+\sqrt{b})^{2}$ for any $a,b\geq 0$. Finally, the result
holds through a union bound over all $t\geq 1$ and the fact that
$\sum_{t=1}^{\infty}\frac{1}{2t^{2}}\leq 1$. ∎

##  Appendix F Proof of Theorem 4.2

We define filtration $\\{\mathcal{G}_{k,h}\\}_{k\in[K],h\in[H]}$ as follows.
Let $\mathcal{G}_{k,h}$ be the $\sigma$-field generated by the state-action
pairs up to $h$-th step and $k$-th episode. That is
$\mathcal{G}_{k,h}=\sigma(\\{s^{i}_{h},a^{i}_{h}\\}_{(i,h)\in{[k-1]\times[H]}}\cup\\{s^{k}_{j},a^{k}_{j}\\}_{j\in[h]})$.
For constants $\sigma_{\mathrm{min}},\epsilon>0$, let
$\mathcal{N}_{\mathcal{F}}=\mathcal{N}_{\mathcal{F}}(\epsilon)$, and
$\dim_{\mathcal{F}}:=\dim_{\mathcal{F}}(\sigma_{\mathrm{min}},KH)$ be the
generalized Eluder dimension in Definition 3.2.

###  F.1 High Probability Events and Optimism

Let $\widehat{\mathcal{B}}_{k,m}$ denote the confidence region as follows:

$\widehat{\mathcal{B}}_{k,m}:=\left\\{f:\sum_{i=1}^{k-1}\sum_{h=1}^{H}\frac{1}{\bar{\sigma}_{i,h,m}^{2}}(\widehat{f}_{k,h,m}(z_{i,h,m})-f(z_{i,h,m}))^{2}\leq\widehat{\beta}_{k}^{2}\right\\},$
(F.1)

where

$\widehat{\beta}_{k}=3\sqrt{\iota_{k}}+2\frac{\iota_{k}}{\gamma^{2}}+\sqrt{\lambda}+\sqrt{6kH\epsilon/\sigma_{\mathrm{min}}^{2}}$
(F.2)

with
$\iota_{k}=16\log\frac{2\mathcal{N}_{\mathcal{F}}(\epsilon)k^{2}H^{2}(\log(kH/\sigma_{\mathrm{min}}^{2})+2)(\log(1/\sigma_{\mathrm{min}}^{2})+2)}{\delta}$.
We define event $\mathcal{E}$ as

$\mathcal{E}:=\\{f_{*}\in\widehat{\mathcal{B}}_{k,m}\text{ for all
}k\in[K],m\in\overline{[M]}\\}.$

The following lemmas hold.

######  Lemma F.1.

For any $k\in[K],m\in[M]$, if $f_{*}\in\widehat{\mathcal{B}}_{k,m}$, we have
for all $h\in[H]$,

$|\widehat{f}_{k,m}(z_{k,h,m})-f_{*}(z_{k,h,m})|\leq\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(z_{k,h,m};D_{k,m}).$

Furthermore,

$\displaystyle
V_{k,h}(s^{k}_{h})-r_{h}(s^{k}_{h},a^{k}_{h})-[\mathbb{P}V_{k,h+1}](s^{k}_{h},a^{k}_{h})$
$\displaystyle\leq
2\min\\{1,\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(z_{k,h,0};D_{k,0})\\},$
$\displaystyle|[\bar{\mathbb{V}}_{k,h}V_{k,h+1}^{2^{m}}](s^{k}_{h},a^{k}_{h})-[\mathbb{V}_{k,h}V_{k,h+1}^{2^{m}}](s^{k}_{h},a^{k}_{h})|$
$\displaystyle\leq E_{k,h,m}.$

###### Proof.

See Appendix G.1 for a detailed proof. ∎

######  Lemma F.2.

Event $\mathcal{E}$ holds with probability at least $1-(M+1)\delta$.

###### Proof.

See Appendix G.2 for a detailed proof. ∎

######  Lemma F.3.

On event $\mathcal{E}$, we have for all $k,h\in[K]\times[H]$,
$Q_{k,h}(\cdot,\cdot)\geq Q^{*}_{h}(\cdot,\cdot)$, $V_{k,h}(\cdot)\geq
V^{*}_{h}(\cdot)$.

###### Proof.

See Appendix G.3 for a detailed proof. ∎

###  F.2 Higher Order Expansion of MDPs

Inspired by Zhang et al. (2021b); Zhou and Gu (2022); Zhao et al. (2023), we
define the following quantities of MDPs. For all $k\in[K],h\in[H+1]$, We use
$I^{k}_{h}$ to denote the following events:

$I^{k}_{h}:=\operatorname{\mathds{1}}\left\\{\forall
m\in\overline{[M]},\sum_{j=1}^{h-1}\frac{1}{\bar{\sigma}_{k,j,m}^{2}}\mathcal{D}_{\mathcal{F}}^{2}(z_{k,j,m};D_{k,j-1,m})\leq
1\right\\}.$ (F.3)

Note $I^{k}_{h}$ is $\mathcal{G}_{k,h-1}$-measurable and monotonically
decreasing. We define $h_{k}$ for all $k\in[K]$ as the least $h$ such that
$I^{k}_{h}$ vanishes.

$h_{k}=\min\\{h\in[H+1]|I^{k}_{h}=0\\}.$ (F.4)

We use the quantity $G$ to denote the number of episodes when the uncertainty
quantity grows sharply:

$\displaystyle G=\sum_{k=1}^{K}(1-I^{k}_{H+1}).$ (F.5)

We use $\check{V}_{k,h}(s)$ to denote the estimation error between the
estimated value function and the optimal value function, and use
$\widetilde{V}_{k,h}(s)$ to denote the sub-optimality gap of policy $\pi^{k}$
at stage $h$:

$\displaystyle\check{V}_{k,h}(s)=V_{k,h}(s)-V_{h}^{*}(s),\quad\forall
s\in\mathcal{S},(k,h)\in[K]\times[H],$ (F.6)
$\displaystyle\widetilde{V}_{k,h}(s)=V_{h}^{*}(s)-V_{h}^{\pi^{k}}(s),\quad\forall
s\in\mathcal{S},(k,h)\in[K]\times[H].$ (F.7)

In addition, we use $\check{S}_{m},\widetilde{S}_{m},S_{m},Q_{m}$ to represent
the total variance of $2^{m}$-th order value functions
($\check{V}_{k,h+1}^{2^{m}}$, $\widetilde{V}_{k,h+1}^{2^{m}}$,
$V_{k,h+1}^{2^{m}}$, $(V^{*}_{h+1})^{2^{m}}$):

$\displaystyle\check{S}_{m}$
$\displaystyle=\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}[\mathbb{V}\check{V}_{k,h+1}^{2^{m}}](s_{h}^{k},a_{h}^{k}),$
(F.8) $\displaystyle\widetilde{S}_{m}$
$\displaystyle=\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}[\mathbb{V}\widetilde{V}_{k,h+1}^{2^{m}}](s_{h}^{k},a_{h}^{k}),$
(F.9) $\displaystyle S_{m}$
$\displaystyle=\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}[\mathbb{V}V_{k,h+1}^{2^{m}}](s_{h}^{k},a_{h}^{k}),$
(F.10) $\displaystyle Q_{m}$
$\displaystyle=\sum_{k=1}^{K}\sum_{h=1}^{H}[\mathbb{V}(V^{*}_{h+1})^{2^{m}}](s^{k}_{h},a^{k}_{h}).$
(F.11)

We further use $\mathcal{Q}_{0}^{*}$ to denote the maximum of $Q_{m}$:

$\mathcal{Q}_{0}^{*}=\max_{m\in\overline{[M]}}Q_{m}.$ (F.12)

Then, for $2^{m}$-th order value functions
($\check{V}_{k,h+1}^{2^{m}},\widetilde{V}_{k,h+1}^{2^{m}},V_{k,h+1}^{2^{m}}$),
we use $\check{A}_{m},\widetilde{A}_{m},A_{m}$ to denote the summation of
stochastic transition noise as follows:

$\displaystyle\check{A}_{m}$
$\displaystyle=\left|\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[[\mathbb{P}\check{V}_{k,h+1}^{2^{m}}](s_{h}^{k},a_{h}^{k})-\check{V}_{k,h+1}^{2^{m}}(s_{h+1}^{k})\right]\right|,$
(F.13) $\displaystyle\widetilde{A}_{m}$
$\displaystyle=\left|\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[[\mathbb{P}\widetilde{V}_{k,h+1}^{2^{m}}](s_{h}^{k},a_{h}^{k})-\widetilde{V}_{k,h+1}^{2^{m}}(s_{h+1}^{k})\right]\right|,$
(F.14) $\displaystyle A_{m}$
$\displaystyle=\left|\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[[\mathbb{P}V_{k,h+1}^{2^{m}}](s_{h}^{k},a_{h}^{k})-V_{k,h+1}^{2^{m}}(s_{h+1}^{k})\right]\right|.$
(F.15)

Next, we use $V_{0}$ to represent the total rewards and $V^{*}_{1}$ for the
average optimal value functions over $K$ episodes:

$\displaystyle V_{0}$
$\displaystyle=\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}r(s^{k}_{h},a^{k}_{h}),$
(F.16) $\displaystyle V^{*}_{1}$
$\displaystyle=\frac{1}{K}\sum_{k=1}^{K}V^{*}_{1}(s^{k}_{1}).$ (F.17)

Finally, we use the $R_{m}$ to denote the summation of bonuses:

$\displaystyle
R_{m}=\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\min\\{1,\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(z_{k,h,m};D_{k,m})\\}.$
(F.18)

Now, we introduce the following lemmas to build the connection between these
quantities.

######  Lemma F.4.

We have

$G\leq(M+1)\dim_{\mathcal{F}}.$ (F.19)

###### Proof.

See Appendix G.4 for a detailed proof. ∎

######  Lemma F.5.

On event $\mathcal{E}$, we have for all $m\in\overline{[M]}$,

$\displaystyle\check{S}_{m}$
$\displaystyle\leq\check{A}_{m+1}+G+2^{m+1}\cdot(2R_{0}),$ (F.20)
$\displaystyle\widetilde{S}_{m}$
$\displaystyle\leq\widetilde{A}_{m+1}+G+2^{m+1}\cdot(2R_{0}+\check{A}_{0}),$
(F.21) $\displaystyle S_{m}$ $\displaystyle\leq
A_{m+1}+G+2^{m+1}\cdot(V_{0}+2R_{0}).$ (F.22)

###### Proof.

See Appendix G.5 for a detailed proof. ∎

######  Lemma F.6.

With probability at least $1-3(M+1)\delta$, we have for all
$m\in\overline{[M]}$,

$\displaystyle\check{A}_{m}\leq\sqrt{\zeta\check{S}_{m}}+\zeta,$ (F.23)
$\displaystyle\widetilde{A}_{m}\leq\sqrt{\zeta\check{S}_{m}}+\zeta,$ (F.24)
$\displaystyle A_{m}\leq\sqrt{\zeta S_{m}}+\zeta,$ (F.25)

where $\zeta=8\log(2(\log(KH)+2)/\delta)$. We denote the corresponding event
by $\mathcal{A}$.

###### Proof.

See Appendix G.6 for a detailed proof. ∎

######  Lemma F.7.

On event $\mathcal{E}\cup\mathcal{A}$, we have for all $m\in\overline{[M]}$,

$\check{A}_{m}\leq\sqrt{\zeta}\cdot\sqrt{\check{A}_{m+1}+G+2^{m+1}\cdot(2R_{0})}+\zeta.$
(F.26)

And

$\displaystyle\check{A}_{0}$ $\displaystyle\leq 2\sqrt{2\zeta
R_{0}}+3\sqrt{\zeta G}+7\zeta,$ (F.27) $\displaystyle\check{A}_{1}$
$\displaystyle\leq 4\sqrt{\zeta R_{0}}+3\sqrt{\zeta G}+7\zeta.$ (F.28)

###### Proof.

See Appendix G.7 for a detailed proof. ∎

######  Lemma F.8.

On event $\mathcal{E}\cup\mathcal{A}$, we have

$\widetilde{A}_{0}\leq 4\sqrt{2\zeta R_{0}}+6\sqrt{\zeta G}+15\zeta.$ (F.29)

###### Proof.

See Appendix G.8 for a detailed proof. ∎

######  Lemma F.9.

We have

$V_{0}\leq V^{*}_{1}K+A_{0}+\check{A}_{0}.$ (F.30)

###### Proof.

See Appendix G.9 for a detailed proof. ∎

######  Lemma F.10 (Formal version of Lemma 4.6).

Let $\gamma^{2}\leq\log\mathcal{N}_{\mathcal{F}}$. On event $\mathcal{E}$, we
have for all $m\in\overline{[M-1]}$,

$R_{m}\leq
4\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{S_{m}+2R_{m+1}+KH\sigma_{\mathrm{min}}^{2}}+24\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}.$
(F.31)

###### Proof.

See Appendix G.10 for a detailed proof. ∎

######  Lemma F.11 (Formal version of Lemma 4.7).

On event $\mathcal{E}\cup\mathcal{A}$, we have

$\displaystyle R_{0}+\check{A}_{0}\leq
32\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}R_{0}}+15\widehat{\beta}_{K}\sqrt{2\dim_{\mathcal{F}}}\cdot\sqrt{\mathcal{Q}_{0}^{*}+G+KH\sigma_{\mathrm{min}}^{2}}+587\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}.$
(F.32)

###### Proof.

See Appendix G.11 for a detailed proof. ∎

######  Lemma F.12.

On event $\mathcal{E}\cup\mathcal{A}$, we have

$R_{0}+A_{0}\leq
32\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{V^{*}_{1}K+\check{A}_{0}}+30\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{G+KH\sigma_{\mathrm{min}}^{2}}+1174\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}.$
(F.33)

###### Proof.

See Appendix G.12 for a detailed proof. ∎

###  F.3 Regret Analysis

###### Proof of Theorem 4.2.

On event $\mathcal{E}\cup\mathcal{A}$, which holds with probability at least
$1-4(M+1)\delta$ by Lemma F.2, F.6 and a union bound, we have all lemmas in
this section hold. By the optimism implied by Lemma F.3, we have

$\mathrm{Regret}(K)=\sum_{k=1}^{K}\left[V^{*}_{1}(s^{k}_{1})-V^{\pi^{k}}_{1}(s^{k}_{1})\right]\leq\sum_{k=1}^{K}\left[V_{k,1}(s^{k}_{1})-V^{\pi^{k}}_{1}(s^{k}_{1})\right].$
(F.34)

We further use Lemma F.13 to bound the regret with the higher-order quantities
defined in Section F.2.

######  Lemma F.13.

On event $\mathcal{E}$, we have

$\sum_{k=1}^{K}\left[V_{k,1}(s^{k}_{1})-V^{\pi^{k}}(s^{k}_{1})\right]\leq
2R_{0}+\check{A}_{0}+\widetilde{A}_{0}+G.$ (F.35)

###### Proof.

See Appendix G.13 for a detailed proof. ∎

On one hand, we have

$\displaystyle 2R_{0}+\check{A}_{0}+\widetilde{A}_{0}+G$
$\displaystyle\overset{(a)}{\leq}{}$ $\displaystyle
64\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}R_{0}}+30\widehat{\beta}_{K}\sqrt{2\dim_{\mathcal{F}}}\cdot\sqrt{\mathcal{Q}_{0}^{*}+G+KH\sigma_{\mathrm{min}}^{2}}+1174\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}$
$\displaystyle\quad+4\sqrt{2\zeta R_{0}}+6\sqrt{\zeta G}+G$
$\displaystyle\overset{(b)}{=}{}$
$\displaystyle\widetilde{O}\left(\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{\mathcal{Q}_{0}^{*}+KH\sigma_{\mathrm{min}}^{2}}+\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}\right),$
(F.36)

where $(a)$ holds due to (F.32) and (F.29), while we utilize
$\zeta\leq\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}$ (which is trivial since
$\zeta$ only consists of logarithmic terms), $x\leq a\sqrt{x}+b$ implies
$x\leq a^{2}+2b$ for any $x\geq 0$ and (F.19) for $(b)$. On the other hand, we
have

$\displaystyle 2R_{0}+\check{A}_{0}+\widetilde{A}_{0}+G$
$\displaystyle\overset{(a)}{\leq}{}$ $\displaystyle
64\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{V^{*}_{1}K+\check{A}_{0}}+60\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{G+KH\sigma_{\mathrm{min}}^{2}}+2348\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}$
$\displaystyle\quad+2\sqrt{2\zeta R_{0}}+3\sqrt{\zeta G}+7\zeta+4\sqrt{2\zeta
R_{0}}+6\sqrt{\zeta G}+G$ $\displaystyle\overset{(b)}{=}{}$
$\displaystyle\widetilde{O}\left(\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{V^{*}_{1}K+KH\sigma_{\mathrm{min}}^{2}}+\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}\right),$
(F.37)

where $(a)$ holds due to (F.33), (F.27) and (F.29), while we utilize
$\zeta\leq\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}$, $x\leq a\sqrt{x}+b$
implies $x\leq a^{2}+2b$ for any $x\geq 0$ and (F.19) in $(b)$. Combining
(F.34), (F.35), (F.36) and (F.37), we have

$\mathrm{Regret}(K)=\widetilde{O}\left(\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{\min\\{\mathcal{Q}_{0}^{*},V^{*}_{1}K\\}+KH\sigma_{\mathrm{min}}^{2}}+\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}\right).$

Recall that according to (F.2),

$\widehat{\beta}_{K}=3\sqrt{\iota_{K}}+2\frac{\iota_{K}}{\gamma^{2}}+\sqrt{\lambda}+\sqrt{6kH\epsilon/\sigma_{\mathrm{min}}^{2}}$

with $\iota_{K}=\widetilde{O}(\log\mathcal{N}_{\mathcal{F}})$. Moreover,
setting
$\lambda=\log\mathcal{N}_{\mathcal{F}},\sigma_{\mathrm{min}}^{2}=\sqrt{\dim_{\mathcal{F}}\log\mathcal{N}_{\mathcal{F}}}/(KH),\gamma^{2}=\sqrt{\log\mathcal{N}_{\mathcal{F}}},\epsilon=\log\mathcal{N}_{\mathcal{F}}\sigma_{\mathrm{min}}^{2}/(KH)$,
we have
$\widehat{\beta}_{K}=\widetilde{O}(\sqrt{\log\mathcal{N}_{\mathcal{F}}})$ and
$KH\sigma_{\mathrm{min}}^{2}=\sqrt{\dim_{\mathcal{F}}\log\mathcal{N}_{\mathcal{F}}}$,
which yields a high-probability regret bound

$\mathrm{Regret}(K)=\widetilde{O}\left(\sqrt{\dim_{\mathcal{F}}\log\mathcal{N}_{\mathcal{F}}}\cdot\sqrt{\min\\{\mathcal{Q}_{0}^{*},V^{*}_{1}K\\}}+\dim_{\mathcal{F}}\log\mathcal{N}_{\mathcal{F}}\right).$

Notice $\mathcal{Q}^{*}=\min\\{\mathcal{Q}_{0}^{*},V^{*}_{1}K\\}$, then the
proof is completed. ∎

##  Appendix G Missing Proofs in Section F

###  G.1 Proof of Lemma F.1

###### Proof of Lemma F.1.

Recall $D_{k,m}=\\{z_{i,h,m},\bar{\sigma}_{i,h,m}\\}_{(i,h)\in[k-1]\times[H]}$
and $D_{k,h,m}=D_{k,m}\cup\\{z_{k,j,m},\bar{\sigma}_{k,j,m}\\}_{j\in[h]}$. If
$f_{*}\in\widehat{\mathcal{B}}_{k,m}$, it follows that

$\displaystyle|\widehat{f}_{k,m}(z_{k,h,m})-f_{*}(z_{k,h,m})|$
$\displaystyle\overset{(a)}{\leq}{}$
$\displaystyle\mathcal{D}_{\mathcal{F}}(z_{k,h,m};D_{k,m})\sqrt{\sum_{i=1}^{k-1}\sum_{h=1}^{H}\frac{1}{\bar{\sigma}_{i,h,m}^{2}}(\widehat{f}_{k,h,m}(z_{i,h,m})-f_{*}(z_{i,h,m}))^{2}+\lambda}$
$\displaystyle\overset{(b)}{\leq}{}$
$\displaystyle(\widehat{\beta}_{k}+\sqrt{\lambda})\mathcal{D}_{\mathcal{F}}(z_{k,h,m};D_{k,m})$
$\displaystyle\overset{(c)}{\approx}{}$
$\displaystyle\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(z_{k,h,m};D_{k,m}),$

where $(a)$ holds due to the definition of $\mathcal{D}_{\mathcal{F}}$ in
Definition 3.2, $(b)$ holds due to $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for any
$a,b\geq 0$, $(c)$ holds due to $\sqrt{\lambda}=O(\widehat{\beta}_{k})$,
therefore we omit the term $\sqrt{\lambda}$ in the proof for simplicity.
Furthermore, we have

$\displaystyle
V_{k,h}(s^{k}_{h})-r_{h}(s^{k}_{h},a^{k}_{h})-[\mathbb{P}V_{k,h+1}](s^{k}_{h},a^{k}_{h})$
$\displaystyle={}$
$\displaystyle\min\\{1,r_{h}(s^{k}_{h},a^{k}_{h})+\widehat{f}_{k,m}(z_{k,h,0})+\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(z_{k,h,0};D_{k,0})\\}-r_{h}(s^{k}_{h},a^{k}_{h})-f_{*}(z_{k,h,0})$
$\displaystyle\leq{}$
$\displaystyle\min\\{1,2\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(z_{k,h,0};D_{k,0})\\}.$

And

$\displaystyle|[\bar{\mathbb{V}}_{k,h}V_{k,h+1}^{2^{m}}](s^{k}_{h},a^{k}_{h})-[\mathbb{V}_{k,h}V_{k,h+1}^{2^{m}}](s^{k}_{h},a^{k}_{h})|$
$\displaystyle={}$
$\displaystyle|[f_{k,m+1}(z_{k,h,m+1})-f_{k,m}^{2}(z_{k,h,m})]-[f_{*}(z_{k,h,m+1})-f_{*}^{2}(z_{k,h,m})]|$
$\displaystyle\leq{}$
$\displaystyle|f_{k,m+1}(z_{k,h,m+1})-f_{*}(z_{k,h,m+1})|+|f_{k,m}^{2}(z_{k,h,m})-f_{*}^{2}(z_{k,h,m})|$
$\displaystyle={}$
$\displaystyle|f_{k,m+1}(z_{k,h,m+1})-f_{*}(z_{k,h,m+1})|+|f_{k,m}(z_{k,h,m})+f_{*}(z_{k,h,m})|\cdot|f_{k,m}(z_{k,h,m})-f_{*}(z_{k,h,m})|$
$\displaystyle\leq{}$
$\displaystyle\min\\{1,\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(z_{k,h,m+1};D_{k,m+1})\\}+\min\\{1,2\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(z_{k,h,m};D_{k,m})\\}$
$\displaystyle={}$ $\displaystyle E_{k,h,m},$

where the last inequality holds due to
$f_{k,m}(z_{k,h,m}),f_{*}(z_{k,h,m})\in[0,1]$. ∎

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

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

We will prove the statement by Theorem 4.4 and induction. For each
$m\in\overline{[M-1]}$, denote
$\xi_{k,h,m}:=f_{*}(z_{k,h,m})+\operatorname{\mathds{1}}\\{f_{*}\in\widehat{\mathcal{B}}_{k,m}\cap\widehat{\mathcal{B}}_{k,m+1}\\}[y_{k,h,m}-f_{*}(z_{k,h,m})]$,
and $\xi_{k,h,M}:=y_{k,h,M}$. Then we have for all $m\in\overline{[M]}$,
$\xi_{k,h,m}\in\mathcal{G}_{k,h}$,
$\mathbb{E}[\xi_{k,h,m}|\mathcal{G}_{k,h}]=f_{*}(z_{k,h,m})$. Recall the
definition of $\bar{\sigma}_{k,h,m}$ in (4) of Algorithm 2, for
$m\in\overline{[M-1]}$, we have

$\displaystyle\bar{\sigma}_{k,h,m}^{-2}\operatorname{{\rm
Var}}[\xi_{k,h,m}|\mathcal{G}_{k,h,m}]$
$\displaystyle=\bar{\sigma}_{k,h,m}^{-2}\operatorname{\mathds{1}}\\{f_{*}\in\widehat{\mathcal{B}}_{k,m}\cap\widehat{\mathcal{B}}_{k,m+1}\\}\operatorname{{\rm
Var}}[y_{k,h,m}|\mathcal{G}_{k,h,m}]$
$\displaystyle=\bar{\sigma}_{k,h,m}^{-2}\operatorname{\mathds{1}}\\{f_{*}\in\widehat{\mathcal{B}}_{k,m}\cap\widehat{\mathcal{B}}_{k,m+1}\\}[\mathbb{V}V_{k,h+1}^{2^{m}}](s^{k}_{h},a^{k}_{h})$
$\displaystyle=\bar{\sigma}_{k,h,m}^{-2}\operatorname{\mathds{1}}\\{f_{*}\in\widehat{\mathcal{B}}_{k,m}\cap\widehat{\mathcal{B}}_{k,m+1}\\}[[\mathbb{P}V_{k,h+1}^{2^{m+1}}](s^{k}_{h},a^{k}_{h})-[\mathbb{P}V_{k,h+1}^{2^{m}}]^{2}(s^{k}_{h},a^{k}_{h})]$
$\displaystyle=\bar{\sigma}_{k,h,m}^{-2}\operatorname{\mathds{1}}\\{f_{*}\in\widehat{\mathcal{B}}_{k,m}\cap\widehat{\mathcal{B}}_{k,m+1}\\}[f_{*}(z_{k,h,m+1})-f_{*}^{2}(z_{k,h,m})]$
$\displaystyle\leq\bar{\sigma}_{k,h,m}^{-2}[f_{k,m+1}(z_{k,h,m+1})-f_{k,m}^{2}(z_{k,h,m})+\min\\{1,\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(z_{k,h,m+1};D_{k,m+1})$
$\displaystyle\qquad\min\\{1,2\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(z_{k,h,m};D_{k,m})\\}\\}]$
$\displaystyle=\bar{\sigma}_{k,h,m}^{-2}[[\bar{\mathbb{V}}_{k,m}V_{k,h+1}^{2^{m}}](s_{h}^{k},a_{h}^{k})+E_{k,h,m}]$
$\displaystyle\leq 1,$

where the first inequality holds due to Lemma F.1 and
$f_{k,m}(z_{k,h,m})\in[0,1]$. And

$\bar{\sigma}_{k,h,M}^{-2}\operatorname{{\rm
Var}}[\xi_{k,h,M}|\mathcal{G}_{k,h,m}]\leq\bar{\sigma}_{k,h,M}^{-2}\leq 1.$

Furthermore, for all $m\in\overline{[M]}$, we have

$\bar{\sigma}_{k,h,m}^{-2}\mathcal{D}_{\mathcal{F}}^{2}(z_{k,h,m};D_{k,m})\leq
1/\gamma^{2}.$

For each $m\in\overline{[M]}$, we define

$\widetilde{f}_{k+1,m}=\mathop{\mathrm{argmin}}_{f\in\mathcal{F}}\sum_{i=1}^{k}\sum_{h=1}^{H}(f(z_{i,h,m})-\xi_{i,h,m})^{2}.$
(G.1)

Applying Theorem 4.4 using $X_{t}=z_{k,h,m}$, $Y_{t}=\xi_{k,h,m}$,
$w_{t}=1/\bar{\sigma}_{k,h,m}$, together with a union bound, with probability
at least $1-(M+1)\delta$, we have for all $m\in\overline{[M]},k\in[K]$,

$\sum_{i=1}^{k-1}\sum_{h=1}^{H}\frac{1}{\bar{\sigma}_{i,h,m}^{2}}(\widetilde{f}_{k,h,m}(z_{i,h,m})-f_{*}(z_{i,h,m}))^{2}\leq
3\sqrt{\iota_{k}}+2\frac{\iota_{k}}{\gamma^{2}}+\sqrt{\lambda}+\sqrt{6kH\epsilon/\sigma_{\mathrm{min}}^{2}}=\widehat{\beta}_{k}^{2},$
(G.2)

where
$\iota_{k}=16\log\frac{2\mathcal{N}_{\mathcal{F}}(\epsilon)k^{2}H^{2}(\log(kH/\sigma_{\mathrm{min}}^{2})+2)(\log(1/\sigma_{\mathrm{min}}^{2})+2)}{\delta}$.

We continue the proof by induction over $(k,m)\in[K]\times\overline{[M]}$.
First, for $k=1$, $m\in\overline{[M]}$, the result holds trivially.

Next, for $k\in[K],m=M$, we have $\xi_{k,h,M}=y_{k,h,M}$, therefore
$\widetilde{f}_{k,M}=\widehat{f}_{k,M}$ by (G.1), which implies
$\widehat{f}_{k,M}\in\widehat{\mathcal{B}}_{k,M}$ by (G.2).

Last, for all $k\in[k],m\in\overline{[M-1]}$, we have the following
observations:

$\displaystyle
f_{*}\in\widehat{\mathcal{B}}_{k,m}\cap\widehat{\mathcal{B}}_{k,m+1}$ (G.3)
$\displaystyle\Longrightarrow{}$ $\displaystyle\xi_{k,h,m}=y_{k,h,m}\text{ for
all }h\in[H]$ $\displaystyle\overset{\eqref{eq:tildef}}{\Longrightarrow}{}$
$\displaystyle\widetilde{f}_{k+1,m}=\widehat{f}_{k+1,m}$
$\displaystyle\overset{\eqref{eq:concentration-proxy}}{\Longrightarrow}{}$
$\displaystyle\widehat{f}_{k+1,m}\in\widehat{\mathcal{B}}_{k+1,m}.$

For any $k\in K$, we assume
$\widehat{f}_{k^{\prime},m}\in\widehat{\mathcal{B}}_{k^{\prime},m}$ for all
$k^{\prime}\leq k,m\in\overline{[M]}$. Notice
$\widehat{f}_{k+1,M}\in\widehat{\mathcal{B}}_{k+1,M}$, using (G.3), we have
$\widehat{f}_{k+1,m}\in\widehat{\mathcal{B}}_{k+1,m}$ for all
$m\in\overline{[M]}$. Then the proof is completed by induction. ∎

###  G.3 Proof of Lemma F.3

###### Proof of Lemma F.3.

We prove the optimism by induction. When $h=H+1$, we have
$V_{k,H+1}(\cdot)=V^{*}_{H+1}(\cdot)=0$, and the result holds trivially. We
assume the statement is true for all $h+1$, and prove the case of $h$. For any
$(s,a)$, if $Q_{k,h}(s,a)=1$, then $Q_{k,h}(s,a)=1\geq Q^{*}_{h}(s,a)$.
Otherwise, we have

$\displaystyle Q_{k,h}(s,a)-Q^{*}_{h}(s,a)$
$\displaystyle=f_{k,0}(s,a,V_{k,h+1})-f_{*}(s,a,V^{*}_{h+1})+\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(s,a,V_{k,h+1};D_{k,0})$
$\displaystyle\geq
f_{k,0}(s,a,V_{k,h+1})-f_{*}(s,a,V_{k,h+1})+\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(s,a,V_{k,h+1};D_{k,0})$
$\displaystyle\geq 0,$

where the first inequality holds due to $V_{k,h+1}(\cdot)\geq
V^{*}_{h+1}(\cdot)$ and the second holds due to Lemma F.1. That is, we have
$Q_{k,h}(\cdot,\cdot)\geq Q^{*}_{h}(\cdot,\cdot)$ and therefore
$V_{k,h}(\cdot)\geq V^{*}_{h}(\cdot)$. Then the proof is completed by
induction. ∎

###  G.4 Proof of Lemma F.4

###### Proof of Lemma F.4.

Recall the definition of $I_{h}^{k}$, we have

$1-I_{H+1}^{k}=1\Leftrightarrow\exists m\in\overline{[M]},\
\sum_{h=1}^{H}\frac{1}{\bar{\sigma}_{k,h,m}^{2}}\mathcal{D}_{\mathcal{F}}^{2}(z_{k,h,m};D_{k,h-1,m})>1.$

Let $\mathcal{D}_{m}$ denote the indices $k$ such that

$\displaystyle\mathcal{D}_{m}:=\bigg{\\{}k\in[K]:\sum_{h=1}^{H}\frac{1}{\bar{\sigma}_{k,h,m}^{2}}\mathcal{D}_{\mathcal{F}}^{2}(z_{k,h,m};D_{k,h-1,m})>1\bigg{\\}}.$

Then we have
$G\leq|\bigcup_{m=0}^{M}\mathcal{D}_{m}|\leq\sum_{m=0}^{M}|\mathcal{D}_{m}|$.
For any $m\in\overline{[M]}$, we have

$\displaystyle|\mathcal{D}_{m}|$
$\displaystyle\leq\sum_{k=1}^{K}\min\left\\{1,\sum_{h=1}^{H}\frac{1}{\bar{\sigma}_{k,h,m}^{2}}\mathcal{D}_{\mathcal{F}}^{2}(z_{k,h,m};D_{k,h-1,m})\right\\}$
$\displaystyle\leq\sum_{k=1}^{K}\sum_{h=1}^{H}\min\left\\{1,\frac{1}{\bar{\sigma}_{k,h,m}^{2}}\mathcal{D}_{\mathcal{F}}^{2}(z_{k,h,m};D_{k,h-1,m})\right\\}$
$\displaystyle\leq\dim_{\mathcal{F}}.$

Taking the summation over $m\in\overline{[M]}$ gives the upper bound of $G$. ∎

###  G.5 Proof of Lemma F.5

###### Proof of Lemma F.5.

We are to bound $\check{S}_{m},\widetilde{S}_{m}$ and $S_{m}$ separately with
similar arguments.

#### Bound $\check{S}_{m}$

Recall the definition of $\check{S}_{m}$ in (F.8), we have

$\displaystyle\check{S}_{m}$
$\displaystyle=\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}[\mathbb{V}\check{V}_{k,h+1}^{2^{m}}](s_{h}^{k},a_{h}^{k})$
$\displaystyle=\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[[\mathbb{P}\check{V}_{k,h+1}^{2^{m+1}}](s_{h}^{k},a_{h}^{k})-[\mathbb{P}\check{V}_{k,h+1}^{2^{m}}]^{2}(s_{h}^{k},a_{h}^{k})^{2}\right]$
$\displaystyle=\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[[\mathbb{P}\check{V}_{k,h+1}^{2^{m+1}}](s_{h}^{k},a_{h}^{k})-\check{V}_{k,h+1}^{2^{m+1}}(s_{h+1}^{k})\right]+\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[\check{V}_{k,h}^{2^{m+1}}(s_{h}^{k})-[\mathbb{P}\check{V}_{k,h+1}^{2^{m}}]^{2}(s_{h}^{k},a_{h}^{k})\right]$
$\displaystyle\qquad+\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left(\check{V}_{k,h+1}^{2^{m+1}}(s_{h+1}^{k})-\check{V}_{k,h}^{2^{m+1}}(s_{h}^{k})\right)$
$\displaystyle\leq\check{A}_{m+1}+\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[\check{V}_{k,h}^{2^{m+1}}(s_{h}^{k})-[\mathbb{P}\check{V}_{k,h+1}^{2^{m}}]^{2}(s_{h}^{k},a_{h}^{k})\right]+\sum_{k=1}^{K}(1-I^{k}_{h_{k}})\check{V}_{k,h_{k}}^{2^{m+1}}(s_{h_{k}}^{k})$
$\displaystyle\leq\check{A}_{m+1}+G+\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[\check{V}_{k,h}^{2^{m+1}}(s_{h}^{k})-[\mathbb{P}\check{V}_{k,h+1}^{2^{m}}]^{2}(s_{h}^{k},a_{h}^{k})\right],$
(G.4)

where $h_{k}$ is defined in (F.4) and the last inequality holds since
$|\check{V}_{k,h}(s_{h}^{k})|\leq 1$ and $I^{k}_{h}$ is monotonically
decreasing. For the third term in (G.4), we have

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[\check{V}_{k,h}^{2^{m+1}}(s_{h}^{k})-[\mathbb{P}\check{V}_{k,h+1}^{2^{m}}]^{2}(s_{h}^{k},a_{h}^{k})\right]$
$\displaystyle\overset{(a)}{\leq}{}$
$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[\check{V}_{k,h}^{2^{m+1}}(s_{h}^{k})-[\mathbb{P}\check{V}_{k,h+1}]^{2^{m+1}}(s_{h}^{k},a_{h}^{k})\right]$
$\displaystyle={}$
$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[\check{V}_{k,h}(s_{h}^{k})-[\mathbb{P}\check{V}_{k,h+1}](s_{h}^{k},a_{h}^{k})\right]\prod_{i=0}^{m}\left[\check{V}_{k,h}^{2^{i}}(s_{h}^{k})+[\mathbb{P}\check{V}_{k,h+1}]^{2^{i}}(s_{h}^{k},a_{h}^{k})\right]$
$\displaystyle\leq{}$ $\displaystyle
2^{m+1}\sum_{k=1}^{K}\sum_{h=1}^{H}I_{h}^{k}\max\left\\{\check{V}_{k,h}(s_{h}^{k})-[\mathbb{P}\check{V}_{k,h+1}](s_{h}^{k},a_{h}^{k}),0\right\\}$
$\displaystyle\overset{(b)}{\leq}{}$ $\displaystyle
2^{m+1}\sum_{k=1}^{K}\sum_{h=1}^{H}I_{h}^{k}\max\left\\{V_{k,h}(s_{h}^{k})-r(s_{h}^{k},a_{h}^{k})-[\mathbb{P}V_{k,h+1}](s_{h}^{k},a_{h}^{k}),0\right\\}$
$\displaystyle\overset{(c)}{\leq}{}$ $\displaystyle
2^{m+1}\sum_{k=1}^{K}\sum_{h=1}^{H}I_{h}^{k}\cdot
2\min\\{1,\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(z_{k,h,0};D_{k,0})\\}$
$\displaystyle={}$ $\displaystyle 2^{m+1}\cdot(2R_{0}),$ (G.5)

where $(a)$ holds due to $\mathbb{E}[X^{2}]\geq(\mathbb{E}[X])^{2}$, $(b)$
holds due to the definition of $\check{V}_{k,h}$ and $V^{*}_{h}(s^{k}_{h})\geq
r(s^{k}_{h},a^{k}_{h})+[\mathbb{P}V^{*}_{h+1}](s^{k}_{h},a^{k}_{h})$, while
$(c)$ is due to Lemma F.1. Substituting (G.5) into (G.4), we have

$\check{S}_{m}\leq\check{A}_{m+1}+G+2^{m+1}\cdot(2R_{0}).$

#### Bound $\widetilde{S}_{m}$

Recall the definition of $\widetilde{S}_{m}$ in (F.9), we have

$\displaystyle\widetilde{S}_{m}$
$\displaystyle=\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}[\mathbb{V}\widetilde{V}_{k,h+1}^{2^{m}}](s_{h}^{k},a_{h}^{k})$
$\displaystyle=\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[[\mathbb{P}\widetilde{V}_{k,h+1}^{2^{m+1}}](s_{h}^{k},a_{h}^{k})-[\mathbb{P}\widetilde{V}_{k,h+1}^{2^{m}}]^{2}(s_{h}^{k},a_{h}^{k})^{2}\right]$
$\displaystyle=\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[[\mathbb{P}\widetilde{V}_{k,h+1}^{2^{m+1}}](s_{h}^{k},a_{h}^{k})-\widetilde{V}_{k,h+1}^{2^{m+1}}(s_{h+1}^{k})\right]+\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[\widetilde{V}_{k,h}^{2^{m+1}}(s_{h}^{k})-[\mathbb{P}\widetilde{V}_{k,h+1}^{2^{m}}]^{2}(s_{h}^{k},a_{h}^{k})\right]$
$\displaystyle\qquad+\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left(\widetilde{V}_{k,h+1}^{2^{m+1}}(s_{h+1}^{k})-\widetilde{V}_{k,h}^{2^{m+1}}(s_{h}^{k})\right)$
$\displaystyle\leq\widetilde{A}_{m+1}+\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[\widetilde{V}_{k,h}^{2^{m+1}}(s_{h}^{k})-[\mathbb{P}\widetilde{V}_{k,h+1}^{2^{m}}]^{2}(s_{h}^{k},a_{h}^{k})\right]+\sum_{k=1}^{K}(1-I^{k}_{h_{k}})\widetilde{V}_{k,h_{k}}^{2^{m+1}}(s_{h_{k}}^{k})$
$\displaystyle\leq\widetilde{A}_{m+1}+G+\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[\widetilde{V}_{k,h}^{2^{m+1}}(s_{h}^{k})-[\mathbb{P}\widetilde{V}_{k,h+1}^{2^{m}}]^{2}(s_{h}^{k},a_{h}^{k})\right],$
(G.6)

where $h_{k}$ is defined in (F.4) and the last inequality holds since
$|\widetilde{V}_{k,h}(s_{h}^{k})|\leq 1$ and $I^{k}_{h}$ is monotonically
decreasing. For the third term in (G.6), we have

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[\widetilde{V}_{k,h}^{2^{m+1}}(s_{h}^{k})-[\mathbb{P}\widetilde{V}_{k,h+1}^{2^{m}}]^{2}(s_{h}^{k},a_{h}^{k})\right]$
$\displaystyle\overset{(a)}{\leq}{}$
$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[\widetilde{V}_{k,h}^{2^{m+1}}(s_{h}^{k})-[\mathbb{P}\widetilde{V}_{k,h+1}]^{2^{m+1}}(s_{h}^{k},a_{h}^{k})\right]$
$\displaystyle={}$
$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[\widetilde{V}_{k,h}(s_{h}^{k})-[\mathbb{P}\widetilde{V}_{k,h+1}](s_{h}^{k},a_{h}^{k})\right]\prod_{i=0}^{m}\left[\widetilde{V}_{k,h}^{2^{i}}(s_{h}^{k})+[\mathbb{P}\widetilde{V}_{k,h+1}]^{2^{i}}(s_{h}^{k},a_{h}^{k})\right]$
$\displaystyle\leq{}$ $\displaystyle
2^{m+1}\sum_{k=1}^{K}\sum_{h=1}^{H}I_{h}^{k}\max\left\\{\widetilde{V}_{k,h}(s_{h}^{k})-[\mathbb{P}\widetilde{V}_{k,h+1}](s_{h}^{k},a_{h}^{k}),0\right\\}$
$\displaystyle\overset{(b)}{=}{}$ $\displaystyle
2^{m+1}\sum_{k=1}^{K}\sum_{h=1}^{H}I_{h}^{k}\max\left\\{V^{*}_{h}(s_{h}^{k})-r(s_{h}^{k},a_{h}^{k})-[\mathbb{P}V^{*}_{h+1}](s_{h}^{k},a_{h}^{k}),0\right\\}$
$\displaystyle\overset{(c)}{\leq}{}$ $\displaystyle
2^{m+1}\sum_{k=1}^{K}\sum_{h=1}^{H}I_{h}^{k}\max\left\\{V_{k,h}(s_{h}^{k})-r(s_{h}^{k},a_{h}^{k})-[\mathbb{P}V_{k,h+1}](s_{h}^{k},a_{h}^{k}),0\right\\}+|[\mathbb{P}\check{V}_{k,h+1}](s_{h}^{k},a_{h}^{k})-\check{V}_{k,h+1}(s_{h+1}^{k})|$
$\displaystyle\overset{(d)}{\leq}{}$ $\displaystyle
2^{m+1}\sum_{k=1}^{K}\sum_{h=1}^{H}I_{h}^{k}\left[2\min\\{1,\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(z_{k,h,0};D_{k,0})\\}+|[\mathbb{P}\check{V}_{k,h+1}](s_{h}^{k},a_{h}^{k})-\check{V}_{k,h+1}(s_{h+1}^{k})|\right]$
$\displaystyle\leq{}$ $\displaystyle 2^{m+1}\cdot(2R_{0}+\check{A}_{0}),$
(G.7)

where $(a)$ holds due to $\mathbb{E}[X^{2}]\geq(\mathbb{E}[X])^{2}$, $(b)$
holds due to the definition of $\widetilde{V}_{k,h}$ and
$V^{\pi^{k}}_{h}(s^{k}_{h})=r(s^{k}_{h},a^{k}_{h})+[\mathbb{P}V^{\pi^{k}}_{h+1}](s^{k}_{h},a^{k}_{h})$,
$(c)$ holds due to $V^{*}_{h}(s_{h}^{k})\geq
r(s_{h}^{k},a_{h}^{k})+[\mathbb{P}V^{*}_{h+1}](s_{h}^{k},a_{h}^{k})$ and the
definition of $\check{V}_{k,h}$, while $(d)$ is due to Lemma F.1. Substituting
(G.7) into (G.6), we have

$\widetilde{S}_{m}\leq\widetilde{A}_{m+1}+G+2^{m+1}\cdot(2R_{0}+\check{A}_{0}).$

#### Bound $S_{m}$

Recall the definition of $S_{m}$ in (F.10), we have

$\displaystyle S_{m}$
$\displaystyle=\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}[\mathbb{V}V_{k,h+1}^{2^{m}}](s_{h}^{k},a_{h}^{k})$
$\displaystyle=\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[[\mathbb{P}V_{k,h+1}^{2^{m+1}}](s_{h}^{k},a_{h}^{k})-[\mathbb{P}V_{k,h+1}^{2^{m}}]^{2}(s_{h}^{k},a_{h}^{k})\right]$
$\displaystyle=\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[[\mathbb{P}V_{k,h+1}^{2^{m+1}}](s_{h}^{k},a_{h}^{k})-V_{k,h+1}^{2^{m+1}}(s_{h+1}^{k})\right]+\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[V_{k,h}^{2^{m+1}}(s_{h}^{k})-[\mathbb{P}V_{k,h+1}^{2^{m}}]^{2}(s_{h}^{k},a_{h}^{k})\right]$
$\displaystyle\qquad+\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left(V_{k,h+1}^{2^{m+1}}(s_{h+1}^{k})-V_{k,h}^{2^{m+1}}(s_{h}^{k})\right)$
$\displaystyle\leq
A_{m+1}+\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[V_{k,h}^{2^{m+1}}(s_{h}^{k})-[\mathbb{P}V_{k,h+1}^{2^{m}}]^{2}(s_{h}^{k},a_{h}^{k})\right]+\sum_{k=1}^{K}(1-I^{k}_{h_{k}})V_{k,h_{k}}^{2^{m+1}}(s_{h_{k}}^{k})$
$\displaystyle\leq
A_{m+1}+G+\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[V_{k,h}^{2^{m+1}}(s_{h}^{k})-[\mathbb{P}V_{k,h+1}^{2^{m}}]^{2}(s_{h}^{k},a_{h}^{k})\right],$
(G.8)

where $h_{k}$ is defined in (F.4) and the last inequality holds since
$|V_{k,h}(s_{h}^{k})|\leq 1$ and $I^{k}_{h}$ is monotonically decreasing. For
the third term in (G.8), we have

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[V_{k,h}^{2^{m+1}}(s_{h}^{k})-[\mathbb{P}V_{k,h+1}^{2^{m}}]^{2}(s_{h}^{k},a_{h}^{k})\right]$
$\displaystyle\overset{(a)}{\leq}{}$
$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[V_{k,h}^{2^{m+1}}(s_{h}^{k})-[\mathbb{P}V_{k,h+1}]^{2^{m+1}}(s_{h}^{k},a_{h}^{k})\right]$
$\displaystyle={}$
$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[V_{k,h}(s_{h}^{k})-[\mathbb{P}V_{k,h+1}](s_{h}^{k},a_{h}^{k})\right]\prod_{i=0}^{m}\left[V_{k,h}^{2^{i}}(s_{h}^{k})+[\mathbb{P}V_{k,h+1}]^{2^{i}}(s_{h}^{k},a_{h}^{k})\right]$
$\displaystyle\leq{}$ $\displaystyle
2^{m+1}\sum_{k=1}^{K}\sum_{h=1}^{H}I_{h}^{k}\max\left\\{V_{k,h}(s_{h}^{k})-[\mathbb{P}V_{k,h+1}](s_{h}^{k},a_{h}^{k}),0\right\\}$
$\displaystyle\overset{(b)}{\leq}{}$ $\displaystyle
2^{m+1}\sum_{k=1}^{K}\sum_{h=1}^{H}I_{h}^{k}\left[r(s^{k}_{h},a^{k}_{h})+2\min\\{1,\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(z_{k,h,0};D_{k,0})\\}\right]$
$\displaystyle\leq{}$ $\displaystyle 2^{m+1}\cdot(V_{0}+2R_{0}),$ (G.9)

where $(a)$ holds due to $\mathbb{E}[X^{2}]\geq(\mathbb{E}[X])^{2}$ and $(b)$
holds due to Lemma F.1. Substituting (G.9) into (G.8), we have

$S_{m}\leq A_{m+1}+G+2^{m+1}\cdot(V_{0}+2R_{0}).$

∎

###  G.6 Proof of Lemma F.6

###### Proof of Lemma F.6.

Let
$X_{k,h}=I^{k}_{h}\left[[\mathbb{P}\check{V}_{k,h+1}^{2^{m}}](s_{h}^{k},a_{h}^{k})-\check{V}_{k,h+1}^{2^{m}}(s_{h+1}^{k})\right]$,
then we have $\mathbb{E}[X_{k,h}|\mathcal{G}_{k,h}]=0$, $|X_{k,h}|\leq 2$ and
$\mathbb{E}[X_{k,h}^{2}|\mathcal{G}_{k,h}]=I^{k}_{h}[\mathbb{V}\check{V}_{k,h+1}^{2^{m}}](s^{k}_{h},a^{k}_{h})$.
Therefore, for any $m\in\overline{[M]}$, applying variance-aware Freedman’s
inequality in Lemma H.2, with probability at least $1-\delta$, we have

$\check{A}_{m}\leq\sqrt{\zeta\check{S}_{m}}+\zeta.$

Thus, taking a union bound over $m\in\overline{[M]}$, with probability at
least $1-(M+1)\delta$, (F.23) holds. The proofs for (F.24) and (F.25) follow
the same arguments as (F.23). ∎

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

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

On event $\mathcal{E}\cup\mathcal{A}$, we have (F.20) and (F.23) hold by Lemma
F.5 and F.6. Substituting the bound of $\check{S}_{m}$ in (F.20) into (F.23),
we have for all $m\in\overline{[M]}$,

$\check{A}_{m}\leq\sqrt{\zeta}\cdot\sqrt{\check{A}_{m+1}+G+2^{m+1}\cdot(2R_{0})}+\zeta.$

And we have for all $m\in\overline{[M]}$, $\check{A}_{m}\leq 2KH$. Then the
result follows by Lemma H.6. ∎

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

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

On event $\mathcal{E}\cup\mathcal{A}$, we have (F.21) and (F.24) hold by Lemma
F.5 and F.6. Substituting the bound of $\widetilde{S}_{m}$ in (F.21) into
(F.24), we have for all $m\in\overline{[M]}$,

$\widetilde{A}_{m}\leq\sqrt{\zeta}\cdot\sqrt{\widetilde{A}_{m+1}+G+2^{m+1}\cdot(2R_{0}+\check{A}_{0})}+\zeta.$

And we have for all $m\in\overline{[M]}$, $\widetilde{A}_{m}\leq 2KH$.
Applying Lemma H.6, we have

$\displaystyle\widetilde{A}_{0}$ $\displaystyle\leq
2\sqrt{\zeta(2R_{0}+\check{A}_{0})}+3\sqrt{\zeta G}+7\zeta$
$\displaystyle\overset{(a)}{\leq}2\sqrt{2\zeta
R_{0}}+2\sqrt{\zeta\check{A}_{0}}+3\sqrt{\zeta G}+7\zeta$
$\displaystyle\overset{(b)}{\leq}2\sqrt{2\zeta
R_{0}}+\zeta+\check{A}_{0}+3\sqrt{\zeta G}+7\zeta$
$\displaystyle\overset{(c)}{\leq}4\sqrt{2\zeta R_{0}}+6\sqrt{\zeta
G}+15\zeta,$

where $(a)$ holds due to $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for $a,b\geq 0$,
$(b)$ holds due to $2\sqrt{ab}\leq a+b$ for $a,b\geq 0$ and $(c)$ holds due to
(F.27) in Lemma F.7. ∎

###  G.9 Proof of Lemma F.9

###### Proof of Lemma F.9.

Recall the definition of $V_{0}$ and $V^{*}_{1}$ in (F.16) and (F.17), we have

$\displaystyle V_{0}-V^{*}_{1}K$
$\displaystyle=\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}r(s^{k}_{h},a^{k}_{h})-\sum_{k=1}^{K}V^{*}_{1}(s^{k}_{h})$
$\displaystyle\leq\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[r(s^{k}_{h},a^{k}_{h})-V^{*}_{h}(s^{k}_{h})+V^{*}_{h+1}(s^{k}_{h+1})\right]$
$\displaystyle\leq\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[V^{*}_{h+1}(s^{k}_{h+1})-[\mathbb{P}_{h}V^{*}_{h+1}](s^{k}_{h},a^{k}_{h})\right]$
$\displaystyle\leq A_{0}+\check{A}_{0},$

where the second inequality holds due to $V^{*}_{h}(s^{k}_{h})\geq
r(s^{k}_{h},a^{k}_{h})+[\mathbb{P}V^{*}_{h+1}](s^{k}_{h},a^{k}_{h})$. ∎

###  G.10 Proof of Lemma F.10

###### Proof of Lemma F.10.

First, for all $m\in\overline{[M]}$, $R_{m}\leq KH$ holds trivially. For
$(k,h)$ where $I_{h}^{k}=1$, we have
$\sum_{j=1}^{h-1}\frac{1}{\bar{\sigma}_{k,j,m}^{2}}\mathcal{D}_{\mathcal{F}}^{2}(z_{k,j,m};D_{k,j-1,m})\leq
1$. By Lemma H.4, it follows that

$\displaystyle\mathcal{D}_{\mathcal{F}}(z_{k,h,m};D_{k,m})$
$\displaystyle\leq{}$
$\displaystyle\exp\left\\{\frac{1}{2}\sum_{j=1}^{h-1}\frac{1}{\bar{\sigma}_{k,j,m}^{2}}\mathcal{D}_{\mathcal{F}}^{2}(z_{k,j,m};D_{k,j-1,m})\right\\}\mathcal{D}_{\mathcal{F}}(z_{k,h,m};D_{k,h-1,m})$
$\displaystyle\leq{}$ $\displaystyle
2\mathcal{D}_{\mathcal{F}}(z_{k,h,m};D_{k,h-1,m}).$

Then we have

$R_{m}\leq
2\sum_{k=1}^{K}\sum_{h=1}^{H}\min\\{1,I^{k}_{h}\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(z_{k,h,m};D_{k,h-1,m})\\},$

which can be bounded by Lemma H.5, with
$\beta_{t}=I_{h}^{k}\widehat{\beta}_{k}$,
$\bar{\sigma}_{t}=\bar{\sigma}_{k,h,m}$ and $X_{t}=z_{k,h,m}$. We have

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\min\\{1,I^{k}_{h}\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(z_{k,h,m};D_{k,h-1,m})\\}$
$\displaystyle\leq{}$
$\displaystyle\dim_{\mathcal{F}}+\widehat{\beta}_{K}\gamma^{2}\dim_{\mathcal{F}}+\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}I_{h}^{k}\big{[}[\bar{\mathbb{V}}_{k,m}V_{k,h+1}^{2^{m}}](s_{h}^{k},a_{h}^{k})+E_{k,h,m}\big{]}+KH\sigma_{\mathrm{min}}^{2}}$
$\displaystyle\leq{}$
$\displaystyle\dim_{\mathcal{F}}+\widehat{\beta}_{K}\gamma^{2}\dim_{\mathcal{F}}+\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}I_{h}^{k}\big{[}[\mathbb{V}V_{k,h+1}^{2^{m}}](s_{h}^{k},a_{h}^{k})+2E_{k,h,m}\big{]}+KH\sigma_{\mathrm{min}}^{2}},$

where the last inequality is due to Lemma F.1. Note that

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}I_{h}^{k}E_{k,h,m}$
$\displaystyle=\sum_{k=1}^{K}\sum_{h=1}^{H}I_{h}^{k}\min\Big{\\{}1,2\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(z_{k,h,m};D_{k,m})\Big{\\}}$
$\displaystyle\qquad+\sum_{k=1}^{K}\sum_{h=1}^{H}I_{h}^{k}\min\Big{\\{}1,\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(z_{k,h,m+1};D_{k,m+1})\Big{\\}}$
$\displaystyle\leq 2R_{m}+R_{m+1},$

where the last inequality holds by the definition of $R_{m}$ in (F.18). Thus,
we have

$\displaystyle R_{m}$ $\displaystyle\leq
2\dim_{\mathcal{F}}+2\widehat{\beta}_{K}\gamma^{2}\dim_{\mathcal{F}}+2\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{S_{m}+4R_{m}+2R_{m+1}+KH\sigma_{\mathrm{min}}^{2}}$
$\displaystyle\overset{(a)}{\leq}16\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}+4\dim_{\mathcal{F}}+4\widehat{\beta}_{K}\gamma^{2}\dim_{\mathcal{F}}+4\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{S_{m}+2R_{m+1}+KH\sigma_{\mathrm{min}}^{2}}$
$\displaystyle\overset{(b)}{\leq}4\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{S_{m}+2R_{m+1}+KH\sigma_{\mathrm{min}}^{2}}+24\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}},$

where $(a)$ holds since $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for any $a,b\geq 0$
and $x\leq a\sqrt{x}+b$ implies $x\leq a^{2}+2b$ for any $x\geq 0$, while
$(b)$ holds due to $\widehat{\beta}_{K},\dim_{\mathcal{F}}\geq 1$ and
$\gamma^{2}\leq\widehat{\beta}_{K}$. ∎

###  G.11 Proof of Lemma F.11

###### Proof of Lemma F.11.

On event $\mathcal{E}\cup\mathcal{A}$, we have (F.31) holds by Lemma F.10. And
we have for all $m\in\overline{[M]}$,

$S_{m}\leq 2Q_{m}+2\check{S}_{m},$ (G.10)

where the inequality holds due to $\operatorname{{\rm Var}}[X+Y]\leq
2\operatorname{{\rm Var}}[X]+2\operatorname{{\rm Var}}[Y]$. Substituting the
bound of $S_{m}$ in (G.10) into (F.31), we have for all
$m\in\overline{[M-1]}$,

$R_{m}\leq
4\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{2Q_{m}+2\check{S}_{m}+2R_{m+1}+KH\sigma_{\mathrm{min}}^{2}}+24\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}.$
(G.11)

Next, on event $\mathcal{E}\cup\mathcal{A}$, we have (F.20) holds by Lemma
F.5. Substituting the bound of $\check{S}_{m}$ in (F.20) into (G.11), we have

$\displaystyle R_{m}$ $\displaystyle\leq
4\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{2R_{m+1}+2\check{A}_{m+1}+2Q_{m}+2G+KH\sigma_{\mathrm{min}}^{2}+2^{m+1}\cdot(4R_{0})}+24\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}$
$\displaystyle\leq
4\widehat{\beta}_{K}\sqrt{2\dim_{\mathcal{F}}}\cdot\sqrt{R_{m+1}+\check{A}_{m+1}+2^{m+1}\cdot(2R_{0})}$
$\displaystyle\qquad+4\widehat{\beta}_{K}\sqrt{2\dim_{\mathcal{F}}}\cdot\sqrt{\mathcal{Q}+G+KH\sigma_{\mathrm{min}}^{2}}+24\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}},$
(G.12)

where the last inequality holds due to the inequality that
$\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for any $a,b\geq 0$, and the definition of
$\mathcal{Q}$ in (F.12). Then, on event $\mathcal{E}\cup\mathcal{A}$, we have
(F.26) holds by Lemma F.7. Add (F.26) to (G.12), using
$\sqrt{a}+\sqrt{b}\leq\sqrt{2}\cdot\sqrt{a+b}$ for any $a,b\geq 0$ and assume
$\zeta\leq\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}$ (which is trivial since
$\zeta$ only consists of logarithmic terms), we have for all
$m\in\overline{[M-1]}$,

$\displaystyle R_{m}+\check{A}_{m}$ $\displaystyle\leq
8\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{R_{m+1}+2\check{A}_{m+1}+2^{m+1}\cdot(4R_{0})}$
$\displaystyle\qquad+5\widehat{\beta}_{K}\sqrt{2\dim_{\mathcal{F}}}\cdot\sqrt{\mathcal{Q}+G+KH\sigma_{\mathrm{min}}^{2}}+25\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}$
$\displaystyle\leq
8\widehat{\beta}_{K}\sqrt{2\dim_{\mathcal{F}}}\cdot\sqrt{R_{m+1}+\check{A}_{m+1}+2^{m+1}\cdot(2R_{0})}$
$\displaystyle\qquad+5\widehat{\beta}_{K}\sqrt{2\dim_{\mathcal{F}}}\cdot\sqrt{\mathcal{Q}+G+KH\sigma_{\mathrm{min}}^{2}}+25\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}.$
(G.13)

And for all $m\in\overline{[M]}$, $R_{m}+\check{A}_{m}\leq 3HK$. Then the
result follows by Lemma H.6. ∎

###  G.12 Proof of Lemma F.12

###### Proof of Lemma F.12.

On event $\mathcal{E}\cup\mathcal{A}$, we have (F.22), (F.25) and (F.31) holds
by Lemma F.5, F.6 and F.10. Substituting the bound of $S_{m}$ in (F.22) into
(F.25) and (F.31) respectively, we have for all $m\in\overline{[M-1]}$,

$\displaystyle A_{m}$
$\displaystyle\leq\sqrt{\zeta}\cdot\sqrt{A_{m+1}+G+2^{m+1}\cdot(V_{0}+2R_{0})}+\zeta,$
(G.14) $\displaystyle R_{m}$ $\displaystyle\leq
4\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{2R_{m+1}+A_{m+1}+G+KH\sigma_{\mathrm{min}}^{2}+2^{m+1}\cdot(V_{0}+2R_{0})}+24\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}$
$\displaystyle\leq
4\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{2R_{m+1}+A_{m+1}+2^{m+1}\cdot(V_{0}+2R_{0})}$
$\displaystyle\qquad+4\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{G+KH\sigma_{\mathrm{min}}^{2}}+24\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}.$
(G.15)

Add (G.14) to (G.15), using $\sqrt{a}+\sqrt{b}\leq\sqrt{2}\cdot\sqrt{a+b}$ for
any $a,b\geq 0$ and assume
$\zeta\leq\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}$, we have for all
$m\in\overline{[M-1]}$,

$\displaystyle R_{m}+A_{m}$ $\displaystyle\leq
4\widehat{\beta}_{K}\sqrt{2\dim_{\mathcal{F}}}\cdot\sqrt{2R_{m+1}+2A_{m+1}+2^{m+1}\cdot(2V_{0}+4R_{0})}$
$\displaystyle\qquad+5\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{G+KH\sigma_{\mathrm{min}}^{2}}+25\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}$
$\displaystyle=8\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{R_{m+1}+A_{m+1}+2^{m+1}\cdot(V_{0}+2R_{0})}$
$\displaystyle\qquad+5\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{G+KH\sigma_{\mathrm{min}}^{2}}+25\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}.$
(G.16)

And for all $m\in\overline{[M]}$, $R_{m}+\check{A}_{m}\leq 2HK$. Applying
Lemma H.6, we have

$R_{0}+A_{0}\leq
16\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{V_{0}+2R_{0}}+15\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{G+KH\sigma_{\mathrm{min}}^{2}}+331\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}.$
(G.17)

We have (F.30) holds by Lemma F.9. Substituting the bound of $V_{0}$ in (F.30)
into (G.17), we have

$\displaystyle R_{0}+A_{0}$ $\displaystyle\leq
16\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{V^{*}_{1}K+A_{0}+\check{A}_{0}+2R_{0}}+15\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{G+KH\sigma_{\mathrm{min}}^{2}}+331\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}}$
$\displaystyle\leq
32\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{V^{*}_{1}K+\check{A}_{0}}+30\widehat{\beta}_{K}\sqrt{\dim_{\mathcal{F}}}\cdot\sqrt{G+KH\sigma_{\mathrm{min}}^{2}}+1174\widehat{\beta}_{K}^{2}\dim_{\mathcal{F}},$

where the last inequality holds since $x\leq a\sqrt{x}+b$ implies $x\leq
a^{2}+2b$ for any $x\geq 0$. ∎

###  G.13 Proof of Lemma F.13

###### Proof of Lemma F.13.

First, we decompose $V_{k,1}(s^{k}_{1})$ and $V^{\pi^{k}}_{1}(s^{k}_{1})$ as
follows

$\displaystyle V_{k,1}(s^{k}_{1})$
$\displaystyle=\sum_{h=1}^{H}I^{k}_{h}[V_{k,h}(s^{k}_{h})-V_{k,h+1}(s^{k}_{h+1})]+\sum_{h=1}^{H}(1-I^{k}_{h})[V_{k,h}(s^{k}_{h})-V_{k,h+1}(s^{k}_{h+1})]$
$\displaystyle=\sum_{h=1}^{H}I^{k}_{h}r(s^{k}_{h},a^{k}_{h})+\sum_{h=1}^{H}I^{k}_{h}\left[V_{k,h}(s^{k}_{h})-r(s^{k}_{h},a^{k}_{h})-[\mathbb{P}V_{k,h+1}](s^{k}_{h},a^{k}_{h})\right]$
$\displaystyle\qquad+\sum_{h=1}^{H}I^{k}_{h}\left[[\mathbb{P}V_{k,h+1}](s^{k}_{h},a^{k}_{h})-V_{k,h+1}(s^{k}_{h+1})\right]+(1-I^{k}_{h_{k}})V_{k,h_{k}}(s^{k}_{h_{k}}),$
$\displaystyle V^{\pi^{k}}_{1}(s^{k}_{1})$
$\displaystyle=\sum_{h=1}^{H}I^{k}_{h}[V^{\pi^{k}}_{h}(s^{k}_{h})-V^{\pi^{k}}_{h+1}(s^{k}_{h+1})]+\sum_{h=1}^{H}(1-I^{k}_{h})[V^{\pi^{k}}_{h}(s^{k}_{h})-V^{\pi^{k}}_{h+1}(s^{k}_{h+1})]$
$\displaystyle=\sum_{h=1}^{H}I^{k}_{h}r(s^{k}_{h},a^{k}_{h})+\sum_{h=1}^{H}I^{k}_{h}\left[V^{\pi^{k}}_{h}(s^{k}_{h})-r(s^{k}_{h},a^{k}_{h})-[\mathbb{P}V^{\pi^{k}}_{h+1}](s^{k}_{h},a^{k}_{h})\right]$
$\displaystyle\qquad+\sum_{h=1}^{H}I^{k}_{h}\left[[\mathbb{P}V^{\pi^{k}}_{h+1}](s^{k}_{h},a^{k}_{h})-V^{\pi^{k}}_{h+1}(s^{k}_{h+1})\right]+(1-I^{k}_{h_{k}})V^{\pi^{k}}_{h_{k}}(s^{k}_{h_{k}})$
$\displaystyle=\sum_{h=1}^{H}I^{k}_{h}r(s^{k}_{h},a^{k}_{h})+\sum_{h=1}^{H}I^{k}_{h}\left[[\mathbb{P}V^{\pi^{k}}_{h+1}](s^{k}_{h},a^{k}_{h})-V^{\pi^{k}}_{h+1}(s^{k}_{h+1})\right]+(1-I^{k}_{h_{k}})V^{\pi^{k}}_{h_{k}}(s^{k}_{h_{k}}),$

where $h_{k}$ is defined in (F.4). Thus it follows that

$\displaystyle V_{k,1}(s^{k}_{1})-V^{\pi^{k}}_{1}(s^{k}_{1})$
$\displaystyle={}$
$\displaystyle\sum_{h=1}^{H}I^{k}_{h}\left[V_{k,h}(s^{k}_{h})-r(s^{k}_{h},a^{k}_{h})-[\mathbb{P}V_{k,h+1}](s^{k}_{h},a^{k}_{h})\right]+(1-I^{k}_{h_{k}})V_{k,h_{k}}(s^{k}_{h_{k}})-(1-I^{k}_{h_{k}})V^{\pi^{k}}_{h_{k}}(s^{k}_{h_{k}})$
$\displaystyle\quad+\sum_{h=1}^{H}I^{k}_{h}\left[[\mathbb{P}V_{k,h+1}](s^{k}_{h},a^{k}_{h})-V_{k,h+1}(s^{k}_{h+1})\right]-\sum_{h=1}^{H}I^{k}_{h}\left[[\mathbb{P}V^{\pi^{k}}_{h+1}](s^{k}_{h},a^{k}_{h})-V^{\pi^{k}}_{h+1}(s^{k}_{h+1})\right]$
$\displaystyle={}$
$\displaystyle\sum_{h=1}^{H}I^{k}_{h}\left[V_{k,h}(s^{k}_{h})-r(s^{k}_{h},a^{k}_{h})-[\mathbb{P}V_{k,h+1}](s^{k}_{h},a^{k}_{h})\right]+(1-I^{k}_{h_{k}})V_{k,h_{k}}(s^{k}_{h_{k}})-(1-I^{k}_{h_{k}})V^{\pi^{k}}_{h_{k}}(s^{k}_{h_{k}})$
$\displaystyle\quad+\sum_{h=1}^{H}I^{k}_{h}\left[[\mathbb{P}\check{V}_{k,h+1}](s^{k}_{h},a^{k}_{h})-\check{V}_{k,h+1}(s^{k}_{h+1})\right]+\sum_{h=1}^{H}I^{k}_{h}\left[[\mathbb{P}\widetilde{V}_{k,h+1}](s^{k}_{h},a^{k}_{h})-\widetilde{V}_{k,h+1}(s^{k}_{h+1})\right].$

Then we have

$\displaystyle\sum_{k=1}^{K}\left[V_{k,1}(s^{k}_{1})-V^{\pi^{k}}(s^{k}_{1})\right]$
$\displaystyle\overset{(a)}{\leq}{}$ $\displaystyle
2\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\min\\{1,\widehat{\beta}_{k}\mathcal{D}_{\mathcal{F}}(z_{k,h,0};D_{k,0})\\}+\sum_{k=1}^{K}(1-I^{k}_{h_{k}})V_{k,h_{k}}(s^{k}_{h_{k}})$
$\displaystyle\quad+\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[[\mathbb{P}\check{V}_{k,h+1}](s^{k}_{h},a^{k}_{h})-\check{V}_{k,h+1}(s^{k}_{h+1})\right]+\sum_{k=1}^{K}\sum_{h=1}^{H}I^{k}_{h}\left[[\mathbb{P}\widetilde{V}_{k,h+1}](s^{k}_{h},a^{k}_{h})-\widetilde{V}_{k,h+1}(s^{k}_{h+1})\right]$
$\displaystyle\overset{(b)}{\leq}{}$ $\displaystyle
2R_{0}+\check{A}_{0}+\widetilde{A}_{0}+G,$

where $(a)$ is due to Lemma F.1 and $(b)$ holds since
$|V_{k,h}(s_{h}^{k})|\leq 1$ and $I^{k}_{h}$ is monotonically decreasing. ∎

##  Appendix H Auxiliary Lemmas

######  Lemma H.1 (Variance-aware and range-aware Freedman’s inequality,
Corollary 2 in Agarwal et al. (2023)).

Let $M\geq m>0,V\geq v>0$ be fixed constants, and $\\{X_{s}\\}_{s\in[t]}$ be a
stochastic process adapted to the filtration
$\\{\mathcal{G}_{s}\\}_{s\in[t]}$, such that $X_{s}$ is
$\mathcal{G}_{s}$-measurable. Suppose $\mathbb{E}[X_{s}|\mathcal{G}_{s-1}]=0$,
$|X_{s}|\leq M$ and $\sum_{s=1}^{t}\mathbb{E}[X_{s}^{2}|\mathcal{G}_{s-1}]\leq
V^{2}$ almost surely. Then for any $\delta>0$, with probability at least
$1-(\log(V^{2}/v^{2})+2)(\log(M/m)+2)\delta$, we have

$\sum_{s=1}^{t}X_{s}\leq\sqrt{2\left(2\sum_{s=1}^{t}\mathbb{E}[X_{s}^{2}|\mathcal{G}_{s-1}]+v^{2}\right)\log\frac{1}{\delta}}+\frac{2}{3}\left(2\max_{s\in[t]}|X_{s}|+m\right)\log\frac{1}{\delta}.$

######  Lemma H.2 (Variance-aware Freedman’s inequality).

Let $M>0$ be fixed constants, and $\\{X_{s}\\}_{s\in[t]}$ be a stochastic
process adapted to the filtration $\\{\mathcal{G}_{s}\\}_{s\in[t]}$, such that
$X_{s}$ is $\mathcal{G}_{s}$-measurable. Suppose
$\mathbb{E}[X_{s}|\mathcal{G}_{s-1}]=0$ and $|X_{s}|\leq M$ almost surely.
Then for any $\delta>0$, with probability at least $1-2(\log t+2)\delta$, we
have

$\displaystyle\sum_{s=1}^{t}X_{s}\leq
2\sqrt{\sum_{s=1}^{t}\mathbb{E}[X_{s}^{2}|\mathcal{G}_{s-1}]\log\frac{1}{\delta}}+4M\log\frac{1}{\delta}.$

###### Proof.

The result follows by applying Lemma H.1 with $V^{2}=M^{2}t,m=v=M$. ∎

######  Lemma H.3 (Elliptical Potential Lemma, Lemma 11 in Abbasi-Yadkori et
al. (2011)).

Let $\\{\bm{x}_{t}\\}_{t\in[T]}\subset\mathbb{R}^{d}$ and assume
$\|\bm{x}_{t}\|_{2}\leq L$ for all $t\in[T]$. Set
$\bm{\Sigma}_{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{\Sigma}_{t-1}^{-1}}\right\\}\leq
2d\log\left(1+\frac{TL^{2}}{d\lambda}\right).$

######  Lemma H.4.

Let $\mathcal{D}_{\mathcal{F}}$ in Definition 3.2, for any $t>t_{0}\geq 1$, we
have

$\mathcal{D}_{\mathcal{F}}^{2}(X_{t};X_{[t_{0}]},\sigma_{[t_{0}]})\leq\exp\left\\{\sum_{s=t_{0}+1}^{t-1}\frac{1}{\sigma_{s}^{2}}\mathcal{D}_{\mathcal{F}}^{2}(X_{s};X_{[s-1]},\sigma_{[s-1]})\right\\}\mathcal{D}_{\mathcal{F}}^{2}(X_{t};X_{[t-1]},\sigma_{[t-1]}).$

###### Proof.

Note

$\displaystyle\mathcal{D}_{\mathcal{F}}^{2}(X_{t};X_{[t-1]},\sigma_{[t-1]})$
$\displaystyle={}$
$\displaystyle\sup_{f_{1},f_{2}\in\mathcal{F}}\frac{(f_{1}(X_{t})-f_{2}(X_{t}))^{2}}{\sum_{s=1}^{t-1}\frac{1}{\sigma_{s}^{2}}(f_{1}(X_{s})-f_{2}(X_{s}))^{2}+\lambda}$
$\displaystyle\geq{}$
$\displaystyle\sup_{f_{1},f_{2}\in\mathcal{F}}\frac{(f_{1}(X_{t})-f_{2}(X_{t}))^{2}}{(1+\frac{1}{\sigma_{t-1}^{2}}\mathcal{D}_{\mathcal{F}}^{2}(X_{t-1};X_{[t-2]},\sigma_{[t-2]}))\sum_{s=1}^{t-2}\frac{1}{\sigma_{s}^{2}}(f_{1}(X_{s})-f_{2}(X_{s}))^{2}+\lambda}$
$\displaystyle\geq{}$