# Toward the Fundamental Limits of Imitation Learning

arXiv: https://arxiv.org/abs/2009.05990 · HTML: https://mlsanity.com/paper/2009.05990/

## Key facts

- Cited by 96 papers in the map (data through 14 Oct 2026).
- Placed in Imitation learning methods, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 13 of its 37 references that are in the map.
- First posted on arXiv 13 Sep 2020.

## Placed in

- Offline RL and imitation learning from data / [Imitation learning methods](https://mlsanity.com/offlinerl/imitation-learning-methods/)

## Builds on (most cited first, 13 of 13)

- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [Behavioral Cloning from Observation](https://mlsanity.com/paper/1805.01954/) (2018)
- [Guided Cost Learning: Deep Inverse Optimal Control via Policy Optimization](https://mlsanity.com/paper/1603.00448/) (2016)
- [Reward learning from human preferences and demonstrations in Atari](https://mlsanity.com/paper/1811.06521/) (2018)
- [Reinforcement and Imitation Learning for Diverse Visuomotor Skills](https://mlsanity.com/paper/1802.09564/) (2018)
- [Imitation Learning as f-Divergence Minimization](https://mlsanity.com/paper/1905.12888/) (2019)
- [Reinforcement and Imitation Learning via Interactive No-Regret Learning](https://mlsanity.com/paper/1406.5979/) (2014)
- [Deeply AggreVaTeD: Differentiable Imitation Learning for Sequential Prediction](https://mlsanity.com/paper/1703.01030/) (2017)
- [Combining Self-Supervised Learning and Imitation for Vision-Based Rope Manipulation](https://mlsanity.com/paper/1703.02018/) (2017)
- [Provably Efficient Imitation Learning from Observation Alone](https://mlsanity.com/paper/1905.10948/) (2019)
- [Learning human behaviors from motion capture by adversarial imitation](https://mlsanity.com/paper/1707.02201/) (2017)
- [Provable Representation Learning for Imitation Learning via Bi-level Optimization](https://mlsanity.com/paper/2002.10544/) (2020)
- [Learning Self-Correctable Policies and Value Functions from Demonstrations with Negative Sampling](https://mlsanity.com/paper/1907.05634/) (2019)

## Built on by (most cited first, 30 of 96)

- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage](https://mlsanity.com/paper/2107.06226/) (2021)
- [Behavior Generation with Latent Actions](https://mlsanity.com/paper/2403.03181/) (2024)
- [Offline Reinforcement Learning with Realizability and Single-policy Concentrability](https://mlsanity.com/paper/2202.04634/) (2022)
- [When Should We Prefer Offline Reinforcement Learning Over Behavioral Cloning?](https://mlsanity.com/paper/2204.05618/) (2022)
- [Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity](https://mlsanity.com/paper/2202.13890/) (2022)
- [Transformers as Decision Makers: Provable In-Context Reinforcement Learning via Supervised Pretraining](https://mlsanity.com/paper/2310.08566/) (2023)
- [Of Moments and Matching: A Game-Theoretic Framework for Closing the Imitation Gap](https://mlsanity.com/paper/2103.03236/) (2021)
- [Dense Reward for Free in Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2402.00782/) (2024)
- [Generalist Reward Models: Found Inside Large Language Models](https://mlsanity.com/paper/2506.23235/) (2025)
- [Online Apprenticeship Learning](https://mlsanity.com/paper/2102.06924/) (2021)
- [Active Exploration for Inverse Reinforcement Learning](https://mlsanity.com/paper/2207.08645/) (2022)
- [Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage](https://mlsanity.com/paper/2106.03207/) (2021)
- [Minimax Optimal Online Imitation Learning via Replay Estimation](https://mlsanity.com/paper/2205.15397/) (2022)
- [Coherent Soft Imitation Learning](https://mlsanity.com/paper/2305.16498/) (2023)
- [ODICE: Revealing the Mystery of Distribution Correction Estimation via Orthogonal-gradient Update](https://mlsanity.com/paper/2402.00348/) (2024)
- [PRISE: LLM-Style Sequence Compression for Learning Temporal Action Abstractions in Control](https://mlsanity.com/paper/2402.10450/) (2024)
- [Collect & Infer -- a fresh look at data-efficient Reinforcement Learning](https://mlsanity.com/paper/2108.10273/) (2021)
- [Discriminator-Guided Model-Based Offline Imitation Learning](https://mlsanity.com/paper/2207.00244/) (2022)
- [Provably Efficient Adversarial Imitation Learning with Unknown Transitions](https://mlsanity.com/paper/2306.06563/) (2023)
- [Transformer-based Model Predictive Control: Trajectory Optimization via Sequence Modeling](https://mlsanity.com/paper/2410.23916/) (2024)
- [REGENT: A Retrieval-Augmented Generalist Agent That Can Act In-Context in New Environments](https://mlsanity.com/paper/2412.04759/) (2024)
- [Rethinking ValueDice: Does It Really Improve Performance?](https://mlsanity.com/paper/2202.02468/) (2022)
- [Mind the Gap: Offline Policy Optimization for Imperfect Rewards](https://mlsanity.com/paper/2302.01667/) (2023)
- [Imitation Learning in Discounted Linear MDPs without exploration assumptions](https://mlsanity.com/paper/2405.02181/) (2024)
- [Memory-Consistent Neural Networks for Imitation Learning](https://mlsanity.com/paper/2310.06171/) (2023)
- [LiLo-VLA: Compositional Long-Horizon Manipulation via Linked Object-Centric Policies](https://mlsanity.com/paper/2602.21531/) (2026)
- [PivotRL: High Accuracy Agentic Post-Training at Low Compute Cost](https://mlsanity.com/paper/2603.21383/) (2026)
- [Understanding Adversarial Imitation Learning in Small Sample Regime: A Stage-coupled Analysis](https://mlsanity.com/paper/2208.01899/) (2022)
- [Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally](https://mlsanity.com/paper/2102.12948/) (2021)

## Abstract (arXiv)

Imitation learning (IL) aims to mimic the behavior of an expert policy in a sequential decision-making problem given only demonstrations. In this paper, we focus on understanding the minimax statistical limits of IL in episodic Markov Decision Processes (MDPs). We first consider the setting where the learner is provided a dataset of N expert trajectories ahead of time, and cannot interact with the MDP. Here, we show that the policy which mimics the expert whenever possible is in expectation lesssim frac|S| H2 log (N)N suboptimal compared to the value of the expert, even when the expert follows an arbitrary stochastic policy. Here S is the state space, and H is the length of the episode. Furthermore, we establish a suboptimality lower bound of gtrsim |S| H2 / N which applies even if the expert is constrained to be deterministic, or if the learner is allowed to actively query the expert at visited states while interacting with the MDP for N episodes. To our knowledge, this is the first algorithm with suboptimality having no dependence on the number of actions, under no additional assumptions. We then propose a novel algorithm based on minimum-distance functionals in the setting where the transition model is given and the expert is deterministic. The algorithm is suboptimal by lesssim min  H √|S| / N , |S| H3/2 / N , showing that knowledge of transition improves the minimax rate by at least a √H factor.