We thank the reviewer for their highly positive review. We're happy to address any questions the reviewer might have during the author-reviewer discussion. If we have resolved the reviewer's concerns, we would appreciate it if they could consider raising their scores.

"Although this is not a weakness of the result itself, I feel that, in order to make the paper self contained, there should be some explanation of how SE works before we jump into the description of Coop-SE as the explanation of the latter assumes familiarity with the former."

We will certainly include this in the final version.

Questions

”In Line 149 you say that the agent observes a reward but you don’t say that the reward is drawn from the SMAB distribution.”

”You have some small brackets in Theorem 2 which should be big brackets. Same for Line 194.”

”Typo in definition 10 - begging instead of beginning”

Thank you for the suggestions. We will address all of them in the final version.

Thank you for your comments. We hope to have addressed all your comments in the rebuttal below, and would be happy to continue discussing this with you during the author-reviewer discussion period. If you find our answers appropriate and satisfactory, we would be grateful if you would consider raising your score.

Weaknesses

“The reason why I don't give a higher score is that this paper does not give any algorithmic contribution and the analysis, though careful, seem not to be applicable to broader cases (i.e., applying to UCB or TS algorithm, but the current analysis only works for elimination algorithms)”

Q1: “Can authors discuss more why the current method does not work for UCB?”

We will answer the weakness and the question together.

The algorithm we introduced, Coop-SE, is new since it is not just SE with message passing, but in our implementation each agent eliminates what other agents have eliminated according to their observations (up to the delay) as well as what the agent observed and calculated. This is a critical modification, which makes it possible to align the policies.

Without this modification, an agent might not eliminate a sub-optimal action, even if other agents eliminated it. In such a case, that agent will continue sampling this sub-optimal action alone and might incur high individual regret in this scenario.

In Coop-SE, we eliminate this action due to the elimination messages from the other agents. This algorithmic change is crucial in our analysis of individual regret.

The following is a discussion of the challenges of achieving individual regret using UCB.

In UCB there is no guarantee regarding the order in which the agent explores. The UCB algorithm analysis bounds the number of rounds in which the sub-optimal actions are chosen.

In the multi-player setting, if we only bound the number of times the sub-optimal actions are played, this is not sufficient to guarantee that the following scenario will not happen. It could be that many agents played the best action in many rounds. They enjoy extremely low individual regret, but these agents didn’t contribute to the exploration of sub-optimal actions. On the other hand, a few agents that played the sub optimal actions can play them many times. Hence, in such a scenario we have high individual regret, yet small group regret.

If one wants to use UCB and achieve individual regret, one must show that the individual exploration of different agents is similar. Alternatively, one can use a reduction to a complete graph. In a reduction to a complete graph, one introduces a delay of $D$, which is added to the regret.

“Can author mention a paper in the stochastic setting that have low group regret, but individual regret is large?”

To see the main difference between group regret and individual regret, note that when we have $m=T$ agents, we can take any agent and let it play randomly, and this increases the group regret by only $1$. This simple example shows the challenges in establishing a general transformation from group regret to individual regret.

From a theoretical perspective, it is highly challenging to show individual regret and somewhat easier to prove group regret. As a concrete example, UCB-like algorithms are highly challenging for providing individual regret guarantees, although they have been shown to achieve good group regret.

Thank you for your comments. We hope to have addressed all your comments in the rebuttal below, and would be happy to continue discussing this with you during the author-reviewer discussion period. If you find our answers appropriate and satisfactory, we would be grateful if you would consider raising your score.

Weaknesses

”...I am not fully convinced of its practical value because of the presence of a $O(\sqrt{\log(T)})$-dependent term. As $T$ grows, this term can dominate, potentially nullifying the advantage of removing diameter dependence...”

We emphasize that the main focus of our paper is theoretical. We would like to understand the inherent regret bound and its dependence on the various parameters of the problem. Previous works had an additive term of $D$, the diameter of the graph. We highlight that one needs to think of the diameter $D$ as a function of $m$, the number of nodes in the graph, which is also the number of agents. An interesting communication network is a grid graph where $D=\sqrt{m}$. Since the ideal regret would be at least $\mathcal{R} / m$, if we aim for low regret, the number of agents $m$ should be a function of $T$. This implies that $D$ is also a function of $T$ (indirectly, through $m$). Hence, the dependency on $D$ hides a dependency on $T$, which is potentially polynomial for small gaps.

About the actual parameters, even in the extreme case that $T=10^{50}$, the number of atoms on Earth, our bound is very reasonable, since $\sqrt{\log(T)} < 11$. Having a diameter more than 11 is definitely reasonable in many cases. We stress again that our focus is theoretical, and this numerical example is only to highlight why in many cases the main term would be $D$.

