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

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

Итак, робот использует этот циферблат, а также всю имеющуюся у него информацию о наградах и вероятностях, чтобы придумать план. А потом говорит, что делать. И это алгоритм MDP!

Чтобы использовать алгоритм MDP, нам необходимо определить следующие элементы:

  • Состояния. Набор возможных состояний системы.
  • Действия. Набор возможных действий, которые может предпринять агент.
  • Функция перехода. Вероятность перехода из одного состояния в другое в зависимости от текущего состояния и действия.
  • Функция вознаграждения. Вознаграждения или штрафы, связанные с каждым состоянием и действием.
  • Коэффициент дисконтирования: важность будущих вознаграждений по сравнению с немедленными вознаграждениями.

Чтобы проиллюстрировать, как работает алгоритм MDP, рассмотрим следующий простой пример:

Предположим, вы пытаетесь решить, какой фильм посмотреть. У вас есть список из трех вариантов: «Действие», «Комедия» и «Драма».

У вас есть предпочтения для каждого жанра с оценкой 1 для "Действия", 2 для "Комедии" и 3 для "Драмы".

В этом случае состояния могут представлять три варианта фильма, а действия могут представлять ваше решение посмотреть один из фильмов.

Функция перехода будет определять вероятность перехода из одного состояния (варианта фильма) в другое в зависимости от действия (вашего решения).

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

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

Состояния: "Действие", "Комедия", "Драма"

Далее вы должны определить набор действий, которые будут вашим решением посмотреть один из фильмов:

Действия: «Действие», «Комедия», «Драма»

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

Функция перехода: P(s’|s,a) = 1, если s’ = a, 0 в противном случае

Эта функция перехода говорит, что если следующее состояние (фильм, который вы действительно смотрите) совпадает с действием (фильмом, который вы выбрали для просмотра), то вероятность перехода равна 1, в противном случае — 0.

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

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

R(s,a) = 1, если s = «Действие» и a = «Действие»,

2, если s = "Комедия" и a = "Комедия",

3, если s = "Драма" и a = "Драма", -10 в противном случае

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

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

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

Чтобы вычислить новые значения каждого состояния, вам нужно выполнить итерацию по набору состояний (s) и действий (a) и использовать функцию вознаграждения (R), функцию перехода (P), коэффициент дисконтирования (γ). и текущие значения состояний (V), чтобы вычислить новые значения каждого состояния.

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

V(s) = max[a] { R(s,a) + γ * Σ[s’] P(s’|s,a) * V(s’)

new_values = {s: max([reward(s, a) +
 gamma * sum([transition(s, s_next, a) * values[s_next] 
for s_next in states]) for a in actions]) for s in states}
  • V(s):это значение состояния (состояний). Он представляет собой ожидаемую общую дисконтированную награду за нахождение в состоянии s и соблюдение оптимальной политики.
  • max[a]: указывает, что значение состояния является максимальным значением среди всех возможных действий (a).
  • R(s,a):это функция вознаграждения, которая определяет вознаграждения или штрафы, связанные с каждым состоянием (состояниями) и действием (а).
  • γ:это коэффициент дисконтирования, который определяет важность будущих вознаграждений. Высокое значение γ (близкое к 1) означает, что алгоритм больше ценит долгосрочные вознаграждения, тогда как низкое значение γ (близкое к 0) означает, что алгоритм больше ценит краткосрочные вознаграждения.
  • Σ[s’]:это указывает на то, что ожидаемое общее вознаграждение со скидкой представляет собой сумму вознаграждений со скидкой для всех возможных следующих состояний (s’).
  • P(s'|s,a):это функция перехода, которая определяет вероятность перехода из текущего состояния(s)в следующее состояние (s')на основе текущего действия(a).
  • V(s'):это значение следующего состояния(s'), которое представляет собой ожидаемое общее дисконтированное вознаграждение за нахождение в следующем состоянии и следование оптимальному политика.

Уравнение, которое вы предоставили, вычисляет ценность состояния (состояний), беря максимальное значение из всех возможных действий (a) вознаграждения за нахождение в состоянии s и выполнение действия a, плюс обесцененное ожидаемое общее вознаграждение за все возможные следующие состояния (s') с учетом текущего состояния s и действия a, умноженные

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

# Define the set of states
states = ["Action", "Comedy", "Drama"]

# Define the set of actions
actions = ["Action", "Comedy", "Drama"]

# Define the transition function
def transition(s, s_next, a):
  if s_next == a:
    return 1
  else:
    return 0

# Define the reward function
def reward(s, a):
  if s == "Action" and a == "Action":
    return 1
  elif s == "Comedy" and a == "Comedy":
    return 2
  elif s == "Drama" and a == "Drama":
    return 3
  else:
    return -10

# Set the discount factor
gamma = 0.9

# Initialize the values of each state
values = {s: 0 for s in states}

# Iterate until the values converge
while True:
  # Compute the new values of each state
  new_values = {s: max([reward(s, a) + gamma * sum([transition(s, s_next, a) * values[s_next] for s_next in states]) for a in actions]) for s in states}

  # Check for convergence
  if all([abs(values[s] - new_values[s]) < 1e-5 for s in states]):
    break

  # Update the values of each state
  values = new_values

# Print the values of each state
print("Values:")
for s in states:
  print(f"State: {s} | Value: {

Состояние: Действие | Значение: 16,999903122619465
Состояние: Комедия | Значение: 19,99993541507965
Состояние: Драма | Значение: 29,999903122619465

Но не верьте нам на слово — попробуйте алгоритм MDP сами и посмотрите, как он может изменить вашу жизнь! И помните: с алгоритмом MDP на вашей стороне вам больше никогда не придется беспокоиться о принятии неверного решения. Удачного принятия решений!

Знаете ли вы, почему алгоритм MDP продолжал теряться в лабиринте?

Потому что он всегда принимал неправильные решения!