Q-learning, actor и critic

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

Один переход вместо полной модели

В марковском процессе решений итерация ценности опиралась на сумму по всем $s'$ с известными вероятностями $P(s'\mid s,a)$. Робот в настоящем коридоре, станция велопроката, накопитель в здании такой таблицы не имеют. Им доступен один-единственный факт опыта — четвёрка

$$(s_t,a_t,r_{t+1},s_{t+1}).$$

Из этой четвёрки нужно извлечь всё. Идея temporal difference проста до неприличия: там, где уравнение Беллмана требует ожидания, подставим одну случайную реализацию и сделаем маленький шаг в её сторону. Ожидание восстановится не в одном обновлении, а в среднем по многим.

Q-learning оценивает ценность действия при оптимальном продолжении. Для наблюдаемого перехода беллмановская цель равна

$$y_t=r_{t+1}+\gamma\max_{a'}Q(s_{t+1},a').$$

Разница между целью и текущей оценкой называется ошибкой временной разности:

$$\delta_t=y_t-Q(s_t,a_t).$$

Она и есть весь учебный сигнал:

$$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha_t\,\delta_t.$$

Если переход оказался лучше текущего ожидания, $\delta_t>0$ и ценность растёт. Если хуже — падает. Обновления шумны, потому что вместо ожидания стоит одна реализация, но в среднем они направлены к решению уравнения Беллмана.

Беллман писал это про задачу с известной моделью. TD-методы берут то же свойство и превращают его в правило пересчёта одной ячейки таблицы по одному наблюдению — без суммы, без вероятностей, без карты мира.

Почему подстановка одного перехода работает

Запишем истинное уравнение оптимальности для пары $(s,a)$:

$$Q^*(s,a)=\mathbb E\bigl[r+\gamma\max_{a'}Q^*(s',a')\bigr].$$

Оператор в правой части обозначим $\mathcal TQ$. Он является сжатием: для любых таблиц $Q_1,Q_2$

$$\|\mathcal TQ_1-\mathcal TQ_2\|_\infty\le\gamma\|Q_1-Q_2\|_\infty .$$

Если бы мы умели вычислять $\mathcal TQ$ точно, повторное применение сходилось бы к неподвижной точке $Q^*$ по теореме Банаха. Мы не умеем: у нас есть только несмещённая выборочная версия

$$\widehat{\mathcal T}Q(s,a)=r+\gamma\max_{a'}Q(s',a'),\qquad \mathbb E\bigl[\widehat{\mathcal T}Q\bigr]=\mathcal TQ .$$

Поэтому TD-обновление — это в точности стохастическая аппроксимация из урока о SGD: шаг делается по зашумлённой оценке нужного направления. Тот же аппарат, та же плата — дисперсия, и та же награда — отсутствие необходимости знать всё сразу.

Волна ценности идёт назад

Пока таблица пуста, TD-ошибка отлична от нуля только там, где встретилась настоящая награда. В следующем эпизоде ненулевой становится соседняя ячейка, и знание ползёт от цели к старту со скоростью один переход за эпизод.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

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

Каким должен быть шаг

Табличный Q-learning сходится к $Q^*$ с вероятностью 1 при двух условиях: каждая пара $(s,a)$ посещается бесконечно часто, а шаги удовлетворяют условиям Роббинса–Монро

$$\sum_t\alpha_t(s,a)=\infty,\qquad \sum_t\alpha_t^2(s,a)<\infty .$$

Первое требование означает «шагов хватит, чтобы уйти от любой начальной ошибки», второе — «шум в конце концов усредняется». Постоянный шаг второму условию не удовлетворяет: оценка вечно дрожит вокруг цели с амплитудой порядка $\alpha$. Классический выбор — $\alpha_n=1/n^{\,p}$ с $p\in(0{,}5;1]$, где $n$ — число посещений именно этой ячейки.

На реальной задаче эту разницу видно глазами: на нашей станции велопроката (о ней ниже) постоянный шаг $\alpha=0{,}02$ за 8000 эпизодов дотягивает лишь до 88,21 руб., постоянный $\alpha=0{,}6$ — до 101,04 руб., а убывающий $\alpha_n=1/n^{0{,}7}$ — до 111,15 руб. при оптимуме 114,88 руб.

Off-policy: действуем одним правилом, учим другое

Поведение агента может быть $\varepsilon$-жадным, но цель содержит $\max_{a'}Q(s',a')$ — оценку идеального продолжения. Значит, Q-learning учит жадную target-policy по данным, собранным другой, исследующей behavior-policy. Это и называется off-policy.

SARSA поступает иначе: в цель подставляется действие, которое агент действительно выбрал:

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

Разница выглядит косметической — $\max_{a'}Q(s',a')$ против $Q(s',a')$ — но она меняет то, о чём вообще идёт речь.

Обрыв: цена оптимизма

Возьмём сетку $4\times8$. Старт слева внизу, цель справа внизу, между ними нижний ряд — обрыв: попадание в него стоит $-100$ и возвращает на старт. Каждый обычный шаг стоит $-1$. Оба алгоритма живут по одной и той же $\varepsilon$-жадной политике с $\varepsilon=0{,}1$ и $\alpha=0{,}5$.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

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

Исследование нельзя выключить слишком рано

Жадная политика

$$\pi(s)=\arg\max_aQ(s,a)$$

использует накопленное знание, но ничего не проверяет. Ячейка с ошибочно низкой оценкой не будет посещена никогда, и ошибка останется навсегда. Самый простой ремонт — $\varepsilon$-greedy:

$$\pi(a\mid s)= \begin{cases} 1-\varepsilon+\varepsilon/|A|, & a=\arg\max_bQ(s,b),\\[2pt] \varepsilon/|A|, & \text{иначе}. \end{cases}$$

На нашей станции велопроката при нулевой инициализации и $\varepsilon=0$ агент навсегда застревает в политике «ничего не завозить» и получает 25,00 руб. против оптимума 114,88 руб. Достаточно $\varepsilon=0{,}3$, чтобы за 6000 эпизодов дойти до 113,40 руб., причём даже расточительное $\varepsilon=0{,}6$ даёт 113,16 руб.: исследование стоит дорого во время обучения, но оценивается жадная политика, а она от него только выигрывает.

Фельдбаум: управление, которое учится по дороге

Дилемму «изучать или использовать» в советской теории автоматического управления сформулировали раньше, чем появилось обучение с подкреплением. Александр Аронович Фельдбаум в 1960–1961 годах опубликовал в «Автоматике и телемеханике» цикл статей «Теория дуального управления». Его тезис: если характеристики объекта неизвестны, управляющее воздействие обязано играть двойную роль — вести объект к цели и одновременно доставлять информацию о нём. Оптимальное управление в условиях неопределённости не бывает чисто исполнительным: оно всегда содержит пробующую составляющую, и величина этой пробы сама подлежит оптимизации.

Наше $\varepsilon$ — самая грубая из возможных реализаций этой идеи: проба, не зависящая ни от состояния, ни от того, много ли мы уже знаем. Фельдбаум ставил вопрос строже — какой должна быть оптимальная проба, если есть апостериорное распределение параметров объекта. Ответ в общем виде оказывается вычислительно чудовищным, и вся последующая история — от бандитов с UCB и Томпсоном до современного RL — это поиск приемлемых приближений к дуальному управлению.

Станция велопроката: учимся без таблицы вероятностей

Возьмём реальные данные: 17 379 часов почасовых наблюдений велопроката — тот же файл, что в уроке о базисных признаках. Спрос на станции в час $t$ — случайная величина с распределением, снятым прямо с этих наблюдений: минимум приходится на 4 часа ночи (в среднем 0,00 велосипеда), пик — на 17 часов (3,69 велосипеда).

Среда устроена так: ёмкость станции 10 велосипедов, эпизод длится сутки, старт с пятью велосипедами. Каждый час агент выбирает завоз $a_t\in\{0,1,2\}$ по 2 рубля за велосипед, затем приходит спрос $d_t$ и обслуживается $\min(q_t+a_t,d_t)$ поездок по 5 рублей:

$$r_t=5\min(q_t+a_t,d_t)-2a_t,$$ $$q_{t+1}=\min(10,q_t+a_t)-\min(q_t+a_t,d_t).$$

Мы, авторы задачи, знаем распределение спроса и можем посчитать точный оптимум обратным динамическим программированием: $V^*=114{,}88$ руб. за сутки. Агент его не знает: у него 792 ячейки $(t,q,a)$ и поток переходов.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Actor и critic: разделение труда

Актёр $\pi_\phi(a\mid s)$ — дифференцируемая стратегия. Критик $V_\psi(s)$ — оценка ценности состояния. Тот же TD-сигнал

$$\delta_t=r_{t+1}+\gamma V_\psi(s_{t+1})-V_\psi(s_t)$$

работает для обоих, но по-разному. Критик уменьшает $\delta_t^2$, актёр получает направление

$$\phi\leftarrow\phi+\eta\,\delta_t\nabla_\phi\log\pi_\phi(a_t\mid s_t).$$

Формула читается буквально: «если получилось лучше ожидаемого, сделай это действие вероятнее». Величина $\delta_t$ служит приближением преимущества

$$A^\pi(s,a)=Q^\pi(s,a)-V^\pi(s),$$

и это ключевой момент: актёр учится не на награде, а на разнице между случившимся и обычным.

Для дискретных действий актёр обычно выдаёт softmax $\pi_i=e^{z_i}/\sum_je^{z_j}$, и градиент логарифма имеет простой вид

$$\nabla_z\log\pi_k=e_k-\pi .$$

Вероятность выбранного действия растёт, все остальные пропорционально уменьшаются — единичная сумма сохраняется автоматически.

Почему baseline не смещает, но помогает

Градиент политики можно записать через любую функцию $b(s)$, не зависящую от действия:

$$\nabla_\phi J=\mathbb E\bigl[(Q^\pi(s,a)-b(s))\nabla_\phi\log\pi_\phi(a\mid s)\bigr].$$

Вычитание $b(s)$ ничего не меняет в ожидании, потому что

$$\mathbb E_{a\sim\pi}\bigl[\nabla_\phi\log\pi_\phi(a\mid s)\bigr] =\sum_a\pi_\phi(a\mid s)\frac{\nabla_\phi\pi_\phi(a\mid s)}{\pi_\phi(a\mid s)} =\nabla_\phi\sum_a\pi_\phi(a\mid s)=\nabla_\phi1=0 .$$

Зато дисперсия меняется сильно: выбор $b(s)=V^\pi(s)$ убирает из сигнала всё, что относится к состоянию, а не к решению. В задаче, где любое действие в богатом состоянии приносит $+100$, а в бедном $-100$, без baseline актёр учит в основном шум состояния. Именно поэтому критик в actor–critic не роскошь, а средство борьбы с дисперсией — ровно как в уроке о смещении и разбросе, только теперь дисперсия убивает не прогноз, а обучение.

Критик ошибается — актёр расплачивается

Актёр не имеет собственного доступа к истине: он видит только $\delta_t$, которую выдал критик. Добавим к TD-сигналу независимый шум $\mathcal N(0,\sigma^2)$ — модель критика, который ошибается не систематически, а просто беспорядочно.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Сколько шагов брать до того, как поверить критику

Между чистым TD (один шаг и оценка) и Monte Carlo (весь эпизод) лежит семейство $n$-шаговых возвратов:

$$G_t^{(n)}=\sum_{k=0}^{n-1}\gamma^kr_{t+k+1}+\gamma^nV(s_{t+n}).$$

Малое $n$ означает много доверия критику: мало дисперсии, но всё его смещение попадает в цель. Большое $n$ — много реального опыта: смещение уходит, дисперсия суммы наград растёт линейно по $n$.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Максимум шумных оценок смещён вверх

Даже если каждая оценка $\widehat Q_a$ несмещённа, максимум по действиям — нет. По неравенству Йенсена для выпуклой функции максимума

$$\mathbb E\max_a\widehat Q_a\ge\max_a\mathbb E\widehat Q_a .$$

Для двух независимых $\mathcal N(0,\sigma^2)$ разница считается точно: $\mathbb E\max=\sigma/\sqrt\pi\approx0{,}564\sigma$. Эксперимент на 100 000 наборов подтверждает: при $\sigma=1$ и двух действиях средний максимум равен $0{,}566$, при десяти действиях — $1{,}539$. При $\sigma=0{,}1$ и десяти действиях смещение падает до $0{,}154$ — оно пропорционально шуму, а значит, исчезает только вместе с ним.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Лекарство — разделить выбор действия и его оценку:

$$y=r+\gamma\,Q_{\bar\theta}\bigl(s',\arg\max_aQ_\theta(s',a)\bigr).$$

Одна таблица выбирает, вторая оценивает, и один и тот же благоприятный шум редко используется дважды. Идея та же, что при разделении обучающей и проверочной выборок в уроке о переобучении: нельзя выбирать и подтверждать по одним и тем же числам.

От таблицы к сети: replay, target-сеть и deadly triad

Для изображения или непрерывного состояния таблица невозможна. Заменим её сетью $Q_\theta(s,a)$ и минимизируем

$$\mathcal L(\theta)=\mathbb E\left[\bigl(r+\gamma\max_{a'}Q_{\bar\theta}(s',a') -Q_\theta(s,a)\bigr)^2\right].$$

Два костыля делают это работоспособным. Target-сеть с параметрами $\bar\theta$ обновляется медленнее основной — иначе цель убегает синхронно с предсказанием и задача превращается в погоню за собственным хвостом. Replay buffer перемешивает прошлые переходы: соседние наблюдения в потоке почти одинаковы, и градиенты по ним не независимы.

Лаборатория TD

Здесь видно всё сразу. Оставьте Q-learning и следите, как окраска ценности расползается от цели к старту — это тот же процесс, что в таблицах рисунка 71.1, только на плоскости. Затем сравните трёх учеников при одном и том же $\varepsilon=0{,}1$: жадный маршрут Q-learning прижмётся к обрыву, SARSA уйдёт наверх, и при этом средний возврат у SARSA окажется выше. Поставьте $\varepsilon=0$ и нажмите «забыть всё»: обучение остановится почти сразу — таблица не может исправить того, чего не пробует. Наконец, поднимите $\alpha$ до 0,9 и посмотрите, как ценности начинают дрожать: таблица повторяет последний шумный опыт вместо того, чтобы усреднять.

Offline-ловушка

Предположим, взаимодействовать со средой нельзя, а есть журнал старой политики. Q-learning всё равно берёт максимум по действиям — включая те, которых в журнале почти нет. Аппроксиматор способен назначить им произвольно высокое значение, bootstrap перенесёт это значение назад, и агент уверует в несуществующий выигрыш. Это extrapolation error, и она тем сильнее, чем уже поддержка данных:

$$\text{надёжно}\quad\Longleftrightarrow\quad \mu_{\text{данные}}(a\mid s)>0\ \text{всюду, где}\ \pi_{\text{новая}}(a\mid s)>0 .$$

Безопасные offline-методы либо штрафуют действия вне поддержки, либо строят консервативные оценки $Q$. Но первый вопрос должен быть другим: нужен ли здесь RL вообще. Если решения не влияют на будущие состояния, достаточно контекстного бандита. Если для фиксированного действия есть хорошие метки исхода, хватит обычного обучения с учителем.

Что должно быть в отчёте

Кривая обучения — самая обманчивая картинка в RL: она показывает результат поведения с исследованием, а внедряют обычно политику без него. Минимальный честный отчёт содержит:

• ценность итоговой политики без exploration noise, отдельно от кривой;
• разброс по нескольким seed, а не одну «удачную» кривую;
• показатели, ради которых всё затевалось (рубли, пики, отказы), а не только reward;
• число нарушений ограничений и поведение в редких состояниях;
• деградацию при сдвиге среды — например, при переносе вечернего пика спроса на другие часы без дообучения.

От перехода к устойчивой политике

Q-learning переносит уравнение Беллмана в поток наблюдаемых переходов: подставляет одну реализацию вместо ожидания и платит за это дисперсией и смещением максимума. SARSA отвечает на другой вопрос — как жить с собственным шумом. Actor–critic отделяет выбор действия от оценки продолжения, покупая низкую дисперсию ценой доверия к критику. Общее у них одно: агент учится на данных, которые сам же и породил, поэтому исследование, поддержка действий и честная оценка важнее красивой финальной кривой. Устойчивость нейросетевого RL достигается устройством эксперимента, а не одной формулой.

Задачи