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

arXiv: https://arxiv.org/abs/2510.22811 · HTML: https://mlsanity.com/paper/2510.22811/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 38 references that are in the map.
- First posted on arXiv 26 Oct 2025.

## Builds on (most cited first, 14 of 14)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Heterogeneous Federated Learning: State-of-the-art and Research Challenges](https://mlsanity.com/paper/2307.10616/) (2023)
- [Federated Bandit: A Gossiping Approach](https://mlsanity.com/paper/2010.12763/) (2020)
- [Distributed Cooperative Decision-Making in Multiarmed Bandits: Frequentist and Bayesian Algorithms](https://mlsanity.com/paper/1606.00911/) (2016)
- [Social Learning in Multi Agent Multi Armed Bandits](https://mlsanity.com/paper/1910.02100/) (2019)
- [The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits](https://mlsanity.com/paper/2001.05452/) (2020)
- [On Distributed Cooperative Decision-Making in Multiarmed Bandits](https://mlsanity.com/paper/1512.06888/) (2015)
- [Multi-Agent Multi-Armed Bandits with Limited Communication](https://mlsanity.com/paper/2102.08462/) (2021)
- [Decentralized Randomly Distributed Multi-agent Multi-armed Bandit with Heterogeneous Rewards](https://mlsanity.com/paper/2306.05579/) (2023)
- [Multi-Armed Bandit for Energy-Efficient and Delay-Sensitive Edge Computing in Dynamic Networks with Uncertainty](https://mlsanity.com/paper/1904.06258/) (2019)
- [Doubly Adversarial Federated Bandits](https://mlsanity.com/paper/2301.09223/) (2023)
- [Decentralized Task Offloading in Edge Computing: A Multi-User Multi-Armed Bandit Approach](https://mlsanity.com/paper/2112.11818/) (2021)
- [Decentralized Upper Confidence Bound Algorithms for Homogeneous Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2111.10933/) (2021)
- [Distributed Online Optimization with Stochastic Agent Availability](https://mlsanity.com/paper/2411.16477/) (2024)

## Built on by (most cited first, 1 of 1)

- [Adapting to Decision-Relevant Non-Stationarity in Decentralized Heterogeneous Bandits](https://mlsanity.com/paper/2609.16824/) (2026)

## Abstract (arXiv)

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.