DAgger Dijelaskan: Mengapa Behavior Cloning Melenceng dan Apa yang Sebenarnya Dibuktikan oleh Dataset Aggregation

Ada satu kegagalan spesifik yang cepat atau lambat dialami oleh semua orang yang melatih policy manipulasi. Policy tersebut mendekati kubus, sampai dalam jarak dua sentimeter, ragu-ragu, melenceng ke samping, lalu melakukan sesuatu yang tidak ada hubungannya dengan tugasnya. Validation loss baik-baik saja. Open-loop replay terhadap episode held-out juga baik-baik saja. Namun lengan robot berakhir dalam pose yang tidak pernah muncul di data pelatihan, dan dari situ ia tidak punya jawaban yang masuk akal.

Kegagalan ini punya nama dan sudah ada teori yang mapan di baliknya. Ini adalah artikel pertama dari empat artikel tentang DAgger, dan artikel ini membahas argumen intinya: mengapa melatih policy pada trajektori milik demonstrator sendiri menghasilkan error yang bisa tumbuh sebanding dengan kuadrat panjang episode, apa yang diubah oleh dataset aggregation, dan apa yang tidak dijamin oleh bukti no-regret. Loop pada hardware sungguhan dibahas di menjalankan loop DAgger pada SO-100, variasi human-gated dibahas di HG-DAgger dan intervensi human-gated, dan soal pengukurannya dibahas di mengukur loop DAgger.

Asumsi tersembunyi yang dibuat oleh behavior cloning

Dataset demonstrasi adalah kumpulan pasangan observasi-aksi. Behavior cloning melatih sebuah fungsi pada kumpulan tersebut dengan supervised learning biasa, lalu berhenti di situ. Ini adalah ide tertua di bidang ini. ALVINN buatan Pomerleau, pada 1988, adalah jaringan back-propagation tiga lapis yang mengambil gambar dari kamera dan laser range finder lalu menghasilkan arah yang harus ditempuh kendaraan; jaringan ini dilatih pada gambar jalan hasil simulasi dan mampu mengikuti jalan sungguhan dalam beberapa kondisi lapangan. Resepnya tidak banyak berubah; yang berubah adalah jaringannya.

Yang terlewatkan adalah pemeriksaan dari mana pasangan-pasangan itu berasal. Setiap pasangan terletak pada trajektori yang dihasilkan oleh demonstrator. Policy yang Anda deploy menghasilkan trajektorinya sendiri. Begitu ia menyimpang, ia ditanya tentang state yang tidak ada dalam distribusi pelatihan, dan jawabannya justru membawanya semakin jauh. Ross, Gordon, dan Bagnell membuka paper DAgger dengan persis hal ini: prediksi sekuensial melanggar asumsi i.i.d. yang mendasari statistical learning, karena prediksi si learner sendiri menentukan input apa yang akan ia lihat berikutnya.

Ilustrasi paling jelas dalam paper itu justru bukan robot sama sekali. Meng-clone sebuah planner near-optimal untuk Super Mario Bros. menghasilkan policy yang berulang kali tersangkut di depan rintangan alih-alih melompatinya. Alasannya merangkum seluruh argumen dalam satu kalimat: expert selalu melompat dari jarak yang nyaman, sehingga dataset tidak memuat satu pun state di mana Mario terhimpit rintangan, dan karena itu tidak ada label tentang apa yang harus dilakukan begitu itu terjadi.

Ganti Mario dengan lengan SO-100 dan strukturnya identik. Demonstrasi Anda menunjukkan pendekatan yang mulus dan genggaman yang mulus, bukan gripper yang menutup dua sentimeter terlalu cepat - sehingga policy tidak tahu harus berbuat apa dari situ, dan apa pun tebakannya justru membawanya semakin jauh. Covariate shift adalah sifat dari prosedur pengumpulan data, bukan sifat dari arsitektur jaringannya.

Dari mana asal suku kuadratik

