Résumé technique : Le Behavior Cloning ne suffit pas

Énoncé du problème

L'article traite d'un puzzle central de l'Apprentissage par Imitation (IL) : alors que les résultats théoriques suggèrent que les méthodes hors ligne (offline) comme le Behavior Cloning (BC) peuvent atteindre une performance optimale sans dépendance à l'horizon dans un cadre d'expert pur, les preuves empiriques dans les applications modernes (particulièrement l'entraînement de modèles de langage via la Distillation On-Policy, ou OPD) montrent systématiquement que les méthodes en ligne (online) surpassent les méthodes hors ligne.

Les auteurs proposent un modèle d'expert bruité pour expliquer cette divergence. Dans ce cadre, l'apprenant n'a pas accès à une politique d'expert parfaite $\pi^\star$, mais plutôt à une version corrompue $\pi^\star_\eta = (1-\eta)\cdot\pi^\star + \eta\cdot\nu$, où $\eta$ est le niveau de bruit et $\nu$ une distribution de bruit. L'objectif de l'apprenant est d'apprendre une politique $\hat{\pi}$ capable de rivaliser avec la récompense attendue de l'expert pur $\pi^\star$, malgré le fait qu'il n'ait accès qu'à des trajectoires générées par l'expert bruité. Ce modèle capture des scénarios du monde réel tels que l'entraînement de modèles de langage sur du texte humain imparfait, la distillation à partir de grands modèles enseignants qui ne sont pas totalement convergés, ou des tâches de raisonnement où l'« expert » est stochastique.

Méthodologie et cadre théorique

Les auteurs analysent les contextes d'IL hors ligne (offline) et en ligne (online) sous cette hypothèse d'expert bruité, en utilisant la distance de Hellinger entre les distributions de trajectoires comme indicateur du regret.

1. Apprentissage par Imitation Hors Ligne (Le résultat de difficulté)

Dans le cadre hors ligne, l'apprenant reçoit un ensemble de données fixe de $n$ trajectoires issues de $\pi^\star_\eta$.

• Analyse : Les auteurs montrent que pour récupérer une politique proche de l'expert pur $\pi^\star$, il faut inverser le bruit. Ils dérivent une borne reliant la distance de Hellinger des trajectoires pures $D_H^2(P_{\pi^\star}, P_{\hat{\pi}})$ à la distance de Hellinger des trajectoires bruitées $D_H^2(P_{\pi^\star_\eta}, P_{\hat{\pi}_\eta})$.
• Résultat clé : Sans hypothèses supplémentaires, la complexité d'échantillonnage requise pour rivaliser avec l'expert pur croît de manière exponentielle avec l'horizon $H$ (plus précisément, suivant une échelle de $(1-\eta)^{-H}$). Même avec une « condition de domination » (où la distribution de bruit est dominée par la classe de politiques), la dépendance reste exponentielle en $H$ si le bruit n'est pas négligeable par rapport à $1/H$.
• Borne inférieure : Les auteurs prouvent que cette dépendance exponentielle est fondamentale. Ils construisent un contre-exemple montrant que tout algorithme hors ligne nécessite une complexité d'échantillonnage exponentielle en $H$ pour atteindre une erreur constante, rendant l'IL hors ligne fondamentalement intraitable dans les contextes bruités à long horizon.

2. Apprentissage par Imitation En Ligne (La solution)

Dans le cadre en ligne, l'apprenant peut interagir avec l'environnement, déployer sa politique actuelle et interroger l'expert bruité pour obtenir les actions aux états visités.

• Trajectoires augmentées : Les auteurs introduisent le concept de distributions de trajectoires augmentées $P_{\pi, \pi'}$, où l'apprenant déploie la politique $\pi$ mais interroge l'expert $\pi'$ pour les actions à chaque état. Cela permet à l'apprenant de comparer sa propre distribution de trajectoire par rapport au comportement de l'expert sur les mêmes états.
• Garantie théorique : Ils prouvent que la sous-optimalité de la politique apprise peut être bornée par la distance de Hellinger (ou la divergence KL) entre les distributions de trajectoires augmentées de l'apprenant et de l'expert bruité. Crucialement, sous une condition de $\kappa$-domination (où la distribution de bruit est dominée par les politiques de l'expert et de l'apprenant), cette borne devient indépendante de l'horizon (horizon-free). Même sans cette condition, la dépendance vis-à-vis de l'horizon n'est que polynomiale ($\sqrt{H}$), un contraste frappant avec la dépendance exponentielle du cas hors ligne.
• Algorithme (NAIL) : Les auteurs proposent NAIL (Noise-robust Aggregation for Imitation Learning). Contra\text{à} l'algorithme DAgger standard qui apprend des politiques étape par étape, NAIL agrège les politiques au niveau de la trajectoire en utilisant des poids exponentiels sur la log-vraisemblance négative des trajectoires augmentées.
  • Corruption connue : NAIL atteint une borne de regret dont l'échelle est $H \sqrt{\log|\Pi|/n}$.
  • Corruption inconnue (Expert déterministe) : Pour le cas où l'expert est déterministe et le bruit est « lisse » (masse de probabilité bornée sur toute action), les auteurs proposent NAILGUN. Cet algorithme atteint une borne de regret indépendante de l'horizon de $\log|\Pi|/n$ sans nécessiter la connaissance du niveau de bruit $\eta$ ou de la distribution $\nu$.

Contributions clés

1. Séparation théorique : L'article établit une séparation nette entre l'IL hors ligne et en ligne en présence d'experts bruités. Il prouve que l'apprentissage hors ligne est fondamentalement difficile (exponentiel en horizon) tandis que l'apprentissage en ligne peut atteindre des garanties indépendantes de l'horizon ou polynomiales.
2. Modèle d'expert bruité : L'introduction d'un modèle d'expert bruité général ($\pi^\star_\eta$) qui explique le succès empirique de l'OPD sur le SFT (Supervised Fine-Tuning) lors de l'entraînement de modèles de langage, même lorsque le professeur et l'élève partagent la même architecture (excluant ainsi la spécification erronée comme seule cause).
3. Analyse de trajectoire augmentée : La dérivation de bornes reliant la performance de l'expert pur à la divergence entre les distributions de trajectoires augmentées ($P_{\hat{\pi}, \pi^\star_\eta}$ vs $P_{\hat{\pi}, \hat{\pi}_\eta}$), fournissant une justification théorique pour les objectifs de distillation on-policy.
4. Algorithmes et bornes :
   • NAIL : Un algorithme pour les contextes de corruption connue avec une complexité d'échantillonnage quasi optimale.
   • NAILGUN : Un algorithme pour les contextes de corruption inconnue (expert déterministe) qui atteint des garanties indépendantes de l'horizon.
   • Bornes inférieures : Des bornes inférieures correspondantes démontrant l'optimalité des algorithmes proposés à une constante près.

Résultats expérimentaux

Les auteurs valident leur théorie sur deux tâches :

1. Addition modulaire (Synthétique) : Une tâche nécessitant une chaîne de pensée pour sommer des nombres modulo 7.
   • Expert pur : Le BC hors ligne (SFT) est le plus performant, ce qui est cohérent avec la théorie.
   • Expert bruité : Le BC hors ligne et l'OPD standard échouent à apprendre. Les variantes proposées de NAIL (minimisant la KL directe/inverse sur les trajectoires augmentées) atteignent une précision parfaite.
2. GSM-8K (Langage naturel) : Un benchmark de raisonnement mathématique utilisant des modèles Gemma.
   • Expert pur : Les méthodes en ligne surpassent le BC hors ligne.
   • Expert bruité : Seules les variantes de NAIL restent efficaces, atteignant une précision non triviale, tandis que l'OPD standard et le SFT échouent complètement (0 % de précision).

Ces résultats confirment que les fonctions de perte dérivées de l'analyse théorique (spécifiquement celles impliquant des trajectoires augmentées) sont plus robustes au feedback de l'expert bruité que les objectifs standards d'apprentissage supervisé.

Signification et revendications

L'article affirme fournir une base théorique expliquant pourquoi la distillation on-policy (OPD) surpasse le fine-tuning supervisé (SFT) standard lors de l'entraînement de modèles de langage à partir d'enseignants imparfaits.

• Explication des phénomènes empiriques : Il résout l'écart entre « théorie et pratique » de l'IL en montrant que l'hypothèse d'un expert « pur » est souvent violée en pratique (en raison du bruit dans les données humaines ou des modèles enseignants imparfaits), et que sous un tel bruit, l'interaction en ligne n'est pas seulement bénéfique, mais nécessaire pour éviter une complexité d'échantillonnage exponentielle.
• Fonction de perte principalisée : L'analyse mène à une fonction de perte alternative (minimisant la divergence sur les trajectoires augmentées) qui est couramment utilisée de manière empirique pour l'entraînement des LM mais qui manquait de justification rigoureuse. L'article fournit cette justification.
• Limites : Les auteurs font preuve de modestie quant à leurs affirmations, notant que leurs résultats reposent sur des classes de politiques finies, des modèles de corruption idéalisés et des hypothèses spécifiques (comme les experts déterministes pour le cas de corruption inconnue). Ils reconnaissent que la traduction directe de ces résultats en pratique nécessite des travaux supplémentaires sur des modèles de bruit plus sophistiqués et des expériences à plus grande échelle.

En résumé, l'article soutient que le Behavior Cloning ne suffit pas lorsque les experts sont bruités ; au contraire, la Distillation On-Policy est théoriquement optimale pour récupérer le comportement d'un expert pur à partir de données bruitées dans des tâches à long horizon.