Серия учебных пособий по обучению с подкреплением

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

Это третья часть серии руководств по RL, в которой представлен обзор книги Обучение с подкреплением: Введение. Второе издание." Ричард С. Саттон и Эндрю Дж. Барто. Эта книга доступна бесплатно «здесь.

Эта статья является частью серии. Ознакомьтесь с полной серией: Часть 1, Часть 2, Часть 3, Часть 4, Часть 5, Часть 6 и Часть 7!

Глава 3 - Конечные марковские процессы принятия решений
Ключевые концепции этой главы:
- Как проблемы RL вписываются в структуру марковского процесса принятия решений (MDP)
- Понимание того, что является марковским свойством
- Каковы вероятности перехода
- Дисконтирование будущих вознаграждений
- Эпизодические и непрерывные задачи
- Решение оптимальных функций политики и ценности с помощью уравнений оптимальности Беллмана

Краткое резюме:

  • Учащийся и лицо, принимающее решение, называется агентом.
  • То, с чем он взаимодействует, включая все, что находится за пределами агента, называется средой.
  • Агент взаимодействует с окружающей средой в течение последовательности дискретных временных шагов, t = 0, 1, 2, 3,. . ..
  • На каждом временном шаге t среда отправляет агенту состояние, St ∈ S, где S - набор возможных состояний.
  • На основании этого агент выбирает действие, At ∈ A (St), где A (St) - набор действий, доступных в состоянии St.
  • Через один временной шаг агент получает вознаграждение, Rt + 1 ∈ R, и оказывается в новом состоянии St + 1.
  • На каждом временном шаге агент следует сопоставлению своего текущего состояния с вероятностями выбора каждого возможного действия в этом состоянии.
  • Это отображение называется политикой агента и обозначается πt (A | S), где πt (A | S) - это вероятность выполнения действия «A» в состоянии «S» на временном шаге «t». ”
  • Цель агента - максимизировать общее вознаграждение, которое он получает в долгосрочной перспективе.

Возвраты
Если мы обозначим последовательность вознаграждений, которые агент получает после временного шага t, как: R (t + 1), R (t + 2),. . .
Агент стремится максимизировать ожидаемую доходность E (Gt).
Где определяется доходность Gt как:
Gt = R (t + 1) + R (t + 2) + R (t + 3) + · · · + R (T), а T - конечный временной шаг.

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

Каждая серия заканчивается особым состоянием, называемым конечным состоянием. После того, как агент достигнет конечного состояния, игра сбрасывается до некоторого начального состояния.

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

Однако возврат (Gt) проблематичен для продолжающихся задач.
Например, представьте, что агент получает вознаграждение +1 на каждом временном шаге.
Поскольку последний временной шаг равен T = ∞ (т.е. нет последнего шага), отдача (которую мы пытаемся максимизировать) будет бесконечной.

Следовательно, нам нужен еще один термин, который мы назовем скидкой.
Теперь цель агента - выбрать действия так, чтобы сумма получаемых дисконтированных вознаграждений была максимальной.
Как правило, он выбирает действие A в момент времени t (At), чтобы максимизировать ожидаемую прибыль со скидкой.

где γ - параметр, 0 ≤ γ ≤ 1, называемый ставкой дисконтирования.

γ в основном говорит, что вознаграждение, полученное в k временных шагов в будущем, стоит только в γ ^ k − 1 раз больше, чем было бы, если бы оно было получено немедленно.

Это решает нашу проблему, поскольку если γ ‹1, бесконечная сумма имеет конечное значение (пока последовательность вознаграждений ограничена).

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

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

Марковское свойство
Оптимально, мы хотели бы иметь сигнал состояния, который резюмирует прошлое таким образом, чтобы сохранялась вся важная информация.
Сигнал состояния, способный к имеющий всю соответствующую информацию из прошлого, считается Марковским или имеет Марковское свойство.
Например, позиция TicTacToe - любое состояние (то есть конфигурация всех фигур на доске) - будет служить марковским состоянием, потому что оно суммирует все важное.
Другими словами, вся информация, которая нам нужна для предсказания будущего, содержится в том представлении состояния, которое у нас есть.
В игре TicTacToe нас не должно волновать прошлое (то есть последовательность ходов, которые противник выбрал раньше). Все, что действительно важно для будущего игры, сохраняется. Нам следует заботиться только о том, где мы сейчас находимся (где фигуры на доске - его состояние).

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

