DAgger expliqué : pourquoi le Behavior Cloning déraille et ce que l'agrégation de données prouve réellement

Il y a un échec spécifique que tous ceux qui entraînent une policy de manipulation rencontrent tôt ou tard. La policy tend le bras vers le cube, se rapproche à deux centimètres, hésite, dérive latéralement, puis fait quelque chose sans rapport avec la tâche. La perte de validation était bonne. Le rejeu en boucle ouverte contre les épisodes retenus était bon. Et pourtant le bras finit dans une pose qui n'apparaît nulle part dans les données d'entraînement, et de là il n'a rien de sensé à dire.

Cet échec a un nom et une théorie établie derrière lui. C'est le premier de quatre articles sur DAgger, et il couvre l'argument lui-même : pourquoi adapter une policy sur les trajectoires du démonstrateur produit une erreur qui peut croître avec le carré de la longueur de l'épisode, ce que l'agrégation de données change, et ce que la preuve sans regret ne promet pas. La boucle sur matériel réel est couverte dans exécuter une boucle DAgger sur un SO-100, la variante en gate humain dans HG-DAgger et interventions en gate humain, et la question de mesure dans mesurer une boucle DAgger.

L'hypothèse que le Behavior Cloning fait silencieusement

Un ensemble de données de démonstration est un tas de paires observation-action. Le Behavior Cloning ajuste une fonction à ce tas avec l'apprentissage supervisé ordinaire et s'arrête là. C'est l'idée la plus ancienne du domaine. Le ALVINN de Pomerleau, en 1988, était un réseau de rétropropagation à trois couches qui prenait les images d'une caméra et d'un télémètre laser et produisait la direction dans laquelle le véhicule devait se déplacer ; il a été entraîné sur les images de route simulées et a suivi les routes réelles sous certaines conditions de terrain. La recette n'a pas beaucoup changé ; les réseaux oui.

Ce qui est omis est une vérification de la provenance de ces paires. Chacune d'elles se trouve sur une trajectoire que le démonstrateur a produite. La policy que vous déployez produit la sienne. Au moment où elle dévie, elle est interrogée sur des états qui n'étaient pas dans la distribution d'entraînement, et sa réponse l'éloigne davantage. Ross, Gordon et Bagnell ouvrent le papier DAgger avec exactement ceci : la prédiction séquentielle viole l'hypothèse i.i.d. sous-jacente l'apprentissage statistique, car les propres prédictions de l'apprenant déterminent les entrées qu'il voit ensuite.

L'illustration la plus claire dans ce papier n'est pas un robot du tout. Le clonage d'un planificateur quasi-optimal pour Super Mario Bros. a produit une policy qui s'est régulièrement coincée contre un obstacle au lieu de le sauter. La raison est tout l'argument en une phrase : l'expert sautait toujours d'une distance confortable, donc l'ensemble de données ne contenait aucun état dans lequel Mario était pressé contre un obstacle, et donc aucun étiquetage pour ce qu'il faut faire une fois qu'il l'était.

Remplacez Mario par un bras SO-100 et la structure est identique. Vos démonstrations montrent une approche propre et une saisie propre, pas la pince qui se ferme deux centimètres trop court - donc la policy n'a aucune idée de ce qu'il faut faire de là, et tout ce qu'elle devine l'éloigne davantage. Covariate shift est une propriété de la procédure de collecte de données, pas de l'architecture du réseau.

D'où vient le terme quadratique

Le papier 2010 AISTATS de Ross et Bagnell, Réductions efficaces pour l'apprentissage par imitation, rend la composition précise. Soit T l'horizon de la tâche, soit le coût de la tâche borné dans l'intervalle unité, et soit epsilon la perte de substitution mesurée sous la distribution d'états de l'expert - le nombre que votre ensemble de validation rapporte. Alors le coût supplémentaire de l'exécution de cette policy pour T étapes, par rapport à l'expert, est borné par T au carré fois epsilon. Ross, Gordon et Bagnell réénoncent ceci comme Théorème 2.1 dans le papier DAgger et ajoutent la phrase qui compte : la borne est étroite. Des problèmes existent où une policy avec perte epsilon sur la distribution de l'expert encourt réellement un coût supplémentaire croissant quadratiquement en T.

Étroit ne signifie pas typique. Le terme quadratique est un pire cas sur une classe de problèmes, pas une prédiction sur votre tâche de prise et placement. Ce qu'il établit c'est que plus de démonstration experte ne peut pas enlever le problème : cela ne fait qu'affiner l'estimation d'epsilon sur une distribution sur laquelle la policy ne sera pas testée.

