DAgger: почему Behavior Cloning смещается и что на самом деле доказывает агрегация набора данных

Есть одна конкретная ошибка, которую рано или поздно встречает каждый, кто обучает политику манипуляции. Политика тянется к кубу, подходит на два сантиметра, колеблется, смещается в сторону, затем делает что-то не связанное с задачей. Валидационная потеря была нормальной. Проигрывание в открытом цикле против отложенных эпизодов было нормальным. И всё же рука оказывается в позе, которой вообще нет в обучающих данных, и оттуда ей нечего разумное сказать.

Эта ошибка имеет название и установившуюся теорию. Это первая из четырёх статей о DAgger, и она охватывает сам аргумент: почему подгонка политики на собственные траектории демонстратора производит ошибку, которая может расти с квадратом длины эпизода, что меняет агрегация данных, и что не обещает доказательство без сожаления. Цикл на реальном оборудовании рассматривается в запуске цикла DAgger на SO-100, вариант с человеческой логикой в HG-DAgger и вмешательства с человеческой логикой, и вопрос измерения в измерении цикла DAgger.

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

Набор данных демонстрации - это куча пар наблюдение-действие. Behavior cloning подгоняет функцию к этой куче с обычным контролируемым обучением и останавливается на этом. Это самая старая идея в этой области. ALVINN Померлё в 1988 году была трёхслойной сетью обратного распространения, которая принимала изображения с камеры и лазерного дальномера и выдавала направление, в котором должно двигаться транспортное средство; она обучалась на имитационных дорожных изображениях и следовала реальным дорогам в некоторых полевых условиях. Рецепт не сильно изменился; сети изменились.

То, что пропускается, - это проверка того, откуда эти пары. Каждая из них лежит на траектории, которую произвёл демонстратор. Политика, которую вы развёртываете, производит своё собственное. В момент отклонения она запрашивается о состояниях, которых нет в распределении обучения, и её ответ отводит её ещё дальше. Росс, Гордон и Бакнелл открывают статью DAgger именно с этого: последовательное предсказание нарушает допущение i.i.d. под статистическим обучением, потому что собственные предсказания учащегося определяют входы, которые он видит дальше.

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

Замените Марио на робот SO-100 и структура одинакова. Ваши демонстрации показывают чистый подход и чистий захват, а не схватывание закрывающегося на два сантиметра короче - так что политика не имеет понятия, что делать оттуда, и всё, что она угадывает, отводит её ещё дальше. Смещение ковариат - это свойство процедуры сбора данных, а не архитектуры сети.

Откуда берётся квадратичный член

Статья AISTATS 2010 года Росса и Бакнелла, Efficient Reductions for Imitation Learning, уточняет совокупление. Пусть T - горизонт задачи, пусть стоимость задачи ограничена единичным интервалом, и пусть epsilon - суррогатная потеря, измеренная под распределением состояний эксперта - число, о котором сообщает ваш набор валидации. Тогда дополнительная стоимость запуска этой политики в течение T шагов, относительно эксперта, ограничена T в квадрате, умноженным на epsilon. Росс, Гордон и Бакнелл переформулировали это как Теорему 2.1 в статье DAgger и добавили важное предложение: граница является жёсткой. Существуют проблемы, где политика с потерей epsilon на распределении эксперта действительно несёт дополнительные затраты, растущие квадратично по T.

Жёсткий не означает типичный. Квадратичный член - это наихудший случай по классу задач, а не прогноз о вашей задаче захвата и укладки. Это устанавливает, что больше демонстраций эксперта не может устранить проблему: это только уточняет оценку epsilon на распределении, на котором политика не будет испытана.

Путь выхода находится в той же статье, переформулированный как Теорема 2.2. Если политика достигает потери epsilon под собственным распределением состояний, и одно неправильное действие стоит максимум u в стоимости достижения цели под экспертом, то дополнительная стоимость ограничена u, умноженным на T, умноженным на epsilon - линейна по горизонту. Константа u - это интересная величина: максимум 1 для расхождения 0-1 с экспертом, и O(1), когда эксперт может восстановиться за несколько шагов. В наихудшем случае это O(T), и линейная граница тогда не лучше квадратичной.

Две попытки, предшествовавшие DAgger

Прямое обучение - честный, но непрактичный ответ. Обучите отдельную политику для каждого временного шага по порядку, каждая на распределении состояний, вызванном политиками, уже зафиксированными для более ранних шагов, поэтому каждая политика видит ровно то распределение, с которым она столкнётся. Подвох в описании: T политик, обучаемых последовательно, без ранней остановки. Для манипуляции эпизод при 30 кадрах в секунду T находится в сотнях.

SMILe из той же статьи и SEARN из работы Доме, Лэнгфорда и Марку по структурированному предсказанию идут другим путём: одна стационарная политика, но стохастическая. Каждая итерация обучает компонент и добавляет его в смесь, смещая вероятностную массу от эксперта. Результат - смесь, в которой некоторые компоненты хуже других - на физической руке, контроллер, который может выбрать плохой компонент в середине движения. Это заявленная мотивация для желания стационарной детерминированной политики вместо этого.

DAgger: одна идея, один бокс

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

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

Три детали имеют больший вес, чем кажется. Метки предназначены для состояний, посещаемых смешанной политикой, но действия поступают от эксперта - политика предоставляет вопросы, эксперт ответы. Переучение проводится на всём совокупном наборе, что делает каждый раунд шагом Следовать-за-Лидером: на раунде n вы выбираете лучшую политику в ретроспективе по каждой траектории до сих пор. Это фреймирование - то, на чём висит доказательство. И алгоритм заканчивается возвращением лучшей политики в последовательности, выбранной на наборе валидации, потому что теоремы гарантируют, что некоторая политика в последовательности хороша, а не что последняя хороша.

Бета-расписание и почему оно не является ручкой регулировки

Смешанная политика - это beta_i, умноженное на эксперта, плюс один минус beta_i, умноженное на учащегося. Смысл практический: первые несколько изученных политик обучаются на очень небольшом количестве данных, допускают много ошибок и в противном случае потратили бы раунд в состояниях, которые становятся нерелевантными, как только политика улучшается.

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

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

Гарантия: сведение к онлайн-обучению без сожаления

Вот движение, которое делает статью тем, чем она является. Рассматривайте каждый раунд DAgger как один пример в онлайн-задаче обучения, где потеря на раунде i - это суррогатная потеря под распределением состояний политики, использованной на раунде i. Учащийся обязуется политикой перед тем, как увидеть эту потерю, и последовательность нестационарна, потому что зависит от произведённых до сих пор политик.

Алгоритм не имеет сожалений, если его средняя потеря по N раундам приближается к лучшей единственной политике в ретроспективе. Следовать-за-Лидером на сильно выпуклых потерях - это такой алгоритм, со средним сожалением, уменьшающимся порядка 1/N - и переучение на всём совокупном наборе именно это и есть Следовать-за-Лидером. Любой другой алгоритм без сожалений послужил бы так же: анализ - это сведение, а не свойство одного оптимизатора.

Одна лемма преодолевает разрыв между смешанной политикой, собравшей данные, и изученной политикой, которая будет развёрнута: Лемма 4.1 ограничивает расстояние L1 между их распределениями состояний 2 T beta_i. Это причина, по которой бета должны распадаться - пока эксперт ещё держит заметный орган управления, состояния, которые вы собираете, - это не те состояния, которые произведёт ваша политика. Объедините лемму с границей сожаления и главный результат следует: после примерно T итераций некоторая политика в последовательности имеет суррогатную потерю под своим распределением в пределах O(1/T) от epsilon_N. Подкормите это линейной границей и вы приземлитесь в Теореме 3.2.

Эмпирическая сторона скромна по нынешним стандартам. В Super Tux Kart контролируемый базовый уровень не улучшил свой средний падений на круг по мере поступления большего количества данных, DAgger достиг политики, которая никогда не упала со трека после пятнадцати итераций, и SMILe после двадцати всё ещё падал примерно дважды на круг. На контрольном тесте почерка точность символов была 82% без структуры, 83,6% контролируемая, 85,5% с DAgger. Ничего из этого - это результат манипуляции.

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

Утверждения теорем условны, и условия нагружены.

Один дальнейший результат часто цитируется как опровержение и не является таковым. Раджараман, Ян, Цяо и Рамачандран изучают минимаксные пределы обучения имитацией в эпизодических МДП с конечным пространством состояний S и горизонтом H, и доказывают нижнюю границу субоптимальности порядка |S| H в квадрате по N, которая удерживает даже когда учащийся может активно запрашивать эксперта в посещённых состояниях. Это наихудший темп по классу МДП при фиксированном бюджете эпизода, и что это исключает, - это идея, что взаимодействие улучшает минимаксный темп; теорема DAgger - это другое утверждение, ограничивающее развёрнутую политику относительно того, что её собственный класс политик может достичь.

Свами, Чоудхури, Бакнелл и Ву позже классифицировали эти алгоритмы по тому, какие моменты поведения эксперта они согласуют, и представили понятие восстанавливаемости момента, которое ограничивает, насколько хорошо каждое семейство смягчает совокупную ошибку. Обзоры Осы и Целемина охватывают алгоритмический ландшафт и интерфейсы человеческой обратной связи.

Счёт: маркировка состояний, которые эксперт никогда не произвёл

Всё вышеуказанное предполагает эксперта, который может быть запрошен где угодно. В имитации с плани­ровщиком, который почти бесплатен - эксперименты Марио использовали почти оптимального планировщика с полным доступом к состоянию игры. С человеком на роботе это доминирующая стоимость, и причудливая: человек должен выдать правильное действие в конфигурации, которую его собственная компетентность никогда не создала.

Келли, Сидран, Дриггс-Кэмпбелл и Кохендерфер прямо формулируют возражение в статье HG-DAgger. Ванилла DAgger требует от эксперта предоставить метки действий, не полностью контролируя систему. Это снижает безопасность, и с человеческими экспертами это вероятно снизит качество собранных меток, что они относят к ощущаемой задержке акуатора. Метка, которую вы получаете, не та, которую алгоритм предположил.

Ласкей и коллеги атакуют проблему с другой стороны с DART, и их фреймирование откровенно: методы на политике утомительны для человеческих руководителей, добавляют вычислительное бремя и могут посещать опасные состояния во время обучения. Их альтернатива вводит калиброванный шум в собственные демонстрации руководителя, так что восстановление демонстрируется, не требуя от робота запуска недоверительной политики. На MuJoCo Humanoid они сообщают, что DART снижает совокупное вознаграждение руководителя на 5% во время обучения, в то время как DAgger выполняет политики с совокупным вознаграждением на 80% меньше, чем руководитель; на захвате в беспорядке с Toyota HSR среднее увеличение на 62%.

SafeDAgger Чжана и Чо рассматривает запросы к контрольной политике как редкий ресурс: отдельная контрольная политика безопасности предсказывает, без запроса, собирается ли основная политика отклониться от контрольной более порога, и только эти состояния передаются. Все три реагируют на один и тот же факт - анализ DAgger ничего не требует за метки эксперта, а реальность требует много.

Что это значит для SO-100 на вашем столе

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

Это отчасти причина, по которой помогает разбиение действий: когда политика выпускает короткую последовательность действий на шаг вывода, количество точек решения уменьшается, и так же количество шансов для совокупления. Чжао, Кумар, Левин и Финн называют совокупную ошибку мотивацией для Action Chunking with Transformers и сообщают 80-90% успеха на шести сложных задачах реального мира, на недорогом бимануальном оборудовании, из десяти минут демонстраций. Разбиение не удаляет смещение ковариат - состояния по-прежнему принадлежат политике - но оно сокращает эффективный горизонт. Смотрите разбиение действия и руководство по обучению имитацией SO-100.

Второй перевод - это метрика прогресса. Вы не можете измерить epsilon под собственным распределением политики напрямую - это требует действий эксперта по земле для каждого посещённого состояния, то, что вы пытаетесь избежать производства. Что вместо этого даёт вам человеческий цикл - это частота вмешательства: доля кадров в запуске, во время которых человек взял управление. Это прокси, и она движется по причинам, не связанным с политикой - терпеливый оператор вмешивается меньше. Используется последовательно, это единственное число, которое говорит вам, стоил ли раунд полдня.

Третий перевод - это предупреждение о качестве данных, которое анализ не охватывает. Мандлекар и коллеги изучали шесть автономных алгоритмов обучения на пяти имитационных и трёх реальных многоэтапных задачах манипуляции и сообщают о чувствительности к выборам алгоритма, зависимости от качества демонстраций и изменчивости, вызванной критерием остановки. Белхале, Цуй и Садиг спорят, что качество набора данных должно быть формализовано через расхождение действий и разнообразие переходов, и отмечают, что разнообразие состояний не всегда полезно. Раунд DAgger добавляет состояния, которые никто не выбирал намеренно: некоторые - это данные восстановления, которые вам нужны, некоторые - робот, пока вы барахтаетесь в поисках управления захватом.

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

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

Часто задаваемые вопросы

Куда идти дальше

Если вы ещё не обучали политику, эта теория преждевременна: сначала запишите набор данных, начиная с обучения первой политике и клиента для рабочего стола. Если вы взвешиваете ещё сто чистых демонстраций против начала коррекций: чистые демонстрации не исправляют проблему распределения. Для механики продолжайте с вариантом с человеческой логикой и затем пошаговым руководством SO-100.