Нахождение оптимальной стратегии методом Монте-Карло

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

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

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

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

Надопонимать, что при этом мы сталкиваемся с серьёзной проблемой. Заключается она вследующем: у нас есть только V(s) для заданной стратегии, но мы не знаем,какие действия приводят к лучшей V(s), поскольку не можем провести упреждающийпоиск. В методе Монте-Карло всё, что мы можем, – это лишь напрямую сыгратьэпизод и использовать отдачи в качестве примеров. Таким образом, ключевымвопросом в использовании метода Монте-Карло для решения проблемы управлениястановится нахождение Q, поскольку оно индексируется и через s, и через a, а значит, мыможем использовать argmax по a, чтобыопределить лучшую стратегию.

Какже использовать метод Монте-Карло, чтобы найти Q? Процесс во многом схож с поиском V, разве чтовместо возвращения кортежей состояний и отдач будут возвращаться кортежисостояний, действий и отдач. Уже тут становится понятно, почему это может бытьпроблематично. Напомню, что количество значений, которое необходимо сохранять,увеличивается по квадратичному закону в зависимости от размера набора состоянийи размера набора действий. Это значит, что у нас теперь намного больше значенийдля приближений, а значит, нам необходимо выполнить намного больше цикломМонте-Карло, чтобы получить удовлетворительный ответ.

Естьи другая проблема, заставляющая нас вернуться к дилемме исследования ииспользования. Если у нас фиксированная стратегия, то каждое Q(s) будет иметьпримеры только из одного действия. Это значит, что вместо |S|*|A| значений,которые нужно заполнить, мы сможем сделать это только для 1/|A| значений.

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

Теперьмы можем вернуться к нашей проблеме управления. Если вы хорошенько подумаете,то поймёте, что уже знаете ответ. Ранее говорилось, что для нахожденияоптимальной стратегии всегда можно использовать метод обобщённой итерации постратегиям, когда мы чередуем оценку стратегии и её совершенствование. Дляоценки стратегии, как мы только что обсудили, можно использовать методМонте-Карло для получения оценки Q. Этап же совершенствования стратегии остаётсяобычным: мы просто берём argmax по всемдействиям от Q:

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

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

Посмотрим,как это выглядит в виде псевдокода, чтобы развить данную идею:

Q = случайное, pi= случайное

while True:

    s, a = случайным образом выбранные из S и A

    states_actions_returns= play_game(start=(s, a))

    for s, a, Gin states_actions_returns:

       returns(s, a).append(G)

        Q(s, a)= average(returns(s, a))

    for s instates:

        pi(s) =argmax[a]{ Q(s, a) }

Первыйэтап – инициация Qи π случайным образом. Затем вбесконечном цикле мы вначале выбираем случайное состояние и случайное действие,с которых и начинаем, – не забывайте, этот метод называется методомисследования начала. Затем мы генерируем эпизод из этой начальной позиции иследуем текущей стратегии. Отсюда мы получаем список кортежей, содержащийсостояния, действия и отдачи. Их мы добавляем к словарю отдач, привязанных кпарам состояние-действие. Далее мы пересчитываем Q(s,a) как среднее всех отдач для этой парысостояние-действие. После этого выполняется этап совершенствования стратегии,который должен указать на действие – argmax по Q.

Обратитевнимание, что у этого алгоритма есть одна неочевидная проблема. Напомню, чтоесли мы выполняем действие, приводящее к столкновению со стеной, то оказываемсяв том же состоянии, что и прежде. Таким образом, если мы будем следовать такойстратегии, то никогда не закончим в конечном состоянии и, соответственно,никогда не закончим эпизод. Чтобы избежать этого, мы введём изменение, прикотором если мы после выполнения действия остаёмся в том же состоянии, тополучаем вознаграждение в -100, что ниже, чем любое другое вознаграждение всреде, и заканчиваем эпизод.

Любопытно, что в данном методе имеет место сходимость, даже если отдачи, собранные для Q, относятся к разным стратегиям. Интуитивно понятно, что Q должно сходиться, поскольку если Q не оптимально, то стратегия изменится, что, в свою очередь, приведёт к изменению Q. Стабильности мы можем достичь лишь в том случае, когда и ценность, и стратегия сходятся к оптимальной ценности и оптимальной стратегии. Интересно и то, что это так никогда и не было формально доказано.

Управление методом Монте-Карло в коде

Используем метод исследования начала Монте-Карло для решения проблемы управления или, другими словами, нахождения оптимальной стратегии и оптимальной функции ценности. Если вы не хотите писать код самостоятельно, хотя я настоятельно рекомендую сделать именно так, то соответствующий файл в репозитарии называется monte_carlo_es.py.

Мыначинаем с нашего обычного импорта библиотек и констант.

import numpy as np

import matplotlib.pyplot as plt

from grid_world import standard_grid, negative_grid

from iterative_policy_evaluation import print_values,print_policy

GAMMA = 0.9

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

# NOTE: this script implements the Monte CarloExploring-Starts method

#       forfinding the optimal policy

Далее идёт функция 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 if we have a deterministic policy

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

  # this iscalled the “exploring starts” method

  start_states =grid.actions.keys()

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

 grid.set_state(start_states[start_idx])

  s =grid.current_state()

  a =np.random.choice(ALL_POSSIBLE_ACTIONS) # first action is uniformly random

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

  # beaware of the timing

  # each tripleis s(t), a(t), r(t)

  # but r(t)results from taking action a(t-1) from s(t-1) and landing in s(t)

 states_actions_rewards = [(s, a, 0)]

  seen_states =set()

  while True:

    old_s =grid.current_state()

    r =grid.move(a)

    s =grid.current_state()

    if s inseen_states:

      # hack sothat we don’t end up in an infinitely long episode

      # bumpinginto the wall repeatedly

     states_actions_rewards.append((s, None, -100))

      break

    elifgrid.game_over():

     states_actions_rewards.append((s, None, r))

      break

    else:

      a =policy[s]

     states_actions_rewards.append((s, a, r))

    seen_states.add(s)

