DAgger Dijelaskan: Kenapa Behavior Cloning Melencong dan Apa yang Sebenarnya Dibuktikan oleh Dataset Aggregation

Terdapat satu kegagalan khusus yang akan ditemui oleh sesiapa sahaja yang melatih satu policy manipulasi, lambat-laun. Policy itu menghala ke arah kiub, sampai dalam jarak dua sentimeter, teragak-agak, melencong ke tepi, kemudian melakukan sesuatu yang tiada kaitan dengan tugas tersebut. Validation loss adalah baik. Open-loop replay terhadap episod held-out juga baik. Namun begitu lengan itu berakhir pada satu postur yang langsung tidak muncul dalam data latihan, dan dari situ ia tidak mempunyai apa-apa jawapan yang munasabah untuk diberikan.

Kegagalan itu ada namanya dan mempunyai teori yang sudah mantap di sebaliknya. Ini ialah artikel pertama daripada empat artikel mengenai DAgger, dan ia membincangkan hujah itu sendiri: kenapa menyesuaikan policy pada trajektori pakar sendiri menghasilkan ralat yang boleh membesar mengikut kuasa dua panjang episod, apa yang diubah oleh dataset aggregation, dan apa yang tidak dijanjikan oleh bukti no-regret. Gelung pada perkakasan sebenar dibincangkan dalam menjalankan gelung DAgger pada SO-100, varian human-gated dalam HG-DAgger dan campur tangan human-gated, dan soal pengukuran dalam mengukur gelung DAgger.

Andaian yang dibuat secara senyap oleh behavior cloning

Dataset demonstrasi ialah timbunan pasangan pemerhatian-tindakan (observation-action). Behavior cloning menyesuaikan satu fungsi kepada timbunan itu menggunakan supervised learning biasa dan berhenti di situ. Ini ialah idea paling lama dalam bidang ini. ALVINN ciptaan Pomerleau, pada tahun 1988, ialah rangkaian back-propagation tiga lapisan yang mengambil imej daripada kamera dan pengesan jarak laser lalu menghasilkan arah yang perlu dilalui oleh kenderaan; ia dilatih menggunakan imej jalan raya simulasi dan berjaya mengikut jalan raya sebenar dalam sesetengah keadaan lapangan. Resipinya tidak banyak berubah; rangkaiannyalah yang berubah.

Yang dilangkau ialah semakan tentang dari mana pasangan-pasangan itu datang. Setiap satunya terletak pada trajektori yang dihasilkan oleh pendemonstrasi. Policy yang anda gunakan pula menghasilkan trajektorinya sendiri. Sebaik sahaja ia menyimpang, ia ditanya tentang keadaan yang tiada dalam taburan latihan, dan jawapannya membawanya lebih jauh lagi terkeluar. Ross, Gordon dan Bagnell membuka kertas DAgger dengan tepat perkara ini: ramalan berjujukan melanggar andaian i.i.d. yang mendasari pembelajaran statistik, kerana ramalan pembelajar itu sendiri menentukan input yang akan dilihatnya seterusnya.

Ilustrasi paling jelas dalam kertas itu bukan robot langsung. Mengklon satu planner hampir-optimum untuk Super Mario Bros. menghasilkan policy yang berulang kali tersekat pada halangan dan bukannya melompatinya. Sebabnya ialah keseluruhan hujah dalam satu ayat: pakar sentiasa melompat dari jarak yang selesa, jadi dataset itu tidak mengandungi satu pun keadaan di mana Mario ditekan rapat pada halangan, dan oleh itu tiada label untuk apa yang perlu dibuat sebaik sahaja ia berlaku.

Gantikan Mario dengan lengan SO-100 dan strukturnya tetap sama. Demonstrasi anda menunjukkan pendekatan yang bersih dan genggaman yang bersih, bukan gripper yang tertutup dua sentimeter terlalu awal - jadi policy tidak tahu apa yang perlu dibuat dari situ, dan apa sahaja tekaannya hanya membawanya lebih jauh terkeluar. Covariate shift ialah sifat prosedur pengumpulan data, bukan sifat seni bina rangkaian.

Dari mana datangnya sebutan kuadratik itu

