# The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and
Policy Switches

Grigoris Velegkas
Yale University, USA
<EMAIL_ADDRESS>Zhuoran Yang
Yale University, USA
<EMAIL_ADDRESS>Amin Karbasi
Yale University, USA
<EMAIL_ADDRESS>
###### Abstract

In this paper, we study the problem of regret minimization for episodic
Reinforcement Learning (RL) both in the model-free and the model-based
setting. We focus on learning with general function classes and general model
classes, and we derive results that scale with the _eluder dimension_ of these
classes. In contrast to the existing body of work that mainly establishes
instance-independent regret guarantees, we focus on the instance-dependent
setting and show that the regret scales logarithmically with the horizon $T$,
provided that there is a gap between the best and the second best action in
every state. In addition, we show that such a logarithmic regret bound is
realizable by algorithms with $O(\log T)$ switching cost (also known as
_adaptivity complexity_). In other words, these algorithms rarely switch their
policy during the course of their execution. Finally, we complement our
results with lower bounds which show that even in the tabular setting, we
cannot hope for regret guarantees lower than $o(\log T)$.

##  1 Introduction

The main goal of Reinforcement Learning (RL) is the design and analysis of
algorithms for automated decision making in complex and unknown environments.
The environment is modeled as a _state space_ and the available decisions are
modeled as an _action space_. In recent years, RL has seen tremendous success
in practical applications including, but not limited to, games and robotics
(Mnih et al., 2015; Silver et al., 2016; Duan et al., 2016; Silver et al.,
2017; Vinyals et al., 2019). Despite this success, a theoretical understanding
of the algorithms that are deployed in these settings remains elusive.
Traditionally, theoretical RL approaches have focused on the _tabular_ setting
where the complexity of the algorithms depends on the cardinality of the
aforementioned spaces (Sutton & Barto, 2018). Thus, they are not suitable for
applications where the state-action space is very large.

A different approach that has gained a lot of attention recently, is the
_function approximation_ regime where the cumulative reward of the algorithm
is modeled through a function, such as linear functions over some feature
space. The advantage of this approach is that the algorithm can perform its
search over a lower-dimensional space. There is a long line of work that
provides regret guarantees for RL in the function approximation setting
(Osband & Van Roy, 2014; Osband et al., 2016; Yang & Wang, 2020; Jin et al.,
2020; Ayoub et al., 2020; Cai et al., 2020; Kakade et al., 2020; Zanette,
Brandfonbrener, Brunskill, Pirotta & Lazaric, 2020; He et al., 2021; Kong et
al., 2021; Zhou et al., 2021).

Most of these works have focused on establishing worst-case $\sqrt{T}$-regret
guarantees, where $T$ is the number of interactions with the environment. The
caveat with these guarantees is that they are pessimistic since they neglect
benign settings where even an _exponential_ improvement over these bounds is
achievable. To address this issue, there are some works that obtain instance-
dependent regret bounds for RL in the tabular setting and in the linear
function approximation setting (Simchowitz & Jamieson, 2019; Yang & Wang,
2020; He et al., 2021). However, getting logarithmic regret bounds in the
context of _general_ function approximation remains open. Hence, a natural
question is the following:

_Can we establish instance-dependent logarithmic regret bounds with general
function approximation?_

In this paper, we provide an affirmative answer to this question. Following
the assumptions in the existing literature, we model the RL problem as an MDP
that enjoys the property that the optimal _policy_ is at least
${\textnormal{gap}}_{\min}$ better than any other policy, where
${\textnormal{gap}}_{\min}>0$ is a parameter that captures the hardness of the
underlying problem. We focus both on the _model-free_ and _model-based_
settings with general function approximation, where we represent the value
function or the transition model by a given function class, respectively.

In the model-free setting, we study the algorithm proposed in Kong et al.
(2021), which is a variant of the least-squares value iteration (LSVI) with
upper confidence bound (UCB) bonuses that guide exploration. Here, the bonus
functions are given by the width of a data-dependent confidence region for
LSVI. For the model-based setting, we develop a similar algorithm which
combines value-targeted regression with UCB bonuses. On top of the logarithmic
regret guarantees they enjoy, our algorithms feature lazy policy updates, in
the sense that policy is updated rarely and only when certain conditions are
met.

For both settings, we establish $O({\rm poly}(\log T)\cdot{\rm
poly}(H)\cdot{\rm poly}(d_{{\mathcal{F}}})\cdot 1/{\textnormal{gap}}_{\min})$
regret guarantees, where $T$ is the number of interactions with the
environment, $H$ is the _planning horizon_ , $d_{{\mathcal{F}}}$ is a term
that captures the complexity of the function class ${\mathcal{F}}$ which is
used to approximate either the value function or the transition model. In
particular, $d_{{\mathcal{F}}}$ involves both the _eluder dimension_ (Russo &
Van Roy, 2013) and the log-covering numbers of the function classes. That is,
for benign MDPs where ${\textnormal{gap}}_{\min}>0$ these RL algorithms
achieve logarithmic regret, which is exponentially better than the worst-case
$O(\sqrt{T})$-regret. Moreover, we show that the _adaptivity complexity_ ,
meaning the number of different policies our algorithms use, is also
logarithmic in $T$. To the best of our knowledge, this is the first work that
establishes a logarithmic instance-dependent regret guarantee for RL with
general function approximation.

###  1.1 Related Work

Logarithmic regret bounds for bandits. There is a long line of work that
establishes logarithmic regret guarantees in bandit problems. Essentially,
bandits are a special case of RL where the transition to the next state does
not depend on the action that was taken by the agent. An extensive list of
such algorithms can be found in Bubeck & Cesa-Bianchi (2012); Slivkins (2019);
Lattimore & Szepesvári (2020).

Logarithmic regret bounds for RL. A series of works are devoted to proving
instance-dependent logarithmic regret bounds in tabular RL. Ok et al. (2018);
Simchowitz & Jamieson (2019) prove lower bounds that show that a logarithmic
dependence on $T$ is unavoidable. Considering the upper bounds, Auer & Ortner
(2007); Tewari & Bartlett (2007) establish logarithmic regret guarantees in
the average reward setting. Both of these guarantees are asymptotic as they
require the number of interactions $T$ with the MDP to be large enough.
Regarding non-asymptotic bounds, Jaksch et al. (2010) provide such an
algorithm that achieves
$O(D^{2}|{\mathcal{S}}|^{2}|{\mathcal{A}}|\log(T)/{\textnormal{gap}}_{\min})$
regret for the average-reward MDP, where $D$ is the diameter of the MDP. For
episodic MDPs, logarithmic regret upper bounds are established in Simchowitz &
Jamieson (2019); Yang et al. (2021). The work that is probably the most
closely related to ours is He et al. (2021). It provides instance-dependent
logarithmic regret guarantees both in the model-free and model-based setting
with _linear_ function approximation. Moreover, the proposed algorithms update
the policy in every episode. Our work generalizes these results since the
linear regime is a special case of the setting we are studying. Furthermore,
we achieve an exponential improvement on the adaptivity complexity over their
algorithms.

Bandits with limited adaptivity complexity. There is a lot of interest in
obtaining bandit algorithms that update their policies rarely (Abbasi-Yadkori
et al., 2011; Perchet et al., 2016; Agarwal et al., 2017; Gao et al., 2019;
Dong et al., 2020; Chen et al., 2020; Ruan et al., 2021). Notably, Dong et al.
(2020) study rare policy switching constraints for a broader class of online
learning and decision making problems such as logit bandits.

RL with limited adaptivity complexity. Recently, there has been a lot of
interest in developing RL algorithms that achieve sub-linear regret and have
low adaptivity complexity (Bai et al., 2019; Zhang et al., 2020; Wang et al.,
2021; Kong et al., 2021; Gao et al., 2021). We develop an algorithm with low
adaptivity complexity that works in the model-based, general function
approximation setting.

RL with general function approximation. As we have alluded to already, because
of the enormous size of the state-action space in real world applications, it
is important to develop and analyze algorithms in the function approximation
regime. So far, the most commonly studied setting is RL with linear function
approximation (Yang & Wang, 2020; Jin et al., 2020; Du et al., 2020; Wang et
al., 2020; Zanette, Lazaric, Kochenderfer & Brunskill, 2020; Agarwal et al.,
2020). Recently, there are also important results in RL with general function
approximation. To be specific, Jiang et al. (2017) design an efficient
algorithm whose sample complexity is bounded in terms of the Bellman rank of
the function class. Ayoub et al. (2020) develop an algorithm for model-based
RL, whose regret bound depends on the eluder dimension of the underlying class
of models. Jin et al. (2021) propose an algorithm for problems where the
underlying class has bounded Bellman eluder dimension. Recent works such as
Wang et al. (2020); Kong et al. (2021) develop algorithms in the model-free
setting whose regret scale with the eluder dimension of the functions. Foster
et al. (2020) also propose an LSVI-based algorithm whose regret depends on a
disagreement coefficient, which is upper bounded by the eluder dimension of
the function class. The caveat with their approach is that it requires the
block MDP assumption.

##  2 Preliminaries

In this section, we present the notation and the important definitions we use
throughout the paper.

###  2.1 Notation

We use the common notation $[N]=\\{1,2,\ldots,N\\}$. We also define the
infinity norm of some function $f:{\mathcal{X}}\rightarrow\mathbb{R}$, where
${\mathcal{X}}$ is some domain, to be
$||f||_{\infty}=\sup_{x\in{\mathcal{X}}}|f(x)|$. For a dataset
${\mathcal{D}}=\\{(x_{i},q_{i})\\}_{i=1}^{n}\subseteq{\mathcal{X}}\times\mathbb{R}$
and a function $f:{\mathcal{X}}\rightarrow\mathbb{R}$, we define the following
norm

$\displaystyle||f||_{{\mathcal{D}}}=\left(\sum_{i=1}^{n}(f(x_{i})-q_{i})^{2}\right)^{1/2}.$

Given a set ${\mathcal{Z}}=\\{x_{i}\\}_{i=1}^{n}\subseteq{\mathcal{X}}$ we let

$\displaystyle||f||_{{\mathcal{Z}}}=\left(\sum_{i=1}^{n}f(x_{i})^{2}\right)^{1/2}.$

be the data-dependent norm. Given a measurable set ${\mathcal{X}}$, we denote
with $\Delta({\mathcal{X}})$ the probability simplex over ${\mathcal{X}}$. We
also denote by $\mathbbm{1}[{\cal E}]$ the indicator function of the event
${\cal E}$. We denote by ${\rm poly}(x)$ a function that is a polynomial in
$x$.

###  2.2 Episodic Markov Decision Processes

The learning agent interacts with the environment over a sequence of $K$
rounds which we call _episodes_. We model the interaction of the agent with
the environment in every episode as a _Markov Decision Process_ (MDP). We
denote an MDP by $M=({\mathcal{S}},{\mathcal{A}},P,r,H,s_{1})$, where
${\mathcal{S}}$ is the _state space_ , ${\mathcal{A}}$ is the _action space_ ,
$P=\\{P_{h}:{\mathcal{S}}\times{\mathcal{A}}\rightarrow\Delta({\mathcal{S}})\\}_{h=1}^{H}$
are the _transition kernels_ ,
$r=\\{r_{h}:{\mathcal{S}}\times{\mathcal{A}}\rightarrow[0,1]\\}_{h=1}^{H}$ are
the _reward functions_ which we assume to be deterministic, $H$ is the
_planning horizon_ , which is the length of every episode, and $s_{1}$ is the
initial state of every episode. During every episode, the agent uses a
_policy_ $\pi=\\{\pi_{h}:{\mathcal{S}}\rightarrow{\mathcal{A}}\\}_{h=1}^{H}$,
to take an action at a given state. We use the Q-function and V-function to
evaluate the expected total reward generated by a policy $\pi$. More
specifically, we define

$\displaystyle Q_{h}^{\pi}(s,a)$
$\displaystyle=\operatorname*{\mathbb{E}}\left[\sum_{h^{\prime}=h}^{H}r_{h^{\prime}}(s_{h^{\prime}},a_{h^{\prime}})\big{|}s_{h}=s,a_{h}=a,\pi\right]$
$\displaystyle V_{h}^{\pi}(s)$
$\displaystyle=\operatorname*{\mathbb{E}}\left[\sum_{h^{\prime}=h}^{H}r_{h^{\prime}}(s_{h^{\prime}},a_{h^{\prime}})\big{|}s_{h}=s,\pi\right],$

where the actions are picked according to $\pi$ and $s_{h^{\prime}+1}\sim
P_{h^{\prime}}(\cdot|s_{h^{\prime}},a_{h^{\prime}})$. For simplicity, we
denote $\langle
P_{h}(\cdot|s,a),V\rangle=\operatorname*{\mathbb{E}}_{s^{\prime}\sim
P_{h}(\cdot|s,a)}[V(s^{\prime})]$. We denote the optimal policy for a given
MDP with $\pi^{*}$. Similarly, for the optimal Q-function and V-function we
use $Q^{*}_{h}(s,a)=Q^{\pi^{*}}_{h}(s,a),V^{*}_{h}(s)=V^{\pi^{*}}_{h}(s)$,
respectively.

The goal of the learner is to improve her performance as she interacts with
the unknown environment. In the episodic setting, the agent commits to a
policy at the beginning of every episode. We let $\pi^{k}$ denote the policy
that the agent uses in the $k$-th episode. At each step $h\in[H]$, the agent
observes the state $s_{h}^{k}$, chooses an action according to $\pi^{k}$, and
then observes the reward $r_{h}(s_{h}^{k},a_{h}^{k})$ and the next state
$s^{k}_{h+1}\sim P_{h}(\cdot|s_{h}^{k},a_{h}^{k})$. In this work, to measure
the performance of the agent we use the notion of _regret_ , defined as

$\displaystyle{\textnormal{Regret}}(K)=\sum_{k=1}^{K}\left(V_{1}^{*}(s_{1})-V_{1}^{\pi^{k}}(s_{1})\right).$

The regret measures the difference between the total reward that the agent
would have accumulated if she was following the optimal policy and the reward
she actually accumulates. The intuition behind striving for algorithms that
guarantee sub-linear regret is that we want, as $K\rightarrow\infty$, the
average reward of the learner who follows the algorithm to approach that of
the optimal policy.

We now describe the tabular MDP setting, which is arguably the simplest
setting one can work on. The lower bounds on the regret that we state apply to
this setting, whereas both of the upper bounds we derive capture the tabular
MDP setting. In this regime, there are $|{\mathcal{S}}|$ states,
$|{\mathcal{A}}|$ actions, and for each step $h\in[H]$ the transition
probability is given by $P_{h}(s^{\prime}|s,a)$, where
$\sum_{s^{\prime}\in{\mathcal{S}}}P_{h}(s^{\prime}|s,a)=1$, and the reward is
denoted by $r_{h}(s,a)$. The caveat with this setting is that in practical
applications the state space and the action space can be very large, so the
bounds that depend explicitly on the cardinality of these quantities are not
very useful.

An important assumption we make in order to achieve logarithmic regret
guarantees is that the minimum _sub-optimality_ gap is positive.

######  Definition 2.1.

We define the sub-optimality gap of a state-action pair $(s,a)$ at step $h$ to
be

$\displaystyle{\textnormal{gap}}_{h}(s,a)=V^{*}_{h}(s)-Q^{*}_{h}(s,a).$

The minimum sub-optimality gap is defined to be

$\displaystyle{\textnormal{gap}}_{\min}=\min_{h,s,a}\\{{\textnormal{gap}}_{h}(s,a):{\textnormal{gap}}_{h}(s,a)\neq
0\\}.$

It is well-known that if we do not make any assumptions the best regret
guarantee we can hope for is $O(\sqrt{T})$ (Jaksch et al., 2010). In this
work, we derive instance-dependent regret guarantees that achieve an
exponential improvement on $T$ when ${\textnormal{gap}}_{\min}>0$.

###  2.3 Model-Free Assumption

In this paper, we deal with general function classes. In the model-free
setting we assume that we have access to a function class
${\mathcal{F}}\subseteq\\{f:{\mathcal{S}}\times{\mathcal{A}}\rightarrow[0,H+1]\\}$.
Our goal is to use the functions in ${\mathcal{F}}$ to approximate the optimal
Q-function. In order to derive meaningful results we assume that this class
has some structure. We follow the same assumption as in Wang et al. (2020);
Kong et al. (2021).

######  Assumption 2.2 (Bellman Operator Assumption).

For any $h\in[H]$ and $V:{\mathcal{S}}\rightarrow[0,H]$ there exists some
$f_{V}\in{\mathcal{F}}$ such that for all
$(s,a)\in{\mathcal{S}}\times{\mathcal{A}}$ we have

$\displaystyle
f_{V}(s,a)=r_{h}(s,a)+\sum_{s^{\prime}\in{\mathcal{S}}}P_{h}(s^{\prime}|s,a)V(s^{\prime}).$

The intuition behind this assumption is that if we apply the one-step Bellman
backup operator to some value function $V$, i.e.

$\displaystyle
r_{h}(s,a)+\sum_{s^{\prime}\in{\mathcal{S}}}P_{h}(s^{\prime}|s,a)V(s^{\prime}),$

the result will remain in the function class. Thus, it implicitly poses some
constraints both on the transition probabilities and the reward function. It
is known that both the tabular setting and the linear MDP setting (Yang &
Wang, 2019; Jin et al., 2020) satisfy this assumption.

Another assumption we make is that the function class and the state-action
space have bounded covering numbers. We will show that the dependence of the
regret on the covering number is poly-logarithmic. This assumption has also
appeared in other works (Russo & Van Roy, 2013; Wang et al., 2020; Jin et al.,
2021; Kong et al., 2021).

######  Assumption 2.3 (Bounded Covering Number).

We say that ${\mathcal{N}}({\mathcal{F}},\varepsilon)$ is a bound on the
$\varepsilon$-covering number of ${\mathcal{F}}$, if for any $\varepsilon>0$
there is an $\varepsilon$-cover
${\mathcal{C}}({\mathcal{F}},\varepsilon)\subseteq{\mathcal{F}}$ with size
$|{\mathcal{C}}({\mathcal{F}},\varepsilon)|\leq{\mathcal{N}}({\mathcal{F}},\varepsilon)$,
so that for all $f\in{\mathcal{F}}$ there is some
$f^{\prime}\in{\mathcal{C}}({\mathcal{F}},\varepsilon)$ such that
$||f-f^{\prime}||_{\infty}\leq\varepsilon$. Similarly, we say that
${\mathcal{N}}({\mathcal{S}}\times{\mathcal{A}},\varepsilon)$ is a bound on
the $\varepsilon$-covering number of ${\mathcal{S}}\times{\mathcal{A}}$ with
respect to ${\mathcal{F}}$, if for any $\varepsilon>0$ there is an
$\varepsilon$-cover
${\mathcal{C}}({\mathcal{S}}\times{\mathcal{A}},\varepsilon)\subseteq{\mathcal{S}}\times{\mathcal{A}}$
with size
$|{\mathcal{C}}({\mathcal{S}}\times{\mathcal{A}},\varepsilon)|\leq{\mathcal{N}}({\mathcal{S}}\times{\mathcal{A}},\varepsilon)$,
so that for all $(s,a)\in{\mathcal{S}}\times{\mathcal{A}}$ there is some
$(s^{\prime},a^{\prime})\in{\mathcal{C}}({\mathcal{S}}\times{\mathcal{A}},\varepsilon)$
such that
$\sup_{f\in{\mathcal{F}}}|f(s,a)-f(s^{\prime},a^{\prime})|\leq\varepsilon$.

The intuition behind this assumption is straightforward: even if the function
class or the state-action space are infinite, we can approximate them using a
small number of points.

###  2.4 Model-Based Assumption

The assumptions in Section 2.3 are _model-free_ since they impose some
structure on the function class that approximates the Q-function instead of
the transition kernel. In order to derive our results, we can also follow a
different route and impose some structure directly on the transition kernel
(Ayoub et al., 2020).

######  Assumption 2.4 (Known Transition Model Family).

For all $h\in[H]$, the transition model $P_{h}$ belongs to a family of models
${\cal P}_{h}$ which is known to the learner. The elements of ${\cal P}_{h}$
are transition kernels that map state-action pairs to signed distributions
over the state space ${\mathcal{S}}$.

We allow signed distributions in our model class to increase its generality.
For example, this is useful when we are given access to a model class that can
be compactly represented only when it includes non-probability kernels. For an
extensive discussion about this, the reader is referred to Pires & Szepesvári
(2016).

Transition kernels, either parametric or non-parametric, have been used to
model complex stochastic controlled systems. For instance, transitions in
robotics systems are often modelled using parameters of the environment, such
as friction.

An important class that satisfies this assumption are the _linear mixture
models_.

######  Definition 2.5.

