Есть ли какие-то простые ограничения на скорость изучения задачи? Исследование в контексте Q-обучения.
Алгоритмы глубокого обучения с подкреплением могут быть самыми сложными алгоритмами в последних разработках машинного обучения для установления числовых ограничений на их производительность (среди тех, которые работают). Аргументация двоякая:
- Глубокие нейронные сети - это туманные черные ящики, и никто по-настоящему не понимает, как и почему они так хорошо сходятся.
- Задача обучения с подкреплением конвергенция исторически нестабильна из-за скудного вознаграждения, наблюдаемого из окружающей среды (и сложности основной задачи - учиться с нуля! ).
Здесь я проведу вас по эвристике, которую мы можем использовать, чтобы описать, как алгоритмы RL могут сходиться, и объясню, как обобщить ее на большее количество сценариев.
Некоторые статьи по теме, которые можно прочитать до или после этого:
- Что такое марковский процесс принятия решений?
- Скрытая линейная алгебра обучения с подкреплением.
- Основы итерационных методов обучения с подкреплением.
В этой статье рассматривается вопрос как сходятся во время обучения итерационные методы, такие как итерация значений, q-обучение и расширенные методы? Здесь мы кратко рассмотрим процессы принятия решений Маркова (см. ссылки 1 и 3 выше для более подробной информации), объясним, как мы можем рассматривать обновления Беллмана как уравнение собственного вектора (подробнее в ссылке 2) и покажите математические вычисления для того, как значения сходятся к оптимальным величинам.
Обзор марковских процессов принятия решений
Марковские процессы принятия решений (MDP) - это стохастическая модель, лежащая в основе обучения с подкреплением (RL). Если вы знакомы, можете пропустить этот раздел.
Определения
- Набор состояний s ∈ S, действий a ∈ A.
- Функция перехода T (s, a, s ’).
- Функция вознаграждения R (s, a, s ’). Любая выборка этой функции r находится в интервале [-Rmax, + Rmax].
- Коэффициент дисконтирования γ (гамма) в интервале [0,1].
- Начальное состояние s0 и, возможно, конечное состояние.
Важные ценности
Есть две важные характерные утилиты MDP - значения состояния и q-значения случайного узла. * в любом значении MDP или RL обозначает оптимальное количество. Утилиты: 1) v значение состояния и 2) Q-значение пары состояние, действие.
Что мы пытаемся сделать, так это оценить эти значения, q-значения и полезности, чтобы наши агенты могли планировать действия, которые максимизируют вознаграждение.
Истинные оценки = оптимальная политика.
Обобщение итеративных обновлений
В первом разделе нового содержания я напомню концепции RL, которые я использую, и выделю математические преобразования, необходимые для получения системы уравнений, которая развивается дискретными шагами и имеет предел сходимости.
Обучение с подкреплением
RL - это парадигма, в которой мы пытаемся «решить» и MDP, но мы не знаем лежащую в основе среду. Простые решения RL представляют собой основанные на выборке варианты фундаментальных алгоритмов решения MDP (Value and Policy Iteration). Вспомните итерацию Q-value, которая представляет собой обновление Беллмана, на котором я остановлюсь:
Рассмотрение того, насколько точна итерация значения или итерация политики сводится к сравнению вектора значений после каждого присвоения (←) в приведенном выше уравнении, которое является одним раундом рекурсивного обновления. Конвергенция этих методов дает меру, пропорциональную тому, как будут сходиться алгоритмы обучения с подкреплением, поскольку алгоритмы обучения с подкреплением представляют собой основанные на выборке версии итераций значений и политик с несколькими другими движущимися частями.
Напомним: Q-обучение - это то же правило обновления, что и итерация Q-значения, но функция перехода заменяется действием выборки, а функция вознаграждения заменяется фактической выборкой, r, получено из окружающей среды.
Линейный оператор и собственные векторы
Нам нужно сформулировать наши обновления Беллмана как линейный оператор B (матрица - это подмножество линейных операторов) и посмотреть, сможем ли мы заставить его вести себя как стохастическая матрица . Стохастическая матрица гарантированно имеет собственный вектор, сопряженный с собственным значением 1.
Это говорит о том, что мы можем изучать итеративные обновления в RL, как если бы мы изучали эволюцию собственного подпространства.
На данный момент нам нужно внести несколько изменений в обозначение для перехода от формул для Q-значений в матрице к формулам, которые действуют на Утилиты в векторе (Утилиты обобщают к ценностям и Q-значениям, в любом случае, потому что это определяется как дисконтированная сумма вознаграждений).
- Мы знаем, что полезности пропорциональны q-значениям; изменить обозначение. Мы будем использовать U.
- Преобразование служебных программ в вектор похоже на функцию
flatten()многих библиотек кодирования (например, смещение пространства состояний XY на 1d векторную индексацию по состояниям). Получаем u.
Эти изменения имеют решающее значение для постановки задачи в виде собственных векторов.
Понимание частей Q-обучения
Начните с основного уравнения для итерации значения Q ниже, как мы можем обобщить его на линейную систему?
В этом случае нам нужно изменить правую часть, чтобы она имела следующий вид:
Это оставляет нам окончательную форму (объединение уравнений из этого раздела и конец раздела собственных значений). Можем ли мы использовать это как линейный оператор, который нам нужен? Подумайте, если мы используем оптимальную политику (без потери общности), тогда выпадает хитрый максимум над действиями, оставляя нас с:
Изучение конвергенции
В этом разделе я выведу соотношение, которое гарантирует минимальную ошибку эпсилон после N шагов, и покажу, что это означает.
Система, которую мы можем изучить
Выше мы видели, что можем сформулировать правило обновления полезности способом, очень близким к собственному вектору, но мы отклонились от постоянного вектора r, представляющего лежащую в основе поверхность вознаграждения. МДП. Что произойдет, если мы возьмем разницу между двумя векторами полезности? Выпадает постоянный член.
Теперь у нас есть наша система, которую мы можем изучать как динамическую систему собственных векторов, но мы работаем в пространстве разницы между полезностями с матрицей B - сумма взвешенных вероятностей перехода. Поскольку векторы полезности определяются друг другом, мы можем волшебным образом изменить это (подставить рекурсивное уравнение Беллмана, взять норму).
Изучение разницы между любой оценкой полезности - гениальное дело, потому что оно показывает а) как оценка отличается от истинной или б) как развиваются данные только из рекурсивного обновления (а не маленького вектора r ).
Связь эпсилон-N
Любое доказательство сходимости будет искать взаимосвязь между границей ошибки, ε, и количеством шагов, N , (итерации). Это соотношение даст нам возможность связать производительность с помощью аналитического уравнения.
Другими словами, мы ищем границу эпсилона, которая является функцией N.
Для начала мы знаем (по определению MDP), что вознаграждение на каждом этапе r, равно ограничено в интервале [-Rmax, + Rmax]. Затем, глядя на определение полезности (дисконтированной суммы вознаграждения) как геометрического ряда, мы можем связать разницу от любого вектора с истинным вектором. (Доказательство сходимости геометрических рядов).
Граница исходит из оценки наихудшего случая - где истинное вознаграждение на каждом шаге равно + Rmax, но мы инициализируем нашу оценку на -Rmax. Увы, у нас есть начальная граница ошибки наших утилит! Напомним, что U0 - это то, чем мы инициализируем вектор утилит, а затем индекс будет увеличиваться каждый раз, когда мы запускаем обновление Беллмана.
К обновлениям Bellman - как эта привязка при инициализации изменяется с каждым шагом? Выше мы видим, что ошибка уменьшается на коэффициент дисконтирования на каждом шаге (из того, как к сумме в рекурсивном обновлении всегда добавляется гамма). Ниже это превращается в серию уменьшающихся ошибок с каждой итерацией.
Все, что осталось, - это объявить границу, epsilon, по отношению к количеству шагов, N.
Результат - визуализация конвергенции
В правой части приведенного выше уравнения у нас есть оценка точности нашей оценки полезности.
Логично - для любого эпсилона мы знаем, что ошибка будет меньше эпсилон за N шагов.
Мы также можем переключаться между эпсилон и N с помощью математического трюка - поэтому, если мы знаем, насколько точными мы хотим быть оценки, мы можем решить, как долго должен работать наш алгоритм!
Найденная граница - это граница ошибки кумулятивного значения в пространстве состояний (сплошная линия ниже). Проницательный читатель задается вопросом: Как соотносятся ошибки политики? Концептуально это означает: «во скольких состояниях текущая политика будет отличаться от оптимальной?» Обороты. вне, с некоторой нормализацией значений (так что они численно похожи по величине) ошибка политики сходится быстрее и быстрее достигает нуля (без асимптоты!).
В некоторых ситуациях это дает преимущество использования итерации политик перед итерацией значений. Относится ли это к большему количеству алгоритмов?
Влияние - ограничение недавних алгоритмов глубокого RL
Все хотят ограничить алгоритмы глубокого RL. В последние годы мы наблюдаем впечатляющие результаты, когда роботы могут бегать, складывать полотенца и играть в игры. Было бы замечательно, если бы у нас был предел производительности.
То, что мы можем сделать, зависит от того, как наше представление о мире будет сходиться. Мы показали, что функция полезности будет сходиться. Есть две непреходящие проблемы:
- нам не дается функция вознаграждения за реальные задачи, мы должны ее разработать.
- выполнение этих итерационных алгоритмов в настоящее время небезопасно e. Роботизированные исследования включают в себя много сил, взаимодействия и (реально) повреждений.
Мы можем изучать сходимость алгоритмов, но большинство инженерных проблем, ограничивающих принятие глубокого RL для реальных задач, - это разработка вознаграждения и безопасное обучение.
Вот где я оставляю вас - призыв к действию, чтобы помочь нам разрабатывать более совершенные системы, чтобы мы могли больше продемонстрировать лежащую в основе математику, управляющую этим.
Вот мое резюме того, что люди нанимают в Deep RL Research.
Более? Подпишитесь на мою рассылку о робототехнике, искусственном интеллекте и обществе!
