Personalizing Recommendations for a Learning User

Changyao Chen, Haixun Wang, Jagannath Putrevu5 Dec 2022

Problem

Recommenders usually assume a customer has fixed preferences that the system gradually uncovers. At Instacart, customers also learn their own preferences while browsing, so what they like shifts as they see more items. The customer never reports a reward, only an accept or reject (a click or purchase). A standard bandit that treats the user as a black box or as a stationary source of feedback explores too little to find the best option.

Example from the article: an arm can be a category such as dairy products, a single item or a whole recommendation algorithm. A rejection can be defined as too few clicks or purchases.

Solution in brief

Model the user as someone who keeps a confidence interval per arm and rejects an arm only when another arm is clearly better. The BAIR algorithm first shows only arms not yet rejected, so the user gathers experience with few rejections. It then removes rejected arms until one is left. This finds the best arm with probability 1−δ within O(1/δ) interactions.

Questions this case answers
  • How to identify the best option for a decision-maker who is still forming their own utility estimates and reveals only binary accept/reject answers
  • How to recommend to a user who is still learning their own preferences and changes them as they see more items?
  • How to find the best category, item or algorithm for a user when you only see accept/reject, not the reward?
  • How to explore with a new user without causing many rejections?

Tools and methods

  • Best arm identification under revealed preference (BAIR) — two-phase algorithm (sweeping, then elimination) for a user who learns while interacting
  • Multi-armed bandit — framing: arms are categories, items or algorithms, the outcome is a binary accept/reject
  • Confidence-interval user model — rational user who rejects an arm when its upper bound is below another arm's lower bound
Continue reading — it's free

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