Counterfactual Estimation and Optimization of Click Metrics for Search Engines

By Lihong Li, Shunbao Chen, Jim Kleban, Ankur Gupta. 2014

30 citations recorded by the source corpus.

Optimizing an interactive system against a predefined online metric is particularly challenging, when the metric is computed from user feedback such as clicks and payments. The key challenge is the counterfactual nature: in the case of Web search, any change to a component of the search engine may result in a different search result page for the same query, but we normally cannot infer reliably from search log how users would react to the new result page. Consequently, it appears impossible to accurately estimate online metrics that depend on user feedback, unless the new engine is run to serve users and compared with a baseline in an A/B test. This approach, while valid and successful, is unfortunately expensive and time-consuming. In this paper, we propose to address this problem using causal inference techniques, under the contextual-bandit framework. This approach effectively allows one to run (potentially infinitely) many A/B tests offline from search log, making it possible to estimate and optimize online metrics quickly and inexpensively. Focusing on an important component in a commercial search engine, we show how these ideas can be instantiated and applied, and obtain very promising results that suggest the wide applicability of these techniques.

Subfields: Artificial Intelligence, Information Systems, Management Science and Operations Research, Information Retrieval & Search, Causal Inference & Discovery, Recommender Systems

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

In Management Science and Operations Research

In Information Retrieval & Search

In Causal Inference & Discovery

In Recommender Systems

Citations in the corpus

Machine Learning Methods That Economists Should Know About (2019, methodology): “As q → 0, the solution penalizes the number of non-zero covariates, leading to best subset regression (Miller [2002], Bertsimas et al.”
Estimation Considerations in Contextual Bandits (2017, background): “There is also a significant body of research that leverages balancing for offline evaluation and learning of contextual bandit or reinforcement learning policies from logged data [57, 28, 44, 27, 43, 59, 37, 60, 10, 38, 64, 26, 39, 58, 66].”
Off-Policy Evaluation and Learning from Logged Bandit Feedback: Error Reduction via Surrogate Policy (2018, background): “One application of such logs is to estimate the performance of new policies, also known as oﬀ-policy evaluation [6, 11, 13].”
Batch learning from logged bandit feedback through counterfactual risk minimization (2015, methodology): “The inverse propensity scoring approach can work well when we have a good model of the historical algorithm (Strehl et al., 2010; Li et al., 2014, 2015), and doubly robust estimators (Dud´ık et al., 2011) are even more eﬀective when we additionally have a good model of the feedback.”