Using Contextual Bandit models in large action spaces at Instacart

David Vengerov16 Jun 2023

Problem

A search team wants to personalize ranking for every user and query, but ranking has no small set of actions. A sorted list of several hundred candidates, drawn from millions of items, is one of a huge number of possible lists. Treating each item as an action also fails, because an item's click or purchase depends on the other items shown, which breaks the independent-reward assumption of contextual bandits. A standard bandit needs each action seen many times in each context, so it cannot be trained.

Example from the article: Instacart search should combine personal relevance, popularity, low price and in-store availability differently for a broad query such as "healthy snack" than for a well-defined one such as "milk".

Solution in brief

Shrink the action space to a handful of rankers or ranking formulas, collect randomized data, and train a contextual bandit to pick the best one per user and query. Score candidate policies offline with IPS and doubly robust estimators, and A/B test only the best.

Questions this case answers
  • How to learn a per-context choice of treatment with a bandit when the natural action (a ranked list) is combinatorially large and item rewards are not independent
  • How to estimate the value of a new decision policy from randomized logged data before launching it online
  • How to personalize search ranking with a contextual bandit when the items shown form a huge action space?
  • How to choose per user and query between several ranking formulas that trade off relevance, popularity, price and availability?

Tools and methods

  • Contextual bandit over rankers — picks a ranking formula per context
  • X-learner (meta-learner) — predicts the lift of each action over the control action
  • XGBoost with "action" as a categorical feature — the simplest bandit policy
  • Ray RLlib (DQN) — neural bandit for discrete actions
  • IPS and doubly robust estimators — offline value of a trained policy
Continue reading — it's free

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