Title: Online Learning to Rank in Stochastic Click Models,
Abstract: Online learning to rank is a core problem in information retrieval and
machine learning. Many provably efficient algorithms have been recently
proposed for this problem in specific click models. The click model is a model
of how the user interacts with a list of documents. Though these results are
significant, their impact on practice is limited, because all proposed
algorithms are designed for specific click models and lack convergence
guarantees in other models. In this work, we propose BatchRank, the first
online learning to rank algorithm for a broad class of click models. The class
encompasses two most fundamental click models, the cascade and position-based
models. We derive a gap-dependent upper bound on the $T$-step regret of
BatchRank and evaluate it on a range of web search queries. We observe that
BatchRank outperforms ranked bandits and is more robust than CascadeKL-UCB, an
existing algorithm for the cascade model.