Optimal Regret Bounds for Collaborative Learning in Bandits
Amitis Shidani Sattar Vakili
We consider regret minimization in a general collaborative multi-agent
multi-armed bandit model, in which each agent faces a finite set of arms and
may communicate with other agents through a central controller. The optimal arm
for each agent in this model is the arm with the largest expected mixed reward,
where the mixed reward of each arm is a weighted average of its rewards across
all agents, making communication among agents crucial. While near-optimal
sample complexities for best arm identification are known under this
collaborative model, the question of optimal regret remains open. In this work,
we address this problem and propose the first algorithm with order optimal
regret bounds under this collaborative bandit model. Furthermore, we show that
only a small constant number of expected communication rounds is needed.