Обучение методом временных разниц

Введение в метод временных разниц

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

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

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

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

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

TD0-предсказание

Давайте рассмотрим, как использовать TD-обучение для решения проблемы предсказания или, другими словами, нахождения функции ценности. Вначале может показаться странным само название – почему в нём нуль, а не какое-то другое число? Дело в том, что есть и другие методы TD-обучения, такие как TD(1) или, в общем случае, TD(λ), но их описание выходит за рамки данного курса. Они схожи, но не обязательны для понимания Q-обучения и методов приближений, к которым мы в конечном итоге стремимся.

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

Вчастности, рассмотрим метод, который на самом деле не требует от нас хранениявсех отдач:

Незабывайте, что α может бытьконстантой или затухать со временем. Поэтому если мы используем данную формулу,она может быть альтернативным способом нахождения средней отдачи от состояния.

Теперьвспомним определение V. Напомню, что это ожидаемое значение отдачи взаданном состоянии. Вспомним также, что мы можем определить V рекурсивно:

Резонноспросить, нельзя ли подставить отдачу в уравнение обновления с помощью этогорекурсивного определения V? Так и сделав, получим метод TD0:

Есливнимательно присмотреться, можно понять, что это целиком оперативныйбутстреп-метод. Действительно, теперь мы не вычисляем G – полнуюотдачу, – вместо этого мы используем другую оценку V, в частности, V для следующего состояния. Кроме того, мы можемобновить V(s), как только узнаем s. Таким образом, вместо того, чтобыждать окончания всего эпизода, нам достаточно дождаться перехода в следующеесостояние, чтобы обновить ценность для состояния текущего.

Полезноизучить, как работают эти оценки и каковы источники неопределённости. В методеМонте-Карло случайность проистекала из того факта, что каждый эпизод мог бытьсыгран по-разному. То есть отдача от состояния является разной, если впоследующих переходах состояний имеется фактор случайности. В случае с TD0 у нас появляется ещё один источник случайности. Вчастности, мы даже не знаем отдачу, а вместо неё используем r + γV(s’) для того, чтобы оценить отдачу G.

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

TD0-предсказание в коде

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

Вначале у нас идут все обычные импорты библиотек и константы с тем лишь исключением, что теперь нам также понадобится коэффициент обучения alpha:

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

SMALL_ENOUGH = 10e-4

GAMMA = 0.9

ALPHA = 0.1

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

# NOTE: this is only policy evaluation, notoptimization

Далее идёт функция random_action. Я не импортировал её из других файлов, поскольку хотел поместить в неё следующий комментарий. С TD0 у нас тут та же проблема, что и в методе Монте-Карло, а именно: если мы никогда не посещаем некоторое состояние, то никогда не обновим и его ценность, так что если у нас будет заданная (детерминированная) стратегия без какого-либо исследования, некоторые состояния не будут иметь ценность. Ничего страшного, если нам не нужны эти ценности, однако мы добавим процесс исследования, чтобы было интереснее.

def random_action(a,eps=0.1):

  # we’ll useepsilon-soft to ensure all states are visited

  # what happensif you don’t do this? i.e. eps=0

  p =np.random.random()

  if p < (1 –eps):

    return a

  else:

    returnnp.random.choice(ALL_POSSIBLE_ACTIONS)

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

def play_game(grid,policy):

  # returns alist of states and corresponding rewards (not returns as in MC)

  # start at thedesignated start state

  s = (2, 0)

 grid.set_state(s)

 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))

  return states_and_rewards

Затем мы переходим к разделу main. Тут используется standard_grid, можете сравнить это с нашими предыдущими скриптами. Стратегия остаётся идентичной первой использованной стратегии. Однако обратите внимание, что прежний ответ не получится, поскольку до этого мы не использовали эпсилон-жадный алгоритм.

