Distributed Consensus Algorithm for Decision-Making in Multi-agent
  Multi-armed Bandit
Xiaotong Cheng Setareh Maghsudi
We study a structured multi-agent multi-armed bandit (MAMAB) problem in a
dynamic environment. A graph reflects the information-sharing structure among
agents, and the arms' reward distributions are piecewise-stationary with
several unknown change points. The agents face the identical
piecewise-stationary MAB problem. The goal is to develop a decision-making
policy for the agents that minimizes the regret, which is the expected total
loss of not playing the optimal arm at each time step. Our proposed solution,
Restarted Bayesian Online Change Point Detection in Cooperative Upper
Confidence Bound Algorithm (RBO-Coop-UCB), involves an efficient multi-agent
UCB algorithm as its core enhanced with a Bayesian change point detector. We
also develop a simple restart decision cooperation that improves
decision-making. Theoretically, we establish that the expected group regret of
RBO-Coop-UCB is upper bounded by $\mathcal{O}(KNM\log T + K\sqrt{MT\log T})$,
where K is the number of agents, M is the number of arms, and T is the number
of time steps. Numerical experiments on synthetic and real-world datasets
demonstrate that our proposed method outperforms the state-of-the-art
algorithms.