Distributed Bandit Learning: Near-Optimal Regret with Efficient Communication
Distributed Bandit Learning: Near-Optimal Regret with Efficient Communication
复制标题
分布式强盗学习：近乎最优的后悔与高效的沟通
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Liwei Wang
中科院分区：
文献类型：
--
作者：
Yuanhao Wang;Jiachen Hu;Xiaoyu Chen;Liwei Wang
研究了分布式盗贼学习中的后悔最小化问题，其中$M$代理在中心服务器的协调下协同工作以最小化他们的总后悔。我们的目标是设计出具有接近最优的差错和较小的通信开销的通信协议，这是以传输的数据总量来衡量的。对于分布式多臂匪徒，我们提出了一个具有近似最优错误和仅$O(M\log(MK))$通信代价的协议，其中$K$是武器数。通信开销与时间跨度无关，仅与武器数成对数关系，且除对数因子外与下界匹配。对于分布式$d$维线性强盗，我们提出了一种协议，该协议实现了近似最优的错误恢复，通信开销为$tide{O}(Md)$，仅对$T$具有对数依赖性。
We study the problem of regret minimization for distributed bandits learning, in which $M$ agents work collaboratively to minimize their total regret under the coordination of a central server. Our goal is to design communication protocols with near-optimal regret and little communication cost, which is measured by the total amount of transmitted data. For distributed multi-armed bandits, we propose a protocol with near-optimal regret and only $O(M\log(MK))$ communication cost, where $K$ is the number of arms. The communication cost is independent of the time horizon $T$, has only logarithmic dependence on the number of arms, and matches the lower bound except for a logarithmic factor. For distributed $d$-dimensional linear bandits, we propose a protocol that achieves near-optimal regret and has communication cost of order $\tilde{O}(Md)$, which has only logarithmic dependence on $T$.
DOI：
10.1109/focs.2019.00017
发表时间：
2019-04
期刊：
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
Chao Tao;Qin Zhang;Yuanshuo Zhou
通讯作者：
Chao Tao;Qin Zhang;Yuanshuo Zhou