Online Learning for Cooperative Multi-Player Multi-Armed Bandits
Online Learning for Cooperative Multi-Player Multi-Armed Bandits
复制标题
DOI：
10.1109/cdc51059.2022.9992885
复制
发表时间：
2021-09
期刊：
影响因子：
--
通讯作者：
William Chang;Mehdi Jafarnia-Jahromi;Rahul Jain
中科院分区：
文献类型：
--
作者：
William Chang;Mehdi Jafarnia-Jahromi;Rahul Jain
针对具有多个合作玩家的多武装匪徒(MAB)提出了一种分布式在线学习框架，其中玩家每轮所获得的奖励取决于所有玩家所采取的行动。这是一个团队环境，目标是共同的。信息不对称使这个问题变得有趣和具有挑战性。我们考虑了三种类型的信息不对称：行动信息不对称，当参与者的行动不能被观察到，但获得的报酬是共同的；报酬信息不对称，当其他参与者的行动可以观察到，但获得的报酬是来自同一分布的IID；当我们同时存在行动和报酬信息不对称时。对于第一种设置，我们提出了一种受UCB启发的算法，无论奖励是IID还是马尔可夫，该算法都能达到O(LogT)遗憾。对于第二部分，我们提供了一个环境，使得第一个设置的算法给出线性遗憾。对于第三种设置，我们展示了‘EXPLE THEN COMMIT’算法的一种变体实现了几乎日志错误。
We introduce a framework for decentralized on-line learning for multi-armed bandits (MAB) with multiple cooperative players, where the reward obtained by the players each round depend on the actions taken by all the players. It’s a team setting, and the objective is common. Information asymmetry is what makes the problem interesting and challenging. We consider three types of information asymmetry: action information asymmetry when the actions of the players can’t be observed but the rewards received are common; reward information asymmetry when the actions of the other players are observable but rewards received are IID from the same distribution; and when we have both action and reward information asymmetry. For the first setting, we propose a UCB-inspired algorithm that achieves O(logT) regret whether the rewards are IID or Markovian. For the second section, we offer an environment such that the algorithm given for the first setting gives linear regret. For the third setting, we show that a variation of the ‘explore then commit’ algorithm achieves almost log regret.