CONFERENCE (INTERNATIONAL) Doubly Robust Off-Policy Evaluation for Ranking Policies under the Cascade Behavior Model

Haruka Kiyohara ( Tokyo Institute of Technology ), Yuta Saito ( Hanjuku-kaso, Co., Ltd. ), Tatsuya Matsuhiro, Yusuke Narita ( Yale University ), Nobuyuki Shimizu, Yasuo Yamamoto

The 15th ACM International Conference on Web Search and Data Mining (WSDM2022)

February 15, 2022

In real-world recommender systems and search engines, optimizing ranking decisions, which present a list of items in a rank order, is critical. Off-policy evaluation (OPE) for ranking policies is thus gaining a growing interest because it enables performance estimation of unknown ranking policies using only logged data. Although OPE is beneficial, however, naive application of OPE for ranking policies faces a critical variance issue, as the item space is combinatorially large. To tackle this problem, previous studies introduce some assumptions on user behavior to make the combinatorial item space tractable. However, an unrealistic strong assumption may cause serious bias. Therefore, appropriately controlling the bias-variance tradeoff by imposing a reasonable assumption is key to success in OPE for ranking policies. To achieve a well-balanced bias-variance tradeoff, we propose the Cascade Doubly Robust estimator, which makes the cascade assumption, that a user interacts with items sequentially from the top position. We show that the proposed estimator is unbiased in more cases compared to existing estimators that make stronger assumptions on user behavior. Furthermore, compared to a previous estimator built on the same cascade assumption, the proposed estimator reduces the variance by leveraging a control variate. Comprehensive experiments on both synthetic and real-world e-commerce data demonstrate that our estimator leads to more accurate OPE than existing estimators in a variety of data and slate sizes.

Paper : Doubly Robust Off-Policy Evaluation for Ranking Policies under the Cascade Behavior Model (external link)