On-Demand Communication for Asynchronous Multi-Agent Bandits
On-Demand Communication for Asynchronous Multi-Agent Bandits
复制标题
DOI：
10.48550/arxiv.2302.07446
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Y. Chen;L. Yang;Xuchuang Wang;Xutong Liu;M. Hajiesmaili;John C.S. Lui;D. Towsley
中科院分区：
文献类型：
--
作者：
Y. Chen;L. Yang;Xuchuang Wang;Xutong Liu;M. Hajiesmaili;John C.S. Lui;D. Towsley
本文研究了协作多智能体多臂随机强盗问题，其中智能体异步操作--智能体拉动时间和速率未知、不规则且异构--并且面临与K臂强盗问题相同的情况。代理可以共享奖励信息，以加快学习过程，但需要额外的通信成本。我们提出了ODC，按需通信协议，量身定制的每对代理的通信的基础上，他们的经验拉时间。ODC是有效的，当拉时间的代理是高度异构的，其通信复杂性取决于经验拉时间的代理。ODC是一个通用的协议，可以集成到大多数合作的强盗算法，而不会降低其性能。然后，我们将ODC的UCB和AAE算法的自然扩展，并提出了两个通信效率的合作算法。我们的分析表明，这两种算法是近最佳的遗憾。
This paper studies a cooperative multi-agent multi-armed stochastic bandit problem where agents operate asynchronously -- agent pull times and rates are unknown, irregular, and heterogeneous -- and face the same instance of a K-armed bandit problem. Agents can share reward information to speed up the learning process at additional communication costs. We propose ODC, an on-demand communication protocol that tailors the communication of each pair of agents based on their empirical pull times. ODC is efficient when the pull times of agents are highly heterogeneous, and its communication complexity depends on the empirical pull times of agents. ODC is a generic protocol that can be integrated into most cooperative bandit algorithms without degrading their performance. We then incorporate ODC into the natural extensions of UCB and AAE algorithms and propose two communication-efficient cooperative algorithms. Our analysis shows that both algorithms are near-optimal in regret.