Хабрахабр

[Из песочницы] Задача о многоруком бандите — сравниваем эпсилон-жадную стратегию и Томпсоновское сэмплирование

Привет, Хабр! Представляю вашему вниманию перевд статьи Solving multiarmed bandits: A comparison of epsilon-greedy and Thompson sampling.

А именно, это задача об оптимальном распределении ресурсов в уcловиях неопределенности. Задача о многоруком бандите – одна из самых основных задач в науке о решениях. Эти автоматы получили прозвище «бандиты», потому что после общения с ними люди обычно чувствовали себя ограбленными. Само название «многорукий бандит» пошло от старых игровых автоматов, которыми управляли при помощи ручек. Раз уж мы взялись играть с этими машинами, мы хотим определить, у какой этот шанс выше и использовать (exploit) эту машину чаще, чем другие. А теперь представьте, что таких машин несколько и шанс выиграть у разных машин разный.

Это не какая-то теоретическая проблема, это проблема, с которой бизнес сталкивается все время. Проблема в следующем: как нам эффективнее всего понять, какая машина подходит лучше всего, и при этом перепробовать много возможностей в реальном времени? Например, у компании есть несколько вариантов сообщений, которые надо показывать пользователям (в число сообщений, например, входят и реклама, сайты, изображения) так, чтобы выбранные сообщения максимизировали некое бизнес-задание (конверсию, кликабельность и пр.)

Т.е сколько-то недель показывать каждый из вариантов одинаково часто, а потом, исходя из статистических тестов, решить, какой вариант лучше. Типичный способ решить эту задачу – много раз запускать A/B тесты. Но когда вариантов много, такой подход становится неэффективным – и по упущенному времени, и по упущенной выгоде. Такой способ подойдет, когда вариантов немного, скажем, 2 или 4.

Больше вариантов – надо больше A/B тестов – надо больше времени на принятие решения. Откуда появляется упущенное время, должно быть легко понятно. Упущенная выгода (opportunity cost) – издержки, связанные с тем, что вместо одного действия мы совершили другое, то есть, говоря упрощенно, это то, что мы потеряли, вложившись в A вместо B. Возникновение упущенной выгоды не так очевидно. То же и с проверкой вариантов. Вложение в B – и есть упущенная выгода от вложения в A. Это значит, что экспериментатор не знает, какой вариант лучше, пока тестирование не закончилось. A/B тесты не должны прерываться, пока они не закончились. Это значит, что, продлевая A/B тесты, мы показываем не самые лучшие варианты достаточно большому числу посетителей (хоть и не знаем, какие именно варианты не самые лучшие), упуская тем самым свою прибыль. Однако, все же предполагается, что один вариант будет лучше, чем другие. Если A/B тест только один, то, возможно, упущенная выгода совсем не велика. Это и есть упущенная выгода от A/B тестирования. Было бы лучше, если бы можно было быстро в реальном времени откинуть плохие варианты, а уже потом, когда вариантов останется мало, использовать для них A/B тесты. Большое число А/В тестов означает, что мы должны длительное время показывать клиентам множество не самых лучших вариантов.

В этой статье я познакомлю вас с Топмсоновским сэмплированием (Thompson sampling) и его свойствами. Сэмплеры или агенты – это способы быстро тестировать и оптимизировать распределение вариантов. Все будет реализовано на Python с чистого листа – весь код можно найти здесь. Я также сравню томпсоновское сэмплирование с эпсилон-жадным алгоритмом — другим популярным вариантом для задачи о многоруком бандите.

Краткий словарь понятий

  • Агент, сэпмлер, бандит (agent,sampler, bandit) – алгоритм, который делает решения касательно того, какой вариант показывать.
  • Вариант (variant) – разный вариант сообщения, которое видит посетитель.
  • Действие (action) – действие, которое выбрал алгоритм (какой вариант показывать).
  • Использовать (exploit) – делать выбор с целью максимизировать суммарную награду исходя из имеющихся данных.
  • Исследовать, пробовать (explore) – делать выбор с целью лучше понять окупаемость для каждого варианта.
  • Награда, очки (score,reward) – бизнес-задание, например, конверсия или кликабельность. Для простоты считаем, что она распределена биномиально и равна либо 1, либо 0 — кликнули или нет.
  • Окружающая среда – контекст, в котором агент работает – варианты и их скрытая для пользователя “окупаемость”.
  • Окупаемость, вероятность успеха (payout rate) – скрытая переменная, равная вероятности получить score=1, для каждого варианта она своя. Но пользовтаель ее не видит.
  • Попытка (trial) – пользователь заходит на страницу.
  • Сожаление (regret) – это разница между тем, какой был бы самый лучший результат из всех доступных вариантов и какой был результат из варианта, доступного на текущей попытке. Чем меньше сожаление по отношению к уже сделанным действиям, тем лучше.
  • Сообщение (message) – баннер, вариант страницы и прочее, разные варианты которого мы хотим попробовать.

Исследовать и использовать (Explore and exploit)

Этот баланс очень важен. Агенты – алгоритмы, которые ищут подход к выбору решений в реальном времени, чтобы достичь баланс между исследованием пространства вариантов и использованием самого оптимального варианта. Если мы сначала обнаружили этот самый оптимальный вариант, а потом все время его используем – мы максимизируем суммарную награду, которая нам доступна из окружающей среды. Пространство вариантов надо исследовать, чтобы иметь понятие о том, какой вариант самый лучший. Иными словами, мы хотим застраховаться против возможных убытков, пробуя немного экспериментировать с субоптимальными вариантами, чтобы уточнить для себя их окупаемость. С другой стороны, мы также хотим исследовать другие возможные варианты – вдруг они в будущем окажутся лучше, а мы просто этого пока не знаем? Другой плюс от исследования вариантов в том, что мы можем лучше понять не только среднюю окупаемость, но и то, как примерно окупаемость распределяется, т.е мы можем лучше оценить неопределенность.
Главная проблема, следовательно, это решить – как лучше всего выйти из дилеммы между исследованием и использованием (exploration-exploitation tradeoff). Если их окупаемость на самом деле более высокая, их можно показывать чаще.

Эпсилон-жадный алгоритм (epsilon-greedy algorithm)

«Жадный» означает именно то, о чем вы подумали. Типичный способ выйти из этой дилеммы– эпсилон-жадный алгоритм. Например, если e=0. После некого начального периода, когда мы случайно делаем попытки – скажем, 1000 раз, алгоритм жадно выбирает самый лучший вариант k в e процентах попыток. На самом деле, это довольно эффективный алгоритм, однако он может недостаточно исследовать пространство вариантов, и следовательно, недостаточно хорошо оценить, какой вариант самый лучший, застрять на субоптимальном варианте. 05, алгоритм 95% времени выбирает лучший вариант, а в оставшиеся 5% времени выбирает случайные попытки. Давайте покажем в коде, как этот алгоритм работает.

Мы должны определить окружающую среду Environment. Но сначала некоторые зависимости. В данном случае, контекст очень простой. Это контекст, в котором алгоритмы будут запускаться. Он вызывает агента, чтобы агент решил, какое выбрать действие, дальше контекст запускает это действие и возвращает полученные за него очки обратно агенту (который как-то обновляет свое состояние).

class Environment: def __init__(self, variants, payouts, n_trials, variance=False): self.variants = variants if variance: self.payouts = np.clip(payouts + np.random.normal(0, 0.04, size=len(variants)), 0, .2) else: self.payouts = payouts #self.payouts[5] = self.payouts[5] if i < n_trials/2 else 0.1 self.n_trials = n_trials self.total_reward = 0 self.n_k = len(variants) self.shape = (self.n_k, n_trials) def run(self, agent): """Run the simulation with the agent. agent must be a class with choose_k and update methods.""" for i in range(self.n_trials): # agent makes a choice x_chosen = agent.choose_k() # Environment returns reward reward = np.random.binomial(1, p=self.payouts[x_chosen]) # agent learns of reward agent.reward = reward # agent updates parameters based on the data agent.update() self.total_reward += reward agent.collect_data() return self.total_reward

Очки распределены биномиально с вероятностью p, зависящей от номера действия (точно также они могли бы быть распределены и непрерывно, суть бы не поменялась). Также я определю класс BaseSampler – он нужен просто чтобы хранить логи и различные атрибуты.

class BaseSampler: def __init__(self, env, n_samples=None, n_learning=None, e=0.05): self.env = env self.shape = (env.n_k, n_samples) self.variants = env.variants self.n_trials = env.n_trials self.payouts = env.payouts self.ad_i = np.zeros(env.n_trials) self.r_i = np.zeros(env.n_trials) self.thetas = np.zeros(self.n_trials) self.regret_i = np.zeros(env.n_trials) self.thetaregret = np.zeros(self.n_trials) self.a = np.ones(env.n_k) self.b = np.ones(env.n_k) self.theta = np.zeros(env.n_k) self.data = None self.reward = 0 self.total_reward = 0 self.k = 0 self.i = 0 self.n_samples = n_samples self.n_learning = n_learning self.e = e self.ep = np.random.uniform(0, 1, size=env.n_trials) self.exploit = (1 - e) def collect_data(self): self.data = pd.DataFrame(dict(ad=self.ad_i, reward=self.r_i, regret=self.regret_i))

Ниже определим 10 вариантов и окупаемость для каждого. Самый лучший вариант – вариант 9 с окупаемостью 0.11%.

variants = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
payouts = [0.023, 0.03, 0.029, 0.001, 0.05, 0.06, 0.0234, 0.035, 0.01, 0.11]

Чтобы было от чего отталкиваться, также определим класс RandomSampler. Этот класс нужен в качестве baseline модели. Он просто чисто случайно выбирает вариант на каждой попытке и не обновляет свои параметры.

class RandomSampler(BaseSampler): def __init__(self, env): super().__init__(env) def choose_k(self): self.k = np.random.choice(self.variants) return self.k def update(self): # nothing to update #self.thetaregret[self.i] = self.thetaregret[self.i] #self.regret_i[self.i] = np.max(self.thetaregret) - self.theta[self.k] #self.thetas[self.i] = self.theta[self.k] self.thetaregret[self.i] = np.max(self.theta) - self.theta[self.k] self.a[self.k] += self.reward self.b[self.k] += 1 self.theta = self.a/self.b self.ad_i[self.i] = self.k self.r_i[self.i] = self.reward self.i += 1

У всех есть методы choose_k и update. У остальных моделей структура следующая. update обновляет параметры агента – этот метод характеризует, как меняется возможность агента выбрать вариант (у RandomSampler эта возможность никак не меняется). choose_k реализует метод, с использованием которого агент выбирает вариант. Мы запускаем агента в окружающей среде используя следующий паттерн.

en0 = Environment(machines, payouts, n_trials=10000)
rs = RandomSampler(env=en0)
en0.run(agent=rs)

Суть эпсилон-жадного алгоритма такова.

  1. Случайным образом выбрать k для n попыток.
  2. На каждой попытке для каждого варианта оценить выигрыш.
  3. После всех n попыток:
  4. С вероятностью 1-e выбрать k с самым высоким выигрышем;
  5. С вероятностью e выбрать K случайно.

Код эпсилон-жадного алгоритма:

class eGreedy(BaseSampler): def __init__(self, env, n_learning, e): super().__init__(env, n_learning, e) def choose_k(self): # e% of the time take a random draw from machines # random k for n learning trials, then the machine with highest theta self.k = np.random.choice(self.variants) if self.i < self.n_learning else np.argmax(self.theta) # with 1 - e probability take a random sample (explore) otherwise exploit self.k = np.random.choice(self.variants) if self.ep[self.i] > self.exploit else self.k return self.k # every 100 trials update the successes # update the count of successes for the chosen machine def update(self): # update the probability of payout for each machine self.a[self.k] += self.reward self.b[self.k] += 1 self.theta = self.a/self.b #self.total_reward += self.reward #self.regret_i[self.i] = np.max(self.theta) - self.theta[self.k] #self.thetaregret[self.i] = self.thetaregret[self.i] self.thetas[self.i] = self.theta[self.k] self.thetaregret[self.i] = np.max(self.thetas) - self.theta[self.k] self.ad_i[self.i] = self.k self.r_i[self.i] = self.reward self.i += 1

На графике показано, какой выбор алгоритм делал на каждой попытке, если попыток было 10 тысяч. Ниже на графике вы можете видеть результаты чисто рандомного сэмплирования, то есть, другими словами, здесь нет никакой модели. Всего он набрал 418 очков.
Алгоритм только пробует, но не учится.

Запустим алгоритм на 10 тысяч попыток с e=0. Давайте посмотрим, как ведет себя в той же окружающей среде эпсилон-жадный алгоритм. 1). 1 и n_learning=500 (первые 500 попыток агент просто пробует, потом пробует с вероятностью e=0. Оценим алгоритм согласно суммарному числу очков, которое он набирает в окружающей среде.

en1 = Environment(machines, payouts, n_trials) eg = eGreedy(env=en1, n_learning=500, e=0.1) en1.run(agent=eg)

Второй график довольно хорошо объясняет этот алгоритм. Эпсилон-жадный алгоритм набрал 788 очков, почти в 2 раза лучше, чем случайный алгоритм – супер! Однако потом оно начинает сильно эксплуатировать вариант 5 – это довольно сильная опция, но не самая лучшая. Мы видим, что для первых 500 шагов действия распределены примерно равномерно и K выбирается случайным образом. Мы также видим, что 10% времени агент по-прежнему выбирает случайным образом.

С другой стороны, алгоритм не обнаружил самый лучший вариант. Это довольно круто — мы написали всего несколько строчек кода, и вот у нас уже есть довольно мощный алгоритм, который может исследовать пространство вариантов и делать в нем близкие к оптимальному решения. Также, в этот процесс по умолчанию вшита случайность – лучший алгоритм может так и не отыскаться. Да, мы может увеличить число шагов для обучения, но так мы будем тратить еще больше времени на случайный поиск, еще сильнее ухудшая итоговый результат.

Но пока давайте разберемся с Томпсоновским сэмплированием и проверим его в той же окружающей среде. Позже я запущу каждый из алгоритмов много раз, чтобы мы могли сравнить их относительно друг друга.

Томпсоновское сэмплирование (Thompson sampling)

Томпсоновское сэмплирование фундаментально отличается от эпсилон-жадного алгоритма тремя главными пунктами:

  1. Оно не жадное.
  2. Оно делает попытки более замысловатым путем.
  3. Оно байесово.

Главным является пункт 3, пункты 1 и 2 следуют из него.

Суть алгоритма такая:

  1. Задать изначальное Бета-распределение между 0 и 1 для окупаемости каждого варианта.
  2. Просэмплировать варианты из этого распределения, выбрать максимальный параметр Тета.
  3. Выбрать такой вариант k, какой бы ассоциировался с самым большим тета.
  4. Посмотреть, сколько очков набрали, обновить параметры распределения.

Подробнее про бета-распределение можно прочитать тут.
А про его применение в Python — тут.

Код алгоритма:

class ThompsonSampler(BaseSampler): def __init__(self, env): super().__init__(env) def choose_k(self): # sample from posterior (this is the thompson sampling approach) # this leads to more exploration because machines with > uncertainty can then be selected as the machine self.theta = np.random.beta(self.a, self.b) # select machine with highest posterior p of payout self.k = self.variants[np.argmax(self.theta)] #self.k = np.argmax(self.a/(self.a + self.b)) return self.k def update(self): #update dist (a, b) = (a, b) + (r, 1 - r) self.a[self.k] += self.reward self.b[self.k] += 1 - self.reward # i.e. only increment b when it's a swing and a miss. 1 - 0 = 1, 1 - 1 = 0 #self.thetaregret[self.i] = self.thetaregret[self.i] #self.regret_i[self.i] = np.max(self.theta) - self.theta[self.k] self.thetas[self.i] = self.theta[self.k] self.thetaregret[self.i] = np.max(self.thetas) - self.theta[self.k] self.ad_i[self.i] = self.k self.r_i[self.i] = self.reward self.i += 1

Формальная запись алгоритма выглядит так.

Как и другие агенты, ThompsonSampler наследуется от BaseSampler и определяет свои собственные методы choose_k и update. Давайте запрограммируем этот алгоритм. Теперь запустим нашего нового агента.

en2 = Environment(machines, payouts, n_trials) tsa = ThompsonSampler(env=en2) en2.run(agent=tsa)

Супер! Как видно, он набрал больше, чем эпсилон-жадный алгоритм. На нем видны две интересные вещи. Посмотрим на график выбора попыток. Во-вторых, агент использовал и другие варианты, но более хитрым путем – примерно после 1000 попыток агент, кроме главного варианта, в основном использовал самые сильные варианты среди остальных. Во-первых, агент верно обнаружил самый лучший вариант (вариант 9) и использовал его на полную катушку. Иными словами, он выбирал не наобум, а более грамотно.

Все просто – неопределенность в апостериорном распределении ожидаемой выгоды для каждого варианта означает, что каждый вариант выбирается с вероятностью, примерно пропорциональной его форме, определенной параметрам альфа и бета. Почему же это работает? Грубо говоря, имея из распределения инофрмацию о неопределенности, агент решает, когда исследовать окружающую среду и когда использовать информацию. Иными словами, на каждой попытке Томпсоновское сэмплирование запускает вариант согласно постериорной вероятности того, что максимальная выгода именно у него. Но для большинства попыток, чем сильнее его постериорное распределение, тем больше его среднее и тем меньше его стандартное отклонение, а значит, тем больше шансов его выбрать. Например, слабый вариант с высокой постериорной неопределенностью может окупаться больше всего для данной попытки.

Ниже на графике изображены постериорные распределения в 6 разных точках и в 20000 попытках. Другое замечательно свойство Томпсоновского алгоритма: так как он байесово, мы можем по его параметрам оценивать неопределенность в оценке окупаемости для каждого варианта. Вы видите, как распределения постепенно начинают сходиться к варианту с самой лучшей окупаемостью.

1 симуляция – это запуск агента на 10000 попытках. Теперь сравним все 3 агента на 100 симуляциях.

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

Сожаление (regret)

Грубо говоря, чем оно меньше, по отношению к уже сделанным действиям, тем лучше. Другой способ оценить, насколько алгоритм хорошо работает – это оценить сожаление (regret). Еще раз – чем меньше regret, тем лучше. Ниже построен график суммарного сожаления и сожаления за ошибку.

Как видно из графиков, томпсоновское сэмплирование сходится к минимальному сожалению гораздо быстрее, чем эпсилон-жадная стратегия. На верхнем графике мы видим суммарное сожаление, а на нижнем сожаление на попытку. С томпсоновским сэмплированием агент сожалеет меньше, потому что он может лучше обнаруживать самый лучший вариант и лучше пробует самые многообещающие варианты – так что томпсоновское сэмплирование особенно хорошо подходит к более продвинутым случаям использования, таким, как статистические модели или нейросети для выбора k. И сходится оно к более низкому уровню.

Выводы

Если подытожить, мы можем использовать довольно сложные методы сэмплирования, если у нас много вариантов, которые мы хотим протестировать в реальном времени. Это довольно длинный технический пост. Т.е мы можем позволить ему оптимизировать распределение вариантов решений в реальном времени. Одно из очень хороших свойств Томпсоновского сэмплирования в том, что оно балансирует использование и исследование довольно хитрым способом. Это классные алгоритмы, и они должны быть полезнее для бизнеса, чем A/B тесты.

Томпсоновское сэмплирование не означает, что вам не надо делать A/B тесты. Важно! Обычно сначала с его помощью находят лучшие варианты, и потом делают A/B тесты уже над ними.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть