Horde of Bandits using Gaussian Markov Random Fields
This addresses the problem of scaling contextual bandits for large recommender systems by enabling efficient information sharing across many users without unrealistic clustering assumptions.
The paper tackled the scalability issue of the Gang of Bandits (GOB) model, which is limited by quadratic time complexity, by connecting it to Gaussian Markov Random Fields (GMRFs) and proposing a Thompson sampling algorithm, resulting in methods that scale to larger graphs without additional assumptions and show competitive or better performance than baseline approaches.
The gang of bandits (GOB) model \cite{cesa2013gang} is a recent contextual bandits framework that shares information between a set of bandit problems, related by a known (possibly noisy) graph. This model is useful in problems like recommender systems where the large number of users makes it vital to transfer information between users. Despite its effectiveness, the existing GOB model can only be applied to small problems due to its quadratic time-dependence on the number of nodes. Existing solutions to combat the scalability issue require an often-unrealistic clustering assumption. By exploiting a connection to Gaussian Markov random fields (GMRFs), we show that the GOB model can be made to scale to much larger graphs without additional assumptions. In addition, we propose a Thompson sampling algorithm which uses the recent GMRF sampling-by-perturbation technique, allowing it to scale to even larger problems (leading to a "horde" of bandits). We give regret bounds and experimental results for GOB with Thompson sampling and epoch-greedy algorithms, indicating that these methods are as good as or significantly better than ignoring the graph or adopting a clustering-based approach. Finally, when an existing graph is not available, we propose a heuristic for learning it on the fly and show promising results.