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

Ответ 1

Да, это единственное различие. On-policy 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суб > , а)}

SARSA: Q (s _{t + 1}, a _{t + 1}) = ε · mean _a Q (s _{t +1}, a) + (1-ε) · max _a Q (s _{t + 1}, a)

Ответ 2

Когда я изучал эту часть, я тоже очень сбивал с толку, поэтому я собрал два псевдокода из R.Sutton и A.G.Barto, надеясь сделать разницу более ясными.

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

TL; NR:

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

где π - ε-жадная политика (например, ε > 0 при исследовании), а μ - жадная политика (например, ε == 0, исследование NO).

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

• В отличие от этого, SARSA все время использует π, поэтому он является алгоритмом on-policy.

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

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

• Однако, когда на самом деле предпринимает действия, Q-обучение все еще использует действие, принятое из ε-жадной политики. Вот почему "Choose A..." находится внутри цикла повторения.

• Следуя логике цикла в Q-обучении, A 'все еще остается из ε-жадной политики.

Ответ 3

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

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

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

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

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

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

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

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

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

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

Ответ 4

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

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

Опечатка находится в аргументе max:

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

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

Ответ 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).

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

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

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

• Обновить значение Q с помощью эквалайзера

• St < - St + 1

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

Ответ 6

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