DAgger erklärt: Warum Behavior Cloning abweicht und was Dataset Aggregation eigentlich zeigt

Es gibt einen bestimmten Fehler, auf den jeder, der eine Manipulations-Policy trainiert, früher oder später trifft. Die Policy greift nach dem Würfel, kommt auf zwei Zentimeter heran, zögert, driftet seitwärts ab, dann macht sie etwas, das nichts mit der Aufgabe zu tun hat. Der Validierungsverlust war in Ordnung. Open-Loop-Wiedergabe gegen zurückgehaltene Episoden war in Ordnung. Und doch landet der Arm in einer Pose, die nirgends in den Trainingsdaten erscheint, und von dort aus hat er nichts Sinnvolles zu sagen.

Dieser Fehler hat einen Namen und einen gefestigten theoretischen Rahmen. Dies ist der erste von vier Artikeln über DAgger, und er behandelt das Argument selbst: warum das Anpassen einer Policy an die eigenen Trajektorien des Demonstrators einen Fehler erzeugt, der mit dem Quadrat der Episodenlänge wachsen kann, was Dataset Aggregation ändert, und was der No-Regret-Beweis nicht verspricht. Die Schleife auf echter Hardware wird behandelt in Ausführung einer DAgger-Schleife auf einem SO-100, die menschlich kontrollierte Variante in HG-DAgger und menschlich kontrollierte Eingriffe, und die Messfrage in Messung einer DAgger-Schleife.

Die Annahme, die Behavior Cloning stillschweigend trifft

Ein Demonstrationsdatensatz ist ein Haufen von Beobachtungs-Aktions-Paaren. Behavior Cloning passt mit gewöhnlichem Supervised Learning eine Funktion an diesen Haufen an und stoppt dann. Es ist die älteste Idee im Feld. Pomerleaus ALVINN, 1988, war ein dreilagiges Backpropagation-Netzwerk, das Bilder von einer Kamera und einem Laser-Entfernungsmesser aufnahm und die Richtung ausgab, in die sich das Fahrzeug bewegen sollte; es wurde auf simulierten Straßenbildern trainiert und folgte realen Straßen unter einigen Feldbedingungen. Das Rezept hat sich nicht viel geändert; die Netzwerke haben.

Was übersprungen wird, ist eine Überprüfung, woher diese Paare kamen. Jedes von ihnen liegt auf einer Trajektorie, die der Demonstrator erzeugt hat. Die Policy, die Sie einsetzen, erzeugt ihre eigene. In dem Moment, in dem sie abweicht, wird sie nach Zuständen befragt, die nicht in der Trainingsverteilung waren, und ihre Antwort treibt sie weiter hinaus. Ross, Gordon und Bagnell eröffnen das DAgger-Paper genau damit: sequenzielle Vorhersage verstößt gegen die i.i.d.-Annahme, die dem statistischen Lernen zugrunde liegt, weil die eigenen Vorhersagen des Lernenden bestimmen, welche Eingaben es danach sieht.

Die klarste Illustration in diesem Paper ist überhaupt kein Roboter. Das Klonen eines nahezu optimalen Planers für Super Mario Bros. erzeugte eine Policy, die sich wiederholt gegen ein Hindernis festfuhr, anstatt darüber zu springen. Der Grund ist das ganze Argument in einem Satz: Der Experte sprach immer aus einer komfortablen Entfernung, daher enthielt der Datensatz keinen Zustand, in dem Mario an ein Hindernis gedrückt wurde, und daher keine Kennzeichnung dafür, was zu tun wäre, wenn er es wäre.

Ersetzen Sie Mario durch einen SO-100 Arm und die Struktur ist identisch. Ihre Demonstrationen zeigen einen sauberen Ansatz und einen sauberen Griff, nicht den Greifer, der zwei Zentimeter zu kurz schließt – also hat die Policy keine Ahnung, was von dort aus zu tun ist, und alles, was sie rät, treibt sie weiter hinaus. Covariate Shift ist eine Eigenschaft der Datenerfassungsprozedur, nicht der Netzwerkarchitektur.

Woher der quadratische Term kommt

Das AISTATS-Paper von 2010 von Ross und Bagnell, Efficient Reductions for Imitation Learning, macht die Fehlerakkumulation präzise. Sei T der Aufgabenhorizont, die Aufgabenkosten seien im Einheitsintervall begrenzt, und epsilon sei der Surrogatverlust, gemessen unter dem Expert state distribution - die Zahl, die Ihr Validierungssatz meldet. Dann ist die Zusatzkosten für das Ausführen dieser Policy für T Schritte, relativ zum Experten, durch T zum Quadrat mal epsilon begrenzt. Ross, Gordon und Bagnell stellen dies als Satz 2.1 im DAgger-Paper wieder dar und fügen den Satz hinzu, der wichtig ist: die Schranke ist dicht. Es gibt Probleme, bei denen eine Policy mit epsilon Verlust auf der Verteilung des Experten wirklich Zusatzkosten entstehen, die quadratisch in T wachsen.

Dicht bedeutet nicht typisch. Der quadratische Term ist ein Worst Case über eine Klasse von Problemen, keine Vorhersage über Ihre Pick-and-Place-Aufgabe. Was es zeigt, ist, dass mehr Expert Demonstration das Problem nicht beheben kann: es schärft nur die Schätzung von epsilon auf einer Verteilung, auf der die Policy nicht getestet wird.

Die Fluchtroute ist im selben Paper, neu formuliert als Satz 2.2. Wenn eine Policy einen Verlust von epsilon unter ihrer eigenen Zustandsverteilung erreicht, und eine einzige falsche Aktion höchstens u in den zukünftigen Kosten unter dem Experten kostet, dann ist die Zusatzkosten durch u mal T mal epsilon – linear im Horizont – begrenzt. Die Konstante u ist die interessante Größe: höchstens 1 bei 0-1-Uneinigkeit mit dem Experten, und O(1), wann immer der Experte sich innerhalb weniger Schritte erholen kann. Im Worst Case ist es O(T), und die lineare Schranke ist dann nicht besser als die quadratische.

Die zwei Versuche, die vor DAgger kamen

Forward Training ist die ehrliche aber unpraktische Antwort. Trainieren Sie eine separate Policy für jeden Zeitschritt, der Reihe nach, jede auf der Zustandsverteilung, die durch die bereits festgelegten Policies für frühere Schritte induziert wird, damit jede Policy genau die Verteilung sieht, der sie sich stellen wird. Die Falle ist in der Beschreibung: T Policies, sequenziell trainiert, kein frühes Stoppen. Für eine ManipulationsEpisode bei 30 Bildern pro Sekunde ist T in den Hunderten.

SMILe, aus dem gleichen Paper, und SEARN, aus Daumes, Langfords und Marcus Arbeit zur strukturierten Vorhersage, gehen den anderen Weg: eine stationäre Policy, aber stochastisch. Jede Iteration trainiert eine Komponente und fügt sie zu einer Mischung hinzu, verschiebt die Wahrscheinlichkeitsmasse weg vom Experten. Das Ergebnis ist eine Mischung, in der einige Komponenten schlechter sind als andere – auf einem echten Arm ein Controller, der eine schlechte Komponente mitten in der Bewegung samplen kann. Das ist die angegebene Motivation dafür, eine stationäre deterministische Policy zu wollen.

DAgger: eine Idee, eine Box

Dataset Aggregation behält die deterministische Policy und verlagert die Reparatur in die Datenerfassung. Jede Runde: Führen Sie die aktuelle Policy aus, zeichnen Sie die Zustände auf, die sie besucht, fragen Sie den Experten, welche Aktion in jedem korrekt gewesen wäre, fügen Sie diese Paare dem bereits vorhandenen Dataset hinzu, trainieren Sie auf der Vereinigung neu. Der Name ist der Algorithmus – Sie aggregieren, Sie verwerfen niemals.

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

Drei Details tragen mehr Gewicht, als sie aussehen. Die Kennzeichnungen sind für Zustände, die von der gemischten Policy besucht werden, aber die Aktionen kommen vom Experten – die Policy stellt die Fragen, der Experte die Antworten. Das Neutraining erfolgt auf dem gesamten Aggregat, was jede Runde zu einem Follow-The-Leader-Schritt macht: in Runde n wählen Sie die beste Policy im Nachhinein über jede Trajektorie bisher. Dieser Rahmen ist das, worum sich der Beweis dreht. Und der Algorithmus endet damit, dass er die beste Policy in der Sequenz wie auf einem Validierungssatz gewählt zurückgibt, weil die Theoreme garantieren, dass irgendeine Policy in der Sequenz ist gut, nicht dass die letzte ist.

Der Beta-Plan und warum er kein Abstimmungsdrehknopf ist

Die gemischte Policy ist beta_i mal der Experte plus eins minus beta_i mal der Lerner. Der Punkt ist praktisch: die ersten gelernten Policies werden mit sehr wenig Daten trainiert, machen viele Fehler, und würden ansonsten das Ausrollen in Zuständen verbringen, die irrelevant werden, sobald sich die Policy verbessert.

Die Theorie setzt genau eine Bedingung auf: der laufende Durchschnitt der Betas muss gegen Null gehen. Die Analyse funktioniert mit beta_i begrenzt durch (1 - alpha) zur Potenz i-1, für eine Konstante alpha unabhängig von T.

Der Abstand zwischen 2980 und 3030 auf einer Skala, die auf etwa 4300 läuft, ist klein, aber die Erklärung des Papers dazu ist die nützlichste praktische Anmerkung in diesem Abschnitt. Mit dem parameterfreien Plan geriet Mario früh an derselben Stelle fest und erzeugte eine Fülle von nahezu doppelten Daten von diesem einen Ort; den Experten einen Teil der Zeit fahren zu lassen, befreite ihn und erweiterte die Vielfalt der Zustände. Der Plan ist weniger über das Mischungsverhältnis als darüber, ob Ihre Datenerfassung weiter neue Zustände erzeugt oder denselben Fehler.

Die Garantie: eine Reduktion auf No-Regret Online Learning

Hier ist der Zug, der das Paper zu dem macht, was es ist. Behandeln Sie jede DAgger-Runde als ein Beispiel in einem Online-Lernproblem, in dem der Verlust bei Runde i der Surrogatverlust unter der Zustandsverteilung der Policy ist, die bei Runde i verwendet wird. Der Lerner verpflichtet sich zu einer Policy, bevor dieser Verlust gesehen wird, und die Sequenz ist nicht-stationär, da sie von den bisherigen Policies abhängt.

Ein Algorithmus ist No-Regret, wenn sich sein durchschnittlicher Verlust über N Runden dem der besten einzelnen Policy im Nachhinein nähert. Follow-The-Leader bei stark konvexen Verlusten ist ein solcher Algorithmus, mit durchschnittlichem Bedauern, das auf der Ordnung von 1/N schrumpft – und Neutraining auf dem vollständigen Aggregat ist genau Follow-The-Leader. Jeder andere No-Regret-Lerner würde auch funktionieren: die Analyse ist eine Reduktion, nicht eine Eigenschaft eines Optimierers.

Ein Lemma überbrückt die Lücke zwischen der gemischten Policy, die die Daten sammelte, und der gelernten Policy, die eingesetzt wird: Lemma 4.1 begrenzt die L1-Entfernung zwischen ihren Zustandsverteilungen um 2 T beta_i. Dies ist der Grund, warum die Betas verfallen müssen – während der Experte immer noch erhebliche Kontrollautorit hält, sind die Zustände, die Sie sammeln, nicht die Zustände, die Ihre Policy erzeugen wird. Kombinieren Sie das Lemma mit der Bedauernisschranke und das Hauptergebnis folgt: Nach etwa T Iterationen hat irgendeine Policy in der Sequenz Surrogatverlust unter ihrer eigenen Verteilung innerhalb O(1/T) von epsilon_N. Geben Sie das in die lineare Schranke ein und Sie landen bei Satz 3.2.

Die empirische Seite ist nach heutigen Maßstäben bescheiden. In Super Tux Kart verbesserte sich das überwachte Basis nicht seine durchschnittlichen Stürze pro Runde, wenn mehr Daten ankamen, DAgger erreichte eine Policy, die nach fünfzehn Iterationen nie von der Strecke fiel, und SMILe nach zwanzig fiel immer noch etwa zweimal pro Runde. Bei der Handschrift-Benchmark lief die Zeichengenauigkeit bei 82 Prozent ohne Struktur, 83,6 Prozent überwacht, 85,5 Prozent mit DAgger. Keine davon ist ein Manipulationsergebnis.

Was der Beweis nicht verspricht

Die Satzaussagen sind bedingt, und die Bedingungen sind tragfähig.

Ein weiteres Ergebnis wird oft als Widerlegung zitiert und ist es nicht. Rajaraman, Yang, Jiao und Ramachandran studieren die Minimax-Grenzen des Imitation Learning in episodischen MDPs mit einem endlichen Zustandsraum S und Horizont H und beweisen eine Suboptimalitätsuntergrenze in der Größenordnung von |S| H zum Quadrat über N, die auch dann gilt, wenn der Lerner den Experten an besuchten Zuständen aktiv abfragen kann. Dies ist eine Worst-Case-Rate über eine Klasse von MDPs bei einem festen Episoden-Budget, und was es ausschließt, ist die Idee, dass Interaktion die Minimax-Rate verbessert; DAggers Theorem ist eine andere Aussage, die die eingesetzte Policy relativ zu dem begrenzt, was ihre eigene Policy-Klasse erreichen kann.

Swamy, Choudhury, Bagnell und Wu klassifizierten diese Algorithmen später danach, welche Momente des Expertenverhaltens sie abgleichen, und führten eine Vorstellung von Moment-Recoverability ein, die delineiert, wie gut jede Familie die Fehlerakkumulation verhindert. Die Umfragen von Osa und Celemin decken die algorithmische Landschaft und die Benutzerinterfaces für menschliches Feedback ab.

Die Rechnung: Kennzeichnung von Zuständen, die der Experte nie erzeugte

Alles oben setzt einen Experten voraus, der überall abgefragt werden kann. In der Simulation mit einem Planer, der fast kostenlos ist – die Mario-Experimente verwendeten einen nahezu optimalen Planer mit vollständigem Zugriff auf den Spielzustand. Mit einem Menschen an einem Roboter ist es die dominante Kosten, und eine eigenartige: Der Mensch muss eine korrekte Aktion in einer Konfiguration produzieren, die seine eigene Kompetenz nie hätte schaffen können.

Kelly, Sidrane, Driggs-Campbell und Kochenderfer stellen den Einwand direkt im HG-DAgger-Paper. Vanilla DAgger erfordert, dass der Experte Handlungsetiketten liefert, während er nicht vollständig über das System verfügt. Dies verringert die Sicherheit, und bei menschlichen Experten wird es wahrscheinlich die Qualität der gesammelten Bezeichnungen verschlechtern, was sie auf wahrgenommene Aktuator-Verzögerung zurückführen. Die Bezeichnung, die Sie zurückbekommen, ist nicht die Bezeichnung, die der Algorithmus angenommen hat.

Laskey und Kollegen greifen das Problem von der anderen Seite mit DART an, und ihre Rahmung ist blunt: On-Policy-Techniken sind für menschliche Betreuer mühsam, fügen Rechenlast hinzu und können während des Trainings gefährliche Zustände besuchen. Ihre Alternative spritzt kalibriertes Rauschen in die eigenen Demonstrationen des Supervisors, damit die Wiederherstellung demonstriert wird, ohne dass der Roboter jemals eine nicht vertrauenswürdige Policy ausführt. Auf MuJoCo Humanoid berichten sie, dass DART die kumulative Belohnung des Supervisors um 5 Prozent während des Trainings senkt, während DAgger Policies mit 80 Prozent weniger kumulativer Belohnung als der Supervisor ausführt; beim Greifen in Unordnung mit einem Toyota HSR ein Durchschnitt von 62 Prozent Anstieg über Behavior Cloning.

Zhang und Chos SafeDAgger behandelt Abfragen zur Referenz-Policy als knappe Ressource: eine separate Sicherheits-Policy sagt voraus, ohne zu fragen, ob die primäre Policy von der Referenz über einen Schwellenwert hinaus abweichen wird, und nur diese Zustände werden übergeben. Alle drei reagieren auf die gleiche Tatsache – die DAgger-Analyse berechnet nichts für Experten-Bezeichnungen, und die Realität berechnet viel.

Was das für einen SO-100 auf Ihrem Schreibtisch bedeutet

Übersetzen Sie den Horizont in Ihre eigenen Einheiten. Eine 20-Sekunden-Episode bei 30 Bildern pro Sekunde sind 600 Entscheidungsschritte, und T in jeder Schranke oben ist diese Zahl. Bei T = 600 ist der Unterschied zwischen einem Term, der mit T skaliert, und einem, der mit T zum Quadrat skaliert, der Unterschied zwischen einer Policy, die sich von einem schlechten Ansatz erholt, und einer, die es nicht tut.

