Model-free Posterior Sampling via Learning Rate Randomization
Authors: Daniil Tiapkin
Denis Belomestny
Daniele Calandriello
Eric Moulines
Remi Munos
Alexey Naumov
Pierre Perrault
Michal Valko
Pierre MENARD
Venue: NeurIPS 2023 poster (2023)
Keywords: reinforcement learning
exploration
q-learning
TL;DR: learning rate randomization in Q-learning gives provably efficient exploration

Abstract: In this paper, we introduce Randomized Q-learning (RandQL), a novel randomized 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 $\widetilde{\mathcal{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 order $\widetilde{\mathcal{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.

Model-free Posterior Sampling via Learning Rate Randomization
Daniil Tiapkin' 12
Denis Belomestny
Daniele Calandriello*
Éric Moulines 1.5
Remi Munos!
Alexey 2aumov Pierre Perrault
Michal Valko
Pierre Ménard
1CMAP, École Polytechnique HSE University
Souisburg-Essen
University
$ *Google DeepMind 'Mohamed Bin Zayed University of AI, UAE IDEMIAA
"ENS Lyon
ddamiilttiapkin, tiapkin, eric. nou.liness/pollyttttmiuuuuu denis. d heabibbeellmeettyyuundddde..ed fdcalandriello, munos, (aallkoo@@@oooll.....oo pierre. www.apl com pierre. pewnrremmnarddens-yyooe
anaumov@hse..
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-basee
algorithm. We analyze the performance of RandQL in both tabular and non-tabular metric space settings. In tabular MDPs, RandQL achieves regret bound of order Ó O(VH horizon, is the number states, the number of actions, and is the number of episodes. For metric state-action space, RandQL enjoys regret bound of or- der Ö (HH5/27(d.+11) +1)/(++2)), where d, 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.
where H is the planning
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 's goal is to maximize the sum of the collected rewards. To achieve this, the agent choose to model- 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 state. The agent then plans this model to find the optimal policy. In contrast, model-free algorithms directly learn the optimal policy, which is the mapping of state to optimal action, 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 ap- proaches offer several advantages. These include smaller time and space complexity, the absence of need to learn explicit model, and often simpler algorithms. As a result, most of the recent breakthroughs in deep RI., such as those reported by Mnih et al. [2013]. Schulman et al. [2015, 2017], Haarnoja al. [2018], have been based on model-frea algorithms, with few notable exceptions, such as Schriuwieser et al. [2020], Hessel et al. [2021]. Many of these model-free algorithms [Mnih al., 2013, Van Hasselt al., 2016, Lillicrap al., 2016 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 behavioral policy while simultaneously incrementally learning the optimal Q-values
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

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 modelled by an episodie 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- eettiiiontelloitttionnn 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 optimism in the face of uncertainty. In finite MDPs, this principle has been successfully implemented in the model-bare 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.
adopt the principle of
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, 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 [TTapkii et al., 2022a]. The random least square value iteration (RLSVI, Osband et al. [2013]) is another well-known model-based technique for exploration. Precisely, RLSVI directly sets
algorithm that leverages Bayesian- a Gaussian prior on the optimal Q- Q-values and then updates the associated posterior trough value iteration in model [Oshand 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 perfor- mance 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, Azizzadeneshelii 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 (c.g. by giving more weight to important states). However, most of the theoretical studies on Bayesian- based exploration have focused 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 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 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-Rand(L. enjoys the same regret bound the OptQL algorithm, that is, Ō(v ((VHHSAA) where S is the number of states and the number of actions. Furthermore, we extend Staged- Staged-RandQL beyond the tabular setting into the Nett-Staged-Raate with metric aatt-ncciinn spaces [Domingues et al., 2021c, Sinclair et al., 2019]. Met-Sttage-Raat RandQL operates similarly to Staged-RandQL RandQL but over fixed discretization of the state-action space and
algorithm to deal
2

---

enjoys regret bound of order (11p:///(..++///dddttt This rate is of the same order as the one of Adaptive-Qua QL by Sinclair et al. [2019, 2023], an adaptation the budget T than one of the uses specific prior tuning to handle the effect of discretization. We prove that Net Pert-SSaaed-Randd where de denotes the covering dimension.
of OptQL metric state-action space and has a better dependence model-based kernel algorithms such that Kernel-UCBVI by Domingues et al. [2021c]. We also explain how to adapt Seee--ttaed-aaaan
and its analysis 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, 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 Ō ((VHS H SATT for staged version of the RandQL algorithm in finite MDPs where S is the number of states and the number of actions, the horizon and T the budget.
A regret bound of order ( (1/rdd+++(((4+)))) 1)/((++))) for an adaptation of RandQL to metric spaces
where de denotes the covering dimension.
Adaptive version of metric space extension of RandQL algorithm that achieves a regret bound of order ((155/2ppd +2))), where dg is a zooming dimension.
Experiments in finite and continuous MDPs that show that RandQL competitive with model-based and model-free baselines while keeping a low complexll......
2 Setting
We consider an episodic MDP (S, A, H, {ph (pns)) (ru (rnhee))) where S is the set of states, A is the set of actions, H is the number of steps in one episode, (s. a) the probability transition from state 8 to state s' upon taking action at step h, and (s. a) E [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 in the episode.
Policy & value functions A deterministic policy π is a collection of functions Thi S + for all h E [H]. where every Tr maps each state to single action. The value functions of ग,, denoted by V as well the optimal value functions, denoted by Vi are given by the Bellman and the optimal Bellman equations,
(s, = (n(s, a) + Pr V (8, (s,aa)) rn(s,a) a) + Ps Vi-
(x) = T (T)
(x()) = max (7,)
where by definition, V V A 0. Furthermore, P.J (s, A (gr-pa(--aaa) [fs')] denotes the expectation operator with respect to the transition probabilities ph and (ng(s) _ g(s, (s)) denotes the composition with the policy
step h.
Learning problem The agent, to which the transitions are unknown (the rewards are assumed to be known' for simplicity). interacts with the environment during T episodes of length H, with fixed initial state s1.² Before each episode the agent selects policy n' based only the past observed transitions up to episode - 1. At each step E [Hf] in episode i, the agent observes a state of, E S. takes action (s()) = di E AA and makes transition to new state s/ according to the probability distribution Pn ) and receives deterministic reward ry (5% af,)-
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 really gets,
T Σ - (51). (s))
R A
'Our work can he extended without too much difficulty to the case of random rewards. 2 As explained by Fiechter [1994] if the first is sampled randomly 81 ~ p. can simply add an artificial first state 81 such that for any action a, the transition prohability defined as the distribution pyr (Sv, a) & p.
3

---

Additional notation For N E N_+, we define the set [N] _ (1....,Ny N). We denote the uniform distribution over this by [ni We define the beta distribution with parameters a, as Beta(o, 33. Appendix A references all the notation used.
3
Randomized Q-learning for Tabular Environments
In this section we assume that the state space S is finite of size S as well as the action space A of size 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 E N, we maintain an ensemble of size J of Q- values² (Q" >>EE)]] updated with random independent Beta-distributed step-sizes (wn,)) where Wn.j Beta H, n). Then, policy Q-values Q" are obtained by taking the maximum among the Q-values of the ensemble
Qn ++1s (s, (1- )n R.j (s, + un.slra V (s
Wn.)
Qn (s,a) max max]= nl
Qn (s,a), Vh Vhtl(s) (s)
max Qn aEA
a+1 (s,a),
jE(J]
where +1 stands for the next (in time) state after n-th visitation of (s, a) at step h.
Note that the policy Q-values Q" are designed to be upper confidence bound on the optimal Q-values. The policy used interact with the environment greedy with respect to the policy Q-values (s) E arg max, Q% (s, a). We provide a formal description of RandQL Appendix
Connection with OptQL We observe that the learning rates of RandQL are in expectation of the same order [[wn.j] H/(n + H) as the ones used by the OptQL algorithm. Thus, we can view our randomized Q-learning noisy version of the OptQL algorithm that doesn't 't use bonuses.
Connection with PSRL If unfold the recursive formula above
express the Q-values
Tu+1d as a weighted sum
nu (s, 1 Wh, Lh (s, + Σ W Wh (r, V h+1 (sh+
where we define W n.j II" whr) and W W,j wh-1. I1 we,s).
To compare, can unfold the corresponding formula for PSRL algorithm using the aggregation properties the Dirichlet distribution (see e.g. Section 4 of Tiapkin et al. [2022b] or Appendix C)
"
t (s. (W + Σ Wh(ra(s,a) +
(1)
where weights (WP :..... W follows Dirichlet distribution Dir(no, 1,..., 1) and ni is a weight for the prior distribution. In particular, one represent these weights partial products of other weights Wn ~ Beta(1, + no). we use (1) to construct model-free algorithm, this would require recomputing the targets rı (s, a) v (sf+4) in each iteration. To make algorithm more efficient and model-free, we approximate F by V" and, as result, obtain RandQL algorithm with weight distribution Wn.j Beta(1, n no).
Note that in expectation this algorithm is equivalent to OptQL with the uniform step-sizes which known to be sub-optimal due to a high bias (see discussion in Section 3 of [Jin et al., 2018J). There two known ways overcome this sub-optimality for Q-learning: to introduce more aggressive
We index the quantities by n in this section where n is the number of times the atatenaction pair (s, a) is visited. In particular this is different from the global time since, in our setting, all the state- action pair are not visited at each episode. See Section 3.2 and Appendix B precise notations.

---

learning rates Wnyj ~ Beta(H, H, n + no) leading to RandQL algorithm, or to use stage-dependent framework by Bai et al. [2019], Zhang et al. [2020] resulting Staged-Randue 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 al., 2019]. Our algorithms (RandQL and 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 in Appendix E.4).
RandQL)
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-1/H) fraction of the the target will be forgotten exponentially fast in the estimation of the Q-values, see Jin al. [2018] 8J, Ménard et al. [2021], I.. 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-Rand(I. 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/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 BraagddRaand. is provided in Algorithm 1.
Counts and stages Let n (s, a) _ Σt= [[ss,, a²,)) = (s, a}} be the number of visits of state-action pair (s,a) at step h before episode t. We say that triple (s, a, h) belongs to the k-th stage at the nj, (s, E [Σ+=] es E 6s). Here e = + 1/H) H is the length
beginning of episode
of the stage k 2 0 and, by convention, c-1 O. Let n (s _ n (s, - Σ/= e; be the number of visits of state-action pair as,a) at step during the current stage k.
Temporary Q-values At the beginning of a stage, let say time I, we initialize J temporary Q-values as 1iad (s. a) = (s, a) + ro(H - h - 1) for j E [J] and ro some pseudo-reward. Then as long as (sho 4/ h) remains within a stage we update recursively the temporary Q-values
{ (1- 2 (s.a) + (,,l(n(ssa) + (*+t(5h+11ll (s,a) (sh, o/) otherwise,
@ (s.
(s,
where ñ = 7 a) is the number of visits, Wyy is a sequence of i.idd. random variables / ~ Beta(1/ (ñ + no)/K) with x > 0 being some posterior inflation coefficient and no number of pseudo-transitions.
Policy Q-values Next we define the policy Q-values that is updated at the end of stage. Let say for state-action pair (s, a) at step an stage ends at time t. This policy Q-values then given by
the maximum of temporary Q-values Q g++
maxje(j] Ø 1.+ (s,a). Then the policy Q-values is constant within stage. The value used to defined the targets is V (s) = max 2 (s,a).
The policy used to interact with the environment is greedy with respect to the policy Q-values
x++1, ++1 (s) mag Qhat (s, a) (we break ties arbitrarily).
h
3.3 Regret bound
We fix 5 E (0, 1) and the number of posterior samples J & [c, log(2SAHT/88], where cy = 1/ logg(/(1 (1 + ((1)) and ((-) is the cumulative distribution function (CDF) of normal distribution. Note that J has a logarithmic dependence on S, A, H, T, and 1/5.
We now state the regret bound of Staged- RandQL with full proof in Appendix D.
5

---

Algorithm Tabular Staged-RandQL
Input: inflation coefficient иi, ensemble size, number of prior transitions no, prior reward ro- 2: Initialize: (n(s) = Qn (s,a) = Q%(s,, a) = r(s, a) + ro(H - 1), initialize counters
(s, = 0 for j. h, s, [J] H x S x A and stage 9h (s,a) = 0.
3: for t E [T] do
4: for h E [H] do
5:
Play dĄ E arg max, (sh,
6: Observe reward and next state 84+1 Ph (Sh. an)-
7: Sample learning rates w, ~ B1ta(1// //s, (n no)/m) (x) for ñ mn(sn; ah)-
8:
Update temporary Q-values for all E [J]
(Sh: = (1 (1--w) w (1 (sh; an) ) + my (ra(sh, an) + +V (n+i(on+1))-
9:
Update counter 7 (sh, ah) (5 an) +
10:
M, 0n) = [(1 + 1/ H for q = qn (5h, an) being the current stage then Update policy Q-values Q2 (sh. 0A) == maxje(J] (s).))) an). Update value function (sh)
11:
12:
max On (sh,a) a)
Reset temporary Q-values 2 (s), a₂) := Th (sh, a₂) + +ro(H 11-1), 1). Reset counter ñi (8h, as) == 0 and change stage On (8h, ah) == (8n, an) + 1.
14:
end if end for
16:
17:
end for
+ Theorem 1. Consider a parameter 8 E (0, 1). Let K 3 (2T()T((T+1)))
no -
[K(co + l0817/16(T)]] - 2, where is absolute constant defined in (5); see Appendix D.3. Then for
with probability at least 1 5,
πº = =ō HSSAT - SA)
Discussion The regret bound of Theorem coincides (up logarithmic factor) with the bound of the OptQL algorithm with Hoeffding-type bonuses from Jin et al. [2018]. Up to factor, our lower bound Ω S SAT) [Jin et al., 2018, Domingues al., 2021b]. This bound could be achieved (up 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 the novel randomization technique and its use to construct computationally tractable model-free algorithms.
regret matches the information-theonm
Computational complexity space complexity OptQL, recall that we set J O(). The per-episode time-complexity is also similar and of order Õ Ö(H).
Staged- Baveed-RandLLIi is model-free free algorithm, and thus gets the Ö(HSA)
4 Randomized Q-learning for Metric Spaces
In this section present way to extend RandQL general state-action spaces. We start from the simplest approach with predefined s-net type discretization of the state-action space S x A (see Song and Sun 2019), and then discuss adaptive version of the algorithm, similar to presented by Sinclair et al. [2019].
4.1 Assumptions
To pose the first assumption, start from general definition of covering numbers.
Definition (Covering number and covering dimension). Let (M, p) be metric space. A M of open balls of radius is called an s-cover of M if M C UnE. B. The cardinality of the minimal E-cover is called covering number N₂ (M, p). We denote the corresponding minimal E-covering by Nr. metric space (M, p)) has covering dimension d, vf > 0 N₂ -xe-de, where Cy constant.

---

The last definition extends the definition of dimension beyond vector spaces. For example, is case of M [0. 1 the covering dimension of M is equal d. For more details and examples see e.g. Vershynin [2018, Section 4.2].
Next are ready to introduce the first assumption.
Assumption 1 (Metric Assumption). Spaces S and AA are separable compact metric spaces with the corresponding metrics ps and P.A. The joint space S x A endowed with product metric p that satisfies p( (s, a), (s', d')) S ps(s, ) + pA(a, a'). Moreover, the diameter of S x is bounded by dmaxx and S x A has covering dimension de with a constant CN.
This assumption is, for example, satisfied for the finite state and action spaces endowed with discrete metrics Ps (8, 8²) { * J PA(a, a') = [a & a'} with de = 0, CN SA and S and A being the cardinalities of the state and action spaces respectively. The above assumption also holds in the case S S [0, i and A S [0, 1] with de ds + dA.
The next two assumptions describe the regularity conditions of transition kernel and rewards. A Assumption 2 (Reparametrization Assumption). The Markov transition kernel could represented as an iterated random function. In other words, there exists measurable space (E, and measurable function FR: (S x A) - S, such that 8p+1 ~ (s (p.) Fi. (5%, an. (b) for sequence of independent random variables {En (EE)))
8h+1
This assumption is naturally satisfied for large family of probabilistic model, see Kingma and Welling [2014]. Moreover, it has been utilized by the RI. community both in theory [Ye and Zhou, 2015] and practice [Heess et al., 2015, Liu al., 2018]. Essentially, this assumption holds for Markov transition kernels over a separable metric space, see Theorem 1. 1.3.6 by Douc et al. [2018]. However, the function Fj could be ill-behaved. To avoid this behaviour, we need the following assumption.
Assumption 3 (Lipschitz Assumption). The function (. is L -ippschhi in the first argument for almost every value of &n. Additionally, the reward function ra S A + [0, 1] is L, Lipsschii
iterated This assumption is commonly used in studies of the Markov processes corresponding 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 vari- ation distance, since deterministic Lipschitz MDPs are not continuous in that sense. Additionally, incorporation of an additive noise deterministic Lipschitz MDPs will lead Assumption 3 with LF 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 I-Wasserstein metric, and that Q' and V are both Lipschitz continuous.
Lemma 1. Let Assumption 1,2,3 hold. Then the transition kernels pk (s, a) are Li-Licschitz continu- ous in 1-Wasserstein distance
Wi Wilp (p, (s(,d'))) S Lr Str-p((s,)))))p ()',)))')))
where 1- 1-Wasserstein distance between two probability measures on the metric space (M,p) is defined as Wi(K,) m) = sup f is 1 Lippchiitz JM fdv J fdn.
Lemma 2. Let Assumption 1,2,3 hold. Then Qi, and Vž are Lipschitz continuous with Lipschitz constant Lv, S Ew= L. -
The proof of these lemmas is postponed to Appendix E. For a more detailed exposition on 1- Wasserstein distance 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- 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 W1 but fail to satisfy Assumption 3.
4.2 Algorithms
In this section, following Song and Sun [2019], we present Sert-Staged-Raadde algorithm that combines a simple non-adaptive discretization and an idea of stages by Bai et al. [2019], Zhang et al. [2020].
7

---

We assume that we have an access to all Lipschitz constants Lr, Lp, Lv - Lv11 Additionally, we have access to the oracle that computes E-cover N₂ of the space S x A for any predefined E > 0',
Counts and stages Let nj, (B) & Σ 11 [[( a))) E B} be the number of visits of the ball B E EN at step h before episode t. Let ex = [(1 + 1/H)* H] be length of the stage k 2 0 and, by convention, 6-1 0. We say that (B,h) belongs to the k-thh stage at the beginning of episode t if
ni, (B) E |Ei= 6i Ei= ej). Let ūj (B) _ (8, Σi= e 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 (B) = roll for j E [J] and To some pseudo-reward. Then within a stage k we update recursively the temporary Q-values
(t) = S (1 (1---) -,,,), (B) + (y of) + V ( (s.a) - (5h, ai))
( (B)
otherwise,
where ñ = -ii, (B) is the number of visits, WjA is sequence of i.i.d random variables Wj, Beta(1/K, (7 + no (k))/R) with k > 0 some posterior inflation coefficient and ni (k) a number of pseudo-transitions. The important difference between tabular and metric settings is the dependence on the pouudo-count (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 ball B 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 Q ++1 (B) = maxje[J] @++1.1 (B). The policy Q-values are constant within stage. The value used to define the targets is computed on-flight
using the formula V (s) = m D (s, a)), where rhe S x A + N₁ is a quantization map, that assigns each state-action pair (8,a) to a ball B 9 (s) The policy used to interact with the environment is greedy with respect to the policy Q-values and also computed on-flight Ti. (s) E arg ma 0x (s, (we break ties arbitrarily).
detail description of Net- Staged-Randeee provided in Algorithm 4 in Appendix E.2.
4.3
Regret Bound
We fix E (0, 1), the discretization level >> O and the number of posterior samples e [ē.- (log(2Cx HT/8) + de log(1/e))],
where logg + + (1))) and (-) is the cumulative distribution function (CDF) of a normal distribution. Note that has a logarithmic dependence on H, 1/s and 1/8. For the regret-optimal discretization level E 1/(, the number J is almost independent of de Let us note that the role of prior in metric spaces is much higher than in the tabular setting. Another important difference dependence of the prior count on the stage index. In particular, we have
EL
(k) = Nu + + H
(ex + Noo + +x)
Nig (Co + - l0g17/16
where co is an absolute constant defined in (5) see Appendix D.3), k. is the posterior inflation coeffi- cient and L = 11+ LV is a constant. We now state the regret bound of Net S-ta-et----aadtt with full proof being postponed Appendix E.
Theorem 2. Suppose that N S Cye-de for all E > 0 and some constant C. > 0. Consider a parameter 8 (0, 1) and take an optimal level of discretization 2(log(8HCx/O0 dd (ogg(1/)++3 (ogglee(TT+))) ro A 2. Then it holds for Net Seeeet-Staed-Raaaa with probability at least 1 5.
--1/(d++2), Let k. &
π.. δ ( H 22
2 + HC + LT #-
We can restore the regret bound in the tabular setting by letting d, = 0 and CN = SA, where S is the cardinality of the state-space, and A is the cardinality of the action-space.
'Remark that the simple greedy algorithu can generate e-cover of size Ne/2, that will not affect the asymptotic behavior of our regret bounds, Song and Sun [2019].
8

---

Discussion From the point of view of eestance-independeee bounds, our algorithm achieves the same result as Net-QL [Song and Sun, 2019] and Adaptive-Qu [Sinclair al., 2019]. that matches the lower bound 92 S(HTT by Sinclair et al. [2023] in dependence on budget T and covering dimension de. Notably, as discussed by Sinclair et al. [2023], the model-based algorithm such as Kernel-UCBI [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 e, our algorithm has a space complex- ity of order (HH))). Assuming that the computation of quantization map te has (1) time com- plexity, achieve per-episode time complexity of ((HA) for finite action space and O (HN)) for an infinite action space in the worst
due to computation of arg ma Qn (W a)).
However, this can improved to (H)) if we consider adaptive discretization [Sinclair et al., 2019].
Adaptive discretization Additionally, we propose a way to combine RandQL with adaptive dis- cretization by Cao and Krishnamurthy [2020], Sinclair et al. [2023]. This combination results in two algorithms: Adaptive Seenttve--aann RandQL and Adaptive-Stagee the instance-dependent regret bound that scales with a zooming dimension, the mnstance-depended measure of dimension. We will follow Sinclair et al. [2023] in the exposition of the required notation.
The second one could achieve
Definition 2. For any (s, a) E S x A, the stage-dependent sub-optimality gap is defined as gap, (s. a) Vi
(s,
This quantity is widely used in the theoretical mustance-dependen analysis of reinforcement learning and contextual bandit algorithms.
Definition 3. The near-optimal set A for a given value e defined as Z (8, a) < (H + 1)s}.
The main insight of this definition is that essentially we are interested in a detailed discretization of the near-optimal set Zí, for small e, whereas all other state-action pairs could be discretized in more rough manner. Interestingly enough, Zí, could be a lower dimensional manifold, leading to the following definition.
Definition 4. The step-h zooming dimension d2 with constant CN.A and scaling factor p 0 is given by
d2,1 inf M 0 (Z CN,
Under some additional structural assumptions Qi it is possible show that the zooming dimension could be significantly smaller than the covering dimension, see, e.g., Lemma 2.8 in Sinclair al. [2023]. However, the same time, has been shown that de,A ds 1, where ds is a covering dimension of the state space. Thus, the zooming dimension allows adaptation to a rich action space but not rich state space.
Given this definition, is possible to define define an adaptive algorithm that attains the following regret guarantees
RandQ
Theorem 3. Consider parameter 8 (0. For value к that depends on T, de ad 8, for Seaptive-Stagen RandQL the following holds with probability at least 1 8,
H
Rt. =ō 1/H
H3/2
Σ
where dz,h the step-h zooming dimension and we ignore all multiplicative factors the covering dimension de log(Cx) and Lipschitz constants.
We refer to Appendix F to a formal statement and a proof.
5 Experiments
In this section present the experiments conducted for tabular environments using rlberry library [Domingues et al., 2021a]. We also provide experiments non-tabular environment in Appendix I.

---

Environment We use grid-world environment with 100 states (i. [10] [10] and 4 actions (left, right, up and down). The horizon is set H 50. When taking an action, the agent moves in the corresponding direction with probability 1 - E, and moves to neighbor state at random with probability 0.2. The agent starts at position (1, 1). The reward equals to at the state (10, 10) and is zero elsewhere.
Variations of randomized Q-learning For the tabular experiment we use the RandQL algo-
003300
Greedy UKBV)
OptoL
rithm, described in Appendix B as it is the ver- sion of randomized Q-learning that is the closest
503300
PSR.
Randsmized
BLSKI
603300
to the baseline OptQL. Note that, we compare the different versions of randomized Q-learning in Appendix B.
503300
203300
Baselines We compare RandQL algorithm to the following baselines: (i) OptQL [Jin al., 2018] (ii) UCEVI [Azar et al., 2017] (iii) GUEVdY-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- hyper-parametts parameters used for these baselines refer to Appendix
105300
Figure 1: Regret curves of RandQL and baselines grid-world environment for = 50 and tran- sition noise 0.2. The average is over 4 seeds.
Results Figure shows the result of the experiments. Overall, we that RandQL outperforms OptQL algorithm on tabular environment, but still degrades in comparison to model- approaches, that is usual for model-free algorithms in tabular environments. Indeed, using model and backward induction allows new information to be more quickly propagated. But as counterpart, RandQL has better cime-complexity and space-complexity than model-based algorithm, see Table 2 in Appendix I.
Conclusion
This paper introduced the RandQL algorithm, a new model-free algorithm that achieves exploration without bonuses. It utilizes novel idea of learning rate randomization, resulting in provable sample efficiency with regret of order Ö HAT) 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- 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 coupled with variance reductions techniques as used by Zhang 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 large gap in the experiments between Q-leaning type algo- rithm that do one-step planning and e.g. UCBVI algorithm that does full plamning or Greedy- UCBVI that does one-step planning with full back-up (expectation under transition of the model) for all ac- tions. 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 1M000DD700321S$00000 00139. Moulines received support from the grant ANR-19-CHIA-ON work has been done under the auspices of Lagrange Center for maths and computing. P. Ménard acknowledges the Chaire SeqAL.0 NNN-22--CHIA-00200001 This research was supported in part through computational resources of HPC facilities at HSE University.
and the agreement with HSE University No. 70-2021-
SCAI and parts of his
10

---

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 pwwps//3e/aaapeeeeeepeeepeeeesae http///////aaaaaaaaaaa 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 Neural Information Processing Systems, volume 30. Cur- ran Associates, Inc., 2017. URL https: http://eweceeen...///e/// wewrss.nurrs.p.. cc/ paper/2017//flee/ 1000144446cc1555503363222d2 Paper .df..
Duncan Alfers and Hermann Dinges. A normal approximation for beta and gamma tail probabilities. Zeitschrift für Wachescheemlichkertssheere und Verwandte Gebiete, 65:399-420, 1984. URL https://limg www.iinn..iiiiii. spr inger.g...... com/ content/paf /10. L007/BF00533744 pdf.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference on Machine Learning, 2017. URL https: //arxiv. wwg/oog//...oooo påf 1703. 05449, paf.
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.2088. 8503252. URL ntttps://doi. org/ 10. 1111/99TTAAA. 2018 8503322...
Yu Bai, Tengyang Xie, Nan Jiang, and Yu-Xiang Wang. Provably efficient q-learning with low switching cost, 2019, URL https: /twpvvaxvvvv///////////ee///.aaa 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: http:::://///cceeeeeeeeeee http://pproceeednnnnnrrrrrpeeepp www.ung....uisssseoom wwcc//aper_fffee fileffieeleeeeeeee faaper_flles/ppperrrreeee /aaper//ieees/pppee22///////// pptp://op2////ileeee 6ef 2ee17778066.2200055bbbbbraaaaa 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:tt///// //axxiv.////i/////////// wwtpsiii.or///ooe org/pdf /10... 077100 off.
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: htttps://prroceedings neurips. httppp..ccpppppee wwtppppppppppeeeeeeeeeeeeee..eee fiw.ffillspppppeeee https/apappppe////e/e2 6/9865b1TT99661371aaefddt888 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/50036 44598338446. URL http:h/o/////ooorrg/g 11977/80031144444888
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: /gi thub. comc www/rlberry-py////ooooeeeeooosee py/rlberry.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic reinforce- ment 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 Learn- ing Theory, volume 132 of Proceedings of Machine Learning Research, pages 578-598. PMLR, 16-19 Mar 2021b. URL https:/ https:///ooceinneeee mlr, http://1v///mmmmmusse..... 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. PMIR, 18-24 Jul 2021c. URL. https: ptttps:/procee htttps//prroceedings mlr. wwwppreessveee /vtsss//v///////// dww.igues2aa.....mmmmooo.om 2hmml.lmm.....l............
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 httptth///rcceeeeeeeeeee Paper pdf.
neurips. cc/
Yonathan Efroni, Nadav Merlis, Mohammad Ghavamzadeh, and Shie Mannor. Tight regret bounds for model-basee reinforcement learning with greedy policies. In H. Wallach, H. Larochelle, A. Beygelz- imer, F. d'Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL http:htttss:/otceshttitttt Paper pdf. paper_ fttp://eeere0/t/t/e//e/e/aaaaaaa
neurips.cm cc/
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. psu edu/ /
1.....9....... 8652kreeprrep11xyppe-dd.. ott.:///................02..22rr
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 conttrnod exploration-exxlootttinn 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-uch-switch: optimal regret bounds for stochastic bandits from both a distribution-dependenn and distribution-fre viewpoints. arXiv preprint arviv: 000. 2018
Subhashis Ghosal and Aad Van der Vaart. Fundamentals of nonparametrie 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. (0.108801065244000152999999
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: / /ttp::::///cccoeeeeeeeeee http///rreeeednnneeee www.rrceeedinng.eeeiii........p. ccpppppprr.ppp.....pppppp Pawp::ttteeeeaaea.ppppppp.
Matteo Hessel, Ivo Danihelka, Fabio Viola, Arthur Guez, Simon Schmitt, Laurent Sifre, Theo- phane Weber, David Silver, and Hado van Hasselt. Muesli: Combining improvements in pol- icy optimization. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th Interna- tional 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:/ ptttp://proceedee pttp///eoccee...eeee/ mlr, teeess/v33///ssee/e html.
12

---

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-2255 URL. http::ttpp//../ uni-trier .ecierrde//eee de/db/cont 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/ httppe/s/ooomme///eeeeee.
jas.chaaaaaaaaaaaaaaaaa 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 htttps//arxiv..rrt org/pdf 1807 00765....... 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 aatt:://arxia org/ abs/ 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 Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
URL https: : / opwnreviereeeeeeeeeeeee net/ wwwmmidddoorraaaa...
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 Reprexentations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Truck Proceedings, 2016. URL http:/ htt////xvvvv.////// org/ abs/ abs/1509 11////500000 .09971.
Hao Liu, Yihao Feng. Yi Mao, Dengyong Zhou, Jian Peng. and Qiang Liu. Action depinnnde control variates for policy optimization via stein identity. In ICLR 2018 Conference, February 2018. URL https://wwet https://www.mmccroofftt micoosoft. com/ en htt.au//eeeeeaeepppaaaaaaioooooa
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 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 Oshand and Benjamin Van Roy. Bootstrapped thompson sampling and deep exploration. CORR, abs/1507.00300 2015, URL http:/ //atxi//rxxvv..o org/
00300.
Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In Doina Precup and Yee Whye Tch, editors, Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 2701-2710. PMLR, 06-11 Aug 2017. URL https: htttp:://proceedings mlr mww.mmees.......mmmmmmmmmmmmmm.e /v00/ isband17a.hton
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 explo- ration via bootstrapped dqn. In D. Lee, M. Sugiyama, U. Luxburg, Guyon, and R. Garnett, editors, Advances in Newral Information Processing Systems, volume 29, Cur- ran Associates, Inc., 2016. URL https: ptwppeeeiigg....../oe///ooo...se B4B811ccee100004444333333666666. Paper pdf.
htt.https::pproeeeeiia wtw.eeeddinnnnn.iiiis.eeee nwwrips...... www.wips....ppppee//////pp /c/paper/2016//tlee/
13

---

Gabriel Peyré and Marco Cuturi. Computational optimal transport: With applications to data science. Foundations and Trends@ Machine Learning, 11(5-6):355-600)) 607, 2019. ISSN 1935-8237. doi:
10.1561/2200000003. URL URI.http://dx doi org/10. /
losif Pinelis. Optimum Bounds for the Distributions of Martingales in Banach Spaces. The Annals of Probability, 22(4):1679 1706, 1994. doi: 10. 10. 00.1214/a0//11766884777 URL https://doi org/ 10. 02214//op/117798/08
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 Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https: https://proceeddngg www.gg..neuiis..m www.rip....pppppr/eeeeee wttppp/pr/////////a/aeaea//// 451168722266002222777722723333-3 Pappa22227731-PPaarrPppp pdf.
Remo Sasso, Michelangelo Conserva, and Paulo E. Rauber. Posterior sampling for deep reinforcement learning. CoRR, abs/2305.00477, 2023. doi: 10.48550k:xXx1:235500077777 URL https://dii.
org/10.48500 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-600 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 7077006477, 2017. URL http:://t//e /ttpppdbllpplp/p wntppp.iiiiiieeeeee tew-trrrrrde de/ jb/jorraass/ caternaall/oorr/eeee coor//oori//e www.hhhmlllht. htt.:HHShhhunnmaMMMR.......
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: htttps://proceeddnngg wwwpriiiiiinnnnnnnn...... wwtpepp..ccpppppreeeeeepe filersffees//eel Saaper_files/paper//000 /ppp/////1///////////// ftle://0aaabbbeffeecccaaaalaaaae
.df.
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. 145/3366703. URL httph:tt//// //doip /ttpp//////oo..///..//// org/10. 1145X2F3366703.
Sean Sinclair, Siddhartha Banerjee, and Christina Lee Yu. Adaptive discretization in online reinforcement learning. Operations Research, 1665)1666-1662, 2023. doi: 10. 10.1287/opre.002. 2396. URL httph::////eet //to:::///do.oe http:///oooooog////// wttp://.////11/.////....
Maciej Skorski. Bernstein-type bounds for beta distribution. Modern Stochastics: Theory and Applications, 10(2):211-22) 1-228, 2023. ISSN 2351-6046. doi: VM559/23-MMMT2223..
Zhao Song and Wen Sun. Efficient model-free reinforcement learning metric spaces, 2019.
Malcolm J. A. Strens. 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.
Danii Tiapkin, Denis Belomestny, Daniele Calandriello, Eric Moulines, Remi Munos, Alexey Naumov, Mark Rowland, Michal Valko, and Pierre Ménard. Optimistic posterior sam- pling 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 Neu- ral Information Processing Systems, volume 35, pages 10737-10751. Curran Associates, Inc., 2022a. URL http:: https://prooeeddings wwweiiinnnn.n.....eeeee.me. neurips. www..ps.cc/pppee.eeeeeeee.. httpae/fleeeeeeeeeeeeeeee pttppppee/22///lee (eo11beeel1662211444222238338330 ort.reaeeeeeeeeaoooeooooooooooor Conference.
14

---

Daniil Tiapkin, Denis Belomestny, Eric Moulines, Alexey Naumov, Sergey Samsonov, Yunhao Tang. Michal Valko, and Pierre Menard. From Dirichlet to rubin: Optimistic exploration 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::/ httppe///procceiingg.. mlr press/ wwtppp/eweettieeeeeeeeeppepeeeee v122/tiapkin222. html.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In Proceedings of the AAAI conference artificial intelligence, volume 30, 2016.
Roman Vershynin. Hlig--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-25)) 292, 1992. URL http:/iiiikk.siiigngneeeee
https://link. spr apringer-- com/ wwwtent/ppt///ttieeeooooo 1007 100///000000///800999555665 pdf.
Tzu-Tsung Wong. Generalized dirichlet distribution in bayesian analysis. Applied Mathemat-
ics and Computation, 97(2):165-181, 1998. ISSN 0096-3003,
doi: hrtp:///doi.rog/100 1016/
(0096-3003397)000440 URL httpp:::/ww...cienneeeeeee $0096300397101400.
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 116638866711,2011 2022.
Fan Ye and Enlu Zhou. Information relaxation and dual formulation of controlled markov diffusions. IEEE Transactions on Automatic Control, 60610))667--661, 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: //rxaaaxvvv/v//////v////////aaia htt///awwww.woodaee///// org/pdf/ 1910/991.0000 00210 20210.ppd. pdd.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-adee advantage decomposition. arXiv preprint arXiv:2004.1001/ 2020. ISSN 23318422. URL https: / //tpxav./vv/////////////////aa// atg/páf/200/ 10019, pdf.
15

---

Appendix
Table of Contents
A Notation
17
B Description of RandQL
18
B.1 RandQL algorithm
18
Sampled-Rand()) algorithm
C Weight Distribution in RandQL
20
D Proofs for Tabular algorithm
22
D.1 Algorithm
22
D.2 Concentration
23
D.3 Optimism
25
Regret Bound
27
E Proofs for Metric algorithm
30
E.1
Assumptions
30
E.2 Algorithm
30
E,3 Concentration
32
E,4 Optimism
33
Regret Bounds
36
F
Adaptive RandQL
40
F.1
Additional Notation
................................
40
F2
Algorithm
40
F3
Regret Bound
42
Deviation and Anti-Concentration Inequalities
49
Deviation inequality for Kurr
49
Anti-coneentration Inequality for Dirichlet Weighted Sums
................................
49
G.3
Rosenthal-type inequality
50
H Technical Lemmas
52
Experimental details
52
L.1 Tabular experiments
52
1.2 Non-tabular experiments
54
16

---

A
Notation
Table I: Table of notation use throughout the paper for the tabular setting
Notation
Meaning
S
state space of size $ action space of size length of one episode number of episodes
A
H
T
J
number of posterior samples
reward
Pa a))
probability transition
Q7
Q-function a given policy ı at step h V-function of a given policy æ at step h optimal O-function at step h optimal V-function step regret
Vī (s)
(s,
(s)
R
and no (k)
number of pseudo-transitions
80
optimistic pseudo-state
To
pseudo-reward
K
posterior inflation parameter state that was visited at h step during episode action that was picked at step during episode
si
Br
ball that contains pair (sf, (4)))
(s,
number of visits of state-action at the beginning of episode t
n (s, a) = kml 1 { (s ax))) (s, ().a
nf,(B)
number of visits of a ball B at the beginning of episode
ek
length of k-th stage e = [[1 + 1/H)* H for k: 2 0 and e-1
(s)
index of stage previous to time at step h and state-action pair (s, a))
kj, (s. a) max(k: nj, (s. Σi e;}
())
number of visits of state-action during the current stage:
/ (s, a) = n2,, (8, a) - Σ (e.())
i-
(B)
number of visits of ball B during the current stage:
(s)s)
upper approximation of the optimal V-value
(s,a)
upper approximation of the optimal Q-value
(B)
upper approximation of the optimal Q-value for all (s, () B
(s,
temporary estimate of the optimal Q-value
(B)
temporary estimate of the optimal Q-value for all (s,a) random learning rates
Wn.j
PS: PAs No
metrics on S, A and S x A correspondingly minimal E-cover if S x A of size N₂ covering dimension of space S x A: VE 0: N: S CNe-de
de
dmax
diameter of S x A
(1 Ex)
reparametrization function 8 (s, + 8h41 = a,,
Ly, LF
Lipschitz constants of rewards and reparametrization function Lipschitz constants of Qi and VI
Lv
Let (X,X') be measurable space and P(X) be the of all probability measures on this space. For E P(X) we denote by E, the expectation w.r.t. p. For random variable ş X - R notation & ~ means Law(E) = p. We also write Egap instead of Ep For independent (resp. ii.d)) random ind variables & pe (resp. &
iid
(resp. E un denote expectation w.r.t. product measure on (Xd x For any x X we denote 8, Dirac measure supported at point z.
p). 1..... we will write
E2 ind
17

---

For any p.9 E P(X) the Kullback-Leilerr divergence (L( q) is given by
de Ep log
KT(p,g)
dg
ع q
100,
otherwise.
For any p P(X) and f: pS L. In particular, for any p Aa and f {0, (0....,d) ,,,]
R. pf = Li=o (())p()). Define (f) pp [(f(s')()))))) - pff) plf (pf)². For any
(8,a) E S, transition kernel p(s,a) E P(S) and f: 8 I define pf(s, Bp(x.a) and Var,]/](s,a) Varp(s.a)(/]-
Let (X, be metric space, then the 1-Wasserstein distance between E P(X) is defined as Wi(p.9) supf 1-Lipschitz Eplf] [f].
We write A,
Ogg(S, A, H, T, 8)) if there exist So, Au, Ho, To, dg and constant
Cr such that for any S 2 So. A 2 An, H 2 Ho, 2 To, < J(S, A, H,T, T, S Cfa (S, A, H,T, 8). We write f(S, A, H, H, = O,,(S,A,HHH)) definition poly-logarithmic in S, A, H,T,1/6.
if Cs in the previous
For a, 3 > O, we define Beta(o, 3) as beta distribution with parameters B. For set X such that XX] Do define Uni uniform distribution over this set. In particular, Unif[N] is uniform distribution over set [N].
For measure p P(0 b)) supported segment [0, b] (equipped with Borel o-algebra) and number ja E [0, bj we define
Kmn(p, 14) A (nf g) : P((0, b)). < q. Ex [X] 2 1n)
As the Kullback-Leibler divergence this quantity admits variational formula by Lemma 18 of Garivier et al. [2018] up rescaling for any u E (0,
Kinr(p.1)
max Ex=p[log(1 - A(X - -n))]- xe(0,1/(b-w)
B Description of RandQL
In this appendix we describe RandQL and Sampled Sampled-RandQL algorithms.
B.1 RandQL algorithm
We recall that n², (s, a) (s, a) at step / before episode
- 1(()) (ss), of)) = (s, }}} is the number of visits of state-action pair
We start by initializing the ensemble Q-values the policy Q-values, and values to an optimistic value Q (s, a) (x a) = (s. rs(s. + ro(H - h) for all (j. s, a) [J] x [H] x S x A and ro > 0 some pseudo-rewards.
At episode / we update the ensemble of Q-values follows, denoting by = n1 a) the count, Wjjn Beta (H, H) the independent learning rates,
[ (1- Win 1l- (s, wg, (5, (s, (s at) otherwise,
(s,a)
where we defined the target 2% (8, a) as mixture between the usual target and some prior target with mixture coefficient Win Beta no) and no the number of prior samples,
= = ui,,lla
V (h4z(sh(zz) + (rn,s)) + rroll - - 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 EE[uy,,)] H/(n + H). Since [ T.n] (n no)) the weight put the prior sample in expectation, when unfold
18

---

the definition of 1h is of order H/n- n/H no/(n + no) = nn + no). which is consistent with the usual prior forgetting in Bayesian learning, In Staged-Randgu, we avoid forgetting the prior too quickly by resetting the temporary Q-value to prior value at the beginning of each stage.
The policy Q-values obtained taking the maximum among the ensemble of Q-values
Qn (s.a) max
1.+ (s,a).
(s) The policy is then greedy with respect the policy Q-values ~ + arg a. Qh (s, and the value is V (s) maxae On ++1 Algorithm 2.
(+1
a), The complete RandQL procedure is detailed in
Algorithm 2 RandQL
1: Input: J ensemble size, number of prior transitions no. prior reward ro-
2: Initialize: Vn(s) = (s, = (s, r(s, a) + tro (oHH-Mhh h), initialize counters n (s, a) =
O for s, E [H] S x A.
3: for t E [T] do
4: for h E [H] do
5:
Play dn arg max, (sh,,a))
6: Observe reward and next state 8h+1 (sh. an)-
7: Sample tü (et no) for = (n
8:
Build targets for all j E [J]
Ø = (r an) Vh+1 + (1-0;)(r(Ssh,,0, + rro(H h)]
9:
Sample learning rates w/ ~ Beta( H, H, Update ensemble Q- 2-functions for all j E [J]
(sh,) an) = (1 w/ 2 (sh, and + wj
Update policy Q-function Q (8h, an) == maxye(J] 0% (sh,
12: Update value function V (sh) == max.EA Qn (s).
end for
14:
end for
B.2 Compled-Randian algorithm
To create algorithm that is more similar to PSRL, it is possible to select a Q-value at random from the ensemble Q-values, rather than using the maximum Q-value
(h a) (s,
with jr 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],
(s,() (ri.nl + V.d (sh+1)) + (1 (1- (1, + +o - --1)]
where (s) max a 24:2 (s, We name this new procedure Sampled -aaaddd--nnLLL---- and detail it
A Algorithm 3.
19

---

Algorithm 3 Samp1 ed RanddQL
1: Input: J ensemble size, number of prior transitions no. prior reward ro-
2: Initialize: (s) (s, (s, a) +ro, -h), initialize counters ny (8,a)
O for h, s, E [H] S A.
3: for t E [T] do
4: Sample ensemble index i ~ Unif[J]
5: for h E [H] do
6: Play d₁ E arg max, (sh.
7: Observe reward and next state S441 Pa (sh: as).
8: Sample úü (eta mn) for (sp. an).
9:
Build targets for all j E [J]
2 = (rh an) + V2+1 (86+1)] (1- + ro(H - -h]]-
10:
Sample learning rates w, Beta(H,1) Update ensemble Q-functions for all j E [J]
11:
@h an) = wÿ ) (sh, an) + wy V
12:
Update value function (sh) = max.EA 0% (sh, a) for all j E [J].
13:
Update policy Q-function Qn (Sh, ax) Q (sh; an).
14:
end for
end for
C Weight Distribution in RandQL
In this section we study the joint distribution weights over all targets in RandQL algorithm, described in details in Appendix B. To do it, describe very useful distribution, defined by Wong [1998].
Definition 5. We say that random vector (X1, Xn, Xn+1) has a generalized Dirichlet distri- bution GDir(a Oni .I.... ,,,) if X,+1 = 1 - (X1 +... + X,)) and (X1..... ..,). ) it has the following density over the simplex {r1, ..l....,,2, Tn x1 + ... + on $ 1).
p(z)
B Bla B.)
24
(1
xz
for Φ + ... + nn I 1, 2 for j = 1,... n2, and P3 = 33 - aj+1 - By+1 for = 1,...,77
and 7/ 3n 1. If we set En+1 (x) In) then obtain homogeneous formula
7
==1 p(x) B(a,, 3,)
Alternative characterization of generalized Dirichlet distribution could be given using independent beta-distrine diitiiitribuee random variables Zı.... .a....,Z, Zn with Z, ~ Beta(a,, (B)) as follows
X1 Z1,
X, = 71511 - X1 - -...- 151-...x--11 X;-1)= Z (1 7.)
for j = 2, .......00
Xat1 1 X1 X, II Z2)
Therefore, for RandQL algorithm without prior re-injection we have the following formula
(a,a)
(s, = Σ
Win
rh (= af Vo Varn(ohtt)).
1=0
20

---

for n = (s, a) and weights are defined as follows
W II wjah, W W, II (0,,), 221. 1.
And, moreover, we have that this vector of weights has the generalized Dirichlet distribution
(W W Whyj Wh GDir(H,
H;; n + Top..... no + 1, n.)
That is, weights generated by the RandQL procedure is an inverted generalized Dirichlet random vector, that induces additional similarities with usual posterior sampling approaches. Notably, that for 1 we recover exactly usual Dirichlet distribution, as the setting of Staged-RandQL.
In the setting of the analysis, the main feature of this distribution is asymmetry attitude to the order of components. In particular, the expectation of the prior weight W is IT i+17 n H that leads to too rapid forgetting of the prior information.
21

---

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 a) be the number of visits of (s, a, h)) (i.e., of the state-action pair (s, a) at step h) at the T+1 (s, a) is the beginning of episode t: (s, = E [(s of,) = (s, (s. In particular, n number of visits of (s, 0, h) after all episodes.
Let Ek [(1 + 1/H)* HJ be the length of each stage for any k 2 0 and, by convention,
e-1 O. We will say that at the beginning of episode t a triple (8, a, h) is in k-th stage if n (s,a)
E 0i=0 Ci E)
k-1
Let n (s, a) be the number of visits of state-action pair during the current stage at the beginning of episode I. Formally, it holds 7., (s, a) n (*, Σ Cis where l is the index of current stage. Let K 0 be the posterior inflation coefficient, no be the number of prior transitions, and J be the number temporary Q-functions. Let @1," be the j-th temporary Q-function and Qn be the policy Q-function at the beginning of episode I. We initialize them as follows
(),s a) = (n(s, a) + ro(H h 1), 1),
T..² (s. a) = (s. + ro(H - h 1--11) 1);
We can treat this initialization as a setting prior over no pseudo-transitions to artificial state with ro > reward for each interaction.
For each transition we perform the following update of temporary Q-functions
(s, 1/11/2 (1 a (s, w ( V n4 (5%+4)) as) = (8), af)) (s,a)
otherwise,
where 7 = ūi, (s, a) is the number of visits (s, a, h) during the current stage at the beginning of episode I, the index of the current stage, and w is sequence of independent beta-distribution random variables - ~ Beta(1/k, (ñ + mo)/k)) Here we slightly abuse the notation by dropping the dependence of weights wy,; on the triple (h, s, a) in order simplify the exposition. In the case that the explicit dependence is required, will call these weights " (s,
k.h
Next we define the stage update follows
D 1 (s,a) a) =
maxjelM 2/41/22(s,) (s,a) a)
1(+
otherwise
(n(s a) + -o(H- h+1) 1
/ (s, 1(1 + 1/H))*H] otherwise
2 g (s,
V/t1 (s) max Th (s,
aEA
++1 2 (x) E arg max @h [+1
(8, a),
aEA
where l is the current stage. In other words, we update q²+1 with temporary values of 1t+1/25, and then, if the change of stage is triggered, reinitialize 1 a) for all j. For episode t we will call kf,ss, (s, a) the index of stage where 2 (s, a) was updated (and (s, a) = -1 if there was no update). For all t define T/ a) < t as episode when the stage update happens. In other words, for any t the following holds
Φtatt (s,a) a) max (1/. (s.a),
JE[j]
where (s, a) and ex = there was no updates. To simplify the notation we will omit dependence on (s, a, h) where it is deducible from the context.
22

---

To simplify the notation, we can extend the state space S by an additional state so that will be purely technical and used the proofs. This state has the prescribed value function V (so) ro h) and could be treated as absorbing pseudo-state with reward ro-
We notice that in this case we use samples to compute (ri(6,a)4122 for h: = ko, (s, a). For this we define f., (s, a) as a time of i-th visit state-action pair (s, a) during k-th stage. Then we have the following decomposition
Th 11/2 (s, = =r) +
Σ
W V
jock (4t1(
(3)
where we drop dependence on k and (8, (8,a, h) in to simplify notations, and use the convention (s,a) h+l
8p. and the following aggregated weights
W j,nkk
II w Wjnnk w II w5gg: i2 1.
We will omit the dependent the stage index k when it is not needed for the statement. However, we notice that these vectors, for different stage will be independent.
By the properties of generalized Dirichlet distribution it is possible to show the following result
Lemma 3. For any fixed n. > O, the random vector (Wo WI tion Dir(no/ k, 1/N,.... 1/k).
Wh jan
has a Dirichlet distribu-
Jon Ja
Proof. Using the Dirichlet random variate generation from marginal beta distributions, it is sufficient to prove that for all i E (O....,,} W (1 Wn convention w 1. This is trivial for i O, W j.n.k w w Now, if this is true for some i,
j.n.k m/n-i+1
j.n.k )wf j. with the
then, for + 1E {0,... ...; n), have
n-1
W
w 1-
II
(1 (1-w) w
g=n-i-1 1-1
to jn-i 1-2 (1
w j.n-i- (1 - W Wn-i++)
w
Winnk
Wn-i+1
jnnk
w - Wn
j.nk
Wa-i+1)
j.n.k
jinck
which finishes the proof.
Notably, the expression (3) shows 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 lazy and model-free fashion.
D.2 Concentration
Let ( (0, 1) x R4 and _ geone 3: (0, - TR, be some function defined later on in Lemma 4. We define the following favorable events
23

---

{²))) - WEN
6k
- (*(6,Ex)
Kinf
Ek
E (5) -
vA E (H) ESSAVEE (s)
r1
j,ee. Jen.))) V
S 60e2,
ek + 10
+ 1200e rotlrllogee (B))
ck + nog
( A
1I E
1 ck
(2n(sa)) Ph Vitt((s, S
2r H2 goono (ö)
Vh+1 (s/+1
Ck
EK
E(8) -
(1 + 1/H) H-
pa.aaiii+ 1
[V
V (+
S 2ern H /
We also introduce the intersection these events, g( & (²) n (8) n E c (0)). We prove that for the right choice of the functions Sr gkl. geone, B, Var the above events hold with high probability.
Lemma 4. For any E (0, 1) and for the following choices of functions B,
8* (5, n) A log(8SAH//5) + log(em 1));
8 A 1og(8SAH//) + log(TJ),
geone
8 A log(8SAH/0) + log(21"),
((6) log(16/8),
holds that
Plg* (8)) 2 - 5/8,
PP()((8) 2 1 8/8,
P|e P (8)] 8/8,
PP((()) 8/8.
In particular,
Proof. From the fact that s//11 are i.i.d. generated from pa(s, a), Theorem 4, and union bound S x A x [H] it holds (()) 2 - 8/8.
Next we fix all t, h, a.J. and denote is sigma-algebra generated by all random variables appeared untill the update (2) in the episode and step h, before newly generated random weights but after receiving new state s/ 1- Formally, we can define it as follows
(s.a) First, define a filtration of o-algebras F, that
Fr, ( ah
W jay (s%, a.))). Vr <1,0)) E ( [J]}
U Ulshi Mi < h3 U f, (sh, ahr), Vh < <h.j <h.je 17)).
24

---

where we drop dependence on ftate-cction pairs everywhere where it is deducible from the context.
Consider sequence & <... t be excursion of the state-action pair (s,a) a) the step h. Each is stopping time w.r.t Ft,k, so we can consider stopped filtration (with a shift by in indices) Fi-1= Fe A- In other words, this filtration at time-stamp i contains all the information that is available just before generation of random weights for i-th update of temporary Q-functions inside the last stage. We notice that under this definition have
E i 115 = Vii
h+1 (8 15tt));
B(W) MIW = E
I t=i
= BW
J.nkk
Next, we notice that the joint vector of weights follows the Dirichlet distribution, applying aggregation property and extending the filtration backward by adding fake transitions we can extend sum to + no summands defining s so
Σ (W j.n.k j. h- (8h+z)) i=0
Σ +1
W B[W,)) v (+
Finally, we notice that marginals of Dirichlet random vector follow Beta distribution, therefore by Proposition 7 and union bound we conclude (()) 2 1 5/8.
To show that P(gcoue( (6)) > - 5/8, is enough to apply Hoeffding inequality for a fixed number of samples eg used in empirical mean, and then use union bound of all possible values of (s, a, h) x A x [H] and E [T'.
Next, define the following sequence
Z,, (1 + 1/H) (IV+ Viri 1(5h -Pp V 16t ak).. t [T], E [H],
It is easy to see that these sequences form martingale-differemn w.r. filtration Fe, of (sly (fe "fe,=")) x"), &t, e [H]] U [(ske, of " ="), h' s h)}. Moreover, [Z,, I Herg for all I [T] and h E [H]. Hence, the Azuma-Hoeffding inequality implies
r
P
Zen > H / HHH B(0) < 22exp(-$(()) = 5/8,
A=1
therefore P(E()) 2 6/8.
D.3 Optimism
In this section we prove that our estimate of Q-function Qi a) is optimistic, that is the event
Eopt A VI ( (T), [H] (8, ES A: 2 (s, 22(s,a))
(4)
holds with high probability on the event (8).
Define constants
49 4 2
8 CO
+ +8+
+1.
(5)
Mog(11/))
(1716)
and
2 CJ
(6)
log
[4.((1)
where (b-) is CDF of a normal distribution.
25

---

Proposition 1. Assume that J = [cs 2og R (6. ta = 2, and [[co + 1og17/16 (T)) k). Then conditionally on (6) the event
Eantioone -
(iplorr) ) ve E (T), vh E (H],
max jEDI
W
jecc V (5 h+1
2 ph Vh (8, ()(3,a)
holds with probability at least - 6/2.
Proof. Let us fix & ( [M] (s. E E A. and E [J]. By Lemma 3, we have that the vector (W; j.c.,)) has Dirichlet distribution. Note that Vi+1 (bh+1) ro ( H 1) is
upper bound on V-function and the weight of the first atom is ag - no/n 2 + 10g17/16 (T) for
co defined in (5). Define measure Pe. c2 -gg Pa 1 a) S HI - 1, can apply Lemma 10 with a fixed 1/2 conditioned on independent samples {sh 1Et, from (s,
Ro= TV (HO) D=1 og + V (ef Since
(lnlsra)) 2 ph Viti 15tt1
P
Wi Wheah
k Vhita (8/+11
1=0
1 +
2(ex + nn x)) Kin (Dei, Ph Vhtti (s,
1 - 2
where & is a CDF of normal distribution. Combining Lemma 12 and the event (6)
(ek + ng - H:) Kint (Pey Ph (s, a)) S ex Kinr (Peu,P) Ph ( (s,a)) S (6, T),
where De. = Dis 8 Viz (the and, as a corollary
W
(iallra) s. Vii41 (8h41
(s) (6), (sh 1
1 11
2, (,,
2
1=0
By taking
(6, T) we have constant probability of being optimistic
nk
1 1- 2(1) - %
P
W We Vh+ (5h+1 2 pn Vha (
Next, using choice
[log [2gg2SAHT/8) log(1/(( (2 (1)1)/1111)] = [[. Log(2SAHT//0
(inlaa) h+1
P max
W & Vh+1
(8
pn (.PVihtisss) (((())
21 (1-(1-7)* 21 2SAHT
JEIJ
1=0
By union bound we conclude the statement.
Next we provide connection between ganticone and gopt Proposition 2. It holds that gopt C ganticone
Proof. We proceed by backward induction over Base of induction = + is trivial. Next by Bellman equations for Q¹ and Qi
h - Qi](s, max JE(J]
Σ
w Ve in h+1 (5h+ta) Ph Vi
where n (x)(( (s.a) and we drop dependence on ki 1, h, in é. By induction hypothesis we have
Vi ( 2 1 (s', n* ++())))) 2 (s', = Vini for any thus
Φ (i) max JE[M
Σ Wh Vi Vit (6 Ph (s.
By the definition of event ganticoue (0) conclude the statement.
26

---

Proposition: (Optimism). Assume that J = [ey 1og(2SAHT/8), (.) = 2. and no [co + log17/1e(T)) k],, where ep defined in (5) and сJ defined (6). Then P( ()) 2 1 - 8/2.
D.4 Regret Bound
Let us define the main event (6) = (()) n n On this event we have the following corollary that connects RandQL with OptQL with Hoeffding bonuses.
Define the following quantity
8 (8) max no/ (8), gron (8),
3(8), (8). log(T no))
Corollary 1. Assume conditions of Proposition 3 hold. Let t. E (7), [H], (s, a) E S x A. Define
kf, (8, a) and let tt <... ger be a excursions of (8, a, h) until the previous stage. Then on the
event G'(0 the following bound holds for k 2
0 (2(s, (8)
Σ
Vh h+1 (+41(hh11) Vh+i (5 + (k)),
n
where
(k) = 61e2 No-l (3max (8))
ToH (S (6))*
1201e
ven
Cj
Proof. The lower bound follows from the definition of the event gopt, For the upper bound we first apply the decomposition for Q'x(s, a) and the definition of event (B) from Lemma
(8, (1 + max JE[J]
Wi Di
Jick
nok roll Vel V (5 +
Sra(s,a) +
+ 60c2
Ck + no
Gk + no
Gk + 720
1=1
+ 1200e roHn log(es + (B)
+ ng
Then, by Bellman equations,
1
-)(s,a)-Q((ss0) - ()) <
V h+1
Vitt1 (oh+t))
+
V
pm (n
Ek
1=1
+ (1200e + 1) To H (8max (0))*
ro-l Po mm (8)
60e².
ek + n10
Vea + no
By the definition of event (8) we conclude the statement.
Let us define 8% v (s)) and Ch V1
Lemma 5. Assume conditions of Proposition 3 hold. Then on event (8() = (()) n gopt, where (()) is defined in Lemma 4, the following upper bound regret holds
H
H ΣΣ
H
RR. S eH ΣΣ
1 (
(h)) --1 +
11
1/H1
H-h
Σ
B
Sh
1=1 1=
1=1
A=1
1=1 1=1
where Eh Ph PPiti VV 1ssh 0} for B,, defined in Corollary
a -IVi+ VEL
(15h and BR B (s)
of)
Proof. We notice that on the event gopt the following upper bound holds
T
(8)
1=1
27

---

Next we analyze 6. By the choice of dh. arg ea ()) Corollary 1, and Bellman equations, we have
5% = (shh)) - V (sh) = (2 a/) - Q (sh, al))
= (sh d/.) (7h ah) + (sh abh - Q (sh: a/h)
NR
< HHINE - 03 1(N > 0}
1
Σ
Sh+1 + B% (6 ah) Ph[Vi++ Vitil(sh ah))
N
where kij - (5%, a,),, NY. - ENg. Cr,, episode of the i-th visitation of the state-action pair (sh ai)) during the stage ki,- and additionally by the convention 0/0 Let c = Ph Vi+++ -V ah) [V Vit ( be ceetrigallediffereeee sequence, and B 13,, (s) 1 0} then
[[ > 0} N N
h s HIIN = 0} +
Σ
Sh+z +8/41 + Eh + BB, Sh+1
and, as a result
T
T
T
1 >
0}
N
<
1(M = -0 +
N%
Sh+11
[=1
t=1
t=1
1=1
T
T
T
Sh+1
Σ
8
8
Σ
Bk-
1=1
t=1
t=1
Next we have to analyze the second term, following the approach by Zhang et al. [2020],
N
No
1 1[ > 0}
>
0}
Σ
1 =
Sh+1
N
Sh
t=1
T 1 0}
N
Σ 1 nlle, = =9)
N
Notice that ΣM 1( q} < since all visitations are increasing in i, and, moreover, it turns to equality if and only if (6% a (s), af. and this visitation happens in stage ki where Ry, is equal to the stage of episode q with respect to (s%, ..)h). h). Since the sum over all the next episodes with respect to stage of q, have that the number of non-zero elements in the sum over t is bounded by (1+1/H)N) Thus
ΣSE q=1
Sh
T 1 N
0}
N = 9) s
(1
T Σ
H
q=1
After a simple algebraic manipulations and using the fact that Ch S 58.
T
T
T
1 = -0 +}+ + Σ (1+1/H)) Σ
Gh
+
B
T =[ + (1+ H
T
T
< H
B
By rolling out the upper bound on regret (8) and using inequality (1 + (1+1/H) H-hh h < e we have
H
H
T
H
R% S
eH
Σ
IN = 0} +
H- ctt
e
B
1=1
1=1
28

---

Proof of Theorem 1. First, we notice that the event (8) defined in Lemma 5, holds with probability least 1 by Lemma and Proposition Thus, we may assume that (6)) holds.
We start from the decomposition given by Lemma
H
H oi) -11 + ΣE
H
R
cH
(s
H
+
B
t=1 hm1
==
f=1 h=1
The first term upper bounded by eSAH', since there no than H visits of each state-action- step triple before the update for the first stage. The second term bounded by Ö(VH*T) by definition of the event {() in Lemma 4. To upper bound the last term we have to analyze the following sum
T
(e 0
R
1T+
(s,a)
Σ
Ex+1
(5xxM))SXAx(1])
where
(1+
1
Ck+l $2/EK.
ek
Ve&
therefore by Cauchy inequality
A
(s.0)
ck+1
2
(s.a)
Vex 2 (
Kh (a,a)
Σ
eu 2
log(T)
V mh (s,a),
T+1
log(1 1/H)
D
kmd
where we used the definition of the previous stage kn
1 (s,
2 (s.a)
(s, Z
k=0
thus by Cauchy inequality and inequality log(1 + 1/HH 1/(4H) for H 21
H He
S 2 log(T)
Σ
N +1
(e
[SxAA)SSAA((I]]
< 4v SAH2 log(T)
(N (NT++ (s,a+))
(8.a.))
< 4v SAHST + 44AHH2 log(T).
(ogT))
Using this upper bound, we have
I H
T (eag(et.a)))
>0] = - O + (e
ΣΣ
H ΣΣΣ
t=1 km1m
1=
Combining this upper bound with the previous ones, we conclude the statement.
29

---

E Proofs for Metric algorithm
E.1
Assumptions
In this section we proof Lemma 2 and Lemma 1.
Proof of Lemma By the dual formula for 1- I-Wasserstein distance (see e.g. Section of Peyré and Cuturi [2019]) we have
Wi(ph(s, ()) P,(',d))) = sup
[pn](s, a) () -pnf(s
f i
By Assumption 2 we have
pa,(s, - -pas(s', Be, -
LFg((s, (8', ())).)).
Proof of Lemma 2. Let us proceed by backward induction over h. For h = H + 1 we have ii++ (s, a) = V (s) = O, therefore they are O-Lipchitz.
Next assume that have for any h' > h the statement of Lemma 2 holds. Then by Bellman equations
( (i S (s, a) + (s (s)ss''') Ips (s, pm Vi+t (5', d')l.
By Assumption 2 we can represent the action of the transition kernel as follows
Ph PiVi+i1s, (s, ph V d') Egg, (F,, Ex)) Vh+1 d', En)
Since by induction hypothesis V is - L, and Ex( is L -ipsscchi therefore
H
Le p((s.c),(5()d)) (1s.n))((s
L, LF
Σ
LE
h h'=h+1
H
Σ
1 L
To show that V/2 is also Lipchitz, we have that there is some action a* equal to π (s) or x'' (s'), such that
(s( V (6') > (s,(sa")) Q2(s', aa)) Lua p((s, a"), (8 aa)) S Lv, ps( 8')
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 E > 0 can compute a minimal g-cover of state-action space Ng.
Next we will use the same notation but with state-action pairs replaces with balls from a fixed cover Ng. To unify the notation, we define vhz S A > Ne that maps any point (s,a) to any ball from E-cover that contains it.
For any I, h we define Bi = the (5), of)). Next, let (B) be number of visits of ball B before the episode t: n2 (B) Σ 1(B = B).
Let eд [(1+1/H)* H be length of each stage for any k 2 and, by convention, e-1 0. We will call that in the beginning of episode t a pair (B, in k-th stage n (B) E EE Ci, E ez).
'Remark that the greedy algorithm can easily generate e-cover of size Ne/2, that will not affect the asymptotic behavior of regret bounds, Song and Sun [2019].
30

---

Algorithm 4 Metric Net Net-Staged -at--aag-d-ddd.. RandQL
Input: inflation coefficient K, J ensemble size, number of prior transitions no(k), prior reward ro, dicretization level E.
2: Initialize: E-net Ne, Qn = (B) = roft initialize counters (B( = 0 for j. h B E
[J] [H] N.,, stage (B) 0, quantization map Uha S A Ne.
3: for t E [T' do
4: for h E [H] do
5: Play a₁ E arg max, Qu (the (sh, a)) and define Bd, (1 an). Observe reward and next state 8441 (s). az).
6:
7:
Sample learning rates w, Beta(1 (n2 (B.))(Bn))/n)) for ñ nn (B.). Compute value function (+p+1) = max Qn+1
8:
9:
Update temporary Q-values for all j E [J]
wz) @b( = (1-w;) w + wy (rn an) + (n+1(+n+1))
10:
Update counter n, (B,) == nu (B.) +1
11:
if (i,(B,)) [(1 + 9 for y = 4h (Ba) is the current stage then Update policy Q-values (B,),
12:
maxje[J] Ø (Bx)-
13:
Reset temporary Q-values Q (Bn) := ro..
14:
Reset counter n (Bp) := 0 and change stage ky. (Bn) (B,) +1.
15:
end if
16:
end for
17:
end for
Let n (B) be number of visits of state-action pair during the current stage in the beginning of episode f. Formally, /, (B) = n (B) - EiD ei where is an index of current stage.
and J as number of temporary Q-functions. Let Øi,'" be j-th temporary Q-value and Q be a policy Q-value at the beginning of episode t, defined over the e-cover. We initialize them as follows
Define k > 0 be posterior inflation coefficient, nu is a number of eseudo-transitie
QB) = rolf, (1. rol..
Additionally, we define to the value function as follows
V (s) = max On (s),a)
aeA
Notice that we cannot precomute it as in the tabular setting, however, is possible to use its values in lazy fashion. For each transition we preform the following update of temporary Q-values over balls B E Ne
2411/25 (1 - (1-waa) 3% (B) + (r,a(r af)) + V..... i (5)
B = B% otherwise,
(B)
where = 7 (B) is the number of visits of (B, h) the beginning episode I, and wyn is sequence of independent beta-distribution random variables wy,ū Bela(1/K, (ñ + na)/k).
Next we define the stage update follows
@h
H+
B
max Φ
(11 (441/2.(B) (B)
di((B)
otherwise
roll 12/ otherwise
(B oh ((1+ [11+1/HH)
51+11(B) =
V (s) min [H h), max Φt (Ve(s,a))):
aed
++1 (s) E arg max Q' (1)
aEA
31

---

where & is the current stage. A detailed description of the algorithm is presented in Algorithm 4.
For episode we will call kj, (B) the index of stage where Q% were updated (and kj (B) -1 if there was no update). For all we define (B) S t as the episode when the stage update happens. In other words, for any the following holds
Qn
(B) max Qh JE[J]
(B) (B),
where (B) O and ex if there 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 eg samples to compute ( for k = Kf (s, a). For this k we define f (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
11/2 (B) (B)
Σ
6K
(raloh ) V ( Vinllshni) W jenn
i=0
where we drop dependence on and (B.h) in l to simplify notations, using the convention
Th an = To, V ( = ro(H - 1) and the following aggregated weights
II (1 wight Wi,, = Wj 0o jn
II w3.9) 12 1.
E.3
Concentration
Let ; (0, 1) NN> x (0, dmax)= - E, and 3 geone, 3: (0, x (0, dmax) - R, be some function defined later on Lemma 6. We define the following favorable events
(,( & vt 4, (B E NN (,, center(B)
1
(6,
Kint
PaVita(saa <
EK
ek
3 (8,E)) A
Vt E [H, [J, (B))
(w j.eu. - E j.co xel)
rh (n afh)) + V (
3
rn H log(ex + (B( (6,
S 60e2
1200e
Ck + no:)
Ck + (
geone (8,E)
V (T, VB - (B):
Vit ( (L11B) - ph 1 ,
(B) LL(B)) S
2r H2 3oone (5,
6N
T H
E(8) A
Σ
[1 + 1/H) H 1
Virh oh) - [Viii V (s
-
1=1 h=1
2erall / /2HT 3(0).
32

---

We also introduce the intersection of these events, G (τ) n (8) 6))n n g (6) n E(). We prove that for the right choice of the functions 8*, gRt, genne 5, gar the above events hold with high probability.
Lemma 6. For any å E (0, 1) and E (0, dmax) and for the following choices of functions B,
(6, 8) _ log(8H/6) + log(N + log(er + 1)),
8 E) log(8H/5) + log( (N,( (TJ).
grone (0, log(8H16) (og((Na log (?T),
( - log(16/8),
it holds that
PP (6, e)] 2 - 5/8,
([ 2 1/88 P[E 2 -8/8..
P| (6, E)] 1 6/8.
In particular, P[G())] 2 1- 6/22.
Proof. Let us describe the changes from the similar statement in Lemma 4.
Regarding event 8* s), for any fixed ball B we have exactly the same structure of the problem thanks to Assumption and sequence of i.idd random variables cf. Thus, Theorem 4 combined with a union bound over B E Ne and H E [H] concludes P E)) 2 1/8.
The proof for the event (5, remains the almost the same, with two differences: the predictable weights slightly changed but upper bound for them remain the same, and we have take union bound not over all state-action pairs (s, a) E S x A but all over balls B E NN
To show that P(Eooue (6,e) > 8/8, let us fix B Ng h H)] and eg [T]. Then we can define filtration Fr,, of ( T TT), &t, [H] f(sh,, x²), h' S h)} and, since e (B) are stopping times for all i I,..., we can define the stopped filtration F. = Fe
Then we notice that X; = 1 ($/+1 ( Ph Vi+i( x
f forms a martingale- martingale-differenee difference an
sequence with respect Fs.,. Thus, by Azuma- coena-Hoefdiing inequality and union bound we have P(goone (6, =)) 2 1 8/8.
The proof of F(E(6)) 2 1 5/8 remains exactly the same as in Lemma 4.
E.4 Optimism
In this section we prove that our estimate of Q-function (1 a) is optimistic that is the event
Eops (5)
VL E [T), E [H] (8, ES A (ve 2 ()(,,)))
(10)
holds with high probability on the event 8 =6.
Define constants
49 4V6 2
Co
+8+
+1.
(11)
Jog Vlg((17/1) (17/16)
and slightly another constant
č log
(12)
4 3+4(1)
where (-)) is a CDF of a normal distribution.
Proposition 4. Define constant L, L,, + Lv + Lr). Assume that J = [ē 1og(NN)], K 2 (6, E,),, ro = 2, and a prior count nu(k)) = [īo + K +
+
H (ex + ny + +k]
eL
dependent on the stage k. where 7o (co + 1 + log17/16(T)) K.
33

---

Then on event E6) the following event
Canticone
vA
W T E [H] B E Ne for k = (B), = center(B)
max JEU
W 10 -
W
pn (s) + Le
holds with probability at least 6/2.
Remark 1. We notice that the obtained result 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 (G DP(v))
G(Ba) ~ Dir(u(B))....,((B.,))
for any measurable partition (BI,... Ba) of X.
Let P. Ei= 8z, be an empirical measure of an i..d. sample Zi...., Zn P. Let be finite (not necessarily probability) measure on X and Pa DP(v + +P,)). Then we have the following representation for the expectations of function f: X - R over sampled measure P, (see Theorem 14.37 of Ghosal and Van der Vaart [2017] with o for proof)
P.f = +1 V.
W Wif(Z,).
where V,, ~ Beta((y],n) Q ~ DP()). and a vector (W....., Wn) follows uniform Dirichlet distribution Dir(I,.... 1). we take nig 8%, for some Zo such that f(Zo) = ro(H - 1)", then by stick-breaking process representation of the Dirichlet distribution we have
Pa. Woroll - 1) WiS(Z), (Wo, Wi) Dir(no. 1, I,..,,
By taking an appropriate X aadd] f we have that Proposition 4 could be interpret as a deriving lower bound on the probability of P(Prf 2 Pf + =L {Z, ).
Proof. First for all, let us fix E h E [M] and B E Nr and, consequently, k = k (B). Also, let fix j E [J]. simplify the notation in sequel, define X, ro(H - 1) and X;
Vi (4,, </ for > 0. Notice that X, for > 0 is sequence of i.id. random variables supported on [0, H 11.
By Lemma 3 have (Wo j.c..kk...... W kk (i)(m 1/k, 1/K). Then use the aggregation property of Dirichlet distribution: there is vector (W ..... W Dir((no(k) no)/K, RO/K, 1/R,.................... 1/x) such that
X W
XD +
WjX,.
Next going represent the Dirichlet random vector W by stick breaking process (or, equivalently, represent via the generalized Dirichlet distribution)
W Ej (W9 W W (1 - E1) (W) ...... W
&j Beta((nnnk)) - 7o)) (er + m)) 1s)) W, Dir(no/ /N, 1/k,.... 1/K),
We can augment the space X with this additional point needed
34

---

where E and W are independent. Therefore, we have the final decomposition
W S pn PnViiti - EEyr((H ph Vn 1 13
Tapprox
-1)
Σ WjX, Pn PnViit(3,a))
Tasach
By independence of E and W we have
TP
W
Jien. X, 2 PA (s, (2 (X,
2 P approx 2 20] PP] 2 0j.
PTapprrox
We split our problem lower bound the two separate probabilities.
Approximation error To deal with approximation error, we first of all notice that pa (s, H 1, therefore we have
Plaapprox 20 H -
Next assume that < (H - 1)/L, since E Beta((no(k)) no)/ (ex + mo)/k), we may apply Alfers and Dinges [1984, Theorem 1.2")
PTTappie 2 0] 2 1b (-signn(p po) / k2p
where (k) No0 (ex + 7o k) and μ = =L. (H 1). Since no [mo + K H-1
(ex + No + x) we have P/Tapprox 2 0] 1/2.
Stochastic error Since Xo ro H - 1) an upper bound on V-function, and we have that the
weight of the first atom ag - 70/k - co + log17/16 - for co defined in (11).
Define measure De, = na-n 5x, + Σ i=1 - 5x, Since pM (8,) S H h 1, we #x
apply Lemma 10 with fixed = 1/2 conditioned independent random variables X;
ck Σ
Wjx:
pn PnVi+120,00 [x
+ 2(ex + no 1.) Kint (Te Ph PiViita (i+z(s,aa) (i ))
1
2
K
where & is a CDF of normal distribution. By Lemma 12 and the event (6,
(e& no - 1t) Kint (Vez: Ph Vn 1 S ex Kint (Des Ph Vit (s) S (8,
where De, c Dee 6y (F ) and, as corollary
P Σ
W w pm (s, (6, (X,
11-1
1100/
( (8,
K
By taking x = 2 (6, T)) we have a constant probability of being optimistic for stochastic error
PlTstoch 2 0 (ō,=)) > 1-4(1)
Overall, combining two lower bound for approximation and stochastic terms, have
W Wi X; 2 ph Pr + +eL)E 2 1- (1) 7.
P
35

---

Next, using choice J = [log((2HT/)) (og(NN))/oog((1/// -))1 = = (log(2HT))) - (og()N))]
Ck W
K Pa Vit + ( 21 (1 -)) > 2N, HT
max Iala
By a union bound we conclude the statement.
Next we provide connection between & ganticone and gopt.
Proposition It holds gops C ganticone,
Proof. We proceed by 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 (8, a) that is the ball where (s, a) contains.
Next by the update formula for Q% and Bellman equations
(v) (s) ()) max JE(J]
W Ir off) rn(ss,aa))
W jnn Vita Ph Vitta(b', d') ) () - Qh(s', a'));
10
where n (B) and drop dependence on k, 1, h 8, in E.. By induction hypothesis have (5) ( Qu+i (VE (s'))
Qh+1 (8, x" (s') = (s') for any i, ttus combining it with Lipchitz continuity of reward function and Q", and the value of (s ,aa' = > rn(s, a),
(1 - (s, a) 2 max W JE[J] jan Ho - Σ
wi Jon
Vh I (F% oh (...))))
im
Ph V (s', - (Lr + Lv)e.
Next we apply Lipschitz continuity of F3 and Vi+ and obtain
()) - a)) 2 max SE[
W No 1) Σ W Vh+ (Fi(sd ((.))) 1=1
Pa V (8, a') - (Ir + [v + Lr))e.
By the definition of event ganticone we conclude the statement.
Proposition (Optimism). Define a constant = L, + Lv (1 + LF). Assume that J [ (1og(2HT//8 + log(N:)], K = 2,, T,),, ), ro = 2, and a prior count no(k) = Nño + k + H-1 (ex + no + +)] dependent on the stage k. where 7o = (co +1+ log17/1e(2Ex)) ni, co is defined in (11), ē is defined in (12). Then P(gopt E9 (5, e)) 2 1 5/2.
E.5 Regret Bounds
As in the tabular setting, first connect algorithm to the algorithm by Song and Sun [2019]. using the following corollary. Define an event G' $) = G c) n gopt.
Let us define the logarithmic term as follows
/o, /o/ 8d (6, B(,, geone gmmx (5,e) max (x,
that has dependence of order (log(THHH) + N.).
Corollary 2. Fix (0, Lv / H) and assume conditions of Proposition 6. Lert E [ E [H], B Ne. Define is kj (B) and let l' <... 8 be excursions of (B, h) till the end of the previous stage. Then on the event ('()) the following bound holds for k 2 0 and any (8, a) E B
0 0 (B) - (7, <
V +0
36

---

where
(2mmx (8, (8,=)) 240le (k) = 121e?.
(3maa (6. =) + +3L,, + (1+ + LF)E
6h
Ek
The lower bound follows from the definition of the event gopt. For the upper bound we first apply the decomposition for (,,s, a) and the definition of event Ed (6, from Lemma
Proof.
max (B)
Σ
ca
W
Th o
Ve h+1 hht1 (6ht)))
jE(M]
(h a + Vh+ (
no(k) 2H ek + (k(k)
+
6k (k)
i=1
H2 (6,
HI log(n (B Cx + no()
120c
2400c
Cx + (A))
Additionally, by Bellman equations
(s.
CN
27 o
1
Σ
(h(o,a) (7h
Ck
CK
(nhsh af))) + pm Virta af)) .
22LV.
Ck
Combining and using the fact that nk(k)) S --1 (ex + mo(k)) no + k for Ly (1 Lr)Ly ()(s,)) - ()) S
Le
h+1
Vitt1
(5 (sh+z))+
1
(ita(sh - ph Vitz(sh aht
Ck
H2 (2 (5, E)) + (2400c + 2)
((3max(5,))) 3Ic.
+ 120c2...
ck
Finally, the applications event gcono(8, e concludes the statement.
Let us define 8% = -V (sf)) and Sh = (s,)) (sl)) Lemma Assume conditions of Proposition 6. Then on event g' (8(88 (8
G(8 E) n gopt, where
c is defined in Lemma 6, the following upper bound on regret holds
H
R.. 2eHl ΣΣ
1( 0}
H + ΣΣn B E
t= h=1
t=1 h=1
where 5/ = Ph [Vitt h+1 - (s ot.) Vitz
V (55 and B = B, (sh. af))
(sh, d 2 0} for B), defined in Corollary 2.
Proof. As in the tabular setting, we notice that on the event gopt we can upper bound the regret in terms of 8
T
RR
<
8
(13)
Next analyze 8% Since aj arg max Q (wbe (sh a)), we can Corollary 2 and Bellman equations in the following way
5% (i( V (sf) o% Qi' (sh, at))
= (((B) (h of)) + (sh, ah))
Q" (sh, a/))
N
Sh+1 + Bl (KA) Pa Vatilleh oh)
Fn
SToH1IN tO 11 > t}
Nt
i=1
37

---

where K/ = (B)), N -xt Ei, is an i-th visitation of the ball Bj, during an stage kj and additionally by convention 0/0 O.
Define 5 Ph h+1
V (sh of) - [V V 1h+1l(sh+21 martingale-difference sequence, 0} then
and B B (
1 1[V > 0}
% S 1 = 0}
h++ G/-1 + 8/+1 + ch + Bj.
N
and, as a result
T
T
T
L(NE 0}
NA
Σ
h S ro Σ
1( = 0}
Ny
t=1
1=1
T
Shet1
8
+
S
+
B
tm
t=1
For the second term we may repeat arguments as in the proof of Lemma 5 and obtain
N
Σ
Sh41
Σ
11 o) = [
Sh+1
q=1
After a simple algebraic manipulations and using the fact that C/ S 0%
1[ = 0 + Σ 1/H)ch+1
Σ Sh
+
Bk
(=1
t=1
T
T
1 = 03 + (1+ H
<
+
+
B
t=1
By rolling out the upper bound on regret (13) we have
R.. 2eH
1[ 0} +
Eu+11/H)
het
Sh
B
t=
1=1==
=1hm1
Proof of Theorem 2. First, we notice that the event (' E) defined in Lemma 7, holds with probabil- ity at least 1 - 8 by Lemma 6 and Proposition 6. Thus, we may assume that ('(5, E) holds for > 0 that we will specify later.
By Lemma
RF S 2cH
ΣV 1=1
-
ΣΣ 11+1/H 1
+
Σ B
(=1 h=
The first term is upper bounded by 2eH3 No. since there is no more than visits of each ball in e-net before the update for the first stage. The second term is bounded by O 333 (5, E)) by definition of the event E()) in Lemma 6.
To analyze the last term, consider the following sum
T H (E) > 0
(B)
Σ
Ck-1
(CH)(BB))
Vex
B..))ENe(HH
K=D
38

---

where
(1+ H
H 7
e ve
S 2V
1 4/2
therefore
kg (B)
S 4V (1 + 1/ H (3 (B)+
ek+1
V (BB++
(14)
Vee
V1+1/H-1
==
Notice that
(B)
c HH (B)+1 NT- +1
+
(B)
Σ k=0
H
thus from the Cauchy-Sehwarz incquality
4VH
Σ
V ( +1
(B.M)EN.
S SAH2
(N 1) 5ATT))/HHTT.... N, 4
(B,h)
By the similar arguments we have
T (ENA(BE) >
ΣΣ
<OHNN, log(T)).
(R),(B))
Using this upper bound, we have for L Lr + (1 LF)LY
1 (eng(es > 0]
Σ Σ By 0
H Hgmax (5,E)
T
(e > 0}
+ H(8mux(6, (6,e))
t=1
1=1
+ O(LTHE)
< 0 (VHTTN (3max (6, 8))2 + H No (3 + LTHH).
Overall, for any fixed > we have
RT. < COVHHHTH,,
(8,=)) + H (8 LTHE + H3T
Next we finally use that S x A have covering dimension de that means S CN E de thus our regret bound transforms follows
भ.. @ HOTCNe- (log(TCxHH/8) (lg/TC/ de log(1/s))2
+ LTHS)
By taking s = (1((((++2) we conclude the statement
39

---

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.
E.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 hicrarchical 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 diam (A) maXz,yEA p(z, y).
A we call
Definition 6. A hierarchical partition of S of a depth d 0 is collection of regions Pa and their centers such that
Each region B E Pa is of the form S(B) x A(B), where S(B) S AA:
Pa is cover of S x A: UBEP, B B= = x A;
For every B Pa, we have diam(B) I dmax 2-
Let B1, B2 E Pa- If B1 * B2 then p(center( (1, center (B2) 2 dmax 2-d;
* For any B E Pa, there exists unique A E Pa-1 (called the parent of B) such that B C A.
and, for d = 0 we define it as Po = (S A).
We call the tree generated by the structure of T = (Pa) a20 a tree of this hierarchical partition. The main example of this partition is the dyadic partition of S x A in the case of S = [0, 1]ds AA [0. 1d4 and the metric induced by the infinity norm p((s, a), (s', (6',a') a')) maxflls s' s'lloo, a'll =0 For examples we refer to [Sinclair et al., 2023].
F.2 Algorithm
In this section we describe two algorithms: SraptiveRRandie which an adaptive metric coun- terpart of RandQL, and Adaptive SlaptieeSttaged- (caged-Randie which is an adaptive metric counterpart of Sraged-Randde First, we start from the notation and algorithmic parts that will be common for both algorithms.
Algorithms maintain an adaptive partition Pj, of x A, that is sub-tree of an (infinite) tree of the hierarchical partition T (Pa)a20- We initialize P) (Po). and then we refine the tree P be adding new nodes that corresponding to nodes of T. The leaf nodes of Ppt represent the active balls, and for B Pf the set of its inactive parent balls is defined as { { PP B B'). For any B E PÍ we define d( ()) as depth of B in the tree under convention d(S x A) 0.
Additionally, need to define so-called selection rule and splitting rule. For any state S we define the set of all relevant balls as R2 (s) = active b E PA (s,a) E B for some a E A).
Then for the current state s), we define the current ball as B arg max Q' (B) and the corresponding action as af,- To define the splitting rule we maintain the counters ni (B) for all B E P/, as a number of visits of a node B and all its parent nodes. Then we will perform splitting of the current ball Bi if / // / ( < diam( BB)). During splitting, we extend pi+1 by its child nodes in the hierarchical partition tree T. For more details we refer to [Sinclair et al., 2023], up to small changes in notation. In particular, their constant Ö' is equal to dmax in our setting to make the construction exactly the same for both Adaptive Seaptive-Randdue -RandQL and Adaptive-Stan algorithms.
40

---

Algorithm 5
1: Input: ensemble size J, number of prior transitions no. prior reward ro-
2: Initialize: (B) (B) r, initialize counters (8, a) 0 for 8, E [H] x S A.
3: for E [T] do
4: for h E [H] do
5: Compute B₁ = arg (es) 2, and play an for (sh, 0%) center(Br)) Observe reward and next state 8/+1 ps. (Sh: ap).
6:
7:
Sample W ~ (n, no) for n = nA (Ba)- Compute value V hn-1 (86+1) 1) = (*0-1) (B)
8:
9:
Build targets for all j E [J] 2 رy (sh, and + + ++++1($4+111 úh rrH..
10:
Sample learning rates w, Beta (H).). Update ensemble Q-functions for all [
11:
(RaB)) = (1- wy w,)a% (sh, an) + wr
12:
Update policy Q-function (sh, an) == max (/, an). Update counters nu (BB) == n2, (Br)) + 1;
13:
14:
(Fvdee /ddmax/ny ( (Ba) I diam B,), then refine partition B, (see Sinclair et al. [2023]).
end for
16:
end for
adaptive-Randee This algorithm is an adaptive metric version of RandQL algorithm. We recall that for Pf, we define ni, (B) = E ((B)), is a parent B} is the number of visits of the ball B and its parent balls step h before episode t. We start by initializing the ensemble of Q-values, the policy Q-values, and values to an optimistic value Q1 (B) = 2% (B) = V (B) = H for all [J] x [H] and the unique ball in the partition B = S x A and ro > 0 some rewards
(j, h)
At episode we update the ensemble of Q-values as follows, denoting by n nj, (B) the count, Wj.n Beta(H, n) the independent learning rates.
2 = [(1 - Q (B) + Win, Q (sh, a/), B = B (B)
otherwise,
where we defined the target 2% (s/, af))) as mixture between the usual target and some prior target with mixture coefficient Wnj Beta(n, no) and no the number of prior samples,
2dd (sh. af)) = wy (sh, a + V V (sh )) + (1 wzjn)roff.
For a discussion on prior re-injection refer to Appendix B. The value function is computed on-flight by the rule V (s) max (B).
The policy Q-values obtained by taking the maximum among the ensemble of Q-values
Q (B) max Q (B) JE[]]
The policy is then greedy with respect to the policy Q-values and selection rule (s, + (s)) =
center(B), where B arg max 11 Q)7² (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
++
The notation for this algorithm is very close to Net Sent-Stage--Raadeee and we describe only differences between them. The main difference a way to com- pute value (i(s) maxBER)(s) D' and policy (s, (s)))))) center(B) for B
41

---

Algorithm 6
Input: inflation coefficient K, J ensemble size, number of prior transitions no (k(k), prior reward
2: Initialize: (B( = () (B) = ro Ho initialize counters 7;, = 0 for j. h. B [
stage gh. (B) 0.
3: for t E [T' do
4: for h E [H] do
5: Compute B₁ arg maX (es) (n) and play an for (Sh, an) center
6: Observe reward and next state 8h+1 Ph (sh. an)-
7: Sample learning rates w, Beta(1/K; (n no (Bx))/K) for ñ. n.. (Br))
8: Compute value Va- (8h+1) BER (sh (B).
9:
Update temporary Q-values for all j E
(B) = mx) (B) + wi (sh an) + Vh+1 (+++(811))
10:
Update counters nn (B,). := Nú (B,) + and nu (B,) == ny (Br) + if (,, [(1 + " for q (B,) is the current stage then Update policy Q-values (B,) maxje(J] 2% (B,).
11:
13:
Reset temporary Q-values Q% (Bn) ro..
Reset counter 7i (B,))= = and change stage kn (B.) == k2 (B,) +1.
15:
end if
16:
V P (/nnn//BB, (Bn) S diam Br), then refine partition B₁ (see Sinclair al. [2023]).
17:
end for
18:
end for
arg maxXBER;CC (B). Additionally, all counters including temporary will move to the child nodes after splitting, as it performed in Shaptive-RandQae The detailed description is presented in Algorithm 6.
F33 Regret Bound
In this section we state the regret bounds for SSaeeeeeStteee-aaaae and derive a proof. The given proof shares lot of similarities with the proof of Net Pet--ttaed Staged-RanddL RandQL in the first half and to the proof of Adaptive Staptive-LL -QL by Sinclair et al. [2023] in the second half.
We fix 5 E (0, 1). and the number of posterior samples
J Tē (TT(2CxxT/O)) + de logz (8T /dmx)m))))],
(15)
where ē, 1/ h//////////3/111// (1))) and ((-) the cumulative distribution function (CDF) of a normal distribution.
Additionally select
L dmax
Ek + 7ig + K
(k)) No + K +
No (co + +1+ log17/1o
--1 VHex k H22
where co is absolute constant defined in (5) (see Appendix D.3), k. is the posterior inflation coefficient and I. = Ly + (1 + Lv is constant. Next we restate the regret bound result for Staptive-Stagen Randdd algorithm.
Theorem (Restatement of Theorem 3). Consider a parameter ă (0, k A 2(lg(SHHCx88) d, log, (8T /dmx) + 3 log(e>(2T + 1))), ro 2 2. Then it holds for with probability at least 1- 5,
H
d
RR = (
LH3/2
Σ
h=1
where dz,h the step-h zooming dimension and we ignore all multiplicative factors the covering dimension de.
42

---

Proof. We divide the proof to four main parts, a little bit different proof of Staged Staged-Randee RandQL and Met--Staeed-aae -RaddQL 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 TD.
(8)
VIEN,
(I) E To, ko,k= (B)( (s,a) center(B):
1
8 (6, ex,E)
Kint
Vy (F ()) .p Pa
6k
6k
(6, T) &
V1 V -(
TO.
(wi jien.h
(ra(sh agg) + Vh (5
K=0
((H3mBB(8EE)
1200e ry TuHn no (B( =))
S 60e2
Ck + (k(
Ck +
(n) nk(
goone (8,T)
Vt E [7], 4h E Ill]
TD. k = (B):
Vitt (8 (ir1B)) - ph Vhn (8)
(B,( (in(B))
2r 222eooon (5,
, .0
1
Ck
1=1
T
E(8)
(1 + +3/H) H1 PA
V
10 a/h) - Vh+t - V (6/+11)
t=1 h=1
20 ro (()
To apply the union bound argument, we have to bound the size of To. First, we notice that relation between centers of balls in each layer Pa implies that there at least [Pa] non-intersecting balls of radius dmax 2 2-2-2 Thus, the size of this sub-tree could be bounded as
IDD < Σ
Namma2-a-2 S CN
E(2++ /dmxx) de S (8/dmaxx) ON 2dc
d=0
d=0
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 E P/.
(
dmax
dinax (diam
(B) S
(16)
2 diam (B)
Our goal to find value D such that P/ TD for any MDPs and correct interactions. To do we notice that it is equivalent to show that diam(B) 2 dmax2 2- D, that could be guaranteed since
diam(B) 2 dmax
dmax
2
nh T++
27
which implies that D = 1 + log, (T') is enough. Finally, since for the value of interest
log |TD S de logz( + log ON + de log(8/dmax),
can define the 3-functions as follows follows
43

---

(6) A log(8CxHH/0) + d. loggg/g (dT + log((e - 1)),
(6, T) - Og(88yyHH)) + d. ( dmax) + ITg(
geone T) & Iog(8Cy H/6) + de logz (08) /
(2T):
((6) - log(16Cx
de logz (87 (8T/)max),
and following line-by-line the proof of Lemma 6, for an event ( 8* (0)))))) E() we have P(G(
(6, T)n
6/2.
Optimism Next, we state the required analog of Proposition 4, We can show that with probability at least 1 - 6 on the event Ex (6) the following event
Canticone
vt E (h W [B TD: for k K,,(B,, (3, center(B))
max JE(J]
Wo Jick To( (H-HH-110 1) 1)+ +
W
Jiek Vh+ (Fn(s, (,),,, (h'))
2 Ph Vh+1 (8, + +L diam (B))
==1
under the choice J = [ēg (log(2H7) /6) + log (bg((TTl)))l.... k ==33) (6, T), rn = 2, and prior count
L dmax
ek 710 +
no(k) Mo ++
H
VHez k- H
dependent the stage k; where 7o (co 1 l0g17/16 (T)) K, L L, + Lv(1 Lr). In
particular, the proof exactly the same the proof of Proposition 4 for dependent on k.
At the same time, it possible to show that aanticono implies
Eopt - { E [ h [H] E ((. B: Qh(B) (1B)) 2h(,,a)
(17)
Indeed, in the proof of Proposition we actively uses the bound p((s af (s, a)) S E. In the adaptive setting, we have to, at first, use an upper bound p((sf a ), (s, a)) diam (B²) by construction B C B and then apply Lemma B.2 by Sinclair et al. [2023] by defining an upper bound
diam B,, ) dmax
dmax
dmax
dmax
(Bf)
VE=
V V
VHe k H²
for k = (B) for particular ball B E P/, in the case Her - k 2220
By combining event Expt and the event 8 ( we can prove the same statement as Corollary
Let t E [T], h [H], B E Pl Define & ky (B) and let tt < ger be excursions of (B, h) till the end the previous stage. Then on the event G'(6) = G(6) n Eopt the following bound holds for k 2 0 and for any (s, a) B
0 & 2) (B)) s (1
h+ (s -ii -Viii--Viiiiiia (8h+ (18)
1=1
where
H2 ( (5. T)
H(3max T))² (
5L. dmax
B¹ = 121c²
+ 240le
(19)
ek
VHex
where k = Kg. (B)) and gmax (8, = max 18 (6, (), 3) (8), geone (()) this bound in terms of diameter of B follows
Also we can express
dmax
dmax
dmax
dmax 2 H
diam(B))) 2 ( (B,)
2 D
2 11 *
1/H1
dmnx
dmax
2 11 + 1/H1K+I
2 22Hee
44

---

thus
1
3diam (B))
VHek
dmax
and we have
BI 7566e 2 [3max (6, diam(()i)()))//( + 15Ldiam (B))
(20)
p(H, @, 6, L) diam (B));
where we define p(H, 6, L) _ 7566e H H3/2 (8, T))* /max + 15L.
As additional corollary, we have for all t E [T], h E [H]
(s) = max Ci(B) = C (B*) (T( V/)ss, (c)
(21)
where 8 is ball that contains pair (s, (s)).
This upper and lower bound have the similar structure 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 Sim- chowitz and Jamieson [2019]. Cao and Krishnamurthy [2020]. Definition introduces the quantity gap, as, Vi (s, a), and for any compact set B C S A we define gap, (B) = (s,)) gap, (s, a). Finally, we define clipping operator for any μ, M E R
clip(ulv) = f S v).
(22)
In partieular, this operator satisfies the following important property
Lemma 8 (Lemma E.2. of Sinclair et al. [2023]). Suppose that gap, (B) S 1/ S 11 + for any v,, P2, Then
gapı (B)
+ (1+ H P2
+ < clip
H +1
Now apply this lemma to our update rules, producing a result similar to Lemma E.3 of Sinclair et al. [2023]. We notice that
gapa (B)) gapa (sh, af)) = (sh)) (hhs
$ ( Q7 a1)) = (BB)) (shhshh
Thus, denoting v/- = (B())) (s a/)) and, by (18),
#1 = HI k + H2 + B% 12
1 >
V (+ Vitta
6k
apply Lemma 8 and obtain
gap, (B)))
((h)) (hh a s clip
H1 HI HH,, /2 ky, + H By
H+1
(23)
+(1+ H
(42 - Vitza(s
for k/, = (B,)) and BY defined in (19).
Regret decomposition The rest of the analysis we preform conditionally on event G'()) G()) Eopt that holds with probability at least - 5.
By defining 8 (s() V= (s and ch V)((s)) (*7( we have
T
R
Σ
Vi((f))
(0f) <
1=1
45

---

and, at the same time, by Bellman equations
6% vh(sh) Qth m (s)) - Qh a/) + (h(sh ah) - (sh.
(((s Qh(sh. + ( (6h+1) V (sh+1) + +
-V((s)) Qh(sh, (h) + 5h41 Sh+1 + Sh.
where 5/ = 11 Vo o8)) - -Vi++1 - Votil(oh++)) is a martingale-difference sequence.
By (23) we have
V (0%) (7/ at) + +8/+1
Sh+ + 5%
[=1
t=1
T
T Σ
k+1
Sh+1
ck
ext i=1
t=1
t=1
t=1
gapp (Bi,)
clip
H1 (Heg /2 > kh + H²) + B (b+)
H + 1
where Ky = k1, (B,)). Repeating argument of Lemma 5 and Zhang et al. [2020]
T
3 T
1+
ch+1 S
1+
H
Using an upper bound Sh S
8)
we have for any h 2
T
T
T
5/
1
1
b+1 +
Σ
5h
H
1=1
T
gap, (BA)
clip
H1 He, /2 S K4, + H2 + By
H +1
and, rolling out starting with h = 1 we have the following regret decomposition
H
H H
/2 R H²)
= (A)
t=1 h=1
H
gap; (BA)
clip B
(B)
H1
1
Σ (1+3/H)
(C)
Term (A) For this term we notice that for any fixed h the following event
Heg, s 2 + H12 + ([ 1 2(k), + H1²),
that is guaranteed if
(1 1/H// S +3 + k log(1 (1 + 1/H) < (2T H22 +3)
Thus, indicator can be equal to 1 no more than H log(2T + 3) times for any t [T]. As result.
(A) H log(2T +3).
46

---

Term (B)
Let us rewrite this term using definition of clipping operator and use the definition of near-optimal (see Definition 3)
T
H
T
H
B =
1 1)B) gap, S
e.
Σ
(center E 2
Next we consider the summation for fixed h. Here follow Theorem F.3 by Sinclair et [2023] and obtain
Σ (center(B)) =
E E
E 2
B:diam(B)=rt::B))
where we applied an additional rescaling by function p defined (20).
Next we fix a constant Tg > 0 and break a summation into two parts: 2 To and r S To-
1. Case S ro- In this situation have can apply (20)
Σ
Σ
Σ
By 1 (center(B) (B) E 2
rSro
Bediam
B) BB
(TTTop(HH,&,))
2. Case r 2 ro- In this situation we also apply (20) under the indicator function
Σ
Σ
Σ
By l (center B) E (
r2 Brdiam B
- B.
Σ
Σ
2.(H,6.L).r) Iccente((B) E h
Σ
By
r2ro B:diam B:diam(B)=r-p(HHl (B)=r-p(HH...))))
t: =B
To upper bound the last sum we repeat the argument of (14) and apply (16), using the fact that diam (B) = p( (H, L)
(B)
Σ Σ =B
ek-1
< A
Ve
vek
k=0
dmax diam(B)
/32H dmax
S 4
H(n (B) + 11 < 4V2H
As a result, we have by (19)
V32H duxx (25226 H (3 (6,T))* + 5Ldmax/ /oddma//iil /VH
Σ B
LBBB=BB
and
Σ Σ
Σ
(centee))(()) E 2
T2r Bidiam B) =r I.B, =B
Σ r2rO
N. N.(22HH......)
H3/2 10maaam3ma (gmax (3max(8,T)) d))
Ldk Ldmax
Finally, by arbitrary choice of ro and definition of zooming dimension with scaling p = p H., L)) (Definition 4)
})
CN
(B) = (11322 (3max((6T)) + Le
inf
Tro + Σ
idu
1=1
r2ro
47

---

Term (C) For this term we just apply definition of the main event ( 2 (() and obtain
(C) - HHT Bmax (6, T))
Final regret bound First, we notice that g ((de), therefore we have
ON. pdza+l +I
H. =
- + L)
Σ inf
Tro +
Σ
+ v
HHTde
r20o
Taking = K-d2,+112 for each h and summing the geometric series we conclude the statement.
48

---

G Deviation and Anti-Concentration Inequalities
G.1 Deviation inequality for Kint
For measure P((0, bl) supported on a segment [0, b] (equipped with Borel o-algebra) and number μe E [0, bj we recall the definition of the minimum Kullback-Leibler divergence
(ir( pi) & inI(KL(V, m) 7 P([O, b < Ex [X] 2 1r)
As the Kullback-Leible divergence this quantity admits a variational formula.
Lemma (Lemma by Garivier al., 2018). For all b[(0,b)), u E (0, b).
[oo 11
Kmg(U, u) = max Ex~y XE
moreover we denote by X* the value at which the above maximum is reached, then
Ex
S1.
x+
X-
b-a
Remark 2. Contrary to Garivier et al. [2018] we allow that u = but in this case Lemma is trivially true, indeed
x b b )
Ku 0)
max Ex-e log XE(0,1]
Let (Xt)teN+ be i.i.d samples from a measure v supported on [0, b]. We denote by 87 E B)(0,,)) the empirical measure i, Σ 5x,, where 6x, is Dirac measure X; [0, b).
We are now ready to state the deviation inequality for Kinf by Tiapkin et al. [2022b] which 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 Kints however, the proof remains completely the same.
Theorem 4. For all v P((O, b)) and for all 8 [0, 1].
P(3n E E n (nn (xxxl(X) > log(1/5) log((eT( + 2m))) S 6.
G.2 Anti-concentration Inequality for Dirichlet Weighted Sums
In this section we state anti-concentratton inequality by Tiapkin et al. [2022a] in terms slightly different definition of Kinf-
2
co(E) [oog(17/16) +8 49 4
π log17/16
(24)
32 32 g2
Theorem 5 (Lower bound). For any a = (oo + 0n
am) E R define E Am such
that p(() = az/a, = O....,m m, where a = Eド= ag. Let E E (0, Assume that ag 2 co(s) + (0g17/16(TT) ( for cole) defined in (24), and क 2 200 Then for any f: (0...., m) - [0, bol
such that f(0) = bu. f(i) & < ba/2.j (1....,m) and (pf.bo) bo)
m Σp(t) 8
P Pa.DDi(()) lwf 2 A) (1 Po) 9
2 King
Next we formulate simple corollary of Theorem 5, that slightly relaxes assumptions of this theorem under assumption μ < b 2
49

---

Lemma 10. For any (0o + 1, a1....... am) E RR define p Am such that p(() = at/a, O,..., m. where a = مド= aj. Also define a measure D = 0 8(())
Let e E (0, 1). Assume that oo 2 (5) + 10817/16 (2( -o)) for ca(s) defined in (24). The for any
f: {O.....m) m + [0, such that f(0) = bo, f(i) S b b j E [m]. and any p E (0,b)
P Pw-Dir(a) f 2 p 2 (1 - P) PPPPNO..)) g
2 KnnlyDD
Proof. Assume that assumption 20g holds.
Then we show that the Theorem also holds for S pf. First, we notice that for any 7 > 0
Fu--Di((a) [f 2 μ4 2 P ww-DDi(a) wff 2 pf + 7 2 (1 - E)P (o 2 /2a Kunt (1, Pf + 7)
By continuity of Kinn in second argument (see Theorem by Honda and Takemura [2010]) we can tend to zero, and then use an equality Kinr(2, = (1, (s) = 0.
Next, assume < 20g. In this case we have pf 2 b, thus for any PSb
P Pw-Dir(a) wwf μ4 (e- 11a 100 idog 2 p1 B (x {
where first apply lower bound f()) 2 0 for all j and f(0) bu. and second apply bound μ & 20/2. Here we may apply the result of Alfers and Dinges [1984, Theorem 1.2"] and obtain the following lower bound
P Pw--Di((a) (wf pl 40(- (-siign(ao/a 1/2) v 2a 22 blakl(a// (ā, 1/2)) 2 (1 (1-68 g- 2
where we used a 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 Xi...., X,, be a martingale-differeeee sequence adapted to filtration (Fejimt...... E[X,|=] = O. Define V; = [ Then for any p 2 2 the following holds
R/2
n
/r
X,
< Cip
Σ V
+ 2C2pl3
max X
(E(m)
where C1 60e, C2 60.
Additionally, we need some additional lemma to use this inequality in our setting.
Definition 7. random variable X is called sub-exponential with parameters (a?, b) if the following tail condition holds for any >>> 0
12
P|
E|X] 2 t < exxp
20 + 2bt
By Theorem of Skorski [2023] we have for any & E B(a, with B 2 and any t 0
PPL - E(g]| 2 t] s 2exp
2(U ct/3)
where
0₂, (a aa+ 2) (a + 3 B+1)
a
2(3 -)
< 2
<
c=
(a 3)22
(a + ( + B
a a+B
f (a/(a +33, + B)) sub-exponential.
50

---

Lemma 11. Let Xi..... Xn be a sequence of centred (o², b) sub-exponent cobeexxonential random variables, not necessarity independent. Then for any p 2 2
E
max EEIm
Xel
S max 80 n, Sblog + e(20)) p012 + 20(8b)pp².
Proof. By Fubini theorem we have for any ll 2 0: E|n"]] = Jo u uP1 2 uldu, thus for any 0 the following holds
max (E(n)
X
P
= p u
max [E[n]
Xe - E[Xe| 2 u du
S a" +
u w PPEE E [n] : |Xel z dl
u²
S a + 2p
un nexp
du.
2( + bu)
By selecting a = maxl / 80 log n, 8b log no we have
u²
S exp (- u²
u²
n nexp
2(0² + bu)
([(002 + bu)
S exp
80
+ exp
88b
for any 2 a. thus
E max Xxl" [E|m
< max / 1802 log n, 8b log n
+ 2p u exp
u
du + 2p
000
wn1 exp
u
du
80
86
max V 80 log n, 8b log + p22/2222 + 2p(8b)
By the bounds on Gamma-function we have
pp(p22) l(p/ 1) (p + 1 13004)/22--00+)/222------
epr p/2
and pT(p) = [pp 1) - (p+ 1/2) 1/ < cp (see Guo et al. [2007]), thus
E
max
X < max v 80² log &blonn/ e(20)) + 20
LEin]
Proposition 7. Let Wi,- W. be a sequence of Beta-distributed random variables W, Beta(1/k, /x (n - 1)/x) for > Let (Fiheej)) be a filtration such that W, is independent from Fi-1 E[W; = E[,, and X1...., Xn be a sequence of bounded predictable random variables: E[X, = X. [X, S B.
Then with probability least 1 the following holds
n
12
logg(1// (1/0)
1200eBB log(n) log" (1/8)
W.X,
72 S 60e² B
X
n
n
Proof. First we notice that Z. (W; - E[W:)) E[ = 0. Therefore, we can apply Theorem 6
X; forms martingale-difference sequence:
p/2
B1/p
Z
< 60e/p- B1/p
Σn
V
120p
1//P
max 2212
[E(m]]
where v = 1 random variable and obtain
= X? Var( W.)). We can easily upper bound the variance of deta-distributed
1//2
p/2
K X2
kB2
E
1/p
Σ V
< 1/p
n²
n
51

---

For the second term we apply Lemma 11 since W are (x/n², ( (uul)n))ssueeepoeeeinie
Se log
16k log
16%.
E
max iE|m]
Z P
B
max
+ t 1/
V n2
n22 (2c) 1/p
3n p
n²
3n
log
20.K
Therefore we have
kB2
Br
log n
E1PP
60e p2/2
1200 p²
n
n
Next we turn from moments to tails. By Markov inequality with 10g((16))
K E
Σ 2117 )
P
Σ
Z
2t
t
1og(1/8)
60eB / x log 1/0)/n 1200 log (1/0)x/x0xx)
Taking = 60c2 Bv #log(1/6) / 1200eB A log(n)) (1/8) we conclude the statement.
H Technical Lemmas
Lemma 12. Let v E P((O.b) b]) be a probability measure over the segment [0, bj and let (1 a) a) + +a- V be mixture between and a Dirac measure on bo >> Then for any E (0, b)
Kin n) S (1 ai) (L,
Proof. By variational formula for Kinr (see Lemma 9)
Kint p1)
max XE (0,01/(bbob))))
E Exx<olog(( A(X p))].
Since 7 is mixture, we have for any À E [0, (bo n)]
E Ex~o|log(1 A(X x))1 (xx))xxxologg/ A(X n))] a log(11 A(ho x)).
Notice that maxaso log(1 A(bo p)) O. Thus, maximizing each term separately over X, we have
(i, S (1 a)
Ex-o A(X -1))]
xe(0,1/(bo-pp =)]
< (1 (1-a)
max \=(0.1/(b-w)
Elool A(X 1))] = (1 a)) (in H).
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.
L.1 Tabular experiments
In our initial experiment, we investigated simple grid-world environment.
52

---

800000
romc Randomized stage
700000
Sampled randamizeed QJ.
600000
103830
200000
100000
0
5000
10000
15000
20000
25000
30000
<pisode
Figure 2: Regret curves of RandQL, Staged-RandQL and Sampled- -andddQLL grid-world envi- ronment with 100 states and actions for H 50 an transitions noise 0.2. We show average over seeds.
Environments For tabular experiments we use two environments.
The first one is grid-world environment with 100 states (i,j) [10] [10] and 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 e, and moves neighbor state random with probability = 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 a chain environment described by Osband et al. [2016] with L = 15 states and actions (left right). The horizon is equal to 30, the probability of moving into wrong direction is equal to 0.1. The agent starts in the leftmost state with reward 0.05, also the largest reward equal to is the rightmost state.
Variations of randomized Q-learning First we compare the different variations of randomized Q-learning grid-world environment. Precisely consider:
RandQL a randomized version of OptQL, detailed in Appendix B.
Staged-RandQu staged version of RandQL, described in Section 3.2.
Sampl Compled-Raan ed-RnddLL 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 = 1.0, no = 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 al. [2022a]. For Staged-Rard -RandQL we use stage of sizes ((1 + 1/H))*)) k21 without the H factor, in order to have several epochs per state-action pair even for few episodes.
The comparison presented Figure 2.
We observe that RandQL and Sampled Compled-Rannee RandQL behave similarly with slightly better performance for Sampled- -andRd.LL. This is coherent with the experiment on the comparison between OPSRL and PSRL Tiapkin et al. [2022a] where the optimistic version performs worst than the fully randomized algorithm. We also note that even with the aggressive stage schedule, Beaagd-Randda needs more episode to converge. We conclude that despite that stage simplifies the analysis, it artificially slows down the learning in practice.
To ease the comparison with the baselines, for the rest the experiments we only use RandQL
because of its similarity with OptQL.
Baselines compare RandQL algorithm to the following baselines:
* OptQL [Jin et al., 2018] model-free optimistic Q-learning.
53

---

tamte
37500
OytEk
35300
4X066
Gready
20000
7900
FLSM
200060
4p9.56
02:004
Figure 3: Regret curves of RandQL and several baselines in (left) grid-world environment with 100 states and actions for H 50 an transitions noise 0.2, and (right) in chain environment of length = 15, actions for H 30 with transition noise 0.1: smaller is better. We show average and error bars over 4 seeds.
UCBVI [Azar al., 2017] model- based optimistic dynamic programming.
Greedy-UCBVI [Efroni et al., 2019] optimistic real-time dynamic programming.
PSRL [Osband al., 2013] model-based posterior sampling.
RLSVI [Russo, 2019] model-basee randomized dynamic programming.
The selection of parameters can have significant impact on the empirical regrets of an algorithm. For example, adjusting the multiplicative constants in the bonus of UCBVI 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 algorithm, UCBVI, OptQL we use simplified bonuses from an idealized Hoeffding inequality of the form
h 8 (8, a) e min (Visle,a) (s,(s)))
h hh111 11)
(25)
[2021], this bonus does not necessarily result true upper- confidence bound on the optimal Q-value. However, it is a valid upper- coper-confidence bound for nj, (s, a) = 0 which is important in order discover new state-action pairs.
As explained by Ménard
For RLSVI we use the variance of Gaussian noise equal simplified Hoeffding bonuses described above in (25).
For PSRL, we use a Dirichlet prior on the transition probability distribution with parameter (L/S, 1/S) and for the rewards Beta prior with parameter (L, 1). Note that since the reward is not necessarily in {0, 1} we just sample new randomized reward r' ~ BBe(rr accordingly a Bernoulli distribution of parameter r, 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 tabular environment, but still degrades comparison to model-based approaches, that is usual for model-free algorithms in tabular environments, Indeed, as explained by Ménard et al. [2021], using model and backward induction allows new information For example UCBVI needs only one episode to propagate information about the last step h = H to the first step h whereas OptQL or RandQL need least episodes. But as counterpart, RandQL has better time-complexity and space- complexity than model based algorithm, see Table 2.
more quickly propagated.
I.2 Non-tabular experiments
The second experiment was performed on a set of two dimensional continuous environments [Domingues et al., 202 with levels of increasing exploration difficulty.
54

---

Algorithm
Time-complexity (per episode) Space complexity
UCBVI [Azar et al., 2017]
PSRL al.
A(S
Ō(HS²A)
RLSVI [Russo, 2019]
Greedy- UCCVII [Rrooei al, 2019]
Ö(HSA)
OptQL
O(H)
O(ISA)
RandQL (his paper)
Õ(H)
O(HSA)
Table 2: Time- and space- complexity of several tabular algorithms.
Environment We use a ball environment with the 2-dimensional unit Euclidean ball as state-space {s E RR2 |||||2 h s }} and horizon = 30. The action space a list 2-dimensional vectors A {[0.0, 0.0), -0005, 0.0], [0.05, 0.0), [0.0, 0.05], [0.0, -0.05] that can be associated with the action staying the same place, moving left, right, up or down. Given a state 8/, and an action ap. the next state is
$/+1 = projs (sA + an + 02R)
where 24, ~ (NO, 0], I2) is some independent Gaussian noise with zero mean and identity covariance matrix and projg is the euclidean projection the unit ball S. The initial position 81 01 with 21 ~ (V, (2) and σ = 0.001, is sampled at random from a Gaussian distribution. The reward function independent of the action and the step
( a) max(0, 0, 1 - l|s -
where 00.5, 0.5] S is the reward center and > 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 /2 x 0.71 and the transition standard deviation is 0.01.
Level 2, sparse reward and small noise. The smoothness parameter = 0.2 and the transition standard deviation
0.01.
Level 3, sparse reward and large noise. The smoothness parameter is = 0.2 and the transition standard deviation
0.025.
RandQL algorithm Among the different versions of RandQL for continuous state-action space, see Section 4, pick the Adaptive adaptive-Rand[L algorithm, described in Appendix F, it is the closest version to the Adaptive-ae algorithm. It combines the RandQL algorithm and adaptive discretization. used ensemble of size J 10 R log(T),
For Adaptive -RandQQL a prior number of samples of no = 0.33. Note that we increased the number of prior samples in comparison the tabular case explained in Section 4.
10 s log(?) and
Baselines
We compare Adaptive-Randn RanddL algorithm to the following baselines:
Adaptive-Qu [Sinclair et al., 2019, 2023], an adaptation of OptQL algorithm to continuous
state-space thanks adaptive discretization;
Kernel-UCBVI [Domingues et al., (021c), a kernel-based version of the UCBVI algorithm;
DQN [Mnih et al., 2013], 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-UcHH baselines we employ the same simplified bonuses (25) used for the tabular experiments. For Kernel-UCBV we used 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 netwrok a 2-layer multilayer perceptron (MLP) with hidden layer size equals to 64. For exploration, DQN utilizes s-greedy exploration with coefficient annealing from 1.0 0.1 during the first 10, 000 steps. For BootDQN we use ensemble of 10 heads and not use e-greedy exploration.
55

---

Adaptox D-kaming
Adaplve landemtead
123933
Adepiive Siaaaring
landomkadd
Eockarup
710353
Karnd
far UCBW
02030
63333
032383
50383
23033
2203
5000
7040
16600
12300
15400
27500
20000
2203
3000
7500
18550
12300
10400
57502
2000
123030
Adagtive Luaaiing
103030
ION
23030
193930
Figure 4: Cumulative rewards (higher is better) of Adaptive 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 seeds.
Algorithm
Episode time (second)
5.780e
Adaptive-QL
4.213e
Kernel-UCBVI
1.523e -01
Table 3: Average time of one episode in second (averaged over 20000 episodes).
Results Figure 4 shows the results of non-tabular experiments. Overall, we see that adaptive-Randue outperforms Adaptive-QI. in all environments, especially in the sparse reward setting. However, we see that model- algorithm is much more sample efficient than model-free algorithm, as it was shown by Domingues al. [2021c]. This is connected to low dimension of the presented environment, where the difference in theoretical regret bounds is not so large. However, this performance come at the price of 3-times larger time complexity, Table
Regarding the comparison to ceural-network based algorithms, we see that approaches based on adaptive discretization always outperforms DQN and BootDQN rewards. We connect this phenomenon to the fact that neural network algorithms are solving two problems the time: exploration and optimization, whereas discretization-basel approaches solve only exploration problem.
environment with non-sparse
In the setup of sparse rewards it turns out that neural network-based approaches are competitive with Adaptive-QL and Adaptive- Sappivee-aanQL... Notably, DQN shows itself as the worst one, whereas Adaptive-Rande and BootDQN show similar performance, additionally justifying exploration effect of ensemble learning and randomized exploration.
56


Reviews:
[{"review_id": "PpsCCsxZDg", "reviewer": "Reviewer_PYAU", "summary": "The paper proposes a new algorithm, Randomized Q-learning (RandQL), for regret minimization in episodic Markov Decision Processes (MDPs). RandQL is the first manageable model-free posterior sampling-based algorithm. The authors study RandQL's performance in both tabular and non-tabular metric space settings. In tabular MDPs, RandQL gives a regret bound of $O(\\sqrt{H^5SAT})$, where $H$ is the planning horizon, $S$ the number of states, $A$ the number of actions, and $T$ the number of episodes. RandQL has a regret bound of order $O(\\sqrt{H^5T^{(d_c+1)/(d_c+2)}})$, where $d_c$ is the covering dimension, in a metric state-action space. Interestingly, RandQL achieves optimistic exploration without bonuses and uses a new idea of learning rate randomization. The authors also show that RandQL does better than current methods on baseline exploration environments in their empirical study.", "questions": "Can authors discuss why the randomized learning rate can work in a high-level idea? For example, is it possible that this randomization brings some optimistic?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The introduction of learning rate randomization is novel and interesting, that lets RandQL achieve optimistic exploration without bonuses. This indeed reduce the memory cost.\n\n2. RandQL does well in both tabular and non-tabular metric space settings. In both cases, the authors show that it gives good regret bounds. That's a pretty solid result.\n", "weaknesses": "In the experiments, the performance gap between model-free algorithms and model-based algorithms seems too large. It would be better to provide stronger evidence in experiments of the benefits of RandQL such as lower computation cost, lower memory cost, or possibly has a closer performance in a more complex environment compared to model-based methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are very thankful to Reviewer PYAU for detailed reading and informative feedback. In the following, we answer the concerns raised in the review.\n\n- “In the experiments, the performance gap between model-free algorithms and model-based algorithms seems too large. It would be better to provide stronger evidence in experiments of the benefits of RandQL”.\n\n\nThe main advantage of model-free algorithms in general (and RandQL in particular) is their smaller time and space complexities. For example, the space complexity of UCBVI, PSRL and Greedy-UCBVI is S-times larger than the space complexity of the randomized Q-learning. We present this comparison in Table 2 of Appendix I due to space constraints.\n\n- High-level idea of the randomized learning rate.\n\n\nThe  learning rate randomization aims to ensure that a (temporary) Q-value estimate is optimistic with positive probability, almost independent of the sampled data, which is crucial for the proper bounding of regrets in the randomized exploration algorithms. \n\n"}, {"review_id": "nEjbZjp7M3", "reviewer": "Reviewer_eHBt", "summary": "This paper introduces a new model-free Q-learning algorithm that utilizes a randomized learning rate. The effectiveness of this algorithm is theoretically validated by demonstrating a promising regret bound of $\\widetilde{O}(\\sqrt{H^{5} SA T})$ under the tabular setting. Furthermore, a theoretical bound is established for the metric state-action space in this paper.", "questions": "1. The idea of using multiple ensembles and maximizing to incentivize exploration has been mentioned in previous works. See e.g., [R1, R2] (the reference of [R1] is missing).  The reviewer wants to know the difference and whether this is a general technique that theorists and practitioners should follow in the future. \n\n2. Why is RLSVI viewed as a model-based algorithm in the introduction? What are the computational benefits compared with RLSVI?\n\n\n[R1] Ishfaq, Haque, et al. \"Randomized exploration in reinforcement learning with general value function approximation.\" *International Conference on Machine Learning*. PMLR, 2021.\n\n[R2] Xiong, Zhihan, et al. \"Near-Optimal Randomized Exploration for Tabular Markov Decision Processes.\" *Advances in Neural Information Processing Systems* 35 (2022): 6358-6371.\n\n", "limitations": "Limitations:\n\n- The claim in the introduction that \"Although empirical evidence suggests that model-based algorithms are more sample efficient than model-free algorithms...\" is somewhat misleading. In the field of deep RL, there is no definitive conclusion yet. Please consider revising this argument.\n\n- The vanilla Q-learning algorithm is rarely used in practice. Practitioners typically utilize the target Q-learning algorithm. Please refer to [R3] for further discussion. It is encouraged to investigate this algorithm with a randomized learning rate.\n\n[R3] Zanette, Andrea, and Martin Wainwright. \"Stabilizing Q-learning with Linear Architectures for Provable Efficient Learning.\" *International Conference on Machine Learning*. PMLR, 2022.\n\n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "\n- Introduces a new model-free algorithm with random exploration.\n- Provides provable guarantees under both tabular and non-tabular settings.\n\n", "weaknesses": "The research significance is not well addressed. What are the benefits of eliminating the exploration bonus? What are the promising parts (for future work to develop new methods and apply to practical tasks) compared with alternative methods (e.g., RLSVI, UCB)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are very thankful to Reviewer eHBt for detailed reading and informative feedback. We will add all missing references. In the sequel we answer the questions raised in the review.\n\n- “What are the benefits of eliminating the exploration bonus?  What are the promising parts compared to alternative methods?”\n\nThe main benefit of eliminating the exploration bonuses is that it allows for a straightforward generalization to large-scale problems. While implementing bonuses requires maintaining counters for all state-action pairs and using them directly, our algorithm needs counters only in the distribution of the learning rates, which could be done more efficiently. Also, we must emphasize that these counters are used not for exploration but to forget previous targets efficiently, as was done in optimistic Q-learning, see Jin et al. (2018). \n\nRegarding the present work, our main interest is in proposing a simple mechanism that ensures provably efficient exploration.\nAs compared to RLVSI, our method provides an alternative way for randomization that automatically adapts to variance (without the need to estimate it); see general comment on RLSVI.\nUCB-type methods usually use highly over-optimistic bonuses (see Osband and Van Roy, 2017), leading to poor empirical performance compared to randomized model-based algorithms such as PSRL or RLSVI. The fairest comparison of RandQL could be done with the OptQL method since both algorithms are model-free, and RandQL outperformed the OptQL algorithm in all numerical experiments presented.\n\n\n\n\nJin, Chi, et al. \"Is Q-learning provably efficient?.\" Advances in neural information processing systems 31 (2018).\nOsband, Ian, and Benjamin Van Roy. \"Why is posterior sampling better than optimism for reinforcement learning?.\" International conference on machine learning. PMLR, 2017.\n\n\n- “Idea of using multiple ensembles is not novel”.\n\nWe would like to stress that the main novel idea presented in our paper is to use learning rate randomization, whereas the ensemble learning idea is a technical tool used to provide high-probability optimism. \n\nLearning rate randomization aims to obtain \"local\" optimism to obtain Q-value with a positive probability to be optimistic for one particular state-action-step triple. However, this property is not enough to provide a proper regret bound since \"global\" optimism is needed, that is, optimism with positive probability for all state-action pairs simultaneously.\n\nFrom the theoretical point of view, using ensembles allows one to move from a \"local\" optimism for one state-action-step triple with positive probability to a \"global\" optimism for the initial value with high probability. Mathematically, this idea is described in the proof of Proposition 1 in Appendix D.3. Learning rate randomization gives \"local\" optimism in Equation 7. However, \"global\" optimism requires taking a maximum over the ensemble. \nWe conjecture that ensembles are not necessary to achieve sublinear regret bounds for this algorithm, and it serves only as a technical instrument. Still, it requires studying the properties of Dirichlet distribution and weighted sums of it more deeply.\n\n\n\n- The claim in the introduction that \"Although empirical evidence suggests that model-based algorithms are more sample efficient than model-free algorithms...\" is somewhat misleading. In the field of deep RL, there is no definitive conclusion yet. Please consider revising this argument.\n\nIn the tabular setting this argument holds as it is demonstrated in our experiments see also Menard et al. (2021). However, we totally agree that there is no consensus yet on the question of sample efficiency beyond the tabular setting, for instance in deep RL setting. We will nuance this argument in the main text and focus on the tabular setting.\n\nMénard, Pierre, et al. \"UCB Momentum Q-learning: Correcting the bias without forgetting.\" International Conference on Machine Learning. PMLR, 2021.\n\n\n- “The vanilla Q-learning algorithm is rarely used in practice. Practitioners typically utilize the target Q-learning algorithm. Please refer to [R3] for further discussion. It is encouraged to investigate this algorithm with a randomized learning rate.”\n\nWe totally agree that the extension of our algorithm to the functional approximation setting in the spirit of [R3] is an interesting direction for future work.\n\nAdditionally, the spirit of the target network idea with delayed estimates for the Q-value is already used in the Staged-RandQL algorithm: the Q-value in the update formula after line 194 is delayed. We will discuss this point and a reference [R3]."}, {"review_id": "VkaezHppAp", "reviewer": "Reviewer_axbs", "summary": "The paper titled Model-free Posterior Sampling via Learning Rate Randomization proposes a novel model-free algorithm called Randomized Q-learning (RandQL) for regret minimization in episodic Markov Decision Processes (MDPs). The algorithm introduces the concept of learning rate randomization to achieve optimistic exploration without using bonuses. The performance of RandQL is analyzed in both tabular and non-tabular metric space settings, and it outperforms existing approaches in baseline exploration environments.\n\nThe authors address the challenge of sample complexity in model-free algorithms where the agent has no access to a simulator. They propose RandQL, a tractable model-free algorithm that achieves exploration without using bonuses. RandQL updates an ensemble of Q-values using Q-learning with Beta distributed step-sizes, introducing noise similar to the posterior sampling approach. The ensemble of Q-values can be seen as posterior samples, and RandQL chooses among these samples in an optimistic fashion. The authors analyze the regret bounds of RandQL in both tabular and metric state-action spaces.\n\nThe paper highlights that Bayesian-based exploration techniques have shown superior empirical performance compared to bonus-based exploration, but most theoretical studies have focused on model-based algorithms. The authors aim to extend the posterior sampling approach to a provably efficient model-free algorithm that matches the empirical performance of its model-based counterparts. Previous attempts at model-free posterior sampling algorithms have not been computationally tractable, making this a challenge to overcome.", "questions": "1. RLSVI related algorithm also do not require bonus but can be can be easily compatible with complex function approximation. Also it utilise all history data in previous theoretical analysis (which can be thought as a definition of model-based), it still only track the optimal value function. Could you give more detailed comparison to this line of work in both computation and sample complexity consideration.\n\n2. See weakness.\n\nI could consider increasing score if the questions are properly answered.\n", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The idea of relating learning rate randomization to PSRL Dirichlet sampling is interesting.\n\n2. The first computationally tractable model-free (optimistic) posterior sampling algorithm with regret guarantees in tabular setting and metric RL setting.\n\n3. 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.", "weaknesses": "Although the author claims the algorithm do not require bonus, the learning rate randomization still needs (s, a) counting. Counting is not easy to generalise to practical RL with function approximation. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are very thankful to Reviewer axbs for detailed reading and informative feedback. In the sequel we answer the particular questions raised in the review.\n\n- “Although the author claims the algorithm do not require bonus, the learning rate randomization still needs (s, a) counting. Counting is not easy to generalise to practical RL with function approximation”.\n\n\nWe agree that we need the counters to define the learning rate with the required properties in the theoretical analysis. However, we would like to insist on two points.\nFirst, using these counters comes from the learning rate of the vanilla Q-learning algorithm rather than exploration. This choice of learning rates aims to forget past targets with a required speed. \nSecond, using counters is only needed to define appropriate parameters of the underlying Beta distribution, and it could be done using other (practical) considerations. For example, one can implement a DQN-type algorithm with a random learning rate whose expectation is the same without this randomization and with variance decaying by some schedule. Note that the same trick cannot work with a direct count-based exploration since it requires counters for exploration.\n\n\n\n- “RLSVI related algorithm also do not require bonus but can be can be easily compatible with complex function approximation. Also it utilise all history data in previous theoretical analysis (which can be thought as a definition of model-based), it still only track the optimal value function. Could you give more detailed comparison to this line of work in both computation and sample complexity consideration.”\n\nThe general comparison with the RLSVI algorithm is provided separately. Additionally, our algorithm also tracks only the optimal value function. Still, it uses the randomness from the Bayesian model on the transitions, leading to the Dirichlet process-like posterior on the value rather than the Gaussian posterior in RLSVI. It makes the extension of RandQL to the function approximation setting a promising direction for further research.\nAdditionally, a small probability of the appearance of large magnitude gradients could help remove a primacy bias, see Nikishin et al. (2022).\n\nNikishin, Evgenii, et al. \"The primacy bias in deep reinforcement learning.\" International conference on machine learning. PMLR, 2022."}, {"review_id": "D7M72L6WzF", "reviewer": "Reviewer_xW74", "summary": "The paper introduces a novel algorithm for regret minimization in episodic Markov Decision Processes. The proposed algorithm, RandQL, achieves optimistic exploration without using bonuses, relying on learning rate randomization. The authors provide theoretical analysis of the algorithm's regret bound and demonstrate its effectiveness in experiments.", "questions": "1. If the learning rate randomization is to approximate the posterior distribution, how is it different from other ensemble methods like bootstrapped DQN[1], which also uses multiple Q values to estimate the posterior distribution?\n2. The proposed method does not necessarily need to be restricted in the tabular case, is it possible to extend it to more practical scenarios since its advantage also comes from computation?", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper presents a novel algorithm that achieves optimistic exploration with learning rate randomization.\n2. Both theoretical analysis of the algorithm and experimental results are provided with discussions to compare with baseline methods.", "weaknesses": "1. Lack of baseline comparison: using ensembles of Q values is not new, for example, bootstrapped DQN [1]. It would be an essential baseline method to show the potential difference in learning rate randomization compared with other ensemble methods.\n2. The experimental section would benefit from a more complex setting other than the grid world, for example, the chain environment in [1] which requires some “deep” exploration.\n\n[1] Deep Exploration via Bootstrapped DQN. Ian Osband, Charles Blundell, Alexander Pritzel, Benjamin Van Roy", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are very thankful to Reviewer xW74 for detailed reading and informative feedback. In the sequel we answer the particular questions raised in the review.\n\n- “Lack of baseline comparison: using ensembles of Q values is not new, for example, bootstrapped DQN [1]. It would be an essential baseline method to show the potential difference in learning rate randomization compared with other ensemble methods.”.\n\nThe main difference between our approach and the approach of bootstrap DQN lies in the assumptions. We provide theoretical guarantees for our method in the tabular and metric space setups. In contrast, providing guarantees for bootstrap DQN and other neural-network-based algorithms remains an open problem unless strong assumptions are imposed. The goals are also different in our work and the bootstrap DQN paper, where the authors aim to construct an efficient algorithm in the Deep RL setting. In contrast, our primary goal is to provide a theoretically grounded model-free version of the PSRL algorithm.\n\nWe agree that ensemble learning is not novel and do not claim it contributes to our work. However, additional sources of randomization are needed to apply this idea since more than the simple effect of different initializations is required, especially if one wants to deal with a stochastic environment. \n\nAdditionally, bootstrap DQN trains the Q-head of a neural network with dependent targets, which breaks the analogy with a usual posterior sampling algorithm where one needs to sample completely independent new heads at each episode. Our work validates that the dependencies between targets and different posterior samples do not break the theoretical efficiency.\n\nIn our algorithm, we use the ensemble learning idea as a  technique to provide high-probability optimism. In particular, learning rate randomization gives \"local\" optimism that is a positive probability to sample an upper-bound on V-value for a fixed state-action-step triple—then given \"local\" optimism, ensembling learning allows us to transmit it to \"global\" optimism that is indeed used in the proof of regret bound. Mathematically, this idea is described in the proof of Proposition 1 in Appendix D.3. Properties of Dirichlet distribution give \"local\" optimism in equation (7). However, \"global\" optimism requires taking a maximum over the ensemble.\n\nRegarding the experimental comparison, we do not provide a comparison with bootstrap DQN because we consider only algorithms with provable guarantees. Still, we compare with PSRL algorithm, the tabular inspiration of the bootstrap DQN.\n\n- “The experimental section would benefit from a more complex setting other than the grid world, for example, the chain environment in [1] which requires some “deep” exploration.”.\n\nWe will add experiments for the chain environment. In particular, this experiment also validates the good exploration properties of RandQL compared to OptQL.\n\n- “If the learning rate randomization is to approximate the posterior distribution, how is it different from other ensemble method?”\n\nTheoretical guarantees are the main difference between our and bootstrap DQN methods. Bootstrap DQN highly relies on the properties of different random neural network initializations that give enough randomness to emulate the posterior distribution. However, more than this idea is needed from a theoretical point of view, even in the simple setting of tabular RL. It thus requires additional randomization, for example, the presented learning rate randomization. Additionally, the initial theoretical justification of the bootstrap DQN assumes independence between different Q-networks. This independence does not hold in practice, whereas our algorithm carefully handles this critical issue.\n\n- “The proposed method does not necessarily need to be restricted in the tabular case, is it possible to extend it to more practical scenarios since its advantage also comes from computation?”\n\nIt is possible to extend our algorithm beyond the tabular setting by using a random learning rate of SGD during neural network training in the DQN-type algorithm. The variance of this random learning rate should decay over time to ensure that we will not leave a good policy in the end. Additionally, we note that using a random learning rate appeared in deep learning literature with another goal rather than exploration, see Biler et al. 2020. We leave the problem of a DQN extension of RandQL to future work.\n\nBlier, Léonard, Pierre Wolinski, and Yann Ollivier. \"Learning with random learning rates.\" Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2019, Würzburg, Germany, September 16–20, 2019, Proceedings, Part II. Springer International Publishing, 2020.\n"}, {"review_id": "Y9JovQK5EX", "reviewer": "Reviewer_4Am8", "summary": "This work aims to develop computationally efficient, posterior sampling-style, model-free RL algorithms. They propose a family of algorithms based on the idea of learning rate randomization, which they show are able to provably learn and mimic to some degree the updates of posterior sampling. In the tabular setting, they show that the regret of this approach scales with $O(\\sqrt{H^5 SAT})$. They also extend the approach to RL in metric spaces, and show that their algorithm is provably efficient in that setting as well.", "questions": "Please clarify the contributions of this paper and why the algorithm of (Russo, 2019) does not satisfy the desiderate (in the tabular setting).", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "1. The algorithmic technique (exploration via learning rate randomization) presented here is interesting and to my knowledge novel. A common technique in RL is to add bonuses to the value function estimates to induce exploration via optimism. A related approach inspired from posterior sampling is to randomize the rewards in training, which has been shown to induce exploration and is provably efficient. Rather than adding bonuses or randomizing rewards, this paper instead induces exploration by updating the $Q$-function at each step with a random learning rate with carefully chosen distribution. They show that the resulting $Q$ function has a form very similar to that which would be generated by posterior sampling, and that that the algorithm is provably efficient. \n2. To my knowledge there are no existing works which propose provably efficient posterior sampling-inspired algorithms for RL in metric spaces, so the results in this setting are the first of their kind.\n3. The technique of learning rate randomization proposed here seems like it could be implemented in a straightforward way in deep RL algorithms, and may therefore have practical implications (though this is not explored in this work---some experiments are given, but these are restricted to gridworld environments).\n4. Experimental results demonstrate that on gridworld MDPs the approach proposed here performs better than OptQL (but worse than model-based algorithms).", "weaknesses": "1. This work is motivated by noting that “a provably tractable model-free posterior sampling algorithm has remained a challenge”. However, I’m not entirely sure this is correct. The RLSVI algorithm of (Russo, 2019) is inspired by posterior sampling, is computationally efficient, and is model free (in that it never requires computing or storing an estimate of the transition dynamics). While I do think the algorithmic techniques are interesting and the extension to the metric RL setting is novel, it’s not clear to me what the contributions of this paper are beyond that.\n2. The guarantee obtained in the metric RL setting does not scale with the zooming dimension, but instead scales with the ambient dimension. While this is optimal in the worst-case, in general one would hope to see a scaling in the zooming dimension for learning in metric spaces (as is shown, for example, in (Sinclair et al., 2022)). \n3. Furthermore, in the metric RL setting the proposed approach is not in general computationally efficient (as the computational complexity scales with $N_\\epsilon$, which in general could be exponentially large in the dimension). In contrast, the metric RL algorithm of (Sinclair et al., 2022) is computationally efficient. Both this and the previous issue arise because the algorithm applies a fixed rather than adaptive discretization technique.\n4. The assumptions required in the metric RL setting (in particular Assumptions 2 and 3) are somewhat stronger than what has been required in previous work on metric RL (Sinclair et al., 2022). I do not believe the extra assumptions are that restrictive, but some more discussion on them would be helpful.\n5. It would greatly strengthen this paper if experiments could be provided using learning rate randomization on deep RL benchmarks, and illustrating that this approach is able to effectively induce exploration in such settings.\n6. It would also be helpful to include the algorithm of (Russo, 2019) in the experimental evaluation of Section 5.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are very thankful to Reviewer 4Am8 for detailed reading and informative feedback. In the sequel we answer the questions raised in the review.\n\n- \"This work is motivated by noting that “a provably tractable model-free posterior sampling algorithm has remained a challenge”. However, I’m not entirely sure this is correct\", \"Please clarify the contributions of this paper and why the algorithm of (Russo, 2019) does not satisfy the desiderate (in the tabular setting).\"\n\nRegarding this question, we refer to the separate comment submitted to all reviewers.\n\n- “Scaling with a zooming dimension instead of a covering dimension”.\n\nWe have discussed the instance-dependent regret bounds scaling with a zooming dimension in the remark after Theorem 2 called “Adaptive discretization” and refer further to Appendix F.\n\nThe presented adaptive version of the algorithms is used in the experiments for metric spaces, and we have provided a regret analysis for this algorithm that scales in zooming dimension instead of covering dimension, see Theorem 3. The proof is only sketched since it mostly reuses the same arguments as in Sinclair et al. 2022 given that optimism and upper bound on the over-estimation error are in the same form.\n\nWe provide a detailed analysis only for a net-based algorithm because it is much simpler and shows all theoretical insights and differences with tabular settings.\n\n- “Computational efficiency of a net-based algorithm”.\n\nWe totally agree and also think that the worst-case algorithm that uses epsilon-nets could be prohibitively expensive from the point of view of both time and space complexity, and it is exactly the reason why we use an adaptive algorithm in the experiments.\n\n- “Assumption 2 and 3 are strong”.\n\nThank you for your assumption question; we will discuss Assumptions 2 and 3.\n\nAbout Assumption 2: this assumption holds for any well-behaved transition kernel over metric spaces, as shown in Theorem 1.3.6 by Douc et al. (2018), so it could be taken for free.\n\nRegarding Assumption 3, this assumption is stronger than the one required in the previous work by Sinclair et al. (2022); see Lemma 1 and Lemma 2. However, in compact metric spaces, we are unaware of any MDPs with Lipschitz continuous transition kernel that fails to satisfy Assumption 3.\n\n- It would greatly strengthen this paper if experiments could be provided using learning rate randomization on deep RL benchmarks, and illustrating that this approach is able to effectively induce exploration in such settings.\n\nProviding experiments on deep RL experiments could be a precious contribution. However, due to a lack of time, we leave the extension of our algorithm to the DQN setting for future work.\nAdditionally, let us mention that using a random learning rate appeared in deep learning literature with another goal rather than exploration, see Biler et al. 2020. \n\nBlier, Léonard, Pierre Wolinski, and Yann Ollivier. \"Learning with random learning rates.\" Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2019, Würzburg, Germany, September 16–20, 2019, Proceedings, Part II. Springer International Publishing, 2020.\n\n- “Empirical comparison with RLSVI”\n\nWe added a numerical comparison with the RLSVI algorithm by Russo (2019), see new figures in the general comment.\n"}, {"review_id": "b9qG45JP1S", "reviewer": "Reviewer_XC7g", "summary": "The paper introduces Randomized Q-learning (RandQL), a novel model-free algorithm for regret minimization in episodic MDPs. Leveraging a new idea of learning rate randomization, two respect algorithms are proposed for tabular and non-tabular metric space settings, achieving near-optimal regret upper bound. Proof-of-concept experiments are conducted.", "questions": "While most questions are shown in the \"weaknesses\" section, there are a few additional smaller questions:\n\n- In Line 141, shouldn't $\\overline{V}_h^{n+1}$ be computed from $\\overline{Q}^{n+1}_h$? Is it a typo?\n\n- What is the intuition of setting $r_0=2$ (e.g., in line 210)?", "limitations": "No negative societal impact was identified.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- The concept of learning rate randomization is very interesting, which enables the algorithm to explore without bonuses. \n\n- Near-optimal regret upper bounds are obtained, showing the efficiency of proposed algorithms.\n\n- Empirical results show that the algorithm outperforms the existing model-free approach (OptQL) and support their theoretical results.", "weaknesses": "- The experiments are too simple. Although the theoretical contribution of this paper has outweighed the limited empirical verification and made this paper relatively solid, conducting additional experiments on more complex environments would be advantageous and could further enhance the overall research.\n\n- I was unable to find an explicit explanation of the intuition of the value of $J$. It would be helpful to understand the implications if $J$ is too small or too large. I noticed that you set $J$ to be of logarithmic order, but a high-level explanation of this choice would be beneficial.\n\n- The policy $Q$ value $\\overline{Q}_h(s_h,a_h)$ is computed by taking the maximum of $J$ temporary $Q$-values. Will it incur a large estimation error? Recall that in double Q-learning, one common trick is to take a minimum of two networks in order to reduce the estimation error. Although I am not sure how this issue affects your theoretical analysis, this seems a real problem in practice.\n\n- The Net-Staged-RandQL replies on the exact computation of covering, which may be considered a drawback. However, it is worth noting that many existing works also depend on this computation, suggesting that it could be an acceptable requirement.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are very thankful to Reviewer  XC7g for detailed reading and informative feedback. Additionally, we are very thankful for pointing out the misprints. In the sequel, we address the particular questions raised in the review.\n\n- “Intuition of the value of J”.\n\nThis value of J is used in the proof to provide \"global\" optimism in the sense that $\\bar{Q}^t_h(s,a) >= Q^*_h(s,a)$ for any $s,a,h$ given \"local\" optimism for any particular state-action pair. The learning rate randomization technique gives precisely the required \"local\" optimism.\n\nThis idea mathematically is described in the proof of Proposition 1 in Appendix D.3: by the properties of the Dirichlet distribution, we can obtain \"local\" optimism with positive probability described in Equation (7). Then we use ensembling to show that this \"local\" optimism holds for all s,a,h with high probability, ensuring \"global\" optimism by induction. The chosen value of $J$ is minimal to ensure global optimism given the local one. It could be possible to have global optimism even with $ J=1 $, but it requires a non-trivial extension of the Dirichlet anti-concentration results, which we leave for future work.\n\n- “Taking maximum over an ensemble leads to overestimation”.\n\nAs usual in optimistic algorithms, the maximum allows us to balance between optimism for ensuring exploration and over-estimation error. In other words, the agent should overestimate, but not too much. \nRegarding comparison with Double Q-learning, the problem of overestimation due to error accumulation becomes very important in the functional approximation setup since it is uncontrollable and could lead to extensive exploration even in environments where it is not needed. In the tabular and metric setting, controlling and reducing over-estimation error is possible due to the proper choice of learning rates. A similar idea of using ensembles to induce additional overestimation was successfully used in BayesUCBDQN algorithm, see Tiapkin et al. (2022).\n\nTiapkin, Daniil, et al. \"From Dirichlet to Rubin: Optimistic exploration in RL without bonuses.\" International Conference on Machine Learning. PMLR, 2022.\n\n- “Exact computation of coverings”.\n\nWe want to stress that we study Net-Staged-RandQL because it is the simplest algorithm for metric spaces, allowing us to obtain (in general) optimal regret bounds in the metric space setting. Additionally, even for this algorithm, it is possible to use not exact covering but its greedy approximation, see Song and Sun [2019]. The price for this inexactness will not change the asymptotic regret.\n\nAdditionally, in Appendix F, we provided the main part of the proof for an adaptive algorithm that does not rely so hard on computation of covering for all space but only for regions of interest.\n\n- “Intuition under setting $r_0 = 2$”.\n\nInstead of 2, one could use any number strictly greater than one at the price of increasing a constant in the definition of a number of prior samples $n_0$. This additional reward gives a large enough prior for the maximum value till enough data is collected. In particular, this reward ensures that even if we collected 0 value many times, the corresponding state-action pair is still considered good enough. This helps to make exploration in the first stages when it is crucial.\n"}]

Author rebuttal:
## Model-based vs model-free
First, we would like to stress that in the tabular setting, according to the Definition 1 by Jin et al. 2018, RLSVI is a model-based algorithm since it needs a space  complexity of order $O(S^2AH)$ independently of $T$, large enough to store an estimate of the MDP (empirical mean reward and empirical transition probabilities). In more general settings, RLSVI algorithms could be implemented in a “model-free fashion” by recording all the observed transitions. However, this implementation approach comes with a trade-off: it requires storing all $T$ transitions and solving a regression problem with sample size $O(T)$. Moreover, one can also argue that these stored transitions form a non-parametric model of the environment, classifying RLSVI as a model-based algorithm.

Similarly, the LSVI-PHE algorithm by Ishfaq et al. (2021) has a memory complexity of order $O(T)$ (to perform linear regressions with different targets at episode $k$, they need to keep in memory all previous transitions) even when the state space is small. In particular, it makes this algorithm model-based in a tabular setting in terms of the required memory complexity if $T$ is large enough (see Definition 1 by Jin et al. 2018). In contrast, the computational complexity of our algorithm doesn’t depend on $T$. To the best of our knowledge, there exists no RLSVI type algorithm avoiding this issue.

## Differences between RLSVI and RandQL

The primary ideological distinction between RLSVI-type algorithms and RandQL lies in the Bayesian model they adopt. RLSVI seeks to construct a Gaussian posterior for the Q-value, whereas RandQL, as a PSRL-based algorithm, approximates the Dirichlet posterior on the transitions in a model free way. Specifically, the Dirichlet Bayesian model on transition probabilities induces a Dirichlet process posterior for the $Q$ value, see Remark 1 in Appendix E.4. This leads to a significantly more expressive distribution family than the Gaussian model employed by RLSVI.

In particular, this expressive representation leads to one interesting feature of RandQL that is not present in RLSVI: the variance adaptivity. In particular, if we consider the expression in Equation 1, the direct computation of the variance of this estimate with respect to random Dirichlet weights yields the empirical variance of the V-value up to a bias that comes from the prior. 

To illustrate the importance of this point, it is worth noting that Xiong et al. (2022) needed to adjust by hand the variance of the Gaussian noise based on the variance of a $V$-value estimate like for the case  of Bernstein-type  bonuses. In contrast, the noise generated by our algorithm automatically adjusts to the variance of the V-values. A potential improvement in the regret bound resulting from this variance adaptivity  is a promising research direction.

As  to the differences between sample complexity and computational costs, the regret bound of RandQL algorithm is of order $\widetilde{O}(\sqrt{H^5 SAT})$ whereas a basic RLSVI algorithm, without a single seed randomization technique and variance adjustment (Xiong, 2022),  has regret of order $\widetilde{O}(\sqrt{H^4 S^2 A T})$ (Agrawal et al, 2021).

From the point of view of computational complexity, RandQL has $\widetilde{O}(H)$ per-episode time complexity and $\widetilde{O}(HSA)$ space complexity that outperforms $O(HS^2A)$ time complexity and $O(HS^2A)$ space complexity of  RLSVI-type algorithms.

## Additional figures

We attach a PDF with all additional figures, that includes 
- Additional experiments on Chain environment  by Osband et al. (2016) with $L = 15$ states and 2 actions (left or right). The horizon is equal to $30$, the probability of moving into wrong direction is equal to 0.1. The agent starts in the leftmost state with reward 0.05, also the largest reward is equal to 1 is the rightmost state.
- Also we add comparison with RLSVI algorithm in tabular experiment with a grid-world environment.

### References

Russo, Daniel. "Worst-case regret bounds for exploration via randomized value functions." Advances in Neural Information Processing Systems 32 (2019).

Xiong, Zhihan, et al. "Near-Optimal Randomized Exploration for Tabular Markov Decision Processes." Advances in Neural Information Processing Systems 35 (2022): 6358-6371.

Jin, Chi, et al. "Is Q-learning provably efficient?." Advances in neural information processing systems 31 (2018).

Ishfaq, Haque, et al. "Randomized exploration in reinforcement learning with general value function approximation." International Conference on Machine Learning. PMLR, 2021.

Agrawal, Priyank, Jinglin Chen, and Nan Jiang. "Improved worst-case regret bounds for randomized least-squares value iteration." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 8. 2021.

Osband, Ian, et al. "Deep exploration via bootstrapped DQN." Advances in neural information processing systems 29 (2016).



Meta-review: The paper introduces an intriguing randomization strategy for the learning rate, aimed at enhancing the efficiency of model-free posterior sampling in Reinforcement Learning (RL). Both theoretical and experimental evidence are provided. All reviewers have expressed a favorable view of the paper, and the authors have satisfactorily addressed questions raised during the rebuttal period.
Decision: Accept (poster)