Путь к обучению с подкреплением

В предыдущих двух статьях: (1) Марковские состояния, марковская цепь и марковский процесс принятия решений и (2) Решение марковского процесса принятия решений я заложил основу для разработки подробной концепции обучения с подкреплением (RL). Проблема RL сформулирована как Марковский процесс принятия решений (MDP), который может быть решен для оптимальных политик (т. Е. Какие действия необходимо предпринять агенту для достижения цели). Решение может быть получено либо путем перебора всего пространства состояний, либо с помощью какого-либо другого метода, признающего, что решение может быть получено рекурсивно путем решения более мелких задач. Последнее является темой динамического программирования.

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

Динамическое программирование — это способ решения сложных проблем путем их разделения на более мелкие и простые подзадачи. Это подход «снизу вверх», при котором сначала решаются меньшие подзадачи, а затем работают вверх, чтобы объединить решения для решения более крупных подзадач.

Чтобы использовать динамическое программирование, задача должна иметь две особенности:

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

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

Мы можем понять это в контексте продольного контроля автоматизированного вождения, целью которого является минимизация расхода топлива. Учтите, что состояние транспортного средства состоит из (v, a), т. е.скорости и ускорения. Мы можем определить набор возможных действий как ускорение, замедление или поддержание постоянной скорости. f(v, a) может быть расходом топлива в зависимости от скорости и ускорения. Это очень разумная функция для расхода топлива (см. [4]).

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

Мы можем определить функцию стоимости C(t, s), которая представляет минимальный расход топлива для достижения состояния s в момент времени t, и используя следующая рекурсия:

где s’ — предшествующий элемент s.

Мы можем получить оптимальную последовательность действий, отслеживая действия, которые были предприняты на каждом временном шаге для достижения минимальной стоимости в это время. Например, в момент времени t транспортное средство находится в состоянии s = (v, a) и минимальная стоимость достижения этого состояния составляет C(t, ( в, а)). Если минимальная стоимость была достигнута за счет выполнения действия «ускорить» в момент времени t-1, то оптимальная последовательность действий включает «ускорение» в момент времени t-1.

Питон-псевдокод приведенного выше примера можно найти по адресу https://gist.github.com/rahulbhadani/a119916d26e251b939b817dde03ad032.

Приблизительное динамическое программирование

Приближенное динамическое программирование (ADP) используется для решения задач, которые иногда бывают большими и сложными и обычно (но не всегда) являются стохастическими.

ADP используется для преодоления проклятия размерности, которое обычно наблюдается в уравнении Беллмана.

ADP — это изучение того, что изучать и как это изучать, чтобы со временем принимать лучшие решения» [5].

В ADP функция истинного значения Vπ(s) заменяется ее статистической аппроксимацией Vπ*(s). Кроме того, ADP шагает вперед во времени с некоторыми вариациями. Приближенную функцию Vπ*(s) можно определить несколькими способами, например:

  1. Поиск таблиц
  2. Параметрические модели
  3. Непараметрические модели

В качестве альтернативы для аппроксимации ожиданий можно использовать метод Монте-Карло.

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

Читатели должны отметить, что с ADP политика может быть неоптимальной, и нам нужно идти на компромисс с неоптимальными политиками.

Заключение

В этой статье я рассмотрел специфику динамического программирования на примере продольного управления при автономном вождении. Динамическое программирование — это эффективный способ решения MDP, который лежит в основе проблем RL. В следующей статье этой серии я расскажу об итерации ценности и итерации политики. Предстоящая будущая статья будет посвящена стратегиям, которые используются для аппроксимации функций ценности.

Если вы еще не ознакомились с первыми двумя статьями из серии «Основы RL», обязательно ознакомьтесь с ними:

  1. https://towardsdatascience.com/foundational-rl-markov-states-markov-chain-and-markov-decision-process-be8ccc341005.
  2. https://towardsdatascience.com/foundation-rl-solving-markov-decision-process-d90b7e134c0b




Вам понравилась эта статья? Купи мне кофе.

Нравится мое письмо? Присоединяйтесь к моему списку рассылки.

Хотите узнать больше о темах, связанных с STEM? Присоединяйтесь к Среде

Рекомендации

  1. Глубокое обучение с подкреплением, Мохит Севак, https://doi.org/10.1007/978-981-13-8285-7
  2. Глубокое обучение с подкреплением, Aske Plaat, https://doi.org/10.1007/978-981-19-0638-1, Springer Singapore
  3. Обучение с подкреплением и стохастическая оптимизация: унифицированная структура для последовательных решений Уоррена Б. Пауэлла (ред.), Wiley (2022). Твердый переплет. ISBN 9781119815051.
  4. Ли, Дж.В., Гюнтер, Г., Рамадан, Р., Альматруди, С., Арнольд, П., Акино, Дж., Барбур, В., Бхадани, Р., Карпио, Дж., Чоу, Ф.К. и Гибсон, М., 2021, май. Интегрированная структура динамики транспортных средств, нестабильностей, моделей энергии и контроллеров сглаживания разреженного потока. В Материалы семинара по управляемым данными и интеллектуальным киберфизическим системам (стр. 41–47). https://doi.org/10.1145/3459609.3460530
  5. Пауэлл, Уоррен Б. Что вам следует знать о приближенном динамическом программировании. Логистика военно-морских исследований (NRL) 56, вып. 3 (2009): 239–249. https://doi.org/10.1002/nav.20347
  6. Бушониу, Лучан, Барт Де Шуттер и Роберт Бабушка. Приблизительное динамическое программирование и обучение с подкреплением. В Интерактивные информационные системы для совместной работы, стр. 3–44. Springer, Berlin, Heidelberg, 2010. https://www.dcsc.tudelft.nl/~bdeschutter/pub/rep/10_028.pdf