The class of models ${\cal P}$ with feature mapping
$\phi(s^{\prime}|s,a):{\mathcal{S}}\times{\mathcal{A}}\times{\mathcal{A}}\rightarrow\mathbb{R}^{d}$
and some $\theta^{*}\in\mathbb{R}^{d},||\theta^{*}||_{2}\leq C_{\theta},$ is
called linear mixture model if:

  * •

$P(s^{\prime}|s,a)=\left\langle\phi(\cdot|s,a),\theta^{*}\right\rangle.$

  * •

For any bounded function $V:{\mathcal{S}}\rightarrow[0,H]$ and any pair
$(s,a)\in{\mathcal{S}}\times{\mathcal{A}}$, we have
$||\phi_{V}(s,a)||_{2}\leq\sqrt{H}$, where

$\phi_{V}(s,a)=\left\langle\phi(\cdot|s,a),V\right\rangle.$

One way to interpret the linear mixture model is as an aggregation of some
basis models which are known to the designer (Modi et al., 2020). Another
interesting way to think about it comes from large-scale queuing networks
where both the arrival rate of jobs and the processing speed for the queues
are unknown. If we approximate this system in discrete time, then the
transition matrix from timestep $t$ to timestep $t+\Delta t$ approaches that
of a linear function with respect to the arrival rate and the processing time
(Gnedenko & Kovalenko, 1989).

Another interesting setting that satisfies this assumption is the linear-
factored MDP (Yang & Wang, 2020). Assuming that the state space is discrete,
we have that

$\displaystyle P(s^{\prime}|s,a)$
$\displaystyle=\phi(s,a)^{T}M\psi(s^{\prime})$
$\displaystyle=\sum_{i=1}^{d_{1}}\sum_{j=1}^{d_{2}}M_{ij}[\psi_{j}(s^{\prime})\phi_{i}(s,a)].$

###  2.5 Complexity Measure: Eluder Dimension

Our results depend on the complexity of the function classes and the model
classes that we consider. To measure this complexity, we use the _eluder
dimension_ of these classes (Russo & Van Roy, 2013).

######  Definition 2.6.

Fix some $\varepsilon\geq 0$ and a sequence of $n$ points
$\mathcal{Z}=\\{(x_{i})\\}_{i\in[n]}\subseteq{\mathcal{X}}$. Then:

  1. 1.

A point $x\in{\mathcal{X}}$ is $\varepsilon$-dependent on $\mathcal{Z}$ with
respect to $\mathcal{F}$ if for all $f,f^{\prime}\in\mathcal{F}$ such that
$||f-f^{\prime}||_{\mathcal{Z}}\leq\varepsilon$ it holds that
$|f(x)-f^{\prime}(x)|\leq\varepsilon$.

  2. 2.

A point $x$ is $\varepsilon$-independent of $\mathcal{Z}$ with respect to
$\mathcal{F}$ if $x$ is not $\varepsilon$-dependent on $\mathcal{Z}$.

  3. 3.

The $\varepsilon$-eluder dimension of $\mathcal{F}$, which is denoted by
$\text{dim}_{E}(\mathcal{F},\varepsilon)$, is the length of the longest
sequence of elements in ${\mathcal{X}}$ such that every element in this
sequence is $\varepsilon^{\prime}$-independent of its predecessors, for some
$\varepsilon^{\prime}\geq\varepsilon$.

Intuitively, the eluder dimension of ${\mathcal{F}}$ quantifies the largest
set of elements ${\mathcal{Z}}\subseteq{\mathcal{X}}$ so that if all
$f\in{\mathcal{F}}$ are close with respect to ${\mathcal{Z}}$, then they are
close on all elements of ${\mathcal{X}}$.

It is known that when
${\mathcal{X}}={\mathcal{S}}\times{\mathcal{A}},f:{\mathcal{S}}\times{\mathcal{A}}\rightarrow[0,H]$,
and ${\mathcal{S}},{\mathcal{A}}$ are finite, we have that
$\dim_{E}({\mathcal{F}},\varepsilon)\leq|{\mathcal{S}}|\cdot|{\mathcal{A}}|$,
for all $\varepsilon>0$ (Russo & Van Roy, 2013; Wang et al., 2020). Moreover,
when ${\mathcal{F}}$ is the class of linear functions, i.e.,
$f_{\theta}(s,a)=\theta^{T}\phi(s,a)$, for a given feauture vector
$\phi(s,a)$, the eluder dimension of ${\mathcal{F}}$ is bounded by
$\dim_{E}({\mathcal{F}},\varepsilon)=O(d\log(1/\varepsilon))$, for all
$\varepsilon>0$. We also remark that more classes including generalized linear
functions and bounded degree polynomials have bounded eluder dimension (Russo
& Van Roy, 2013; Osband & Van Roy, 2014; Li et al., 2021).

###  2.6 Switching Cost

Essentially, the _switching cost_ or the _adaptivity complexity_ measures the
number of episodes the algorithm has to update its policy in order to achieve
the guaranteed regret bound (Bai et al., 2019; Kong et al., 2021). More
formally:

######  Definition 2.7.

We define the switching cost of an algorithm $A$ over $K$ episodes to be

$\displaystyle
N_{\textnormal{switch}}=\sum_{k=1}^{K-1}\mathbbm{1}[\pi_{k}\neq\pi_{k+1}].$

##  3 Overview of the Algorithms and Main Results

In this section, we present our main results and give a high-level description
of the techniques we use. We treat both the model-free and the model-based
setting in a unified way. Our algorithm, inspired by Kong et al. (2021), is
presented in Algorithm 1. The only differences between the two settings are
the different sampling routine and Q-function estimator used by Algorithm 1.
In a nutshell, our low-switching cost algorithm works as follows:

  * •

After each round of the interaction with the MDP, Algorithm 1 adds elements to
the current dataset with some probability that depends on their significance
and updates the policy only if the dataset has changed. This guarantees that
the adaptivity of the algorithm depends logarithmically on $T$, without
hurting the regret guarantee.

  * •

We use a least-squares estimate of the Q-function (transition kernel) in the
model-free (model-based) setting.

  * •

We add a bonus to this estimate which encourages exploration and, with high
probability, guarantees that the current estimate of the Q-function serves as
an element-wise upper bound of $Q^{*}$. This bonus is based on a sub-sampled
dataset that we have accumulated from previous interactions with the MDP.

Before we delve deeper into the two settings separately, we describe a
parameter that is crucial for both of the algorithms we are using. Following
Kong et al. (2021), we define the _sensitivity_ of an element $z$ with respect
to a dataset ${\mathcal{Z}}$ and a function class ${\mathcal{F}}$ to be

$\displaystyle\textnormal{sensitivity}_{{\mathcal{Z}},{\mathcal{F}}}(z)=\min\left\\{\sup_{f_{1},f_{2}\in{\mathcal{F}}}\frac{\left(f_{1}(z)-f_{2}(z)\right)^{2}}{\min\\{||f_{1}-f_{2}||_{{\mathcal{Z}}}^{2},T(H+1)^{2}\\}+\beta}\right\\}.$

Intuitively, this parameter captures the importance of the current element $z$
relative to the dataset we are working with. We will elaborate on the choice
of the parameter $\beta$ for each of the two settings separately. To establish
the regret guarantee, we propose a novel regret decomposition where we utilize
the “peeling technique” that has been applied in prior works in local
Rademacher complexities (Bartlett et al., 2005) and in RL (He et al., 2021;
Yang et al., 2021). By doing that, we show how the regret of the algorithm
relates to the suboptimality gap.

To establish the lower bound on the regret of any algorithm in the settings we
are interested in, we utilize a result that was proved in Ok et al. (2018);
Simchowitz & Jamieson (2019). It states that for all algorithms that achieve
sublinear regret, there exists a tabular MDP where its regret is at least
$\Omega({\rm poly}(\log(T))\cdot{\rm poly}(H)\cdot
1/{\textnormal{gap}}_{\min})$.

###  3.1 Model-Free Setting

We first present the approach we use in the model-free setting, i.e., where we
have access to some function class ${\mathcal{F}}$ and state-action space
${\mathcal{S}}\times{\mathcal{A}}$ that satisfy Assumption 2.2 and Assumption
2.3, respectively. The Q-function estimator and the sampling routine that we
use for this setting are presented in Algorithm 2 and Algorithm 3,
respectively. The dataset includes pairs of the form
$z_{h}^{k}=(s_{h}^{k},a_{h}^{k})$. The Q-function routine is a least-squares
estimator that is based on all the previous interactions with the MDP. Notice
that the bonus function is based only on the sub-sampled dataset and depends
on a hardcoded parameter $\beta$. This parameter is chosen in a way that
ensures the Q-function is an optimistic estimate of the actual one and the
bonus we add is not too large. Since we are working with the same assumptions
as Kong et al. (2021), our choice of $\beta$ coincides with theirs.

A crucial part of the algorithm is the online sub-sampling routine. The reason
we are using this routine is twofold. Firstly, if we use the entire dataset
there will be a huge number of distinct elements in it, which can make the
exploration bonus unstable since it changes constantly and can take infinitely
many different values. In order to establish the optimism of the Q-function
estimation, namely,

$\displaystyle Q_{h}^{*}(s,a)\leq Q_{h}^{k}(s,a)\leq\langle
P_{h}(\cdot|s,a),V_{h}^{k}\rangle+2b_{h}^{k}(s,a),$

Kong et al. (2021) show that it is crucial to bound the complexity of the
exploration bonus. Secondly, if we sub-sample the dataset based on the
importance of the elements, we can achieve the regret guarantees that we are
aiming for by switching the policy only when an important element has been
added. Notice that whenever an element is added to the dataset, multiple
copies are included. This is to make the sub-sampled dataset behave like an
unbiased estimator of the orignal one. Then, using concentration bounds one
can show that it approximates the original one with high probability. The full
description of this procedure is presented in Algorithm 3. For a more detailed
discussion about the importance of sub-sampling the dataset, the interested
reader is referred to Wang et al. (2020); Kong et al. (2021).

0: Failure probability $\delta\in(0,1)$, number of episodes $K$, and setting
of operation

1: $\tilde{k}\leftarrow 1$

2: $\widehat{Z}_{h}^{1}\leftarrow\emptyset,\forall h\in[H]$

3: for $k\in[K]$ do

4: for $h=H,H-1,\ldots,1$ do

5: if $k\geq 2$ then

6: $\widehat{{\mathcal{Z}}}_{h}^{k}\leftarrow\textbf{Online-
Sample}({\mathcal{F}},\widehat{{\mathcal{Z}}}_{h}^{k-1},z_{h}^{k-1},\delta)$

7: end if

8: end for

9: if $k=1\text{ or }\exists
h\in[H]:\widehat{Z}_{h}^{k}\neq\widehat{Z}_{h}^{\tilde{k}}$ then

10: $\tilde{k}\leftarrow k$

11: $Q_{H+1}^{k}(\cdot,\cdot)\leftarrow 0,V_{H+1}^{k}(\cdot)\leftarrow 0$

12: for $h=H,H-1,\ldots,1$ do

13: $\mathcal{T}_{h}^{k}\leftarrow$ history of execution

14:
$Q_{h}^{k}(\cdot,\cdot)\leftarrow\textbf{Q-Estimator}(\mathcal{T}_{h}^{k},{\mathcal{Z}}_{h}^{k})$

15: $V_{h}^{k}(\cdot)=\max_{a\in{\mathcal{A}}}Q_{h}^{k}(\cdot,a)$

16:
$\pi_{h}^{k}(\cdot)\leftarrow\arg\max_{a\in{\mathcal{A}}}Q_{h}^{k}(\cdot,a)$

17: end for

18: end if

19: Receive initial state $s_{1}$ of episode $k$

20: for $h\in[H]$ do

21: Take action $a_{h}^{k}\leftarrow\pi_{h}^{\tilde{k}}(s_{h}^{k})$

22: end for

23: end for

Algorithm 1 Low Switching Cost Value Iteration (with parameters $\delta,K$)

0: Current sub-sampled dataset $\widehat{{\mathcal{Z}}}$, history of execution
$\mathcal{T}$

1:
${\mathcal{D}}_{h}^{k}\leftarrow\\{(s_{h}^{\tau},a_{h}^{\tau},r_{h}^{\tau}+V_{h+1}^{k}(s_{h+1}^{\tau}))\\}_{\tau\in[k-1]}$

2:
$\widehat{f}\leftarrow\arg\min_{f\in{\mathcal{F}}}||f||^{2}_{{\mathcal{D}}}$

3:
$\widehat{F}_{h}^{k}\leftarrow\\{f_{1},f_{2}\in{\mathcal{F}}:\min\\{\|f_{1}-f_{2}\|^{2}_{\widehat{{\mathcal{Z}}}_{h}^{k}},T(H+1)^{2}\leq\beta\\}$

4:
$b_{h}^{k}(\cdot,\cdot)\leftarrow\sup_{f_{1},f_{2}\in\widehat{{\mathcal{F}}}^{k}_{h}}|f_{1}(\cdot,\cdot)-f_{2}(\cdot,\cdot)|$

5: Return $\min\\{f_{h}^{k}(\cdot,\cdot)+b_{h}^{k}(\cdot,\cdot),H\\}$

Algorithm 2 Q-function Model-Free Estimator

0: Function class ${\mathcal{F}}$, current sub-sampled dataset
$\widehat{{\mathcal{Z}}}$, new element $z=(s,a)$, failure probability
$\delta\in(0,1)$

1: Let $p_{z}$ be the smallest number such that $1/p_{z}$ is an integer and
$p_{z}$ is greater than
$\displaystyle\min\\{1,C\textnormal{sensitivity}_{\widehat{{\mathcal{Z}}},{\mathcal{F}}}\newline
\log(T{\mathcal{N}}({\mathcal{F}},\sqrt{\delta/(64T^{3})})/\delta)\\}$

2: Let
$\widehat{z}\in{\mathcal{C}}{({\mathcal{S}}\times{\mathcal{A}},1/16\sqrt{64T^{3}/\delta})}$
such that  $\sup_{f\in{\mathcal{F}}}|f(z)-f(\widehat{z})|\leq
1/16\sqrt{64T^{3}/\delta}$

3: Add $1/p_{z}$ copies of $\widehat{z}$ into $\widehat{{\mathcal{Z}}}$ with
probability $p_{z}$

4: Return $\widehat{{\mathcal{Z}}}$

Algorithm 3 Model-Free Sampling Routine

We are now ready to state our main result in this setting.

######  Theorem 3.1.

There exists an absolute constant $C>0,$ and a proper parameter $\beta$ for
Algorithm 1 such that with probability of at least $1-\lceil\log T\rceil
e^{-\tau}-\delta$ the regret of the algorithm is bounded by

$\displaystyle{\textnormal{Regret}}(K)\leq\frac{Cd_{{\mathcal{F}}}H^{5}\log^{4}T}{{\textnormal{gap}}_{\min}}+\frac{16H^{2}\tau}{3}+2,$

for any $\delta,\tau>0$, where
$d_{{\mathcal{F}}}=\dim^{2}_{E}({\mathcal{F}},1/T)\cdot\log({\mathcal{N}}({\mathcal{F}},\delta/T^{2})/\delta)\cdot\log({\mathcal{C}}({\mathcal{S}}\times{\mathcal{A}},\delta/T^{2})/\delta)$
is a parameter that captures the complexity of the function class. The value
of the parameter $\beta$ is

$\displaystyle\beta=Cd^{\prime}_{{\mathcal{F}}}H^{2}\log^{4}T,$

where
$d^{\prime}_{{\mathcal{F}}}=\log({\mathcal{N}}({\mathcal{F}},\delta/T^{3})/\delta)\dim_{E}({\mathcal{F}},1/T)\log({\mathcal{N}}({\mathcal{S}}\times{\mathcal{A}},\delta/T^{3})/\delta))$.
Moreover, the number of switching policies is bounded by

$\displaystyle
O\left(H\log(T{\mathcal{N}}({\mathcal{F}},\sqrt{\delta}/T^{2})/\delta)\dim_{E}({\mathcal{F}},1/T)\log^{2}T\right).$

Notice that the regret in the previous bound depends on $\log T$ and
$1/{\textnormal{gap}}_{\min}$. We show that this dependence is necessary.

######  Remark 3.2.

There exists an MDP that satisfies Assumption 2.2 and Assumption 2.3 such that
the expected regret of every algorithm is lower bounded by

$\operatorname*{\mathbb{E}}[{\textnormal{Regret}}(K)]\geq\Omega\left({\rm
poly}(\log(T))\cdot{\rm
poly}(H)\cdot\frac{1}{{\textnormal{gap}}_{\min}}\right).$

It is known that the setting we are studying captures the tabular MDP setting
(see e.g. (Wang et al., 2020)). Hence, we can see that the result by Ok et al.
(2018); Simchowitz & Jamieson (2019) we mentioned proves our claim.

###  3.2 Model-Based Setting

In this regime, we assume that the MDP satisfies Assumption 2.4. We also
assume that the reward function is known to the learner similar to Ayoub et
al. (2020). If the reward is unknown, we just estimate it and construct a
confidence region.

Before we discuss the details of our approach, we need to describe an
important set of functions that show up in our algorithm and in the regret
guarantee. Let ${\cal V}$ be the set of all measurable functions that are
bounded by $H$. Let ${\cal P}_{h}$ be the set of potential models in step $H$.
We also let $f:{\mathcal{S}}\times{\mathcal{A}}\times{\cal
V}\rightarrow\mathbb{R}$ and define the following set:

$\displaystyle{\mathcal{F}}_{h}$
$\displaystyle=\biggl{\\{}f:\exists\tilde{P}_{h}\in{\cal P}_{h}\text{ so that
}f(s,a,V)=\int_{\mathcal{S}}\tilde{P}_{h}(s^{\prime}|s,a)V(s^{\prime})ds^{\prime},\forall(s,a,V)\in{\mathcal{S}}\times{\mathcal{A}}\times{\cal
V}\biggr{\\}}.$

The bounds we state scale with the complexity of ${\mathcal{F}}_{h}$. The
Q-function estimator and the sampling routine we use that are specific to this
setting are presented in Algorithm 4 and Algorithm 5, respectively. The
dataset includes elements of the form
$z_{h}^{k}=(s_{h}^{k},a_{h}^{k},V^{k}_{h+1}(\cdot))$. The Q-function routine
works in the following way. We first estimate a model $\widehat{P}_{h}\in{\cal
P}_{h}$ using a least-squares estimator that is based on all the previous
interactions with the MDP. Using a concentration argument for this estimator
of the model, similar to Russo & Van Roy (2013); Ayoub et al. (2020), we can
show that for an appropriate choice of $\beta$, the estimated model lies in a
data-dependent ball centered at $\widehat{P}_{h}$, with high probability (see
Lemma B.11 in the Appendix). Thus, we can set the bonus function to be the
diameter of this ball in order to ensure that $\widehat{Q}_{h}$ is an
optimistic estimate of $Q_{h}^{*}$. In addition, the choice of $\beta$ ensures
that the bonus we add is not very large. Notice also that since the
concentration argument in this setting differs with that in the model-free
setting, we do not need to round the elements that we are adding to the sub-
sampled dataset.

In this setting, the main reason we sub-sample the dataset is to achieve
logarithmic adaptivity. Moreover, not using the entire dataset to compute the
bonus function improves the computational complexity of our algorithm. To
bound the adaptivity complexity, we use a similar approach as in Kong et al.
(2021).

0: Function class ${\mathcal{F}}$, current sub-sampled dataset
$\widehat{{\mathcal{Z}}}$, current regression dataset ${\mathcal{D}}$

1: $\widehat{P}_{h}^{k}\leftarrow\arg\min_{P\in{\cal P}_{h}}\newline \hskip
1.00006pt\sum_{k^{\prime}=1}^{k-1}\left(\langle
P(\cdot|s_{h}^{k^{\prime}},a_{h}^{k^{\prime}}),V_{h+1}^{k^{\prime}}\rangle-
V_{h+1}^{k^{\prime}}(s_{h+1}^{k^{\prime}})\right)^{2}$

2:
${\mathcal{F}}_{h}^{k}=\\{f_{1},f_{2}:\min\\{||f_{1}-f_{2}||_{\widehat{{\mathcal{Z}}}_{h}^{k}},T(H+1)^{2}\\}\leq\beta\\}$

3:
$b_{h}^{k}(\cdot,\cdot)\leftarrow\sup_{f_{1},f_{2}\in{\mathcal{F}}^{k}_{h}}|f_{1}(\cdot,\cdot,V_{h+1})-f_{2}(\cdot,\cdot,V_{h+1})|$

4: Return
$\min\\{r_{h}(\cdot,\cdot)+\langle\widehat{P}^{k}_{h}(\cdot|\cdot,\cdot),V^{k}_{h+1}\rangle+b_{h}^{k}(\cdot,\cdot),H\\}$

Algorithm 4 Q-function Model-Based Estimator

0: Function class ${\mathcal{F}}$, current sub-sampled dataset
$\widehat{{\mathcal{Z}}}$, new element $z=(s,a,V)$, failure probability
$\delta\in(0,1)$