As discussed in Section 1.1, one can see that small sub-optimality gaps ($\Delta \approx 1/\sqrt{T}$) may contribute a lot to the regret. If the regret bound depends on the diameter, one remains with a polynomial dependency on $T$ (for example, $T^{1/6}$ for a grid graph), and increasing the number of agents will not help. But with the bounds from Coop-SE, for a sufficiently large number of agents, one remains with only $A^2+A\sqrt{\log(T)}$ regret.

”...It remains unclear whether the $T$-dependence in the additive term is truly necessary, or whether a tighter, $T$-independent bound might be achievable.”

Let us give an intuition about the $\log(T)$ and $\sqrt{\log(T)}$ in the additive terms. The $\log(T)$ terms (or $\sqrt{\log(T)}$) are there to ensure high-probability concentration bounds. Since we need the concentration bound to hold simultaneously for any agent, action and time step, we have an actual $\sqrt{log(mAT)}$ term.

The additive $\sqrt{\log(mAT)}$ term arises in cases where the number of agents is large compared to the stage length. In sparse graphs like the line graph, even with many agents, only $O(t^2)$ samples can be collected by time $t$. This leads to a $\sqrt{\log(mAT)}$ term from concentration bounds. See line 977 in the appendix.

To summarize, these logarithmic terms are due to the concentration bounds, which we require for our analysis. The tightness of the lower bound remains an open question, as we mention in lines 201-202.

"While the treatment of limited communication settings in Sections 7 and 8 is valuable and introduces novel ideas, I believe addressing the substantial gap in all of the regret bounds is a more pressing issue.”

We agree that achieving an algorithm that gives the best possible regret bound would be a substantial contribution, however, we feel that we made significant progress in that direction. It is still an open question whether the lower bound of $\sqrt{A}$ is indeed the tightest, and we mention this open problem in the paper (lines 201-202 and in Appendix A lines 818-819).

”This gap makes the overall theoretical contribution feel somewhat incomplete.”

The main contribution of the paper is a simple algorithm, and an analysis that shows that this algorithm achieves $\mathcal{R}/m + A^2 + A\sqrt{\log(T)}$ individual regret for any graph. Other methods depend on the diameter $D$. As we mentioned before, the diameter naturally depends on the size of the graph, $m$, the number of agents. The number of agents is a function of $T$, if we aim to achieve low regret. Please see Section 1.1 for more explanation of why in some natural cases, those methods yield $T^c$ regret, for $c>0$.

”Furthermore, the regret bound for Coop-SE-Comm-Cost includes a larger additive term of $O(A\log T)$, which—aside from being independent of the gaps—effectively offsets the cooperative benefit of the $O(1/m)$ term by dominating it for large $T$.”

We discussed before the relationship between $A\sqrt{\log(T)}$ and the diameter $D$. An additional issue that one needs to consider is the sub-optimality gaps. The gaps are parameters that may contribute substantially to the regret. The benefit of $O(1/m)$ still has a high impact, since the gaps might contribute $\sqrt{T}$ regret, as explained in Section 1.1. The $(1/m)$ term overcomes this potentially large $\sqrt{T}$ regret.

”As previously noted, this work does not include any experimental evaluation...”

This work's main focus is theoretical and therefore does not include experiments.

Other concerns

We thank the reviewer for their suggestions. We will correct the typos and inconsistencies. For completeness, Theorem 4 should be stated as: $O(\mathcal{R}/m + A\sqrt{\log(mAT)} + A^2)$, and Theorem 5 as: $O(\mathcal{R}\log(A)/m + A\log(A)\log(mAT))$.

Questions

Q1 “...could the authors clarify how their algorithms are expected to perform on a fixed problem instance as a function of $T$? Specifically, do the proposed methods offer practical advantages over existing algorithms in such settings?”

Other methods suffer from a regret of at least $D$, where $D$ is the diameter of the graph. This holds independently from the number of agents. Our algorithm offers a much better regret.

Here is how we expect our algorithm to work on a cycle graph with sufficiently many agents. An agent at time $t$ will receive about $t^2$ samples. This implies that it will be able to discard a sub-optimal action $i$ after roughly $\log (T) / \Delta_i$ rounds, in contrast to the single-agent setting where the elimination occurs only after $\log (T) / \Delta_i^2$ . Note that this time can be much smaller than the diameter $D$, and this is the main advantage of our algorithms and analysis. An important aspect of the algorithm is that agents send the actions they discarded, and therefore guarantee that the agents have similar policies.

A more detailed comparison with other methods: In UCB there is no guarantee regarding the order in which the agent explores. The UCB algorithm analysis bounds the number of rounds the sub-optimal actions are chosen.

In the multi-player setting, if we only bound the number of times the sub-optimal actions are played, this is not sufficient to guarantee that the following scenario will not happen. It could be that many agents played the best action in many rounds. They enjoy extremely low individual regret, but these agents didn’t contribute to the exploration of sub optimal actions. On the other hand, a few agents that played the sub optimal actions can play them many times. Hence, in such a scenario we have high individual regret, yet small group regret.

