Communication-Efficient Algorithm for Asynchronous Multi-Agent Bandits

Reviewer: Number of agents: in the experiments, the number of agents is lower than the number of arms.

Answer: In Figure 7 in Appendix D of the revised manuscript, we report additional experiments where the number of agents is $M=30$ greater than the number of arms $K=16$. In these experiments, our algorithm outperforms other baseline algorithms in communication and enjoys similar regret as the other baselines, which is the same observation as in our original numerical simulations in Figure 1.

Reviewer: Communication cost: the reviewer is wondering why agents send an elimination message to other agents (line 7), while agents also send their estimates line 15.

Answer: The seemly redundant communications are due to the asynchronous decision rounds of agents and the small number of communications (constant communications in total). In synchronous cases, as all agents have the same number of decision rounds, sending reward mean estimates is enough. However, when it comes to this paper's asynchronous case, sending reward mean estimates (Line 15) is not enough. Without the elimination message to other agents (Line 7), some "fast" agents (high active frequency) may eliminate one arm much earlier than some "slow" agents: the number of reward observations of "fast" agents can be much larger than that of the "slow" ones, and the small number of communications achieved by our algorithm design can delay the observation sharing from "fast" agents to "slow" agents a lot. Therefore, the elimination message in Line 7 is important for reducing the regret cost due to "slow" agents (more general, due to asynchronicity) and thus is not redundant in an asynchronous setting.

Reviewer: Objective function: the authors wrote that the expectation in the expected regret (actually, the pseudo regret) is taken over the randomness of the algorithm and reward realizations. However, the reviewer did not find where there is randomness in Algorithm 1. So, there is no expectation in the second line of the pseudo regret R(T).

Answer: The mention of randomness in the expected regret definition is a standard approach to cover a wide range of algorithms, including probabilistic ones. Although Algorithm 1 is deterministic, this inclusion allows our analysis to remain applicable to other potential algorithms, such as those based on stochastic methods like Thompson sampling based ones.

Reviewer: Algorithm 1: the reviewer does not understand what lines 21-24 mean.

Answer: Lines 21-22 are the receiving counterpart for the message sent in Line 16 (by other agents $m'$), while Lines 23-24 are the receiving counterpart for the message sent in Line 15. Take the pair between Line 16 and Lines 21-22 as an example. Line 16 means that, when sending message from agent $m$ to agent $m'$, the agent $m$ sends the token $`tk`^{(m\to m')}$ to agent $m'$ as well. Lines 21-22 means that, when receiving a token $`tk`^{(m'\to m)}$ that was used to send a message from agent $m'$ to agent $m$, agent $m$ keeps this token. This pair constitutes the token receiving and sending protocol. We will add this explanation to the final version of this paper.

Reviewer: Model: the authors assume that there is only on best arm (\mu_1 > \mu_2 \geq …). This is a strong assumption that limits the scope of this study.

Answer: Assuming a single optimal arm is for the ease of presentation, which was widely assumed in literature (e.g., see Even-Dar et al. (2006, Section 2.1)). In the case of multiple optimal arms, tailoring our current algorithm could also work. In the original algorithm design, when only one arm remains in the candidate arm set (the optimal arm), the algorithm stops communication. When it comes to the case of multiple optimal arms, the above communication stop condition is invalid. Instead, one can set an exploration threshold, and when the number of times pulling the remaining arms in the candidate arm set exceeds this threshold, stop the communication. This threshold would guarantee that the total communications are still constant, as well as that the reward means of remaining arms are close enough to have a sublinear regret upper bound.

Even-Dar, Eyal, et al. "Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems." Journal of Machine Learning Research 7.6 (2006).

Reviewer: Proof of Theorem 2, step 3: the reviewer does not understand where the last equation page 17 comes from. Could you provide more details?

Answer: The last inequality comes from the last equation, where we substitute $1=`ECR`\_t^{(m)}(0)$ and take $\log_\alpha$ on both sides. Below, we illustrate how the last equation is derived, and we updated this proof detail in the revised version as well. We note that the estimated confidence radius $`ECR`\_k^{(m)}(T)$ should be written as the $`ECR`_k^{(m)}(\tau_k(\kappa_k))$ at the last communication round $\tau_k(\kappa_k)$ because after the last communication, the width of $`ECR`$ has no further impact on communication. \newline Recall that $\tau_k(t)$ is the latest communication round about arm $k$ on or before time slot $t$. Then, $`ECR`_k^{(m)}(\tau_k(\kappa_k))$ is the $`ECR`$ at the latest communication for arm $k$ which can be upper bounded as follows, $`ECR`_k^{(m)}(\tau_k(\kappa_k)) \overset{(a)}= `CR`(n_k(\tau_k(\kappa_k))) \ge `CR`(n_k (\kappa_k)) \ge \frac{\Delta_k}{2(1+\alpha)},$ where equality (a) is because $\tau_k(\kappa_k)$ is a communication time slot in which the estimated confidence radius ($`ECR`$) is equal to $`CR`$.

Reviewer: Proof of Lemma 1: equation (a1), M_t is not defined and misleading.

Answer: In inequality (a1), the upper bound of summation is $M\times t$, not $M_t$, where $M$ is the number of agents and $t$ is the current time index. In the revised, we updated it to $M\cdot t$ to avoid misunderstanding.

Reviewer: I can see that from Theorem 2, a smaller alpha yields smaller regret. I can also see that from Figure 1,2, the proposed method has a higher regret compared to UCB-IBC. Therefore, I'm interested in the question of when we use smaller to achieve similar $\alpha$ regret as UCB-IBC, will the number of communications of the proposed method still be much smaller?

Answer: We note that our algorithm only needs constant communications, which are far less than the linear communication cost of UCB-ICB; it is impossible for our algorithm to beat UCB-ICB in terms of regret metric. For another thing, there is indeed a trade-off of regret and communication in our algorithm ($`SE-AAC-ODC`$) in terms of the parameter $\alpha$. In Appendix D of the revised manuscript, we compare the performance of $`SE-AAC-ODC`$ with $\alpha=3$ and $\alpha=6$ in Figure 6. This simulation validates the trade-off---the case of $\alpha=3$ enjoys a better regret but suffers a higher communication. Additionally, the communications of both cases are much lower than that of other baseline algorithms.

Reviewer: I'm quite interested in the property of constant communication. By Theorem 2, the authors show that the regret bound is closely related to T, but the number of communications is independent of T. This means that communication between agents is not so important and even if there are only a few communications, smaller can still be achieved by using a large T. Can the authors intuitively explain the philosophy behind this property?

Answer: The high-level intuition is that an agent only needs to know which arm is optimal to achieve sublinear regret in multi-armed bandits, and the communication cost of sharing this information (an arm index) is independent of the total number of decision rounds. Therefore, if one fast agent (with a large number of active decision rounds) could somehow "smartly" find the optimal arm, then it only needs to pay a constant number of communications to disseminate the optimal arm index to all other agents.

Reviewer: Can the authors clarify what is indeed the most important measurement (time or communication) in the MA2B task? The authors explained that synchronous updates will lead to redundant communication (Section 3.1). This is reasonable, but what is the final purpose of saving communication? Is it to achieve a lower regret within a shorter time horizon? If time is the most important thing, then by Figure 1,2, the performance of the proposed method is not as good as UCB-IBC.

Answer: We acknowledge that this paper primarily delves into theoretical aspects, with the central focus on assessing the efficacy of communication cost reduction while maintaining near-optimal $O(K\log T)$ regret, referred to as "time" in the reviewer's question. It is essential to clarify that the primary goal is not to minimize regret further, as prior works, including our own, have already achieved near-optimal regret levels. While empirical results indicate that the proposed algorithm's regret may not match that of UCB-IBC, it is noteworthy that both UCB-IBC and our algorithm attain the same $O(K\log T)$ regret level.

Reviewer: Although the order of the regret bound of the proposed algorithm (see Remark 3) is the same as the optimal bound, the constant term before the order can be quite large. For example, when setting $\alpha=6$ as used in the experiments, the constant can be as large as 392, which is a very large number. I suggest the authors provide the regret bound (not only the order) of alternative methods and compare them. It will also be better to plot the regret bounds and the communication complexity bounds of the proposed method and alternative methods.

Answer: The leading term coefficients of $`SE-ODC`$ and SE-IBC in our experiment setting are $24$, which is better than the $392$ factor in our $`SE-AAC-ODC`$ algorithm. For one thing, we note that the larger constant coefficient of our regret upper bound comes from a more involved regret analysis for our constant communication result. This implies the challenge and novelty of our new algorithm. For another thing, in our experiments, e.g., Figure 1(b), our algorithm with only constant communication has a better regret performance than that of $`SE-ODC`$ with logarithmic communication. That implies although there is a larger artificial factor in our regret upper bound result, the empirical regret performance of our algorithm is better (even with lower communications).

Reviewer: Can the authors also provide a lower bound on the communication cost of the asynchronous multi-agent MAB model considered in this paper?

Answer: Providing a non-trivial lower bound for communication in asynchronous multi-agent MAB settings is highly challenging and remains an open problem in the literature. This is because some extremely asynchronous scenarios could make communication unnecessary. For example, consider the case that one agent is active in all time slots, while all other agents are only active in one single time slot. In this case, there is no need to conduct communication among these agents, that is, one can achieve near-optimal regret by all agents individually running UCB without any communication.

On the other hand, the only related communication lower bound results that we are aware of is in Wang et al. (2020, Section 3.4), where they show that to achieve a $o(M\sqrt{KT})$ regret upper bound in synchronous multi-agent MAB, the expected communication is at least $\Omega(M)$. If we exclude the extreme cases and only consider mildly asynchronous scenarios, then the $\Omega(M)$ lower bound could be used to understand the tightness of our communication upper bound. That implies that our communication upper bound $O(KM\log(\Delta^{-1}))$ is tight in terms of the number of agents $M$.

In a word, proving a non-trivial communication lower bound is challenging and beyond the scope of this work. Comparing with known results suggests that our communication upper bound is tight in terms of $M$.

• Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: Nearoptimal regret with efficient communication. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020b.

Reviewer: Potentially misleading claim about the communication cost of the SE-AAC-ODC:

Answer: It is unfair to compare the result in Corollary 2(b) (Chen et al., 2023) with our algorithm. This is because the result in Corollary 2(b) (Chen et al., 2023) only holds when the buffer thresholds are exponential (e.g., doubling in $`SE-ODC-D`$ in the above simulation). But if the buffer thresholds are exponential, the algorithm in Chen et al. (2023) suffers a $O(KM\log T)$ regret which is away from the near-optimal regret by a factor of the number of agents $M$ (see their regret upper bound's second term in Theorem 1 (b)). In fact, this $O(KM\log T)$ regret upper bound can be achieved by all agents individually running UCB without any communication. Hence, it is unfair to compare the result in Corollary 2(b) (Chen et al., 2023) with our algorithm that always achieves the near-optimal $O(K\log T)$ regret.

Reviewer: Missing details in numerical simulations: The algorithm AAE-ODC from (Chen et. al. 2023) uses a buffer threshold for messages communicated among the agents. There is no mention of the values of the buffer threshold used in AAE-ODC for the experiments presented in the paper

Answer: For the experiments in the main paper, we set the buffer of $`SE-ODC`$ ($`AAE-ODC`$) as constant $1$ (that is, immediately communicate when there is a demand without any buffer). In Figure 5 of Appendix D, we report the $`SE-ODC`$ with no buffer (green), and $`SE-ODC-D`$ with doubling buffer (brown) and compare both to our algorithm, $`SE-AAC-ODC`$ (red). Although $`SE-ODC-D`$ with doubling buffer enjoys better communication performance than $`SE-ODC`$ with constant buffer, $`SE-ODC-D`$'s communication performance is still worse than that of $`SE-AAC-ODC`$ proposed in our paper, and $`SE-ODC-D`$'s empirical regret is far worse than $`SE-AAC-ODC`$, which is because $`SE-ODC-D`$'s regret upper bound $O(KM\log T)$ is intrinsically worse than our algorithm's $O(K\log T)$ regret upper bound. We updated these additional simulation results in the revised version of this paper.

Reviewer: Lack of originality: The algorithm and the analysis are extensions of known works in (Yang et. al. 2023) and (Chen et. al. 2023)

Answer: We acknowledge the foundational role of Yang et al. (2023) and Chen et al. (2023) in our algorithmic design. However, our analysis significantly extends their work, addressing challenges unique to our setting. On the one hand, the analysis of Chen et al. (2023) cannot be used in our case, as we are aiming for a constant communication upper bound, which is intrinsically different from their time-dependent bounds. On the other hand, the analysis tool in Yang et al. (2023) relies heavily on the synchronous multi-agent setting (agents always have the same number of samples), which is invalid in our asynchronous setting. In this paper, we develop a new analysis approach that relies on the ''fastest'' agent (with the highest number of active decision rounds, see Lemma 1). We refer the reviewer to Section 1.2 (related works) for a more comprehensive discussion about how this work differs from (Yang et al. 2023) and (Chen et al. 2023).

We highly appreciate the reviewer for suggesting other minor changes. All were addressed in the revised version, except for $\mathbb{N}^+$. Because whether the natural number contains zero is ambiguous (see the first sentence of the nature number on the Wikipedia page), the authors think it would be better to use $\mathbb{N}^+$ to avoid misunderstanding.

Fair enough, although the dependence of communication parameter $\alpha$ on the leading order term $\log T$ in group regret (as $(1 + \alpha)^2$) isn't ideal in my opinion. I am raising my score to 5, but can't vouch for acceptance of the paper because of the aforementioned concern.

Reviewer: The authors do not provide a lower bound for the number of communication rounds required, which makes it difficult to assess the performance of the proposed algorithm.

Answer: Providing a non-trivial lower bound for communication in asynchronous multi-agent MAB settings is highly challenging and remains an open problem in the literature. This is because some extremely asynchronous scenarios could make communication unnecessary. For example, consider the case that one agent is active in all time slots, while all other agents are only active in one single time slot. In this case, there is no need to conduct communication among these agents, that is, one can achieve near-optimal regret by all agents individually running UCB without any communication.

On the other hand, the only related communication lower bound results that we are aware of is in Wang et al. (2020, Section 3.4), where they show that to achieve a $o(M\sqrt{KT})$ regret upper bound in synchronous multi-agent MAB, the expected communication is at least $\Omega(M)$. If we exclude the extreme cases and only consider mildly asynchronous scenarios, then the $\Omega(M)$ lower bound could be used to understand the tightness of our communication upper bound. That implies that our communication upper bound $O(KM\log(\Delta^{-1}))$ is tight in terms of the number of agents $M$.

In a word, proving a non-trivial communication lower bound is challenging and beyond the scope of this work. Comparing with known results suggests that our communication upper bound is tight in terms of $M$.

• Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: Nearoptimal regret with efficient communication. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020b.

Reviewer: The proposed algorithm is not validated with real-world data.

Answer: In numerical experiments, we set arm reward means as the click-through-rate from an ad-click Kaggle dataset (Avito Context Ad Clicks, 2015. https://www.kaggle.com/c/avito-context-ad-clicks), which simulates the real click-through process in online advertising applications. We updated this in the revised manuscript.