Ipinaliwanag ang DAgger: Bakit Lumilihis ang Behavior Cloning at Ano Talaga ang Pinatutunayan ng Dataset Aggregation

May isang tiyak na pagkabigo na mararanasan, maaga man o huli, ng sinumang nagsasanay ng manipulation policy. Aabot ang policy sa cube, malapit na lang - dalawang sentimetro - pero mag-aatubili ito, lilihis pasalungat, at gagawa ng isang bagay na wala namang kinalaman sa gawain. Maayos naman ang validation loss. Maayos din ang open-loop replay laban sa held-out episodes. Pero sa huli, natatapos ang braso sa isang pose na wala talagang lumalabas sa training data, at mula roon, wala na itong makatwirang masasabi.

May pangalan ang pagkabigong iyan at may matatag na teorya sa likod nito. Ito ang una sa apat na artikulo tungkol sa DAgger, at tinatalakay nito ang mismong argumento: bakit ang pag-fit ng policy sa mga trajectory mismo ng demonstrator ay nagdudulot ng error na maaaring lumaki ayon sa parisukat ng haba ng episode, ano ang binabago ng dataset aggregation, at ano ang hindi ipinapangako ng no-regret proof. Ang loop sa aktwal na hardware ay tinatalakay sa pagpapatakbo ng DAgger loop sa isang SO-100, ang human-gated variant naman sa HG-DAgger at human-gated interventions, at ang tanong tungkol sa pagsukat ay nasa pagsukat ng isang DAgger loop.

Ang palagay na tahimik na ginagawa ng behavior cloning

Ang isang demonstration dataset ay isang bunton ng observation-action pairs. Ang behavior cloning ay nag-a-angkop ng isang function sa buntong iyon gamit ang ordinaryong supervised learning at doon na humihinto. Ito ang pinakamatandang ideya sa larangan. Ang ALVINN ni Pomerleau, noong 1988, ay isang three-layer back-propagation network na kumukuha ng mga imahe mula sa isang camera at isang laser range finder at naglalabas ng direksyong dapat tahakin ng sasakyan; sinanay ito gamit ang mga simulated na imahe ng kalsada at nakasunod ito sa aktwal na kalsada sa ilang kondisyon sa field. Hindi gaanong nagbago ang recipe; ang mga network ang nagbago.

Ang nalalaktawan ay ang pagsusuri kung saan nanggaling ang mga pares na iyon. Bawat isa sa kanila ay nakasalalay sa isang trajectory na ginawa ng demonstrator. Ang policy na ipinapatakbo mo ay gumagawa ng sarili nitong trajectory. Sa sandaling lumihis ito, tinatanong na ito tungkol sa mga state na wala sa training distribution, at ang sagot nito ang siyang naglalayo pa rito. Binuksan nina Ross, Gordon, at Bagnell ang DAgger paper mismo sa puntong ito: lumalabag ang sequential prediction sa i.i.d. assumption na siyang saligan ng statistical learning, dahil ang mismong mga prediksyon ng learner ang nagtatakda kung anong input ang makikita nito sunod.

Ang pinakamalinaw na ilustrasyon sa papel na iyon ay hindi pala tungkol sa robot. Ang pag-clone ng isang near-optimal na planner para sa Super Mario Bros. ay nagbunga ng isang policy na paulit-ulit na natitigil laban sa isang balakid sa halip na lundagin ito. Ang dahilan ay ang buong argumento sa isang pangungusap: laging tumatalon ang expert mula sa isang komportableng distansya, kaya walang state sa dataset kung saan naka-diin si Mario laban sa isang balakid, at dahil dito, walang label kung ano ang gagawin kapag nasa ganoong sitwasyon na siya.

Palitan si Mario ng isang SO-100 na braso at magkatulad ang istruktura. Ipinapakita ng iyong mga demonstration ang isang malinis na paglapit at isang malinis na paghawak, hindi ang gripper na sumasara nang kulang ng dalawang sentimetro - kaya wala talagang alam ang policy kung ano ang gagawin mula roon, at anuman ang hulaan nito ay lalo lang nitong nilalayo ang sarili. Ang covariate shift ay isang katangian ng proseso ng pangongolekta ng data, hindi ng network architecture.

Saan nanggagaling ang quadratic term