Paper AISTATS 2010 oleh Ross dan Bagnell, Efficient Reductions for Imitation Learning, membuat akumulasi error ini presisi. Misalkan T adalah horizon tugas, misalkan cost tugas dibatasi dalam interval satuan, dan misalkan epsilon adalah surrogate loss yang diukur berdasarkan distribusi state milik expert - angka yang dilaporkan oleh validation set Anda. Maka biaya tambahan dari menjalankan policy tersebut selama T langkah, relatif terhadap expert, dibatasi oleh T kuadrat dikali epsilon.

Tight tidak berarti tipikal. Suku kuadratik ini adalah worst case pada suatu kelas masalah, bukan prediksi tentang tugas pick-and-place Anda. Yang ditegaskannya adalah bahwa demonstrasi expert yang lebih banyak tidak bisa menghilangkan masalah ini: itu hanya mempertajam estimasi epsilon pada distribusi yang policy-nya tidak akan diuji di sana.

Jalan keluarnya ada di paper yang sama, ditegaskan kembali sebagai Teorema 2.2. Jika sebuah policy mencapai loss epsilon berdasarkan distribusi state miliknya sendiri, dan satu aksi yang salah berbiaya paling banyak u dalam cost-to-go menurut expert, maka biaya tambahannya dibatasi oleh u dikali T dikali epsilon - linear terhadap horizon. Konstanta u adalah besaran yang menarik: paling banyak 1 untuk selisih 0-1 dengan expert, dan O(1) kapan pun expert bisa pulih dalam beberapa langkah. Dalam kasus terburuk nilainya O(T), dan batas linear ini pun menjadi tidak lebih baik daripada batas kuadratik.

Dua upaya yang mendahului DAgger

Forward training adalah jawaban yang jujur tapi tidak praktis. Latih policy terpisah untuk setiap timestep, secara berurutan, masing-masing pada distribusi state yang dihasilkan oleh policy-policy yang sudah ditetapkan untuk langkah-langkah sebelumnya, sehingga setiap policy benar-benar melihat distribusi yang akan dihadapinya. Masalahnya ada dalam deskripsinya sendiri: T buah policy, dilatih secara berurutan, tanpa early stopping. Untuk satu episode manipulasi pada 30 frame per detik, T bernilai ratusan.

SMILe, dari paper yang sama, dan SEARN, dari karya Daume, Langford, dan Marcu tentang structured prediction, mengambil jalan lain: satu policy stasioner, tetapi stokastik. Setiap iterasi melatih satu komponen dan menambahkannya ke dalam campuran, menggeser massa probabilitas menjauh dari expert. Hasilnya adalah campuran di mana sebagian komponen lebih buruk daripada yang lain - pada lengan robot fisik, ini berarti controller yang bisa saja mengambil sampel komponen yang buruk di tengah gerakan. Itulah motivasi yang dinyatakan untuk menginginkan policy stasioner yang deterministik sebagai gantinya.

DAgger: satu ide, satu kotak

Dataset Aggregation mempertahankan policy deterministik dan memindahkan perbaikannya ke tahap pengumpulan data. Setiap ronde: jalankan (roll out) policy saat ini, catat state yang dikunjunginya, tanyakan pada expert apa aksi yang benar untuk masing-masing state tersebut, tambahkan pasangan-pasangan itu ke dataset yang sudah Anda miliki, lalu latih ulang pada gabungannya. Namanya adalah algoritmanya sendiri - Anda mengagregasi, Anda tidak pernah 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

Ada tiga detail yang bobotnya lebih besar daripada kelihatannya. Label diberikan untuk state yang dikunjungi oleh policy campuran, tetapi aksinya berasal dari expert - policy menyediakan pertanyaannya, expert menyediakan jawabannya. Pelatihan ulang dilakukan pada seluruh agregat, yang menjadikan setiap ronde sebagai satu langkah Follow-The-Leader: pada ronde n Anda memilih policy terbaik secara hindsight atas seluruh trajektori sejauh ini. Kerangka inilah yang menjadi tumpuan buktinya. Dan algoritma ini berakhir dengan mengembalikan policy terbaik dalam urutan tersebut, dipilih berdasarkan validation set, karena teorema-teoremanya hanya menjamin bahwa beberapa policy dalam urutan itu baik, bukan berarti yang terakhir pasti baik.

Jadwal beta, dan mengapa itu bukan tombol tuning

