Title: EFFICIENT EXPLORATION THROUGH BAYESIAN DEEP Q-NETWORKS

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 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.
Under review as a conference paper at ICLR 2019 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 sampling 1 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 1 BDQN approximates the posterior resulting in approximating Thompson sample. In the remaining, we state Thompson Sampling and its approximation as Thomson samples unless we specify.

1. INTRODUCTION:

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 & Szepesvári, 2015 ). 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.

3. BAYESIAN DEEP Q-NETWORKS:

Consider an MDP M as a tuple X , A, P, P 0 , R, γ , with state space X , action space A, transition kernel P , initial state distribution P 0 , 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 )

EQUATION

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 â = arg max a Q(x , a ).

In order to reduce the bias of the estimator, DQN utilizes a target network Q target , target value Execute a t = arg max a w a φ θ (x t ), observe reward r t , successor State x t+1 8:

Store transition (x t , a t , r t , x t+1 ) in the replay buffer 9:

Sample a random minibatch of transitions (x τ , a τ , r τ , x τ +1 ) from replay buffer 10: â) , and approaches the regression on the empirical estimates of the loss

y τ ← r τ terminal x τ +1 r τ +w target â φ θ target (x τ +1 ), â := arg max a w a φ θ (x τ +1 )non-terminal x τ +1 11: θ ← θ -η • ∇ θ (y τ -w aτ φ θ (x τ )) 2 y = r + γQ target (x ,

L(Q, Q target ); L(Q, Q target ) = E π (Q(x, a) -y) 2 (2)

i.e., L(Q, Q target ). A DQN agent, once in a while updates the Q target 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 â = arg max a Q target (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) ∈ R d parametrized by θ, i.e., for all pairs of state-action ∀a ∈ A, x ∈ X , we have Q(x, a) = φ θ (x) w a with w a ∈ R d , the output layer. Consequently, the target model has the same architecture as the Q, and consists of φ θ target (•) ∈ R d , the feature representation of target network, and w target a , ∀a ∈ A the target weight. For a given tuple of experiences (x, a, r, x ), and â = arg max a φ θ target w target

a Q(x, a) = φ θ (x) w a → y := r + γφ θ target (x )w target â

The regression in Eq. 2 induces linear regression in the learning of the output layer, i.e., w a '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 w a , resulting in the posterior distribution of the Q-function. As in BLR methods, we maintain a Gaussian prior N (0, σ 2 I) 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 D a for each action with a τ = a. For each action a, we construct a matrix Φ θ a ∈ R d×|Da| , the concatenation of feature vectors {φ θ (x i )} |Da| i=1 , and y a ∈ R |Da| , the concatenation of target values in set D a . Finally, we approximate the posterior distribution of w a as follows:

w a ∼ N (w a , Cov a ) , w a := 1 σ 2 Cov a Φ θ a y a , Cov a := 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 w a is drawn from the posterior distribution Fig. 2 . In BDQN, every T sample times step, we draw a new w a , ∀a ∈ A and follow the resulting policy, i.e., a TS := max a 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.

EQUATION

We update the target network every T target steps and set θ target to θ. With the period of T Bayes target , we update the posterior distribution using a minibatch of B randomly chosen experiences in the replay buffer, and set the w target a = w a , ∀a ∈ A which is the mean of the posterior distribution( more details in Section A.5. We describe BDQN algorithm in Alg. 1. for h = 1 to the end of episode do 5:

4. BAYESIAN REGRET BOUND:

Follow π t policy 6:

Update the confidence C t (δ)

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, P 0 , 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 φ(•, 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 , Ψ :=

•) := X × A → R d , i.e., Q ω * π * (x, a) := φ(x, a) ω * , ∀x, a ∈ X × A, where ω * ∈ R d and π * : X → A as π * (x) := arg max a∈A Q ω * π * (x,

    1 γ γ 2 . . . γ H-1 0 1 γ . . . γ H-2 . . . . . . . . . . . . . . . 0 . . . . . . . . . 1    

The vector R ∈ R H is the random vector of rewards in an episode and R ∈ R H 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} ) ∈ R H×d is row-wise concatenation of their features and ν(x {1:H} , a {1:H} ) ∈ R d 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 max a∈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 C t-1 i.e., ω * ∈ C t with high probability. At each time step h, given a state x h t , the agent follows the optimistic policy; π t (x h t ) = arg max a∈A max ω∈Ct-1 φ (X h t , a)ω. Through exploration and exploitation, we show that the confidence set C t 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) ∈ R d , the Thompson sampling on ω, Alg. 2, after T episodes, guarantees;

BayesReg T : = E T t V ω * π * -V ω * πt = O d √ T H log(T )

Proof is Appendix B.2. Note that N = T H is the number of agent-environment interactions.

Theorem 2 (Frequentist Regret). For an episodic MDP with episode length H, γ = 1, feature mapping φ(x, a) ∈ R d , the optimism on ω, Alg. 3, after T episodes, guarantees;

Reg T : = E T t V ω * π * -V ω * πt |ω * = O d √ T H 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 & Szepesvá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 .

5. EXPERIMENTS:

We apply BDQN on a variety of Atari games using the Arcade Learning Environment (Bellemare et al., 2013) through OpenAI Gym 2 (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. (Osband et al., 2016) , CTS, Pixel, Reactor (Ostrovski et al., 2017) are borrowed from the original papers. For NoisyNet (Fortunato et al., 2017) , the scores of NoisyDQN are reported. Sample complexity, SC: the number of samples the BDQN requires to beat the human score (Mnih et al., 2015) (" -" means BDQN could not beat human score). SC + : the number of interactions the BDQN requires to beat the score of DDQN + . 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 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.

6. RELATED WORK:

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) (Anandkumar et al., 2014) . Furthermore, Bartó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 & Szepesvá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 & Szepesvá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.

7. CONCLUSION:

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.

William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 1933.

Nikolaos Tziortziotis, Christos Dimitrakakis, and Konstantinos Blekas. Linear bayesian reinforcement learning. In IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, 2013.

Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double qlearning. In AAAI, 2016.

A APPENDIX:

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. 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.

A.2 CHOICE OF HYPER-PARAMETERS::

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 T Bayes 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 T Bayes 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 the B 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 T Bayes 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.

A.3 LEARNING RATE::

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. 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 • T Bayes 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.

A.5 THOMPSON SAMPLING FREQUENCY:

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 wa where T sample , the period that of each wa is sampled out of posterior, is much smaller than T sample and wa , ∀a are used for Thompson sampling where w a , ∀a are used for backpropagation of feature representation. For game Assault, we tried using T sample and each wa but did not observe much a difference, and set them to T sample and each w a . But for RL setting with a shorter horizon, we suggest using them.

A.6 DROPOUT AS A RANDOMIZED EXPLORATION STRATEGY:

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. 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.

Figure 6 : BDQN on Atlantis after removing the limit on max of episode length hits the score of 62M in 16M samples. In Table 2 , we provide the scores of bootstrap DQN (Osband et al., 2016) and NoisyNet5 Fortunato 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 CT S, 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 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.

A.9 A SHORT DISCUSSION ON SAFETY

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 γ t r t |x 0 = x, a 0 = a, D a , approximated as N 1 σ 2 φ θ (x) Ξ a Φ θ a y a , φ θ (x) Ξ a φ θ (x)

One can use this distribution and come up with a safe RL criterion for the agent (Garcıa & Ferná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.

unsafe deviation mean mean deviation safer Figure 8 : Two actions, with the same mean, but the one with higher variance on the return might be less safe than the one with narrower variance on the return.

B BAYESIAN AND FREQUENTIST REGRET, PROOF OF THEOREMS 1,2:

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 h t in the episode, condition on X h0 , A h0 we have

H h=h0 R h = φ(X h0 , A h0 ) ω * + H h=h0 ν h with φ(X, A) ∈ R d .

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 ,

EQUATION

The vector R ∈ R H is a random vector, as stack of rewards in a episode, i.e., R h = r h . The matrix Φ(X {1:H} , X {1:H} ) ∈ R H×d is a row-wised concatenation of sequence of state-action features, Φ h = φ(X h , A h ) 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:

EQUATION

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} ) ∈ R H 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 X h , possible stochasticity in policy i.e., A h , reward R h . 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 (X h , A h ). Moreover, since ν h encodes the stochasticity in transition and reward at time step h, conditional distribution of ν h |(X h , A h ) is mean zero and independent {ν 0 , . . .

{ν h-1 , ν h+1 , . . . , ν H } other of since φ(X h , A h ) ω * represent the true Q value of X h , A h .

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 We restate the Eq. 5 in its abstract way;

EQUATION

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 F t-1 at time t is sub-Gaussian random vector, i.e. there exists a parameter

σ ≥ 0 such that ∀α ∈ R d E exp α ν t F t-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 F t = 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;

S t := 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 , R i } T i=1 , under the Asm. 1 and the following estimator for ω t

ω t := t i Φ i Φ i + λI -1 t i Φ i R i with probability at least 1 -δ ω τ -ω * χ t ≤ θ t (δ) : σ 2 log (1/δ) + d log (1 + tL 2 /λ) + λ 1/2 L ω

for all t ≤ T where ω * 2 ≤ L ω and trace Φ(•)Φ(•) ≤ L, and therefore the confidence set is

C t (δ) := {ω ∈ R d : ω t -ω χ t ≤ θ t (δ)}

Let Θ T denote the event that the confidence bounds in Lemma 1 holds.

Lemma 2 (Determinant Lemma). For a sequence

EQUATION

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.

Reg T : = 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.

BayesReg T : = E T t V ω * π * -V ω * πt B.1 OPTIMISM: REGRET BOUND OF ALG. 3

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 R i

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(δ) φ (X h t , a)ω

Furthermore, we define state and policy dependent optimistic parameter ω t (π) as follows;

ω t (π) := arg max ω∈Ct-1(δ) φ(X 1 t , π(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 (X h t ) ≥ V ωt(π * ) π * (X h t )

Therefore, under the event Θ T we have

Reg T : = E     T t     V ω * π * (X 1 t ) -V ω * πt (X 1 t ) ∆ h=1 t     |ω *     ≤ E T t V ωt( πt) πt (X 1 t ) -V ωt(π * ) π * (X 1 t ) + V ω * π * (X 1 t ) -V ω * πt (X 1 t ) |ω * = E    T t   V ωt( πt) πt (X 1 t ) -V ω * πt (X 1 t ) + V ω * π * (X 1 t ) -V ωt(π * ) π * (X 1 t ) ≤ 0    |ω *   

Resulting in

Reg T ≤ E T t V ωt( πt) πt (X 1 t ) -V ω * πt (X 1 t ) |ω *

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 X 1 t , . . . X h t .

Reg T ≤ E T t V ωt( πt) πt (X 1 t ) -V ω * πt (X 1 t ) |ω * = 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 ) |ω *

Given the generative model in Eq.5 we have

Reg T ≤ 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 ) |ω * = E T t φ(X 1 t , π t (X 1 t )) ω t ( π t ) -φ(X 1 t , π t (X 1 t )) ω * + V ω * πt (X 1 t ; 1 : π * ) -V ω * πt (X 1 t ) |ω * = E     T t     φ(X 1 t , π t (X 1 t )) ( ω t ( π t ) -ω * ) + V ω * πt (X 1 t ; 1 : π * ) -V ω * πt (X 1 t ) (∆ h=2 t )     |ω *    

For ∆ h=2 t we deploy the similar decomposition and upper bound as

∆ h=1 t ∆ 2 t := 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 policy on the same model for 1 time step, the reward at the first time step has the same distribution, therefore we have;

∆ h=2 t = E V ω * πt (X 2 t ; 1 : π * ) -V ω * πt (X 2 t )|X 1 t , ω * rustling in ∆ h=2 t = E V ω * πt (X 2 t ; 1 : π * ) -V ω * πt (X 2 t )|X 1 t , ω * ≤ E     φ(X 2 t , π t (X 2 t )) ( ω t ( π t ) -ω * ) + V ω * πt (X 2 t ; 2 : π * ) -V ω * πt (X 2 t ) (∆ h=3 t ) |X 1 t , ω *    

Similarly we can defined ∆ h=3 t , . . . ∆ h=H t . Therefore;

Reg T ≤ E T t H h φ(X h t , π 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 χ -1 t ω t ( π t ) -ω * χ t |ω * ≤ E √ H T t Φ t χ -1 t 2θ t-1 (δ)|ω * (9)

Since the maximum expected cumulative reward, condition on states of a episode is at most 1, we have;

Reg T ≤ √ HE T t min{ Φ t χ - t 1 2θ 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

EQUATION

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 χ -1 t , 1} ≤ 2 T t log 1 + Φ t χ -1 t

By applying the Lemma 2 and substituting the RHS of Eq. 8 into Eq. 10, we get

Reg T ≤ 2 σ 2 log (1/δ) + d log (1 + T L 2 /λ) + λ 1/2 L ω 2T Hd log(λ + T L 2 /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

Reg T ≤ 1 + 2 σ 2 log (T ) + d log (1 + T L 2 /λ) + λ 1/2 L ω 2T Hd log(λ + T L 2 /d)

and theorem statement follows.

B.2 BAYESIAN REGRET OF ALG. 2:

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.

BayesReg T : = E T t V ω * π * -V ω * πt E T t V ω * π * -V ω * πt H t

Here H t 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 φ(X h t , a) ω t

Condition on the history H t , 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 R i

Lemma 1 states that under event Θ T , ω t -ω * χ t ≤ θ t (δ). Conditioned on H t , the ω t and ω * are equally distributed, then we have

E V ωt(π * ) π * H t = E V ωt(πt) πt H t

Therefore, under event Θ T holds for all ω * we have

BayesReg T : = T t E     V ω * π * (X 1 t ) -V ω * πt (X 1 t ) ∆ h=1 t |H t     = T t E V ωt(πt) πt (X 1 t ) -V ωt(π * ) π * (X 1 t ) + V ω * π * (X 1 t ) -V ω * πt (X 1 t )|H t = T t E   V ωt(πt) πt (X 1 t ) -V ω * πt (X 1 t ) + V ω * π * (X 1 t ) -V ωt(π * ) π * (X 1 t ) ≤ 0 |H t    Resulting in BayesReg T ≤ T t E V ωt(πt) πt (X 1 t ) -V ω * πt (X 1 t )|H t

Similar to optimism and defining V ω π (X 1 t , . . . , X h t ; h : π ) accomponeid with Eq.5 we have;

BayesReg T ≤ E T t V ωt(πt) πt (X 1 t ) -V ω * πt (X 1 t )|H t = 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 )|H t ≤ E T t φ(X 1 t , π t (X 1 t )) ω t (π t ) -φ(X 1 t , π t (X 1 t )) ω * + V ω * πt (X 1 t ; 1 : π * ) -V ω * πt (X 1 t )|H t = E     T t     φ(X 1 t , π t (X 1 t )) ( ω t (π t ) -ω * ) + V ω * πt (X 1 t ; 1 : π * ) -V ω * πt (X 1 t ) (∆ h=2 t ) |H t        

For ∆ h=2 t we deploy the similar decomposition and upper bound as

∆ h=1 t ∆ 2 t := 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=2 t = E V ω * πt (X 2 t ; 1 : π * ) -V ω * πt (X 2 t )|X 1 t , H t rustling in ∆ h=2 t = E V ω * πt (X 2 t ; 1 : π * ) -V ω * πt (X 2 t )|X 1 t , H t ≤ E     φ(X 2 t , π t (X 2 t )) ( ω t (π t ) -ω * ) + V ω * πt (X 2 t ; 2 : π * ) -V ω * πt (X 2 t ) (∆ h=3 t ) |X 1 t , H t    

Similarly we can defined ∆ h=3 t , . . . ∆ h=H t . The condition on H t was required to come up with the mentioned decomposition through ∆ h t and it is not needed anymore, therefore;

EQUATION

Again similar to optimism we have the maximum expected cumulative reward condition on states of a episode is at most 1, we have;

BayesReg T ≤ √ HE T t min{ Φ t χ - t 1 2θ 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

EQUATION

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

BayesReg T ≤ 1 + 2 σ 2 log (T ) + d log (1 + T L 2 /λ) + λ 1/2 L ω 2T Hd log(λ + T L 2 /d)

and theorem statement follows.

B.3 DISCOUNT FACTOR:

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 R t := ΨR t ν 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 ∆ h t 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 .

B.4 PROOF OF LEMMAS:

Lemma 3. Let α ∈ R d be be an arbitrary vector and for any t ≥ 0 define

M α t := exp t i α Φ i ν i σ - 1 2 Φ i α 2 2

Then, for a stopping time under the filtration {F t } ∞ 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 α 2 2

Therefore, we can rewrite E [M α t ] as follows:

E [M α t |F t-1 ] = E D α 1 . . . D α t-1 D α t |F t-1 = D α 1 . . . D α t-1 E [D α t |F t-1 ] ≤ M α t-1

The last inequality follows since E [D 

≤ δ:

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 +

ω t -ω * χ t ≤ θ t (δ) = σ 2 log det(χ t ) 1/2 det(λI) -1/2 δ + λ 1/2 L ω

The det(χ t ) can be written as det(χ t ) = d j α j therefore, trace(χ t ) = d j α j . We also know that; Proof. Lemma 2 We have the following for the determinant of det (χ T )

det (χ T ) = det χ T -1 + Φ T Φ T = det I H + Φ T χ -1 t Φ T det χ T -1 = T t det I H + Φ 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; CP t (λ) = det(λI H -Φ t χ -1 t Φ t ). If the set {λ 1 , λ 2 , . . . , λ d } represent the eigenvalues of Φ t χ -1 t Φ t where λ i ≥ λ j if i ≥ j, one can rewrite CP t (λ) as follows;

CP (λ) = (λ -λ 1 )(λ -λ 2 ) • • • (λ -λ H )

Now by adding the matrix I H to Φ t χ -1 t Φ t , we get CP t (λ) = det(λI H -I H -Φ t χ -1 t Φ t ), therefore; 

CP t (λ) = (λ -1 -λ 1 )(λ -1 -λ 2 ) • • • (λ -1 -λ H )

:

Each input frame is a pixel-max of the two consecutive frames. We detailed the environment setting in the implementation code

To 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

This 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

Figures and Tables:

Figure 1: Thompson Sampling vs ε-greedy and Boltzmann exploration. (a) ε-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. Boltzmann exploration randomizes over actions even if the optimal action is identifies. (b) Boltzmann exploration does not incorporate uncertainties over the estimated action-values and chooses actions 5 and 6 with similar probabilities while action 6 is significantly more uncertain. Thomson Sampling is a simple remedy to all these issues. Algorithm 1 BDQN 1: Initialize θ, θ target , w a , w target a , Cov a ∀a, and B 2: for episode = 1,2,3. . . do 3:

Figure 2: BDQN deploys Thompson Sampling to, sample w a ∀a ∈ A around the empirical mean w a with w * a the underlying parameter of interest.

Figure 3: The comparison between DDQN and BDQN

Figure 4: Effect of learning rate on DDQN

Figure 5: The comparison between DDQN, BDQN and Dropout-DDQN

Figure 7: A couple of more runs of BDQN where the jump around 15M constantly happens A.8 FURTHER DISCUSSION ON REPRODUCIBILITY

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).

to Lemma 10 and 11 inAbbasi-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.

Characteristics of Thompson Sampling, ε-greedy, and Boltzmann exploration what information they use for exploration

Table content: <table><tr><td>Strategy</td><td>Greedy-Action Estimated Q-values Estimated uncertainties</td></tr><tr><td>ε-greedy</td><td/></tr><tr><td>Boltzmann exploration</td><td/></tr><tr><td>Thompson Sampling</td><td/></tr></table>

Comparison of scores and sample complexities (scores in the first two columns are average of 100 consecutive episodes). The scores of DDQN + are the reported scores of DDQN inVan Hasselt  et al. (2016)  after running it for 200M interactions at evaluation time where the ε = 0.001. Bootstrap DQN

Table content: <table/>

1st column: score ratio of BDQN to DDQN run for same number of time steps. 2nd column: score ratio of BDQN to DDQN + . 3rd column: score ratio of BDQN to human scores reported atMnih et al. (2015). 4th column: Area under the performance plot ration (AuPPr) of BDQN to DDQN. AuPPr is the integral of area under the performance plot ration. For Pong, since the scores start form -21, we shift it up by 21. 5th column: Sample complexity, SC: the number of samples the BDQN requires to beat the human score(Mnih et al., 2015)(" -" means BDQN could not beat human score). 6th column: SC + : the number of samples the BDQN requires to beat the score of DDQN + . We run both BDQN and DDQN for the same number of times steps, stated in the last column.

Table content: <table><tr><td>Game</td><td>BDQN DDQN</td><td>BDQN DDQN +</td><td>BDQN HUMAN</td><td colspan="3">AuPPr SC SC + Steps</td></tr><tr><td>Amidar</td><td>558%</td><td>788%</td><td colspan="4">325% 280% 22.9M 4.4M 100M</td></tr><tr><td>Alien</td><td>103%</td><td>103%</td><td colspan="2">43% 110%</td><td colspan="2">-36.27M 100M</td></tr><tr><td>Assault</td><td>396%</td><td>176%</td><td colspan="4">589% 290% 1.6M 24.3M 100M</td></tr><tr><td>Asteroids</td><td colspan="6">2517% 1516% 108% 680% 58.2M 9.7M 100M</td></tr><tr><td>Asterix</td><td>531%</td><td>385%</td><td colspan="4">687% 590% 3.6M 5.7M 100M</td></tr><tr><td>BeamRider</td><td>207%</td><td>114%</td><td colspan="4">150% 210% 4.0M 8.1M 70M</td></tr><tr><td>BattleZone</td><td>281%</td><td>253%</td><td colspan="4">172% 180% 25.1M 14.9M 50M</td></tr><tr><td>Atlantis</td><td colspan="6">80604% 49413% 11172% 380% 3.3M 5.1M 40M</td></tr><tr><td>DemonAttack</td><td>292%</td><td>114%</td><td colspan="4">326% 310% 2.0M 19.9M 40M</td></tr><tr><td>Centipede</td><td>114%</td><td>178%</td><td colspan="2">61% 105%</td><td>-</td><td>4.2M 40M</td></tr><tr><td>BankHeist</td><td>211%</td><td>100%</td><td colspan="4">100% 250% 2.1M 10.1M 40M</td></tr><tr><td>CrazyClimber</td><td>148%</td><td>122%</td><td colspan="4">350% 150% 0.12M 2.1M 40M</td></tr><tr><td colspan="7">ChopperCommand 14500% 1576% 732% 270% 4.4M 2.2M 40M</td></tr><tr><td>Enduro</td><td>295%</td><td>350%</td><td colspan="4">361% 300% 0.82M 0.8M 30M</td></tr><tr><td>Pong</td><td>112%</td><td>100%</td><td colspan="4">226% 130% 1.2M 2.4M 5M</td></tr><tr><td colspan="2">A.1 NETWORK ARCHITECTURE:</td><td/><td/><td/><td/></tr></table>

The comparison of BDQN, DDQN, Dropout-DDQN and random policy. Dropout-DDQN as another randomization strategy provides a deficient estimation of uncertainty and results in poor exploration/exploitation trade-off.

Table content: <table><tr><td>Game</td><td colspan="6">BDQN DDQN DDQN + Dropout-DDQN Random Policy Step</td></tr><tr><td colspan="2">CrazyClimber 124k</td><td>84k</td><td>102k</td><td>19k</td><td>11k</td><td>40M</td></tr><tr><td>Atlantis</td><td colspan="3">3.24M 39.7k 64.76k</td><td>7.7k</td><td>12.85k</td><td>40M</td></tr><tr><td>Enduro</td><td colspan="3">1.12k 0.38k 0.32k</td><td>0.27k</td><td>0</td><td>30M</td></tr><tr><td>Pong</td><td>21</td><td>18.82</td><td>21</td><td>-18</td><td>-20.7</td><td>5M</td></tr></table>

Lemma 4. [Extension to Self-normalized bound inAbbasi-Yadkori et al. (2011)] For a stopping time τ and filtration {F t } ∞ t=0 , with probability at least 1 -δ Proof. of Lemma 4. Given the definition of the parameters of self-normalized process, we can rewrite M α t as follows;Consider Ω as a Gaussian random vector and f (Ω = α) denotes the density with covariance matrix of χ -1 . DefineM t := E M Ω t |F ∞ . Therefore we have E [M t ] = E E M Ω t |Ω ≤ 1. ThereforeSince χ t and χ are positive semi definite and positive definite respectively, we have α -χ -1 t S t /σ 2 χt + α 2

Table content: <table><tr><td/><td/><td/><td/><td>S τ</td><td/><td colspan="2">2 χ -1 τ</td><td colspan="3">≤ 2σ 2 log(</td><td>det (χ t ) 1/2 det( χ) -1/2 δ</td><td>)</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="3">M α t = exp</td><td>α S t σ</td><td>-</td><td>1 2</td><td>α χt</td></tr><tr><td>M t =</td><td>R d</td><td>exp</td><td colspan="2">α S t σ</td><td colspan="2">-</td><td>1 2</td><td colspan="3">α χt f (α)dα</td></tr><tr><td>=</td><td>R d</td><td>exp</td><td>1 2</td><td colspan="7">α -χ -1 t S t /σ 2 χt +</td><td>1 2</td><td>S t /σ 2 χ -1 t</td><td>f (α)dα</td></tr><tr><td>=</td><td colspan="4">det ( χ) (2π) d exp</td><td>1 2</td><td/><td colspan="3">S t /σ χ -1 t</td><td>R d</td><td>exp</td><td>1 2</td><td>α -χ -1 t S t /σ 2 χt +</td><td>1 2</td><td>α 2 χ dα</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>χ -1 t</td><td>-S t /σ 2 ( χ+χt) -1</td></tr><tr><td>Therefore,</td><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td>M t =</td><td colspan="3">det ( χ) (2π) d exp</td><td>1 2</td><td colspan="5">S t /σ ( χ+χt) -1</td><td>R d</td><td>exp</td><td>1 2</td><td>α -χ + χ -1 t</td><td>S t /σ 2 χ+χt dα</td></tr><tr><td>=</td><td colspan="3">det ( χ) det ( χ + χ t )</td><td colspan="2">1/2</td><td colspan="2">exp</td><td>1 2</td><td colspan="2">S t /σ 2 ( χ+χt) -1</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="3">1/2 1/2 δ det ( χ)</td><td>≤</td><td>E exp 1 2 S τ /σ 2 ( χ+χτ ) -1 det( χ+χτ ) 1/2</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>δ det( χ)</td></tr></table>

where applying self normalized Lemma 4, with probability at least 1 -δ|ζ ω t -ζ ω * | ≤ ζ χ -1

Table content: <table><tr><td/><td>t</td><td/><td colspan="2">-1 t</td></tr><tr><td/><td colspan="2">Φ i Φ i + λI</td><td/><td/><td>Φ i ν i</td></tr><tr><td/><td>i</td><td/><td/><td>i</td></tr><tr><td/><td>t</td><td/><td colspan="2">-1</td></tr><tr><td>-ζ λ</td><td colspan="2">Φ i Φ i + λI</td><td/><td>ω  *</td></tr><tr><td/><td>i</td><td/><td/><td/></tr><tr><td colspan="6">As a results, applying Cauchy-Schwarz inequality and inequalities ω  *  1 λ ω  *  2 we get</td><td>χ -1 t</td><td>≤ 1 λ(χ t ) ω  *</td><td>2 ≤</td></tr><tr><td/><td>t</td><td/><td/><td/></tr><tr><td>|ζ ω t -ζ ω  *  | ≤ ζ χ -1 t</td><td colspan="2">Φ i ν i χ -1 t</td><td colspan="3">+ λ ζ χ -1 t</td><td>ω  *</td><td>χ -1 t</td></tr><tr><td/><td>i</td><td/><td/><td/></tr><tr><td/><td>t</td><td/><td/><td/></tr><tr><td>≤ ζ χ -1 t</td><td colspan="3">Φ i ν i χ -1 t</td><td colspan="2">+ λ 1/2 ω  *</td><td>2</td></tr><tr><td/><td>i</td><td/><td/><td/></tr><tr><td>t</td><td>2σ log</td><td colspan="3">1/2 det (χ t ) δ det ( χ) 1/2</td><td>+ λ 1/2 L</td></tr></table>

and the eigenvalues ofI H + Φ t χ -1 t Φ t are shifted eigenvalues of Φ t χ -1 t Φ t by +1, i.e. {λ 1 + 1, λ 2 + 1, . . . , λ d + 1}. Since ξ Φ t χ -1 t Φ t ξ = Φχ , λ 2 , . . . , λ d } are non-negative. As a results, det I H + Φ t χ -1 t Φ t ≥ 1 + Φ t χ -1

Table content: <table><tr><td/><td/><td>-1/2 t</td><td>ξ</td><td>Φχ -1/2 t</td><td>ξ all the eigenvalues</td></tr><tr><td colspan="5">{λ 1 t</td></tr><tr><td colspan="2">As a consequence;</td><td/><td/></tr><tr><td/><td>T</td><td/><td/></tr><tr><td/><td>det (χ T ) ≥ det ( χ)</td><td colspan="3">1 + Φ t χ -1 t</td></tr><tr><td/><td>t</td><td/><td/></tr><tr><td colspan="2">Moreover we have</td><td/><td/></tr><tr><td>T</td><td/><td/><td/></tr><tr><td>2</td><td>log 1 + Φ t χ -1</td><td/><td/></tr><tr><td>t</td><td/><td/><td/></tr></table>

Peer review (iclr2018):
 The authors propose a new algorithm for exploration in Deep RL. They apply Bayesian linear regression, given the last layer of a DQN network as features, to estimate the Q function for each action. Posterior weights are sampled to select actions during execution (Thompson Sampling style). I generally liked the paper and the approach, here are some more detailed comments. Unlike traditional regression, here we are not observing noisy realisations of the true target, since the algorithm is bootstrapping on non-stationary targets. It’s not immediately clear what the semantics of this posterior are then. Take for example the case where a particular transition (s,a,r,s’) gets replayed multiple times in a row, the posterior about Q(s,a) might then become overly confident even though no new observation was introduced. Previous applications of TS to MDPs (Strens, (A Bayesian framework for RL) 2000; Osband 2013) commit to a posterior sample for an episode. But the proposed algorithm samples every T_sample steps, did you find this beneficial to wait longer before resampling? It would be useful to comment on that aspect. The method is evaluated on 6 Atari games (How were the games selected? Do they have exploration challenges?) against a single baseline (DDQN). DDQN wasn’t proposed as an exploration method so it would be good to justify why this is an appropriate baseline (versus other exploration methods). The authors argue they could not reproduce Osband’s bootstrapped DQN, which is also TS-based, but you could at least have reported their scores. On these games versus (their implementation of) DDQN, the results seem encouraging. But it would be good to know whether the approach works well across games and is competitive against other stronger baselines. Alternatively, some evidence that interesting exploratory behavior is obtained (in Atari or even smaller domain) would help convince the reader that the approach does what it claims in practice. In addition, your reported score on Atlantis of ~2M seems too big. Did you cap the max episode time to 30mins? As is done in the baselines usually. Minor things: -“TS finds the true Q-function very fast” But that contradicts the previous statements, I think you mean something different. If TS does not select certain actions, the Q-function would not be updated for these actions. It might find the optimal policy quickly though, even though it doesn’t resolve the entire value function completely. -Which epsilon did you use for evaluation of DDQN in the experiments? It’s a bit suspicious that it doesn’t achieve 20+ in Pong. -The history of how to go from a Bellman equation to a sample-based update seems a bit distorted. Sample-based RL did not originate in 2008. Also, DQN does not optimize the Bellman residual, it’s a TD update.