mlsanityData to 7 Oct 2026

Toward the Fundamental Limits of Imitation Learning

arXiv 2009.05990 ↗First posted 13 Sep 2020cs.LG cs.AI math.OCcited by 96

On the map: Offline RL and imitation learning from data → Imitation learning methods

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.

Key facts. Cited by 96 papers in the map (data through 7 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.

Builds on

13 of 37 references.

Closest ancestors · 5

Same direction, newest first

  1. 2020Provable Representation Learning for Imitation Learning via Bi-level Optimization24 Feb
  2. 2019Learning Self-Correctable Policies and Value Functions from Demonstrations with Negative Sampling12 Jul
  3. 2019Imitation Learning as f-Divergence Minimization30 May
  4. 2019Provably Efficient Imitation Learning from Observation Alone27 May
  5. 2018Behavioral Cloning from Observation4 May

Other references · 8

  1. 2016Generative Adversarial Imitation Learningcited by 1,576
  2. 2016Guided Cost Learning: Deep Inverse Optimal Control via Policy Optimizationcited by 400
  3. 2018Reward learning from human preferences and demonstrations in Ataricited by 314
  4. 2018Reinforcement and Imitation Learning for Diverse Visuomotor Skillscited by 124
  5. 2014Reinforcement and Imitation Learning via Interactive No-Regret Learningcited by 116
  6. 2017Deeply AggreVaTeD: Differentiable Imitation Learning for Sequential Predictioncited by 93
  7. 2017Combining Self-Supervised Learning and Imitation for Vision-Based Rope Manipulationcited by 90
  8. 2017Learning human behaviors from motion capture by adversarial imitationcited by 75

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 12; 2023: 14; 2024: 23; 2025: 21; 2026: 18.

96 papers.

Sort:

By area:

  1. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  2. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 160
  3. 2024Behavior Generation with Latent Actionscited by 159
  4. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 122
  5. 2022When Should We Prefer Offline Reinforcement Learning Over Behavioral Cloning?cited by 86
  6. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
  7. 2023Transformers as Decision Makers: Provable In-Context Reinforcement Learning via Supervised Pretrainingcited by 82
  8. 2021Of Moments and Matching: A Game-Theoretic Framework for Closing the Imitation Gapcited by 80
  9. 2024Dense Reward for Free in Reinforcement Learning from Human Feedbackcited by 77
  10. 2025Generalist Reward Models: Found Inside Large Language Modelscited by 34
  11. 2021Online Apprenticeship Learningcited by 28
  12. 2022Active Exploration for Inverse Reinforcement Learningcited by 27
38 more
  1. 2021Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coveragecited by 26
  2. 2022Minimax Optimal Online Imitation Learning via Replay Estimationcited by 25
  3. 2023Coherent Soft Imitation Learningcited by 21
  4. 2024ODICE: Revealing the Mystery of Distribution Correction Estimation via Orthogonal-gradient Updatecited by 21
  5. 2024PRISE: LLM-Style Sequence Compression for Learning Temporal Action Abstractions in Controlcited by 21
  6. 2021Collect & Infer -- a fresh look at data-efficient Reinforcement Learningcited by 17
  7. 2022Discriminator-Guided Model-Based Offline Imitation Learningcited by 17
  8. 2023Provably Efficient Adversarial Imitation Learning with Unknown Transitionscited by 16
  9. 2022Rethinking ValueDice: Does It Really Improve Performance?cited by 15
  10. 2023Mind the Gap: Offline Policy Optimization for Imperfect Rewardscited by 15
  11. 2024Imitation Learning in Discounted Linear MDPs without exploration assumptionscited by 15
  12. 2024Transformer-based Model Predictive Control: Trajectory Optimization via Sequence Modelingcited by 15
  13. 2023Memory-Consistent Neural Networks for Imitation Learningcited by 14
  14. 2022Understanding Adversarial Imitation Learning in Small Sample Regime: A Stage-coupled Analysiscited by 13
  15. 2021Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimallycited by 12
  16. 2022Relational Reasoning via Set Transformers: Provable Efficiency and Applications to MARLcited by 12
  17. 2023Reward-Consistent Dynamics Models are Strongly Generalizable for Offline Reinforcement Learningcited by 12
  18. 2024REGENT: A Retrieval-Augmented Generalist Agent That Can Act In-Context in New Environmentscited by 12
  19. 2026LiLo-VLA: Compositional Long-Horizon Manipulation via Linked Object-Centric Policiescited by 12
  20. 2026PivotRL: High Accuracy Agentic Post-Training at Low Compute Costcited by 12
  21. 2021Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximationcited by 11
  22. 2024How to Leverage Diverse Demonstrations in Offline Imitation Learningcited by 11
  23. 2022Robust Imitation Learning from Corrupted Demonstrationscited by 10
  24. 2023CTRLStruct: Dialogue Structure Learning for Open-Domain Response Generationcited by 8
  25. 2023How To Guide Your Learner: Imitation Learning with Active Adaptive Expert Involvementcited by 8
  26. 2024Offline Imitation Learning with Model-based Reverse Augmentationcited by 8
  27. 2025Posterior Behavioral Cloning: Pretraining BC Policies for Efficient RL Finetuningcited by 8
  28. 2024OLLIE: Imitation Learning from Offline Pretraining to Online Finetuningcited by 6
  29. 2024Provably and Practically Efficient Adversarial Imitation Learning with General Function Approximationcited by 6
  30. 2025Learning to Answer from Correct Demonstrationscited by 6
  31. 2022On Efficient Online Imitation Learning via Classificationcited by 5
  32. 2023Curricular Subgoals for Inverse Reinforcement Learningcited by 5
  33. 2024A Natural Extension To Online Algorithms For Hybrid RL With Limited Coveragecited by 5
  34. 2024How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approachcited by 5
  35. 2025IL-SOAR : Imitation Learning with Soft Optimistic Actor cRiticcited by 5
  36. 2025Inverse Q-Learning Done Right: Offline Imitation Learning in Qπ-Realizable MDPscited by 5
  37. 2023Towards the Fundamental Limits of Knowledge Transfer over Finite Domainscited by 4
  38. 2023Is Inverse Reinforcement Learning Harder than Standard Reinforcement Learning? A Theoretical Perspectivecited by 4

50 most cited of 96 All 96 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2025The Pitfalls of Imitation Learning when Actions are Continuous
  2. 2022Sequence Model Imitation Learning with Unobserved Contexts
  3. 2021On the Sample Complexity of Stability Constrained Imitation Learning
  4. 2023A Strong Baseline for Batch Imitation Learning
  5. 2024A Bayesian Solution To The Imitation Gap
  6. 2020State-only Imitation with Transition Dynamics Mismatch
  7. 2026Behavior Cloning is Not All You Need: The Optimality of On-Policy Distillation for Noisy Expert Feedback
  8. 2020Robust Asymmetric Learning in POMDPs