More Efficient Adversarial Imitation Learning Algorithms With Known and Unknown Transitions

Tian Xu, Ziniu Li, Yang Yu

Abstract

In this work, we design provably (more) efficient imitation learning algorithms that directly optimize policies from expert demonstrations. Firstly, when the transition function is known, we build on the nearly minimax optimal algorithm MIMIC-MD and develop an adversarial imitation learning (AIL) algorithm named TAIL with a gradient-based optimization procedure. TAIL achieves a sample complexity of $\widetilde{\mathcal{O}}(H^{3/2} |\mathcal{S}|/\varepsilon)$ and offers improved space complexity over previous methods. Secondly, for scenarios where the transition function is unknown, we present MB-TAIL, which connects reward-free exploration with AIL. MB-TAIL significantly outperforms the best-known OAL algorithm in both sample and interaction complexity, marking a significant shift in the efficiency of imitation learning in unknown environments.

Introduction

Imitation Learning (IL) is a powerful paradigm for training agents when explicit reward functions are difficult to specify. By leveraging expert demonstrations, agents can bypass the inefficiencies of random exploration. The two primary approaches in this field are Behavioral Cloning (BC), which treats imitation as a supervised learning problem, and Adversarial Imitation Learning (AIL), which matches the expert's state-action distribution through a minimax game.

While AIL often outperforms BC in empirical studies, its theoretical advantages have remained a subject of debate. A fundamental challenge is "compounding errors": in BC, small mistakes lead the agent into unfamiliar states, causing errors to grow quadratically with the planning horizon ($H^2$). This research provides a formal understanding of when and why AIL can provably overcome these barriers.

Theoretical Framework: TAIL and MB-TAIL

The authors analyze three variants of AIL to establish sharper complexity bounds:

  1. VAIL (Vanilla AIL): The standard approach using direct maximum likelihood estimation to match distributions.
  2. TAIL (Transition-aware AIL): A more efficient version for known transitions that leverages environment dynamics to achieve a sample complexity of $\widetilde{\mathcal{O}}(H^{3/2} |\mathcal{S}|/\varepsilon)$.
  3. MB-TAIL (Model-based TAIL): An extension for unknown environments that integrates reward-free exploration to learn the model and policy simultaneously.

Unlike standard reduction-based proofs, this work utilizes a dynamic programming-based analysis. This approach allows for navigating the non-convex nature of the AIL objective, leading to more precise theoretical guarantees.

Environment-Dependent Performance

The study reveals that the relative performance of BC and AIL is highly dependent on environment structure. In simple "Standard Imitation" setups, AIL can actually be less efficient than BC due to the statistical noise involved in matching full distributions—a phenomenon termed the "Sample Barrier."

However, in "Reset Cliff" environments—where errors lead to terminal states with zero reward—AIL demonstrates horizon-free generalization. By matching future state-action distributions, AIL receives guidance that prevents the snowballing errors typical of BC. In these scenarios, AIL can outperform BC by a factor of $H^2$.

Key Results and Complexity Bounds

The quantitative results highlight dramatic improvements in efficiency. For known transitions, VAIL achieves significantly better scaling in the Reset Cliff environment compared to BC.

Table 1: Sample complexity comparison between BC and VAIL across different environment types.

For unknown transitions, the proposed MB-TAIL algorithm sets a new benchmark. It reduces both the number of expert trajectories required (sample complexity) and the number of environment interactions (interaction complexity) compared to the previous state-of-the-art algorithm, OAL.

Table 2: Comparison of Sample and Interaction Complexity between OAL and the proposed MB-TAIL algorithm.

Conclusion

This research provides the first formal proof that Adversarial Imitation Learning can fundamentally outperform Behavioral Cloning by achieving horizon-free performance in challenging environments. By decoupling exploration from imitation and leveraging future distribution matching, algorithms like MB-TAIL offer a more robust path for learning from experts. While currently demonstrated in tabular settings, these insights provide a theoretical foundation for scaling AIL to more complex domains using function approximation.

Summary updated

Abstract

In this work, we design provably (more) efficient imitation learning algorithms that directly optimize policies from expert demonstrations. Firstly, when the transition function is known, we build on the nearly minimax optimal algorithm MIMIC-MD and relax a projection operator in it. Based on this change, we develop an adversarial imitation learning (AIL) algorithm named \emph{TAIL} with a gradient-based optimization procedure. Accordingly, TAIL has the same sample complexity (i.e., the number of expert trajectories) $\widetilde{\mathcal{O}}(H^{3/2} |\mathcal{S}|/\varepsilon)$ with MIMIC-MD, where $H$ is the planning horizon, $|\mathcal{S}|$ is the state space size and $\varepsilon$ is desired policy value gap. In addition, TAIL is more practical than MIMIC-MD as the former has a space complexity $\mathcal{O} (|\mathcal{S}||\mathcal{A}|H)$ while the latter's is about $\mathcal{O} (|\mathcal{S}|^2 |\mathcal{A}|^2 H^2)$. Secondly, under the scenario where the transition function is unknown but the interaction is allowed, we present an extension of TAIL named \emph{MB-TAIL}. The sample complexity of MB-TAIL is still $\widetilde{\mathcal{O}}(H^{3/2} |\mathcal{S}|/\varepsilon)$ while the interaction complexity (i.e., the number of interaction episodes) is $\widetilde{\mathcal{O}} (H^3 |\mathcal{S}|^2 |\mathcal{A}| / \varepsilon^2)$. In particular, MB-TAIL is significantly better than the best-known OAL algorithm, which has a sample complexity $\widetilde{\mathcal{O}}(H^{2} |\mathcal{S}|/\varepsilon^2)$ and interaction complexity $\widetilde{\mathcal{O}} (H^4 |\mathcal{S}|^2 |\mathcal{A}| / \varepsilon^2)$. The advances in MB-TAIL are based on a new framework that connects reward-free exploration and AIL. To our understanding, MB-TAIL is the first algorithm that shifts the advances in the known transition setting to the unknown transition setting.
BibTeX
@misc{xu2021more,
  author = {Tian Xu and Ziniu Li and Yang Yu},
  title = {{More Efficient Adversarial Imitation Learning Algorithms With Known and Unknown Transitions}},
  year = {2021},
  eprint = {2106.10424},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2106.10424},
}
Figure