Траектория «Обучение с подкреплением» · конспект 5 из 12

Табличные SARSA и Q-обучение

О чём эта тема: Первые полноценные алгоритмы управления без модели среды: TD-обучение из конспекта 4 переносится с V на Q, и получаются два классических метода — off-policy Q-learning и on-policy SARSA. Оба разбираются с выводом, кодом и полномасштабным примером FrozenLake, включая разбор неожиданной оптимальной политики и влияние гиперпараметров. По конспекту преподавателя и лекции 4 курса «RL: от бандитов до RLHF» (мехмат МГУ).
Аннотация: Конспект начинается с уравнения оптимальности Беллмана для Q-функции — жадная политика превращает усреднение по действиям в максимум — и итерационного метода его решения при известной модели. Замена усреднения по модели на наблюдаемый переход даёт Q-learning; разбираются его код с ε-распадом, смысл off-policy обучения и связь с оптимальным оператором Беллмана, дающая сходимость при условиях Роббинса–Монро. Затем вводится SARSA — on-policy вариант, использующий фактически выбранное следующее действие, — с таблицей отличий от Q-learning и промежуточным вариантом Expected SARSA. Отдельный раздел завершает линию динамического программирования: итерационный поиск политики при известной модели. Центральная практика — FrozenLake: разбор оптимальной политики гномика, путающего направления, точный расчёт её ценностей, влияние гиперпараметров на кривые обучения и численное разрешение вопроса, оставленного в источнике открытым. В тренажёре Q-learning и SARSA обучаются прямо в браузере. Завершается конспект систематической переоценкой максимума — мостом к Double DQN.
Пререквизиты: Конспект 4 (TD(0), TD-ошибка, бутстрап, on/off-policy, условия Роббинса–Монро, GPI), конспект 3 (уравнение Беллмана, оптимальные функции ценности, оператор и сжатие), конспект 2 (ε-жадные стратегии), конспект 1 (FrozenLake как среда).
Мотивация: TD(0) из конспекта 4 оценивает состояния, но управлять через V без модели нельзя — для жадного шага нужен просмотр вперёд по вероятностям среды. Перенос TD-идеи на Q-функцию убирает последнее препятствие: агент учится сравнивать действия напрямую, по одним лишь переходам. Q-learning, которому это удалось первым (Уоткинс, 1989), до сих пор — самый узнаваемый алгоритм RL: его глубокая версия DQN (конспект 7) играла в Atari.

1. Уравнение оптимальности Беллмана

Пусть агент всегда выбирает действие с максимальной полезностью: \(a = \arg\max_a Q(s,a)\). Для такой жадной детерминированной политики усреднение по действиям в связи \(V = \sum_a \pi Q\) (конспект 3, формула (3.7)) вырождается в максимум: \(V(s) = \max_\alpha Q(s, \alpha)\). Подстановка в уравнение Беллмана для Q (конспект 3, формула (3.11)) даёт уравнение оптимальности Беллмана:

