Многорукий бандит

Материал из MachineLearning.

(Различия между версиями)

Перейти к: навигация, поиск

Текущая версия

Статья написана с использованием LLM ChatGPT 5.5 и проверена участником Liliia Davletova

Содержание

1 Многорукий бандит

Многорукий бандит

Многорукий бандит (Multi-Armed Bandit, MAB) — классическая задача обучения с подкреплением, теории принятия решений и машинного обучения, в которой агент последовательно выбирает одно из нескольких действий (рук, arms) с неизвестным распределением вознаграждений. Цель агента — максимизировать суммарное полученное вознаграждение, одновременно решая фундаментальную проблему баланса исследования и эксплуатации (exploration–exploitation trade-off).

Задача многорукого бандита является одним из наиболее изученных объектов современной теории обучения. Она лежит в основе систем рекомендаций, онлайн-рекламы, A/B-тестирования, медицинских исследований, управления вычислительными ресурсами, робототехники и многих других областей.

Интуитивное объяснение

Название происходит от игровых автоматов («одноруких бандитов»). Представим казино, в котором имеется K игровых автоматов. Каждый автомат имеет неизвестную вероятность выигрыша.

Игрок может многократно выбирать автомат, но заранее не знает, какой из них наиболее выгоден.

Возникает дилемма:

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

Если исследовать слишком долго, теряется накопленная прибыль. Если исследовать слишком мало, можно навсегда пропустить оптимальное действие.

Именно этот компромисс составляет основную сложность задачи.

Формальная постановка

Пусть имеется множество действий

$\mathcal{A}=\{1,\ldots,K\}.$

Каждому действию соответствует неизвестное распределение наград

$P_i(r).$

На шаге $t$ агент выбирает действие

$A_t \in \mathcal A,$

после чего получает случайную награду

$R_t \sim P_{A_t}.$

Среднее вознаграждение действия определяется как

$\mu_i=\mathbb E[R|A=i].$

Оптимальная рука

$i^*=\arg\max_i\mu_i.$

Цель состоит в максимизации

$\sum_{t=1}^{T}R_t.$

Регрет

Качество алгоритмов обычно измеряется через регрет (regret).

Накопленный регрет определяется как

$R(T)=T\mu^*-\sum_{t=1}^{T}\mu_{A_t},$

где

$\mu^*=\max_i\mu_i.$

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

Для хорошего алгоритма желательно, чтобы

$R(T)=O(\log T)$

или

$R(T)=O(\sqrt{T}),$

в зависимости от постановки задачи.

Исследование и эксплуатация

Практически все алгоритмы многорукого бандита отличаются способом решения компромисса между исследованием и эксплуатацией.

Исследование позволяет получить информацию о малоизученных действиях.

Эксплуатация использует уже накопленные знания для максимизации текущей прибыли.

Именно баланс между ними отличает задачи многорукого бандита от классической оптимизации.

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

ε-greedy

Самый простой алгоритм.

С вероятностью

$\varepsilon$

выбирается случайное действие.

С вероятностью

$1-\varepsilon$

выбирается действие с максимальной оценкой среднего выигрыша.

Преимущества:

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

Недостатки:

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

Upper Confidence Bound (UCB)

Алгоритмы семейства Upper Confidence Bound используют принцип оптимизма при неопределенности.

Выбирается действие

$A_t=\arg\max_i\left(\hat\mu_i+c\sqrt{\frac{\ln t}{N_i}}\right),$

где

$\hat\mu_i$ — текущая оценка среднего выигрыша;
$N_i$ — число выборов данной руки;
$c$ — параметр исследования.

Редко исследованные действия получают высокий доверительный интервал и потому продолжают исследоваться.

Алгоритм UCB1 обладает логарифмическим регретом и стал одним из наиболее известных алгоритмов задачи многорукого бандита. :contentReference[oaicite:0]{index=0}

Thompson Sampling

Thompson Sampling представляет собой байесовский подход.

