Монте-Карло, TD и Q-learning

Зачем это нужно

В прошлом уроке мы знали правила среды: вероятности переходов $P$ и награды $R$. Тогда оптимальную политику можно вычислить, не сделав ни одного хода. В жизни правил обычно нет. Никто не выдаст таблицу вероятностей для пользователя чат-бота или для соперника в игре. Остаётся пробовать, ошибаться и делать выводы. Это обучение без модели средыобучение без модели среды (model-free RL)EN model-free reinforcement learningАгент не знает вероятностей переходов и наград и учится только на собственном опыте. (model-free RL).

Методы этого урока — классика, на которой построен «словарь» всего RL. В языковых моделях Q-learning почти не применяют, но слова бутстрэп, TD-ошибка, исследование, on-policy и off-policy встречаются в каждой статье про PPO и GRPO. TD-ошибка станет кирпичиком GAE в следующем уроке, а off-policy — причиной, по которой в формуле PPO появляется отношение вероятностей $\pi_\theta / \pi_{\text{old}}$.

Что посмотреть параллельно

• Практический курс: Hugging Face Deep RL Course, юнит 2 «Introduction to Q-Learning» (Монте-Карло против TD, Q-learning, ноутбук с FrozenLake) и юнит 3 (DQN). Текст — на huggingface.co/learn/deep-rl-course; русского перевода нет, но английский там простой.
• Видео: лекции DeepMind × UCL 2021, лекции 5 и 6 (model-free prediction и control).
• По-русски: Practical_RL, недели week03_model_free и week04_approx_rl.

Монте-Карло: сыграть и усреднить

Напомним: $V^\pi(s)$ — средняя отдача из состояния $s$. Раз среднее, его можно оценить выборкой — сыграть много эпизодов и усреднить фактические отдачи. Это метод Монте-Карлометод Монте-Карло (в RL)EN Monte Carlo methodОценка ценности усреднением фактических отдач законченных эпизодов. Без смещения, но с большим разбросом., тот же закон больших чисел, что в уроке 1.3.1.

Пример на коридоре из прошлого урока (политика 50/50, $\gamma = 0.9$). Три эпизода из $A$:

Эпизод	Путь	Награды	$G$ из $A$
1	$A \to B \to$ выход	$[0, 1]$	$0.9$
2	$A \to A \to B \to$ выход	$[0, 0, 1]$	$0.81$
3	$A \to B \to A \to B \to$ выход	$[0, 0, 0, 1]$	$0.729$

Оценка $V(A) \approx (0.9 + 0.81 + 0.729) / 3 = 0.813$. Точное значение — 0.647: в этих трёх эпизодах нам повезло, агент быстро нашёл выход. С ростом числа эпизодов среднее приближается к истине.

Чтобы не хранить все отдачи, среднее считают «на ходу»: $V(s) \leftarrow V(s) + \alpha\,\big(G_t - V(s)\big)$. При $\alpha = 1/N$ это точное среднее, при постоянном $\alpha$ — среднее с бо́льшим весом у свежих эпизодов.

Плюс Монте-Карло: оценка честная, без смещения — она опирается только на то, что действительно произошло. Минус: нужно ждать конца эпизода, а отдача — сумма многих случайных наград, поэтому разброс большой.

TD: учиться на каждом шаге

Представьте, что вы едете домой и прогнозируете время в пути: «30 минут». Через 10 минут вы встали в пробку и думаете: «ещё минут 25». Новый прогноз всего пути — 35 минут, и исправить первоначальный можно уже сейчас, не дожидаясь приезда. Это идея обучения на временных разностяхобучение на временных разностях (TD)EN temporal-difference learningОбновление оценки после каждого шага: V(s) ← V(s) + α[r + γV(s′) − V(s)]. (temporal difference, TD).

