Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: #rebuttal responses
 I am pleased by the authors' responses. Thus I change the score to weak accept.

#review
This paper presented OPIQ, a model-free algorithm that does not rely on an optimistic initialization
to ensure efficient exploration. OPIQ augments the Q-values with a new count-based optimism bonus. 
OPIO is ensured with good sample efficiency in the tabular setting. Experimental results show that OPIQ drives
better exploration than DQN variants that utilize a pseudo count-based intrinsic motivation in the randomized chain and the maze environment.

The new optimism bonus is interesting and convincing with a good theoretical guarantee. The paper would be more clear if the authors add a motivating example in a tabular environment. That is, why does this extra optimism bonus help to predict optimistic estimates for novel state and action pairs. 

I appreciate that the authors compare extensive DQN variants using count-based explorations. But the experimental results are somewhat weak, as there are no comparison results on hard Atari games, such as freeway and Montezuma's revenge.

I am willing to improve the score if the authors show better motivation or results on Atari games.
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: The paper proposes a method to optimistically initialize Q-values for unseen state actions for the case of Deep Q-Networks (DQNs) with high dimensional state representations, in order to step closer towards the optimistic initializations in the tabular Q-learning case which have proven guarantees of convergence. The paper shows that simple alternatives such as adding a bias to a DQN do not help as the generalization to novel states usually reduces the optimism of unvisited state-actions. Instead, a separate optimistic Q function is proposed that is an addition of two parts - a Deep Q-network which may be pessimistically initialized (in the worst case) and a term with pseudo-counts of state-actions that together form an optimistic estimate of novel state-actions. For the tabular case, the paper shows a convergence with guarantees similar to UCB-H (Jin et. al., 2018). This optimistic Q-function is used during action selection as well as bootstrapping in the n-step TD update.

I vote for weak accept as this paper does a great job at demonstrating the motivation, simple examples and thorough comparisons for their proposed “OPIQ” model on simple environments such as the Randomized Chain (from Shyam et. al., 2019) and a 2D maze grid. While the experiments are in toy settings, the connection to UCB-H and the novel optimistic Q-function and it’s training formulation make the contributions of this paper significant.

However, my confidence on this rating is low as I have not gone through the theorem in the appendix and I may be wrong in judging the amount of empirical evidence required for the approach.

While the paper does cover a lot of ground with important details and clear motivation, a lot of the desired experiments have been left to future work as mentioned in the paper. This, in addition to the experiments on just toy settings, is not sufficient to conclude that this approach may be applicable to actually high dimensional state spaces where pseudo counts do not work well. Ultimately, the proposed approach relies strongly on good pseudo-count estimates in high dimensional state spaces, which is still an open problem.

review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: Optimistic Exploration even with a Pessimistic Initialisation
================================================================

This paper presents an exploration algorithm based on "optimism in the face of uncertainty" via count-based bonus.
The authors observe that typical neural net initializations close to zero can be pessimistic, but show that augmenting a count-based bonus for acting and bootstrapping can overcome this.
The authors support their claim with an adaptation of a regret bound for the tabular case, and a series of didactic experiments with neural net models.


There are several things to like about this paper:
- Exploration with generalization in Deep RL is a large outstanding problem, with few effective options and none really commonly used in the field beyond epsilon-greedy or Boltzmann.
- This algorithm is reasonably well thought out, building on an established literature of exploration bonuses, but with a slightly different take on the structure of the bonus.
- The paper is well structured, building from intuition to theory to toy examples in DQN setting.
- Overall the algorithm appears to perform well against a wide variety of related variants (although that presentation is a little confusing / overwhelming).


There are several places the paper might be improved:
- I don't think the authors make a clear enough case for why this method is *better* than the other optimistic bonus approaches listed... Yes there is a regret bound, but this is not as good as some other methods... Yes there are ablations... but they're not really clear about what the mechanism that makes this method better than others!
- Although this algorithm is motivated by applications to *deep* RL, the key choice of the "count" (and thus the method for optimism bonus) is mostly sidestepped. It amounts to an essentially tabular bonus in the space of the hashing function... and it's not clear why this approach should work any better or worse than other similar approaches that the paper complains about. For example, if you used "Randomized Prior Functions" or "Random Network Distillation" with that same hashing functions you would likely end up with similar results?
- The comparison to benchmark algorithms seems quite confusing and I'm not sure if it's really presented well. It might be good to focus on fewer comparisons at a time and push remaining less important ones to the appendix.
- It would be great to get an evaluation of these algorithms on a standardized and open-source benchmark... and I think that bsuite could be a really good candidate for this paper https://github.com/deepmind/bsuite particularly the "deep sea" experiments.


Overall I think this is a reasonable paper, and I expect it to improve during the review process.
At the moment I have to say that I don't think there is a clear enough case for why this method is preferable to other similar approaches, or enough insight into the pros and cons to accept.

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

Updating to "weak accept" as part of rebuttal.
review_title: Official Blind Review #2

Meta-review: The paper propose a scheme to enable optimistic initialization in the deep RL setting, and shows that it's helpful.

The reviewers agreed that the paper is well-motivated and executed, but had some minor reservations (e.g. about the proposal scaling in practice). In an example of a successful rebuttal two of the reviewers raised their scores after the authors clarified the paper and added an experiment on Montezuma's revenge.

The paper proposes a useful, simple and practical idea on the bridge between tabular and deep RL, and I gladly recommend acceptance.
Decision: Accept (Poster)