Contextual Bandits in a Collaborative Environment
Authors:
Open Access
- 7 July 2016
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 529-538
Abstract
Contextual bandit algorithms provide principled online learning solutions to find optimal trade-offs between exploration and exploitation with companion side-information. They have been extensively used in many important practical scenarios, such as display advertising and content recommendation. A common practice estimates the unknown bandit parameters pertaining to each user independently. This unfortunately ignores dependency among users and thus leads to suboptimal solutions, especially for the applications that have strong social components. In this paper, we develop a collaborative contextual bandit algorithm, in which the adjacency graph among users is leveraged to share context and payoffs among neighboring users while online updating. We rigorously prove an improved upper regret bound of the proposed collaborative bandit algorithm comparing to conventional independent bandit algorithms. Extensive experiments on both synthetic and three large-scale real-world datasets verified the improvement of our proposed algorithm against several state-of-the-art contextual bandit algorithms.Keywords
Funding Information
- National Science Foundation (IIS-1553568)
This publication has 15 references indexed in Scilit:
- Stochastic bandits with side observations on networksACM SIGMETRICS Performance Evaluation Review, 2014
- Multi-armed bandits in the presence of side observations in social networks2013
- Interactive collaborative filtering2013
- A Contextual-Bandit Algorithm for Mobile Context-Aware Recommender System2012
- Bandit problems in networks: Asymptotically efficient distributed allocation rules2011
- A contextual-bandit approach to personalized news article recommendation2010
- Learning diverse rankings with multi-armed bandits2008
- Methods and metrics for cold-start recommendations2002
- Item-based collaborative filtering recommendation algorithms2001
- Asymptotically efficient adaptive allocation rulesAdvances in Applied Mathematics, 1985