\[ Q^*(s, a) = \sum_{s'} \sum_{r} p(s', r \,|\, s, a) \Bigl[ r + \gamma \max_{a'} Q^*(s', a') \Bigr]. \tag{5.1}\]

В отличие от уравнения для фиксированной политики, система (5.1) нелинейна — внутри стоит максимум, и решить её обращением матрицы, как в конспекте 3, нельзя. Но итерационный подход работает: оптимальный оператор Беллмана (правая часть (5.1)) — тоже γ-сжатие, и при известной модели среды к \(Q^*\) сходятся итерации

\[ Q(s,a) \;\leftarrow\; Q(s,a) + \lambda \Bigl[ \sum_{s',r} p(s', r|s, a) \bigl( r + \gamma \max_{a'} Q(s', a') \bigr) - Q(s,a) \Bigr], \tag{5.2}\]

где \(\lambda\) — скорость обучения. Смысл прост: если \(Q\) меньше, чем требует уравнение Беллмана, — увеличить, если больше — уменьшить.

2. Q-learning

Если модель неизвестна, сумму по \((s', r)\) в (5.2) заменяем единственным наблюдённым переходом \(s_t \xrightarrow{a_t} s_{t+1}, r_{t+1}\) — тот же ход, что превратил уравнение Беллмана в TD(0) в конспекте 4:

\[ Q(s_t, a_t) \;\leftarrow\; Q(s_t, a_t) + \lambda \Bigl[ r_{t+1} + \gamma \max_{a} Q(s_{t+1}, a) - Q(s_t, a_t) \Bigr]. \tag{5.3}\]

Выражение в скобках — TD-ошибка \(\delta\) (конспект 4, формула (4.10)) с жадной целью: \(\delta > 0\) — переход позитивно неожиданный, \(\delta < 0\) — негативно. Для разведки действия выбираются ε-жадно (конспект 2), причём \(\varepsilon\) экспоненциально распадается: от \(\varepsilon_1\) до \(\varepsilon_2\) за decays эпизодов, затем ноль. Код из конспекта преподавателя:

Q = np.zeros((num_states, num_actions))    # начальные значения 0
eps1, eps2, decays = 1, 0.001, 5000       # параметры epsilon-распада
epsilon = eps1
decay   = math.exp(math.log(eps2/eps1)/decays)

def policy(s):                             # epsilon-жадная политика
    if np.random.random() < epsilon:       # случайно любое действие
        return np.random.randint(num_actions)
    return np.argmax(Q[s])                 # иначе лучшее

def run_episode(ticks=1000):
    s0, _ = env.reset()                    # начальное состояние среды
    for _ in range(ticks):
        a0 = policy(s0)                    # выбираем действие
        s1, r1, done, truncated, _ = env.step(a0)
        Q[s0, a0] += lm * (r1 + gamma * np.max(Q[s1]) - Q[s0, a0])   # (5.3)
        if done or truncated:
            return
        s0 = s1

def learn(episodes, ticks):
    global epsilon
    for episode in range(episodes):
        run_episode(ticks)
        epsilon *= decay                   # становимся жаднее
        if epsilon < eps2: epsilon = 0

Это типичный онлайн-метод: обучение происходит на каждой новой порции данных. Почему это работает? Целевая величина \(r_{t+1} + \gamma\max_a Q(s_{t+1}, a)\) — несмещённая выборочная оценка оптимального оператора Беллмана: её условное ожидание при данных \((s, a)\) — в точности правая часть (5.1). Неподвижная точка оператора — \(Q^*\), и в конечных MDP Q-learning сходится к \(Q^*\) почти наверное, если каждая пара \((s,a)\) посещается бесконечно часто, а шаги удовлетворяют условиям Роббинса–Монро (конспект 4, формула (4.12)).

Обратите внимание на тонкость: действия выбирает ε-жадная политика, а в цели (5.3) стоит максимум — как если бы дальше агент действовал жадно, чего на самом деле нет (при \(\varepsilon > 0\)). Q-функция оценивает одну политику, действуя по другой — это и есть off-policy обучение (конспект 4, раздел 2) без всякой важностной выборки: одношаговой цели хватает знания одного перехода.

3. SARSA и Expected SARSA

Аналогичная процедура без максимума называется SARSA — по пятёрке \((S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})\), задействованной в обновлении: в цели стоит Q того действия, которое ε-жадная политика фактически выбрала в следующем состоянии:

\[ Q(s_t, a_t) \;\leftarrow\; Q(s_t, a_t) + \lambda \Bigl[ r_{t+1} + \gamma\, Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t) \Bigr]. \tag{5.4}\]

def run_episode(ticks=1000):
    s0, _ = env.reset()
    a0 = policy(s0)                        # действие выбирается заранее
    for _ in range(ticks):
        s1, r1, done, truncated, _ = env.step(a0)
        a1 = policy(s1)                    # фактическое следующее действие
        Q[s0, a0] += lm * (r1 + gamma * Q[s1, a1] - Q[s0, a0])       # (5.4)
        if done or truncated:
            return
        s0, a0 = s1, a1

При \(\varepsilon = 0\) методы совпадают: \(Q(s_{t+1}, a_{t+1}) = \max_a Q(s_{t+1}, a)\). При \(\varepsilon > 0\) различие тонкое, но важное: SARSA — on-policy, его Q-функция оценивает ту же ε-жадную политику, что выбирает действия, — включая её случайные выходки. Сводка из лекции курса:

свойство	SARSA	Q-learning
цель обновления	r + γ·Q(s′, a′)	r + γ·max_a Q(s′, a)
тип метода	on-policy	off-policy
что предполагается о будущем	реальное следующее действие (с разведкой)	жадное продолжение
к чему сходится	Q^π текущей политики	сразу к Q*
поведение при разведке	осторожнее	оптимистичнее

Различие проявляется в средах с коротким рискованным и длинным безопасным путями: SARSA учитывает, что случайная разведка может столкнуть с обрыва, и выбирает безопасный маршрут; Q-learning верит в жадное будущее и идёт по краю.

Промежуточный вариант — Expected SARSA: вместо случайного \(a_{t+1}\) в цели стоит ожидание по политике:

\[ Q(s_t, a_t) \;\leftarrow\; Q(s_t, a_t) + \lambda \Bigl[ r_{t+1} + \gamma \sum_{a'} \pi(a' | s_{t+1})\, Q(s_{t+1}, a') - Q(s_t, a_t) \Bigr]. \tag{5.5}\]

Метод остаётся on-policy, но целевая величина не содержит случайности выбора \(a_{t+1}\) — её дисперсия ниже, чем у SARSA.

Типичная ошибка Пишут SARSA, но в цель подставляют max вместо фактического a′ — и незаметно получают Q-learning. Или наоборот: выбирают a′ для цели, а действием в среде делают другое. В SARSA действие a₁ обязано быть одним и тем же в двух местах: в обновлении (5.4) и в следующем шаге среды — потому он и называется по пятёрке S-A-R-S-A.

4. Если модель известна: итерационный поиск политики

Q-learning и SARSA хороши тем, что не требуют модели среды. Когда модель есть, работает прямая реализация GPI из конспекта 4 — итерационный поиск политики (англ. policy iteration), чередующий два этапа:

Оценка политики: итерации \(V_{k+1}(s) = \sum_{s',r} p(s', r|s, \pi(s)) [r + \gamma V_k(s')]\) до стабилизации — это оператор Беллмана из конспекта 3 (тренажёр «двигатель»); работает и «in-place», когда для части состояний уже используются обновлённые значения;
Улучшение политики: \(\pi(s) = \arg\max_a \sum_{s',r} p(s', r|s, a) [r + \gamma V(s')]\) — жадный шаг, законный по теореме об улучшении (конспект 4).

Повторять, пока политика не перестанет меняться. В конечном MDP политик конечное число, и каждая итерация строго улучшает — алгоритм останавливается на оптимальной за конечное число шагов.

5. Практика: FrozenLake

Вернёмся к среде из конспекта 1 во всех деталях. Карта 4×4, старт в ячейке 0, подарок в 15, проруби в 5, 7, 11, 12. Гномик иногда путает направление — такое бывает со всеми, особенно после хорошего празднования дня рождения: с вероятностью 1/3 идёт куда планирует, и с вероятностями по 1/3 — в каждое из перпендикулярных направлений; при попытке выйти за карту остаётся на месте (или его шатнёт вбок). Награда — только 1 за достижение цели:

Карта FrozenLake 4 на 4 с нумерацией ячеек, прорубями, гномом на старте и подарком в углу; роза направлений действий — Нумерация состояний и действий (0: ←, 1: ↓, 2: →, 3: ↑)

Та же карта со стрелками оптимальной политики в каждой ячейке — Оптимальная политика

Из конспекта преподавателя

Оптимальная политика выглядит неожиданно — стрелки часто направлены не к цели. Разберём состояние 6 (между двумя прорубями). Пойти «вниз» (к цели) удастся лишь с вероятностью 1/3, а с вероятностью 2/3 гнома снесёт в одну из соседних прорубей. А при движении «влево» в прорубь он попадёт с вероятностью только 1/3, и с вероятностью 1/3 его качнёт вниз — куда и нужно. Оптимально здесь идти влево! Следуя этой политике, гном гарантированно (хотя и с возвратами) проходит ячейки 0, 4, 8, 9 — прижимаясь к безопасной стене.

Ценности оптимальной политики при \(\gamma = 1\) считаются из вероятностных соображений: например, для стартового состояния \(V_0 = \tfrac13 V_0 + \tfrac13 V_0 + \tfrac13 V_4\), для предцелевого \(V_{14} = \tfrac13 V_{14} + \tfrac13 V_{13} + \tfrac13 (1 + 0)\). Решение всей системы даёт (в семнадцатых долях):

\[ V^*(s) = \frac{1}{17}\begin{pmatrix} 14 & 14 & 14 & 14\\ 14 & 0 & 9 & 0\\ 14 & 14 & 13 & 0\\ 0 & 15 & 16 & 0 \end{pmatrix} \tag{5.6}\]

— вероятность добраться до подарка со старта равна \(14/17 \approx 0{,}8235\).

Оба метода справляются с задачей примерно за 10 000 эпизодов, но гиперпараметры критичны: при \(\gamma = 1\) обучение неустойчиво, при малых decays (слишком быстрое выключение разведки) — не сходится вовсе. Причина видна из устройства награды: пока агент ни разу не достиг цели, вся таблица \(Q\) — нули, и «жадность» бессмысленна; только после первого успеха ценность начинает обратным ходом распространяться по таблице от цели к старту — по одному шагу за успешный эпизод, ровно как в TD-обновлении:

Четыре кривые обучения при разных гиперпараметрах: устойчивый рост при gamma 0.99, шумные и падающие кривые при gamma равном единице и при быстром распаде epsilon — Кривые обучения при разных γ, λ и параметрах ε-распада. Из конспекта преподавателя

Визуализация после обучения: таблицы Q по четырём действиям, функция V и итоговая политика; средняя награда 0.74 — Итог обучения: Q(s, a) по действиям, V(s) и политика; средняя награда 0,74. Из конспекта преподавателя

Типичная средняя награда обученного агента — около 0,74, и в источнике вопрос, почему она ниже теоретической \(14/17 \approx 0{,}82\), оставлен открытым. Ответ находится численно: всё дело в лимите длины эпизода. В Gymnasium эпизод FrozenLake обрезается на 100 шагах, а оптимальная политика «прижимания к стене» часто топчется дольше. Моделирование оптимальной политики (200 000 эпизодов) даёт вероятность успеха 0,740 при лимите 100 шагов, 0,818 при лимите 200 и 0,824 при снятии лимита — предел в точности \(14/17\). Обученный агент выжимает из усечённой среды всё возможное.

Тренажёр: Q-обучение на FrozenLake вживую

метод:

кривая обучения

Скользкий FrozenLake, гиперпараметры из конспекта преподавателя: λ = 0.1, γ = 0.95, ε-распад с 1.0 до 0.001 за 5000 эпизодов. В ячейках — стрелка жадного действия и V(s) = max Q; заливка темнеет с ростом ценности. Нажимайте «+2000 эпизодов» и наблюдайте обратное распространение ценности от подарка к старту и рождение «неожиданной» политики прижимания к стене. После 10 000 эпизодов средняя награда ≈ 0.749 (Q-learning) и 0.800 (SARSA) — сверено с независимой репликой на Python; сравните выученные стрелки с оптимальной политикой на рисунке выше.

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

Типичная ошибка Ставят γ = 1 «для честного учёта всей награды». В стохастических средах с зацикливаниями это делает обучение неустойчивым (видно на кривых выше): дисконт γ < 1 не только отражает неопределённость будущего, но и стягивает оператор Беллмана (конспект 3) — при γ = 1 гарантия сжатия исчезает.

6. Переоценка максимума

У Q-learning есть системный изъян: операция \(\max\) по шумным оценкам завышает цель. Для любых случайных оценок \(\hat{Q}(s', a)\):

\[ \Bigl\langle \max_a \hat{Q}(s', a) \Bigr\rangle \;\ge\; \max_a \Bigl\langle \hat{Q}(s', a) \Bigr\rangle, \tag{5.7}\]

поскольку \(\max_a \hat Q \ge \hat Q(s', b)\) для каждого \(b\), а значит, и в среднем \(\langle\max\rangle \ge \langle \hat Q(s',b)\rangle\) для каждого \(b\) — в том числе для лучшего. Даже если каждая оценка несмещённа, максимум по ним смещён вверх: шумно завышенное действие охотно выбирается максимумом, и его завышение попадает в цель обновления. Эффект накапливается по цепочке бутстрапа и порождает систематический оптимизм Q-значений. Лекарство — разделить выбор действия и оценку его ценности между двумя независимыми таблицами — называется Double Q-learning; его глубокая версия Double DQN ждёт нас в конспекте 8.

Контрольные вопросы

Вместо усреднения по действиям с весами политики в нём стоит максимум — жадный выбор. Из-за max система нелинейна, матричное решение (конспект 3, формула (3.16)) неприменимо; работают итерации сжимающего оптимального оператора или их выборочная версия — Q-learning.
В итерациях (5.2) при известной модели стоит усреднение Σ p(s',r|s,a)[r + γ max Q(s',·)]. Без модели усреднение заменяется одним наблюдённым переходом (s, a → s', r): цель r + γ max Q(s',·), обновление Q += λ(цель − Q) — формула (5.3). Условное ожидание цели равно правой части (5.1), поэтому неподвижная точка — Q*.
Действия выбирает ε-жадная (поведенческая) политика, а цель обновления построена для жадной (целевой): max предполагает жадное продолжение, которого при ε > 0 не происходит. Коррекция распределений не нужна, потому что цель одношаговая: для неё достаточно знать один переход, а он не зависит от будущих действий политики.
SARSA ставит в цель Q фактически выбранного следующего действия (on-policy, сходится к Q^π ε-жадной политики), Q-learning — максимум (off-policy, сходится к Q*). При ε = 0 они совпадают. Различие видно в средах с рискованным коротким и безопасным длинным путями: SARSA учитывает случайные шаги разведки и осторожничает, Q-learning оптимистично идёт по краю.
Из-за скольжения: «вниз» исполняется с вероятностью 1/3, а с вероятностью 2/3 гнома сносит в соседние проруби. «Влево» ведёт в прорубь лишь с вероятностью 1/3, и с вероятностью 1/3 качнёт вниз — куда и нужно. Оптимальная политика учитывает динамику среды, а не геометрию карты.
Из-за лимита длины эпизода: FrozenLake в Gymnasium обрезается на 100 шагах, а оптимальная политика «прижимания к стене» часто требует больше. Моделирование даёт успех 0,740 при лимите 100, 0,818 при 200 и 0,824 без лимита — предел равен 14/17.
max_a Q̂ ≥ Q̂(s',b) для любого b; взяв ожидание, получаем ⟨max Q̂⟩ ≥ ⟨Q̂(s',b)⟩ для каждого b, в частности для максимального — значит, ⟨max Q̂⟩ ≥ max⟨Q̂⟩. Максимум по шумным оценкам систематически завышен; через цель (5.3) и бутстрап оптимизм накапливается. Решение — Double Q-learning: выбор действия и оценку его ценности разносят по двум таблицам.