Cooperative Multi-agent Bandits: Distributed Algorithms with Optimal
  Individual Regret and Constant Communication Costs
Lin Yang Xuchuang Wang Mohammad Hajiesmaili Lijun Zhang John C. S. Lui Don Towsley
Recently, there has been extensive study of cooperative multi-agent
multi-armed bandits where a set of distributed agents cooperatively play the
same multi-armed bandit game. The goal is to develop bandit algorithms with the
optimal group and individual regrets and low communication between agents. The
prior work tackled this problem using two paradigms: leader-follower and fully
distributed algorithms. Prior algorithms in both paradigms achieve the optimal
group regret. The leader-follower algorithms achieve constant communication
costs but fail to achieve optimal individual regrets. The state-of-the-art
fully distributed algorithms achieve optimal individual regrets but fail to
achieve constant communication costs. This paper presents a simple yet
effective communication policy and integrates it into a learning algorithm for
cooperative bandits. Our algorithm achieves the best of both paradigms: optimal
individual regret and constant communication costs.