Цель задачи оптимизации - найти лучшее решение из всех возможных решений путем нахождения оптимума целевой функции.

Методы оптимизации:

Наиболее распространенные целевые функции для разных типов обучения:

я. потеря журнала для классификации,

II. среднеквадратичная ошибка для регрессии, и

iii. функция вознаграждения / ценности для обучения с подкреплением (RL) *.

* RL - это целенаправленный метод обучения, и цель формализуется вознаграждением. Отличие от других методов машинного обучения состоит в том, что в RL мы учимся, взаимодействуя с окружающей средой, и у нас нет супервизора (оракула, раскрывающего истину). Вместо этого у нас есть награда, которая всегда представляет собой одно число.

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

Потеря классификации и ошибка регрессии являются относительно хорошими показателями для оценки значений параметров функции.

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

Проблема с методами RL заключается в том, что сигналы вознаграждения имеют тенденцию быть слабыми; в некоторых средах агенты застревают в поисках закономерностей в случайных данных ». Джеффри Хинтон .

Если вам нужно краткое введение в обучение, ознакомьтесь с разделом Обучение = Представление + Оценка + Оптимизация.

(Точное) динамическое программирование

DP: набор алгоритмов для вычисления оптимальных политик с учетом идеального знания среды. Окружающая среда обычно моделируется как конечный марковский процесс принятия решений (MDP).

📆 Динамический = происходит последовательно (т. е. последовательно), изменяется во времени (во времени)

⏳Programming = математическое программирование, задача оптимизации

🤔 Неопределенность = результаты частично случайны и частично находятся под контролем (т. Е. Выбора) лица, принимающего решение (т. Е. Агента).

Принцип оптимальности Беллмана:

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

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

То есть, чтобы решить проблему от некоторого начального периода t до некоторого конечного периода T, нужно неявно решать подзадачи, начиная с более поздних дат s , где t ‹s‹ T. Это пример оптимальной подструктуры, который показывает, как значение проблемы, начиная с t, связано со значением проблемы, начиная с s. Принцип оптимальности Беллмана можно рассматривать как составную часть MDP, решаемого DP.

Среда MDP

MDP: стандартная структура для моделирования последовательного принятия решений или планирования в условиях неопределенности.

🧩 Компоненты MDP:

  • состояние (X или обозначается как S), - основание для действия -
  • вероятности перехода между состояниями (P), - изменить состояние после действия -
  • действие (A), - выбор, сделанный агентом-
  • награда (R), -Оцените состояние или действие, которое вы предприняли-
  • и коэффициент дисконтирования (γ). - влияние времени, переходящего к вознаграждениям -

Конечное пространство MDP = A, S конечно, а его динамика задается набором вероятностей P (s ’, r | s, a). (Приближенный DP для непрерывных пространств).

Ключевая идея DP & RL - использование функций ценности для организации поиска хороших политик (моделей поведения).

Решения MDP (уравнение Беллмана): динамическое программирование, обучение с подкреплением.

Функция значения = «насколько хорошо *» находиться в состоянии v (s) или выполнять действие из этого состояния q (s, a). Прогноз будущей награды, взятый из этой среды [* определяется будущими наградами].

Политика π (a | s) = агент выбирает действия как функции состояний; сопоставить состояния с действиями. Он оптимизирует функцию ценности, максимизируя вознаграждение.

Вознаграждение: ожидаемая долгосрочная отдача от политики для каждого возможного состояния.

Фундаментальное различие между DP и RL i в том, что первый предполагает полное знание среды (доступны все компоненты MDP), которая редко реагирует на реальные ситуации. . RL, с другой стороны, изучает модель среды (то есть MDP, где обычно P или R неизвестны). Исходя из этого различия, мы иногда называем их проблемами планирования и обучения соответственно. Планирование в MDP означает поиск оптимальной политики для данной известной среды.

Вопросы, связанные с RL & DP:

1. временная сложность O (N): количество итераций, необходимых для поиска оптимальных решений,

2. сложность пространства (память): размерность пространства функций (например, состояние),

3. эксплуатация (известного лучшего решения) против разведки (неизвестных решений) компромисс в определенном временном горизонте .

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

DP используется для задач, где между переменными существует линейная без изменения порядка (строки в предложении, матрицы в цепочке, слева направо порядок листьев в дереве поиска), например:

  • Планирование в MDP (решение: DP, перебор)
  • Строковые алгоритмы (например, выравнивание последовательностей)
  • Алгоритмы графов (например, алгоритмы кратчайшего пути)
  • Графические модели (например, алгоритм Витерби)
  • Алгоритмы планирования

Методы планирования

Этапы. Задача планирования состоит из двух этапов: оценка политики и ее улучшение.

Оценка политики находит оптимальное значение (argmax) для всех состояний в пространстве состояний.

  1. ⛅️ Планирование - это в первую очередь проблема прогнозирования:

→ Ввод: процесс вознаграждения Маркова ( MDP и политика)

← Выход: функция значения v.

⚙️ Процесс: оценка политики

Мы вычислили функцию ценности для детерминированной (фиксированной) политики, потому что нам нужно найти лучшие политики (действия для каждого состояния). Этот процесс известен как улучшение политики: если мы предпримем другое действие в данном состоянии, приведет ли к новой и лучшей политике?

2. ✨ Тогда это проблема улучшения:

→ Ввод: MDP, функция значения

← Результат: лучшая политика

⚙️ Процесс: улучшение политики

🎮 1. + 2. = Контроль.

