Модуль 2. Состояние, ценность и уравнения Беллмана

Версия материала: 2026.7
Фактический снимок: 2026-08-04
Язык: RU
Основная практика: уровень A — браузер, Python, NumPy и центральный процессор (CPU)
Структура: 4 урока, 20 шагов
Ориентировочное время: 8–12 часов вместе с основным практикумом

В Модуле 1 мы описывали RL как цикл выбора действий и обратной связи. Теперь возникает более трудный вопрос: как оценить состояние или действие до того, как станет известен окончательный результат? Ответ начинается с правильно выбранного состояния, продолжается функциями ценности и приводит к уравнениям Беллмана.

Предварительный курс по классическому RL по-прежнему не требуется. Новые понятия сначала объясняются словами, затем записываются формально и только после этого связываются с LLM. Читатель, уже знакомый с RL, может быстрее пройти §§2.1.1–2.1.4 и сосредоточиться на границах токеновой модели, различии завершения и усечения эпизода, точных условиях сходимости и связях с современным дообучением LLM.

Цели модуля. После прохождения вы сможете:

1. проверить, содержит ли состояние достаточно информации для марковской модели;
2. отличить состояние от наблюдения, а завершение задачи — от технического усечения траектории;
3. вычислять $V^\pi$, $Q^\pi$ и преимущество $A^\pi$ и объяснять их смысл для генерации LLM;
4. вывести уравнение ожидания Беллмана из рекуррентности накопленной награды;
5. решать небольшую табличную задачу принятия решений как систему линейных уравнений или итерациями;
6. различать оценивание методом Монте-Карло, одношаговое обучение по временным различиям и $n$-шаговые цели;
7. объяснять различие двух табличных методов управления через политику поведения и целевую политику;
8. распознавать смещение максимизации и объяснять, как разделение выбора и оценивания его уменьшает;
9. воспроизвести численные эксперименты на Gridworld, FrozenLake, коридоре и CliffWalking.

Публичный вычислительный практикум находится в исполняемой практике. Он содержит точное оценивание политики, итерацию ценности, MC, TD(0), многошаговый TD, Q-learning, SARSA и Double Q-learning. Для основного маршрута достаточно NumPy, Matplotlib и CPU; GPU не нужен.

---

Практический маршрут. После лекции идут оцениваемые задания, решения, открывающиеся после попытки, и исполняемая практика. Само объяснение остаётся самодостаточным.

Урок 2.1. От истории к состоянию, затем к ценности

Урок 2.1. От истории к состоянию, затем к ценности

1. Зачем вообще нужно состояние
2. Конечный MDP и соглашение о награде
3. Завершение задачи и техническое усечение — не одно и то же
4. Три функции ценности: V, Q и преимущество A
5. Как читать ценности для LLM

далее — 7 проверочных шагов

Шаг 2.1.1 — Зачем вообще нужно состояние

Полная история взаимодействия к моменту $t$ может быть очень длинной:

$$H_t=(O_0,A_0,R_1,O_1,\ldots,A_{t-1},R_t,O_t).$$

Здесь важно сразу развести два употребления слова «состояние».

1. Состояние среды — переменная, относительно которой будущая динамика обладает марковским свойством. Оно не обязано быть «сжатием истории»: у физической среды состояние может существовать независимо от того, что успел увидеть агент.
2. Состояние или представление агента — то, что агент строит из доступной истории: полный журнал, окно наблюдений, вектор памяти рекуррентной сети, содержимое внешней памяти. Такое представление является лишь кандидатом на достаточное состояние.

Пусть $S_t=f(H_t)$ — выбранное агентом представление. Оно достаточно для одношагового предсказания, если

$$P(S_{t+1},R_{t+1}\mid H_t,A_t) = P(S_{t+1},R_{t+1}\mid S_t,A_t).$$

Формула говорит не о том, что мир «забыл прошлое». Она говорит, что после фиксации $S_t$ и $A_t$ более ранняя история не должна дополнительно менять распределение следующего состояния и награды. Если меняет, представление потеряло существенную информацию.

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

Наблюдение $O_t$ может быть неполным. Если доступное состояние содержит всю существенную информацию, задачу можно описывать как марковский процесс принятия решений (Markov decision process, MDP). Если скрытая часть среды влияет на будущие переходы, естественной моделью становится частично наблюдаемый марковский процесс принятия решений (partially observable Markov decision process, POMDP). Тогда агент использует историю наблюдений, внутреннюю память или распределение убеждений о скрытом состоянии.

Для чистой авторегрессионной генерации можно положить

$$S_t=(x,y_{<t}), \qquad A_t=y_t, \qquad S_{t+1}=(x,y_{\le t}).$$

Если переход действительно состоит только в добавлении выбранного токена, параметры модели и правила декодирования фиксированы, а условие остановки определяется видимым префиксом, полный префикс является достаточным состоянием. Случайность сэмплирования при этом не нарушает марковское свойство: она относится к политике $\pi(a\mid s)$, а после фиксации выбранного токена переход к следующему префиксу детерминирован.

Система с браузером, файловой сессией, пользователем или внешним инструментом может иметь скрытое состояние. При фиксированных модели среды и начальном распределении полная история $H_t$ может служить растущим информационным состоянием: она определяет условное распределение будущих наблюдений и наград, даже если не раскрывает фактическое состояние мира. Распределение убеждений $b_t(s)=P(s_t=s\mid H_t)$ сжимает эту историю для предсказания в модели POMDP. Два возможных скрытых состояния при одной истории могут давать разные исходы; это совместимо с одним условным вероятностным законом.

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

Практический тест достаточности. Могут ли две полные истории, сжатые в одну запись $S_t$, при одинаковом действии давать разные условные распределения следующего наблюдения и награды? Если да, представление потеряло существенную информацию. Разные случайные исходы при одном и том же условном распределении марковское свойство не нарушают.

Архитектурный контекст: Modern LLMs, Модуль 18 «Агенты и работа с инструментами» (modern_llms.module_16_agents), подробнее разбирает устройство таких систем. Здесь нам достаточно различия между состоянием среды, наблюдением и внутренним представлением агента.

---

Шаг 2.1.2 — Конечный MDP и соглашение о награде

Конечный MDP зададим набором

$$\mathcal{M} = (\mathcal{S},\mathcal{A},P,P_R,\rho_0,\gamma).$$

Здесь:

• $\mathcal{S}$ — множество состояний;
• $\mathcal{A}$ — множество действий;
• $P(s'\mid s,a)$ — вероятность следующего состояния;
• $P_R(r\mid s,a,s')$ — распределение награды на переходе;
• $\rho_0(s)$ — начальное распределение;
• $\gamma\in[0,1]$ — фактор дисконтирования.

В табличных вычислениях удобно хранить не всё распределение награды, а её условное среднее:

$$\bar r(s,a,s') = \mathbb{E}[R_{t+1}\mid S_t=s,A_t=a,S_{t+1}=s'].$$

Ожидаемая награда $\bar r(s,a)=\mathbb{E}[R_{t+1}\mid s,a]$ при интегрируемой награде всегда определяется усреднением: $\bar r(s,a)=\sum_{s'}P(s'\mid s,a)\bar r(s,a,s')$. Для этой маргинализации не нужна условная независимость. Дополнительным предположением было бы равенство $\bar r(s,a,s')=\bar r(s,a)$ для каждого достижимого следующего состояния. Аналогично, $\bar r(s)$ может означать усреднение по действиям заданной политики, тогда как независимость модели награды от действия — более сильное условие. В модуле основной остаётся форма с условием на переход.

Политика $\pi(a\mid s)$ не входит в динамику среды. Один и тот же MDP допускает разные политики. Совместное распределение одного перехода при фиксированной политике раскладывается как

$$P(A_t=a,S_{t+1}=s',R_{t+1}=r\mid S_t=s) = \pi(a\mid s)P(s'\mid s,a)P_R(r\mid s,a,s').$$

Эта факторизация будет полезна дальше: уравнение Беллмана усредняет сначала по действиям политики, затем по переходам и наградам среды.

В эпизодической задаче взаимодействие достигает терминального состояния. В продолжающейся задаче естественного терминала может не быть; тогда при бесконечном горизонте обычно используют $\gamma<1$ или другую постановку, обеспечивающую конечность цели.

В этом модуле награда относится к переходу. Если агент получает $+1$ при входе в цель, это значение остаётся в $R_{t+1}$, даже когда $V(s_{terminal})=0$. Нулевая ценность терминала означает отсутствие дальнейшего продолжения, а не отмену последней награды.

---

Шаг 2.1.3 — Завершение задачи и техническое усечение — не одно и то же

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

1. Завершение (termination) означает, что достигнуто терминальное состояние самой задачи: цель выполнена, агент проиграл, ответ завершён токеном конца последовательности. В заданном MDP продолжения после перехода нет.
2. Усечение (truncation) означает, что сбор данных остановили внешним ограничением: закончился бюджет шагов, время стенда, длина буфера или место в пакете. Сама задача могла бы продолжаться.

Удобно ввести маску продолжения

$$m_t=\mathbf 1\{\text{переход }t\text{ не терминальный}\}.$$

Тогда одношаговая цель записывается одной строкой:

$$y_t=R_{t+1}+\gamma m_tV(S_{t+1}).$$

Отсюда получаются два случая:

$$y_t= \begin{cases} R_{t+1}, & \text{если задача завершилась},\\[4pt] R_{t+1}+\gamma V(S_{t+1}), & \text{если сбор лишь усечён и процесс продолжается}. \end{cases}$$

Если временной лимит является частью самой задачи, оставшийся бюджет нужно включить в состояние. Тогда исчерпание бюджета может быть настоящим терминальным условием. Если лимит введён только для удобства сбора данных, обнулять продолжение обычно ошибочно.

Для LLM различие видно особенно хорошо:

• токен конца последовательности (end of sequence, EOS) обычно выражает завершение ответа;
• остановка по max_tokens часто является усечением, если более длинная генерация всё ещё имела бы смысл;
• в задаче «дать ответ не более чем за 256 токенов» тот же лимит входит в определение цели и может быть терминальным исходом;
• остановка роллаута из-за заполнения пакета — свойство инфраструктуры, а не задачи.

Смешение двух случаев вносит систематическое смещение. Если истинная ценность продолжения положительна, ошибочное обнуление усечённой траектории занижает цель; если отрицательна — завышает. Поэтому современные интерфейсы Gymnasium передают terminated и truncated раздельно. Само наличие двух флагов, однако, не снимает ответственность с автора среды: нужно правильно решить, является ли лимит частью задачи.

---

Шаг 2.1.4 — Три функции ценности: V, Q и преимущество A

Зафиксируем политику $\pi$ и накопленную награду

$$G_t=\sum_{k=0}^{\infty}\gamma^k R_{t+k+1}$$

для продолжающейся задачи либо соответствующую конечную сумму для эпизода.

Ценность состояния — ожидаемый итог, если начать в $s$ и далее следовать политике:

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

Ценность действия — ожидаемый итог, если первое действие зафиксировать, а затем следовать политике:

$$Q^\pi(s,a) = \mathbb{E}_\pi[G_t\mid S_t=s,A_t=a].$$

Поэтому ценность состояния является средним значением $Q^\pi$ по действиям политики:

$$V^\pi(s) = \sum_a \pi(a\mid s)Q^\pi(s,a).$$

Преимущество (advantage) сравнивает действие со средним поведением той же политики:

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

Из определения сразу следует

$$\sum_a \pi(a\mid s)A^\pi(s,a)=0.$$

Положительное $A^\pi(s,a)$ означает «лучше среднего действия текущей политики в этом состоянии», а не «объективно хорошее действие при любой политике».

Есть и полезная инвариантность. Если ко всем $Q(s,a)$ в одном состоянии прибавить одну и ту же константу $c(s)$, то пересчитанное $V(s)$ сдвинется на ту же величину, а $A(s,a)$ не изменится:

$$Q'(s,a)=Q(s,a)+c(s), \quad V'(s)=V(s)+c(s), \quad A'(s,a)=A(s,a).$$

Это утверждение относится к сдвигу оценок действий в фиксированном состоянии. Оно не означает, что произвольное изменение функции награды оставляет преимущества неизменными во всём MDP.

Для терминального состояния в принятом соглашении $V^\pi(s_{terminal})=0$. Финальная награда ответа или эпизода при этом относится к переходу в терминал и уже входит в $G_t$.

---

Шаг 2.1.5 — Как читать ценности для LLM

В токеновой модели состояние — запрос и уже созданный префикс, а действие — следующий токен. Тогда:

• $Q^\pi(s,a)$ — ожидаемая итоговая награда, если сейчас выбрать токен $a$, а дальше продолжать по $\pi$;
• $V^\pi(s)$ — средняя итоговая награда продолжения, полученного из текущего распределения токенов;
• $A^\pi(s,a)$ — насколько выбор токена лучше или хуже среднего выбора текущей политики.

Маленькое дерево префиксов помогает прочитать определения без нейросетевого шума. Пусть после слова «потому» политика с вероятностью $0.7$ выбирает «проверить» и получает награду $1$, а с вероятностью $0.3$ выбирает «пропустить» и получает $0.4$. Тогда

$$V^\pi(\text{``потому''})=0.7\cdot1+0.3\cdot0.4=0.82.$$

Если альтернативный префикс «угадаю» имеет ценность $-0.10$, а в пустом префиксе политика выбирает «потому» с вероятностью $0.55$, то

$$V^\pi(\varnothing)=0.55\cdot0.82+0.45\cdot(-0.10)=0.406.$$

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

В реальной модели оценивание трудно: пространство префиксов огромно, итоговая награда часто появляется только после полного ответа, а два почти одинаковых рассуждения могут получить разные оценки. Поэтому нейросетевой RL использует аппроксиматоры ценности, модели оценки промежуточных шагов или методы без отдельного обучаемого критика.

Здесь легко сделать слишком сильный вывод о групповой относительной оптимизации политики (group relative policy optimization, GRPO). В исходной постановке DeepSeekMath для одного запроса генерируется группа полных ответов, а награды нормируются внутри группы. Это даёт относительный сигнал без отдельной модели ценности. Но выборочная статистика конечной группы относится к запросу и полным ответам; она не является точным $V^\pi(s_t)$ для каждого токенового префикса. Более поздние варианты GRPO меняют нормировку, агрегацию и распределение сигнала по токенам, поэтому название метода само по себе не фиксирует все детали.

Главный мост. Функция ценности отвечает на вопрос: «чего в среднем стоит продолжение, которого мы ещё не увидели целиком?» Критик в PPO, групповая базовая оценка в GRPO и оценка частичного рассуждения при поиске приближают эту идею разными способами. Они не являются одной математической конструкцией.

Дальнейшее углубление: Модуль 4 (rl_llm.module_04_policy_gradients) свяжет преимущество с градиентом политики и GAE; Модуль 9 (rl_llm.module_09_rlvr_grpo) подробно разберёт GRPO и его варианты. Modern LLMs, Модуль 15 «Модели рассуждения и вычисления во время инференса (test-time compute)» (modern_llms.module_13_reasoning), даёт архитектурный контекст для оценки промежуточных шагов.

---

Урок 2.2. Уравнения Беллмана: оценивание и улучшение

Урок 2.2. Уравнения Беллмана: оценивание и улучшение

1. Одношаговое разложение накопленной награды
2. Точное оценивание политики как линейная система
3. Оптимальность и точное условие сжатия
4. Оценивание, улучшение и обобщённая итерация политики
5. Воспроизводимый пример: FrozenLake

далее — 6 проверочных шагов

Шаг 2.2.1 — Одношаговое разложение накопленной награды

В Модуле 1 мы получили рекуррентность

$$G_t=R_{t+1}+\gamma G_{t+1}.$$

Возьмём условное математическое ожидание при $S_t=s$ и фиксированной политике $\pi$. Получим уравнение ожидания Беллмана:

$$V^\pi(s) = \sum_a \pi(a\mid s) \sum_{s'}P(s'\mid s,a) \left[ \bar r(s,a,s')+\gamma V^\pi(s') \right].$$

Терминальные состояния можно оставить в сумме, если договориться, что их продолжение равно нулю. Награда на переходе в терминал при этом сохраняется в $\bar r(s,a,s')$.

Прочитаем формулу словами:

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

Для $Q^\pi$ первое действие уже зафиксировано:

$$Q^\pi(s,a) = \sum_{s'}P(s'\mid s,a) \left[ \bar r(s,a,s') + \gamma\sum_{a'}\pi(a'\mid s')Q^\pi(s',a') \right].$$

Введём оператор Беллмана фиксированной политики:

$$(T_\pi V)(s) = \sum_a \pi(a\mid s) \sum_{s'}P(s'\mid s,a) \left[ \bar r(s,a,s')+\gamma V(s') \right].$$

Истинная функция ценности является его неподвижной точкой:

$$V^\pi=T_\pi V^\pi.$$

Слово «оператор» означает правило, которое берёт целый вектор оценок и строит новый вектор одношаговых оценок.

Что уравнение Беллмана не делает само. Оно не выбирает способ сбора данных, не задаёт нейросетевую архитектуру и не гарантирует, что градиентный оптимизатор найдёт неподвижную точку. Это условие согласованности, из которого строятся разные точные и приближённые алгоритмы.

---

Шаг 2.2.2 — Точное оценивание политики как линейная система

При фиксированной политике можно объединить действия и получить:

$$P_\pi(s,s') = \sum_a\pi(a\mid s)P(s'\mid s,a),$$ $$r_\pi(s) = \sum_a\pi(a\mid s) \sum_{s'}P(s'\mid s,a)\bar r(s,a,s').$$

Уравнение Беллмана становится векторным:

$$V^\pi=r_\pi+\gamma P_\pi V^\pi,$$

а значит,

$$(I-\gamma P_\pi)V^\pi=r_\pi.$$

Для конечного дисконтированного MDP с $0\le\gamma<1$ матрица $I-\gamma P_\pi$ обратима, поэтому решение единственно. При $\gamma=1$ общая гарантия через дисконтирование исчезает. В эпизодической задаче систему всё же можно решить по нетерминальным состояниям, если при фиксированной политике терминал достигается почти наверное и соответствующая матрица невырождена.

Классический пример — поле $4\times4$ с терминалами в левом верхнем и правом нижнем углах, наградой $-1$ за каждый шаг и равновероятными движениями. Точное решение для $\gamma=1$:

$$V^\pi= \begin{bmatrix} 0 & -14 & -20 & -22\\ -14 & -18 & -20 & -20\\ -20 & -20 & -18 & -14\\ -22 & -20 & -14 & 0 \end{bmatrix}.$$

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

Для приближённой функции $\widehat V$ полезен остаток Беллмана:

$$e_\pi= T_\pi\widehat V-\widehat V.$$

Нулевой остаток означает точное выполнение уравнения, но малый остаток нужно интерпретировать с учётом $\gamma$. При $\gamma<1$:

$$\|\widehat V-V^\pi\|_\infty \le \frac{\|e_\pi\|_\infty}{1-\gamma}.$$

Когда $\gamma$ близок к единице, даже небольшой одношаговый остаток может соответствовать заметной ошибке длинного горизонта.

---

Шаг 2.2.3 — Оптимальность и точное условие сжатия

Оценивание отвечает на вопрос «насколько хороша фиксированная политика?». Управление требует другого вопроса: «какое действие выбрать лучше всего?»

Оптимальная функция ценности удовлетворяет

$$V^*(s) = \max_a \sum_{s'}P(s'\mid s,a) \left[ \bar r(s,a,s')+\gamma V^*(s') \right].$$

Определим оператор оптимальности:

$$(T_*V)(s) = \max_a \sum_{s'}P(s'\mid s,a) \left[ \bar r(s,a,s')+\gamma V(s') \right].$$

При $0\le\gamma<1$ оба оператора являются $\gamma$-сжатиями в норме максимума. Для $T_*$ ключевой шаг таков:

$$\begin{aligned} |(T_*V)(s)-(T_*W)(s)| &\le \max_a \left| \gamma\sum_{s'}P(s'\mid s,a)(V(s')-W(s')) \right|\\ &\le \gamma\|V-W\|_\infty. \end{aligned}$$

После максимизации по состояниям:

$$\|T_*V-T_*W\|_\infty \le \gamma\|V-W\|_\infty.$$

Отсюда следует единственность неподвижной точки и геометрическая сходимость итераций $V_{k+1}=T_*V_k$.

Граница результата существенна. При $\gamma=1$ коэффициент сжатия равен единице, поэтому это доказательство уже не даёт сходимость. Некоторые конечные эпизодические задачи при $\gamma=1$ всё равно корректно решаются методами динамического программирования, но для этого нужны дополнительные условия. Например, в постановке стохастического кратчайшего пути должна существовать политика, которая из каждого релевантного состояния достигает терминала почти наверное за конечное ожидаемое число шагов; незавершающиеся политики нельзя оставлять конкурентоспособными как будто они имеют обычную конечную стоимость. Одной фразы «в задаче есть терминал» недостаточно. Поэтому утверждение «оператор Беллмана всегда является строгим сжатием» без указания режима неверно.

---

Шаг 2.2.4 — Оценивание, улучшение и обобщённая итерация политики

Из уравнений Беллмана получаются два чередующихся действия.

1. Оценивание политики: приблизить $V^\pi$ для текущей $\pi$.
2. Улучшение политики: выбирать действия, максимизирующие одношаговую оценку

$$Q(s,a)= \sum_{s'}P(s'\mid s,a) \left[ \bar r(s,a,s')+\gamma V(s') \right].$$

Если оценивание доводить до сходимости, а затем делать жадное улучшение, получается итерация политики (policy iteration). Если на каждом проходе сразу применять максимум, получается итерация ценности (value iteration):

$$V_{k+1}(s)=\max_a Q_k(s,a).$$

Более общий принцип называется обобщённой итерацией политики (generalized policy iteration, GPI): оценивание и улучшение могут быть неполными, асинхронными и выполняться с разной скоростью, но оба процесса постепенно приводят политику и её оценку к согласованности.

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

---

Шаг 2.2.5 — Воспроизводимый пример: FrozenLake

В module_2_reference.py построена собственная NumPy-версия FrozenLake $4\times4$ со скользкими переходами. В каждой клетке выбранное направление и два боковых отклонения имеют вероятность $1/3$. Лунки и цель терминальны. Награда $1$ выдаётся только на переходе в цель.

Пусть $T\ge1$ — число переходов до окончания эпизода, то есть до цели или лунки. Поскольку единичная награда выдаётся только на переходе в цель, успешная траектория вносит в $G_0$ величину $\gamma^{T-1}$, а неуспешная — ноль. Поэтому для оптимального поведения

$$V^*(s) = \mathbb E\!\left[ \gamma^{T-1}\mathbf 1\{\text{цель достигнута}\} \mid S_0=s \right].$$

При $\gamma=0.9$ это не простая вероятность успеха: раннее достижение цели имеет больший вес, чем позднее.

from module_2_reference import build_frozen_lake_4x4, value_iteration

P, R, terminal = build_frozen_lake_4x4()
V, sweeps = value_iteration(P, R, gamma=0.9, terminals=terminal)
print(sweeps)
print(V.reshape(4, 4))

При допуске $10^{-10}$ синхронная итерация ценности из нулевого вектора выполняет 145 полных проходов и даёт

[[0.068891 0.061415 0.074410 0.055807]
 [0.091855 0.000000 0.112208 0.000000]
 [0.145436 0.247497 0.299618 0.000000]
 [0.000000 0.379936 0.639020 0.000000]]

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

Число 145 — свойство этого протокола: модели переходов, нумерации действий, $\gamma$, нулевой инициализации, синхронных обновлений и критерия остановки. Асинхронный порядок, другой допуск или другое $\gamma$ изменят число проходов.

Почему табличный алгоритм нужен в курсе про LLM? Не потому, что мы собираемся хранить таблицу для всех префиксов. Он делает видимыми три идеи, которые сохраняются при масштабировании:

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

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

---

Урок 2.3. Оценивание без модели: от полной траектории к бутстрэппингу

Урок 2.3. Оценивание без модели: от полной траектории к бутстрэппингу

1. Задача предсказания по собранным траекториям
2. Метод Монте-Карло
3. Один наблюдённый шаг и оценка продолжения
4. Многошаговая цель соединяет MC и TD
5. Коридор: сравниваем оценки, а не лозунги

далее — 6 проверочных шагов

Шаг 2.3.1 — Задача предсказания по собранным траекториям

До сих пор мы предполагали, что известны $P$ и $\bar r$. В реальной среде агент обычно видит только выборку переходов

$$S_t,A_t,R_{t+1},S_{t+1}.$$

Задача предсказания (prediction) состоит в оценивании $V^\pi$ или $Q^\pi$ для фиксированной политики по данным взаимодействия, без явной таблицы динамики.

Любой метод такого рода выбирает целевое значение $Y_t$ и приближает к нему текущую оценку. Для табличного $V$ типичное обновление:

$$V(S_t) \leftarrow V(S_t)+\alpha\bigl(Y_t-V(S_t)\bigr),$$

где $\alpha$ — размер шага. Методы различаются прежде всего тем, что берут в качестве $Y_t$.

• Полная наблюдённая накопленная награда почти не опирается на текущую оценку, но требует дождаться конца эпизода.
• Одношаговая цель доступна сразу, но использует ещё не точное $V(S_{t+1})$.
• Промежуточные $n$-шаговые цели используют часть наблюдённых наград и затем выполняют бутстрэппинг.

Бутстрэппинг (bootstrapping) означает, что оценка обновляется с помощью другой текущей оценки. Это не то же самое, что статистический бутстрэп с повторной выборкой.

---

Шаг 2.3.2 — Метод Монте-Карло

Метод Монте-Карло (Monte Carlo, MC) использует фактически наблюдённую накопленную награду:

$$Y_t^{\mathrm{MC}}=G_t.$$

Для первого посещения состояния в каждом эпизоде можно хранить среднее всех последующих $G_t$:

$$V_n(s)=\frac{1}{n}\sum_{i=1}^{n}G^{(i)}(s).$$

Если эпизоды действительно получены фиксированной политикой, завершение корректно, а накопленная награда имеет конечное ожидание, это обычное выборочное среднее наблюдений с математическим ожиданием $V^\pi(s)$. В таком ограниченном смысле MC-цель не использует смещённую текущую оценку продолжения.

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

Сильные стороны MC:

• не нужна модель переходов;
• нет бутстрэппинга;
• ошибка текущего $V$ не входит в целевое значение.

Ограничения:

• нужно дождаться достаточного продолжения или конца эпизода;
• одна терминальная награда может давать большую дисперсию;
• длинные эпизоды дороги;
• при редких посещениях данные накапливаются медленно.

Полный ответ LLM с одной итоговой оценкой даёт на уровне последовательности сигнал, похожий на MC-оценку: результат наблюдается после генерации, но вклад отдельных токенов остаётся скрытым.

---

Шаг 2.3.3 — Один наблюдённый шаг и оценка продолжения

Обучение по временным различиям (temporal-difference learning, TD) обновляет оценку до завершения эпизода. Одношаговый вариант TD(0) использует

$$Y_t^{\mathrm{TD}(0)} = R_{t+1}+\gamma V(S_{t+1})$$

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

$$\delta_t = R_{t+1}+\gamma V(S_{t+1})-V(S_t).$$

Обновление:

$$V(S_t)\leftarrow V(S_t)+\alpha\delta_t.$$

Для настоящего терминала продолжение обнуляется:

$$\delta_t=R_{t+1}-V(S_t).$$

Для технического усечения, при котором процесс мог бы продолжаться, $V(S_{t+1})$ обычно сохраняется в цели.

TD(0) использует меньше случайных будущих наград, но опирается на текущую оценку. Поэтому в конечной выборке у цели появляется зависимость от ошибки $V$. Часто это снижает дисперсию ценой смещения, однако универсального порядка «TD всегда лучше MC» или «MC всегда точнее TD» нет. Результат зависит от среды, представления, размера шага и бюджета данных.

Полезная интуиция: MC ждёт счёт за весь маршрут; TD пересчитывает текущую оценку после каждого нового участка пути.

---

Шаг 2.3.4 — Многошаговая цель соединяет MC и TD

Если в следующих $n$ переходах задача не завершилась, $n$-шаговая цель имеет вид

$$G_{t:t+n} = \sum_{k=0}^{n-1}\gamma^kR_{t+k+1} + \gamma^nV(S_{t+n}).$$

При $n=1$ получаем TD(0). Если окно дошло до истинного терминала раньше $t+n$, сумма обрывается на последней наблюдённой награде, а бутстрэппинг отсутствует. В частности, когда $n$ покрывает весь остаток эпизода, цель превращается в MC-цель.

С ростом $n$:

• в цель входит больше реально наблюдённых наград;
• уменьшается зависимость от текущего $V$;
• обновление приходится ждать дольше;
• обычно возрастает влияние случайности более длинного хвоста.

Это не монотонная гарантия качества. Ошибка текущего $V$, корреляция переходов, размер шага и длина эпизода могут менять оптимальный горизонт.

Позже обобщённая оценка преимущества (generalized advantage estimation, GAE) объединит TD-ошибки разных горизонтов экспоненциальными весами. Здесь важно увидеть основу: многошаговая цель — не новая функция ценности, а способ выбрать место, где наблюдённая часть траектории уступает место текущей оценке продолжения.

Функция n_step_target() в эталонном модуле принимает список наблюдённых наград, значение продолжения, $\gamma$ и явный признак терминального конца окна. Это не даёт случайно принять внешнее усечение за настоящий терминал.

---

Шаг 2.3.5 — Коридор: сравниваем оценки, а не лозунги

Возьмём симметричный коридор с терминалами 0 и 4, стартом из середины и равновероятными действиями влево и вправо. Награда $1$ выдаётся только при входе в правый терминал. При $\gamma=1$ точные значения равны вероятностям добраться вправо раньше, чем влево:

$$V^\pi=[0,\ 0.25,\ 0.50,\ 0.75,\ 0].$$

График построен по единому протоколу:

• бюджеты от 20 до 2500 эпизодов;
• 40 независимых начальных значений генератора;
• MC первого посещения;
• TD(0) и трёхшаговый TD с постоянным $\alpha=0.1$;
• ошибка — корень из средней квадратичной ошибки (root mean squared error, RMSE) по трём нетерминальным состояниям;
• линия показывает медиану, полоса — межквартильный диапазон.

Эксперимент намеренно не поддерживает лозунг «один метод всегда лучше». При малом бюджете важны шум и начальные условия. При большом бюджете выборочное среднее MC продолжает приближаться к точному значению. TD с постоянным размером шага сохраняет остаточные колебания; трёхшаговая цель в этом протоколе занимает не постоянное «среднее место», а собственную кривую, зависящую от того, как наблюдённые награды сочетаются с текущей оценкой.

Воспроизводимые контрольные значения:

exact: [0.00, 0.25, 0.50, 0.75, 0.00]
MC, 1000 episodes, seed=7:
       [0.00, 0.255539, 0.496000, 0.733728, 0.00]
TD(0), 1000 episodes, seed=42, alpha=0.1:
       [0.00, 0.233105, 0.582660, 0.829850, 0.00]
3-step TD, 1000 episodes, seed=42, alpha=0.1:
       [0.00, 0.248712, 0.523243, 0.769480, 0.00]

Разные начальные значения генератора в контрольных строках нужны для воспроизводимости конкретных функций, а не для объявления победителя. Если уменьшать $\alpha$, менять горизонт, использовать аппроксимацию, повторное использование данных или нестационарную среду, картина изменится.

Мост к LLM. Итоговая награда полного ответа похожа на MC-наблюдение. Критик, модель оценки промежуточного шага или иной предсказатель продолжения вводит бутстрэппинг. Групповая нормировка сравнивает полные ответы, но сама по себе не становится точной токеновой функцией ценности.

---

Урок 2.4. Управление: текущая и целевая политики

Урок 2.4. Управление: текущая и целевая политики

1. От оценки фиксированной политики к улучшению поведения
2. Две цели обновления различаются одной строкой, но не смыслом
3. CliffWalking: один протокол, разные маршруты
4. Почему максимум завышает шумные оценки
5. Что переносится в RL для LLM, а что остаётся табличной учебной моделью

далее — 6 проверочных шагов

Шаг 2.4.1 — От оценки фиксированной политики к улучшению поведения

В задаче управления политика меняется во время обучения. Полезно различать:

• политику поведения (behavior policy) — ту, которая фактически выбирает действия и собирает данные;
• целевую политику (target policy) — ту, чью функцию ценности мы оцениваем или улучшаем.

Если они совпадают, метод обучается по данным текущей политики (on-policy). Если целевая политика отличается от политики поведения, метод обучается по данным другой политики (off-policy). Эти определения относятся не к наличию буфера опыта и не к самому факту случайного исследования, а к тому, о какой политике делается вывод из каких данных.

Для исследования можно использовать $\varepsilon$-жадную политику:

• с вероятностью $1-\varepsilon$ выбрать действие с максимальным $Q(s,a)$;
• с вероятностью $\varepsilon$ выбрать случайное действие.

Это простейший способ не замкнуться сразу на первом найденном маршруте. Систематическое исследование будет темой Модуля 3; здесь $\varepsilon$ нужен, чтобы увидеть различие двух целей обновления.

---

Шаг 2.4.2 — Две цели обновления различаются одной строкой, но не смыслом

Оба метода обновляют табличное $Q(S_t,A_t)$:

$$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha\bigl(Y_t-Q(S_t,A_t)\bigr).$$

Метод «состояние–действие–награда–состояние–действие» (state–action–reward–state–action, SARSA) использует следующее действие, действительно выбранное политикой поведения:

$$Y_t^{\mathrm{SARSA}} = R_{t+1}+\gamma Q(S_{t+1},A_{t+1}).$$

Если поведение $\varepsilon$-жадное, SARSA оценивает последствия вместе с будущим исследованием. Это метод по данным текущей политики.

Q-learning использует жадную цель независимо от того, какое следующее действие будет фактически выполнено:

$$Y_t^{Q} = R_{t+1}+\gamma\max_{a'}Q(S_{t+1},a').$$

Данные может собирать $\varepsilon$-жадная политика, но цель относится к жадной политике. Поэтому Q-learning является методом по данным другой политики.

Для терминального перехода обе цели равны только $R_{t+1}$. Для технически усечённой траектории продолжение обычно не обнуляется.

В конечном дисконтированном табличном MDP с ограниченными наградами Q-learning сходится к $Q^*$ при классических условиях: каждая пара состояние–действие посещается бесконечно часто, а последовательности размеров шага для каждой пары удовлетворяют $\sum_t\alpha_t(s,a)=\infty$ и $\sum_t\alpha_t^2(s,a)<\infty$. Это асимптотическое утверждение о табличной стохастической аппроксимации. Постоянный размер шага, конечный набор данных, нейросетевая функция $Q$, меняющаяся цель и совместно обучаемые компоненты не наследуют гарантию автоматически.

---

Шаг 2.4.3 — CliffWalking: один протокол, разные маршруты

В CliffWalking агент идёт из левого нижнего угла в правый. Обычный шаг даёт $-1$. Попадание в обрыв даёт $-100$ и возвращает агента к старту. Во время обучения политика остаётся $\varepsilon$-жадной.

Фиксированный протокол статической иллюстрации:

• начальное значение генератора 0;
• 500 эпизодов;
• $\alpha=0.5$;
• $\gamma=1$;
• $\varepsilon=0.1$;
• жадная проверка после обучения.

Результаты этого воспроизводимого запуска:

Q-learning оценивает маршрут так, будто будущие действия будут жадными, поэтому находит короткий путь рядом с обрывом. Но фактическое $\varepsilon$-жадное поведение иногда отклоняется и дорого падает. SARSA учитывает будущие исследовательские действия и в этом запуске выбирает более длинный маршрут с большим запасом.

Это не универсальный рейтинг. Изменятся $\varepsilon$, штраф, число эпизодов, инициализация или правило оценки — изменятся и результаты. Эксперимент показывает причинную связь между целью обновления и тем риском, который представляет обучаемая функция $Q$.

---

Шаг 2.4.4 — Почему максимум завышает шумные оценки

Пусть истинные ценности нескольких действий одинаковы, но оценки содержат шум:

$$\widehat Q(a)=Q(a)+\varepsilon_a, \qquad \mathbb{E}[\varepsilon_a]=0.$$

Каждая оценка по отдельности может быть несмещённой, однако максимум выбирает действие, которому случайно досталась положительная ошибка:

$$\mathbb{E}\left[\max_a \widehat Q(a)\right] \ge \max_a Q(a).$$

Это смещение максимизации (maximization bias). Q-learning использует одну и ту же таблицу и для выбора действия, и для его оценки в цели, поэтому ошибка выбора может войти в обновление как завышенное продолжение.

Double Q-learning разделяет две роли. При обновлении первой таблицы действие выбирается по $Q^A$, а оценивается по $Q^B$:

$$a^*=\arg\max_a Q^A(s',a),$$ $$Y_t^{\mathrm{Double}} = R_{t+1}+\gamma Q^B(s',a^*).$$

Затем роли таблиц могут меняться. Если ошибки оценок достаточно независимы, случайное завышение, определившее выбор в $Q^A$, не обязано повториться в $Q^B$. Метод уменьшает типичное переоценивание, но не гарантирует отсутствие любой ошибки и в некоторых режимах может недооценивать максимум.

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

---

Шаг 2.4.5 — Что переносится в RL для LLM, а что остаётся табличной учебной моделью

Соберём главные идеи модуля.

1. Состояние — не просто запись входа. Оно должно быть достаточным для будущей динамики. Полный префикс подходит для чистой авторегрессии, но внешняя среда может сделать задачу частично наблюдаемой.
2. $V$, $Q$ и $A$ отвечают на разные вопросы. $V$ усредняет по политике, $Q$ фиксирует первое действие, $A$ сравнивает действие со средним текущей политики.
3. Уравнение Беллмана — одношаговая согласованность, а не готовый алгоритм обучения. Оно связывает оценку сейчас с наградой и оценкой продолжения.
4. MC и TD выбирают разные места для бутстрэппинга. MC использует наблюдённый хвост; TD заменяет часть хвоста текущей оценкой; $n$-шаговые цели соединяют крайние случаи.
5. Политика поведения и целевая политика могут различаться. Именно это различие, а не наличие буфера, делает Q-learning off-policy.
6. Максимизация шумных оценок создаёт систематическую проблему отбора. Double Q-learning разделяет выбор и оценивание, уменьшая один конкретный источник переоценивания.
7. Причина окончания траектории входит в математику. Истинный терминал обнуляет продолжение, внешнее усечение — нет.

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

Краткий справочник:

Источники и маршрут чтения

Ссылки проверены 4 августа 2026 года. Ни один источник ниже не заменяет ограничения, явно указанные в тексте.

1. Sutton & Barto, Reinforcement Learning: An Introduction, 2-е изд. — https://incompleteideas.net/book/the-book-2nd.html. Основной источник для конечных MDP, функций ценности, уравнений Беллмана, MC, TD, SARSA, Q-learning и GPI. Табличная теория из книги не доказывает сходимость нейросетевого RL для LLM.
2. Farama Foundation, “Handling Time Limits”. — https://gymnasium.farama.org/tutorials/gymnasium_basics/handling_time_limits/. Поддерживает инженерное различие terminated/truncated и правило бутстрэппинга. Это руководство по интерфейсу и постановке среды, а не отдельная общая теорема о всех конечных горизонтах.
3. Watkins & Dayan, “Q-learning” (1992). — https://doi.org/10.1007/BF00992698. Первичный источник классического табличного алгоритма и его сходимости при специальных условиях посещаемости и размеров шага. Эти условия нельзя молча переносить на нелинейную аппроксимацию.
4. van Hasselt, “Double Q-learning” (2010). — https://proceedings.neurips.cc/paper/3964-double-q-learning.pdf. Первичный источник анализа смещения максимизации и разделения выбора с оцениванием. Double Q-learning уменьшает характерное завышение, но не является универсально несмещённым оценивателем.
5. Schulman et al., “High-Dimensional Continuous Control Using Generalized Advantage Estimation”. — https://arxiv.org/abs/1506.02438. Нужен для перехода от многошаговых TD-ошибок к GAE; использование GAE в policy gradient будет разобрано в Модуле 4.
6. Shao et al., DeepSeekMath. — https://arxiv.org/abs/2402.03300. Это авторское описание исходной GRPO-конструкции с группой ответов и без обучаемого критика. Оно подтверждает устройство предложенного метода, но не является независимой проверкой всех его эмпирических выводов и не описывает все более поздние варианты.
7. Официальные описания FrozenLake и CliffWalking в Gymnasium. — https://gymnasium.farama.org/environments/toy_text/frozen_lake/ и https://gymnasium.farama.org/environments/toy_text/cliff_walking/. Они фиксируют канонические учебные среды; численные значения курса вычислены собственной проверяемой NumPy-реализацией с явно указанным протоколом.

Расширенный реестр утверждений, статусов проверки и границ вывода находится в Module_2_Sources.md.

Дальше — Модуль 3: бандиты и исследование. Мы временно уберём многошаговую динамику и отдельно разберём цену исследования, методы верхней доверительной границы, сэмплирование Томпсона и связь отбора из нескольких ответов с контекстными бандитами.