Communication-Efficient Collaborative Best Arm Identification
This work addresses communication bottlenecks in collaborative multi-agent learning, offering incremental improvements for distributed bandit algorithms.
The paper tackles the problem of top-m arm identification in a multi-agent bandit setting, aiming to maximize learning speedup while minimizing communication costs, and demonstrates the effectiveness of their algorithms through experiments.
We investigate top-$m$ arm identification, a basic problem in bandit theory, in a multi-agent learning model in which agents collaborate to learn an objective function. We are interested in designing collaborative learning algorithms that achieve maximum speedup (compared to single-agent learning algorithms) using minimum communication cost, as communication is frequently the bottleneck in multi-agent learning. We give both algorithmic and impossibility results, and conduct a set of experiments to demonstrate the effectiveness of our algorithms.