Distributed Multi-Agent Bandits Over ErdHos-R'enyi Random Networks

We study the distributed multi-agent multi-armed bandit problem with heterogeneous rewards over random communication graphs. Uniquely, at each time step t agents communicate over a time-varying random graph Gt generated by applying the ErdHos-R'enyi model to a fixed connected base graph G (for classical ErdHos-R'enyi graphs, G is a complete graph), where each potential edge in G is randomly and independently present with the link probability p. Notably, the resulting random graph is not necessarily connected at each time step. Each agent's arm rewards follow time-invariant distributions, and the reward distribution for the same arm may differ across agents. The goal is to minimize the cumulative expected regret relative to the global mean reward of each arm, defined as the average of that arm's mean rewards across all agents. To this end, we propose a fully distributed algorithm that integrates the arm elimination strategy with the random gossip algorithm. We theoretically show that the regret upper bound is of order log T and is highly interpretable, where T is the time horizon. It includes the optimal centralized regret Oleft(sumk: Deltak>0 fraclog TDeltakright) and an additional term Oleft(fracN2 log Tp λN-1(Lap(G)) + fracKN2 log Tpright) where N and K denote the total number of agents and arms, respectively. This term reflects the impact of G's algebraic connectivity λN-1(Lap(G)) and the link probability p, and thus highlights a fundamental trade-off between communication efficiency and regret. As a by-product, we show a nearly optimal regret lower bound. Finally, our numerical experiments not only show the superiority of our algorithm over existing benchmarks, but also validate the theoretical regret scaling with problem complexity.