Марковский процесс принятия решений, более известный как MDP, представляет собой подход к обучению с подкреплением для принятия решений в среде gridworld. Среда gridworld состоит из состояний в виде сеток.

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

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

В этом руководстве мы подробно рассмотрим MDP, состояния, действия, награды, политики и способы их решения с помощью уравнений Беллмана.

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

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

MDP определяется как совокупность следующего:

  • Состояния: S
  • Действия: A (s), A
  • Модель перехода: T (s, a, s ’) ~ P (s’ | s, a)
  • Награды: R (s), R (s, a), R (s, a, s ’).
  • Политика:

  • оптимальная политика

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

Давайте попробуем разбить это на разные блоки лего, чтобы понять, что означает этот общий процесс.

Марковское свойство

Короче говоря, в соответствии с свойством Маркова, чтобы знать информацию ближайшего будущего (скажем, во время t + 1), текущая информация во время t имеет значение.

Учитывая последовательность,

, первый приказ Маркова гласит:

, то есть,

зависит только от

. Следовательно,

будет зависеть только от

. Второй приказ Маркова гласит:

, то есть,

зависит только от

а также

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

, зависит только от текущего состояния,

, так что текущее состояние фиксирует и запоминает свойства и знания из прошлого. Таким образом, согласно свойству Маркова, мир (то есть среда) считается стационарным, то есть правила в мире фиксированы.

Набор состояний S

Набор состояний S - это набор различных состояний, представленных как s, которые составляют среду. Состояния - это характерное представление данных, полученных из среды. Таким образом, любой ввод от датчиков агента может играть важную роль в формировании состояния. Пространства состояний могут быть дискретными или непрерывными. Он запускается из начального состояния и должен достичь целевого состояния по наиболее оптимизированному пути, не попадая в плохие состояния (например, состояние красного цвета, показанное на диаграмме ниже).

Рассмотрим следующий сеточный мир как имеющий 12 дискретных состояний, где зеленая сетка - это состояние цели, красный - это состояние, которого следует избегать, а черный - это стена, от которой вы отскочите, если столкнетесь с ней:

Состояния могут быть представлены как 1, 2,… .., 12 или координатами, (1,1), (1,2),… .. (3,4).

Действия

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

Рассмотрим следующий пример gridworld, имеющий 12 дискретных состояний и 4 дискретных действия (ВВЕРХ, ВНИЗ, ВПРАВО и ВЛЕВО):

В предыдущем примере показано, что пространство действий является пространством дискретного набора, то есть a

A, где A = {ВВЕРХ, ВНИЗ, ВПРАВО и ВЛЕВО}. Его также можно рассматривать как функцию состояния, то есть a = A (s), где в зависимости от функции состояния он решает, какое действие возможно.

Переходная модель

Модель перехода T (s, a, s ') - это функция трех переменных: текущее состояние (s), действие (a ) и новое состояние (s ') и определяет правила игры в среде. Он дает вероятность P (s '| s, a), то есть вероятность попадания в новое состояние s' при условии, что агент выполняет действие, a, в данном состоянии s.

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

Давайте рассмотрим следующую среду (мир) и рассмотрим различные случаи, детерминированные и стохастические:

Поскольку действия a

A, где A = {ВВЕРХ, ВНИЗ, ВПРАВО и ВЛЕВО}.

Поведение этих двух случаев зависит от определенных факторов:

  • Определенная среда: в определенной среде, если вы предпримете определенное действие, например ВВЕРХ, вы обязательно выполните это действие с вероятностью 1.
  • Стохастическая среда. В стохастической среде, если вы выполните то же действие, скажем ВВЕРХ, с определенной вероятностью будет 0,8, чтобы фактически выполнить данное действие, и с вероятностью 0,1 может выполнять действие (ВЛЕВО или ВПРАВО) перпендикулярно данному действию, ВВЕРХ. Здесь для состояния s и модели перехода действий UP T (s ’, UP, s) = P (s’ | s, UP) = 0,8.

Поскольку T (s, a, s ’) ~ P (s’ | s, a), где вероятность нового состояния зависит только от текущего состояния и действия, а не от предыдущих состояний. Таким образом, модель перехода следует марковскому свойству первого порядка.

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

Награды

Награда государства количественно определяет полезность перехода в состояние. Существует три различных формы для представления вознаграждения, а именно: R (s), R (s, a) и R (s, a, s ') , но все они эквивалентны.

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

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

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

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

Политика

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

Политика - это функция, которая принимает состояние в качестве входных данных и выводит действие, которое необходимо предпринять. Следовательно, политика - это команда, которой агент должен подчиняться.

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

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

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

Поскольку оптимальная

политика - это политика, которая максимизирует ожидаемое вознаграждение, поэтому

,

куда

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

политика. Таким образом,

выводит

политика, имеющая наивысшее ожидаемое вознаграждение.

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

политики, то полезность

политика для состояния s, то есть

будут ожидаемыми наградами от этого состояния и далее:

Немедленное вознаграждение государства, то есть

отличается от полезности

состояние (то есть полезность оптимальной политики

состояние) из-за концепции отложенного вознаграждения. С этого момента полезность

состояние будет относиться к полезности оптимальной политики государства, то есть

штат.

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

где T (s, a, s ') - вероятность перехода, то есть P (s' | s, a) и U (s ' ) - это полезность нового состояния посадки после выполнения действия a над состоянием s.

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

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

куда,

это немедленная награда и

- это вознаграждение из будущего, то есть дисконтированные полезности состояния «s», куда агент может добраться из данного состояния s, если предпринято действие a.

Решение уравнения Беллмана для поиска политики

Скажем, у нас есть n состояний в данной среде, и если мы увидим уравнение Беллмана,

обнаруживаем, что дано n состояний; следовательно, у нас будет n уравнений и n неизвестных, но

функция делает его нелинейным. Таким образом, мы не можем решить их как линейные уравнения.

Следовательно, чтобы решить:

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

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

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

Попробуем разобраться в этом на примере.

Пример итерации значений с использованием уравнения Беллмана

Рассмотрим следующую среду и данную информацию:

Данная информация:

  • A, C и X - названия некоторых состояний.
  • Состояние, выделенное зеленым цветом, - это состояние цели, G, с вознаграждением +1.
  • Состояние красного цвета - это плохое состояние, B, с наградой -1, постарайтесь предотвратить переход вашего агента в это состояние.
  • Таким образом, зеленый и красный состояния являются конечными состояниями, войдите в любое из них, и игра окончена. Если агент встречается с зеленым состоянием, то есть с состоянием цели, агент побеждает, а если они входят в красное состояние, то агент проигрывает игру.

  • ,

  • (то есть награда за все состояния, кроме состояний G и B, составляет -0,04),

  • (то есть полезность на первом временном шаге равна 0, за исключением состояний G и B).
  • Вероятность перехода T (s, a, s ’) равна 0,8 при движении в желаемом направлении; в противном случае - по 0,1, если они идут перпендикулярно желаемому направлению. Например, если действие ВВЕРХ, то с вероятностью 0,8 агент переходит ВВЕРХ, но с вероятностью 0,1 он переходит ВПРАВО и 0,1 - на ВЛЕВО.

Вопросов:

  1. Находить

  1. , полезность состояния X на временном шаге 1, то есть агент выполнит одну итерацию
  2. Аналогично найдите

Решение:

R(X) = -0.04

Действие как »

ПРАВИЛЬНО

G

0,8 + 10,8 x 1 = 0,8 RIGHTC0,100,1 x 0 = 0 RIGHTX0,100,1 x 0 = 0

Таким образом, для действия a = RIGHT,

Действие как »

ВНИЗ

C

0,800,8 x 0 = 0 DOWNG 0,1 + 10,1 x 1 = 0,1 DOWNA 0,100,1 x 0 = 0

Таким образом, для действия a = DOWN,

Действие как »

UP

X

0,800,8 x 0 = 0UPG0,1 + 10,1 x 1 = 0,1UPA0,100,1 x 0 = 0

Таким образом, для действия a = UP,

Действие как »

ЛЕВЫЙ

A

0,800,8 x 0 = 0LEFTX0,100,1 x 0 = 0LEFTC0,100,1 x 0 = 0

Таким образом, для действия a = LEFT,

Поэтому среди всех действий

Следовательно,

, куда

а также

Аналогично рассчитываем

а также

и мы получаем

а также

С,

, а также,

R(X) = -0.04

Действие как »

ПРАВИЛЬНО

G

0,8 + 10,8 x 1 = 0,8RIGHTC0,1–0,040,1 x -0,04 = -0,004RIGHTX0,10,360,1 x 0,36 = 0,036

Таким образом, для действия a = RIGHT,

Действие как »

ВНИЗ

C

0,8–0,040,8 x -0,04 = -0,032 DOWNG0,1 + 10,1 x 1 = 0,1 DOWNA0,1–0,040,1 x -0,04 = -0,004

Таким образом, для действия a = DOWN,

Действие как »

UP

X

0,80,360,8 x 0,36 = 0,288UPG0,1 + 10,1 x 1 = 0,1UPA0,1–0,040,1 x -0,04 = -0,004

Таким образом, для действия a = UP,

Действие как »

ЛЕВЫЙ

A

0,8–0,040,8 x -0,04 = -0,032LEFTX0,10,360,1 x 0,36 = 0,036LEFTC0,1–0,040,1 x -0,04 = -0,004

Таким образом, для действия a = LEFT,

Поэтому среди всех действий

Следовательно,

, куда

а также

Следовательно, ответы на предыдущие вопросы таковы:

Повторение политики

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

  • Начните со случайной политики,

  • Для данного

  • политики на шаге итерации t, вычислить

  • используя следующую формулу:

  • Улучшить

  • политика

На этом заканчивается интересное руководство по обучению с подкреплением. Хотите реализовать современные алгоритмы обучения с подкреплением с нуля? Получите бестселлер Обучение с подкреплением с TensorFlow.

Читать дальше:

Как работает обучение с подкреплением

Сверточные нейронные сети с обучением с подкреплением

Начало работы с Q-Learning с использованием TensorFlow