A contextual-bandit approach to personalized news article recommendation
By Lihong Li, Wei Chu, J. Langford, Robert E. Schapire. 2010
3,422 citations recorded by the source corpus.
Personalized web services strive to adapt their services (advertisements, news articles, etc.) to individual users by making use of both content and user information. Despite a few recent advances, this problem remains challenging for at least two reasons. First, web service is featured with dynamically changing pools of content, rendering traditional collaborative filtering methods inapplicable. Second, the scale of most web services of practical interest calls for solutions that are both fast in learning and computation. In this work, we model personalized recommendation of news articles as a contextual bandit problem, a principled approach in which a learning algorithm sequentially selects articles to serve users based on contextual information about the users and articles, while simultaneously adapting its article-selection strategy based on user-click feedback to maximize total user clicks. The contributions of this work are three-fold. First, we propose a new, general contextual bandit algorithm that is computationally efficient and well motivated from learning theory. Second, we argue that any bandit algorithm can be reliably evaluated offline using previously recorded random traffic. Finally, using this offline evaluation method, we successfully applied our new algorithm to a Yahoo! Front Page Today Module dataset containing over 33 million events. Results showed a 12.5% click lift compared to a standard context-free bandit algorithm, and the advantage becomes even greater when data gets more scarce.
Subfields: Artificial Intelligence, Information Systems, 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
- Sergey Levine
- Yoshua Bengio
- Pieter Abbeel
- Mohit Bansal
- Jianfeng Gao
- Percy Liang
- Ruslan Salakhutdinov
- Quoc V. Le
In Information Systems
- Xiangnan He
- Xing Xie
- Xiang Wang
- Maarten de Rijke
- Tat-seng Chua
- Thorsten Joachims
- Lihong Li
- Nathan Kallus
In Management Science and Operations Research
- Lihong Li
- Sergey Levine
- Csaba Szepesvari
- Nathan Kallus
- Emma Brunskill
- R´emi Munos
- Nan Jiang
- Alekh Agarwal
In Recommender Systems
- Nathan Kallus
- Lihong Li
- Xiangnan He
- Charu C. Aggarwal
- Thorsten Joachims
- Qingyun Wu
- Hongning Wang
- Xing Xie
Citations in the corpus
- Bridging the Gap Between Value and Policy Based Reinforcement Learning (2017, background): “Model-free RL has a myriad of applications in games [22, 37], robotics [16, 17], and marketing [18, 38], to name a few.”
- Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems (2020, methodology): “Nevertheless, OPE is a popular tool in areas such as online advertising (Li et al., 2010) or healthcare (Murphy et al.”
- Conservative Q-Learning for Offline Reinforcement Learning (2020, background): “Recent advances in reinforcement learning (RL), especially when combined with expressive deep network function approximators, have produced promising results in domains ranging from robotics [29] to strategy games [4] and recommendation systems [35].”
- DRN: A Deep Reinforcement Learning Framework for News Recommendation (2018, methodology): “Our method is significantly different from the MAB group of methods [5, 7, 23, 40, 44, 50] due to its explicit modeling of future rewards, and different from previous MDP methods [27, 35, 36, 38] using user log due to its continuous representation of state and action, and the capability to scale to ”
- How algorithmic confounding in recommendation systems increases homogeneity and decreases utility (2017, background): “Some investigators have modeled these systems using temporal dynamics [35] or framed them in an explore/exploit paradigm [38, 60].”
- Taking the Human Out of the Loop: A Review of Bayesian Optimization (2016, methodology): “Although the objective function is shown, in practice it is unknown.”
- 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 Linear Contextual Bandits (2018, methodology): “We focus on the domain of linear online contextual bandits with provable guarantees, such as LinUCB (Li et al. 2010) and LinTS (Agrawal and Goyal 2013), and we propose two new algorithms, balanced linear UCB (BLUCB) and balanced linear Thompson sampling (BLTS).”
- Estimation Considerations in Contextual Bandits (2017, methodology): “BLTS and BLUCB build on linear contextual bandits LinTS [6] and LinUCB [45] respectively.”
- Doubly Robust Policy Evaluation and Optimization (2014, methodology): “A more effective learning algorithm, by definition, will have a higher V1:T value (Li et al., 2010).”
- Counterfactual Estimation and Optimization of Click Metrics for Search Engines (2014, background): “ypically does not know ˇahead of time when data are being collected, and there may be multiple policies to be evaluated on the same exploration data. One natural choice, as is adopted by some authors [21, 22], is to minimize the worst-case variance, leading to a uniform distribution: p a1=Kfor all a”
- Learning from Logged Implicit Exploration Data (2010, methodology): “To obtain non-random log data, we ran the LinUCB algorithm using the offline bandit simulation procedure, both from [8], on our random log data D0 and recorded events (x, a, r) for which LinUCB chose arm a for context x.”
- Off-policy evaluation for slate recommendation (2016, methodology): “In recommendation systems for e-commerce, search, or news, we would like to use the data collected during operation to test new content-serving algorithms (called policies) along metrics such as revenue and number of clicks [4, 25].”
- Benchmarks for Deep Off-Policy Evaluation (2021, background): “However, this sort of active online interaction is often impractical for real-world problems, where active data collection can be costly (Li et al., 2010), dangerous (Hauskrecht & Fraser, 2000; Kendall et al., 2019), or time consuming (Gu et al., 2017).”
- Reinforcement learning (2019, neutral): “I Related to gradient bandit algorithms [Sutton and Barto, 2018] and contextual bandits [Li et al., 2010].”