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

Элементы марковского процесса принятия решений

Государственное пространство

Пространство состояний определяет возможные состояния, в которые может развиваться MDP. Состояние используется для описания MDP на заданном временном шаге. Агент использует состояние в качестве критерия принятия решения при выборе действия (с целью максимизации вознаграждения).

Возьмем в качестве примера шахматы: одно состояние будет содержать информацию о каждой фигуре на доске. На основе этого состояния агенту предоставляется возможность планировать свой следующий ход (решая, какая фигура перемещается на какое поле). Это состояние может быть представлено либо численно, либо изображением шахматной доски (что усложнит общую задачу, так как усложнит обработку изображения). В этом примере пространство состояний содержит все возможные (законные) положения шахматных фигур (согласно «числу Шеннона» пространство состояний шахмат содержит около 10¹²⁰ различных состояний).

Марковская недвижимость

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

Это означает, что для того, чтобы не нарушать свойство Маркова, состояние должно

«включать информацию обо всех аспектах прошлого взаимодействия агента с окружающей средой, которые имеют значение для будущего» (Р. С. Саттон и А. Г. Барто).

В конце концов, агент принимает решение, основываясь на состоянии текущего временного шага, а не на состояниях, которые он видел ранее (как если бы у агента не было памяти).

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

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

Начальное и конечное состояния

Есть два типа особых состояний. Во-первых, есть начальные состояния, которые часто обозначаются как S₀. Во-вторых, есть конечные состояния, которые отмечают конец эпизода. Терминальные состояния обычно обозначаются заглавной T, например Sₜ. Взаимодействие между средой и агентом, которое простирается от начального до конечного состояния, называется эпизодом. Обратите внимание, что не все MDP имеют терминальные состояния. Те, которые имеют терминальные состояния, часто называются эпизодическими MDP, тогда как те, у которых нет терминальных состояний, называются продолжающимися MDP.

Пространство действий

Пространство действий определяет возможные действия Aₜ, которые агент может предпринять в заданном состоянии. Выполнение действия вызывает переход состояния и приводит к новому состоянию MDP Aₜ₊₁. Пространства действий можно классифицировать по их типу действия, которое может быть либо дискретным, либо непрерывным. В непрерывных пространствах действий действие может принимать любое действительное число в указанном интервале. С другой стороны, действия в дискретных пространствах действий могут принимать только дискретные значения.

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

Функция вознаграждения

После совершения действия агент получает не только информацию о новом состоянии MDP, но и скалярное вознаграждение Rₜ₊₁ ∈ ℝ. Вознаграждение служит обратной связью о качестве определенного действия в данном состоянии. Цель агента — максимизировать сумму вознаграждения с течением времени (как мы увидим через минуту, эта сумма будет дисконтирована). Расчет вознаграждения может быть выражен как функция r(s, a, s′), которая зависит от текущего состояния s, последующего состояния s ′, а также действие a, предпринятое для перехода из текущего состояния в последующее. Функция вознаграждения является частью реализации каждой среды и очень важна, поскольку она кодирует цель текущей задачи. Разумный выбор определения вознаграждения является ключом к функциональности обучения с подкреплением.

Вознаграждение, данное агенту, может быть классифицировано как разреженное или плотное. Небольшие награды выдаются агенту редко (обычно в конце эпизода). Напротив, большие вознаграждения присуждаются агенту часто (как правило, после каждого действия). Давайте снова возьмем наш пример с вратарем в настольном футболе: в сценарии с редким вознаграждением агент получит вознаграждение только после того, как вратарь удержит мяч (например, r=1) или гол был забит (например, r=-1). В сценарии с плотным вознаграждением агент может получать вознаграждение после каждого действия в виде расстояния между вратарем и мячом (чем меньше расстояние, тем выше вознаграждение). Таким образом, агент мог бы легко изучить поведение приближения к мячу, чтобы удерживать его. В большинстве случаев использование плотного вознаграждения облегчает обучение, поскольку мы чаще даем обратную связь агенту. С другой стороны, иногда трудно определить плотные награды (например, в шахматах). Наконец, используя редкие вознаграждения, мы косвенно предоставляем агенту предварительные знания (чего мы обычно не хотим). Как и в сценарии с вратарем, мы даем агенту информацию о том, что хорошо быть близко к мячу, чтобы удерживать его (было бы неплохо, если бы агент мог сам уловить такое поведение?).

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

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

Сумма дисконтируется с помощью коэффициента γ∈[0,1], который используется для определения степени влияния будущих вознаграждений по сравнению с немедленными вознаграждениями. Чем выше γ, тем большее влияние на доход оказывают будущие вознаграждения. В случае, когда γ=1, вознаграждения в далеком будущем окажут такое же влияние на доход, как и немедленные вознаграждения. Если γ=0, нас вообще не волнуют будущие вознаграждения. Агент усвоит политику, которая фокусируется только на выборе действия, которое максимизирует вознаграждение в настоящем и игнорирует все будущие последствия, которые это может вызвать (например, съесть целый пакет мармеладных мишек сейчас, потому что они такие вкусные, но полностью игнорируя тот факт, что это может впоследствии вызвать боль в животе). Правильный выбор γ зависит от поставленной задачи и является одним из наиболее важных гиперпараметров в обучении с подкреплением.

Функция перехода

Как упоминалось ранее, выполнение действия приводит к переходу MDP в новое состояние. Более формально этот переход можно описать следующим образом:

Функция перехода p определяет вероятность достижения следующего состояния s′ и получения вознаграждения r, если агент выбирает действие a, находясь в состоянии s. Или, другими словами: p определяет внутреннюю динамику MDP.

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

Напротив, в детерминированных средах при переходе между состояниями не происходит случайной динамики. Это приводит к тому, что функция перехода принимает исключительно значение 0 или 1. Это означает, что когда вы совершаете действие a, находясь в состоянии s, вы всегда можете ожидать тот же статус-преемник s′ и вознаграждение r.

Агентская сторона MDP

Компоненты, описанные выше, определили MDP, который является формальным определением нашей среды в обучении с подкреплением. Другая сторона уравнения — агент, который принимает решения, выбирая действия. В основном нас интересует поиск (или обучение) агента, который выбирает (хорошие) действия, максимизирующие вознаграждение. Агент выбирает эти действия на основе политики, которая обозначается как π. Более формально π определяет поведение агента, определяя распределение вероятностей действий на основе текущего состояния:

Говоря об глубоком обучении с подкреплением, политика π представлена ​​глубокой нейронной сетью.

Чтобы иметь возможность находить политики, которые работают хорошо, нам нужен способ их оценки. Поэтому для оценки используются функции стоимости.

«насколько хорошо агенту находиться в данном состоянии» (Р. С. Саттон и А. Г. Барто).

Это делается с помощью так называемой функции значения состояния Vπ(S). Он определяет ожидаемую будущую доходность [см. уравнение (3)], когда вы находитесь в состоянии s и после этого следуете политике π:

Полученная из функции состояния-ценности функция действия-ценности Qπ(S) оценивает доход при совершении действия в определенном состоянии и последующем соблюдении политики π:

Значения действия обычно называются Q-значениями. Если предполагается, что после выполнения действия a действует оптимально, функция действия-ценности обозначается как Q*(s,a).

В случае, если оптимальная функция действия-значения Q*(s,a) известна, оптимальные действия можно выполнить, просто следуя жадной политике, которая выбирает действие, которое максимизирует Q*(s ,а) на каждом временном шаге:

Или, проще говоря, оптимально действовать можно, выбирая наилучшее возможное действие в данном состоянии. Наилучшее возможное действие — это действие с наивысшим значением Q. Как бы то ни было, предположение об оптимальной функции действия-ценности в большинстве случаев не выполняется. Следовательно, мы должны либо аппроксимировать оптимальную функцию «действие-ценность», либо использовать другие подходы, чтобы заставить работать глубокое обучение с подкреплением.

Источники: