Achieving Near-Optimal Individual Regret & Low Communications in Multi-Agent Bandits
Authors: Xuchuang Wang
Lin Yang
Yu-Zhen Janice Chen
Xutong Liu
Mohammad Hajiesmaili
Don Towsley
John C.S. Lui
Venue: ICLR 2023 poster (2023)
Keywords: Multi-agent multi-armed bandits
individual regret
communication

Abstract: Cooperative multi-agent multi-armed bandits (CM2AB) study how distributed agents cooperatively play the same multi-armed bandit game. Most existing CM2AB works focused on maximizing the group performance of all agents---the accumulation of all agents' individual performance (i.e., individual reward). However, in many applications, the performance of the system is more sensitive to the ``bad'' agent---the agent with the worst individual performance. For example, in a drone swarm, a ``bad'' agent may crash into other drones and severely degrade the system performance. In that case, the key of the learning algorithm design is to coordinate computational and communicational resources among agents so to optimize the individual learning performance of the ``bad'' agent. In CM2AB, maximizing the group performance is equivalent to minimizing the group regret of all agents, and minimizing the individual performance can be measured by minimizing the maximum (worst) individual regret among agents. Minimizing the maximum individual regret was largely ignored in prior literature, and currently, there is little work on how to minimize this objective with a low communication overhead. In this paper, we propose a near-optimal algorithm on both individual and group regrets, in addition,  we also propose a novel communication module in the algorithm, which only needs \(O(\log (\log T))\) communication times where \(T\) is the number of decision rounds. We also conduct simulations to illustrate the advantage of our algorithm by comparing it to other known baselines.

Published as a conference paper at ICLR 2023
ACHIEVING NEAR-OPTIMAL INDIVIDUAL REGRET & Low COMMUNICATIONS IN MULTI-AGENT BANDITS
Xuchuang Wang
Lin Yang
Department of Computer Science and Engineering The Chinese University of Hong Kong
School Intelligence Science and Technology Nanjing University linyang@n ju edu.er en
xuchuangw@gma com
Yu-zhen Janice Chen
Xutong Liu
College Information and Computer Sciences University of Massachusetts Amherst yuzhenchen cs. uma a s. edu
Department Computer Science and Engineering The Chinese University of Hong Kong
1 liuxtocse. cuhk, edu
Mohammad Hajiesmaili & Don Towsley
John C.S. Lui
College of Information and Computer Sciences University of Massachusetts Amherst (ha mhjjissmaili towsley @cs. umass edu
Department of Computer Science and Engineering The Chinese University of Hong Kong cslui seluiecan csse. cuhk. edu. hk
ABSTRACT
Cooperative multi-agent multi-armed bandits (CMA2B) study how distributed agents cooperatively play the same multi-arma armed bandit game. Most existing CMA2B works focused on maximizing the group performance of all agents- the accumula- tion of all agents' individual performance (i.e., individual reward). However, in many applications, the performance the system more sensitive to the "bad" agent-tthe the agent with the worst individual performance. For example, in drone swarm, a "bad" agent may crash into other drones and severely degrade the system performance. In that case, the key of the learning algorithm design is to coordinate computational and communicational resources among agents so to optimize the individual learning performance of the "bad"' agent. In CMA2P, maximizing the group performance is equivalent to minimizing the group regret of all agents, and maximizing the individual performance mum (worst) individual regret among agents. Minimizing the maximum individual regret was largely ignored in prior literature. and currently, there is little work on how to minimize this objective with low communication overhead. In this paper, we propose near-optimal algorithm on both individual and group regrets, addition, we also propose novel communication module in the algorithm, which only needs Ologglog T') communication times where T is the number of decision rounds. We also conduct simulations to illustrate the advantage of our algorithm by comparing to other known baselines.
be measured by minimizing the maxi-
INTRODUCTION
The stochastic K arms, there is one agent who repeatedly chooses one arm to pull and observes a stochastic reward from the pulled arm in each time slot. To maximize cumulative reward (or minimize regret which the cumulative reward difference between the optimal decision and agent's choices), the agent needs to pull an arm either with large empirical mean reward to greedily maximize reward (exploitation), or whose reward estimate is highly uncertain as reduce that uncertainty to discover good arms (exploration). To model many real life applications, e.g., cognitive radio with multiple users (Liu & Zhao, 2010: Jouini et al., 2010; Boursier & Perchet, 2019), clinical trials in multiple labs (Wang, 1991), recommendation systems with multiple servers (Agarwal et al., 2008; Li et al., 2010; Landgren al., 2016), cooperative source search by multiple robots (Li al., 2014: 4; Jin et al., 2017), etc., one
bandit problem is a classic sequential decision making problem. Given

---

Published as a conference paper at ICLR 2023
Table 1: comparison summary of prior literature and this work (all regret bounds are problem- dependent and we omit the 1/A2 factor.)
Individual regret
Group regret
Communication time
DPE2 (Wang et al., 2020a)
O[K T")
O(K log T)
O(K2M²)
ComEx (Madhushani & Leonard, 2021)
O(K T)
O(K log T)
O(KM log T)
GosInE (Chawla et al., 2020)
D((KMM + log T)
O((K + 2M)
A1 I)
Dec_ Dec_UCB (Zhu et ul., 2021a)
O((K/M) log
OLK log T)
O(MT)
UCB-TCOM (our algorithm)
(((KMM) TogT)
O(K log T)
O(KM log(log T))
needs to extend the model to allow for more than one agent (M > 1) playing the same multi-armed bandit game. These agents cooperate with each other to minimize their regrets. We call this problem the cooperative multi-agent multi-armed bandits (CMA2B) problem and present it formally in $2.
The most common objective of CMA2B is to minimize the aggregate regret among all M agents, dubbed as group regret in this paper. This objective has been studied in the majority of prior work (Boursier & Perchet, 2019; Chawla al., 2020; Huang al., 2021; Shi et al., 2021b; Wang et al., 2020a;b). In addition to group regret, individual performance among agents is another important metric that less studied in prior work on CMA2B. The performance of each individual agent is critical in many applications in distributed systems. For example, in many distributed resource allocation scenarios with different agents in charge of the allocation, overall performance depends on the performance of the bottleneck agent instead of the aggregate performance of all agents. This can also be seen in a computer network scenario, in which an ISP may apply learning-based algorithms (Ma et al., 2010; Jiang et al., 2018) for some networking problems such as shortest path routing, channel selection, etc. To ensure that the users are served fairly, the underlying algorithms should fairly provide approximately equivalent individual performance for each learning agent. This is equivalent to minimizing the bottleneck agent's 's individual regret. For another thing, in network optimization literature, the max-min fairness metric-maxiiin maximize the minimal individual reward- is widely used to measure a system's fairness (Srikant& & Ying, 2013, $2.21), such as fair queuing (Demers et al., 1989). Since the regret is the opposite of reward, optimizing the max-min fairness is also equivalent to minimizing the bottleneck agent's regret. Other fairness motivation examples can be found in political philosophy (Rawls, 2004). In this paper, we explicitly take into account the notion of minimizing the maximum individual regret and, for brevity, hereinafter, refer to it as the individual regret.
Another important metric in CMA2B the communication time of all agents. For some distributed systems, e.g., agents are geographically located, communications among agents can be expensive. Thus it is important to design cooperative learning algorithm that provides minimal group and individual regrets, while at the same time, incurs small communication cost. In addition, it will be desirable to have a learning algorithm in which one can tune parameters so as to trade off communication times with regret as needed by different applications.
Contributions. In $3, we present the UCB-TCOM algorithm that achieves not only a near-optimal group regret of O((K/)) ) log I') but also near-optimal problem-dependen individual regret of O(KKMMA, log 7) with only Olog T)) communication times, where A₂ is the smallest reward mean gap between arms and T is the number of rounds. This is the first near-optimal algorithm on individual regret with efficient communications: Previous low communication algorithms, e.g., the leader-follower algorithm (Wang et al., 2020b), cannot achieve the near-optimal individual regret; and previous near-optimal algorithms on individual regret, e.g., Gos (Chawla et al., 2020), required high communication times (see related works below). UCB-TCOM achieves the near-optimal individual regret performance by evenly dividing the group regret to all agents. To equalize the regrets of all agents, UCB-TCOM directs agents to synchronously pull arms: agents only utilize the common reward observations, i.e., those having been broadcast over all agents, to make decisions. The communication policy TCOM (Tunable COMmunication) of UCB-TCOM is a parametric meta-algorithm that governs the communication of agents and can be executed on top of any underlying bandit learning algorithm. A salient feature of TCOM is that it can be tuned to balance regret and communication times. In particular, two parameters in TCOM can be tuned to determine the aggressiveness and frequency of communications among agents. Our analysis explicitly demonstrates how communication times can be tuned from 0 to OTT). Finally, we report numerical results in $5.
2

---

Published as a conference paper at ICLR 2023
Related works. The most relevant prior literature CMA2B is summarized in Table 1. First of all, notice all algorithms in Table attain a similar O(K log T)) regret upper bound. So, we compare them from the perspective of individual regret and communication cost. Previous algorithms exhibit good individual regret bounds, i.e., Dec_UCR (Zhu et al., 2021a) and GosTnE (Chawla et al., 2020). However, the communication times of Dec_UCB Ologg) T'. It is worth noting that the leader-follower algorithm (DPE2) (Wang et al., 2020a), where an agent, i.e., the leader, takes responsibility for exploration, and the other agents, i.e., followers, only exploit the arms recommended by the leader incurs constant (11) communication cost. However, the followrollower approach inherently fails achieve good individual regret- the leader agent incurs almost all of the regret OKK log 7) while followers only incur constant regrets. Lastly, we mention the communication policy ComEx (Madhushani & Leonard, 2021) designed for fully distributed al algorithms achieves a near-optimal group regret of O K log 7) with communication cost of (log 7'.. However, ComEx does not guarantee optimal individual regret. We provide a comprehensive discussion of related work in Appendix A.
O(T) and that of Gos InE
least
2 MODEL
System Model. Consider a multi aulti--rmed bandit (MAB) game with E N arms. Each arm k E [K] is associated with a (tt/2)ssubggusssii
reward distribution with unknown mean ((k), e.g.. can be any distribution whose support is [0, 1]. Assume there are M E N4 distributed agents playing this bandit game in T' N rounds. In time slot t [T', each agent E [M] pulls an arm
A E [K] and receives a reward x (A()) drawn from the reward distribution of arm (8)) When more than one agent pulls the same arm, each of them gets an independent reward drawn from the arm's 's distribution. Without loss of generality, assume the K arms are ordered in descending of their mean rewards, i.e., p(1)= > p(2) >
{)) Denote the reward mean gap as A == p(1) ((k) and assume 22 > 0, i.e., arm 1 is the unique optimal arm.
Group regret. This paper uses group regret-the cumulative difference between the optimal policy rewards and an algorithm's 's rewards- as the algorithm's 's performance metric. Each agent's 's optimal policy to pull arm in all rounds. So, under any cooperative algorithm A, the expected group regret of all M agents is defined as follows,
(9) (4 RT = MT)(1) - E Σ SE[M] EET
E
X,
(1)
where the expectation is taken over the randomness of stochastic rewards and algorithm's (agents') decisions.
Maximum individual regret. While the group regret in (1) characterizes overall system performance. individual performance of each agent is important as well, and, among all individual regrets of agents, the maximum one is usually more important. For example, in drone swarm, the failure/mishehavior of a single drone, e.g., it crashes into other drones, can dramatically degrade the whole system's 's overall performance; in network measurement, the slowest inference engine determines how fast the network parameters, c.g., traffic flows and channel bandwidths, are learned. In the above systems, one can define the individual regret objective as follows,
LE Rijd (A)) Tp(1) EE minse[M] Σ x xx (4.00)
Communication times. Agents in the system cooperate with each other by communicating their reward observations reward averages. Any message (if communicated) is broadcast to all agents and received within a single time slot. A broadcast message includes an arm index, the average arm reward for all observations since the previous broadcast, and the number of observations. The total number of messages communicated among these M agents quantifies the communication times of an algorithm. We count each broadcast as one message². Hence, the communication times under
In this paper, for any integer L we denote the set 21, L} as [4].
"In this work, we choose the name "communication times" emphasize that we focus on reducing the number of communicated messages/communicatio communication. e.g., Wang et al. (2020b); Hanna et al. (2021): Shi et al. (2021b). Studying the necessary bits for TCOM is an interesting further work, e.g., one can consider apply the adaptive differential communication (Shi al., 2021b) our observation sharing.
rounds. There are some works considering the bits in
3

