# A kernel-based approach to non-stationary reinforcement learning in metric spaces

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. A kernel-based approach to non-stationary reinforcement learning in metric spaces. International Conference on Artificial Intelligence and Statistics, Apr 2021, San Diego / Virtual, United States. hal-03289026

HAL Id: hal-03289026

https://inria.hal.science/hal-03289026

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.
# A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces

Omar D. Domingues<fnref n="1" />,² Pierre Ménard³ Matteo Pirotta⁴ Emilie Kaufmann<fnref n="1" />,²,⁵ Michal Valko<fnref n="1" />,⁶

¹Inria Lille ²Université de Lille ³OvGU ⁴Facebook AI Research ⁵CNRS ⁶DeepMind Paris

## Abstract

In this work, we propose *KeRNS*: an algorithm for episodic reinforcement learning in non-stationary Markov Decision Processes (MDPs) whose state-action set is endowed with a metric. Using a non-parametric model of the MDP built with time-dependent kernels, we prove a regret bound that scales with the covering dimension of the state-action space and the total variation of the MDP with time, which quantifies its level of non-stationarity. Our method generalizes previous approaches based on sliding windows and exponential discounting used to handle changing environments. We further propose a practical implementation of *KeRNS*, we analyze its regret and validate it experimentally.

## 1 Introduction

In reinforcement learning (RL), an agent interacts with an environment by sequentially taking actions, receiving rewards and observing state transitions. One of the main challenges in RL is the trade-off between exploration, the act of gathering information about the environment, and exploitation, the act of using the current knowledge to maximize the sum of rewards. In non-stationary environments, handling this trade-off becomes much harder: what has been learned in the past may no longer be valid in the present. Therefore, the agent needs to constantly re-explore previously known parts of the environment to discover possible changes. In this work, we propose *KeRNS*,<fnref n="1" /> an algorithm that handles this problem by acting optimistically and by

forgetting data that are far in the past, which naturally causes the agent to keep exploring to discover changes. *KeRNS* relies on non-parametric kernel estimators of the MDP, and the non-stationarity is handled by using time-dependent kernels.

The regret of an algorithm, defined as the difference between the rewards obtained by an optimal agent and the ones obtained by the algorithm, allows us to quantify how well an agent balances exploration and exploitation. We prove a regret bound for *KeRNS* that holds in a challenging setting, where the state-action space can be continuous and the environment can change in every episode, as long as the cumulative changes remain small when compared to the total number of episodes.

**Related work** Regret bounds for RL in stationary environments have been extensively studied in finite (tabular) MDPs (Jaksch et al., 2010; Azar et al., 2017; Dann et al., 2017; Jin et al., 2018; Zanette and Brunskill, 2019), and also in metric spaces under Lipschitz continuity assumptions (Ortner and Ryabko, 2012; Song and Sun, 2019; Sinclair et al., 2019; Domingues et al., 2020; Sinclair et al., 2020). Recent works provide algorithms with regret bounds for non-stationary RL in the tabular setting (Gajane et al., 2018; Ortner et al., 2019; Cheung et al., 2020). These algorithms estimate the transitions and the rewards in an episode *k* using the data observed up to episode *k* − 1. However, since the MDP can change from one episode to another, these estimators are *biased*. If nothing is done to handle this bias, the algorithms will suffer a linear regret (Ortner et al., 2019) that depends on the magnitude of the bias. To deal with this issue, different approaches have been proposed: Gajane et al. (2018) and Cheung et al. (2020) use sliding windows to compute estimators that use only the most recently observed transitions, whereas Ortner et al. (2019) restart the algorithm periodically and, after each restart, new estimators are built and past data are discarded. In the multi-armed bandit literature, in addition to sliding windows, exponential discounting has also been used as a mean to give more importance to recent data (Kocsis and Szepesvári, 2006;

<footnote n="1">¹meaning *Kernel-based Reinforcement Learning in Non-Stationary environments*.</footnote>
Garivier and Moulines, 2011; Russac et al., 2019). In this paper, we study the dynamic regret of the algorithm, where, in each episode k, we compare the learner to the optimal policy of the MDP in episode k. A related approach consists in comparing the performance of the learner to the best stationary policy in hindsight, e.g., (Even-Dar et al., 2009; Yu and Mannor, 2009; Neu et al., 2013; Dick et al., 2014), which is less suited to non-stationary environments, since the performance of any fixed policy can be very bad. Non-stationary RL has also been studied outside the regret minimization framework, without, however, tackling the issue of exploration. For instance, Choi et al. (2000) propose a model where the MDP varies according to a sequence of tasks whose changes form a Markov chain. Szita et al. (2002) and Csáji and Monostori (2008) study the convergence of Q-learning when the environment changes but remain close to a fixed MDP. Assuming full knowledge of the MDP at each time step, but with unknown evolution, Lecarpentier and Rachelson (2019) introduce a risk-averse approach to planning in slowly changing environments. In a related setting, Lykouris et al. (2019) study episodic RL problems where the MDP can be corrupted by an adversary and provide regret bounds in this case.

**Contributions** We provide the first regret bound for non-stationary RL in continuous environments. More precisely, we show that the Kernel-UCBVI algorithm of Domingues et al. (2020), based on non-parametric kernel smoothing, can be modified to tackle non-stationary environments by using appropriate time- and space-dependent kernels. We analyze the resulting algorithm, KeRNS, under mild assumptions on the kernel, which in particular recover previously studied forgetting mechanisms to tackle non-stationarity in bandits and RL: sliding windows (Gajane et al., 2018) and exponential discounting (Kocsis and Szepesvári, 2006; Garivier and Moulines, 2011; Russac et al., 2019), and allow for combinations between those. On the practical side, kernel-based approaches can be very computationally demanding since their complexity grows with the number of data points. Building on the notion of representative states, promoted in previous work on practical kernel-based RL (Kveton and Theocharous, 2012; Barreto et al., 2016) we propose an efficient version of KeRNS, called RS-KeRNS, which has constant runtime per episode. We analyze the regret of RS-KeRNS, showing that it enables a trade-off between regret and runtime, and we validate this algorithm empirically.

## 2 Setting

**Notation** For any $n \in \mathbb{N}^*$, let $[n] \stackrel{\text{def}}{=} \{1, \dots, n\}$. If $\mu$ and $P(\cdot|x, a)$ are measures for any $(x, a)$ and $f$ is an

arbitrary function, we define $\mu f \stackrel{\text{def}}{=} \int f(y)d\mu(y)$ and $Pf(x, a) \stackrel{\text{def}}{=} \int f(y)dP(y|x, a)^2$.

**Non-stationary MDPs** We consider an episodic RL setting where, in each episode $k \in [K]$, an agent interacts with the environment for $H \in \mathbb{N}^*$ time steps. The time is indexed by $(k, h)$, where $k$ represents an episode and $h$ the time step within the episode. The environment is modeled as a non-stationary MDP, defined by the tuple $(\mathcal{X}, \mathcal{A}, r, P)$, where $\mathcal{X}$ is the state space, $\mathcal{A}$ is the action space, $r = \{r_h^k\}_{k,h}$ and $P = \{P_h^k\}_{k,h}$ are sets of reward functions and transition kernels, respectively. More precisely, when taking action $a$ in state $x$ at time $(k, h)$, the agent observes a random reward $\tilde{r}_h^k \in [0, 1]$ with mean $r_h^k(x, a)$ and makes a transition to the next state according to the probability measure $P_h^k(\cdot|x, a)$. A deterministic policy $\pi$ is a mapping from $[H] \times \mathcal{X}$ to $\mathcal{A}$, and we denote by $\pi(h, x)$ the action chosen in state $x$ at step $h$. The action-value function of a policy $\pi$ in step $h$ of episode $k$ is defined as

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

where $x_{h'+1} \sim P_{h'}^k(\cdot|x_{h'}, a_{h'})$, $a_{h'} = \pi(h', x)$, and its value function is defined by $V_{k,h}^\pi(x) = Q_{k,h}^\pi(x, \pi(h, x))$. The optimal value functions, $V_{k,h}^*(x) \stackrel{\text{def}}{=} \sup_\pi V_{k,h}^\pi(x)$ satisfy the Bellman equations (Puterman, 2014)

$$V_{k,h}^*(x) = \max_{a \in \mathcal{A}} Q_{k,h}^*(x, a), \text{ where}$$

$$Q_{k,h}^*(x, a) \stackrel{\text{def}}{=} r_h^k(x, a) + P_h^k V_{k,h+1}^*(x, a)$$

and where $V_{k,H+1}^* = 0$ by definition.

**Dynamic regret** The agent interacts with the environment in a sequence of episodes and, in each episode $k$, it uses a policy $\pi_k$ that can be chosen based on its observations from previous episodes. We measure its performance by the dynamic regret, defined as the sum over all episodes of the difference between the optimal value function in episode $k$ and the value of $\pi_k$:

$$\mathcal{R}(K) \stackrel{\text{def}}{=} \sum_{k=1}^{K} \left( V_{k,1}^*(x_1^k) - V_{k,1}^{\pi_k}(x_1^k) \right)$$

where $x_1^k$ is the starting state in each episode, which is chosen arbitrarily and given to the learner.

**Assumptions** Since regret lower bounds scale with the number of states and actions (Jaksch et al., 2010), structural assumptions are needed in order to enable

<footnote n="2">²See also Table 2 in Appendix A summarizing the main notations used in the paper and in the proofs.</footnote>
learning in continuous MDPs. A common assumption is that rewards and transitions are Lipschitz continuous with respect to some known metric (Ortner and Ryabko, 2012; Song and Sun, 2019; Domingues et al., 2020; Sinclair et al., 2020), which is the approach that we follow in this work. We make no assumptions regarding how the MDP changes, and our regret bounds will be expressed in terms of its total variation over time.

