Year: 2018

Abstract:
We propose Bayesian Deep Q-Networks (BDQN), a principled and a practical Deep Reinforcement Learning (DRL) algorithm for Markov decision processes (MDP). It combines Thompson sampling with deep-Q networks (DQN). Thompson sampling ensures efficient exploration-exploitation trade-off in high dimensions. It is typically carried out through posterior sampling over the model parameters, which makes it computationally expensive. To overcome this limitation, we directly incorporate uncertainty over the value (Q) function. Further, we only introduce randomness in the last layer (i.e. the output layer) of the DQN and use independent Gaussian priors on the weights. This allows us to efficiently carry out Thompson sampling through Gaussian sampling and Bayesian Linear Regression (BLR), which has fast closed-form updates. The rest of the layers of the Q network are trained through back propagation, as in a standard DQN. We apply our method to a wide range of Atari games in Arcade Learning Environments and compare BDQN to a powerful baseline: the double deep Q-network (DDQN). Since BDQN carries out more efficient exploration, it is able to reach higher rewards substantially faster: in less than 5M±1M interactions for almost half of the games to reach DDQN scores while a typical run of DDQN is 50-200M. We also establish theoretical guarantees for the special case when the feature representation is d-dimensional and fixed. We show that the Bayesian regret of posterior sampling RL (PSRL) and frequentist regret of the optimism in the face of uncertainly (OFU) after N time step are upper bounded by Õ(d √ N) which are tight up-to logarithmic factors. To the best of our knowledge, these are the first model free theoretical guarantee for continuous state-action space MDP, beyond the tabular setting.

text: We propose Bayesian Deep Q-Networks (BDQN), a principled and a practical Deep Reinforcement Learning (DRL) algorithm for Markov decision processes (MDP). It combines Thompson sampling with deep-Q networks (DQN). Thompson sampling ensures efficient exploration-exploitation trade-off in high dimensions. It is typically carried out through posterior sampling over the model parameters, which makes it computationally expensive. To overcome this limitation, we directly incorporate uncertainty over the value (Q) function. Further, we only introduce randomness in the last layer (i.e. the output layer) of the DQN and use independent Gaussian priors on the weights. This allows us to efficiently carry out Thompson sampling through Gaussian sampling and Bayesian Linear Regression (BLR), which has fast closed-form updates. The rest of the layers of the Q network are trained through back propagation, as in a standard DQN. We apply our method to a wide range of Atari games in Arcade Learning Environments and compare BDQN to a powerful baseline: the double deep Q-network (DDQN). Since BDQN carries out more efficient exploration, it is able to reach higher rewards substantially faster: in less than 5M±1M interactions for almost half of the games to reach DDQN scores while a typical run of DDQN is 50-200M. We also establish theoretical guarantees for the special case when the feature representation is d-dimensional and fixed. We show that the Bayesian regret of posterior sampling RL (PSRL) and frequentist regret of the optimism in the face of uncertainly (OFU) after N time step are upper bounded by Õ(d √ N) which are tight up-to logarithmic factors. To the best of our knowledge, these are the first model free theoretical guarantee for continuous state-action space MDP, beyond the tabular setting.

heading: 1 INTRODUCTION
text: One of the central challenges in reinforcement learning (RL) is to design efficient explorationexploitation trade-off that also scales to high-dimensional state and action spaces. Recently deep RL has shown good promise in being able scale to high-dimensional (continuous) spaces. These successes are mainly demonstrated in simulated domains where exploration is considered to be inexpensive and simple exploration strategies are deployed, e.g. ε-greedy which uniformly explores over all the actions with ε probability. Such exploration strategies inherently inefficient for complex high-dimensional environments. On the other hand, more sophisticated strategies have mostly been limited to low dimensional MDPs. For example, OFU is only practical when the domain is small enough to be represented with lookup tables for the Q-values (Jaksch et al., 2010; Brafman & Tennenholtz, 2003).
An alternative to optimism-under-uncertainty is Thompson Sampling (TS), a general sampling and randomization approach (in both frequentist and Bayesian settings) (Thompson, 1933). Under the Bayesian framework, Thompson sampling maintains a prior distribution over the environmental models (i.e. models of reward and dynamics), and updating the posterior based on observations collected. An action is chosen from the posterior distribution, the belief, such that it maximizes the expected return. Thompson sampling has been observed to work significantly better than optimistic approaches in many low dimensional settings such as contextual bandits (Chapelle & Li, 2011), small MDPs (Osband et al., 2013) and also has strong theoretical bounds (Russo & Van Roy, 2014a;b; Agrawal & Goyal, 2012; Osband et al., 2013; Abbasi-Yadkori & Szepesvári, 2015).
In the MDP setting, (model-based) Thompson Sampling involves sampling the parameters of reward and dynamics models, performing MDP planning using the sampled model and then computing the policy (Strens, 2000; Osband et al., 2013; Osband & Van Roy, 2014b;a). However, the computational costs of posterior sampling and planning scales as cubic in the problem dimension, which makes it intractable for large MDPs. Therefore, some form of function approximation is required to scale Thompson Sampling to high dimensions, and this can be either of the model, the Q-value function, or the policy. To address this, Osband et al. (2014) introduced randomized least-squares value iteration (RLSVI) which combines linear value function approximation with Bayesian regression to directly sample the value-function weights from a distribution. The authors prove a regret bound for this approach in tabular MDPs. This has been extended to continuous spaces by Osband et al. (2016), where deep networks are used to approximate the Q function. Through a bootstrapped-ensemble approach, several deep-Q network (DQN) models are trained in parallel to approximate the posterior distribution. Other works use the posterior distribution over the parameters of each node in the network and employ variational approximation (Lipton et al., 2016b) or use noisy networks (Fortunato et al., 2017). These approaches significantly increase the computation cost compared to the standard DQN. For instance, the bootstrapped-ensemble incurs a computation overhead that is linear in the number of bootstrap models. Moreover, despite principled design of the methods in the above works, they only produced modest gains over DQN in empirical studies.
Contribution 1 – Design of BDQN: We introduce Bayesian Deep Q-Network (BDQN), a Thompsonsampling algorithm for deep RL. It is a simple approach that extends randomized least-squares value iteration (Osband et al., 2014) to deep networks. We introduce stochasticity only in the last layer of the Q-network using independent Gaussian priors on the weights. This allows us to do efficient approximate Thompson sampling1 using Bayesian linear regression (BLR), which has fast closedform updates and sampling from the resulting posterior distribution. The rest of the Q-network is trained through usual back propagation.
Contribution 2 – Strong empirical results for BDQN: We test BDQN on a wide range of Atari games (Bellemare et al., 2013; Machado et al., 2017), and compare our results to a powerful baseline: Double DQN (DDQN) (Van Hasselt et al., 2016) a bias-reduced extension of DQN. BDQN and DDQN use the same network architecture, and follow the same target objective, and differ only in the way they select actions: DDQN uses ε-greedy exploration while BDQN performs (approximate) Thompson sampling.
We found that BDQN is able to reach much higher cumulative rewards, and also at a higher speed, compared to DDQN on all the tested games. We also found that BDQN can be trained with much higher learning rates compared to DDQN. This is intuitive since BDQN has better exploration strategy. The cumulative reward (score) for BDQN at the end of training improves by a median of 300% with a maximum of 80K% in these games. Also, BDQN has 300%± 40% (mean and standard deviation) improvement over these games on area under the performance measure. This can be considered as a surrogate for sample complexity and regret. Indeed, no single measure of performance provides a complete picture of an algorithm, and we present detailed experiments in Section 5.
In terms of computational cost, BDQN is only slightly more expensive compared to DQN and DDQN. For the DQN in Atari games, this is the cost of inverting a 512× 512 matrix every 100,000 time steps, which is negligible. On the other hand, more sophisticated Bayesian RL techniques are significantly more expensive and have not lead to large gains over DQN and DDQN (Osband et al., 2016).
Contribution 3 – Tight Bayesian and frequentist regret upper bounds for continuous MDPs: We establish theoretical guarantees for the special case when the feature representation is fixed (i.e. all layers except the last), and not learnt. We consider episodic MDPs with continuous space of states and actions such that the Q-function is a linear function of a given d-dimensional feature map. We show that when PSRL and OFUare deployed, respectively, the Bayesian regret and frequentist regret after N time step are upper bounded by Õ(d √ N), which is shown to be tight up-to logarithmic factors. Since linear bandits are a special case of episodic continuous MDPs (with horizon length 1), it implies that our regret bounds are tight in the dimension d and in the number of episodes. The Bayesian bound matches the Bayesian regret bound of linear bandits (Russo & Van Roy, 2014a) and the frequentist bound matches the frequentist regret bound for linear bandits (Abbasi-Yadkori
1BDQN approximates the posterior resulting in approximating Thompson sample. In the remaining, we state Thompson Sampling and its approximation as Thomson samples unless we specify.
et al., 2011). To the best of our knowledge, these are the first model free theoretical guarantee for continuous MDPs beyond the tabular setting.
Thus, our proposed approach has several desirable features – faster learning and better sample complexity due to targeted exploration, negligible computational overhead due to simplicity, significant improvement in experiments, and tight theoretical bounds.
2 THOMPSON SAMPLING VS ε-GREEDY AND BOLTZMANN EXPLORATION
In a value approximation RL algorithm, there are different ways to manage the explorationexploitation trade-off. DQN uses a naive ε-greedy for exploration, where with ε probability it chooses a random action and with 1− ε probability it chooses the greedy action based on the estimated Q function. Note that there are only point estimates of the Q function in DQN. In contrast, our proposed Bayesian approach BDQN maintains uncertainties over the estimated Q function, and employs it to carry out Thompson Sampling based exploration. Here, we demonstrate the fundamental benefits of Thompson Sampling over ε-greedy and Boltzmann exploration strategies using simple examples. In Table 1, we list the three strategies and their properties.
ε-greedy is the simplest exploration strategy since it is uniformly random over all the non-greedy actions. Boltzmann exploration is an intermediate strategy since it uses the estimated Q function to sample the actions. However, it does not maintain uncertainties over the Q function estimation. In contrast, Thompson sampling also incorporates uncertainties over Q estimation and utilizes most information for exploration strategy.
Consider the example in Figure 1(a) with current estimates and uncertainties of the Q function over different actions. ε-greedy is wasteful since it assigns uniform probability to explore over 5 and 6, which are obviously sub-optimal when the uncertainty estimates are available. In this setting, a possible remedy is Boltzmann exploration since it assigns lower probability to actions 5 and 6 but randomizes with almost the same probabilities over the remaining actions.
However, Boltzmann exploration is sub-optimal in settings where there is high variances. For example if the current Q estimate is according to Figure 1(b), then Boltzmann exploration assigns almost equal probability to actions 5 and 6, even though action 6 has much higher uncertainty and needs to be explored more. Thus, both ε-greedy and Boltzmann exploration strategies are sub-optimal since they do not maintain an uncertainty estimate over the Q function estimation. In contrast, Thompson sampling uses both estimated Q function and its uncertainty estimates to carry out the most efficient exploration.

heading: 3 BAYESIAN DEEP Q-NETWORKS
text: Consider an MDP M as a tuple 〈X ,A, P, P0, R, γ〉, with state space X , action space A, transition kernel P , initial state distribution P0, accompanied with reward function of R, and discount factor 0 ≤ γ < 1. In value based model free RL, the core of most prominent approaches is to learn the Q-function through minimizing the Bellman residual (Lagoudakis & Parr, 2003; Antos et al., 2008)
L(Q) = Eπ [ (Q(x, a)− r − γQ(x′, â))2 ] (1)
and temporal difference (TD) update (Tesauro, 1995) where the tuple (x, a, r, x′) consists of a consecutive experiences under a behavior policy π. Mnih et al. (2015) carries the same idea, and propose DQN where the Q-function is parameterized by a deep network and â = arg maxa′ Q(x′, a′). In order to reduce the bias of the estimator, DQN utilizes a target network Qtarget, target value
Algorithm 1 BDQN 1: Initialize θ, θtarget, wa, wtargeta , Cova ∀a, and B 2: for episode = 1,2,3. . . do 3: for t = 1 to the end of episode do 4: Draw sample wa ∼ N (wtargeta , Cova) ∀a every T sample 5: Set θtarget ← θ every T target 6: Update wtargeta and Cova, ∀a using B experiences every TBayes target 7: Execute at = arg maxa′w > a′φθ(xt), observe reward rt, successor State xt+1
8: Store transition (xt, at, rt, xt+1) in the replay buffer 9: Sample a random minibatch of transitions (xτ , aτ , rτ , xτ+1) from replay buffer 10: yτ← { rτ terminal xτ+1 rτ+w target â > φθtarget(xτ+1), â := arg maxa′w > a′φθ(xτ+1)non-terminal xτ+1 } 11: θ ← θ − η · ∇θ(yτ − w>aτφθ(xτ )) 2
y = r + γQtarget(x′, â), and approaches the regression on the empirical estimates of the loss L(Q,Qtarget);
L(Q,Qtarget) = Eπ [ (Q(x, a)− y)2 ] (2)
i.e., L̂(Q,Qtarget). A DQN agent, once in a while updates the Qtarget network and sets it to the Q network, follows the regression in Eq.2 with the new target value and provides a biased estimator of the target. To mitigate the bias in this estimator, Van Hasselt et al. (2016) proposes DDQN and instead use â = arg maxa′ Qtarget(x′, a′). We deploy this approach for the rest of this paper.
DQN architecture consists of a deep neural network where the Q-function is approximated as a linear function of the feature representation layer φθ(x) ∈ Rd parametrized by θ, i.e., for all pairs of state-action ∀a ∈ A, x ∈ X , we have Q(x, a) = φθ(x)>wa with wa ∈ Rd, the output layer. Consequently, the target model has the same architecture as the Q, and consists of φθ target
(·) ∈ Rd, the feature representation of target network, and wtargeta, ∀a ∈ A the target weight. For a given tuple of experiences (x, a, r, x′), and â = arg maxa′φ θtarget > wtargeta′
Q(x, a) = φθ(x) > wa → y := r + γφθ target (x′)wtargetâ
The regression in Eq. 2 induces linear regression in the learning of the output layer, i.e., wa’s. In this work, we utilize the DQN architecture and instead propose to use BLR (Rasmussen & Williams,
2006) in learning of the output layer. Through BLR, we efficiently approximate the distribution over the Q-values, capture the uncertainty over the Q-fucntion estimation, and design a efficient exploration and exploitation strategy using Thompson Sampling.
By deploying BLR on the feature representation layer, we approximate the posterior distribution of each wa, resulting in the posterior distribution of the Q-function. As in BLR methods, we maintain a Gaussian prior N (0, σ2I) with the target value y ∼ w>a φθ(x) + for each weight vector where ∼ N (0, σ2 ) is an i.i.d. Gaussian noise.
Given a experience replay buffer D = {xτ , aτ , yτ}Dτ=1, we construct |A| (number of actions) disjoint datasets Da for each action with aτ = a. For each action a, we construct a matrix Φθa ∈ Rd×|Da|, the concatenation of feature vectors {φθ(xi)}|Da|i=1 , and ya ∈ R|Da|, the concatenation of target values in setDa. Finally, we approximate the posterior distribution of wa as follows:
wa ∼ N (wa, Cova) , wa := 1
σ2 CovaΦ
θ aya, Cova :=
( 1
σ2 ΦθaΦ θ a
> + 1
σ2 I
)−1 (3)
Fig. 2 expresses that the covariance matrix induces an ellipsoid around the estimated mean of the approximated posterior and samples drawn through Thompson Sampling are mainly close to this mean. A sample of Q(x, a) is w>a φθ(x) where wa is drawn from the posterior distribution Fig. 2. In BDQN, every T sample times step, we draw a new wa, ∀a ∈ A and follow the resulting policy, i.e., aTS := maxa w > a φθ(x). We simultaneously train the feature network under the loss (yτ − w>aτφθ(xτ )) 2 with xτ , aτ , yτ experiences from the replay buffer i.e.
θ ← θ − η · ∇θ(yτ − [ w>aτφθ(xτ ) ] aτ )2 (4)
We update the target network every T target steps and set θtarget to θ. With the period of TBayes target, we update the posterior distribution using a minibatch of B randomly chosen experiences in the replay buffer, and set the wtargeta = wa, ∀a ∈ A which is the mean of the posterior distribution( more details in Section A.5. We describe BDQN algorithm in Alg. 1.

heading: 4 BAYESIAN REGRET BOUND
text: Algorithm 2 PSRL 1: Input: the prior and likelihood 2: for episode t= 1,2,. . . do 3: ωt ∼ posterior distribution 4: for h = 0 to the end of episode do 5: Follow πt policy induced by ωt 6: Update the posterior
Algorithm 3 OFU 1: Input: σ, λ and δ 2: for episode = 1,2,. . . do 3: choose optimistic π̃t in Ct−1(δ) 4: for h = 1 to the end of episode do 5: Follow π̃t policy 6: Update the confidence Ct(δ)
In this section we provide the analysis of Bayesian regret upper bound of PSRL Alg. 2 and frequentis regret upper bound of optimism Alg. 3 when the feature representation is given and fixed. Consider a finite horizon stochastic MDP M := 〈X ,A, P, P0, R, γ,H〉, an MDP with horizon length H and 0 ≤ γ ≤ 1. We consider a class of MDPs where the optimal Q-function is a linear transformation of φ(·, ·) := X × A → Rd, i.e., Qω∗π∗ (x, a) := φ(x, a)>ω∗, ∀x, a ∈ X × A, where ω∗ ∈ Rd and π∗ : X → A as π∗(x) := arg maxa∈AQω ∗ π∗ (x, a). Let V ω∗
π∗ denote the corresponding value function. The following is the generative model of the environment;
R := ΨR = Φ(x{1:H}, a{1:H})ω∗+Ψν(x{1:H}, a{1:H}), where , Ψ :=  1 γ γ2 . . . γH−1
0 1 γ . . . γH−2 ... . . . . . . . . .
... 0 . . . . . . . . . 1

The vector R ∈ RH is the random vector of rewards in an episode and R ∈ RH the corresponding per step return. x{1:H}, a{1:H} is the sequence of states and actions, the matrix Φ(x{1:H}, a{1:H}) ∈ RH×d is row-wise concatenation of their features and ν(x{1:H}, a{1:H}) ∈ Rd the noise. Alg. 2 maintains a prior over the vector ω∗ and updating the posterior over time. At the beginning of an episode t, the agent draws ωt from the posterior, and follows its induced policy πt where a := arg maxa∈A φ
>(x, a)ωt,∀x ∈ X . Alg. 3, at the beginning of t’th episode, exploits the so-far collected samples and estimates ω∗ up to a high probability confidence interval Ct−1 i.e., ω∗ ∈ Ct with high probability. At each time step h, given a state xht , the agent follows the optimistic policy; π̃t(x h t ) = arg maxa∈Amaxω∈Ct−1 φ
>(Xht , a)ω. Through exploration and exploitation, we show that the confidence set Ct shrinks with the rate of Õ ( 1/ √ t )
resulting in less and less per step regret (Lemma 1 in Appendix B). Similar to the linear bandit (Abbasi-Yadkori et al., 2011), consider the following generic assumptions,
• The noise vector ν is sub-Gaussian vector with parameter σ. (Assumption 1 in Appendix B) • ‖ω∗‖2 ≤ Lω and trace ( Φ(·)Φ(·)> ) ≤ L, a.s.
• Maximum expected cumulative reward of an episode condition on the states of that episode is in [0, 1].
For any prior and likelihood satisfying the mentioned assumptions, we have;
Theorem 1 (Bayesian Regret). For an episodic MDP with episode length H , γ = 1, feature mapping φ(x, a) ∈ Rd, the Thompson sampling on ω, Alg. 2, after T episodes, guarantees;
BayesRegT : = E [ T∑ t [ V ω ∗ π∗ − V ω ∗ π̃t ]] = O ( d √ TH log(T ) )
Proof is Appendix B.2. Note that N = TH is the number of agent-environment interactions.
Theorem 2 (Frequentist Regret). For an episodic MDP with episode length H , γ = 1, feature mapping φ(x, a) ∈ Rd, the optimism on ω, Alg. 3, after T episodes, guarantees;
RegT : = E [ T∑ t [ V ω ∗ π∗ − V ω ∗ π̃t ] |ω∗ ] = O ( d √ TH log(T ) )
Proof is given in the Appendix B.1. Remark 1. For any discount factor γ, 0 ≤ γ ≤ 1, both theorems 1 and 2 hold if we replace √ H with a smaller constant ‖[1, γ, γ2, . . . , γH−1]‖2 in the theorem statements (see Section B.3).
These bounds are similar to those in linear bandits (Abbasi-Yadkori et al., 2011; Russo & Van Roy, 2014a) and linear quadratic control (Abbasi-Yadkori & Szepesvári, 2011), i.e. Õ(d √ T ). Since for H = 1, this problem reduces to linear bandit and for linear bandit the lower bound is Ω(d √ T ) therefore, our bound is order optimal in d and T .

heading: 5 EXPERIMENTS
text: We apply BDQN on a variety of Atari games using the Arcade Learning Environment (Bellemare et al., 2013) through OpenAI Gym2 (Brockman et al., 2016). As a baseline, we run the DDQN algorithm and evaluate BDQN on the measures of sample complexity and score. All the implementations are coded in MXNet framework (Chen et al., 2015). The details on architecture, Appendix A.1, learning rate Appendix A.3, computation A.4. In Appendix A.2 we describe how we spend less than two days on a single game for the hyper parameter choices which is another evidence of significance of BDQN.
2Each input frame is a pixel-max of the two consecutive frames. We detailed the environment setting in the implementation code
Baselines: We implemented DDQN and BDQN exactly the same way as described in Van Hasselt et al. (2016). We also attempted to implement a few other deep RL methods that employ strategic exploration, e.g., (Osband et al., 2016; Bellemare et al., 2016). Unfortunately we encountered several implementation challenges where neither code nor the implementation details was publicly available. Despite the motivation of this work on sample complexity, since we do not have access to the performance plots of these methods, the least is to report their final scores. To try to illustrate the performance of our approach we instead, extracted the best reported scores from a number of state-of-the-art deep RL methods and include them in Table 2, which is the only way to bring a comparison. We compare against DDQN, as well as DDQN+ which is the reported scores of DDQN in Van Hasselt et al. (2016) at evaluation time where the ε = 0.001. Furthermore, we compared against scores of Bootstrap DQN (Osband et al., 2016), NoisyNet (Fortunato et al., 2017), CTS, Pixel, Reactor (Ostrovski et al., 2017) which are borrowed from the original papers. For NoisyNet, the scores of NoisyDQN are reported. We also provided the sample complexity, SC: the number of interactions BDQN requires to beat the human score (Mnih et al., 2015)(“− ” means BDQN could not beat human score) and SC+: the number of interactions the BDQN requires to beat the score of DDQN+. Note that these are not perfect comparisons, as there are additional details that are not included in the papers, i.e. it is hard to just compare the reported results (an issue that has been discussed extensively recently, e.g. (Henderson et al., 2017)).4. Moreover, when the regret analysis of an algorithm is considered, no evaluation phase required, and the reported results of BDQN are those while exploration. It is worth noting that, the scores during evaluation are much higher than those during the exploration and exploitation period, Appendix A.8.
Results: The results are provided in Fig. 3. We observe that BDQN significantly improve the sample complexity of DDQN and reaches the highest score of DDQN in much fewer number of interactions than DDQN needs. We expected BDQN, due to it better exploration-exploitation strategy, to improve the regret and enhance the sample complexity, but we also observed a significantly improvement in scores. It worth noting that since BDQN is designed to minimize the regret, and the study in Fig. 3 also for sample complexity analysis, either of the reported BDQN and DDQN scores are while
4To further reproducibility, we released our codes and trained models. Since DRL experiments are expensive, we also have released the recorded arrays of returns. We also implemented bootstrapped DQN (Osband et al., 2016) and released the code but we were not able to reproduce their results beyond the performance of random policy
exploration. For example, DDQN gives score of 18.82 during the learning phase, but setting ε to zero, it mostly gives the score of 21. In addition to the Table 2, we also provided the score ratio as well area under the performance plot ratio comparisons in Table 3.
For the game Atlantis, DDQN+ gives score of 64.67k during the evaluation phase, while BDQN reaches score of 3.24M after 20M interactions. As it is been shown in Fig. 3, BDQN saturates for Atlantis after 20M interactions. We realized that BDQN reaches the internal OpenAIGym limit of max episode, where relaxing it improves score after 15M steps to 62M , Appendix A.7. We observe that BDQN immediately learns significantly better policies due to its efficient explore/exploit in a much shorter period of time. Since BDQN on game Atlantis promise a big jump around time step 20M , we ran it five more times in order to make sure it was not just a coincidence Appendix A.7 Fig. 7. For the game Pong, we ran the experiment for a longer period but just plotted the beginning of it in order to observe the difference. Due to cost of deep RL methods, for some games, we run the experiment until a plateau is reached.

heading: 6 RELATED WORK
text: The complexity of the exploration-exploitation trade-off has been deeply investigated in RL literature for both continuous and discrete MDPs (Kearns & Singh, 2002; Brafman & Tennenholtz, 2003; Asmuth et al., 2009; Kakade et al., 2003; Ortner & Ryabko, 2012). Jaksch et al. (2010) investigates the regret analysis of MDPs with finite state and action where Optimism in Face of Uncertainty (OFU) principle is deployed to guarantee a regret upper bound, while Ortner & Ryabko (2012) relaxes it to a continuous state space and propose a sublinear regret bound. Azizzadenesheli et al. (2016a) deploys OFUand propose a regret upper bound for Partially Observable MDPs (POMDPs) using spectral methods (Anandkumar et al., 2014). Furthermore, Bartók et al. (2014) tackles a general case of partial monitoring games and provides minimax regret guarantee. For linear quadratic models OFU is deployed to provide an optimal regret bound (Abbasi-Yadkori & Szepesvári, 2011).
In multi-arm bandit, there are compelling empirical pieces of evidence that Thompson Sampling sometimes provides better results than optimism-under-uncertainty approaches (Chapelle & Li, 2011), while also the performance guarantees are preserved (Russo & Van Roy, 2014a; Agrawal & Goyal, 2012). A natural adaptation of this algorithm to RL, posterior sampling RL (PSRL) Strens (2000) also shown to have good frequentist and Bayesian performance guarantees (Osband et al., 2013; Abbasi-Yadkori & Szepesvári, 2015).
Even though the theoretical RL addresses the exploration and exploitation trade-offs, these problems are still prominent in empirical reinforcement learning research (Mnih et al., 2015; Abel et al., 2016; Azizzadenesheli et al., 2016b). On the empirical side, the recent success in the video games has sparked a flurry of research interest. Following the success of Deep RL on Atari games (Mnih et al., 2015) and the board game Go (Silver et al., 2017), many researchers have begun exploring practical
applications of deep reinforcement learning (DRL). Some investigated applications include, robotics (Levine et al., 2016), self-driving cars (Shalev-Shwartz et al., 2016), and safety (Lipton et al., 2016a). Inevitably for PSRL, the act of posterior sampling for policy or value is computationally intractable with large systems, so PSRL can not be easily leveraged to high dimensional problems (Ghavamzadeh et al., 2015; Engel et al., 2003; Dearden et al., 1998; Tziortziotis et al., 2013). To remedy these failings Osband et al. (2017) consider the use of randomized value functions. For finite state-action space MDP, Osband et al. (2014) propose posterior sampling directly on the space of Q-functions and provide a strong Bayesian regret bound guarantee. To approximate the posterior, they use BLR on one-hot encoding of state-action and improve the computation complexity of PSRL. The approach deployed in BDQN is strongly related and similar to this work, and is a generalization to continues state-action space MDPs.
To combat the computational and scalability shortcomings, Osband et al. (2016) suggests a bootstrapped-ensemble approach that trains several models in parallel to approximate the posterior distribution. Other works suggest using a variational approximation to the Q-networks (Lipton et al., 2016b) or a concurrent work on noisy network (Fortunato et al., 2017). However, most of these approaches significantly increase the computational cost of DQN and neither approach produced much beyond modest gains on Atari games. Interestingly, the Bayesian approach as a technique for learning a neural network has been deployed for object recognition and image caption generation where its significant advantage has been verified Snoek et al. (2015).
Concurrently, Levine et al. (2017) proposes least squares temporal difference which learns a linear model on the feature representation in order to estimate the Q-function while ε-greedy exploration is employed and improvement on 5 tested Atari games is provided. Out of these 5 games, one is common with our set of 15 games which BDQN outperform it by factor of 360% (w.r.t. the score reported in their paper). As motivated by theoretical understanding, our empirical study shows that performing Bayesian regression instead, and sampling from the result, can yield a substantial benefit, indicating that it is not just the higher data efficiency at the last layer, but that leveraging an explicit uncertainty representation over the value function is of substantial benefit.
Drop-out, as another randomized exploration method is proposed by Gal & Ghahramani (2016) but Osband et al. (2016) investigates the sufficiency of the estimated uncertainty and hardness in driving suitable exploitation out of it. We also implemented the dropout version of DDQN and compared its performance against BDQN, DDQN, DDQN+, and the random policy (the policy which chooses actions uniformly at random) but did not observe much gain beyond the performance of the random policy (See section A.6). As stated before, in spite of the novelties proposed by the methods, mentioned in this section, neither of them, including TSbased approaches, produced much beyond modest gains on Atari games while BDQN provides significant improvements in terms of both sample complexity and final performance.

heading: 7 CONCLUSION
text: In this work we proposed BDQN, a practical Thompson sampling based RL algorithm which provides efficient exploration/exploitation in a computationally efficient manner. It involved making simple modifications to the DDQN architecture by replacing the last layer with Bayesian linear regression. Under the Gaussian prior, we obtained fast closed-form updates for the posterior distribution. We demonstrated significantly faster training and much better performance in many games compared to the reported results of a wide number of state-of-the-art baselines. We also established theoretical guarantees for an episodic MDP with continuous state and action spaces in the special case where the feature representation is fixed. We derived an order-optimal frequentist and Bayesian regret bound of Õ(d √ N) after N time steps.
In future, we plan to extend the analysis to the more general frequentist setting. The current theoretical guarantees are mainly developed for the class of linear functions. For general class of functions, optimism in the face of uncertainty is deployed to guarantee a tight probably approximately correct (PAC) bound (Jiang et al., 2016) but the proposed algorithm requires solving a NP-hard problem at each iteration. We aim to further provide a tight theoretical bound through Thomson sampling while also preserving computational feasibility.

heading: A APPENDIX
text: In the main text, for simplicity, we use the terms ”BLR” for i.i.d. samples and BLR for non i.i.d. samples exchangeable, even though, technically, the do not have equal meaning. In RL, the data is not i.i.d, and we extend the BLR to non i.i.d. setting by deploying additional Martingale type argument and handles the data with temporal dependency.

heading: A.1 NETWORK ARCHITECTURE:
text: The input to the network part of BDQN is 4 × 84 × 84 tensor with a rescaled and averaged over channels of the last four observations. The first convolution layer has 32 filters of size 8 with a stride of 4. The second convolution layer has 64 filters of size 4 with stride 2. The last convolution layer has 64 filters of size 3 followed by a fully connected layer with size 512. We add a BLR layer on top of this.

heading: A.2 CHOICE OF HYPER-PARAMETERS:
text: For BDQN, we set the values of W target to the mean of the posterior distribution over the weights of BLR with covariances Cov and draw W from this posterior. For the fixed W and W target, we randomly initialize the parameters of network part of BDQN, θ, and train it using RMSProp, with learning rate of 0.0025, and a momentum of 0.95, inspired by (Mnih et al., 2015) where the discount factor is γ = 0.99, the number of steps between target updates T target = 10k steps, and weights W are re-sampled from their posterior distribution every T sample steps. We update the network part of BDQN every 4 steps by uniformly at random sampling a mini-batch of size 32 samples from the replay buffer. We update the posterior distribution of the weight set W every TBayes target using mini-batch of size B (if the size of replay buffer is less than B at the current step, we choose the minimum of these two ), with entries sampled uniformly form replay buffer. The experience replay contains the 1M most recent transitions. Further hyper-parameters are equivalent to ones in DQN setting.
For the BLR, we have noise variance σ , variance of prior over weights σ, sample size B, posterior update period TBayes target, and the posterior sampling period T sample. To optimize for this set of hyper-parameters we set up a very simple, fast, and cheap hyper-parameter tuning procedure which proves the robustness of BDQN. To find the first three, we set up a simple hyper-parameter search. We used a pretrained DQN model for the game of Assault, and removed the last fully connected layer in order to have access to its already trained feature representation. Then we tried combination of B = {T target, 10 · T target}, σ = {1, 0.1, 0.001}, and σ = {1, 10} and test for 1000 episode of the game. We set these parameters to their best B = 10 · T target, σ = 0.001, σ = 1. The above hyper-parameter tuning is cheap and fast since it requires only a few times theB number of forwarding passes. For the remaining parameters, we ran BDQN ( with weights randomly initialized) on the same game, Assault, for 5M time steps, with a set of TBayes target = {T target, 10 · T target} and T sample = {T target
10 , T target 100 }, where BDQN performed better with choice of T Bayes target =
10 · T target. For both choices of T sample, it performs almost equal and we choose the higher one to reduce the computation cost. We started off with the learning rate of 0.0025 and did not tune for that. Thanks to the efficient Thompson sampling exploration and closed form BLR, BDQN can learn a better policy in an even shorter period of time. In contrast, it is well known for DQN based methods that changing the learning rate causes a major degradation in the performance (Fig. 4). The proposed hyper-parameter search is very simple and an exhaustive hyper-parameter search is likely to provide even better performance.

heading: A.3 LEARNING RATE:
text: It is well known that DQN and DDQN are sensitive to the learning rate and change of learning rate can degrade the performance to even worse than random policy. We tried the same learning rate as BDQN, 0.0025, for DDQN and observed that its performance drops. Fig. 4 shows that the DDQN with higher learning rates learns as good as BDQN at the very beginning but it can not maintain the rate of improvement and degrade even worse than the original DDQN with learning rate of 0.00025.

heading: A.4 COMPUTATIONAL AND SAMPLE COST COMPARISON:
text: For a given period of game time, the number of the backward pass in both BDQN and DQN are the same where for BDQN it is cheaper since it has one layer (the last layer) less than DQN. In the sense of fairness in sample usage, for example in duration of 10 · TBayes target = 100k, all the layers of both BDQN and DQN, except the last layer, sees the same number of samples, but the last layer of BDQN sees 16 times fewer samples compared to the last layer of DQN. The last layer of DQN for a duration of 100k, observes 25k = 100k/4 (4 is back prob period) mini batches of size 32, which is 16 · 100k, where the last layer of BDQN just observes samples size of B = 100k. As it is mentioned in Alg. 1, to update the posterior distribution, BDQN draws B samples from the replay buffer and needs to compute the feature vector of them. Therefore, during the 100k interactions for the learning procedure, DDQN does 32 ∗ 25k of forward passes and 32 ∗ 25k of backward passes, while BDQN
does same number of backward passes (cheaper since there is no backward pass for the final layer) and 36 ∗ 25k of forward passes. One can easily relax it by parallelizing this step along the main body of BDQN or deploying on-line posterior update methods.

heading: A.5 THOMPSON SAMPLING FREQUENCY:
text: The choice of Thompson sampling update frequency can be crucial from domain to domain. Theoretically, we show that for episodic learning, the choice of sampling at the beginning of each episode, or a bounded number of episodes is desired. If one chooses T sample too short, then computed gradient for backpropagation of the feature representation is not going to be useful since the gradient get noisier and the loss function is changing too frequently. On the other hand, the network tries to find a feature representation which is suitable for a wide range of different weights of the last layer, results in improper waste of model capacity. If the Thompson sampling update frequency is too low, then it is far from being Thompson sampling and losses the randomized exploration property. We are interested in a choice of T sample which is in the order of upper bound on the average length of each episode of the Atari games. The current choice of T sample is suitable for a variety of Atari games since the length of each episode is in range of O(T sample) and is infrequent enough to make the feature representation robust to big changes.
For the RL problems with shorter a horizon we suggest to introduce two more parameters, T̃ sample and each w̃a where T̃ sample, the period that of each w̃a is sampled out of posterior, is much smaller than T sample and w̃a,∀a are used for Thompson sampling where wa ,∀a are used for backpropagation of feature representation. For game Assault, we tried using T̃ sample and each w̃a but did not observe much a difference, and set them to T sample and each wa. But for RL setting with a shorter horizon, we suggest using them.

heading: A.6 DROPOUT AS A RANDOMIZED EXPLORATION STRATEGY
text: Dropout, as another randomized exploration method, is proposed by Gal & Ghahramani (2016), but Osband et al. (2016) argue about the deficiency of the estimated uncertainty and hardness in driving a suitable exploration and exploitation trade-off from it (Appendix A in (Osband et al., 2016)). They argue that Gal & Ghahramani (2016) does not address the fundamental issue that for large networks trained to convergence all dropout samples may converge to every single datapoint. As also observed by (Dhillon et al., 2018), dropout might results in a ensemble of many models, but all almost the same (converge to the very same model behavior). We also implemented the dropout version of DDQN, Dropout-DDQN, and ran it on four randomly chosen Atari games (among those we ran for less than 50M time steps). We observed that the randomization in Dropout-DDQN is deficient and results in performances worse than DDQN on these four Atari games, Fig. 5. In Table 4 we compare the performance of BDQN, DDQN, DDQN+, and Dropout-DDQN, as well as the performance of the random policy, borrowed from Mnih et al. (2015). We observe that the Dropout-DDQN not only does not outperform the plain ε-greedy DDQN, it also sometimes underperforms the random policy. For the game Pong, we also ran Dropout-DDQN for 50M time steps but its average performance did not get any better than -17. For the experimental study we used the default dropout rate of 0.5 to mitigate its collapsing issue.

heading: A.7 FURTHER INVESTIGATION ON ATLANTIS:
text: After removing the maximum episode length limit for the game Atlantis, BDQN gets the score of 62M. This episode is long enough to fill half of the replay buffer and make the model perfect for the later part of the game but losing the crafted skill for the beginning of the game. We observe in Fig. 6 that after losing the game in a long episode, the agent forgets a bit of its skill and loses few games but wraps up immediately and gets to score of 30M . To overcome this issue, one can expand the replay buffer size, stochastically store samples in the reply buffer where the later samples get stored with lowest chance, or train new models for the later parts of the episode. There are many possible cures for this interesting observation and while we are comparing against DDQN, we do not want to advance BDQN structure-wise.

heading: A.8 FURTHER DISCUSSION ON REPRODUCIBILITY
text: In Table 2, we provide the scores of bootstrap DQN (Osband et al., 2016) and NoisyNet5Fortunato et al. (2017) along with BDQN. These score are directly copied from their original papers and we did not make any change to them. We also desired to report the scores of count-based method (Ostrovski et al., 2017), but unfortunately there is no table of score in that paper in order to provide them here.
In order to make it easier for the readers to compare against the results in Ostrovski et al. (2017), we visually approximated their plotted curves for CTS, P ixel, and Reactor, and added them to the Table 2. We added these numbers just for the convenience of the readers. Surely we do not argue any scientific meaning for them and leave it to the readers to interpret them.
Table 2 shows a significant improvement of BDQN over these baselines. Despite the simplicity and negligible computation overhead of BDQN over DDQN, we can not scientifically claim that BDQN
5This work does not have scores of Noisy-net with DDQN objective function but it has Noisy-net with DQN objective which are the scores reported in Table 2
outperforms these baselines by just looking at the scores in Table2 because we are not aware of their detailed implementation as well as environment details. For example, in this work, we directly implemented DDQN by following the implementation details mentioned in the original DDQN paper and the scores of our DDQN implementation during the evaluation time almost matches the scores of DDQN reported in the original paper. But the reported scores of implemented DDQN in Osband et al. (2016) are much different from the reported score in the original DDQN paper.

heading: A.9 A SHORT DISCUSSION ON SAFETY
text: In BDQN, as mentioned in Eq. 3, the prior and likelihood are conjugate of each others. Therefore, we have a closed form posterior distribution of the discounted return, ∑N t=0 γ
trt|x0 = x, a0 = a,Da, approximated as
N ( 1
σ2 φθ(x)>ΞaΦ θ aya, φ θ(x)>Ξaφ θ(x) ) One can use this distribution and come up with a safe RL criterion for the agent (Garcıa & Fernández, 2015). Consider the following example; for two actions with the same mean, if the estimated variance over the return increases, then the action becomes more unsafe Fig. 8. By just looking at the low and high probability events of returns under different actions we can approximate whether an action is safe to take.

heading: B BAYESIAN AND FREQUENTIST REGRET, PROOF OF THEOREMS 1,2
text: Modeling: We consider the following linear model over the Q functions and returns for episodic MDPs with episode length of H . We consider the discount factor to be any number 0 ≤ γ ≤ 1. Let ω∗ denotes the parameter corresponding the underlying model. For a given policy π and the time step ht in the episode, condition on Xh0 , Ah0 we have ∑H h=h0 Rh = φ(X h0 , Ah0)>ω∗+ ∑H h=h0
νh with φ(X,A) ∈ Rd. The noise process is correlated, dependent on the agent policy, and is not mean zero unless under policy π∗.
ΨR = Φ(X{1:H}, A{1:H})ω∗ + Ψν(X{1:H}, A{1:H}) , where , Ψ :=  1 γ γ2 . . . γH−1 0 1 γ . . . γH−2 0 0 1 . . . ...
... . . . . . . . . . ... 0 . . . . . . . . . 1
 (5)
The vector R ∈ RH is a random vector, as stack of rewards in a episode, i.e., Rh = rh. The matrix Φ(X{1:H}, X{1:H}) ∈ RH×d is a row-wised concatenation of sequence of state-action features, Φh = φ(Xh, Ah) with Φh denotes the h’th row.
In order to provide more intuition on the model, we can exploit the property of the matrix Ψ where
Ψ−1 =  1 -γ 0 . . . 0 0 1 -γ . . . 0 0 0 1 . . . ...
... . . . . . . . . . ... 0 . . . . . . . . . 1  and rewrite Eq. 5 as follows:
Rt = Ψ −1Φtω + νt (6)
We denote Ψ′ := Ψ−1>. We build our analysis based on the former notation. We consider the feature representing matrix and weights for any X{1:H}, A{1:H} to satisfy;
trace ( Φ(X{1:H}, A{1:H})Φ(X{1:H}, A{1:H})> ) ≤ L , ‖ω‖2 ≤ Lω
The vector ν(X{1:H}, A{1:H}) ∈ RH is a state-action and policy dependent noise vector. The MDP assumption is crucial for the analysis in this paper. The noise νh encodes the randomness in transition to state Xh, possible stochasticity in policy i.e., Ah, reward Rh. For any h, the noises after time step h, {νh, νh+1, . . . , νH}, are conditionally independent from the noises before time step h′, {ν1, ν2, . . . , νh−1} given (Xh, Ah). Moreover, since νh encodes the stochasticity in transition and reward at time step h, conditional distribution of νh|(Xh, Ah) is mean zero and independent {ν0, . . . {νh−1, νh+1, . . . , νH} other of since φ(Xh, Ah)>ω∗ represent the true Q value of Xh, Ah. The agent policy at each episode is denoted as πt. In the remaining, we show how to estimate ω∗ through data collected by following πt. We denote ω̂t, the estimation of ω∗. We show over time the estimation concentrates around ω∗ under the desire matrix norm. We further show, we can deploy this analysis an construct two algorithms, one based on PSRL, and another Optimism OFUto guaranteed Bayesian and frequentist regret upper bounds respectively. The main body of the following analyses on concentration of measure is a matrix extension of contextual linear bandit analyses Abbasi-Yadkori et al. (2011); Chu et al. (2011); Li et al. (2010); Rusmevichientong & Tsitsiklis (2010); Dani et al. (2008); Russo & Van Roy (2014a) and self normalized processes (de la Pena et al., 2004). Our regret analysis extends prior analysis in frequentist and Bayesian regret literature Osband et al. (2013); Jaksch et al. (2010).
We restate the Eq. 5 in its abstract way;
Rt := ΨRt = Φtω + νt , where νt := Ψνt (7)
We consider the discount factor to be any number 0 ≤ γ ≤ 1 for the modeling and for the sake of analysis we consider γ = 1 from now on which we later argue the bounds also hold for any 0 ≤ γ ≤ 1. Assumption 1 (Sub-Gaussian random vector (Hsu et al., 2012)). The noise model at time t, conditioned on the filtration Ft−1 at time t is sub-Gaussian random vector, i.e. there exists a parameter σ ≥ 0 such that ∀α ∈ Rd
E [ exp ( α>νt ) ∣∣∣Ft−1] ≤ exp (‖α‖2σ2/2) The filtration at time t also includes X{1:H}, A{1:H}. Asm. 1 also implies that E [ νt
∣∣∣Ft] = 0 which means that after drawing the matrix Φt, the random variable νt is means zero. A similar assumption on the noise model is assumed in prior analyses of linear bandit (Abbasi-Yadkori et al., 2011).
Furthermore, we consider the maximum expected cumulative reward condition on states of a episode is at most 1.
Defined the following quantities for self-normalized processes;
St := t∑ i Φ>i νi, χt := t∑ i=0 Φ>i Φi, χt = χt + χ̃
where χ̃ is a ridge regularization matrix and usually is equal to λI .
Lemma 1 (Confidence ellipsoid for problem in Eq. 5). For a matrix problem in Eq. 5, given a sequence of {Φi,Ri}Ti=1, under the Asm. 1 and the following estimator for ω̂t
ω̂t := ( t∑ i Φ>i Φi + λI )−1 t∑ i ( Φ>i Ri ) with probability at least 1− δ
‖ω̂τ − ω∗‖χt ≤ θt(δ) : σ √ 2 log (1/δ) + d log (1 + tL2/λ) + λ1/2Lω
for all t ≤ T where ‖ω∗‖2 ≤ Lω and trace ( Φ(·)Φ(·)> ) ≤ L, and therefore the confidence set is
Ct(δ) := {ω ∈ Rd : ‖ω̂t − ω‖χt ≤ θt(δ)}
Let ΘT denote the event that the confidence bounds in Lemma 1 holds. Lemma 2 (Determinant Lemma). For a sequence ∑T t log ( 1 + ‖Φt‖χ−1t ) we have
T∑ t log ( 1 + ‖Φt‖χ−1t ) ≤ d log(λ+ TL2/d) (8)
Regret Definition We defined V ωπ , the value of policy π applied on model specified by ω in Eq. 5. We restate the definition of the regret and Bayesian regret.
RegT : = E [ T∑ t [ V ω ∗ π∗ − V ω ∗ πt ] |ω∗ ]
Where πt is the agent policy at time t
When there is a prior over the ω∗ the expected Bayesian regret might be the target of the study.
BayesRegT : = E [ T∑ t [ V ω ∗ π∗ − V ω ∗ πt ]]

heading: B.1 OPTIMISM: REGRET BOUND OF ALG. 3
text: Given samples by following the agent policy π′t for each episode t ′ ≤ t we estimate the ω̂t as follows;
ω̂t := ( t∑ i Φ>i Φi + λI )−1 t∑ i ( Φ>i Ri ) Lemma 1 states that under event ΘT , ‖ω̂t − ω∗‖χt ≤ θt(δ). For an observed state X 1 t , the optimistic policy is
π̃t(X h t ) = arg max
a∈A max ω∈Ct−1(δ) φ>(Xht , a)ω
Furthermore, we define state and policy dependent optimistic parameter ω̃t(π) as follows;
ω̃t(π) := arg max ω∈Ct−1(δ)
φ(X1t , π(X 1 t )) >ω
For ease of notation we drop the state in the notation. Following OFU, Alg. 3, we set πt = π̃t denote the optimistic policy. By the definition we have
V ω̃t(π̃t) π̃t (Xht ) ≥ V ω̃t(π ∗) π∗ (X h t )
Therefore, under the event ΘT we have
RegT : = E  T∑ t V ω∗π∗ (X1t )− V ω∗π̃t (X1t )︸ ︷︷ ︸ ∆h=1t  |ω∗ 
≤ E [ T∑ t [ V ω̃t(π̃t) π̃t (X1t )− V ω̃t(π ∗) π∗ (X 1 t ) + V ω∗ π∗ (X 1 t )− V ω ∗ π̃t (X1t ) ] |ω∗ ]
= E  T∑ t V ω̃t(π̃t)π̃t (X1t )− V ω∗π̃t (X1t ) + V ω∗π∗ (X1t )− V ω̃t(π∗)π∗ (X1t )︸ ︷︷ ︸ ≤ 0  |ω∗ 
Resulting in
RegT ≤ E [ T∑ t [ V ω̃t(π̃t) π̃t (X1t )− V ω ∗ π̃t (X1t ) ] |ω∗ ]
Lets defined V ωπ (X 1 t , . . . , X
h′
t ;h : π ′) as the value function following policy π for h time step then
switching to policy π′ on the model ω and observing X1t , . . . X h′ t .
RegT ≤ E [ T∑ t [ V ω̃t(π̃t) π̃t (X1t )− V ω ∗ π̃t (X1t ) ] |ω∗ ]
= E [ T∑ t [ V ω̃t(π̃t) π̃t (X1t )− V ω ∗ π̃t (X1t ; 1 : π ∗) + V ω ∗ π̃t (X1t ; 1 : π ∗)− V ω ∗ π̃t (X1t ) ] |ω∗ ]
Given the generative model in Eq.5 we have
RegT ≤ E [ T∑ t [ V ω̃t(π̃t) π̃t (X1t )− V ω ∗ π̃t (X1t ; 1 : π ∗) + V ω ∗ π̃t (X1t ; 1 : π ∗)− V ω ∗ π̃t (X1t ) ] |ω∗ ]
= E [ T∑ t [ φ(X1t , π̃t(X 1 t )) >ω̃t(π̃t)− φ(X1t , π̃t(X1t ))>ω∗ + V ω ∗ π̃t (X1t ; 1 : π ∗)− V ω ∗ π̃t (X1t ) ] |ω∗ ]
= E  T∑ t φ(X1t , π̃t(X1t ))> (ω̃t(π̃t)− ω∗) + V ω∗π̃t (X1t ; 1 : π∗)− V ω∗π̃t (X1t )︸ ︷︷ ︸ (∆h=2t )  |ω∗ 
For ∆h=2t we deploy the similar decomposition and upper bound as ∆ h=1 t
∆2t := V ω∗ π̃t (X1t ; 1 : π ∗)− V ω ∗ π̃t (X1t )
Since for both of V ω ∗
π̃t (X1t ; 1 : π
∗) and V ω ∗
π̃t (X1t ) we follow the same policy on the same model for 1
time step, the reward at the first time step has the same distribution, therefore we have; ∆h=2t = E [ V ω ∗ π̃t (X2t ; 1 : π ∗)− V ω ∗ π̃t (X2t )|X1t , ω∗ ] rustling in
∆h=2t = E [ V ω ∗ π̃t (X2t ; 1 : π ∗)− V ω ∗ π̃t (X2t )|X1t , ω∗ ]
≤ E φ(X2t , π̃t(X2t ))> (ω̃t(π̃t)− ω∗) + V ω∗π̃t (X2t ; 2 : π∗)− V ω∗π̃t (X2t )︸ ︷︷ ︸ (∆h=3t ) |X1t , ω∗ 
Similarly we can defined ∆h=3t , . . .∆ h=H t . Therefore;
RegT ≤ E [ T∑ t H∑ h φ(Xht , π̃t(X h t )) > (ω̃t(π̃t)− ω∗) |ω∗ ]
= E [ T∑ t 1 >Φt (ω̃t(π̃t)− ω∗) |ω∗ ]
= E [ T∑ t 1 >Φtχ −1/2 t χ 1/2 t (ω̃t(π̃t)− ω∗) |ω∗ ]
≤ E [ √ H
T∑ t ‖Φt‖χ−1t ‖ω̃t(π̃t)− ω ∗‖χt |ω ∗
]
≤ E [ √ H
T∑ t ‖Φt‖χ−1t 2θt−1(δ)|ω ∗
] (9)
Since the maximum expected cumulative reward, condition on states of a episode is at most 1, we have;
RegT ≤ √ HE [ T∑ t min{‖Φt‖χ−t 12θt−1(δ), 1}|ω ∗ ]
≤ √ HE [ T∑ t H∑ h 2θt−1(δ) min{‖Φt‖χ−t 1, 1}|ω ∗ ]
Moreover, at time T , we can use Jensen’s inequality, exploit the fact that θt(δ) is an increasing function of t and have
RegT ≤ 2E  √√√√THθT (δ)2 T∑
t
min{‖Φt‖χ−t 1, 1}|ω ∗  ≤ 2 ( σ √ 2 log (1/δ) + d log (1 + TL2/λ) + λ1/2Lω ) E  √√√√TH T∑
t
min{‖Φt‖χ−1t , 1}|ω ∗  (10)
Now, using the fact that for any scalar α such that 0 ≤ α ≤ 1, then α ≤ 2 log(1 + α) we can rewrite the latter part of Eq. 10√√√√ T∑
t min{‖Φt‖χ−1t , 1} ≤ 2 T∑ t log ( 1 + ‖Φt‖χ−1t )
By applying the Lemma 2 and substituting the RHS of Eq. 8 into Eq. 10, we get RegT ≤ 2 ( σ √ 2 log (1/δ) + d log (1 + TL2/λ) + λ1/2Lω )√ 2THd log(λ+ TL2/d) (11)
with probability at least 1 − δ. If we set δ = 1/T then the probability that the event ΘT holds is 1− 1/T and we get regret of at most the RHS of Eq. 11, otherwise with probability at most 1/T we get maximum regret of T , therefore
RegT ≤ 1 + 2 ( σ √ 2 log (T ) + d log (1 + TL2/λ) + λ1/2Lω )√ 2THd log(λ+ TL2/d)
and theorem statement follows.

heading: B.2 BAYESIAN REGRET OF ALG. 2
text: The analysis developed in the previous section, up to some minor modification, e.g., change of strategy to PSRL, directly applies to Bayesian regret bound, with a farther expectation over models.
When there is a prior over the ω∗ the expected Bayesian regret might be the target of the study.
BayesRegT : = E [ T∑ t [ V ω ∗ π∗ − V ω ∗ πt ]]
E [ T∑ t [ V ω ∗ π∗ − V ω ∗ πt ∣∣Ht]]
HereHt is a multivariate random sequence which indicates history at the beginning of episode t and πt is the policy following PSRL. For the remaining πt denotes the PSRL policy. As it mentioned in the Alg. 2, at the beginning of an episode, we draw ωt for the posterior and the corresponding policy is
πt(X h t ) := arg max a∈A φ(Xht , a) >ωt
Condition on the historyHt, samples by following the agent policy π′t for each episode t′ ≤ t, similar to previous section we estimate the ω̂t as follows;
ω̂t := ( t∑ i Φ>i Φi + λI )−1 t∑ i ( Φ>i Ri ) Lemma 1 states that under event ΘT , ‖ω̂t − ω∗‖χt ≤ θt(δ). Conditioned onHt, the ωt and ω
∗ are equally distributed, then we have
E [ V ω̃t(π ∗) π∗ ∣∣Ht] = E [V ω̃t(πt)πt ∣∣Ht] Therefore, under event ΘT holds for all ω∗ we have
BayesRegT : = T∑ t E V ω∗π∗ (X1t )− V ω∗πt (X1t )︸ ︷︷ ︸ ∆h=1t |Ht  =
T∑ t E [ V ω̃t(πt)πt (X 1 t )− V ω̃t(π ∗) π∗ (X 1 t ) + V ω∗ π∗ (X 1 t )− V ω ∗ πt (X 1 t )|Ht ]
= T∑ t E V ω̃t(πt)πt (X1t )− V ω∗πt (X1t ) + V ω∗π∗ (X1t )− V ω̃t(π∗)π∗ (X1t )︸ ︷︷ ︸ ≤ 0 |Ht 
Resulting in
BayesRegT ≤ T∑ t E [ V ω̃t(πt)πt (X 1 t )− V ω ∗ πt (X 1 t )|Ht ]
Similar to optimism and defining V ωπ (X 1 t , . . . , X
h′
t ;h : π ′) accomponeid with Eq.5 we have;
BayesRegT ≤ E [ T∑ t [ V ω̃t(πt)πt (X 1 t )− V ω ∗ πt (X 1 t )|Ht ]]
= E [ T∑ t [ V ω̃t(πt)πt (X 1 t )− V ω ∗ πt (X 1 t ; 1 : π ∗) + V ω ∗ πt (X 1 t ; 1 : π ∗)− V ω ∗ πt (X 1 t )|Ht ]]
≤ E [ T∑ t [ φ(X1t , πt(X 1 t )) >ω̃t(πt)− φ(X1t , πt(X1t ))>ω∗ + V ω ∗ πt (X 1 t ; 1 : π ∗)− V ω ∗ πt (X 1 t )|Ht ]]
= E  T∑ t φ(X1t , πt(X1t ))> (ω̃t(πt)− ω∗) + V ω∗πt (X1t ; 1 : π∗)− V ω∗πt (X1t )︸ ︷︷ ︸ (∆h=2t ) |Ht  
For ∆h=2t we deploy the similar decomposition and upper bound as ∆ h=1 t
∆2t := V ω∗ πt (X 1 t ; 1 : π ∗)− V ω ∗ πt (X 1 t )
Since for both of V ω ∗
πt (X 1 t ; 1 : π
∗) and V ω ∗
πt (X 1 t ) we follow the same distribution over policies and
models for 1 time step, the reward at the first time step has the same distribution, therefore we have; ∆h=2t = E [ V ω ∗ πt (X 2 t ; 1 : π ∗)− V ω ∗ πt (X 2 t )|X1t ,Ht ] rustling in
∆h=2t = E [ V ω ∗ πt (X 2 t ; 1 : π ∗)− V ω ∗ πt (X 2 t )|X1t ,Ht ]
≤ E φ(X2t , πt(X2t ))> (ω̃t(πt)− ω∗) + V ω∗πt (X2t ; 2 : π∗)− V ω∗πt (X2t )︸ ︷︷ ︸ (∆h=3t ) |X1t ,Ht  Similarly we can defined ∆h=3t , . . .∆ h=H t . The condition onHt was required to come up with the mentioned decomposition through ∆ht and it is not needed anymore, therefore;
BayesRegT ≤ E [ T∑ t H∑ h φ(Xht , πt(X h t )) > (ω̃t(πt)− ω∗) ] (12)
= T∑ t E [ 1 >Φt (ω̃t(πt)− ω∗) ] (13)
= E [ T∑ t 1 >Φtχ −1/2 t χ 1/2 t (ω̃t(πt)− ω∗) ] (14)
≤ E [ √ H
T∑ t ‖Φt‖χ−1t ‖ω̃t(πt)− ω ∗‖χt
] (15)
≤ E [ √ H
T∑ t ‖Φt‖χ−1t 2θt−1(δ)
] (16)
Again similar to optimism we have the maximum expected cumulative reward condition on states of a episode is at most 1, we have;
BayesRegT ≤ √ HE [ T∑ t min{‖Φt‖χ−t 12θt−1(δ), 1} ]
≤ √ HE [ T∑ t H∑ h 2θt−1(δ) min{‖Φt‖χ−t 1, 1} ]
Moreover, at time T , we can use Jensen’s inequality, exploit the fact that θt(δ) is an increasing function of t and have
BayesRegT ≤ 2E  √√√√THθT (δ)2 T∑
t
min{‖Φt‖χ−t 1, 1}  ≤ 2 ( σ √ 2 log (1/δ) + d log (1 + TL2/λ) + λ1/2Lω ) E  √√√√TH T∑
t
min{‖Φt‖χ−1t , 1}  ≤ 2 ( σ √ 2 log (1/δ) + d log (1 + TL2/λ) + λ1/2Lω )√ 2THd log(λ+ TL2/d)
(17)
Under event ΘT which holds with probability at least 1− δ. If we set δ = 1/T then the probability that the event Θ holds is 1 − 1/T and we get regret of at most the RHS of Eq. 17, otherwise with probability at most 1/T we get maximum regret of T , therefore
BayesRegT ≤ 1 + 2 ( σ √ 2 log (T ) + d log (1 + TL2/λ) + λ1/2Lω )√ 2THd log(λ+ TL2/d)
and theorem statement follows.

heading: B.3 DISCOUNT FACTOR
text: Through the analysis of the theorems 1 and 2 we studied the regret upper bounds for undiscounted reward MDPs when γ = 1. If we consider the problem expression as follows
Rt := ΨRt νt := Ψνt the parameter νt for a general matrix Ψ represent the stochasticity of the return under any discount factor 0 ≤ γ ≤ 1. Under the general discount factor, the Assumption 1 describes the sub-Gaussian characteristics of νt. Moreover under discounted return, the value function represent the expectation of the discounted return, resulting in a potentially smaller Lω. Furthermore, in the decompositions derived in the Eqs. 9 and 12 regarding ∆ht we require to aggregate the regret while discounting the per step regrets. It means we replace 1 with [1, γ, γ2, . . . , γH−1]> in those equations. Consequently, instead of considering the ‖1‖2 to upper bound the regrets, we are interested in the discounted returns and consider ‖[1, γ, γ2, . . . , γH−1]‖2 to come up with the corresponding upper bounds and replace√ H in the final statements of the theorems 1 and 2 with a discount factor dependent and smaller value ‖[1, γ, γ2, . . . , γH−1]‖2.

heading: B.4 PROOF OF LEMMAS
text: Lemma 3. Let α ∈ Rd be be an arbitrary vector and for any t ≥ 0 define
Mαt := exp ( t∑ i [ α>Φ>i νi σ − 1 2 ‖Φiα‖22 ]) Then, for a stopping time under the filtration {Ft}∞t=0, Mλτ ≤ 1.
Proof. Lemma 3 We first show that {Mαt }∞t=0 is a supermartingale sequence. Let
Dαi = exp
( α>Φ>i νi
σ − 1 2 ‖Φiα‖22 ) Therefore, we can rewrite E [Mαt ] as follows:
E [Mαt |Ft−1] = E [ Dα1 . . . D α t−1D α t |Ft−1 ] = Dα1 . . . D α t−1E [Dαt |Ft−1] ≤Mαt−1
The last inequality follows since E [Dαt |Ft−1] ≤ 1 due to Assumption 1, therefore since for the first time step E [Mα1 ] ≤ 1, then E [Mαt ] ≤ 1. For a stopping time τ , Define a variable M α t = M α min{t,τ}
and since E [Mατ ] = E [ lim inft→∞M α t ] ≤ lim inft→∞ E [ M α t ] ≤ 1, therefore the Lemma 3
holds.
Lemma 4. [Extension to Self-normalized bound in Abbasi-Yadkori et al. (2011)] For a stopping time τ and filtration {Ft}∞t=0, with probability at least 1− δ
‖Sτ‖2χ−1τ ≤ 2σ 2 log(
det (χt) 1/2 det(χ̃)−1/2
δ )
Proof. of Lemma 4. Given the definition of the parameters of self-normalized process, we can rewrite Mαt as follows;
Mαt = exp ( α>St σ − 1 2 ‖α‖χt ) Consider Ω as a Gaussian random vector and f(Ω = α) denotes the density with covariance matrix of χ−1. Define Mt := E [ MΩt |F∞ ] . Therefore we have E [Mt] = E [ E [ MΩt |Ω ]] ≤ 1. Therefore
Mt = ∫ Rd exp ( α>St σ − 1 2 ‖α‖χt ) f(α)dα
= ∫ Rd exp ( 1 2 ‖α− χ−1t St/σ‖2χt + 1 2 ‖St/σ‖2χ−1t ) f(α)dα
=
√ det (χ̃)
(2π) d
exp
( 1
2 ‖St/σ‖χ−1t )∫ Rd exp ( 1 2 ‖α− χ−1t St/σ‖2χt + 1 2 ‖α‖2χ̃ ) dα
Since χt and χ̃ are positive semi definite and positive definite respectively, we have
‖α− χ−1t St/σ‖2χt + ‖α‖ 2 χ̃ = ‖α− ( χ̃+ χ−1t ) St/σ‖2χ̃+χt + ‖χ −1 t St/σ‖2χt − ‖St/σ‖ 2 (χ̃+χt) −1
= ‖α− ( χ̃+ χ−1t ) St/σ‖2χ̃+χt + ‖St/σ‖ 2 χ−1t − ‖St/σ‖2(χ̃+χt)−1
Therefore,
Mt =
√ det (χ̃)
(2π) d
exp
( 1
2 ‖St/σ‖(χ̃+χt)−1 )∫ Rd exp ( 1 2 ‖α− ( χ̃+ χ−1t ) St/σ‖2χ̃+χt ) dα
=
( det (χ̃)
det (χ̃+ χt)
)1/2 exp ( 1
2 ‖St/σ‖2(χ̃+χt)−1 ) Since E [Mτ ] ≤ 1 we have
P ( ‖Sτ‖2(χ̃+χτ )−1 ≤ 2σ log ( det (χ̃+ χτ ) 1/2
δ det (χ̃) 1/2
)) ≤ E [ exp ( 1 2‖Sτ/σ‖ 2 (χ̃+χτ ) −1 )] (
det(χ̃+χτ ) δ det(χ̃) )1/2 ≤ δ Where the Markov inequality is deployed for the final step. The stopping is considered to be the time step as the first time in the sequence when the concentration in the Lemma 4 does not hold.
Proof of Lemma 1. Given the estimator ω̂t we have the following:
ω̂t = ( t∑ i Φ>i Φi + λI )−1 t∑ i ( Φ>i (Φiω ∗ + νi) )
= ( t∑ i Φ>i Φi + λI )−1 t∑ i ( Φ>i νi ) +
( t∑ i Φ>i Φi + λI )−1( t∑ i Φ>i Φi + λI ) ω∗
− λ ( t∑ i Φ>i Φi + λI )−1 ω∗
therefore, for any vector ζ ∈ Rd ζ>ω̂t − ζ>ω∗ = ζ> (
t∑ i Φ>i Φi + λI )−1 t∑ i ( Φ>i νi ) − ζ>λ
( t∑ i Φ>i Φi + λI )−1 ω∗
As a results, applying Cauchy-Schwarz inequality and inequalities ‖ω∗‖χ−1t ≤ 1 λ(χt) ‖ω∗‖2 ≤ 1 λ‖ω ∗‖2 we get
|ζ>ω̂t − ζ>ω∗| ≤ ‖ζ‖χ−1t ‖ t∑ i ( Φ>i νi ) ‖χ−1t + λ‖ζ‖χ−1t ‖ω ∗‖χ−1t
≤ ‖ζ‖χ−1t
( ‖
t∑ i ( Φ>i νi ) ‖χ−1t + λ 1/2‖ω∗‖2 ) where applying self normalized Lemma 4, with probability at least 1− δ
|ζ>ω̂t − ζ>ω∗| ≤ ‖ζ‖χ−1t
( 2σ log ( det (χt) 1/2
δ det (χ̃) 1/2
) + λ1/2Lω ) hold for any ζ. By plugging in ζ = χt (ω̂t − ω∗) we get the following;
‖ω̂t − ω∗‖χt ≤ θt(δ) = σ
√ 2 log ( det(χt) 1/2 det(λI)−1/2
δ
) + λ1/2Lω
The det(χt) can be written as det(χt) = ∏d j αj therefore, trace(χt) = ∑d j αj . We also know that;
( d∏ j αj) 1/d ≤
∑d j αj
d
A matrix extension to Lemma 10 and 11 in Abbasi-Yadkori et al. (2011) results in det(χt) ≤( trace(χt)
d
)d while we have trace(χt) = trace(λI) + trace( ∑t i Φ > i Φi) ≤ dλ+ tL,
det(χt) ≤ ( dλ+ tL
d
)d (18)
therefore the main statement of Lemma 1 goes through.
Proof. Lemma 2 We have the following for the determinant of det (χT )
det (χT ) = det ( χT−1 + Φ > TΦT ) = det ( IH + ΦTχ −1 t Φ > T ) det ( χT−1
) =
T∏ t det ( IH + Φtχ −1 t Φ > t ) det (χ̃)
From linear algebra, and given a time step t, we define the characteristic polynomial of the matrix Φtχ −1 t Φ > t as;
CPt(λ) = det(λIH −Φtχ−1t Φ>t ).
If the set {λ1, λ2, . . . , λd} represent the eigenvalues of Φtχ−1t Φ>t where λi ≥ λj if i ≥ j, one can rewrite CPt(λ) as follows;
CP (λ) = (λ− λ1)(λ− λ2) · · · (λ− λH)
Now by adding the matrix IH to Φtχ−1t Φ > t , we get CP ′ t (λ) = det(λIH − IH − Φtχ−1t Φ>t ), therefore;
CP ′t (λ) = (λ− 1− λ1)(λ− 1− λ2) · · · (λ− 1− λH)
and the eigenvalues of IH + Φtχ−1t Φ > t are shifted eigenvalues of Φtχ −1 t Φ > t by +1, i.e. {λ1 + 1, λ2 + 1, . . . , λd + 1}. Since ξ>Φtχ−1t Φ>t ξ = ( Φχ −1/2 t > ξ )>( Φχ −1/2 t > ξ ) all the eigenvalues
{λ1, λ2, . . . , λd} are non-negative. As a results,
det ( IH + Φtχ −1 t Φ > t ) ≥ ( 1 + ‖Φt‖χ−1t )
As a consequence;
det (χT ) ≥ det (χ̃) T∏ t ( 1 + ‖Φt‖χ−1t ) Moreover we have
2 T∑ t log ( 1 + ‖Φt‖χ−1t ) ≤ 2 (log (det (χT ))− log (det (χ̃))) ≤ 2d log(λ+ TL2/d) (19)
and the statement follows.

Review summaries:
This paper proposes a method for more efficient exploration in RL by maintaining uncertainty estimates over the learned Q-value function. It is comparable to Double DQN (DDQN) but uses its learned uncertainty estimates with Thompson sampling for exploration, rather than \epsilon-greedy. Empirically the method is significantly more sample-efficient for Atari agents than DDQN and other baselines.