Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and Generalization
Year: 2021

Abstract:
Despite the significant interests and many progresses in decentralized multi-player multi-armed bandits (MP-MAB) problems in recent years, the regret gap to the natural centralized lower bound in the heterogeneous MP-MAB setting remains open. In this paper, we propose BEACON – Batched Exploration with Adaptive COmmunicatioN – that closes this gap. BEACON accomplishes this goal with novel contributions in implicit communication and efficient exploration. For the former, we propose a novel adaptive differential communication (ADC) design that significantly improves the implicit communication efficiency. For the latter, a carefully crafted batched exploration scheme is developed to enable incorporation of the combinatorial upper confidence bound (CUCB) principle. We then generalize the existing linear-reward MP-MAB problems, where the system reward is always the sum of individually collected rewards, to a new MP-MAB problem where the system reward is a general (nonlinear) function of individual rewards. We extend BEACON to solve this problem and prove a logarithmic regret. BEACON bridges the algorithm design and regret analysis of combinatorial MAB (CMAB) and MP-MAB, two largely disjointed areas in MAB, and the results in this paper suggest that this previously ignored connection is worth further investigation.

heading: 1 Introduction
text: Motivated by the application of cognitive radio (Anandkumar et al., 2010, 2011; Gai et al., 2010), the multi-player version of the multi-armed bandits problem (MP-MAB) has sparked significant interests in recent years. MP-MAB takes player interactions into account by having multiple decentralized players simultaneously play the bandit game and interact with each other through arm collisions.
Prior MP-MAB studies mostly focus on the homogeneous variant, where the bandit model is assumed to be the same across players (Liu and Zhao, 2010; Rosenski et al., 2016; Besson and Kaufmann, 2018). Recent attentions have shifted towards the more general MP-MAB model with player-dependent bandit instances (i.e., the heterogeneous variant) (Bistritz and Leshem, 2018, 2020; Tibrewal et al., 2019; Boursier et al., 2020). However, unlike the homogeneous variant, the current understanding of the heterogeneous setting is still limited.
• Recent advances (Boursier and Perchet, 2019; Wang et al., 2020) show that for the homogeneous setting, decentralized MP-MAB algorithms can achieve almost the same performance as centralized ones. However, state-of-the-art results in heterogeneous variants still have significant gaps from
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
the centralized performance. It remains an open problem whether a decentralized algorithm can approach the centralized performance for the heterogeneous MP-MAB variant. • All prior MP-MAB works are confined to a linear system reward function: the system reward is the sum of individual outcomes from players. However, practical system objectives are often captured by more complicated nonlinear reward functions, e.g., the minimal function (see Section 5.1).
In this paper, we make progress in the aforementioned problems for decentralized heterogeneous MPMAB. A novel algorithm called BEACON – Batched Exploration with Adaptive COmmunicatioN – is proposed and analyzed. In particular, this work makes the following contributions.
• BEACON introduces several novel ideas to the design of implicit communication and efficient exploration. For the former, a novel adaptive differential implicit communication (ADC) scheme is proposed, which can significantly lower the implicit communication loss compared to the state of the art. For the latter, core principles from CUCB (Chen et al., 2013) are incorporated with a batched exploration design, which leads to both efficient and effective explorations. • For the linear reward function, we rigorously show that regret bounds of BEACON, both problemdependent and problem-independent, not only improve all prior regret analyses but more importantly are capable of approaching the centralized lower bounds, thus answering the aforementioned open problem positively. • We then propose to generalize the study of heterogeneous MP-MAB to general (nonlinear) reward functions. BEACON is extended to solve such problems and we show that it achieves a regret of O(log(T )), where T is the time horizon. The analysis itself holds important value as it bridges the regret analysis of combinatorial MAB (CMAB) and MP-MAB. • BEACON achieves impressive empirical results. It not only outperforms existing decentralized algorithms significantly, but indeed has a comparable performance as the centralized benchmark, hence corroborating the theoretical analysis. Remarkably, BEACON with the linear reward function generally achieves ∼ 6× improvement over the state-of-the-art METC (Boursier et al., 2020).

heading: 2 Problem Formulation
text: A decentralized MP-MAB model consists of K arms and M players. As commonly assumed (Bistritz and Leshem, 2020; Boursier et al., 2020), there are more arms than players, i.e., M ≤ K, and initially the players have knowledge of K but not M . Furthermore, no explicit communications are allowed among players, which results in a decentralized system. Also, time is assumed to be slotted, and at time step t, each player m ∈ [M ] chooses and pulls an arm sm(t) ∈ [K]. The action vector of all players at time t is denoted as S(t) := [s1(t), ..., sM (t)], which is referred to as a “matching” for convenience although it is not necessarily one-to-one.
Individual Outcomes. For each player m, an outcome1 Ok,m(t) is associated with her action of pulling arm sm(t) = k at time t, which is defined as
Ok,m(t) := Xk,m(t)ηk(S(t)). (1)
In Eqn. (1), Xk,m(t) is a random variable of arm utility and ηk(S(t)) is the no-collision indicator defined by ηk(S) := 1{|Ck(S)| ≤ 1} with Ck(S) := {n ∈ [M ]|sn = k}. In other words, if player m is the only player choosing arm k, the outcome is Xk,m(t); if multiple players choose arm k simultaneously, a collision happens on this arm and the outcome is zero regardless of Xk,m(t).
For a certain arm-player pair, i.e., (k,m), the set of random arm utilities {Xk,m(t)}t≥1 is assumed to be sampled independently from an unknown distribution φk,m, which has a bounded support on [0, 1] and an unknown expectation E[Xk,m(t)] = µk,m. In general, these utility distributions are player-dependent, i.e., µk,m 6= µk,n when m 6= n. Note that despite the time independence among {Xk,m(t)}t≥1 for a certain arm-player pair (k,m), correlations can exist among the random utility variables of different arm-player pairs, i.e., among Xk,m(t) for different (k,m) pairs.
To ease the exposition, we define S = {S = [s1, ..., sM ]|sm ∈ [K],∀m ∈ [M ]} as the set of all possible matchings S and abbreviate the arm k of player m as arm (k,m). We further denote µ = [µk,m](k,m)∈[K]×[M ] and µS = [µsm,m]m∈[M ] for S = [s1, ..., sM ].
System Rewards. Besides players’ individual outcomes, with matching S(t) chosen at time t, a random system reward, denoted as V (S(t), t), is collected for the entire system. The most commonly-
1The term “outcome” distinguishes players’ individual rewards from the later introduced system rewards.
studied reward function (Bistritz and Leshem, 2020; Boursier et al., 2020) is the sum of outcomes from different players (referrd to as the linear reward function), i.e., V (S(t), t) := ∑ m∈[M ]Osm(t),m(t). With this linear reward function, for matching S, the expected system reward is denoted as Vµ,S := E[V (S, t)] = ∑ m∈[M ] µsm,mηsm(S) under matrix µ. As almost all of the existing MP-MAB literature focus on the linear reward function, we also focus on this case first, but note that the problem formulation presented in this section can be extended to general (nonlinear) reward functions in Section 5.
Feedback Model. Different feedback models exist in the MP-MAB literature, and this work focuses on the collision-sensing model (Bistritz and Leshem, 2018, 2020; Boursier and Perchet, 2019; Boursier et al., 2020). Specifically, player m can access her own outcome Osm(t),m(t) and the corresponding no-collision indicator ηsm(t)(S(t)), but neither the overall reward V (S(t), t) nor outcomes of other players. In other words, at time t, player m chooses arm sm(t) based on her own history Hm(t) = { sm(τ), Osm(τ),m(τ), ηsm(τ)(S(τ)) } 1≤τ≤t−1.
Regret Definition. If µ is known a priori, the optimal choice is the matching that gives the highest expected reward Vµ,∗ := maxS∈S Vµ,S . We formally define the regret after T rounds of playing as
R(T ) = TVµ,∗ − E [ T∑ t=1 V (S(t), t) ] , (2)
where the expectation is w.r.t. the randomness of the policy and the environment.
One technical novelty worth noting is that this work considers the general case with possibly multiple optimal matchings, instead of the commonly assumed unique one (Bistritz and Leshem, 2018, 2020). Multiple optimal matchings might be uncommon for the linear reward function, but often occur under more sophisticated reward functions that will be discussed later, e.g., the minimal function, and brings substantial difficulties into player coordination. In addition, the proposed BEACON design is also applicable to the homogeneous setting, i.e., ∀m ∈ [M ], µk,m = µk, with some trivial adjustments.

heading: 3 The BEACON Algorithm

heading: 3.1 Algorithm Structure and Key Ideas
text: After the orthogonalization procedure (Wang et al., 2020) at the beginning of the game, during which each player individually estimates the number of players M and assigns herself of a unique index m ∈ [M ], BEACON proceeds in epochs and each epoch consists of two phases: (implicit) communication and exploration.2 While similar two-phase structures have been adopted by other heterogeneous MP-MAB algorithms (Tibrewal et al., 2019; Boursier et al., 2020), those designs fail to have regrets approaching the centralized lower bound.
The challenge in approaching the centralized lower bound is not only designing more efficient implicit communications and explorations, but also connecting them in a way that neither phase dominates the overall regret and both approach the centralized lower bound simultaneously. BEACON precisely achieves these goals, with several key ideas that not only are crucial to closing the regret gap but also hold individual values in MP-MAB research. First, a novel adaptive differential communication (ADC) method is proposed, which is fundamental in improving the effectiveness and efficiency of implicit communications. Specifically, ADC drastically reduces the communication cost from up to O(log(T )) per epoch in state-of-the-art designs (Boursier et al., 2020) to O(1) per epoch, which ensures a low communication cost. Second, CUCB principles (Chen et al., 2013) are incorporated with a batched exploration structure to ensure a low exploration loss (see Section 8 for more discussions on the relationship between CMAB and MP-MAB). CUCB principles address a critical challenge of large amount of matchings in heterogeneous MP-MAB (i.e., |S| = KM ), which hampered prior designs. The batched structure, on the other hand, is carefully embedded and optimized such that the need of communication and exploration is balanced, leading to neither dominating the overall regret.
2Details of the orthogonalization procedure are given in the supplementary material. In addition, by “exploration phase”, we mean the time steps in one epoch that are not used for (implicit) communications, which actually contain both exploration and exploitation.

heading: 3.2 Batched Exploration
text: To facilitate the illustration, we first present the batched exploration scheme and also a sketch of BEACON under an imaginary communication-enabled setting, which will be addressed in Section 3.3. Specifically, players are assumed to be able to communicate with each other freely in this subsection.
The batched exploration proceeds as follows. At the beginning of epoch r, each playermmaintains an arm counters prk,m for each arm k of hers. The counters are updated as p r k,m = blog2(T rk,m)c, where T rk,m is the number of exploration pulls on arm (k,m) up to epoch r. Then, the leader (referring to the player with index 1) collects arm statistics from followers (referring to the players other than the leader). Specifically, if prk,m > p r−1 k,m , statistics µ̃ r k,m is collected from follower m; otherwise, µ̃ r k,m is not updated and kept the same as µ̃r−1k,m , where µ̃ r k,m is a to-be-specified characterization of arm (k,m)’s sample mean µ̂rk,m. With the updated information, an upper confidence bound (UCB) matrix
µ̄r = [µ̄ r k,m](k,m)∈[K]×[M ] is calculated by the leader, where µ̄ r k,m = µ̃ r k,m+ √ 3 ln tr/2
prk,m+1, and tr is the time step at the beginning of epoch r.
The UCB matrix µ̄r is then fed into a combinatorial optimization solver, denoted as Oracle(·), which outputs the optimal matching w.r.t. the input. Specifically, Sr = [sr1, ..., s r M ] ← Oracle(µ̄r) = arg maxS∈S {∑
sm µ̄rsm,m
} , which can be computed with a polynomial time complexity using the
Hungarian algorithm (Munkres, 1957). We note that similar optimization solvers are also required by Boursier et al. (2020); Tibrewal et al. (2019). Inspired by the exploration choice of CUCB, this matching Sr is chosen to be explored. The leader thus assigns the matching Sr to followers, i.e., arm srm for player m.
After the assignment, the exploration begins. One important ingredient of BEACON is that the duration of exploring the chosen matching, i.e., the adopted batch size, is determined by the smallest arm counter in it. Specifically, for Sr, we denote pr = minm∈[M ] prsrm,m and the batch size is chosen to be 2pr . In other words, during the following 2pr time steps, players are fixated to exploring the matching Sr. Then, epoch r + 1 starts, and the same procedures are iterated.
Remarks. BEACON directly selects the matching with the largest UCB to explore. It turns out that this natural method significantly outperforms the “matching-elimination” scheme in Boursier et al. (2020), and is critical to achieving a near-optimal exploration loss. In addition, the chosen batch size of 2pr ensures sufficient but not excessive pulls w.r.t. the least pulled arm(s) in the chosen matching, which dominate the uncertainties. Furthermore, while similar batched structures have been utilized in the bandit literature (Auer et al., 2002; Hillel et al., 2013), the updating of arm counters in BEACON is carefully tailored. Last, the leader collects followers’ statistics only when arm counters increase, i.e., prk,m > p r−1 k,m , which means µ̃ r k,m is sufficiently more precise than µ̃ r−1 k,m . This design contributes to a low communication frequency while not affecting the exploration efficiency.

heading: 3.3 Efficient Implicit Communication
text: Since explicit communication is prohibited in decentralized MP-MAB problems, we now discuss how to use implicit communication (Boursier and Perchet, 2019) to share information in BEACON. Specifically, players can take predetermined turns to “communicate” by having the “receive” player sample one arm and the “send” player either pull (create collision; bit 1) or not pull (create no collision; bit 0) the same arm to transmit one-bit information. Although information sharing is enabled, such a forced-collision communication approach is inevitably costly, as collisions reduce the rewards. The challenge now is how to keep the communication loss small, ideally O(log(T )).
The batched exploration scheme plays a key role in reducing the communication loss via infrequent information updating. In other words, players only communicate statistics and decisions before each batch instead of each time step. With the aforementioned batch size, there are at most O(log(T )) epochs in horizon T . Thus, intuitively, if the communication loss per epoch can be controlled of order O(1) irrelevant of T , the overall communication loss would not be dominating. However, this requirement is challenging and none of the existing implicit communication schemes (Boursier and Perchet, 2019; Boursier et al., 2020) can meet it, which calls for a novel communication design.
From the discussion of the exploration phases, we can see that sharing arm statistics µ̃rk,m is the most challenging part. Specifically, as opposed to sharing integers of arm indices in Sr and the batch
size parameter pr, statistics µ̃rk,m is often a decimal while forced-collision is fundamentally a digital communication protocol. We thus focus on the communication design for sharing statistics µ̃rk,m, and propose the adaptive differential communication (ADC) method as detailed below. Details of sharing Sr and pr can be found in supplementary material.
Algorithm 1 BEACON: Leader 1: Initialization: r ← 0; ∀(k,m), prk,m ← −1, T rk,m ← 0, µ̃rk,m ← 0
2: Play each arm k ∈ [K] and T r+1k,1 ← T r k,1 + 1 3: while not reaching the time horizon do 4: r ← r + 1 5: ∀(k,m), prk,m ← ⌊ log2(T r k,m)
⌋ 6: ∀k ∈ [K], update sample mean µ̂rk,1 with the
first 2p r k,1 exploratory samples from arm k
. Communication Phase 7: for (k,m) ∈ [K]× [M ] do 8: if prk,m > pr−1k,m then 9: δ̃rk,m ← Receive(δ̃rk,m,m)
10: µ̃rk,m ← µ̃r−1k,m + δ̃ r k,m 11: else 12: µ̃rk,m ← µ̃r−1k,m 13: end if 14: end for 15: ∀(k,m), µ̄rk,m ← µ̃rk,m + √ 3 ln tr/2 pr k,m +1 16: Sr = [sr1, ..., srM ]← Oracle(µ̄r) 17: ∀m ∈ [M ], Send(srm,m)
. Exploration Phase 18: pr ← minm∈[M ] prsrm,m 19: Play arm sr1 for 2pr times 20: Signal followers to stop exploration 21: Update ∀m ∈ [M ], T r+1sm,m ← T r sm,m + 2 pr 22: end while
The first important idea is to let followers adaptively quantize sample means for communication. Specifically, upon communication, the arm statistics µ̃rk,m is not directly set as the collected sample mean µ̂rk,m. Instead, µ̃ r k,m is a quantized version of µ̂rk,m using d1 + prk,m/2e bits. Since µ̃rk,m is communicated only upon an increase of the arm counter prk,m, this quantization length is adaptive to the arm counter (or equivalently the arm pulls), and further to the adopted confidence bound in Section 3.2, i.e.,√
3 ln tr/2 prk,m+1. However, this idea alone is not sufficient because prk,m is of order up to O(log(T )), instead of O(1).
To overcome this obstacle, the second key idea is differential communication, which significantly reduces the redundancies in statistics sharing. Specifically, follower m first computes the difference δ̃rk,m = µ̃ r k,m − µ̃ r−1 k,m , and then truncates the bit string of δ̃rk,m upon the most significant non-zero bit, e.g., 110 for 000110. She only communicates this truncated version of δ̃rk,m in the transmission of µ̃rk,m to the leader. The intuition is that µ̃rk,m and µ̃ r−1 k,m are both concentrated at µk,m with high probabilities, which results in a small δ̃rk,m. From an informationtheoretic perspective, the conditional entropy of µ̃rk,m on µ̃ r−1 k,m , i.e., H(µ̃ r k,m|µ̃ r−1 k,m), is often small because they are highly correlated. 3
As will be clear in the regret analysis, putting these two ideas together results in an effective communication design, i.e, the ADC scheme, whose expected regret is of order O(1) per epoch and O(log(T )) overall. This method itself represents an important improvement over prior implicit communication protocols in MP-MAB, whose loss is typically of order O(log(T )) per epoch and O(log2(T )) in total with multiple optimal matchings (Boursier and Perchet, 2019; Boursier et al., 2020). Techniques similar to ADC have been utilized in areas outside of MAB, e.g., wireless communications (Goldsmith and Chua, 1998), with proven success in practice (Goldsmith, 2005).
3Note that sharing the truncated version of δ̃rk,m results in another difficulty that its length varies for different player-arm pairs and is unknown to the leader. A specially crafted “signal-then-communicate” scheme is designed to tackle this challenge and can be found in the supplementary material.
The complete BEACON algorithm can now be obtained by plugging ADC into the batched exploration structure. A sketch of one BEACON epoch is illustrated in Fig. 1, and the leader’s algorithm is presented in Algorithm 1. The follower’s algorithm can be found in the supplementary material, along with the definitions of the implicit communication protocols denoted by functions Send() and Receive(). Note that the for-loops with (k,m) and ∀(k,m) in the pseudo-codes indicate the iteration over all possible arm-player pairs of [K]×[M ]. In addition, the communications of the leader to herself indicated by the pseudo-codes denote her own calculations instead of real forced-collision communications (among the leader and followers), which is a simplification for better exposition.

heading: 4 Theoretical Analysis
text: With notations Sc := {S ∈ S|∃m 6= n, sm = sn} as the set of collided matchings; S∗ := {S ∈ S|Vµ,S = Vµ,∗} as the set of optimal matchings; Sb = S\(S∗ ∪ Sc) as the set of collision-free suboptimal matchings; ∆k,mmin := Vµ,∗−max{Vµ,S |S ∈ Sb, sm = k} as the minimum sub-optimality gap for collision-free matchings containing arm-player pair (k,m); ∆min := min(k,m){∆k,mmin} as the minimum sub-optimality gap for all collision-free matchings, the regret of BEACON with the linear reward function is analyzed in the following theorem. Theorem 1. With the linear reward function, the regret of BEACON is upper bounded as4
Rlinear(T ) = Õ  ∑ (k,m)∈[K]×[M ] M log(T ) ∆k,mmin +M2K log(T )  (3) = Õ ( M2K log(T )
∆min
) .
Note that in Eqn. (3), the first term represents the exploration regret of BEACON, and the second term the communication regret. Compared with the state-of-the-art regret result Õ(M3K log(T )/∆min) for METC (Boursier et al., 2020), the regret bound in Theorem 1 improves the dependence of M from M3 to M2. It turns out that this quadratic dependence is optimal because the same dependence exists in the centralized lower bound (hence a natural lower bound for decentralized MP-MAB) for the linear reward function, as from Kveton et al. (2015c):5
Rlinear(T ) = Ω
( M2K
∆min log(T )
) . (4)
By comparing Theorem 1 and Eqn. (4), it can be observed that with the linear reward function, BEACON achieves a regret that approaches the centralized lower bound. The efficiency and effectiveness of both exploration and communication phases are critical in this achievement, as we can see that both terms in Theorem 1 are non-dominating at Õ(M2K log(T )).
In addition to the problem-dependent bound given in Theorem 1, the following theorem establishes a problem-independent bound, which can be thought of as a worst-case characterization. Theorem 2. With the linear reward function, it holds that
Rlinear(T ) = O ( M √ KT log(T ) ) .
Theorem 2 not only improves the best known problem-independent bound O(M 3 2 √ KT log(T )) (Boursier et al., 2020) in the decentralized MP-MAB literature, but also approaches the centralized lower bound Ω(M √ KT ) (Kveton et al., 2015c; Merlis and Mannor, 2020) up to logarithmic factors.
Theorems 1 and 2 demonstrate that for the linear reward function, BEACON closes the performance gap (both problem-dependent and problem-independent) between decentralized heterogeneous MP-MAB algorithms and their centralized counterparts. The regret bounds of various MP-MAB algorithms, including BEACON, are summarized in Table 1.
4With the notation Õ(·), logarithmic parameters containing K are ignored. 5This lower bound holds for the cases with arbitrarily correlated arms, as considered in this work. Under
additional arm independence assumptions (Combes et al., 2015), lower regrets can be achieved.
Remarks. We note that it is also feasible to combine the ADC protocol and METC (Boursier et al., 2020), which can address its communication inefficiency, especially with multiple optimal matchings. However, with ideas from CUCB, BEACON is much more efficient in exploration than “Explore-then-Commit”-type of algorithms (e.g., METC), which is the main reason we did not fully elaborate the combination of METC and ADC in this work. Theoretically, this superiority can be reflected in the extra multiplicative factor in the exploration loss of METC shown in Table 1.

heading: 5 Beyond Linear Reward Functions

heading: 5.1 General Reward Functions
text: In this section, we move away from the linear reward functions in almost all prior MP-MAB research, and extend the study to general (nonlinear) reward functions. Two exemplary nonlinear reward functions are given below, with more examples provided in the supplementary material.
• Proportional fairness: V (S, t) = ∑ m∈[M ] ωm ln( + Osm,m(t)), where > 0 and ωm > 0 are
constants. It promotes fairness among players (Mo and Walrand, 2000); • Minimal: V (S, t) = minm∈[M ]{Osm,m(t)}, which indicates the system reward is determined by
the least-rewarded player, i.e., the short board of the system;6
These reward functions all hold their value in real-world applications, but are largely ignored and cannot be effectively solved by previous approaches. The difficulty introduced by this extension not only lies in the complex mapping from the (unreliable) individual outcomes to system rewards, but also comes from the potential “coupling” effect among players (e.g., the minimal reward function).
To better characterize the problem, the following mild assumptions are considered. Assumption 1. There exists an expected reward function v(·) such that Vµ,S := E[V (S, t)] = v(µS ηS), where ηS := [ηsm(S)]m∈[M ] and µS ηS := [µsm,mηsm(S)]m∈[M ]. Assumption 2 (Monotonicity). The expected reward function is monotonically non-decreasing with respect to the vector Λ = µS ηS , i.e., if Λ Λ
′, we have v(Λ) ≤ v(Λ′). Assumption 3 (Bounded smoothness). There exists a strictly increasing (and thus invertible) function f(·) such that ∀Λ,Λ′, |v(Λ)− v(Λ′)| ≤ f(‖Λ−Λ′‖∞).
Assumption 1 indicates that the expected reward Vµ,S of matching S is determined only by its expected individual outcomes. It is true for the linear reward function, and also generally holds if
6Differences with the max-min fairness (Bistritz et al., 2020) are elaborated in the supplementary material.
distributions {φk,m} are mutually independent and determined by their expectations {µk,m}, e.g., Bernoulli distribution. Assumptions 2 and 3 concern the monotonicity and smoothness of the expected reward function, which are natural for most practical reward functions, including the above examples. Similar assumptions have been adopted by Chen et al. (2013, 2016b); Wang and Chen (2018).

heading: 5.2 BEACON Adaption and Performance Analysis
text: In Section 3.2, a combinatorial optimization solver Oracle(·) is implemented for the linear reward function. With ideas from CUCB (Chen et al., 2013), BEACON can be extended to handle a general reward function with a corresponding solver Oracle(·) that outputs the optimal (non-collision) matching w.r.t. the input matrix µ′, i.e., S′ ← Oracle(µ′) = arg maxS∈S\Sc Vµ′,S . With such an oracle, the following theorem provides performance guarantees of BEACON. Theorem 3 (General reward function). Under Assumptions 1, 2, and 3, denoting ∆k,mmax := Vµ,∗− min{Vµ,S |S ∈ Sb, sm = k} and ∆c := f(1), the regret of BEACON is upper bounded as
R(T ) = Õ  ∑ (k,m)∈[K]×[M ] [ ∆k,mmin (f−1(∆k,mmin)) 2 + ∫ ∆k,mmax ∆k,mmin
1
(f−1(x))2 dx
] log(T ) +M2K∆c log(T )  = Õ
 ∑ (k,m)∈[K]×[M ] ∆k,mmax log(T ) (f−1(∆k,mmin)) 2 +M2K∆c log(T )  . With a stronger smoothness assumption, we can obtain a clearer exposition of the regret. Corollary 1. Under Assumptions 1 and 2, if there exists B > 0 such that ∀Λ,Λ′, |v(Λ)− v(Λ′)| ≤ B‖Λ−Λ′‖∞, it holds that
R(T ) = Õ  ∑ (k,m)∈[K]×[M ] B2 ∆k,mmin log(T ) +M2KB log(T )  . In addition, since the combinatorial optimization problems with general reward functions can be NP-hard, it is more practical to adopt approximate solvers rather than the exact ones (Vazirani, 2013). To accommodate such needs, we introduce the following definition of (α, β)-approximation oracle for α, β ∈ [0, 1] as in Chen et al. (2013, 2016a,b); Wang and Chen (2017): Definition 1. With a matrix µ′ = [µ′k,m](k,m)∈[K]×[M ] as input, an (α, β)-approximation oracle outputs a matching S′, such that P[Vµ′,S′ ≥ α · Vµ′,∗] ≥ β, where Vµ′,∗ = maxS∈S Vµ′,S .
With only an approximate solver, it is no longer fair to compare the performance against the optimal reward. Instead, as in the CMAB literature (Chen et al., 2013, 2016a,b; Wang and Chen, 2017), an (α, β)-approximation regret is considered: Rα,β(T ) = TαβVµ,∗ − E[ ∑T t=1 V (S(t), t)], where the performance is compared to the αβ fraction of the optimal reward. As shown in the supplementary material, for this (α, β)-approximation regret, an upper bound similar to Theorem 3 can be obtained.

heading: 6 Experiments
text: In this section, BEACON is empirically evaluated with both linear and general (nonlinear) reward functions. All results are averaged over 100 experiments and the utilities follow mutually independent Bernoulli distributions. Additional experimental details, empirical algorithm enhancements and more experimental results (e.g., with a large game), can be found in the supplementary material.
Linear Reward Function. BEACON is evaluated along with the centralized CUCB (Chen et al., 2013) and the state-of-the-art decentralized algorithm METC (Boursier et al., 2020). The decentralized GoT algorithm (Bistritz and Leshem, 2020) is also evaluated but its regrets are over 100× larger than those of BEACON, and thus is omitted in the plots. Fig. 2(a) reports results under the same instance in Boursier et al. (2020) withK = 5,M = 5. Although this is a relatively hard instance with multiple optimal matchings and small sub-optimality gaps, BEACON still achieves a comparable performance as CUCB, and significantly outperforms METC: an approximate 7× regret reduction at the horizon.
To validate whether this significant gain of BEACON over METC is representative, we plot in Fig. 2(b) the histogram of regrets with 100 randomly generated instances still with M = 5,K = 5, T = 106. Expected arm utilities are uniformly sampled from [0, 1] in each instance. It can be observed that the gain of BEACON is very robust – its average regret is approximately 6× lower than METC. General Reward Function. Two representative nonlinear reward functions are used to evaluate BEACON: (1) the proportional fairness function with ∀m ∈ [M ], ωm = 1, = 10−2; (2) the minimal function. BEACON is compared with CUCB and METC.7 Under a game instance with M = 6,K = 8, Fig. 2(c) reports the regrets under the proportional fairness function, and Fig. 2(d) with the minimal function. From both results, it can be observed that BEACON has slightly larger (but comparable) regrets than the centralized CUCB, while significantly outperforming METC.
To summarize, BEACON not only significantly outperforms state-of-the-art decentralized MP-MAB algorithms, but is also capable of empirically approaching the centralized performance, which is the first time for a decentralized heterogeneous MP-MAB algorithm to the best of our knowledge.

heading: 7 Discussions
text: We briefly summarize the novel theoretical contributions of this work:
• Closing the regret gap. With the linear reward function, BEACON can approach (both problemdependent and problem-independent) centralized lower bounds. To the best of our knowledge, this is the first time such performance gap is closed (scaling wise) for the heterogeneous MP-MAB. • Broader applicability. BEACON can handle a broad range of general reward functions with a regret of O(log(T )), while existing algorithms mostly focus on the linear reward function and their analyses do not apply to the general reward functions. To the best of our knowledge, this is the first time general reward functions are studied in decentralized MP-MAB. • Fewer assumptions. BEACON achieves a strictly O(log(T ))-regret without any assumptions or prior knowledge of the game instance, while prior MP-MAB algorithms typically rely on additional assumptions or knowledge; see Table 1 for details.
In addition to these tangible contributions, this work also demonstrates the benefit of incorporating CMAB techniques in the study of MP-MAB. In this paper, both the BEACON design and its regret analysis benefit from CMAB, especially CUCB (Chen et al., 2013; Kveton et al., 2015c). While these two sub-fields of MAB are largely considered disjoint, this work shows that the underlying connection is rather fundamental. This revelation may open up interesting future research directions. For example, under the structure of BEACON, it is conceivable to introduce more advanced CMAB algorithms, e.g., ESCB (Combes et al., 2015), into the study of MP-MAB with additional assumptions on the arm dependence. In another direction, ideas from this work may also contribute to the study of CMAB. For example, due to the batched structure, BEACON only accesses the oracle O(log(T )) times over T steps, which is more computational efficient than the O(T ) times access in CUCB.
Besides contributions, there are open questions left for future studies. First, BEACON relies on a centralized combinatorial optimization solver, i.e., Oracle(·), and so do Boursier et al. (2020); Tibrewal et al. (2019). While being a reasonable requirement, this oracle might be computationalinfeasible for some applications, e.g., with Internet-of-Things (IoT) devices, especially when M and K are large. Also, while the oracle allows general analysis, it also decouples the problem into
7To make meaningful comparisons, non-trivial adjustments and enhancements have been applied to METC, which originally applies only to the linear reward function. Details are given in the supplementary material.
two disconnected parts: combinatorial optimization and bandits. It might be helpful to tailor the algorithm into one specific reward function, where joint designs over these two parts can be performed. Furthermore, it would be interesting to investigate the non-cooperative setting as in Boursier and Perchet (2020), where we believe the design ideas in this work can still be of use, especially ADC.

heading: 8 Related Works
text: Decentralized MP-MAB. Since Liu and Zhao (2010), most MP-MAB works consider the homogeneous variant with player-independent arm utilities (Avner and Mannor, 2014; Rosenski et al., 2016; Besson and Kaufmann, 2018). With implicit communications, Boursier and Perchet (2019); Wang et al. (2020) prove regrets that approach the centralized ones. The homogeneous variant is fairly well understood by now. The heterogeneous MP-MAB problems (Kalathil et al., 2014; Nayyar et al., 2016) with player-dependent arm utilities, on the other hand, remain largely open. The recent attempts have been summarized in Table 1, whose regrets are far from the (natural) centralized lower bound. Note that a similar idea of adaptive quantization is applied by Boursier et al. (2020), but the differential communication part in ADC is entirely novel and more critical to the overall performance.
All the aforementioned works are confined to the linear reward model. To the best of our knowledge, this work is the first to study general reward functions. Fairness is considered in Bistritz et al. (2020) but with major differences elaborated in the supplementary material. Other MP-MAB variants, including “stable” allocations (Avner and Mannor, 2016; Darak and Hanawal, 2019), no-sensing (Lugosi and Mehrabian, 2018; Shi et al., 2020; Bubeck and Budzinski, 2020; Bubeck et al., 2021), and adversarial (Alatur et al., 2020; Bubeck et al., 2020; Shi and Shen, 2021), fall out of our scope.
Combinatorial MAB. Since first presented by Chen et al. (2013), many variants of stochastic CMAB have been investigated (Kveton et al., 2014, 2015a). Some recent works have also introduced Thompson Sampling into CMAB (Wang and Chen, 2018; Perrault et al., 2020). The study of lower bounds in CMAB has been active, e.g., for the linear reward function with correlated arms (Kveton et al., 2015b; Degenne and Perchet, 2016) and independent arms (Combes et al., 2015). Recent attempts on lower bounds for general reward functions are reported by Merlis and Mannor (2020).
As illustrated in the design of BEACON, the decentralized MP-MAB model is closely related to CMAB, while these connections are largely ignored in the previous works. With more details presented in the supplementary material, we here briefly note that in some sense, MP-MAB can be thought of as a decentralized version of CMAB, and this decentralized nature leads to additional challenges with collision-avoidance and information sharing.

heading: 9 Conclusion
text: In this work, we first investigated decentralized heterogeneous MP-MAB problems with linear reward function and proposed the BEACON algorithm. A novel adaptive differential (implicit) communication approach was designed and a batched structure was carefully crafted to incorporate the exploration principles from CUCB. With these novel ideas, BEACON achieved regrets that not only improve all prior regret bounds but in fact approach the centralized lower bound for the first time in the study of decentralized heterogeneous MP-MAB. Then, we extended the study to general reward functions and showed that BEACON can still obtain a regret of O(log(T )) with simple modifications. Experimental results demonstrated that the gain of BEACON does not exist just in the theoretical analysis – significant gains over state-of-the-art decentralized algorithms and achieving a comparable performance with the centralized benchmark have been empirically established.
BEACON has demonstrated the intimate connection between MP-MAB and CMAB, two largely disjoint sub-fields of the MAB research. It is our hope that this work sparks future interest in investigating this fundamental connection and improving existing algorithms in both areas.

heading: Acknowledgement
text: The CSs acknowledge the funding support by the US National Science Foundation under Grants ECCS-2029978, ECCS-2033671, and CNS-2002902, and the Bloomberg Data Science Ph.D. Fellowship. WX acknowledges the funding support by the Hong Kong Ph.D. Fellowship. The work of JY
was supported by the US National Science Foundation under Grants CNS-1956276, CNS-2003131, CNS-2114542, and ECCS-2030026.

Review summaries:
This paper studies heterogeneous multiplayer bandits (with collision sensing). Designing a new communication protocol, it proposes a batched and decentralized version of CUCB to reach centralized performances in heterogeneous multiplayer bandits. The proposed algorithm can also be extended to more general reward functions, similarly to CUCB in combinatorial bandits.

This paper proposes the BEACON algorithm under Multi-player MAB settings. The authors make use of the ideas in combinatorial-MAB area and implement batched exploration, in which they choose an update rule for the arm counters to sufficiently but not excessively explore the arms. Then, they  extends the adaptive communication to adaptive differential communication, also, the communication only happens when the sample mean is sufficiently precise. With the combination of these strategies, the BEACON achieves the regret lower bound while requiring less assumptions (unknown horizon, non-linear reward functions, etc.) than prior works in the area. 

Overall, this paper introduces a new algorithm BEACON for multi-agent multi-armed bandits that closes the gap between the state-of-the-art upper bound and information theoretic lower bound of the regrets by implicit communication via adaptive differential communication protocols and efficient exploration via UCB-based algorithms. In addition to the existing case where the system-level reward is a linear combination of individual rewards, BEACON also tackles the general cases where the combination is non-linear, obtaining a regret bound of O(log T). Experiments show that BEACON significantly outperforms state-of-the-art benchmarks in decentralized bandits.