Venue: ICLR 2017 conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: This paper proposed to use a simple count-based exploration technique in high-dimensional RL application (e.g., Atari Games). The counting is based on state hash, which implicitly groups (quantizes) similar state together. The hash is computed either via hand-designed features or learned features (unsupervisedly with auto-encoder). The new state to be explored receives a bonus similar to UCB (to encourage further exploration).

Overall the paper is solid with quite extensive experiments. I wonder how it generalizes to more Atari games. Montezuma’s Revenge may be particularly suitable for approaches that implicitly/explicitly cluster states together (like the proposed one), as it has multiple distinct scenarios, each with small variations in terms of visual appearance, showing clustering structures. On the other hand, such approaches might not work as well if the state space is fully continuous (e.g. in RLLab experiments). 

The authors did not answer my question about why the hash code needs to be updated during training. I think it is mainly because the code still needs to be adaptive for a particular game (to achieve lower reconstruction error) in the first few iterations . After that stabilization is the most important. Sec. 2.3 (Learned embedding) is quite confusing (but very important). I hope that the authors could make it more clear (e.g., by writing an algorithm block) in the next version.
review_title: Solid paper

final_score: rating: null
review_content: Apologies for the (very) late questions!

For the learned embedding:

1. U(-0.3, 0.3) ? Why the magnitude of 0.3, and why uniform? This seems arbitrary.. did you try others? Is this what people have used in the past? Is this domain(Atari)-dependent?

2a. Can you explain p(s_i) in the autoencoder loss of Equation (4)? Normally MSE is used for reconstruction, so I don't know how to interpret p(s_i) here, and it is never defined.
2b. After some digging, I suspect there is a softmax distribution per pixel? Is the output of these distributions a probability per pixel value (0-255)? And is p(s_i) then a sum of likelihoods over all the pixels? If so, this should be explained in more detail here. PixelCNN is still quite new so p(s_i) should either be defined formally or at the very least described in a sentence.

3. "Because the code dimension often needs to be large in order to correctly reconstruct the input, we apply a downsampling procedure to the resulting code, either through random projection to a lower-dimensional space or through grouping bits together." Ok, so which one is it: random projection or grouping bits together? Can you elaborate and give some details here? This section is quite lacking in details.. it might be difficult to reproduce this. If the details come later in the paper, I recommend referring to the section here. Otherwise, it could leave the reader confused.


review_title: Clarifications for Sec 2.3

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper proposes a new exploration scheme for reinforcement learning using locality-sensitive hashing states to build a table of visit counts which are then used to encourage exploration in the style of MBIE-EB of Strehl and Littman.

Several points are appealing about this approach: first, it is quite simple compared to the current alternatives (e.g. VIME, density estimation and pseudo-counts). Second, the paper presents results across several domains, including classic benchmarks, continuous control domains, and Atari 2600 games. In addition, there are results for comparison from several other algorithms (DQN variants), many of which are quite recent. The results indicate that the approach clearly improves over the baseline. The results against other exploration algorithms are not as clear (more dependent on the individual domain/game), but I think this is fine as the appeal of the technique is its simplicity. Third, the paper presents results on the sensitivity to the granularity of the abstraction.

I have only one main complaint, which is it seems there was some engineering involved to get this to work, and I do not have much confidence in the robustness of the conclusions. I am left uncertain as to how the story changes given slight perturbations over hyper-parameter values or enabling/disabling of certain choices. For example, how critical was using PixelCNN (or tying the weights?) or noisifying the output in the autoencoder, or what happens if you remove the custom additions to BASS? The granularity results show that the choice of resolution is sensitive, and even across games the story is not consistent.

The authors decide to use state-based counts instead of state-action based counts, deviating from the theory, which is odd because the reason to used LSH in the first place is to get closer to what MBIE-EB would advise via tabular counts. There are several explanations as to why state-based versus state-action based counts perform similarly in Atari; the authors do not offer any. Why?

It seems like the technique could be easily used in DQN as well, and many of the variants the authors compare to are DQN-based, so omitting DQN here again seems strange. The authors justify their choice of TRPO by saying it ensures safe policy improvement, though it is not clear that this is still true when adding these exploration bonuses.

The case study on Montezuma's revenge, while interesting, involves using domain knowledge and so does not really fit well with the rest of the paper.

So, in the end, simple and elegant idea to help with exploration tested in many domains, though I am not certain which of the many pieces are critical for the story to hold versus just slightly helpful, which could hurt the long-term impact of the paper.

--- After response:

Thank you for the thorough response, and again my apologies for the late reply.

I appreciate the follow-up version on the robustness of SimHash and state counting vs. state-action counting.