---

Published as a conference paper at ICLR 2023
algorithm A are defined follows,
E [[TT(A)]= E | Emery {agent broadcasts one message in time slot 1}
Model extensions. For ease of presentation of the core ideas, we focus on simple model formulation where agents reside on a complete graph (i.e., one clique) and incur no communication delays. In Appendix G. we extend the basic model and communication policy TCOM account for arbitrary communication topology and deterministic communication delays. These demonstrate the generality of our core algorithmic ideas.
3 ALGORITHM DESIGN
In this section, we devise a cooperative learning algorithm, UCB-TCOM, which attains the near-optimal results of not only group regret but maximum individual regret as well with only ((oog(oo T)) communication times. The core of UCB-TCCM is a communication strategy TCOM that can run on top of diverse bandit learning algorithms in multi-agent systems. Specifically, TCOM determines how an agent broadcasts its reward observations to other agents, while the underlying bandit learning algorithm, c.g., UCB, Thompson sampling, climination, determines how each agent pulls arms. 3 In $3.1, we present TCOM as the communication module of our algorithm design. Then, in $3.2, show how to integrate TCOM with UCB as the underlying bandit algorithm to obtain UCB-TCOM.
Recall that in CMA2B, the near-optimal group regret (((K/A2) log T)) (Wang et al., 2020a, $1.2) is the summation of individual regrets of all agents. Therefore, minimizing the maximum individual regret is equivalent equalizing individual regrets of all agents. Uniformly dividing the group regret to each individual agent can be achieved by a symmetric learning structure where agents pull same arms each time slot. However, in current state-of-the-ar algorithms, e.g. the leader- follower algorithm DPE2 (Wang et al., 2020a), agents usually take different roles-some explore and other exploit- and thus those algorithms are suboptimal on the individual regret objective. For another thing. some straightforward symmetric learning algorithms, e.g., cooperative UCB (Yang et al., 2022, $III.B) where agents communicate and take the same action in every time slots, requires high communication times; most are O(T). Instead UCB-TCOM proposes novel communication policy TCOM to maintain a symmetric learning structure with low communication times. Especially, to maintain the symmetric learning structure, agents only utilize global reward observations. Here "global" " observations refer to those observations that have already been broadcast to all agents, excluding those recent reward observations that have not been shared (i.e., only local one agent).
3.1
TCOM: A TUNABLE COMMUNICATION POLICY
key idea of TCOM based on the observation that the benefit of cooperation in multi-agent setting comes primarily from sharing information regarding suboptimal arms instead of the optimal arm. Specifically, an agent can avoid pulling suboptimal arm when she receives external observations from others, while sharing observations from the optimal arm may not necessarily reduce individual agent regret, e.g., sharing information about an optimal arm while other agents still need to exploit the optimal arm will not decrease regret but merely increase communication times. So, instead of paying the cost for communicating the optimal arm observations, an agent can let other agents explore the optimal arm by themselves. Hence, agents reduce overall communication overhead by refraining from communicating the optimal arm's 's rewards while still guarantecing ncar-optimal from which
regret. To implement the above idea, each agent constructs communication TCOM dynamically excludes the arms that are likely to be optimal. Then, each agent only shares observations about potentially suboptimal arms in the communication arm set. We explain how to construct the communication arm set in $3.1.1.
The communication arm set technique in the previous paragraph reduces communication times to (log T'). To further reduce communication times, another key idea of TCOM is to aggregate an arm's 's multiple observations and send their average at one time. Naively applying phase-based
Bessddes the UCB-TCOM algorithm presented in this section, also preset the Thompson sampling and climination based algorithm in Appendix F
4

---

Published as a conference paper at ICLR 2023
communication protocol, e.g., the one in (Wang et al., 2020b), to aggregate arm observations does not automatically further decrease communication times to O[log(log Because the phase-based protocol was used to achieve O(log T') communication times which is already reached via the communication arm set technique. Instead, one needs to break the pre-assigned rigid phased- based communications, i.e., observations of all arms are communicated together at the end of each phase, and allow each arm den-dddeningg on how many times it lies inside the communication arm sct-to have its own specific and dynamic phases for communications. This idea is implemented by carefully designed observation- buffering technique. The novel technique can boost the above communication arm set technique and further reduce communication times to Olog(loo T)). We formalize this idea in $3.1.2.
3.1.1 CONSTRUCTION OF THE COMMUNICATION ARM SET
In each time slot, each agent determines its communication arm set by comparing its estimated confidence intervals of the reward means. Let (k) denote the number of times of the global reward observations of arm & up to time slot t. That is, the number of observations that has been broadcast across the whole CMA2B. Let (k) denote the mean reward estimate of these (k) observations. Then, given the empirical mean Pú (R:) and the number of observations nu (k), we construct tunable confidence interval for the true reward mean pakk by Hoeffding" inequality (Hoeffding, 1994). The confidence interval centered at je (k) has width CI,(k, a) expressed as
CI,(k, a) //vlooo (kf
where E (-o0, 0o) is tunable parameter. The reward mean (()) lies inside the confidence interval (k) - CI (ks, a), (k) + CI,(k,
(k, a:) with probability of at least 1 - 2t=2aa (see Lemma 1 in Appendix B.2). We define the tunable upper and lower confidence bounds of fdo (k) as
EUCB, a) = (b) + (l, ELCB,(k, a) = (c(k) - cI,
For any arm k, if there exists another arm k' whose upper confidence bound tUCB, ar) is greater than arm k's lower confidence bound SLCB,(k, (k;, a), then arm k's mean reward estimate is significantly greater than those of others. In this case, arm l is potentially identified as suboptimal, and its new observation (if any) should be broadcast to others. Formally, given tuning parameter a, communication arm set C, (a) of agent at time t contains all arms identified as suboptimal, i.c.,
Ca(a) = [k+ E [K] ER [K] \ {b} such that tUCB, a) LLCB,(k, a))-
(3)
Remark 1 (Comparison to the candidate arm set of elimination algorithms). At the first glance, the communication arm set in (3) similar to the active arm elimination (AAE) policy's 's candidate arm set (Auer et al., 2002; Even-Dar al., 2006; Yang et al., 2022). However, the two sets have intrinsically different usages: TCOM constructs the communication arm set to determine how to broadcast observations, while AAE uses its candidate set to determine how to pull arms.
Remark 2 (Comparsion to ComEx (Madhushani & Leonard, 2020; 2021)). The intuition we utilize in this subsection- communicainniiinnn the observations of suboptimal arms more useful than that of the optimal arm han also been observed in Madhushani & Leonard (2020; 2021). Compared to ComEx, the algorithmic novelties of TCOM are (1) applying confidence intervals to more accurately identify the suboptimal arms; (2) combining the observation-bufferin broadcast with the communication arm set technique; (3) including unablle parameters with more flexibility. The detailed algorithm design comparisons are deferred to Appendix A.I. Furthermore, as we mentioned in Table 1. ComEx fails to achieve the near optimal individual regret and its communication times Ollog T) are not as good as Ollog(log (logT)) result.
3.1.2 INDERVATIONN-UTTTESS OBSERVATION--BUTERINN BROADCAST
While the straightforward immediate broadcast observation sharing method can produce near- optimal group regret, its Olog T') communication times are not efficient. Prior literature (Desautels et al., 2014; Gao et al., 2019) has shown that the near-optimal regret in stochastic bandit games is preserved in the presence of a constant delay before receiving reward observations (Desautels et al., 2014), and the regret upper bound does not deteriorate too much when delays increase according to a geometric sequence (Gao et al., 2019). These results suggest that it is not necessary to immediately communicate the latest observations. Instead, to reduce communication times, the
5

---

Published as a conference paper at ICLR 2023
Algorithm 1 The UCB-TCOM Algorithm (for each agent)
1: Input: the communication arm set parameter and buffering ratio _
2: Initialization: (k( = 0. .k)(k) O, (k) = 0, (k)
3: for each decision round t do
Both for-loops (Lines 3 and 15) run in parallel.
4: Pull arm A, with the highest global UCB
5: Observe arm A, 's reward (x,)
6: if A, E (a) then
7: Increase (A,) by
8: Update this phase's empirical mean (As) end if
9:
10: if (A,)) > [3NT((A.) then
11:
Broadcast the message (A,, (a())), (A))))A)))))) A.)
12:
(A() +-
13:
end if
end for
15:
for each newly received message (#+( N₂ (k). from the past decision round do
16: Update the empirical mean (k) R. (k)))))) (A) (k)1--/9))
[x 1/3]]
17:
Increase (k) by (+) - 1
18: Update the communication arm set C, (a) via (3) based tunable confidence bounds
19:
end for
policy can aggregate multiple reward observations from an arm and communicate their sample mean in one message. Combining this mechanism with the designed communication arm set in (3) leads to communication policy TCOM.
Next, we present how the buffering mechanism controls observation aggregation. Denote by (k) the number of times that an agent pulls arm & when the arm lies inside the communication arm set, i.c., k E Ca)a), up time t. Therefore, (k) is the number of messages agent would broadcast, each containing a single arm l observation, one employs immediate broadcast. Instead of immediate broadcast, buffer observations and then broadeast their average when the number of observations (since previous broadcast) increases by ratio. For example, if the ratio is 2, the agent sends arm k's reward average of the arm's new observations since last broadcast whenever the counter N₂ Nk) equals 2, 4, 8, 16, ..,, etc, or power of 2. More generally, let 3 (> 1) denote a ratio parameter that controls how the buffering size of reward observations increased. When counter (k(k) increases to [,N, (k)] since the last time agent broadcast arm k' average reward, i.e., N₂ (k) > [k)], then agent broadeasts a message including the arm index the counter N₂ (k)), and the sample mean tu (k), of this arm's latest [N) - 1) observations to other agents. Due to the space limit, the detailed discussion of TCOM's tunability on parameters a and 33 is deferred to Appendix D.
3.2 UCB-TCOM: APPLICATION OF TCOM ON THE UCB ALGORRITH
In this section, demonstrate how to leverage the communication policy TCOM to develop communication--ffiiieee extension of cooperative UCB. We call the proposed algorithm UCB-TCOM.
In slot t, agent chooses the with the largest global UCB index, i.e., A, arg max; (C), where UCB,(k) (A) == P. (k) + / log t/ (k), and observes the arm's reward x(()) (1) (A,). Note the UCB indexes and action A, are the same for all agents; thus omit their superscript (f). After pulling
arm Ag, the agent checks whether the arm in its communication arm set C, (Line 6); yes, counter Ne(AA) is increased by and the buffered reward sample mean is updated (Lines 7-8). When the counter (r(A:) is increased by factor 3 since the last time slot that agent communicated arm A,'s 's sample mean (Line 10), the agent sends out arm A, 's sample mean to other agents (Line 11). Meanwhile, if the agent receives messages from other agents, it updates its estimates accordingly (Lines 16- 18). The details are presented Algorithm 1.
THEORETICAL RESULTS
In this section, we analyze the regret and communication times of UCB-TCOM (Algorithm 1).

---

Published as a conference paper at ICLR 2023
4.1 RESULT OVERVIEW
We present near-optimal group and individual regret upper bounds of UCB-TCCM in Theorem 1. Theorem 1 (Regret upper bounds of UCB-TCOM for 1). When the communication arm set parameter a 1st and nuffering-ratie 3 1, UCB-TCOM (Algorithm 1) attains a near-optimal group regret upper bound in terms number decision rounds T, arms K, and agents M, formally,
88 + MK 20 -
E (A))
(4)
a² 1
and UCB-TCOM
(Algorithm (Algoorrtt also attains a near-optimal individual regret upper bound, or formally,
83logT T
2a -1
E E ind (A))
K
(5)
MA.
a²
KS1
Theorem I's group regret proof is based on the observation that most suboptimal arm observations are broadcast when a >> (see Theorem 2(ii)), and the fact that under the observation buffering mechanism the number of observations of suboptimal arms increases by at most ratio of /3 between broadcasts. Theorem Iss individual regret proof is based on the fact that all M agents are symmetric- they always pull the same arms. Proofs of Theorem is given in Appendix B.3.
In Theorem 2, we present the communication times of UCB-TCOM, It shows how parameter influences the communication of optimal and suboptimal arms observations.
Theorem 2. The communication times of UCB-TCOM has the following properties:
(i When a < -v2, no communication occurs among agents.
When -22 < a < /2 and 3 > 1, the number of broadcasts of observations of the optimal arm by one agent O (log T)). More rigorously, it is less than
2
[22++ +
(
(8log T A
2a a²
logg
V22-a
-
MK
(6)
(iii) When almost all observations of suboptimal arms except for finite number independent -are broadcast.
are
(iv) When a > 2v/2x(1) almost all observations of the optimal arm except for a finite number Du
that is independent Tf broadcast.
The proof of Theorem 2(i) follows from the fact that when < <-v2. the pulled arm's 's LLCB index greater than those tUCB indexes of all other arms, which violates the communication arm set's condition in (3). Hence, the pulled arm never lies inside the communication arm set, and thus no communication occurs. The proof of Theorem 2(ii) is based on the geometric growth of the time interval between broadcasts and a key observation: the number of broadcasts of the optimal arm's observations upper bounded by some suboptimal arm k's total number of pulls, that is, (1)(()) < ((V2+ a)/(v² - 2n) (4) (k). Theorems 2(ii)) and 2(iv) are derived by excluding some well-designed small probability events and from the fact that the arm mean rewards lie inside their tunable confidence intervals with high probability. The proof of Theorem 2 is given in Appendix B. B.4.
Remark 3. Theorem 2's proof is not a simple extension of the analysis of previous algorithms. First, TCOM relies on a group of tunable confidence intervals to identify suboptimal arms and communicate new observations while ComEx are only based arm empirical reward mean; special case of tunable confidence intervals. Second, the observation-bufferigg broadcast incurs additional delays of the global observations sharing which is a unique challenge in TCOM. We defer the detailed explanation of both challenges to Appendix B.I
'Thcorem I's condition Appendix B.2). This condition can be relaxed a > 1 via the peeling technique (see Appendix C) where (4)'s 's second term will also change accordingly. This relaxation is also applicable to Theorem 2(ii).
1 remnant from bounding a small probability event (see Lemma in
7

---

Published as a conference paper at ICLR 2023
4.2 DISCUSSIONS
(a) Regret optimality of UCB-TCOM. The following asymptotic lower bound has been established in the classic bandits literature (e.g.. Lai et al. (1985)):
[[R((A))
lim inf T-00
log T
R>1 KL(U,,
where 2t the reward distribution of arm & and KL is the Kullback-Leibler divergence between two probability distributions. When the reward distributions are Bernoulli or Gaussian, the regret lower bound can be written as S2( (log T/As), (Lattimore & Szepesvári, 2020, $16). Since the CMA2B model has the same objective the centralized (single agent) MAB model, it inherits this group regret lower bound (Wang et al., 2020a, $1.2) under any possible communication policies. Given this lower bound, Theorem I's group regret upper bound in (7) is near-optimal, i.c., it is tight up to a constant factor.
Recall that the individual regret in (2) corresponds to the maximal individual regret among M agents. Since the maximal individual regret is minimized when all agents uniformly pay the regret time, from the above group regret lower bound, one obtain the following individual regret lower bound,
ind (AA) E E
1 M 1>1
lim inf
log T
KL(Uk, PI)
Compared to this lower bound, Theorem I's individual regret upper bound in (5) is also near-optimal.
(b) Impact of cooperation and number of agents M on group regret. If there no cooperation among the M agents-cach agent individually plays the game, then the group regret is lower bounded as follows:
E[RT(A)) log
inf T-000
M
KL(
which is M times worse than the group regret achieved by UCB-TCOM in Theorem 1. This highlights the benefits of cooperation. Furthermore, when the number of rounds T is large, the second term containing M factor in the group regret (4) is negligible. That is, the group regret of UCB-TCOM does not increase rapidly when the number of agents M increases, while it would without cooperation.
(c) Individual regret comparison to the leader-follower algorithm. Equation (5) shows that the individual regret of UCB-TCOM deceases as the number of agents M increases. This is in contrast to DPE2 (Wang al., 2020a) based on the leader-follower paradigm, which attributes all exploration costs to single leader, and thus DPE2's individual regret is M times worse than that of UCB-TCOM. In many large-scale distributed systems, e.g., edge computing, database, etc., computational resources are often distributed geographically. The largest individual computational time that these distributed nodes (agents) need to pay can mapped to the individual regret. From this perspective, UCB-TCOM with the oear-optimal individual regret is preferable to DPE2 especially when M is large.
(d) Communication Times of UCB-TCOM. Theorem 2(ii) shows that when -22 <a < V2, the number of broadcasts of the optimal arm's observations is (log(log T)). Additionally, the observation buffering mechanism also aggregates the suboptimal arms O T) observations into Olog(log T)) broadcasts. So, in this case, UCB-TCOM only incurs O(log log 7)) communication time. Combined the above with Theorem 1 shows that when < a < V2 and 3 > 1, UCB- TCOM enjoys the near-optimal group and individual regret upper bounds with only O(log(Igg T)) communication times.
We also discuss how parameters a and 8 of TCOM influence cooperation among the agents and how they impact communication times and regret in Appendix D.
5 NUMERICAL SIMULATIONS
Experiment setup. Unless otherwise stated, the experiments consist of M = 25 agents and = 20 arms, communication parameter 1.2, buffering ratio B = 2, and T 300 000. Each arm is
8

---

Published as a conference paper at ICLR 2023
+ UCB-TCDM GosInE Dec.UCB A DPE2
ComEx
COUCB
11
0.5 =100
Group Regret
Indiviuud Regret
Communication
10
Time slot
<10*
Time slot
<10
Time slat
<10*
(a) Group regret
(h) Individual regret
(c) Communications
Figure I: UCB-TCOM vs. Dec_UCB, Gos InE, DPE2, ComEx and COUCB
associated with Bernoulli reward random variable whose mean is uniformly randomly taken from Ad-Clicks (Avito, 2015). All results are averaged over 50 trials and their standard deviations are plotted shaded regions.
Comparison to state-of-the-art baselines. We consider five baselines: Dec_UCB (Zhu et al., 2021a), Gos InE (Chawla al., 2020) DPE2 (Wang al., 2020a), ComEx (Madhushani & Leonard, 2021) 1), and COUCB. The first four are discussed in Table 1. To compare all algorithms fairly, we implement them using the same undirected complete communication graph where agents can broadcast its observations to all other agents. The communication times of Gos InE is set to as small as the algorithm allows. COJCB is naïve adaptation of UCB in CMA2B, where each agent runs an instance of UCB and always immediately broadcasts its new reward observations to other agents.
Comparison results are reported in Figure 1. Both group and individual regrets are reported in Figures la and lb as function of time. UCB-TCOM performs only slightly worse than the best algo- rithm (DPE2 in group regrets, COUCB in individual regrets). Figure 1c compares the communication times of these algorithms in the log scale. It corroborates the fact that UCB-TCOM-I'S Oloo T)) communication times lie between ComEx and GosInE's Ollog T) and DPE2's O(1) performance.
We also provide additional simulations in Appendices D, and F.
CONCLUSION
In this paper, we proposed communication policy TCOM which, combined with diverse single-agent bandit learning algorithms, can be used to devise fully distributed cooperative multi-agent bandit learning algorithms. We specifically study the UCB-TCOM algorithm where agents pull arms via UCB and communicates via TCOM. We show that UCB-TCOM can attain both near-optimal group and individual regrets while only incurring Olooglog T)) communication costs. Extensive simulations are also reported to support our results.
We note that TCOM also be tuned to balance the regret and communications. One interesting future work is to systemically study the Pareto frontier of group/individual regrets vs. communication times from the perspective of the upper bounds of TCOM and the intrinsic lower bounds (difficulties) of CMA2B as well.
7 ACKNOWLEDGEMENTS
The work of Mohammad Hajiesmaili is supported by NSF CAREER- 2106299, and 2NS-2102963. The work of Don Towsley is funded in part by US Army contract INF-17-2-0019 The work of John C.S. Lui is supported in part by the RGC's GRF 14215722. Lin Yang is the corresponding author.
(PS-2136199, CNS-

---

Published as a conference paper at ICLR 2023
REFERENCES
Deepak Agarwal, Bee-Chung Chen, Pradheep Elango, Nitin Motgi, Seung- Taek Park, Raghu Ra- makrishnan, Scott Roy, and Joe Zachariah. Online models for content optimization. Advances in Neural Information Processing Systems, 21, 2008.
Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pp. 39-1. JMLR Workshop and Conference Proceedings, 2012.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256, 2002.
Avito. Avito context aal--addcclckee
Context Ad Clicks, 2015.
https: /ttps::/www.... www.www..gle... com/ c/
Yogev Bar-On and Yishay Mansour. Individual regret in cooperative nonstochastic multi-armed bandits. Advances in Neural Information Processing Systems, 32, 2019.
Etienne Boursier and Vianney Perchet. Sic-mmab: synchronisation involves communication in multiplayer multi-armed bandits. Advances in Neural Information Processing Systems, 32, 2019.
Sébastien Bubeck. Bandits games and clustering foundations. PhD thesis, Université des Sciences et Technologie de Lille-Lille I, 2010.
Swapna Buccapatnam, Jian Tan, and Li Zhang. Information sharing in distributed stochastic bandits. In 2015 IEEE Conference on Computer Communications (INFOCOM), pp. 2605-2613 IEEE, 2015.
Ronshee Chawla, Abishek Sankararaman, Ayalvadi Ganesh, and Sanjay Shakkottai. The gossiping insert-eliminate algorithm for multi-agent bandits. In International Conference Artificial Intelligence and Statistics, pp. 3471-3481. PMLR, 2020.
Alan Demers, Srinivasan Keshav, and Scott Shenker. Analysis and simulation of fair queueing algorithm. ACM SIGCOMM Computer Communication Review, 19(4)1112, 1989.
Thomas Desautels, Andreas Krause, and Joel W Burdick. Parallelizing exploration-exploite tradcoffs in gaussian process bandit optimization. Journal of Machine Learning Research, 15: 3873-3923, 2014.
Abhimanyu Dubey et al. Cooperative multi-agent bandits with heavy tails. In International Conference Machine Learning, pp. 2730-2739. PMLR, 2020.
Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006.
Raphaël Féraud, Réda Alami, and Romain Laroche. Decentralized exploration in multi-armed bandits. In International Conference on Machine Learning, pp. 1901-1909. PMLR, 2019.
Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengging Zhou. Batched multi-armed bandits problem. Advances in Neural Information Processing Systems, 32, 2019.
Osama A Hanna, Lin F Yang, and Christina Fragouli. Solving multi-am arm bandit using a few bits of communication. arXiv preprint arXhv:2111.00667 2021.
Eshcar Hillel, Zohar S Karnin, Tomer Koren, Ronny Lempel, and Oren Somekh. Distributed exploration in multi-armed bandits. Advances Neural Information Processing Systems, 26, 2013.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. In The collected works Wassily Hoeffding, pp. 409 426. Springer, 1994.
Ruiquan Huang, Weiqiang Wu, Jing Yang, and Cong Shen. Federated linear contextual bandits.
Advances in Neural Information Processing Systems, 34, 2021.
10

---

Published as a conference paper at ICLR 2023
Jingyan Jiang, Liang Hu, Pingting Hao, Rui Sun, Jiejun Hu, and Hongtu Li. Q-fdba: improving qoe fairness for video streaming. Multimedia Tools and Applications, 7709):17777- 2018.
Long Jin, Shuai Li, Lin Xiao, Rongbo Lu, and Bolin Liao. Cooperative motion generation in distributed network of redundant robot manipulators with noises. IEEE Transactions on Systems, Man, and Cybernetics: Systems,
2017.
Wassim Jouini, Damien Ernst, Christophe Moy, and Jacques Palicot. Upper confidence bound based decision making strategies and dynamic spectrum access. In 2010 IEEE International Conference on Communications, pp. 1-5, IEEE, 2010.
Nikolai Karpov, Qin Zhang, and Yuan Zhou. Collaborative top distribution identifications with limited interaction. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pp. 160-171. IEEE, 2020.
Ravi Kumar Kolla, Krishna Jagannathan, and Aditya Gopalan. Collaborative learning of stochastic bandits over a social network. IEEE/ACM Transactions on Networking, 2684):1722-1755, 2018.
Tze Leung Lai, Herbert Robbins, et al. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard. Distributed cooperative decision- making in multiarmed bandits: Frequentist and bayesian algorithms. In 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 167-172. IEEE, 2016.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Lihong Li. Wei Chu, John Langford, and Robert Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661-670, 2010.
Shuai Li, Ruofan Kong, and Yi Guo. Cooperative distributed source seeking by multiple robots: Algorithms and experiments. JEEE/ASME Transactions on mechatronics, 1966)1810-1820 2014.
Keqin Liu and Qing Zhao. Distributed learning in multi-armed bandit with multiple players. IEEE transactions on signal processing, 58( 1556166656765611 2010.
Richard TB Ma. Dah Ming Chiu, John CS Lui, Vishal Misra, and Dan Rubenstein. Internet economics: The use of shapley value for isp settlement. IEEE/ACM Transactions on networking, 18(3):775-777, 2010.
Udari Madhushani and Naomi Leonard. doesn't get better and here's why: A fundamental drawback in natural extensions of ucb multi-agent bandits. In "I Can't Believe It's Not Better! "NeurIPS 2020 workshop. 2020.
Udari Madhushani and Naomi Leonard. When to call your neighbor? strategic communication in cooperative stochastic bandits. arXiv preprint arXiv:2110.04396, 2021.
David CaatúnezzRubio. Varun Kanade, and Patrick Rebeschini. Decentralized cooperative stochastic bandits. Advances in Neural Information Processing Systems, 32, 2019.
Abbas Mehrabian, Etienne Boursier, Emilie Kaufmann, and Vianney Perchet. A practical algorithm for multiplayer bandits when arm means vary among players. In International Conference on Artificial Intelligence and Statistics, pp. 1211-1221. PMLR, 2020.
John Rawls. A theory of justice. In Ethics, pp. 229-234. Routledge, 2004.
Chengshuai Shi and Cong Shen. Federated armee bandits. In Proceedings of the 35th AAAI Conference Artificial Intelligence (AAAI), 2021.
Chengshuai Shi, Cong Shen, and Jing Yang. Federated multi armed bandits with personalization. In International Conference Artificial Intelligence and Statisties, pp. 2917-2925. PMLR, 2021a.
11

---

Published as a conference paper at ICLR 2023
Chengshuai Shi, Wei Xiong, Cong Shen, and Jing Yang. Heterogeneous multi multi- bandits: Closing the gap and generalization. Advances in Neural Information Processing Systems, 34, 2021b.
Rayadurgam Srikant and Lei Ying. Communication networks: an optimization, control, and stochastic networks perspective. Cambridge University Press, 2013.
Balazs Szorenyi, Róbert Busa-Fekete, István Hegedus, Róbert Ormándi, Márk Jelasity, and Balázs Kégl. Gossip-based distributed stochastic bandit algorithms. In International Conference on Machine Learning, pp. 19-27. PMLR, 2013.
Chao Tao, Qin Zhang, and Yuan Zhou. Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi-armed bandits. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pp. 126-146 146. IEEE, 2019.
Po-An Wang, Alexandre Proutiere, Kaito Ariu, Yassir Jedra, and Alessio Russo. Optimal algorithms for multiplayer multi-armed bandits. In International Conference on Artificial Intelligence and Statistics, pp. 4120-411 4129. PMLR, 2020a.
You-Gan Wang. Sequential allocation clinical trials. Communications in Statistics-Theory and Methods, 20(3):791-88) 1991.
Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: Near-optimal regret with efficient communication. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020b.
Lin Yang, Yu-zhen Janice Chen, Mohammad Hajiesmaili, John Lui, and Don Towsley. Distributed bandits with heterogeneous agents. arXiv preprint wrXiv:2201009355 2022.
Jingxuan Zhu and Ji Liu. A distributed algorithm for multi-armed bandit with homogeneous rewards over directed graphs. In 2021 American Control Conference (ACC), pp. 3038-3043. IEEE, 2021.
Jingxuan Zhu, Romeil Sandhu, and Ji Liu. distributed algorithm for sequential decision making in multi-armed bandit with homogeneous rewards. In 2020 59th IEEE Conference Decision and Control (CDC), pp. 3078-3083, IEEE, 2020.
Jingxuan Zhu, Ethan Mulle, Christopher Salomon Smith, and Ji Liu. Decentralized multi-armed bandit can outperform classic upper confidence bound. arXiv preprint arXiv:2111./0933, 2021a.
Zhaowei Zhu, Jingxuan Zhu, Ji Liu, and Yang Liu. Federated bandit: gossiping approach. In Abstract Proceedings of the 2021 ACM SICMETRCCS/Iermattiodd Conference Measurement and Modeling of Computer Systems, pp. 3-4, 2021b.
12

---

Published as a conference paper at ICLR 2023
A RELATED WORKS
CMA2B with a central server or leader. Many distributed bandits models (Wang et al., 2020b;a; Shi & Shen, 2021; Shi et al., 2021a; Mehrabian et al., 2020; Shi et al., 2021b) assume the existence of a central server or elect a leader among agents. We choose two mostly related works to discuss. Wang et al. (2020b) consider the CMA2B model with a central server. The server collects informa- tion from each agent and then sends its aggregated information back to each agent. Specifically, Wang et al. (2020b) propose phased-based elimination algorithm that achieves the near-optimal problem-ing inglllmm-ndeeeddent regret bound O(VKMT KM log M)) with finite number of communication times (independent of the number of rounds 7). However, when it comes to near-optimal problem- dependent regret upper bound which the focus of this paper, their algorithm suffers logarithmic communication times while our algorithm only incurs O(log( 7)) communications, Wang et al. (2020a) propose the DPE2 algorithm for CMA2B based on a leader-follower paradigm: The leader takes the responsibility of exploring while other agents (followers) only exploit arms recommended by the leader. Although it achieves the optimal group regret with finite number of communications, the DPE2 algorithm is inherently unfair one single agent, the leader, incurs almost all regret O(K log T) while other followers only incur finite regrets (()). We also note that algorithms of previous works heavily rely on central server (or elected leader) and thus are vulnerable to attacks on the central server (or a leader), while fully distributed algorithms that this paper studies can tolerate such attacks.
CMA2B without a central server. The fully decentralized CMA2B model has been studied in Buc- capatnam et al. (2015); Landgren et al. (2016); Kolla et al. (2018); Martinez-Rubio et al. (2019), where they mainly focus on minimizing regrets and seldom quantify their communication times. Some of these algorithms assume that agents can gossip with each other, e.g.. via a graph represented by the gossiping matrix (Martínez-Rubbl protocols (Szorenyi et al., 2013). In their gossip setting, agents can only communicate with their neighbors. This is fairly different from our all-agent broadcast communication (in Appendix G.2, we relax the all-agent broadcast in TCOM to communication with neighbors in the graph). Recently, Madhushani & Leonard (2021) proposed a communication protocol, ComEx, which aims to limit the communications of optimal arm's 's reward observations. Our tunable communication policy TCOM subsumes ComEx special case (see Remark 1). Also, ComEx incurs Ollog T) communication times while our algorithm only needs Olog(log T)) to attain the near-optimal regret upper bound.
et al., 2019: Chawla et al., 2020), or via peer-to-peet
Beyond the above related work, there are other works distributed bandits such federated bandits (Shi & Shen, 2021; Shi et al., 2021a; Zhu et al., 2021b; Huang et al., 2021), distributed bandits with collision setting (Boursier & Perchet, 2019; Mchrabian et al., 2020; Wang et al., 2020b; Shi et al., 2021b). and cooperative pure exploration (Hillel et al., 2013; Tao et al., 2019; Karpov et al., 2020). The federated bandits (Shi & Shen, 2021; Shi al., 2021a; Zhu et al., 202 lb; Huang et al., 2021) consider heterogeneous local reward distributions, which is different from our homogeneous reward environment. distributed bandits with collision setting model (Boursier & Perchet, 2019; Mehrabian et al., 2020; Wang et al., 2020b; Shi et al., Ib), when more than one agent chooses the same arm, each of these agents gets a zero reward, while our model, each of these agents obtains an independent reward. Cooperative pure exploration (best arm identification) (Hillel et al., 2013; Tao et al., 2019; Féraud et al., 2019; Karpov et al., 2020) study how multi-agent cooperation can reduce the sample complexity of identifying the best arm which is a different objective from work on regret minimization. Some of their high-level ideas in communication are similar to TCOM, e.g., Hillel et al. (2013) utilize the doubling phase for communication and Féraud et al. (2019)'s algorithm communicates bad arms. However, as we discussed in Appendix 1, our algorithm is novel in specific design detail, and thus introduces unique challenges that cannot be addressed by the techniques of these known works.
Individual regret in CMA2B With the majority of previous CMA2B works studying the group regret objective, the individual regrets were also studied sparingly, e.g., in stochastic CMA2B (Zhu et al., 2021a; Zhu & Liu, 2021; Zhu et al., 2020), in adversarial CMA2B (Bar-On & Mansour, 2019), and in federated bandits (Zhu et al., 2021b). Among them, Zhu et al. (2021a) was the most related to ours, where they devised algorithms that achieved the near-optimal individual regret with OTT) communication times, while our algorithms, with near-optimal individual regrets as well, only needs Olog(log T)) communication times.
13

---

Published as a conference paper at ICLR 2023
A.1 DETAIL COMPARISON TO COMEx
TCOM shares some high-level ideas from known algorithms. However, when it comes to the algorithm design details, TCOM needs resolve unique challenges improve the state-of-the-ard result. There are three algorithmic ideas in the design of TCOM which enables improving the state-of-the-art result in the literature. In the following, we outline each idea separately and clarify its novelty as compared to the most relevant prior work.
On how to identify suboptimal arms: algorithmic idea is ComEx [Madhushani et. al., 2021] where arms with suboptimal empirical reward means are identified as suboptimal communication. In TCOM, however, we utilize group of tunable confidence intervals, which compared to the empirical means in ComEx, provides a clearer separation between optimal and suboptimal arms. Further, we emphasize that although using confidence intervals in bandits is classic technique for minimizing regret, TCOM instead uses confidence intervals to decide whether an arm's ' observation should be shared or not. It is worth noting that the dynamic construction of the communication arm set emphasizes the need for different proof techniques than those in ComEx, which is elaborated Appendix B.I.
The most related work with similar high-level
2. On how to buffer observations: Observation buffering (a.k.a. phase-based communication) has been used in previous works, e.g., [Shi et. al.. 2021], where applying this techniques can achieve (log I') communication times. However, TCOM has its own technique for construction of communication arm sets (relevant to the first algorithmic idea above), which already enjoys a (log T) communication times improvement, without using batched communication. Therefore, simply applying the batched communication technique does not automatically improve the communication times of TCOM. Instead, we design an arm- whether
specific inservattion-uufeene mechanism which allows each arm- aeddddeeding it lies in the communication arm set-to have its own specific and dynamic phases for communication. This carefully designed dnservation-buferiii technique can boost TCOM's first communication arm set technique and further reduce the communication times to (log(log T)).
3.
On algorithm design with tunable parameter: Last, unique to our algorithm design, we introduced two tunable parameters a and 3 that determine how to add arms into the dynamic communication arm set based on their confidence intervals. This addition provides greater flexibility to TCOM, which is explained in details in Appendix D.
B PROOFS IN ANALYSIS (SECTION 4)
B.I HIGHLIGHT OF ANALYSIS CHALLENGES
TCOM utilizes two techniques: communication arm set construction ($3.1.1) and eexervation-bufferinn broadcast ($3.1.2). Each technique alone reduce the communication times to O(log 7), and TCOM combines both to further reduce the communication times to Olog(log 7)). This Oloog (log T)) result comes directly from the TCOM policy design. The major challenge in analysis is to establish that-with these reduced and delayed sharing observations due to TCOM-the UCB-TCOM algorithm still preserves the near-optimal group and individual regrets. To do so, we show (1) the communication arm set construction technique can prevent communicating most optimal arm observations while allow communicating most suboptimal arm observations; (2) the observation sharing delay due to the sntevaation-uufferin broadcast technique (upon the communication arm set technique) does not have an intrinsic impact on UCB-TCOM's group and individual regret performance.
(1) Although the communication arm set construction technique shares the high level idea of ComEx (Madhushani & Leonard, 2021), the analysis of ComEx not applicable to TCOM. Be- cause the empirical means utilized for identifying the suboptimal arms in ComEx is only a special case of the tunable confidence intervals that TCOM relies on. Therefore, to show that agents can prove
selectively share suboptimal arms' observations by the communication arm set technique, two new results: (a) the optimal arm's 's observations are often not broadcast (i.c., the optimal arm is often not in the communication arm set, Theorem 2(i));; (b) suboptimal arm observations are almost
14

---

Published as a conference paper at ICLR 2023
always broadcast (i.e., the suboptimal arms often in the set, Theorem 2(ii)). The (a) is proved via showing that the number of times that the optimal arm is in the communication arm set is no greater than that of an suboptimal arm (multippied by a constant factor); thus is upper bounded by (log T). This is based on revealing a relation between the handit arm pull policy and the communication arm set construction. Then (b) is proved via showing whenever an agent pulls suboptimal arm, the arm is inside the communication arm set with a high probability, and thus the suboptimal arm's 's observations are almost always buffered for later communication.
Our inservattion-ufferrnnn broadcast mechanism shares high-level idea of doubling phase technique, but its specific design is different from known ones, and, consequently, its analysis addresses novel challenges. The doubling phase technique was utilized in CMA2B literature, e.g., Boursier & Perchet (2019); Wang al. (2020b); Shi et al. (2021b), where their arm pull policies within a phase were either uniformly pulling each arm (Boursier & Perchet, 2019; Wang et al., 2020a) or sticking to several arms (Shi al., 2021b). However, different from these previous "rigid" arm pull policies, UCB-TCOM applies the "flexible" UCB arm pull policy. In order to adapt the doubling phase technique to the UCB policy, we propose the observation -ouiroinnn-ffriigggg broadcast mechanism which separately buffers the observation of each arms and respectively communicates each arm's 's compound observations whenever this arm's 's observation times is doubled (or generally, increased by a 3 factor).
(2) Since this observation buttrratioonufffinggggg broadcast is different from known doubling phase algorithms, Hence, proving that this
their existing analysis approaches are not applicable to observation-bufferiien broadcast mechanism does intrinsically deteriorate the near-optimal group and individual regrets of UCB-TCOM is unique challenge. More specifically, we prove that the delay due to buffering only makes regrets worse by constant factor. This via showing that the Dbservation-buuferiin mechanism separately buffers each arm's observations, and, therefore, the observation delay of each arm's observations (as well as the pulling times of this arm during the delay) can be respectively upper bounded by at most constant factor multiplying this arm's 's total previous pulling times (see (9) of Theorem I's proof as a formal expression).
B.2 PRELIMINARIES
In this subsection, we provide several basic results and definitions that are crucial in the later analysis. Definition 1 (Type-I and Type-II decisions). An agent makes a Type-I decision in time slot if in this time slot all arms' true reward means p(k) lie inside this agent's 's tunable confidence intervals (tLCB,(k a), tUCB, at)) respectively. Otherwise, the agent makes a Type-Il decision.
Lemma 1. For any arm & [K], any agent i [M], and time slot E [T]. the probability that the arm k's true reward mean p(k) lies inside its tunable confidence interval (tLCB, (k, a), (U, (calculated by agent i) is no less than 1 21. 120
Proof of Lemma 1. We first bound the probability that the true reward mean no less than the tunable upper confidence bound tUCB
logt (u(k) > LUCB,(K. a)) =P P.P. (((k) (((k) (e(k)) > V fi (b))
log L
P ((k)) - (x)( > /
(k() = P(nx(k)) = 8)
(k))))
log
P
((()) (k(k)) > a1 (k)
(o((k)
22a
1-22
where the inequality (a) is by the Hoeffding's inequality and that the random variable μ²k) (k) is ()uuuasa)ss With similar derivation, the probability that the true reward mean (a(k)
15

---

Published as a conference paper at ICLR 2023
no greater than the tunable lower confidence bound CLCB, i..,, ju()) < L a). also be upper bounded by z1~20". Therefore, by excluding the above two events, the probability that the true reward mean lies inside the tunable confidence interval is no less than 1 - 122=0
Lemma 2 (Bound the number of times of Type-Il decisions). When 1, the expected total number of times of Type-Il decisions by any agent at any time slot in the system is finite. Specifically, it is less than K 2002
Proof of Lemma 2. That time slot l is Type-ll means that there exists at least one arm whose reward mean lies outside its tunable confidence interval. We bound the expected total number of times of Type-II decisions as follows,
T
P (Ek E [K] such that ((k) & (tLCB,(k, (L)CB)())
K P (u(k) & (IIC
K
PP (u(k)) & (k),
1=1
(4)
2K
1-20"
t=1
T
< 2K
1+
11-2a" 2a
dt
20 1 a² I
MK
where the inequality (a) holds for Lemma 1, and the inequality (b) holds because > 1 (i.e.. 1 2a² < -)).
Next, we state standard property of UCB algorithms and provide its proof for completeness.
Lemma (Adapted from (Yang et al., 2022, Lemma 2)). If at any time t & T agent E [M] by UCB makes a Type-l decision and pulls arm k the total number of globally observed rewards of the arm k. by agent up to time is upper bounded as follows,
8logt
(k) <
A
Proof of Lemma 3. Given that the suboptimal arm Is is pulled by agent i, we have the following inequality
2log
2 V (k)
A..
(8)
Otherwise, we have
2 log I fee
(CB = +
(0)
((L) ((() + A
2 2log Tec(k)
((K) +2
(c) (c((k) +
2log
Pockk)
= UCB
16

---

Published as a conference paper at ICLR 2023
which contradicts the pulling of arm k. Note that inequalities (a) and (c) from Type-I decision's definition that reward means lie inside confidence interval, and incquality (b) due to the inverse of (8). Therefore, (8) holds and rearranging (8) concludes the proof.
B.3 PROOFS OF GROUP REGRET (THEOREM
Proof of Theorem I. To bound the regret, one needs to bound the number of times of pulling subop- timal arms by all M agents in the system. Let k be the index of suboptimal the reward observations of pulling arm k are only broadcast (together as reward means) whenever arm k's local observation times increased by ratio. So, there are delays before receiving other agents' observations. These delays may cause each agent pulling additional number of times of arm k. Next, we show that such delays do not significantly increase arm k's overall pulling times in the system.
In UCB-TCOM,
Note that the communication set contains all suboptimal arms when agents make Type-I decisions, in which case all suboptimal arm pulls increase the counter (k) by 1. Adding the other cost in Type-II decisions (at most K 2a² by Lemma 2 and 2=2=1 for each arm), the total pulling times of o
an suboptimal arm k among all M agents are upper bounded by Eie(M] Nk((k) M 2
Recall that Te (A) denotes the last time slot (before time slot 1) when agent broadcasts arm k's buffered observations' average reward. To bound the first term in RHS, we have
(a)
E (R) (k) (b) 8. RE[M]
Σ N.Kk
&
A
ME(M]
where inequality (a) is because the counter N.(k) is at most B times greater than its value at the last
broadcast time slot, and inequality (b) is because ΣiE(M) (x) (k) is total global observations of arm k at time slot which is less than SA 2 log by Lemma
At last, we sum up the regret cost of pulling suboptimal arms in Type-l decisions and the other cost 20
by Lemma 2 given > 1). So, the group regret is in Type-II decisions (in total at most M K a²-I upper bounded as follows
8, T + MK
20 -
E R
(AA)
a 2
#>1
Notice that executing Algorithm I, agents have the same arm pull behavior. So, the group regret are evenly divided into each agent's 's individual regret and thus the individual regret is upper bound upper bounded as follows,
8, T
2a -
(A))
Rini ind
+ MK
A
a 2-1
#>1
B.4 PROOFS OF COMMUNICATION COSTS (THEOREM 2)
Proof of Theorem 2(1). No occurrence of communication for a < 5-22 is because that the pulled
arm A, never inside the communication set (ai) in (3). When a < -2,, an arm's ELCB is greater than its original UCB index, that is, LLCB, a) = (k) (k. a) > (k) + (k) = UCB, (A)); and its EUCB is smaller than its UCB index, that is, tKC a) (k) + /2 log t/ (k) (k). Then, for the pulled arm A,, the inverse of the communication set's condition holds:
+I,
LLCB,(A,, a) > (CB)
(a)
(k), Vk: + A > (UC a), Vk + A,,
where the inequality (a) is because that the pulled arm A, has the highest UCB index in time slot
17

---

Published as a conference paper at ICLR 2023
Proof of Theorem 2(ii). If reward observation of optimal arm is broadcast by agent at time slot t, then there exists at least one suboptimal arm lt such that the following two events hold at the same time:
(1) > (K) LLCB,(1,a) < (k,
where the first event is from the UCB arm selection policy, and the second event holds because the pulled arm belongs the communication set. These two events imply:
(1( + (2logt/f..1)) > (k) + 22g (k)
(1( CI, CI
(M(1) - (((k)) > /2log (1) v 2lggt/i (k) (1) - (e(k) <a (Vlog l/(4(1] + Vlog 1eggt/nl1 f4 (k)
(V2+ a)) a log (1)+(1) > (v2 alg t/k,((.
After rearranging the inequality, show that the number of observations of the optimal arm is upper bounded by a factor multiplying the number of observations of a suboptimal arm as follows,
12+a 2
(1) < V2
(k.))..
(10)
Lemmas 2 and 3 together show that in the UCB-TCOM algorithm the maximum pulling times of any suboptimal arm k is upper bounded as follows
8 log T
2a -
(k)
K
(1I)
A
a²
Substituting the above inequality to (10)'s RHS and choosing k -2 (because 1/2ß is maximal when k 2) for any time we have
V2 + a
) 22 a
188/lg /8log T
20 - + K
-22--111
(1) <
A
a² -1
Notice that whenever the optimal arm is pulled and lies inside the communication set, the counter (1) increases by 1. So, the buffering counter (1( is no greater than (1). That is,
2 + 22 -
( (8log T
2a K
-1
N(1) &
A
a²
These N2 observations are aggregated and communicated at one time in each phase. These phases' lengths increases in geometric sequence with common ratio B. So, the number of communicated messages of the optimal arm most
2
(Ng)(N.(11) & log, ((22ta)
(8log? T
20²
(e=1)
K a
=O(log(log T)).
A
Proof of Theorem 2(iii). We first show, suboptimal arm is pulled by a Type-I decision, its reward observation will definitely be broadcast, i.e., the pulled arm is inside the communication set. Because the pulled suboptimal arm k's tunable lower confidence bound LCBB(k, a:) is less than the optimal arm 1's tunable upper confidence bound LUCB(1, a): LLCB(K, a) & Pa Ai < tUCB(1, a).
Lemma shows that when a > 1, agents make Type-I decisions in almost time slots (except finite Type-II decisions). Therefore, almost all observations of suboptimal arms are broadcast.
18

---

Published as a conference paper at ICLR 2023
Proof of Theorem 2(iv). We first show that when the optimal arm is pulled and the agent makes a Type-I decision in time slot t, the event that (LC > ELCB,(k, a), Ak * happens with small probability.
P <(t > >LLB)((k,)) vk # 1/4, =) (A(()) ( cI, cI,(ka) Ak 1/A, 1)
< (P((()) >
cI,(k)a) Ak 1|A
min (Ā(1) > al)
min P (A(1)) - m(1) > cI,(k, - ((1))
k=1
(12)
min PP (i(1) (d(1)-(()) ((1) > A:
2 m(11)
min exp (-(asx/2 (2((1))(((1)
k#1
(-(aA2/2 (1)
exp
where inequality (a) holds because (8) in Lemma 3's proof shows that when agent makes Type-I decision to pull suboptimal arm k, the confidence interval CI's width of this arm's reward mean no less than half of the arm's reward gap. i.e., v
2log (A))
A and inequality (b) holds because
2
aAr 2122(1) > O and Hoeffding's s inequality.
Next, show that the number of times that the optimal arm I's observations is not broadcast is finite.
E
Σ
1{A,
and the obs. is not broadcast}
LE|T
<
E
(agent i makes a Type-Il decision in time #}
(E(T]
+ E
Σ [E(T]
1(A = 1 and the obs. is not broadcast and Type-I decision is made in time f
E
Σ
is Type-IIl
+E
I(tICB((1,a) tUCB,(k, a), Vk + 1/A. 1}
FE(T]
(E(T]
IE
Σ AE|T
is Type-I1}
+ E
(LtLCB((L,a) (LCCC(( Ak # 1/A 1}
1E|2]
(0)
E
Σ
fst Type-Il)
exp
FE|T]
tE[T
(b)
2a
MK
exp
(-(ad2/2 -2 dn
a² -1
n=
2a²
2
MK a -
a 2v22(1))
where the inequality (a) is from applying (12) to the second term, and the inequality (b) bounds the number of times of Type-Il decisions by Lemma 2.
19

---

Published as a conference paper at ICLR 2023
C APPLY PEELING TECHNIQUE TO RELAX THE TUNABLE PARAMETER'S CONSTRAINT
In this section, we apply peeling technique (Bubeck, 2010, $2.2) to relax Lemma 2 (thus Theorems and 2(ii)))ss 1 constraint
-2' This finer result helps move the critical point in Figure 2's a-axis to V and extend the red arrow range (with near-optimal group regret and Ollog(log 2 communications) to v2)
Lemma 4 (Bound the number of times of Type-Il decisions via peeling technique). Lemma 2's condition a > can be relaxed to a > / 1 via peeling technique for ?y E (0, 1). The total number of Type-Il decisions no greater than
24
22 +1
2M
+
2029 -1
log(1 (gg(1/7)(2a2)
1)2
Proof. The key idea is applying peeling argument to enhance Lemma I's proof. Denote Y E (0, 1). t For any s & t, there exists j 10.1..... log(1/>)
}} such that 7 < 8 & g Then, we have
logt (k)
(m(k)) > EUCBi(K, a)) P ((k) - -e(kk) 3 1
logt t
P
3s < t: ((k) - -b(k) > 11 (k)
ne(k)) =
Ing(
log
P
38 (7 x-11)/111 (((k) - -Ae(k) 2 a1.
ne(k) =
(k)
1=0
log t
P
3s E (7't, )--18| ((()) (k) > 11
(o(k) =
1=
logt (ng(t/))
a² log!
7.8
exp
2 (1/470+10)
1 179(
exp (~2a227008))
==
log t
)
t 2002
2
log log(1/7) (1/>)
where the inequality (a) is from the maximal Hoeffding's inequality. Symmetrically, also have
logt IP (u(k) & (L)) < 2 log(1/7 (g(17))
t 20
Together, we have
TP (px @ (tICB,(k,o) (UC <
logt log(1/7)
x2a27
20

---

Published as a conference paper at ICLR 2023
[Cr(A)):
0
(log T))
Olog T
(via Theorem 2(1))
(via Theorem 2(ii) and 2(iii)
(via Theorem 2(iv))
-22
v2
2 2/22p 1) 2
E (TA)):
((TT)
O log T)
(via Theorem 1)
Figure 2: Impact parameter a on UCB-TCOM's communication time (Cr(A) and group regret E[RT(A), When a E (1, 22), UCB-TCOM achieves the near-optimal group and individual regret upper bounds with (log T)) communications.
Substituting Lemma 2's proof's third step with the above tighter inequality, we have
P (px & (tLCB(().Q,,
T
< MK)
P (Mt & tUC,,
1=1
log t
< 2MK
Σ
2 +
t 2-20
log(1/7)
1=1
logt
< 2MK
1
2 log(1/7)
t. 2
t=1
22a2x +1 2a -1
< 2MK
log(1 (0g() 1)
where the last inequality requires the exist of integral, i.e., 2a > 1, from which one has a >
and it becomes V when 7 7-1
D TUNABILITY OF TCOM
D.1 ALGORITHM DESIGN DISCUSSION
The parameter tunes the aggressiveness of identifying arm suboptimal. When the condition is aggressive (a is small), the communication arm set ( is small: most arms inside c.a) (a) are suboptimal with high probability, but there may exist some suboptimal arms outside c. (a), i.c., cia) (a) fails cover a subset of suboptimal arms. Therefore, the observations of those suboptimal arms outside the communication arm set cannot be shared, which causes more explorations on them. That is, the cooperative algorithm's 's regret may be large when a communication arm set with small a.
When the condition is conservative (a is large), c( (a) tends to be large: it contains not only most suboptimal arms but sometimes the optimal arm as well. As the observation times of optimal arm are also broadcast, the communication times would be large when is large.
The parameter controls the frequency of communicating an arm's observation. When large, communication times reduce at the expense of longer delays before other agents receive the observa- tions. Therefore, the group regret increases. And vice versa when decreases.
D.2 THEORETICAL DISCUSSION
Impact of communication parameter a. (1) Theorem 2(i) shows that when a & -V2, there is no communication among agents and thus there are no global observations for agents to optimize
their decisions. (2) Theorems 2(iii) and 2(iv) shows that when 2v2n(1) V2) almost all
42
21

---

Published as a conference paper at ICLR 2023
0.18
x110>
1.5
Communicane @Round 30k
Individual Regret @Round 30K
>x10a
x10a
Group Regret @Round 30K
Group Regret
Group Regret @Round 30K
Group Regret Iudividual Regret
Individual Regret @Round
Individual Regret
1.4
1.4
0.16
Comuonuicatio
Comutmiettiio
12
0.14
0.25
Communication
0.8
0.2
0.6
0.12
0.9
0.15
E0.4
0.1
0.7
0.1
0.2
1.1
3
9
(a) Varying (given 8 2)
(b) Varying (given 1.2)
Figure 3: Impact of communication set parameter a with fixed [ = in Figures 3a; and buffering ratio 3 with fixed 1.2 in Figures 3b
reward observations are broadcast. Hence the number of global observations that were broadcast is similar to that of total observations of agents. (3) Theorem 2(ii) shows that when -v2 < a < V2, the number of broadcasts of the optimal arm's observations
Ollog(log) T)). Additionally, the observation buffering mechanism also aggregates the suboptimal arms Ollog observations into O(log(log T)) broadcasts. So, in this case, UCB-TCOM only incurs (log (log T)) communication time. (4) Combined with (3), Theorem shows that when < < v2, UCB-TCOM has near-optimal group and individual regret upper bounds with only (log(log T') communication cost. We refer to the interval (1, v2) as the preferable range for a. Figure summarizes the impact of parameter on the regret-commuuication trade-off.
Impact of observation buffering ratio 3. In addition to at the 3 can also be used to tune the regret-communication trade-off. When the 3 increases, Theorems 1 shows that both group and individual regrets increase. At the same time, note that 3 is the logarithm base in (6) of Theorem 2(i)), which means the communication times of TCOM decreases as B increases. Similarly, the regrets decrease and communication times increases as the ratio 8 decreases.
D.3 SIMULATIONS ON TUNABILITY
Figure 3 illustrates the impact of communication set parameter a and observation buffering ratio on the performance of UCB-TCOM. From regret aspect, Figure 3a shows that both the group and individual regrets do not change much as a increases, which confirms the regret upper bounds in Theorem where does not appear the dominating logarithmic term of (4) and (5). Figure 3b shows that the regrets increase with respect to 3, which corresponds to the appearance of /3 in the dominating logarithmic term of regret bounds in Theorem From communication aspect, Figure 3a and Figure 3b also corroborate (6) of Theorem 2, where the communication times increases with respect and decreases with respect to 8.
E SIMULATIONS ON THE PERFORMANCE OF UCB-TCOM IN DIFFERENT ENVIRONMENTS
In Figures 4a and 4b, we vary the number of agents M in {5, 25, 45, 65, 85, 105} and the number of arms K {10, 20, 40, 60, 80, 100) respectively while fixing other default values. The group regret in Figure 4a is flat (compared to Figure 4b's group regret), corroborating that it does not increase rapidly with respect to number of agents M (discussed in Section 4.2(b), also note that the second term in (4) does not depend on T). Its decreasing individual regret curve corroborates the scalability advantage of the multi-agent system - the more agents in the system, the smaller the maximum individual cost these agents need pay (discussed in Section 4. 4.2(c)). Figure 4b shows that both
22

---

Published as a conference paper at ICLR 2023
Algorithm 2 The TS USBUCB Algorithm (for each agent)
1: Input: the communication arm set parameter and buffering ratio B
2: Initialization: (k( = 0, (k) O, (k) = (k) =
3: for each decision round t do
4: For each arm E XC, sample 0, (A) from the (e)a( + (b) + 1) distribution.
5: Pull arm A, with the highest 0, (k)
6: Observe arm A, reward (A,)
7: if Ar E (a) then
Increase (A,) by 9: Update this phase's empirical mean (Aa)
8:
10:
end if
if (e,)). > (AN) then
12:
Broadcast the message (A,, (c2))), At)
13:
Tr(A)) +
end if
15:
end for
for each newly received message (pe(k), (k).)). from the past decision round do
17: Update the empirical mean Pr (A) < (k) (())
18:
Increase n (k) by (k) 1/
19: Update the communication arm set C, (a) via (3) based on tunable confidence bounds
end for
group and individual regrets, and communication cost increase linearly the number of arms K increases, which signifies the linear dependence of regret on the number of arms.
65
15
Communications @iooudd 30k
Individual Regret Round 30k 2 0 & %
0,7
@Rondd 30K
Group Regret @Round 30K
Geoup Regret
Group Regret @oundd 30k
Individual Regrat @Round
Indiiiiuuall Regret
10
20
Communication
&
- Croup Regret Ledividuua Regget
Communication
25
45
65
85
105
10
20
40
60
80
100
Number Agenss
Number of Arts Agentt
(a) Different agents M (K = 20)
(b) Different # arms K (M 25)
Figure 4: The performance of UCB-TCOM with different number of agents and arms
F APPLY TCOM TO OTHER BANDITS ALGORITTMS
In this section, illustrate how TCOM can be applied other bandits algorithms. Specifically, devise the TS-TCOM algorithm based on the Thompson sampling (TS) algorithm (Agrawal & Goyal, 2012) and the AAE-TCOM algorithm based the active arm elimination (AAE) algorithm (Even-Dar et al., 2006).
For the ease of presenting TS-TCOM, restrict reward distributions to Bernoulli (same simulation setting) and assume the prior of all arms' rewards are Beta(1, Then, at time t, the arm k's reward posterior distribution Beta für (z)) + 1, ne(k) 1), where the (k) and ju (k( are the global pulling times and the global reward mean estimate of arm & respectively. We present TS-TCOM in Algorithm 2. The only difference between TS-TCOM and UCB-TCOM is Line 4-5.
In AAE- -TOMM agents need to construct global candidate arm set D, which is defined as follows,
D, {k E [K] (C) 2 ICB((()), VK [K]),
(13)
23

---

Published as a conference paper at ICLR 2023
Algorithm 3 The AAE TCOM Algorithm (for each agent)
1: Input: the communication arm set parameter a and buffering ratio B
2: Initialization: (k, = 0, .k)(k) O, (k) = 0, (k)
3: for each decision round t do
4: Update candidate arm set Dd via (13)
5: Pull arm A, with the smallest global observation times ft (k) among arms in D,
6: Observe arm A,'s reward (A))
7: if A, (a) then
8:
Increase (A,) by
9:
Update this phase's empirical mean (Aa)
10:
end if
if (e,)). >
then
12:
Broadcast the message (A,, (ce))), At)
13:
Tr(A)) +
end if
15:
end for
for each newly received message (pe(k), (k).)). from the past decision round do
17: Update the empirical mean Pr (A) < (K) (.)((111/3))
18:
Increase nn (k) by (k) 1/
19: Update the communication arm set C, (a) via (3) based on tunable confidence bounds
end for
-10*
x20
1.4 x102
@
UCB-TCON + AAE-TOIM
0.35
Communitaaiinn tnme
Induddiall Rogres
0.3
Group Regret
0.2
2.8
0.6
UCB-TCON
UCB-TCOM AAE-TCOM
2.4
AAE-TCOM
TO-TOON
TS-TOOM
Time slot
Time sloc
<10"
(a) Group regret
(b) Individual regret
(c) Communications
Figure 5: UCB-TCOM AAE- TS-TCOM
where UCB;(K) = (k) + 2 t/fu(k) is the same as UCB-TCOM, and LCB,(k) = (e( /2 log (k)). We note that since both (k) and ñ (k) are global, all agents' candidate arm set are the same. Then, at each time slot agents pull the arm with smallest observation times among all arms in the candidate difference between MAE-TCOM and BCCB-TCH is also in Line 4-5.
set, i.e., arg min (k). We present AAE-TCOM in Algorithm 3. The
In Figure 5, we report the performance comparison between UCB-TCOM, TS-TCOM, and AAE -COM. The simulations are conducted under the default setting in $5. In Figure 5a and 5b, the algorithm has the worse regret performance than UCB-TCOM, and UCB-TCOM is worse than TCOM. This matches the folklore in bandits that the empirical performance of TS is better than that of UCB, and UC3 better than AAE. Comparing the individual regret in Figure 5b to the group regret in Figure 5a shows that the AAE.TCOM and TS-TCOM algorithms have good individual regret performance. Figure 5c shows that these three algorithms need the similar communication times, which validates the communication efficiency of IS-MCOM and AAE-TCOM
believe that the TS-TCOM and AAE-TCOM algorithms (like UCB-TCOM) also enjoy the Olog(log T)) communication times and near-optimal group and individual regrets. However, this requires new analysis, especially for the Thompson sampling case, because its Bayesian approach very different from the method utilized in UCB and TS-TCOM needs to validate the symmetric learning structure. Studying both new algorithms' theoretical performance is an interesting future work.
24

---

Published as a conference paper at ICLR 2023
G EXTENSION OF TCOM TO CMA2B WITH COMMUNICATION WITH DELAYS AND COMMUNICATION OVER A GRAPH
In this section, extend the basic CMA2B model in $2 to allow deterministic communication delays and also from that the agents can broadcast to any others to the case that agents residing on network can only communicate with their neighbors (i.c., cannot broadcast). In the communication network model, we also allow agents to passing its received messages to other neighbors, i.c., allow cassage-passingg We show that UCB-TCOM (with minor changes) still enjoys the near-optimal group and individual regret upper bounds as in Theorem I with only constant additional cost (independent of T). We also note that the communication times results in Theorem still hold because its proofs are not influenced by these extensions.
G.1 DETERMINISTIC DELAY
Denote E N as the deterministic delay of agents' message broadcasts. The deterministic delay can also be relaxed random delay but with the d as the delay upper bound. Algorithmically, the global UCB utilized for selecting arms to pull should be re-defined to those observations that have been broadcast d time slots before. Because only these reward observations have been received by all agents even with the communication delay and thus agents utilize the same observations to make decisions.
Theorem 3. When the communication set parameter
and buffering-rate tratiin 3 > given all delays of communication is no greater than d, UCB-TCOM attains near-optimal group regret upper bound in terms of number of decision rounds T, arms K, and agents M, or formally.
8BlogT + MK
20² a²
+ dM
A
A
k>1
and UCB-TCOM also attains near-optimal individual regret upper bound, or formally,
83 T
2aa 1
E|R ind (A))
K a + d Σ A
MD
K>1
Proof of Theorem 3. The proof procedure of Theorem 1 still applies to Theorem 3. The only change is that the inequality (9) should be updated as follows,
(0) Σ
8.log (b) N.,0, + dM <
Σ N() RE[M]
(BN 71 (k) + &B Σ RE(M]
+ dM,
A
XE[M]
where inequality (a) is because the counter N2(K) is at most 3 times greater than its value at the last broadcast time slot plus the delay d, and inequality (b) is because LiE[M] (N.(()(k) is total global
observations of arm at time slot t which is less than 8 log T by Lemma 3.
With the rest proof the same Theorem I's, UCB-TCOM's group regret is upper bounded follows:
88 T dd Σ A + MK
2x² -
E|R((A)
A
a
As the symmetry of UCB-TCOM still holds, the individual regret upper bound immediately follows,
8,3 log T
20² 2 -1
EjRind (A)]
d
Σ
A
K
MAr
k>1
G.2 COMMUNICATION TOPOLOGY: PEER-TO-PEER AND MESSAGE PASSING COMMUNICATION
We assume the communication network is a connected graph, i.e., there exists a path between any two nodes, and the diameter of the graph is D. In the message-passing protocol (following Dubey
25

---

Published as a conference paper at ICLR 2023
al. (2020)'s model), agents i [M] communication via messages (i, ()()) (A)), Aj). This message is sent to its neighbors in the graph and then is forwarded to by any agents when receives to their neighbors until the time slot + D. Under this protocol, the broadcast message will final reach to any agents with a delay at most D. In algorithmic aspect, the TCOM algorithm still works with minor modifications:
1. Change the Line 11 in Algorithm from broadcast to communication to neighbors;
2. Add a line after Line 11 that an agent should also send all its received messages with time index t' t D to neighbors on the graph:
3. Line 15 should be changed to receive all messages that have not been received before (i.e., with unique i, & prefix in the message).
With the above modifications in UCB-TCOM, the algorithm solves a problem equivalent a CMA2B with communication delay D complete graph. Therefore, based on Theorem 3, one obtains the following corollary to bound the group and individual regrets of the modified UCB-TCOM algorithm.
Corollary 4. When the communication arm set parameter all agents residing on network with diameter D, UCB-TCOM attains near-optimal group regret upper bound in terms of number of decision rounds T, arms K, and agents M, or formally,
and buffering-ratt 3 > 1, given
To
2a 2
([R](A))
MK a
DM Σ A
A
k>1
and UCB-TCOM also attains a near-optimal individual regret upper bound, or formally,
8ol
2a²
E E
(A)
D Σ D
M
a 1
k>1
26


Reviews:
[{"review_id": "lspjeZMsJn", "reviewer": "Reviewer_coEu", "summary": "", "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": "", "summary_of_the_paper": "This work focuses on a cooperating learning version of the classical multi-armed bandit problem, where M agents play the same problem instance over T rounds. Agents can communicate their observations through global broadcasts. The authors propose an algorithm that needs O(log log T) communication rounds to achieve logarithmic individual as well as group regret.", "summary_of_the_review": "The paper is generally well written and a pleasure to read. Appears to be technically sound, comprehensive in literature survey, and meaningful in contribution as it improves upon extant baselines by a considerable margin. It would be great if the authors could address or at least remark upon the questions raised earlier; that would really cement the contributions well and make it accessible for a more general audience. Overall, I vote for an acceptance.", "strength_and_weaknesses": "The main contribution appears to be showing that a factor of M improvement in group as well as individual regret is possible using only O(log log T) rounds of (broadcast) communications between the M agents. The improvement is relative to the scenario where the agents do not communicate and simply keep playing their own instance, oblivious to the rewards accrued by others. The communication efficiency of O(log log T) is achieved by sharing information about (empirically) sub-optimal arms as opposed to optimal ones, which I find to be a very neat idea.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "YxbhDr2av9", "reviewer": "Reviewer_VQR1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "summary_of_the_paper": "This paper study the collaborative MAB, where agents can communicate together to handle the same MAB problem. The authors propose a new notion of regret: the individual regret is the maximum regret over the players. This notion of regret is given in addition to the usual notion of regret. This regret could be related to the notion of fairness, since the closer the individual regret to regret the greater the fairness is. \nIn collaborative MAB the goal is to minimize the regret but also the communication cost. They provide a communication policy that has a communication cost in O(log log T) and that benefits from a near-optimal regret bound for both notions of regret. In some experiments, they show that their algorithm (UCB-TCOM) provides a good compromise between group regret and individual regret, while they obtain a low communication cost, even if it is not the smallest. \n", "summary_of_the_review": "Overall, despite some shortcomings that can be fixed, this paper is technically sound, well written, and presents some novelties.\n_____________________________\nI read the rebuttal and I thank the authors for their answers.", "strength_and_weaknesses": "The proposed communication policy is sound. The analysis and the experiments are well done. \nHowever, the paper presents some shortcomings. \n\n1/The definition of both regrets seems incorrect. Indeed, there is an expectation in the regret, while there is no random variable inside: \\mu(A^i_t) is the mean reward of arm chosen by agent i at time t. Did the authors take the expectation over the choices of players? Why not using the usual definition of pseudo-regret (cumulative difference between the expected reward of the optimal arm and the expected reward of the chosen arm)?\n\n2/ In comparison to DEP2, UCB-TCOM is outperformed in two metrics (group regret and communication time). So the only advantage of UCB-TCOM is that its individual regret is smaller. So in the comparison, individual regret is crucial, and it has to be better motivated. May be by enhancing fairness ?\n\nMinor comments:\nTable 1 presents an error: the communication time is in O(1) for DEP2.\nThe authors could refer some works done in the collaborative exploration setting. Indeed, explore then commit algorithm can also reach a near-optimal regret (Garivier et al 2016), and despite different contexts, the two following papers use similar ideas: doubling trick for communication policy in (Hillel et al 2016), communicating only about bad arms in (Feraud et al 2019).\n\n(Hillel et al 2013) Distributed exploration in multi-armed bandits, NeurIPS 2016. \n\n(Feraud et al 2019) Decentralized exploration in multi-armed bandits, ICML 2019.\n\n(Garivier et al 2016), On explore the commit strategies, NeurIPS 2016.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QOcMsBw0k64", "reviewer": "Reviewer_3zzv", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "", "summary_of_the_paper": "This paper studies distributed multi-armed bandits with the goal of minimizing the largest regret incured among all the agents. This work makes two contributions: First, it suggests a different objective—minimizing individual regret rather than group regret—motivated by real-world applications. Second, it proposes a new algorithm—UCB-TCOM—with almost optimal bound for both individual and group regret. In addition, the new approach only incurs communication cost of $O(\\log \\log T)$ times.", "summary_of_the_review": "This paper is well-motivated by real-world applications. The author(s) have proposed a new algorithm with nearly-optimal individual and group regret. Besides, it incurs only $O(\\log \\log T)$ communication times. However, the techniques used are not brand-new. I struggle to understand how challenging it is to establish the theory in the paper.", "strength_and_weaknesses": "Strength\n* The new objective is strongly supported by practical applications. \n* Numerical simulations with real-world data are offered to verify the proposed algorithm\n* The paper is written well.\n\nWeaknesses\n* It seems to me the key technique to lower the communication complexity from $O(\\log T)$ to $O(\\log \\log T)$ is the doubling technique or observation-buffering broadcast mentioned in the paper, which is a well-known technique in bandit literature. It would be preferable if the author(s) could explain in the study why establishing the intended outcomes was challenging.\n--------------------\n\nAfter rebuttal\n\nThe author(s) have added discussions regarding the challenge raised during the proof of the communication complexity. And I have raised my score.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster