On Generalization of Adversarial Imitation Learning and Beyond

Xu Tian, Ziniu Li, Yang Yu, Zhi‐Quan LuoarXiv 2021 · DOI · arXiv

TL;DR

This paper provides the first theoretical proof that Adversarial Imitation Learning (AIL) can beat Behavioral Cloning (BC) by a massive margin—specifically, a factor of the planning horizon squared ($H^2$). However, it also reveals a catch: in certain simple environments, AIL can actually perform worse than BC due to slower statistical convergence.

What Problem Does This Paper Address?

In Imitation Learning (IL), an agent tries to learn a policy by watching an expert. There are two main ways to do this:

  1. Behavioral Cloning (BC): Treat it as a supervised learning problem (mapping states to actions). It’s simple but suffers from "compounding errors"—a tiny mistake early on leads the agent to states it never saw in the training data, where it then fails completely.
  2. Adversarial Imitation Learning (AIL): Try to make the agent’s entire state-action distribution match the expert's. Algorithms like GAIL have shown incredible empirical success, often working with very few expert demonstrations.

The mystery has been: Why? Does AIL actually generalize better than BC, or is its success just a fluke of neural network architecture? This paper investigates this question using the lens of sample complexity—how many expert trajectories are needed to reach a specific level of performance?

Methods

The authors analyze Vanilla AIL (VAIL) and a more advanced version called MIMIC-MD within tabular, episodic Markov Decision Processes (MDPs).

Key methodological contributions include:

  • Dynamic Programming Analysis: To bypass the fact that AIL objectives are non-convex (making them hard to analyze with standard tools), the authors used a dynamic programming-based approach to study optimal solutions.
  • TAIL & MB-TAIL: They introduce Transition-aware AIL (TAIL), a gradient-based version of MIMIC-MD, and MB-TAIL, which extends the logic to environments where the physics (transitions) are unknown by incorporating "reward-free exploration" strategies.

Datasets

The study uses two specially designed synthetic MDP environments to test the limits of these algorithms:

  • Standard Imitation: A "hard" case for AIL where states are absorbing. This environment highlights AIL's statistical weaknesses.
  • Reset Cliff: An environment where a single wrong move sends the agent to a "bad" terminal state. This mimics many real-world robotics tasks (like a robot falling over) and highlights BC's compounding error problem.

Key Insights and Ideas

  • The "Sample Barrier": The authors found that VAIL has a slower convergence rate ($1/\sqrt{N}$) compared to BC ($1/N$) regarding the number of expert trajectories $N$. In simple environments without compounding errors, BC is actually the superior choice.
  • Weak Convergence: VAIL can fail even on states the expert did visit because matching a distribution is "looser" than directly copying an action.
  • The Horizon-Free Miracle: The "Aha!" moment comes in the Reset Cliff setting. Here, VAIL achieves horizon-free sample complexity. This means the number of expert demos needed doesn't increase as the task gets longer. In these cases, AIL beats BC by a factor of $O(H^2)$, explaining why GAIL works so well for long-horizon tasks with few demos.
  • Future Guidance: The reason AIL wins in complex tasks is that the objective at time step $t+1$ provides "guidance" for the decision at time step $t$. If the agent makes a mistake now, it won't be able to match the expert's distribution later, so the optimizer forces it to get the early steps right.

Key Results

The paper provides a clear breakdown of when each algorithm wins:

Environment BC Sample Complexity VAIL Sample Complexity Winner
Standard Imitation $O(|S|H/\epsilon)$ $\Theta(|S|H^2/\epsilon^2)$ BC
Reset Cliff $\Theta(|S|H^2/\epsilon)$ $O(|S|/\epsilon^2)$ VAIL

Note: $|S|$ is the number of states, $H$ is the horizon, and $\epsilon$ is the error tolerance.

In the unknown transition setting, their new MB-TAIL algorithm improved both sample and interaction complexity over the previous state-of-the-art (OAL), reducing the dependence on the horizon $H$ significantly.

Limitations and Future Work

The primary limitation is that this analysis is restricted to tabular MDPs (where states and actions are discrete and finite). While this is the standard starting point for theoretical proofs, real-world AIL uses deep neural networks to handle continuous state spaces.

The authors suggest that the next frontier is extending these "horizon-free" insights to function approximation (neural nets) and exploring how representation learning helps AIL identify the "good" states that prevent compounding errors.

Summary updated

Abstract

Despite massive empirical evaluations, one of the fundamental questions in imitation learning is still not fully settled: does AIL (adversarial imitation learning) provably generalize better than BC (behavioral cloning)? We study this open problem with tabular and episodic MDPs. For vanilla AIL that uses the direct maximum likelihood estimation, we provide both negative and positive answers under the known transition setting. For some MDPs, we show that vanilla AIL has a worse sample complexity than BC. The key insight is that the state-action distribution matching principle is weak so that AIL may generalize poorly even on visited states from the expert demonstrations. For another class of MDPs, vanilla AIL is proved to generalize well even on non-visited states. Interestingly, its sample complexity is horizon-free, which provably beats BC by a wide margin. Finally, we establish a framework in the unknown transition scenario, which allows AIL to explore via reward-free exploration strategies. Compared with the best-known online apprenticeship learning algorithm, the resulting algorithm improves the sample complexity and interaction complexity.
BibTeX
@misc{tian2021generalization,
  author = {Xu Tian and Ziniu Li and Yang Yu and Zhi‐Quan Luo},
  title = {{On Generalization of Adversarial Imitation Learning and Beyond}},
  year = {2021},
  eprint = {2106.10424},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2106.10424},
}
Figure