1: Let $p_{z}$ be the smallest number such that $1/p_{z}$ is an integer and
$p_{z}$ is greater than
$\min\\{1,C\cdot\textnormal{sensitivity}_{\widehat{{\mathcal{Z}}},{\mathcal{F}}}\cdot\log(T{\mathcal{N}}({\mathcal{F}},\sqrt{\delta/(64T^{3})})/\delta)\\}$

2: Add $1/p_{z}$ copies of $z$ into $\widehat{{\mathcal{Z}}}$ with probability
$p_{z}$

3: Return $\widehat{{\mathcal{Z}}}$

Algorithm 5 Model-Based Sampling Routine

We are now ready to state our main result in this setting.

######  Theorem 3.3.

There exists an absolute constant $C$ and a proper value of the parameter
$\beta$ for Algorithm 1 such that with probability at least $1-\lceil\log
T\rceil e^{-\tau}-\delta$ the regret of the algorithm is bounded by

$\displaystyle\textnormal{Regret}(K)\leq\frac{Cd_{{\mathcal{F}}}H^{5}\log
T}{{\textnormal{gap}}_{\min}}+\frac{16H^{2}\tau}{3}+2,$

where
$d_{{\mathcal{F}}}=\log({\mathcal{N}}({\mathcal{F}},1/T)/\delta)\dim^{2}_{E}({\mathcal{F}},1/T)$.
The value of the parameter $\beta$ is

$\displaystyle\beta$
$\displaystyle=4H^{2}\log(2{\mathcal{N}}({\mathcal{F}},1/T)/\delta)+4/H\left(C+\sqrt{H^{2}/4\log(T/\delta)}\right),$

where
${\mathcal{N}}({\mathcal{F}},1/T)=\max_{h\in[H]}{\mathcal{N}}({\mathcal{F}}_{h},1/T),\dim_{E}({\mathcal{F}},1/T)=\max_{h\in[H]}\dim_{E}({\mathcal{F}}_{h},1/T)$.

The number of switching policies is bounded by

$O\left(H\log(T{\mathcal{N}}(F,\sqrt{\delta/(64T^{3})})/\delta)\dim_{E}({\mathcal{F}},1/T)\log^{2}T\right).$

As in Section 3.1, notice that the regret in the previous bound depends on
$\log T$ and $1/{\textnormal{gap}}_{\min}$. We show that this dependence is
indeed necessary.

######  Remark 3.4.

There exists an MDP that satisfies Assumption 2.4 such that the expected
regret of every algorithm is lower bounded by

$\operatorname*{\mathbb{E}}[{\textnormal{Regret}}(K)]\geq\Omega\left({\rm
poly}(\log(T)){\rm poly}(H)\frac{1}{{\textnormal{gap}}_{\min}}\right).$

It is known that the setting we are studying captures the tabular MDP setting
(see e.g. (Ayoub et al., 2020)), so the proof follows from the result by Ok et
al. (2018); Simchowitz & Jamieson (2019).

We remark that if we want to derive instance-independent regret guarantees and
follow the regret decomposition in Ayoub et al. (2020), we can get a
$\sqrt{T}$-regret with logarithmic adaptivity.

##  4 Proof Sketch of Main Results

In this section, we sketch the proof of our main results. Due to space
limitation, we only discuss the model-free setting. The full proofs in the
model-free, model-based setting can be found in Appendix A, Appendix B,
respectively.

The first step in our analysis is the regret decomposition of the algorithm.
Lemma A.1 shows that
$\operatorname*{\mathbb{E}}\left[{\textnormal{Regret}}(K)\right]=\operatorname*{\mathbb{E}}\left[\sum_{k=1}^{K}\sum_{h=1}^{H}{\textnormal{gap}}_{h}(s_{h}^{k},a_{h}^{k})\right]$.
Thus, we see that to bound the regret it is enough to bound
$\sum_{k=1}^{K}{\textnormal{gap}}_{h}(s_{h}^{k},a_{h}^{k})$ for every
$h\in[H]$. Towards this end, notice that
${\textnormal{gap}}_{h}(s_{h}^{k},a_{h}^{k})\in[{\textnormal{gap}}_{\min},H]$.
We apply the “peeling technique” that has also been used in local Rademacher
complexities (Bartlett et al., 2005) and in He et al. (2021); Yang et al.
(2021). The idea is to split the interval $[0,H]$ into
$\log(H/{\textnormal{gap}}_{\min})$ intervals, where the $i$-th interval is
$[2^{i-1}{\textnormal{gap}}_{\min},2^{i}{\textnormal{gap}}_{\min}]$. Hence,
for every ${\textnormal{gap}}_{h}(s_{h},a_{h})$ that falls in the $i$-th
interval its contribution to the regret is at most
$2^{i}{\textnormal{gap}}_{\min}$. Thus, to bound the regret it suffices to
bound the number of suboptimalities that fall into every interval. Notice that
for some ${\textnormal{gap}}_{h}(s_{h}^{k},a_{h}^{k})$ in this interval we
have that

$\displaystyle
V_{h}^{*}(s_{h}^{k})-Q_{h}^{\pi_{k}}(s_{h}^{k},a_{h}^{k})\geq{\textnormal{gap}}_{h}(s_{h}^{k},a_{h}^{k})\geq
2^{i-1}{\textnormal{gap}}_{\min},$

so it suffices to bound the number of sub-optimalities
$V_{h}^{*}(s_{h}^{k})-Q_{h}^{\pi_{k}}(s_{h}^{k},a_{h}^{k})$ that fall into the
$i$-th interval. Both for the model-free and the model-based setting, we can
derive such a bound. Finally, notice that once we have bounded the number of
suboptimilaties in every interval, it is not difficult to bound the total
regret. Let
$C_{i}=[2^{i-1}{\textnormal{gap}}_{\min},2^{i}{\textnormal{gap}}_{\min})$ and
$N=\log(H/{\textnormal{gap}}_{\min})$. Then, we know that
${\textnormal{Regret}}(K)$ can be upper bounded by

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}{\textnormal{gap}}_{h}(s_{h}^{k},a_{h}^{k})$
$\displaystyle\qquad=\sum_{i=1}^{N}\sum_{{\textnormal{gap}}_{h}(s_{h}^{k},a_{h}^{k})\in
C_{i}}{\textnormal{gap}}_{h}(s_{h}^{k},a_{h}^{k})$
$\displaystyle\qquad\leq\sum_{i=1}^{N}\sum_{k=1}^{K}2^{i}\mathbbm{1}\left[{\textnormal{gap}}_{h}(s_{h}^{k},a_{h}^{k})\in
C_{i}\right]$
$\displaystyle\qquad\leq\sum_{i=1}^{N}2^{i}\sum_{k=1}^{K}\mathbbm{1}\left[V^{*}_{h}(s_{h}^{k})-Q_{h}^{\pi_{k}}(s_{h}^{k},a_{h}^{k})\geq
2^{i-1}{\textnormal{gap}}_{\min}\right].$

Hence, deriving the regret guarantee boils down to bounding
$\sum_{k=1}^{K}\mathbbm{1}\left[V^{*}_{h}(s_{h}^{k})-Q_{h}^{\pi_{k}}(s_{h}^{k},a_{h}^{k})\geq
2^{i}{\textnormal{gap}}_{\min}\right]$. We provide such a bound in Lemma A.9,
which depends polynomially on $\log T,1/{\textnormal{gap}}_{\min}$, and the
complexity parameters of the function class. The outline of the proof is the
following. We fix some episode $h\in[H]$ and let $K^{\prime}$ be the set of
rounds where $V^{*}_{h}(s_{h}^{k})-Q_{h}^{\pi_{k}}(s_{h}^{k},a_{h}^{k})\geq
2^{i}{\textnormal{gap}}_{\min}$. To get a bound on $|K^{\prime}|$, our
approach is to lower bound and upper bound the quantity
$\sum_{i=1}^{|K^{\prime}|}Q_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})-Q_{h}^{\pi_{k_{i}}}(s_{h}^{\pi_{k_{i}}},a_{h}^{\pi_{k_{i}}})$
by $f_{1}(|K^{\prime}|),f_{2}(|K^{\prime}|)$, respectively. Then, we use the
fact that $f_{1}(|K^{\prime}|)\leq f_{2}(|K^{\prime}|)$ to establish our
bound. For the lower bound, using the definition of $K^{\prime}$ we get
$f_{1}(|K^{\prime}|)=2^{i}{\textnormal{gap}}_{\min}|K^{\prime}|$. For the
upper bound, we leverage the fact that
$Q_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})\leq\langle
P_{h}(\cdot|s_{h}^{k_{i}},a_{h}^{k_{i}}),V_{h+1}^{k_{i}}\rangle+2b_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})$
(cf. Lemma A.8) and obtain
$f_{2}(|K^{\prime}|)\leq\sum_{i=1}^{|K^{\prime}|}\sum_{h^{\prime}=h}^{H}\varepsilon_{h^{\prime}}^{k_{i}}+\sum_{i=1}^{|K^{\prime}|}\sum_{h^{\prime}=h}^{H}b_{h^{\prime}}^{k_{i}}(s_{h^{\prime}}^{k_{i}},a_{h^{\prime}}^{k_{i}})$,
where $\varepsilon_{h}^{k_{i}}$ forms a bounded martingale difference
sequence. We bound each term on the RHS separately. For the first one, we use
the Azuma-Hoeffding inequality which can be found in Lemma A.7. For the second
term, we generalize the bound on the summation of the bonus functions over all
the episodes from Kong et al. (2021), and show that a similar bound holds for
the summation of the bonus over _any_ set of episodes $K^{\prime}$ (see Lemma
A.6). Putting everything together, we get that
$|K^{\prime}|=O\left(1/(4^{i}{\textnormal{gap}}_{\min})\cdot
H^{4}\cdot\log^{4}T\cdot{\rm poly}(d_{{\mathcal{F}}})\right)$, where
$d_{{\mathcal{F}}}$ is the complexity parameter of the class.

##  5 Conclusion

In this paper, we consider episodic RL with general function approximation. We
prove that there are algorithms with logarithmic adaptivity complexity both in
the model-free and model-based settings that achieve logarithmic instance-
dependent regret guarantees. An interesting open question is to establish the
optimal dependence of the regret guarantees on the planning horizon $H$.

## References

  * (1)
  * Abbasi-Yadkori et al. (2011) Abbasi-Yadkori, Y., Pál, D. & Szepesvári, C. (2011), ‘Improved algorithms for linear stochastic bandits’, Advances in neural information processing systems 24, 2312–2320.
  * Agarwal et al. (2017) Agarwal, A., Agarwal, S., Assadi, S. & Khanna, S. (2017), Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons, in ‘Conference on Learning Theory’, PMLR, pp. 39–75.
  * Agarwal et al. (2020) Agarwal, A., Kakade, S., Krishnamurthy, A. & Sun, W. (2020), ‘Flambe: Structural complexity and representation learning of low rank mdps’, arXiv preprint arXiv:2006.10814 .
  * Auer & Ortner (2007) Auer, P. & Ortner, R. (2007), Logarithmic online regret bounds for undiscounted reinforcement learning, in ‘Advances in neural information processing systems’, pp. 49–56.
  * Ayoub et al. (2020) Ayoub, A., Jia, Z., Szepesvari, C., Wang, M. & Yang, L. (2020), Model-based reinforcement learning with value-targeted regression, in ‘International Conference on Machine Learning’, PMLR, pp. 463–474.
  * Bai et al. (2019) Bai, Y., Xie, T., Jiang, N. & Wang, Y.-X. (2019), ‘Provably efficient q-learning with low switching cost’, arXiv preprint arXiv:1905.12849 .
  * Bartlett et al. (2005) Bartlett, P. L., Bousquet, O. & Mendelson, S. (2005), ‘Local rademacher complexities’, The Annals of Statistics 33(4), 1497–1537.
  * Bubeck & Cesa-Bianchi (2012) Bubeck, S. & Cesa-Bianchi, N. (2012), ‘Regret analysis of stochastic and nonstochastic multi-armed bandit problems’, arXiv preprint arXiv:1204.5721 .
  * Cai et al. (2020) Cai, Q., Yang, Z., Jin, C. & Wang, Z. (2020), Provably efficient exploration in policy optimization, in ‘International Conference on Machine Learning’, PMLR, pp. 1283–1294.
  * Cesa-Bianchi & Lugosi (2006) Cesa-Bianchi, N. & Lugosi, G. (2006), Prediction, learning, and games, Cambridge university press.
  * Chen et al. (2020) Chen, L., Yu, Q., Lawrence, H. & Karbasi, A. (2020), ‘Minimax regret of switching-constrained online convex optimization: No phase transition’, Advances in Neural Information Processing Systems 33, 3477–3486.
  * Dong et al. (2020) Dong, K., Li, Y., Zhang, Q. & Zhou, Y. (2020), Multinomial logit bandit with low switching cost, in ‘International Conference on Machine Learning’, PMLR, pp. 2607–2615.
  * Du et al. (2020) Du, S. S., Lee, J. D., Mahajan, G. & Wang, R. (2020), ‘Agnostic q-learning with function approximation in deterministic systems: Near-optimal bounds on approximation error and sample complexity’, Advances in Neural Information Processing Systems 2020.
  * Duan et al. (2016) Duan, Y., Chen, X., Houthooft, R., Schulman, J. & Abbeel, P. (2016), Benchmarking deep reinforcement learning for continuous control, in ‘International conference on machine learning’, PMLR, pp. 1329–1338.
  * Foster et al. (2020) Foster, D. J., Rakhlin, A., Simchi-Levi, D. & Xu, Y. (2020), ‘Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement-based perspective’, arXiv preprint arXiv:2010.03104 .
  * Freedman (1975) Freedman, D. A. (1975), ‘On tail probabilities for martingales’, the Annals of Probability pp. 100–118.
  * Gao et al. (2021) Gao, M., Xie, T., Du, S. S. & Yang, L. F. (2021), ‘A provably efficient algorithm for linear markov decision process with low switching cost’, arXiv preprint arXiv:2101.00494 .
  * Gao et al. (2019) Gao, Z., Han, Y., Ren, Z. & Zhou, Z. (2019), ‘Batched multi-armed bandits problem’, arXiv preprint arXiv:1904.01763 .
  * Gnedenko & Kovalenko (1989) Gnedenko, B. V. & Kovalenko, I. N. (1989), Introduction to queueing theory, Birkhauser Boston Inc.
  * He et al. (2021) He, J., Zhou, D. & Gu, Q. (2021), Logarithmic regret for reinforcement learning with linear function approximation, in ‘International Conference on Machine Learning’, PMLR, pp. 4171–4180.
  * Jaksch et al. (2010) Jaksch, T., Ortner, R. & Auer, P. (2010), ‘Near-optimal regret bounds for reinforcement learning.’, Journal of Machine Learning Research 11(4).
  * Jiang et al. (2017) Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J. & Schapire, R. E. (2017), Contextual decision processes with low bellman rank are pac-learnable, in ‘International Conference on Machine Learning’, PMLR, pp. 1704–1713.
  * Jin et al. (2021) Jin, C., Liu, Q. & Miryoosefi, S. (2021), ‘Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms’, arXiv preprint arXiv:2102.00815 .
  * Jin et al. (2020) Jin, C., Yang, Z., Wang, Z. & Jordan, M. I. (2020), Provably efficient reinforcement learning with linear function approximation, in ‘Conference on Learning Theory’, PMLR, pp. 2137–2143.
  * Kakade et al. (2020) Kakade, S., Krishnamurthy, A., Lowrey, K., Ohnishi, M. & Sun, W. (2020), ‘Information theoretic regret bounds for online nonlinear control’, arXiv preprint arXiv:2006.12466 .
  * Kong et al. (2021) Kong, D., Salakhutdinov, R., Wang, R. & Yang, L. F. (2021), ‘Online sub-sampling for reinforcement learning with general function approximation’, arXiv preprint arXiv:2106.07203 .
  * Lattimore & Szepesvári (2020) Lattimore, T. & Szepesvári, C. (2020), Bandit algorithms, Cambridge University Press.
  * Li et al. (2021) Li, G., Kamath, P., Foster, D. J. & Srebro, N. (2021), ‘Eluder dimension and generalized rank’, arXiv preprint arXiv:2104.06970 .
  * Mnih et al. (2015) Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G. et al. (2015), ‘Human-level control through deep reinforcement learning’, nature 518(7540), 529–533.
  * Modi et al. (2020) Modi, A., Jiang, N., Tewari, A. & Singh, S. (2020), Sample complexity of reinforcement learning using linearly combined model ensembles, in ‘International Conference on Artificial Intelligence and Statistics’, PMLR, pp. 2010–2020.
  * Ok et al. (2018) Ok, J., Proutiere, A. & Tranos, D. (2018), ‘Exploration in structured reinforcement learning’, arXiv preprint arXiv:1806.00775 .
  * Osband & Van Roy (2014) Osband, I. & Van Roy, B. (2014), ‘Model-based reinforcement learning and the eluder dimension’, arXiv preprint arXiv:1406.1853 .
  * Osband et al. (2016) Osband, I., Van Roy, B. & Wen, Z. (2016), Generalization and exploration via randomized value functions, in ‘International Conference on Machine Learning’, PMLR, pp. 2377–2386.
  * Perchet et al. (2016) Perchet, V., Rigollet, P., Chassang, S. & Snowberg, E. (2016), ‘Batched bandit problems’, The Annals of Statistics 44(2), 660–681.
  * Pires & Szepesvári (2016) Pires, B. Á. & Szepesvári, C. (2016), Policy error bounds for model-based reinforcement learning with factored linear models, in ‘Conference on Learning Theory’, PMLR, pp. 121–151.
  * Ruan et al. (2021) Ruan, Y., Yang, J. & Zhou, Y. (2021), Linear bandits with limited adaptivity and learning distributional optimal design, in ‘Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing’, pp. 74–87.
  * Russo & Van Roy (2013) Russo, D. & Van Roy, B. (2013), Eluder dimension and the sample complexity of optimistic exploration., in ‘NIPS’, Citeseer, pp. 2256–2264.
  * Silver et al. (2016) Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M. et al. (2016), ‘Mastering the game of go with deep neural networks and tree search’, nature 529(7587), 484–489.
  * Silver et al. (2017) Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A. et al. (2017), ‘Mastering the game of go without human knowledge’, nature 550(7676), 354–359.
  * Simchowitz & Jamieson (2019) Simchowitz, M. & Jamieson, K. G. (2019), ‘Non-asymptotic gap-dependent regret bounds for tabular mdps’, Advances in Neural Information Processing Systems 32, 1153–1162.
  * Slivkins (2019) Slivkins, A. (2019), ‘Introduction to multi-armed bandits’, arXiv preprint arXiv:1904.07272 .
  * Sutton & Barto (2018) Sutton, R. S. & Barto, A. G. (2018), Reinforcement learning: An introduction, MIT press.
  * Tewari & Bartlett (2007) Tewari, A. & Bartlett, P. L. (2007), Optimistic linear programming gives logarithmic regret for irreducible mdps., in ‘NIPS’, Citeseer, pp. 1505–1512.
  * Vinyals et al. (2019) Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung, J., Choi, D. H., Powell, R., Ewalds, T., Georgiev, P. et al. (2019), ‘Grandmaster level in starcraft ii using multi-agent reinforcement learning’, Nature 575(7782), 350–354.
  * Wang et al. (2020) Wang, R., Salakhutdinov, R. & Yang, L. F. (2020), ‘Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension’, arXiv preprint arXiv:2005.10804 .
  * Wang et al. (2021) Wang, T., Zhou, D. & Gu, Q. (2021), ‘Provably efficient reinforcement learning with linear function approximation under adaptivity constraints’, arXiv preprint arXiv:2101.02195 .
  * Yang et al. (2021) Yang, K., Yang, L. & Du, S. (2021), Q-learning with logarithmic regret, in ‘International Conference on Artificial Intelligence and Statistics’, PMLR, pp. 1576–1584.
  * Yang & Wang (2019) Yang, L. & Wang, M. (2019), Sample-optimal parametric q-learning using linearly additive features, in ‘International Conference on Machine Learning’, PMLR, pp. 6995–7004.
  * Yang & Wang (2020) Yang, L. & Wang, M. (2020), Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound, in ‘International Conference on Machine Learning’, PMLR, pp. 10746–10756.
  * Zanette, Brandfonbrener, Brunskill, Pirotta & Lazaric (2020) Zanette, A., Brandfonbrener, D., Brunskill, E., Pirotta, M. & Lazaric, A. (2020), Frequentist regret bounds for randomized least-squares value iteration, in ‘International Conference on Artificial Intelligence and Statistics’, PMLR, pp. 1954–1964.
  * Zanette, Lazaric, Kochenderfer & Brunskill (2020) Zanette, A., Lazaric, A., Kochenderfer, M. & Brunskill, E. (2020), Learning near optimal policies with low inherent bellman error, in ‘International Conference on Machine Learning’, PMLR, pp. 10978–10989.
  * Zhang et al. (2020) Zhang, Z., Zhou, Y. & Ji, X. (2020), ‘Almost optimal model-free reinforcement learning via reference-advantage decomposition’, arXiv preprint arXiv:2004.10019 .
  * Zhou et al. (2021) Zhou, D., He, J. & Gu, Q. (2021), Provably efficient reinforcement learning for discounted mdps with feature mapping, in ‘International Conference on Machine Learning’, PMLR, pp. 12793–12802.

