<figure><img src="image_1.png" /></figure>

HAL
open science

# Kernel-based reinforcement Learning: A finite-time analysis

Omar D Domingues, Pierre Ménard, Matteo Pirotta, Emilie Kaufmann,
Michal Valko

► To cite this version:

Omar D Domingues, Pierre Ménard, Matteo Pirotta, Emilie Kaufmann, Michal Valko. Kernel-based reinforcement Learning: A finite-time analysis. International Conference on Machine Learning, Jul 2021, Vienna / Virtual, Austria. hal-02541790v2

HAL Id: hal-02541790

https://inria.hal.science/hal-02541790v2

Submitted on 16 Jul 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
Omar D. Domingues¹² Pierre Ménard³ Matteo Pirotta⁴ Emilie Kaufmann¹⁵ Michal Valko¹⁵⁶

**Abstract**

We consider the exploration-exploitation dilemma in finite-horizon reinforcement learning problems whose state-action space is endowed with a metric. We introduce Kernel-UCBVI, a model-based optimistic algorithm that leverages the smoothness of the MDP and a non-parametric kernel estimator of the rewards and transitions to efficiently balance exploration and exploitation. For problems with *K* episodes and horizon *H*, we provide a regret bound of $\tilde{O}(H^3 K^{\frac{2d}{d+1}})$, where *d* is the covering dimension of the joint state-action space. This is the first regret bound for kernel-based RL using smoothing kernels, which requires very weak assumptions on the MDP and has been previously applied to a wide range of tasks. We empirically validate our approach in continuous MDPs with sparse rewards.

**1. Introduction**

Reinforcement learning (RL) is a learning paradigm in which an agent interacts with an environment by taking actions and receiving rewards. At each time step *t*, the environment is characterized by a state variable $x_t \in \mathcal{X}$, which is observed by the agent and influenced by its actions $a_t \in \mathcal{A}$. In this work, we consider the online learning problem where the agent has to learn how to act optimally by interacting with an unknown environment. To learn efficiently, the agent has to trade-off exploration to gather information about the environment and exploitation to act optimally with respect to the current knowledge. The performance of the agent is measured by the *regret*, i.e., the difference between the rewards that would be gathered by an optimal agent and the rewards obtained by the agent. This problem has been extensively studied for Markov Decision Processes (MDPs) with finite state-action space. Optimism

in the face of uncertainty (OFU, Jaksch et al. 2010) and Thompson Sampling (Strens, 2000; Osband et al., 2013) principles have been used to design algorithms with sublinear regret. However, the guarantees for these approaches cannot be naturally extended to an arbitrarily large state-action space since the regret depends on the number of states and actions. When the state-action space is continuous, additional structure in MDP is required to efficiently solve the exploration-exploitation dilemma.

In this paper, we focus on the online learning problem in MDPs with large or continuous state-action spaces. We suppose that the state-action set $\mathcal{X} \times \mathcal{A}$ is equipped with a known *metric*. For instance, this is typically the case in continuous control problems in which the state space is a subset of $\mathbb{R}^d$ equipped with the Euclidean metric. As shown by Ormoneit & Sen (2002) and Barreto et al. (2016), smoothing-kernel approaches converge asymptotically to an optimal policy and perform well empirically in a wide range of continuous MDPs. In this paper, we tackle the problem of *exploration* in such approaches, by proposing an *optimistic* algorithm based on smoothing-kernel estimators of the reward and transition functions of the underlying MDP. The advantages of this approach are: (i) it requires weak assumptions on the MDP, (ii) it allows us to easily provide expert knowledge to the algorithm through kernel design, and (iii) it applies to problems with possibly infinite states without relying on any kind of discretization.

**Related work** Kernel-based RL (KBRL) using smoothing kernels has been initially proposed by Ormoneit & Sen (2002), who analyzed the algorithm assuming that transitions are generated from *independent* samples, and provide *asymptotic* convergence guarantees. Barreto et al. (2016) propose a stochastic factorization technique to reduce the computational complexity of KBRL. In this paper, we provide a modification of KBRL that collects data *online* and for which we prove *finite-time* regret guarantees under weak conditions on the MDP. Under stronger conditions, that use positive-defined kernels defining reproducing kernel Hilbert spaces (RKHS) or Gaussian Processes, regret bounds are provided by Chowdhury & Gopalan (2019), Chowdhury & Oliveira (2020) and Yang et al. (2020).

Regret minimization in finite MDPs has been extensively studied both in model-based and model-free settings. While

<footnote n="1">¹Inria Lille ²Université de Lille ³Otto von Guericke University ⁴Facebook AI Research, Paris ⁵CNRS ⁶DeepMind Paris. Correspondence to: Omar D. Domingues <omar.darwiche-domingues@inria.fr>.</footnote>
model-based algorithms (Jaksch et al., 2010; Azar et al., 2017; Zanette & Brunskill, 2019) use the estimated rewards and transitions to perform planning at each episode, model-free algorithms (Jin et al., 2018) directly build an estimate of the optimal Q-function that is updated incrementally.

For MDPs with continuous state-action space, the sample complexity (Kakade et al., 2003; Kearns & Singh, 2002; Lat-timore et al., 2013; Pazis & Parr, 2013) or regret have been studied under structural assumptions. Regarding regret min- imization, a standard assumption is that rewards and tran- sitions are Lipschitz continuous. Ortner & Ryabko (2012) studied this problem in average reward problems. They com- bined the ideas of UCRL2 (Jaksch et al., 2010) and uniform discretization, proving a regret bound of $\tilde{O}(T^{\frac{2d+1}{2d+2}})$ for a learning horizon $T$ in $d$-dimensional state spaces. This work was later extended by Lakshmanan et al. (2015) to use a kernel density estimator instead of a frequency estimator for each region of the fixed discretization. For each discrete region $I(x)$, the density $p(\cdot|I(x), a)$ of the transition kernel is computed through kernel density estimation. The granu- larity of the discretization is selected in advance based on the properties of the MDP and the learning horizon $T$. As a result, they improve upon the bound of Ortner & Ryabko (2012), but require the transition kernels to have densities that are $\kappa$ times differentiable.<fnref n="1" /> However, these two al- gorithms rely on an intractable optimization problem for finding an optimistic MDP. Jian et al. (2019) solve this issue by providing an algorithm that uses exploration bonuses, but they still rely on a uniform discretization of the state space. Ok et al. (2018) studied the asymptotic regret in Lipschitz MDPs with finite state and action spaces, providing a nearly asymptotically optimal algorithm. Their algorithm lever- ages ideas from asymptotic optimal algorithms in structured bandits (Combes et al., 2017) and tabular RL (Burnetas & Katehakis, 1997), but does not scale to continuous state-action spaces.

Regarding exploration for finite-horizon MDP with continu- ous state-action space, Ni et al. (2019) present an algorithm for deterministic MDPs with Lipschitz transitions. Assum- ing that the Q-function is Lipschitz continuous, Song & Sun (2019) provided a model-free algorithm by combin- ing the ideas of tabular optimistic Q-learning (Jin et al., 2018) with uniform discretization, showing a regret bound of $O(H^{\frac{5}{2}}K^{\frac{d+1}{d+2}})$ where $d$ is the covering dimension of the state-action space. This approach was extended by Sinclair et al. (2019) and Touati et al. (2020) to use adaptive parti- tioning of the state-action space, achieving the same regret bound. Osband & Van Roy (2014) prove a Bayesian regret bound in terms of the eluder and Kolmogorov dimension, as- suming access to an approximate MDP planner. In addition,

there are many results for facing the exploration problem in continuous MDP with parametric structure, e.g., linear- quadratic systems (Abbasi-Yadkori & Szepesvári, 2011) or other linearity assumptions (Yang & Wang, 2020; Jin et al., 2020), which are outside the scope of our paper.

**Contributions** The main contributions of this paper are the following. (1) We provide the first regret bound for KBRL, which applies to a wide range of RL tasks with an entirely data-dependent approach; (2) In order to derive our regret bound, we provide novel concentration inequalities for weighted sums (Lemmas 2 and 3) that permit to build confidence intervals for non-parametric kernel estimators (Propositions 1 and 2) that are of independent interest. (3) We show that the regret of model-based algorithms, although having a better empirical performance, seem to suffer from a worse dependence on the state-action dimension $d$ than model-free ones. We discuss the origins of this issue by looking at the regret bounds of tabular algorithms.

## 2. Setting

**Notation** For any $j \in \mathbb{Z}_+$, we define $[j] \stackrel{\text{def}}{=} \{1, \dots, j\}$. For a measure $P$ and any function $f$, let $Pf \stackrel{\text{def}}{=} \int f(y)dP(y)$. If $P(\cdot|x, a)$ is a measure for all $(x, a)$, we let $Pf(x, a) = P(\cdot|x, a)f = \int f(y)dP(y|x, a)$.

**Markov decision processes** Let $\mathcal{X}$ and $\mathcal{A}$ be the sets of states and actions, respectively. We assume that there exists a metric $\rho: (\mathcal{X} \times \mathcal{A})^2 \to \mathbb{R}_{\ge 0}$ on the state-action space and that $(\mathcal{X}, \mathcal{T}_{\mathcal{X}})$ is a measurable space with $\sigma$-algebra $\mathcal{T}_{\mathcal{X}}$. We consider an episodic Markov decision process (MDP), defined by the tuple $\mathcal{M} \stackrel{\text{def}}{=} (\mathcal{X}, \mathcal{A}, H, P, r)$ where $H \in \mathbb{Z}_+$ is the length of each episode, $P = \{P_h\}_{h \in [H]}$ is a set of transition kernels from $(\mathcal{X} \times \mathcal{A}) \times \mathcal{T}_{\mathcal{X}}$ to $\mathbb{R}_{\ge 0}$, and $r = \{r_h\}_{h \in [H]}$ is a set of reward functions from $\mathcal{X} \times \mathcal{A}$ to $[0, 1]$. A policy $\pi$ is a mapping from $[H] \times \mathcal{X}$ to $\mathcal{A}$, such that $\pi(h, x)$ is the action chosen by $\pi$ in state $x$ at step $h$. The Q-value of a policy $\pi$ for state-action $(x, a)$ at step $h$ is the expected sum of rewards obtained by taking action $a$ in state $x$ at step $h$ and then following the policy $\pi$, that is

$$Q_{h}^{\pi}(x, a) \stackrel{\text{def}}{=} \mathbb{E} \left[ \sum_{h'=h}^{H} r_{h'}(x_{h'}, a_{h'}) \mid x_h = x, a_h = a \right],$$