La route de sortie est dans le même papier, réénoncée comme Théorème 2.2. Si une policy atteint une perte epsilon sous la propre distribution d'états, et une seule mauvaise action coûte au maximum u en coût-pour-aller-au-but sous l'expert, le coût supplémentaire est borné par u fois T fois epsilon - linéaire dans l'horizon. La constante u est la quantité intéressante : au maximum 1 pour le désaccord 0-1 avec l'expert, et O(1) chaque fois que l'expert peut se rétablir en quelques étapes. Dans le pire cas c'est O(T), et la borne linéaire n'est pas meilleure que la quadratique.

Les deux tentatives qui ont précédé DAgger

L'entraînement par anticipation est la réponse honnête mais impraticable. Entraîner une policy séparée pour chaque pas de temps, dans l'ordre, chacun sur la distribution d'états induite par les policies déjà fixées pour les étapes antérieures, donc chaque policy voit exactement la distribution qu'elle affrontera. Le piège est dans la description : T policies, entraînées séquentiellement, pas d'arrêt anticipé. Pour un épisode de manipulation à 30 images par seconde, T est dans les centaines.

SMILe, du même papier, et SEARN, du travail de Daume, Langford et Marcu sur la prédiction structurée, prennent l'autre route : une policy stationnaire, mais stochastique. Chaque itération entraîne un composant et l'ajoute à un mélange, décalant la masse de probabilité loin de l'expert. Le résultat est un mélange dans lequel certains composants sont pires que d'autres - sur un bras physique, un contrôleur qui peut échantillonner un mauvais composant en mouvement. C'est la motivation affichée pour préférer une policy stationnaire déterministe à la place.

DAgger : une idée, une boîte

L'agrégation de données garde la policy déterministe et déplace la correction dans la collecte de données. Chaque tour : exécuter la policy actuelle, enregistrer les états qu'elle visite, demander à l'expert quelle est l'action correcte dans chacun, ajouter ces paires à l'ensemble de données que vous avez déjà, réentraîner sur l'union. Le nom est l'algorithme - vous agréger, vous ne jetez jamais.

D            <- {}                      # the aggregate dataset
pi_hat_1     <- any policy in Pi

for i = 1 .. N:
    pi_i  = beta_i * expert  +  (1 - beta_i) * pi_hat_i
    roll out pi_i for T steps, record every visited state s
    D_i   = { (s, expert(s))  for every visited state s }
    D     = D  union  D_i               # aggregate, do not replace
    pi_hat_{i+1} = train on all of D

return the best pi_hat_i on a validation set

Trois détails portent plus de poids qu'ils ne l'ont l'air. Les étiquetages sont pour les états visités par la policy mixte, mais les actions proviennent de l'expert - la policy fournit les questions, l'expert les réponses. Le réentraînement est sur l'agrégat entier, ce qui fait de chaque tour une étape Suivre-Le-Leader : au tour n vous choisissez la meilleure policy avec le recul sur chaque trajectoire jusqu'à présent. C'est ce cadrage sur lequel la preuve s'appuie. Et l'algorithme se termine en retournant la meilleure policy de la séquence comme choisie sur un ensemble de validation, car les théorèmes garantissent que certaine policy dans la séquence est bonne, pas que la dernière l'est.

La planification bêta, et pourquoi ce n'est pas un bouton de réglage

La policy mixte est beta_i fois l'expert plus un moins beta_i fois l'apprenant. Le point est pratique : les premières policies apprises sont entraînées sur très peu de données, font beaucoup d'erreurs, et auraient autrement passé l'exécution dans des états qui deviennent hors de propos une fois que la policy s'améliore.

La théorie impose exactement une condition : la moyenne mobile des bêtas doit aller vers zéro. L'analyse fonctionne avec beta_i borné par (1 - alpha) à la puissance i-1, pour une constante alpha indépendante de T.

L'écart entre 2980 et 3030 sur une échelle montant à environ 4300 est faible, mais l'explication du papier c'est la note pratique la plus utile dans la section. Avec la planification sans paramètre, Mario s'est coincé au même endroit tôt et a généré une masse de données quasi-dupliquées à partir de ce seul endroit ; laisser l'expert conduire une fraction du temps l'a à la fois débloqué et élargi la variété d'états. La planification est moins sur le rapport de mélange que sur si votre collecte de données continue à produire de nouveaux états ou le même échec.

La garantie : une réduction à l'apprentissage en ligne sans regret

Voilà le geste qui rend le papier ce qu'il est. Traiter chaque tour DAgger comme un exemple dans un problème d'apprentissage en ligne, où la perte au tour i est la perte de substitution sous la distribution d'états de la policy utilisée au tour i. L'apprenant s'engage à une policy avant de voir cette perte, et la séquence est non-stationnaire parce qu'elle dépend des policies produites jusqu'à présent.

Un algorithme est sans regret si sa perte moyenne sur N tours s'approche de celle de la meilleure policy unique avec le recul. Suivre-Le-Leader sur les pertes fortement convexes est un tel algorithme, avec un regret moyen rétrécissant de l'ordre de 1/N - et le réentraînement sur l'agrégat entier est précisément Suivre-Le-Leader. Tout autre apprenant sans regret conviendrait aussi bien : l'analyse est une réduction, pas une propriété d'un optimiseur.

Un lemme comble l'écart entre la policy mixte qui a collecté les données et la policy apprise qui sera déployée : le Lemme 4.1 borne la distance L1 entre leurs distributions d'états par 2 T beta_i. C'est pourquoi les bêtas doivent décroître - tandis que l'expert tient toujours l'autorité de contrôle appréciable, les états que vous collectez ne sont pas les états que votre policy produira. Combiné le lemme avec la borne de regret et le résultat principal suit : après environ T itérations, certaine policy dans la séquence a une perte de substitution sous sa propre distribution à l'intérieur de O(1/T) d'epsilon_N. Injectez cela dans la borne linéaire et vous atterrissez au Théorème 3.2.

Le côté empirique est modeste selon les standards actuels. Dans Super Tux Kart la ligne de base supervisée n'a pas amélioré ses chutes moyennes par tour à mesure que plus de données arrivaient, DAgger a atteint une policy qui n'a jamais quitté la piste après quinze itérations, et SMILe après vingt tombait toujours environ deux fois par tour. Sur le benchmark d'écriture manuscrite, la précision des caractères s'est exécutée 82 pour cent sans structure, 83,6 pour cent supervisé, 85,5 pour cent avec DAgger. Aucun de ceux-ci n'est un résultat de manipulation.

Ce que la preuve ne promet pas

Les énoncés de théorème sont conditionnels, et les conditions portent du poids.

Un autre résultat est souvent cité comme une réfutation et ne l'est pas. Rajaraman, Yang, Jiao et Ramachandran étudient les limites minimax de l'apprentissage par imitation dans les MDPs épisodiques avec un espace d'états fini S et un horizon H, et prouvent une borne inférieure de sous-optimalité de l'ordre de |S| H au carré sur N qui tient même quand l'apprenant peut interroger activement l'expert aux états visités. C'est un taux de pire cas sur une classe de MDPs à un budget d'épisode fixe, et ce qu'il règne c'est l'idée que l'interaction améliore le taux minimax ; le théorème de DAgger est une déclaration différente, bornant la policy déployée par rapport à ce que sa propre classe de policy peut atteindre.

Swamy, Choudhury, Bagnell et Wu ont plus tard classé ces algorithmes par quels moments du comportement de l'expert ils correspondent, et ont introduit une notion de recouvrabilité des moments qui délimite comment bien chaque famille atténue l'erreur composée. Les sondages d'Osa et de Celemin couvrent le paysage algorithmique et les interfaces de rétroaction humaine.

La facture : étiqueter les états que l'expert n'a jamais produit

Tout ce qui précède assume un expert qui peut être interrogé n'importe où. En simulation avec un planificateur qui est presque gratuit - les expériences Mario ont utilisé un planificateur quasi-optimal avec accès complet à l'état du jeu. Avec un humain sur un robot c'est le coût dominant, et un curieux : l'humain doit produire une action correcte dans une configuration que sa propre compétence n'aurait jamais créée.

Kelly, Sidrane, Driggs-Campbell et Kochenderfer énoncent l'objection directement dans le papier HG-DAgger. Le DAgger vanille exige que l'expert fournisse des étiquetages d'actions sans être complètement en contrôle du système. Cela réduit la sécurité, et avec des experts humains c'est probable de dégrader la qualité des étiquetages collectés, qu'ils attribuent au lag d'actionneur perçu. L'étiquetage que vous récupérez n'est pas l'étiquetage que l'algorithme a supposé.

Laskey et collègues s'attaquent au problème de l'autre côté avec DART, et leur cadrage est franc : les techniques on-policy sont fastidieuses pour les superviseurs humains, ajoutent un fardeau de calcul, et peuvent visiter des états dangereux pendant l'entraînement. Leur alternative injecte du bruit calibré dans les propres démonstrations du superviseur, donc la récupération se démontre sans que le robot exécute jamais une policy non fiable. Sur le Humanoid MuJoCo ils rapportent DART diminuant le cumul de récompense du superviseur de 5 pour cent pendant l'entraînement, tandis que DAgger exécute des policies avec 80 pour cent moins de cumul de récompense que le superviseur ; sur la saisie en désordre avec un Toyota HSR, une augmentation moyenne de 62 pour cent sur le behavior cloning.

Le SafeDAgger de Zhang et Cho traite les interrogations à la policy de référence comme la ressource rares : une policy de sécurité séparée prédit, sans interroger, si la policy principale est sur le point de dévier de la référence au-delà d'un seuil, et seuls ces états sont remis. Tous les trois réagissent au même fait - l'analyse DAgger ne charge rien pour les étiquetages experts, et la réalité charge beaucoup.

Ce que cela signifie pour un SO-100 sur votre bureau

Traduisez l'horizon dans vos propres unités. Un épisode de vingt secondes à 30 images par seconde est 600 étapes de décision, et T dans chaque borne ci-dessus est ce nombre. À T = 600, la différence entre un terme qui s'échelle avec T et un qui s'échelle avec T au carré est la différence entre une policy qui se récupère d'une mauvaise approche et une qui ne le fait pas.

C'est en partie pourquoi le chunking d'actions aide : quand une policy émet une courte séquence d'actions par étape d'inférence, le nombre de points de décision baisse, et le nombre de chances de composé aussi. Zhao, Kumar, Levine et Finn nomment l'erreur composée comme la motivation pour Action Chunking avec Transformers, et rapportent 80 à 90 pour cent de succès sur six tâches du monde réel difficiles, sur du matériel bimanuel faible coût, à partir de dix minutes de démonstrations. Le chunking n'enlève pas le covariate shift - les états sont toujours ceux de la policy - mais il raccourcit l'horizon effectif. Voir chunking d'actions et le guide d'apprentissage par imitation SO-100.

La deuxième traduction est la métrique de progrès. Vous ne pouvez pas mesurer epsilon sous la propre distribution de la policy directement - cela a besoin d'actions experts au sol pour chaque état visité, la chose que vous essayez d'éviter de produire. Ce qu'une boucle en gate humain vous donne à la place c'est le taux d'intervention : la fraction de frames dans une exécution pendant laquelle l'humain a pris le contrôle. C'est un proxy, et il change pour des raisons sans rapport à la policy - un opérateur patient intervient moins. Utilisé systématiquement, c'est le nombre unique qui dit si un tour en valait la peine l'après-midi.

Une troisième traduction est un avertissement de qualité de données que l'analyse ne couvre pas. Mandlekar et collègues ont étudié six algorithmes d'apprentissage hors ligne sur cinq tâches de manipulation multi-étapes simulées et trois du monde réel, et rapportent une sensibilité aux choix de conception algorithmique, une dépendance à la qualité des démonstrations, et une variabilité causée par le critère d'arrêt. Belkhale, Cui et Sadigh arguent que la qualité du ensemble de données doit être formalisée par la divergence d'actions et la diversité de transitions, et notent que la diversité d'états n'est pas toujours bénéfique. Un tour DAgger ajoute des états que personne n'a choisi délibérément : certains sont les données de récupération dont vous avez besoin, certains sont le robot qui s'agite tandis que vous cherchez à tâtons le contrôle de takeover.

Mécaniquement un tour est six étapes : exécuter l'inférence avec enregistrement, prendre le contrôle quand la policy se comporte mal, examiner l'exécution et classer chaque épisode, synchroniser les corrections, composer un ensemble de données mixte à partir des originaux plus les corrections avec la sélection d'épisode faite explicitement par source, et continuer l'entraînement à partir du checkpoint précédent plutôt que le modèle de base. Sur ay-robots ces étapes existent comme boutons, ce qui élimine la plomberie mais pas le jugement. Deux mises en garde : continuer à partir d'un checkpoint initialise les poids et n'est pas une reprise d'optimiseur, et le mouvement d'alignement du bras leader est toujours légèrement testé sur matériel. Voir entraînement et ensembles de données.

L'arbre généalogique, en une table

Questions fréquemment posées

Où aller à partir d'ici

Si vous n'avez pas encore entraîné une policy, cette théorie est prématurée : enregistrez d'abord un ensemble de données, en commençant par entraîner votre première policy et le client de bureau. Si vous soupesez une centaine de démonstrations propres supplémentaires contre le démarrage des corrections : les démonstrations propres ne résolvent pas un problème de distribution. Pour la mécanique, continuez avec la variante en gate humain et puis la marche SO-100.