Introduction
Reinforcement Learning (RL) often struggles in complex environments characterized by sparse rewards, where an agent may explore for extended periods without receiving feedback. Hierarchical Reinforcement Learning (HRL) addresses this by decomposing large tasks into smaller, manageable subgoals—for instance, requiring an agent to "find the key" before attempting to "open the door."
A significant challenge in HRL is the "chicken and egg" problem: discovering useful subgoals typically requires a mathematical model of the environment's state transitions. However, building such a model is often as complex as the original task. This paper proposes a model-free approach to subgoal discovery and hierarchical representation learning, relying solely on the agent's raw experience.
The Hierarchical Framework
The authors propose a two-level architecture designed to handle complex tasks without a world model:
- The Meta-Controller: Acting as a high-level supervisor, it observes the environment and selects a subgoal ($g$) from a discovered set. It utilizes Temporal Difference (TD) learning to determine which subgoals are most likely to lead to the final objective.
- The Controller: This low-level component receives the subgoal and executes specific actions to achieve it. It is driven by intrinsic motivation, receiving internal rewards upon successfully reaching the assigned subgoal.
Subgoal Discovery Mechanism
The core innovation lies in how subgoals are identified without a transition model. The agent maintains a memory of recent transitions and applies two unsupervised techniques:
- Anomaly Detection: The system identifies "outlier" states where the agent experiences sudden changes in reward, such as picking up a key. These anomalies often signal significant milestones.
- Incremental Clustering ($K$-means): By grouping similar experiences, the agent identifies "bottleneck" states—such as doorways in a navigation task—which naturally serve as effective subgoals.
Experimental Evaluation
The method was primarily evaluated in a "Rooms" grid-world environment. The agent's task is to navigate through four rooms to pick up a key and then reach a car. This requires multi-step planning and the identification of critical milestones.
The results demonstrate that the unsupervised algorithm correctly identified the key ($r = +10$) and the car ($r = +40$) as anomalous subgoals (see Figure 1b). Furthermore, $K$-means clustering successfully pinpointed the doorways between rooms as candidate subgoals (see Figure 1d). The agent learned both the subgoals and the necessary skills to reach them simultaneously, effectively navigating a task that typically defeats standard "flat" RL agents.
Conclusion and Future Work
This model-free approach offers a scalable path toward solving high-dimensional RL problems by avoiding the need for complex transition models. While the current implementation relies on a memory of recent experiences and adds some computational overhead for clustering, it demonstrates significant potential for tasks with sparse rewards. Future work will focus on scaling these techniques to visual inputs, such as the Atari 2600 benchmark Montezuma’s Revenge, and further integrating internal representation learning.
Summary updated