If one wants to use UCB and achieve individual regret, one must show that the individual exploration of different agents is similar. Alternatively, one can use a reduction to a complete graph, as mentioned in Wang et al. [1]. In a reduction to a complete graph, one introduces a delay of $D$, which is added to the regret.

Wang et al. [1] use a version of UCB and give a precise analysis for the complete graph with extremely low communication. To address a general graph, they give a general reduction. Their reduction implicitly assumes that all agents’ policies are the same (as far as we understand). The reviewer may look at Wang et al. [1], section G.2: “the algorithm solves a problem equivalent to a CMA2B with communication delay D on a complete graph”. (CMA2B is an abbreviation of “Cooperative multi-agent multi-armed bandits”, and $D$ is the diameter). The reduction to a complete graph requires delay of $D$ which is added to the regret.

Coop-SE does not depend on the diameter $D$, and enjoys better regret.

Q2 ”Could the authors provide an intuitive explanation for the emergence of the $O(\sqrt{\log(T)})$ and $O(\log(T))$ terms in the regret upper bounds? ... Additionally, have any attempts been made to reduce or eliminate this $T$-dependence…?”

As we mentioned before, the $\sqrt{\log(T)}$ and the $\log(T)$ terms in the additive term are due to the use of concentration bounds, which are required for our analysis. The reviewer may refer to our answer to a previous comment they made.

Q3 “How much global knowledge about the communication graph is assumed or required from the agents during these phases? Additionally, could the authors clarify how regret is accounted for during these preprocessing steps?”

Since we assume the agents have common knowledge of the communication graph, the spanning tree is also part of it, and all the agents know it in advance.

Constructing a spanning tree in a distributed way has been studied in the communication networks community; see Peleg [2].

Constructing the spanning tree in an online fashion while maintaining low regret under communication constraints remains an open question that is beyond the scope of this paper.

[1] Wang, Xuchuang, and Lin Yang. "Achieving near-optimal individual regret low communications in multi-agent bandits." The Eleventh International Conference on Learning Representations (ICLR). 2023.

[2] Peleg, David. “Distributed computing: a locality-sensitive approach”. SIAM, 2000.

Thank you for your comments. We hope to have addressed all your comments in the rebuttal below, and would be happy to continue discussing this with you during the author-reviewer discussion period. If you find our answers appropriate and satisfactory, we would be grateful if you would consider raising your score.

W1: “Although concretely new progress on the direction of multi-agent MAB, the reviewer thinks that the result in this paper is not very significant (even the authors did a good job in the discussion in S1.1). The main improvement of this paper is from $D$ to $\min \{A+\sqrt{\log(T)},D\}$, where the latter can remove the dependence of $D$ when the graph has a large diameter. However, (1) the $O(\sqrt{log(T)})$ term is still relatively large since the time horizon $T$ in the bandit setting is typically the largest constant. (2) The improvement only happens when the graph has a large diameter (larger than $\sqrt{\log(T)}$!).”

We emphasize that the main focus of our paper is theoretical. We would like to understand the inherent regret bound and its dependency on the various parameters of the problem.

Previous works had an additive term of $D$, the diameter of the graph. We highlight that one needs to think of the diameter $D$ as a function of $m$, the number of nodes in the graph, which is also the number of agents. An interesting communication network is a grid graph where $D=\sqrt{m}$. Since the ideal regret would be at least $\mathcal{R} / m$, if we aim for low regret, the number of agents $m$ should be a function of $T$. This implies that $D$ is also a function of $T$ (indirectly, through $m$). Hence, the dependency on $D$ hides a dependency on $T$, which is potentially polynomial for small gaps.

Regarding the actual parameters, even in the extreme case that $T=10^{50}$, the number of atoms on Earth, our bound is very reasonable, since $\sqrt{\log(T)} < 11$. Having a diameter greater than $11$ is definitely reasonable in many cases. We stress again that our focus is theoretical, and this numerical example is only to highlight why in many cases the main term would be $D$.

As discussed in Section 1.1, one can see that small sub-optimality gaps ($\Delta \approx 1/\sqrt{T}$) may contribute a lot to the regret. If the regret bound depends on the diameter, one remains with a polynomial dependency on $T$ (for example, $T^{1/6}$ for a grid graph), and increasing the number of agents will not help. But with the bounds from Coop-SE, for a sufficiently large number of agents, one remains with only $A^2+A\sqrt{\log(T)}$ individual regret.

W2: “The current results are not tight. The upper bound $O(A^2)$ has a large gap in comparison with the $\Omega(\sqrt A)$ lower bound.”

Regarding the gap in the additive term between the lower bound and the upper bound, the reviewer may find it interesting that when the played action is selected randomly from the set of active actions, we get $\mathcal{R}/m + A \log(mAT)$ (instead of the $\mathcal{R}/m + A^2 + A\sqrt{\log(mAT)}$ with round-robin).

It is still an open question whether the lower bound of $\sqrt{A}$ is indeed the tightest, and we mention it in the future work section (lines 201-202 and in Appendix A, lines 818-819).

W3: “Although the analysis is new, the Coop-SE algorithm has been proposed multiple times in various prior works (as the authors are also aware). It would be better to posit the contribution of this work on the analysis side and attribute the merit of the Coop-SE algorithm design to these prior works (e.g., remove “ours” after Coop-SE in Table 1).”

We will emphasize in the final version that SE with message passing in the cooperative setting is not a new algorithm.

The algorithm we introduced, Coop-SE, is new since it is not just SE with message passing, but in our implementation each agent eliminates what other agents eliminated according to their observations (with elimination messages), as well as what the agent observed and calculated. This is a critical modification, which makes it possible to align the policies of the different agents.

Without this modification, an agent might not eliminate a sub-optimal action, even if other agents eliminated it. In such a case, such an agent will continue sampling this sub-optimal action alone and might incur high individual regret in this scenario.

In Coop-SE, we eliminate this action due to the elimination messages from other agents. This algorithmic change is crucial in our analysis for the individual regret.

Questions

”Line 37: why omit the $\log(T)$ regret term here? It dominates the $\sqrt{\log(T)}$ term.”

We omitted the $\log(T)$ term since for a large number of agents this term vanishes.

”Line 65: the $\mathcal{R}$ still dependent on the gaps.”

Thank you, we will change this.

”Line 67: It would be better to present the upper bound in minimax form here as well.”

Yes, we agree, and we will present both bounds in the minimax form.

”Line 74—79: the open problem can be addressed by other prior works mentioned in the related work section, why emphasizes it here? Is there a special insight of the current work on the problem?”

We will definitely add a discussion regarding this point. We acknowledge that this question has been addressed by prior works. While our contribution lies in analyzing individual regret independent of the graph’s diameter, we will explicitly state in the final version that prior works have also contributed to this specific question.

”The communication round of TCOM should be additive $D$ instead of multiplicative $D$.”

Thanks, we will change this.

The reviewer thanks the authors for their responses.

Coop-SE with both message passing and eliminated arm signal is already a common technique in the literature.

See Algorithm 2 of "Yang, Lin, et al. "Distributed bandits with heterogeneous agents." IEEE INFOCOM 2022-IEEE Conference on Computer Communications. IEEE, 2022." and papers cited it.

Thank you for your comments. We hope to have addressed all your comments in the rebuttal below, and will be happy to continue discussing this with you during the author-reviewer discussion period.

“the presented results still do not provide a clear idea as to what extent the structure of the graph can be exploited”

We will emphasize in the final version that leveraging the graph structure can potentially reduce the additive term in the regret. For instance, in the case of a complete graph, the regret can be as low as $\mathcal{R}/m$, and if $m > \mathcal{R}$ the regret is constant. An interesting open problem is to characterize the dependencies of the regret on the graph’s structure. We will add it to the Future Work section.

Our goal is to derive graph-independent regret bounds and to give regret bounds that hold for any graph. As you remark, the only potential gains are in the dependency of the additive term, which is already rather insignificant compared to the regular single-agent regret.

”Some minor points concerning the introduction; it does not seem that the additive terms in Theorems 4 and 5 are exactly as reported in Section 1.2 and Table 1”

Thank you for noticing the mismatch between Theorems 4 and 5 and to the statements elsewhere. We will fix this. Theorem 4 should be: $O(\mathcal{R}/m + A\sqrt{\log(mAT)} + A^2)$, and Theorem 5 should be: $O(\mathcal{R}\log(A)/m + A\log(A)\log(mAT))$.

”moreover, in lines 91-93, it seems that the argument should be that $h(\mathcal{G})$ can increase (potentially up to $m$) if $\lambda_2$ is close to $1$, not $0$.

It indeed should be “The eigenvalue … can be very close to one for some graphs” (not to zero). Thanks again.

Questions

”Concerning the additive term, do you believe that the shortcoming is in the upper bound? If so, could this be a limitation of the successive elimination algorithm? Could it be a limitation of only using local graph information?”

We believe that this is an artifact of the analysis rather than of the algorithm. The additive $A$ term arises in part because we treat each stage as having a length of at least $1$, which leads to a regret of at least $A$. However, potentially, multiple stages may have length $0$. Unfortunately, we were unable to refine our analysis to account for this. When the agents are completely connected (there is no issue of local graph information), i.e., the graph is a complete graph, the additive term is eliminated with our algorithm.