The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits
The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits
复制标题
DOI：
--
复制
发表时间：
2020-01
期刊：
影响因子：
--
通讯作者：
Ronshee Chawla;Abishek Sankararaman;A. Ganesh;S. Shakkottai
中科院分区：
文献类型：
--
作者：
Ronshee Chawla;Abishek Sankararaman;A. Ganesh;S. Shakkottai
我们考虑一个分散的多智能体多武装匪徒（MAB）设置由$N$代理，解决相同的MAB实例，以尽量减少个人累积遗憾。在我们的模型中，代理通过在任意连接图上的成对八卦式通信来交换消息。我们开发了两种新的算法，每个代理只从所有武器的一个子集。代理使用通信介质来仅推荐手臂ID（而不是样本），并且因此更新它们从其玩的手臂的集合。我们建立，如果代理通信$\Omega（\log（T））$次通过任何连接的成对的八卦机制，那么每个代理的遗憾是一个因素的顺序$N$相比，没有合作的情况下。此外，我们还证明了通信约束对算法的遗憾度只产生二阶影响。然后，我们分析这个二阶项的遗憾，以获得界限的遗憾沟通的权衡。最后，我们经验性地评估我们的算法，并得出结论，见解是根本的，而不是我们的边界的文物。我们还展示了一个下界，这使得我们的算法获得的遗憾缩放不能得到改善，即使在没有任何通信约束。因此，我们的研究结果表明，即使是最低水平的代理之间的合作大大减少了所有代理的遗憾。
We consider a decentralized multi-agent Multi Armed Bandit (MAB) setup consisting of $N$ agents, solving the same MAB instance to minimize individual cumulative regret. In our model, agents collaborate by exchanging messages through pairwise gossip style communications on an arbitrary connected graph. We develop two novel algorithms, where each agent only plays from a subset of all the arms. Agents use the communication medium to recommend only arm-IDs (not samples), and thus update the set of arms from which they play. We establish that, if agents communicate $\Omega(\log(T))$ times through any connected pairwise gossip mechanism, then every agent's regret is a factor of order $N$ smaller compared to the case of no collaborations. Furthermore, we show that the communication constraints only have a second order effect on the regret of our algorithm. We then analyze this second order term of the regret to derive bounds on the regret-communication tradeoffs. Finally, we empirically evaluate our algorithm and conclude that the insights are fundamental and not artifacts of our bounds. We also show a lower bound which gives that the regret scaling obtained by our algorithm cannot be improved even in the absence of any communication constraints. Our results thus demonstrate that even a minimal level of collaboration among agents greatly reduces regret for all agents.