Distributed Cooperative Decision-Making in Multiarmed Bandits: Frequentist and Bayesian Algorithms
This work addresses the challenge of efficient decision-making in distributed systems, such as sensor networks or robotics, by providing scalable algorithms for multi-agent bandit problems, though it is incremental as it builds on existing single-agent methods.
The paper tackles the problem of distributed cooperative decision-making in multiarmed bandits by extending single-agent algorithms to multi-agent settings with fixed communication networks, showing that the algorithms asymptotically recover centralized performance and characterizing the impact of graph structure on group performance.
We study distributed cooperative decision-making under the explore-exploit tradeoff in the multiarmed bandit (MAB) problem. We extend the state-of-the-art frequentist and Bayesian algorithms for single-agent MAB problems to cooperative distributed algorithms for multi-agent MAB problems in which agents communicate according to a fixed network graph. We rely on a running consensus algorithm for each agent's estimation of mean rewards from its own rewards and the estimated rewards of its neighbors. We prove the performance of these algorithms and show that they asymptotically recover the performance of a centralized agent. Further, we rigorously characterize the influence of the communication graph structure on the decision-making performance of the group.