Policy campuran adalah beta_i dikali expert ditambah (satu dikurangi beta_i) dikali learner. Alasannya praktis: beberapa policy hasil pembelajaran yang pertama dilatih dengan data yang sangat sedikit, membuat banyak kesalahan, dan jika dibiarkan akan menghabiskan rollout pada state yang jadi tidak relevan begitu policy-nya membaik.

Teorinya hanya mensyaratkan satu kondisi: rata-rata berjalan dari beta harus menuju nol. Analisisnya berlaku dengan beta_i dibatasi oleh (1 - alpha) pangkat (i-1), untuk suatu konstanta alpha yang tidak bergantung pada T.

Selisih antara 2980 dan 3030 pada skala yang membentang hingga sekitar 4300 memang kecil, tetapi penjelasan paper tentang hal ini adalah catatan praktis paling berguna di bagian tersebut. Dengan jadwal parameter-free, Mario cepat tersangkut di titik yang sama dan menghasilkan banyak data yang hampir duplikat dari satu lokasi itu saja; membiarkan expert mengemudikan sebagian waktu sekaligus melepaskannya dari kemacetan dan memperluas variasi state. Jadwal ini lebih berkaitan dengan apakah pengumpulan data Anda terus menghasilkan state baru atau kegagalan yang sama, ketimbang soal rasio pencampurannya.

Jaminannya: reduksi ke no-regret online learning

Inilah langkah yang membuat paper ini menjadi seperti sekarang. Perlakukan setiap ronde DAgger sebagai satu contoh dalam masalah online learning, di mana loss pada ronde i adalah surrogate loss berdasarkan distribusi state dari policy yang digunakan pada ronde i. Learner berkomitmen pada satu policy sebelum melihat loss tersebut, dan urutannya bersifat non-stasioner karena bergantung pada policy-policy yang dihasilkan sejauh ini.

Sebuah algoritma disebut no-regret jika rata-rata loss-nya selama N ronde mendekati rata-rata loss dari satu policy terbaik secara hindsight. Follow-The-Leader pada loss yang strongly convex adalah algoritma semacam itu, dengan rata-rata regret yang menyusut pada orde 1/N - dan melatih ulang pada seluruh agregat persis sama dengan Follow-The-Leader. Learner no-regret mana pun yang lain juga bisa dipakai: analisisnya adalah sebuah reduksi, bukan sifat khusus dari satu optimizer tertentu.

Satu lema menjembatani kesenjangan antara policy campuran yang mengumpulkan data dengan policy hasil pembelajaran yang akan di-deploy: Lema 4.1 membatasi jarak L1 antara kedua distribusi state tersebut dengan 2 T beta_i. Inilah sebabnya beta harus meluruh - selama expert masih memegang otoritas kontrol yang cukup besar, state yang Anda kumpulkan bukanlah state yang akan dihasilkan oleh policy Anda. Gabungkan lema ini dengan batas regret, dan hasil utamanya pun mengikuti: setelah kira-kira T iterasi, ada policy dalam urutan tersebut yang surrogate loss-nya berdasarkan distribusinya sendiri berada dalam O(1/T) dari epsilon_N. Masukkan itu ke dalam batas linear dan Anda sampai pada Teorema 3.2.

Dari sisi empiris, hasilnya sederhana bila diukur dengan standar sekarang. Pada Super Tux Kart, baseline supervised tidak menunjukkan perbaikan pada rata-rata jumlah jatuh per lap seiring bertambahnya data, DAgger mencapai policy yang tidak pernah keluar jalur setelah lima belas iterasi, dan SMILe setelah dua puluh iterasi masih jatuh sekitar dua kali per lap. Pada benchmark tulisan tangan, akurasi karakter berada di 82 persen tanpa struktur, 83,6 persen dengan supervised, dan 85,5 persen dengan DAgger. Tak satu pun dari hasil-hasil ini adalah hasil manipulasi robot.

Apa yang tidak dijanjikan oleh bukti ini

Pernyataan-pernyataan teorema ini bersifat kondisional, dan kondisi-kondisi tersebut sangat menentukan.

