Optimal Algorithms for Multiplayer Multi-Armed Bandits
Optimal Algorithms for Multiplayer Multi-Armed Bandits
复制标题
多人多臂强盗的最优算法
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Alessio Russo
中科院分区：
文献类型：
--
作者：
Po;A. Proutière;Kaito Ariu;Yassir Jedra;Alessio Russo
本文研究了多人多臂强盗(MMAB)问题，其中M个决策者或玩家合作以最大化他们的累积回报。我们fi首先调查MMAB问题，在这个问题中，玩家选择相同的手臂经历碰撞(并意识到这一点)，并且不会获得任何奖励。针对这一问题，我们提出了DPE1(Distributed Parsimonous Explore)算法，这是一种与最优集中式算法具有相同的渐近遗憾的分散式算法。DPE1比最先进的算法SIC-MMAB Boursier and Perchet(2019年)更简单，但ff有更好的性能保证。然后我们研究了无碰撞的MMAB问题，其中玩家可以选择相同的手臂。玩家坐在图的顶点上，在每一轮中，他们能够向图中的邻居发送消息。我们提出了一种简单且渐近最优的算法DPE2，它的性能优于最先进的算法DD-UCB Mart‘ıNez-Rubio等人。(2019年)。此外，在DPE2下，图中玩家传输的期望比特数为finite。
The paper addresses various Multiplayer Multi-Armed Bandit ( MMAB ) problems, where M decision-makers, or players, collaborate to maximize their cumulative reward. We first investigate the MMAB problem where players selecting the same arms experience a collision (and are aware of it) and do not collect any reward. For this problem, we present DPE1 (Decentralized Parsimonious Exploration), a decentralized algorithm that achieves the same asymptotic regret as that obtained by an optimal centralized algorithm. DPE1 is simpler than the state-of-the-art al-gorithm SIC-MMAB Boursier and Perchet (2019), and yet offers better performance guarantees. We then study the MMAB problem without collision, where players may select the same arm. Players sit on vertices of a graph, and in each round, they are able to send a message to their neighbours in the graph. We present DPE2 , a simple and asymptotically optimal algorithm that out-performs the state-of-the-art algorithm DD-UCB Mart´ınez-Rubio et al. (2019). Besides, under DPE2 , the expected number of bits transmitted by the players in the graph is finite.
合作多臂强盗中的社会模仿：具有严格本地信息的基于分区的算法
DOI：
10.1109/cdc.2018.8619744
发表时间：
2018
期刊：
2018 IEEE Conference on Decision and Control
影响因子：
--
作者：
Landgren, Peter;Srivastava, Vaibhav;Ehrich Leonard, Naomi
通讯作者：
Ehrich Leonard, Naomi