Learning from Trajectories via Subgoal Discovery

Sujoy Paul, Jeroen van Baar, Amit K. Roy-Chowdhury

Abstract

Learning to solve complex goal-oriented tasks with sparse terminal-only rewards often requires an enormous number of samples. In such cases, using a set of expert trajectories could help to learn faster. However, Imitation Learning (IL) via supervised pre-training with these trajectories may not perform as well and generally requires additional finetuning with expert-in-the-loop. In this paper, we propose an approach which uses the expert trajectories and learns to decompose the complex main task into smaller sub-goals. We learn a function which partitions the state-space into sub-goals, which can then be used to design an extrinsic reward function. We follow a strategy where the agent first learns from the trajectories using IL and then switches to Reinforcement Learning (RL) using the identified sub-goals, to alleviate the errors in the IL step. To deal with states which are under-represented by the trajectory set, we also learn a function to modulate the sub-goal predictions. We show that our method is able to solve complex goal-oriented tasks, which other RL, IL or their combinations in literature are not able to solve.

Introduction

Reinforcement Learning (RL) excels at optimization but struggles with "sparse rewards"—scenarios where an agent only receives feedback at the very end of a long, complex task. Without intermediate feedback, agents often spend excessive time in unproductive exploration. Imitation Learning (IL) addresses this by mimicking expert trajectories, but it is notoriously brittle; errors compound quickly when the agent encounters states not present in the expert data.

This paper introduces a framework that bridges the gap between IL and RL by automatically discovering subgoals from expert trajectories. By partitioning the state-space into ordered subgoals and using a "one-class classifier" to handle unfamiliar states, the authors create a dense reward signal that allows agents to solve complex, sparse-reward tasks without requiring the expert's internal value function.

Methodology

The proposed framework follows a three-stage pipeline: supervised pre-training, subgoal discovery, and RL with subgoal-based rewards.

  1. Supervised Pre-training: The agent begins with Behavioral Cloning to obtain an initial policy from expert trajectories.
  2. Subgoal Discovery: The core innovation involves partitioning expert trajectories into $n_g$ subgoals. This uses an iterative process: a "Learning Step" trains a neural network to classify states into subgoals, and an "Inference Step" uses Dynamic Time Warping (DTW) to refine labels by enforcing temporal order.
  3. RL with Subgoal-based Rewards: Discovered subgoals form a potential-based reward function. To ensure robustness, a Deep One-Class Classification module estimates how well-represented a state is in the expert data. If a state is unfamiliar, the subgoal reward is modulated to prevent following "hallucinated" paths.
The proposed architecture (a) and conceptual state-space partitioning (b).

Experimental Setup

The authors evaluated their method on three challenging MuJoCo environments:

  • Ball-in-Maze (BiMGame): Moving a ball through concentric rings by tilting a board (image-based state space).
  • AntTarget: An Ant robot reaching the center of a circle.
  • AntMaze: A U-shaped maze navigation task, a classic benchmark for sparse-reward RL.

Results and Discussion

The proposed method consistently solved the AntMaze and BiMGame tasks, where standard RL (A3C) and standard IL (Behavioral Cloning) failed completely.

The three evaluation environments (top) and cumulative reward performance comparison (bottom).

Key findings include:

  • Surpassing the Expert: The RL agent often outperformed the expert trajectories it learned from by finding more efficient paths through the discovered subgoal "map."
  • Robustness: The method remains effective even with sub-optimal trajectories, as long as they maintain a general temporal order.
  • Safety: The One-Class Classifier acts as a vital safety net, preventing counterproductive reward shaping in unexplored regions.

Conclusion

While the framework is powerful, it is sensitive to the choice of the number of subgoals ($n_g$) and assumes a relatively linear task progression. Future work will explore automatically determining the optimal number of subgoals and applying the method to non-goal-oriented, repetitive tasks.

Summary updated

Abstract

Learning to solve complex goal-oriented tasks with sparse terminal-only rewards often requires an enormous number of samples. In such cases, using a set of expert trajectories could help to learn faster. However, Imitation Learning (IL) via supervised pre-training with these trajectories may not perform as well and generally requires additional finetuning with expert-in-the-loop. In this paper, we propose an approach which uses the expert trajectories and learns to decompose the complex main task into smaller sub-goals. We learn a function which partitions the state-space into sub-goals, which can then be used to design an extrinsic reward function. We follow a strategy where the agent first learns from the trajectories using IL and then switches to Reinforcement Learning (RL) using the identified sub-goals, to alleviate the errors in the IL step. To deal with states which are under-represented by the trajectory set, we also learn a function to modulate the sub-goal predictions. We show that our method is able to solve complex goal-oriented tasks, which other RL, IL or their combinations in literature are not able to solve.
BibTeX
@inproceedings{paul2019learning,
  author = {Sujoy Paul and Jeroen van Baar and Amit K. Roy-Chowdhury},
  title = {{Learning from Trajectories via Subgoal Discovery}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=sn0HA_JBCB},
}
Figure