DAgger Förklarat: Varför Behavior Cloning Driftar och Vad Dataset Aggregation Faktiskt Bevisar

Det finns ett specifikt misslyckande som alla som tränar en manipulationspolicy stöter på förr eller senare. Policyn sträcker sig efter kuben, kommer inom två centimeter, tveka, driftar åt sidan, gör sedan något orelaterat till uppgiften. Valideringsmisslyckning var bra. Open-loop-uppspelning mot reserverade episoder var bra. Och ändå hamnar armen i en pose som inte förekommer någonstans i träningsdata, och därifrån har den ingenting vettigt att säga.

Det misslyckandet har ett namn och ett etablerat teoriavsnitt bakom sig. Det här är det första av fyra artiklar om DAgger, och det täcker själva argumentet: varför anpassning av en policy på demonstrantens egna banor producerar ett fel som kan växa med kvadraten på episodlängden, vad dataset aggregation ändrar, och vad no-regret-beviset inte lovar. Loopen på verklig hårdvara täcks i köra en DAgger-loop på en SO-100, den människostyrda varianten i HG-DAgger och människostyrda interventioner, och mätfrågan i mäta en DAgger-loop.

Det antagande behaviour cloning gör i tystnad

En demonstrationsdataset är en hög observationsåtgärdpar. Behavior cloning anpassar en funktion till den högen med vanlig övervakad inlärning och slutar där. Det är den äldsta idén på området. Pomerleau's ALVINN, 1988, var ett tre-lager backpropagation-nätverk som tog bilder från en kamera och en laserskanning och producerade den riktning fordonet skulle färdas; den tränade på simulerade vägar och följde verkliga vägar under vissa fältförhållanden. Receptet har inte förändrats mycket; nätverken har.

Vad som hoppas över är en kontroll på var dessa par kom från. Varje par ligger på en bana som demonstranten producerade. Den policy du distribuerar producerar sin egen. I det ögonblick den avviker är den att frågad om tillstånd som inte fanns i träningsfördelningen, och dess svar flyttar den längre ut. Ross, Gordon och Bagnell öppnar DAgger-papperet med exakt detta: sekventiell förutsägelse bryter mot i.i.d-antagandet under statistisk inlärning, eftersom lärarens egna förutsägelser bestämmer ingångarna den ser härnäst.

Den tydligaste illustrationen i det papperet är inte en robot alls. Att klona en nästan optimal planerare för Super Mario Bros. producerade en policy som upprepade gånger fastnade mot ett hinder i stället för att hoppa över det. Anledningen är hela argumentet på en mening: experten hoppade alltid från ett bekvämt avstånd, så datasetet innehöll inget tillstånd där Mario var pressad mot ett hinder, och därför ingen etikett för vad man gör när han är.

Byt Mario mot en SO-100 arm och strukturen är identisk. Dina demonstrationer visar ett renare tillvagahållande och ett renas grepp, inte griparen som stängs två centimeter kort - så policyn har ingen aning om vad man gör därifrån, och vad det än gissar tar det längre ut. Covariate shift är en egenskap hos datainsamlingsproceduren, inte av arkitekturen i nätverket.

Var den kvadratiska termen kommer från

2010 AISTATS-papperet av Ross och Bagnell, Efficient Reductions for Imitation Learning, gör sammansättningen exakt. Låt T vara aktivitetshorisonten, låt aktivitetskostnad vara begränsad i enhetsintervallet, och låt epsilon vara den ersättande förlusten uppmätt under expertens tillståndsfördelning - numret din valideringsuppsättning rapporterar. Då är den extra kostnaden för att köra den policyn för T steg, i förhållande till experten, begränsad av T i kvadrat gånger epsilon. Ross, Gordon och Bagnell omformulerar detta som Theorem 2.1 i DAgger-papperet och lägger till meningen som spelar någon roll: gränsen är åt. Problem finns där en policy med epsilon-förlust på expertens fördelning verkligen ådrar sig extra kostnad som växer kvadratiskt i T.

Åt betyder inte typiskt. Den kvadratiska termen är ett värsta fall över en klass av problem, inte en förutsägelse om ditt pick-and-place-uppdrag. Vad den etablerar är att mer expertdemonstration inte kan ta bort problemet: det bara skärper uppskattningen av epsilon på en fördelning som policyn inte kommer att testas på.

