In high-dimensional reinforcement learning settings with sparse rewards, performing effective exploration to even obtain any reward signal is an open challenge. While model-based approaches hold promise of better exploration via planning, it is extremely difficult to learn a reliable enough Markov Decision Process (MDP) in high dimensions (e.g., over 10 100 states). In this paper, we propose learning an abstract MDP over a much smaller number of states (e.g., 10
5 ), which we can plan over for effective exploration. We assume we have an abstraction function that maps concrete states (e.g., raw pixels) to abstract states (e.g., agent position, ignoring other objects). In our approach, a manager maintains an abstract MDP over a subset of the abstract states, which grows monotonically through targeted exploration (possible due to the abstract MDP). Concurrently, we learn a worker policy to travel between abstract states; the worker deals with the messiness of concrete states and presents a clean abstraction to the manager. On three of the hardest games from the Arcade Learning Environment (MONTEZUMA'S RE-VENGE, PITFALL!, and PRIVATE EYE), our approach outperforms the previous state-of-the-art by over a factor of 2 in each game. In PITFALL!, our approach is the first to achieve superhuman performance without demonstrations.
This paper considers how to effectively perform exploration in the setting where a difficult, high-dimensional MDP can be mapped to a simpler, lower-dimensional MDP. They propose a hierarchical approach where a model of the abstract MDP is incrementally learned, and then used to train sub-policies to transition between abstract states. These sub-policies are trained using intrinsic rewards for transitioning to the correct state, and the transition probabilities in the abstract MDP reflect how well a sub-policy can perform the transition. 
The approach is evaluated on three difficult Atari games, which all require difficult exploration: Montezuma's Revenge, Pitfall and Private Eye, and is shown to achieve good performance in all of them. Furthermore, the model can be used to generalize to new tasks by changing the rewards associated with different transitions. 
The main downside with this paper is that the mapping from original state (i.e. pixels) to the abstract state is assumed to be known beforehand, which requires prior knowledge. The authors hardcode this mapping for each of the games by fetching the relevant bits of information from RAM. This prevents fair comparison to many other methods which only use pixels, and makes this paper borderline rather than strong accept. 
Quality: the method is evaluated on difficult problems and shown to perform well. The experiments are thorough and explore a variety of dimensions such as robustness to stochasticity, granularity of the abstract state and generalization to new tasks. The approach does strike me as rather complicated though - it requires 19 (!) different hyperparameters as shown in table 2. The authors do mention that many of these did not require much tuning and they intend on making their code public. Still, this suggests that re-implementation or extensions by others may be challenging. Are all of these moving parts necessary?
Clarity: the paper is well-written, for the most part clear, and the details are thoroughly described in the appendix. 
Originality: this approach in the context of modern deep learning is to my knowledge novel.
Significance: This paper provides a general approach for hierarchical model-based planning when the mapping from the hard MDP to the easy one is known, and in this sense is significant. It is limited by the assumption that the mapping to abstract states is known. I suspect the complexity of the approach may also be a limiting factor. 
Pros:
+ good results on 3 challenging problems
+ effective demonstration of hierachical model-based planning
Cons:
- requires significant prior knowledge for state encoding
- complicated method
Minor:
- in the intro, last paragraph: "Our approach significantly outperforms previous non-demonstration SOTA approaches in all 3 domains". Please specify that you use extra knowledge extracted from RAM, otherwise this is misleading. 
- Algorithm 1: nagivate -> navigate
- Section 4, last sentence: broken appendix link. 
- Bottom of page 6: "Recent work on contextual MDPs...as we do here" is not a sentence. 
- In related work, it would be nice to mention some relevant early work by Schmidhuber on subgoal generation: http://people.idsia.ch/~juergen/subgoals.html
*** Updated ***
After reading the updated paper, responses, other reviews, and looking at related works more closely, I have changed my score to a 5. This is due to several factors. 
Although the paper's core idea is definitely interesting, the fact that they use hardcoded features, rather the standard setup which uses pixels, makes comparison to other methods much more complicated. In particular, I think that the comparison to DQN-PixelCNN is unfair, as this other method makes very few assumptions about the inputs (only that they are pixels). The authors sort of point this out in the main text, but this is somewhat misleading. They say "PixelCNN uses less prior knowledge than our approach". In fact, it uses as much prior knowledge as any RL method which operates on pixels. Granted, this is nonzero, but it's vastly less than what this paper's method assumes. The other comparison is to SOORL (which uses a different state encoding altogether). The comparison to SmartHash is fairer, although the variant of SmartHash they compare against is not the main method the paper proposes (a generic autoencoder-based state encoding which makes minimal assumptions about the input). It would have been better if the authors included experiments for their method using such a learned state encoding.
Reporting SOTA results on very hard tasks using extra hardcoded features or other domain knowledge is potentially misleading to the community as to how far along we are in solving these tasks, and extra care should be taken to put these results in context. Otherwise, for those not familiar with the subtleties, this makes it seem like these tasks are being solved when in fact they are not. My concern is that other works may then be asked to be compared against these artificially high results. Having many different task setups also makes comparison between different published works confusing in general. Other works (such as Ostrovski et al) have been able to make progress on these tasks while staying within the standard pixel-based framework.
These concerns would have been partially mitigated had the authors made it *very* clear that they were assuming substantial prior knowledge, which makes their method non-comparable to others which do not make this assumption. This could have been done in the introduction (which was one of my comments, but this was not included in the updated draft). I.e., something to the effect of "We emphasize that our approach assumes substantially more prior knowledge than other approaches which operate only on pixels, and as such is not directly comparable with these approaches". In addition, I would have liked if the authors had followed the suggestion of Reviewer 1 to include results in pixel space, even if negative, but this was not done either (using a simple autoencoder-based representation, like the one in the SmartHash paper, would have also been fine). As it is, statements such as "Our approach achieves more than 2x the reward of prior non-demonstration SOTA approaches" and "our approach relies on some prior knowledge in the state abstraction function, although we compare against SOTA methods using a similar amount of prior knowledge in our experiments" are quite misleading and unfair to other methods which do not assume access to prior knowledge (the second statement is untrue for the case of DQN-PixelCNN). 
Another point which I had not noticed previously is the very high sample complexity (2 billion). One of the motivations behind model-based approaches is that they are supposed to be more sample efficient, but that does not seem to be the case here.