Recommendation System, Online Learning, Diversity, Multi Armed Bandit, Upper Conﬁdence 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 ﬁxed 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 eﬀectively 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  and Independent Bandits  in terms of satisfying diverse types of users while minimizing computational complexity.
Rahman, Mahmuda and Oh, Jae C., "A Graph-based Bandit Algorithm for Maximum User Coverage in Online Recommendation Systems" (2016). Electrical Engineering and Computer Science. 249.