Flyktvärgen är i samma papper, omformulerat som Theorem 2.2. Om en policy uppnår epsilon-förlust under sin egen tillståndsfördelning, och en enda felaktig åtgärd kostar maximalt u i kostnad-till-gå under experten, är den extra kostnaden begränsad av u gånger T gånger epsilon - linjär i horisonten. Konstanten u är den intressanta mängden: högst 1 för 0-1 oenighet med experten, och O(1) när experten kan återhämta sig inom några steg. I värsta fall är den O(T), och den linjära gränsen är då inte bättre än den kvadratiska.

De två försöken innan DAgger

Forward training är det ärliga men opraktiska svaret. Träna en separat policy för varje tidssteg, i ordning, var och en på tillståndsfördelningen som induceras av de policyer som redan är fixerade för tidigare steg, så att varje policy ser exakt den fördelning den kommer att möta. Fångsten ligger i beskrivningen: T-policyer, tränade sekventiellt, ingen tidig stopp. För en manipulations episode vid 30 bilder per sekund är T i hundratalen.

SMILe, från samma papper, och SEARN, från Daumé, Langford och Marcus arbete med strukturerad förutsägelse, tar den andra vägen: en stationär policy, men stokastisk. Varje iteration tränar en komponent och lägger den till en blandning, förskjuter sannolikhetsmassa bort från experten. Resultatet är en blandning där vissa komponenter är värre än andra - på en fysisk arm, en regulator som kan sampla en dålig komponent under rörelse. Det är det angivna motivet för att vilja ha en stationär deterministisk policy i stället.

DAgger: en idé, en låda

Dataset Aggregation håller kvar den deterministiska policyn och flyttar fixeringen in i datainsamlingen. Varje runda: rulla ut den aktuella policyn, spela in de tillstånd den besöker, fråga experten vad den korrekta åtgärden skulle ha varit i var och en, lägg till dessa par till datasetet du redan har, träna om på unionen. Namnet är algoritmen - du aggregerar, du kastar aldrig bort.

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 detaljer väger mer än de ser ut som. Etiketterna är för tillstånd som besöks av den blandade policyn, men åtgärderna kommer från experten - policyn tillhandahåller frågorna, experten svaren. Omträningen är på hela aggregatet, vilket gör varje runda till ett Follow-The-Leader-steg: vid runda n väljer du den bästa policyn i retrospektiv över varje bana hittills. Den framing är vad beviset hänga på. Och algoritmen slutar genom att returnera den bästa policyn i sekvensen enligt valt på en valideringsuppsättning, eftersom satserna garanterar att någon policy i sekvensen är bra, inte att den sista är.

Beta-schemat, och varför det inte är en trimknapp

Den blandade policyn är beta_i gånger experten plus ett minus beta_i gånger läraren. Poängen är praktisk: de första få inlärda policyer tränas på väldigt lite data, gör många misstag, och skulle annars spendera rullen i tillstånd som blir irrelevanta när policyn förbättras.

Teorin lägger exakt en villkor: det löpande genomsnittet av betorna måste gå till noll. Analysen fungerar med beta_i begränsad av (1 - alpha) till potensen i-1, för en konstant alpha oberoende av T.

Gapet mellan 2980 och 3030 på en skala som löper upp till ungefär 4300 är litet, men papirets förklaring av det är den mest användbara praktiska noten i avsnittet. Med det parameterfria schemat fastnade Mario på samma plats tidigt och genererade en massa nästan-dubbel data från den ena platsen; att låta experten köra en bråkdel av tiden både lossade honom och utökade variationen av tillstånd. Schemat handlar mindre om blandningsförhållandet än om huruvida din datainsamling fortsätter att producera nya tillstånd eller samma misslyckande.

Garantin: en minskning till no-regret online-inlärning

Här är steget som gör papperet vad det är. Behandla varje DAgger-runda som ett exempel i ett online-inlärningsproblem, där förlusten vid runda i är den ersättande förlusten under tillståndsfördelningen för den policy som användes vid runda i. Läraren förbinder sig till en policy innan den ser den förlusten, och sekvensen är icke-stationär eftersom den beror på de policyer som producerats hittills.

