Всем привет! Меня зовут Саша, работаю ведущим аналитиком в Озон Банке. По мотивам доклада на онлайн-дне МатеМаркетинга'25 было решено написать данную статью, пересказывающую основные идеи доклада о семплировании Томпсона

Решаемая задача

Представьте: вы пришли в казино с кучей игровых автоматов.

• Вы хотите найти тот, в котором вероятность выигрыша наибольшая, проверяя автоматы путем игры в них.

• Каждая итерация проверки платная - вы хотите крутить "плохие" автоматы как можно меньше

Как же следует поступить, чтобы найти лучший автомат и параллельно с этим не переехать жить под мост? Ответ - алгоритмы семплирования, созданные для решения задач "многоруких бандитов". В данной статье мы поговорим про семплирование Томпсона в сравнении с эпсилон-жадным алгоритмом - одним из самых известных.

ε-жадный алгоритм

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

1. Первые N итераций (обычно 5-10% от выборки) - автоматы выбираются случайно

2. Далее, для каждой итерации "подбрасывается монетка":

   • С вероятность 1 - ε для итерации выбирается автомат с наибольшей оценкой по текущим данным

   • С вероятностью ε - случайный автомат

3. После этого история итераций обновляется

4. Возврат к шагу 2

У данного алгоритма есть свои недостатки:

• Доля ε всех попыток всегда тратится на случайные автоматы - неэффективно при высоком ε

• После обучения алгоритм может попасть на субоптимальный вариант - и очень нескоро вернуться к оптимальному при маленьком ε

Как же эти проблемы решает семплирование Томпсона?

Семплирование Томпсона

Данный алгоритм основан на сопряженных априорных распределениях - в нашем случае итерация каждого автомата имеет распределение Бернулли. Для Бернулли сопряженным является Бета-распределение:

Данное распределение показывает распределение возможных значений параметра p из распределения Бернулли для каждого автомата в зависимости от количества успешных и неудачных попыток. Чтобы получить распределение, нужно подставить:
? = число побед + 1
? = число поражений +1

Схематично алгоритм выглядит так:

1. Изначально все автоматы получают параметры ? = ? = 1 (что соответствует равномерному распределению от 0 до 1)

2. Далее для каждого автомата генерируем случайную величину из его Бета-распределения

3. Выбираем автомат с наибольшей сгенерированной Бета и пробуем его

   • В случае успеха для автомата ? += 1

   • В случае неудачи для автомата ? += 1

4. Возврат к шагу 2

Пример работы семплирования

Посмотрим на алгоритм в действии - разберем на примере с тремя автоматами с вероятностями выиграть (0,3; 0,5; 0,7)

Изначально все автоматы имеют одинаковые равномерные распределения параметра p (вертикальные прерывистые линии показывают истинные значения p)

Выбираем случайный автомат (выпал синий) - крутим - видим проигрыш. Меняем оценки в худшую сторону

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

Спустя еще 8 попыток видим следующую картину:

• Синий больше не проверяли

• Красный сыграл 1 и проиграл 2 раза

• Желтый сыграл 2 и проиграл 3 раза

Красный автомат потихоньку идет в лидеры

Спустя еще 90 попыток

• Синий проиграл еще 3 раза

• Желтый сыграл 1 и проиграл 2 раза

• В основном перешли на красный автомат

Лучший автомат стал явным лидером - из 90 раз 84 выбирали его

Спустя еще 900 попыток

• Красный автомат победил - остальные автоматы к концу алгоритма больше не крутим

• На длинной дистанции синий все же обогнал желтого (хотя нам это и неважно - нужно найти только лучший автомат)

Сравнение алгоритмов

Сравним алгоритмы на симуляциях

• Рандом - выбирает каждый раз случайный автомат

• Два жадных алгоритма с разными ε (0,1 и 0,05)

• Семплирование Томпсона

Видим, что:

• Семплирование Томпсона выигрывает на 6-7% чаще

• В среднем, семплирование Томпсона почти на 8 п.п. чаще выбирает лучший автомат

• После 5% аудитории семплирование Томпсона на 8 п. п. чаще выбирает истинно лучший автомат как лучший

Победа семплирования Томпсона обеспечивается отсутствием выбора случайного автомата в доле случаев ε и более тщательной проверкой всех вариантов

А как, собственно, "расстреливать"? Практика

Вместо игровых автоматов можно использовать ваши фичи, а вместо выигрышей - конверсии. Например, Озон Банк запускал кредитную карту в этом году - и для продвижения использовал виджет на главной странице Банка. Мы приняли разные текстовки на данном виджете (их было 9 штук, привожу 6) за автоматы и использовали семплирование Томпсона, чтобы выбрать 3 лучших.

На выбор трех лучших виджетов ушла 1 неделя. Далее мы проверили эти 3 текстовки против контроля (старой текстовки) в АБ на 4 группы, который тоже шел 1 неделю.

В итоге, за 2 недели мы получили:

• Рост CTR на 15%

• Рост конверсии в клик по виджету на 13%

• Рост конверсии в анкету кредитной карты на 2%

• Ускорение Time-to-Market в 4,5 раза (АБ на 10 групп шел бы 9 недель)

При чем тут ML?

"Контрольным выстрелом" в данном пайплайне является машинное обучение.

Мы решили не отказываться от 3 проигравших текстовок из АБ

Вместо этого обучили на каждой тестовой/контрольной группе модели, которые предсказывают вероятность клика по виджету с той или иной текстовкой (простые catboost-классификаторы). После этого мы запустили еще один АБ-тест:

• Контроль - победившая в прошлом АБ текстовка

• Тест - каждому юзеру показываем текстовку с наибольшим скором

В результате имеем еще больший рост метрик:

• +3% рост конверсии в анкету (суммарный за Thompson + ML)

• +1,6% рост конверсии в скоринг

• +8,3% рост CTR

• +7,1% рост конверсии в клик

Выводы

• Семплирование Томпсона - это КРУТО! Экономит время и помогает проверять больше вариантов

• ML - КРУТО! Позволяет извлечь эффект даже из проигравших в тесте фичей

• НО! АБ тесты нужны - семплирование имеет более сильные предположения и не дает ответа на вопрос о размере аплифта