Bayesian Algorithms for Decentralized Stochastic Bandits
- 18 May 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Information Theory
- Vol. 2 (2) , 564-583
Abstract
We study a decentralized cooperative multi-agent multi-armed bandit (MAB) problem with K arms and N agents connected over a network. In this model, each arm's reward distribution is the same for every agent, and rewards are drawn independently across agents and over time steps. At each iteration, agents independently choose an arm to play and exchange at most poly(K) real-valued messages with their neighbors. Existing lower bound on the average per-agent regret over the network shows that cooperation with other agents can achieve a reduction of O(\frac 1N) over when playing in isolation. Motivated by this, we study a message-passing algorithm that can be combined with existing Bayesian MAB algorithms. Using this, we propose a decentralized Thompson Sampling (TS) algorithm and a decentralized Bayes-UCB algorithm. Under decentralized TS for bounded rewards, we establish a problem-dependent upper bound on the average per-agent regret in terms of the number of agents in the network and the network topology. For Bernoulli rewards, our upper bound asymptotically matches the lower bound. We empirically show that the proposed decentralized TS algorithm incurs significantly lesser per-agent regret than previously proposed algorithms. Furthermore, we show that the proposed decentralized TS can be extended to general bandit problems, where posterior distribution cannot be computed in closed form. We combine our decentralized TS algorithm with Variational Inference to apply our proposed algorithm to complex realistic reward distributions in a computationally efficient manner. We implement our proposed decentralized TS under gossip protocol and over time-varying networks, where each communication link has a fixed probability of failure and show that it incurs logarithmic regret.Keywords
All Related Versions
Funding Information
- Office of Naval Research Global (N00014-18-1-2191)
This publication has 21 references indexed in Scilit:
- Collaborative Filtering Bandits2016
- Distributed Detection: Finite-Time Analysis and Impact of Network TopologyIEEE Transactions on Automatic Control, 2015
- A collaborative user-centered framework for recommending items in Online Social NetworksComputers in Human Behavior, 2015
- Information sharing in distributed stochastic bandits2015
- Distributed Online Learning in Social Recommender SystemsIEEE Journal of Selected Topics in Signal Processing, 2014
- The Safe Bayesian2012
- Dual Averaging for Distributed Optimization: Convergence Analysis and Network ScalingIEEE Transactions on Automatic Control, 2011
- Distributed Learning in Multi-Armed Bandit With Multiple PlayersIEEE Transactions on Signal Processing, 2010
- Competitive Collaborative LearningLecture Notes in Computer Science, 2005
- ON THE LIKELIHOOD THAT ONE UNKNOWN PROBABILITY EXCEEDS ANOTHER IN VIEW OF THE EVIDENCE OF TWO SAMPLESBiometrika, 1933