Kertas AISTATS 2010 oleh Ross dan Bagnell, Efficient Reductions for Imitation Learning, menjadikan sifat berkompaun ini lebih tepat. Biar T ialah horizon tugas, biar kos tugas terikat dalam selang unit, dan biar epsilon ialah surrogate loss yang diukur di bawah taburan keadaan pakar - iaitu angka yang dilaporkan oleh set validasi anda. Maka kos tambahan menjalankan policy tersebut selama T langkah, berbanding pakar, terikat oleh T kuasa dua didarab epsilon. Ross, Gordon dan Bagnell menyatakan semula ini sebagai Teorem 2.1 dalam kertas DAgger dan menambah ayat yang penting: sempadan ini ketat. Terdapat masalah di mana policy dengan epsilon loss pada taburan pakar benar-benar mengalami kos tambahan yang membesar secara kuadratik mengikut T.

Ketat tidak bermakna tipikal. Sebutan kuadratik itu ialah kes paling teruk merentasi satu kelas masalah, bukan ramalan tentang tugas pick-and-place anda. Apa yang dibuktikannya ialah lebih banyak demonstrasi pakar tidak dapat menghapuskan masalah itu: ia hanya mempertajamkan anggaran epsilon pada satu taburan yang policy tersebut tidak akan diuji ke atasnya.

Jalan keluarnya terdapat dalam kertas yang sama, dinyatakan semula sebagai Teorem 2.2. Jika satu policy mencapai epsilon loss di bawah taburan keadaan dirinya sendiri, dan satu tindakan yang salah mengenakan kos paling banyak u dalam cost-to-go di bawah pakar, kos tambahan itu terikat oleh u didarab T didarab epsilon - linear mengikut horizon. Pemalar u ialah kuantiti yang menarik: paling banyak 1 untuk ketidaksepakatan 0-1 dengan pakar, dan O(1) apabila pakar boleh pulih dalam beberapa langkah sahaja. Dalam kes paling teruk ia ialah O(T), dan sempadan linear itu kemudian tidak lebih baik daripada sempadan kuadratik.

Dua percubaan yang wujud sebelum DAgger

Forward training ialah jawapan yang jujur tetapi tidak praktikal. Latih satu policy berasingan bagi setiap timestep, mengikut urutan, masing-masing pada taburan keadaan yang diakibatkan oleh policy yang telah ditetapkan bagi langkah-langkah terdahulu, supaya setiap policy melihat dengan tepat taburan yang akan dihadapinya. Masalahnya terletak pada huraiannya sendiri: T policy, dilatih secara berjujukan, tanpa early stopping. Bagi satu episod manipulasi pada 30 bingkai sesaat, T berada dalam lingkungan ratusan.

SMILe, daripada kertas yang sama, dan SEARN, daripada kerja Daume, Langford dan Marcu mengenai structured prediction, mengambil laluan yang lain: satu policy pegun (stationary), tetapi stokastik. Setiap iterasi melatih satu komponen dan menambahkannya ke dalam satu campuran, mengalihkan jisim kebarangkalian menjauhi pakar. Hasilnya ialah satu campuran di mana sesetengah komponen lebih teruk daripada yang lain - pada lengan fizikal, ini bermakna satu pengawal yang boleh mengambil sampel komponen yang buruk di tengah-tengah pergerakan. Itulah motivasi yang dinyatakan untuk mahukan satu policy pegun yang deterministik sebagai gantinya.

DAgger: satu idea, satu kotak

Dataset Aggregation mengekalkan policy deterministik dan memindahkan pembetulan itu ke dalam pengumpulan data. Setiap pusingan: jalankan rollout policy semasa, rekod keadaan yang dilaluinya, tanya pakar apakah tindakan yang betul bagi setiap satu, tambahkan pasangan-pasangan itu ke dalam dataset yang sudah anda ada, dan latih semula menggunakan gabungan kesemuanya. Nama itu sendiri ialah algoritmanya - anda mengagregat, anda tidak sesekali membuang.

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

Tiga butiran ini membawa lebih makna daripada yang kelihatan. Label-label itu adalah untuk keadaan yang dilawati oleh policy campuran, tetapi tindakannya datang daripada pakar - policy menyediakan soalan, pakar menyediakan jawapan. Latihan semula dilakukan ke atas keseluruhan agregat, yang menjadikan setiap pusingan satu langkah Follow-The-Leader: pada pusingan n anda memilih policy terbaik secara retrospektif merentasi semua trajektori setakat itu. Kerangka inilah yang menjadi tumpuan bukti tersebut. Dan algoritma ini berakhir dengan memulangkan policy terbaik dalam jujukan itu seperti yang dipilih pada satu set validasi, kerana teorem-teorem menjamin bahawa sesuatu policy dalam jujukan itu adalah baik, bukan bahawa yang terakhir itu baik.

