A Decentralized Policy with Logarithmic Regret for a Class of
  Multi-Agent Multi-Armed Bandit Problems with Option Unavailability
  Constraints and Stochastic Communication Protocols
  This paper considers a multi-armed bandit (MAB) problem in which multiple
mobile agents receive rewards by sampling from a collection of spatially
dispersed stochastic processes, called bandits. The goal is to formulate a
decentralized policy for each agent, in order to maximize the total cumulative
reward over all agents, subject to option availability and inter-agent
communication constraints. The problem formulation is motivated by applications
in which a team of autonomous mobile robots cooperates to accomplish an
exploration and exploitation task in an uncertain environment. Bandit locations
are represented by vertices of the spatial graph. At any time, an agent's
option consist of sampling the bandit at its current location, or traveling
along an edge of the spatial graph to a new bandit location. Communication
constraints are described by a directed, non-stationary, stochastic
communication graph. At any time, agents may receive data only from their
communication graph in-neighbors. For the case of a single agent on a fully
connected spatial graph, it is known that the expected regret for any optimal
policy is necessarily bounded below by a function that grows as the logarithm
of time. A class of policies called upper confidence bound (UCB) algorithms
asymptotically achieve logarithmic regret for the classical MAB problem. In
this paper, we propose a UCB-based decentralized motion and option selection
policy and a non-stationary stochastic communication protocol that guarantee
logarithmic regret. To our knowledge, this is the first such decentralized
policy for non-fully connected spatial graphs with communication constraints.
When the spatial graph is fully connected and the communication graph is
stationary, our decentralized algorithm matches or exceeds the best reported
prior results from the literature.
