Мультиармные бандиты

Мультиармные бандиты (англ. multi-armed bandits) — класс задач и методов в теории принятия решений, машинном обучении и статистике, моделирующих ситуацию выбора между несколькими альтернативами (действиями, стратегиями) с неизвестной заранее отдачей. Название происходит от образа игрока перед рядом одноруких бандитов (игровых автоматов), каждый из которых имеет свою, неизвестную игроку, вероятность выигрыша. Цель — максимизировать суммарный выигрыш за заданное число попыток, находя баланс между исследованием новых автоматов (exploration) и эксплуатацией уже известных с высокой отдачей (exploitation).

Определение и формализация

В классической постановке задача мультиармного бандита формулируется следующим образом. Имеется конечное множество «рук» (действий) \( A = \{1, 2, \dots, K\} \). Каждая рука \( i \) имеет неизвестное распределение вероятностей \( P_i \) с математическим ожиданием \( \mu_i \) (средняя отдача). На каждом шаге \( t = 1, 2, \dots, T \) агент выбирает руку \( a_t \in A \) и получает случайную награду \( r_t \sim P_{a_t} \). Цель агента — максимизировать ожидаемый суммарный выигрыш \( \mathbb{E}[\sum_{t=1}^T r_t] \).

Ключевым понятием является регрет (regret) — разница между суммарным выигрышем, который мог бы быть получен при постоянном выборе оптимальной руки с максимальным средним \( \mu^ = \max_i \mu_i \), и фактическим выигрышем: \[ R_T = T \mu^ - \mathbb{E}\left[\sum_{t=1}^T r_t\right]. \] Задача агента — минимизировать регрет, то есть как можно быстрее идентифицировать лучшую руку и минимизировать потери от выбора субоптимальных вариантов.

История

Задача мультиармного бандита была впервые сформулирована в 1933 году американским математиком Уильямом Томпсоном в контексте клинических испытаний. Томпсон предложил вероятностный подход (ныне известный как выборка Томпсона) для распределения пациентов между несколькими методами лечения с неизвестной эффективностью. В 1952 году Герберт Роббинс формализовал задачу как проблему последовательного выбора в условиях неопределённости. В 1985 году Т. Лай и Х. Роббинс установили фундаментальные нижние границы регрета для стохастических бандитов, показав, что регрет любого алгоритма растёт как минимум логарифмически по времени \( T \). Развитие методов мультиармных бандитов продолжилось в 1990-х — 2000-х годах в связи с ростом интереса к онлайн-обучению и рекомендательным системам. Крупные технологические компании, включая Google, Microsoft и Яндекс, внедрили алгоритмы бандитов для оптимизации рекламных кампаний и персонализации контента.

Классификация и виды

Задачи мультиармных бандитов делятся на несколько основных типов в зависимости от свойств среды и дополнительных ограничений.

Стохастические бандиты

Наиболее распространённый тип. Каждая рука имеет фиксированное, но неизвестное распределение наград. Награды независимы во времени. Алгоритмы для этого случая включают:

• ε-жадный алгоритм — с вероятностью \( \varepsilon \) выбирает случайную руку (исследование), с вероятностью \( 1-\varepsilon \) — руку с максимальной средней наградой (эксплуатация).
• Upper Confidence Bound (UCB) — выбирает руку с максимальной верхней границей доверительного интервала для средней награды. Формула: \( a_t = \arg\max_i \left( \hat{\mu}_i + \sqrt{\frac{2 \ln t}{n_i}} \right) \), где \( \hat{\mu}_i \) — эмпирическое среднее, \( n_i \) — число выборов руки \( i \).
• Выборка Томпсона — байесовский метод: для каждой руки поддерживается апостериорное распределение её среднего, на каждом шаге из каждого распределения берётся случайная выборка, выбирается рука с максимальным значением выборки.

Адверсариальные (противоборствующие) бандиты

Награды не предполагают стационарности и могут выбираться противником (адаптивно). Классический алгоритм — EXP3 (Exponential-weight algorithm for Exploration and Exploitation), использующий взвешенную случайную выборку с экспоненциальным обновлением весов.

Контекстуальные бандиты

На каждом шаге перед выбором руки агенту предоставляется контекст (вектор признаков, описывающий ситуацию). Награда зависит как от выбранной руки, так и от контекста. Этот тип широко применяется в рекомендательных системах, где контекстом может быть профиль пользователя или время суток. Алгоритмы: LinUCB, Thompson sampling with linear models.

Бандиты с ограничениями

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

Применение

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

Рекламные системы

В интернет-рекламе алгоритмы бандитов используются для выбора рекламного объявления или креатива, которое будет показано конкретному пользователю. Система одновременно исследует эффективность новых объявлений и эксплуатирует уже проверенные. Например, Яндекс и Google применяют контекстуальные бандиты для оптимизации кликабельности (CTR) в реальном времени.

Рекомендательные системы

Бандиты позволяют решать проблему «холодного старта» — рекомендации контента новым пользователям, о которых нет истории. Алгоритм может предлагать разные варианты (статьи, видео, товары) и быстро адаптироваться к предпочтениям пользователя. В новостных агрегаторах, таких как Google News, используются контекстуальные бандиты для персонализации ленты новостей.

Клинические испытания

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

Обучающие системы

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

Финансы и трейдинг

Бандиты применяются для выбора стратегий управления портфелем активов в условиях неопределённости. Каждая рука соответствует инвестиционной стратегии, награда — доходность. Алгоритм балансирует между исследованием новых стратегий и эксплуатацией проверенных.

Алгоритмы и методы

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

Алгоритмы на основе градиентов

Gradient Bandit Algorithms — используют стохастический градиент для обновления предпочтений каждой руки. На каждом шаге выбирается рука с вероятностью, пропорциональной экспоненте от её предпочтения, затем предпочтения обновляются с учётом полученной награды.

Бандиты с конечным горизонтом

Для случая, когда общее число шагов \( T \) известно заранее, существуют алгоритмы с оптимальным регретом, например, UCB-V (с учётом дисперсии) или KL-UCB, использующие расхождение Кульбака — Лейблера для построения более точных доверительных интервалов.

Многорукие бандиты с переключением

В задачах, где среда может меняться (нестационарные распределения), применяются алгоритмы с адаптивным окном, такие как SW-UCB (Sliding Window UCB), которые сбрасывают старые наблюдения и учитывают только последние данные.

Критика и ограничения

Несмотря на широкое применение, мультиармные бандиты имеют ряд ограничений. Основное — предположение о независимости наград между руками, которое редко выполняется в реальных системах (например, эффект от показа одного объявления может зависеть от того, какие объявления были показаны ранее). Контекстуальные бандиты частично решают эту проблему, но требуют больше данных и вычислительных ресурсов.

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

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

Связь с другими областями

Мультиармные бандиты тесно связаны с задачами обучения с подкреплением (Reinforcement Learning, RL). В RL агент взаимодействует с динамической средой, где текущие действия влияют на будущие состояния. Бандиты рассматриваются как частный случай RL с одним состоянием (контекст может быть интерпретирован как состояние, но без перехода). Методы, разработанные для бандитов (например, UCB и выборка Томпсона), часто используются как компоненты более сложных RL-алгоритмов.

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

Источники

• Robbins, H. (1952). Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society.
• Lai, T. L., & Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics.
• Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine Learning.
• Chapelle, O., & Li, L. (2011). An empirical evaluation of Thompson sampling. Advances in Neural Information Processing Systems.
• Slivkins, A. (2019). Introduction to Multi-Armed Bandits. Foundations and Trends in Machine Learning.