На пути к повышению эффективности обучения агентов по обучению с подкреплением

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

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

Эта статья вдохновлена ​​Лекцией Дэвида Сильвера о MDP, и уравнения, используемые в этой статье, взяты из той же самой.

Содержание

  1. Терминология
  2. Марковское свойство
  3. Марковский процесс или цепь Маркова
  4. Марковский процесс вознаграждения (MRP)
  5. Марковский процесс принятия решений (MDP)
  6. Возврат (G_t)
  7. Политика (π)
  8. Функции значения
  9. Функции оптимального значения

Терминология

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

  1. Агент: Агент RL - это объект, который мы обучаем принимать правильные решения (например, робот, который обучается перемещаться по дому без сбоев).
  2. Окружение: Окружение - это окружение, с которым взаимодействует агент (например, дом, в котором движется робот). Агент не может манипулировать окружающей средой; он может управлять только своими собственными действиями (например, робот не может контролировать, где в доме стоит стол, но может обходить его, чтобы избежать сбоев).
  3. Состояние: состояние определяет текущую ситуацию агента (например: это может быть точное положение робота в доме, выравнивание двух его ног или текущее положение; это зависит от о том, как вы решаете проблему).
  4. Действие: выбор, который агент делает на текущем временном шаге (например: он может переместить правую или левую ногу, или поднять руку, или поднять объект, повернуть направо или налево и т. д. ). Мы заранее знаем набор действий (решений), которые может совершить агент.
  5. Политика. Политика - это мыслительный процесс, лежащий в основе выбора действия. На практике это распределение вероятностей, присвоенное набору действий. Действия с высокой степенью вознаграждения будут иметь высокую вероятность, и наоборот.

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

Марковская собственность

Предположим, что робот сидел на стуле, он встал и выставил вперед правую ногу. Итак, в настоящее время он стоит правой ногой вперед (это его текущее состояние).

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

Формально, для состояния S_t быть марковским, вероятность следующего состояния S_ (t + 1) быть должно зависеть только от текущего состояния S_t = s _ t , а не в остальных прошлых состояниях S₁ = s₁, S₂ = s₂,…

Марковский процесс или цепь Маркова

Марковский процесс определяется как (S, P), где S - состояния, а P - вероятность перехода между состояниями. Он состоит из последовательности случайных состояний S₁, S₂,…, где все состояния подчиняются свойству Маркова.

Вероятность перехода состояния или P_ss ' - это вероятность перехода в состояние s' из текущего состояния s.

Чтобы получить представление о концепции, рассмотрите рисунок выше. Сидящий, Стоящий, Разбитый и т. Д. - это состояния, и указаны их соответствующие вероятности перехода между состояниями.

Марковский процесс вознаграждения (MRP)

MRP определяется как (S, P, R, γ), где S - состояния, P - вероятность перехода между состояниями, R_s - награда, а γ - коэффициент скидки (будет рассмотрен в следующих разделах).

Награда состояния R_s - это ожидаемая награда за все возможные состояния, в которые можно перейти из состояния s . Эта награда получена за нахождение в состоянии S_t. По соглашению, он считается полученным после того, как агент покидает состояние, и, следовательно, рассматривается как R_ (t + 1).

Например:

Марковский процесс принятия решений (MDP)

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

Теперь мы обсудим, как использовать MDP для решения проблем RL.

Возврат (G_t)

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

Скидка (γ)

Переменная γ ∈ [0, 1 ] на рисунке - коэффициент дисконтирования. Интуиция, лежащая в основе использования скидки, заключается в том, что нет уверенности в отношении будущих вознаграждений; то есть, насколько важно учитывать будущие награды для увеличения доходности, не менее важно ограничить вклад будущих вознаграждений в доходность (поскольку вы не можете быть на 100% уверены в будущем).

А еще потому, что пользоваться скидкой математически удобно.

Политика (π)

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

Формально политика - это распределение вероятностей по набору действий a с учетом текущего состояния s т.е. дает вероятность выбрать действие a в состоянии s.

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

Функция значения - это долгосрочное значение состояния или действия, то есть ожидаемый возврат по состоянию или действию. Это то, что мы действительно заинтересованы в оптимизации.

Состояние Значение Функция (для MRP)

Функция значения состояния v (s) - это ожидаемый возврат, начиная с состояния s.

Уравнение ожидания Беллмана (для MRP)

Уравнение Беллмана дает стандартное представление для функций стоимости. По сути, он разбивает функцию ценности на два компонента:

  1. Немедленное вознаграждение R_ (t + 1)
  2. Дисконтированная стоимость будущего состояния γ.v (S_ (t + 1))

Если вы не знаете, как мы закончили повторение вышеупомянутого, следуйте этой теме: https://medium.com/@arnau.jc91/really-nice-explanation-3e71ccb4d49e. Окончательный ответ: https://rojagtap.medium.com/i-got-your-point-502bbaa27b8e

Чтобы лучше понять это, давайте рассмотрим следующий сценарий (для простоты рассмотрим только MRP):

Агент может перейти из текущего состояния s в некоторое состояние s ’. Теперь функция значения состояния - это в основном ожидаемое значение Returns для всех s ’. Теперь, используя то же определение, мы можем рекурсивно заменить Return следующего состояния s ' функцией значения s' . Именно это и делает уравнение Беллмана:

Теперь давайте решим это уравнение:

Итак, поскольку ожидание является распределительным, мы можем решить как R_ (t + 1), так и v (s ') отдельно. Мы уже видели, что ожидаемое значение R_ (t + 1) над S_t = s - это состояние вознаграждение R_s. И ожидание v (s ') по всем s' равно принято по определению Ожидаемая стоимость.

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

Функция значения состояния (для MDP)

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

Действие Значение Функция (для MDP)

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

Функции значения состояния и функции значения действия тесно связаны. Мы увидим, как это сделать, в следующем разделе.

Уравнение ожидания Беллмана (для MDP)

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

Обратите внимание: мы обозначаем состояния кружками, а действия - точками; Обе диаграммы выше представляют собой представление одного и того же MDP на разных уровнях, левое - «ориентированное на государство» представление, а право - «ориентированное на действие» представление.

Давайте сначала разберемся с цифрой:

  • Круг к точке: агент находится в состоянии s; он выбирает действие a в соответствии с политикой. Например: допустим, мы обучаем агента игре в шахматы. Один временной шаг эквивалентен одному целому ходу (соответственно, один ход белых и один ход черных). Итак, в этой части перехода агент выбирает действие (делает ход). Эта часть полностью контролируется агентом, поскольку он может выбрать действие.
  • От точки к кругу. Среда воздействует на агента и переводит его в состояние, основанное на вероятности перехода. Например: продолжение примера с агентом, играющим в шахматы, это часть перехода, когда противник делает ход. После обоих ходов мы называем это полным переходом между состояниями. Эта часть не контролируется агентом, поскольку она не может контролировать действия среды, а только свое собственное поведение.

Теперь мы рассматриваем их как два отдельных мини-перехода:

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

И это полностью удовлетворяет уравнению Беллмана, как и для функции значения действия:

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

Оптимальные функции ценности

Скажем, мы получаем значение для всех состояний / действий MDP для всех возможных шаблонов действий, которые можно выбрать, то есть для всех политик. Затем мы можем просто выбрать политику с наибольшим значением для состояний и действий. Приведенные выше уравнения представляют именно это.

Если мы получим q ∗ (s, a), проблема решена.

Мы можем просто присвоить вероятность 1 для действия, которое имеет максимальное значение для q ∗ и 0 для остальных действий для всех данных состояний, т.е.

Уравнение оптимальности Беллмана

Поскольку мы в любом случае собираемся выбрать действие, которое дает max q ∗, мы можем просто присвоить это значение как функцию оптимального значения.

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

Заключение

Мы можем решить большинство проблем RL как MDP (как мы это сделали для робота или агента, играющего в шахматы). Просто определите набор состояний и действий.

В предыдущем разделе я сказал: «Скажем, мы получаем значение для всех состояний / действий MDP для всех возможных шаблонов действий, которые можно выбрать, то есть для всех политик». Однако это практически невозможно. Могут быть миллионы возможных схем переходов, и мы не можем оценить их все. Кроме того,

В этой статье мы обсудили формулировку любой проблемы RL в MDP и оценку агента в контексте MDP. Однако мы не говорили о поиске оптимальных ценностей / политики.

Существует множество итерационных решений для получения оптимального решения для MDP. Например:

  1. Итерация значений
  2. Итерация политики
  3. SARSA
  4. Q-Learning

Я постараюсь осветить это в будущих статьях.

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

Лекция Дэвида Сильвера о MDP: https://www.youtube.com/watch?v=lfHX2hHRMVQ&list=PLqYmG7hTraZDM-OYHWgPebj2MfCFzFObQ&index=2

Курс NPTEL RL: https://www.youtube.com/watch?v=BpSNh1h4HeQ&list=PLyqSpQzTE6M_FwzHFAyf4LSkz_IjMyjD9&index=21