#InsideRL

Обучение с подкреплением: процесс принятия решений по Маркову (часть 1)

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

Прежде чем мы ответим на наш основной вопрос, то есть как мы формулируем задачи RL математически (с использованием MDP), нам необходимо развить нашу интуицию относительно:

  • Отношения агент-среда
  • Марковская собственность
  • Марковский процесс и цепи Маркова
  • Марковский процесс вознаграждения (MRP)
  • Уравнение Беллмана
  • Марковское вознаграждение

Хватай кофе и не останавливайся, пока не почувствуешь гордость! 🧐

Взаимоотношения агента и окружающей среды

Сначала давайте посмотрим на некоторые формальные определения:

Агент: программы, которые принимают разумные решения и изучают RL. Эти агенты взаимодействуют с окружающей средой посредством действий и получают вознаграждение за свои действия.

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

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

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

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

Переход. Переход из одного состояния в другое называется переходом.

Вероятность перехода: вероятность того, что агент перейдет из одного состояния в другое, называется вероятностью перехода.

Марковское свойство утверждает, что:

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

Математически мы можем выразить это утверждение как:

S [t] обозначает текущее состояние агента, а s [t + 1] обозначает следующее состояние. Это уравнение означает, что переход из состояния S [t] в S [t + 1] полностью не зависит от прошлого. Таким образом, RHS уравнения означает то же, что и LHS, если система имеет свойство Маркова. Интуитивно означает, что наше текущее состояние уже фиксирует информацию о прошлых состояниях.

Вероятность перехода между состояниями:

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

Для марковского состояния из S [t] в S [t + 1], то есть для любого другого последующего состояния, вероятность перехода между состояниями определяется выражением

Мы можем сформулировать вероятность перехода состояния в матрицу вероятности перехода состояния следующим образом:

Каждая строка в матрице представляет собой вероятность перехода из нашего исходного или начального состояния в любое последующее состояние. Сумма каждой строки равна 1.

Марковский процесс или марковские цепи

Марковский процесс - это случайный процесс без памяти, то есть последовательность случайных состояний S [1], S [2],… .S [n] с марковским свойством. Таким образом, это в основном последовательность состояний со свойством Маркова. Ее можно определить с помощью набора состояний (S) и матрицы вероятности перехода (P). Динамику среды можно полностью определить с помощью состояний (S) и перехода. Матрица вероятностей (P).

Но что означает случайный процесс?

Чтобы ответить на этот вопрос, давайте рассмотрим пример:

Ребра дерева обозначают вероятность перехода. Из этой цепочки возьмем образец. Теперь предположим, что мы спали, и согласно распределению вероятностей существует 0,6 шанс, что мы будем бегать и 0,2 шанс, что спите больше и снова 0,2, что мы будем есть мороженое. Точно так же мы можем думать о других последовательностях, которые мы можем выбрать из этой цепочки.

Некоторые образцы из сети:

  • Сон - Бег - Мороженое - Сон
  • Сон - Мороженое - Мороженое - Беги

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

Прежде чем переходить к процессу вознаграждения Маркова, давайте рассмотрим некоторые важные концепции, которые помогут нам понять MRP.

Вознаграждение и возврат

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

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

Мы можем определить Returns как:

r [t + 1] - это вознаграждение, полученное агентом на временном шаге t [0] при выполнении действия (a) по переходу из одного состояния в другое. Аналогично, r [t + 2] - это награда, полученная агентом на временном шаге t [1] за выполнение действия по переходу в другое состояние. И r [T] - это вознаграждение, полученное агентом на последнем временном шаге за выполнение действия по переходу в другое состояние.

Эпизодические и непрерывные задачи

Эпизодические задачи: это задачи, которые имеют конечное состояние (конечное состояние). Можно сказать, что у них есть конечные состояния. Например, в гоночных играх мы запускаем игру (запускаем гонку) и играем в нее, пока игра не закончится (гонка закончится!). Это называется эпизодом. Как только мы перезапустим игру, она начнется с начального состояния, и, следовательно, каждый эпизод будет независимым.

