Демистификация марковского процесса принятия решений с помощью мемов

Что такое МДП?

Если мы перейдем к статьям Википедии для MDP, он определяется как:

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

Так что же это на самом деле означает?

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

Почему я должен заботиться о MDP?

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

Open AI 5 от Deep Mind победил чемпионов мира среди людей в DOTA 2 в 2019 году, используя MDP в качестве одного из инструментов для моделирования и освоения игры. Вы можете прочитать больше об этом здесь".

Итак, как мы можем смоделировать проблему с MDP?

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

  1. Должны быть наблюдаемые состояния
  2. Должны быть Действия, которые Актер может предпринять, чтобы повлиять на эти Наблюдаемые Состояния.
  3. Вероятности перехода к будущим наблюдаемым состояниям должны зависеть только от предыдущего состояния.
  4. Должно быть распределение вознаграждения, чтобы указать целевые состояния или нежелательные состояния.

Например, в DOTA 2 возможным наблюдаемым Состоянием S_1 может быть враг, у которого осталось 9 башен. Действие A_1 может быть атакой одной из башен, а другое Состояние S_2 может быть противником, имеющим 8 башни остались. Здесь вы можете перейти от S_1 к S_2, выбрав A_1.

Переход к S_2 зависит от того, находится ли он в состоянии S_1 с самого начала. При переходе с S_1 на S_2 действующий агент может получить небольшую награду R_1, за разрушение башни, так как это приблизило его к победе в игра.

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

Пять компонентов MDP

Пять компонентов, составляющих MDP, следующие:

  • Состояния: что вы можете наблюдать
  • Действия/Политика: то, что вы сможете делать в штате.
  • Функция перехода: вероятность перехода из одного состояния в другое.

  • Награды: печенье за ​​достижение цели, яд за попадание в яму

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

Где t представляет временной шаг.

состояния

Состояние — это то, что наблюдает актор в окружающей среде на данном временном шаге. Состояние должно быть определено таким образом, чтобы оно содержало всю информацию, влияющую на переход в будущее состояние из текущего. Например, в следующей среде Grid World состояние — это один из блоков в сетке. Его можно представить в виде координаты вида (0, 0).

Политика/Действие

Функция Политики действий дает нам вероятности возможных действий, которые Актёр может предпринять при заданном Состоянии S_t.

Формально определяется как:

где π() — Функция политики.

Например, на следующем рисунке Вопрос — это Состояние, а Параметры A B C D — это >возможные действия, которые Актер может предпринять в этом состоянии.

Награды

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

Формально определяется как:

Вероятности перехода состояния

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

Чтобы смоделировать этот недетерминизм, который часто наблюдается в сценариях реальной жизни, MDP имеет функцию вероятности перехода состояния, которая дает нам вероятность перехода в состояние S_2, учитывая наше текущее состояние S_1. и текущее действие A_1.

Формально определяется как:

Фактор скидки

γ ∈ [0, 1] — коэффициент дисконтирования, представляющий разницу в важности между настоящим и будущим вознаграждением.

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

Совокупное вознаграждение / доход

Совокупное вознаграждение или доход для состояния S_t — это сумма общих вознаграждений, которые Актер получает от Среды, начиная с состояния S_t и заканчивая состоянием S_t. до конца Эпизода или до определенного шага времени, t.

Вознаграждения, которые находятся на расстоянии временных шагов от состояния, S_t для которого рассчитывается доход, получают меньший вес путем умножения коэффициента скидки (который, как упоминалось ранее, должен быть между 0 и 1). Коэффициент дисконтирования возводится в степень по мере того, как дальше временные шаги от состояния S_t, когда было получено вознаграждение. Это сделано для того, чтобы Актер придавал большее значение Состояниям и ближе к ним вознаграждал.

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

Где G_t – это совокупный доход.

В приведенном ниже примере по мере того, как штаты приближаются,S_{t + 3}, к фактическому вознаграждению, выделенному зеленым цветом, их совокупное вознаграждение увеличивается, указывая на то, что рядом находится действительно большое вознаграждение. В то время как государства, которые находятся дальше , S_t, получают меньшую часть того же вознаграждения из-за взвешивания, ставка скидки применяется к вознаграждениям, которые находятся дальше временных шагов.

Заключение

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

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

Примечания

Среда

Среда — это окружение, в котором действует Актер/Агент. Сам Мир Решетки в Мире Сети Шиба Ину является средой.

Актер/Агент

Сущность, действующая в среде.

Эпизод

Все состояния, находящиеся между начальным и конечным состояниями. Например: состояния между началом боя и моментом, когда вы или другой игрок получаете фаталити в Mortal Kombat.

Шаг времени

Атомарный шаг в среде, который приводит к переходу Актера из одного состояния в другое.