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.
Update after feedback: I would like to thank the authors for huge work done on improving the paper. I appreciate the tight time constrains given during the discussion phase and big steps towards more clear paper, but at the current stage I keep my opinion that the paper is not ready for publication. Also variability of concerns raised by other reviewers does not motivate acceptance.
I would like to encourage the authors to make careful revision and I would be happy to see this work published. It looks very promising. 
Just an example of still unclear parts of the paper: the text between eq. (3) and (4). This describes the proposed method, together with theoretical discussions this is the main part of the paper. As a reader I would appreciate this part being written detailed, step by step.
=========================================================
The paper proposes the Bayesian version of DQN (by replacing the last layer with Bayesian linear regression) for efficient exploration. 
The paper looks very promising because of a relatively simple methodology (in the positive sense) and impressive results, but I find the paper having big issues with clarity. There are so many mistakes, typos, unclear statements and a questionable structure in the text that it is difficult to understand many parts. In the current version the paper is not ready for publication. 
In details (more in the order of appearance rather than of importance):
1. It seems that the authors use “sample” for tuples from the experience replay buffer and draws W from its posterior distribution (at least for these two purposes), which is extremely confusing
2. pp.1-2 “We show that the Bayesian regret is bounded by O(d \sqrt{N}), after N time steps for a d-dimensional feature map, and this bound is shown to be tight up-to logarithmic factors.” – maybe too many details for an abstract and introduction and it is unclear for a reader anyway at that point
3. p.1 “A central challenge in reinforcement learning (RL) is to design efficient exploration-exploitation tradeoff” – sounds too strong. Isn’t the central challenge to train an agent to get a maximum reward? It’s better to change to at least “One of central challenges”
4. p.1 “ε-greedy which uniformly explores over all the non-greedy strategies with 1 − ε probability” – it is possible, but isn’t it more conventional for an epsilon-greedy policy to take a random action with the probability epsilon and acts greedy with the probability 1 – epsilon? Moreover, later in Section 2 the authors state the opposite “where with ε probability it chooses a random action and with 1 − ε probability it chooses the greedy action based on the estimated Q function.”
5. p.1 “An action is chosen from the posterior distribution of the belief” – a posterior distribution is the belief
6. p.2 “and follow the same target objective” – if BDQN is truly Bayesian it should find a posterior distribution over weights, whereas in DDQN there is no such concept as a posterior distribution over weights, therefore, this statement does not sound right
7. p.2 “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 4” – maybe too many details for introduction (plus missing full stop at the end)
8. p.2 “This is the cost of inverting a 512 × 512 matrix every 100,000 time steps, which is negligible.” – doesn’t this depend on some parameter choices? Now the claim looks like it is true unconditionally. Also too many details for introduction
9. p.2 “On the other hand, more sophisticated Bayesian RL techniques are significantly more expensive and have not lead to large gains over DQN and DDQN.” – it would be better to justify the claim with some reference
10. Previous work presented in Introduction is a bit confusing. If the authors want to focus only on Thompson Sampling approaches, then it is unclear, why they mentioned OFU methods. If they mention OFU methods, then it is unclear why other exploration methods are not covered (in Introduction). It is better to either move OFU methods to Related Work completely, or to give a taste of other methods (for example, from Related Work) in Introduction as well
11. p.3 “Consider an MDP M as a tuple <X , A, P, P0, R, γ>, with state space X , action space A, the transition kernel P, accompanied with reward function of R, and discount factor 0 ≤ γ < 1.” – P_0 is not defined
12. p.4 “A common assumption in DNN is that the feature representation is suitable for linear classification or regression (same assumption in DDQN), therefore, building a linear model on the features is a suitable choice.” – the statement is more confusing than explaining. Maybe it is better to state that the last fully connected layer, representing linear relationship, in DQN is replaced with BLR in the proposed model
13. p.5 In eq. (3) it is better to carry definition of $\bar{w}_a$ outside the Gaussian distribution, as it is done for $\Xi_a$
14. p.5 The text between eq. (3) and (4) seems to be important for the model description and yet it is very unclear: how $a_{TS}$ is used? “we draw $w_a$ follow $a_{TS}$” – do the authors mean “following” (though it is still unclear with “following”)? What does notation $[W^T \phi^{\theta} (x_{\tau})]_{a_{\tau}}$ denote? Which time steps do the authors mean?
15. p.5 The paragraph under eq. (4) is also very confusing. “to the mean of the posterior A.6.” – reference to the appendix without proper verbal reference. Cov in Algorithm 1 is undefined, is it equal to $\Xi$? Notation in step 8 in Algorithm 1 is too complicated.
16. Algorithm 1 gives a vague idea about the proposed algorithm, but the text should be revised, the current version is very unclear and confusing
17. pp.5-6 The text of the authors' attempts to reproduce the results of others' work (from "We also aimed to implement..." to "during the course of learning and exploration") should be formalised
18. p. 6 "We report the number of samples" - which samples? W? from the buffer replay?
19. p. 6 missing reference for DDQN+
20. p. 6 definition of SC+ and references for baselines should be moved from the table caption to the main text of the paper
21. p. 6 Table 3 is never discussed, appears in a random place of the text, there should be note in its reference that it is in the appendix
22. p.6 Where is the text for footnotes 3-6?
23. p.6 Table 2 may be transposed to fit the borders
24. p.6 (and later) It is unclear why exploration in BDQN is called targeted
25. p.7 Caption of Figure 3 is not very good
26. p.7 Too small font size of axis labels and titles in plots in Figure 3 (there is still a room for 1.5 pages, moreover the paper is allowed to go beyond 10 pages due to big figures)
27. p.7 Figure 3. Why Assault has different from the others y-axis? Why in y-axis (for the others) is "per episode" and x-axis is "number of steps" (wise versa for Assault)?
27. Section 5 should go before Experiments
28. p. 7 “Where Ψ is upper triangular matrix all ones 6.” – reference 6 should be surrounded by brackets and/or preceded by "eq." and it is unclear what “all ones” means especially given than the matrix in eq. (6) does not contain only ones
29. p. 7 “Similar to the linear bandit problems,” – missing citation
30. p. 7 PSRL appears in the theorem, but is introduced only later in Related work
31. p. 7 “Proof: in Theorem. B” – proof is given in Appendix B?
32. p. 8 Theorem discussion, “grows not faster than linear in the dimension, and \sqrt(HT)” – unclear. Is it linear in the product of dimension (of what?) and \sqrt(HT)?
33. p.8 “On lower bound; since for H = 1…” – what on lower bound?
34. p.8 “our bound is order optimal in d and T” – what do the authors mean by this?
35. p.8 "while also the state of the art performance bounds are preserved" - what does it mean?
36. p.8 "To combat these shortcomings, " - which ones?
37. p.8 "one is common with our set of 15 games which BDQN outperformS it..." - what is it?
38. p.9 "Due to the computational limitations..." - it is better to remove this sentence
39. p.9 missing connection in "where the feature representation is fixed, BDQN is given the feature representation", or some parts of this sentence should be removed?
40. p.9 PAC is not introduced
41. pp.13-14 There is no need to divide Appendices A.2 and A.3. In fact, it is more confusing than helpful with the last paragraph in A.2 repeating, sometimes verbatim, the beginning of the first paragraph in A.3
42. In the experiments, do the authors pre-train their BDQN with DQN? In this case, it is unfair to say that BDQN learns faster than DDQN if the latter is not pre-trained with DQN as well. Or is pre-training with DQN is used only for hyperparameter tuning?
43. p.14 “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.” – it seems that the authors tried two learning rates for DDQN, for the one it is clear that it is set to 0.0025, another one is unclear. The word “original” is also unclear in this context. From the legend of Figure 4 it seems that the second choice for the learning rate is 0.00025, but it should be stated in the text more explicitly. The legend label “DDQN-10xlr” is not the best choice either. It is better to specify explicitly the value of the learning rate for both DDQN
44. p.15 “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.” – B samples never mentioned in Algorithm 1
45. p.15 “during the duration of 100k decision making steps, for the learning procedure,” – i) “during … duration”, ii) what did the authors meant by “decision making steps” and “the learning procedure”?, and iii) too many commas
46. p.15 “where $\tilde{T}^{sample}$, the period that of $\tilde{W}$ is sampled our of posterior” – this text does not make sense. Is “our” supposed to be “out”? “… the number of steps, after which a new $\tilde{W}$ is sampled from the posterior”?
47. p.15 “$\tilde{W}$ is being used just for making Thompson sampling actions” – could the authors be more specific about the actions here?
48. p.16 “In BDQN, as mentioned in Eq. 3, the prior and likelihood are conjugate of each others.” – it is difficult to imagine that an equation would mention anything and eq. (3) gives just the final formula for the posterior, rather than the prior and likelihood
49. p.16 The formula after “we have a closed form posterior distribution of the discounted return, ” is unclear
50. p.17 “we use ω instead of ω to avoid any possible confusion” – are there any differences between two omegas?
51. p.17 what is $\hat{b}_t$?
There are a lot of minor mistakes and typos also, I will add them as a comment since there is a limit of characters for the review.