Динамическое программирование

Введение в динамическое программирование и итерационную оценку стратегии

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

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

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

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

def iterative_policy_evaluation(π)

    инициируем V(s) = 0 для всех

    whileTrue:

        Δ = 0

        для каждого :

            старое_v = V(s)

            Δ = max(Δ, |V(s) – старое_v|)

        if Δ < предел:break

    return V(s)

Входнымаргументом для функции итерационной оценки стратегии является стратегия π, а возвращает она функцию ценности дляэтой стратегии. Начинаем мы с инициации V(s)равной нулю для всех состояний. Затем в бесконечном цикле инициируем переменнуюΔ, представляющую максимальноеизменение на протяжении текущей итерации. Мы использует Δ для определения момента окончания цикла: когда Δ станет достаточно малой, мы выходим изцикла. Далее для каждого состояния в пространстве состояний мы сохраняем копиюстарого значения V(s), а затем используемуравнение Беллмана для его обновления. Переменной Δ при этом присваивается значение максимального изменения V(s) в этой итерации. Придостижении сходимости мы возвращаем значение V(s).

Главныйинтерес в алгоритме представляет, конечно, часть, содержащая уравнениеБеллмана. Обратите внимание, что, строго говоря, ценность на (k+1)-й итерации зависиттолько от ценности на k-й итерации. Однако это не обязательно: действительно, мы всегдаможем воспользоваться новейшими значениями функции ценности для любогосостояния, что в конечном итоге быстрее приводит к схождению.

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

Мир-решётка в коде

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

Вначалеу нас идёт импорт всех обычных библиотек.

import numpy as np

import matplotlib.pyplot as plt

Далее идёт класс Grid. Аргументами конструктора являются ширина, высота и начальная позиция, причём последняя должна быть кортежем из двух целых чисел, а текущее местоположение будет храниться в двух переменных экземпляра i и j:

class Grid: # Environment

  def __init__(self, width, height, start):

    self.width =width

    self.height= height

    self.i =start[0]

    self.j =start[1]

Следующим идёт установщик, одновременно определяющий как вознаграждения, так и действия в среде. В actions, говоря просто, перечисляются все возможные действия, которые могут привести к новому состоянию. Так, например, если «над» нами стена, то мы можем попробовать выполнить действие «вверх», но в действительности выполнено оно не будет, поскольку не состоит в словаре действий – класс Grid просто проигнорирует его. Таким образом, и вознаграждения, и действия будут словарями, ключами в которых будут координаты (i, j), представляющие состояние, а значениями – или численное вознаграждение, или список возможных действий. Как вы увидите позже, действия будут представлены символами «U», «D», «L», и «R».

  def set(self, rewards, actions):

    # rewardsshould be a dict of: (i, j): r (row, col): reward

    # actionsshould be a dict of: (i, j): A (row, col): list of possible actions

    self.rewards= rewards

    self.actions= actions

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

  def set_state(self, s):

    self.i =s[0]

    self.j =s[1]

Следующейидёт функция current_state.Она указывает на текущую позицию агента с координатами (i, j).

  def current_state(self):

    return(self.i, self.j)

Следующаяфункция – is_terminal. Она возвращаетлогическое значение «истина», если аргумент sявляется конечным состоянием, и «ложь» – если нет. Есть простой способопределить, находимся ли мы в конечном состоянии, – проверить словарь действий.Если мы можем выполнить действие в некотором состоянии и перейти в другоесостояние, то данное состояние не является конечным.

  def is_terminal(self, s):

    return s notin self.actions

