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
Google or a one-time email code. No password.