Introduction
Reinforcement Learning (RL) excels at many tasks but struggles significantly with "sparse rewards"—scenarios where an agent only receives a signal upon reaching a final goal. In complex environments, an agent might wander for millions of steps without ever seeing a reward, making learning nearly impossible.
While Imitation Learning (IL) uses expert demonstrations to jumpstart the process, it suffers from compounding errors (where small mistakes lead the agent into unfamiliar states) and expert dependency (where the agent's performance is capped by the quality of the expert). This paper introduces a framework that bridges this gap by using expert data not just to mimic actions, but to discover the underlying structure of the task. By automatically decomposing expert trajectories into a sequence of ordered subgoals, the framework creates a denser reward signal for RL, allowing the agent to surpass the original experts and handle unseen states.
Methodology: Subgoal Discovery and RL
The authors propose a robust pipeline that transitions from Imitation Learning to Reinforcement Learning, guided by automatically discovered subgoals.
- Imitation Learning (Pre-training): The agent first learns a policy via supervised learning on expert trajectories to establish a baseline starting point.
- Iterative Subgoal Discovery: The framework partitions the state space into $n_g$ subgoals. It begins with a simple temporal equipartition and refines it using Dynamic Time Warping (DTW) to align trajectories. This ensures consistent "milestones" even if different experts move at different speeds. A neural network is then trained to predict which subgoal a given state belongs to.
- RL with Subgoal-Based Rewards: The agent switches to RL. Instead of relying solely on sparse terminal rewards, it receives an extrinsic reward whenever it transitions from one subgoal to the next in the correct order.
- Out-of-Set Augmentation: To handle distribution shifts when the agent explores areas the expert didn't visit, the system uses Deep One-Class Classification. This acts as a confidence measure; if the agent is in an unrecognized state, the subgoal reward is modulated to prevent it from following erroneous predictions.
Environments and Key Results
The method was evaluated on three challenging MuJoCo-based environments:
- Ball-in-Maze (BiMGame): Moving a ball through concentric rings to the center using image-based inputs.
- AntTarget: Navigating a four-legged "Ant" robot to a target in an open environment.
- AntMaze: A highly complex task where the Ant must navigate a U-shaped maze to reach a goal.
The proposed method consistently solved all three tasks, whereas standard RL (A3C), standard IL (DAgger), and hybrid methods like AggreVaTeD failed to learn or performed significantly worse. Notably, because the discovered subgoals define a new reward function for RL, the agent is free to find better ways to achieve those subgoals than the expert did. In the AntMaze task, the agent achieved a cumulative reward 60x higher than the sub-optimal expert that provided the initial data.
Key Insights
- Discrete vs. Continuous Rewards: Discrete subgoal rewards prove more robust than continuous "value-based" reward shaping. Learned value functions are often noisy and can trap agents in local optima, whereas subgoals provide a clearer checkpoint system.
- Temporal Ordering: By assuming subgoals follow a natural order ($S_1 \to S_2 \to \dots \to S_{ng}$), the framework uses DTW to find structural bottlenecks without manual annotation.
- Ablation Success: The "Out-of-Set Augmentation" is crucial. Without it, the agent often gets trapped in local optima (e.g., in the BiMGame) by receiving "fake" subgoal rewards in states the expert never visited.
Limitations and Future Work
The framework relies on a user-defined hyperparameter for the number of subgoals ($n_g$). While robust to this choice in tested environments, highly complex tasks might require automated determination. Additionally, the current model assumes a linear, one-way progression of subgoals, making it less suitable for repetitive or cyclic tasks. Future work could extend this approach to non-goal-oriented tasks where the underlying structure resembles a graph rather than a linear sequence.
Summary updated