Алгоритм SARSA: on-policy обучение с подкреплением по шагам

SARSA - один из базовых алгоритмов обучения с подкреплением, который учит агента действовать, пробуя шаги в среде и постепенно уточняя оценку «насколько хорош тот или иной выбор». Название складывается из пяти величин, которые алгоритм использует на каждом шаге: state, action, reward, state, action. В отличие от знаменитого Q-обучения, SARSA оценивает не идеальную, а ту стратегию, которой агент реально следует, включая её случайные пробы. Разберём правило обновления, его связь с временной разностью и то, почему SARSA называют осторожным алгоритмом. Ниже можно собрать запрос по своей задаче и получить пошаговый разбор.

Что обозначает аббревиатура SARSA

Имя алгоритма буквально перечисляет данные одного обучающего перехода. Агент находится в состоянии $S_t$, выбирает действие $A_t$, получает награду $R_{t+1}$, переходит в новое состояние $S_{t+1}$ и там выбирает следующее действие $A_{t+1}$. Эта пятёрка

$$(S_t,\; A_t,\; R_{t+1},\; S_{t+1},\; A_{t+1})$$

и дала название SARSA. Ключевая деталь в том, что последнее $A_{t+1}$ - реально выбранное агентом действие, а не теоретически наилучшее. Именно из-за этого SARSA относят к классу on-policy: он улучшает ту же стратегию, по которой собирает опыт.

Рассчитать для своей задачи

Правило обновления

Алгоритм хранит таблицу оценок $Q(s,a)$ - ожидаемой суммарной награды за выбор действия $a$ в состоянии $s$. После каждого перехода значение для пары $(S_t, A_t)$ сдвигается в сторону наблюдаемого опыта:

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha\,\bigl[R_{t+1} + \gamma\,Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)\bigr]$$

Здесь $\alpha \in (0,1]$ - скорость обучения, $\gamma \in [0,1]$ - коэффициент дисконтирования будущих наград. Выражение в скобках называют ошибкой временной разности (TD-ошибкой):

$$\delta_t = R_{t+1} + \gamma\,Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)$$

Она показывает, насколько прежняя оценка $Q(S_t, A_t)$ расходится с уточнённой целью $R_{t+1} + \gamma\,Q(S_{t+1}, A_{t+1})$. Если TD-ошибка положительна, значит шаг оказался лучше ожиданий, и оценка растёт; если отрицательна - падает. Множитель $\alpha$ задаёт, какую долю этого расхождения учесть за один раз.

Удобно понимать обновление как обучение на собственном прогнозе: цель сама собрана из оценок $Q$, а не из конечного выигрыша, который ещё далеко в будущем. Этот приём называют бутстрэпом - алгоритм подтягивает текущую оценку к более свежей оценке того же типа, не дожидаясь конца эпизода. Благодаря этому SARSA учится онлайн, прямо в ходе одного прохода по среде, а не только по завершённым траекториям. Коэффициент дисконтирования $\gamma$ при этом регулирует горизонт планирования: при $\gamma$ близком к нулю агент гонится за немедленной наградой, при $\gamma$ близком к единице - учитывает далёкие последствия своих ходов.

On-policy: почему берётся реальное A_{t+1}

Главная особенность SARSA спрятана в цели обновления. Она использует $Q(S_{t+1}, A_{t+1})$, где $A_{t+1}$ выбирается той же политикой, что управляет агентом, обычно epsilon-жадной. Это значит, что в цель попадают и исследовательские, иногда невыгодные шаги. Алгоритм оценивает не гипотетически оптимальную стратегию, а ту, по которой агент действительно ходит - со всеми её случайными пробами.

Сравните с близким Q-обучением, где в цели стоит $\max_a Q(S_{t+1}, a)$: там оценивается наилучшее возможное действие независимо от того, что агент выберет на самом деле. Поэтому Q-обучение называют off-policy - оно учит одну (жадную) политику, следуя другой (исследующей).

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

Выбор действия: epsilon-жадная стратегия

Чтобы агент не застрял на первой найденной приличной траектории, действия выбираются с долей случайности. Самый частый приём - epsilon-жадная стратегия:

$$A_t = \begin{cases} \arg\max_a Q(S_t, a), & \text{с вероятностью } 1-\varepsilon \\ \text{случайное действие}, & \text{с вероятностью } \varepsilon \end{cases}$$

Параметр $\varepsilon$ задаёт долю исследования. На старте его держат большим (агент много пробует), затем плавно уменьшают, и поведение становится почти жадным. В SARSA это $\varepsilon$ влияет дважды: и на текущий шаг $A_t$, и на следующий $A_{t+1}$, который входит прямо в формулу обновления.

