Полуградиентное предсказание. Завершение курса

Полуградиентное предсказание методом TD0

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

Раз уж мы смогли применить методы приближений к методу Монте-Карло, возникает закономерный вопрос: можно ли применить их и к TD-обучению? Ответ: да, можно, но и одной оговоркой.

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

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

Тутвозникает одна маленькая проблема: используемые нами целевые переменные неявляются действительными целевыми переменными, поскольку зависят отпредсказания модели, в частности, V(s’). То есть в некотором смысле мыиспользуем результат работы модели как целевую переменную для уточненияпараметров модели, что выглядит довольно странно. В то же время это работает,поэтому всё равно продолжим. Это называется полуградиентным методом, посколькуиспользуемые целевые переменные не являются истинными целевыми переменными, аградиент не является истинным градиентом.

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

Вначалеу нас идут все обычные импорты вместе с некоторыми полезными функциями изнашего предыдущего скрипта по TD-обучению,такими как play_game.

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 td0_prediction import play_game, SMALL_ENOUGH,GAMMA, ALPHA, ALL_POSSIBLE_ACTIONS

# NOTE: this is only policy evaluation, notoptimization

Вэтой программе мы определим модель в виде класса с API,схожим на используемый в SciKit Learn. У нас есть функция init,используемая для инициации данных; функция s2x, преобразующая состояние в вектор признаков (обратитевнимание, что используется то же самое преобразование признаков, что и в случаеметода Монте-Карло, и что эти признаки могут оказаться неудачными); функция predict, принимающая в качестве аргументасостояние s,преобразующее его в x и возвращающая скалярное произведение θ и x; и, наконец, функция grad,просто возвращающая s.

class Model:

  def __init__(self):

    self.theta =np.random.randn(4) / 2

  def s2x(self, s):

    returnnp.array([s[0] – 1, s[1] – 1.5, s[0]*s[1] – 3, 1])

  def predict(self, s):

    x =self.s2x(s)

    returnself.theta.dot(x)

  def grad(self, s):

    returnself.s2x(s)

Затемидёт раздел 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()

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

  }

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

  model = Model()

  deltas = []

  # repeatuntil convergence

  k = 1.0

  for it in xrange(20000):

    if it % 10== 0:

      k += 0.01

    alpha =ALPHA/k

   biggest_change = 0

    # 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

      old_theta= model.theta.copy()

      ifgrid.is_terminal(s2):

        target =r

      else:

        target =r + GAMMA*model.predict(s2)

     model.theta += alpha*(target – model.predict(s))*model.grad(s)

     biggest_change = max(biggest_change, np.abs(old_theta –model.theta).sum())

   deltas.append(biggest_change)

 plt.plot(deltas)

  plt.show()

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

  # obtain predicted values

  V = {}

  states =grid.all_states()

  for s instates:

    if s ingrid.actions:

      V[s] =model.predict(s)

    else:

      # terminalstate or state we can’t otherwise get to

      V[s] = 0

  print“values:”

 print_values(V, grid)

  print“policy:”

 print_policy(policy, grid)

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

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

Полуградиентное SARSA

Перейдём к проблеме управления, в частности, реализуем алгоритм SARSA, однако вместо того, чтобы использовать Q, мы создадим параметризованную модель приближённого Q. Обратите внимание, что это будет сложнее, чем с приближённым V, поскольку вместо приближённого представления |S| значений теперь придётся приближённо представлять |S|x|A| значений.

В то же время основная идея остаётся прежней. Напомню, что нашей целевой переменной является r + γQ(s’,a’), а предсказанием – Q(s,a):

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

Таккак Qиндексируется и через s, и через a, нам нужно найти способ объединить их в векторпризнаков. Простейшим способом тут может быть то, что мы использовали преждедля V,применив прямое кодирование по отношению к действиям. В результате у насполучится строка, столбец, произведение строки и столбца, вверх, вниз, влево,вправо и ещё одно место для свободного члена:

Однакоесли вы так и сделаете – что я рекомендую, чтобы вы прошли через те жерассуждения, что и я, – то обнаружите, что такой модели недостаёт гибкости.Другими словами, линейная модель с такими заданными признаками не может даватьприближённое Qс достаточной точностью.

Вконце концов я решил добавить квадратные члены и иметь отдельные наборыпризнаков для каждого из действий. Таким образом, теперь для каждого действия унас есть строка, столбец, квадрат строки, квадрат столбца, произведение строкии столбца и единицу, которая представляет не совсем свободный член, а действие,закодированное прямым кодированием. Впрочем, свободный член тоже присутствует.Возникает вопрос: сжимается ли до сих пор Q с таким-то количеством признаков? Давайтепосчитаем. Для каждого из четырёх направлений у нас есть 6 разных признаков, включающихразные комбинации строки и столбца. Это 4*6 = 24 плюс единица для свободногочлена – всего 25. Если бы мы хранили Q в виде таблицы, то у нас было бы 9 состояний и 4действия для каждого состояния – всего 36. Следовательно, некоторая экономияприсутствует.

В коде я также оставлю возможность прямого кодирования всех пар состояние-действие, что эквивалентно выполнению обычного алгоритма SARSA без каких-либо приближений – можете попробовать, чтобы убедиться, что всё работает. В связи с этим нам понадобится словарь SA2IDX, отображающий пары состояние-действие с уникальным индексом x. Это похоже на то, что вы могли видеть в моих курсах по обработке естественных языков, где у нас был словарь word2index, отображавший каждое слово словаря с уникальным индексом x.

Полуградиентное 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 sarsa import random_action, GAMMA, ALPHA,ALL_POSSIBLE_ACTIONS

SA2IDX = {}

IDX = 0

Затем мы создаём класс Model. Функция init прежняя и просто инициирует данные. Обратите внимание, что размерность теперь равна 25.

class Model:

  def __init__(self):

    self.theta= np.random.randn(25) / np.sqrt(25)

    # if we useSA2IDX, a one-hot encoding for every (s,a) pair

    # in realitywe wouldn’t want to do this b/c we have just

    # as manyparams as before

    # print“D:”, IDX

    # self.theta= np.random.randn(IDX) / np.sqrt(IDX)

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

  def sa2x(self, s, a):

    # NOTE:using just (r, c, r*c, u, d, l, r, 1) is not expressive enough

    returnnp.array([

      s[0] –1                   if a == ‘U’ else 0,

      s[1] –1.5                 if a == ‘U’ else 0,

      (s[0]*s[1]– 3)/3      if a == ‘U’ else 0,

      (s[0]*s[0]– 2)/2      if a == ‘U’ else 0,

      (s[1]*s[1]– 4.5)/4.5 if a == ‘U’ else 0,

      1                             if a == ‘U’ else0,

      s[0] –1                    if a == ‘D’ else 0,

      s[1] –1.5                  if a == ‘D’ else 0,

      (s[0]*s[1]– 3)/3       if a == ‘D’ else 0,

      (s[0]*s[0]– 2)/2      if a == ‘D’ else 0,

      (s[1]*s[1]– 4.5)/4.5 if a == ‘D’ else 0,

      1                             if a == ‘D’ else0,

      s[0] –1                    if a == ‘L’ else 0,

      s[1] –1.5                  if a == ‘L’ else 0,

      (s[0]*s[1]– 3)/3       if a == ‘L’ else 0,

      (s[0]*s[0]– 2)/2      if a == ‘L’ else 0,

      (s[1]*s[1]– 4.5)/4.5 if a == ‘L’ else 0,

      1                             if a == ‘L’ else0,

      s[0] –1                    if a == ‘R’ else 0,

      s[1] –1.5                 if a == ‘R’ else 0,

      (s[0]*s[1]– 3)/3      if a == ‘R’ else 0,

      (s[0]*s[0]– 2)/2      if a == ‘R’ else 0,

      (s[1]*s[1]– 4.5)/4.5 if a == ‘R’ else 0,

      1                             if a == ‘R’ else0,

      1

    ])

    # if we useSA2IDX, a one-hot encoding for every (s,a) pair

    # in realitywe wouldn’t want to do this b/c we have just

    # as manyparams as before

    # x =np.zeros(len(self.theta))

    # idx =SA2IDX[s][a]

    # x[idx] = 1

    # return x

Далее у нас идут функции predict и grad, такие же, как и ранее.

  def predict(self, s, a):

    x =self.sa2x(s, a)

    returnself.theta.dot(x)

  def grad(self, s, a):

    returnself.sa2x(s, a)

Затем у нас идёт функция getQs. Причина, по которой она нам нужна, заключается в том, что в определённый момент выполнения алгоритма SARSA нам нужно взять argmax по Q, но мы не можем этого сделать, если Q не представлено в виде словаря. Поэтому цель данной функции – превратить прогноз Q в словарь с некоторым заданным состоянием s:

