Model-Free Active Exploration in Reinforcement Learning
Authors: Alessio Russo
Alexandre Proutiere
Venue: NeurIPS 2023 poster (2023)
Keywords: reinforcement learning; best policy identification; model free; exploration; sample complexity

Abstract: We study the problem of exploration in Reinforcement Learning and present a novel model-free solution. We adopt an information-theoretical viewpoint and start from the  instance-specific lower bound of the number of samples that have to be collected to identify a nearly-optimal policy. Deriving this lower bound along with the optimal exploration strategy entails solving an intricate optimization problem and requires a model of the system. In turn, most existing sample optimal exploration algorithms rely on estimating the model. We derive an approximation of the instance-specific lower bound that only involves quantities that can be inferred using model-free approaches. Leveraging this approximation, we devise an ensemble-based model-free exploration strategy  applicable to both tabular and continuous Markov decision processes. Numerical results demonstrate that our strategy is able to identify efficient policies faster than state-of-the-art exploration approaches.

Model-Free Active Exploration in Reinforcement Learning
Alessio Russo
Alexandre Proutiere
Division of Decision and Control Systems KTH Royal Institute of Technology Stockholm, SE
Division of Decision and Control Systems KTH Royal Institute of Technology Stockholm, SE
Abstract
We study the problem of exploration in Reinforcement Learning and present a novel model-free solution. We adopt information-theoreticc viewpoint and start from the instance-specific lower bound of the number of samples that have be collected to identify nearly-optimal policy. Deriving this lower bound along with the optimal exploration strategy entails solving an intricate optimization problem and requires model of the system. In turn, most existing sample optimal exploration algorithms rely on estimating the model. We derive an approximation of the restance-speciffe lower bound that only involves quantities that can be inferred using model-free approaches. Leveraging this approximation, we devise ensemble-based model-free exploration strategy applicable to both tabular and continuous Markov decision processes. Numerical results demonstrate that our strategy is able identify efficient policies faster than state-of-thh-an art exploration approaches.
Introduction
Efficient exploration remains a major challenge for reinforcement learning (RI.) algorithms. Over the last two decades, several exploration strategies have been proposed in the literature, often designed with the aim of minimizing regret. These include model- -bsed approaches such as Posterior Sampling for RL (PSRL) and Upper Confidence Bounds for RL 4 22 (UCCRL) along with model-free
UCB-like methods [19] [66]. Regret minimization is a relevant objective when one cares about the rewards accumulated during the learning phase. Nevertheless, an often more important objective is to devise strategies that explore the environment so as to learn efficient policies using the fewest number of samples [16]. Such an objective, referred as Best Policy Identification (BPI), has been investigated in simplistic Multi-Arees Bandit problems [66] 21 and more recently in tabular MDPs For these problems, tight specifc sample complexity lower bounds are known, as well as model-based based algorithms approaching these limits. However, model-based approaches may be computationally expensive or infeasible to obtain. In this paper, we investigate whether we can adapt the design of these algorithms that they become model-free and hence more practical.
28 29
approach, and design our algorithms starting from an instance-specific lower bound on the sample complexity of learning nearly-optimal policy in Markov decision process (MDP). This lower bound is the value of an optimization problem. referred to as the lower bound problem, whose solution dictates the optimal exploration strategy in an environment. Algorithms designed on this restance-specife lower bound, rather than minimax bounds, result in truly adaptive methods, capable of tailoring their exploration strategy according to the specific MDP's learning difficulty. Our method estimates the solution the lower bound problem and employs it as our exploration strategy. However, we face two major challenges: (1) the
Inspired by 28 29 we adopt an information-theoretee
Code
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

