Обучение с подкреплением

Все предыдущие статьи трека решали одну и ту же задачу: есть выборка пар «объект — правильный ответ», нужно найти функцию, которая по объекту предсказывает ответ. Даже кластеризация и снижение размерности, где ответов нет, работали с фиксированным датасетом: данные лежат, модель их читает, ничего не меняется.

Обучение с подкреплением (Reinforcement Learning, RL) ломает эту картину в трёх местах сразу.

1. Правильного ответа никто не знает. Вместо «в этой ситуации нужно было сделать X» среда сообщает лишь «то, что ты сделал, стоило +3». Хорошо это или плохо и что нужно было сделать вместо — вы не узнаете. Обратная связь оценочная (evaluative), а не инструктивная (instructive).
2. Награда отложена. Ход в шахматах приносит 0 очков, а через сорок ходов вы проигрываете. Какой из сорока ходов виноват? Это проблема присвоения заслуг (credit assignment) — центральная трудность RL, которой нет в supervised learning.
3. Данные порождает сам агент. Выборка не i.i.d. и не фиксирована: изменили политику — изменилось распределение состояний, в которых вы оказываетесь. Обучение и сбор данных сцеплены в петлю обратной связи, и эта петля способна разъезжаться.

Аналогия, которая работает лучше всех: дрессировка. Вы не показываете собаке «правильную» последовательность движений — вы даёте лакомство, когда получилось похоже на нужное. Собака исследует пространство поведений, замечает корреляции между действиями и лакомством и постепенно смещает вероятности. RL — это математически строгая версия того же процесса.

Практическая ценность двойная. Во-первых, RL решает задачи, которые supervised learning не формулирует в принципе: управление роботом, планирование ресурсов, стратегии в играх, адаптивные рекомендации, дообучение языковых моделей под предпочтения людей (RLHF). Во-вторых — и это важнее для большинства читателей — понимание RL меняет взгляд на любые системы с обратной связью. Рекомендательная лента (статья 12) формирует данные, на которых обучается завтра; кредитный скоринг определяет, кого мы больше никогда не увидим. Это RL-ситуации, даже если вы обучаете в них обычный градиентный бустинг.

Формализм: марковский процесс принятия решений

Базовая абстракция — MDP (Markov Decision Process), пятёрка $\langle \mathcal{S}, \mathcal{A}, P, R, \gamma \rangle$:

• $\mathcal{S}$ — множество состояний среды;
• $\mathcal{A}$ — множество действий (возможно, зависящее от состояния);
• $P(s’ \mid s, a)$ — вероятность перехода: куда среда попадёт, если в $s$ сделать $a$;
• $R(s, a, s’)$ — награда за переход (скаляр!);
• $\gamma \in [0, 1]$ — коэффициент дисконтирования.

Марковское свойство: $P(s_{t+1} \mid s_t, a_t) = P(s_{t+1} \mid s_1, a_1, \dots, s_t, a_t)$. Будущее зависит от настоящего, но не от того, как мы в настоящее попали. Это не свойство мира, а свойство выбранного представления состояния. Позиция на шахматной доске марковская, а «последний ход противника» — нет. Если у вас есть скрытая информация (POMDP, Partially Observable MDP), стандартный приём — включить в состояние историю наблюдений или её сжатое представление (рекуррентную скрытую переменную, стек последних кадров, как в оригинальном DQN на Atari).

Цикл взаимодействия:

Политика $\pi(a \mid s)$ — распределение действий в состоянии; детерминированная политика записывается как $a = \pi(s)$. Обучение = поиск хорошей политики.

Что значит «хорошая»? Определим возврат (return) — суммарную дисконтированную награду с момента $t$:

$$ G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \dots = \sum_{k=0}^{\infty} \gamma^k r_{t+k+1} $$

Цель агента — максимизировать $\mathbb{E}_ \pi[G_0]$.

Зачем нужен дисконт γ

Три причины, и только одна из них философская.

1. Математическая. Если эпизод бесконечен, а награды ограничены $|r| \le R_{\max}$, то ряд без дисконта расходится, а с $\gamma < 1$ сходится: $|G_t| \le R_{\max}/(1 - \gamma)$. Без этого «максимизировать сумму» не имеет смысла.
2. Инженерная. $\gamma$ задаёт эффективный горизонт планирования $\approx 1/(1-\gamma)$ шагов. $\gamma = 0.99$ — примерно 100 шагов, $\gamma = 0.9$ — примерно 10. Это самый недооценённый гиперпараметр RL: слишком маленькая $\gamma$ делает агента близоруким, слишком большая — резко увеличивает дисперсию оценок и замедляет обучение.
3. Содержательная. Награда сейчас предпочтительнее награды потом (ставка дисконтирования в финансах — ровно это).

Для эпизодических задач с гарантированным терминалом можно брать $\gamma = 1$, но на практике $\gamma \in [0.95, 0.999]$ почти всегда.

Игрушечный MDP

Возьмём среду «инженер и его карьера» — она нам пригодится дальше:

Заметьте ловушку, ради которой пример и построен: «перерабатывать» даёт мгновенные +8 — больше любого другого действия. Жадный по мгновенной награде агент выберет его и застрянет в состоянии с $-5$ за шаг. Правильное решение видно только при $\gamma$, достаточно большой, чтобы разглядеть последствия. Это RL в одном абзаце.

Ценность и уравнения Беллмана

Работать напрямую с $\mathbb{E}[G_0]$ неудобно, поэтому вводят функции ценности.

Ценность состояния при политике $\pi$:

$$ V^\pi(s) = \mathbb{E}_ \pi\big[G_t \mid s_t = s\big] $$

Ценность пары состояние-действие (Q-функция):

$$ Q^\pi(s, a) = \mathbb{E}_ \pi\big[G_t \mid s_t = s,\ a_t = a\big] $$

Разница принципиальна для практики: зная $V$, чтобы выбрать действие, нужна модель среды («куда я попаду, если сделаю $a$?»). Зная $Q$, действие выбирается напрямую: $a^\ast = \arg\max_a Q(s, a)$. Поэтому model-free методы почти всегда учат $Q$.

Из определения через рекурсию $G_t = r_{t+1} + \gamma G_{t+1}$ получаем уравнение Беллмана для оценки:

$$ V^\pi(s) = \sum_a \pi(a \mid s) \sum_{s’} P(s’ \mid s, a)\Big[R(s,a,s’) + \gamma V^\pi(s’)\Big] $$

Это система линейных уравнений размера $|\mathcal{S}|$: ценность состояния = средняя награда плюс дисконтированная ценность того, куда попадём.

Уравнение оптимальности Беллмана описывает лучшую из возможных политик:

$$ V^\ast (s) = \max_a \sum_{s’} P(s’ \mid s, a)\Big[R(s,a,s’) + \gamma V^\ast (s’)\Big] $$

$$ Q^\ast (s, a) = \sum_{s’} P(s’ \mid s, a)\Big[R(s,a,s’) + \gamma \max_{a’} Q^\ast (s’, a’)\Big] $$

Здесь уже нелинейность из-за $\max$, зато есть замечательное свойство: оператор Беллмана $\mathcal{T}$ является $\gamma$-сжатием в норме $|\cdot|_ \infty$:

$$ |\mathcal{T}V_1 - \mathcal{T}V_2|_ \infty \le \gamma |V_1 - V_2|_ \infty $$

По теореме Банаха о неподвижной точке отсюда следует: неподвижная точка существует, единственна, и итерация $V_{k+1} = \mathcal{T}V_k$ сходится к ней геометрически со скоростью $\gamma^k$. Это фундамент, на котором стоит почти весь RL. И это же объясняет, почему $\gamma$ близкая к 1 делает задачу тяжёлой: скорость сходимости падает, а константа $1/(1-\gamma)$ в оценках ошибки взрывается.

Если модель известна: динамическое программирование

Когда $P$ и $R$ заданы явно (например, вы моделируете склад или очередь), задача решается точно.

Policy iteration чередует два шага:

1. Оценка политики: решить уравнение Беллмана для текущей $\pi$ (итеративно или напрямую обращением матрицы за $O(|\mathcal{S}|^3)$).
2. Улучшение политики: $\pi’(s) = \arg\max_a \sum_{s’} P(s’|s,a)[R + \gamma V^\pi(s’)]$.

Теорема об улучшении политики гарантирует $V^{\pi’} \ge V^\pi$ покомпонентно, а так как политик конечное число, процесс сходится за конечное число итераций — на практике за единицы.

Value iteration сливает оба шага в один, применяя оператор оптимальности до сходимости:

import numpy as np

def value_iteration(P, R, gamma=0.99, theta=1e-8, max_iter=10_000):
    """Итерация по ценностям для MDP с явно заданной моделью.

    P: массив (S, A, S) — вероятности переходов P[s, a, s']
    R: массив (S, A, S) — награды R[s, a, s']
    Возвращает: V (S,), детерминированную политику pi (S,)

    Сложность: O(|S|^2 |A|) на итерацию, число итераций ~ log(1/eps) / log(1/gamma).
    Память: O(|S|^2 |A|) на модель, O(|S|) на V.
    """
    n_states, n_actions, _ = P.shape
    V = np.zeros(n_states)

    for it in range(max_iter):
        # Q[s, a] = sum_s' P[s,a,s'] * (R[s,a,s'] + gamma * V[s'])
        Q = np.einsum("sat,sat->sa", P, R + gamma * V[None, None, :])
        V_new = Q.max(axis=1)                 # оператор оптимальности Беллмана
        delta = np.abs(V_new - V).max()       # норма бесконечности
        V = V_new
        if delta < theta:
            break

    Q = np.einsum("sat,sat->sa", P, R + gamma * V[None, None, :])
    pi = Q.argmax(axis=1)
    # Гарантия качества: если ||V_{k+1} - V_k||_inf < theta,
    # то ||V_k - V*||_inf < theta * gamma / (1 - gamma)
    return V, pi

Когда это применимо в проде. Чаще, чем кажется: управление запасами, задачи замены оборудования, оптимальная остановка, маршрутизация в сетях с известной топологией, ценообразование при известной модели спроса. Ограничение — проклятие размерности: $|\mathcal{S}|$ растёт экспоненциально с числом переменных состояния. Склад на 10 товаров по 100 единиц каждого — это $101^{10}$ состояний. Именно отсюда растут все остальные методы.

Model-free prediction: Монте-Карло против TD

Модели среды обычно нет. Есть только возможность взаимодействовать и собирать траектории.

Метод Монте-Карло прямолинеен: дождаться конца эпизода, посчитать фактический возврат $G_t$, усреднить по всем посещениям состояния:

$$ V(s_t) \leftarrow V(s_t) + \alpha\big[G_t - V(s_t)\big] $$

