Multi-Armed Bandits in Yandex Lavka

Evgeny Komarov27 May 2023

Problem

A grocery delivery app has a homepage block, "You'll like it", where the team can look for hidden user interests. They believe finding new interests lowers churn. They also need to learn quickly about new users, new items and promotions. A ranking that only exploits known preferences repeats popular items and collects no randomized data. Personal statistics are thin: a few dozen items per user against thousands per city.

Example from the article: in the Yandex Lavka pilot, the number of top items needed to cover 80% of homepage impressions grew several times after the bandits replaced the production ranking.

Solution in brief

Each item is a bandit arm with a Beta distribution of its click or add-to-cart probability, and the block shows items with the best sampled values (Thompson sampling). Statistics live in a tree: city × socio-demographic segment, then store × segment, then the user. A node with few interactions leans on its parent's CTR.

Questions this case answers
  • How to explore new items in a recommendation block with Thompson sampling when per-user interaction data is sparse, by sharing statistics across a hierarchy of segments
  • How to measure the effect of exploration on diversity, and approximate a long-term retention effect, when absolute impression counts are unavailable and long-term outcomes cannot yet be observed
  • How to explore new user interests in a grocery homepage recommendation block with multi-armed bandits
  • How to share statistics between a user, a store and a city so that a Thompson sampling bandit works with sparse personal data

Tools and methods

  • Thompson sampling with Beta distributions — chooses which item to show, and explores items with wide posteriors
  • Tree merging of statistics (Laplace-smoothing-like, parameter ν) — shares data from city to store to user
  • Socio-demographic classifiers — segment users by age, gender and income
  • Three-group A/B test — control, bandits without history, bandits with history
  • Cohort transition matrix — proxy for retention
Continue reading — it's free

Google or a one-time email code. No password.