where the expectation is under transitions in the MDP $x_{h'+1} \sim P_{h'}(\cdot|x_{h'}, a_{h'})$ and $a_{h'} = \pi(h', x_{h'})$. The value function of policy $\pi$ at step $h$ is $V_h^\pi(x) = Q_h^\pi(x, \pi(h, x))$. The optimal value functions, defined by $V_h^*(x) \stackrel{\text{def}}{=} \sup_\pi V_h^\pi(x)$ for $h \in [H]$, satisfy the optimal Bellman equations (Puterman, 1994): $V_h^*(x) = \max_{a \in \mathcal{A}} Q_h^*(x, a)$,

<footnote n="1">¹For instance, when $d = 1$ and $\kappa \to \infty$, their bound approaches $T^{\frac{2}{3}}$, improving the previous bound of $T^{\frac{3}{4}}$.</footnote>
where

$$Q_h^*(x, a) \stackrel{\text{def}}{=} r_h(x, a) + \int_{\mathcal{X}} V_{h+1}^*(y) dP_h(y|x, a)$$

and, by definition, $V_{H+1}^*(x) = 0$ for all $x \in \mathcal{X}$.

**Learning problem** A reinforcement learning agent interacts with $\mathcal{M}$ in a sequence of episodes $k \in [K]$ of fixed length $H$ by playing a policy $\pi_k$ in each episode, where the initial state $x_1^k$ is chosen arbitrarily and revealed to the agent. The learning agent does not know $P$ and $r$ and it selects the policy $\pi_k$ based on the samples observed over previous episodes. Its performance is measured by the regret $\mathcal{R}(K) \stackrel{\text{def}}{=} \sum_{k=1}^K (V_1^*(x_1^k) - V_1^{\pi_k}(x_1^k))$.

We make the following assumptions:

**Assumption 1.** The metric $\rho$ is given to the learner. Also, there exists a metric $\rho_X$ on $\mathcal{X}$ and a metric $\rho_A$ on $\mathcal{A}$ such that, for all $(x, x', a, a')$, $\rho[(x, a), (x', a')] = \rho_X(x, x') + \rho_A(a, a')$.

**Assumption 2.** The reward functions are $\lambda_r$-Lipschitz and the transition kernels are $\lambda_p$-Lipschitz with respect to the 1-Wasserstein distance: $\forall (x, a, x', a')$ and $\forall h \in [H]$, $|r_h(x, a) - r_h(x', a')| \le \lambda_r \rho[(x, a), (x', a')], \text{ and}$

$$|r_h(x, a) - r_h(x', a')| \le \lambda_r \rho[(x, a), (x', a')], \quad \text{and}$$

$$W_1(P_h(\cdot|x, a), P_h(\cdot|x', a')) \le \lambda_p \rho[(x, a), (x', a')]$$

where, for two measures $\mu$ and $\nu$, we have $W_1(\mu, \nu) \stackrel{\text{def}}{=} \sup_{f: \text{Lip}(f) \le 1} \int_{\mathcal{X}} f(y)(d\mu(y) - d\nu(y))$ and where, for a function $f: \mathcal{X} \to \mathbb{R}$, $\text{Lip}(f)$ denotes its Lipschitz constant w.r.t. $\rho_X$.

To assess the relevance of these assumptions, we show below that they apply to deterministic MDPs with Lipschitz reward and transition functions (whose transition kernels are not Lipschitz w.r.t. the total variation distance).

**Example 1** (Deterministic MDP in $\mathbb{R}^d$). Consider an MDP $\mathcal{M}$ with a finite action set, with a compact state space $\mathcal{X} \subset \mathbb{R}^d$, and deterministic transitions $y = f(x, a)$, i.e., $P_h(y|x, a) = \delta_{f(x,a)}(y)$. Let $\rho_X$ be the Euclidean distance on $\mathbb{R}^d$ and $\rho_A(a, a') = 0$ if $a = a'$ and $\infty$ otherwise. Then, if for all $a \in \mathcal{A}$, $x \mapsto r_h(x, a)$ and $x \mapsto f(x, a)$ are Lipschitz, $\mathcal{M}$ satisfies assumptions 1 and 2.

Under our assumptions, the optimal $Q$ functions are Lipschitz continuous:

**Lemma 1.** Let $L_h \stackrel{\text{def}}{=} \sum_{h'=h}^H \lambda_r \lambda_p^{H-h'}$. Under Assumption 2, for all $(x, a, x', a')$ and for all $h \in [H]$, we have $|Q_h^*(x, a) - Q_h^*(x', a')| \le L_h \rho[(x, a), (x', a')]|$, i.e., the optimal $Q$-functions are Lipschitz continuous.

**Algorithm 1 Kernel-UCBVI**

**Input:** global parameters $K, H, \delta, \lambda_r, \lambda_p, \sigma, \beta$

initialize data lists $\mathcal{D}_h = \emptyset$ for all $h \in [H]$

**for** episode $k = 1, \dots, K$ **do**

get initial state $x_1^k$

$$Q_h^k = \text{optimisticQ}(k, \{\mathcal{D}_h\}_{h \in [H]})$$

**for** step $h = 1, \dots, H$ **do**

execute $a_h^k = \operatorname*{argmax}_a Q_h^k(x_h^k, a)$

observe reward $r_h^k$ and next state $x_{h+1}^k$

add sample $(x_h^k, a_h^k, x_{h+1}^k, r_h^k)$ to $\mathcal{D}_h$

**end for**

**end for**

### 3. Algorithm

In this section, we present Kernel-UCBVI, a model-based algorithm for exploration in MDPs in metric spaces that employs kernel smoothing to estimate the rewards and transitions, for which we derive confidence intervals. Kernel-UCBVI uses exploration bonuses based on these confidence intervals to efficiently balance exploration and exploitation. Our algorithm requires the knowledge of the metric $\rho$ on $\mathcal{X} \times \mathcal{A}$ and of the Lipschitz constants of the rewards and transitions.<fnref n="2" />

#### 3.1. Kernel Function

We leverage the knowledge of the state-action space metric to define the kernel function. Let $u, v \in \mathcal{X} \times \mathcal{A}$. For some function $g: \mathbb{R}_{\ge 0} \to [0, 1]$, we define the kernel function as

$$\psi_{\sigma}(u, v) \stackrel{\text{def}}{=} g(\rho[u, v] / \sigma)$$

where $\sigma$ is the bandwidth parameter that controls the degree of “smoothing” of the kernel. In order to be able to construct valid confidence intervals, we require certain structural properties for $g$.

**Assumption 3.** The function $g: \mathbb{R}_{\ge 0} \to [0, 1]$ is differentiable, non-increasing, $g(4) > 0$, and there exists two constants $C_1^g, C_2^g > 0$ that depend only on $g$ such that

$$g(z) \le C_1^g \exp(-z^2/2) \text{ and } \sup_z |g'(z)| \le C_2^g.$$

This assumption is trivially verified by the Gaussian kernel $g(z) = \exp(-z^2/2)$. Other examples include the kernels $g(z) = \exp(-|z|^p/2)$ for $p > 2$.

<footnote n="2">²This assumption is standard in previous works in RL (e.g., Ortner & Ryabko, 2012; Sinclair et al., 2019). Theoretically, we could replace the Lipschitz constant $L_1$ by $\log k$, in each episode $k$, and our regret bound would have an additive term of order $He^{L_1}$, since $Q_h^k$ would be optimistic for $\log k \ge L_1$ (see e.g., Reeve et al., 2018). However, this would degrade the performance of the algorithm in practice.</footnote>
**Algorithm 2** optimisticQ

Input: episode k, data {$\mathcal{D}_h$}$_{h \in [H]}$

Initialize $V_{H+1}^k(x) = 0$ for all $x$

for step $h = H, \dots, 1$ do

// Compute optimistic targets

for $m = 1, \dots, k-1$ do

$$ \tilde{Q}_h^k(x_h^m, a_h^m) = \sum_{s=1}^{k-1} \tilde{w}_h^s(x_h^m, a_h^m) (r_h^s + V_{h+1}^k(x_{h+1}^s)) $$

$$ \tilde{Q}_h^k(x_h^m, a_h^m) = \tilde{Q}_h^k(x_h^m, a_h^m) + \mathbf{B}_h^k(x_h^m, a_h^m) $$

end for

// Interpolate the Q function

$$ Q_h^k(x, a) = \min_{s \in [k-1]} \left( \tilde{Q}_h^k(x_h^s, a_h^s) + L_h \rho [(x, a), (x_h^s, a_h^s)] \right) $$

for $m = 1, \dots, k-1$ do

$$ V_h^k(x_h^m) = \min (H - h + 1, \max_{a \in \mathcal{A}} Q_h^k(x_h^m, a)) $$

end for

end for

return $Q_h^k$

## 3.2. Kernel Estimators and Optimism

In each episode $k$, Kernel-UCBVI computes an optimistic estimate $Q_h^k$ for all $h$, which is an upper confidence bound on the optimal Q function $Q_h^*$, and plays the associated greedy policy. Let $(x_h^s, a_h^s, x_{h+1}^s, r_h^s)$ be the random variables representing the state, the action, the next state and the reward at step $h$ of episode $s$, respectively. We denote by $\mathcal{D}_h = \{(x_h^s, a_h^s, x_{h+1}^s, r_h^s)\}_{s \in [k-1]}$ for $h \in [H]$ the samples collected at step $h$ before episode $k$.

For any $(x, a)$ and $(s, h) \in [K] \times [H]$, we define the *weights* and the *normalized weights* as

$$ w_h^s(x, a) \stackrel{\text{def}}{=} \psi_{\sigma}((x, a), (x_h^s, a_h^s)) \quad \text{and} $$

$$ \tilde{w}_h^s(x, a) \stackrel{\text{def}}{=} \frac{w_h^s(x, a)}{\beta + \sum_{l=1}^{k-1} w_l^s(x, a)}, $$

where $\beta > 0$ is a regularization term. These weights are used to compute an estimate of the rewards and transitions for each state-action pair<fnref n="3" />:

$$ \hat{r}_h^k(x, a) \stackrel{\text{def}}{=} \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) r_h^s, $$

$$ \hat{P}_h^k(y|x, a) \stackrel{\text{def}}{=} \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) \delta_{x_{h+1}^s}(y). $$

As other algorithms using OFU, Kernel-UCBVI computes an optimistic Q-function $\tilde{Q}_h^k$ through value iteration, a.k.a. backward induction:

$$ \tilde{Q}_h^k(x, a) = \hat{r}_h^k(x, a) + \hat{P}_h^k V_{h+1}^k(x, a) + \mathbf{B}_h^k(x, a) \quad (1) $$

where $V_{H+1}^k(x) = 0$ for all $x \in \mathcal{X}$ and $\mathbf{B}_h^k(x, a)$ is an exploration bonus described later. From Lemma 1, the

true Q function $Q_h^*$ is $L_h$-Lipschitz. Computing $\tilde{Q}_h^k$ for all previously visited state action pairs $(x_h^s, a_h^s)$ for $s \in [k-1]$ permits to define a $L_h$-Lipschitz upper confidence bound and the associated value function:

$$ Q_h^k(x, a) \stackrel{\text{def}}{=} \min_{s \in [k-1]} \left( \tilde{Q}_h^k(x_h^s, a_h^s) + L_h \rho [(x, a), (x_h^s, a_h^s)] \right) $$

and $V_h^k(x) \stackrel{\text{def}}{=} \min (H - h + 1, \max_{a'} Q_h^k(x, a'))$. The policy $\pi_k$ executed by Kernel-UCBVI is the greedy policy with respect to $Q_h^k$ (see Alg. 1).

Let $\mathbf{C}_h^k(x, a) \stackrel{\text{def}}{=} \beta + \sum_{s=1}^{k-1} w_h^s(x, a)$ be the generalized counts, which are a proxy for the number of visits to $(x, a)$. The exploration bonus is defined based on the uncertainties on the transition and reward estimates and takes the form

$$ \mathbf{B}_h^k(x, a) \approx \frac{H}{\sqrt{\mathbf{C}_h^k(x, a)}} + \frac{\beta H}{\mathbf{C}_h^k(x, a)} + L_1 \sigma $$

where we omit constants and logarithmic terms. Refer to Eq. 4 in App. B for the exact definition.

## 4. Theoretical Guarantees & Discussion

The theorem below gives a high probability regret bound for Kernel-UCBVI. It features the $\sigma$-covering number of the state-action space. The $\sigma$-covering number of a metric space, formally defined in Def. 2 (App. A), is roughly the number of $\sigma$-radius balls required to cover the entire space. The covering dimension of a space is the smallest number $d$ such that its $\sigma$-covering number is $O(\sigma^{-d})$. For instance, the covering number of a ball in $\mathbb{R}^d$ with the Euclidean distance is $O(\sigma^{-d})$ and its covering dimension is $d$.

**Theorem 1.** With probability at least $1 - \delta$, the regret of Kernel-UCBVI for a bandwidth $\sigma$ satisfies

$$ \mathcal{R}(K) \le \tilde{\mathcal{O}} \left( H^2 \sqrt{|\mathcal{C}_\sigma| K} + L_1 K H \sigma + H^3 |\mathcal{C}_\sigma| |\tilde{\mathcal{C}}_\sigma| \right), $$

where $|\mathcal{C}_\sigma|$ and $|\tilde{\mathcal{C}}_\sigma|$ are the $\sigma$-covering numbers of $(\mathcal{X} \times A, \rho)$ and $(\mathcal{X}, \rho_\mathcal{X})$, respectively, and $L_1$ is the Lipschitz constant of the optimal Q-functions.

*Proof.* Restatement of Theorem 4 in App. D. A proof sketch is given in Section 6. $\square$

**Corollary 1.** By taking $\sigma = (1/K)^{1/(2d+1)}$, $\mathcal{R}(K) = \tilde{\mathcal{O}}(H^3 K^{\max(\frac{1}{2}, \frac{2d}{2d+1})})$, where $d$ is the covering dimension of the state-action space.

**Remark 1.** As for other model-based algorithms, the dependence on $H$ can be improved if the transitions are stationary, i.e., do not depend on $h$. In this case, the regret of Kernel-UCBVI becomes $\tilde{\mathcal{O}}(H^2 K^{\frac{2d}{2d+1}})$ due to a gain a factor of $H$ in the second order term (see App. E).

<footnote n="3">³Here, $\delta_x$ denotes the Dirac measure with mass at $x$.</footnote>
To the best of our knowledge, this is the first regret bound for kernel-based RL using smoothing kernels, and we present below further discussions on this result.

**Comparison to lower bound for Lipschitz MDPs** In terms of the number of episodes *K* and the dimension *d*, the lower bound for Lipschitz MDPs is $\Omega(K^{(d+1)/(d+2)})$, which is a consequence of the result for contextual Lipschitz bandits (Slivkins, 2014). In terms of *H*, the optimal dependence can be conjectured to be $H^{3/2}$, which is the case for tabular MDPs (Jin et al., 2018).<fnref n="4" /> For *d* = 1, our bound has an optimal dependence on *K*, leading to a regret of order $\tilde{O}(H^3 K^{2/3})$, or $\tilde{O}(H^2 K^{2/3})$ when the transitions are stationary (see Remark 1).

**Comparison to other upper bounds for Lipschitz MDPs**
The best available upper bound in this setting, in terms of *K* and *d*, is $\Omega(H^{5/2} K^{d+1/(d+2)})$, which is achieved by model-free algorithms performing either uniform or adaptive discretization of the state-action space (Song & Sun, 2019; Sinclair et al., 2019; Touati et al., 2020).

**Relevance of a kernel-based algorithm** Although our upper bound does not match the lower bound for Lipschitz MDPs, kernel-based RL can be a very useful tool in practice to handle the bias-variance trade-off in RL. It allows us to easily provide expert knowledge to the algorithm through kernel design, which can be seen as introducing more bias to reduce the variance of the algorithm and, consequently, improve the learning speed. As shown by Kveton & Theocharous (2012) and Barreto et al. (2016), KBRL are empirically successful in medium-scale tasks ($d \approx 10$), such as control problems, HIV drug scheduling and an epilepsy suppression task. In such problems, Kernel-UCBVI can be used to enhance exploration, and the confidence intervals we derive here may also be useful in settings such as robust planning (Lim & Autef, 2019). Interestingly, Badia et al. (2020) have shown that kernel-based exploration bonuses similar to the ones derived in this paper can improve exploration in Atari games.

**Regularity assumptions** The regret bound we provide only requires only weak assumptions on the MDP: we assume that both the transitions and rewards are Lipschitz continuous, but we have no constraints on the behavior of the Bellman operator. As a consequence, the regret bounds suffer from the curse of dimensionality: as *d* goes to infinity, both the lower and upper bounds become linear in the number of episodes *K*. Other settings, such as low-rank MDPs (Jin et al., 2020) and RKHS approximations (Yang et al., 2020; Chowdhury & Oliveira, 2020) achieve regret bounds scaling with $\sqrt{K}$, but they require much stronger assumptions

on the MDP, such as the closedness of the Bellman operator in the function class used to represent *Q* functions, which is a condition that is much harder to verify. Barreto et al. (2016) show that KBRL (with smoothing kernels) can be related to low-rank MDPs, and we believe that our analysis brings new elements to study this trade-off that exists between regularity assumptions and regret bounds.

**Model-free vs. Model-based** An interesting remark comes from the comparison between our algorithm and recent model-free approaches in continuous MDPs (Song & Sun, 2019; Sinclair et al., 2019; Touati et al., 2020). These algorithms are based on optimistic Q-learning (Jin et al., 2018), to which we refer as OptQL, and achieve a regret of order $\tilde{O}(H^{5/2} K^{d+1/(d+2)})$, which has an optimal dependence on *K* and *d*. While we achieve the same $\tilde{O}(K^{2/3})$ regret when *d* = 1, our bound is slightly worse for *d* > 1. To understand this gap, it is enlightening to look at the regret bound for tabular MDPs.

Since our algorithm is inspired by UCBVI (Azar et al., 2017) with Chernoff-Hoeffding bonus, we compare it to OptQL, which is used by (Song & Sun, 2019; Sinclair et al., 2019; Touati et al., 2020), with the same kind of exploration bonus. Consider an MDP with *X* states and *A* actions and non-stationary transitions. UCBVI has a regret bound of $\tilde{O}(H^2\sqrt{XAK} + H^3X^2A)$ while OptQL has $\tilde{O}(H^{5/2}\sqrt{XAK} + H^2XA)$. As we can see, OptQL is a $\sqrt{H}$-factor worse than UCBVI when comparing the first-order term, but it is $HX$ times better in the second-order term. For large values of *K*, second-order terms can be neglected in the comparison of the algorithms in tabular MDPs, since they do not depend on *K*. However, they play an important role in continuous MDPs, where *X* and *A* are replaced by the $\sigma$-covering number of the state-action space, which is roughly $1/\sigma^d$. In tabular MDPs, the second-order term is constant (i.e., does not depend on *K*). On the other hand, in continuous MDPs, the algorithms define the granularity of the representation of the state-action space based on the number of episodes, connecting the number of states *X* with *K*. For example, in (Song & Sun, 2019) the $\epsilon$-net used by the algorithm is tuned such that $\epsilon = (HK)^{-1/(d+2)}$ (see also Ortner & Ryabko 2012; Lakshmanan et al. 2015; Jian et al. 2019). Similarly, in our algorithm we have that $\sigma = K^{-1/(2d+1)}$. For this reason, the second-order term in UCBVI becomes the dominant term in our analysis, leading to a worse dependence on *d* compared to model-free algorithms, as highlighted in the proof sketch (Sec. 6). For similar reasons, Kernel-UCBVI has an additional $\sqrt{H}$ factor compared to model-free algorithms based on (Jin et al., 2018). This shows that the direction of achieving first-order optimal terms at the expense of higher second-order terms may not be justified outside the tabular case. Whether this

<footnote n="4">⁴See also (Sinclair et al., 2019, Sec. 4.4).</footnote>
is a flaw in the algorithm design or in the analysis is left as an open question. However, as observed in Section 7, model-based algorithms seem to enjoy a better empirical performance.

## 5. Improving the Computational Complexity

Kernel-UCBVI is a non-parametric model-based algorithm and, consequently, it inherits the weaknesses of these approaches. In order to be data adaptive, it needs to store all the samples $(x_h^k, a_h^k, x_{h+1}^k, r_h^k)$ and their optimistic values $\tilde{Q}_h^k$ and $V_h^k$ for $(k, h) \in [K] \times [H]$, leading to a total memory complexity of $O(HK)$. Like standard model-based algorithms, it needs to perform planning at each episode which gives a total runtime of $O(HAK^3)^5$, where the factor A takes into account the complexity of computing the maximum over actions.<fnref n="6" /> Kernel-UCBVI has similar time and space complexity of recent approaches for low-rank MDPs (Jin et al., 2020; Zanette et al., 2019).

To alleviate the computational burden of Kernel-UCBVI, we leverage Real-Time Dynamic Programming (RTDP), see (Barto et al., 1995), to perform incremental planning. Similarly to OptQL, RTDP-like algorithms maintain an optimistic estimate of the optimal value function that is updated incrementally by interacting with the MDP. The main difference is that the update is done by using an estimate of the MDP (i.e., model-based) rather than the observed transition sample. In episode k and step h, our algorithm, named Greedy-Kernel-UCBVI, computes an upper bound $\tilde{Q}_h^k(x_h^k, a)$ for each action a using the kernel estimate as in Eq. (1). Then, it executes the greedy action $a_h^k = \operatorname*{argmax}_{a \in A} \tilde{Q}_h^k(x_h^k, a)$. As a next step, it computes $\tilde{V}_h^k(x_h^k) = \tilde{Q}_h^k(x_h^k, a_h^k)$ and refines the previous $L_h$-Lipschitz upper confidence bound on the value function

$$V_h^{k+1}(x) = \min \left( (V_h^k(x), \tilde{V}_h^k(x_h^k) + L_h \rho_x(x, x_h^k)) \right).$$

The complete description of Greedy-Kernel-UCBVI is given in Alg. 3 in App. F. The total runtime of this efficient version is $O(HAK^2)$ with total memory complexity of $O(HK)$.

RTDP has been recently analyzed by (Efroni et al., 2019) in tabular MDPs. Following their analysis, we prove the following theorem, which shows that Greedy-Kernel-UCBVI achieves the same guarantees of Kernel-UCBVI with a

large improvement in computational complexity.

**Theorem 2.** With probability at least $1 - \delta$, the regret of Greedy-Kernel-UCBVI for a bandwidth $\sigma$ is of order $R(K) = \tilde{O}(R(K, \text{Kernel} - \text{UCBVI}) + H^2|\tilde{C}_\sigma|)$, where $|\tilde{C}_\sigma|$ is the $\sigma$-covering number of state space. This results in a regret of $\tilde{O}(H^3 K^{2d/(2d+1)})$ when $\sigma = (1/K)^{1/(2d+1)}$.

*Proof.* The complete proof is provided in App. F. The key properties for proving this regret bound are: (i) optimism, and (ii) the fact that $(V_h^k)$ are point-wise non-increasing.

Besides RTDP, other techniques previously proposed to accelerate KBRL can also be applied, notably the use of representative states (Kveton & Theocharous, 2012; Barreto et al., 2016) that merge states that are close to each other to avoid a per-episode runtime that increases with $k$.

## 6. Proof sketch

We now provide a sketch of the proof of our main result, Theorem 1. The complete proof is given in the Appendix. The analysis splits into three parts: (i) deriving confidence intervals for the reward and transition kernel estimators; (ii) proving that the algorithm is optimistic, i.e., that $V_h^k(x) \ge V_h^*(x)$ for any $(x, k, h)$ on a high probability event $G$; and (iii) proving an upper bound on the regret by using the fact that $R(K) = \sum_k (V_1^*(x_1^k) - V_1^{\pi_k}(x_1^k)) \le \sum_k (V_1^k(x_1^k) - V_1^{\pi_k}(x_1^k))$.

### 6.1. Concentration

The most interesting part is the concentration of the transition kernel. Since $\tilde{P}_h^k(\cdot|x, a)$ are weighted sums of Dirac measures, we cannot bound the distance between $P_h(\cdot|x, a)$ and $\tilde{P}_h^k(\cdot|x, a)$ directly. Instead, for $V_{h+1}^*$ the optimal value function at step $h+1$, we bound the difference

$$ \begin{aligned} & |(\tilde{P}_h^k - P_h)V_{h+1}^*(x, a)| \\ &= \left| \sum_{s=1}^{k-1} \tilde{w}_s^h(x, a)V_{h+1}^*(x_{h+1}^s) - P_h V_{h+1}^*(x, a) \right| \\ &\le \underbrace{\left| \sum_{s=1}^{k-1} \tilde{w}_s^h(x, a)(V_{h+1}^*(x_{h+1}^s) - P_h V_{h+1}^*(x_h^s, a_h^s)) \right|}_{(\mathbf{A})} \\ &\quad + \lambda_p L_{h+1} \sum_{s=1}^{k-1} \tilde{w}_s^h(x, a) \rho[(x, a), (x_h^s, a_h^s)] + \underbrace{\frac{\beta \|V_{h+1}^*\|_{\infty}}{C_h^k(x, a)}}_{(\mathbf{C})}. \end{aligned} $$

The term $(\mathbf{A})$ is a weighted sum of a martingale difference sequence. To control it, we propose a new Hoeffding-type inequality, Lemma 2, that applies to weighted sums with random weights. The term $(\mathbf{B})$ is a bias term that is ob-

<footnote n="5">⁵Since the runtime of an episode k is $O(HAk^2)$.</footnote>

<footnote n="6">⁶While in theory the algorithm works with a compact action space, the main practical issue resides in the computation of the best action (i.e., $a_h^k = \operatorname*{argmax}_a Q_h^k(x_h^k, a)$). In this case, we could resort to black box optimization algorithms (e.g., Munos, 2014, Sec. 3.3), which might require the discretization of the action space. This is however less critical than the discretization of the state-space, since the possible actions must always be known in advance, unlike the set of possible states.</footnote>
tained using the fact that $V_{h+1}^* = L_{h+1}$-Lipschitz and that the transition kernel is $\lambda_p$-Lipschitz, and can be shown to be proportional to the bandwidth $\sigma$ under Assumption 3 (Lemma 7). The term (C) is the bias introduced by the regularization parameter $\beta$. Hence, for a fixed state-action pair $(x, a)$, we show that$^7$, with high-probability,

$$|(\hat{P}_h^k - P_h)V_{h+1}^*(x, a)| \lesssim \frac{H}{\sqrt{\mathbf{C}_h^k(x, a)}} + \frac{\beta H}{\mathbf{C}_h^k(x, a)} + L_1\sigma.$$

Then, we extend this bound to all $(x, a)$ by leveraging the continuity of all the terms involving $(x, a)$ and a covering argument. This continuity is a consequence of kernel smoothing, and it is a key point in avoiding a discretization of $\mathcal{X} \times \mathcal{A}$ in the algorithm.

In Theorem 3, we define a favorable event $\mathcal{G}$, of probability larger than $1 - \delta/2$, in which (a more precise version of) the above inequality holds, the mean rewards belong to their confidence intervals, and we further control the deviations of $(\hat{P}_h^k - P_h)f(x, a)$ for any $2L_1$-Lipschitz function $f$. This last part is obtained thanks to a new Bernstein-like concentration inequality for weighted sums (Lemma 3).

## 6.2. Optimism

To prove that the optimistic value function $V_h^k$ is indeed an upper bound on $V_h^*$, we proceed by induction on $h$ and we use the $Q$ functions. When $h = H + 1$, we have $Q_{H+1}^k(x, a) = Q_{H+1}^*(x, a) = 0$ for all $(x, a)$, by definition. Assuming that $Q_{h+1}^k(x, a) \ge Q_{h+1}^*(x, a)$ for all $(x, a)$, we have $V_{h+1}^k(x) \ge V_{h+1}^*(x)$ for all $x$. Then, the bonuses are defined so that $\tilde{Q}_h^k(x, a) \ge Q_h^*(x, a)$ for all $(x, a)$, on the event $\mathcal{G}$.

In particular $\tilde{Q}_h^k(x_h^s, a_h^s) - Q_h^*(x_h^s, a_h^s) \ge 0$ for all $s \in [k-1]$, which gives us

$$\tilde{Q}_h^k(x_h^s, a_h^s) + L_h \rho [(x, a), (x_h^s, a_h^s)] \\ \ge Q_h^*(x_h^s, a_h^s) + L_h \rho [(x, a), (x_h^s, a_h^s)] \ge Q_h^*(x, a)$$

for all $s \in [k-1]$, since $Q_h^*$ is $L_h$-Lipschitz. It follows from the definition of $Q_h^k$ that $Q_h^k(x, a) \ge Q_h^*(s, a)$, which in turn implies that, for all $x$, $V_h^k(x) \ge V_h^*(x)$ in $\mathcal{G}$.

## 6.3. Bounding the regret

To provide an upper bound on the regret in the event $\mathcal{G}$, let $\delta_h^k \stackrel{\text{def}}{=} V_h^k(x_h^k) - V_h^{\pi_k}(x_h^k)$. The fact that $V_h^k \ge V_h^*$ gives us $\mathcal{R}(K) \le \sum_k \delta_1^k$. Introducing $(\tilde{x}_h^k, \tilde{a}_h^k)$, the state-action pair in the past data $\mathcal{D}_h$ that is the closest to $(x_h^k, a_h^k)$ and letting $\square_h^k = \rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)]$, we bound $\delta_h^k$ using the

following decomposition:

$$\begin{aligned} \delta_h^k &\le Q_h^k(x_h^k, a_h^k) - Q_h^{\pi_k}(x_h^k, a_h^k) \\ &\le \tilde{Q}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - Q_h^{\pi_k}(x_h^k, a_h^k) + L_h \square_h^k \\ &\le 2 \mathbf{B}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) + (L_h + \lambda_p L_h + \lambda_r) \square_h^k \\ &\quad + (\hat{P}_h^k - P_h) V_{h+1}^*(\tilde{x}_h^k, \tilde{a}_h^k) \quad (1) \\ &\quad + P_h (V_{h+1}^k - V_{h+1}^{\pi_k}) (x_h^k, a_h^k) \quad (2) \\ &\quad + (\hat{P}_h^k - P_h) (V_{h+1}^k - V_{h+1}^{*}) (\tilde{x}_h^k, \tilde{a}_h^k) \quad (3). \end{aligned}$$

The term (1) is shown to be smaller than $\mathbf{B}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)$, by definition of the bonus. The term (2) can be rewritten as $\delta_{h+1}^k$ plus a martingale difference sequence $\xi_{h+1}^k$. To bound the term (3), we use that $V_{h+1}^k - V_{h+1}^* = 2L_1$-Lipschitz. The uniform deviations that hold on event $\mathcal{G}$ yield

$$\textcircled{3} \quad \frac{1}{H} (\delta_{h+1}^k + \xi_{h+1}^k) + \frac{H^2 |\tilde{C}_\sigma|}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} + L_1 \square_h^k + L_1 \sigma.$$