Оценка несмещённая (по определению $V$ есть матожидание $G$), но дисперсия огромна: $G_t$ — сумма сотен случайных величин. Плюс метод требует завершения эпизода, то есть не работает в непрерывных задачах.

Temporal Difference, TD(0) заменяет фактический хвост траектории текущей оценкой:

$$ V(s_t) \leftarrow V(s_t) + \alpha\underbrace{\big[r_{t+1} + \gamma V(s_{t+1}) - V(s_t)\big]}_ {\text{TD-ошибка } \delta_t} $$

Это бутстрэппинг: обновляем оценку на основании другой оценки. Смещение появляется (потому что $V(s_{t+1})$ пока неверна), зато дисперсия падает драматически — суммируется один шаг вместо сотни. И обновление происходит онлайн, после каждого перехода.

Между ними — непрерывный спектр. n-шаговый возврат:

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

При $n = 1$ это TD(0), при $n = \infty$ — Монте-Карло. TD(λ) усредняет все $n$ с геометрическими весами $(1-\lambda)\lambda^{n-1}$, что реализуется эффективно через следы приемлемости (eligibility traces) — вектор «насколько недавно и часто мы посещали это состояние», обновляемый за $O(|\mathcal{S}|)$ на шаг. Практический вывод: $\lambda \approx 0.9$ и $n \in [3, 20]$ почти всегда работают лучше, чем крайности. В современных алгоритмах эта идея живёт как GAE (Generalized Advantage Estimation), о котором ниже.

Ключевое различие в том, чему они сходятся на конечной выборке. MC минимизирует среднеквадратичную ошибку на наблюдённых возвратах. TD сходится к решению максимально правдоподобной MDP, построенной по данным (certainty-equivalence estimate). Классический пример из Саттона и Барто (задача с восемью эпизодами про состояния A и B) показывает, что это разные ответы, и обычно TD-ответ лучше обобщается, потому что использует марковскую структуру.

Управление: SARSA и Q-learning

Оценка ценности — половина дела; нужно ещё улучшать политику. Обобщённая схема — GPI (Generalized Policy Iteration): непрерывное чередование частичной оценки и частичного улучшения.

SARSA (по названию пятёрки $s, a, r, s’, a’$) — on-policy метод:

$$ Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha\big[r_{t+1} + \gamma Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t)\big] $$

Здесь $a_{t+1}$ — действие, которое агент реально сделает по своей (исследующей) политике.

Q-learning — off-policy метод:

$$ Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha\big[r_{t+1} + \gamma \max_{a’} Q(s_{t+1}, a’) - Q(s_t, a_t)\big] $$

Здесь берётся максимум — действие оптимальной политики, независимо от того, что агент сделает на самом деле. Это позволяет учить оптимальную политику, ведя себя как угодно (лишь бы исследовать), — свойство, на котором держатся все современные off-policy алгоритмы и offline RL.

Разница между ними — не академическая. Вот каноническая демонстрация:

Q-learning находит истинно оптимальный маршрут вдоль края обрыва, но во время обучения регулярно падает из-за $\varepsilon$-шагов, и его онлайн-производительность хуже. SARSA учит ценность $\varepsilon$-жадной политики, то есть «знает», что иногда оступится, — и выбирает безопасный обход. Если агент учится в реальном мире, где падение стоит денег, on-policy осторожность может быть тем, что вам нужно. При $\varepsilon \to 0$ SARSA сходится к тому же оптимуму.

import numpy as np
from collections import defaultdict

def eps_greedy(Q, s, n_actions, eps, rng):
    if rng.random() < eps:
        return rng.integers(n_actions)
    return int(np.argmax(Q[s]))

def q_learning(env, n_actions, episodes=5000, alpha=0.1, gamma=0.99,
               eps_start=1.0, eps_end=0.05, seed=0):
    """Табличный Q-learning с линейным затуханием epsilon.

    Сложность: O(1) на шаг по времени, O(|S| * |A|) по памяти.
    """
    rng = np.random.default_rng(seed)
    Q = defaultdict(lambda: np.zeros(n_actions))

    for ep in range(episodes):
        # затухание разведки: сначала исследуем, потом эксплуатируем
        eps = eps_end + (eps_start - eps_end) * max(0.0, 1 - ep / (0.8 * episodes))
        s, _ = env.reset()
        done = False
        while not done:
            a = eps_greedy(Q, s, n_actions, eps, rng)
            s_next, r, terminated, truncated, _ = env.step(a)
            done = terminated or truncated
            # ВАЖНО: в терминальном состоянии будущей ценности нет.
            # Пропуск этой проверки — ошибка №1 в самописных реализациях.
            target = r if terminated else r + gamma * Q[s_next].max()
            Q[s][a] += alpha * (target - Q[s][a])
            s = s_next

    policy = {s: int(np.argmax(q)) for s, q in Q.items()}
    return Q, policy


def sarsa(env, n_actions, episodes=5000, alpha=0.1, gamma=0.99, eps=0.1, seed=0):
    """SARSA: on-policy, цель строится по РЕАЛЬНО выбранному следующему действию."""
    rng = np.random.default_rng(seed)
    Q = defaultdict(lambda: np.zeros(n_actions))

    for _ in range(episodes):
        s, _ = env.reset()
        a = eps_greedy(Q, s, n_actions, eps, rng)
        done = False
        while not done:
            s_next, r, terminated, truncated, _ = env.step(a)
            done = terminated or truncated
            a_next = eps_greedy(Q, s_next, n_actions, eps, rng)
            target = r if terminated else r + gamma * Q[s_next][a_next]
            Q[s][a] += alpha * (target - Q[s][a])
            s, a = s_next, a_next
    return Q

