Четыре политических класса обучения с подкреплением

Четыре политических класса обучения с подкреплением

Исчерпывающая классификация стратегий решения для обучения с подкреплением

Политика обучения с подкреплением (RL) окутана определенной мистикой. Проще говоря, политика π: s → a - это любая функция, которая возвращает возможное действие для проблемы. Ни меньше, ни больше. Например, вы можете просто выполнить первое действие, которое придет в голову, выбрать действие наугад или запустить эвристику. Однако то, что делает RL особенным, заключается в том, что мы активно предвидим последующие последствия решений и извлекаем уроки из наших наблюдений; поэтому мы ожидаем некоторой разумности в нашей политике. В своей концепции последовательного принятия решений [1] Уоррен Пауэлл утверждает, что существует четыре класса политик для RL. Методы всех четырех классов широко используются в разных областях, но еще не получили всеобщего признания. Эта статья представляет собой краткое - и, несомненно, неполное - введение в эту классификацию стратегий решения.

Решение моделей MDP

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

Но на самом деле нам не нужно уравнение Беллмана. В конечном итоге мы просто пытаемся максимизировать совокупное вознаграждение; оптимальная политика делает именно это. Это также избавляет от необходимости рассматривать функции значений V ^ π * (s ’), что мы делаем только в одном из четырех классов политик. Таким образом, мы можем сформулировать нашу цель следующим образом:

Для достижения оптимальности модели MDP существует два основных подхода: (i) итерация политики и (ii) итерация значения. Итерация политики исправляет политику, вычисляет соответствующее значение политики и впоследствии обновляет политику с использованием нового значения. Алгоритм повторяется между этими шагами, пока политика не останется стабильной. Итерация значений на самом деле основывается на очень похожих шагах (см. рисунок ниже), но направлена ​​на прямое максимизирование функций значений и только потом обновляет политику. Обратите внимание, что поиск функций оптимального значения равносилен поиску оптимальной политики; либо достаточно для решения системы уравнений Беллмана.

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

s: состояние (информация, необходимая для принятия решения)

a: действие (выполнимая операция в состоянии)

π: политика (сопоставляет состояние с действием)

ϕ: базовая функция (выводит характеристики из состояния)

θ: веса характеристик (параметризация политики)

t: эпоха времени (дискретный момент времени)

R: функция вознаграждения (прямое вознаграждение за выполнение действия в состоянии)

V: функция значения (последующее вознаграждение за определенное состояние)

Приближение политики

В решениях приближения политики мы непосредственно изменяем саму политику. Такие стратегии решения, как правило, работают лучше всего, когда политика имеет четкую структуру. Мы можем выделить два класса: PFA и CFA.

Аппроксимация функции политики (PFA)

Аппроксимация функции политики (PFA) по существу является параметризованной функцией политики. Подключение состояния напрямую возвращает выполнимое действие. Линейная PFA может выглядеть так:

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

Аппроксимация функции затрат (CFA)

Как и PFA, аппроксимация функции затрат (CFA) также выполняет прямой поиск в области политики. Однако CFA не возвращает действие напрямую, а скорее решает проблему оптимизации в ограниченном пространстве действий. Примерный состав будет:

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

Приближение значения

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

Аппроксимация функции цены (VFA)

Аппроксимация функции ценности (VFA) представляет последующие значения как функцию. Одна из проблем с уравнением Беллмана заключается в том, что после выполнения действия случайные события могут привести нас ко многим новым состояниям s’∈ S ’. Таким образом, для каждого действия мы должны учитывать значение всех достижимых состояний s ’ и вероятность их достижения. VFA обходят эту проблему, заменяя член стохастического математического ожидания детерминированной функцией аппроксимации V_t (s_t, a_t). В каноническом виде VFA выглядит так:

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

Прямое опережающее приближение (DLA)

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

По общему признанию, это уравнение выглядит довольно громоздким, но на самом деле может быть самым простым из всех. Условия ожидания подразумевают, что мы делаем выборку в будущем и применяем некоторую (неоптимальную) политику для оценки последующих значений. Принимая во внимание, что мы максимизируем все возможные действия в текущее время t, для будущих времен t ' мы обычно используем более легкую в вычислительном отношении политику (например, эвристику) и / или упрощенное представление проблемы (например, при условии совершенного предвидения). Стратегия DLA сопряжена со своими проблемами (выборка сценария, методы агрегации и т. Д.), Но в отличие от трех других политик она не требует оценки функции (так что нет, замена «функции» на «прогноз» - это не просто семантика). По сути, он часто служит последним средством решения сложных проблем, в которых три другие стратегии терпят неудачу.

Гибридные классы

Было бы упущением не упомянуть возможности комбинирования стратегий из нескольких классов. Например, классическая структура «актер-критик» содержит элементы как PFA (актер), так и VFA (критик). Однако существует гораздо больше комбинаций, таких как встраивание VFA в качестве нисходящей политики в алгоритм прямого просмотра. Комбинированные стратегии могут нивелировать слабые стороны друг друга, часто давая лучшие результаты по сравнению с решениями одного класса.

Выводы

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

• Не существует универсального решения. Хотя существуют некоторые практические правила, несколько стратегий могут дать хорошие решения. Наглядный пример этого утверждения можно найти в Powell & Meisel [3], где демонстрируются реализации всех четырех стратегий решения одной и той же проблемы.
• Ученые любят элегантность. PFA и VFA, по-видимому, наиболее популярны в академических кругах. В конце концов, есть определенная математическая красота в том, чтобы зафиксировать сложную политику принятия решений в одной функции.
• Промышленность любит результаты. Когда проблемы становятся слишком большими или сложными, CFA и DLA могут дать удивительно хорошие результаты. Несмотря на то, что он в некоторой степени полагается на грубую силу и перечисление, затраты на проектирование значительно меньше.
• У всего есть своя цена. Всегда приходится идти на компромисс между удобством, трудоемкостью проектирования, вычислительной сложностью, интерпретируемостью и т. д. Характер проблемы определяет, насколько важны эти компромиссы.
• Классификация - ключ к успеху. Есть много сообществ RL, много техник, много стилей обозначений, много алгоритмов. Чтобы упростить сферу деятельности и способствовать развитию, необходима четкая всеобъемлющая структура.

использованная литература

[1] Пауэлл, Уоррен Б. «Единая структура для стохастической оптимизации». Европейский журнал операционных исследований 275.3 (2019): 795–821.

[2] Саттон, Ричард С. и Эндрю Дж. Барто. Обучение с подкреплением: введение. MIT press, 2018.

[3] Пауэлл, Уоррен Б. и Стефан Мейзел. «Учебное пособие по стохастической оптимизации в энергетике - Часть II: Иллюстрация накопителя энергии». IEEE Transactions on Power Systems 31.2 (2015): 1468–1475.