Decentralized Cooperative Stochastic Bandits
This addresses the problem of efficient decision-making in distributed networks for applications like sensor networks or multi-agent systems, representing an incremental improvement over existing decentralized bandit algorithms.
The paper tackles the decentralized cooperative stochastic multi-armed bandit problem by designing a fully decentralized algorithm that uses accelerated consensus and UCB to minimize overall network regret, achieving better regret bounds than prior work with simpler analysis and less network information.
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.