Перспективы пути в обучении ценности

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

Эти оценки стоимости ведут себя по-разному там, где пересекаются пути опыта.

+2–1

Монте Карло

V(st) ? RtV(s_t) ~hookleftarrow~ R_tV (s t)  ?  R t?

+2–1

Временная Разница

V(st) ? rt + ?V(st+1)V(s_t) ~hookleftarrow~ r_{t} ~+~ gamma V(s_{t+1})V (s t)  ?  r t +  ? V ( s t + 1)

+2–1

Q-Обучение

Q(st,at) ? rt + ?V(st+1)Q(s_t, a_t) ~hookleftarrow~ r_{t} ~+~ gamma V(s_{t+1})Q (s t, a t)  ?  r t +  ? V (s t + 1) V(st+1) = maxa Q(st+1,at+1)V(s_{t+1}) ~=~ mathop{ extrm{max}} limits_{a} ~ Q(s_{t+1},a_{t+1})V (s t + 1)  =  a maxQ  ( s t + 1, A t + 1)

Введение

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

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

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

Утес Мира

[1]

это классический пример RL, где агент учится к прогулка вдоль скалы, чтобы достичь цели .

Иногда агент достигает своей цели.

В других случаях он падает с обрыва.

Монте-Карло усредняет траектории там, где они пересекаются.

Если состояние посещается только одним эпизодом, Монте-Карло говорит, что его значение-это возвращение этого эпизода. Если несколько эпизодов посещают состояние, Монте-Карло оценивает его значение как среднее по ним.

Давайте напишем Монте-Карло немного более формально. В RL мы часто описываем алгоритмы с правилами обновления, которые говорят нам, как оценки меняются с еще одним эпизодом. Мы будем использовать оператор “обновления в сторону” ( ?hookleftarrow? ), чтобы сохранить простые уравнения. 2

V(st)  V(s_t)~~V (s t)  

  hookleftarrow~~?  

RtR_tRt?

Государственное значение Возврат

Термин справа называется возвратом, и мы используем его для измерения суммы долгосрочного вознаграждения, которое получает агент. Доходность - это просто взвешенная сумма будущих вознаграждений rt+?rt+1+?2rt+2+...r_{t} + gamma r_{t+1} + gamma^2 r_{t+2} + …r t + ? r t + 1 + ? 2 r t + 2+ ... где ?gamma?-коэффициент дисконтирования, который определяет, сколько краткосрочных вознаграждений стоит относительно долгосрочных вознаграждений. Оценка стоимости путем обновления в сторону возврата имеет большой смысл. Ведь от определения стоимости ожидается доходность. Это может быть удивительно, что мы можем сделать лучше.

Обыгрывание Монте-Карло

Но мы можем сделать и лучше! Хитрость состоит в том , чтобы использовать метод под названием Temporal Difference (TD) learning, который загрузится из соседних состояний, чтобы сделать обновления значения.

V(st)  V(s_t)~~V (s t)  

  hookleftarrow~~?  

rtr_{t} rt?

+++

V(st+1)gamma V(s_{t+1})? V ( s t + 1)

Государственное значение Вознаграждение Следующее значение состояния

Пересечения между двумя траекториями обрабатываются по-разному в этом обновлении. В отличие от Монте-Карло, TD обновляет пересечения слияния так, что возврат течет назад ко всем предыдущим состояниям.

Иногда агент достигает своей цели.

В других случаях он падает с обрыва.

TD learning объединяет пути, где они пересекаются.

Что значит "объединить траектории" в более формальном смысле? Почему это может быть хорошей идеей? Одна вещь, чтобы заметить, что V(st+1)V(s_{t+1})V (s t + 1) можно записать как ожидание по всем его обновлениям TD:

V(st+1)  V(s_{t+1})~~V ( s t + 1)  

  simeq~~?  

E[rt+1? + ?V(st+2?)]mathop{mathbb{E}} igr[ r’_{t+1} ~+~ gamma V(s’_{t+2}) igl] E [ r t + 1 '  +  ? V ( s t + 2 ')]

  simeq~~?  

E[rt+1?]  +  ?E[V(st+2?)]mathop{mathbb{E}} igr[ r’_{t+1} igl] ~~+~~ gamma mathop{mathbb{E}} igr[ V(s’_{t+2}) igl] E [ r t + 1 ']   +   ? E [ V ( s t + 2 ')]

Теперь мы можем использовать это уравнение для рекурсивного расширения правила обновления TD:

V(st) V(s_t)~V (s t) 

 hookleftarrow~? 