When $\square_h^k > 2\sigma$, we bound $\delta_h^k$ by $H$ and we verify that $H \sum_{h=1}^H \sum_{k=1}^K \mathbb{I}\{\square_h^k > 2\sigma\} \le H^2 |\tilde{C}_\sigma|$ by a pigeonhole argument. Hence, we can focus on the case where $\square_h^k \le 2\sigma$, and add $H^2 |\tilde{C}_\sigma|$ to the regret bound, to take into account the steps $(k, h)$ where $\square_h^k > 2\sigma$. The sum of $\xi_{h+1}^k$ over $(k, h)$ is bounded by $\tilde{\mathcal{O}}(H^{3/2} \sqrt{K})$ by Hoeffding-Azuma's inequality, on some event $\mathcal{F}$ of probability larger than $1 - \delta/2$. Now, we focus on the case where $\square_h^k \le 2\sigma$ and we omit the terms involving $\xi_{h+1}^k$. Using the definition of the bonus, we obtain

$$\delta_h^k \lesssim \left(1 + \frac{1}{H}\right) \delta_{h+1}^k + \frac{H}{\sqrt{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} + \frac{H^2 |\tilde{C}_\sigma|}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} + L_1 \sigma.$$

Using the fact that $(1 + 1/H)^H \le e$, we have, on $\mathcal{G} \cap \mathcal{F}$,

$$\mathcal{R}(K) \lesssim \sum_{h,k} \left( \frac{H}{\sqrt{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} + \frac{H^2 |\tilde{C}_\sigma|}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} \right) + L_1 K H \sigma.$$

The term in $1/\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)$ is the second order term (in $K$).

In the tabular case, it is multiplied by the number of states. Here, it is multiplied by the covering number of the state space $|\tilde{C}_\sigma|$.

From there it remains to bound the sum of the first and second-order terms, and we specifically show that

$$\sum_{h,k} \frac{1}{\sqrt{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} \lesssim H \sqrt{|\tilde{C}_\sigma| K} \quad (2)$$

$$\text{and} \quad \sum_{h,k} \frac{1}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} \lesssim H |\tilde{C}_\sigma| \log K, \quad (3)$$

where we note that (3) has a worse dependence on $|\tilde{C}_\sigma|$. As mentioned before, unlike in the tabular case the sum of

<footnote>$^7$Here, $\lesssim$ means smaller than or equal up to logarithmic terms.</footnote>
“second-order” terms will actually be the leading term, since the choice of σ that minimizes the regret depends on K.

Finally, we obtain that on $G \cap F$ (of probability $\ge 1 - \delta$)

$$ \mathcal{R}(K) \lesssim H^2 \sqrt{|C_{\sigma}|K} + H^3|C_{\sigma}||\tilde{C}_{\sigma}| + L_1KH\sigma + H^2|C_{\sigma}|, $$

where the extra $H^2|C_{\sigma}|$ takes into account the episodes where $\square_h^k > 2\sigma$.

If the transitions kernels are stationary, i.e., $P_1 = \dots = P_H$, the bounds (2) and (3) can be improved to $\sqrt{|C_{\sigma}|KH}$ and $|C_{\sigma}|\log(KH)$ respectively, thus improving the final scaling in $H$.<fnref n="8" /> See App. E for details.

## 7. Experiments

To illustrate experimentally the properties of Kernel-UCBVI, we consider a Grid-World environment with continuous states. This Grid-World is composed of two rooms separated by a wall, such that $\chi = ([0, 1-\Delta] \cup [1+\Delta, 2]) \times [0, 1]$ where $2\Delta = 0.1$ is the width of the wall, as illustrated by Figure 1. There are four actions: left, right, up, and down, each one resulting to a displacement of 0.1 in the corresponding direction. A two-dimensional Gaussian noise is added to the transitions, and, in each room, there is a single region with non-zero reward. The agent has 0.5 probability of starting in each of the rooms, and the starting position is at the room’s bottom left corner.

We compare Kernel-UCBVI and Greedy-Kernel-UCBVI to the following baselines: (i) UCBVI (Azar et al., 2017) using a uniform discretization of the state-space; (ii) OptQL (Jin et al., 2018) also on a uniform discretization; (iii) Adaptive-Q-Learning (Sinclair et al., 2019) that uses an adaptive discretization of the state-space. We used the Euclidean distance and the Gaussian kernel with a fixed bandwidth $\sigma = 0.025$, matching the granularity of the uniform discretization used by some of the baselines. We also implemented a version of Kernel-UCBVI using the “expert knowledge” that the two rooms are equivalent under translation, by using a metric that is invariant with respect to the change of rooms. More details about the experimental setup are provided in Appendix I.<fnref n="9" />

We ran the algorithms for $5 \times 10^4$ episodes, and Figure 2 shows the sum of rewards obtained by each of them. When the curves start behaving as a straight line, it roughly means that the algorithm has converged to a policy whose value is the slope of the line. We see that Kernel-UCBVI is able to outperform the baselines, and that the use of expert knowledge in the kernel design can considerably increase

<figure><img src="image_2.png" /><figcaption>Figure 1. Continuous grid-world with two rooms separated by a wall. The circles represent the regions with non-zero rewards.</figcaption></figure>

the learning speed. Asymptotically, the extra bias introduced by the kernel (especially its bandwidth) might make Kernel-UCBVI converge to a worse policy at the end: the kernel bandwidth and the discretization width are comparable, but the Gaussian kernel introduces more bias due to sample aggregation. On the other hand, we see that introducing more bias can greatly improve the learning speed in the beginning, especially when expert knowledge is used. This flexibility in handling the bias-variance trade-off is one of the strengths of kernel-based approaches.

<figure><img src="image_3.png" /><figcaption>Figure 2. Total sum of rewards obtained by Kernel-UCBVI and baselines versus the number of episodes. Average over 8 runs.</figcaption></figure>

## 8. Conclusion

In this paper, we introduced Kernel-UCBVI, a model-based algorithm for finite-horizon reinforcement learning in metric spaces which employs kernel smoothing to estimate rewards and transitions. By providing new high-probability confidence intervals for weighted sums and non-parametric kernel estimators, we generalize the techniques introduced by (Azar et al., 2017) in tabular MDPs to the continuous setting. We prove that the regret of Kernel-UCBVI is of order $H^3K^{-\max(\frac{1}{2}, \frac{2d}{2d+1})}$, which is the first regret bound for kernel-based RL using smoothing kernels. In addition, we provide experiments illustrating the effectiveness of Kernel-UCBVI in handling the bias-variance trade-off and in the use of expert knowledge. Interesting directions for future work include the use of learned metrics (e.g., using neural networks) and the use of adaptive kernel bandwidths to better handle the bias-variance trade-off asymptotically.

<footnote n="8">⁸This is because, in the non-stationary case, we bound the sums over $k$ and then multiply the resulting bound by $H$. In the stationary case, we can directly bound the sums over $(k, h)$.</footnote>

<footnote n="9">⁹Implementations of Kernel-UCBVI are available on GitHub, and use the `rlberry` library (Domingues et al., 2021).</footnote>
Acknowledgements

At Inria and CNRS, this work was supported by the Eu-
ropean CHIST-ERA project DELTA, French Ministry of
Higher Education and Research, Nord-Pas-de-Calais Re-
gional Council, French National Research Agency project
BOLD (ANR19-CE23-0026-04), FMJH PGMO project
2018-0045. Pierre Ménard is supported by the SFI Sachsen-
Anhalt for the project RE-BCI ZS/2019/10/102024 by the
Investitionsbank Sachsen-Anhalt.

References

Abbasi-Yadkori, Y. and Szepesvári, C. Regret bounds for the adaptive control of linear quadratic systems. In *Proceedings of the 24th Annual Conference on Learning Theory*, pp. 1–26, 2011.

Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. In *Advances in Neural Information Processing Systems*, pp. 2312–2320, 2011.

Azar, M. G., Osband, I., and Munos, R. Minimax regret bounds for reinforcement learning. In *Proceedings of the 34th International Conference on Machine Learning-Volume 70*, pp. 263–272. JMLR. org, 2017.

Badia, A. P., Sprechmann, P., Vitvitskyi, A., Guo, D., Piot, B., Kapturowski, S., Tieleman, O., Arjovsky, M., Pritzel, A., Bolt, A., et al. Never give up: Learning directed exploration strategies. *arXiv preprint arXiv:2002.06038*, 2020.

Barreto, A. M., Precup, D., and Pineau, J. Practical kernel-
based reinforcement learning. *The Journal of Machine
Learning Research*, 17(1):2372–2441, 2016.

Barto, A. G., Bradtke, S. J., and Singh, S. P. Learning to act using real-time dynamic programming. *Artificial intelligence*, 72(1-2):81–138, 1995.

Boucheron, S., Lugosi, G., and Massart, P. *Concentration inequalities: A nonasymptotic theory of independence*. Oxford university press, 2013.

Burnetas, A. N. and Katehakis, M. N. Optimal adaptive policies for Markov decision processes. *Mathematics of Operations Research*, 22(1):222–255, feb 1997. ISSN 0364-765X.

Chowdhury, S. R. and Gopalan, A. Online learning in kernelized markov decision processes. In *Proceedings of Machine Learning Research*, volume 89, 2019.

Chowdhury, S. R. and Oliveira, R. No-regret reinforcement learning with value function approximation: a kernel embedding approach. *arXiv preprint arXiv:2011.07881*, 2020.

Combes, R., Magureanu, S., and Proutiere, A. Minimal exploration in structured stochastic bandits. In *Advances in Neural Information Processing Systems*, pp. 1763–1771, 2017.

Domingues, O. D., Flet-Berliac, Y., Leurent, E., Ménard, P., Shang, X., and Valko, M. rlberry - A Reinforcement Learning Library for Research and Education. https://github.com/rlberry-py/rlberry, 2021.

Efroni, Y., Merlis, N., Ghavamzadeh, M., and Mannor, S. Tight regret bounds for model-based reinforcement learning with greedy policies. In *Advances in Neural Information Processing Systems*, pp. 12203–12213, 2019.

Gottlieb, L.-A., Kontorovich, A., and Krauthgamer, R. Ef-
ficient regression in metric spaces via approximate lips-
chitz extension. *IEEE Transactions on Information The-
ory*, 63(8):4838–4849, 2017.

Jaksch, T., Ortner, R., and Auer, P. Near-optimal regret bounds for reinforcement learning. *Journal of Machine Learning Research*, 11(Apr):1563–1600, 2010.

Jian, Q., Fruit, R., Pirotta, M., and Lazaric, A. Exploration bonus for regret minimization in discrete and continuous average reward mdps. In *Advances in Neural Information Processing Systems*, pp. 4891–4900, 2019.

Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. Is q-learning provably efficient? In *Advances in Neural Information Processing Systems*, pp. 4863–4873, 2018.

Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. Provably efficient reinforcement learning with linear function approximation. In *Conference on Learning Theory (COLT)*, 2020.

Kakade, S., Kearns, M. J., and Langford, J. Exploration in metric state spaces. In *Proceedings of the 20th International Conference on Machine Learning (ICML-03)*, pp. 306–312, 2003.

Kearns, M. and Singh, S. Near-optimal reinforcement learning in polynomial time. *Machine learning*, 49(2-3):209–232, 2002.

Kveton, B. and Theocharous, G. Kernel-based reinforce-
ment learning on representative states. In *Twenty-Sixth
AAAI Conference on Artificial Intelligence*, 2012.

Lakshmanan, K., Ortner, R., and Ryabko, D. Improved regret bounds for undiscounted continuous reinforcement learning. In *International Conference on Machine Learning*, pp. 524–532, 2015.
Lattimore, T., Hutter, M., Sunehag, P., et al. The sample-complexity of general reinforcement learning. In *Proceedings of the 30th International Conference on Machine Learning*. Journal of Machine Learning Research, 2013.

Lim, S. H. and Autef, A. Kernel-based reinforcement learning in robust markov decision processes. In *Proceedings of the 36th International Conference on Machine Learning*, (ICML), 2019.

Munos, R. From bandits to monte-carlo tree search: The optimistic principle applied to optimization and planning. *Found. Trends Mach. Learn.*, 7(1):1–129, 2014.

Ni, C., Yang, L. F., and Wang, M. Learning to control in metric space with optimal regret. In *2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton)*, pp. 726–733. IEEE, 2019.

Ok, J., Proutiere, A., and Tranos, D. Exploration in structured reinforcement learning. In *Advances in Neural Information Processing Systems*, pp. 8874–8882, 2018.

Ormoneit, D. and Sen, S. Kernel-based reinforcement learning. *Machine learning*, 49(2-3):161–178, 2002.

Ortner, R. and Ryabko, D. Online regret bounds for undiscounted continuous reinforcement learning. In *Advances in Neural Information Processing Systems*, pp. 1763–1771, 2012.

Osband, I. and Van Roy, B. Model-based reinforcement learning and the eluder dimension. In *Advances in Neural Information Processing Systems*, pp. 1466–1474, 2014.

Osband, I., Russo, D., and Van Roy, B. (more) efficient reinforcement learning via posterior sampling. In *Advances in Neural Information Processing Systems*, pp. 3003–3011, 2013.

Pazis, J. and Parr, R. Pac optimal exploration in continuous space markov decision processes. In *Twenty-Seventh AAAI Conference on Artificial Intelligence*, 2013.

Peña, V. H., Lai, T. L., and Shao, Q.-M. *Self-normalized processes: Limit theory and Statistical Applications*. Springer Science & Business Media, 2008.

Puterman, M. L. *Markov Decision Processes: Discrete Stochastic Dynamic Programming*. John Wiley and Sons, Inc., New York, NY, USA, 1994. ISBN 0471619779.

Reeve, H. W. J., Mellor, J., and Brown, G. The k-nearest neighbour UCB algorithm for multi-armed bandits with covariates. In *ALT*, volume 83 of *Proceedings of Machine Learning Research*, pp. 725–752. PMLR, 2018.

Sinclair, S. R., Banerjee, S., and Yu, C. L. Adaptive discretization for episodic reinforcement learning in metric spaces. *Proceedings of the ACM on Measurement and Analysis of Computing Systems*, 3(3):1–44, 2019.

Slivkins, A. Contextual bandits with similarity information. *Journal of Machine Learning Research*, 15(1):2533–2568, 2014.

Song, Z. and Sun, W. Efficient model-free reinforcement learning in metric spaces. *arXiv preprint arXiv:1905.00475*, 2019.

Strens, M. A bayesian framework for reinforcement learning. In *ICML*, volume 2000, pp. 943–950, 2000.

Touati, A., Taiga, A. A., and Bellemare, M. G. Zooming for Efficient Model-Free Reinforcement Learning in Metric Spaces. *arXiv e-prints*, art. arXiv:2003.04069, March 2020.

Yang, L. F. and Wang, M. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In *International Conference on Machine Learning (ICML)*, 2020.

Yang, Z., Jin, C., Wang, Z., Wang, M., and Jordan, M. Provably efficient reinforcement learning with kernel and neural function approximations. *Advances in Neural Information Processing Systems*, 33, 2020.

Zanette, A. and Brunskill, E. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In *Proceedings of the 36th International Conference on Machine Learning*, 2019.

Zanette, A., Brandfonbrener, D., Pirotta, M., and Lazaric, A. Frequentist regret bounds for randomized least-squares value iteration. *CoRR*, abs/1911.00567, 2019.
# A. Notation and preliminaries

## A.1. Notation

Table 1 presents the main notations used in the proofs. Also, we use the symbol $\lesssim$ with the following meaning:

$$A \lesssim B \iff A \leq B \times \text{polynomial}(\log(k), \log(1/\delta), \lambda_r, \lambda_p, \beta, d_1, d_2).$$

<table><caption>Table 1. Table of notations</caption><thead><tr><th>Notation</th><th>Meaning</th></tr></thead><tbody><tr><td>ρ : (X × A)<sup>2</sup> → ℝ<sub>+</sub></td><td>metric on the state-action space X × A</td></tr><tr><td>ψ<sub>σ</sub>((x, a), (x', a'))</td><td>kernel function with bandwidth σ</td></tr><tr><td>g : ℝ<sub>+</sub> → [0, 1]</td><td>"mother" kernel function such that ψ<sub>σ</sub>(u, v) = g(ρ[u, v] /σ)</td></tr><tr><td>C<sub>1</sub><sup>g</sup>, C<sub>2</sub><sup>g</sup></td><td>positive constants that depend on g (Assumption 3)</td></tr><tr><td>N(ε, X × A, ρ)</td><td>ε-covering number of the metric space (X × A, ρ)</td></tr><tr><td>G</td><td>"good" event (see Theorem 3)</td></tr><tr><td>λ<sub>r</sub>, λ<sub>p</sub></td><td>Lipschitz constants of rewards and transitions, respectively</td></tr><tr><td>L<sub>h</sub>, for h ∈ [H]</td><td>Lipschitz constant of value functions (see Lemma 4)</td></tr><tr><td>log<sup>+</sup>(x)</td><td>equal to log(x + e)</td></tr><tr><td>Lip(f)</td><td>Lipschitz constant of the function f</td></tr><tr><td>d<sub>1</sub>, d</td><td>covering dimension of (X × A, ρ)</td></tr><tr><td>d<sub>2</sub></td><td>covering dimension of (X, ρ<sub>X</sub>)</td></tr><tr><td>|C<sub>σ</sub>|, |C̃<sub>σ</sub>|</td><td>σ-covering numbers of (X × A, ρ) and (X, ρ<sub>X</sub>), respectively</td></tr></tbody></table>

We consider the filtration defined as follows:

**Definition 1.** Let $\mathcal{F}_h^k$ be the $\sigma$-algebra generated by the random variables $\{x_h^s, a_h^s, x_{h+1}^s, r_h^s\}_{s=1}^{k-1} \cup \{x_{h', a_{h'}^k, x_{h'+1}^k, r_h^k}\}_{h'<h}$, and let $(\mathcal{F}_h^k)_{k,h}$ be its corresponding filtration.

## A.2. Preliminaries

Let $\sigma > 0$. We define the weights and the normalized weights as

$$w_h^s(x, a) \stackrel{\text{def}}{=} \psi_\sigma((x, a), (x_h^s, a_h^s)) \quad \text{and} \quad \tilde{w}_h^s(x, a) \stackrel{\text{def}}{=} \frac{w_h^s(x, a)}{\beta + \sum_{l=1}^{k-1} w_h^l(x, a)}$$

where $\beta > 0$ is a regularization parameter. We define the generalized count at $(x, a)$ at time $(k, h)$ as $C_h^k(x, a) \stackrel{\text{def}}{=} \beta + \sum_{s=1}^{k-1} w_h^s(x, a)$.

We define the following estimators for the transition kernels $\{P_h\}_{h \in [H]}$ and for the reward functions $\{r_h\}_{h \in [H]}$:

$$\hat{P}_h^k(y|x, a) \stackrel{\text{def}}{=} \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) \delta_{x_{h+1}^s}(y) \quad \text{and} \quad \hat{r}_h^k(x, a) \stackrel{\text{def}}{=} \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) r_h^s.$$

For any function $V: \mathbb{R} \to \mathbb{R}$, we recall that

$$P_h V(x, a) = \int_{\mathcal{X}} V(y) dP_h(y|x, a) \quad \text{and} \quad \hat{P}_h^k V(x, a) = \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) V(x_{h+1}^s).$$

We will also using the notion of covering of metric spaces, according to the definition below.

**Definition 2 (covering of a metric space).** Let $(\mathcal{U}, \rho)$ be a metric space. For any $u \in \mathcal{U}$, let $\mathcal{B}(u, \sigma) = \{v \in \mathcal{U} : \rho(u, v) \le \epsilon\}$. We say that a set $C_\sigma \subset \mathcal{U}$ is a $\sigma$-covering of $(\mathcal{U}, \rho)$ if $\mathcal{U} \subset \bigcup_{u \in C_\sigma} \mathcal{B}(u, \sigma)$. In addition, we define the $\sigma$-covering number of $(\mathcal{U}, \rho)$ as

$$\mathcal{N}(\sigma, \mathcal{U}, \rho) \stackrel{\text{def}}{=} \min \{|C_\sigma| : C_\sigma \text{ is a } \sigma\text{-covering of } (\mathcal{U}, \rho)\}.$$
## B. Description of the algorithm

At the beginning of each episode $k$, the agent has observed the data $\mathcal{D}_h = \{(x_h^s, a_h^s, x_{h+1}^s, r_h^s)\}_{s \in [k-1]}$ for $h \in [H]$. The number of data tuples in each $\mathcal{D}_h$ is $k-1$.

At each step $h$ of episode $k$, the agent has access to an optimistic value function at step $h+1$, denoted by $V_{h+1}^k$. Using this optimistic value function, the agent computes an upper bound for the $Q$ function at each state-action pair in the data, denoted by $\tilde{Q}_h^k(x_h^s, a_h^s)$ for $s \in [k-1]$, which we call *optimistic targets*. For any $(x, a)$, we can compute an optimistic target as