Jadual beta, dan kenapa ia bukan suatu tombol penalaan

Policy campuran ialah beta_i didarab pakar, ditambah (satu tolak beta_i) didarab pembelajar. Tujuannya bersifat praktikal: beberapa policy terlatih yang pertama dilatih menggunakan sangat sedikit data, melakukan banyak kesilapan, dan jika tidak dikawal akan menghabiskan rollout dalam keadaan-keadaan yang menjadi tidak relevan sebaik sahaja policy itu bertambah baik.

Teori ini mengenakan tepat satu syarat: purata bergerak bagi beta mestilah menuju ke sifar. Analisis ini menggunakan beta_i yang tersempadan oleh (1 - alpha) berkuasa i-1, bagi satu pemalar alpha yang tidak bergantung kepada T.

Jurang antara 2980 dan 3030 pada skala yang mencecah kira-kira 4300 adalah kecil, tetapi penjelasan kertas tersebut mengenainya ialah nota praktikal paling berguna dalam bahagian ini. Dengan jadual bebas-parameter, Mario tersekat pada tempat yang sama pada peringkat awal dan menghasilkan sejumlah besar data yang hampir-berulang daripada satu lokasi itu sahaja; membenarkan pakar memandu pada sebahagian daripada masa bukan sahaja melepaskannya daripada kesekatan itu tetapi juga meluaskan kepelbagaian keadaan. Jadual itu kurang berkait dengan nisbah campuran berbanding sama ada pengumpulan data anda terus menghasilkan keadaan baharu atau kegagalan yang sama berulang-ulang.

Jaminan itu: satu reduksi kepada no-regret online learning

Inilah langkah yang menjadikan kertas ini seperti adanya. Anggap setiap pusingan DAgger sebagai satu contoh dalam satu masalah online learning, di mana loss pada pusingan i ialah surrogate loss di bawah taburan keadaan bagi policy yang digunakan pada pusingan i. Pembelajar komited kepada satu policy sebelum melihat loss tersebut, dan jujukan itu bersifat non-stationary kerana ia bergantung kepada policy-policy yang telah dihasilkan setakat itu.

Satu algoritma dikatakan no-regret jika purata loss-nya sepanjang N pusingan menghampiri purata loss policy tunggal terbaik secara retrospektif. Follow-The-Leader pada loss yang strongly convex ialah algoritma sebegini, dengan purata regret mengecil pada aras 1/N - dan melatih semula menggunakan keseluruhan agregat adalah tepat sekali Follow-The-Leader. Mana-mana pembelajar no-regret yang lain juga boleh berfungsi sama baik: analisis ini adalah satu reduksi, bukan sifat khusus bagi satu pengoptimum tertentu.

Satu lema merapatkan jurang antara policy campuran yang mengumpul data dan policy terlatih yang akan digunakan: Lema 4.1 menyempadani jarak L1 antara taburan keadaan kedua-duanya dengan 2 T beta_i. Inilah sebabnya beta mesti mereput - selagi pakar masih memegang autoriti kawalan yang ketara, keadaan yang anda kumpul bukanlah keadaan yang akan dihasilkan oleh policy anda. Gabungkan lema ini dengan sempadan regret dan hasil utamanya terhasil: selepas kira-kira T iterasi, terdapat satu policy dalam jujukan itu yang mempunyai surrogate loss di bawah taburannya sendiri dalam lingkungan O(1/T) daripada epsilon_N. Masukkan itu ke dalam sempadan linear dan anda sampai kepada Teorem 3.2.

Sisi empirikal ini sederhana sahaja mengikut piawaian masa kini. Dalam Super Tux Kart, baseline supervised tidak menambah baik purata kejatuhannya bagi setiap pusingan (lap) walaupun lebih banyak data tiba, DAgger mencapai satu policy yang tidak pernah tergelincir keluar landasan selepas lima belas iterasi, manakala SMILe selepas dua puluh iterasi masih tergelincir kira-kira dua kali bagi setiap pusingan. Pada benchmark tulisan tangan, ketepatan aksara ialah 82 peratus tanpa struktur, 83.6 peratus secara supervised, dan 85.5 peratus dengan DAgger. Tiada satu pun daripada ini merupakan hasil manipulasi.

Apa yang tidak dijanjikan oleh bukti ini

Pernyataan-pernyataan teorem ini bersyarat, dan syarat-syarat itu memikul beban yang penting.