**Assumption 1.** The state-action space $\mathcal{X} \times \mathcal{A}$ is equipped with a metric $\rho: (\mathcal{X} \times \mathcal{A})^2 \to \mathbb{R}_+$, which is given to the learner. Also, we assume that there exists a metric $\rho_{\mathcal{X}}$ on $\mathcal{X}$ such that, for all $(x, x', a)$, $\rho[(x, a), (x', a)] \le \rho_{\mathcal{X}}(x, x')$.<fnref n="3" />

**Assumption 2.** The reward functions are $L_r$-Lipschitz and the transition kernels are $L_p$-Lipschitz with respect to the 1-Wasserstein distance: $\forall(x, a, x', a')$ and $\forall(k, h) \in [K] \times [H]$,

$$|r_h^k(x, a) - r_h^k(x', a')| \le L_r \rho[(x, a), (x', a')], \quad \text{and} \\ \mathbb{W}_1(P_h^k(\cdot|x, a), P_h^k(\cdot|x', a')) \le L_p \rho[(x, a), (x', a')]$$

where, for two measures $\mu$ and $\nu$, we have $\mathbb{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 any Lipschitz function $f: \mathcal{X} \to \mathbb{R}$ with respect to $\rho_{\mathcal{X}}$, $\text{Lip}(f)$ denotes its Lipschitz constant.

**Assumption 3.** For any $(k, h)$, the optimal $Q$-function $Q_{k,h}^*$ is $L$-Lipschitz with respect to $\rho$. Assumptions 1 and 2 imply that $L \le \sum_{h=1}^H L_r L_p^{H-h}$ (Lemma 26 in the Appendix).

# 3 An Algorithm for Kernel-Based RL in Non-Stationary Environments

In this section, we introduce KeRNS, a model-based RL algorithm for learning in non-stationary MDPs. In each episode $k$, we estimate the transitions and the rewards using the data observed up to episode $k-1$. Using exploration bonuses that represent the uncertainty in the estimated model, KeRNS builds a $Q$-function $Q_h^k$, and plays the greedy policy with respect to it. KeRNS generalizes sliding-window and exponential discounting approaches by considering time-dependent kernel functions, which also allow us to handle exploration in continuous environments (Domingues et al., 2020).

## 3.1 Kernel-Based Estimators for Changing MDPs

Let $\Gamma: \mathbb{N} \times (\mathcal{X} \times \mathcal{A})^2 \to [0, 1]$ be a non-stationary kernel function, where $\Gamma(t, u, v)$ represents the similarity

between two state action pairs $u, v$ in $\mathcal{X} \times \mathcal{A}$ visited at an interval $t$.

**Definition 1 (kernel weights).** Let $(x_h^s, a_h^s)$ be the state-action pair visited at time $(s, h)$. For any $(x, a) \in \mathcal{X} \times \mathcal{A}$ and $s < k$, we define the weights and the normalized weights at time $(k, h)$ as

$$w_h^{k,s}(x, a) \stackrel{\text{def}}{=} \Gamma(k-s-1, (x, a), (x_h^s, a_h^s))$$

and $\tilde{w}_h^{k,s}(x, a) \stackrel{\text{def}}{=} w_h^{k,s}(x, a)/C_h^k(x, a)$, where $C_h^k(x, a) \stackrel{\text{def}}{=} \beta + \sum_{s=1}^{k-1} w_h^{k,s}(x, a)$ and $\beta > 0$ is a regularization parameter.

Using the kernel function $\Gamma$ and past data, KeRNS builds estimators $\hat{r}_h^k$ of the reward function and $\hat{P}_h^k$ of the transitions at time $(k, h)$, which are defined below.

**Definition 2 (empirical MDP).** At time $(s, h) \in [K] \times [H]$, let $(x_h^s, a_h^s, x_{h+1}^s, \tilde{r}_h^s)$ represent the state, the action, the next state and the reward observed by the algorithm. Before each episode $k$, KeRNS estimates the rewards and transitions using the data observed up to episode $k-1$:

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

where $\delta_{x_{h+1}^s}$ is the Dirac measure at $x$. Let $\hat{\mathcal{M}}_k$ be the MDP whose rewards and transitions at step $h$ are $\hat{r}_h^k(x, a)$ and $\hat{P}_h^k(y|x, a)$.<fnref n="4" />

The weights $w_h^{k,s}(x, a)$ measure the influence that the transitions and rewards observed at time $(s, h)$ will have on the estimators for the state-action pair $(x, a)$ at time $(k, h)$. Their sum, $C_h^k(x, a)$, is a proxy for the number of visits to $(x, a)$. Intuitively, the kernel function $\Gamma$ must be designed in order to ensure that $w_h^{k,s}(x, a)$ is small when $(x, a)$ is very far from $(x_h^s, a_h^s)$, with respect to the distance $\rho$. It must also be small when $k-s-1$ is large, which means that the sample $(x_h^s, a_h^s)$ was collected too far in the past and should have a small impact on the estimators. For our theoretical analysis, we will need the assumptions below on the kernel function $\Gamma$.

**Assumption 4 (kernel properties).** Let $\sigma > 0$, $\eta \in [0, 1[$ and $W \in \mathbb{N}$ be the kernel parameters. For each set of parameters, we assume that we have access to a base kernel function $\bar{\Gamma}_{(\eta, W)}: \mathbb{N} \times \mathbb{R} \to [0, 1]$ and we define, for any $t, u, v \in \mathbb{N}^* \times \mathcal{X} \times \mathcal{A}$,

$$\Gamma(t, u, v) = \bar{\Gamma}_{(\eta, W)}(t, \rho[u, v] / \sigma).$$

<footnote n="3">³If $(\mathcal{A}, \rho_{\mathcal{A}})$ is also a metric space, we can take $\rho[(x, a), (x', a')] = \rho_{\mathcal{X}}(x, x') + \rho_{\mathcal{A}}(a, a')$, for instance. See Section 2.3 of Sinclair et al. (2019) for more examples and a discussion.</footnote>

<footnote n="4">⁴Since the normalized weights do not sum to 1, $\hat{P}_h^k$ is not a probability kernel. In this case, we suffer a bias of order $\beta$ and the property that $\hat{P}_h^k$ is a sub-probability measure is enough for the analysis.</footnote>
We assume that $z \mapsto \bar{\Gamma}_{(\eta, W)}(t, z)$ is non-increasing for any $t \in \mathbb{N}$. Additionally, we assume that there exists positive constants $C_1, C_2$, a constant $C_3 \ge 0$ and an arbitrary function $G: \mathbb{R} \to \mathbb{R}_{\ge 0}$ that satisfies $G(4) > 0$ such that

$$ (1) \quad \forall (t, z), \bar{\Gamma}_{(\eta, W)}(t, z) \le C_1 \exp(-z^2/2) $$

$$ (2) \quad \forall (t, y, z), |\bar{\Gamma}_{(\eta, W)}(t, y) - \bar{\Gamma}_{(\eta, W)}(t, z)| \le C_2 |y - z| $$

$$ (3) \quad \forall z, \bar{\Gamma}_{(\eta, W)}(t, z) \le C_3 \eta^t, \quad \text{for all } t \ge W $$

$$ (4) \quad \forall z, \bar{\Gamma}_{(\eta, W)}(t, z) \ge G(z) \eta^t, \quad \text{for all } t < W. $$

We now provide some justification for these conditions. (1) ensures that the bias due to kernel smoothing remains bounded by $\tilde{\mathcal{O}}(\sigma)$ (Lemma 23); (2) ensures smoothness conditions that are needed to provide concentration inequalities for the rewards and transitions (Lemma 24); (3) and (4) allow us to control the bias and the variance due to non-stationarity, respectively (Lemmas 2 and 16). Intuitively, (3) says the algorithm should forget data further than $W$ episodes in the past, and (4) says that recent data in the $W$ most recent episodes must have a minimum weight. The condition $G(4) > 0$ is mostly technical: it is used to ensure that $C_h^k(x, a)$ is not too small in a $4\sigma$-neighborhood of $(x, a)$ (see lemmas 15 and 16). The kernels in the example below satisfy our conditions, and show that they indeed generalize sliding-window and exponential discounting approaches:

**Example 1 (sliding-window and exponential discount).** The kernels $\bar{\Gamma}_{(\eta, W)}(t, z) = \mathbb{I}\{t < W\} \exp(-|z|^p/2)$ (sliding-window) and $\bar{\Gamma}_{(\eta, W)}(t, z) = \eta^t \exp(-|z|^p/2)$ (exponential discount) satisfy Assumption 4 for $p \ge 2$.

The conditions in Assumption 4 are needed to prove our regret bounds. However, if one has further knowledge about the MDP and its changes, this information can also be integrated to the kernel function $\Gamma$. For example, if the MDP only changes in certain region of the state-action space, the kernel can be designed to forget past data only in that region. Also, the kernel $\Gamma$ can be designed to enforce restarts, as proposed by Ortner et al. (2019) for finite MDPs, by setting $\Gamma(t, u, v)$ to zero every time $t$ exceeds a certain threshold. Although this would require a separate analysis, our proof could be combined to the one of (Ortner et al., 2019) to obtain a regret bound in this case.

## 3.2 Algorithm

KeRNS is presented in Algorithm 1. At time $(k, h)$, let $\mathbb{B}_h^k(x, a)$ be the exploration bonus at $(x, a)$ representing

the uncertainty of $\tilde{\mathcal{M}}_k$ with respect to the true MDP:

$$ \mathbb{B}_h^k(x, a) = \tilde{\mathcal{O}} \left( \frac{H}{\sqrt{\mathbb{C}_h^k(x, a)}} + \frac{\beta H}{\mathbb{C}_h^k(x, a)} + L\sigma \right) \quad (1) $$

where $\tilde{\mathcal{O}}(\cdot)$ hides logarithmic terms. The exact expression for the bonuses is given in Def. 5 in Appendix A. Before starting episode $k$, KeRNS computes, for all $h \in [H]$, the values $Q_h^k$ by running backward induction on $\tilde{\mathcal{M}}_k$, with the bonus $\mathbb{B}_h^k(x, a)$ added to the rewards, followed by an interpolation step:

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

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

$$ V_h^k(x) = \min(H - h + 1, \max_a Q_h^k(x, a)) $$

where $V_{H+1}^k \stackrel{\text{def}}{=} 0$. The interpolation is needed to ensure that $Q_h^k$ and $V_h^k$ are L-Lipschitz. This procedure is defined in detail in Algorithm 3 in Appendix A, which is the same kind of backward induction used by Kernel-UCBVI (Domingues et al., 2020). Once $Q_h^k$ is computed, KeRNS plays the greedy policy associated to it. Notice that, although $Q_h^k(x, a)$ and $V_h^k(x)$ are defined for all $(x, a)$, they only need to be computed for the states and actions observed by the algorithm up to episode $k$.

### Algorithm 1 KeRNS

1: **Input:** $K, H, L, L_r, L_p, \beta, \delta, d, \sigma, \eta, W$.

2: **Initialize history:** $\mathcal{T}_h = \emptyset$ for all $h \in [H]$.

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

4: get initial state $x_1^k$

5: // Run kernel backward induction

6: compute $(Q_h^k)_h$ using $(\mathcal{T}_h)_h$ and Algorithm 3.

7: **for** $h=1, \dots, H$ **do**

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

9: observe reward $\tilde{r}_h^k$ and next state $x_{h+1}^k$

10: store transition $\mathcal{T}_h = \mathcal{T}_h \cup \{x_h^k, a_h^k, x_{h+1}^k, \tilde{r}_h^k\}$

11: **end for**

12: **end for**

## 3.3 Theoretical guarantees

We introduce $\Delta$, the total variation of the MDP in $K$ episodes:

**Definition 3 (MDP variation).** We define $\Delta = \Delta^r + L\Delta^p$, where

$$ \Delta^r \stackrel{\text{def}}{=} \sum_{i=1}^{K} \sum_{h=1}^{H} \sup_{x,a} |r_h^i(x, a) - r_h^{i+1}(x, a)|, $$

$$ \Delta^p \stackrel{\text{def}}{=} \sum_{i=1}^{K} \sum_{h=1}^{H} \sup_{x,a} \mathbb{W}_1 \left( P_h^i(\cdot|x, a), P_h^{i+1}(\cdot|x, a) \right) $$
A similar notion has been introduced, for instance, by Ortner et al. (2019); Li and Li (2019) for MDPs and by Besbes et al. (2014) for multi-armed bandits. Here, the difference is that we use the Wasserstein distance to define the variation of the transitions, instead of the total variation (TV) distance $||P_h^t(\cdot|x, a) - P_h^{t+1}(\cdot|x, a)||_1$. This choice was made in order to take into account the metric $\rho$ when measuring changes in the environment: our results would be analogous if we had chosen the TV distance.<fnref n="5" />

Using the same algorithm, we provide two regret bounds for KeRNS, which are given below. The notation $\lesssim$ omits constants and logarithmic terms (see Definition 4 in Appendix A).

**Theorem 1.** The regret of KeRNS is bounded as $\mathcal{R}^{\text{KeRNS}}(K) \lesssim \min(\mathcal{R}_1(K), \mathcal{R}_2(K)) + \text{bias}(\sigma, \eta, W, \Delta)$, where

$$ \begin{aligned} \mathcal{R}_1(K) &= H^2 K \sqrt{\log \frac{1}{\eta} \sqrt{|\mathcal{C}'_\sigma| |\mathcal{C}_\sigma|}} + H^2 |\mathcal{C}_\sigma| K \log \frac{1}{\eta} \\ \mathcal{R}_2(K) &= H^2 K \sqrt{\log \frac{1}{\eta} \sqrt{|\mathcal{C}_\sigma|}} + H^3 |\mathcal{C}_\sigma| |\mathcal{C}'_\sigma| K \log \frac{1}{\eta} \\ \text{bias}(\sigma, \eta, W, \Delta) &= W \Delta H + \frac{\eta^W}{1-\eta} KH^3 + LKH\sigma \end{aligned} $$

with probability at least $1 - \delta$. Here, $|\mathcal{C}'_\sigma|$ and $|\mathcal{C}_\sigma|$ are the $\sigma$-covering numbers of $(\mathcal{X}, \rho_\sigma)$ and $(\mathcal{X} \times \mathcal{A}, \rho)$ respectively, $(\sigma, \eta, W)$ are the kernel parameters.

*Proof.* This result comes from combining theorems 3 and 4 in Appendix F. See Section 5 for a proof outline.

As discussed below, after optimizing the kernel parameters (Table 1), the bound $\mathcal{R}_1$ has a worse dependence on $K$, and a better dependence on $\Delta$. On the other hand, $\mathcal{R}_2$ is better with respect to $K$, but worse in $\Delta$. Concretely, this trade-off may give hints on how to choose the kernel parameters according to the amount of variation that we expect to see in the environment. Technically, the difference comes from how we handle the concentration of the transitions in the proof. To obtain $\mathcal{R}_1$, we use concentration inequalities on the term $|(\hat{P}_h^k - P_h^k)f|$ for all functions $f$ that are bounded and Lipschitz continuous. To obtain $\mathcal{R}_2$, the concentration is done only for $f = V_{k,h+1}^*$, but this results in larger second-order terms, as in (Azar et al., 2017; Domingues et al., 2020).

**Corollary 1.** Let $d$ be the covering dimension of $(\mathcal{X} \times \mathcal{A}, \rho)$. By optimizing the kernel parameters, we obtain the regret bounds in Table 1. Table 3 in Appendix B.2 gives the values of $(\sigma, \eta, W)$ that yield these bounds.

*Proof.* Assuming that $|\mathcal{C}'_\sigma| \le |\mathcal{C}_\sigma|$, we have that $|\mathcal{C}_\sigma|$ and $|\mathcal{C}'_\sigma|$ are $O(1/\sigma^d)$. Then, the bounds follow from

**Theorem 1.** The general case, handling separately the covering dimensions of $(\mathcal{X} \times \mathcal{A}, \rho)$ and $(\mathcal{X}, \rho_\mathcal{X})$, is stated in corollaries 6 and 9 in Appendix F.

**Discussion** We now discuss regret bounds for optimized kernel parameters, according to the covering dimension of $(\mathcal{X} \times \mathcal{A}, \rho)$, denoted by $d$. Roughly, the covering dimension is the smallest number $d \ge 0$ such that the $\sigma$-covering number $|\mathcal{C}_\sigma|$ is $O(1/\sigma^d)$.<fnref n="6" /> We consider two cases: the tabular (finite MDP) case, where the covering dimension of $(\mathcal{X} \times \mathcal{A}, \rho)$ is $d=0$, and the continuous case, where $d > 0$.

**Tabular case** Let $X = |\mathcal{X}|$ and $A = |\mathcal{A}|$. By taking $\sigma=0$, we have $|\mathcal{C}'_\sigma| = X$ and $|\mathcal{C}_\sigma| = XA$. As shown in Table 1, the $\mathcal{R}_1$ bound states that the regret of KeRNS is $\tilde{O}(H^2 X \sqrt{A \Delta^{\frac{1}{3}} K^{\frac{2}{3}}})$. This bound matches the one proved by Ortner et al. (2019) for the average reward setting using restarts, up to a factor of $H^{\frac{2}{3}}$ coming from our episodic setting, where the transitions $P_h^k$ depend on $h$. The $\mathcal{R}_2$ bound states that the regret of KeRNS can be improved to $\tilde{O}(H^2 \sqrt{X A \Delta^{\frac{1}{3}} K^{\frac{2}{3}}})$, up to second-order terms. In the bandit case ($H=1$), these bounds are optimal in terms of $K$ and $\Delta$ (Besbes et al., 2014).

**Continuous case** For $d > 0$, we prove the first dynamic regret bounds in our setting, which are of order $H^2 \Delta^{\frac{1}{3}} K^{\frac{2d+2}{2d+3}}$ (better in $\Delta$) or $H^2 \Delta^{\frac{1}{2}} K^{\frac{2d+1}{2d+2}}$ (better in $K$) for two different tunings of the kernel. Deriving a lower bound in the non-stationary case for $d > 0$ is an open problem, even for multi-armed bandits. As a sanity-check, we note that in stationary MDPs, for which $\Delta = 0$, we recover the regret bound of Kernel-UCBVI<fnref n="7" /> (Domingues et al., 2020) of $H^3 K^{\frac{2d}{2d+1}}$ from the bound $\mathcal{R}_2$ with $\log(1/\eta) = 1/K$, $W \to \infty$ and $\sigma = K^{-\frac{1}{2d+1}}$, which is optimal for $d=1$ in the (stationary) bandit case (Bubeck et al., 2011).

In tabular MDPs, we may achieve sub-linear regret as long as $\Delta < K$.<fnref n="8" /> In the continuous case however, our bounds show that we might need $\Delta < K^{\frac{3}{2d+3}}$ (for the $\mathcal{R}_1$ bound) or $\Delta < K^{\frac{1}{d+1}}$ (for the $\mathcal{R}_2$ bound) in order to avoid a linear regret, which is an immediate consequence of the bounds in Table 1.

**Knowledge of $\Delta$** To optimally choose the kernel parameters, KeRNS requires an upper bound on the

<footnote n="5">⁵More precisely, in the proof of Corollary 2, the Wasserstein distance could be replaced by the TV distance.</footnote>

<footnote n="6">⁶For more details about covering numbers and covering dimension, see Section 3 of Kleinberg et al. (2019) and Section 2.2 of Sinclair et al. (2019).</footnote>

<footnote n="7">⁷Another choice of $\eta$ might allow us to avoid the dependence on $H^3$ of Kernel-UCBVI and get $H^2$ instead.</footnote>

<footnote n="8">⁸Notice that, if $\Delta$ scales linearly with the number of episodes $K$, we cannot expect to learn. Indeed, according to the lower bound (Besbes et al., 2014), the regret is necessarily linear in this case.</footnote>
<table><caption>Table 1: Regret for optimized kernel parameters.</caption><thead><tr><th></th><th>bound</th><th>regret</th></tr></thead><tbody><tr><td rowspan="2">d = 0</td><td>R<sub>1</sub></td><td>H<sup>2</sup>X√AΔ<sup>1/3</sup>K<sup>2/3</sup></td></tr><tr><td>R<sub>2</sub></td><td>H<sup>2</sup>√XΔΔ<sup>1/3</sup>K<sup>2/3</sup> + H<sup>3</sup>X<sup>2</sup>AΔ<sup>2/3</sup>K<sup>1/3</sup></td></tr><tr><td rowspan="2">d > 0</td><td>R<sub>1</sub></td><td>H<sup>2</sup>Δ<sup>1/3</sup>K<sup>2d<sup>2</sup>+2</sup></td></tr><tr><td>R<sub>2</sub></td><td>H<sup>2</sup>Δ<sup>1/2</sup>K<sup>2d<sup>2</sup>+1</sup> + H<sup>3</sup>Δ<sup>1/4</sup>K<sup>3/4</sup></td></tr></tbody></table>

variation $\Delta$. Recent work has started to tackle this issue in bandit algorithms (Chen et al., 2019; Auer et al., 2019), and finite MDPs using sliding windows (Cheung et al., 2020). Their extension to continuous MDPs is left to future work.

# 4 Efficient Implementation

Since KeRNS uses non-parametric kernel estimators, its computational complexity scales with the number of observed transitions. Let $\tau_A$ be the time required to compute the maximum of $a \mapsto Q_h^k(x, a)$. Similarly to Kernel-UCBVI, its total space complexity is $O(KH)$ and its time complexity per episode $k$ is $O(Hk^2 + H\tau_A k)$, resulting in a total runtime of $O(HK^3 + H\tau_A K^2)$. This runtime is very prohibitive in practice, especially in changing environments, where we might need to run the algorithm for a very long time. Domingues et al. (2020) propose a version of Kernel-UCBVI with improved per-episode time complexity of $O(H\tau_A k)$ based on real-time dynamic programming (RTDP) (Barto et al., 1995; Efroni et al., 2019). However, this requires the upper bounds $V_h^k$ to be non-increasing, which is not the case in KeRNS, since $V_h^k$ increases in regions that were not visited recently. This property is necessary to promote extra exploration and adapt to possible changes. Additionally, the RTDP-based approach of Domingues et al. (2020) still has a time complexity that scales with time, which can be a considerable issue in practice. Here, we propose an alternative to run KeRNS in constant time per episode, while controlling the impact of this speed-up on the regret.

## 4.1 Using Representative States and Actions

As proposed by Kveton and Theocharous (2012) and Barreto et al. (2016), we take an approach based on using representative states to construct an algorithm called RS-KeRNS (for KeRNS on Representative States). In each episode $k$, RS-KeRNS keeps and updates sets of representative states $\tilde{X}_h$, actions $\tilde{A}_h$ and next-states $\tilde{Y}_h$, for each $h$, whose cardinalities are denoted by $\tilde{X}_h$, $\tilde{A}_h$ and $\tilde{Y}_h$, respectively. For simplicity, we omit the dependence on $k$ of these sets and their cardinal-

ities. Every time a new transition $\{x_h^k, a_h^k, x_{h+1}^k, \tilde{r}_h^k\}$ is observed, the representative sets are updated using Algorithm 2, which ensures that any two representative state-action pairs are at a distance greater than $\varepsilon$ from each other. Similarly, it ensures that any pair of representative next-states are at a distance greater than $\varepsilon_\chi$ from each other. Then, $(x_h^k, a_h^k)$ and $x_{h+1}^k$ are mapped to their nearest neighbors in $\tilde{X}_h \times \tilde{A}_h$ and $\tilde{Y}_h$, respectively, and the estimators of the rewards and transitions are updated. Consequently, we build a finite MDP, denoted by $\tilde{M}_k$, with $\tilde{X}_h$ states, $\tilde{A}_h$ actions and $\tilde{Y}_h$ next-states, per stage $h$. The rewards and transitions of $\tilde{M}_k$ can be stored in arrays of size $\tilde{X}_h \tilde{A}_h$ and $\tilde{X}_h \tilde{A}_h \tilde{Y}_h$, for each $h$.

RS-KeRNS is described precisely in Algorithm 4 in Appendix G. It computes a $Q$-function for all $(\bar{x}, \bar{a}) \in \cup_h \tilde{X}_h \times \tilde{A}_h$ by running backward induction in $\tilde{M}_k$, which is then extended to any $(x, a) \in \mathcal{X} \times \mathcal{A}$ by performing an interpolation step, as in KeRNS. In Appendix G, we explain how the rewards and transitions estimators of $\tilde{M}_k$ can be updated online. Below, we provide regret and runtime guarantees for this efficient implementation.

**Algorithm 2 Update Representative Sets**

1: **Input:** $k, h, \tilde{X}_h, \tilde{A}_h, \tilde{Y}_h, \{x_h^k, a_h^k, x_{h+1}^k\}, \varepsilon, \varepsilon_\chi$.

2: **if** $\min_{(\bar{x}, \bar{a}) \in \tilde{X}_h \times \tilde{A}_h} \rho[(\bar{x}, \bar{a}), (x_h^k, a_h^k)] > \varepsilon$ **then**

3: $\tilde{X}_h = \tilde{X}_h \cup \{x_h^k\}, \tilde{A}_h = \tilde{A}_h \cup \{a_h^k\}$

4: **end if**

5: **if** $\min_{\tilde{y} \in \tilde{Y}_h} \rho_\chi(\bar{x}, x_{h+1}^k) > \varepsilon_\chi$ **then**

6: $\tilde{Y}_h = \tilde{Y}_h \cup \{x_{h+1}^k\}$

7: **end if**

## 4.2 Theoretical Guarantees & Runtime

Theorem 2 states that RS-KeRNS enjoys the same regret bounds as KeRNS plus a bias term that can be controlled by $\varepsilon$ and $\varepsilon_\chi$, as long as we use a Gaussian kernel.

**Theorem 2 (regret of RS-KeRNS).** Let $\chi_{(\eta, W)}: \mathbb{N} \to [0, 1]$, $u, v \in \mathcal{X} \times \mathcal{A}$, and consider the kernel

$$ \Gamma(t, u, v) = \chi_{(\eta, W)}(t) \exp \left( -\rho[u, v]^2 / (2\sigma^2) \right) $$

assumed to satisfy Assumption 4. With this choice of kernel, the regret of RS-KeRNS is bounded by

$$ \mathcal{R}(K) \lesssim \mathcal{R}^{\text{KeRNS}}(K) + L(\varepsilon + \varepsilon_\chi)KH^2 + \frac{\varepsilon}{\sigma}KH^3 $$

with probability at least $1 - \delta$, where $\mathcal{R}^{\text{KeRNS}}$ is regret bound of KeRNS given in Theorem 1.

*Proof.* This result comes from theorems 5 and 6 in Appendix G. See Appendix B for a proof outline.
**Lemma 1** (runtime of RS-KeRNS). Consider the kernel defined in Theorem 2, and let $(\alpha_i)_{i \ge 1}$ be a sequence of real numbers in $[0, 1]$. If we take $\chi_{(\eta, W)}(t) = \prod_{i=1}^t \alpha_i$, the per-episode runtime of RS-KeRNS is bounded by

$$ \mathcal{O}(H \min(k^2, |C_{\varepsilon}| |C'_{\varepsilon_{\chi}}|) + H \min(k, |C'_{\varepsilon_{\chi}}|) \tau_A), $$

where $|C_{\varepsilon}|$ is the $\varepsilon$-covering number of $(\mathcal{X} \times \mathcal{A}, \rho)$, $|C'_{\varepsilon_{\chi}}|$ is the $\varepsilon_{\chi}$-covering number of $(\mathcal{X}, \rho)$, and $\tau_A$ is the time required to compute the maximum of a $\mapsto Q_h^k(x, a)$. In particular, we can take $\alpha_i = \eta$ for all $i$, which gives an exponential-discount strategy for handling non-stationarity.

*Proof.* By construction, in any episode $k$, we have $\bar{X}_h \bar{A}_h \le \min(k, |C_{\varepsilon}|)$ and $\bar{Y}_h \le \min(k, |C'_{\varepsilon_{\chi}}|)$. Backward induction (Algorithm 5) is performed in $\mathcal{O}(\sum_h \bar{X}_h \bar{A}_h \bar{Y}_h + \tau_A \sum_h \bar{Y}_h)$ time, and the choice of $\chi_{(\eta, W)}(t)$ implies that the model updates can be done in $\mathcal{O}(\sum_h \bar{X}_h \bar{A}_h \bar{Y}_h)$ time, as detailed in Appendix G.2.

Consequently, the constants $\varepsilon$ and $\varepsilon_{\chi}$ provide a trade-off between regret and computational complexity. Since $|C_{\varepsilon}| = \mathcal{O}(\varepsilon^{-d_1})$ and $|C'_{\varepsilon_{\chi}}| = \mathcal{O}(\varepsilon^{-d_2})$, increasing $(\varepsilon, \varepsilon_{\chi})$ may reduce exponentially the runtime of RS-KeRNS, while having only a linear increase in its regret.

Kveton and Theocharous (2012) and Barreto et al. (2016) studied the idea of using representative states to accelerate kernel-based RL (KBRL), but we provide the first regret bounds in this setting. More precisely, our result improves previous work in the following aspects: (i) Kveton and Theocharous (2012) and Barreto et al. (2016) do not tackle exploration and do not have finite-time analyses: they provide approximate versions of the KBRL algorithm of Ormoneit and Sen (2002) which has asymptotic guarantees assuming that transitions are generated from independent samples; (ii) The error bounds of Kveton and Theocharous (2012) scale with $\exp(1/\sigma^2)$. In our online setting, $\sigma$ can be chosen as a function of the horizon $K$, and their bound could result in an error that scales exponentially with $K$, instead of linearly, as ours. Our result comes from an improved analysis of the smoothness of kernel estimators, that leverages the regularization constant $\beta$ (Lemma 25); (iii) Barreto et al. (2016) propose an algorithm that also builds a set of representative states in an online way. However, their theoretical guarantees only hold when this set is fixed, i.e., cannot be updated during exploration, whereas our bounds hold in this case; (iv) unlike (Kveton and Theocharous, 2012; Barreto et al., 2016), our theoretical results also hold in continuous action spaces.

## 4.3 Numerical Validation

To illustrate the behavior of RS-KeRNS, we consider a continuous MDP whose state-space is the unit

ball in $\mathbb{R}^2$ with four actions, representing a move to the right, left, up or down. The agent starts at $(0, 0)$. Let $b_i^k \in \{0, 0.25, 0.5, 0.75, 1\}$ and $x_i \in \{(0.8, 0.0), (0.0, 0.8), (-0.8, 0.0), (0.0, -0.8)\}$. We consider the following mean reward function:

$$ r_h^k(x, a) = \sum_{i=1}^{4} b_i^k \max \left( 0, 1 - \frac{\|x - x_i\|_2}{0.5} \right) $$

which do not depend on $h$. Every $N$ episodes, the coefficients $b_i^k$ are changed, which impact the optimal policy.

<figure><img src="image_1.png" /><figcaption>Figure 1: Performance of RS-KeRNS compared to baselines for $N = 2000$. Average over 4 runs.</figcaption></figure>

Taking $\eta = \exp(-(1/N)^{2/3})$, we used the kernel $\Gamma(t, u, v) = \eta^t \exp(-(\rho[u, v]/\sigma)^4/2)$. We set $\sigma = 0.05$, $\varepsilon = \varepsilon_{\chi} = 0.1$, $\beta = 0.01$, $H = 15$ and ran the algorithm for $2 \times 10^4$ episodes. KeRNS was compared to two baselines: (i) Kernel-UCBVI combined with representative states, that we call RS-Kernel-UCBVI, which is designed for stationary environments. This corresponds to RS-KeRNS with $\chi(t) = 1$, that is, $\eta = 1$; (ii) A restart-based algorithm, called RestartBaseline, which is implemented as RS-Kernel-UCBVI, but it has full information about when the environment changes, and, at every change, it restarts its reward estimator and its bonuses. We can see that, as expected, RS-KeRNS outperforms RS-Kernel-UCBVI, which was not designed for non-stationary environments, and is able to “track” the behavior of the restart-based algorithm which has full information about how the environment changes. In Appendix I, we give more details about the experimental setup and provide more experiments, varying the period $N$ of changes in the MDP and the kernel function.

# 5 Proof Outline

We now outline the proof of Theorem 1 assuming, for simplicity, that the rewards are known.
**Bias due to non-stationarity** To bound the bias, we introduce an average MDP with transitions $\bar{P}_h^k$:

$$ \bar{P}_h^k(y|x, a) \stackrel{\text{def}}{=} \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) P_h^s(y|x, a) + \frac{\beta P_h^k(y|x, a)}{\mathbf{C}_h^k(x, a)}, $$

where $(P_h^s)_{s,h}$ are the true transitions at time $(s, h)$. We prove that, for any L-Lipschitz function $f$ bounded by $H$, (Corollary 2):

$$ \left| (\bar{P}_h^k - \bar{P}_h^k) f(x, a) \right| \leq \mathbf{bias}_p(k, h) $$

where the term $\mathbf{bias}_p(k, h)$ is defined as

$$ L \sum_{i=1 \lor (k-W)}^{k-1} \sup_{x,a} \mathbb{W}_1 (\bar{P}_h^i(\cdot|x, a), \bar{P}_h^{i+1}(\cdot|x, a)) + \frac{2C_3H}{\beta} \frac{\eta^W}{1-\eta}. $$

**Concentration** Using concentration inequalities for weighted sums, we prove that $\bar{P}_h^k$ is close to the average transition $\bar{P}_h^k$ using Hoeffding- and Bernstein-type inequalities (lemmas 5, 6, 7, and 8), and define an event $\mathcal{G}$ where our confidence sets hold (Lemma 9), such that $\mathbb{P}[\mathcal{G}] \geq 1 - \delta/2$. For instance, Lemma 5 gives us

$$ \left| (\bar{P}_h^k - \bar{P}_h^k) V_{k,h+1}^*(x, a) \right| \lesssim \sqrt{\frac{H^2}{\mathbf{C}_h^k(x, a)}} + \frac{\beta H}{\mathbf{C}_h^k(x, a)} + L\sigma, $$

which explains the form of the exploration bonuses.

**Upper bound on the true value function** On the event $\mathcal{G}$, we show that (Lemma 10):

$$ Q_h^k(x, a) + \sum_{h'=h}^{H} \mathbf{bias}(k, h) \geq Q_{k,h}^*(x, a) $$

where the term $\mathbf{bias}(k, h)$ is the sum of $\mathbf{bias}_p(k, h)$ defined above, and a similar term representing the bias in the reward estimation.

**Regret bounds** Let $(\tilde{x}_h^k, \tilde{a}_h^k)$ be the state-action pair among the previously visited ones that is the closest to $(x_h^k, a_h^k)$:

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

We show that (see proof of Lemma 11):

$$ H \sum_{k=1}^{K} \sum_{h=1}^{H} \mathbb{I}\{\rho[(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] > 2\sigma\} \leq H^2 |\mathcal{C}_\sigma|. $$

Thus, to simplify the outline, for all $(k, h)$, we assume that $\rho[(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] \leq 2\sigma$ and add $H^2 |\mathcal{C}_\sigma|$ to the

final regret bound. On the event $\mathcal{G}$, we prove that the regret of KeRNS is bounded by (lemmas 11 and 12):

$$ \mathcal{R}(K) \lesssim \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{\beta H}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} \right) + \sum_{k=1}^{K} \sum_{h=1}^{H} \mathbf{bias}(k, h) + LKH\sigma + H^2 |\mathcal{C}_\sigma| $$

where we omitted factors involving $|\mathcal{C}_\sigma|$ and $|\mathcal{C}_\sigma'|$ (which depend on the type of bound considered, $\mathcal{R}_1$ or $\mathcal{R}_2$), and martingale terms (which are bounded by $\approx H^{3/2}\sqrt{K}$ with probability at least $1 - \delta/2$).

Using the properties of the kernel $\Gamma$ (Assumption 4), we prove that (Lemma 16):

$$ \sum_{k=1}^{K} \sum_{h=1}^{H} \frac{1}{\sqrt{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} \lesssim HK \log \frac{1}{\eta} \left( |\mathcal{C}_\sigma| + \sqrt{\frac{|\mathcal{C}_\sigma|}{\log(1/\eta)}} \right) \\ \sum_{k=1}^{K} \sum_{h=1}^{H} \frac{1}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} \lesssim H |\mathcal{C}_\sigma| K \log \frac{1}{\eta} $$

Finally, in Corollary 5, we prove that the bias $\sum_{k=1}^{K} \sum_{h=1}^{H} \mathbf{bias}(h, k)$ is bounded by

$$ 2W (\Delta^r + L\Delta^p) + \frac{2C_3(H+1)KH}{\beta} \frac{\eta^W}{1-\eta}. $$

Putting these bounds together, we prove Theorem 1. The proof of Theorem 2 is outlined in Appendix B.

# 6 Conclusion

In this paper, we introduced and analyzed KeRNS, the first algorithm for continuous MDPs with dynamic regret guarantees in changing environments. Building upon previous work on using representative states for kernel-based RL, we proposed RS-KeRNS, a practical version of KeRNS that runs in constant time per episode. Moreover, we provide the first analysis that quantifies the trade-off between the regret and the computational complexity of this approach. In discrete environments, our regret bound matches the existing lower bound for multi-armed bandits in terms of the number of episodes and the variation of MDP, whereas finding a lower bound in continuous environments remains an open problem.

We believe that the ideas introduced in this paper might be useful for large-scale problems. Indeed, we provide stronger online guarantees for practical kernel-based RL, which has already been shown to be empirically
successful in medium-scale environments ($d \approx 10$) (Kve-
ton and Theocharous, 2012; Barreto et al., 2016), and
we show that kernel-based RL is naturally suited to
tackle non-stationarity. In larger dimension, kernel-
based exploration bonuses have been recently shown
to enhance exploration in RL for Atari games (Badia
et al., 2020), and our approach might inspire the de-
sign of bonuses for high-dimensional non-stationary
environments.

Acknowledgements

The research presented was supported by European
CHIST-ERA project DELTA, French Ministry of
Higher Education and Research, Nord-Pas-de-Calais
Regional Council, French National Research Agency
project BOLD (ANR19-CE23-0026-04), FMJH PGMO
project 2018-0045, and the SFI Sachsen-Anhalt for the
project RE-BCI ZS/2019/10/102024 by the Investi-
tionsbank Sachsen-Anhalt.

References

Auer, P., Gajane, P., and Ortner, R. (2019). Adaptively tracking the best bandit arm with an unknown number of distribution changes. In *Conference on Learning Theory*, pages 138–158.

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

Badia, A. P., Sprechmann, P., Vitvitskyi, A., Guo, D., Piot, B., Kapturowski, S., Tieleman, O., Arjovsky, M., Pritzel, A., Bolt, A., and Blundell, C. (2020). Never give up: Learning directed exploration strategies. In *International Conference on Learning Representations*.

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

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

Besbes, O., Gur, Y., and Zeevi, A. (2014). Stochastic multi-armed-bandit problem with non-stationary rewards. In *Advances in neural information processing systems*, pages 199–207.

Bubeck, S., Munos, R., Stoltz, G., and Szepesvári, C. (2011). X-armed bandits. *Journal of Machine Learning Research*, 12:1587–1627.

Chen, Y., Lee, C.-W., Luo, H., and Wei, C.-Y. (2019). A new algorithm for non-stationary contextual ban-

dits: Efficient, optimal and parameter-free. In *Conference on Learning Theory*, pages 696–726. PMLR.

Cheung, W. C., Simchi-Levi, D., and Zhu, R. (2020). Reinforcement learning for non-stationary Markov decision processes: The blessing of (More) optimism. In *Proceedings of the 37th International Conference on Machine Learning*.

Choi, S. P., Yeung, D.-Y., and Zhang, N. L. (2000). Hidden-mode markov decision processes for nonstationary sequential decision making. In *Sequence Learning*, pages 264–287. Springer.

Csáji, B. C. and Monostori, L. (2008). Value function based reinforcement learning in changingrovian environments. *Journal of Machine Learning Research*, 9(Aug):1679–1709.

Dann, C., Lattimore, T., and Brunskill, E. (2017). Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. In *Advances in Neural Information Processing Systems*, pages 5713–5723.

Dick, T., Gyorgy, A., and Szepesvari, C. (2014). Online learning in markov decision processes with changing cost sequences. In *International Conference on Machine Learning*, pages 512–520. PMLR.

Domingues, O. D., Ménard, P., Pirotta, M., Kaufmann, E., and Valko, M. (2020). Regret Bounds for Kernel-Based Reinforcement Learning. *arXiv e-prints*, page arXiv:2004.05599.

Efroni, Y., Merlis, N., Ghavamzadeh, M., and Man-
nor, S. (2019). Tight regret bounds for model-based
reinforcement learning with greedy policies. In *Adv-
vances in Neural Information Processing Systems*,
pages 12203–12213.

Even-Dar, E., Kakade, S. M., and Mansour, Y. (2009). Online markov decision processes. *Mathematics of Operations Research*, 34(3):726–736.

Gajane, P., Ortner, R., and Auer, P. (2018). A sliding-window algorithm for markov decision processes with arbitrarily changing rewards and transitions. *arXiv preprint arXiv:1805.10066*.

Garivier, A. and Moulines, E. (2011). On Upper-Confidence Bound Policies For Switching Bandit Problems. In *Algorithmic Learning Theory (ALT)*, pages 174–188. PMLR.

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

Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. (2018). Is Q-learning provably efficient? In *Advances in Neural Information Processing Systems*, pages 4863–4873.
Kleinberg, R., Slivkins, A., and Upfal, E. (2019). Bandits and experts in metric spaces. *Journal of the ACM (JACM)*, 66(4):1–77.

Kocsis, L. and Szepesvári, C. (2006). Discounted UCB. In *2nd PASCAL Challenges Workshop*.

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

Lecarpentier, E. and Rachelson, E. (2019). Non-stationary markov decision processes, a worst-case approach using model-based reinforcement learning. In *Advances in Neural Information Processing Systems*, pages 7214–7223.

Li, Y. and Li, N. (2019). Online learning for markov decision processes in nonstationary environments: A dynamic regret analysis. In *2019 American Control Conference (ACC)*, pages 1232–1237. IEEE.

Lykouris, T., Simchowitz, M., Slivkins, A., and Sun, W. (2019). Corruption robust exploration in episodic reinforcement learning. *arXiv preprint arXiv:1911.08689*.

Neu, G., György, A., Szepesvari, C., and Antos, A. (2013). Online markov decision processes under bandit feedback. *IEEE Transactions on Automatic Control*, 59(3):676–691.

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

Ortner, R., Gajane, P., and Auer, P. (2019). Variational regret bounds for reinforcement learning. In *Proceedings of the 35th Conference on Uncertainty in Artificial Intelligence*.

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

Puterman, M. L. (2014). *Markov decision processes: discrete stochastic dynamic programming*. John Wiley & Sons.

Russac, Y., Vernade, C., and Cappé, O. (2019). Weighted linear bandits for non-stationary environments. In *Advances in Neural Information Processing Systems*, pages 12017–12026.

Sinclair, S., Wang, T., Jain, G., Banerjee, S., and Yu, C. (2020). Adaptive discretization for model-based reinforcement learning. In *Advances in Neural Information Processing Systems*, pages 3858–3871.

Sinclair, S. R., Banerjee, S., and Yu, C. L. (2019). Adaptive discretization for episodic reinforcement learning in metric spaces. *Proceedings of the ACM*

on *Measurement and Analysis of Computing Systems*, 3(3):1–44.

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

Szita, I., Takács, B., and Lörincz, A. (2002). ε-mdps: Learning in varying environments. *Journal of Machine Learning Research*, 3(Aug):145–174.

Yu, J. Y. and Mannor, S. (2009). Online learning in markov decision processes with arbitrarily changing rewards and transitions. In *2009 international conference on game theory for networks*, pages 314–322. IEEE.

Zanette, A. and Brunskill, E. (2019). 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*.
# Appendix

## Table of Contents

<table><tr><td>A Preliminaries</td><td>12</td></tr><tr><td>A.1 Notation</td><td>12</td></tr><tr><td>A.2 Probabilistic model</td><td>13</td></tr><tr><td>A.3 Exploration Bonuses and Kernel Backward Induction</td><td>13</td></tr><tr><td>B Proof Outline</td><td>15</td></tr><tr><td>B.1 Theorem 2</td><td>15</td></tr><tr><td>B.2 Optimized Kernel Parameters and Regret Bounds</td><td>16</td></tr><tr><td>C Handling the bias due to non-stationarity</td><td>17</td></tr><tr><td>D Concentration</td><td>19</td></tr><tr><td>D.1 Concentration inequalities for weighted sums</td><td>19</td></tr><tr><td>D.2 Hoeffding-type concentration inequalities</td><td>19</td></tr><tr><td>D.3 Bernstein-type concentration inequality</td><td>23</td></tr><tr><td>D.4 Good event</td><td>26</td></tr><tr><td>E Upper bound on true value function</td><td>27</td></tr><tr><td>F Regret bounds</td><td>29</td></tr><tr><td>F.1 Regret bound in terms of the sum of exploration bonuses (UCRL-type)</td><td>29</td></tr><tr><td>F.2 Regret bound in terms of the sum of exploration bonuses (UCBVI-type)</td><td>32</td></tr><tr><td>F.3 Bounding the sum of bonuses and bias</td><td>34</td></tr><tr><td>F.4 Final regret bounds</td><td>38</td></tr><tr><td>G RS-KeRNS: An efficient version of KeRNS using representative states</td><td>41</td></tr><tr><td>G.1 Definitions</td><td>41</td></tr><tr><td>G.2 Online updates & runtime</td><td>44</td></tr><tr><td>G.3 Regret analysis</td><td>45</td></tr><tr><td>H Technical Lemmas</td><td>57</td></tr><tr><td>I Experiments</td><td>61</td></tr><tr><td>I.1 Setup</td><td>61</td></tr><tr><td>I.2 Results</td><td>61</td></tr></table>
# A Preliminaries

## A.1 Notation

Throughout the proof, we use the following notation when omitting constants and logarithmic terms:

**Definition 4.**

$$A \lesssim B \iff A \le B \times \text{polynomial}(d_1, d_2, \log(K), \log(1/\delta), \beta, 1/\beta, L_r, L_p).$$

Table 2 summarizes the main notations used in the paper and in the proofs.

<table><caption>Table 2: Table of notations</caption><thead><tr><th>Notation</th><th>Meaning</th></tr></thead><tbody><tr><td>ρ : (X × A)<sup>2</sup> → R<sub>+</sub></td><td>metric on the state-action space X × A</td></tr><tr><td>ρ<sub>X</sub> : X<sup>2</sup> → R<sub>+</sub></td><td>metric on the state space X</td></tr><tr><td>N(ε, X × A, ρ)</td><td>ε-covering number of the metric space (X × A, ρ)</td></tr><tr><td>K</td><td>number of episodes</td></tr><tr><td>H</td><td>horizon, length of each episode</td></tr><tr><td>δ</td><td>confidence parameter</td></tr><tr><td>σ</td><td>kernel bandwidth parameter</td></tr><tr><td>η</td><td>kernel temporal decay parameter</td></tr><tr><td>W</td><td>kernel temporal window parameter</td></tr><tr><td>β</td><td>regularization parameter</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><tr><td>L<sub>r</sub>, L<sub>p</sub>, L</td><td>Lipschitz constants of the rewards, transitions and value functions</td></tr><tr><td>Γ</td><td>kernel function from N<sup>*</sup> × (X × A)<sup>2</sup> to [0, 1]</td></tr><tr><td>Γ<sub>(η,W)</sub></td><td>parameterized kernel function from N<sup>*</sup> × R<sub>+</sub> to [0, 1]</td></tr><tr><td>C<sub>1</sub>, C<sub>2</sub>, C<sub>3</sub></td><td>constants related to kernel properties, see Assumption 4</td></tr><tr><td>G : R<sub>+</sub> → R<sub>+</sub></td><td>function related to kernel properties, see Assumption 4</td></tr><tr><td>M<sub>k</sub></td><td>true MDP at episode k, with rewards r<sub>h</sub><sup>k</sup> and transitions P<sub>h</sub><sup>k</sup></td></tr><tr><td>μ̂<sub>k</sub></td><td>empirical MDP built by KeRNS in episode k</td></tr><tr><td>w<sub>h</sub><sup>k,s</sup>(x, a)</td><td>weight at (x, a) in at time (k, h) w.r.t the sample (x<sub>h</sub><sup>s</sup>, a<sub>h</sub><sup>s</sup>) (Def. 1)</td></tr><tr><td>⟨w<sub>h</sub><sup>k,s</sup>(x, a), (Q<sub>k,h</sub><sup>*</sup>, V<sub>k,h</sub><sup>*</sup>)⟩<sub>h∈[H]</sub></td><td>normalized version of w<sub>h</sub><sup>k,s</sup>(x, a) (Def. 1)</td></tr><tr><td>(Q<sub>k,h</sub><sup>*</sup>, V<sub>k,h</sub><sup>*</sup>)<sub>h∈[H]</sub></td><td>true value functions in episode k</td></tr><tr><td>(⟨Q<sub>k,h</sub><sup>*</sup>, V<sub>k,h</sub><sup>*</sup>)⟩<sub>h∈[H]</sub></td><td>value functions computed by KeRNS in episode k</td></tr><tr><td>⟨Q<sub>k,h</sub><sup>*</sup>, Ṽ<sub>k,h</sub><sup>*</sup>)⟩<sub>h∈[H]</sub></td><td>value functions computed by RS-KeRNS in episode k</td></tr><tr><td>⟨X̃<sub>k,h</sub><sup>k</sup>, Ã<sub>h</sub><sup>k</sup>, Ỹ<sub>h</sub><sup>k</sup></sub></td><td>sets of representative states, actions and next states, at stage h of episode k</td></tr><tr><td>⟨ζ<sub>h</sub><sup>k</sup>, ζ<sub>h</sub><sup>k</sup></sub></td><td>mapping from X × A to X̃<sub>h</sub><sup>k</sup> × Ã<sub>h</sub><sup>k</sup></td></tr><tr><td>Δ<sup>r</sup>, Δ<sup>P</sup></td><td>mapping from X to Ỹ<sub>h</sub><sup>k</sup></td></tr><tr><td>Δ</td><td>temporal variation of the rewards and transitions (Def. 3)</td></tr><tr><td>d (= d<sub>1</sub>)</td><td>temporal variation of the MDP = Δ<sup>r</sup> + LΔ<sup>P</sup></td></tr><tr><td>d<sub>2</sub></td><td>covering dimension of (X × A, ρ)</td></tr><tr><td>ε</td><td>covering dimension of (X, ρ<sub>X</sub>)</td></tr><tr><td>ε<sub>X</sub></td><td>threshold distance to add a new representative state-action pair</td></tr><tr><td>L (L, H)</td><td>threshold distance to add a new representative state</td></tr><tr><td>bias<sub>p</sub>(k, h)</td><td>set of L-Lipschitz functions from X to R bounded by H</td></tr><tr><td>bias<sub>r</sub>(k, h)</td><td>bias in transition estimation at time (k, h), (Def. 6)</td></tr><tr><td>bias(k, h)</td><td>bias in reward estimation at time (k, h) (Def. 6)</td></tr><tr><td>G</td><td>sum of biases bias<sub>p</sub>(k, h) + bias<sub>r</sub>(k, h) (Def. 6)</td></tr><tr><td>log<sup>+</sup>(z)</td><td>good event, on which confidence intervals hold (Lemma 9)</td></tr><tr><td>log<sup>+</sup>(z)</td><td>equal to log(z + e) for any z ∈ R</td></tr></tbody></table>
## A.2 Probabilistic model

The interaction between the algorithm and the MDP defines a stochastic process $(x_h^s, a_h^s, x_{h+1}^s, \tilde{r}_h^s)$ for $h \in [H]$ and $s \in \mathbb{N}^*$, representing the state, the action, the next state and the reward at step $h$ of episode $s$. Let $\mathcal{H}_h^s \stackrel{\text{def}}{=} \{x_{h'}^{s'}, a_{h'}^{s'}, x_{h'+1}^{s'}, \tilde{r}_{h'}^{s'}\}_{s'<s,h' \in [H]} \cup \{x_{h'}^s, a_{h'}^s, x_{h'+1}^s, \tilde{r}_{h'}^s\}_{h'<h}$ be the history of the process up to time $(s, h)$.

We define $\mathcal{F}_h^s$ as the $\sigma$-algebra generated by $\mathcal{H}_h^s$, and denote its corresponding filtration by $(\mathcal{F}_h^s)_{s,h}$.

## A.3 Exploration Bonuses and Kernel Backward Induction

A reinforcement learning algorithm can be seen as a mapping from the set of possible histories $\cup_{h \in [H], k \in \mathbb{N}^*} (\mathcal{X} \times \mathcal{A} \times \mathcal{X} \times [0, 1])^{kh-1}$ to the set of actions $\mathcal{A}$.

For a time $(k, h)$, KeRNS performs this mapping in the following way:

1. Build $\hat{r}_h^k$ and $\hat{P}_h^k$ as in Definition 2, which are $\mathcal{F}_h^{k-1}$-measurable.

2. For each $h \in [H]$, with $V_{H+1}^k = 0$,

* Compute

$$ \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 \text{for all } (x, a) \in \{(x_h^s, a_h^s)\}_{s<k} $$

* Define, for any $(x, a)$,

$$ \begin{aligned} Q_h^k(x, a) &= \min_{s \in [k-1]} \left[ \tilde{Q}_h^k(x_h^s, a_h^s) + L\rho[(x, a), (x_h^s, a_h^s)] \right] \\ V_h^k(x) &= \min \left( H - h + 1, \max_{a'} Q_h^k(x, a') \right) \end{aligned} $$

3. Choose the action $a_h^k \in \text{argmax}_a Q_h^k(x_h^k, a)$.

Notice the algorithmic structure of KeRNS is the same as Kernel-UCBVI (Domingues et al., 2020). However, KeRNS uses non-stationary kernels to be able to adapt to changing environments.

It can be checked that Algorithm 3 returns the functions $Q_h^k$ described above.

The exploration bonus is defined below:
**Definition 5** (exploration bonuses). The exploration bonus in $(x, a)$ at time $(k, h)$ is defined as

$$ \mathbf{B}_h^k(x, a) \stackrel{\text{def}}{=} r \mathbf{B}_h^k(x, a) + p \mathbf{B}_h^k(x, a), \quad \text{where} $$

$$ r \mathbf{B}_h^k(x, a) \stackrel{\text{def}}{=} \sqrt{\frac{2 \Box_1^r(k, \delta/8)}{\mathbf{C}_h^k(x, a)}} + \frac{\beta}{\mathbf{C}_h^k(x, a)} + \mathbf{b}_r(k, \delta/8)\sigma, \quad \text{and} $$

$$ p \mathbf{B}_h^k(x, a) \stackrel{\text{def}}{=} \sqrt{\frac{2H^2 \Box_1^p(k, \delta/8)}{\mathbf{C}_h^k(x, a)}} + \frac{\beta H}{\mathbf{C}_h^k(x, a)} + \mathbf{b}_p(k, \delta/8)\sigma $$

where

$$ \Box_1^r(k, \delta) = \tilde{\mathcal{O}}(d_1) = \log \left( \frac{\mathcal{N}(\sigma^2/K, \mathcal{X} \times \mathcal{A}, \rho) \sqrt{1+k/\beta}}{\delta} \right) $$

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

$$ \Box_1^p(k, \delta) = \tilde{\mathcal{O}}(d_1) = \log \left( \frac{H \mathcal{N}(\sigma^2/KH, \mathcal{X} \times \mathcal{A}, \rho) \sqrt{1+k/\beta}}{\delta} \right) $$

$$ \mathbf{b}_p(k, \delta) = \tilde{\mathcal{O}}(L + \sqrt{d_1}) = \left( \frac{C_2}{2\beta^{3/2}} \sqrt{2\Box_1^p(k, \delta)} + \frac{4C_2}{\beta} \right) + 2L_p L \left( 1 + \sqrt{\log^+(C_1 k / \beta)} \right). $$

and where $d_1$ is the covering dimension of $(\mathcal{X} \times \mathcal{A}, \rho)$ and, for any $z \in \mathbb{R}$, $\log^+(z) = \log(z + e)$.

**Algorithm 3** Kernel Backward Induction with Exploration Bonuses

1: **Input:** $k, H, \Gamma, L, \beta$, transitions $(x_h^s, a_h^s, x_{h+1}^s, \tilde{r}_h^s)_{s=1}^{k-1}$ for all $h \in [H]$.

2: **Initialization:** $V_{H+1}(x) = 0$ for all $x \in \mathcal{X}$

3: **for** $h = H, \dots, 1$ **do**

4: &nbsp;&nbsp;&nbsp;&nbsp;**for** $m = 1, \dots, k-1$ **do**

5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;// Using weights given in Def.1 and bonus given in Def. 5, compute:

6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \tilde{Q}_h(x_h^m, a_h^m) = \sum_{s=1}^{k-1} \tilde{w}_h^{k,s} (x_h^m, a_h^m) (\tilde{r}_h^s + V_{h+1}(x_{h+1}^s)) + \mathbf{B}_h^k(x_h^m, a_h^m) $$

7: &nbsp;&nbsp;&nbsp;&nbsp;**end for**

8: &nbsp;&nbsp;&nbsp;&nbsp;// Interpolated $Q$-function. Defined, but not computed, for all $(x, a)$

9: &nbsp;&nbsp;&nbsp;&nbsp;$$ Q_h(x, a) = \min_{m \in [k-1]} \left( \tilde{Q}_h(x_h^m, a_h^m) + L \rho [(x, a), (x_h^m, a_h^m)] \right) $$

10: **for** $m = 1, \dots, k-1$ **do**

11: &nbsp;&nbsp;&nbsp;&nbsp;$$ V_h(x_h^m) = \min(H - h + 1, \max_a Q_h(x_h^m, a)) $$

12: **end for**

13: **end for**

14: **Return:** $(Q_h)_{h \in [H]}$
# B Proof Outline

In this section, we outline the proof of the regret bound of RS-KeRNS (Theorem 2).

## B.1 Theorem 2

To prove the regret bound in Theorem 2 for RS-KeRNS, we consider the kernel:

$$ \Gamma(t, u, v) = \chi_{(\eta, W)}(t)\phi(u, v), \text{ where } \phi(u, v) \stackrel{\text{def}}{=} \exp\left(-\rho[u, v]^2/(2\sigma^2)\right), $$

for a given function $\chi_{(\eta, W)}: \mathbb{N} \to [0, 1]$. In each episode $k$, RS-KeRNS has built representative sets of states $\bar{\mathcal{X}}_h^k$, actions $\bar{\mathcal{A}}_h^k$ and next states $\bar{\mathcal{Y}}_h^k$, for each $h \in [H]$. We define of the projections:

$$ \zeta_h^k(x, a) \stackrel{\text{def}}{=} \underset{(\bar{x}, \bar{a}) \in \bar{\mathcal{X}}_h^k \times \bar{\mathcal{A}}_h^k}{\operatorname{argmin}} \rho[(x, a), (\bar{x}, \bar{a})], \quad \bar{\zeta}_h^k(y) \stackrel{\text{def}}{=} \underset{\bar{y} \in \bar{\mathcal{Y}}_h^k}{\operatorname{argmin}} \rho_{\mathcal{X}}(y, \bar{y}). $$

from any $(x, a, y)$ to their representatives.

Let $\tilde{W}_h^{k+1}(x, a) = \sum_{s=1}^k \chi(k-s)\phi(\zeta_h^{k+1}(x, a), \zeta_h^{s+1}(x_h^s, a_h^s))$. In episode $k+1$, RS-KeRNS computes the following estimate of the rewards

$$ \tilde{r}_h^{k+1}(x, a) = \frac{1}{\beta + \tilde{W}_h^{k+1}(x, a)} \sum_{s=1}^{k} \chi(k-s) \phi(\zeta_h^{k+1}(x, a), \zeta_h^{s+1}(x_h^s, a_h^s)) \tilde{r}_h^s $$

and the following estimate of the transitions

$$ \tilde{P}_h^{k+1}(y|x, a) = \frac{1}{\beta + \tilde{W}_h^{k+1}(x, a)} \sum_{s=1}^{k} \chi(k-s) \phi(\zeta_h^{k+1}(x, a), \zeta_h^{s+1}(x_h^s, a_h^s)) \delta_{\zeta_h^{s+1}(x_h^{s+1})}(y). $$

which are similar to the estimates that would be computed by KeRNS, but using the projections $\zeta$ and $\bar{\zeta}$ to the representative states and actions. The values of $\tilde{r}_h^{k+1}(x, a)$ and $\tilde{P}_h^{k+1}(y|x, a)$ are defined for all $(x, a, y) \in \mathcal{X} \times \mathcal{A} \times \mathcal{X}$, but they only need to be stored for $(x, a, y) \in \bar{\mathcal{X}}_h^k \times \bar{\mathcal{A}}_h^k \times \bar{\mathcal{Y}}_h^k$, which corresponds to storing a finite representation of the MDP. The exploration bonuses of RS-KeRNS are defined similarly:

$$ \tilde{\mathcal{B}}_h^{k+1}(x, a) \stackrel{\text{def}}{=} \tilde{\mathcal{O}} \left( \frac{H}{\sqrt{\beta + \tilde{W}_h^{k+1}(x, a)}} + \frac{\beta H}{\beta + \tilde{W}_h^{k+1}(x, a)} + L\sigma \right) $$

We prove that the estimates used by RS-KeRNS are close to the ones used by KeRNS up to bias terms. Then, this result is used to prove that the regret bound of RS-KeRNS is the same as KeRNS, but adding a bias term multiplied by the number of episodes. For any $(x_h^s, a_h^s)$ with $s < k$ and $h \in [H]$, we show that (consequence of Lemma 18):

$$ \left| (\tilde{P}_h^k - \tilde{P}_h^k) V(x_h^s, a_h^s) \right| \lesssim L\varepsilon_{\mathcal{X}} + 8H \frac{\varepsilon}{\sigma} $$

and similar bounds are obtained for the rewards $\tilde{r}_h^k(x, a)$ (Lemma 19) and the exploration bonuses (Lemma 20). This allows us to prove that the regret of RS-KeRNS is bounded as (theorems 5 and 6)

$$ \mathcal{R}^{\text{RS-KeRNS}}(K) \lesssim \mathcal{R}^{\text{KeRNS}}(K) + L(\varepsilon + \varepsilon_{\mathcal{X}})KH^2 + \frac{\varepsilon}{\sigma}KH^3. $$

If we choose $\chi_{(\eta, W)}(t) = \prod_{i=1}^t \alpha_i$, the estimators used by RS-KeRNS can be updated online. Indeed, as detailed in Appendix G, we can related the estimates at time $(k+1, h)$ to the ones at time $(k, h)$:

$$ \begin{align*} \tilde{W}_h^{k+1}(\bar{x}, \bar{a}) &= \phi((\bar{x}, \bar{a}), \zeta_h^{k+1}(x_h^k, a_h^k)) + \alpha_{k-s} \tilde{W}_h^k(\bar{x}, \bar{a}), \\ \tilde{r}_h^{k+1}(\bar{x}, \bar{a}) &= \frac{\phi((\bar{x}, \bar{a}), \zeta_h^{k+1}(x_h^k, a_h^k))}{\beta + \tilde{W}_h^{k+1}(\bar{x}, \bar{a})} \tilde{r}_h^k + \alpha_{k-s} \left( \frac{\beta + \tilde{W}_h^k(\bar{x}, \bar{a})}{\beta + \tilde{W}_h^{k+1}(\bar{x}, \bar{a})} \right) \tilde{r}_h^k(\bar{x}, \bar{a}), \quad \text{and} \\ \tilde{P}_h^{k+1}(y|\bar{x}, \bar{a}) &= \frac{\phi((\bar{x}, \bar{a}), \zeta_h^{k+1}(x_h^k, a_h^k))}{\beta + \tilde{W}_h^{k+1}(\bar{x}, \bar{a})} \delta_{\zeta_h^{k+1}(x_h^k)}(y) + \alpha_{k-s} \left( \frac{\beta + \tilde{W}_h^k(\bar{x}, \bar{a})}{\beta + \tilde{W}_h^{k+1}(\bar{x}, \bar{a})} \right) \tilde{P}_h^k(y|\bar{x}, \bar{a}). \end{align*} $$
One issue that we need to solve is that $\tilde{W}_h^k(\bar{x}, \bar{a})$, $\tilde{r}_h^k(\bar{x}, \bar{a})$ and $\tilde{P}_h^k(y|\bar{x}, \bar{a})$ were not necessarily computed before episode $k+1$. This happens when $(\bar{x}, \bar{a})$ is a new representative state-action pair added in episode $k$. In Section G.2, we show that this can be easily handled by defining some auxiliary quantities that can be updated online and that can be used to initialize the values $\tilde{W}_h^k(\bar{x}, \bar{a})$, $\tilde{r}_h^k(\bar{x}, \bar{a})$ and $\tilde{P}_h^k(y|\bar{x}, \bar{a})$ when necessary, with little overhead to the runtime of the algorithm.

## B.2 Optimized Kernel Parameters and Regret Bounds

<table><caption>Table 3: Regret bound for optimized kernel parameters, for $W = \log_{\eta}((1 - \eta)/K)$.</caption><thead><tr><th></th><th>σ</th><th>log(1/η)</th><th>condition</th><th>bound</th><th>regret</th></tr></thead><tbody><tr><td rowspan="2">d = 0</td><td>0</td><td>Δ<sup>2/3</sup>K<sup>-2/3</sup></td><td>Δ &lt; K</td><td>R<sub>1</sub></td><td>H<sup>2</sup>X√AΔ<sup>1/3</sup>K<sup>2/3</sup></td></tr><tr><td>0</td><td>Δ<sup>2/3</sup>K<sup>-2/3</sup></td><td>Δ &lt; K</td><td>R<sub>2</sub></td><td>H<sup>2</sup>√XΔΔ<sup>1/3</sup>K<sup>2/3</sup> + H<sup>3</sup>X<sup>2</sup>AΔ<sup>2/3</sup>K<sup>1/3</sup></td></tr><tr><td rowspan="2">d &gt; 0</td><td>(1/K)<sup>1/(2d+3)</sup></td><td>Δ<sup>2/3</sup>K<sup>-2d+2/(2d+3)</sup></td><td>Δ &lt; K<sup>3/(2d+3)</sup></td><td>R<sub>1</sub></td><td>H<sup>2</sup>Δ<sup>1/3</sup>K<sup>2d+2/(2d+3)</sup></td></tr><tr><td>(1/K)<sup>1/(2d+2)</sup></td><td>Δ<sup>1/2</sup>K<sup>-2d+1/(2d+2)</sup></td><td>Δ &lt; K<sup>1/(d+1)</sup></td><td>R<sub>2</sub></td><td>H<sup>2</sup>Δ<sup>1/2</sup>K<sup>2d+1/(2d+2)</sup> + H<sup>3/2</sup>Δ<sup>1/4</sup>K<sup>3/4</sup></td></tr></tbody></table>
C Handling the bias due to non-stationarity

**Lemma 2** (temporal bias). Let $(F_h^s)_{h,s}$ be an arbitrary sequence of functions from $\mathcal{X} \times \mathcal{A}$ to $\mathbb{R}$ bounded by $M$. Then,

$$ \left| \frac{1}{\mathbf{C}_h^k(x, a)} \sum_{s=1}^{k-1} w_h^{k,s}(x, a) (F_h^s(x, a) - F_h^k(x, a)) \right| \le \sum_{i=1 \lor (k-W)}^{k-1} |F_h^i(x, a) - F_h^{i+1}(x, a)| + \frac{2MC_3}{\beta} \frac{\eta^W}{1-\eta}. $$

*Proof.* The result is straightforward when $k \le W$. Assuming $k > W$, we have

$$ \begin{aligned} & \frac{1}{\mathbf{C}_h^k(x, a)} \sum_{s=1}^{k-1} w_h^{k,s}(x, a) (F_h^s(x, a) - F_h^k(x, a)) \\ & = \frac{1}{\mathbf{C}_h^k(x, a)} \sum_{s=k-W}^{k-1} w_h^{k,s}(x, a) (F_h^s(x, a) - F_h^k(x, a)) + \frac{1}{\mathbf{C}_h^k(x, a)} \sum_{s=1}^{k-W-1} w_h^{k,s}(x, a) (F_h^s(x, a) - F_h^k(x, a)) \\ & \le \frac{1}{\mathbf{C}_h^k(x, a)} \sum_{s=k-W}^{k-1} w_h^{k,s}(x, a) \sum_{i=s}^{k-1} (F_h^i(x, a) - F_h^{i+1}(x, a)) + \frac{2MC_3}{\beta} \sum_{s=1}^{k-W-1} \eta^{k-1-s} \\ & \le \frac{1}{\mathbf{C}_h^k(x, a)} \sum_{i=k-W}^{k-1} \left( \sum_{s=k-W}^{i} w_h^{k,s}(x, a) \right) (F_h^i(x, a) - F_h^{i+1}(x, a)) + \frac{2MC_3}{\beta} \frac{\eta^W - \eta^{k-1}}{1-\eta} \\ & \le \sum_{i=k-W}^{k-1} |F_h^i(x, a) - F_h^{i+1}(x, a)| + \frac{2MC_3}{\beta} \frac{\eta^W}{1-\eta}, \end{aligned} $$

where in the first inequality we used by Assumption 4 that

$$ \begin{aligned} w_h^{k,s}(x, a) &= \Gamma(k-s-1, (x, a), (x_h^s, a_h^s)) \\ &= \bar{\Gamma}_{(\eta, W)}(k-s-1, \rho[(x, a), (x_h^s, a_h^s)]) \\ &\le C_3 \eta^{k-s-1}. \end{aligned} $$

By symmetry, we obtain

$$ \frac{1}{\mathbf{C}_h^k(x, a)} \sum_{s=1}^{k-1} w_h^{k,s}(x, a) (F_h^k(x, a) - F_h^s(x, a)) \le \sum_{i=k-W}^{k-1} |F_h^i(x, a) - F_h^{i+1}(x, a)| + \frac{2MC_3}{\beta} \frac{\eta^W}{1-\eta}. $$

which concludes the proof. □

**Definition 6** (temporal bias of the MDP). The temporal bias at time $(k, h)$ is defined by

$$ \text{bias}(k, h) = \text{bias}_r(k, h) + \text{bias}_p(k, h) $$

where

$$ \text{bias}_r(k, h) = \sum_{i=1 \lor (k-W)}^{k-1} \sup_{x,a} |r_h^i(x, a) - r_h^{i+1}(x, a)| + \frac{2C_3}{\beta} \frac{\eta^W}{1-\eta} $$

$$ \text{bias}_p(k, h) = L \sum_{i=1 \lor (k-W)}^{k-1} \sup_{x,a} \mathbb{W}_1 (P_h^i(\cdot|x, a), P_h^{i+1}(\cdot|x, a)) + \frac{2C_3 H}{\beta} \frac{\eta^W}{1-\eta} $$
**Definition 7** (Average MDP at episode k). Let

$$ \bar{r}_h^k(x, a) \stackrel{\text{def}}{=} \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) r_h^s(x, a) + \frac{\beta}{\mathbf{C}_h^k(x, a)} r_h^k(y|x, a) $$

$$ \bar{P}_h^k(y|x, a) \stackrel{\text{def}}{=} \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) P_h^s(y|x, a) + \frac{\beta}{\mathbf{C}_h^k(x, a)} P_h^k(y|x, a) $$

and let $\mathcal{M}_k^{av}$ be the MDP with transitions $\{\bar{P}_h^k\}_h$ and rewards $\{\bar{r}_h^k\}_h$.

**Corollary 2.** Let $\mathcal{L}(L, H)$ be the class of L-Lipschitz functions from $\mathcal{X}$ to $\mathbb{R}$ bounded by H. Then,

$$ \sup_{x,a} |r_h^k(x, a) - \bar{r}_h^k(x, a)| \leq \mathbf{bias}_r(k, h) $$

$$ \sup_{f \in \mathcal{L}(L, H)} \left| \left( P_h^k - \bar{P}_h^k \right) f(x, a) \right| \leq \mathbf{bias}_p(k, h) $$

*Proof.* For the reward term, we have from Lemma 2:

$$ \begin{aligned} |r_h^k(x, a) - \bar{r}_h^k(x, a)| &= \left| \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) (r_h^k(x, a) - \bar{r}_h^k(x, a)) \right| \\ &\leq \sum_{i=1 \lor (k-W)}^{k-1} |r_h^i(x, a) - r_h^{i+1}(x, a)| + \frac{2C_3 \eta^W}{\beta (1-\eta)} \\ &\leq \mathbf{bias}_r(k, h). \end{aligned} $$

For the transitions term, we also apply Lemma 2 and the definition of the 1-Wasserstein distance:

$$ \begin{aligned} \left| \left( P_h^k - \bar{P}_h^k \right) f(x, a) \right| &= \left| \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) \left( P_h^k f(x, a) - \bar{P}_h^k f(x, a) \right) \right| \\ &\leq \sum_{i=1 \lor (k-W)}^{k-1} \left| P_h^i f(x, a) - P_h^{i+1} f(x, a) \right| + \frac{2C_3 H}{\beta} \frac{\eta^W}{1-\eta} \\ &\leq L \sum_{i=1 \lor (k-W)}^{k-1} W_1 \left( P_h^i(\cdot|x, a), P_h^{i+1}(\cdot|x, a) \right) + \frac{2C_3 H}{\beta} \frac{\eta^W}{1-\eta} \\ &\leq \mathbf{bias}_p(k, h). \end{aligned} $$

**Remark 1.** Since the functions in $\mathcal{L}(L, H)$ are bounded, the 1-Wasserstein distance could be replaced by the total variation (TV) distance $\|P_h^i(\cdot|x, a) - P_h^{i+1}(\cdot|x, a)\|_1$.

□
# D Concentration

In this Section, we provide confidence intervals that will be used to prove our regret bounds. The main concentration results are presented in Lemma 9, which defines an event $G$ where all the confidence intervals hold, and we show that $\mathbb{P}[G] \ge 1 - \delta/2$.

## D.1 Concentration inequalities for weighted sums

We reproduce here the concentration inequalities for weighted sums proved by Domingues et al. (2020), which we will need.

**Lemma 3** (Hoeffding type inequality (Domingues et al., 2020)). 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$ and $V_t \stackrel{\text{def}}{=} \sum_{s=1}^t w_s^2$, and assume $w_s \le 1$ almost surely for all $s$. 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{\frac{2c^2 \log \left( \frac{\sqrt{1+t/\beta}}{\delta} \right)}{\sum_{s=1}^{t} w_s + \beta}} $$

*Proof.* See Lemma 2 of Domingues et al. (2020). □

**Lemma 4** (Bernstein type inequality (Domingues et al., 2020)). 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} [Y_s^2 | \mathcal{F}_{s-1}] \quad \text{and} \quad W_t \stackrel{\text{def}}{=} \sum_{s=1}^{t} w_s, $$

Assume that, for all $t \ge 1$, (i) $w_t$ is $\mathcal{F}_{t-1}$ measurable, (ii) $\mathbb{E}[Y_t | \mathcal{F}_{t-1}] = 0$, (iii) $w_t \in [0, 1]$ almost surely, (iv) there exists $b > 0$ such that $|Y_t| \le b$ almost surely. Then, 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.* See Lemma 3 of Domingues et al. (2020). □

## D.2 Hoeffding-type concentration inequalities

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

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

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

$$ \Box_1^P(k, \delta) = \tilde{\mathcal{O}}(d_1) = \log \left( \frac{KH\mathcal{N}(\sigma^2/(KH), \mathcal{X} \times \mathcal{A}, \rho) \sqrt{1+k/\beta}}{\delta} \right) \\ \mathbf{b}_p(k, \delta) = \tilde{\mathcal{O}}(L + \sqrt{d_1}) = \left( \frac{C_2}{2\beta^{3/2}} \sqrt{2\Box_1^P(k, \delta)} + \frac{4C_2}{\beta} \right) + 2L_p L \left( 1 + \sqrt{\log(C_1k/\beta)} \right) $$

and where $d_1$ is the covering dimension of $(\mathcal{X} \times \mathcal{A}, \rho)$.
**Proof.** Let $V = V_{k,h+1}^*$. For fixed $(x, a, h)$, we have

$$ \begin{aligned} & \left| (\hat{P}_h^k - \bar{P}_h^k) V_{k,h+1}^*(x, a) \right| \\ &= \left| \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) \left( V(x_{h+1}^s) - \int_X V(y) dP_h^s(y|x, a) \right) - \frac{\beta}{\mathbf{C}_h^k(x, a)} \int_X V(y) dP_h^k(y|x, a) \right| \\ &\le \left| \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) \left( V(x_{h+1}^s) - \int_X V(y) dP_h^s(y|x_h^s, a_h^s) \right) \right| \\ &\qquad + \underbrace{\left| \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) \left( \int_X V(y) dP_h^s(y|x_h^s, a_h^s) - \int_X V(y) dP_h^s(y|x, a) \right) \right|}_{\textcircled{2}} \\ &\qquad + \frac{\beta H}{\mathbf{C}_h^k(x, a)}. \end{aligned} $$

