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

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

Награда Rₜ - это скаляр, просто число, используемое для обратной связи. Он показывает, насколько хорошо агент выполняет шаг t. Задача агентов - максимизировать вознаграждение. Как агент это делает? На каждом этапе агент должен предпринимать ту или иную форму действия Aₜ, основываясь на наблюдении Oₜ, которое он получает от среда. Мы можем охарактеризовать эту последовательность событий как историю,

который мы можем принять как все наблюдаемые переменные до времени t. В среде могут существовать другие влияющие переменные, но поскольку они не наблюдаются нашим агентом, мы отклоняем их как несущественные. Эту историю можно рассматривать как своего рода сенсомоторный поток для агента. Состояние - это функция истории → Sₜ = f (Hₜ), используемая для определения того, что произойдет дальше. На самом деле существует несколько определений для состояния, но для нашей цели мы будем интересоваться математическим определением, также известным как информация состояние или состояние Маркова . Рассмотрим следующее утверждение:

Будущее не зависит от прошлого, учитывая настоящее.

Это называется марковским свойством. Состояние S ₜ считается марковским тогда и только тогда, когда

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

Обучение с подкреплением обычно включает в себя одно или несколько из следующих действий:

  • policy π, функция, определяющая поведение агентов.
  • Функция значение, которая вычисляет, насколько хорошо каждое состояние и / или действие
  • модель, представляющая среду агентами.

Политика представляет собой карту от состояния к действию ... Она может быть детерминированной: a = π (s)
, а также (что очень полезно) быть стохастической, что позволяет учитывать вероятности и проводить дополнительные исследования. поведение:

Функция значения состояния оценивает, насколько хорошо / плохо состояние, и является предсказанием будущего вознаграждения. Следовательно, это зависит от политики. Его можно записать как

где гамма γ - это ставка дисконтирования между [0,1], которую мы добавляем и можем изменять, что говорит о том, что мы больше заботимся о немедленных вознаграждениях, а не о последующих вознаграждениях. Это объясняет тот факт, что у нас нет идеальной модели. Тесно связан со стоимостью возврат Gₜ, который представляет собой общее дисконтированное вознаграждение с временного шага t.

Итак, давайте свяжем все это вместе с процессом принятия решений Маркова. MDP - это кортеж (S, A, P, R, γ), где

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

  • R - функция вознаграждения:

  • γ - коэффициент дисконтирования γ ∈ [0,1]

Ключ к решению марковского процесса принятия решений - это уравнение ожидания Беллмана. Помните функцию состояния-значения сверху? Что ж, функция значения действия имеет аналогичное назначение, но учитывает значения всех будущих действий (которые мы называем q -значениями) и может быть разложена аналогичным образом:

Чтобы понять, как v и q работают вместе, давайте взглянем на следующую диаграмму:

Белый круг обозначает состояние, в котором вы находитесь, а два черных круга обозначают возможные действия. Вероятность выполнения каждого действия определяется политикой, и для каждого действия существует q -значение (значение-действие), которое говорит нам, насколько хорошо выполнить это действие из этого состояния. Мы смотрим на среднее значение q-значений, чтобы сообщить нам значение состояния исходного состояния. А теперь посмотрим на обратное.

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

Теперь мы можем объединить их, чтобы получить красивую рекурсию, которая помогает нам понять v в терминах самого себя.

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

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

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

Функция оптимальной ценности действия - это функция максимальной ценности действия по всем политикам.

Как только у нас есть оптимальная функция ценности действий, мы закончили - у нас есть лучшие действия, которые нужно предпринять. Решение марковского процесса принятия решений можно рассматривать как поиск q ⁎.

Теперь нам нужно определить, как мы сравниваем / частично упорядочиваем разные политики:

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

Мы также можем описать оптимальную политику, сказав, что мы максимизируем оптимальные значения q:

Теперь, если мы заменим эти функции оптимального значения исходными, которые у нас были раньше, мы можем получить уравнение оптимальности Беллмана для V⁎ и q⁎

Имея за плечами основы марковских процессов принятия решений, есть несколько ключевых моментов, которые важно отметить в отношении уравнения оптимальности Беллмана:

  • Это нелинейно
  • Нет закрытого решения (как правило)

Чтобы решить уравнение и найти оптимальную политику, мы используем итерационные методы решения, такие как

  • Итерация значений
  • Итерация политики
  • Q-обучение
  • Сарса

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

Как всегда, большое спасибо за чтение и не стесняйтесь обращаться с любыми мыслями / комментариями / вопросами.

Ресурсы

Обучение с подкреплением: введение Саттон и Барто

Курс RL Дэвида Сильвера на YouTube