Regret vs. Communication: Distributed Stochastic Multi-Armed Bandits and Beyond
This work addresses communication efficiency in distributed learning systems, offering incremental improvements with specific theoretical guarantees for multi-armed bandit applications.
The paper tackles the distributed stochastic multi-armed bandit problem by analyzing the trade-off between regret and communication among multiple players, proposing strategies like Over-Exploration that achieve regret independent of the number of players with minimal communication, and establishing lower bounds and matching strategies for unknown time horizons.
In this paper, we consider the distributed stochastic multi-armed bandit problem, where a global arm set can be accessed by multiple players independently. The players are allowed to exchange their history of observations with each other at specific points in time. We study the relationship between regret and communication. When the time horizon is known, we propose the Over-Exploration strategy, which only requires one-round communication and whose regret does not scale with the number of players. When the time horizon is unknown, we measure the frequency of communication through a new notion called the density of the communication set, and give an exact characterization of the interplay between regret and communication. Specifically, a lower bound is established and stable strategies that match the lower bound are developed. The results and analyses in this paper are specific but can be translated into more general settings.