Sensitive and Scalable Online Evaluation with Theoretical Guarantees
This work addresses the problem of scalable online evaluation for search engines, offering a method that balances correctness and user experience, which is incremental in improving existing multileaved comparison techniques.
The paper tackles the trade-off in multileaved comparison methods between reliable outcomes and user experience, proposing a theoretical framework and a new method called Pairwise Preference Multileaving (PPM) that is proven to be both considerate and have fidelity, showing empirically that PPM is more sensitive to user preferences and scalable.
Multileaved comparison methods generalize interleaved comparison methods to provide a scalable approach for comparing ranking systems based on regular user interactions. Such methods enable the increasingly rapid research and development of search engines. However, existing multileaved comparison methods that provide reliable outcomes do so by degrading the user experience during evaluation. Conversely, current multileaved comparison methods that maintain the user experience cannot guarantee correctness. Our contribution is two-fold. First, we propose a theoretical framework for systematically comparing multileaved comparison methods using the notions of considerateness, which concerns maintaining the user experience, and fidelity, which concerns reliable correct outcomes. Second, we introduce a novel multileaved comparison method, Pairwise Preference Multileaving (PPM), that performs comparisons based on document-pair preferences, and prove that it is considerate and has fidelity. We show empirically that, compared to previous multileaved comparison methods, PPM is more sensitive to user preferences and scalable with the number of rankers being compared.