##  Appendix A Proof of Theorem 3.1

In this section, our main goal is to prove Theorem 3.1. Recall that we assume
we have access to a set
${\mathcal{F}}\subseteq\\{f:{\mathcal{S}}\times{\mathcal{A}}\rightarrow[0,H+1]\\}$,
which we use to approximate the Q-function. For this set, we work with
Assumption 2.2 and Assumption 2.3.

The proofs of the supporting lemmas are postponed to Appendix A.1. Before we
are ready to prove our result, we need to discuss some results of prior works
that are crucial to our proof.

The regret decomposition in He et al. (2021), gives us that

######  Lemma A.1.

(He et al. 2021) For any MDP $M$ we have that

$\displaystyle\operatorname*{\mathbb{E}}\left[{\textnormal{Regret}}(K)\right]=\operatorname*{\mathbb{E}}\left[\sum_{k=1}^{K}\sum_{h=1}^{H}{\textnormal{gap}}_{h}(s_{h}^{k},a_{h}^{k})\right].$

Moreover, for any $\tau>0$ it holds with probability at least $1-\lceil\log
T\rceil e^{-\tau}$ that

$\displaystyle{\textnormal{Regret}}(K)\leq
2\sum_{k=1}^{K}\sum_{h=1}^{H}{\textnormal{gap}}_{h}(s_{h}^{k},a_{h}^{k})+\frac{16H^{2}\tau}{3}+2.$

The following lemma resembles Lemma 6.3 (He et al. 2021). Its proof is
postponed to Appendix A.1.

######  Lemma A.2.

If we pick

$\beta=CH^{2}\log(T{\mathcal{N}}({\mathcal{F}},\delta/T^{2})/\delta)\dim_{E}({\mathcal{F}},1/T)\log^{2}T\log\left({\mathcal{C}}({\mathcal{S}}\times{\mathcal{A}},\delta/T^{2})T/\delta)\right),$

for come constant C and for $h\in[H]$, then we have that with probability at
least $1-2K\delta$

$\displaystyle\sum_{k=1}^{K}\left(V_{h}^{*}(s_{h}^{k})-Q_{h}^{*}(s_{h}^{k},a_{h}^{k})\right)\leq\frac{CH^{4}\dim^{2}_{E}({\mathcal{F}},1/T)\log^{2}T\log(T{\mathcal{N}}({\mathcal{F}},\delta/T^{2})/\delta)\log({\mathcal{C}}({\mathcal{S}}\times{\mathcal{A}},\delta/T^{2})T/\delta)}{{\textnormal{gap}}_{\min}}.$

We are now ready to state the regret bound of our algorithm. In particular the
regret guarantee follows from the regret decomposition and the bound we
established before.

######  Lemma A.3.

There exists a constant $C$ and proper values of the parameter $\beta$ of
Algorithm 1 such that with probability at least $1-\lceil\log T\rceil
e^{-\tau}-2K\delta$ the regret of the algorithm is bounded by

$\displaystyle{\textnormal{Regret}}(K)\leq\frac{CH^{5}\dim^{2}_{E}({\mathcal{F}},1/T)\log^{2}T\log(T{\mathcal{N}}({\mathcal{F}},\delta/T^{2})/\delta)\log({\mathcal{C}}({\mathcal{S}}\times{\mathcal{A}},\delta/T^{2})T/\delta)}{{\textnormal{gap}}_{\min}}+\frac{16H^{2}\tau}{3}+2.$

The choice of the parameter is

$\beta=CH^{2}\log(T{\mathcal{N}}({\mathcal{F}},\delta/T^{2})/\delta)\dim_{E}({\mathcal{F}},1/T)\log^{2}T\log\left({\mathcal{C}}({\mathcal{S}}\times{\mathcal{A}},\delta/T^{2})T/\delta)\right).$

###### Proof.

Throughout the proof, we condition on the events described in Lemma A.1, A.2
which happen with probability at least $1-\lceil\log T\rceil
e^{-\tau}-2K\delta$.

From Lemma A.1 we have that

$\displaystyle{\textnormal{Regret}}(K)\leq
2\sum_{k=1}^{K}\sum_{h=1}^{H}{\textnormal{gap}}_{h}(s_{h}^{k},a_{h}^{k})+\frac{16H^{2}\tau}{3}+2.$

We can bound the first term on the RHS using Lemma A.2 as follows

$\displaystyle
2\sum_{k=1}^{K}\sum_{h=1}^{H}{\textnormal{gap}}_{h}(s_{h}^{k},a_{h}^{k})$
$\displaystyle=2\sum_{k=1}^{K}\sum_{h=1}^{H}\left(V_{h}^{*}(s_{h}^{k})-Q_{h}^{*}(s_{h}^{k},a_{h}^{k})\right)$
$\displaystyle\leq\frac{CH^{5}\dim^{2}_{E}({\mathcal{F}},1/T)\log^{2}T\log(T{\mathcal{N}}({\mathcal{F}},\delta/T^{2})/\delta)\log({\mathcal{C}}({\mathcal{S}}\times{\mathcal{A}},\delta/T^{2})T/\delta)}{{\textnormal{gap}}_{\min}}.$

Hence, for the total regret we have that

$\displaystyle{\textnormal{Regret}}(K)\leq\frac{CH^{5}\dim^{2}_{E}({\mathcal{F}},1/T)\log^{2}T\log(T{\mathcal{N}}({\mathcal{F}},\delta/T^{2})/\delta)\log({\mathcal{C}}({\mathcal{S}}\times{\mathcal{A}},\delta/T^{2})T/\delta)}{{\textnormal{gap}}_{\min}}+\frac{16H^{2}\tau}{3}+2.$

∎

Finally, we state the bound on the adaptivity of our algorithm. In particular,
since our algorithm is the same as in Kong et al. (2021), the logarithmic
switching cost follows directly from their result.

######  Lemma A.4.

(Kong et al. 2021) For any fixed $h\in[H]$, With probability $1-\delta$, the
sub-sampled dataset $\widehat{{\mathcal{Z}}}_{h}^{k}$ changes at most

$O\left(\log(T{\mathcal{N}}({\mathcal{F}},\sqrt{\delta/T^{3}})/\delta)\dim_{E}({\mathcal{F}},1/T)\log^{2}T\right)$

times.

We are now ready to prove Theorem 3.1.

Proof of Theorem 3.1:

The proof of this theorem follows by using Lemma A.3 and taking a union on the
result of Lemma A.4 and setting the error probability accordingly. $\Box$

###  A.1 Supporting Lemmas: Theorem 3.1

In this section, we present the proof of Lemma A.2.

First, we need to show that the sub-sampled dataset is a good approximation of
the original one. To this end, we use Proposition 1 from Kong et al. (2021).

######  Proposition A.5.

(Kong et al. 2021) For any $h,k\in[H]\times[K]$ we let

$\displaystyle\underline{b}_{h}^{k}(\cdot,\cdot)=\sup_{\|f_{1}-f_{2}\|^{2}_{\mathcal{Z}^{k}_{h}}\leq\beta/100}|f_{1}(\cdot,\cdot)-f_{2}(\cdot,\cdot)|,$
$\displaystyle\overline{b}_{h}^{k}(\cdot,\cdot)=\sup_{\|f_{1}-f_{2}\|^{2}_{{\mathcal{Z}}^{k}_{h}}\leq
100\beta}|f_{1}(\cdot,\cdot)-f_{2}(\cdot,\cdot)|.$

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

$\displaystyle\underline{b}_{h}^{k}(\cdot,\cdot)\leq
b_{h}^{k}(\cdot,\cdot)\leq\overline{b}_{h}^{k}(\cdot,\cdot).$

We now present a generalized version of Lemma 11 (Kong et al. 2021) that will
be used to bound the regret of our algorithm. Essentially, this gives a bound
on the summation of the bonus terms over a set of episodes
$K^{\prime}\subseteq[K]$ in terms of the eluder dimension of the function
class and the number of episodes.

######  Lemma A.6.

For any set $K^{\prime}\subseteq[K]$ , with probability at least $1-\delta/32$
we have that

$\displaystyle\sum_{i=1}^{|K^{\prime}|}\sum_{h=1}^{H}b_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})\leq
H+H(H+1)\cdot\textnormal{dim}_{E}(\mathcal{F},1/T)+CH\sqrt{\textnormal{dim}_{E}(\mathcal{F},1/T)|K^{\prime}|\cdot\beta},$

where $C>0$ is some constant.

###### Proof.

Throughout the proof, we condition on the event defined in Proposition A.5.
This gives us that for any $k\in K^{\prime},h\in H$

$\displaystyle
b_{h}^{k}(s_{h}^{k},a_{h}^{k})\leq\bar{b}_{h}^{k}(s_{h}^{k},a_{h}^{k})=\sup_{||f_{1}-f_{2}||^{2}_{{\mathcal{Z}}_{h}^{k}}\leq
100\beta}|f_{1}(s_{h}^{k},a_{h}^{k})-f_{2}(s_{h}^{k},a_{h}^{k})|.$

We bound
$\sum_{i=1}^{K^{\prime}}\bar{b}_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})$ for
each $h\in[H]$ separately.

Given some $\epsilon>0$, we define
$\mathcal{L}_{h}=\\{(s_{h}^{k_{i}},a_{h}^{k_{i}}):k_{i}\in
K^{\prime},\bar{b}_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})>\epsilon\\}$, i.e.
the set of state-action pairs at step $h$ and some episode in $K^{\prime}$
where the bonus function has value greater than $\epsilon$. Consider some
$k\in K^{\prime}$. We denote $L_{h}=|\mathcal{L}_{h}|$,
$\widetilde{{\mathcal{Z}}}_{h}^{k}=\\{(s_{h}^{k},a_{h}^{k})\in{\mathcal{Z}}_{h}^{k},k\in
K^{\prime}\\}$ . Our goal is to show that there is some
$z_{h}^{k}=(s_{h}^{k},a_{h}^{k})\in\mathcal{L}_{h}$ that is
$\epsilon$-dependent on at least
$L_{h}/\textnormal{dim}_{E}({\mathcal{F}},\epsilon)-1$ disjoint subsequences
in ${\mathcal{Z}}_{h}^{k}\cap\mathcal{L}_{h}$. We also denote
$N=L_{h}/\textnormal{dim}_{E}({\mathcal{F}},\epsilon)-1$.

To do that, we decompose $\mathcal{L}_{h}$ into $N+1$ disjoint subsets and we
denote the $j$-th subset by $\mathcal{L}_{h}^{j}$. We use the following
procedure. Initially we set ${\mathcal{L}}_{h}^{j}=\emptyset$ for all
$j\in[N+1]$ and consider every $z_{h}^{k}\in{\mathcal{L}}_{h}$ in a sequential
manner. For each such $z_{h}^{k}$ we find the smallest index $j,1\leq j\leq
N$, such that $z_{h}^{k}$ is $\epsilon$-independent of the elements in
${\mathcal{L}}_{h}^{j}$ with respect to ${\mathcal{F}}$. If there is no such
$j$, we set $j=N+1$. Then, we update
${\mathcal{L}}_{h}^{j}\leftarrow{\mathcal{L}}_{h}^{j}\cup z_{h}^{k}$. Notice
that after we go through all the elements of ${\mathcal{L}}_{h}$, we must have
that ${\mathcal{L}}_{h}^{N+1}\neq\emptyset$. This is because every set
${\mathcal{L}}_{h}^{j},1\leq j\leq N$, contains at most
$\textnormal{dim}_{E}({\mathcal{F}},\epsilon)$ elements. Moreover, by
definition, every element $z_{h}^{k}\in{\mathcal{L}}_{h}^{N+1}$ is
$\epsilon$-dependent on
$N=L_{h}/\textnormal{dim}_{E}({\mathcal{F}},\epsilon)-1$ disjoint subsequences
in ${\mathcal{Z}}_{h}^{k}\cap{\mathcal{L}}^{h}$.

Furthermore, since $\bar{b}_{h}^{k}(s_{h}^{k},a_{h}^{k})>\epsilon$ for all
$z_{h}^{k}\in{\mathcal{L}}_{h}$ there must exist $f_{1},f_{2}\in{\mathcal{F}}$
such that $|f_{1}(s_{h}^{k},a_{h}^{k})-f_{2}(s_{h}^{k},a_{h}^{k})|>\epsilon$
and $||f_{1}-f_{2}||^{2}_{{\mathcal{Z}}_{h}^{k}}\leq 100\beta$. Hence, since
$z_{h}^{k}\in{\mathcal{L}}_{h}^{N+1}$ is $\epsilon$-dependent on $N$ disjoint
subsequences ${\mathcal{L}}_{h}^{j}$ and for each such subsequence, by the
definition of $\epsilon$-dependence, it holds that
$||f_{1}-f_{2}||_{{\mathcal{L}}_{h}^{j}}>\epsilon^{2}$ we have that

$\displaystyle
N\epsilon^{2}\leq||f_{1}-f_{2}||^{2}_{{\mathcal{Z}}_{h}^{k}}\leq
100\beta\implies(L_{h}/\textnormal{dim}_{E}({\mathcal{F}},\epsilon)-1)\epsilon^{2}\leq
100\beta\implies
L_{h}\leq\left(\frac{100\beta}{\epsilon^{2}}+1\right)\textnormal{dim}_{E}({\mathcal{F}},\epsilon).$

We now pick a permutation
$\bar{b}_{1}\geq\bar{b}_{2}\geq\ldots\geq\bar{b}_{|K^{\prime}|}$ of the bonus
functions $\\{\bar{b}_{h}^{k}(s^{k}_{h},a^{k}_{h})\\}_{k\in K^{\prime}}$. For
all $\bar{b}_{k}\geq 1/|K^{\prime}|$ it holds that

$\displaystyle
k\leq\left(\frac{100\beta}{\bar{b}_{k}^{2}}+1\right)\textnormal{dim}_{E}({\mathcal{F}},\bar{b}_{k})$
$\displaystyle\leq\left(\frac{100\beta}{\bar{b}_{k}^{2}}+1\right)\textnormal{dim}_{E}({\mathcal{F}},1/K^{\prime})\implies$
$\displaystyle\bar{b}_{k}$
$\displaystyle\leq\left(\frac{k}{\textnormal{dim}_{E}({\mathcal{F}},1/K^{\prime})}-1\right)^{-1/2}\sqrt{100\beta}.$

Moreover, notice that we get by definition that $\bar{b}_{k}\leq H+1$. Hence,
we have that

$\displaystyle\sum_{i=1}^{|K^{\prime}|}\bar{b}_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})$
$\displaystyle=\sum_{i:\bar{b}_{k_{i}}<1/|K^{\prime}|}\bar{b}_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})+\sum_{i:\bar{b}_{k_{i}}\geq
1/|K^{\prime}|}\bar{b}_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})$
$\displaystyle\leq|K^{\prime}|\cdot 1/|K^{\prime}|+\sum_{i:\bar{b}_{k_{i}}\geq
1/|K^{\prime}|,i\leq\textnormal{dim}_{E}({\mathcal{F}},1/|K^{\prime}|)}\bar{b}_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})+\sum_{i:\bar{b}_{k_{i}}\geq
1/|K^{\prime}|,|K^{\prime}|\geq
i>\textnormal{dim}_{E}({\mathcal{F}},1/|K^{\prime}|)}\bar{b}_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})$
$\displaystyle\leq
1+(H+1)\cdot\dim_{E}({\mathcal{F}},1/|K^{\prime}|)+\sum_{|K^{\prime}|\geq
i>\textnormal{dim}_{E}({\mathcal{F}},1/|K^{\prime}|)}\left(\frac{k}{\textnormal{dim}_{E}({\mathcal{F}},1/|K^{\prime}|)}-1\right)^{-1/2}\sqrt{100\beta}$
$\displaystyle\leq
1+(H+1)\cdot\dim_{E}({\mathcal{F}},1/|K^{\prime}|)+C\sqrt{\textnormal{dim}_{E}({\mathcal{F}},1/|K^{\prime}|)|K^{\prime}|\beta}$
$\displaystyle\leq
1+(H+1)\cdot\dim_{E}({\mathcal{F}},1/T)+C\sqrt{\textnormal{dim}_{E}({\mathcal{F}},1/T)|K^{\prime}|\beta}$

for some constant $C>0$, where the second to last inequality can be obtained
by bounding the summation by the integral and the last one by the definition
of the eluder dimension. Summing up all the inequalities for $h\in[H]$, we get
the result. ∎

We need the Azuma-Hoeffding inequality to bound a martingale difference
sequence. For completeness, we present it here as well.

######  Lemma A.7.

(Cesa-Bianchi & Lugosi 2006) Let $\\{x_{i}\\}_{i=1}^{n}$ be a martingale
difference sequence with respect to some filtration $\\{{\mathcal{F}}_{i}\\}$
for which $|x_{i}|\leq M$ for some constant $M$, $x_{i}$ is
${\mathcal{F}}_{i+1}$ measurable and
$\operatorname*{\mathbb{E}}[x_{i}|{\mathcal{F}}_{i}]=0$. Then, for any
$0<\delta<1$, we have that with probability at least $1-\delta$ it holds that

$\displaystyle\sum_{i=1}^{n}x_{i}\leq M\sqrt{2n\log(1/\delta)}.$

The following lemma that appears in Kong et al. (2021) shows that the estimate
of the $Q$-function upper bounds the optimal one.

######  Lemma A.8.

(Kong et al. 2021) With probability at least $1-\delta/2$ we have that for all
$(k,h)\in[K]\times[H]$ and all $(s,a)\in{\mathcal{S}}\times{\mathcal{A}}$

$\displaystyle Q^{*}_{h}(s,a)\leq
Q^{k}_{h}(s,a)\leq\bar{f}_{h}^{k}(s,a)+2b_{h}^{k}(s,a)$

where
$\bar{f}_{h}^{k}(\cdot,\cdot)=\sum_{s^{\prime}\in{\mathcal{S}}}P_{h}(s^{\prime}|\cdot,\cdot)V_{h+1}^{k}(s^{\prime})+r_{h}(\cdot,\cdot)$.

We now present a lemma that bounds the number of rounds that the suboptimilaty
gap falls in some interval. It is inspired by Lemma 6.2 (He et al. 2021).

######  Lemma A.9.

If we pick

$\beta=CH^{2}\log(T{\mathcal{N}}({\mathcal{F}},\delta/T^{2})/\delta)\dim_{E}({\mathcal{F}},1/T)\log^{2}T\log\left({\mathcal{C}}({\mathcal{S}}\times{\mathcal{A}},\delta/T^{2})T/\delta)\right),$

then there exists a constant $\widetilde{C}$ such that for all
$h\in[H],n\in[N]$ with probability at least $1-2K\delta$, we have that

$\displaystyle\sum_{k=1}^{K}\mathbbm{1}[V^{*}_{h}(s_{h}^{k})-Q_{h}^{\pi_{k}}(s_{h}^{k},a_{h}^{k})\geq
2^{n}{\textnormal{gap}}_{\min}]\leq\frac{\widetilde{C}H^{4}\dim^{2}_{E}({\mathcal{F}},1/T)\log^{2}T\log(T{\mathcal{N}}({\mathcal{F}},\delta/T^{2})/\delta)\log({\mathcal{C}}({\mathcal{S}}\times{\mathcal{A}},\delta/T^{2})T/\delta)}{4^{n}{\textnormal{gap}}_{\min}^{2}}.$

###### Proof.

We keep $h$ fixed.

We denote by $K^{\prime}$ the set of episodes where the gap at step $h$ is at
least $2^{n}$, i.e.

$\displaystyle
K^{\prime}=\left\\{k\in[K]:V^{*}_{h}(s_{h}^{k})-Q_{h}^{\pi_{k}}(s_{h}^{k},a_{h}^{k})\geq
2^{n}{\textnormal{gap}}_{\min}\right\\}.$

The goal is to bound the quantity
$\sum_{i=1}^{|K^{\prime}|}\left(Q_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})-Q_{h}^{\pi_{k_{i}}}(s_{h}^{k_{i}},a_{h}^{k_{i}})\right)$
from below and above with functions $f_{1}(|K^{\prime}|),f_{2}(|K^{\prime}|)$
and then use the fact that $f_{1}(|K^{\prime}|)\leq f_{2}(|K^{\prime}|)$ to
derive an upper bound on $|K^{\prime}|$.

For the lower bound, we have that

$\displaystyle\sum_{i=1}^{|K^{\prime}|}\left(Q_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})-Q_{h}^{\pi_{k_{i}}}(s_{h}^{k_{i}},a_{h}^{k_{i}})\right)$
$\displaystyle\geq\sum_{i=1}^{|K^{\prime}|}\left(Q_{h}^{k_{i}}(s_{h}^{k_{i}},\pi_{h}^{*}(s_{h}^{k_{i}}))-Q_{h}^{\pi_{k_{i}}}(s_{h}^{k_{i}},a_{h}^{k_{i}})\right)$
$\displaystyle\geq\sum_{i=1}^{|K^{\prime}|}\left(Q_{h}^{*}(s_{h}^{k_{i}},\pi_{h}^{*}(s_{h}^{k_{i}}))-Q_{h}^{\pi_{k_{i}}}(s_{h}^{k_{i}},a_{h}^{k_{i}})\right)$
$\displaystyle=\sum_{i=1}^{|K^{\prime}|}\left(V_{h}^{*}(s_{h}^{k_{i}})-Q_{h}^{\pi_{k_{i}}}(s_{h}^{k_{i}},a_{h}^{k_{i}})\right)\geq
2^{n}{\textnormal{gap}}_{\min}|K^{\prime}|,$

where the first inequality holds by the definition of the policy
$\pi_{k_{i}}$, the second one follows because $Q^{k_{i}}_{h}(\cdot,\cdot)$ is
an optimistic estimate of $Q^{*}_{h}(\cdot,\cdot)$ which happens with
probability at least $1-\delta/2$ (see Lemma A.8) and the third one by the
definition of $k_{i}$.

We get the upper bound on this quantity in the following way. For any
$h^{\prime}\in[H]$ we have

$\displaystyle
Q_{h^{\prime}}^{k}(s_{h^{\prime}}^{k},a_{h^{\prime}}^{k})-Q_{h^{\prime}}^{\pi_{k}}(s_{h^{\prime}}^{k},a_{h^{\prime}}^{k})$
$\displaystyle\leq\sum_{s^{\prime}\in{\mathcal{S}}}P_{h^{\prime}}(s^{\prime}|s_{h^{\prime}}^{k},a_{h^{\prime}}^{k})V^{k}_{h^{\prime}+1}(s^{\prime})+r_{h^{\prime}}(s_{h^{\prime}}^{k},a_{h^{\prime}}^{k})+2b_{h^{\prime}}^{k}(s_{h^{\prime}}^{k},a_{h^{\prime}}^{k})-Q_{h^{\prime}}^{\pi_{k}}(s_{h^{\prime}}^{k},a_{h^{\prime}}^{k})$
$\displaystyle=\left\langle
P_{h^{\prime}}(\cdot|s_{h^{\prime}}^{k},a_{h^{\prime}}^{k}),V_{h^{\prime}+1}^{k}-V_{h^{\prime}+1}^{\pi_{k}}\right\rangle+2b_{h^{\prime}}^{k}(s_{h^{\prime}}^{k},a_{h^{\prime}}^{k})$
$\displaystyle=V_{h^{\prime}+1}^{k}(s_{h^{\prime}+1}^{k})-V_{h^{\prime}+1}^{\pi_{k}}(s_{h^{\prime}+1}^{k})+\epsilon_{h^{\prime}}^{k}+2b_{h^{\prime}}^{k}(s_{h^{\prime}}^{k},a_{h^{\prime}}^{k})$
$\displaystyle=Q_{h^{\prime}+1}^{k}(s_{h^{\prime}+1}^{k},a_{h^{\prime}+1}^{k})-Q_{h^{\prime}+1}^{\pi_{k}}(s_{h^{\prime}+1}^{k},a_{h^{\prime}+1}^{k})+\epsilon_{h^{\prime}}^{k}+2b_{h^{\prime}}^{k}(s_{h^{\prime}}^{k},a_{h^{\prime}}^{k})$

where we define $\epsilon_{h^{\prime}}^{k}=\left\langle
P_{h^{\prime}}(\cdot|s_{h^{\prime}}^{k},a_{h^{\prime}}^{k}),V_{h^{\prime}+1}^{k}-V_{h^{\prime}+1}^{\pi_{k}}\right\rangle-(V_{h^{\prime}+1}^{k}(s_{h^{\prime}+1}^{k})-V_{h^{\prime}+1}^{\pi_{k}}(s_{h^{\prime}+1}^{k}))$
and the inequality follows from Lemma A.8.

We now take the summation over all $k\in|K^{\prime}|,h\leq h^{\prime}\leq H$
and we get

$\displaystyle\sum_{i=1}^{|K^{\prime}|}\left(Q_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})-Q_{h}^{\pi_{k_{i}}}(s_{h}^{k_{i}},a_{h}^{k_{i}})\right)\leq\sum_{i=1}^{|K^{\prime}|}\sum_{h^{\prime}=h}^{H}\epsilon_{h^{\prime}}^{k_{i}}+\sum_{i=1}^{|K^{\prime}|}\sum_{h^{\prime}=h}^{H}b_{h^{\prime}}^{k_{i}}(s_{h^{\prime}}^{k_{i}},a_{h^{\prime}}^{k_{i}}).$

We will bound each of the two terms on the RHS separately.

For the first term, we notice that $x_{j}=\left\langle
P_{j}(\cdot|s_{j}^{k_{i}},a_{j}^{k_{i}}),V_{j+1}^{k_{i}}-V_{j+1}^{\pi_{k_{i}}}\right\rangle-(V_{j+1}^{k_{i}}(s_{j+1}^{k_{i}})-V_{j+1}^{\pi_{k_{i}}}(s_{j+1}^{k_{i}}))$
forms a martingale difference sequence with zero mean and $|x_{j}|\leq 2H$.
Hence, we can use Lemma A.7 and that for each $k\in K^{\prime}$, with
probability at least $1-\delta$ we have that

$\displaystyle\sum_{i=1}^{k}\sum_{j=1}^{H}\left(\left\langle
P_{j}(\cdot|s_{j}^{k_{i}},a_{j}^{k_{i}}),V_{j+1}^{k_{i}}-V_{j+1}^{\pi_{k_{i}}}\right\rangle-\left(V_{j+1}^{k_{i}}(s_{j+1}^{k_{i}})-V_{j+1}^{\pi_{k_{i}}}(s_{j+1}^{k_{i}})\right)\right)\leq\sqrt{8kH^{3}\log(1/\delta)}.$

If we take the union bound over all $k\in[K]$ we have that with probability at
least $1-|K^{\prime}|\delta$

$\displaystyle\sum_{i=1}^{|K^{\prime}|}\sum_{h^{\prime}=h}^{H}\epsilon_{h^{\prime}}^{k_{i}}\leq\sqrt{8|K^{\prime}|H^{3}\log(1/\delta)}.$

We now focus on the second term. Using Lemma A.6 we get that

$\displaystyle\sum_{i=1}^{|K^{\prime}|}\sum_{h^{\prime}=h}^{H}b_{h^{\prime}}^{k_{i}}(s_{h^{\prime}}^{k_{i}},a_{h^{\prime}}^{k_{i}})\leq
H+H(H+1)\dim_{E}({\mathcal{F}},1/T)+CH\sqrt{\textnormal{dim}_{E}({\mathcal{F}},1/T)|K^{\prime}|\beta}$

and this happens with probability at least $1-\delta/32$. Hence, combining the
upper and lower bound of

$\sum_{i=1}^{|K^{\prime}|}\left(Q_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})-Q_{h}^{\pi_{k_{i}}}(s_{h}^{k_{i}},a_{h}^{k_{i}})\right)$

we get that

$\displaystyle
2^{n}{\textnormal{gap}}_{\min}|K^{\prime}|\leq\sqrt{8|K^{\prime}|H^{3}\log(1/\delta)}+H+H(H+1)\dim_{E}({\mathcal{F}},1/T)+CH\sqrt{\textnormal{dim}_{E}({\mathcal{F}},1/T)|K^{\prime}|\beta}.$

Solving for $|K^{\prime}|$ gives us that

$\displaystyle|K^{\prime}|\leq\frac{\widetilde{C}H^{4}\dim^{2}_{E}({\mathcal{F}},1/T)\log^{2}T\log(T{\mathcal{N}}({\mathcal{F}},\delta/T^{2})/\delta)\log({\mathcal{C}}({\mathcal{S}}\times{\mathcal{A}},\delta/T^{2})T/\delta)}{4^{n}{\textnormal{gap}}_{\min}^{2}}.$

∎

We are now ready to prove Lemma A.2.

Proof of Lemma A.2: Throughout this proof we condition on the event described
in Lemma A.9 which happens with probability at least $1-2K\delta$. Since
${\textnormal{gap}}_{\min}>0$ whenever we do not take the optimal action, we
have that either $V_{h}^{*}(s_{k})-Q_{h}^{*}(s_{h}^{k},a_{h}^{k})=0$ or
$V_{h}^{*}(s_{k})-Q_{h}^{*}(s_{h}^{k},a_{h}^{k})\geq{\textnormal{gap}}_{\min}$.
Our approach is to divide the interval $[0,H]$ into
$N=\lceil\log(H/{\textnormal{gap}}_{\min})\rceil$ intervals and count the
number of $V_{h}^{*}(s_{k})-Q_{h}^{*}(s_{h}^{k},a_{h}^{k})$ that fall into
each interval. Notice that for every
$V_{h}^{*}(s_{k})-Q_{h}^{*}(s_{h}^{k},a_{h}^{k})$ that falls into interval $i$
we can get an upper bound of
$V_{h}^{*}(s_{k})-Q_{h}^{*}(s_{h}^{k},a_{h}^{k})\leq
2^{i}{\textnormal{gap}}_{\min}$ and this upper bound is essentially tight.
Hence, we have that

$\displaystyle\sum_{k=1}^{K}\left(V_{h}^{*}(s_{h}^{k})-Q_{h}^{*}(s_{h}^{k},a_{h}^{k})\right)$
$\displaystyle\leq\sum_{i=1}^{N}\sum_{k=1}^{K}\mathbbm{1}\left[2^{i}{\textnormal{gap}}_{\min}\geq
V_{h}^{*}(s_{h}^{k})-Q_{h}^{*}(s_{h}^{k},a_{h}^{k})\geq
2^{i-1}{\textnormal{gap}}_{\min}\right]\cdot 2^{i}{\textnormal{gap}}_{\min}$
$\displaystyle\leq\sum_{i=1}^{N}\sum_{k=1}^{K}\mathbbm{1}\left[V_{h}^{*}(s_{h}^{k})-Q_{h}^{*}(s_{h}^{k},a_{h}^{k})\geq
2^{i-1}{\textnormal{gap}}_{\min}\right]\cdot 2^{i}{\textnormal{gap}}_{\min}$
$\displaystyle\leq\sum_{i=1}^{N}\frac{\widetilde{C}H^{4}\dim^{2}_{E}({\mathcal{F}},1/T)\log^{2}T\log(T{\mathcal{N}}({\mathcal{F}},\delta/T^{2})/\delta)\log({\mathcal{C}}({\mathcal{S}}\times{\mathcal{A}},\delta/T^{2})T/\delta)}{4^{i-1}{\textnormal{gap}}_{\min}^{2}}\cdot
2^{i}{\textnormal{gap}}_{\min}$
$\displaystyle=\sum_{i=1}^{N}\frac{\widetilde{C}H^{4}\dim^{2}_{E}({\mathcal{F}},1/T)\log^{2}T\log(T{\mathcal{N}}({\mathcal{F}},\delta/T^{2})/\delta)\log({\mathcal{C}}({\mathcal{S}}\times{\mathcal{A}},\delta/T^{2})T/\delta)}{2^{i}{\textnormal{gap}}_{\min}}$
$\displaystyle\leq\frac{CH^{4}\dim^{2}_{E}({\mathcal{F}},1/T)\log^{2}T\log(T{\mathcal{N}}({\mathcal{F}},\delta/T^{2})/\delta)\log({\mathcal{C}}({\mathcal{S}}\times{\mathcal{A}},\delta/T^{2})T/\delta)}{{\textnormal{gap}}_{\min}}$

where the first inequality holds by the definition of the intervals, the
second due to the properties of the indicator function, the third because of
Lemma A.9 and in the last two steps we just manipulate the constants. $\Box$

##  Appendix B Proof of Theorem 3.3

In this section, our main goal is to prove Theorem 3.3. We work with
Assumption 2.4. We follow the same regret decomposition as in Appendix A.

We first present a lemma that is crucial in bounding the regret of the
algorithm.

######  Lemma B.1.

If we pick

$\beta=4H^{2}\log(2{\mathcal{N}}({\mathcal{F}},1/T)/\delta)+4/H\left(C+\sqrt{H^{2}/4\log(4(K(K+1)/\delta)})\right),$

for come constant C and for $h\in[H]$, then we have that with probability at
least $1-(K+3)\delta$

$\displaystyle\sum_{k=1}^{K}\left(V_{h}^{*}(s_{h}^{k})-Q_{h}^{*}(s_{h}^{k},a_{h}^{k})\right)\leq\frac{CH^{4}\log(T{\mathcal{N}}({\mathcal{F}},1/T)/\delta)\dim^{2}_{E}({\mathcal{F}},1/T)}{{\textnormal{gap}}_{\min}}.$

We are now ready to state the regret bound of our algorithm.

######  Lemma B.2.

There exists a constant $C$ and proper values of the parameter $\beta$ of
Algorithm 1 such that with probability at least $1-\lceil\log T\rceil
e^{-\tau}-H(K+3)\delta$ the regret of the algorithm is bounded by

$\displaystyle\textnormal{Regret}(K)\leq\frac{CH^{5}\log(T{\mathcal{N}}({\mathcal{F}},1/T)/\delta)\dim^{2}_{E}({\mathcal{F}},1/T)}{{\textnormal{gap}}_{\min}}+\frac{16H^{2}\tau}{3}+2.$

The value of the parameter is

$\beta=4H^{2}\log(2{\mathcal{N}}({\mathcal{F}},1/T)/\delta)+4/H\left(C+\sqrt{H^{2}/4\log(4(K(K+1)/\delta)})\right).$

where
${\mathcal{N}}({\mathcal{F}},1/T)=\arg\max_{h\in[H]}{\mathcal{N}}({\mathcal{F}}_{h},1/T)$.

In particular, the dependence of the regret in the time horizon $T$ is
logarithmic.

###### Proof.

Throughout the proof, we condition on the events described in Lemma A.1, B.1
which happen with probability at least $1-\lceil\log T\rceil
e^{-\tau}-H(K+3)\delta$.

From Lemma A.1 we have that

$\displaystyle\text{Regret}(K)\leq
2\sum_{k=1}^{K}\sum_{h=1}^{H}{\textnormal{gap}}_{h}(s_{h}^{k},a_{h}^{k})+\frac{16H^{2}\tau}{3}+2.$

We can bound the first term on the RHS using Lemma B.1 as follows

$\displaystyle
2\sum_{k=1}^{K}\sum_{h=1}^{H}{\textnormal{gap}}_{h}(s_{h}^{k},a_{h}^{k})=2\sum_{k=1}^{K}\sum_{h=1}^{H}\left(V_{h}^{*}(s_{h}^{k})-Q_{h}^{*}(s_{h}^{k},a_{h}^{k})\right)\leq\frac{2CH^{5}\log(T{\mathcal{N}}({\mathcal{F}},1/T)/\delta)\dim^{2}_{E}({\mathcal{F}},1/T)}{{\textnormal{gap}}_{\min}}.$

This gives us the result.

∎

The only thing that we need to do now is to bound the number of rounds that we
update our policy. Since we are using exactly the same sensitivity score and
update probability as in Kong et al. (2021), this follows from their result.

######  Lemma B.3.

(Kong et al. 2021) With probability at least $1-\delta/32$ for any fixed
$h\in[H]$ we have that the sub-sampled dataset $\widehat{Z}_{h}^{k},k\in[K]$
changes at most

$S_{\max}=C\cdot\log(T{\mathcal{N}}(F_{h},\sqrt{\delta/(64T^{3})})/\delta)\dim_{E}({\mathcal{F}}_{h},1/T)\log^{2}T$

times.

We are now ready to prove Theorem 3.3.

Proof of Theorem 3.3:

=The proof of this theorem follows by combining Lemma B.2 and taking a union
on the result of Lemma B.3 and setting the error probability accordingly.
$\Box$

###  B.1 Supporting Lemmas: Theorem 3.3

In this section our goal is to prove the supporting lemmas of Theorem 3.3.

Recall that our approach is to modify the algorithm in Kong et al. (2021) to
work in this setting and use a similar analysis as in Appendix A. Unlike
Appendix A where we approximate the optimal Q-function, here we try to
estimate the true transition kernel. Let
${\mathcal{Z}}_{h}^{k}=\\{\left(s_{h}^{\tau},a_{h}^{\tau},V_{h+1}^{\tau}(\cdot)\right)\\}_{\tau\in[k-1]}$
be the dataset up to episode $k$ and $\widehat{{\mathcal{Z}}}_{h}^{k}$ the
sub-sampled dataset. In each episode $k$, we update our policy whenever we add
an element in the dataset for some $h\in[H]$. Recall that whenever we perform
an update our policy becomes:

$\displaystyle Q_{H+1}^{k}(s,a)=0,$ $\displaystyle V_{H+1}^{k}(s)=0,$
$\displaystyle
Q_{h}^{k}(s,a)=\min\\{r_{h}(s,a)+\langle\widehat{P}^{k}_{h}(\cdot|s,a),V^{k}_{h+1}\rangle+b_{h}^{k}(s,a),H\\},$
$\displaystyle V_{h}^{k}(s)=\max_{a\in{\mathcal{A}}}Q_{h}^{k}(s,a)$

for some $\widehat{P}_{h}^{k},b_{h}^{k}(\cdot,\cdot)$ that we will define
shortly. We get the policy $\pi^{k}_{h}(s)$ by picking greedily the action
that maximizes the estimate $Q_{h}^{k}(s,a)$.

The least-squares estimate of the model is

$\displaystyle\widehat{P}_{h}^{k+1}=\arg\min_{P\in{\cal
P}_{h}}\sum_{k^{\prime}=1}^{k}\left(\langle
P(\cdot|s_{h}^{k^{\prime}},a_{h}^{k^{\prime}}),V_{h+1}^{k^{\prime}}\rangle-
y_{h}^{k^{\prime}}\right)^{2},y_{h}^{k^{\prime}}=V_{h+1}^{k^{\prime}}(s_{h+1}^{k^{\prime}}).$

Recall the definition of the function class that we use in the derivation of
our results.

######  Definition B.4.

Let ${\cal V}$ be the set all measurable functions that are bounded by $H$. We
now let $f:{\mathcal{S}}\times{\mathcal{A}}\times{\cal
V}\rightarrow\mathbb{R}$ and define the following set:

$\displaystyle{\mathcal{F}}_{h}=\left\\{f:\exists P_{h}\in{\cal P}_{h}\text{
so that
}f(s,a,V)=\int_{\mathcal{S}}P_{h}(s^{\prime}|s,a)V(s^{\prime})ds^{\prime},\forall(s,a,V)\in{\mathcal{S}}\times{\mathcal{A}}\times{\cal
V}\right\\}.$ (1)

Recall that in this setting the norm of a function with respect to a dataset
${\mathcal{Z}}$ is

$||f||_{{\mathcal{Z}}}=\sqrt{\sum_{z=(s_{z},a_{z},V_{z}(\cdot))\in{\mathcal{Z}}}\left(f(s_{z},a_{z},V_{z}(\cdot)\right)^{2}}.$

Recall also that the bonus function is

$\displaystyle
b_{h}^{k}(s,a)=\sup_{f_{1},f_{2}\in{\mathcal{F}}_{h}:\min\\{||f_{1}-f_{2}||_{\widehat{{\mathcal{Z}}}_{h}^{k}},T(H+1)^{2}\\}\leq\beta}|f_{1}(s,a,V_{h+1}^{k}(\cdot))-f_{2}(s,a,V_{h+1}^{k}(\cdot))|.$

The parameter $\beta$ will be defined later in a way that will ensure
optimism.

First, we need to show that at for every $k\in[K],h\in[H]$, the sub-sampled
dataset approximates the original one. Our approach is inspired by (Kong et
al. 2021).

We define the following quantities

$\displaystyle\underline{{\mathcal{C}}}_{h}^{k}(\alpha)$
$\displaystyle=\left\\{(f_{1},f_{2})\in{\mathcal{F}}_{h}\times{\mathcal{F}}_{h}:||f_{1}-f_{2}||^{2}_{{\mathcal{Z}}_{h}^{k}}\leq\alpha/100\right\\}$
$\displaystyle\widehat{{\mathcal{C}}}_{h}^{k}(\alpha)$
$\displaystyle=\left\\{(f_{1},f_{2})\in{\mathcal{F}}_{h}\times{\mathcal{F}}_{h}:\min\\{||f_{1}-f_{2}||^{2}_{\widehat{{\mathcal{Z}}}_{h}^{k}},T(H+1)^{2}\\}\leq\alpha\right\\}$
$\displaystyle\overline{{\mathcal{C}}}_{h}^{k}(\alpha)$
$\displaystyle=\left\\{(f_{1},f_{2})\in{\mathcal{F}}_{h}\times{\mathcal{F}}_{h}:||f_{1}-f_{2}||^{2}_{{\mathcal{Z}}_{h}^{k}}\leq
100\alpha\right\\}.$

We also let

$\displaystyle\underline{b}_{h}^{k}(s,a)=\sup_{f_{1},f_{2}\in\underline{{\mathcal{C}}}_{h}^{k}(\beta)}|f_{1}(s,a,V_{h+1}^{k}(\cdot))-f_{2}(s,a,V_{h+1}^{k}(\cdot))|$
$\displaystyle\overline{b}_{h}^{k}(s,a)=\sup_{f_{1},f_{2}\in\overline{{\mathcal{C}}}_{h}^{k}(\beta)}|f_{1}(s,a,V_{h+1}^{k}(\cdot))-f_{2}(s,a,V_{h+1}^{k}(\cdot))|.$

Our goal is to show that
$\underline{{\mathcal{C}}}_{h}^{k}(\alpha)\subseteq\widehat{{\mathcal{C}}}_{h}^{k}(\alpha)\subseteq\overline{{\mathcal{C}}}_{h}^{k}(\alpha)$
with high probability. Let ${\cal E}_{h}^{k}(\alpha)$ denote the event that
this holds. We also denote by ${\cal E}_{h}^{k}=\cap_{n=0}^{\infty}{\cal
E}_{h}^{k}(100^{n}\beta)$. This event will show us that
$\widehat{{\mathcal{Z}}}_{h}^{k}$ is a good approximation to
${\mathcal{Z}}_{h}^{k}$.
Notice that whenever this happens, it holds that
$\underline{b}_{h}^{k}(s,a)\leq b_{h}^{k}(s,a)\leq\overline{b}_{h}^{k}(s,a)$.

The following lemma which is inspired by Kong et al. (2021) establishes that
fact.

######  Lemma B.5.

The probability that all the events ${\cal E}_{h}^{k}$ happen satisfies

$\displaystyle\Pr\left(\bigcap_{k=1}^{K}\bigcap_{h=1}^{H}{\cal
E}_{h}^{k}\right)\geq 1-\delta.$

To prove Lemma B.5 we need the following concentration inequality proved in
Freedman (1975).

######  Lemma B.6.

Let $\\{Y_{i}\\}_{i\in\mathbb{N}}$ be a real-valued martingale with difference
sequence $\\{X_{i}\\}_{i\in\mathbb{N}}$. Let $R$ be a uniform bound on
$X_{i}$. Fix some $n\in\mathbb{N}$ and let $\sigma^{2}$ be a number such that

$\displaystyle\sum_{i=1}^{n}\operatorname*{\mathbb{E}}[X_{i}^{2}|Y_{0},\ldots,Y_{i-1}]\leq\sigma^{2}.$

Then, for all $t\geq 0$ we have that

$\displaystyle\Pr(|Y_{n}-Y_{0}|\geq t)\leq
2\exp{\left\\{-\frac{t^{2}/2}{\sigma^{2}+Rt/3}\right\\}}.$

Moreover, we need a bound on the number of elements that are in the sub-
sampled dataset. This is established in Kong et al. (2021).

######  Lemma B.7.

(Kong et al. 2021) We have that with probability at least $1-\delta/(64T)$, we
have $|\widehat{{\mathcal{Z}}}_{h}^{k}|\leq 64T^{3}/\delta$ for all
$\delta>0$.

The subsequent lemma shows that, indeed, whenever ${\cal E}_{h}^{k}$ happens
the sub-sampled dataset is a good approximation of the original one. It was
proved in (Kong et al. 2021).

######  Lemma B.8.

(Kong et al. 2021) Whenever the event ${\cal E}_{h}^{k}$ happens, it holds
that

$\displaystyle\frac{1}{10000}||f_{1}-f_{2}||^{2}_{{\mathcal{Z}}_{h}^{k}}\leq\min\\{||f_{1}-f_{2}||^{2}_{\widehat{{\mathcal{Z}}}_{h}^{k}},T(H+1)^{2}\\}\leq
10000||f_{1}-f_{2}||^{2}_{{\mathcal{Z}}_{h}^{k}},\textnormal{ if
}||f_{1}-f_{2}||^{2}_{{\mathcal{Z}}_{h}^{k}}>100\beta$

and

$\displaystyle\min\\{||f_{1}-f_{2}||^{2}_{\widehat{{\mathcal{Z}}}_{h}^{k}},T(H+1)^{2}\\}\leq
10000\beta,\textnormal{ if }||f_{1}-f_{2}||^{2}_{{\mathcal{Z}}_{h}^{k}}\leq
100\beta.$

To establish our result, we need the following lemma. The proof follows the
approach of Kong et al. (2021). We present it here for completeness.

######  Lemma B.9.

For any $\alpha\in[\beta,T(H+1)^{2}]$, a fixed $h\in[H]$ and $k\in[K]$ we have
the following bound for the probability that all the events $\\{{\cal
E}_{h}^{i}\\}_{i\leq k-1}$ happen and the last one does not happen

$\displaystyle\Pr\left(\left(\bigcap_{i=1}^{k-1}{\cal E}_{h}^{i}\right){\cal
E}_{h}^{k}(\alpha)^{c}\right)\leq\delta/(32T^{2}).$

###### Proof.

Let $C_{1}$ be the quantity the sensitivity in the sampling probability. We
fix some $h\in[H]$ throughout the proof.

We consider a fixed pair of functions $f_{h}^{1},f_{h}^{2}$ in the discretized
set ${\mathcal{C}}({\mathcal{F}}_{h},\sqrt{\delta/(64T^{3})})$ and for $i\geq
2$ we let

$Z_{i}=\max\left\\{||f_{h}^{1}-f_{h}^{2}||^{2}_{{\mathcal{Z}}_{h}^{i}},\min\\{||f_{h}^{1}-f_{h}^{2}||^{2}_{\widehat{{\mathcal{Z}}}_{h}^{i-1}},T(H+1)^{2}\\}\right\\}.$

We also define

$\displaystyle
Y_{i}=\begin{cases}\frac{1}{p_{z_{h}^{i-1}}}(f_{h}^{1}(z_{h}^{i-1})-f_{h}^{2}(z_{h}^{i-1}))^{2}&\text{$z_{h}^{i-1}$
is added to $\widehat{{\mathcal{Z}}}_{h}^{i}$ and $Z_{i}\leq
2000000\alpha$}\\\ 0,&\text{$z_{h}^{i-1}$ is not added to
$\widehat{{\mathcal{Z}}}_{h}^{i}$ and $Z_{i}\leq 2000000\alpha$}\\\
(f_{h}^{1}(z_{h}^{i-1})-f_{h}^{2}(z_{h}^{i-1}))^{2}&\text{otherwise}\end{cases}$

Let $\mathbb{F}_{i}$ be the filtration that $Y_{i}$ is adapted to. Our goal is
to use Freedman’s inequality (i.e. Lemma B.6) for $Y_{i}$. Notice that
$\operatorname*{\mathbb{E}}[Y_{i}|\mathbb{F}_{i}]=(f_{h}^{1}(z_{h}^{i-1})-f_{h}^{2}(z_{h}^{i-1}))^{2}$.
Now we focus on the variance of $Y_{i}$. Notice that if $p_{z_{h}^{i-1}}=1$ or
$Z_{i}>2000000\alpha$ then $Y_{i}$ is deterministic so
$Y_{i}-\operatorname*{\mathbb{E}}[Y_{i}|\mathbb{F}_{i-1}]=\text{Var}[Y_{i}-\operatorname*{\mathbb{E}}[Y_{i}|\mathbb{F}_{i-1}]]=0$.
For the other case, recall that

$p_{z_{h}^{i}}=\min\\{1,C^{\prime}\cdot\text{sensitivity}_{\widehat{{\mathcal{Z}}}_{h}^{i-1},{\mathcal{F}}_{h}}(z_{h}^{i})\cdot\log(T{\mathcal{N}}({\mathcal{F}},\sqrt{\delta/64T^{3}})/\delta)\\}=\min\\{1,C_{1}\cdot\text{sensitivity}_{\widehat{{\mathcal{Z}}}_{h}^{i-1},{\mathcal{F}}_{h}}(z_{h}^{i})\\}$

and

$\displaystyle\text{sensitivity}_{{\mathcal{Z}},{\mathcal{F}}}(z)=\min\left\\{\sup_{f_{1},f_{2}\in{\mathcal{F}}}\frac{(f_{1}(z)-f_{2}(z))^{2}}{\min\\{||f_{1}-f_{2}||_{\mathcal{{\mathcal{Z}}}},T(H+1)^{2}\\}+\beta},1\right\\}$

Since $p_{z_{h}^{i-1}}<1\implies
C_{1}\cdot\text{sensitivity}_{\widehat{{\mathcal{Z}}}^{i-1}_{h},{\mathcal{F}}_{h}}(z_{h}^{i})<1$.
We consider two cases. If $Y_{i}\neq 0$ we can see that
$Y_{i}\geq\operatorname*{\mathbb{E}}[Y_{i}|\mathbb{F}_{i}]$ so
$|Y_{i}-\operatorname*{\mathbb{E}}[Y_{i}]|\leq Y_{i}$. Moreover,

$\displaystyle Y_{i}$
$\displaystyle\leq\frac{(f_{h}^{1}(z_{h}^{i-1})-f_{h}^{2}(z_{h}^{i-1}))^{2}}{p_{z_{h}^{i-1}}}$
$\displaystyle\leq\frac{(f_{h}^{1}(z_{h}^{i-1})-f_{h}^{2}(z_{h}^{i-1}))^{2}}{C_{1}\sup_{f_{1},f_{2}\in{\mathcal{F}}_{h}}\frac{(f_{1}(z_{h}^{i-1})-f_{2}(z_{h}^{i-1}))^{2}}{\min\\{||f_{1}-f_{2}||_{\mathcal{\widehat{{\mathcal{Z}}}}_{h}^{i-1}},T(H+1)^{2}\\}+\beta}}$
$\displaystyle\leq\frac{(f_{h}^{1}(z_{h}^{i-1})-f_{h}^{2}(z_{h}^{i-1}))^{2}\min\\{||f_{1}-f_{2}||_{\mathcal{\widehat{{\mathcal{Z}}}}_{h}^{i-1}},T(H+1)^{2}\\}+\beta\\}}{C_{1}(f_{h}^{1}(z_{h}^{i-1})-f_{h}^{2}(z_{h}^{i-1}))^{2}}$
$\displaystyle=\left(\min\\{||f_{1}-f_{2}||_{\mathcal{\widehat{{\mathcal{Z}}}}_{h}^{i-1}},T(H+1)^{2}\\}+\beta\right)\cdot
1/C_{1}$ $\displaystyle\leq 2000001\alpha/C_{1}<3000000\alpha/C_{1}$

Thus, we see that $|Y_{i}-\operatorname*{\mathbb{E}}[Y_{i}]|\leq
3000000\alpha/C_{1}$. On the other hand, we can see that if $Y_{i}=0$ then
$|\operatorname*{\mathbb{E}}_{i-1}[Y_{i}]-Y_{i}|=(f_{h}^{1}(z_{h}^{i-1})-f_{h}^{2}(z_{h}^{i-1}))^{2}$
and the inequality we derived above still holds.

For the variance, we can see that

$\displaystyle\text{Var}[Y_{i}-\operatorname*{\mathbb{E}}[Y_{i}|\mathbb{F}_{i}]|\mathbb{F}_{i}]$
$\displaystyle=p_{z_{h}}^{i-1}\left(\frac{1}{p_{z_{h}^{i-1}}}(f_{h}^{1}(z_{h}^{i-1})-f_{h}^{2}(z_{h}^{i-1}))^{2}\right)^{2}+(1-p_{z_{h}}^{i-1})\cdot
0$
$\displaystyle\leq\frac{1}{p_{z_{h}^{i-1}}}(f_{h}^{1}(z_{h}^{i-1})-f_{h}^{2}(z_{h}^{i-1}))^{4}$
$\displaystyle\leq
3000000\alpha\left(f_{h}^{1}(z_{h}^{i-1})-f_{h}^{2}(z_{h}^{i-1})\right)^{2}/C_{1}$

where the first equality follows from the definition, the first inequality is
trivial and the third one from the inequality we derived above. Let
$k^{\prime}$ be the maximum number $\leq k$ such that $Z_{k^{\prime}}\leq
2000000\alpha$. Summing up the above inequalities for $i=2,\ldots,k$ we get

$\displaystyle\sum_{i=2}^{k}\text{Var}[Y_{i}-\operatorname*{\mathbb{E}}[Y_{i}|\mathbb{F}_{i}]|\mathbb{F}_{i}]$
$\displaystyle=\sum_{i=2}^{k^{\prime}}\text{Var}[Y_{i}-\operatorname*{\mathbb{E}}[Y_{i}|\mathbb{F}_{i}]|\mathbb{F}_{i}]$
$\displaystyle\leq\frac{3000000\alpha}{C_{1}}\sum_{i=2}^{k^{\prime}}(f_{h}^{1}(z_{h}^{i-1})-f_{h}^{2}(z_{h}^{i-1}))^{2}$
$\displaystyle\leq\frac{3000000\alpha\cdot 2000000\alpha}{C_{1}}$
$\displaystyle\leq\frac{(3000000\alpha)^{2}}{C_{1}}$

where the the first equality follows from the fact that for $i>k^{\prime}$ the
random variable is deterministic, the first inequality follows by the
summation of the previous one and the second one by the fact that
$\sum_{i=2}^{k^{\prime}}(f_{h}^{1}(z_{h}^{i-1})-f_{h}^{2}(z_{h}^{i-1}))^{2}\leq||f_{h}^{1}-f_{h}^{2}||_{{\mathcal{Z}}_{h}^{k^{\prime}}}\leq
Z_{k^{\prime}}$.

We are now ready to use Freedman’s inequality (Lemma B.6) with
$R=\frac{3000000\alpha}{C_{1}},\sigma^{2}=\frac{(3000000\alpha)^{2}}{C_{1}}$.
We get

$\displaystyle\Pr\left(\left|\sum_{i=1}^{k}(Y_{i}-\operatorname*{\mathbb{E}}[Y_{i}|\mathbb{F}_{i}])\right|\geq\alpha/100\right)$
$\displaystyle=\Pr\left(\left|\sum_{i=1}^{k^{\prime}}(Y_{i}-\operatorname*{\mathbb{E}}[Y_{i}|\mathbb{F}_{i}])\right|\geq\alpha/100\right)$
$\displaystyle\leq
2\exp\left\\{-\frac{(\alpha/100)^{2}/2}{(3000000\alpha)^{2}/C_{1}+\alpha^{2}3000000/300C_{1}}\right\\}$
$\displaystyle=2\exp\left\\{-\frac{C_{1}}{20000(3000000+10000)}\right\\}$
$\displaystyle=2\exp\left\\{-\frac{C\log(T{\mathcal{N}}({\mathcal{F}}_{h},\sqrt{\delta/64T^{3}})/\delta)}{20000(3000000+10000)}\right\\}$
$\displaystyle=2\exp\left\\{-\frac{C(\log((T{\mathcal{N}}({\mathcal{F}}_{h},\sqrt{\delta/64T^{3}})/\delta)^{2}))}{40000(3000000+10000)}\right\\}$
$\displaystyle\leq(\delta/64T^{2})/({\mathcal{N}}({\mathcal{F}}_{h},\sqrt{\delta/64T^{3}}))^{2}$

for some choice of $C$. Now we can take a union bound over all the functions
in the discretized set and conclude that with probability at least
$1-\delta/(64T^{2})$ we have that

$\displaystyle\left|\sum_{i=1}^{k}(Y_{i}-\operatorname*{\mathbb{E}}[Y_{i}|\mathbb{F}_{i}])\right|\leq\alpha/100$

for all pairs of functions in this set. We condition on this event and on the
event in Lemma B.7. We first show that when this event happens, we have that
$\underline{{\mathcal{C}}}_{h}^{k}(\alpha)\subseteq\widehat{{\mathcal{C}}}_{h}^{k}(\alpha)$.
Consider $f_{1},f_{2}\in\underline{{\mathcal{C}}}_{h}^{k}(\alpha)$. We know
that there exist
$f_{1}^{\prime},f_{2}^{\prime}\in{\mathcal{C}}({\mathcal{F}},\sqrt{\delta/(64T^{3})})\times{\mathcal{C}}({\mathcal{F}},\sqrt{\delta/(64T^{3})})$
with
$||f_{1}-f_{1}^{\prime}||_{\infty},||f_{2}-f_{2}^{\prime}||_{\infty}\leq\sqrt{\delta/64T^{3}}$.
Hence, we get that

$\displaystyle||f_{1}^{\prime}-f_{2}^{\prime}||_{{\mathcal{Z}}_{h}^{k}}^{2}$
$\displaystyle\leq\left(||f_{1}-f_{1}^{\prime}||_{{\mathcal{Z}}_{h}^{k}}+||f_{2}-f_{2}^{\prime}||_{{\mathcal{Z}}_{h}^{k}}+||f_{1}-f_{2}||_{{\mathcal{Z}}_{h}^{k}}\right)^{2}$
$\displaystyle\leq\left(||f_{1}-f_{2}||_{{\mathcal{Z}}_{h}^{k}}+2\sqrt{\delta|{\mathcal{Z}}_{h}^{k}|/(64T^{3})}\right)^{2}\leq\alpha/50$

We now consider the $Y_{i}$’s that are generated by
$f_{1}^{\prime},f_{2}^{\prime}$. It holds that
$||f_{1}^{\prime}-f_{2}^{\prime}||^{2}_{{\mathcal{Z}}_{h}^{k}}\leq\alpha/50\implies||f_{1}^{\prime}-f_{2}^{\prime}||^{2}_{{\mathcal{Z}}_{h}^{k-1}}\leq\alpha/50$.
Since the event ${\cal E}_{h}^{k-1}$ happens it follows that
$\min\\{||f_{1}^{\prime}-f_{2}^{\prime}||_{\widehat{{\mathcal{Z}}}_{h}^{k-1}}^{2},T(H+1)^{2}\\}\leq
100(\alpha/50)=2\alpha<2000000\alpha\implies Z_{k}\leq 2000000\alpha$. Thus,
every $Y_{i}$ is exactly
$(f_{1}^{\prime}(z_{h}^{i})-f_{2}^{\prime}(z_{h}^{i}))^{2}$ multiplied by the
number of times $z_{h}^{i}$ is in the sub-sampled dataset. Hence, we get

$\displaystyle||f_{1}^{\prime}-f_{2}^{\prime}||^{2}_{\widehat{{\mathcal{Z}}}_{h}^{k}}=\sum_{i=2}^{k}Y_{i}$
$\displaystyle\leq\sum_{i=2}^{k}\operatorname*{\mathbb{E}}[Y_{i}|\mathbb{F}_{i}]+\alpha/100$
$\displaystyle\leq||f^{\prime}_{1}-f_{2}^{\prime}||_{{\mathcal{Z}}_{h}^{k}}^{2}+\alpha/100\leq
3\alpha/100$

where the first inequality follows from the concentration bound we have
derived and the other two simply from the definitions of these quantities.

We now bound $||f_{1}-f_{2}||^{2}_{\widehat{{\mathcal{Z}}}_{h}^{k}}$. We have
that

$\displaystyle||f_{1}-f_{2}||_{\widehat{{\mathcal{Z}}}_{h}^{k}}^{2}$
$\displaystyle\leq\left(||f_{1}^{\prime}-f_{2}^{\prime}||_{\widehat{{\mathcal{Z}}}_{h}^{k}}+||f_{1}-f_{1}^{\prime}||_{\widehat{{\mathcal{Z}}}_{h}^{k}}+||f_{2}-f_{2}^{\prime}||_{\widehat{{\mathcal{Z}}}_{h}^{k}}\right)^{2}$
$\displaystyle\leq(||f_{1}^{\prime}-f_{2}^{\prime}||_{\widehat{{\mathcal{Z}}}_{h}^{k}}+2\sqrt{|\widehat{{\mathcal{Z}}}_{h}^{k}}|\cdot\sqrt{\delta/(64T^{3})})^{2}$
$\displaystyle\leq(||f_{1}^{\prime}-f_{2}^{\prime}||_{\widehat{{\mathcal{Z}}}_{h}^{k}}+2)^{2}\leq(\sqrt{3\alpha/100}+2)^{2}\leq\alpha$

Hence, we have shown that
$\underline{{\mathcal{C}}}_{h}^{k}(\alpha)\subseteq\widehat{{\mathcal{C}}}_{h}^{k}(\alpha)$.
So in this case, the one inequality that define ${\cal E}_{h}^{k}$ holds.

