  This paper studies a homogeneous decentralized multi-armed bandit problem, in
which a network of multiple agents faces the same set of arms, and each agent
aims to minimize its own regret. A fully decentralized upper confidence bound
(UCB) algorithm is proposed for a multi-agent network whose neighbor relations
are described by a directed graph. It is shown that the decentralized algorithm
guarantees each agent to achieve a lower logarithmic asymptotic regret compared
to the classic UCB algorithm, provided the neighbor graph is strongly
connected. The improved asymptotic regret upper bound is reciprocally related
to the maximal size of a local neighborhood within the network. The roles of
graph connectivity, maximum local degree, and network size are analytically
elucidated in the expression of regret.
