Метод Монте-Карло

Введение в метод Монте-Карло

Здравствуйте и вновь добро пожаловать на занятия по теме «Искусственный интеллект: обучение с подкреплением на языке Python».

В этой части курса мы обсудим ещё один метод решения марковских процессов принятия решений, который называется методом Монте-Карло, оценим стратегию с этим методом в коде и мире-решетки с ветром.

В предыдущей части, посвящённой  динамическому программированию, можно было заметить нечто странное: как обсуждалось в этом курсе ранее, обучение с подкреплением целиком посвящено обучению из опыта игры, тогда как ни в одном из алгоритмов динамического программирования мы на самом деле ни в какие игры не играли. У нас была полная модель среды, включая и вероятности перехода состояний. Возникает вопрос, можно ли предположить, что у нас будет такая информация в реальной среде? Для настольных игр – может быть, но как насчёт беспилотных автомобилей? Способ реализации наших алгоритмов динамического программирования требует, чтобы мы поместили агента в определённое состояние, что не всегда возможно, особенно если речь идёт о беспилотном автомобиле или даже видеоигре – в видеоигре мы начинаем в состоянии, которое выбрала сама игра, мы не можем его выбирать. Это ещё один пример возможностей в «режиме бога», так что не очень реально предполагать, что это всегда возможно.

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

«Метод Монте-Карло» – понятие, довольно плохо определённое. Обычно под ним понимается любой алгоритм, включающий значительную случайную составляющую. В случае метода Монте-Карло в обучении с подкреплением случайной составляющей является отдача. Напомню, что мы всегда рассматриваем ожидаемую отдачу при нахождении в состоянии s. В методе Монте-Карло вместо вычисления истинной ожидаемой ценности, требующей распределений вероятностей, мы берём среднее значение выборки. В связи с этим необходимо считать, что мы выполняем лишь эпизодические задачи. Дело в том, что эпизод должен завершиться, прежде чем мы сможем вычислить какую-либо отдачу. Это также значит, что методы Монте-Карло являются не совсем оперативными алгоритмами: мы делаем обновление не после каждого действия, а после каждого эпизода.

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

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

Оценка стратегии методом Монте-Карло

Решим проблему предсказания с использованием оценки методом Монте-Карло.

Напомним  определение функции ценности. Это ожидаемое значение будущей отдачи при условии текущего пребывания в состоянии s:

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

где i – индекс эпизода, s – индекс состояния.

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

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

Тут возникает интересный вопрос: а что, если нам в эпизоде встретится одно и то же состояние более одного раза, например, если получится состояние s и в момент времени t = 1, и в момент t = 3? Какова отдача для состояния s? На этот вопрос есть два ответа, и, как ни странно, оба приводят к одному и тому же результату. Первый метод называется методом Монте-Карло первого посещения. Это значит, что мы учитываем только отдачу для момента t = 1. Второй метод называется методом Монте-Карло постоянного посещения, что значит, что мы вычисляем отдачу каждый раз, попадая в состояние s, и все они будут вносить вклад в среднее значение выборки.

Рассмотрим  теперь псевдокод для предсказания методом Монте-Карло, в частности, в версии первого посещения:

def first_visit_monte_carlo_prediction(π, N)

    V = инициация случайным образом

    all_returns = {}  # по умолчанию = []

    выполнить N раз:

        states, returns = play_episode

        for s, g in zip (states, returns):

            если s ещё не встречалось в этом эпизоде:

                all_returns[s].append(g)

                V(s) = sample_mean(all_returns[s])

    return V

Аргументами  функции являются стратегия и количество примеров, которое хотим сгенерировать. Мы инициируем случайным образом V и создаём словарь для хранения наших отдач со значением по умолчанию в виде пустого списка. После этого повторяем цикл N раз. В теле цикла мы генерируем эпизод, сыграв в игру, а затем перебираем последовательности состояний и отдач, однако отдача включается, только если мы впервые столкнулись с данным состоянием в данном эпизоде, поскольку это метод Монте-Карло первого посещения. Если это так, то мы добавляем отдачу в наш список отдач для этого состояния. Далее мы обновляем V(s) в качестве среднего значения выборки по всем отдачам, собранным для данного состояния. В конце мы возвращаем V.

Как вы могли заметить из псевдокода, от нас требуется сохранять все отдачи, полученные для каждого состояния, чтобы можно было вычислить среднее значение выборки. Однако, если вы помните часть, посвящённую многорукому бандиту, есть более эффективные способы вычисления среднего значения, например – через предыдущее среднее значение. Существуют методы и для нестационарных задач вроде скользящего среднего, так что все уже изученные вами ранее методы работают и тут.

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

