Decentralized multi-armed bandit with multiple distributed players

We formulate and study a decentralized multi-armed bandit (MAB) problem, where M distributed players compete for N independent arms with unknown reward statistics. At each time, each player chooses one arm to play without exchanging information with other players. Players choosing the same arm collide, and, depending on the collision model, either no one receives reward or the colliding players share the reward in an arbitrary way. We show that the minimum system regret of the decentralized MAB grows with time at the same logarithmic order as in the centralized counterpart where players act collectively as a single entity by exchanging observations and making decisions jointly. A general framework of constructing fair and order-optimal decentralized policies is established based on a Time Division Fair Sharing (TDFS) of the M best arms. A lower bound on the system regret growth rate is established for a general class of decentralized polices, to which all TDFS policies belong. We further develop several fair and order-optimal decentralized polices within the TDFS framework and study their performance in different applications including cognitive radio networks, multi-channel communications in unknown fading environment, target collecting in multi-agent systems, and web search and advertising.