Technical Summary: Behavior Cloning is Not All You Need

Problem Statement

The paper addresses a central puzzle in Imitation Learning (IL): while theoretical results suggest that offline methods like Behavioral Cloning (BC) can achieve horizon-free, optimal performance in the clean expert setting, empirical evidence in modern applications (particularly Large Language Model training via On-Policy Distillation, or OPD) consistently shows that online methods outperform offline ones.

The authors propose a noisy expert model to explain this discrepancy. In this setting, the learner does not have access to a perfect expert policy $\pi^\star$, but rather a corrupted version $\pi^\star_\eta = (1-\eta)\cdot\pi^\star + \eta\cdot\nu$, where $\eta$ is the noise level and $\nu$ is a noise distribution. The learner's goal is to learn a policy $\hat{\pi}$ that competes with the expected reward of the clean expert $\pi^\star$, despite only having access to trajectories generated by the noisy expert. This model captures real-world scenarios such as training language models on imperfect human text, distilling from large teacher models that are not fully converged, or reasoning tasks where the "expert" is stochastic.

Methodology and Theoretical Framework

The authors analyze both offline and online IL settings under this noisy expert assumption, utilizing the Hellinger distance between trajectory distributions as a proxy for regret.

1. Offline Imitation Learning (The Hardness Result)

In the offline setting, the learner is given a fixed dataset of $n$ trajectories from $\pi^\star_\eta$.

• Analysis: The authors show that to recover a policy close to the clean expert $\pi^\star$, one must invert the noise. They derive a bound relating the Hellinger distance of the clean trajectories $D_H^2(P_{\pi^\star}, P_{\hat{\pi}})$ to the Hellinger distance of the noisy trajectories $D_H^2(P_{\pi^\star_\eta}, P_{\hat{\pi}_\eta})$.
• Key Finding: Without additional assumptions, the sample complexity required to compete with the clean expert grows exponentially with the horizon $H$ (specifically, scaling as $(1-\eta)^{-H}$). Even with a "domination condition" (where the noise distribution is dominated by the policy class), the dependence remains exponential in $H$ if the noise is not negligible relative to $1/H$.
• Lower Bound: The authors prove this exponential dependence is fundamental. They construct a counter-example showing that any offline algorithm requires sample complexity exponential in $H$ to achieve a constant error, rendering offline IL fundamentally intractable in long-horizon noisy settings.

2. Online Imitation Learning (The Solution)

In the online setting, the learner can interact with the environment, roll out its current policy, and query the noisy expert for actions at the visited states.

• Augmented Trajectories: The authors introduce the concept of augmented trajectory distributions $P_{\pi, \pi'}$, where the learner rolls out policy $\pi$ but queries the expert $\pi'$ for actions at each state. This allows the learner to compare its own trajectory distribution against the expert's behavior on the same states.
• Theoretical Guarantee: They prove that the suboptimality of the learned policy can be bounded by the Hellinger distance (or KL divergence) between the augmented trajectory distributions of the learner and the noisy expert. Crucially, under a $\kappa$-domination condition (where the noise distribution is dominated by the expert and learner policies), this bound becomes horizon-free. Even without this condition, the dependence on the horizon is only polynomial ($\sqrt{H}$), a stark contrast to the exponential dependence in the offline case.
• Algorithm (NAIL): The authors propose NAIL (Noise-robust Aggregation for Imitation Learning). Unlike standard DAgger which learns step-wise policies, NAIL aggregates policies at the trajectory level using exponential weights on the negative log-likelihood of augmented trajectories.
  • Known Corruption: NAIL achieves a regret bound scaling as $H \sqrt{\log|\Pi|/n}$.
  • Unknown Corruption (Deterministic Expert): For the case where the expert is deterministic and the noise is "smooth" (bounded probability mass on any action), the authors propose NAILGUN. This algorithm achieves a horizon-free regret bound of $\log|\Pi|/n$ without requiring knowledge of the noise level $\eta$ or distribution $\nu$.

Key Contributions

1. Theoretical Separation: The paper establishes a sharp separation between offline and online IL in the presence of noisy experts. It proves that offline learning is fundamentally hard (exponential in horizon) while online learning can achieve horizon-free or polynomial horizon guarantees.
2. Noisy Expert Model: The introduction of a general noisy expert model ($\pi^\star_\eta$) that explains the empirical success of OPD over Supervised Fine-Tuning (SFT) in training language models, even when the teacher and student architectures are identical (ruling out misspecification as the sole cause).
3. Augmented Trajectory Analysis: The derivation of bounds linking the clean expert's performance to the divergence between augmented trajectory distributions ($P_{\hat{\pi}, \pi^\star_\eta}$ vs $P_{\hat{\pi}, \hat{\pi}_\eta}$), providing a theoretical justification for on-policy distillation objectives.
4. Algorithms and Bounds:
   • NAIL: An algorithm for known corruption settings with near-optimal sample complexity.
   • NAILGUN: An algorithm for unknown corruption settings (deterministic expert) that achieves horizon-free guarantees.
   • Lower Bounds: Matching lower bounds demonstrating the optimality of the proposed algorithms up to constant factors.

Experimental Results

The authors validate their theory on two tasks:

1. Modular Addition (Synthetic): A task requiring a chain of thought to sum numbers modulo 7.
   • Clean Expert: Offline BC (SFT) performs best, consistent with theory.
   • Noisy Expert: Offline BC and standard OPD fail to learn. The proposed NAIL variants (minimizing forward/reverse KL on augmented trajectories) achieve perfect accuracy.
2. GSM-8K (Natural Language): A math reasoning benchmark using Gemma models.
   • Clean Expert: Online methods outperform offline BC.
   • Noisy Expert: Only NAIL variants remain effective, achieving non-trivial accuracy, while standard OPD and SFT fail completely (0% accuracy).

These results confirm that the loss functions derived from the theoretical analysis (specifically those involving augmented trajectories) are more robust to noisy expert feedback than standard supervised learning objectives.

Significance and Claims

The paper claims to provide a theoretical foundation for why on-policy distillation (OPD) outperforms standard supervised fine-tuning (SFT) when training language models from imperfect teachers.

• Explanation of Empirical Phenomena: It resolves the "theory vs. practice" gap in IL by showing that the assumption of a "clean" expert is often violated in practice (due to noise in human data or imperfect teacher models), and that under such noise, online interaction is not just beneficial but necessary to avoid exponential sample complexity.
• Principled Loss Function: The analysis leads to an alternative loss function (minimizing divergence on augmented trajectories) that is commonly considered empirically for LM training but lacked rigorous justification. The paper provides this justification.
• Limitations: The authors are modest about their claims, noting that their results rely on finite policy classes, idealized corruption models, and specific assumptions (like deterministic experts for the unknown corruption case). They acknowledge that translating these results directly to practice requires further work on more sophisticated noise models and scaling experiments.

In summary, the paper argues that Behavior Cloning is not all you need when experts are noisy; instead, On-Policy Distillation is theoretically optimal for recovering clean expert behavior from noisy data in long-horizon tasks.