We study stochastic multi-armed bandits with many players. The players do not know the number of players, cannot communicate with each other and if multiple players select a common arm they collide and none of them receive any reward. We consider the static scenario, where the number of players remains fixed, and the dynamic scenario, where the players enter and leave at any time. We provide algorithms based on a novel `trekking approach' that guarantees constant regret for the static case and sub-linear regret for the dynamic case with high probability. The trekking approach eliminates the need to estimate the number of players resulting in fewer collisions and improved regret performance compared to the state-of-the-art algorithms. We also develop an epoch-less algorithm that eliminates any requirement of time synchronization across the players provided each player can detect the presence of other players on an arm. We validate our theoretical guarantees using simulation based and real test-bed based experiments.

本文研究了具有许多玩家的随机多臂老虎机。结果表明我们提出的一种新的“徒步旅行策略”不需要估计玩家的数量，同时保证了静态情况下常数风险和动态情况下高概率的子线性风险表现。我们还证明了我们的算法的有效性。

多人赌博机问题：一种追踪方法