Multi-armed bandits in multi-agent networks
Multi-armed bandits in multi-agent networks
复制标题
多代理网络中的多臂老虎机
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
A. Jadbabaie
中科院分区：
文献类型：
--
作者：
Shahin Shahrampour;A. Rakhlin;A. Jadbabaie
本文在一个多玩家的框架中讨论了多手强盗问题。玩家探索一组有限的带有随机奖励的武器，每个武器的奖励分布与玩家有关。我们的目标是找到最佳的全局武器，即在玩家中平均获得最大预期奖励的武器。为了实现这一目标，我们开发了著名的UCB1算法的分布式变体。在网络结构中，玩家交换局部信息来估计全局奖励，同时使用依赖于网络特征的置信度界限。然后，在每一轮中，每个玩家投票选出一只手臂，多数投票作为网络动作进行。整个网络获得网络行动的回报，希望全球福利最大化。算法的性能是通过网络后悔的概念来衡量的。我们证明了在网络的谱间隙中，后悔与时间范围成对数关系，与时间范围成反比。我们的算法是最优的，因为在一个完整的网络中，它按网络大小缩小了单人游戏的遗憾。通过数值实验验证了理论结果。
This paper addresses the multi-armed bandit problem in a multi-player framework. Players explore a finite set of arms with stochastic rewards, and the reward distribution of each arm is player-dependent. The goal is to find the best global arm, i.e., the one with the largest expected reward when averaged out among players. To achieve this goal, we develop a distributed variant of the well-known UCB1 algorithm. Confined to a network structure, players exchange information locally to estimate the global rewards, while using a confidence bound relying on the network characteristics. Then, at each round, each player votes for an arm, and the majority vote is played as the network action. The whole network gains the reward of the network action, hoping to maximize the global welfare. The performance of the algorithm is measured via the notion of network regret. We prove that the regret scales logarithmically with respect to time horizon and inversely in the spectral gap of the network. Our algorithm is optimal in the sense that in a complete network it scales down the regret of its single-player counterpart by the network size. We demonstrate numerical experiments to verify our theoretical results.