Обучение с подкреплением: от проб и ошибок к глубокому Q-обучению

Моя цель в этой статье — демистифицировать несколько основополагающих концепций обучения с подкреплением (RL) на практических примерах.

Мы собираемся применить RL к печально известному испытанию «Стеклянный мост» из седьмого эпизода Squid Game сериала Netflix.

Хотя никаких предварительных знаний в области RL не требуется, для следования содержанию этой статьи необходимы твердые навыки программирования на Python и базовое понимание машинного обучения.

Код можно найти здесь.

Проблема обучения с подкреплением

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

каков наилучший подход для достижения моей цели?
Какие действия приблизят меня к цели?
Как система отреагирует на действие?

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

Элементы обучения с подкреплением

Следующие определения могут сначала сбить с толку, но они станут яснее, когда мы углубимся в практические примеры.

Агент: это система, которой мы хотим управлять. Агент обучения обладает тремя основными характеристиками:
1. он имеет явные цели,
2. он может ощущать аспекты своего окружения,
3. он может выбирать действия, чтобы влиять на свое окружение.
Среда: определяет все, с чем может взаимодействовать агент.
Действие: это действие, которое агент выполняет для взаимодействия со средой.
Состояние: представляет собой наблюдение за окружающей средой после выполнения действия.
Политика: она определяет способ поведения обучающего агента в данный момент времени. Политика — это функция, которая принимает в качестве входных данных состояние среды в данный момент времени и возвращает действие. Это может быть простая таблица поиска, функция или более обширный поисковый процесс. В целом политика является стохастической.
Награда: это сигнал, одно число. Цель обучающего агента — увеличить это число. Награда зависит от текущего действия агента и состояния среды. Агент обучения может влиять на сигнал вознаграждения двумя способами:
1. напрямую через свои действия,
2. косвенно, через изменение состояния среды.
Ценность: это ожидаемое общее вознаграждение, начиная с определенного состояния. В то время как вознаграждение определяет, что хорошо в данный момент, ценность определяет, что хорошо в долгосрочной перспективе. Хотя ценность вторична (то есть не может существовать без вознаграждения), она является наиболее важным компонентом почти всех алгоритмов обучения с подкреплением. Мы ищем действия, которые приносят состояния наивысшей ценности, а не высшей награды. Например, состояние может давать небольшое немедленное вознаграждение, но все же иметь высокую ценность, поскольку за ним регулярно следуют другие состояния, приносящие высокое вознаграждение. Определить ценности гораздо сложнее, чем определить награды, ценности должны оцениваться и переоцениваться на основе последовательностей наблюдений, которые агент делает за всю свою жизнь.
Модель среды: имитирует поведение среды. Учитывая состояние и действие, модель предсказывает следующее состояние и вознаграждение. Модели окружающей среды используются для определения курса действий путем рассмотрения возможных будущих ситуаций. Методы решения задач обучения с подкреплением могут быть либо основанными на моделях, либо немодальными (метод проб и ошибок), либо комбинированными.

Марковский процесс принятия решений

Есть несколько фреймворков, которые можно использовать при работе с RL. Здесь мы рассматриваем структуру Марковского процесса принятия решений.
Марковские процессы принятия решений (MDP) представляют собой формализацию последовательных процессов принятия решений, в которых каждое действие влияет не только на непосредственное вознаграждение, но и на все последующие состояния и поэтому будущие награды. Структура MDP определяет, что каждый целенаправленный процесс принятия решений может быть сведен всего к трем сигналам, которыми обмениваются агент и среда. Эти сигналы:

выбор агента (действия),
основание, на котором был сделан этот выбор (состояние),
цель агента (вознаграждение).

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

MDP можно визуализировать с помощью следующей схемы:

На каждом временном шаге агент выбирает действие в состоянии, а среда возвращает наблюдение (т. е. новое состояние) и награда.

Дилемма разведка-эксплуатация

Агенту RL необходимо найти правильный баланс между изучением окружающей среды, поиском новых способов получения вознаграждения и использованием уже обнаруженных источников вознаграждения.

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

Давайте приступим к делу

Задача на стеклянный мост

Как упоминалось во вступлении, мы собираемся воссоздать печально известную задачу со стеклянным мостом из 7-го эпизода сериала Netflix Squid Game.

Агент управляет перемещением персонажа по сетке. Персонаж должен перейти с одной стороны моста на другую. Единственная загвоздка в том, что не все плитки моста сделаны из закаленного стекла, некоторые — из обычного стекла, которое моментально разбивается под тяжестью персонажа.

