Thank you for reviewing the responses and for sharing the valuable suggestions and references. We will incorporate the discussions and references [5, 6] into the paper and benchmarks, as elaborated in the following paragraphs verbatim. The works [5, 6], in addition to establishing the elegant algorithms and optimal regret bounds that explicitly characterize the dependency of regret bounds on the conductance of the graph, also pave the way for integrating communication efficiency and privacy guarantee optimization into our settings with random graphs and heterogeneous rewards. The characterization of the trade-off between regret and communication cost in the regret bound theoretically demonstrates the improvement resulting from replacing ring graphs with complete graphs. The techniques include asynchronous communication protocols and communication cost optimization, in line with both federated learning (the number of transmitted estimators is $O(M)$ or $\log (MK)$, instead of the common $O(MK)$) and decentralized multi-agent MAB (the number of communication rounds having a budget of $O(\log T)$ or $o(T)$, instead of $O(T)$). We appreciate the references and have added them to the communication efficiency discussion that is also suggested by reviewer a3u4 and reviewer H8V9. In the meantime, transmitting arm selections, rather than reward estimators based on historical arm pulls, significantly enhances client privacy.
Modifications to Introduction
Line 47: In the field of decentralized multi-agent MAB, it is commonly assumed that the mean reward value of an arm for different clients is the same, or equivalently, homogeneous. This assumption can be seen in works such as [..., 3, 5, 6].
Line 66: Besides rewards, the underlying graph assumptions are essential to the decentralized multi-agent MAB problem, as increased communication among clients leads to better identification of global optimal arms and smaller regret. The existing works [5, 6] relate regret with graph structures and characterize the dependency of regret on the graph complexity with respect to conductance. When considering two special cases, [6] demonstrates the theoretical improvement achieved by circular ring graphs compared to complete graphs, and [3] numerically shows that the circular ring graph presents the most challenging scenario with the largest regret, while the complete graph is the simplest.
Modifications to Remark (Specification of the parameters)
Line 335: We observe that the regret bound is dependent on the transition kernel $\pi$ and the spectral gap $\lambda$ of the underlying Markov chain associated with $\pi$. This indicates the significance of graph complexities and distributions within the framework of the random graph model when deriving the regret bounds, in a similar manner as the role of graph conductance in the regret bounds established in [5, 6] for time-invariant graphs.
Modifications to our experimental details
Models and benchmarks: We will implement the proposed algorithms. In term of heavy-tailed rewards, we will consider [1]
as the benchmark, since the work assumes heavy-tailed rewards and deterministic graphs in the analysis, and additionally it conducts experiments with a fixed E-R model. Meanwhile, we will also compare the new method with [2] which focuses on deterministic graphs and sub-gaussian rewards and motivates our work. We will also include [5, 6] as benchmarks, where the regret bounds in [5, 6] fully characterize the dependencies on the sub-optimality gap and the graph complexity in terms of conductance. These works and [3] also consider communication efficiency and privacy, and the experiments will also cover complete graph scenarios.
Variables in the settings: We will explore various settings to analyze the tightness of the regret bounds' dependencies on a range of factors. These factors include the degree of setting heterogeneity ($h$), the distributions of graphs with different complexities ($f$), the number of clients ($M$), the number of arms ($K$), and the reward distributions ($\sigma^2$, $\mu$, and $s$), where $s$ denotes whether the distribution is light-tailed or heavy-tailed.
Evaluation:
The evaluation metric will be the regret measure as defined in the paper. We will also include the communication cost as another performance measure, which is thoroughly considered in [3, 5, 6], based on the reviewers' suggestions and existing literature. This will help us understand the trade-off between regret and communication cost under different models. Meanwhile, the privacy guarantee will also be regarded as an evaluation metric, as optimized in [5, 6], following the privacy measure defined in [3] or a newly defined measure. Additionally, runtime can provide insights into the time complexity of the models.
[5] Sankararaman et.al. Social Learning in Multi Armed Bandits, SIGMETRICS 2019
[6] Chawla et.al. The Gossiping Insert-Eliminate Algorithm for multi-agent Bandits, AISTATS 2020