Затемидёт функция move с аргументом action.Первое, что она делает, – это проверяет, есть ли действие в словаре действий.Если нет, то мы не можем сделать движение по решётке и просто остаёмся в той жепозиции, в противном случае выполняется действие. Заметьте, что тут, следуяправилам перечисления массивов, i = 0 вверху иувеличивается по мере движения вниз, а j= 0 слева и увеличивается при движении направо. В конце возвращаетсявознаграждение за текущую позицию из словаря вознаграждений. Текущая позицияможет быть как новой позицией после выполнения действия, так и той же самой,если действие было передано, но не привело к какому-либо передвижению. Обратитевнимание, что если для данной позиции вознаграждение не определено, то поумолчанию оно считается равным нулю.

  def move(self, action):

    # check iflegal move first

    if action inself.actions[(self.i, self.j)]:

      if action== ‘U’:

        self.i-= 1

      elifaction == ‘D’:

        self.i+= 1

      elifaction == ‘R’:

        self.j+= 1

      elifaction == ‘L’:

        self.j-= 1

    # return areward (if any)

    returnself.rewards.get((self.i, self.j), 0)

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

  def undo_move(self, action):

    # these arethe opposite of what U/D/L/R should normally do

    if action ==‘U’:

      self.i +=1

    elif action== ‘D’:

      self.i -=1

    elif action== ‘R’:

      self.j -=1

    elif action== ‘L’:

      self.j +=1

    # raise anexception if we arrive somewhere we shouldn’t be

    # shouldnever happen

   assert(self.current_state() in self.all_states())

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

  def game_over(self):

    # returnstrue if game is over, else false

    # true if weare in a state where no actions are possible

    return(self.i, self.j) not in self.actions

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

  def all_states(self):

    #possibly buggy but simple way to get all states

    # either aposition that has possible next actions

    # or aposition that yields a reward

    return set(self.actions.keys() +self.rewards.keys())

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

def standard_grid():

  # define agrid that describes the reward for arriving at each state

  # and possibleactions at each state

  # the gridlooks like this

  # x means youcan’t go there

  # s meansstart position

  # number meansreward at that state

  # .  . .  1

  # .  x  . -1

  # s  . .  .

  g = Grid(3, 4,(2, 0))

  rewards = {(0,3): 1, (1, 3): -1}

  actions = {

    (0, 0):(‘D’, ‘R’),

    (0, 1):(‘L’, ‘R’),

    (0, 2):(‘L’, ‘D’, ‘R’),

    (1, 0):(‘U’, ‘D’),

    (1, 2):(‘U’, ‘D’, ‘R’),

    (2, 0):(‘U’, ‘R’),

    (2, 1):(‘L’, ‘R’),

    (2, 2):(‘L’, ‘R’, ‘U’),

    (2, 3):(‘L’, ‘U’),

  }

  g.set(rewards,actions)

  return g

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

def negative_grid(step_cost=-0.1):

  # in this gamewe want to try to minimize the number of moves

  # so we willpenalize every move

  g =standard_grid()

 g.rewards.update({

    (0, 0):step_cost,

    (0, 1):step_cost,

    (0, 2):step_cost,

    (1, 0):step_cost,

    (1, 2):step_cost,

    (2, 0):step_cost,

    (2, 1):step_cost,

    (2, 2):step_cost,

    (2, 3):step_cost,

  })

  return g

Итерационная оценка стратегии в коде

Чтобыпродемонстрировать, как можно найти функцию ценности для различных стратегий,мы проведём итерационную оценку для двух разных стратегий. Первая из рассматриваемыхстратегий – совершенно случайная. Не забывайте, что в уравнении Беллмана естьдва распределения вероятностей – π(a|s)и марковская вероятность перехода состояний p(s’,r|s,a).Какое из них, по вашему мнению, соответствует реализации уравнения Беллмана?

Правильныйответ: π(a|s). Это вероятность того,что мы выполним действие a, находясьв состоянии s. Для равномернораспределённой случайной стратегии эта вероятность будет равна единице,делённой на количество возможных действий в состоянии s: 1/|A(s)|. Вторая жевероятность – p(s’,r|s,a) –соответствует уравнению, только когда сами переходы состояний являютсяслучайными. Это ситуация, когда мы пытаемся идти влево, а вместо этого движемсявправо.

Втораястратегия, которую мы рассмотрим, – полностью определённая стратегия. Рисуноквставлен сугубо для вашего удобства (см. слайд). Из начальной позиции мыдвигаемся прямо к цели – два хода вверх и три вправо. Однако если мы начнём скакого-либо другого состояния, эта стратегия ведёт прямиком к проигрышу, апотому следует ожидать, что ценность при движении вверх вдоль левого краядолжна быть положительной, а ценность остальных состояний – отрицательной.

Атеперь перейдём к коду.

Начинаеммы с импорта обычных библиотек, а из файла grid_world импортируем функциюstandard_grid:

import numpy as np

import matplotlib.pyplot as plt

from grid_world import standard_grid

Порог сходимости обозначим через SMALL_ENOUGH и установим равным10-4:

SMALL_ENOUGH = 1e-3 # threshold for convergence

Далееу нас идут две функции, которые помогут нам наглядно показать стратегии иценности. Первая функция – print_values. Её аргументами являются словари ценностей V и решётки g, а сама она вкаждой позиции выводит значение ценности:

def print_values(V,g):

  for i in xrange(g.width):

    print“—————————“

    for j in xrange(g.height):

      v =V.get((i,j), 0)

      if v >=0:

        print” %.2f|” % v,

      else:

        print“%.2f|” % v, # -ve sign takes up an extra space

    print “”

Функцияprint_policy очень похожа,разве что её аргументом является стратегия P,а не функция ценности V. Как и V, она определяется координатами i и j,представляющими состояние, однако ценность может изменяться. Обратите внимание,что это работает только для детерминированных стратегий, поскольку мы не можемвыводить более одного значения в позиции.

def print_policy(P,g):

  for i in xrange(g.width):

    print“—————————“

    for j in xrange(g.height):

      a =P.get((i,j), ‘ ‘)

      print”  %s  |” % a,

    print “”

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

if __name__ == ‘__main__’:

  # iterativepolicy evaluation

  # given apolicy, let’s find it’s value function V(s)

  # we will dothis for both a uniform random policy and fixed policy

  # NOTE:

  # there are 2sources of randomness

  # p(a|s) –deciding what action to take given the state

  # p(s’,r|s,a)– the next state and reward given your action-state pair

  # we are onlymodeling p(a|s) = uniform

  # how wouldthe code change if p(s’,r|s,a) is not deterministic?

  grid =standard_grid()

  # states willbe positions (i,j)

  # simpler thantic-tac-toe because we only have one “game piece”

  # that canonly be at one position at a time

  states = grid.all_states()

Далеемы выполняем оценку стратегии для равномерно распределённых случайных действий.Первый этап – инициировать все V[s] равными 0, затем мы устанавливаем коэффициентобесценивания равным 1. После этого мы входим в бесконечный цикл, в телекоторого просматриваем все состояния, сохраняя старые значения V[s], чтобы можнобыло отслеживать абсолютную величину каждого изменения. Далее мы просматриваемвсе возможные действия в этом состоянии, используя переменную new_V для накопленияответа, поскольку он будет суммой по различным действиям. Вероятностьвыполнения любого действия равна единице, делённой на количество возможныхдействий. Тут-то и вступает в действие операция упреждения, о которой шла речьранее: мы должны сначала установить состояние s, а затем выполнить действие, чтобы можно былоопределить следующее состояние s’, необходимоедля использования уравнения Беллмана. После этого мы добавляем члены суравнения Беллмана к переменной new_v. Как только цикл завершается, мы устанавливаем V[s] равным new_v и обновляемнаибольшее изменение, чтобы оно было максимальным среди всех предыдущихнаибольших изменений и новым. Теперь можно проверить, не оказалось ли этонаибольшее изменение меньше нашего порогового значения и если да, то мы выходимиз цикла и выводим на экран найденные значения:

  ###uniformly random actions ###

  # initializeV(s) = 0

  V = {}

  for s instates:

    V[s] = 0

  gamma = 1.0 #discount factor

  # repeat untilconvergence

  while True:

   biggest_change = 0

    for s instates:

      old_v =V[s]

      # V(s)only has value if it’s not a terminal state

      if s ingrid.actions:

        new_v =0 # we will accumulate the answer

        p_a =1.0 / len(grid.actions[s]) # each action has equal probability

        for a ingrid.actions[s]:

         grid.set_state(s)

          r =grid.move(a)

          new_v+= p_a * (r + gamma * V[grid.current_state()])

        V[s] =new_v

       biggest_change = max(biggest_change, np.abs(old_v – V[s]))

    ifbiggest_change < SMALL_ENOUGH:

      break

  print“values for uniformly random actions:”

 print_values(V, grid)

  print“\n\n”

Затеммы переходим к фиксированной стратегии. Вначале мы выводим её на экран, чтобывы знали, как она выглядит. Далее мы заново инициируем все V[s] равными нулю,но на этот раз коэффициент обесценивания установим равным 0,9, так что ценностьбудет уменьшаться по мере удаления от целевого состояния. Затем мы точно так женачинаем цикл, как и ранее. Обратите внимание, насколько проще он стал: нам нетнеобходимости просматривать все действия, поскольку есть только одно действиена состояние. В связи с этим вероятность действия в этом состоянии равна 1.Остальная часть цикла остаётся прежней. Когда цикл заканчивается, мы вновьвыводим на экран значения ценностей.

  ### fixedpolicy ###

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

  }

  print_policy(policy,grid)

  # initializeV(s) = 0

  V = {}

  for s instates:

    V[s] = 0

  # let’s seehow V(s) changes as we get further away from the reward

  gamma = 0.9 #discount factor

  # repeat untilconvergence

  while True:

    biggest_change= 0

    for s instates:

      old_v =V[s]

      # V(s)only has value if it’s not a terminal state

      if s inpolicy:

        a =policy[s]

       grid.set_state(s)

        r =grid.move(a)

        V[s] = r+ gamma * V[grid.current_state()]

       biggest_change = max(biggest_change, np.abs(old_v – V[s]))

    ifbiggest_change < SMALL_ENOUGH:

      break

  print“values for fixed policy:”

print_values(V,grid)

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

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

Что касается фиксированной стратегии с коэффициентом обесценивания 0,9, то мы получаем ожидаемую картину: чем дальше мы от конечного состояния, тем сильнее падает ценность, каждый раз ровно на 10%. Так, 0,81 – это 0,9 * 0,9, 0,73 – это 0,81*0,9 и так далее.

Совершенствование стратегии

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

Ещёраз взглянем на наше рекурсивное определение Q. Оно указывает нам ценность выполнения действия a, пребывая всостоянии sи используя стратегию π:

Используятекущую стратегию, мы просто получаем текущую функцию ценности состояний:

Однакопредположим, что мы хотим изменить лишь одно из действий в стратегии. Можем лимы так сделать? Конечно, можем! У нас есть конечный набор действий, поэтомувсё, что нам нужно, – это выбрать то, которое даст большее Q, чем при π(s):

Здесьоказываются очень полезными упражнения по программированию. Выглядит это каксугубо абстрактное уравнение, однако оно просто говорит нам, что если стратегияна данный момент подталкивает нас «вверх», то давайте посмотрим, не приводит лидвижение «влево», «право» или «вниз» к большему Q, и если приводит, то давайте изменим нашу стратегиюдля этого состояния, включив это новое действие. Формально говоря, выбираяновое действие для состояния, мы находим новую стратегию π’, имеющую большуюценность для состояния, чем π:

Иделается этого ради того, чтобы выбрать действие, дающее нам наибольшее Q. Заметьте, чтомы можем записать это как с использованием Q, так и в виде поиска по V:

Иделается этого ради того, чтобы выбрать действие, дающее нам наибольшее Q. Заметьте, чтомы можем записать это как с использованием Q, так и в виде поиска по V:

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

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

В случае, когда имеем строго меньше, мы совершенствуем стратегию, когда же получаем равенство, улучшений больше нет – мы нашли оптимальную стратегию.

Продолжение по итерации стратегий смотрите в следующей статье!

В случае, когда имеем строго меньше, мы совершенствуем стратегию, когда же получаем равенство, улучшений больше нет – мы нашли оптимальную стратегию.

Продолжение по итерации стратегий смотрите в следующей статье!

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

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