Введение

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

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

В этой части (Часть I) мы обсудим , что такое бандиты и почему их следует использовать для рекомендаций, а также как перевести проблему ранжирования в проблему бандитов. Мы также рассмотрим проблемы науки о данных, которые могут возникнуть при практическом применении бандитов.

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

Что такое многорукие бандиты и зачем их использовать?

Постановка задачи

Многорукие бандиты — это класс алгоритмов исследования и эксплуатации, которые используются для принятия решений в условиях неопределенности. Чтобы помочь концептуально понять, что мы подразумеваем под «алгоритмом исследования-эксплуатации», лучше всего рассмотреть следующую постановку задачи, от которой многорукие бандиты получили свое название.

Постановка задачи начинается в казино. Вы входите, и вам предлагают несколько игровых автоматов на выбор. У каждого из этих игровых автоматов есть рычаг (рычаг), за который вы можете потянуть, и когда вы это сделаете, вы получите некоторую случайную награду (выплату), выбранную из заранее определенных игровых автоматов. распределение вероятности вознаграждения. Обратите внимание, что каждый игровой автомат имеет разное распределение вероятности вознаграждения, и эти распределения неизвестны вам, когда вы впервые начинаете играть.

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

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

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

Определение

Стандартная постановка задачи о многоруком бандите может быть определена более формально следующим образом:

  • Бандиты — это класс алгоритмов исследования и эксплуатации, используемых для принятия решений в условиях неопределенности. Их можно рассматривать как упрощенный алгоритм обучения с подкреплением.
  • Данный набор из k рук (параметров) A = {a₁, a₂, …, aₖ }, цель состоит в том, чтобы определить лучшие руки для игры, чтобы максимизировать кумулятивный выигрыш от игры в эти руки.
  • Когда рука aᵢ разыгрывается в момент времени t, мы наблюдаем вознаграждение rₜ, выбранное из распределения вероятностей вознаграждения этой руки — никаких других вознаграждений за неразыгранные руки не наблюдается. Мы записываем это как наблюдение, представляющее собой пару "рука-вознаграждение" (aᵢᵗ, rᵢᵗ).
  • Мы разрабатываем стратегию оптимального выбора следующей ветви, чтобы узнать больше об истинном ожидаемом вознаграждении для каждой ветви, не показывая слишком часто неоптимальную руку. Стратегия учитывает историю наблюдений за вознаграждением за руки до момента времени t-1 и использует эту историю, чтобы решить, что выбрать в момент времени t.

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

  1. Эпсилон-Жадность
    -    Выберите руку с лучшим эмпирическим вознаграждением с вероятностью 1-ε
    - Выберите руку равномерно случайным образом с вероятностью ε
  2. "Decayed Epsilon-Greedy"
     –    Используйте стратегию Epsilon-Greedy, но пусть ε со временем уменьшается, чтобы уменьшить исследование, когда мы будем более уверены в наших оценках ожидаемого вознаграждения.
  3. Верхняя граница достоверности (UCB1)
     –    Построение доверительных интервалов для ожидаемого вознаграждения каждой руки
     – Выберите группу, верхняя граница доверительного интервала которой является наибольшей.
  4. Выборка Томпсона
     –    Используйте байесовский подход и установите априорные значения для распределения вознаграждения каждой руки
     – С каждой новой оценкой вознаграждения обновляйте апостериорное распределение
     – Выборка из каждого заднюю часть руки и выбрать руку с наибольшей выборкой

В качестве примечания: приложения, которые мы создали в Udemy с использованием нашей системы MAB, в основном использовали стратегию выборки Томпсона.

Использование многоруких бандитов для рекомендаций

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

  • Набор элементов-кандидатов, которые следует рекомендовать, представляет собой набор рук для игры (каждый элемент представляет собой руку).
  • Отображение определенного рекомендуемого элемента пользователю в течение определенного периода времени эквивалентно «игранию этой рукой».
  • Отклики пользователя при показе рекомендуемого элемента, такие как клики, поднятие большого пальца или зачисление (в случае рекомендуемых курсов в Udemy), являются наблюдаемой наградой (т. е. наградой, выбранной из неизвестного распределения вознаграждения за предмет).
  • Цель состоит в том, чтобы как можно быстрее определить предметы с наибольшими выплатами вознаграждения, динамически рекомендуя различные предметы пользователю таким образом, чтобы уравновешивать исследование с эксплуатацией.

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

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

Бандиты помогают преодолеть проблему предвзятости цикла обратной связи с рекомендациями.

Проблема предвзятости цикла обратной связи с рекомендациями возникает из-за того, что элементы, которые уже рекомендованы, имеют больше возможностей для воздействия и, следовательно, положительных отзывов от пользователей. Многие традиционные контролируемые алгоритмы машинного обучения, которые используют эту обратную связь во время обучения, склонны рекомендовать эти элементы дальше, продолжая цикл.Исследование бандитов по своей сути разрывает этот цикл — менее часто исследуемые элементы необходимо тестировать в глаза бандита, поэтому мы менее склонны застревать, показывая одни и те же предметы снова и снова, если они действительно не оптимальны.

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

Как представить проблему ранжирования как проблему бандитов

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

Одним из распространенных применений ранжирования в Udemy является рекомендательная единица ранжирования. Блок рекомендаций — это горизонтальная карусель курсов, принадлежащих к какому-либо типу группы (например, «Потому что вы смотрели», «Рекомендуется вам», «Популярно для ____» и т. д.). Порядок, в котором эти блоки рекомендаций появляются на домашней странице пользователя, вошедшего в систему, может быть очень важным как с точки зрения пользователя, так и с точки зрения бизнеса.

Мы формулируем проблему ранжирования рекомендательных единиц следующим образом:

  1. Каждый тип рекомендательной единицы — это рука-кандидат.
  2. Разыгрывание руки означает показ рекомендательного блока пользователю в заданной позиции в течение фиксированного периода времени (в нашем случае 15 минут). показанная единица. Обратите внимание, что наблюдение начинается только после того, как сделан единичный оттиск.
  3. Вознаграждение — это метрика, которую мы хотим использовать для сравнения эффективности различных подразделений на заданной позиции.
     – Мы используем комбинацию кликов пользователей и зачислений на курсы в подразделении за фиксированный период времени.

Все это кажется достаточно простым. Однако нам еще предстоит уточнить, как обрабатывать отзывы на нескольких позициях рейтинга. В традиционной схеме бандита показана только одна рука. Чтобы воспользоваться преимуществом того, что несколько рук можно тянуть одновременно, нам нужно изменить традиционную настройку бандита. Для этого мы рассмотрим две возможные схемы: структуру для каждой позиции и структуру Slate Bandit.

Структура для каждой позиции

В структуре для каждой позиции мы рассматриваем возможность использования отдельного экземпляра бандита для каждой позиции в рейтинге. Цель каждого бандита — найти оптимальную руку для игры в заданной позиции (например, Bandit₂ считает руку «сыгранной» только в том случае, если единица показана пользователю в позиции 2, и учитывает только вознаграждения, полученные за клики и регистрации в положение 2).

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

Тем не менее, есть некоторые практические проблемы, которые возникают при использовании структуры для каждой позиции:

  • Существуют внутренние взаимозависимости между каждым из экземпляров бандита в каждой позиции. Например, Bandit₂ может захотеть показать блок «Потому что вы просматривали» в определенное время, но если Bandit₁ уже выбрал тот же блок , тогда Bandit₂ должен выбрать что-то другое, чтобы избежать дублирования на стороне пользователя. Вы можете себе представить, что эти взаимозависимости становятся все более и более сложными по мере того, как мы спускаемся вниз по рейтингу и расширяем его на большее количество позиций.
  • Вы должны одновременно поддерживать несколько разных экземпляров бандитов. Это потоковые приложения с зависимостями друг от друга; сбой одного экземпляра бандита может вызвать проблемы для других экземпляров бандита.
  • Отзывы о наградах не могут быть легко разделены между бандитами. Поскольку определение вознаграждения за блок «Потому что вы посмотрели» в глазах Bandit₂ – это клики и регистрации, которые происходят, когда этот блок отображается на позиции 2, клики пользователей и регистрации, которые происходят в блоке «Потому что вы смотрели» в позиции 3, не могут быть переданы Bandit₂. Это увеличивает время обучения бандита и сближения рейтинга (подробнее о сближении мы поговорим позже!).

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

