Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and Generalization
Authors: Chengshuai Shi
Wei Xiong
Cong Shen
Jing Yang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Multi-agent System
Multi-armed Bandits
Decentralized Learning

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.

Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and Generalization
Chengshuai Shi University of Virginia cs7ync@virginia edu
Wei Xiong The Hong Kong University of Science and Technology wxiongae@connect. ust hk
Cong Shen University of Virginia cong@virginia. edu
Jing Yang
The Pennsylvania State University
yangjing@psu.ee edu
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 novel adaptive differential communication (ADC) design that significantly improves the implicit communication efficiency. For the latter, a carefully crafted batched exploration scheme 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 new MP-MAB problem where the system reward a general (nonlinear) function of individual rewards. We extend BEACON solve this problem and prove 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 worth further investigation.
Introduction
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 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.) [0066] Besson and Kaufmann 2018). Recent attentions have shifted towards the more general MP-MAB model with player-dependem bandit instances (i.e., the heterogeneous variant) (Bistritz and Leshem] 2018 [020] Tibrewal et al.
2019, Boursier al.) (020). 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, sfate-of-the-ee results in heterogeneous variants still have significant gaps from
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

the centralized performance. It remains an open problem whether 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 1.1).
In this paper, we make progress in the aforementioned problems for decentralized heterogeneous MP- MAB. A novel algorithm called BEACON - Batched Exploration with Adaptive COmmunicatioN- 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 functionn we rigorously show that regret bounds of BEACON, both problem- dependent and
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 show that it achieves regret of (T)) where T' is the time horizon. The amalysis 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 comparable performance the centralized benchmark, hence corroborating the theoretical analysis. Remarkably, BEACON with the linear reward function generally achieves 6x improvement over the state-of-the-ard METC (Boursier et al. 2020).
2 Problem Formulation
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 decentralized system. Also, time is assumed to be slotted, and at time step I, each player m E [M] chooses and pulls an arm 8m (f) E [K] The action vector of all players at time / is denoted S(1)= [st (I), --. 8M (f), which is referred as a "matching" for convenience although it is not necessarily one-to-one.
Individual Outcomes. For each player m. outcome Ok.m(t) (t) is associated with her action of pulling arm sm (f) = k at time f, which is defined as
Oz.m (t) == X ()(((((()))))))))))))))))))))(
In Eqn. Xam (t) is a random variable of arm utility and my (S())) is the no-collision indicator defined by M& (S) 1 (S)) I 1} with Cx(() = fn E [M]ss k). In other words, if player m is the only player choosing arm k the outcome is X (t); if multiple players choose arm simultaneously, a collision happens this arm and the outcome is zero regardless of Xk,m (t).
For certain arm-player pair, i.e., (k, m), the set of random arm utilities {Xx,m(1))) is assumed to be sampled independently from an unknown distribution di.m. which has a bounded support on [0, 1] and an unknown expectation E
m (t) = 1As.. In general, these utility distributions are player-dependent, i.c., Mamm # Pk,n when m * n. Note that despite the time independence among {X (t) for a certain arm-player pair (k: m)) correlations can exist among the random utility variables of different arm-player pairs, i.c., among Xk,m (t) for different (k, m) pairs.
To ease the exposition, we define S = {S = [si,..., s
s sm E [K], Vm E [M]] as the set of all possible matchings S and abbreviate the arm k of player m as arm (k, m). We further denote 4 == (Mk.ml( and μ [u.m [Mmm..mmm[ for S [$1, sM).
System Rewards. Besides players' individual outcomes, with matching S(t) chosen at time t, a random system reward, denoted V(S(t), t), is collected for the entire system. The most commonly-
'The 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..., V (S(t), := Eme(M) [r] O=... (t) (t). With this linear reward function, for matching S, the expected system reward denoted as Vu.s BIV (S, t)] m mm... (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
Feedback Model. Different feedback models exist in the MP-MAB literature, and this work focuses on the collision-sensingg model (Bistritz and Leshem 2018 2020 Boursier and Perchet 2019
Boursier et al. 2020). Specifically, player m can access her own outcome (t..
(t) (t) and the
corresponding no-collision indicator (1) (S()), but neither the overall reward V(S()), 1) nor
outcomes of other players. In other words, at time player chooses arm 8. (t) based her
history (t) {sm(7) O (m),)), (T), (r
Regret Definition. If ş is known priori, the optimal choice is the matching that gives the highest expected reward VA, := maxses Vn.s. We formally define the regret after T rounds of playing as
T
R(T) = -V 1.- - E
Σ v(s(t),
(2)
where the expectation 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., Vm [M], Mk.m - μax, with some trivial adjustments.
3
The BEACON Algorithm
3.1 Algorithm Structure and Key Ideas
After the orthogonalization procedure (Wang et al.] 2020)
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 al. 2019 Boursier 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 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 (log(T)) per epoch in state-of-thh-aat designs (Boursier et al., 2020) to ((1) per epoch, which ensures low communication cost. Second, CUCB principles (Chen al. 2013) are incorporated with a batched exploration structure to ensure low exploration loss (see Section 8 for more discussions on the relationship between CMAB and MP-MAB), CUCB principles address critical challenge of large amount of matchings in heterogeneous MP-MAB (i.e., |S] = K A² 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.
Details 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.
3

---

3.2 Batched Exploration
To facilitate the illustration, we first present the batched exploration scheme and also a sketch of BEACON under imaginary coammuiccationnnaalle setting, which will be addressed in Section [.3] Specifically, players are assumed to he able to communicate with each other freely in this subsection.
The batched exploration proceeds as follows. At beginning of epoch r. each player m maintains an arm counters Pk.m for each arm of hers. The counters are updated as Pk.. [log (7 where T..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 Pk.m > Pk. statisties p is collected from follower m; otherwise, Pi, is not updated and kept the same as Hk.m where P is a to-be-specified characterization of arm (k, m)'s sample mean i With the updated information, upper confidence bound (UCB) matrix
7r-1
F, = =I (tk.. [K] x x[M]] is calculated by the leader, where F = 1% m + In l,t,/2 +1 and f, is the time step at the beginning of epoch
The UCB matrix μt then fed into combinatorial optimization solver, denoted as Oracle(-), which outputs the optimal matching w.r.t. the input. Specifically, S, = [s., sy + Oracle( = arg maxses {Σ s... H }. which can be computed with polynomial time complexity using the Hungarian algorithi (Munkres) 1957). We note that similar optimization solvers are also required by Boursier et al. (2020p; Tibrewal et al. (2019). Inspired by the exploration choice of CUCB, this matching S, is chosen to explored. The leader thus assigns the matching S, to followers, i.e., arm St, 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 Sp. we denote p.- = m Per,.. and the batch size is chosen to be 2hr In other words, during the following 2 time steps, players are fixated to exploring the matching S,,. Then, epoch r + 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-eliminatoon elimination" " scheme in Boursier et al. (2020), and is critical to achieving near-optimal exploration loss. In addition, the chosen batch size 2 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. Pl.. > pk which means "g... is sufficiently more precise than / This design contributes to low communication frequency while not affecting the exploration efficiency.
3.3 Efficient Implicit Communication
Since explicit communication 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 cooccddcoolsioon communication approach is inevitably costly, as collisions reduce the rewards. The challenge now is how to keep the communication loss small, ideally (llo(TT))
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 (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. (020)) can meet it, which calls for novel communication design.
From the discussion of the exploration phases, most challenging part. Specifically, opposed to sharing integers of arm indices in S, and the batch
see that sharing arm statistics i is the

---

size parameter Pr, statistics F..m is often decimal while forced-collision is fundamentally digital communication protocol. We thus focus on the communication design for sharing statistics j% and propose the adaptive differential communication (ADC) method as detailed below. Details of sharing S, and pr be found in supplementary material.
The first important idea is to let followers adap- tively quantize sample means for communica- tion. Specifically, upon communication, the arm statistics Pk is not directly set as the collected sample mean Pk.m Instead, Pk.m is quan- tized version of f4.m using [1 + mk.m/22 /2] bits.
Algorithm BEACON; Leader
1: Initialization:
+ O: V(k, m), Pk.m
-1,77, +- 0, Pk.m +-
Play each arm E [K] and TET +- Th. +1 while not reaching the time horizon do
3:
Since fk.m is communicated only upon an in- crease of the arm counter Pk.m this quantiza- tion length is adaptive to the arm counter (or equivalently the arm pulls), and further to the adopted confidence bound Section 3.2 i.c.,
4:
r -+++1
5:
v(k, m), Pk..
(TT.)
Wk E [K], update sample mean Ph, with
first 2Ph,1 exploratory samples from arm k b. Communication Phase
7:
for (k, m) E [K] x [M do
V 3 / However, this idea alone is not sufficient because Pi.m. is of order up to (log(T)), instead of O(1).
if Phem > Pk. then
9:
8r, + Reeeeive (82.
10:
jk.m + 14 + 8%,m
To overcome this obstacle, the second key idea
11:
else
12:
is differential communication, which signifi-
13:
cantly reduces the redundancies in statisties shar-
end for
ing. Specifically, follower m first computes the
difference 8% Mk f --1 and then trun-
15:
((k,, m), Ah.m + Wh.m /lt,,
16:
S. = (s) - Oracle((())
cates the bit string of oG... upon the most signifi-
17:
Vmn E [M] (M,SSendss, (end(s"... m))
cant non-zero bit, c.g., 110 for 000110. She only
Exploration Phase
communicates this truncated version of 8g... in
18:
p. +- milmm[[] PS:
19:
Play arm sf for 2 times
the transmission of jh to the leader. The in-
20:
Signal followers to stop exploration
tuition is that ik.m and "3 are both concen-
21:
Update Vm E [M], T m
T T'mmm 2
trated at fk.m with high probabilities, which
22: end while
results in small km From information- theoretic perspective, the conditional entropy of i on Ak i..., H (P% ( is often small because they are highly correlated
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 (ll) overall. This method itself represents an important improvement over prior implicit communication protocols in MP-MAB, whose loss is typically of order O Olog per epoch and Ollog 2 (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)
Leader
Update counters pl..
Receive the truncated 8
Find Omclee(R.)
Calculate pr min Pria negM)
Transmit matching S.
Explore arm.s] 2Pr times
if PEal
Follower
Update arm counters Plam
Truncate 6f,,
Recelve assigned si
Explore arm sj, for
m
Figure I: A sketch of epoch in BEACON. Yellow boxes and yellow lines indicate communications, green boxes for explorations, and boxes with dotted frame for computations.
"Note that sharing the truncated version of oü.m. results in another difficulty that its length varies for different player-arm arm pairs and is unknown to the leader. A specially crafted "signal-then wwwe--hommmiicaleee scheme is designed tackle this challenge and can be found the supplementary material.
5

---

The complete BEACON algorithm can now be obtained by plugging ADC into the batched exploration structure. sketch of one BEACON epoch is illustrated in Fig. T and the leader's algorithm is presented in Algorithm [ 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 O) Note that the for-loops with (k, m) and V(k, m) in the pseudo-codes indicate the iteration over all possible arm-player pairs of [K] x [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 a simplification for better exposition.
Theoretical Analysis
With notations S. == {S S|Em F 8m =sn} the set of collided matchings; S. {S SIV,.s = Vn,= as the set of optimal matchings; S = SS, U S.) as the set of collision- suboptimal matchings; Aim VH max[Vu.s]$ E Sb. Sm k} the minimum sub- sub-optimality gap for collision-free matchings containing arm-player pair (kt m); Amin min m)) { ( as the minimum sub-optimality gap for all collision cellision-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 a
M MT) +
Riiinar (T) =
M K log(T)
(3)
k.m
[[
min
M (og(T)
=
Amiu
Note that in Eqn. (3) the first term represents the exploration regret of BEACON, and the second term the communication regret. Compared with the siile-oftthearr regret result (M K log(T')/mmi)) for METC (Boursier et al. (2200), the regret bound in Theorem improves the dependence of M from 3 M It turns out that this quadratic dependence is optimal because the same dependence exists in the centralized lower bound (hence natural lower bound for decentralized MP-MAB) for linear reward function, as from Kveton et al. (211cc)
M Amin log(T))
Riinear (T) 2
By comparing Theorem and Eqn. 4 it can be observed that with the linear reward function, BEA- CON achieves 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 are non-dominating (M2 K log(?)).
In addition the problem-dependent bound given in Theorem [ the following theorem establishes problem-indepeedent bound, which can be thought of as worst-case characterization.
Theorem With the linear reward function, holds that
Riincar (T) = (00MMMM) (MVKTlog(T))
Theorem 2 not only improves the best known problem-independent bound O K'llog( (Boursier al. 2020) in the decentralized MP-MAB literature, but also approaches the centralized Merlis and Mannor 2020)) up to logarithmic factors.
lower bound Ω KT) (Kveton al. 2015c
Theorems and 2 demonstrate that for the linear reward function, BEACON closes the perfor- between decentralized heterogencous MP-MAB algorithms and their centralized counterparts. The regret bounds of various MP-MAB algorithms, including BEACON, are summarized in Table
mance gap (both problem-dee -eeeedede and
With the notation (-)) logarithmic parameters containing are ignored. "This lower bound holds for the cases with arbitrarily correlated arms, 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 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-Comee -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 the extra multiplicative factor the exploration loss of METC shown in Table
Table 1: Regret Bounds of Decentralized MP-MAB Algorithms
Assumptions
Reward function
Кnown horizon
Known
Unique
Algorilnn/Reference
Regret
gap
optimal
T
Amin
matching
GoT
Linear
No
Yes
Yes
O (Mloot*(TT)
[Bistritz and Leshem
2020
Decentralized MUMAB
Linear
No
Yes
No
0 log())
Magesh and Veeravalli 2019
ESET
Linear
No
No
Yes
O
M log (1)
Tibrewal et al.
2019
min
METC
Lincar
Yes
No
O
R log(T)
Boursier et al.
2020
Amin
METC
112 loR(T) 14. Amin
Lincar
Yes
No
No
O
MK
Boursier ot al.
2020
BEACON
General
No
No
No
MKA MKAmua log(T)) (T)
(this work, Thm.
if
(Bmin))
BEACON
Linear
No
No
Ö
MP log(T)
(this work, Thm.
mmin
Lower bound
Linear
N/A
N/A
N/A
Ω
Mr log(T)
(Kveton et
2015c
Amin
i: tuning parameters GoT requires knowledge arm utilities; KG L. arbitrarily small non-zero constants.
5 Beyond Linear Reward Functions
5.1 General Reward Functions
In this section, 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) Eme(na M] Wm In(e + Oam,, (t)), where > and Wm
constants. It promotes fairness among players (Mo and Walrand, 2000);
Minimal: ((S,t) t) = minme[M] (O... ( which indicates the system reward is determined by the least-rewarded player, i.e., the short board of the system
These reward functions 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 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 considered. Assumption 1. There exists an expected reward function v(-) such that Vu.s == E(V = ulu ns), where 7s == [n.. (S)]mE[M] and #t Ms := [ysmmmm?e... (S)M
Assumption (Monotonicity). The expected reward function is monotonically non-decreasing with respect the vector μı @ ms. i.e., if A 2 A', we have v(A) S v(A').
Assumption 3 (Bounded smoothness). There exists strictly increasing (and thus invertible) function f() such that VA, A', (m(A) u(A')l < f(IAA A' Allloo).
Assumption I indicates that the expected reward Vp.s of matching is determined only by its expected individual outcomes. It is true for the linear reward function, and also generally holds if
Diffferences with the max-min faimess BBsttriz et al. 2020 elaborated in the supplementary material.

---

distributions {ór.m are mutually independent and determined by their expectations { J e.g., Bemoulli distribution. AasuuptiinsS2andBoooom reward function, which are natural for most practical reward functions, including the above examples. Similar assumptions have been adopted by Chen et (2013] 2016b); Wang and Chen (2018).
the monotonicity and smoothness of the expected
5.2
BEACON Adaption and Performance Analysis
In Section 3.2 a combinatorial optimization solver Oracle(-) is implemented for the linear reward function. With ideas from CUCB (Chen al. 2013), BEACON can be extended handle general reward function with corresponding solver Oracle that outputs the optimal (non-collision) matching w.n.. the input matrix j i.c., S' +- Dracle(p") arg maxses),s VH's.
With such an oracle, the following theorem provides performance guarantees of BEACON. Theorem (General reward ftunction). Under Assumptions I and denoting A A.m. := Vu.* min(Vunsle E Sb. Sm }} and A. := =(1),, the regret of BEACON is upper bounded as
k,m
R(T) Ō
E
min
(- de log(T) + MA log(T)
k.m min
[K]
A k.m (Tg(T)) (
-
Σ
M Mo
k.m ))²
(H.m)E]K]x(M))
With a stronger smoothness assumption, we can obtain clearer exposition of the regret.
Corollary 1. Under Assumptions 7 and 2
if there exists B > such that AA, A', Iu(A) v(A')l
B|A - Allooo it holds that
R(T) -
E
B²
log(T) + M²K
k,m
(K [M)
min
In addition, since the combinatorial optimization problems with general reward functions can be NP-hard, is more practical adopt approximate solvers rather than the exact ones (Vazirami] 2013).
To accommodate such needs, we introduce the following definition of (a, apppoooooinnaoo oracle for 3 [0, as in Chen et al. (2013 2016a by: Wang and Chen (017)):
Definition 1. With a matrix μt (kk)m outputs matching S', such that P[[V,ss 2 a- Vwr,+ B, where Vu''. maxses Vw'ss.
input, (a, apprroiiitiinnniinnnn oracle
With only an approximate solver, is no longer fair to compare the performance against the optimal reward. Instead, in the CMAB literature (Chen al. 2013 2016a bj Wang and Chen 2017). an (a. apppooxixooinniio regret is considered: R,,, (T) Ta p.. EI V(S(t), t)], where the performance is compared to the axB fraction of the optimal reward. As shown in the supplementary material, for this (a, (a,3) approxxxxiatooonn regret, an upper bound similar to Theorem can be obtained.
Experiments
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 Bernoulii 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 tfate-of-the-ard decentralized algorithm METC (Boursier et al., 2020). The decentralized GoT algorithm (Bistritz and Leshem| 2020) is also evaluated but its regrets are over 100x larger than those of BEACON, and thus is omitted the plots. Fig. 2(a) reports results under the same instance in Boursier et al. 2020) with K = 5, M 5. Although this is relatively hard instance with multiple optimal matchings and small sub-optimality gaps, BEACON still achieves comparable performance CUCB, and significantly outperforms METC: an approximate 7x regret reduction the horizon.

---

PRTI
DEADON
ECACON
NETI
Regnec
SE00P)
(a) Linear, cumul. regret. (b) Linear, regret histo. (c) Proportional fairness.
(d) Minimal.
Figure 2: Regret comparisons. The continuous curves represent the empirical average values, and the shadowed areas represent the standard deviations. (a), (c) and (d) are evaluated with specific game instances, and (b) is the regret histogram of 100 randomly generated instances.
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 = 5, K 5, 10" 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 6x lower than METC.
General Reward Function. Two representative nonlinear reward functions are used to evaluate BEACON: (1) the proportional fairness function with Vm e Ww 1, 10 2: (2) the minimal function. BEACON is compared with CUCB and METC. Under game instance with 6 K 8, Fig. [ reports the regrets under the proportional fairness function, and Fig. 2
reprrrt
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 also capable of empirically approaching the centralized performance, which the first time for a decentralized heterogeneous MP-MAB algorithm to the best of our knowledge.
7 Discussions
We briefly summarize the novel theoretical contributions of this work:
Closing the regret gap. With the linear reward function, BEACON can approach (both problem- dependent and problem--nndependen) centralized lower bounds. To the best of knowledge, this is the first time such performance gap is closed (scaling wise) for the heterogeneous MP-MAB. Broader applicability. BEACON can handle broad range of general reward functions with regret of ((log(T)), ). while existing algorithms mostly focus on the linear reward function and their analyses do not apply 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 (log(T)) -regrett without any assumptions or prior knowledge of the game instance, while prior MP-MAB algorithms typically rely on additional assumptions or knowledge; see Table 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., [013)] Kveton et al.) (015c). 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 the study of CMAB. For example. due to the batched structure, BEACON only accesses the oracle (logg(T)) times over T steps, which 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 centralized combinatorial optimization solver, i.e., Oracle(-), and do Boursier et al. 2200); Tibrewal et al. (2019). While being reasonable requirement, this oracle might be computational- infeasible 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
To make meaningful comparisons, non trivirivial adjustments and enhancements have been applied to METC, which originally applies only to the linear reward function. Details 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.
8 Related Works
Decentralized MP-MAB. Since Liu and Zhao (2010) most MP-MAB works consider the homo-
geneous variant with player-independet 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, the other hand, remain largely open. The recent attempts have been summarized in Table whose regrets are far from the (natural) centralized lower bound. Note that similar idea of adaptive quantization is applied by Boursier 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
(ugosii and Mehrabian] 2018 [Shi et 20200 Bubeck and Budzinski] [2200] Bubeck et al. 202T).
and adversarial (Alatur et al. 2020 Bubeck et al. 2020 Shi and Shen 2021). 1. 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|
| 201 5a). Some recent works have also introduced
Thompson Sampling into CMAB (Wang and Chen 2018 Perrault et al. (020). 'he study of lower bounds in CMAB has been active, e.g., for the linear reward function with correlated arms (Kveton al. 2015b; Degenne and Perchet 2016) and independent arms (Combes et al., (0015). 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 decentralized version of CMAB, and this decentralized nature leads to additional challenges with collision-avoidee avoidancc and information sharing.
9 Conclusion
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 regret of O(lo(TT) with simple modifications. Experimental results demonstrated that the gain of BEACON does not cxist just in the theoretical analysis significant gains over state-of-the-an decentralized algorithms and achieving 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.
Acknowledgement
The CSs acknowledge the funding support by the US National Science Foundation under Grants RCCS-2029978, ECCS-2033671, and CNS-2002902, and the Bloomberg Data Science Ph.D. Fellow- ship. WX acknowledges the funding support by the Hong Kong Ph.D. Fellowship. The work of JY
10

---

was supported by the US National Science Foundation under Grants CNS- 2003110 CNS-2114542, and ECCS-2030026
References
Alatur, Levy, K. Y., and Krause, A. (2020). Multi Multi-player bandits: The adversarial case. Journal of Machine Learning Research, 21.
Anandkumar, A., Michael, N., and Tang, A. (2010). Opportunistic spectrum access with multiple
users: Learning under competition. 2010 Proceedings IEEE INFOCOM, pages 1-9. IEEE.
Anandkumar, A., Michael, N., Tang, A. K., and Swami, A. (2011). Distributed algorithms for learning and cognitive medium access with logarithmic regret. IEEE Journal on Selected Areas in Communications, 29(4):731-745
Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235255 256.
Avner, O. and Mannor, S. (2014). Concurrent bandits and cognitive radio networks. In Joint European Conference on Machine Learning and Knowledge Discovery Databases, pages 66-81 Springer.
Avner, O. and Mannor, (2016). Multi-user lax communications: a multi-armed bandit approach. In IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Commu- nications, pages 1 1-9. IEEE.
Besson, I.. and Kaufmann, E. (2018). Multi-player bandits revisited. In Algorithmic Learning Theory, pages 56-92.
Bistritz, I., Baharav, T., Leshem, A., and Bambos, N. (2020). My fair bandit: Distributed learning of max-min fairness with multi-player bandits. In International Conference Machine Learning. pages 930-940. PMLR.
Bistritz, I. and Leshem, A. (2018). Distributed multi-player bandits-a game of thrones approach. In Advances in Neural Information Processing Systems, pages 7222-7232.
Bistritz, I. and Leshem, A. (2020). Game of thrones: Fully distributed learning for multiplayer bandits. Mathematics of Operations Research.
Boursier, E., Kaufmann, E., Mehrabian, A., and Perchet, V. (2020). A practical algorithm for multiplayer bandits when arm means vary among players. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), Palermo, Sicily, Italy.
Boursier, E. and Perchet, V. (2019). Sic-mmab: synchronisation involves communication mul- tiplayer multi-armed bandits. In Advances in Neural Information Processing Systems, pages 12071-12080.
Boursier, E. and Perchet, V. (2020). Selfish robustness and equilibria in multi-player bandits. In Conference on Learning Theory, pages 530-581. PMLR.
Bubeck, S. and Budzinski, T. (2020). Coordination without communication: optimal regret in two players multi-armed bandits. Conference on Learning Theory.
Bubeck, S., Budzinski, T., and Sellke, (2021). Cooperative and stochastic multi-player multi- armed bandit: Optimal regret with neither communication nor collisions. In Conference on Learning Theory.
Bubeck, S., Li, Y., Peres, Y., and Sellke, M. (2020). Non-stochastic multi-player multi-armed bandits: Optimal rate with collision information, sublinear without. In Conference Learning Theory, pages 961-987.
Chen, W. Hu, W., L, Liu, Y., and Lu, P. (2016a). Combinatorial multi-armed bandit with general reward functions. Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 1659-1667.

---

Chen, W., Wang, Y., and Yuan, Y. (2013). Combinatorial multi- armed bandit: General framework and applications. In International Conference on Machine Learning, pages 151-159.
Chen, W., Wang, Y. Yuan, Y., and Wang, Q. (2016b). Combinatorial multi-armed bandit and its extension to probabilistically triggered arms. The Journal of Machine Learning Research, 17(1):1746-1775
Combes, R., Talebi Mazrach Shahi, M. S., Proutiere, A., et al. (2015). Combinatorial bandits revisited. Advances in neural information processing systems, 16-2144
Darak, S. J. and Hanawal, M. K. (2019). Multi-player multi-armes bandits for stable allocation in heterogeneous ad-hoc networks. IEEE Journal on Selected Areas in Communications, 37(10):2350- 2363.
Degenne, R. and Perchet, V. (2016). Combinatorial semi-bandit with known covariance. In Advances in Neural Information Processing Systems, pages 2972-2980.
Gai, Y., Krishnamachari, B., and Jain, R. (2010). Learning multiuser channel allocations cognitive radio networks: A combinatorial multi-armed bandit formulation. In 2010 IEEE Symposium on New Frontiers in Dynamic Spectrum (DySPAN), pages 1-9. IEEE.
Goldsmith, A. (2005). Wireless communications Cambridge university press.
Goldsmith, A. J. and Chua, S.-G. (1998). Adaptive coded modulation for fading channels. IEEE Transactions on communications, 46(5):595-602.
Hillel, E., Karnin, Z., Koren, T., Lempel. R., and Somekh, O. (2013). Distributed exploration in multi-armed bandits. In Proceedings of the 26th International Conference on Neural Information Processing Systems, pages 854-862.
Kalathil, D., Nayyar, N., and Jain, R. (2014). Decentralized learning for multiplayer multiarmed bandits. IEEE Transactions on Information Theory, 60(4):2331-234
Kveton, B., Szepesvari, C., Wen, Z.,, and Ashkan, A. (2015a). Cascading bandits: Learning to rank in the cascade model. International Conference on Machine Learning, pages 767-776. PMLR.
Kveton, B., Wen, Z.,, Ashkan, A., Fydgahi, H., and Eriksson, B. (2014). Matroid bandits: fast combi- natorial optimization with learning. In Proceedings of the Thirtieth Conference Uncertainty in Artificial Intelligence, pages 420-429.
Kveton, B., Wen, Z., Ashkan, A., and Szepesvári, C. (2015b). Combinatorial cascading bandits. In Proceedings the 28th International Conference on Neural Information Processing Systems- Volume 1, pages 1450-1458.
Kveton, B., Wen, Z., Ashkan, A., and Szepesvari, C. (2015c). Tight regret bounds for stochastic combinatorial semi-bandits. In Artificial Intelligence and Statistics, pages 535-543.
Liu, K. and Zhao, Q. (2010). Distributed learning in multi-armed bandit with multiple players. IEEE Transactions on Signal Processing, 58(1 1)56677-666.
Lugosi, G. and Mehrabian, A. (2018). Multiplayer bandits without observing collision information. arXiv preprint arXiv:1808. 004118888.084....
Magesh, and Veeravalli, V. (2019). Multi-user mabs with user dependent rewards for uncoordi- nated spectrum access. In 2019 53rd Asilomar Conference on Signals. Systems, and Computers, pages 969-972. IEEE.
Merlis, N. and Mannor, (2020). Tight lower bounds for combinatorial multi-armed bandits. In Conference on Learning Theory, pages 2830-2851 PMLR
Mo, J. and Walrand, J. (2000). Fair end-to-end window- congestion control. 1EEF/ACM Transactions on networking, 8(5):556-56) 567.
Munkres, J. (1957). Algorithms for the assignment and transportation problems. Journal of the society for industrial and applied mathematics, 5(1):32-38.
12

---

Nayyar, N., Kalathil, D., and Jain, R. (2016). On regret-optimal learning in decentralized multiplayer multiarmed bandits. IEEE Transactions on Control of Network Systems, 5(1):597-606.
Perrault, P., Boursier, E., Perchet, V., and Valko, M. (2020). Statistical efficiency of thompson sampling for combinatorial semi-bandits. In Advances in Neural Information Processing Systems.
Rosenski, J., Shamir, O., and Szlak, L. (2016). Multi-player bandits-a musical chairs approach. In International Conference on Machine Learning, pages 153-163.
Shi, C. and Shen, C. (2021). On no-sensing adversarial multi-player multi-armed bandits with collision communications. IEEE Journal on Selected Areas in Information Theory.
Shi, C., Xiong, W., Shen, C., and Yang, (2020). Decentralized multi- multi-player with no collision information. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), Palermo, Sicily, Italy.
bandits
Tibrewal, H., Patchala, S., Hanawal, M. K., and Darak, S. J. (2019). Multiplayer multi-armed bandits for optimal assignment in heterogeneous networks. arXiv preprint arXiv:1901.03866
Vazirani, V. V. (2013). Approximation algorithms. Springer Science & Business Media.
Wang, P.-A., Proutiere, A., Ariu, K., Jedra, Y., and Russo, A. (2020). Optimal algorithms for multiplayer multi-armed bandits. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), Palermo, Sicily, Italy
Wang. Q. and Chen, W. (2017). Improving regret bounds for combinatorial semi-bandits with probabilistically triggered arms and its applications. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 1161-1171.
Wang, and Chen, W. (2018). Thompson sampling for combinatorial semi-bandits. International Conference Machine Learning, pages 5114-5122.
13


Reviews:
[{"review_id": "mLBouzjqAA", "reviewer": "Reviewer_Vyvg", "summary": "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.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The paper is well-written, with all the sections clearly explained and the contributions clearly stated. The authors have made comprehensive comparisons against state-of-the-art benchmarks from prior work, and have clearly stated future directions from the work.  \n\n2. The contributions of this paper to the research community are evident and non-trivial. Using batch processing along with implicit communication protocols, BEACON not only closes the regret gap to information-theoretic lower bounds, but also generalizes to general reward functions with fewer assumptions/prerequisites.  \n\n3. Proper experiments have been conducted, with the necessary comparisons with existing state-of-the-art bandit algorithms included in the paper. \n\nWeaknesses:\n1. Rather than putting all discussion of the connection between Combinatorial MAB and MP-MAB into the supplementary materials, it would be beneficial to provide a summary as to how MP-MAB could be reduced to/relates to a CMAB problem. What does ‘the largest amount of matchings’ stand for in Section 3.1? The descriptions at this point are inadequate and don’t provide enough intuition.\n\n2. It is not immediately clear why the differential bit representation in the ADC protocol would help reduce the overall (expected) regret at each communication epoch to O(1). It would be ideal to include a brief description(at least intuitively) how truncating bits of the intra-epoch mean difference would result in regret reduction. \n\n3. Are there any constraints with respect to the number of players each player is able to communicate with? It appears from the paper that BEACON sets constraints on the number of times a player(as leader) communicates with other players(as followers ) during communication, but not who to communicate with. What does the underlying communication graph amongst players look like? Some additional clarification would be helpful for further understanding.\n\nOverall, my recommendation would be a ‘6, marginally above’. I’d be happy to revise my score, if the authors address my concerns accordingly. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations:  BEACON depends on an oracle solver for combinatorial optimization, a requirement of which might make BEACON computationally infeasible when the numbers of arms and players becomes extremely large. \n\nSocietal Impact: Not applicable. The paper is largely algorithmic and centers on theoretical justification of an abstract model. If any, the potential impact of this paper to the research community would be beneficial as it provides new methods for cooperative bandit decision making. \n", "review_text": "", "extra_scores": {"ethical_concerns": "Not applicable.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "JkWtqRN0E93", "reviewer": "Reviewer_5RkM", "summary": "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The combination of implicit communication for distributed operation with the use of centralized UCB (CUCB) seems like the main novelty of the work. The idea of using differential encoding to reduce the communication load, while natural, is useful. \n\nClarity: The paper is very clearly written and well organized, even though the notation is heavy, the clear presentation make it sufficiently easy to read and understand the paper. The authors explain the key ideas very clearly. The literature review appear sufficient as well. In particular, the related works are carefully discussed and compared to emphasize the contributions.\n\nSignificance: The proposed BEACON achieves the regret lower bound while requiring less assumptions than earlier works. Also, the possibility of allowing the reward function to be non-linear may be significant. While these technical results appear solid, I am not convinced in the importance of the problem setting. The need for implicit communication amongst distributed agents via collisions is quite artificial and forced. I do not see strong justification for enforcing such a constraint especially in a cooperative setting such as the one in this work. It may be more acceptable is a non-cooperative setting where users have self-interests. However, this would make the existing design useless, as it assumes thrust. \n\nMinor question: why is the expected system reward V_{\\mu,S} given by the sum_m \\mu_{s_m,m} in line 84? Shouldn't there be an expectation over the  no-collision indicator?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As the author pointed out, the work utilizes a combinatorial optimization ORACLE, which can be infeasible when the scale is large. There aren’t any negative societal impact of their work that I can identify.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "CssXzxzmSn8", "reviewer": "Reviewer_CoDr", "summary": "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.\nThe proposed algorithm can also be extended to more general reward functions, similarly to CUCB in combinatorial bandits.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I have read the other reviews and the authors' answers and maintain my positive opinion about this work.\n\n-----------------------------------------\n\nI find this work very interesting: nicely combining combinatorial bandits and multiplayer bandits was necessary to reach near centralized bound in the heterogeneous setting and is done nicely here, thanks to the differential communication protocol (which leads to log(T) communication rounds instead of log^2(T)).\n\nThe paper is well written, although we feel that the authors struggled to fit the 9 pages limit (eg it contains many footnotes): the description of the algorithm is very clear and the analysis seems to follow from the analysis of CUCB once the communication protocols are carefully handled. I have no major concern regarding this work, hence my overall score. \n\n- Note that if the horizon T is a priori known, using epochs of length 2^p log(T) (instead of 2^p) leads to a constant (in T) number of communication phases for existing ETC algorithms. Could such an improvement be combined with differential communication to decrease even further the communication cost? This could be of great interest, especially without sensing information, as sending a single bit here has a cost of order log(T)\n\n------- minor comments --------\n\n- I think the \"matching\" denomination is poorly chosen, as matching usually means that no arm is assigned to several players (ie it corresponds to the set S_b here)\n\n- line 83: V_{mu, S} is not well defined in case of collisions. It is here suggested that collisions do not degrade the total reward.\n\n- The length of communication is random (and thus unknown) to the different players. This is an additional challenge of the algorithm that is only mentioned in the Appendix. If the authors manage to save some room, I suggest to at least mention this additional difficulty in Section 3.3\n\n- equation (3): in the last formulation, the second term is not necessary since it is dominated by the first one\n\n- in table 1: I think it would be better to remove the tilde on O for all the algorithms that do not incur extra log(K) terms\n\n- Section 6 does not really seem at its right place in the current structure. I would rather postpone it after the experiments (or before the conclusion)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not concerned", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 h"}, "extra_text": {}}, {"review_id": "6yG5ojsI9Q", "reviewer": "Reviewer_5qQj", "summary": "The paper studies the decentralized multi-armed bandit problem and proposes an algorithm, appealing to the ideas of batched exploration and adaptive communication, which has the same order of regret as the centralized version of the problem. ", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The decentralized heterogeneous bandit problem is important and hard. Both the ideas of batched exploration and adaptive communication are interesting. My concern of the paper is as follows. \n\nThe paper aims to close the gap in regrets between the centralized and decentralized settings. However, the proposed algorithm heavily relies on centralized design. For example, there is a leader among all the agents which can collect all information from all agents and perform a centralized optimization task at each round. Another example is that the batched exploration procedure also depends on a network-wise pieces of information, like the smallest arm counter. With these, it is not reasonable to me to call the algorithm decentralized. More importantly, with allowing such information collection and processing in a \"center\", it can be expected that the proposed algorithm can perform as good as (or even outperform) the centralized algorithm. \n\nUpdate Sep 6: Thanks the authors for their responses.\n \nThe paper claims to close the \"gap\" between centralized and decentralized regrets. However, the authors to some extend \"mixed\" the existing literature. The original decentralized setting does not allow communication among the agents (e.g. Kalathil et al. 2014 and Nayyar et al. 2016 in the Related Works section, as well as the NIPS paper Bistritz and Leshem, 2018 in the authors' response); this is why the gap exists in my understanding. Now, the paper follows some recent development and allows communication among the agents. To me, this significantly changes the game. I would call it a distributed/cooperative setting, since it requires that all the agents coordinate (have to send correct information). In the vast distributed convex optimization (which allows communication among the agents and the communication graph can be sparse, as long as connected) literature, it is known that distributed convex optimization algorithms can achieve the same order of convergence rate as the centralized counterpart; the difference is in the constant coefficient level, which depends on the graph connectivity. Intuitively, the more connected the graph is, the faster (better constant coefficient) the convergence is. Since the current paper makes use of a leader-follower scheme in communication, it essentially corresponds to a complete graph in a distributed setting. So it is not surprising to me that it can achieve the regret close to the centralized setting. Also, from a distributed algorithm design point of view, assigning a unique ID to each agent, as the current paper does, is a very strong assumption; that is why in most distributed optimization algorithms, there does not exist a \"leader\".\n\nWith the above in mind, my understanding of the paper contribution is how to design a communication efficient scheme between the leader and each follower to achieve an \"optimal\" tradeoff between communication and system regret, instead of closing the \"gap\" between centralized and decentralized regrets, because it essentially considers a very special distributed setting. Note that transmitting one bit is essentially different from transmitting more bits as the former implicitly requires establishing new communication channels. \n\nFrom my focus point of view (the distributed/decentralized setting), the paper's scope is limited and the title could be misleading, so I keep my score 5.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper looks at the multi-player multi-arm bandit problem, with heterogenous rewards. This specific problem of reaching the centralized case with  decentralized protocols was still open, while it was settled with homogenous rewards.

This result requires combining additional, non trivial techniques from combinatorial bandits amongst others, hence hitting the acceptance bar.






Decision: Accept (Poster)