This study presents a theoretical analysis on the efficiency of interleaving,
an efficient online evaluation method for rankings. Although interleaving has
already been applied to production systems, the source of its high efficiency
has not been clarified in the literature. Therefore, this study presents a
theoretical analysis on the efficiency of interleaving methods. We begin by
designing a simple interleaving method similar to ordinary interleaving
methods. Then, we explore a condition under which the interleaving method is
more efficient than A/B testing and find that this is the case when users leave
the ranking depending on the item’s relevance, a typical assumption made in
click models. Finally, we perform experiments based on numerical analysis and
user simulation, demonstrating that the theoretical results are consistent with
the empirical results.