Dynamic Clustering of Contextual Multi-Armed Bandits

• Main Authors: NGUYEN, Trong T., LAUW, Hady W.
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2014
• Subjects: exploitation and exploration; multi-armed bandit; clustering; Databases and Information Systems; Numerical Analysis and Scientific Computing
• Online Access: https://ink.library.smu.edu.sg/sis_research/2328; https://ink.library.smu.edu.sg/context/sis_research/article/3328/viewcontent/cikm14b.pdf
• Institution: Singapore Management University

With the prevalence of the Web and social media, users increasingly express their preferences online. In learning these preferences, recommender systems need to balance the trade-off between exploitation, by providing users with more of the "same", and exploration, by providing users with something "new" so as to expand the systems' knowledge. Multi-armed bandit (MAB) is a framework to balance this trade-off. Most of the previous work in MAB either models a single bandit for the whole population, or one bandit for each user. We propose an algorithm to divide the population of users into multiple clusters, and to customize the bandits to each cluster. This clustering is dynamic, i.e., users can switch from one cluster to another, as their preferences change. We evaluate the proposed algorithm on two real-life datasets.