# Explaining Fast Improvement in Online Imitation Learning

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

## Key facts

- Cited by 1 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 18 of its 45 references that are in the map.
- First posted on arXiv 6 Jul 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, 18 of 18)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [DART: Noise Injection for Robust Imitation Learning](https://mlsanity.com/paper/1703.09327/) (2017)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [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)
- [Learning to Search Better Than Your Teacher](https://mlsanity.com/paper/1502.02206/) (2015)
- [On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities](https://mlsanity.com/paper/1510.03925/) (2015)
- [Fast Policy Learning through Imitation and Reinforcement](https://mlsanity.com/paper/1805.10413/) (2018)
- [Empirical Risk Minimization for Stochastic Convex Optimization: O(1/n)- and O(1/n2)-type of Risk Bounds](https://mlsanity.com/paper/1702.02030/) (2017)
- [Online Learning with Continuous Variations: Dynamic Regret and Reductions](https://mlsanity.com/paper/1902.07286/) (2019)
- [Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditions](https://mlsanity.com/paper/1805.04577/) (2018)
- [Predictor-Corrector Policy Optimization](https://mlsanity.com/paper/1810.06509/) (2018)
- [Accelerating Imitation Learning with Predictive Models](https://mlsanity.com/paper/1806.04642/) (2018)
- [Continuous Online Learning and New Insights to Online Imitation Learning](https://mlsanity.com/paper/1912.01261/) (2019)

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

- [Improved Policy Optimization for Online Imitation Learning](https://mlsanity.com/paper/2208.00088/) (2022)

## Abstract (arXiv)

Online imitation learning (IL) is an algorithmic framework that leverages interactions with expert policies for efficient policy optimization. Here policies are optimized by performing online learning on a sequence of loss functions that encourage the learner to mimic expert actions, and if the online learning has no regret, the agent can provably learn an expert-like policy. Online IL has demonstrated empirical successes in many applications and interestingly, its policy improvement speed observed in practice is usually much faster than existing theory suggests. In this work, we provide an explanation of this phenomenon. Let xi denote the policy class bias and assume the online IL loss functions are convex, smooth, and non-negative. We prove that, after N rounds of online IL with stochastic feedback, the policy improves in tildeO(1/N + √xi/N) in both expectation and high probability. In other words, we show that adopting a sufficiently expressive policy class in online IL has two benefits: both the policy improvement speed increases and the performance bias decreases.