Venue: ICLR 2018 conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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. 

review_title: A nice algorithm. Decent preliminary results, but some more validation would be welcome.

final_score: rating: 5: Marginally below acceptance threshold
review_content: 
The authors describe how to use Bayesian neural networks with Thompson sampling
for efficient exploration in q-learning. The Bayesian neural networks are only
Bayesian in the last layer. That is, the authors learn all the previous layers
by finding point estimates. The Bayesian learning of the last layer is then
tractable since it consists of a linear Gaussian model. The resulting method is
called BDQL. The experiments performed show that the proposed approach, after
hyper-parameter tuning, significantly outperforms the epsilon-greedy
exploration approaches such as DDQN.

Quality:

I am very concern about the authors stating on page 1 "we sample from the
posterior on the set of Q-functions". I believe this statement is not correct.
The Bayesian posterior distribution is obtained by combining an assumed
generative model for the data, data sampled from that model and some prior
assumptions. In this paper there is no generative model for the data and the
data obtained is not actually sampled from the model. The data are just targets
obtained by the q-learning rule. This means that the authors are adapting
Q-learning methods so that they look Bayesian, but in no way they are dealing
with a principled posterior distribution over Q-functions. At least this is my
opinion, I would like to encourage the authors to be more precise and show in
the paper what is the exact posterior distribution over Q-functions and show
how they approximate that distribution, taking into account that a posterior
distribution is obtained as $p(theta|D) \propto p(D|theta)p(\theta)$. In the
case addressed in the paper, what is the likelihood $p(D|\theta)$ and what are
the modeling assumptions that explain how $D$ is generated by sampling from a
model parameterized by \theta?

I am also concerned about the hyper-parameter tuning for the baselines. In
section 5 (choice of hyper-parameters) the authors describe a quite exhaustive
hyper-parameter tuning procedure for BDQL. However, they do not mention whether
they perform a similar hyper-parameter tuning for DDQN, in particular for the
parameter epsilon which will determine the amount of exploration. This makes me
wonder if the comparison in table 2 is fair. Especially, because the authors
tune the amount of data from the replay-buffer that is used to update their
posterior distribution. This will have the effect of tuning the width of their
posterior approximation which is directly related to the amount of exploration
performed by Thompson sampling. You can, therefore, conclude that the authors are
tuning the amount of exploration that they perform on each specific problem.
Is that also being done for the baseline DDQN, for example, by tuning epsilon in
each problem?

The authors also report in table 2 the scores obtained for DDQN by Osband et
al. 2016. What is the purpose of including two rows in table 2 with the same
method? It feels a bit that the authors want to hide the fact that they only
compare with a singe epsilon-greedy baseline (DDQN). Epsilon-greedy methods
have already been shown to be less efficient than Bayesian methods with
Thompson sampling for exploration in q learning (Lipton et al. 2016).

The authors do not compare with variational approaches to Bayesian learning
(Lipton et al. 2016). They indicate that since Lipton et al. "do not
investigate the Atari games, we are not able to have their method as an
additional baseline". This statement seems completely unjustified. The authors
should clearly include a description of why Lipton's approach cannot be applied
to the Atari games or include it as a baseline. 

The method proposed by the authors is very similar to Lipton's approach. The
only difference is that Lipton et al. use variational inference with a
factorized Gaussian distribution to approximate the posterior on all the
network weights. The authors by contrast, perform exact Bayesian inference, but
only on the last layer of their neural network. It would be very useful to know
whether the exact linear Gaussian model in the last layer proposed by the
authors has advantages with respect to a variational approximation on all the
network weights. If Lipton's method would be expensive to apply to large-scale
settings such as the Atari games, the authors could also compare with that
method in smaller and simpler problems.

The plots in Figure 2 include performance in terms of episodes. However, it
would also be useful to know how much is the extra computational costs of
the proposed method. One could imagine that computing the posterior
approximation in equation 6 has some additional cost. How do BDQN and DDQN
compare when one takes into account running time and not episode count into
account?

Clarity:

The paper is clearly written. However, I found a lack of motivation for the
specific design choices made to obtain equations 9 and 10. What is a_t in
equation 9? The parameters \theta are updated just after equation 10 by
following the gradient of the loss in which the weights of the last layer are
fixed to a posterior sample, instead of the posterior mean. Is this update rule
guaranteed to produce convergence of \theta? I could imagine that at different
times, different posterior samples of the weights will be used to compute the
gradients. Does this create any instability in learning? 

I found the paragraph just above section 5 describing the maze-like
deterministic game confusing and not very useful. The authors should improve
this paragraph.

Originality:

The proposed approach in which the weights in the last layer of the neural
network are the only Bayesian ones is not new. The same method was proposed in

Snoek, J., Rippel, O., Swersky, K., Kiros, R., Satish, N., Sundaram, N., ... &
Adams, R. (2015, June). Scalable Bayesian optimization using deep neural
networks. In International Conference on Machine Learning (pp. 2171-2180).

which the authors fail to cite. The use of Thompson sampling for efficient
exploration in deep Q learning is also not new since it has been proposed by
Lipton et al. 2016. The main contribution of the paper is to combine these two
methods (equations 6-10) and evaluate the results in the large-scale setting of
ATARI games, showing that it works in practice.

Significance:

It is hard to determine how significant the work is since the authors only
compare with a single baseline and leave aside previous work on efficient
exploration with Thompson sampling based on variational approximations.

As far as the method is described, I believe it would be impossible to
reproduce their results because of the complexity of the hyper-parameter tuning
performed by the authors. I would encourage the authors to release code that can
directly generate Figure 2 and table 2.

