BubbleRank: Safe Online Learning to Re-Rank via Implicit Click Feedback
This addresses the challenge of safe exploration in ranking for applications like search, where traditional methods lack exploration or have high initial costs, though it is incremental as it builds on existing bandit and ranking techniques.
The paper tackles the problem of safe online learning to re-rank by combining offline and online approaches to improve ranking lists using implicit click feedback, resulting in BubbleRank, which achieves a proven upper bound on regret that degrades with the quality of the initial base list and is validated on a large-scale real-world dataset.
In this paper, we study the problem of safe online learning to re-rank, where user feedback is used to improve the quality of displayed lists. Learning to rank has traditionally been studied in two settings. In the offline setting, rankers are typically learned from relevance labels created by judges. This approach has generally become standard in industrial applications of ranking, such as search. However, this approach lacks exploration and thus is limited by the information content of the offline training data. In the online setting, an algorithm can experiment with lists and learn from feedback on them in a sequential fashion. Bandit algorithms are well-suited for this setting but they tend to learn user preferences from scratch, which results in a high initial cost of exploration. This poses an additional challenge of safe exploration in ranked lists. We propose BubbleRank, a bandit algorithm for safe re-ranking that combines the strengths of both the offline and online settings. The algorithm starts with an initial base list and improves it online by gradually exchanging higher-ranked less attractive items for lower-ranked more attractive items. We prove an upper bound on the n-step regret of BubbleRank that degrades gracefully with the quality of the initial base list. Our theoretical findings are supported by extensive experiments on a large-scale real-world click dataset.