Ang 2010 AISTATS paper nina Ross at Bagnell, Efficient Reductions for Imitation Learning, ang gumagawa sa compounding na maging eksakto. Ipagpalagay na si T ang task horizon, na nakatali ang task cost sa loob ng unit interval, at si epsilon ang surrogate loss na sinusukat sa ilalim ng state distribution ng expert - ang numerong iniuulat ng iyong validation set. Pagkatapos, ang dagdag na cost ng pagpapatakbo ng policy na iyon sa loob ng T na hakbang, kumpara sa expert, ay nakatali sa T squared na pinarami sa epsilon. Muling isinaad ito nina Ross, Gordon, at Bagnell bilang Theorem 2.1 sa DAgger paper, at idinagdag ang pangungusap na mahalaga: mahigpit ang bound. May mga problemang umiiral kung saan ang isang policy na may epsilon loss sa distribution ng expert ay talagang nagdudulot ng dagdag na cost na lumalaki nang quadratic sa T.

Ang tight ay hindi pareho ng typical. Ang quadratic term ay isang worst case sa isang klase ng mga problema, hindi isang hula tungkol sa iyong pick-and-place task. Ang naipapakita nito ay hindi maaalis ng mas maraming demonstration ng expert ang problema: pino-refine lang nito ang estimate ng epsilon sa isang distribution na hindi naman susubukan ang policy.

Ang solusyon ay nasa parehong papel, muling isinaad bilang Theorem 2.2. Kung ang isang policy ay may epsilon loss sa ilalim ng sarili nitong state distribution, at ang isang maling aksyon ay nagkakahalaga ng hanggang u sa cost-to-go sa ilalim ng expert, ang dagdag na cost ay nakatali sa u na pinarami sa T na pinarami sa epsilon - linear sa horizon. Ang constant na u ang kawili-wiling dami: hanggang 1 para sa 0-1 disagreement laban sa expert, at O(1) tuwing kayang mag-recover ng expert sa loob ng ilang hakbang lamang. Sa worst case ito ay O(T), kaya ang linear bound ay hindi na mas mainam kaysa sa quadratic.

Ang dalawang naunang pagtatangka bago ang DAgger

Ang forward training ang tapat pero hindi praktikal na sagot. Sanayin ang hiwalay na policy para sa bawat timestep, nang sunud-sunod, bawat isa ay batay sa state distribution na dulot ng mga policy na naitakda na sa mga naunang hakbang, kaya ang bawat policy ay nakikita eksakto ang distribution na haharapin nito. Ang bitag ay nasa mismong deskripsyon: T na policy, sinanay nang sunud-sunod, walang early stopping. Para sa isang manipulation episode sa 30 frames per second, ang T ay nasa daan-daan.

Ang SMILe, mula sa parehong papel, at ang SEARN, mula sa gawa nina Daume, Langford, at Marcu tungkol sa structured prediction, ay kumukuha ng ibang ruta: isang stationary na policy, pero stochastic. Sinasanay ng bawat iteration ang isang component at idinaragdag ito sa isang mixture, inililipat ang probability mass palayo sa expert. Ang resulta ay isang mixture kung saan ang ilang component ay mas masama kaysa sa iba - sa isang aktwal na braso, isang controller na maaaring makapili ng isang masamang component sa gitna ng galaw. Iyan ang nakasaad na motibasyon para sa pagnanais ng isang stationary na deterministic policy sa halip.

DAgger: isang ideya, isang kahon

Pinapanatili ng Dataset Aggregation ang deterministic na policy at inililipat ang ayos papunta sa pangongolekta ng data. Sa bawat round: patakbuhin ang kasalukuyang policy, itala ang mga state na dinaraanan nito, tanungin ang expert kung ano sana ang tamang aksyon sa bawat isa, idagdag ang mga pares na iyon sa dataset na mayroon ka na, at muling sanayin gamit ang unyon ng lahat. Ang pangalan mismo ang algorithm - nag-a-aggregate ka, hindi ka kailanman nagtatapon.

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

May tatlong detalye na mas mabigat kaysa sa itsura nila. Ang mga label ay para sa mga state na dinaraanan ng mixed policy, pero ang mga aksyon ay galing sa expert - ang policy ang nagbibigay ng mga tanong, ang expert ang mga sagot. Ang muling pagsasanay ay sa buong aggregate, na siyang gumagawa sa bawat round na isang Follow-The-Leader step: sa round n, pinipili mo ang pinakamahusay na policy sa hindsight sa lahat ng trajectory hanggang ngayon. Ang framing na iyon ang siyang basehan ng proof. At natatapos ang algorithm sa pagbabalik ng pinakamahusay na policy sa sequence ayon sa pinili sa isang validation set, dahil ginagarantiya ng mga theorem na may isang policy sa sequence na mabuti, hindi na ang huli ang siya.

