# Provably Efficient Imitation Learning from Observation Alone

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

## Key facts

- Cited by 78 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 21 of its 51 references that are in the map.
- First posted on arXiv 27 May 2019.

## Placed in

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

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [Wasserstein GAN](https://mlsanity.com/paper/1701.07875/) (2017)
- [Behavioral Cloning from Observation](https://mlsanity.com/paper/1805.01954/) (2018)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Imitation from Observation: Learning to Imitate Behaviors from Raw Video via Context Translation](https://mlsanity.com/paper/1707.03374/) (2017)
- [Generalization and Equilibrium in Generative Adversarial Nets (GANs)](https://mlsanity.com/paper/1703.00573/) (2017)
- [Reinforcement and Imitation Learning via Interactive No-Regret Learning](https://mlsanity.com/paper/1406.5979/) (2014)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Imitating Latent Policies from Observation](https://mlsanity.com/paper/1805.07914/) (2018)
- [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)
- [Learning to Search Better Than Your Teacher](https://mlsanity.com/paper/1502.02206/) (2015)
- [Truncated Horizon Policy Search: Combining Reinforcement Learning & Imitation Learning](https://mlsanity.com/paper/1805.11240/) (2018)
- [Learning to Filter with Predictive State Inference Machines](https://mlsanity.com/paper/1512.08836/) (2015)
- [Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches](https://mlsanity.com/paper/1811.08540/) (2018)
- [Learning to Search for Dependencies](https://mlsanity.com/paper/1503.05615/) (2015)

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

- [Imitation Learning as f-Divergence Minimization](https://mlsanity.com/paper/1905.12888/) (2019)
- [Offline Reinforcement Learning with Realizability and Single-policy Concentrability](https://mlsanity.com/paper/2202.04634/) (2022)
- [XIRL: Cross-embodiment Inverse Reinforcement Learning](https://mlsanity.com/paper/2106.03911/) (2021)
- [Toward the Fundamental Limits of Imitation Learning](https://mlsanity.com/paper/2009.05990/) (2020)
- [Recent Advances in Imitation Learning from Observation](https://mlsanity.com/paper/1905.13566/) (2019)
- [State-Only Imitation Learning for Dexterous Manipulation](https://mlsanity.com/paper/2004.04650/) (2020)
- [Of Moments and Matching: A Game-Theoretic Framework for Closing the Imitation Gap](https://mlsanity.com/paper/2103.03236/) (2021)
- [State Alignment-based Imitation Learning](https://mlsanity.com/paper/1911.10947/) (2019)
- [Off-Policy Imitation Learning from Observations](https://mlsanity.com/paper/2102.13185/) (2021)
- [Feedback in Imitation Learning: The Three Regimes of Covariate Shift](https://mlsanity.com/paper/2102.02872/) (2021)
- [Imitation Learning: Progress, Taxonomies and Challenges](https://mlsanity.com/paper/2106.12177/) (2021)
- [Imitation Learning from Observations by Minimizing Inverse Dynamics Disagreement](https://mlsanity.com/paper/1910.04417/) (2019)
- [MobILE: Model-Based Imitation Learning From Observation Alone](https://mlsanity.com/paper/2102.10769/) (2021)
- [Provable Representation Learning for Imitation Learning via Bi-level Optimization](https://mlsanity.com/paper/2002.10544/) (2020)
- [Energy-Based Imitation Learning](https://mlsanity.com/paper/2004.09395/) (2020)
- [Inverse Reinforcement Learning without Reinforcement Learning](https://mlsanity.com/paper/2303.14623/) (2023)
- [Robust Inverse Reinforcement Learning under Transition Dynamics Mismatch](https://mlsanity.com/paper/2007.01174/) (2020)
- [A Simple Reward-free Approach to Constrained Reinforcement Learning](https://mlsanity.com/paper/2107.05216/) (2021)
- [Causal Imitation Learning under Temporally Correlated Noise](https://mlsanity.com/paper/2202.01312/) (2022)
- [Learning from Imperfect Demonstrations from Agents with Varying Dynamics](https://mlsanity.com/paper/2103.05910/) (2021)
- [Robust Imitation Learning from Noisy Demonstrations](https://mlsanity.com/paper/2010.10181/) (2020)
- [Interactive Learning from Activity Description](https://mlsanity.com/paper/2102.07024/) (2021)
- [Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage](https://mlsanity.com/paper/2106.03207/) (2021)
- [LobsDICE: Offline Learning from Observation via Stationary Distribution Correction Estimation](https://mlsanity.com/paper/2202.13536/) (2022)
- [A Ranking Game for Imitation Learning](https://mlsanity.com/paper/2202.03481/) (2022)
- [SelfD: Self-Learning Large-Scale Driving Policies From the Web](https://mlsanity.com/paper/2204.10320/) (2022)
- [Imitation Learning by Reinforcement Learning](https://mlsanity.com/paper/2108.04763/) (2021)
- [Identifiability and Generalizability in Constrained Inverse Reinforcement Learning](https://mlsanity.com/paper/2306.00629/) (2023)
- [A Survey of Imitation Learning Methods, Environments and Metrics](https://mlsanity.com/paper/2404.19456/) (2024)
- [Diffusing States and Matching Scores: A New Framework for Imitation Learning](https://mlsanity.com/paper/2410.13855/) (2024)

## Abstract (arXiv)

We study Imitation Learning (IL) from Observations alone (ILFO) in large-scale MDPs. While most IL algorithms rely on an expert to directly provide actions to the learner, in this setting the expert only supplies sequences of observations. We design a new model-free algorithm for ILFO, Forward Adversarial Imitation Learning (FAIL), which learns a sequence of time-dependent policies by minimizing an Integral Probability Metric between the observation distributions of the expert policy and the learner. FAIL is the first provably efficient algorithm in ILFO setting, which learns a near-optimal policy with a number of samples that is polynomial in all relevant parameters but independent of the number of unique observations. The resulting theory extends the domain of provably sample efficient learning algorithms beyond existing results, which typically only consider tabular reinforcement learning settings or settings that require access to a near-optimal reset distribution. We also investigate the extension of FAIL in a model-based setting. Finally we demonstrate the efficacy of FAIL on multiple OpenAI Gym control tasks.