В лекции Стэнфордского университета по курсу CS234 профессор Эмма Бранскилл представляет финальный обзор методов эффективного исследования (exploration) в обучении с подкреплением, совершая переход от простых многоруких бандитов к сложным марковским процессам принятия решений (MDP). В материале рассматриваются как классические табличные алгоритмы с теоретическими гарантиями, так и современные подходы на стыке глубокого обучения и мета-исследования, включая применение трансформеров. Особое внимание уделяется практическому кейсу автоматизации проверки студенческих работ, демонстрирующему реальную ценность оптимизированного поиска стратегий.
🎮 Практическая магия RL: как научить агента проверять студенческие работы 4:00
Эмма Бранскилл делится вдохновляющим примером применения алгоритмов исследования из недавней совместной работы с профессором Челси Финн и группой аспирантов Стэнфорда. В рамках учебного курса студенты пишут код для воссоздания классической игры Breakout, самостоятельно создавая игровую среду. Однако полноценное обучение программированию невозможно без обратной связи, которая требует проверки корректности симуляции: правильно ли отрисовывается ракетка, адекватно ли рассчитывается траектория отскока мяча и соблюдаются ли заданные правила перехода состояний.
Традиционный процесс оценки выглядит чрезвычайно трудоемким. Проверяющий должен запустить игру и вручную тестировать различные сценарии, выстраивая в голове собственную стратегию поведения для поиска багов. На проверку одной работы уходит около 8 минут. При наличии 300 студентов на курсе (а на платформе вроде code.org их число в разы больше) ручная проверка оборачивается колоссальными затратами человеческих ресурсов. Из-за этого некоторые образовательные платформы вообще отказываются от оценивания, что серьезно вредит обучению студентов.
Для решения этой проблемы Эмма Бранскилл, профессор Крис Пич и их студент Эван разработали систему на основе обучения с подкреплением. Вместо человека в среду запускается RL-агент, задача которого — максимально быстро и эффективно исследовать игровое пространство, чтобы выявить скрытые программные ошибки. Эван развил эту идею в серии публикаций на конференции NeurIPS, применив мета-обучение с подкреплением (meta reinforcement learning) и алгоритм DREAM для ускоренного стратегического поиска. Свежие исследования команды доказали, что гибридный подход, объединяющий автоматизированного агента и человека-проверяющего, значительно сокращает время оценки и одновременно повышает ее точность.
🧠 От бандитов к марковским процессам: алгоритм MBIE-EB 10:05
Завершив рассмотрение многоруких бандитов, где принимаемые решения не влияют на последующие состояния, лектор переходит к марковским процессам принятия решений (MDP). Базовые концепции, такие как оптимизм в условиях неопределенности (optimism under uncertainty) и сэмплирование по апостериорному распределению (Thompson sampling), успешно переносятся на табличные MDP, а затем, при соблюдении осторожности, и на аппроксимацию функций.
Одним из классических и наиболее наглядных алгоритмов оптимистичного исследования в табличных MDP является MBIE-EB (Model-Based Interval Estimation with Exploration Bonus). Этот метод опирается на построение модели. В процессе работы алгоритм собирает статистику:
- Количество посещений: фиксируется число выборов определенного действия в конкретном состоянии.
- Матрица переходов: подсчитывается, сколько раз из текущего состояния при данном действии агент попадал в каждое из следующих состояний.
На основе этих данных вычисляется эмпирическое среднее для функции вознаграждения и строится оценка модели динамики среды. Вместо стандартного планирования на эквивалентных моделях, MBIE-EB модифицирует уравнение Белмана, добавляя к нему специальный бонус за исследование (exploration bonus).
Математически это выглядит как вычисление оператора Белмана с добавлением штрафа за редкое посещение. Если пара «состояние-действие» встречалась мало, этот бонус становится огромным. Величина бонуса рассчитывается по формуле, включающей коэффициент $\beta$, фактор дисконтирования $\gamma$ и корень из количества посещений в знаменателе. Подобный оптимизм заставляет агента целенаправленно посещать те области пространства, о вознаграждении и динамике которых у него меньше всего информации, распространяя этот стимул назад во времени через многократные итерации Белмана.
📊 Теоретические гарантии PAC и суровая реальность 17:28
Алгоритм MBIE-EB относится к категории PAC-алгоритмов (Probably Approximately Correct — вероятно, приблизительно корректный). Это означает, что с высокой долей вероятности ценность выбираемого агентом действия будет отличаться от оптимального не более чем на величину $\epsilon$. Число шагов, на которых алгоритм способен совершить ошибку, строго ограничено полиномом от размера пространства состояний, пространства действий, $1/\epsilon$ и $1/(1-\gamma)$.
Эмма Бранскилл призывает своих студентов всегда подставлять реальные числа в теоретические оценки, чтобы сопоставлять абстрактные формулы с практикой. Проведя простой расчет для скромного MDP с 10 состояниями, 10 действиями, при условии $\epsilon = 0.1$ и $\gamma = 0.9$, можно получить верхнюю границу в районе $10^{12}$ временных шагов.
По мнению Бранскилл, такие теоретические оценки оказываются чрезвычайно консервативными. Очевидно, что для простой среды типа GridWorld из 10 состояний агент обучается адекватному поведению существенно быстрее. Тем не менее, ценность PAC-анализа заключается в самом факте существования строгой верхней границы, гарантирующей, что алгоритм не будет совершать ошибки бесконечно, в отличие от простых случайных стратегий.
📐 Лемма о симуляции: мост между моделью и ценностью 20:39
Ключевым математическим фундаментом для доказательства сходимости PAC-алгоритмов выступает так называемая лемма о симуляции (Simulation Lemma). Ее главная суть состоит в том, что она связывает точность прогностических моделей (динамики и вознаграждения) с точностью результирующей функции ценности Q.
В рамках лекции приводится эскиз доказательства для табличного случая с фиксированной политикой $\pi$ и бесконечной нормой. Предположим, существуют два разных марковских процесса (например, эмпирический и истинный), чьи функции вознаграждения различаются максимум на величину $\alpha$, а модели динамики переходов — максимум на $\beta$.
Используя неравенство треугольника и искусственный прием с добавлением и вычитанием промежуточного члена, Бранскилл демонстрирует, как расхождение между соответствующими Q-функциями ограничивается рекурсивным выражением. В итоге выводится финальная оценка для максимальной ошибки $\Delta$:
$$\Delta \le \frac{1}{1-\gamma} \alpha + \frac{\gamma}{(1-\gamma)^2} R_{max} \beta$$
По словам лектора, данная лемма критически важна для понимания процессов исследования: она математически гарантирует, что по мере накопления данных и улучшения прогностических моделей оценка Q-функции неизбежно становится точнее. Агент защищен от ситуации, когда он бесконечно учится в одних и тех же состояниях, но не приближается к реальному пониманию ценности своих действий.
🎲 Байесовские MDP и алгоритм PSRL: борьба с метаниями агента 34:11
В качестве альтернативы частотным методам выступает байесовский подход, позволяющий использовать априорные знания о среде. Примером успешного переноса идеи сэмплирования Томсона на последовательные задачи является алгоритм PSRL (Posterior Sampling Reinforcement Learning), разработанный Яном Осбандом, Дэном Руссо и Бенджамином Ван Роем в стенах Стэнфорда.
В отличие от бандитов, где сэмплирование параметров сразу определяет оптимальное действие, в MDP ситуация сложнее: после сэмплирования параметров среды агенту необходимо полностью решить задачу планирования (например, методом итерации ценности), чтобы получить функцию $Q^*$. Архитектура PSRL строится по эпохам (эпизодам):
- В начале каждого эпизода агент сэмплирует из текущего апостериорного распределения единую модель динамики и вознаграждения для всех пар состояний и действий.
- На основе сэмплированной модели рассчитывается оптимальная стратегия $Q^*$.
- Агент строго следует этой стратегии на протяжении всего эпизода длиной $H$ шагов, собирая новые данные.
- В конце эпизода апостериорное распределение обновляется.
Для моделирования динамики переходов в байесовском подходе применяется распределение Дирихле, которое является сопряженным априорным распределением для мультиномиального распределения. Это позволяет обновлять параметры распределения простым инкрементом счетчиков переходов, аналогично работе с бета-распределением.
Бранскилл подчеркивает критическую важность фиксации (commit) выбранной модели на протяжении всей эпохи. Если бы агент пересэмплировал модель и обновлял свои убеждения на каждом промежуточном шаге, это привело бы к деструктивному поведению, называемому «метанием» (thrashing). В качестве примера приводится задача прохождения цепочки состояний (chain MDP), где высокие награды расположены на противоположных концах. Постоянно меняя гипотезы о среде под влиянием локальных нулевых наград, агент без фиксации стратегии непрерывно разворачивался бы обратно, топчась на месте и увязая в бесконечном цикле неэффективного поиска.
🐁 Параллельные агенты и координация: метод Seed Sampling 45:42
Развитием байесовских подходов для распределенных систем стали работы Марии Димакопулу, посвященные параллельному обучению с подкреплением (concurrent reinforcement learning). В условиях, когда одну и ту же среду одновременно исследуют несколько независимых агентов (например, стая мышей в лабиринте, ищущая сыр), отсутствие координации делает их действия хаотичными или избыточными.
Для решения этой проблемы Димакопулу предложила метод сэмплирования семян (seed sampling). Его суть сводится к стратегическому распределению исследовательских задач между агентами:
- Диверсификация гипотез: каждому параллельному агенту принудительно задаются разные «семена» для сэмплирования MDP, что заставляет их верить в перспективность различных областей пространства.
- Совместное исследование: один агент отправляется проверять наличие награды в левой части лабиринта, другой — в правой.
- Объединение опыта: в конце эпохи их индивидуальный опыт сливается в единое глобальное апостериорное распределение.
Лектор указывает на любопытный разрыв между теорией и экспериментом в этой области. С теоретической точки зрения, согласно статье 2015 года, жесткая координация не является обязательной для получения практически линейного ускорения от масштабирования числа агентов. Однако на практике скоординированное сэмплирование семян демонстрирует колоссальное преимущество, защищая систему от дублирования усилий и позволяя находить скрытые награды кратно быстрее.
🎯 Масштабирование: от контекстных бандитов к глубокому RL 54:11
Переход от табличных абстракций к огромным пространствам состояний реального мира сталкивается с фундаментальными трудностями. Для оптимистичного подхода становится крайне тяжело математически выразить меру неопределенности внутри глубоких нейросетей, а для байесовских методов — рассчитывать многомерные апостериорные распределения.
Промежуточным шагом между бандитами и полноценными MDP выступают контекстные бандиты, где агент видит состояние (контекст), но его действия не меняют последующие контексты среды. Классические алгоритмы вроде UCB без обмена информацией сталкиваются со стремительным ростом накопленного регрета (упущенной выгоды) при увеличении числа альтернатив. Алгоритм Linear UCB решает эту проблему за счет представления действий через фиксированные векторы признаков, что позволяет переносить знания между похожими объектами — например, рекламными кампаниями со схожей тематикой. Ограничение неопределенности в данном случае сводится к оценке доверительных эллипсоидов для вектора параметров $\theta$, что вычислительно эффективно и активно применяется в коммерческих рекомендательных системах новостей.
В глубоком обучении с подкреплением для полноценных MDP базовые счетчики посещений теряют смысл: в сложных играх вроде Atari игрок физически не может увидеть один и тот же экран дважды. Чтобы преодолеть это ограничение, Марк Бельмар и его коллеги ввели концепцию псевдо-счетчиков (pseudo-counts), оценивающих плотность распределения состояний через генеративные модели. В культовой по своей сложности игре Montezuma's Revenge стандартный алгоритм DQN за 50 миллионов кадров не мог выбраться даже из первой комнаты из-за неэффективности обычного случайного исследования ($\epsilon$-greedy). Внедрение обобщенных псевдо-счетчиков, по словам Бранскилл, привело к качественному прорыву, позволив агентам успешно осваивать сложнейшие игровые локации.
В качестве современных альтернатив для работы с неопределенностью в глубоких сетях Бранскилл упоминает:
- Ансамблирование и бутстреп: аппроксимация неопределенности через обучение нескольких независимых сетей (глубокий аналог PSRL от Яна Осбанда).
- Байесовская линейная регрессия: применение статистических оценок исключительно к последнему слою нейросети, что работает на удивление стабильно.
🤖 Будущее за трансформерами: предобучение стратегиям исследования 1:05:49
В финальной части лекции Эмма Бранскилл знакомит слушателей с передним краем науки — мета-исследованием с использованием предварительно обученных трансформеров (Decision Pre-trained Transformers). Этот подход меняет парадигму: вместо ручного конструирования бонусов или эвристик неопределенности, нейросеть обучается эффективному поиску на множестве различных задач.
Процесс обучения строится на отображении задачи RL на парадигму обучения с учителем (supervised learning), напоминая поведенческий клонинг. Однако ключевое отличие заключается в том, что вместо простого копирования прошлых траекторий, трансформер обучается предсказывать математически оптимальное поисковое действие для мета-структуры. В результате модель фактически индуктивно воссоздает поведение, эквивалентное Thompson sampling, автоматически наследуя все его строгие теоретические гарантии сходимости.
Самым удивительным свойством таких трансформеров, по мнению Бранскилл, является их способность самостоятельно обнаруживать и кодировать скрытую латентную структуру среды без подсказок со стороны инженеров. В ходе экспериментов, если семейство тестовых задач имело общую линейную зависимость, предобученный трансформер при столкновении с абсолютно новой задачей мгновенно выстраивал траекторию поиска так, словно ему изначально передали точную математическую модель этой скрытой структуры. Это избавляет алгоритмы от хрупкости, свойственной классическим методам с жестко заданными признаками, и открывает прямой путь к созданию по-настоящему адаптивного искусственного интеллекта.