rtr_{t} rt?

+++

V(st+1)gamma V(s_{t+1})? V ( s t + 1) hookleftarrow~? 

rtr_{t} rt?

+++

E[rt+1?]gamma mathop{mathbb{E}} igr[ r’_{t+1} igl]? E [ r t + 1 ']

+++

2E[V(st+2??)]gamma^2 mathop{mathbb{E}} igr[ V(s’’_{t+2}) igl]? 2 E [ V ( s t + 2 ' ')] hookleftarrow~? 

rtr_{t} rt?

+++

E [rt+1?]gamma mathop{mathbb{E}} ~ igr[ r’_{t+1} igl]? E  [ r t + 1 ']

+++

2EE [rt+2??]gamma^2 mathop{mathbb{EE}} ~ igr[ r’’_{t+2} igl]? 2 E E  [ r t + 2 ' ']

+ +~+ 

...  …~~...  

Это дает нам странную на вид сумму вложенных математических ожиданий. На первый взгляд, не совсем понятно, как сравнивать их с более простым на вид обновлением Monte Carlo. Что еще более важно, неясно, что мы должны сравнивать эти два; обновления настолько разные, что это похоже на сравнение яблок с апельсинами. Действительно, легко думать о Монте-Карло и TD learning как о двух совершенно разных подходах.

Но в конце концов они не так уж и отличаются. Давайте перепишем обновление Монте-Карло с точки зрения вознаграждения и разместим его рядом с расширенным обновлением TD.

Обновление MC

V(st) V(s_t)~V (s t) 

 ?  ~hookleftarrow~~ ?  

rtr_{t}rt?

+ +~+ 

 rt+1gamma ~ r_{t+1}? rt+1?

+ +~+ 

2 rt+2gamma^2 ~ r_{t+2}?2 rt+2?

+ +~+ 

...…...

Награда от настоящего пути. Награда от настоящего пути. Награда от настоящего пути… Обновление TD

V(st) V(s_t)~V (s t) 

 ?  ~hookleftarrow~~ ?  

rtr_{t}rt?

+ +~+ 

E [rt+1?]gamma mathop{mathbb{E}} ~ igr[ r’_{t+1} igl]? E  [ r t + 1 ']

+ +~+ 

2EE [rt+2??]gamma^2 mathop{mathbb{EE}} ~ igr[ r’’_{t+2} igl]? 2 E E  [ r t + 2 ' ']

+ +~+ 

...…...

Награда от настоящего пути. Ожидание по путям, пересекающимся с настоящим путем. Ожидание по путям, пересекающимся с путями, пересекающимися с настоящим путем…

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

Перспектива Пути

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

Траектория 1

Траектория 2

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

Путь 1

Путь 2

Путь 3

Путь 4

Оценочная величина. Оказывается, что Монте-Карло усредняет реальные траектории, тогда как TD learning усредняет все возможные пути. Вложенные математические ожидания, которые мы видели ранее, соответствуют усреднению агента по всем возможным будущим путям .

Оценка По Методу Монте-Карло

Средние значения по реальным траекториям

Итоговая оценка MC

Оценка Временных Разностей

Средние значения по возможным путям

Итоговая оценка TD

Сравнивая эти две вещи. Вообще говоря, наилучшая оценка стоимости - это оценка с наименьшей дисперсией. Поскольку табличные TD и Монте-Карло являются эмпирическими средними, метод, который дает лучшую оценку, является тем, который усредняет больше элементов. Это вызывает естественный вопрос:какая оценка усредняет больше предметов?

Var[V(s)]  Var[V(s)]~~Var[V(s)]  

  propto~~?  

1Nfrac{1}{N} N1?

Дисперсия оценки Обратное от количества элементов в среднем

Во-первых, TD learning никогда не усредняется по меньшему числу траекторий, чем Монте-Карло, потому что существует никогда не меньше моделируемых траекторий, чем реальные траектории. С другой стороны, когда существует больше моделируемых траекторий, обучение TD имеет шанс усреднить большую часть опыта агента. Эта линия рассуждений предполагает, что TD learning является лучшей оценкой и помогает объяснить, почему TD стремится превзойти Монте-Карло в табличных средах.

Введение Q-функций

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

Много раз мы хотели бы сравнить ценность действий в рамках политики.

Это трудно сделать с помощью функции value.

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

Есть и некоторые другие приятные свойства Q-функций. Чтобы увидеть их, давайте выпишем правила Монте-Карло и обновления TD.

Обновление Q-функций. Правило обновления Монте-Карло выглядит почти идентичным тому, которое мы записали для V(s)V(s)V (s ):

Q(st,at)  Q(s_t, a_t)~~Q ( s t, a t)  

  hookleftarrow~~?  

RtR_tRt?

Значение состояния-действия Возврат

Мы все еще обновляем в сторону возвращения. Однако вместо обновления в сторону возвращения бытия в некотором состоянии мы обновляем в сторону возвращения бытия в некотором состоянии и выбора некоторых действий.

Теперь давайте попробуем сделать то же самое с обновлением TD:

Q(st,at)  Q(s_t, a_t)~~Q ( s t, a t)  

  hookleftarrow~~?  

rtr_{t} rt?

+++

Q(st+1,at+1)gamma Q(s_{t+1}, a_{t+1})? Q ( s t + 1, a t + 1)

Значение состояния-действия Вознаграждение Следующее значение состояния

Эта версия правила обновления TD требует кортежа вида (st,at,rt,st+1,at+1)(s_t, a_t, r_{t}, s_{t+1}, a_{t+1})(s t, a t, r t, s t + 1 , A t + 1), поэтому мы называем его алгоритмом Sarsa. Sarsa может быть самым простым способом написать это обновление TD, но это не самый эффективный способ. Проблема с Sarsa заключается в том, что он использует Q(st+1,at+1)Q(s_{t+1},a_{t+1})Q ( s t + 1, A t + 1) для следующего значения состояния, когда он действительно должен использовать V(st+1)V(s_{t+1})V ( s t + 1) . То, что нам нужно, - это лучшая оценка V(st+1)V(s_{t+1})V ( s t + 1) .

Q(st,at)  Q(s_t, a_t)~~Q ( s t, a t)  

  hookleftarrow~~?  

rtr_{t} rt?

+++

V(st+1)gamma V(s_{t+1})? V ( s t + 1)

Значение состояния-действия Вознаграждение Следующее значение состояния

V(st+1)  V(s_{t+1})~~V ( s t + 1)  

=  =~~=  

?

Существует множество способов восстановления V(st+1)V(s_{t+1})V (s t + 1) из Q-функций. В следующем разделе мы подробно рассмотрим четыре из них.

Обучение Q-функций с перевешенными путями

Ожидал Увидеть Сарсу. Лучший способ оценить значение следующего состояния - это взвешенная сумма 3 над его Q-значениями. Мы называем такой подход ожидаемым Sarsa:

Sarsa использует значение Q, связанное с at+1a_{t+1}t + 1, чтобы оценить значение следующего состояния.

Ожидаемая Sarsa использует ожидание по Q-значениям для оценки значения следующего состояния.

Вот удивительный факт об ожидаемом Sarsa: оценка стоимости, которую он дает, часто лучше, чем оценка стоимости, вычисленная прямо из опыта. Это происходит потому, что математическое ожидание взвешивает Q-значения по истинному распределению политики, а не эмпирическому распределению политики. При этом ожидаемая Sarsa корректирует разницу между эмпирическим распределением политики и истинным распределением политики.

Вне политики значение обучения. Мы можем продвинуть эту идею еще дальше. Вместо того чтобы взвешивать Q-значения истинным распределением политик, мы можем взвешивать их произвольной политикой, ?offpi^{off}? o f f:

Вне политики значение обучения Весов Q-значения произвольной политики.

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

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

В этом состоянии пересекаются несколько путей переживания.

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

+2 -1

Вес восходящего пути: 0.00

Всякий раз, когда мы переносим Q-значения, мы также переносим пути, которые проходят через них.

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

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

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

Q-обучение отсекает все, кроме наиболее ценных путей. Оставшиеся пути-это те, по которым агент будет следовать во время тестирования; это единственные пути, на которые он должен обратить внимание. Такой вид обучения ценностям часто приводит к более быстрой конвергенции, чем внутриполитические методы 4 .

Двойное Q-Обучение. Проблема с Q-обучением заключается в том, что оно дает необъективные оценки стоимости. Более конкретно, он чрезмерно оптимистичен в присутствии шумных вознаграждений. Вот пример, где Q-learning терпит неудачу:

Вы идете в казино и играете на сотне игровых автоматов. Это ваш счастливый день: вы попали в джек-пот на машине 43. Теперь, если вы используете Q-learning для оценки стоимости пребывания в казино,вы выберете лучший результат над действиями игровых автоматов. Вы будете в конечном итоге думать, что ценность казино - это ценность джекпота...и решить, что КАЗИНО-это отличное место, чтобы быть!

Иногда самое большое Q-значение состояния является большим просто случайно ; выбор его над другими делает оценку значения предвзятой. Один из способов уменьшить этот уклон - пригласить друга посетить казино и сыграть в тот же набор игровых автоматов. Затем спросите их, что их выигрыш был на машине 43 и использовать их ответ в качестве оценки стоимости. Маловероятно, что вы оба выиграли Джекпот на одной и той же машине, поэтому на этот раз вы не будете в конечном итоге с чрезмерно оптимистичной оценкой. Мы называем этот подход двойным Q-обучением .

[2]

Складываю их вместе. Легко думать о Sarsa, ожидаемом Sarsa, Q-learning и двойном Q-learning как о разных алгоритмах. Но, как мы уже видели, это просто разные способы оценки V(st+1)V(s_{t+1})V ( s t + 1) в обновлении TD.

Внутриполитические методы

Sarsa использует значение Q, связанное с at+1a_{t+1}t + 1, чтобы оценить значение следующего состояния.

Ожидаемая Sarsa использует ожидание по Q-значениям для оценки значения следующего состояния.

Внеполитические методы

Вне политики значение обучения Весов Q-значения произвольной политики.

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

Двойное Q-обучение выбирает лучшее действие с QAQ_AQ A, а затем оценивает значение этого действия с помощью QBQ_BQ B.

Интуиция, стоящая за всеми этими подходами, заключается в том, что они повторно утяжеляют пересечения путей.

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

Объединение путей с функциональными Аппроксиматорами

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

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

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

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

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

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

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

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

Теперь использование евклидова усреднителя приводит к плохим обновлениям значений.

Слияние неверных путей. На диаграмме ниже показаны эффекты слияния неверных путей немного более явно. Поскольку усреднитель Евклида виноват в плохом обобщении, и Монте-Карло, и TD делают плохие обновления значений. Однако TD learning значительно усиливает эти ошибки, в то время как Монте-Карло этого не делает.

Мы видели, что TD learning делает более эффективные обновления ценности. Цена, которую мы платим, заключается в том, что эти обновления оказываются гораздо более чувствительными к плохому обобщению.

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

Нейронная сеть. Глубокие нейронные сети являются, пожалуй, наиболее популярными функциональными аппроксиматорами для обучения подкреплению. Эти модели интересны по многим причинам, но одно особенно приятное свойство заключается в том, что они не делают неявных предположений о том, какие состояния находятся “рядом".”

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

Но по мере развития обучения нейронные сети действительно могут научиться преодолевать эти ошибки. Они узнают, какие состояния находятся "рядом" из собственного опыта. В Примере с миром Утесов мы могли бы ожидать, что полностью обученная нейронная сеть научилась тому, что обновление значений состояний выше барьера никогда не должно влиять на значения состояний ниже барьера. Это не то, что может сделать большинство других аппроксиматоров функций. Это одна из причин, почему deep RL так интересен!

Метрика расстояния, полученная с помощью нейронной сети

[3]

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

ТД или не тд? До сих пор мы видели, как TD learning может превзойти Монте-Карло, объединяя пути опыта там, где они пересекаются. Мы также видели, что слияние путей-это обоюдоострый меч: когда аппроксимация функции вызывает плохие обновления значений, TD может в конечном итоге сделать еще хуже.

За последние несколько десятилетий большинство работ в RL предпочли TD learning Монте-Карло. Действительно, многие подходы к RL используют обновления значений в стиле TD. С учетом сказанного, есть много других способов использовать Монте-Карло для подкрепления обучения. Наши дискуссионные центры вокруг Монте-Карло для оценки стоимости в этой статье, но он также может быть использован для выбора политики, как в Silver и др.

[4]

Поскольку Монте-Карло и TD learning оба имеют желательные свойства, почему бы не попробовать построить оценщик ценности, который является смесью этих двух? Таковы рассуждения, лежащие в основе td (?lambda? ) обучения. Это метод, который просто интерполирует (используя коэффициент ?lambda? ) между Монте-Карло и обновлениями TD 5 . Часто, TD (?lambda? ) работает лучше, чем либо Монте-Карло или TD обучения в одиночку 6 .

Вывод

В этой статье мы представили новый способ думать об обучении TD. Это помогает нам понять, почему обучение TD может быть полезным, почему оно может быть эффективным для внеполитического обучения и почему могут возникнуть проблемы в объединении обучения TD с функциональными аппроксиматорами.

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

Источник: distill.pub

Комментарии: