Common approaches to Reinforcement Learning (RL) are seriously challenged by large-scale applications involving huge state spaces and sparse delayed reward feedback. Hierarchical Reinforcement Learning (HRL) methods attempt to address this scalability issue by learning action selection policies at multiple levels of temporal abstraction. Abstraction can be had by identifying a relatively small set of states that are likely to be useful as subgoals, in concert with the learning of corresponding skill policies to achieve those subgoals. Many approaches to subgoal discovery in HRL depend on the analysis of a model of the environment, but the need to learn such a model introduces its own problems of scale. Once subgoals are identified, skills may be learned through intrinsic motivation, introducing an internal reward signal marking subgoal attainment. In this paper, we present a novel model-free method for subgoal discovery using incremental unsupervised learning over a small memory of the most recent experiences of the agent. When combined with an intrinsic motivation learning mechanism, this method learns subgoals and skills together, based on experiences in the environment. Thus, we offer an original approach to HRL that does not require the acquisition of a model of the environment, suitable for large-scale applications. We demonstrate the efficiency of our method on two RL problems with sparse delayed feedback: a variant of the rooms environment and the ATARI 2600 game called Montezuma's Revenge.
This paper proposes an unsupervised method for subgoal discovery and shows how to combine it with a model-free hierarchical reinforcement learning approach. The main idea behind the subgoal discovery approach is to first build up a buffer of “interesting” states using ideas from anomaly detection. The states in the buffer are then clustered and the centroids are taken to be the subgoal states.
Clarity:
I found the paper somewhat difficult to follow. The main issue is that the details of the algorithm are scattered throughout the paper with Algorithm 1 describing the method only at a very high level. For example, how does the algorithm determine that an agent has reached a goal? It’s not clear from the algorithm box. Some important details are also left out. The section on Montezuma’s Revenge mentioned that the goal set was initialized using a “custom edge detection algorithm”. What was the algorithm? Also, what exactly is being clustered (observations or network activations) and using what similarity measure? I can’t find it anywhere in the paper. Omissions like this make the method completely unreproducible. 
Novelty:
The idea of using clustering to discover goals in reinforcement learning is quite old and the paper does a poor job of citing the most relevant prior work. For example, there is no mention of “Dynamic Abstraction in Reinforcement Learning via Clustering” by Mannor et al. or of “Learning Options in Reinforcement Learning” by Stolle and Precup (which uses bottleneck states as goals). The particular instantiation of clustering interesting states used in this paper does seem to be new but it is important to do a better job of citing relevant prior work and the overall novelty is still somewhat limited.
Significance:
I was not convinced that there are significant ideas or lessons to be taken away from this paper. The main motivation was to improve scalability of RL and HRL to large state spaces, but the experiments are on the four rooms domain and the first room of Montezuma’s Revenge, which is not particularly large scale. Existing HRL approaches, e.b. Feudal Networks from Vezhnevets et al. have been shown to work on a much wider range of domains. Further, it’s not clear how this method could address scalability issues. Repeated clustering could become expensive and it’s not clear how the number of clusters affects the approach as the complexity of the task increases. I would have liked to see some experiments showing how the performance changes for different numbers of clusters because setting the number of clusters to 4 in the four rooms task is a clear use of prior knowledge about the task.
Overall quality:
The proposed approach is based on a number of heuristics and is potentially brittle. Given that there are no ablation experiments looking at how different choices (number of clusters/goals, how outliers are selected, etc) I’m not sure what to take away from this paper. There are just too many seemingly arbitrary choices and moving parts that are not evaluated separately.
Minor comments:
- Can you back up the first sentence of the abstract? AlphaGo/AlphaZero do well on the game of Go which has ~10^170 valid states.
- First sentence of introduction. How can the RL problem have a scaling problem? Some RL methods might, but I don’t understand what it means for a problem to have scaling issues.
- Please check your usage of \cite and \citep. Some citations are in the wrong format.
- The Q-learning loss in section 2 is wrong. The parameters of the target (r+\gamma max Q) are held fixed in Q-learning.