Dies ist ein Teil, warum Action Chunking hilft: Wenn eine Policy eine kurze Sequenz von Aktionen pro Inferenzschritt ausgibt, sinkt die Anzahl der Entscheidungspunkte, und damit auch die Anzahl der Chancen sich zu verschärfen. Zhao, Kumar, Levine und Finn nennen Fehlerakkumulation als Motivation für Action Chunking with Transformers und berichten von 80 bis 90 Prozent Erfolg bei sechs schwierigen realen Aufgaben, auf kostengünstiger bimanualer Hardware, von zehn Minuten Demonstrationen. Chunking entfernt nicht den Covariate Shift – die Zustände sind immer noch die der Policy – aber es verkürzt den effektiven Horizont. Siehe Action Chunking und die SO-100 Imitation Learning Anleitung.

Die zweite Übersetzung ist die Fortschrittsmetrik. Sie können epsilon unter der eigenen Verteilung der Policy nicht direkt messen – das benötigt Grundwahrheits-Experten-Aktionen für jeden besuchten Zustand, das, was Sie zu vermeiden versuchen. Was eine menschlich kontrollierte Schleife Ihnen stattdessen gibt, ist die Interventionsrate: der Anteil der Frames in einer Ausführung, während deren der Mensch übernommen hatte. Es ist ein Proxy, und er ändert sich aus Gründen, die nichts mit der Policy zu tun haben – ein geduldiger Bediener greift weniger ein. Konsistent verwendet, ist es die eine Zahl, die sagt, ob eine Runde den Nachmittag wert war.

Eine dritte Übersetzung ist eine Datenqualitäts-Warnung, die die Analyse nicht abdeckt. Mandlekar und Kollegen studieren sechs Offline-Lern-Algorithmen auf fünf simulierten und drei realen Multi-Stage-Manipulations-Aufgaben und berichten von einer Empfindlichkeit gegenüber algorithmischen Designentscheidungen, einer Abhängigkeit von der Qualität der Demonstrationen und einer Variabilität, die durch das Stoppkriterium verursacht wird. Belkhale, Cui und Sadigh argumentieren, dass die Dataset-Qualität durch Aktionsdivergenz und Übergangsdiversität formalisiert werden sollte, und bemerken, dass Zustands-Vielfalt nicht immer vorteilhaft ist. Eine DAgger-Runde fügt Zustände hinzu, die niemand absichtlich wählte: einige sind die Wiederherstellungsdaten, die Sie benötigen, einige sind der Roboter, der sich wehrt, während Sie nach der Übernahmekontrolle herumspielen.

Mechanisch ist eine Runde sechs Schritte: Führen Sie die Inferenz mit Aufzeichnung durch, übernehmen Sie, wenn die Policy fehlerhaft ist, überprüfen Sie die Ausführung und reichen Sie jede Episode ein, synchronisieren Sie die Korrektionen, stellen Sie ein gemischtes Dataset aus Originen plus Korrektionen mit expliziter Episoden-Auswahl pro Quelle zusammen und setzen Sie das Training vom vorherigen Checkpoint statt des Basis-Modells fort. Bei ay-robots existieren diese Schritte als Schaltflächen, die die Rohrleitungen entfernen, aber nicht das Urteil. Zwei Vorbehalte: das Fortsetzen von einem Checkpoint initialisiert Gewichte und ist kein Optimierer-Resume, und die Leader-Arm-Ausrichtungsbewegung wird immer noch leicht auf Hardware getestet. Siehe Training und Datasets.

Der Stammbaum in einer Tabelle

Häufig gestellte Fragen

Wohin von hier aus gehen

Wenn Sie noch keine Policy trainiert haben, ist diese Theorie verfrüht: zeichnen Sie zuerst einen Datensatz auf, angefangen bei Trainieren Sie Ihre erste Policy und die Desktop-Client. Wenn Sie hundert weitere saubere Demonstrationen gegen den Start von Korrektionen abwägen: Saubere Demonstrationen beheben ein Verteilungsproblem nicht. Für die Mechanik, fahren Sie fort mit die menschlich kontrollierte Variante und dann die SO-100 Anleitung.