Ada satu hasil lain yang sering dikutip seolah-olah membantah semua ini, padahal bukan. Rajaraman, Yang, Jiao, dan Ramachandran mempelajari batas minimax dari imitation learning pada MDP episodik dengan ruang state S yang terhingga dan horizon H, dan membuktikan batas bawah suboptimalitas pada orde |S| H kuadrat dibagi N, yang berlaku bahkan ketika learner boleh secara aktif bertanya kepada expert pada state yang dikunjungi. Itu adalah laju worst-case pada suatu kelas MDP dengan anggaran episode yang tetap, dan yang disingkirkannya adalah gagasan bahwa interaksi memperbaiki laju minimax; teorema DAgger adalah pernyataan yang berbeda, yang membatasi policy yang di-deploy relatif terhadap apa yang bisa dicapai oleh kelas policy-nya sendiri.

Swamy, Choudhury, Bagnell, dan Wu kemudian mengklasifikasikan algoritma-algoritma ini berdasarkan momen perilaku expert mana yang mereka cocokkan, dan memperkenalkan konsep moment recoverability yang menggambarkan seberapa baik setiap keluarga algoritma meredam compounding error. Survei oleh Osa dan oleh Celemin membahas lanskap algoritmanya serta antarmuka umpan balik manusia (human-feedback).

Tagihannya: memberi label pada state yang tidak pernah dihasilkan oleh expert

Semua yang dijelaskan di atas mengasumsikan expert yang bisa ditanya di mana saja. Dalam simulasi dengan planner, biayanya nyaris gratis - eksperimen Mario menggunakan planner near-optimal dengan akses penuh ke state permainan. Dengan manusia pada robot, ini menjadi biaya yang dominan, dan biaya yang aneh pula: manusia harus menghasilkan aksi yang benar dalam konfigurasi yang kompetensinya sendiri tidak akan pernah menciptakannya.

Kelly, Sidrane, Driggs-Campbell, dan Kochenderfer menyampaikan keberatan ini secara langsung dalam paper HG-DAgger. DAgger versi vanilla mengharuskan expert memberikan label aksi padahal ia tidak sepenuhnya memegang kendali atas sistem. Ini mengurangi keamanan, dan dengan expert manusia hal ini cenderung menurunkan kualitas label yang terkumpul, yang mereka kaitkan dengan persepsi lag pada aktuator. Label yang Anda dapatkan kembali bukanlah label yang diasumsikan oleh algoritmanya.

Laskey dan rekan-rekannya menyerang masalah ini dari sisi lain dengan DART, dan kerangka mereka blak-blakan: teknik on-policy melelahkan bagi supervisor manusia, menambah beban komputasi, dan bisa mengunjungi state yang berbahaya selama pelatihan. Alternatif mereka menyuntikkan noise yang dikalibrasi ke dalam demonstrasi supervisor sendiri, sehingga pemulihan ikut terdemonstrasikan tanpa robot pernah menjalankan policy yang belum teruji. Pada MuJoCo Humanoid mereka melaporkan DART menurunkan cumulative reward supervisor sebesar 5 persen selama pelatihan, sementara DAgger menjalankan policy dengan cumulative reward 80 persen lebih rendah daripada supervisor; pada tugas grasping di tengah clutter dengan Toyota HSR, terjadi peningkatan rata-rata 62 persen dibanding behavior cloning.

SafeDAgger dari Zhang dan Cho memperlakukan query ke reference policy sebagai sumber daya yang langka: sebuah safety policy terpisah memprediksi, tanpa perlu bertanya, apakah primary policy akan menyimpang dari reference melebihi ambang batas tertentu, dan hanya state semacam itu yang diserahkan untuk diberi label. Ketiganya bereaksi terhadap fakta yang sama - analisis DAgger tidak membebankan biaya apa pun untuk label expert, sedangkan dunia nyata membebankan biaya yang sangat besar.

Apa artinya ini untuk SO-100 di meja Anda

Terjemahkan horizon ke dalam satuan Anda sendiri. Episode dua puluh detik pada 30 frame per detik berarti 600 langkah keputusan, dan T pada setiap batas di atas adalah angka itu. Pada T = 600, perbedaan antara suku yang berskala dengan T dan yang berskala dengan T kuadrat adalah perbedaan antara policy yang bisa pulih dari pendekatan yang buruk dan yang tidak bisa.

Inilah salah satu alasan mengapa action chunking membantu: ketika sebuah policy mengeluarkan urutan aksi yang pendek per langkah inferensi, jumlah titik keputusan berkurang, begitu pula jumlah kesempatan untuk terjadinya compounding error. Zhao, Kumar, Levine, dan Finn menyebut compounding error sebagai motivasi di balik Action Chunking with Transformers, dan melaporkan tingkat keberhasilan 80 hingga 90 persen pada enam tugas dunia nyata yang sulit, pada hardware bimanual berbiaya rendah, hanya dari sepuluh menit demonstrasi. Chunking tidak menghilangkan covariate shift - state-nya tetap milik policy itu sendiri - tetapi ia memperpendek horizon efektifnya. Lihat action chunking dan panduan imitation learning untuk SO-100.

Terjemahan kedua adalah metrik kemajuannya. Anda tidak bisa mengukur epsilon berdasarkan distribusi milik policy itu sendiri secara langsung - itu membutuhkan aksi expert ground-truth untuk setiap state yang dikunjungi, yaitu justru hal yang sedang Anda hindari untuk dihasilkan. Yang diberikan oleh loop human-gated sebagai gantinya adalah intervention rate: proporsi frame dalam satu run di mana manusia sedang mengambil alih. Ini adalah proksi, dan nilainya bisa berubah karena alasan yang tidak berhubungan dengan policy-nya - operator yang sabar melakukan intervensi lebih sedikit. Jika digunakan secara konsisten, inilah satu-satunya angka yang bisa mengatakan apakah satu ronde sepadan dengan waktu satu sore yang dihabiskan untuknya.

Terjemahan ketiga adalah peringatan soal kualitas data yang tidak dicakup oleh analisis teoretisnya. Mandlekar dan rekan-rekannya mempelajari enam algoritma offline learning pada lima tugas manipulasi multi-tahap hasil simulasi dan tiga di dunia nyata, dan melaporkan adanya sensitivitas terhadap pilihan desain algoritma, ketergantungan pada kualitas demonstrasi, dan variabilitas yang disebabkan oleh stopping criterion. Belkhale, Cui, dan Sadigh berargumen bahwa kualitas dataset seharusnya diformalkan melalui action divergence dan transition diversity, dan mencatat bahwa diversitas state tidak selalu menguntungkan. Satu ronde DAgger menambahkan state yang tidak sengaja dipilih siapa pun: sebagian adalah data recovery yang Anda butuhkan, sebagian lagi adalah robot yang bergerak liar sementara Anda meraba-raba mencari kontrol takeover.

Secara mekanis, satu ronde terdiri dari enam langkah: jalankan inferensi dengan perekaman aktif, ambil alih ketika policy berperilaku buruk, tinjau run tersebut dan arsipkan setiap episode, sinkronkan koreksinya, susun dataset campuran dari data asli ditambah koreksi dengan pemilihan episode yang dilakukan secara eksplisit per sumber, lalu lanjutkan pelatihan dari checkpoint sebelumnya, bukan dari model dasar. Di ay-robots, langkah-langkah tersebut sudah tersedia sebagai tombol, yang menghilangkan urusan pemipaan teknis tetapi tidak menghilangkan kebutuhan akan penilaian Anda sendiri. Dua catatan penting: melanjutkan dari sebuah checkpoint hanya menginisialisasi bobot dan bukan resume optimizer, dan langkah penyelarasan leader arm masih minim pengujian pada hardware. Lihat training dan datasets.

Pohon keluarga algoritmanya, dalam satu tabel

Pertanyaan yang sering diajukan

Langkah selanjutnya

Jika Anda belum melatih policy sama sekali, teori ini masih terlalu dini untuk diterapkan: rekam dataset terlebih dahulu, mulai dari melatih policy pertama Anda dan desktop client. Jika Anda sedang menimbang antara menambah seratus demonstrasi bersih lagi atau mulai melakukan koreksi: demonstrasi bersih tidak memperbaiki masalah distribusi. Untuk mekanismenya, lanjutkan dengan varian human-gated lalu kemudian walkthrough SO-100.