Сравнение методов обучения с подкреплением, основанных на моделях, и без них в динамическом сеточном мире
Делиться
В последнее время алгоритмы обучения с подкреплением (RL) получили большую популярность благодаря решению таких исследовательских задач, как сворачивание белков , достижение сверхчеловеческого уровня в гонках дронов или даже интеграция человеческой обратной связи в ваши любимые чат-боты.
Действительно, RL предлагает эффективные решения для множества задач последовательного принятия решений. Методы обучения на основе временных разностей (TD-обучения) являются популярным подмножеством алгоритмов RL. Методы TD-обучения сочетают ключевые аспекты методов Монте-Карло и динамического программирования для ускорения обучения без необходимости использования идеальной модели динамики окружающей среды.
В этой статье мы сравним различные типы алгоритмов TD в пользовательском Grid-мире. В плане эксперимента будет подчеркнута важность непрерывного исследования , а также индивидуальные характеристики тестируемых алгоритмов: Q-learning , Dyna-Q и Dyna-Q +.
План этого поста содержит:
- Описание окружающей среды
- Обучение на основе временных различий (TD)
- Методы TD без моделей (Q-learning) и методы TD на основе моделей (Dyna-Q и Dyna-Q+)
- Параметры
- Сравнение производительности
- Заключение
Полный код, позволяющий воспроизвести результаты и графики, доступен здесь: https://github.com/RPegoud/Temporal-Difference-learning
Окружающая среда
Среда, которую мы будем использовать в этом эксперименте, представляет собой сетчатый мир со следующими характеристиками:
- Сетка имеет размер 12 на 8 ячеек.
- Агент стартует в левом нижнем углу сетки, цель — добраться до сокровища, расположенного в правом верхнем углу (конечное состояние с наградой 1).
- Синие порталы соединены, проход через портал, расположенный на клетке (10, 6), ведёт в клетку (11, 0) . После первого перехода агент не может повторно пройти через портал.
- Фиолетовый портал появляется только после 100 эпизодов, но позволяет агенту быстрее добраться до сокровищ. Это стимулирует постоянное исследование окружающего мира.
- Красные порталы — это ловушки (конечные состояния с наградой 0), они завершают эпизод.
- Столкновение со стеной заставляет агента остаться в том же состоянии.
Целью данного эксперимента является сравнение поведения агентов Q-learning, Dyna-Q и Dyna-Q+ в изменяющейся среде . Действительно, после 100 эпизодов оптимальная политика неизбежно изменится, а оптимальное количество шагов в успешном эпизоде уменьшится с 17 до 12 .
Введение в изучение временных различий:
Метод временной разницы представляет собой комбинацию методов Монте-Карло (МК) и динамического программирования (ДП):
- Как и методы МК, методы ТД позволяют учиться на опыте , не требуя модели динамики окружающей среды .
- Как и методы DP, методы TD обновляют оценки после каждого шага на основе других изученных оценок, не дожидаясь результата (это называется самонастройкой).
Одной из особенностей методов TD является то, что они обновляют оценку своего значения на каждом шаге времени , в отличие от методов MC, которые ждут конца эпизода.
Действительно, оба метода имеют разные цели обновления . Методы MC нацелены на обновление возвращаемого значения Gt , которое доступно только в конце эпизода. Вместо этого методы TD нацелены на:
Где V — оценка истинной функции значения Vπ .
Таким образом, методы TD объединяют выборку MC (путем использования оценки истинного значения) и бутстреппинг DP (путем обновления V на основе оценок, опирающихся на дальнейшие оценки).
Простейшая версия обучения на основе временной разницы называется TD(0) или одношаговым TD, практическая реализация TD(0) будет выглядеть следующим образом:
При переходе из состояния S в новое состояние S' алгоритм TD(0) вычисляет резервное значение и соответствующим образом обновляет V(S) . Это резервное значение называется ошибкой TD и представляет собой разницу между наблюдаемым вознаграждением R и дисконтированным значением нового состояния γV(St+1) и текущей оценкой значения V(S) :
В заключение следует отметить, что методы ТД обладают рядом преимуществ:
- Им не требуется идеальная модель динамики окружающей среды.
- Они реализуются в режиме онлайн, обновляя цель после каждого временного шага.
- TD(0) гарантированно сходится для любой фиксированной политики π, если α (скорость обучения или размер шага) следует условиям стохастической аппроксимации (для более подробной информации см. стр. 55 «Отслеживание нестационарной проблемы» в [4])
Подробности реализации:
В следующих разделах рассматриваются основные характеристики и производительность нескольких алгоритмов TD в мире сеток.
Для простоты во всех моделях использовались одни и те же параметры:
- Эпсилон ( ε) = 0,1: вероятность выбора случайного действия в ε-жадных политиках
- Гамма ( γ) = 0,9: коэффициент дисконтирования, применяемый к будущим вознаграждениям или оценкам стоимости
- Aplha (α) = 0,25: скорость обучения, ограничивающая обновления значений Q
- Шаги планирования = 100: для Dyna-Q и Dyna-Q+ количество шагов планирования, выполненных для каждого прямого взаимодействия
- Каппа ( κ ) = 0,001: для Dyna-Q+, вес бонусных вознаграждений, применяемых на этапах планирования
Производительность каждого алгоритма сначала представлена для одного запуска из 400 эпизодов (разделы: Q-learning , Dyna-Q и Dyna-Q+ ), а затем усреднена по 100 запускам из 250 эпизодов в разделе « Обзор и сравнение алгоритмов ».
Q-обучение
Первый алгоритм, который мы здесь реализуем, — это знаменитое Q-обучение (Уоткинс, 1989):
Q-обучение называется алгоритмом вне политики, поскольку его цель — приблизиться к оптимальной функции значения напрямую, а не к функции значения π, политике, которой следует агент.
На практике Q-обучение по-прежнему опирается на политику, часто называемую «политикой поведения», для выбора пар «состояние-действие», которые следует посетить и обновить. Однако Q-обучение не основано на политике, поскольку обновляет свои Q-значения на основе наилучшей оценки будущих вознаграждений , независимо от того, следуют ли выбранные действия текущей политике π.
По сравнению с предыдущим псевдокодом обучения TD есть три основных отличия:
- Нам нужно инициализировать функцию Q для всех состояний и действий, а Q(terminal) должен быть равен 0.
- Действия выбираются из политики, основанной на значениях Q (например, ϵ-жадная политика в отношении значений Q)
- Обновление нацелено на функцию значения действия Q, а не на функцию значения состояния V.
Теперь, когда у нас есть первые данные алгоритма для тестирования, мы можем начать фазу обучения. Наш агент будет перемещаться по Grid World, используя свою ε-жадную политику в отношении значений Q. Эта политика выбирает действие с наибольшим значением Q с вероятностью (1 – ε) и выбирает случайное действие с вероятностью ε . После каждого действия агент будет обновлять свои оценки значений Q.
Мы можем визуализировать динамику оценочной максимальной ценности действия Q(S, a) каждой ячейки Grid World с помощью тепловой карты. Здесь агент воспроизводит 400 эпизодов. Поскольку на эпизод приходится только одно обновление, динамика значений Q довольно медленная, и значительная часть состояний остаётся неотображённой:
После завершения 400 эпизодов анализ общего количества посещений каждой ячейки позволяет нам получить достоверную оценку среднего маршрута агента. Как показано на правом графике ниже, агент, по-видимому, сошелся на неоптимальном маршруте , избегая ячейки (4,4) и последовательно следуя вдоль нижней стенки .
В результате этой неоптимальной стратегии агент достигает минимум 21 шага за эпизод , следуя по пути, обозначенному на графике «количество посещений». Различия в количестве шагов можно объяснить ε-жадной политикой, которая вводит 10% вероятность случайных действий. Учитывая эту политику, следование нижней границе является приемлемой стратегией для ограничения потенциальных помех, вызванных случайными действиями.
В заключение, агент Q-обучения, как уже упоминалось, пришёл к неоптимальной стратегии . Более того, часть окружения остаётся неисследованной Q-функцией, что не позволяет агенту найти новый оптимальный путь при появлении фиолетового портала после 100-го эпизода.
Эти ограничения производительности можно объяснить относительно небольшим количеством шагов обучения (400), что ограничивает возможности взаимодействия с окружающей средой и исследования, вызванного ε-жадной политикой.
Планирование , неотъемлемый компонент методов обучения с подкреплением на основе моделей , особенно полезно для повышения эффективности выборки и оценки значений действий . Dyna-Q и Dyna-Q+ являются хорошими примерами алгоритмов TD, включающих этапы планирования.
Dyna-Q
Алгоритм Dyna-Q (Dynamic Q-learning) представляет собой комбинацию обучения с подкреплением и обучения с обратным обучением на основе моделей .
Алгоритмы обучения с подкреплением на основе моделей используют модель окружающей среды для включения планирования в качестве основного способа обновления оценок стоимости . В отличие от них, алгоритмы без моделей основаны на прямом обучении.
«Модель окружающей среды — это все, что агент может использовать для прогнозирования реакции среды на его действия» — Обучение с подкреплением: введение.
В рамках данной статьи модель можно рассматривать как аппроксимацию динамики перехода p(s', r|s, a). Здесь p возвращает одну пару «следующее состояние — вознаграждение» для текущей пары «состояние — действие».
В средах, где p является стохастическим , мы различаем модели распределения и модели выборки: первая возвращает распределение следующих состояний и действий, тогда как вторая возвращает одну пару, выбранную из предполагаемого распределения.
Модели особенно полезны для имитации эпизодов и, следовательно, обучения агента путем замены реальных взаимодействий этапами планирования, т. е. взаимодействиями с моделируемой средой.
Агенты, реализующие алгоритм Dyna-Q, относятся к классу агентов планирования , сочетающих прямое обучение с подкреплением и обучение моделям . Они используют прямое взаимодействие с окружающей средой для обновления своей функции ценности (как в Q-обучении), а также для обучения модели окружающей среды. После каждого прямого взаимодействия они также могут выполнять шаги планирования для обновления своей функции ценности, используя смоделированные взаимодействия.
Быстрый пример шахмат
Представьте себе, что вы играете в шахматы. После каждого хода реакция соперника позволяет вам оценить качество вашего хода . Это похоже на получение положительного или отрицательного вознаграждения, которое позволяет вам «обновить» свою стратегию. Если ваш ход приводит к ошибке, вы, вероятно, не стали бы делать его снова, если бы у вас была та же конфигурация доски. Пока что это сравнимо с прямым обучением с подкреплением .
Теперь добавим планирование . Представьте, что после каждого вашего хода, пока противник думает, вы мысленно пересматриваете все свои предыдущие ходы, чтобы оценить их качество . Вы можете обнаружить слабые места, которые не заметили с первого взгляда, или обнаружить, что какие-то ходы были лучше, чем вы думали. Эти размышления также могут позволить вам обновить стратегию. Именно в этом и заключается суть планирования: обновление функции ценности без взаимодействия с реальной средой, а скорее с её моделью .
Таким образом, Dyna-Q содержит некоторые дополнительные шаги по сравнению с Q-learning:
После каждого прямого обновления значений Q модель сохраняет пару «состояние-действие», а также наблюдаемые награду и следующее состояние. Этот этап называется обучением модели.
- После обучения модели Dyna-Q выполняет n шагов планирования:
- Из буфера модели выбирается случайная пара «состояние-действие» (т.е. эта пара «состояние-действие» наблюдалась во время прямых взаимодействий).
- Модель генерирует имитированное вознаграждение и следующее состояние
- Функция ценности обновляется с использованием моделированных наблюдений (s, a, r, s')
Теперь мы воспроизводим процесс обучения с помощью алгоритма Dyna-Q, используя n=100 . Это означает, что после каждого прямого взаимодействия с окружающей средой мы используем модель для выполнения 100 шагов планирования (т. е. обновлений).
Следующая тепловая карта демонстрирует быструю сходимость модели Dyna-Q. Фактически, алгоритму требуется всего около 10 эпизодов для поиска оптимального пути . Это связано с тем, что каждый шаг приводит к 101 обновлению значений Q (вместо 1 для Q-обучения).
Ещё одним преимуществом планирования этапов является более точная оценка значений действий по всей сетке. Поскольку косвенные обновления нацелены на случайные переходы, хранящиеся в модели, состояния, далёкие от цели, также обновляются.
Напротив, в Q-обучении значения действий медленно распространяются от цели, что приводит к неполному отображению сетки.
Используя Dyna-Q, мы находим оптимальный путь , позволяющий решить задачу сеточного мира за 17 шагов , как показано на графике ниже красными полосами. Оптимальные результаты достигаются регулярно, несмотря на периодические вмешательства ε-жадных действий, совершаемых в целях исследования.
Наконец, хотя Dyna-Q может показаться более убедительным, чем Q-learning, из-за включения в него планирования, важно помнить, что планирование представляет собой компромисс между вычислительными затратами и реальным исследованием .
Dyna-Q+
До сих пор ни один из протестированных алгоритмов не смог найти оптимальный путь, появляющийся после шага 100 (фиолетовый портал). Более того, оба алгоритма быстро пришли к оптимальному решению, которое оставалось неизменным до конца фазы обучения . Это подчёркивает необходимость непрерывного исследования на протяжении всего обучения.
Dyna-Q+ во многом похож на Dyna-Q, но добавляет к алгоритму небольшое изменение. Dyna-Q+ постоянно отслеживает количество временных шагов, прошедших с момента проверки каждой пары «состояние-действие» в реальном взаимодействии с окружающей средой.
В частности, рассмотрим переход, дающий вознаграждение r , которое не было опробовано в течение τ временных шагов. Dyna-Q+ будет выполнять планирование так, как если бы вознаграждение за этот переход составляло r + κ √τ , при этом κ было достаточно малым (0,001 в эксперименте).
Это изменение в системе вознаграждения побуждает агента постоянно исследовать окружающую среду. Предполагается, что чем дольше не проверялась пара «состояние-действие», тем выше вероятность того, что динамика этой пары изменилась или модель неверна.
Как показано на следующей тепловой карте, Dyna-Q+ гораздо активнее обновляется по сравнению с предыдущими алгоритмами. До эпизода 100 агент исследует всю сетку и находит синий портал и первый оптимальный маршрут.
Значения действий для остальной части сетки уменьшаются, а затем снова медленно увеличиваются, поскольку пары «состояния-действие» в верхнем левом углу некоторое время не исследуются.
Как только в 100-м эпизоде появляется фиолетовый портал, агент находит новый короткий путь, и ценность всей области увеличивается. До завершения 400 эпизодов агент будет постоянно обновлять ценность действия каждой пары «состояние-действие», периодически исследуя сетку.
Благодаря бонусу, добавленному к вознаграждениям модели, мы наконец получаем полное отображение функции Q (каждое состояние или ячейка имеет значение действия).
В сочетании с непрерывным исследованием агенту удается найти новый наилучший маршрут (т.е. оптимальную политику) по мере его появления, сохраняя при этом предыдущее решение.
Однако компромисс между разведкой и эксплуатацией в Dyna-Q+ действительно имеет свою цену. Если пары «состояние-действие» не посещались достаточно долго, бонус за разведку побуждает агента повторно посещать эти состояния, что может временно снизить его текущую эффективность . Такое поведение разведки отдаёт приоритет обновлению модели для улучшения долгосрочного принятия решений.
Это объясняет, почему некоторые эпизоды, воспроизводимые Dyna-Q+, могут длиться до 70 шагов, в то время как Q-learning и Dyna-Q — максимум 35 и 25 шагов соответственно. Более длинные эпизоды в Dyna-Q+ отражают готовность агента вкладывать дополнительные шаги в исследование, чтобы собрать больше информации об окружающей среде и усовершенствовать свою модель, даже если это приводит к кратковременному снижению производительности.
Напротив, Dyna-Q+ регулярно достигает оптимальной производительности (показано зелеными полосами на графике ниже), чего не удавалось достичь предыдущим алгоритмам.
Резюме и сравнение алгоритмов
Чтобы сравнить ключевые различия между алгоритмами, мы используем две метрики (имейте в виду, что результаты зависят от входных параметров, которые для простоты были идентичными для всех моделей):
- Количество шагов на эпизод : эта метрика характеризует скорость сходимости алгоритмов к оптимальному решению. Она также описывает поведение алгоритма после сходимости, особенно в процессе исследования.
- Средняя кумулятивная награда : процент эпизодов, приведших к положительной награде.
Анализ количества шагов на эпизод (см. график ниже) раскрывает несколько аспектов методов, основанных на моделях, и методов без моделей:
- Эффективность на основе моделей : Алгоритмы на основе моделей (Dyna-Q и Dyna-Q+), как правило, более эффективны с точки зрения выборки в этом конкретном мире Grid (это свойство также наблюдается в более общем плане в RL). Это объясняется тем, что они могут планировать заранее, используя изученную модель среды, что может привести к более быстрой сходимости к решениям, близким к оптимальным или оптимальным.
- Сходимость Q-обучения : Q-обучение, хотя и сходится к решению, близкому к оптимальному, требует для этого больше эпизодов (125). Важно подчеркнуть, что Q-обучение выполняет только одно обновление за шаг, в отличие от множественных обновлений, выполняемых Dyna-Q и Dyna-Q+.
- Множественные обновления : Dyna-Q и Dyna-Q+ выполняют 101 обновление за шаг, что способствует более быстрой сходимости. Однако плата за эту эффективность выборки — высокие вычислительные затраты (см. раздел «Время выполнения» в таблице ниже).
- Сложные среды : В более сложных или стохастических средах преимущества методов, основанных на моделях, могут снижаться. Модели могут содержать ошибки или неточности, что может привести к принятию неоптимальных политик. Поэтому данное сравнение следует рассматривать как обзор сильных и слабых сторон различных подходов, а не как прямое сравнение эффективности.
Теперь мы вводим среднее кумулятивное вознаграждение (ACR), которое представляет собой процент эпизодов, в которых агент достигает цели (поскольку вознаграждение равно 1 за достижение цели и 0 за срабатывание ловушки), тогда ACR просто вычисляется по формуле:
Где N — количество эпизодов (250), K — количество независимых запусков (100), а Rn,k — кумулятивная награда за эпизод n в запуске k.
Вот анализ производительности всех алгоритмов:
- Dyna-Q быстро сходится и достигает наивысшей общей доходности с ACR 87%. Это означает, что система эффективно обучается и достигает цели в значительной части эпизодов.
- Метод Q-learning также достигает схожего уровня эффективности, но для его достижения требуется больше эпизодов, что объясняет его немного более низкий показатель ACR — 70%.
- Dyna-Q+ быстро находит подходящую стратегию, достигая кумулятивного вознаграждения 0,8 всего за 15 эпизодов. Однако вариативность и исследовательская активность, вызванные бонусным вознаграждением, снижают производительность до шага 100. После 100 шагов производительность начинает улучшаться по мере нахождения нового оптимального пути. Однако краткосрочное исследование снижает производительность, в результате чего ACR составляет 79%, что ниже, чем у Dyna-Q, но выше, чем у Q-обучения.
Заключение
В этой статье мы представили фундаментальные принципы обучения по методу временной разницы и применили Q-обучение, Dyna-Q и Dyna-Q+ к пользовательскому сетчатому миру. Дизайн этого сетчатого мира помогает подчеркнуть важность непрерывного исследования как способа поиска и использования новых оптимальных стратегий в изменяющихся условиях. Разница в производительности (оцениваемая по количеству шагов в эпизоде и кумулятивному вознаграждению) иллюстрирует сильные и слабые стороны этих алгоритмов.
Подводя итог, можно сказать, что методы, основанные на моделях (Dyna-Q, Dyna-Q+), выигрывают от более высокой эффективности выборки по сравнению с методами, основанными на моделях (Q-learning), за счёт эффективности вычислений. Однако в стохастических или более сложных средах неточности модели могут снизить производительность и привести к неоптимальным политикам.
Ссылки:
[1] Демис Хассабис, AlphaFold раскрывает структуру вселенной белков (2022), DeepMind
[2] Элия Кауфманн, Леонард Бауэрсфельд, Антонио Локерсио, Маттиас Мюллер, Владлен Колтун и Давиде Скарамуцца, Гонки на дронах чемпионского уровня с использованием глубокого обучения с подкреплением (2023), Nature
[3] Натан Ламберт, Луи Кастрикато, Леандро фон Верра, Алекс Хаврилла, Иллюстрация обучения с подкреплением на основе обратной связи с человеком (RLHF), HuggingFace
[4] Саттон, Р. С. и Барто, А. Г. Обучение с подкреплением: введение (2018), Кембридж (Массачусетс): Издательство MIT.
[5] Кристофер Дж. Ч. Х. Уоткинс и Питер Даян, Q-learning (1992), Машинное обучение, Springer Link
Источник: towardsdatascience.com
