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

Типы задач RL

Все задачи RL можно разделить на два типа:
1. Эпизодические задачи:Говоря о примере обучения ходьбе из предыдущего поста, мы видим, что агент должен научиться самостоятельно идти к точке назначения. Что происходит, когда агент успешно достигает точки назначения? Поскольку это все, что нужно было сделать для задачи, теперь агент может снова начать с исходной позиции и попытаться достичь пункта назначения более эффективно. Это пример эпизодической задачи. В таких задачах среда агента разбивается на последовательность эпизодов. Эпизодические задачи математически проще, потому что каждое действие влияет только на конечное количество наград, полученных впоследствии в течение эпизода.
2. Продолжающиеся задания: я уверен, что читатели знакомы с бесконечными беговыми играми, такими как Subway Surfers и Temple Run. Теперь представьте агента, пытающегося научиться играть в эти игры, чтобы максимизировать счет. Но этим играм нет конца. Это пример постоянной задачи. Другой пример — агент, который должен назначать входящие HTTP-запросы различным серверам по всему миру. Эта задача будет продолжаться до тех пор, пока серверы находятся в сети, и ее можно рассматривать как непрерывную задачу.

Марковские процессы принятия решений — Будущее зависит от того, что я делаю сейчас!

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

Говоря более технически, будущее и прошлое условно независимы при наличии настоящего.

Рассмотрим пример MDP:

На изображении выше есть три состояния: S₀, S₁, S₂ и 2 возможных действия в каждом состоянии: a₀, a₁. Цифры на этих стрелках представляют вероятности перехода. Например, если агент начинает с состояния S₀ и выполняет действие a₀, существует 50 % вероятность того, что агент попадет в состояние S₂, и еще 50 % вероятность того, что агент вернется в состояние S₀. В этом MDP можно получить 2 награды, взяв ₁ в S₂ или взяв ₀ в S₁.

Уравнения Беллмана

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

Мы знаем, что ценность состояния — это общая ожидаемая награда от этого состояния до конечного состояния. Это также можно представить следующим образом: если мы совершаем действие a в состоянии s и заканчиваем в состоянии s', то значение состояния s – это сумма вознаграждения, полученного за выполнение действия aв состоянии s, и значения состояния s' .

Аналогично для Q-значения:

Уравнения ожидания Беллмана

Это свойство рекурсивного обновления уравнений Беллмана облегчает обновление как функции значения состояния, так и функции значения действия. По мере того, как агент переходит из состояния в состояние, следуя политике π:

Уравнения оптимальности Беллмана

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

Должно быть совершенно ясно, что если агент знаком с динамикой среды, поиск оптимальных значений возможен. Но переходные вероятности Pᵃₛₛ’ и R(s, a) для большинства задач неизвестны. Тем не менее, уравнения Беллмана составляют основу многих алгоритмов RL.

Динамическое программирование — поиск оптимальной политики, когда модель среды известна.

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

Оценка политики

Вычислите значение состояния Vπ для политики π. Это называется Оценка политики.

где π(a|s) — вероятность выполнения действия aв состоянии s согласно политике π, а ожидания отмечены индексом π, чтобы указать, что они зависят от соблюдения π.

Улучшение политики

Предположим, мы определили функцию ценности Vπ для произвольной детерминированной политики π. Для некоторых состояний s мы хотели бы знать, должны ли мы изменить политику, чтобы детерминистически выбирать действие a > ≠ π(s).
Один из способов — выбрать a в s, а затем следуйте существующей политике π.

Предположим, вы выбрали действие a ≠ π(s)и следовали существующей политике π чем выбирать действие, предложенное текущей политикой, ожидается, что каждый раз, когда встречается состояние s, будет выбираться действие a всегда будет лучше, чем выбор действия, предложенного π(s). Это приводит к улучшению общей политики. Это теорема об улучшении политики.

Итерация политики

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

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

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