RL - Основы алгоритмов и терминов
Краткое изложение основных алгоритмов, терминов и концепций обучения с подкреплением.
Определения
Марковский процесс принятия решений (MDP)
Горизонт: количество временных шагов, которые мы выбираем или моделируем.
Фактор скидки: скидка на будущие вознаграждения.
Обозначение
Другое соглашение:
Обучение с подкреплением
Функция значения
Функция состояния-значения (общие награды от состояния s):
Функция ценности действия (общие награды за выполнение действия a в состоянии s)
Преимущества функции:
Функция оптимального значения V *
Оптимальная политика
Линейная система с аддитивным гауссовским шумом.
Линейный гауссовский регулятор
Линейная гауссова динамика
Алгоритмы армирования
Итерации значений
Уравнение Беллмана:
Алгоритмы:
Итерации Q-значения
Уравнение Беллмана:
Итерация:
Итерации политики
Оценка политики
Итерации:
Алгоритм:
Q-обучение (SARSA Max)
Алгоритм:
Глубокое Q-обучение
Градиент политики
Градиент политики Монте-Карло с базовой линией:
Градиент естественной политики
TRPO
Поиск строки с возвратом:
Алгоритм "актер-критик"
Актер-критик одного действия
A3C
A3C - это асинхронная версия A2C.
DDPG
Добавление параметра шума для исследования:
Поиск по дереву Монте-Карло (MCTS)
Выборка по важности
В RL мы можем захотеть оценить функции ценности для политики π, но мы собираем только выборочные результаты из π ’. Выборка по важности позволяет нам оценить политику из другой политики.
Выборка по важности - это метод оценки ожидаемого значения f (x), где x имеет распределение данных p. Однако вместо выборки из p мы вычисляем результат из выборки q.
Мы отбираем данные из q и оцениваем ожидаемое значение для p, используя:
Чтобы это работало, q (xi) не может быть нулевым, если соответствующий p (xi) не равен нулю. Продемонстрируем это на примере и вычислим 𝔼 [f (x)] с распределением данных x1 и x2 по отдельности .
Теперь мы повторно оцениваем ожидаемое значение для x2 на основе результатов выборки с использованием x1.
В RL мы выбираем результаты, используя текущую политику π1, и мы можем использовать выборку по важности для оценки результата, если мы перейдем к политике π 2.
Функция преимущества с выборкой по важности .
Функция преимущества - это вознаграждение со скидкой за вычетом базового уровня. Существует множество возможных способов вычисления функций ценности (дисконтированных вознаграждений), включая внедрение метода Монте-Карло, временную разницу или их комбинацию. Для полноты картины ниже приводится k-шаговый прогноз, используемый в A3C для вычисления функции преимущества. Это k-этапное развертывание. Мы наблюдаем за вознаграждениями и сравниваем их со значением функции соответствующего состояния, которое может быть аппроксимировано глубокой сетью.
Есть много возможных исходных условий. Различные базовые показатели могут достигать одной и той же оптимальной точки, если это не зависит от модели политики θ. Таким образом, на основе выбора вычисления функций ценности вы можете выбрать соответствующую базовую линию, чтобы уменьшить дисперсию вычислений.
Выборка по важности вычисляет функцию преимущества A путем выборки Â с использованием текущей политики θk. Затем результат повторно калибруется для новой политики θ с использованием отношения вероятностей между этими двумя политиками.
Метод доверенного региона
ε-жадная политика
Чтобы выбрать k-й эпизод, мы используем приведенный ниже ε-жадный алгоритм, чтобы выбрать, какое действие выбрать следующим. Вот распределение данных, используемое при выборе действия:
Dyna-Q
DAgger: агрегирование наборов данных
DAgger - это алгоритм аргументации обучающего набора данных с экспертными демонстрациями для состояний, которые могут посещаться текущей изученной политикой. Таким образом, даже если текущая политика неточна или дрейфует, мы можем предпринять корректирующие действия.
Алгоритм оптимизации
Метод Ньютона
Решение f (x) = 0:
Свернуть f (x):
Нелинейная задача наименьших квадратов с методом Гаусса-Ньютона
(Кредит на метод Гаусса-Ньютона)
Метод Ньютона по оптимизации:
Согласно приведенному выше уравнению направление поиска p (также известное как Δx) с использованием метода Ньютона можно записать как:
Вычислите производную первого и второго порядка от f:
В методе Гаусса-Ньютона мы аппроксимируем вторую производную, указанную выше, без члена Q. Член Q меньше первого члена, и если проблема не имеет остатка, r = Q = 0. Метод Гаусса-Ньютона применяет это приближение к методу Ньютона.
Направление поиска метода Гаусса-Ньютона:
Приведем пример, мы хотим определить скорость роста антилопы. Мы разрабатываем модель g и подгоняем данные в модель для вычисления остаточной ошибки r:
Сопряженный градиент
Мы используем метод сопряженных градиентов для оптимизации квадратного уравнения или для решения линейного уравнения.
В линейном поиске мы определяем направление подъема, а затем выбираем размер шага. Например, при подъеме по градиенту мы следуем направлению с самым крутым градиентом и делаем шаг с размером, равным градиенту, умноженному на скорость обучения. В приведенном ниже примере самое глубокое направление согласно контуру градиента - это движение вправо. Следующий ход может пойти вверх и немного влево. Даже если мы приближаемся к оптимальной точке с каждым ходом, мы можем спросить, почему каждое движение отменяет часть предыдущего хода (например, перемещение немного влево во втором ходу)
Метод сопряженных градиентов - это метод линейного поиска с тщательным выбором согласованных направлений. Он оптимизирует квадратное уравнение за меньшее количество шагов, чем градиентный подъем. Если x является N -мерным (N параметров), мы можем найти оптимальную точку не более чем за n шагов. . Для каждого следующего хода мы хотим, чтобы направление было сопряжено со всеми предыдущими ходами. Математически это означает, что любое новое направление dj должно подчиняться следующему с любым предыдущим направлением di:
где A - матрица квадратного уравнения.
Мы можем визуализировать это в нашем примере как перемещение перпендикулярно предыдущим.
Это алгоритм. Мы начинаем со случайного (или обоснованного) предположения Xo и используем приведенное ниже уравнение, чтобы вычислить, куда мы должны двигаться дальше X1. p - направление движения (эквивалент d выше)
Определим два термина:
- e - ошибка между текущим предположением и оптимальной точкой.
- r измеряет, насколько мы далеки от правильного значения b. Мы можем рассматривать это как ошибку e, преобразованную A в пространство b.
Из,
Мы можем вывести:
Скажем, наша следующая точка вычисляется как:
Чтобы будущее направление не отменяло прогресс по сравнению с предыдущим, давайте попробуем сделать d и e ортогональными:
α зависит от e, значение которого нам неизвестно. Итак, вместо ортогонального, давайте попробуем, чтобы все направление поиска d было A -ортогональным:
Для выполнения этих условий мы переместим xi в направлении d к оптимальной точке в направлении поиска d .
Используя требование A -ортогональности, α вычисляется как:
Таким образом, сопряженный градиент - это поиск A -ортогонального направления поиска каждый раз и переход к оптимальной точке в этом направлении поиска. Эти векторы не зависят друг от друга и охватывают N -мерное пространство. Таким образом, мы можем решить не более чем за n шагов.
Условия
Серия Тейлора
В векторном виде:
где g - матрица Якоби, а H - матрица Гессе.
Матрица Якоби
Матрица Гессе
Примеры:
KL-дивергенция
В глубоком обучении нам нужна модель, предсказывающая распределение данных Q, напоминающее распределение P на основе данных. Такую разницу между двумя распределениями вероятностей можно измерить с помощью расхождения KL, которое определяется как:
Положительно определенная матрица
Матрица A положительно определена, если
для всего действительного ненулевого вектора z.
Концепции
Контролируемое обучение против обучение без учителя против обучение с подкреплением
Контролируемое обучение - это обучение на основе обучающего набора данных, снабженного ярлыками из известных источников (например, человека). Например, мы хотим узнать класс объекта (метку) объекта внутри изображения (образец данных). Когда системе предлагается новый образец, она должна обобщить то, что она узнает, чтобы ответить на вопрос «каков ярлык?».
Обучение без учителя исследует скрытую структуру данных. Например, каковы скрытые особенности выборки данных или к какой категории (кластеру) принадлежат данные.
Обучение с подкреплением наблюдает за окружающей средой и предпринимает действия, чтобы максимизировать вознаграждение (цели). В основном это касается исследования, эксплуатации, поиска методом проб и ошибок, отложенного вознаграждения, системной динамики (того, как среда реагирует на предпринятые действия) и определения целей.
Агент (Контроллер)
Система (например, роботы), которая взаимодействует с окружающей средой и воздействует на нее.
Политика
Политика определяет, как обучающийся агент может действовать из определенного состояния. Математически это вероятность выполнения действия a с учетом состояния s. π = p (a | s)
Награды
Сигнал вознаграждения (r (s, a, s ’)) определяет цель в задаче обучения с подкреплением. Например, это счет в игре или поворот дверной ручки для манипулятора. Общая награда - это возврат.
Функция значения (функция значения состояния)
Ценность состояния - это общая сумма вознаграждений, которую агент может получить с этого момента до конца V (s).
Функция значения действия
Ценность выполнения действия из состояния - это общая сумма вознаграждений, которую агент может получить с этого момента до конца, выполнив определенное действие Q (s, a).
Модель окружающей среды
Модель описывает, как среда может измениться при действии из состояния p (s, a, s ’).
Эпизоды
Эпизод проигрывается через всю последовательность (например, игру) до достижения конечного состояния.
Ставка дисконтирования γ
Ставка дисконтирования оценивает будущие вознаграждения по текущей стоимости.
Модель против. модель бесплатно
В свободном от модели RL динамика системы неизвестна или не требуется.
Метод Монте-Карло
Методы Монте-Карло проигрывают завершенный эпизод. Он вычисляет среднее значение выборки из нескольких эпизодов для оценки функций ценности. В следующем примере создается скользящее среднее с использованием метода Монте-Карло.
Контроль Монте-Карло
Используйте методы Монте-Карло для оценки текущей политики. Используя функции оценочной стоимости, мы улучшаем текущую политику.
Политическое обучение против внеполитическое обучение
Мы используем политику, чтобы определить, какие действия следует предпринять. При изучении политики мы оптимизируем текущую политику и используем ее, чтобы определить, какие действия следует изучить дальше. Поскольку текущая политика не оптимизирована или субоптимизирована, она по-прежнему допускает некоторую форму исследования. Внеполитическое обучение позволяет второй политике, такой как ε-жадная политика, явно определять желаемое исследование. Обучение вне политики оптимизирует текущую политику, но использует другую политику для изучения действий. Вне политики предоставляет больший выбор, но медленнее сходится и имеет большую сложность. Внебиржевое обучение в основном использует выборку по важности при оценке политики.
Прогноз
Оценка политики
Обучение с временной разницей (TD)
Вместо прохождения всего эпизода, как в Монте-Карло:
Раскатываем k-step и собираем награды. Мы оцениваем функцию ценности на основе собранных вознаграждений и функцию ценности после k шагов. Ниже приведено одноступенчатое обучение TD. Мы находим свою награду за одно действие и узнаем функцию ценности для нового состояния.
Планирование
Мы используем динамику системы (модель) для создания имитационного опыта и используем их для корректировки функций ценности или политики.
Разница между обучением и планированием заключается в реальном опыте, созданном окружающей средой, и в моделировании опыта.
Ниже приводится алгоритм Dyna-Q, который использует изученную модель для корректировки значений функции Q.
Оптимизация траектории
Способы съемки
Оптимизируйте траекторию на основе разомкнутой системы. Наблюдайте за исходным (первым) состоянием и оптимизируйте соответствующие действия.
Для стохастической системы это неоптимально, потому что мы не корректируем действия на основе наблюдаемых состояний, в которые мы переходим.
Методы размещения
Оптимизируйте траекторию на основе замкнутой системы, действия которой мы предпринимаем на основе наблюдаемых состояний.
