Multi-armed bandit на собеседовании Data Scientist

Зачем разбирать на собесе

MAB — задача exploration vs exploitation. На собесе DS: «алгоритмы», «отличие от A/B test», «применения».

Постановка задачи

K arms (вариантов). Каждый arm — distribution rewards. Цель — maximize total reward за T rounds.

Каждый round: выбираем arm a_t.
Получаем reward r_t от arm a_t.

Trade-off:

• Exploration. Пробовать ранее непротестированные arms.
• Exploitation. Использовать best известный arm.

Чисто exploration — много reward потеряно. Чисто exploitation — можем застрять на subоптимальном.

Epsilon-greedy

Простейший подход.

With probability ε: explore (random arm).
With probability 1-ε: exploit (best known arm).

ε — гипepparam, обычно 0.05-0.2. Decaying ε лучше (epsilon = 1/t).

Pros: simple. Cons: иногда explores, даже когда нечего.

UCB

Upper Confidence Bound. Выбираем arm с максимальным UCB.

UCB_a = mean_reward_a + sqrt(2 ln(t) / n_a)

n_a — сколько раз a был выбран. t — total rounds.

Логика. Среднее + bonus за uncertainty. Less-tried arms имеют bigger bonus → forces exploration.

Pros: теоретически хорошие гарантии. Cons: detеrministic.

Thompson sampling

Bayesian подход. Каждому arm — Beta posterior на reward probability.

For each arm a:
  Sample θ_a from Beta(α_a, β_a) — текущий belief.
Choose arm with max sampled θ.
After observing reward r:
  Update Beta — α += r, β += (1-r).

Pros: хорошие практические результаты. Naturally explores when uncertain.

Cons: требует prior, более сложен в реализации.

Contextual bandits

Расширение — arm reward зависит от context (user features).

At round t: see context x_t (user, time, etc).
Choose arm a_t = π(x_t) — policy зависит от context.
Get reward r_t.

Алгоритмы:

• LinUCB — линейная регрессия + UCB.
• Neural bandits — DNN policy.

Применения: personalized recommendations, ad targeting.

MAB vs A/B

A/B test — лучше для продуктовых решений (нужна significance).

MAB — лучше для production ML (continuous traffic optimization).

Частые ошибки

MAB вместо A/B test. A/B test нужен для inference. MAB — для optimization. Не смешивать.

Reward delay. Если reward через 7 дней (subscription) — banished не подходит, нужен offline learning.

Без context на personalized. «User'ам нравится A в среднем» — но user X предпочитает B. Используй contextual.

Игнорировать non-stationarity. Reward distributions меняются со временем. Sliding window / discounting.

Слишком сильный exploration. Большой ε теряет потенциал, малый — застревает.

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

• A/B testing fundamentals
• Bayesian методы на собесе DS
• Active learning на собесе DS
• Collaborative filtering на собесе DS
• Подготовка к собесу Data Scientist

FAQ

Когда A/B, когда MAB?

A/B — нужно знать, какой вариант лучше (продуктовое решение). MAB — нужно continuously serve best variant.

Это официальная информация?

Нет. Статья основана на работах (Auer 2002 UCB, Thompson 1933, Li 2010 LinUCB).

Тренируйте Data Science — откройте тренажёр с 1500+ вопросами для собесов.