if __name__ == ‘__main__’:

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

  # to iterativepolicy 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’,

  }

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

  #initialize V(s) and returns

  V = {}

  states =grid.all_states()

  for s instates:

    V[s] = 0

  # repeat untilconvergence

  for it in xrange(1000):

    # generatean episode using pi

   states_and_rewards = play_game(grid, policy)

    # the first(s, r) tuple is the state we start in and 0

    # (since wedon’t get a reward) for simply starting the game

    # the last(s, r) tuple is the terminal state and the final reward

    # the valuefor the terminal state is by definition 0, so we don’t

    # care aboutupdating it.

    for t in xrange(len(states_and_rewards) – 1):

      s, _ =states_and_rewards[t]

      s2, r =states_and_rewards[t+1]

      # we willupdate V(s) AS we experience the episode

      V[s] =V[s] + ALPHA*(r + GAMMA*V[s2] – V[s])

Вконце мы выводим найденные значения ценностей и стратегию.

  print“values:”

  print_values(V,grid)

  print“policy:”

 print_policy(policy, grid)

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

Всё как ожидалось.

SARSA

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

Напомним,что в части, посвящённой методу Монте-Карло, объясняется причина, по которойиспользуется Q:потому что оно позволяет выбрать действие, основываясь на аргументемаксимизации (argmax) по Q; сделать то же с V мы не можем, поскольку оно индексируется только посостояниям. Поскольку Q имеет ту же рекурсивную форму, мы можем применитьпрежнее уравнение обновления:

Обратитевнимание, что тут имеется то же ограничение, что и в методе Монте-Карло:поскольку Qиндексируется и по состоянию, и по действию, нам необходимо намного большеитераций, чтобы получить достаточное количество данных для схождения. Посколькуобновление зависит от наличия 5-кортежа (s, a, r, s’, a’), этот метод называется SARSA.

Таккак SARSA требует знания Q(s, a) для всехвозможных действий a в состоянии s, чтобы можно было точно выбрать аргументмаксимизации, то у нас опять возникает та же проблема, что и в методеМонте-Карло. Напомню, она заключалась в том, что если мы следуемдетерминированной стратегии, то будем выполнять лишь 1/|A| возможныхдействий, что оставит большинство значений Q не определёнными. Для решения этой проблемынеобходимо либо использовать метод исследование начала, либо стратегию,позволяющую исследование наподобие эпсилон-жадной. И поскольку мы знаем, чтоисследование начала нереалистично, то используем эпсилон-жадный алгоритм.

Рассмотримпсевдокод, чтобы закрепить эту идею:

Q(s,a) = произвольное, Q(конечное, a) = 0

for t=1..N

    s =начальное_состояние, a =эпсилон_жадное_с(Q(s))

    while not конец игры:

        s’,r = выполнить_действие(a)

        a’= эпсилон_жадное_с(Q(s’))

        Q(s,a) = Q(s,a) + alpha*[r + gamma*Q(s’, a’) – Q(s,a)]

        s = s’, a = a’

Вначалемы инициируем Qслучайным образом с 0 для любого конечного состояния, затем начинаетсябесконечный цикл. Внутри цикла мы начинаем игру, получаем первое состояние ивыбираем первое действие, основываясь на эпсилон-жадном алгоритме и текущем Q, – назовём этокортежем (s, a). Внутри этого цикла запускается ещёодин, который заканчивается при окончании эпизода. Мы выполняем действие a, приводящее всостояние s и дающеевознаграждение r.Затем выбирается следующее действие на основе эпсилон-жадного алгоритма итекущего Q– назовём это a. Далее выполняетсяобновление Q(s), зависящее от самого Q(s), r и Q(s’, a’). После этого s обновляется до s, a – до a.

Любопытный факт о SARSA: доказательство о его сходимости никогда не было опубликовано, однако неофициально было объявлено, что SARSA сойдётся, если стратегия сходится с жадной стратегией. Один из способов этого добиться – установить ε = 1/t, где t – время. Мы это используем в коде. Обратите внимание, что числитель вовсе не обязательно должен быть равен единице – можно поставить 0,5/t или 0,8/t, или сколько-нибудь ещё на ваше усмотрение. Кроме того, затухание не обязательно должно быть кратным t – можно выбрать 1/(t2/3) или любой другой показатель степени – это можно считать очередным гиперпараметром.