Наконец, задачи оценки и улучшения объединены в задачу Контроль. Теперь нам нужно решить, какой метод планирования использовать для расчета оптимальной политики. Два классических метода DP для точного планирования в MDP - это итерация политики и итерация значения.

1. Итерация политики (PI)

Оценивайте политики, создавая их функции ценности (ΝΟΤ оптимальные VF), и используйте эти VF для поиска новых, улучшенных политик.

Он состоит из трех этапов:

  1. Инициализация политики и VF (произвольно)
  2. Оценка политики (прогноз): вычисление VF состояния для некоторых или всех состояний с учетом фиксированной политики.
  3. Улучшение политики: Действуйте жадно (т. е. выбирайте наилучшее действие в каждом состоянии) в соответствии с политикой с учетом оптимальной функции состояния и значения. Тогда мы гарантированно улучшим политику.

Повторяйте шаги 2, 3, пока не будет выполнено одно из следующих условий:

(i) политика остается неизменной, если она уже оптимальна,

(ii) истек срок, или

(iii) изменение функции цены ниже определенного порога Δ (обозначенного как η на следующем рисунке).

2. Итерация значений (VI)

Найдите функцию оптимального значения, которая используется для вычисления (только один раз) оптимальной политики.

Он состоит из двух этапов:

  1. Инициализация VF (произвольно)
  2. Найдите оптимальную VF с помощью одного шага оценки политики + немедленно сделайте одно улучшение политики.

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

Теперь, когда у нас есть представление о методах планирования, мы можем закодировать их на Python.

Кодирование (Python)

Прежде всего, нам нужен доступ к идеальной среде MDP. Мы будем использовать стандартную среду, используемую в Обучение с подкреплением: Введение, Глава 4. Вы можете найти код здесь.

Оценка политики

Итерация политики

Итерация значений

Резервные копии: количество и глубина обновлений политики

Резервное копирование = обновление политики

Улучшение политики в изменении значений и изменение политики осуществляется с помощью «полной резервной копии», которая представляет собой не что иное, как уравнения Беллмана, преобразованные в обновления политики. В каждом состоянии мы можем заглянуть на один шаг вперед для каждого возможного действия и следующего состояния. Мы можем это сделать только потому, что у нас есть идеальная модель окружающей среды. Альтернативой является использование образцов резервных копий.

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

Неглубокие резервные копии / на 1 шаг вперед: обновленные оценки основаны на предыдущих оценках.

Глубокое резервное копирование: выполнение всех шагов до конечных состояний.

DP и исчерпывающий поиск - два метода планирования. Они используют полные резервные копии для обновления измерения ширины политики. Эти методы принимают ожидаемые значения обновлений по всем состояниям (на основе распределения возможных траекторий). Ожидаемые обновления требуют модели распространения.

Одноэтапное обучение TD и чистый метод Монте-Карло используют образцы резервных копий (примерные траектории sar) из реальных или смоделированное взаимодействие с окружающей средой. Это методы обучения, поскольку они не имеют доступа к полной MDP для вычисления функций значений.

Как мы выбираем траектории? Мы выполняем резервное копирование по Беллману только в тех состояниях, которые посещаются в соответствии с правильными политиками.

Таким образом, мы можем решить проблему масштабирования перебора всех возможных состояний. Для образцов обновлений требуется только образец модели (не все возможные переходы, требуемые DP), либо можно быть сделано на основе фактического опыта вообще без модели (это можно рассматривать как еще одно измерение вариации).

Что такое начальная загрузка? Краткий ответ: изучите прогноз на основе полученного позже прогноза (с использованием оценок для обновления оценок). Степень начальной загрузки - это еще один аспект вариативности резервного копирования.

Приближенное (нейро) динамическое программирование и обучение с глубоким подкреплением

На практике применимость DP и RL ограничена огромным размером базовых пространств состояний. Это известно как «проклятие размерности» Беллмана или «расширяющаяся сетка».

Проклятие размерности: экспоненциальный рост состояний с расширением временного горизонта (количества шагов, которые делает агент).

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

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

Ключевая идея: изучить (приблизить) состояние, действие или динамику перехода как линейную (или нет) комбинацию входных функций.

В приближении функции значения для настройки параметров используется моделирование. То есть вычислить приближенное решение уравнения Беллмана и затем построить политику, близкую к оптимальной.

Альтернативой является использование оптимизации политики, также называемой оптимизацией в области политики. Это настройка параметров политики в сторону улучшения. Подход к оптимизации политики включает i. Мета-эвристика, например, эволюционные алгоритмы; и ii. Градиенты политики.

Методы градиента политики основаны на оптимизации параметризованных политик w.r.t. награда градиентным спуском. Параметры - это политики, индексированные вектором параметров чисел, аналогично классификации или регрессии с вводом состояний и выводом действий. Вы можете использовать те же функции приближения, что и в: i. сеть классификации (d iscrete пространство действий) выводит вектор вероятностей, и ii. сеть регрессии (c непрерывное пространство действий) выводит среднюю и диагональную ковариацию гауссовского

Let J(θ) be a policy optimization function and α the learning rate
Search for the local maximum of J(θ) by ascending the gradient of θ.

Ресурсы для дальнейшего чтения:

  1. Обучение с подкреплением - Введение
  2. Учебное пособие по аппроксиматорам линейных функций для динамического программирования и обучения с подкреплением
  3. Методы градиента политики: учебное пособие и новые рубежи
  4. Модельное обучение с подкреплением
  5. Курс RL Дэвида Сильвера

Все ошибки мои собственные. ☞ Или бот. Помогите исправить это или используйте лучшие практики🙄

Hap-py-кодирование ⇧⏎

И как всегда спасибо за чтение😎