Sequential Selection of Correlated Ads by POMDPs
This addresses the challenge for online publishers of optimizing ad selection to increase revenue, representing an incremental improvement over existing methods.
The paper tackles the problem of online publishers selecting ads to maximize long-term income by using Partially Observable Markov Decision Processes (POMDPs) to balance exploration and exploitation, leveraging ad correlations to update belief states similarly to collaborative filtering. Experiments on a real-world dataset show that the algorithms significantly outperform strong baselines.
Online advertising has become a key source of revenue for both web search engines and online publishers. For them, the ability of allocating right ads to right webpages is critical because any mismatched ads would not only harm web users' satisfactions but also lower the ad income. In this paper, we study how online publishers could optimally select ads to maximize their ad incomes over time. The conventional offline, content-based matching between webpages and ads is a fine start but cannot solve the problem completely because good matching does not necessarily lead to good payoff. Moreover, with the limited display impressions, we need to balance the need of selecting ads to learn true ad payoffs (exploration) with that of allocating ads to generate high immediate payoffs based on the current belief (exploitation). In this paper, we address the problem by employing Partially observable Markov decision processes (POMDPs) and discuss how to utilize the correlation of ads to improve the efficiency of the exploration and increase ad incomes in a long run. Our mathematical derivation shows that the belief states of correlated ads can be naturally updated using a formula similar to collaborative filtering. To test our model, a real world ad dataset from a major search engine is collected and categorized. Experimenting over the data, we provide an analyse of the effect of the underlying parameters, and demonstrate that our algorithms significantly outperform other strong baselines.