**Bounding ① (martingale term)** Let $Y_s = V(x_{h+1}^s) - P_h^s V(x_h^s, a_h^s)$. From Lemma 3, we have, for a fixed tuple $(x, a, k, h)$,

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

with probability at least $1 - \delta$, since $(Y_s)_s$ is a martingale difference sequence with respect to $(\mathcal{F}_h^s)_s$.

From Lemma 24, we verify that the functions

$$ (x, a) \mapsto \sqrt{1/\mathbf{C}_h^k(x, a)} \quad \text{and} \quad (x, a) \mapsto \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) Y_s $$

are Lipschitz continuous, with Lipschitz constants bounded by $C_2k/(2\sigma\beta^{3/2})$ and $4HC_2k/(\beta\sigma)$, respectively. Let $C_{\mathcal{X}\times\mathcal{A}}(\sigma^2/KH)$ be a $(\sigma^2/KH)$-covering of $\mathcal{X} \times \mathcal{A}$. Using the Lipschitz continuity of the functions above and a union bound over $C_{\mathcal{X}\times\mathcal{A}}(\sigma^2/(KH))$ and over $h \in [H]$, we have

$$ \textcircled{2} = \left| \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) Y_s \right| \le \sqrt{2H^2 \log \left( \frac{\sqrt{1+k/\beta}}{\delta} \right) \frac{1}{\mathbf{C}_h^k(x, a)}} + \left( \frac{C_2k}{2\sigma\beta^{3/2}} \sqrt{2H^2 \log \left( \frac{\sqrt{1+k/\beta}}{\delta} \right)} + \frac{4HC_2k}{\beta\sigma} \right) \frac{\sigma^2}{KH} $$

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

**Bounding ② (spatial bias term)** We have

$$ \begin{aligned} \textcircled{2} &= \left| \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) \left( \int_X V(y) dP_h^s(y|x_h^s, a_h^s) - \int_X V(y) dP_h^s(y|x, a) \right) \right| \\ &\le L \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) W_1 (P_h^s(\cdot|x_h^s, a_h^s), P_h^s(\cdot|x, a)) \quad \text{by the definition of } W_1(\cdot, \cdot) \\ &\le L_p L \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) \rho[(x_h^s, a_h^s), (x, a)] \quad \text{by Assumption 2} \\ &\le 2\sigma L_p L \left( 1 + \sqrt{\log^+(C_1k/\beta)} \right) \quad \text{by Lemma 23.} \end{aligned} $$
Putting together the bounds for ① and ② concludes the proof.

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

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

$$|\hat{r}_h^k(x, a) - \bar{r}_h^k(x, a)| \le \sqrt{\frac{2\Box_1^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

$$\Box_1^r(k, \delta) = \tilde{\mathcal{O}}(d_1) = \log \left( \frac{\mathcal{N}(\sigma^2/K, \mathcal{X} \times \mathcal{A}, \rho) \sqrt{1 + k/\beta}}{\delta} \right)$$

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

and where $d_1$ is the covering dimension of $(\mathcal{X} \times \mathcal{A}, \rho)$.

*Proof.* Almost identical to the proof of Lemma 5, except for the fact that the rewards are bounded by 1 instead of $H$. □

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

**Lemma 7.** Let $\mathcal{L}(2L, 2H)$ be the class of $2L$-Lipschitz functions from $\mathcal{X}$ to $\mathbb{R}$ bounded by $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{L}(2L, 2H)$, we have

$$|(\hat{P}_h^k - \bar{P}_h^k)f(x, a)| \le \sqrt{\frac{8H^2\Box_2^p(k, \delta)}{\mathbf{C}_h^k(x, a)}} + \frac{2\beta H}{\mathbf{C}_h^k(x, a)} + \theta_b^1(k, \delta)\sigma^{1+d_2/2} + \theta_b^2(k, \delta)\sigma$$

where

$$\Box_2^p(k, \delta) = \tilde{\mathcal{O}}(|C'_\sigma| + d_1 d_2) = \log \left( \frac{KH\mathcal{N}(\sigma^{2+d_2/2}/KH, \mathcal{X} \times \mathcal{A}, \rho) \sqrt{1+k/\beta}}{\delta} \left( \frac{2H}{L\sigma} \right)^{\mathcal{N}(\sigma, \mathcal{X}, \rho_X)} \right)$$

$$\theta_b^1(k, \delta) = \tilde{\mathcal{O}}\left(\sqrt{|C'_\sigma|} + \sqrt{d_1 d_2}\right) = \frac{4C_2}{\beta} + \frac{C_2}{2\beta^{3/2}}\sqrt{8\Box_2^p(k, \delta)}$$

$$\theta_b^2(k, \delta) = \tilde{\mathcal{O}}(L) = 4L_p L \left( 1 + \sqrt{\log^+(C_1 k / \beta)} \right) + 32L$$

and where $d_1$ is the covering dimension of $(\mathcal{X} \times \mathcal{A}, \rho)$, $d_2$ is the covering dimension of $(\mathcal{X}, \rho_X)$ and $|C'_\sigma| = \mathcal{N}(\sigma, \mathcal{X}, \rho_X)$.

*Proof.* Fix a function $f \in \mathcal{L}(2L, 2H)$. Proceeding as in the proof of Lemma 5, we have

$$|(\hat{P}_h^k - \bar{P}_h^k)f(x, a)| = \left| \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) \left( f(x_{h+1}^s) - \int_{\mathcal{X}} f(y) d\mathbf{P}_h^s(y|x, a) \right) - \frac{\beta}{\mathbf{C}_h^k(x, a)} \int_{\mathcal{X}} f(y) d\mathbf{P}_h^k(y|x, a) \right| \le \left| \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) Y_s(f) \right| + 4\sigma L_p L \left( 1 + \sqrt{\log^+(C_1 k / \beta)} \right) + \frac{2\beta H}{\mathbf{C}_h^k(x, a)}.$$

where $Y_s(f) = f(x_{h+1}^s) - \mathbf{P}_h^s f(x_h^s, a_h^s)$.
Now, for fixed $(x, a, k, h, f)$, Lemma 3 gives us

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

with probability at least $1 - \delta$, since $(Y_s(f))_s$ is a martingale difference sequence with respect to $(\mathcal{F}_h^s)_s$ bounded by $4H$.

**Covering $\mathcal{L}(2L, 2H)$** Now let $\mathcal{C}_\mathcal{L}$ be a $8L\sigma$-covering of $(\mathcal{L}(2L, 2H), \|\cdot\|_\infty)$. Using the fact that the function $f \mapsto Y_s(f)$ is 2-Lipschitz with respect to $\|\cdot\|_\infty$, we do a union bound over $\mathcal{C}_\mathcal{L}$ to obtain

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

for all $k$ and all $f \in \mathcal{L}(2L, 2H)$, with probability at least $1 - \delta (\frac{2H}{L\sigma})^{N(\sigma, \mathcal{X}, \rho, \mathcal{X})}$, since the $8L\sigma$-covering number of $\mathcal{C}_\mathcal{L}$ is bounded by $(\frac{2H}{L\sigma})^{N(\sigma, \mathcal{X}, \rho, \mathcal{X})}$, by Lemma 5 of Domingues et al. (2020).

**Covering $(\mathcal{X} \times \mathcal{A}, \rho)$** By Lemma 24, the functions

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

are $4HC_2k/(\beta\sigma)$-Lipschitz and $C_2k/(2\beta^{3/2}\sigma)$, respectively, with respect to the distance $\rho$. Let $\mathcal{C}_{\mathcal{X}\times\mathcal{A}}$ be a $\sigma^{2+d_2/2}/KH$ covering of $(\mathcal{X} \times \mathcal{A}, \rho)$. Using the continuity of the functions above, a union bound over $\mathcal{C}_{\mathcal{X}\times\mathcal{A}}$ gives us<fnref n="9" />

$$ \left| \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) Y_s(f) \right| \le \sqrt{8H^2 \log \left( \frac{\sqrt{1+k/\beta}}{\delta} \right) \frac{1}{C_h^k(x, a)}} + 32L\sigma + \frac{\sigma^{2+d_2/2}}{KH} \left( \frac{4HC_2k}{\beta\sigma} + \frac{C_2k}{2\beta^{3/2}\sigma} \sqrt{8H^2 \log \left( \frac{\sqrt{1+k/\beta}}{\delta} \right)} \right) $$

for all $k$, all $f \in \mathcal{L}(2L, 2H)$ and all $(x, a) \in \mathcal{X} \times \mathcal{A}$, with probability at least

$$ 1 - \delta \left( \frac{2H}{L\sigma} \right)^{N(\sigma, \mathcal{X}, \rho, \mathcal{X})} \mathcal{N} \left( \frac{\sigma^{2+d_2/2}}{KH}, \mathcal{X} \times \mathcal{A}, \rho \right) $$

and a union bound over $(k, h) \in [K] \times [H]$ concludes the proof. $\square$

<footnote n="9">⁹see, for instance, Lemma 6 of Domingues et al. (2020).</footnote>
### D.3 Bernstein-type concentration inequality

**Lemma 8.** Let $\mathcal{L}(2L, 2H)$ be the class of $2L$-Lipschitz functions from $\mathcal{X}$ to $\mathbb{R}$ bounded by $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{L}(2L, 2H)$, we have

$$ \begin{aligned} \left| (\hat{P}_h^k - \bar{P}_h^k) f(x, a) \right| & \le \frac{1}{H} P_h^k |f|(x, a) + \frac{14H^2 C_2 \square_3(k, \delta) + 2\beta H}{C_h^k(x, a)} \\ & \quad + \theta_b^3(k, \delta) \sigma^{1+d_2} + \theta_b^4(k, \delta) \sigma + \frac{2}{H} \text{bias}_p(k, h) \end{aligned} $$

where $d_1$ is the covering dimension of $(\mathcal{X} \times \mathcal{A}, \rho)$, $d_2$ is the covering dimension of $(\mathcal{X}, \rho_{\mathcal{X}})$ and

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

$$ \theta_b^3(k, \delta) = \tilde{\mathcal{O}}(|\mathcal{C}'_{\sigma}| + d_1 d_2 + L\sigma) = \frac{2L_p L\sigma}{H^2 K} + \frac{4C_2}{H\beta} + \frac{14\square_3(k, \delta)C_2}{\beta^2} $$

$$ \theta_b^4(k, \delta) = \tilde{\mathcal{O}}(L) = 32L + 6L_p L \left( 1 + \sqrt{\log^+(C_1 k / \beta)} \right) $$

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

*Proof.* We have

$$ \begin{aligned} & \left| (\hat{P}_h^k - \bar{P}_h^k) f(x, a) \right| \\ &= \left| \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) (f(x_{h+1}^s) - P_h^s f(x, a)) - \frac{\beta P_h^k f(x, a)}{C_h^k(x, a)} \right| \\ &\le \left| \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) \left( f(x_{h+1}^s) - \int_{\mathcal{X}} f(y) dP_h^s(y|x_h^s, a_h^s) \right) \right| \\ &\qquad + \underbrace{\left| \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) \left( \int_{\mathcal{X}} f(y) dP_h^s(y|x_h^s, a_h^s) - \int_{\mathcal{X}} f(y) dP_h^s(y|x, a) \right) \right|}_{\textcircled{2}} + \frac{2\beta H}{C_h^k(x, a)}. \end{aligned} $$

