Multi-player Multi-armed Bandits with Delayed Feedback

1 Introduction

Multi-armed Bandits (MAB) is a classic framework widely applied in diverse fields such as online advertising, clinical trials, and recommendation systems [Lattimore and Szepesv´ari, 2020]. In this framework, at each time s, a single player sequentially selects an arm k from a finite set [K] := {1, ...,K} and receives a random reward Xk(s). However, in many real-world scenarios involving multiple users, the standard MAB framework may fail to capture the complexities. For instance, in cognitive radio systems designed to efficiently share spectrum resources among users, a key distinction from the traditional MAB problem is that when multiple users select the same channel, they collide and no message is transmitted. This situation motivates multiplayer multi-armed bandits (MP-MAB) framework in which M players simultaneously pull arms. If two or more players pull the same arm, their rewards turn to zero which represents failed transmission.

∗Corresponding author.

A problem is referred to as centralized when players can freely communicate about their actions and rewards through a central coordinator at each time step. In this scenario, players coordinate their actions using shared information without cost [Komiyama et al., 2015]. Yet the centralized setting incurs significant energy costs in cognitive radio networks. To address this limitation, recent research has shifted focus to the decentralized MP-MAB, where each player has access only to her own information, and explicit communication is prohibited. Many studies develop implicit communication by intentionally inducing collisions to pass binary information [Boursier and Perchet, 2019; Wang et al., 2020; Shi et al., 2020]. The mechanism enables players to fully utilize the information of others and achieve performance comparable to the centralized setting, but it relies on synchronous feedback from all players.

However, in practical networks, a more realistic scenario involves users experiencing delay due to various inherent factors, including spectrum analysis, heterogeneous link layer protocols, path loss, and wireless link errors [Akyildiz et al., 2006; Ahmad et al., 2020]. Although the MP-MAB problem has been well studied, most existing approaches struggle in the presence of delayed feedback [Shi et al., 2021; Huang et al., 2022]. In decentralized settings, players rely on immediate feedback to perform implicit communication, and delays break this mechanism, leading to frequent collisions and poor exploration efficiency.

While single-player MAB with delayed feedback has been extensively studied, these approaches cannot be directly applied to multi-player settings, as they may lead to competition and frequent collisions among players. Specifically, in single-player MAB, a player selects an arm but observes the reward only after a period of delay [Joulani et al., 2013; Lancewicki et al., 2021; Tang et al., 2024]. However, when multiple players are involved, they tend to compete for the same optimal arm, leading to frequent collisions. Also note that, in single-player bandits, although delayed feedback primarily affects the timeliness of updates, each feedback is substitutable over time. Specifically, if one is delayed, subsequent feedback can still guide learning. In contrast, in the multi-player setting, some feedback is irreplaceable: missing it may lead to miscoordination and persistent collisions. These collisions are particularly harmful, as players pulling the same arm receive no reward, resulting in significant regret. Therefore, a key challenge for MP-MAB with delayed feedback lies in maintaining coordination even with incomplete or delayed feedback. In this paper, we address this challenge, and our contributions are presented below.

1.1 Contribution

Motivated by the pressing challenge of delay in cognitive radio networks, we propose a novel bandit framework of multiplayer multi-armed bandits with stochastic delay which follows a σ2 -sub-Gaussian distribution with expectation E[d]. For this problem, we introduce an algorithm DDSE (Delayed Decentralized Successive Elimination), where every player maintains a set of arms with the highest empirical rewards at each time. They estimate the delay and choose a set of arms updated from an earlier time slot, which is considered to be consistent with the choices of all players with high probability. By selecting arms from the identical arm set, players avoid collisions and mitigate the impact of delay. They also engage in implicit communication with other players by pulling arms from the identical arm set, thereby utilizing the exploration results of others. Therefore, this approach efficiently addresses the challenge outlined in Section 1.