Непрерывные задачи: это задачи, у которых нет конца, т. е. они не имеют конечного состояния. Эти типы задач никогда не закончатся. Например, обучение программированию!

Теперь легко подсчитать отдачу от эпизодических задач, поскольку они в конечном итоге закончатся, но как насчет непрерывных задач, поскольку они будут продолжаться бесконечно. Возврат от суммы до бесконечности! Итак, как мы определяем отдачу для непрерывных задач?

Здесь нам нужен коэффициент скидки (ɤ).

Коэффициент скидки (ɤ): он определяет, насколько значение следует придавать немедленному вознаграждению и будущему вознаграждению. Это в основном помогает нам избегать бесконечности в качестве награды за выполнение непрерывных задач. Его значение находится в диапазоне от 0 до 1. Значение 0 означает, что большее значение придается немедленному вознаграждению, а значение 1 означает что больше внимания уделяется будущим вознаграждениям. На практике коэффициент дисконтирования, равный 0, никогда не будет учиться, поскольку он учитывает только немедленное вознаграждение, а коэффициент дисконтирования, равный 1, будет применяться для будущих вознаграждений, которые могут привести к бесконечности. Следовательно, оптимальное значение коэффициента дисконтирования находится в диапазоне от 0,2 до 0,8.

Итак, мы можем определить доходность с использованием коэффициента дисконтирования следующим образом: (Допустим, это уравнение 1, поскольку мы собираемся использовать это уравнение позже для вывода уравнения Беллмана)

Давайте разберемся с этим на примере, предположим, что вы живете в месте, где вы сталкиваетесь с нехваткой воды, поэтому, если кто-то придет к вам и скажет, что он даст вам 100 литров воды! (Предположите, пожалуйста!) В течение следующих 15 часов в зависимости от некоторый параметр (ɤ). Давайте рассмотрим две возможности: (Допустим, это уравнение 1, поскольку мы собираемся использовать это уравнение позже для вывода уравнения Беллмана)

Один с коэффициентом дисконтирования (ɤ) 0,8:

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

Во-вторых, с коэффициентом дисконтирования (ɤ) 0,2:

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

Итак, какое значение коэффициента скидки использовать?

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

Марковское вознаграждение

До сих пор мы видели, как цепь Маркова определяла динамику среды, используя набор состояний (S) и матрицу вероятности перехода (P). Но мы знаем, что обучение с подкреплением - это цель максимизировать вознаграждение. > добавить вознаграждение в нашу цепочку Маркова. Это дает нам процесс вознаграждения Маркова.

Процесс вознаграждения Маркова: как следует из названия, MDP - это цепи Маркова с оценкой ценностей. Как правило, мы получаем значение из каждого состояния, в котором находится наш агент.

Математически мы определяем Марковский процесс вознаграждения как:

Это уравнение означает, какое вознаграждение (Rs) мы получаем в конкретном состоянии S [t]. Это говорит нам о немедленном вознаграждении из того конкретного состояния, в котором находится наш агент. В следующей истории мы увидим, как мы максимизируем эти вознаграждения из каждого состояния, в котором находится наш агент. Проще говоря, максимизация совокупного вознаграждения, которое мы получаем из каждого состояния.

Мы определяем MRP как (S, P, R, ɤ), где:

  • S - набор состояний,
  • P - матрица вероятности перехода,
  • R - это функция вознаграждения, которую мы видели ранее,
  • ɤ - коэффициент дисконтирования

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

Теперь давайте разовьем нашу интуицию в отношении уравнения Беллмана и процесса принятия решений Маркова.

Функция политики и функция значения

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

Политика - это простая функция, которая определяет распределение вероятностей по Действиям (a∈ A) для каждого состояния (s ∈ S). Если агент в момент времени t следует политике π, то π (a | s) - это вероятность того, что агент предпримет действие (a) на определенном временном шаге (t). агента определяет изменение политики. Математически политика определяется следующим образом:

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

Это уравнение дает нам ожидаемую доходность, начиная с состояния (состояний) и переходя в последующие состояния после этого с политикой π. Следует отметить, что доходность, которую мы получаем, является стохастической, тогда как значение состояния не стохастическое. Это ожидание возврата из начального состояния s и после этого в любое другое состояние. А также обратите внимание, что значение конечного состояния (если оно есть) равно нулю. Давайте посмотрим на пример:

Предположим, что наше начальное состояние - это класс 2, и мы переходим к классу 3, затем «пройден», затем «спит». Короче говоря, класс 2 ›класс 3› пройден ›спящий режим.

Наша ожидаемая доходность указана с учетом коэффициента дисконтирования 0,5:

Примечание. Это -2 + (-2 * 0,5) + 10 * 0,25 + 0 вместо -2 * -2 * 0,5 + 10 *. 0,25 + 0. Тогда значение класса 2 равно -0,5.

Уравнение Беллмана для функции цены

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

Уравнение Беллмана утверждает, что функцию ценности можно разложить на две части:

  • Немедленное вознаграждение, R [t + 1]
  • Дисконтированная стоимость правопреемников,

Математически мы можем определить уравнение Беллмана как:

Давайте разберемся, что говорит это уравнение, на примере:

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

Давайте посмотрим на другой пример:

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

Вышеупомянутое уравнение может быть выражено в матричной форме следующим образом:

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

Сложность выполнения этого вычисления составляет O (n³). Следовательно, это явно не практическое решение для решения больших MRP (то же самое для MDPs). В последующих блогах мы рассмотрим более эффективные методы, такие как Динамическое программирование (итерация значения и итерация политики), методы Монте-Кларо и TD-Learning.

В следующем рассказе мы поговорим об уравнении Беллмана более подробно.

Что такое марковский процесс принятия решений?

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

Это кортеж из (S, A, P , R, 𝛾) где:

  • S - набор состояний,
  • A - это набор действий, которые агент может выбрать,
  • P - матрица вероятностей перехода,
  • R - Награда, накопленная за действия агента,
  • 𝛾 - коэффициент скидки.

P и R будут немного изменяться относительно следующих действий:

Матрица вероятности перехода

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

Теперь наша функция вознаграждения зависит от действия.

До сих пор мы говорили о получении вознаграждения (r), когда наш агент проходит через набор состояний, следуя политике π. Фактически, в Марковском процессе принятия решений (MDP) политика - это механизм для принятия решений. Итак, теперь у нас есть механизм, который выбирает действие.

Политики в MDP зависят от текущего состояния. Они не зависят от истории. Это марковское свойство. Итак, нынешнее состояние, в котором мы находимся, характеризует историю.

Мы уже видели, насколько хорошо агенту находиться в определенном состоянии (функция значения состояния). Теперь давайте посмотрим, насколько хорошо выполнить определенное действие в соответствии с политикой π из состояния s (функция «действие-значение»).

Функция значения состояния-действия или Q-функция

Эта функция определяет, насколько хорошо агент выполняет действие (а) в состоянии (ах) с политикой π.

Математически мы можем определить функцию значения Состояние-действие как:

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

Давайте посмотрим на пример Марковского процесса принятия решений:

Теперь мы видим, что вероятностей больше нет. Фактически, теперь у нашего агента есть выбор: после пробуждения мы можем выбрать просмотр Netflix или код и отладку. Конечно, действия агента определяются некоторой политикой π и соответственно получат вознаграждение.

Фантастика!

Поздравляю с тем, что продержался до конца! 👍

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

Надеюсь, эта история расширит ваше понимание MDP. Хотел бы связаться с вами в Instagram.

Спасибо, что поделились со мной временем!

Часть 1, Часть 2 и Часть 3 о Марковском процессе принятия решений:

Использованная литература :

ОСТАВАЙТЕСЬ ГЛУБОКО