We shift our attention to the second inequality now. We will show the
contrapositive of our claim, i.e. if
$f_{1},f_{2}\notin\overline{C}_{h}^{k}(\alpha)\implies
f_{1},f_{2}\notin\widehat{C}_{h}^{k}(\alpha)$. Let
$f_{1},f_{2}\in{\mathcal{F}}_{h}\times{\mathcal{F}}_{h}$ such that
$||f_{1}-f_{2}||_{{\mathcal{Z}}_{h}^{k}}>100\alpha$. We know that there exist
$f_{1}^{\prime},f_{2}^{\prime}\in{\mathcal{C}}({\mathcal{F}},\sqrt{\delta/(64T^{3})})\times{\mathcal{C}}({\mathcal{F}},\sqrt{\delta/(64T^{3})})$
with
$||f_{1}-f_{1}^{\prime}||_{\infty},||f_{2}-f_{2}^{\prime}||_{\infty}\leq\sqrt{\delta/64T^{3}}$.
Hence, using the triangle inequality we get that

$\displaystyle||f_{1}^{\prime}-f_{2}^{\prime}||_{{\mathcal{Z}}_{h}^{k}}^{2}$
$\displaystyle\geq(||f_{1}-f_{2}||_{{\mathcal{Z}}_{h}^{k}}-||f_{1}-f_{1}^{\prime}||_{{\mathcal{Z}}_{h}^{k}}-||f_{2}-f_{2}^{\prime}||_{{\mathcal{Z}}_{h}^{k}})^{2}$
$\displaystyle\geq(||f_{1}-f_{2}||_{{\mathcal{Z}}_{h}^{k}}-2\sqrt{|{\mathcal{Z}}_{h}^{k}|}\sqrt{\delta/(64T^{3})})^{2}$
$\displaystyle=(\sqrt{100\alpha}-2\sqrt{\delta/(64T^{2})})^{2}>50\alpha$

Again, consider the $Y_{i}$’s that are generated by
$f_{1}^{\prime},f_{2}^{\prime}$. We want to show that
$||f_{1}^{\prime}-f_{2}^{\prime}||_{\widehat{{\mathcal{Z}}}_{h}^{k}}^{2}>40\alpha$.
Assume towards contradiction that
$||f_{1}^{\prime}-f_{2}^{\prime}||_{\widehat{{\mathcal{Z}}}_{h}^{k}}^{2}\leq
40\alpha$. We consider three different cases.

First Case: $||f_{1}^{\prime}-f_{2}^{\prime}||^{2}_{{\mathcal{Z}}_{h}^{k}}\leq
2000000\alpha$. Similarly as before, we have that

$\displaystyle||f_{1}^{\prime}-f_{2}^{\prime}||_{\widehat{{\mathcal{Z}}}_{h}^{k}}^{2}=\sum_{i=2}^{k}Y_{i}$
$\displaystyle\geq\operatorname*{\mathbb{E}}[Y_{i}|\mathbb{F}_{i}]-\alpha/100$
$\displaystyle>50\alpha-\alpha/100>40\alpha$

So we get a contradiction.

Second Case:
$||f_{1}^{\prime}-f_{2}^{\prime}||^{2}_{{\mathcal{Z}}_{h}^{k-1}}>10000\alpha$.
The contradiction comes directly from the fact that ${\cal E}_{h}^{k-1}$
holds, so

$||f_{1}^{\prime}-f_{2}^{\prime}||_{\widehat{{\mathcal{Z}}}_{h}^{k}}^{2}\geq||f_{1}^{\prime}-f_{2}^{\prime}||_{\widehat{{\mathcal{Z}}}_{h}^{k-1}}^{2}>100\alpha$

.

Third Case:
$||f_{1}^{\prime}-f_{2}^{\prime}||^{2}_{{\mathcal{Z}}_{h}^{k-1}}\leq
10000\alpha$ and
$||f_{1}^{\prime}-f_{2}^{\prime}||^{2}_{{\mathcal{Z}}_{h}^{k}}>2000000\alpha$.
We can directly see that for this case
$(f_{1}^{\prime}(z_{h}^{k})-f_{2}^{\prime}(z_{h}^{k}))^{2}\geq 1900000\alpha$.
Since $||f_{1}^{\prime}-f_{2}^{\prime}||^{2}_{{\mathcal{Z}}_{h}^{k-1}}\leq
10000\alpha\implies||f_{1}^{\prime}-f_{2}^{\prime}||^{2}_{\widehat{{\mathcal{Z}}}_{h}^{k-1}}\leq
1000000\alpha$. Thus, since $\alpha\geq\beta$ we can see that the sensitivity
is 1 so the element will be added to the sub-sampled dataset. Hence,
$||f_{1}^{\prime}-f_{2}^{\prime}||_{{\mathcal{Z}}_{h}^{k}}^{2}\geq(f_{1}^{\prime}(z_{h}^{k})-f_{2}^{\prime}(z_{h}^{k}))^{2}>40\alpha$.

Thus, in any case we have that
$||f_{1}^{\prime}-f_{2}^{\prime}||_{\widehat{{\mathcal{Z}}}_{h}^{k}}^{2}>40\alpha>\alpha$,
so we get the result. ∎

We are now ready to prove Lemma B.5.

Proof of Lemma B.5:

We know that for all $k\in[K],k\neq 1,h\in[H]$ it holds that

$\displaystyle\Pr({\cal E}_{h}^{1}{\cal E}_{h}^{2}\ldots{\cal
E}_{h}^{k-1})-\Pr({\cal E}_{h}^{1}{\cal E}_{h}^{2}\ldots{\cal E}_{h}^{k})$
$\displaystyle=\Pr\left({\cal E}_{h}^{1}{\cal E}_{h}^{2}\ldots{\cal
E}_{h}^{k-1}({\cal E}_{h}^{k})^{c}\right)$ $\displaystyle=\Pr\left({\cal
E}_{h}^{1}{\cal E}_{h}^{2}\ldots{\cal
E}_{h}^{k-1}\left(\cap_{n=0}^{\infty}{\cal
E}_{h}^{k}(100^{n}\beta)\right)^{c}\right)$ $\displaystyle=\Pr\left({\cal
E}_{h}^{1}{\cal E}_{h}^{2}\ldots{\cal E}_{h}^{k-1}\cup_{n=0}^{\infty}{\cal
E}_{h}^{k}(100^{n}\beta)^{c}\right)$
$\displaystyle\leq\sum_{n=0}^{\infty}\Pr\left({\cal E}_{h}^{1}{\cal
E}_{h}^{2}\ldots{\cal E}_{h}^{k-1}({\cal E}_{h}^{k}(100^{n}\beta))^{c}\right)$
$\displaystyle=\sum_{n\geq 0,100^{n}\beta\leq T(H+1)^{2}}\Pr\left({\cal
E}_{h}^{1}{\cal E}_{h}^{2}\ldots{\cal E}_{h}^{k-1}({\cal
E}_{h}^{k}(100^{n}\beta))^{c}\right).$

Thus, using Lemma B.9 we see that $\Pr({\cal E}_{h}^{1}{\cal
E}_{h}^{2}\ldots{\cal E}_{h}^{k-1})-\Pr({\cal E}_{h}^{1}{\cal
E}_{h}^{2}\ldots{\cal
E}_{h}^{k})\leq\delta/(32T^{2})(\log(T(H+1)^{2}/\beta)+2)\leq\delta/32T$.

Hence, for any fixed $h\in[H]$ we get

$\displaystyle\Pr\left(\bigcap_{k=1}^{K}{\cal E}_{h}^{k}\right)$
$\displaystyle=1-\sum_{k=1}^{K}\left(\Pr({\cal E}_{h}^{1}{\cal
E}_{h}^{2}\ldots{\cal E}_{h}^{k-1})-\Pr({\cal E}_{h}^{1}{\cal
E}_{h}^{2}\ldots{\cal E}_{h}^{k})\right)$ $\displaystyle\geq
1-K(\delta/32T)=1-\delta/(32H)$

and by taking a union bound over $h\in[H]$ we get the result. $\Box$

Now that we have shown that the sub-sampled dataset approximates well the
original one, we shift our attention back to showing that our approach
achieves optimism.

We first need a definition and a concetration lemma that is related to least-
squares-estimators from prior work.

######  Definition B.10.

A random variable $X$ is conditionally $\sigma$-subgaussian with respect to
some filtration $\mathbb{F}$ if for all $\lambda\in\mathbb{R}$ it holds that
$\mathbb{E}[\exp(\lambda X)]\leq\exp(\lambda^{2}\sigma^{2}/2)$.

######  Lemma B.11 ((Russo & Van Roy 2013), (Ayoub et al. 2020)).

Let $\mathbb{F}=\\{\mathbb{F}_{p}\\}_{p=0,1,\ldots}$ be a filtration,
$\\{(X_{p},Y_{p})\\}_{p}$ measurable random variables where
$X_{p}\in\mathcal{X},Y_{p}\in\mathbb{R}$. Let $\widetilde{{\mathcal{F}}}$ be a
set of measurable functions from $\mathcal{X}$ to $\mathbb{R}$ and assume that
$\operatorname*{\mathbb{E}}[Y_{p}|\mathbb{F}_{p-1}]=f^{*}(X_{p})$ for some
$f^{*}\in\widetilde{{\mathcal{F}}}$. Assume that
$\\{Y_{p}-f^{*}(X_{p})\\}_{p=1,\ldots}$ is conditionally $\sigma$-subgaussian
given $\mathbb{F}_{p-1}$. Let
$\widehat{f}_{t}=\arg\min_{f\in\widetilde{{\mathcal{F}}}}\sum_{p=1}^{t}\left(f(X_{p})-Y_{p}\right)^{2}$
and
$\widetilde{{\mathcal{F}}}_{t}(\beta)=\left\\{f\in\widetilde{F}:\sum_{p=1}^{t}\left(f(X_{p})-\widehat{f}(X_{p}))\right)^{2}\leq\beta\right\\}$.
Then, for any $\alpha>0$, with probability $1-\delta$, for all $t\geq 1$ it
holds that $f^{*}\in\widetilde{{\mathcal{F}}}_{t}(\beta_{t}(\delta,\alpha))$,
where

$\displaystyle\beta_{t}(\delta,\alpha)=8\sigma^{2}\log(2{\mathcal{N}}(\widetilde{{\mathcal{F}}},\alpha)/\delta)+4t\alpha\left(C+\sqrt{\sigma^{2}\log(4t(t+1)/\delta)}\right).$

We are now ready to prove that our algorithm ensures optimism.

######  Lemma B.12.

With probability at least $1-2\delta$, we have that for all
$h\in[H],k\in[K],s\in{\mathcal{S}},a\in{\mathcal{A}}$

$\displaystyle Q_{h}^{k}(s,a)-Q_{h}^{\pi_{k}}(s,a)\leq\langle
P_{h}(\cdot|s,a),V_{h+1}^{k}(\cdot)-V_{h+1}^{\pi_{k}}(\cdot)\rangle+2b_{h}^{k}(s,a).$

Moreover, it holds that $Q_{h}^{k}(s,a)\geq Q_{h}^{*}(s,a)$.

###### Proof.

Fix some $h\in[H],k\in[K],s\in{\mathcal{S}},a\in{\mathcal{A}}$. Throughout the
proof, we condition on the events in Lemma B.5 and Lemma B.11. We assume that
$k$ is a round that we perform an update.

We define ${\mathcal{X}}={\mathcal{S}}\times{\mathcal{A}}\times{\cal
V},X_{h}^{k}=(s_{h}^{k},a_{h}^{k},V_{h+1}^{k}(\cdot)),Y_{h}^{k}=V_{h+1}^{k}(s^{k}_{h+1})$.
We also pick $\widetilde{{\mathcal{F}}}={\mathcal{F}}_{h}$, where
${\mathcal{F}}_{h}$ is defined in Definition B.4. Then, we see that
$\mathbb{E}[Y_{h}^{k}|\mathbb{F}_{k-1}]=f^{*}_{h}(X_{h}^{k})$, where
$f^{*}_{h}$ is the function that corresponds to the true model $P_{h}$, and we
know that $f^{*}_{h}\in{\mathcal{F}}_{h}$. Recall that the optimization
problem we solve in Algorithm 1 for every round $k$ we update our policy is

$\widehat{P}_{h}^{k}=\arg\min_{P\in{\cal P}_{h}}\sum_{p=1}^{k}\left(\langle
P(\cdot|s^{p}_{h},a^{p}_{h}),V_{h+1}^{p}\rangle-
V_{h+1}^{p}(s^{p}_{h+1})\right)^{2}.$

Based on the definition of ${\mathcal{F}}_{h}$, we can see that this is
equivalent to

$f_{h}^{k}=\arg\min_{f\in{\mathcal{F}}_{h}}\sum_{p=1}^{k}\left(f(s_{h}^{p},a_{h}^{p},V_{h+1}^{p})-V_{h+1}^{p}(s^{p}_{h+1})\right)^{2}.$

Moreoever, $Y_{h}^{k}\in[0,H]$, so $Z_{h}^{k}=Y_{h}^{k}-f_{h}^{*}(X_{h}^{k})$
is $H/2$-conditionally subgaussian. Thus, if we pick $\alpha=1/T$ and

$\beta_{h}^{k}=4H^{2}\log(2{\mathcal{N}}({\mathcal{F}}_{h},1/T)/\delta)+4k/T\left(C+\sqrt{H^{2}/4\log(4(k(k+1)/\delta)})\right)$

then Lemma B.11 gives us that
$||f^{*}_{h}-\widehat{f}_{h}^{k}||^{2}_{{\mathcal{Z}}_{h}^{k}}\leq\beta_{h}^{k}$.
In particular, can pick

$\widetilde{\beta}=\beta_{h}^{K}=4H^{2}\log(2{\mathcal{N}}({\mathcal{F}}_{h},1/T)/\delta)+4K/T\left(C+\sqrt{H^{2}/4\log(4(K(K+1)/\delta)})\right)$

and get a parameter that is independent of $k$. Moreover, Lemma B.5

$||f_{h}^{*}-\widehat{f}_{h}^{k}||_{\widehat{{\mathcal{Z}}}_{h}^{k}}\leq
100\widetilde{\beta}=\beta.$

This implies that for our bonus function we have that
$|\widehat{f}_{h}^{k}(s,a,V_{h+1}^{k}(\cdot))-f_{h}^{*}(s,a,V_{h+1}^{k}(\cdot))|\leq
b_{h}^{k}(s,a)$.

Hence, we have that

$\displaystyle\langle\widehat{P}_{h}^{k}(\cdot|s,a),V_{h+1}^{k}(\cdot)\rangle-\langle
P_{h}(\cdot|s,a),V_{h+1}^{k}(\cdot)\rangle$
$\displaystyle=\widehat{f}_{h}^{k}(s,a,V_{h+1}^{k})-f^{*}_{h}(s,a,V_{h+1}^{k})$
$\displaystyle\leq|\widehat{f}_{h}^{k}(s,a,V_{h+1}^{k})-f^{*}_{h}(s,a,V_{h+1}^{k})|$
$\displaystyle\leq b_{h}^{k}(s,a).$

Now we use the definition of $Q_{h}^{k}(s,a),Q_{h}^{\pi_{k}}(s,a)$ to get that

$\displaystyle Q^{k}_{h}(s,a)$ $\displaystyle\leq
r_{h}^{k}(s,a)+\langle\widehat{P}_{h}^{k}(\cdot|s,a),V_{h+1}^{k}(\cdot)\rangle+b_{h}^{k}(s,a)$
$\displaystyle\leq r_{h}^{k}(s,a)+\langle
P_{h}(\cdot|s,a),V_{h+1}^{k}(\cdot)\rangle+2b_{h}^{k}(s,a)$ $\displaystyle
Q^{\pi_{k}}_{h}(s,a)$ $\displaystyle=r_{h}^{k}(s,a)+\langle
P_{h}(\cdot|s,a),V_{h+1}^{\pi_{k}}(\cdot)\rangle.$

Combining these two, we get that

$\displaystyle Q^{k}_{h}(s,a)-Q^{\pi_{k}}_{h}(s,a)\leq\langle
P_{h}(\cdot|s,a),V_{h+1}^{k}(\cdot)-V_{h+1}^{\pi_{k}}(\cdot)\rangle+2b_{h}^{k}(s,a)$

which proves the first part of the result.

For the second part, notice that if $Q_{h}^{k}(s,a)=H$ then the statement
holds trivially since $Q^{*}_{h}(s,a)\leq H$. So we can assume without loss of
generality that
$Q_{h}^{k}(s,a)=r_{h}^{k}(s,a)+\langle\widehat{P}_{h}^{k}(\cdot|s,a),V_{h+1}^{k}(\cdot)\rangle+b_{h}^{k}(s,a)$.
The Bellman optimality condition gives us that
$Q^{*}_{h}(s,a)=r_{h}^{k}(s,a)+\langle
P_{h}^{*}(\cdot|s,a),V_{h+1}^{*}(\cdot)\rangle$. Hence, we have that

$\displaystyle Q_{h}^{k}(s,a)-Q_{h}^{*}(s,a)$
$\displaystyle=\langle\widehat{P}_{h}^{k}(\cdot|s,a),V_{h+1}^{k}(\cdot)\rangle-\langle
P_{h}(\cdot|s,a),V_{h+1}^{*}(\cdot)\rangle+b_{h}^{k}(s,a)$
$\displaystyle=\langle\widehat{P}_{h}^{k}(\cdot|s,a),V_{h+1}^{k}(\cdot)\rangle-\langle
P_{h}(\cdot|s,a),V_{h+1}^{k}(\cdot)\rangle+\langle
P_{h}(\cdot|s,a),V_{h+1}^{k}(\cdot)\rangle-\langle
P_{h}(\cdot|s,a),V_{h+1}^{*}(\cdot)\rangle+b_{h}^{k}(s,a)$
$\displaystyle=\langle\widehat{P}_{h}^{k}(\cdot|s,a)-P_{h}(\cdot|s,a),V_{h+1}^{k}(\cdot)\rangle+\langle
P_{h}(\cdot|s,a),V_{h+1}^{k}(\cdot)-V_{h+1}^{*}(\cdot)\rangle+b_{h}^{k}(s,a).$

Now from our previous discussion it follows that
$b_{h}^{k}(s,a)+\langle\widehat{P}_{h}^{k}(\cdot|s,a)-P_{h}(\cdot|s,a),V_{h+1}^{k}(\cdot)\rangle\geq
0$. Hence, it suffices to show that $\langle
P_{h}(\cdot|s,a),V_{h+1}^{k}(\cdot)-V_{h+1}^{*}(\cdot)\rangle\geq 0$. To do
that, we can just prove that
$V_{h+1}^{k}(s^{\prime})-V_{h+1}^{*}(s^{\prime})\geq 0,\forall
s^{\prime}\in{\mathcal{S}}$. Since
$V_{H+1}^{k}(s^{\prime})=V_{H+1}^{*}(s^{\prime})=0,\forall
s^{\prime}\in{\mathcal{S}}$ we get that $Q_{H}^{k}(s,a)\geq Q_{H}^{*}(s,a)$.
Thus, if we combine this with the update rule for $V_{h}^{k},V_{h}^{*}$ we get
the claim by induction. ∎

Now that we have established the previous lemma, we need to bound the bonus
that we are using in every round. The issue is that we do not update our
policy in every round.

To do that, we follow a similar approach as in Appendix A.

######  Lemma B.13.

For every set $K^{\prime}\subseteq[K]$ With probability at least $1-\delta$,
we have that

$\displaystyle\sum_{i=1}^{|K^{\prime}|}\sum_{h=1}^{H}b_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})\leq
H+H(H+1)\dim_{E}({\mathcal{F}},1/T)+CH\sqrt{\textnormal{dim}_{E}({\mathcal{F}},1/T)|K^{\prime}|\beta}$

where
$\textnormal{dim}_{E}({\mathcal{F}},1/T)=\max_{h\in[H]}\textnormal{dim}_{E}({\mathcal{F}}_{h},1/T)$.

###### Proof.

We condition on the event described in Lemma B.5. From the definition of the
bonus function, we have that for any $k\in[K]$

$\displaystyle
b_{h}^{k}(s_{h}^{k},a_{h}^{k})\leq\bar{b}_{h}^{k}(s_{h}^{k},a_{h}^{k})=\sup_{||f_{1}-f_{2}||^{2}_{{\mathcal{Z}}_{h}^{k}}\leq
100\beta}|f_{1}(s_{h}^{k},a_{h}^{k})-f_{2}(s_{h}^{k},a_{h}^{k})|.$

We bound
$\sum_{i=1}^{K^{\prime}}\bar{b}_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})$ for
each $h\in[H]$ separately.

Given some $\epsilon>0$, we define $\widetilde{K}=\\{k\in
K^{\prime}:\bar{b}_{h}^{k}(s_{h}^{k},a_{h}^{k})>\epsilon\\}$, i.e. the set of
episodes in $K^{\prime}$ where the bonus function at $h$ has value greater
than $\epsilon$. Consider some $k\in K^{\prime}$. We denote
${\mathcal{L}}_{h}=\\{(s_{h}^{k},a_{h}^{k},V_{h+1}^{k}(\cdot)):k\in\widetilde{K}\\},L_{h}=|{\mathcal{L}}_{h}|$,
and $N=L_{h}/\textnormal{dim}_{E}({\mathcal{F}}_{h},\epsilon)-1$. Our goal is
to show that there is some
$z_{h}^{k}=(s_{h}^{k},a_{h}^{k},V_{h+1}^{k}(\cdot))\in{\mathcal{L}}_{h}$ that
is $\epsilon$-dependent on at least $N$ disjoint subsequences in
${\mathcal{Z}}_{h}^{k}\cap{\mathcal{L}}_{h}$.

To do that, we decompose ${\mathcal{L}}_{h}$ into $N+1$ disjoint subsets and
we denote the $j$-th subset by ${\mathcal{L}}_{h,j}$. We use the following
procedure. Initially we set ${\mathcal{L}}_{h,j}=\emptyset$ for all
$j\in[N+1]$ and consider every $z_{h}^{k}\in{\mathcal{L}}_{h}$ in a sequential
manner. For each such $z_{h}^{k}$ we find the smallest index $j,1\leq j\leq
N$, such that $z_{h}^{k}$ is $\epsilon$-independent of the elements in
${\mathcal{L}}_{h,j}$ with respect to ${\mathcal{F}}_{h}$. If there is no such
$j$, we set $j=N+1$. Then, we update
${\mathcal{L}}_{h,j}\leftarrow{\mathcal{L}}_{h,j}\cup z_{h}^{k}$. Notice that
after we go through all the elements of ${\mathcal{L}}_{h}$, we must have that
${\mathcal{L}}_{h,N+1}\neq\emptyset$. This is because every set
${\mathcal{L}}_{h,j},1\leq j\leq N$, contains at most
$\textnormal{dim}_{E}({\mathcal{F}}_{h},\epsilon)$ elements. Moreover, by
definition, every element $z_{h}^{k}\in{\mathcal{L}}_{h,N+1}$ is
$\epsilon$-dependent on at least $N$ disjoint subsequences in
${\mathcal{L}}_{h}$.

Furthermore, since $\bar{b}_{h}^{k}(s_{h}^{k},a_{h}^{k})>\epsilon$ for all
$z_{h}^{k}\in{\mathcal{L}}_{h}$ there must exist
$f_{1},f_{2}\in{\mathcal{F}}_{h}$ such that
$|f_{1}(s_{h}^{k},a_{h}^{k},V_{h+1}^{k}(\cdot))-f_{2}(s_{h}^{k},a_{h}^{k},V_{h+1}^{k}(\cdot))|>\epsilon$
and $||f_{1}-f_{2}||^{2}_{{\mathcal{Z}}_{h}^{k}}\leq 100\beta$. Hence, since
$z_{h}^{k}\in{\mathcal{L}}_{h,N+1}$ is $\epsilon$-dependent on $N$ disjoint
subsequences ${\mathcal{L}}_{h}$ and for each such subsequence
${\mathcal{L}}$, by the definition of $\epsilon$-dependence, it holds that
$||f_{1}-f_{2}||^{2}_{{\mathcal{L}}}>\epsilon^{2}$ we have that

$\displaystyle
N\epsilon^{2}\leq||f_{1}-f_{2}||^{2}_{{\mathcal{Z}}_{h}^{k}}\leq 100\beta$
$\displaystyle\implies(L_{h}/\textnormal{dim}_{E}({\mathcal{F}}_{h},\epsilon)-1)\epsilon^{2}\leq
100\beta$ $\displaystyle\implies
L_{h}\leq\left(\frac{100\beta}{\epsilon^{2}}+1\right)\textnormal{dim}_{E}({\mathcal{F}}_{h},\epsilon).$

We now pick a permutation
$\bar{b}_{1}\geq\bar{b}_{2}\geq\ldots\geq\bar{b}_{|K^{\prime}|}$ of the bonus
functions $\\{\bar{b}_{h}^{k}(s^{k}_{h},a^{k}_{h})\\}_{k\in K^{\prime}}$. For
all $\bar{b}_{k}\geq 1/|K^{\prime}|$ it holds that

$\displaystyle
k\leq\left(\frac{100\beta}{\bar{b}_{k}^{2}}+1\right)\textnormal{dim}_{E}({\mathcal{F}}_{h},\bar{b}_{k})$
$\displaystyle\leq\left(\frac{100\beta}{\bar{b}_{k}^{2}}+1\right)\textnormal{dim}_{E}({\mathcal{F}}_{h},1/K^{\prime})\implies$
$\displaystyle\bar{b}_{k}$
$\displaystyle\leq\left(\frac{k}{\textnormal{dim}_{E}({\mathcal{F}}_{h},1/K^{\prime})}-1\right)^{-1/2}\sqrt{100\beta}.$

Moreover, notice that we get by definition that $\bar{b}_{k}\leq H+1$. Hence,
we have that

$\displaystyle\sum_{i=1}^{|K^{\prime}|}\bar{b}_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})$
$\displaystyle=\sum_{i:\bar{b}_{k_{i}}<1/|K^{\prime}|}\bar{b}_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})+\sum_{i:\bar{b}_{k_{i}}\geq
1/|K^{\prime}|}\bar{b}_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})$
$\displaystyle\leq|K^{\prime}|\cdot 1/|K^{\prime}|+\sum_{i:\bar{b}_{k_{i}}\geq
1/|K^{\prime}|,i\leq\textnormal{dim}_{E}({\mathcal{F}}_{h},1/|K^{\prime}|)}\bar{b}_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})+\sum_{i:\bar{b}_{k_{i}}\geq
1/|K^{\prime}|,|K^{\prime}|\geq
i>\textnormal{dim}_{E}({\mathcal{F}}_{h},1/|K^{\prime}|)}\bar{b}_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})$
$\displaystyle\leq
1+(H+1)\dim_{E}({\mathcal{F}}_{h},1/|K^{\prime}|)+\sum_{|K^{\prime}|\geq
i>\textnormal{dim}_{E}({\mathcal{F}}_{h},1/|K^{\prime}|)}\left(\frac{k}{\textnormal{dim}_{E}({\mathcal{F}}_{h},1/|K^{\prime}|)}-1\right)^{-1/2}\sqrt{100\beta}$
$\displaystyle\leq
1+(H+1)\dim_{E}({\mathcal{F}}_{h},1/|K^{\prime}|)+C\sqrt{\textnormal{dim}_{E}({\mathcal{F}}_{h},1/|K^{\prime}|)|K^{\prime}|\beta}$
$\displaystyle\leq
1+(H+1)\dim_{E}({\mathcal{F}}_{h},1/T)+C\sqrt{\textnormal{dim}_{E}({\mathcal{F}}_{h},1/T)|K^{\prime}|\beta}$

for some constant $C>0$, where the second to last inequality can be obtained
by bounding the summation by the integral and the last one by the definition
of the eluder dimension. We get the final result by summing up all the
inequalities over $H$. ∎

The next step in our proof, is to bound the number of episodes that our policy
can be worse than the optimal one by $2^{n}{\textnormal{gap}}_{\min}$, for all
$n\in\mathbb{N}$. This is inspired by He et al. (2021).

######  Lemma B.14.

If we pick

$\beta=4H^{2}\log(2{\mathcal{N}}({\mathcal{F}},1/T)/\delta)+4/H\left(C+\sqrt{H^{2}/4\log(4(K(K+1)/\delta)})\right),$

then for every $h\in[H]$ and $n\in\mathbb{N}$, with probability at least
$1-(K+3)\delta$, we have that

$\displaystyle\sum_{k=1}^{K}\mathbbm{1}\left[V_{h}^{*}(s_{h}^{k})-Q_{h}^{\pi_{k}}(s_{h}^{k},a_{h}^{k})\geq
2^{n}{\textnormal{gap}}_{\min}\right]\leq\frac{\widetilde{C}H^{4}\log(T{\mathcal{N}}({\mathcal{F}}_{h},1/T)/\delta)\dim^{2}_{E}({\mathcal{F}},1/T)}{4^{n}{\textnormal{gap}}_{\min}^{2}}.$

###### Proof.

We keep $h$ fixed.

We denote by $K^{\prime}$ the set of episodes where the gap at step $h$ is at
least $2^{n}$, i.e.

$\displaystyle
K^{\prime}=\left\\{k\in[K]:V^{*}_{h}(s_{h}^{k})-Q_{h}^{\pi_{k}}(s_{h}^{k},a_{h}^{k})\geq
2^{n}{\textnormal{gap}}_{\min}\right\\}.$

The goal is to bound the quantity
$\sum_{i=1}^{|K^{\prime}|}\left(Q_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})-Q_{h}^{\pi_{k_{i}}}(s_{h}^{k_{i}},a_{h}^{k_{i}})\right)$
from below and above with functions $f_{1}(|K^{\prime}|),f_{2}(|K^{\prime}|)$
and then use the fact that $f_{1}(|K^{\prime}|)\leq f_{2}(|K^{\prime}|)$ to
derive an upper bound on $|K^{\prime}|$.

For the lower bound, we have that

$\displaystyle\sum_{i=1}^{|K^{\prime}|}\left(Q_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})-Q_{h}^{\pi_{k_{i}}}(s_{h}^{k_{i}},a_{h}^{k_{i}})\right)$
$\displaystyle\geq\sum_{i=1}^{|K^{\prime}|}\left(Q_{h}^{k_{i}}(s_{h}^{k_{i}},\pi_{h}^{*}(s_{h}^{k_{i}}))-Q_{h}^{\pi_{k_{i}}}(s_{h}^{k_{i}},a_{h}^{k_{i}})\right)$
$\displaystyle\geq\sum_{i=1}^{|K^{\prime}|}\left(Q_{h}^{*}(s_{h}^{k_{i}},\pi_{h}^{*}(s_{h}^{k_{i}}))-Q_{h}^{\pi_{k_{i}}}(s_{h}^{k_{i}},a_{h}^{k_{i}})\right)$
$\displaystyle=\sum_{i=1}^{|K^{\prime}|}\left(V_{h}^{*}(s_{h}^{k_{i}})-Q_{h}^{\pi_{k_{i}}}(s_{h}^{k_{i}},a_{h}^{k_{i}})\right)$
$\displaystyle\geq 2^{n}{\textnormal{gap}}_{\min}|K^{\prime}|$

where the first inequality holds by the definition of the policy
$\pi_{k_{i}}$, the second one follows because $Q^{k_{i}}_{h}(\cdot,\cdot)$ is
an optimistic estimate of $Q^{*}_{h}(\cdot,\cdot)$ which happens with
probability at least $1-2\delta$ (see Lemma B.12) and the third one by the
definition of $k_{i}$.

We get the upper bound on this quantity in the following way. For any
$h^{\prime}\in[H]$ we have

$\displaystyle
Q_{h^{\prime}}^{k}(s_{h^{\prime}}^{k},a_{h^{\prime}}^{k})-Q_{h^{\prime}}^{\pi_{k}}(s_{h^{\prime}}^{k},a_{h^{\prime}}^{k})$
$\displaystyle\leq\sum_{s^{\prime}\in{\mathcal{S}}}P_{h^{\prime}}(s^{\prime}|s_{h^{\prime}}^{k},a_{h^{\prime}}^{k})V^{k}_{h^{\prime}+1}(s^{\prime})+r_{h^{\prime}}(s_{h^{\prime}}^{k},a_{h^{\prime}}^{k})+2b_{h^{\prime}}^{k}(s_{h^{\prime}}^{k},a_{h^{\prime}}^{k})-Q_{h^{\prime}}^{\pi_{k}}(s_{h^{\prime}}^{k},a_{h^{\prime}}^{k})$
$\displaystyle=\left\langle
P_{h^{\prime}}(\cdot|s_{h^{\prime}}^{k},a_{h^{\prime}}^{k}),V_{h^{\prime}+1}^{k}-V_{h^{\prime}+1}^{\pi_{k}}\right\rangle+2b_{h^{\prime}}^{k}(s_{h^{\prime}}^{k},a_{h^{\prime}}^{k})$
$\displaystyle=V_{h^{\prime}+1}^{k}(s_{h^{\prime}+1}^{k})-V_{h^{\prime}+1}^{\pi_{k}}(s_{h^{\prime}+1}^{k})+\epsilon_{h^{\prime}}^{k}+2b_{h^{\prime}}^{k}(s_{h^{\prime}}^{k},a_{h^{\prime}}^{k})$
$\displaystyle=Q_{h^{\prime}+1}^{k}(s_{h^{\prime}+1}^{k},a_{h^{\prime}+1}^{k})-Q_{h^{\prime}+1}^{\pi_{k}}(s_{h^{\prime}+1}^{k},a_{h^{\prime}+1}^{k})+\epsilon_{h^{\prime}}^{k}+2b_{h^{\prime}}^{k}(s_{h^{\prime}}^{k},a_{h^{\prime}}^{k})$

where we define $\epsilon_{h^{\prime}}^{k}=\left\langle
P_{h^{\prime}}(\cdot|s_{h^{\prime}}^{k},a_{h^{\prime}}^{k}),V_{h^{\prime}+1}^{k}-V_{h^{\prime}+1}^{\pi_{k}}\right\rangle-\left(V_{h^{\prime}+1}^{k}(s_{h^{\prime}+1}^{k})-V_{h^{\prime}+1}^{\pi_{k}}(s_{h^{\prime}+1}^{k})\right)$
and the inequality follows from Lemma B.12.

We now take the summation over all $k\in|K^{\prime}|,h\leq h^{\prime}\leq H$
and we get

$\displaystyle\sum_{i=1}^{|K^{\prime}|}\sum_{h^{\prime}=h}^{H}\left(Q_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})-Q_{h}^{\pi_{k_{i}}}(s_{h}^{k_{i}},a_{h}^{k_{i}})\right)\leq\sum_{i=1}^{|K^{\prime}|}\sum_{h^{\prime}=h}^{H}\epsilon_{h^{\prime}}^{k_{i}}+\sum_{i=1}^{|K^{\prime}|}\sum_{h^{\prime}=h}^{H}b_{h^{\prime}}^{k_{i}}(s_{h^{\prime}}^{k_{i}},a_{h^{\prime}}^{k_{i}}).$

We will bound each of the two terms on the RHS separately.

For the first term, we notice that $x_{j}=\left\langle
P_{j}(\cdot|s_{j}^{k_{i}},a_{j}^{k_{i}}),V_{j+1}^{k_{i}}-V_{j+1}^{\pi_{k_{i}}}\right\rangle-\left(V_{j+1}^{k_{i}}(s_{j+1}^{k_{i}})-V_{j+1}^{\pi_{k_{i}}}(s_{j+1}^{k_{i}})\right)$
forms a martingale difference sequence with zero mean and $|x_{j}|\leq 2H$.
Hence, we can use Lemma A.7 and that for each $k\in K^{\prime}$, with
probability at least $1-\delta$ we have that

$\displaystyle\sum_{i=1}^{k}\sum_{j=1}^{H}\left(\left\langle
P_{j}(\cdot|s_{j}^{k_{i}},a_{j}^{k_{i}}),V_{j+1}^{k_{i}}-V_{j+1}^{\pi_{k_{i}}}\right\rangle-\left(V_{j+1}^{k_{i}}(s_{j+1}^{k_{i}})-V_{j+1}^{\pi_{k_{i}}}(s_{j+1}^{k_{i}})\right)\right)\leq\sqrt{8kH^{3}\log(1/\delta)}.$

If we take the union bound over all $k\in[K]$ we have that with probability at
least $1-|K^{\prime}|\delta$

$\displaystyle\sum_{i=1}^{|K^{\prime}|}\sum_{h^{\prime}=h}^{H}\epsilon_{h^{\prime}}^{k_{i}}\leq\sqrt{8|K^{\prime}|H^{3}\log(1/\delta)}.$

We now focus on the second term. Using Lemma B.13 we get that

$\displaystyle\sum_{i=1}^{|K^{\prime}|}\sum_{h^{\prime}=h}^{H}b_{h^{\prime}}^{k_{i}}(s_{h^{\prime}}^{k_{i}},a_{h^{\prime}}^{k_{i}})\leq
H+H(H+1)\dim_{E}({\mathcal{F}},1/T)+CH\sqrt{\textnormal{dim}_{E}({\mathcal{F}},1/T)|K^{\prime}|\beta}$

and this happens with probability at least $1-\delta$. Hence, combining the
upper and lower bound of

$\sum_{i=1}^{|K^{\prime}|}\left(Q_{h}^{k_{i}}(s_{h}^{k_{i}},a_{h}^{k_{i}})-Q_{h}^{\pi_{k_{i}}}(s_{h}^{k_{i}},a_{h}^{k_{i}})\right)$

we get that

$\displaystyle 2^{n}{\textnormal{gap}}_{\min}|K^{\prime}|$
$\displaystyle\leq\sqrt{8|K^{\prime}|H^{3}\log(1/\delta)}+H+H(H+1)\dim_{E}({\mathcal{F}},1/T)+CH\sqrt{\textnormal{dim}_{E}({\mathcal{F}},1/T)|K^{\prime}|\beta}$
$\displaystyle\implies|K^{\prime}|$
$\displaystyle\leq\frac{\widetilde{C}H^{4}\log(T{\mathcal{N}}({\mathcal{F}},1/T)/\delta)\dim^{2}_{E}({\mathcal{F}},1/T)}{4^{n}{\textnormal{gap}}_{\min}^{2}}.$

∎

We are now ready to prove Lemma B.1.

Proof of Lemma B.1: Throughout this proof we condition on the event described
in Lemma B.14 which happens with probability at least $1-(K+3)\delta$. Since
${\textnormal{gap}}_{\min}>0$ whenever we do not take the optimal action, we
have that either $V_{h}^{*}(s_{k})-Q_{h}^{*}(s_{h}^{k},a_{h}^{k})=0$ or
$V_{h}^{*}(s_{k})-Q_{h}^{*}(s_{h}^{k},a_{h}^{k})\geq{\textnormal{gap}}_{\min}$.
Our approach is to divide the interval $[0,H]$ into
$N=\lceil\log(H/{\textnormal{gap}}_{\min})\rceil$ intervals and count the
number of $V_{h}^{*}(s_{k})-Q_{h}^{*}(s_{h}^{k},a_{h}^{k})$ that fall into
each interval. Notice that for every
$V_{h}^{*}(s_{k})-Q_{h}^{*}(s_{h}^{k},a_{h}^{k})$ that falls into interval $i$
we can get an upper bound of
$V_{h}^{*}(s_{k})-Q_{h}^{*}(s_{h}^{k},a_{h}^{k})\leq
2^{i}{\textnormal{gap}}_{\min}$ and this upper bound is essentially tight.
Hence, we have that

$\displaystyle\sum_{k=1}^{K}\left(V_{h}^{*}(s_{h}^{k})-Q_{h}^{*}(s_{h}^{k},a_{h}^{k})\right)$
$\displaystyle\leq\sum_{i=1}^{N}\sum_{k=1}^{K}\mathbbm{1}\left[2^{i}{\textnormal{gap}}_{\min}\geq
V_{h}^{*}(s_{h}^{k})-Q_{h}^{*}(s_{h}^{k},a_{h}^{k})\geq
2^{i-1}{\textnormal{gap}}_{\min}\right]\cdot 2^{i}{\textnormal{gap}}_{\min}$
$\displaystyle\leq\sum_{i=1}^{N}\sum_{k=1}^{K}\mathbbm{1}\left[V_{h}^{*}(s_{h}^{k})-Q_{h}^{*}(s_{h}^{k},a_{h}^{k})\geq
2^{i-1}{\textnormal{gap}}_{\min}\right]\cdot 2^{i}{\textnormal{gap}}_{\min}$
$\displaystyle\leq\sum_{i=1}^{N}\frac{\widetilde{C}H^{6}\log(T{\mathcal{N}}({\mathcal{F}},1/T)/\delta)\dim^{2}_{E}({\mathcal{F}},1/T)}{4^{i-1}{\textnormal{gap}}_{\min}^{2}}\cdot
2^{i}{\textnormal{gap}}_{\min}$
$\displaystyle=\sum_{i=1}^{N}\frac{C^{\prime}H^{4}\log(T{\mathcal{N}}({\mathcal{F}},1/T)/\delta)\dim^{2}_{E}({\mathcal{F}},1/T)}{2^{i}{\textnormal{gap}}_{\min}}$
$\displaystyle\leq\frac{CH^{4}\log(T{\mathcal{N}}({\mathcal{F}},1/T)/\delta)\dim^{2}_{E}({\mathcal{F}},1/T)}{{\textnormal{gap}}_{\min}}$

where the first inequality holds by the definition of the intervals, the
second due to the properties of the indicator function, the third because of
Lemma B.14 and in the last two steps we just manipulate the constants. $\Box$