$$ \tilde{Q}_h^k(x, a) = \hat{r}_h^k(x, a) + \hat{P}_h^k V_{h+1}^k(x, a) + \mathbf{B}_h^k(x, a) $$

where $\mathbf{B}_h^k(x, a)$ is an exploration bonus for the pair $(x, a)$ that represents the sum of uncertainties on the transitions and rewards estimates and is defined below:

**Definition 3 (exploration bonus).**

$$ \mathbf{B}_h^k(x, a) = {}^p\mathbf{B}_h^k(x, a) + {}^r\mathbf{B}_h^k(x, a) = \underbrace{\left( \sqrt{\frac{H^2 \mathbf{v}_p(k, \delta/6)}{\mathbf{C}_h^k(x, a)}} + \frac{\beta H}{\mathbf{C}_h^k(x, a)} + \mathbf{b}_p(k, \delta/6) \sigma \right)}_{\text{transition bonus}} + \underbrace{\left( \sqrt{\frac{\mathbf{v}_r(k, \delta/6)}{\mathbf{C}_h^k(x, a)}} + \frac{\beta}{\mathbf{C}_h^k(x, a)} + \mathbf{b}_r(k, \delta/6) \sigma \right)}_{\text{reward bonus}} \quad (4) $$

where

$$ \mathbf{v}_r(k, \delta) = \tilde{\mathcal{O}}(d_1) = 2 \log \left( HN \left( \sigma^2/(KH), \mathcal{X} \times \mathcal{A}, \rho \right) \frac{\sqrt{1+k/\beta}}{\delta} \right) $$

$$ \mathbf{b}_r(k, \delta) = \tilde{\mathcal{O}}(L_1 + \sqrt{d_1}) = \frac{4C_2^g}{\beta} + \sqrt{\mathbf{v}_r(k, \delta)} \frac{C_2^g}{\beta^{3/2}} + 2\lambda_r L_1 \left( 1 + \sqrt{\log^+(C_1^g k/\beta)} \right) $$

$$ \mathbf{v}_p(k, \delta) = \tilde{\mathcal{O}}(d_1) = 2 \log \left( HN \left( \sigma^2/(KH), \mathcal{X} \times \mathcal{A}, \rho \right) \frac{\sqrt{1+k/\beta}}{\delta} \right) $$

$$ \mathbf{b}_p(k, \delta) = \tilde{\mathcal{O}}(L_1 + \sqrt{d_1}) = \frac{4C_2^g}{\beta} + \sqrt{\mathbf{v}_p(k, \delta)} \frac{C_2^g}{\beta^{3/2}} + 2\lambda_p L_1 \left( 1 + \sqrt{\log^+(C_1^g k/\beta)} \right) $$

Then, we build an optimistic $Q$ function $Q_h^k$ by interpolating the optimistic targets:

$$ \forall (x, a), \ Q_h^k(x, a) \stackrel{\text{def}}{=} \min_{s \in [k-1]} \left[ \tilde{Q}_h^k(x_h^s, a_h^s) + L_h \rho [(x, a), (x_h^s, a_h^s)] \right] \quad (5) $$

and the value function $V_h^k$ is computed as

$$ \forall x, \ V_h^k(x) \stackrel{\text{def}}{=} \min \left( H - h + 1, \max_{a'} Q_h^k(x, a') \right). $$

We can check that $(x, a) \mapsto Q_h^k(x, a)$ is $L_h$-Lipschitz with respect to $\rho$ and that $(x) \mapsto V_h^k(x)$ is $L_h$-Lipschitz with respect to $\rho_X$.

## C. Concentration

The first step towards proving our regret bound is to derive confidence intervals for the rewards and transitions, which are presented in propositions 1 and 2, respectively.

In addition, we need a Bernstein-type inequality for the transition kernels, which is stated in Proposition 3.

Finally, Theorem 3 defines a favorable event in which all the confidence intervals that we need to prove our regret bound are valid and we prove that this event happens with high probability.
### C.1. Confidence intervals for the reward functions

**Proposition 1.** For all $(k, h) \in [K] \times [H]$ and all $(x, a) \in \mathcal{X} \times \mathcal{A}$, we have

$$|\hat{r}_h^k(x, a) - r_h(x, a)| \le \sqrt{\frac{\mathbf{v}_r(k, \delta)}{\mathbf{C}_h^k(x, a)}} + \frac{\beta}{\mathbf{C}_h^k(x, a)} + \mathbf{b}_r(k, \delta)\sigma$$

with probability at least $1 - \delta$, where

$$\mathbf{v}_r(k, \delta) = \tilde{\mathcal{O}}(d_1) = 2 \log \left( H\mathcal{N} \left( \sigma^2/(KH), \mathcal{X} \times \mathcal{A}, \rho \right) \frac{\sqrt{1+k/\beta}}{\delta} \right) \\ \mathbf{b}_r(k, \delta) = \tilde{\mathcal{O}} \left( L_1 + \sqrt{d_1} \right) = \frac{4C_2^g}{\beta} + \sqrt{\mathbf{v}_r(k, \delta)} \frac{C_2^g}{\beta^{3/2}} + 2\lambda_r L_1 \left( 1 + \sqrt{\log^+(C_1^g k/\beta)} \right)$$

*Proof.* The proof is almost identical to the proof of Proposition 2. The main difference is that the rewards are bounded by 1, and not by $H$. □

### C.2. Confidence intervals for the transition kernels

**Proposition 2.** For all $(k, h) \in [K] \times [H]$ and all $(x, a) \in \mathcal{X} \times \mathcal{A}$, we have

$$|\hat{P}_h^k V_{h+1}^*(x, a) - P_h V_{h+1}^*(x, a)| \le \sqrt{\frac{H^2 \mathbf{v}_p(k, \delta)}{\mathbf{C}_h^k(x, a)}} + \frac{\beta H}{\mathbf{C}_h^k(x, a)} + \mathbf{b}_p(k, \delta)\sigma$$

with probability at least $1 - \delta$, where

$$\mathbf{v}_p(k, \delta) = \tilde{\mathcal{O}}(d_1) = 2 \log \left( H\mathcal{N} \left( \sigma^2/(KH), \mathcal{X} \times \mathcal{A}, \rho \right) \frac{\sqrt{1+k/\beta}}{\delta} \right) \\ \mathbf{b}_p(k, \delta) = \tilde{\mathcal{O}} \left( L_1 + \sqrt{d_1} \right) = \frac{4C_2^g}{\beta} + \sqrt{\mathbf{v}_p(k, \delta)} \frac{C_2^g}{\beta^{3/2}} + 2\lambda_p L_1 \left( 1 + \sqrt{\log^+(C_1^g k/\beta)} \right)$$

*Proof.* Consider a fixed tuple $(x, a, h)$, and let $V = V_{h+1}^*$. We have:

$$|\hat{P}_h^k V(x, a) - P_h V(x, a)| \le \left| \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) (V(x_{h+1}^s) - P_h V(x, a)) \right| + \left| \frac{\beta P_h V(x, a)}{\mathbf{C}_h^k(x, a)} \right| \\ \le \left| \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) (V(x_{h+1}^s) - P_h V(x, a)) \right| + \frac{\beta H}{\mathbf{C}_h^k(x, a)}$$
since $||V||_\infty \le H$. Now, by Assumption 2 and the fact that $V$ is $L_1$-Lipschitz:

$$ 
\begin{aligned}
& \left| \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) (V(x_{h+1}^s) - P_h V(x, a)) \right| \\
& \le \left| \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) (V(x_{h+1}^s) - P_h V(x_h^s, a_h^s)) \right| + \left| \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) (P_h V(x_h^s, a_h^s) - P_h V(x, a)) \right| \\
& \le \left| \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) (V(x_{h+1}^s) - P_h V(x_h^s, a_h^s)) \right| + L_1 \left| \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) W_1 (P_h(\cdot|x_h^s, a_h^s), P_h(\cdot|x, a)) \right| \\
& \le \left| \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) (V(x_{h+1}^s) - P_h V(x_h^s, a_h^s)) \right| + \lambda_p L_1 \left| \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) \rho [(x_h^s, a_h^s), (x, a)] \right| \\
& \le \left| \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) (V(x_{h+1}^s) - P_h V(x_h^s, a_h^s)) \right| + \lambda_p L_1 2\sigma \left( 1 + \sqrt{\log^+(C_1^g k/\beta)} \right)
\end{aligned}
$$

where, in the last inequality, we used Lemma 7.

Let $W_s \stackrel{\text{def}}{=} V(x_{h+1}^s) - P_h V(x_h^s, a_h^s)$. We have $|W_s| \le 2H$, and $(W_s)_s$ is a martingale difference sequence with respect to the filtration $(\mathcal{F}_h^s)_s$. Lemma 2 and an union bound over $h$ gives us:

$$ \left| \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) W_s \right| \le \sqrt{2H^2 \log \left( \frac{\sqrt{1+k/\beta}}{\delta} \right) \frac{1}{C_h^k(x, a)}} $$

for all $(k, h)$ and fixed $(x, a)$, with probability at least $1 - \delta H$.

Now, let's extend this inequality for all $(x, a)$ using a covering argument. We define

$$ f_1(x, a) \stackrel{\text{def}}{=} \left| \frac{1}{C_h^k(x, a)} \sum_{s=1}^{k-1} w_h^s(x, a) W_s \right| \quad \text{and} \quad f_2(x, a) \stackrel{\text{def}}{=} \sqrt{\frac{1}{C_h^k(x, a)}} $$

Lemma 8 implies that $\text{Lip}(f_1) \le 4C_2^g H k/(\beta\sigma)$ and $\text{Lip}(f_2) \le (C_2^g k/\sigma)^{\beta^{-3/2}}$. Applying Technical Lemma 6 using a $\sigma^2/(KH)$-covering of $(X \times A, \rho)$, we obtain:

$$ 
\begin{aligned}
\left| \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) W_s \right| & \le \sqrt{2H^2 \log \left( \frac{\sqrt{1+k/\beta}}{\delta} \right) \frac{1}{C_h^k(x, a)} \\
& \quad + \frac{\sigma^2}{KH} \text{Lip}(f_1) + \frac{\sigma^2}{KH} \sqrt{2H^2 \log \left( \frac{\sqrt{1+k/\beta}}{\delta} \right) \text{Lip}(f_2)}
\end{aligned}
$$

for all $(x, a, k, h)$ with probability at least $1 - \delta H N (\sigma^2/(KH), X \times A, \rho)$.

The fact that

$$ \left| \hat{P}_h^k V(x, a) - P_h V(x, a) \right| \le \left| \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) W_s \right| + 2\lambda_p L_1 \sigma \left( 1 + \sqrt{\log^+(C_1^g k/\beta)} \right) + \frac{\beta H}{C_h^k(x, a)} $$

allows us to conclude.
### C.3. A confidence interval for $P_h f$ uniformly over Lipschitz functions $f$

In the regret analysis, we will need to control quantities like $(\hat{P}_h^k - P_h)(\hat{f}_h^k)$ for random Lipschitz functions $\hat{f}_h^k$, which motivate us to propose a deviation inequality for $(\hat{P}_h^k - P_h)(f)$ which holds uniformly over $f$ in a class of Lipschitz functions. We provide such a result in Proposition 3.

**Proposition 3.** Consider the following function space:

$$ \mathcal{F}_{2L_1} \stackrel{\text{def}}{=} \{f : \mathcal{X} \to \mathbb{R} \text{ such that } f \text{ is } 2L_1\text{-Lipschitz and } \|f\|_{\infty} \le 2H\}. $$

With probability at least $1 - \delta$, for all $(x, a, h, k) \in \mathcal{X} \times \mathcal{A} \times [K] \times [H]$ and for all $f \in \mathcal{F}_{2L_1}$, we have

$$ \left| (\hat{P}_h^k - P_h) f(x, a) \right| \le \frac{1}{H} P_h |f|(x, a) + \frac{11H^2\theta_v(k, \delta) + 2\beta H}{\mathbf{C}_h^k(x, a)} + \theta_b^1(k, \delta)\sigma^{1+d_2} + \theta_b^2(k, \delta)\sigma $$

with probability at least $1 - \delta$, where

$$ \theta_v(k, \delta) = \tilde{\mathcal{O}} (|\tilde{C}_\sigma| + d_1 d_2) = \log \left( \frac{4e(2k+1)}{\delta} H \mathcal{N} \left( \frac{\sigma^{2+d_2}}{KH^2}, \mathcal{X} \times \mathcal{A}, \rho \right) \left( \frac{2H}{L_1 \sigma} \right)^{\mathcal{N}(\sigma, \mathcal{X}, \rho \mathcal{X})} \right) $$

$$ \theta_b^1(k, \delta) = \tilde{\mathcal{O}} (|\tilde{C}_\sigma| + d_1 d_2) = \left( \frac{2\lambda_p L_1 \sigma}{KH^2} + \frac{4C_2^g}{H\beta} + \frac{11C_2^g \theta_v(k, \delta)}{\beta^2} \right) $$

$$ \theta_b^2(k, \delta) = \tilde{\mathcal{O}}(L_1) = 32L_1 + 6\lambda_p L_1 \left( 1 + \sqrt{\log^+(C_1^g k/\beta)} \right) $$

where $|\tilde{C}_\sigma| = \mathcal{O}(1/\sigma_2^d)$ is the $\sigma$-covering number of $(\mathcal{X}, \rho_\mathcal{X})$.

*Proof.* First, consider a fixed tuple $(x, a, h, k)$. Using the same arguments as in the proof of Proposition 2, we show that:

$$ \left| \hat{P}_h^k f(x, a) - P_h f(x, a) \right| \le \underbrace{\left| \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) W_s(f) \right|}_{(\mathbf{A})} + 4\lambda_p L_1 \sigma \left( 1 + \sqrt{\log^+(C_1^g k/\beta)} \right) + \frac{2\beta H}{\mathbf{C}_h^k(x, a)} $$

where $W_s(f) \stackrel{\text{def}}{=} f(x_{h+1}^s) - P_h f(x_h^s, a_h^s)$. We have $|W_s(f)| \le 4H$, and $(W_s)_s$ is a martingale difference sequence with respect to the filtration $(\mathcal{F}_h^s)_s$ for any fixed $f$. We will bound the term $(\mathbf{A})$ using the Bernstein-type inequality given in Lemma 3. We start by bounding the variance of $f(x_{h+1}^s)$ given $\mathcal{F}_h^s$:

$$ \begin{aligned} \mathbb{V}[f(x_{h+1}^s) | \mathcal{F}_h^s] &= \mathbb{E}[f(x_{h+1}^s)^2 | \mathcal{F}_h^s] - \left( \int_{\mathcal{X}} f(y) dP_h(y|x_h^s, a_h^s) \right)^2 \\ &\le 2H \mathbb{E}[|f(x_{h+1}^s)| | \mathcal{F}_h^s] \\ &= 2HP_h |f|(x_h^s, a_h^s) \end{aligned} $$
and, consequently,

$$
\begin{align*}
\sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) \mathbb{V} [f(x_{h+1}^s) | \mathcal{F}_h^s] &\le 2H \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) P_h |f|(x_h^s, a_h^s) \\
&= 2H \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) P_h |f|(x, a) + 2H \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) (P_h |f|(x_h^s, a_h^s) - P_h |f|(x, a)) \\
&\le 2H \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) P_h |f|(x, a) + 4H \lambda_p L_1 \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) \rho [(x_h^s, a_h^s)] \\
&\le 2H P_h |f|(x, a) + 4H \lambda_p L_1 \sigma \left(1 + \sqrt{\log^+(C_1^g k/\beta)}\right), \tag{6}
\end{align*}
$$

where, in the last two inequalities, we used Assumption 2 and Lemma 7.

Let $\square(k, \delta) = \log(4e(2k+1)/\delta)$. Using Lemma 3 and the facts that $\sqrt{u+v} \le \sqrt{u} + \sqrt{v}$ and $\sqrt{uv} \le (u+v)/2$ for all $u, v > 0$, we obtain

$$
\begin{align*}
(\mathbf{A}) &= \left| \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) W_s(f) \right| = \left| \frac{\sum_{s=1}^{k-1} w_h^s(x, a) W_s(f)}{\beta + \sum_{s=1}^{k-1} w_h^s(x, a)} \right| \\
&\le \sqrt{ 2 \square(k, \delta) \frac{\sum_{s=1}^{k-1} w_h^s(x, a)^2 \mathbb{V}[f(x_{h+1}^s) | \mathcal{F}_h^s] + 16H^2}{(\beta + \sum_{s=1}^{k-1} w_h^s(x, a))^2} + \frac{(8/3)H \square(k, \delta)}{\beta + \sum_{s=1}^{k-1} w_h^s(x, a)} } \\
&\le \frac{H^2 \square(k, \delta)}{\beta + \sum_{s=1}^{k-1} w_h^s(x, a)} + \frac{1}{2H^2} \frac{\sum_{s=1}^{k-1} w_h^s(x, a)^2 \mathbb{V}[f(x_{h+1}^s) | \mathcal{F}_h^s]}{\beta + \sum_{s=1}^{k-1} w_h^s(x, a)} + \frac{(8/3 + 4\sqrt{2})H \square(k, \delta)}{\beta + \sum_{s=1}^{k-1} w_h^s(x, a)} \\
&\le \frac{(H^2 + 10H) \square(k, \delta)}{C_h^k(x, a)} + \frac{1}{2H^2} \frac{\sum_{s=1}^{k-1} w_h^s(x, a) \mathbb{V}[f(x_{h+1}^s) | \mathcal{F}_h^s]}{\beta + \sum_{s=1}^{k-1} w_h^s(x, a)} \\
&= \frac{(H^2 + 10H) \square(k, \delta)}{C_h^k(x, a)} + \frac{1}{2H^2} \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) \mathbb{V}[f(x_{h+1}^s) | \mathcal{F}_h^s]
\end{align*}
$$

for all $k$, with probability at least $1 - \delta$. Above, we also used the fact that $w_h^s(x, a)^2 \le w_h^s(x, a)$ since the weights are in $[0, 1]$.

Inequality 6 yields

$$
(\mathbf{A}) \le \frac{1}{H} P_h |f|(x, a) + \frac{(H^2 + 10H) \square(k, \delta)}{C_h^k(x, a)} + \frac{2\lambda_p L_1 \sigma}{H} \left(1 + \sqrt{\log^+(C_1^g k/\beta)}\right)
$$

with probability at least $1 - \delta$.

**Extending to all** $(x, a)$ Assumption 2 implies that $(x, a) \mapsto (1/H)P_h |f|(x, a)$ is $2\lambda_p L_1$-Lipschitz. Let

$$
f_1(x, a) = \left| \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) W_s(f) \right| \quad \text{and} \quad f_2(x, a) = \frac{1}{C_h^k(x, a)}.
$$

Lemma 8 implies that Lip($f_1$) $\le 4HC_2^g k/(\beta\sigma)$ and Lip($f_2$) $\le C_2^g k/(\beta^2\sigma)$. Applying Technical Lemma 6 using a $\sigma^{2+d_2}/(KH^2)$-covering of $(\mathcal{X} \times \mathcal{A}, \rho)$, and doing an union bound over $[H]$, we obtain:

$$
\left| \sum_{s=1}^{k-1} \tilde{w}_h^s(x, a) W_s(f) \right| \le \frac{1}{H} P_h |f|(x, a) + \frac{(H^2 + 10H) \square(k, \delta)}{C_h^k(x, a)} + \frac{2\lambda_p L_1 \sigma}{H} \left(1 + \sqrt{\log^+(C_1^g k/\beta)}\right) \\
+ \frac{\sigma^{2+d_2}}{KH^2} \left(2\lambda_p L_1 + \frac{4HC_2^g k}{\beta\sigma} + \frac{C_2^g k(H^2 + 10H) \square(k, \delta)}{\beta^2\sigma}\right)
$$

for all $(x, a, h, k)$ with probability at least $1 - \delta H N (\frac{\sigma^{2+d_2}}{KH^2}, \mathcal{X} \times \mathcal{A}, \rho)$.
Extending to all $f \in \mathcal{F}_{2L_1}$ The inequalities above give us

$$ \left| \hat{P}_h^k f(x, a) - P_h f(x, a) \right| \le \frac{1}{H} P_h |f|(x, a) + \frac{(H^2 + 10H)\Box(k, \delta)}{\mathbf{C}_h^k(x, a)} \\ + \frac{\sigma^{2+d_2}}{KH^2} \left( 2\lambda_p L_1 + \frac{4HC_2^g k}{\beta\sigma} + \frac{C_2^g k(H^2 + 10H)\Box(k, \delta)}{\beta^2\sigma} \right) \\ + 6\lambda_p L_1 \sigma \left( 1 + \sqrt{\log^+(C_1^g k/\beta)} \right) + \frac{2\beta H}{\mathbf{C}_h^k(x, a)} $$

for all $(x, a, h, k)$ with probability at least $1 - \delta H \mathcal{N} \left( \frac{\sigma^{2+d_2}}{KH^2}, \mathcal{X} \times \mathcal{A}, \rho \right)$.

According to Lemma 5, the $8L_1\sigma$-covering number of $\mathcal{F}_{2L_1}$ is bounded by $(2H/(L_1\sigma))^{\mathcal{N}(\sigma, \mathcal{X}, \rho\mathcal{X})}$. The functions $f \mapsto |\hat{P}_h^k f(x, a) - P_h f(x, a)|$ and $f \mapsto \frac{1}{H} P_h |f|(x, a)$ are 2-Lipschitz with respect to $\|\cdot\|_{\infty}$. Hence, Lemma 6 gives us:

$$ \left| \hat{P}_h^k f(x, a) - P_h f(x, a) \right| \le \frac{1}{H} P_h |f|(x, a) + \frac{(H^2 + 10H)\Box(k, \delta)}{\mathbf{C}_h^k(x, a)} \\ + \frac{\sigma^{2+d_2}}{KH^2} \left( 2\lambda_p L_1 + \frac{4HC_2^g k}{\beta\sigma} + \frac{C_2^g k(H^2 + 10H)\Box(k, \delta)}{\beta^2\sigma} \right) \\ + 6\lambda_p L_1 \sigma \left( 1 + \sqrt{\log^+(C_1^g k/\beta)} \right) + \frac{2\beta H}{\mathbf{C}_h^k(x, a)} \\ + 32L_1\sigma $$

for all $(x, a, h, k)$ with probability at least $1 - \delta H \mathcal{N} \left( \frac{\sigma^{2+d_2}}{KH^2}, \mathcal{X} \times \mathcal{A}, \rho \right) (2H/(L_1\sigma))^{\mathcal{N}(\sigma, \mathcal{X}, \rho\mathcal{X})}$, which concludes the proof. □
### C.4. Good event

**Theorem 3 (Good event).** Let $\mathcal{G} = \mathcal{G}_1 \cup \mathcal{G}_2 \cup \mathcal{G}_3$, where

$$
\begin{align*}
\mathcal{G}_1 &\stackrel{\text{def}}{=} \left\{ \forall (x, a, k, h), \left| \hat{r}_h^k(x, a) - r_h(x, a) \right| \le \sqrt{\frac{\mathbf{v}_r(k, \delta/6)}{\mathbf{C}_h^k(x, a)}} + \frac{\beta}{\mathbf{C}_h^k(x, a)} + \mathbf{b}_r(k, \delta/6)\sigma \right\} \\
\mathcal{G}_2 &\stackrel{\text{def}}{=} \left\{ \forall (x, a, k, h), \left| \hat{P}_h^k V_{h+1}^*(x, a) - P_h V_{h+1}^*(x, a) \right| \le \sqrt{\frac{H^2 \mathbf{v}_p(k, \delta/6)}{\mathbf{C}_h^k(x, a)}} + \frac{\beta H}{\mathbf{C}_h^k(x, a)} + \mathbf{b}_p(k, \delta/6)\sigma \right\} \\
\mathcal{G}_3 &\stackrel{\text{def}}{=} \left\{ \forall (x, a, k, h, f), \left| (\hat{P}_h^k - P_h) f(x, a) \right| \le \frac{1}{H} P_h |f|(x, a) + \frac{11H^2\theta_v(k, \delta/6) + 2\beta H}{\mathbf{C}_h^k(x, a)} \right. \\
&\qquad \left. + \theta_b^1(k, \delta/6)\sigma^{1+d_2} + \theta_b^2(k, \delta/6)\sigma \right\}
\end{align*}
$$

for $(x, a, k, h) \in \mathcal{X} \times \mathcal{A} \times [K] \times [H]$ and $f \in \mathcal{F}_{2L_1}$, and where

$$
\begin{align*}
\mathbf{v}_r(k, \delta) &= \tilde{\mathcal{O}}(d_1), & \mathbf{b}_r(k, \delta) &= \tilde{\mathcal{O}}(L_1 + \sqrt{d_1}) \\
\mathbf{v}_p(k, \delta) &= \tilde{\mathcal{O}}(d_1), & \mathbf{b}_p(k, \delta) &= \tilde{\mathcal{O}}(L_1 + \sqrt{d_1}), \\
\theta_v(k, \delta) &= \tilde{\mathcal{O}}(|\tilde{\mathcal{C}}_\sigma| + d_1 d_2), & \theta_b^1(k, \delta) &= \tilde{\mathcal{O}}(|\tilde{\mathcal{C}}_\sigma| + d_1 d_2), & \theta_b^2(k, \delta) &= \tilde{\mathcal{O}}(L_1)
\end{align*}
$$

are defined in Propositions 1, 2 and 3. Then,

$$ \mathbb{P}[\mathcal{G}] \ge 1 - \delta/2. $$

*Proof.* Immediate consequence of Propositions 1, 2 and 3. □

### D. Optimism and regret bound

**Proposition 4 (Optimism).** In the event $\mathcal{G}$, whose probability is greater than $1 - \delta/2$, we have:

$$ \forall (x, a), \mathcal{Q}_h^k(x, a) \ge \mathcal{Q}_h^*(x, a) $$

*Proof.* We proceed by induction.

*Initialization* When $h = H + 1$, we have $\mathcal{Q}_h^k(x, a) = \mathcal{Q}_h^*(x, a) = 0$ for all $(x, a)$.

*Induction hypothesis* Assume that $\mathcal{Q}_{h+1}^k(x, a) \ge \mathcal{Q}_{h+1}^*(x, a)$ for all $(x, a)$.

*Induction step* The induction hypothesis implies that $\mathcal{V}_{h+1}^k(x) \ge \mathcal{V}_{h+1}^*(x)$ for all $x$. Hence, for all $(x, a)$, we have

$$ \tilde{\mathcal{Q}}_h^k(x, a) - \mathcal{Q}_h^*(x, a) = \underbrace{(\hat{r}_h^k(x, a) - r_h(x, a)) + (\hat{P}_h^k - P_h)V_{h+1}^*(x, a) + \mathbf{B}_h^k(x, a)}_{\ge 0 \text{ in } \mathcal{G}} + \underbrace{\hat{P}_h^k(V_{h+1}^k - V_{h+1}^*)(x, a)}_{\ge 0} \ge 0. $$

In particular $\tilde{\mathcal{Q}}_h^k(x_h^s, a_h^s) - \mathcal{Q}_h^*(x_h^s, a_h^s) \ge 0$ for all $s \in [k-1]$. This implies that

$$ \tilde{\mathcal{Q}}_h^k(x_h^s, a_h^s) + L_h \rho [(x, a), (x_h^s, a_h^s)] \ge \mathcal{Q}_h^*(x_h^s, a_h^s) + L_h \rho [(x, a), (x_h^s, a_h^s)] \ge \mathcal{Q}_h^*(x, a) $$

for all $s \in [k-1]$, since $\mathcal{Q}_h^*$ is $L_h$-Lipschitz. Finally, we obtain

$$ \forall (x, a), \mathcal{Q}_h^k(x, a) = \min_{s \in [k-1]} \left[ \tilde{\mathcal{Q}}_h^k(x_h^s, a_h^s) + L_h \rho [(x, a), (x_h^s, a_h^s)] \right] \ge \mathcal{Q}_h^*(x, a). $$
<figure><img src="image_4.png" /></figure>

**Corollary 2.** Let $\delta_h^k \stackrel{\text{def}}{=} V_h^k(x_h^k) - V_h^{\pi_k}(x_h^k)$. Then, on $\mathcal{G}$, $\mathcal{R}(K) \le \sum_{k=1}^K \delta_h^k$.

*Proof.* Combining the definition of the regret with Proposition 4 easily yields, on the event $\mathcal{G}$,

$$ \begin{aligned} \mathcal{R}(K) &= \sum_{k=1}^{K} (V_1^*(x_1^k) - V_1^{\pi_k}(x_1^k)) = \sum_{k=1}^{K} \left( \max_a Q_1^*(x_1^k, a) - V_1^{\pi_k}(x_1^k) \right) \\ &\le \sum_{k=1}^{K} \left( \min \left[ H - h + 1, \max_a Q_1^k(x_1^k, a) \right] - V_1^{\pi_k}(x_1^k) \right) = \sum_{k=1}^{K} (V_1^k(x_1^k, a) - V_1^{\pi_k}(x_1^k)), \end{aligned} $$

<figure><img src="image_5.png" /></figure>

**Definition 4.** For any $(k, h)$, we define $(\tilde{x}_h^k, \tilde{a}_h^k)$ as state-action pair in the past data $\mathcal{D}_h$ that is the closest to $(x_h^k, a_h^k)$, that is

$$ (\tilde{x}_h^k, \tilde{a}_h^k) \stackrel{\text{def}}{=} \underset{(x_h^s, a_h^s): s < k}{\operatorname{argmin}} \rho [(x_h^k, a_h^k), (x_h^s, a_h^s)]. $$

**Proposition 5.** With probability $1 - \delta$, the regret of Kernel – UCBVI is bounded as follows

$$ \begin{aligned} \mathcal{R}(K) &\lesssim H^2 |C_\sigma| + L_1 K H \sigma + \sum_{k=1}^K \sum_{h=1}^H \left(1 + \frac{1}{H}\right)^h \tilde{\xi}_{h+1}^k \\ &\quad + \sum_{k=1}^K \sum_{h=1}^H \left( \frac{H}{\sqrt{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} + \frac{H^2 |\tilde{C}_\sigma|}{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} \right) \mathbb{I}\{\rho[(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] \le 2\sigma\} \end{aligned} $$

where $\tilde{\xi}_{h+1}^k$ is a martingale difference sequence with respect to $(\mathcal{F}_h^k)_{k,h}$ such that $|\tilde{\xi}_{h+1}^k| \le 4H$.

*Proof.* On $\mathcal{G}$, we have

$$ \begin{aligned} \delta_h^k &= V_h^k(x_h^k) - V_h^{\pi_k}(x_h^k) \\ &\le Q_h^k(x_h^k, a_h^k) - Q_h^{\pi_k}(x_h^k, a_h^k) \\ &\le Q_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - Q_h^{\pi_k}(x_h^k, a_h^k) + L_1 \rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)], \text{ since } Q_h^k \text{ is } L_1\text{-Lipschitz} \\ &\le \tilde{Q}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - Q_h^{\pi_k}(x_h^k, a_h^k) + L_1 \rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)], \text{ since } Q_h^k(\tilde{x}_h^k, \tilde{a}_h^k) \le \tilde{Q}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) \text{ by definition of } Q_h^k \\ &= \hat{r}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - r_h(x_h^k, a_h^k) + L_1 \rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] + B_h^k(\tilde{x}_h^k, \tilde{a}_h^k) + \hat{P}_h^k V_{h+1}^k(\tilde{x}_h^k, \tilde{a}_h^k) - P_h V_{h+1}^{\pi_k}(x_h^k, a_h^k) \\ &= \underbrace{\hat{r}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - r_h(x_h^k, a_h^k)}_{(\mathbf{A})} + \underbrace{[\hat{P}_h^k - P_h] V_{h+1}^*(\tilde{x}_h^k, \tilde{a}_h^k)}_{(\mathbf{B})} + \underbrace{[\hat{P}_h^k - P_h] (V_{h+1}^k - V_{h+1}^*) (\tilde{x}_h^k, \tilde{a}_h^k)}_{(\mathbf{C})} \\ &\quad + \underbrace{P_h V_{h+1}^k(\tilde{x}_h^k, \tilde{a}_h^k) - P_h V_{h+1}^{\pi_k}(x_h^k, a_h^k)}_{(\mathbf{D})} + L_1 \rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] + B_h^k(\tilde{x}_h^k, \tilde{a}_h^k) \end{aligned} $$

Now, let's bound each of the terms $(\mathbf{A})$, $(\mathbf{B})$, $(\mathbf{C})$ and $(\mathbf{D})$
**Term (A)** Using the fact that $r_h$ is $\lambda_r$-Lipschitz and the definition of $\mathcal{G}$:

$$ (\mathbf{A}) = \hat{r}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - r_h(x_h^k, a_h^k) \leq \lambda_r \rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] + {}^r\mathbb{B}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) \\ \lesssim \lambda_r \rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] + \sqrt{\frac{1}{\mathbf{C}_h^k(x, a)}} + \frac{\beta}{\mathbf{C}_h^k(x, a)} + L_1\sigma. $$

**Term (B)** Using the definition of $\mathcal{G}$:

$$ (\mathbf{B}) = [\hat{P}_h^k - P_h] V_{h+1}^*(\tilde{x}_h^k, \tilde{a}_h^k) \lesssim \sqrt{\frac{H^2}{\mathbf{C}_h^k(x, a)}} + \frac{\beta H}{\mathbf{C}_h^k(x, a)} + L_1\sigma $$

**Term (C)** Using again the definition of $\mathcal{G}$, where $V_{h+1}^k \geq V_{h+1}^*$, and the fact that $V_{h+1}^* \geq V_{h+1}^{\pi_k}$:

$$ (\mathbf{C}) = [\hat{P}_h^k - P_h] (V_{h+1}^k - V_{h+1}^*) (\tilde{x}_h^k, \tilde{a}_h^k) \\ \lesssim \frac{1}{H} P_h (V_{h+1}^k - V_{h+1}^*) (\tilde{x}_h^k, \tilde{a}_h^k) + \frac{H^2 |\tilde{\mathcal{C}}_\sigma|}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} + L_1\sigma \\ \leq \frac{1}{H} P_h (V_{h+1}^k - V_{h+1}^*) (x_h^k, a_h^k) + 2\lambda_p L_1 \rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] + \frac{H^2 |\tilde{\mathcal{C}}_\sigma|}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} + L_1\sigma \\ \lesssim \frac{1}{H} P_h (V_{h+1}^k - V_{h+1}^{\pi_k}) (x_h^k, a_h^k) + L_1 \rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] + \frac{H^2 |\tilde{\mathcal{C}}_\sigma|}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} + L_1\sigma \\ = \frac{1}{H} (\delta_{h+1}^k + \xi_{h+1}^k) + L_1 \rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] + \frac{H^2 |\tilde{\mathcal{C}}_\sigma|}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} + L_1\sigma $$

where

$$ \xi_{h+1}^k = P_h (V_{h+1}^k - V_{h+1}^{\pi_k}) (x_h^k, a_h^k) - \delta_{h+1}^k $$

is a martingale difference sequence with respect to $(\mathcal{F}_h^k)_{k,h}$ bounded by $4H$.

**Term (D)** We have

$$ (\mathbf{D}) = P_h V_{h+1}^k(\tilde{x}_h^k, \tilde{a}_h^k) - P_h V_{h+1}^{\pi_k}(x_h^k, a_h^k) \\ \leq \lambda_p L_1 \rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] + P_h V_{h+1}^k(x_h^k, a_h^k) - P_h V_{h+1}^{\pi_k}(x_h^k, a_h^k) \\ = \delta_{h+1}^k + \xi_{h+1}^k + \lambda_p L_1 \rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)]. $$

Putting together the bounds above, we obtain

$$ \delta_h^k \lesssim \left(1 + \frac{1}{H}\right) (\delta_{h+1}^k + \xi_{h+1}^k) + L_1 \rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] + \sqrt{\frac{H^2}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} + \frac{H^2 |\tilde{\mathcal{C}}_\sigma|}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} + L_1\sigma $$

where the constant in front of $\delta_{h+1}^k$ is exact (not hidden by $\lesssim$).

Now, consider the event $E_h^k \stackrel{\text{def}}{=} \{\rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] \leq 2\sigma\}$ and let $\bar{E}_h^k$ be its complement. Using the fact that $\delta_{h+1}^k \geq 0$ on $\mathcal{G}$, the inequality above implies

$$ \begin{aligned} \mathbb{I}\{E_h^k\} \delta_h^k \lesssim \mathbb{I}\{E_h^k\} \left(1 + \frac{1}{H}\right) (\delta_{h+1}^k + \xi_{h+1}^k) + 3L_1\sigma + \mathbb{I}\{E_h^k\} \sqrt{\frac{H^2}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} + \mathbb{I}\{E_h^k\} \frac{H^2 |\tilde{\mathcal{C}}_\sigma|}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} \\ \lesssim \left(1 + \frac{1}{H}\right) (\delta_{h+1}^k + \mathbb{I}\{E_h^k\} \xi_{h+1}^k) + 3L_1\sigma + \mathbb{I}\{E_h^k\} \sqrt{\frac{H^2}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} + \mathbb{I}\{E_h^k\} \frac{H^2 |\tilde{\mathcal{C}}_\sigma|}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}. \end{aligned} \quad (7) $$
Now, using the fact that $\delta_h^k \le H$, we obtain

$$ 
\begin{aligned}
\delta_h^k &= \mathbb{I}\{E_h^k\} \delta_h^k + \mathbb{I}\{\bar{E}_h^k\} \delta_h^k \\
&\le \mathbb{I}\{E_h^k\} \delta_h^k + H\mathbb{I}\{\bar{E}_h^k\} \\
&\lesssim H\mathbb{I}\{\bar{E}_h^k\} + \left(1 + \frac{1}{H}\right) \left(\delta_{h+1}^k + \mathbb{I}\{E_h^k\} \xi_{h+1}^k\right) + 3L_1\sigma + \mathbb{I}\{E_h^k\} \sqrt{\frac{H^2}{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} + H\mathbb{I}\{E_h^k\} \frac{H^2|\tilde{C}_\sigma|}{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}.
\end{aligned} 
\quad (8) $$

This yields

$$ 
\begin{aligned}
\delta_1^k \lesssim & \sum_{h=1}^H \mathbb{I}\{E_h^k\} \left( \sqrt{\frac{H^2}{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} + \frac{H^2|\tilde{C}_\sigma|}{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} \right) \\
& + \sum_{h=1}^H \left(1 + \frac{1}{H}\right)^h \mathbb{I}\{E_h^k\} \xi_{h+1}^k + L_1 H \sigma + H \sum_{h=1}^H \mathbb{I}\{\bar{E}_h^k\}.
\end{aligned} 
$$

Let $\tilde{\xi}_{h+1}^k \stackrel{\text{def}}{=} \mathbb{I}\{E_h^k\} \xi_{h+1}^k$. We can verify that $\tilde{\xi}_{h+1}^k$ is a martingale difference sequence with respect to $(\mathcal{F}_h^k)_{k,h}$ bounded by $4H$.

Applying Corollary 2, we obtain:

$$ 
\begin{aligned}
\mathcal{R}(K) \le & \sum_{k=1}^K \delta_1^k \lesssim \sum_{k=1}^K \sum_{h=1}^H \mathbb{I}\{E_h^k\} \left( \sqrt{\frac{H^2}{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} + \frac{H^2|\tilde{C}_\sigma|}{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} \right) \\
& + \sum_{k=1}^K \sum_{h=1}^H \left(1 + \frac{1}{H}\right)^h \tilde{\xi}_{h+1}^k + L_1 K H \sigma + H \sum_{k=1}^K \sum_{h=1}^H \mathbb{I}\{\bar{E}_h^k\}.
\end{aligned} 
$$

Finally, we bound the sum

$$ H \sum_{k=1}^{K} \sum_{h=1}^{H} \mathbb{I}\{\bar{E}_h^k\} = H \sum_{h=1}^{H} \sum_{k=1}^{K} \mathbb{I}\{\rho[(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] > 2\sigma\} \le H^2|C_\sigma| $$

since, for each $h$, the number of episodes where the event $\{\rho[(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] > 2\sigma\}$ occurs is bounded by $|C_\sigma|$. Recalling the definition $E_h^k \stackrel{\text{def}}{=} \{\rho[(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] \le 2\sigma\}$, this concludes the proof. $\square$

<figure><img src="image_6.png" /></figure>

**Proposition 6.** We have

$$ \sum_{k=1}^{K} \sum_{h=1}^{H} \frac{1}{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} \mathbb{I}\{\rho[(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] \le 2\sigma\} \lesssim H|C_\sigma| $$

and

$$ \sum_{k=1}^{K} \sum_{h=1}^{H} \frac{1}{\sqrt{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} \mathbb{I}\{\rho[(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] \le 2\sigma\} \lesssim H|C_\sigma| + H\sqrt{|C_\sigma|K} $$

*Proof.* First, we will need some definitions. Let $C_\sigma = \{(x_j, a_j) \in \mathcal{X} \times \mathcal{A}, j = 1, \dots, |C_\sigma|\}$ be a $\sigma$-covering of $(\mathcal{X} \times \mathcal{A}, \rho)$. We define a partition $\{B_j\}_{j=1}^{|C_\sigma|}$ of $\mathcal{X} \times \mathcal{A}$ as follows:

$$ B_j = \left\{ (x, a) \in \mathcal{X} \times \mathcal{A} : (x_j, a_j) = \underset{(x_i, a_i) \in C_\sigma}{\operatorname{argmin}} \rho[(x, a), (x_i, a_i)] \right\} $$
where ties in the argmin are broken arbitrarily.

We define the number of visits to each set $B_j$ as $\mathbf{N}_h^k(B_j) \stackrel{\text{def}}{=} \sum_{s=1}^{k-1} \mathbb{I}\{(x_h^s, a_h^s) \in B_j\}$.

Now, assume that $(x_h^k, a_h^k) \in B_j$. If, in addition, $\rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] \le 2\sigma$, we obtain

$$
\begin{align*}
\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) &= \beta + \sum_{s=1}^{k-1} \psi_{\sigma}((\tilde{x}_h^k, \tilde{a}_h^k), (x_h^s, a_h^s)) = \beta + \sum_{s=1}^{k-1} g\left(\frac{\rho[(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^s, a_h^s)]}{\sigma}\right) \\
&\ge \beta + \sum_{s=1}^{k-1} g\left(\frac{\rho[(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^s, a_h^s)]}{\sigma}\right) \mathbb{I}\{(x_h^s, a_h^s) \in B_j\} \\
&\ge \beta + g(4) \sum_{s=1}^{k-1} \mathbb{I}\{(x_h^s, a_h^s) \in B_j\} = \beta(1 + g(4)\beta^{-1}\mathbf{N}_h^k(B_j))
\end{align*}
$$

since, if $(x_h^s, a_h^s) \in B_j$, we have $\rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^s, a_h^s)] \le 4\sigma$ and we use the fact that $g$ is non-increasing.

We are now ready to bound the sums involving $1/\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)$. We will use the fact that $g(4) > 0$ by Assumption 3.

Bounding the sum of the first order terms

$$
\begin{align*}
& \sum_{k=1}^{K} \sum_{h=1}^{H} \sqrt{\frac{1}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} \mathbb{I}\{\rho[(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] \le 2\sigma\} \\
&= \sum_{k=1}^{K} \sum_{h=1}^{H} \sum_{j=1}^{|C_\sigma|} \sqrt{\frac{1}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} \mathbb{I}\{\rho[(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] \le 2\sigma\} \mathbb{I}\{(x_h^k, a_h^k) \in B_j\} \\
&\le \beta^{-1/2} \sum_{k=1}^{K} \sum_{h=1}^{H} \sum_{j=1}^{|C_\sigma|} \frac{1}{\sqrt{1 + g(4)\beta^{-1}\mathbf{N}_h^k(B_j)}} \mathbb{I}\{\rho[(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] \le 2\sigma\} \mathbb{I}\{(x_h^k, a_h^k) \in B_j\} \\
&\le \beta^{-1/2} \sum_{h=1}^{H} \sum_{j=1}^{|C_\sigma|} \sum_{k=1}^{K} \frac{\mathbb{I}\{(x_h^k, a_h^k) \in B_j\}}{\sqrt{1 + g(4)\beta^{-1}\mathbf{N}_h^k(B_j)}} \le \beta^{-1/2} \sum_{h=1}^{H} \sum_{j=1}^{|C_\sigma|} \left(1 + \int_0^{\mathbf{N}_h^{K+1}(B_j)} \frac{dz}{\sqrt{1 + g(4)\beta^{-1}z}}\right) \text{ by Lemma 9} \\
&\le \beta^{-1/2} H |C_\sigma| + \frac{2\beta^{1/2}}{g(4)} \sum_{h=1}^{H} \sum_{j=1}^{|C_\sigma|} \sqrt{1 + g(4)\beta^{-1}\mathbf{N}_h^{K+1}(B_j)} \\
&\le \beta^{-1/2} H |C_\sigma| + \frac{2\beta^{1/2}}{g(4)} \sum_{h=1}^{H} \sqrt{|C_\sigma|} \sqrt{|C_\sigma| + g(4)\beta^{-1}K} \quad \text{by Cauchy-Schwarz inequality} \\
&\le H \left(\beta^{-1/2} + \frac{2\beta^{1/2}}{g(1)}\right) |C_\sigma| + \frac{2H}{g(4)} \sqrt{g(4)|C_\sigma|K} \lesssim H|C_\sigma| + H\sqrt{|C_\sigma|K}.
\end{align*}
$$
Bounding the sum of the second order terms

$$
\begin{align*}
& \sum_{k=1}^{K} \sum_{h=1}^{H} \frac{1}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} \mathbb{I}\{\rho[(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] \le 2\sigma\} \\
&= \sum_{k=1}^{K} \sum_{h=1}^{H} \sum_{j=1}^{|C_\sigma|} \frac{1}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} \mathbb{I}\{\rho[(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] \le 2\sigma\} \mathbb{I}\{(x_h^k, a_h^k) \in B_j\} \\
&\le \beta^{-1} \sum_{k=1}^{K} \sum_{h=1}^{H} \sum_{j=1}^{|C_\sigma|} \frac{1}{1 + g(4)\beta^{-1}\mathbf{N}_h^k(B_j)} \mathbb{I}\{\rho[(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] \le 2\sigma\} \mathbb{I}\{(x_h^k, a_h^k) \in B_j\} \\
&\le \beta^{-1} \sum_{h=1}^{H} \sum_{j=1}^{|C_\sigma|} \sum_{k=1}^{K} \frac{\mathbb{I}\{(x_h^k, a_h^k) \in B_j\}}{1 + g(4)\beta^{-1}\mathbf{N}_h^k(B_j)} \le \beta^{-1} \sum_{h=1}^{H} \sum_{j=1}^{|C_\sigma|} \left(1 + \int_{0}^{\mathbf{N}_h^{K+1}(B_j)} \frac{dz}{1 + g(4)\beta^{-1}z}\right) \quad \text{by Lemma 9} \\
&\le \beta^{-1} H |C_\sigma| + \frac{1}{g(4)} \sum_{h=1}^{H} \sum_{j=1}^{|C_\sigma|} \log(1 + g(4)\beta^{-1}\mathbf{N}_h^{K+1}(B_j)) \\
&\le \beta^{-1} H |C_\sigma| + \frac{1}{g(4)} \sum_{h=1}^{H} |C_\sigma| \log\left(\frac{\sum_{j=1}^{|C_\sigma|} (1 + g(4)\beta^{-1}\mathbf{N}_h^{K+1}(B_j))}{|C_\sigma|}\right) \quad \text{by Jensen's inequality} \\
&\le \beta^{-1} H |C_\sigma| + \frac{1}{g(4)} H |C_\sigma| \log\left(1 + \frac{1 + g(4)\beta^{-1}K}{|C_\sigma|}\right) \lesssim H |C_\sigma|.
\end{align*}
$$

<figure><img src="image_7.png" /></figure>

**Theorem 4.** With probability at least $1 - \delta$, the regret of Kernel – UCBVI is bounded as

$$
\begin{gathered}
\mathcal{R}(K) \lesssim H^2 \sqrt{|C_{\sigma}|K} + H^3 |C_{\sigma}| |\tilde{C}_{\sigma}| + H^{3/2} \sqrt{K} + L_1 K H \sigma + H^2 |C_{\sigma}|, \\
\text{where } |C_{\sigma}| \text{ and } |\tilde{C}_{\sigma}| \text{ are the } \sigma\text{-covering numbers of } (\mathcal{X} \times \mathcal{A}, \rho) \text{ and } (\mathcal{X}, \rho_{\mathcal{X}}), \text{ respectively.}
\end{gathered}
$$

*Proof.* The result follows from propositions 5 and 6 and from Hoeffding-Azuma's inequality, which ensures that the term $\sum_{k=1}^{K} \sum_{h=1}^{H} (1 + 1/H)^H \tilde{\xi}_{h+1}^k$ is bounded by

$$ (\sqrt{8e^2H^2 \log(2/\delta)}) \sqrt{KH} $$

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

<figure><img src="image_8.png" /></figure>

D.1. Proof of Corollary 1

Assumption 1 states that $\rho[(x, a), (x', a')] = \rho_{\mathcal{X}}(x, x') + \rho_{\mathcal{A}}(a, a')$, which implies that $|\tilde{C}_{\sigma}| \le |C_{\sigma}|$. Using Theorem 1 and the fact that $|C_{\sigma}| = \mathcal{O}(\sigma^{-d})$, we obtain $\mathcal{R}(K) = \tilde{\mathcal{O}}(H^2\sigma^{-d/2}\sqrt{K} + H^3\sigma^{-2d} + HK\sigma)$. Taking $\sigma = (1/K)^{1/(2d+1)}$, we see that the regret is $\tilde{\mathcal{O}}(H^2K^{\frac{3d+1}{4d+2}} + H^3K^{\frac{2d}{2d+1}})$. The fact that $(3d+1)/(4d+2) \le 2d/(2d+1)$ for $d \ge 1$ allows us to conclude.

E. Remarks & regret bounds in different settings

E.1. Improved regret for stationary MDPs

The regret bound of Kernel-UCBVI can be improved if the MDP is stationary, i.e., $P_1 = \dots = P_H$ and $r_1 = \dots = r_H$. Let $t = kh$ be the total time at step $h$ of episode $k$, and now we index by $t$ all the quantities that were indexed by $(k, h)$, e.g.,
$w_t(x, a) = w_h^k(x, a)$. In the stationary case, the rewards and transitions estimates become

$$ \hat{P}_t(y|x, a) \stackrel{\text{def}}{=} \frac{1}{\mathbf{C}_t(x, a)} \sum_{t'=1}^{t-1} w_{t'}(x, a) \delta_{x_{t'+1}}(y) \quad \text{and} \quad \hat{r}_t(x, a) \stackrel{\text{def}}{=} \frac{1}{\mathbf{C}_t(x, a)} \sum_{t'=1}^{t-1} w_{t'}(x, a) r_{t'} $$

respectively, where we redefine the generalized counts as

$$ \mathbf{C}_t(x, a) \stackrel{\text{def}}{=} \beta + \sum_{t'=1}^{t-1} w_{t'}(x, a). $$

The proofs of the concentration results and of the regret bound remain valid, in particular Proposition 5, up to minor changes in the constants $v_p(k, h)$, $b_p(k, h)$, $v_r(k, h)$, $b_r(k, h)$, $\theta_v(k, h)$ and $\theta_b^1(k, h)$. However, the bounds presented in Proposition 6 can be improved to obtain a better regret bound in terms of the horizon $H$. Consider the sets $B_j$ introduced in the proof of Proposition 6 and let

$$ \mathbf{N}_t(B_j) \stackrel{\text{def}}{=} \sum_{t'=1}^{t-1} \mathbb{I}\{(x_t, a_t) \in B_j\}. $$

As we did in the proof Proposition 6, we can show that $\mathbf{C}_t(\tilde{x}_t, \tilde{a}_t) \ge \beta + g(4)\mathbf{N}_t(B_j)$ if $(x_t, a_t) \in B_j$ and $\rho[(\tilde{x}_t, \tilde{a}_t), (x_t, a_t)] \le 2\sigma$. The sum of the first order terms $\sum_t 1/\sqrt{\mathbf{C}_t(\tilde{x}_t, \tilde{a}_t)}$ is now bounded as

$$ \begin{aligned} & \sum_{t=1}^{KH} \sqrt{\frac{1}{\mathbf{C}_t(\tilde{x}_t, \tilde{a}_t)}} \mathbb{I}\{\rho[(\tilde{x}_t, \tilde{a}_t), (x_t, a_t)] \le 2\sigma\} \\ & \le \beta^{-1} \sum_{j=1}^{|C_\sigma|} \sum_{t=1}^{KH} \frac{\mathbb{I}\{(x_t, a_t) \in B_j\}}{\sqrt{1+g(4)\beta^{-1}\mathbf{N}_t(B_j)}} \\ & \le \beta^{-1} \sum_{j=1}^{|C_\sigma|} \left(1 + \int_0^{\mathbf{N}_{KH+1}(B_j)} \frac{dz}{\sqrt{1+g(4)\beta^{-1}z}}\right) \quad \text{by Lemma 9} \\ & \le \beta^{-1} |C_\sigma| + \frac{2}{g(4)} \sum_{j=1}^{|C_\sigma|} \sqrt{1+g(4)\beta^{-1}\mathbf{N}_{KH+1}(B_j)} \\ & \le \beta^{-1} |C_\sigma| + \frac{2}{g(4)} \sqrt{|C_\sigma|} \sqrt{|C_\sigma| + g(4)\beta^{-1}KH} \quad \text{by Cauchy-Schwarz inequality} \\ & \le \left(\beta^{-1} + \frac{2}{g(4)}\right) |C_\sigma| + \frac{2}{g(4)} \sqrt{g(4)\beta^{-1}|C_\sigma|HK} \\ & = \mathcal{O}\left(|C_\sigma| + \sqrt{|C_\sigma|HK}\right). \end{aligned} $$

When compared to the non-stationary case, where the corresponding sum is bounded by $\mathcal{O}(H|C_\sigma| + H\sqrt{|C_\sigma|K})$, we gain a factor of $\sqrt{H}$ in the term multiplying $\sqrt{K}$ and a factor of $H$ in the term multiplying $|C_\sigma|$.

Similarly, the sum of the second order terms $\sum_t 1/\mathbf{C}_t(\tilde{x}_t, \tilde{a}_t)$ is now bounded as

$$ \begin{aligned} & \sum_{t=1}^{KH} \frac{1}{\mathbf{C}_t(\tilde{x}_t, \tilde{a}_t)} \mathbb{I}\{\rho[(\tilde{x}_t, \tilde{a}_t), (x_t, a_t)] \le 2\sigma\} \\ & \le \beta^{-1} |C_\sigma| + \frac{1}{g(4)} |C_\sigma| \log \left(1 + \frac{1+g(4)\beta^{-1}KH}{|C_\sigma|}\right) \\ & = \tilde{\mathcal{O}}(|C_\sigma|). \end{aligned} $$

In the non-stationary case, the corresponding sum is bounded by $\tilde{\mathcal{O}}(H|C_\sigma|)$, thus we gain a factor of $H$.

Hence, if the MDP is stationary, we obtain a regret bound of

$$ \mathcal{R}_{\text{stationary}}(K) = \tilde{\mathcal{O}}\left(H^{3/2}\sqrt{|C_\sigma|K} + L_1HK\sigma + H^2|C_\sigma|^2\right) $$

which is $\tilde{\mathcal{O}}(H^2K^{\max(\frac{1}{2}, \frac{2d}{2d+1})})$ by taking $\sigma = (1/K)^{1/(2d+1)}$.
### E.1.1. IMPORTANT REMARK

Computationally, in order to achieve this improved regret for Kernel-UCBVI, every time a new transition and a new reward are observed at a step $h$, the estimates $\hat{P}_t(y|x, a)$ and $\hat{r}_t(x, a)$ need to be updated, and the optimistic $Q$-functions need to be recomputed through backward induction, which increases the computational complexity by a factor of $H$.

The UCBVI-CH algorithm of (Azar et al., 2017) in the tabular setting for stationary MDPs also suffers from this problem. If the optimistic $Q$-function is not recomputed at every step $h$, its regret is $\tilde{O}(H^{3/2}\sqrt{XAK} + H^3X^2A)$ and not $\tilde{O}(H^{3/2}\sqrt{XAK} + H^2X^2A)$, where $X$ is the number of states, as claimed in their paper. To see why, let's analyze its second order term, which is $O(H^2X \sum_{k,h} 1/N_k(x_h^k, a_h^k))^{10}$, where $N_k(x, a)$ is the number of visits to $(x, a)$ before episode $k$, i.e.,

$$N_k(x, a) = \max \left( 1, \sum_{h=1}^{H} \sum_{s=1}^{k-1} \mathbb{I} \{(x_h^s, a_h^s) = (x, a)\} \right).$$

If $K \ge XA$, and if $N_k(x, a)$ is updated **only at the end** of each episode, we can show that there exists a sequence $(x_h^k, a_h^k)$ such that the sum $\sum_{k,h} 1/N_k(x_h^k, a_h^k)$ is greater than $HXA$. Let $(x_k, a_k)_{k \in [XA]}$ be $XA$ distinct state-action pairs, and take the sequence $(x_h^k, a_h^k)_{h \in [H], k \in [XA]}$ such that $(x_h^k, a_h^k) = (x_k, a_k)$. That is, in each of the $XA$ episodes, the algorithm visits, in each of the $H$ steps, only one state-action pair that has never been visited before. Since $N_k(x, a)$ is updated only at the end of the episodes, we have $N_k(x_h^k, a_h^k) = 1$ for all $h \in [H]$ and $k \in [XA]$, with this choice of $(x_h^k, a_h^k)_{h,k}$. Hence,

$$H^2 X \sum_{k=1}^{XA} \sum_{h=1}^{H} \frac{1}{N_k(x_h^k, a_h^k)} = H^2 X \sum_{k=1}^{XA} \sum_{h=1}^{H} 1 = H^3 X^2 A.$$

Consequently, the sum of second order term is lower bounded (in a worst case sense) by $H^3X^2A$ and cannot be $\tilde{O}(H^2X^2A)$ as claimed by (Azar et al., 2017), since their bound must hold for any possible sequence $(x_h^k, a_h^k)_{h,k}$. An application of Lemma 9 with $c = H$ can be used to show that the second order term is indeed $\tilde{O}(H^3X^2A)$ when updates are done at the end of the episodes only.

To gain a factor of $H$ (i.e., have $\tilde{O}(H^2X^2A)$ as second order term), one solution is to update the counts $N_k(x_h^k, a_h^k)$ every time a new state-action pair is observed, and recompute the optimistic $Q$-function. Another solution is to recompute it every time the number of visits of the current state-action pair is doubled, as done by (Jaksch et al., 2010) in the average-reward setting.

The efficient version of our algorithm, Greedy-Kernel-UCBVI, does not suffer from this increased computational complexity in the stationary case. This is due to the fact that the value functions are updated in real time, and there is no need to run a backward induction every time a new transition is observed. Hence, in the stationary case, Greedy-Kernel-UCBVI has a regret bound that is $H$ times smaller than in the non-stationary case, without an increase in the computational complexity.

### E.2. Dependence on the Lipschitz constant & regularity w.r.t. the total variation distance

Notice that the regret bound of Kernel-UCBVI has a linear dependency on $L_1$ that appears in the bias term $L_1HK\sigma$:

$$\mathcal{R}(K) \le \tilde{O} \left( H^2 \sqrt{|C_{\sigma}| K} + L_1HK\sigma + H^3 |C_{\sigma}| |\tilde{C}_{\sigma}| + H^2 |C_{\sigma}| \right).$$

As long as the Lipschitz constant $L_1 = \sum_{h=1}^{H} \lambda_{\tau} \lambda_p^{H-h}$ is $O(H)$ or $O(H^2)$, our regret bound has no additional dependency on $H$. However, if $\lambda_p > 1$, the constant $L_1$ can be exponential in $H$. This issue is caused by the smoothness of the MDP and not by algorithmic design. With minor modifications to our proof, we could also consider that the transitions are Lipschitz with respect to the total variation distance, in which case $L_1$ would always be $O(H)$ and the regret of Kernel-UCBVI would remain $\tilde{O}(H^3 K^{\max(\frac{1}{2}, \frac{2d}{2d+1})})$ by taking $\sigma = (1/K)^{1/(2d+1)}$. The regret bounds of other algorithms for Lipschitz MDPs also depend on the Lipschitz constant, which always appears in a bias term (e.g., (Ortner & Ryabko, 2012)).

<footnote n="10">¹⁰See page 7 of (Azar et al., 2017).</footnote>
**Algorithm 3 Greedy-Kernel-UCBVI**

**Input:** global parameters $K, H, \delta, \lambda_r, \lambda_p, \sigma, \beta$
initialize $\mathcal{D}_h = \emptyset$ and $V_h^1(x) = H - h + 1$, for all $h \in [H]$

**for** episode $k = 1, \dots, K$ **do**

get initial state $x_h^k$

**for** step $h = 1, \dots, H$ **do**

// define, for all $a$:

$$ \tilde{Q}_h^k(x_h^k, a) = \sum_{s=1}^{k-1} \tilde{w}_h^s(x_h^k, a) (r_h^s + V_{h+1}^k(x_{h+1}^s)) + \mathbf{B}_h^k(x_h^k, a) $$

$$ \text{execute } a_h^k = \operatorname*{argmax}_a \tilde{Q}_h^k(x_h^k, a) $$

$$ \text{observe } r_h^k \text{ and } x_{h+1}^k $$

$$ \tilde{V}_h^k(x_h^k) = \min \left( H - h + 1, \max_{a \in \mathcal{A}} \tilde{Q}_h^k(x_h^k, a) \right) $$

// interpolate: define $V_h^{k+1}$ for all $x \in \mathcal{D}_h$ as

$$ V_h^{k+1}(x) = \min \left( \min_{s \in [k-1]} [V_h^k(x_h^s) + L_h \rho_X(x, x_h^s)], \tilde{V}_h^k(x_h^k) + L_h \rho_X(x, x_h^k) \right) $$

$$ \text{add } (x_h^k, a_h^k, x_{h+1}^k, r_h^k) \text{ to } \mathcal{D}_h $$

**end for**

**end for**

In addition, the value $L_h = \sum_{h'=h}^H \lambda_r \lambda_p^{H-h'}$ represents simply an upper bound on the Lipschitz constant of the $Q$-function $Q_h^*$. If the functions $Q_h^*$ for $h \in [H]$ are $\tilde{L}_h$-Lipschitz with $\tilde{L}_h$ known and such that $\tilde{L}_h < L_h$, Kernel-UCBVI could exploit the knowledge of $\tilde{L}_h$ and use it instead of $L_h$, which would also improve the regret bound. For instance, if all rewards functions $r_h$ are 0 except for $r_H$, we could use $\tilde{L}_h = \lambda_r$, the Lipschitz constant of $r_H$, which is independent of $H$.

## F. Efficient implementation

In this Appendix, following (Efroni et al., 2019), we show that if we only apply the optimistic Bellman operator once instead of doing a complete value iteration we obtain almost the same guarantees as for Algorithm 1 but with a large improvement in computational complexity. Indeed, the time complexity of each episode $k$ is reduced from $O(k^2)$ to $O(k)$. This complexity is comparable to other model-based algorithm in structured MDPs (e.g., Jin et al., 2020).

The algorithm goes as follows. Assume we are at episode $k$ at step $h$ at state $x_h^k$. To compute the next action we will apply the optimistic Bellman operator to the previous value function. That is, for all $a \in \mathcal{A}$ we compute the upper bounds on the $Q$-value based on a kernel estimator:

$$ \tilde{Q}_h^k(x_h^k, a) = \hat{r}_h^k(x, a) + \hat{P}_h^k V_{h+1}^k(x, a) + \mathbf{B}_h^k(x, a). $$

Then we act greedily

$$ a_h^k = \underset{a \in \mathcal{A}}{\operatorname{argmax}} \tilde{Q}_h^k(x_h^k, a), $$

and define a new optimistic target $\tilde{V}_h^k(x_h^k) = \min(H - h + 1, \tilde{Q}_h^k(x_h^k, a_h^k))$ for the value function at state $x_h^k$. Then we build an optimistic value function $V_h^k$ by interpolating the previous optimistic target and the new one we just defined

$$ \forall x, V_h^{k+1}(x) = \min \left( \min_{s \in [k-1]} [V_h^k(x_h^s) + L_h \rho_X(x, x_h^s)], \tilde{V}_h^k(x_h^k) + L_h \rho_X(x, x_h^k) \right). $$

The complete procedure is detailed in Algorithm 3.

**Proposition 7 (Optimism).** In the event $\mathcal{G}$, whose probability is greater than $1 - \delta$, we have:

$$ \forall (k, h), \forall x, V_h^k(x) \geq V_h^*(x) \text{ and } V_h^k(x) \geq V_h^{k+1}(x). $$

*Proof.* To show that $V_h^k(x) \geq V_h^{k+1}(x)$, notice that

$$ \forall x, V_h^{k+1}(x) = \min \left( V_h^k(x), \tilde{V}_h^k(x_h^k) + L_h \rho_X(x, x_h^k) \right) \leq V_h^k(x) $$

since, by definition, $V_h^k(x) = \min_{s \in [k-1]} [V_h^k(x_h^s) + L_h \rho_X(x, x_h^s)]$.
To show that $V_h^k(x) \ge V_h^*(x)$, we proceed by induction on $k$. For $k = 1$, $V_h^k(x) = H - h \ge V_h^*(x)$ for all $x$ and $h$.

Now, assume that $V_h^{k-1} \ge V_h^*$ for all $h$. As in the proof of Proposition 4, we prove that $V_h^k \ge V_h^*$ by induction on $h$. For $h = H + 1$, $V_h^k(x) = V_h^*(x) = 0$ for all $x$. Now, assume that $V_{h+1}^k(x) \ge V_{h+1}^*(x)$ for all $x$. We have, for all $(x, a)$,

$$ \begin{aligned} \tilde{Q}_h^k(x, a) &= \hat{r}_h^k(x, a) + \hat{P}_h^k V_{h+1}^k(x, a) + \mathbf{B}_h^k(x, a) \\ &\ge \hat{r}_h^k(x, a) + \hat{P}_h^k V_{h+1}^*(x, a) + \mathbf{B}_h^k(x, a) \quad \text{by induction hypothesis on } h \\ &\ge r_h(x, a) + P_h V_{h+1}^*(x, a) = Q_h^*(x, a) \quad \text{in } \mathcal{G} \end{aligned} $$

which implies that $\tilde{V}_h^k(x_h^k) \ge V_h^*(x_h^k)$ and, consequently,

$$ \begin{aligned} \tilde{V}_h^k(x_h^k) + L_h \rho_X (x, x_h^k) &\ge V_h^*(x_h^k) + L_h \rho_X (x, x_h^k) \ge V_h^*(x) \\ \implies V_h^k(x) &= \min \left( V_h^{k-1}(x), \tilde{V}_h^k(x_h^k) + L_h \rho_X (x, x_h^k) \right) \ge V_h^*(x) \quad \text{by induction hypothesis on } k \end{aligned} $$

and we used the fact that $V_h^*$ is $L_h$-Lipschitz.

<figure><img src="image_9.png" /></figure>

**Proposition 8.** With probability at least $1 - \delta$, the regret of Greedy-Kernel-UCBVI is bounded as

$$ \mathcal{R}(K) \lesssim H^2 \sqrt{|\mathcal{C}_\sigma|K} + H^3 |\mathcal{C}_\sigma| |\tilde{\mathcal{C}}_\sigma| + H^{3/2} \sqrt{K} + L_1 K H \sigma + H^2 |\mathcal{C}_\sigma| + H^2 |\tilde{\mathcal{C}}_\sigma|, $$

where $|\mathcal{C}_\sigma|$ and $|\tilde{\mathcal{C}}_\sigma|$ are the $\sigma$-covering numbers of $(\mathcal{X} \times \mathcal{A}, \rho)$ and $(\mathcal{X}, \rho)$, respectively.

*Proof.* On $\mathcal{G}$, we have

$$ \begin{aligned} \tilde{\delta}_h^k &\stackrel{\text{def}}{=} V_h^{k+1}(x_h^k) - V_h^{\pi_k}(x_h^k) \le V_h^k(x_h^k) - V_h^{\pi_k}(x_h^k) \\ &\le \tilde{V}_h^k(x_h^k) - V_h^{\pi_k}(x_h^k) \le \tilde{Q}_h^k(x_h^k, a_h^k) - Q_h^{\pi_k}(x_h^k, a_h^k) \end{aligned} $$

From this point we can follow the proof of Proposition 5 to obtain

$$ \begin{aligned} \delta_h^k &\lesssim \left(1 + \frac{1}{H}\right) (\delta_{h+1}^k + \xi_{h+1}^k) + L_1 \rho \left[ (\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k) \right] + \sqrt{\frac{H^2}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} + \frac{H^2 |\tilde{\mathcal{C}}_\sigma|}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} + L_1 \sigma \\ &\lesssim \left(1 + \frac{1}{H}\right) \left( \tilde{\delta}_{h+1}^k + (V_{h+1}^k - V_{h+1}^{k+1})(x_{h+1}^k) + \xi_{h+1}^k \right) + L_1 \rho \left[ (\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k) \right] \\ &\quad + \sqrt{\frac{H^2}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} + \frac{H^2 |\tilde{\mathcal{C}}_\sigma|}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} + L_1 \sigma \end{aligned} $$

On $\mathcal{G}$, using that $V_h^* \le V_h^{k+1}$ and the same arguments as in equations (7) and (8) in Proposition 5 (which can be used since
$V_{h+1}^k \geq V_{h+1}^{k+1}$), we obtain

$$
\begin{align*}
\mathcal{R}(K) &\leq \sum_{k=1}^{K} \tilde{\delta}_1^k \\
&\leq H^2 |\mathcal{C}_\sigma| + L_1 K H \sigma + \sum_{k=1}^{K} \sum_{h=1}^{H} \left(1 + \frac{1}{H}\right)^h \xi_{h+1}^k \\
&\quad + \sum_{k=1}^{K} \sum_{h=1}^{H} \left( \frac{H}{\sqrt{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} + \frac{H^2 |\tilde{\mathcal{C}}_\sigma|}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} \right) \mathbb{I}\{\rho[(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] \leq 2\sigma\} \\
&\quad + \sum_{k=1}^{K} \sum_{h=1}^{H} \left(1 + \frac{1}{H}\right)^h (V_{h+1}^k - V_{h+1}^{k+1}) (x_{h+1}^k)
\end{align*}
$$

This bound differs only by the last additive term above from the bound given in Proposition 5. Thus we just need to handle
this sum and rely on the previous analysis to upper bound the other terms. We consider the following partition of the state
space:

**Definition 5.** Let $\tilde{\mathcal{C}}_\sigma$ be a $\sigma$-covering of $\mathcal{X}$. We write $\tilde{\mathcal{C}}_\sigma \stackrel{\text{def}}{=} \{x_j, j \in [|\mathcal{C}_\sigma|]\}$. For each $x_j \in \tilde{\mathcal{C}}_\sigma$, we define the set $B_j \subset \mathcal{X}$ as the set of points in $\mathcal{X}$ whose nearest neighbor in $\tilde{\mathcal{C}}_\sigma$ is $x_j$, with ties broken arbitrarily, such that $\{B_j\}_{j \in [|\mathcal{C}_\sigma|]}$ form a partition of $\mathcal{X}$.

Using the fact that the $V_h^k$ are point-wise non-increasing we can transform the last sum in the previous inequality in a telescopic sum

$$
\begin{align*}
\sum_{k=1}^{K} \sum_{h=1}^{H} \left(1 + \frac{1}{H}\right)^h (V_{h+1}^k - V_{h+1}^{k+1}) (x_{h+1}^k) &\le e \sum_{k=1}^{K} \sum_{h=1}^{H} (V_{h+1}^k - V_{h+1}^{k+1}) (x_{h+1}^k) \\
&\le e \sum_{j=1}^{|\tilde{\mathcal{C}}_\sigma|} \sum_{k=1}^{K} \sum_{h=1}^{H} (V_{h+1}^k - V_{h+1}^{k+1}) (x_{h+1}^k) \mathbb{I}\{x_{h+1}^k \in B_j\} \\
&\le e \sum_{j=1}^{|\tilde{\mathcal{C}}_\sigma|} \sum_{k=1}^{K} \sum_{h=1}^{H} (V_{h+1}^k - V_{h+1}^{k+1}) (x_j) \mathbb{I}\{x_{h+1}^k \in B_j\} \\
&\quad + 2L_h \rho_X (x_j, x_{h+1}^k) \mathbb{I}\{x_{h+1}^k \in B_j\} \\
&\le e \sum_{j=1}^{|\tilde{\mathcal{C}}_\sigma|} \sum_{k=1}^{K} \sum_{h=1}^{H} (V_{h+1}^k - V_{h+1}^{k+1}) (x_j) + eK \sum_{h=1}^{H} 2L_1 \sigma \\
&\le eH^2 |\tilde{\mathcal{C}}_\sigma| + 2e\sigma L_1 H K,
\end{align*}
$$

where in the third inequality, we used the fact that the function $V_{h+1}^k - V_{h+1}^{k+1}$ is $2L_h$-Lipschitz. Combining the previous inequalities and the proof of Theorem 4, as explained above, allows us to conclude. $\square$

G. New concentration inequalities

In this section we present two new concentration inequalities that control, uniformly over time, the deviation of weighted sums of zero-mean random variables. They both follow from the so-called method of mixtures (e.g., (Peña et al., 2008)), and can have applications beyond the scope of this work.

**Lemma 2 (Hoeffding type inequality).** Consider the sequences of random variables $(w_t)_{t \in \mathbb{N}^*}$ and $(Y_t)_{t \in \mathbb{N}^*}$ adapted to a filtration $(\mathcal{F}_t)_{t \in \mathbb{N}^*}$. Assume that, for all $t \ge 1$, $w_t$ is $\mathcal{F}_{t-1}$ measurable and $\mathbb{E}[\exp(\lambda Y_t) | \mathcal{F}_{t-1}] \le \exp(\lambda^2 c^2/2)$ for all $\lambda > 0$.
Let

$$S_t \stackrel{\text{def}}{=} \sum_{s=1}^{t} w_s Y_s \quad \text{and} \quad V_t \stackrel{\text{def}}{=} \sum_{s=1}^{t} w_s^2.$$

Then, for any $\beta > 0$, with probability at least $1 - \delta$, for all $t \ge 1$,

$$\frac{|S_t|}{\sum_{s=1}^{t} w_s + \beta} \le \sqrt{2c^2 \left[ \log\left(\frac{1}{\delta}\right) + \frac{1}{2}\log\left(\frac{V_t + \beta}{\beta}\right) \right] \frac{V_t + \beta}{\left(\sum_{s=1}^{t} w_s + \beta\right)^2}}.$$

In addition, if $w_s \le 1$ almost surely for all $s$, we have $V_t \le \sum_{s=1}^{t} w_s \le t$ and the above can be simplified to

$$\frac{|S_t|}{\sum_{s=1}^{t} w_s + \beta} \le \sqrt{2c^2 \log\left(\frac{\sqrt{1+t/\beta}}{\delta}\right) \frac{1}{\sum_{s=1}^{t} w_s + \beta}}.$$

**Proof.** Let

$$M_t^{\lambda} = \exp\left(\lambda S_t - \frac{\lambda^2 c^2 V_t}{2}\right),$$

with the convention $M_0^{\lambda} = 1$. The process $\{M_t^{\lambda}\}_{t \ge 0}$ is a supermartingale, since

$$\mathbb{E}[M_t^{\lambda} | \mathcal{F}_{t-1}] = \mathbb{E} \left[ \exp \left( w_t Y_t - \frac{\lambda^2 c^2 w_t^2}{2} \right) \mid \mathcal{F}_{t-1} \right] M_{t-1}^{\lambda} \le M_{t-1}^{\lambda}, \quad (9)$$

which implies that $\mathbb{E}[M_t^{\lambda}] \le \mathbb{E}[M_0^{\lambda}] = 1$. Now, we apply the method of mixtures, as in (Peña et al., 2008) see also (Abbasi-Yadkori et al., 2011). We define the supermartingale $M_t$ as

$$M_t = \sqrt{\frac{\beta c^2}{2\pi}} \int_{\mathbb{R}} M_t^{\lambda} \exp\left(-\frac{\beta c^2 \lambda^2}{2}\right) d\lambda = \sqrt{\frac{\beta}{V_t + \beta}} \exp\left(\frac{S_t^2}{2(V_t + \beta)c^2}\right).$$

The maximal inequality for non-negative supermartingales gives us:

$$\mathbb{P}[\exists t \ge 0 : M_t \ge \delta^{-1}] \le \delta \mathbb{E}[M_0] = \delta.$$

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

$$\forall t \ge 0, \quad |S_t| \le \sqrt{2c^2 \left[ \log(1/\delta) + \left(\frac{1}{2}\log\left(\frac{V_t + \beta}{\beta}\right)\right)^2 \right]} \quad (V_t + \beta).$$

Dividing both sides by $\sum_{s=1}^{t} w_s + \beta$ gives the result. $\square$

**Lemma 3 (Bernstein type inequality).** Consider the sequences of random variables $(w_t)_{t \in \mathbb{N}^*}$ and $(Y_t)_{t \in \mathbb{N}^*}$ adapted to a filtration $(\mathcal{F}_t)_{t \in \mathbb{N}}$. Let

$$S_t \stackrel{\text{def}}{=} \sum_{s=1}^{t} w_s Y_s, \quad V_t \stackrel{\text{def}}{=} \sum_{s=1}^{t} w_s^2 \mathbb{E} \left[ Y_s^2 \mid \mathcal{F}_{s-1} \right] \quad \text{and} \quad W_t \stackrel{\text{def}}{=} \sum_{s=1}^{t} w_s,$$

and $h(x) = (x + 1) \log(x + 1) - x$. Assume that, for all $t \ge 1$,

* $w_t$ is $\mathcal{F}_{t-1}$ measurable,

* $\mathbb{E}[Y_t | \mathcal{F}_{t-1}] = 0$,

* $w_t \in [0, 1]$ almost surely,
• there exists $b > 0$ such that $|Y_t| \le b$ almost surely.

Then, we have

$$ \mathbb{P} \left[ \exists t \ge 1, (V_t/b^2 + 1)h \left( \frac{b|S_t|}{V_t + b^2} \right) \ge \log(1/\delta) + \log(4e(2t+1)) \right] \le \delta. $$

The previous inequality can be weakened to obtain a more explicit bound: for all $\beta > 0$, with probability at least $1 - \delta$, for all $t \ge 1$,

$$ \frac{|S_t|}{\beta + \sum_{s=1}^{t} w_s} \le \sqrt{\frac{2 \log(4e(2t+1)/\delta)}{(\beta + \sum_{s=1}^{t} w_s)^2} + \frac{2b \log(4e(2t+1)/\delta)}{3 \beta + \sum_{s=1}^{t} w_s}}. $$

*Proof.* By homogeneity we can assume that $b = 1$ to prove the first part. First note that for all $\lambda > 0$,

$$ e^{\lambda w_t Y_t} - \lambda w_t Y_t - 1 \le (w_t Y_t)^2 (e^{\lambda} - \lambda - 1), $$

because the function $y \to (e^y - y - 1)/y^2$ (extended by continuity at zero) is non-decreasing. Taking the expectation yields

$$ \mathbb{E} [e^{\lambda w_t Y_t} | \mathcal{F}_{t-1}] - 1 \le w_t^2 \mathbb{E} [Y_t^2 | \mathcal{F}_{t-1}] (e^{\lambda} - \lambda - 1), $$

thus using $y + 1 \le e^y$ we get

$$ \mathbb{E} [e^{\lambda(w_t Y_t)} | \mathcal{F}_{t-1}] \le e^{w_t^2 \mathbb{E}[Y_t^2 | \mathcal{F}_{t-1}]} (e^{\lambda} - \lambda - 1). $$

We just proved that the following quantity is a supermartingale with respect to the filtration $(\mathcal{F}_t)_{t \ge 0}$,

$$ M_t^{\lambda,+} = e^{\lambda(S_t+V_t)-V_t(e^{\lambda}-1)}. $$

Similarly, using that the same inequality holds for $-X_t$, we have

$$ \mathbb{E} [e^{-\lambda w_t Y_t} | \mathcal{F}_{n-1}] \le e^{w_t^2 \mathbb{E}[Y_t^2 | \mathcal{F}_{n-1}]} (e^{\lambda} - \lambda - 1), $$

thus, we can also define the supermartingale

$$ M_t^{\lambda,-} = e^{\lambda(-S_t+V_t)-V_t(e^{\lambda}-1)}. $$

We now choose the prior over $\lambda_x = \log(x+1)$ with $x \sim \mathcal{E}(1)$, and consider the (mixture) supermartingale

$$ M_t = \frac{1}{2} \int_0^{+\infty} e^{\lambda_x(S_t+V_t)-V_t(e_x^\lambda-1)} e^{-x} dx + \frac{1}{2} \int_0^{+\infty} e^{\lambda_x(-S_t+V_t)-V_n(e_x^\lambda-1)} e^{-x} dx. $$

Note that by construction it holds $\mathbb{E}[M_t] \le 1$. We will apply the method of mixtures to that super martingale thus we need to lower bound it with the quantity of interest. To this aim we will lower bound the integral by the one only around the maximum of the integrand. Using the change of variable $\lambda = \log(1+x)$, we obtain

$$ \begin{aligned} M_t &\ge \frac{1}{2} \int_0^{+\infty} e^{\lambda_x(|S_t|+V_t)-V_t(e^{\lambda_x}-1)} e^{-x} dx \\ &\ge \frac{1}{2} \int_0^{+\infty} e^{\lambda(|S_t|+V_t+1)-(V_t+1)(e^{\lambda}-1)} d\lambda \\ &\ge \frac{1}{2} \int_{\log(|S_t|/(V_t+1)+1)}^{\log(|S_t|/(V_t+1)+1+1/(V_t+1))} e^{\lambda(\log(|S_t|/(V_t+1)+1)-(V_t+1)(e^{\lambda}-1))} d\lambda \\ &\ge \frac{1}{2} \int_{\log(|S_t|/(V_t+1)+1)}^{\log(|S_t|/(V_t+1)+1+1/(V_t+1))} e^{\log(|S_t|/(V_t+1)+1)(|S_t|+V_t+1)-|S_t|-1} d\lambda \\ &= \frac{1}{2e} e^{(V_t+1)h(|S_t|/(V_t+1))} \log\left(1 + \frac{1}{|S_t| + V_t + 1}\right) \ge \frac{1}{4e(2t+1)} e^{(V_t+1)h(|S_t|/(V_t+1))}, \end{aligned} $$
where in the last line we used $log(1 + 1/x) \ge 1/(2x)$ for $x \ge 1$ and the trivial bounds $|S_t| \le 1$, $V_t \le t$. The method of mixtures, see (Peña et al., 2008), allows us to conclude for the first inequality of the lemma. The second inequality is a straightforward consequence of the previous one. Indeed, using that (see Exercise 2.8 of (Boucheron et al., 2013)) for $x \ge 0$

$$h(x) \ge \frac{x^2}{2(1 + x/3)},$$

we get

$$\frac{|S_t|/b}{V_t/b^2 + 1} \le \sqrt{\frac{2 \log (4e(2t+1)/\delta)}{V_t/b^2 + 1}} + \frac{2 \log (4e(2t+1)/\delta)}{3 V_t/b^2 + 1}.$$

Dividing by $\beta + \sum_{s=1}^t w_s$ and multiplying by $b(V_t/b^2 + 1)$ the previous inequality allows us to conclude. □

# H. Auxiliary results

## H.1. Proof of Lemma 1

In this section, we prove that the optimal $Q$-functions $Q_h$ are Lipschitz continuous.

**Lemma 4 (Value functions are Lipschitz continuous). Under assumption 2 we have:**

$$\forall (x, a, x', a'), \forall h \in [H], \quad |Q_h^*(x, a) - Q_h^*(x', a')| \le L_h \rho [(x, a), (x', a')]$$

where $L_h \stackrel{\text{def}}{=} \sum_{h'=h}^H \lambda_r \lambda_p^{H-h'}$.

*Proof.* We proceed by induction. For $h = H$, $Q_h^*(x, a) = r(x, a)$ and the statement is true, since $r$ is $\lambda_r$-Lipschitz. Now, assume that it is true for $h + 1$ and let's prove it for $h$.

First, we note that $V_{h+1}^*(x)$ is Lipschitz by the induction hypothesis:

$$\begin{aligned} V_{h+1}^*(x) - V_{h+1}^*(x') &= \max_a Q_{h+1}^*(x, a) - \max_a Q_{h+1}^*(x', a) \le \max_a (Q_{h+1}^*(x, a) - Q_{h+1}^*(x', a)) \\ &\le \max_a \sum_{h'=h+1}^H \lambda_r \lambda_p^{H-h'} \rho [(x, a), (x', a)] = \sum_{h'=h+1}^H \lambda_r \lambda_p^{H-h'} \rho_X (x, x'), \end{aligned}$$

where, in the last equality, we used the fact that $\rho [(x, a), (x', a')] = \rho_X (x, x') + \rho_A (a, a')$ by Assumption 1.

By applying the same argument and inverting the roles of $x$ and $x'$, we obtain

$$|V_{h+1}^*(x) - V_{h+1}^*(x')| \le \sum_{h'=h+1}^H \lambda_r \lambda_p^{H-h'} \rho_X (x, x').$$

Now, we have

$$\begin{aligned} Q_h^*(x, a) - Q_h^*(x', a') &\le \lambda_r \rho [(x, a), (x', a')] + \int_X V_{h+1}^*(y) (P_h(dy|x, a) - P_h(dy|x', a')) \\ &\le \lambda_r \rho [(x, a), (x', a')] + L_{h+1} \int_X \frac{V_{h+1}^*(y)}{L_{h+1}} (P_h(dy|x, a) - P_h(dy|x', a')) \\ &\le \left[ \lambda_r + \lambda_p \sum_{h'=h+1}^H \lambda_r \lambda_p^{H-h'} \right] \rho [(x, a), (x', a')] = \sum_{h'=h}^H \lambda_r \lambda_p^{H-h'} \rho [(x, a), (x', a')] \end{aligned}$$

where, in last inequality, we use fact that $V_{h+1}^*/L_{h+1}$ is 1-Lipschitz, the definition of the 1-Wasserstein distance and Assumption 2. □
## H.2. Covering-related lemmas

**Lemma 5.** Let $\mathcal{F}_L$ be the set of L-Lipschitz functions from the metric space $(\mathcal{X}, \rho)$ to $[0, H]$. Then, its $\epsilon$-covering number with respect to the infinity norm is bounded as follows

$$ \mathcal{N}(\epsilon, \mathcal{F}_L, \|\cdot\|_{\infty}) \le \left( \frac{8H}{\epsilon} \right)^{\mathcal{N}(\epsilon/(4L), \mathcal{X}, \rho)} $$

*Proof.* Let's build an $\epsilon$-covering of $\mathcal{F}_L$. Let $\mathcal{C}_\mathcal{X} = \{x_1, \dots, x_M\}$ be an $\epsilon_1$-covering of $(\mathcal{X}, \rho)$ such that $\rho(x_i, x_j) > \epsilon_1$ for all $i, j \in [M]$ (i.e., $\mathcal{C}_\mathcal{X}$ is also an $\epsilon_1$-packing). Let $\mathcal{C}_{[0,H]} = \{y_1, \dots, y_N\}$ be an $\epsilon_2$-covering of $[0, H]$. For any function $p: [M] \to [N]$, we build a 2L-Lipschitz function $\hat{f}_p: \mathcal{X} \to \mathbb{R}$ as follows

$$ \hat{f}_p(x) = \min_{i \in [M]} [y_{p(i)} + 2L\rho(x, x_i)]. $$

Let $\epsilon_1 = \epsilon/(4L)$ and $\epsilon_2 = \epsilon/8$. We now show that the set $\mathcal{C}_{\mathcal{F}_L} \stackrel{\text{def}}{=} \{\hat{f}_p: p \text{ is a function from } [M] \text{ to } [N]\}$ is an $\epsilon$-covering of $\mathcal{F}_L$. Take an arbitrary function $f \in \mathcal{F}_L$. Let $p: [M] \to [N]$ be such that $|f(x_i) - y_{p(i)}| \le \epsilon_2$ for all $i \in [M]$. For any $x \in \mathcal{X}$, let $j \in [M]$ be such that $\rho(x, x_j) \le \epsilon_1$. We have

$$ \begin{aligned} |f(x) - \hat{f}_p(x)| & \le |f(x_j) - \hat{f}_p(x_j)| + |f(x) - f(x_j)| + |\hat{f}_p(x_j) - \hat{f}_p(x)| \\ & \le |f(x_j) - \hat{f}_p(x_j)| + 3L\rho(x, x_j) \\ & \le |f(x_j) - y_{p(j)}| + |y_{p(j)} - \hat{f}_p(x_j)| + 3L\epsilon_1 \\ & \le |y_{p(j)} - \hat{f}_p(x_j)| + 3L\epsilon_1 + \epsilon_2. \end{aligned} $$

Now, let's prove that $\hat{f}_p(x_j) = y_{p(j)}$, which is true if and only if $y_{p(j)} \le y_{p(i)} + 2L\rho(x, x_i)$ for all $i \in [M]$. By definition of $p$ and the fact that $f$ is L-Lipschitz, we have $y_{p(j)} \le y_{p(i)} + L\rho(x_j, x_i) + 2\epsilon_2 \le y_{p(i)} + 2L\rho(x_j, x_i)$ for all $i \in [M]$, since $L\rho(x_j, x_i) > L\epsilon_1 = 2\epsilon_2$. Consequently,

$$ \forall x, \quad |f(x) - \hat{f}_p(x)| \le 3L\epsilon_1 + \epsilon_2 < \epsilon $$

which shows that $\mathcal{C}_{\mathcal{F}_L}$ is indeed an $\epsilon$-covering of $\mathcal{F}_L$ whose carnality is bounded by $N^M$. To conclude, we take $\mathcal{C}_{[0,H]} = \{0, \epsilon_2, \dots, N\epsilon_2\}$ for $N = [H/\epsilon_2]$ and $\mathcal{C}_\mathcal{X}$ such that $|\mathcal{C}_\mathcal{X}| = M = \mathcal{N}(\epsilon_1, \mathcal{X}, \rho)$.

For $H = 1$, this result is also given by (Gottlieb et al., 2017), Lemma 5.2. $\square$

**Lemma 6.** Let $(\mathcal{X} \times \mathcal{A}, \rho)$ be a metric space and $(\Omega, \mathcal{T}, \mathbb{P})$ be a probability space. Let $F$ and $G$ be two functions from $\mathcal{X} \times \mathcal{A} \times \Omega$ to $\mathbb{R}$ such that $\omega \to F(x, a, \omega)$ and $\omega \to G(x, a, \omega)$ are random variables. Also, assume that $(x, a) \to F(x, a, \omega)$ and $(x, a) \to G(x, a, \omega)$ are $L_F$ and $L_G$-Lipschitz, respectively, for all $\omega \in \Omega$. If

$$ \forall (x, a), \quad \mathbb{P}[\omega \in \Omega : G(x, a, \omega) \ge F(x, a, \omega)] \le \delta $$

then

$$ \mathbb{P}[\omega \in \Omega : \exists(x, a), G(x, a, \omega) \ge F(x, a, \omega) + (L_G + L_f)\epsilon] \le \delta \mathcal{N}(\epsilon, \mathcal{X} \times \mathcal{A}, \rho). $$

*Proof.* Let $C_\epsilon$ be an $\epsilon$-covering of $(\mathcal{X} \times \mathcal{A}, \rho)$ and let

$$ (x_\epsilon, a_\epsilon) \stackrel{\text{def}}{=} \underset{(x', a') \in C_\epsilon}{\operatorname{argmin}} \rho[(x', a'), (x, a)]. $$

Let $E \stackrel{\text{def}}{=} \{\omega \in \Omega : \exists(x, a), G(x, a, \omega) \ge F(x, a, \omega) + (L_G + L_f)\epsilon\}$. In $E$, we have, for some $(x, a)$,

$$ G(x^\epsilon, a^\epsilon, \omega) + L_G\epsilon \ge G(x, a, \omega) \ge F(x, a, \omega) + (L_G + L_f)\epsilon \ge F(x^\epsilon, a^\epsilon, \omega) + L_G\epsilon. $$
Hence, in E, there exists $(x, a)$ such that:

$$G(x^e, a^e, \omega) \geq F(x^e, a^e, \omega)$$

and

$$ \begin{aligned} \mathbb{P}[E] &\leq \mathbb{P}[\omega \in \Omega : \exists (x^e, a^e) \in C_\epsilon, G(x^e, a^e, \omega) \geq F(x^e, a^e, \omega)] \\ &\leq \sum_{(x^e, a^e) \in C_\epsilon} \mathbb{P}[\omega \in \Omega : G(x^e, a^e, \omega) \geq F(x^e, a^e, \omega)] \leq \sum_{(x^e, a^e) \in C_\epsilon} \delta \end{aligned} $$

which gives us $\mathbb{P}[E] \leq \delta N(\epsilon, \chi \times \mathcal{A}, \rho)$. $\square$

### H.3. Technical lemmas

We state and prove three technical lemmas that help controlling some of the sums that appear in our regret analysis.

**Lemma 7.** Consider a sequence of non-negative real numbers $\{z_s\}_{s=1}^t$ and let $g: \mathbb{R}_+ \to [0, 1]$ satisfy Assumption 3. Let

$$w_s \stackrel{\text{def}}{=} g\left(\frac{z_s}{\sigma}\right) \quad \text{and} \quad \tilde{w}_s \stackrel{\text{def}}{=} \frac{w_s}{\beta + \sum_{s'=1}^t w_{s'}}.$$

for $\beta > 0$. Then, for $t \geq 1$, we have

$$\sum_{s=1}^{t} \tilde{w}_s z_s \leq 2\sigma \left( 1 + \sqrt{\log(C_1^g t / \beta + e)} \right).$$

*Proof.* We split the sum into two terms:

$$\sum_{s=1}^{t} \tilde{w}_s z_s = \sum_{s:z_s<c} \tilde{w}_s z_s + \sum_{s:z_s \geq c} \tilde{w}_s z_s \leq c + \sum_{s:z_s \geq c} \tilde{w}_s z_s$$

From Assumption 3, we have $w_s \leq C_1^g \exp(-z_s^2/(2\sigma^2))$. Hence, $\tilde{w}_s \leq (C_1^g/\beta) \exp(-z_s^2/(2\sigma^2))$, since $\beta + \sum_{s'=1}^t w_{s'} \geq \beta$.

We want to find $c$ such that:

$$z_s \geq c \implies \frac{C_1^g}{\beta} \exp\left(-\frac{z_s^2}{2\sigma^2}\right) \leq \frac{1}{t} \frac{2\sigma^2}{z_s^2}$$

which implies, for $z_s \geq c$, that $\tilde{w}_s \leq \frac{1}{t} \frac{2\sigma^2}{z_s^2}$.

Let $x = z_s^2/2\sigma^2$. Reformulating, we want to find a value $c'$ such that $C_1^g \exp(-x) \leq \beta/(xt)$ for all $x \geq c'$. Let $c' = 2 \log(C_1^g t/\beta + e)$. If $x \geq c'$, we have:

$$ \begin{aligned} \frac{x}{2} &\geq \log\left(\frac{C_1^g t}{\beta} + e\right) \implies x \geq \frac{x}{2} + \log\left(\frac{C_1^g t}{\beta} + e\right) \implies x \geq \log x + \log(C_1^g t/\beta + e) \\ &\implies (C_1^g/\beta) \exp(-x) \leq 1/(xt) \end{aligned} $$

as we wanted. Hence, we choose $c' = 2 \log(C_1^g t/\beta + e)$.

Now, $x \geq c'$ is equivalent to $z_s \geq \sqrt{2\sigma^2 c'} = 2\sigma \sqrt{\log(C_1^g t/\beta + e)}$. Therefore, we take $c = 2\sigma \sqrt{\log(C_1^g t/\beta)}$, which gives us

$$\sum_{s:z_s \geq c} \tilde{w}_s z_s \leq \sum_{s:z_s \geq c} \frac{1}{t} \frac{2\sigma^2}{z_s^2} z_s \leq \frac{2\sigma^2}{t} \sum_{s:z_s \geq c} \frac{1}{z_s} \leq \frac{2\sigma^2}{c} \frac{|\{s: z_s \geq c\}|}{t} \leq \frac{2\sigma^2}{c}$$
Finally, we obtain:

$$
\begin{align*}
\sum_{s=1}^{t} \tilde{w}_s z_s &\le c + \sum_{s: z_s \ge c} \tilde{w}_s z_s \le c + \frac{2\sigma^2}{c} \\
&= 2\sigma \sqrt{\log(C_1^g t/\beta + e)} + \frac{\sigma}{\sqrt{\log(C_1^g t/\beta + e)}} \le 2\sigma \left(1 + \sqrt{\log(C_1^g t/\beta + e)}\right)
\end{align*}
$$

<figure><img src="image_10.png" /></figure>

**Lemma 8.** Let {$y_s$}$_{s=1}^t$ be a sequence of real numbers and let $\sigma > 0$. For $z \in \mathbb{R}_+^t$, let

$$
f_1(z) \stackrel{\text{def}}{=} \frac{\sum_{s=1}^{t} g(z_s/\sigma)y_s}{\beta + \sum_{s=1}^{t} g(z_s/\sigma)}, \quad f_2(z) \stackrel{\text{def}}{=} \sqrt{\frac{1}{\beta + \sum_{s=1}^{t} g(z_s/\sigma)}} \quad \text{and} \quad f_3(z) \stackrel{\text{def}}{=} \frac{1}{\beta + \sum_{s=1}^{t} g(z_s/\sigma)}.
$$

Then, $f_1$, $f_2$ and $f_3$ are Lipschitz continuous with respect to the norm $\|\cdot\|_{\infty}$:

$$
\text{Lip}(f_1) \le \frac{2C_2^g t(\max_s |y_s|)}{\beta\sigma}, \quad \text{Lip}(f_2) \le \frac{C_2^g t}{2\sigma\beta^{3/2}}, \quad \text{Lip}(f_3) \le \frac{C_2^g t}{\sigma\beta^2}
$$

where Lip ($f_i$) denotes the Lipschitz constant of $f_i$, for $i \in \{1, 2, 3\}$.

*Proof.* Using Assumption 3, the partial derivatives of $f_1$ and $f_2$ are bounded as follows

$$
\begin{align*}
\left| \frac{\partial f_1(z)}{\partial z_s} \right| &\le \frac{1}{\sigma} \frac{|g'(z_s/\sigma)| |y_s|}{\beta + \sum_{s=1}^t g(z_s/\sigma)} + \frac{1}{\sigma} \frac{\sum_{s=1}^t g(z_s/\sigma) |y_s|}{\left(\beta + \sum_{s=1}^t g(z_s/\sigma)\right)^2} |g'(z_s/\sigma)| \le \frac{2C_2^g}{\beta\sigma} \max_s |y_s| \\
\left| \frac{\partial f_2(z)}{\partial z_s} \right| &\le \frac{1}{2\sigma} \frac{|g'(z_s/\sigma)|}{\left(\beta + \sum_{s=1}^t g(z_s/\sigma)\right)^{3/2}} \le \frac{C_2^g}{2\sigma\beta^{3/2}} \\
\left| \frac{\partial f_3(z)}{\partial z_s} \right| &\le \frac{1}{\sigma} \frac{|g'(z_s/\sigma)|}{\left(\beta + \sum_{s=1}^t g(z_s/\sigma)\right)^2} \le \frac{C_2^g}{\sigma\beta^2}.
\end{align*}
$$

Therefore,

$$
\|\nabla f_1(z)\|_1 \le \frac{2C_2^g t(\max_s |y_s|)}{\beta\sigma}, \quad \|\nabla f_2(z)\|_1 \le \frac{C_2^g t}{2\sigma\beta^{3/2}}, \quad \|\nabla f_3(z)\|_1 \le \frac{C_2^g t}{\sigma\beta^2}
$$

and the result follows from the fact that $|f_i(z_1) - f_i(z_2)| \le \sup_z \|\nabla f_i(z)\|_1 \|z_1 - z_2\|_\infty$ for $i \in \{1, 2, 3\}$. $\square$

<figure><img src="image_11.png" /></figure>

**Lemma 9.** Consider a sequence {$a_n$}$_{n \ge 1}$ of non-negative numbers such that $a_m \le c$ for some constant $c > 0$. Let $A_t = \sum_{n=1}^{t-1} a_n$. Then, for any $b > 0$ and any $p > 0$,

$$
\sum_{t=1}^{T} \frac{a_t}{(1 + bA_t)^p} \le c + \int_{0}^{A_{T+1}-c} \frac{1}{(1 + bz)^p} dz
$$
Proof. Let $n \stackrel{\text{def}}{=} \max\{t: a_1 + \dots + a_{t-1} \le c\}$. We have $\sum_{t=1}^{n-1} \frac{a_t}{(1+bA_t)^p} \le \sum_{t=1}^{n-1} a_t \le c$ and, consequently,

$$ 
\begin{align*}
\sum_{t=1}^{T} \frac{a_t}{(1+bA_t)^p} &\le c + \sum_{t=n}^{T} \frac{a_t}{(1+bA_t)^p} = c + \sum_{t=n}^{T} \frac{A_{t+1}-A_t}{(1+bA_t)^p} \\
&= c + \sum_{t=n}^{T} \frac{A_{t+1}-A_t}{(1+bA_{t+1}-bA_t)^p} \le c + \sum_{t=n}^{T} \frac{A_{t+1}-A_t}{(1+b(A_{t+1}-c))^p} \\
&= c + \sum_{t=n}^{T} \int_{A_t}^{A_{t+1}} \frac{1}{(1+b(A_{t+1}-c))^p} dz \le c + \sum_{t=n}^{T} \int_{A_t}^{A_{t+1}} \frac{1}{(1+b(z-c))^p} dz \\
&= c + \int_{A_n}^{A_{T+1}} \frac{1}{(1+b(z-c))^p} dz \le c + \int_{c}^{A_{T+1}} \frac{1}{(1+b(z-c))^p} dz.
\end{align*}
$$

□

# I. Experimental setup

For Kernel-UCBVI, we used the following simplified exploration bonuses:

$$ \mathbf{B}_h^k(x, a) = \frac{1}{\sqrt{\mathbf{C}_h^k(x, a)}} + \frac{H-h+1}{\mathbf{C}_h^k(x, a)}. $$

The same bonus was used for the baselines, except that $\mathbf{C}_h^k(x, a)$ was replaced by $\mathbf{N}_h^k(I(x), a) = \max(1, \sum_{s=1}^{k-1} I\{I(x_s) = I(x), a_s^s = a\})$ where $I(x)$ is the index of the discrete state corresponding to the continuous state $x$.

We used the Euclidean distance on the states and the Gaussian kernel function $g(z) = \exp(-z^2/2)$. The regularization was taken as $\beta = 0.01$.

Additionally, in Kernel-UCBVI, we used representative states (Kveton & Theocharous, 2012; Barreto et al., 2016) to merge states that are at a distance smaller than 0.05 from each other, which provides a great improvement in the runtime of the algorithm.