Table 1 compares the regret bound of our algorithm with DSE (Decentralized Successive Elimination), which is a simplified version of DDSE. In DSE, players directly select arms in the latest updated set of arms with the highest empirical rewards, leading to a regret of O(exp(E[d]/KM + σ2 d /K2M 2 )) which grows exponentially with increasing E[d] and σ2 d . Through careful algorithm design, DDSE successfully prevents this exponential term. The term O( M ∑k>M ∆1,k K-M ˜ d3) in DDSE is the regret that players coordinate with each other to select the same set of best empirical arms. Compared with O( M ∑k>M ∆1,k K-M E[d]) in the centralized upper bound, the regret of our algorithm in the decentralized setting differs by only O( M ∑k>M ∆1,k K-M √σ2 d log(K)), which diminishes when the delay remains stable, i.e., σ2 d approaches zero. Additionally, we establish a lower bound in Table 1, demonstrating that our regret bound is near-optimal. We also extensively evaluate DDSE through a large number of experiments, validating its effectiveness across various delayed feedback scenarios.

1 Simplified version of DDSE. In this algorithm, players do not estimate delay and use the latest set of arms.

2 RelatedWork

The problem of multi-player multi-armed bandits has recently been studied in different settings in the existing literature, where most of the efforts have concentrated on the decentralized setting. Boursier and Perchet [2019] propose an implicit communication mechanism where players intentionally collide to signal information, achieving performance comparable to centralized approaches. Wang et al. [2020] improve this communication phase by electing a leader and only allowing the leader to communicate with followers. Research also has focused on heterogeneous reward settings [Besson and Kaufmann, 2018; Bistritz and Leshem, 2018; Tibrewal et al., 2019; Shi et al., 2021], adversarial collision scenarios [Mahesh et al., 2022], incomplete feedback [Boursier and Perchet, 2019; Shi et al., 2020; Lugosi and Mehrabian, 2022; Huang et al., 2022], and shareable arms Wang et al.; Xu et al. [2022; 2023]. Recently, Richard et al. [2024] consider asynchronous multi-player bandits in the centralized setting and derive a constant or logarithmic regret.

There has been growing interest in stochastic delay in multi-armed bandits. Vernade et al. [2017] investigate delayed Bernoulli bandits, although their approach requires knowledge of the delay distribution. Pike-Burke et al. [2018] consider scenarios where a sum of observations is received after some stochastic delay. Zhou et al. [2019] explore contextual bandits with stochastic delay. Arm-dependent delay is discussed by Gael et al. [2020], and Lancewicki et al. [2021] later remove the restriction on delay distribution. Tang et al. [2024] focus on strongly reward-dependent delay and achieve near-optimal results. Yang et al. [2024] propose a reductionbased framework to handle delays with sub-exponential distributions.

A similar setting to ours is multi-agent bandits with delay. Existing literature has focused on decentralized cooperative bandits [Cesa-Bianchi et al., 2016; Mart´ınez-Rubio et al., 2019], while non-cooperative game with delay is discussed in Bistritz et al.; Bistritz et al. [2019; 2022]. Zhang et al. [2023] consider multi-agent reinforcement learning with both finite and infinite delay. Li and Guo [2023] discuss adversarial bandit problem with delayed feedback from multiple users. Hanna et al. [2024] propose an algorithm in multiagent bandits with delay and derive a sub-linear regret. However, none of these works consider collisions between players. Since collisions result in a loss of reward, current algorithms in multi-agent bandits cannot be directly applied to our problem.

3 Preliminaries

