Learning diverse rankings with multi-armed bandits

The probabilistic ranking principle advocates ranking documents in order of de-creasing probability of relevance to a query, independent of how other documents are ranked. The result is that similar documents are often ranked at similar po-sitions. In contrast, empirical studies have shown that a diverse set of results is often preferable over one containing redundant results, as typical web queries of-ten have different meanings for different users (such as jaguar). We present a new multi-armed bandit learning algorithm that directly learns a diverse ranking of results based on users ’ clicking behavior. In particular, it maximizes the proba-bility that a relevant document is found in the top k positions of a ranking. After T presentations of n documents ranked for a fixed query, our algorithm achieves a total payoff of at least (1 − 1/e)OPT − O(k√Tn log n) where OPT is the payoff of the optimal ordering if we knew the information needs of all users and (1 − 1/e)OPT is the best obtainable polynomial time approximation.