# On Efficient Online Imitation Learning via Classification

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

## Key facts

- Cited by 5 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 33 of its 91 references that are in the map.
- First posted on arXiv 26 Sep 2022.

## Placed in

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

## Builds on (most cited first, 30 of 33)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [Scheduled Sampling for Sequence Prediction with Recurrent Neural Networks](https://mlsanity.com/paper/1506.03099/) (2015)
- [An Algorithmic Perspective on Imitation Learning](https://mlsanity.com/paper/1811.06711/) (2018)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [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)
- [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015)
- [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)
- [Error Bounds of Imitating Policies and Environments](https://mlsanity.com/paper/2010.11876/) (2020)
- [Robust Imitation of Diverse Behaviors](https://mlsanity.com/paper/1707.02747/) (2017)
- [Provably Efficient Imitation Learning from Observation Alone](https://mlsanity.com/paper/1905.10948/) (2019)
- [On Oracle-Efficient PAC RL with Rich Observations](https://mlsanity.com/paper/1803.00606/) (2018)
- [Smoothed Online Learning is as Easy as Statistical Learning](https://mlsanity.com/paper/2202.04690/) (2022)
- [Fighting Bandits with a New Kind of Smoothness](https://mlsanity.com/paper/1512.04152/) (2015)
- [The Computational Power of Optimization in Online Learning](https://mlsanity.com/paper/1504.02089/) (2015)
- [Efficient Algorithms for Adversarial Contextual Learning](https://mlsanity.com/paper/1602.02454/) (2016)
- [Oracle-Efficient Online Learning and Auction Design](https://mlsanity.com/paper/1611.01688/) (2016)
- [Online Linear Optimization via Smoothing](https://mlsanity.com/paper/1405.6076/) (2014)
- [Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries](https://mlsanity.com/paper/2202.08549/) (2022)
- [BISTRO: An Efficient Relaxation-Based Method for Contextual Bandits](https://mlsanity.com/paper/1602.02196/) (2016)
- [Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits](https://mlsanity.com/paper/1606.00313/) (2016)
- [Concentration Inequalities for Multinoulli Random Variables](https://mlsanity.com/paper/2001.11595/) (2020)
- [Online Learning with Continuous Variations: Dynamic Regret and Reductions](https://mlsanity.com/paper/1902.07286/) (2019)
- [Smooth Imitation Learning for Online Sequence Prediction](https://mlsanity.com/paper/1606.00968/) (2016)
- [Online Learning via the Differential Privacy Lens](https://mlsanity.com/paper/1711.10019/) (2017)
- [Predictor-Corrector Policy Optimization](https://mlsanity.com/paper/1810.06509/) (2018)

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

- [Imitation Learning in Discounted Linear MDPs without exploration assumptions](https://mlsanity.com/paper/2405.02181/) (2024)
- [Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning](https://mlsanity.com/paper/2505.17610/) (2025)
- [Interactive and Hybrid Imitation Learning: Provably Beating Behavior Cloning](https://mlsanity.com/paper/2412.07057/) (2024)
- [Agnostic Interactive Imitation Learning: New Theory and Practical Algorithms](https://mlsanity.com/paper/2312.16860/) (2023)
- [Multi-agent imitation learning with function approximation: Linear Markov games and beyond](https://mlsanity.com/paper/2602.22810/) (2026)

## Abstract (arXiv)

Imitation learning (IL) is a general learning paradigm for tackling sequential decision-making problems. Interactive imitation learning, where learners can interactively query for expert demonstrations, has been shown to achieve provably superior sample efficiency guarantees compared with its offline counterpart or reinforcement learning. In this work, we study classification-based online imitation learning (abbrev. COIL) and the fundamental feasibility to design oracle-efficient regret-minimization algorithms in this setting, with a focus on the general nonrealizable case. We make the following contributions: (1) we show that in the COIL problem, any proper online learning algorithm cannot guarantee a sublinear regret in general; (2) we propose Logger, an improper online learning algorithmic framework, that reduces COIL to online linear optimization, by utilizing a new definition of mixed policy class; (3) we design two oracle-efficient algorithms within the Logger framework that enjoy different sample and interaction round complexity tradeoffs, and conduct finite-sample analyses to show their improvements over naive behavior cloning; (4) we show that under the standard complexity-theoretic assumptions, efficient dynamic regret minimization is infeasible in the Logger framework. Our work puts classification-based online imitation learning, an important IL setup, into a firmer foundation.