The paper addresses an important problem (exploration), suggesting a "simple" (compared to density estimation) counting method via hashing. It is a nice alternative approach to the one offered by Bellemare et al. If discussion among reviewers were possible, I would now try to assemble an argument to accept the paper. Specifically, I am not as concerned about beating the state of the art in Montezuma's as Reviewer3 as the merit of the current paper is one the simplicity of the hashing and on the wide comparison of domains vs. the baseline TRPO. This paper shows that we should not give up on simple hashing. There still seems to be a bunch of fiddly bits to get this to work, and I am still not confident that these results are easily reproducible. Nonetheless, it is an interesting new contrasting approach to exploration which deserves attention.

Not important for the decision: The argument in the rebuttal concerning DQN & A3C is a bit of a straw man. I did not mention anything at all about A3C, I strictly referred to DQN, which is less sensitive to parameter-tuning than A3C. Also, Bellemare 2016 main result on Montezuma used DQN. Hence the omission of these techniques applied to DQN still seems a bit strange (for the Atari experiments). The figure S9 from Mnih et al. points to instances of asynchronous one-step Sarsa with varied thread counts.. of course this will be sensitive to parameters: it is both asynchronous online algorithms *and* the parameter varied is the thread count! This is hardly indicative of DQN's sensitivity to parameters, since DQN is (a) single-threaded (b) uses experience replay, leading to slower policy changes. Another source of stability, DQN uses a target network that changes infrequently. Perhaps the authors made a mistake in the reference graph in the figure? (I see no Figure 9 in https://arxiv.org/pdf/1602.01783v2.pdf , I assume the authors meant Figure S9)
review_title: Final review: significant results in an important problem, but many moving parts

final_score: rating: null
review_content: I assume pixel-SimHash is to use the entire image as input to SimHash without any preprocessing. Is this correct? For learned embedding, from Eqn.4 it seems that from the optimization of AE, we already get a binary representation for each state. So why there is an additional step applying SimHash on (almost) binarized code b(s)? From the context, Eqn. 4 needs to be optimized online while RL training is running, but Alg. 1 does not make it explicit. How often does Eqn. 4 gets optimized? I assume it is after every episode but is it true? From the text it seems that the binary code needs to be consistent during the training, which is not required if the code is updated between episodes.
review_title: Confusion about the algorithm

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper introduces a new way of extending the count based exploration approach to domains where counts are not readily available. The way in which the authors do it is through hash functions. Experiments are conducted on several domains including control and Atari. 

It is nice that the authors confirmed the results of Bellemare in that given the right "density" estimator, count based exploration can be effective. It is also great the observe that given the right features, we can crack games like Montezuma's revenge to some extend.

I, however, have several complaints:

First, by using hashing, the authors did not seem to be able to achieve significant improvements over past approaches. Without "feature engineering", the authors achieved only a fraction of the performance achieved in Bellemare et al. on Montezuma's Revenge. The proposed approaches In the control domains, the authors also does not outperform VIME. So experimentally, it is very hard to justify the approach. 

Second, hashing, although could be effective in the domains that the authors tested on, it may not be the best way of estimating densities going forward. As the environments get more complicated, some learning methods, are required for the understanding of the environments instead of blind hashing. The authors claim that the advantage of the proposed method over Bellemare et al. is that one does not have to design density estimators. But I would argue that density estimators have become readily available (PixelCNN, VAEs, Real NVP, GANs) that they can be as easily applied as can hashing. Training the density estimators is not difficult problem as more.


review_title: Review

Meta-review: The paper proposes a simple approach to exploration that uses a hash of the current state within a exploration bonus approach (there are some modifications to learned hash codes, but this is the basic approach). The method achieves reasonable performance on Atari game tasks (sometimes outperformed by other approaches, but overall performing well), and it's simplicity is its main appeal (although the autoencoder-based learned hash seems substantially less simple, so actually loses some advantage there). 
 
 The paper is likely borderline, as the results are not fantastic: the approach is typically outperformed or similarly-performed by one of the comparison approaches (though it should be noted that no comparison approach performs well over all tasks, so this is not necessarily that bad). But overall, especially because so many of these methods have tunable hyperparameters it was difficult to get a clear understanding of just how these experimental results fit.
 
 Pros:
 + Simple method for exploration that seems to work reasonably well in practice
 + Would have the potential to be widely used because of its simplicity
 
 Cons:
 - Improvements over previous approaches are not always there, and it's not clear whether the algorithm has any "killer app" domain where it is just clearly the best approach
  
 Overall, this work in its current form is too borderline. The PCs encourage the authors to strengthen the empirical validation and resubmit.
Decision: Reject