Multi-player bandits: a musical chairs approach
Multi-player bandits: a musical chairs approach
复制标题
多人强盗：抢椅子的方法
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Liran Szlak
中科院分区：
文献类型：
--
作者：
Jonathan Rosenski;Ohad Shamir;Liran Szlak
我们考虑随机多武器盗匪问题的一个变体，其中多个玩家同时从同一组武器中进行选择，并且可能发生碰撞，没有获得奖励。这种设置是由认知无线电网络中出现的问题所驱动的，并且在玩家之间的交流有限的现实假设下尤其具有挑战性。我们提供了一种无交流的算法（音乐椅子），它可以实现高概率的持续后悔，以及一种亚线性后悔，无交流的算法（动态音乐椅子），用于更困难的设置，即玩家在整个游戏过程中动态进入和离开。此外，这两种算法都不需要事先知道玩家的数量。据我们所知，这些是第一个具有这些形式保证类型的无通信算法。
We consider a variant of the stochastic multiarmed bandit problem, where multiple players simultaneously choose from the same set of arms and may collide, receiving no reward. This setting has been motivated by problems arising in cognitive radio networks, and is especially challenging under the realistic assumption that communication between players is limited. We provide a communication-free algorithm (Musical Chairs) which attains constant regret with high probability, as well as a sublinear-regret, communication-free algorithm (Dynamic Musical Chairs) for the more difficult setting of players dynamically entering and leaving throughout the game. Moreover, both algorithms do not require prior knowledge of the number of players. To the best of our knowledge, these are the first communication-free algorithms with these types of formal guarantees.