Common approaches to Reinforcement Learning (RL) are seriously challenged bylarge-scale applications involving huge state spaces and sparse delayed rewardfeedback. Hierarchical Reinforcement Learning (HRL) methods attempt to addressthis scalability issue by learning action selection policies at multiple levelsof temporal abstraction. Abstraction can be had by identifying a relativelysmall set of states that are likely to be useful as subgoals, in concert withthe learning of corresponding skill policies to achieve those subgoals. Manyapproaches to subgoal discovery in HRL depend on the analysis of a model of theenvironment, but the need to learn such a model introduces its own problems ofscale. Once subgoals are identified, skills may be learned through intrinsicmotivation, introducing an internal reward signal marking subgoal attainment.In this paper, we present a novel model-free method for subgoal discovery usingincremental unsupervised learning over a small memory of the most recentexperiences (trajectories) of the agent. When combined with an intrinsicmotivation learning mechanism, this method learns both subgoals and skills,based on experiences in the environment. Thus, we offer an original approach toHRL that does not require the acquisition of a model of the environment,suitable for large-scale applications. We demonstrate the efficiency of ourmethod on two RL problems with sparse delayed feedback: a variant of the roomsenvironment and the first screen of the ATARI 2600 Montezuma's Revenge game.