Divide & Conquer Imitation Learning

Alexandre Chenu, Nicolas Perrin-Gilbert, Olivier Sigaud

Abstract

Deep Reinforcement Learning (DRL) often struggles with long-horizon tasks characterized by sparse rewards. While Imitation Learning (IL) can mitigate these challenges, most existing methods require extensive expert demonstrations. This paper introduces Divide & Conquer Imitation Learning (DCIL), an algorithm designed to solve complex, long-horizon robotic tasks using only a single expert demonstration. By partitioning a trajectory into manageable sub-tasks and employing a novel chaining reward bonus based on future value functions, DCIL achieves sample efficiency orders of magnitude higher than current state-of-the-art methods.

Introduction

In the field of robotics, "long-horizon" tasks—such as navigating a complex maze or performing multi-stage object manipulation—present a significant hurdle for standard reinforcement learning. The primary issue is the "sparse reward" problem: if an agent only receives a success signal at the end of a long sequence of actions, the probability of discovering that signal through random exploration is infinitesimally small.

Imitation Learning (IL) offers a solution by providing expert trajectories to guide the agent. However, collecting a large library of expert data is often prohibitively expensive or impractical. While single-demonstration methods like Backplay or PWIL exist, they frequently struggle with high-dimensional state spaces or fail to ensure that the transition between different segments of a task is seamless. DCIL addresses these limitations by leveraging a sequential inductive bias to decompose and solve complex tasks efficiently.

Methodology

DCIL operates on a "Divide & Conquer" principle, breaking a single expert demonstration into a sequence of smaller, achievable goals.

1. Divide

The algorithm begins by projecting the single expert trajectory into a lower-dimensional "goal space." This trajectory is then divided into $N$ sub-trajectories, or "skills," of equal length. This decomposition transforms one daunting long-horizon problem into a series of short-horizon tasks.

2. Conquer

A single Goal-Conditioned Policy (GCP) is trained using Soft Actor-Critic (SAC) to master these individual skills. To facilitate learning, the agent is reset to various starting points along the expert path, allowing it to practice specific segments of the trajectory in parallel.

3. Chaining and Continuity

The core innovation of DCIL lies in how it ensures these individual skills can be successfully sequenced. The authors introduce two primary mechanisms:

  • Overshoot: Upon completing skill $i$, the agent does not stop; it immediately attempts to reach the goal defined for skill $i+1$. This encourages the agent to maintain momentum and continuity.
  • Chaining Reward Bonus: To ensure the agent ends skill $i$ in a state that is conducive to starting skill $i+1$, DCIL provides a bonus based on the Value Function of the subsequent skill. This mathematically propagates the requirements of future tasks back to the current one, ensuring that the agent's terminal state for one skill (e.g., its orientation or velocity) is optimal for the next.

Experimental Evaluation

The researchers evaluated DCIL against several baselines, including Backplay, PWIL, and Behavioral Cloning, across two distinct simulated environments:

  • Dubins Maze: A 2D navigation task using a non-holonomic "Dubins car." This environment tests the agent's ability to handle constraints where orientation is critical for success.
  • Fetch Object Transportation: A high-dimensional (8-DOF) robot arm task involving grasping an object and placing it inside a drawer. With a 604-dimensional state space, this task represents a significant challenge for traditional IL methods.

Key Results and Insights

DCIL demonstrated remarkable sample efficiency and performance across both benchmarks:

  • Efficiency Gains: In the Dubins Maze, DCIL reached a solution in just $10^5$ training steps, whereas all baselines failed to solve the task even after $10^6$ steps. In the Fetch task, DCIL solved the problem three orders of magnitude faster than Backplay.
  • The Importance of Chaining: Ablation studies confirmed that the chaining reward bonus is the most critical component of the algorithm. Without it, the agent could solve individual skills in isolation but failed to transition between them, leading to a failure in the overall sequence.
  • Goal Space Advantage: By focusing on a lower-dimensional goal space rather than the full state space, DCIL effectively manages the complexity of high-dimensional robotics while the value function chaining ensures the necessary state-space details (like joint angles) are preserved for task continuity.

Conclusion and Future Work

Divide & Conquer Imitation Learning represents a significant step forward in making single-demonstration imitation learning viable for complex tasks. By treating a long trajectory as a chain of value-linked skills, it bypasses the exploration bottlenecks of traditional RL.

However, the current implementation relies on a "reset-anywhere" assumption, requiring the simulation to be resettable to any state in the expert demonstration. Future research will focus on relaxing this constraint, potentially by developing "return-to-state" policies that allow a robot to navigate back to specific training points autonomously. Additionally, exploring the application of DCIL to multi-stage manipulation and reversible skills remains a promising avenue for further development.

Summary updated

Abstract

When cast into the Deep Reinforcement Learning framework, many robotics tasks require solving a long horizon and sparse reward problem, where learning algorithms struggle. In such context, Imitation Learning (IL) can be a powerful approach to bootstrap the learning process. However, most IL methods require several expert demonstrations which can be prohibitively difficult to acquire. Only a handful of IL algorithms have shown efficiency in the context of an extreme low expert data regime where a single expert demonstration is available. In this paper, we present a novel algorithm designed to imitate complex robotic tasks from the states of an expert trajectory. Based on a sequential inductive bias, our method divides the complex task into smaller skills. The skills are learned into a goal-conditioned policy that is able to solve each skill individually and chain skills to solve the entire task. We show that our method imitates a non-holonomic navigation task and scales to a complex simulated robotic manipulation task with very high sample efficiency.
BibTeX
@inproceedings{chenu2022divide,
  author = {Alexandre Chenu and Nicolas Perrin-Gilbert and Olivier Sigaud},
  title = {{Divide \& Conquer Imitation Learning}},
  booktitle = {HAL},
  year = {2022},
  doi = {10.1109/iros47612.2022.9982020},
}
Figure