Research map / Bandits and online learning / Multi-armed bandits
Distributed Multi-Agent Bandits Over Erdős-Rényi Random Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Gossip Successive Elimination, a fully distributed arm-elimination bandit with random gossip over Erdős–Rényi graphs induced by a connected base graph, giving a log T regret upper bound with explicit dependence on link probability p and algebraic connectivity, plus a near-matching lower bound.
Problem
Distributed multi-agent multi-armed bandits with heterogeneous rewards where agents communicate over time-varying random Erdős–Rényi graphs (possibly disconnected at each step) induced by a fixed connected base graph, aiming to minimize regret relative to global mean rewards.
Approach
Combine successive arm elimination with a random gossip protocol using a Laplacian-based random weight matrix W_t = I - Lap(G_t)/N (i.i.d. across rounds), with a confidence radius that has an estimation term and a consensus term depending on p and the base graph's algebraic connectivity.
Key results
- Regret upper bound O(sum_{Δk>0} log T/Δk + N^2 log T/(p λ_{N-1}(Lap G)) + K N^2 log T/p), which for complete base graphs gives O(sum log T/Δk + KN log T/p), improving on prior E-R results requiring p>1/2 and N-dependence.
- A near-matching instance-dependent lower bound: lim inf Reg_T/log T >= sum_{Δk>0} 2(1-s)/((1+ε)^2 Δk) for consistent policies, matching the centralized log T/Δ term.
- Experiments show the algorithm outperforms DrFed-UCB on synthetic and MovieLens data and that regret decreases as link probability p increases; the complete base graph yields the lowest regret.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Gossip Successive Elimination instead of DrFed-UCB | Distributed multi-agent bandits · Synthetic dataset | cumulative regret | Helped |
| Use Gossip Successive Elimination instead of DrFed-UCB | Distributed multi-agent bandits · MovieLens | cumulative regret | Helped |
| Increase the link probability p | Gossip Successive Elimination · Synthetic random-graph experiments | cumulative regret | Helped |
| Use a complete base graph rather than the other tested base graphs | Gossip Successive Elimination · Synthetic random-graph experiments | cumulative regret | Helped |
Limitations
- Lower bound does not capture the communication-graph term (N^2/p), left as open.
- Assumes algebraic connectivity of base graph is known; link probability p must be estimated in a burn-in phase otherwise.
- Analysis limited to stochastic rewards; contextual or adversarial settings not studied.
Experimental setup
Datasets: MovieLens
Benchmarks: synthetic bandit instances (N=16, K=5, T=10000) MovieLens (N=20 users, K=5 genres)
Metrics: cumulative regret
Baselines: DrFed-UCB
Builds on: successive elimination random gossip algorithm DrFed-UCB
Closest papers by meaning
- Decentralized Randomly Distributed Multi-agent Multi-armed Bandit with Heterogeneous Rewards (NeurIPS 2023 · similarity 0.94)
- Distributed Bandit Learning: Near-Optimal Regret with Efficient Communication (ICLR 2020 · similarity 0.92)
- Individual Regret in Cooperative Stochastic Multi-Armed Bandits (NeurIPS 2025 · similarity 0.90)
- Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling on Sparse Hypergraphs (AAAI 2024 · similarity 0.90)
- Heterogeneous Multi-Agent Bandits with Parsimonious Hints (AAAI 2025 · similarity 0.89)
- Communication-Efficient Collaborative Regret Minimization in Multi-Armed Bandits (AAAI 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.