Online ranker evaluation is a key challenge in information
retrieval. An important task in the online evaluation of
rankers is using implicit user feedback for inferring preferences between rankers. Interleaving methods have been
found to be ecient and sensitive, i.e. they can quickly detect even small dierences in quality. It has recently been
shown that multileaving methods exhibit similar sensitivity
but can be more ecient than interleaving methods. This
paper presents empirical results demonstrating that existing multileaving methods either do not scale well with the
number of rankers, or, more problematically, can produce
results which substantially dier from evaluation measures
like NDCG. The latter problem is caused by the fact that
they do not correctly account for the similarities that can
occur between rankers being multileaved. We propose a new
multileaving method for handling this problem and demonstrate that it substantially outperforms existing methods, in
some cases reducing errors by as much as 50%.