BooVI: Provably Efficient Bootstrapped Value Iteration
Authors: Boyi Liu
Qi Cai
Zhuoran Yang
Zhaoran Wang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Reinforcement Learning
Exploration

Abstract: Despite the tremendous success of reinforcement learning (RL) with function approximation, efficient exploration remains a significant challenge, both practically and theoretically. In particular, existing theoretically grounded RL algorithms based on upper confidence bounds (UCBs), such as optimistic least-squares value iteration (LSVI), are often incompatible with practically powerful function approximators, such as neural networks. In this paper, we develop a variant of \underline{boo}tstrapped LS\underline{VI}, namely BooVI, which bridges such a gap between practice and theory. Practically, BooVI drives exploration through (re)sampling, making it compatible with general function approximators. Theoretically, BooVI inherits the worst-case $\tilde{O}(\sqrt{d^3 H^3 T})$-regret of optimistic LSVI in the episodic linear setting. Here $d$ is the feature dimension, $H$ is the episode horizon, and $T$ is the total number of steps.

Boo VI: Provably Efficient Bootstrapped Value Iteration
Boyi Liu"
Qi Cait
Zhuoran Yang!
Zhaoran Wang
Abstract
Despite the tremendous success reinforcement learning (RL) with function ap- proximation, efficient exploration remains significant challenge, both practically and theoretically. In particular, existing theoretically grounded RL algorithms based upper confidence bounds (UCBs), such optimistic least-squares value iteration (LSVV), are often incompatible with practically powerful function ap- proximators, such neural networks. In this paper, develop variant of bootstrapped LSVI, namely BooVI, which bridges such a gap between practice and theory. Practically, Boo'II drives exploration through (re)sampling, making it compatible with general function approximators. Theoretically, BooVI inherits the worst-case d - of optimistic L.VV in the episodic linear setting. Here d the feature dimension, H the episode horizon, and the total number of steps.
Introduction
Reinforcement learning (RL) with function approximation demonstrates significant empirical success in broad range of applications [e.g., [6] 38,
45]. However, computationally and statistically efficient exploration of large and intricate state spaces remains major barrier. Practically, the lack of iemporally-extended exploration [31] 28 30 in existing RI. algorithms, e.g., deterministic policy gradient
40
(39] and soft actor-critic 19], hinders them from solving more challenging tasks, e.g.,
Montezuma's 's Revenge in Atari Games 22 17], in more sample-efficient manner. Theoretically, it remains unclear how to design provably efficient RL algorithms with finite sample complexities or regrets that allow for practically powerful function approximators, e.g., neural networks.
There exist two principled approaches to efficient exploration in RL, namely optimism in the face of
uncertainty [e.g.. [1111 23 24] and posterior sampling [e.g.. 22 34, 33
30 27 (36.
The optimism- based upproach often instantiated by incorporating upper confidence bounds (UCBs) into the estimated (action-)valu functions bonuses, which used direct exploration. In the tabular setting, the resulting algorithms, e.g., variants of upper confidence bound reinforcement learning (UCRL) [4] 21 11 5], known attain the optimal worst- case regret (32). Beyond the tabular setting, it remains unclear how to construct closed-form UCBs principled manner for general function approximators, e.g., neural networks. The only exception is the linear setting [5] 52 24 8) where optimistic least-squares value
iteration (LSVVI is known to attain optrmoptimal (with respect T KH) worst-case regret. However, the closed-form UCB therein is tailored to linear models I 9 rather than fully general purpose. general-purpose.
Northwestem University; boyiliu201 8 e.northwesterm.cc Northwestern University; qicai2022 n.rttheesterm.edu
I Princeton University: zy6@ prreerrinntto.edu Northwester University; @ waaiingg@@@mmmoommmmm..mc
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

On the other hand, the posterior- based approach, which originates from Thompson sampling + 337, can be instantiated using randomized (action-) functions [4 30
27 [6]
Unlike optimistic I.SVI, the resulting algorithm, namely randomized I.SVI, straightforwardly allows for general function approximators, as it only requires injecting random noise into the training data of LSVI. Ideally, such injected random noise does not depend on particular function approximators. In the tabular setting, randomized LSVI is known to attain near-optimal worst-case and Bayesian regrets [30 36). Meanwhile, in the linear setting, randomized LSVI is very recently shown to attain a near-optimal worst-case regret [54]. which is only worse than that of optimistic LSVI by a factor of v vdH. Here d is the feature dimension and H is the episode horizon. However, achieving such regret requires a nontrivial modification of the injected random noise, which is tailored to linear models. Such a specialized modification diminishes the supposed practical advantage of randomized LSVI.
To bridge such gap between practice and theory, we aim to answer the following question: Can we design an RI. algorithm that simultaneously achieves the practical advantage of randomized LSVI and the theoretical guarantee of optimistic LSVI?
In this paper, we propose a variant of bootstrapped LSVI, namely BooVI, which combines the advantages of the optimism-base and posterior-based approaches. The key idea of Boo is to use posterior sampling to implicitly construct an "optimistic version" of the estimated (action-)vall) value functions in a data-driven manner. Unlike randomized LSVI, which samples from the posterior only once, e.g.. by injecting random noise into the training data of LSVI, Boo samples from the posterior
multiple times, e.g., via the Langevin dynamics [48 35 Upon evaluating an action at a state, BooVI ranks the values of the randomized faction-)valus functions sampled from the posterior in descending order and returns a top-ranked value, which can be shown to be approximately optimistic. Generally speaking, Boo corresponds to bootstrapping the noise in the least-squares regression problem of LSVI. As result, it can be viewed bootstrap technique used in bootstrapped deep Q-networks (DQNs) [31 30), which demonstrates significant empirical success in terms of exploration.
parametric bootstrap counterpart of the nonparametric
Compared with existing RL algorithms with function approximation, the advantage of Boo is twofold:
Practically, BIoVI bypasses the explicit construction of the closed- form UCB in optimistic LSVI. Like randomized LSVI, BooVI straightforwardl allows for general function approxi- mators, it only requires injecting random noise into the training process of LSVI, e.g., via the Langevin dynamics.
Theoretically, Bo inherits the worst-case Ö( (d of optimistic LSVI in the linear setting. Here d is the feature dimension, H/ is the episode horizon, and T is the total number of steps. Such regret is better than the best known worst-case regret of randomized LSVI by factor of v d.H. More importantly, unlike the specialized variant of randomized LSVI studied in [54). Boo can be applied to the linear setting "as is", without tailoring the injected random noise to linear models.
More Related Work:
The idea of using posterior sampling to achieve optimism in a data-driven manner is previously studied in the linear bandit setting (26) and the tabular setting of RL 3 In fact, our linear setting of RL covers the linear bandit setting as a special case, where the episode horizon H is set to one, and the tabular setting of RL another special case, where the feature mapping is the canonical basis of the state and action spaces. Although BooVI is practically applicable to general function approximators, our theoretical guarantee on worst-case regret is only applicable to the linear setting. Despite the recent progress [49 22 [3 [5], simultancously achieving provable computational and statistical efficiency in exploration with general function approximators remains challenging. See, e.g.,
for the recent progress in the contextual bandit setting. Finally, we refer 55 for theories on the generalized models of linear MDPs, which all share similar (approximately) linear structure with the class of linear MDPs considered in the analysis of this paper. We expect our regret bound stays the same for those settings with linear structures, or admits an extra O()T)) dependency over T for those settings with approximately linear structure, where > describes the level of nonlinearity in the MDP. We also refer readers to [50] for sharper regret bounds in linear MDPs, which are out of the scope of this paper.
18)
readers to 446 53 57
2

---

2 Background
In this section, we introduce the general problem setting.
Episodic Markov Decision Process. We consider the episodic Markov decision process represented
by a tuple (S, A, H, P. r). where S is compact state space, a finite action space with cardinality
A, H is the number of timesteps in each episode, P = {Pa with Pa. S x S x A + [0,
for all h E [H] is the set of transition kernels, and r (TH] with r4 S x A + [0: 1] for all
E [H] is the set of reward functions.
At each timestep o A + R for all h E [H], interacts with the environment by first taking an action of with probability , (a s and then receiving the corresponding reward r = rΛ (s af)
[M] of episode k, agent state s 8 with policy x² { he where
We evaluate the performance of policy = {TT (TEHE starting from timestep h, and state-action pair
(s, a) using its action-vaie value function Q7 S x A R, which is defined as
H
Q (s. a) = E
The (8ur, ax) 8h. = On
M==h
for & E [H]. Correspondingly, the value function
V SS - R of a policy л is defined as
H
(s) = E
Σ -
TM (sw, and 8/ = E, [Q a) sn = =s],
for all E [H]. Here the expectation E, [.] is taken over the trajectory generated by æ. Also, we let Qh+ = 0 and thus V 0. Furthermore, we denote by V% (s) the value function corresponding to the optimal policy x². Finally, for notational simplicity, we define [PAV] = Ey'-P.( [ (V()), where V S IR can be any function.
For any algorithm that generates sequence of policies {or ]e[[K], we track its performance via the cumulative regret defined by
K Regret(A K) = -IV - (+4),
k=1
where K is the number of episodes. Here sf is the initial state of episode k. which is arbitrarily chosen the start of the episode.
Bootstrapped Value Iteration
In this section, we introduce Bootstrapped Value Iteration (BooVI in Algorithm IT. For notational simplicity, we write rn (sf, a as r throughout the rest of this paper. Also, in this paper, we write max(minf: }, 0} min(., ++, *.an and denote by || - the 2-norm for vectors.
Least-Squares Value Iteration. At timestep E [H] of episode k. given the estimated action-value a) for all 7 E 1 - and E A, let V ($ max 1 (5 a). Then, Least-Squares Value Iteration (I.SVI) updates the parameter of the action-value function via
function 1
Sf + argmin
|
Σ
(rT
V (5 Q(5 (l:w))
(3.1)
WERd
where Q(:::
A Rd being its parameter, and À > 0 is the regularization parameter. Although the deterministic parameter update by LSVI could exploit the historical data well, has limited ability to address the exploration need in more challenging tasks.
the parameterization of action-value function with w Rd
Bootstrapped Value Iteration. To achieve guided exploration, we introduce BooVI (Algorithm I which uses bootstrapping to enforce the optimism of the estimated action-value function.
3

---

At the timestep h of episode k; given the current data buffer D = {(s,, o2 "h (41) re(k-1) which contains the data collected from the previous i episodes, and the current bootstrapped state values { &
1]. we define
y r V h+1 (s++)); for all [k 1].
(3.2)
With po(w) as prior and p(v (1%, an),, ; w) as the likelihood of yh. the posterior of w is given by
A-1
1ep r(w| (Viii (e D po(w)
p(on (5% w)) T=1
II
(3.3)
In BooVI (Algorithm[) T. we propose to sample repeatedly from such posterior for N& times, which is equivalent to sampling repeatedly from randomized action-value function since each sample w/, corresponds to one randomized action-value function Q(- (((.:wh Such collection of posterior weights is later used construct the bootstrapped action-value function in Algorithm 2
To independently sample from the posterior in 3,3) we can consider, e.g., using the Langevin dynamics w(t + 1) w(t) (w(t), where
Aw(() = <t ( (ogroo(()()))
V log (b))))) mh, Σ
(3.4)
where >> O is the stepsize, and (0 (t). We note here that, after running sufficient
many iterations with suitable choices of stepsizes 6 > 0, the Langevin dynamics gives effectively
independent parameter samples from the posterior in 3.3
To instantiate the connection between the posterior 3.3 with the LSVI, consider Gaussian prior
and likelihood as an example. For the Gaussian prior w ~ No0 Ia) and the Gaussian likelihood p(y (8% a),,w) x exp( (.T Q(5T, (T:w)) (220=) the posterior of is given by
1 p( (VA re(k- Di) exp - ||011
1
E(E (0 Q(sh ([:))) (3.5)
20
where o > is an absolute constant, In this case, the maximum posteriori (MAP) estimate of w coincides with the weight estimate / obtained by LSVI. Such observation suggests that sampling from the posterior distribution p(w (V/, (15%+))ree exploitation based on the available data, and generate noise for randomized exploration. More specifically, the Aw(t) in (3.4) takes the form of
D would allows to both achieve
Aw(t)= = 4 [w(tt++ 2
T Σ vT. -(5 ((5, Vu (T:((t)) + my.
which can be viewed as using stochastic gradient descent to solve for the LSVI update 3. with o² and Vit replaced by V See also Lemma E.1 for the closed form of the posterior in linear MDP setting with Gaussian prior and likelihood.
We would like to highlight that, although the theoretical guarantee in this paper is built upon the Gaussian prior and likelihood, the choices of prior and likelihood are flexible. For example, we can use uninformative prior for generalized linear model, and Gaussian process prior for kernel of overparameterized neural networks (6). Moreover, as suggested by theoretical results on Langevin Dynamics (56) and illustrative experiments in Appendix [F] the computational overhead caused by replacing the minimization of 3.1 with posterior sampling is mild.

---

Algorithm I Boottstraped Value Iteration (BooVI)
1: Require: MDP (S, (, H. P.r). r). action-value function parameterization Q(:;; S x A x
R + IR, number of episodes K, number of posterior weights {Ne]ke[k], lower and upper bootstrapping ratios a, 8 E (0, 1)
2: Initialize the data buffer Dj O for h E [H]
3: For episode k 1,.... K do
4: Set NE.. + fa- 1. < 13 NNll and Whi wH+1 t 0 for all i e [N&]]
5: Sample uniformly from {Ne,a NE. + +,...,,, N,,
6: For timestep H....... H...., do
7:
Generate 1 (1 using Algorithm with weights (w DE(NN and parameter mi for all a E A and T -k] ( < maxacA ( a) for all r E [k-1]
8:
Independently sample ( [ee[NN]] from the posterior p(w (5++1()))) D defined in (333), c.g., using Langevin dynamics in (3.4) end For timestep 1 H do
9:
11:
12:
Generate (1 a) using Algorithm 2 with weights " hel] and parameter n. for all A
13:
Take action of +- argmax 2% a), and observe rft and s
14:
Update the data buffer DK+1 + D U [(s ah, rh. s +)
15:
End
16:
End
The following Algorithm2 serves as the critical building block of BooVI for enforcing the optimism of the estimated action- value. At episode in BooVI, for any (s. S x A, Algorithm ranks the estimated action-value functions corresponding to the posterior sample obtained in Line of
Algorithm [ in ascending order. Then, in order to enforce the optimism of the estimated action-value function, Algorithm reorrillm@essmmplss resamples the n4-th top-ranked value from the ordered estimated action-value functions in the manner of bootstrapping. Finally, to ensure sufficient optimism of the obtained bootstrapped action-value function, we extrapolate with tunable parameter y 1.
Algorithm 2 Bootstrapping Action Value Function
1: Require: Action-value function parameterization Q(: :) 8 AxR R, posterior sample (wx Nejj "eEiN. integer ngg E [Ni,), extrapolation parameter v >> 1, and state-action pair (s, a)
2: Compute ( (s, t Q(s, a; (.)) for all i E [N&]
3: Set (s, a) + (1/Nz) INr (s,a)
4: Rank 10 (s, (s,a))E[NA) in ascending order to obtain
(Q),10) (s, ()E()))))
5: Output: (s, min((1 v) (s. + (o.(me) (s,a), H h 17*
Remark 3.1 (Sample Efficiency and Computational Efficiency). Here we clarify the differences between sample efficiency and computational efficiency. Throughout this paper, we refer sample efficiency to the learning efficiency with respect to the total number T = K H of interactions with the environment. Such interactions can often time be very resource demanding. Thus, this paper seeks to provide an algorithm that aims to achieve the sample efficiency with respect to the number of such interactions. Although posterior weights are sampled in Algorithm [ the efficiency such posterior sampling process is categorized as computational efficiency since it is purely based on the current data buffer DJ and does not require any extra interaction with the environment.
Remark 3.2 (Additional Computational Cost). Here we discuss the computational cost of BooVI compared LSVI. (i) Posterior sampling vs. least-square minimization: Consider the Langevin dynamics in (..). Since posterior sampling replaces and admits similar steps as least-square minimization, the computational cost should not differ significantly between L.VI and BooVI. (ii) Computing bootstrapped Q Q-function: To compute bootstrapped Q-function, at each state-action pair,
5

---

the extra sorting takes ( log N₂) time complexity, which makes the action selection procedure ( log N&) times slower. In addition, keeping N₂ posterior weights takes O N₂ memory. We note that, although the requirement on Nr. in our subsequent analysis is large, we should be able to use much smaller N₂ practice due to the pessimistic nature of the analysis. See Appendix F for illustrative experiment results.
is worth mentioning that BooVI is applicable to any specific parameterization Q(::; x A x Rd > of the action-value function and is fully data-driven. We also note here that the design of BooVI does not rely on the Gaussian prior/posterior or the Langevin dynamics sampling technique.
4
Main Results
While VI (Algorithm D is generally applicable to different parameterizations of the action-value function, we establish its regret for class of linear MDPs.
Linear Markoy Decision Process. We consider a class of MDPs, where the transition kernels and the reward functions linear in the same feature mapping. Specifically, we have the following definition.
Definition 4.1 (Linear MDP). MDP (S, called linear MDP with feature mapping Φ: S x A -> IRd, if for any h [ there exists d unknown signed measures fan = =1u (1)
(d)
over S and an unknown vector 0₁ E IR such that for any (s,a) E S x A, we have
(- 8, a) = (0(s, a), pa()), rn(s, a) (0(s, 0n)
(4.1)
See [51 52 24 for examples such a class of linear MDPs. Specifically, examples include tabular MDPs where d = SA and the feature mapping is the canonical basis Φ(s, = ((sa)) and the simplex feature space where the feature space {ō(s, a) (s, a) E S x A} is a subset of the d-dimensional simplex. See also [14 44 [25] for related discussions on such linear representation. For notational simplicity, we write the feature @ ax))) as of throughout the rest of this paper.
Based Definition
without loss of generality,
make the following assumption.
Assumption 4.2. The MDP (S, A. H, P, r) is a linear MDP with [| a)ll < 1 for all (s, E SxA and ( ||O|]]} S vd for all h E [H].
To motivate the linear parameterization of the action-value function in the subsequent section, we have the following proposition.
Proposition 4.3 (Linear Action-Value Function, Proposition 2.3 in [24] For linear MDP, for any policy and h [H). there exists w IRd such that for all (s, a) E S A, we have (s, = (o(s, a),
Regret of BI for Linear MDPs. For a linear MDP, by Proposition 4.3 the parameterization Q(:-:.) :): S x A x Rd + IR in BooVI should take the form of Q(s, a; w) (ø(s, a), w). where Rd. Furthermore, when the prior and the likelihood are Gaussian, the posterior of w is Gaussian distribution with mean being is the weight update by LSVI with chioce of A o?
For any bootstrapping ratio E (0, 1), we write Cg = ( throughout the rest of this paper, where (--) is the cumulative distribution function of the standard Gaussian. Then, we have the following upper bound of regret of BooVI.
Theorem 4.4. Suppose that Assumption 4.2 holds, and that d 2 2. We set a = 1, dHt and fix failure probability p E (0, 1]. Then there exists sequence of posterior sample sizes [Nej) and there exist absolute constants cæ > ca > O, such that if N₂. O(TTTkk/p") for all & e [K].
C. = Ca Vl, and Cp c3 Vt, BooVI (Algorithm with Gaussian posterior in (35) satisfies
Regret( K) = (
with probability at least p. where T K H and = log(3dT/p).
Proof. See Section 5 for proof sketch.

---

Proof Sketch
Notation. At episode k, given the number of posterior sample weights N₂ and given ne sampled in Line Li of Algorithm we define Cj. Φ (rux/N2 At timestep h of episode k. further given
posterior weights [NeN))) ]e[[N.]. corresponding the bootstrapped action-value function 2% generated by Algorithm 2 we define the bootstrapped value function as
V (s) max Ø% (8, a).
(5.1)
acA
Next, we define the mean bootstrapped action-value functions as
(s) min Bu (1 v)- (s, + v. (s, H h + 13²
(5.2)
where E [ is taken over w with respect to the posterior p(w ( h+1 ( (t D defined
3.3
Correspondingly, we define the mean bootstrapped value function
(=())) max Q% acA
(5.3)
Also, denote by
k-1 t = (A
Σ
sh 0%
(5.4)
the mean of the posterior distribution p(w ( (5% Dk), where y% defined in 3.2 For fixed failure probability p E (0, 1]. we write log(3dT/pp /p), where T KH. Finally, define matrix A& E Rdxd by
A = Σ
( 4 18.
(5.5)
Concentration Events. Before proving Theorem 4.4 we first present two lemmas, each character- izing an event that involved throughout the remaining proofs. The first lemma characterizes the concentration behavior of the bootstrapped action-value function Ø
Lemma 5.1. Let o = 1, v = dH, and Cg = cæ Vi for some C3 > 0. For a fixed failure probability p E (0, 1], we define & as the event that the condition
(h a) (x, a)) S (cs/Va+3) H Hddk
satisfied for all (s, k, h) E S x Ax K x H Then, there exists sequence posterior sample sizes (Na]ee[K] satisfying N₂ (d k/p / for all i E [K], such that P(E) ' 1 p/3.
Proof. See Appendix C for a detailed proof.
The second lemma characterizes the concentration behavior of the mean bootstrapped state value function Vk AM
Lemma 5.2. Let = 1, v dH, and C3 ca vi for some constant c3 > For a fixed failure
E (0, 1], we define E' as the event that the condition
Σ th (Vh. W
IPA M 1 am))
dH
(AP)-1
satisfied for all (k, h) E [K] x H.. where = (0g(3(1+c))d7 /p)].
Then we have P(E') 2 1 1-p/3.
Proof. See Appendix D for detailed proof.

---

Model Estimation Error. With the events E and E' ready, we can proceed to characterize the model estimation error Sh S A for all (k, h) [K] [H] defined as
ch - Q (rA + [Px (PAV*++))
(5.6)
which can be comprehended as the estimation error of the model at timestep h of episode A: induced by the mean bootstrapped value function Q We have the following lemma charaterizing the model estimation error ç defined in (5.6). Lemma 5.3 (Model Estimation Error). Let d 2 2, v = dH, = 1, and E (0, 1]. Then there exists a sequence of posterior sample sizes {N&, KE(K]. and there exist absolute constants Gg > Co
such that, if N = O/dT"k/pp for all E [K]. C. = Ca Vt, and C3 = ca Vl, for the model estimation error ch defined in (5.6). we under events and E' that
0 5 Ch (8, a) < (Ca + cg) aHVv (AA)
for all (s, h) E S x Ax K x [H].
Proof. Under Assumption 4.2 using 4.
we have [Pr TP h+1] Is (6') (x)")) Then, V
with slight abuse of notation, we denote by V ( Is (itzl())nndd R2d and write
Pa PAV h+1 = (0, (A
V
= (A -
(1(T)) ( Vitalen)) + (1)) V
( (mn))
d. (A
Σ 0% (Pn V 1 mh) )) + (0,
(0, (A -'t (mn)))
where the second equality follows from (5. Thus, we have the following decomposition
(rn + Pa V. x+1 S u1 + u2.
where W/ is defined in 6.4 and
Th (V (Vi+22004+2) - [Pa hh gb3) (
0. (A
61
(0, (A
Σ Th Th.0% 0% v v rh
02
In the sequel, we upper bound un and U22 separately. Upper bounding uh First, we further decompose 11
Σ oh ((h+)))) V Vit1, (ot+1) + (V (Vh+1(sh+1) [Pr V 10 }})
(A
applying the Cauchy-Schward inequality to which we obtain
41 < 0, (A Σ th (Vi4 - -h+1(
(5.7)
V ④ (A+)
Σ 0% (Vh af) |P PPaVm-l($T
(Ag)-1
Now we proceed to upper bound the two terms on the right-hand side of (57 in the following. For the first term, since by Lemma 5.1 we have under event that V (sh+1)
V h+ (1h
(ca/ (ca/Vd+3) 3)- H / de/kk we have
( 6, (A
-k1
Σ 0h
- Vh - (cs/Va++) H di/k
(A
(5.8)
8

---

By the inequality and Lemma D.1 in [2] (see Appendix E we have
(A (At) )
1/2 s Vde/h: v (
Σ Φ (A
Σ Φ (A
th
taking which into (5.8) and gives
K
(A
%% ( (sh+1) - The - (6 |))))>> (co/Vā+ dH dHv oJ (TA))-1)
Σ
(5.9)
Taking 5.9 into (.7) and applying Lemma 5.2 to the second term on the fight-hand side of (5.7
we have under the events E and E' that
U1 E (cs/Vd+3) 3) dH dH 0 (A
(5.10)
Upper bounding U2: By 44.
have
= (ax) + V (+
Then, by the Cauchy-Schward inequality, we further obtain
U2 S T (A (IV (1n) + +110n ((all(as)-))
(A (1V [10all) s 2H/d VOT (OT(A)))
(5.11)
where the second inequality follows from A = la. and the last inequality follows from |10 S vd in Assumption well the fact that V (+) S H h s H 1 for all S. Combining
5.10 and 5.11 we obtain under event that
(6, (rh + PAV 8+ /////// (A
(5.12)
< (ce/VV++3 dH A dxl + 2H
< [ce/VV+ dH C. VV - ddH
where C³ > is an absolute constant. Next, we need to find an absolute constant cø > 0 such that
C² Vi = (cs/ vcs/vv++0 + 5) + C- / log(1 + cg) < C3 VL. Note that d 2 2 and 2 log 2, it suffices to pick 0g > 0 such that
log2 + log (1 + cg) < 11-1/ - -5| log
(5.13)
which must exist as the left hand side grows logarithmically in Cp and the right-hand side grows linearly in ca. For Cæ > O satisfying (5.13), we pick any ca > 0 such that C' S Co < ca and let
C. = Ca VT. By 5.12 and ra + [Pw V h+d S h + 1, we obtain under events and E' that
c min (p, Ck. (TT(A)) H n+13 (rn PAV h+1)
2 min (co C²) dH Viv TJ
20
On the other hand, by (5.12), we also have under events E and E' that
ch s (0) wht - (rn + PA PAa + C. V (T(TT))))))))))))))))()))))) s (ca + cg). dH Vi & (T(A))
Therefore, we finish the proof of Lemma 5.3
As results of Lemma 5.3 have the following two lemmas characterizing the optimism and the cumulative estimation error of the mean bootstrapped value function V respectively.

---

Lemma 5,4 (Optimistic Random Value Function). Let o and v dH. There there exists sequence of posterior sample sizes {Na & (ekjke and there exist absolute constants og ca > such that if N& = O(dT*k//app k/p²) for all & E [K]. C. = =ca Vt, and C3 = C3 Vt, we have under the events & and e" that
K
Σ
- -v so.
Proof. See Appendix D for detailed proof.
Lemma 5.5 (Cumulative Estimation Error), Let 1, v dH, and (0, 1J. There exists sequence of posterior sample sizes {N& kejk) and there exist absolute constants 63 > Co > such that if N₂ = OddT<k//oppp k/p²) for all & E [K]. C. = ca Vt, and C3 = cB vi, we have under the events & and E' that
K
E VI" (s4) S V18T22 log(3/p) + 4(03/ (eclc///// + HaKa
1=1
+ (Ca + cB) VdK
with probability at least p/3.
Proof. See Appendix D for a detailed proof.
Finally, the regret bound of BooVI for the class of linear MDPs be established consequence of the optimism (Lemmas 5.4p and the upper bound of the cumulative estimation error (Lemma of the bootstrapped value tunction.
Proof of Theorem 4.4 First, recall that we have V (s) defined in 5.3 We have the regret decom- position
K Σ (v) - -V (+ + Σ V (st)).
Regret( K)
(5.14)
Applying Lemmas
5.4 and 5.5
to 5.14p. we obtain under the events & and El that
Regret
5 12 log(3/p) Maca/Va HVKK.
+ (Ca + cg) dHH2
=(((H
(5.15)
with probability at least - p/3. Finally, by Lemmas 5.1 and 5.2 we have with least probability 1 - p/3 p/3 2p/3 that the events & and E' hold simultaneously Thus, we have (515 hold with probability at least p. which concludes the proof.
Conclusion
The cost of collecting data via online experiments is often prohibitive compared to collecting offline data, e.g., via posterior sampling. Thus, designing online learning algorithms that provably explores the environment in data-driven manner is essential. Moreover, applicability general environments critical since reinforcement learning tasks are getting more chanlleging and complex recently. We aspire motivate the design of novel reinforcement learning algorithms that utilize cheaper data to boost online sample efficiency. Our algorithm and analysis serve as a step towards developing general applicable and provable sample-efficient reinforcement learning. While this paper mainly on algorithmic and theoretical aspects of the bootstrapping idea in RL, it would be interesting to see the empirical strength BooVI in more challenging RL environments. We leave this part to our future work.
10

---

Acknowledgement
Zhaoran Wang acknowledges National Science Foundation (Awards 2048075, 2008827, 2015568. 1934931), Simons Institute (Theory of Reinforcement Learning), Amazon, J.P. Morgan, and Two Sigma for their supports.
Zhuoran Yang acknowledges Simons Institute (Theory of Reinforcement Learning).
References
[1] AADKSI-YADKORI, Y., PÁL., D. and SZEPESVÁRI, C. (2011). Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems.
AGARWAL, A., Hsu, D., KALE, S., LANGFORD, J., LI, and SCHAPIRE, R. (2014). Taming the monster: and simple algorithm for contextual bandits. International Conference on Machine Learning.
[3] AGRAWAL, S. and JIA, R. (2017). Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. In Advances in Neural Information Processing Systems.
[4] AUER, P. and ORTNER, R. (2006). Logarithmic online regret bounds for undiscounted reinforcement learning. In Advances in Neural Information Processing Systems.
[5] AZAR, M. G., OSBAND, I. and MUNOS, R. (2017). Minimax regret hounds for reinforcement learning. In International Conference Machine Learning.
BERNARDO, J., BERGER, J., DAWID, A., SMITH, AL. (1998). Regression and classification using gaussian process priors. Bayesian statistics 475.
[7] BROCKMAN, G., CHEUNG, V., PETTERSSON, L.,, SCHNEIDER, J., SCHULMAN, J., TANG, J. and ZAREMBA, W. (2016). Openai gym. arXiv preprint arXiv:1606.01540
[8] CAL, Q.. YANG, Z., JIN, C. and WANG, Z. (2019). Provably efficient exploration in policy optimization. arXiv preprint (rXiv:191.00583)
[9] CHU. W., LI. L.. REYZIN, L. and SCHAPIRE, R. (2011). Contextual bandits with linear payoff functions. In International Conference Artificial Intelligence and Statistics.
[10] DANI, V., HAYES, T. P. and KAKADE, S. M. (2008). Stochastic linear optimization under bandit feedback. Conference on Learning Theory.
[11] DANN, C. and BRUNSKILLL, F. (2015). Sample complexity of episodic fixed-horizon reinforcement learning. In Advances in Neural Information Processing Systems.
[12] DANN, C., LATTIMORE, and BRUNSKILL, E. (2017). Unifying PAC regret: Uniform PAC bounds for episodic reinforcement learning. In Advances in Neurul Information Processing Systems.
[13] DONG, K., PENG, J., WANG, Y. and ZHOU, Y. (2019). Vn-regret for learning in Markov decision processes with function approximation and low Bellman rank. arXiv preprint 1xXiv:1909002506
[14] DU, S. S., KAKADE, S. M., WANG, R. and YANG, L. F. (2019). Is good representation sufficient for sample efficient reinforcement learning? arXiv preprint arXiv: 19100030.
[15] Du, S. S., LUO, Y., WANG, R. and ZHANG, H. (2019). Provably efficient Q-learning with function approximation via distribution shift checking oracle. arXiv preprint arXiv: /906.063//
[16] DUAN, Y., CHEN, X., HOUTHOOFT, R., SCHULMAN, J. and ABBEEL, (2016). Benchmarking deep reinforcement learning for continuous control. International Conference on Machine Learning.
[17] ECOFFET, A., HUIZINGA, J., LEHMAN, J., STANLEY, K. O. and CLUNE, J. (2019). Go-explore: A new approach for hard-exploration problems. arXiv preprint arXiv:1901.1099;
[18] FOSTER, D. J., AGARWAL, A., DUDÍK, M., LUO, H. and SCHAPIRE, R. E. (2018). Practical contextual bandits with regression oracles. arXiv preprint arXiv: /803 01088.
[19] HAARNOJA, T., ZHOU, A., ABBEEL, P. and LEVINE, S. (2018). Soft actor-critic: Off- Off-policy maximum entropy deep reinforcement learning with stochastic actor. arXiv preprint arXiv:1801.01290

---

[20] HSU, D.. KAKADE, S. and ZHANG. Т. (2012). A tail inequality for quadratic forms of subgaussian random vectors. Electromic Communications in Probability 17.
[21] JAKSCH, T., ORTNER. R. and AUER. P. (2010). Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research 1563-1600.
[22] JIANG, N., KRISHNAMURTHY, A., AGARWAL, A., LANGFORD, and SCHAPIRE, R. E. (2017)-
Contextual decision processes with low Bellman rank are PAC-lcamable. In International Conference on Machine Learning.
[23] JIN, C.,, ALLEN-ZHU, Z., BUBECK, S. and JORDAN, M. I. (2018). Is Q-learning provably efficient? In Advances in Neural Information Processing Systems.
[24] JIN, C.. YANG, Z., WANG, Z. and JORDAN, M. I. (2019), Provably efficient reinforcement learning with linear function approximation. arXiv preprint 1rXiv:1907.05885
[25] LATTIMORE, T. and SZEPESVARI, C. (2019). Learning with good feature representations in bandits and in RL with a generative model. arXiv preprint arXiv:191..0666.
[26] MAY, B. C.. KORDA, N., LEE. A. and LESLIE, D. (2012). Optimistic bayesian sampling contextual- bandit problems. Journal of Machine Learning Research 13 2069-2106
[27] OSBAND, I., ASLANIDES, J. and CASSIRER, A. (2018). Randomized prior functions for deep reinforce- ment learning. In Advances in Neural Information Processing Systems.
[28] OSBAND, I., BLUNDELL, C., PRITZEL, A. and VAN Roy, B. (2016). Deep exploration via bootstrapped DQN. In Advances in Neural Information Processing Systems,
[29] OSBAND, I., Russo, D. and VAN Roy, B. (2013). (more) efficient reinforcement learning via posterior sampling. In Advances Neural Information Processing Systems.
[30] OSBAND, I., Russo, D., WEN, Z. and VAN Roy, B. (2017). Deep exploration via randomized value functions. Journal of Machine Learning Research.
[31] OSBAND, and VAN Roy, B. (2015). Bootstrapped Thompson sampling and deep exploration. arXiv preprint 107:0000..00300.
[32] OSBAND, and VAN ROy, B. (2016). On lower bounds for regret in reinforcement lcarning. arXiv preprint arviv: / 02732.
[33] OSBAND, I. and VAN ROY, B. (2017). Why is posterior sampling better than optimism for reinforcement learning? In International Conference Machine Learning.
[34] OSBAND, I., VAN ROY, B. and WEN, Z. (2014). Generalization and exploration via randomized value functions. arXiv preprint
[35] RAGINSKY, M., RAKHLIN, A. and TELGARSKY, M. (2017). Non-convex learning via stochastic gradient Langevin dynamics: a nonasymptotic analysis. arXiv preprint arXiv:1702.03849.
[36] Russo, D. (2019). Worst-case regret bounds for exploration via randomized value functions. Advances in Neural Information Processing Systems.
[37] RUSSO, D. J., VAN ROY, B., KAZEROUNI, A., OSBAND, and WEN, Z. (2018). A tutorial on Thompson sampling. Foundations and Trends@ in Machine Learning 11 1-96.
[38] SILVER, D., HUANG, A., MADDISON, C. J., GUEZ, A., SIFRE, L., VAN DEN DRIESSCHE, G., SCHRITTWIESER, J., ANTONOGLOU, I, PANNEERSHELYAM, V., LANCTOT, M. ET AL. (2016). Mastering the game of Go with deep neural networks and tree search. Nature 484.
[39] SILVER, D., LEVER, G., HEESS, N., DEGRIS, T., WIERSTRA, D. and RIEDMILLER, M. (2014). Deterministic policy gradient algorithms. In International Conference on Machine Learning-
[40] SILVER, D.,, SCHRITTWIESER J.. SIMONYAN, K., ANTONOGLOU, I., HUANG, A., GUEZ, A., HUBERT. T.. BAKER, L., LAI, M., BOLTON, A. ET AL. (2017). Mastering the game of Go without human knowledge. Nature 550 354.
[41] STREHL, A. L., LI, L., WIEWIORA, E.,, LANGFORD, J. and LITTMAN, M. L. (2006). PAC model-free reinforcement learning. In International Conference Machine Learning.
12

---

[42] TAIGA, A. A., FEDUS, W., MACHADO, M. C., COURVILLE, A. and BELLEMARE. M. G. (2019). Benchmarking bonus-based exploration methods on the Arcade Learning Environment. arXiv preprint (rXiv:I908.00) 02388.
[43] THOMPSON, W. R. (1933). On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika 25 285-294..
[44] VAN Roy, B. and DONG, S. (2019). Comments the Du-Kakade-Wann Saaiee--WWnn-aaaaa lower bounds. arXiv preprint arXiv:1911.0791
[45] WANG, W. Y.. LI, J. and HE, X. (2018). Deep reinforcement learning for NLP. In Association for Computational Linguistics.
[46] WANG, Y., WANG, R., Du, S. S. and KRISHNAMURTHY, A. (2019). Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint arXiv:1912.04136.
[47] WATKINS, C. J. C. H. (1989). Learning from delayed rewards.
[48] WELLING, M. and TEH, Y. W. (2011). Bayesian learning via stochastic gradient I. Langevin dynamics. In International Conference on Machine Learning.
[49] WEN, Z. and VAN ROY, B. (2017). Efficient reinforeement learning in deterministic systems with value function generalization. Mathematics Operations Research 42 762-782.
[50] XIONG, Z., SHEN, R. and Du, S. S. (2021). Randomized exploration is near-optimal for tabular mdp. arXiv preprint 2rXiv:2102.09700)
[51] YANG, L. and WANG, M. (2019). Sample-optimal parametric Q-learning using linearly additive features. In International Conference Machine Learning.
[52] YANG, L. F. and WANG, M. (2019). Reinforeement leaning in feature space: Matrix bandit, kernels, and regret bound. arXiv preprint 190.v:1905.1000 10389.
[53] YANG, Z., JIN, C., WANG, Z., WANG. M. and JORDAN, M. (2020). Provably efficient reinforcement learning with kernel and neural function approximations. Advances Neural Information Processing Systems
[54] ZANETTE, A., BRANDFONBRENER, D., PIROTTA, bounds for randomized least-squares value iteration. arXiv preprint arXiv:
LAZARIC, (2019), Frequentist regret
[55] ZANETTE, A., LAZARIC, A., KOCHENDERFER, M. and BRUNSKILL, E. (2020). Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning. PMLR.
[56] ZHANG, Y., LIANG, P. and CHARIKAR, (2017). A hitting time analysis of stochastic gradient langevin dynamics. In Conference on Learning Theory. PMLR.
[57] ZHOU, D., GU, Q. and SZEPESVARI, (2021). Nearly minimax optimal reinforcement leaming for lincar mixture markov decision processes, In Conference on Learning Theory. PMLR.
[58] ZHOU, H., CHEN, J.. VARSHNEY. and JAGMOHAN, A. (2020). Nonstationary reinforcement learning with linear function approximation. arXiv preprint 20X0v:2010.04244
13


Reviews:
[{"review_id": "n-fTCl3JvQo", "reviewer": "Reviewer_PuQ1", "summary": "This paper proposes a modified version of LSVI based on bootstrapping, called BooVI. Different from the famous Bootstrapped DQN, it shows that BooVI is provably efficient under linear MDP; meanwhile, although not theoretically supported, an implementation of BooVI also admits general function approximation like neural networks.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I consider this paper as a good attempt to theoretically support the power of bootstrapping and posterior sampling in reinforcement learning with function approximation. I also consider the specific usage of bootstrapping and Langevin dynamics as novel. The writing is in general a good flow, although with several potential improvements that will be given in \"Suggestions on writing\" part.\n\nHowever, I have several concerns about its significance and technical soundness. In particular, Although one of the advantage of BooVI over other provably efficient algorithms is that it practically admits general function approximation, the provided experiments do not contain this part. Other concerns will be given in \"Question\" part.\n\nQuestions:\n- How many steps does the Langevin dynamics take?\n- The given worst-case regret bound is not strictly an improvement over [1] beucause [1] considers a slightly more general low-rank MDP. Do you think the regret of BooVI is still applicable to the low-rank MDP?\n- In the proof of Lemma B.2, why does $\\mathcal{F}^1_1$ not contain $\\lbrace\\omega_h^{1, i}\\rbrace$? More importantly, the claim that $\\mathbb{E}\\left[\\xi^k_h(s_h^k, a_h^k, s_{h+1}^k)\\mid \\mathcal{F}^k_h\\right]=0$ makes me feel wired because I think neither $\\mathbb{E}\\left[\\bar{Q}_h^k-Q_h^{\\pi^k}(s_h^k, a_h^k)\\mid \\mathcal{F}_h^k\\right]=0$, since $Q^{\\pi^k}_h$ is based on the underlying unknown MDP, nor $\\mathbb{E}\\left[\\bar{V}^k_h(s^k_h)-\\bar{Q}^k_h(s_h^k, a_h^k)\\mid\\mathcal{F}_h^k\\right]=0$ holds, since $a_h^k$ does not necessarily maximize $\\bar{Q}^k_h(s_h^k, \\cdot)$. How do the terms in $\\xi^k\\_h(s_h^k, a\\_h^k, s\\_{h+1}^k)$ cancel each other under $\\mathbb{E}[\\cdot\\mid\\mathcal{F}_h^k]$?\n\nSuggestions on writing:\n- Is line 12 in Algorithm 1 necessary? It seems that $\\widetilde{Q}^k_h$'s have been generated at line 7 except $\\widetilde{Q}^k_1$.\n- The writing of proof for Lemma 5.3 may need some improvements because it uses $\\bar{\\omega}^k_h$ without defining it and implicitly uses Lemma E.1 without mentioning. I apologize if I simply missed them.\n- It is probably better to give a slightly more detailed sketch on how the optimism is ensured through Bootstrapping step in Algorithm 2.\n\n```\n[1] ZANETTE, A., BRANDFONBRENER, D., PIROTTA, M. and LAZARIC, A. (2019). Frequentist regret bounds for randomized least-squares value iteration. arXiv preprint arXiv:1911.00567.\n```\n\n- - -\n\nScore is increased after rebuttal because the technical concerns are well-addressed.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations of their work in Section 6 by presenting them as potential future works. The potential negative social impact is not addressed, which will generally be all potential malicious usage of any reinforcement learning algorithms.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "gBgpkBi5HtO", "reviewer": "Reviewer_GkJA", "summary": "This paper proposes a posterior sampling-based algorithm BooVI, which suffices for general function approximation purposes. In the case of linear MDP setting, it achieves $\\tilde{O}\\sqrt{d^3H^3T}$ regret with Gaussian posterior sampling. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, this paper provides an interesting posterior sampling algorithm BooVI that works for general MDPs. The technique and proofs look sound to me. However, I have the following two questions.\n\n1. The regret obtained for the linear MDP has no improvement over Jin et. al, is that due to the limitation of the technical tools or due to the algorithmic design?\n\n2. The paper would be more complete if you can instantiate more examples, e.g. linear mixture MDP. Could you provide an explanation of what the theoretical result would look like for your algorithm?\n\nGiven that the paper provides some nice contributions, I would like to raise my score if the authors can address my concerns.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 Hours"}, "extra_text": {}}, {"review_id": "LenLQNn8__h", "reviewer": "Reviewer_pToa", "summary": "The paper studies the low-rank model and proposes a randomized strategy that is competitive in terms of statistical efficiency with the best computationally tractable exploration method for such setting.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The work makes very strong contributions to randomized algorithms which are notoriously difficult to study theoretically. This ultimately gives a sqrt{dH} improvement compared to the state of the art randomized RL method (Zanette et al, 2020) with a seemingly clearer and more general analysis.\n\nI am not an expert of Langevin dynamics so I went very fast there. I have a direct question for the authors: is the algorithm computationally tractable, meaning that it requires poly(d,A,H,T,1/\\delta) elementary operations? (I understand yes but wanted a direct confirmation).\n\nUnfortunately I did not have the time to carefully examine the proof sketch, but if the result is correct without major caveats then the paper is strong.\n\nI have another question for the authors. The work seems to rely on the linear MDP setting a lot; would the analysis still work in setting of low-inherent Bellman error (e.g., Zanette et al ’20)? I suspect no, because the action value function you maintain is not linear, i.e., it cannot be expressed as \\phi(s,a)^\\top w.  \n\n====\n\nUnchanged after rebuttal", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "none", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "E2wCOJEq_wt", "reviewer": "Reviewer_gbqJ", "summary": "The paper proposes an approach for provably efficient reinforcement learning in linear MDPs that avoids constructing explicit confidence intervals. Instead, akin to posterior sampling, this method only requires sampling from a posterior distribution. The paper proves that this approach still yields optimistic value function estimates and retains the regret rate of optimistic LSVI. Because the algorithm requires only  sampling, the paper further claims that the method can be used more easily with general function approximation but does not provide empirical or theoretical results. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Summary: Overall, I like the boostrap idea but it is not clear how it provides any tangible benefit compared to existing approaches. The paper also has clarity issues.\n\n- Originality: I like the idea of using this concrete form of boostrap for constructing optimistic Q functions and to the best of my knowledge, it has not been proposed or analyzed before. That said, there are existing works that construct Q function estimates by maximizing over multiple posterior samples and which provide theoretical guarantees in the tabular MDP setting. \n- Significance: BooVI is likely more conservative than optimistic LSVI, thereby loosing one of the main benefits of RLSVI. This seem to be confirmed by the illustrative experiments in the appendix, where the performance of optimistic LSVI is better or on par than BooVI's. Although the guarantees of BooVI and optimistic LSVI are stronger than that of RLSVI, one would expect it that RLSVI to outperform both without significant parameter tuning. \n- Quality: The feature that BooVI only requires posterior sampling and is thus more suitable for use with general function approximation is presented as one of the main advantages. Yet, the paper does not provide any concrete evidence that BooVI is in fact more suitable with general function approximation, neither empirically nor theoretically. This claim is therefore not substantiated. While it is true that sampling is often easier than constructing confidence intervals, this requires a posterior representation that is accurate or which at least induces sufficient exploration. The paper needs to provide concrete examples for this argument to be convincing.\n- Clarity: The paper is not sufficiently clear. Here are a few instances that needs improvement:\na) Specifically, the algorithm description in 3 was unnecessary convoluted with cyclic dependencies. For example, the reader does not know where tilde V come from and the reference to Line 1 in Alg 1 seems incorrect. The reader further wonders what the posterior is in line 122 which will only be make clear later. I suggest to first present the posterior given some target values (including the concrete example with Gaussian prior) and then explain how the optimistic target values are generated from the posterior samples, which is the main innovation in this paper.  \nb) I recommend to restate the condition on C_alpha and C_beta in Thm 4.4 and lemmas as alpha = ... and beta = ... to clarify that they are conditions on those algorithm parameters.\nc) The quantity \\bar \\omega is used extensively in the proof sketch of the main paper and the appendix but never introduced. Lemma E.1 should be stated from and center to clarify this.\nd) Generally, it would be more useful for the proof sketch to highlight the differences to existing work, concretely the analysis of optimistic LSVI. \n\n\nMinor comments and typos:\n- Line 168: class MDPs -> class of MDPs\n- Alg 1 Ln 7: uising -> using", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper does not sufficiently discuss the technical limitations of the proposed approach, concretely the challenges around defining good posteriors for settings beyond linear MDPs. \nI do not foresee negative societal impacts of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper improves the state-of-the-art analysis of randomized RL algorithms with function approximation. The authors should improve the presentation and add more empirical support.
Decision: Accept (Poster)