Для  полноты картины я покажу и псевдокод для вычисления отдач.

s = grid.current_state()

states_and_rewards = [(s, 0)]

while not game_over:

    a = policy(s)

    r = grid.move(a)

    s = grid.current_state()

    states_and_rewards.append((s, r))

G = 0

states_and_returns = []

for s, r in reversed (states_and_rewards):

    states_and_returns.append((s, G))

    G = r + gamma*G

states_and_returns.reverse()

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

Второй  блок кода предназначен для вычисления отдач. Мы начинаем с пустого списка, а затем по циклу перебираем состояния и вознаграждения в обратном порядке. Заметьте, что на первой итерации этого цикла состояние s представляет конечное состояние, а G = 0, что логично, поскольку ценность любого конечного состояния должна быть равна нулю. Далее мы идёт обновление G. Обратите внимание, что на первой итерации цикла оно включает вознаграждение для конечного состояния. Когда цикл завершается, мы идём по списку состояний и вознаграждений в обратном порядке, поскольку он должен идти в том же порядке, в котором мы попадали в состояния.

И последнее замечание относительно метода Монте-Карло. Напомним, что одним из недостатков динамического программирования является то, что нам приходится перебирать весь набор состояний на каждой итерации, что не подходит для большинства практических ситуаций, где число состояний огромно. Обратите внимание, что метод Монте-Карло обновляет ценность только тех состояний, в которых мы действительно побывали. Это значит, что даже если пространство состояний велико, но мы попадали лишь в небольшое подмножество состояний, это не имеет значения. Стоит отметить и то, что в методе Монте-Карло нам даже не нужно знать, какие это состояния, – мы можем их просто исследовать, сыграв в игру. Таким образом, у метода Монте-Карло есть ряд преимуществ в случаях, когда выполнение полных точных расчётов является невозможным.

Оценка стратегии методом Монте-Карло в коде

Теперь воплотим в коде метод Монте-Карло для нахождения функции ценности состояний. Если вы не хотите писать код самостоятельно, хотя я настоятельно рекомендую сделать именно так, то соответствующий этой лекции файл называется monte_carlo.py.

Вначале у нас идут обычные импорты. Мы импортируем как standard_grid, так и negative_grid, и я рекомендую испытать их обоих, а также, как обычно, функции print_values и print_policy, которые мы определили ранее.

import numpy as np

from grid_world import standard_grid, negative_grid

from iterative_policy_evaluation import print_values, print_policy

Константы тоже прежние.

SMALL_ENOUGH = 10e-4

GAMMA = 0.9

ALL_POSSIBLE_ACTIONS = (‘U’, ‘D’, ‘L’, ‘R’)

# NOTE this is only policy evaluation, not optimization

Далее у нас идёт функция play_game, в качестве аргументов принимающая мир-решётку и стратегию. Стратегия у нас та же, что и была ранее, – пройти слева вверх до целевого состояния, а для всех состояний, не находящихся на этом пути, – двигаться к проигрышному состоянию. Поскольку в методе Монте-Карло вычисляется ценность только тех состояний, в которых мы действительно побывали, а мы всегда начинаем с заранее предопределённого начального состояния, то будут некоторые состояния, в которых мы никогда не побываем. В связи с этим нам нужно немного видоизменить игру, чтобы можно было начать её с любого состояния. Это называется методом исследования начала, и мы обсудим его подробнее позже.

def play_game(grid, policy)

  # returns a list of states and corresponding returns

  # reset game to start at a random position

  # we need to do this, because given our current deterministic policy

  # we would never end up at certain states, but we still want to measure their value

  start_states = grid.actions.keys()

  start_idx = np.random.choice(len(start_states))

  grid.set_state(start_states[start_idx])

Далее  мы играем. Код тут во многом совпадает с псевдокодом, показанным мною ранее. Целью является составить список всех посещённых состояний и полученных  вознаграждений. Далее вычисляются отдачи для каждого состояния. Вновь-таки, тут в точности повторяется показанный ранее псевдокод: мы обращаемся к каждому состоянию в обратном порядке и рекурсивно вычисляем отдачу. В конце мы «переворачиваем» список отдач, поскольку он должен идти в хронологическом  порядке, ведь у нас метод Монте-Карло первого посещения.

  s = grid.current_state()

  states_and_rewards = [(s, 0)] # list of tuples of (state, reward)

  while not grid.game_over()

    a = policy[s]

    r = grid.move(a)

    s = grid.current_state()

    states_and_rewards.append((s, r))

  # calculate the returns by working backwards from the terminal state

  G = 0

  states_and_returns = []

  first = True

  for s, r in reversed(states_and_rewards)

    # the value of the terminal state is 0 by definition

    # we should ignore the first state we encounter

    # and ignore the last G, which is meaningless since it doesn’t correspond to any move

    if first

      first = False

    else

      states_and_returns.append((s, G))

    G = r + GAMMAG

  states_and_returns.reverse() # we want it to be in order of state visited

  return states_and_returns

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

if __name__ == ‘__main__’

  # use the standard grid again (0 for every step) so that we can compare

  # to iterative policy evaluation

  grid = standard_grid()

  # print rewards

  print rewards

  print_values(grid.rewards, grid)

  # state – action

  policy = {

    (2, 0) ‘U’,

    (1, 0) ‘U’,

    (0, 0) ‘R’,

    (0, 1) ‘R’,

    (0, 2) ‘R’,

    (1, 2) ‘R’,

    (2, 1) ‘R’,

    (2, 2) ‘R’,

    (2, 3) ‘U’,

  }

  # initialize V(s) and returns

  V = {}

  returns = {} # dictionary of state – list of returns we’ve received

  states = grid.all_states()

  for s in states

    if s in grid.actions

      returns[s] = []

    else

      # terminal state or state we can’t otherwise get to

      V[s] = 0

Далее у нас идёт цикл метода Монте-Карло, в котором мы играем и получаем список состояний и отдач. После этого мы создаём набор для отслеживания всех увиденных состояний, ведь нам необходимо добавить отдачу только при первом появлении  данного состояния в эпизоде. Затем мы перебираем все состояния и отдачи. Если состояние встретилось нам впервые, мы добавляем его в наш список отдач для этого состояния, после чего заново вычисляем V(s). Обратите внимание, что мы тут не делаем ничего особенного для вычисления среднего значения, просто используя  определение по умолчанию, после чего добавляем s в список виденных состояний.

В конце мы выводим на экран вычисленные ценности и использованную стратегию.

  # repeat

  for t in xrange(100)

    # generate an episode using pi

    states_and_returns = play_game(grid, policy)

    seen_states = set()

    for s, G in states_and_returns

      # check if we have already seen s

      # called first-visit MC policy evaluation

      if s not in seen_states

        returns[s].append(G)

        V[s] = np.mean(returns[s])

        seen_states.add(s)

  print values

  print_values(V, grid)

  print policy

  print_policy(policy, grid)

Итак, запустим программу и посмотрим, что получится.

Похоже, получилось ровно то же самое, что и при итерационной оценке ценности.

Оценка ценности в мире-решётке с ветром

Используем аналогичный алгоритм предсказания Монте-Карло для нахождения V, но на этот раз события будут происходить в мире-решётке с ветром, а мы используем несколько иную стратегию.

В последнем скрипте вы могли заметить, что на самом деле метод Монте-Карло был не очень-то и нужен, поскольку отдачи являлись определёнными (детерминированными). Это связано с тем обстоятельством, что оба интересующих нас распределения вероятностей – π(a|s) и p(s’,r|s,a) – также были детерминированными. В мире-решётке с ветром переходы состояний таковыми не являются, поэтому у нас будет источник неопределённости и, следовательно, придётся использовать метод Монте-Карло. Кроме того, изменится и стратегия, в частности, при данной стратегии мы всегда будем стараться выиграть или, другими словами, дойти до целевого состояния. Мы увидим, что несмотря на то, что эта стратегия заключается в достижении целевого состояния, не все ценности будут положительными, поскольку в мире-решётке с ветром последний может в конце концов столкнуть нас в проигрышное состояние. Следовательно, средняя отдача от такого состояния является отрицательной.

Если вы не хотите писать код сами, хотя я настоятельно рекомендую именно это, то соответствующий файл в репозитарии называется monte_carlo_random.py.

Итак, вначале идут все те же обычные импорты библиотек и константы, что и в обычном скрипте для метода Монте-Карло.

import numpy as np

from grid_world import standard_grid, negative_grid

from iterative_policy_evaluation import print_values, print_policy

SMALL_ENOUGH = 10e-4

GAMMA = 0.9

ALL_POSSIBLE_ACTIONS = (‘U’, ‘D’, ‘L’, ‘R’)

# NOTE: this is only policy evaluation, not optimization

Дальше появляется функция random_action. Работает она так же, как и в предыдущем мире-решётке: у нас есть вероятность 0,5, что будет выполнено запланированное действие, и вероятность 0,5/3 – что какое-то другое.