**Bounding ② (spatial bias term)** As in the proof of Lemma 5, we can show that

$$ \textcircled{2} = \left| \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) \left( \int_{\mathcal{X}} f(y) dP_h^s(y|x_h^s, a_h^s) - \int_{\mathcal{X}} f(y) dP_h^s(y|x, a) \right) \right| \le 4\sigma L_p L \left( 1 + \sqrt{\log^+(C_1 k / \beta)} \right) $$

**Bounding the martingale term (①) with a Bernstein-type inequality** Notice that $(x, a) \mapsto \int_{\mathcal{X}} f(y) dP_h^k(y|x, a)$ is bounded by $2H$ and

$$ \mathbb{E} [f(x_{h+1}^s) | \mathcal{F}_h^s] = \int_{\mathcal{X}} f(y) dP_h^s(y | x_h^s, a_h^s). $$

The conditional variance of $f(x_{h+1}^s)$ is bounded as follows

$$ \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^s(y | x_h^s, a_h^s) \right)^2 \\ &\le 2H \mathbb{E} [|f(x_{h+1}^s)| | \mathcal{F}_h^s] \\ &= 2H \int_{\mathcal{X}} |f(y)| dP_h^s(y | x_h^s, a_h^s) \end{aligned} $$
which we use to bound its weighted average

$$
\begin{align*}
& \frac{1}{\mathbf{C}_h^k(x, a)} \sum_{s=1}^{k-1} w_h^{k,s}(x, a)^2 \mathbb{V}[f(x_{h+1}^s) | \mathcal{F}_h^s] \\
& \leq \frac{1}{\mathbf{C}_h^k(x, a)} \sum_{s=1}^{k-1} w_h^{k,s}(x, a) \mathbb{V}[f(x_{h+1}^s) | \mathcal{F}_h^s] \\
& \leq \frac{2H}{\mathbf{C}_h^k(x, a)} \sum_{s=1}^{k-1} w_h^{k,s}(x, a) \int_{\mathcal{X}} |f(y)| \, d\mathbf{P}_h^s(y|x_h^s, a_h^s) \\
& = \frac{2H}{\mathbf{C}_h^k(x, a)} \sum_{s=1}^{k-1} w_h^{k,s}(x, a) \mathbf{P}_h^s |f|(x, a) + \frac{2H}{\mathbf{C}_h^k(x, a)} \sum_{s=1}^{k-1} w_h^{k,s}(x, a) (\mathbf{P}_h^s |f|(x_h^s, a_h^s) - \mathbf{P}_h^s |f|(x, a)) \\
& \leq 2H \left( \bar{\mathbf{P}}_h^k |f|(x, a) - \frac{\beta \mathbf{P}_h^k |f|(x, a)}{\mathbf{C}_h^k(x, a)} \right) + \frac{4HL_pL}{\mathbf{C}_h^k(x, a)} \sum_{s=1}^{k-1} w_h^{k,s}(x, a) \rho[(x_h^s, a_h^s), (x, a)] \\
& \leq 2H \bar{\mathbf{P}}_h^k |f|(x, a) + 8HL_pL\sigma \left( 1 + \sqrt{\log^+(C_1k/\beta)} \right)
\end{align*}
$$

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

Let $\Delta(k, \delta) = \log(4e(2k+1)/\delta)$. Let $Y_s(f) = f(x_{h+1}^s) - \mathbf{P}_h^s f(x_h^s, a_h^s)$. By Lemma 4, we have

$$
\textcircled{1} = \left| \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) Y_s(f) \right| \le \sqrt{2\Delta(k, \delta) \frac{\sum_{s=1}^{k-1} w_h^{k,s}(x, a)^2 \mathbb{V}[f(x_{h+1}^s}) |\mathcal{F}_h^s]}{\mathbf{C}_h^k(x, a)^2} + \frac{10H\Delta(k, \delta)}{\mathbf{C}_h^k(x, a)}
$$

with probability at least $1 - \delta$, since, for a fixed $f$, $(Y_s(f))_s$ is a martingale difference sequence with respect to $(\mathcal{F}_h^s)_s$. Using the fact that $\sqrt{uv} \le (u+v)/2$ for all $u, v > 0$,

$$
\begin{align*}
\left| \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) Y_s(f) \right| &\le \frac{4H^2 \Delta(k, \delta)}{\mathbf{C}_h^k(x, a)} + \frac{1}{4H^2} \frac{\sum_{s=1}^{k-1} w_h^{k,s}(x, a)^2 \mathbb{V}[f(x_{h+1}^s)] |\mathcal{F}_h^s|}{\mathbf{C}_h^k(x, a)} + \frac{10H \Delta(k, \delta)}{\mathbf{C}_h^k(x, a)} \\
&\le \frac{1}{H} \int_{\mathcal{X}} |f(y)| d\bar{\mathbf{P}}_h^k(y|x, a) + \frac{(4H^2 + 10H) \Delta(k, \delta)}{\mathbf{C}_h^k(x, a)} + \frac{2L_p L \sigma}{H} \left( 1 + \sqrt{\log^+(C_1 t / \beta)} \right)
\end{align*}
$$

From Corollary 2, we have

$$
\int_{\mathcal{X}} |f(y)| d\bar{\mathbf{P}}_h^k(y|x, a) = (\bar{\mathbf{P}}_h^k - \mathbf{P}_h^k) |f(y)| (x, a) + \mathbf{P}_h^k |f(y)| (x, a) \le 2 \mathbf{bias}_p(k, h) + \mathbf{P}_h^k |f(y)| (x, a)
$$

which gives us

$$
\left| \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) Y_s(f) \right| \le \frac{1}{H} \mathbf{P}_h^k |f(y)| (x, a) + \frac{(4H^2 + 10H) \Delta(k, \delta)}{\mathbf{C}_h^k(x, a)} \\
+ \frac{2}{H} \mathbf{bias}_p(k, h) + \frac{2L_p L \sigma}{H} \left( 1 + \sqrt{\log^+(C_1 t / \beta)} \right)
$$

with probability $1 - \delta$.

Covering of $\mathcal{X} \times \mathcal{A}$ As a consequence of Assumption 2, the function $(x, a) \mapsto (1/H)\mathbf{P}_h^k |f(y)| (x, a)$ is $2L_pL$-Lipschitz. Also, the functions

$$
(x, a) \mapsto \left| \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) Y_s(f) \right| \quad \text{and} \quad (x, a) \mapsto \frac{1}{\mathbf{C}_h^k(x, a)}
$$
are $4HC_2k/(\beta\sigma)$-Lipschitz and $C_2k/(\beta^2\sigma)$, respectively, by Lemma 24. Consequently, a union bound over a $(\sigma^{2+d_2}/(H^2K))$-covering of $(\mathcal{X} \times \mathcal{A}, \rho)$ and over $[H]$ gives us

$$ \left| \sum_{s=1}^{k-1} \tilde{w}_h^{k,s}(x, a) Y_s(f) \right| \le \frac{1}{H} P_h^k |f(y)| (x, a) + \frac{(4H^2 + 10H)\Delta(k, \delta)}{C_h^k(x, a)} \\ + \frac{2}{H} \text{bias}_p(k, h) + \frac{2L_p L \sigma}{H} \left( 1 + \sqrt{\log^+(C_1 t/\beta)} \right) \\ + \left( 2L_p L + \frac{4HC_2k}{\beta\sigma} + \frac{(4H^2 + 10H)\Delta(k, \delta)C_2k}{\beta^2\sigma} \right) \frac{\sigma^{2+d_2}}{H^2K} $$

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

**Covering of $\mathcal{L}(2L, 2H)$** The bounds for ① and ② give us

$$ \left| (\hat{P}_h^k - \bar{P}_h^k) f(x, a) \right| \le \frac{1}{H} P_h^k |f(y)| (x, a) + \frac{(4H^2 + 10H)\Delta(k, \delta)}{C_h^k(x, a)} \\ + \frac{2}{H} \text{bias}_p(k, h) + \left( 2L_p L + \frac{4HC_2k}{\beta\sigma} + \frac{(4H^2 + 10H)\Delta(k, \delta)C_2k}{\beta^2\sigma} \right) \frac{\sigma^{2+d_2}}{H^2K} \\ + 6\sigma L_p L \left( 1 + \sqrt{\log^+(C_1k/\beta)} \right) + \frac{2\beta H}{C_h^k(x, a)} $$

The $8L\sigma$-covering number of $\mathcal{L}(2L, 2H)$ with respect to the infinity norm is bounded by $(2H/(L\sigma))^{\mathcal{N}(\sigma, \mathcal{X}, \rho\mathcal{X})}$, by Lemma 5 of Domingues et al. (2020). The functions $f \mapsto |(P_h^k - \hat{P}_h^k)f(x, a)|$ and $f \mapsto \frac{1}{H} \int_{\mathcal{X}} |f(y)| d\bar{P}_h^k(y|x, a)$ are 2-Lipschitz with respect to $\|\cdot\|_{\infty}$. Consequently, with probability at least

$$ 1 - \delta K H N \left( \frac{\sigma^{2+d_2}}{H^2 K}, \mathcal{X} \times \mathcal{A}, \rho \right) \left( \frac{2H}{L\sigma} \right)^{\mathcal{N}(\sigma, \mathcal{X}, \rho\mathcal{X})}, $$

for all $\mathcal{L}(2L, 2H)$ and for all $(x, a, h, k)$, we have

$$ \left| (\hat{P}_h^k - \bar{P}_h^k) f(x, a) \right| \le \frac{1}{H} P_h^k |f(y)| (x, a) + \frac{(4H^2 + 10H)\Delta(k, \delta)}{C_h^k(x, a)} \\ + \frac{2}{H} \text{bias}_p(k, h) + \left( 2L_p L + \frac{4HC_2k}{\beta\sigma} + \frac{(4H^2 + 10H)\Delta(k, \delta)C_2k}{\beta^2\sigma} \right) \frac{\sigma^{2+d_2}}{H^2K} \\ + 6\sigma L_p L \left( 1 + \sqrt{\log^+(C_1k/\beta)} \right) + \frac{2\beta H}{C_h^k(x, a)} + 32L\sigma $$

which concludes the proof.

□
D.4 Good event

**Lemma 9.** Let $\mathcal{G} = \mathcal{G}_1 \cap \mathcal{G}_2 \cap \mathcal{G}_3 \cap \mathcal{G}_4$, where

$$ \mathcal{G}_1 \stackrel{\text{def}}{=} \left\{ \forall (x, a, k, h), \left| \hat{r}_h^k(x, a) - \bar{r}_h^k(x, a) \right| \le \sqrt{\frac{2 \square_1^r(k, \delta/8)}{\mathbf{C}_h^k(x, a)} + \frac{\beta}{\mathbf{C}_h^k(x, a)} + \mathbf{b}_r(k, \delta/8)\sigma} \right\} $$

$$ \mathcal{G}_2 \stackrel{\text{def}}{=} \left\{ \forall (x, a, k, h), \left| (\hat{P}_h^k - \bar{P}_h^k) V_{k,h+1}^*(x, a) \right| \le \sqrt{\frac{2H^2 \square_1^p(k, \delta/8)}{\mathbf{C}_h^k(x, a)} + \frac{\beta H}{\mathbf{C}_h^k(x, a)} + \mathbf{b}_p(k, \delta/8)\sigma} \right\} $$

$$ \mathcal{G}_3 \stackrel{\text{def}}{=} \left\{ \forall (x, a, k, h, f), \left| (\hat{P}_h^k - \bar{P}_h^k) f(x, a) \right| \le \sqrt{\frac{2H^2 \square_2^p(k, \delta/8)}{\mathbf{C}_h^k(x, a)} + \frac{\beta H}{\mathbf{C}_h^k(x, a)} \right. \\ \left. + \theta_b^1(k, \delta/8)\sigma^{1+d_2/2} + \theta_b^2(k, \delta/8)\sigma \right\} $$

$$ \mathcal{G}_4 \stackrel{\text{def}}{=} \left\{ \forall (x, a, k, h, f), \left| (\hat{P}_h^k - \bar{P}_h^k) f(x, a) \right| \le \frac{1}{H} P_h^k |f(y)| (x, a) + \frac{14H^2 C_2 \square_3(k, \delta/8) + 2\beta H}{\mathbf{C}_h^k(x, a)} \right. \\ \left. + \theta_b^3(k, \delta/8)\sigma^{1+d_2} + \theta_b^4(k, \delta/8)\sigma + \frac{2}{H} \text{bias}_p(k, h) \right\} $$

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

$$ \square_1^p(k, \delta) = \tilde{\mathcal{O}}(d_1), \quad \mathbf{b}_p(k, \delta) = \tilde{\mathcal{O}}(L + \sqrt{d_1}), \quad \square_1^r(k, \delta) = \tilde{\mathcal{O}}(d_1), \quad \mathbf{b}_r(k, \delta) = \tilde{\mathcal{O}}(L + \sqrt{d_1}) $$

$$ \square_2^p(k, \delta) = \tilde{\mathcal{O}}(|C'_\sigma| + d_1 d_2), \quad \theta_b^1(k, \delta) = \tilde{\mathcal{O}}(\sqrt{|C'_\sigma|} + \sqrt{d_1 d_2}), \quad \theta_b^2(k, \delta) = \tilde{\mathcal{O}}(L) $$

$$ \square_3(k, \delta) = \tilde{\mathcal{O}}(|C'_\sigma| + d_1 d_2), \quad \theta_b^3(k, \delta) = \tilde{\mathcal{O}}(|C'_\sigma| + d_1 d_2 + L\sigma), \quad \theta_b^4(k, \delta) = \tilde{\mathcal{O}}(L) $$

are defined in Lemmas 5, 6, 7 and 8, respectively. Then,

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

*Proof.* Immediate consequence of Lemmas 5, 6, 7 and 8. □

<figure><img src="image_4.png" /></figure>
## E Upper bound on true value function

In this section, we show that the true value functions can be upper bounded by the value functions computed by KeRNS plus a bias term. This result will be used to upper bound the regret in the next section.

**Lemma 10 (upper bound on Q functions).** On $G$, for all $(x, a, k, h) \in \mathcal{X} \times \mathcal{A} \times [K] \times [H]$, we have

$$Q_h^k(x, a) + \sum_{h'=h}^{H} \textbf{bias}(k, h) \geq Q_{k,h}^*(x, a)$$

where $\textbf{bias}(k, h) = \textbf{bias}_r(k, h) + \textbf{bias}_p(k, h)$ is the temporal bias of the algorithm at time $(k, h)$ (see Definition 6).

*Proof.* We proceed by induction on $h$. For $h = H + 1$, both quantities are zero, so the inequality is trivially verified. Now, assume that it is true for $h + 1$ and let's prove it for $h$.

From the induction hypothesis, we have $V_{h+1}^k(x) + \sum_{h'=h+1}^H \textbf{bias}(k, h) \geq V_{k,h+1}^*(x)$. Indeed,

$$\max_a Q_{h+1}^k(x, a) + \sum_{h'=h+1}^{H} \textbf{bias}(k, h) \geq \max_a Q_{k,h}^*(x, a) = V_{k,h+1}^*(x)$$

and, since $V_{k,h+1}^*(x) \leq H - h$, we have

$$V_{h+1}^k(x) + \sum_{h'=h+1}^{H} \textbf{bias}(k, h) = \min \left( H - h, \max_a Q_{h+1}^k(x, a) \right) + \sum_{h'=h+1}^{H} \textbf{bias}(k, h) \geq V_{k,h+1}^*(x).$$

From the definition of the algorithm, we have

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

where $\tilde{Q}_h^k(x, a) = \hat{r}_h^k(x, a) + \hat{P}_h^k V_{h+1}^k(x, a) + B_h^k(x, a)$. Hence,

$$\tilde{Q}_h^k(x, a) - Q_{k,h}^*(x, a) = \underbrace{\hat{r}_h^k(x, a) - r_h^k(x, a) + r^B_h(x, a)}_{(\mathbf{A})} + \underbrace{\hat{P}_h^k V_{h+1}^k(x, a) - P_h^k V_{k,h+1}^*(x, a) + p^B_h(x, a)}_{(\mathbf{B})}.$$

The term $(\mathbf{A})$ is lower bounded as follows

$$(\mathbf{A}) = \hat{r}_h^k(x, a) - \bar{r}_h^k(x, a) + r^B_h(x, a) + \bar{r}_h^k(x, a) - r_h^k(x, a) \geq - \textbf{bias}_r(k, h)$$

by Corollary 2 and the fact that $\hat{r}_h^k(x, a) - \bar{r}_h^k(x, a) + r^B_h(x, a) \geq 0$ on $G$.

Similarly, for the term $(\mathbf{B})$, we have

$$(\mathbf{B}) = \hat{P}_h^k (V_{h+1}^k - V_{k,h+1}^*) (x, a) + (\hat{P}_h^k - \bar{P}_h^k) V_{k,h+1}^*(x, a) + (\bar{P}_h^k - P_h^k) V_{k,h+1}^*(x, a) + p^B_h(x, a) \\ \geq \hat{P}_h^k (V_{h+1}^k - V_{k,h+1}^*) (x, a) - \textbf{bias}_p(k, h)$$
which gives us

$$
\begin{align*}
\tilde{Q}_h^k(x, a) - Q_{k,h}^*(x, a) & \\
&\geq \hat{P}_h^k (V_{h+1}^k - V_{k,h+1}^*) (x, a) - (\mathbf{bias}_r(k, h) + \mathbf{bias}_p(k, h)) \\
&= \hat{P}_h^k (V_{h+1}^k - V_{k,h+1}^*) (x, a) + \sum_{h'=h+1}^H \mathbf{bias}(k, h) - \sum_{h'=h}^H \mathbf{bias}(k, h) \\
&\geq \hat{P}_h^k \left( V_{h+1}^k + \sum_{h'=h+1}^H \mathbf{bias}(k, h) - V_{k,h+1}^* \right) (x, a) - \sum_{h'=h}^H \mathbf{bias}(k, h) \\
&\geq - \sum_{h'=h}^H \mathbf{bias}(k, h) \quad \text{by the induction hypothesis.}
\end{align*}
$$

Consequently, for all $(x, a)$ and all $s \in [k-1]$, we have

$$
\begin{align*}
Q_{k,h}^*(x, a) - \sum_{h'=h}^{H} \mathbf{bias}(k, h) &\le Q_{k,h}^*(x_h^s, a_h^s) + L\rho[(x, a), (x_h^s, a_h^s)] - \sum_{h'=h}^{H} \mathbf{bias}(k, h) \\
&\le \tilde{Q}_h^k(x_h^s, a_h^s) + L\rho[(x, a), (x_h^s, a_h^s)]
\end{align*}
$$

since $Q_{k,h}^*$ is L-Lipschitz. Which implies the result

$$
Q_{k,h}^*(x, a) - \sum_{h'=h}^{H} \mathbf{bias}(k, h) \le \min_{s \in [k-1]} \left[ \tilde{Q}_h^k(x_h^s, a_h^s) + L \rho[(x, a), (x_h^s, a_h^s)] \right] = Q_h^k(x, a).
$$

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

**Corollary 3.** Let $Q_{k,h}^+$ and $V_{k,h}^+$ be defined as as

$$
Q_{k,h}^{+}(x, a) \stackrel{\text{def}}{=} Q_{h}^{k}(x, a) + \sum_{h'=h}^{H} \mathbf{bias}(k, h'), \quad V_{k,h}^{+}(x) \stackrel{\text{def}}{=} \min\left(H, \max_{a} Q_{k,h}^{+}(x, a)\right)
$$

Then,

$$
\sup_{x \in \mathcal{X}} |V_h^k(x) - V_{k,h}^+(x)| \le \sum_{h'=h}^{H} \mathbf{bias}(k, h')
$$

and, by Lemma 10, we have $V_{k,h}^+ \ge V_{k,h}^*$ on the event $\mathcal{G}$.

Proof. For any $x \in \mathcal{X}$,

$$
\begin{align*}
|V_h^k(x) - V_{k,h}^+(x)| &= \left| \min(H, \max_a Q_h^k(x, a)) - \min(H, \max_a Q_{k,h}^+(x, a)) \right| \\
&\le \left| \max_a Q_h^k(x, a) - \max_a Q_{k,h}^+(x, a) \right| \\
&\le \max_a \left| Q_h^k(x, a) - Q_{k,h}^+(x, a) \right| \\
&= \sum_{h'=h}^H \mathbf{bias}(k, h').
\end{align*}
$$

where we used the fact that, for any $a, b, c \in \mathbb{R}$, we have $|\min(a, b) - \min(a, c)| \le |b - c|$.

<figure><img src="image_6.png" /></figure>
## F Regret bounds

Using the results proved in the previous sections, we are now ready to prove our regret bounds. We first start by proving that the regret is bounded by sums involving $\sqrt{1/C_h^k(x, a)}$, $1/C_h^k(x, a)$ and bias terms. Then, we provide upper bounds for these sums, which result in the final regret bounds.

In Theorem 1, we prove two regret bounds, $\mathcal{R}_1$ and $\mathcal{R}_2$. Here, we refer to $\mathcal{R}_1$ as a UCRL-type regret bound and to $\mathcal{R}_2$ as a UCBVI-type bound, due to the technique used to bound the difference between $\hat{P}_h^k$ and $P_h^k$. Making an analogy with finite MDPs, in UCRL (Jaksch et al., 2010), a term analogous to $\|\hat{P}_h - P_h^k\|_1$ is bounded (as in Lemma 7), whereas in UCBVI (Azar et al., 2017), the term $|(\hat{P}_h - P_h^k)V_{k,h+1}^*|$ is bounded (as in Lemma 5).

**Corollary 4.** Let $\delta_h^k \stackrel{\text{def}}{=} V_h^k(x_h^k) - V_{k,h}^k(x_h^k)$. Then, on $\mathcal{G}$

$$ \mathcal{R}(K) \leq \sum_{k=1}^{K} \delta_{1}^{k} + \sum_{k=1}^{K} \sum_{h=1}^{H} \text{bias}(k, h). $$

*Proof.* It follows directly from Lemma 10:

$$ \mathcal{R}(K) = \sum_{k=1}^{K} V_{k,1}^{*}(x_{1}^{k}) - V_{k,h}^{*}(x_{1}^{k}) \leq \sum_{k=1}^{K} \left( V_{1}^{k}(x_{1}^{k}) + \sum_{h=1}^{H} \text{bias}(k, h) - V_{k,h}^{*}(x_{1}^{k}) \right). $$

**Definition 8.** For any $(k, h)$, let $(\tilde{x}_h^k, \tilde{a}_h^k)$ be defined as

$$ (\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)] $$

that is, the state-action pair in the history that is the closest to $(x_h^k, a_h^k)$.

## F.1 Regret bound in terms of the sum of exploration bonuses (UCRL-type)

**Lemma 11** (UCRL-type bound with sum of bonuses). On the event $\mathcal{G}$, the regret of KeRNS is bounded by

$$ \mathcal{R}(K) \lesssim \sum_{k=1}^{K} \sum_{h=1}^{H} \left( \frac{H \sqrt{|\mathcal{C}_{\sigma}|}}{\sqrt{\mathbf{C}_{h}^{k}(\tilde{x}_{h}^{k}, \tilde{a}_{h}^{k})}} + \frac{\beta H}{\mathbf{C}_{h}^{k}(\tilde{x}_{h}^{k}, \tilde{a}_{h}^{k})} \right) \mathbb{I}\{\rho[(x_{h}^{k}, a_{h}^{k}), (\tilde{x}_{h}^{k}, \tilde{a}_{h}^{k})] \le 2\sigma\} + H^2 |\mathcal{C}_{\sigma}| \\ + \sum_{k=1}^{K} \sum_{h=1}^{H} \tilde{\xi}_{h+1}^{k} + H \sum_{k=1}^{K} \sum_{h=1}^{H} \text{bias}(k, h) + LKH\sigma $$

where $|\mathcal{C}_{\sigma}|$ is the $\sigma$-covering number of $(\mathcal{X} \times \mathcal{A}, \rho)$, $|\mathcal{C}'_{\sigma}|$ is the $\sigma$-covering number of $(\mathcal{X}, \rho_{\mathcal{X}})$ and $(\tilde{\xi}_{h+1}^k)_{k,h}$ is a martingale difference sequence with respect to $(\mathcal{F}_h^k)_{k,h}$ bounded by $4H$.
**Proof.** **Regret decomposition** On $G$, we upper bound $\delta_h^k$ using the following decomposition:

$$
\begin{align*}
\delta_h^k &= V_h^k(x_h^k) - V_{k,h}^{\pi_k}(x_h^k) \\
&\le Q_h^k(x_h^k, a_h^k) - Q_{k,h}^{\pi_k}(x_h^k, a_h^k) \\
&\le Q_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - Q_{k,h}^{\pi_k}(x_h^k, a_h^k) + L \rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)], \quad \text{since } Q_h^k \text{ is } L\text{-Lipschitz} \\
&\le \tilde{Q}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - Q_{k,h}^{\pi_k}(x_h^k, a_h^k) + L \rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)], \quad \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) \\
&= \hat{r}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - r_h^k(x_h^k, a_h^k) + \hat{P}_h^k V_{h+1}^k(\tilde{x}_h^k, \tilde{a}_h^k) - P_h^k V_{k,h+1}^{\pi_k}(x_h^k, a_h^k) + \mathbf{B}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) + L \rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] \\
&= \underbrace{\hat{r}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - r_h^k(x_h^k, a_h^k)}_{(\mathbf{A})} + \underbrace{\left[\hat{P}_h^k - P_h^k\right] V_{k,h+1}^*(\tilde{x}_h^k, \tilde{a}_h^k)}_{(\mathbf{B})} + \underbrace{\left[\hat{P}_h^k - P_h^k\right] (V_{h+1}^k - V_{k,h+1}^*)(\tilde{x}_h^k, \tilde{a}_h^k)}_{(\mathbf{C})} \\
&\quad + P_h^k V_{h+1}^k(\tilde{x}_h^k, \tilde{a}_h^k) - P_h^k V_{k,h+1}^{\pi_k}(x_h^k, a_h^k) + \mathbf{B}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) + 2L \rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)].
\end{align*}
$$

Now, we bound each term $(\mathbf{A})-(\mathbf{D})$ separately.

**Term (A):**

$$
\begin{align*}
(\mathbf{A}) &= \hat{r}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - r_h^k(\tilde{x}_h^k, \tilde{a}_h^k) + r_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - r_h^k(x_h^k, a_h^k) \\
&\le \hat{r}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - r_h^k(\tilde{x}_h^k, \tilde{a}_h^k) + L_r \rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] \\
&= \hat{r}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - \tilde{r}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) + \tilde{r}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - r_h^k(\tilde{x}_h^k, \tilde{a}_h^k) + L_r \rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] \\
&\le r \mathbf{B}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) + \text{bias}_r(k, h) + L_r \rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)]
\end{align*}
$$

by the definition of $G$ and Corollary 2.

**Term (B):**

$$
\begin{align*}
(\mathbf{B}) &= [\hat{P}_h^k - P_h^k] V_{k,h+1}^*(\tilde{x}_h^k, \tilde{a}_h^k) = [\hat{P}_h^k - \bar{P}_h^k] V_{k,h+1}^*(\tilde{x}_h^k, \tilde{a}_h^k) + [\bar{P}_h^k - P_h^k] V_{k,h+1}^*(\tilde{x}_h^k, \tilde{a}_h^k) \\
&\le {}^p\mathbf{B}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) + \text{bias}_p(k, h).
\end{align*}
$$

**Term (C):** Using Corollary 2, we obtain

$$
\begin{align*}
(\mathbf{C}) &= [\hat{P}_h^k - P_h^k] (V_{h+1}^k - V_{k,h+1}^*) (\tilde{x}_h^k, \tilde{a}_h^k) \\
&\le [\hat{P}_h^k - \bar{P}_h^k] (V_{h+1}^k - V_{k,h+1}^*) (\tilde{x}_h^k, \tilde{a}_h^k) + 2 \text{bias}_p(k, h) \\
&\le \sqrt{\frac{8H^2 \Box_2^p(k, \delta/8)}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} + \frac{2\beta H}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} + \theta_b^1(k, \delta/8)\sigma^{1+d_2/2} + \theta_b^2(k, \delta/8)\sigma + 2 \text{bias}_p(k, h) \\
&\lesssim \sqrt{\frac{H^2 |C_\sigma'|}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} + \frac{\beta H}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} + L\sigma + 2 \text{bias}_p(k, h)
\end{align*}
$$

by the definition of $G$.

**Term (D):** From Assumption 2, for any $L$-Lipschitz function, the mapping $(x, a) \mapsto P_h^k f(x, a)$ is $L_p L$-Lipschitz. Consequently,

$$
\begin{align*}
(\mathbf{D}) &= P_h^k V_{h+1}^k(\tilde{x}_h^k, \tilde{a}_h^k) - P_h^k V_{k,h+1}^{\pi_k}(x_h^k, a_h^k) \\
&\le P_h^k V_{h+1}^k(x_h^k, a_h^k) - P_h^k V_{k,h+1}^{\pi_k}(x_h^k, a_h^k) + L_p L \rho [(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] \\
&= P_h^k (V_{h+1}^k - V_{k,h+1}^{\pi_k})(x_h^k, a_h^k) + L_p L \rho [(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] \\
&= \delta_{h+1}^k + \xi_{h+1}^k + L_p L \rho [(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)]
\end{align*}
$$
This yields

$$
\delta_1^k \lesssim \sum_{h=1}^{H} \mathbb{I}\{E_h^k\} \sqrt{\frac{H^2 |C_\sigma'|}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} + \sum_{h=1}^{H} \mathbb{I}\{E_h^k\} \frac{\beta H}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} \\
+ \sum_{h=1}^{H} \mathbb{I}\{E_h^k\} \xi_{h+1}^k + H \sum_{h=1}^{H} \text{bias}(k, h) + H \sum_{h=1}^{H} \mathbb{I}\{\bar{E}_h^k\} + HL\sigma
$$

Using Corollary 4, we obtain

$$
\begin{align*}
\mathcal{R}(K) &\le \sum_{k=1}^{K} \delta_1^k + \sum_{k=1}^{K} \sum_{h=1}^{H} \text{bias}(k, h) \\
&\approx \sum_{k=1}^{K} \sum_{h=1}^{H} \mathbb{I}\{E_h^k\} \sqrt{\frac{H^2 |C_\sigma'|}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} + \sum_{k=1}^{K} \sum_{h=1}^{H} \mathbb{I}\{E_h^k\} \frac{\beta H}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} \\
&\quad + \sum_{k=1}^{K} \sum_{h=1}^{H} \mathbb{I}\{E_h^k\} \xi_{h+1}^k + H \sum_{k=1}^{K} \sum_{h=1}^{H} \text{bias}(k, h) + H \sum_{k=1}^{K} \sum_{h=1}^{H} \mathbb{I}\{\bar{E}_h^k\} + KHL\sigma.
\end{align*}
$$

For each $h$, the number of episodes $k$ where the event $\{\rho[(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] > 2\sigma\}$ occurs is bounded by $|C_\sigma|$. Hence, we can 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[(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] > 2\sigma\} \le H^2 |C_\sigma|.
$$

We conclude the proof by recalling the definition $E_h^k \stackrel{\text{def}}{=} \{\rho [(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] \le 2\sigma\}$ and using the fact that $\tilde{\xi}_{h+1}^k \stackrel{\text{def}}{=} \mathbb{I}\{E_h^k\} \xi_{h+1}^k$ is a martingale difference sequence with respect to $(\mathcal{F}_h^k)_{k,h}$ bounded by $4H$. $\square$

## F.2 Regret bound in terms of the sum of exploration bonuses (UCBVI-type)

**Lemma 12** (UCBVI-type bound with sum of bonuses). In the event $G$, the regret of KeRNS is bounded by

$$
\mathcal{R}(K) \lesssim \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 |\mathcal{C}_\sigma'|}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} \right) \mathbb{I}\{\rho[(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] \le 2\sigma\} + H^2 |\mathcal{C}_\sigma| \\
+ \sum_{k=1}^{K} \sum_{h=1}^{H} \left(1 + \frac{1}{H}\right)^h \tilde{\xi}_{h+1}^k + H \sum_{k=1}^{K} \sum_{h=1}^{H} \text{bias}(k, h) + LKH\sigma
$$

where $|C_\sigma|$ is the $\sigma$-covering number of $(\mathcal{X} \times \mathcal{A}, \rho)$, $|C_\sigma'|$ is the $\sigma$-covering number of $(\mathcal{X}, \rho_\mathcal{X})$ and $(\tilde{\xi}_{h+1}^k)_{k,h}$ is a martingale difference sequence with respect to $(\mathcal{F}_h^k)_{k,h}$ bounded by $4H$.

*Proof.* The proof follows the one of Proposition 5 of Domingues et al. (2020). The key difference is that we need to handle the temporal bias. In particular, $V_h^k$ is not an upper bound on $V_{k,h+1}^*$ due to the temporal bias, which makes our proof slightly more technical by introducing $V_{k,h}^+$ (see Cor. 3) when applying the Bernstein-type concentration of Lemma 8.

**Regret decomposition** We use the same regret decomposition as in the proof of Lemma 11. The terms (A), (B) and (D) are bounded in the same way, but we handle the term (C) differently.
Term (C): To bound this term, we use corollaries 2 and 3:

$$
\begin{align*}
(\mathbf{C}) &= [\hat{P}_h^k - P_h^k] (V_{h+1}^k - V_{k,h+1}^*) (\tilde{x}_h^k, \tilde{a}_h^k) \\
&= [\hat{P}_h^k - P_h^k] (V_{k,h+1}^+ - V_{k,h+1}^*) (\tilde{x}_h^k, \tilde{a}_h^k) + [\hat{P}_h^k - P_h^k] (V_{h+1}^k - V_{k,h+1}^+) (\tilde{x}_h^k, \tilde{a}_h^k) \\
&\leq [\hat{P}_h^k - P_h^k] (V_{k,h+1}^+ - V_{k,h+1}^*) (\tilde{x}_h^k, \tilde{a}_h^k) + 2 \sum_{h'=h}^{H} \text{bias}(k, h'), \quad \text{by Cor. 3} \\
&= [\hat{P}_h^k - \bar{P}_h^k] (V_{k,h+1}^+ - V_{k,h+1}^*) (\tilde{x}_h^k, \tilde{a}_h^k) + [\bar{P}_h^k - P_h^k] (V_{h+1}^+ - V_{k,h+1}^+) (\tilde{x}_h^k, \tilde{a}_h^k) + 2 \sum_{h'=h}^{H} \text{bias}(k, h') \\
&\leq [\hat{P}_h^k - \bar{P}_h^k] (V_{k,h+1}^+ - V_{k,h+1}^*) (\tilde{x}_h^k, \tilde{a}_h^k) + 2 \text{bias}_{\mathbf{p}}(k, h) + 2 \sum_{h'=h}^{H} \text{bias}(k, h'), \quad \text{by Cor. 2} \\
&\leq \frac{1}{H} P_h^k (V_{k,h+1}^+ - V_{k,h+1}^*) (\tilde{x}_h^k, \tilde{a}_h^k) + \frac{14H^2 C_2 \square_3 (k, \delta/8) + 2\beta H}{\mathbf{C}_h^k (\tilde{x}_h^k, \tilde{a}_h^k)} \\
&\quad + \theta_b^3(k, \delta/8)\sigma^{1+d_2} + \theta_b^4(k, \delta/8)\sigma + \frac{2}{H} \text{bias}_{\mathbf{p}}(k, h) + 2 \text{bias}_{\mathbf{p}}(k, h) + 2 \sum_{h'=h}^{H} \text{bias}(k, h') \\
&\leq \frac{1}{H} P_h^k (V_{k,h+1}^+ - V_{k,h+1}^*) (x_h^k, a_h^k) + \frac{14H^2 C_2 \square_3 (k, \delta/8) + 2\beta H}{\mathbf{C}_h^k (\tilde{x}_h^k, \tilde{a}_h^k)} + \frac{2L_p L}{H} \rho [(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] \\
&\quad + \theta_b^3(k, \delta/8)\sigma^{1+d_2} + \theta_b^4(k, \delta/8)\sigma + \frac{2}{H} \text{bias}_{\mathbf{p}}(k, h) + 2 \text{bias}_{\mathbf{p}}(k, h) + 2 \sum_{h'=h}^{H} \text{bias}(k, h'),
\end{align*}
$$

where we also used the definition of $\mathcal{G}$ and the fact that the function $(x, a) \mapsto P_h^k(V_{k,h+1}^+ - V_{k,h+1}^*) (x, a)$ is $2L_p L$-Lipschitz, from Assumption 2. Now, since

$$ \square_3(k, \delta) = \tilde{\mathcal{O}}(|C'_\sigma| + d_1 d_2), \quad \theta_b^3(k, \delta) = \tilde{\mathcal{O}}(|C'_\sigma| + d_1 d_2 + L\sigma), \quad \theta_b^4(k, \delta) = \tilde{\mathcal{O}}(L) $$

and $|C'_\sigma| = \mathcal{O}(1/\sigma^{d_2})$, we have

$$
(\mathbf{C}) \lesssim \frac{1}{H} P_h^k \left(V_{k,h+1}^+ - V_{k,h+1}^*\right) (x_h^k, a_h^k) + \frac{H^2 |C'_\sigma|}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} + L\sigma \\
+ \left(2 + \frac{2}{H}\right) \mathbf{bias}_{\mathbf{p}}(k, h) + 2 \sum_{h'=h}^{H} \mathbf{bias}(k, h') + \frac{2L_p L}{H} \rho [(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)].
$$

Using again Corollary 3, we have

$$ \frac{1}{H} P_h^k (V_{k,h+1}^+ - V_{k,h+1}^*) (x_h^k, a_h^k) \leq \frac{1}{H} P_h^k (V_{h+1}^k - V_{k,h+1}^*) (x_h^k, a_h^k) + \frac{1}{H} \sum_{h'=h}^{H} \text{bias}(k, h') $$

which gives us, since $V_{k,h+1}^{\pi_k} \leq V_{k,h+1}^*$,

$$
\begin{align*}
(\mathbf{C}) &\lesssim \frac{1}{H} P_h^k (V_{h+1}^k - V_{k,h+1}^*) (x_h^k, a_h^k) + \frac{H^2 |C'_\sigma|}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} + L\sigma + \sum_{h'=h}^{H} \text{bias}(k, h') + L\rho [(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] \\
&\lesssim \frac{1}{H} P_h^k (V_{h+1}^k - V_{k,h+1}^{\pi_k}) (x_h^k, a_h^k) + \frac{H^2 |C'_\sigma|}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} + L\sigma + \sum_{h'=h}^{H} \text{bias}(k, h') + L\rho [(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)]
\end{align*}
$$

where we omit constants. Notice, however, that there are no constants omitted in the term $\frac{1}{H} P_h^k (V_{h+1}^k - V_{k,h+1}^{\pi_k}) (x_h^k, a_h^k)$.
Putting together the bounds for (A)-(D), we obtain

$$ \delta_h^k \lesssim \left(1 + \frac{1}{H}\right) (\delta_{h+1}^k + \xi_{h+1}^k) + L\rho \left[ (x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k) \right] + 2 \mathbf{B}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) + \frac{H^2 |C_\sigma'|}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} + L\sigma + \sum_{h'=h}^{H} \text{bias}(k, h') $$

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

Let $E_h^k \stackrel{\text{def}}{=} \{\rho [(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] \le 2\sigma\}$. Using the definition of the bonus

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

and the same argument as in the proof of Lemma 11, we obtain

$$ \begin{aligned} \mathcal{R}(K) &\le \sum_{k=1}^{K} \delta_1^k + \sum_{k=1}^{K} \sum_{h=1}^{H} \text{bias}(k, h) \\ &\lesssim \sum_{k=1}^{K} \sum_{h=1}^{H} \mathbb{I}\{E_h^k\} \sqrt{\frac{H^2}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} + \sum_{k=1}^{K} \sum_{h=1}^{H} \mathbb{I}\{E_h^k\} \frac{H^2 |C_\sigma'|}{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} \\ &\quad + \sum_{k=1}^{K} \sum_{h=1}^{H} \mathbb{I}\{E_h^k\} \xi_{h+1}^k + H \sum_{k=1}^{K} \sum_{h=1}^{H} \text{bias}(k, h) + H^2 |C_\sigma'| + KHL\sigma. \end{aligned} $$

As in Lemma 11, we conclude the proof by recalling the definition $E_h^k \stackrel{\text{def}}{=} \{\rho [(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] \le 2\sigma\}$ and using the fact that $\tilde{\xi}_{h+1}^k \stackrel{\text{def}}{=} \mathbb{I}\{E_h^k\} \xi_{h+1}^k$ is a martingale difference sequence with respect to $(\mathcal{F}_h^k)_{k,h}$ bounded by $4H$. $\square$

## F.3 Bounding the sum of bonuses and bias

**Lemma 13.** Let $(\mu_i)_{i \ge 1}$ be a sequence of non-negative numbers. Then,

$$ \sum_{k=1}^{K} \sum_{i=1 \lor (k-W)}^{k-1} \mu_i \le 2W \sum_{i=1}^{K} \mu_i. $$

*Proof.* We have

$$ \begin{aligned} \sum_{k=1}^{K} \sum_{i=1 \lor (k-W)}^{k-1} \mu_i &= \sum_{k=1}^{W} \sum_{i=1}^{k-1} \mu_i + \sum_{k=W+1}^{K} \sum_{i=k-W}^{k-1} \mu_i \le W \sum_{i=1}^{K} \mu_i + \sum_{k=i+1}^{K-1} \sum_{i=i+W}^{i+1} \mu_i \\ &\le W \sum_{i=1}^{K} \mu_i + W \sum_{i=1}^{K} \mu_i = 2W \sum_{i=1}^{K} \mu_i. \end{aligned} $$

**Corollary 5** (bound on the temporal bias). Let $\Delta^r$ and $\Delta^p$ be the variation of the MDP over KH time steps,

$$ \Delta^r \stackrel{\text{def}}{=} \sum_{i=1}^{K} \sum_{h=1}^{H} \sup_{x,a} |r_h^i(x, a) - r_h^{i+1}(x, a)|, \quad \Delta^p \stackrel{\text{def}}{=} \sum_{i=1}^{K} \sum_{h=1}^{H} \sup_{x,a} \mathbb{W}_1 (P_h^i(\cdot|x, a), P_h^{i+1}(\cdot|x, a)). $$

Then,

$$ \sum_{k=1}^{K} \sum_{h=1}^{H} \text{bias}(h, k) \le 2W (\Delta^r + L\Delta^p) + \frac{2C_3(H+1)KH}{\beta} \frac{\eta^W}{1-\eta}. $$
*Proof.* From Lemma 13, we have

$$
\begin{align*}
\sum_{k=1}^{K} \sum_{h=1}^{H} \text{bias}_{\mathbf{p}}(h, k) &= \sum_{k=1}^{K} \sum_{h=1}^{H} L \sum_{i=1 \lor (k-W)}^{k-1} \sup_{x,a} \mathbb{W}_1 (P_h^i(\cdot|x, a), P_h^{i+1}(\cdot|x, a)) + \sum_{k=1}^{K} \sum_{h=1}^{H} \frac{2C_3H}{\beta} \frac{\eta^W}{1-\eta} \\
&\le 2WL \sum_{h=1}^{H} \sum_{i=1}^{K} \sup_{x,a} \mathbb{W}_1 (P_h^i(\cdot|x, a), P_h^{i+1}(\cdot|x, a)) + \frac{2C_3KH^2}{\beta} \frac{\eta^W}{1-\eta}.
\end{align*}
$$

The sum $\sum_{k=1}^{K} \sum_{h=1}^{H} \text{bias}_{\mathbf{r}}(h, k)$ is bounded in the same way, which concludes the proof. $\square$

**Lemma 14 (bounding sum on sliding window).** Let {$a_n$}$_{n \ge 1}$ be a sequence of real numbers such that $0 \le a \le c$ for some constant $c > 0$. Let $A_t = \sum_{n=1 \lor (t-W)}^{t-1} a_n$. Then, for any $p, b > 0$,

$$
\sum_{t=1}^{T} \frac{a_t}{(1 + bA_t)^p} \le \sum_{n=1}^{\lceil T/W \rceil} \left( c + \int_{0}^{A_{nW+1}-c} \frac{1}{(1+bz)^p} dz \right).
$$

*Proof.* We have

$$
\sum_{t=1}^{T} \frac{a_t}{(1 + bA_t)^p} = \underbrace{\sum_{t=1}^{W} \frac{a_t}{(1 + bA_t)^p}}_{\textcircled{1}} + \underbrace{\sum_{t=W+1}^{T} \frac{a_t}{(1 + bA_t)^p}}_{\textcircled{2}}.
$$

By Lemma 9 of Domingues et al. (2020), we have

$$
\textcircled{1} = \sum_{t=1}^{W} \frac{a_t}{(1 + bA_t)^p} \le c + \int_{0}^{A_{W+1} - c} \frac{1}{(1 + bz)^p} dz.
$$

Now, we handle ②:

$$
\begin{align*}
\textcircled{2} \quad &\le \sum_{n=1}^{[T/W]-1} \sum_{t=nW+1}^{(n+1)W} \frac{a_t}{(1+bA_t)^p} = \sum_{n=1}^{[T/W]-1} \sum_{l=1}^{W} \frac{a_{l+nW}}{(1+bA_{l+nW})^p} \\
&\le \sum_{n=1}^{[T/W]-1} \left( c + \int_{0}^{A_{(n+1)W+1}-c} \frac{1}{(1+bz)^p} dz \right).
\end{align*}
$$

**Definition 9.** Consider a $\sigma$-covering of $(\mathcal{X} \times \mathcal{A}, \rho)$, $C_{\sigma} = \{(x_j, a_j) \in \mathcal{X} \times \mathcal{A}, j = 1, \dots, |C_{\sigma}|\}$. We define a partition $\{B_j\}_{j \in [C_{\sigma}]}$ such that

$$
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\}
$$

with ties broken arbitrarily.

**Lemma 15.** Let $U_{\eta} \stackrel{\text{def}}{=} [1/\log(1/\eta)]$ and

$$
\mathbf{N}_h^k(B_j, U_\eta) \stackrel{\text{def}}{=} \sum_{s=1 \lor (k-U_\eta)}^{k-1} \mathbb{I}\{(x_h^s, a_h^s) \in B_j\}.
$$

If $U_\eta \le W$, $\rho[(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] \le 2\sigma$ and $(x_h^k, a_h^k) \in B_j$ then

$$
\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) \geq \beta + G(4)e^{-1}\mathbf{N}_h^k(B_j, U_\eta).
$$
Proof. This result is based on the proof of Proposition 6 of Domingues et al. (2020), which we generalize to the case where the kernel is time-dependent. From Assumption 4, we have $\bar{\Gamma}_{(\sigma, \eta, W)}(k-1-s, z) \ge G(z)\eta^{k-1-s}$ for all $s \ge k-W$. Consequently, if $U_{\eta} \le W$, for all $s \ge k - U_{\eta}$:

$$ \bar{\Gamma}_{(\sigma, \eta, W)}(k-1-s, z) \ge G(z)\eta^{k-1-s} \ge G(z)\eta^{U_{\eta}} \ge G(z) \exp(-1). \quad (3) $$

Also, if $\rho[(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] \le 2\sigma$, $(x_h^k, a_h^k) \in B_j$, and $(x_h^s, a_h^s) \in B_j$, we have

$$ \begin{aligned} \rho[(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^s, a_h^s)] &\le \rho[(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] + \rho[(x_h^k, a_h^k), (x_h^s, a_h^s)] \\ &\le 2\sigma + \rho[(x_h^k, a_h^k), (x_j, a_j)] + \rho[(x_j, a_j), (x_h^s, a_h^s)] \le 4\sigma. \end{aligned} \quad (4) $$

By Assumption 4, the function $z \mapsto \bar{\Gamma}_{(\eta, W)}(t, z)$ is non-increasing. Together with (3) and (4), this yields:

$$ \begin{aligned} \mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) &= \beta + \sum_{s=1}^{k-1} \bar{\Gamma}_{(\sigma, \eta, W)} \left( k-1-s, \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} \bar{\Gamma}_{(\sigma, \eta, W)} \left( k-1-s, \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 + \sum_{s=1 \vee (k-U_{\eta})}^{k-1} \bar{\Gamma}_{(\sigma, \eta, W)}(k-1-s, 4) \mathbb{I}\{(x_h^s, a_h^s) \in B_j\} \\ &\ge \beta + G(4)e^{-1} \sum_{s=k-U_{\eta}}^{k-1} \mathbb{I}\{(x_h^s, a_h^s) \in B_j\}, \end{aligned} $$

which concludes the proof. $\square$

**Lemma 16.** Let $U_{\eta} = [1/\log(1/\eta)]$. If $U_{\eta} \le W$, we have

$$ \begin{aligned} & \sum_{k=1}^{K} \sum_{h=1}^{H} \frac{1}{\sqrt{\mathbf{C}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} \mathbb{I}\{\rho[(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] \le 2\sigma\} \lesssim H \left[\frac{K}{U_{\eta}}\right] \left( |C_{\sigma}| + \sqrt{|C_{\sigma}| U_{\eta}} \right) \\ & \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[(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] \le 2\sigma\} \lesssim H |C_{\sigma}| \left[\frac{K}{U_{\eta}}\right]. \end{aligned} $$

Proof. The proof relies on Lemmas 14 and 15.

Here, we define the constant $c$ as $c = G(4)\beta^{-1}e^{-1} > 0$, since $G(4) > 0$ by Assumption 4.
Bounding the sum $\sum_k 1/\sqrt{C_h^k}$

$$
\begin{align*}
& \sum_{k=1}^{K} \frac{1}{\sqrt{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} \mathbb{I}\{\rho[(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] \le 2\sigma\} \\
&= \sum_{j=1}^{|C_\sigma|} \sum_{k=1}^{K} \frac{1}{\sqrt{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} \mathbb{I}\{\rho[(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] \le 2\sigma\} \mathbb{I}\{(x_h^k, a_h^k) \in B_j\} \\
&\le \beta^{-1/2} \sum_{j=1}^{|C_\sigma|} \sum_{k=1}^{K} \frac{\mathbb{I}\{(x_h^k, a_h^k) \in B_j\}}{\sqrt{1+c\mathbf{N}_h^k(B_j, U_\eta)}}, \quad \text{by Lemma 15} \\
&\le \beta^{-1/2} \sum_{j=1}^{|C_\sigma|} \sum_{n=1}^{[K/U_\eta]} \left(1 + \int_0^{\mathbf{N}_h^{nU_\eta+1}(B_j, U_\eta)} \frac{1}{\sqrt{1+cz}} dz\right), \quad \text{by Lemma 14} \\
&= \beta^{-1/2} |C_\sigma| \left[\frac{K}{U_\eta}\right] + \frac{2\beta^{-1/2}}{c} \sum_{n=1}^{[K/U_\eta]} \sum_{j=1}^{|C_\sigma|} \sqrt{1+c\mathbf{N}_h^{nU_\eta+1}(B_j, U_\eta)} \\
&\le \beta^{-1/2} |C_\sigma| \left[\frac{K}{U_\eta}\right] + \frac{2\beta^{-1/2}}{c} \sum_{n=1}^{[K/U_\eta]} \sqrt{|C_\sigma|} \sqrt{|C_\sigma| + c\sum_{j=1}^{|C_\sigma|} \mathbf{N}_h^{nU_\eta+1}(B_j, U_\eta)}, \quad \text{by Cauchy-Schwarz inequality} \\
&\le \beta^{-1/2} |C_\sigma| \left[\frac{K}{U_\eta}\right] + \frac{2\beta^{-1/2}}{c} \sum_{n=1}^{[K/U_\eta]} \sqrt{|C_\sigma|} \sqrt{|C_\sigma| + cU_\eta} \lesssim |C_\sigma| \left[\frac{K}{U_\eta}\right] + \sqrt{|C_\sigma|} |U_\eta| \left[\frac{K}{U_\eta}\right].
\end{align*}
$$

Bounding the sum $\sum_k 1/C_h^k$

$$
\begin{align*}
& \sum_{k=1}^{K} \frac{1}{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} \mathbb{I}\{\rho[(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] \le 2\sigma\} \\
&= \sum_{j=1}^{|C_\sigma|} \sum_{k=1}^{K} \frac{1}{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} \mathbb{I}\{\rho[(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] \le 2\sigma\} \mathbb{I}\{(x_h^k, a_h^k) \in B_j\} \\
&\le \beta^{-1} \sum_{j=1}^{|C_\sigma|} \sum_{k=1}^{K} \frac{\mathbb{I}\{(x_h^k, a_h^k) \in B_j\}}{1+c\mathbf{N}_h^k(B_j, U_\eta)}, \quad \text{by Lemma 15} \\
&\le \beta^{-1} \sum_{j=1}^{|C_\sigma|} \sum_{n=1}^{[K/U_\eta]} \left(1 + \int_0^{\mathbf{N}_h^{nU_\eta+1}(B_j, U_\eta)} \frac{1}{1+cz} dz\right), \quad \text{by Lemma 14} \\
&= \beta^{-1} |C_\sigma| \left[\frac{K}{U_\eta}\right] + \frac{\beta^{-1} |C_\sigma|}{c} \sum_{n=1}^{[K/U_\eta]} \sum_{j=1}^{|C_\sigma|} \frac{1}{|C_\sigma|} \log \left(1 + c\mathbf{N}_h^{nU_\eta+1}(B_j, U_\eta)\right) \\
&\le \beta^{-1} |C_\sigma| \left[\frac{K}{U_\eta}\right] + \frac{\beta^{-1} |C_\sigma|}{c} \sum_{n=1}^{[K/U_\eta]} \log \left(1 + \frac{c}{|C_\sigma|} \sum_{j=1}^{|C_\sigma|} \mathbf{N}_h^{nU_\eta+1}(B_j, U_\eta)\right), \quad \text{by Jensen's inequality} \\
&\le \beta^{-1} |C_\sigma| \left[\frac{K}{U_\eta}\right] + \frac{\beta^{-1} |C_\sigma|}{c} \left[\frac{K}{U_\eta}\right] \log \left(1 + c \frac{U_\eta}{|C_\sigma|}\right) \lesssim |C_\sigma| \left[\frac{K}{U_\eta}\right].
\end{align*}
$$
## F.4 Final regret bounds

### F.4.1 UCRL-type regret bounds

**Theorem 3 (UCRL-type regret bound).** If $U_\eta = [1/\log(1/\eta)] \le W$, the regret of KeRNS is bounded by

$$ \begin{aligned} \mathcal{R}(K) \lesssim & H^2 \left[ \frac{K}{U_\eta} \right] \sqrt{|C'_\sigma|} \left( |C_\sigma| + \sqrt{|C_\sigma| U_\eta} \right) + H^2 |C_\sigma| \left[ \frac{K}{U_\eta} \right] + H^{3/2} \sqrt{K} \\ & + W (\Delta^r + L \Delta^P) H + \frac{\eta^W}{1-\eta} KH^3 \\ & + H^2 |C_\sigma| + LKH\sigma \end{aligned} $$

with probability at least $1 - \delta$, where $|C_\sigma|$ and $|C'_\sigma|$ are the $\sigma$-covering numbers of $(\mathcal{X} \times \mathcal{A}, \rho)$ and $(\mathcal{X}, \rho_\mathcal{X})$, respectively, and

$$ \Delta^r \stackrel{\text{def}}{=} \sum_{i=1}^{K} \sum_{h=1}^{H} \sup_{x,a} |r_h^i(x, a) - r_h^{i+1}(x, a)|, \quad \Delta^P \stackrel{\text{def}}{=} \sum_{i=1}^{K} \sum_{h=1}^{H} \sup_{x,a} \mathbb{W}_1 (P_h^i(\cdot|x, a), P_h^{i+1}(\cdot|x, a)) $$

represent the variation of the rewards and transitions, respectively.

*Proof.* We apply Lemma 11, Lemma 16 and Corollary 5 and the fact that $\mathbb{P}[\mathcal{G}] \ge 1 - \delta/2$ by Lemma 9. To conclude, notice that $\sum_{k=1}^K \sum_{h=1}^H \tilde{\xi}_{h+1}^k \lesssim H\sqrt{KH}$ with probability at least $1 - \delta/2$ by Hoeffding-Azuma's inequality. $\square$

**Corollary 6.** Let $d_1$ and $d_2$ be the covering dimensions of $(\mathcal{X} \times \mathcal{A}, \rho)$ and $(\mathcal{X}, \rho_\mathcal{X})$, respectively. Let $\alpha = \frac{1}{d_1+d_2+3}$, $\Delta = \Delta^r + L\Delta^P$ and

$$ \sigma = K^{-\alpha}, \quad \log\left(\frac{1}{\eta}\right) = \left(\frac{\Delta}{K^{1+\alpha(d_1+d_2)/2}}\right)^{2/3}, \quad W = \frac{\log(K/(1-\eta))}{\log(1/\eta)} $$

Since $W \ge U_\eta = [1/\log(1/\eta)]$, we have, with probability at least $1 - \delta$,

$$ \begin{aligned} \mathcal{R}(K) \lesssim & H^2 \Delta^{\frac{2}{3}} K^{\frac{d_1+d_2/6+1}{d_1+d_2+3}} + H^2 \Delta^{\frac{1}{3}} K^{\frac{d_1+d_2+2}{d_1+d_2+3}} \\ & + H^2 \Delta^{\frac{2}{3}} K^{\frac{d_1+d_2/6+1}{d_1+d_2+3}} + H^{\frac{3}{2}} \sqrt{K} + H \Delta^{\frac{1}{3}} K^{\frac{d_1+d_2+2}{d_1+d_2+3}} \log\left(\frac{HK}{1-\eta}\right) + H^3 \\ & + H^2 K^{\frac{d_1}{d_1+d_2+3}} + LHK^{\frac{d_1+d_2+2}{d_1+d_2+3}} \end{aligned} $$

that is,

$$ \mathcal{R}(K) = \tilde{\mathcal{O}}\left(\Delta^{\frac{1}{3}} K^{\frac{d_1+d_2+2}{d_1+d_2+3}} \left(H^2 + H \log\left(\frac{HK}{1-\eta}\right)\right)\right). $$

Furthermore, if $\limsup_{K \to \infty} \Delta/K = 0$, we have

$$ \eta = \exp\left(-\Delta^{2/3}/K^{\frac{d_1+d_2+2}{d_1+d_2+3}}\right) \underset{K \to \infty}{\sim} 1 - \Delta^{2/3}/K^{\frac{d_1+d_2+2}{d_1+d_2+3}} $$

which implies

$$ \mathcal{R}(K) = \tilde{\mathcal{O}}\left(H^2 \Delta^{\frac{1}{3}} K^{\frac{d_1+d_2+2}{d_1+d_2+3}}\right). $$

*Proof.* Immediate consequence of Theorem 3 and the fact that $|C_\sigma| = \mathcal{O}(\sigma^{-d_1})$ and $|C'_\sigma| = \mathcal{O}(\sigma^{-d_2})$. $\square$
**Corollary 7 (UCRL-type regret bound in discrete case).** If $\mathcal{X} \times \mathcal{A}$ is finite, we can take $\sigma = 0$ and $|\mathcal{C}_\sigma| = X\Lambda$, $|\mathcal{C}'_\sigma| = X$, where $X = |\mathcal{X}|$ and $\Lambda = |\mathcal{A}|$. In this case, Theorem 3 and Corollary 6 give us

$$ \mathcal{R}(K) = \tilde{\mathcal{O}}\left(H^2 X \sqrt{A \Delta^{\frac{1}{3}} K^{\frac{2}{3}}}\right). $$

## F.4.2 UCBVI-type regret bounds

**Theorem 4 (UCBVI-type regret bound).** If $U_\eta = \lceil 1/\log(1/\eta) \rceil \le W$, the regret of KeRNS is bounded by

$$ \begin{aligned} \mathcal{R}(K) \lesssim & H^2 \left[ \frac{K}{U_\eta} \right] \left( |\mathcal{C}_\sigma| + \sqrt{|\mathcal{C}_\sigma| U_\eta} \right) + H^3 |\mathcal{C}_\sigma| |\mathcal{C}'_\sigma| \left[ \frac{K}{U_\eta} \right] + H^{3/2} \sqrt{K} \\ & + W (\Delta^r + L \Delta^p) H + \frac{\eta^W}{1-\eta} KH^3 \\ & + H |\mathcal{C}_\sigma| + LKH\sigma \end{aligned} $$

with probability at least $1 - \delta$, where $|\mathcal{C}_\sigma|$ and $|\mathcal{C}'_\sigma|$ are the $\sigma$-covering numbers of $(\mathcal{X} \times \mathcal{A}, \rho)$ and $(\mathcal{X}, \rho_\mathcal{X})$, respectively, and

$$ \Delta^r \stackrel{\text{def}}{=} \sum_{i=1}^{K} \sum_{h=1}^{H} \sup_{x,a} |r_h^i(x, a) - r_h^{i+1}(x, a)|, \quad \Delta^p \stackrel{\text{def}}{=} \sum_{i=1}^{K} \sum_{h=1}^{H} \sup_{x,a} W_1(P_h^i(\cdot|x, a), P_h^{i+1}(\cdot|x, a)) $$

represent the variation of the rewards and transitions, respectively.

*Proof.* We apply Lemma 12, Lemma 16 and Corollary 5 and the fact that $\mathbb{P}[\mathcal{G}] \ge 1 - \delta/2$ by Lemma 9. To conclude, notice that $\sum_{k=1}^K \sum_{h=1}^H (1 + \frac{1}{H})^h \tilde{\xi}_{h+1}^k \lesssim H\sqrt{KH}$ with probability at least $1 - \delta/2$ by Hoeffding-Azuma's inequality. $\square$
**Corollary 8 (UCBVI-type regret bound in discrete case).** If $\mathcal{X} \times \mathcal{A}$ is finite, we can take $\sigma = 0$ and $|\mathcal{C}_\sigma| = XA$, $|\mathcal{C}'_\sigma| = X$, where $X = |\mathcal{X}|$ and $A = |\mathcal{A}|$. In this case, Theorem 4 gives us

$$ \mathcal{R}(K) \lesssim H^2 \left[ \frac{K}{U_\eta} \right] (XA + \sqrt{XAU_\eta}) + H^3 X^2 A \left[ \frac{K}{U_\eta} \right] + H^{3/2} \sqrt{K} \\ + W (\Delta^r + L \Delta^p) H + \frac{\eta^W}{1-\eta} K H^3 + H^2 X A $$

Let $\Delta = \Delta^r + L\Delta^p$. By choosing

$$ \log \left( \frac{1}{\eta} \right) = \left( \frac{\Delta}{K} \right)^{2/3}, \quad W = \frac{\log(K/(1-\eta))}{\log(1/\eta)} $$

we obtain

$$ \mathcal{R}(K) \lesssim H^2 X A \Delta^{\frac{2}{3}} K^{\frac{1}{3}} + H^2 \sqrt{X A} \Delta^{\frac{1}{3}} K^{\frac{2}{3}} + H^3 X^2 A \Delta^{\frac{2}{3}} K^{\frac{1}{3}} \\ + H^{3/2} \sqrt{K} + \log \left( \frac{K}{1-\eta} \right) H \Delta^{\frac{1}{3}} K^{\frac{2}{3}} + H^3 + H X A. $$

since $W \ge U_\eta = [1/\log(1/\eta)]$. Furthermore, if $\limsup_{K \to \infty} \Delta/K = 0$, we have

$$ \eta = \exp \left( -\Delta^{\frac{2}{3}} / K^{\frac{2}{3}} \right) \underset{K \to \infty}{\sim} 1 - \Delta^{\frac{2}{3}} / K^{\frac{2}{3}} $$

which implies

$$ \mathcal{R}(K) = \tilde{O} \left( H^2 \sqrt{X A} \Delta^{\frac{1}{3}} K^{\frac{2}{3}} + H^3 X^2 A \Delta^{\frac{2}{3}} K^{\frac{1}{3}} \right). $$

**Corollary 9.** Let $d_1$ and $d_2$ be the covering dimensions of $(\mathcal{X} \times \mathcal{A}, \rho)$ and $(\mathcal{X}, \rho_\mathcal{X})$, respectively. Let $\alpha = \frac{1}{d_1+d_2+2}$, $\Delta = \Delta^r + L\Delta^p$ and

$$ \sigma = K^\alpha, \quad \log \left( \frac{1}{\eta} \right) = \left( \frac{\Delta}{HK^{1+\alpha(d_1+d_2)}} \right)^{1/2}, \quad W = \left[ \frac{\log(K/(1-\eta))}{\log(1/\eta)} \right] $$

Since $W \ge U_\eta = [1/\log(1/\eta)]$, we have, with probability at least $1 - \delta$,

$$ \mathcal{R}(K) \lesssim H^2 \left( 1 + \log \left( \frac{K}{1-\eta} \right) \right) \Delta^{\frac{1}{2}} K^{\frac{d_1+d_2+1}{d_1+d_2+2}} + H^{\frac{3}{2}} \Delta^{\frac{1}{4}} K^{\frac{3}{4}} + LHK^{\frac{d_1+d_2+1}{d_1+d_2+2}} + H^2. $$

Furthermore, if $\limsup_{K \to \infty} \Delta/K = 0$, we have

$$ \eta = \exp \left( -\Delta^{1/2} / K^{\frac{d_1+d_2+1}{d_1+d_2+2}} \right) \underset{K \to \infty}{\sim} 1 - \Delta^{1/2} / K^{\frac{d_1+d_2+1}{d_1+d_2+2}} $$

which implies

$$ \mathcal{R}(K) = \tilde{O} \left( H^2 \Delta^{\frac{1}{2}} K^{\frac{d_1+d_2+1}{d_1+d_2+2}} + H^{\frac{3}{2}} \Delta^{\frac{1}{4}} K^{\frac{3}{4}} \right). $$

*Proof.* Immediate consequence of Theorem 4 and the fact that $|\mathcal{C}_\sigma| = O(\sigma^{-d_1})$ and $|\mathcal{C}'_\sigma| = O(\sigma^{-d_2})$. □
# G RS-KeRNS: An efficient version of KeRNS using representative states

RS-KeRNS is described in Algorithm 4, which uses a backward induction on representative states (Algorithm 5) and updates the model online (algorithms 6 and 7). In this section, we introduce the main definitions used by RS-KeRNS, and we analyze its runtime and regret.

## G.1 Definitions

In each episode $k$ and for each $h$, RS-KeRNS keeps and updates sets of representative states $\tilde{\mathcal{X}}_h^k$, actions $\tilde{\mathcal{A}}_h^k$, and next-states $\tilde{\mathcal{Y}}_h^k$, with cardinalities $\tilde{\mathcal{X}}_h^k$, $\tilde{\mathcal{A}}_h^k$ and $\tilde{\mathcal{Y}}_h^k$, respectively. These sets are built using the data observed up to episode $k-1$. We define the following projections:

$$ \zeta_h^{k+1}(x, a) \stackrel{\text{def}}{=} \underset{(\bar{x}, \bar{a}) \in \tilde{\mathcal{X}}_h^k \times \tilde{\mathcal{A}}_h^k}{\operatorname{argmin}} \rho[(x, a), (\bar{x}, \bar{a})], \quad \zeta_h^{k+1}(y) \stackrel{\text{def}}{=} \underset{\bar{y} \in \tilde{\mathcal{Y}}_h^k}{\operatorname{argmin}} \rho_{\mathcal{X}}(y, \bar{y}). $$

where we also assume to have access to the metric $\rho_{\mathcal{X}}$. The definitions below introduce the kernel function and the estimated MDP used by RS-KeRNS.

**Definition 10 (kernel function for RS-KeRNS).** Let $(\alpha_i)_{i \ge 1}$ be a sequence of numbers in $[0, 1]$. RS-KeRNS uses a kernel of the form $\Gamma(t, u, v) = \chi(t)\phi(u, v)$, where

$$ \chi(t) \stackrel{\text{def}}{=} \prod_{i=1}^{t} \alpha_i, \quad \phi(u, v) \stackrel{\text{def}}{=} \exp \left( -\rho[u, v]^2 / (2\sigma^2) \right), $$

and, by convention, $\chi(0) = 1$.

**Definition 11 (empirical MDP for RS-KeRNS).** Let

$$ \tilde{W}_h^{k+1}(x, a) = \sum_{s=1}^{k} \chi(k-s)\phi(\zeta_h^{k+1}(x, a), \zeta_h^{s+1}(x_h^s, a_h^s)). $$

In episode $k+1$, RS-KeRNS uses the following estimate of the reward function

$$ \tilde{r}_h^{k+1}(x, a) = \frac{1}{\beta + \tilde{W}_h^{k+1}(x, a)} \sum_{s=1}^{k} \chi(k-s)\phi(\zeta_h^{k+1}(x, a), \zeta_h^{s+1}(x_h^s, a_h^s)) \tilde{r}_h^s $$

and the following estimate of the transitions

$$ \tilde{P}_h^{k+1}(y|x, a) = \frac{1}{\beta + \tilde{W}_h^{k+1}(x, a)} \sum_{s=1}^{k} \chi(k-s)\phi(\zeta_h^{k+1}(x, a), \zeta_h^{s+1}(x_h^s, a_h^s)) \delta_{\zeta_h^{s+1}(x_h^{s+1})}(y). $$

Also, its exploration bonuses are computed as

$$ \tilde{\mathcal{B}}_h^{k+1}(x, a) \stackrel{\text{def}}{=} \tilde{\mathcal{O}} \left( \frac{H}{\sqrt{\beta + \tilde{W}_h^{k+1}(x, a)}} + \frac{\beta H}{\beta + \tilde{W}_h^{k+1}(x, a)} + L\sigma \right) $$

where the factors hidden by $\tilde{\mathcal{O}}(\cdot)$ are the same as in Definition 5.

At step $h$, RS-KeRNS needs to store the quantities in Def. 11 only for the representatives $(x, a)$ in $\tilde{\mathcal{X}}_h^{k+1} \times \tilde{\mathcal{A}}_h^{k+1}$ and $y \in \tilde{\mathcal{Y}}_h^{k+1}$. We will show that, using the auxiliary quantities defined below, the values of $\tilde{W}_h^k$, $\tilde{r}_h^k$ and $\tilde{P}_h^k$ can be updated online in $\mathcal{O}(\sum_h \tilde{X}_h^k \tilde{\mathcal{A}}_h^k \tilde{\mathcal{Y}}_h^k)$ time per episode $k$.
**Definition 12** (auxiliary quantities for online updates). For any $(h, x, a)$, we define

$$ \tilde{N}_h^{k+1}(x, a, y) \stackrel{\text{def}}{=} \sum_{s=1}^{k} \chi(k-s) \mathbb{I}\{\zeta_h^{s+1}(x_h^s, a_h^s) = (x, a)\} \delta_{\tilde{\zeta}_h^{s+1}(x_{h+1}^s)}(y) $$

$$ \tilde{N}_h^{k+1}(x, a) \stackrel{\text{def}}{=} \sum_{s=1}^{k} \chi(k-s) \mathbb{I}\{\zeta_h^{s+1}(x_h^s, a_h^s) = (x, a)\} $$

$$ \tilde{S}_h^{k+1}(x, a) \stackrel{\text{def}}{=} \sum_{s=1}^{k} \chi(k-s) \mathbb{I}\{\zeta_h^{s+1}(x_h^s, a_h^s) = (x, a)\} \tilde{r}_h^s. $$

Notice that, if $(x, a) \notin \bar{\mathcal{X}}_h^{k+1} \times \bar{\mathcal{A}}_h^{k+1}$, the quantities above are equal to zero.

The following Lemma will be necessary in order to derive online updates.

**Lemma 17.** The empirical MDP used by RS-KeRNS can be computed as

$$ \tilde{r}_h^{k+1}(x, a) = \frac{\sum_{(\bar{x}, \bar{a})} \phi(\zeta_h^{k+1}(x, a), (\bar{x}, \bar{a})) \tilde{S}_h^{k+1}(\bar{x}, \bar{a})}{\beta + \sum_{(\bar{x}, \bar{a})} \phi(\zeta_h^{k+1}(x, a), (\bar{x}, \bar{a})) \tilde{N}_h^{k+1}(\bar{x}, \bar{a})} \quad (5) $$

$$ \tilde{P}_h^{k+1}(y|x, a) = \frac{\sum_{(\bar{x}, \bar{a})} \phi(\zeta_h^{k+1}(x, a), (\bar{x}, \bar{a})) \tilde{N}_h^{k+1}(\bar{x}, \bar{a}, y)}{\beta + \sum_{(\bar{x}, \bar{a})} \phi(\zeta_h^{k+1}(x, a), (\bar{x}, \bar{a})) \tilde{N}_h^{k+1}(\bar{x}, \bar{a})} \quad (6) $$

$$ \tilde{W}_h^{k+1}(x, a) = \sum_{(\bar{x}, \bar{a})} \phi(\zeta_h^{k+1}(x, a), (\bar{x}, \bar{a})) \tilde{N}_h^{k+1}(\bar{x}, \bar{a}) \quad (7) $$

where the sums are over $(\bar{x}, \bar{a}) \in \bar{\mathcal{X}}_h^{k+1} \times \bar{\mathcal{A}}_h^{k+1}$.

*Proof.* It is an immediate consequence of the definitions. For instance,

$$ \begin{align*} \tilde{W}_h^{k+1}(x, a) &= \sum_{s=1}^{k} \chi(k-s) \phi(\zeta_h^{k+1}(x, a), \zeta_h^{s+1}(x_h^s, a_h^s)) \\ &= \sum_{s=1}^{k} \chi(k-s) \phi(\zeta_h^{k+1}(x, a), \zeta_h^{s+1}(x_h^s, a_h^s)) \sum_{(\bar{x}, \bar{a}) \in \bar{\mathcal{X}}_h^{k+1} \times \bar{\mathcal{A}}_h^{k+1}} \mathbb{I}\{\zeta_h^{s+1}(x_h^s, a_h^s) = (\bar{x}, \bar{a})\} \\ &= \sum_{(\bar{x}, \bar{a})} \sum_{s=1}^{k} \chi(k-s) \phi(\zeta_h^{k+1}(x, a), (\bar{x}, \bar{a})) \mathbb{I}\{\zeta_h^{s+1}(x_h^s, a_h^s) = (\bar{x}, \bar{a})\} \\ &= \sum_{(\bar{x}, \bar{a})} \phi(\zeta_h^{k+1}(x, a), (\bar{x}, \bar{a})) \sum_{s=1}^{k} \chi(k-s) \mathbb{I}\{\zeta_h^{s+1}(x_h^s, a_h^s) = (\bar{x}, \bar{a})\} \\ &= \sum_{(\bar{x}, \bar{a})} \phi(\zeta_h^{k+1}(x, a), (\bar{x}, \bar{a})) \tilde{N}_h^{k+1}(\bar{x}, \bar{a}). \end{align*} $$

□
**Algorithm 4 RS-KeRNS**

1: **Input:** global parameters K, H, L, L_r, L_p, β, δ, d, σ, η, W, ε_χ, ε.

2: Initialize representative states, actions and next states: $\tilde{\mathcal{X}}_h = \emptyset, \tilde{\mathcal{A}}_h = \emptyset, \tilde{\mathcal{Y}}_h = \emptyset$, for $h \in [H]$.

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

4: get initial state $x_1^k$

5: compute $(\tilde{Q}_h^k)_h$ using kernel backward induction on the representative sets (Alg. 5).

6: **for** $h = 1, \dots, H$ **do**

7: execute $a_h^k = \operatorname{argmax}_a \tilde{Q}_h^k(x_h^k, a)$, observe reward $\tilde{r}_h^k$ and next state $x_{h+1}^k$

8: update representatives $\tilde{\mathcal{X}}_h, \tilde{\mathcal{A}}_h, \tilde{\mathcal{Y}}_h$ using $\{x_h^k, a_h^k, x_{h+1}^k\}$ with Alg. 6

9: update model using $x_h^k, a_h^k, x_{h+1}^k, \tilde{r}_h^k$ with Alg. 7

10: **end for**

11: **end for**

**Algorithm 5 Kernel Backward Induction on Representative States**

1: **Input:** $\tilde{r}_h^k(\bar{x}, \bar{a})$, $\tilde{P}_h^k(\bar{y}|\bar{x}, \bar{a})$, $\tilde{\mathcal{B}}_h^k(\bar{x}, \bar{a})$ for all $(\bar{x}, \bar{a}, \bar{y}) \in \tilde{\mathcal{X}}_h^k \times \tilde{\mathcal{A}}_h^k \times \tilde{\mathcal{Y}}_h^k$ and all $h \in [H]$.

2: **Initialization:** $\tilde{V}_{H+1}(x) = 0$ for all $x \in \mathcal{X}$

3: **for** $h = H, \dots, 1$ **do**

4: **for** $(\bar{x}, \bar{a}) \in \tilde{\mathcal{X}}_h^k \times \tilde{\mathcal{A}}_h^k$ **do**

5: $\tilde{Q}_{h,\zeta}^k(\bar{x}, \bar{a}) = \tilde{r}_h^k(\bar{x}, \bar{a}) + \tilde{P}_h^k \tilde{V}_{h+1}(\bar{x}, \bar{a}) + \tilde{\mathcal{B}}_h^k(\bar{x}, \bar{a})$

6: **end for**

7: **// Interpolated Q-function.** Defined, but not computed for all $(x, a)$

8: $\tilde{Q}_h^k(x, a) = \min_{(\bar{x}, \bar{a}) \in \tilde{\mathcal{X}}_h^k \times \tilde{\mathcal{A}}_h^k} (\tilde{Q}_{h,\zeta}^k(\bar{x}, \bar{a}) + L\rho[(x, a), (\bar{x}, \bar{a})])$

9: **if** $h > 1$ **then**

10: **// Compute V-function at the next states for the stage $h-1$**

11: **for** $\bar{y} \in \tilde{\mathcal{Y}}_{h-1}^k$ **do**

12: $\tilde{V}_h^k(\bar{y}) = \min(H - h + 1, \max_a \tilde{Q}_h^k(\bar{y}, a))$

13: **end for**

14: **end if**

15: **end for**

16: **Return:** $(\tilde{Q}_h^k)_{h \in [H]}$

**Algorithm 6 Update Representative Sets**

1: **Input:** $\bar{\mathcal{X}}_h^k, \bar{\mathcal{A}}_h^k, \bar{\mathcal{Y}}_h^k, \{x_h^k, a_h^k, x_{h+1}^k\}, \varepsilon, \varepsilon_\mathcal{X}$.

2: **if** $\min_{(\bar{x}, \bar{a}) \in \bar{\mathcal{X}}_h^k \times \bar{\mathcal{A}}_h^k} \rho[(\bar{x}, \bar{a}), (x_h^k, a_h^k)] > \varepsilon$ **then**

3: $\bar{\mathcal{X}}_h^{k+1} = \bar{\mathcal{X}}_h^k \cup \{x_h^k\}, \quad \bar{\mathcal{A}}_h^{k+1} = \bar{\mathcal{A}}_h^k \cup \{a_h^k\}$

4: **else**

5: $\bar{\mathcal{X}}_h^{k+1} = \bar{\mathcal{X}}_h^k, \quad \bar{\mathcal{A}}_h^{k+1} = \bar{\mathcal{A}}_h^k$

6: **end if**

7: **if** $\min_{\bar{y} \in \bar{\mathcal{Y}}_h^k} \rho(\bar{x}, x_{h+1}^k) > \varepsilon_\mathcal{X}$ **then**

8: $\bar{\mathcal{Y}}_h^{k+1} = \bar{\mathcal{Y}}_h^k \cup \{x_{h+1}^k\}$

9: **else**

10: $\bar{\mathcal{Y}}_h^{k+1} = \bar{\mathcal{Y}}_h^k$

11: **end if**
<caption>**Algorithm 7** Online update of RS-KeRNS Model</caption>

1: **Input:** $k, h, x_h^k, a_h^k, x_{h+1}^k, \tilde{r}_h^k$.
2: // Map to representatives
3: Map $(\tilde{x}, \tilde{a}) = \zeta_h^{k+1}(x_h^k, a_h^k)$ and $\tilde{y} = \zeta_h^{k+1}(x_{h+1}^k)$
4: // Update auxiliary quantities
5: $\tilde{N}_h^{k+1}(\tilde{x}, \tilde{a}, \tilde{y}) = 1 + \alpha_{k-s} \tilde{N}_h^k(\tilde{x}, \tilde{a}, \tilde{y})$
6: $\tilde{N}_h^{k+1}(\tilde{x}, \tilde{a}) = 1 + \alpha_{k-s} \tilde{N}_h^k(\tilde{x}, \tilde{a})$
7: $\tilde{S}_h^{k+1}(\tilde{x}, \tilde{a}) = \tilde{r}_h^k + \alpha_{k-s} \tilde{S}_h^k(\tilde{x}, \tilde{a})$
8: // Update empirical MDP
9: **for** $(\bar{x}, \bar{a}) \in \tilde{\mathcal{X}}_h^{k+1} \times \tilde{\mathcal{A}}_h^{k+1}$ **do**
10:     **if** $(\bar{x}, \bar{a}) \in \tilde{\mathcal{X}}_h^k \times \tilde{\mathcal{A}}_h^k$ **then**
11:         // $(\bar{x}, \bar{a})$ was added before episode k
12:         $\tilde{W}_h^{k+1}(\bar{x}, \bar{a}) = \phi((\bar{x}, \bar{a}), (\tilde{x}, \tilde{a})) + \alpha_{k-s} \tilde{W}_h^k(\bar{x}, \bar{a})$
13:         $\tilde{r}_h^{k+1}(\bar{x}, \bar{a}) = \frac{\phi((\bar{x}, \bar{a}), (\tilde{x}, \tilde{a}))}{\beta + \tilde{W}_h^{k+1}(\bar{x}, \bar{a})} \tilde{r}_h^k + \alpha_{k-s} \left( \frac{\beta + \tilde{W}_h^k(\bar{x}, \bar{a})}{\beta + \tilde{W}_h^{k+1}(\bar{x}, \bar{a})} \right) \tilde{r}_h^k(\bar{x}, \bar{a})$
14:         **for** $y \in \tilde{\mathcal{Y}}_h^{k+1}$ **do**
15:             $\tilde{P}_h^{k+1}(y|\bar{x}, \bar{a}) = \frac{\phi((\bar{x}, \bar{a}), (\tilde{x}, \tilde{a}))}{\beta + \tilde{W}_h^{k+1}(\bar{x}, \bar{a})} \delta_{\tilde{y}}(y) + \alpha_{k-s} \left( \frac{\beta + \tilde{W}_h^k(\bar{x}, \bar{a})}{\beta + \tilde{W}_h^{k+1}(\bar{x}, \bar{a})} \right) \tilde{P}_h^k(y|\bar{x}, \bar{a})$
16:         **end for**
17:     **else**
18:         // $(\bar{x}, \bar{a})$ was added in episode k
19:         Initialize $\tilde{r}_h^{k+1}(\bar{x}, \bar{a}), \tilde{P}_h^{k+1}(\cdot|\bar{x}, \bar{a}), \tilde{W}_h^{k+1}(\bar{x}, \bar{a})$ using equations (5), (6) and (7)
20:     **end if**
21: **end for**

## G.2 Online updates & runtime

Assume that we observed a transition $\{x_h^k, a_h^k, x_{h+1}^k, \tilde{r}_h^k\}$ at time $(k, h)$, updated the representative sets, and mapped the transition to the representatives $(\tilde{x}, \tilde{a}, \tilde{y}) \in \tilde{\mathcal{X}}_h^{k+1} \times \tilde{\mathcal{A}}_h^{k+1} \times \tilde{\mathcal{Y}}_h^{k+1}$. We wish to update the estimated MDP given in Def. 11, which, at step $h$, are only stored for $(x, a)$ in $\tilde{\mathcal{X}}_h^{k+1} \times \tilde{\mathcal{A}}_h^{k+1}$ and $y \in \tilde{\mathcal{Y}}_h^{k+1}$.

The auxiliary quantities (Def. 12) are updated as:

$$ \begin{aligned} \tilde{N}_h^{k+1}(\tilde{x}, \tilde{a}, \tilde{y}) &= 1 + \alpha_{k-s} \tilde{N}_h^k(\tilde{x}, \tilde{a}, \tilde{y}) \\ \tilde{N}_h^{k+1}(\tilde{x}, \tilde{a}) &= 1 + \alpha_{k-s} \tilde{N}_h^k(\tilde{x}, \tilde{a}) \\ \tilde{S}_h^{k+1}(\tilde{x}, \tilde{a}) &= \tilde{r}_h^k + \alpha_{k-s} \tilde{S}_h^k(\tilde{x}, \tilde{a}). \end{aligned} $$

We need to update $\tilde{W}_h^k, \tilde{r}_h^k$ and $\tilde{P}_h^k$ for all $(\bar{x}, \bar{a}, \bar{y}) \in \tilde{\mathcal{X}}_h^{k+1} \times \tilde{\mathcal{A}}_h^{k+1} \times \tilde{\mathcal{Y}}_h^{k+1}$. The update rule will depend on whether the $(\bar{x}, \bar{a})$ is a new representative state-action pair (included in episode $k$) or it was visited before episode $k$. These two cases are studied below.

**Case 1:** $(\bar{x}, \bar{a}) \in \tilde{\mathcal{X}}_h^{k+1} \times \tilde{\mathcal{A}}_h^{k+1}$ and $(\bar{x}, \bar{a}) \notin \tilde{\mathcal{X}}_h^k \times \tilde{\mathcal{A}}_h^k$. This means that the representative state-action pair $(\bar{x}, \bar{a})$ was added at time $(k, h)$. In this case, for all $y \in \tilde{\mathcal{Y}}_h^{k+1}$, the quantities $\tilde{r}_h^{k+1}(\bar{x}, \bar{a}), \tilde{P}_h^{k+1}(y|\bar{x}, \bar{a})$ and $\tilde{W}_h^{k+1}(\bar{x}, \bar{a})$ can be initialized using equations (5), (6) and (7). This is done in $\mathcal{O}(\tilde{X}_h^{k+1} \tilde{A}_h^{k+1} \tilde{Y}_h^{k+1})$ time and can happen, at most, for one pair $(\bar{x}, \bar{a})$: the one that was newly added. Therefore, we have a total per-episode runtime of $\mathcal{O}(\sum_{h=1}^H \tilde{X}_h^{k+1} \tilde{A}_h^{k+1} \tilde{Y}_h^{k+1})$ taking this case into account.
**Case 2:** $(\bar{x}, \bar{a}) \in \tilde{\mathcal{X}}_h^k \times \tilde{\mathcal{A}}_h^k$. This means that the representative state-action pair $(\bar{x}, \bar{a})$ was added before episode $k$, which implies that $\zeta_h^{k+1}(\bar{x}, \bar{a}) = \zeta_h^k(\bar{x}, \bar{a}) = (\bar{x}, \bar{a})$. Hence,

$$ 
\begin{align*}
\tilde{W}_h^{k+1}(\bar{x}, \bar{a}) &= \sum_{s=1}^{k} \chi(k-s) \phi(\zeta_h^{k+1}(\bar{x}, \bar{a}), \zeta_h^{s+1}(x_h^s, a_h^s)) \\
&= \phi(\zeta_h^{k+1}(\bar{x}, \bar{a}), \zeta_h^{k+1}(x_h^k, a_h^k)) + \sum_{s=1}^{k-1} \left( \prod_{i=1}^{k-s} \alpha_i \right) \phi(\zeta_h^k(\bar{x}, \bar{a}), \zeta_h^{s+1}(x_h^s, a_h^s)) \\
&= \phi((\bar{x}, \bar{a}), \zeta_h^{k+1}(x_h^k, a_h^k)) + \alpha_{k-s} \sum_{s=1}^{k-1} \left( \prod_{i=1}^{k-s-1} \alpha_i \right) \phi(\zeta_h^k(\bar{x}, \bar{a}), \zeta_h^{s+1}(x_h^s, a_h^s)) \\
&= \phi((\bar{x}, \bar{a}), \zeta_h^{k+1}(x_h^k, a_h^k)) + \alpha_{k-s} \tilde{W}_h^k(\bar{x}, \bar{a}),
\end{align*}
$$

where we used the convention $\chi(0) = 1$. This implies that, for a fixed $(\bar{x}, \bar{a})$, the quantity $\tilde{W}_h^{k+1}(\bar{x}, \bar{a})$ can be updated in $\mathcal{O}(1)$ time, assuming that the mapping $\zeta_h^{k+1}(x_h^k, a_h^k)$ was previously computed (this mapping is only computed once for all the updates, and takes $\mathcal{O}(\tilde{X}_h^{k+1} \times \tilde{A}_h^{k+1})$ time).

Now, notice that

$$ 
\begin{align*}
\tilde{r}_h^{k+1}(\bar{x}, \bar{a}) &= \frac{\sum_{s=1}^{k} \chi(k-s) \phi(\zeta_h^{k+1}(\bar{x}, \bar{a}), \zeta_h^{s+1}(x_h^s, a_h^s)) \tilde{r}_h^s}{\beta + \tilde{W}_h^{k+1}(\bar{x}, \bar{a})} \\
&= \frac{\phi((\bar{x}, \bar{a}), \zeta_h^{k+1}(x_h^k, a_h^k))}{\beta + \tilde{W}_h^{k+1}(\bar{x}, \bar{a})} \tilde{r}_h^k + \alpha_{k-s} \left( \frac{\beta + \tilde{W}_h^k(\bar{x}, \bar{a})}{\beta + \tilde{W}_h^{k+1}(\bar{x}, \bar{a})} \right) \tilde{r}_h^k(\bar{x}, \bar{a})
\end{align*}
$$

where we used again the fact that, in this case, $\zeta_h^{k+1}(\bar{x}, \bar{a}) = \zeta_h^k(\bar{x}, \bar{a})$. Hence, similarly to $\tilde{W}_h^{k+1}(\bar{x}, \bar{a})$, the quantity $\tilde{r}_h^{k+1}(\bar{x}, \bar{a})$ can be updated in $\mathcal{O}(1)$ time. A similar reasoning shows that $\tilde{P}_h^{k+1}(y, \bar{x}, \bar{a})$ can be updated, for all $y \in \tilde{\mathcal{Y}}_h^{k+1}$, in $\mathcal{O}(\tilde{Y}_h^{k+1})$ time:

$$ \tilde{P}_h^{k+1}(y|\bar{x}, \bar{a}) = \frac{\phi((\bar{x}, \bar{a}), \zeta_h^{k+1}(x_h^k, a_h^k))}{\beta + \tilde{W}_h^{k+1}(\bar{x}, \bar{a})} \delta_{\zeta_h^{k+1}(x_h^{k+1})}(y) + \alpha_{k-s} \left( \frac{\beta + \tilde{W}_h^k(\bar{x}, \bar{a})}{\beta + \tilde{W}_h^{k+1}(\bar{x}, \bar{a})} \right) \tilde{P}_h^k(y|\bar{x}, \bar{a}). $$

**Summary** Every time a new transition is observed at time $(k, h)$, the estimators for all $(x, a, y) \in \tilde{\mathcal{X}}_h^{k+1} \times \tilde{\mathcal{A}}_h^{k+1} \times \tilde{\mathcal{Y}}_h^{k+1}$ must be updated. For a given representative $(x, a)$, the updates can be done in $\mathcal{O}(\tilde{Y}_h^{k+1})$ time if it has been observed before episode $k$ (case 2). This results in a total runtime, per episode, of $\mathcal{O}(\sum_h \tilde{X}_h^{k+1} \tilde{A}_h^{k+1} \tilde{Y}_h^{k+1})$ for all the representatives observed before episode $k$. If the representative $(x, a)$ has not been observed before episode $k$ (case 1), the updates require $\mathcal{O}(\tilde{X}_h^{k+1} \tilde{A}_h^{k+1} \tilde{Y}_h^{k+1})$ time, and this can happen, at most, for one state-action pair at each time $(k, h)$. Hence, the total runtime required for the updates is $\mathcal{O}(\sum_h \tilde{X}_h^{k+1} \tilde{A}_h^{k+1} \tilde{Y}_h^{k+1})$ per episode.

## G.3 Regret analysis

The regret analysis of RS-KeRNS is based on the following result, which is a corollary of Lemma 25, and is used to bound the bias introduced by using representative states.
**Corollary 10.** Let $\chi_{(\eta,W)}: \mathbb{N} \to [0, 1]$, consider the following kernel

$$ \Gamma(t, u, v) = \chi_{(\eta, W)}(t) \exp\left(-\rho[u, v]^2/(2\sigma^2)\right) $$

where $u, v \in \mathcal{X} \times \mathcal{A}$. For $s < k$, let

$$ w_h^{k,s}(x, a) = \Gamma(k-s-1, (x, a), (x_h^s, a_h^s)), \quad w_{h,\zeta}^{k,s}(x, a) \stackrel{\text{def}}{=} \Gamma(k-s-1, \zeta_h^k(x, a), \zeta_h^k(x_h^s, a_h^s)) $$

and consider the functions

$$ g_1(x, a) = \frac{\sum_{s=1}^{k-1} w_h^{k,s}(x, a)Y_s}{\beta + \sum_{s=1}^{k-1} w_h^{k,s}(x, a)}, \quad g_1^\zeta(x, a) = \frac{\sum_{s=1}^{k-1} w_{h,\zeta}^{k,s}(x, a)Y_s}{\beta + \sum_{s=1}^{k-1} w_{h,\zeta}^{k,s}(x, a)}, $$

$$ g_2(x, a) = \sqrt{\frac{1}{\beta + \sum_{s=1}^{k-1} w_h^{k,s}(x, a)}}, \quad g_2^\zeta(x, a) = \sqrt{\frac{1}{\beta + \sum_{s=1}^{k-1} w_{h,\zeta}^{k,s}(x, a)}}, $$

$$ g_3(x, a) = \frac{1}{\beta + \sum_{s=1}^{k-1} w_h^{k,s}(x, a)}, \quad g_3^\zeta(x, a) = \frac{1}{\beta + \sum_{s=1}^{k-1} w_{h,\zeta}^{k,s}(x, a)}. $$

where $(Y_s)_{s=1}^{k-1}$ is an arbitrary sequence. Then, $g_1, g_2$ and $g_3$ are Lipschitz continuous, whose Lipschitz constants are bounded by $L_1, L_2$ and $L_3$, respectively, with

$$ L_1 = \frac{4 \max_s |Y_s|}{\sigma} \left( 1 + \sqrt{\log^+(k/\beta)} \right), \quad L_2 = \frac{1 + \sqrt{\log^+(k/\beta)}}{2\beta^{1/2}\sigma}, \quad L_3 = \frac{1 + \sqrt{\log^+(k/\beta)}}{\beta\sigma} $$

Furthermore, for any $(x, a)$ and for $i \in \{1, 2, 3\}$,

$$ |g_i^\zeta(x, a) - g_i(\zeta_h^k(x, a))| \le L_i \max_s \rho [(x_h^s, a_h^s), \zeta_h^k(x_h^s, a_h^s)]. $$

**Proof.** First, let's prove that $g_1, g_2$ and $g_3$ are Lipschitz continuous. From Lemma 25, taking $z = (\rho[(x, a), (x_h^s, a_h^s)])_{s=1}^{k-1}$ and $y = (\rho[(x', a'), (x_h^s, a_h^s)])_{s=1}^{k-1}$ we have

$$ |g_1(x, a) - g_1(x', a')| \le \frac{4 \max_s |Y_s|}{\sigma} \left( 1 + \sqrt{\log^+(k/\beta)} \right) \max_{s \in [k-1]} |z_s - y_s|. $$

By the triangle inequality, for all $s$,

$$ |z_s - y_s| = |\rho[(x, a), (x_h^s, a_h^s)] - \rho[(x', a'), (x_h^s, a_h^s)]| \le \rho[(x, a), (x', a')] $$

which implies

$$ |g_1(x, a) - g_1(x', a')| \le \frac{4 \max_s |Y_s|}{\sigma} \left( 1 + \sqrt{\log^+(k/\beta)} \right) \rho[(x, a), (x', a')]. $$

giving the Lipschitz constant of $g_1$. The Lipschitz constants of $g_2$ and $g_3$ follow similarly from Lemma 25.

Now, let's bound the differences $|g_i^\zeta(x, a) - g_i(\zeta_h^k(x, a))|$. Let $\chi(s) = \chi_{(\eta, W)}(k-s-1)$. For $i=1$, and applying
again Lemma 25, we obtain

$$
\begin{align*}
& \left| g_1^{\zeta}(x, a) - g_1(\zeta_h^k(x, a)) \right| \\
&= \left| \frac{\sum_{s=1}^{k-1} \chi(s) \exp\left(-\frac{\rho[\zeta_h^k(x, a), \zeta_h^k(x_s, a_s)]^2}{2\sigma^2}\right) Y_s}{\beta + \sum_{s=1}^{k-1} \chi(s) \exp\left(-\frac{\rho[\zeta_h^k(x, a), \zeta_h^k(x_s, a_s)]^2}{2\sigma^2}\right)} - \frac{\sum_{s=1}^{k-1} \chi(s) \exp\left(-\frac{\rho[\zeta_h^k(x, a), (x_s, a_s)]^2}{2\sigma^2}\right) Y_s}{\beta + \sum_{s=1}^{k-1} \chi(s) \exp\left(-\frac{\rho[\zeta_h^k(x, a), (x_s, a_s)]^2}{2\sigma^2}\right)} \right| \\
&\le \frac{4 \max_s |Y_s|}{\sigma} \left(1 + \sqrt{\log^+(k/\beta)}\right) \max_{s \in [k-1]} \left| \rho[\zeta_h^k(x, a), \zeta_h^k(x_s, a_s)] - \rho[\zeta_h^k(x, a), (x_s, a_s)] \right| \\
&\le \frac{4 \max_s |Y_s|}{\sigma} \left(1 + \sqrt{\log^+(k/\beta)}\right) \max_{s \in [k-1]} \rho[\zeta_h^k(x_s, a_s), (x_s, a_s)],
\end{align*}
$$

where, in the last line, we used the triangle inequality. The proof for $i \in \{2, 3\}$ also follow from Lemma 25. $\square$

We use Corollary 10 to bound the difference between the estimators and the bonuses of KeRNS, ($\hat{r}_h^k, \hat{P}_h^k, \mathbf{B}_h^k$), and the ones of RS-KeRNS, ($\tilde{r}_h^k, \tilde{P}_h^k, \tilde{\mathbf{B}}_h^k$).

**Lemma 18.** Let $V$ be an arbitrary L-Lipschitz function bounded by $H$. Then, for any $(x, a)$,

$$
\left| (\hat{P}_h^k - \tilde{P}_h^k) V(x, a) \right| \le \frac{4H}{\sigma} \left( 1 + \sqrt{\log^+(k/\beta)} \right) \left( \rho[(x, a), \zeta_h^k(x, a)] + \varepsilon \right) \\
+ 3L\varepsilon_X + 8H \left( 1 + \sqrt{\log^+(k/\beta)} \right) \frac{\varepsilon}{\sigma}
$$

*Proof.* To simplify the notations, let $f(s) \stackrel{\text{def}}{=} \chi(k-s-1)$ for $s \in [k-1]$. We have

$$
\begin{align*}
& \left| (\hat{P}_h^k - \tilde{P}_h^k) V(x, a) \right| \\
&= \left| \frac{\sum_{s=1}^{k-1} f(s) \phi((x, a), (x_h^s, a_h^s)) V(x_{h+1}^s)}{\beta + \sum_{s=1}^{k-1} f(s) \phi((x, a), (x_h^s, a_h^s))} - \frac{\sum_{s=1}^{k-1} f(s) \phi(\zeta_h^k(x, a), \zeta_h^{s+1}(x_h^s, a_h^s)) V(\bar{\zeta}_h^{s+1}(x_{h+1}^s))}{\beta + \sum_{s=1}^{k-1} f(s) \phi(\zeta_h^k(x, a), \zeta_h^{s+1}(x_h^s, a_h^s))} \right| \\
&\le \textcircled{1} + \textcircled{2}
\end{align*}
$$

where ① and ② are defined and bounded below. First,

$$
\begin{align*}
\textcircled{1} &= \left| \frac{\sum_{s=1}^{k-1} f(s) \phi((x, a), (x_h^s, a_h^s)) V(x_{h+1}^s)}{\beta + \sum_{s=1}^{k-1} f(s) \phi((x, a), (x_h^s, a_h^s))} - \frac{\sum_{s=1}^{k-1} f(s) \phi(\zeta_h^k(x, a), \zeta_h^k(x_h^s, a_h^s)) V(\bar{\zeta}_h^k(x_{h+1}^s))}{\beta + \sum_{s=1}^{k-1} f(s) \phi(\zeta_h^k(x, a), \zeta_h^k(x_h^s, a_h^s))} \right| \\
&\le \left| \frac{\sum_{s=1}^{k-1} f(s) \phi((x, a), (x_h^s, a_h^s)) V(x_{h+1}^s)}{\beta + \sum_{s=1}^{k-1} f(s) \phi((x, a), (x_h^s, a_h^s))} - \frac{\sum_{s=1}^{k-1} f(s) \phi((x, a), (x_h^s, a_h^s)) V(\bar{\zeta}_h^k(x_{h+1}^s))}{\beta + \sum_{s=1}^{k-1} f(s) \phi((x, a), (x_h^s, a_h^s))} \right| \\
&\quad + \left| \frac{\sum_{s=1}^{k-1} f(s) \phi((x, a), (x_h^s, a_h^s)) V(\bar{\zeta}_h^k(x_{h+1}^s))}{\beta + \sum_{s=1}^{k-1} f(s) \phi((x, a), (x_h^s, a_h^s))} - \frac{\sum_{s=1}^{k-1} f(s) \phi(\zeta_h^k(x, a), (x_h^s, a_h^s)) V(\bar{\zeta}_h^k(x_{h+1}^s))}{\beta + \sum_{s=1}^{k-1} f(s) \phi(\zeta_h^k(x, a), (x_h^s, a_h^s))} \right| \\
&\quad + \left| \frac{\sum_{s=1}^{k-1} f(s) \phi(\zeta_h^k(x, a), (x_h^s, a_h^s)) V(\bar{\zeta}_h^k(x_{h+1}^s))}{\beta + \sum_{s=1}^{k-1} f(s) \phi(\zeta_h^k(x, a), (x_h^s, a_h^s))} - \frac{\sum_{s=1}^{k-1} f(s) \phi(\zeta_h^k(x, a), \zeta_h^k(x_h^s, a_h^s)) V(\bar{\zeta}_h^k(x_{h+1}^s))}{\beta + \sum_{s=1}^{k-1} f(s) \phi(\zeta_h^k(x, a), \zeta_h^k(x_h^s, a_h^s))} \right| \\
&\le L \max_{s \in [k-1]} \rho_X(x_{h+1}^s, \bar{\zeta}_h^k(x_{h+1}^s)) \\
&\quad + \frac{4H}{\sigma} \left(1 + \sqrt{\log^+(k/\beta)}\right) \rho[(x, a), \zeta_h^k(x, a)] \\
&\quad + \frac{4H}{\sigma} \left(1 + \sqrt{\log^+(k/\beta)}\right) \max_s \rho[(x_h^s, a_h^s), \zeta_h^k(x_h^s, a_h^s)]
\end{align*}
$$

by using the fact that $V$ is L-Lipschitz and Corollary 10.
To bound ②, let $z_s = \rho[\zeta^k(x, a), \zeta^{s+1}(x_h^s, a_h^s)]$ and $y_s = \rho[\zeta^k(x, a), \zeta^k(x_h^s, a_h^s)]$, for $s \in [k-1]$. Using again the fact that V is L-Lipschitz and Corollary 10, we obtain

$$ \begin{aligned} \textcircled{2} &= \left| \frac{\sum_{s=1}^{k-1} f(s) \phi(\zeta_h^k(x, a), \zeta_h^k(x_h^s, a_h^s)) V(\bar{\zeta}_h^k(x_{h+1}^s))}{\beta + \sum_{s=1}^{k-1} f(s) \phi(\zeta_h^k(x, a), \zeta_h^k(x_h^s, a_h^s))} - \frac{\sum_{s=1}^{k-1} f(s) \phi(\zeta_h^k(x, a), \zeta_h^{s+1}(x_h^s, a_h^s)) V(\bar{\zeta}_h^{s+1}(x_{h+1}^s))}{\beta + \sum_{s=1}^{k-1} f(s) \phi(\zeta_h^k(x, a), \zeta_h^{s+1}(x_h^s, a_h^s))} \right| \\ &\le L \max_s \rho_X (\bar{\zeta}^{s+1}(x_{h+1}^s), \zeta^k(x_{h+1}^s)) + \frac{4H}{\sigma} \left(1 + \sqrt{\log^+(k/\beta)}\right) \max_s |z_s - y_s| \\ &\le 2L\varepsilon_X + \frac{4H}{\sigma} \left(1 + \sqrt{\log^+(k/\beta)}\right) \max_s |\rho[\zeta^k(x_h^s, a_h^s), \zeta^{s+1}(x_h^s, a_h^s)]| \\ &\le 2L\varepsilon_X + 8H \left(1 + \sqrt{\log^+(k/\beta)}\right) \frac{\varepsilon}{\sigma}. \end{aligned} $$

By the construction of the algorithm, $\rho_X(x_{h+1}^s, \bar{\zeta}_h^k(x_{h+1}^s)) \le \varepsilon_X$, $\rho[(x_h^s, a_h^s), \zeta_h^k(x_h^s, a_h^s)] \le \varepsilon$, $\rho_X(\bar{\zeta}^{s+1}(x_{h+1}^s), \zeta^k(x_{h+1}^s)) \le 2\varepsilon_X$ and $\rho[\zeta^k(x_h^s, a_h^s), \zeta^{s+1}(x_h^s, a_h^s)] \le 2\varepsilon$, which concludes the proof. □

**Lemma 19.** For any $(x, a)$,

$$ \begin{aligned} |\hat{r}_h^k(x, a) - \check{r}_h^k(x, a)| &\le \frac{4}{\sigma} \left(1 + \sqrt{\log^+(k/\beta)}\right) \left(\rho[(x, a), \zeta_h^k(x, a)] + \varepsilon\right) \\ &\quad + 8 \left(1 + \sqrt{\log^+(k/\beta)}\right) \frac{\varepsilon}{\sigma} \end{aligned} $$

*Proof.* It follows from a similar decomposition as in the proof of Lemma 18, and from Corollary 10. □

**Lemma 20.** For any $(x, a)$, we have,

$$ |\mathbf{B}_h^k(x, a) - \check{\mathbf{B}}_h^k(x, a)| \lesssim \frac{H}{\sigma} \left(1 + \frac{1}{2^{\beta^{1/2}}}\right) \left(\rho[(x, a), \zeta_h^k(x, a)] + \varepsilon\right) + H \left(1 + \frac{1}{\beta^{1/2}}\right) \frac{\varepsilon}{\sigma} $$

*Proof.* To simplify the notations, let $f(s) \stackrel{\text{def}}{=} \chi(k-s-1)$ for $s \in [k-1]$. Using definitions 5, 10, and 11, we have

$$ \begin{aligned} & |\mathbf{B}_h^k(x, a) - \check{\mathbf{B}}_h^k(x, a)| \\ &\lesssim H \underbrace{\left| \frac{1}{\beta + \sum_{s=1}^{k-1} f(s) \phi((x, a), (x_h^s, a_h^s))} \right|}_{\textcircled{1}} - \underbrace{\left| \frac{1}{\beta + \sum_{s=1}^{k-1} f(s) \phi(\zeta_h^k(x, a), \zeta_h^{s+1}(x_h^s, a_h^s))} \right|}_{\textcircled{2}} \\ &\quad + \beta H \underbrace{\left| \frac{1}{\beta + \sum_{s=1}^{k-1} f(s) \phi((x, a), (x_h^s, a_h^s))} - \frac{1}{\beta + \sum_{s=1}^{k-1} f(s) \phi(\zeta_h^k(x, a), \zeta_h^{s+1}(x_h^s, a_h^s))} \right|}_{\textcircled{3}}. \end{aligned} $$
Using Corollary 10, we obtain

$$
\begin{align*}
\textcircled{1} &\le \left| \frac{1}{\beta + \sum_{s=1}^{k-1} f(s) \phi((x, a), (x_h^s, a_h^s))} - \frac{1}{\beta + \sum_{s=1}^{k-1} f(s) \phi(\zeta_h^k(x, a), (x_h^s, a_h^s))} \right| \\
&\quad + \left| \frac{1}{\beta + \sum_{s=1}^{k-1} f(s) \phi(\zeta_h^k(x, a), (x_h^s, a_h^s))} - \frac{1}{\beta + \sum_{s=1}^{k-1} f(s) \phi(\zeta_h^k(x, a), \zeta_h^{s+1}(x_h^s, a_h^s))} \right| \\
&\quad + \left| \frac{1}{\beta + \sum_{s=1}^{k-1} f(s) \phi(\zeta_h^k(x, a), \zeta_h^k(x_h^s, a_h^s))} - \frac{1}{\beta + \sum_{s=1}^{k-1} f(s) \phi(\zeta_h^k(x, a), \zeta_h^{s+1}(x_h^s, a_h^s))} \right| \\
&\le \left( \frac{1 + \sqrt{\log^+(k/\beta)}}{2\beta^{1/2}\sigma} \right) \left( \rho[(x, a), \zeta_h^k(x, a)] + \max_{s \in [k-1]} \rho[(x_h^s, a_h^s), \zeta_h^k(x, a)] \right. \\
&\qquad \left. + \max_{s \in [k-1]} \rho[\zeta_h^k(x_h^s, a_h^s), \zeta_h^{s+1}(x, a)] \right).
\end{align*}
$$

Similarly, Corollary 10 yields

$$
\textcircled{2} \le \left( \frac{1 + \sqrt{\log^+(k/\beta)}}{\beta\sigma} \right) \left( \rho[(x, a), \zeta_h^k(x, a)] + \max_{s \in [k-1]} \rho[(x_h^s, a_h^s), \zeta_h^k(x, a)] \right. \\
\left. \qquad + \max_{s \in [k-1]} \rho[\zeta_h^k(x_h^s, a_h^s), \zeta_h^{s+1}(x, a)] \right).
$$

By the construction of the algorithm, $\rho[(x_h^s, a_h^s), \zeta_h^k(x, a)] \le \varepsilon$ and $\rho[\zeta^k(x_h^s, a_h^s), \zeta^{s+1}(x_h^s, a_h^s)] \le 2\varepsilon$, which
concludes the proof. $\square$

**Lemma 21.** Let $\tilde{Q}_{h,\zeta}^k$ and $\tilde{Q}_{h,\zeta}^k$ be the Q-functions defined in Algorithm 5. Then,

$$
\begin{align*}
\tilde{Q}_h^k(x, a) &\stackrel{\text{def}}{=} \min_{(\bar{x}, \bar{a}) \in \bar{\mathcal{X}}_h^k \times \bar{\mathcal{A}}_h^k} \left( \tilde{Q}_{h,\zeta}^k(\bar{x}, \bar{a}) + L \rho[(x, a), (\bar{x}, \bar{a})] \right) \\
&= \min_{s \in [k-1]} \left( \tilde{Q}_{h,\zeta}^k(x_h^s, a_h^s) + L \rho[(x, a), \zeta_h^k(x_h^s, a_h^s)] \right).
\end{align*}
$$

*Proof.* Notice that, although $\tilde{Q}_{h,\zeta}^k$ is only computed for the representative state-action pairs, it is defined for any $(x, a)$ as

$$
\tilde{Q}_{h,\zeta}^k(x, a) = \tilde{r}_h^k(x, a) + \tilde{P}_h^k \tilde{V}_{h+1}(x, a) + \tilde{B}_h^k(x, a).
$$

We claim that

$$
\underbrace{\{\zeta_h^k(x_h^s, a_h^s) : s \in [k-1]\}}_{A} = \underbrace{\bar{\mathcal{X}}_h^k \times \bar{\mathcal{A}}_h^k}_{B}.
$$

First, $A \subset B$, since $\forall (s, h)$, we have $\zeta_h^k(x_h^s, a_h^s) \in \bar{\mathcal{X}}_h^k \times \bar{\mathcal{A}}_h^k$. Second, for any $(\bar{x}, \bar{a}) \in \bar{\mathcal{X}}_h^k \times \bar{\mathcal{A}}_h^k$, there exists $(s, h)$ such that $(\bar{x}, \bar{a}) = (x_h^s, a_h^s) = \zeta_h^{s+1}(x_h^s, a_h^s) = \zeta_h^k(x_h^s, a_h^s) \in A$, which implies that $B \subset A$.

Together with the fact that $\tilde{Q}_{h,\zeta}^k(x_h^s, a_h^s) = \tilde{Q}_{h,\zeta}^k(\zeta_h^k(x_h^s, a_h^s))$, which holds by Definition 11 and Algorithm 5, this
concludes the proof. $\square$

**Lemma 22.** The difference between the Q-values computed by *KeRNS* and *RS-KeRNS* are bounded as follows

$$
\sup_{x,a} |Q_h^k(x, a) - \tilde{Q}_h^k(x, a)| \lesssim \left(L(\varepsilon + \varepsilon_{\mathcal{X}}) + \frac{\varepsilon}{\sigma}H\right) (H - h + 1).
$$
Proof. We proceed by induction on h. Let

$$ \epsilon_h \stackrel{\text{def}}{=} \left( L(\epsilon + \epsilon_{\mathcal{X}}) + \frac{\epsilon}{\sigma} H \right) (H - h + 1). $$

For $h = H + 1$, $\epsilon_{H+1} = 0$, $Q_{H+1}^k = \tilde{Q}_{H+1}^k = 0$ and the claim holds.

Now, assume that the claim is true for $h + 1$. In this case, we have, for any $x$,

$$ \begin{aligned} & |V_{h+1}^k(x) - \tilde{V}_{h+1}^k(x)| \\ &= \left| \min \left( H - h, \max_a Q_{h+1}^k(x, a) \right) - \min \left( H - h, \max_a \tilde{Q}_{h+1}^k(x, a) \right) \right| \\ &\le \left| \max_a Q_{h+1}^k(x, a) - \max_a \tilde{Q}_{h+1}^k(x, a) \right| \\ &\le \max_a \left| Q_{h+1}^k(x, a) - \tilde{Q}_{h+1}^k(x, a) \right| \le \epsilon_{h+1}, \end{aligned} $$

where we used induction hypothesis and the fact that, for any $a, b, c \in \mathbb{R}$, we have $|\min(a, b) - \min(a, c)| \le |b - c|$ (Fact 1).

For any $(x_h^s, a_h^s)$ with $s \in [k-1]$, we have

$$ \begin{aligned} & |\tilde{Q}_h^k(x_h^s, a_h^s) - \tilde{Q}_{h,\zeta}^k(x_h^s, a_h^s)| \\ &\le |\hat{r}_h^k(x_h^s, a_h^s) - \tilde{r}_h^k(x_h^s, a_h^s)| + |\mathbf{B}_h^k(x_h^s, a_h^s) - \tilde{\mathbf{B}}_h^k(x_h^s, a_h^s)| \\ &\quad + |(\hat{P}_h^k - \tilde{P}_h^k) V_{h+1}^k(x_h^s, a_h^s) + \tilde{P}_h^k (V_{h+1}^k - \tilde{V}_{h+1}^k)(x_h^s, a_h^s)| \\ &\lesssim \epsilon_{h+1} + \frac{H}{\sigma} (\rho [(x_h^s, a_h^s), \zeta_h^k(x_h^s, a_h^s)] + \epsilon) + L\epsilon_{\mathcal{X}} + \frac{\epsilon}{\sigma} H \end{aligned} $$

where, in the last line, we used the induction hypothesis and lemmas 18, 19 and 20.

By the construction of RS-KerNS, we have $\max_{s' \in [k-1]} \rho [(x_h^{s'}, a_h^{s'}), \zeta_h^k(x_h^{s'}, a_h^{s'})] \le \epsilon$. Consequently,

$$ |\tilde{Q}_h^k(x_h^s, a_h^s) - \tilde{Q}_{h,\zeta}^k(x_h^s, a_h^s)| \lesssim \epsilon_{h+1} + L\epsilon_{\mathcal{X}} + \frac{\epsilon}{\sigma} H. $$

Now, take an arbitrary $(x, a)$. By Lemma 21,

$$ \begin{aligned} \tilde{Q}_h^k(x, a) &= \min_{(\bar{x}, \bar{a}) \in \mathcal{X}_h^k \times \bar{\mathcal{A}}_h^k} \left( \tilde{Q}_{h,\zeta}^k(\bar{x}, \bar{a}) + L\rho \left[ (x, a), (\bar{x}, \bar{a}) \right] \right) \\ &= \min_{s \in [k-1]} \left( \tilde{Q}_{h,\zeta}^k(x_h^s, a_h^s) + L\rho \left[ (x, a), \zeta_h^k(x_h^s, a_h^s) \right] \right) \end{aligned} $$

and, by definition,

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

we obtain, for any $(x, a)$,

$$ \begin{aligned} & |Q_h^k(x, a) - \tilde{Q}_h^k(x, a)| \\ &\lesssim \min_{s \in [k-1]} |\tilde{Q}_h^k(x_h^s, a_h^s) - \tilde{Q}_{h,\zeta}^k(x_h^s, a_h^s)| + L \min_{s \in [k-1]} |\rho[(x, a), (x_h^s, a_h^s)] - \rho[(x, a), \zeta_h^k(x_h^s, a_h^s)]| \\ &\le \epsilon_{h+1} + L\epsilon_{\mathcal{X}} + \frac{\epsilon}{\sigma} H + L \max_{s \in [k-1]} \rho [(x_h^s, a_h^s), \zeta_h^k(x_h^s, a_h^s)] \\ &\le \epsilon_{h+1} + L(\epsilon + \epsilon_{\mathcal{X}}) + \frac{\epsilon}{\sigma} H = \epsilon_h. \end{aligned} $$

which concludes the proof.

□
**Theorem 5 (UCRL-type regret bound for RS-KeRNS).** With probability at least $1-\delta$, the regret of RS-KeRNS is bounded as follows

$$ \mathcal{R}^{\text{RS-KeRNS}}(K) \lesssim \mathcal{R}_1^{\text{KeRNS}}(K) + L(\varepsilon + \varepsilon_{\mathcal{X}})KH^2 + \frac{\varepsilon}{\sigma}KH^3. $$

where $\mathcal{R}_1^{\text{KeRNS}}(K)$ is the UCRL-type regret bound given in Theorem 3 for KeRNS.

*Proof.* Let $\tilde{\pi}_k$ be the policy followed by RS-KeRNS in episode $k$ and let $\tilde{\delta}_h^k \stackrel{\text{def}}{=} \tilde{V}_h^k(x_h^k) - V_{k,h}^{\tilde{\pi}_k}(x_h^k)$

**Regret decomposition** Consider the following decomposition, also used in the proof of Lemma 11:

$$
\begin{aligned}
\tilde{\delta}_h^k &= \tilde{V}_h^k(x_h^k) - V_{k,h}^{\tilde{\pi}_k}(x_h^k) \\
&\le \tilde{Q}_h^k(x_h^k, a_h^k) - Q_{k,h}^{\tilde{\pi}_k}(x_h^k, a_h^k) \\
&\le \tilde{Q}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - Q_{k,h}^{\tilde{\pi}_k}(x_h^k, a_h^k) + L\rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)], \quad \text{since } \tilde{Q}_h^k \text{ is L-Lipschitz} \\
&\le \tilde{Q}_{h,\zeta}^k(\tilde{x}_h^k, \tilde{a}_h^k) - Q_{k,h}^{\tilde{\pi}_k}(x_h^k, a_h^k) + L\rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)], \quad \text{since } \tilde{Q}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) \le \tilde{Q}_{h,\zeta}^k(\tilde{x}_h^k, \tilde{a}_h^k) \\
&= \tilde{r}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - r_h^k(x_h^k, a_h^k) + \tilde{P}_h^k V_{h+1}^k(\tilde{x}_h^k, \tilde{a}_h^k) - P_h^k V_{k,h+1}^{\tilde{\pi}_k}(x_h^k, a_h^k) + \tilde{B}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) + L\rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)] \\
&= \underbrace{\tilde{r}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - r_h^k(x_h^k, a_h^k)}_{(\mathbf{A})} + \underbrace{[\tilde{P}_h^k - P_h^k] V_{k,h+1}^*(\tilde{x}_h^k, \tilde{a}_h^k)}_{(\mathbf{B})} + \underbrace{[\tilde{P}_h^k - P_h^k] (\tilde{V}_{h+1}^k - V_{k,h+1}^*)(\tilde{x}_h^k, \tilde{a}_h^k)}_{(\mathbf{C})} \\
&\quad + P_h^k \tilde{V}_{h+1}^k(\tilde{x}_h^k, \tilde{a}_h^k) - P_h^k V_{k,h+1}^{\tilde{\pi}_k}(x_h^k, a_h^k) + \tilde{B}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) + 2L\rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)].
\end{aligned}
$$

We will use the following results, which are a consequence of Lemmas 18, 19 and 20 and the fact that $\rho [(\tilde{x}_h^k, \tilde{a}_h^k), \zeta(\tilde{x}_h^k, \tilde{a}_h^k)] \le \varepsilon$:

$$ |\hat{r}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - \tilde{r}_h^k(\tilde{x}_h^k, \tilde{a}_h^k)| \lesssim \frac{4}{\sigma} (\rho [(\tilde{x}_h^k, \tilde{a}_h^k), \zeta_h^k(\tilde{x}_h^k, \tilde{a}_h^k)] + \varepsilon) + \frac{8\varepsilon}{\sigma} \lesssim \frac{\varepsilon}{\sigma}. $$

$$
\begin{aligned}
\tilde{B}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) &= B_h^k(\tilde{x}_h^k, \tilde{a}_h^k) + \tilde{B}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - B_h^k(\tilde{x}_h^k, \tilde{a}_h^k) \\
&\lesssim B_h^k(\tilde{x}_h^k, \tilde{a}_h^k) + \frac{H}{\sigma} (\rho [(\tilde{x}_h^k, \tilde{a}_h^k), \zeta_h^k(\tilde{x}_h^k, \tilde{a}_h^k)] + \varepsilon) + \frac{H\varepsilon}{\sigma} \\
&\lesssim B_h^k(\tilde{x}_h^k, \tilde{a}_h^k) + \frac{\varepsilon}{\sigma}H.
\end{aligned}
$$

and, for any function $f$ that is L-Lipschitz and bounded by $H$,

$$ \left| (\hat{P}_h^k - \tilde{P}_h^k) f(\tilde{x}_h^k, \tilde{a}_h^k) \right| \lesssim L\varepsilon_{\mathcal{X}} + \frac{4H}{\sigma} (\rho [(\tilde{x}_h^k, \tilde{a}_h^k), \zeta(\tilde{x}_h^k, \tilde{a}_h^k)] + \varepsilon) + \frac{H\varepsilon}{\sigma} \lesssim L\varepsilon_{\mathcal{X}} + \frac{\varepsilon}{\sigma}H. $$

Now, we bound each term $(\mathbf{A}) - (\mathbf{D})$.

**Term (A):** by Lemma 19, the definition of $\mathcal{G}$ and Corollary 2, we have

$$
\begin{aligned}
(\mathbf{A}) &= \tilde{r}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - \hat{r}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) + \hat{r}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - r_h^k(\tilde{x}_h^k, \tilde{a}_h^k) + r_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - r_h^k(x_h^k, a_h^k) \\
&\lesssim \frac{\varepsilon}{\sigma} + \hat{r}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - r_h^k(\tilde{x}_h^k, \tilde{a}_h^k) + r_h^k(\tilde{x}_h^k, \tilde{a}_h^k) - r_h^k(x_h^k, a_h^k) \\
&\lesssim \frac{\varepsilon}{\sigma} + r \mathbf{B}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) + \text{bias}_r(k, h) + L_r \rho [(\tilde{x}_h^k, \tilde{a}_h^k), (x_h^k, a_h^k)].
\end{aligned}
$$
Term (B):

$$
\begin{align*}
(\mathbf{B}) &= [\tilde{P}_h^k - \hat{P}_h^k] V_{k,h+1}^*(\tilde{x}_h^k, \tilde{a}_h^k) + [\hat{P}_h^k - P_h^k] V_{k,h+1}^*(\tilde{x}_h^k, \tilde{a}_h^k) \\
&\lesssim L\varepsilon_{\mathcal{X}} + \frac{\varepsilon}{\sigma}H + [\hat{P}_h^k - \bar{P}_h^k] V_{k,h+1}^*(\tilde{x}_h^k, \tilde{a}_h^k) + [\bar{P}_h^k - P_h^k] V_{k,h+1}^*(\tilde{x}_h^k, \tilde{a}_h^k) \\
&\le L\varepsilon_{\mathcal{X}} + \frac{\varepsilon}{\sigma}H + {}^p\mathbf{B}_h^k(\tilde{x}_h^k, \tilde{a}_h^k) + \text{bias}_{\mathbf{p}}(k, h)
\end{align*}
$$

Term (C): Using Corollary 2, we obtain

$$
\begin{align*}
(\mathbf{C}) &= [\tilde{P}_h^k - P_h^k] (\tilde{V}_{h+1}^k - V_{k,h+1}^*) (\tilde{x}_h^k, \tilde{a}_h^k) \\
&= [\tilde{P}_h^k - P_h^k] (\tilde{V}_{h+1}^k - V_{k,h+1}^*) (\tilde{x}_h^k, \tilde{a}_h^k) + [\hat{P}_h^k - P_h^k] (\tilde{V}_{h+1}^k - V_{k,h+1}^*) (\tilde{x}_h^k, \tilde{a}_h^k) \\
&\lesssim L\varepsilon_{\mathcal{X}} + \frac{\varepsilon}{\sigma}H + [\hat{P}_h^k - \bar{P}_h^k] (\tilde{V}_{h+1}^k - V_{k,h+1}^*) (\tilde{x}_h^k, \tilde{a}_h^k) + \text{bias}_{\mathbf{p}}(k, h) \\
&\lesssim L\varepsilon_{\mathcal{X}} + \frac{\varepsilon}{\sigma}H + \sqrt{\frac{H^2 |C_{\sigma}'|}{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} + \frac{\beta H}{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} + L\sigma + \text{bias}_{\mathbf{p}}(k, h)
\end{align*}
$$

by the definition of G.

Term (D): From Assumption 2, for any L-Lipschitz function, the mapping (x, a) ↦→ P_h^k f(x, a) is L_pL-Lipschitz.
Consequently,

$$
\begin{align*}
(\mathbf{D}) &= P_h^k \tilde{V}_{h+1}^k (\tilde{x}_h^k, \tilde{a}_h^k) - P_h^k V_{k,h+1}^{\tilde{\pi}_k} (x_h^k, a_h^k) \\
&\leq P_h^k \tilde{V}_{h+1}^k (x_h^k, a_h^k) - P_h^k V_{k,h+1}^{\tilde{\pi}_k} (x_h^k, a_h^k) + L_p L \rho [(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] \\
&= P_h^k (\tilde{V}_{h+1}^k - V_{k,h+1}^{\tilde{\pi}_k}) (x_h^k, a_h^k) + L_p L \rho [(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] \\
&= \tilde{\delta}_{h+1}^k + \xi_{h+1}^k + L_p L \rho [(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)].
\end{align*}
$$

where

$$
\xi_{h+1}^k \stackrel{\text{def}}{=} P_h^k \left( \tilde{V}_{h+1}^k - V_{k,h+1}^{\tilde{\pi}_k} \right) (x_h^k, a_h^k) - \tilde{\delta}_{h+1}^k
$$

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

Putting together the bounds for (A)-(D) and using the definition of the bonuses $\mathbf{B}_h^k$, we obtain

$$
\begin{align*}
\tilde{\delta}_h^k \lesssim \tilde{\delta}_{h+1}^k + \xi_{h+1}^k + L\rho [(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] + \sqrt{\frac{H^2 |C_\sigma'|}{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} \\
+ \frac{\beta H}{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} + L\sigma + \text{bias}(k, h') + L\varepsilon_\chi + \frac{\varepsilon}{\sigma}H
\end{align*}
$$

where the constant in front of $\tilde{\delta}_{h+1}^k$ is exact (i.e., not omitted by $\lesssim$).

Now, we follow the same arguments as in the proof of Lemma 11. Consider the event $E_h^k \stackrel{\text{def}}{=} \{\rho [(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] \le 2\sigma\}$. The inequality above gives us

$$
\begin{align}
& \mathbb{I}\{E_h^k\} \tilde{\delta}_h^k \lesssim \mathbb{I}\{E_h^k\} \tilde{\delta}_{h+1}^k + \mathbb{I}\{E_h^k\} \xi_{h+1}^k + \mathbb{I}\{E_h^k\} \sqrt{\frac{H^2 |C_\sigma'|}{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} \nonumber \\
& \qquad + \mathbb{I}\{E_h^k\} \frac{\beta H}{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} + 3L\sigma + \text{bias}(k, h') + L\varepsilon_\chi + \frac{\varepsilon}{\sigma}H. \tag{8}
\end{align}
$$
Using Lemmas 10 and 22, we upper bound $\mathbb{I}\{E_h^k\} \check{\delta}_{h+1}^k$ in terms of $\check{\delta}_{h+1}^k$:

$$
\begin{align}
\mathbb{I}\{E_h^k\} \check{\delta}_{h+1}^k &= \mathbb{I}\{E_h^k\} (\tilde{V}_{h+1}^k(x_{h+1}^k) - V_{k,h}^{\tilde{\pi}_k}(x_{h+1}^k)) \nonumber \\
&\lesssim \mathbb{I}\{E_h^k\} (HL(\varepsilon + \varepsilon_\mathcal{X}) + \frac{\varepsilon}{\sigma}H^2 + V_{h+1}^k(x_{h+1}^k) - V_{k,h+1}^{\tilde{\pi}_k}(x_{h+1}^k)) \nonumber \\
&\leq HL(\varepsilon + \varepsilon_\mathcal{X}) + \frac{\varepsilon}{\sigma}H^2 + \mathbb{I}\{E_h^k\} \underbrace{(V_{h+1}^k(x_{h+1}^k) + \sum_{h'=h+1}^H \text{bias}(k,h) - V_{k,h+1}^{\tilde{\pi}_k}(x_{h+1}^k))}_{\ge 0 \text{ by Lemma 10}} \nonumber \\
&\leq HL(\varepsilon + \varepsilon_\mathcal{X}) + \frac{\varepsilon}{\sigma}H^2 + V_{h+1}^k(x_{h+1}^k) - V_{k,h+1}^{\tilde{\pi}_k}(x_{h+1}^k) + \sum_{h'=h+1}^H \text{bias}(k,h) \nonumber \\
&\leq 2HL(\varepsilon + \varepsilon_\mathcal{X}) + 2\frac{\varepsilon}{\sigma}H^2 + \tilde{V}_{h+1}^k(x_{h+1}^k) - V_{k,h+1}^{\tilde{\pi}_k}(x_{h+1}^k) + \sum_{h'=h+1}^H \text{bias}(k,h) \nonumber \\
&= \check{\delta}_{h+1}^k + 2HL(\varepsilon + \varepsilon_\mathcal{X}) + 2\frac{\varepsilon}{\sigma}H^2 + \sum_{h'=h+1}^H \text{bias}(k,h) \tag{9}
\end{align}
$$

Let $\bar{E}_h^k$ be the complement of $E_h^k$. Using the inequality above combined with (8), and the fact that $\check{\delta}_h^k \le H$, we obtain

$$
\begin{align}
\check{\delta}_h^k &= \mathbb{I}\{\bar{E}_h^k\} \check{\delta}_h^k + \mathbb{I}\{E_h^k\} \check{\delta}_h^k \tag{10} \\
&\leq H \mathbb{I}\{\bar{E}_h^k\} + \mathbb{I}\{E_h^k\} \check{\delta}_h^k \nonumber \\
&\lesssim H \mathbb{I}\{\bar{E}_h^k\} + \check{\delta}_{h+1}^k + HL(\varepsilon + \varepsilon_\mathcal{X}) + \frac{\varepsilon}{\sigma}H^2 + \sum_{h'=h}^H \text{bias}(k,h) + \mathbb{I}\{E_h^k\} \xi_{h+1}^k \nonumber \\
&\quad + \mathbb{I}\{E_h^k\} \sqrt{\frac{H^2 |C_\sigma'|}{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} + \mathbb{I}\{E_h^k\} \frac{\beta H}{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} + L\sigma \nonumber
\end{align}
$$

Consequently,

$$
\sum_{k=1}^{K} \check{\delta}_1^k \lesssim \sum_{k=1}^{K} \sum_{h=1}^{H} \left( \frac{H \sqrt{|C_\sigma'|}}{\sqrt{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} + \frac{\beta H}{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} \right) \mathbb{I}\{E_h^k\} + H \sum_{k=1}^{K} \sum_{h=1}^{H} \mathbb{I}\{\bar{E}_h^k\} \\
+ \sum_{k=1}^{K} \sum_{h=1}^{H} \mathbb{I}\{E_h^k\} \xi_{h+1}^k + H \sum_{k=1}^{K} \sum_{h=1}^{H} \text{bias}(k,h) + L(\varepsilon + \varepsilon_\mathcal{X})KH^2 + \frac{\varepsilon}{\sigma}KH^3
$$

Now, as in the proof of Lemma 11, we show that

$$
H \sum_{k=1}^{K} \sum_{h=1}^{H} \mathbb{I}\{\bar{E}_h^k\} \leq H^2 |C_\sigma|
$$
and, from lemmas 10 and 22, we have:

$$
\begin{align*}
\mathcal{R}^{\text{RS-KeRNS}}(K) &= \sum_{k=1}^{K} (V_{k,1}^{*}(x_1^k) - V_{k,h}^{\tilde{\pi}_k}(x_1^k)) \\
&\le \sum_{k=1}^{K} (V_1^k(x_1^k) - V_{k,h}^{\tilde{\pi}_k}(x_1^k)) + \sum_{k=1}^{K} \sum_{h=1}^{H} \text{bias}(k, h) \\
&\lesssim \sum_{k=1}^{K} (\tilde{V}_1^k(x_1^k) - V_{k,h}^{\tilde{\pi}_k}(x_1^k)) + \sum_{k=1}^{K} \sum_{h=1}^{H} \text{bias}(k, h) + LKH(\varepsilon + \varepsilon_{\mathcal{X}}) + \frac{\varepsilon}{\sigma}KH^2 \\
&= \sum_{k=1}^{K} \tilde{\delta}_1^k + \sum_{k=1}^{K} \sum_{h=1}^{H} \text{bias}(k, h) + LKH(\varepsilon + \varepsilon_{\mathcal{X}}) + \frac{\varepsilon}{\sigma}KH^2 \\
&\lesssim \sum_{k=1}^{K} \sum_{h=1}^{H} \left( \frac{H\sqrt{|C_{\sigma}|}}{\sqrt{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)}} + \frac{\beta H}{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} \right) \mathbb{I}\{E_h^k\} + H^2 |C_{\sigma}| \\
&\quad + \sum_{k=1}^{K} \sum_{h=1}^{H} \mathbb{I}\{E_h^k\} \xi_{h+1}^k + H \sum_{k=1}^{K} \sum_{h=1}^{H} \text{bias}(k, h) + L(\varepsilon + \varepsilon_{\mathcal{X}})KH^2 + \frac{\varepsilon}{\sigma}KH^3.
\end{align*}
$$

Recall the definition $E_h^k \stackrel{\text{def}}{=} \{\rho[(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] \le 2\sigma\}$ and the fact that $\tilde{\xi}_{h+1}^k \stackrel{\text{def}}{=} \mathbb{I}\{E_h^k\} \xi_{h+1}^k$ is a martingale difference sequence with respect to $(\mathcal{F}_h^k)_{k,h}$ bounded by $4H$. Then, as in the proof of Theorem 3, we obtain

$$
\mathcal{R}^{\text{RS-KeRNS}}(K) \lesssim \mathcal{R}_1^{\text{KeRNS}}(K) + LKH^2(\varepsilon + \varepsilon_{\mathcal{X}}) + \frac{\varepsilon}{\sigma}KH^3
$$

with probability at least $1 - \delta$.

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

**Theorem 6** (UCBVI-type regret bound for RS-KeRNS). With probability at least $1 - \delta$, the regret of RS-KeRNS is bounded as follows

$$
\mathcal{R}^{\text{RS-KeRNS}}(K) \lesssim \mathcal{R}_2^{\text{KeRNS}}(K) + L(\varepsilon + \varepsilon_{\mathcal{X}})KH^2 + \frac{\varepsilon}{\sigma}KH^3.
$$

where $\mathcal{R}_2^{\text{KeRNS}}(K)$ is the UCBVI-type regret bound given in Theorem 4 for KeRNS.

*Proof.* We use the same regret decomposition as in the proof of Theorem 5, but the term (C) is bounded differently (as in Lemma 12).
Using Lemma 18, Lemma 22, and the same arguments as in the proof of Lemma 12, we have

$$
\begin{align*}
(\mathbf{C}) &= [\tilde{P}_h^k - P_h^k] (\tilde{V}_{h+1}^k - V_{k,h+1}^*) (\tilde{x}_h^k, \tilde{a}_h^k) \\
&= [\tilde{P}_h^k - \hat{P}_h^k] (\tilde{V}_{h+1}^k - V_{k,h+1}^*) (\tilde{x}_h^k, \tilde{a}_h^k) + [\hat{P}_h^k - P_h^k] (\tilde{V}_{h+1}^k - V_{k,h+1}^*) (\tilde{x}_h^k, \tilde{a}_h^k) \\
&\lesssim L(\varepsilon + \varepsilon_{\mathcal{X}})H + \frac{\varepsilon}{\sigma}H^2 + [\hat{P}_h^k - P_h^k] (V_{h+1}^k - V_{k,h+1}^*) (\tilde{x}_h^k, \tilde{a}_h^k) \quad (\text{by lemmas 18 and 22}) \\
&\lesssim L(\varepsilon + \varepsilon_{\mathcal{X}})H + \frac{\varepsilon}{\sigma}H^2 + \frac{1}{H}P_h^k (V_{h+1}^k - V_{k,h+1}^*) (x_h^k, a_h^k) + \frac{H^2 |C_{\sigma}'|}{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} \\
&\quad + L\sigma + \sum_{h'=h}^{H} \mathbf{bias}(k, h') + L\rho [(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)] \quad (\text{following the proof of Lemma 12}) \\
&\lesssim L(\varepsilon + \varepsilon_{\mathcal{X}})H + \frac{\varepsilon}{\sigma}H^2 + \frac{1}{H}P_h^k (\tilde{V}_{h+1}^k - V_{k,h+1}^{\tilde{\pi}_k}) (x_h^k, a_h^k) + \frac{H^2 |C_{\sigma}'|}{C_h^k(\tilde{x}_h^k, \tilde{a}_h^k)} \\
&\quad + L\sigma + \sum_{h'=h}^{H} \mathbf{bias}(k, h') + L\rho [(x_h^k, a_h^k), (\tilde{x}_h^k, \tilde{a}_h^k)]
\end{align*}
$$

where, in the last line, we used the fact that $V_{k,h+1}^{\tilde{\pi}_k} \le V_{k,h+1}^*$ and that $V_{k+1}^k \le \tilde{V}_{k+1}^k + L(\varepsilon + \varepsilon_{\mathcal{X}})H + (\varepsilon/\sigma)H^2$ by Lemma 22.

Putting together the bounds for (A) – (D) and using the same arguments as in the proof of Theorem 5, especially the inequalities (8), (9) and (10), we obtain

$$
\sum_{k=1}^{K} \tilde{\delta}_{1}^{k} \lesssim \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} |C_{\sigma}'|}{C_{h}^{k}(\tilde{x}_{h}^{k}, \tilde{a}_{h}^{k})} \right) \mathbb{I} \{ \rho [(x_{h}^{k}, a_{h}^{k}), (\tilde{x}_{h}^{k}, \tilde{a}_{h}^{k})] \le 2\sigma \} + H^{2} |C_{\sigma}| \\
+ \sum_{k=1}^{K} \sum_{h=1}^{H} \left( 1 + \frac{1}{H} \right)^{H-h+1} \tilde{\xi}_{h+1}^{k} + H \sum_{k=1}^{K} \sum_{h=1}^{H} \mathbf{bias}(k, h) + LKH\sigma + L(\varepsilon + \varepsilon_{\mathcal{X}})H^2 + \frac{\varepsilon}{\sigma}H^3
$$

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

Now, from lemmas 10 and 22, we have:

$$
\begin{align*}
\mathcal{R}^{\text{RS-KeRNS}}(K) &= \sum_{k=1}^{K} (V_{k,1}^{*}(x_{1}^{k}) - V_{k,h}^{\tilde{\pi}_{k}}(x_{1}^{k})) \le \sum_{k=1}^{K} (V_{1}^{k}(x_{1}^{k}) - V_{k,h}^{\tilde{\pi}_{k}}(x_{1}^{k})) + \sum_{k=1}^{K} \sum_{h=1}^{H} \text{bias}(k, h) \\
&\lesssim \sum_{k=1}^{K} (\tilde{V}_{1}^{k}(x_{1}^{k}) - V_{k,h}^{\tilde{\pi}_{k}}(x_{1}^{k})) + \sum_{k=1}^{K} \sum_{h=1}^{H} \text{bias}(k, h) + LKH(\varepsilon + \varepsilon_{\mathcal{X}}) + \frac{\varepsilon}{\sigma}KH^2 \\
&= \sum_{k=1}^{K} \tilde{\delta}_{1}^{k} + \sum_{k=1}^{K} \sum_{h=1}^{H} \text{bias}(k, h) + LKH(\varepsilon + \varepsilon_{\mathcal{X}}) + \frac{\varepsilon}{\sigma}KH^2 \\
&\lesssim \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} |C_{\sigma}'|}{C_{h}^{k}(\tilde{x}_{h}^{k}, \tilde{a}_{h}^{k})} \right) \mathbb{I} \{ \rho [(x_{h}^{k}, a_{h}^{k}), (\tilde{x}_{h}^{k}, \tilde{a}_{h}^{k})] \le 2\sigma \} + H^{2} |C_{\sigma}| \\
&\quad + \sum_{k=1}^{K} \sum_{h=1}^{H} \left( 1 + \frac{1}{H} \right)^{h} \tilde{\xi}_{h+1}^{k} + H \sum_{k=1}^{K} \sum_{h=1}^{H} \text{bias}(k, h) + LKH\sigma + L(\varepsilon + \varepsilon_{\mathcal{X}})KH^2 + \frac{\varepsilon}{\sigma}KH^3
\end{align*}
$$

Then, as in the proof of Theorem 4, we obtain

$$
\mathcal{R}^{\text{RS-KeRNS}}(K) \lesssim \mathcal{R}_{2}^{\text{KeRNS}}(K) + L(\varepsilon + \varepsilon_{\mathcal{X}})KH^2 + \frac{\varepsilon}{\sigma}KH^3
$$
with probability at least $1 - \delta$.

☐
## H Technical Lemmas

**Lemma 23** (adapted from Domingues et al. (2020)). Consider a sequence of non-negative real numbers {$z_s$}$_{s=1}^t$ and let $\bar{\Gamma}_{(\eta, W)}: \mathbb{R}_+ \to [0, 1]$ satisfy Assumption 4. For a given $t$, let

$$w_s \stackrel{\text{def}}{=} \bar{\Gamma}_{(\eta, W)} \left(t - s - 1, \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, we have

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

*Proof.* For completeness, we reproduce here the proof of Lemma 7 of Domingues et al. (2020), which also applies to our setting. 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 \ge c} \tilde{w}_s z_s \le c + \sum_{s: z_s \ge c} \tilde{w}_s.$$

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

We want to find $c$ such that:

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

which implies, for $z_s \ge c$, that $\tilde{w}_s \le \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 \exp(-x) \le \beta/(xt)$ for all $x \ge c'$. Let $c' = 2\log(C_1 t / \beta + e)$. If $x \ge c'$, we have:

$$\begin{align*} \frac{x}{2} \ge \log\left(\frac{C_1 t}{\beta} + e\right) &\implies x \ge \frac{x}{2} + \log\left(\frac{C_1 t}{\beta} + e\right) &\implies x \ge \log x + \log(C_1 t / \beta + e) \\ &\implies (C_1 / \beta) \exp(-x) \le 1 / (xt) \end{align*}$$

as we wanted.

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

$$\sum_{s: z_s \ge c} \tilde{w}_s z_s \le \sum_{s: z_s \ge c} \frac{1}{t} \frac{2\sigma^2}{z_s^2} z_s \le \frac{2\sigma^2}{t} \sum_{s: z_s \ge c} \frac{1}{z_s} \le \frac{2\sigma^2}{c} \frac{|\{s: z_s \ge c\}|}{t} \le \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 t / \beta + e)} + \frac{\sigma}{\sqrt{\log(C_1 t / \beta + e)}} \le 2\sigma \left(1 + \sqrt{\log(C_1 t / \beta)}\right). \end{align*}$$

□
**Lemma 24.** Let $\bar{\Gamma}_{(\eta,W)}: \mathbb{R}_+ \to [0,1]$ be a kernel that satisfies Assumption 4. Let $a \in \mathbb{R}_+^t$ and $f_1, f_2, f_3$ be functions from $\mathbb{R}_+^t$ to $\mathbb{R}$ defined as

$$ 
\begin{aligned}
f_1(z) &= \frac{\sum_{s=1}^{t} \bar{\Gamma}_{(\eta, W)} (t-s-1, z_s/\sigma) a_s}{\beta + \sum_{s=1}^{t} \bar{\Gamma}_{(\eta, W)} (t-s-1, z_s/\sigma)}, \\
f_2(z) &= \sqrt{\frac{1}{\beta + \sum_{s=1}^{t} \bar{\Gamma}_{(\eta, W)} (t-s-1, z_s/\sigma)}}, \\
f_3(z) &= \frac{1}{\beta + \sum_{s=1}^{t} \bar{\Gamma}_{(\eta, W)} (t-s-1, z_s/\sigma)}
\end{aligned}
$$

Then, for any $y, z \in \mathbb{R}_+$, we have

$$ 
\begin{aligned}
|f_1(z) - f_1(y)| &\le \frac{2C_2 \|a\|_{\infty} t}{\beta\sigma} \|z - y\|_{\infty} \\
|f_2(z) - f_2(y)| &\le \frac{C_2 t}{2\beta^{3/2}\sigma} \|z - y\|_{\infty} \\
|f_3(z) - f_3(y)| &\le \frac{C_2 t}{\beta^2\sigma} \|z - y\|_{\infty}
\end{aligned}
$$

*Proof.* From Assumption 4, the function $z \mapsto \bar{\Gamma}_{(\eta,W)}(t-s-1, z)$ is $C_2$-Lipschitz, which yields

$$ 
\begin{aligned}
& |f_1(z) - f_1(y)| \\
&\le \left| \frac{\sum_{s=1}^{t} (\bar{\Gamma}_{(\eta,W)}(t-s-1, z_s/\sigma) - \bar{\Gamma}_{(\eta,W)}(t-s-1, y_s/\sigma)) a_s}{\beta + \sum_{s=1}^{t} \bar{\Gamma}_{(\eta,W)}(t-s-1, z_s/\sigma)} \right| \\
&\quad + \left| \frac{\sum_{s=1}^{t} \bar{\Gamma}_{(\eta,W)}(t-s-1, y_s/\sigma) a_s}{\beta + \sum_{s=1}^{t} \bar{\Gamma}_{(\eta,W)}(t-s-1, y_s/\sigma)} \right| \left| \frac{\sum_{s=1}^{t} (\bar{\Gamma}_{(\eta,W)}(t-s-1, z_s/\sigma) - \bar{\Gamma}_{(\eta,W)}(t-s-1, y_s/\sigma))}{\beta + \sum_{s=1}^{t} \bar{\Gamma}_{(\eta,W)}(t-s-1, z_s/\sigma)} \right| \\
&\le \frac{C_2 \sum_{s=1}^{t} (1/\sigma) |z_s - y_s| a_s}{\beta + \sum_{s=1}^{t} \bar{\Gamma}_{(\eta,W)}(t-s-1, z_s/\sigma)} + \|a\|_{\infty} \frac{C_2 \sum_{s=1}^{t} (1/\sigma) |z_s - y_s|}{\beta + \sum_{s=1}^{t} \bar{\Gamma}_{(\eta,W)}(t-s-1, z_s/\sigma)} \\
&\le \frac{2C_2 \|a\|_{\infty} t}{\beta\sigma} \|z - y\|_{\infty}.
\end{aligned}
$$

The proofs for $f_2$ and $f_3$ are analogous. For $f_2$, we also use the fact that the function $x \mapsto (1/\sqrt{\beta+x})$ is $1/(2\beta^{3/2})$-Lipschitz. $\square$

**Lemma 25.** Let $a \in \mathbb{R}_+^t$ and $f_1, f_2, f_3$ be functions from $\mathbb{R}_+^t$ to $\mathbb{R}$ defined as

$$ 
\begin{aligned}
f_1(z) &= \frac{\sum_{s=1}^{t} g(s) \exp(-z_s^2/(2\sigma^2)) a_s}{\beta + \sum_{s=1}^{t} g(s) \exp(-z_s^2/(2\sigma^2))}, \\
f_2(z) &= \sqrt{\frac{1}{\beta + \sum_{s=1}^{t} g(s) \exp(-z_s^2/(2\sigma^2))}}, \\
f_3(z) &= \frac{1}{\beta + \sum_{s=1}^{t} g(s) \exp(-z_s^2/(2\sigma^2))}
\end{aligned}
$$

where $g: \mathbb{N}^* \to [0,1]$ is an arbitrary function bounded by 1. Then, for any $y, z \in \mathbb{R}_+$, we have

$$ 
\begin{aligned}
|f_1(z) - f_1(y)| &\le \frac{4 \|a\|_{\infty}}{\sigma} \left(1 + \sqrt{\log^+(t/\beta)}\right) \|z - y\|_{\infty} \\
|f_2(z) - f_2(y)| &\le \frac{1}{2\beta^{1/2}\sigma} \left(1 + \sqrt{\log^+(t/\beta)}\right) \|z - y\|_{\infty} \\
|f_3(z) - f_3(y)| &\le \frac{1}{\beta\sigma} \left(1 + \sqrt{\log^+(t/\beta)}\right) \|z - y\|_{\infty}
\end{aligned}
$$
Proof. We use the fact that, for any differentiable $f: \mathbb{R}_+^t \to \mathbb{R}$,

$$|f(x) - f(y)| \le \sup_{z \in \mathbb{R}_+^t} \|\nabla f(z)\|_1 \|x - y\|_{\infty}.$$

We have

$$\left| \frac{\partial f_1(z)}{\partial z_i} \right| \le \frac{2 \|a\|_{\infty}}{\sigma^2} \frac{g(i) z_i \exp(-z_i^2/(2\sigma^2))}{\beta + \sum_{s=1}^t g(s) z_s \exp(-z_s^2/(2\sigma^2))}$$

which implies, by Lemma 23,

$$\begin{aligned} \|\nabla f_1(z)\|_1 &\le \frac{2 \|a\|_{\infty}}{\sigma^2} \frac{\sum_{i=1}^t g(i) z_i \exp(-z_i^2/(2\sigma^2))}{\beta + \sum_{s=1}^t g(s) z_s \exp(-z_s^2/(2\sigma^2))} \\ &\le \frac{2 \|a\|_{\infty}}{\sigma^2} 2\sigma \left( 1 + \sqrt{\log^+(t/\beta)} \right) = \frac{4 \|a\|_{\infty}}{\sigma} \left( 1 + \sqrt{\log^+(t/\beta)} \right). \end{aligned}$$

The proofs for $f_2$ and $f_3$ are analogous. □

**Lemma 26** (value functions are Lipschitz continuous). Under Assumptions 1 and 2, for all $(k, h)$, the functions $V_{k,h}^*$ and $Q_{k,h}^*$ are $L_h$-Lipschitz, where $L_h = \sum_{h'=h}^H L_r L_p^{H-h'}$.

Proof. This fact is proved in Lemma 4 of Domingues et al. (2020) and also in Proposition 2.5 of Sinclair et al. (2019). For completeness, we also present a proof here.

We proceed by induction. For $h = H$, $Q_{k,H}^*(x, a) = r_H^k(x, a)$ which is $L_r$-Lipschitz by Assumption 2. Also,

$$V_{k,H}^*(x) - V_{k,H}^*(y) = \max_a Q_{k,H}^*(x, a) - \max_a Q_{k,H}^*(y, a) \le \max_a (Q_{k,H}^*(x, a) - Q_{k,H}^*(y, a)) \quad (11)$$

$$\le \max_a L_H \rho [(x, a), (y, a)] \le L_H \rho_X (x, y), \quad \text{by Assumption 1} \quad (12)$$

which verifies the induction hypothesis for $h = H$, since we can invert the roles of $x$ and $y$ to obtain $|V_{k,H}^*(x) - V_{k,H}^*(y)| \le L_H \rho_X (x, y)$.

Now, assume that the hypothesis is true for $h+1$, i.e., that $V_{k,h+1}^*$ and $Q_{k,h+1}^*$ are $L_{h+1}$-Lipschitz. We have

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

where, in last inequality, we use fact that $V_{k,h+1}^*/L_{h+1}$ is 1-Lipschitz, the definition of the 1-Wasserstein distance and Assumption 2. The same argument used in Eq. 11 shows that $|V_{k,h}^*(x) - V_{k,h}^*(y)| \le L_h \rho_X (x, y)$, which concludes the proof. □

**Fact 1** (small useful result).

$$|\min(a, b) - \min(a, c)| \le |b - c|$$
*Proof.* Since $min(x, y) = (x + y)/2 - |x - y|/2$, we have

$$ 
\begin{aligned}
\min(a,b) - \min(a,c) &= \frac{a+b}{2} - \frac{|a-b|}{2} - \frac{a+c}{2} + \frac{|a-c|}{2} \\
&= \frac{b-c}{2} + \frac{|a-c| - |a-b|}{2} \\
&\le \frac{b-c}{2} + \frac{|b-c|}{2} \\
&\le |b-c|
\end{aligned}
$$

where we used the fact that $|a-c| \le |a-b| + |b-c|$. By symmetry, $\min(a,c) - \min(a,b) \le |b-c|$. which gives us the result. □
# I Experiments

## I.1 Setup

We consider a continuous MDP whose state-space is the unit ball in $\mathbb{R}^2$ with four actions, representing a move to the right, left, up or down. Each action results in a displacement of 0.1 in the corresponding direction, plus a Gaussian noise, in both directions, of standard variation 0.01. The agent starts at (0, 0). Let $b_i^k \in \{0, 0.25, 0.5, 0.75, 1\}$ and $x_i \in \{(0.8, 0.0), (0.0, 0.8), (-0.8, 0.0), (0.0, -0.8)\}$. We consider the following mean reward function:

$$r_h^k(x, a) = \sum_{i=1}^{4} b_i^k \max \left( 0, 1 - \frac{\|x - x_i\|_2}{0.5} \right)$$

Every $N$ episodes, the coefficients $b_i^k$ are changed, which impact the optimal policy.

Taking $\eta = \exp(-(1/N)^{2/3})$, we tested the Gaussian kernel $\Gamma(t, u, v) = \eta^t \exp(-\rho[u, v]^2/(2\sigma^2))$ and a higher-order kernel $\Gamma(t, u, v) = \eta^t \exp(-(\rho[u, v]/\sigma)^4/2)$. We set $\sigma = 0.05$, $\varepsilon = \varepsilon_{\mathcal{N}} = 0.1$, $\beta = 0.01$, $H = 15$.

We ran the experiment with horizon $H = 15$ for $2 \times 10^4$ episodes. Every $N$ episodes, the coefficients $b_i^k$ were changed, according to Table 4.

<table><caption>Table 4: Value of $b_i^k$ according to $x_i$ and the episode $k$</caption><thead><tr><th>episode / x<sub>i</sub></th><th>(0.8, 0.0)</th><th>(0.0, 0.8)</th><th>(-0.8, 0.0)</th><th>(0.0, -0.8)</th></tr></thead><tbody><tr><td>k mod N = 0</td><td>1/4</td><td>0</td><td>0</td><td>0</td></tr><tr><td>k mod N = 1</td><td>1/4</td><td>1/2</td><td>0</td><td>0</td></tr><tr><td>k mod N = 2</td><td>1/4</td><td>1/2</td><td>3/4</td><td>0</td></tr><tr><td>k mod N = 3</td><td>1/4</td><td>1/2</td><td>3/4</td><td>1</td></tr></tbody></table>

We took $\beta = 0.01$ and used the following simplified exploration bonuses:

$$B_h^k(x, a) = \frac{0.1}{\sqrt{C_h^k(x, a)}} + \frac{\beta H}{C_h^k(x, a)} \quad (13)$$

where the factor 0.1 was chosen in order to ensure that the baseline is able to learn a good policy in less than 1000 episodes, i.e., before there is a change in the environment.

Additionally, to take into account the fact that the Lipschitz constant is rarely known in practical problems, we replaced the interpolation step (line 8 of Alg. 5) by a nearest-neighbor search in the representative states:

$$\tilde{Q}_h^k(x, a) = \tilde{Q}_{h, \zeta}^k(x', a'), \quad \text{where} \quad (x', a') = \underset{(\bar{x}, \bar{a}) \in \bar{X}_h^k \times \bar{A}_h^k}{\operatorname{argmin}} \rho[(x, a), (\bar{x}, \bar{a})].$$

## I.2 Results

Figures 2 and 3 show the total reward and the regret of RS-KeRNS compared to baselines for the two choices of kernel function (Gaussian and 4-th order kernel), for 3 different values of $\Delta$, which is determined by the period $N$ of changes in the MDP (the reward changes every $N$ episodes).

In all experiments we observe that Kernel-UCBVI is not able to adapt to the changes in the environment, whereas RS-KeRNS is able to track the behavior of the baseline RestartBaseline which knows when the changes happen and resets the reward estimator when there is a change.
<figure><img src="image_8.png" /><figcaption>Figure 2: Total reward (top row) and regret (bottom row) of RS-KeRNS compared to baselines, using the Gaussian kernel $\Gamma(t, u, v) = \eta^t \exp(-\rho[u, v]^2 / (2\sigma^2))$. The figures on the left, in the middle, and on the right correspond to $N = 1000$, $N = 2000$ and $N = 5000$, respectively, where $N$ is the period of the changes in the MDP. Average over 4 runs.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 3: Total reward (top row) and regret (bottom row) of RS-KeRNS compared to baselines, using the kernel $\Gamma(t, u, v) = \eta^t \exp(-(\rho[u, v]/\sigma)^4/2)$. The figures on the left, in the middle, and on the right correspond to $N = 1000$, $N = 2000$ and $N = 5000$, respectively, where $N$ is the period of the changes in the MDP. Average over 4 runs.</figcaption></figure>