Skip to content

Distributed Multi-Agent Bandits Over Erdős-Rényi Random Networks

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

This paper proposes Gossip Successive Elimination (GSE), a fully distributed algorithm for multi-agent multi-armed bandits (MA-MAB) over generalized Erdős–Rényi random communication graphs with heterogeneous rewards. The regret upper bound is O(log T) and explicitly characterizes the impact of both link probability p and the base graph's algebraic connectivity, removing prior assumptions that p must be large. A matching lower bound confirms the centralized component is tight.

Problem

Existing MA-MAB work on random graphs (specifically Xu & Klabjan 2023) requires p > 1/2 and derives regret bounds with no explicit p-dependence. No prior work handles generalized Erdős–Rényi graphs where communication is constrained to a fixed connected base graph G (classical E-R is the special case where G is complete). The gap: how to derive interpretable, tight regret bounds for any p ∈ (0,1] over arbitrary connected base graphs with heterogeneous rewards.

Method

GSE integrates three components under a time-varying random graph G_t induced by base graph G with per-edge inclusion probability p:

  1. Arm elimination: Each agent maintains an active arm set S_i and eliminates arm k when another arm k′ satisfies GLCB_{i,k′}(t) ≥ GUCB_{i,k}(t). All agents pull active arms with minimum pull count, ensuring comparable sample counts.
  2. Laplacian-based gossip weight matrix: W_t = I_N − (1/N)Lap(G_t), chosen so weight matrices are i.i.d. across rounds, enabling global reward estimate z_{i,k}(t) to converge to true global mean µ_k via neighbor aggregation.
  3. Two-term confidence bound: c_{i,k}(t) = √(4log(T) / (N·max{T_{i,k}(t)−KL, 1})) + 4(√N + τ) / max{T_{i,k}(t)−KL, 1}, where τ = 2log(NT)/(p·λ_{N-1}(Lap(G))) captures consensus delay and L* = N − 2N log(T)/log(1−p) is the burn-in arm count. If p is unknown, a O(log T) burn-in phase estimates p̂ ∈ (p/2, p].

Key Contributions

  • First MA-MAB formulation over generalized Erdős–Rényi graphs (arbitrary connected base graph G, not just complete graphs), valid for any p ∈ (0,1].
  • Regret upper bound O(Σ_{k:Δ_k>0} log T/Δ_k + N²log T/(p·λ_{N-1}(Lap(G))) + KN²log T/p), explicit in p and algebraic connectivity λ_{N-1}(Lap(G)).
  • Under classical E-R (complete base graph), improves over Xu & Klabjan 2023 by reducing N-dependence: O(Σ log T/Δ_k + KN log T) vs. their O(Σ N log T/Δ_k).
  • Nearly matching lower bound: Σ_{k:Δ_k>0} 2(1−s)/((1+ε)²Δ_k) · log T, confirming the centralized term is optimal.
  • Explicit regret–communication trade-off: higher p reduces regret but increases expected communication pN T per agent.

Results

  • Synthetic (T=10,000, N=16, K=5, complete graph, p=0.9): GSE achieves ~300 cumulative regret vs. DrFed-UCB ~500; regret plateaus after initial exploration as suboptimal arms are eliminated.
  • Real-world MovieLens (T=10,000, N=20, K=5): GSE achieves ~100 cumulative regret vs. DrFed-UCB ~400.
  • Graph topology effect (synthetic): At p=0.9, complete graph < Petersen graph < grid graph in regret; grid's low λ_{N-1} produces regret ~800 vs. ~300 for complete graph.
  • Link probability effect: Regret decreases monotonically with p across all base graph types, consistent with O(1/p) theoretical bound.
  • Baseline: DrFed-UCB (Xu & Klabjan 2023), the only prior gossip algorithm for E-R MA-MAB with heterogeneous rewards.

Limitations

  • Requires algebraic connectivity λ_{N-1}(Lap(G)) to be known a priori (or estimated externally); only p can be estimated online.
  • Lower bound does not formally capture the communication-dependent terms (O(N²/p) component is argued intuitively, not proven); full characterization of the communication-graph lower bound is left as future work.
  • Restricted to stochastic reward settings; extension to contextual or adversarial rewards is not addressed.
  • Experiments use small N (≤20) and K (=5); scalability to large-N regimes is not empirically validated.

Relevance to Agentic AI / LLM Agents

This work addresses the theoretical foundations of how distributed agents can collectively learn optimal actions when they cannot freely communicate — a core constraint in any real multi-agent deployment where network topology, bandwidth, or privacy limits information flow. The explicit regret–communication trade-off (tunable via p) is directly actionable for designing agentic systems that balance coordination overhead against decision quality. The gossip-based arm elimination framework is a building block for decentralized LLM agent ensembles performing distributed exploration (e.g., hyperparameter search, tool selection, or routing decisions across federated nodes). The heterogeneous reward setting — where the same arm yields different returns for different agents — maps naturally to personalized or role-differentiated multi-agent scenarios common in LLM orchestration frameworks.