Динамическое программирование. Итерация по стратегиям

Итерация по стратегиям

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

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

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

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

policy_changed = False

for s in all_states:

    old_a =policy(s)

    policy(s) =argmax[a] {sum[s’, r] { p(s’, r | s, a) [r + gamma*V(s’) } }

    if policy(s)!= old_a: policy_changed = True

if policy_changed: возврат к этапу 2

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

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

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

Начинаем мы с обычного импорта библиотек; из файла grid_world нам понадобятся функции standard_grid и negative_grid. Мы используем negative_grid, но я убедительно рекомендую попробовать и standard_grid, чтобы посмотреть, получится ли у агента отыскать хорошую стратегию.

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

Далеемы определяем ряд констант. У нас вновь есть пороговое значение для нахожденияV(s) – переменная SMALL_ENOUGH, переменная GAMMА, представляющая коэффициентобесценивания, и ALL_POSSIBLE_ACTIONS с четырьмя направлениями по решётке:

SMALL_ENOUGH = 10e-4

GAMMA = 0.9

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

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

# this is deterministic

# all p(s’,r|s,a) = 1 or 0

Следующимидёт раздел main. Вначале идёт функция negative_grid с установленной поумолчанию ценой шага -0,1. После этого мы выводим вознаграждения, чтобы знать,как они выглядят. Обратите внимание, что здесь мы можем просто использоватьфункцию print_values, поскольку она выводит на экран любой словарь сместоположением в качестве ключа и числом в качестве значения ценности.

if __name__ == ‘__main__’:

  # this grid givesyou a reward of -0.1 for every non-terminal state

  # we want to seeif this will encourage finding a shorter path to the goal

  grid =negative_grid()

  # print rewards

  print“rewards:”

 print_values(grid.rewards, grid)

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

  # state ->action

  # we’ll randomlychoose an action and update as we learn

  policy = {}

  for s ingrid.actions.keys():

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

  # initial policy

  print“initial policy:”

 print_policy(policy, grid)

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

  # initialize V(s)

  V = {}

  states =grid.all_states()

  for s in states:

    # V[s] = 0

    if s ingrid.actions:

      V[s] =np.random.random()

    else:

      # terminalstate

      V[s] = 0

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

  # repeat untilconvergence – will break out when policy does not change

  while True:

    # policyevaluation step – we already know how to do this!

    while True:

     biggest_change = 0

      for s instates:

        old_v =V[s]

        # V(s) onlyhas 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

Следующимидёт этап совершенствования стратегии. У нас есть флаг is_policy_converged,который мы инициируем со значением «истина». Далее мы перебираем все состояния,выбираем существующее действие и присваиваем его переменной old_a, после чегоперебираем все возможные состояния для поиска новой лучшей последующейценности. Мы выбираем действие, дающее нам лучшую ценность, и обновляемстратегию. Если новое действие new_a не равно старому old_a, флагуis_policy_converged присваивается значение «ложь». При окончании прохода цикласовершенствования стратегии мы проверяем, изменилась ли стратегия, и если нет,то прерываем основной цикл:

    # policyimprovement step

   is_policy_converged = True

    for s instates:

      if s inpolicy:

        old_a =policy[s]

        new_a =None

        best_value= float(‘-inf’)

        # loopthrough all possible actions to find the best current action

        for a inALL_POSSIBLE_ACTIONS:

         grid.set_state(s)

          r =grid.move(a)

          v = r +GAMMA * V[grid.current_state()]

          if v >best_value:

           best_value = v

            new_a =a

        policy[s] =new_a

        if new_a !=old_a:

         is_policy_converged = False

    ifis_policy_converged:

      break

Ив конце выводим на экран окончательные значения ценностей и окончательнуюстратегию:

  print“values:”

  print_values(V,grid)

  print“policy:”

  print_policy(policy,grid)

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

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

Итерация по стратегиям в мире-решётке с ветром

Модификация нашей среды, которая называется «мир-решётка с ветром».

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

Тути возникает мир-решётка с ветром. Представьте, что мы идём по обдуваемой ветромулице. Мы стараемся идти прямо, однако ветер отталкивает нас назад или влево.То же самое будет происходить с агентом: он будет пытаться идти вверх, но вместоэтого среда иногда будет отталкивать его в каком-то другом направлении. В нашемслучае вероятность выполнения запланированного действия установим равной 0,5, авероятности выполнения других трёх действий – равными 0,5/3.

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

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

import numpy as np

from grid_world import standard_grid, negative_grid

from iterative_policy_evaluation import print_values,print_policy

SMALL_ENOUGH = 1e-3

GAMMA = 0.9

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

Одноиз главных отличий этого мира-решётки заключается в том, что теперь онвероятностный, поэтому изменяется значение цены шага, определяемого переменной step_cost. Что будет, если мы установим её равной -1,0?Поскольку достижение цели даёт нам вознаграждение лишь 1, а попадание впроигрышное состояние – вознаграждение –1, то ясно, что агент на самом делезахочет закончить игру как можно быстрее, даже если это означает попадание впроигрышное состояние. Например, если мы находимся в трёх шагах от цели, тополучим вознаграждение в -3, прежде чем у нас появится хотя бы шанс достичь её.Однако если при этом мы всего в шаге от состояния проигрыша, то получимвознаграждение только в -1. Не забывайте, что цель агента – вовсе не достижениетого, что мы определяем как выигрышное или проигрышное состояние. Он лишьстарается максимизировать своё вознаграждение. В связи с этим я рекомендуюиспытать разные решётки с разной ценой шага и понаблюдать, что из этогополучится.

# next state and reward will now have some randomness

# you’ll go in your desired direction with probability0.5

# you’ll go in a random direction a’ != a withprobability 0.5/3

if __name__ == ‘__main__’:

  # this grid givesyou a reward of -0.1 for every non-terminal state

  # we want to seeif this will encourage finding a shorter path to the goal

  grid =negative_grid(step_cost=-1.0)

  # grid =negative_grid(step_cost=-0.1)

  # grid =standard_grid()

Послеэтого мы выводим на экран вознаграждения, чтобы знать, как они выглядят.

  # print rewards

  print“rewards:”

 print_values(grid.rewards, grid)

Далеемы генерируем случайную стратегию и случайную функцию ценности – то же самое,что и в детерминированном случае.

  # state ->action

  # we’ll randomlychoose an action and update as we learn

  policy = {}

  for s ingrid.actions.keys():

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

  # initial policy

  print“initial policy:”

 print_policy(policy, grid)

  # initialize V(s)

  V = {}

  states =grid.all_states()

  for s in states:

    # V[s] = 0

    if s ingrid.actions:

      V[s] =np.random.random()

    else:

      # terminalstate

      V[s] = 0

Затеммы входим в основной цикл. Первый этап – оценка стратегии. Обратите внимание,что теперь мы должны добавить вероятность перехода состояния, хотя имейте ввиду, что сама стратегия является детерминированной. Мы тут можем поиграть сдвумя вероятностями, но в этот раз ограничимся лишь переходами состояний. Итак,мы перебираем все возможные действия, исходя из текущей стратегии. Вероятностьвыполнения этого действия равна 0,5, вероятность выполнения другого – 0,5/3.

  # repeat untilconvergence – will break out when policy does not change

  while True:

    # policyevaluation step – we already know how to do this!

    while True:

     biggest_change = 0

      for s instates:

        old_v =V[s]

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

        new_v = 0

        if s inpolicy:

          for a inALL_POSSIBLE_ACTIONS:

            if a ==policy[s]:

              p =0.5

            else:

              p =0.5/3

           grid.set_state(s)

            r =grid.move(a)

            new_v+= p*(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

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

    # policyimprovement step

    is_policy_converged= True

    for s instates:

      if s inpolicy:

        old_a =policy[s]

        new_a =None

        best_value= float(‘-inf’)

        # loopthrough all possible actions to find the best current action

        for a inALL_POSSIBLE_ACTIONS: # chosen action

          v = 0

          for a2 inALL_POSSIBLE_ACTIONS: # resulting action

            if a ==a2:

              p =0.5

            else:

              p =0.5/3

           grid.set_state(s)

            r =grid.move(a2)

            v +=p*(r + GAMMA * V[grid.current_state()])

          if v >best_value:

           best_value = v

            new_a =a

        policy[s] =new_a

        if new_a !=old_a:

         is_policy_converged = False

    ifis_policy_converged:

      break

Вконце выводится ценность окончательной стратегии.

  print“values:”

  print_values(V,grid)

  print“policy:”

 print_policy(policy, grid)

# result: every move is as bad as losing, so lose asquickly as possible

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

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

Итерация по ценности

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

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

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

Алгоритм,который рассматривается в этой лекции, делает шаг вперёд. Он называетсяитерацией по ценности и объединяет оценку стратегии с её совершенствованием водно целое. Любопытно, что при этом выглядит он почти идентично уже виденномунами уравнению:

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

Итак,это уравнение очень похоже на уравнение оценки стратегии за исключением того,что теперь мы ищем максимум по всем возможным действиям. Этот алгоритм такжеитеративный, как видно из индекса k. Как и в случае оценки стратегии, на самом деле нам нет нуждыждать всех k итераций V, чтобы начатьвычислять (k+1)-ю итерацию V – мы можем обновлятьзначение «на месте». Обратите внимание, как тут объединяются и оценка, исовершенствование стратегии в один этап. Это связано с тем, чтосовершенствование стратегии происходит при нахождении аргумента максимизации (argmax) выражения справа. Таким образом, просто находя максимум, мысовершаем этап оценки той стратегии, которую мы бы выбрали при использовании argmax.

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

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

while True:

    Δ = 0

    для каждого s = S:

    old_V = V(s)

        Δ = max(Δ, |V(s) – old_v|)

    ifΔ < пороговоезначение: break

для каждого s = S:

Первый этап – инициировать V произвольным образом. Это могут быть случайные числа или нули, не важно. Затем мы входим в бесконечный цикл. Как и в случае оценки стратегии, мы отслеживаем наибольшее изменение и прерываем цикл, когда это наибольшее изменение падает ниже некоторого порогового уровня, указывая на схождение. Единственное отличие между этим алгоритмом и оценкой стратегии состоит в том, что мы находим максимум по всем действиям для уравнения Беллмана справа. После схождения мы выводим стратегию π(s), взяв argmax по каждому V(s).

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

Если вы не хотите писать код сами, хотя я настоятельно рекомендую сделать именно так, то соответствующий файл для этой лекции называется value_iteration.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

SMALL_ENOUGH = 10e-4

GAMMA = 0.9

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

# this is deterministic

# all p(s’,r|s,a) = 1 or 0

Перейдём к разделу main. Тут всё как прежде – negative_grid, вывод на экран вознаграждений, с которыми вы уже знакомы, а также инициация стратегии. Кроме того, мы случайным образом инициируем V(s).

if __name__ == ‘__main__’:

  # thisgrid gives you a reward of -0.1 for every non-terminal state

  # we want tosee if this will encourage finding a shorter path to the goal

  grid =negative_grid()

  # printrewards

  print“rewards:”

 print_values(grid.rewards, grid)

  # state ->action

  # we’llrandomly choose an action and update as we learn

  policy = {}

  for s ingrid.actions.keys():

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

  # initialpolicy

  print“initial policy:”

 print_policy(policy, grid)

  # initializeV(s)

  V = {}

  states =grid.all_states()

  for s instates:

    # V[s] = 0

    if s ingrid.actions:

      V[s] =np.random.random()

    else:

      # terminalstate

      V[s] = 0

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

  # repeatuntil convergence

  # V[s] =max[a]{ sum[s’,r] { p(s’,r|s,a)[r + gamma*V[s’]] } }

  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:

        new_v = float(‘-inf’)

        for a inALL_POSSIBLE_ACTIONS:

         grid.set_state(s)

          r =grid.move(a)

          v = r+ GAMMA * V[grid.current_state()]

          if v > new_v:

           new_v = v

        V[s] =new_v

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

    ifbiggest_change < SMALL_ENOUGH:

      break

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

  # find apolicy that leads to optimal value function

  for s inpolicy.keys():

    best_a =None

    best_value =float(‘-inf’)

    # loopthrough all possible actions to find the best current action

    for a inALL_POSSIBLE_ACTIONS:

     grid.set_state(s)

      r =grid.move(a)

      v = r +GAMMA * V[grid.current_state()]

      if v >best_value:

       best_value = v

        best_a =a

    policy[s] =best_a

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

  # ourgoal here is to verify that we get the same answer as with policy iteration

  print“values:”

 print_values(V, grid)

  print“policy:”

 print_policy(policy, grid)

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

Можем подтвердить, что получился прежний ответ.

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

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

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

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

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

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

Хотяв этой части мы представили итерацию по стратегиям как алгоритм динамическогопрограммирования, вы увидите, что главный принцип, лежащий в основе итерации постратегиям, будет появляться вновь и вновь на протяжении всего курса. В чём он заключается?В том, что мы итерационно выполняем два этапа – оценку стратегии и еёсовершенствование, чередуя эти два этапа, пока не достигнем схождения. Единственныйспособ достичь схождения – дождаться, когда уравнение Беллмана станет истинным,или, другими словами, ценность сойдётся для заданной стратегии, а стратегиястабилизируется относительно жадного выбора функции ценности. Это можнопоказать наглядно с помощью двухмерной диаграммы (см. слайд). Вначале стратегияи функция ценности могут быть очень неоптимальными, но требование, чтобыстратегия была жадной относительно функции ценности, а та, в свою очередь, соответствоваластратегии, позволяет приблизиться к оптимальной стратегии и оптимальной функцииценности.

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

Пустьколичество состояний равно N, а количество действий – M. Еслидопустить, что агент может перейти из начального состояния в целевое за O(N) ходов, то у насполучится последовательность действий длиной O(N), а количество возможных действий будетравняться MN.На практике пришлось бы составить список всех перестановок последовательностейвозможных состояний, а затем делать оценку стратегии для каждой из них,сохраняя стратегию, которая даёт максимальную функцию ценности. Тут происходитрост по экспоненте в зависимости от количества состояний, поэтому легко видеть,насколько динамическое программирование является более эффективным.

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

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

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

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