Explaining fast improvement in online imitation learning

Xinyan Yan, Byron Boots, Ching-An ChengUAI 2021 · OpenReview

Abstract

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 surrogate loss functions that are updated as the agent collects new data. While standard online learning theory suggests a "slow" convergence rate of $O(1/\sqrt{N})$, this paper bridges the gap by accounting for policy class bias, proving that sufficiently expressive models can achieve an $O(1/N)$ convergence rate, explaining the efficiency of these algorithms in practice.

Introduction

In Online Imitation Learning (IL), such as the DAgger algorithm, an agent learns by iteratively interacting with an expert. Traditionally, this is analyzed as a "no-regret" online learning problem. Under standard assumptions of convex and Lipschitz losses, theory predicts a convergence rate of $O(1/\sqrt{N})$, implying a high number of rounds ($N$) are required to reach an optimal policy.

However, a significant mismatch exists between this theory and real-world performance. Practitioners have observed that Online IL is remarkably fast; for instance, autonomous driving models can learn expert behavior in just a few rounds. This paper investigates this discrepancy, arguing that existing theory is overly pessimistic because it neglects the stability provided by a consistent expert and the specific properties of IL loss functions.

Theoretical Framework

The authors move away from adversarial analysis, introducing a framework that accounts for policy class bias ($\xi$). This bias measures how well the chosen policy class can mimic the expert. The analysis is built on three pillars:

  1. CSN Loss Functions: Losses are assumed to be Convex, Smooth, and Non-negative (CSN), such as squared error or KL-divergence.
  2. Bias Sensitivity: The convergence rate is explicitly linked to the expressivity of the model.
  3. New Regret Decomposition: Instead of standard martingale analysis, the authors use concentration inequalities based on "path-wise statistics" to capture the self-bounding properties of smooth, non-negative losses.
Comparison of Online IL with other common learning paradigms, highlighting its unique stochastic and non-stationary nature.

As shown in the table above, Online IL occupies a unique position compared to standard online learning or stochastic bandits. It is both stochastic and non-stationary, yet it lacks the partial feedback constraints of bandits, allowing for more efficient optimization through online estimators.

Key Insights: The Speed of Expressivity

A central finding is the "double benefit" of model expressivity. While larger models typically reduce final error (lower bias), this work proves they also accelerate the learning process. As the policy class becomes more expressive (bias $\xi \to 0$), the learning rate transitions from the slow $O(1/\sqrt{N})$ to a fast $O(1/N)$.

This acceleration is possible because the expert in IL is relatively fixed, providing a stability effect. By assuming the loss is smooth and non-negative, the variance of the gradients can be related directly to the value of the loss itself. This "self-bounding" property is the mathematical foundation for the faster convergence rates.

Empirical Validation

The theoretical bounds were validated using a simulated CartPole balancing task. By manipulating the $\ell_2$-norm constraints on the learner's policy weights, the researchers simulated varying levels of "bias."

The results confirmed the theory:

  • Unbiased policies (high expressivity) showed an error decay slope near $-1$ on log-log plots, corresponding to the $O(1/N)$ rate.
  • Biased policies (low expressivity) showed a slope closer to $-1/2$, matching the standard $O(1/\sqrt{N})$ rate.

Furthermore, these "fast improvement" trends were observed even with deep neural networks, suggesting that the insights remain robust even when strict convexity assumptions are technically violated.

Conclusion

This work provides a theoretical explanation for the practical success of Online IL. By proving a bound of $\tilde{O}(1/N + \sqrt{\xi/N})$, the authors show that the speed of imitation learning is fundamentally tied to the expressivity of the policy class. Future work aims to extend these proofs to non-convex settings to more directly model the behavior of deep learning architectures in imitation tasks.

Summary updated

Abstract

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 learn...
BibTeX
@inproceedings{yan2021explaining,
  author = {Xinyan Yan and Byron Boots and Ching-An Cheng},
  title = {{Explaining fast improvement in online imitation learning}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=JV_bJCkQIqQ},
}
Figure