lower bound problem is non-convex and often intractable; (2) this lower bound problem depends on the initially unknown MDP. In 29 the authors propose MDP-NAS model-based algorithm that explores according to the estimated MDP. They convexify the lower bound problem and explore according to the solution of the resulting simplified problem. However, this latter problem still has a complicated dependency on the MDP. Moreover, extending MDP-NAS to large MDPs is challenging since it requires an estimate of the model, and the capability to perform policy iteration. Additionally, MDP- ADP-NAS employs a forced exploration technique to ensure that the parametric uncertainty (the uncertainty about the true underlying MDP) diminishes over time - method, as we argue later, that we believe not to be efficient in handling this uncertainty.
We propose an alternative way to approximate the lower bound problem, so that its solution can be learnt via model-free approach. This solution depends only on the Q-function and the variance of the value function. Both quantities can advantageously be inferred using classical stochastic approximation methods. To handle the parametric uncertainty, we propose an ensemble-han based method using a bootstrapping technique. This technique inspired by posterior sampling and allows us to quantify the uncertainty when estimating the Q-function and the variance of the value function.
Our contributions are as follows: (1) we shed light on the role of the instance-specific quantities needed to drive exploration in uncertain MDPs; (2) we derive an alternate upper bound of the lower bound problem that turn can be approximated using quantities that can be learned in a model-free manner. We then evaluate the quality of this approximation on various environments: (i) a random MDP. (ii) the Riverswim environment 47 and (iii) the Forked Riverswim environment (a novel environment with high sample complexity); (3) based on this approximation, we present Model Free Best Policy Identification (MF-BPI), a model-free exploration algorithm for tabular and continuous MDPs. For the tabular MDPs, we test the performance of MF-BPI on the Riverswim and the Forked PSRL [6), and MDP-NAS 29). For continuous state-spaces, we compare our algorithm to IDS 33 and BSP [39 (Boostrapped DQN with randomized prior value functions) and assess their performance on hard-exploration problems from the DeepMind BSuite [41] (the DeepSea and the Cartpole swingup problems).
Riverswim environments, and compare it to that of Q-UCB 19 56
2 Related Work
The body of work related to exploration methods in RL problems is vast, and we mainly focus on online discounted MDPs (for the generative setting, refer to the analysis presented in [17 28 Exploration strategies RL often draw inspiration from the approaches used in multi aamti bandit
problems [26 49]. including c-greedy exploration, Boltzmann exploration [57 49 26 I.. or more
advanced procedures, such as Upper-Confidence Bounds (UCB) methods [2] 3 26 or Bayesian procedures [52 58 14
We first discuss tabular MDPs, and then extend the discussion to the case of RL with function approximation.
44).
Exploration in tabular MDPs. Numerous algorithms have been proposed with the aim of matching the PAC sample complexity minimax lower bound i [S
25 In the design of these
algorithms, model-free approaches typically rely on UCB- exploration 2 126. whereas model- based methods leverage estimates of the MDP to drive the exploration. Some well-known model-free
algorithms are MEDIAN-PAC [42]. DELAYED Q-LEARNING [48] and Q-UCB (56) 19]. Some
notable model-based algorithms include: DEL (34). an algorithm that achieves asymptotically
optimal dnseanne regret; UCRL 25 algorithm that uses extended aalue-iteration to
compute an optimistic MDP; PSRL (36], that uses posterior sampling to sample an MDP. Other
algorithms include MBIE 47 E3 (22]. R-MAX 20), and MORMAX [50). Most of existing algorithms are designed towards regret minimization. Recently, however, there has been a growing
interest towards exploration strategies with minimal sample complexity, see e.g. [60] 28] In 28 29]
the authors showed that computing an exploration strategy with minimal sample complexity requires to solve a non-convex problem. To overcome this challenge, they derived a tractable approximation of the lower bound problem, whose solution provides an efficient exploration policy under the generative model (28 and the forward model 229 This policy necessitates an estimate of the model, and includes forced exploration phase (an e-soft policy to guarantee that all state-action pairs are visited infinitely often). In [5T), the above procedure is extended to linear MDPs, but there again, computing an optimal exploration strategy remains challenging. On side note, in (55) the authors provide an

---

alternative bound in the tabular case for episodic MDPs, and later extend it to linear MDPs (54). The episodic setting further explored in [53] for deterministic MDPs.
Exploration in Deep Reinforcement Learning (DRL). Exploration methods in DRL environments face several challenges, related to the fact that the state-action spaces often continuous, and other issues related to training deep neural architectures [46]. The main issue in these large MDPs is that good exploration becomes extremely hard when either the reward is sparse/delayed or the observations contain distracting features [T 59] Numerous heuristics have been proposed to tackle these challenges, such as (1) adding an entropy term to the optimization problem encourage the policy to be more randomized [31 [8] or (2) injecting noise in the observations/parameeee [15] 43). More generally, exploration techniques generally fall into two categories: uncertainty- methods decouple the uncertainty quantifies the uncertainty in the parameters of the state-action value. This uncertainty vanishes as the agent explores and learns. The aleatoric uncertainty accounts for the inherent randomness of the environment and of the policy 132
based and perriniic-motiattiine based [59] 24]. Uncertainty-base
into parametric and aleatoric uncertainty. Parametric uncertainty [4
32
23 59
23 [5]] Various methods have been proposed to address the parametric
uncertainty, including UCB-like mechanisms [ [9], or TS-like (Thompson Sampling) techniques
38 36 35
37
40 However, computing a posterior of the Q-values is a difficult task. For
instance, Bayesian DQN [5] extends Randomized Least-Squares Value Iteration (RLSVI) (38 by considering the features prior to the output layer of the deep-Q network as a fixed feature vector, in order to recast the problem as a linear MDP. Non-pan Von-parametric posterior sampling methods include
Bootstrapped DQN (and Bootstrapped DQN with prior functions) B7 39 40), which maintains several independent Q-value functions and randomly samples one of them to explore the environment. Bootstrapped DQN was extended in various ways by integrating other techniques 6 27]. For the sake of brevity, we refer the reader to the survey in (59) for an exhaustive list of algorithms. Most of these algorithms do not directly account for aleatoric uncertainty in the value function. This uncertainty is usually estimated using methods like Distributional RL [8] 13
30). Well-known exploration methods that account for both aleatoric and epistemic uncertainties include Double Uncertain Value Network (DUVN) (32) and Information Directed Sampling (IDS) [23 33 The former uses Bayesian dropout to measure the epistemic uncertainty, and the latter uses distributional RL [8] to estimate the variance of the returns. In addition, IDS uses bootstrapped DQN to estimate the parametric uncertainty in the form of a bound on the estimate of the suboptimality gaps. These uncertainties are then combined to compute an exploration strategy. Similarly, in [12. the authors propose UA-DQN, an approach that uses QR-DQN [3] to learn the parametric and aleatoric uncertainties from the quantile networks. Lastly, we refer the reader to (59 45 7 for the class of motivatiooovviii-bnbbba based methods.
3 Preliminaries
Markov Decision Process. We consider an infinite-horizon discounted Markov Decision Process (MDP), defined by the tuple o = (S, A, P. 7oPo). S is the state space, A is the action space, P:Sx x A + ASS) is the distribution over the next state given a state-action pair (s, a), q : S x A + A(OO, IJ) is the distribution of the collected reward (with support in [0, I). 7 E [0, 1) is the discount factor and po is the distribution over the initial state.
Let T : S + (AA) be a stationary Markovian policy that maps a state to a distribution over actions, and denote by r(s,a) a) = Ex-g(-ls.a)) [r] the average reward collected when action a is chosen in state We denote by (s) B E'zo?"r(su ae |so = s) the discounted value of policy т. We denote by n¹ an optimal stationary policy: for any S, (s) E arg max, V'((s) and define (*) = max, (s). For the sake of simplicity, we assume that the MDP has a unique optimal policy (we extend our results to more general MDPs in the appendix). We further define (Ø) = { -|V* VV* ol < <e), the set of c-optimal policies in ø for 2 0. Finally, to avoid technicalities, we assume (as in (29) that the MDP & is communicating (that is, for every pair of states (s, 8'), there exists deterministic policy π such that state s' is accessible from state s using T)).
We denote by (* a) == r(x, a) + +>
[ (s') the Q-function of x in state (s, We also define the sub-optimality gap of action a in state & to be A(s, a) == Q* x (x)) Q'(s,, a). where Q" is the Q-uuctioon of T²' and let Amin = min (s) A a) be the minimum gap in ø. For some policy n, we define Var,a [V* == Var,~ (s')] ]]) to be the variance of the value function V in the next state after taking action a in state s. More generally, we define [V[ =
3

---

Bx-P()aa)) (V*('') - V* (
to be the 2 -t moment of the value function in the
next state after taking action a in state s. We also let sa [V*] the span of & under æ, i.e., the maximum deviation from the mean of the next state value after taking action a in state 8.
|| - P(-ss())
(V [VT]] be
Best policy identification and sample complexity lower bounds. The MDP Φ is initially unknown, and we are interested in the scenario where the agent interacts sequentially with Φ. In each round t E N, the agent selects an action at and observes the next state and the reward (8141, re): 86+1 ~ P(-]ae; (e) and r ~ q0-1118 |&,, (e). The objective of the agent is to learn policy in (T) (possibly x*) as fast as possible. This objective is often formalized in a PAC framework where the learner has to stop interacting with the MDP when she can output an e-optimal policy with probability at least 1- 8. In this formalism, the learner strategy consists of (i) a sampling rule or exploration strategy; (ii) a stopping time r; (iii) estimated optimal policy ft. The strategy is called (c, - it stops almost surely, and [ E I [6)] 2 1 8. Interestingly, one may derive instance -spacccc lower bounds of the sample complexity [r]r] of any (c, 6)-PAC algorithm [8 29), which involves computing an optimal allocation vector Wopt E A(S x A) (where ASS x A) is the set of distributions over S x A) that specifies the proportion of times an agent needs sample each pair (s, a) confidently identify the optimal policy:
Es [
liminf 6-+0
2 To (Wope) where Te(w)=' = inf (e [KL ((, (8), (EA
(I)
kl 1 8)
and Wopt arg (n Te(w)-1 Here, (d) is the set of confusing MDPs to such that the e-optimal policies of 6 are not e-optimal in tb, i.c., (o) == { < b. (1) n (b) =0. 0}.
In this definition, if the next state and reward distributions under 1 are P'(s, a) and g' a).
write
ó < di if for all (s, a) the distributions of the next state and of the rewards satisfy P(s, a) < as) and q(s, a) < (sss, (s, a). We further let KL (s, a) (L(P(s, a), P'(s, a)) KL( a). (s). ((0) is the set of possible allocations; in the generative case it is A(S x A), while with navigation constraints we have 12())= = {w E A(S x A) : w(s)
Es -. P(s s a' (w)ssss ,d)),,
(')].. Vs E S). with
w(s) = En wss Finally, kl(a, b) is the KL--divegeecce between two Bernoulli distributions of means and b.
4 Towards Efficient Exploration Allocations
We aim to extend previous studies on best policy identification to online model-free exploration. In this section, we derive approximation to the bound proposed in (28), involving quantities learnable via stochastic approximation, thereby cnabling the use of model-free approaches.
The optimization problem [ leading to instance-specific sample complexity lower bounds has an important interpretation 28 29). An allocation Wopt corresponds to an exploration strategy with minimal sample complexity. To devise an efficient exploration strategy, one could then think of estimating the MDP o, and solving [ for this estimated MDP to get an approximation of Wopt- There are two important challenges towards applying this approach:
(i) Estimating the model can be difficult, especially for MDPs with large state and action spaces, and arguably. a model-free method would be preferable.
(ii) The lower bound problem [ is, in general, non-convex 28 29
simple way circumvent issue (ii) involves deriving an upper bound of the value of the sample complexity lower bound problem (I). Specifically, one may derive an upper bound U (w(w) of T (w) by convexifying the corresponding optimization problem. The exploration strategy can then be the wt that achieves the infimum of U U(w). This approach ensures that we identify an approximately optimal policy, at the cost of wvrrexpporing at a rate corresponding to the gap U (w=) T. (Wopt). Note that using a lower bound of Te (w) would not guarantee the identification of an optimal policy, since we would explore "less" than required. The aforementioned approach was already used in [8 where the authors derive an explicit upper bound (n(w) of To(w). We also apply it, but derive an upper bound such that implementing the corresponding allocation wt can be done in a model-free manner (hence solving the first issue (i)).

---

4.1 Upper bounds on (w)
The next theorem presents the upper bound derived in 22
Theorem 4.1 ((8)). Consider communicating MDP o with unique optimal policy x². For all
vectors E AS X A),
= max Ho(s,a) (1,0) wss.a) + max
H
To(w)= & Uo(w)=
(2)
(s))
with
Ho(s,a)= A(s,a}² + max
2
16 Var A(8,0)2
6MD
A(a,a)
H
A (1 (1-7)² + min
A (1-7))
27
max
16 max, Var (ulV" A2 mnn
maxx MD "n (V) A 473 (1-7)//3
In the upper bound presented in this theorem, the following quantities characterize the hardness of learning the optimal policy: A(s, a) represents the difficulty of learning that in state action is sub-optimal: the variance Var.a measures the aleatoric uncertainty future state values; and the span MD,,.VV [V*] of the optimal value function can be seen as another measure of alcatoric uncertainty, large whenever there is significant variability the value for the possible next states.
Estimating the span MD,a [V], in an online setting, challenging task for large MDPs. Our objective is to derive alternative upper bound that, in turn, be approximated using quantities that can be learned in a model-free manner. We observe that the variance of the value function, and more generally its moments sa [V+]2 for 2 (see Appendix C), are smaller than the span. By refining the proof techniques used in (28). we derive the following alternative upper bound.
Theorem 4.2. Let 2 0 and let k(s, a) = arg suPkeN M [V=]2** (for brevity, we write is instead of k(s, ((s,a)). a)). Then, Vu A(S A), we have (w) I (Ww), with
+ 8+* [1 w(s a)
C(s)(1 +7)²
U(w)= = max saatt' (s)
+ max
(3)
w(s T' (f))
where C(s') max (4, 24 M (st) [vpptt and is the golden ratio.
We can observe that in the worst case, the upper bound U(w") of the sample complexity lower bound, with w* = arg inf (w), scales as O |5|A max, MD..rtco/VTP Since MD+o[V') [V*] I (1 - 7)-
(1-7))
|S||A| then U(w*) scales most O 22 (1- However, the following questions arise: (1) Can
select a single value that provides a good approximation across all states and actions? (2) How
much does this bound improve that of Theorem 4 As illustrate in the example presented in the next subsection, we believe that actually selecting A = for all states and actions leads to sufficiently good results. With this choice, we obtain the following approximation:
(2 + 8,p² Var [V*] ((s,a)) (s)
C'(s') + 7)
Ui Ui(w)=
max
max w(s', T (T))) 0) ).
(4)
8,a95i" (8)
where C" C"(s') max (4, 26 V= U1 (w) resembles the term in Theorem 4.1 (note that do not know whether Uj is valid upper bound for T:). For the second question, our numerical experiments (presented below) suggest that U (w) is a tighter upper bound than (www).
4.2 Example on Tabular MDPs
In Figure I compare the characteristic time upper bounds obtained in the previous subsection. These upper bounds correspond to the allocations w*, wß. and w/ obtained by minimizing, over ASS A (ww), Vo(w), and (w),, respectively. We evaluated these characteristic times on various MDPs: (1) random MDP (see Sec. A in the appendix); (2) the RiverSwim environment
Results similar when account for the navigation constraints. We omit these results for simplicity.
5

---

RandomMDD
Riverswim
Forked Riverswim
10
Characteristio Time
1017
10a1
x
U(wo)
x
((wi)
1014
10tb
((w
10
10a
Uo(w))
104
10"1
109
5
10
15
20
5
10
15
20
5
7 11
15
21
[S]
|S]
[5]
Comparison of the upper bounds (2) and (3) for different sizes of S and y = 0.95. We evaluated different allocations using Un(w) and U' (w)). The allocations are: wh (the optimal allocation
Figure 1:
(2) w (the optimal allocation (3) and wi (the optimal allocation in (4) by setting k unitormly across states and actions). For the random MDP we show the median value across 30 runs.
47 (3) the Forked RiverSwim, a novel environment where the agent needs to constantly explore two different states learn the optimal policy (compared to the RiverSwim environment, the sample complexity is higher; refer to Appendix A for complete description).
We note that across all plots, the optimal allocation wi has a quite large characteristie time (black cross). Instead, the optimal allocation w" (blue circle) computed using our new upper bound (3) achieves a lower characteristic time. When we evaluate w on the new bound (orange star), we observe similar characteristic times.
Finally, to verify that can indeed choose k = 1 uniformly across states and actions, evaluated the characteristic time w/ computed using 4 (green triangle). Our results indicate that the perfor- mance is not different from those obtained with w*, suggesting that the quantities of interest (gaps and variances) are enough to learn an efficient exploration allocation. We investigate the choice in more detail in Appendix A.
Model-Free Active Exploration Algorithms
In this section present MF-BPI, model-free exploration algorithm that leverages the optimal allocations obtained through the previously derived upper bound of the sample complexity lower bound. We first present an upper bound (ww) of (w)), so that it is possible to derive a closed form solution of the optimal allocation (an idea previously proposed in (28)).
Proposition 5.1. Assume that à has unique optimal policy x². For all w E A(S x A), we have:
S ((w): := max H(s,a) 2,0 (8) w(s ming w(s', n (s'))"
H
with H (s, a) = 2 - M vv and
Cls C(s"X(++)) The minimizer is = arg inf,, ((w)
[(a,0)²
A -77
satisfies (s. a) x H(s, a) for a # xs)) and äs
a (s x V HH H)s.0)/IS
otherwise.
In the MF-BPI algorithm, we estimate the gaps A(s, a) and MA V for a fixed small value of k (we later explain how to this model-free manner.) and compute the corresponding allocation wr. This allocation drives the exploration under MF-BPI. Using this design approach, we face two issues:
(1) Uniform l and regularization. is impractical to estimate M [V*] for multiple values of k. Instead, we fix small value of k (e.g., k = 1 or & = 2) for all state-action pairs (refer to the previous section for a discussion on this choice). Then, to avoid excessively small values of the gaps in the denominator, we regularize the allocation 5* by replacing, in the expression of H (s, a) (resp. Hmin), ( a) (resp. Amin) by (A(s, a) + (resp. (Amin + X)) for some À 0.
(2) Handling parametric uncertainty via bootstrapping. The quantities A(s,a) a) and M [V+] required compute W' remain unknown during training, and we adopt the Certainty Equivalence principle, substituting the current estimates of these quantities to compute the exploration strategy.

---

Algorithm Boostrapped MF-BPI (Boostrapped Model Free Best Policy Identification)
Require: Parameters (A, p); ensemble size B; learning rates {(r, 3.) Initialize Q1,b(s,)) (10 1/(1 (1-1)) and M1,(s,a) u( 1/ -))²1) for all (s, a)
S x A and E [B].
2: for = 0, 1, .......... do
3: Bootstrap a sample (Qc, MM) from the ensemble, and compute the allocation with using Proposition 5.1 Sample at ~ (s.. observe (re, 8t+1) ~ g(-) st. ar) @ P(-Ist; oz). B
4: for = l.b.......BB do
5: With probability p. using the experience (st, ar, rt. st+1), update Qe and Mc using Equations (5) and (6).
6: end for
7: end for
By doing SO, are inherently introducing parametric uncertainty into these terms that is not taken into account by the allocation Wt. To deal with this uncertainty, the traditional method, as used e.g. in [8 (2),, involves using e-soft exploration policies to guarantee that all state-action pairs are visited infinitely often. This ensures that the estimation errors vanish as time grows large. In practice, we find this type of forced exploration inefficient. In MF-BPI, opt for bootstrapping approach to manage parametric uncertainties, which can augment the traditional forced exploration step, leading more principled exploration.
5.1 Exploration in tabular MDPs.
The pseudo-code of MF-BPI for tabular MDPs is presented Algorithm [ In round I, MF- BPI explores the MDP using the allocation (t) estimating w To compute this allocation, we
use Proposition 5.1 and need (i) the sub-optimality gaps A(s, a), which can be easily derived from the Q-function; (ii) the 2 moment M [V*]. which can always be learnt by means of stochastic approximation. fact, for any Markovian policy æ and pair (s, a) we have M [Vg] =
yau Eyr e. 1dT (s, a, s')²*,, where (*s a, 8') = r(s, a) + +)Baaraa(le) (Q
(8',''' a')) -"" Q" (s. is
variant of the TD-error. MF-BPI then uses an asynchronous two-timescale stochastic approximation algorithm to learn Q" and [V*,
Qu+1 ut) Qr(s, at) ) an(se, at) (re + max (+(8411, Q1((),
(5)
M141 04) = Me(se, 04) (s 0z) (185/7)2* Me(st,
a) 0z), and ((ar, B:) 12) are learning rates satisfying Ex a) Ecz0 () co, (a, Br(s, a)3) S co, and (x(s.)) 0.
where 8/ r max,
Bi(s,a)
MF-BPI uses bootstrapping to handle parametric uncertainty. We maintain ensemble of (Q, M))valuess with B members, from which we sample (Q., Mc) time This sample is generated by sampling a uniform random variable & ~ L4([0, 1]) and, for each (s,a) set Qs(s.a) Quantile, (Qr, (s,a),.. a), (t, (assuming linear interpolation). This method akin to sampling from the parametric uncertainty distribution (we perform the same opera- tion also to compute M.). This sample is used to compute the allocation w(t)) using Propo- sition 5.1 by setting a)( = max, Qr(s, a') Q((s,a) a), TT()) = arg max, Qe(s, a) and Amin, ming Ar(s, a). Note that, the allocation (!))) can be mixed with a uniform policy, to guarantee asymptotic convergence of the estimates. Upon observing an experience, with probability p. MF-BPI updates a member of the ensemble using this new experience. tunes the rate at which the models are updated, similar sampling with replacement, speeding up the learning process. Selecting high value for p compromises the estimation of the parametric uncertainty, whereas choosing low value may slow down the learning process.
Exploration without bootstrapping? To illustrate the need for our bootstrapping approach, we tried use the allocation ( mixed with a uniform allocation. Figure we show the results on Riverswim- like environments with 5 states. While forced exploration ensures infinite visits to all
7

---

Forced MF-BPI
Riverswim
ForkedRiverssie
Optimal
Optimal
1.0
0.5
0.0
0.0
10000
20000
30000
40000
50000
10000
20000
30000
40000
50000
Figure 2: Forced exploration example with 5 states. We explore according to w (8, a) (1 # (s),a) 4) E. 07 (=t,0)) + Et [A] mixing the estimate of the allocation D from Proposition 5.1 with uniform
policy, with 6 max(10-3 1/N)(s,)) where (s) indicates the number of times the agent visited state s up to time l. Shade indicates 95% confidence interval.
state-action pairs, this guarantee only holds asymptotically. As result, the allocation mainly focuses on the current MDP estimate, neglecting other plausible MDPs that could produce the same data. This makes the forced exploration approach too sluggish for effective convergence, suggesting its inadequacy for rapid policy learning. These results highlight the need to account for the uncertainty Q, M when computing the allocation.
5.2 Extension Deep Reinforcement Learning
To extend bootstrapped ME-BPI continuous MDPs, propose DBMF-BPI (see Algorithml 2 or Appendix B). DBMF-BBI BPI uses the mechanism of prior networks from BSP (bootstraapiin with additive prior) to account for uncertainty that does not originate from the observed data. As before, we keep an ensemble {Qo..... Qs of Q-values (with their target networks) and an en- semble (M,,.... Mra} } of M M-values, as well as their prior networks. We use the same procedure as the tabular case to compute (Qt: M,) at time 6, except that we sample { U([0, 1]) every T, x (1-7)-1 training steps (or the end of an episode) to make the training procedure more stable. The quantity Qe is used to compute पद (st) and (s a). We estimate Amin, via stochastic approx- imation, with the minimum gap from the last batch of transitions sampled from the replay buffer
2+8p2 (e. (A, (s.:))))
serving target. To derive the exploration strategy, compute Hj(st, a)
and H. 411+>)² max(1,11) 11 2 Malas. (++)))" (s+)))²=*) Next, we set the allocation w!') as follows:
[Ami A +A)=
w 1 (st, = (s if n. (st) and w (() V Eafpy(an) E. Hi a) otherwise.
Finally, obtain é2-soft exploration policy (st, by mixing ( (st, w (st, a) with a uniform distribution (using an exploration parameter (t).
Algorithm 2 DBMF-BI BPI (Deep Bootstrapped Model Free BPI)
Require: Paramcters (A, k); ensemble size B; exploration rate {ee h:; estimate Amino; mask probability p. I: Initialize replay buffer D, networks Qa, Mr, and targets Qøg for all b E [B).
2: for = 1,2.....
3: Sampling step.
Compute allocation (1) +- Conputekllocatioonsss. (Qu,, Mr, heje,, Amin.e: e. 7, X, k ft). Sample a, ~ (())) (s),.) and observe (re, 85+1) ~ q(11s,, a.) P(- at).
6: Add transition 2 = (st, ar, 8641) to the replay buffer D.
7: Training step. Sample batch B from 2, and with probability p add the 8t experience in B to sub-batch Ba. Vb E [B]. Update the (Q, -valuuss the 6th member in the ensemble using Ba: (Qo,, Qog, Mr, hej t Training([B.) Qo,, Qoj Mr he(p)) Update estimate Aminet1 <- EstimateMMinimuaan Amii, B, (eeps))
8:
10: end for

---

Numerical Results
We evaluate the performance of MF-BPI on benchmark problems and compare it against state-of-the art methods (details can be found in Appendix A).
Tabular MDPs. In the tabular case, compared various algorithms the Riverswim and Forked Riverswim environments. We evaluate MF-BPI with (1) bootstrapping and with (2) the forced exploration step using e-soft exploration policy, MDP-NAS [29]. PSRL [36] and Q-UCB [9 [6]. For MDP-NAS, the model of the MDP was initialized in an optimistic way (with additive smoothing).
V
In both environments, we varied the size of the state space. In Figure 3 we show
I|
performance measure for the estimated policy क after T |S| 10 steps with 7 0.99.
Results (the higher the better) indicate that bootstrapped MF-BPI can compete with model-based and model-free algorithms on hard-expler exploraxooo problems, without resorting to expensive model-based procedures. Details of the experiments, including the initialization of the algorithms, are provided in Appendix A.
Revesvim
Forloei
Agent
Bootstruped ME.-B BPI
Funaal MP-RPI QUBB
MDP-Na3
0:75
10
30
10 [S]
[8]
Figure 3: Evaluation of the estimated optimal policy क after T steps for MF-BPI, Q-UCB, MDP- NAS and PSRL. Results are averaged across 10 seeds and lines indicate 95% confidence intervals.
Deep RL. In environments with continuous state space, we compared DBMF-BP1 with BSP 40 (Bootstrapped DQN with randomized priors) and IDS [33] (Information-Diree Directed Sampling). We also evaluated DB MF-BPI against BSP2, variant of BSP that uses the same masking mechanism as DBMF-BPI for updating the ensemble. These methods were tested on challenging exploration problems from the Deep behavior suite 41 with varying levels of difficulty: (1) a stochastic version of DeepSea and (2) the Cartpole swingup problem. The DeepSea problem includes 5% probability of the agent slipping, i.e., that an incorrect action is executed, which increases the aleatoric variance.
The results for the Cartpole swingup problem are depicted Figure for various difficulty levels (see also Appendix A.5 for more details), demonstrating the ability of DBMF-BPI to quickly learn an efficient policy. While BSP generally performs well, there is notable difference in performance when compared to DBMF-BPL For fair comparison, we used the same network initialization across all methods, except for IDS. Untuned, IDS performed poorly; proper initialization improved its performance, but results remained unsatisfactory. In Figure 5 we present two exploration metrics
Cartpole swingup- difficulty & 10
Cartpole swingup episnde 200
Total uprighht time (steps]
Total upright. time [stepe]
DBMF-RPI
30000
60000
BSP
BSP2
20000
IDS
40000
10000
20000
150
200
Episode
Difficulty
Figure Cartpole swingup problem. On the left: total upright time at a difficulty level the right: total upright time after 200 episodes for different difficulties k. To observe positive reward,
the pole's angle must satisfy cos(0) > k/20, and the cart's position should satisfy | < k/20. Bars and shaded areas indicate 95% confidence intervals.

---

Frequency of visit (entropy)
Recent visit (entropy)
0.7
Normalized entropy
0.6
DBMF-BPI
0.5
BSP
BSP2
0.4
IDS
0
5000
10000
15000
20000
5000
10000
15000
20000
Timestep &
Timestep
Figure 5: Exploration Cartpole swingup for 5. On the left, we show the entropy of visitation frequency for the state space (æ, a; 0, 0) during training. On the right, we show a measure of the dispersion of the most recent visits; smaller values indicate that the agent is less explorative as t increases.
for difficulty 5. The frequency of visits measures the uniformity and dispersion of visits across the state space, while the second metric evaluates the recency of visits to different regions, capturing how frequently the methods keep visiting previously visited states (a smaller value indicates that the agent tends to concentrate on specific region of the state space). For detailed analysis, please refer appendix A.
Slipping DeepSea problem size 30
Slipping DeepSea
Exploration
Suocessful episodes
DBMF-BPI
0.4
400
BSP
BSP2
(tiie)
0.3
IDS
200
0.2
0.1
0.0
1000
2000
3000
10
20
30
40
50
Episode
DeepSea problem size
Figure 6: Slipping DeepSea problem. On the left: total number of successful episodes (i.e., that the agent managed to reach the final reward) for a grid with 30 input features. On the right: standard deviation of tvisit the last episode, depicting how much each agent explored (the lower the better).
For the slipping DeepSea problem, results depicted in Fig. (see also Appendix A.4 for more details).. Besides the number of successful episodes, we also display the standard deviation of (tvistt) across all cells (i,j), where (fvish) indicates the last timestep t that cell (i,j) was visited (normalized by NT, the product of the grid size, and the number of episodes). The right plot shows (Ivist)) for different problem sizes, highlighting the good exploration properties of DB DBMF-BPP Additional details and exploration metrics can be found in Appendix A.
7 Conclusions
In this work, we studied the problem of exploration in Reinforcement Learning and presented MF- BPI, a model-free solution for both tabular and continuous state-space MDPs. To derive this method, we established novel approximation of the speeccc- lower bound necessary for identifying nearly-optimal policies. Importantly, this approximation depends only on quantities learnable via stochastic approximation, paving the way towards model-free methods. Numerical results on hard- exploration problems highlighted the effectiveness of our approach for learning efficient policies over state-of-the-art methods.
10

---

Acknowledgments
This research was supported by the Swedish Foundation for Strategic Research through the CLAS project (grant RIT17-0044 and partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. The authors would also like to thank the anonymous reviewers for their valuable and insightful feedback. On a personal note, Alessio Russo wishes to personally thank Damianos Tranos, Yassir Jedra, Daniele Foffano, and Letizia Orsini for their invaluable assistance in reviewing the manuscript.
References
[1] Peter Atkins, Peter William Atkins, and Julio de Paula. Atkins' physical chemistry. Oxford university press, 2014.
[2] Peter Auer. Using confidence bounds for exploitation-exploaiiee trade-offs. Journal of Machine Learning Research, ((Nov):397-422) 2002.
[3] Peter Auer, Nicolo Cesa-Bianchi. and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-256, 2002.
[4] Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in Neural Information Processing Systems (NeurlPS), 21, 2008
[5] Kamyar Azizzadenesheli, Emma Brunskill, and Animashree Anandkumar. Efficient exploration through bayesian deep q-networks. In 2018 Information Theory and Applications Workshop (ITA), pages 1-9. IEEE, 2018.
[6] Chenjia Bai, Lingxiao Wang, Lei Han, Jianye Hao, Animesh Garg, Peng Liu, and Zhaoran Wang. Principled exploration via optimistic bootstrapping and backward induction. In International Conference on Machine Learning, pages 577-587. PMLR, 2021.
[7] Andrew G Barto. Intrinsic motivation and reinforcement learning. Intrinsically Motivated Learning in Natural and Artificial Systems, Springer, pages 17-47, 2013.
[8] Mare G Bellemare, Will Dabney, and Rémi Munos. A distributional perspective reinforce- ment learning. In International Conference on Machine Learning, pages 449-458. PMLR, 2017.
[9] Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research, 31ct))213-231, 2002.
[10] Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. In International Conference on Learning Representations, 2018.
[11] Richard Y Chen, Szymon Sidor, Pieter Abbeel, and John Schulman. Ucb exploration via g-ensembles. arXiv preprint arXiv:1706.000 502, 2017.
[12] William Clements, Bastien Van Delft, Benoît-Maric Robaglia, Reda Bahi Slaoui, and Sébastien Toth. Estimating risk and uncertainty in deep reinforcement learning. arXiv preprint arXiv:1905.00638,, 2019.
[13] Will Dabney, Mark Rowland, Mare Bellemare, and Rémi Munos. Distributional reinforce- ment learning with quantile regression. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018.
[14] Richard Dearden, Nir Friedman, and Stuart Russell. Bayesian q-learning. In Proceedings of the 15th National Conference on Artificial Intelligence, American Association for Artificial Intelligence, July, 1998, pages 761-768. AAAI Press, 1998.
[15] Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Ian Osband, Alex Graves, Vlad Mnih, Remi Munos, Demis Hassabis, Olivier Pietquin, al. Noisy networks for exploration. Xrxiv preprint arXiv:1706.10200 2017.

---

[16] Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 998-1027. PMLR, 2016.
[17] Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert Kappen. Minimax pac bounds on the sample complexity of reinforcement learning with a generative model. Machine learning, Springer, 91:325-3493 2013.
[18] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with stochastic actor. In International Conference on Machine Learning, pages 1861-1870. PMLR, 2018.
[19] Chi Jin, Zeyuan Bhuen Sebastien Bubeck, and Michael Jordan. Is q-learning provably efficient? Advances in Neural Information Processing Systems (NeurIPS), 31, 2018.
[20] Sham Machandranath Kakade. On the sample complexity of reinforcement learning. University of London, University College London (United Kingdom), 2003.
[21] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best arm identification in multi-armed bandit models. Journal of Machine Learning Research, 17:1-42, 2016.
[22] Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Machine learning, Springer, 49:209-22 202.222222222 2002.
[23] Johannes Kirschner and Andreas Krause. Information directed sampling and bandits with heteroscedastic noise. In Conference On Learning Theory, pages 358-384. PMLR, 2018.
[24] Pawel Ladosz, Lilian Weng, Minwoo Kim, and Hyondong Oh. Exploration in deep reinforce- ment learming: A survey. Information Fusion, 2022.
[25] Tor Lattimore and Marcus Hutter. Pac bounds for discounted mdps. In Algorithmic Learn- ing Theory: 23rd International Conference, ALT 2012, Lyon, France, October 29-31, 2012. Proceedings 23, pages 220-334. Springer, 2012.
[26] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[27] Kimin Lee, Michael Laskin, Aravind Srinivas, and Pieter Abbeel. Sunrise: A simple unified framework for ensemble learning in deep reinforcement learning. In International Conference on Machine Learning, pages 6131-6141. PMLR, 2021.
[28] Aymen Al Marjani and Alexandre Proutiere. Adaptive sampling for best policy identification in markov decision processes. In International Conference on Machine Learning. pages 7459- 7468. PMLR, 2021.
[29] Aymen Al Marjani, Aurélien Garivier, and Alexandre Proutiere. Navigating to the best policy in markov decision processes. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[30] Borislav Mavrin, Hengshuai Yao, Linglong Kong, Kaiwen Wu, and Yaoliang Yu. Distributional reinforcement learning for efficient exploration. In International Conference on Machine Learning, pages 4424-4434. PMLR, 2019.
[31] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforce- ment learning. In International Conference Machine Learning, pages 1937-1937. PMLR, 2016.
[32] Thomas M Moerland, Joost Broekens, and Catholijn M Jonker. Efficient exploration with double uncertain value networks. In Deep Reinforcement Learning Symposium, NIPS 2017. 2017.
[33] Nikolay Nikolov, Johannes Kirschner, Felix Berkenkamp, and Andreas Krause. Information- directed exploration for deep reinforcement learning. International Conference on Learning Representations, 2018.
12

---

[34] Jungseul Ok, Alexandre Proutiere, and Damianos Tranos. Exploration in structured reinforce- ment learning, Advances Neural Information Processing Systems (NeurIPS), 31, 2018.
[35] Ian Osband and Benjamin Van Roy. Bootstrapped thompson sampling and deep exploration. arXiv preprint arXiv: 1507.00300. 2015.
[36] Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems (NeurIPS), 26, 2013.
[37] Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via hootstrapped dqn. Advances in Neural Information Processing Systems (NeurIPS), 29, 2016.
[38] Ian Oshand, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. In International Conference on Machine Learning, pages 2377-2386. PMLR, 2016.
[39] Ian Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep re- inforcement learning. Advances in Neural Information Processing Systems (NeurIPS), 31, 2018.
[40] Ian Osband, Benjamin Van Roy, Daniel Russo, and Zheng Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20:1-62, 2019.
[41] Ian Osband, Yotam Doron, Mattco Hessel, John Aslanides, Eren Sezener, Andre Saraiva, Katrina McKinney, Tor Lattimore, Csaba Szepesvári, Satinder Singh, Benjamin Van Roy, Richard Sutton, David Silver, and Hado van Hasselt, Behaviour suite for reinforcement learning. In International Conference on Learning Representations, 2020.
[42] Jason Pazis, Ronald E Parr, and Jonathan P How. Improving pac exploration using the median of means. Advances in Neural Information Processing Systems (NeurIPS), 29, 2016.
[43] Matthias Plappert, Rein Houthooft, Prafulla Dhariwal, Szymon Sidor, Richard Chen, Xi Chen, Tamim Asfour, Pieter Abbeel, and Marcin Andrychowicz. Parameter space noise for exploration. In International Conference on Learning Representations, 2018.
[44] Daniel J Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen, et al. A tutorial on thompson sampling. Foundations and Trends@ in Machine Learning, 11(1): 2018.
[45] Richard M Ryan and Edward L Deci. Intrinsic and extrinsic motivations: Classic definitions and new directions. Contemporary educational psychology, 25(1):544 2000..
[46] Mohit Sewak. Deep reinforcement leurning. Springer, 2019.
[47] Alexander L Strehl and Michael L Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 74(8):1309 1331, 2008.
[48] Alexander L Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L Littman. Pac model-free reinforcement learning. In Proceedings of the 23rd International Conference on Machine learning, pages
2006.
[49] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[50] István Szita and Csaba Szepesvári. Model-based reinforcement learning with nearly tight exploration complexity bounds. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pages 1031-1038, 2010.
[51] Jérôme Taupin, Yassir Jedra, and Alexandre Proutiere. Best policy identification in discounted linear mdps. In Sixteenth European Workshop on Reinforcement Learning, 2023.
[52] William Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):255-294, 1933.
13

---

[53] Andrea Tirinzoni, Aymen Al Marjani, and Emilie Kaufmann. Near instance- optimal pac reinforcement learning for deterministic mdps. Advances in Neural Information Processing Systems (NeurIPS), 35:8785-877 -7998, 2022.
[54] Andrew Wagenmaker and Kevin G Jamieson. Instance-dependent near-optimal policy identifi- cation in linear mdps via online experiment design. Advances in Neural Information Processing Systems (NeurIPS), 35:5968-5555 598155981112 2022.
[55] Andrew J Wagenmaker, Max Simchowitz, and Kevin Jamieson. Beyond no regret: Instance- dependent pac reinforcement learning. In Conference on Learning Theory, pages 358-418. PMLR, 2022.
[56] Yuanhao Wang, Kefan Dong, Xiaoyu Chen, and Liwei Wang. Q-learnig with ucb explo- ration is sample efficient for infinite-horizon mdp. In International Conference on Learning Representations, 2019.
[57] Christopher John Cornish Hellaby Watkins. Learning from delayed rewards. PhD) thesis, Cambridge University, Cambridge, England, 1989.
[58] Jeremy Wyatt. Exploration and inference in learning from reinforcement. PhD thesis, University of Edinburgh, Edinburgh, England, 1998.
[59] Tianpei Yang, Hongyao Tang, Chenjia Bai, Jinyi Liu, Jianye Hao, Zhaopeng Meng, Peng Liu, and Zhen Wang. Exploration in deep reinforcement learning: comprehensive survey, arXiv preprint 1rXiv:2109.06660 2021.
[60] Andrea Zanette, Mykel J Kochenderfer, and Emma Brunskill. Almost horizon-free structure- aware best policy identification with generative model. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019.
14


Reviews:
[{"review_id": "qM5PbXOn9Z", "reviewer": "Reviewer_VjsS", "summary": "This work focuses on the exploration of reinforcement learning and introduces a novel model-free algorithm. The authors derive a new bound for the lower bound of the number of samples needed to identify a near-optimal policy. Based on that, they develop a model-free exploration strategy that is applicable to both tabular and continuous MDPs. Experimental results demonstrate that their strategy is competitive to existing approaches in efficiently identifying optimal policies.", "questions": "- Considering the gap between the theory and the algorithm mentioned above, is there any convergence guarantee for the algorithm?\n\n- When the authors select $\\bar k=1$ (line 211) and arrive at $\\bar{U}^1_{\\epsilon}$, does it remain an upper bound for $T_\\epsilon$?\n\n- I was a bit confused about the main idea. The authors first proposed an upper bound $\\tilde{U}$ for the well-established lower bound $T_0$, and then they proceeded to carry out all computations based on this new bound. Although I understand that it is their point to derive this approximation that makes the bound easier to handle, it remains unclear to me why this approach is rational. Typically, what we usually do is to derive a more manageable upper bound on another harder upper bound, or derive a more manageable lower bound on another harder lower bound. Then we just need to minimize the new bound, because in doing so, the original bound is indirectly minimized (or maximized). However, this paper proposed an upper bound for the lower bound, making the aforementioned relationship inapplicable. Therefore, I am curious what the underlying principle here is.", "limitations": "No negative societal impact was identified.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Theoretically, the new proposed bounds look novel and sound. They transform the original lower bound into a more manageable form, making it easier to handle and apply in practical scenarios.\n\n- Empirically, the experiments confirm the superiority of the proposed algorithm over existing methods, aligning with their claims.", "weaknesses": "- There seems to be a big gap between the theory and the algorithm. The theoretical results involve certain quantities (e.g., $\\Delta(s,a)$) that are unknown to the algorithm. The authors addressed this issue by approximating these quantities through Q-value (and M-value) learning, subsequently treating the approximated Q and M as ground truth for all computations. This introduces a substantial gap between the theory and the algorithm.\n\n- It would improve if the authors could provide an intuitive explanation of the terms in the complicated expressions presented in Theorems 4.1 and 4.2. Understanding and evaluating these results as a whole seems challenging without a better explanation.\n\n- Although I admit that the main contributions lie in the theoretical aspects, it would be better to conduct more complicated experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments and constructive feedback. We appreciate the time you took to review our paper and will address each of your comments individually. \n\n\n> When the authors select $\\bar k=1$ (line 211) and arrive at $\\bar U_\\epsilon^1$, does it remain an upper bound for $T_\\epsilon$ ?\n\n Concerning your question about $\\bar k=1$ and whether $\\bar U_\\epsilon^1$ remains an upper bound for $T_\\epsilon$, the answer is no. Note that for each state-action pair $(s,a)$ the optimal value of $\\bar k$ may differ. In principle, it is possible to extend our algorithm to account for this, at the cost of an increased computational complexity that does not seem worth given the numerical results that we obtained. Lastly, the choice of $\\bar k=1$ follows simply from the scaling argument that we outline in the paper.\n\n> Considering the gap between the theory and the algorithm mentioned above, is there any convergence guarantee for the algorithm?\n\nRegarding the convergence guarantee for our algorithm, we understand your concern. In this context, asymptotic almost sure convergence of the $Q,M$-values is guaranteed if we mix the allocation with an $\\epsilon$-soft policy (see, for example, Algorithm 6, line 6 in the `EstimateAllocation` function, page 38 of the appendix; similarly, also for the tabular case).\n\n\nHowever, compared to [1,28], it is hard to derive a sample complexity upper bound due to the various approximations. It is not  within the scope of this paper, but we believe that, in absence of approximations, we could apply similar ideas from [1] and [28] to find a sample complexity upper bound.\nFinally, since the $Q,M$-values are all you need to compute the optimal allocation of Corollary 5.1, then asymptotically, we can still converge a.s. to the minimizer of $\\bar U_\\varepsilon$. \n\nLastly, regarding your concern about the gap, it is common in information-theoretical algorithms of this type to use the current estimate according to a certainty-equivalence principle (see for example [1,28] and other papers on best arm identification [17,22]).\n\n\n\n> I was a bit confused about the main idea. [...] Therefore, I am curious what the underlying principle here is.\n\nTo clarify our approach of deriving an upper bound for the lower bound, we realize that the derivation is not straightforward.\n\nThe idea is as follows: for an MDP $M$ the quantity $T_\\varepsilon(\\omega)$ represents the characteristic time, i.e., characterizes the sample complexity of estimating the optimal policy using an exploration policy $\\omega$. Therefore, the minimum value $\\min_\\omega T_\\varepsilon(\\omega)$ yields the characteristic time of the lowest sample complexity that one can possibly achieve. Unfortunately, this minimum cannot be easily computed since it involves solving a non-convex problem (see [1] for an example). It is then not possible to find a non-trivial smaller bound that is convex, unless it works only for a certain type of MDP.\n\nHowever, it is possible to find a convex upper bound of $T_\\varepsilon(\\omega)$, that we call $\\bar U(\\omega)$, and then compute the minimizer $\\bar \\omega^\\star=\\arg\\min_\\omega\\bar U(\\omega)$. How far is this new minimum from the minimum of $T_\\varepsilon$ is still an open question (and quite difficult to answer).\n\n\n\n\n> It would improve if the authors could provide an intuitive explanation of the terms in the complicated expressions presented in Theorems 4.1 and 4.2.\n\nYour suggestion to provide a more intuitive explanation for the complicated expressions in Theorems 4.1 and 4.2 is well taken. Using the explanation of the main idea in the paragraph above, we can see now how $\\bar U(\\omega)$ is a convex upper bound of $T(\\omega)$ that we try to minimize. This upper bound is characterized by some quantities, e.g. $\\Delta(s,a)$ and $M_{sa}^{\\bar k}[V^\\star]$. The former represents the sub-optimality gap (the hardness of learning the optimal action in a certain state). While the latter term represents a sort of variance of the value function in the next state (to be precise, the $2k$-th moment), and thus, it represents a sort of \"difficulty\" in learning the optimal policy by looking at future trajectories (it measures the uncertainty in the value estimate due to the aleatoric nature of the MDP).\n\nIn comparison, in [1] they found a characterization based also on the span of the MDP, which is however not necessary in our formulation. To summarize, if we think of $\\bar U$ as the characteristic time of the MDP, then we see that the sample complexity is completely characterized by the suboptimality gaps and the $2k$-th moment of the value function in each state.\n\n\n> Although I admit that the main contributions lie in the theoretical aspects, it would be better to conduct more complicated experiments.\n\n\nAs for conducting more complicated experiments, we understand the concern of the reviewer. However, note that we used hard exploration environments that are also used by other practitioners when evaluating exploration algorithms ( see for example [39], or the Bsuite library, where they propose the DeepSea problem and the Cartpole swingup problem to assess exploration properties). Furthermore, we used a more difficult version of the classical DeepSea environment (because of the slipping probability), and evaluated the environments for various difficulty levels for all environments.\n\n\\\n&nbsp;\n\nThank you again for your review that will greatly help us to improve our paper. We are pleased that you acknowledged the novelty and soundness of our proposed bounds and how they transform the lower bound into a more manageable form. \n"}, {"review_id": "FrEcQKFbgE", "reviewer": "Reviewer_KZND", "summary": "This paper introduces an approximation of a lower bound on the number of samples needed to identify a nearly optimal policy directly applicable to model free RL.\nThey further propose a model free exploration strategy that can be applied to the tabular and continuous MDPs.\n", "questions": "Why have you used the 2k-th moments in the bound? \nCan the authors clarify which eq. Compute Allocation, training and estimate minimum gap refer to?\nHow is the mask probability being computed? are the results sensitive to this parameter? \n\n\n", "limitations": "The authors could provide a more thorough limitation description of the approach under which circumstances does the proposed approach fail, how critical and reasonable are the assumptions made, for instance the communicating MDPs. How does the approach perform in more challenging tasks such as Montezuma's revenge, and more structured exploration tasks. Under which types of exploration difficulty does the proposed approach excel or fail.\n\n", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is clear and well written. With experiments showing the proposed approach seems competitive with other exploration approaches. ", "weaknesses": "The paper lacks a comparison of the current approach with more common exploration strategies in DeepRL such as 34, 37. \nThe results remain very toy. It would be great to have an understanding of the kind of exploration the proposed approach performs well, with increasingly sparse rewards? on which circumstances is this preferable. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review and positive feedback on our paper. We appreciate the constructive suggestions and have taken them into consideration. We address below your questions  and discuss the perceived weaknesses.\n\n> Why have you used the 2k-th moments in the bound?\n\n There are multiple reasons for the use of 2k-th moments in the bound: (1) first, we wanted to find an alternative bound to [1] that did not involve the span of an MDP, since this quantity is difficult to estimate online (since it involves an $\\infty$-norm), and may not characterize very well the difficulty of learning the MDP; (2) secondly, we found that the span of an MDP can be lower bounded by the square root of the  variance  of the value function (Lemma C.1 in the appendix, line 969). This prompted us to find an alternative bound, through an alternative proof technique (Lemma C.10 is the main tool, line 1156 in the appendix) that led us to the refinement of the bound in [1].\nThis refinement allows us to characterize the bound in terms of the $2k$-th moment of the value function in each state-action space, which can be estimated online through the use of stochastic approximation.\n\n> Can the authors clarify which eq. Compute Allocation, training and estimate minimum gap refer to? How is the mask probability being computed? are the results sensitive to this parameter?\n\n For your question about which equations Compute Allocation, training, and estimate minimum gap refer to, please refer to Algorithm 6 in the appendix, page 38.\n\nRegarding the mask probability computation $p$, it is a user chosen hyper-parameter. It draws similarity from classical Bootstrapping, and it can speed-up the learning process. The higher the value of $p$, the worse the characterization will be of the parametric uncertainty of the $Q,M$-values, while a smaller value of $p$ may compromise exploration efficiency. While we also discuss more in detail the algorithm in the appendix, we will make sure to include a more detailed explanation of the masking probability in the revised version of the manuscript.\n\n\n\n> The paper lacks a comparison of the current approach with more common exploration strategies in DeepRL such as 34, 37\n\n Unless we misunderstood the reviewer comment, we compare with the bootstrapped technique from [34,37,38]. In the numerical results it is called BSP (Bootstrapping with additive prior [38], which is an advancement on classical Bootstrapped DQN). We mainly focused on comparing with other information-theoretical strategy for a fair comparison.\n\n\n> It would be great to have an understanding of the kind of exploration the proposed approach performs well, with increasingly sparse rewards? on which circumstances is this preferable.\n\n From the numerical results, we see that the strategy performs well in environments with sparse reward. In general, we expect good performance in sparse reward environments due to characterization of the parametric uncertainty through Bootstrapping with random prior functions. This technique, combined with our proposed bound, allows us to derive effective exploration strategies that only explore where it is needed to learn the optimal value function. However, the exploration strategy, since it is guided from theory, relies on some assumptions such as having a communicating MDP. Therefore, it is possible that one may need to tailor it depending on the type of problem. For example, one may not need to explore at every step, but may try to pair the exploration policy with another policy depending on the problem. Finally, we remark that we discuss limitations, including basic assumptions and requirements, in the appendix (right after the table of content, page 17). \n\n\\\n&nbsp;\n\nWe thank the reviewer once again for your valuable feedback and for your positive endorsement of our paper's contributions. "}, {"review_id": "4vg45aYi9t", "reviewer": "Reviewer_M4pn", "summary": "\nThe authors propose a model free approach to exploration in RL, that is based around best policy identification. This technique, unlike prior work, uses stochastic approximation to learn a lower bound on the policy performance based on collected samples.\n", "questions": "\n- Could you please clarify where the proof and derivations of the different theorems are? For instance, for theorem 4.2 there is a nice explanation of the implications of the theorem, but it is not stated how that upper bound is derived. The same is true about corollary 5.1.\nPlease clarify this, as the evaluation of soundness of the paper heavily relies on being able to find how these theorems where proved.\n\n- Algorithm 1 only samples actions according to the allocation omega, does this mean that over time omega converges to pi^*?\n\n- Corollary 5.1, the denominator in  H_epsilon contains the term delta_min is defined in terms of the optimal policy for the MDP. How are you sampling according to corollary 5.1 (algorithm 1), when the optimal policy pi^* is needed to compute that value?\nThis is a bit unclear.", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "\n\n- The paper presents an model-free approach that's heavily guided by theory, and results show how this technique can be effective in improving exploration in terms of improved performance as well as reduced performance variance.\n", "weaknesses": "\n\n- The paper is a bit tough to get through; being so theoretically heavy, some intuitive high-level explanation of their implications would be really helpful for the reader to follow along the thought process of the authors.\n\n- It is unclear where the derivation of the many theorems is in the text. For example, looking for a derivation on how the authors reached at corollary 5.1, the closest reference I found in the appendix was section B.3, but that's just an explanation on how to use that corollary. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful review and positive feedback. We appreciate the time you took to review our paper and have taken into consideration your suggestions. We address below your questions and discuss the perceived weaknesses.\n\n\n> Could you please clarify where the proof and derivations of the different theorems are?[...] Please clarify this, as the evaluation of soundness of the paper heavily relies on being able to find how these theorems where proved.\n\n We apologize for any confusion regarding the location and details of the derivations.  The derivation of all the proofs can be found in the appendix, Section C. In Section C.1, we derive some general results, and later in Section C.2, we derive the alternative bound. The main lemma used to prove Theorem 4.2 is Lemma C.10 (line 1156 in the appendix). Corollary 5.1 is proved in Section C.2.3 (see Corollary C.8). Please, note that the bound that we derive in the appendix is \\emph{more general} that the one we present in the main paper. In fact, the lower bound we find in the appendix holds also for MDPs with multiple $\\varepsilon$-optimal policies. We also want to thank the reviewer for asking this question, we will include additional references in the revised manuscript to clarify where to find the proofs for Corollary 5.1 and Theorem 4.2.\n\n\n\n> Algorithm 1 only samples actions according to the allocation $\\omega_t$, does this mean that over time $\\omega_t$ converges to $\\pi^\\star$?\n\n Note that the allocation $\\omega_t$ is an exploration policy, and it _should not_  converge to the greedy policy $\\pi^\\star$. However, the samples that we obtain when exploring should be used to learn the greedy policy $\\pi^\\star$ in an off-policy way. Therefore, this method is inherently off-policy.\n\nAs a final remark: the exploration policy $\\omega_t$  is derived from Corollary 5.1. When applied in a model-free fashion, as we do, it should converge to the optimal allocation given by Corollary 5.1 projected on the set defined by the navigation constraints. For the interested reader that wants to try with a toy example, in the code you can find in `BoundsAnalysis/utils/utils.py` the function to compute the projection given an allocation and the transition function (`project_omega` or `compute_stationary_distribution`).\n\n\n> How are you sampling according to corollary 5.1 (algorithm 1), when the optimal policy $\\pi^\\star$ is needed to compute that value?\n\nThe confusion surrounding the use of the optimal policy in Corollary 5.1's sampling is understandable. As in [1], and other papers that use information-theoretical arguments, we use a certainty-equivalence principle, where we use the current plug-in estimator of the quantity of interest. In our case, we use the $Q$-values of the greedy policy, learnt through off-policy learning, to derive $\\pi_t^\\star$, the current estimator of the greedy policy at time $t$.\n\n> ...some intuitive high-level explanation of their implications would be really helpful for the reader to follow along the thought process of the authors.\n\nWe understand that the theoretical density of the paper can be challenging to navigate. We will include in the revised version a more intuitive high-level explanation of the concepts and their implications to assist the readers in grasping our thought process.\n\nFor completeness, we briefly summarize the general idea is as follows: for an MDP $M$ the quantity $T_\\varepsilon(\\omega)$ represents the characteristic time, i.e., characterizes the sample complexity of estimating the optimal policy using an exploration policy $\\omega$. Therefore, the minimum value $\\min_\\omega T_\\varepsilon(\\omega)$ yields the characteristic time of the lowest sample complexity that one can possibly achieve. Unfortunately, computing the best optimal exploration policy  $\\arg\\min_\\omega T_\\varepsilon(\\omega)$ amounts to solving a non-convex problem (see [1] for an example).\n\nTo address this challenge, the main idea is to find a convex upper bound of $T_\\varepsilon(\\omega)$, that we call $\\bar U(\\omega)$, and then compute the minimizer $\\bar \\omega^\\star=\\arg\\min_\\omega\\bar U(\\omega)$ (for example, using corollary 5.1 to obtain a closed form solution). Therefore, we can use $\\bar \\omega^\\star$ to explore an environment. \n\n\n\\\n&nbsp;\n\nWe would like to thank you again for your review, and  for acknowledging the novelty and soundness of our model-free approach to exploration in RL.\n"}, {"review_id": "sbhZMk6qgc", "reviewer": "Reviewer_qwpS", "summary": "The paper introduces a model-free exploration approach developed on an information theoretical basis. Firstly, the lower bound on the number of samples for a near-optimal policy is estimated, and based on this lower bound, the paper develops an exploration strategy for both tabular and deep RL approaches. The exploration strategy is further validated via experiments, where it is found to be superior to other competing approaches.", "questions": "1. Can more challenging environments possibly be added? If not, are there any fundamental limitations that make this infeasible?\n\n2. Wouldn’t the approximation errors in the deep RL version of the algorithm affect the suboptimality gap? Is this somehow accounted for?\n\n3. Apart from the current results, perhaps for some of the environments, the actual exploration trajectories could be traced/charted out to explicitly show how the exploration is modified. I noticed something along these lines included in the appendix, but it would be good to bring similar results forward into the main text. \n\n4. It would benefit readers to include more details about the main results in [1].\n\n5. Although it may be obvious, in the cartpole swingup environment, it would be good to include a brief paragraph regarding why/how increasing k makes the task more difficult.\n\n6. In line 297, what is N?\n\n7. I am not sure why Fig 3 shows the performance in Riverswim vs |S| and ForkedRiverswim vs N\n\n8. How is $\\Delta_{min}$ initialized in the Deep RL version?\n", "limitations": "Currently, there is no explicit section outlining the limitations. I suggest the authors include a short paragraph about this covering at least the basic assumptions and requirements for the proposed to be applicable. Perhaps some comments regarding the scalability of the approach to more complex environments could also be added if that is indeed an issue. ", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper is generally well written and addresses an important problem. The developed exploration strategy having an information theoretic basis sets it apart from some of the previous approaches which have mainly been based on heuristics.\n", "weaknesses": "The paper does not include experiments in more complex environments such as Montezuma’s revenge, where exploration is known to be a key challenge. A more detailed summary of the main intuitions and theoretical results from [1] could have made the paper more readable.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your  insights and constructive feedback. We appreciate the effort you invested in reviewing our paper and have carefully considered your suggestions. Below, we respond to your queries and address the highlighted concerns.\n\n> Currently, there is no explicit section outlining the limitations.\n\nWe actually discuss limitations, including basic assumptions and requirements, in the appendix (right after the table of content, page 17) due to lack of space.\n\n\n> What is $N$?  Why Fig 3 shows the performance in Riverswim vs $|S|$ and ForkedRiverswim vs $N$? How is $\\Delta_{min}$ initialized?\n\nWe understand the confusion. The parameter $N$ is more properly explained in the appendix, Section A.2 (page 19). The Forked Riverswim environment consists of two rivers, each of length $N-1$, plus the starting state (that's why $|S|=2N-1$). To improve clarity, we can change the $x$-label of Figure 3 to maintain consistency.\n\nRegarding $\\Delta_{min}$, we suggest to initialize it a small value. In the attached code, we can see that we initialized it to $10^{-6}$ for the Slipping DeepSea problem, and to $10^{-2}$ for the Cartpole Swingup problem.\n\n> Wouldn’t the approximation errors in the deep RL version of the algorithm affect the suboptimality gap? \n\nWe understand the reviewer's concern. In this case, the approximation error that is introduced is, somehow, modeled by the parametric uncertainty, and thus  covered by the technique that we propose (as long as the neural networks are expressive enough to model the true $Q$-value function).\n\n\n> [...]the actual exploration trajectories could be traced/charted out to explicitly show how the exploration is modified.\n \nWe appreciate your suggestion to bring forward some of the exploration trajectories into the main text of the paper. This could indeed help readers to better understand the practical impact of our exploration strategy. We will consider this for the final version of our paper, by adding perhaps an image in the introduction.\n\n> Can more challenging environments possibly be added? If not, are there any fundamental limitations that make this infeasible?\n\nAs for conducting more complicated experiments, we understand the concern of the reviewer. There are not fundamental limitations that make this infeasible. We simply used hard exploration environments that are used for example by BSP [39] and the DeepMind BSuite library (where they propose the DeepSea problem and the Cartpole Swingup problem to assess exploration properties). Furthermore, we used a more difficult version of the classical DeepSea environment (because of the slipping probability), and evaluated the environments for various difficulty levels for all environments. However, we will try to include more environments and add plots to improve clarity.\n\n\n> It would benefit readers to include more details about the main results in [1].\n\n Your suggestion to include more details about the main results from [1] is noted. We initially aimed for conciseness, but understand that more context could make the paper more readable. We will strive to strike a better balance in the revised version, by adding a more detailed explanation.\n\n> In the Cartpole Swingup environment, it would be good to include a brief paragraph regarding why/how increasing $k$ makes the task more difficult.\n\nFor a detailed explanation of the environment, please refer to Section A.6 of the appendix (page 27). While we are constrained by the page limit for the main paper, we understand the reviewer's request for more details.We will make sure to clarify where to find more information in the main text of the manuscript.\n\nIn the Cartpole Swingup problem the agent incurs in a negative reward unless the cart's position and the pole's angle satisfy, respectively, the conditions $|x|<1-k/20$ and $cos(\\theta)>k/20$. Therefore we see that as $k$ increases, the agent needs to learn a more stabilizing controller to collect positive rewards.\n\n\n\\\n&nbsp;\n\nThank you again for your review and for being overall positive about the novelty and soundness of our approach. \n"}, {"review_id": "pGb4c65YIQ", "reviewer": "Reviewer_1tWW", "summary": "In this paper, the authors propose a way of obtaining tighter PAC bounds for model-free reinforcement learning. The new theoretical results allow the authors to propose new practical methods for exploration in both discrete and continuous state spaces. The proposed algorithms use ensembles of Q-values, and the results are very competitive when compared with model-based approaches.", "questions": "* How exactly is the alearotic uncertainty in the value function accounted for by the methods proposed in this paper?\n\n* There is probability p in Alg. 1. It would be useful if its role and rationale were explained.\n\n* The use of the variance of the value function is slick, and the authors are careful saying that this addresses the aleatoric uncertainty only, but it would be useful if the authors explained why epistemic uncertainty is not addressed.", "limitations": "I tried to discuss this in the weaknesses and questions sections above. Even though some of my comments may appear critical, I am very positive about this paper. This is solid work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "* The new methods adapt to specific problems in an automated way.\n\n* The paper is well written, and the discussion is supported by relevant citations. The contributions are backed up by both theoretical arguments and empirical results on a range RL domains.\n\n* The contributions seem relevant and important. The results indicate that the proposed methods have merit.\n\n* The paper comes with a comprehensive and long appendix (which would be a pain to read for a busy reviewer), but the future readers will most certainly appreciate it. The appendix provides many details that contribute to the quality of the work.\n", "weaknesses": "* The authors should make it clear from the start that the new algorithms are ensembles. After reading a few pages of the paper, I was anticipating a clever algorithm that would be purely based on the proposed theory. It was a bit disappointing that ensembles were used at the end. I don't say that this is bad, well there is no free lunch, but it would be fair to expect that, when the new algorithms are mentioned for the first time, ensembles are mentioned too.\n\n* The paper argues that model-base approaches are expensive to run. The methods presented in this paper are ensembles. What is their runtime? Are that they really faster than model-based methods?\n\n* Since the new methods proposed in this paper are ensembles, I would expect some discussion on ensembles in RL. I would expect that there must exist ensemble based RL methods that could be competitive with the methods presented here. Literature review on ensembles in RL would be useful. A classic paper on this is: Wiering, M.A. and Van Hasselt, H., 2008. Ensemble algorithms in reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 38(4), pp.930-936.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We really appreciate your  review and  positive endorsement of our paper's merits. We're particularly pleased that the reviewer recognizes the innovative approach to tighter PAC bounds, the quality of the writing, and the comprehensive appendix. \n\n\n> How exactly is the alearotic uncertainty in the value function accounted for by the methods proposed in this paper? [...] it would be useful if the authors explained why epistemic uncertainty is not addressed by the variance of the value function.\n\n Your questions on aleatoric uncertainty, and why epistemic uncertainty is not addressed by the bound, are both very important.\n\n1. Regarding the former question, the variance of the value function in the next state  represents a sort of \"difficulty\" in learning the optimal policy by looking at future trajectories (due to the stochasticity of the MDP). It quantifies the dispersion of  values in the next state. In contrast, while the sub-optimality gap provides a measure of how far our current policy is from the optimal one, the variance measures the uncertainty in the value estimate due to the aleatoric nature of the MDP. Finally, our bound generalizes to even-th moments of the value function, but the rationale remains the same.\n2. Regarding the latter question, to our understanding, the reason why parametric/epistemic uncertainty is not addressed by the bound is that the result that we along with [1] propose can only be achieved asymptotically, i.e., when the parametric uncertainty has vanished (when all state-action pairs have been visited infinitely often). Our take on this is that the derivation of the bound does not account for the current uncertainty in the estimates of the $Q$-values and $M$-values. Using the certainty equivalence principle, we simply use the plug-in estimator of these values, without considering this uncertainty. This opens up an exciting research direction on how to incorporate this uncertainty knowledge in the derivation of the bound (perhaps using Bayesian methods).\n\nTo overcome this issue, we leverage a bootstrapping approach to characterize this type of parametric uncertainty and use the ensemble to sample the $(Q,M)$-functions to derive the allocation strategy through Corollary 5.1.\n\n\n\n\n\nWe hope that this explanation is clear and addresses the reviewer's questions.\n\n\n> There is probability $p$ in Alg. 1. It would be useful if its role and rationale were explained.\n\n Regarding the mask probability computation $p$, it is a user-chosen hyper-parameter that draws similarity to classical Bootstrapping and can speed up the learning process. The higher the value of $p$, the less accurate the characterization will be of the parametric uncertainty of the $Q,M$-values, while a smaller value of $p$ may compromise exploration efficiency. While we also discuss more in detail the algorithm in the appendix, we will make sure to include a more detailed explanation of the masking probability in the revised version of the manuscript.\n\n\n> Clarification on Ensemble Approach.\n\nWe understand and share the concern regarding the late introduction of the ensemble approach in our algorithms. To be more transparent, we will introduce the ensemble aspect earlier in the paper.\nWe will also include a comprehensive review on ensembles in RL, incorporating the cited classic paper to contextualize our work.\nRegarding the use of ensembles, we found that randomized prior value functions provide an excellent way to reduce the computational complexity of model-based methods. We typically do not need to increase the number of ensemble members but simply tune the scale parameter of the random prior function.\nLastly, we believe that model-based approaches are useful depending on the problem and can be used efficiently in conjunction with our method.\n\n\\\n&nbsp;\n\nThank you once again for the detailed feedback and your overall favorable view of our work. "}]

Author rebuttal:

Meta-review: After the discussion, the reviewers in general agree the algorithm is novel and proposed method and analysis provide a good contribution to the problem of exploration in RL.
Decision: Accept (poster)