Упрощённый без состояний: выбираем действие, получаем награду и балансируем исследование с эксплуатацией.
Ключевые тезисы
- Thompson sampling и UCB — два рабочих алгоритма с теоретическими гарантиями.
- Контекстные учитывают пользователя — это уже полноценная рекомендательная модель.
- В отличие от , бандит минимизирует потери во время эксперимента.
Какую задачу решает
Многорукий бандит — упрощённое без состояний: есть несколько вариантов действия, у каждого неизвестная средняя награда, и нужно за серию попыток набрать максимум. Действие не меняет мир, поэтому вся задача сводится к одному напряжению — исследовать варианты или эксплуатировать лучший из найденных.
На практике это самая применимая часть . решают ровно ту задачу, которую в продукте обычно решают A/B-тестами, но эффективнее: вместо фиксированного разделения трафика пополам они постепенно перенаправляют его на выигрывающий вариант, теряя меньше на заведомо плохих.
Пять вариантов баннера, из них один вдвое лучше остальных, трафик 100 000 показов. отдаёт каждому варианту по 20 000 показов, то есть 80 000 показов уходит на заведомо худшие. Бандит на алгоритме Thompson sampling за первые несколько тысяч показов уверенно определит лидера и дальше будет отдавать ему около 80–90% трафика, продолжая изредка проверять остальных. Выигрыш по суммарной конверсии — десятки процентов. Плата: точных по каждому варианту вы не получите, потому что показы распределены неравномерно и не случайно.
Подробный разбор
- среднее значение
- число объектов в выборке
- логарифм: превращает произведения в суммы и сжимает масштаб
Thompson sampling делает то же самое вероятностно: сэмплирует значение из апостериорного распределения каждой руки и выбирает максимум. На практике обычно работает не хуже UCB и проще настраивается.
| Бандит | ||
|---|---|---|
| Цель | измерить эффект | максимизировать награду |
| Потери во время эксперимента | высокие | низкие |
| Статистический вывод | строгий | сложнее |
| Когда выбирать | нужно решение и цифра | нужен результат здесь и сейчас |
Контекстные — мост к рекомендациям: выбор варианта зависит от пользователя, и модель обучается онлайн.
Где применяется
- Выбор варианта интерфейсаАльтернатива A/B-тесту с меньшими потерями на плохих вариантах.
- Рекомендации и баннерыКакой контент показать, обучаясь на кликах в реальном времени.
- Динамическое ценообразованиеПодбор цены с обучением на отклике.
- Клинические испытанияИсторическая мотивация задачи: меньше пациентов получают заведомо худшее лечение.
- Холодный стартНовый товар или контент нужно исследовать, не теряя слишком много.
Плюсы, минусы и альтернативы
Плюсы
- Меньше потерь, чем у : трафик перетекает к лучшему варианту по ходу.
- Работает бесконечно: не требует фиксированной даты окончания.
- Легко добавлять и убирать варианты на ходу.
- Контекстные версии дают персонализацию почти бесплатно.
Минусы
- Не даёт строгого статистического вывода о размере эффекта.
- Неверно работает при нестационарности, если не предусмотреть забывание.
- Требует быстрой обратной связи: отложенная награда ломает схему.
- Сложнее в эксплуатации и отладке, чем обычный .
Брать, если
- Вариантов много и хочется минимизировать потери на плохих.
- Обратная связь приходит быстро.
- Варианты нужно добавлять и убирать без остановки эксперимента.
Не брать, если
- Нужен строгий вывод «вариант B лучше на 3% ± 1%» — берите .
- Награда приходит через недели.
- Вариантов два и трафика много: A/B проще и понятнее.
Чем заменяют
Видеолекции
Записи университетских курсов, где эта тема звучит. Ссылка открывает запись с той секунды, где о ней говорят, — искать по трёхчасовой лекции не нужно.
Связанные темы
Решения в условиях неопределённости
Offline RL80%
Оффлайн RL · Обучение с подкреплениемОбучение политики по логам прошлых взаимодействий, без возможности экспериментировать со средой.
Beta Distribution80%
Бета-распределение · Теория вероятностей и распределенияРаспределение вероятности на отрезке [0,1] — естественный априор для конверсии и для многоруких бандитов.
A/B testing80%
A/B-тестирование · Оценка моделейОнлайн-эксперимент, который единственный честно измеряет влияние модели на продуктовые метрики.
Experiment Infrastructure80%
Инфраструктура экспериментов · Системный дизайн ML-сервисовМеханика раскатки: разделение трафика, стабильные группы, метрики и автоматический откат.
Bayesian Optimization80%
Байесовская оптимизация · Практика MLСтроит модель зависимости метрики от гиперпараметров и выбирает следующую точку осознанно.
Всё, что названо в описании, разобрано здесь же или в соседней теме — переходы под каждым определением.
Исследование и эксплуатация
Пробовать новое или брать лучшее известное. Основной компромисс задачи.
Разбор ниже: UCB и Thompson sampling-жадная стратегия
С вероятностью случайное действие, иначе лучшее. Просто и работает.
Разбор ниже: UCB и Thompson samplingUCB
Выбор по верхней доверительной границе: неопределённость сама подталкивает к исследованию.
Разбор ниже: UCB и Thompson samplingThompson sampling
Байесовский подход: сэмплируем оценку из апостериорного распределения и берём лучшую. На практике часто сильнейший.
Разбор ниже: UCB и Thompson samplingКонтекстные бандиты
Награда зависит от ситуации — мост между бандитами и персонализацией.
Разбор ниже: Бандит против A/B-тестаУсиливает профиль: Инженер рекомендаций.
Спрашивают на собеседовании: Яндекс — RecSys, Сбер — Рекомендации и персонализация, Т-Банк — Рекомендации и персонализация, VK — Лента и рекомендации, Альфа-Банк — Персонализация и CVM, ЮMoney — Конверсия платежа и эксперименты, Магнит — Лояльность и персонализация, билайн — Маркетинг и удержание.
Тема встречается в тесте по направлениям — ошибки приведут обратно на эту страницу.
Глава «Обучение с подкреплением» последний раз правилась . Нашли ошибку — напишите.