# Стэнфордский профессор объяснил, как сэмплирование Томпсона спасает рекомендательные системы от задержек данных

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

---

В лекции Стэнфордского университета из цикла по обучению с подкреплением (CS234, 2024 год) рассматриваются передовые стратегии эффективного исследования среды в контексте многоруких бандитов. Профессор подробно разбирает концепцию вероятно приблизительно корректного (PAC) обучения, математику байесовских бандитов и алгоритм сэмплирования Томпсона. На практических примерах, включая реальную систему тестирования на COVID-19 в Греции и рекомендательные системы Yahoo, демонстрируются преимущества и ограничения различных подходов в условиях задержки обратной связи.

## 🧠 Проверка понимания: тонкости алгоритма UCB и влияние параметров
[[JUMP:0:05]]

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

Второй вопрос касается классического алгоритма UCB (Upper Confidence Bound). В условиях конечного множества «рукавов» (действий) эмпирическая оценка эффективности каждого из них базируется на формуле, где среднее наблюдаемое вознаграждение суммируется со специальным бонусным членом. В этой формуле переменная $N_t(a)$ обозначает, сколько раз действие $a$ было выбрано за $t$ шагов во времени, а логарифмическая функция отражает зависимость от параметра доверия $\delta$. Этот параметр используется для построения доверительных интервалов вокруг эмпирического среднего.

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

Особый интерес вызывает анализ скорости сужения доверительных интервалов. Профессор предлагает сравнить стандартную скорость сужения $N_t(a)^{-1/2}$ с гипотетической скоростью $N_t(a)^{-1/4}$. Если действие было выполнено, например, 100 раз, то в первом случае бонусный член уменьшится до $1/10$, а во втором — лишь до $1/3$. Это означает, что при скорости $N_t(a)^{-1/4}$ доверительные интервалы сужаются медленнее, оставаясь более широкими при том же объеме данных. В качестве альтернативного примера упоминаются алгоритмы исследовательской лаборатории DeepMind, где часто применяется скорость $N_t(a)^{-1}$, обеспечивающая гораздо более быстрое схлопывание интервалов.

Выбор скорости сужения границ позволяет регулировать баланс между исследованием (exploration) и эксплуатацией (exploitation). На практике теоретические интервалы, выведенные из неравенства Хёфдинга, часто оказываются излишне консервативными. В реальных прикладных задачах разработчики сознательно увеличивают скорость сужения, чтобы снизить объем нерационального исследования среды. Аналогичный компромисс наблюдается в алгоритме PPO (Proximal Policy Optimization), где строгие теоретические шаги оптимизации заменяются более агрессивным методом отсечения (clipping) ради практической эффективности. С другой стороны, медленное сужение границ необходимо в нестационарных средах — например, когда предпочтения клиентов меняются со временем и системе требуется постоянно собирать свежие данные.

Последний важный аспект экспресс-теста связан с природой оптимизма алгоритма. Если к эмпирическому среднему прибавить фиксированный бонус (например, 20), станет ли алгоритм оптимистичным? Он определенно будет оптимистичным по отношению к самому эмпирическому среднему. Однако это не гарантирует оптимизм по отношению к истинному (математическому) среднему значению вознаграждения. Профессор иллюстрирует это примером с монетой, истинная вероятность выпадения орла для которой равна 0.5. Если подбросить её один раз и получить решку, эмпирическое среднее будет равно 0. Добавление фиксированного бонуса 0.01 даст оценку 0.01, что все еще значительно ниже истинного значения 0.5. Именно поэтому для достижения строгой оптимистичности необходимо использовать честно выведенные доверительные интервалы Хёфдинга.

## 🏥 Практика RL: умное тестирование на COVID-19 в Греции
[[JUMP:14:48]]

Для демонстрации применимости бандитских алгоритмов в реальном мире профессор подробно разбирает научную работу Хамсы Бастани, опубликованную в журнале Nature несколько лет назад. Исследование посвящено распределению дефицитных медицинских ресурсов в условиях пандемии COVID-19, когда Греции необходимо было принимать решения о тестировании и карантине прибывающих в страну путешественников. Тотальное тестирование всех пассажиров было невозможным из-за ограниченности лабораторных мощностей и высоких финансовых затрат государства на оплату карантинных отелей.

Разработанная исследователями система под названием Eva использовала результаты предыдущих тестов для оптимизации стратегии текущего контроля на границе. Пассажиры заранее заполняли специальную форму в аэропорту, и алгоритм Eva на основе их данных определял, кого именно следует отправить на тестирование, а кого можно пропустить без задержек. Результаты ПЦР-анализов поступали в центральную базу данных через 24–48 часов, в течение которых туристы находились на изоляции. Собранная информация возвращалась в систему для динамического обновления алгоритма.

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

* **Размерность пространства действий:** Переменная $k$ в данном случае очень мала и равна двум — система принимает бинарное решение (тестировать пассажира или нет).
* **Контекст (состояния):** Каждый прибывающий описывается вектором признаков (страна отправления, демографические данные), формирующим текущее состояние системы.
* **Нестационарность:** Эпидемиологическая обстановка постоянно менялась. Бастани доказала, что официальная популяционная статистика стран (ограниченная и поступающая с задержкой) была менее информативной для прогнозирования рисков, чем данные бандитского алгоритма, собираемые в режиме реального времени.
* **Батчевый характер и задержка обратной связи:** Решения принимаются не индивидуально-последовательно, а группами. Например, на самолете прилетает 200 человек, и вердикт нужно вынести для всех сразу, не дожидаясь результатов предыдущих тестов, которые станут известны лишь через двое суток.
* **Ограничения:** В системе присутствовали жесткие ресурсные лимиты (например, фиксированное число тестов в день) и политические ограничения (невозможность полностью заблокировать въезд из конкретной страны).

Профессор отмечает, что групповое (батчевое) принятие решений критически важно для многих современных ИТ-сфер. Подобная механика используется при оптимизации моделей по предпочтениям человека (Direct Preference Optimization, DPO), когда разметка данных происходит пакетами. Исследовательская лаборатория лектора совместно со специалистом Шарадом Гоэлом из Гарвардской школы Кеннеди активно изучает такие задачи, поскольку популяционные ограничения и требования справедливости (fairness constraints) существенно усложняют вычисления и не позволяют рассматривать каждого агента изолированно от других.

Примечательно, что система Eva была развернута и запущена в Греции всего за один месяц. Поскольку в условиях смертоносной пандемии проведение классического рандомизированного контролируемого исследования (РКИ) было этически недопустимо, авторы оценивали эффективность алгоритма с помощью офлайн-методов (batch methods), рассчитывая контрфактуальные сценарии упущенной выгоды.

## 📊 Стратегия PAC против минимизации регрета
[[JUMP:23:46]]

Возвращаясь к теории обучения с подкреплением, профессор сопоставляет две концепции оценки эффективности алгоритмов: минимизацию регрета и критерий PAC (Probably Approximately Correct — вероятно приблизительно корректное обучение). В качестве альтернативы сложным доверительным границам часто предлагают использовать простую оптимистичную инициализацию — заполнить таблицу ценностей действий $Q$ заведомо высокими значениями. По закону больших чисел алгоритм со временем сойдется к истинным показателям, однако на практике этот метод имеет серьезные изъяны.

Если установить начальные значения слишком высокими (например, задать ценность 70 при реальном диапазоне наград от 0 до 1), алгоритм будет тратить чрезмерно много времени на неэффективное исследование. Хуже того, если ошибиться с уровнем инициализации в меньшую сторону, система может навсегда заблокироваться на субоптимальном действии, что приведет к линейному росту регрета. В глубоком обучении с подкреплением (Deep Q-Learning), где функция ценности аппроксимируется нейросетью, гарантировать оптимистичную инициализацию параметров для всех достижимых состояний и вовсе практически невозможно.

Концепция PAC-обучения, пришедшая в RL из общей теории машинного обучения, предлагает иной взгляд на качество работы алгоритма. На каждом временном шаге PAC-алгоритм должен выбирать действие, чья ценность является $\epsilon$-оптимальной, то есть удовлетворяет условию:

$$Q(a_t) \ge Q(a^*) - \epsilon$$

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

Количество допустимых «плохих» шагов (выходящих за рамки $\epsilon$-оптимальности) жестко зависит от параметров сложности среды:

* При уменьшении значения $\epsilon$ (требования к точности) необходимый объем данных растет пропорционально $1/\epsilon^2$.
* Снижение параметра $\delta$ (требование к надежности и уверенности) также влечет за собой необходимость сбора большего объема информации.
* Большое количество доступных действий в среде линейно увеличивает число шагов, требуемых для обучения.

