Многоруких бандитов пост Неделю назад я рассказал, как рассчи | Матчасть

Многоруких бандитов пост

Неделю назад я рассказал, как рассчитывать размер выборки для простого эксперимента: закупаем фиксированное число кликов, потом сравниваем конверсию этой кампании с базовым значением. В комментариях резонно заметили, что на практике так делают редко, ибо клики стоят дорого, а различных комбинаций таргетингов и цен много. И выходит, что на уверенный выбор наилучшей комбинации уйдёт целый годовой бюджет. Поэтому подход "сначала провести эксперименты и выбрать лучший вариант, потом его использовать в остальной рекламе" часто экономически невыгоден.

Альтернатива такая: одновременно и проводить эксперименты, и эксплуатировать предварительные результаты этих экспериментов. Математически эта постановка задачи называется "multi-armed bandit" в честь американских игровых автоматов. Дано: несколько ручек автомата, каждая из которых приносит случайный выигрыш, и для каждой распределение возможных выигрышей может быть своё. Есть фиксированное число попыток, за которые надо заработать максимум денег. Вместо ручек могут быть рекламные объявления, предлагаемые юзеру музыкальным сервисом исполнители, торговые стратегии на бирже, странички в поисковой выдаче, you name it.

Универсального решения (для любого числа ручек и любого распределения выигрышей) эта задача не имеет. Но есть эвристические решения, которые работают неплохо. Например: для каждой из ручек построить 95% доверительный интервал для матожидания её выигрыша, и каждый раз дёргать ту ручку, у которой верхняя граница интервала самая высокая. Напомним, верхнюю границу можно вычислить примерно как mean + 2 * std / sqrt(n), где mean - это средний выигрыш из этой ручки, std - стандартное отклонение выигрышей из неё, n - число попыток с этой ручкой. Чтобы считать стандартные отклонения, каждую ручку сначала надо дёрнуть хотя бы дважды.

Если нам повезло, и мы сразу выбрали самую лучшую ручку, то всё хорошо, и надо продолжать в том же духе. Если же нам попалась плохая ручка, то по мере того, как мы её будем дёргать, выборка выигрышей из этой ручки будет расти, и доверительный интервал для среднего выигрыша - сужаться. А значит, верхняя граница интервала поползёт вниз, и довольно быстро мы выберем другую ручку. У новой ручки либо интервал более широкий (т.е. распределение выигрышей плохо изучено), либо середина интервала расположена достаточно высоко (т.е. средний выигрыш большой). А на интервалы с низким средним выигрышем, которые изучены уже неплохо, ресурсы зря расходоваться не будут. Профит!

Кроме этой стратегии, основанной на доверительных интервалах, есть много других подходов к многоруким бандитам (например, байесовские). Но все эти подходы так или иначе ищут баланс между exploration (исследованием новых опций) и exploitation (извлечением выгоды из уже известных опций).

И, кажется, это очень похоже на то, чем все мы, человеки, занимаемся по жизни.