def random_action(a):

  # choose given a with probability 0.5

  # choose some other a’ != a with probability 0.5/3

  p = np.random.random()

  if p < 0.5:

    return a

  else:

    tmp = list(ALL_POSSIBLE_ACTIONS)

    tmp.remove(a)

    return np.random.choice(tmp)

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

def play_game(grid, policy):

  # returns a list of states and corresponding returns

  # reset game to start at a random position

  # we need to do this, because given our current deterministic policy

  # we would never end up at certain states, but we still want to measure their value

  start_states = grid.actions.keys()

  start_idx = np.random.choice(len(start_states))

  grid.set_state(start_states[start_idx])

  s = grid.current_state()

  states_and_rewards = [(s, 0)] # list of tuples of (state, reward)

  while not grid.game_over():

    a = policy[s]

    a = random_action(a)

    r = grid.move(a)

    s = grid.current_state()

    states_and_rewards.append((s, r))

  # calculate the returns by working backwards from the terminal state

  G = 0

  states_and_returns = []

  first = True

  for s, r in reversed(states_and_rewards):

    # the value of the terminal state is 0 by definition

    # we should ignore the first state we encounter

    # and ignore the last G, which is meaningless since it doesn’t correspond to any move

    if first:

      first = False

    else:

      states_and_returns.append((s, G))

    G = r + GAMMA*G

  states_and_returns.reverse() # we want it to be in order of state visited

  return states_and_returns

Затем мы переходим к разделу main. У нас та же решётка и вознаграждения, что и ранее, а отличается стратегия. В частности, мы всегда пытаемся достичь цели независимо от состояния, в котором находимся. Так, если мы под стеной, то выбираем путь налево, чтобы, пройдя верхний левый угол, достичь цели. Обратите внимание, что в комментариях я добавил ответ, полученный из итерации по стратегиям. Что замечательно в этих алгоритмах – то, что их можно использовать для перепроверки друг друга. От метода Монте-Карло ожидается очень похожий, но не идентичный ответ.

if __name__ == ‘__main__’:

  # use the standard grid again (0 for every step) so that we can compare

  # to iterative policy evaluation

  grid = standard_grid()

  # print rewards

  print “rewards:”

  print_values(grid.rewards, grid)

  # state -> action

  # found by policy_iteration_random on standard_grid

  # MC method won’t get exactly this, but should be close

  # values:

  # —————————

  #  0.43|  0.56|  0.72|  0.00|

  # —————————

  #  0.33|  0.00|  0.21|  0.00|

  # —————————

  #  0.25|  0.18|  0.11| -0.17|

  # policy:

  # —————————

  #   R  |   R  |   R  |      |

  # —————————

  #   U  |      |   U  |      |

  # —————————

  #   U  |   L  |   U  |   L  |

  policy = {

    (2, 0): ‘U’,

    (1, 0): ‘U’,

    (0, 0): ‘R’,

    (0, 1): ‘R’,

    (0, 2): ‘R’,

    (1, 2): ‘U’,

    (2, 1): ‘L’,

    (2, 2): ‘U’,

    (2, 3): ‘L’,

  }

  # initialize V(s) and returns

  V = {}

  returns = {} # dictionary of state -> list of returns we’ve received

  states = grid.all_states()

  for s in states:

    if s in grid.actions:

      returns[s] = []

    else:

      # terminal state or state we can’t otherwise get to

      V[s] = 0

Заметьте, что всё, что дальше, остаётся прежним. Алгоритм Монте-Карло не меняется, поскольку при нахождении средних значений уже учитываются все случайности как в стратегии, так и в переходах состояний.

  # repeat until convergence

  for t in xrange(5000):

    # generate an episode using pi

    states_and_returns = play_game(grid, policy)

    seen_states = set()

    for s, G in states_and_returns:

      # check if we have already seen s

      # called “first-visit” MC policy evaluation

      if s not in seen_states:

        returns[s].append(G)

        V[s] = np.mean(returns[s])

        seen_states.add(s)

  print “values:”

  print_values(V, grid)

  print “policy:”

  print_policy(policy, grid)

Итак, запустим программу и посмотрим, что у нас получится.

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

Андрей Никитенко
Андрей Никитенко
Задать вопрос эксперту
Понравилась статья? Поделить с друзьями:
Комментариев: 2
  1. Евгений

    Хорошо пояснено, но многослитных слов затрудняет чтение

    1. adminCraft

      Здравствуйте Евгений!

      Спасибо что указали на ошибки.

      Сегодня же исправим все что найдем.

Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: