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

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

Классический подход к принятию решений по вариантам с неизвестными результатами производительности - это выполнение нескольких A / B-тестов. Обычно они выполняются путем равномерного распределения процента трафика по каждому из вариантов в течение нескольких недель, а затем выполнения статистических тестов для определения наилучшего варианта. Это прекрасно, когда есть небольшое количество вариантов сообщения (например, 2–4), но может быть совершенно неэффективным с точки зрения как времени, так и альтернативных затрат, когда Здесь очень много.

Аргумент времени понять легко. Просто для большего количества вариантов требуется больше A / B-тестов, которые занимают больше времени, таким образом задерживая «обратную связь» и принятие решений. Аргумент альтернативной стоимости более тонкий. В экономике альтернативные издержки - это издержки, связанные с выполнением одного действия, а не другого. Просто, что я упустил, вложив свои деньги в инвестицию A, а не в инвестицию B? Инвестиции B - это альтернативная стоимость принятия инвестиций A. В мире тестирования вариантов это означает отправку клиента в A, а не в B.

По уважительным причинам A / B-тесты не следует «подглядывать» во время их выполнения. Это означает, что экспериментаторы не будут знать, какой вариант лучше, до тех пор, пока не закончат испытание. Однако обычно предполагается, что один вариант превзойдет другие. Что это означает на самом деле? Это означает, что A / B-тестирование включает в себя сознательную отправку части ваших клиентов неоптимального сообщения (хотя вы не знаете, какое именно!) - возможно, если эти клиенты были отправлены на оптимальный вариант, они могли подписаться на вашу услугу.

Это альтернативная стоимость при A / B-тестировании. Для одного теста это приемлемо. Однако, когда есть много вариантов для тестирования, это означает, что вы потенциально направляете многих клиентов на неоптимальные варианты в течение длительного периода времени. В этом сценарии было бы лучше, если бы мы могли в режиме реального времени быстро исключить неудачные варианты, не направляя на них слишком много трафика; затем после определения ряда эффективных вариантов выполните A / B-тест на этом меньшем подмножестве (обычно это требуется для статистической мощности). Алгоритмы Bandit или сэмплеры - это средство быстрого тестирования и оптимизации распределения вариантов.

В этом посте я расскажу о семплировании Томпсона (TS) и его свойствах. Я также сравню выборку Томпсона с эпсилон-жадным алгоритмом, который является еще одним популярным выбором для задач MAB. Все будет реализовано на Python с нуля - весь код можно найти здесь.

В своем посте я использую следующую лексику:

Пробная версия: клиент, переходящий на веб-страницу.

Сообщение: тестируемое изображение / слова / цвета и т. д.

Вариант: разные варианты сообщения (объявление / изображение / веб-страница и т. д.)

Действие: действие, выполняемое алгоритмом, то есть вариант, который он решает показать.

Вознаграждение: бизнес-цель, например подписка на услугу и переход по ссылке. Для простоты предположим, что вознаграждения распределяются биномиально. То есть награда - либо 1, либо 0 (по клику или нет).

Агент: алгоритм, принимающий решение о том, какой вариант отображать. Я также называю их бандитами и сэмплерами.

Среда: контекст, в котором работает агент, т. е. варианты и их скрытые «выплаты».

Разведка и разработка

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

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

Эпсилон-Жадный

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

Сначала некоторые зависимости и котел. Нам нужно определить среду. Среда - это контекст, в котором будут работать алгоритмы. В данном случае все очень просто. Среда вызывает агента (то есть алгоритм бандита), чтобы «решить», какое действие предпринять, затем он запускает действие, наблюдает за вознаграждением и передает вознаграждение обратно агенту, который обновляет себя. У этого есть много симуляторов для подкрепления обучения, и, действительно, алгоритмы MAB считаются «облегченной» формой RL.

Вознаграждение распределяется биномиально с вероятностью p, определяемой предпринятыми действиями (примечание: это можно легко распространить на непрерывные результаты). Здесь я также определяю класс BaseSampler. На самом деле цель этого класса состоит только в хранении различных атрибутов и журналов (для визуализации), которые являются общими для бандитов. Здесь мы также определяем наши варианты и их скрытые, но неизвестные ставки выплат. Всего протестируем 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. Он просто выбирает случайным образом вариант для каждого испытания, он не узнает и не обновляет. Это чисто для тестирования других агентов.

Остальные агенты следуют этой базовой структуре. Все они реализуют методы choose_k и update. choose_k реализует политику, с помощью которой агент выбирает вариант. update обновляет параметры агента - так агент «развивает» свою способность выбирать вариант (класс RandomSampler ничего не обновляет). Мы запускаем агент в среде, используя этот шаблон:

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

Описание каждого компонента электронного жадного алгоритма встроено, но суть алгоритма такова:

- randomly choose k for n trials
- On each trial estimate the payout rate for each variant
- after n learning trials:
- select 1-e% of the time k with the the highest payout rate and;
- e% of the time sample from the variants randomly

На графике ниже вы можете увидеть результаты чисто случайной выборки. То есть не существует модели, определяющей процесс выбора агента. График показывает выбор, сделанный в каждом испытании из 10 000 испытаний. Это чистое исследование без обучения. Общее вознаграждение, полученное этим агентом, составляет 418.

Давайте посмотрим, как алгоритм e-greedy работает в той же среде. Мы снова запустим алгоритм для 10000 испытаний и установим e = 0,05 и n_learning = 1000. Мы будем оценивать алгоритм по общему вознаграждению, которое он создает в среде.

Общее вознаграждение, созданное e-greedy, составляет 788, это почти 100% улучшение по сравнению с случайной выборкой - приятно! График 2 позволяет лучше понять алгоритм. Мы видим, что для первых 1000 шагов обучения распределение действий относительно равномерно, поскольку k выбирается случайным образом. После этого он начинает активно использовать вариант 5, который является сильным вариантом с выплатой 0,06%, хотя и не лучшим. Мы также можем видеть случайное исследование, которое выполняется во время испытаний, поскольку оно случайным образом выбирается из пула вариантов в 10% случаев.

Это довольно круто, всего в нескольких строках кода у нас есть довольно мощный алгоритм, способный исследовать пространство вариантов и принимать в нем решения, близкие к оптимальным. Однако алгоритм не выявил абсолютно лучшего варианта. Конечно, мы могли бы увеличить количество шагов обучения, но тогда мы тратим больше испытаний на случайный поиск, что еще больше повредит общей награде. Кроме того, этому процессу присуща случайность, поэтому, если бы мы снова запустили алгоритм, возможно, что e-greedy определит и воспользуется лучшим вариантом.

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

Пробоотборник Томпсона

Сэмплер Томпсона существенно отличается от алгоритма e-greedy по трем основным направлениям:

  • он не жадный;
  • его исследование более сложное, и;
  • это байесовский

1 и 2 из-за 3.

Как и в случае с e -greedy, код комментируется внутри строки, но суть алгоритма такова:

- Set a uniform prior distribution between 0 and 1 for each variant k’s payout rate
- Draw a parameter theta from the each k's posterior distribution
- Select the variant k that is associated with the highest parameter theta
- Observe the reward and update the distribution parameters

Более формально для каждого испытания:

Обратите внимание, что здесь я определяю сэмплер Thompson Sampling как бета-сэмплер Бернулли. Однако выборка Томпсона может быть обобщена для выборки из любых произвольных распределений по параметрам. Бета-версия TS Бернулли - это хороший способ развить интуицию для алгоритма и, на самом деле, часто является лучшим вариантом для решения многих проблем на практике. Если вы ищете учебник по бета-дистрибутиву, не ищите ничего, кроме сообщения в блоге Дэвида Робинсона.

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

Теперь запустим сэмплер. Общая награда с образцом Томпсона в качестве агента составляет 1023. Это немного больше, чем просто электронная жадность, круто! Давайте посмотрим на образец графика. Здесь выделяются две вещи. Во-первых, агент правильно определяет лучший вариант (вариант 9) и максимально использует его. Тем не менее, он также исследует другие варианты, но более изощренным образом. Если вы внимательно посмотрите на варианты, которые агент выбирает больше всего (после 1000 испытаний или около того), они, как правило, являются более сильными вариантами. Другими словами, его исследование является скорее управляемым, чем чисто случайным.

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

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

Давайте теперь сравним всех трех агентов в 100 симуляциях. Симуляция - это один запуск 10000 испытаний на бандита. Здесь мы сравниваем их общую награду в каждой симуляции. Как видно из графика, и e- greedy, и Thompson сильно превосходят случайную выборку. Вы можете быть удивлены, что e -greedy и Thompson обычно вполне сопоставимы с точки зрения их общего вознаграждения. E -greedy может быть очень эффективным, но более рискованным, потому что может застрять - как это было в первом случае, я запустил его, когда он набрал всего 788. Мы можем увидеть это в некоторых из низких точек в сюжете. В этих прогонах e -greedy выбрал неоптимальный вариант и использовал его больше всего. Как видите, Томпсон никогда не застревает в этом. Это связано с более сложным исследованием альтернативного пространства.

Сожаление

Дополнительным средством оценки эффективности алгоритмов является концепция сожаления. Интуитивно сожалеть довольно просто. Сожаление алгоритма о своем действии (что k показать) должно быть как можно меньше. Проще говоря, сожаление - это разница между лучшей производительностью варианта на данный момент и производительностью варианта, выбранного для текущего испытания t. Ниже я изображаю совокупное сожаление и сожаление за испытание t. Если это неочевидно, сожаление следует свести к минимуму.

Верхний график показывает совокупное сожаление, а нижний - сожаление за испытание. Из графиков сожаления видно, что Томпсон сходится к наименьшему сожалению гораздо лучше, чем e -greedy (на самом деле мы не ожидаем, что случайная выборка сойдется). Кроме того, верхний график показывает, что совокупное сожаление о е -жадности имеет более крутой наклон, чем Томпсон. Мы также можем видеть, что сожаление сводится к минимуму и лучше сходится с Томпсоном.

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

Резюме

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

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

Еще один способ думать об алгоритмах МАБ - через призму обучения с подкреплением. По сути, они автоматически оптимизируются без предварительного знания своей задачи, получая вознаграждение от среды для обновления своих параметров. В моем следующем посте по этой теме я более подробно исследую этот угол с помощью Contextual Bandits, то есть бандитов, которые позволяют персонализировать варианты на основе другой информации, такой как особенности пользователя, посещающего страница в Интернете.

Спасибо за чтение, надеюсь, вам было интересно.