# Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally

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

## Key facts

- Cited by 12 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 17 of its 28 references that are in the map.
- First posted on arXiv 25 Feb 2021.

## Placed in

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

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

- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [Learning Robust Rewards with Adversarial Inverse Reinforcement Learning](https://mlsanity.com/paper/1710.11248/) (2017)
- [Guided Cost Learning: Deep Inverse Optimal Control via Policy Optimization](https://mlsanity.com/paper/1603.00448/) (2016)
- [DART: Noise Injection for Robust Imitation Learning](https://mlsanity.com/paper/1703.09327/) (2017)
- [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)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Toward the Fundamental Limits of Imitation Learning](https://mlsanity.com/paper/2009.05990/) (2020)
- [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)
- [Error Bounds of Imitating Policies and Environments](https://mlsanity.com/paper/2010.11876/) (2020)
- [Learning Montezuma's Revenge from a Single Demonstration](https://mlsanity.com/paper/1812.03381/) (2018)
- [Provably Efficient Imitation Learning from Observation Alone](https://mlsanity.com/paper/1905.10948/) (2019)
- [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)
- [Dynamic Regret Convergence Analysis and an Adaptive Regularization Algorithm for On-Policy Robot Imitation Learning](https://mlsanity.com/paper/1811.02184/) (2018)

## Built on by (most cited first, 12 of 12)

- [Transformers as Decision Makers: Provable In-Context Reinforcement Learning via Supervised Pretraining](https://mlsanity.com/paper/2310.08566/) (2023)
- [PoliFormer: Scaling On-Policy RL with Transformers Results in Masterful Navigators](https://mlsanity.com/paper/2406.20083/) (2024)
- [Minimax Optimal Online Imitation Learning via Replay Estimation](https://mlsanity.com/paper/2205.15397/) (2022)
- [Provably Efficient Adversarial Imitation Learning with Unknown Transitions](https://mlsanity.com/paper/2306.06563/) (2023)
- [Understanding Adversarial Imitation Learning in Small Sample Regime: A Stage-coupled Analysis](https://mlsanity.com/paper/2208.01899/) (2022)
- [Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification](https://mlsanity.com/paper/2502.12465/) (2025)
- [Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximation](https://mlsanity.com/paper/2108.08765/) (2021)
- [Robust Imitation Learning from Corrupted Demonstrations](https://mlsanity.com/paper/2201.12594/) (2022)
- [IL-SOAR : Imitation Learning with Soft Optimistic Actor cRitic](https://mlsanity.com/paper/2502.19859/) (2025)
- [Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning](https://mlsanity.com/paper/2505.17610/) (2025)
- [Imitation Learning as Return Distribution Matching](https://mlsanity.com/paper/2509.12026/) (2025)
- [Blindfolded Experts Generalize Better: Insights from Robotic Manipulation and Videogames](https://mlsanity.com/paper/2510.24194/) (2025)

## Abstract (arXiv)

We study the statistical limits of Imitation Learning (IL) in episodic Markov Decision Processes (MDPs) with a state space S. We focus on the known-transition setting where the learner is provided a dataset of N length-H trajectories from a deterministic expert policy and knows the MDP transition. We establish an upper bound O(|S|H3/2/N) for the suboptimality using the Mimic-MD algorithm in Rajaraman et al (2020) which we prove to be computationally efficient. In contrast, we show the minimax suboptimality grows as Omega( H3/2/N) when |S|≥ 3 while the unknown-transition setting suffers from a larger sharp rate Theta(|S|H2/N) (Rajaraman et al (2020)). The lower bound is established by proving a two-way reduction between IL and the value estimation problem of the unknown expert policy under any given reward function, as well as building connections with linear functional estimation with subsampled observations. We further show that under the additional assumption that the expert is optimal for the true reward function, there exists an efficient algorithm, which we term as Mimic-Mixture, that provably achieves suboptimality O(1/N) for arbitrary 3-state MDPs with rewards only at the terminal layer. In contrast, no algorithm can achieve suboptimality O(√H/N) with high probability if the expert is not constrained to be optimal. Our work formally establishes the benefit of the expert optimal assumption in the known transition setting, while Rajaraman et al (2020) showed it does not help when transitions are unknown.