Cooperative Bandit Algorithms With Optimal Regret and Communication Costs

In the cooperative multi-armed bandits problem, multiple agents cooperatively play the same multi-armed bandit game. The goal is to develop bandit algorithms with optimal group and individual regrets and low communication among agents. Despite extensive prior research, existing algorithms either cannot achieve time-independent communication costs or fail to achieve optimal individual regrets. We present a simple yet effective communication policy for cooperative bandits where the core algorithmic ideas fundamentally differ from prior work. That is, the proposed communication policy carefully determines the sharing frequency of agents’ local observations so that a certain quality of reward estimates is always maintained compared to a full cooperation policy. By deriving a separate lower bound on communication costs of cooperative algorithms, we show that our algorithms achieve the ultimate optimality goal: optimal group and individual regrets and time-independent communication costs.