| Abstract |
This paper studies a cooperative multi-armed bandit problem with M agents cooperating together to solve the same instance of a K-armed stochastic bandit problem with the goal of maximizing the cumulative reward of agents. The agents are heterogeneous in (i) their limited access to a local subset of arms; and (ii) their decision-making rounds, i.e., agents are asynchronous with different decision-making gaps. The goal is to find the global optimal arm and agents are able to pull any arm, however, they observe the reward only when the selected arm is local.The challenge is a tradeoff for agents between pulling a local arm with the possibility of observing the feedback, or relying on the observations of other agents that might occur at different rates. Naive extensions of traditional algorithms lead to an arbitrarily poor regret as a function of aggregate action frequency of any suboptimal arm located in slow agents. We resolve this issue by proposing a novel two-stage learning algorithm, called CO-LCB algorithm, whose regret is a function of aggregate action frequency of agents containing the optimal arm. We also show that the regret of CO-LCB matches the regret lower bound up to a small factor. |