Напомню,что и коэффициент обучения также может быть затухающим, однако с затуханием,равным 1/t,возникает проблема. Не забывайте, что каждый раз только одна парасостояние-действие будет обновляться в Q. Следовательно, коэффициент обучения будет затухатьдля значений Q,которые ранее ещё никогда не обновлялись. Можно попробовать это исправить,уменьшая коэффициент обучения лишь раз за эпизод, однако проблема остаётся: втечение эпизода может быть посещено лишь подмножество полного множествасостояний, а для каждого состояния может быть выполнено лишь одно из возможныхдействий. Таким образом, даже если мы уменьшаем коэффициент обучения лишь разза эпизод, мы всё равно уменьшаем коэффициент обучения для части Q, которые ранееникогда не обновлялись.

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

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

SARSA в коде

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

Вначале у нас идут все обычные импорты. Заметьте, что сейчас нам требуется функция max_dict из файла 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

from monte_carlo_es import max_dict

from td0_prediction import random_action

Константытоже все прежние, однако обратите внимание, что ALPHA– это не то эффективное α, котороеиспользуется для Q;то эффективное α будет вычислено изэтого исходного α.

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

GAMMA = 0.9

ALPHA = 0.1

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

Далее мы переходим к разделу main. Обратите внимание, что мы используем negative_grid, однако вы можете попробовать и standard_grid, чтобы понаблюдать за эффектом.

if __name__ == ‘__main__’:

  # NOTE: if weuse the standard grid, there’s a good chance we will end up with

  # suboptimalpolicies

  # e.g.

  #—————————

  #   R |   R  |   R  |     |

  #—————————

  #   R* |     |   U  |     |

  #—————————

  #   U |   R  |   U  |  L  |

  # since goingR at (1,0) (shown with a *) incurs no cost, it’s OK to keep doing that.

  # we’ll eitherend up staying in the same spot, or back to the start (2,0), at which

  # point wewhould then just go back up, or at (0,0), at which point we can continue

  # on right.

  # instead,let’s penalize each movement so the agent will find a shorter route.

  #

  # grid =standard_grid()

  grid =negative_grid(step_cost=-0.1)

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

  # printrewards

  print“rewards:”

 print_values(grid.rewards, grid)

  # no policyinitialization, we will derive our policy from most recent Q

  # initializeQ(s,a)

  Q = {}

  states =grid.all_states()

  for s instates:

    Q[s] = {}

    for a inALL_POSSIBLE_ACTIONS:

      Q[s][a] =0

  # let’s alsokeep track of how many times Q[s] has been updated

  update_counts= {}

 update_counts_sa = {}

  for s instates:

    update_counts_sa[s]= {}

    for a inALL_POSSIBLE_ACTIONS:

     update_counts_sa[s][a] = 1.0

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

  # repeatuntil convergence

  t = 1.0

  deltas = []

  for it in xrange(10000):

    if it % 100== 0:

      t += 10e-3

    if it % 2000== 0:

      print“it:”, it

    # instead of‘generating’ an epsiode, we will PLAY

    # an episodewithin this loop

    s = (2, 0) #start state

    grid.set_state(s)

Внутри цикла мы играем в игру. Мы указываем начальное состояние и находим начальное действие, основываясь на Q. Затем мы входим в игровой цикл. Мы выполняем действие, чтобы получить вознаграждение и найти следующее состояние. После этого мы находим следующее действие, основываясь на эпсилон-жадном алгоритме. Обратите внимание, что ε здесь не константа, оно меняется с течением времени. Далее вычисляется α, равное начальному значению α, делённому на величину, зафиксированную в словаре. Эта величина также обновляется, но не сильно. Обратите внимание, что мы здесь отслеживаем и Δ, поскольку хотим знать, насколько изменяется Q по мере обучения. Затем делается обновление Q и словаря update_counts_sa, после чего s и a присваиваются новые значения. После этого цикл заканчивается.

    # the first(s, r) tuple is the state we start in and 0

    # (since wedon’t get a reward) for simply starting the game

    # the last(s, r) tuple is the terminal state and the final reward

    # the valuefor the terminal state is by definition 0, so we don’t

    # care aboutupdating it.

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

    a =random_action(a, eps=0.5/t)

   biggest_change = 0

    while notgrid.game_over():

      r =grid.move(a)

      s2 =grid.current_state()

      # we needthe next action as well since Q(s,a) depends on Q(s’,a’)

      # if s2not in policy then it’s a terminal state, all Q are 0

      a2 =max_dict(Q[s2])[0]

      a2 =random_action(a2, eps=0.5/t) #epsilon-greedy

      # we willupdate Q(s,a) AS we experience the episode

      alpha =ALPHA / update_counts_sa[s][a]

     update_counts_sa[s][a] += 0.005

      old_qsa =Q[s][a]

      Q[s][a] =Q[s][a] + alpha*(r + GAMMA*Q[s2][a2] – Q[s][a])

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

      # we wouldlike to know how often Q(s) has been updated too

     update_counts[s] = update_counts.get(s,0) + 1

      # nextstate becomes current state

      s = s2

      a = a2

   deltas.append(biggest_change)

 plt.plot(deltas)

  plt.show()

Поскольку мы хотим вывести на экран стратегию, её надо найти, взяв argmax по Q. Кроме того, мы воспользуемся возможностью и заодно вычислим функцию ценности состояний. Также напомню, что мы хотим показать, какую долю времени мы проводим в каждом состоянии, поэтому собираем значения ценностей и с помощью функции print_values выводим на экран. В конце мы выводим ценности состояний и конечную стратегию.

  # determine the policyfrom Q*

  # find V*from Q*

  policy = {}

  V = {}

  for s ingrid.actions.keys():

    a, max_q =max_dict(Q[s])

    policy[s] =a

    V[s] = max_q

  # what’s theproportion of time we spend updating each part of Q?

  print“update counts:”

  total =np.sum(update_counts.values())

  for k, v inupdate_counts.iteritems():

   update_counts[k] = float(v) /total

 print_values(update_counts, grid)

  print“values:”

 print_values(V, grid)

  print“policy:”

 print_policy(policy, grid)

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

Стратегия у нас выглядит очень неплохо.

Q-обучение

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

Как же работает Q-обучение?

Оно очень схоже на SARSA. На самом деле на первых порах я сам даже не мог сказать, в чём отличие, поэтому не удивляйтесь, если вы посмотрите на уравнения и они покажутся вам теми же.

Идеяв том, что вместо того, чтобы выбирать a, основанное на argmax по Q, мы обновляем Q, основываясь на максимуме по всем действиям:

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

SARSA в коде

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

Вначале у нас идут все обычные импорты. Заметьте, что сейчас нам требуется функция max_dict из файла 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

from monte_carlo_es import max_dict

from td0_prediction import random_action

Константытоже все прежние, однако обратите внимание, что ALPHA– это не то эффективное α, котороеиспользуется для Q;то эффективное α будет вычислено изэтого исходного α.

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

GAMMA = 0.9

ALPHA = 0.1

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

Далее мы переходим к разделу main. Обратите внимание, что мы используем negative_grid, однако вы можете попробовать и standard_grid, чтобы понаблюдать за эффектом.

