  We study a decentralized multi-agent multi-armed bandit problem in which
multiple clients are connected by time dependent random graphs provided by an
environment. The reward distributions of each arm vary across clients and
rewards are generated independently over time by an environment based on
distributions that include both sub-exponential and sub-gaussian distributions.
Each client pulls an arm and communicates with neighbors based on the graph
provided by the environment. The goal is to minimize the overall regret of the
entire system through collaborations. To this end, we introduce a novel
algorithmic framework, which first provides robust simulation methods for
generating random graphs using rapidly mixing Markov chains or the random graph
model, and then combines an averaging-based consensus approach with a newly
proposed weighting technique and the upper confidence bound to deliver a
UCB-type solution. Our algorithms account for the randomness in the graphs,
removing the conventional doubly stochasticity assumption, and only require the
knowledge of the number of clients at initialization. We derive optimal
instance-dependent regret upper bounds of order $\log{T}$ in both sub-gaussian
and sub-exponential environments, and a nearly optimal mean-gap independent
regret upper bound of order $\sqrt{T}\log T$ up to a $\log T$ factor.
Importantly, our regret bounds hold with high probability and capture graph
randomness, whereas prior works consider expected regret under assumptions and
require more stringent reward distributions.