Вышеприведенное уравнение называется динамической функцией p.
Это позволяет нам предсказать следующее состояние (S ') и ожидаемое следующее вознаграждение (r) с учетом текущего состояния (S) и действия (a).
Что в основном говорит нам о том, как меняется окружающая среда, когда мы переходим из состояния в состояние и предпринимаем различные действия.

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

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

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

Какова вероятность следующего состояния (S ’) с учетом текущего состояния и действия

Какая награда за определенное состояние и действие

Какая награда за определенное состояние, действие и следующее состояние

Диаграмма переходов
Полезный способ увидеть динамику конечного MDP - диаграмма переходов

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

Первая строка - мы видим, как в этой среде мы можем перейти из состояния «высокий» в состояние «высокий», выполнив действие «поиск». Мы также можем видеть, что у нас есть вероятность «а» перехода в состояние «высокий» после того, как мы находимся в состоянии «высокий» и выполняем действие «а». Наконец, мы видим, что награда, которую мы получим за это, будет «r_search».

Функции значения
Практически все алгоритмы RL включают функции оценки. Напомним, что функции ценности оценивают, насколько хорошо для агента находиться в заданном состоянии.
Напомним, что πt (A | S) - это вероятность выполнения действия «A» в состоянии «S» на временном шаге «t», что также называется политикой агента.
Значение состояния S в соответствии с политикой π, обозначенное V π (s), представляет собой ожидаемую отдачу при запуске в S и после этого после π.

Мы называем функцию V π функцией значения состояния для политики π.
где Gt - ожидаемый доход, о котором я упоминал ранее.

Точно так же мы можем определить значение действия «A» в состоянии «S» в соответствии с политикой π как q π (S, A).

Мы называем эту функцией значения действия для политики π. Это ожидаемый доход, начиная с состояния S, выполняя действие A и затем следуя политике π.

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

Если агент также поддерживает отдельные средние значения для каждого действия, предпринятого в состоянии, то эти средние значения также сходятся к значениям действия qπ (s, a).

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

Где π (a | s) - это вероятность выполнения действия «a» в состоянии «s» в соответствии с политикой π.
Приведенное выше уравнение является уравнением Беллмана для Vπ. Он выражает взаимосвязь между значением состояния S и значениями следующего состояния S ’в соответствии с политикой π.
Думайте об этом как о «значении данного состояния (в котором вы находитесь в данный момент) зависит от того, какие следующие состояния возможны».

Это можно увидеть на схеме резервного копирования:

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

Обратите внимание, что аналогично V π, существует также уравнение Беллмана и резервная диаграмма для q π (S, A), следуя тем же принципам.

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

В нашей политике мы выбираем действия равномерно случайным образом: влево, вверх, вправо, вниз, каждое с равной вероятностью (25%).
Среда сообщает нам, что мы получаем 10 наград при переходе от A к A ', 5 наград, когда мы переходим от B к B ', отрицательная награда, когда мы падаем с карты, и 0 наград в противном случае.

Итак, давайте посмотрим, как мы получили значение 2.3 для состояния, обведенного кружком:
Из состояния, обведенного кружком, мы можем перейти влево, вверх, вправо или вниз к следующему состоянию.
Каждое из этих состояний имеет определенное значение - Gt + 1 (4.4, 3.0, 0.7, 1.9).
У нас 0,25 шанса попасть в каждую.
В этом примере коэффициент дисконтирования γ равен 0,9.

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

0 + 0.9* [(0.25 * 4.4) + (0.25*1.9) + (0.25*0.7) + (0.25*3.0)] = 2.25 — > 2.3

0 - награда
0,9 - коэффициент скидки
0,25 - вероятность перехода в каждое состояние (влево, вверх…)
умноженное на 0,25 значение - это значение этого состояния ( например left = 3.0)

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

Уравнения оптимальности Беллмана - это способ решения оптимального значения состояний.

Оптимальное значение состояния обозначается V * (s)

Где уравнения 3.16 и 3.17 представляют собой две формы уравнения оптимальности Беллмана для V ∗.

Очень похоже на предыдущий, но теперь мы берем «max (a)», то есть действие с лучшей наградой для каждого состояния, чтобы максимизировать награду.
Когда у нас есть V ∗, легко определить оптимальную политику, которая в этом примере выглядит следующим образом:

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

Проблема, однако, в том, что почти со всеми проблемами трудно решить в вычислительном отношении явное решение для оптимального значения в каждом состоянии. Например, в более сложной среде, такой как игра Backgammon, у нас есть около 10²⁰ состояний. В следующих главах мы увидим, как решить эту проблему.

До скорого,

Ваше здоровье.