Разницу между регретом и PAC профессор наглядно демонстрирует на шуточном медицинском примере лечения травмы пальцев ног с помощью операции, фиксации пластырем или отказа от вмешательства. Пусть истинная ценность операции составляет 0.9, фиксации — 0.86, а бездействия — 0.2. Если задать порог $\epsilon = 0.05$, то ценность фиксации пластырем попадает в доверительный интервал оптимальности. С точки зрения PAC-критерия выбор этого метода не будет считаться ошибкой алгоритма, в то время как классический регрет начислит штраф за любое, даже минимальное отклонение от идеального выбора в 0.9. Таким образом, PAC игнорирует мелкие погрешности, фокусируясь на ограничении количества катастрофических ошибок.

## 🎲 Байесовский подход и магия сопряженных распределений
[[JUMP:37:04]]

Часто используемые частотные (фреквентистские) методы, включая границы Хёфдинга, не накладывают никаких априорных допущений на распределение наград в среде, кроме требования их ограниченности и независимости. Однако в реальной инженерной или медицинской практике эксперты часто заранее знают природу генерации данных — например, что награда распределена по Гауссу или подчиняется схеме Бернулли. Байесовский подход позволяет напрямую встроить эти знания в структуру бандитских алгоритмов для ускорения сходимости.

В основе байесовского вывода лежит планомерное обновление априорного распределения параметров (prior) на основе совершаемых наблюдений. Если вероятность выздоровления пациента после хирургического вмешательства описывается неизвестным параметром $\theta$, исследователь формирует начальное распределение вероятностей для этого параметра. После проведения операции и фиксации исхода применяется классическая формула Байеса для вычисления апостериорного распределения (posterior):

$$P(\theta \mid R) = \frac{P(R \mid \theta) \cdot P(\theta)}{P(R)}$$

В данном уравнении математические компоненты имеют строгое назначение:

* $P(\theta)$ — априорная вероятность параметра, отражающая начальную гипотезу экспериментатора.
* $P(R \mid \theta)$ — функция правдоподобия (likelihood), показывающая вероятность получить конкретную награду $R$ при заданном значении параметра.
* $P(R)$ — полная вероятность получения такой награды, рассчитываемая путем маргинализации (интегрирования) совместного распределения по всему пространству параметров.

В общем случае вычисление этого интеграла в знаменателе представляет собой колоссальную вычислительную сложность. Однако математики обнаружили элегантное семейство сопряженных априорных распределений (conjugate priors). Их фундаментальное свойство заключается в том, что после применения формулы Байеса апостериорное распределение сохраняет ту же самую статистическую структуру и принадлежит к тому же семейству, что и априорное.

Для бинарных наград (распределение Бернулли) идеальным сопряженным распределением является бета-распределение. Его формула содержит гамма-функции и параметры $\alpha$ и $\beta$, но алгоритм обновления невероятно прост и интуитивен. Параметры $\alpha$ и $\beta$ можно интерпретировать как счетчики успехов и неудач. Если алгоритм выбирает рукав и получает награду 1, параметр $\alpha$ увеличивается на единицу. Если выпадает 0, на единицу увеличивается параметр $\beta$. 

Таким образом, вся байесовская статистика сводится к банальному инкременту счетчиков, избавляя компьютер от сложных процедур интегрирования. Начальные значения параметров позволяют гибко задавать степень уверенности эксперта: значения $\alpha=100, \beta=2$ моделируют твердую убежденность в успехе, тогда как параметры $\alpha=1, \beta=1$ задают абсолютно плоское, неинформативное равномерное распределение, означающее полное неведение.

## 🏹 Сэмплирование Томпсона: алгоритм и визуальная интуиция
[[JUMP:47:41]]

Исторически алгоритм подбора распределений (probability matching), известный сегодня как сэмплирование Томпсона, был предложен ученым Уильямом Томпсоном еще в районе 1919 года. Однако сообщество машинного обучения фактически забыло про него почти на 80 лет, вернув в авангард науки лишь в 2010–2011 годах, когда обнаружилось его колоссальное эмпирическое превосходство над жесткими схемами UCB.

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

1.  Из текущего апостериорного распределения каждого рукава случайным образом извлекается (сэмплируется) конкретное значение параметра ценности.
2.  Среди полученных случайных чисел находится максимальное, и алгоритм выполняет соответствующее ему действие.
3.  Наблюдается реальная награда от среды.
4.  Апостериорное распределение выбранного рукава обновляется по правилам сопряженных распределений (путем инкремента $\alpha$ или $\beta$).

Профессор детально демонстрирует этот процесс на графиках для примера с травмированными пальцами ног, начиная с абсолютно плоских априорных распределений Beta(1,1) для всех трех методов лечения. В рамках первой итерации случайный сэмпл для операции дает значение 0.3, для фиксации пластырем — 0.5, а для бездействия — 0.6. Алгоритм выбирает бездействие как максимальное значение, но пациент не выздоравливает (награда 0). Распределение для бездействия мгновенно трансформируется в Beta(1,2), и его график математически прогибается, перенося основную массу вероятности ближе к нулю, поскольку низкие значения параметров с большей вероятностью генерируют неудачи.

На следующем шаге старые сэмплы выбрасываются. Алгоритм сэмплирует заново из распределений Beta(1,1) для первых двух рукавов и Beta(1,2) для третьего. Теперь вероятность вытащить высокое значение для бездействия существенно ниже. Сэмпл операции оказывается равен 0.7, что приводит к ее выбору и успешному исходу (награда 1). Распределение операции превращается в симметричное Beta(2,1). 

С каждым новым успехом график этого рукава трансформируется из прямой линии в крутую кривую Beta(3,1), смещаясь вправо и постепенно концентрируясь (сужаясь) вокруг истинного значения эффективности. Сэмплирование Томпсона демонстрирует важное отличие от UCB: оно не требует обязательного предварительного прокликивания каждого рукава по одному разу для инициализации границ и начинает эффективную работу с первого же шага.

## 📈 Сравнительный анализ Yahoo: работа бандитов в условиях лагов
[[JUMP:1:03:10]]

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

Профессор ссылается на хрестоматийную исследовательскую работу Оливье Шапеля и Лихонга Ли, работавших в Yahoo. Они тестировали контекстных бандитов на задаче построения рекомендаций новостных статей, где контекстом выступали признаки пользователя, действиями — статьи, а бинарной наградой — клик (Click-Through Rate, CTR), моделируемый логистической регрессией. Главным предметом изучения было влияние временной задержки (delay) получения обратной связи на качество работы систем. В реальном бизнесе Amazon или Yahoo пользователь может увидеть товар или новость сейчас, а кликнуть или совершить покупку лишь спустя значительное время.

В ходе экспериментов сравнивались алгоритмы: стандартное сэмплирование Томпсона (TS), оптимистичное сэмплирование Томпсона (OTS), UCB и эпсилон-жадная стратегия (EG). Результаты показали следующую динамику:

* **Поведение UCB:** При минимальной задержке алгоритм демонстрирует хорошие показатели, однако по мере роста лага обратной связи его эффективность драматически падает.
* **Поведение Сэмплирования Томпсона:** График эффективности TS остается практически плоским и стабильным даже при очень длительных задержках данных.

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

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

## 👑 Проблема оптимальности и теоретический индекс Гиттинса
[[JUMP:1:13:32]]

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

Эту задачу можно математически переформулировать как частично наблюдаемый марковский процесс принятия решений (POMDP) над самими параметрами распределения. В такой мета-модели:

* Текущим состоянием являются сами скрытые параметры.
* Действиями — выбор рукавов бандита.
* Пространством убеждений (belief state) — текущие плотности вероятностей параметров.

Решение такого POMDP через динамическое программирование гарантирует получение математически безупречной стратегии. Однако на практике это абсолютно нереализуемо (intractable): размерность истории действий и наград растет экспоненциально с увеличением временного горизонта, упираясь в комбинаторный взрыв.

Чтобы обойти это проклятие размерности, ученые используют так называемые индексные политики (index policies). Их суть заключается в том, что для каждого рукава на основе исключительно его собственной локальной статистики и оставшегося временного горизонта рассчитывается одно вещественное число — индекс. Алгоритм просто выбирает рукав с наивысшим показателем, полностью игнорируя сложные экспоненциальные взаимосвязи всей истории. И жадный алгоритм, и семейство UCB технически являются индексными политиками.

Удивительный прорыв в этой области совершил математик Джон Гиттинс. Он строго доказал теорему, согласно которой для байесовских многоруких бандитов с дисконтированием выигрыша существует специфический индекс (индекс Гиттинса), который превращает индексную политику в абсолютно оптимальное решение задачи. Это уникальный случай, когда локальные независимые вычисления для каждого рукава позволяют достичь глобального максимума POMDP без экспоненциальных затрат. Сэмплирование Томпсона математически не эквивалентно индексу Гиттинса, однако ввиду простоты реализации и надежности оно остается главным практическим выбором инженеров по всему миру.