Для каждой руки поддерживается апостериорное распределение параметров.

На каждом шаге:

генерируется случайная оценка параметров каждой руки;
выбирается действие с максимальным сэмплом;
обновляется апостериорное распределение.

Для бернуллиевских наград используется сопряженная пара

$\theta_i\sim Beta(\alpha_i,\beta_i).$

После получения очередного результата параметры обновляются.

Метод отличается:

высокой практической эффективностью;
естественным учетом неопределенности;
простотой реализации.

В последние годы Thompson Sampling считается одним из наиболее успешных алгоритмов для прикладных систем рекомендаций. Его оптимальные оценки регрета были доказаны в серии работ 2012–2013 годов.

Контекстный многорукий бандит

Во многих приложениях перед выбором действия известен некоторый контекст

$x_t.$

Например:

профиль пользователя;
содержимое страницы;
время суток;
устройство.

В этом случае стратегия должна выбирать действие

$A_t=\pi(x_t),$

используя как накопленный опыт, так и текущий контекст.

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

Известные алгоритмы:

LinUCB;
Linear Thompson Sampling;
Neural Bandits;
NeuralUCB;
Bootstrapped Thompson Sampling.

Связь с обучением с подкреплением

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

Отличия:

Многорукий бандит	Обучение с подкреплением
одно состояние	множество состояний
отсутствуют переходы	имеется динамика среды
нет долгосрочного планирования	требуется оптимизация стратегии

Поэтому многие идеи обучения с подкреплением сначала исследуются именно на задаче многорукого бандита.

Современные направления исследований

В последние годы активно исследуются следующие расширения классической постановки.

Нестационарные бандиты

Распределения наград изменяются во времени.

Используются:

Sliding Window UCB;
Discounted UCB;
Change-point Detection;
Adaptive Thompson Sampling.

Линейные и обобщенные бандиты

Среднее вознаграждение зависит от признаков объекта.

Используются модели

$r=x^\top\theta+\varepsilon.$

Комбинаторные бандиты

За один шаг выбирается сразу множество действий.

Применяются при:

маршрутизации;
поиске;
рекомендациях;
распределении ресурсов.

Байесовские бандиты

Предполагается наличие априорных знаний о распределениях наград.

Используются методы:

Thompson Sampling;
Bayesian UCB;
Information Directed Sampling.

Нейронные бандиты

Функция ожидаемого вознаграждения моделируется глубокой нейронной сетью.

Подходы используются в современных рекомендательных системах и онлайн-рекламе.

Гибридные алгоритмы

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

Применения

Многорукие бандиты широко используются в:

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

См. также

Литература

Auer P., Cesa-Bianchi N., Fischer P. Finite-time Analysis of the Multiarmed Bandit Problem // Machine Learning. — 2002. — Т. 47. — № 2–3. — С. 235–256.

Thompson W. R. On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples // Biometrika. — 1933. — Т. 25. — № 3–4. — С. 285–294.

Lai T., Robbins H. Asymptotically Efficient Adaptive Allocation Rules // Advances in Applied Mathematics. — 1985. — Т. 6. — № 1. — С. 4–22.

Agrawal S., Goyal N. Analysis of Thompson Sampling for the Multi-Armed Bandit Problem // Conference on Learning Theory. — 2012.

Li L., Chu W., Langford J., Schapire R. A Contextual-Bandit Approach to Personalized News Article Recommendation // WWW. — 2010. — С. 661–670.

Sutton R., Barto A. Reinforcement Learning: An Introduction. — MIT Press. — 2018.

Lattimore T., Szepesvári C. Bandit Algorithms. — Cambridge University Press. — 2020.

Russo D., Van Roy B., Kazerouni A., Osband I., Wen Z. A Tutorial on Thompson Sampling // Foundations and Trends in Machine Learning. — 2018. — Т. 11. — № 1. — С. 1–96.

Lattimore T., Szepesvári C. Bandit Algorithms2026-06-30.

TS-UCB: Improving on Thompson Sampling With Little to No Additional Computation2026-06-30.

Источник — «http://83.149.227.45/wiki/index.php?title=%D0%9C%D0%BD%D0%BE%D0%B3%D0%BE%D1%80%D1%83%D0%BA%D0%B8%D0%B9_%D0%B1%D0%B0%D0%BD%D0%B4%D0%B8%D1%82»

@@ Строка 3: / Строка 3: @@
 = Многорукий бандит =
-'''Многорукий бандит''' (Multi-Armed Bandit, '''MAB''') — классическая задача [[обучение с подкреплением|обучения с подкреплением]], [[теория принятия решений|теории принятия решений]] и [[машинное обучение|машинного обучения]], в которой агент последовательно выбирает одно из нескольких действий (''рук'', ''arms'') с неизвестным распределением вознаграждений. Цель агента — максимизировать суммарное полученное вознаграждение, одновременно решая фундаментальную проблему '''баланса исследования и эксплуатации''' ({{lang-en|exploration–exploitation trade-off}}).
+'''Многорукий бандит''' (Multi-Armed Bandit, '''MAB''') — классическая задача [[обучение с подкреплением|обучения с подкреплением]], [[теория принятия решений|теории принятия решений]] и [[машинное обучение|машинного обучения]], в которой агент последовательно выбирает одно из нескольких действий (''рук'', ''arms'') с неизвестным распределением вознаграждений. Цель агента — максимизировать суммарное полученное вознаграждение, одновременно решая фундаментальную проблему '''баланса исследования и эксплуатации''' (exploration–exploitation trade-off).
 Задача многорукого бандита является одним из наиболее изученных объектов современной [[теория обучения|теории обучения]]. Она лежит в основе систем рекомендаций, [[онлайн-реклама|онлайн-рекламы]], A/B-тестирования, медицинских исследований, управления вычислительными ресурсами, робототехники и многих других областей.
@@ Строка 147: / Строка 147: @@
 Для бернуллиевских наград используется сопряженная пара
-:<math>
+:<tex>\theta_i\sim Beta(\alpha_i,\beta_i).</tex>
-\theta_i\sim Beta(\alpha_i,\beta_i).
-</math>
 После получения очередного результата параметры обновляются.
@@ Строка 159: / Строка 157: @@
 * простотой реализации.
-В последние годы Thompson Sampling считается одним из наиболее успешных алгоритмов для прикладных систем рекомендаций. Его оптимальные оценки регрета были доказаны в серии работ 2012–2013 годов. :contentReference[oaicite:1]{index=1}
+В последние годы Thompson Sampling считается одним из наиболее успешных алгоритмов для прикладных систем рекомендаций. Его оптимальные оценки регрета были доказаны в серии работ 2012–2013 годов.
 == Контекстный многорукий бандит ==
@@ Строка 264: / Строка 262: @@
 === Гибридные алгоритмы ===
-Современные исследования объединяют достоинства различных методов. Например, алгоритм TS-UCB сочетает байесовский выбор действий с доверительными оценками UCB и демонстрирует улучшенный регрет на синтетических и прикладных задачах. :contentReference[oaicite:2]{index=2}
+Современные исследования объединяют достоинства различных методов. Например, алгоритм TS-UCB сочетает байесовский выбор действий с доверительными оценками UCB и демонстрирует улучшенный регрет на синтетических и прикладных задачах.
 == Применения ==

Многорукий бандит

Материал из MachineLearning.

Текущая версия

Содержание

Многорукий бандит

Интуитивное объяснение

Формальная постановка

Регрет

Исследование и эксплуатация

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

ε-greedy

Upper Confidence Bound (UCB)

Thompson Sampling

Контекстный многорукий бандит

Связь с обучением с подкреплением

Современные направления исследований

Нестационарные бандиты

Линейные и обобщенные бандиты

Комбинаторные бандиты

Байесовские бандиты

Нейронные бандиты

Гибридные алгоритмы

Применения

См. также

Литература

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты