DAgger обяснен: Защо Behavior Cloning отклонява и какво всъщност доказва Dataset Aggregation

Има конкретна грешка, която всеки, който обучава манипулационна политика, среща по-рано или по-късно. Политиката достига куба, приближава се до два сантиметра, колебае се, отклонява се встрани и след това прави нещо несвързано със задачата. Loss при валидация е бил добър. Open-loop replay срещу задържани епизоди е бил добър. И все пак ръката завършва в поза, която не се появява никъде в обучаващите данни, и оттам няма нищо разумно да каже.

Тази грешка има име и установена теория зад нея. Това е първата от четири статии относно DAgger, и тя покрива аргумента: защо вмъкване на политика на собствените траектории на демонстратора произвежда грешка, която може да расте с квадрата на дължината на епизода, какво променя dataset aggregation и какво не обещава доказателството за no-regret. Цикълът на истински хардуер е покрит в пускане на DAgger цикъл на SO-100, човешко-управляваният вариант в HG-DAgger и човешко-управлявани интервенции, и въпросът за измерването в измерване на DAgger цикъл.

Предположението behavior cloning мълчаливо прави

Демонстрационен набор данни е купчина двойки наблюдение-действие. Behavior cloning вмъква функция към тази купчина с обикновено надзорно обучение и спира там. Това е най-старата идея в областта. Померло ALVINN, през 1988 г., беше трислойна мрежа с обратно разпространение, която взимаше изображения от камера и лазерен скенер на разстояние и произвеждаше посока, в която превозното средство трябва да пътува; беше обучена на симулирани пътни изображения и следваше истински пътища при някои полски условия. Рецептата не се е променила много; мрежите има.

Това, което се пропуска, е проверка откъде идват тези двойки. Всеки един от тях лежи на траектория, която демонстраторът произведе. Политиката, която разгръщаш, произвежда своя собствена. В момента, когато се отклони, тя отговаря на въпроси относно състояния, които не са в разпределението на обучение, и нейният отговор я отдалечава още. Ross, Gordon и Bagnell отварят DAgger хартията с точно това: последователното предсказване нарушава i.i.d. предположението под статистическото обучение, тъй като собствените предсказания на обучаващия определят входовете, които вижда по-нататък.

Най-ясната илюстрация в тази хартия не е робот изобщо. Клониране на близо-оптимален планер за Super Mario Bros. произведе политика, която многократно се зацакляше срещу препятствие вместо да го преследи. Причината е целия аргумент в едно изречение: експертът винаги скачаше от удобно разстояние, затова датасетът не съдържаше никакво състояние, в което Mario е натиснат до препятствие, и затова нямаше етикет какво да направи след като се окажеш там.

Замени Mario със SO-100 ръка и структурата е идентична. Демонстрациите ти показват чист подход и чист хват, не захвата затворена два сантиметра накъсо - така че политиката няма идея какво да направи оттам, и както и да го отгатва, го отдалечава. Covariate shift е свойство на процедурата за събиране на данни, не на архитектурата на мрежата.

Откъде идва квадратичният член

Хартията от 2010 г. на AISTATS от Ross и Bagnell, Efficient Reductions for Imitation Learning, прави натрупването точно. Нека T е хоризонт на задачата, нека разход на задача е ограничен в единичния интервал, и нека epsilon е сурогатна загуба, измерена под разпределението на състояния на експерта - числото, което съобщава набор от валидация. Тогава допълнителен разход на пускане на тази политика за T стъпки, спрямо експерта, е ограничен от T квадрат по epsilon. Ross, Gordon и Bagnell преповтарят това като Theorem 2.1 в DAgger хартията и добавят изречението, което има значение: граница е плътна. Проблеми съществуват, при които политика с epsilon загуба на разпределението на експерта наистина понася допълнителен разход, растящ квадратично в T.

Плътната граница не означава типична. Квадратичният член е най-лошия случай над клас проблеми, не прогноза за вашата pick-and-place задача. Какво установява е, че повече експертна демонстрация не може да премахне проблема: само остря оценката на epsilon на разпределение, което политиката не ще бъде тестирана.

Маршрутът на бягство е в същата хартия, преформулиран като Theorem 2.2. Ако политика постига загуба epsilon под своя собствено разпределение на състояния, и едно неправилно действие струва най-много u в разход-до-цел под експерта, допълнителният разход е ограничен от u по T по epsilon - линейно на хоризонта. Константата u е интересното количество: най-много 1 за 0-1 неъгласие с експерта, и O(1) винаги, когато експертът може да възстанови в рамките на няколко стъпки. В най-лошия случай то е O(T), и линейната граница тогава не е по-добра от квадратичната.

Двете опита, които дойдоха преди DAgger

Forward training е честна но непрактична отговор. Обучи отделна политика за всеки timestep, по ред, всяка на разпределението на состояния, индуцирано от политиките вече фиксирани за по-ранни стъпки, така че всяка политика вижда точно разпределението, което ще срещне. Уловката е в описанието: T политики, обучени последователно, без ранна спирка. За манипулация епизод на 30 кадъра в секунда, T е в стотици.

SMILe, от същата хартия, и SEARN, от работата на Daume, Langford и Marcu по структурирано предсказване, вземат другия маршрут: една стационарна политика, но стохастична. Всяка итерация обучава компонент и го добавя към смес, преместване вероятност маса далеч от експерта. Резултатът е смес, в която някои компоненти са по-лошо от други - на физическа ръка, контролер, който може да вземе лоша компонента в средата на движение. Това е декларираната мотивация за желание на стационарна детерминирана политика вместо.

DAgger: една идея, един box

Dataset Aggregation пази детерминирана политика и премества поправката в събиране на данни. Всеки кръг: разгърни сегашната политика, запиши состояния, които посещава, попроси експерта какво би bilo правилното действие в всяко, добави тези двойки към датасета, който вече имаш, преобучи на един. Името е алгоритъма - агрегираш, никога не отхвърляш.

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

Три детайла носят повече тегло, отколкото изглеждат. Етикетите са за состояния, посетени от смесена политика, но действията идват от експерта - политиката дава въпросите, експертът отговорите. Преобучаването е на цялата съвкупност, което прави всеки кръг Follow-The-Leader стъпка: на кръг n избираш най-добра политика в анализ над всяка траектория досега. Тази рамка е това на което доказателството се основава. И алгоритъма завършва, връщайки най-добра политика в последователност, както избрана на набор за валидация, тъй като теоремите гарантират, че някои политика в последователност е добра, не че последния е.

Beta schedule и защо не е tunning knob

Смесена политика е beta_i по експерт плюс един минус beta_i по обучител. Точката е практична: първите няколко научени политики са обучени на много малко данни, правят много грешки, и иначе биха прекарали разгръщане в состояния, които станат неуместни след като политиката се подобри.

Теорията налага точно един условие: текущ средна на betasи трябва да отиде до нула. Анализ работи с beta_i ограничена от (1 - alpha) до мощност i-1, за константа alpha независима от T.

Пролуката между 2980 и 3030 на скала, която работи към приблизително 4300, е малка, но обяснението на хартията за нея е най-полезната практична забележка в раздела. С параметър-свободна разписание, Mario се зацакля в същото място рано и произведе маса близо-дублирани данни от този един локатор; позволяване на експерт да управлява дял от времето и открива го и разширява разнообразието на состояния. Разписанието е по-малко за съотношението на смешване отколкото дали събиране на данни продължава да произвежда нови состояния или същия отказ.

Гарантията: намаляване на no-regret online learning

Ево ходът, който прави хартията какво е. Третирай всеки DAgger кръг като един пример в online learning проблем, където загуба на кръг i е сурогатна загуба под разпределението на состояния на политика използвана при кръг i. Обучител се поставя на политика преди видене на загуба, и последователност не е стационарна, защото зависи на политиките произведени досега.

Алгоритъм е no-regret ако него среден загуба над N кръгове приближава на най-добра единична политика в анализ. Follow-The-Leader на силно изпъкнали загуби е такъв алгоритъм, със средна раскаяние свиване на ред на 1/N - и преобучаване на пълна съвкупност е точно Follow-The-Leader. Всеки друг no-regret обучител би служил също: анализ е намаляване, не свойство на един оптимизатор.

Един лема мосты пролуката между смесена политика, която събра данни и научена политика, която ще бъде развернута: Lemma 4.1 ограничава L1 разстояние между техни разпределения на состояния от 2 T beta_i. Това е защо betasи трябва да намалеят - докато експертът все още държи преценяща контролна орган, состояния събирате не са състояния политиката ще произведе. Комбинирай лема с regret ограничение и главен резултат следва: след приблизително T итерации, някои политика в последователност има сурогатна загуба под своя собствено разпределение в O(1/T) на epsilon_N. Хранене, че в линейно ограничение и достигаш Theorem 3.2.

Емпиричната страна е скромна по текущи стандарти. В Super Tux Kart надзорния baseline не подобри неговия средна падане по кръг, тъй като повече данни пристига, DAgger достигнала политика, която никога падна разваляне на пътека след петнадесет итерации, и SMILe след двадесет все още падна приблизително два пъти на кръг. На ръкописната бенчмарк, точност символ работа 82 процента без структура, 83.6 процента надзорни, 85.5 процента със DAgger. Нито един от тези е резултат манипулация.

Какво доказателството не обещава

Теоремата államatok са условни, и условията са товар-носене.

Един допълнителен резултат често цитиран като опровержение и не е един. Rajaraman, Yang, Jiao и Ramachandran учат minimax ограничение на imitation learning в епизодно MDPs с крайни state space S и хоризонт H, и доказват suboptimality долна граница на ред на |S| H квадрат над N, което държи дори когато обучител може активно запита експерта при посетени состояния. Това е най-лошия случай процент над клас на MDPs в крайния епизод бюджет, и какво го изключи е идея, че взаимодействие подобря minimax процент; DAgger теорема е различно твърдение, ограничаване развърнати политика спрямо какво собствено политика класа може достичне.

Swamy, Choudhury, Bagnell и Wu по-късно класифицира тези алгоритми по кои моменти на експертно поведение те съответстват, и се въвеждам понятие на moment recoverability че разграничава как добре всяка семейство смекчава натрупване на грешка. Обобщенията от Osa и от Celemin покриват алгоритмично ландшафта и човешко-обратни взаимодействия.

Сметката: етикетиране на состояния експертът никога производителност

Всичко по-горе предполага експерт, който може да бъде пита навсякъде. В симулация със планер, което е почти безплатно - Mario експерименти използвана близо-оптимален планер с пълен достъп до игра състояние. С човек на робот това е преобладаващия разход, и странен един: човек трябва да произведе правилно действие в конфигурация собствено компетенция никога би бил произвел.

Kelly, Sidrane, Driggs-Campbell и Kochenderfer направи възражение директно в HG-DAgger хартията. Ванила DAgger поискай експертът да достави действие етикети докато не пълен контрол на система. Това намалява безопасност, и със човешки експерти вероятно е да деградира качество събран етикети, което те дават до възприето actuator забавяне. Етикет получаш назад е не етикет алгоритъм предполага.

Laskey и колеги атакуват проблем от другия страна със DART, и техния рамка е тъп: on-policy техники са досаден за човешки надзорници, добави изчислителен товар, и може посетят опасни състояния докато обучение. Техния алтернатив вкарва калибриран шум в надзорник собствено демонстрации, така че възстановяване попълнена без робот когато пътува недоверено политика. На MuJoCo Humanoid те съобщавам DART намаляване надзорник совкупност награда от 5 процента докато обучение, докато DAgger изпълнява политики със 80 процента по-малко совкупност награда отколкото надзорник; на хватане в смут със Toyota HSR, средно 62 процента увеличение над behavior cloning.

Zhang и Cho SafeDAgger третира запита за референсна политика като редкия ресурс: отделен безопасност политика предсказва, без запит, дали главния политика ще отклони от референс над праг, и само тези състояния са предадени. Всички три реакция също факт - DAgger анализ зарежда нищо за експертни етикети, и реалност зарежда много.

Какво това значи за SO-100 на вашия писал

Преводи хоризонт в вашия собствено единици. Двадесет-втори епизод на 30 кадъра във втория е 600 решение стъпки, и T в всеки ограничение по-горе е че число. На T = 600, разлика между термин скала със T и един скала със T квадрат е разлика между политика че възстановяване от лоша подход и един че няма.

Това е частично защо действие семена помага: когато политика произвежда кръ последователност на действия на inference стъпка, число на решение точки капки, и така връзка число от шансове на compound. Zhao, Kumar, Levine и Finn назовете натрупване на грешка като мотивация за Action Chunking със Transformers, и съобщавам 80 до 90 процента успех на шест трудни истински-свят задачи, на нисък разход бимануална хардуер, от десет минути стойност на демонстрации. Семена няма премахване covariate shift - състояния са все още политиката собствено - но съкъсто ефективен хоризонт. Вижте действие семена и SO-100 imitation learning водач.

Втория превод е прогреса метрика. Не можеш мерка epsilon под политиката собствено разпределение директно - че нужди земя-истина експертни действия за всеки посетени състояние, че нещо опитваш да избегна произвеждане. Какво човешко-управлявана цикъл дава вместо е интервенционен процент: дял на кадъра в бяжащ по време на които човек беше взел над. Това е прокси, и го движи за причини несвързано със политика - пациент оператор интервенира по-малко. Използва последователно, това е един число че казва дали кръг беше стойност на обяд.

Трети превод е качество-данни предупреждение анализ няма покритие. Mandlekar и колеги учен шест оффлайн обучение алгоритми на пет симулирани и три истински-свят мулти-етап манипулация задачи, и съобщавам чувствителност на алгоритмично дизайн избори, зависимост на качество на демонстрации, и вариабилност причинено от спиране критерий. Belkhale, Cui и Sadigh твърдят че датасет качество трябва да е формализирани чрез действие дивергенция и преход разнообразие, и отбелязват че състояние разнообразие не е винаги полезно. DAgger кръг добави състояния никой избра умишлено: някои са възстановяване данни нужди, някои са робот трепа докато те грабват за takeover управление.

Механично кръг е шест стъпки: работа умозаключение със запис на, вземанието пончик политика неправилно повада, преглед на бяжащ и файл всеки епизод, sync на коррекции, съставляват смесена датасет от оригинали плюс корекции със епизод избор направи явно за источник, и продължи обучение от предходен контролна точка по-скоро отколкото база модел. На ay-robots че стъпки съществуват като бутони, които премахва тръбопровода но не на преценката. Две предупреждения: продължи от контролна точка инициализира тегла и не е оптимизатор възобновяване, и лидер-ръка подравняване преместване е все още светлина тестиран на хардуер. Виж обучение и датасети.

Семейство дърво, в един таблица

Често зададени въпроси

Където отиди от тук

Ако не си обучена политика все още, че теория е преждевременна: запиши датасет първо, стартирам от обучение на първо политика и лапто клиент. Ако взвешиш други сто чисти демонстрации срещу стартирам корекции: чисти демонстрации няма поправи разпределение проблем. За механика, продължи със човешко-управлявана вариант и тогава SO-100 разходка чрез.