  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 $\tilde{O}(1/N + \sqrt{\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.
