Decentralized Cooperative Stochastic Bandits

Abstract

We study a decentralized cooperative stochastic multi-armed bandit problem with $K$ arms on a network of $N$ agents. In our model, the reward distribution of each arm is the same for each agent and rewards are drawn independently across agents and time steps. In each round, each agent chooses an arm to play and subsequently sends a message to her neighbors. The goal is to minimize the overall regret of the entire network. We design a fully decentralized algorithm that uses an accelerated consensus procedure to compute (delayed) estimates of the average of rewards obtained by all the agents for each arm, and then uses an upper confidence bound (UCB) algorithm that accounts for the delay and error of the estimates. We analyze the regret of our algorithm and also provide a lower bound. The regret is bounded by the optimal centralized regret plus a natural and simple term depending on the spectral gap of the communication matrix. Our algorithm is simpler to analyze than those proposed in prior work and it achieves better regret bounds, while requiring less information about the underlying network. It also performs better empirically.

Cited by in corpus (20)

• Pervasive AI for IoT applications: A Survey on Resource-efficient Distributed Artificial Intelligence
• Federated Bandit: A Gossiping Approach
• Multi-Agent Multi-Armed Bandits with Limited Communication
• Federated Linear Contextual Bandits
• Multi-player Multi-armed Bandits with Collision-Dependent Reward Distributions
• Cooperative Online Learning: Keeping your Neighbors Updated
• Dominate or Delete: Decentralized Competing Bandits in Serial Dictatorship
• Federated Multi-Armed Bandits
• Distributed Learning: Sequential Decision Making in Resource-Constrained Environments
• Robust Multi-Agent Multi-Armed Bandits
• When to Call Your Neighbor? Strategic Communication in Cooperative Stochastic Bandits
• The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits
• Online Learning for Cooperative Multi-Player Multi-Armed Bandits
• Exploiting Heterogeneity in Robust Federated Best-Arm Identification
• On Effective Parallelization of Monte Carlo Tree Search
• A Bandit Model for Human-Machine Decision Making with Private Information and Opacity
• PAC Guarantees for Cooperative Multi-Agent Reinforcement Learning with Restricted Communication
• Cooperative Multi-Agent Graph Bandits: UCB Algorithm and Regret Analysis
• Cooperative Stochastic Multi-agent Multi-armed Bandits Robust to Adversarial Corruptions
• Decentralized Upper Confidence Bound Algorithms for Homogeneous Multi-Agent Multi-Armed Bandits