Problem
Expedia Group ranks the components of a home page and learns the order from user clicks. A ranker trained on clicks only sees feedback on what it showed, so an item that was never shown, or shown too low, is never promoted. Clicks are also noisy: a click does not prove the item was the best choice. With 15 candidates and a list of 10 there are roughly 11 billion possible rankings, too many to test one by one.
Example from the article: a model keeps recommending a backpack because it gets clicks, and never learns that a museum would have a higher click-through rate, because the museum is never shown.
Solution in brief
Treat each item as a sub-arm of a bandit. Model clicks with the cascade assumption, so the model is one attraction probability per item. Estimate it with a linear model of item and context features and pick rankings by Thompson sampling (CascadeLinTS), which explores until the posterior is narrow.
Questions this case answers
- How to learn the best ordered list of items from implicit click feedback when only the shown items produce feedback and the number of possible orderings is too large to test one by one
- How to correct for position bias when learning a ranking from clicks while still exploring items that are rarely shown
- How to rank the components of a home page when clicks are the only feedback and the current model never shows some good items?
- How to learn the best ordering of a list when the number of possible rankings is in the billions?
Tools and methods
- Cascade click model — explains position bias: users scan from the top and stop at the first attractive item
- CascadeLinTS — linear Thompson sampling for cascade bandits, chooses the ranking and updates after feedback
- Structured (sub-arm) feedback — one list gives information about every ranking that contains the same items
- Regret — the loss against the optimal ranking, used to compare the bandit with a greedy baseline
Google or a one-time email code. No password.