Этот пост представляет собой резюме лекции 1 Deep RL Bootcamp 2017 в Калифорнийском университете в Беркли. Все рисунки, уравнения и текст взяты из слайдов лекций и видеороликов, доступных здесь.
Проблемы RL моделируются как Марковские процессы принятия решений (MDP). В MDP есть агент, который взаимодействует с окружающей средой. Агент может наблюдать за состоянием (s_t) и вознаграждением (r_t), а также выполнять действие (a_t). В результате его действия среда изменится на состояние s_ (t + 1), и будет получено немедленное вознаграждение r_ (t + 1).
Несколько примеров успешных историй успеха RL включают Atari game 2013, Go player 2016.
Есть несколько способов решения проблем RL. Здесь мы сначала рассмотрим итерацию политики и итерацию значения, которые основаны на динамическом программировании.
Чтобы сформулировать проблему, MDP определяется как
- Набор состояний S , напр. пиксели экрана в Atari Breakout, углы сочленений и скорости в роботе.
- Набор действий A, напр. влево, вправо или команда огня в Atari Breakout, значения фонарей для разных двигателей.
- Функция перехода P (s ’| s, a), распределение следующего состояния с учетом текущего состояния и действия.
- Функция вознаграждения R (s, a, s '), определяет вознаграждение за данное состояние s и выполнение действия a, переход в состояние s '.
- Начальное состояние s_0.
- Коэффициент дисконтирования γ, насколько вы заботитесь о будущем по сравнению с настоящим временем?
- Horizon H, как долго вы собираетесь действовать, конечное или бесконечное
В качестве примера рассмотрим Gridworld, как показано ниже. Агент может перемещаться на север, восток, запад и юг. Если агент достигнет синего ромба, он получит награду +1. Если он упадет в оранжевый квадрат, он получит награду -1. Достижение любого другого места в лабиринте не приносит никакой награды.
Цель состоит в том, чтобы найти оптимальную политику, чтобы максимизировать ожидаемую сумму вознаграждений в соответствии с этой политикой .
Политика π определяет, какое действие предпринять для данного состояния. Это может быть распределение по действиям или детерминированная функция. В качестве примера ниже показана детерминированная политика π для Gridworld.
Задача оптимального управления или планирования состоит в том, чтобы по заданному MDP (S, A, P, R, γ, H) найти оптимальную политику π *. Два точных метода решения этой проблемы - это итерация значения и итерация политики.
Итерация значений
В итерации значения концепция, называемая функцией оптимального значения V *, определяется как
который представляет собой сумму вознаграждений со скидкой при запуске в состоянии s и при оптимальных действиях.
Например, функция оптимального значения Gridworld с детерминированной функцией перехода, то есть действия всегда успешны, гамма = 1 и H = 100 вычисляются следующим образом:
V*(4,3) = 1
V*(3,3) = 1
V*(2,3) = 1
V*(1,1) = 1
V*(4,2) = -1
Другой пример, функция оптимального значения Gridworld, когда действия всегда успешны, гамма = 0,9 и H = 100 рассчитываются как:
V*(4,3) = 1
V * (3,3) = 0,9 # из-за коэффициента дисконтирования гамма = 0,9
V*(2,3) = 0.9*0.9 = 0.81
V*(1,1) = 0.9*0.9*0.9*0.9*0.9 = 0.59
V*(4,2) = -1
Другой пример, функция оптимального значения, если действия успешны с вероятностью 0,8, с вероятностью 0,1 она может остаться на том же месте и с вероятностью 0,1 она может перейти в соседнее состояние, гамма = 0,9, H = 100, рассчитываются как:
V*(4,3) = 1
V*(3,3) = 0.8 * 0.9 + 0.1 * 0.9 * V*(3,3) + 0.1 * 0.9 * V*(3,2)
V*(2,3) =
V*(1,1) =
V*(4,2)
Как видите, в случае стохастической функции перехода функция оптимального значения для состояния зависит от функции значения других состояний. Другими словами, это требует рекурсивного / итеративного расчета. Вот где может сыграть роль итерация значений!
Алгоритм итерации значений показан ниже:
Здесь:
Оптимальные значения для Gridworld с H = 100, скидкой = 0,9 и шумом = 0,2 вычислены и показаны ниже. Отмечается, что после определенного количества итераций функция цены перестает существенно меняться.
Итерация значений гарантированно сходится. При сходимости находится функция оптимального значения и, как следствие, оптимальная политика.
Итерация Q-значения
Мы рассмотрим другой метод, называемый Q-Learning, для решения задач RL. С этой целью оптимальное значение Q определяется как:
Q-значения аналогичны V-значениям, за исключением того, что в дополнение к состоянию s функции также передается действие a. Аналогичным образом существует уравнение Беллмана для значений Q
Для решения Q * итерация Q-значения определяется как
Есть несколько преимуществ использования Q-обучения по сравнению с итерацией значений, которые будут обсуждаться позже. На данный момент стоит отметить, что в Q-обучении мы вычисляем только Q-значения, и оно неявно кодирует оптимальную политику в отличие от итерации значений, которая нам нужна для отслеживания как политики, так и функции значения.
Например, значения Q для Gridworld с гаммой = 0,9 и шумом = 0,2 после 100 итераций будут выглядеть, как показано ниже. Для каждого состояния существует четыре значения Q, поскольку необходимо предпринять четыре действия.
Итерация политики
Наконец, мы рассмотрим оценку политики / итерацию политики. При оценке политики мы фиксируем политику и вычисляем итерацию значения для данной политики как
Как видно из приведенного выше уравнения, операция max удалена, так как политика теперь исправлена, и в результате нужно предпринять только одно действие, а именно π (s).
Таким образом, итерация политики приведена ниже. Мы повторяем, пока политика не сходится. При некоторых условиях он сходится быстрее, чем итерация значений.
Примечание. Лабораторная работа 1 включает примеры итерации значения и итерации политики.
Заворачивать
На первой лекции были представлены основы RL и MDP. Были описаны точные методы решения небольших проблем MDP. Это следующие методы: итерация значения, Q-обучение и итерация политики. Ограничения этих методов включают: они требуют повторения и хранения для всех состояний и действий. Таким образом, они подходят для небольшого дискретного пространства состояния и действия. Кроме того, для обновления уравнений им требуется доступ к динамике среды или функции перехода P (s ’| s, a).
Если вы нашли эту статью полезной, попробуйте нажать кнопку хлопка. Не стесняйтесь поделиться этой статьей на своей платформе. Вы также можете следить за мной в Twitter за последними сообщениями.
