Explore/Exploit Schemes for Web Content Optimization

TLDR

Bandit methods have long been studied, but existing solutions fail for web content publishing due to dynamic item sets, short lifetimes, delayed feedback, and non‑stationary CTRs. The paper proposes novel multi‑armed bandit schemes, including a Bayesian solution, to maximize clicks on regularly published Yahoo! content modules. The authors use a Bayesian multi‑armed bandit framework that explores items by sampling a small fraction of visits to estimate CTRs, exploits high‑CTR items to maximize clicks, and validates the approach with live side‑by‑side experiments on Yahoo!

Abstract

We propose novel multi-armed bandit (explore/exploit) schemes to maximize total clicks on a content module published regularly on Yahoo! Intuitively, one can "explore'' each candidate item by displaying it to a small fraction of user visits to estimate the item's click-through rate (CTR), and then "exploit'' high CTR items in order to maximize clicks. While bandit methods that seek to find the optimal trade-off between explore and exploit have been studied for decades, existing solutions are not satisfactory for Web content publishing applications where dynamic set of items with short lifetimes, delayed feedback and non-stationary reward (CTR) distributions are typical. In this paper, we develop a Bayesian solution and extend several existing schemes to our setting. Through extensive evaluation with nine bandit schemes, we show that our Bayesian solution is uniformly better in several scenarios. We also study the empirical characteristics of our schemes and provide useful insights on the strengths and weaknesses of each. Finally, we validate our results with a "side-by-side'' comparison of schemes through live experiments conducted on a random sample of real user visits to Yahoo!