if __name__ == ‘__main__’:

  # NOTE: if weuse the standard grid, there’s a good chance we will end up with

  # suboptimalpolicies

  # e.g.

  #—————————

  #   R |   R  |   R  |     |

  #—————————

  #   R* |     |   U  |     |

  #—————————

  #   U |   R  |   U  |  L  |

  # since goingR at (1,0) (shown with a *) incurs no cost, it’s OK to keep doing that.

  # we’ll eitherend up staying in the same spot, or back to the start (2,0), at which

  # point wewhould then just go back up, or at (0,0), at which point we can continue

  # on right.

  # instead,let’s penalize each movement so the agent will find a shorter route.

  #

  # grid =standard_grid()

  grid =negative_grid(step_cost=-0.1)

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

  # printrewards

  print“rewards:”

 print_values(grid.rewards, grid)

  # no policyinitialization, we will derive our policy from most recent Q

  # initializeQ(s,a)

  Q = {}

  states =grid.all_states()

  for s instates:

    Q[s] = {}

    for a inALL_POSSIBLE_ACTIONS:

      Q[s][a] =0

  # let’s alsokeep track of how many times Q[s] has been updated

  update_counts= {}

 update_counts_sa = {}

  for s instates:

    update_counts_sa[s]= {}

    for a inALL_POSSIBLE_ACTIONS:

     update_counts_sa[s][a] = 1.0

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

  # repeatuntil convergence

  t = 1.0

  deltas = []

  for it in xrange(10000):

    if it % 100== 0:

      t += 10e-3

    if it % 2000== 0:

      print“it:”, it

    # instead of‘generating’ an epsiode, we will PLAY

    # an episodewithin this loop

    s = (2, 0) #start state

    grid.set_state(s)

Внутри цикла мы играем в игру. Мы указываем начальное состояние и находим начальное действие, основываясь на Q. Затем мы входим в игровой цикл. Мы выполняем действие, чтобы получить вознаграждение и найти следующее состояние. После этого мы находим следующее действие, основываясь на эпсилон-жадном алгоритме. Обратите внимание, что ε здесь не константа, оно меняется с течением времени. Далее вычисляется α, равное начальному значению α, делённому на величину, зафиксированную в словаре. Эта величина также обновляется, но не сильно. Обратите внимание, что мы здесь отслеживаем и Δ, поскольку хотим знать, насколько изменяется Q по мере обучения. Затем делается обновление Q и словаря update_counts_sa, после чего s и a присваиваются новые значения. После этого цикл заканчивается.

    # the first(s, r) tuple is the state we start in and 0

    # (since wedon’t get a reward) for simply starting the game

    # the last(s, r) tuple is the terminal state and the final reward

    # the valuefor the terminal state is by definition 0, so we don’t

    # care aboutupdating it.

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

    a =random_action(a, eps=0.5/t)

   biggest_change = 0

    while notgrid.game_over():

      r =grid.move(a)

      s2 =grid.current_state()

      # we needthe next action as well since Q(s,a) depends on Q(s’,a’)

      # if s2not in policy then it’s a terminal state, all Q are 0

      a2 =max_dict(Q[s2])[0]

      a2 =random_action(a2, eps=0.5/t) #epsilon-greedy

      # we willupdate Q(s,a) AS we experience the episode

      alpha =ALPHA / update_counts_sa[s][a]

     update_counts_sa[s][a] += 0.005

      old_qsa =Q[s][a]

      Q[s][a] =Q[s][a] + alpha*(r + GAMMA*Q[s2][a2] – Q[s][a])

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

      # we wouldlike to know how often Q(s) has been updated too

     update_counts[s] = update_counts.get(s,0) + 1

      # nextstate becomes current state

      s = s2

      a = a2

   deltas.append(biggest_change)

 plt.plot(deltas)

  plt.show()

Поскольку мы хотим вывести на экран стратегию, её надо найти, взяв argmax по Q. Кроме того, мы воспользуемся возможностью и заодно вычислим функцию ценности состояний. Также напомню, что мы хотим показать, какую долю времени мы проводим в каждом состоянии, поэтому собираем значения ценностей и с помощью функции print_values выводим на экран. В конце мы выводим ценности состояний и конечную стратегию.

  # determine the policyfrom Q*

  # find V*from Q*

  policy = {}

  V = {}

  for s ingrid.actions.keys():

    a, max_q =max_dict(Q[s])

    policy[s] =a

    V[s] = max_q

  # what’s theproportion of time we spend updating each part of Q?

  print“update counts:”

  total =np.sum(update_counts.values())

  for k, v inupdate_counts.iteritems():

   update_counts[k] = float(v) /total

 print_values(update_counts, grid)

  print“values:”

 print_values(V, grid)

  print“policy:”

 print_policy(policy, grid)

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

Стратегия у нас выглядит очень неплохо.

Q-обучение

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

Как же работает Q-обучение?

Оно очень схоже на SARSA. На самом деле на первых порах я сам даже не мог сказать, в чём отличие, поэтому не удивляйтесь, если вы посмотрите на уравнения и они покажутся вам теми же.

Идеяв том, что вместо того, чтобы выбирать a, основанное на argmax по Q, мы обновляем Q, основываясь на максимуме по всем действиям:

Вначалеможет показаться, что это то же самое: если мы выбираем a’ как argmax по Q, то,что возле γ, будет Q(s’,a’) с максимумом по a.

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

Таким образом, ключевым отличием Q-обучения является то, что не важно, какой стратегии мы придерживаемся в игре. При этом возникает резонный вопрос: при каких обстоятельствах Q-обучение эквивалентно SARSA? Если стратегия, используемая при Q-обучении, является жадной, то есть мы всегда выбираем argmax по Q, то наше Q(s’,a’) будет соответствовать следующему предпринимаемому действию. В этом случае выполнение SARSA означает и выполнение Q-обучения.

Q-обучение в коде

Если вы не хотите писать код самостоятельно, хотя я настоятельно рекомендую сделать именно так, соответствующий файл в репозитарии называется q_learning.py. Учтите, что во многом код тот же, что и в скрипте с SARSA.

Перейдёмсразу к основному циклу, поскольку именно там находятся все соответствующиеизменения.

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

from td0_prediction import random_action

GAMMA = 0.9

ALPHA = 0.1

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

if __name__ == ‘__main__’:

  # NOTE: if weuse the standard grid, there’s a good chance we will end up with

  # suboptimalpolicies

  # e.g.

  #—————————

  #   R |   R  |   R  |     |

  #—————————

  #   R* |     |   U  |     |

  #—————————

  #   U |   R  |   U  |  L  |

  # since goingR at (1,0) (shown with a *) incurs no cost, it’s OK to keep doing that.

  # we’ll eitherend up staying in the same spot, or back to the start (2,0), at which

  # point wewhould then just go back up, or at (0,0), at which point we can continue

  # on right.

  # instead,let’s penalize each movement so the agent will find a shorter route.

  #

  # grid =standard_grid()

  grid =negative_grid(step_cost=-0.1)

  # printrewards

  print“rewards:”

 print_values(grid.rewards, grid)

  # no policyinitialization, we will derive our policy from most recent Q

  # initializeQ(s,a)

  Q = {}

  states =grid.all_states()

  for s instates:

    Q[s] = {}

    for a inALL_POSSIBLE_ACTIONS:

      Q[s][a] =0

  # let’s alsokeep track of how many times Q[s] has been updated

  update_counts= {}

 update_counts_sa = {}

  for s instates:

   update_counts_sa[s] = {}

    for a inALL_POSSIBLE_ACTIONS:

     update_counts_sa[s][a] = 1.0

  # repeat untilconvergence

  t = 1.0

  deltas = []

  for it in xrange(10000):

    if it % 100== 0:

      t += 10e-3

    if it % 2000== 0:

      print“it:”, it

    # instead of‘generating’ an epsiode, we will PLAY

    # an episodewithin this loop

    s = (2, 0) #start state

    grid.set_state(s)

Преждевсего отметим, что место, где мы выбираем действительно предпринимаемоедействие, имеет другую позицию. В этом скрипте выполняется эпсилон-жадныйалгоритм, однако я оставляю вам и возможность выбора случайного равномернораспределённого действия. Вы увидите, что работают оба варианта, однакослучайное равномерное распределение занимает больше времени при том жеколичестве эпизодов, поскольку в этом случае нет попытки прямо добраться доцели. Обратите внимание, что мы используем адаптивный коэффициент обучения иадаптивный ε.Далее обратите внимание на место, где мы выбираем a2для следующего Q. Эта частьидентична коду для SARSA – мы такжеприсваиваем a значение a2 в конце цикла.Но если мы вернёмся назад, то a может измениться. Это и отличает Q-обучение отSARSA.

    # thefirst (s, r) tuple is the state we start in and 0

    # (since wedon’t get a reward) for simply starting the game

    # the last(s, r) tuple is the terminal state and the final reward

    # the valuefor the terminal state is by definition 0, so we don’t

    # care aboutupdating it.

    a, _ =max_dict(Q[s])

   biggest_change = 0

    while notgrid.game_over():

      a =random_action(a, eps=0.5/t) # epsilon-greedy

      # randomaction also works, but slower since you can bump into walls

      # a =np.random.choice(ALL_POSSIBLE_ACTIONS)

      r =grid.move(a)

      s2 =grid.current_state()

      # adaptivelearning rate

      alpha =ALPHA / update_counts_sa[s][a]

     update_counts_sa[s][a] += 0.005

      # we willupdate Q(s,a) AS we experience the episode

      old_qsa =Q[s][a]

      # thedifference between SARSA and Q-Learning is with Q-Learning

      # we willuse this max[a’]{ Q(s’,a’)} in our update

      # even ifwe do not end up taking this action in the next step

      a2,max_q_s2a2 = max_dict(Q[s2])

      Q[s][a] =Q[s][a] + alpha*(r + GAMMA*max_q_s2a2 – Q[s][a])

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

      # we wouldlike to know how often Q(s) has been updated too

     update_counts[s] = update_counts.get(s,0) + 1

      # nextstate becomes current state

      s = s2

   deltas.append(biggest_change)

  plt.plot(deltas)

  plt.show()

  # determinethe policy from Q*

  # find V* fromQ*

  policy = {}

  V = {}

  for s ingrid.actions.keys():

    a, max_q =max_dict(Q[s])

    policy[s] =a

    V[s] = max_q

  # what’s theproportion of time we spend updating each part of Q?

  print“update counts:”

  total =np.sum(update_counts.values())

  for k, v inupdate_counts.iteritems():

   update_counts[k] = float(v) / total

 print_values(update_counts, grid)

  print“values:”

 print_values(V, grid)

  print“policy:”

 print_policy(policy, grid)

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

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

Обучение методом временных разниц. Итоги

И наконец, мы подведём итог всему, что сделали в этой части.

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

Издинамического программирования мы взяли такие идеи, как бутстреппинг ииспользование рекурсивной формы функции ценности для оценки отдачи. Объединивих вместе, мы получили TD0, где вместотого, чтобы находить среднее значение отдач, мы находили среднее значениепредполагаемых отдач, основываясь на текущем вознаграждении и ценности следующегосостояния.

Чтокасается проблемы управления, то мы вновь должны были использовать функциюценности действий, а не функцию ценности состояний – по той же причине, что ипри оценке по методу Монте-Карло. Мы вывели алгоритм SARSA,объединяющий идеи итерации по ценности и TD0,а также изучили разницу между алгоритмами, ориентированными и неориентированными на стратегию, только позже выяснив, что все виденные нами ранеерешения проблемы управления были ориентированными на стратегию. Однако затем мыизучили не ориентированный на стратегию алгоритм, именуемый Q-обучением, который в последнее время набираетпопулярность, отчасти благодаря глубокому Q-обучению.

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

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

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