En algoritm är no-regret om dess genomsnittliga förlust över N rundor närmar sig den för den enda bästa policyn i retrospektiv. Follow-The-Leader på starkt konvexa förluster är sådan en algoritm, med genomsnittlig ångra som krymper på ordningen 1/N - och omträning på det fullständiga aggregatet är exakt Follow-The-Leader. Någon annan no-regret-lärare skulle fungera lika bra: analysen är en minskning, inte en egenskap hos en optimerare.

En lemma överbryggar gapet mellan den blandade policyn som samlade in data och den inlärda policyn som kommer att implementeras: Lemma 4.1 binder L1-avståndet mellan deras tillståndsfördelningar av 2 T beta_i. Det är därför betorna måste förfalla - medan experten fortfarande innehar väsentlig kontrolleautoritet är de tillstånd du samlar inte de tillstånd din policy kommer att producera. Kombinera lemman med ångerbunden och huvudresultatet följer: efter ungefär T iterationer har någon policy i sekvensen ersättande förlust under sin egen fördelning inom O(1/T) av epsilon_N. Mata det i den linjära gränsen och du landar på Theorem 3.2.

Den empiriska sidan är blygsam efter dagens standarder. I Super Tux Kart forbättrade den övervakade utgångspunkten inte sitt genomsnittliga fall per varv när mer data kom, DAgger nådde en policy som aldrig föll från spåret efter femton iterationer, och SMILe efter tjugo föll fortfarande ungefär två gånger per varv. På handskrift-benchmarken körde teckenprecisionen 82 procent utan struktur, 83,6 procent övervakad, 85,5 procent med DAgger. Inget av dessa är ett manipulationsresultat.

Vad beviset inte lovar

Satsangivelserna är villkorad, och villkoren är betydelsefulla.

Ett ytterligare resultat citeras ofta som en motfattning och är inte en. Rajaraman, Yang, Jiao och Ramachandran studerar minimax-gränserna för imitationsinlärning i episodiska MDPer med ett ändligt tillståndsrum S och horisont H, och bevisar en suboptimalitetslägre gräns på ordningen |S| H i kvadrat över N som gäller även när läraren kan aktivt fråga experten vid besökta tillstånd. Det är ett värsta fall över en klass av MDPer vid en fast episodbudget, och vad det utesluter är tanken att interaktion förbättrar minimax-hastigheten; DAggers teorem är ett annat uttalande, som binder den implementerade policyn relativt till vad sin egen policysklass kan uppnå.

Swamy, Choudhury, Bagnell och Wu klassificerade senare dessa algoritmer genom vilka ögonblick av expertens beteende de stämmer, och introducerade en uppfattning om momentåterhämtning som avgränsar hur väl varje familj minskar sammansatt fel. Undersökningarna av Osa och av Celemin täcker algoritmlandet och de människofeedback-gränssnitten.

Notan: märka tillstånd experten aldrig producerade

Allt ovan antar en expert som kan frågad överallt. I simulering med en planerare som nästan är fri - Mario-experimenten använde en nästan optimal planerare med full åtkomst till spelstillståndet. Med en människa på en robot är det den dominerande kostnaden, och en märklig sådan: människan måste producera en korrekt åtgärd i en konfiguration som deras egna kunskaper aldrig skulle ha skapat.

Kelly, Sidrane, Driggs-Campbell och Kochenderfer anger invändningen direkt i HG-DAgger-papperet. Vanilla DAgger kräver att experten tillhandahåller åtgärdsetiketter medan de inte är helt i kontroll över systemet. Detta minskar säkerheten, och med mänskliga experter är det sannolikt att försämra kvaliteten på de insamlade etiketterna, vilket de tillskriver uppfattad styrenhetsfördröjning. Etiketten du får tillbaka är inte etiketten algoritmen antog.

Laskey och kollegor attackerar problemet från den andra sidan med DART, och deras inramning är rakt: on-policy-tekniker är tråkiga för mänskliga handledare, lägger till beräkningsbörda, och kan besöka farliga tillstånd under träning. Deras alternativ injicerar kalibrerad brus i handledarens egna demonstrationer, så återhämtning demonstreras utan att roboten någonsin kör en opålitlig policy. På MuJoCo Humanoid rapporterar de DART minskar handledarens kumulativa belöning med 5 procent under träning, medan DAgger exekverar policyer med 80 procent mindre kumulativ belöning än handledaren; på grepphållning i rörelse med en Toyota HSR, ett genomsnitt på 62 procent ökning över behavior cloning.

Zhangs och Chos SafeDAgger behandlar frågor till referenspolicyn som den knappa resursen: en separat säkerhetspolicy förutsäger, utan att fråga, om den primära policyn är på väg att avvika från referensen bortom ett tröskelvärde, och endast dessa tillstånd överlämnas. Alla tre reagerar på samma faktum - DAgger-analysen debiterar ingenting för expertetikett, och verkligheten debiterar mycket.

Vad detta betyder för en SO-100 på ditt skrivbord

Översätt horisonten till dina egna enheter. En tjugo-sekunders-episod vid 30 bilder per sekund är 600 beslutssteg, och T i varje gräns ovan är det numret. Vid T = 600 är skillnaden mellan en term som skalerar med T och en som skalerar med T i kvadrat skillnaden mellan en policy som återhämtar sig från en dålig tillvagahållande och en som inte gör det.

Det här är en del av varför åtgärdsbuntning hjälper: när en policy emitterar en kort sekvens av åtgärder per slutledningssteg, sjunker antalet beslutspunkter, och så gör antalet chanser att sammansätta. Zhao, Kumar, Levine och Finn namnger sammansatt fel som motivationen för Action Chunking with Transformers, och rapporterar 80 till 90 procent framgång på sex svåra verklig-världen-uppgifter, på låg-kostnad tvåarmad hårdvara, från tio minuters värd av demonstrationer. Buntning tar inte bort covariate shift - tillstånden är fortfarande policyn själv - men det förkortar den effektiva horisonten. Se åtgärdsbuntning och SO-100 imitationsinlärningsguiden.

Den andra översättningen är framstegsmåttet. Du kan inte mäta epsilon under policyn egen fördelning direkt - det behöver ground-truth expertåtgärder för varje besökt tillstånd, det du försöker undvika att producera. Vad en människostyrning-slinga ger dig i stället är interventionsfrekvensen: bråkdelen av bildrutor i en körning under vilka människan hade tagit över. Det är en proxy, och den rör sig av orsaker orelaterade till policyn - en tålmodig operatör intervenerar mindre. Använd konsekvent är det det enda numret som säger om en runda var värd eftermiddagen.

En tredje översättning är en datakvalitetsvarning som analysen inte täcker. Mandlekar och kollegor studerade sex offline-inlärningsalgoritmer på fem simulerade och tre verklig-världen multi-steg-manipulationsuppgifter, och rapporterar en känslighet för algoritmiska designval, ett beroende av demonstrationskvaliteten, och variabilitet orsakad av stoppkriteriet. Belkhale, Cui och Sadigh argumenterar att datasetkvalitet bör formaliseras genom åtgärdsdivergence och övergångsdiversitet, och noterar att tillståndsdiversitet inte alltid är fördelaktig. En DAgger-runda lägger till tillstånd som ingen valde medvetet: vissa är återhämtningsdatan du behöver, vissa är roboten som fladdrar medan du famlar för takeover-kontrollen.

Mekaniskt är en runda sex steg: köra slutledning med inspelning på, ta över när policyn misstag, granska körningen och arkivera varje episod, synkronisera korrigeringarna, samla en blandad dataset från original plus korrigeringar med episodval gjord uttryckligt per källa, och fortsätta träning från föregående checkpoint snarare än basmodellen. På ay-robots finns dessa steg som knappar, vilket tar bort rörmunningen men inte bedömningen. Två varningar: fortsättning från en checkpoint initialiserar vikter och är inte en optimerare-återupptagning, och leader-arm-justeringsrörelsen är fortfarande lätt testad på hårdvara. Se träning och dataset.

Familjeträdet, i en tabell

Ofta ställda frågor

Vart man går härifrån

Om du inte har tränat en policy än är denna teori för tidig: spela in en dataset först, med början från träna din första policy och skrivbordsklienten. Om du väger en annan hundra rena demonstrationer mot att börja korrigeringar: rena demonstrationer fixar inte ett distribitionsproblem. För mekaniken, fortsätt med den människostyrda varianten och sedan SO-100-genomgången.