  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.
