Distributed Clustering of Linear Bandits in Peer to Peer Networks

Abstract

We provide two distributed confidence ball algorithms for solving linear bandit problems in peer to peer networks with limited communication capabilities. For the first, we assume that all the peers are solving the same linear bandit problem, and prove that our algorithm achieves the optimal asymptotic regret rate of any centralised algorithm that can instantly communicate information between the peers. For the second, we assume that there are clusters of peers solving the same bandit problem within each cluster, and we prove that our algorithm discovers these clusters, while achieving the optimal asymptotic regret rate within each one. Through experiments on several real-world datasets, we demonstrate the performance of proposed algorithms compared to the state-of-the-art.

arXiv commentThe 33rd ICML, 2016

References in corpus (5)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Contextual Bandits with Similarity Information
• Online Clustering of Bandits
• Graph Clustering Bandits for Recommendation

Cited by in corpus (23)

• Differentially-Private Federated Linear Bandits
• Game of Thrones: Fully Distributed Learning for Multi-Player Bandits
• Hierarchical stochastic graphlet embedding for graph-based pattern recognition
• Federated Bandit: A Gossiping Approach
• Federated Linear Contextual Bandits
• Simple Regret Minimization for Contextual Bandits
• Cuttlefish: A Lightweight Primitive for Adaptive Query Processing
• Distributed Bandit Learning: Near-Optimal Regret with Efficient Communication
• Kernel Methods for Cooperative Multi-Agent Contextual Bandits
• Improved Algorithm on Online Clustering of Bandits
• Cooperative Multi-Agent Bandits with Heavy Tails
• Robust Multi-Agent Multi-Armed Bandits
• Asynchronous Parallel Empirical Variance Guided Algorithms for the Thresholding Bandit Problem
• Accelerated Gossip in Networks of Given Dimension using Jacobi Polynomial Iterations
• Collaborative Filtering Bandits
• The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits
• Online Learning for Cooperative Multi-Player Multi-Armed Bandits
• PAC Guarantees for Cooperative Multi-Agent Reinforcement Learning with Restricted Communication
• Show Me the Whole World: Towards Entire Item Space Exploration for Interactive Personalized Recommendations
• Context-Aware Bandits
• Multitask Bandit Learning Through Heterogeneous Feedback Aggregation
• Fast Distributed Bandits for Online Recommendation Systems
• Collaborative Pure Exploration in Kernel Bandit