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

Question

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

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

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

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

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

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

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

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

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

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}, a)

САРСА: Q (s_{t + 1}, a_{t + 1}) = ε · означает_a Q (s_{t + 1}, a) + (1-ε) · max_a Q (s_{t + 1}, a)

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):

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

---

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

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

В пределе (учитывая бесконечное количество времени для накопления опыта и обучения) и при некоторых дополнительных допущениях это означает, что 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)]

Опечатка в аргументе max:

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

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

Answer 5

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

Answer 6

В 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-значение, используя уравнение.

• Ст <- Ст + 1

До тех пор, пока St терминал

Answer 7

Я не читал ни одной книги, просто я вижу их значение q обучение просто сосредоточьтесь на (сетке действий) обучение SARSA просто сосредоточьтесь на (от состояния к состоянию) и наблюдайте за списком действий s и s ', а затем обновите ( состояние сетки состояния)

Answer 8

Агенты SARSA и Q-learning следуют политике электронной жадности для взаимодействия с окружающей средой.

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

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

Следовательно, SARSA соответствует политике, а Q-learning — вне политики.