В уравнении Беллмана $V(s) = \mathbb{E}[r + \gamma V(s')]$. Сделав один шаг, мы видим конкретные $r$ и $s'$ и можем подвинуть $V(s)$ к цели $r + \gamma V(s')$:

$$V(s) \leftarrow V(s) + \alpha\, \delta, \qquad \delta = r + \gamma\, V(s') - V(s)$$

Как читать: $\delta$ — TD-ошибкаTD-ошибкаEN TD errorδ = r + γV(s′) − V(s): насколько после шага дела оказались лучше (или хуже), чем ожидалось., «сюрприз» этого шага: насколько «награда плюс ценность того, куда попали» больше или меньше того, что мы ожидали в $s$. $\alpha$ — шаг обучения, как learning rate в градиентном спуске (урок 1.4.1). Если $s'$ конечное, будущего нет и цель — просто $r$.

Пример. Текущие оценки $V(A) = 0.5$, $V(B) = 0.8$. Агент шагнул из $A$ в $B$, награда 0, $\gamma = 0.9$, $\alpha = 0.1$. Ошибка $\delta = 0 + 0.9 \cdot 0.8 - 0.5 = 0.22$ — в $B$ оказалось лучше, чем мы думали про $A$. Новая оценка $V(A) = 0.5 + 0.1 \cdot 0.22 = 0.522$.

Главное слово: цель $r + \gamma V(s')$ содержит нашу же оценку $V(s')$. Обновлять оценку с опорой на другую оценку называют бутстрэпомбутстрэп (в RL)EN bootstrappingОбновление оценки с опорой на другую собственную оценку (V(s′) или max Q(s′, ·)), а не на полную фактическую отдачу. Не путать с бутстрэп-выборкой из статистики. (bootstrapping — «вытянуть себя за шнурки ботинок»). Не путайте с бутстрэп-выборкой из статистики (уроки 1.3.4 и 2.3.1): слово то же, смысл другой.

Смещение и разброс: Монте-Карло против TD

Это знакомый компромисс из урока 2.1.2, только про оценки ценности:

	Монте-Карло	TD(0)
Цель обновления	фактическая отдача $G_t$	$r_t + \gamma V(s_{t+1})$
Когда обновляем	в конце эпизода	после каждого шага
Смещениекомпромисс смещения и разбросаEN bias–variance tradeoff	нет: $\mathbb{E}[G_t] = V^\pi(s_t)$	есть, пока $V(s_{t+1})$ неточна
Разброс	большой: сумма многих случайных наград	маленький: одна случайная награда и один переход
Бесконечные задачи	не подходит	подходит

Между ними — целое семейство: $n$-шаговая цель берёт $n$ настоящих наград, а дальше доверяется оценке:

$$G_t^{(n)} = r_t + \gamma r_{t+1} + \dots + \gamma^{n-1} r_{t+n-1} + \gamma^n V(s_{t+n})$$

При $n = 1$ это TD, при $n$ до конца эпизода — Монте-Карло. В следующем уроке GAE возьмёт взвешенное среднее всех $n$-шаговых оценок с одним параметром $\lambda$ — тем самым, что стоит в конфигах PPO для LLM.

Исследование и использование

Оценивать политику мало, её нужно улучшать. И здесь появляется новая проблема. Вы в незнакомом городе нашли неплохое кафе. Ходить туда каждый день — использование (exploitation): надёжно, но вы никогда не узнаете, что за углом кафе лучше. Каждый день пробовать новое — исследование (exploration): узнаете много, но часто будете есть плохо. Это компромисс исследования и использованияисследование и использованиеEN exploration vs. exploitationКомпромисс между «пробовать новое, чтобы узнать больше» и «делать то, что сейчас кажется лучшим»..

В чистом виде он живёт в задаче многорукого бандитамногорукий бандитEN multi-armed banditПростейшая задача RL — K «ручек» с неизвестными средними наградами, один шаг на эпизод.: $K$ игровых автоматов с неизвестными средними выигрышами, на каждом шаге дёргаем одну ручку. Это MDP из одного состояния. Простейшее решение — ε-жадная стратегияε-жадная стратегияEN ε-greedy policyС вероятностью ε — случайное действие, иначе — действие с наибольшей оценкой Q.:

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

Лучшее действие выбирается с вероятностью $1 - \varepsilon + \varepsilon/|A|$: при $\varepsilon = 0.1$ и четырёх действиях это $0.9 + 0.025 = 0.925$, каждое из остальных — 0.025. Часто $\varepsilon$ уменьшают со временем: сначала много исследуем, потом в основном используем.

Проверим на трёх автоматах с вероятностями выигрыша 0.3, 0.5 и 0.7 (агент их не знает):

import numpy as np

means = np.array([0.3, 0.5, 0.7])          # вероятность выигрыша у трёх «автоматов» (агент её не знает)


def play(eps, steps=1000, seed=0):
    rng = np.random.default_rng(seed)
    Q, N = np.zeros(3), np.zeros(3)         # оценки и счётчики нажатий
    total = 0.0
    for t in range(steps):
        if rng.random() < eps:
            a = int(rng.integers(3))                            # исследуем
        else:
            a = int(rng.choice(np.flatnonzero(Q == Q.max())))   # используем (ничьи — случайно)
        r = float(rng.random() < means[a])                      # награда 1 или 0
        N[a] += 1
        Q[a] += (r - Q[a]) / N[a]                               # бегущее среднее наград ручки a
        total += r
    return total / steps


for eps in [0.0, 0.01, 0.1, 0.3]:
    avg = np.mean([play(eps, seed=s) for s in range(200)])
    print(f"ε = {eps:<4}  средняя награда за шаг {avg:.3f}   (лучшее возможное 0.700)")

ε = 0.0   средняя награда за шаг 0.555   (лучшее возможное 0.700)
ε = 0.01  средняя награда за шаг 0.630   (лучшее возможное 0.700)
ε = 0.1   средняя награда за шаг 0.666   (лучшее возможное 0.700)
ε = 0.3   средняя награда за шаг 0.636   (лучшее возможное 0.700)

Чисто жадный агент ($\varepsilon = 0$) часто «залипает» на первой ручке, которая повезла. Слишком любопытный ($\varepsilon = 0.3$) тратит много шагов впустую. Лучше всего — немного исследования.

Исследование у языковых моделей

У LLM нет ε-жадности, но та же проблема есть. Исследование там — это сэмплирование с температурой (урок 4.1.3), группа из нескольких ответов на промпт в GRPO и энтропийный бонус в PPO (урок 6.0.3). А на многоруком бандите в уроке 6.3.1 вы обучите политику градиентом — тем же методом, которым учат LLM.

SARSA и Q-learning: учимся действовать

Для улучшения политики удобнее оценивать не $V$, а $Q(s, a)$: тогда лучшее действие — просто $\arg\max_a Q(s, a)$, модель среды не нужна. Применим TD-идею к $Q$.

SARSASARSAEN SARSA (state–action–reward–state–action)Как Q-learning, но в цели Q(s′, a′) действия, которое агент действительно выбрал. On-policy. (по буквам перехода: $s, a, r, s', a'$):

$$Q(s, a) \leftarrow Q(s, a) + \alpha \big[\, r + \gamma\, Q(s', a') - Q(s, a) \,\big]$$

где $a'$ — действие, которое агент действительно выберет в $s'$ своей ε-жадной политикой.

Q-learningQ-learningEN Q-learningQ(s,a) ← Q(s,a) + α[r + γ max_a′ Q(s′,a′) − Q(s,a)]. Off-policy: учит Q* при любом поведении. (Уоткинс, 1989) отличается одним символом — максимумом:

$$Q(s, a) \leftarrow Q(s, a) + \alpha \big[\, r + \gamma \max_{a'} Q(s', a') - Q(s, a) \,\big]$$

Как читать Q-learning: «награда плюс ценность лучшего действия в следующем состоянии» — это правая часть уравнения оптимальности Беллмана из прошлого урока, оценённая по одному переходу. Поэтому Q-learning сходится к $Q^*$.

Пример. $Q(s', \cdot) = [0.5,\ 0.8]$, награда $r = 0$, $\gamma = 0.9$, $\alpha = 0.1$, $Q(s, a) = 0$. Цель Q-learning: $0 + 0.9 \cdot 0.8 = 0.72$, TD-ошибка 0.72, новое $Q(s, a) = 0.072$. Если ε-жадный агент случайно выбрал в $s'$ первое действие, цель SARSA — $0.9 \cdot 0.5 = 0.45$, новое $Q(s, a) = 0.045$.

Алгоритм для обоих:

1. Таблица $Q$ из нулей. Для каждого эпизода: $s$ = старт, $a$ = ε-жадно по $Q(s, \cdot)$.
2. Сделать шаг: получить $r$ и $s'$. Выбрать $a'$ ε-жадно по $Q(s', \cdot)$.
3. Обновить $Q(s, a)$ по формуле SARSA или Q-learning. Если $s'$ конечное — цель равна $r$.
4. $s, a \leftarrow s', a'$. Повторять до конца эпизода.

On-policy и off-policy

SARSA учит ценность той самой политики, которой действует, — ε-жадной, со всеми её случайными шагами. Это on-policyon-policy (обучение на данных текущей политики)EN on-policyПротивоположность — off-policy, обучение на данных другой политики. обучение. Q-learning ведёт себя ε-жадно, а учит ценность другой политики — чисто жадной. Это off-policyoff-policy (обучение на данных другой политики)EN off-policyПолитика, которую учим, отличается от той, что собирала данные. Пример — Q-learning; в PPO и GRPO — поправка π/π_old.: данные собирает одна политика, учим другую.

Разницу видно на классическом примере 6.6 из Саттона и Барто — «прогулке по обрыву». Поле 4×12, старт и цель в нижних углах, между ними обрыв: шаг туда — награда −100 и конец эпизода; каждый обычный шаг −1. Мы прогнали оба алгоритма по 500 эпизодов ($\varepsilon = 0.1$, $\alpha = 0.5$, три разных seed):

	Q-learning	SARSA
Жадный путь после обучения	13 шагов по самому краю обрыва (оптимум)	17 шагов, на два ряда выше
Средняя отдача за последние 100 эпизодов обучения	от −33 до −40	от −22 до −26

Q-learning выучил кратчайший путь, но во время обучения его ε-жадные случайные шаги у края то и дело сбрасывают агента вниз. SARSA «знает», что сам иногда делает случайный шаг, и прокладывает путь подальше от края. Это вы повторите в домашней работе.

Почему это важно для LLM. В PPO и GRPO ответы генерирует политика $\pi_{\text{old}}$, а потом по этому же батчу делают несколько шагов оптимизации — после первого шага модель уже немного другая, и данные становятся «чуть-чуть off-policy». Поправку на это даёт отношение вероятностей $\pi_\theta / \pi_{\text{old}}$ (урок 6.0.3). А в асинхронном RL для агентов (урок 8.3.4) данные бывают устаревшими на несколько версий политики — и off-policy-поправки становятся обязательными.

От таблицы к нейросети: DQN

Таблица $Q$ работает, пока состояний немного. У игры Atari состояние — картинка экрана, вариантов астрономически много. Решение — приближать $Q(s, a)$ нейросетью $Q(s, a; \theta)$: на вход состояние, на выход по числу на каждое действие. Учить её регрессией к TD-цели:

$$\mathcal{L}(\theta) = \big(\, r + \gamma \max_{a'} Q(s', a'; \theta^-) - Q(s, a; \theta) \,\big)^2$$

Наивная версия расходится, и DQNDQN (глубокая Q-сеть)EN deep Q-network (DQN)Mnih и др., 2015 — Q-learning с нейросетью, буфером воспроизведения и целевой сетью; играл в Atari по пикселям. (Mnih et al., Nature, 2015) добавил два приёма:

• Буфер воспроизведениябуфер воспроизведения (replay buffer)EN experience replay bufferХранилище прошлых переходов (s, a, r, s′), из которого сэмплируют случайные мини-батчи. (replay buffer) хранит десятки тысяч прошлых переходов $(s, a, r, s')$, а сеть учится на случайных мини-батчах из него. Соседние кадры игры почти одинаковы, и без перемешивания градиенты сильно коррелированы. Заодно каждый переход используется много раз. Учиться на старых переходах можно, потому что Q-learning — off-policy.
• Целевая сетьцелевая сеть (target network)EN target networkЗамороженная копия Q-сети для вычисления цели r + γ max Q; её веса обновляют редко. $\theta^-$ — копия сети, которую обновляют редко (раз в несколько тысяч шагов). Иначе цель $r + \gamma \max Q$ сдвигается при каждом шаге вместе с $\theta$, и сеть гоняется за собственным хвостом.

По словам авторов, один и тот же алгоритм с одной архитектурой и одними гиперпараметрами играл в 49 игр Atari по пикселям экрана на уровне профессионального тестировщика игр. Это была первая громкая победа глубокого RL.

Честно о Q-learning и LLM

В RL для языковых моделей Q-learning и DQN почти не используют. Политика LLM уже готова после претрейна и SFT — это softmax над словарём, и её удобно улучшать градиентом политики (следующий урок). Учить с нуля $Q$ для 150 тысяч токенов в каждом из бесконечного числа контекстов — гораздо труднее. Но идеи урока — TD-ошибка, бутстрэп, исследование, off-policy, обучение на старых данных — вы встретите в каждой статье про RLHF и рассуждающие модели.

Практика

Задание: Q-learning и SARSA на скользком озере

Среда — «скользкое озеро» 4×4 в стиле FrozenLake: S — старт, F — лёд, H — прорубь (эпизод кончается без награды), G — цель (+1). С вероятностью 0.2 агент скользит вбок. Реализуйте ε-жадный выбор со случайным разрешением ничьих, шаги Q-learning и SARSA, цикл обучения с убывающим $\varepsilon$ и оценку жадной политики. Порог — дойти до цели хотя бы в 45% эпизодов. Политика, оптимальная при $\gamma = 0.9$ (как в задании), доходит примерно в 74% случаев: с дисконтом выгоднее идти коротким путём мимо прорубей и иногда соскальзывать, чем долго осторожничать. Политика, которая думает только о доходе до цели, без спешки, дошла бы в ~94% эпизодов за 100 шагов — это снова роль $\gamma$.

Q-learning и SARSA на скользком озереnumpy · нужен интернет7 тестов

import numpy as np


# ── Среда уже готова: «скользкое озеро» 4×4 ─────────────────────────────────
# S — старт, F — лёд, H — прорубь (эпизод кончается, награда 0), G — цель (+1, конец).
# С вероятностью slip агент скользит вбок от выбранного направления (по slip/2 в каждую сторону).
class SlipperyLake:
    MOVES = [(-1, 0), (0, 1), (1, 0), (0, -1)]     # действия: 0 ↑, 1 →, 2 ↓, 3 ←

    def __init__(self, layout=("SFFF", "FHFF", "FFFH", "HFFG"), slip=0.2, max_steps=100, seed=0):
        self.layout, self.slip, self.max_steps = layout, slip, max_steps
        self.H, self.W = len(layout), len(layout[0])
        self.n_states, self.n_actions = self.H * self.W, 4
        self.rng = np.random.default_rng(seed)

    def reset(self):
        self.s, self.t = 0, 0                         # старт — левый верхний угол
        return self.s

    def step(self, a):
        u = self.rng.random()
        if u < self.slip / 2:
            a = (a + 1) % 4                            # поскользнулись вправо от направления
        elif u < self.slip:
            a = (a + 3) % 4                            # … или влево
        r, c = divmod(self.s, self.W)
        nr = min(max(r + self.MOVES[a][0], 0), self.H - 1)
        nc = min(max(c + self.MOVES[a][1], 0), self.W - 1)
        self.s, self.t = nr * self.W + nc, self.t + 1
        cell = self.layout[nr][nc]
        reward = 1.0 if cell == "G" else 0.0
        done = cell in "GH" or self.t >= self.max_steps
        return self.s, reward, done


# ── Ваша часть ──────────────────────────────────────────────────────────────

def epsilon_greedy(q_row, eps, rng):
    """ε-жадный выбор действия по строке Q[s].

    С вероятностью eps (проверка rng.random() < eps) — случайное действие rng.integers(len(q_row)).
    Иначе — действие с наибольшей оценкой; если таких несколько — случайное из них
    (np.flatnonzero(q_row == q_row.max()) и rng.choice). Вернуть int.
    """
    # TODO: ваш код
    ...


def q_learning_update(Q, s, a, r, s_next, done, alpha, gamma):
    """Шаг Q-learning, Q меняется НА МЕСТЕ:  Q[s,a] += alpha * (target − Q[s,a]).

    target = r, если done (у конечного состояния нет будущего),
    иначе target = r + gamma * max_a' Q[s_next, a'].  Вернуть TD-ошибку target − Q[s,a] (до обновления).
    """
    # TODO: ваш код
    ...


def sarsa_update(Q, s, a, r, s_next, a_next, done, alpha, gamma):
    """То же, что Q-learning, но в цели Q[s_next, a_next] — оценка действия, которое агент
    действительно выбрал следующим (а не максимум). Вернуть TD-ошибку."""
    # TODO: ваш код
    ...


def train(env, method="q", episodes=1000, alpha=0.1, gamma=0.9, eps_start=1.0, eps_end=0.05, seed=0):
    """Обучить таблицу Q (нули [n_states, n_actions]). Вернуть (Q, wins), wins[i] — награда i-го эпизода.

    rng = np.random.default_rng(seed). ε убывает линейно от eps_start до eps_end за первые 70% эпизодов:
        eps = eps_end + (eps_start − eps_end) * max(0, 1 − ep / (0.7 * episodes))
    Эпизод: s = env.reset(); a = epsilon_greedy(...); пока не done:
        s_next, r, done = env.step(a); a_next = epsilon_greedy(Q[s_next], ...);
        обновление (method "q" — q_learning_update, иначе sarsa_update); s, a = s_next, a_next.
    """
    # TODO: ваш код
    ...


def greedy_success_rate(env, Q, episodes=300):
    """Доля эпизодов, дошедших до цели, если всегда брать int(np.argmax(Q[s])) (без исследования)."""
    # TODO: ваш код
    ...


# Проверьте себя кнопкой «Запустить»
for method in ["q", "sarsa"]:
    out = train(SlipperyLake(seed=0), method)
    if out is not None:
        Q, wins = out
        rate = greedy_success_rate(SlipperyLake(seed=1), Q, episodes=200)
        print(f"{method:5}: успехов за последние 200 эпизодов обучения {wins[-200:].mean():.2f}, жадная политика {rate:.2f}")
        cells = "".join(SlipperyLake().layout)
        print("\n".join(" ".join(ch if ch in "HG" else "↑→↓←"[Q[4 * r + c].argmax()]
                                for c, ch in enumerate(cells[4 * r:4 * r + 4])) for r in range(4)))

ЗапуститьПроверитьПодсказкаСбросить

После решения нажмите «Запустить»: вы увидите долю успехов и стрелки обеих политик. Сравните, где SARSA обходит проруби осторожнее.

Локально: DQN на CartPole

CartPole — классическая задача: удержать шест на тележке, толкая её влево или вправо. Состояние — 4 числа (положение и скорость тележки, угол и угловая скорость шеста), награда +1 за каждый шаг, эпизод обрывается на 500 шагах. Нужны pip install gymnasium и PyTorch из ступени 3. Видеокарта не нужна: сеть крошечная, всё идёт на CPU.

import random
from collections import deque

import gymnasium as gym
import numpy as np
import torch
import torch.nn as nn

torch.manual_seed(0)
random.seed(0)
env = gym.make("CartPole-v1")
n_obs, n_act = env.observation_space.shape[0], env.action_space.n   # 4 числа состояния, 2 действия


def make_net():
    return nn.Sequential(nn.Linear(n_obs, 128), nn.ReLU(), nn.Linear(128, 128), nn.ReLU(), nn.Linear(128, n_act))


q_net = make_net()                                   # Q(s, ·; θ) — обучаем
target_net = make_net()                              # Q(s, ·; θ⁻) — замороженная копия для цели
target_net.load_state_dict(q_net.state_dict())
opt = torch.optim.Adam(q_net.parameters(), lr=1e-3)
buffer = deque(maxlen=50_000)                        # replay buffer: последние 50 тыс. переходов
gamma, batch_size, total_steps = 0.99, 64, 0
history = []                                         # отдачи всех эпизодов

for episode in range(1, 401):
    s, _ = env.reset(seed=episode)
    ep_return, done = 0.0, False
    while not done:
        eps = max(0.05, 1.0 - total_steps / 10_000)  # ε-жадность: от 1.0 к 0.05 за 10 тыс. шагов
        if random.random() < eps:
            a = random.randrange(n_act)
        else:
            with torch.no_grad():
                a = int(q_net(torch.as_tensor(s, dtype=torch.float32)).argmax())
        s2, r, terminated, truncated, _ = env.step(a)
        done = terminated or truncated
        buffer.append((s, a, r, s2, float(terminated)))   # обрыв по лимиту — не конец «по-настоящему»
        s, ep_return, total_steps = s2, ep_return + r, total_steps + 1

        if len(buffer) >= 1000:                      # учимся на случайном мини-батче из прошлого опыта
            batch = random.sample(buffer, batch_size)
            S, A, R, S2, T = (torch.as_tensor(np.array(x), dtype=torch.float32) for x in zip(*batch))
            q = q_net(S).gather(1, A.long()[:, None])[:, 0]          # Q(s, a)
            with torch.no_grad():                                     # цель r + γ max Q_target(s′, ·)
                target = R + gamma * (1 - T) * target_net(S2).max(1).values
            loss = nn.functional.smooth_l1_loss(q, target)            # Huber loss — устойчивее MSE
            opt.zero_grad()
            loss.backward()
            opt.step()
        if total_steps % 500 == 0:                   # раз в 500 шагов обновляем целевую сеть
            target_net.load_state_dict(q_net.state_dict())
    history.append(ep_return)
    if episode % 50 == 0:
        print(f"эпизод {episode:3d}  шагов всего {total_steps:6d}  ε = {eps:.2f}  "
              f"средняя отдача за 50 эпизодов {np.mean(history[-50:]):5.1f}")

Вывод (PyTorch 2.x, gymnasium 1.x, один поток CPU; на другой версии числа будут другими, а у DQN — заметно):

эпизод  50  шагов всего   1169  ε = 0.88  средняя отдача за 50 эпизодов  23.4
эпизод 100  шагов всего   2173  ε = 0.78  средняя отдача за 50 эпизодов  20.1
эпизод 150  шагов всего   4282  ε = 0.57  средняя отдача за 50 эпизодов  42.2
эпизод 200  шагов всего   8422  ε = 0.16  средняя отдача за 50 эпизодов  82.8
эпизод 250  шагов всего  15982  ε = 0.05  средняя отдача за 50 эпизодов 151.2
эпизод 300  шагов всего  25670  ε = 0.05  средняя отдача за 50 эпизодов 193.8
эпизод 350  шагов всего  39752  ε = 0.05  средняя отдача за 50 эпизодов 281.6
эпизод 400  шагов всего  44813  ε = 0.05  средняя отдача за 50 эпизодов 101.2

Пока $\varepsilon$ велико, агент действует почти случайно (отдача около 20). Потом начинается обучение, и к 350-му эпизоду средняя отдача достигает 280. А дальше — провал до 100. Это не ошибка в коде, а известная болезнь DQN: бутстрэп к собственным оценкам, off-policy-данные и нейросеть вместе делают обучение неустойчивым, и выученная политика может «забыться». Лечат меньшим шагом обучения, Double DQN, мягким обновлением целевой сети и сохранением лучшей модели. Сравните с PPO в следующем уроке: на той же задаче он растёт заметно ровнее. Прогон занимает несколько минут на одном ядре CPU.

Обратите внимание на две детали. В буфер пишется terminated, а не done: если эпизод оборван лимитом в 500 шагов, у состояния есть будущее, и цель должна бутстрэпиться через $V(s')$ — та же тонкость встретится в GAE. И (1 - T) обнуляет будущее только у настоящих конечных состояний (шест упал).

Китайский угол: где учить табличные методы по-китайски

• «Обучение с подкреплением своими руками» (Hands-on-RL, Шанхайский университет Цзяотун, Apache-2.0) — глава 5 «Алгоритмы временных разностей»: Sarsa, n-шаговый Sarsa и Q-learning на той же «прогулке по обрыву» (Cliff Walking), что в нашей домашней работе, с графиками отдачи по эпизодам. Глава 7 — DQN на CartPole, как наш локальный пример.
• easy-rl, «Грибная книга» (Datawhale) — глава 3 «Табличные методы». По словам авторов, она подготовлена по курсу Ли Кэцзяо «Чемпион мира учит обучению с подкреплением с нуля» на платформе Baidu AI Studio, а главы 4–11 книги — по лекциям Ли Хунъи «Глубокое обучение с подкреплением». Названия разделов — готовый словарь: 3.3.1 «Оценка стратегии методом Монте-Карло», 3.3.2 «Временные разности», 3.4.1 «Sarsa: управление по временным разностям с той же стратегией», 3.4.2 «Q-обучение: управление по временным разностям с другой стратегией».

Термины. Model-free по-китайски буквально «свободный от модели», TD — «разность во временном ряду», бутстрэп — «самоподъём». Исследование и использование, replay buffer («воспроизведение опыта») и целевая сеть называются дословно. On-policy и off-policy — «та же стратегия» и «другая стратегия»: политику по-китайски называют стратегией.

Проверь себя

Проверь себя6 вопросов·

1 TD(0): $V(s) = 0.5$, агент получил $r = 1$ и попал в $s'$ с $V(s') = 0.4$; $\gamma = 0.9$, $\alpha = 0.5$. Чему станет равна $V(s)$?

2 ε-жадная стратегия, 5 действий, $\varepsilon = 0.2$. С какой вероятностью выбирается лучшее действие?

3 Какие утверждения верны?Можно выбрать несколько ответов

Монте-Карло обновляет оценку только после конца эпизодаTD(0) использует собственную оценку $V(s')$ в цели — это бутстрэпЦель Монте-Карло не смещена, но имеет больший разброс, чем цель TDTD-методы нельзя применять в бесконечных задачах

4 В $s'$ оценки $Q(s', \cdot) = [1, 3]$, но ε-жадный агент случайно выбрал там действие 0. Награда $r = 0$, $\gamma = 1$. Какие цели обновления у Q-learning и SARSA?

Q-learning: 3, SARSA: 1Q-learning: 1, SARSA: 3Обе: 3Обе: 2

5 Почему на «прогулке по обрыву» SARSA во время обучения получает отдачу выше, чем Q-learning?

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

6 Зачем DQN нужна целевая сеть $\theta^-$?

Чтобы выбирать действия во время игрыЧтобы цель $r + \gamma \max Q$ не менялась при каждом шаге оптимизации и обучение не расходилосьЧтобы хранить прошлые переходыЧтобы считать энтропию политики

Проверить ответы

Итоги

• Без модели среды ценность оценивают по опыту. Монте-Карло усредняет фактические отдачи: без смещения, но шумно и только после конца эпизода. TD(0) обновляет после каждого шага по TD-ошибке $\delta = r + \gamma V(s') - V(s)$, опираясь на собственную оценку (бутстрэп): меньше разброс, есть смещение. Между ними — $n$-шаговые оценки.
• Чтобы найти хорошую политику, агент должен исследовать; простейший способ — ε-жадность с убывающим $\varepsilon$.
• SARSA (on-policy) учит ценность своей ε-жадной политики и осторожнее; Q-learning (off-policy) учит $Q^*$ при любом поведении. Off-policy — ключ к обучению на старых данных и причина поправки $\pi_\theta / \pi_{\text{old}}$ в PPO.
• DQN заменил таблицу нейросетью и стабилизировал обучение буфером воспроизведения и целевой сетью.

Дальше: методы, которые учат саму политику, а не $Q$, — градиент политики, actor-critic, GAE и PPO целиком, и как всё это переносится на языковую модель.