Off-policy evaluation for slate recommendation

By Adith Swaminathan, Akshay Krishnamurthy, Alekh Agarwal, Miroslav Dud'ik, J. Langford, Damien Jose, Imed Zitouni. 2016

255 citations recorded by the source corpus.

This paper studies the evaluation of policies that recommend an ordered set of items (e.g., a ranking) based on some context---a common scenario in web search, ads, and recommendation. We build on techniques from combinatorial bandits to introduce a new practical estimator that uses logged data to estimate a policy's performance. A thorough empirical evaluation on real-world data reveals that our estimator is accurate in a variety of settings, including as a subroutine in a learning-to-rank task, where it achieves competitive performance. We derive conditions under which our estimator is unbiased---these conditions are weaker than prior heuristics for slate evaluation---and experimentally demonstrate a smaller bias than parametric approaches, even when these conditions are violated. Finally, our theory and experiments also show exponential savings in the amount of required data compared with general unbiased estimators.

Subfields: Computer Networks and Communications, Management Science and Operations Research, Reinforcement Learning, 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 Computer Networks and Communications

In Management Science and Operations Research

In Reinforcement Learning

In Recommender Systems

Citations in the corpus

Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems (2020, methodology): “Applications of offline RL for recommender systems include slate and whole-page optimization (Swaminathan et al., 2017), applying doubly robust estimation to estimate website visits Dudík et al. (2014), and A/B testing for click optimization (Gilotte et al., 2018).”
DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections (2019, background): “Off-policy Policy Evaluation The problem of off-policy policy evaluation has been heavily studied in contextual bandits [8, 42, 45] and in the more general RL setting [10, 16, 20, 23, 28, 29, 30, 43, 44].”
More Robust Doubly Robust Off-policy Evaluation (2018, background): “, actions are in the form of slates (Swaminathan et al., 2017), and 3) when the behavior policy is unknown.”
Benchmarks for Deep Off-Policy Evaluation (2021, background): “…reinforcement learning, has been studied extensively in domains such as healthcare (Thapa et al., 2005; Raghu et al., 2018), recommender systems (Dudík et al., 2014; Theocharous et al., 2015; Swaminathan et al., 2017), education (Mandel et al., 2014), and robotics (Kalashnikov et al., 2018).”
Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning (2019, background): “Given its importance, the research community actively advances OPE techniques, both for the bandit [15, 3, 49, 56, 32, 36] and reinforcement learning settings [26, 15, 16, 33, 58, 54, 40, 59, 10].”
Statistical Bootstrapping for Uncertainty Estimation in Off-Policy Evaluation (2020, background): “The OPE problem is especially relevant to many practical domains, such as health [22, 18], education [21], and recommendation systems [34], where accurate evaluation of a new policy is critical to maximize safety and minimize risks associated with deployment of a new policy [38].”
Bias and Debias in Recommender System: A Survey and Future Directions (2020, background): “Inspired by [157], some work [156], [158], [159] further explore off-policy evaluation for non-stationary recommendation environments or slate recommendation.”
Explore, exploit, and explain: personalizing explainable recommendations with bandits (2018, background): “The latter is the stronger assumption and naïvely assumes that combinatorial actions such as slate recommendation [23] result in rewards that are a sum of rewards for each action (see Section 5 for a discussion about future work).”
Calibrated recommendations (2018, background): “Given that calibration is a property of the entire recommended list, future improvements may be achieved by integrating calibration in the objective of listwise learning-to-rank approaches, and by going beyond the typical offline-setting of training and testing recommender systems, e.g., [24].”
Online Evaluation for Information Retrieval (2016, background): “Ugander et al. [2013] propose an approach to identifying possible units of experimentation using graph algorithms.”
Introduction to Multi-Armed Bandits (2019, background): “(2011), and further developed in subsequent work, (e.g., Dudı́k et al., 2012, 2014; Swaminathan and Joachims, 2015; Swaminathan et al., 2017).”
Top-K Off-Policy Correction for a REINFORCE Recommender System (2018, methodology): “a time [44].”
Efficient Counterfactual Learning from Bandit Feedback (2018, methodology): “…log data coming from the following data generating process (DGP), which is similar to those used in the literature on the offline evaluation of contextual bandit algorithms (Li et al. 2010; Strehl et al. 2010; Li et al. 2011; 2012; Swaminathan and Joachims 2015a; 2015b; Swaminathan et al. 2017).”
A Survey on Causal Inference (2020, methodology): “ˆERM = argmin ˆ Y ∈H { Rˆ IPS(Yˆ|P)}, where Rˆ IPS(Yˆ|P) is defined in Eqn.(32). Later, various works are developed to drawbacks of propensity score weighting, including estimation variance reduction [115, 135], handle data sparsity [115, 135], doubly robust estimation [143]. In addition to using IP”
Towards a Fair Marketplace: Counterfactual Evaluation of the trade-off between Relevance, Fairness & Satisfaction in Recommendation Systems (2018, background): “Off-policy evaluation, and counterfactual estimation of metrics has recently gained a lot of attention in the research community, with recent work focusing on counterfactual estimation of search engine metrics [14], for evaluating slate recommendations [27].”
Efficient Algorithms for Logistic Contextual Slate Bandits with Bandit Feedback (2025, unknown): “Recently a large number of works [Swaminathan et al., 2017, Kiyohara et al., 2024, Vlassis et al., 2024] have studied the slate bandit problem in the off-policy setting, wherein they utilize a dataset collected using some base policy to find optimal slate bandit policies.”