  Most learning to rank research has assumed that the utility of different
documents is independent, which results in learned ranking functions that
return redundant results. The few approaches that avoid this have rather
unsatisfyingly lacked theoretical foundations, or do not scale. We present a
learning-to-rank formulation that optimizes the fraction of satisfied users,
with several scalable algorithms that explicitly takes document similarity and
ranking context into account. Our formulation is a non-trivial common
generalization of two multi-armed bandit models from the literature: "ranked
bandits" (Radlinski et al., ICML 2008) and "Lipschitz bandits" (Kleinberg et
al., STOC 2008). We present theoretical justifications for this approach, as
well as a near-optimal algorithm. Our evaluation adds optimizations that
improve empirical performance, and shows that our algorithms learn orders of
magnitude more quickly than previous approaches.