Ang beta schedule, at kung bakit ito hindi isang tuning knob

Ang mixed policy ay beta_i na pinarami sa expert kasama ang isa-minus-beta_i na pinarami sa learner. Praktikal ang punto: ang unang ilang natutong policy ay sinanay sa napakakaunting data, gumagawa ng maraming pagkakamali, at kung hindi dahil dito ay gugugol na lang ng rollout sa mga state na magiging hindi na mahalaga kapag gumaling na ang policy.

Isang kondisyon lamang ang ipinapataw ng teorya: dapat pumunta sa zero ang running average ng mga beta. Gumagana ang analysis gamit ang beta_i na nakatali ng (1 - alpha) sa kapangyarihang i-1, para sa isang constant na alpha na independiyente sa T.

Maliit ang agwat sa pagitan ng 2980 at 3030 sa isang scale na umaabot hanggang humigit-kumulang 4300, pero ang paliwanag ng papel dito ang pinaka-kapaki-pakinabang na tala sa seksyong ito. Gamit ang parameter-free na schedule, natigil si Mario sa parehong lugar nang maaga at nakabuo ng malaking bunton ng halos-magkatulad na data mula sa isang lokasyong iyon; ang pagpapahintulot sa expert na magmaneho sa ilang bahagi ng oras ay parehong nakapagpalaya sa kanya at nagpalawak sa iba't ibang uri ng state. Ang schedule ay hindi gaanong tungkol sa mixing ratio kundi tungkol sa kung ang iyong pangongolekta ng data ay patuloy bang gumagawa ng mga bagong state o paulit-ulit na parehong kabiguan.

Ang garantiya: isang reduction tungo sa no-regret online learning

Narito ang galaw na siyang gumagawa sa papel kung ano ito. Ituring ang bawat DAgger round bilang isang halimbawa sa isang online learning problem, kung saan ang loss sa round i ay ang surrogate loss sa ilalim ng state distribution ng policy na ginamit sa round i. Kumikilos ang learner sa isang policy bago pa makita ang loss na iyon, at ang sequence ay non-stationary dahil nakadepende ito sa mga policy na nagawa na hanggang ngayon.

Ang isang algorithm ay no-regret kung ang average loss nito sa N na round ay lumalapit sa average loss ng pinakamahusay na iisang policy sa hindsight. Ang Follow-The-Leader sa strongly convex na losses ay ganitong uri ng algorithm, na may average regret na lumiliit sa antas na 1/N - at ang muling pagsasanay gamit ang buong aggregate ay eksaktong Follow-The-Leader. Kahit anong ibang no-regret learner ay pwede ring gamitin: ang analysis ay isang reduction, hindi katangian ng isang optimizer lamang.

May isang lemma na nagtutulay sa agwat sa pagitan ng mixed policy na nangolekta ng data at ng natutong policy na ipapatakbo: nililimitahan ng Lemma 4.1 ang L1 distance sa pagitan ng kanilang mga state distribution ng 2 T beta_i. Kaya kailangang bumaba ang mga beta - habang malaki pa rin ang control authority ng expert, ang mga state na kinokolekta mo ay hindi pa ang mga state na gagawin ng iyong policy. Pagsamahin ang lemma sa regret bound at lalabas ang pangunahing resulta: pagkatapos ng humigit-kumulang T na iteration, may isang policy sa sequence na may surrogate loss sa ilalim ng sarili nitong distribution na nasa loob ng O(1/T) ng epsilon_N. Ipasok ito sa linear bound at maaabot mo ang Theorem 3.2.

Katamtaman ang panig ng empirical results ayon sa kasalukuyang pamantayan. Sa Super Tux Kart, hindi umunlad ang average falls per lap ng supervised baseline habang dumarating ang mas maraming data, umabot ang DAgger sa isang policy na hindi na kailanman nahulog sa track pagkatapos ng labinlimang iteration, at ang SMILe pagkatapos ng dalawampung iteration ay humigit-kumulang dalawang beses pa ring nahuhulog bawat lap. Sa handwriting benchmark, ang character accuracy ay 82 porsyento nang walang structure, 83.6 porsyento na supervised, 85.5 porsyento gamit ang DAgger. Wala sa mga ito ang isang resulta ng manipulation.

Ano ang hindi ipinapangako ng proof

Kondisyonal ang mga pahayag ng theorem, at load-bearing ang mga kondisyon.

Isang karagdagang resulta ang madalas na binabanggit bilang isang pagtanggi (refutation) pero hindi ito ganoon. Sinuri nina Rajaraman, Yang, Jiao, at Ramachandran ang mga minimax na limitasyon ng imitation learning sa episodic MDP na may finite na state space S at horizon H, at pinatunayan ang isang suboptimality lower bound sa antas ng |S| H squared over N na may bisa kahit pwede nang aktibong tanungin ng learner ang expert sa mga state na dinaanan. Iyon ay isang worst-case rate sa isang klase ng MDP sa isang fixed na episode budget, at ang tinatanggihan nito ay ang ideya na napapabuti ng interaction ang minimax rate; ibang pahayag ang theorem ng DAgger, na naglilimita sa deployed policy kaugnay ng kung ano ang kayang abutin ng sarili nitong policy class.

Kinlasify kalaunan nina Swamy, Choudhury, Bagnell, at Wu ang mga algorithm na ito ayon sa kung aling moments ng ugali ng expert ang kanilang tinutugma, at nagpakilala ng konsepto ng moment recoverability na naglalarawan kung gaano kahusay pinagagaan ng bawat pamilya ang compounding error. Sinasaklaw ng mga survey nina Osa at ni Celemin ang algorithmic landscape at ang mga human-feedback interface.

Ang bayarin: paglagay ng label sa mga state na hindi kailanman ginawa ng expert

Ipinapalagay ng lahat sa itaas na may isang expert na maaaring tanungin kahit saan. Sa simulation, gamit ang isang planner na halos libre - ginamit ng mga eksperimento sa Mario ang isang near-optimal na planner na may buong access sa game state. Sa isang tao sa isang robot, ito ang pangunahing gastos, at isa itong kakaiba: kailangang gumawa ng tamang aksyon ang tao sa isang configuration na hindi kailanman magmumula sa sarili niyang kakayahan.

Direktang binanggit nina Kelly, Sidrane, Driggs-Campbell, at Kochenderfer ang objection na ito sa HG-DAgger paper. Hinihiling ng vanilla DAgger na magbigay ang expert ng mga action label habang hindi ganap na kontrolado ang sistema. Binabawasan nito ang kaligtasan, at sa mga human expert, malamang na bumaba ang kalidad ng mga nakolektang label, na iniuugnay nila sa perceived na actuator lag. Ang label na natatanggap mo ay hindi ang label na ipinagpalagay ng algorithm.

Sinasalakay nina Laskey at mga kasamahan ang problema mula sa kabilang panig gamit ang DART, at prangka ang kanilang framing: nakakapagod para sa mga human supervisor ang mga on-policy technique, nagdaragdag ng computational burden, at maaaring dumaan sa mga mapanganib na state habang sinasanay. Ang alternatibo nila ay nagsisingit ng calibrated na noise sa mismong mga demonstration ng supervisor, kaya naidedemonstrate ang recovery kahit hindi kailanman pinatakbo ng robot ang isang hindi pa napagkakatiwalaang policy. Sa MuJoCo Humanoid, iniulat nilang binabawasan ng DART ang cumulative reward ng supervisor ng 5 porsyento habang sinasanay, samantalang ang DAgger ay nagpapatakbo ng mga policy na may 80 porsyentong mas mababang cumulative reward kaysa sa supervisor; sa grasping sa clutter gamit ang isang Toyota HSR, isang average na 62 porsyentong pagtaas kumpara sa behavior cloning.

Itinuturing ng SafeDAgger nina Zhang at Cho ang mga query sa reference policy bilang ang iisang mapagkukunang kakaunti: may hiwalay na safety policy na naghuhula, nang walang query, kung malapit nang lumihis ang primary policy mula sa reference nang lampas sa isang threshold, at ang mga state lamang na iyon ang inililipat. Ang tatlong ito ay tumutugon sa parehong katotohanan - walang sinisingil ang analysis ng DAgger para sa mga label ng expert, pero malaki ang sinisingil ng realidad.

Ano ang ibig sabihin nito para sa isang SO-100 sa iyong desk

Isalin ang horizon sa sarili mong unit. Ang isang dalawampung-segundong episode sa 30 frames per second ay 600 decision step, at ang T sa bawat bound sa itaas ay ang bilang na iyon. Sa T = 600, ang pagkakaiba sa pagitan ng isang termino na sumusukat kasabay ng T at isa na sumusukat kasabay ng T squared ay ang pagkakaiba sa pagitan ng isang policy na nakakabawi mula sa isang masamang paglapit at isa na hindi.

Bahagi ito kung bakit tumutulong ang action chunking: kapag ang isang policy ay naglalabas ng isang maikling sequence ng mga aksyon bawat inference step, bumababa ang bilang ng decision point, at bumababa rin ang bilang ng pagkakataong mag-compound ang error. Tinawag nina Zhao, Kumar, Levine, at Finn ang compounding error bilang ang motibasyon para sa Action Chunking with Transformers, at iniulat ang 80 hanggang 90 porsyentong success sa anim na mahirap na aktwal-mundong gawain, sa mababang-halaga at bimanual na hardware, mula sa sampung minuto lamang na demonstration. Hindi inaalis ng chunking ang covariate shift - sarili pa rin ng policy ang mga state - pero pinaiikli nito ang epektibong horizon. Tingnan ang action chunking at ang gabay sa SO-100 imitation learning.

Ang ikalawang salin ay ang progress metric. Hindi mo direktang masusukat ang epsilon sa ilalim ng sarili nitong distribution ng policy - kailangan nito ng ground-truth na aksyon ng expert para sa bawat state na dinaanan, ang mismong bagay na sinusubukan mong iwasang gawin. Ang ibinibigay sa iyo ng isang human-gated loop sa halip ay ang intervention rate: ang porsyento ng mga frame sa isang run kung saan kinuha ng tao ang kontrol. Isa itong proxy, at gumagalaw ito dahil sa mga dahilang walang kinalaman sa policy - mas kaunti ang panghihimasok ng isang matiyagang operator. Kung gagamitin nang konsistent, ito ang iisang numerong nagsasabi kung sulit ba ang isang round sa ginugol na hapon.

Isang ikatlong salin ay isang babala tungkol sa kalidad ng data na hindi sinasaklaw ng analysis. Pinag-aralan nina Mandlekar at mga kasamahan ang anim na offline learning algorithm sa limang simulated at tatlong aktwal-mundong multi-stage manipulation task, at iniulat ang isang sensitivity sa mga algorithmic design choice, isang pagdepende sa kalidad ng mga demonstration, at variability na dulot ng stopping criterion. Iginigiit nina Belkhale, Cui, at Sadigh na dapat i-formalize ang kalidad ng dataset sa pamamagitan ng action divergence at transition diversity, at binanggit na hindi laging kapaki-pakinabang ang state diversity. Ang isang DAgger round ay nagdaragdag ng mga state na walang sinadyang pumili: ang iba ay ang recovery data na kailangan mo, ang iba ay ang robot na nag-aalboroto habang kinakapa mo ang takeover control.

Sa mekanismo, anim na hakbang ang isang round: patakbuhin ang inference nang naka-on ang recording, kunin ang kontrol kapag masama ang ugali ng policy, suriin ang run at i-file ang bawat episode, i-sync ang mga correction, buuin ang isang mixed dataset mula sa mga orihinal kasama ang mga correction na may episode selection na eksplisitong ginawa bawat source, at ipagpatuloy ang pagsasanay mula sa nakaraang checkpoint sa halip na mula sa base model. Sa ay-robots, umiiral ang mga hakbang na ito bilang mga buton, na inaalis ang plumbing pero hindi ang paghatol. Dalawang paalala: ang pagpapatuloy mula sa isang checkpoint ay nag-i-initialize lamang ng weights at hindi isang optimizer resume, at ang leader-arm alignment move ay bahagya pa lang nasusubukan sa hardware. Tingnan ang pagsasanay at ang mga dataset.

Ang family tree, sa isang table

Mga madalas itanong

Saan magpatuloy mula rito

Kung hindi ka pa nakakapagsanay ng policy, maaga pa para sa teoryang ito: mag-record muna ng isang dataset, magsimula sa pagsasanay ng iyong unang policy at ang desktop client. Kung tinitimbang mo ang isa pang daang malinis na demonstration laban sa pagsisimula ng mga correction: hindi maaayos ng malinis na demonstration ang isang problema sa distribution. Para sa mekanismo, magpatuloy sa human-gated variant at pagkatapos ay SO-100 walkthrough.