# Stanford CS234 Reinforcement Learning I Policy Evaluation I 2024 I Lecture 3

Источник: https://www.youtube.com/watch?v=jjq51TRNVvk
Канал: Stanford Online
Опубликовано: 30.10.2024

---

Очередная лекция престижного образовательного курса Стэнфордского университета Stanford CS234 посвящена фундаментальной задаче обучения с подкреплением — оценке стратегий без использования готовой модели среды. В рамках занятия подробно разбираются два ключевых подхода: классический метод Монте-Карло и алгоритм обучения временным различиям TD(0). Профессор наглядно демонстрирует, как различные математические допущения заставляют эти алгоритмы приходить к совершенно разным результатам при работе с ограниченными объемами данных.

## 📊 Введение в табличные MDP и парадокс сходимости
[[JUMP:0:05]]

Лектор начинает занятие с интерактивного опроса, призванного освежить в памяти студентов концепцию марковских процессов принятия решений (MDP). В центре обсуждения оказывается табличный случай (tabular MDP), где функция ценности каждого состояния может быть представлена в виде явной таблицы. Это принципиально отличает данный подход от использования глубоких нейронных сетей, где один параметр отвечает сразу за множество состояний.

Важным теоретическим ограничением является общее число возможных детерминированных стратегий, которое выражается формулой $A^S$, где $A$ — количество доступных действий, а $S$ — число состояний. Как подчеркивает лектор, в табличном дискретном случае алгоритмы итерации ценности (Value Iteration) и итерации стратегий (Policy Iteration) асимптотически гарантируют сходимость к истинной функции ценности. Однако динамика их сходимости в краткосрочной перспективе принципиально различается.

Для иллюстрации этого парадокса приводится пример экстремально простого MDP с одним состоянием и одним действием. В таком сценарии:

*   Алгоритм итерации стратегий (Policy Iteration) находит оптимальное решение ровно за один раунд.
*   Алгоритм итерации ценности (Value Iteration) вынужден совершать множество шагов до тех пор, пока изменения не станут пренебрежимо малыми.

Если задать вознаграждение равным 1, коэффициент дисконтирования $\gamma = 0.9$, а начальную ценность равной 0, то истинная ценность состояния $V^*$ рассчитывается через сумму геометрической прогрессии:

$$V^*(s) = \frac{1}{1 - \gamma} = 10$$

После первой итерации алгоритм выдаст значение $V_1(s) = 1$, что далеко от целевого показателя 10. Это наглядно доказывает, что даже при гарантированной долгосрочной сходимости вычислительная траектория алгоритмов может быть совершенно разной.

## 🌍 Оценка стратегий без модели (Model-Free Policy Evaluation)
[[JUMP:8:28]]

В реальном мире агенты редко обладают полной информацией об окружающей среде. Лектор объявляет переход к изучению методов «без модели» (model-free), когда агенту не даны уравнения динамики переходов и модель вознаграждений. Единственный способ понять качество принимаемых решений — это прямое взаимодействие со средой.

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

*   Возврат ($G$) — дисконтированная сумма вознаграждений, полученных за конкретный эпизод.
*   Функция ценности состояния ($V^\pi(s)$) — ожидаемый возврат, который агент получит в среднем, стартуя из состояния $s$ и следуя стратегии $\pi$.
*   Функция ценности действия ($Q^\pi(s, a)$) — ожидаемый возврат, если агент начнет в состоянии $s$, выполнит действие $a$, а затем продолжит следовать стратегии $\pi$.

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

## 🎲 Метод Монте-Карло: простота усреднения траекторий
[[JUMP:14:20]]

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

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

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

*   Применимость только в эпизодических задачах (episodic MDPs), где каждый сеанс взаимодействия гарантированно завершается. Невозможно рассчитать полный возврат $G$, если процесс длится бесконечно.
*   Проблема редких состояний. Если какое-то критическое состояние (например, редкий побочный эффект от вакцины) встречается крайне редко, потребуется колоссальное количество траекторий для получения адекватной оценки.

Существует три основных модификации этого подхода:

1.  First-visit Monte Carlo — ценность состояния обновляется только при его первом посещении внутри конкретного эпизода. Этот метод дает несмещенную оценку.
2.  Every-visit Monte Carlo — обновление происходит при каждом посещении состояния в рамках одной траектории. Данные в одной траектории коррелируют, поэтому оценка становится смещенной, но на практике она часто минимизирует среднеквадратичную ошибку за счет более полного использования данных.
3.  Инкрементальный метод Монте-Карло — текущая оценка плавно корректируется с использованием скорости обучения (learning rate) $\alpha$.

Графически метод Монте-Карло можно представить как исследование гигантского дерева вероятностей (expectimax tree). Вместо точного обхода всего дерева, требующего огромных мощностей, алгоритм просто сэмплирует случайные пути до самого конца. На этой концепции построены алгоритмы поиска по дереву Монте-Карло (MCTS), которые легли в основу знаменитой системы AlphaGo.

