🔴 Сложный ⏱️ 55 минут

Reinforcement Learning

📋 Содержание урока

Reinforcement Learning 🎮

До сих пор весь курс двигался вдоль одной из двух парадигм, о которых ты узнал ещё в уроке 303: либо у модели есть готовые правильные ответы, и она учится их предсказывать (обучение с учителем — от линейной регрессии до BERT и GPT), либо правильных ответов нет вовсе, и модель ищет скрытую структуру в самих данных (обучение без учителя — кластеризация, снижение размерности, автоэнкодеры и VAE из прошлого урока). Обе парадигмы объединяет одна общая черта: модель один раз смотрит на статичный набор примеров и извлекает из него закономерность. Она не действует, не влияет на то, какие данные увидит дальше, и не платит за свою ошибку ничем, кроме числа в функции потерь.

Существует и третий, принципиально другой способ учиться — тот, которым на самом деле учится любое живое существо, впервые оказавшееся в незнакомой обстановке. Ребёнок, учащийся ходить, не получает от родителей миллион размеченных примеров «вот так ставить ногу правильно, а вот так — нет». Он пробует, падает, получает обратную связь в виде боли или радости от того, что удержал равновесие, и постепенно, через серию проб и ошибок, вырабатывает стратегию, которая работает. Именно эта третья парадигма — обучение с подкреплением, или Reinforcement Learning (RL), — и есть тема сегодняшнего урока. Здесь нет ни готовых правильных ответов на каждом шаге, ни пассивного поиска структуры в неподвижных данных: есть агент, который действует в среде, и среда, которая в ответ на каждое действие выдаёт награду — иногда сразу, а чаще с задержкой, объединяющей вклад целой цепочки решений.

Урок 303 уже познакомил тебя с обучением с подкреплением бегло, ровно настолько, чтобы дать общую картину и показать главное отличие: в RL сигнал качества — это не заранее известный правильный ответ на конкретный вход, а вознаграждение за последовательность решений. Сегодня мы разворачиваем эту тему полностью: разбираем формальный язык RL — агента, среду, состояние, действие, награду и политику, — строгую математическую модель задачи (марковский процесс принятия решений), способ оценивать «насколько хорошо» находиться в том или ином состоянии (функцию ценности и уравнение Беллмана) и центральную дилемму любого обучающегося агента — стоит ли пробовать новое действие или полагаться на уже проверенное хорошее (exploration vs exploitation).

Урок 344 про BERT, GPT и большие языковые модели закончился обещанием: современные модели вроде ChatGPT и Claude дообучаются через Reinforcement Learning from Human Feedback (RLHF) — обучение с подкреплением на основе обратной связи людей, — и это отдельная, обширная тема, которая заслуживает собственного урока. Сегодня мы это обещание выполняем: к концу урока ты будешь понимать не только теорию RL как таковую, но и то, почему именно эта парадигма — а не обучение с учителем напрямую — оказалась нужна, чтобы превратить сырую языковую модель, предсказывающую следующий токен, в помощника, который старается быть полезным, честным и безопасным.

История

Корни обучения с подкреплением уходят одновременно в две, на первый взгляд, далёкие друг от друга области — психологию обучения животных и теорию оптимального управления. В начале XX века американский психолог Эдвард Торндайк, наблюдая, как кошки учатся выбираться из проблемных ящиков, сформулировал «закон эффекта»: действия, за которыми следует удовлетворительный результат, закрепляются и с большей вероятностью повторяются в аналогичной ситуации, а действия, за которыми следует неприятный результат, — ослабляются. Это интуитивное наблюдение — обучение через последствия собственных действий, а не через объяснение «правильного» ответа заранее, — и есть психологическая суть подкрепления, давшая всей области её название. Параллельно, уже в середине века, Ричард Беллман — тот самый математик, чьё имя ты видел в уроке 270 про динамическое программирование, — развивал теорию оптимального управления многошаговыми процессами и сформулировал уравнение, носящее сегодня его имя: оптимальное решение многошаговой задачи складывается из немедленной выгоды на текущем шаге и оптимального решения всей оставшейся задачи. Это уравнение, выведенное для задач инженерного управления, оказалось математическим фундаментом, на котором десятилетия спустя выстроилось всё современное RL.

Дисциплина в её нынешнем виде — как отдельная область машинного обучения со своим строгим математическим аппаратом — сложилась в 1980–1990-е годы прежде всего благодаря работам Ричарда Саттона (Richard Sutton) и Эндрю Барто (Andrew Barto). Их совместная книга «Reinforcement Learning: An Introduction», первое издание которой вышло в 1998 году, стала (и остаётся по сей день) главным учебником по предмету — именно в ней собраны воедино идеи временных различий (temporal difference learning), Q-learning, придуманного Крисом Уоткинсом в 1989 году, и формальный аппарат марковских процессов принятия решений. Саттон и Барто не просто систематизировали существующие результаты — они показали, что за внешне разрозненными идеями из психологии обучения, теории оптимального управления и информатики стоит единая математическая структура.

Следующий большой скачок случился уже в 2010-е годы, когда RL соединили с глубокими нейросетями. В 2013 году компания DeepMind опубликовала работу о Deep Q-Network (DQN) — алгоритме, который научился играть в классические игры Atari (Breakout, Pong и десятки других) прямо по пикселям экрана, без единой подсказки о правилах игры, и во многих играх превзошёл человека. А в 2016 году тот же DeepMind представил AlphaGo — систему, обыгравшую действующего чемпиона мира по игре го Ли Седоля, — событие, которое многие специалисты считали невозможным для компьютеров ещё десятилетие, потому что число возможных позиций в го (около $10^{170}$) превышает число атомов в наблюдаемой Вселенной, и никакой прямой перебор здесь принципиально не работает. Про AlphaGo и его развитие ты подробнее прочитаешь в разделе «Интересные факты» этого урока. А ещё десятилетие спустя ровно та же математическая идея — агент, действие, награда, оптимизация политики — легла в основу RLHF, о котором мы подробно поговорим в разделе «Связь с темами курса».

Агент, среда, состояние, действие, награда и политика

Интуиция

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

Ключевое отличие RL от обучения с учителем в том, что среда не сообщает агенту заранее, какое действие было бы «правильным». Она лишь выдаёт число — награду — уже после того, как действие совершено, и агенту приходится самому, через множество попыток, выяснять, какие действия в среднем ведут к более высоким наградам в долгосрочной перспективе, а не только прямо сейчас. Резкое торможение перед поворотом может дать низкую награду в моменте (потеря скорости), но избежать вылета с трассы и куда большего штрафа через секунду — агенту нужно научиться видеть эту отложенную связь.

Формула

Формальные компоненты RL-задачи. На каждом дискретном шаге времени $t$:

  • агент наблюдает текущее состояние среды $s_t \in S$, где $S$ — множество всех возможных состояний;
  • агент выбирает действие $a_t \in A$ согласно своей политике $\pi(a \mid s)$ — функции (детерминированной или вероятностной), сопоставляющей состоянию распределение вероятностей по действиям;
  • среда в ответ переходит в новое состояние $s_{t+1}$ и выдаёт скалярную награду $r_{t+1} \in \mathbb{R}$;
  • процесс повторяется, порождая траекторию (эпизод) $s_0, a_0, r_1, s_1, a_1, r_2, s_2, \ldots$

Цель обучения — найти политику $\pi^*$, максимизирующую ожидаемую суммарную дисконтированную награду (return):

$$G_t = \sum_{k=0}^{\infty} \gamma^k r_{t+k+1}, \qquad \gamma \in [0, 1]$$

где $\gamma$ — коэффициент дисконтирования, определяющий, насколько сильно агент «ценит» награды, отложенные во времени, по сравнению с наградами прямо сейчас.

Разбор примеров

Пример 1 (пятиклеточный лабиринт — определение всех компонентов). Рассмотрим прямой коридор из пяти клеток, пронумерованных от 1 до 5. Агент стартует в клетке 1, может двигаться влево или вправо на одну клетку за шаг, а клетка 5 — выход с наградой $+10$; за каждый обычный шаг агент получает штраф $-1$ (чтобы стимулировать искать выход быстрее). Определим все компоненты формально: множество состояний $S = \{1, 2, 3, 4, 5\}$; множество действий $A = \{\text{влево}, \text{вправо}\}$ (с учётом того, что из клетки 1 действие «влево» невозможно и просто оставляет агента на месте); функция награды $R(s, a) = -1$ для любого обычного перехода и $R(4, \text{вправо}) = +10$ для перехода в терминальную клетку 5; политика — это, например, простое правило «всегда идти вправо», $\pi(\text{вправо} \mid s) = 1$ для любого $s$. Траектория при этой политике: $s_0{=}1 \to a_0{=}\text{вправо} \to r_1{=}{-}1, s_1{=}2 \to \ldots \to a_3{=}\text{вправо} \to r_4{=}{+}10, s_4{=}5$. Суммарная (недисконтированная) награда за эпизод: три шага по $-1$ плюс финальный $+10$, итого $-1-1-1+10 = 7$.

Пример 2 (та же задача с дисконтированием — как $\gamma$ меняет предпочтения). Возьмём тот же коридор, но сравним политику «всегда вправо» (доходит до выхода за 4 шага) с гипотетической неэффективной политикой, которая сначала делает шаг влево и обратно (получая лишний штраф), а затем всё равно доходит за 6 шагов вместо 4. Награды первой политики по шагам: $-1, -1, -1, +10$. Награды второй: $-1, -1, -1, -1, -1, +10$. При $\gamma = 1$ (без дисконтирования) первая политика даёт сумму $7$, вторая — $5$: разница очевидна и без дисконтирования. Но теперь возьмём $\gamma = 0{,}9$ и посчитаем $G_0$ для первой политики: $G_0 = -1 + 0{,}9\cdot(-1) + 0{,}9^2\cdot(-1) + 0{,}9^3\cdot 10 = -1 - 0{,}9 - 0{,}81 + 7{,}29 = 4{,}58$. Для второй политики: $G_0 = -1 - 0{,}9 - 0{,}81 - 0{,}729 - 0{,}6561 + 0{,}9^5\cdot10 = -4{,}0951 + 5{,}9049 = 1{,}81$. Дисконтирование не изменило вывод — первая политика всё равно лучше, — но заметно увеличило разрыв в её пользу, потому что штрафы второй политики растянуты по времени сильнее, а награда получена позже (значит, она сильнее «обесценена» степенью $\gamma^5$ вместо $\gamma^3$). Именно так дисконтирование естественным образом наказывает медлительность и поощряет более быстрый путь к цели.

Пример 3 (крайние значения $\gamma$ — почему нельзя просто взять $\gamma=1$ или $\gamma=0$). При $\gamma = 0$ формула $G_t = \sum_k \gamma^k r_{t+k+1}$ вырождается в $G_t = r_{t+1}$ — агент учитывает только награду за самый ближайший шаг и полностью игнорирует всё, что будет дальше; это агент с «памятью на один шаг», неспособный жертвовать сиюминутной выгодой ради стратегического выигрыша (например, он никогда не согласится на временный штраф ради последующей крупной награды). При $\gamma = 1$, наоборот, все будущие награды учитываются с равным весом, без затухания; в эпизодических задачах с гарантированным концом (как коридор из примера 1) это допустимо, но в задачах без естественного конца сумма $\sum_k r_{t+k+1}$ может расходиться к бесконечности при постоянном ненулевом потоке наград, и сравнивать между собой две бесконечные суммы становится математически бессмысленно. Именно поэтому на практике почти всегда берут $\gamma$ строго между 0 и 1, обычно в диапазоне $0{,}9$–$0{,}99$: это гарантирует сходимость суммы в задачах без естественного конца и одновременно даёт агенту достаточно «дальновидности», чтобы учитывать отложенные последствия своих решений.

Почему это важно

Точный словарь агента, среды, состояния, действия, награды и политики — это не педантизм ради педантизма: путаница в этих понятиях на практике оборачивается конкретными и дорогими ошибками при проектировании системы. Если состояние спроектировано неполным (агенту не видна информация, необходимая для принятия хорошего решения), никакой алгоритм обучения не сможет её компенсировать — агент будет систематически принимать субоптимальные решения не из-за плохого алгоритма, а из-за плохого описания задачи. Если награда выбрана неудачно — скажем, слишком редкой (sparse reward, награда только в самом конце очень долгого эпизода) или случайно поощряющей не то поведение, которое реально нужно (проблема reward hacking, дословно «взлом награды», когда агент находит формальный способ максимизировать награду, не решая задачу по существу), — обучение либо не сходится вообще, либо сходится к нежелательному поведению. Именно поэтому в реальных RL-проектах значительная часть инженерной работы уходит не на выбор алгоритма обучения, а на аккуратное проектирование пространства состояний и функции награды.

Марковский процесс принятия решений (MDP) и марковское свойство

Интуиция

Формальные компоненты из предыдущего раздела — агент, состояние, действие, награда — сами по себе ещё не образуют математически строгую модель, с которой можно доказывать теоремы и писать сходящиеся алгоритмы. Нужна дополнительная структура, которая связывает эти компоненты в единый объект. Такой структурой служит марковский процесс принятия решений (Markov Decision Process, MDP) — формальная математическая модель практически любой RL-задачи. Название отсылает к русскому математику Андрею Маркову и к ключевому упрощающему предположению, которое делает задачу вычислительно разрешимой: марковское свойство — будущее состояние и награда зависят только от текущего состояния и текущего действия, а не от всей истории, которая привела агента в это состояние.

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

Формула

Марковский процесс принятия решений (MDP) формально задаётся кортежем из пяти элементов $(S, A, P, R, \gamma)$:

  • $S$ — множество состояний;
  • $A$ — множество действий;
  • $P(s' \mid s, a)$ — функция переходов: вероятность оказаться в состоянии $s'$, выполнив действие $a$ в состоянии $s$;
  • $R(s, a)$ — функция награды: ожидаемая немедленная награда за выполнение действия $a$ в состоянии $s$;
  • $\gamma$ — коэффициент дисконтирования.

Марковское свойство формально записывается как условие независимости будущего от всей истории при известном настоящем:

$$P(s_{t+1} \mid s_t, a_t, s_{t-1}, a_{t-1}, \ldots, s_0, a_0) = P(s_{t+1} \mid s_t, a_t)$$

то есть распределение следующего состояния зависит только от текущего состояния и текущего действия, а не от того, как агент в них оказался.

Разбор примеров

Пример 1 (проверка марковского свойства на конкретном состоянии). Возьми игру в шахматы. Является ли текущая расстановка фигур на доске марковским состоянием для задачи выбора следующего хода? Да: правила шахмат таковы, что для определения множества допустимых ходов и для оценки позиции (кроме двух формальных технических исключений — правила взятия на проходе и права на рокировку, которые технически требуют знания одного-двух предыдущих ходов) достаточно текущей расстановки фигур, а не всей истории партии, которая к ней привела. Одна и та же позиция, достигнутая совершенно разными последовательностями ходов, порождает одно и то же множество разумных продолжений. Для контраста возьми игру в покер с закрытыми картами соперника: видимая агенту «часть состояния» (открытые карты на столе, размер банка) сама по себе не марковская в строгом смысле, потому что оптимальное решение зависит ещё и от истории ставок соперника, по которой можно судить о вероятном составе его закрытых карт, — приходится либо расширять понятие состояния (включая историю торгов явно), либо переходить к более сложной модели с частичной наблюдаемостью (POMDP).

Пример 2 (сетка 3×3 — формальное задание MDP и расчёт таблицы переходов). Рассмотрим сетку $3\times3$ с клетками, пронумерованными от $(1,1)$ в левом верхнем углу до $(3,3)$ в правом нижнем. Агент стартует в $(1,1)$, на каждом шаге может двигаться вверх, вниз, влево или вправо (попытка выйти за границу сетки оставляет агента на месте), клетка $(3,3)$ — терминальная с наградой $+10$, клетка $(2,2)$ в центре — «ловушка» с наградой $-5$ и без завершения эпизода, все остальные переходы дают награду $-1$. Формально: $S = \{(i,j) : 1 \le i,j \le 3\}$, $A = \{\text{вверх, вниз, влево, вправо}\}$, переходы детерминированные (для простоты примера $P(s' \mid s, a) = 1$ для единственного корректного $s'$), $R\big((2,3), \text{вниз}\big) = +10$ и $R\big((3,2), \text{вправо}\big) = +10$ (входы в терминальную клетку с двух соседних сторон), $R(1,2 \to 2,2) = -5$ и аналогично для всех переходов в клетку-ловушку, а все остальные переходы дают $-1$. Эта конкретная численная сетка используется дальше, в следующем разделе, чтобы вручную посчитать функцию ценности через уравнение Беллмана.

Пример 3 (контрпример — задача без марковского свойства и способ его восстановить). Представь робота-пылесоса, у которого есть только один датчик — расстояние до ближайшего препятствия впереди, без памяти о пройденном пути. Если он находится в узком коридоре, «текущее расстояние до препятствия» не говорит, движется ли он к тупику или, наоборот, только что выехал из тупика и едет к открытому пространству, — при одинаковом текущем показании датчика правильное действие («двигаться дальше» или «развернуться») может быть разным в зависимости от того, что было раньше. Такое «сырое» состояние не марковское: одинаковое наблюдение соответствует разным оптимальным действиям в зависимости от истории. Стандартное решение — расширить состояние, включив в него, например, последние несколько показаний датчика или направление движения за последние несколько шагов; после такого расширения новое, более богатое состояние вновь становится (приближённо) марковским, потому что вся нужная для решения информация о недавней динамике теперь содержится в нём самом, а не потеряна в истории.

Почему это важно

MDP — это не абстрактная формальность, а конкретный проектный вопрос, который приходится решать в самом начале любого RL-проекта: что именно включить в описание состояния, чтобы марковское свойство выполнялось хотя бы приближённо? Слишком бедное состояние (как у робота-пылесоса без памяти) ломает саму применимость стандартных алгоритмов RL, потому что вся их математика — от уравнения Беллмана до сходимости Q-learning — опирается на марковское свойство. Слишком богатое состояние (например, вся история всех предыдущих кадров игры без сжатия) резко увеличивает размерность задачи и замедляет обучение. Практическое умение находить баланс — достаточно информативное состояние, но не избыточное, — часто определяет успех RL-проекта сильнее, чем выбор конкретного алгоритма обучения.

Функция ценности, Q-функция и уравнение Беллмана

Интуиция

Чтобы агент мог принимать хорошие решения, ему недостаточно знать награду за один непосредственный шаг — нужно уметь оценивать долгосрочную «ценность» текущей ситуации с учётом всех последующих шагов. Представь себя на развилке в лабиринте: один проход выглядит скучным и узким, но за ближайшим поворотом ведёт прямиком к выходу, а другой — просторный и приятный, но заканчивается тупиком. Оценивать нужно не «насколько приятен проход прямо сейчас», а «насколько хороша вся дальнейшая последовательность решений, которая начинается с выбора этого прохода». Именно эту интуицию формализует функция ценности состояния $V(s)$ — ожидаемая суммарная дисконтированная награда, которую агент получит, если начнёт в состоянии $s$ и дальше будет следовать своей политике. Родственная величина, Q-функция $Q(s, a)$, оценивает то же самое, но для конкретной пары «состояние плюс действие» — насколько хорошо выполнить именно это действие в этом состоянии, а дальше уже следовать политике.

Ключевое наблюдение, которое делает вычисление этих функций практически осуществимым, — то же самое наблюдение, которое лежало в основе всего урока 270 про динамическое программирование: ценность состояния можно выразить рекурсивно, через ценности следующих состояний, вместо того чтобы «разворачивать» всю бесконечную (или очень длинную) сумму будущих наград целиком. Это и есть уравнение Беллмана — прямой математический родственник рекуррентной формулы динамического программирования, только записанный на языке состояний, действий и наград, а не на языке индексов массива.

Формула

Уравнение Беллмана для функции ценности состояния (при заданной политике $\pi$):

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

Уравнение Беллмана для Q-функции:

$$Q^\pi(s, a) = \sum_{s'} P(s' \mid s, a) \big[R(s,a) + \gamma \sum_{a'} \pi(a' \mid s') Q^\pi(s', a')\big]$$

Уравнение Беллмана оптимальности (для оптимальной политики $\pi^*$, максимизирующей ценность в каждом состоянии):

$$V^*(s) = \max_a \sum_{s'} P(s' \mid s, a) \big[R(s,a) + \gamma V^*(s')\big], \qquad Q^*(s,a) = \sum_{s'} P(s' \mid s, a)\big[R(s,a) + \gamma \max_{a'} Q^*(s', a')\big]$$

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

Разбор примеров

Пример 1 (прямая параллель с уроком 270 — сравнение формул бок о бок). В уроке 270 рекуррентная формула для кратчайшего пути в графе записывалась в духе «стоимость лучшего пути до вершины $j$ равна минимуму по предшественникам $i$ от стоимости пути до $i$ плюс вес ребра $i \to j$», а в задании 30 того урока эта параллель уже была явно указана как $V(s) = \max_a\big[R(s,a) + \gamma V(s')\big]$. Сопоставим структуру формул впрямую. Табуляция чисел Фибоначчи: $dp[i] = dp[i-1] + dp[i-2]$ — значение в ячейке строится из значений в предыдущих ячейках. Рекуррентная формула 0/1-рюкзака: $dp[i][w] = \max\big(dp[i-1][w],\ dp[i-1][w-\text{wt}_i]+\text{val}_i\big)$ — оптимум для текущего состояния строится как максимум по вариантам из оптимумов для предыдущих состояний. Уравнение Беллмана оптимальности: $V^*(s) = \max_a\big[R(s,a) + \gamma V^*(s')\big]$ — оптимум для текущего состояния строится как максимум по действиям из немедленной награды плюс оптимум для следующего состояния. Три формулы, записанные для трёх разных задач в разных уроках курса, — это буквально одна и та же математическая структура: значение в «ячейке» (индекс массива, пара «предмет-вместимость» или состояние среды) выражается через максимум (или сумму) по вариантам перехода от значений в соседних, уже известных «ячейках». Отличие уравнения Беллмана от рюкзака или Фибоначчи чисто поверхностное: там детерминированный переход к следующей ячейке таблицы, здесь — переход в следующее состояние среды, часто вероятностный, с явным коэффициентом дисконтирования $\gamma$ вместо простого суммирования.

Пример 2 (сетка 3×3 — полный расчёт ценностей состояний методом value iteration, итерации по ценности). Возьмём сетку из примера 2 предыдущего раздела, но упростим до варианта $3\times3$ без ловушки в центре — только терминальная клетка $(3,3)$ с наградой $+10$ и штраф $-1$ за любой обычный переход, детерминированные переходы, $\gamma = 0{,}9$. Инициализируем все $V(s) = 0$ и применим value iteration — итеративное применение уравнения Беллмана оптимальности к каждой клетке, пока значения не перестанут заметно меняться (это прямой аналог табуляции: заполняем таблицу ценностей, опираясь на предыдущую итерацию, пока таблица не сойдётся). Для терминальной клетки $(3,3)$ ценность фиксирована и равна $0$ (эпизод в ней завершается, дальнейших наград не будет). Клетки, соседние с терминальной, — $(2,3)$ и $(3,2)$ — на первой же итерации получают $V = \max_a\big[R + \gamma\cdot 0\big]$; лучшее действие из $(2,3)$ — шаг вниз в $(3,3)$ с наградой $+10$ (а не обычный штрафной переход $-1$ в другую сторону), значит $V(2,3) = 10 + 0{,}9\cdot 0 = 10$, и симметрично $V(3,2) = 10$. На следующей итерации клетка $(1,3)$: лучшее действие — шаг вниз в уже посчитанную $(2,3)$ с $V=10$, но сама награда за этот переход обычная, $-1$ (это не терминальный переход, просто движение по сетке ближе к цели): $V(1,3) = -1 + 0{,}9 \cdot 10 = -1 + 9 = 8$. Аналогично $V(3,1) = 8$ через симметричный путь. Клетка $(2,2)$ в центре: лучшее действие — шаг вправо к $(2,3)$ ($V{=}10$) или вниз к $(3,2)$ ($V{=}10$), оба варианта равноценны: $V(2,2) = -1 + 0{,}9\cdot10 = 8$. Клетка $(1,2)$: лучшее действие — вниз к $(2,2)$ ($V{=}8$) или вправо к $(1,3)$ ($V{=}8$) — оба дают одинаковый результат: $V(1,2) = -1 + 0{,}9\cdot 8 = -1+7{,}2=6{,}2$. Симметрично $V(2,1) = 6{,}2$. Наконец стартовая клетка $(1,1)$: лучшее действие — вправо к $(1,2)$ ($V{=}6{,}2$) или вниз к $(2,1)$ ($V{=}6{,}2$): $V(1,1) = -1 + 0{,}9\cdot 6{,}2 = -1 + 5{,}58 = 4{,}58$. Собранная таблица ценностей (округлённо): $(1,1){=}4{,}58$, $(1,2){=}6{,}2$, $(1,3){=}8$, $(2,1){=}6{,}2$, $(2,2){=}8$, $(2,3){=}10$, $(3,1){=}8$, $(3,2){=}10$, $(3,3){=}0$ (терминальная). Оптимальная политика из любой клетки — двигаться туда, где значение $V$ соседней клетки выше, то есть кратчайшим путём к правому нижнему углу, что полностью совпадает с интуитивно очевидным ответом для такой простой сетки, но теперь получено формальным, повторяемым для куда более сложных сред вычислением.

Пример 3 (связь Q-функции с V-функцией и извлечение политики). Используя ту же сетку и уже посчитанные значения $V$, вычислим Q-функцию для стартовой клетки $(1,1)$ по всем допустимым действиям. Действие «вправо» ведёт в $(1,2)$: $Q\big((1,1),\text{вправо}\big) = R + \gamma V(1,2) = -1 + 0{,}9\cdot 6{,}2 = 4{,}58$. Действие «вниз» ведёт в $(2,1)$: $Q\big((1,1),\text{вниз}\big) = -1 + 0{,}9\cdot 6{,}2 = 4{,}58$ — то же значение в силу симметрии сетки. Действие «влево» или «вверх» упирается в границу и возвращает агента в ту же клетку $(1,1)$: $Q\big((1,1),\text{влево}\big) = -1 + 0{,}9 \cdot V(1,1)$; если использовать уже сошедшееся значение $V(1,1)=4{,}58$, это даёт $-1 + 0{,}9\cdot4{,}58 \approx 3{,}12$ — заметно хуже двух других вариантов. Оптимальная политика в состоянии $(1,1)$ — выбрать действие с максимальным $Q$: $\pi^*(1,1) = \arg\max_a Q\big((1,1),a\big)$, то есть «вправо» или «вниз» (оба дают одинаковый максимум $4{,}58$, выбор между ними произволен). Этот пример показывает главное практическое преимущество Q-функции перед V-функцией: зная только $V(s)$, агенту всё равно нужна модель переходов $P(s'\mid s,a)$, чтобы понять, к какому действию какое следующее состояние приведёт. Зная же сразу $Q(s,a)$ для каждого действия, оптимальное действие находится тривиально — простым взятием максимума по уже готовым числам, вообще без обращения к модели среды. Именно поэтому практические алгоритмы вроде Q-learning, разобранного в следующем разделе, работают именно с Q-функцией, а не с V-функцией напрямую.

Почему это важно

Уравнение Беллмана — не просто удобная формула, а единственная причина, по которой RL-задачи вообще вычислительно разрешимы. Прямой перебор всех возможных бесконечных траекторий агента в среде, чтобы честно оценить $\sum_k \gamma^k r_{t+k+1}$ для каждого варианта поведения, экспоненциально или вовсе бесконечно затратен — ровно та же проблема, что и наивная рекурсия для чисел Фибоначчи без кэша из урока 270, только на порядки серьёзнее, потому что «дерево вариантов» здесь ветвится на каждом шаге бесконечного во времени процесса. Уравнение Беллмана превращает эту невозможную задачу в разрешимую ровно тем же приёмом, что и динамическое программирование: заменяет прямой перебор на рекуррентную зависимость ценности от ценностей соседних, более простых состояний, что открывает дорогу итеративным алгоритмам (value iteration, Q-learning), сходящимся к точному ответу за конечное, практически приемлемое число шагов.

Q-learning: обучение без модели среды

Интуиция

Value iteration из примера 2 предыдущего раздела прекрасно работает, когда агенту заранее известна вся модель среды — функция переходов $P(s'\mid s,a)$ и функция награды $R(s,a)$, — как в примере с сеткой, где мы сами задали правила игры. Но в большинстве реальных задач агент этой модели не имеет: он не знает заранее, куда приведёт то или иное действие и какую награду принесёт, — он вынужден узнавать это, пробуя действия на практике и наблюдая результат. Q-learning, алгоритм Криса Уоткинса 1989 года, решает именно эту задачу: он учит Q-функцию напрямую из опыта взаимодействия со средой, вообще не строя явной модели переходов, — поэтому Q-learning относят к так называемым безмодельным (model-free) методам RL.

Идея удивительно проста: агент хранит таблицу Q-значений для всех пар «состояние-действие» (изначально заполненную произвольно, часто нулями), действует в среде, а после каждого шага немного «подправляет» Q-значение только что использованной пары в сторону более точной оценки, полученной из уравнения Беллмана. Со временем, после достаточного числа проб, таблица сходится к истинной оптимальной Q-функции — той же самой, что value iteration вычислил бы напрямую, если бы модель среды была известна заранее.

Формула

Правило обновления Q-learning:

$$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \Big[\underbrace{r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a')}_{\text{цель (target)}} - \underbrace{Q(s_t, a_t)}_{\text{текущая оценка}}\Big]$$

где $\alpha \in (0, 1]$ — темп обучения (learning rate), определяющий, насколько сильно новое наблюдение сдвигает старую оценку. Разница в скобках называется временн'ой разностью (temporal difference, TD-error) — расхождением между тем, что Q-таблица предсказывала раньше, и тем, что реально произошло на этом шаге (немедленная награда плюс лучшая доступная оценка ценности следующего состояния).

Разбор примеров

Пример 1 (одно обновление Q-таблицы вручную, пошагово). Пусть агент находится в состоянии $s=(1,1)$ той же сетки $3\times3$, все Q-значения инициализированы нулём, $\alpha = 0{,}5$, $\gamma = 0{,}9$. Агент выполняет действие «вправо», получает награду $r=-1$ и попадает в состояние $s'=(1,2)$, где на текущий момент все $Q(s', a') = 0$ (обучение только началось). Цель: $r + \gamma\max_{a'}Q(s',a') = -1 + 0{,}9\cdot 0 = -1$. Обновление: $Q\big((1,1),\text{вправо}\big) \leftarrow 0 + 0{,}5\cdot\big[-1 - 0\big] = -0{,}5$. После этого единственного шага таблица знает лишь одно: попытка пойти вправо из $(1,1)$ пока выглядит слегка убыточной — куда более грубая и осторожная оценка, чем истинное значение $4{,}58$ из value iteration, но именно с таких маленьких, локальных обновлений и начинается сходимость: каждое следующее посещение той же пары «состояние-действие» будет чуть точнее предыдущего.

Пример 2 (трассировка нескольких эпизодов — как награда «просачивается» назад по цепочке). Продолжим пример 1: пусть агент, оказавшись в $(1,2)$, продолжает двигаться и на следующем шаге совершает действие «вправо» в $(1,3)$, а оттуда — «вниз» в $(2,3)$, а оттуда — «вниз» в терминальную клетку $(3,3)$ с наградой $+10$. При условии, что все промежуточные Q-значения на этом первом проходе ещё нулевые, обновление для последнего шага $Q\big((2,3),\text{вниз}\big) \leftarrow 0 + 0{,}5\cdot[10 + 0{,}9\cdot 0 - 0] = 5$ — таблица впервые «узнаёт» про большую награду. При повторном (втором) прогоне того же маршрута обновление для предпоследнего шага уже видит ненулевое значение впереди: $Q\big((1,3),\text{вниз}\big) \leftarrow 0 + 0{,}5\cdot[-1 + 0{,}9\cdot 5 - 0] = 0{,5}\cdot[-1+4{,}5] = 1{,}75$. При третьем прогоне обновится $Q\big((1,2),\text{вправо}\big)$, «увидев» уже ненулевое $Q\big((1,3),\text{вниз}\big)=1{,}75$, и так далее. Это наглядно показывает механизм Q-learning: информация о крупной награде в конце эпизода не появляется во всей таблице мгновенно — она «просачивается» назад по цепочке посещённых состояний, эпизод за эпизодом, пока при достаточном числе повторов вся цепочка Q-значений не сойдётся к согласованным между собой оценкам, удовлетворяющим уравнению Беллмана.

Пример 3 (крестики-нолики — масштаб таблицы и необходимость перехода к нейросетям). В игре в крестики-нолики число различных положений на доске (с учётом того, что не все комбинации X и О физически достижимы по правилам игры) — несколько тысяч, а число пар «состояние-действие» — на порядок больше; такая Q-таблица целиком помещается в оперативную память любого современного компьютера и обучается до сильной игры за разумное число партий против случайного или самого себя играющего оппонента. Но масштаб быстро выходит из-под контроля: число состояний в шахматах оценивается величиной порядка $10^{47}$, а в игре го — порядка $10^{170}$, как уже упоминалось в разделе «История». Никакая таблица, даже теоретически, не может хранить отдельную ячейку для каждого из такого количества состояний — их физически негде разместить и невозможно посетить каждое хотя бы раз за разумное время обучения. Именно эта стена масштаба и привела к идее Deep Q-Network (DQN): вместо явной таблицы Q-значений использовать нейросеть, которая принимает состояние на вход и предсказывает Q-значения для всех действий на выходе, обучаясь по тому же самому правилу временной разности, но обобщая на состояния, которые никогда не встречались явно в процессе обучения, — способность, которой у табличного Q-learning нет в принципе.

Почему это важно

Q-learning — не просто исторически первый практичный алгоритм RL, а концептуальный мост между чистой теорией (уравнение Беллмана, value iteration с известной моделью среды) и практикой (обучение из сырого опыта, без модели среды вообще). Тот факт, что Q-learning доказуемо сходится к оптимальной Q-функции даже без знания $P(s'\mid s,a)$ и $R(s,a)$ заранее — при условии, что каждая пара «состояние-действие» посещается бесконечно много раз, — сделал возможным применение RL к задачам, где построить точную модель среды либо невозможно, либо непрактично (например, реальная физическая робототехника или пользовательское поведение в рекомендательной системе). А переход от табличного представления к нейросетевому (DQN и его многочисленные развития) снял главное практическое ограничение табличного подхода — необходимость явно перечислить и хранить каждое состояние — и открыл дорогу к играм с астрономическим числом состояний, вроде Atari, шахмат и го.

Баланс исследования и использования (exploration vs exploitation)

Интуиция

Представь, что ты переехал в новый город и ищешь, где хорошо позавтракать. В первое же утро ты находишь приличное кафе рядом с домом — не идеальное, но вполне сносное. Дальше перед тобой встаёт постоянный выбор: каждое следующее утро снова идти в уже проверенное кафе (использование, exploitation — брать то, что уже известно как достаточно хорошее) или попробовать новое, незнакомое место (исследование, exploration — рисковать ради шанса найти что-то заметно лучше, или заметно хуже). Если ты всегда выбираешь только использование, ты никогда не узнаешь, что в двух кварталах есть кафе гораздо лучше первого. Если ты всегда выбираешь только исследование, ты тратишь почти каждое утро на случайные, часто неудачные пробы, вместо того чтобы пользоваться уже накопленным знанием.

Ты уже встречал этот же самый компромисс в уроке 299 про байесовскую оптимизацию, где функция приобретения (Expected Improvement) явно балансировала между точками с хорошим прогнозируемым средним (exploitation) и точками с высокой неопределённостью (exploration), а также, менее формально, в контексте эволюционных алгоритмов. В обучении с подкреплением этот же компромисс становится, пожалуй, самой центральной темой всей области: агент, который на каждом шаге выбора действия всегда берёт то, что Q-таблица на текущий момент считает лучшим, рискует навсегда застрять в первой же найденной посредственной стратегии, так и не попробовав действия, которые, возможно, ведут к куда большей награде, — просто потому, что Q-таблица никогда не успела их толком опробовать и обновить.

Формула

$\varepsilon$-жадная стратегия (epsilon-greedy) — самый распространённый практический способ балансировать exploration и exploitation в Q-learning:

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

где $\varepsilon \in [0,1]$ — вероятность выбрать случайное (исследующее) действие вместо текущего наилучшего по таблице (использующего) действия. На практике $\varepsilon$ часто не фиксируют, а постепенно уменьшают по ходу обучения (например, по формуле $\varepsilon_t = \varepsilon_0 \cdot \lambda^t$ с $\lambda < 1$) — от высокого значения в начале обучения, когда Q-таблица ещё почти ничего не знает и исследование особенно ценно, к низкому значению позже, когда таблица уже накопила достаточно достоверных оценок и разумнее в основном полагаться на них.

Разбор примеров

Пример 1 (численный расчёт вероятностей действий при заданном $\varepsilon$). Пусть в некотором состоянии доступно 4 действия, и агент использует $\varepsilon = 0{,}1$. Вероятность того, что будет выбрано конкретно жадное (наилучшее по текущей Q-таблице) действие: с вероятностью $1-\varepsilon = 0{,}9$ оно выбирается напрямую как argmax, плюс ещё небольшой шанс, что при случайном выборе (с вероятностью $\varepsilon=0{,}1$, равномерно распределённой между всеми 4 действиями) случайно выпадет именно оно же — это добавляет $0{,}1 \cdot \tfrac14 = 0{,}025$. Итоговая вероятность выбрать лучшее действие: $0{,}9 + 0{,}025 = 0{,}925$. А вероятность выбрать любое из трёх оставшихся, заведомо не наилучших по таблице действий — только за счёт случайного исследования: $0{,}1 \cdot \tfrac14 = 0{,}025$ на каждое, суммарно $0{,}075$ на все три вместе. Даже при небольшом $\varepsilon=0{,}1$ агент подавляющее большинство времени пользуется уже накопленным знанием, но регулярно, примерно в одном случае из десяти, сознательно пробует что-то другое — ровно настолько часто, чтобы со временем заметить, если одно из «неоптимальных на вид» действий на самом деле окажется лучше.

Пример 2 (постоянный $\varepsilon$ против затухающего — иллюстрация на числах). Пусть обучение длится 1000 эпизодов. При постоянном $\varepsilon = 0{,}2$ агент совершает случайное исследующее действие в среднем в 200 из 1000 случаев выбора действия на протяжении всего обучения — включая самый конец, когда Q-таблица уже, скорее всего, близка к истинным значениям и дальнейшее исследование в основном тратит опыт впустую, вместо того чтобы стабильно применять уже найденную хорошую политику. При затухающем $\varepsilon_t = 1{,}0 \cdot 0{,}995^t$: на шаге $t=0$ агент действует полностью случайно ($\varepsilon_0=1{,}0$), на шаге $t=200$ значение падает до $\varepsilon_{200} = 0{,}995^{200} \approx 0{,}367$, на шаге $t=500$ — до $\varepsilon_{500} \approx 0{,}0817$, а на шаге $t=1000$ — до $\varepsilon_{1000} \approx 0{,}0067$, то есть меньше одного случайного действия из ста. Затухающая схема даёт агенту достаточно широкое исследование в самом начале, когда таблица знает мало, и почти полностью переключает его на использование к концу обучения, когда накопленным оценкам уже можно достаточно доверять, — на практике это почти всегда даёт заметно более быструю и стабильную сходимость, чем постоянный $\varepsilon$.

Пример 3 (многорукий бандит — чистая задача exploration/exploitation без состояний). Рассмотрим три игровых автомата (multi-armed bandit) с неизвестными вероятностями выигрыша: автомат А выигрывает с вероятностью 0,3, автомат Б — с вероятностью 0,5, автомат В — с вероятностью 0,4 (истинные значения агенту неизвестны заранее, ему предстоит их оценивать по опыту). Это вырожденный частный случай RL — задача без состояний вовсе (или, формально, с одним-единственным состоянием), где вся сложность сосредоточена ровно в балансе exploration и exploitation. Если агент после первых трёх пробных дёрганий (по одному на автомат) случайно получил выигрыш от А и проигрыши от Б и В, чисто жадная стратегия ($\varepsilon=0$) зафиксируется на автомате А навсегда, даже несмотря на то, что истинно лучший автомат Б, — потому что жадная стратегия никогда больше не тронет Б и В, чтобы проверить, не ошиблась ли она в оценке по столь скудной, случайно неудачной выборке. $\varepsilon$-жадная стратегия с ненулевым $\varepsilon$ продолжает время от времени дёргать все три автомата и в среднем на длинной дистанции (за счёт закона больших чисел) успевает скорректировать первоначально ошибочную оценку, найдя настоящего лидера — автомат Б.

Почему это важно

Баланс exploration и exploitation — не техническая деталь одного конкретного алгоритма, а фундаментальное свойство любой задачи обучения через взаимодействие со средой, будь то Q-learning, байесовская оптимизация гиперпараметров из урока 299 или эволюционные алгоритмы. Всюду, где агент вынужден сам выбирать, какие данные собрать дальше (а не пассивно получать фиксированный датасет, как в обучении с учителем), решение полагаться только на уже известное хорошее рискует зафиксироваться на локально хорошем, но глобально неоптимальном решении, а решение постоянно пробовать новое рискует так и не воспользоваться накопленным знанием в полной мере. Осознанное управление этим балансом — через $\varepsilon$-жадную стратегию, через постепенное затухание исследования, или через более тонкие методы вроде верхних доверительных границ (upper confidence bound) — часто оказывается более важным фактором успеха реального RL-проекта, чем выбор конкретной формулы обновления Q-значений.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Своими словами перечисли шесть основных компонентов RL-задачи (агент, среда, состояние, действие, награда, политика) и приведи для каждого пример из игры в шахматы против компьютера.

Задание 2: Дана последовательность наград агента за эпизод: $r_1=2$, $r_2=0$, $r_3=-1$, $r_4=5$. Посчитай дисконтированный return $G_0$ при $\gamma=0{,}5$.

Задание 3: Объясни своими словами, чем задача обучения с подкреплением принципиально отличается от обучения с учителем, даже если в обоих случаях модель получает числовой сигнал качества после предсказания.

Задание 4: В коридоре из пяти клеток (как в примере 1 первого раздела) агент стартует в клетке 3 и всегда идёт вправо. Награды: $-1$ за обычный шаг, $+10$ за выход в клетку 5. Посчитай суммарную (недисконтированную) награду за эпизод.

Задание 5: Своими словами объясни, что означает «марковское свойство», и приведи собственный пример состояния из повседневной жизни, которое это свойство нарушает.

Задание 6: Заполни таблицу переходов для одномерного коридора из 4 клеток (1–4), где клетка 4 терминальная с наградой $+5$, а обычный шаг стоит $-1$: посчитай $V$ для клеток 3, 2, 1 методом value iteration при $\gamma=1$ (без дисконтирования), считая, что агент всегда движется оптимально вправо.

Задание 7: Объясни своими словами разницу между функцией ценности состояния $V(s)$ и Q-функцией $Q(s,a)$.

Задание 8: Каким будет $G_t$, если $\gamma=0$? Объясни, какого агента такой выбор описывает.

Задание 9: Своими словами объясни, почему в $\varepsilon$-жадной стратегии обычно уменьшают $\varepsilon$ по ходу обучения, а не держат его постоянным.

Задание 10: В задаче о трёх игровых автоматах (multi-armed bandit) с истинными вероятностями выигрыша 0,2, 0,6 и 0,3 объясни, почему стратегия с $\varepsilon=0$ (чисто жадная) рискует никогда не найти лучший автомат.

Средние задания (11–20)

Задание 11: Дана последовательность наград $r_1=1$, $r_2=1$, $r_3=1$, $r_4=1$, $r_5=100$. Сравни $G_0$ при $\gamma=1$ и при $\gamma=0{,}5$, и объясни, как дисконтирование меняет относительный вес последней, крупной награды.

Задание 12: Для сетки $3\times3$ из основного текста урока (терминальная клетка $(3,3)$ с наградой $+10$, штраф $-1$ за обычный шаг, $\gamma=0{,}9$) посчитай $Q\big((2,2), \text{вправо}\big)$, используя уже вычисленное в уроке значение $V(2,3)=10$.

Задание 13: Объясни своими словами, почему Q-learning называют «безмодельным» (model-free) алгоритмом, и в чём его практическое преимущество перед value iteration, которое требует знания $P(s'\mid s,a)$ и $R(s,a)$ заранее.

Задание 14: Агент в состоянии $s$ выполняет действие $a$, получает награду $r=3$ и попадает в состояние $s'$, где текущие Q-значения — $Q(s',a_1)=2$, $Q(s',a_2)=5$, $Q(s',a_3)=1$. Текущее $Q(s,a)=4$, $\alpha=0{,}2$, $\gamma=0{,}9$. Посчитай обновлённое значение $Q(s,a)$.

Задание 15: Объясни своими словами, почему число состояний в шахматах (порядка $10^{47}$) или в го (порядка $10^{170}$) делает табличный Q-learning практически неприменимым и какая идея решает эту проблему.

Задание 16: Своими словами сформулируй, что такое политика $\pi$, и приведи пример двух разных политик для одной и той же задачи (сетка $3\times3$ из урока), одна из которых явно хуже другой.

Задание 17: В $\varepsilon$-жадной стратегии с 5 доступными действиями и $\varepsilon=0{,}25$ посчитай итоговую вероятность выбрать конкретное жадное (наилучшее по таблице) действие.

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

Задание 19: В примере с многоруким бандитом (три автомата с истинными вероятностями 0,3, 0,5, 0,4) объясни, почему увеличение общего числа попыток (эпизодов обучения) при фиксированном $\varepsilon>0$ со временем приближает оценки Q-значений к истинным вероятностям выигрыша, а не к случайным величинам.

Задание 20: Своими словами объясни аналогию между рекуррентной формулой уравнения Беллмана и рекуррентной формулой 0/1-рюкзака из урока 270 ($dp[i][w] = \max(dp[i-1][w],\ dp[i-1][w-\text{wt}_i]+\text{val}_i)$).

Продвинутые задания (21–30)

Задание 21: Реализуй на псевдокоде (Python-подобном) полный цикл обучения Q-learning с $\varepsilon$-жадной стратегией для произвольной дискретной среды с интерфейсом env.reset() и env.step(action).

Задание 22: Докажи (формальным рассуждением, не строгим математическим доказательством) корректность уравнения Беллмана для оптимальной Q-функции, опираясь на принцип оптимальности Беллмана из урока 270.

Задание 23: В сетке $4\times4$ (индексы от $(1,1)$ до $(4,4)$) с терминальной клеткой $(4,4)$, наградой $+20$ за вход в неё, штрафом $-1$ за обычный шаг и $\gamma=0{,}9$ посчитай $V(3,4)$ и $V(4,3)$ методом value iteration (клетки, соседние с терминальной).

Задание 24: Продолжая задание 23, посчитай $V(2,4)$, используя уже найденное $V(3,4)=20$.

Задание 25: Объясни своими словами, почему сходимость value iteration (повторяющееся применение уравнения Беллмана оптимальности ко всем состояниям) гарантирована математически, и какую роль в этой гарантии играет условие $\gamma<1$.

Задание 26: Спроектируй функцию награды для обучения RL-агента игре в «Flappy Bird» (игра, где птица должна пролетать между трубами, не задевая их) так, чтобы избежать проблемы sparse reward (слишком редкой награды).

Задание 27: Объясни своими словами, почему RLHF (Reinforcement Learning from Human Feedback) — это именно обучение с подкреплением, а не обучение с учителем, хотя исходные данные для него собирают люди-разметчики.

Задание 28: Дан вопрос: почему в задаче с высокой размерностью пространства состояний (например, изображение с экрана видеоигры как вход) Q-learning с явной таблицей принципиально не масштабируется, даже если формально число уникальных пиксельных комбинаций конечно?

Задание 29: Своими словами сформулируй, чем отличается ценность действия при использовании фиксированной, заранее заданной политики ($Q^\pi$) от ценности действия при оптимальной политике ($Q^*$), и почему цель Q-learning — приблизиться именно ко второй.

Задание 30: Объясни своими словами, почему AlphaGo не мог полагаться на чистый Q-learning или value iteration в их простейшей табличной форме, и какие дополнительные идеи (кратко, без деталей реализации) потребовались для игры в го на уровне чемпиона мира.

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

Путать обучение с подкреплением с обучением с учителем только потому, что в RLHF или в некоторых играх агент получает число, похожее на «метку». Ключевое отличие — не форма сигнала (число или категория), а его природа: готовый правильный ответ на конкретный вход (обучение с учителем) против отложенной, часто коллективной награды за последовательность действий, требующей дополнительного вывода о том, какие именно шаги привели к результату (RL).

Проектировать слишком разреженную (sparse) функцию награды, выдающую сигнал только в самом конце очень долгого эпизода. Агент, не получающий вообще никакой обратной связи на протяжении сотен или тысяч шагов, фактически обучается вслепую — как показано в разделе про задания (задание 26), решение почти всегда в добавлении плотных промежуточных наград за приближение к цели, а не в ожидании, что агент сам «догадается» найти редкую конечную награду методом чистого случайного блуждания.

Забывать про баланс exploration и exploitation и использовать чисто жадную стратегию ($\varepsilon=0$) с самого начала обучения. Как показано в примере с многоруким бандитом, такая стратегия рискует навсегда зафиксироваться на первом же случайно удачно оценённом варианте, так и не обнаружив по-настоящему лучший.

Задавать функцию награды, которая лишь приблизительно, а не точно отражает реально желаемое поведение, и удивляться проблеме reward hacking, когда агент находит формальную лазейку, максимизирующую число, но не решающую задачу по существу. Награда должна проектироваться настолько аккуратно, насколько это возможно, с явным продумыванием, какие нежелательные способы её максимизации теоретически существуют.

Забывать о том, что марковское свойство — это предположение, а не автоматическая гарантия. Если реальное состояние среды спроектировано неполным (агенту не хватает информации, доступной ранее в истории, для принятия оптимального решения прямо сейчас), никакой алгоритм обучения — ни Q-learning, ни его нейросетевые развития — не сможет компенсировать эту потерю информации самостоятельно.

Путать $Q^\pi$ (ценность при конкретной, возможно неоптимальной политике) и $Q^*$ (ценность при оптимальной политике) и не понимать, почему Q-learning со своим правилом обновления через $\max_{a'}Q(s',a')$ сходится именно к $Q^*$ независимо от того, какой политикой агент фактически исследует среду в процессе обучения.

Пытаться применить табличный Q-learning напрямую к задачам с огромным или непрерывным пространством состояний (изображения, показания сенсоров робота) без перехода к функциональному приближению (нейросети). Табличный подход принципиально не масштабируется за пределы задач с относительно небольшим, конечным и перечислимым числом состояний.

Главное запомнить

  • Обучение с подкреплением (Reinforcement Learning, RL) — третья парадигма машинного обучения наравне с обучением с учителем и без учителя: агент учится через взаимодействие со средой и отложенную обратную связь в виде награды, а не через готовые правильные ответы или поиск структуры в статичных данных.

  • Формальные компоненты RL-задачи — агент, среда, состояние, действие, награда и политика — точно описывают, кто принимает решения, где, на основе какой информации, каким набором выборов и с каким сигналом качества.

  • Марковский процесс принятия решений (MDP) — строгая математическая модель RL-задачи, а марковское свойство означает, что будущее зависит только от текущего состояния и действия, а не от всей предыдущей истории.

  • Функция ценности $V(s)$ и Q-функция $Q(s,a)$ оценивают долгосрочную, а не только немедленную выгоду от нахождения в состоянии или выполнения действия, учитывая всю дальнейшую траекторию агента.

  • Уравнение Беллмана — прямой математический родственник рекуррентной формулы динамического программирования из урока 270: ценность текущего состояния выражается через немедленную награду плюс дисконтированную ценность следующего состояния, вместо перебора всех возможных бесконечных траекторий целиком.

  • Q-learning — безмодельный (model-free) алгоритм, обучающий Q-функцию напрямую из наблюдаемого опыта взаимодействия со средой, без явного знания функции переходов или функции награды заранее.

  • Баланс исследования и использования (exploration vs exploitation) — центральная дилемма RL: полагаться только на уже проверенное хорошее рискует застрять в локальном оптимуме, а пробовать только новое — не пользоваться накопленным знанием; $\varepsilon$-жадная стратегия с постепенно затухающим $\varepsilon$ — стандартный практический компромисс.

  • Табличные методы принципиально не масштабируются на задачи с огромным или непрерывным пространством состояний (шахматы, го, изображения); переход к нейросетевому приближению Q-функции или политики (Deep Q-Network и его развития) снимает это ограничение.

  • RLHF (Reinforcement Learning from Human Feedback) — обучение с подкреплением на основе обратной связи людей — этап дообучения, превращающий сырую языковую модель, предсказывающую следующий токен, в помощника вроде ChatGPT или Claude, стремящегося быть полезным и следовать инструкциям.

  • AlphaGo и подобные системы демонстрируют, что чистое RL, объединённое с глубокими нейросетями и направленным поиском, способно превзойти человека в задачах с пространством состояний, на порядки превышающим число атомов во Вселенной.

Связь с темами курса

Самая прямая и явная связь этого урока — с уроком 270 про динамическое программирование. Уравнение Беллмана носит имя того же самого Ричарда Беллмана, который в 1950-х годах ввёл сам термин «динамическое программирование», работая над задачами многошагового оптимального управления в RAND. Рекуррентная формула ДП для 0/1-рюкзака, $dp[i][w] = \max\big(dp[i-1][w],\ dp[i-1][w-\text{wt}_i]+\text{val}_i\big)$, и уравнение Беллмана оптимальности для RL, $V^*(s)=\max_a\big[R(s,a)+\gamma V^*(s')\big]$, — это не просто похожие формулы, а буквально одна и та же математическая структура: значение текущего «состояния» строится как максимум по вариантам выбора от немедленного вклада плюс уже известный оптимум для следующего, более простого «состояния». Value iteration, разобранная в этом уроке на примере сетки $3\times3$, — это, по сути, та же самая табуляция, что заполняла таблицы Фибоначчи и рюкзака в уроке 270, только применённая к бесконечному (в общем случае) пространству состояний среды вместо конечного массива индексов, и повторяемая итеративно до сходимости вместо однократного прохода слева направо.

Вторая важная связь — с уроком 344 про BERT, GPT и большие языковые модели, который закончился обещанием подробнее разобрать RLHF (Reinforcement Learning from Human Feedback). Современный пайплайн обучения таких моделей, как Claude или ChatGPT, состоит из нескольких этапов: сначала self-supervised предобучение (самообучение на неразмеченных данных) на огромном неразмеченном корпусе текста, затем supervised fine-tuning (дообучение с учителем) на размеченных парах «инструкция — качественный ответ», а затем — этап RLHF. На этом финальном этапе люди сравнивают пары ответов модели и отмечают, какой лучше; на этих сравнениях обучается отдельная модель вознаграждения, дающая приближённую оценку «насколько этот ответ понравился бы человеку», а сама языковая модель дальше дообучается методами RL так, чтобы максимизировать ожидаемую оценку этой модели вознаграждения. В терминах этого урока: языковая модель — это агент, диалог с пользователем — среда, последовательность генерируемых токенов — действия, оценка модели вознаграждения — награда, а сама языковая модель, отображающая текущий контекст в распределение вероятностей над следующим токеном, — это в точности политика $\pi(a\mid s)$. Именно RLHF, а не одно лишь supervised fine-tuning, оказался ключевым шагом, который научил модели следовать неявным, трудноформализуемым человеческим предпочтениям — быть полезными, безопасными и честными способами, которые невозможно исчерпывающе описать конечным набором размеченных примеров правильных ответов.

Третья связь — с уроком 299 про байесовскую оптимизацию, где функция приобретения Expected Improvement явно балансировала между exploitation (доверие хорошему прогнозу суррогатной модели) и exploration (готовность рискнуть ради высокой неопределённости) в одной формуле. В этом уроке та же самая дилемма встречается в ядре Q-learning в виде $\varepsilon$-жадной стратегии, а её крайний, наиболее прозрачный частный случай — многорукий бандит (multi-armed bandit) — вообще устраняет всю остальную сложность RL (состояния, переходы, отложенные награды), оставляя только чистый компромисс между исследованием и использованием. Понимание того, что это один и тот же фундаментальный компромисс, проявляющийся в разных областях — от подбора гиперпараметров модели до обучения игрового агента, — экономит время при столкновении с новой, на первый взгляд непохожей задачей: если задача требует самому выбирать, какие данные собрать дальше, а не пассивно принимать фиксированный датасет, скорее всего где-то внутри неё прячется тот же самый компромисс exploration/exploitation.

Интересные факты

Победа AlphaGo над Ли Седолем в марте 2016 года запомнилась не только итоговым счётом 4:1 в пользу машины, но и конкретным, знаменитым 37-м ходом во второй партии — ходом, который профессиональные комментаторы сначала сочли ошибкой программы, настолько нетипичным он выглядел для человеческой игровой практики; лишь спустя несколько ходов стало ясно, что это был блестящий стратегический манёвр, до которого столетия человеческой игровой традиции в го попросту не додумались. Это стало одним из первых широко обсуждаемых публичных примеров того, что RL-система, обучавшаяся преимущественно через самостоятельную игру с собой (self-play), способна находить стратегии, отличающиеся от всего накопленного человечеством игрового опыта, а не просто копирующие его на более высоком уровне мастерства.

Более поздняя система той же команды DeepMind, AlphaZero (2017), пошла ещё дальше и отказалась от использования баз данных партий мастеров-людей вообще: она обучалась игре в го, шахматы и сёги (японские шахматы) исключительно через самостоятельную игру с собой, начиная со случайной, ничего не умеющей политики, и всего за несколько часов обучения на мощном кластере превзошла все существовавшие ранее шахматные движки, включая созданные десятилетиями ручной инженерной работы и явно закодированных шахматных знаний.

Термин «многорукий бандит» (multi-armed bandit), встречавшийся в этом уроке как упрощённый пример дилеммы exploration/exploitation, — это отсылка к игровым автоматам в казино («одноруким бандитам», one-armed bandits, из-за характерного рычага сбоку), а «многорукий» — гипотетический автомат сразу с несколькими рычагами, каждый из которых выплачивает выигрыш с неизвестной заранее вероятностью, что и есть максимально упрощённая, но математически точная модель задачи выбора между уже проверенным и ещё не опробованным вариантом.

Reinforcement Learning from Human Feedback как метод дообучения языковых моделей не был изобретён специально для ChatGPT — сама общая идея обучать политику на основе предпочтений людей, а не на основе явно размеченных правильных ответов, разрабатывалась исследователями RL ещё в середине 2010-х годов применительно к куда более простым задачам, например к обучению роботизированной руки выполнять движения, которые люди-наблюдатели оценивали как «более похожие на желаемое», сравнивая пары коротких видеозаписей поведения агента.

Лайфхаки

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

Начинай с максимально простой, «игрушечной» версии среды (как сетка $3\times3$ или коридор из пяти клеток в этом уроке), где можно вручную посчитать правильный ответ через value iteration, и только после того, как алгоритм на ней сходится к ожидаемому результату, переходи к более сложной и реалистичной версии задачи. Отладка RL-алгоритма на среде, где невозможно вручную проверить правильность результата, значительно сложнее, чем на игрушечном примере с заранее известным ответом.

Логируй не только итоговую награду за эпизод, но и значение $\varepsilon$, темп обучения и, если возможно, значения нескольких характерных Q-значений на протяжении обучения — резкие скачки или, наоборот, полное отсутствие изменений в этих величинах часто указывают на проблему (слишком высокий или низкий $\alpha$, застрявшее исследование) значительно раньше, чем итоговая награда за эпизод успевает её отразить.

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

Не пытайся сразу применять глубокие нейросетевые методы (DQN и его развития) там, где задача помещается в разумную табличную Q-таблицу — табличный Q-learning проще отлаживать, быстрее сходится на маленьких задачах и даёт математические гарантии сходимости, которых у нейросетевых приближений в общем случае нет; переходи к нейросетям только тогда, когда пространство состояний действительно делает табличный подход невозможным.

Если результат обучения кажется неожиданно плохим, в первую очередь проверь баланс exploration/exploitation, прежде чем менять саму формулу обновления или архитектуру модели: слишком быстро затухающий $\varepsilon$ (или изначально слишком низкий) — одна из самых частых причин, по которой агент «застревает» в посредственной, но не оптимальной политике, и эта проблема решается настройкой одного числового параметра, а не переписыванием алгоритма.

Ты только что прошёл путь от простого наблюдения — крыса в лабиринте запоминает, какие повороты приводят к сыру, — до строгой математической модели, которая учит роботов ходить, побеждает чемпионов мира по го и превращает необученную языковую модель в полезного, следующего инструкциям помощника. Это, пожалуй, один из самых наглядных примеров во всём курсе, как психологическая интуиция XX века (закон эффекта Торндайка), инженерная теория оптимального управления (уравнение Беллмана) и алгоритмическая техника (динамическое программирование из урока 270) сходятся в единый, работающий на практике математический аппарат. Дальше в курсе, изучая перенос обучения (transfer learning) в следующем уроке, ты продолжишь исследовать, как модели, обученные на одной задаче, переносят накопленные знания на другие, — и обучение с подкреплением, освоенное сегодня, останется одним из самых мощных инструментов в этом общем наборе.

Понял тему? Закрепи в боте! 🚀

Попрактикуйся на задачах и получи персональные рекомендации от AI

💪 Начать тренировку
💬 Есть вопрос? Спроси бота!