DAgger Spiegato: Perché il Behavior Cloning Diverge e Cosa Dimostra Davvero l'Aggregazione di Dataset

C'è un specifico fallimento che chiunque addestri una policy di manipolazione incontra prima o poi. La policy raggiunge il cubo, arriva a due centimetri di distanza, esita, devia lateralmente, poi fa qualcosa di estraneo al compito. La loss di validazione era corretta. La riproduzione ad anello aperto rispetto agli episodi trattenuti era corretta. Eppure il braccio finisce in una posa che non appare da nessuna parte nei dati di addestramento, e da lì non ha nulla di sensato da dire.

Quel fallimento ha un nome e un pezzo di teoria consolidata dietro di esso. Questo è il primo di quattro articoli su DAgger, e copre l'argomento stesso: perché adattare una policy sulle proprie traiettorie del dimostratore produce un errore che può crescere con il quadrato della lunghezza dell'episodio, cosa cambia l'aggregazione di dataset, e cosa la prova senza rammarico non promette. Il loop su hardware reale è coperto in esecuzione di un loop DAgger su un SO-100, la variante controllata dall'umano in HG-DAgger e interventi controllati dall'uomo, e la questione della misurazione in misurazione di un loop DAgger.

L'assunzione che il behavior cloning fa silenziosamente

Un dataset di dimostrazione è un mucchio di coppie osservazione-azione. Behavior cloning adatta una funzione a quel mucchio con l'apprendimento supervisionato ordinario e si ferma lì. È l'idea più antica del campo. ALVINN di Pomerleau, nel 1988, era una rete di backpropagazione a tre strati che prendeva immagini da una telecamera e un sensore laser e produceva la direzione in cui il veicolo dovrebbe viaggiare; è stata addestrata su immagini stradali simulate e ha seguito strade reali in alcune condizioni di campo. La ricetta non è cambiata molto; le reti sì.

Quello che viene saltato è un controllo su dove quelle coppie provenivano. Ognuna di esse si trova su una traiettoria che il dimostratore ha prodotto. La policy che implementi produce la sua. Nel momento in cui devia, viene interrogata su stati che non erano nella distribuzione di addestramento, e la sua risposta la sposta ulteriormente fuori. Ross, Gordon e Bagnell aprono il paper DAgger con esattamente questo: la predizione sequenziale viola l'assunzione i.i.d. sotto l'apprendimento statistico, perché le predizioni proprie dell'apprendente determinano gli input che vede dopo.

L'illustrazione più chiara in quel paper non è un robot affatto. Clonare un planner quasi ottimale per Super Mario Bros. ha prodotto una policy che ripetutamente si è bloccata contro un ostacolo invece di saltarlo. Il motivo è l'intero argomento in una frase: l'esperto ha sempre saltato da una distanza comoda, quindi il dataset non conteneva alcuno stato in cui Mario era premuto contro un ostacolo, e quindi nessuna etichetta per cosa fare una volta che lo era.

Scambia Mario con un SO-100 arm e la struttura è identica. Le tue dimostrazioni mostrano un approccio pulito e una presa pulita, non l'end-effector che si chiude due centimetri di distanza - quindi la policy non ha idea di cosa fare da lì, e qualunque cosa indovini la sposta ulteriormente fuori. Covariate shift è una proprietà della procedura di raccolta dati, non dell'architettura di rete.

Da dove viene il termine quadratico

Il paper AISTATS 2010 di Ross e Bagnell, Efficient Reductions for Imitation Learning, rende la composizione precisa. Sia T l'orizzonte del compito, sia il costo del compito limitato nell'intervallo unitario, e sia epsilon la loss sostitutiva misurata sotto la distribuzione di stato dell'esperto - il numero che il tuo set di validazione segnala. Allora il costo extra dell'esecuzione di quella policy per T passi, relativo all'esperto, è limitato da T al quadrato volte epsilon. Ross, Gordon e Bagnell riformulano questo come Teorema 2.1 nel paper DAgger e aggiungono la frase che importa: il limite è stretto. Esistono problemi dove una policy con epsilon loss sulla distribuzione dell'esperto davvero sostiene un costo extra che cresce quadraticamente in T.

Stretto non significa tipico. Il termine quadratico è un worst case su una classe di problemi, non una previsione del tuo compito di pick-and-place. Quello che stabilisce è che una maggiore dimostrazione dell'esperto non può rimuovere il problema: solo affina la stima di epsilon su una distribuzione su cui la policy non verrà testata.

Il percorso di fuga è nello stesso paper, riformulato come Teorema 2.2. Se una policy raggiunge la loss epsilon sotto la sua propria distribuzione di stato, e una singola azione sbagliata costa al massimo u in costo-da-azione sotto l'esperto, il costo extra è limitato da u volte T volte epsilon - lineare nell'orizzonte. La costante u è la quantità interessante: al massimo 1 per disaccordo 0-1 con l'esperto, e O(1) ogni volta che l'esperto può recuperare entro pochi passi. Nel peggiore dei casi è O(T), e il limite lineare non è allora migliore di quello quadratico.

I due tentativi che hanno preceduto DAgger

Forward training è la risposta onesta ma impratica. Allena una policy separata per ogni timestep, in ordine, ognuna sulla distribuzione di stato indotta dalle policy già fissate per i passi precedenti, così ogni policy vede esattamente la distribuzione che affronterà. Il trucco è nella descrizione: T policy, addestrate sequenzialmente, niente early stopping. Per un episodio di manipolazione episodio a 30 frame al secondo, T è nelle centinaia.

SMILe, dallo stesso paper, e SEARN, dal lavoro di Daume, Langford e Marcu sulla predizione strutturata, prendono l'altra strada: una policy stazionaria, ma stocastica. Ogni iterazione addestra un componente e lo aggiunge a una miscela, spostando la massa di probabilità lontano dall'esperto. Il risultato è una miscela in cui alcuni componenti sono peggiori di altri - su un braccio fisico, un controllore che può campionare un cattivo componente a metà movimento. Questa è la motivazione dichiarata per volere una policy stazionaria deterministica invece.

DAgger: un'idea, una scatola

Dataset Aggregation mantiene la policy deterministica e sposta la correzione nella raccolta dati. Ogni round: esegui la policy attuale, registra gli stati che visita, chiedi all'esperto quale sarebbe stata l'azione corretta in ognuno, aggiungi quelle coppie al dataset che hai già, riadatta l'unione. Il nome è l'algoritmo - aggreghi, non scardi mai.

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

Tre dettagli hanno più peso di quanto sembrino. Le etichette sono per gli stati visitati dalla policy mista, ma le azioni provengono dall'esperto - la policy fornisce le domande, l'esperto le risposte. L'riadattamento è sull'aggregato intero, che fa di ogni round un passo Follow-The-Leader: al round n scegli la migliore policy in retrospettiva su ogni traiettoria finora. Questo è il framing su cui si basa la prova. E l'algoritmo finisce restituendo la migliore policy nella sequenza scelta su un set di validazione, perché i teoremi garantiscono che qualche policy nella sequenza è buona, non che l'ultima lo sia.

Il beta schedule, e perché non è un manopola di sintonizzazione

La policy mista è beta_i volte l'esperto più uno meno beta_i volte l'apprendente. Il punto è pratico: le prime policy apprese sono addestrate su molto pochi dati, commettono molti errori, e altrimenti passerebbero il rollout in stati che diventano irrilevanti una volta che la policy migliora.

La teoria impone esattamente una condizione: la media mobile dei beta deve andare a zero. L'analisi funziona con beta_i limitato da (1 - alpha) alla potenza i-1, per una costante alpha indipendente da T.

Il divario tra 2980 e 3030 su una scala che arriva a circa 4300 è piccolo, ma la spiegazione del paper è la nota pratica più utile della sezione. Con lo schedule senza parametri, Mario è rimasto bloccato nello stesso punto all'inizio e ha generato una massa di dati quasi duplicati da quella sola posizione; lasciare che l'esperto guidi una frazione del tempo sia lo ha sbloccato che ha ampliato la varietà di stati. Lo schedule riguarda meno il rapporto di miscelazione che se la raccolta dati continua a produrre nuovi stati o lo stesso fallimento.

La garanzia: una riduzione all'apprendimento online senza rammarico

Ecco la mossa che rende il paper quello che è. Tratta ogni round DAgger come un esempio in un problema di apprendimento online, dove la loss al round i è la loss sostitutiva sotto la distribuzione di stato della policy utilizzata al round i. L'apprendente si impegna a una policy prima di vedere quella loss, e la sequenza è non-stazionaria perché dipende dalle policy prodotte finora.

Un algoritmo è senza rammarico se la sua loss media su N round si avvicina a quella della migliore singola policy in retrospettiva. Follow-The-Leader su loss fortemente convesse è tale algoritmo, con rammarico medio che si restringe dell'ordine di 1/N - e l'riadattamento sull'aggregato completo è precisamente Follow-The-Leader. Qualsiasi altro learner senza rammarico servirebbe altrettanto bene: l'analisi è una riduzione, non una proprietà di un solo ottimizzatore.

Un lemma colma il divario tra la policy mista che ha raccolto i dati e la policy appresa che verrà implementata: Lemma 4.1 limita la distanza L1 tra le loro distribuzioni di stato da 2 T beta_i. Questo è il motivo per cui i beta devono decadere - mentre l'esperto detiene ancora un'autorità di controllo apprezzabile, gli stati che raccogli non sono gli stati che la tua policy produrrà. Combina il lemma con il limite di rammarico e il risultato principale segue: dopo circa T iterazioni, qualche policy nella sequenza ha loss sostitutiva sotto la sua propria distribuzione dentro O(1/T) di epsilon_N. Inseriscilo nel limite lineare e arrivi al Teorema 3.2.

Il lato empirico è modesto secondo gli standard attuali. In Super Tux Kart la baseline supervisionata non ha migliorato le sue cadute medie per giro mentre arrivavano più dati, DAgger ha raggiunto una policy che non è mai caduta dalla pista dopo quindici iterazioni, e SMILe dopo venti è ancora caduta circa due volte per giro. Nel benchmark della scrittura a mano, l'accuratezza dei caratteri era 82 percento senza struttura, 83,6 percento supervisionato, 85,5 percento con DAgger. Nessuno di questi è un risultato di manipolazione.

Cosa la prova non promette

Gli enunciati dei teoremi sono condizionali, e le condizioni portano il peso.

Un ulteriore risultato è spesso citato come una confutazione e non lo è. Rajaraman, Yang, Jiao e Ramachandran studiano i limiti minimax dell'imitation learning in MDP episodici con uno spazio di stato finito S e orizzonte H, e provano un limite di sottoottimalità minimax dell'ordine di |S| H al quadrato su N che vale anche quando l'apprendente può interrogare attivamente l'esperto negli stati visitati. Questo è un tasso worst-case su una classe di MDP a un budget di episodio fisso, e quello che esclude è l'idea che l'interazione migliori il tasso minimax; il teorema di DAgger è un'affermazione diversa, che limita la policy implementata rispetto a quello che la sua stessa classe di policy può raggiungere.

Swamy, Choudhury, Bagnell e Wu hanno successivamente classificato questi algoritmi per quali momenti del comportamento dell'esperto corrispondono, e hanno introdotto una nozione di recuperabilità del momento che delinea quanto bene ogni famiglia mitiga l'errore composito. I sondaggi di Osa e di Celemin coprono il paesaggio algoritmico e le interfacce di feedback umano.

Il conto: etichettare gli stati che l'esperto non ha mai prodotto

Tutto quanto sopra assume un esperto che può essere interrogato ovunque. In simulazione con un planner quasi gratuito - gli esperimenti Mario hanno usato un planner quasi ottimale con accesso completo allo stato del gioco. Con un umano su un robot è il costo dominante, e uno peculiare: l'umano deve produrre un'azione corretta in una configurazione che la sua stessa competenza non avrebbe mai creato.

Kelly, Sidrane, Driggs-Campbell e Kochenderfer dichiarano l'obiezione direttamente nel paper HG-DAgger. Vanilla DAgger richiede all'esperto di fornire etichette di azione mentre non è pienamente in controllo del sistema. Questo riduce la sicurezza, e con esperti umani è probabile che degradi la qualità delle etichette raccolte, che attribuiscono al ritardo dell'attuatore percepito. L'etichetta che recuperi non è l'etichetta che l'algoritmo ha assunto.

Laskey e colleghi attaccano il problema dall'altro lato con DART, e il loro framing è diretto: le tecniche on-policy sono noiose per i supervisori umani, aggiungono carico computazionale, e possono visitare stati pericolosi durante l'addestramento. La loro alternativa inietta rumore calibrato nelle proprie dimostrazioni del supervisore, così il recupero viene dimostrato senza che il robot esegua mai una policy non attendibile. Su MuJoCo Humanoid segnalano che DART riduce il premio cumulativo del supervisore del 5 percento durante l'addestramento, mentre DAgger esegue policy con l'80 percento di premio cumulativo inferiore al supervisore; su presa in disordine con un Toyota HSR, un aumento medio del 62 percento su behavior cloning.

SafeDAgger di Zhang e Cho tratta le query alla policy di riferimento come la risorsa scarsa: una policy di sicurezza separata predice, senza interrogare, se la policy primaria sta per deviare dalla referenza oltre una soglia, e solo quegli stati vengono consegnati. Tutti e tre reagiscono allo stesso fatto - l'analisi DAgger non addebita nulla per le etichette dell'esperto, e la realtà addebita molto.

Cosa significa questo per un SO-100 sulla tua scrivania

Traduci l'orizzonte nelle tue unità. Un episodio di venti secondi a 30 frame al secondo è 600 step decisionali, e T in ogni limite sopra è quel numero. A T = 600, la differenza tra un termine che scala con T e uno che scala con T al quadrato è la differenza tra una policy che si recupera da un cattivo approccio e una che non lo fa.

Questo è parte del motivo per cui l'action chunking aiuta: quando una policy emette una breve sequenza di azioni per step di inferenza, il numero di punti decisionali diminuisce, così come il numero di opportunità di comporsi. Zhao, Kumar, Levine e Finn nominano l'errore composito come la motivazione per Action Chunking with Transformers, e segnalano 80 a 90 percento di successo su sei compiti reali difficili, su hardware bimanuale a basso costo, da dieci minuti di dimostrazione. Chunking non rimuove covariate shift - gli stati sono ancora quelli della policy - ma accorcia l'orizzonte effettivo. Vedi action chunking e la SO-100 imitation learning guide.

La seconda traduzione è la metrica di progresso. Non puoi misurare epsilon sotto la distribuzione della policy stessa direttamente - ciò richiede azioni dell'esperto di ground-truth per ogni stato visitato, la cosa che stai cercando di evitare di produrre. Quello che un loop controllato dall'umano ti dà invece è il tasso di intervento: la frazione di frame in una corsa durante i quali l'umano aveva preso il controllo. È un proxy, e si muove per motivi non correlati alla policy - un operatore paziente interviene meno. Usato coerentemente, è l'unico numero che dice se un round era degno del pomeriggio.

Una terza traduzione è un avviso di qualità dei dati che l'analisi non copre. Mandlekar e colleghi hanno studiato sei algoritmi di apprendimento offline su cinque compiti di manipolazione multi-stadio simulati e tre reali, e segnalano una sensibilità alle scelte di progettazione algoritmiche, una dipendenza dalla qualità delle dimostrazioni, e variabilità causata dal criterio di arresto. Belkhale, Cui e Sadigh sostengono che la qualità del dataset dovrebbe essere formalizzata attraverso la divergenza di azione e la diversità di transizione, e notano che la diversità di stato non è sempre vantaggiosa. Un round DAgger aggiunge stati che nessuno ha scelto deliberatamente: alcuni sono i dati di recupero di cui hai bisogno, alcuni sono il robot che agita mentre frughi il controllo di presa.

Meccanicamente un round è sei step: esegui l'inferenza con la registrazione attiva, prendi il controllo quando la policy si comporta male, rivedi la corsa e archivia ogni episodio, sincronizza le correzioni, componi un dataset misto da originali più correzioni con la selezione di episodio fatta esplicitamente per fonte, e continua l'addestramento dal precedente checkpoint piuttosto che dal modello di base. Su ay-robots questi step esistono come pulsanti, che rimuove l'impianto idraulico ma non il giudizio. Due avvertenze: continuare da un checkpoint inizializza i pesi e non è una ripresa dell'ottimizzatore, e la mossa di allineamento del braccio leader è ancora leggermente testata su hardware. Vedi training e datasets.

L'albero genealogico, in una tabella

Domande frequenti

Dove andare da qui

Se non hai ancora addestrato una policy, questa teoria è prematura: registra un dataset prima, a partire da addestramento della tua prima policy e il client da tavolo. Se stai soppesando un'altra centinaio di dimostrazioni pulite contro l'inizio delle correzioni: le dimostrazioni pulite non risolvono un problema di distribuzione. Per la meccanica, continua con la variante controllata dall'umano e poi la procedura SO-100.