Model-free Posterior Sampling via Learning Rate
Randomization

Daniil Tiapkin¹,² Denis Belomestny³,² Daniele Calandriello⁴ Éric Moulines¹,⁵

Remi Munos⁴ Alexey Naumov² Pierre Perrault⁶ Michal Valko⁴ Pierre Ménard⁷

¹CMAP, École Polytechnique

²HSE University

³Duisburg-Essen University

⁴Google DeepMind

⁵Mohamed Bin Zayed University of AI, UAE

⁶IDEMIA

⁷ENS Lyon

{daniil.tiapkin,eric.moulines}@polytechnique.edu

denis.belomestny@uni-due.de

{dcalandriello,munos,valkom}@google.com anaumov@hse.ru

pierre.perrault@outlook.com pierre.menard@ens-lyon.fr

Abstract

In this paper, we introduce Randomized Q-learning (RandQL), a novel random-
ized model-free algorithm for regret minimization in episodic Markov Decision
Processes (MDPs). To the best of our knowledge, RandQL is the first tractable
model-free posterior sampling-based algorithm. We analyze the performance of
RandQL in both tabular and non-tabular metric space settings. In tabular MDPs,
RandQL achieves a regret bound of order $\tilde{O}(\sqrt{H^5 SAT})$, where H is the planning
horizon, S is the number of states, A is the number of actions, and T is the number
of episodes. For a metric state-action space, RandQL enjoys a regret bound of or-
der $\tilde{O}(H^{5/2}T^{(d_z+1)/(d_z+2)})$, where $d_z$ denotes the zooming dimension. Notably,
RandQL achieves optimistic exploration without using bonuses, relying instead on a
novel idea of learning rate randomization. Our empirical study shows that RandQL
outperforms existing approaches on baseline exploration environments.

# 1 Introduction

In reinforcement learning (RL, Sutton and Barto 1998), an agent learns to interact with an unknown environment by acting, observing the next state, and receiving a reward. The agent's goal is to maximize the sum of the collected rewards. To achieve this, the agent can choose to use model-based or model-free algorithms. In model-based algorithms, the agent builds a model of the environment by inferring the reward function and the transition kernel that produces the next state. The agent then plans in this model to find the optimal policy. In contrast, model-free algorithms directly learn the optimal policy, which is the mapping of a state to an optimal action, or equivalently, the optimal Q-values, which are the mapping of a state-action pair to the expected return of an optimal policy starting by taking the given action at the given state.

Although empirical evidence suggests that model-based algorithms are more sample efficient than model-free algorithms [Deisenroth and Rasmussen, 2011, Schulman et al., 2015]; model-free approaches offer several advantages. These include smaller time and space complexity, the absence of a need to learn an explicit model, and often simpler algorithms. As a result, most of the recent breakthroughs in deep RL, such as those reported by Mnih et al. [2013], Schulman et al. [2015, 2017], Haarnoja et al. [2018], have been based on model-free algorithms, with a few notable exceptions, such as Schrittwieser et al. [2020], Hessel et al. [2021]. Many of these model-free algorithms [Mnih et al., 2013, Van Hasselt et al., 2016, Lillicrap et al., 2016] are rooted in the well-known Q-learning algorithm of Watkins and Dayan [1992]. Q-learning is an off-policy learning technique where the agent follows a behavioral policy while simultaneously incrementally learning the optimal Q-values
by combining asynchronous dynamic programming and stochastic approximation. Until recently, little was known about the sample complexity of Q-learning in the setting where the agent has no access to a simulator allowing to sample an arbitrary state-action pair. In this work, we consider such challenging setting where the environment is modelled by an episodic Markov Decision Process (MDP) of horizon *H*. After *T* episodes, the performance of an agent is measured through regret which is the difference between the cumulative reward the agent could have obtained by acting optimally and what the agent really obtained during the interaction with the MDP.

This framework poses the famous exploration-exploitation dilemma where the agent must balance the need to try new state-action pairs to learn an optimal policy against exploiting the current observations to collect the rewards. One effective approach to resolving this dilemma is to adopt the principle of optimism in the face of uncertainty. In finite MDPs, this principle has been successfully implemented in the model-based algorithm using bonuses [Jaksch et al., 2010, Azar et al., 2017, Fruit et al., 2018, Dann et al., 2017, Zanette and Brunskill, 2019]. Specifically, the upper confidence bounds (UCBs) on the optimal Q-value are built by adding bonuses and then used for planning. Building on this approach, Jin et al. [2018] proposed the OptQL algorithm, which applies a similar bonus-based technique to Q-learning, achieving efficient exploration. Recently, Zhang et al. [2020] introduced a simple modification to OptQL that achieves optimal sample complexity, making it competitive with model-based algorithms.

Another class of methods for optimistic exploration is Bayesian-based approaches. An iconic example among this class is the posterior sampling for reinforcement learning (PSRL, Strens 2000, Osband et al. 2013) algorithm. This model-based algorithm maintains a *surrogate Bayesian model* of the MDP, for instance, a Dirichlet posterior on the transition probability distribution if the rewards are known. At each episode, a new MDP is sampled (i.e., a transition probability for each state-action pair) according to the posterior distribution of the Bayesian model. Then, the agent plans in this sampled MDP and uses the resulting policy to interact with the environment. Notably, an optimistic variant of PSRL, named optimistic posterior sampling for reinforcement learning (OPSRL, Agrawal and Jia, 2017, Tiapkin et al., 2022a) also enjoys an optimal sample complexity [Tiapkin et al., 2022a]. The random least square value iteration (RLSVI, Osband et al. [2013]) is another well-known model-based algorithm that leverages a Bayesian-based technique for exploration. Precisely, RLSVI directly sets a Gaussian prior on the optimal Q-values and then updates the associated posterior trough value iteration in a model [Osband et al., 2013, Russo, 2019]. A close variant of RLSVI proposed by Xiong et al. [2022], using a more sophisticated prior/posterior couple, is also proven to be near-optimal.

It is noteworthy that Bayesian-based exploration techniques have shown superior empirical performance compared to bonus-based exploration, at least in the tabular setting [Osband et al., 2013, Osband and Van Roy, 2017]. Furthermore, these techniques have also been successfully applied to the deep RL setting [Osband et al., 2016, Azizzadenesheli et al., 2018, Fortunato et al., 2018, Li et al., 2022, Sasso et al., 2023]. Finally, Bayesian methods allow for the incorporation of apriori information into exploration (e.g. by giving more weight to important states). However, most of the theoretical studies on Bayesian-based exploration have focused on model-based algorithms, raising the natural question of whether the PSRL approach can be extended to a provably efficient model-free algorithm that matches the good empirical performance of its model-based counterparts. Recently, Dann et al. [2021] proposed a model-free posterior sampling algorithm for structured MDPs, however, it is not computationally tractable. Therefore, a provably tractable model-free posterior sampling algorithm has remained a challenge.

In this paper, we aim to resolve this challenge. We propose the randomized Q-learning (RandQL) algorithm that achieves exploration without bonuses, relying instead on a novel idea of learning rate randomization. RandQL is a tractable model-free algorithm that updates an ensemble of Q-values via Q-learning with Beta distributed step-sizes. If tuned appropriately, the noise introduced by the random learning rates is similar to the one obtained by sampling from the posterior of the PSRL algorithm. Thus, one can see the ensemble of Q-values as posterior samples from the same induced posterior on the optimal Q-values as in PSRL. Then, RandQL chooses among these samples in the same optimistic fashion as OPSRL. We prove that for tabular MDPs, a staged version [Zhang et al., 2020] of RandQL, named Staged-RandQL enjoys the same regret bound as the OptQL algorithm, that is, $\tilde{O}(\sqrt{H^5SAT})$ where *S* is the number of states and *A* the number of actions. Furthermore, we extend Staged-RandQL beyond the tabular setting into the Net-Staged-RandQL algorithm to deal with metric state-action spaces [Domingues et al., 2021c, Sinclair et al., 2019]. Net-Staged-RandQL operates similarly to Staged-RandQL but over a fixed discretization of the state-action space and
uses a specific prior tuning to handle the effect of discretization. We prove that Net-Staged-RandQL enjoys a regret bound of order $\tilde{O}(H^{5/2}T^{(d_c+1)/(d_c+2)})$, where $d_c$ denotes the covering dimension. This rate is of the same order as the one of Adaptive-QL by Sinclair et al. [2019, 2023], an adaptation of OptQL to metric state-action space and has a better dependence on the budget $T$ than one of the model-based kernel algorithms such that Kernel-UCBVI by Domingues et al. [2021c]. We also explain how to adapt Net-Staged-RandQL and its analysis to work with an adaptive discretization as by Sinclair et al. [2019, 2023]. Finally, we provide preliminary experiments to illustrate the good performance of RandQL against several baselines in finite and continuous environments.

We highlight our main contributions:

* The RandQL algorithm, a new tractable (provably efficient) model-free Q-learning adaptation of the PSRL algorithm that explores through randomization of the learning rates.

* A regret bound of order $\tilde{O}(\sqrt{H^5SAT})$ for a staged version of the RandQL algorithm in finite MDPs where $S$ is the number of states and $A$ the number of actions, $H$ the horizon and $T$ the budget.

* A regret bound of order $\tilde{O}(H^{5/2}T^{(d_c+1)/(d_c+2)})$ for an adaptation of RandQL to metric spaces where $d_c$ denotes the covering dimension.

* Adaptive version of metric space extension of RandQL algorithm that achieves a regret bound of order $\tilde{O}(H^{5/2}T^{(d_z+1)/(d_z+2)})$, where $d_z$ is a zooming dimension.

* Experiments in finite and continuous MDPs that show that RandQL is competitive with model-based and model-free baselines while keeping a low time-complexity.

## 2 Setting

We consider an episodic MDP $(S, A, H, \{p_h\}_{h \in [H]}, \{r_h\}_{h \in [H]})$, where $S$ is the set of states, $A$ is the set of actions, $H$ is the number of steps in one episode, $p_h(s'|s, a)$ is the probability transition from state $s$ to state $s'$ upon taking action $a$ at step $h$, and $r_h(s, a) \in [0, 1]$ is the bounded deterministic reward received after taking the action $a$ in state $s$ at step $h$. Note that we consider the general case of rewards and transition functions that are possibly non-stationary, i.e., that are allowed to depend on the decision step $h$ in the episode.

**Policy & value functions** A deterministic policy $\pi$ is a collection of functions $\pi_h: S \to A$ for all $h \in [H]$, where every $\pi_h$ maps each state to a single action. The value functions of $\pi$, denoted by $V_h^\pi$, as well as the optimal value functions, denoted by $V_h^*$ are given by the Bellman and the optimal Bellman equations,

$$ 
\begin{aligned}
Q_h^\pi(s, a) &= r_h(s, a) + p_h V_{h+1}^\pi(s, a) \\
Q_h^*(s, a) &= r_h(s, a) + p_h V_{h+1}^*(s, a)
\end{aligned}
\qquad
\begin{aligned}
V_h^\pi(s) &= \pi_h Q_h^\pi(s) \\
V_h^*(s) &= \max_a Q_h^*(s, a),
\end{aligned}
$$

where by definition, $V_{H+1}^* \triangleq V_{H+1}^\pi \triangleq 0$. Furthermore, $p_h f > (s, a) \triangleq E_{s' \sim p_h(s|s,a)}[f(s')]$ denotes the expectation operator with respect to the transition probabilities $p_h$ and $\pi_h g(s) \triangleq g(s, \pi_h(s))$ denotes the composition with the policy $\pi$ at step $h$.

**Learning problem** The agent, to which the transitions are unknown (the rewards are assumed to be known<fnref n="1" /> for simplicity), interacts with the environment during $T$ episodes of length $H$, with a fixed initial state $s_1$.<fnref n="2" /> Before each episode $t$ the agent selects a policy $\pi^t$ based only on the past observed transitions up to episode $t-1$. At each step $h \in [H]$ in episode $t$, the agent observes a state $s_h^t \in S$, takes an action $\pi_h^t(s_h^t) = a_h^t \in A$ and makes a transition to a new state $s_{h+1}^t$ according to the probability distribution $p_h(s_h^t, a_h^t)$ and receives a deterministic reward $r_h(s_h^t, a_h^t)$.

**Regret** The quality of an agent is measured through its regret, that is the difference between what it could obtain (in expectation) by acting optimally and what it really gets,

$$ \mathfrak{R}^T \triangleq \sum_{t=1}^{T} V_1^*(s_1) - V_1^{\pi^t}(s_1). $$

<footnote n="1">¹Our work can be extended without too much difficulty to the case of random rewards.</footnote>

