BooVI: Provably Efficient Bootstrapped Value Iteration
Year: 2022

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 bootstrapped LSVI, 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 e O( p d3H3T )-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.

text: p d3H3T )-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.

heading: 1 Introduction
text: Reinforcement learning (RL) with function approximation demonstrates significant empirical success in a broad range of applications [e.g., 16, 38, 40, 45]. However, computationally and statistically efficient exploration of large and intricate state spaces remains a major barrier. Practically, the lack of temporally-extended exploration [31, 28, 30] in existing RL algorithms, e.g., deterministic policy gradient [39] and soft actor-critic [19], hinders them from solving more challenging tasks, e.g., Montezuma’s Revenge in Atari Games [42, 17], in a 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., 4, 41, 21, 11, 12, 5, 23, 24] and posterior sampling [e.g., 29, 34, 33, 30, 27, 36].
• The optimism-based approach is often instantiated by incorporating upper confidence bounds (UCBs) into the estimated (action-)value functions as bonuses, which are used to direct exploration. In the tabular setting, the resulting algorithms, e.g., variants of upper confidence bound reinforcement learning (UCRL) [4, 21, 11, 5], are known to attain the optimal worstcase regret [32]. Beyond the tabular setting, it remains unclear how to construct closed-form UCBs in a principled manner for general function approximators, e.g., neural networks. The only exception is the linear setting [51, 52, 24, 8], where optimistic least-squares value iteration (LSVI) [24] is known to attain a near-optimal (with respect to T = KH) worst-case regret. However, the closed-form UCB therein is tailored to linear models [1, 9] rather than fully general-purpose.
⇤Northwestern University; boyiliu2018@u.northwestern.edu †Northwestern University; qicai2022@u.northwestern.edu ‡Princeton University; zy6@princeton.edu §Northwestern University; zhaoranwang@gmail.com
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
• On the other hand, the posterior-based approach, which originates from Thompson sampling [43, 37], can be instantiated using randomized (action-)value functions [34, 30, 27, 36]. Unlike optimistic LSVI, the resulting algorithm, namely randomized LSVI, 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 p dH . Here d is the
feature dimension and H is the episode horizon. However, achieving such a 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 a gap between practice and theory, we aim to answer the following question: Can we design an RL 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-based and posterior-based approaches. The key idea of BooVI is to use posterior sampling to implicitly construct an “optimistic version” of the estimated (action-)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, BooVI 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 (action-)value functions sampled from the posterior in descending order and returns a top-ranked value, which can be shown to be approximately optimistic. Generally speaking, BooVI corresponds to bootstrapping the noise in the least-squares regression problem of LSVI. As a result, it can be viewed as a parametric bootstrap counterpart of the nonparametric bootstrap technique used in bootstrapped deep Q-networks (DQNs) [31, 30], which demonstrates significant empirical success in terms of exploration.
Compared with existing RL algorithms with function approximation, the advantage of BooVI is twofold:
• Practically, BooVI bypasses the explicit construction of the closed-form UCB in optimistic LSVI. Like randomized LSVI, BooVI straightforwardly allows for general function approximators, as it only requires injecting random noise into the training process of LSVI, e.g., via the Langevin dynamics. • Theoretically, BooVI inherits the worst-case eO( p d3H3T )-regret 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 a regret is better than the best known worst-case regret of randomized LSVI by a factor of p dH . More importantly, unlike the specialized variant of randomized LSVI studied in [54], BooVI 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 as 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 its worst-case regret is only applicable to the linear setting. Despite the recent progress [49, 22, 13, 15], simultaneously achieving provable computational and statistical efficiency in exploration with general function approximators remains challenging. See, e.g., [2, 18] for the recent progress in the contextual bandit setting. Finally, we refer readers to [46, 53, 57, 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 ✏ > 0 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.

heading: 2 Background
text: 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 a compact state space, A is a finite action space with cardinality A, H is the number of timesteps in each episode, P = {Ph}h2[H] with Ph : S ⇥ S ⇥A ! [0, 1] for all h 2 [H] is the set of transition kernels, and r = {rh}h2[H] with rh : S ⇥A! [0, 1] for all h 2 [H] is the set of reward functions.
At each timestep h 2 [H] of episode k, an agent at state sk h 2 S with policy ⇡k = {⇡k h }h2[H], where ⇡k h : A ⇥ S ! R for all h 2 [H], interacts with the environment by first taking an action ak h with probability ⇡k h (ak h | sk h ) and then receiving the corresponding reward rk h = rh(skh, a k h ).
We evaluate the performance of policy ⇡ = {⇡h}h2[H] starting from timestep h, and state-action pair (s, a) using its action-value function Q⇡
h : S ⇥A! R, which is defined as
Q⇡ h (s, a) = E⇡
 HX
h0=h
rh0(sh0 , ah0) sh = s, ah = a ,
for all h 2 [H]. Correspondingly, the value function V ⇡ h : S ! R of a policy ⇡ is defined as
V ⇡ h (s) = E⇡
 HX
h0=h
rh0(sh0 , ah0) sh = s = E⇡ ⇥ Q⇡ h (sh, a) sh = s ⇤ ,
for all h 2 [H]. Here the expectation E⇡[ · ] is taken over the trajectory generated by ⇡. Also, we let Q⇡
H+1 ⌘ 0 and thus V ⇡H+1 ⌘ 0. Furthermore, we denote by V ⇤h (s) the value function corresponding to the optimal policy ⇡⇤. Finally, for notational simplicity, we define [PhV ](s, a) = Es0⇠Ph(· | s,a)[V (s0)], where V : S ! R can be any function.
For any algorithm that generates a sequence of policies {⇡k}k2[K], we track its performance via the cumulative regret defined by
Regret(K) = KX
k=1
⇥ V ⇤1 (s k 1) V ⇡ k 1 (s k 1) ⇤ ,
where K is the number of episodes. Here sk1 is the initial state of episode k, which is arbitrarily chosen at the start of the episode.

heading: 3 Bootstrapped Value Iteration
text: In this section, we introduce Bootstrapped Value Iteration (BooVI in Algorithm 1). For notational simplicity, we write rh(skh, a k h ) as rk h throughout the rest of this paper. Also, in this paper, we write max{min{·, ·}, 0} as min{·, ·}+, and denote by k · k the 2-norm for vectors.
Least-Squares Value Iteration. At timestep h 2 [H] of episode k, given the estimated action-value function bQk
h+1(s ⌧ h+1, a) for all ⌧ 2 [k 1] and a 2 A, let bV kh+1(s⌧h+1) = maxa2A bQkh+1(s⌧h+1, a). Then, Least-Squares Value Iteration (LSVI) updates the parameter ! of the action-value function via
b!k h argmin
!2Rd
⇢ · k!k2 + k 1X
⌧=1
r⌧ h + bV k h+1(s ⌧ h+1) Q(s⌧h, a⌧h;!) 2 , (3.1)
where Q(·, · ; ·) : S ⇥A⇥ Rd ! R is the parameterization of action-value function with ! 2 Rd being its parameter, and 0 is the regularization parameter. Although the deterministic parameter update by LSVI could exploit the historical data well, it has limited ability to address the exploration need in more challenging tasks.
Bootstrapped Value Iteration. To achieve guided exploration, we introduce BooVI (Algorithm 1), which uses bootstrapping to enforce the optimism of the estimated action-value function.
At the timestep h of episode k, given the current data buffer Dk h = {(s⌧ h , a⌧ h , r⌧ h , s⌧ h+1)}⌧2[k 1], which contains the data collected from the previous k 1 episodes, and the current bootstrapped state values {eV k
h+1(s ⌧ h+1)}⌧2[k 1], we define
y⌧ h = r⌧ h + eV k h+1(s ⌧ h+1), for all ⌧ 2 [k 1]. (3.2)
With p0(!) as prior of ! and p(y⌧h | (s⌧h, a⌧h),!) as the likelihood of y⌧h, the posterior of ! is given by
p ⇣ ! eV k
h+1(s ⌧ h+1) ⌧2[k 1],D k h
⌘ / p0(!) · k 1Y
⌧=1
p y⌧ h (s⌧ h , a⌧ h ),! . (3.3)
In BooVI (Algorithm 1), we propose to sample repeatedly from such posterior for Nk times, which is equivalent to sampling repeatedly from randomized action-value function since each sample !k,i
h
corresponds to one randomized action-value function Q(·, ·;!k,i h ). Such a collection of posterior weights is later used to 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 !(t+ 1) !(t) + !(t), where
!(t) = ✏t 2 · ✓ r! log p0 !(t) + k 1X
⌧=1
r! log p y⌧ h (s⌧ h , a⌧ h ),!(t) ◆ + ⌘t, (3.4)
where ✏t > 0 is the stepsize, and ⌘t ⇠ N (0, ✏t). We note here that, after running sufficient many iterations with suitable choices of stepsizes ✏t > 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, we consider Gaussian prior and likelihood as an example. For the Gaussian prior ! ⇠ N (0, Id) and the Gaussian likelihood p(y⌧
h | (s⌧ h , a⌧ h ),!) / exp{ (y⌧ h Q(s⌧ h , a⌧ h ;!))2/(2 2)}, the posterior of ! is given by
p ⇣ ! eV k
h+1(s ⌧ h+1) ⌧2[k 1],D k h
⌘ / exp ⇢ 1 2 · k!k2 1 2 2 k 1X
⌧=1
y⌧ h Q(s⌧ h , a⌧ h ;!)
2 , (3.5)
where > 0 is an absolute constant. In this case, the maximum a posteriori (MAP) estimate of ! coincides with the weight estimate b!k
h obtained by LSVI. Such observation suggests that sampling
from the posterior distribution p(! | {eV k h+1(s ⌧
h+1)}⌧2[k 1],Dkh) would allows us to both achieve exploitation based on the available data, and generate noise for randomized exploration. More specifically, the !(t) in (3.4) takes the form of
!(t) = ✏t 2 ·  !(t) + 1 2 k 1X
⌧=1
⇣ y⌧ h Q s⌧ h , a⌧ h ;!(t) ⌘ ·r!Q s⌧ h , a⌧ h ;!(t) + ⌘t,
which can be viewed as using stochastic gradient descent to solve for the LSVI update (3.1) with = 2 and bV k
h+1 replaced by eV kh+1. See also in Lemma E.1 for the closed form of the posterior in a 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 1 Bootstrapped Value Iteration (BooVI)
1: Require: MDP (S,A, H,P, r), action-value function parameterization Q(·, · ; ·) : S ⇥ A ⇥ Rd ! R, number of episodes K, number of posterior weights {Nk}k2[K], lower and upper bootstrapping ratios ↵, 2 (0, 1) 2: Initialize the data buffer D1 h {} for h 2 [H] 3: For episode k = 1, . . . ,K do 4: Set Nk,↵ d↵ ·Nke,Nk, b ·Nkc, and !k,iH+1 0 for all i 2 [Nk] 5: Sample nk uniformly from {Nk,↵, Nk,↵ + 1, . . . , Nk, } 6: For timestep h = H, . . . , 1 do 7: Generate eQk
h+1(s ⌧ h+1, a) using Algorithm 2 with weights {! k,i h+1}i2[Nk] and parameter nk for all a 2 A and ⌧ 2 [k 1]
8: eV k h+1(s ⌧ h+1) maxa2A eQkh+1(s⌧h+1, a) for all ⌧ 2 [k 1] 9: Independently sample {!k,i
h }i2[Nk] from the posterior p(! | {eV kh+1(s⌧h+1)}⌧2[k 1],Dkh)
defined in (3.3), e.g., using Langevin dynamics in (3.4) 10: end 11: For timestep h = 1, . . . , H do 12: Generate eQk
h (sk h , a) using Algorithm 2 with weights {!k,i h }i2[Nk] and parameter nk for
all a 2 A 13: Take action ak
h argmax a2A eQk h (sk h , a), and observe rk h and sk h+1
14: Update the data buffer Dk+1 h Dk h [ {(sk h , ak h , rk h , sk h+1)} 15: End 16: End
The following Algorithm 2 serves as the critical building block of BooVI for enforcing the optimism of the estimated action-value. At episode k in BooVI, for any (s, a) 2 S ⇥A, Algorithm 2 ranks the estimated action-value functions corresponding to the posterior sample obtained in Line 1 of Algorithm 1 in ascending order. Then, in order to enforce the optimism of the estimated action-value function, Algorithm 2 resamples the nk-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 a tunable parameter ⌫ > 1.
Algorithm 2 Bootstrapping Action-Value Function
1: Require: Action-value function parameterization Q(·, · ; ·) : S⇥A⇥Rd ! R, posterior sample {!k,i
h }i2[Nk], integer nk 2 [Nk], extrapolation parameter ⌫ > 1, and state-action pair (s, a)
2: Compute Qk,i h (s, a) Q(s, a;!k,i h ) for all i 2 [Nk] 3: Set bQk
h (s, a) (1/Nk)
P Nk
i=1 Q k,i h (s, a)
4: Rank {Qk,i h (s, a)}i2[Nk] in ascending order to obtain {Qk,(i)
h (s, a)}i2[Nk]
5: Output: eQk h (s, a) min{(1 ⌫) · bQk h (s, a) + ⌫ ·Qk,(nk) h (s, a), H h+ 1}+
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 = KH 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 1, the efficiency of such posterior sampling process is categorized as computational efficiency since it is purely based on the current data buffer Dk
h 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 to LSVI. (i) Posterior sampling vs. least-square minimization: Consider the Langevin dynamics in (3.4). Since posterior sampling replaces and admits similar steps as least-square minimization, the computational cost should not differ significantly between LSVI and BooVI. (ii) Computing bootstrapped Q-function: To compute bootstrapped Q-function, at each state-action pair,
the extra sorting takes O(Nk logNk) time complexity, which makes the action selection procedure O(Nk logNk) times slower. In addition, keeping Nk posterior weights takes O(d ·Nk) memory. We note that, although the requirement on Nk in our subsequent analysis is large, we should be able to use much smaller Nk in practice due to the pessimistic nature of the analysis. See Appendix F for illustrative experiment results.
It is worth mentioning that BooVI is applicable to any specific parameterization Q(·, · ; ·) : S ⇥A⇥ Rd ! R 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.

heading: 4 Main Results
text: While BooVI (Algorithm 1) is generally applicable to different parameterizations of the action-value function, we establish its regret for a class of linear MDPs.
Linear Markov Decision Process. We consider a class of MDPs, where the transition kernels and the reward functions are linear in the same feature mapping. Specifically, we have the following definition. Definition 4.1 (Linear MDP). An MDP (S,A, H,P, r) is called a linear MDP with feature mapping : S ⇥A! Rd, if for any h 2 [H], there exists d unknown signed measures µh = (µ(1)h , . . . , µ (d) h
) over S and an unknown vector ✓h 2 Rd, such that for any (s, a) 2 S ⇥A, we have
Ph(· | s, a) = ⌦ (s, a), µh(·) ↵ , rh(s, a) = ⌦ (s, a), ✓h ↵ . (4.1)
See [51, 52, 24] for examples of such a class of linear MDPs. Specifically, examples include tabular MDPs where d = SA and the feature mapping is the canonical basis (s, a) = e(s,a), and the simplex feature space where the feature space { (s, a) | (s, a) 2 S ⇥ A} is a subset of the d-dimensional simplex. See also [14, 44, 25] for related discussions on such a linear representation. For notational simplicity, we write the feature (sk
h , ak h ) as k h throughout the rest of this paper.
Based on Definition 4.1, without loss of generality, we make the following assumption. Assumption 4.2. The MDP (S,A, H,P, r) is a linear MDP with k (s, a)k  1 for all (s, a) 2 S⇥A and max{kµh(S)k, k✓hk}  p d for all h 2 [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 a linear MDP, for any policy ⇡ and h 2 [H], there exists !⇡
h 2 Rd such that for all (s, a) 2 S ⇥ A, we have
Q⇡ h (s, a) = h (s, a),!⇡ h i.
Regret of BooVI for Linear MDPs. For a linear MDP, by Proposition 4.3, the parameterization Q(·, · ; ·) : S ⇥ A ⇥ Rd ! R in BooVI should take the form of Q(s, a;!) = h (s, a),!i, where ! 2 Rd. Furthermore, when the prior and the likelihood are Gaussian, the posterior of ! is Gaussian distribution with mean being is the weight update by LSVI with chioce of = 2.
For any bootstrapping ratio q 2 (0, 1), we write Cq = 1(q) 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. We set = 1, ⌫ = dH , and fix a failure probability p 2 (0, 1]. Then there exists a sequence of posterior sample sizes {Nk}k2[K], and there exist absolute constants c > c↵ > 0, such that if Nk = O(d6T 4k/p4) for all k 2 [K], C↵ = c↵ · p ◆, and C = c · p ◆, BooVI (Algorithm 1) with Gaussian posterior in (3.5) satisfies
Regret(K) = O p d3H3T ◆2
with probability at least 1 p, where T = KH and ◆ = log(3dT/p).
Proof. See Section 5 for a proof sketch.

heading: 5 Proof Sketch
text: Notation. At episode k, given the number of posterior sample weights Nk and given nk sampled in Line 1 of Algorithm 1, we define Ck = 1(nk/Nk). At timestep h of episode k, further given posterior weights {!k,i
h }i2[Nk], corresponding to the bootstrapped action-value function eQkh generated
by Algorithm 2, we define the bootstrapped value function as
eV k h (s) = max a2A eQk h (s, a). (5.1)
Next, we define the mean bootstrapped action-value functions as
Q k
h (s, a) = min n E! ⇥ (1 ⌫) · bQk h (s, a) + ⌫ ·Qk,(nk) h (s, a) ⇤ , H h+ 1 o+ , (5.2)
where E![ · ] is taken over ! with respect to the posterior p(! | {eV kh+1(s⌧h+1)}⌧2[k 1],Dkh) defined in (3.3). Correspondingly, we define the mean bootstrapped value function as
V k
h (s) = max a2A Q
k h (s, a). (5.3)
Also, we denote by
!k h = (⇤k h ) 1
k 1X
⌧=1
y⌧ h · ⌧ h (5.4)
the mean of the posterior distribution p(! | {eV k h+1(s ⌧
h+1)}⌧2[k 1],Dkh), where y⌧h is defined in (3.2). For a fixed failure probability p 2 (0, 1], we write ◆ = log(3dT/p), where T = KH . Finally, we define matrix ⇤k
h 2 Rd⇥d by
⇤k h =
k 1X
⌧=1
⌧ h ( ⌧ h )> + 2 · Id. (5.5)
Concentration Events. Before proving Theorem 4.4, we first present two lemmas, each characterizing an event that is involved throughout the remaining proofs. The first lemma characterizes the concentration behavior of the bootstrapped action-value function eQk
h .
Lemma 5.1. Let = 1, ⌫ = dH , and C = c · p ◆ for some c > 0. For a fixed failure probability p 2 (0, 1], we define E as the event that the condition eQk
h (s, a) Qk h (s, a)
 c / p d+ 3 ·H p d◆/k
is satisfied for all (s, a, k, h) 2 S⇥A⇥ [K]⇥ [H]. Then, there exists a sequence of posterior sample sizes {Nk}k2[K] satisfying Nk = O(d6T 4k/p4) for all k 2 [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 V k
h .
Lemma 5.2. Let = 1, ⌫ = dH , and C = c · p ◆ for some constant c > 0. For a fixed failure p 2 (0, 1], we define E 0 as the event that the condition k 1X
⌧=1
⌧ h · V
k h+1(s ⌧ h+1) [PhV k h+1](s ⌧ h , a⌧ h ) (⇤kh) 1  C · dHp
is satisfied for all (k, h) 2 [K]⇥[H], where = log[3(1+c )dT/p)]. Then we have P(E 0) 1 p/3.
Proof. See Appendix D for a detailed proof.
Model Estimation Error. With the events E and E 0 ready, we can proceed to characterize the model estimation error ⇣k
h : S ⇥A! R for all (k, h) 2 [K]⇥ [H] defined as
⇣k h = Q
k h rh + [PhV k h+1] , (5.6)
which can be comprehended as the estimation error of the model at timestep h of episode k induced by the mean bootstrapped value function Q k
h+1. We have the following lemma charaterizing the model estimation error ⇣k
h defined in (5.6).
Lemma 5.3 (Model Estimation Error). Let d 2, ⌫ = dH , = 1, and p 2 (0, 1]. Then there exists a sequence of posterior sample sizes {Nk}k2[K], and there exist absolute constants c > c↵ > 0 such that, if Nk = O(d6T 4k/p4) for all k 2 [K], C↵ = c↵ · p ◆, and C = c · p ◆, for the model estimation error ⇣k h defined in (5.6), we under events E and E 0 that
0  ⇣k h (s, a)  (c↵ + c ) · dH
p ◆ q (s, a)>(⇤k
h ) 1 (s, a)
for all (s, a, k, h) 2 S ⇥A⇥ [K]⇥ [H].
Proof. Under Assumption 4.2, using (4.1) we have [PhV k h+1] = R S V k h+1(s 0) · h , µh(ds0)i. Then, with slight abuse of notation, we denote by V k h+1(µh) = R S V k h+1(s)µh(ds) 2 Rd and write
PhV k h+1 = ⌦ , (⇤k h ) 1(⇤k h )V k h+1(µh) ↵
= ⌧ , (⇤k
h ) 1
✓k 1X
⌧=1
⌧ h ( ⌧ h )>V k h+1(µh)
◆ + ⌦ , (⇤k
h ) 1V
k h+1(µh) ↵
= ⌧ , (⇤k
h ) 1
✓k 1X
⌧=1
⌧ h · [PhV
k h+1](s ⌧ h , a⌧ h )
◆ + ⌦ , (⇤k
h ) 1V
k h+1(µh) ↵ ,
where the second equality follows from (5.5). Thus, we have the following decomposition h ,!k
h i (rh + PhV
k h+1)  u1 + u2,
where !k h is defined in (5.4), and
u1 =
⌧ , (⇤k
h ) 1
k 1X
⌧=1
⌧ h · eV k h+1(s ⌧ h+1) [PhV k h+1](s ⌧ h , a⌧ h ) ,
u2 =
⌧ , (⇤k
h ) 1
✓k 1X
⌧=1
r⌧ h · ⌧ h V k h+1(µh) ◆ rh .
In the sequel, we upper bound u1 and u2 separately. Upper bounding u1: First, we further decompose u1 as ⌧ , (⇤k
h ) 1
⇢k 1X
⌧=1
⌧ h · h eV k h+1(s ⌧ h+1) V k h+1,(s ⌧ h+1) + V k h+1(s ⌧ h+1) [PhV k h+1](s ⌧ h , a⌧ h ) i ,
applying the Cauchy-Schwartz inequality to which we obtain
u1  ⌧ , (⇤k h ) 1 k 1X
⌧=1
⌧ h · eV k h+1(s ⌧ h+1) V k h+1(s ⌧ h+1)
(5.7)
+ q >(⇤k
h ) 1 ·
k 1X
⌧=1
⌧ h · V
k h+1(s ⌧ h , a⌧ h ) [PhV k h+1](s ⌧ h+1)
(⇤kh) 1 .
Now we proceed to upper bound the two terms on the right-hand side of (5.7) in the following. For the first term, since by Lemma 5.1 we have under event E that |eV k
h+1(s ⌧ h+1) V k h+1(s ⌧ h+1)|  (c / p d+ 3) ·H p d◆/k, we have
⌧ , (⇤k
h ) 1
k 1X
⌧=1
⌧ h · eV k h+1(s ⌧ h+1) V k h+1(s ⌧ h+1) 
c / p d+ 3 ·H p d◆/k k 1X
⌧=1
>(⇤k h ) 1 ⌧ h .
(5.8)
By the Cauchy-Schwartz inequality and Lemma D.1 in [24] (see Appendix E), we have k 1X
⌧=1
>(⇤k h ) 1 ⌧ h  ✓k 1X
⌧=1
>(⇤k h ) 1 ⌧ h
◆ · ✓k 1X
⌧=1
>(⇤k h ) 1
◆ 1/2  p d◆/k · p dk q >(⇤k
h ) 1 ,
taking which into (5.8) and gives
⌧ , (⇤k
h ) 1
k 1X
⌧=1
⌧ h · eV k h+1(s ⌧ h+1) V k h+1(s ⌧ h+1) 
c / p d+ 3 · dH p ◆ q
>(⇤k h ) 1 .
(5.9)
Taking (5.9) into (5.7) and applying Lemma 5.2 to the second term on the right-hand side of (5.7), we have under the events E and E 0 that
u1  h c / p d+ 3 · dH p ◆+ C · dHp i · q >(⇤k h ) 1 . (5.10)
Upper bounding u2: By (4.1), we have
u2 = D , (⇤k h ) 1 ✓h + V k h+1(µh) E .
Then, by the Cauchy-Schwartz inequality, we further obtain
u2  q >(⇤k h ) 1 · ⇣ V k h+1(µh)
(⇤kh)
1 + ✓h
(⇤kh) 1
⌘
 q >(⇤k
h ) 1 · ⇣ V k h+1(µh) + ✓h ⌘  2H p d · q >(⇤k h ) 1 , (5.11)
where the second inequality follows from ⇤k h ⌫ Id, and the last inequality follows from k✓hk 
p d
in Assumption (4.2) as well as the fact that V k
h+1(s)  H h  H 1 for all s 2 S . Combining (5.10) and (5.11), we obtain under event E that
h ,!k h i (rh + PhV
k h+1) .q >(⇤k h ) 1 (5.12)
 h c / p d+ 3 · dH p ◆+ C · dHp + 2H p d i  h c / p d+ 5 · dH p ◆+ C · dHp i = C 0 · dH p ◆,
where C 0 > 0 is an absolute constant. Next, we need to find an absolute constant c > 0 such that C 0 · p ◆ = (c / p d+ 5) · p ◆+ C · p ◆+ log(1 + c ) < c · p ◆. Note that d 2 and ◆ log 2, it suffices to pick a c > 0 such that
C · q log 2 + log(1 + c ) < h 1 1/ p 2 c 5 i · p log 2, (5.13)
which must exist as the left hand side grows logarithmically in c and the right-hand side grows linearly in c . For c > 0 satisfying (5.13), we pick any c↵ > 0 such that C 0  c↵ < c and let C↵ = c↵ · p ◆. By (5.12) and rh + [PhV k h+1]  H h+ 1, we obtain under events E and E 0 that
⇣k h = min
n h ,!k
h i+ Ck · ⌫ ·
q >(⇤k
h ) 1 , H h+ 1 o+ (rh + PhV k h+1)
min n (c↵ C 0) · dH p ◆ q >(⇤k h ) 1 , 0 o 0.
On the other hand, by (5.12), we also have under events E and E 0 that
⇣k h  h ,!k h i (rh + PhV
k h+1) + C · ⌫ · q >(⇤k h ) 1  (c↵ + c ) · dH p ◆ q >(⇤k h ) 1 .
Therefore, we finish the proof of Lemma 5.3.
As results of Lemma 5.3, we have the following two lemmas characterizing the optimism and the cumulative estimation error of the mean bootstrapped value function V k
h , respectively.
Lemma 5.4 (Optimistic Random Value Function). Let = 1 and ⌫ = dH . There there exists a sequence of posterior sample sizes {Nk}k2[K], and there exist absolute constants c > c↵ > 0, such that if Nk = O(d6T 4k/p4) for all k 2 [K], C↵ = c↵ · p ◆, and C = c · p ◆, we have under the events E and E 0 that KX
k=1
⇥ V ⇤1 (s k 1) V k 1(s k 1) ⇤  0.
Proof. See Appendix D for a detailed proof.
Lemma 5.5 (Cumulative Estimation Error). Let = 1, ⌫ = dH , and p 2 (0, 1]. There exists a sequence of posterior sample sizes {Nk}k2[K], and there exist absolute constants c > c↵ > 0, such that if Nk = O(d6T 4k/p4) for all k 2 [K], C↵ = c↵ · p ◆, and C = c · p ◆, we have under the events E and E 0 that KX
k=1
⇥ V k
1(s k 1) V ⇡ k 1 (s k 1) ⇤  p 18TH2 · log(3/p) + 4(c / p d+ 3) ·H2 p dK◆
+ (c↵ + c ) · dH2 p 2dK◆2,
with probability at least 1 p/3.
Proof. See Appendix D for a detailed proof.
Finally, the regret bound of BooVI for the class of linear MDPs can be established as a consequence of the optimism (Lemmas 5.4) and the upper bound of the cumulative estimation error (Lemma 5.5) of the bootstrapped value function.
Proof of Theorem 4.4. First, recall that we have V k
h (s) defined in (5.3). We have the regret decom-
position
Regret(K) = KX
k=1
⇥ V ⇤1 (s k 1) V k 1(s k 1) ⇤ +
KX
k=1
⇥ V k
1(s k 1) V ⇡ k 1 (s k 1) ⇤ . (5.14)
Applying Lemmas 5.4 and 5.5 to (5.14), we obtain under the events E and E 0 that
Regret(K)  0 + p 18TH2 · log(3/p) + 4(c / p d+ 3) ·H2 p dK◆
+ (c↵ + c ) · dH2 p 2dK◆2
= O p d3H3T ◆2
(5.15)
with probability at least 1 p/3. Finally, by Lemmas 5.1 and 5.2, we have with at least probability 1 p/3 p/3 = 1 2p/3 that the events E and E 0 hold simultaneously. Thus, we have (5.15) hold with probability at least 1 p, which concludes the proof.

heading: 6 Conclusion
text: 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 a data-driven manner is essential. Moreover, applicability to general environments is critical since reinforcement learning tasks are getting more chanlleging and complex recently. We aspire to 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 is mainly on algorithmic and theoretical aspects of the bootstrapping idea in RL, it would be interesting to see the empirical strength of BooVI in more challenging RL environments. We leave this part to our future work.

heading: Acknowledgement
text: 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).

Review summaries:
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.