Задача многорукого бандита: алгоритмы и решения
Разбираем задачу многорукого бандита: от ε-жадного алгоритма до UCB и сэмплирования Томпсона. Практические примеры и код.
Введение: когда выбор стоит денег
Представьте, что вы стоите в зале казино перед рядом игровых автоматов. У каждого — своя (неизвестная вам) вероятность выигрыша. У вас ограниченное количество попыток. Как действовать: всё время тянуть за один рычаг, который уже дал выигрыш? Или методично проверять остальные в надежде найти лучший?
Это и есть задача многорукого бандита (Multi-Armed Bandit, MAB) — один из фундаментальных вопросов теории принятия решений и обучения с подкреплением (Reinforcement Learning). За простой игровой метафорой скрывается проблема, которая встречается в A/B-тестировании, персонализации контента, клинических испытаниях, рекламных системах и управлении портфелем.
В этой статье мы разберём суть дилеммы, математику за ней и главные алгоритмические решения — от наивного ε-жадного до байесовского сэмплирования Томпсона.
Формализация задачи
Что такое «бандит»?
Термин «однорукий бандит» — жаргонное название игрового автомата (он «грабит» игроков). «Многорукий бандит» — это задача с K рычагами, каждый из которых при нажатии выдаёт случайное вознаграждение из некоторого (неизвестного) распределения.
Формально:
- Есть K действий (рычагов) $a_1, a_2, \ldots, a_K$
- Каждое действие $a_i$ имеет истинное среднее вознаграждение $Q^*(a_i)$, неизвестное агенту
- На каждом шаге $t$ агент выбирает действие $A_t$ и получает вознаграждение $R_t$
- Цель: максимизировать суммарное вознаграждение за $T$ шагов
Дилемма исследования и эксплуатации
«Эксплуатация использует лучшее из того, что вы уже знаете, но исследование может помочь найти нечто лучшее в будущем.»
Это ключевое противоречие в MAB и в обучении с подкреплением в целом:
- Эксплуатация (Exploitation): выбирать действие с наибольшей известной на данный момент оценкой
- Исследование (Exploration): пробовать менее изученные действия, чтобы уточнить их реальную ценность
Делать только одно — проигрывать. Чистая эксплуатация зацикливается на субоптимальном рычаге. Чистое исследование игнорирует накопленные знания.
Качество стратегии оценивается через regret (сожаление) — разницу между тем, что мог заработать идеальный агент (всегда выбирающий лучший рычаг), и тем, что заработал реальный агент:
$$L_T = T \cdot Q^(a^) - \sum_{t=1}^{T} Q^*(A_t)$$
Хороший алгоритм должен добиваться сублинейного regret — то есть средние потери на шаг стремятся к нулю по мере роста $T$.
Алгоритм 1: ε-жадный (Epsilon-Greedy)
Самый простой и интуитивный подход. Идея: большую часть времени действуй жадно (выбирай лучший известный вариант), но с вероятностью ε — исследуй случайно.
Как работает
import numpy as np
class EpsilonGreedy:
def __init__(self, n_arms, epsilon=0.1):
self.n_arms = n_arms
self.epsilon = epsilon
self.counts = np.zeros(n_arms) # сколько раз выбирали руку i
self.values = np.zeros(n_arms) # оценка Q(a)
def select_arm(self):
if np.random.random() < self.epsilon:
return np.random.randint(self.n_arms) # исследование
return np.argmax(self.values) # эксплуатация
def update(self, arm, reward):
self.counts[arm] += 1
n = self.counts[arm]
# инкрементальное среднее
self.values[arm] += (reward - self.values[arm]) / n
Плюсы и минусы
Алгоритм прост в реализации и понятен. Однако у него есть врождённый недостаток: он исследует равномерно случайно — тратит одинаковое время на плохие и хорошие неизученные руки. Кроме того, фиксированное ε не адаптируется: в начале хочется больше исследовать, в конце — эксплуатировать.
Решение: убывающее ε — например, $\varepsilon_t = 1/t$ или $\varepsilon_t = \varepsilon_0 / \sqrt{t}$.
Алгоритм 2: Upper Confidence Bound (UCB)
ε-жадный алгоритм исследует случайно. UCB исследует умно: он явно учитывает неопределённость — чем реже выбиралась рука, тем выше её «оптимистичная» оценка.
Принцип оптимизма в условиях неопределённости
Идея UCB1 (Auer et al., 2002):
$$A_t = \arg\max_{a} \left[ Q_t(a) + c \cdot \sqrt{\frac{\ln t}{N_t(a)}} \right]$$
где:
- $Q_t(a)$ — текущая оценка ценности руки $a$
- $N_t(a)$ — сколько раз рука $a$ выбиралась до момента $t$
- $c$ — параметр уверенности (обычно 1 или 2)
- $\sqrt{\ln t / N_t(a)}$ — «бонус за неизученность»
Чем реже рука выбиралась относительно других, тем выше её UCB-оценка — и тем больше вероятность, что агент её исследует.
class UCB1:
def __init__(self, n_arms, c=2.0):
self.n_arms = n_arms
self.c = c
self.counts = np.zeros(n_arms)
self.values = np.zeros(n_arms)
self.total_steps = 0
def select_arm(self):
# сначала попробуем каждую руку хотя бы раз
for arm in range(self.n_arms):
if self.counts[arm] == 0:
return arm
ucb_scores = self.values + self.c * np.sqrt(
np.log(self.total_steps) / self.counts
)
return np.argmax(ucb_scores)
def update(self, arm, reward):
self.total_steps += 1
self.counts[arm] += 1
n = self.counts[arm]
self.values[arm] += (reward - self.values[arm]) / n
UCB1 достигает логарифмического regret $O(\ln T)$ — теоретически оптимального для стохастических бандитов.
Алгоритм 3: Сэмплирование Томпсона (Thompson Sampling)
Томпсон-сэмплирование — байесовский подход, предложенный ещё в 1933 году, но широко применяемый лишь с 2010-х. Здесь агент поддерживает вероятностное распределение над истинными ценностями каждой руки и обновляет его по наблюдениям.
Алгоритм для бернуллиевских наград (0/1)
Предположим, что вознаграждение каждой руки — бинарное (клик/не клик). Используем бета-распределение $\text{Beta}(\alpha, \beta)$ как сопряжённый приор:
- $\alpha_i$ — число успехов (наград 1) для руки $i$
- $\beta_i$ — число неудач (наград 0) для руки $i$
class ThompsonSampling:
def __init__(self, n_arms):
self.n_arms = n_arms
self.alpha = np.ones(n_arms) # successes + 1
self.beta = np.ones(n_arms) # failures + 1
def select_arm(self):
# сэмплируем θ из Beta-распределения для каждой руки
theta = np.random.beta(self.alpha, self.beta)
return np.argmax(theta)
def update(self, arm, reward):
# reward ∈ {0, 1}
self.alpha[arm] += reward
self.beta[arm] += (1 - reward)
Почему это работает?
По мере накопления данных бета-распределение «сужается» вокруг истинного значения. Рука, которая редко выигрывала, будет иметь широкое распределение — и иногда случайно получит высокий сэмпл, стимулируя исследование. Успешные руки — узкое распределение с высоким центром, что стимулирует эксплуатацию.
Томпсон-сэмплирование:
- Асимптотически оптимально (достигает нижней границы Lai-Robbins)
- Хорошо работает на практике, особенно при малом числе шагов
- Естественно расширяется на контекстуальные бандиты
Сравнение алгоритмов
| Алгоритм | Тип исследования | Regret | Сложность реализации | Адаптивность |
|---|---|---|---|---|
| ε-Greedy | Случайное | $O(T^{2/3})$ | ⭐ Низкая | Умеренная |
| Убывающий ε | Случайное | $O(\ln T)$ | ⭐⭐ Средняя | Хорошая |
| UCB1 | Оптимистичное | $O(\ln T)$ | ⭐⭐ Средняя | Умеренная |
| Thompson Sampling | Байесовское | $O(\ln T)$ | ⭐⭐⭐ Выше | Отличная |
| Gradient Bandit | Softmax | $O(\sqrt{T})$ | ⭐⭐ Средняя | Хорошая |
graph TD
A[Задача MAB] --> B{Есть контекст?}
B -- Нет --> C[Стохастический бандит]
B -- Да --> D[Контекстуальный бандит]
C --> E{Стационарное окружение?}
E -- Да --> F{Нужна простота?}
E -- Нет --> G[Sliding Window UCB / Discounted]
F -- Да --> H[ε-Greedy]
F -- Нет --> I{Байесовский подход?}
I -- Да --> J[Thompson Sampling]
I -- Нет --> K[UCB1]
D --> L[LinUCB / Neural Bandit]
Практические применения
A/B/n-тестирование
Классическое A/B-тестирование делит трафик поровну на фиксированный срок — и в итоге долго отправляет пользователей на плохой вариант. MAB-алгоритмы (особенно Томпсон-сэмплирование) адаптивно перераспределяют трафик в пользу лучших вариантов, минимизируя потери на этапе теста.
Microsoft, Google, Netflix используют MAB-подходы для тестирования интерфейсов и рекламных баннеров.
Рекомендательные системы
Рекомендации контента — классический контекстуальный бандит: у нас есть профиль пользователя (контекст), набор возможных рекомендаций (руки) и обратная связь (клик/просмотр). LinUCB и нейронные бандиты активно применяются в этой области.
Клинические испытания
В медицинских исследованиях MAB позволяет адаптивно направлять больше пациентов на более эффективное лечение — это Response-Adaptive Randomization. Это этически важнее фиксированного разбиения.
Автонастройка гиперпараметров
Bayesian Optimization — по сути бандит: каждый набор гиперпараметров — это «рука», а качество модели — вознаграждение. Инструменты вроде Optuna и Ray Tune используют похожие принципы.
Расширения: за пределами базового MAB
Контекстуальные бандиты (Contextual Bandits)
В реальных системах у нас всегда есть контекст — информация о пользователе, времени суток, устройстве. Контекстуальный бандит выбирает действие на основе контекста $x_t$:
$$A_t = \arg\max_a Q(x_t, a)$$
Популярный алгоритм — LinUCB, где ценность параметризована линейной функцией от контекста.
Адверсариальные бандиты
Что если среда враждебна и намеренно подбирает плохие вознаграждения? Для таких случаев разработан алгоритм EXP3 (Exponential-weight algorithm for Exploration and Exploitation), гарантирующий sublinear regret даже против адверсариального оппонента.
Бандиты с задержкой наград
В рекламе между показом и конверсией может пройти несколько дней. Алгоритмы с задержкой (Delayed Feedback Bandits) учитывают эту временну́ю асимметрию.
Заключение
Задача многорукого бандита — элегантная формализация универсальной человеческой проблемы: как принимать решения в условиях неполной информации, балансируя между использованием известного и поиском лучшего.
Главные выводы:
- ε-жадный — отправная точка, прост и работает, но исследует нецеленаправленно
- UCB1 — теоретически обоснован, логарифмический regret, отличный выбор для стационарных сред
- Thompson Sampling — практический фаворит, особенно при малых данных и бинарных наградах
- Для реальных систем почти всегда нужен контекстуальный бандит или полноценное RL
- Метрика regret — главный инструмент сравнения алгоритмов
МАB-алгоритмы — это не просто академическая задача. Они работают прямо сейчас в рекомендательных системах, рекламных платформах и медицинских испытаниях. Понимание их принципов даёт разработчику мощный инструмент для построения адаптивных, самооптимизирующихся систем.