1. Введение
В задаче о сетке агент помещается в прямоугольный массив M X N. Ячейки сетки соответствуют состояниям окружающей среды. В каждой ячейке возможны четыре действия: ВВЕРХ, ВНИЗ, ВЛЕВО и ВПРАВО. Задача агента — изучить политику, с помощью которой он стохастически или детерминистически выбирает действие в конкретном состоянии. Среда
реагирует, переводя агента в следующее состояние и предоставляя агенту немедленное вознаграждение. Например, если агент находится в (i, j), i-я строка, j-й столбец. Выбрав действие «Влево», среда может отреагировать, переведя агента в (i, j − 1) ячейку. Наша цель — научить агента переходить из произвольного состояния в конечное состояние, чтобы он научился максимизировать долгосрочные выгоды. Для реализации методов обучения с подкреплением взаимодействие агента и среды настраивается как марковский процесс принятия решений.
На каждом временном шаге t агент находится в одном из состояний среды, St ∈ S , где S — множество возможных состояний,
и на этом основании выбирает действие, At ∈ A, где A — множество действий. Через один временной шаг в результате своего
действия агент получает награду Rt+1 и переходит в новое состояние St+1. Вероятность достижения нового состояния St+1 и получения вознаграждения Rt+1 не зависит от прошлых переходов при условии, что состояние St и действие At известны как марковское свойство.
2. Постановка проблемы
Рассмотрим сетку 6X6 с состояниями (i, j), 1 ≤ i; j ≤ 6. Предположим, что состояния (4, 3) и (5, 3) удалены (вы можете думать
о них как о дырах). На каждом квадрате вам разрешены следующие действия: попытка влево, попытка вправо, попытка вверх и
попытка вниз. Когда вы пытаетесь совершить действие, вы можете добиться успеха с вероятностью 0,8. С вероятностью 0,1 вы останетесь
там, где находитесь. С вероятностью 0,05 вы двигаетесь в направлении +90◦ (по часовой стрелке) к предпринятому направлению и -90◦
(против часовой стрелки) к предпринятому направлению. Если когда-нибудь попытка хода выведет вас из сетки или заведет в дыру
, вы останетесь там, где были. Кроме того, есть ограниченная ячейка (6, 3), которую агент должен научиться избегать. (6, 6) — это
конечное состояние, и как только вы попадете в это состояние, эпизод закончится.
Рисунок 2: Настройка мира сетки. Зеленая точка представляет конечное состояние. Красный цвет обозначает состояние, которое следует
избегать, а серые точки — дыры.
3. Настройка вознаграждений
Если действия агента приводят к посещению (6, 3), он получает вознаграждение в размере -15, а если действие приводит к посещению (6, 6), он получает
награда +15. Остальные оставшиеся переходы возвращают нулевое вознаграждение.
4.Динамический подход к программированию
Значение p(r, s’ |s, a) есть вероятность перехода. Это вероятность того, что после принятия At = a при St = s агент достигнет состояния St+1 = s и получит вознаграждение Rt+1 = r. Когда вероятности перехода неизвестны, приходится полагаться на методы Монте-Карло. Позже мы увидим метод Монте-Карло и другие алгоритмы, основанные на моделировании.
Итеративная оценка политики
Улучшение политики
Чтобы также получить оптимальную политику, реализуем алгоритм улучшения политики.
Теорема об улучшении политики предполагает, что мы можем улучшить данную политику (если не оптимальную), перенеся ненулевую вероятность неоптимальных действий на любое из оптимальных действий. Он предоставляет нам итеративный алгоритм для детерминированного выбора лучшего действия для всех состояний на данной итерации. Затем мы используем оценку политики для обновления функции ценности и повторяем процесс, пока не сойдемся на оптимальной политике.
Если мы дадим ту же проблему человеку, скорее всего, он придумает тот же набор действий. Обратите внимание, как агент учится избегать ячейки с ограниченным доступом (6,3). Если мы поместим агента в ячейку (6,2), он не выполнит действие, так как тогда у нас все еще есть вероятность 0,05 войти в запрещенную ячейку (6,3). Выбор влево гарантирует, что он не перепрыгнет на ячейку (6,3).
5. Моделирование методом Монте-Карло
В этом и следующем разделах мы рассмотрим другой подход к изучению оптимальных политик. Алгоритмы динамического программирования бесполезны, когда мы не знаем вероятности перехода. В таких сценариях мы полагаемся на прошлый опыт агента, чтобы оценить значения состояния-действия. Алгоритм на основе моделирования не требует явного знания вероятностей перехода, но требует механизма для генерации эпизода (последовательности состояний, действий и вознаграждений) в соответствии с вероятностями перехода. Опыт (сбор образцов) делится на эпизоды. Все эпизоды в конечном итоге завершаются независимо от того, какие действия выбраны. Здесь у нас есть только (6,6) в качестве конечного состояния. Новый эпизод начинается, когда агент достигает (6,6). Оценки стоимости и политики меняются только по завершении эпизода. Моделирование не ограничивается фактическим выполнением задачи в течение многих эпизодов. Это может быть образцом прошлого опыта.
Существует два варианта алгоритмов MC. А именно первое посещение и каждое посещение. мы хотим оценить vπ(s) по набору эпизодов, полученному в соответствии с политикой π. Каждое появление состояния s в эпизоде называется посещением s. s могут быть посещены несколько раз в одном и том же эпизоде. Метод MC при первом посещении оценивает vπ(s) как среднее значение доходности после первых посещений s, тогда как метод MC при каждом посещении усредняет доход после всех посещений s. Сначала мы пишем код для создания эпизода для любой заданной политики на основе вероятностей перехода.
Монте-Карло, Испания
Мы рассмотрим метод MC первого посещения. Теоретически, если мы сгенерируем бесконечное количество эпизодов и сохраним запись дисконтированных возвратов после первого посещения состояния, а также гарантируем, что каждое состояние будет посещено бесконечное количество раз за бесконечные эпизоды, то выборочное среднее доходностей после первого посещения состояния s, усредненное по всем эпизодам, будет сходиться к vπ(s). Эти два предположения вовсе не гарантируются, если мы начинаем каждый эпизод с определенного состояния и запускаем этот алгоритм только для конечного числа эпизодов. Мы согласны с конечным числом эпизодов, поскольку близкое приближение к значениям состояния достаточно для нашей цели. Даже в методах динамического программирования мы сходимся к значениям, а не получаем точную функцию значения состояния. Чтобы иметь дело с предположением, что все состояния посещаются достаточно большое количество раз, мы реализуем идею начала исследования. Мы можем начать каждый эпизод в произвольном состоянии, так что выбор любого конкретного состояния в начале будет ненулевым. У нас есть аналогичный алгоритм оценки Qπ(s, a) для всех пар состояние-действие. Мы делаем то же самое, мы сохраняем запись для возвратов, следующих после выбора действия a в состоянии s. Мы усредним доходность по всем эпизодам, это будут наши оценки Qπ(s, a). Мы будем обновлять нашу политику после каждого эпизода так же, как мы делали это при улучшении политики, детерминистически выбирая действие, которое максимизирует ценность действия состояния для данного состояния. Примечание. Можно застрять на плохой детерминированной политике. В таких случаях выполнение эпизодов может занять много времени. Таким образом, мы должны отбросить конкретный эпизод, если он занимает больше некоторого фиксированного количества временных шагов.