We consider a multi-player multi-armed bandits problem with delayed feedback. Denote by M the number of players and K the number of arms. Let T denote the time horizon. At each time s ∈ [T], every player j selects an arm k and has a reward which she does not observe immediately. Denote by πjs the arm that is selected by player j at s. If more than one player selects the same arm at the same time, a collision occurs, and their reward turns to zero. Define ηk(s) := 1{|Ck(s)| > 1} as the collision indicator where Ck(s) := {j ∈ [M] | πjs = k} is the set of players who pull the same arms at time step s. After a period of delay djs , at time t such that s + djs = t, player j receives ηk(s) and a reward rj (s) := Xjk (s) [1 - ηk(s)], where Xjk (s) is drawn i.i.d. from an unknown fixed distribution with expectation µk ∈ [0, 1]. Note that K > M so that there is at least one arm available for each player without mandatory overlap or collision. Denote by [M] the set of all players and [K] the set of arms. The expected regret is defined as

where µ(j) is j-th order statistics of µ, i.e. µ(1) ≥ µ(2) ≥ ... ≥ µ(K).

Define d(θ) := min{γ ∈ N|P (d ≤ γ) ≥ θ} as the quantile function of the delay distribution. We consider the following assumption.

Assumption 1. Let {djt }T,M t=1,j=1 denote independent nonnegative random variables with sub-Gaussian distribution. Denote by σ2 d the sub-Gaussian parameter and E[d] the expectation of the distribution. Then for any a > 0,

Assumption 1 models the delay as a light-tailed random variable, where larger delays occur with lower probability. This behavior is consistent with real-world networks, where delays often arise from bounded processing times, network latency, or short-term queuing, and are typically constrained by hardware and protocol limitations [Azarfar et al., 2015]. As a result, sub-Gaussian distributions provide a realistic and analytically tractable model for capturing such stochastic delays.

Algorithm 1 DDSE (Leader with j = M)

Input: K (number of arms), M (number of players), T

• 1: InitializeMj0 randomly, K = [K], p = 0, qj = 0, ˆµjd = 0, (ˆσ2 d )j = 0, ˆµk(t) = 0. 2: while t ≤ T do 3: Explore inMjp-qj and K/Mjp-qj . 4: if j receive a feedback from time s then 5: djs ← t - s . 6: Update ˆµjd , (ˆσ2 d )j , ˆµk(t) accordingly. 7: end if 8: Remove fromK the arm k satisfying: |{i | ∀i ̸= k, i ∈ K s.t. LCBt(i) ≥ UCBt(k)}| ≥ M. 9: if t mod (KM⌈log(T)⌉) = 0 then 10: p ← p + 1. 11: Mjp ← {k | ˆµk(t) ranks in the top-M of ˆµi(t). for all i ∈ K}. 12: ifMjp ̸=Mjp-1 then 13: Communication(). 14: else VirtualCom(Mjp-qj ). 15: end if 16: Find qj s.t. (1). 17: end if 18: if |K| = M and qj = 0 then 19: Select Mjpmax (j) until T . 20: end if 21: end while

Considering cognitive wireless sensor networks, sensor nodes are usually pre-deployed [Joshi et al., 2013], so they are equipped with information on the total number of nodes and their ID. Consequently, we assume that each player in our algorithms is initialized with her ID among all players and is aware of the total number of players. Discussion on removing this assumption is in Appendix G.

4 Algorithm

The proposed algorithm DDSE (Delayed Decentralized Successive Elimination) is composed of exploration phase, communication phase and exploitation phase. Denote by pmax the maximum number of communication phases within a given time horizon. Mjp denotes the set of the top M arms with highest empirical rewards for player j during the p-th communication phase. We have |Mjp | = M for all j ∈ [M] and p ≤ pmax. The key idea of DDSE is to estimate delay and pick Mjp-q after the p-th communication phase, so that Mjp-q = Mℓp-q for j ̸= ℓ with high probability. To better understand our algorithm, we also give an example in Appendix B.

4.1 Exploration Phase

We assign each player an ID j and initialize Mj0 for each player j ∈ [M]. The player with j = M becomes the leader, and others are followers. Algorithm 1 describes DDSE from the view of the leader. The algorithm from the view of follow-

Algorithm 2 Communication (Leader with j = M)

1: Initialize ia-, a+ by comparingMjp andMjp-1 . Part 1: Remove Arm 2: for M time steps do 3: SelectMjp-qj (ia-). 4: end for Part 2: Add Arm 5: for K time steps do 6: Select a+. 7: end for Part 3: Notify End 8: for M time steps do 9: if |K| =M then 10: pmax ← p. 11: i ← [t mod M]. 12: Select Mjp-qj (i). 13: else 14: Select Mjp-qj (j). 15: end if 16: end for

ers is in Appendix B. Define Nt(k) := ∑s<t 1{πjs = k, j = M} as the number of times that the leader chooses arm k before t. Also define nt(k) := ∑s<t 1{πjs = k, djs + s < t, j = M} as the number of received feedback of the leader from arm k before t. Denote by K the active arm set, and it is initialized with K = [K]. The leader selects arms from K in a round-robin way. When receiving the feedback of arm k at t in the exploration phase, she updates

where ˆµk(t) := Sk(t)/nt(k) is the empirical reward of arm k and Sk(t) is the sum of rewards that the leader has collected on arm k by the end of time t. During the exploration phase, the leader eliminates an arm k from K at t if there exist more than M arms whose lower confidence bounds are bigger than UCBk(t).

When t mod KM⌈log(T)⌉ = 0, the leader enters a new communication phase. She sorts ˆµk(t) and places the arms corresponding to the top M highest ˆµk(t) into Mjp . If Mjp has changed, the leader communicates the update to the followers by sending collisions in Communication. Otherwise, she runs a VirtualCom, during which no collisions are sent. Details about VirtualCom are in Appendix B. From the perspective of a follower ℓ, it takes time for her to receive the update because of the delay. However, since the leader only communicates with followers after Mjp has changed, if follower ℓ has not received the update, Mjp ̸=Mℓp . Therefore, players need to pick a previous set Mjp-qj , which is considered to be received by all players with high probability. Specifically, by the sub-Gaussian property of delay, we know that when

Algorithm 3 Communication (Follower j)

1: Com←Com ∪ {(t, t +M +K)}. 2: Use←Use ∪ {p- qj}. Part 1: Remove Arm 3: for M time steps do 4: i ← [(t + j) mod M]. 5: SelectMp-qj (i). 6: end for Part 2: Add Arm 7: for K time steps do 8: i ← [(t + j) mod K]. 9: Select the i-th arm in [K]. 10: end for Part 3: Notify End 11: for M time step do 12: SelectMjp-qj (j). 13: end for 14: if j has received two collisions ηk(s), ηk′(s′ ) such that ∃i, s < s′ , s ∈ Com(i) and s′ ∈ Com(i) then 15: t0, t1 ← Com(i). 16: p0 ← t0/KM⌈log(T)⌉ and u ←Use(i). 17: ia- ← the index of k in Mju and a+ ← k′ . 18: Mjp0 (ia-) ← a+. 19: end if

Mjp is received by all followers with high probability. When a player j receive a feedback at time t, she update the estimation of E[d] and σ2 d with

Thus, each player j aims to find qj ∈ N such that

Then in exploration phase, followers only select arms from Mjp-qj in a round-robin way. To avoid collision with followers and ensure sufficient exploration, the leader first selects arms inMjp-qj with followers. Then she selects other arms in K in a round-robin way while skipping arms in Mjp-qj . In other words, the leader constantly explores all arms except those that have been eliminated. An example of the process of arm selection is in Appendix B.

Sub-optimal arms in K are gradually eliminated by the leader. When |K| = M, she tells the final result to followers in the next communication phase. After that, the leader remains in the exploration phase until qj = 0, at which point she moves to the exploitation phase and pulls Mjpmax (j). When a follower j receives the final update and finds qj = 0, she also begins the exploitation phase and continuously selects armMjpmax (j) until T .

4.2 Communication Phase

Players begin a communication phase at time t such that t = KM⌈log(T )⌉. The length of each communication phase is K + 2M. Motivated by Wang et al. [2020], the communication phase in our algorithm is divided into three parts. The first and second parts are used for removing and adding an arm inMp. The third part is used for the leader to send the ending signal. Let a- denote the arm to remove and a+ the arm to add. Given a list A, let ik denotes the index of item k in A such that A(ik) = k.

Part 1: Remove Arm

The leader firstly initializes ia- and a+ by comparing the difference between Mjp and Mjp-1 . Followers save the time duration of current communication phase to Com and save p - qj to Use. Then in this part, the leader selects arm MMp-qj (ia-) for M consecutive rounds. Meanwhile, followers select arms fromMjp-qj in a round-robin way, ensuring that each follower collides once with the leader. The round of collision represents the index of the arm to be removed. Since Mp is ordered for all p ≤ pmax, followers can receive the update of the leader to remove arm a- fromMjp by selecting arms inMjp-qj . Thus, the information is passed successfully even if Mjp is incomplete for follower j, allowing our algorithm to adapt to large delays.

Part 2: Add Arm

In this part, the leader continuously selects a+ for K rounds while followers select arms in [K] in a round-robin way. Each follower also collides once with the leader. The collision denotes the arm to be added. Later, if a follower j receives two collisions ηs(k) and ηs′ (k′ ) where s < s′ and they belong to the same Com(i), we say that she has completely received an update of a communication phase in which the updated result should be stored in Mp0 with p0 = t0/KM⌈log(T)⌉ and t0 ∈ Com(i). Since Use saves the index (p - qj) of Mjp-qj that player j uses in each communication phase p ≤ pmax, the index at communication phase p0 is u := Use(i). Thus, follower j finds the index of k inMju is ia- and then places a+ in the position of Mjp0 (ia-), which does not break the order of Mjp0 .

Part 3: Notify End

If |K| = M, it indicates that all sub-optimal arms have been eliminated and the leader selects arms in Mjp-qj sequentially, while followers continuously select armMjp-qj (j) for M times. Otherwise, the leader does not send collisions by selecting Mjp-qi (j) for M times. Finally, each follower receives a collision, which is a symbol of the end of exploration.

The reason why the beginning of our communication phase is fixed rather than starts asMjp changes is that players need to ensure synchronization with others. In Wang et al. [2020], the leader sends a collision to followers as the beginning signal of communication. However, when the feedback of this collision is delayed, followers hardly receive it at the same time and then stagger with the leader. Once players are not aligned with others, followers may receive incorrect information during the communication phase. Furthermore, since communication and exploration are alternating, players might end up selecting the same arm during the exploration phase, resulting in collisions.

Denote by p′ a communication phase such that Mjp′ is the most recent to have been completely received by player j. If the delay is sufficiently small, players can receive the feedback from the p-th communication phase before the (p+1)-th communication begins. Then q is equal to zero in our algorithm, and players continue selecting arms from Mjp . We discuss DSE, which is a simplified version of DDSE, where players directly pull arms inMjp′ . This version does not estimate ˆµjd or (ˆσ2 d )j and also does not coordinate players to pull in the same set of best empirical arms. Details on DSE are presented in Appendix B.

5 Theoretical Analysis

In this section, we provide a comprehensive analysis of our algorithms, examining both the decentralized and centralized settings. Additionally, we derive a lower bound to demonstrate the near-optimality of the regret upper bound.

5.1 Centralized Lower Bound

Note that a key objective in decentralized MP-MAB is to match the performance of the centralized setting. In the centralized case, a central coordinator enables communication without incurring any regret. In contrast, players in the decentralized setting rely on implicit communication, typically through intentional collisions, which inevitably induces some regret. The goal is to ensure that this communication-induced regret remains a constant, independent of the time horizon T. Therefore, comparing the regret of decentralized algorithms against the centralized lower bound is both meaningful and standard [Boursier and Perchet, 2019; Shi et al., 2020; Shi et al., 2021]. Theorem 1 presents a centralized lower bound for MP-MAB with delays. Full proof of this theorem is provided in Appendix F.

Theorem 1. For any sub-optimal gap set S∆ = {∆M,k | ∆M,k = µ(M) - µ(k) ∈ [0, 1]} of cardinality K -M and a quantile θ ∈ (0, 1), there exists an instance with an order on S∆ and a delay distribution under Assumption 1 such that

5.2 Regret of DDSE

Theorem 2 presents our main result, which establishes the regret upper bound of DDSE in the decentralized setting. The complete proof of Theorem 2 is provided in Appendix C.

Theorem 2. In decentralized setting, for delay distribution under Assumption 1, given any K,M, µ and a quantile θ ∈ (0, 1), the regret of DDSE satisfies

Only the first terms in (2) and (3) are related to T. Term A is aligned with term I up to constant factors. Term E arises due to the decentralized environment and is not related to delay. Regarding delay, a comparison of term II with terms B, C, and D reveals that the difference on K and M is only O( 1 1-M/K )√log(K). This indicates that the regret caused by delay does not increase rapidly as K and M increase. Therefore, our result is near-optimal.

Moreover, since the decentralized setting is generally more challenging than the centralized one, the near-optimality of our result (Theorem 2) with respect to the centralized lower bound further highlights the strength of our approach. We also establish a centralized upper bound for DDSE in Corollary 1, with the proof provided in Appendix D.

We also analyze the regret of DDSE in the centralized setting, where players can freely exchange information. The regret upper bound is presented in Corollary 1.

Corollary 1. In centralized setting, for delay distribution under Assumption 1, given any K,M, µ and a quantile θ ∈ (0, 1), the regret of DDSE satisfies

When DDSE is executed in the centralized setting, followers are immediately aware of the leader's latest exploration results. Once the leader identifies the optimal set of armsM∗ , exploitation begins without incurring the regret of O(σd log(K)) in term C. Comparing with term II in Theorem 1 and term F, G, D, we note that the regret due to delay differs by O( 1 1-M/K ) on K and M. Proof of Corollary 1 is provided in Appendix D.

5.3 Regret of DSE

This section presents the regret of DSE, where players do not adjust to the sameMjp-qj . Theorem 3 shows that it is critical to maintain consistency between players. The detailed proof is included in Appendix E.

Theorem 3. In decentralized setting, for delay distribution under Assumption 1, given any K,M, µ and a quantile θ ∈ (0, 1), the regret of DSE is bounded by

If players do not estimate the delay and pull arms inMjp′ , followers will collide with the leader after each communication phase ends. This happens because the leader begins communication after she updates Mjp , while the followers have not yet received this update, ultimately contributing to termH. Additionally, followers receive incorrect information during the communication phase ifMjp′ ̸=Mℓp′ , which leads to an exponential regret in term J.

Compare Theorem 3 with Theorem 2 and we find by using Mjp-qj instead of Mp′ , players will not collide with each other after the communication ends, thereby avoiding term H, which could be large when ∆2M,k is sufficiently small. Moreover, since Mp- qj j = Mp- qℓ ℓ for all j, ℓ ∈ [M] with high probability, followers receive consistent information from the leader. As a result, the regret due to asynchronous feedback and coordination errors is reduced from O(exp(E[d])) in term J to O(E[d]) in Theorem 2, highlighting the effectiveness of our delay-aware coordination mechanism.

Remark 1 (OnRelaxingAssumption 1). The analysis relies on Assumption 1, which is used to estimate the delay quantile. Specifically, the sub-Gaussian assumption allows us to derive high-probability bounds on delay, which are essential for player coordination. Similar guarantees can also be obtained under sub-exponential delay distributions.

More generally, since our goal is to estimate a delay threshold d such that most delays fall below it, the delay quantile can be estimated directly without assuming a specific distribution. Given a quantile level θ, the number of observed delays below d follows a Binomial(n, θ) distribution, where n is the number of samples. This enables us to bound the quantile estimation error using standard binomial tail inequalities in a distribution-free manner. We believe this quantile-based approach offers a promising direction for extending our algorithm to settings with heavy-tailed or unknown delay distributions, which we leave as future work.

6 Experiments

We conduct experiments to validate our theoretical results. Let ∆ := ∑K-1 k=1 µ(k)-µ(k+1) K-1 denote the average reward gap between consecutive arms. Each experiment runs for T = 300,000 rounds and is averaged over 20 trials. Default parameters are K = 20, M = 10, E[d] = 200, σd = 100, and ∆ = 0.05. We assume Gaussian rewards and compare DDSE with DSE; SIC-MMAB [Boursier and Perchet, 2019], MCTopM, RandTopM, Selfish [Besson and Kaufmann, 2018]; Game of Throne [Bistritz and Leshem, 2018]; and ESER [Tibrewal et al., 2019]. Real-world results are reported below, while numerical simulations are deferred to Appendix A.

We evaluate our algorithms using real-world spectrum data collected in Finland by the 5G-Xcast project 2 . Figure 1 shows a sample of power measurements across four bands. In cognitive radio networks, secondary users share spectrum with primary users without causing interference. Multi-player bandit algorithms help secondary users identify available channels. A channel is considered occupied by a primary user if its power measurement exceeds the threshold of -90 dBm, as in Alipour-Fanid et al. [2022]. We assess performance using cumulative throughput and collisions [Wang et al., 2021; Alipour-Fanid et al., 2022]. Throughput is computed using Shannon's formula:

where W denotes bandwidth and SNR denotes signal to noise ratio. No throughput is achieved when a user selects a busy channel or experiences a collision.

Figure 2(a) illustrates the cumulative throughput over time for different algorithms. Our algorithm, DDSE, achieves the highest throughput, demonstrating its effectiveness. DSE performs slightly worse than DDSE due to the inconsistent Mjp . Selfish also shows an increasing throughput as time progresses. However, as the name suggests, players in the Selfish algorithm explore independently without communication. In contrast, our DDSE algorithm leverages an adjusted form of implicit communication that is robust to incomplete feedback, making it more effective in the presence of delays.

Figure 2(b) compares the cumulative collisions across various algorithms. Notably, DDSE achieves a remarkably low level of cumulative collisions due to the carefully designed nature of our algorithm. It is worth mentioning that ESER

2 The full dataset used in this experiment is publicly available at https://zenodo.org/records/1293283.

(a) Throughput

experiences nearly zero collisions, thanks to its unique mechanism, where players select fixed arms in a round-robin fashion during the exploration phase and pull their optimal arms during the exploitation phase. In contrast, DDSE allows most players (i.e., followers) to exploit arms in Mjp , while the leader explores and updates her results for the followers. Although this method incurs slightly higher collisions than ESER, DDSE achieves a higher throughput, demonstrating its superior performance in terms of overall efficiency.

7 Conclusion

In this paper, we proposed the algorithm DDSE for multiplayer bandits with delayed feedback and derive a regret upper bound. Rather than allowing players to update blindly, coordinating to maintain consistency with other players significantly improves performance and reduces regret. The lower bound in the centralized setting further shows that our algorithm is near-optimal. Practical simulations have also validated the superiority of our algorithm.

A promising direction for future work is to relax the subGaussian delay assumption. As discussed in Remark 1, our framework can potentially be extended to handle heavy-tailed or unknown delay distributions using a quantile-based estimation approach. Another direction is to study playerdependent delays in MP-MAB, as delays in cognitive networks often depend on user-specific factors such as location and device capability.

Acknowledgements

The corresponding author Shuai Li is supported by National Natural Science Foundation of China (62376154).