Bandits for Recommender Systems

eugeneyan

eugeneyan

Начните здесь Статьи Выступления Прототипирование О себе

Bandits for Recommender Systems

Бандиты для рекомендательных систем

[ teardown recsys machinelearning ] · 14 min read

[ teardown recsys machinelearning ] · чтение на 14 мин

Recommender systems work well when we have a lot of data on user-item preferences. With a lot of data, we have high certainty about what users like. Conversely, with very little data, we have low certainty. Despite the low certainty, recommenders tend to greedily promote items that received higher engagement in the past. And because they influence how much exposure an item gets, potentially relevant items that aren’t recommended continue getting no to low engagement, perpetuating the feedback loop.

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

Bandits address this by modeling uncertainty and exploration. By acknowledging the uncertainty in the data and deliberately exploring to reduce it, bandits learn about the relevance of unexplored items.

Бандиты решают эту проблему, моделируя неопределённость и исследование. Признавая неопределённость в данных и целенаправленно исследуя, чтобы её снизить, бандиты узнают о релевантности неисследованных объектов.

This is especially applicable when the item set changes quickly, such as for news, ads, and tweets, or when the rate of traffic is low. If new items are constantly added, waiting to collect batch data before retraining the model can be too slow. Bandits are a good fit as they can incrementally update with new data and adaptively focus on items with higher reward. This reduces regret, which is the opportunity cost while recommending suboptimal items.

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

ε-greedy, UCB, and Thompson Sampling

ε-greedy, UCB и Thompson Sampling

We’ll briefly discuss three main bandit algorithms before looking at some industrial implementations of each. Here are a few terms I use throughout: (i) action/arm: recommendation candidates, (ii) reward: customer interaction from a single trial, such as a click or purchase, (iii) value: estimated long-term reward of an arm over multiple trials, and (iv) policy: algorithm/agent that chooses actions based on learned values.

Мы кратко обсудим три основных алгоритма бандитов, прежде чем рассмотреть промышленные реализации каждого из них. Вот несколько терминов, которые я использую на протяжении статьи: (i) действие/рука (action/arm): кандидаты на рекомендацию, (ii) награда (reward): взаимодействие клиента в рамках одной попытки, например клик или покупка, (iii) ценность (value): оценочная долгосрочная награда руки за множество попыток, и (iv) политика (policy): алгоритм/агент, выбирающий действия на основе изученных ценностей.

ε-greedy is the classic bandit algorithm. At every trial, it randomly chooses an action with probability ε and greedily chooses the highest value action with probability 1 - ε. We balance the explore-exploit trade-off via the parameter ε. A higher ε leads to more exploration while a lower ε leads to more exploitation. However, ε-greedy can explore longer than necessary (though this can be mediated by decreasing ε over time). Another downside is that ε-greedy doesn’t provide guidance on which items to explore and defaults to exploring all items uniformly at random.

ε-greedy — это классический алгоритм бандита. На каждой попытке он с вероятностью ε случайно выбирает действие и с вероятностью 1 - ε жадно выбирает действие с наибольшей ценностью. Мы балансируем компромисс между исследованием и эксплуатацией через параметр ε. Более высокое ε ведёт к большему исследованию, а более низкое ε — к большей эксплуатации. Однако ε-greedy может исследовать дольше, чем необходимо (хотя это можно смягчить, уменьшая ε со временем). Другой недостаток в том, что ε-greedy не подсказывает, какие объекты исследовать, и по умолчанию исследует все объекты равномерно случайно.

Upper Confidence Bound (UCB) considers the uncertainty of an arm and selects arms that have the highest potential. Uncertainty is modeled via confidence bounds while potential is represented by the upper confidence bound (thus the name of the algorithm). Because of how it works, UCB is often referred to as “optimism in the face of uncertainty”.

Upper Confidence Bound (UCB) учитывает неопределённость руки и выбирает руки с наибольшим потенциалом. Неопределённость моделируется через доверительные границы, а потенциал представлен верхней доверительной границей (отсюда и название алгоритма). Из-за принципа своей работы UCB часто называют «оптимизмом перед лицом неопределённости».

Example of UCB with a frequently tried arm (green) and a rarely tried arm (red)

Пример UCB с часто пробуемой рукой (зелёная) и редко пробуемой рукой (красная)

In the image above, Qₜ(a) is the estimated value of arm a at time step t, Nₜ(a) is the number of times arm a was selected, and c is a confidence parameter (which defaults to 1). The green arm has been chosen frequently and thus has narrower confidence bounds. In contrast, the red arm hasn’t been selected as often and thus has wider confidence bounds. When selecting an action, even though the green arm has a higher estimated value, the red arm has a higher UCB and is thus chosen. As the red arm is selected more, its confidence bounds will shrink. If the estimated value stays the same, its UCB will decrease to below the UCB of the green arm and the green arm will be chosen.

На изображении выше Qₜ(a) — это оценочная ценность руки a на шаге времени t, Nₜ(a) — число раз, когда рука a была выбрана, а c — параметр уверенности (по умолчанию равен 1). Зелёная рука выбиралась часто и потому имеет более узкие доверительные границы. Напротив, красная рука выбиралась не так часто и потому имеет более широкие доверительные границы. При выборе действия, хотя зелёная рука имеет более высокую оценочную ценность, у красной руки выше UCB, и потому выбирается именно она. По мере того как красная рука выбирается чаще, её доверительные границы сужаются. Если оценочная ценность останется прежней, её UCB снизится ниже UCB зелёной руки, и будет выбрана зелёная рука.

Thomson Sampling models uncertainty by building a probability distribution from historical rewards and then samples from the distribution when choosing actions. In the simple case where rewards are binary, a Beta distribution is used. The Beta distribution takes two parameters, α and β, and the mean value of the distribution is α/α + β which can be thought of as successes / successes + failures. To select an action, we sample from each arm’s Beta distribution and choose the arm with the highest sampled values.

Thompson Sampling моделирует неопределённость, строя распределение вероятностей по историческим наградам, а затем сэмплирует из этого распределения при выборе действий. В простом случае, когда награды бинарны, используется бета-распределение. Бета-распределение принимает два параметра, α и β, и среднее значение распределения равно α/α + β, что можно представить как успехи / успехи + неудачи. Чтобы выбрать действие, мы сэмплируем из бета-распределения каждой руки и выбираем руку с наибольшими сэмплированными значениями.

Beta distributions that get narrower as α and β increase

Бета-распределения, которые сужаются по мере роста α и β

As we collect more data, α and β increase. As a result, the Beta distribution becomes narrower and we gain more certainty in our estimate of the arm’s value. The Beta distributions above all have the same mean of 0.5 though those with larger α and β are narrower. With a narrower distribution, our sampled values will be closer to the mean, thus reducing exploration and increasing exploitation.

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

Industry examples of bandits for recsys

Отраслевые примеры бандитов для recsys

An example of ε-greedy is Spotify’s recplanations (recommending explanations for music recommendations). They adopted ε-greedy for its simplicity of implementation in production and propensity scoring. To limit the negative impact of exploration on user experience, they pre-select 100 most relevant items to explore. These 100 items were selected via a separate embedding-based model that captured user preferences similar to the candidate selection stage of the YouTube paper.

Пример ε-greedy — это recplanations у Spotify (рекомендация объяснений к музыкальным рекомендациям). Они выбрали ε-greedy за простоту реализации в продакшене и propensity scoring. Чтобы ограничить негативное влияние исследования на пользовательский опыт, они заранее отбирают 100 наиболее релевантных объектов для исследования. Эти 100 объектов отбираются отдельной моделью на основе эмбеддингов, которая улавливает предпочтения пользователя, аналогично этапу отбора кандидатов из статьи YouTube.

Another example is Schibsted’s multi-armed bandit ranker which reranks candidate items from multiple sub-recommenders. For every input that is reranked, 5% random items are added to avoid local minima during training.

Другой пример — ранжировщик на многоруких бандитах от Schibsted, который переранжирует объекты-кандидаты от нескольких субрекомендателей. К каждому переранжируемому входу добавляется 5% случайных объектов, чтобы избежать локальных минимумов во время обучения.

The classic example of UCB is Yahoo’s LinUCB for news recommendations. Ridge regression is trained to estimate reward linear on an arm’s features. The UCB is then derived by summing the predicted reward and the standard deviation of the ridge regression. A hybrid version of LinUCB also uses features that are shared by all arms (e.g., news category) and experiments showed that shared features allowed CTR information to be learned and exploited across multiple news articles.

Классический пример UCB — это LinUCB от Yahoo для рекомендации новостей. Гребневая регрессия (ridge regression) обучается оценивать награду линейно по признакам руки. Затем UCB выводится сложением предсказанной награды и стандартного отклонения гребневой регрессии. Гибридная версия LinUCB также использует признаки, общие для всех рук (например, категорию новости), и эксперименты показали, что общие признаки позволяли извлекать и эксплуатировать информацию о CTR сразу по нескольким новостным статьям.

Another example is Alibaba’s LinUCB for item recommendations where they adopted the user browsing model to add positional weights. The goal was to address position bias which has a strong influence on user engagement, especially on mobile surfaces. The positional weights modeled examination probability and the rewards for each arm are updated to consider both the arm’s features and examination probability. Similarly, ridge regression is applied and the standard deviation is used to compute the UCB.

Другой пример — LinUCB от Alibaba для рекомендации объектов, где они применили модель просмотра пользователем, чтобы добавить позиционные веса. Цель состояла в устранении позиционного смещения (position bias), которое сильно влияет на вовлечённость пользователя, особенно на мобильных поверхностях. Позиционные веса моделировали вероятность рассмотрения, и награды для каждой руки обновляются с учётом как признаков руки, так и вероятности рассмотрения. Аналогично применяется гребневая регрессия, а стандартное отклонение используется для вычисления UCB.

An example of Thompson Sampling is Doordash’s bandits for cuisine recommendations. User preferences for a cuisine is modeled via Beta(α=number of orders of the cuisine, β=number of orders of other cuisines). When selecting a set of cuisine filters to show on the explore page, the value for each cuisine is sampled from the cuisine’s Beta distribution. These values are then sorted in descending order to select the top cuisines to display.

Пример Thompson Sampling — это бандиты от Doordash для рекомендации кухонь. Предпочтения пользователя к кухне моделируются через Beta(α=число заказов этой кухни, β=число заказов других кухонь). При выборе набора фильтров кухонь для показа на странице исследования значение для каждой кухни сэмплируется из её бета-распределения. Затем эти значения сортируются по убыванию, чтобы отобрать топовые кухни для показа.

Another example is Yahoo’s Thompson Sampling bandit for recommending ads and news. To predict the reward (i.e., CTR) of an ad or news article, they learned a regularized logistic regression model. Then, to model uncertainty, the posterior distribution of the model’s weights are represented by Gaussian distributions. For every trial, each weight is drawn independently from its Gaussian posterior distribution before being used to predict the reward of an action.

Другой пример — бандит на Thompson Sampling от Yahoo для рекомендации рекламы и новостей. Чтобы предсказать награду (то есть CTR) рекламы или новостной статьи, они обучили регуляризованную модель логистической регрессии. Затем, чтобы смоделировать неопределённость, апостериорное распределение весов модели представляется гауссовыми распределениями. На каждой попытке каждый вес независимо извлекается из своего гауссова апостериорного распределения перед тем, как использоваться для предсказания награды действия.

A similar example is Amazon’s multivariate bandits to optimize page layouts. Model weights are also represented and sampled from independent Gaussian distributions. However, because the decision space is so large due to the many layout combinations, they approximate argmax via greedy hill-climbing instead of an exhaustive search. Random restarts are included to alleviate suboptimal solutions.

Похожий пример — многомерные бандиты от Amazon для оптимизации макетов страниц. Веса модели также представлены и сэмплируются из независимых гауссовых распределений. Однако, поскольку пространство решений очень велико из-за множества комбинаций макетов, они аппроксимируют argmax через жадное восхождение к вершине (greedy hill-climbing) вместо исчерпывающего перебора. Включены случайные перезапуски, чтобы смягчить проблему субоптимальных решений.

Uncertainty can also be modeled via deep learning techniques. Twitter’s deep learning bandit for ad recommendations considered two approaches: bootstrapping and dropout.

Неопределённость можно также моделировать методами глубокого обучения. Бандит на глубоком обучении от Twitter для рекомендации рекламы рассматривал два подхода: бутстрэппинг и дропаут.

Bootstrapping models uncertainty by training multiple identical networks on different subsets of the data. However, this is costly as it requires partitioning and storing masks of the data, training multiple networks, and multiple forward passes across all networks. To reduce the computation cost, they used a multi-headed network that shares the same bottom layers and had each data subset pass through a different head during training.

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

Dropout models uncertainty by having the network predict an action’s value via multiple forward passes with different dropout units. This is akin to sampling from the posterior distribution. The dropout layer acts as the heads of the multi-headed network.

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

Twitter's bayesian bandit which models uncertainty via a perultimate dropout layer

Байесовский бандит от Twitter, который моделирует неопределённость через предпоследний слой дропаута

Their eventual architecture used a dropout layer as the penultimate layer (right side of image above). When sampling from the posterior, they only needed to compute the bottom layers once before multiple passes through the dropout layer are done in parallel. The dropout layer provides a mask for each data point without having to explicitly partition the data set and also acts as the heads in a multi-headed network.

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

Lessons on applying bandits in industry

Уроки применения бандитов в индустрии

First, UCB and Thompson Sampling outperform ε-greedy. By default, ε-greedy is unguided and chooses actions uniformly at random. In contrast, UCB and Thompson Sampling are guided by confidence bounds and probability distributions that shrink as the action is tried more often. As a result, because UCB and Thompson Sampling smartly explore arms that have higher uncertainty, they have lower regret.

Во-первых, UCB и Thompson Sampling превосходят ε-greedy. По умолчанию ε-greedy не направлен и выбирает действия равномерно случайно. Напротив, UCB и Thompson Sampling направляются доверительными границами и распределениями вероятностей, которые сужаются по мере того, как действие пробуется чаще. В результате, поскольку UCB и Thompson Sampling разумно исследуют руки с большей неопределённостью, у них ниже сожаление (regret).

Second, when feedback is delayed, Thompson Sampling outperforms UCB. Delayed feedback, where user-item interactions are not processed immediately, is common for most real-world systems due to resource and run-time constraints. In this situation, because UCB selects arms deterministically, it chooses the same action until new feedback is incorporated. In contrast, because Thompson Sampling chooses actions stochastically by sampling from the posterior distribution, it randomizes over actions even without updated rewards. Yahoo’s evaluation of Thompson Sampling and Deezer’s music bandit observed that this led to wider exploration and thus better outcomes.

Во-вторых, при отложенной обратной связи Thompson Sampling превосходит UCB. Отложенная обратная связь, когда взаимодействия пользователя с объектами обрабатываются не сразу, характерна для большинства реальных систем из-за ограничений по ресурсам и времени выполнения. В этой ситуации, поскольку UCB выбирает руки детерминированно, он выбирает одно и то же действие, пока не будет учтена новая обратная связь. Напротив, поскольку Thompson Sampling выбирает действия стохастически, сэмплируя из апостериорного распределения, он рандомизирует выбор действий даже без обновлённых наград. Оценка Thompson Sampling от Yahoo и музыкальный бандит Deezer отметили, что это приводило к более широкому исследованию и, как следствие, к лучшим результатам.

To further study the impact of delayed rewards, Yahoo simulated different update delays of 10, 30, and 60 minutes. Thompson Sampling was competitive over all delays. On the other hand, while UCB outperformed Thompson Sampling when the delay was short (10 minutes), it performed worse than Thompson Sampling when the delay increased to 30 and 60 minutes. Overall, this suggests that stochastic policies are more robust to delay as they continue to explore even without updated rewards.

Чтобы дополнительно изучить влияние отложенных наград, Yahoo смоделировали разные задержки обновления — 10, 30 и 60 минут. Thompson Sampling был конкурентоспособен при всех задержках. С другой стороны, хотя UCB превосходил Thompson Sampling при короткой задержке (10 минут), он показывал себя хуже Thompson Sampling, когда задержка возрастала до 30 и 60 минут. В целом это говорит о том, что стохастические политики более устойчивы к задержке, поскольку продолжают исследование даже без обновлённых наград.

Third, how the bandit is initialized makes a difference. Deezer found that pessimistic initialization performed better than naive initialization. For Thompson Sampling, they experimented with naive initialization where the prior was Beta(1, 1) and pessimistic initialization where the prior was Beta(1, 99). Similar naive and pessimistic initialization was adopted for UCB. They found that pessimistic initialization performed better due to the lower prior probabilities which were more reflective of real-world reward.

В-третьих, способ инициализации бандита имеет значение. Deezer обнаружили, что пессимистичная инициализация работает лучше наивной. Для Thompson Sampling они экспериментировали с наивной инициализацией, где априорным распределением было Beta(1, 1), и пессимистичной инициализацией, где априорным распределением было Beta(1, 99). Аналогичная наивная и пессимистичная инициализация была применена для UCB. Они обнаружили, что пессимистичная инициализация работает лучше из-за более низких априорных вероятностей, которые точнее отражали реальную награду.

Exploring new items - two options

Исследование новых объектов — два варианта

The few papers that discussed exploration adopted two main approaches: (i) large exploration on a limited set of users vs. (ii) small exploration on all users.

Те немногие статьи, что обсуждали исследование, применяли два основных подхода: (i) обширное исследование на ограниченном наборе пользователей против (ii) небольшого исследования на всех пользователях.

For the former, Yahoo uses an exploration bucket that users are randomly selected into. Users in the exploration bucket are then served news articles uniformly at random. Similarly, Twitter has a random ad policy that serves 1% of production traffic.

Для первого Yahoo использует бакет исследования, в который пользователи отбираются случайным образом. Пользователям в бакете исследования затем показываются новостные статьи равномерно случайно. Аналогично, у Twitter есть политика случайной рекламы, обслуживающая 1% продакшен-трафика.

For the latter, Netflix tests new artwork on all users (“… the regret incurred by exploration is typically very small and is amortized across our large member base with each member implicitly helping provide feedback on artwork for a small portion of the catalog.”) Similarly, Schibsted adds 5% random items to every input of their bandit ranker.

Для второго Netflix тестирует новые обложки на всех пользователях («… сожаление от исследования обычно очень мало и амортизируется по всей нашей огромной базе участников, при этом каждый участник неявно помогает давать обратную связь по обложкам для небольшой части каталога»). Аналогично, Schibsted добавляет 5% случайных объектов к каждому входу своего ранжировщика на бандитах.

Addressing the curse of dimensionality

Борьба с проклятием размерности

We can represent users via features such as gender, age group, location, behavior, etc. However, one concern with applying bandits conditioned on these features is the curse of dimensionality. More dimensions leads to less data for each combination of dimensions.

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

Yahoo addressed this by applying PCA for dimensionality reduction before learning a policy via LinUCB. They started with 1.2k user features (e.g., demographics, geolocation, and behavior). They also had 83 article features based on URL categories and editor categories. For feature reduction, they projected user features onto article features and then clustered users into five groups where users in each group had similar preferences. This reduced the 1.2k user features into five features. Article features were also reduced in a similar manner.

Yahoo решили это, применив PCA для снижения размерности перед обучением политики через LinUCB. Они начали с 1,2 тыс. пользовательских признаков (например, демография, геолокация и поведение). У них также было 83 признака статей на основе категорий URL и редакторских категорий. Для сокращения признаков они спроецировали пользовательские признаки на признаки статей, а затем кластеризовали пользователей на пять групп, где пользователи в каждой группе имели схожие предпочтения. Это сократило 1,2 тыс. пользовательских признаков до пяти признаков. Признаки статей были сокращены аналогичным образом.

Deezer compared between representing users as clusters (semi-personalization) vs. user features (full personalization). For semi-personalization, users were clustered into 100 groups via k-means clustering on past behavior. This resulted in clusters of users with similar musical tastes. They then trained a separate bandit for each cluster. For full personalization, users were represented via a 97-dimension vector which summarizes user preferences for genres, moods, countries, etc. The vector was obtained by factorizing the user-song interaction matrix. They then trained a contextual bandit on these user features.

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

The semi-personalized approach outperformed the fully personalized alternative. Because the semi-personalized bandits were trained on user clusters, each bandit received more feedback and was thus able to learn more effectively and rank playlists faster.

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

Warm-starting bandits for better user experience

«Тёплый старт» бандитов для лучшего пользовательского опыта

To ensure our bandits provide a good user experience from the very first interaction, it’s typical to learn from previously logged user interactions to warm-start the bandit.

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

Doordash shared how they warm-start their cuisine bandits via higher-level regional data. For each cuisine, they learn a bandit policy at multiple levels (i.e., regional, subregional, user). The top-level bandit is initialized at Beta(α=1, β=1). Then, for each lower-level bandit, they update α by adding the average number of orders for the cuisine (at that level) and update β by adding the average number of orders for other cuisines (at that level). Finally, for the user-level bandit, α and β are updated with the user’s order data. As a result, a new user’s cuisine bandit is warm-started with higher-level marketplace data before each new order updates the bandit with their personal preferences.

Doordash рассказали, как они выполняют тёплый старт своих бандитов по кухням через данные более высокого регионального уровня. Для каждой кухни они изучают политику бандита на нескольких уровнях (то есть региональном, субрегиональном, пользовательском). Бандит верхнего уровня инициализируется как Beta(α=1, β=1). Затем для каждого бандита более низкого уровня они обновляют α, прибавляя среднее число заказов этой кухни (на данном уровне), и обновляют β, прибавляя среднее число заказов других кухонь (на данном уровне). Наконец, для бандита пользовательского уровня α и β обновляются данными о заказах самого пользователя. В результате бандит по кухням для нового пользователя получает тёплый старт на данных маркетплейса более высокого уровня, прежде чем каждый новый заказ обновит бандита его персональными предпочтениями.

Another approach is to warm-start user preferences using data collected via a random policy. Yahoo learned user-specific CTR estimates (on random data) which were then added to context-free CTR estimates for news recommendations. They found that bandits warm-started with user preferences data were able to beat the context-free bandits.

Другой подход — выполнить тёплый старт пользовательских предпочтений на данных, собранных через случайную политику. Yahoo изучили CTR-оценки, специфичные для пользователя (на случайных данных), которые затем добавлялись к контекстно-независимым CTR-оценкам для рекомендации новостей. Они обнаружили, что бандиты с тёплым стартом на данных о предпочтениях пользователей смогли обойти контекстно-независимых бандитов.

As an alternative to random data, this paper showed how to warm-start bandits on data logged via the production policy by importance weighting it. The production policy (i.e., probability of each action) is required to importance weight logged events. To derive the production policy, they used empirical estimation. Specifically, for each ad and page pair, they computed the number of times an ad appeared on each page. This estimate is then used to importance weight logged events that the bandit learns on.

В качестве альтернативы случайным данным эта статья показала, как выполнить тёплый старт бандитов на данных, залогированных через продакшен-политику, путём их перевзвешивания по важности (importance weighting). Продакшен-политика (то есть вероятность каждого действия) необходима для перевзвешивания залогированных событий по важности. Чтобы вывести продакшен-политику, они использовали эмпирическую оценку. В частности, для каждой пары реклама-страница они подсчитывали, сколько раз реклама появлялась на каждой странице. Эта оценка затем используется для перевзвешивания по важности залогированных событий, на которых обучается бандит.

Data collected via a greedy policy can also be helpful for warm-start. Twitter warm-started their bandit on data collected by a greedy policy and found that warm-starting for more epochs (500 vs. 100) led to improved metrics on the test set.

Данные, собранные через жадную политику, также могут быть полезны для тёплого старта. Twitter выполнил тёплый старт своего бандита на данных, собранных жадной политикой, и обнаружил, что тёплый старт на большем числе эпох (500 против 100) приводил к улучшению метрик на тестовом наборе.

Evaluating bandits via off-policy evaluation

Оценка бандитов через off-policy evaluation

Several bandit implementations (e.g., Netflix, Yahoo) cite the replay method by Li et al. for off-policy evaluation. Replay assumes that (i) individual events are independently and identically distributed and (ii) the logging policy chose each arm uniformly at random. The paper then states that the latter assumption can be weakened so any randomized policy—not just uniform random—can be used. (My understanding is that randomness is required for sufficient support and thus uniform randomness isn’t strictly necessary.)

Несколько реализаций бандитов (например, Netflix, Yahoo) ссылаются на метод replay от Li et al. для оценки вне политики (off-policy evaluation). Replay предполагает, что (i) отдельные события независимы и одинаково распределены и (ii) логирующая политика выбирала каждую руку равномерно случайно. Далее в статье говорится, что второе предположение можно ослабить, так что может использоваться любая рандомизированная политика — не только равномерно случайная. (Насколько я понимаю, случайность необходима для достаточного покрытия (support), и потому равномерная случайность строго не обязательна.)

During evaluation, replay takes in the new policy (to be evaluated) and the logged policy events. If the new policy chooses the same action as the logged policy, the event is added to the history and the reward is updated. If not, the event is ignored with no reward update. (Counterfactual evaluation via Inverse Propensity Scoring is another alternative.)

Во время оценки replay принимает на вход новую политику (которую нужно оценить) и события залогированной политики. Если новая политика выбирает то же действие, что и залогированная политика, событие добавляется в историю и награда обновляется. Если нет, событие игнорируется без обновления награды. (Контрфактическая оценка через Inverse Propensity Scoring — ещё одна альтернатива.)

How does bandit off-policy evaluation compare to typical supervised machine learning evaluation on logged data? Twitter’s paper provides some insight. They computed two sets of metrics: (i) PR-AUC on a standard test set and (ii) CTR improvements vs. a random policy. There was a trade-off between PR-AUC and CTR.

Как off-policy оценка бандитов соотносится с типичной оценкой обучения с учителем на залогированных данных? Статья Twitter даёт некоторое понимание. Они вычислили два набора метрик: (i) PR-AUC на стандартном тестовом наборе и (ii) улучшения CTR против случайной политики. Между PR-AUC и CTR наблюдался компромисс.

Although the greedy policy performed well on PR-AUC, it did relatively poorly on CTR. Conversely, bandit policies such as UCB and Thompson Sampling did poorer on PR-AUC but outperformed the greedy policy on CTR. This shows the divergence where supervised learning that evaluates well on biased logged data via conventional metrics may not actually perform well on the metrics we really care about (e.g., CTR, conversion).

Хотя жадная политика показала хорошие результаты по PR-AUC, по CTR она показала себя относительно плохо. И наоборот, политики бандитов, такие как UCB и Thompson Sampling, показали себя хуже по PR-AUC, но превзошли жадную политику по CTR. Это демонстрирует расхождение, при котором обучение с учителем, которое хорошо оценивается на смещённых залогированных данных по традиционным метрикам, может на деле работать плохо по тем метрикам, которые нас действительно волнуют (например, CTR, конверсия).

• • •

• • •

Whew, that was a lot longer than the average post. If you’re still with me, I hope you found bandits to be a viable alternative for recommendation systems. Their focus on modeling uncertainty and deliberate exploration makes them effective when our data is small and we have low certainty on user-item preferences.

Уф, это оказалось гораздо длиннее среднего поста. Если вы всё ещё со мной, надеюсь, вы убедились, что бандиты — жизнеспособная альтернатива для рекомендательных систем. Их фокус на моделировании неопределённости и целенаправленном исследовании делает их эффективными, когда данных мало и у нас низкая уверенность в предпочтениях пользователей по отношению к объектам.

Do you know of other industrial implementations of bandit-based recommendation systems? Please share them in the comments below!

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

References

Ссылки

Artwork Personalization at Netflix Personalized Cuisine Filter A Contextual-Bandit Approach to Personalized News Article Learning from Logged Implicit Exploration Data Explore, Exploit, and Explain: Personalizing Explainable Recommendations Bandit based Optimization of Multiple Objectives on a Music Streaming Platform Carousel Personalization in Music Streaming Apps with Contextual Bandits Contextual User Browsing Bandits for Mobile Recommendations An Efficient Bandit Algorithm for Realtime Multivariate Optimization Deep Bayesian Bandits: Exploring in Online Personalized Recommendations Deep Neural Network Marketplace Recommenders in Online Experiments An Empirical Evaluation of Thompson Sampling Unbiased Offline Evaluation of Contextual-bandit-based News Article Recommendation Algorithms

If you found this useful, please cite this write-up as:

Если вы нашли это полезным, пожалуйста, цитируйте эту статью так:

Yan, Ziyou. (May 2022). Bandits for Recommender Systems. eugeneyan.com. https://eugeneyan.com/writing/bandits/.

Yan, Ziyou. (Май 2022). Bandits for Recommender Systems. eugeneyan.com. https://eugeneyan.com/writing/bandits/.

or

или

@article{yan2022bandit, title = {Bandits for Recommender Systems}, author = {Yan, Ziyou}, journal = {eugeneyan.com}, year = {2022}, month = {May}, url = {https://eugeneyan.com/writing/bandits/} }

@article{yan2022bandit, title = {Bandits for Recommender Systems}, author = {Yan, Ziyou}, journal = {eugeneyan.com}, year = {2022}, month = {May}, url = {https://eugeneyan.com/writing/bandits/} }

Join 11,800+ readers getting updates on machine learning, RecSys, LLMs, and engineering.

Присоединяйтесь к 11 800+ читателям, получающим обновления о машинном обучении, RecSys, LLM и инженерии.