DAgger forklaret: Hvorfor Behavior Cloning Mistes og Hvad Dataset Aggregation Faktisk Beviser

Der er en bestemt fejl, som alle, der træner en manipulationspolicy, møder før eller senere. Policyen når efter kuben, kommer inden for to centimeter, nøler, glider sidelens og gør derefter noget uden tilknytning til opgaven. Valideringsfejl var fin. Open-loop-gengivelse mod tilbageholdte episoder var fin. Og alligevel ender armen i en position, der ikke forekommer nogen steder i træningsdataene, og derfra har den intet fornuftigt at sige.

Den fejl har et navn og en etableret teori bag sig. Dette er det første af fire artikler om DAgger, og den dækker argumentet selv: hvorfor tilpasningen af en policy på demonstrantens egne baner producerer en fejl, der kan vokse med kvadratet af episodelængden, hvad dataset-aggregation ændrer, og hvad no-regret-beviset ikke lover. Løkken på rigtig hardware er dækket i kørsel af en DAgger-løkke på en SO-100, den menneskelig-gated variant i HG-DAgger og menneskelig-gated interventioner, og målespørgsmålet i måling af en DAgger-løkke.

Den antagelse, som behavior cloning stille gør

Et demonstrationsdatasæt er en bunke observation-handling-par. Behavior cloning tilpasser en funktion til denne bunke med almindelig overvåget læring og stopper der. Det er den ældste idé inden for området. Pomerleau's ALVINN fra 1988 var et trelagigt back-propagation-netværk, der tog billeder fra et kamera og en laser-afstandsmåler og producerede den retning, køretøjet skulle køre; det blev trænet på simulerede vejbilleder og fulgte rigtige veje under nogle feltbetingelser. Recepten har ikke ændret sig meget; netværkene har.

Hvad der bliver sprunget over er en kontrol af, hvor disse par kommer fra. Hver eneste af dem ligger på en bane, som demonstranten producerede. Den policy, du implementerer, producerer sin egen. I det øjeblik den afviger, bliver den spurgt om tilstande, der ikke var i træningsfordelingen, og dens svar flytter den længere ud. Ross, Gordon og Bagnell åbner DAgger-papiret med præcis dette: sekventiel prediktion overtræder den i.i.d.-antagelse under statistisk læring, fordi lærerens egne prædikeringer bestemmer de input, den ser efter.

Den klareste illustration i papiret er slet ikke en robot. Kloning af en næsten optimal planlægger for Super Mario Bros. producerede en policy, der gentagne gange blev fanget mod en hindring i stedet for at hoppe den. Grunden er hele argumentet i en sætning: eksperten hoppede altid fra en behagelig afstand, så datasættet indeholdt ingen tilstand, hvor Mario blev presset op mod en hindring, og derfor ingen etiket for, hvad man skulle gøre, når han var det.

Udskift Mario med en SO-100 arm og strukturen er identisk. Dine demonstrationer viser en ren tilgang og et rent greb, ikke griberen, der lukker to centimeter for kort - så policyen har ingen idé om, hvad man skal gøre derfra, og hvad den end gætter, tager den længere ud. Covariate shift er en egenskab ved data collection procedure, ikke af netværksarkitekturen.

Hvor det kvadratiske led kommer fra

2010 AISTATS-papiret af Ross og Bagnell, Efficient Reductions for Imitation Learning, gør sammensætningen præcis. Lad T være oppgavehorisonten, lad opgaveomkostninger være afgrænset i enheds-intervallet, og lad epsilon være surrogatfejlen målt under ekspertens tilstandsfordeling - tallet som dit valideringssæt rapporterer. Så ekstraomkostningerne ved at køre den policy i T trin i forhold til eksperten er afgrænset af T i anden gange epsilon. Ross, Gordon og Bagnell omtaler dette som sætning 2.1 i DAgger-papiret og tilføjer den sætning, der betyder noget: grænsen er stram. Der findes problemer, hvor en policy med epsilon-tab på ekspertens fordeling virkelig pådrager sig ekstraomkostninger, der vokser kvadratisk i T.

Stram betyder ikke typisk. Det kvadratiske led er et worst case over en klasse af problemer, ikke en forudsigelse om din pick-and-place opgave. Hvad det etablerer er, at mere ekspertdemonstration ikke kan fjerne problemet: det skærper kun estimatet af epsilon på en fordeling, som policyen ikke vil blive testet på.

Flugtvejen er i samme papir, omtalt som sætning 2.2. Hvis en policy opnår tab epsilon under sin egen tilstandsfordeling, og en enkelt forkert handling koster højst u i cost-to-go under eksperten, er ekstraomkostningerne afgrænset af u gange T gange epsilon - lineær i horisonten. Konstanten u er den interessante størrelse: højst 1 for 0-1 uenighed med eksperten, og O(1) når som helst, når eksperten kan komme sig inden for nogle få trin. I værste fald er det O(T), og den lineære grænse er så ikke bedre end den kvadratiske.

De to forsøg før DAgger

Forward training er det ærlige men upraktisk svar. Træn en separat policy for hvert tidstrin i rækkefølge, hver på tilstandsfordelingen induceret af de politikker, der allerede er fastsat for tidligere trin, så hver policy ser præcis den fordeling, den vil møde. Fangsten er i beskrivelsen: T-politikker trænet sekventielt uden tidlig standsning. For en manipulations episode ved 30 billeder pr. sekund er T i hundredtals.

SMILe fra samme papir, og SEARN fra Daume, Langford og Marcu's arbejde med struktureret forudsigelse, tager den anden rute: én stationær policy, men stokastisk. Hver iteration træner en komponent og tilføjer den til en blanding, der skubber sandsynlighedsmassen væk fra eksperten. Resultatet er en blanding, hvor nogle komponenter er værre end andre - på en fysisk arm en controller, der kan sample en dårlig komponent under bevægelse. Det er den angivne motivation for at ville en stationær deterministisk policy i stedet.

DAgger: en idé, en boks

Dataset Aggregation bevarer den deterministiske policy og flytter rettelsen ind i dataindsamlingen. Hver runde: kør den aktuelle policy, registrer de tilstande, den besøger, spørg eksperten, hvad den korrekte handling ville være i hver, tilføj disse par til det datasæt, du allerede har, træn om på foreningen. Navnet er algoritmen - du aggregerer, du kasserer aldrig.

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 vejer mere, end de ser ud til at gøre. Etiketterne er for tilstande, der besøges af den blandet policy, men handlingerne kommer fra eksperten - policyen giver spørgsmålene, eksperten svarene. Omtræningen er på hele aggregatet, hvilket gør hver runde til et Follow-The-Leader-trin: på runde n vælger du den bedste policy i bagklogskab over hver bane til nu. Den framing er det, beviset hænger på. Og algoritmen slutter ved at returnere den bedste policy i sekvensen som valgt på et valideringssæt, fordi sætningerne garanterer, at nogle policy i sekvensen er god, ikke at den sidste er.

Beta schedule og hvorfor det ikke er en tunings-knap

Den blandet policy er beta_i gange eksperten plus en minus beta_i gange læreren. Pointen er praktisk: de første få lærte politikker trænes på meget lidt data, laver mange fejl, og ville ellers bruge rollout'en i tilstande, der bliver irrelevante, når policyen forbedres.

Teorien påtvinger præcis en betingelse: det løbende gennemsnit af betaerne skal gå til nul. Analysen virker med beta_i afgrænset af (1 - alpha) til magten i-1, for en konstant alpha uafhængig af T.

Gabet mellem 2980 og 3030 på en skala, der løber til cirka 4300, er småt, men paperets forklaring af det er den mest brugbare praktiske note i sektionen. Med den parameterløse tidsplan blev Mario fanget på samme sted tidligt og genererede en masse næsten-duplikat data fra den ene placering; at lade eksperten køre en brøkdel af tiden både befriede ham og udvidede variationen af tilstande. Tidsplanen handler mindre om blandingsforholdet end om, hvorvidt din dataindsamling fortsætter med at producere nye tilstande eller den samme fejl.

Garantien: en reduktion til no-regret online learning

Her er det træk, der gør papiret til det, det er. Behandl hver DAgger-runde som et eksempel i et online learning-problem, hvor tabet på runde i er surrogatfejlen under tilstandsfordelingen af den policy, der bruges på runde i. Læreren forpligter sig til en policy, før den ser det tab, og sekvensen er ikke-stationær, fordi den afhænger af de politikker, der er produceret til nu.

En algoritme er no-regret, hvis dens gennemsnitlige tab over N runder nærmer sig det af den bedste single policy i bagklogskab. Follow-The-Leader på stærkt konvekse tab er sådan en algoritme, med gennemsnits-regret, der krymper på størrelse omkring 1/N - og omtrænning på hele aggregatet er præcist Follow-The-Leader. Enhver anden no-regret learner ville virke lige så godt: analysen er en reduktion, ikke en egenskab for en optimizer.

Et lemma bygger broen mellem den blandet policy, der indsamlede dataene, og den lærte policy, der skal implementeres: Lemma 4.1 afgrænser L1-afstanden mellem deres tilstandsfordelinger med 2 T beta_i. Dette er grunden til, at betaerne skal forfalde - mens eksperten stadig har væsentlig kontrolmyndighed, er de tilstande, du indsamler, ikke de tilstande, din policy vil producere. Kombiner lemmaet med regret-grænsen, og hovedresultatet følger: efter cirka T iterationer har nogle policy i sekvensen surrogatfejl under sin egen fordeling inden for O(1/T) af epsilon_N. Føder det ind i den lineære grænse, og du lander på sætning 3.2.

Den empiriske side er beskeden efter nuværende standarder. I Super Tux Kart forbedrede den overvågede baseline ikke sit gennemsnitlige fald pr. omgang, da mere data ankom, DAgger nåede en policy, der aldrig faldt af banen efter femten iterationer, og SMILe efter tyve faldt stadig cirka to gange pr. omgang. På benchmark'et for håndskrift løb karakternøjagtighed 82 procent uden struktur, 83,6 procent overvåget, 85,5 procent med DAgger. Ingen af disse er et manipulationsresultat.

Hvad beviset ikke lover

Sætningsudtrykkene er betinget, og betingelserne er byrdebare.

Et yderligere resultat bliver ofte citeret som en tilbagevisning og er det ikke. Rajaraman, Yang, Jiao og Ramachandran studerer de minimax-grænser for imitation learning i episodiske MDP'er med et endeligt tilstandsrum S og horisont H, og beviser en suboptimalitetsgrænse på størrelse omkring |S| H i anden over N, der gælder selv når læreren aktivt kan spørge eksperten ved besøgte tilstande. Det er en worst-case-rate over en klasse af MDP'er ved et fast episode-budget, og hvad det udelukker, er ideen om, at interaktion forbedrer minimax-satsen; DAgger's sætning er en anden udsagn, der afgrænser den implementerede policy i forhold til hvad dens egen policy-klasse kan opnå.

Swamy, Choudhury, Bagnell og Wu klassificerede senere disse algoritmer efter hvilke øjeblikke af ekspertens adfærd de matcher, og introducerede en forestilling om moment genoprettelse, der afgrænser hvor godt hver familie formidler sammensætningsfejl. Undersøgelserne af Osa og Celemin dækker det algoritmiske landskab og grænsefladerne for menneskelig feedback.

Regningen: mærkning af tilstande, som eksperten aldrig producerede

Alt ovenfor forudsætter en ekspert, der kan blive spurgt hvor som helst. I simulation med en planlægger, der næsten er gratis - Mario-eksperimenterne brugte en næsten optimal planlægger med fuld adgang til spiltilstand. Med et menneske på en robot er det den dominerende omkostning og en ejendommelig: mennesket skal producere en korrekt handling i en konfiguration, som deres egen kompetence aldrig ville have skabt.

Kelly, Sidrane, Driggs-Campbell og Kochenderfer angiver indvendingen direkte i HG-DAgger-papiret. Vanilla DAgger kræver, at eksperten leverer handlings-etiketter, mens han ikke er fuldstændigt i kontrol over systemet. Dette reducerer sikkerheden og med menneskelige eksperter vil det sandsynligvis forringe kvaliteten af de indsamlede etiketter, som de tilskriver til opfattet aktuator-lag. Etiketten, du får tilbage, er ikke den etiket, som algoritmen antog.

Laskey og kolleger angriber problemet fra den anden side med DART, og deres framing er direkte: on-policy teknikker er kedelige for menneskelige supervisorer, tilføjer computerbelastning og kan besøge farlige tilstande under træning. Deres alternativ sprøjter kalibreret støj ind i supervisorens egne demonstrationer, så gendannelse bliver demonstreret uden at roboten kører nogen upålidelig policy. På MuJoCo Humanoid rapporterer de DART reducerer supervisorens kumulative belønning med 5 procent under træning, mens DAgger udfører politikker med 80 procent mindre kumulativ belønning end supervisoren; på grebning i belemring med en Toyota HSR en gennemsnitlig 62-procent stigning over behavior cloning.

Zhang og Cho's SafeDAgger behandler forespørgsler til referencepolicyen som den knappe ressource: en separat sikkerhedspolicy forudsiger uden at forespørge, hvorvidt hovedpolicyen er ved at afvige fra referencen ud over en tærskel, og kun disse tilstande overleveres. Alle tre reagerer på det samme faktum - DAgger-analysen beregner intet for ekspertetiketter, og virkelighed beregner meget.

Hvad det betyder for en SO-100 på dit skrivebord

Oversæt horisonten til dine egne enheder. En tyvesekunders episode ved 30 billeder pr. sekund er 600 beslutningsskridt, og T i hver grænse ovenfor er det tal. Ved T = 600 er forskellen mellem et led, der skaleres med T og et, der skaleres med T i anden, forskellen mellem en policy, der kommer sig fra en dårlig tilgang og en, der ikke gør.

Dette er en del af grunden til, at handling chunking hjælper: når en policy udsender en kort sekvens af handlinger pr. inferenstrin, falder antallet af beslutningspunkter, og så gør antallet af chancer for at sammensætte. Zhao, Kumar, Levine og Finn nævner sammensætningsfejl som motivationen for Action Chunking with Transformers, og rapporterer 80 til 90 procent succes på seks vanskelige real-world-opgaver, på billig bimanuel hardware, fra ti minutter værd af demonstrationer. Chunking fjerner ikke covariate shift - tilstandene er stadig policyen selv - men den forkorter den effektive horisont. Se action chunking og SO-100 imitation learning guide.

Den anden oversættelse er progressionsmålet. Du kan ikke måle epsilon under policyen's egen fordeling direkte - det kræver grund-sandhedsekspert-handlinger for hver besøgt tilstand, det ting du forsøger at undgå at producere. Hvad en menneskelig-gated løkke giver dig i stedet, er interventionsraten: brøkdelen af billeder i en kørsel, hvor mennesket havde overtaget. Det er en proxy, og den bevæger sig af grunde uden tilknytning til policyen - en tålmodig operatør griber ind mindre. Brugt konsistent er det det ene tal, der siger, om en runde var værd eftermiddagen.

En tredje oversættelse er en data-kvalitets-advarsel, som analysen ikke dækker. Mandlekar og kolleger studerede seks offline learning-algoritmer på fem simulerede og tre real-world multi-stage manipulationsopgaver, og rapporterer en følsomhed over for algoritmiske designvalg, en afhængighed af kvaliteten af demonstrationerne og variabilitet forårsaget af stoppekriterierne. Belkhale, Cui og Sadigh argumenterer for, at datasæt-kvalitet bør formaliseres gennem handlingsafvigelse og transitions-mangfoldighed, og bemærker, at tilstand-mangfoldighed ikke altid er gavnlig. En DAgger-runde tilføjer tilstande, som ingen valgte bevidst: nogle er de gendannelse-data, du har brug for, nogle er roboten, der flakker, mens du famler efter overtag-kontrollen.

Mekanisk er en runde seks trin: kør inferens med registrering på, overtag, når policyen misbehaver, gennemgå kørslen og file hver episode, synkroniser korrektionerne, sammensæt et blandet datasæt fra originaler plus korrektioner med episode-valg foretaget eksplicit per kilde, og fortsæt træning fra det tidligere checkpoint snarere end base-modellen. På ay-robots eksisterer disse trin som knapper, hvilket fjerner rørlæggeriet men ikke skellet. To forbehold: fortsætter fra et checkpoint initialiserer vægte og er ikke en optimizer-genoptagelse, og leader-arm-justeringsbevægelsen er stadig let testet på hardware. Se training og datasets.

Familiestamtræet i en tabel

Hyppigt stillede spørgsmål

Hvor skal man gå herfra

Hvis du ikke har trænet en policy endnu, er denne teori for tidlig: registrer først et datasæt, der starter fra træning af din første policy og desktop klient. Hvis du vejer endnu hundrede rene demonstrationer mod at starte korrektioner: rene demonstrationer løser ikke et distributions-problem. For mekanikken, fortsæt med menneskelig-gated varianten og så SO-100 gennemgang.