Offline evaluation of ranking policies with click models

Shuai Li, S. Muthukrishnan, Yasin Abbasi-Yadkori, Vishwa Vinay, Branislav Kveton, Zheng Wen

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    Many web systems rank and present a list of items to users, from recommender systems to search and advertising. An important problem in practice is to evaluate new ranking policies offline and optimize them before they are deployed. We address this problem by proposing evaluation algorithms for estimating the expected number of clicks on ranked lists from historical logged data. The existing algorithms are not guaranteed to be statistically efficient in our problem because the number of recommended lists can grow exponentially with their length. To overcome this challenge, we use models of user interaction with the list of items, the so-called click models, to construct estimators that learn statistically efficiently. We analyze our estimators and prove that they are more efficient than the estimators that do not use the structure of the click model, under the assumption that the click model holds. We evaluate our estimators in a series of experiments on a real-world dataset and show that they consistently outperform prior estimators.

    Original languageEnglish (US)
    Title of host publicationKDD 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
    PublisherAssociation for Computing Machinery
    Pages1685-1694
    Number of pages10
    ISBN (Print)9781450355520
    DOIs
    StatePublished - Jul 19 2018
    Event24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2018 - London, United Kingdom
    Duration: Aug 19 2018Aug 23 2018

    Publication series

    NameProceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

    Other

    Other24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2018
    CountryUnited Kingdom
    CityLondon
    Period8/19/188/23/18

    Keywords

    • Click models
    • Importance sampling
    • Offline evaluation
    • Ranking

    ASJC Scopus subject areas

    • Software
    • Information Systems

    Fingerprint Dive into the research topics of 'Offline evaluation of ranking policies with click models'. Together they form a unique fingerprint.

  • Cite this

    Li, S., Muthukrishnan, S., Abbasi-Yadkori, Y., Vinay, V., Kveton, B., & Wen, Z. (2018). Offline evaluation of ranking policies with click models. In KDD 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 1685-1694). (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining). Association for Computing Machinery. https://doi.org/10.1145/3219819.3220028