Рассчитать для своей задачи

Полный цикл одного эпизода

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

1. Инициализировать $Q(s,a)$ произвольно (часто нулями).
2. Начать в стартовом состоянии $S$, выбрать $A$ epsilon-жадно.
3. Повторять для каждого шага эпизода:
   • выполнить $A$, получить награду $R$ и новое состояние $S'$;
   • в $S'$ выбрать $A'$ epsilon-жадно;
   • обновить $Q(S, A)$ по правилу SARSA с этим $A'$;
   • присвоить $S \leftarrow S'$, $A \leftarrow A'$.
4. Завершить, когда $S$ - терминальное состояние.

Поскольку $A'$ выбирается до обновления и затем становится действием следующего шага, опыт собирается и используется одной и той же политикой без разрыва.

Осторожность SARSA на примере обрыва

Классическая иллюстрация различия - задача «прогулка по обрыву» (cliff walking). Агент идёт по краю пропасти: кратчайший путь проходит вплотную к обрыву, падение даёт большой штраф. Q-обучение, оценивая идеальную жадную политику, выводит агента на самый короткий, но рискованный маршрут у самого края. SARSA же учитывает, что из-за исследования агент иногда оступится в пропасть, и потому предпочитает идти чуть дальше от обрыва - путь длиннее, зато безопаснее.

Это и есть смысл фразы «SARSA осторожнее»: он оптимизирует ту политику, которая включает случайные ошибки, поэтому избегает состояний, где такая ошибка дорого стоит. При стремлении $\varepsilon \to 0$ оба алгоритма сходятся к одной оптимальной политике, ведь без исследования случайных падений в пропасть больше не случается, и безопасный окольный путь теряет преимущество. На практике это означает, что выбор между SARSA и Q-обучением зависит от цены ошибки во время самого обучения: если агент учится в реальной системе, где промах опасен, осторожность SARSA ценнее формально оптимального, но рискованного маршрута Q-обучения.

Частые ошибки

• Путать SARSA и Q-обучение в формуле. В SARSA в цели стоит $Q(S_{t+1}, A_{t+1})$ с реально выбранным $A_{t+1}$, а не $\max_a Q(S_{t+1}, a)$. Подмена меняет алгоритм на off-policy.
• Обновлять Q до выбора A'. Сначала выбирают следующее действие $A'$ epsilon-жадно, и только потом подставляют его в формулу обновления - иначе теряется суть on-policy.
• Держать $\varepsilon$ и $\alpha$ постоянными до конца. Без затухания исследования и скорости обучения оценки не стабилизируются, а агент продолжает совершать лишние пробы.
• Игнорировать терминальное состояние. В терминальном $S_{t+1}$ слагаемое $\gamma\,Q(S_{t+1}, A_{t+1})$ обнуляют, иначе оценка завышается.
• Слишком большой $\alpha$. При скорости обучения близко к 1 оценка скачет за каждым случайным переходом и не сходится.

FAQ

Чем SARSA принципиально отличается от Q-обучения? SARSA - on-policy: в цель обновления входит действие $A_{t+1}$, которое агент действительно выберет своей текущей политикой. Q-обучение - off-policy: в цели стоит максимум по действиям, то есть оценка наилучшего хода независимо от реального выбора. Из-за этого SARSA ведёт себя осторожнее в рискованных средах.

Что такое TD-ошибка в SARSA? Это разность между уточнённой целью $R_{t+1} + \gamma\,Q(S_{t+1}, A_{t+1})$ и прежней оценкой $Q(S_t, A_t)$. Она измеряет, насколько опыт расходится с ожиданием, и именно на её долю (через коэффициент $\alpha$) сдвигается значение в таблице.

Сходится ли SARSA к оптимальной политике? Да, при выполнении условий сходимости (убывающие шаг обучения и доля исследования, посещение всех пар состояние-действие) SARSA сходится к оптимальной политике. Когда $\varepsilon \to 0$, осторожная политика SARSA совпадает с жадной оптимальной.

Коротко

SARSA - это on-policy алгоритм временной разности, который обновляет таблицу $Q$ по пятёрке state-action-reward-state-action, подставляя в цель реально выбранное следующее действие $A_{t+1}$. Из-за этого он оценивает ту же epsilon-жадную политику, по которой собирает опыт, и ведёт себя осторожнее off-policy Q-обучения в средах с риском, сходясь к одной и той же оптимальной политике при затухании исследования.