Response to Weakness 5:

Q: In the experiments, the authors simply compare DDSE with two methods that do not account for delay. This comparison may be somewhat unfair. If there is no other available algorithm, it would be better to compare DDSE with the benchmark centralized algorithm.

As Reviewer N47W suggests, we have compared our algorithms with [5, 6, 7]. All the experimental results show that our algorithms perform best. We also compare DDSE in both decentralized and centralized settings. Experimental results in Figure 10 show that the performance of DDSE closely matches that in the centralized setting.

Response to Question 1:

Q: In cognitive radio networks, players are usually dynamic. Additionally, there are some hidden nodes (players) that are unknown to each other. In this case, will the DDSE algorithm still work?

Dynamic Players:

If players are dynamic, the setting is called asynchronous multi-player bandits. In this setting, players can enter the game and leave at any time. The latest study on asynchronous MMAB is [8]. However, [8] relies on several assumptions:

1. There exists a centralized environment, where players can freely communicate with others.

2. Although players enter the game at different times, they leave at the same time $T$.

3. At each time, the probability that every player enters the game is the same and known.

The area of centralized asynchronous MMAB without assumptions is still blank, let alone decentralized asynchronous MMAB. In decentralized bandits, delay has already significantly complicated the problem because players rely on the feedback of collisions to get some information from other players. Incomplete feedback causes inconsistency between players, leading to staggered exploration, frequent collisions, or premature exploitation.

Hidden Players:

As stated in "Response to Weakness 1", if players have no prior knowledge about others, an initialization phase can be introduced. Players start with an initialization phase where, despite incomplete feedback, they begin to explore arms. If a collision occurs during exploration that should not have happened, the affected player notifies others by sending a collision signal at a specific time. After a period of delay, players receive the signal and re-enter the initialization phase, followed by the next round of exploration. By adopting this approach, it is possible to provide probabilistic guarantees under our sub-Gaussian delay assumption. However, this would complicate the notation significantly. The problem addressed in this work is already sufficiently challenging, as our study is the first to tackle delays in multi-player bandits where collisions occur when players select the same arm. Our goal is to pave the way for further study in this area. A fully decentralized MMAB can be discussed in future work.

Response to Question 2:

Q: If a player $j$ is waiting for the feedback from arm $k$ (i.e., $t<s+d _ s^j$) and another player $l$ pulls this arm $k$, will there be a collision? If a collision occurs, will player $j$ fail to obtain a reward from arm $k$ after waiting $t−s$ time slots?

In our paper, players selecting the same arm at the same time is called "collision". A player $j$ selects arm $k$ at time $s$. Another player $\ell$ also selects arm $k$ at time $s$. Then we call that the two players collide with each other, but they do not receive the feedback immediately. The delay $d _ s^j$ and $d _ s^{\ell}$ do not have to be the same. Player $j$ and player $\ell$ will receive their feedback that they have collided at time $s$ in different time slots. When the feedback from time $s$ has not been received, player $j$ can wait for the feedback from arm $k$ (i.e., $t<s+d _ s^j$) while selecting other arms. "Waiting" does not mean that the player is idle. If another player $\ell$ selects arm $k$ also at time $s$, then both player $j$ and $\ell$ will receive collisions. If the player $\ell$ selects arm $k$ at $t^{\prime}$ (We define $s \leq t^{\prime} \leq s+d _ s^j$. ), player $j$ will not receive a collision at time $s+d _ s^j$, because at time $s$, only $j$ selects the arm $k$.

The first block is used for removing an arm from $\mathcal{M}^j _ p$ .

The leader first finds the bad arm $a^- _ p$ in $\mathcal{M}^j _ p$ and identifies the position of $a^- _ p$ . Then the leader selects the $i _ {a^- _ p}$ -th arm in $\mathcal{M}^j _ {p-q _ j}$ for $M$ times. Followers still select arms in $\mathcal{M}^j _ {p-q _ j}$ in a round-robin way. After a collision occurs, followers save the position that a collision happens. Then when she gets both the position of the arm to be removed and the arm to be added, she will update the best arm set. In the example, players in phase $2$ (i.e., $p=2$) but they still use $\mathcal{M} _ 1^j$. $t _ 1$ to $t _ 4$ denotes the rounds in the first block. We suppose that the leader wants to remove arm $1$ from $\mathcal{M} _ 2^4$. The arm selection is in the table.

Each follower collides on arm $3$ once. They remember the position of collision in $p=2$ is $4$.

The second block is used for adding an arm from $\mathcal{M}^j _ p$.

The leader finds a better arm that has higher empirical rewards but not in $\mathcal{M}^j _ p$. Then she wants to pass the new arm to followers. Because the new arm $a^+ _ p$ might not be in $\mathcal{M}^j _ p$ or $\mathcal{M}^j _ {p-q _ j}$, we can not let followers receive the collision information via the best arm set. Thus, we utilize the whole arm set. The leader continuously selects $a^+ _ p$ for $K$ times. Followers select all arms in a round-robin way. This block continues $K$ times because the length of the original arm is $K$ and we hope to use the original whole arm set to pass the information.

In the example, $t _ 5$ to $t _ 6$ denotes the rounds in the second block. We suppose that the leader wants to add arm $1$.

Each follower collides on arm $5$ once. They remember that the arm where the collision happens is $5$.

The third block is used for passing the ending of exploration.

Leader explores and gradually eliminates all sub-optimal arms from $[K]$. However, as for followers, they do not know when the exploration of the leader ends. If the leader's exploration has ended and passes all optimal arms to followers, continuing to enter the communication phase is a waste of time for followers. Therefore, a block used for passing the ending of exploration is necessary. Players' actions are similar to the first block.

After a period of delay:

Note that the collisions in the first and second blocks can not be received immediately. After a period of delay, follower $j$ receives the position $4$ and the arm to be added is $5$. She also knows the feedback is from phase $2$. Therefore, she updates:

$$\mathcal{M} _ 1^j = \\{4, 2, 6, 3\\} \rightarrow \mathrm{replace\ the\ arm\ in\ position\ 4\ to\ arm\ 5} \rightarrow\mathcal{M}^j _ 2 = \\{4, 2, 6, 5\\}$$

No matter how late the feedback is received by the follower, she can update the correct $\mathcal{M} _ p^j$.

Response to Weakness 3:

Q: I suggest the authors to move Subsection 5.3 ahead of Subsection 5.1 for better logic, as the centralized lower bound serve as the benchmark.

We sincerely thank the reviewer for the valuable suggestion regarding the organization of the theoretical analysis section. In response, we have moved the lower bound to the beginning of this section, as it serves as a natural benchmark for the subsequent analysis.

Response to Weakness 4:

Q: In the experiments, the number of players $M$ is a relatively small compared to typical application of cognitive radio networks.

We truly appreciate that the reviewer points out the concern regarding the relatively small number of players. To address this, we have conducted additional experiments with larger parameters, specifically for $M=30$ and $M=40$. The results, which are now included in Appendix B, demonstrate that our algorithms continue to outperform others as the number of players increases.

Thank you for your comments about our manuscript. We have studied the comments carefully, and find them valuable for improving our paper. The responses to your comments are as follows:

Response to Weakness 1:

 Q: This DDSE algorithm is not fully decentralized. In many cognitive radio networks, sensing nodes are dynamic, and some nodes are even hidden or unknown to the network operator.

We have considered a fully decentralized setting at the beginning of our work. In such fully decentralized multi-player bandits, players do not know the existence of others so there is no guarantee to avoid collisions. Thus, decentralized MMAB algorithms need an initialization phase where players utilize collisions to get some information before exploration, so that they can select arms in a round-robin way. There are two kinds of methods for initialization.

1. [1, 2, 3] adopt a musical chair method, where each player preempts an arm until no collision happens. After preempting an arm, players then intentionally select some arms. By counting the times of accumulated collision in this period, each player can know $M$ and her ID among these players.

2. In [4], players also try to preempt arms once. If they fail to preempt it, i.e., receive a collision, they will select specific arms later to pass the information that she has not found her arm to other players. When no collision occurs, it means that everyone finds the proper arm. Then they perform a procedure similar to [1, 2, 3] and get the information on $M$ and their ID.

However, when delay is introduced to the environment, players can not receive the collision immediately. If the delay is too long, players must wait in the initialization phase to receive the feedback of collision, because they need to get $M$ and their ID to start an exploration where they can select arms in a round-robin way. Actually, players always hope that they should receive some feedback in a certain known period, which conflicts with the scenario where feedback is delayed for an unknown period.

Of course, if we assume that delay is bounded by a known value $d _ {\max}$, the problem of initialization will be solved easily by using the classical technique and waiting for extra $d _ {\max}$ rounds in the beginning. In cognitive radio networks, transmission delay is sometimes bounded by protocol limits, so it is also natural to consider a bounded delay where we can sue $d _ {\max}$ as the input of algorithms to perform an initialization.

Our assumption on delay is more mild than this bounded delay. We allow some exceedingly large and unknown delay in the environment. If the assumption on the initialization does not exist, i.e., players are fully decentralized, we can also implement that pre-mentioned technique in our algorithms. For example, players start with an initialization phase. Although their feedback might not be completed, they still begin to explore arms. If a player in exploration has a collision that should not have happened, she notifies others also by sending collisions at a specific time. After a period of delay, players receive the signal and start an initialization again. Then comes the next exploration. By doing so, it is possible to give a probability guarantee using our sub-Gaussian delay assumption. However, it will make the notation more complicated. The existing problem is enough challenging and our work is the first paper handling delay in multi-player bandits where a collision occurs when selecting the same arm. Our goal is to pave the way for further study in this area. A fully decentralized MMAB can be discussed in future work.

Response to Weakness 2:

Q: The communication assumption weakens the solution in this work.

We do not assume that players can freely communicate. They can only know $M$ and their own ID. The communication phase is designed to solve the difficulty that player can not directly communicate. We review that a player $j$ receives feedback on the reward of the arm that she selected several rounds ago and whether she has a collision on the arm. The collision indicates that there exists at least another player who also selected the same arm. In our algorithm design, collisions that happen on specific periods represent some implicit information. Thus, by intentionally sending collisions, players can pass some information to others.

Next, we explain our communication phase here. The primary goal of communication phase is to pass the update of $\mathcal{M} _ p^j$. Each communication phase is composed of three blocks. We consider $M=4$ and $K=6$. The example is:

\begin{aligned} \mathrm{Leader:} \ &\mathcal{M}^4_1 = \{4, 2, 6, 3\}, \mathcal{M}^4_2 = \{4, 2, 6, 1\}, \mathcal{M}^4_3 = \{4, 2, 6, 5\} \\ \mathrm{Follower\ 1:} \ &\mathcal{M}^1_1 = \{4, 2, 6, 3\} \\ \mathrm{Follower\ 2:} \ &\mathcal{M}^2_1 = \{4, 2, 6, 3\} \\ \mathrm{Follower\ 3:} \ &\mathcal{M}^3_1 = \{4, 2, 6, 3\} \end{aligned}

Reference

[1] Boursier, Etienne, and Vianney Perchet. "SIC-MMAB: Synchronisation involves communication in multiplayer multi-armed bandits." Advances in Neural Information Processing Systems 32 (2019).

[2] Shi, Chengshuai, et al. "Decentralized multi-player multi-armed bandits with no collision information." International Conference on Artificial Intelligence and Statistics. PMLR, 2020.

[3] Huang, Wei, Richard Combes, and Cindy Trinh. "Towards optimal algorithms for multi-player bandits without collision sensing information." Conference on Learning Theory. PMLR, 2022.

[4] Wang, Po-An, et al. "Optimal algorithms for multiplayer multi-armed bandits." International Conference on Artificial Intelligence and Statistics. PMLR, 2020.

[5] Besson, Lilian, and Emilie Kaufmann. "Multi-player bandits revisited." Algorithmic Learning Theory. PMLR, 2018.

[6] Bistritz, Ilai, and Amir Leshem. "Distributed multi-player bandits-a game of thrones approach." Advances in Neural Information Processing Systems 31 (2018).

[7] Tibrewal, Harshvardhan, et al. "Distributed learning and optimal assignment in multiplayer heterogeneous networks." IEEE INFOCOM 2019-IEEE Conference on Computer Communications. IEEE, 2019.

[8] Richard, Hugo, Etienne Boursier, and Vianney Perchet. "Constant or Logarithmic Regret in Asynchronous Multiplayer Bandits with Limited Communication." International Conference on Artificial Intelligence and Statistics. PMLR, 2024.

1. The first block is used for removing an arm from $\mathcal{M}^j _ p$ .

The leader first finds the bad arm $a^- _ p$ in $\mathcal{M}^j _ p$ and identifies the position of $a^- _ p$ . Then the leader selects the $i _ {a^- _ p}$ -th arm in $\mathcal{M}^j _ {p-q _ j}$ for $M$ times. Followers still select arms in $\mathcal{M}^j _ {p-q _ j}$ in a round-robin way. After a collision occurs, followers save the position that a collision happens. Then when she gets both the position of the arm to be removed and the arm to be added, she will update the best arm set. In the example, players in phase $2$ (i.e., $p=2$) but they still use $\mathcal{M} _ 1^j$. $t _ 1$ to $t _ 4$ denotes the rounds in the first block. We suppose that the leader wants to remove arm $1$ from $\mathcal{M} _ 2^4$. The arm selection is in the table.

Each follower collides on arm $3$ once. They remember the position of collision in $p=2$ is $4$.

2. The second block is used for adding an arm from $\mathcal{M}^j _ p$.

The leader finds a better arm that has higher empirical rewards but not in $\mathcal{M}^j _ p$. Then she wants to pass the new arm to followers. Because the new arm $a^+ _ p$ might not be in $\mathcal{M}^j _ p$ or $\mathcal{M}^j _ {p-q _ j}$, we can not let followers receive the collision information via the best arm set. Thus, we utilize the whole arm set. The leader continuously selects $a^+ _ p$ for $K$ times. Followers select all arms in a round-robin way. This block continues $K$ times because the length of the original arm is $K$ and we hope to use the original whole arm set to pass the information. In the example, $t _ 5$ to $t _ 6$ denotes the rounds in the second block. We suppose that the leader wants to add arm $1$.

Each follower collides on arm $5$ once. They remember that the collision happens on arm $5$.

3. The third block is used for passing the ending of exploration.

Leader explores and gradually eliminates all sub-optimal arms from $[K]$. However, as for followers, they do not know when the exploration of the leader ends. If the leader's exploration has ended and passes all optimal arms to followers, continuing to enter the communication phase is a waste of time for followers. Therefore, a block used for passing the ending of exploration is necessary. Players' actions are similar to the first block.

4. After a period of delay:

Note that the collisions in the first and second blocks can not be received immediately. After a period of delay, follower $j$ receives the position $4$ and the arm to be added is $5$. She also knows the feedback is from phase $2$. Therefore, she updates:

$$\mathcal{M}_1^j = \\{4, 2, 6, 3\\} \rightarrow \mathrm{replace\ the\ arm\ in\ position\ 4\ to\ arm\ 5} \rightarrow\mathcal{M}^j_2 = \\{4, 2, 6, 5\\}$$

Therefore, although players use the previous arm set $\mathcal{M} _ 1^j$, followers can still receive the correct update information of $\mathcal{M} _ 2^j$ even though they do not know $\mathcal{M} _ 2^j$.

Regret Analysis of DDSE

Exploration Phase

Lemma 5 ensures that the delayed feedback from the communication phase of all followers is bounded. Then Lemma 6 establishes the accuracy of the estimates for $\mathbb{E}[d]$ and $\sigma _ d^2$. As a result, player $j$ can correctly determine $q _ j$ and align with the same best empirical arm set, thereby preventing collisions caused by inconsistencies between the leader and the followers. Thus, the regret in exploration phase is generated from (1) selecting sub-optimal arms, (2) players not receiving any feedback initially, and (3) the leader not entering the exploitation phase immediately after identifying all sub-optimal arms. During the period after the leader identifies all sub-optimal arms but before entering the exploitation phase, the leader still needs to maintain consistency with followers by selecting arms in $\mathcal{M} _ {p-q _ M}$. We separately bound these terms in Appendix D.

Communication Phase

We have already known that the length of each communication phase is $K+2M$. Note that players enter a communication phase every $KM\log(T)$ rounds. The next step is to bound the times that the leader needs to receive feedback and eliminate all sub-optimal arms. Thus, $T _ {expl}/KM\log(T)$ indicates the number of times players enter a communication phase, which we then multiply by the phase length $K+2M$. Note that there are $M$ players in communication phase, so we finally take a union bound of $M$.

Combining the results in exploration and communication phase, we derive the regret bound of DDSE. By comparing with the lower bound in Theorem 1, DDSE is near-optimal.

Response to Question 1:

Q: Can the authors highlight the main technical challenges?

We appreciate the reviewer's insightful question. The main technical challenge lies in accurately estimating the delay within the decentralized multi-armed bandit setting, particularly under the collision model. While delay analysis has been explored previously, our approach introduces a novel consideration of sub-Gaussian delays, which adds complexity to bounding delays during the communication phase. Specifically, we address the challenge by proving the correctness of our estimations for both $\mathbb{E}[d]$ and $\sigma^2 _ d$ (Lemma 2) and analyzing potential errors in delay estimation. Leveraging the fact that the square of a sub-Gaussian variable is sub-Exponential, we rigorously bound the probabilities of deviations $|\hat{\mu} _ {d _ t^j}-\mathbb{E}[d]| \leq \epsilon _ {\mu}$ and $|\hat{\sigma} _ {d _ t^j}^2-\sigma _ d^2| \leq \epsilon _ {\sigma}$. In Lemma 9, applying the inverse Jensen inequality twice allows us to derive $\mathbb{E}[s _ p-s _ {p-1}]$, so that we can utilize $\mathbb{E}[s _ p-s _ {p-1}]=KM\log(T)$. Combining this with the term $T$ on the outside, we finally get the bound of $R_{\mathcal{F}}$.

Thank you for your comments about our manuscript. We have studied the comments carefully, and find them valuable for improving our paper. The responses to your comments are as follows:

Response to Weakness 1:

Q: Can the paper provide any other relevant examples except cognitive radio?

Autonomous Vehicles in Traffic Management:

When multiple autonomous vehicles (players) choose the same lane or intersection (arm) at the same time, traffic congestion or collisions can occur. By applying our algorithm, route optimization and intersection management can be significantly improved, leading to fewer collisions and smoother traffic flow.

Resource Scheduling in Cloud Computing:

In cloud computing, users (players) often compete for access to the same virtual machines or servers (arms), which can create resource bottlenecks and degrade performance. Our algorithm dynamically allocates tasks to available resources, effectively reducing conflicts and improving system efficiency.

Response to Weakness 2:

Q: The paper is very hard to read, hence, the contributions are obscure.

Thank you sincerely for the thoughtful comments that clarity could be improved. We have revised our manuscript by refining notations, enhancing the descriptions of the algorithms, and improving the presentation of the proofs. Below, we summarize our main contributions for better clarity:

1. We propose a novel framework for multi-player multi-armed bandits (MMAB) with delayed feedback. To the best of our knowledge, we are the first to address delay in MMAB settings where selecting the same arm results in collisions.

2. To tackle this challenge, we introduce the DDSE (Decentralized Delayed Successive Elimination) algorithm. In DDSE, players coordinate to utilize the same best empirical arm set, determined based on their delay estimations, before each exploration phase. This ensures that collisions are effectively avoided.

3. We derive a regret bound of DDSE, and study the regret bound of DDSE in centralized setting. We also derive a centralized lower bound in MMAB with delayed feedback. Compared with the lower bound, the regret of DDSE is near-optimal.

4. Finally, we validate the efficacy of DDSE through numerical experiments conducted on both synthetic and real-world datasets.

We describe our main algorithm and its proof here.

Algorithm: DDSE

Our algorithm is composed of exploration and communication. Because the environment is decentralized, we design this communication phase where players can pass implicit information using intentional collisions to simulate communication. The player with ID $M$ becomes the leader and others are followers.

Exploration

In exploration, the leader explores all active arms while followers only select arms from a specific best arm set. The set of followers is updated when they receive information from the leader in communication phase. Due to the decentralized environment, each player may have a different best arm set. Thus, we define $\mathcal{M} _ p^j$ as the best arm set of player $j$ at phase $p$. Note that the leader sends the information to followers only after she knows the results, but the information that followers receive is delayed for an unknown time. Thus, after every communication phase ends, the updated $\mathcal{M} _ p^M$ is different with $\mathcal{M} _ p^j, j<M$. Different best arm sets lead to: (1) collision in the exploration phase, (2) passing wrong information in the communication phase. To avoid this situation, we introduce our method of delay estimation. The intuition is, that although the current best arm set is different, players can select arms in the previous best arm set which has been received completely. Lemma 1 and Lemma 2 guarantee that players select the same best arm set so that no collision occurs in exploration phase.

Communication

The goal of communication phase is to pass the update of $\mathcal{M} _ p^j$. Each communication phase is composed of three blocks. We consider an example with $M=4$ and $K=6$ to better understand the algorithm. We suppose that players are in phase $2$. They use the previous arm set $\mathcal{M} _ 1^j$. The leader wants to update to $\mathcal{M} _ 3^4$.

\begin{aligned} \mathrm{Leader:} \ &\mathcal{M}^4_1 = \{4, 2, 6, 3\}, \mathcal{M}^4_2 = \{4, 2, 6, 1\}, \mathcal{M}^4_3 = \{4, 2, 6, 5\} \\ \mathrm{Follower\ 1:} \ &\mathcal{M}^1_1 = \{4, 2, 6, 3\} \\ \mathrm{Follower\ 2:} \ &\mathcal{M}^2_1 = \{4, 2, 6, 3\} \\ \mathrm{Follower\ 3:} \ &\mathcal{M}^3_1 = \{4, 2, 6, 3\} \end{aligned}

Response to Question on Experiments:

Q: In the experiment section, why are the algorithms in [1, 2, 3] papers not considered?