Агент получает вознаграждение за то, что нашел проходимую дорожку к плитке цели, которая является последней плиткой моста из закаленного стекла.

Персонаж является агентом.
Стеклянный мост — это окружающая среда.
Достижение цели, то есть пересечение всего моста без падений, возвращает награду != 0.
Возможные движения персонажа, т. е. переход к следующей или самой дальней плитке, являются действиями.
Положение персонажа на стеклянном мосту — это состояние окружающей среды.
Траектория от начала до конца называется эпизодом. Траектория завершается, когда выполняется условие завершения. Условие завершения — либо достижение цели, либо наступление на обычную стеклянную плитку.

Открытый тренажерный зал с искусственным интеллектом

Библиотека тренажерного зала OpenAI представляет собой набор тестовых задач, известных как среды, которые можно использовать для разработки алгоритмов обучения с подкреплением.

Пересечение стеклянного моста методом проб и ошибок

Давайте начнем с понимания схемы «состояние-действие-вознаграждение».

Здесь я адаптирую FrozenLakeEnv, определенный в библиотеке Gym, чтобы воссоздать стеклянный мост из эпизода 7 Squid Game (Netflix).

Каждый эпизод начинается с вызова reset(), который возвращает исходное observation (или состояние среды). Действия выбираются случайным образом (политика) из пространства действий среды. Возможные действия:

ВПРАВО: переместитесь на соседнюю плитку справа от вас (мост пересекает слева направо)
ДИАГОНАЛЬ: двигаться по диагонали (т.е. переходить к следующей, а не соседней стеклянной плитке)

Кроме того, для каждого действия среда может вернуть с небольшой вероятностью (20%) результат альтернативного действия. Например, действие DIAGONAL может вернуть агента на правую соседнюю стеклянную плитку, а RIGHT может переместить агента по диагонали.

Первая строка создает среду GlassBridge. Затем мы просматриваем 20 эпизодов. В каждом эпизоде мы сбрасываемся на стартовую стеклянную плитку (3-я строка). На каждом временном шаге t агент в состоянии выбирает действие, в результате чего получает числовое вознаграждение и оказывается в новом состоянии. Подробно:

5-я строка отображает игру.

7-я строка предлагает действие, которое выбирается случайным образом.

На 8-й строке совершается действие, и среда дает четыре возврата:

newstate: целое число, представляющее позицию агента (см. иллюстрацию ниже) после взятия action.
reward: 1, если newstate == тайл цели, 0 в противном случае.
done: флаг, указывающий, окончена ли игра (наступила на обычное стекло или безопасно пересекла мост) или нет.
info: дополнительная отладочная информация.

9-я строка: если игра завершена, начать новый эпизод.

Записывая переходы агентов, мы можем наметить окружение. Последовательность этих переходов и есть траектория агента.

Мы можем напрямую визуализировать все возможные траектории с помощью следующей карты.

Вспоминая MDP, предположим, что мы находимся в состоянии 6. Мы знаем, что движение по диагонали (действие 1) с высокой вероятностью вернет конечное вознаграждение. Эта вероятность зависит только от текущего состояния 6, а не от предыдущей последовательности состояний. Это пример марковского свойства.

Q-обучение

Всегда существует по крайней мере одна политика, которая лучше или равна всем остальным политикам. Это называется оптимальной политикой. Оптимальная политика характеризуется оптимальной функцией действия и ценности, обозначаемой q*(s, a). Для пары состояние-действие (𝑠, a) эта функция дает ожидаемый доход от выполнения действия 𝑎 в состоянии 𝑠 в соответствии с оптимальной политикой.

Давайте теперь представим алгоритм, известный как Q-обучение (Watkins, 1989). Алгоритм Q-обучения позволяет нам определить функцию Q, которая непосредственно аппроксимирует 𝑞*.

Мы хотим рассчитать доход, а не немедленное вознаграждение. В заданное время t для заданной пары состояние-действие возврат представляет собой сумму всех вознаграждений до завершения эпизода,

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

Это можно переписать как

Агент должен выбрать действие 𝑎ₜ₊₁, которое максимизирует доход:

Чтобы аппроксимировать оптимальную функцию действия-ценности, мы применяем поправку, взвешенную по скорости обучения 𝛼. Под коррекцией мы понимаем разницу между измеренной функцией действия-ценности 𝑄(𝑠ₜ, 𝑎ₜ) и ожидаемой функцией действия-ценности 𝑄ₑₓₚ(𝑠ₜ, 𝑎ₜ),

и обновленное значение 𝑄 (𝑄ᵤₚₜ) гласит:

что приводит к

Выученная функция ценности действия 𝑄ᵤₚₜ(sₜ, aₜ) напрямую аппроксимирует 𝑞∗, оптимальную функцию ценности действия, независимую от применяемой политики. Уравнение выше, чтобы обновить 𝑄, является знаменитым уравнением Беллмана.

Давайте реализуем уравнение Беллмана.

Q — это таблица, в которой хранятся значения Q.

Давайте обучим агента решать GlassBridgeEnv, запустив несколько эпизодов. В каждом эпизоде мы обновляем функцию «действие-ценность», используя уравнение Беллмана, определенное выше.

Обратите внимание на следующие характеристики Q:

Q-значения нормированы в диапазоне [0,1] для удобочитаемости, где максимальное значение = 1. Это значение фактически получено для конечной пары состояние-действие, которая предшествует цели (𝑠=6, 𝑎=1).
Q-значения равны 0 для конечных состояний (обычные стеклянные плитки и целевое состояние), поскольку переход из конечных состояний не происходит.
Чем выше значение Q пары состояние-действие, тем ближе эта пара состояние-действие к цели.

Теперь сравним нашего обученного агента с агентом, выбирающим случайные действия. Обученный агент будет выбирать действия с наивысшим значением Q, чтобы максимизировать вознаграждение. Такая политика известна как жадная политика.

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

При случайной политике мы получаем ~1% успешных эпизодов, а при жадной — ~20%. Обученный агент превосходит случайного агента.

Дилемма эксплуатации и исследования

Тем не менее, мы обучаем агента тысячам эпизодов, значения Q все еще неточны.

Почему это?!

В начале все значения Q равны 0, в последовательных эпизодах агент случайным образом выбирает действие, и, делая это, он имеет конечную вероятность найти пути вознаграждения. Предупреждение заключается в том, что эта случайная политика не позволяет агенту использовать наиболее выгодный путь, потому что он не исследует достаточно путей, которые могли бы привести к максимальной отдаче.

Чтобы улучшить случайную политику, мы можем вместо этого использовать политику epsilon greedy (𝜖-greedy). Эта политика работает следующим образом:

В каждом эпизоде агент совершает случайное действие с вероятностью 𝜖 и жадное действие с вероятностью 1−𝜖.
В последовательных эпизодах значение 𝜖 уменьшается, переключая политику со случайного исследования на выбор пути, который максимизирует вознаграждение.

Тонкая настройка гиперпараметров

Есть несколько рекомендаций по решению простых задач RL, которые помогут добиться успеха.

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

Если агент успешно работает несколько раз, но не использует эти успехи, попробуйте выполнить следующие действия:

Отрегулируйте скорость обучения.
Увеличьте количество серий → тренируйтесь дольше.
Увеличьте discount_factor, чтобы убедиться, что вознаграждение в достаточной степени соответствует значениям Q для начальных состояний.

Эпсилон-жадная политика успешно уравновешивает разведку и эксплуатацию. Сочетание табличного Q-обучения с эпсилон-жадной политикой — мощный подход к решению простых сред.

Глубокое Q-обучение

Табличное Q-Learning (как обсуждалось в предыдущем разделе) создает таблицу, в которой требуется запись для каждой комбинации состояния и действия. Если среда проста, это действительно мощный подход, но если среда более сложная, с множеством состояний и действий, размер Q-таблицы становится огромным.

Вместо использования таблицы мы можем прогнозировать значения Q с помощью нейронных сетей.

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

Вход в нейронную сеть — это состояние с горячим кодированием, выход — вектор Q-значений для каждого действия. Таким образом, вход — это вектор длины num_states, а выход — вектор длины num_actions.

Выход этой ячейки (16, 2), где 16 — количество состояний, а 2 — возможные действия (ВПРАВО, ДИАГОНАЛЬ).

Мы определяем нелинейную нейронную сеть с 16 входами и 2 выходами, используя API TF Keras. Нейронная сеть имеет следующие характеристики:

выполнен из одного плотного слоя,
использует функцию активации relu,
веса инициализируются небольшими положительными значениями,
не использует предвзятость. Почему?! Учитывая, что каждый нейрон соответствует действию, независимо от состояния, 𝑄(𝑠1, a1) будет иметь то же смещение, что и 𝑄(𝑠2, a2). Обучение модели изменит это смещение и одновременно повлияет на несколько прогнозов.

Как мы обучаем NN? Выполняем следующие шаги:

Предположим, мы находимся в состоянии s0, первое, что мы делаем, — это выбираем действие, которое должен выполнить агент. Как мы выбираем действие? Мы используем, например, 𝜖-жадную политику. Отличие от Q-табличного обучения в том, что теперь нейронная сеть заменяет Q-таблицу.

2. После выполнения действия мы записываем следующее состояние, в котором мы находимся, и полученную награду.

newstate, reward, done, _ = env.step(action)

3. Затем мы вычисляем целевое значение добротности, используя обновление Беллмана.

где 𝑠ₒ — состояние шага 1, а 𝑎 — действие, которое мы предприняли.

q-значения для состояния представляют собой двумерный массив формы (1, 2), например. [[0.04, 0.01]], где два значения обозначают Q-значения двух возможных действий (ВПРАВО, ДИАГОНАЛЬ) соответственно. Значение 0 в q_values[0, action] используется для [[0.04, 0.01]]--› [0.04, 0.01] .

4. Теперь, когда у нас есть целевое значение Q, мы обучаем NN прогнозировать это значение Q. Таким образом, в следующем эпизоде действие, которое мы предпримем в s₀, будет определяться этим новым обновленным значением Q, и в идеале действие, соответствующее максимальному значению q, будет тем, которое приблизит нас к конечной цели.

model.fit(one_hot_encode_state(state), q_values)

Четыре шага выше должны выполняться в цикле. Для каждого эпизода мы возвращаем обученную модель, возврат эпизода (или сумму вознаграждений) и продолжительность эпизода. Эта последняя метрика очень важна, потому что агент будет успешно выполнять все больше и больше шагов, и эпизод будет длиться дольше по мере того, как агент будет учиться. Продолжительность эпизода — отличный показатель для отслеживания обучения агента.

Следующий фрагмент кода обучает агента с помощью сети Deep Q Network (DQN) и определенной выше политики 𝜖-жадности. Он записывает продолжительность эпизода агента и вознаграждение агента за эпизод в качестве метрик и отображает их. Как правило, можно также определить порог успеха (например, процент успехов), чтобы знать, когда прекратить тренировку, или, как мы будем отслеживать продолжительность эпизода.

Вознаграждение от конечного состояния должно распространяться обратно на Q-значения начального состояния. Чем выше discount_factor, тем больше доля вознаграждения, которая распространяется обратно. Следовательно, держите discount_factor высоким.

Повтор опыта

Онлайн-DQN последовательно обучается на кортежах, сгенерированных во время живого обучения. Это делает тренировку нестабильной… почему? Потому что обучение модели в последовательном порядке на траектории состояний означает, что последовательные состояния похожи. Подобные в том смысле, что эти кортежи сильно коррелированы, это противоречит правилу независимо и одинаково распределенных (i.i.d.) данных. Даже если мы выберем наше начальное состояние случайным образом, остальные действия и состояния для перехода будут выбраны в соответствии с траекторией, они выбираются политикой за один шаг, что не делает последовательные шаги полностью независимыми случайными выборками. Чтобы сделать выборочные наблюдения независимыми, нужно сделать новый случайный выбор, а для одинакового распределения этот выбор должен быть сделан справедливо по всему набору данных.

Если входные данные модели не являются i.i.d, модель не сможет хорошо обобщаться на другие данные, и поэтому обучение становится нестабильным. Нейронные сети полагаются на предположение, что входные данные являются i.i.d.

Вход в Повтор опыта.

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

сохранить кортеж для перехода состояния в буфер,
выборка пакета кортежей из буфера воспроизведения и обучение NN на нем.

Обучение на пакетах кортежей вместо отдельных кортежей позволяет лучше использовать опыт агента и делает обучение более стабильным.

Целевые сети

Другой метод, который дополняет воспроизведение опыта и позволяет стабилизировать обучение DQN, — это Целевые сети. При выполнении онлайн-DQN при каждом переходе состояния веса NN обновляются для повышения прогностической способности. Те же веса и сеть используются для прогнозирования целевых значений Q. NN тренируется, используя свои собственные прогнозы. В результате целевые значения Q не остаются стабильными, и мы сталкиваемся с проблемой преследования движущейся цели.

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

для создания буфера воспроизведения мы используем структуру данных deque из библиотеки Python collections. Это позволяет нам установить максимальный размер, и если этот размер превышен, он удаляет первый элемент и добавляет новый элемент в конец очереди.