Multi-Agent Multi-Armed Bandits with Limited Communication
share
We consider the problem where N agents collaboratively interact with an instance of a stochastic K arm bandit problem for K ≫ N. The agents aim to simultaneously minimize the cumulative regret over all the agents for a total of T time steps, the number of communication rounds, and the number of bits in each communication round. We present Limited Communication Collaboration - Upper Confidence Bound (LCC-UCB), a doubling-epoch based algorithm where each agent communicates only after the end of the epoch and shares the index of the best arm it knows. With our algorithm, LCC-UCB, each agent enjoys a regret of Õ(√((K/N+ N)T)), communicates for O(log T) steps and broadcasts O(log K) bits in each communication step. We extend the work to sparse graphs with maximum degree K_G, and diameter D and propose LCC-UCB-GRAPH which enjoys a regret bound of Õ(D√((K/N+ K_G)DT)). Finally, we empirically show that the LCC-UCB and the LCC-UCB-GRAPH algorithm perform well and outperform strategies that communicate through a central node
READ FULL TEXT