Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms

By Lihong Li, Wei Chu, J. Langford, Xuanhui Wang. 2010

614 citations recorded by the source corpus.

Contextual bandit algorithms have become popular for online recommendation systems such as Digg, Yahoo! Buzz, and news recommendation in general. Offline evaluation of the effectiveness of new algorithms in these applications is critical for protecting online user experiences but very challenging due to their "partial-label" nature. Common practice is to create a simulator which simulates the online environment for the problem at hand and then run an algorithm against this simulator. However, creating simulator itself is often difficult and modeling bias is usually unavoidably introduced. In this paper, we introduce a replay methodology for contextual bandit algorithm evaluation. Different from simulator-based approaches, our method is completely data-driven and very easy to adapt to different applications. More importantly, our method can provide provably unbiased evaluations. Our empirical results on a large-scale news article recommendation dataset collected from Yahoo! Front Page conform well with our theoretical results. Furthermore, comparisons between our offline replay and online bucket evaluation of several contextual bandit algorithms show accuracy and effectiveness of our offline evaluation method.

Subfields: Artificial Intelligence, Management Science and Operations Research, 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 Management Science and Operations Research

In Recommender Systems

Citations in the corpus

How algorithmic confounding in recommendation systems increases homogeneity and decreases utility (2017, methodology): “[39] propose a method specically for reducing this bias in contextual bandit algorithms.”
Recommendations as Treatments: Debiasing Learning and Evaluation (2016, background): “To get unbiased estimates of recommendation quality despite missing observations, consider the following connection to estimating average treatment effects of a given policy in causal inference, that was already explored in the contextual bandit setting (Li et al., 2011; Dud´ık et al., 2011).”
Counterfactual reasoning and learning systems: the example of computational advertising (2012, methodology): “In particular, the work presented in this section is closely related to the Monte-Carlo approach of reinforcement learning (Sutton and Barto, 1998, chapter 5) and to the offline evaluation of contextual bandit policies (Li et al., 2010, 2011).”
Balanced Policy Evaluation and Learning (2017, background): “sification model '̂ to {(Xi, Ti) : i 2 [n]} and then estimates SAPE in an alternate but also plug-in fashion: ⌧̂ IPW(⇡) = ⌧̂W IPW(⇡), W IPW i (⇡) = ⇡Ti(Xi)/'̂Ti(Xi) For a deterministic policy, ⇡(x) 2 {0, 1}m, this can be interpreted as a rejection and importance sampling approach [23, 34]: reject sa”
Doubly Robust Off-policy Value Evaluation for Reinforcement Learning (2015, background): “In robotics and business/marketing applications, for instance, it is often risky (thus expensive) to run a policy without an estimate of the policy’s quality (Li et al., 2011; Bottou et al., 2013; Thomas et al., 2015a).”
Doubly Robust Policy Evaluation and Optimization (2014, methodology): “Our nonstationary policy evaluation builds on the rejection sampling approach, which has been previously shown to be effective (Li et al., 2011).”
Counterfactual Estimation and Optimization of Click Metrics for Search Engines (2014, methodology): “One natural choice, as is adopted by some authors [21, 22], is to minimize the worst-case variance, leading to a uniform distribution: pa ≡ 1/K for all a.”
Off-policy Bandits with Deficient Support (2020, background): “It is known that the IPS estimator is unbiased, E D [ R IPS ( π )] = R ( π ) , if the logging policy π 0 has full support for π [18]. estimator require that the logging policy π 0 all policies π ∈ Π in the policy space. spaces, like deep-networks f w ( x , y ) with softmax outputs of the π w ( y |…”
Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation (2019, background): “This problem is widely encountered in many real-life applications (e.g., Murphy et al., 2001; Li et al., 2011; Bottou et al., 2013; Thomas et al., 2017), where online experiments are expensive and high-quality simulators are difficult to build.”
Behavior Regularized Offline Reinforcement Learning (2019, background): “For example, for recommendation systems (Li et al., 2011; Covington et al., 2016) or health applications (Murphy et al., 2001), deploying a new policy may only be done at a low frequency after extensive testing and evaluation.”
DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections (2019, background): “Furthermore, in many real-world domains such as medicine [32], recommendation [25], and education [30], the deployment of a new policy, even just for the sake of performance evaluation, may be expensive and risky.”
Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation (2018, background): “This problem is of great practical importance in many application domains where deploying a new policy can be costly or risky, such as medical treatments [26], econometrics [13], recommender systems [19], education [23], Web search [18], advertising and marketing [4, 5, 38, 40].”
More Robust Doubly Robust Off-policy Evaluation (2018, background): “…et al. 2015a; Li et al. 2015; Jiang & Li 2016; Thomas & Brunskill 2016), and some of the results have been applied to problems in marketing (e.g., Li et al. 2011; Theocharous et al. 2015), healthcare (e.g., Murphy et al. 2001; Hirano et al. 2003), and education (e.g., Mandel et al. 2014; 2016).”
Optimal and Adaptive Off-policy Evaluation in Contextual Bandits (2016, methodology): “This question has been extensively researched in the contextual bandit model (see, e.g., [Li et al., 2011, Bottou et al., 2013, Oh and Scheuren, 1983, Little and Rubin, 2002] and references therein).”
Policy Evaluation and Optimization with Continuous Treatments (2018, background): “IPW estimation corrects distribution mismatch by averaging outcomes over a new dataset created out of reweighted instances where the logging and target policies assign the same treatment [16].”