Обучение с подкреплением — одна из самых сложных областей машинного обучения из-за его математической сложности, а также амбициозных задач, которые оно пытается решить.
Проще говоря, конечная цель алгоритма RL — сделать агента способным действовать в среде, чтобы максимизировать общее вознаграждение.
Легче сказать, чем сделать: за этим единственным предложением скрывается множество вопросов, например:
- Как определить «цель» и «награду»?
- Как заставить агента «действовать»?
- Как смоделировать «среду»?
Проблема намного сложнее, чем кажется, но на сегодняшний день достигнут значительный прогресс, наиболее известными примерами которого являются научные прорывы, такие как AlphaGo и AlphaTensor от DeepMind.
Тем не менее, если вы хотите глубоко понять область, вы должны начать с основ. Целью этого поста будет дать общий обзор RL, а также представить три алгоритма, которые представляют собой основы многих других, более продвинутых: Temporal Difference, SARSA и Q-Learning.
Обучение с подкреплением: строительные блоки
В RL мы используем простую модель для описания того, как агент взаимодействует с пространством, которая называется Марковский процесс принятия решений.
MDP представляют собой математическую основу для моделирования ситуаций, в которых динамика частично контролируется агентом, а частично определяется характеристиками среды. В MDP агент постоянно взаимодействует со средой, которая отвечает наградами, влияющими на последующие действия агента. Давайте посмотрим на следующую картинку:
На каждом временном шаге t агент получает представление состояния Sₜ среды, которое обуславливает выбор действия Aₜ. На следующем временном шаге t+1 агент получает награду Rₜ₊₁, которая информирует его о том, насколько хорошим было его прошлое действие, а также новое представление среда.
В конечной MDP состояния Sₜ, действия Aₜ и вознаграждения Rₜ имеют конечное число элементов, при этом Sₜ и Rₜ имеют четко определенные дискретные распределения вероятностей, зависящие только от предшествующих состояний и действий. Эти характеристики обычно делают проблему более разрешимой. Однако не все проблемы можно смоделировать с помощью конечных состояний, действий или вознаграждений, однако многие предположения и выводы, которые мы будем делать, легко обобщаются на непрерывные условия.
Непрерывное взаимодействие между агентом и средой порождает траекторию:
S₀, A₀, R₀, S₁, A₁, R₁, S₂, A₂, R₂…
Тем самым вероятность перехода из состояния Sₜ в Sₜ₊₁ зависит от выбора действия Aₜ, но при условии Sₜ и Aₜ, он условно независим от всех предыдущих состояний и действий. Поэтому мы говорим, что переходы состояний MDP удовлетворяют свойству Маркова.
Конечная цель агента — максимизировать общую доходность в долгосрочной перспективе, которая обычно учитывает коэффициент дисконтирования γ, рассчитываемый следующим образом:
Фактор дисконтирования γ определяет, насколько агент жаждет немедленного вознаграждения (γ = 0) или имеет более долгосрочную перспективу и стремится к высокой отдаче в будущем (γ = 1).
Агент должен вести себя так, чтобы переходить в состояния, дающие высокие вознаграждения. Поведение агента определяется политикой π(a|s), функцией, которая выводит вероятность выполнения действия a при условии, что агент находится в состоянии с. В соответствии с заданной политикой мы можем определить функцию значения состояния (и функцию значения состояния-действия), которая измеряет ожидаемую прибыль, которую агент получает, начиная с s (и выполнение a), а затем π.
Теперь цели алгоритмов RL обычно две:
- Прогноз: оценка функций ценности заданной политики π
2. Контроль: поиск оптимальной политики π*, а именно политики, которая максимизирует отдачу в долгосрочной перспективе.
Обратите внимание, что эти две задачи взаимосвязаны: если агент следует политике π, моя первая цель — оценить, насколько хороша эта политика (Прогноз). Оценив функции ценности политики, я могу решить, как изменить ее, чтобы получить еще лучшую функцию ценности (Контроль).
Знание модели среды, а именно знание вероятностных распределений действий и вознаграждений, дает значительное преимущество в решении этих двух задач. Тем не менее, модель часто скрыта или слишком сложна для обработки, поэтому алгоритмы лучше учатся на опыте (или эпизодах), которые представляют собой последовательности состояний, действий и вознаграждений, заканчивающиеся с терминальными состояниями. Например, полная игра в крестики-нолики представляет собой эпизод, в котором конечное состояние достигается, когда один из игроков выигрывает (или оба играют вничью).
Список алгоритмов, доступных для решения задач прогнозирования и управления, велик, и каждый из них способен получать оптимальные результаты при определенных предположениях. Здесь я решил рассказать о трех базовых алгоритмах, которые в целом показали себя довольно хорошо, но также представляют собой основу для многих более сложных алгоритмов:
- Временная разница
- САРСА
- Q-обучение
Временная разница
Временная разница считается центральной идеей обучения с подкреплением, поскольку оно учится на необработанном опыте без модели окружающей среды. Он решает проблему прогнозирования, а именно оценивает функцию ценности состояний MDP.
Проблема с обучением на опыте заключается в том, что нужно дождаться окончания эпизода (и, следовательно, окончательного результата), чтобы обновить оценки функций ценности. TD преодолевает это препятствие, ожидая одного единственного шага, чтобы сделать это.
На каждом временном шаге t функция ценности состояния Sₜ немедленно обновляется на основе немедленно полученного вознаграждения Rₜ₊₁ и оценок нового состояния Sₜ₊₁. Это простейшая версия TD, называемая TD(0), где ноль обозначает тот факт, что для выполнения обновления необходимо дождаться одного шага, однако эту идею можно распространить на более сложные алгоритмы, такие как n-шаг. TD и TD(λ). Как вы заметили, правило обновления одного состояния использует оценки другого состояния: этот метод называется самозагрузка.
Мы упомянули, в чем плюсы использования TD, вот краткое изложение:
- Ему не нужна модель окружающей среды
- Его оценки сходятся (быстро) к функции ценности реального состояния
- Он выполняет инкрементные обновления в режиме онлайн, а именно ему не нужно ждать окончания эпизодов, чтобы обновить оценки функции ценности.
САРСА
Я знаю, о чем вы думаете: такое странное название для алгоритма. Ну, действительно, название SARSA происходит от перехода из состояния S в S':
SARSA — это метод TD, основанный на политике, для решения проблемы Control, что означает, что он пытается найти оптимальную политику для данной задачи. Почему «на политику»?
При обучении на основе политики функция оптимального значения изучается на основе действий, предпринятых с использованием текущей политики 𝜋(𝑎|𝑠).
Действительно, причина, по которой SARSA определяется как «в соответствии с политикой», заключается в том, что мы используем текущую политику для обновления Q(s, a). Если это неясно, подождите, чтобы увидеть, что делает Q-Learning, и проверьте разницу.
Теперь, как SARSA узнает оптимальную политику? Мы упомянули, что это метод TD, что означает, что он использует правило обновления TD для оценки функции ценности. Но как это улучшит политику для получения функции большего значения?
SARSA достигает этого, изменяя политику π ε-жадным образом: на каждом шаге мы выполняем:
- действие с наибольшим Q(a,s), с вероятностью 1 - ε
- другое случайное действие, каждое из которых имеет вероятность ε / N(a) быть выбранным, где N(a) — количество возможных действий
Параметр ε уравновешивает компромисс между использованием и исследованием: в то же время вы хотите использовать то, что вы уже знаете, а именно выполнение наилучшего действия, но вы также хотите изучить другие возможности, а именно обнаружить возможное лучшее действия.
После завершения процедуры, если мы тщательно посетили каждую пару состояние-действие, мы получим оптимальное ε-жадное Q*(a, s), что легко приводит к оптимальная ε-жадная политика:
Q-обучение
В общем, Q-Learning — это неполитический метод TD для решения проблемы Control.
При обучении вне политики функция оптимального значения изучается на основе действий, предпринимаемых независимо от текущей политики 𝜋(𝑎|𝑠).
Q-Learning на самом деле очень похож на SARSA. Единственное (но значимое) отличие заключается в правиле обновления Q(a, s), а именно:
В этом случае значение Q не обновляется в соответствии с ε-жадной политикой, которой мы следуем, но оно основано на наилучшем действии, которое мы можем предпринять из следующего состояния Sₜ₊₁ (и это сильно отличается от SARSA!) .
Аналогичным образом, пока каждая пара значений состояние-действие посещается бесконечное количество раз, Q-Learning сходится к оптимальному Q*(a, s) и к оптимальной политике.
Итак… SARSA или Q-Learning?
Мы видели два алгоритма решения задач управления, однако есть разница в способах их обучения. В процессе обучения SARSA руководствуется выбранным ε-жадным действием, которое может быть (и это часто бывает) неоптимальным. С другой стороны, Q-Learning всегда выполняет жадное действие при обновлении Q(s, a).
Эта (большая) разница приводит к тому, что политика, изученная SARSA, является почти оптимальной.
Так не следует ли всегда выбирать Q-Learning? Ну, технически вы могли бы. Но бывают случаи, когда выбор жадного действия может повлечь за собой некоторый риск и дорогостоящие ошибки, которых можно избежать или ограничить, выбрав более консервативный алгоритм, такой как SARSA.
Выводы
В этом посте я обобщил ключевые концепции RL, начиная с базовых элементов, таких как концепции состояний, действий и вознаграждений, и заканчивая сложными методами поиска наилучшей политики для достижения конкретной цели.
Обучение с подкреплением представляет собой набор сложных методов, иногда трудных для понимания и реализации, однако эти методы часто основаны на концепциях, проиллюстрированных здесь, поэтому я предлагаю вам освоить их, прежде чем двигаться дальше.
Я надеюсь, что вы нашли этот пост полезным! Если это так, то почему бы вам…
1. хлопать в ладоши 👏
2. подписываться на меня ❤️
3. проверять мою страницу GitHub 💻
4. добавлять меня в ЛинкедИн! 🤝 (Я всегда открыт для общения!!!)
Кредиты
[1] «Обучение с подкреплением: введение», Эндрю Барто и Ричард С. Саттон.
