Обучение с подкреплением - Reinforcement learning

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

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

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

Вступление

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

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

Базовое усиление моделируется как марковский процесс принятия решений (MDP) :

  • набор состояний среды и агента, S ;
  • набор действий агента A ;
  • - вероятность перехода (во время ) из состояния в состояние под действием .
  • это немедленная награда после перехода от действия к действию .

Цель обучения с подкреплением состоит в том, чтобы агент усвоил оптимальную или почти оптимальную политику, которая максимизирует «функцию вознаграждения» или другой предоставляемый пользователем сигнал подкрепления, который накапливается из немедленных вознаграждений. Это похоже на процессы, которые происходят в психологии животных. Например, биологический мозг запрограммирован так, чтобы интерпретировать такие сигналы, как боль и голод, как отрицательное подкрепление, а удовольствие и прием пищи - как положительное подкрепление. В некоторых обстоятельствах животные могут научиться вести себя, оптимизируя эти награды. Это говорит о том, что животные способны к обучению с подкреплением.

Базовый агент обучения с подкреплением ИИ взаимодействует со своей средой дискретными временными шагами. В каждый момент времени t агент получает текущее состояние и вознаграждение . Затем он выбирает действие из набора доступных действий, которое впоследствии отправляется в среду. Среда переходит в новое состояние, и определяется вознаграждение, связанное с переходом . Цель учебного армирования агента является изучение политики : , которая максимизирует ожидаемое кумулятивное вознаграждение.

Формулировка проблемы в виде MDP предполагает, что агент непосредственно наблюдает за текущим состоянием окружающей среды; в этом случае говорят, что проблема полностью наблюдаема . Если агент имеет доступ только к подмножеству состояний или наблюдаемые состояния искажены шумом, говорят, что агент имеет частичную наблюдаемость , и формально проблема должна быть сформулирована как частично наблюдаемый марковский процесс принятия решений . В обоих случаях набор действий, доступных агенту, может быть ограничен. Например, состояние баланса счета может быть ограничено положительным; если текущее значение состояния равно 3, а переход состояния пытается уменьшить значение на 4, переход не будет разрешен.

Когда производительность агента сравнивается с эффективностью агента, который действует оптимально, разница в производительности порождает понятие сожаления . Чтобы действовать почти оптимально, агент должен рассуждать о долгосрочных последствиях своих действий (т. Е. Максимизировать будущий доход), хотя немедленное вознаграждение, связанное с этим, может быть отрицательным.

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

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

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

Исследование

Компромисс между разведкой и эксплуатацией был наиболее тщательно изучен с помощью проблемы многорукого бандита и для MDP в пространстве состояний в Burnetas and Katehakis (1997).

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

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

Алгоритмы управления обучением

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

Критерий оптимальности

Политика

Выбор действия агента моделируется в виде карты, называемой политикой :

Карта политик дает вероятность принятия мер в состоянии . Есть также детерминированные политики.

Функция состояния-значения

Функция значения определяется как ожидаемый возврат, начиная с состояния , т. Е. И последовательно следуя политике . Следовательно, грубо говоря, функция ценности оценивает, «насколько хорошо» находиться в данном состоянии.

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

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

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

Грубая сила

Перебор подход предусматривает два этапа:

  • Для каждой возможной политики образец возвращается, следуя ему
  • Выберите полис с наибольшей ожидаемой доходностью

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

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

Функция значения

Подходы с функцией ценности пытаются найти политику, которая максимизирует отдачу, поддерживая набор оценок ожидаемой отдачи для некоторой политики (обычно либо «текущей» [в соответствии с политикой], либо оптимальной [вне политики]).

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

Чтобы определить оптимальность формальным образом, определите ценность политики следующим образом:

где означает отдачу, связанную со следующим из начального состояния . Определяя как максимально возможное значение , где разрешено изменение,

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

Хотя значений состояния достаточно для определения оптимальности, полезно определить значения действия. Принимая во внимание состояние , действие и политику , действие-значение пары Under определяется

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

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

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

Методы Монте-Карло

Методы Монте-Карло можно использовать в алгоритме, имитирующем итерацию политики. Политика итерация состоит из двух этапов: оценки политики и усовершенствование политики .

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

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

Проблемы с этой процедурой включают:

  • Процедура может потратить слишком много времени на оценку неоптимальной политики.
  • Он использует выборки неэффективно, так как длинная траектория улучшает оценку только одной пары состояние-действие, которая начала траекторию.
  • Когда доходность по траекториям имеет большой разброс , сходимость происходит медленно.
  • Работает только в эпизодических задачах ;
  • Он работает только в небольших конечных MDP.

Методы временной разницы

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

Вторую проблему можно исправить, позволив траекториям вносить вклад в любую пару состояние-действие в них. Это также может в некоторой степени помочь с третьей проблемой, хотя лучшее решение, когда доходность имеет высокую дисперсию, - это методы временной разницы (TD) Саттона, основанные на рекурсивном уравнении Беллмана . Вычисление в методах TD может быть инкрементным (когда после каждого перехода память изменяется и переход отбрасывается) или пакетным (когда переходы группируются и оценки вычисляются один раз на основе пакета). Пакетные методы, такие как метод наименьших квадратов временной разности, могут лучше использовать информацию в выборках, в то время как инкрементные методы являются единственным выбором, когда пакетные методы невозможны из-за их высокой вычислительной сложности или сложности с памятью. Некоторые методы пытаются объединить два подхода. Методы, основанные на временных различиях, также решают четвертую проблему.

Для решения пятой проблемы используются методы аппроксимации функций . Приближение линейной функции начинается с отображения, которое назначает конечномерный вектор каждой паре состояние-действие. Затем значения действия пары состояние-действие получаются путем линейного комбинирования компонентов с некоторыми весами :

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

Итерация значений также может использоваться в качестве отправной точки, что дает начало алгоритму Q-обучения и его многочисленным вариантам.

Проблема с использованием значений действия состоит в том, что им могут потребоваться высокоточные оценки значений конкурирующих действий, которые может быть трудно получить, когда результаты зашумлены, хотя эта проблема в некоторой степени смягчается методами временной разницы. Использование так называемого метода аппроксимации совместимых функций ставит под угрозу общность и эффективность. Другая проблема, характерная для TD, связана с их опорой на рекурсивное уравнение Беллмана. Большинство методов TD имеют так называемый параметр, который может непрерывно интерполировать между методами Монте-Карло, которые не полагаются на уравнения Беллмана, и основными методами TD, которые полностью полагаются на уравнения Беллмана. Это может быть эффективным средством решения этой проблемы.

Прямой поиск политики

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

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

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

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

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

Алгоритмы на основе моделей

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

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

Теория

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

Эффективное исследование MDP описано в Burnetas and Katehakis (1997). Ограничения производительности за конечное время также появились для многих алгоритмов, но ожидается, что эти границы будут довольно неопределенными, и, следовательно, требуется дополнительная работа, чтобы лучше понять относительные преимущества и ограничения.

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

Исследовать

Темы исследования включают

  • адаптивные методы, которые работают с меньшим количеством параметров (или без них) в большом количестве условий
  • решение проблемы геологоразведки в крупных МДП
  • комбинации с логическими фреймворками
  • крупномасштабные эмпирические оценки
  • обучение и действия в соответствии с частичной информацией (например, с использованием прогнозируемого представления состояния )
  • модульное и иерархическое обучение с подкреплением
  • улучшение существующих методов поиска по функциям ценности и политике
  • алгоритмы, которые хорошо работают с большими (или непрерывными) пространствами действий
  • передача обучения
  • обучение на протяжении всей жизни
  • эффективное планирование на основе выборки (например, на основе поиска по дереву Монте-Карло ).
  • обнаружение ошибок в программных проектах
  • Внутренняя мотивация, которая отличает стремление к информации, поведение типа любопытства от поведения, зависящего от задачи, целенаправленного поведения (обычно) путем введения функции вознаграждения, основанной на максимальном использовании новой информации.
  • Когнитивное моделирование с использованием обучения с подкреплением активно используется в вычислительной психологии.
  • Многоагентное или распределенное обучение с подкреплением - это интересная тема. Приложения расширяются.
  • Актер-критик обучение с подкреплением
  • Алгоритмы обучения с подкреплением, такие как TD-обучение, исследуются как модель для обучения мозга на основе дофамина . В этой модели дофаминергические проекции из черной субстанции в базальные ганглии действуют как ошибка прогноза. Обучение с подкреплением использовалось как часть модели обучения человеческим навыкам, особенно в отношении взаимодействия между неявным и явным обучением при приобретении навыков (первая публикация этого приложения была в 1995–1996 гг.).
  • Управление, ориентированное на пассажира
  • Алгоритмическая торговля и оптимальное исполнение
  • Оптимизация вычислительных ресурсов

Сравнение алгоритмов обучения с подкреплением

Алгоритм Описание Политика Пространство действий Государственное пространство Оператор
Монте-Карло Каждый визит в Монте-Карло Или Дискретный Дискретный Образец-средство
Q-обучение Состояние – действие – награда – состояние Вне политики Дискретный Дискретный Q-значение
SARSA Состояние – действие – награда – состояние – действие В соответствии с политикой Дискретный Дискретный Q-значение
Q-обучение - Лямбда Состояние – действие – награда – состояние со следами правомочности Вне политики Дискретный Дискретный Q-значение
SARSA - Лямбда Состояние – действие – награда – состояние – действие со следами правомочности В соответствии с политикой Дискретный Дискретный Q-значение
DQN Сеть Deep Q Вне политики Дискретный Непрерывный Q-значение
DDPG Глубокий детерминированный градиент политики Вне политики Непрерывный Непрерывный Q-значение
A3C Алгоритм асинхронного преимущества "субъект-критик" В соответствии с политикой Непрерывный Непрерывный Преимущество
NAF Q-Learning с нормализованными функциями преимущества Вне политики Непрерывный Непрерывный Преимущество
TRPO Оптимизация политики доверенного региона В соответствии с политикой Непрерывный Непрерывный Преимущество
PPO Проксимальная оптимизация политики В соответствии с политикой Непрерывный Непрерывный Преимущество
TD3 Двойной отложенный глубокий детерминированный градиент политики Вне политики Непрерывный Непрерывный Q-значение
SAC Мягкий Актер-Критик Вне политики Непрерывный Непрерывный Преимущество

Ассоциативное обучение с подкреплением

Задачи ассоциативного обучения с подкреплением сочетают в себе аспекты задач стохастических обучающих автоматов и задач классификации контролируемых шаблонов обучения. В задачах обучения с ассоциативным подкреплением обучающая система взаимодействует с окружающей средой по замкнутому циклу.

Глубокое обучение с подкреплением

Этот подход расширяет возможности обучения с подкреплением за счет использования глубокой нейронной сети без явного проектирования пространства состояний. Работа по изучению игр ATARI с помощью Google DeepMind повысила внимание к глубокому обучению с подкреплением или сквозному обучению с подкреплением .

Обратное обучение с подкреплением

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

Безопасное обучение с подкреплением

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

Частично контролируемое обучение с подкреплением (PSRL)

В алгоритмах PSRL синергетически сочетаются преимущества контролируемого подхода и подхода, основанного на RL. Например, политика управления, изученная с помощью подхода, основанного на обратной ИНС, для управления нелинейной системой, может быть уточнена с использованием RL, тем самым избегая вычислительных затрат, возникающих при запуске со случайной политики в традиционном RL. Частично контролируемые подходы могут облегчить потребность в обширных обучающих данных в контролируемом обучении, уменьшая при этом необходимость в дорогостоящем исчерпывающем случайном исследовании в чистом RL.

Смотрите также

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

дальнейшее чтение

внешние ссылки