Thank you for your question. We have included comparisons with the algorithms from these papers. The experimental results are presented in Section 5 and detailed further in Appendix B. Our algorithms demonstrate superior performance compared to these methods. Additionally, we discuss the results and analyze why these algorithms do not perform well on Page 9.

Specifically, [1] design a special UCB index which decreases when collision occurs. However, as the name suggests, players in this algorithm are selfish and only want to maximize their own rewards. Thus, they fail to utilize the exploration results of others, causing the regret to increase rapidly as $M$ grows. Both Game of Throne [2] and ESER [3] follow an explore-then-commit approach, so they rely on the adjustment of parameters heavily. Meanwhile, MCTopM and RandomTopM from [1] are built on the Musical Chair framework [4], where players randomly preempt a chair with no collision. When delay happens, an arm that is identified to be idle in earlier rounds may already have been preempted by other players, but the player always gets out-of-date feedback, resulting in non-stop exploration to find idle arms.

More importantly, none of these algorithms are involved in simulating communication by collisions. The flow of information between players is helpful for them to find optimal arms and lead that the main term in the regret bound is not multiplied by $M$. Our experimental results in Figure 2 also show that the regret of [1, 2, 3] grows rapidly when $M$ increases, while our algorithms are more stable.

As Reviewer fYEh suggested, we also add experiments on a real-world dataset following the work of [5]. See our update on Page 10. The dataset can be found at https://zenodo.org/records/1293283. The throughput is computed using Shannon Formula which is also aligned with [5]. We also compare the cumulative collisions in this experiment, following the experiment in [5, 6]. The results demonstrate that our algorithms outperform the others.

We observe that the regrets of some algorithms that in our comparison increase rapidly, so we evaluated DDSE in both decentralized and centralized settings as Reviewer j5FD suggested. Experimental results in Figure 10 show that the performance of DDSE in decentralized setting closely matches that in centralized setting.

Response to Minor Issues:

Q: (1) Line 209: $s<T$ or $s<t$. (2) Is there any difference between sequential hopping and round-robin? (3) Why $|[K]|=M$ ?

1. Thank you for pointing this out. We have corrected it to $t$.

2. We sincerely appreciate your observation. The terms "sequential hopping" and "round-robin" indeed refer to the same concept. To avoid confusion, we have updated the paper to consistently use "round-robin" throughout our paper.

3. We are truly grateful for your attention to the notation. Our previous notation was slightly ambiguous. As explained in "Respond to Question 4", in multi-player bandits, each player has her optimal arm so we totally have $M$ optimal arms. When the leader eliminates all sub-optimal arms, i.e., there are $M$ optimal arms left, she will send collisions in the third block of the next communication phase and then begin exploitation. To clarify, we have introduced an active arm set $\mathcal{K}$ and replaced instances of $[K]$ with $\mathcal{K}$ where appropriate. This ensures the notation aligns with the context more accurately.

Reference

[1] Besson, Lilian, and Emilie Kaufmann. "Multi-player bandits revisited." Algorithmic Learning Theory. PMLR, 2018.

[2] Bistritz, Ilai, and Amir Leshem. "Distributed multi-player bandits-a game of thrones approach." Advances in Neural Information Processing Systems 31 (2018).

[3] Tibrewal, Harshvardhan, et al. "Distributed learning and optimal assignment in multiplayer heterogeneous networks." IEEE INFOCOM 2019-IEEE Conference on Computer Communications. IEEE, 2019.

[4] Rosenski, Jonathan, Ohad Shamir, and Liran Szlak. "Multi-player bandits–a musical chairs approach." International Conference on Machine Learning. PMLR, 2016.

[5] Alipour-Fanid, Amir, et al. "Multiuser scheduling in centralized cognitive radio networks: A multi-armed bandit approach." IEEE Transactions on Cognitive Communications and Networking 8.2 (2022): 1074-1091.

[6] Wang, Wenbo, et al. "Decentralized learning for channel allocation in IoT networks over unlicensed bandwidth as a contextual multi-player multi-armed bandit game." IEEE Transactions on Wireless Communications 21.5 (2021): 3162-3178.

Response to Question 4:

Q: How are collisions interpreted in the communication phase? Is it binary signaling?

The collisions are just collisions that represent that at least two players select the same arm at the time. We design the communication phase to handle the difficulty that players can not directly communicate with others. Although there is no way to pass the information directly under the environment, our algorithms build a specific framework for players to pass information in such an environment. Via the algorithm, collisions can be interpreted as some information by players.

Next, we explain our communication phase here. The primary goal of communication phase is to pass the update of $\mathcal{M} _ p^j$. Each communication phase is composed of three blocks. We consider $M=4$ and $K=6$. The example is:

\begin{aligned} \mathrm{Leader:} \ &\mathcal{M}^4_1 = \{4, 2, 6, 3\}, \mathcal{M}^4_2 = \{4, 2, 6, 1\}, \mathcal{M}^4_3 = \{4, 2, 6, 5\} \\ \mathrm{Follower\ 1:} \ &\mathcal{M}^1_1 = \{4, 2, 6, 3\} \\ \mathrm{Follower\ 2:} \ &\mathcal{M}^2_1 = \{4, 2, 6, 3\} \\ \mathrm{Follower\ 3:} \ &\mathcal{M}^3_1 = \{4, 2, 6, 3\} \end{aligned}

The first block is used for removing an arm from $\mathcal{M}^j _ p$ .

The leader first finds the bad arm $a^- _ p$ in $\mathcal{M}^j _ p$ and identifies the position of $a^- _ p$ . Then the leader selects the $i_{a^- _ p}$ -th arm in $\mathcal{M}^j _ {p-q _ j}$ for $M$ times. Followers still select arms in $\mathcal{M}^j _ {p-q _ j}$ in a round-robin way. After a collision occurs, followers save the position that a collision happens. Then when she gets both the position of the arm to be removed and the arm to be added, she will update the best arm set. In the example, players in phase $2$ (i.e., $p=2$) but they still use $\mathcal{M} _ 1^j$. $t _ 1$ to $t _ 4$ denotes the rounds in the first block. We suppose that the leader wants to remove arm $1$ from $\mathcal{M} _ 2^4$. The arm selection is in the table.

Each follower collides on arm $3$ once. They remember the position of collision in $p=2$ is $4$.

The second block is used for adding an arm from $\mathcal{M}^j _ p$.

The leader finds a better arm that has higher empirical rewards but not in $\mathcal{M}^j _ p$. Then she wants to pass the new arm to followers. Because the new arm $a^+ _ p$ might not be in $\mathcal{M}^j _ p$ or $\mathcal{M}^j _ {p-q _ j}$, we can not let followers receive the collision information via the best arm set. Thus, we utilize the whole arm set. The leader continuously selects $a^+ _ p$ for $K$ times. Followers select all arms in a round-robin way. This block continues $K$ times because the length of the original arm is $K$ and we hope to use the original whole arm set to pass the information.

In the example, $t _ 5$ to $t _ 6$ denotes the rounds in the second block. We suppose that the leader wants to add arm $1$.

Each follower collides on arm $5$ once. They remember that the collision occurred on arm 5.

The third block is used for passing the ending of exploration.

Leader explores and gradually eliminates all sub-optimal arms from $[K]$. However, as for followers, they do not know when the exploration of the leader ends. If the leader's exploration has ended and passes all optimal arms to followers, continuing to enter the communication phase is a waste of time for followers. Therefore, a block used for passing the ending of exploration is necessary. Players' actions are similar to the first block.

After a period of delay:

Note that the collisions in the first and second blocks can not be received immediately. After a period of delay, follower $j$ receives the position $4$ and the arm to be added is $5$. She also knows the feedback is from phase $2$. Therefore, she updates:

$$\mathcal{M}_1^j = \\{4, 2, 6, 3\\} \rightarrow \mathrm{replace\ the\ arm\ in\ position\ 4\ to\ arm\ 5} \rightarrow\mathcal{M}^j_2 = \\{4, 2, 6, 5\\}$$

No matter how late the feedback is received by the follower, she can update the correct $\mathcal{M} _ p^j$.

Thank you for your comments about our manuscript. We have studied the comments carefully, and find them valuable for improving our paper. The responses to your comments are as follows.

Response to Weakness 1:

Q: The literature review is not detailed.

Thank you for your valuable feedback. We have expanded the literature review to include a discussion of several papers that address multi-player bandits with more general heterogeneous rewards. Please refer to Appendix A for the updated related works section.

Response to Question 1:

Q: What is the duration of exploration, communication, and exploitation?

The length of a communication phase is $K+2M$. The total duration of exploration is in Equation (14). Players are in exploration phase. They enter a communication phase every $KM\log(T)$ times. After the leader eliminates all sub-optimal arms and communicates the ending signal of exploration in the next communication phase, She begins the exploitation phase and continuously selects her arm until $T$. As for followers, they select arms in $\mathcal{M}^j _ {p-q _ j}$ and enter the communication phase every $KM\log(T)$ to receive the collision from the leader. After they receive a collision from the third block from a certain communication phase, they save the number of the final communication phase as $p _ {\max}$. Then followers will no longer enter a communication phase at the left time. All they need to do is select arms in $\mathcal{M} _ {p _ {\max}-q _ j}$. With time going by, $q _ j=0$ and followers select arms in the final best arm set, meaning that they are in exploitation.

Response to Question 2:

Q: Line 190 says, "the best empirical set arm set of player j." How is this set defined?

We define $\mathcal{M} _ {p}^j$ as the best empirical arm set of player $j$ at phase $p$. In the beginning, the set is randomly initialized. As the leader explores, she gets empirical rewards of arms and ranks these arms with their rewards. The $M$-th first should be put into the set. After finding an update, the leader passes the information to followers in the communication phase.

Response to Question 3:

Q: How is it ensured that the best empirical arm of leader and follower do not overlap in the exploration phase? How is the collision avoided?

To ensure sufficient exploration, the leader should explore all arms. However, followers are selecting arms in $\mathcal{M} _ {p-q _ j}^j$ in a round-robin way. Thus, we have a sophisticated design for leader's arm selection. We first give an example with $K=8$ and $M=4$:

\begin{aligned} \mathrm{Leader:} \ &\mathcal{M}^4_1 = \{4, 2, 6, 3\} \quad \mathrm{to} \quad \mathcal{M}^4_2 = \{4, 2, 6, 8\} \\ \mathrm{Follower\ 1:} \ &\mathcal{M}^1_1 = \{4, 2, 6, 3\} \\ \mathrm{Follower\ 2:} \ &\mathcal{M}^2_1 = \{4, 2, 6, 3\} \\ \mathrm{Follower\ 3:} \ &\mathcal{M}^3_1 = \{4, 2, 6, 3\} \end{aligned}

In this example, we suppose that they are focusing on $\mathcal{M} _ 1^j$. They select arms as follows:

The leader first selects arms in $\mathcal{M} _ 1^4$ with followers. After pulling all arms in $\mathcal{M} _ 1^4$, she begins to select other arms in $\mathcal{K}\backslash \mathcal{M} _ 1^4$. (Here $\mathcal{K}$ denotes the active arm set, to avoid the abuse of $|[K]|$.) The process continues for $KM\log(T)$ rounds.

In our supplemental material, you can find the related code in "$\mathtt{ReviewCode/ours/ddse.py}$". We have implemented the process of arm selection in the function "$\mathtt{play()}$".

"None of these algorithms are involved in simulating communication by collisions" means that [1, 2, 3] do not design a specific communication phase where players pass the reward or arm choice to others. Players in [1, 2, 3] do not utilize the exploration results of others. Therefore, the regrets in [1, 2, 3] are multiplied by $M$. Our regret of DDSE is $O(\log(T))$ due to the communication phase where players communicate on the update of $\mathcal{M} _ {p}^j$.

[1, 2, 3] only do experiments on small $K$ and $M$. When $M$ increases, the results are bad. In our experiments, we do experiments with at most $K=50$ and $M=40$.

We originally did not compare with [1, 2, 3] because they do not have the communication phase. In contrast, comparison with SIC-MMAB [4] is more suitable. Experimental results in Figure 10 have already shown that performance of DDSE in decentralized setting closely matches that in the centralized setting. We do not know why Reviewer N47W asks us to compare with [1, 2, 3] and is not satisfied with the comparison results. However, we would like to explain the experiments if you still have questions.

[1] Bistritz, Ilai, and Amir Leshem. "Distributed multi-player bandits-a game of thrones approach." _Advances in Neural Information

[2] Besson, Lilian, and Emilie Kaufmann. "Multi-player bandits revisited." Algorithmic Learning Theory. PMLR, 2018.

[3] Tibrewal, Harshvardhan, et al. "Distributed learning and optimal assignment in multiplayer heterogeneous networks." IEEE INFOCOM 2019-IEEE Conference on Computer Communications. IEEE, 2019.

[4] Boursier, Etienne, and Vianney Perchet. "SIC-MMAB: Synchronisation involves communication in multiplayer multi-armed bandits." Advances in Neural Information Processing Systems 32 (2019).

Thanks for your valuable feedback. We recognize that [1] includes a signaling phase, and we acknowledge that there were inaccuracies in our initial explanation of this work. However, we would like to emphasize that our experiments were conducted rigorously and correctly. This algorithm was implemented using an open-source GitHub library [2]. We have updated our supplementary material since 22 Nov 2024. For further clarification, we invite you to review the code provided in "$`ReviewCode/tibrewal2019`$". It should be noted that ESER performs well when parameters are appropriate (e.g. Figure 2 (a)), but its regret grows rapidly when $K$ and $M$ increase.

[1] Tibrewal, Harshvardhan, et al. "Distributed learning and optimal assignment in multiplayer heterogeneous networks." IEEE INFOCOM 2019-IEEE Conference on Computer Communications. IEEE, 2019.

[2] Wang, Wenbo, et al. "Decentralized learning for channel allocation in IoT networks over unlicensed bandwidth as a contextual multi-player multi-armed bandit game." IEEE Transactions on Wireless Communications 21.5 (2021): 3162-3178. https://github.com/wbwang2020/MP-MAB

Response to Weakness 4:

Q: This paper lacks a description of the proof process for the theorems.

Thanks for your advice. We have added some description in Appendix D. We briefly describe the proof of Theorem 1 here.

Exploration Phase

In the exploration phase, Lemma 5 ensures that the delayed feedback from the communication phase of all followers is bounded. Then Lemma 6 establishes the accuracy of the estimates for $\mathbb{E}[d]$ and $\sigma _ d^2$. As a result, player $j$ can correctly determine $q _ j$ and align with the same best empirical arm set, thereby preventing collisions caused by inconsistencies between the leader and the followers. Thus, the regret in exploration phase is generated from (1) selecting sub-optimal arms, (2) players not receiving any feedback initially, and (3) the leader not entering the exploitation phase immediately after identifying all sub-optimal arms. During the period after the leader identifies all sub-optimal arms but before entering the exploitation phase, the leader still needs to maintain consistency with followers by selecting arms in $\mathcal{M} _ {p-q _ M}$, i.e., $|\mathcal{K}|=M$, $e _ M=M$ but $q _ M\neq 0$ which do not satisfy Line 14 in Algorithm 1. Then we bound these terms separately in Appendix D.

Communication Phase

We have already known that the length of each communication phase is $K+2M$. Note that players enter a communication phase every $KM\log(T)$ rounds. The next step is to bound $T_{expl}$ which is the total time that the leader needs to receive feedback and eliminate all sub-optimal arms. Thus, $T _ {expl}/KM\log(T)$ indicates the number of times players enter a communication phase, which we then multiply by the phase length $K+2M$. Note that there are $M$ players in communication phase, so we finally take a union bound of $M$.

Response to Question 1:

Q: The writing is confused, many symbols are written incorrectly.

We sincerely thank the reviewer for the careful reading and valuable feedback. All noted issues with symbols and writing have been addressed. Below, we provide our detailed responses to the points raised.

1. We use the definition $r^j(s)$ because the reward has already been determined by a given player $j$ and a round $s$. There is no need to add a notation of $k$.
2. As stated in Line 154, $\mu_ {(k)}$ is the $k$-th highest reward. We have a order $\mu _ {(1)} \geq \mu _ {(2)} \geq ... \geq \mu _ {(K)}$. We define $\mu _ k$ as the expectation of arm $k$.
3. Thank you very much for pointing out this one. We have updated it in Line 203. $N_t(k):= \sum_{s \leq t} \mathbb{I}\{\pi_s^j=k, j=M\}$ is the number of times that the leader chooses arm $k$ before $t$.
4. We truly appreciate your attention to this detail. The notation has been updated to $\mathcal{M} _ 0^M$.
5. Thank you for highlighting this point. $\mathcal{M} _ {com}$ is originally used for determining whether to communicate the update of $\mathcal{M}^j _ p$. If $\mathcal{M}^M _ {p}=\mathcal{M}^M _ {p-1}$, the leader do not need to communicate with followers. We have removed the notation of $\mathcal{M} _ {com}$ and change the if-condition in Algorithms 1 into "$\mathtt{if}\ \mathcal{M}^M _ p \neq \mathcal{M}^M _ {p-1}\ \mathtt{then}$ ". If $\mathcal{M}^M _ p \neq \mathcal{M}^M _ {p-1}$, the leader send collisions in communication phase. Otherwise, she runs a virtual communication to select arms with followers in $\mathcal{M}^M _ {p-q_M}$ with no collision.

Response to Question 2:

Q: The introduction of the Algorithm 1 is very confusing. e.g. (1) Line 10 line of the Algorithm 1, (2) concern about $|[K]|=M$.

1. We have removed the notation of $\mathcal{M} _ {com}$ in Line 10 of Algorithm 1 and use "$\mathtt{if}\ \mathcal{M}^M _ p \neq \mathcal{M}^M _ {p-1}\ \mathtt{then}$ " as the if-else condition. The detailed explanation and example are in "Response to Weakness 1". Thank you for pointing out this improvement.
2. The leader explores and gradually eliminates all sub-optimal arms. As stated in "Response to Weakness 1", in multi-player bandits, each player has her optimal arm so we totally have $M$ optimal arms. When the leader eliminates all sub-optimal arms, i.e., there are $M$ optimal arms left, the arm set shrinks into the length of $M$. Therefore, when $[K]$ shrinks to only $M$ elements, the exploration ends.

Reference

[1] Boursier, Etienne, and Vianney Perchet. "SIC-MMAB: Synchronisation involves communication in multiplayer multi-armed bandits." Advances in Neural Information Processing Systems 32 (2019).

[2] Shi, Chengshuai, et al. "Decentralized multi-player multi-armed bandits with no collision information." International Conference on Artificial Intelligence and Statistics. PMLR, 2020.

[3] Huang, Wei, Richard Combes, and Cindy Trinh. "Towards optimal algorithms for multi-player bandits without collision sensing information." Conference on Learning Theory. PMLR, 2022.

Thank you for your comments about our manuscript. We have studied the comments carefully, and find them valuable for improving our paper. The responses to your comments are as follows.

Response to Weakness 1:

Q: Why set the length of each communication phase as $K+2M$? If the length of communication phase becomes time-varying, will the methods in this paper still apply?

Each communication phase is composed of three blocks.

The first block is used for removing an arm from $\mathcal{M}^j _ p$ .

We first explain the case that players do not delay the update of $\mathcal{M}^j _ p$. The leader continuously selects the arm to be removed for $M$ times. Followers selects arms in $\mathcal{M}^j _ {p}$. Because the length of $\mathcal{M}^j _ p$ is $M$, during the process of round-robin selection, each follower will collide with the leader once. The arm that generates a collision will be removed from $\mathcal{M}^j _ p$.

If the update of $\mathcal{M}^j _ p$ is delayed, i.e. players should use $\mathcal{M}^j _ {p-q _ j}$ instead of $\mathcal{M}^j _ {p}$. During this block, we still hope to pass the information that an arm in $\mathcal{M}^j _ p$ should be removed. Therefore, the leader firstly finds the bad arm $a^- _ p$ in $\mathcal{M}^j _ p$. If the leader directly selects $a _ p^-$, followers will get the wrong information because they are selecting arms in $\mathcal{M}^j _ {p-q _ j}$ which is not the same with $\mathcal{M}^j _ p$. We consider the example with $M=4$ and $K=6$:

\begin{aligned} \mathrm{Leader:} \ &\mathcal{M}^4_1 = \{4, 2, 6, 3\}, \mathcal{M}^4_2 = \{4, 2, 6, 5\} , \mathcal{M}^4_3 = \{4, 2, 6, 1\} \\ \mathrm{Follower\ 1:} \ &\mathcal{M}^1_1 = \{4, 2, 6, 3\} \\ \mathrm{Follower\ 2:} \ &\mathcal{M}^2_1 = \{4, 2, 6, 3\} \\ \mathrm{Follower\ 3:} \ &\mathcal{M}^3_1 = \{4, 2, 6, 3\} \end{aligned}

In this example, the leader wants to remove arm $5$ from $\mathcal{M}^4 _ 2$. Note that followers do not know $\mathcal{M}^j _ 2$ and can only select arms in $\mathcal{M}^j _ 1$ in the communication phase. If the leader simply selects arm $5$ in this communication phase, followers will not receive the collision because they just select arm ${4,2,6,3}$. This will lead to missing information from the communication phase.

To avoid this situation, the leader also finds the position of $a^- _ p$ . We define the position of $a^- _ p$ as $i _ {a^- _ p}$. Then the leader selects the $i _ {a^- _ p}$ -th arm in $\mathcal{M}^j _ {p-q _ j}$ for $M$ times. Followers still select arms in $\mathcal{M}^j _ {p-q _ j}$ in a round-robin way. After a collision occurs, followers save the position that a collision happens. Then when she gets both the position of the arm to be removed and the arm to be added, she will update the best arm set. In this example, the leader finds that the position of arm $5$ is $4$, so she selects the $4$-th arm in $\mathcal{M}^4 _ 1$, i.e. arm $3$, for $M$ times. Followers select arm $\{4,2,6,3\}$ in a round-robin way. The detailed arm selection is in the table.

Each follower collides on arm $3$ once. They remember the position of collision in $p=2$ is $4$.

The second block is used for adding an arm from $\mathcal{M}^j _ p$.

The leader finds a better arm that has higher empirical rewards but not in $\mathcal{M}^j _ p$. Then she wants to pass the new arm to followers. Because the new arm $a^+ _ p$ might not be in $\mathcal{M}^j _ p$ or $\mathcal{M}^j _ {p-q _ j}$, we can not let followers receive the collision information via the best arm set. Thus, we utilize the whole arm set. The leader continuously selects $a^+ _ p$ for $K$ times. Followers select all arms in a round-robin way. This block continues $K$ times because the length of the original arm is $K$ and we hope to use the original whole arm set to pass the information. In the example, $t _ 5$ to $t _ 6$ denotes the rounds in the second block. We suppose that the leader wants to add arm $1$.

Each follower collides on arm $5$ once. They remember that the collision happens on arm $5$.

The third block is used for passing the ending of exploration.

Leader explores and gradually eliminates all sub-optimal arms from $[K]$. However, as for followers, they do not know when the exploration of the leader ends. If the leader's exploration has ended and passes all optimal arms to followers, continuing to enter the communication phase is a waste of time for followers. Therefore, a block used for passing the ending of exploration is necessary.

In this block, we can utilize $\mathcal{M}^j _ {p-q _ j}$ to pass information. The length of $\mathcal{M}^j _ {p-q _ j}$ is $M$, so this block continues for $M$ times. In multi-player bandits, each player has her optimal arm so we have $M$ optimal arms in total. When the leader eliminates all sub-optimal arms, i.e., there are $M$ optimal arms left, she will send collisions in the third block of the next communication phase. Otherwise, she does not send collisions in this block.

After a period of delay:

Note that the collisions in the first and second blocks can not be received immediately. After a period of delay, follower $j$ receives the position $4$ and the arm to be added is $5$. She also knows the feedback is from phase $2$. Therefore, she updates:

$$\mathcal{M} _ 1^j = \\{4, 2, 6, 3\\} \rightarrow \mathrm{replace\ the\ arm\ in\ position\ 4\ to\ arm\ 5} \rightarrow\mathcal{M}^j_2 = \\{4, 2, 6, 5\\} \\$$

Therefore, although players use the previous arm set $\mathcal{M} _ 1^j$, followers can still receive the correct update information of $\mathcal{M}_2^j$ even though they do not know $\mathcal{M} _ 2^j$.

In summary, the length of $K+2M$ is enough short to pass the information between players. There is no need to design a time-varying length.

Response to Weakness 2:

Q: The paper lacks an analysis of the lower bound for decentralized algorithm, which should be the main focus of the paper.

In decentralized multi-player bandits, players intentionally collide with others to simulate communication, which inevitably results in some regret. Therefore, our goal is to minimize the communication duration and the associated regret. To evaluate this, we compare our results with the centralized lower bound to evaluate how the additional information exchange impacts regret reduction. The goal of decentralized multi-player bandits is to reach the same performance as in the centralized setting. [1, 2, 3] study decentralized multi-player bandits and compare their results with centralized lower bound.

Response to Weakness 3:

 Q: In larger scenarios of experiments, DDSE without delay estimation performs better than DDSE. What is the significance of considering delay estimation in delay estimation algorithms in large-scale scenarios?

We have updated our experimental results. In all of these experiments, only Figure 8(d) shows that DDSE is slightly worse than DDSE without delay estimation. As the red words explained in Appendix B, the interval of each communication phase is $KM\log(T)$, which is large when $K$ and $M$ increase. A large interval makes sure that followers receive feedback from a communication phase before the next communication phase begins.

However, in large-scale scenarios where the delay is very long, i.e., exceeding $KM\log(T)$, players might update the communication results wrongly so that DDSE without delay estimation has a large fluctuation. The fluctuation is also validated in Figure 9(d) where DDSE without delay estimation has a large standard error. In real-world cognitive networks, we can not know the maximum delay in advance. It is impossible to adjust the interval manually. As nodes in cognitive networks increase, real-world delay is also increasing due to the congestion of the network. It is hard to guarantee that a large $K$ or $M$ is enough to balance the delay.

Therefore, DDSE does not need to adjust the interval of each communication phase. No matter what $K$ or $M$ is, and no matter how large the delay is, DDSE always shows a good performance and has a better guarantee. Experiments also show that DDSE is more stable than DDSE without delay estimation. In real-world applications, DDSE is more robust and can adapt to complicated cognitive networks.

Thank you for your comments about our manuscript. We have studied the comments carefully, and find them valuable for improving our paper. The responses to your comments are as follows:

Response to Question 1:

Q: The proposed algorithm takes a leader-follower approach which makes it semi-distributed.

We agree that many works on decentralized MMAB do not need to assume that $M$ and the ID of each player are known. Actually, we have considered this fully decentralized setting at the beginning of our work. In such fully decentralized multi-player bandits, players do not know the existence of others so there is no guarantee to avoid collisions. Thus, decentralized MMAB algorithms need an initialization phase where players utilize collisions to get some information before exploration so that they can select arms in a round-robin way. There are two kinds of methods for initialization.

1. [1, 2, 3] adopt a musical chair method, where each player preempts an arm until no collision happens. After preempting an arm, players then intentionally select some arms. By counting the times of accumulated collision in this period, each player can know $M$ and her ID among these players.
2. In [4], players also try to preempt arms once. If they fail to preempt it, i.e., receive a collision, they will select specific arms later to pass the information that she has not find her arm to other players. When no collision occur, it means that everyone finds the proper arm. Then they perform an procedure similar to [1, 2, 3] and get the information on $M$ and their ID.

However, when delay is introduced to the environment, players can not receive the collision immediately. If the delay is too long, players must wait in the initialization phase to receive the feedback of collision, because they need to get $M$ and their ID to start an exploration where they can select arms in a round-robin way. Actually, players always hope that they should receive some feedback in a certain known period, which conflicts with the scenario where feedback is delayed for an unknown period.

Of course, if we assume that delay is bounded by a known value $d _ {\max}$, the problem of initialization will be solved easily by using the classical technique and waiting for extra $d _ {\max}$ rounds in the beginning. In cognitive radio networks, transmission delay is sometimes bounded by protocol limits, so it is also natural to consider a bounded delay where we can use $d_{\max}$ as the input of algorithms to perform initialization.

Our assumption on delay is more mild than this bounded delay. We allow some exceedingly large and unknown delays in the environment. If the assumption on the initialization does not exist, i.e., players are fully decentralized, we can also implement that pre-mentioned technique in our algorithms. For example, players start with an initialization phase. Although their feedback might not be completed, they still begin to explore arms. If a player in exploration has a collision that should not have happened, she notifies others also by sending collisions at a specific time. After a period of delay, players receive the signal and start an initialization again. Then comes the next exploration. By doing so, it is possible to give a probability guarantee using our sub-Gaussian delay assumption. However, it will make the notation more complicated. The existing problem is enough challenging and our work is the first paper to handle delay in multi-player bandits where a collision occurs when selecting the same arm. Our goal is to pave the way for further study in this area. A fully decentralized MMAB can be discussed in future work.

Response to Question 2:

Q: What is the rationale behind Assumption 1? What are the components of delay? For example, does it contain queueing delay? How practical is the consideration of sub-Gaussian delay?

Rationale behind Assumption 1

The rationale behind Assumption 1 lies in providing a realistic yet mathematically tractable model for network delays in multi-player bandit problems. In real-world networks, transmission delays are inherently bounded by physical and protocol limits, which prevent excessively large values. A common assumption on delay is that all delay is bounded by a fixed value $d_{\max}$. However, we choose not to rely on this assumption. Instead, we propose a more flexible sub-Gaussian assumption that permits larger delays but with a low probability of occurrence. It is worth noticing that our assumption is more general than bounded delay, as all bounded random variables are inherently sub-Gaussian. In our analysis, we leverage the property of exponential decay in the tail probabilities characteristic of sub-Gaussian distributions.

Components of delay

In cognitive radio networks, delay typically consists of several components, depending on the communication process and network architecture. These components can include:

1. Propagation Delay: The time required for a signal to travel from the transmitter to the receiver across the communication medium.
2. Transmission Delay: The time taken to push all the bits of a packet onto the transmission medium. It depends on the packet size and the bandwidth of the link.
3. Processing Delay [5]: The time spent on processing tasks, such as spectrum sensing, packet routing, and other computational operations required before transmission.
4. Queueing Delay [6, 7]: The time an SU's data packet spends in a queue, either at the SU’s transmitter or at network devices (e.g., routers or base stations), waiting to be transmitted. Queueing delay occurs due to competition among SUs for limited resources, such as unoccupied PU channels or transmission opportunities.

Thus, queueing delay is an important and common component of the overall delay in cognitive radio networks.

How practical is our assumption

As stated before, sub-Gaussian delay is practical and well-suited to the dynamic nature of cognitive radio networks. Sub-Gaussian delay models are characterized by exponential tail decay, which reflects the typical behavior of delays in real-world systems. Most delays are relatively small, but occasionally, larger delays can occur with diminishing probability. This is particularly relevant for cognitive radio networks, where delays may arise from dynamic spectrum access or contention among secondary users for idle channels. Moreover, our assumption is a generalization of bounded delay. Compared with [8, 9, 10], sub-Gaussian delay allows for rare occurrences of larger delays while maintaining tractability. This makes it more flexible and realistic for cognitive radio networks.

Response to Question 3:

Q: Concerns about fixed users in the system.

If players are not fixed, the setting is called asynchronous multi-player bandits. In this setting, players can enter the game and leave at any time. The latest study on asynchronous MMAB is [11]. However, [11] relies on several assumptions:

1. There exists a centralized environment, where players can freely communicate with others.
2. Although players enter the game at different times, they leave at the same time $T$.
3. At each time, the probability that every player enters the game is the same and known.

The area of centralized asynchronous MMAB without assumptions is still blank, let alone decentralized asynchronous MMAB. In decentralized bandits, the delay has already significantly complicated the problem because players rely on the feedback of collisions to get some information from other players. Incomplete feedback causes inconsistency between players, leading to staggered exploration, frequent collisions, or premature exploitation. We expect to discuss it in the future work.

Response to Question 4:

Q: It is not clear why there is a provision of eliminating arms for which LCB is bigger than UCB. Please specify the motivation behind the virtual communication phase in details.

Arm Elimination

In multi-player bandits, there are $M$ players and $K$ arms. The ultimate goal is that every player is assigned an optimal arm. Thus, there exist at least $M$ optimal arms. In our algorithms, the leader explores all arms and puts $M$ arms with the $M$-th highest empirical rewards into the best arm set $\mathcal{M} _ p^j$. Therefore, if the potential reward of arm $k$ is worse than that of at least $M$ arms, it should be considered a bad arm because we already have at least $M$ arms that are better than $k$. Then we can eliminate arm $k$. To evaluate how the "potential reward" is, we introduce the LCB and UCB which are lower confidence bound and upper confidence bound [12]. They are separately defined as:

$$LCB_t(k):=\hat{\mu}_k(t) - \sqrt{\frac{2\log(T)}{n_t(k)}},\ UCB_t(k):=\hat{\mu}_k(t) + \sqrt{\frac{2\log(T)}{n_t(k)}}.$$

$\hat{\mu}_k(t)$ is the empirical reward expectation of arm $k$ at time $t$ and $n_t(k)$ denotes the number of times that the leader receives feedback on arm $k$ up to $t$. If $UCB_k(t)$ is higher, we deem that arm $k$ is better. In the equation, the higher first term $\hat{\mu}_k(t)$ means higher current rewards, which represent exploitation. Note that $T$ is the total time and $n_t(k)$ indicates how familiar we are with this arm. Higher $T$ and lower $n_t(k)$ indicate that we have less knowledge of arm $k$. Thus, the higher second term $\sqrt{\frac{2\log(T)}{n_t(k)}}$ means the degree of uncertainty, which represent exploration. By Hoeffding's inequality, we have

$$P\left(\left|\hat{\mu}_k(t)-\mu_k\right| \leq \sqrt{\frac{2\log(T)}{n_t(k)}}\right) \geq 1-2(\frac{1}{T})^4$$

Thus, by picking an arm with the highest UCB, the player can finally find the optimal solution. In our algorithms, if the UCB of arm $k$ is worse than at least $M$ arms' LCB, the arm $k$ will be eliminated because optimal arms exist in the left arms. By eliminating arms gradually, the leader can find $M$ optimal arms in total.

Motivation behind Virtual Communication

We have modified our algorithms by removing the notation of $\mathcal{M} _ {com}$ as reviewer WghT suggested. Here we briefly describe the communication phase. The leader passes the update of $\mathcal{M} _ p^j$ to followers at each communication phase. In the communication phase, collisions represent removing or adding an arm to $\mathcal{M} _ p^j$. The collision is also used for passing the ending signal of exploration. However, if $\mathcal{M} _ p^j=\mathcal{M} _ {p-1}^j$ and the exploration does not end, it is not necessary for the leader to pass information in the communication phase. From the point of followers, they do not know which communication phase does not have information, so they choose to enter every communication phase between a fixed gap. To maintain alignment with followers, the leader should enter a "virtual communication" phase if she does not want to pass any information. In virtual communication, the leader selects arms with followers and does not send collisions. Later, if followers do not receive any feedback from certain communication phase, they can know that the best arm set $\mathcal{M} _ {p}^j$ is the same as the prior best arm set $\mathcal{M} _ {p-1}^j$.

If virtual communication does not exist, we have the following problems: (1) Because followers always enter a communication phase between a fixed gap, in the second block of communication, they select arms from the whole arm set $[K]$. If the leader does not make adjustments, she might collide with followers. This collision will be regarded by followers as information about adding an arm, but actually, the information is wrong. (2) Followers update $\mathcal{M} _ {p}^j$ based on $\mathcal{M} _ {p-1}^j$, if $\mathcal{M} _ {p-1}^j$ is blank or wrong as (1) mentioned, the updated $\mathcal{M} _ {p}^j$ might also be wrong.

Therefore, virtual communication is critical in our algorithm.

Response to Question 5:

Q: Please provide a pointer.

Thank you for your comment. We have updated the paper to include a clear reference to the result where the upper bound on the feedback delay is derived. This result is now explicitly linked to Lemma 1.

Response to Question 6:

 Q: Can the authors quantify the gap between the lower bound and upper bound on the regret of the proposed algorithm?   Thank you for the suggestion. We have updated the paper to address this point. The first term in Theorem 2 (regret of DDSE) is aligned with Theorem 1 (lower bound) up to constant factors. The observed difference comes from the decentralized setting, where players cannot directly communicate about rewards or collisions. Importantly, the regret introduced by the decentralized structure and delay remains independent of $T$. Therefore, our result is near-optimal.