В чем разница между Q-learning и SARSA?

Question

Хотя я знаю, что SARSA находится вне политики, в то время как Q-learning вне политики, при взгляде на их формулы трудно (для меня) увидеть разницу между ними два алгоритма.

Согласно книге Обучение усилению: Введение (Саттон и Барто). В алгоритме SARSA, с учетом политики, соответствующая функция-значение Q (в состоянии s и действии a, на временном шаге t), т.е. Q (s _t , a _t ), можно обновить следующим образом

Q (с _т , а _т ) = Q (с _т , а _т ) + α * (r _т + γ * Q (с _{т + 1} , а _{т + 1} ) - Q (с _т , а _т ))

С другой стороны, шаг обновления для алгоритма Q-обучения следующий

Q (с _т , а _т ) = Q (с _т , а _т ) + α * (r _t + γ * max _a Q (s _{t + 1} , a) - Q (s _t , a _t ))

, который также можно записать как

Q (с _t , a _t ) = (1 - α) * Q (с _t , a _t ) + α * (r _t + γ * max _a Q (s _{t + 1} , a))

, где γ (гамма) - коэффициент дисконтирования, а r _t - вознаграждение, полученное от окружающей среды на шаге t.

Разница между этими двумя алгоритмами заключается в том, что SARSA ищет только следующее значение политики, а Q-learning ищет следующее максимальное значение политики?

TLDR (и мой собственный ответ)

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

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

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

* * Г тысячу сто двадцать пять (т + 1) * * тысяча сто двадцать шесть

на самом деле

* +1131 * г (т) * * тысяча сто тридцать-два

Надеюсь, это поможет кому-нибудь застрять в этом.

Answer 1

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

На практике, в соответствии с политикой ε-жадности, Q-Learning вычисляет разницу между Q (s, a) и максимальным значением действия, тогда как SARSA вычисляет разницу между Q (s, a) и взвешенной суммой среднее значение действия и максимум:

Q-Learning: Q (s _{t + 1} , a _{t + 1} ) = max _a Q (s _{t + 1} , а)

САРСА: Q (с _{t + 1} , a _{t + 1} ) = ε · среднее _a Q (с _{t + 1} , а) + (1-ε) · макс. _а Q (с _{т + 1} , а)

Answer 2

Когда я изучал эту часть, мне это тоже показалось очень запутанным, поэтому я собрал два псевдокода от Р.Саттона и А.Г.Барто, надеясь прояснить разницу.

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

TL; NR :

|             | SARSA | Q-learning |
|:-----------:|:-----:|:----------:|
| Choosing A' |   π   |      π     |
| Updating Q  |   π   |      μ     |

где π - политика ε-жадных алгоритмов (например, ε> 0 сразведка), а μ - жадная политика (например, ε == 0, НИКАКОЕ исследование).

1. Учитывая, что Q-learning использует разные политики для выбора следующего действия A 'и обновления Q. Другими словами, он пытается оценить π, следуя другой политике μ, так что этовне политики алгоритм.

2. В отличие от этого, SARSA постоянно использует π, следовательно, это алгоритм на основе политики.

Более подробное объяснение :

1. Самое важное различие между ними заключается в том, как Q обновляется после каждого действия.SARSA использует Q ', следуя ε-жадной политике, точно так же, как A' взято из нее.Напротив, Q-learning использует максимальное значение Q 'для всех возможных действий для следующего шага.Это выглядит как следование жадной политике с ε = 0, т. Е. НИКАКОГО исследования в этой части.

2. Однако, когда фактически выполняется действие, Q-learning все еще использует действие, предпринятое изε-жадная политика.Вот почему «Выбрать A ...» находится внутри цикла повторения.

3. Следуя логике цикла в Q-learning, A 'по-прежнему относится к политике ε-жадности.

Answer 3

Какая разница математически?

Как уже было описано в большинстве других ответов, разница между двумя обновлениями математически действительно заключается в том, что при обновлении значения Q для состоянияпара действий (S _t , A _t ) :

• Sarsa использует политику поведения (то есть политику, используемуюагент для генерации опыта в среде, который обычно epsilon -greedy) для выбора дополнительного действия A _{t + 1} , а затем использует Q (S _{t + 1} , A _{t + 1} ) (дисконтировано gamma ) как ожидаемые будущие доходы при вычислении цели обновления.
• Q - обучение не использует политику поведения для выбора дополнительного действия A _{t + 1} .Вместо этого он оценивает ожидаемые будущие доходы в правиле обновления как max _A Q (S _{t + 1} , A) .Используемый здесь оператор max можно рассматривать как «выполняющий» полностью жадную политику. Агент фактически не следует жадной политике, хотя ;в правиле обновления говорится только: «Предположим, что с этого момента я начну следовать жадной политике, каким будет мое ожидаемое будущее возвращение?».

---

Что это значитинтуитивно?

Как уже упоминалось в других ответах, различие, описанное выше, означает, используя техническую терминологию, что Sarsa является алгоритмом обучения on-policy , а Q-learning отключен -policy алгоритм обучения.

В пределе (учитывая бесконечное количество времени для накопления опыта и обучения) и при некоторых дополнительных предположениях это означает, что Sarsa и Q-learning сходятся к различным решениям / "оптимальным" политикам :

• Sarsa будет сходиться к , что является оптимальным решением, если мы будем придерживаться той же политики, которая использовалась для создания опыта ,Это часто будет политика с некоторым элементом (довольно «глупой») случайности, такой как epsilon -greedy, потому что в противном случае мы не сможем гарантировать, что вообще сойдемся с чем-либо.
• Q-Learning превратится в решение, оптимальное при условии, что после накопления опыта и обучения мы перейдем к жадной политике .

---

Когда использовать какой алгоритм?

Алгоритм, подобный Sarsa , обычно предпочтительнее в ситуациях, когда мы заботимся о производительности агента в процессе обучения / генерацииопыт .Например, представьте, что агент - это дорогой робот, который сломается, если упадет с обрыва.Мы бы не хотели, чтобы он падал слишком часто в процессе обучения, потому что это дорого.Поэтому мы заботимся о его производительности в процессе обучения.Тем не менее, мы также знаем, что нам нужно иногда действовать случайным образом (например, эпсилон-жадный).Это означает, что для робота очень опасно идти вдоль обрыва, потому что он может решить действовать случайно (с вероятностью epsilon) и упасть.Итак, мы бы предпочли, чтобы он быстро узнал, что находиться рядом со скалой опасно; даже если жадная политика сможет идти рядом с ней, не падая, мы знаем, что следуем эпсилон-жадной политике со случайностью, и мы заботимся об оптимизации нашей производительности, учитывая, что мы знаем, что будемглупый иногда .Это ситуация, когда Сарса предпочтительнее.

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

Answer 4

В вашей формуле для Q-Learning есть ошибка индекса.Страница 148 Саттона и Барто.

Q (st, at) <- Q (st, at) + alpha * [r (t + 1) + gamma * max Q (st + 1), a) - Q (st, at)] </p>

В аргументе max указана опечатка:

индексы st + 1 и a, а в вашем вопросе ониst + 1 и at + 1 (это верно для SARSA).

Надеюсь, это немного поможет.

Answer 5

В Q-Learning

Это ваше: Q-Learning: Q (St, At) = Q (St, At) + a [R (t + 1) + скидка * max Q (St+ 1, At ) - Q (St, At)]

следует изменить на Q-Learning: Q (St, At) = Q (St, At) + a [R(t + 1) + скидка * max Q (St + 1, a ) - Q (St, At)]

Как вы сказали, вы должны найти максимальное значение Qдля обновления экв.изменив a , тогда у вас будет новый Q (St, At).ВНИМАНИЕ, a , который дает вам максимальное значение Q, не является следующим действием.На этом этапе вы знаете только следующее состояние (St + 1), и прежде чем перейти к следующему раунду, вы хотите обновить St на St + 1 (St <- St + 1). </p>

Для каждого цикла;

• выберите At из St, используя Q-значение

• , возьмите At и наблюдайте Rt + 1 и St + 1

• Обновление Q-значения с использованием уравнения

• St <- St + 1 </p>

Пока St не терминал