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

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

Здравствуйте и вновь добро пожаловать на занятия по теме «Искусственный интеллект: обучение с подкреплением на языке 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, gin 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, notoptimization

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

def play_game(grid,policy)

  # returns alist of states and corresponding returns

  # reset gameto start at a random position

  # we need todo this, because given our current deterministic policy

  # we wouldnever 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 notgrid.game_over()

    a =policy[s]

    r =grid.move(a)

    s =grid.current_state()

   states_and_rewards.append((s, r))

  # calculatethe returns by working backwards from the terminal state

  G = 0

 states_and_returns = []

  first = True

  for s, r in reversed(states_and_rewards)

    # the valueof the terminal state is 0 by definition

    # we shouldignore the first state we encounter

    # and ignorethe 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 statevisited

  return states_and_returns

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

if __name__ == ‘__main__’

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

  # to iterativepolicy evaluation

  grid =standard_grid()

  # printrewards

  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’,

  }

  # initializeV(s) and returns

  V = {}

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

  states =grid.all_states()

  for s instates

    if s ingrid.actions

      returns[s]= []

    else

      # terminalstate or state we can’t otherwise get to

      V[s] = 0

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

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

  # repeat

  for t in xrange(100)

    # generatean episode using pi

   states_and_returns = play_game(grid, policy)

    seen_states= set()

    for s, G instates_and_returns

      # check ifwe have already seen s

      # calledfirst-visit MC policy evaluation

      if s notin 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, notoptimization

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

def random_action(a):

  # choose givena with probability 0.5

  # choose someother 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)

    returnnp.random.choice(tmp)

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

def play_game(grid,policy):

  # returns alist of states and corresponding returns

  # reset gameto start at a random position

  # we need todo this, because given our current deterministic policy

  # we wouldnever 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 notgrid.game_over():

    a =policy[s]

    a =random_action(a)

    r =grid.move(a)

    s =grid.current_state()

   states_and_rewards.append((s, r))

  # calculatethe returns by working backwards from the terminal state

  G = 0

 states_and_returns = []

  first = True

  for s, r in reversed(states_and_rewards):

    # the valueof the terminal state is 0 by definition

    # we shouldignore the first state we encounter

    # and ignorethe 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 statevisited

  return states_and_returns

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

if __name__ == ‘__main__’:

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

  # to iterativepolicy evaluation

  grid =standard_grid()

  # printrewards

  print“rewards:”

 print_values(grid.rewards, grid)

  # state ->action

  # found bypolicy_iteration_random on standard_grid

  # MC methodwon’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’,

  }

  # initializeV(s) and returns

  V = {}

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

  states =grid.all_states()

  for s instates:

    if s ingrid.actions:

      returns[s]= []

    else:

      # terminalstate or state we can’t otherwise get to

      V[s] = 0

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

  # repeatuntil convergence

  for t in xrange(5000):

    # generatean episode using pi

   states_and_returns = play_game(grid, policy)

    seen_states= set()

    for s, G instates_and_returns:

      # check ifwe have already seen s

      # called“first-visit” MC policy evaluation

      if s notin 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)

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

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

Обратитевнимание, что с точки зрения реализации в коде крайне полезно выполнить цикл посостояниям и вознаграждениям в обратном порядке, поскольку 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, gin 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, notoptimization

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

def play_game(grid,policy)

  # returns alist of states and corresponding returns

  # reset gameto start at a random position

  # we need todo this, because given our current deterministic policy

  # we wouldnever 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 notgrid.game_over()

    a =policy[s]

    r =grid.move(a)

    s =grid.current_state()

   states_and_rewards.append((s, r))

  # calculatethe returns by working backwards from the terminal state

  G = 0

 states_and_returns = []

  first = True

  for s, r in reversed(states_and_rewards)

    # the valueof the terminal state is 0 by definition

    # we shouldignore the first state we encounter

    # and ignorethe 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 statevisited

  return states_and_returns

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

if __name__ == ‘__main__’

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

  # to iterativepolicy evaluation

  grid =standard_grid()

  # printrewards

  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’,

  }

  # initializeV(s) and returns

  V = {}

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

  states =grid.all_states()

  for s instates

    if s ingrid.actions

      returns[s]= []

    else

      # terminalstate or state we can’t otherwise get to

      V[s] = 0

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

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

  # repeat

  for t in xrange(100)

    # generatean episode using pi

   states_and_returns = play_game(grid, policy)

    seen_states= set()

    for s, G instates_and_returns

      # check ifwe have already seen s

      # calledfirst-visit MC policy evaluation

      if s notin 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, notoptimization

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

def random_action(a):

  # choose givena with probability 0.5

  # choose someother 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)

    returnnp.random.choice(tmp)

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

def play_game(grid,policy):

  # returns alist of states and corresponding returns

  # reset gameto start at a random position

  # we need todo this, because given our current deterministic policy

  # we wouldnever 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 notgrid.game_over():

    a =policy[s]

    a =random_action(a)

    r =grid.move(a)

    s =grid.current_state()

   states_and_rewards.append((s, r))

  # calculatethe returns by working backwards from the terminal state

  G = 0

 states_and_returns = []

  first = True

  for s, r in reversed(states_and_rewards):

    # the valueof the terminal state is 0 by definition

    # we shouldignore the first state we encounter

    # and ignorethe 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 statevisited

  return states_and_returns

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

if __name__ == ‘__main__’:

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

  # to iterativepolicy evaluation

  grid =standard_grid()

  # printrewards

  print“rewards:”

 print_values(grid.rewards, grid)

  # state ->action

  # found bypolicy_iteration_random on standard_grid

  # MC methodwon’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’,

  }

  # initializeV(s) and returns

  V = {}

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

  states =grid.all_states()

  for s instates:

    if s ingrid.actions:

      returns[s]= []

    else:

      # terminalstate or state we can’t otherwise get to

      V[s] = 0

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

  # repeatuntil convergence

  for t in xrange(5000):

    # generatean episode using pi

   states_and_returns = play_game(grid, policy)

    seen_states= set()

    for s, G instates_and_returns:

      # check ifwe have already seen s

      # called“first-visit” MC policy evaluation

      if s notin 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)

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

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

Понравилась статья? Поделить с друзьями:
Добавить комментарий

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