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

We thank the reviewer for the valuable suggestions and address the concerns as follows.

Q1: Regarding concern on the confidence interval in Figure 2

A1: Thank you for your careful review. We would like to note that Figure 2 includes confidence intervals in a different format from Figure 1, using error bars rather than shaded regions (as in Figure 1). We chose this format because the confidence intervals are relatively small in this case, which may make them less visually prominent. This small variance across runs also supports the robustness and stability of our proposed algorithm, GSE. To improve clarity, we will revise Figure 2 either to be consistent with Figure 1 by using shaded areas or to enlarge the error bars to make the confidence intervals more apparent.

Q2: Line 337 (...we sample $<>$ each independently...) seems to have a missing term. Is it "edge"? In line 338 , what is this new term $q_i$ used to define means? They dont seem to have a definition either above or in the appendix table symbology! Is this expected?

A2: Thank you for pointing this out. The missing term in Line 337 should be $q_i$. The variable $q_i$ is intentionally introduced to model the heterogeneity across agents by ensuring that each agent $i \in [N]$ has a different reward distribution for the same arm $k$. Specifically, $q_i$ is independently and uniformly sampled from $[0,1]$ at the beginning, and the local mean reward is defined as $\mu_{i,k} = q_i \cdot \frac{k-1}{K-1}$, which induces global heterogeneity. This experimental design follows a similar approach as in [1], and we will revise the text to clearly define $q_i$ and eliminate any ambiguity in the revised version.

Q3: In line 348 authors briefly discuss the algorithm's performance based on the rate at which agents discard their dominated arms. A graph on these dynamics, something like that arms discarded over total arms discarded along with the regret in a temporal phase, like in Figure 1 would be very informative, right? This could help clearly define for the agents' exploitation phase of farming rewards from the "trusted" arms!

A3: To further investigate the dynamic behavior of our algorithm during the arm elimination phase, we track the regret progression at each point where an arm is eliminated. Table 4 records five independent trials under a classical Erdős–Rényi communication graph with $p=0.9$. After averaging over 20 trials, we report the average timestep when an arm is eliminated and the average corresponding cumulative regret. We observe a consistent trend across experiments: each elimination event corresponds to a gradual transition from exploration to exploitation, as reflected in the slower growth rate of regret after the elimination of more suboptimal arms. This illustrates that agents progressively narrow their action set to focus on near-optimal arms, thereby stabilizing their regret growth. This temporal analysis provides empirical support for our theoretical discussion, and highlights the importance of timely arm elimination in reducing long-term regret.

Table 4: Average over 20 runs of GSE with classical Erdős–Rényi graph and p=0.9.

Q4: A bit mild on the multi-agent side of problem formulation: getting information from agents, even ones you are neighbors with can be noisy/adversarial from the agents' perspective!

A4: We appreciate the valuable suggestions and would include the discussion on scenarios with noisy and adversarial agents in the future work section as well. The discussion reads as follows verbatim. 1. Noisy agents: When information from other agents is noisy—meaning that the shared reward data consists of the original reward signal plus potentially random noise or has correlation risks [4], as commonly observed in digital communication channels—this issue can, in principle, be addressed using techniques from noisy optimization [6]. These methods combine statistical and optimization tools to effectively handle function optimization under noise, which can be leveraged in the construction of reward estimators when using such noisy information. Also, this problem is novel and meaningful in the sense that random communication and random noise coexist, making the noisy optimization problem more challenging. 2. Adversarial agents: When other agents are adversarial—intentionally broadcasting malicious information—we will adopt a Byzantine-robust framework [2, 5], in which the reward information is truncated to produce robust estimators, such as the trimmed mean or median of means, to filter out malicious reward information. Notably, this direction is novel in that the presence of random graphs with underlying base graphs further complicates the construction of Byzantine-robust estimators, compared to traditional multi-agent bandits or distributed robust optimization settings with fixed, connected graphs or assuming linear reward models.

