Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-armed Bandits
Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-armed Bandits
复制标题
DOI：
10.1109/focs.2019.00017
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Chao Tao;Qin Zhang;Yuanshuo Zhou
中科院分区：
文献类型：
--
作者：
Chao Tao;Qin Zhang;Yuanshuo Zhou
多臂强盗中的最佳臂识别（或纯探索）是机器学习中的一个基本问题。在本文中，我们研究这个问题的分布式版本，我们有多个代理，他们希望学习最好的手臂协作。我们希望量化有限交互（或通信步骤）下的协作能力，因为在许多情况下交互是昂贵的。我们衡量的运行时间的分布式算法的加速比最好的集中式算法，只有一个代理。我们给几乎紧轮加速权衡这个问题，沿着，我们开发了几种新的技术证明时间或置信度约束下的通信步骤的数量的下界。
Best arm identification (or, pure exploration) in multi-armed bandits is a fundamental problem in machine learning. In this paper we study the distributed version of this problem where we have multiple agents, and they want to learn the best arm collaboratively. We want to quantify the power of collaboration under limited interaction (or, communication steps), as interaction is expensive in many settings. We measure the running time of a distributed algorithm as the speedup over the best centralized algorithm where there is only one agent. We give almost tight round-speedup tradeoffs for this problem, along which we develop several new techniques for proving lower bounds on the number of communication steps under time or confidence constraints.