Document Type



Spring 5-5-2016

Embargo Period



Recommendation System, Online Learning, Diversity, Multi Armed Bandit, Upper Confidence Bound, Directed Graph




Electrical and Computer Engineering


We study a type of recommendation systems problem, in which the system must be able to cover as many users’ tastes as possible while users’ tastes change over time. This problem can be viewed as a variation of the maximum coverage problem, where the number of sets and elements within any sets can change dynamically. When the number of distinctive elements is large, an exhaustive search for even a fixed number of elements is known to be computationally expensive. Many known algorithms tend to have exponential growth in complexity. We propose a novel graph based UCB1 algorithm that effectively minimizes the number of elements to consider, thereby reducing the search space greatly. The algorithm utilizes a new rewarding scheme to choose items that satisfy more user types as it construct a relational graph between items to choose. Experiments show that the new algorithm performs better than existing techniques such as Ranked Bandits [17] and Independent Bandits [12] in terms of satisfying diverse types of users while minimizing computational complexity.

Additional Information

Under Review by Journal of Applied Intelligence