Slate Bandit Framework

В структуре slate bandit мы отказываемся от использования отдельного экземпляра bandit для каждой позиции и вместо этого используем одиночный бандит, который одновременно тестирует несколько рук. В этой настройке мы определяем «разыгрывание руки» как отображение юнита в любой из k верхних позиций. Выбор значения для k важен; обратная связь для рук, показанных в одной из верхних позиций k, обрабатывается одинаково, поэтому щелчок или регистрация в первой позиции ничем не отличается от щелчка или регистрации в позиции kᵗʰ в глазах бандита. Вообще говоря, значение, выбранное для k, является дизайнерским решением и будет варьироваться в зависимости от варианта использования и макета страницы. Для нашего конкретного варианта использования мы выбрали k = 3, потому что домашняя страница вошедшего в систему пользователя обычно показывает три полных единицы в окне, когда экран развернут, поэтому можно привести аргумент, что обратная связь для единиц в этих позициях в целом сопоставима.

Обратите внимание, что в соответствии с этой структурой бандит больше не пытается найти лучшие юниты на каждой позиции в рейтинге, а теперь отвечает на менее конкретный вопрос: «Какие юниты лучше всего показывать вверху страницы?»

Недостатки этой уменьшенной детализации включают следующее:

  • Рейтинг внутри первых k позиций не оптимизирован — бандит рассматривает лучшие руки как неупорядоченный набор, поскольку обратная связь среди первых k неразличима.
  • Рейтинг за пределами верхних k позиций индуцирован, а не изучен напрямую — единица, которая оказывается на позиции k+1, помещается туда, потому что это то, что, по мнению бандита, является следующий лучший юнит, чтобы показать где-то на первых k позициях, если бы мог, а не потому, что бандит считает позицию k+1 оптимальной

Тем не менее, slate bandit framework также имеет множество преимуществ:

  • Простота внедрения и обслуживания — всего один бандит без сложностей, возникающих из-за взаимозависимостей между несколькими бандитами.
  • Больше отзывов о вознаграждении для каждого экземпляра бандита — вознаграждения за все руки, показанные в верхних k позициях, используются бандитом, поэтому мы получаем больше отзывов на пользователя для бандита, чем в структуре для каждой позиции. Это позволяет бандиту учиться и сходиться намного быстрее

Мы внедрили slate bandit framework для нашего приложения ранжирования блоков и наблюдали значительный рост дохода и вовлеченности во время нашего A/B-тестирования по сравнению с нашим существующим алгоритмом ранжирования небандитов. Это говорит о том, что более простая структура Slate Bandit все еще может быть очень эффективной, одновременно снижая сложность.

Проблемы науки о данных

Достижение/оценка конвергенции

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

Определить и измерить конвергенцию можно разными способами. Для нашей системы ранжирования сланцевых бандитов мы разработали метрику, которая анализирует последовательные рейтинги, выдаваемые бандитом, и отслеживает среднюю долю изменений набора рук в верхних k позициях за временное окно. Концептуально эту метрику можно рассматривать как метрику «скорости изменений».

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

Как правило, мы видели, что успешные результаты A/B-тестирования с нашей бандитской системой сильно коррелируют с успешной и быстрой конвергенцией. Выбирая приложение и решая, подходят ли бандиты, имейте в виду все факторы, которые могут повлиять на конвергенцию.

Оценка в автономном режиме

Еще одна проблема, связанная с наукой о данных, которая возникает при работе с бандитскими системами, — это оценка в автономном режиме. Офлайн-оценка полезна для определения того, какую стратегию «исследуй-эксплуатируй» тестировать онлайн в A/B-тестировании, а также для сокращения времени, необходимого для итерации и улучшения.

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

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

Заключение

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