Online Learning и A/B Testing

Классический A/B тест 2 недели, 500k пользователей. За это время 3.5 миллиона сессий «потрачены» на заведомо худший вариант. Multi-armed bandit и interleaving решают эту проблему по-разному - и Netflix, и Spotify, и Google используют их в production вместо классических A/B тестов для рекомендаций.

• **Netflix:** Team Draft Interleaving - основной метод сравнения алгоритмов рекомендаций до A/B теста. Также использует contextual bandits для выбора обложки фильма: разным пользователям показывается разная обложка того же контента.
• **Spotify:** Discover Weekly построен на exploration стратегии. Система намеренно включает незнакомые треки - это exploration, которая обновляет модель вкуса пользователя и предотвращает filter bubble.
• **Google News:** Contextual Bandits (LinUCB) для персонализации новостного feed в реальном времени. Алгоритм учитывает контекст пользователя и адаптируется без полного переобучения модели.

Предварительные знания

• Вероятность и матожидание
• Проверка гипотез и доверительные интервалы
• Бандиты и exploration-exploitation

• Multi-Objective and Re-Ranking
• Evaluation

Бандиты, Thompson Sampling и онлайн-эксперименты

Проблема exploration-exploitation стара. В 1933 году William R. Thompson описал правило сэмплирования для выбора между двумя методами лечения через выборку из апостериорной вероятности того, что каждый из них лучший, идею, которую теперь называют Thompson sampling. Десятилетиями она почти не использовалась, а затем стала рабочей лошадкой онлайн-рекомендаций, как только системам понадобилось учиться на живой обратной связи. В 2010 году Lihong Li с коллегами в Yahoo представили LinUCB, контекстный бандит, который использует признаки пользователя и статьи для выбора новостей и балансирует награду против upper confidence bound на неопределённость, с несмещённым методом offline replay для оценки. Примерно в тот же период дисциплина online controlled experiments повзрослела в компаниях вроде Microsoft и Google, превратив A/B-тестирование в стандартный способ измерить, действительно ли изменение в рекомендациях помогает пользователям, а не просто лучше выглядит офлайн.

Multi-armed bandits: лучше A/B теста

Классический A/B тест - это расточительство. Пока идёт тест, половина пользователей получает заведомо худший вариант. При миллионе пользователей и 2-недельном тесте это 7 миллионов «потраченных» сессий на вариант B, который окажется хуже. Multi-armed bandit (задача многорукого бандита) решает это иначе: алгоритм адаптивно направляет больше трафика к лучшему варианту по мере накопления данных. Название - из теории вероятностей: представьте игровые автоматы (однорукие бандиты) с неизвестными вероятностями выигрыша. Нужно максимизировать суммарный выигрыш, не зная заранее, какой автомат лучший.

Основные алгоритмы: Epsilon-Greedy (с вероятностью epsilon исследуй случайный вариант, иначе выбирай лучший), UCB (Upper Confidence Bound - учитывай неопределённость, выбирай вариант с лучшим верхним доверительным интервалом), Thompson Sampling (байесовский: сэмплируй из апостериорного распределения каждого варианта). Thompson Sampling на практике превосходит epsilon-greedy при небольшом числе вариантов.

Explore-exploit дилемма в рекомендациях

Explore-exploit - фундаментальный конфликт рекомендательных систем. Exploitation: рекомендуй то, что заведомо нравится пользователю (выше краткосрочный engagement). Exploration: рекомендуй новое, чтобы узнать вкусы лучше (выше долгосрочное качество). Слишком много exploitation - пользователь застрял в filter bubble. Слишком много exploration - пользователь видит нерелевантный контент и уходит. Netflix тратит около 20% рекомендательных слотов на exploration. Spotify «Discovery Weekly» - чистая exploration стратегия с user согласия.

Контекстуальные bandits (Contextual Bandits) расширяют задачу: выбор руки зависит от контекста (features пользователя, времени, устройства). Алгоритм LinUCB линейно моделирует reward от контекста. Google использовал contextual bandits для персонализации новостей в Google News, Netflix - для выбора обложек фильмов (разным пользователям - разная обложка того же фильма).

Interleaving: быстрее A/B на два порядка

A/B тест для рекомендательных систем требует тысяч пользователей и нескольких недель для значимых результатов. Interleaving - альтернатива, разработанная в Netflix и Spotify: пользователю показывается смешанный список из двух алгоритмов A и B. Каждый item помечен своим источником. После взаимодействия считается, какой алгоритм «победил» у этого пользователя. Поскольку оба алгоритма конкурируют в одной сессии, смещение уменьшается в разы. Interleaving требует в 100-1000 раз меньше трафика для того же уровня уверенности.

Три типа interleaving: Team Draft Interleaving (случайно выбирается, кто делает следующий выбор из своего списка), Balanced Interleaving (чередование позиций), Probabilistic Interleaving (взвешенное смешивание по scores). Team Draft - наиболее распространён: он минимизирует позиционное смещение. Netflix использует Team Draft как основной метод сравнения алгоритмов перед A/B тестом.

Метрики качества рекомендаций

Метрика - это контракт между бизнесом и алгоритмом. Оптимизация не той метрики ведёт к Goodhart's Law: когда мера становится целью, она перестаёт быть хорошей мерой. YouTube оптимизировал watch time и получил алгоритм, рекламирующий сенсационный контент, - потому что он удерживает внимание. Рекомендательные системы имеют несколько классов метрик: offline (считаются на historical data без пользователей), online (A/B тест, реальные пользователи), proxy (быстрые, но не всегда коррелирующие с бизнес-целями).

NDCG (Normalized Discounted Cumulative Gain) - стандартная ranking метрика: учитывает релевантность и позицию. Precision@K и Recall@K - доля релевантных item в top-K. MRR (Mean Reciprocal Rank) - для систем, где важна позиция первого релевантного результата. Coverage - доля каталога, которую система рекомендует хотя бы раз (борьба с long-tail проблемой). Diversity - разнообразие рекомендаций внутри списка.

Ключевые идеи

• **Thompson Sampling** превосходит epsilon-greedy за счёт байесовского обновления уверенности. Алгоритм естественно уменьшает exploration по мере накопления данных без ручной настройки epsilon decay.
• **Interleaving** требует в 100-1000 раз меньше трафика, чем A/B тест, устраняя межсубъектную вариабельность: оба алгоритма конкурируют на одном пользователе в одной сессии.
• **Метрики - это контракт:** NDCG и offline метрики слабо коррелируют с online результатами. Watch time YouTube - классический пример Goodhart's Law. Правильная метрика важнее, чем правильный алгоритм.

Связанные темы

Online learning и тестирование связаны с production инфраструктурой рекомендательных систем:

• Serving рекомендаций — Online learning требует feature store для получения свежих признаков в real-time - без быстрого serving невозможен быстрый update модели
• Матричная факторизация — Online learning дополняет batch-обученные MF модели: bandits выбирают между несколькими моделями или дообучают top-layer в real-time

Вопросы для размышления

• Thompson Sampling использует Beta-распределение для Bernoulli reward (клик/нет клика). Как адаптировать алгоритм для непрерывного reward (время просмотра) и какое распределение подойдёт?
• Interleaving показывает пользователям смешанные списки без их ведома. Есть ли этические аргументы против этого, и как крупные компании обосновывают это в своих privacy политиках?
• Coverage метрика важна для long-tail items - редкого контента, который не попадает в рекомендации из-за недостатка данных. Как технически обеспечить минимальный coverage для long-tail без ущерба релевантности?

Связанные уроки

• rec-08 — Bandit-ы питают исследование внутри слоя реранкинга
• rec-12 — Онлайн-политики надо отдавать с малой задержкой
• rec-19-evaluation — Онлайн-тесты дополняют офлайн-метрики оценки
• ml-53-ab-testing-ml — Та же дисциплина A/B-тестов, что в ML
• stat-05-hypothesis — A/B-тестирование опирается на проверку гипотез