Title: Multi-Player Bandits: A Trekking Approach,
Abstract: 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.