<footnote n="2">²As explained by Fiechter [1994] if the first state is sampled randomly as $s_1 \sim p$, we can simply add an artificial first state $s_{1'}$ such that for any action $a$, the transition probability is defined as the distribution $p_{1'}(s_{1'}, a) \triangleq p$.</footnote>
**Additional notation** For $N \in \mathbb{N}_{++}$, we define the set $[N] \triangleq \{1, \dots, N\}$. We denote the uniform distribution over this set by $\text{Unif}[N]$. We define the beta distribution with parameters $\alpha, \beta$ as $\text{Beta}(\alpha, \beta)$. Appendix A references all the notation used.

# 3 Randomized Q-learning for Tabular Environments

In this section, we assume that the state space $\mathcal{S}$ is finite of size $\mathcal{S}$ as well as the action space $\mathcal{A}$ of size $\mathcal{A}$. We first provide some intuitions for RandQL algorithm.

## 3.1 Concept

The main idea of RandQL is to perform the usual Q-learning updates but instead of adding bonuses to the targets as OptQL to drive exploration, RandQL injects noise into the updates of the Q-values through noisy learning rates. Precisely, for $J \in \mathbb{N}$, we maintain an ensemble of size $J$ of Q-values$^3$ $(\overline{Q}^{n,j})_{j \in [J]}$ updated with random independent Beta-distributed step-sizes $(w_{n,j})_{j \in [J]}$ where $w_{n,j} \sim \text{Beta}(H, n)$. Then, policy Q-values $\overline{Q}^n$ are obtained by taking the maximum among the Q-values of the ensemble

$$ \overline{Q}_h^{n+1,j}(s, a) = (1 - w_{n,j})\overline{Q}_h^{n,j}(s, a) + w_{n,j}[r_h(s, a) + \overline{V}_{h+1}^n(s_{h+1}^n)] \\ \overline{Q}_h^{n+1}(s, a) = \max_{j \in [J]} \overline{Q}_h^{n+1,j}(s, a), \quad \overline{V}_h^{n+1}(s) = \max_{a \in \mathcal{A}} \overline{Q}_h^{n+1}(s, a), $$

where $s_{h+1}^n$ stands for the next (in time) state after n-th visitation of $(s, a)$ at step $h$.

Note that the policy Q-values $\overline{Q}^n$ are designed to be upper confidence bound on the optimal Q-values. The policy used to interact with the environment is greedy with respect to the policy Q-values $\pi_h^n(s) \in \arg\max_a \overline{Q}_h^n(s, a)$. We provide a formal description of RandQL in Appendix B.

**Connection with OptQL** We observe that the learning rates of RandQL are in expectation of the same order $\mathbb{E}[w_{n,j}] = H/(n+H)$ as the ones used by the OptQL algorithm. Thus, we can view our randomized Q-learning as a noisy version of the OptQL algorithm that doesn't use bonuses.

**Connection with PSRL** If we unfold the recursive formula above we can express the Q-values $\overline{Q}^{n+1,j}$ as a weighted sum

$$ \overline{Q}_h^{n+1,j}(s, a) = W_{n,j}^0 \overline{Q}_h^{1,j}(s, a) + \sum_{k=1}^n W_{n,j}^k [r_h(s, a) + \overline{V}_{h+1}^k (s_{h+1}^k)], $$

where we define $W_{n,j}^0 = \prod_{\ell=0}^{n-1} (1 - w_{\ell,j})$ and $W_{n,j}^k = w_{k-1,j} \prod_{\ell=k}^{n-1} (1 - w_{\ell,j})$.

To compare, we can unfold the corresponding formula for PSRL algorithm using the aggregation properties of the Dirichlet distribution (see e.g. Section 4 of Tiapkin et al. [2022b] or Appendix C)

$$ \overline{Q}_h^{n+1}(s, a) = \widetilde{W}_n^0 \overline{Q}_h^1(s, a) + \sum_{k=1}^n \widetilde{W}_n^k [r_h(s, a) + \overline{V}_{h+1}^{n+1}(s_{h+1}^k)], \quad (1) $$

where weights $(\widetilde{W}_n^0, \dots, \widetilde{W}_n^n)$ follows Dirichlet distribution $\text{Dir}(n_0, 1, \dots, 1)$ and $n_0$ is a weight for the prior distribution. In particular, one can represent these weights as partial products of other weights $w_n \sim \text{Beta}(1, n + n_0)$. If we use (1) to construct a model-free algorithm, this would require recomputing the targets $r_h(s, a) + \overline{V}^{n+1}(s_{h+1}^k)$ in each iteration. To make algorithm more efficient and model-free, we approximate $\overline{V}^{n+1}$ by $\overline{V}^k$, and, as a result, obtain RandQL algorithm with weight distribution $w_{n,j} \sim \text{Beta}(1, n + n_0)$.

Note that in expectation this algorithm is equivalent to OptQL with the uniform step-sizes which are known to be sub-optimal due to a high bias (see discussion in Section 3 of [Jin et al., 2018]). There are two known ways to overcome this sub-optimality for Q-learning: to introduce more aggressive

<footnote>$^3$We index the quantities by $n$ in this section where $n$ is the number of times the state-action pair $(s, a)$ is visited. In particular this is different from the global time $t$ since, in our setting, all the state-action pair are not visited at each episode. See Section 3.2 and Appendix B precise notations.</footnote>
learning rates $w_{n,j} \sim \text{Beta}(H, n + n_0)$ leading to RandQL algorithm, or to use stage-dependent framework by Bai et al. [2019], Zhang et al. [2020] resulting in Staged-RandQL algorithm.

The aforementioned transition from PSRL to RandQL is similar to the transition from UCBVI [Azar et al., 2017] to Q-learning. To make UCBVI model-free, one has to keep old targets in Q-values. This, however, introduces a bias that could be eliminated either by more aggressive step-size [Jin et al., 2018] or by splitting on stages [Bai et al., 2019]. Our algorithms (RandQL and Staged-RandQL) perform the similar tricks for PSRL and thus could be viewed as model-free versions of it. Additionally, RandQL shares some similarities with the OPSRL algorithm [Agrawal and Jia, 2017, Tiapkin et al., 2022a] in the way of introducing optimism (taking maximum over $J$ independent ensembles of Q-values). Let us also mention a close connection to the theory of Dirichlet processes in the proof of optimism for the case of metric spaces (see Remark 1 in Appendix E.4).

**Prior** As remarked above, in expectation, RandQL has a learning rate of the same order as OptQL. In particular, it implies that the first $(1 - 1/H)$ fraction of the target will be forgotten exponentially fast in the estimation of the Q-values, see Jin et al. [2018], Ménard et al. [2021]. Thus we need to re-inject prior targets, as explained in Appendix B, in order to not forget too quickly the prior and thus replicate the same exploration mechanism as in the PSRL algorithm.

## 3.2 Algorithm

In this section, following Bai et al. [2019], Zhang et al. [2020], we present the Staged-RandQL algorithm a scheduled version of RandQL that is simpler to analyse. The main idea is that instead of using a carefully tuned learning rate to keep only the last $1/H$ fraction of the targets we split the learning of the Q-values in stages of exponentially increasing size with growth rate of order $1 + 1/H$. At a given stage, the estimate of the Q-value relies only on the targets within this stage and resets at the beginning of the next stage. Notice that the two procedures are almost equivalent. A detail description of Staged-RandQL is provided in Algorithm 1.

**Counts and stages** Let $n_h^t(s, a) \triangleq \sum_{i=1}^{t-1} 1\{(s_h^i, a_h^i) = (s, a)\}$ be the number of visits of state-action pair $(s, a)$ at step $h$ before episode $t$. We say that a triple $(s, a, h)$ belongs to the $k$-th stage at the beginning of episode $t$ if $n_h^t(s, a) \in [\sum_{i=0}^{k-1} e_i, \sum_{i=0}^k e_i)$. Here $e_k = \lfloor (1 + 1/H)^k \cdot H \rfloor$ is the length of the stage $k \ge 0$ and, by convention, $e_{-1} = 0$. Let $\tilde{n}_h^t(s, a) \triangleq n_h^t(s, a) - \sum_{i=0}^{k-1} e_i$ be the number of visits of state-action pair $(s, a)$ at step $h$ during the current stage $k$.

**Temporary Q-values** At the beginning of a stage, let say time $t$, we initialize *J* temporary Q-values as $\tilde{Q}_h^{t,j}(s, a) = r_h(s, a) + r_0(H - h - 1)$ for $j \in [J]$ and $r_0$ some pseudo-reward. Then as long as $(s_h^t, a_h^t, h)$ remains within a stage we update recursively the *temporary* Q-values

$$ \tilde{Q}_h^{t+1,j}(s, a) = \begin{cases} (1 - w_{j,\tilde{n}}) \tilde{Q}_h^{t,j}(s, a) + w_{j,\tilde{n}} [r_h(s, a) + \bar{V}_{h+1}^t(s_{h+1}^t)], & (s, a) = (s_h^t, a_h^t) \\ \tilde{Q}_h^{t,j}(s, a) & \text{otherwise,} \end{cases} $$

where $\tilde{n} = \tilde{n}_h^t(s, a)$ is the number of visits, $w_{j,\tilde{n}}$ is a sequence of i.i.d. random variables $w_{j,\tilde{n}} \sim \text{Beta}(1/\kappa, (\tilde{n} + n_0)/\kappa)$ with $\kappa > 0$ being some posterior inflation coefficient and $n_0$ a number of pseudo-transitions.

**Policy Q-values** Next we define the policy Q-values that is updated at the end of a stage. Let say for state-action pair $(s, a)$ at step $h$ an stage ends at time $t$. This policy Q-values is then given by the maximum of temporary Q-values $\bar{Q}_h^{t+1} = \max_{j \in [J]} \tilde{Q}_h^{t+1,j}(s, a)$. Then the policy Q-values is constant within a stage. The value used to defined the targets is $\bar{V}_h^{t+1}(s) = \max_{a \in A} \bar{Q}_h^{t+1}(s, a)$. The policy used to interact with the environment is greedy with respect to the policy Q-values $\pi_h^{t+1}(s) \in \arg \max_{a \in A} \bar{Q}_h^{t+1}(s, a)$ (we break ties arbitrarily).

## 3.3 Regret bound

We fix $\delta \in (0, 1)$ and the number of posterior samples $J \triangleq [c_J \cdot \log(2SAHT/\delta)]$, where $c_J = 1/\log(2/(1 + \Phi(1)))$ and $\Phi(\cdot)$ is the cumulative distribution function (CDF) of a normal distribution. Note that $J$ has a logarithmic dependence on $S, A, H, T$, and $1/\delta$.

We now state the regret bound of Staged-RandQL with a full proof in Appendix D.
**Algorithm 1 Tabular Staged-RandQL**

1: **Input:** inflation coefficient $\kappa$, $J$ ensemble size, number of prior transitions $n_0$, prior reward $r_0$.

2: **Initialize:** $\bar{V}_h(s) = \bar{Q}_h(s, a) = \tilde{Q}_h^j(s, a) = r(s, a) + r_0(H - h - 1)$, initialize counters $\tilde{n}_h(s, a) = 0$ for $j, h, s, a \in [J] \times [H] \times S \times A$ and stage $q_h(s, a) = 0$.

3: **for** $t \in [T]$ **do**

4: **for** $h \in [H]$ **do**

5: Play $a_h \in \arg \max_a \bar{Q}_h(s_h, a)$.

6: Observe reward and next state $s_{h+1} \sim p_h(s_h, a_h)$.

7: Sample learning rates $w_j \sim \text{Beta}(1/\kappa, (\tilde{n} + n_0)/\kappa)$ for $\tilde{n} = \tilde{n}_h(s_h, a_h)$.

8: Update temporary $Q$-values for all $j \in [J]$

$$ \tilde{Q}_h^j(s_h, a_h) := (1 - w_j) \tilde{Q}_h^j(s_h, a_h) + w_j (r_h(s_h, a_h) + \bar{V}_{h+1}(s_{h+1})) $$

9: Update counter $\tilde{n}_h(s_h, a_h) := \tilde{n}_h(s_h, a_h) + 1$

10: **if** $\tilde{n}_h(s_h, a_h) = \lfloor (1 + 1/H)^q H \rfloor$ for $q = q_h(s_h, a_h)$ being the current stage **then**

11: Update policy $Q$-values $\bar{Q}_h(s_h, a_h) := \max_{j \in [J]} \tilde{Q}_h^j(s_h, a_h)$.

12: Update value function $\bar{V}_h(s_h) := \max_{a \in A} \bar{Q}_h(s_h, a)$

13: Reset temporary $Q$-values $\tilde{Q}_h^j(s_h, a_h) := r_h(s_h, a_h) + r_0(H - h - 1)$.

14: Reset counter $\tilde{n}_h(s_h, a_h) := 0$ and change stage $q_h(s_h, a_h) := q_h(s_h, a_h) + 1$.

15: **end if**

16: **end for**

17: **end for**

**Theorem 1.** Consider a parameter $\delta \in (0, 1)$. Let $\kappa \triangleq 2(\log(8SAH/\delta) + 3 \log(e\pi(2T+1)))$, $n_0 \triangleq [\kappa(c_0 + \log_{17/16}(T))]$, $r_0 \triangleq 2$, where $c_0$ is an absolute constant defined in (5); see Appendix D.3. Then for Staged-RandQL, with probability at least $1 - \delta$,

$$ \Re^T = \tilde{O}(\sqrt{H^5 SAT} + H^3 SA). $$

**Discussion** The regret bound of Theorem 1 coincides (up to a logarithmic factor) with the bound of the OptQL algorithm with Hoeffding-type bonuses from Jin et al. [2018]. Up to a $H$ factor, our regret matches the information-theoretic lower bound $\Omega(\sqrt{H^3 SAT})$ [Jin et al., 2018, Domingues et al., 2021b]. This bound could be achieved (up to logarithmic terms) in model-free algorithms by using Bernstein-type bonuses and variance reduction [Zhang et al., 2020]. We keep these refinements for future research as the main focus of our paper is on the novel randomization technique and its use to construct computationally tractable model-free algorithms.

**Computational complexity** Staged-RandQL is a model-free algorithm, and thus gets the $\tilde{O}(HSA)$ space complexity as OptQL, recall that we set $J = \tilde{O}(1)$. The per-episode time-complexity is also similar and of order $\tilde{O}(H)$.

# 4 Randomized Q-learning for Metric Spaces

In this section we present a way to extend RandQL to general state-action spaces. We start from the simplest approach with predefined $\varepsilon$-net type discretization of the state-action space $S \times A$ (see Song and Sun 2019), and then discuss an adaptive version of the algorithm, similar to one presented by Sinclair et al. [2019].

## 4.1 Assumptions

To pose the first assumption, we start from a general definition of covering numbers.

**Definition 1 (Covering number and covering dimension).** Let $(M, \rho)$ be a metric space. A set $M$ of open balls of radius $\varepsilon$ is called an $\varepsilon$-cover of $M$ if $M \subseteq \bigcup_{B \in \mathcal{M}} B$. The cardinality of the minimal $\varepsilon$-cover is called covering number $N_\varepsilon$ of $(M, \rho)$. We denote the corresponding minimal $\varepsilon$-covering by $\mathcal{N}_\varepsilon$. A metric space $(M, \rho)$ has a covering dimension $d_c$ if $\forall \varepsilon > 0 : N_\varepsilon \le C_N \varepsilon^{-d_c}$, where $C_N$ is a constant.
The last definition extends the definition of dimension beyond vector spaces. For example, is case of $M = [0, 1]^d$ the covering dimension of $M$ is equal to $d$. For more details and examples see e.g. Vershynin [2018, Section 4.2].

Next we are ready to introduce the first assumption.

**Assumption 1 (Metric Assumption).** Spaces $S$ and $A$ are separable compact metric spaces with the corresponding metrics $\rho_S$ and $\rho_A$. The joint space $S \times A$ endowed with a product metric $\rho$ that satisfies $\rho((s, a), (s', a')) \le \rho_S(s, s') + \rho_A(a, a')$. Moreover, the diameter of $S \times A$ is bounded by $d_{\max}$, and $S \times A$ has covering dimension $d_c$ with a constant $C_N$.

This assumption is, for example, satisfied for the finite state and action spaces endowed with discrete metrics $\rho_S(s, s') = 1\{s \ne s'\}$, $\rho_A(a, a') = 1\{a \ne a'\}$ with $d_c = 0$, $C_N = SA$ and $S$ and $A$ being the cardinalities of the state and action spaces respectively. The above assumption also holds in the case $S \subseteq [0, 1]^{ds}$ and $A \subseteq [0, 1]^{dA}$ with $d_c = d_S + d_A$.

The next two assumptions describe the regularity conditions of transition kernel and rewards.

**Assumption 2 (Reparametrization Assumption).** The Markov transition kernel could be represented as an iterated random function. In other words, there exists a measurable space $(\Xi, \mathcal{F}_{\Xi})$ and a measurable function $F_h: (S \times A) \times \Xi \to S$, such that $s_{h+1} \sim p_h(s_h, a_h) \iff s_{h+1} = F_h(s_h, a_h, \xi_h)$ for a sequence of independent random variables $\{\xi_h\}_{h \in [H]}$.

This assumption is naturally satisfied for a large family of probabilistic model, see Kingma and Welling [2014]. Moreover, it has been utilized by the RL community both in theory [Ye and Zhou, 2015] and practice [Heess et al., 2015, Liu et al., 2018]. Essentially, this assumption holds for Markov transition kernels over a separable metric space, see Theorem 1.3.6 by Douc et al. [2018]. However, the function $F_h$ could be ill-behaved. To avoid this behaviour, we need the following assumption.

**Assumption 3 (Lipschitz Assumption).** The function $F_h(\cdot, \xi_h)$ is $L_F$-Lipschitz in the first argument for almost every value of $\xi_h$. Additionally, the reward function $r_h: S \times A \to [0, 1]$ is $L_r$-Lipschitz.

This assumption is commonly used in studies of the Markov processes corresponding to iterated random functions, see Diaconis and Freedman [1999], Ghosh and Marecek [2022]. Moreover, this assumption holds for many cases of interest. As main example, it trivially holds in tabular and Lipschitz continuous deterministic MDPs [Ni et al., 2019]. Notably, this observation demonstrates that Assumption 3 does not necessitate Lipschitz continuity of the transition kernels in total variation distance, since deterministic Lipschitz MDPs are not continuous in that sense. Additionally, incorporation of an additive noise to deterministic Lipschitz MDPs will lead to Assumption 3 with $L_F = 1$.

Furthermore, it is possible to show that Assumption 3 implies other assumptions stated in the literature. For example, it implies that the transition kernel is Lipschitz continuous in 1-Wasserstein metric, and that $Q^*$ and $V^*$ are both Lipschitz continuous.

**Lemma 1.** Let Assumption 1,2,3 hold. Then the transition kernels $p_h(s, a)$ are $L_F$-Lipschitz continuous in 1-Wasserstein distance

$$W_1(p_h(s, a), p_h(s', a')) \le L_F \cdot \rho((s, a), (s', a')),$$

where 1-Wasserstein distance between two probability measures on the metric space $(M, \rho)$ is defined as $W_1(\nu, \eta) = \sup_f \int_M f d\nu - \int_M f d\eta$.

**Lemma 2.** Let Assumption 1,2,3 hold. Then $Q_h^*$ and $V_h^*$ are Lipschitz continuous with Lipschitz constant $L_{V,h} \le \sum_{h'=h}^H L_F^{h'-h} L_r$.

The proof of these lemmas is postponed to Appendix E. For a more detailed exposition on 1-Wasserstein distance we refer to the book by Peyré and Cuturi [2019]. The first assumption was studied by Domingues et al. [2021c], Sinclair et al. [2023] in the setting of model-based algorithms in metric spaces. We are not aware of any natural examples of MDPs with a compact state-action space where the transition kernels are Lipschitz in $W_1$ but fail to satisfy Assumption 3.

## 4.2 Algorithms

In this section, following Song and Sun [2019], we present Net-Staged-RandQL algorithm that combines a simple non-adaptive discretization and an idea of stages by Bai et al. [2019], Zhang et al. [2020].
We assume that we have an access to all Lipschitz constants $L_r, L_F, L_V \triangleq L_{V,1}$. Additionally, we have access to the oracle that computes $\varepsilon$-cover $\mathcal{N}_\varepsilon$ of the space $S \times A$ for any predefined $\varepsilon > 0^4$.

**Counts and stages** Let $n_h^t(B) \triangleq \sum_{i=1}^{t-1} 1\{(s_h^i, a_h^i) \in B\}$ be the number of visits of the ball $B \in \mathcal{N}_\varepsilon$ at step $h$ before episode $t$. Let $e_k = \lfloor(1+1/H)^k \cdot H\rfloor$ be length of the stage $k \ge 0$ and, by convention, $e_{-1} = 0$. We say that $(B, h)$ belongs to the $k$-th stage at the beginning of episode $t$ if $n_h^t(B) \in [\sum_{i=0}^{k-1} e_i, \sum_{i=0}^k e_i]$. Let $\tilde{n}_h^t(B) \triangleq n_h^t(s, a) - \sum_{i=0}^{k-1} e_i$ be the number of visits of the ball $B$ at step $h$ during the current stage $k$.

**Temporary Q-values** At the beginning of a stage, let say time $t$, we initialize $J$ temporary Q-values as $\tilde{Q}_h^{t,j}(B) = r_0H$ for $j \in [J]$ and $r_0$ some pseudo-reward. Then within a stage $k$ we update recursively the temporary Q-values

$$ \tilde{Q}_h^{t+1,j}(B) = \begin{cases} (1 - w_{j,\tilde{n}})\tilde{Q}_h^{t,j}(B) + w_{j,\tilde{n}}[r_h(s_h^t, a_h^t) + \bar{V}_{h+1}^t(s_{h+1}^t)], & (s, a) = (s_h^t, a_h^t) \\ \tilde{Q}_h^{1,j}(B) & \text{otherwise,} \end{cases} $$

where $\tilde{n} = \tilde{n}_h^t(B)$ is the number of visits, $w_{j,\tilde{n}}$ is a sequence of i.i.d random variables $w_{j,\tilde{n}} \sim \text{Beta}(1/\kappa, (\tilde{n} + n_0(k))/\kappa)$ with $\kappa > 0$ some posterior inflation coefficient and $n_0(k)$ a number of pseudo-transitions. The important difference between tabular and metric settings is the dependence on the pseudo-count $n_0(k)$ on $k$ in the latter case, since here the prior is used to eliminate the approximation error.

**Policy Q-values** Next, we define the policy Q-values that are updated at the end of a stage. Let us fix a ball $B$ at step $h$ and suppose that the currents stage ends at time $t$. Then the policy Q-values are given by the maximum of the temporary Q-values $\bar{Q}_h^{t+1}(B) = \max_{j \in [J]} \tilde{Q}_h^{t+1,j}(B)$. The policy Q-values are constant within a stage. The value used to define the targets is computed on-flight using the formula $\bar{V}_h^t(s) = \max_{a \in A} \tilde{Q}_h^t(\psi_\varepsilon(s, a))$, where $\psi_\varepsilon: S \times A \to \mathcal{N}_\varepsilon$ is a quantization map, that assigns each state-action pair $(s, a)$ to a ball $B \ni (s, a)$. The policy used to interact with the environment is greedy with respect to the policy Q-values and also computed on-flight $\pi_h^t(s) \in \arg\max_{a \in A} \tilde{Q}_h^t(\psi_\varepsilon(s, a))$ (we break ties arbitrarily).

A detail description of Net-Staged-RandQL is provided in Algorithm 4 in Appendix E.2.

## 4.3 Regret Bound

We fix $\delta \in (0, 1)$, the discretization level $\varepsilon > 0$ and the number of posterior samples

$$ J \triangleq \lceil \tilde{c}_J \cdot (\log(2C_NHT/\delta) + d_c \log(1/\varepsilon)) \rceil, $$

where $\tilde{c}_J = 1/\log(4/(3+\Phi(1)))$ and $\Phi(\cdot)$ is the cumulative distribution function (CDF) of a normal distribution. Note that $J$ has a logarithmic dependence on $H, T, 1/\varepsilon$ and $1/\delta$. For the regret-optimal discretization level $\varepsilon = T^{-1/(d_c+2)}$, the number $J$ is almost independent of $d_c$. Let us note that the role of prior in metric spaces is much higher than in the tabular setting. Another important difference is dependence of the prior count on the stage index. In particular, we have

$$ n_0(k) = \left\lceil \tilde{n}_0 + \kappa + \frac{\varepsilon L}{H-1} \cdot (e_k + \tilde{n}_0 + \kappa) \right\rceil, \quad \tilde{n}_0 = (c_0 + 1 + \log_{17/16}(T)) \cdot \kappa $$

where $c_0$ is an absolute constant defined in (5) (see Appendix D.3), $\kappa$ is the posterior inflation coefficient and $L = L_r+(1+L_F)L_V$ is a constant. We now state the regret bound of Net-Staged-RandQL with a full proof being postponed to Appendix E.

**Theorem 2.** Suppose that $N_\varepsilon \le C_N \varepsilon^{-d_c}$ for all $\varepsilon > 0$ and some constant $C_N > 0$. Consider a parameter $\delta \in (0, 1)$ and take an optimal level of discretization $\varepsilon = T^{-1/(d_c+2)}$. Let $\kappa \triangleq 2(\log(8HC_N/\delta)+d_c \log(1/\varepsilon)+3\log(e\pi(2T+1)))$, $r_0 \triangleq 2$. Then it holds for Net-Staged-RandQL, with probability at least $1-\delta$,

$$ \mathfrak{R}^T = \tilde{\mathcal{O}}\left(H^{5/2} C_N^{1/2} T^{\frac{d_c+1}{d_c+2}} + H^3 C_N T^{\frac{d_c}{d_c+2}} + LT^{\frac{d_c+1}{d_c+2}}\right). $$

We can restore the regret bound in the tabular setting by letting $d_c = 0$ and $C_N = SA$, where $S$ is the cardinality of the state-space, and $A$ is the cardinality of the action-space.

<footnote n="4">⁴Remark that the simple greedy algorithm can generate $\varepsilon$-cover of size $N_\varepsilon/2$, that will not affect the asymptotic behavior of our regret bounds, see Song and Sun [2019].</footnote>
**Discussion** From the point of view of instance-independent bounds, our algorithm achieves the same result as Net-QL [Song and Sun, 2019] and Adaptive-QL [Sinclair et al., 2019], that matches the lower bound $\Omega(HT^{\frac{d_c+1}{d_c+2}})$ by Sinclair et al. [2023] in dependence on budget T and covering dimension $d_c$. Notably, as discussed by Sinclair et al. [2023], the model-based algorithm such as Kernel-UCBVI [Domingues et al., 2021c] does not achieves optimal dependence in T due to hardness of the transition estimation problem.

**Computational complexity** For a fixed level of discretization $\epsilon$, our algorithm has a space complexity of order $\tilde{O}(HN_\epsilon)$. Assuming that the computation of a quantization map $\psi_\epsilon$ has $\tilde{O}(1)$ time complexity, we achieve a per-episode time complexity of $\tilde{O}(HA)$ for a finite action space and $O(HN_\epsilon)$ for an infinite action space in the worst case due to computation of $\arg\max_{a\in A}\tilde{Q}_h(\psi_\epsilon(s, a))$. However, this can be improved to $\tilde{O}(H)$ if we consider adaptive discretization [Sinclair et al., 2019].

**Adaptive discretization** Additionally, we propose a way to combine RandQL with adaptive discretization by Cao and Krishnamurthy [2020], Sinclair et al. [2023]. This combination results in two algorithms: Adaptive-RandQL and Adaptive-Staged-RandQL. The second one could achieve the instance-dependent regret bound that scales with a zooming dimension, the instance-dependent measure of dimension. We will follow Sinclair et al. [2023] in the exposition of the required notation.

**Definition 2.** For any $(s, a) \in S \times A$, the stage-dependent sub-optimality gap is defined as $\text{gap}_h(s, a) = V_h^*(s) - Q_h^*(s, a)$.

This quantity is widely used in the theoretical instance-dependent analysis of reinforcement learning and contextual bandit algorithms.

**Definition 3.** The near-optimal set of $S \times A$ for a given value $\epsilon$ defined as $Z_h^\epsilon = \{(s, a) \in S \times A | \text{gap}_h(s, a) \le (H+1)\epsilon\}$.

The main insight of this definition is that essentially we are interested in a detailed discretization of the near-optimal set $Z_h^\epsilon$ for small $\epsilon$, whereas all other state-action pairs could be discretized in a more rough manner. Interestingly enough, $Z_h^\epsilon$ could be a lower dimensional manifold, leading to the following definition.

**Definition 4.** The step-h zooming dimension $d_{z,h}$ with a constant $C_{N,h}$ and a scaling factor $\rho > 0$ is given by

$$d_{z,h} = \inf\{d > 0 : \forall \epsilon > 0 N_\epsilon(Z_h^{\rho \cdot \epsilon}) \le C_{N,h} \epsilon^{-d}\}.$$

Under some additional structural assumptions on $Q_h^*$, it is possible to show that the zooming dimension could be significantly smaller than the covering dimension, see, e.g., Lemma 2.8 in Sinclair et al. [2023]. However, at the same time, it has been shown that $d_{z,h} \ge d_S - 1$, where $d_S$ is a covering dimension of the state space. Thus, the zooming dimension allows adaptation to a rich action space but not a rich state space.

Given this definition, it is possible to define an adaptive algorithm Adaptive-Staged-RandQL that attains the following regret guarantees

**Theorem 3.** Consider a parameter $\delta \in (0, 1)$. For a value $\kappa$ that depends on T, $d_c$ ad $\delta$, for Adaptive-Staged-RandQL the following holds with probability at least $1 - \delta$,

$$\mathfrak{R}^T = \tilde{\mathcal{O}}\left(H^3 + H^{3/2} \sum_{h=1}^{H} T^{\frac{d_{z,h}+1}{d_{z,h}+2}}\right),$$

where $d_{z,h}$ is the step-h zooming dimension and we ignore all multiplicative factors in the covering dimension $d_c$, $\log(C_N)$, and Lipschitz constants.

We refer to Appendix F to a formal statement and a proof.

# 5 Experiments

In this section we present the experiments we conducted for tabular environments using rlberry library [Domingues et al., 2021a]. We also provide experiments in non-tabular environment in Appendix I.
**Environment** We use a grid-world environment with 100 states $(i, j) \in [10] \times [10]$ and 4 actions (left, right, up and down). The horizon is set to $H = 50$. When taking an action, the agent moves in the corresponding direction with probability $1 - \varepsilon$, and moves to a neighbor state at random with probability $\varepsilon = 0.2$. The agent starts at position $(1, 1)$. The reward equals to 1 at the state (10, 10) and is zero elsewhere.

**Variations of randomized Q-learning** For the tabular experiment we use the RandQL algorithm, described in Appendix B as it is the version of randomized Q-learning that is the closest to the baseline OptQL. Note that, we compare the different versions of randomized Q-learning in Appendix B.

**Baselines** We compare RandQL algorithm to the following baselines: (i) OptQL [Jin et al., 2018] (ii) UCBVI [Azar et al., 2017] (iii) Greedy-UCBVI, a version of UCBVI using real-time dynamic programming [Efroni et al., 2019] (iv) PSRL [Osband et al., 2013] and (v) RLSVI [Russo, 2019]. For the hyper-parameters used for these baselines refer to Appendix I.

<figure><img src="image_1.png" /><figcaption>Figure 1: Regret curves of RandQL and baselines in a grid-world environment for $H = 50$ and transition noise $\varepsilon = 0.2$. The average is over 4 seeds.</figcaption></figure>

**Results** Figure 1 shows the result of the experiments. Overall, we see that RandQL outperforms OptQL algorithm on tabular environment, but still degrades in comparison to model-based approaches, that is usual for model-free algorithms in tabular environments. Indeed, using a model and backward induction allows new information to be more quickly propagated. But as counterpart, RandQL has a better time-complexity and space-complexity than model-based algorithm, see Table 2 in Appendix I.

# 6 Conclusion

This paper introduced the RandQL algorithm, a new model-free algorithm that achieves exploration without bonuses. It utilizes a novel idea of learning rate randomization, resulting in provable sample efficiency with regret of order $\tilde{O}(\sqrt{H^5 SAT})$ in the tabular case. We also extend RandQL to the case of metric state-action space by using proper discretization techniques. The proposed algorithms inherit the good empirical performance of model-based Bayesian algorithm such that PSRL while keeping the small space and time complexity of model-free algorithm. Our result rises following interesting open questions for a further research.

**Optimal rate for RandQL** We conjecture that RandQL could get optimal regret in the tabular setting if coupled with variance reductions techniques as used by Zhang et al. [2020]. However, obtaining such improvements is not straightforward due to the intricate statistical dependencies involved in the analysis of RandQL.

**Beyond one-step learning** We observe a large gap in the experiments between Q-learning type algorithm that do one-step planning and e.g. UCBVI algorithm that does full planning or Greedy-UCBVI that does one-step planning with full back-up (expectation under transition of the model) for all actions. Therefore, it would interesting to study also algorithms that range between these two extremes [Efroni et al., 2018, 2019].

# Acknowledgments

The work of D. Tiapkin, A. Naumov, and D. Belomestny were supported by the grant for research centers in the field of AI provided by the Analytical Center for the Government of the Russian Federation (ACRF) in accordance with the agreement on the provision of subsidies (identifier of the agreement 000000D730321P5Q0002) and the agreement with HSE University No. 70-2021-00139. E. Moulines received support from the grant ANR-19-CHIA-002 SCAI and parts of his work has been done under the auspices of Lagrange Center for maths and computing. P. Ménard acknowledges the Chaire SeqALO (ANR-20-CHIA-0020-01). This research was supported in part through computational resources of HPC facilities at HSE University.
References

Shipra Agrawal and Navin Goyal. Further optimal regret bounds for thompson sampling. In Carlos M. Carvalho and Pradeep Ravikumar, editors, *Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics*, volume 31 of *Proceedings of Machine Learning Research*, pages 99–107, Scottsdale, Arizona, USA, 29 Apr–01 May 2013. PMLR. URL https://proceedings.mlr.press/v31/agrawal13a.html.

Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, *Advances in Neural Information Processing Systems*, volume 30. Curran Associates, Inc., 2017. URL https://proceedings.neurips.cc/paper/2017/file/3621f1454cacf995530ea53652ddf8fb-Paper.pdf.

Duncan Alfers and Hermann Dinges. A normal approximation for beta and gamma tail probabilities. *Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete*, 65:399–420, 1984. URL https://link.springer.com/content/pdf/10.1007/BF00533744.pdf.

Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In *International Conference on Machine Learning*, 2017. URL https://arxiv.org/pdf/1703.05449.pdf.

Kamyar Azizzadenesheli, Emma Brunskill, and Animashree Anandkumar. Efficient exploration through bayesian deep q-networks. In *2018 Information Theory and Applications Workshop, ITA 2018*, San Diego, CA, USA, February 11-16, 2018, pages 1–9. IEEE, 2018. doi: 10.1109/ITA.2018.8503252. URL https://doi.org/10.1109/ITA.2018.8503252.

Yu Bai, Tengyang Xie, Nan Jiang, and Yu-Xiang Wang. Provably efficient q-learning with low switching cost, 2019. URL https://arxiv.org/abs/1905.12849.

Tongyi Cao and Akshay Krishnamurthy. Provably adaptive reinforcement learning in metric spaces. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, *Advances in Neural Information Processing Systems*, volume 33, pages 9736–9744. Curran Associates, Inc., 2020. URL https://proceedings.neurips.cc/paper_files/paper/2020/file/6ef1173b096aa200158bfbc8af3ae8e3-Paper.pdf.

Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning. In *Neural Information Processing Systems*, 2017. URL https://arxiv.org/pdf/1703.07710.pdf.

Christoph Dann, Mehryar Mohri, Tong Zhang, and Julian Zimmert. A provably efficient model-free posterior sampling method for episodic reinforcement learning. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, *Advances in Neural Information Processing Systems*, volume 34, pages 12040–12051. Curran Associates, Inc., 2021. URL https://proceedings.neurips.cc/paper_files/paper/2021/file/649d45bf179296e31731adfd4df25588-Paper.pdf.

Marc Peter Deisenroth and Carl Edward Rasmussen. Pilco: A model-based and data-efficient approach to policy search. In *Proceedings of the 28th International Conference on International Conference on Machine Learning*, ICML’11, page 465–472, Madison, WI, USA, 2011. Omnipress. ISBN 9781450306195.

Persi Diaconis and David Freedman. Iterated random functions. *SIAM Review*, 41(1):45–76, 1999. doi: 10.1137/S0036144598338446. URL https://doi.org/10.1137/S0036144598338446.

Omar Darwiche Domingues, Yannis Flet-Berliac, Edouard Leurent, Pierre Ménard, Xuedong Shang, and Michal Valko. rlberry - A Reinforcement Learning Library for Research and Education, 10 2021a. URL https://github.com/rlberry-py/rlberry.

Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited. In Vitaly Feldman, Katrina Ligett, and Sivan Sabato, editors, *Proceedings of the 32nd International Conference on Algorithmic Learning Theory*, volume 132 of *Proceedings of Machine Learning Research*, pages 578–598. PMLR, 16–19 Mar 2021b. URL https://proceedings.mlr.press/v132/domingues21a.html.
Omar Darwiche Domingues, Pierre Menard, Matteo Pirotta, Emilie Kaufmann, and Michal Valko. Kernel-based reinforcement learning: A finite-time analysis. In *Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning*, volume 139 of *Proceedings of Machine Learning Research*, pages 2783–2792. PMLR, 18–24 Jul 2021c. URL https://proceedings.mlr.press/v139/domingues21a.html.

Randal Douc, Eric Moulines, Pierre Priouret, and Philippe Soulier. *Markov chains*. Springer, 2018.

Yonathan Efroni, Gal Dalal, Bruno Scherrer, and Shie Mannor. Multiple-step greedy policies in approximate and online reinforcement learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, *Advances in Neural Information Processing Systems*, volume 31. Curran Associates, Inc., 2018. URL https://proceedings.neurips.cc/paper_files/paper/2018/file/3f998e713a6e02287c374fd26835d87e-Paper.pdf.

Yonathan Efroni, Nadav Merlis, Mohammad Ghavamzadeh, and Shie Mannor. Tight regret bounds for model-based reinforcement learning with greedy policies. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, *Advances in Neural Information Processing Systems*, volume 32. Curran Associates, Inc., 2019. URL https://proceedings.neurips.cc/paper_files/paper/2019/file/25caef3a545a1fff2ff4055484f0e758-Paper.pdf.

Thomas S Ferguson. A bayesian analysis of some nonparametric problems. *The annals of statistics*, pages 209–230, 1973.

Claude-Nicolas Fiechter. Efficient reinforcement learning. In *Conference on Learning Theory*, 1994. URL http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=7F5F8FCD1AA7ED07356410DDD5B384FE?doi=10.1.1.49.8652&rep=rep1&type=pdf.

Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Ian Osband, Alexander Graves, Vlad Mnih, Remi Munos, Demis Hassabis, Olivier Pietquin, Charles Blundell, and Shane Legg. Noisy networks for exploration. In *Proceedings of the International Conference on Representation Learning (ICLR 2018)*, Vancouver (Canada), 2018.

Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient bias-span-constrained exploration-exploitation in reinforcement learning. In *International Conference on Machine Learning*, pages 1578–1586. PMLR, 2018.

Aurélien Garivier, Hédi Hadiji, Pierre Menard, and Gilles Stoltz. Kl-ucb-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpoints. *arXiv preprint arXiv:1805.05071*, 2018.

Subhashis Ghosal and Aad Van der Vaart. *Fundamentals of nonparametric Bayesian inference*, volume 44. Cambridge University Press, 2017.

Ramen Ghosh and Jakub Marecek. Iterated function systems: A comprehensive survey, 2022.

Senlin Guo, Feng Qi, and Hari Srivastava. Necessary and sufficient conditions for two classes of functions to be logarithmically completely monotonic. *Integral Transforms and Special Functions*, 18:819–826, 11 2007. doi: 10.1080/10652460701528933.

Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In *International conference on machine learning*, pages 1861–1870. PMLR, 2018.

Nicolas Heess, Gregory Wayne, David Silver, Timothy Lillicrap, Tom Erez, and Yuval Tassa. Learning continuous control policies by stochastic value gradients. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, *Advances in Neural Information Processing Systems*, volume 28. Curran Associates, Inc., 2015. URL https://proceedings.neurips.cc/paper_files/paper/2015/file/148510031349642de5ca0c544f31b2ef-Paper.pdf.

Matteo Hessel, Ivo Danihelka, Fabio Viola, Arthur Guez, Simon Schmitt, Laurent Sifre, Theophane Weber, David Silver, and Hado van Hasselt. Muesli: Combining improvements in policy optimization. In *Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning*, ICML 2021, 18–24 July 2021, Virtual Event, volume 139 of *Proceedings of Machine Learning Research*, pages 4214–4226. PMLR, 2021. URL http://proceedings.mlr.press/v139/hessel21a.html.
Junya Honda and Akimichi Takemura. An asymptotically optimal bandit algorithm for bounded support models. In Adam Tauman Kalai and Mehryar Mohri, editors, COLT, pages 67–79. Omnipress, 2010. ISBN 978-0-9822529-2-5. URL http://dblp.uni-trier.de/db/conf/colt/colt2010.html#HondaT10.

Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 99:1563–1600, 2010. URL http://www.jmlr.org/papers/volume11/jaksch10a/jaksch10a.pdf.

Chi Jin, Zeyuan Allen-Zhu, Sébastien Bubeck, and Michael I. Jordan. Is Q-learning provably efficient? In Neural Information Processing Systems, 2018. URL https://arxiv.org/pdf/1807.03765.pdf.

Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In Yoshua Bengio and Yann LeCun, editors, 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014. URL http://arxiv.org/abs/1312.6114.

Ziniu Li, Yingru Li, Yushun Zhang, Tong Zhang, and Zhi-Quan Luo. Hyperdqn: A randomized exploration method for deep reinforcement learning. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL https://openreview.net/forum?id=XOnrKAXu7g-.

Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In Yoshua Bengio and Yann LeCun, editors, 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL http://arxiv.org/abs/1509.02971.

Hao Liu, Yihao Feng, Yi Mao, Dengyong Zhou, Jian Peng, and Qiang Liu. Action-dependent control variates for policy optimization via stein identity. In ICLR 2018 Conference, February 2018. URL https://www.microsoft.com/en-us/research/publication/action-dependent-control-variates-policy-optimization-via-stein-identity/.

Pierre Ménard, Omar Darwiche Domingues, Xuedong Shang, and Michal Valko. Ucb momentum q-learning: Correcting the bias without forgetting. In International Conference on Machine Learning, pages 7609–7618. PMLR, 2021.

Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. In NIPS Deep Learning Workshop. 2013.

Chengzhuo Ni, Lin F Yang, and Mengdi Wang. Learning to control in metric space with optimal regret. In 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 726–733. IEEE, 2019.

Ian Osband and Benjamin Van Roy. Bootstrapped thompson sampling and deep exploration. CoRR, abs/1507.00300, 2015. URL http://arxiv.org/abs/1507.00300.

Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 2701–2710. PMLR, 06–11 Aug 2017. URL https://proceedings.mlr.press/v70/osband17a.html.

Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.

Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016. URL https://proceedings.neurips.cc/paper/2016/file/8d8818c8e140c64c743113f563cf750f-Paper.pdf.
Gabriel Peyré and Marco Cuturi. Computational optimal transport: With applications to data science. *Foundations and Trends® in Machine Learning*, 11(5-6):355-607, 2019. ISSN 1935-8237. doi: 10.1561/2200000073. URL http://dx.doi.org/10.1561/2200000073.

Iosif Pinelis. Optimum Bounds for the Distributions of Martingales in Banach Spaces. *The Annals of Probability*, 22(4):1679–1706, 1994. doi: 10.1214/aop/1176988477. URL https://doi.org/10.1214/aop/1176988477.

Daniel Russo. Worst-case regret bounds for exploration via randomized value functions. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Gar- nett, editors, *Advances in Neural Information Processing Systems*, volume 32. Curran Associates, Inc., 2019. URL https://proceedings.neurips.cc/paper/2019/file/451ae86722d26a608c2e174b2b2773f1-Paper.pdf.

Remo Sasso, Michelangelo Conserva, and Paulo E. Rauber. Posterior sampling for deep reinforcement learning. *CoRR*, abs/2305.00477, 2023. doi: 10.48550/arXiv.2305.00477. URL https://doi.org/10.48550/arXiv.2305.00477.

Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with a learned model. *Nature*, 588(7839):604–609, 2020.

John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In *International conference on machine learning*, pages 1889–1897. PMLR, 2015.

John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. *CoRR*, abs/1707.06347, 2017. URL http://dblp.uni-trier.de/db/journals/corr/corr1707.html#SchulmanWDRK17.

Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Gar- nett, editors, *Advances in Neural Information Processing Systems*, volume 32. Curran Asso- ciates, Inc., 2019. URL https://proceedings.neurips.cc/paper_files/paper/2019/file/10a5ab2db37feedfdeaab192ead4ac0e-Paper.pdf.

Sean R. Sinclair, Siddhartha Banerjee, and Christina Lee Yu. Adaptive discretization for episodic reinforcement learning in metric spaces. *Proceedings of the ACM on Measurement and Analysis of Computing Systems*, 3(3):1–44, dec 2019. doi: 10.1145/3366703. URL https://doi.org/10.1145/2F3366703.

Sean R. Sinclair, Siddhartha Banerjee, and Christina Lee Yu. Adaptive discretization in online reinforcement learning. *Operations Research*, 71(5):1636–1652, 2023. doi: 10.1287/opre.2022.2396. URL https://doi.org/10.1287/opre.2022.2396.

Maciej Skorski. Bernstein-type bounds for beta distribution. *Modern Stochastics: Theory and Applications*, 10(2):211–228, 2023. ISSN 2351-6046. doi: 10.15559/23-VMSTA223.

Zhao Song and Wen Sun. Efficient model-free reinforcement learning in metric spaces, 2019.

Malcolm J. A. Strens. A bayesian framework for reinforcement learning. In *Proceedings of the Seventeenth International Conference on Machine Learning*, ICML '00, page 943–950, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc. ISBN 1558607072.

R. Sutton and A. Barto. *Reinforcement Learning: an Introduction*. MIT press, 1998.

Daniil Tiapkin, Denis Belomestny, Daniele Calandriello, Eric Moulines, Remi Munos, Alexey Naumov, Mark Rowland, Michal Valko, and Pierre Ménard. Optimistic posterior sampling for reinforcement learning with few samples and tight guarantees. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, *Advances in Neural Information Processing Systems*, volume 35, pages 10737–10751. Curran Associates, Inc., 2022a. URL https://proceedings.neurips.cc/paper_files/paper/2022/file/45e15bae91a6f213d45e203b8a29be48-Paper-Conference.pdf.
Daniil Tiapkin, Denis Belomestny, Eric Moulines, Alexey Naumov, Sergey Samsonov, Yunhao Tang, Michal Valko, and Pierre Menard. From Dirichlet to rubin: Optimistic exploration in RL without bonuses. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, *Proceedings of the 39th International Conference on Machine Learning*, volume 162 of *Proceedings of Machine Learning Research*, pages 21380–21431. PMLR, 17–23 Jul 2022b. URL https://proceedings.mlr.press/v162/tiapkin22a.html.

Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q-learning. In *Proceedings of the AAAI conference on artificial intelligence*, volume 30, 2016.

Roman Vershynin. *High-dimensional probability: An introduction with applications in data science*, volume 47. Cambridge university press, 2018.

Chris J. Watkins and Peter Dayan. Q-learning. *Machine Learning*, 8(3-4):279–292, 1992. URL https://link.springer.com/content/pdf/10.1007/BF00992698.pdf.

Tzu-Tsung Wong. Generalized dirichlet distribution in bayesian analysis. *Applied Mathematics and Computation*, 97(2):165–181, 1998. ISSN 0096-3003. doi: https://doi.org/10.1016/S0096-3003(97)10140-0. URL https://www.sciencedirect.com/science/article/pii/S0096300397101400.

Zhihan Xiong, Ruoqi Shen, Qiwen Cui, Maryam Fazel, and Simon S Du. Near-optimal randomized exploration for tabular markov decision processes. *Advances in Neural Information Processing Systems*, 35:6358–6371, 2022.

Fan Ye and Enlu Zhou. Information relaxation and dual formulation of controlled markov diffusions. *IEEE Transactions on Automatic Control*, 60(10):2676–2691, 2015.

Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In *International Conference on Machine Learning*, 2019. URL https://arxiv.org/pdf/1901.00210.pdf.

Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advantage decomposition. *arXiv preprint arXiv:2004.10019*, 2020. ISSN 23318422. URL https://arxiv.org/pdf/2004.10019.pdf.
# Appendix

## Table of Contents

<table><tr><td>A Notation</td><td>17</td></tr><tr><td>B Description of RandQL</td><td>18</td></tr><tr><td>B.1 RandQL algorithm</td><td>18</td></tr><tr><td>B.2 Sampled-RandQL algorithm</td><td>19</td></tr><tr><td>C Weight Distribution in RandQL</td><td>20</td></tr><tr><td>D Proofs for Tabular algorithm</td><td>22</td></tr><tr><td>D.1 Algorithm</td><td>22</td></tr><tr><td>D.2 Concentration</td><td>23</td></tr><tr><td>D.3 Optimism</td><td>25</td></tr><tr><td>D.4 Regret Bound</td><td>27</td></tr><tr><td>E Proofs for Metric algorithm</td><td>30</td></tr><tr><td>E.1 Assumptions</td><td>30</td></tr><tr><td>E.2 Algorithm</td><td>30</td></tr><tr><td>E.3 Concentration</td><td>32</td></tr><tr><td>E.4 Optimism</td><td>33</td></tr><tr><td>E.5 Regret Bounds</td><td>36</td></tr><tr><td>F Adaptive RandQL</td><td>40</td></tr><tr><td>F.1 Additional Notation</td><td>40</td></tr><tr><td>F.2 Algorithm</td><td>40</td></tr><tr><td>F.3 Regret Bound</td><td>42</td></tr><tr><td>G Deviation and Anti-Concentration Inequalities</td><td>49</td></tr><tr><td>G.1 Deviation inequality for K<sub>inf</sub></td><td>49</td></tr><tr><td>G.2 Anti-concentration Inequality for Dirichlet Weighted Sums</td><td>49</td></tr><tr><td>G.3 Rosenthal-type inequality</td><td>50</td></tr><tr><td>H Technical Lemmas</td><td>52</td></tr><tr><td>I Experimental details</td><td>53</td></tr><tr><td>I.1 Tabular experiments</td><td>53</td></tr><tr><td>I.2 Non-tabular experiments</td><td>55</td></tr></table>
A Notation

<table><caption>Table 1: Table of notation use throughout the paper for the tabular setting</caption><thead><tr><th>Notation</th><th>Meaning</th></tr></thead><tbody><tr><td>S</td><td>state space of size S</td></tr><tr><td>A</td><td>action space of size A</td></tr><tr><td>H</td><td>length of one episode</td></tr><tr><td>T</td><td>number of episodes</td></tr><tr><td>J</td><td>number of posterior samples</td></tr><tr><td>r<sub>h</sub>(s, a)</td><td>reward</td></tr><tr><td>p<sub>h</sub>(s'|s, a)</td><td>probability transition</td></tr><tr><td>Q<sup>π</sup><sub>h</sub>(s, a)</td><td>Q-function of a given policy π at step h</td></tr><tr><td>V<sup>π</sup><sub>h</sub>(s)</td><td>V-function of a given policy π at step h</td></tr><tr><td>Q<sup>*</sup><sub>h</sub>(s, a)</td><td>optimal Q-function at step h</td></tr><tr><td>V<sup>*</sup><sub>h</sub>(s)</td><td>optimal V-function at step h</td></tr><tr><td>R<sup>T</sup></td><td>regret</td></tr><tr><td>n<sub>0</sub> and n<sub>0</sub>(k)</td><td>number of pseudo-transitions</td></tr><tr><td>s<sub>0</sub></td><td>optimistic pseudo-state</td></tr><tr><td>r<sub>0</sub></td><td>pseudo-reward</td></tr><tr><td>κ</td><td>posterior inflation parameter</td></tr><tr><td>s<sup>t</sup><sub>h</sub></td><td>state that was visited at h step during t episode</td></tr><tr><td>a<sup>t</sup><sub>h</sub></td><td>action that was picked at h step during t episode</td></tr><tr><td>B<sup>t</sup><sub>h</sub></td><td>a ball that contains a pair (s<sup>t</sup><sub>h</sub>, a<sup>t</sup><sub>h</sub>)</td></tr><tr><td>n<sup>t</sup><sub>h</sub>(s, a)</td><td>number of visits of state-action at the beginning of episode t</td></tr><tr><td>n<sup>t</sup><sub>h</sub>(B)</td><td>n<sup>t</sup><sub>h</sub>(s, a) = &sum;<sup>t-1</sup><sub>k=1</sub> 1{(s<sup>k</sup><sub>h</sub>, a<sup>k</sup><sub>h</sub>) = (s, a)}</td></tr><tr><td>e<sub>k</sub></td><td>length of k-th stage e<sub>k</sub> = &lfloor;(1 + 1/H)<sup>k</sup>H&rfloor; for k &ge; 0 and e<sub>-1</sub> = 0</td></tr><tr><td>k<sup>t</sup><sub>h</sub>(s, a)</td><td>index of stage previous to time t at step h and state-action pair (s, a): k<sup>t</sup><sub>h</sub>(s, a) = max{k : n<sup>t</sup><sub>h</sub>(s, a) &ge; &sum;<sup>k</sup><sub>i=0</sub> e<sub>i</sub>}</td></tr><tr><td>n&#771;<sup>t</sup><sub>h</sub>(s, a)</td><td>number of visits of state-action during the current stage: n&#771;<sup>t</sup><sub>h</sub>(s, a) = n<sup>t</sup><sub>h</sub>(s, a) - &sum;<sup>k<sub>h</sub>(s,a)</sup><sub>i=0</sub> e<sub>i</sub></td></tr><tr><td>n&#771;<sup>t</sup><sub>h</sub>(B)</td><td>number of visits of a ball B during the current stage:</td></tr><tr><td>V&#771;<sup>t</sup><sub>h</sub>(s)</td><td>upper approximation of the optimal V-value</td></tr><tr><td>Q&#771;<sup>t</sup><sub>h</sub>(s, a)</td><td>upper approximation of the optimal Q-value</td></tr><tr><td>Q&#771;<sup>t</sup><sub>h</sub>(B)</td><td>upper approximation of the optimal Q-value for all (s, a) &isin; B</td></tr><tr><td>Q&#771;<sup>t,j</sup><sub>h</sub>(s, a)</td><td>temporary estimate of the optimal Q-value</td></tr><tr><td>Q&#771;<sup>t,j</sup><sub>h</sub>(B)</td><td>temporary estimate of the optimal Q-value for all (s, a) &isin; B</td></tr><tr><td>w<sub>n,j</sub></td><td>random learning rates</td></tr><tr><td>&rho;<sub>S</sub>, &rho;<sub>A</sub>, &rho;</td><td>metrics on S, A and S &times; A correspondingly</td></tr><tr><td>N<sub>&epsilon;</sub></td><td>minimal &epsilon;-cover if S &times; A of size N<sub>&epsilon;</sub></td></tr><tr><td>d<sub>c</sub></td><td>covering dimension of space S &times; A: &forall;&epsilon; &gt; 0 : N<sub>&epsilon;</sub> &le; C<sub>N</sub>&epsilon;<sup>-d<sub>c</sub></sup></td></tr><tr><td>d<sub>max</sub></td><td>diameter of S &times; A</td></tr><tr><td>F<sub>h</sub>(s, a, &xi;<sub>h</sub>)</td><td>reparametrization function s<sub>h+1</sub> &sim; p<sub>h</sub>(s, a) &harr; s<sub>h+1</sub> = F<sub>h</sub>(s, a, &xi;<sub>h</sub>)</td></tr><tr><td>L<sub>r</sub>, L<sub>F</sub></td><td>Lipschitz constants of rewards and reparametrization function</td></tr><tr><td>L<sub>V</sub></td><td>Lipschitz constants of Q<sup>*</sup><sub>h</sub> and V<sup>*</sup><sub>h</sub></td></tr></tbody></table>

Let $(X, \mathcal{X})$ be a measurable space and $\mathcal{P}(X)$ be the set of all probability measures on this space. For $p \in \mathcal{P}(X)$ we denote by $E_p$ the expectation w.r.t. $p$. For random variable $\xi: X \to \mathbb{R}$ notation $\xi \sim p$ means Law($\xi$) = $p$. We also write $E_{\xi \sim p}$ instead of $E_p$. For independent (resp. i.i.d.) random variables $\xi_\ell \stackrel{\text{ind}}{\sim} p_\ell$ (resp. $\xi_\ell \stackrel{\text{i.i.d}}{\sim} p_\ell$), $\ell = 1, \dots, d$, we will write $E_{\xi_\ell \stackrel{\text{ind}}{\sim} p_\ell}$ (resp. $E_{\xi_\ell \stackrel{\text{i.i.d}}{\sim} p_\ell}$), to denote expectation w.r.t. product measure on $(X^d, \mathcal{X}^{\otimes d})$. For any $x \in X$ we denote $\delta_x$ a Dirac measure supported at point $x$.
For any $p, q \in \mathcal{P}(X)$ the Kullback-Leibler divergence KL($p, q$) is given by

$$KL(p, q) \triangleq \begin{cases} \mathbb{E}_p[\log \frac{dp}{dq}], & p \ll q, \\ +\infty, & \text{otherwise.} \end{cases}$$

For any $p \in \mathcal{P}(X)$ and $f: X \to \mathbb{R}$, $pf = \mathbb{E}_p[f]$. In particular, for any $p \in \Delta_d$ and $f: \{0, \dots, d\} \to \mathbb{R}$, $pf = \sum_{\ell=0}^d f(\ell)p(\ell)$. Define $\text{Var}_p(f) = \mathbb{E}_{s' \sim p}[(f(s') - pf)^2] = p[f^2] - (pf)^2$. For any $(s, a) \in S$, transition kernel $p(s, a) \in \mathcal{P}(S)$ and $f: S \to \mathbb{R}$ define $pf(s, a) = \mathbb{E}_{p(s,a)}[f]$ and $\text{Var}_p[f](s, a) = \text{Var}_{p(s,a)}[f]$.

Let $(X, \rho)$ be a metric space, then the 1-Wasserstein distance between $p, q \in \mathcal{P}(X)$ is defined as $W_1(p, q) = \sup_{f \text{ is 1-Lipschitz}} \mathbb{E}_p[f] - \mathbb{E}_q[f]$.

We write $f(S, A, H, T) = \mathcal{O}(g(S, A, H, T, \delta))$ if there exist $S_0, A_0, H_0, T_0, \delta_0$ and constant $C_{f,g}$ such that for any $S \ge S_0, A \ge A_0, H \ge H_0, T \ge T_0, \delta < \delta_0$, $f(S, A, H, T, \delta) \le C_{f,g} \cdot g(S, A, H, T, \delta)$. We write $f(S, A, H, T, \delta) = \tilde{\mathcal{O}}(g(S, A, H, T, \delta))$ if $C_{f,g}$ in the previous definition is poly-logarithmic in $S, A, H, T, 1/\delta$.

For $\alpha, \beta > 0$, we define Beta($\alpha, \beta$) as a beta distribution with parameters $\alpha, \beta$. For set $X$ such that $|X| < \infty$ define Unif($X$) as a uniform distribution over this set. In particular, Unif[$N$] is a uniform distribution over a set $[N]$.

For a measure $p \in \mathcal{P}([0, b])$ supported on a segment $[0, b]$ (equipped with a Borel $\sigma$-algebra) and a number $\mu \in [0, b]$ we define

$$\mathcal{K}_{\inf}(p, \mu) \triangleq \inf\{\text{KL}(p, q) : q \in \mathcal{P}([0, b]), p \ll q, \mathbb{E}_{X \sim q}[X] \ge \mu\}.$$

As the Kullback-Leibler divergence this quantity admits a variational formula by Lemma 18 of Garivier et al. [2018] up to rescaling for any $u \in (0, b)$

$$\mathcal{K}_{\inf}(p, \mu) = \max_{\lambda \in [0, 1/(b-\mu)]} \mathbb{E}_{X \sim p}[\log(1 - \lambda(X - \mu))]$$

# B Description of RandQL

In this appendix we describe RandQL and Sampled-RandQL algorithms.

## B.1 RandQL algorithm

We recall that $n_h^t(s, a) = \sum_{i=1}^{t-1} 1\{(s_h^i, a_h^i) = (s, a)\}$ is the number of visits of state-action pair $(s, a)$ at step $h$ before episode $t$.

We start by initializing the ensemble of Q-values, the policy Q-values, and values to an optimistic value $\tilde{Q}_h^{t,j}(s, a) = \bar{Q}_h^1(s, a) = \bar{V}_h^1(s, a) = r_h(s, a) + r_0(H - h)$ for all $(j, h, s, a) \in [J] \times [H] \times S \times A$ and $r_0 > 0$ some pseudo-rewards.

At episode $t$ we update the ensemble of Q-values as follows, denoting by $n = n_h^t(s, a)$ the count, $w_{j,n} \sim \text{Beta}(H, n)$ the independent learning rates,

$$\tilde{Q}_h^{t+1,j}(s, a) = \begin{cases} (1 - w_{j,n}) \tilde{Q}_h^{t,j}(s, a) + w_{j,n} \hat{Q}_h^{t,j}(s, a), & (s, a) = (s_h^t, a_h^t) \\ \tilde{Q}_h^{t,j}(s, a) & \text{otherwise,} \end{cases}$$

where we defined the target $\hat{Q}_h^{t,j}(s, a)$ as a mixture between the usual target and some prior target with mixture coefficient $\hat{w}_{n,j} \sim \text{Beta}(n, n_0)$ and $n_0$ the number of prior samples,

$$\hat{Q}_h^{t,j}(s, a) = \hat{w}_{n,j}[r_h(s, a) + \bar{V}_{h+1}^t(s_{h+1}^t)] + (1 - \hat{w}_{n,j})[r_h(s, a) + r_0(H - h - 1)].$$

It is important to note that in our approach, we need to re-inject prior targets to avoid forgetting their effects too quickly due to the aggressive learning rate. Indeed, the exponential decay of the prior effect can hurt exploration. We observe that the ensemble Q-value only averages uniformly over the last $1/H$ fraction of the targets, as the expected value of the learning rate is $\mathbb{E}[w_{j,n}] = H/(n+H)$. Since $\mathbb{E}[1 - \hat{w}_{n,j}] = n_0(n + n_0)$ the weight put on the prior sample in expectation, when we unfold
the definition of $\tilde{Q}_h^{t+1,j}$, is of order $H/n \cdot n/H \cdot n_0/(n+n_0) = n_0/(n+n_0)$, which is consistent with the usual prior forgetting in Bayesian learning. In Staged-RandQL, we avoid forgetting the prior too quickly by resetting the temporary Q-value to a prior value at the beginning of each stage.

The policy Q-values are obtained by taking the maximum among the ensemble of Q-values

$$ \bar{Q}_h^{t+1}(s, a) = \max_{j \in [J]} \tilde{Q}_h^{t+1,j}(s, a). $$

The policy is then greedy with respect to the policy Q-values $\pi_h^{t+1}(s) \in \arg\max_{a \in \mathcal{A}} \bar{Q}_h^{t+1}(s, a)$ and the value is $\bar{V}_h^{t+1}(s) = \max_{a \in \mathcal{A}} \bar{Q}_h^{t+1}(s, a)$. The complete RandQL procedure is detailed in Algorithm 2.

**Algorithm 2 RandQL**

1: **Input:** $J$ ensemble size, number of prior transitions $n_0$, prior reward $r_0$.

2: **Initialize:** $\bar{V}_h(s) = \bar{Q}_h(s, a) = \tilde{Q}_h^j(s, a) = r(s, a) + r_0(H-h)$, initialize counters $n_h(s, a) = 0$ for $h, s, a \in [H] \times S \times \mathcal{A}$.

3: **for** $t \in [T]$ **do**

4: **for** $h \in [H]$ **do**

5: Play $a_h \in \arg\max_a \bar{Q}_h(s_h, a)$.

6: Observe reward and next state $s_{h+1} \sim p_h(s_h, a_h)$.

7: Sample $\hat{w}_j \sim \text{Beta}(n, n_0)$ for $n = n_h(s_h, a_h)$.

8: Build targets for all $j \in [J]$

$$ \hat{Q}_h^j = \hat{w}_j[r_h(s_h, a_h) + \bar{V}_{h+1}(s_{h+1})] + (1 - \hat{w}_j)[r_h(s_h, a_h) + r_0(H-h)]. $$

9: Sample learning rates $w_j \sim \text{Beta}(H, n)$.

10: Update ensemble Q-functions for all $j \in [J]$

$$ \tilde{Q}_h^j(s_h, a_h) := (1 - w_j) \tilde{Q}_h^j(s_h, a_h) + w_j \hat{Q}_h^j. $$

11: Update policy Q-function $\bar{Q}_h(s_h, a_h) := \max_{j \in [J]} \tilde{Q}_h^j(s_h, a_h)$.

12: Update value function $\bar{V}_h(s_h) := \max_{a \in \mathcal{A}} \bar{Q}_h(s_h, a)$.

13: **end for**

14: **end for**

**B.2 Sampled-RandQL algorithm**

To create an algorithm that is more similar to PSRL, it is possible to select a Q-value at random from the ensemble of Q-values, rather than using the maximum Q-value

$$ \tilde{Q}_h^t(s, a) = \tilde{Q}_h^{t,j_t}(s, a) \quad \text{with } j_t \sim \text{Unif}[J]. $$

In this case we also need to update each Q-value in the ensemble with its corresponding target, see Osband and Van Roy [2015],

$$ \hat{Q}_h^{t,j}(s, a) = \hat{w}_{j,n}[r_h(s, a) + \tilde{V}_{h+1}^{t,j}(s_{h+1}^t)] + (1 - \hat{w}_{j,n})[r_h(s, a) + r_0(H - h - 1)] $$

where $\tilde{V}_h^{t,j}(s) = \max_{a \in \mathcal{A}} \tilde{Q}_h^{t,j}(s, a)$. We name this new procedure Sampled-RandQL and detail it in Algorithm 3.
Algorithm 3 Sampled-RandQL

1: **Input:** J ensemble size, number of prior transitions $n_0$, prior reward $r_0$.

2: **Initialize:** $\bar{V}_h(s) = \bar{Q}_h(s, a) = \tilde{Q}_h^j(s, a) = r(s, a) + r_0(H - h)$, initialize counters $n_h(s, a) = 0$ for $h, s, a \in [H] \times S \times A$.

3: **for** $t \in [T]$ **do**

4: Sample ensemble index $i \sim \text{Unif}[J]$

5: **for** $h \in [H]$ **do**

6: Play $a_h \in \arg \max_a \bar{Q}_h(s_h, a)$.

7: Observe reward and next state $s_{h+1} \sim p_h(s_h, a_h)$.

8: Sample $\hat{w}_j \sim \text{Beta}(n, n_0)$ for $n = n_h(s_h, a_h)$.

9: Build targets for all $j \in [J]$

$$ \tilde{Q}_h^j = \hat{w}_j[r_h(s_h, a_h) + \tilde{V}_{h+1}^j(s_{h+1})] + (1 - \hat{w}_j)[r_h(s_h, a_h) + r_0(H - h)]. $$

10: Sample learning rates $w_j \sim \text{Beta}(H, n)$.

11: Update ensemble Q-functions for all $j \in [J]$

$$ \tilde{Q}_h^j(s_h, a_h) := (1 - w_j) \tilde{Q}_h^j(s_h, a_h) + w_j \hat{Q}_h^j. $$

12: Update value function $\bar{V}_h(s_h) := \max_{a \in A} \tilde{Q}_h^j(s_h, a)$ for all $j \in [J]$.

13: Update policy Q-function $\bar{Q}_h(s_h, a_h) := \tilde{Q}_h^i(s_h, a_h)$.

14: **end for**

15: **end for**

C Weight Distribution in RandQL

In this section we study the joint distribution of weights over all targets in RandQL algorithm, described in details in Appendix B. To do it, we describe a very useful distribution, defined by Wong [1998].

**Definition 5.** We say that a random vector $(X_1, \dots, X_n, X_{n+1})$ has a generalized Dirichlet distribution GDir$(\alpha_1, \dots, \alpha_n; \beta_1, \dots, \beta_n)$ if $X_{n+1} = 1 - (X_1 + \dots + X_n)$ and $(X_1, \dots, X_n)$ it has the following density over the simplex $\{x_1, \dots, x_n : x_1 + \dots + x_n \le 1\}$,

$$ p(x) = \prod_{i=1}^{n} \frac{1}{B(\alpha_i, \beta_i)} x_i^{\alpha_i - 1} (1 - x_1 - \dots - x_i)^{\gamma_i} $$

for $x_1 + \dots + x_n \le 1$, $x_j \ge 0$ for $j = 1, \dots, n$, and $\gamma_j = \beta_j - \alpha_{j+1} - \beta_{j+1}$ for $j = 1, \dots, n-1$ and $\gamma_n = \beta_n - 1$. If we set $x_{n+1} = 1 - (x_1 + \dots + x_n)$ then we obtain a homogeneous formula

$$ p(x) = \prod_{i=1}^{n} \frac{1}{B(\alpha_i, \beta_i)} x_i^{\alpha_i - 1} \left( \sum_{j=i+1}^{n+1} x_j \right)^{\gamma_i} $$

Alternative characterization of generalized Dirichlet distribution could be given using independent beta-distributed random variables $Z_1, \dots, Z_n$ with $Z_i \sim \text{Beta}(\alpha_i, \beta_i)$ as follows

$$ X_1 = Z_1, $$

$$ X_j = Z_j(1 - X_1 - \dots - X_{j-1}) = Z_j \prod_{i=1}^{j-1} (1 - Z_i) \quad \text{for } j = 2, 3, \dots, n $$

$$ X_{n+1} = 1 - X_1 - \dots - X_n = \prod_{i=1}^{n} (1 - Z_i) $$

Therefore, for RandQL algorithm without prior re-injection we have the following formula

$$ \tilde{Q}_h^{t,j}(s, a) = \sum_{i=0}^{n_h^t(s, a)} W_{j,n}^i \left( r_h(s_h^{\ell_i}, a_h^{\ell_i}) + \bar{V}_{h+1}^{\ell_i}(s_{h+1}^{\ell_i}) \right), $$
for $n = n_h^t(s, a)$ and weights are defined as follows

$$W_{j,n}^0 = \prod_{q=0}^{n-1} (1 - w_{j,q}), \quad W_{j,n}^i = w_{j,i-1} \cdot \prod_{q=i}^{n-1} (1 - w_{j,q}), \quad i \ge 1.$$

And, moreover, we have that this vector of weights has the generalized Dirichlet distribution

$$(W_{n,j}^n, W_{n,j}^{n-1}, \dots, W_{n,j}^1, W_{n,j}^0) \sim \text{GDir}(H, H, \dots, H; n + n_0, \dots, n_0 + 1, n_0).$$

That is, weights generated by the RandQL procedure is an inverted generalized Dirichlet random vector, that induces additional similarities with a usual posterior sampling approaches. Notably, that for $H = 1$ we recover exactly usual Dirichlet distribution, as in the setting of Staged-RandQL.

In the setting of the analysis, the main feature of this distribution is asymmetry in attitude to the order of components. In particular, the expectation of the prior weight $W_{n,j}^0$ is $\prod_{i=1}^n \left(1 - \frac{H}{i+H}\right) \sim n^{-H}$ that leads to too rapid forgetting of the prior information.
# D Proofs for Tabular algorithm

## D.1 Algorithm

In this section we describe in detail the tabular algorithms and the ways we will analyze them. We also provide some notations that will be used in the sequel.

Let $n_h^t(s, a)$ be the number of visits of $(s, a, h)$ (i.e., of the state-action pair $(s, a)$ at step $h$) at the beginning of episode $t$: $n_h^t(s, a) = \sum_{i=1}^{t-1} 1\{(s_h^i, a_h^i) = (s, a)\}$. In particular, $n_h^{t+1}(s, a)$ is the number of visits of $(s, a, h)$ after all episodes.

Let $e_k = \lfloor(1 + 1/H)^k \cdot H \rfloor$ be the length of each stage for any $k \ge 0$ and, by convention, $e_{-1} = 0$. We will say that at the beginning of episode $t$ a triple $(s, a, h)$ is in $k$-th stage if $n_h^t(s, a) \in [\sum_{i=0}^{k-1} e_i, \sum_{i=0}^k e_i)$.

Let $\tilde{n}_h^t(s, a)$ be the number of visits of state-action pair during the current stage at the beginning of episode $t$. Formally, it holds $\tilde{n}_h^t(s, a) = n_h^t(s, a) - \sum_{i=0}^{k-1} e_i$, where $k$ is the index of current stage.

Let $\kappa > 0$ be the posterior inflation coefficient, $n_0$ be the number of prior transitions, and $J$ be the number of temporary $Q$-functions. Let $\tilde{Q}_h^{t,j}$ be the $j$-th temporary $Q$-function and $\overline{Q}_h^t$ be the policy $Q$-function at the beginning of episode $t$. We initialize them as follows

$$ \overline{Q}_h^1(s, a) = r_h(s, a) + r_0(H - h - 1), \quad \tilde{Q}_h^{1,j}(s, a) = r_h(s, a) + r_0(H - h - 1), $$

We can treat this initialization as a setting prior over $n_0$ pseudo-transitions to artificial state $s_0$ with $r_0 > 1$ reward for each interaction.

For each transition we perform the following update of temporary $Q$-functions

$$ \tilde{Q}_h^{t+1/2,j}(s, a) = \begin{cases} (1 - w_{j,\tilde{n}}^k) \cdot \tilde{Q}_h^{t,j}(s, a) + w_{j,\tilde{n}}^k [r_h(s, a) + \overline{V}_{h+1}^t(s_{h+1}^t)], & (s, a) = (s_h^t, a_h^t) \\ \tilde{Q}_h^{t,j}(s, a) & \text{otherwise,} \end{cases} \quad (2) $$

where $\tilde{n} = \tilde{n}_h^t(s, a)$ is the number of visits of $(s, a, h)$ during the current stage at the beginning of episode $t$, $k$ is the index of the current stage, and $w_{j,\tilde{n}}^k$ is a sequence of independent beta-distribution random variables $w_{j,\tilde{n}}^k \sim \text{Beta}(1/\kappa, (\tilde{n} + n_0)/\kappa)$. Here we slightly abuse the notation by dropping the dependence of weights $w_{j,\tilde{n}}^k$ on the triple $(h, s, a)$ in order to simplify the exposition. In the case that the explicit dependence is required, we will call these weights as $w_{j,\tilde{n}}^{k,h}(s, a)$.

Next we define the stage update as follows

$$ \begin{aligned} \overline{Q}_h^{t+1}(s, a) &= \begin{cases} \max_{j \in [J]} \tilde{Q}_h^{t+1/2,j}(s, a) & \tilde{n}_h^t(s, a) = \lfloor(1 + 1/H)^k H \rfloor \\ \overline{Q}_h^t(s, a) & \text{otherwise} \end{cases} \\ \tilde{Q}_h^{t+1,j}(s, a) &= \begin{cases} r_h(s, a) + r_0(H - h + 1) & \tilde{n}_h^t(s, a) = \lfloor(1 + 1/H)^k H \rfloor \\ \tilde{Q}_h^{t+1/2,j}(s, a) & \text{otherwise} \end{cases} \\ \overline{V}_h^{t+1}(s) &= \max_{a \in A} \overline{Q}_h^{t+1}(s, a) \\ \pi_h^{t+1}(s) &\in \arg \max_{a \in A} \tilde{Q}_h^{t+1}(s, a), \end{aligned} \quad (3) $$

where $k$ is the current stage. In other words, we update $\overline{Q}^{t+1}$ with temporary values of $\tilde{Q}^{t+1/2,j}$, and then, if the change of stage is triggered, reinitialize $\tilde{Q}_h^{t+1,j}(s, a)$ for all $j$. For episode $t$ we will call $k_h^t(s, a)$ the index of stage where $\overline{Q}_h^t(s, a)$ was updated (and $k_h^t(s, a) = -1$ if there was no update). For all $t$ we define $\tau_h^t(s, a) \le t$ as an episode when the stage update happens. In other words, for any $t$ the following holds

$$ \overline{Q}_h^{t+1}(s, a) = \max_{j \in [J]} \tilde{Q}_h^{\tau_h^t(s, a)+1/2,j}(s, a), $$

where $\tau_h^t(s, a) = 0$ and $e_k = 0$ if there was no updates. To simplify the notation we will omit dependence on $(s, a, h)$ where it is deducible from the context.
To simplify the notation, we can extend the state space $\mathcal{S}$ by an additional state $s_0$ that will be purely technical and used in the proofs. This state has the prescribed value function $V_h^*(s_0) = r_0(H - h)$ and could be treated as a absorbing pseudo-state with reward $r_0$.

We notice that in this case we use $e_k$ samples to compute $\tilde{Q}_{h}^{\tau_h^t(s,a)+1/2,j}$ for $k = k_h^t(s, a)$. For this $k$ we define $\ell_{k,h}^i(s, a)$ as a time of $i$-th visit of state-action pair $(s, a)$ during $k$-th stage. Then we have the following decomposition

$$ \tilde{Q}_{h}^{\tau_h^t+1/2,j}(s, a) = r_h(s, a) + \sum_{i=0}^{e_k} W_{j,e_k,k}^i \bar{V}_{h+1}^{\ell_i}(s_{h+1}^{\ell_i}), \quad (3) $$

where we drop dependence on $k$ and $(s, a, h)$ in $\ell^i$ to simplify notations, and use the convention $s_{h+1}^{\ell_{k,h}^i(s,a)} = s_0$, and the following aggregated weights

$$ W_{j,n,k}^0 = \prod_{q=0}^{n-1} (1 - w_{j,q}^k), \quad W_{j,n,k}^i = w_{j,i-1}^k \cdot \prod_{q=i}^{n-1} (1 - w_{j,q}^k), \quad i \ge 1. $$

We will omit the dependence on the stage index $k$ when it is not needed for the statement. However, we notice that these vectors, for different stages $k$, will be independent.

By the properties of the generalized Dirichlet distribution, it is possible to show the following result

**Lemma 3.** For any fixed $n > 0$, the random vector $(W_{j,n}^0, W_{j,n}^1, \dots, W_{j,n}^n)$ has a Dirichlet distribution $\text{Dir}(n_0/\kappa, 1/\kappa, \dots, 1/\kappa)$.

*Proof.* Using the Dirichlet random variate generation from marginal beta distributions, it is sufficient to prove that for all $i \in \{0, \dots, n\}$, $W_{j,n,k}^{n-i} = (1 - W_{j,n,k}^n - \dots - W_{j,n,k}^{n-i+1})w_{j,n-i-1}^k$, with the convention $w_{j,n-1}^k = 1$. This is trivial for $i = 0$, as $W_{j,n,k}^n = w_{j,n-1}^k$. Now, if this is true for some $i$, then, for $i+1 \in \{0, \dots, n\}$, we have

$$ \begin{aligned} W_{j,n,k}^{n-i-1} &= w_{j,n-i-2}^k \prod_{q=n-i-1}^{n-1} (1 - w_{j,q}^k) \\ &= w_{j,n-i-2}^k (1 - w_{j,n-i-1}^k) (1 - W_{j,n,k}^n - \dots - W_{j,n,k}^{n-i+1}) \\ &= w_{j,n-i-2}^k (1 - W_{j,n,k}^n - \dots - W_{j,n,k}^{n-i+1} - \underbrace{w_{j,n-i-1}^k (1 - W_{j,n,k}^n - \dots - W_{j,n,k}^{n-i+1})}_{=W_{j,n,k}^{n-i}}), \end{aligned} $$

which finishes the proof. $\square$

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

Notably, the expression (3) shows a significant similarity between our method and OPSRL. It is the reason why we can call this method a model-free posterior sampling, where posterior sampling is performed over the model in a lazy and model-free fashion.

## D.2 Concentration

Let $\beta^*: (0, 1) \times \mathbb{N} \to \mathbb{R}_+$ and $\beta^B, \beta^{\text{conc}}, \beta: (0, 1) \to \mathbb{R}_+$ be some function defined later on in Lemma 4. We define the following favorable events
$$
\mathcal{E}^*(\delta) \triangleq \left\{ \forall t \in \mathbb{N}, \forall h \in [H], \forall (s, a) \in \mathcal{S} \times \mathcal{A}, k = k_h^t(s, a) : \right.
$$
$$
\left. \qquad \mathcal{K}_{\inf} \left( \frac{1}{e_k} \sum_{i=1}^{e_k} \delta_{V_{h+1}^*(s_{h+1}^i)}, p_h V_{h+1}^*(s, a) \right) \le \frac{\beta^*(\delta, e_k)}{e_k} \right\},
$$

$$
\mathcal{E}^B(\delta) \triangleq \left\{ \forall t \in [T], \forall h \in [H], \forall (s,a) \in \mathcal{S} \times \mathcal{A}, \forall j \in [J], k = k_h^t(s,a) : \right.
$$
$$
\left. \left| \sum_{i=0}^{e_k} (W_{j,e_k,k}^i - \mathbb{E}[W_{j,e_k,k}^i]) \bar{V}_{h+1}^{\ell^i}(s_{h+1}^{\ell^i}) \right| \le 60e^2 \sqrt{\frac{r_0^2 H^2 \kappa \beta^B(\delta)}{e_k + n_0}} \right.
$$
$$
\left. \qquad + 1200e \frac{r_0 H \kappa \log(e_k)(\beta^B(\delta))^2}{e_k + n_0} \right\},
$$

$$
\mathcal{E}^{\text{conc}}(\delta) \triangleq \left\{ \forall t \in [T], \forall h \in [H], \forall (s,a) \in \mathcal{S} \times \mathcal{A}, k = k_h^t(s,a) : \right.
$$
$$
\left. \left| \frac{1}{e_k} \sum_{i=1}^{e_k} V_{h+1}^*(s_{h+1}^{\ell_{k,h}^i(s,a)}) - p_h V_{h+1}^*(s,a) \right| \le \sqrt{\frac{2r_0^2 H^2 \beta^{\text{conc}}(\delta)}{e_k}} \right\}
$$

$$
\mathcal{E}(\delta) \triangleq \left\{ \sum_{t=1}^{T} \sum_{h=1}^{H} (1 + 1/H)^{H-h} \left| p_h [V_{h+1}^{\star} - V_{h+1}^{\pi_t}](s_h^t, a_h^t) - [V_{h+1}^{\star} - V_{h+1}^{\pi_t}](s_{h+1}^t) \right| \right. \\
\left. \le 2er_0 H \sqrt{2HT\beta(\delta)}. \right\}.
$$

We also introduce the intersection of these events, $\mathcal{G}(\delta) \triangleq \mathcal{E}^*(\delta) \cap \mathcal{E}^B(\delta) \cap \mathcal{E}^{\text{conc}}(\delta) \cap \mathcal{E}(\delta)$. We prove that for the right choice of the functions $\beta^*, \beta^{\text{KL}}, \beta^{\text{conc}}, \beta, \beta^{\text{Var}}$ the above events hold with high probability.

**Lemma 4.** For any $\delta \in (0, 1)$ and for the following choices of functions $\beta$,

$$
\beta^*(\delta, n) \triangleq \log(8SAH/\delta) + 3\log(e\pi(2n+1)),
$$

$$
\beta^B(\delta) \triangleq \log(8SAH/\delta) + \log(TJ),
$$

$$
\beta^{\text{conc}}(\delta) \triangleq \log(8SAH/\delta) + \log(2T),
$$

$$
\beta(\delta) \triangleq \log(16/\delta),
$$

it holds that

$$
\begin{align*}
\mathbb{P}[\mathcal{E}^*(\delta)] \ge 1 - \delta/8, &\qquad \mathbb{P}[\mathcal{E}^B(\delta)] \ge 1 - \delta/8, \\
\mathbb{P}[\mathcal{E}^{\text{conc}}(\delta)] \ge 1 - \delta/8, &\qquad \mathbb{P}[\mathcal{E}(\delta)] \ge 1 - \delta/8.
\end{align*}
$$

In particular, $\mathbb{P}[\mathcal{G}(\delta)] \ge 1 - \delta/2$.

*Proof.* From the fact that $s_{h+1}^{\ell^i}$ are i.i.d. generated from $p_h(s, a)$, Theorem 4, and union bound $\mathcal{S} \times \mathcal{A} \times [H]$ it holds $\mathbb{P}[\mathcal{E}^*(\delta)] \ge 1 - \delta/8$.

Next we fix all $t, h, s, a, j$, and denote $n = e_{k_h^t(s,a)}$. First, we define a filtration of $\sigma$-algebras $\mathcal{F}_\tau$ that is sigma-algebra generated by all random variables appeared untill the update (2) in the episode $t$ and step $h$, before newly generated random weights but after receiving new state $s_{h+1}^t$. Formally, we can define it as follows

$$
\mathcal{F}_{t,h} = \sigma \left( \left\{ (s_{h'}^{\tau}, a_{h'}^{\tau}, w_{j, \tilde{n}_{h'}^{\tau}}^{k_{h'}^{\tau}+1, h'} (s_{h'}^{\tau}, a_{h'}^{\tau})), \forall \tau < t, (h', j) \in [H] \times [J] \right\} \cup \left\{ (s_{h'}^{t}, a_{h'}^{t}, s_{h'+1}^{t}), \forall h' \le h \right\} \cup \left\{ w_{j, \tilde{n}_{h'}^{t}}^{k_{h'}^{t}+1, h'} (s_{h'}^{t}, a_{h'}^{t}), \forall h' < h, j \in [J] \right\} \right),
$$
where we drop dependence on state-action pairs everywhere where it is deducible from the context.

Consider a sequence $\ell^1 < \dots < \ell^n$ be an excursion of the state-action pair $(s, a)$ at the step $h$. Each $\ell^i$ is a stopping time w.r.t $\mathcal{F}_{t,h}$, so we can consider a stopped filtration (with a shift by 1 in indices) $\tilde{\mathcal{F}}_{i-1} = \mathcal{F}_{\ell^i, h}$. In other words, this filtration at time-steps $i-1$ contains all the information that is available just before the generation of random weights for the $i$-th update of temporary Q-functions inside the last stage. We notice that under this definition, we have

$$ \mathbb{E}[\overline{V}_{h+1}^{\ell_i}(s_{h+1}^{\ell_i}) | \tilde{\mathcal{F}}_{i-1}] = \overline{V}_{h+1}^{\ell_i}(s_{h+1}^{\ell_i}), \quad \mathbb{E}[w_{j,n}^i | \tilde{\mathcal{F}}_{i-1}] = \mathbb{E}[w_{j,n}^i] $$

and, moreover, $w_{j,n}^i$ is $\tilde{\mathcal{F}}_i$-measurable. To simplify the notation, we define $Y_i = \overline{V}_{h+1}^{\ell_i}(s_{h+1}^{\ell_i})/(r_0 \cdot H)$, and then we notice that we can apply the recursion on the aggregated weights back: define two Q-value-style sequences

$$ X_i = (1 - w_{j,n}^i)X_{i-1} + w_{j,n}^i Y_i, \quad \bar{X}_i = (1 - \mathbb{E}[w_{j,n}^i])\bar{X}_{i-1} + \mathbb{E}[w_{j,n}^i]Y_i. $$

Then, by the aggregation property, we have

$$ (r_0 \cdot H) \cdot (X_n - \bar{X}_n) = \sum_{i=0}^{n} (W_{j,n,k}^i - \mathbb{E}[W_{j,n,k}^i]) \overline{V}_{h+1}^{\ell_i}(s_{h+1}^{\ell_i}). $$

Given this reformulation, Proposition 7 and union bound implies $\mathbb{P}[\mathcal{E}^B(\delta)] \ge 1 - \delta/8$.

To show that $\mathbb{P}(\mathcal{E}^{\text{conc}}(\delta)) > 1 - \delta/8$, it is enough to apply Hoeffding inequality for a fixed number of samples $e_k$ used in empirical mean, and then use union bound of all possible values of $(s, a, h) \in S \times A \times [H]$ and $e_k \in [T]$.

Next, define the following sequence

$$ Z_{t,h} \triangleq (1 + 1/H)^{H-h} \left( [V_{h+1}^* - V_{h+1}^{\pi^t}](s_{h+1}^t) - p_h[V_{h+1}^* - V_{h+1}^{\pi^t}](s_h^t, a_h^t) \right), \quad t \in [T], h \in [H], $$

It is easy to see that these sequences form a martingale-difference w.r.t filtration $\mathcal{F}_{t,h} = \sigma\{(s_{h'}^\ell, a_{h'}^\ell, \pi^\ell), \ell < t, h' \in [H]\} \cup \{(s_{h'}^t, a_{h'}^t, \pi^t), h' \le h\}$. Moreover, $|Z_{t,h}| \le 2e_0 H$ for all $t \in [T]$ and $h \in [H]$. Hence, the Azuma-Hoeffding inequality implies

$$ \mathbb{P}\left(\left|\sum_{t=1}^{T} \sum_{h=1}^{H} Z_{t,h}\right| > 2e_0 H \sqrt{2tH \cdot \beta(\delta)}\right) \le 2 \exp(-\beta(\delta)) = \delta/8, $$

therefore $\mathbb{P}[\mathcal{E}(\delta)] \ge 1 - \delta/8$. $\square$

### D.3 Optimism

In this section we prove that our estimate of Q-function $\overline{Q}_h^t(s, a)$ is optimistic, that is the event

$$ \mathcal{E}_{\text{opt}} \triangleq \left\{ \forall t \in [T], h \in [H], (s, a) \in S \times A : \overline{Q}_h^t(s, a) \ge Q_h^*(s, a) \right\}. \quad (4) $$

holds with high probability on the event $\mathcal{E}^*(\delta)$.

Define constants

$$ c_0 \triangleq \frac{8}{\pi} \left( \frac{4}{\sqrt{\log(17/16)}} + 8 + \frac{49 \cdot 4\sqrt{6}}{9} \right)^2 + 1. \quad (5) $$

and

$$ c_J \triangleq \frac{1}{\log\left(\frac{2}{1+\Phi(1)}\right)}, \quad (6) $$

where $\Phi(\cdot)$ is a CDF of a normal distribution.

**Proposition 1.** Assume that $J = [c_J \cdot \log(2SAHT/\delta)]$, $\kappa = 2\beta^*(\delta, T)$, $r_0 = 2$, and $n_0 = \lceil(c_0 + 1 + \log_{17/16}(T)) \cdot \kappa\rceil$. Then conditionally on $\mathcal{E}^*(\delta)$ the event

$$ \mathcal{E}_{\text{anticonc}} \triangleq \left\{ \forall t \in [T], \forall h \in [H], \forall (s, a) \in S \times A : \max_{j \in [J]} \left\{ \sum_{i=0}^{e_k} W_{j,e_k,k}^i V_{h+1}^*(s_{h+1}^{\ell_{t,h}^i(s,a)}) \right\} \ge p_h V_{h+1}^*(s, a), k = k_h^t(s, a) \right\} $$

holds with probability at least $1 - \delta/2$.
**Proof.** Let us fix $t \in [T]$, $h \in [H]$, $(s, a) \in S \times A$, and $j \in [J]$. By Lemma 3, we have that the vector $(W_{j,e_k,k}^i)_{i=0,\dots,e_k}$ has Dirichlet distribution. Note that $V_{h+1}^*(s_{h+1}^{\ell_0}) = r_0(H-h-1)$ is an upper bound on $V$-function and the weight of the first atom is $\alpha_0 \triangleq n_0/\kappa \ge c_0 + \log_{17/16}(T)$ for $c_0$ defined in (5). Define a measure $\bar{\nu}_{e_k} = \frac{n_0-1}{e_k+n_0-1} \delta_{V_{h+1}^*(s_0)} + \sum_{i=1}^{e_k} \frac{1}{e_k+n_0-1} \delta_{V_{h+1}^*(s_{h+1}^{\ell_i})}$. Since $p_h V_{h+1}^*(s, a) \le H-h-1$, we can apply Lemma 10 with a fixed $\varepsilon = 1/2$ conditioned on independent samples $\{s_{h+1}^{\ell_i}\}_{i=1}^{e_k}$ from $p_h(s, a)$

$$ \mathbb{P}\left[\sum_{i=0}^{e_k} W_{j,e_k,k}^i V_{h+1}^*(s_{h+1}^{\ell_{t,h}^i(s,a)}) \ge p_h V_{h+1}^*(s, a) \mid \{s_{h+1}^{\ell_i}\}_{i=1}^{e_k}\right] \\ \ge \frac{1}{2} \left(1 - \Phi\left(\sqrt{\frac{2(e_k + n_0 - \kappa) \mathcal{K}_{\inf}(\bar{\nu}_{e_k}, p_h V_{h+1}^*(s, a))}{\kappa}}\right)\right), \quad (7) $$

where $\Phi$ is a CDF of a normal distribution. Combining Lemma 12 and the event $\mathcal{E}^*(\delta)$

$$ (e_k + n_0 - \kappa) \mathcal{K}_{\inf}(\bar{\nu}_{e_k}, p_h V_{h+1}^*(s, a)) \le e_k \mathcal{K}_{\inf}(\hat{\nu}_{e_k}, p_h V_{h+1}^*(s, a)) \le \beta^*(\delta, T), $$

where $\hat{\nu}_{e_k} = \frac{1}{e_k} \sum_{i=1}^{e_k} \delta_{V_{h+1}^*(s_{h+1}^{\ell_i})}$, and, as a corollary

$$ \mathbb{P}\left[\sum_{i=0}^{e_k} W_{j,e_k,k}^i V_{h+1}^*(s_{h+1}^{\ell_{t,h}^i(s,a)}) \ge p_h V_{h+1}^*(s, a) \mid \mathcal{E}^*(\delta), \{s_{h+1}^{\ell_i}\}_{i=1}^{e_k}\right] \ge \frac{1}{2}\left(1 - \Phi\left(\sqrt{\frac{2\beta^*(\delta, T)}{\kappa}}\right)\right). $$

By taking $\kappa = 2\beta^*(\delta, T)$ we have a constant probability of being optimistic

$$ \mathbb{P}\left(\sum_{i=0}^{e_k} W_{j,e_k,k}^i V_{h+1}^*(s_{h+1}^{\ell_{t,h}^i(s,a)}) \ge p_h V_{h+1}^*(s, a) \mid \mathcal{E}^*(\delta)\right) \ge \frac{1 - \Phi(1)}{2} \triangleq \gamma. $$

Next, using a choice $J = \lceil \log(2SAHT/\delta)/\log(1/(1-\gamma)) \rceil = \lceil c_J \cdot \log(2SAHT/\delta) \rceil$

$$ \mathbb{P}\left[\max_{j \in [J]} \left\{\sum_{i=0}^{e_k} W_{j,e_k,k}^i V_{h+1}^*(s_{h+1}^{\ell_{t,h}^i(s,a)})\right\} \ge p_h V_{h+1}^*(s, a) \mid \mathcal{E}^*(\delta)\right] \ge 1 - (1 - \gamma)^J \ge 1 - \frac{\delta}{2SAHT}. $$

By a union bound we conclude the statement. $\square$

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

Next we provide a connection between $\mathcal{E}^{\text{anticonc}}$ and $\mathcal{E}^{\text{opt}}$.

**Proposition 2.** It holds that $\mathcal{E}^{\text{opt}} \subseteq \mathcal{E}^{\text{anticonc}}$.

**Proof.** We proceed by a backward induction over $h$. Base of induction $h = H+1$ is trivial. Next by Bellman equations for $\bar{Q}_h^t$ and $Q_h^*$

$$ [\bar{Q}_h^t - Q_h^*](s, a) = \max_{j \in [J]} \left\{ \sum_{i=0}^{n} W_{j,n}^i \bar{V}_{h+1}^{\ell_i}(s_{h+1}^{\ell_i}) \right\} - p_h V_{h+1}^*(s, a), $$

where $n = e_k \bar{Q}_h^t(s, a)$ and we drop dependence on $k, t, h, s, a$ in $\ell^i$. By induction hypothesis we have $\bar{V}_{h+1}^{\ell_i}(s') \ge \bar{Q}_{h+1}^{\ell_i}(s', \pi^*(s')) \ge Q_{h+1}^*(s', \pi^*(s')) = V_{h+1}^*(s')$ for any $i$, thus

$$ [\bar{Q}_h^t - Q_h^*](s, a) \ge \max_{j \in [J]} \left\{ \sum_{i=0}^{n} W_{j,n}^i V_{h+1}^*(s_{h+1}^{\ell_i}) \right\} - p_h V_{h+1}^*(s, a). $$

By the definition of event $\mathcal{E}^{\text{anticonc}}(\delta)$ we conclude the statement. $\square$

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

**Proposition 3 (Optimism).** Assume that $J = \lceil c_J \cdot \log(2SAHT/\delta) \rceil$, $\kappa = 2\beta^*(\delta, T)$, $r_0 = 2$, and $n_0 = \lceil (c_0 + 1 + \log_{17/16}(T)) \cdot \kappa \rceil$, where $c_0$ is defined in (5) and $c_J$ is defined in (6). Then $\mathbb{P}(\mathcal{E}^{\text{opt}} \mid \mathcal{E}^*(\delta)) \ge 1 - \delta/2$.
### D.4 Regret Bound

Let us define the main event $G'(\delta) = G(\delta) \cap \mathcal{E}^{\text{opt}}$. On this event we have the following corollary that connects RandQL with OptQL with Hoeffding bonuses.

Define the following quantity

$$ \beta^{\max}(\delta) = \max\{\kappa, n_0/\kappa, \beta^B(\delta), \beta^{\text{conc}}(\delta), \beta(\delta), \log(T + n_0)\} = \mathcal{O}(\log(SATH/\delta)). $$

**Corollary 1.** Assume conditions of Proposition 3 hold. Let $t \in [T]$, $h \in [H]$, $(s, a) \in \mathcal{S} \times \mathcal{A}$. Define $k = k_h^t(s, a)$ and let $\ell^1 < \dots < \ell^{e_k}$ be a excursions of $(s, a, h)$ until the previous stage. Then on the event $G'(\delta)$ the following bound holds for $k \ge 0$

$$ 0 \le \bar{Q}_h^t(s, a) - Q_h^*(s, a) \le \frac{1}{n} \sum_{i=1}^n [\bar{V}_{h+1}^{\ell^i}(s_{h+1}^{\ell^i}) - V_{h+1}^*(s_{h+1}^{\ell^i})] + \mathcal{B}_h^t(k), $$

where

$$ \mathcal{B}_h^t(k) = 61e^2 \frac{r_0 H(\beta^{\max}(\delta))}{\sqrt{e_k}} + 1201e \frac{r_0 H(\beta^{\max}(\delta))^4}{e_k}. $$

*Proof.* The lower bound follows from the definition of the event $\mathcal{E}^{\text{opt}}$. For the upper bound we first apply the decomposition for $\bar{Q}_h^t(s, a)$ and the definition of event $\mathcal{E}^B(\delta)$ from Lemma 4

$$ \begin{aligned} \bar{Q}_h^t(s, a) &= r_h(s, a) + \max_{j \in [J]} \left\{ \sum_{i=0}^{e_k} W_{j, e_k}^i \bar{V}_{h+1}^{\ell^i}(s_{h+1}^{\ell^i}) \right\} \\ &\le r_h(s, a) + \frac{1}{e_k + n_0} \sum_{i=1}^{e_k} \bar{V}_{h+1}^{\ell^i}(s_{h+1}^{\ell^i}) + \frac{n_0 \kappa \cdot r_0 H}{e_k + n_0} + 60e^2 \sqrt{\frac{r_0^2 H^2 \kappa \beta^B(\delta)}{e_k + n_0}} \\ &\quad + 1200e \frac{r_0 H \kappa \log(e_k + n_0)(\beta^B(\delta))^2}{e_k + n_0}. \end{aligned} $$

Then, by Bellman equations,

$$ \begin{aligned} \bar{Q}_h^t(s, a) - Q_h^*(s, a) \le \frac{1}{e_k} \sum_{i=1}^{e_k} \left[ \bar{V}_{h+1}^{\ell^i} - V_{h+1}^* \right] (s_{h+1}^{\ell^i}) + \frac{1}{e_k} \sum_{i=1}^{e_k} \left[ V_{h+1}^*(s_{h+1}^{\ell^i}) - p_h V_{h+1}^*(s, a) \right] \\ + (1200e + 1) \frac{r_0 H (\beta^{\max}(\delta))^4}{e_k + n_0} + 60e^2 \cdot \frac{r_0 H \beta^{\max}(\delta)}{\sqrt{e_k + n_0}} \end{aligned} $$

By the definition of event $\mathcal{E}^{\text{conc}}(\delta)$ we conclude the statement. $\square$

Let us define $\delta_h^t = \bar{V}_h^t(s_h^t) - V_h^{\pi^t}(s_h^t)$ and $\zeta_h^t = \bar{V}_h^t(s_h^t) - V_h^{\star}(s_h^t)$.

**Lemma 5.** Assume conditions of Proposition 3 hold. Then on event $G'(\delta) = G(\delta) \cap \mathcal{E}^{\text{opt}}$, where $G(\delta)$ is defined in Lemma 4, the following upper bound on regret holds

$$ \mathfrak{R}^T \le eH \sum_{t=1}^{T} \sum_{h=1}^{H} \left\{ k_h^t(s_h^t, a_h^t) = -1 \right\} + \sum_{t=1}^{T} \sum_{h=1}^{H} \left(1 + 1/H\right)^{H-h} \xi_h^t + e \sum_{t=1}^{T} \sum_{h=1}^{H} \mathcal{B}_h^t, $$

where $\xi_h^t = p_h[V_{h+1}^* - V_{h+1}^{\pi^t}](s_h^t, a_h^t) - [V_{h+1}^* - V_{h+1}^{\pi^t}](s_{h+1}^t)$ and $\mathcal{B}_h^t = \mathcal{B}_h^t(s_h^t, a_h^t) \cdot 1\{k_h^t(s_h^t, a_h^t) \ge 0\}$ for $\mathcal{B}_h^t$ defined in Corollary 1.

*Proof.* We notice that on the event $\mathcal{E}^{\text{opt}}$ the following upper bound holds

$$ \mathfrak{R}^T \le \sum_{t=1}^{T} \delta_t^t. \qquad (8) $$
Next we analyze $\delta_h^t$. By the choice of $a_h^t = \arg\max_{a\in A} \bar{Q}_h^t(s_h^t, a)$, Corollary 1, and Bellman equations, we have

$$ 
\begin{aligned}
\delta_h^t &= \bar{V}_h^t(s_h^t) - V_h^{\pi^t}(s_h^t) = \bar{Q}_h^t(s_h^t, a_h^t) - Q_h^{\pi^t}(s_h^t, a_h^t) \\
&= \bar{Q}_h^t(s_h^t, a_h^t) - Q_h^*(s_h^t, a_h^t) + Q_h^*(s_h^t, a_h^t) - Q_h^{\pi^t}(s_h^t, a_h^t) \\
&\le H1\{N_h^t = 0\} + 1\{N_h^t > 0\} \left( \frac{1}{N_h^t} \sum_{i=1}^{N_h^t} \zeta_{h+1}^{\ell_{t,h}^i} + \mathcal{B}_h^t(s_h^t, a_h^t) + p_h[V_{h+1}^* - V_{h+1}^{\pi^t}](s_h^t, a_h^t) \right).
\end{aligned}
$$

where $k_h^t = k_h^t(s_h^t, a_h^t)$, $N_h^t = e_{k_h^t}$, $\ell_{t,h}^i$ is episode of the i-th visitation of the state-action pair $(s_h^t, a_h^t)$ during the stage $k_h^t$, and additionally by the convention $0/0 = 0$. Let $\xi_h^t = p_h[V_{h+1}^* - V_{h+1}^{\pi^t}](s_h^t, a_h^t) - [V_{h+1}^* - V_{h+1}^{\pi^t}](s_h^t, a_h^t)$ be a martingale-difference sequence, and $\mathcal{B}_h^t = \mathcal{B}_h^t(s_h^t, a_h^t)1\{N_h^t > 0\}$ then

$$ \delta_h^t \le H1\{N_h^t = 0\} + \frac{1\{N_h^t > 0\}}{N_h^t} \sum_{i=1}^{N_h^t} \zeta_{h+1}^{\ell_{t,h}^i} - \delta_{h+1}^t + \delta_{h+1}^t + \xi_h^t + \mathcal{B}_h^t. $$

and, as a result

$$ 
\begin{aligned}
\sum_{t=1}^{T} \delta_h^t \le H \sum_{t=1}^{T} 1\{N_h^t = 0\} &+ \sum_{t=1}^{T} \frac{1\{N_h^t > 0\}}{N_h^t} \sum_{i=1}^{N_h^t} \zeta_{h+1}^{\ell_{t,h}^i} \\
& - \sum_{t=1}^{T} \zeta_{h+1}^t + \sum_{t=1}^{T} \delta_{h+1}^t + \sum_{t=1}^{T} \xi_h^t + \sum_{t=1}^{T} \mathcal{B}_h^t.
\end{aligned}
$$

Next we have to analyze the second term, following the approach by Zhang et al. [2020],

$$ 
\begin{aligned}
\sum_{t=1}^{T} \frac{1\{N_h^t > 0\}}{N_h^t} \sum_{i=1}^{N_h^t} \zeta_{h+1}^{\ell_{t,h}^i} &= \sum_{q=1}^{T} \sum_{t=1}^{T} \frac{1\{N_h^t > 0\}}{N_h^t} \sum_{i=1}^{N_h^t} \zeta_{h+1}^{\ell_{t,h}^i} 1\{\ell_{t,h}^i = q\} \\
&= \sum_{q=1}^{T} \zeta_{h+1}^q \cdot \sum_{t=1}^{T} \frac{1\{k_h^t \ge 0\}}{N_h^t} \sum_{i=1}^{N_h^t} 1\{\ell_{t,h}^i = q\}.
\end{aligned}
$$

Notice that $\sum_{i=1}^{N_h^t} 1\{\ell_{t,h}^i = q\} \le 1$ since all visitations are increasing in $i$, and, moreover, it turns to equality if and only if $(s_h^q, a_h^q) = (s_h^t, a_h^t)$ and this visitation happens in stage $k_h^t$, where $k_h^t$ is equal to the stage of episode $q$ with respect to $(s_h^q, a_h^q, h)$. Since the sum is over all the next episodes with respect to stage of $q$, we have that the number of non-zero elements in the sum over $t$ is bounded by $(1 + 1/H)N_h^t$. Thus

$$ \sum_{q=1}^{T} \zeta_{h+1}^{q} \cdot \sum_{t=1}^{T} \frac{1\{k_h^t \ge 0\}}{N_h^t} \sum_{i=1}^{N_h^t} 1\{\ell_{t,h}^i = q\} \le \left(1 + \frac{1}{H}\right) \sum_{q=1}^{T} \zeta_{h+1}^{q}. $$

After a simple algebraic manipulations and using the fact that $\zeta_h^t \le \delta_h^t$,

$$ 
\begin{aligned}
\sum_{t=1}^{T} \delta_h^t &\le H \sum_{t=1}^{T} 1\{N_h^t = 0\} + \sum_{t=1}^{T} (1 + 1/H)\zeta_{h+1}^t - \sum_{t=1}^{T} \zeta_{h+1}^t + \sum_{t=1}^{T} \delta_{h+1}^t + \sum_{t=1}^{T} \xi_h^t + \sum_{t=1}^{T} \mathcal{B}_h^t \\
&\le H \sum_{t=1}^{T} 1\{N_h^t = 0\} + \left(1 + \frac{1}{H}\right) \sum_{t=1}^{T} \delta_{h+1}^t + \sum_{t=1}^{T} \xi_h^t + \sum_{t=1}^{T} \mathcal{B}_h^t.
\end{aligned}
$$

By rolling out the upper bound on regret (8) and using inequality $(1 + 1/H)^{H-h} \le e$ we have

$$ \mathfrak{R}^T \le eH \sum_{t=1}^{T} \sum_{h=1}^{H} 1\{N_h^t = 0\} + \sum_{t=1}^{T} \sum_{h=1}^{H} (1 + 1/H)^{H-h} \xi_h^t + e \sum_{t=1}^{T} \sum_{h=1}^{H} \mathcal{B}_h^t. $$

□
Proof of Theorem 1. First, we notice that the event $G'(\delta)$ defined in Lemma 5, holds with probability at least $1 - \delta$ by Lemma 4 and Proposition 3. Thus, we may assume that $G'(\delta)$ holds.

We start from the decomposition given by Lemma 5

$$ \mathfrak{R}^T \le eH \sum_{t=1}^{T} \sum_{h=1}^{H} \mathbb{1}\{k_h^t(s_h^t, a_h^t) = -1\} + \sum_{t=1}^{T} \sum_{h=1}^{H} (1+1/H)^{H-h} \xi_h^t + e \sum_{t=1}^{T} \sum_{h=1}^{H} \mathcal{B}_h^t $$

The first term is upper bounded by eSAH³, since there is no more than H visits of each state-action-step triple before the update for the first stage. The second term is bounded by $\tilde{O}(\sqrt{H^3T})$ by a definition of the event $\mathcal{E}(\delta)$ in Lemma 4. To upper bound the last term we have to analyze the following sum

$$ \sum_{t=1}^{T} \sum_{h=1}^{H} \frac{\mathbb{1}\{e_{k_h^t}(s_h^t, a_h^t) > 0\}}{\sqrt{e_{k_h^t}(s_h^t, a_h^t)}} \le \sum_{(s,a,h) \in \mathcal{S} \times \mathcal{A} \times [H]} \sum_{k=0}^{k_h^{T+1}(s,a)} \frac{e_{k+1}}{\sqrt{e_k}}, $$

where

$$ e_k = \left\lfloor \left(1 + \frac{1}{H}\right)^k H \right\rfloor \Rightarrow \frac{e_{k+1}}{\sqrt{e_k}} \le 2\sqrt{e_k}, $$

therefore by Cauchy inequality

$$ \sum_{k=0}^{k_h^{T+1}(s,a)} \frac{e_{k+1}}{\sqrt{e_k}} \le 2 \sum_{k=0}^{k_h^{T+1}(s,a)} \sqrt{e_k} \le 2 \sqrt{k_h^{T+1}(s,a)} \sqrt{\sum_{k=0}^{k_h^{T+1}(s,a)} e_k} \le 2 \sqrt{\frac{\log(T)}{\log(1+1/H)}} \sqrt{n_h^{T+1}(s,a)}, $$

where we used the definition of the previous stage $k_h^{T+1}(s,a)$

$$ N_h^{T+1}(s, a) \ge \sum_{k=0}^{k_h^{T+1}(s, a)} e^k, $$

thus by Cauchy inequality and inequality $\log(1 + 1/H) \ge 1/(4H)$ for $H \ge 1$

$$ \begin{aligned} \sum_{t=1}^{T} \sum_{h=1}^{H} \frac{\mathbb{1}\{e_{k_h^t}(s_h^t, a_h^t) > 0\}}{\sqrt{e_{k_h^t}(s_h^t, a_h^t)}} &\le 2\sqrt{H \log(T)} \sum_{(s,a,h) \in \mathcal{S} \times \mathcal{A} \times [H]} \sqrt{N_h^{T+1}(s,a) + 1} \\ &\le 4\sqrt{SAH^2 \log(T)} \sqrt{\sum_{(s,a,h)} (N_h^{T+1}(s,a) + 1)} \\ &\le 4\sqrt{SAH^3 T \log(T)} + 4SAH^2 \log(T). \end{aligned} $$

Using this upper bound, we have

$$ \sum_{t=1}^{T} \sum_{h=1}^{H} \mathcal{B}_h^t = \tilde{\mathcal{O}} \left( H \sum_{t=1}^{T} \sum_{h=1}^{H} \frac{\mathbb{1}\{e_{k_h^t}(s_h^t, a_h^t) > 0\}}{\sqrt{e_{k_h^t}(s_h^t, a_h^t)}} \right) = \tilde{\mathcal{O}} \left( \sqrt{H^5 SAT} + SAH^3 \right). $$

Combining this upper bound with the previous ones, we conclude the statement. $\square$
# E Proofs for Metric algorithm

## E.1 Assumptions

In this section we proof Lemma 2 and Lemma 1.

*Proof of Lemma 1.* By the dual formula for 1-Wasserstein distance (see e.g. Section 6 of Peyré and Cuturi [2019]) we have

$$W_1(p_h(s, a), p_h(s', a')) = \sup_{f \text{ is 1-Lipchitz}} \{p_h f(s, a) - p_h f(s', a')\}.$$

By Assumption 2 we have

$$p_h f(s, a) - p_h f(s', a') = \mathbb{E}_{\xi_h} [f(F_h(s, a, \xi_h)) - f(F_h(s', a', \xi_h))] \le L_F \rho((s, a), (s', a')).$$

□

*Proof of Lemma 2.* Let us proceed by a backward induction over $h$. For $h = H + 1$ we have $Q_{H+1}^*(s, a) = V_{H+1}^*(s) = 0$, therefore they are 0-Lipchitz.

Next we assume that have for any $h' > h$ the statement of Lemma 2 holds. Then by Bellman equations

$$|Q_h^*(s, a) - Q_h^*(s', a')| \le |r_h(s, a) + r_h(s', a')| + |p_h V_{h+1}^*(s, a) - p_h V_{h+1}^*(s', a')|.$$

By Assumption 2 we can represent the action of the transition kernel as follows

$$p_h V_{h+1}^*(s, a) - p_h V_{h+1}^*(s', a') = \mathbb{E}_{\xi_h} [V_{h+1}^*(F_h(s, a, \xi_h)) - V_{h+1}^*(F_h(s', a', \xi_h))].$$

Since by induction hypothesis $V_{h+1}^*$ is $\sum_{h'=h+1}^H L_F^{h'-h} L_r$-Lipschitz and $F_h(\cdot, \xi_h)$ is $L_F$-Lipschitz, therefore

$$\begin{aligned} |Q_h^*(s, a) - Q_h^*(s', a')| &\le \left( L_r + L_F \cdot \sum_{h'=h+1}^H L_F^{h'-h} L_r \right) \rho((s, a), (s', a')) \\ &\le \left( \sum_{h'=h}^H L_F^{h'-h} L_r \right) \rho((s, a), (s', a')) \end{aligned}$$

To show that $V_h^*$ is also Lipschitz, we have that there is some action $a^*$ equal to $\pi^*(s)$ or $\pi^*(s')$, such that

$$|V_h^*(s) - V_h^*(s')| \le |Q_h^*(s, a^*) - Q_h^*(s', a^*)| \le L_{V,h} \cdot \rho((s, a^*), (s', a^*)) \le L_{V,h} \cdot \rho_S(s, s'),$$

where in the end we used the sub-additivity assumption on metric over joint space (see Assumption 1).

□

## E.2 Algorithm

Next we describe a simple non-adaptive version of our algorithm that works with metric spaces. We assume that for any $\varepsilon > 0$ we can compute a minimal $\varepsilon$-cover of state-action space $N_\varepsilon$.<fnref n="5" />

Next we will use the same notation but with state-action pairs replaces with balls from a fixed cover $N_\varepsilon$. To unify the notation, we define $\psi_\varepsilon: S \times A \to N_\varepsilon$ that maps any point $(s, a)$ to any ball from $\varepsilon$-cover that contains it.

For any $t, h$ we define $B_h^t = \psi_\varepsilon(s_h^t, a_h^t)$. Next, let $n_h^t(B)$ be a number of visits of ball $B$ before the episode $t$: $n_h^t(B) = \sum_{k=1}^{t-1} 1\{B_h^k = B\}$.

Let $e_k = \lfloor(1+1/H)^k \cdot H \rfloor$ be length of each stage for any $k \ge 0$ and, by convention, $e_{-1} = 0$. We will call that in the beginning of episode $t$ a pair $(B, h)$ is in $k$-th stage if $n_h^t(B) \in [\sum_{i=0}^{k-1} e_i, \sum_{i=0}^k e_i)$.

<footnote n="5">⁵Remark that the greedy algorithm can easily generate $\varepsilon$-cover of size $N_\varepsilon/2$, that will not affect the asymptotic behavior of regret bounds, see Song and Sun [2019].</footnote>
**Algorithm 4 Metric Net-Staged-RandQL**

1: **Input:** inflation coefficient $\kappa$, $J$ ensemble size, number of prior transitions $n_0(k)$, prior reward $r_0$, dicretization level $\varepsilon$.

2: **Initialize:** $\varepsilon$-net $\mathcal{N}_\varepsilon$, $\overline{Q}_h(B) = \tilde{Q}_h^j(B) = r_0H$, initialize counters $\tilde{n}_h(B) = 0$ for $j, h, B \in [J] \times [H] \times \mathcal{N}_\varepsilon$, stage $q_h(B) = 0$, quantization map $\psi_\varepsilon: S \times A \to \mathcal{N}_\varepsilon$.

3: **for** $t \in [T]$ **do**

4: **for** $h \in [H]$ **do**

5: Play $a_h \in \arg \max_a \overline{Q}_h(\psi_\varepsilon(s_h, a))$ and define $B_h = \psi_\varepsilon(s_h, a_h)$.

6: Observe reward and next state $s_{h+1} \sim p_h(s_h, a_h)$.

7: Sample learning rates $w_j \sim \text{Beta}(1/\kappa, (\tilde{n} + n_0(q_h(B_h))/\kappa)$ for $\tilde{n} = \tilde{n}_h(B_h)$.

8: Compute value function $\overline{V}_{h+1}(s_{h+1}) = \max_{a \in A} \overline{Q}_{h+1}(\psi_\varepsilon(s_{h+1}, a))$.

9: Update temporary Q-values for all $j \in [J]$

$$ \tilde{Q}_h^j(B) := (1 - w_j) \tilde{Q}_h^j(B) + w_j (r_h(s_h, a_h) + \overline{V}_{h+1}(s_{h+1})). $$

10: Update counter $\tilde{n}_h(B_h) := \tilde{n}_h(B_h) + 1$

11: **if** $\tilde{n}_h(B_h) = \lfloor (1 + 1/H)^q H \rfloor$ for $q = q_h(B_h)$ is the current stage **then**

12: Update policy Q-values $\overline{Q}_h(B_h) := \max_{j \in [J]} \tilde{Q}_h^j(B_h)$.

13: Reset temporary Q-values $\tilde{Q}_h^j(B_h) := r_0H$.

14: Reset counter $\tilde{n}_h(B_h) := 0$ and change stage $k_h(B_h) := k_h(B_h) + 1$.

15: **end if**

16: **end for**

17: **end for**

Let $\tilde{n}_h^t(B)$ be a number of visits of state-action pair during the current stage in the beginning of episode $t$. Formally, $\tilde{n}_h^t(B) = n_h^t(B) - \sum_{i=0}^{k-1} e_i$, where $k$ is an index of current stage.

Define $\kappa > 0$ be a posterior inflation coefficient, $n_0$ is a number of pseudo-transitions, and $J$ as a number of temporary Q-functions. Let $\tilde{Q}_h^{t,j}$ be a $j$-th temporary Q-value and $\overline{Q}_h^t$ be a policy Q-value at the beginning of episode $t$, defined over the $\varepsilon$-cover. We initialize them as follows

$$ \overline{Q}_h^1(B) = r_0H, \quad \tilde{Q}_h^{1,j}(s, a) = r_0H. $$

Additionally, we define to the value function as follows

$$ \overline{V}_h^t(s) = \max_{a \in A} \overline{Q}_h^t(\psi_\varepsilon(s, a)). $$

Notice that we cannot precompute it as in the tabular setting, however, it is possible to use its values in lazy fashion.

For each transition we preform the following update of temporary Q-values over balls $B \in \mathcal{N}_\varepsilon$

$$ \tilde{Q}_h^{t+1/2,j}(B) = \begin{cases} (1 - w_{j,\tilde{n}}) \cdot \tilde{Q}_h^{t,j}(B) + w_{j,\tilde{n}}[r_h(s_h^t, a_h^t) + \overline{V}_{h+1}^t(s_{h+1}^t)], & B = B_h^t \\ \tilde{Q}_h^{t,j}(B) & \text{otherwise,} \end{cases} $$

where $\tilde{n} = \tilde{n}_h^t(B)$ is the number of visits of $(B, h)$ in the beginning of episode $t$, and $w_{j,\tilde{n}}$ is a sequence of independent beta-distribution random variables $w_{j,\tilde{n}} \sim \text{Beta}(1/\kappa, (\tilde{n} + n_0)/\kappa)$.

Next we define the stage update as follows

$$ \overline{Q}_h^{t+1}(B) = \begin{cases} \max_{j \in [J]} \tilde{Q}_h^{t+1/2,j}(B) & \tilde{n}_h^t(B) = \lfloor (1 + 1/H)^k H \rfloor \\ \overline{Q}_h^t(B) & \text{otherwise} \end{cases} $$

$$ \tilde{Q}_h^{t+1,j}(B) = \begin{cases} r_0H & n_h^t(B) \in \tilde{n}_h^t(B) = \lfloor (1 + 1/H)^k H \rfloor \\ \tilde{Q}_h^{t+1/2,j}(B) & \text{otherwise} \end{cases} $$

$$ \overline{V}_h^{t+1}(s) = \min\{r_0(H - h), \max_{a \in A} \overline{Q}_h^{t+1}(\psi_\varepsilon(s, a))\}; $$

$$ \pi_h^{t+1}(s) \in \arg \max_{a \in A} \overline{Q}_h^{t+1}(\psi_\varepsilon(s, a)), $$
where k is the current stage. A detailed description of the algorithm is presented in Algorithm 4.

For episode t we will call $k_h^t(B)$ the index of stage where $\overline{Q}_h^t(B)$ were updated (and $k_h^t(B) = -1$ if there was no update). For all t we define $\tau_h^t(B) \le t$ as the episode when the stage update happens. In other words, for any t the following holds

$$ \overline{Q}_h^{t+1}(B) = \max_{j \in [J]} \tilde{Q}_h^{\tau_h^t(B)+1/2, j}(B), $$

where $\tau_h^t(B) = 0$ and $e_k = 0$ if there was no updates. To simplify the notation we will omit dependence on $(s, a, h)$ where it is deducible from the context.

We notice that in this case we use $e_k$ samples to compute $\tilde{Q}_h^{\tau_h^t(B)+1/2, j}$ for $k = k_h^t(s, a)$. For this $k$ we define $\ell_{k,h}^i(s, a)$ as the time of $i$-th visit of state-action pair $(s, a)$ during $k$-th stage. Then we have the following decomposition

$$ \tilde{Q}_h^{\tau^t+1/2, j}(B) = \sum_{i=0}^{e_k} W_{j, e_k}^i \left( r_h(s_h^{\ell^i}, a_h^{\ell^i}) + \bar{V}_{h+1}^{\ell^i}(s_{h+1}^{\ell^i}) \right), \quad (9) $$

where we drop dependence on $k$ and $(B, h)$ in $\ell^i$ to simplify notations, using the convention $r_h(s_h^{\ell^0}, a_h^{\ell^0}) = r_0, \bar{V}_{h+1}^{\ell^0}(s_{h+1}^{\ell^0}) = r_0(H-1)$ and the following aggregated weights

$$ W_{j,n}^0 = \prod_{q=0}^{n-1} (1 - w_{j,q}), \quad W_{j,n}^i = w_{j,i-1} \cdot \prod_{q=i}^{n-1} (1 - w_{j,q}), \quad i \ge 1. $$

## E.3 Concentration

Let $\beta^*: (0, 1) \times \mathbb{N} \times (0, d_{\max}) \to \mathbb{R}_+$ and $\beta^B, \beta^{\text{conc}}, \beta: (0, 1) \times (0, d_{\max}) \to \mathbb{R}_+$ be some function defined later on in Lemma 6. We define the following favorable events

$$ \mathcal{E}^*(\delta, \varepsilon) \triangleq \left\{ \forall t \in \mathbb{N}, \forall h \in [H], \forall B \in \mathcal{N}_\varepsilon, k = k_h^t(B), (s, a) = \text{center}(B) : \right. \\ \left. \qquad \mathcal{K}_{\inf}\left(\frac{1}{e_k} \sum_{i=1}^{e_k} \delta_{V_{h+1}^*(F_h(s,a,\xi_{h+1}^{\ell^i}))}, p_h V_{h+1}^*(s, a)\right) \le \frac{\beta^*(\delta, e_k, \varepsilon)}{e_k} \right\}, $$

$$ \mathcal{E}^B(\delta, \varepsilon) \triangleq \left\{ \forall t \in [T], \forall h \in [H], \forall B \in \mathcal{N}_\varepsilon, \forall j \in [J], k = k_h^t(B) : \right. \\ \left. \qquad \left| \sum_{i=0}^{e_k} (W_{j,e_k,k}^i - \mathbb{E}[W_{j,e_k,k}^i]) \left( r_h(s_h^{\ell^i}, a_h^{\ell^i}) + \bar{V}_{h+1}^{\ell^i}(s_{h+1}^{\ell^i}) \right) \right| \le 60e^2 \sqrt{\frac{r_0^2 H^2 \kappa \beta^B(\delta, \varepsilon)}{e_k + n_0(k)}} + 1200e \frac{r_0 H \kappa \log(e_k + n_0(k)) (\beta^B(\delta, \varepsilon))^2}{e_k + n_0(k)} \right\}, $$

$$ \mathcal{E}^{\text{conc}}(\delta, \varepsilon) \triangleq \left\{ \forall t \in [T], \forall h \in [H], \forall B \in \mathcal{N}_\varepsilon, k = k_h^t(B) : \left| \frac{1}{e_k} \sum_{i=1}^{e_k} V_{h+1}^*(s_{h+1}^{\ell_{k,h}^i}(B)) - p_h V_{h+1}^*(s_h^{\ell_{k,h}^i}(B), a_h^{\ell_{k,h}^i}(B)) \right| \le \sqrt{\frac{2r_0^2 H^2 \beta^{\text{conc}}(\delta, \varepsilon)}{e_k}} \right\} $$

$$ \mathcal{E}(\delta) \triangleq \left\{ \sum_{t=1}^{T} \sum_{h=1}^{H} (1 + 1/H)^{H-h} \left| p_h \left[ V_{h+1}^{\star} - V_{h+1}^{\pi_t} \right] (s_h^t, a_h^t) - \left[ V_{h+1}^{\star} - V_{h+1}^{\pi_t} \right] (s_{h+1}^t) \right| \le 2er_0H \sqrt{2HT\beta(\delta)}. \right\}. $$
We also introduce the intersection of these events, $G(\delta) \triangleq \mathcal{E}^*(\delta) \cap \mathcal{E}^B(\delta) \cap \mathcal{E}^{\text{conc}}(\delta) \cap \mathcal{E}(\delta)$. We prove that for the right choice of the functions $\beta^*, \beta^{\text{KL}}, \beta^{\text{conc}}, \beta, \beta^{\text{Var}}$ the above events hold with high probability.

**Lemma 6.** For any $\delta \in (0, 1)$ and $\varepsilon \in (0, d_{\text{max}})$ and for the following choices of functions $\beta$,

$$ 
\begin{aligned}
\beta^*(\delta, n, \varepsilon) &\triangleq \log(8H/\delta) + \log(N_\varepsilon) + 3\log(e\pi(2n+1)), \\
\beta^B(\delta, \varepsilon) &\triangleq \log(8H/\delta) + \log(N_\varepsilon) + \log(TJ), \\
\beta^{\text{conc}}(\delta, \varepsilon) &\triangleq \log(8H/\delta) + \log(N_\varepsilon) + \log(2T), \\
\beta(\delta) &\triangleq \log(16/\delta),
\end{aligned}
$$

it holds that

$$ 
\begin{aligned}
\mathbb{P}[\mathcal{E}^*(\delta, \varepsilon)] \ge 1 - \delta/8, &\qquad \mathbb{P}[\mathcal{E}^B(\delta, \varepsilon)] \ge 1 - \delta/8, \\
\mathbb{P}[\mathcal{E}^{\text{conc}}(\delta, \varepsilon)] \ge 1 - \delta/8, &\qquad \mathbb{P}[\mathcal{E}(\delta)] \ge 1 - \delta/8.
\end{aligned}
$$

In particular, $\mathbb{P}[\mathcal{G}(\delta)] \ge 1 - \delta/2$.

*Proof.* Let us describe the changes from the similar statement in Lemma 4.

Regarding event $\mathcal{E}^*(\delta, \varepsilon)$, for any fixed ball $B$ we have exactly the same structure of the problem thanks to Assumption 2 and a sequence of i.i.d. random variables $\xi_h^{\ell_i}$. Thus, Theorem 4 combined with a union bound over $B \in \mathcal{N}_\varepsilon$ and $H \in [H]$ concludes $\mathbb{P}(\mathcal{E}^*(\delta, \varepsilon)) \ge 1 - \delta/8$.

The proof for the event $\mathcal{E}^B(\delta, \varepsilon)$ remains the almost the same, with two differences: the predictable weights slightly changed but the upper bound for them remain the same, and we have taken a union bound not over all state-action pairs $(s, a) \in S \times A$ but all over balls $B \in \mathcal{N}_\varepsilon$.

To show that $\mathbb{P}(\mathcal{E}^{\text{conc}}(\delta, \varepsilon)) \ge 1 - \delta/8$, let us fix $B \in \mathcal{N}_\varepsilon$, $h \in [H]$ and $e_k \in [T]$. Then we can define a filtration $\mathcal{F}_{t,h} = \sigma\{(s_{h'}, a_{h'}^t, \pi^t), \ell < t, h' \in [H]\} \cup \{(s_h^t, a_h^t, \pi^t), h' \le h\}$ and, since $\ell_{k,h}^i(B)$ are stopping times for all $i = 1, \dots, e_k$, we can define the stopped filtration $\tilde{\mathcal{F}}_i = \mathcal{F}_{\ell_{k,h}^i}$.

Then we notice that $X_i = V_{h+1}^*(s_{h+1}^{\ell_{k,h}^i(B)}) - p_h V_{h+1}^*(s_h^{\ell_{k,h}^i(B)}, a_h^{\ell_{k,h}^i(B)})$ forms a martingale-difference sequence with respect to $\tilde{\mathcal{F}}_{i,h}$. Thus, by Azuma-Hoeffding inequality and a union bound we have $\mathbb{P}(\mathcal{E}^{\text{conc}}(\delta, \varepsilon)) \ge 1 - \delta/8$.

The proof of $\mathbb{P}(\mathcal{E}(\delta)) \ge 1 - \delta/8$ remains exactly the same as in Lemma 4. $\square$

## E.4 Optimism

In this section we prove that our estimate of $Q$-function $\overline{Q}_h^t(s, a)$ is optimistic that is the event

$$ \mathcal{E}_{\text{opt}}(\varepsilon) \triangleq \{\forall t \in [T], h \in [H], (s, a) \in S \times A : \overline{Q}_h^t(\psi_\varepsilon(s, a)) \ge Q_h^*(s, a)\}. \quad (10) $$

holds with high probability on the event $\mathcal{E}^*(\delta, \varepsilon)$.

Define constants

$$ c_0 \triangleq \frac{8}{\pi} \left( \frac{4}{\sqrt{\log(17/16)}} + 8 + \frac{49 \cdot 4\sqrt{6}}{9} \right)^2 + 1. \quad (11) $$

and slightly another constant

$$ \tilde{c}_J \triangleq \frac{1}{\log\left(\frac{4}{3+\Phi(1)}\right)}, \quad (12) $$

where $\Phi(\cdot)$ is a CDF of a normal distribution.

**Proposition 4.** Define a constant $L = L_r + L_V(1 + L_F)$. Assume that $J = \lceil \tilde{c}_J \cdot (\log(2HT/\delta) + \log(N_\varepsilon)) \rceil$, $\kappa = 2\beta^*(\delta, T, \varepsilon)$, $r_0 = 2$, and a prior count $n_0(k) = \lceil \tilde{n}_0 + \kappa + \frac{\varepsilon L}{H-1} \cdot (e_k + \tilde{n}_0 + \kappa) \rceil$ dependent on the stage $k$, where $\tilde{n}_0 = (c_0 + 1 + \log_{17/16}(T)) \cdot \kappa$.
Then on event $\mathcal{E}^*(\delta, \varepsilon)$ the following event

$$ \mathcal{E}_{\text{anticonc}} \triangleq \left\{ \begin{array}{l} \forall t \in [T] \ \forall h \in [H] \ \forall B \in \mathcal{N}_{\varepsilon} : \text{for } k = k_h^t(B), (s, a) = \text{center}(B): \\ \max_{j \in [J]} \left\{ W_{j,e_k,k}^0 r_0(H-1) + \sum_{i=1}^{e_k} W_{j,e_k,k}^i V_{h+1}^*(F_h(s, a, \xi_h^{\ell_i})) \right\} \ge p_h V_{h+1}^*(s, a) + L\varepsilon \end{array} \right\} $$

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

**Remark 1.** We notice that the obtained result is connected to the theory of Dirichlet processes.

First, let us define the Dirichlet process, following Ferguson [1973]. The stochastic process G, indexed by elements B of X, is a Dirichlet Process with parameter $\nu$ ($G \sim \text{DP}(\nu)$) if

$$ G(B_1), \dots, G(B_d) \sim \text{Dir}(\nu(B_1), \dots, \nu(B_d)), $$

for any measurable partition $(B_1, \dots, B_d)$ of X.

Let $\tilde{P}_n = \frac{1}{n} \sum_{i=1}^n \delta_{Z_i}$ be an empirical measure of an i.i.d. sample $Z_1, \dots, Z_n \sim P$. Let $\nu$ be a finite (not necessarily probability) measure on X and $\tilde{P}_n \sim \text{DP}(\nu + n\tilde{P}_n)$. Then we have the following representation for the expectations of a function $f: X \to \mathbb{R}$ over a sampled measure $\tilde{P}_n$ (see Theorem 14.37 of Ghosal and Van der Vaart [2017] with $\sigma = 0$ for a proof)

$$ \tilde{P}_n f = V_n \cdot Qf + (1 - V_n) \sum_{i=1}^{n} W_i f(Z_i), $$

where $V_n \sim \text{Beta}(|\nu|, n)$, $Q \sim \text{DP}(\nu)$, and a vector $(W_1, \dots, W_n)$ follows uniform Dirichlet distribution Dir$(1, \dots, 1)$. If we take $\nu = n_0 \cdot \delta_{Z_0}$ for some $Z_0 \in X$ such that $f(Z_0) = r_0(H-1)^6$, then by a stick-breaking process representation of the Dirichlet distribution we have

$$ \tilde{P}_n f = \tilde{W}_0 r_0(H-1) + \sum_{i=1}^{n} \tilde{W}_1 f(Z_i), \quad (\tilde{W}_0, \dots, \tilde{W}_1) \sim \text{Dir}(n_0, 1, \dots, 1). $$

By taking an appropriate X and f we have that Proposition 4 could be interpret as a deriving a lower bound on the probability of $\mathbb{P}[\tilde{P}_n f \ge Pf + \varepsilon L \mid \{Z_i\}_{i=1}^n]$.

*Proof.* First for all, let us fix $t \in [T]$, $h \in [H]$ and $B \in \mathcal{N}_\varepsilon$ and, consequently, $k = k_h^t(B)$. Also, let fix $j \in [J]$. To simplify the notation in the sequel, define $X_0 = r_0(H-1)$ and $X_i = V_{h+1}^*(F_h(s, a, \xi_h^{\ell_i}))$ for $i > 0$. Notice that $X_i$ for $i > 0$ is a sequence of i.i.d. random variables supported on $[0, H-h-1]$.

By Lemma 3 we have $(W_{j,e_k,k}^0, \dots, W_{j,e_k,k}^{e_k}) \sim \text{Dir}(n_0(k)/\kappa, 1/\kappa, \dots, 1/\kappa)$. Then we use the aggregation property of Dirichlet distribution: there is a vector $(\tilde{W}_j^{-1}, \dots, \tilde{W}_j^{e_k}) \sim \text{Dir}((n_0(k) - \tilde{n}_0)/\kappa, \tilde{n}_0/\kappa, 1/\kappa, \dots, 1/\kappa)$ such that

$$ \sum_{i=0}^{e_k} W_{j,e_k,k}^i X_i = \tilde{W}_j^{-1} X_0 + \sum_{i=0}^{e_k} \tilde{W}_j^i X_i. $$

Next we are going to represent the Dirichlet random vector $\tilde{W}$ by a stick breaking process (or, equivalently, represent via the generalized Dirichlet distribution)

$$ \begin{array}{l} \tilde{W}_j^{-1} = \xi_j \qquad \xi_j \sim \text{Beta}((n_0(k) - \tilde{n}_0)/\kappa, (\tilde{n}_0 + \tilde{n}_0)/\kappa), \\ (\tilde{W}_j^0, \dots, \tilde{W}_j^{e_k}) = (1 - \xi_j) \cdot (\tilde{W}_j^0, \dots, \tilde{W}_j^{e_k}), \qquad \tilde{W}_j \sim \text{Dir}(\tilde{n}_0/\kappa, 1/\kappa, \dots, 1/\kappa), \end{array} $$

<footnote n="6">⁶We can augment the space X with this additional point if needed</footnote>
where $\xi_j$ and $\hat{W}_j$ are independent. Therefore, we have the final decomposition

$$ \sum_{i=0}^{e_k} W_{j,e_k,k}^i X_i - p_h V_{h+1}^*(s, a) - \varepsilon L = \underbrace{\xi_j (r_0(H-1) - p_h V_{h+1}^*(s, a)) - \varepsilon L}_{T_{\text{approx}}} + (1 - \xi_j) \cdot \underbrace{\left( \sum_{i=0}^{e_k} \hat{W}_j^i X_i - p_h V_{h+1}^*(s, a) \right)}_{T_{\text{stoch}}}. $$

By independence of $\xi_j$ and $\hat{W}_j$ we have

$$ \mathbb{P} \left[ \sum_{i=0}^{e_k} W_{j,e_k,k}^i X_i \geq p_h V_{h+1}^*(s, a) + \varepsilon L \mid \{X_i\}_{i=1}^{e_k} \right] \geq \mathbb{P}[T_{\text{approx}} \geq 0] \cdot \mathbb{P}[T_{\text{stoch}} \geq 0]. $$

We split our problem to lower bound the two separate probabilities.

**Approximation error** To deal with approximation error, we first of all notice that $p_h V_{h+1}^*(s, a) \le H - 1$, therefore we have

$$ \mathbb{P}[T_{\text{approx}} \ge 0] = \mathbb{P}\left[\xi_j \ge \frac{\varepsilon L}{H-1}\right]. $$

Next we assume that $\varepsilon < (H-1)/L$, since $\xi_j \sim \text{Beta}((n_0(k) - \tilde{n}_0)/\kappa, (e_k + \tilde{n}_0)/\kappa)$, we may apply Alfers and Dinges [1984, Theorem 1.2]"

$$ \mathbb{P}[T_{\text{approx}} \ge 0] \ge \Phi\left(-\text{sign}(p-\mu) \cdot \sqrt{2\alpha \text{kl}(p, \mu)}\right), $$

where $p = (n_0(k) - \tilde{n}_0 - \kappa)/(e_k + \tilde{n}_0 - \kappa)$ and $\mu = \varepsilon L/(H-1)$. Since $n_0(k) = [\tilde{n}_0 + \kappa + \frac{\varepsilon L}{H-1} \cdot (e_k + \tilde{n}_0 + \kappa)]$, we have $\mathbb{P}[T_{\text{approx}} \ge 0] \ge 1/2$.

**Stochastic error** Since $X_0 = r_0(H-1)$ is an upper bound on $V$-function, and we have that the weight of the first atom $\alpha_0 \triangleq \tilde{n}_0/\kappa - 1 = c_0 + \log_{17/16}(T) - 1$ for $c_0$ defined in (11).

Define a measure $\bar{\nu}_{e_k} = \frac{\tilde{n}_0 - \kappa}{e_k + \tilde{n}_0 - \kappa} \delta_{X_0} + \sum_{i=1}^{e_k} \frac{1}{e_k + n_0 - 1} \delta_{X_i}$. Since $p_h V_{h+1}^*(s, a) \le H - h - 1$, we can apply Lemma 10 with a fixed $\varepsilon = 1/2$ conditioned on independent random variables $X_i$

$$ \mathbb{P}\left[\sum_{i=0}^{e_k} \hat{W}_j^i X_i \geq p_h V_{h+1}^*(s, a) \mid \{X_i\}_{i=1}^{e_k}\right] \\ \geq \frac{1}{2} \left( 1 - \Phi\left(\sqrt{\frac{2(e_k + n_0 - \kappa) K_{\text{inf}}(\bar{\nu}_{e_k}, p_h V_{h+1}^*(s, a))}{\kappa}}\right) \right), $$

where $\Phi$ is a CDF of a normal distribution. By Lemma 12 and the event $\mathcal{E}^*(\delta, \varepsilon)$

$$ (e_k + n_0 - \kappa) K_{\text{inf}}(\bar{\nu}_{e_k}, p_h V_{h+1}^*(s, a)) \le e_k K_{\text{inf}}(\hat{\nu}_{e_k}, p_h V_{h+1}^*(s, a)) \le \beta^*(\delta, T, \varepsilon), $$

where $\hat{\nu}_{e_k} = \frac{1}{e_k} \sum_{i=1}^{e_k} \delta_{V_{h+1}^*(F(s, a, \xi_{h+1}^i))}$, and, as a corollary

$$ \mathbb{P}\left[\sum_{i=0}^{e_k} \hat{W}_j^i X_i \geq p_h V_{h+1}^*(s, a) \mid \mathcal{E}^*(\delta, \varepsilon), \{X_i\}_{i=1}^{e_k}\right] \geq \frac{1}{2} \left( 1 - \Phi\left(\sqrt{\frac{2\beta^*(\delta, T, \varepsilon)}{\kappa}}\right) \right). $$

By taking $\kappa = 2\beta^*(\delta, T, \varepsilon)$ we have a constant probability of being optimistic for stochastic error

$$ \mathbb{P}[T_{\text{stoch}} \ge 0 \mid \mathcal{E}^*(\delta, \varepsilon)] \ge \frac{1 - \Phi(1)}{2}. $$

Overall, combining two lower bound for approximation and stochastic terms, we have

$$ \mathbb{P}\left[\sum_{i=0}^{e_k} W_{j,e_k,k}^i X_i \geq p_h V_{h+1}^*(s, a) + \varepsilon L \mid \mathcal{E}^*(\delta, \varepsilon)\right] \geq \frac{1 - \Phi(1)}{4} = \gamma. $$
Next, using a choice $J = [(\log(2HT/\delta) + \log(N_\epsilon))/\log(1/(1-\gamma))] = [\tilde{c}_J \cdot (\log(2HT/\delta) + \log(N_\epsilon))]$

$$ \mathbb{P}\left[\max_{j \in [J]} \left\{ \sum_{i=0}^{e_k} W_{j,e_k,k}^i X_i \right\} \ge p_h V_{h+1}^*(s, a) + \epsilon L | \mathcal{E}^*(\delta, \epsilon) \right] \ge 1 - (1-\gamma)^J \ge 1 - \frac{\delta}{2N_\epsilon H T}. $$

By a union bound we conclude the statement. □

Next we provide a connection between $\mathcal{E}^{\text{anticonc}}$ and $\mathcal{E}^{\text{opt}}$.

**Proposition 5.** It holds $\mathcal{E}^{\text{opt}} \subseteq \mathcal{E}^{\text{anticonc}}$.

*Proof.* We proceed by a backward induction over $h$. Base of induction $h = H + 1$ is trivial. Fix state-action pair $(s, a)$ and let us call $(s', a')$ a center of the ball $\psi_\epsilon(s, a)$ that is the ball where $(s, a)$ contains.

Next by the update formula for $\overline{Q}_h^t$, and Bellman equations

$$ \overline{Q}_h^t(\psi_\epsilon(s, a)) - Q_h^*(s, a) = \max_{j \in [J]} \left\{ \sum_{i=0}^n W_{j,n}^i [r_h(s_h^{\ell_i}, a_h^{\ell_i}) - r_h(s', a')] + \sum_{i=0}^n W_{j,n}^i \overline{V}_{h+1}^{\ell_i}(s_{h+1}^{\ell_i}) - p_h V_{h+1}^*(s', a') \right\} + [Q_h^*(s, a) - Q_h^*(s', a)], $$

where $n = e_k^t(B)$ and we drop dependence on $k, t, h, s, a$ in $\ell^i$. By induction hypothesis we have $\overline{V}_{h+1}^{\ell_i}(s') \ge \overline{Q}_{h+1}^{\ell_i}(\psi_\epsilon(s', \pi^*(s')) \ge Q_{h+1}^*(s', \pi^*(s')) = V_{h+1}^*(s')$ for any $i$, thus combining it with Lipchitz continuity of reward function and $Q^*$, and the value of $r_h(s^{\ell^0}, a^{\ell^0}) = r_0 > r_h(s, a)$,

$$ \overline{Q}_h^t(\psi_\epsilon(s, a)) - Q_h^*(s, a) \ge \max_{j \in [J]} \left\{ W_{j,n}^0 r_0(H-1) + \sum_{i=1}^n W_{j,n}^i V_{h+1}^*(F_h(s_h^{\ell_i}, a_h^{\ell_i}, \xi_h^{\ell_i})) \right\} - p_h V_{h+1}^*(s', a') - (L_r + L_V)\epsilon. $$

Next we apply Lipschitz continuity of $F_h$ and $V_{h+1}^*$ and obtain

$$ \overline{Q}_h^t(\psi_\epsilon(s, a)) - Q_h^*(s, a) \ge \max_{j \in [J]} \left\{ W_{j,n}^0 r_0(H-1) + \sum_{i=1}^n W_{j,n}^i V_{h+1}^*(F_h(s', a', \xi_h^{\ell_i})) \right\} - p_h V_{h+1}^*(s', a') - (L_r + L_V(1+L_F))\epsilon. $$

By the definition of event $\mathcal{E}^{\text{anticonc}}$ we conclude the statement. □

**Proposition 6 (Optimism).** Define a constant $L = L_r + L_V(1+L_F)$. Assume that $J = [\tilde{c}_J \cdot (\log(2HT/\delta) + \log(N_\epsilon))]$, $\kappa = 2\beta^*(\delta, T, \epsilon)$, $r_0 = 2$, and a prior count $n_0(k) = [\tilde{n}_0 + \kappa + \frac{\epsilon L}{H-1} \cdot (e_k + \tilde{n}_0 + \kappa)]$ dependent on the stage $k$, where $\tilde{n}_0 = (c_0 + 1 + \log_{17/16}(2e_k)) \cdot \kappa$, $c_0$ is defined in (11), $\tilde{c}_J$ is defined in (12). Then $\mathbb{P}(\mathcal{E}^{\text{opt}} | \mathcal{E}^*(\delta, \epsilon)) \ge 1 - \delta/2$.

## E.5 Regret Bounds

As in the tabular setting, we first connect our algorithm to the algorithm by Song and Sun [2019], using the following corollary. Define an event $\mathcal{G}'(\delta, \epsilon) = \mathcal{G}(\delta, \epsilon) \cap \mathcal{E}^{\text{opt}}$.

Let us define the logarithmic term as follows

$$ \beta^{\max}(\delta, \epsilon) = \max\{\kappa, \tilde{n}_0/\kappa, \beta^B(\delta, \epsilon), \beta(\delta, \epsilon), \beta^{\text{conc}}(\delta, \epsilon)\} $$

that has dependence of order $\mathcal{O}(\log(TH/\delta) + \log N_\epsilon)$.

**Corollary 2.** Fix $\epsilon \in (0, L_V/H)$ and assume conditions of Proposition 6. Let $t \in [T]$, $h \in [H]$, $B \in N_\epsilon$. Define $k = k_h^t(B)$ and let $\ell^1 < \dots < \ell^{e_k}$ be a excursions of $(B, h)$ till the end of the previous stage. Then on the event $\mathcal{G}'(\delta)$ the following bound holds for $k \ge 0$ and any $(s, a) \in B$

$$ 0 \le \overline{Q}_h^t(B) - Q_h^*(s, a) \le \frac{1}{e_k} \sum_{i=1}^{e_k} [\overline{V}_{h+1}^{\ell_i}(s_{h+1}^{\ell_i}) - V_{h+1}^*(s_{h+1}^{\ell_i})] + \mathcal{B}_h^t(k), $$
where

$$B_h^t(k) = 121e^2 \cdot \sqrt{\frac{H^2(\beta^{\max}(\delta, \varepsilon))^2}{e_k}} + 2401e \cdot \frac{H(\beta^{\max}(\delta, \varepsilon))^4}{e_k} + 3(L_r + (1 + L_F)L_V)\varepsilon.$$

*Proof.* The lower bound follows from the definition of the event $\mathcal{E}^{\text{opt}}$. For the upper bound we first apply the decomposition for $\overline{Q}_h^t(s, a)$ and the definition of event $\mathcal{E}^B(\delta, \varepsilon)$ from Lemma 6

$$\begin{aligned} \overline{Q}_h^t(B) = \max_{j \in [J]} & \left\{ \sum_{i=0}^{e_k} W_{j,n}^i \left( r_h(s_h^{\ell^i}, a_h^{\ell^i}) + \bar{V}_{h+1}^{\ell^i}(s_{h+1}^{\ell^i}) \right) \right\} \\ & \le \frac{1}{e_k + n_0(k)} \sum_{i=1}^{e_k} \left( r_h(s_h^{\ell^i}, a_h^{\ell^i}) + \bar{V}_{h+1}^{\ell^i}(s_{h+1}^{\ell^i}) \right) + \frac{n_0(k) \cdot 2H}{e_k + n_0(k)} \\ & + 120e^2 \sqrt{\frac{H^2 \kappa \beta^B(\delta, \varepsilon)}{e_k + n_0(k)}} + 2400e \frac{H \kappa \log(n + n_0(k)) (\beta^B(\delta, \varepsilon))^2}{e_k + n_0(k)}. \end{aligned}$$

Additionally, by Bellman equations

$$\begin{aligned} Q_h^*(s, a) = & \frac{1}{e_k} \sum_{i=1}^{e_k} Q_h^*(s_h^{\ell^i}, a_h^{\ell^i}) + \frac{1}{e_k} \sum_{i=1}^{e_k} (Q_h^*(s, a) - Q_h^*(s_h^{\ell^i}, a_h^{\ell^i})) \\ & \ge \frac{1}{e_k} \sum_{i=1}^{e_k} (r_h(s_h^{\ell^i}, a_h^{\ell^i}) + p_h V_{h+1}^*(s_h^{\ell^i}, a_h^{\ell^i})) - 2\varepsilon L_V. \end{aligned}$$

Combining and using the fact that $n_0(k) \le \frac{L\varepsilon}{H-1} \cdot (e_k + n_0(k)) + \tilde{n}_0 + \kappa$ for $L = L_r + (1 + L_F)L_V$

$$\begin{aligned} \overline{Q}_h^t(s, a) - Q_h^*(s, a) \le & \frac{1}{e_k} \sum_{i=1}^{e_k} \left[ \bar{V}_{h+1}^{\ell^i} - V_{h+1}^* \right] (s_{h+1}^{\ell^i}) + \frac{1}{e_k} \sum_{i=1}^{e_k} \left[ V_{h+1}^*(s_{h+1}^{\ell^i}) - p_h V_{h+1}^*(s_h^{\ell^i}, a_h^{\ell^i}) \right] \\ & + 120e^2 \cdot \sqrt{\frac{H^2(\beta^{\max}(\delta, \varepsilon))^2}{e_k}} + (2400e + 2) \frac{H(\beta^{\max}(\delta, \varepsilon))^4}{e_k} + 3L\varepsilon. \end{aligned}$$

Finally, the applications of event $\mathcal{E}^{\text{conc}}(\delta, \varepsilon)$ concludes the statement. $\square$

Let us define $\delta_h^t = \bar{V}_h^t(s_h^t) - V_h^{\pi^t}(s_h^t)$ and $\zeta_h^t = \bar{V}_h^t(s_h^t) - V_h^*(s_h^t)$.

**Lemma 7.** Assume conditions of Proposition 6. Then on event $\mathcal{G}'(\delta, \varepsilon) = \mathcal{G}(\delta, \varepsilon) \cap \mathcal{E}^{\text{opt}}$, where $\mathcal{G}(\delta, \varepsilon)$ is defined in Lemma 6, the following upper bound on regret holds

$$\mathfrak{R}^T \le 2eH \sum_{t=1}^{T} \sum_{h=1}^{H} 1\{N_h^t = 0\} + \sum_{t=1}^{T} \sum_{h=1}^{H} (1 + 1/H)^{H-h} \xi_h^t + e \sum_{t=1}^{T} \sum_{h=1}^{H} \mathcal{B}_h^t.$$

where $\xi_h^t = p_h[V_{h+1}^* - V_{h+1}^{\pi^t}](s_h^t, a_h^t) - [V_{h+1}^* - V_{h+1}^{\pi^t}](s_{h+1}^t)$ and $\mathcal{B}_h^t = \mathcal{B}_h^t(k_h^t(s_h^t, a_h^t))$. $1\{k_h^t(s_h^t, a_h^t) \ge 0\}$ for $\mathcal{B}_h^t$ defined in Corollary 2.

*Proof.* As in the tabular setting, we notice that on the event $\mathcal{E}^{\text{opt}}$ we can upper bound the regret in terms of $\delta_1^t$.

$$\mathfrak{R}^T \le \sum_{t=1}^{T} \delta_1^t. \qquad (13)$$

Next we analyze $\delta_h^t$. Since $a_h^t = \arg\max_{a \in \mathcal{A}} \overline{Q}_h^t(\psi_\varepsilon(s_h^t, a))$, we can use Corollary 2 and Bellman equations in the following way

$$\begin{aligned} \delta_h^t = & \bar{V}_h^t(s_h^t) - V_h^{\pi^t}(s_h^t) = \overline{Q}_h^t(B_h^t) - Q_h^{\pi^t}(s_h^t, a_h^t) \\ = & \overline{Q}_h^t(B_h^t) - Q_h^*(s_h^t, a_h^t) + Q_h^*(s_h^t, a_h^t) - Q_h^{\pi^t}(s_h^t, a_h^t) \\ \le & r_0 H 1\{N_h^t = 0\} + 1\{N_h^t > 0\} \left( \frac{1}{N_h^t} \sum_{i=1}^{N_h^t} \zeta_{h+1}^{\ell^i, h} + \mathcal{B}_h^t(k_h^t) + p_h [V_{h+1}^* - V_{h+1}^{\pi^t}](s_h^t, a_h^t) \right). \end{aligned}$$
where $k_h^t = k_h^t(B_h^t)$, $N_h^t = e_{k_h^t}$, $\ell_{t,h}^i$ is an i-th visitation of the ball $B_h^t$ during an stage $k_h^t$, and additionally by a convention $0/0 = 0$.

Define $\xi_h^t = p_h[V_{h+1}^* - V_{h+1}^{\pi^t}](s_h^t, a_h^t) - [V_{h+1}^* - V_{h+1}^{\pi^t}](s_{h+1}^t)$ a martingale-difference sequence, and $B_h^t = B_h^t(k_h^t)1\{N_h^t > 0\}$ then

$$ \delta_h^t \le r_0 H 1\{N_h^t = 0\} + \frac{1\{N_h^t > 0\}}{N_h^t} \sum_{i=1}^{N_h^t} \zeta_{h+1}^{\ell_{t,h}^i} - \zeta_{h+1}^t + \delta_{h+1}^t + \xi_h^t + B_h^t. $$

and, as a result

$$ \sum_{t=1}^{T} \delta_h^t \le r_0 H \sum_{t=1}^{T} 1\{N_h^t = 0\} + \sum_{t=1}^{T} \frac{1\{N_h^t > 0\}}{N_h^t} \sum_{i=1}^{N_h^t} \zeta_{h+1}^{\ell_{t,h}^i} \\ - \sum_{t=1}^{T} \zeta_{h+1}^t + \sum_{t=1}^{T} \delta_{h+1}^t + \sum_{t=1}^{T} \xi_h^t + \sum_{t=1}^{T} B_h^t. $$

For the second term we may repeat arguments as in the proof of Lemma 5 and obtain

$$ \sum_{q=1}^{T} \zeta_{h+1}^{q} \cdot \sum_{t=1}^{T} \frac{1\{k_h^t \ge 0\}}{N_h^t} \sum_{i=1}^{N_h^t} 1\{\ell_{t,h}^i = q\} \le \left(1 + \frac{1}{H}\right) \sum_{q=1}^{T} \zeta_{h+1}^{q}. $$

After a simple algebraic manipulations and using the fact that $\zeta_h^t \le \delta_h^t$

$$ \sum_{t=1}^{T} \delta_h^t \le H \sum_{t=1}^{T} 1\{N_h^t = 0\} + \sum_{t=1}^{T} (1 + 1/H)\zeta_{h+1}^t - \sum_{t=1}^{T} \zeta_{h+1}^t + \sum_{t=1}^{T} \delta_{h+1}^t + \sum_{t=1}^{T} \xi_h^t + \sum_{t=1}^{T} B_h^t \\ \le H \sum_{t=1}^{T} 1\{N_h^t = 0\} + \left(1 + \frac{1}{H}\right) \sum_{t=1}^{T} \delta_{h+1}^t + \sum_{t=1}^{T} \xi_h^t + \sum_{t=1}^{T} B_h^t. $$

By rolling out the upper bound on regret (13) we have

$$ \mathfrak{R}^T \le 2eH \sum_{t=1}^{T} \sum_{h=1}^{H} 1\{N_h^t = 0\} + \sum_{t=1}^{T} \sum_{h=1}^{H} (1+1/H)^{H-h} \xi_h^t + e \sum_{t=1}^{T} \sum_{h=1}^{H} B_h^t. $$

□

*Proof of Theorem 2.* First, we notice that the event $\mathcal{G}'(\delta, \varepsilon)$ defined in Lemma 7, holds with probability at least $1 - \delta$ by Lemma 6 and Proposition 6. Thus, we may assume that $\mathcal{G}'(\delta, \varepsilon)$ holds for $\varepsilon > 0$ that we will specify later.

By Lemma 7

$$ \mathfrak{R}^T \le 2eH \sum_{t=1}^{T} \sum_{h=1}^{H} 1\{k_h^t = -1\} + \sum_{t=1}^{T} \sum_{h=1}^{H} (1+1/H)^{H-h} \xi_h^t + e \sum_{t=1}^{T} \sum_{h=1}^{H} B_h^t. $$

The first term is upper bounded by $2eH^3 \cdot N_\varepsilon$, since there is no more than $H$ visits of each ball in $\varepsilon$-net before the update for the first stage. The second term is bounded by $O(\sqrt{H^3 T \beta^{\max}(\delta, \varepsilon)})$ by a definition of the event $\mathcal{E}(\delta)$ in Lemma 6.

To analyze the last term, consider the following sum

$$ \sum_{t=1}^{T} \sum_{h=1}^{H} \frac{1\{e_{k_h^t}(B_h^t) > 0\}}{\sqrt{e_{k_h^t}(B_h^t)}} \le \sum_{(B,h) \in \mathcal{N}_\varepsilon \times [H]} \sum_{k=0}^{k_h^T(B)} \frac{e_{k+1}}{\sqrt{e_k}}, $$
where

$$e_k = \left\lfloor \left(1 + \frac{1}{H}\right)^k H \right\rfloor \Rightarrow \frac{e_{k+1}}{\sqrt{e_k}} \le 2\sqrt{H} \left(1 + \frac{1}{H}\right)^{k/2},$$

therefore

$$\sum_{h=0}^{k_h^T(B)} \frac{e_{k+1}}{\sqrt{e_k}} \le 4\sqrt{H} \frac{(1+1/H)^{(k_h^T(B)+1)/2}}{\sqrt{1+1/H}-1} = 4H \sqrt{e^{k_h^T(B)+1}}. \quad (14)$$

Notice that

$$N_h^{T+1}(B) \ge \sum_{k=0}^{k_h^T(B)} e^k = H(e^{k_h^T(B)+1} - 1) \Rightarrow e^{k_h^T(B)+1} \le \frac{N_h^{T+1}(B)+1}{H}$$

thus from the Cauchy-Schwarz inequality

$$\sum_{t=1}^{T} \sum_{h=1}^{H} \frac{1\{e_{k_h^t(B_h^t)}>0\}}{\sqrt{e^{k_h^t(B_h^t)}}} \le 4\sqrt{H} \sum_{(B,h) \in \mathcal{N}_\varepsilon \times [H]} \sqrt{N_h^{T+1}(B)+1} \\ \le 4\sqrt{SAH^2} \sqrt{\sum_{(B,h)} (N_h^{T+1}(B)+1)} \le 4\sqrt{H^3 T \cdot N_\varepsilon} + 4N_\varepsilon H^2.$$

By the similar arguments we have

$$\sum_{t=1}^{T} \sum_{h=1}^{H} \frac{1\{e_{k_h^t(B_h^t)}>0\}}{e_{k_h^t(B_h^t)}} \le \mathcal{O}(HN_\varepsilon \log(T)).$$

Using this upper bound, we have for $L = L_r + (1 + L_F)L_V$

$$\sum_{t=1}^{T} \sum_{h=1}^{H} \mathcal{B}_h^t = \mathcal{O}\left(H \beta^{\max}(\delta, \varepsilon) \sum_{t=1}^{T} \sum_{h=1}^{H} \frac{1\{e_{k_h^t(s_h^t, a_h^t)}>0\}}{\sqrt{e^{k_h^t(s_h^t, a_h^t)}}}\right) \\ + \mathcal{O}\left(H(\beta^{\max}(\delta, \varepsilon))^4 \sum_{t=1}^{T} \sum_{h=1}^{H} \frac{1\{e_{k_h^t(s_h^t, a_h^t)}>0\}}{\sqrt{e^{k_h^t(s_h^t, a_h^t)}}}\right) \\ + \mathcal{O}(LTH\varepsilon) \\ \le \mathcal{O}\left(\sqrt{H^5 TN_\varepsilon \cdot (\beta^{\max}(\delta, \varepsilon))^2} + H^3 N_\varepsilon (\beta^{\max}(\delta, \varepsilon))^4 + LTH\varepsilon\right).$$

Overall, for any fixed $\varepsilon > 0$ we have

$$\mathfrak{R}^T \le \mathcal{O}\left(\sqrt{H^5 TN_\varepsilon \cdot (\beta^{\max}(\delta, \varepsilon))^2} + H^3 N_\varepsilon (\beta^{\max}(\delta, \varepsilon))^4 + LTH\varepsilon + \sqrt{H^3 T}\right).$$

Next we finally use that $\mathcal{S} \times \mathcal{A}$ have covering dimension $d_c$ that means $N_\varepsilon \le C_N \cdot \varepsilon^{-d_c}$, thus our regret bound transforms as follows

$$\mathfrak{R}^T \le \mathcal{O}\left(\sqrt{H^5 TC_N \varepsilon^{-d_c} \cdot \left(\log(TC_N H/\delta) + d_c \log(1/\varepsilon)\right)^2} + H^3 C_N \varepsilon^{-d_c} \left(\log(TC_N H/\delta) + d_c \log(1/\varepsilon)\right)^4 + LTH\varepsilon\right).$$

By taking $\varepsilon = T^{-1/(d_c+2)}$ we conclude the statement

□
# F Adaptive RandQL

In this section we describe how to improve the dependence in our algorithm from covering dimension to zooming dimension, and describe all required notation.

## F.1 Additional Notation

In this section we introduce an additional notation that is needed for introducing an adaptive version of RandQL algorithm for metric spaces.

**Hierarchical partition** Next, we define all required notation to describe an adaptive partition, as Sinclair et al. [2019, 2023]. Finally, we define the following general framework of hierarchical partition. Instead of balls, we will use a more general notion of regions that will induce a better structure from the computational point of view. We recall for any compact set $A \subseteq S \times A$ we call $\text{diam}(A) = \max_{x,y \in A} \rho(x, y)$.

**Definition 6.** A hierarchical partition of $S \times A$ of a depth $d > 0$ is a collection of regions $\mathcal{P}_d$ and their centers such that

* Each region $B \in \mathcal{P}_d$ is of the form $S(B) \times A(B)$, where $S(B) \subseteq S$, $A(B) \subseteq A$;

* $\mathcal{P}_d$ is a cover of $S \times A: \bigcup_{B \in \mathcal{P}_d} B = S \times A$;

* For every $B \in \mathcal{P}_d$, we have $\text{diam}(B) \le d_{\max} \cdot 2^{-d}$;

* Let $B_1, B_2 \in \mathcal{P}_d$. If $B_1 \neq B_2$ then $\rho(\text{center}(B_1), \text{center}(B_2)) \ge d_{\max} \cdot 2^{-d}$;

* For any $B \in \mathcal{P}_d$, there exists a unique $A \in \mathcal{P}_{d-1}$ (called the parent of B) such that $B \subseteq A$.

and, for $d=0$ we define it as $\mathcal{P}_0 = \{S \times A\}$.

We call the tree generated by the structure of $\mathcal{T} = \{\mathcal{P}_d\}_{d \ge 0}$ a tree of this hierarchical partition. The main example of this partition is the dyadic partition of $S \times A$ in the case of $S = [0, 1]^{d_S}$, $A = [0, 1]^{d_A}$ and the metric induced by the infinity norm $\rho((s, a), (s', a')) = \max\{\|s - s'\|_{\infty}, \|a - a'\|_{\infty}\}$. For examples we refer to [Sinclair et al., 2023].

## F.2 Algorithm

In this section we describe two algorithms: **Adaptive-RandQL** which is an adaptive metric counterpart of RandQL, and **Adaptive-Staged-RandQL** which is an adaptive metric counterpart of Staged-RandQL. First, we start from the notation and algorithmic parts that will be common for both algorithms.

Algorithms maintain an adaptive partition $\mathcal{P}_h^t$ of $S \times A$, that is a sub-tree of an (infinite) tree of the hierarchical partition $\mathcal{T} = \{\mathcal{P}_d\}_{d \ge 0}$. We initialize $\mathcal{P}_h^t = \{\mathcal{P}_0\}$, and then we refine the tree $\mathcal{P}_h^t$ by adding new nodes that corresponding to nodes of $\mathcal{T}$. The leaf nodes of $\mathcal{P}_h^t$ represent the active balls, and for $B \in \mathcal{P}_h^t$ the set of its inactive parent balls is defined as $\{B' \in \mathcal{P}_h^t | B \subset B'\}$. For any $B \in \mathcal{P}_h^t$ we define $d(B)$ as a depth of B in the tree under a convention $d(S \times A) = 0$.

Additionally, we need to define so-called selection rule and splitting rule. For any state $s \in S$ we define the set of all relevant balls as $\mathcal{R}_h^t(s) = \{ \text{active } b \in \mathcal{P}_h^t | (s, a) \in B \text{ for some } a \in A \}$. Then for the current state $s_h^t$ we define the current ball as $B_h^t = \arg\max_{B \in \mathcal{R}_h^t(s_h^t)} \bar{Q}_h^t(B)$ and the corresponding action as $a_h^t$. To define the splitting rule we maintain the counters $n_h^t(B)$ for all $B \in \mathcal{P}_h^t$ as a number of visits of a node B and all its parent nodes. Then we will perform splitting of the current ball $B_h^t$ if $\sqrt{d_{\max}^2/n_h^t(B_h^t)} \le \text{diam}(B_h^t)$. During splitting, we extend $\mathcal{P}_h^{t+1}$ by its child nodes in the hierarchical partition tree $\mathcal{T}$. For more details we refer to [Sinclair et al., 2023], up to small changes in notation. In particular, their constant $\tilde{C}$ is equal to $d_{\max}$ in our setting to make the construction exactly the same for both Adaptive-RandQL and Adaptive-Staged-RandQL algorithms.
Algorithm 5 Adaptive-RandQL

1: **Input:** ensemble size $J$, number of prior transitions $n_0$, prior reward $r_0$.

2: **Initialize:** $\tilde{Q}_h(B) = \tilde{Q}_h^j(B) = r_0 H$, initialize counters $n_h(s, a) = 0$ for $h, s, a \in [H] \times S \times A$.

3: **for** $t \in [T]$ **do**

4: **for** $h \in [H]$ **do**

5: Compute $B_h = \arg \max_{B \in \mathcal{R}_h^t(s_h)} \bar{Q}_h(B)$ and play $a_h$ for $(s_h, a_h) = \text{center}(B_h)$;

6: Observe reward and next state $s_{h+1} \sim p_h(s_h, a_h)$.

7: Sample $\hat{w}_j \sim \text{Beta}(n, n_0)$ for $n = n_h(B_h)$.

8: Compute value $\bar{V}_{h+1}(s_{h+1}) = \max_{B \in \mathcal{R}_h^t(s_{h+1})} \bar{Q}_{h+1}(B)$.

9: Build targets for all $j \in [J]$

$$ \hat{Q}_h^j = \hat{w}_j[r_h(s_h, a_h) + \bar{V}_{h+1}(s_{h+1})] + (1 - \hat{w}_j)r_0 H. $$

10: Sample learning rates $w_j \sim \text{Beta}(H, n)$.

11: Update ensemble $Q$-functions for all $j \in [J]$

$$ \tilde{Q}_h^j(B_h) := (1 - w_j)\tilde{Q}_h^j(s_h, a_h) + w_j \hat{Q}_h^j. $$

12: Update policy $Q$-function $\bar{Q}_h(s_h, a_h) := \max_{j \in [J]} \tilde{Q}_h^j(s_h, a_h)$.

13: Update counters $n_h(B_h) := n_h(B_h) + 1$;

14: If $\sqrt{d_{\max}^2/n_h(B_h)} \le \text{diam}(B_h)$, then refine partition $B_h$ (see Sinclair et al. [2023]).

15: **end for**

16: **end for**

**Adaptive-RandQL** This algorithm is an adaptive metric version of RandQL algorithm. We recall that for $B \in \mathcal{P}_h^t$ we define $n_h^t(B) = \sum_{i=1}^{t-1} 1\{(B_h^i)\}$ is a parent of $B$} is the number of visits of the ball $B$ and its parent balls at step $h$ before episode $t$. We start by initializing the ensemble of Q-values, the policy Q-values, and values to an optimistic value $\tilde{Q}_h^t(B) = \bar{Q}_h^1(B) = \bar{V}_h^1(B) = r_0 H$ for all $(j, h) \in [J] \times [H]$ and the unique ball in the partition $B = S \times A$ and $r_0 > 0$ some pseudo-rewards.

At episode $t$ we update the ensemble of Q-values as follows, denoting by $n = n_h^t(B)$ the count, $w_{j,n} \sim \text{Beta}(H, n)$ the independent learning rates,

$$ \tilde{Q}_h^{t+1,j}(B) = \begin{cases} (1 - w_{j,n}) \tilde{Q}_h^{t,j}(B) + w_{j,n} \hat{Q}_h^{t,j}(s_h^t, a_h^t), & B = B_h^t \\ \tilde{Q}_h^{t,j}(B) & \text{otherwise,} \end{cases} $$

where we defined the target $\hat{Q}_h^{t,j}(s_h^t, a_h^t)$ as a mixture between the usual target and some prior target with mixture coefficient $\hat{w}_{n,j} \sim \text{Beta}(n, n_0)$ and $n_0$ the number of prior samples,

$$ \hat{Q}_h^{t,j}(s_h^t, a_h^t) = \hat{w}_{j,n}[r_h(s_h^t, a_h^t) + \bar{V}_{h+1}^t(s_{h+1}^t)] + (1 - \hat{w}_{j,n})r_0 H. $$

For a discussion on prior re-injection we refer to Appendix B. The value function is computed on-flight by the rule $\bar{V}_h^t(s) = \max_{B \in \mathcal{R}_h^t} \bar{Q}_h^t(B)$.

The policy Q-values are obtained by taking the maximum among the ensemble of Q-values

$$ \bar{Q}_h^{t+1}(B) = \max_{j \in [J]} \tilde{Q}_h^{t+1,j}(B). $$

The policy is then greedy with respect to the policy Q-values and selection rule $(s, \pi_h^{t+1}(s)) = \text{center}(B)$, where $B = \arg \max_{B \in \mathcal{R}_h^{t+1}} \bar{Q}_h^{t+1}(B)$. After the update of Q-values, algorithm verifies the splitting rule. If the splitting rule is triggered, then all new balls are defined by counter and Q-values of its parent. We notice that all Q-values could be efficiently computed on the nodes of the adaptive partition. The complete and detailed description is presented in Algorithm 6.

**Adaptive-Staged-RandQL** The notation for this algorithm is very close to Net-Staged-RandQL and we describe only differences between them. The main difference is a way to compute value $\bar{V}_h^t(s) = \max_{B \in \mathcal{R}_h^t(s)} \bar{Q}_h^t(B)$ and policy $(s, \pi_h^t(s)) = \text{center}(B)$ for $B =$
Algorithm 6 Adaptive-Staged-RandQL

1: **Input:** inflation coefficient $\kappa$, $J$ ensemble size, number of prior transitions $n_0(k)$, prior reward $r_0$.

2: **Initialize:** $\bar{Q}_h(B) = \tilde{Q}_h^j(B) = r_0 H$, initialize counters $\tilde{n}_h(B) = 0$ for $j, h, B \in [J] \times [H] \times \mathcal{N}_\epsilon$, stage $q_h(B) = 0$.

3: **for** $t \in [T]$ **do**

4: **for** $h \in [H]$ **do**

5: Compute $B_h = \arg \max_{B \in \mathcal{R}_h^t(s_h)} \bar{Q}_h(B)$ and play $a_h$ for $(s_h, a_h) = \text{center}(B_h)$;

6: Observe reward and next state $s_{h+1} \sim p_h(s_h, a_h)$.

7: Sample learning rates $w_j \sim \text{Beta}(1/\kappa, (\tilde{n} + n_0(q_h(B_h))/\kappa)$ for $\tilde{n} = \tilde{n}_h(B_h)$.

8: Compute value $\bar{V}_{h+1}(s_{h+1}) = \max_{B \in \mathcal{R}_h^t(s_{h+1})} \bar{Q}_{h+1}(B)$.

9: Update temporary $Q$-values for all $j \in [J]$

$$ \tilde{Q}_h^j(B) := (1 - w_j) \tilde{Q}_h^j(B) + w_j (r_h(s_h, a_h) + \bar{V}_{h+1}(s_{h+1})) $$

10: Update counters $\tilde{n}_h(B_h) := \tilde{n}_h(B_h) + 1$ and $n_h(B_h) := n_h(B_h) + 1$.

11: **if** $\tilde{n}_h(B_h) = \lfloor (1 + 1/H)^q H \rfloor$ for $q = q_h(B_h)$ is the current stage **then**

12: Update policy $Q$-values $\bar{Q}_h(B_h) := \max_{j \in [J]} \tilde{Q}_h^j(B_h)$.

13: Reset temporary $Q$-values $\tilde{Q}_h^j(B_h) := r_0 H$.

14: Reset counter $\tilde{n}_h(B_h) := 0$ and change stage $k_h(B_h) := k_h(B_h) + 1$.

15: **end if**

16: If $\sqrt{d_{\max}^2/n_h(B_h)} \le \text{diam}(B_h)$, then refine partition $B_h$ (see Sinclair et al. [2023]).

17: **end for**

18: **end for**

$\arg \max_{B \in \mathcal{R}_h^t(s)} \bar{Q}_h^t(B)$. Additionally, all counters including temporary will move to the child nodes after splitting, as it performed in Adaptive-RandQL. The detailed description is presented in Algorithm 6.

## F.3 Regret Bound

In this section we state the regret bounds for Adaptive-Staged-RandQL and derive a proof. The given proof shares a lot of similarities with the proof of Net-Staged-RandQL in the first half and to the proof of Adaptive-QL by Sinclair et al. [2023] in the second half.

We fix $\delta \in (0, 1)$, and the number of posterior samples

$$ J \triangleq \lfloor \tilde{c}_J \cdot (\log(2C_N H T / \delta) + d_c \log_2(8T / d_{\max})) \rfloor, \quad (15) $$

where $\tilde{c}_J = 1/\log(4/(3+\Phi(1)))$ and $\Phi(\cdot)$ is the cumulative distribution function (CDF) of a normal distribution.

Additionally we select

$$ n_0(k) = \left\lfloor \tilde{n}_0 + \kappa + \frac{L \cdot d_{\max}}{H-1} \cdot \frac{e_k + \tilde{n}_0 + \kappa}{\sqrt{H e_k - k - H^2}} \right\rfloor, \quad \tilde{n}_0 = (c_0 + 1 + \log_{17/16}(T)) \cdot \kappa $$

where $c_0$ is an absolute constant defined in (5) (see Appendix D.3), $\kappa$ is the posterior inflation coefficient and $L = L_r + (1 + L_F)L_V$ is a constant. Next we restate the regret bound result for Adaptive-Staged-RandQL algorithm.

**Theorem (Restatement of Theorem 3).** Consider a parameter $\delta \in (0, 1)$. Let $\kappa \triangleq 2(\log(8HC_N/\delta) + d_c \log_2(8T/d_{\max}) + 3 \log(e\pi(2T+1)))$, $r_0 \triangleq 2$. Then it holds for Adaptive-Staged-RandQL, with probability at least $1 - \delta$,

$$ \mathcal{R}^T = \tilde{\mathcal{O}}\left(LH^{3/2} \sum_{h=1}^{H} T^{\frac{d_{z,h}+1}{d_{z,h}+2}}\right), $$

where $d_{z,h}$ is the step-h zooming dimension and we ignore all multiplicative factors in the covering dimension $d_c$.
*Proof.* We divide the proof to four main parts, a little bit different proof of Staged-RandQL and Net-Staged-RandQL since we also need to apply clipping techniques.

**Concentration events** We can define (almost) the same set of events as in Appendix E.3, where union bound over balls is taken over all the hierarchical partition tree up to depth *D* that we define as $\mathcal{T}_D$.

$$ \mathcal{E}^*(\delta) \triangleq \left\{ \forall t \in \mathbb{N}, \forall h \in [H], \forall B \in \mathcal{T}_D, k = k_h^t(B), (s, a) = \text{center}(B): \right. \\ \left. \qquad \mathcal{K}_{\inf}\left(\frac{1}{e_k} \sum_{i=1}^{e_k} \delta_{V_{h+1}^*(F_h(s,a,\xi_{h+1}^{\ell^i}))}, p_h V_{h+1}^*(s, a)\right) \le \frac{\beta^*(\delta, e_k, \varepsilon)}{e_k} \right\}, $$

$$ \mathcal{E}^B(\delta, T) \triangleq \left\{ \forall t \in [T], \forall h \in [H], \forall B \in \mathcal{T}_D, \forall j \in [J], k = k_h^t(B): \left| \sum_{i=0}^{e_k} (W_{j,e_k,k}^i - \mathbb{E}[W_{j,e_k,k}^i]) \left( r_h(s_h^{\ell^i}, a_h^{\ell^i}) + \bar{V}_{h+1}^{\ell^i}(s_{h+1}^{\ell^i}) \right) \right| \le 60e^2 \sqrt{\frac{r_0^2 H^2 \kappa \beta^B(\delta, \varepsilon)}{e_k + n_0(k)} + 1200e \frac{r_0 H \kappa \log(e_k + n_0(k))(\beta^B(\delta, \varepsilon))^2}{e_k + n_0(k)}} \right\}, $$

$$ \mathcal{E}^{\text{conc}}(\delta, T) \triangleq \left\{ \forall t \in [T], \forall h \in [H], \forall B \in \mathcal{T}_D, k = k_h^t(B): \left| \frac{1}{e_k} \sum_{i=1}^{e_k} V_{h+1}^*(s_{h+1}^{\ell^i(B)}) - p_h V_{h+1}^*(s_h^{\ell^i(B)}, a_h^{\ell^i(B)}) \right| \le \sqrt{\frac{2r_0^2 H^2 \beta^{\text{conc}}(\delta, \varepsilon)}{e_k}} \right\}, $$

$$ \mathcal{E}(\delta) \triangleq \left\{ \sum_{t=1}^{T} \sum_{h=1}^{H} (1 + 3/H)^{H-h} \left| p_h \left[ V_{h+1}^{\star} - V_{h+1}^{\pi_t} \right] (s_h^t, a_h^t) - \left[ V_{h+1}^{\star} - V_{h+1}^{\pi_t} \right] (s_{h+1}^t) \right| \le 2e^3 r_0 H \sqrt{2HT\beta(\delta)}. \right. $$

To apply the union bound argument, we have to bound the size of $\mathcal{T}_D$. First, we notice that relation between centers of balls in each layer $\mathcal{P}_d$ implies that there at least $|\mathcal{P}_d|$ non-intersecting balls of radius $d_{\max} \cdot 2^{-d-2}$. Thus, the size of this sub-tree could be bounded as

$$ |\mathcal{T}_D| \le \sum_{d=0}^{D} N_{d_{\max} 2^{-d-2}} \le C_N \sum_{d=0}^{D} (2^{d+2}/d_{\max})^{d_c} \le (8/d_{\max})^{d_c} C_N \cdot 2^{d_c \cdot D}. $$

using the relation between covering and packing numbers, see e.g. Lemma 4.2.8 by Vershynin [2018]. The only undefined quantity here is *D*, that can be upper-bounded given budget *T*. To do it, we apply Lemma B.2 by Sinclair et al. [2023] for any $B \in \mathcal{P}_h^t$

$$ \left( \frac{d_{\max}}{2 \cdot \text{diam}(B)} \right)^2 \le n_h^t(B) \le \left( \frac{d_{\max}}{\text{diam}(B)} \right)^2. \qquad (16) $$

Our goal is to find a value *D* such that $\mathcal{P}_h^{T+1} \subseteq \mathcal{T}_D$ for any MDPs and correct interactions. To do it, we notice that it is equivalent to show that $\text{diam}(B) \ge d_{\max} 2^{-D}$, that could be guaranteed since

$$ \text{diam}(B) \ge \frac{d_{\max}}{2\sqrt{n_h^{T+1}(B)}} \ge \frac{d_{\max}}{2T}, $$

which implies that $D = 1 + \log_2(T)$ is enough. Finally, since for the value of interest

$$ \log |\mathcal{T}_D| \le d_c \log_2(T) + \log C_N + d_c \log(8/d_{\max}), $$

we can define the $\beta$-functions as follows follows
$$ \beta^*(\delta) \triangleq \log(8C_N H/\delta) + d_c \log_2(8T/d_{\max}) + 3\log(e\pi(2n+1)), $$

$$ \beta^B(\delta, T) \triangleq \log(8C_N H/\delta) + d_c \log_2(8T/d_{\max}) + \log(TJ), $$

$$ \beta^{\text{conc}}(\delta, T) \triangleq \log(8C_N H/\delta) + d_c \log_2(8T/d_{\max}) + \log(2T), $$

$$ \beta(\delta) \triangleq \log(16C_N H/\delta) + d_c \log_2(8T/d_{\max}), $$

and following line-by-line the proof of Lemma 6, for an event $\mathcal{G}(\delta) = \mathcal{E}^*(\delta) \cap \mathcal{E}^B(\delta, T) \cap \mathcal{E}^{\text{conc}}(\delta, T) \cap \mathcal{E}(\delta)$ we have $\mathbb{P}(\mathcal{G}(\delta)) \ge 1 - \delta/2$.

**Optimism** Next, we state the required analog of Proposition 4. We can show that with probability at least $1 - \delta/2$ on the event $\mathcal{E}^*(\delta)$ the following event

$$ \mathcal{E}_{\text{anticonc}} \triangleq \left\{ \forall t \in [T] \ \forall h \in [H] \ \forall B \in \mathcal{T}_D : \text{for } k = k_h^t(B), (s, a) = \text{center}(B) : \right. $$

$$ \max_{j \in [J]} \left\{ W_{j,e_k,k}^0 r_0(H-1) + \sum_{i=1}^{e_k} W_{j,e_k,k}^i V_{h+1}^*(F_h(s, a, \xi_h^{\ell^i})) \right\} \ge p_h V_{h+1}^*(s, a) + L \cdot \text{diam}(B_h^t) $$

under the choice $J = \lceil \tilde{c}_J \cdot (\log(2HT/\delta) + \log(|\mathcal{T}_D|)) \rceil$, $\kappa = 2\beta^*(\delta, T)$, $r_0 = 2$, and a prior count

$$ n_0(k) = \lceil \tilde{n}_0 + \kappa + \frac{L \cdot d_{\max}}{H-1} \cdot \frac{e_k + \tilde{n}_0 + \kappa}{\sqrt{He_k - k - H^2}} \rceil $$

dependent on the stage $k$, where $\tilde{n}_0 = (c_0 + 1 + \log_{17/16}(T)) \cdot \kappa$, $L = L_r + L_V(1 + L_F)$. In particular, the proof exactly the same as the proof of Proposition 4 for $\varepsilon$ dependent on $k$.

At the same time, it is possible to show that $\mathcal{E}_{\text{anticonc}}$ implies

$$ \mathcal{E}_{\text{opt}} \triangleq \left\{ \forall t \in [T], h \in [H], \forall B \in \mathcal{P}_h^t, \forall (s, a) \in B : \bar{Q}_h^t(B) \ge Q_h^*(s, a) \right\}. \quad (17) $$

Indeed, in the proof of Proposition 5 we actively uses the bound $\rho((s_h^{\ell^i}, a_h^{\ell^i}), (s, a)) \le \varepsilon$. In the adaptive setting, we have to, at first, use an upper bound $\rho((s_h^{\ell^i}, a_h^{\ell^i}), (s, a)) \le \text{diam}(B_h^{\ell^i})$ by a construction $B \subseteq B_h^{\ell^i}$, and then apply Lemma B.2 by Sinclair et al. [2023] by defining an upper bound

$$ \text{diam}(B_h^{\ell^i}) \le \frac{d_{\max}}{\sqrt{n_h^{\ell^i}(B_h^{\ell^i})}} \le \frac{d_{\max}}{\sqrt{\sum_{i=0}^{k-1} e_i}} \le \frac{d_{\max}}{\sqrt{H \sum_{i=0}^{k-1} (1+1/H)^i - k}} \le \frac{d_{\max}}{\sqrt{He_k - k - H^2}} $$

for $k = k_h^t(B)$ for a particular ball $B \in \mathcal{P}_h^t$ in the case $He_k - k - H^2 \ge 0$.

By combining event $\mathcal{E}_{\text{opt}}$ and the event $\mathcal{E}^B(\delta)$ we can prove the same statement as Corollary 2.

Let $t \in [T]$, $h \in [H]$, $B \in \mathcal{P}_h^t$. Define $k = k_h^t(B)$ and let $\ell^1 < \dots < \ell^{e_k}$ be excursions of $(B, h)$ till the end of the previous stage. Then on the event $\mathcal{G}'(\delta) = \mathcal{G}(\delta) \cap \mathcal{E}_{\text{opt}}$ the following bound holds for $k \ge 0$ and for any $(s, a) \in B$

$$ 0 \le \bar{Q}_h^t(B) - Q_h^*(s, a) \le H1\{He_k/2 \le k+H^2\} + \frac{1}{e_k} \sum_{i=1}^{e_k} [V_{h+1}^{\ell^i}(s_{h+1}^{\ell^i}) - V_{h+1}^*(s_{h+1}^{\ell^i})] + \mathcal{B}_h^t, \quad (18) $$

where

$$ \mathcal{B}_h^t = 121e^2 \cdot \sqrt{\frac{H^2(\beta^{\text{max}}(\delta, T))^2}{e_k}} + 2401e \cdot \frac{H(\beta^{\text{max}}(\delta, T))^4}{e_k} + \frac{5L \cdot d_{\max}}{\sqrt{He_k}} \quad (19) $$

where $k = k_h^t(B_h^t)$ and $\beta^{\text{max}}(\delta, T) = \max\{\beta^*(\delta, T), \beta^B(\delta), \beta^{\text{conc}}(\delta), \beta(\delta)\}$. Also we can express this bound in terms of a diameter of $B_h^t$ as follows

$$ \begin{aligned} \text{diam}(B_h^t) &\ge \frac{d_{\max}}{2\sqrt{n_h^t(B_h^t)}} \ge \frac{d_{\max}}{2\sqrt{\sum_{i=0}^k e_i}} \ge \frac{d_{\max}}{2\sqrt{H \sum_{i=0}^k (1+1/H)^i}} \ge \frac{d_{\max}}{2\sqrt{H}} \\ &\ge \frac{d_{\max}}{2\sqrt{H^2(1+1/H)^{k+1}}} \ge \frac{d_{\max}}{2\sqrt{2He_k}}, \end{aligned} $$
thus

$$ \frac{1}{\sqrt{He_k}} \leq \frac{3\mathrm{diam}(B_h^t)}{d_{\mathrm{max}}}, $$

and we have

$$ \begin{aligned} B_h^t &\leq 7566e^2 H^{3/2} (\beta^{\max}(\delta, T))^4 \mathrm{diam}(B_h^t) / d_{\mathrm{max}} + 15L \mathrm{diam}(B_h^t) \\ &\leq \rho(H, \delta, L) \cdot \mathrm{diam}(B_h^t), \end{aligned} \quad (20) $$

where we define $\rho(H, \delta, L) \triangleq 7566e^2 H^{3/2} (\beta^{\max}(\delta, T))^4 / d_{\mathrm{max}} + 15L$.

As an additional corollary, we have for all $t \in [T]$, $h \in [H]$

$$ \bar{V}_h^t(s) = \max_{B \in \mathcal{R}_h^t(s)} \bar{Q}_h^t(B) = \bar{Q}_h^t(B^*) \geq Q_h^*(s, \pi^*(s)) = V_h^*(s), \quad (21) $$

where $B^*$ is a ball that contains a pair $(s, \pi^*(s))$.

This upper and lower bound have the similar structure as Lemma D.2 by Sinclair et al. [2023] and the rest of the proof directly follows [Sinclair et al., 2023].

**Clipping techniques** Next we introduce the required clipping techniques developed by Simchowitz and Jamieson [2019], Cao and Krishnamurthy [2020]. Definition 2 introduces the quantity $\mathrm{gap}_h(s, a) = V_h^*(s) - Q_h^*(s, a)$, and for any compact set $B \subseteq S \times A$ we define $\mathrm{gap}_h(B) = \min_{(s,a) \in B} \mathrm{gap}_h(s, a)$. Finally, we define clipping operator for any $\mu, \nu \in \mathbb{R}$

$$ \mathrm{clip}(\mu|\nu) = \mu 1\{\mu \leq \nu\}. \quad (22) $$

In particular, this operator satisfies the following important property

**Lemma 8 (Lemma E.2. of Sinclair et al. [2023]).** Suppose that $\mathrm{gap}_h(B) \leq \psi \leq \mu_1 + \mu_2$ for any $\psi, \mu_1, \mu_2$. Then

$$ \psi \leq \mathrm{clip} \left[ \mu_1 \left| \frac{\mathrm{gap}_h(B)}{H+1} \right| + \left( 1 + \frac{1}{H} \right) \mu_2 \right] $$

Now we apply this lemma to our update rules, producing a result similar to Lemma E.3 of Sinclair et al. [2023]. We notice that

$$ \begin{aligned} \mathrm{gap}_h(B_h^t) &\leq \mathrm{gap}_h(s_h^t, a_h^t) = V_h^*(s_h^t) - Q_h^*(s_h^t, a_h^t) \\ &\leq \bar{V}_h^t(s_h^t) - Q_h^*(s_h^t, a_h^t) = \bar{Q}_h^t(B_h^t) - Q_h^*(s_h^t, a_h^t). \end{aligned} $$

Thus, denoting $\psi = \bar{Q}_h^t(B_h^t) - Q_h^*(s_h^t, a_h^t)$ and, by (18),

$$ \mu_1 = H1\{He_{k_h^t}/2 > k_h^t + H^2\} + \mathcal{B}_h^t, \quad \mu_2 = \frac{1}{e_k} \sum_{i=1}^{e_k} [\bar{V}_{h+1}^{\ell_i}(s_{h+1}^{\ell_i}) - V_{h+1}^*(s_{h+1}^{\ell_i})] $$

we apply Lemma 8 and obtain

$$ \begin{aligned} \bar{V}_h^t(s_h^t) - Q_h^*(s_h^t, a_h^t) \leq \mathrm{clip} \left[ H1\{He_{k_h^t}/2 \leq k_h^t + H^2\} + \mathcal{B}_h^t \left| \frac{\mathrm{gap}_h(B_h^t)}{H+1} \right. \right] \\ + \left(1 + \frac{1}{H}\right) \frac{1}{e_k} \sum_{i=1}^{e_k} \left[ \bar{V}_{h+1}^{\ell_i}(s_{h+1}^{\ell_i}) - V_{h+1}^*(s_{h+1}^{\ell_i}) \right] \end{aligned} \quad (23) $$

for $k_h^t = k_h^t(B_h^t)$ and $\mathcal{B}_h^t$ defined in (19).

**Regret decomposition** The rest of the analysis we perform conditionally on event $\mathcal{G}'(\delta) = \mathcal{G}(\delta) \cap \mathcal{E}_{\mathrm{opt}}$ that holds with probability at least $1 - \delta$.

By defining $\delta_h^t = \bar{V}_h^t(s_h^t) - V^{\pi^t}(s_h^t)$ and $\zeta_h^t = \bar{V}_h^t(s_h^t) - V_h^*(s_h^t)$ we have

$$ \mathfrak{R}^T = \sum_{t=1}^{T} V_1^*(s_1^t) - V_1^{\pi^t}(s_1^t) \leq \sum_{t=1}^{T} \delta_1^t, $$
and, at the same time, by Bellman equations

$$
\begin{align*}
\delta_h^t &= \bar{V}_h^t(s_h^t) - Q^{\pi_h^t}(s_h^t, a_h^t) = \bar{V}_h^t(s_h^t) - Q_h^*(s_h^t, a_h^t) + Q_h^*(s_h^t, a_h^t) - Q^{\pi^t}(s_h^t, a_h^t) \\
&= \bar{V}_h^t(s_h^t) - Q_h^*(s_h^t, a_h^t) + V_{h+1}^*(s_{h+1}^t) - V_h^{\pi^t}(s_{h+1}^t) + \xi_h^t \\
&= \bar{V}_h^t(s_h^t) - Q_h^*(s_h^t, a_h^t) + \delta_{h+1}^t - \zeta_{h+1}^t + \xi_h^t,
\end{align*}
$$

where $\xi_h^t = p_h[V_{h+1}^* - V_{h+1}^{\pi^t}](s_h^t, a_h^t) - [V_{h+1}^* - V_{h+1}^{\pi^t}](s_{h+1}^t)$ is a martingale-difference sequence.
By (23) we have

$$
\begin{align*}
\sum_{t=1}^{T} \delta_h^t &= \sum_{t=1}^{T} \bar{V}_h^t(s_h^t) - Q_h^*(s_h^t, a_h^t) + \delta_{h+1}^t - \zeta_{h+1}^t + \xi_h^t \\
&\le \left(1 + \frac{1}{H}\right) \sum_{t=1}^{T} \frac{1}{e_{k_h^t}} \sum_{i=1}^{e_{k_h^t}} \zeta_{h+1}^{\ell_{k_h^t}^i} + \sum_{t=1}^{T} \delta_{h+1}^t - \sum_{t=1}^{T} \zeta_{h+1}^t + \sum_{t=1}^{T} \xi_h^t \\
&\quad + \sum_{t=1}^{T} \text{clip} \left[ H1\{He_{k_h^t}^t/2 > k_h^t + H^2\} + B_h^t(k_h^t) \middle| \frac{\text{gap}_h(B_h^t)}{H+1} \right]
\end{align*}
$$

where $k_h^t = k_h^t(B_h^t)$. Repeating argument of Lemma 5 and Zhang et al. [2020]

$$
\left(1 + \frac{1}{H}\right) \sum_{t=1}^{T} \frac{1}{e_{k_h^t}} \sum_{i=1}^{e_{k_h^t}} \zeta_{h+1}^{\ell_{k_h^t}^i} \le \left(1 + \frac{1}{H}\right)^2 \sum_{t=1}^{T} \zeta_{h+1}^t \le \left(1 + \frac{3}{H}\right) \sum_{t=1}^{T} \zeta_{h+1}^t.
$$

Using an upper bound $\zeta_h^t \le \delta_h^t$ we have for any $h \ge 1$

$$
\sum_{t=1}^{T} \delta_h^t \le \left(1 + \frac{3}{H}\right) \sum_{t=1}^{T} \delta_{h+1}^t + \sum_{t=1}^{T} \xi_h^t \\
+ \sum_{t=1}^{T} \text{clip} \left[ H1\{He_{k_h^t}^t/2 \le k_h^t + H^2\} + B_h^t \middle| \frac{\text{gap}_h(B_h^t)}{H+1} \right],
$$

and, rolling out starting with $h = 1$ we have the following regret decomposition

$$
\Re^T \le e^3 \sum_{t=1}^{T} \sum_{h=1}^{H} H1\{He_{k_h^t}^t/2 \le k_h^t + H^2\} = (A)
$$

$$
+ e^3 \sum_{t=1}^{T} \sum_{h=1}^{H} \text{clip} \left[ B_h^t \middle| \frac{\text{gap}_h(B_h^t)}{H+1} \right] = (B)
$$

$$
+ \sum_{t=1}^{T} \sum_{h=1}^{H} (1 + 3/H)^{H-h} \xi_h^t. \qquad = (C)
$$

**Term (A)** For this term we notice that for any fixed $h$ the following event

$$
He_{k_h^t} \le 2(k_h^t + H^2) \iff H \lfloor H(1 + 1/H)^{k_h^t} \rfloor \le 2(k_h^t + H^2),
$$

that is guaranteed if

$$
(1 + 1/H)^{k_h^t} \le 2T + 3 \iff k_h^t \log(1 + 1/H) \le \log(2T/H^2 + 3).
$$

Thus, indicator can be equal to 1 no more than $H \log(2T + 3)$ times for any $t \in [T]$. As a result,

$$
(\mathbf{A}) \le e^2 H^3 \log(2T + 3).
$$
**Term (B)** Let us rewrite this term using a definition of clipping operator and use the definition of near-optimal set (see Definition 3)

$$ (\mathbf{B}) = e^3 \sum_{t=1}^{T} \sum_{h=1}^{H} \mathcal{B}_h^t \mathbf{1}\{(H+1)\mathcal{B}_h^t \ge \text{gap}_h(\mathcal{B}_h^t)\} \le e^3 \sum_{t=1}^{T} \sum_{h=1}^{H} \mathcal{B}_h^t \mathbf{1}\{\text{center}(\mathcal{B}_h^t) \in Z_h^{\mathcal{B}_h^t}\}. $$

Next we consider the summation for a fixed $h$. Here we follow Theorem F.3 by Sinclair et al. [2023] and obtain

$$ \sum_{t=1}^{T} \mathcal{B}_h^t \mathbf{1}\{\text{center}(\mathcal{B}_h^t) \in Z_h^{\mathcal{B}_h^t}\} = \sum_{r} \sum_{B:\text{diam}(B)=r} \sum_{t:B_h^t=B} \mathcal{B}_h^t \mathbf{1}\{\text{center}(B) \in Z_h^{\mathcal{B}_h^t}\}, $$

where we applied an additional rescaling by a function $\rho$ defined in (20).

Next we fix a constant $r_0 > 0$ and break a summation into two parts: $r \ge r_0$ and $r \le r_0$.

1. Case $r \le r_0$. In this situation we have can apply (20)

$$ \sum_{r \le r_0} \sum_{B:\text{diam}(B)=r} \sum_{t:B_h^t=B} \mathcal{B}_h^t \mathbf{1}\{\text{center}(B) \in Z_h^{\mathcal{B}_h^t}\} \\ = \mathcal{O}(\text{Tr}_0 \rho(H, \delta, L)). $$

2. Case $r \ge r_0$. In this situation we also apply (20) under the indicator function

$$ \sum_{r \ge r_0} \sum_{B:\text{diam}(B)=r} \sum_{t:B_h^t=B} \mathcal{B}_h^t \mathbf{1}\{\text{center}(B) \in Z_h^{\mathcal{B}_h^t}\} \\ \le \sum_{r \ge r_0} \sum_{B:\text{diam}(B)=r \cdot \rho(H, \delta, L)} \mathbf{1}\{\text{center}(B) \in Z_h^{\rho(H, \delta, L) \cdot r}\} \sum_{t:B_h^t=B} \mathcal{B}_h^t. $$

To upper bound the last sum we repeat the argument of (14) and apply (16), using the fact that $\text{diam}(B) = r \cdot \rho(H, \delta, L)$

$$ \sum_{t:B_h^t=B} \frac{1}{\sqrt{e_k}} \le \sum_{k=0}^{k_h^T(B)} \frac{e_{k+1}}{\sqrt{e_k}} \le 4H \sqrt{e^{k_h^T(B)+1}} \\ \le 4\sqrt{H(n_h^{T+1}(B)+1)} \le 4\sqrt{2H} \cdot \frac{d_{\max}}{\text{diam}(B)} = \frac{\sqrt{32H} \cdot d_{\max}}{r}. $$

As a result, we have by (19)

$$ \sum_{t:B_h^t=B} \mathcal{B}_h^t \le \frac{\sqrt{32H} \cdot d_{\max}}{r} \cdot \left( 2522e^2 H (\beta^{\max}(\delta, T))^4 + 5L d_{\max} / \sqrt{H} \right) $$

and

$$ \sum_{r \ge r_0} \sum_{B:\text{diam}(B)=r} \sum_{t:B_h^t=B} \mathcal{B}_h^t \mathbf{1}\{\text{center}(B) \in Z_h^{\mathcal{B}_h^t}\} \\ = \mathcal{O}\left(\sum_{r \ge r_0} N_r (Z_h^{\rho(H, \delta, L) \cdot r}) \cdot \frac{H^{3/2} d_{\max} (\beta^{\max}(\delta, T))^4 + L d_{\max}^2}{r}\right). $$

Finally, by an arbitrary choice of $r_0$ and a definition of zooming dimension with a scaling $\rho = \rho(H, \delta, L)$ (Definition 4)

$$ (\mathbf{B}) = \mathcal{O}\left( (H^{3/2} d_{\max}(\beta^{\max}(\delta, T))^4 + L d_{\max}^2) \cdot \sum_{h=1}^{H} \inf\left\{ \text{Tr}_0 + \sum_{r \ge r_0} \frac{C_{N,h}}{\tilde{r}^{d_{z,h}+1}} \right\} \right). $$
**Term (C)** For this term we just apply definition of the main event $G(\delta) \supseteq \mathcal{E}(\delta)$ and obtain

$$ (C) = \mathcal{O}\left(\sqrt{H^3 T \beta^{\max(\delta, T)}}\right). $$

**Final regret bound** First, we notice that $\beta^{\max(\delta,T)} = \tilde{\mathcal{O}}(d_c)$, therefore we have

$$ \mathfrak{R}^T = \tilde{\mathcal{O}}\left( H^3 d_c + (H^{3/2} d_c^4 + L) \sum_{h=1}^{H} \inf_{r_0>0} \left\{ \mathrm{Tr}_0 + \sum_{r \ge r_0} \frac{C_{N,h}}{r^{d_{z,h}+1}} \right\} + \sqrt{H^3 T d_c} \right). $$

Taking $r_0 = K^{-d_{z,h}+1/2}$ for each $h$ and summing the geometric series we conclude the statement. $\square$

<figure><img src="image_5.png" /></figure>
# G Deviation and Anti-Concentration Inequalities

## G.1 Deviation inequality for $K_{inf}$

For a measure $\nu \in \mathcal{P}([0, b])$ supported on a segment $[0, b]$ (equipped with a Borel $\sigma$-algebra) and a number $\mu \in [0, b]$ we recall the definition of the minimum Kullback-Leibler divergence

$$ K_{inf}(\nu, \mu) \triangleq \inf\{\text{KL}(\nu, \eta) : \eta \in \mathcal{P}([0, b]), \nu \ll \eta, \mathbb{E}_{X \sim \eta}[X] \geq \mu\}. $$

As the Kullback-Leibler divergence this quantity admits a variational formula.

**Lemma 9** (Lemma 18 by Garivier et al., 2018). For all $\nu \in \mathcal{P}([0, b])$, $u \in [0, b)$,

$$ K_{inf}(\nu, u) = \max_{\lambda \in [0,1]} \mathbb{E}_{X \sim \nu} \left[ \log \left( 1 - \lambda \frac{X-u}{b-u} \right) \right], $$

moreover if we denote by $\lambda^*$ the value at which the above maximum is reached, then

$$ \mathbb{E}_{X \sim \nu} \left[ \frac{1}{1 - \lambda^* \frac{X-u}{b-u}} \right] \leq 1. $$

**Remark 2.** Contrary to Garivier et al. [2018] we allow that $u = 0$ but in this case Lemma 9 is trivially true, indeed

$$ K_{inf}(\nu, 0) = 0 = \max_{\lambda \in [0,1]} \mathbb{E}_{X \sim \nu} \left[ \log \left( 1 - \lambda \frac{X}{b} \right) \right]. $$

Let $(X_t)_{t \in \mathbb{N}^*}$ be i.i.d. samples from a measure $\nu$ supported on $[0, b]$. We denote by $\hat{\nu}_n \in \mathcal{P}([0, b])$ the empirical measure $\hat{\nu}_n = \sum_{i=1}^n \delta_{X_i}$, where $\delta_{X_i}$ is a Dirac measure on $X_i \in [0, b]$.

We are now ready to state the deviation inequality for the $K_{inf}$ by Tiapkin et al. [2022b] which is a self-normalized version of Proposition 13 by Garivier et al. [2018]. Notice that this inequality is stated in terms of slightly less general definition of $K_{inf}$, however, the proof remains completely the same.

**Theorem 4.** For all $\nu \in \mathcal{P}([0, b])$ and for all $\delta \in [0, 1]$,

$$ \mathbb{P}(\exists n \in \mathbb{N}^*, n K_{inf}(\hat{\nu}_n, \mathbb{E}_{X \sim \nu}[X]) > \log(1/\delta) + 3 \log(e\pi(1+2n))) \leq \delta. $$

## G.2 Anti-concentration Inequality for Dirichlet Weighted Sums

In this section we state anti-concentration inequality by Tiapkin et al. [2022a] in terms of slightly different definition of $K_{inf}$.

$$ c_0(\varepsilon) = \left( \frac{4}{\sqrt{\log(17/16)}} + 8 + \frac{49 \cdot 4\sqrt{6}}{9} \right)^2 \frac{2}{\pi \cdot \varepsilon^2} + \log_{17/16} \left( \frac{5}{32 \cdot \varepsilon^2} \right). \quad (24) $$

**Theorem 5** (Lower bound). For any $\alpha = (\alpha_0 + 1, \alpha_1, \dots, \alpha_m) \in \mathbb{R}_{++}^{m+1}$ define $\bar{p} \in \Delta_m$ such that $\bar{p}(\ell) = \alpha_\ell/\bar{\alpha}, \ell = 0, \dots, m$, where $\bar{\alpha} = \sum_{j=0}^m \alpha_j$. Let $\varepsilon \in (0, 1)$. Assume that $\alpha_0 \ge c_0(\varepsilon) + \log_{17/16}(\bar{\alpha})$ for $c_0(\varepsilon)$ defined in (24), and $\bar{\alpha} \ge 2\alpha_0$. Then for any $f: \{0, \dots, m\} \to [0, b_0]$ such that $f(0) = b_0, f(j) \le b < b_0/2, j \in \{1, \dots, m\}$ and $\mu \in (\bar{p}f, b_0)$

$$ \mathbb{P}_{w \sim \text{Dir}(\alpha)}[wf \ge \mu] \ge (1-\varepsilon)\mathbb{P}_{g \sim \mathcal{N}(0,1)} \left[ g \ge \sqrt{2\bar{\alpha} K_{\text{inf}} \left( \sum_{i=0}^{m} \bar{p}(i) \cdot \delta_{f(i)}, \mu \right)} \right]. $$

Next we formulate a simple corollary of Theorem 5, that slightly relaxes assumptions of this theorem under assumption $\mu < b \le b_0/2$.
**Lemma 10.** For any $\alpha = (\alpha_0 + 1, \alpha_1, \dots, \alpha_m) \in \mathbb{R}_{++}^{m+1}$ define $\bar{p} \in \Delta_m$ such that $\bar{p}(\ell) = \alpha_\ell/\bar{\alpha}, \ell = 0, \dots, m$, where $\bar{\alpha} = \sum_{j=0}^m \alpha_j$. Also define a measure $\bar{\nu} = \sum_{i=0}^m \bar{p}(i) \cdot \delta_{f(i)}$.

Let $\varepsilon \in (0, 1)$. Assume that $\alpha_0 \ge c_0(\varepsilon) + \log_{17/16}(2(\bar{\alpha} - \alpha_0))$ for $c_0(\varepsilon)$ defined in (24). The for any $f: \{0, \dots, m\} \to [0, b_0]$ such that $f(0) = b_0, f(j) \le b \le b_0/2, j \in [m]$, and any $\mu \in (0, b)$

$$ \mathbb{P}_{w \sim \text{Dir}(\alpha)}[wf \ge \mu] \ge (1 - \varepsilon) \mathbb{P}_{g \sim \mathcal{N}(0,1)} \left[ g \ge \sqrt{2\bar{\alpha} \mathcal{K}_{\text{inf}}(\bar{\nu}, \mu)} \right]. $$

*Proof.* Assume that assumption $\bar{\alpha} \ge 2\alpha_0$ holds.

Then we show that the Theorem 5 also holds for $\mu \le \bar{p}f$. First, we notice that for any $\gamma > 0$

$$ \mathbb{P}_{w \sim \text{Dir}(\alpha)}[wf \ge \mu] \ge \mathbb{P}_{w \sim \text{Dir}(\alpha)}[wf \ge \bar{p}f + \gamma] \ge (1 - \varepsilon) \mathbb{P}_{g \sim \mathcal{N}(0,1)} \left[ g \ge \sqrt{2\bar{\alpha} \mathcal{K}_{\text{inf}}(\bar{\nu}, \bar{p}f + \gamma)} \right]. $$

By continuity of $\mathcal{K}_{\text{inf}}$ in its second argument (see Theorem 7 by Honda and Takemura [2010]) we can tend $\gamma$ to zero, and then use an equality $\mathcal{K}_{\text{inf}}(\bar{\nu}, \bar{p}f) = \mathcal{K}_{\text{inf}}(\bar{\nu}, \mu) = 0$.

Next, assume $\bar{\alpha} \le 2\alpha_0$. In this case we have $\bar{p}f \ge b$, thus for any $0 \le \mu \le b$

$$ \mathbb{P}_{w \sim \text{Dir}(\alpha)}[wf \ge \mu] \ge \mathbb{P}_{\xi \sim \text{Beta}(\alpha_0+1, \bar{\alpha}-\alpha_0)}[b_0\xi \ge \mu] \ge \mathbb{P}_{\xi \sim \text{Beta}(\alpha_0+1, \bar{\alpha}-\alpha_0)} \left[ \xi \ge \frac{1}{2} \right], $$

where we first apply a lower bound $f(j) \ge 0$ for all $j > 0$ and $f(0) = b_0$, and second apply a bound $\mu \le b_0/2$. Here we may apply the result of Alfers and Dinges [1984, Theorem 1.2"] and obtain the following lower bound

$$ \mathbb{P}_{w \sim \text{Dir}(\alpha)}[wf \ge \mu] \ge \Phi\left(-\text{sign}(\alpha_0/\bar{\alpha} - 1/2) \cdot \sqrt{2\bar{\alpha} \text{kl}(\alpha_0/\bar{\alpha}, 1/2)}\right) \ge (1 - \varepsilon) \mathbb{P}_{g \sim \mathcal{N}(0,1)}[g \ge 0] $$

where we used $\alpha_0/\bar{\alpha} > 1/2$.

### G.3 Rosenthal-type inequality

In this section we state Rosenthal-type inequality for martingale differences by [Pinelis, 1994, Theorem 4.1]. The exact constants could be derived from the proof.

**Theorem 6.** Let $X_1, \dots, X_n$ be a martingale-difference sequence adapted to a filtration $\{\mathcal{F}_i\}_{i=1,\dots,n}$: $\mathbb{E}[X_i|\mathcal{F}_i] = 0$. Define $\mathcal{V}_i = \mathbb{E}[X_i^2|\mathcal{F}_{i-1}]$. Then for any $p \ge 2$ the following holds

$$ \mathbb{E}^{1/p} \left[ \left| \sum_{i=1}^{n} X_i \right|^p \right] \le C_1 p^{1/2} \mathbb{E}^{1/p} \left[ \left| \sum_{i=1}^{n} \mathcal{V}_i \right|^{p/2} \right] + 2C_2 p \mathbb{E}^{1/p} \left[ \max_{i \in [n]} |X_i|^p \right], $$

where $C_1 = 60e, C_2 = 60$.

Additionally, we need some additional lemma to use this inequality in our setting.

**Definition 7.** A random variable $X$ is called sub-exponential with parameters $(\sigma^2, b)$ if the following tail condition holds for any $t > 0$

$$ \mathbb{P}[|X - \mathbb{E}[X]| \ge t] \le 2 \exp \left( - \frac{t^2}{2\sigma^2 + 2bt} \right). $$

By Theorem 1 of Skorski [2023] we have for any $\xi \in B(\alpha, \beta)$ with $\beta \ge \alpha$ and any $t > 0$

$$ \mathbb{P}[|\xi - \mathbb{E}[\xi]| \ge t] \le 2 \exp \left( - \frac{t^2}{2(v + ct/3)} \right), $$

where

$$ v = \frac{\alpha\beta}{(\alpha + \beta)^2(\alpha + \beta + 1)} \le \frac{\alpha}{(\alpha + \beta)^2}, \quad c = \frac{2(\beta - \alpha)}{(\alpha + \beta)(\alpha + \beta + 2)} \le \frac{2}{\alpha + \beta}, $$

so $\xi$ is $(\alpha/(\alpha + \beta)^2, 2/(3(\alpha + \beta)))$ sub-exponential.
**Lemma 11.** Let $X_1, \dots, X_n$ be a sequence of centred $(\sigma^2, b)$ sub-exponential random variables, not necessarily independent. Then for any $p \ge 2$

$$ \mathbb{E}\left[\max_{\ell \in [n]} |X_\ell|^p\right] \le \max\{\sqrt{8\sigma^2 \log n}, 8b \log n\}^p + e(2\sigma)^p p^{p/2} + 2e(8b)^p p^p. $$

*Proof.* By Fubini theorem we have for any $\eta \ge 0$: $\mathbb{E}[\eta^p] = p \int_0^\infty u^{p-1} \mathbb{P}[\eta \ge u] du$, thus for any $a > 0$ the following holds

$$ \begin{aligned} \mathbb{E}\left[\max_{\ell \in [n]} |X_\ell|^p\right] &= p \int_0^\infty u^{p-1} \mathbb{P}\left[\max_{\ell \in [n]} |X_\ell - \mathbb{E}[X_\ell]| \ge u\right] du \\ &\le a^p + p \int_a^\infty u^{p-1} \mathbb{P}[\exists \ell \in [n] : |X_\ell| \ge u] du \\ &\le a^p + 2p \int_a^\infty u^{p-1} n \exp\left(-\frac{u^2}{2(\sigma^2 + bu)}\right) du. \end{aligned} $$

By selecting $a = \max\{\sqrt{8\sigma^2 \log n}, 8b \log n\}$ we have

$$ n \exp\left(-\frac{u^2}{2(\sigma^2 + bu)}\right) \le \exp\left(-\frac{u^2}{4(\sigma^2 + bu)}\right) \le \exp\left(-\frac{u^2}{8\sigma^2}\right) + \exp\left(-\frac{u}{8b}\right) $$

for any $u \ge a$, thus

$$ \begin{aligned} \mathbb{E}\left[\max_{\ell \in [n]} |X_\ell|^p\right] &\le \max\{\sqrt{8\sigma^2 \log n}, 8b \log n\}^p \\ &\quad + 2p \int_a^\infty u^{p-1} \exp\left(-\frac{u^2}{8\sigma^2}\right) du + 2p \int_a^\infty u^{p-1} \exp\left(-\frac{u}{8b}\right) du \\ &\le \max\{\sqrt{8\sigma^2 \log n}, 8b \log n\}^p + p(2\sqrt{2\sigma})^p \Gamma(p/2) + 2p(8b)^p \Gamma(p). \end{aligned} $$

By the bounds on Gamma-function we have

$$ p\Gamma(p/2) = \Gamma(p/2 + 1) \le (p + 1)^{(p+1)/2} 2^{-(p+1)/2} e^{1-p/2} \le ep^{p/2} 2^{-p/2} $$

and $p\Gamma(p) = \Gamma(p+1) \le (p+1/2)^{p+1/2} e^{1-p} \le ep^p$ (see Guo et al. [2007]), thus

$$ \mathbb{E}\left[\max_{\ell \in [n]} |X_\ell|^p\right] \le \max\{\sqrt{8\sigma^2 \log n}, 8b \log n\}^p + e(2\sigma)^p p^{p/2} + 2e(8b)^p p^p. $$

□

**Proposition 7.** Let $(Y_t, w_t)_{t=1,...,n}$ be a sequence of random variables, where $w_t$ are Beta$(1/\kappa, (t+t_0)/\kappa)$, and let $(\mathcal{F}_t)_{t=t,...,n}$ be a filtration such that 1) $Y_t$ are $\mathcal{F}_{t-1}$-measurable (i.e., predictable), 2) $w_t$ is $\mathcal{F}_t$-measurable (i.e., adapted to $\mathcal{F}_t$), 3) $\mathbb{E}[w_t|\mathcal{F}_{t-1}] = \mathbb{E}[w_t]$, 4) $Y_t \in [0, 1]$ almost surely.

Then, consider the following two sequences:

$$ X_t \triangleq (1 - w_t)X_{t-1} + w_t \cdot Y_t, \quad \bar{X}_t \triangleq (1 - \bar{w}_t)\bar{X}_{t-1} + \bar{w}_t \cdot Y_t, $$

where $\bar{w}_t = \mathbb{E}[w_t]$ and $X_0 = \bar{X}_0 = 1$. Then, with probability at least $1 - \delta$, the following holds

$$ |X_n - \bar{X}_n| \le 60e^2 \sqrt{\frac{\kappa \log(1/\delta)}{n + t_0}} + 1200e \frac{\kappa \log(n) \log^2(1/\delta)}{n + t_0}. $$

*Proof.* First, we notice that

$$ \begin{aligned} X_t - \bar{X}_t &= (1 - w_t)X_{t-1} + w_t Y_t - (1 - \bar{w}_t)\bar{X}_{t-1} + \bar{w}_t Y_t \\ &= (1 - \bar{w}_t)(X_t - \bar{X}_t) + (w_t - \bar{w}_t)(Y_t - X_{t-1}), \end{aligned} $$

wherefore we have $\mathbb{E}[X_t - \bar{X}_t|\mathcal{F}_{t-1}] = (1 - \bar{w}_t)(X_{t-1} - \bar{X}_{t-1})$. Notice that it is not a martingale, but instead we can consider the following martingale

$$ Z_t \triangleq \frac{X_t - \bar{X}_t}{P_t}, \quad P_t \triangleq \prod_{j=1}^{t} (1 - \bar{w}_t). $$
It is easy to check that $Z_t$ is a martingale: $\mathbb{E}[Z_t] = \mathbb{E}[(X_t - \bar{X}_t)/P_t|\mathcal{F}_{t-1}] = (1-\bar{w}_t)(X_t - \bar{X}_t)/P_t = (X_t - \bar{X}_t)/P_{t-1}$. Thus, defining $\Delta_t = Z_t - Z_{t-1}$, we apply Theorem 6:

$$ \mathbb{E}^{1/p} [|Z_n|^p] \le 60e\sqrt{p} \cdot \mathbb{E}^{1/p} \left[ \left| \sum_{t=1}^n \mathcal{V}_t \right|^{p/2} \right] + 120p \cdot \mathbb{E}^{1/p} \left[ \max_{t \in [n]} |\Delta_t|^p \right], \quad (25) $$

where $\mathcal{V}_t = \mathbb{E}[(\Delta_t)^2|\mathcal{F}_{t-1}]$. Next, we compute $\Delta_t$ and $P_t$ as follows

$$ \Delta_t = \frac{X_t - \bar{X}_t}{P_t} - \frac{X_{t-1} - \bar{X}_{t-1}}{P_{t-1}} = \frac{(w_t - \bar{w}_t)(Y_t - \bar{X}_{t-1})}{P_t}, \quad P_t = \prod_{j=1}^{t} \left(1 - \frac{1}{j + t_0}\right) = \frac{t_0}{t + t_0}. $$

Next, we are going to bound all the terms in the (25). We start from the variance term by noting that

$$ \mathcal{V}_t = \frac{(Y_t - \bar{X}_{t-1})^2}{P_t^2} \mathrm{Var}(w_t) \le \frac{(t+t_0)^2}{t_0^2} \cdot \frac{\kappa}{(t+t_0+1)^2} \le \frac{\kappa}{t_0^2}, $$

and, as a result,

$$ \mathbb{E}^{1/p} \left[ \left| \sum_{t=1}^{n} \mathcal{V}_t \right|^{p/2} \right] \le \sqrt{\frac{n \cdot \kappa}{t_0^2}}. $$

For the second term, we first upper-bound $\Delta_t$ as $|\Delta_t| \le \frac{|w_t - \bar{w}_t|}{P_t}$, and then we notice that $|w_t - \bar{w}_t|$ is sub-exponential with parameter $(\kappa/(t+t_0)^2, 2\kappa/3(t+t_0))$ and, as a result, $|w_t - \bar{w}_t|/P_t$ are $(\kappa/t_0^2, 2\kappa/(3t_0))$-subexponential for any $t$. Therefore, Lemma 11 implies

$$ \mathbb{E} \left[ \max_{t \in [n]} |\Delta_t|^p \right] \le \max \left\{ \sqrt{8\kappa/t_0^2 \log(n)}, 16/3 \cdot \kappa/t_0 \cdot \log(n) \right\}^p + e\left(2\kappa/t_0^2\right)^p \cdot p^{p/2} + 2e\left(16\kappa/3t_0\right)^p \cdot p^p \le \left(20 \cdot \kappa/t_0 p \cdot \log(n)\right)^p. $$

Thus, we have

$$ \mathbb{E}^{1/p} [|Z_n|^p] \le \frac{60e}{t_0} \sqrt{n \cdot \kappa \cdot p} + 1200 \cdot \frac{\kappa \cdot p^2 \cdot \log(n)}{t_0}. $$

Next, we plug-in into this inequality $Z_n = (X_n - \bar{X}_n)/P_n$ and achieve the following bound

$$ \mathbb{E}^{1/p} [|X_n - \bar{X}_n|^p] \le 60e \sqrt{\frac{\kappa \cdot p}{n + t_0}} + 1200 \cdot \frac{\kappa \cdot p^2 \cdot \log(n)}{n + t_0}. $$

Next we turn from moments to tails. By Markov inequality with $p = \log(1/\delta)$

$$ \begin{aligned} \mathbb{P}[|X_n - \bar{X}_n| \ge t] & \le \left( \frac{\mathbb{E}^{1/p} [|X_n - \bar{X}_n|^p]}{t} \right)^p \\ & \le \left( \frac{60eB \sqrt{\frac{\kappa \log(1/\delta)}{n+t_0}} + 1200 \log^2(1/\delta) B \kappa \frac{\log(n)}{n+t_0}}{t} \right)^{\log(1/\delta)}. \end{aligned} $$

Taking $t = 60e^2 B \sqrt{\frac{\kappa \log(1/\delta)}{n+t_0}} + 1200eB \frac{\kappa \log(n) \log^2(1/\delta)}{n+t_0}$ we conclude the statement. $\square$

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

## H Technical Lemmas

**Lemma 12.** Let $\nu \in \mathcal{P}([0, b])$ be a probability measure over the segment $[0, b]$ and let $\bar{\nu} = \alpha\delta_{b_0} + (1-\alpha) \cdot \nu$ be a mixture between $\nu$ and a Dirac measure on $b_0 > b$. Then for any $\mu \in (0, b)$

$$ K_{\mathrm{inf}}(\bar{\nu}, \mu) \le (1 - \alpha) K_{\mathrm{inf}}(\nu, \mu). $$
<figure><img src="image_7.png" /><figcaption>Figure 2: Regret curves of RandQL, Staged-RandQL and Sampled-RandQL on a grid-world environment with 100 states and 4 actions for $H = 50$ an transitions noise 0.2. We show average over 4 seeds.</figcaption></figure>

*Proof.* By a variational formula for $\mathcal{K}_{\inf}$ (see Lemma 9)

$$ \mathcal{K}_{\inf}(\bar{\nu}, \mu) = \max_{\lambda \in [0, 1/(b_0 - \mu)]} \mathbb{E}_{X \sim \bar{\nu}}[\log(1 - \lambda(X - \mu))] $$

Since $\bar{\nu}$ is a mixture, we have for any $\lambda \in [0, 1/(b_0 - \mu)]$

$$ \mathbb{E}_{X \sim \bar{\nu}}[\log(1 - \lambda(X - \mu))] = (1 - \alpha)\mathbb{E}_{X \sim \bar{\nu}}[\log(1 - \lambda(X - \mu))] + \alpha \log(1 - \lambda(b_0 - \mu)). $$

Notice that $\max_{\lambda>0} \log(1 - \lambda(b_0 - \mu)) = 0$. Thus, maximizing each term separately over $\lambda$, we have

$$ \begin{aligned} \mathcal{K}_{\inf}(\bar{\nu}, \mu) &\le (1 - \alpha) \max_{\lambda \in [0, 1/(b_0 - \mu)]} \mathbb{E}_{X \sim \bar{\nu}}[\log(1 - \lambda(X - \mu))] \\ &\le (1 - \alpha) \max_{\lambda \in [0, 1/(b_0 - \mu)]} \mathbb{E}_{X \sim \bar{\nu}}[\log(1 - \lambda(X - \mu))] = (1 - \alpha) \mathcal{K}_{\inf}(\nu, \mu). \end{aligned} $$

□

# I Experimental details

In this section, we detail the experiments we conducted for tabular and non-tabular environments. For all experiments, we used 2 CPUs (Intel Xeon CPU 2.20GHz), and no GPU was used. Each experiment took approximately one hour.

## I.1 Tabular experiments

In our initial experiment, we investigated a simple grid-world environment.

**Environments** For tabular experiments we use two environments.

The first one is a grid-world environment with 100 states $(i, j) \in [10] \times [10]$ and 4 actions (left, right, up and down). The horizon is set to $H = 50$. When taking an action, the agent moves in the corresponding direction with probability $1 - \varepsilon$, and moves to a neighbor state at random with probability $\varepsilon = 0.2$. The agent starts at position $(1, 1)$. The reward equals to 1 at the state $(10, 10)$ and is zero elsewhere.

The second one is a chain environment described by Osband et al. [2016] with $L = 15$ states and 2 actions (left or right). The horizon is equal to 30, and the probability of moving in the wrong direction is equal to 0.1. The agent starts in the leftmost state with reward 0.05, and the largest reward is equal to 1 in the rightmost state.
**Variations of randomized Q-learning** First, we compare the different variations of randomized Q-learning on the grid-world environment. Precisely, we consider:

* RandQL a randomized version of OptQL, detailed in Appendix B.

* Staged-RandQL a staged version of RandQL, described in Section 3.2.

* Sampled-RandQL a version of RandQL which samples one Q-value function in the ensemble to act, described in Appendix B.

For these algorithms, we used the same parameters: posterior inflation $\kappa = 1.0$, $n_0 = 1/S$ prior sample (same as PSRL, see below), ensemble size $J = 10$. We use a similar ensemble size as the one used for the experiments with OPSRL by Tiapkin et al. [2022a]. For Staged-RandQL we use stage of sizes $((1 + 1/H)^k)_{k \ge 1}$ without the $H$ factor, in order to have several epochs per state-action pair even for few episodes.

The comparison is presented in Figure 2. We observe that RandQL and Sampled-RandQL behave similarly, with slightly better performance for Sampled-RandQL. This is coherent with the experiment on the comparison between OPSRL and PSRL Tiapkin et al. [2022a] where the optimistic version performs worse than the fully randomized algorithm. We also note that even with the aggressive stage schedule, Staged-RandQL needs more episodes to converge. We conclude that, despite simplifying the analysis, it artificially slows down the learning in practice.

To ease the comparison with the baselines, for the rest of the experiments, we only use RandQL because of its similarity with OptQL.

**Baselines** We compare RandQL algorithm to the following baselines:

* OptQL [Jin et al., 2018] a model-free optimistic Q-learning.

* UCBVI [Azar et al., 2017] a model-based optimistic dynamic programming.

* Greedy-UCBVI [Efroni et al., 2019] optimistic real-time dynamic programming.

* PSRL [Osband et al., 2013] model-based posterior sampling.

* RLSVI [Russo, 2019] model-based randomized dynamic programming.

The selection of parameters can have a significant impact on the empirical regrets of an algorithm. For example, adjusting the multiplicative constants in the bonus of UCBVI or the scale of the noise in RLSVI can result in vastly different regrets. To ensure a fair comparison between algorithms, we have made the following parameter choices:

* For bonus-based algorithms, UCBVI, OptQL, we use simplified bonuses from an idealized Hoeffding inequality of the form

$$ \beta_h^t(s, a) \triangleq \min \left( \sqrt{\frac{1}{n_h^t(s, a)}} + \frac{H-h+1}{n_h^t(s, a)}, H-h+1 \right). \quad (26) $$

As explained by Ménard et al. [2021], this bonus does not necessarily result in a true upper- confidence bound on the optimal Q-value. However, it is a valid upper-confidence bound for $n_h^t(s, a) = 0$, which is important in order to discover new state-action pairs.

* For RLSVI we use the variance of Gaussian noise equal to simplified Hoeffding bonuses described above in (26).

* For PSRL, we use a Dirichlet prior on the transition probability distribution with parameter $(1/S, \dots, 1/S)$ and for the rewards a Beta prior with parameter $(1, 1)$. Note that since the reward $r$ is not necessarily in $\{0, 1\}$, we just sample a new randomized reward $r' \sim \text{Ber}(r)$ accordingly to a Bernoulli distribution of parameter $r$, to update the posterior, see Agrawal and Goyal [2013].

**Results** Figure 3 shows the result of the experiments. Overall, we see that RandQL outperforms OptQL algorithm on the tabular environment, but still degrades in comparison to model-based approaches, which is usual for model-free algorithms in tabular environments. Indeed, as explained
<figure><img src="image_8.png" /><figcaption>Figure 3: Regret curves of RandQL and several baselines in (left) a grid-world environment with 100 states and 4 actions for $H = 50$ an transitions noise 0.2, and (right) in a chain environment of length $L = 15$, 2 actions for $H = 30$ with transition noise 0.1: smaller is better. We show average and error bars over 4 seeds.</figcaption></figure>

<table><caption>Table 2: Time- and space-complexity of several tabular algorithms.</caption><thead><tr><th>Algorithm</th><th>Time-complexity (per episode)</th><th>Space complexity</th></tr></thead><tbody><tr><td>UCBVI [Azar et al., 2017]</td><td></td><td></td></tr><tr><td>PSRL [Osband et al., 2013]</td><td>$\tilde{O}(HS^2A)$</td><td>$\tilde{O}(HS^2A)$</td></tr><tr><td>RLSVI [Russo, 2019]</td><td></td><td></td></tr><tr><td>Greedy-UCBVI [Efroni et al., 2019]</td><td>$\tilde{O}(HSA)$</td><td></td></tr><tr><td>OptQL [Jin et al., 2018]</td><td>$\tilde{O}(H)$</td><td>$\tilde{O}(HSA)$</td></tr><tr><td>RandQL (this paper)</td><td>$\tilde{O}(H)$</td><td>$\tilde{O}(HSA)$</td></tr></tbody></table>

by Ménard et al. [2021], using a model and backward induction allows new information to be more quickly propagated. For example, UCBVI needs only one episode to propagate information about the last step $h = H$ to the first step $h = 1$, whereas OptQL or RandQL need at least $H$ episodes. But as a counterpart, RandQL has a better time-complexity and space-complexity than model-based algorithms, see Table 2.

## I.2 Non-tabular experiments

The second experiment was performed on a set of two-dimensional continuous environments [Domingues et al., 2021a] with levels of increasing exploration difficulty.

**Environment** We use a ball environment with the 2-dimensional unit Euclidean ball as state-space $S = \{s \in \mathbb{R}^2, \|s\|_2 \le 1\}$ and of horizon $H = 30$. The action space is a list of 2-dimensional vectors $A = \{[0.0, 0.0], [-0.05, 0.0], [0.05, 0.0], [0.0, 0.05], [0.0, -0.05]\}$ that can be associated with the action of staying at the same place, moving left, right, up or down. Given a state $s_h$ and an action $a_h$ the next state is

$$s_{h+1} = \text{proj}_S(s_h + a_h + \sigma z_h)$$

where $z_h \sim \mathcal{N}([0, 0], I_2)$ is some independent Gaussian noise with zero mean and identity covariance matrix and $\text{proj}_B$ is the Euclidean projection on the unit ball $S$. The initial position $s_1 = \sigma_1 z_1$ with $z_1 \sim \mathcal{N}([0, 0], I_2)$ and $\sigma_1 = 0.001$, is sampled at random from a Gaussian distribution. The reward function is independent of the action and the step

$$r_h(s, a) = \max(0, 1 - \|s - s'\|/c)$$

where $s' = [0.5, 0.5] \in S$ is the reward center and $c > 0$ is some smoothness parameter. We distinguish 3 levels by increasing exploration difficulty:

* Level 1, dense reward and small noise. The smoothness parameter is $c = 0.5 \cdot \sqrt{2} \approx 0.71$ and the transition standard deviation is $\sigma = 0.01$.
<table><caption>Table 3: Average time of one episode in second (averaged over 20000 episodes).</caption><thead><tr><td>Algorithm</td><td>Episode time (second)</td></tr></thead><tbody><tr><td>Adaptive-RandQL</td><td>5.780e-02</td></tr><tr><td>Adaptive-QL</td><td>4.213e-02</td></tr><tr><td>Kernel-UCBVI</td><td>1.523e-01</td></tr></tbody></table>

* Level 2, sparse reward, and small noise. The smoothness parameter is $c = 0.2$ and the transition standard deviation is $\sigma = 0.01$.

* Level 3, sparse reward, and large noise. The smoothness parameter is $c = 0.2$ and the transition standard deviation is $\sigma = 0.025$.

**RandQL algorithm** Among the different versions of RandQL for continuous state-action space, see Section 4, we pick the Adaptive-RandQL algorithm, described in Appendix F, as it is the closest version to the Adaptive-QL algorithm. It combines the RandQL algorithm and adaptive discretization. For Adaptive-RandQL we used an ensemble of size $J = 10 \approx \log(T)$, $\kappa = 10 \approx \log(T)$ and a prior number of samples of $n_0 = 0.33$. Note that we increased the number of prior samples in comparison to the tabular case as explained in Section 4.

**Baselines** We compare Adaptive-RandQL algorithm to the following baselines:

* Adaptive-QL [Sinclair et al., 2019, 2023], an adaptation of OptQL algorithm to continuous state-space thanks to adaptive discretization;

* Kernel-UCBVI [Domingues et al., 2021c], a kernel-based version of the UCBVI algorithm;

* DQN [Mnih et al., 2013], a deep RL algorithm;

* BootDQN [Osband and Van Roy, 2015], a deep RL algorithm with an additional exploration given by bootstraping several Q-networks;

For Adaptive-QL and Kernel-UCBVI baselines, we employ the same simplified bonuses (26) used for the tabular experiments. For Kernel-UCBVI we used a Gaussian kernel of bandwidth 0.025 and the representative states technique, with 300 representative states, described by Domingues et al. [2021c].

For DQN and BootDQN we use as a network a 2-layer multilayer perceptron (MLP) with a hidden layer size equal to 64. For exploration, DQN utilizes $\epsilon$-greedy exploration with coefficient annealing from 1.0 to 0.1 during the first 10,000 steps. For BootDQN we use an ensemble of 10 heads and do not use $\epsilon$-greedy exploration.

**Results** Figure 4 shows the results of non-tabular experiments. Overall, we see that Adaptive-RandQL outperforms Adaptive-QL in all environments, especially in the sparse reward setting. However, we see that the model-based algorithm is much more sample efficient than the model-free algorithm, as it was shown by Domingues et al. [2021c]. This is connected to a low dimension of the presented environment, where the difference in theoretical regret bounds is not so large. However, this performance comes at the price of 3-times larger time complexity, see Table 3.

Regarding the comparison to neural-network-based algorithms, we see that approaches based on adaptive discretization always outperform DQN and BootDQN on an environment with non-sparse rewards. We connect this phenomenon to the fact that neural network algorithms are solving two problems at the same time: exploration and optimization, whereas discretization-based approaches solve only the exploration problem.

In the setup of sparse rewards, it turns out that neural network-based approaches are competitive with Adaptive-QL and Adaptive-RandQL. Notably, DQN shows itself as the worst one, whereas Adaptive-RandQL and BootDQN show similar performance, additionally justifying the exploration effect of ensemble learning and randomized exploration.
<figure><img src="image_9.png" /><figcaption>Figure 4: Cumulative rewards (higher is better) of Adaptive-RandQL and several baselines in ball environments with increasing exploration difficulty: Upper Left displays Level 1, Upper Right shows Level 2, Down shows Level 3. We show average and error bars over 4 seeds.</figcaption></figure>