def getQs(model, s):

  # we needQ(s,a) to choose an action

  # i.e. a =argmax[a]{ Q(s,a) }

  Qs = {}

  for a inALL_POSSIBLE_ACTIONS:

    q_sa =model.predict(s, a)

    Qs[a] = q_sa

  return Qs

После этого идёт раздел main. Здесь используется negative_grid, однако вы вольны попробовать и standard_grid. Мы выводим вознаграждения и заполняем словарь SA2IDX.

if __name__ == ‘__main__’:

  # NOTE:if we use 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

  # enumerateall (s,a) pairs, each will have its own weight in our “dumb” model

  # essentiallyeach weight will be a measure of Q(s,a) itself

  states =grid.all_states()

  for s instates:

    SA2IDX[s] ={}

    for a inALL_POSSIBLE_ACTIONS:

     SA2IDX[s][a] = IDX

      IDX += 1

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

  #initialize model

  model =Model()

  # repeat untilconvergence

  t = 1.0

  t2 = 1.0

  deltas = []

  for it in xrange(20000):

    if it % 100== 0:

      t += 10e-3

      t2 += 0.01

    if it % 1000== 0:

      print“it:”, it

    alpha =ALPHA / t2

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

    # an episodewithin this loop

    s = (2, 0) #start state

   grid.set_state(s)

    # get Q(s)so we can choose the first action

    Qs = getQs(model, s)

Далее мы переходим к основному игровому циклу. Обратите внимание, что здесь мы должны использовать getQs, прежде чем использовать max_dict.

    # 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(Qs)[0]

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

   biggest_change = 0

    while notgrid.game_over():

      r =grid.move(a)

      s2 =grid.current_state()

Каки в TD0-предсказании, у нас разные целевые переменные,зависящие от того, находимся ли мы в конечном состоянии. Если мы в конечномсостоянии, то знаем, что Q(s’,a’) равно нулю, иможем более точно указать целевую переменную, просто равную r.

Всёостальное здесь вам уже знакомо.

      # 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

      old_theta= model.theta.copy()

      ifgrid.is_terminal(s2):

       model.theta += alpha*(r – model.predict(s, a))*model.grad(s, a)

      else:

        # notterminal

        Qs2 =getQs(model, s2)

        a2 =max_dict(Qs2)[0]

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

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

       model.theta += alpha*(r + GAMMA*model.predict(s2, a2) – model.predict(s,a))*model.grad(s, a)

        # nextstate becomes current state

        s = s2

        a = a2

      biggest_change= max(biggest_change, np.abs(model.theta – old_theta).sum())

   deltas.append(biggest_change)

 plt.plot(deltas)

  plt.show()

  # determinethe policy from Q*

  # find V* fromQ*

  policy = {}

  V = {}

  Q = {}

  for s ingrid.actions.keys():

    Qs =getQs(model, s)

    Q[s] = Qs

    a, max_q =max_dict(Qs)

    policy[s] =a

    V[s] = max_q

  print“values:”

 print_values(V, grid)

  print“policy:”

 print_policy(policy, grid)

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

Вначале видим Δ. Окончательная стратегия также кажется разумной.

Итоги курса и следующие действия

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

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

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

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

Чтобырассмотреть это всё в контексте, сделаем обзор всему, что мы сделали в этомкурсе. Мы начали курс с рассмотрения задачи о многоруком бандите, которую вывпервые увидали в моём курсе «Байесовское машинное обучение: A/B-тестирование».Мы узнали о дилемме исследования и использования, являющейся ключевой дляобучения с подкреплением, и рассмотрели четыре разных способа решения задачи омногоруком бандите, включая эпсилон-жадный алгоритм, метод оптимистическихначальных значений, UCB1 исэмплирование по Томпсону. Далее мы узнали о некоторых других основныхопределениях обучения с подкреплением и применили их для создания агента игры вкрестики-нолики. Написав код для агента игры в крестики-нолики, мы смоглипонять, как работает обучение с подкреплением и типы алгоритмов, которые мыиспользовали для обучения.

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

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

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

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

Ещёодин момент, который следует учитывать, – что мы пока что параметризовалитолько функцию ценности. В следующем курсе мы также рассмотрим, как можнопараметризовать стратегию π(a|s). Это называетсяметодом градиента стратегии.

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

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

Спасибо за прохождение этого курса и увидимся на следующих занятиях!

Однакоесли вы так и сделаете – что я рекомендую, чтобы вы прошли через те жерассуждения, что и я, – то обнаружите, что такой модели недостаёт гибкости.Другими словами, линейная модель с такими заданными признаками не может даватьприближённое Qс достаточной точностью.

Вконце концов я решил добавить квадратные члены и иметь отдельные наборыпризнаков для каждого из действий. Таким образом, теперь для каждого действия унас есть строка, столбец, квадрат строки, квадрат столбца, произведение строкии столбца и единицу, которая представляет не совсем свободный член, а действие,закодированное прямым кодированием. Впрочем, свободный член тоже присутствует.Возникает вопрос: сжимается ли до сих пор Q с таким-то количеством признаков? Давайтепосчитаем. Для каждого из четырёх направлений у нас есть 6 разных признаков, включающихразные комбинации строки и столбца. Это 4*6 = 24 плюс единица для свободногочлена – всего 25. Если бы мы хранили Q в виде таблицы, то у нас было бы 9 состояний и 4действия для каждого состояния – всего 36. Следовательно, некоторая экономияприсутствует.

В коде я также оставлю возможность прямого кодирования всех пар состояние-действие, что эквивалентно выполнению обычного алгоритма SARSA без каких-либо приближений – можете попробовать, чтобы убедиться, что всё работает. В связи с этим нам понадобится словарь SA2IDX, отображающий пары состояние-действие с уникальным индексом x. Это похоже на то, что вы могли видеть в моих курсах по обработке естественных языков, где у нас был словарь word2index, отображавший каждое слово словаря с уникальным индексом x.

Полуградиентное 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 sarsa import random_action, GAMMA, ALPHA,ALL_POSSIBLE_ACTIONS

SA2IDX = {}

IDX = 0

Затем мы создаём класс Model. Функция init прежняя и просто инициирует данные. Обратите внимание, что размерность теперь равна 25.

class Model:

  def __init__(self):

    self.theta= np.random.randn(25) / np.sqrt(25)

    # if we useSA2IDX, a one-hot encoding for every (s,a) pair

    # in realitywe wouldn’t want to do this b/c we have just

    # as manyparams as before

    # print“D:”, IDX

    # self.theta= np.random.randn(IDX) / np.sqrt(IDX)

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

  def sa2x(self, s, a):

    # NOTE:using just (r, c, r*c, u, d, l, r, 1) is not expressive enough

    returnnp.array([

      s[0] –1                   if a == ‘U’ else 0,

      s[1] –1.5                 if a == ‘U’ else 0,

      (s[0]*s[1]– 3)/3      if a == ‘U’ else 0,

      (s[0]*s[0]– 2)/2      if a == ‘U’ else 0,

      (s[1]*s[1]– 4.5)/4.5 if a == ‘U’ else 0,

      1                             if a == ‘U’ else0,

      s[0] –1                    if a == ‘D’ else 0,

      s[1] –1.5                  if a == ‘D’ else 0,

      (s[0]*s[1]– 3)/3       if a == ‘D’ else 0,

      (s[0]*s[0]– 2)/2      if a == ‘D’ else 0,

      (s[1]*s[1]– 4.5)/4.5 if a == ‘D’ else 0,

      1                             if a == ‘D’ else0,

      s[0] –1                    if a == ‘L’ else 0,

      s[1] –1.5                  if a == ‘L’ else 0,

      (s[0]*s[1]– 3)/3       if a == ‘L’ else 0,

      (s[0]*s[0]– 2)/2      if a == ‘L’ else 0,

      (s[1]*s[1]– 4.5)/4.5 if a == ‘L’ else 0,

      1                             if a == ‘L’ else0,

      s[0] –1                    if a == ‘R’ else 0,

      s[1] –1.5                 if a == ‘R’ else 0,

      (s[0]*s[1]– 3)/3      if a == ‘R’ else 0,

      (s[0]*s[0]– 2)/2      if a == ‘R’ else 0,

      (s[1]*s[1]– 4.5)/4.5 if a == ‘R’ else 0,

      1                             if a == ‘R’ else0,

      1

    ])

    # if we useSA2IDX, a one-hot encoding for every (s,a) pair

    # in realitywe wouldn’t want to do this b/c we have just

    # as manyparams as before

    # x =np.zeros(len(self.theta))

    # idx =SA2IDX[s][a]

    # x[idx] = 1

    # return x

Далее у нас идут функции predict и grad, такие же, как и ранее.

  def predict(self, s, a):

    x =self.sa2x(s, a)

    returnself.theta.dot(x)

  def grad(self, s, a):

    returnself.sa2x(s, a)

Затем у нас идёт функция getQs. Причина, по которой она нам нужна, заключается в том, что в определённый момент выполнения алгоритма SARSA нам нужно взять argmax по Q, но мы не можем этого сделать, если Q не представлено в виде словаря. Поэтому цель данной функции – превратить прогноз Q в словарь с некоторым заданным состоянием s:

def getQs(model, s):

  # we needQ(s,a) to choose an action

  # i.e. a =argmax[a]{ Q(s,a) }

  Qs = {}

  for a inALL_POSSIBLE_ACTIONS:

    q_sa =model.predict(s, a)

    Qs[a] = q_sa

  return Qs

После этого идёт раздел main. Здесь используется negative_grid, однако вы вольны попробовать и standard_grid. Мы выводим вознаграждения и заполняем словарь SA2IDX.

if __name__ == ‘__main__’:

  # NOTE:if we use 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

  # enumerateall (s,a) pairs, each will have its own weight in our “dumb” model

  # essentiallyeach weight will be a measure of Q(s,a) itself

  states =grid.all_states()

  for s instates:

    SA2IDX[s] ={}

    for a inALL_POSSIBLE_ACTIONS:

     SA2IDX[s][a] = IDX

      IDX += 1

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

  #initialize model

  model =Model()

  # repeat untilconvergence

  t = 1.0

  t2 = 1.0

  deltas = []

  for it in xrange(20000):

    if it % 100== 0:

      t += 10e-3

      t2 += 0.01

    if it % 1000== 0:

      print“it:”, it

    alpha =ALPHA / t2

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

    # an episodewithin this loop

    s = (2, 0) #start state

   grid.set_state(s)

    # get Q(s)so we can choose the first action

    Qs = getQs(model, s)

Далее мы переходим к основному игровому циклу. Обратите внимание, что здесь мы должны использовать getQs, прежде чем использовать max_dict.

    # 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(Qs)[0]

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

   biggest_change = 0

    while notgrid.game_over():

      r =grid.move(a)

      s2 =grid.current_state()

Каки в TD0-предсказании, у нас разные целевые переменные,зависящие от того, находимся ли мы в конечном состоянии. Если мы в конечномсостоянии, то знаем, что Q(s’,a’) равно нулю, иможем более точно указать целевую переменную, просто равную r.

Всёостальное здесь вам уже знакомо.

      # 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

      old_theta= model.theta.copy()

      ifgrid.is_terminal(s2):

       model.theta += alpha*(r – model.predict(s, a))*model.grad(s, a)

      else:

        # notterminal

        Qs2 =getQs(model, s2)

        a2 =max_dict(Qs2)[0]

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

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

       model.theta += alpha*(r + GAMMA*model.predict(s2, a2) – model.predict(s,a))*model.grad(s, a)

        # nextstate becomes current state

        s = s2

        a = a2

      biggest_change= max(biggest_change, np.abs(model.theta – old_theta).sum())

   deltas.append(biggest_change)

 plt.plot(deltas)

  plt.show()

  # determinethe policy from Q*

  # find V* fromQ*

  policy = {}

  V = {}

  Q = {}

  for s ingrid.actions.keys():

    Qs =getQs(model, s)

    Q[s] = Qs

    a, max_q =max_dict(Qs)

    policy[s] =a

    V[s] = max_q

  print“values:”

 print_values(V, grid)

  print“policy:”

 print_policy(policy, grid)

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

Вначале видим Δ. Окончательная стратегия также кажется разумной.

Итоги курса и следующие действия

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

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

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

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

Чтобырассмотреть это всё в контексте, сделаем обзор всему, что мы сделали в этомкурсе. Мы начали курс с рассмотрения задачи о многоруком бандите, которую вывпервые увидали в моём курсе «Байесовское машинное обучение: A/B-тестирование».Мы узнали о дилемме исследования и использования, являющейся ключевой дляобучения с подкреплением, и рассмотрели четыре разных способа решения задачи омногоруком бандите, включая эпсилон-жадный алгоритм, метод оптимистическихначальных значений, UCB1 исэмплирование по Томпсону. Далее мы узнали о некоторых других основныхопределениях обучения с подкреплением и применили их для создания агента игры вкрестики-нолики. Написав код для агента игры в крестики-нолики, мы смоглипонять, как работает обучение с подкреплением и типы алгоритмов, которые мыиспользовали для обучения.

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

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

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

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

Ещёодин момент, который следует учитывать, – что мы пока что параметризовалитолько функцию ценности. В следующем курсе мы также рассмотрим, как можнопараметризовать стратегию π(a|s). Это называетсяметодом градиента стратегии.

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

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

Спасибо за прохождение этого курса и увидимся на следующих занятиях!

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

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