Distributed Bandits with Heterogeneous Agents
Distributed Bandits with Heterogeneous Agents
复制标题
DOI：
10.1109/infocom48880.2022.9796901
复制
发表时间：
2022-01
期刊：
影响因子：
--
通讯作者：
Lin Yang;Y. Chen;M. Hajiesmaili;John C.S. Lui;D. Towsley
中科院分区：
文献类型：
--
作者：
Lin Yang;Y. Chen;M. Hajiesmaili;John C.S. Lui;D. Towsley
本文解决了一个多智能体的强盗设置M代理合作一起解决同一个例子的K-臂随机强盗问题。代理人是异质的：每个代理具有对本地分支子集的有限访问，并且代理是异步的，在决策回合之间具有不同的间隙。每个智能体的目标是找到其最优的局部分支，并且智能体可以通过与其他智能体共享他们的观察结果来进行合作。虽然代理之间的合作提高了学习的性能，但它带来了代理之间通信的额外复杂性。对于这种异构的多智能体设置，我们提出了两种学习算法，CO-UCB和CO-AAE。我们证明了这两种算法都实现了订单最优遗憾，即$O\left（{{\sum _{i：{{\bar \Delta }_i} > 0}}\log T/{{\tilde \Delta }_i}}\right）$，其中${\tilde \Delta _i}$是臂i的奖励均值与任何局部最优臂之间的最小次优差距。此外，精心选择有价值的合作信息，CO-AAE实现了O（log T）的低通信复杂度。最后，数值实验验证了这两种算法的有效性。
This paper tackles a multi-agent bandit setting where M agents cooperate together to solve the same instance of a K-armed stochastic bandit problem. The agents are heterogeneous: each agent has limited access to a local subset of arms and the agents are asynchronous with different gaps between decision-making rounds. The goal for each agent is to find its optimal local arm, and agents can cooperate by sharing their observations with others. While cooperation between agents improves the performance of learning, it comes with an additional complexity of communication between agents. For this heterogeneous multi-agent setting, we propose two learning algorithms, CO-UCB and CO-AAE. We prove that both algorithms achieve order-optimal regret, which is $O\left({{\sum _{i:{{\bar \Delta }_i} > 0}}\log T/{{\tilde \Delta }_i}}\right)$, where ${\tilde \Delta _i}$ is the minimum suboptimality gap between the reward mean of arm i and any local optimal arm. In addition, a careful selection of the valuable information for cooperation, CO-AAE achieves a low communication complexity of O(log T). Last, numerical experiments verify the efficiency of both algorithms.