Q5: While authors already clearly acknowledge their algorithm suffers from a tradeoff between regret minimization and communication cost reduction, they could probably benefit from analyzing the communication in a broadcasted sense that emerges from the connected components in the $\mathcal{G}_t$, rather than a one-to-one communication between edges several times.

A5: We appreciate this suggestion and will include the idea of communication cost reduction through the information propagation of graph-level analysis rather than edge-level analysis in the discussion of future work. Hypothetically, communication based on connected components can be illustrated using $l$-connected graphs [3], which consider the composition of subgraphs across time steps. Instead of analyzing a single graph at each time step, we consider the joint information provided by graphs from previous steps, which could potentially further reduce communication costs.

[1] Jialin Yi and Milan Vojnovic. Doubly adversarial federated bandits. In the International Conference on Machine Learning, 2023.

[2] Vial, Daniel, Sanjay Shakkottai, and R. Srikant. Robust multi-agent bandits over undirected graphs. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 2022

[3] Zhu, Jingxuan, and Ji Liu. Distributed multiarmed bandits. IEEE Transactions on Automatic Control, 2023

[4] Shao, Qi, Jiancheng Ye, and John CS Lui. Risk-aware multi-agent multi-armed bandits. Proceedings of the Twenty-fifth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, 2024.

[5] Mitra, Aritra, Arman Adibi, George J. Pappas, and Hamed Hassani. Collaborative linear bandits with adversarial agents: Near-optimal regret bounds. Advances in neural information processing systems, 2022

[6] Mai, Van Sy, Richard J. La, Tao Zhang, and Abdella Battou. Distributed optimization with global constraints using noisy measurements. IEEE Transactions on Automatic Control, 2023

Thanks for your positive feedback. We address your concerns as follows.

Q1: Concerns about algorithm novelty

A1: Reviewer nBgW raised a similar concern; please see Q3 and A3 in response to reviewer nBgW for a detailed explanation of algorithmic novelties and corresponding theoretical analysis.

Q2: Concerns about knowledge of $\lambda_{N-1}$

A2: We appreciate the reviewer’s concern about algebraic connectivity $\lambda_{N-1}$. Similar to prior work [2,3], our confidence bound requires knowledge of $\lambda_{N-1}$. However, $\lambda_{N-1}$ can be estimated in a fully decentralized manner (e.g. brief gossip-based power iteration [7]).

Q3: Concerns about additional term on estimating $p$

A3: We appreciate and agree that estimating $p$ without prior knowledge inevitably incurs extra regret. In future work, we plan to reduce this overhead by (1) improving the sample efficiency of the estimation phase, or (2) incorporating the estimated $p$ into decision making during exploitation instead of requiring the exact value.

Q4: Concerns about the communication complexity

A4: Thanks for highlighting this point. As discussed in Remark 5.6, the average communication complexity per agent in our setting is $O(p|\mathcal{E}|T/N)$, where $p$ is the edge activation probability and $\mathcal{E}$ is the edge set of the base graph with $|\mathcal{E}| \leq O(N^2)$. In contrast, [1] assumes a complete graph and incurs $O(pNT)$ communication. Notably, when $|\mathcal{E}|=O(N)$, our complexity becomes $O(pT)$, independent of $N$, indicating better scalability. Exploring ways to further reduce communication—building on recent advances in cost-efficient protocols [5]—is an exciting future direction.

Q5: Challenges in upper bounds in Lemma 5.2 and Theorem 5.3

A5: Thanks for the question. The main technical challenge in establishing the regret bounds in Lemma 5.2 and Theorem 5.3 lies in the general communication model we consider. Unlike prior works that assume fixed or strongly connected graphs w.h.p., our setting allows each edge to appear independently with probability $p>0$, meaning the graph may be disconnected in many rounds. As a result, traditional confidence bounds—designed to handle sampling noise—are no longer sufficient, since error also arises from communication delays. The key challenge is thus to design a confidence interval that accounts for both statistical estimation and consensus error.

To this end, we introduce the confidence interval $c_{i,k}(t)$ in Eq.(4), which captures both estimation and consensus error. The regret bounds in Lemma 5.2 and Theorem 5.3 build upon Lemma 5.1, which guarantees convergence of each agent’s estimate $z_{i,k}(t)$ to the global mean $\mu_k$ under this interval. The proof involves defining several high-probability events (Appendix C, Line 520) ensuring: (i) concentration of local estimates, (ii) sufficient mixing of information across agents to reach consensus, and (iii) balanced arm pulls for different agents. These allow us to decompose the error in $z_{i,k}(t)$ into estimation and consensus components (Eq.(12)), which are then bounded separately. We will incorporate the above explanation into the revised version of the paper.

Q6: Tightness of regret bounds and obstacles in reducing upper bound

A6: We acknowledge that there remains a gap between the theoretical upper and lower bounds in our current analysis. Specifically, while the first term in Theorem 5.3—which captures the centralized noise matches the lower bound in Theorem 5.9, the remaining terms in the upper bound depending on graph properties such as $p$ and $\lambda_{N-1}$, are not yet matched by our lower bound. However, we would also like to add that we make contributions toward narrowing the gap between the lower and upper bounds in existing work. Notably, our upper bound is smaller by the order of $O(N)$ compared to that in [3] for the centralized regret term under their assumptions. More importantly, it also introduces a novel reflection of the communication graph through the presence of $1/p$ in the upper bound. Our newly added experiment (A3(ii), Table 2 in responses to reviewer bG2e) shows that the actual regret exhibits a dependency of $1/p^{0.93}$, which numerically validates the near-tightness of our upper bound. On the other hand, our lower bound improves upon existing work [1] by explicitly incorporating the sub-optimality gap.

Moreover, we believe that the $O(N^2/p)$ term in the upper bound reflects a fundamental limitation due to communication delays and is unlikely to be avoided. Consider, for instance, a communication graph structured as a cycle, where each edge is connected independently with probability $p$ in each round. In such a scenario, it takes on average $O(N/p)$ rounds for information from one agent to reach all other agents (similar philosophy as suggested by the reward delay in [6]). Since each agent must collect information from all others to compute a globally optimal policy, this implies a minimum communication delay of $O(N/p)$ for each agent. Summing up across all $N$ agents, this suggests a lower bound of $O(N^2/p)$ on the global regret, indicating that the communication-induced term in Theorem 5.3 is intrinsic to the problem. While we have explored ideas for reducing the last two terms in Theorem 5.3 (e.g., potentially improving dependency on $K$ in the third term from $O(K)$ to $O(\log K)$, as discussed in our reply to Reviewer bG2e), we still anticipate that any meaningful upper bound must involve a term of at least $O(N^2/p)$ to account for the global information aggregation delay. Closing this remaining gap and formally establishing a lower bound that includes $p$ and $\lambda_{N-1}$ remains an important direction for future work.

Q7: Possibility to improve the graph-dependent terms to match bounds in time-invariant, homogeneous setting

A7: While there remains a gap between our regret bound in the time-invariant and homogeneous setting and the result in [2], we believe that this gap is not merely due to our analysis, but rather stems from a fundamental difference between the homogeneous and heterogeneous settings which results in the difference in the algorithm design.

The dependence on $N$ in our second and third terms is $O(N^2)$, while the corresponding dependence in Theorem 3.2 of [2] is only $O(N\log N)$. As explained in A6, in the heterogeneous setting, each agent must collect information from all other agents to accurately estimate the global reward and make optimal decisions. This necessity leads to an inherent $O(N^2)$ communication delay (even in the time-invariant case when $p=1$). In contrast, in the homogeneous setting, agents share the same reward structure and do not necessarily need information from others, enabling a regret bound with only $O(N\log N)$ dependence. This core difference fundamentally limits the possibility of matching the bounds in [2] within our heterogeneous setting.

Given this, we see potential to improve our bounds via algorithmic modifications for best-of-both-worlds performance—i.e., optimality in both heterogeneous and homogeneous settings. One idea is to detect reward consistency across agents and switch accordingly between heterogeneous and homogeneous algorithms, akin to prior work adapting to stochastic vs. adversarial regimes [4]. This may also reduce the $\log T$ dependence in Theorem 5.3, as achieved in [2] for homogeneous setting. We leave this for future work.

Q8: Distinctions between our lower bound and single-agent lower bound and the possibility to add graph-dependent terms in our lower bound

A8: Our proof extends beyond the single-agent case by directly targeting global regret across all $N$ agents. Unlike classical lower bounds that perturb one arm's mean for a single agent, we construct two instances $\nu$ and $\nu'$ that shift the mean of the same arm for all agents simultaneously (see lines 305–308), yielding a lower bound on $\sum_{i=1}^N \mathbb{E}[T_{i,k}(T)]$ and thus the global regret. This primarily establishes the tightness of the centralized term. That said, we acknowledge that the lower bound is not our main contribution. The key novelties lie in: 1) a new setting with generalized random graphs; 2) a new algorithm based on successive elimination with a novel confidence bound adapted to random gossip; and 3) an upper-bound analysis that explicitly captures graph parameters ($p$, $\lambda_{N-1}$), removing the strong assumptions on $p$ in [3]. Still, our lower bound improves upon [1], and we agree that extending it to incorporate graph-dependent terms remains a challenging and important direction.

Q9: Regarding the concerns about the placement of conclusion, future work and proofreading modifications

A9: Thank you for the suggestions. We will move the conclusion and future work to the main body, proofread, and incorporate these changes in the revision.

References

[1] Mengfan Xu and Diego Klabjan. Multi-agent multi-armed bandit regret complexity and optimality. AISTATS, 2025.

[2] David Martínez-Rubio, Varun Kanade, and Patrick Rebeschini. Decentralized cooperative stochastic bandits. NeurIPS, 2019.

[3] Mengfan Xu and Diego Klabjan. Decentralized randomly distributed multi-agent multi-armed bandit with heterogeneous rewards. NeurIPS, 2023.

[4] Bubeck, Sébastien, and Aleksandrs Slivkins. The best of both worlds: Stochastic and adversarial bandits. COLT, 2012.

[5] Xuchuang Wang, Lin Yang, Yu-Zhen Janice Chen, Xutong Liu, Mohammad Hajiesmaili, Don Towsley, John C.S. Lui. Achieving near-optimal individual regret low communications in multi-agent bandits. ICLR, 2023.

[6] Tal Lancewicki, Shahar Segal, Tomer Koren, Yishay Mansour. Stochastic multi-armed bandits with unrestricted delay distributions. ICML, 2021.

[7] David Kempe, Alin Dobra, and Johannes Gehrke. Gossip‐based computation of aggregate information. FOCS, 2003.

Q1: Concerns about conclusion and future works.

A1: Thank you for the suggestion. We will revise the paper by moving the conclusion and future work to the final section of the main body.

Q2: Concerns about tightness of upper bound and regret-communication trade-off existence

A2: We acknowledge that verifying the presence of graph-dependent terms in the lower bound is essential to substantiate the regret-communication trade-off emphasized in our upper bound analysis. While Theorem 5.3 presents an upper bound that includes terms dependent on graph properties such as the link probability $p$, the lower bound in Theorem 5.9 does not yet capture these dependencies. However, we argue that the trade-off is inherent to the problem and not merely an artifact of the analysis, and we make contributions towards this direction.

To support this claim, consider a cycle graph over $N$ agents, where each edge is activated independently with probability $p$. On average, it takes $O(N/p)$ rounds for information to propagate from one agent to reach all the other agents. Since our setting requires each agent to optimize with respect to global rewards, which depend on data from all agents, this information delay directly impacts the agent's ability to make optimal decisions. Therefore, each agent may suffer at least $O(N/p)$ regret, leading to a total global regret of at least $O(N^2/p)$. This suggests a fundamental dependence on $p$, even in the lower bound. Combined with the lower bound on the statistical noise term in Theorem 5.9, this observation highlights that the regret-communication trade-off should indeed exist. Intuitively, as $p$ decreases, it takes longer for information to diffuse across the network, resulting in larger regret. In the extreme case where $p$ approaches zero, inter-agent communication becomes virtually impossible, and no agent can optimize global performance, leading to linear regret. This aligns with the trade-off discussed in Remark 5.6: more frequent communication reduces regret, while sparse communication increases it.

We would also like to add that we make contributions toward narrowing the gap between the lower and upper bounds in existing work. Notably, our upper bound is smaller compared to [1]. More importantly, it also introduces a novel reflection of the communication graph through the presence of $\frac{1}{p}$ in the upper bound. Surprisingly, our newly added experiment ((ii), Table 2 in A3 for Q3 raised by reviewer bG2e) shows that the actual regret exhibits a dependency of $\frac{1}{p^{1}}$, which numerically validates the near-tightness of our upper bound. On the other hand, our lower bound improves upon existing work [4] by explicitly incorporating the sub-optimality gap.

We do sincerely agree that formally incorporating this communication-related dependency (e.g., via $p$ or $\lambda_{N-1}(\text{Lap}(\mathcal{G}))$) into the lower bound remains an important open direction. We hope our work could inspire future work on how to close the gap between upper and lower bounds in terms of graph-dependent terms.

Q3: Concerns about our methodological contribution

A3: The core contribution of our work lies in studying the multi-agent bandit problem under a general random communication graph, where each edge is independently active with probability $p\in(0,1]$. In contrast, prior works either assume strongly connected communication graphs at all times [2,3], or require the graph to be strongly connected with high probability at each round [1]. While [1] is the only work that explicitly incorporates the edge activation probability $p\ge 1/2+1/2\sqrt{1-(\epsilon/{NT})^{2/(N-1)}}$, which requires $p$ to be significantly large—approaching $1$ as $N$ or $T$ grows—and yields a regret bound ($O\left(\sum_{k:\Delta_k>0}\Delta_k^{-1}\log(T)+KN\log(T)\right)$ in [1]) that is worse than ours ($O\left(\sum_{k:\Delta_k>0}\Delta_k^{-1}N\log(T)\right)$ in ours) by a factor of $N$.

In our novel and more general setting, our proposed algorithm (GSE) introduces several key methodological innovations compared to prior work. These include a new algorithmic framework based on arm elimination, refined weight matrix for gossip, and a carefully designed confidence interval that accounts for both estimation and consensus errors. Each of these components is tailored to the challenges of heterogeneous MA-MAB with random communication and plays a critical role in achieving stronger theoretical guarantees under minimal connectivity assumptions.

Algorithmically, we introduce them as follows:

(i) Algorithm framework: From the perspective of algorithmic protocol, our method adopts a arm elimination framework, whereas prior works in this literature primarily rely on UCB-style algorithms [1,2,3]. While arm elimination is not new, it is particularly well-suited to the heterogeneous MA-MAB setting. In this setting, each agent only observes local rewards, while the goal is to minimize cumulative global regret. To ensure the global estimate—obtained via gossip averaging—is unbiased and not overly influenced by individual agents’ feedback, it is important that all agents pull each arm a comparable number of times. Arm elimination naturally enforces such balance, as shown in Lemma B.4, which bounds pull count differences across agents. In contrast, UCB-based gossip algorithms need to prioritize under-sampled arms, requiring complex detection mechanisms and making them harder to implement and analyze under heterogeneous feedback. Our approach provides a simpler and more robust solution tailored for this setting.

(ii) Refined weight matrix: The design of the weight matrix $W_t$ is another key aspect of our algorithm’s novelty. As defined in Eq.(2), we construct $W_t$ using the Laplacian matrix, which ensures that the weight matrices are independent and identically distributed (i.i.d.) across rounds. This property is essential for satisfying the conditions in Lemma B.3, enabling us to rigorously show that information from different agents becomes sufficiently balanced over time. As a result, the local estimates $z_{i,k}(t)$ on each agent converge to the true global mean reward $\mu_k$ as the number of rounds increases.

(iii) Confidence interval design: Furthermore, we propose a novel confidence interval (Eq.~(4)) that captures both estimation error and consensus error, which is critical under the stochastic communication graph and heterogeneous reward model. Specifically, the estimation error term $\sqrt\frac{4\log(T)}{N\max(T\_{i,k}(t)-KL^\*,1)}$ accounts for the statistical variance due to finite sampling, while the consensus error term $\frac{4(\sqrt{N}+\tau^*)}{\max(T_{i,k}(t)-KL^\*,1)}$ reflects the additional approximation error incurred due to time-delayed information propagation through the gossip protocol under a random graph. To our knowledge, this is the first formulation of a confidence bound that explicitly captures this two-fold structure in the heterogeneous MA-MAB setting.

Analytically, we introduce the following contribution.

Moreover, the analysis and theoretical results of our algorithm form a central—and arguably the most crucial—part of our contribution. In Theorem 5.3, we establish an upper bound on the global regret for the heterogeneous MA-MAB problem under random graph communication. The first term in the bound, $O\left(\sum_{k:\Delta_k>0}\frac{\log T}{\Delta_k} \right)$, reflects the estimation error originating from limited samples and matches the theoretical lower bound in Theorem 5.9, confirming its optimality. The second and third terms, $O\left( \frac{N^2\log T}{p\lambda_{N-1}(\text{Lap}(\mathcal{G}))}+\frac{KN^2\log(NT)}{p} \right)$, stem from consensus errors and reveal the regret’s dependence on key graph parameters, including connection probability $p$ and algebraic connectivity $\lambda_{N-1}(\text{Lap}(\mathcal{G}))$. As the first work to consider MA-MAB with general random graphs where each edge appears independently with arbitrary probability $p \in (0,1]$, we also provide the first regret bounds that explicitly reflect these structural dependencies. Remark 5.6 highlights the inherent trade-off between communication frequency and regret. As previously discussed, this trade-off is fundamental: for example, in a cycle graph with edge appearance probability $p$, information may require $O(N/p)$ rounds to propagate (similar philosophy as suggested by the reward delay in [6]). Since each agent must access global information to achieve optimality, this implies a fundamental regret lower bound of $O(N^2/p)$. Finally, as shown in Remark 5.5, our results generalize existing works as special cases (e.g., fixed or strongly connected graphs), underscoring the broad applicability of our framework.

Together, these innovations enable us to systematically address both reward heterogeneity and random graph communication—an unexplored combination in prior work.

[1] Mengfan Xu, and Diego Klabjan. Decentralized randomly distributed multi-agent multi-armed bandit with heterogeneous rewards. Advances in Neural Information Processing Systems, 2023.

[2] Zhaowei Zhu, Jingxuan Zhu, Ji Liu, and Yang Liu. Federated bandit: A gossiping approach. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 2021.

[3] Jingxuan Zhu, and Ji Liu. Distributed multiarmed bandits. IEEE Transactions on Automatic Control, 2023.

[4] Mengfan Xu, and Diego Klabjan. Multi-agent multi-armed bandit regret complexity and optimality. The 28th International Conference on Artificial Intelligence and Statistics, 2025.

[5] David Martínez-Rubio, Varun Kanade, and Patrick Rebeschini. Decentralized cooperative stochastic bandits. Advances in Neural Information Processing Systems, 2019.

[6] Tal Lancewicki, Shahar Segal, Tomer Koren, Yishay Mansour. Stochastic multi-armed bandits with unrestricted delay distributions. In International Conference on Machine Learning, 2021.

Thank you for your feedback and hope our responses address your concerns. If this is the case, we would appreciate it if you can reconsider your score.

Q1: Position of the conclusion and future work

A1: Thank you for pointing that out. We will reorganize the paper and move the conclusion and future work section to the main body as the final section in the revised version.

Q2: Motivation of global optimality.

A2: Thank you for this suggestion. In many real‐world applications, global rather than local optimality is the true objective. For instance, a company with multiple branches may face region‐specific demands: a policy that maximizes one branch’s profit could inadvertently harm others. To avoid such "local bias", each branch must choose a policy that maximizes the aggregate reward across all branches.

Motivated by the real-world applications, we model this problem as $N$ agents seeking to maximise the global reward, as the sum of each agent’s expected reward. If each agent only optimizes its own local bandit, these local biases can cause the global regret to grow linearly in $T$ (as illustrated in [1], where linear regret is shown to be unavoidable if the graph is disconnected, preventing optimization toward global optimality). By contrast, our GSE algorithm is designed to minimise this global regret. As established in Lemma 5.2 and Theorem 5.3, both the per‐agent and total global regret under GSE converge at a logarithmic rate, demonstrating that GSE indeed achieves true global optimality rather than merely local gains.

Q3: Additional experiments

A3: Based on the suggestions, we conduct additional experiments as follows. For each experiment, we run the algorithm for 20 times and report the average performance.

(i) To further investigate the regret’s dependence on the time horizon $T$, we report in Table 1 the final cumulative regret of GSE and DrFed-UCB across a range of $T$ values. The results show that GSE scales much more slowly with $T$ compared to DrFed-UCB, aligning with our theoretical tighter upper bound. This experiment confirms the favorable scaling behavior of GSE and supports the tightness of our regret analysis.

Table 1: Regret of GSE vs. DrFed-UCB for varying T with classical ER graph and p=0.9.

(ii) To better understand the dependence of the regret on the link probability $p$, we conduct additional experiments on complete base graphs with small values of $p\in[0.04, 0.18]$, and report the log–log relationship between $p$ and the resulting regret. The results are shown in the Table 2. By performing a linear regression between $\log(p)$ and $\log(\text{Regret})$, we obtain a slope $\hat\alpha = -0.93$ with $R^2 = 1.0$, indicating a nearly perfect linear fit (of order $\frac{1}{p^{0.93}}$). Surprisingly, we also report the $R^2$ corresponding to the curve of fit $\frac{1}{p}$, and find out that $R^2$ is $0.995$, which represents that the curve fit is quite statistically significant and thus a perfect linear fit. This strongly supports the inverse proportionality between regret and $p$, i.e., regret scales approximately as $O(1/p)$, which is consistent with our theoretical upper bound. This result empirically also validates that smaller $p$ leads to significantly higher regret due to slower information diffusion across agents.

Table 2: Log–log data for GSE: $\log(p)$ and $\log(\mathrm{Regret})$ with classical ER graph, p=0.9)

Fit allowing slope free

Fit with fixed slope = –1

(iii) To empirically investigate the dependence of regret on the spectral gap of the base graph, we conduct experiments using $d$-regular graphs with varying degrees $d$. Specifically, we construct the base graphs as circulant graphs. This structure provides a controllable family of regular graphs with increasing algebraic connectivity as $d$ grows. We run our algorithm GSE under this setting with the link probability $p = 0.9$. Table 3 shows a clear inverse relationship: as $\lambda_{N-1}$ increases with higher $d$, the regret decreases significantly. This supports our theoretical findings that larger algebra connectivity leads to more efficient information propagation and thus lower regret.

Table 3: Average regret of GSE with d-regular graph

Q4: Regarding the tightness of bounds and possibility to include communication cost of graph in lower bound

A4: Thank you for the insightful question. In our paper, we provide a theoretical regret upper bound in Theorem 5.3 and a corresponding lower bound in Theorem 5.9. The first term in the upper bound, which captures the centralized regret due to the statistical uncertainty from limited samples, matches the lower bound, indicating that this term is tight and optimal. The remaining two terms in the upper bound arise from delays in information propagation due to random communication, and these are not yet matched by a lower bound.

To gain intuition on the potential tightness of these communication-related terms, consider a simple cycle graph where each edge is activated independently with probability $p$ at each round. On average, it would take $O(N/p)$ rounds for information from one agent to reach all the other agents (can be viewed as reward delay in [3]). Since agents are optimizing for global rewards, one agent must wait to receive information from all others to make informed decisions. This implies that each agent may need $O(N/p)$ rounds to effectively optimize its local policy with respect to the global objective. Summing across all $N$ agents gives a global regret contribution of at least $O(N^2/p)$, which intuitively explains the dependency on $p$ and $N$ in the graph-dependent terms in our upper bound. This argument provides heuristic evidence for partial tightness of our bound with respect to communication regret.

We would also like to add that we make contributions toward narrowing the gap between the lower and upper bounds in existing work. Notably, our upper bound is smaller compared to [2]. More importantly, it also introduces a novel reflection of the communication graph through the presence of $\frac{1}{p}$ in the upper bound. Empirically, Table 2 in A3 shows that the actual regret exhibits a dependency of $\frac{1}{p}$, which numerically validates the near-tightness of our upper bound. On the other hand, our lower bound improves upon existing work [1] by explicitly incorporating the sub-optimality gap. We acknowledge that a formal lower bound capturing communication costs—especially for specific topologies such as trees or cycles—remains open and is an important direction for future work.

Q5: Regarding the necessity of $K$ in Lemma B.4

A5: We thank the reviewer for this insightful comment. Indeed, under our round‐robin protocol, the “waves” for different arms proceed in parallel, so we can refine the disagreement‐length bound as follows. At any time $t$, if $|\mathcal S_i(t)|=m$, each wave lasts at most $\left\lceil \frac{N L_p(\delta)}{m} \right\rceil$ rounds for agent $i$. Since $|\mathcal S_i(t)|$ decreases by at least one each time a wave completes, the total number of disagreement rounds is bounded by $\sum_{m=1}^K \left\lceil \frac{N L_p(\delta)}{m} \right\rceil=NL_p(\delta)\sum_{m=1}^K \frac{1}{m} + O(K) =NL_p(\delta)(H_K + O(1)),$ where $H_K=\sum_{m=1}^K 1/m=O(\log K)$. Consequently, the right‐hand side of Lemma B.4 can be improved toO(NL_p(\delta)\log K).$ We appreciate the suggestion and will incorporate this tighter bound and its detailed proof in the revised version of the paper.

Q6: The derivation of Eq.(14) (line 531-532)

A6: The second equality holds because of the definition of $z_{i, k}(t)$ and the doubly stochasticity of the matrix of $W_t$.

References

[1] Mengfan Xu, and Diego Klabjan. Multi-agent multi-armed bandit regret complexity and optimality. In International Conference on Artificial Intelligence and Statistics, 2025.

[2] Mengfan Xu, and Diego Klabjan. Decentralized randomly distributed multi-agent multi-armed bandit with heterogeneous rewards. Advances in Neural Information Processing Systems, 2023.

[3] Tal Lancewicki, Shahar Segal, Tomer Koren, Yishay Mansour. Stochastic multi-armed bandits with unrestricted delay distributions. In International Conference on Machine Learning, 2021.