Abstract
Online imitation learning (IL) is an algorithmic framework that leverages interactions with expert policies for efficient policy optimization. Policies are optimized by performing online learning on a sequence of loss functions that encourage the learner to mimic expert actions. While online IL has demonstrated empirical success, 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 (CSN). 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. This shows that adopting a sufficiently expressive policy class in online IL has two benefits: both the policy improvement speed increases and the performance bias decreases.
Introduction: The Theory-Practice Gap
In sequential decision-making, Imitation Learning (IL) allows an agent to learn by mimicking an expert rather than through trial-and-error. Online IL algorithms, such as DAgger, treat this as an iterative online learning problem where the agent's policy is updated based on expert feedback.
However, a significant "theory-practice gap" has long persisted. Standard online learning theory suggests that for convex losses, the error should decrease at a rate of $O(1/\sqrt{N})$. Yet, researchers consistently observe much faster improvement in practice. While "fast rates" ($O(1/N)$) can be proven under strong convexity, this condition rarely holds in high-dimensional robotics or deep learning. This paper bridges this gap by introducing a more realistic explanation for empirical speedups.
Methodology: Bias-Dependent Convergence
The authors introduce a theoretical framework based on bias-dependent convergence rates. This approach hinges on several key components:
- CSN Losses: The analysis assumes imitation losses are Convex, Smooth, and Non-negative (CSN), covering common choices like squared error or KL-divergence.
- Regret Decomposition: The cumulative loss is decomposed into terms that explicitly account for the policy class bias ($\xi$)—a measure of how well the chosen model can represent the expert.
- Martingale Concentration: Advanced martingale concentration inequalities are used to handle the non-stationary nature of online learning, where the data distribution changes as the learner improves.
- Adaptive Stepsizes: The proofs extend to practical, adaptive optimizers like AdaGrad.
Key Insights: The Expressivity Bonus
The core finding is that model expressivity provides a "speed bonus." Usually, a larger model is thought to only provide lower final error. This work shows it also accelerates learning.
The proven rate of $\tilde{O}(1/N + \sqrt{\xi/N})$ provides a smooth transition: when bias ($\xi$) is high, the slow $1/\sqrt{N}$ rate dominates. As the model becomes more expressive and $\xi$ approaches zero, the rate naturally accelerates to $1/N$. This provides a theoretical justification for fast improvement that doesn't rely on the restrictive assumption of strong convexity.
Empirical Results
The theory was validated using a simulated CartPole balancing task. By restricting the model's capacity using $\ell_2$-norm constraints, the researchers could control the bias ($\xi$) and observe its effect on the learning curve.
As shown in the log-log plots, with high bias (tight constraints), the slope is roughly $-1/2$, corresponding to the $O(1/\sqrt{N})$ rate. As constraints are relaxed (lower bias), the slope moves toward $-1$, confirming the $O(1/N)$ improvement. Interestingly, this acceleration was observed even when training full neural networks, suggesting the insights from the convex analysis have broader applicability.
Conclusion
This work explains why online IL often "clicks" so quickly in real-world applications. By proving that expressivity directly impacts convergence speed, the authors provide a new lens through which to view model selection in imitation learning. Future research may leverage these "self-bounding" properties to design new algorithms that proactively use model capacity to achieve even faster learning.
Summary updated