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.
Introduction
Imitation Learning (IL) is a powerful paradigm for teaching agents through expert demonstrations. Two dominant approaches are Behavioral Cloning (BC), which treats IL as supervised learning, and Adversarial Imitation Learning (AIL), which aims to match the agent's occupancy distribution with the expert's. While AIL often outperforms BC in practice, especially in long-horizon tasks, theoretical justification for this superiority has remained elusive. This paper provides a fine-grained theoretical comparison, identifying specific conditions under which AIL excels.
Methodology and Experimental Setup
The authors analyze Vanilla AIL (VAIL) in tabular, episodic Markov Decision Processes (MDPs). To overcome the non-convexity of the AIL objective, they employ a novel dynamic programming-based analysis. For unknown environments, they introduce MB-TAIL (Model-Based Transition-aware AIL), which combines transition-aware distribution matching with reward-free exploration strategies.
The study utilizes two synthetic MDPs to probe algorithmic limits:
- Standard Imitation: A setting where every state is absorbing, used to demonstrate AIL's potential statistical weaknesses.
- Reset Cliff: A realistic scenario where non-expert actions lead to a "bad" absorbing state, representing tasks where staying on the expert path is critical.
Theoretical Analysis: The AIL vs. BC Trade-off
The research reveals that AIL is not universally superior. In "Standard Imitation" tasks, VAIL can actually perform worse than BC. Because VAIL focuses on matching average distributions, it may exhibit higher error on frequently visited states compared to BC's "perfectionist" approach. Statistically, VAIL faces a $1/\sqrt{N}$ error rate, while BC achieves $1/N$ (where $N$ is the number of expert trajectories).
However, AIL shines in "Reset Cliff" environments. The distribution matching objective provides "indirect guidance"—the agent must act correctly in the present to match the expert's future distribution. This leads to horizon-free sample complexity, where AIL's error does not explode with task length ($H$), unlike BC's quadratic compounding error.
Key Results and Algorithmic Advances
As shown in the table above, VAIL achieves a sample complexity of $O(|S|/\epsilon^2)$ in Reset Cliff scenarios, independent of the horizon $H$. In contrast, BC is constrained by a $\Theta(|S|H^2/\epsilon)$ complexity.
For unknown transition settings, the proposed MB-TAIL algorithm significantly improves upon the previous state-of-the-art, OAL. It reduces interaction complexity from $O(H^4)$ to $O(H^3)$ and improves sample complexity, as detailed in the comparison below.
Conclusion
This work clarifies the theoretical landscape of imitation learning. While AIL may be less efficient in simple, absorbing environments, its ability to leverage future state distributions makes it remarkably effective in complex, "cliff-like" tasks. Future research will focus on extending these insights to continuous control with function approximation and exploring the impact of stochastic expert behavior.
Summary updated