review_title: Interesting idea but lack of baselines, strong theoretical justification and reference to previous work

final_score: rating: 5: Marginally below acceptance threshold
review_content: (Last minute reviewer brought in as a replacement).

This paper proposed "Bayesian Deep Q-Network" as an approach for exploration via Thompson sampling in deep RL.
This algorithm maintains a Bayesian posterior over the last layer of the neural network and uses that as an approximate measure of uncertainty.
The agent then samples from this posterior for an approximate Thompson sampling.
Experimental results show that this outperforms an epsilon-greedy baseline.

There are several things to like about this paper:
- The problem of efficient exploration with deep RL is important and under-served by practical algorithms. This seems like a good algorithm in many ways.
- The paper is mostly clear and well written.
- The experimental results are impressive in their outperformance.

However, there are also some issues, many of which have already been raised:
- The poor performance of the DDQN baseline is concerning and does not seem to match the behavior of prior work (see Pong for example).
- There are some loose and misleading descriptions of the algorithm computing "the posterior" when actually this is very much an approximation method... that's OK to have approximations but it shouldn't be hidden away.
- The connection to RLSVI is definitely understated, since with a linear architecture this is precisely RLSVI. The sentiment that extending TS to larger spaces hasn't been fully explored is definitely valid... but this line of work should certainly be mentioned in the 4th paragraph. RLSVI is provably-efficient with a state-of-the-art regret bound for tabular learning - you would probably strengthen the case for this algorithm as an extension of RLSVI by building on this connection... otherwise it's a bit adhoc to justify this approximation method.
- This paper spends a lot of time re-deriving Bayesian linear regression in a really standard way... and without much discussion of how/why this method is an approximation (it is) especially when used with deep nets.

Overall, I like this paper and the approach of extending TS-style algorithms to Deep RL by just taking the final layer of the neural network.
However, it also feels like there are some issues with the baselines + being a bit more clear about the approximations / position relative to other algorithms for approximate TS would be a better approach.
For example, in linear networks this is the same as RLSVI, bootstrapped DQN is one way to extend this idea to deep nets, but this is another one and it is much better because XYZ. (this discussion could perhaps replace the rather mundane discussion of BLR, for example).

In it's current state I'd say marginally above, but wouldn't be surprised if these changes turned it into an even better paper quite quickly.


===============================================================

Revising my review following the rebuttal period and also the (ongoing) revisions to the paper.

I've been disappointed by the authors have incorporated the feedback/reviews - I expected something a little more clear / honest. Given the ongoing review decisions/issues I'm putting my review slightly below accept.

## Relation to literature on "randomized value functions"
It's really wrong to present BDQN as is if it's the first attempt at large-scale approximations to Thompson sampling (and then slip in a citation to RLSVI as a BDQN-like algorithm). This algorithm is a form of RLSVI (2014) where you only consider uncertainty over the last (linear) layer - I think you should present it like this. Similarly *some* of the results for Bootstrapped DQN (2016) on Atari are presented without bootstrapping (pure ensemble) but this is very far from an essential part of the algorithm! If you say something like "they did not estimate a true posterior" then you should quantify this and (presumably) justify the implication that taking a gaussian approximation to the final layer is a *true* posterior. In a similar vein, you should be clear about the connections to Lipton et al 2016 as another method for approximate Bayesian posteriors in DQN.

## Quality/science of experiments
The experimental results have been updated, and the performance of the baseline now seems much more reasonable. However, the procedure for "selecting arbitrary number of frames" to report performance seems really unnecessary... it would be clear that BDQN is outperforming DDQN... you should run them all for the same number of frames and then either compare (final score, cumulative score, #frames to human) or something else more fair/scientific. This type of stuff smells like overfitting!
review_title: Interesting approach for Thompson sampling in DQN, some concerns over baseline.

final_score: rating: null
review_content: "Shallow Updates for Deep Reinforcmeent Learning"
https://arxiv.org/pdf/1705.07461.pdf

This work on LS-DQN follows a (relatively) similar narrative of using a Least-Squares RL on the last layer of DQN.
You might consider that this paper on Bayesian DQN is similar to an RLSVI-version of LS-DQN.

I was not aware of this until recently.
review_title: [Late] another paper to discuss / cite

Meta-review: This work develops a methodology for exploration in deep Q-learning through Thompson sampling to learn to play Atari games.  The major innovation is to perform a Bayesian linear regression on the last layer of the deep neural network mapping from frames to Q-values.  This Bayesian linear regression allows for efficiently drawing (approximate) samples from the network.  A careful methodology is presented that achieves impressive results on a subset of Atari games.

The initial reviews all indicated that the results were impressive but questioned the rigor of the empirical analysis and the implementation of the baselines.  The authors have since improved the baselines and demonstrated impressive results across more games but questions over the empirical analysis remain (by AnonReviewer3 for instance) and the results still span only a small subset of the Atari suite.  The reviewers took issue with the treatment of related work, placing the contributions of this paper in relation to previous literature.

In general, this paper shows tremendous promise, but is just below borderline.  It is very close to a strong and impressive paper, but requires more careful empirical work and a better treatment of related work.  Hopefully the reviews and the discussion process will help make the paper much stronger for a future submission.

Pros:
- Very impressive results on a subset of Atari games
- A simple and elegant solution to achieving approximate samples from the Q-network
- The paper is well written and the methodology is clearly explained

Cons:
- Questions remain about the rigor of the empirical analysis (comparison to baselines)
- Requires more thoughtful comparison in the manuscript to related literature
- The theoretical justification for the proposed methods is not strong
Decision: Reject