Satu lagi hasil sering dipetik sebagai satu penafian, sedangkan ia bukan begitu. Rajaraman, Yang, Jiao dan Ramachandran mengkaji had minimax bagi pembelajaran tiruan dalam MDP episodik dengan ruang keadaan terhingga S dan horizon H, dan membuktikan satu sempadan bawah sub-optimum pada aras |S| H kuasa dua bahagi N yang tetap terpakai walaupun pembelajar boleh secara aktif bertanya kepada pakar pada keadaan yang dilawati. Itu ialah kadar kes-paling-teruk merentasi satu kelas MDP pada satu bajet episod yang tetap, dan apa yang ditolaknya ialah idea bahawa interaksi menambah baik kadar minimax; teorem DAgger merupakan satu pernyataan yang berbeza, iaitu menyempadani policy yang digunakan secara relatif kepada apa yang boleh dicapai oleh kelas policy-nya sendiri.

Swamy, Choudhury, Bagnell dan Wu kemudiannya mengklasifikasikan algoritma-algoritma ini mengikut momen tingkah laku pakar yang cuba disepadankan, dan memperkenalkan konsep moment recoverability yang menggariskan sejauh mana setiap keluarga algoritma mengurangkan compounding error. Kajian tinjauan oleh Osa dan oleh Celemin merangkumi lanskap algoritma serta antara muka maklum balas manusia.

Kosnya: melabelkan keadaan yang tidak pernah dihasilkan oleh pakar

Segala-galanya di atas mengandaikan satu pakar yang boleh ditanya di mana-mana sahaja. Dalam simulasi dengan satu planner yang hampir percuma - eksperimen Mario menggunakan satu planner hampir-optimum dengan akses penuh kepada keadaan permainan. Dengan seorang manusia pada sebuah robot, itulah kos yang mendominasi, dan satu kos yang agak ganjil: manusia itu perlu menghasilkan satu tindakan yang betul dalam satu konfigurasi yang tidak akan pernah dicipta oleh kecekapannya sendiri.

Kelly, Sidrane, Driggs-Campbell dan Kochenderfer menyatakan bantahan ini secara terus dalam kertas HG-DAgger. DAgger asal (vanilla) memerlukan pakar membekalkan label tindakan sedangkan dia tidak sepenuhnya mengawal sistem tersebut. Ini mengurangkan keselamatan, dan dengan pakar manusia ia berkemungkinan menjejaskan kualiti label yang dikumpul, yang mereka kaitkan dengan lag aktuator yang dirasai. Label yang anda perolehi kembali bukanlah label yang diandaikan oleh algoritma tersebut.

Laskey dan rakan-rakan menyerang masalah ini dari sudut yang lain dengan DART, dan kerangka mereka adalah terus terang: teknik on-policy adalah membosankan bagi penyelia manusia, menambah beban pengkomputeran, dan mungkin melawati keadaan yang berbahaya semasa latihan. Alternatif mereka menyuntik hingar (noise) yang dikalibrasi ke dalam demonstrasi penyelia sendiri, supaya pemulihan dapat didemonstrasikan tanpa robot tersebut sekali pun menjalankan satu policy yang tidak dipercayai. Pada MuJoCo Humanoid mereka melaporkan DART menurunkan ganjaran kumulatif penyelia sebanyak 5 peratus semasa latihan, manakala DAgger menjalankan policy dengan ganjaran kumulatif 80 peratus lebih rendah berbanding penyelia; pada tugas menggenggam dalam keadaan bersepah dengan Toyota HSR, peningkatan purata 62 peratus berbanding behavior cloning.

SafeDAgger ciptaan Zhang dan Cho melayan pertanyaan kepada reference policy sebagai sumber yang terhad: satu safety policy berasingan meramalkan, tanpa bertanya, sama ada primary policy akan menyimpang daripada reference policy melebihi satu ambang, dan hanya keadaan-keadaan itu sahaja yang diserahkan. Ketiga-tiganya bertindak balas terhadap fakta yang sama - analisis DAgger tidak mengenakan sebarang kos untuk label pakar, sedangkan realiti mengenakan kos yang besar.

Apa maknanya ini untuk SO-100 di atas meja anda

Terjemahkan horizon itu kepada unit anda sendiri. Satu episod dua puluh saat pada 30 bingkai sesaat ialah 600 langkah keputusan, dan T dalam setiap sempadan di atas ialah angka itu. Pada T = 600, perbezaan antara satu sebutan yang berskala dengan T dan satu lagi yang berskala dengan T kuasa dua ialah perbezaan antara satu policy yang dapat pulih daripada pendekatan yang buruk dengan satu lagi yang tidak dapat.

Inilah sebahagian daripada sebab kenapa action chunking membantu: apabila satu policy mengeluarkan satu jujukan pendek tindakan bagi setiap langkah inferens, bilangan titik keputusan berkurangan, dan begitu juga bilangan peluang untuk berkompaun. Zhao, Kumar, Levine dan Finn menamakan compounding error sebagai motivasi bagi Action Chunking with Transformers, dan melaporkan kadar kejayaan 80 hingga 90 peratus pada enam tugas dunia-sebenar yang sukar, pada perkakasan bimanual kos-rendah, hasil daripada demonstrasi bernilai sepuluh minit sahaja. Chunking tidak menghapuskan covariate shift - keadaan-keadaan itu tetap milik policy itu sendiri - tetapi ia memendekkan horizon efektif. Lihat action chunking dan panduan pembelajaran tiruan SO-100.

Terjemahan kedua ialah metrik kemajuan. Anda tidak boleh mengukur epsilon di bawah taburan policy itu sendiri secara terus - itu memerlukan tindakan pakar ground-truth bagi setiap keadaan yang dilawati, iaitu perkara yang cuba anda elakkan daripada dihasilkan. Apa yang diberikan oleh satu gelung human-gated sebagai gantinya ialah kadar campur tangan (intervention rate): pecahan bingkai dalam satu larian di mana manusia telah mengambil alih. Ia adalah satu proksi, dan ia berubah atas sebab-sebab yang tiada kaitan dengan policy tersebut - seorang operator yang sabar campur tangan lebih sedikit. Jika digunakan secara konsisten, itulah satu-satunya angka yang memberitahu sama ada satu pusingan itu berbaloi dengan masa yang dihabiskan.

Terjemahan ketiga ialah satu amaran kualiti-data yang tidak dirangkumi oleh analisis tersebut. Mandlekar dan rakan-rakan mengkaji enam algoritma offline learning pada lima tugas manipulasi berbilang-peringkat yang disimulasikan dan tiga tugas dunia-sebenar, dan melaporkan sensitiviti terhadap pilihan reka bentuk algoritma, kebergantungan kepada kualiti demonstrasi, dan kebolehubahan yang disebabkan oleh kriteria pemberhentian. Belkhale, Cui dan Sadigh berhujah bahawa kualiti dataset harus diformalkan melalui action divergence dan transition diversity, dan mencatatkan bahawa kepelbagaian keadaan (state diversity) tidak selalunya bermanfaat. Satu pusingan DAgger menambah keadaan-keadaan yang tidak dipilih secara sengaja oleh sesiapa: sebahagiannya ialah data pemulihan yang anda perlukan, sebahagian lagi ialah robot yang meronta-ronta semasa anda tergagap-gagap mencari kawalan pengambilalihan.

Secara mekanikal, satu pusingan terdiri daripada enam langkah: jalankan inferens dengan rakaman dihidupkan, ambil alih apabila policy tersebut bertindak salah, semak larian tersebut dan failkan setiap episod, segerakkan (sync) pembetulan-pembetulan itu, gubah satu dataset campuran daripada data asal ditambah pembetulan dengan pemilihan episod dibuat secara eksplisit bagi setiap sumber, dan teruskan latihan daripada checkpoint sebelumnya dan bukannya daripada model asas (base model). Pada ay-robots, langkah-langkah ini wujud sebagai butang-butang, yang menghapuskan kerja-kerja teknikal tetapi bukan pertimbangan yang diperlukan. Dua peringatan: meneruskan daripada satu checkpoint hanya menginisialisasi weight dan bukannya satu optimizer resume, dan langkah penjajaran leader-arm masih kurang diuji pada perkakasan. Lihat latihan dan dataset.

Pohon keluarga, dalam satu jadual

Soalan lazim

Ke mana seterusnya

Jika anda belum melatih satu policy lagi, teori ini masih terlalu awal untuk anda: rakam satu dataset dahulu, bermula daripada melatih policy pertama anda dan desktop client. Jika anda sedang menimbang antara seratus lagi demonstrasi bersih berbanding memulakan pembetulan: demonstrasi bersih tidak dapat membetulkan masalah taburan. Untuk mekanismenya, teruskan dengan varian human-gated dan kemudian panduan langkah demi langkah SO-100.