Условия сходимости

Табличный Q-learning сходится к $Q^\ast $ с вероятностью 1 (Watkins & Dayan, 1992) при условиях Роббинса–Монро на шаг обучения:

$$ \sum_{t} \alpha_t(s,a) = \infty, \qquad \sum_{t} \alpha_t^2(s,a) < \infty $$

и при бесконечном посещении каждой пары $(s, a)$. Первое условие означает «шагов хватит, чтобы дойти откуда угодно», второе — «шум в итоге затухнет». Классический пример: $\alpha_t = 1/t$ подходит, $\alpha_t = \text{const}$ — формально нет (оценка будет колебаться вокруг решения), но на практике постоянный $\alpha \in [0.01, 0.1]$ используют повсеместно, потому что в нестационарной среде забывать старое — это фича.

Смещение максимизации и Double Q-learning

У оператора $\max$ есть неприятное свойство: $\mathbb{E}[\max_a \hat{Q}(s,a)] \ge \max_a \mathbb{E}[\hat{Q}(s,a)]$ (неравенство Йенсена). Шум в оценках систематически завышает цель — это maximization bias. На среде с большим числом действий и зашумлёнными наградами Q-learning может уверенно выучить, что плохое действие хорошее.

Лечение — Double Q-learning (Hasselt, 2010): держать две таблицы и разделить выбор действия и оценку его ценности:

$$ Q_1(s,a) \leftarrow Q_1(s,a) + \alpha\Big[r + \gamma, Q_2\big(s’, \arg\max_{a’} Q_1(s’, a’)\big) - Q_1(s,a)\Big] $$

Обновляем случайно выбранную из двух таблиц. Та же идея позже стала Double DQN. Ещё один вариант — Expected SARSA, где вместо сэмпла $a_{t+1}$ берётся точное матожидание $\sum_{a’} \pi(a’|s’)Q(s’,a’)$: убирает дисперсию от выбора действия, стоит $O(|\mathcal{A}|)$ на шаг и почти всегда доминирует обычный SARSA.

Разведка против эксплуатации

Фундаментальная дилемма: использовать лучшее известное или искать лучшее неизвестное? Она изолированно изучается на многоруких бандитах — MDP из одного состояния.

Метрика качества — regret (сожаление) за $T$ шагов: $\mathcal{R}(T) = T\mu^\ast - \sum_{t=1}^{T}\mathbb{E}[\mu_{a_t}]$. Нижняя граница Лаи–Роббинса говорит: любой разумный алгоритм имеет $\mathcal{R}(T) = \Omega(\log T)$. Логарифм — это хорошо: доля потерь стремится к нулю.

UCB реализует принцип «оптимизм при неопределённости»: непопробованное действие получает большой бонус за неуверенность и обязательно будет исследовано. Thompson sampling делает то же самое элегантнее — через сэмплирование из апостериорного распределения.

import numpy as np

def thompson_bernoulli(env, n_arms, T, seed=0):
    """Thompson sampling для бандита с бинарной наградой.

    Сопряжённый приор Beta(1,1) = равномерный. После каждого шага
    апостериорное распределение обновляется в замкнутой форме.
    Сложность: O(K) на шаг.
    """
    rng = np.random.default_rng(seed)
    alpha = np.ones(n_arms)   # успехи + 1
    beta = np.ones(n_arms)    # неудачи + 1

    for t in range(T):
        theta = rng.beta(alpha, beta)      # сэмпл из апостериорного
        a = int(np.argmax(theta))          # жадно по сэмплу, а не по среднему
        r = env.pull(a)                    # 0 или 1
        alpha[a] += r
        beta[a] += 1 - r
    return alpha / (alpha + beta)

Практика. Именно бандиты, а не полноценный RL, стоят за большинством продовых «RL-систем»: выбор баннера, порядок карточек, подбор заголовка, тюнинг цены. Причина проста — в них нет проблемы присвоения заслуг, они сходятся на порядки быстрее, а контекстные бандиты (LinUCB, Thompson с линейной моделью) добавляют персонализацию почти бесплатно. Если ваша задача формулируется как «одно решение → быстрая награда, состояние не меняется», не берите RL, берите бандита.

В глубоком RL к базовым стратегиям добавляются: шум в параметрах (NoisyNet), внутренняя мотивация (Random Network Distillation, ICM — награда за новизну состояния), энтропийный бонус в policy gradient и счётчики псевдо-посещений. Это критично в средах с редкой наградой: в Montezuma’s Revenge $\varepsilon$-жадная стратегия не находит первую награду никогда.

Аппроксимация функций и deadly triad

Таблица $Q[s][a]$ умирает, как только состояний становится больше миллиона, а на непрерывных состояниях не существует вовсе. Заменяем её параметрической моделью $Q_\theta(s,a)$ — линейной по признакам, деревом или нейросетью — и минимизируем:

$$ L(\theta) = \mathbb{E}\Big[\big(\underbrace{r + \gamma \max_{a’} Q_{\theta^-}(s’, a’)}_ {\text{цель } y} - Q_\theta(s,a)\big)^2\Big] $$

Здесь начинаются настоящие проблемы. Deadly triad (Саттон и Барто, гл. 11) — комбинация трёх свойств, каждое из которых полезно, но вместе они дают расходимость:

Уберите любой из трёх элементов — и сходимость восстанавливается (линейный TD on-policy сходится; Монте-Карло с аппроксимацией сходится; таблица off-policy сходится). Держите все три — и получите знаменитый контрпример Бэрда (Baird’s counterexample), где веса уходят в бесконечность на тривиальной среде из семи состояний.

Отдельная тонкость: TD-обновление не является градиентом никакой функции потерь. Мы считаем градиент только по $Q_\theta(s,a)$, а зависимость цели от $\theta$ игнорируем — это полуградиент (semi-gradient). Формально мы обновляемся не в направлении антиградиента, и именно поэтому гарантий нет.

DQN и его семейство

Deep Q-Network (Mnih et al., 2015, Nature) сделал глубокий RL работающим на Atari за счёт двух инженерных приёмов:

1. Experience replay — буфер из последних $N$ (обычно $10^6$) переходов, из которого сэмплируется случайный минибатч. Разбивает временну́ю корреляцию и превращает задачу в почти-supervised, а заодно даёт переиспользование данных (sample efficiency).
2. Target network — отдельная копия весов $\theta^-$, обновляемая раз в $C$ шагов (или мягко: $\theta^- \leftarrow \tau\theta + (1-\tau)\theta^-$). Цель перестаёт «убегать» от предсказания, задача становится похожа на стационарную регрессию.

import torch, torch.nn as nn, torch.nn.functional as F

class QNet(nn.Module):
    """Q-сеть выдаёт вектор ценностей всех действий за один проход:
    это дешевле, чем |A| проходов с действием на входе."""
    def __init__(self, obs_dim, n_actions, hidden=128):
        super().__init__()
        self.net = nn.Sequential(
            nn.Linear(obs_dim, hidden), nn.ReLU(),
            nn.Linear(hidden, hidden), nn.ReLU(),
            nn.Linear(hidden, n_actions),
        )

    def forward(self, s):
        return self.net(s)


def dqn_loss(batch, q_net, target_net, gamma=0.99, double=True):
    """Одна итерация обучения DQN / Double DQN.

    batch: словарь тензоров s (B,obs), a (B,), r (B,), s2 (B,obs), done (B,)
    Сложность: O(B * параметры сети) на шаг.
    """
    s, a, r, s2, done = batch["s"], batch["a"], batch["r"], batch["s2"], batch["done"]

    # Q(s, a) — берём столбец, соответствующий реально выполненному действию
    q_sa = q_net(s).gather(1, a.unsqueeze(1)).squeeze(1)

    with torch.no_grad():
        if double:
            # выбор действия — онлайн-сетью, оценка — целевой:
            # это и есть лекарство от смещения максимизации
            a_star = q_net(s2).argmax(dim=1, keepdim=True)
            q_next = target_net(s2).gather(1, a_star).squeeze(1)
        else:
            q_next = target_net(s2).max(dim=1).values
        # (1 - done) обнуляет будущее в терминальных состояниях
        y = r + gamma * (1.0 - done) * q_next

    # Huber вместо MSE: устойчивость к выбросам в TD-ошибке
    return F.smooth_l1_loss(q_sa, y)

Дальнейшие улучшения, собранные вместе в Rainbow (Hessel et al., 2018) и дающие в сумме кратный прирост:

• Double DQN — развязка выбора и оценки (код выше);
• Dueling — разложение $Q(s,a) = V(s) + A(s,a) - \frac{1}{|\mathcal{A}|}\sum_{a’}A(s,a’)$; полезно, когда в большинстве состояний выбор действия не важен;
• Prioritized Experience Replay — сэмплировать переходы пропорционально $|\delta|^\alpha$, с коррекцией смещения весами importance sampling;
• Multi-step returns ($n = 3$) — быстрее распространяют награду назад;
• Distributional RL (C51, QR-DQN) — учить распределение возврата, а не среднее;
• NoisyNet — обучаемый шум в весах вместо $\varepsilon$.

Policy gradient: учим политику напрямую

Value-based методы плохи там, где действий бесконечно много (непрерывное управление), где оптимальная политика стохастична (покер, камень-ножницы-бумага) и где нужен плавный контроль над политикой. Решение — параметризовать политику $\pi_\theta(a|s)$ и оптимизировать $J(\theta) = \mathbb{E}_ {\tau \sim \pi_\theta}[G_0]$ напрямую.

Теорема о градиенте политики:

$$ \nabla_\theta J(\theta) = \mathbb{E}_ {\pi_\theta}\Big[\sum_{t} \nabla_\theta \log \pi_\theta(a_t \mid s_t), Q^{\pi_\theta}(s_t, a_t)\Big] $$

Красота результата в том, что в правой части нет $\nabla_\theta P(s’|s,a)$: градиент не требует модели среды. Интуиция проста — увеличиваем логарифм вероятности действий, которые привели к высокому возврату, уменьшаем для остальных. Это «взвешенное правдоподобие», где веса — это то, насколько хорошо всё закончилось.

REINFORCE (Williams, 1992) подставляет вместо $Q$ фактический возврат $G_t$. Работает, но дисперсия невыносима. Три стандартных лекарства:

1. Baseline. Вычесть любую функцию, не зависящую от действия: $\nabla J = \mathbb{E}[\nabla \log \pi_\theta(a|s)(G_t - b(s))]$. Оценка остаётся несмещённой (потому что $\mathbb{E}_ a[\nabla\log\pi] = 0$), а дисперсия падает в разы. Оптимальный baseline — это $V(s)$.
2. Преимущество (advantage): $A^\pi(s,a) = Q^\pi(s,a) - V^\pi(s)$ — «насколько это действие лучше среднего в этом состоянии». Отвечает на правильный вопрос: не «хорошо ли здесь», а «стоило ли делать именно это».
3. Actor-critic: учим две сети — актора $\pi_\theta$ и критика $V_\phi$, оценивающего baseline. Критик обучается по TD, актор — по градиенту политики.

GAE (Generalized Advantage Estimation, Schulman et al., 2016) — это TD(λ) для преимуществ, экспоненциально взвешенная сумма TD-ошибок:

$$ \hat{A}_ t^{\text{GAE}(\gamma,\lambda)} = \sum_{l=0}^{\infty}(\gamma\lambda)^l \delta_{t+l}, \qquad \delta_t = r_t + \gamma V(s_{t+1}) - V(s_t) $$

$\lambda = 0$ даёт одношаговый TD (смещённый, низкодисперсионный), $\lambda = 1$ — Монте-Карло. На практике $\lambda \in [0.9, 0.97]$.

PPO — рабочая лошадка

Проблема ванильного policy gradient: слишком большой шаг разрушает политику, а восстановиться некому — плохая политика собирает плохие данные. TRPO решал это через ограничение на KL-дивергенцию и решение задачи с доверительной областью; PPO (Schulman et al., 2017) достигает почти того же результата одной строкой с клиппингом:

$$ L^{\text{CLIP}}(\theta) = \mathbb{E}_ t\Big[\min\big(\rho_t \hat{A}_ t,\ \text{clip}(\rho_t, 1-\epsilon, 1+\epsilon)\hat{A}_ t\big)\Big], \qquad \rho_t = \frac{\pi_\theta(a_t|s_t)}{\pi_{\theta_{\text{old}}}(a_t|s_t)} $$

Смысл: если отношение вероятностей ушло дальше чем на $\epsilon$ (обычно 0.2) и это улучшает цель, градиент обнуляется — шаг отсекается. Если ухудшает, штраф остаётся. Это позволяет делать несколько эпох градиентных шагов по одному батчу данных, не разваливая политику.

import torch

def ppo_loss(logp_new, logp_old, adv, values, returns,
             clip=0.2, vf_coef=0.5, ent_coef=0.01, entropy=None):
    """Комбинированная функция потерь PPO-clip.

    logp_new/logp_old: log π(a|s) под новыми/старыми параметрами, (B,)
    adv: оценки преимущества (GAE), (B,)
    """
    # Нормализация преимуществ — не теория, а критичный на практике трюк:
    # стабилизирует масштаб градиента между батчами.
    adv = (adv - adv.mean()) / (adv.std() + 1e-8)

    ratio = torch.exp(logp_new - logp_old)          # ρ_t, устойчиво через логарифмы
    unclipped = ratio * adv
    clipped = torch.clamp(ratio, 1 - clip, 1 + clip) * adv
    policy_loss = -torch.min(unclipped, clipped).mean()

    value_loss = 0.5 * (values - returns).pow(2).mean()
    entropy_bonus = entropy.mean() if entropy is not None else 0.0

    # энтропийный бонус не даёт политике схлопнуться в детерминированную слишком рано
    return policy_loss + vf_coef * value_loss - ent_coef * entropy_bonus

Непрерывное управление

Практическое правило: SAC — если взаимодействие дорогое (робот, реальная система), PPO — если симулятор дешёвый и можно гнать тысячи параллельных сред. SAC на порядок эффективнее по числу сэмплов, PPO проще и устойчивее к настройке.

Model-based RL и планирование

Model-free методы тратят миллионы взаимодействий. Если модель среды можно выучить или она известна, планирование даёт огромный выигрыш в sample efficiency.

• Dyna-Q — простейшая гибридизация: после реального шага сделать $n$ «воображаемых» обновлений на переходах, сгенерированных выученной моделью. Десять строк кода, кратное ускорение.
• MCTS (Monte Carlo Tree Search) — планирование поиском по дереву с балансом разведки/эксплуатации через UCT. Основа AlphaGo/AlphaZero: нейросеть даёт приоры и оценку позиции, MCTS их уточняет, результат поиска становится обучающей целью для сети.
• MuZero (Schrittwieser et al., 2020) — учит модель не в пространстве наблюдений, а в латентном пространстве, и только те её аспекты, которые нужны для предсказания награды, ценности и политики. Это снимает необходимость точно реконструировать пиксели.
• World models / Dreamer — обучение политики целиком «во сне», внутри выученной модели.

Главный риск: эксплуатация ошибок модели. Оптимизатор найдёт в вашей неточной модели состояние, где она предсказывает награду $+10^6$, и радостно туда пойдёт. Лечение — ансамбли моделей и учёт неопределённости, короткие горизонты воображаемых роллаутов.

Offline RL: обучение без взаимодействия

В большинстве промышленных задач взаимодействовать с реальной средой нельзя: нельзя экспериментировать с дозировками лекарств, с торговым алгоритмом на живых деньгах, с логистикой склада. Но есть логи — история решений и их последствий. Offline RL (batch RL) учится только по ним.

Проблема здесь одна, но фатальная: сдвиг распределения. Q-функция уверенно оценивает действия, которых в данных не было (экстраполяция нейросети), $\max$ выбирает именно их, ошибка через бутстрэп усиливается и разъезжается. Наивный DQN на офлайн-данных работает хуже, чем поведенческое клонирование.

Семейство решений:

• BCQ / BEAR — ограничить политику окрестностью данных;
• CQL (Conservative Q-Learning) — добавить штраф, занижающий $Q$ на действиях вне данных;
• IQL (Implicit Q-Learning) — вообще не оценивать $Q$ на неизвестных действиях, использовать экспектильную регрессию;
• Decision Transformer — переформулировать RL как авторегрессионное моделирование последовательностей, обусловленное желаемым возвратом.

Отдельная тема — off-policy evaluation (OPE): как оценить новую политику по логам старой, не выкатывая её. Базовый инструмент — importance sampling $\hat{V}^{\pi} = \frac{1}{n}\sum_i \frac{\pi(a_i|s_i)}{\mu(a_i|s_i)} r_i$, где $\mu$ — логирующая политика. Дисперсия растёт экспоненциально с горизонтом, поэтому применяют клиппинг весов, self-normalized IS и doubly robust оценки. Практическое следствие, которое стоит запомнить: логируйте вероятности своих решений. Если логирующая политика была детерминированной, корректная офлайн-оценка невозможна в принципе — добавьте хотя бы небольшую рандомизацию.

RLHF: RL внутри языковых моделей

Самое массовое применение RL сегодня — дообучение LLM под человеческие предпочтения.

Ключевые особенности этой постановки:

• Награда выучена, а не задана. Reward model обучается на попарных сравнениях через модель Брэдли–Терри: $P(y_1 \succ y_2) = \sigma(r_\psi(x,y_1) - r_\psi(x,y_2))$. Люди плохо ставят абсолютные оценки, но хорошо сравнивают.
• KL-штраф обязателен. Без члена $-\beta,\mathrm{KL}(\pi_\theta | \pi_{\text{SFT}})$ политика уходит в reward hacking: находит текстовые паттерны, которые reward model любит, а люди — нет. Это буквально та же эксплуатация ошибок модели, что и в model-based RL.
• Один шаг, огромное действие. Эпизод — это генерация одного ответа; действие — токен. Задача ближе к контекстному бандиту, чем к классическому MDP.
• DPO (Direct Preference Optimization, 2023) показал, что при некоторых предположениях оптимум этой задачи выражается в замкнутой форме и обучается обычным supervised-лоссом на парах — без reward model и без RL-петли. Для многих задач это проще и стабильнее.

Подробнее про архитектуры, на которых это работает (трансформеры, обучение больших сетей), — в треке «Нейронные сети» на портале.

Эволюция области

Как выбрать алгоритм

Типичные ошибки

1. Взять RL там, где хватает бандита или supervised. Самая дорогая ошибка. Если решение не влияет на будущие состояния — это не RL-задача. Оцените честно: становится ли следующая ситуация другой из-за вашего действия?
2. Забыть обнулить будущее в терминальном состоянии. target = r + gamma * Q(s2).max() без (1 - done) — классика. Агент учится, что после смерти жизнь продолжается, и ценности расходятся.
3. Путать terminated и truncated. Обрыв эпизода по таймауту — не терминал среды. Бутстрэпить в этом случае нужно, иначе вы систематически занижаете ценности. В Gymnasium это два разных флага именно поэтому.
4. Неотмасштабированные награды. Награды порядка $10^4$ ломают обучение сети так же, как неотмасштабированные признаки ломают градиентный спуск (см. статью 02). Клиппинг наград в $[-1, 1]$ или нормализация возвратов бегущим средним — стандартная практика.
5. Reward shaping, ломающий оптимальную политику. Добавили бонус «за движение вперёд» — агент научился ездить кругами. Безопасный способ единственный: potential-based shaping $F(s,a,s’) = \gamma\Phi(s’) - \Phi(s)$ — теорема Ng, Harada & Russell (1999) гарантирует, что оптимальная политика при этом не меняется.
6. Сравнивать алгоритмы по одному запуску. Дисперсия между сидами в глубоком RL сопоставима с разницей между алгоритмами. Минимум 5–10 сидов, показывайте медиану и межквартильный размах, а не среднее и не лучший запуск (Henderson et al., «Deep RL That Matters»).
7. Слишком маленькая γ. Агент физически не видит последствий дальше $1/(1-\gamma)$ шагов. Если награда приходит через 500 шагов, а $\gamma = 0.95$ (горизонт ~20), обучение невозможно в принципе.
8. Оценивать по обучающей кривой. Кривая обучения включает $\varepsilon$-шум разведки. Отдельно прогоняйте детерминированную (жадную) политику для оценки.
9. Игнорировать нестационарность в проде. Пользователи, конкуренты и рынок меняются. Политика, обученная на прошлогодних данных, оптимизирует прошлогодний мир. Мониторинг распределения состояний и наград — обязателен (см. MLOps).
10. Не логировать вероятности действий. Убивает любую возможность корректной офлайн-оценки и переобучения политики позже.

RL в проде: где действительно работает

Честная картина по состоянию на сегодня.

Работает и приносит деньги:

• Контекстные бандиты в рекомендациях и рекламе — выбор креатива, ранжирование, exploration в холодном старте. Это RL в самой лёгкой форме, и она окупается.
• Real-time bidding — ставки в аукционах с бюджетным ограничением: естественная последовательная задача с чётким сигналом награды.
• Управление инфраструктурой — охлаждение датацентров (DeepMind/Google, около 40% экономии на охлаждении), автомасштабирование, планирование задач, кэш-политики.
• RLHF/DPO для LLM — сегодня крупнейшая по объёму вычислений область применения RL.
• Робототехника с sim-to-real — обучение в симуляторе с domain randomization, перенос на железо (манипуляция, локомоция).
• Оптимизация цепочек поставок и запасов — там, где классический DP не масштабируется.

Работает плохо или не окупается:

• Задачи, где нет ни симулятора, ни большого объёма логов.
• Задачи с редкой наградой и без осмысленного shaping.
• Всё, где стоимость ошибки при разведке высока и симулировать нельзя (медицина, финансы) — здесь offline RL плюс строгая офлайн-оценка, и очень осторожно.
• Ситуации, где интерпретируемость решения обязательна по регуляторике.

Инструменты: Gymnasium (стандартный API сред, наследник OpenAI Gym), Stable-Baselines3 (надёжные реализации PPO/SAC/TD3/DQN — берите их, а не свои), CleanRL (однофайловые референсные реализации, лучший источник для чтения), Ray RLlib (распределённое обучение), PettingZoo (мультиагентные среды), Optuna для подбора гиперпараметров.

Настоятельный совет: не пишите свой PPO для прода. Разница между корректной и почти корректной реализацией — десятки процентов качества, и все грабли уже задокументированы (см. «The 37 Implementation Details of PPO»).

Мини-итог

Обучение с подкреплением — это оптимизация последовательных решений, когда правильный ответ неизвестен, награда отложена, а данные порождает сам обучаемый агент. Формальная рамка — MDP, математический фундамент — уравнения Беллмана и сжимающий оператор, гарантирующий сходимость в табличном случае.

Все методы раскладываются по двум осям. Есть ли модель среды: если да — динамическое программирование и планирование, если нет — обучение по опыту. Что параметризуем: ценность (Q-learning, SARSA, DQN), политику (REINFORCE, PPO) или оба (actor-critic, SAC). Между Монте-Карло и одношаговым TD лежит непрерывный спектр компромисса смещение/дисперсия, настраиваемый через $n$ или $\lambda$.

Как только табличное представление заменяется нейросетью, теоретические гарантии исчезают, и deadly triad превращает обучение в инженерную дисциплину: target network, replay buffer, нормализация наград, клиппинг шага. Это не украшения, это то, без чего алгоритм расходится.

И главное, что стоит унести: RL — дорогой инструмент. Он оправдан, когда решение действительно меняет будущее и когда есть симулятор или много логов. В остальных случаях контекстный бандит или обычная supervised-модель с грамотно построенной целевой переменной дадут 90% пользы за 10% сложности.

Источники

• Sutton R., Barto A. Reinforcement Learning: An Introduction, 2nd ed., 2018 — главная книга области, бесплатный PDF.
• Szepesvári C. Algorithms for Reinforcement Learning, 2010 — компактная теоретическая сводка, PDF.
• Puterman M. Markov Decision Processes: Discrete Stochastic Dynamic Programming, 1994 — канон по MDP и динамическому программированию.
• Lattimore T., Szepesvári C. Bandit Algorithms, 2020 — бесплатный PDF.
• Watkins C., Dayan P. Q-learning, Machine Learning 8, 1992 — доказательство сходимости.
• Williams R. Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning, Machine Learning 8, 1992 — REINFORCE.
• Mnih V. et al. Human-level control through deep reinforcement learning, Nature 518, 2015 — DQN.
• van Hasselt H. et al. Deep Reinforcement Learning with Double Q-learning, AAAI 2016.
• Schulman J. et al. High-Dimensional Continuous Control Using Generalized Advantage Estimation, ICLR 2016 — GAE.
• Schulman J. et al. Proximal Policy Optimization Algorithms, 2017 — PPO.
• Haarnoja T. et al. Soft Actor-Critic, ICML 2018.
• Fujimoto S. et al. Addressing Function Approximation Error in Actor-Critic Methods, ICML 2018 — TD3.
• Hessel M. et al. Rainbow: Combining Improvements in Deep RL, AAAI 2018.
• Schrittwieser J. et al. Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model, Nature 588, 2020 — MuZero.
• Levine S. et al. Offline Reinforcement Learning: Tutorial, Review, and Perspectives, 2020.
• Kumar A. et al. Conservative Q-Learning for Offline RL, NeurIPS 2020.
• Kostrikov I. et al. Offline RL with Implicit Q-Learning, ICLR 2022 — IQL.
• Ng A., Harada D., Russell S. Policy Invariance Under Reward Transformations, ICML 1999 — теория reward shaping.
• Henderson P. et al. Deep Reinforcement Learning That Matters, AAAI 2018 — про воспроизводимость.
• Ouyang L. et al. Training language models to follow instructions with human feedback, NeurIPS 2022 — InstructGPT/RLHF.
• Rafailov R. et al. Direct Preference Optimization, NeurIPS 2023 — DPO.
• Huang S. et al. The 37 Implementation Details of Proximal Policy Optimization, ICLR Blog Track 2022.
• Spinning Up in Deep RL — лучший практический вводный курс с кодом.
• Документация Gymnasium и Stable-Baselines3.

Что дальше

MLOps: от эксперимента до продакшена — финальная статья трека и та часть работы, без которой всё предыдущее остаётся ноутбуком. Разберём версионирование данных и моделей, воспроизводимость экспериментов, feature store, стратегии деплоя и раскатки, мониторинг дрейфа и деградации качества, автоматическое переобучение и то, как выстроить всё это в надёжный конвейер. Для RL-систем этот слой особенно критичен: политика, которая сама порождает свои будущие обучающие данные, деградирует тише и опаснее любой offline-модели.