Затеммы вычисляем отдачи. В основном тут всё то же самое, разве что мы добавляем ещёи действия.

  #calculate the returns by working backwards from the terminal state

  G = 0

 states_actions_returns = []

  first = True

  for s, a, r inreversed(states_actions_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_actions_returns.append((s,a, G))

    G = r +GAMMA*G

 states_actions_returns.reverse() # we want it to be in order of statevisited

  return states_actions_returns

Далее у нас идёт специальная функция, которая одновременно находит argmax и максимум по словарю, который будет использоваться для хранения Q. Она возвращает ключ для максимальной ценности и саму максимальную ценность.

def max_dict(d):

  # returns theargmax (key) and max (value) from a dictionary

  # put thisinto a function since we are using it so often

  max_key = None

  max_val = float(‘-inf’)

  for k, v ind.iteritems():

    if v >max_val:

      max_val =v

      max_key =k

  returnmax_key, max_val

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

if __name__ == ‘__main__’:

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

  # to iterativepolicy evaluation

  # grid =standard_grid()

  # try thenegative grid too, to see if agent will learn to go past the “badspot”

  # in order tominimize number of steps

  grid =negative_grid(step_cost=-0.9)

  # printrewards

  print“rewards:”

  print_values(grid.rewards,grid)

  # state ->action

  # initialize arandom policy

  policy = {}

  for s ingrid.actions.keys():

    policy[s] =np.random.choice(ALL_POSSIBLE_ACTIONS)

Затеминициируем Q и наш словарь отдач. Обратите внимание, что дажехотя Qне строго обязательно инициировать для выполнения оценки стратегии, это нужнодля случая, когда мы находим argmax, а ценности ещёне установлены.

  #initialize Q(s,a) and returns

  Q = {}

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

  states =grid.all_states()

  for s instates:

    if s ingrid.actions: # not a terminal state

      Q[s] = {}

      for a inALL_POSSIBLE_ACTIONS:

        Q[s][a]= 0 # needs to be initialized to something so we can argmax it

       returns[(s,a)] = []

    else:

      # terminalstate or state we can’t otherwise get to

      pass

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

  # repeatuntil convergence

  deltas = []

  for t in xrange(2000):

    if t % 100 == 0:

      print t

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

    #generate an episode using pi

   biggest_change = 0

   states_actions_returns = play_game(grid, policy)

   seen_state_action_pairs = set()

    for s, a, Gin states_actions_returns:

      # check ifwe have already seen s

      # called“first-visit” MC policy evaluation

      sa = (s, a)

      if sa notin seen_state_action_pairs:

        old_q =Q[s][a]

       returns[sa].append(G)

        Q[s][a]= np.mean(returns[sa])

       biggest_change = max(biggest_change, np.abs(old_q – Q[s][a]))

       seen_state_action_pairs.add(sa)

   deltas.append(biggest_change)

    # updatepolicy

    for s inpolicy.keys():

      policy[s]= max_dict(Q[s])[0]

Далеемы выводим на экран Δ и оптимальнуюстратегию. Обратите внимание, что с помощью Q мы можем найти и оптимальную функцию ценностисостояний, что мы и делаем, также с выводом на экран.

  plt.plot(deltas)

  plt.show()

  print“final policy:”

 print_policy(policy, grid)

  # find V

  V = {}

  for s, Qs inQ.iteritems():

    V[s] =max_dict(Q[s])[1]

  print“final values:”

 print_values(V, grid)

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

Обратите внимание, что у нас имеется несколько сотен в Δ. Это потому, что начальная стратегия содержала действия, приводящие к столкновению со стеной. Однако окончательная стратегия вполне логична, как и ценности.

Управление методом Монте-Карло без исследования начала

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

Напомню, что в этой части уже говорилось, что все изученные методы решения задачи о многоруком бандите тут вполне применимы. В частности, мы можем следовать не жадной, а эпсилон-жадной стратегии или любому другому методу, позволяющему нам больше исследовать. Изменения в коде должны быть достаточно простыми: всё, что нужно сделать, – это убрать часть, где выполняется исследование начала, а вместо этого начинать только с официальной стартовой позиции. Кроме того, в части кода, посвящённой игре, вместо следования жадной стратегии мы должны иметь небольшую вероятность ε выполнения случайного действия.

Обратитевнимание, что в некоторых источниках можно встретить так называемыйэпсилон-мягкий алгоритм. Он немного отличается по виду, но по сути делает то жесамое. Идея, лежащая в его основе, в том, что ε используется как гарантия того, что любое действие имеетвероятность быть выбранным. Это следует из того, что вероятность (a|s) больше или равна ε, делённому на количество возможных действий:

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

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

Посмотрим,как это выглядит в виде псевдокода, чтобы развить данную идею:

Q = случайное, pi= случайное

while True:

    s, a = случайным образом выбранные из S и A

    states_actions_returns= play_game(start=(s, a))

    for s, a, Gin states_actions_returns:

       returns(s, a).append(G)

        Q(s, a)= average(returns(s, a))

    for s instates:

        pi(s) =argmax[a]{ Q(s, a) }

Первыйэтап – инициация Qи π случайным образом. Затем вбесконечном цикле мы вначале выбираем случайное состояние и случайное действие,с которых и начинаем, – не забывайте, этот метод называется методомисследования начала. Затем мы генерируем эпизод из этой начальной позиции иследуем текущей стратегии. Отсюда мы получаем список кортежей, содержащийсостояния, действия и отдачи. Их мы добавляем к словарю отдач, привязанных кпарам состояние-действие. Далее мы пересчитываем Q(s,a) как среднее всех отдач для этой парысостояние-действие. После этого выполняется этап совершенствования стратегии,который должен указать на действие – argmax по Q.

Обратитевнимание, что у этого алгоритма есть одна неочевидная проблема. Напомню, чтоесли мы выполняем действие, приводящее к столкновению со стеной, то оказываемсяв том же состоянии, что и прежде. Таким образом, если мы будем следовать такойстратегии, то никогда не закончим в конечном состоянии и, соответственно,никогда не закончим эпизод. Чтобы избежать этого, мы введём изменение, прикотором если мы после выполнения действия остаёмся в том же состоянии, тополучаем вознаграждение в -100, что ниже, чем любое другое вознаграждение всреде, и заканчиваем эпизод.

Любопытно, что в данном методе имеет место сходимость, даже если отдачи, собранные для Q, относятся к разным стратегиям. Интуитивно понятно, что Q должно сходиться, поскольку если Q не оптимально, то стратегия изменится, что, в свою очередь, приведёт к изменению Q. Стабильности мы можем достичь лишь в том случае, когда и ценность, и стратегия сходятся к оптимальной ценности и оптимальной стратегии. Интересно и то, что это так никогда и не было формально доказано.

Управление методом Монте-Карло в коде

Используем метод исследования начала Монте-Карло для решения проблемы управления или, другими словами, нахождения оптимальной стратегии и оптимальной функции ценности. Если вы не хотите писать код самостоятельно, хотя я настоятельно рекомендую сделать именно так, то соответствующий файл в репозитарии называется monte_carlo_es.py.

Мыначинаем с нашего обычного импорта библиотек и констант.

import numpy as np

import matplotlib.pyplot as plt

from grid_world import standard_grid, negative_grid

from iterative_policy_evaluation import print_values,print_policy

GAMMA = 0.9

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

# NOTE: this script implements the Monte CarloExploring-Starts method

#       forfinding the optimal policy

Далее идёт функция 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 if we have a deterministic policy

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

  # this iscalled the “exploring starts” method

  start_states =grid.actions.keys()

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

 grid.set_state(start_states[start_idx])

  s =grid.current_state()

  a =np.random.choice(ALL_POSSIBLE_ACTIONS) # first action is uniformly random

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

  # beaware of the timing

  # each tripleis s(t), a(t), r(t)

  # but r(t)results from taking action a(t-1) from s(t-1) and landing in s(t)

 states_actions_rewards = [(s, a, 0)]

  seen_states =set()

  while True:

    old_s =grid.current_state()

    r =grid.move(a)

    s =grid.current_state()

    if s inseen_states:

      # hack sothat we don’t end up in an infinitely long episode

      # bumpinginto the wall repeatedly

     states_actions_rewards.append((s, None, -100))

      break

    elifgrid.game_over():

     states_actions_rewards.append((s, None, r))

      break

    else:

      a =policy[s]

     states_actions_rewards.append((s, a, r))

    seen_states.add(s)

Затеммы вычисляем отдачи. В основном тут всё то же самое, разве что мы добавляем ещёи действия.

  #calculate the returns by working backwards from the terminal state

  G = 0

 states_actions_returns = []

  first = True

  for s, a, r inreversed(states_actions_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_actions_returns.append((s,a, G))

    G = r +GAMMA*G

 states_actions_returns.reverse() # we want it to be in order of statevisited

  return states_actions_returns

Далее у нас идёт специальная функция, которая одновременно находит argmax и максимум по словарю, который будет использоваться для хранения Q. Она возвращает ключ для максимальной ценности и саму максимальную ценность.

def max_dict(d):

  # returns theargmax (key) and max (value) from a dictionary

  # put thisinto a function since we are using it so often

  max_key = None

  max_val = float(‘-inf’)

  for k, v ind.iteritems():

    if v >max_val:

      max_val =v

      max_key =k

  returnmax_key, max_val

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

if __name__ == ‘__main__’:

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

  # to iterativepolicy evaluation

  # grid =standard_grid()

  # try thenegative grid too, to see if agent will learn to go past the “badspot”

  # in order tominimize number of steps

  grid =negative_grid(step_cost=-0.9)

  # printrewards

  print“rewards:”

  print_values(grid.rewards,grid)

  # state ->action

  # initialize arandom policy

  policy = {}

  for s ingrid.actions.keys():

    policy[s] =np.random.choice(ALL_POSSIBLE_ACTIONS)

Затеминициируем Q и наш словарь отдач. Обратите внимание, что дажехотя Qне строго обязательно инициировать для выполнения оценки стратегии, это нужнодля случая, когда мы находим argmax, а ценности ещёне установлены.

  #initialize Q(s,a) and returns

  Q = {}

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

  states =grid.all_states()

  for s instates:

    if s ingrid.actions: # not a terminal state

      Q[s] = {}

      for a inALL_POSSIBLE_ACTIONS:

        Q[s][a]= 0 # needs to be initialized to something so we can argmax it

       returns[(s,a)] = []

    else:

      # terminalstate or state we can’t otherwise get to

      pass

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

  # repeatuntil convergence

  deltas = []

  for t in xrange(2000):

    if t % 100 == 0:

      print t

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

    #generate an episode using pi

   biggest_change = 0

   states_actions_returns = play_game(grid, policy)

   seen_state_action_pairs = set()

    for s, a, Gin states_actions_returns:

      # check ifwe have already seen s

      # called“first-visit” MC policy evaluation

      sa = (s, a)

      if sa notin seen_state_action_pairs:

        old_q =Q[s][a]

       returns[sa].append(G)

        Q[s][a]= np.mean(returns[sa])

       biggest_change = max(biggest_change, np.abs(old_q – Q[s][a]))

       seen_state_action_pairs.add(sa)

   deltas.append(biggest_change)

    # updatepolicy

    for s inpolicy.keys():

      policy[s]= max_dict(Q[s])[0]

Далеемы выводим на экран Δ и оптимальнуюстратегию. Обратите внимание, что с помощью Q мы можем найти и оптимальную функцию ценностисостояний, что мы и делаем, также с выводом на экран.

  plt.plot(deltas)

  plt.show()

  print“final policy:”

 print_policy(policy, grid)

  # find V

  V = {}

  for s, Qs inQ.iteritems():

    V[s] =max_dict(Q[s])[1]

  print“final values:”

 print_values(V, grid)

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

Обратите внимание, что у нас имеется несколько сотен в Δ. Это потому, что начальная стратегия содержала действия, приводящие к столкновению со стеной. Однако окончательная стратегия вполне логична, как и ценности.

Управление методом Монте-Карло без исследования начала

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

Напомню, что в этой части уже говорилось, что все изученные методы решения задачи о многоруком бандите тут вполне применимы. В частности, мы можем следовать не жадной, а эпсилон-жадной стратегии или любому другому методу, позволяющему нам больше исследовать. Изменения в коде должны быть достаточно простыми: всё, что нужно сделать, – это убрать часть, где выполняется исследование начала, а вместо этого начинать только с официальной стартовой позиции. Кроме того, в части кода, посвящённой игре, вместо следования жадной стратегии мы должны иметь небольшую вероятность ε выполнения случайного действия.

Обратитевнимание, что в некоторых источниках можно встретить так называемыйэпсилон-мягкий алгоритм. Он немного отличается по виду, но по сути делает то жесамое. Идея, лежащая в его основе, в том, что ε используется как гарантия того, что любое действие имеетвероятность быть выбранным. Это следует из того, что вероятность (a|s) больше или равна ε, делённому на количество возможных действий:

Номы также используем ε и для того,чтобы решить, будет ли проводиться исследование или нет, а потому можемзаписать:

Отнынемы тоже будем считать это эпсилон-жадным алгоритмом.

Любопытнопосмотреть, какой будет вероятность достижения состояния, которое не являетсячастью траектории, определённой стратегией. Пусть мы находимся в состоянии,отстоящем на Kшагов от начального, пребываем в режиме исследования на каждом этапе  и выбираем состояния, необходимые длядостижения целевого. Тогда общая вероятность будет равна

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

Управление методом Монте-Карло без исследования начала в коде

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

Начинаеммы со всех прежних импортов библиотек и констант.

import numpy as np

import matplotlib.pyplot as plt

from grid_world import standard_grid, negative_grid

from iterative_policy_evaluation import print_values,print_policy

from monte_carlo_es import max_dict

GAMMA = 0.9

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

# NOTE: find optimal policy and value function

#       usingon-policy first-visit MC

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

def random_action(a,eps=0.1):

  # choose givena with probability 1 – eps + eps/4

  # choose someother a’ != a with probability eps/4

  p =np.random.random()

  # if p < (1– eps + eps/len(ALL_POSSIBLE_ACTIONS)):

  #   return a

  # else:

  #   tmp = list(ALL_POSSIBLE_ACTIONS)

  #   tmp.remove(a)

  #   return np.random.choice(tmp)

  #

  # this isequivalent to the above

  if p < (1 –eps):

    return a

  else:

    returnnp.random.choice(ALL_POSSIBLE_ACTIONS)

Далее у нас идёт функция play_game. Обратите внимание, на то, что мы убрали код исследования начала и теперь всегда начинаем с позиции (2, 0), а также на строку, где добавлена эпсилон-жадная стратегия, в которой используется описанная выше функция random_action.

def play_game(grid,policy):

  # returns alist of states and corresponding returns

  # in thisversion we will NOT use “exploring starts” method

  # instead wewill explore using an epsilon-soft policy

  s = (2, 0)

 grid.set_state(s)

  a =random_action(policy[s])

  # be aware ofthe timing

  # each tripleis s(t), a(t), r(t)

  # but r(t)results from taking action a(t-1) from s(t-1) and landing in s(t)

 states_actions_rewards = [(s, a, 0)]

  while True:

    r =grid.move(a)

    s =grid.current_state()

    ifgrid.game_over():

      states_actions_rewards.append((s, None, r))

      break

    else:

      a =random_action(policy[s]) # the next state is stochastic

     states_actions_rewards.append((s, a, r))

Отдачивычисляются точно так же, как и ранее.

  #calculate the returns by working backwards from the terminal state

  G = 0

 states_actions_returns = []

  first = True

  for s, a, r inreversed(states_actions_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_actions_returns.append((s, a, G))

    G = r +GAMMA*G

 states_actions_returns.reverse() # we want it to be in order of statevisited

  returnstates_actions_returns

Далее мы переходим к разделу main. Заметьте, тут всё в точности то же, что и прежде; единственное отличие этого алгоритма – в том, как выполняется итерация по стратегиям, а точнее, какая стратегия используется для игры. Мы запускаем negative_grid, выводим на экран вознаграждения, инициируем случайную стратегию и случайное Q. Обратите внимание, что нам необходимо инициировать Q, хоть это и не нужно для решения задачи оценки. Это связано с тем, что когда позже мы выполняем argmax, нам нужны значения ценностей, из которых будем выбирать.

if __name__ == ‘__main__’:

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

  # to iterativepolicy evaluation

  # grid =standard_grid()

  # try thenegative grid too, to see if agent will learn to go past the “badspot”

  # in order tominimize number of steps

  grid =negative_grid(step_cost=-0.1)

  # printrewards

  print“rewards:”

 print_values(grid.rewards, grid)

  # state ->action

  # initialize arandom policy

  policy = {}

  for s ingrid.actions.keys():

    policy[s] =np.random.choice(ALL_POSSIBLE_ACTIONS)

  # initializeQ(s,a) and returns

  Q = {}

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

  states =grid.all_states()

  for s instates:

    if s ingrid.actions: # not a terminal state

      Q[s] = {}

      for a inALL_POSSIBLE_ACTIONS:

        Q[s][a]= 0

        returns[(s,a)]= []

    else:

      # terminalstate or state we can’t otherwise get to

      pass

  # repeat untilconvergence

  deltas = []

  for t in xrange(5000):

    if t % 1000== 0:

      print t

    # generatean episode using pi

   biggest_change = 0

   states_actions_returns = play_game(grid, policy)

Восновном цикле мы вновь-таки отслеживаем максимальное Δ, чтобы потом можно было вывести изменения по мере продвижения.

    # calculateQ(s,a)

    seen_state_action_pairs= set()

    for s, a, Gin states_actions_returns:

      # check ifwe have already seen s

      # called“first-visit” MC policy evaluation

      sa = (s,a)

      if sa notin seen_state_action_pairs:

        old_q =Q[s][a]

       returns[sa].append(G)

        Q[s][a] = np.mean(returns[sa])

       biggest_change = max(biggest_change, np.abs(old_q – Q[s][a]))

       seen_state_action_pairs.add(sa)

   deltas.append(biggest_change)

    # calculatenew policy pi(s) = argmax[a]{ Q(s,a) }

    for s inpolicy.keys():

      a, _ =max_dict(Q[s])

      policy[s]= a

 plt.plot(deltas)

  plt.show()

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

  # findthe optimal state-value function

  # V(s) =max[a]{ Q(s,a) }

  V = {}

  for s inpolicy.keys():

    V[s] =max_dict(Q[s])[1]

  print“final values:”

 print_values(V, grid)

  print“final policy:”

 print_policy(policy, grid)

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

Метод Монте-Карло. Итоги

В заключение, как обычно мы подведём итоги всему рассмотренному в этой части материалу.

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

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

Управление методом Монте-Карло без исследования начала в коде

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

Начинаеммы со всех прежних импортов библиотек и констант.

import numpy as np

import matplotlib.pyplot as plt

from grid_world import standard_grid, negative_grid

from iterative_policy_evaluation import print_values,print_policy

from monte_carlo_es import max_dict

GAMMA = 0.9

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

# NOTE: find optimal policy and value function

#       usingon-policy first-visit MC

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

def random_action(a,eps=0.1):

  # choose givena with probability 1 – eps + eps/4

  # choose someother a’ != a with probability eps/4

  p =np.random.random()

  # if p < (1– eps + eps/len(ALL_POSSIBLE_ACTIONS)):

  #   return a

  # else:

  #   tmp = list(ALL_POSSIBLE_ACTIONS)

  #   tmp.remove(a)

  #   return np.random.choice(tmp)

  #

  # this isequivalent to the above

  if p < (1 –eps):

    return a

  else:

    returnnp.random.choice(ALL_POSSIBLE_ACTIONS)

Далее у нас идёт функция play_game. Обратите внимание, на то, что мы убрали код исследования начала и теперь всегда начинаем с позиции (2, 0), а также на строку, где добавлена эпсилон-жадная стратегия, в которой используется описанная выше функция random_action.

def play_game(grid,policy):

  # returns alist of states and corresponding returns

  # in thisversion we will NOT use “exploring starts” method

  # instead wewill explore using an epsilon-soft policy

  s = (2, 0)

 grid.set_state(s)

  a =random_action(policy[s])

  # be aware ofthe timing

  # each tripleis s(t), a(t), r(t)

  # but r(t)results from taking action a(t-1) from s(t-1) and landing in s(t)

 states_actions_rewards = [(s, a, 0)]

  while True:

    r =grid.move(a)

    s =grid.current_state()

    ifgrid.game_over():

      states_actions_rewards.append((s, None, r))

      break

    else:

      a =random_action(policy[s]) # the next state is stochastic

     states_actions_rewards.append((s, a, r))

Отдачивычисляются точно так же, как и ранее.

  #calculate the returns by working backwards from the terminal state

  G = 0

 states_actions_returns = []

  first = True

  for s, a, r inreversed(states_actions_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_actions_returns.append((s, a, G))

    G = r +GAMMA*G

 states_actions_returns.reverse() # we want it to be in order of statevisited

  returnstates_actions_returns

Далее мы переходим к разделу main. Заметьте, тут всё в точности то же, что и прежде; единственное отличие этого алгоритма – в том, как выполняется итерация по стратегиям, а точнее, какая стратегия используется для игры. Мы запускаем negative_grid, выводим на экран вознаграждения, инициируем случайную стратегию и случайное Q. Обратите внимание, что нам необходимо инициировать Q, хоть это и не нужно для решения задачи оценки. Это связано с тем, что когда позже мы выполняем argmax, нам нужны значения ценностей, из которых будем выбирать.

if __name__ == ‘__main__’:

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

  # to iterativepolicy evaluation

  # grid =standard_grid()

  # try thenegative grid too, to see if agent will learn to go past the “badspot”

  # in order tominimize number of steps

  grid =negative_grid(step_cost=-0.1)

  # printrewards

  print“rewards:”

 print_values(grid.rewards, grid)

  # state ->action

  # initialize arandom policy

  policy = {}

  for s ingrid.actions.keys():

    policy[s] =np.random.choice(ALL_POSSIBLE_ACTIONS)

  # initializeQ(s,a) and returns

  Q = {}

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

  states =grid.all_states()

  for s instates:

    if s ingrid.actions: # not a terminal state

      Q[s] = {}

      for a inALL_POSSIBLE_ACTIONS:

        Q[s][a]= 0

        returns[(s,a)]= []

    else:

      # terminalstate or state we can’t otherwise get to

      pass

  # repeat untilconvergence

  deltas = []

  for t in xrange(5000):

    if t % 1000== 0:

      print t

    # generatean episode using pi

   biggest_change = 0

   states_actions_returns = play_game(grid, policy)

Восновном цикле мы вновь-таки отслеживаем максимальное Δ, чтобы потом можно было вывести изменения по мере продвижения.

    # calculateQ(s,a)

    seen_state_action_pairs= set()

    for s, a, Gin states_actions_returns:

      # check ifwe have already seen s

      # called“first-visit” MC policy evaluation

      sa = (s,a)

      if sa notin seen_state_action_pairs:

        old_q =Q[s][a]

       returns[sa].append(G)

        Q[s][a] = np.mean(returns[sa])

       biggest_change = max(biggest_change, np.abs(old_q – Q[s][a]))

       seen_state_action_pairs.add(sa)

   deltas.append(biggest_change)

    # calculatenew policy pi(s) = argmax[a]{ Q(s,a) }

    for s inpolicy.keys():

      a, _ =max_dict(Q[s])

      policy[s]= a

 plt.plot(deltas)

  plt.show()

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

  # findthe optimal state-value function

  # V(s) =max[a]{ Q(s,a) }

  V = {}

  for s inpolicy.keys():

    V[s] =max_dict(Q[s])[1]

  print“final values:”

 print_values(V, grid)

  print“final policy:”

 print_policy(policy, grid)

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

Метод Монте-Карло. Итоги

В заключение, как обычно мы подведём итоги всему рассмотренному в этой части материалу.

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

Изтеории вероятностей мы знаем, что ожидаемое значение чего-либо можноприближённо выразить через среднее значение выборки:

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

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

Затеммы рассмотрели проблему управления. Отличие метода Монте-Карло в том, чтотеперь мы используем Q, а не V, чтобы взять argmaxпо всем действиям. Это необходимо оттого, что в методе Монте-Карло, в отличиеот динамического программирования, мы не можем выполнить упреждающий поиск.Однако, как мы видели, можно продолжать использовать идею итерации постратегиям из части, посвящённой динамическому программированию. Напомню, чтоэто когда мы чередуем оценку стратегии и её совершенствование. Мы озвучили тотфакт, что при этом метод Монте-Карло имеет один существенный недостаток: ему нужномного примеров для точности, причём внутри цикла, что делает его оченьнеэффективным. Мы использовали тот же подход, что и в случае итерации поценности, выполняя только одно обновление для оценки на итерацию. Удивительно,но отдачи выборки тут из разных стратегий, поскольку стратегия меняется по меревыполнения итераций. Удивительно и то, что формально никто не доказал ихсходимость.

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

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

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

Затеммы рассмотрели проблему управления. Отличие метода Монте-Карло в том, чтотеперь мы используем Q, а не V, чтобы взять argmaxпо всем действиям. Это необходимо оттого, что в методе Монте-Карло, в отличиеот динамического программирования, мы не можем выполнить упреждающий поиск.Однако, как мы видели, можно продолжать использовать идею итерации постратегиям из части, посвящённой динамическому программированию. Напомню, чтоэто когда мы чередуем оценку стратегии и её совершенствование. Мы озвучили тотфакт, что при этом метод Монте-Карло имеет один существенный недостаток: ему нужномного примеров для точности, причём внутри цикла, что делает его оченьнеэффективным. Мы использовали тот же подход, что и в случае итерации поценности, выполняя только одно обновление для оценки на итерацию. Удивительно,но отдачи выборки тут из разных стратегий, поскольку стратегия меняется по меревыполнения итераций. Удивительно и то, что формально никто не доказал ихсходимость.

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

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

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