## ⏱️ Обучение временным различиям: метод TD(0)
[[JUMP:37:01]]

В качестве альтернативы лектор вводит понятие обучения временным различиям (Temporal Difference, TD), ссылаясь на классический учебник Ричарда Саттона и Эндрю Барто. Авторы книги называют эту идею центральной и самой инновационной в теории обучения с подкреплением. Метод TD(0) объединяет в себе лучшие черты сэмплирования траекторий и бутстрэпирования.

Главное отличие TD(0) от Монте-Карло заключается в том, что агенту не нужно ждать окончания эпизода. Корректировка ценности состояния происходит мгновенно, как только получен кортеж данных $(s, a, r, s')$. Это позволяет применять алгоритм в задачах с бесконечным горизонтом планирования.

Формула обновления выглядит как сдвиг старой оценки в сторону целевого значения TD (TD target) с определенным коэффициентом $\alpha$:

$$\text{TD-Target} = r + \gamma V(s')$$

Разница между текущей оценкой и целевым значением называется ошибкой временного различия (TD0 error).

Чтобы продемонстрировать разницу в поведении алгоритмов на старте, лектор приводит детальный разбор траектории движения робота (наподобие марсохода Mars Rover). При инициализации всех векторов ценностей нулями и получении награды, равной 1, только в самом конце пути перед терминальным состоянием:

*   Алгоритм TD(0) после одного эпизода обновит значение ценности только для одного-единственного состояния, предшествующего финишу. Все остальные состояния в его таблице останутся нулевыми.
*   Метод Монте-Карло (First-visit) запишет единицы во все состояния, которые робот успел посетить за этот эпизод, так как он дождался финального выигрыша и распределил его по всей траектории назад.

Это наглядно иллюстрирует, что на малых объемах данных алгоритмы демонстрируют кардинально разную эффективность сэмплирования.

## 🧠 Принцип эквивалентности определенности (Certainty Equivalence)
[[JUMP:1:01:44]]

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

В табличном случае это реализуется методом максимального правдоподобия (MLE) через банальный подсчет частот. Агент считает, сколько раз он находился в состоянии $s$, совершал действие $a$ и оказывался в $s'$, а затем делит это на общее число посещений пары $(s, a)$. Аналогично восстанавливается и модель вознаграждений. На полученной «псевдомодели» запускается классическое динамическое программирование.

По оценке лектора, ключевые свойства данного подхода включают:

*   Экстремальная эффективность использования данных (data efficiency). Любая крупица информации мгновенно интегрируется в модель и распространяется по всему графу состояний.
*   Высокая вычислительная сложность. Пересчет модели и запуск динамического программирования требуют огромных ресурсов — порядка $O(S^2 A)$ для итерационных методов.

## 📦 Пакетная оценка (Batch Evaluation) и фундаментальное различие MC и TD
[[JUMP:1:05:26]]

В финальной части лекции рассматривается концепция пакетной оценки (batch policy evaluation), крайне актуальная для сфер с «дорогой» или опасной генерацией данных (медицина, юриспруденция). Агенту предоставляется фиксированный набор из $k$ эпизодов, на котором многократно запускаются обновления Монте-Карло или TD(0) до полной сходимости.

Для демонстрации глубокого математического различия между подходами лектор разбирает классический пример Саттона и Барто. Дана простая среда из двух состояний (A и B), отсутствует дисконтирование ($\gamma = 1$), а пакет данных состоит из 8 эпизодов:

*   1 эпизод: из состояния А агент переходит в B с наградой 0, затем эпизод завершается с наградой 0.
*   6 эпизодов: агент стартует в B и сразу завершает эпизод с наградой 1.
*   1 эпизод: агент стартует в B и завершает эпизод с наградой 0.

При многократном повторении этого пакета оба алгоритма солидарны в оценке состояния B: шесть успехов из восьми посещений дают среднее значение $V(B) = 0.75$. Однако оценка состояния А взрывает интуицию:

*   Метод Монте-Карло сойдется к значению $V(A) = 0$. Объясняется это тем, что в единственном эпизоде с участием А суммарный возврат всей траектории составил строго 0. Метод Монте-Карло беспристрастно минимизирует среднеквадратичную ошибку относительно наблюдаемых возвратов.
*   Метод TD(0) сойдется к значению $V(A) = 0.75$. Алгоритм TD жестко опирается на марковское допущение и связывает ценность А с ценностью В через уравнение Беллмана: $V(A) = R + \gamma V(B) = 0 + 1 \times 0.75 = 0.75$,.

Этот пример обнажает глубинную суть: метод TD(0) неявно решает задачу через призму модели максимального правдоподобия марковского процесса (принцип эквивалентности определенности). Он «верит» в структуру графа, тогда как Монте-Карло «верит» только чистым фактам зафиксированных исходов траекторий. Выбор между ними в реальных проектах полностью зависит от того, насколько строго в конкретной задаче выполняется свойство марковости.