Cooperative Stochastic Bandits with Asynchronous Agents and Constrained Feedback
Authors: Lin Yang
Yu-Zhen Janice Chen
Stephen Pasteris
Mohammad Hajiesmaili
John Lui
Don Towsley
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bandits
Regret
Multi-agent learning

Abstract: This paper studies a cooperative multi-armed bandit problem with $M$ agents cooperating together to solve the same instance of a $K$-armed stochastic bandit problem with the goal of maximizing the cumulative reward of agents. The agents are heterogeneous in (i) their limited access to a local subset of arms; and (ii) their decision-making rounds, i.e., agents are asynchronous with different decision-making gaps. 
The goal is to find the global optimal arm and agents are able to pull any arm, however, they observe the reward only when the selected arm is local.
The challenge is a tradeoff for agents between pulling a local arm with the possibility of observing the feedback, or relying on the observations of other agents that might occur at different rates. Naive extensions of traditional algorithms lead to an arbitrarily poor regret as a function of aggregate action frequency of any $\textit{suboptimal}$ arm located in slow agents. We resolve this issue by proposing a novel two-stage learning algorithm, called $\texttt{CO-LCB}$ algorithm, whose regret is a function of aggregate action frequency of agents containing the $\textit{optimal}$ arm. We also show that the regret of $\texttt{CO-LCB}$ matches the regret lower bound up to a small factor.

Cooperative Stochastic Bandits with Asynchronous Agents and Constrained Feedback
Lin Yang, Yu-Zhen Janice Chen University of Massachusetts Amherst [linyang, www.yuchhhhneeeeeeccc umass. edu
Stephen Pasteris University College London stephen. stephen.pasteris@ge.e... pasteris@gmail com
Mohammad H. Hajiesmaili University of Massachusetts Amherst hajiesmail iiccs. umass. edu
John C. S. Lui Chinese University of Hong Kong cslui@cse. cuhk. edu.ht hk
Don Towsley
University of Massachusetts Amherst towsleyθcs umass.ed.
Abstract
Motivated by the scenario of large-scale learning in distributed systems, this paper studies scenario where M agents cooperate together to solve the same instance of a K -rrdedd stochastic bandit problem. The agents have limited access to a local subset of arms and are asynchronous with different gaps between decision-male -akinng rounds. The goal is to find the global optimal arm, and agents are able to pull any arm; however, they can only observe the reward when the selected arm local. The challenge is a tradeoff for agents between pulling local arm with observable feedback or pulling external arms without feedback and relying on others' observations that occur at different rates, We propose AAE-LCB, a two-stage algorithm that prioritizes pulling local arms following an active arm elimination policy and switches to other arms only if all local arms are dominated by some external arms. We analyze the regret of AAE-LCB and show it matches regret lower bound up to small factor.
1 Introduction
Multi-armed bandits (MABs) [16] 50 is remarkably successful online learning framework that has been extensively studied since the 1950s (47] It has broad range of applications including
datacenter optimization, web advertising, and recommender systems (50) 31 33 15). the basic MAB problem, learner repeatedly chooses action (pulls arm) in each round, and collects (and observes) the reward associated with the selected arm, but not rewards associated with the unselected arms. The goal of the learner to maximize the long-term reward collected, and the performance metric is regret, which is the difference between the expected reward for the best arm and that received by the learner.
The distributed/multi- paanmuuliiaggntmmuullllaaaal MAB problem is an extension of the basic MAB that has
been studied extensively in different settings [43 [1 II|
36 33
25
45
53
48 This problem is
motivated by several applications such as (1) large-scale learning systems
19 in domains such
finance recommendation systems; (2) cooperative search by multiple robots 41 32]; (3) the
application wireless cognitive radio 17 43 9 and (4) distributed learning in distributed
systems (e.g., set of loT devices learning about underlying environment) 46 23
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Most prior work on the aulti-agent MAB problem assumes that agents have full access to all arms, and hence they solve the same MAB problem with the goal of minimizing the aggregate regret of the agents either in a competition setting 3 17 53
13
43
42 9 where agents
receive degraded or no rewards when pulling the same arm, or in a collaboraaion/coneeratii
36 48 44 where agents receive independent rewards when they pull the same arm, and agents can communicate to improve their learning performance. In this work, we focus on the cooperative version of this problem, which has been extensively studied in recent years under different settings. In a thread of work, the agents are considered to be connected together over 10 24). Among them, [53] presents more practical model in which agents are limited in their available communication capacity with others, and also develops algorithm which achieves an asymptotically optimal regret. The above basic models have been extended to several other settings such as pure-exploration through cooperation among agents for identifying the best stochastic arm (29) cooperative multi-agent bandits with heavy
setting [45 53 38
37
communication graph 45 the
153 38 37
tails (25). cooperative kernelised contextual bandits [27] linear bandits with safety constraints (2),
and the case with both honest and malicious agents [52] In [0], the problem is extended to the
case where the underlying topology is time-varying. In another trend, the cooperative bandits have been studied over social networks [48 51 36). Last, in very recent trend, the stochastic bandits
have extended to the federated setting, in which the learning task is distributed among multiple
agents [56 49 26
In this paper, we study a heterogeneous version of the cooperative aulti-agent stochastic bandit problem with set A = (I....,,M,, of agents and set IC = (1...., K} of arms. Agent j E AA has access to a subset K.j S KC of arms. We refer to arms in K.j as local and the remaining arms in AC K. as external arms. Agents come with different learning capabilities and can pull an arm every 1 1/0, rounds, with 0 < < S. 1 as the action rate of agent j. The goal is to collaboratively find the optimal arm in K. An agent can pull any arm and receives a reward: however, it observes the reward only when it pulls a local arm. It instantaneously forwards this observation to all other agents. We call this setup Feedback-comstrraneet Cooperative Multi-agent MAB (FC-CMA2B) and formally define it in Section 2
The FC- FC-CMABB setting arises naturally in large-scale learning systems that are often geographically distributed for domains such as web search, finance, and recommendation systems. In such large- scale systems, it is usually impossible to run single bandit algorithm. Instead, a distributed set of agents work to solve the problem, each with access to a subset of the action space. However, the entire learning task is integrated and the goal is to find the best global action, e.g., the most relevant search result in a web search application, or the best possible video recommendation in the YouTube recommendation system among millions of possible recommendations. In the above scenario, learning among different agents may be asynchronous in the sense that each agent has its own action (decision making) rate, which is captured by FC-CMA2B. In Appendix A we provide a few concrete application scenarios that could be captured by FC-CMA2B.
The algorithmic challenge in FC-CMA2B originates from nontrivial tradcoff that agent must make between pulling a local arm with an observable reward, and pulling an external arm with the expectation of a larger but not observable reward. One might simply run cooperative UCB algorithm on each agent without any distinction between local and external arms and pull the arm with the highest confidence interval. Then, if the selected arm is local, the agent can broadcast its observation to others. However, this strategy suffers a poor regret. The reason is intuitive. Consider a case where suboptimal arm is only observable by slow agent, i.e., an agent with a very small action rate 0,. In such a case, the upper confidence bound of the suboptimal arm will remain large due to the limited observations available only to the slow agent. Since the indexing policy of cooperative UCB suggests pulling the arm with the highest upper confidence bound, then, the suboptimal arm will be continuously pulled by everyone, resulting in a poor regret.
We note that (55) also considers a cooperative bandit setting with heterogeneous agents with a subset of arms and different action rates. However, in [55], the goal of each agent is to find the local optimal arm, while in this work, the goal of each agent is to find the global optimal arm. This difference leads to substantially different challenges in the algorithm design and analysis. More specifically, in our work, a foundational challenge is to find an effective cooperative strategy to resolve a dilemma between pulling local vs. external arms. This is not the case in (55) since the goal is find the best local action.
2

---

Contributions. This paper makes the following contributions.
Algorithm design using a two-stage learning strategy. To tackle the new dilemma in FC-CMA2B for pulling either local or external arms, a proper bandit algorithm should be able to collect sufficient reward information, which is possible only by pulling local arms. To achieve this, our high-level idea is to distinguish between local and external arms and prioritize the local arms and only switch to external arms when they are clearly better. We implement this idea by proposing AAE-LCB, two-stage learning strategy, which in the first stage selects local arms based on a carefully-designed active arm elimination (AAE) policy, and in the second stage selects external arms based on lower confidence bound (LCB) policy.
More specifically, in the first stage of AAE-LCB, each agent pulls only from dynamically-construce candidate set of local arms. Then through an AAE process, a local arm is removed from the candidate set when its confidence interval falls below that of at least one other (local or external) arm. With this strategy, AAE-LCB makes a sufficient number of observations of local arms, and resolves issues encountered by the cooperative UCB. For an agent whose local arms do not include the optimal arm, the elimination process continues until all local arms are eliminated, and when so, the algorithm enters a second stage, where the agent only pulls external arms.
In the second stage, the agent totally relies on external observations that may occur at different rates. Differences in observation rates complicates decision making regarding choice of external arm such that the agent has to balance between well observed arms, and those that are not well observed but likely to be optimal. To tackle this tradeoff, AAE-LCB pulls external arm with the largest LCB, and to the intuition is that an arm with greater LCB is both better observed and more likely to be optimal. Note that selecting based on largest UCB may lead to pulling external arms whose upper confidence bounds are large due to a lack of samples.
Regret lower and upper bounds. We analyze the regret of AAE-LCB and show that it achieves regret of O(E.>;>0 م0 0,/0,- x K log T/ /.), where O is the action rate of arm i defined as the sum the action rates of agents containing arm i and i* is the optimal arm. We further establish regret lower bound for FC- CCCBM and shows AAE-LCB is regret optimal up to a small factor. For comparison, we investigate the regret of baseline algorithm, AAE- AAE, which pulls external arms based another AAE process and show that it exhibits poor performance in the presence of agents with low action rates. Specifically, we show that AAE-AAE suffers regret of 22(O) mmi log T), where + = Eje, A fg and
Quin min ΣJAEK, 02 are the aggregate action rate of all agents, and the minimum aggregate action rate of agents containing any arm i, respectively. This result shows that regret can be arbitrarily bad when Omin. i.e., the minimum observation rate among all arms (either optimal or suboptimal), small. Hence, instead of regret depending on the observation rate of the least observable (and possibly suboptimal) arms, the regret of AAE-LCB depends on that of the optimal arm.
Numerical results. Through brief numerical experiments, we verify our theoretical observations and show that the cooperative extension of UCB and AΑE-AAE are either unable to gain sufficient observations for the global optimal arm or vulnerable to the action rate of slow agents with suboptimal arms, while AAE-LCB is robust to both issues and achieves much better performance.
2 Problem Setup
brobback-constrained Cooperative Multi-agent MAB (FC-CMA2B), We consider multi-agent stochastic bandit setting with a set A (1,...., M) of independent agents existing over the entire time period, and a set K. = {1,.... K} of arms. Associated with arms are mutually independent sequences of i..d. Bernoulli rewards with mean 0 < μ(i)= S 1, for arm E K. Agent j E A has full access to subset K, S KG, K, [K,l. of arms. We refer to Kj and K. \ K. the sets of local and external arms of agent j. respectively. Agents are allowed to pull and receive a reward from any arm from KC, however, they only receive observations from local arms. That is to say, if the selected arm is external, the agent does not observe the reward even though the reward is allocated. Last, we make no assumption regarding overlaps among sets Kg.
In addition to heterogeneity access to arms, agents are also heterogeneous in their decision making capabilities. Specifically, considering the decision rounds (1, ....... T), agent j is able to pull an arm every W/ E N+ rounds, i.e., decision rounds for agent j are = wy, 2wj..... Nywu, where N₂ = [T // Parameter wy represents the inter-round gap of agent j. For simplicity of analysis,
3

---

we define 8, := 1/w, as the action rate of agent j. Intuitively, the larger f,, the faster the agent is pulling arms.
The goal of each agent to learn the global optimal arm. The regret for agent j in FC-CMA2B
where i* is the optimal arm in K. and 132 E K. is the pulled arm by agent j at time Agent j receives the reward xy xT())) whose value is observable only if I E Ky. The ultimate goal is to minimize the aggregate regret of the agents, i.c., My = EEEARt R4
note that when two agents select the same arm, they collect stochastically independent rewards, and there is reward degradation such occurs in competition settings. We also consider full and truthful cooperation among agents, i..,, after committing to one decision and receiving a reward from the pulled arm, agent broadcasts observations to others at no cost and no delay. In the supplementary material, we further consider a more general model with communication delays among agents.
Additional notations and terminologies. introduce the following notations. Let A, denote the set of agents whose local arm sets include arm i,
To facilitate our algorithm design and analysis, we
A Lj E Ki)
E.
By A(', i), we denote the difference in mean rewards of arms i' and i.e., (i', == m((i) pu(t). When i' = i", we rewrite A(i", ,i) as A., which is known as the suboptimality gap in the basic bandit problem. Last, we define and θ, i K. as follows
θ
Σe, 0z. and O D,=-00m jEA
jEA:
where O; is the action rate of arm across all agents in A;- Intuitively, the larger O is, the higher the rate at which arm can be pulled by agents in A, The action rate O plays a key role in characterizing the regret bounds.
3 Algorithm Design
Each agent in the FC-CMA2B setting has to resolve a tradeoff between two categories of arms: (i) local arms with observable rewards, and (ii) external arms whose rewards are not observable but may be better than local arms. This heterogeneity in information feedback motivates our two-stage learning algorithm, ACE-LCB. In the first stage, agents running AAE-LCB are focused on sampling local arms to collect sufficient information that is useful for all agents in finding the global optimal arm. And when with high probability, an agent confident that its local set does not contain the optimal arm, moves to the second stage by pulling external arms based on others' observations.
3.1 Stage 1: Selecting a local arm
In order converge the global optimal arm, agents must collect sufficient observations in the first stage. Toward this, our idea is to prioritize pulling local arms as much as possible and only switch to external arms when the agent finds an external arm that is sufficiently better than all its local arms with high confidence. To implement this idea, we extend the active arm elimination (AAE) capture the additional issues in FC-CMA2B. Similar to the basic AAE algorithm, in our a algorithms, we start off by constructing a dynamic candidate set of local arms and gradually eliminating arms from it. The elimination process is similar to the basic AAE, which eliminates arm when its confidence interval falls below that of at least one other arm. However, the difference that while the candidate set includes local arms, the criteria for eliminating an arm is based comparison between both local and external arms.
algorithm [28]
Specifically, we define the width of the confidence interval for arm and agent j at time t
a log 8,
cint(i,j.t) =
(1)
2n (i)

---

Algorithm :CB: A Cooperative Bandit Algorithm for Agent j in the FC-CMA2B setting
1: Initialization: (i) 0. fa(). E KC, C = K, a > 2, 6z.
2: for each decision round f do
3:
for each new received z. (1). i E K, <tt,t,, do
4: Execute line
8 10 for arm i
5: end for
6:
if C2 * ( then
D Stage 1: Pulling local arms through an AAE process
7:
Pull arm 1/ with the least no. of observations from Cj3
8:
Increase counter for the selected arm by I: (T.) f- n (Ia) +
9:
Update estimate of the mean value of the selected arm ((e)
10:
Reconstruct candidate set based on updated values of ñ (I.) and p(I)) as in Equation 2
11:
Broadcast It (TF) to other agents
12: else
Stage Pulling external arms through a LCB process
13:
Select an external arm with the largest lower confidence bound as in Equation
14:
end if
15:
end for
where (i) is the total number of observations (either local or received from other agents) of arm available to agent j by time t (observations made in time slots from I to t - 1). Also, 6, > 0 and > 2 are parameters of the confidence interval. The removal of arm from agent j's candidate set time with empirical mean of fu(i, ne (i)) occurs if there another arm i', such that the difference in empirical means of i and i' is larger than the widths of the confidence intervals, i... A(t', fog (t') fu(i, fn (i)) cint(1', j) + cint(i, j, t). This means that with high probability, arm i is not optimal. Note that i' could be either a local or an external arm. More formally, agent constructs the following dynamic candidate set C5, at time during its learning process.
c ()) or pli, (1) - p(t. (()) S cint(i, t) +cint((( j.t), Vi E x]
(2)
Note that in the above construction the local candidate set of agent j includes all local arms not yet observed and all others dominated by any other local external arm. If the local candidate set is not empty, an agent always prioritize selecting local arms and, following basic AAE, pulls local arm in the candidate set with the least number of observations, and then updates the empirical mean values and broadcasts the observation to others as in Lines I of Algorithm[ [ We also note that the size of the dynamic candidate set is not necessarily decreasing and it is possible that after pulling some external arms, some local arms are put back into the local candidate set. Hence, in run time, fluctuations between pulling local and external arms might be possible.
3.2 Stage 2: Selecting external arm
As Stage 1 of the learning process moves forward, it is possible that the local candidate set of an agent will become empty, i.e., external arm eventually dominates all local arms. In this situation, the question becomes how to pick an external arm. The answer to this question critical in designing cooperative algorithms with low regret.
Different action rates among different agents can lead arms to suffer different observation limitations that can invalidate the selection indices commonly used in the bandit algorithms. Specifically, when suboptimal arm is only accessible to slow agents, estimates of the empirical mean reward of this arm will be updated more slowly than those of other arms pulled by faster agents, and thus contain more errors. In this way. those algorithms, which are unaware of confidence of estimates, may be misled into selecting suboptimal arm with low-level confidence in the FC-CMA22 setting. For example, "slow arms", i.e., those arms that are only in the local sets of slow agents, have much looser confidence interval and much larger upper confidence bound than others. As result, fast agents running cooperative version of AAE or UCB-based algorithms that pull external arms based on estimated upper confidence bounds may be misled into continuously selecting a suboptimal "slow" arm because its upper confidence bound is large due to insufficient number of observations. To address this, we propose to follow Lower Confidence Bound (LCB) policy, which selects the external arm with the largest lower confidence bound, i.c.,
P = arg max ((i, (((()) - cint(1.j.) iEK.K,
5

---

An important observation on LCB is that the lower confidence bound of an arm is large only if it is well observed and hence likely to be the optimal arm. Indeed this is not the case if the selection policy is based on the largest upper confidence bound, since external arms with low observation might have large upper confidence bound.
3.3 Baseline Algorithms: CD-UCB and AAE-AAE
To show the advantages of AAE-LCB, we introduce two baseline algorithms. The first one is CO-UCB, cooperative version of UCB that the agents do not distinguish between local and external arms. In other words, each agent running CO-UCB, pulls the arm with the largest upper confidence bound and, if the information observable, broadcasts it to all other agents. Further, each agent will updates its confidence intervals not only based on its local observations, but also, based on the information received from other agents.
The second algorithm is AAE-AAR which has a similar two-stage structure to prioritize pulling local arms as AAE-LCB, but adapts another layer of active arm elimination for pulling external arms. In the second stage, i.e., when the local set is emptied, AAE-AAE randomly pulls an external arm whose confidence interval have overlaps with others' and dynamically reconstructs the external candidate set similar to the process in the first stage, but for external arms. Because external arms with few observations has loose confidence interval, they satisfy the criteria to be in the candidate set, hence, the agents running AAE-AAE may repeatedly pull them.
In Section 5 we numerically compare the performance of both baseline algorithms with AAE-LCB and show the poor performance CO-UCB due to the same treatment for local and external arms, and the improvement of AAE-LCB over AAE due to better treatment of external arms. In addition, in the next section, we theoretically compare the regret of AAE-LCB and AAE-AAE.
Regret Results
Two main regret results are highlighted in the following two theorems. We first introduce some terminology to facilitate the presentation of the results. Consider an algorithm running on agents in FC-CMA2B. We say that is consistent, if its regret satisfies E [R)(T)) ((TT))) as T - +o0 for any a > and for any set of Bernoulli reward distributions. Further, let (L Ps A,) refer to the the Kullback-Leible divergence between a Bernuuli of parameter μu, and μ4 + A.
Theorem (Asymptotic Regret Lower Bound for FC-CMA2B) For any consistent algorithm π and any 0 < a < 1, its expected regret satisfies
[RT(T)
T 0/- (0/0 lo (Tg = 2( Σ
liminf
KL ps + +A))
CA,S0
The proof for the lower bound consists of two steps. In the first one, we prove that under any given agent action rates, any algorithm suffers a regret of ([og(TT)) for large T. This proof uses techniques commonly used to prove lower bounds for stochastic bandits. In the second step, we prove that, with large enough T and O/O,,, no algorithm can have dependency on (0/0,- jo for 0 << a 1. This is proved by contradiction. The details are given in the supplementary material.
Theorem (Expected Regret for AAE-LCB) Define å min., 81/0,- The expected regret of AAE-LCB with parameter o > 2 has the following upper hound
4a log 8-
KO, 0,
120,a logo-
E Rrl <
Σ
max
2
A
N
+
+ 2
1
+r
0j
1/0,
JEA
1=1
iEK,
Corollary With 6, 1/t and
2, have the following regret for the AAE-LCB algorithm.
KO, log
E Rr]
0
Σ
O,
NEK:A,

---

The prove is given in Section 4.1 From Corollary and Theorem I we observe that the asymp- totic regret of the proposed AAE LCB algorithm matches the lower bound up to small factor ((K()/O,-)) ) where is arbitrarily close to 1.
We also compare the regret of AAE-LCB to that of AAE-AAE. With 6 = 1/T, and 4, the regret of AAE-AAE could be characterized as
+ E [RT] = 92 ( ( log (0m_1oTT))
(4)
where Qmin == min; θ; The detailed derivation of the the above regret is in the supplementary materials. The regret of AAE- in (4) strongly depends on m i.e., the smallest aggregate action rate among all arms. Hence, as min goes to zero, the regret of AAE-AAE significantly degrades. The regret of AAE-LCB shown in Corollary [ however, depends only on the action rate of the optimal arm. Hence, AAE-LCB outperforms AAE- AAE, in the sense that its performance is independent of the slowest arm.
4.1
A Proof for Theorem 2
There are two contributions to the regret of AAE-LCB: one due to pulling suboptimal local arms, and the other one due to pulling suboptimal external arms. To prove Theorem [ analyze these two contributions. Note that, observations are generated whenever agents pull local arms. Thus, the first contribution regret can be upper bounded by analyzing the relationship between the confidence interval and the number of observations obtained from each arm. By analyzing the algorithm rules of AAE- AAE, we upper bound the expected number of observations required from suboptimal arms to identify the optimal arm if it lies in the local set, as well as the first contribution to regret. Regarding the second contribution to regret, the main difficulty comes form the heterogeneity of action rates associated with the arms. To upper bound this contribution to regret, we first upper bound the time period needed for the agents containing the optimal arm in their local sets generate enough observations such that the lower confidence bound of the optimal arm is higher than those of any others. With this, we can prove the the final result by upper bounding the number of times that suboptimal external arms need to be selected in the above proved time period.
Now, we proceed to formally prove the regret result. First, we categorize decisions made by the agents into Type-I and Type-II decisions. Type-I corresponds to the decisions of an agent when the actual mean values of local arms lie in the confidence intervals calculated by the agent, otherwise, Type-Il II decision happens, i.e., the actual mean value of some local arm is not within the calculated confidence interval. Specifically, when agent j makes a Type-I decision time t, we have
[p (1) cint(i.j.f), (.) + cint(i,j.t) i E Kj.
pat) E
With Type-I decisions, agent can keep the local optimal arm in its candidate set and eventually converges its decisions to the local optimal arm. The following Lemma, whose proof is given in the supplementary material, provides the probability that a Type-I decision happens at particular decision round.
Lemma Agent j rumning AAE-AAE with makes Type-I decision, in round 1/0g. with 18, 80
probability of at least 1 2 EiEK, 02 1/0,'
In the ACB algorithm, a suboptimal arm pulled by agent j lies either in the candidate set or is the one with the largest lower confidence bound among all arms. Thus, we split the regret analysis into two cases: Case I: local arm selection, where a suboptimal decision is made during the arm elimination period for arms lying the local set; and Case II: external arm selection, where a suboptimal decision is made based on the lower confidence bound when selecting external arms. In the following, we analyze the regret in each case separately.
Case I: regret due to local arm selection: For suboptimal arm i, we upper bound the total number of pulling times by agents in A,, which is actually equal to nif (i). First, we focus on the cases that the algorithm makes a Type-I decision at time i.e., the mean value of any arm lies in its confidence interval calculated by agent j. Then, at time I, if agent j in A, selects arm i, we have
2cint(i, + 2cint(i" (i", ..tt) 2 A.
(5)
7

---

Q. Then, the regret spent the arm i in other agents is Otherwise, we have
+ St4 + (i. < 44 A cint(i"
-cint((" (j.t)
-/-- 2cint(i" j,t) S M(i" (. - ci,nt(i,,,,)
implying that arm is strictly dominated by i", hence, can not selected by agent contradicting the assumption that i is selected by j. It follows from Equation (5) that
A
max ()) 2eintt ,J. [)())
and by the definition of cint(.) in Equation we have
8a log 0,
min [ (1))))))))) <
(6)
A
Now, we focus on Type-II decisions. Let Q denotes the number of Type-II decisions. By Lemmal we have
10
E QQ
01/0,-
JEA 1=l iEN
By combining Equations
6 and 7 we have
min
E
n (i)
E
[n]
8xx Boglog 8-1
[Q]
(8)
Then, have
2 T E
E E[
E
(i))
(9)
K
O
K
where the first inequality is based the fact that the expected number of decision rounds with the optimal arm in the candidate set is at least T E
Q and the second one is based on the fact that
T 2 for (1) Combining the results in Equations
S and (9. we get
88 log 8-1 A?
Sa Ka, logō-1 5-1
Oi O..
E [i) max
1+
E E[Q]-
(10)
A,
Case II: regret due external arm selection: Now, we aim upper bounding the expected number of selection times for a suboptimal arm by the agents outside set A;; Again, we assume that agent j makes a Type-I decision at time slot t. Consider the case that I = and i not within K.j. By algorithm rules, have that arm i has the largest lower confidence bound. We claim that
1/2ccnt(i".j... A
(11)
Otherwise, we have
p(i, (e((() cint(i, sn(i) n(i²) A: <pili" (i()))) + cint(i", .j.t) 2cint(i", j.t) =ū(i", (i()))) cint((",j,t
contradicting the rules of the algorithm. Thus, at time t, the selected arm satisfies
aK log
A s 2/ 10 -Q
The above equation is obtained by replacing nif (i*) in equation 2/2cint(i"... j,t) A, with [/O;- Q)/K K, since (i(())) 2 |/,,- - Q//K.
For any agent j. the largest time slot when the agent makes a Type-I decision and a suboptimal arm i lies in the candidate set is 4 log
A,O,
0,-
upper bounded by 4 a log 8-1
Q8:
0, +Q.
8,

---

Cunuuativve Regret, @Round SDK
=10
Avg Cumu Regret @Round 30K
2x10*
- LAB UCB AE- AAE
-AE-ICB
-AE-LCB
0.25
-0-000
Cumulstive Regret
CD-UCB AAE-AAE
AAE-AAB
0.15
13 0F
0.05
5x
10x
15x
20x
25k
10x
15x
20x
25x
Speed Ratio: Fast vs Slow Agents
Speed Ratio: Fast vs Slow Agents
Round
x10
(a) Cumulative regret
Avg. (over observation) regret
(c) Cumulative regret 05x
X10"
-AA--ICB
6000
-AA--CEE CU-UCH AAE-IAE
500
-AA-ICE
Curuuaaiiv Regret
CC-UCB AAE-AAE
Cumuletive Regres
5000
400
CU-UCE
10 to a. on
LAE-AAE
4000
300
Cumulative
3000
200
2000
0
-100
Round
x10
Round
x10
Round
(d) Cumulative regret @25x
(c) Per-agent regret (fast agent)
(f) Per-agent regret (slow agent)
Figure 1: Regret of AAE-LCB vs. AAE-AAE vs. CD-UCB with two groups of "fast" and "slow" agents and varying action rate ratio between them. Notable observations: AAE-LCB outperforms CO-UCB significantly and outperforms AAE-AAE slightly. Comparing (c) and (d) shows that improvement of AAE-LCB over CO-UCB increases as the difference between action rates increases. Comparing (e) and (f) shows substantial regret degradation of CO-UCB in fast agent due to existence of slow agents.
Summing up the above two pieces of regret and the expected number of Type-Il decisions yields
4a log 8
KO;
120,a log 8-1
E [rrl
S
Σ
max
2
θ,
O,
O
10:
2
1
89,08-
θ,,
8,
jEA 1m1 iE
This completes the proof.
Numerical Experiments
Our goal in this section is to numerically investigate the performance of AAE-LCB and compare it to that of AAE-AAE and CD-UCB (see Section (.3), and show that AAE-LCB effectively resolves the challenge slow agents present, while neither AλE nor CO-UCB do so. More specifically, by comparing AAE-LCB with CO-UCB, our goal is to verify the importance of two-stage learning in the design of AAE-LCB, and by comparing AAE-LCB and AAE-AAE, our goal is to verify the importance of using LCB as the indexing policy for external arm selection.
Experimental setup. We assume there are K = 100 arms with Bernoulli rewards with average rewards uniformly randomly taken from Ad-Clicks (I] our experiments, we report the cumulative regret after 30,000 rounds, which corresponds to the number of decision rounds of the fastest agent. All reported values are averaged over 20 independent trials. We have 20 agents, each with 12 arms selected from among set of K 100 arms into two categories of 10 "fast" agents each with action rate of and "slow" agents with varying action rates of less than 1. We compare the performances of AAE-LCB and AAE-AAE and CD-UCB that introduced in Section
Experimental results. Figures ((a) and ((b) we fix the action rate of the fast agents and vary the ratio between action rate of fast and slow agents from 5x to 25x with steps of 5. The results

---

show relatively sound performance of AAE-LCB as the speed ratio between fast and slow agents increases. However. the performance of CO-UCB decreases substantially as shown in Figure [[b] average per-agent regret, which is mainly due to treating local and external arms in the same way. This further verifies our intuitions for the need to distinguish between local and external arms as the main motivation for developing AAE-LCB. AAE-AAE and AAE-LCB exhibit similar performance showing the importance of prioritizing the local arms, however, AAE-LCE LCB performs slightly better since it uses better external arm selection policy than that of AAE- AAE. The evolution of cumulative regrets over time in Figures [[c] and [ and per-agent regret for fast and slow agents in Figures [(e]
and I(f) also demonstrate that AAE- LCB outperform the alternatives.
Note that the above experimental scenarios are designed to demonstrate the "average-case" performance, since re- wards of arms are generated according to real data traces and all arms are randomly allocated to fast and slow agents, However, another important consideration on the efficiency of learning algorithm is its performance in the worst case. From our thcoretical results in Section 4 base- line algorithms suffers severe performance degradation and our algorithm outperforms the baseline algorithms a lot only when the optimal arm lies in a fast agent and there exists some arm with few observations. Specifically, the regret of the AAE-A AAE algorithm degrades with the small- est aggregate action rate of agents containing arm i, E IC, i.e. miin while that of AAE-LCB depends the action the "worst" case
0.08
Avg Cumu Regret @Ronn
AAE-LCB
0.07
AAE- AAE
0.06
0.05
0.04
0.03
0.02
6x
10x
15x 20x 25x 30x 35x 40x
Speed Ratio: Fast vs Slow Agents
Figure 2: Performance comparison in
rate of the agent which the optimal arm lies in. To validate the efficiency of AAE-LCB in the worst case, we straiy add a synthetic scenario and generate a special worst-case instance where the optimal arm only lies in fast agents. Specifically, we rank the arms in descending order based on their reward means, and allocate half of the arms with high reward means only to the fast agents and the other half only to the slow agents. The results in Figure 2 show as the ratio between the action rates of slow and fast agents increases, AAE-LGE LCB outperforms AAE AAE significantly.
Conclusion and Future Directions
In this paper, proposed bandit algorithms with near-optimal regret for cooperative stochastic bandit problem among multiple agents playing the same instance of the problem, each with limited access to the set of arms and with different decision-make capabilities.
limitation of this work is that in the current result, there is a gap between the regret of AAE-LCB and the regret lower bound. We leave developing an algorithm with the optimal regret for the FC-CMA2B setting as an open problem. Additionally, critical, yet practically relevant question how to extend the algorithms to the case with communication delay and cost between agents. We address the communication delay in the supplementary material of the paper. Regarding communication cost, the question is how to design algorithms that can provide a tradeoff between the regret and communication costs. While this tradeoff has been studied extensively in recent works 18 21 29 5T], none of them consider this tradeoff in the presence of heterogeneous agents. This task is challenging since in each decision-making making round, each agent should make a nontrivial decision on whether or not broadcast with other agents or subset of agents. Another question arises by considering topological constraints for agents. In this work, we focus our analysis to a set of fully-connected agents. In practice, however, geographically distributed agents might have limited access to other agents over an underlying graph. This setting also has been studied in recent works such as [36, 48]; however, there is no work on the heterogeneous version of this setting. Last, do not see any negative societal impacts of our work.
Acknowledgments and Disclosure of Funding
We acknowledge the support from U.S. Army Research Laboratory Army Research Laboratory under Cooperative Agreement W91 W991NNF-1-22 17-2-17-- (loBT CRA) and from U.S Army Research Laboratory and the U.K. Ministry of Defence under Agreement W91 1911NNF11633-000 support by NSF CAREER 2045641, CNS 1908298, 2102963, and CPS 21 2136199. The work of John C.S. Lui was supported in part by the GRF 14200420 and SRFS2122-4202.
We also acknowledge the
10

---

References
[1] Kaggle avito
context ad ad-cikks
clicks 2015.
https://www. http:://wwwwkkgll....m wwggle.com/c
[2] S. Amani and C. Thrampoulidis. Decentralized multi-agent linear bandits with safety constraints. Proc. of AAAI, 2021.
[3] A. Anandkumar, N. Michael, A. K. Tang, and Swami. Distributed algorithms for learning and cognitive medium access with logarithmic regret. IEEE Journal on Selected Areas in Communications, 29(4):731-745, 2011.
[4] Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3))233-25555 2002.
[5] O. Avner and S. Mannor, Multi-user lax communications: multi-armed bandit approach. In Proc. of IEEE INFOCOM, pages 1-9, 2016.
[6] B. Awerbuch and R. Kleinberg. Competitive collaborative learning. Journal of Computer and System Sciences, 74(8): 12711-288, 2008.
[7] Y. Bar-On and Y. Mansour. Individual regret cooperative nonstochastic multi-armed bandits.
In Advances in Neural Information Processing Systems, pages 3116-3126, 2019.
[8] D. Basu, C. Dimitrakakis, and A. Y. Tossou. Privacy in multi-armed bandits: Fundamental definitions and lower bounds. arXiv: 12298v2, 2019.
[9] L. Besson and E. Kaufmann. Multi-player bandits revisited. In Algoritmmic Learning Theory, pages 56-92. PMLR, 2018.
[10] I. Bistritz and N. Bambos. Cooperative multi-player bandit optimization. Advances in Neural Information Processing Systems, 33, 2020.
[11] Bistritz and A. Leshem. Distributed multi-player bandits-a game thrones approach. In Advances in Neural Information Processing Systems, pages 7222-7232, 2018.
[12] R. Bonnefoi, L. Besson, C. Moy, E. Kaufmann, and J. Palicot. Multi-armed bandit learning in iot networks: Learning helps even in non- stationar settings. In International Conference on Cognitive Radio Oriented Wireless Networks, pages 173-185. Springer, 2017.
[13] E. Boursier, E. Kaufmann, A. Mehrabian, and V. Perchet. A practical algorithm for multiplayer bandits when arm means vary among players. In AISTATS 2020, 2020.
[14] E. Boursier and V. Perchet. SIC-MMAB: synchronisation involves communication in multi- player multi-armed bandits. In Advances in Neural Information Processing Systems, pages 12071-12080, 2019.
[15] G. Bresler, D. Shah, and L. Voloch. Collaborative filtering with low regret. In Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science, pages 207-220, 2016.
[16] S. Bubeck, N. Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1):1-122, 2012.
[17] S. Bubeck, Y. Li, Y. Peres, and M. Sellke. Non-stochastic multi-player multi-armed bandits: Optimal rate with collision information, sublinear without. In Conference on Learning Theory, pages 961-987, 2020.
[18] S. Buccapatnam, Tan, and L. Zhang. Information sharing in distributed stochastic bandits. In Proc. of IEEE INFOCOM, pages 2605-2613, 2015.
[19] N. Cesa-Bianchi, T. Cesari, and C. Monteleoni. neighbors updated. Algorithmic Learning Theory, pages 234-250, PMLR, 2020.
Cooperative online learning: Keeping your
[20] N. Cesa-Bianchi, C. Gentile, Y. Mansour, and Minora. Delay and cooperation in nonstochastic bandits. In Conference on Learning Theory, pages 605-622. PMLR, 2016.

---

[21] M. Chakraborty, K. Y. P. Chua, S. Das, and B. Juba. Coordinated versus decentralized explo- ration in multi-agent multi- armed bandits. In LJCAI, pages 164-170, 2017.
[22] C. Cortes, G. DeSalvo, C. Gentile, M. Mohri, and S. Yang. Online learning with sleeping experts and feedback graphs. In International Conference on Machine Learning, pages 1370-1378, 2019.
[23] J. Darak and M. K. Hanawal. Multi-player multi-armed bandits for stable allocation in hetero- geneous ad- hoc networks. IEEE Journal on Selected Areas in Communications, 37(10))2350- 2363, 2019.
[24] R. Della Vecchia and T. Cesari. An efficient algorithm for cooperative semi-bandits. In Algorithmic Learning Theory, pages 529-552. PMLR, 2021.
[25] A. Dubey and A. Pentland. Cooperative multi-agent bandits with heavy tails. In Proc. of ICML, 2020.
[26] A. Dubey and A. Pentland. Differentially-priiese federated linear bandits. In Proc. of NeurIPS, 2020.
[27] A. Dubey and A. Pentland. Kernel methods for cooperative multi-agent contextual bandits. 2020.
[28] E. Even-Dar, Mannor, and Y. Mansour. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 10un):1099-1105 2006.
[29] E. Hillel, Z. S. Karnin, T. Koren, R. Lempel, and O. Somekh. Distributed exploration in multi-armed bandits. In Advances Neural Information Processing Systems, pages 854-862, 2013.
[30] Ito, D. Hatano, Sumita, K. Takemura, T. Fukunaga, N. Kakimura, and K.-I. Kawarabayashi. Delay and cooperation in nonstochastic linear bandits. In Proc. of NeurlPS, 2020.
[31] Jiang, R. Das, G. Anamthanarayanan, P. A. Chou, V. Padmanabhan, V. Sekar, E. Dominique, M. Goliszewski, D. Kukoleca, R. Vafin, et al. Via: Improving internet telephony call quality using predictive relay selection. In Proc. of ACM SIGCOMM, pages 286-299, 2016.
[32] L. Jin, S. Li, L. Xiao, R. Lu, and B. Liao. Cooperative motion generation in distributed network of redundant robot manipulators with noises. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 48(10):1715 1724, 2017.
[33] D. Kalathil, N. Nayyar, and R. Jain. Decentralized learning for multiplayer multiarmed bandits. IEEE Transactions on Information Theory, 60(4):2331-255 2345, 2014.
[34] V. Kanade, H. B. McMahan, and B. Bryan. Sleeping experts and bandits with stochastic action availability and adversarial rewards. In Artificial Intelligence and Statistics, pages 272-279, 2009.
[35] R. Kleinberg, A. Niculescu-Mizii and Y. Sharma. Regret bounds for sleeping experts and bandits. Machine learning, 80(2-3):245-217 272, 2010.
[36] R. K. Kolla, K. Jagannathan, and A. Gopalan. Collaborative learning of stochastic bandits over a social network. JEEE/ACM Transactions on Networking, 2684):172--1795. 2018.
[37] Landgren, Srivastava, and N. E. Leonard. Distributed cooperative decision-making making in multiarmed bandits: Frequentist and bayesian algorithms. In Proc. of IEEE CDC, pages 167-172, 2016.
[38] P. Landgren, V. Srivastava, and N. E. Leonard. Social imitation in cooperative multiarmed bandits: partition-based algorithms with strictly local information. In Proc. of IEFE CDC, pages 5239-5244, 2018.
12

---

[39] J. Langford and T. Zhang. The epoch-greedy algorithm for contextual multi-armes bandits. In Proceedings of the 20th International Conference on Neural Information Processing Systems, pages 817-824. Citeseer, 2007.
[40] F. Li, J. Liu, and B. Ji. Combinatorial sleeping bandits with fairness constraints. IEEE Transactions on Network Science and Engineering, 2019.
[41] S. Li, R. Kong, and Y. Guo. Cooperative distributed source seeking by multiple robots: Algorithms and experiments. /EEE/ASME Transactions mechatronics, 190011810-1820, 2014.
[42] K. Liu and Q. Zhao. Decentralized multi-armed bandit with multiple distributed players. In Proc. of Information Theory and Applications Workshop (ITA), pages 1-10, 2010.
[43] K. Liu and Q. Zhao. Distributed learning in multi-armed bandit with multiple players. IEEE Transactions on Signal Processing, 58(1) 58(11):56667 ):5667-5688) 2010.
[44] U. Madhushani, A. Dubey, N. Leonard, and A. Pentland. One more step towards reality: Cooperative bandits with imperfect communication. Advances Neural Information Processing Systems, 34, 2021.
[45] D. Martinez-Rubio, V. Kanade, and P. Rebeschini. Decentralized cooperative stochastic bandits.
In Advances in Neural Information Processing Systems, pages 4529-4540, 2019.
[46] S. McQuade and C. Montelconi. Global climate model tracking using geospatial neighborhoods. In Proc. of AAAI, 2012.
[47] H. Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5) 1952.
[48] A. Sankararaman. A. Ganesh, and S. Shakkottai. Social learning in multi agent multi armed bandits. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3(3):1- 35, 2019.
[49] C. Shi and C. Shen. Federated multi-armed bandits. In Proc. of AAAi, 2021.
[50] A. Slivkins. Introduction to multi-armed bandits. arXiv preprint arXiv: DEK.::1904.07222.,0 2019.
[51] B. Szorenyi, R. Busa-Fekete, Hegedus, R. Ormándi, M. Jelasity, and Kégl. Gossip-based distributed stochastic bandit algorithms. In International Conference on Machine Learning. pages 19-27, 2013.
[52] D. Vial, S. Shakkottai, and R. Srikant. Robust multi-agent multi-armed bandits. arXiv preprint arXiv:2007.03812, 2020.
[53] P.-A. Wang, A. Proutiere, K. Ariu, Y. Jedra, and A. Russo. Optimal algorithms for multiplayer multi-armed bandits. In International Conference on Artificial Intelligence and Statistics, pages 41 4120-4129, 2020.
[54] W. Xia, T. Q. Quek, K. Guo, W. Wen, H. H. Yang, and Zhu. Multi-armed bandit based client scheduling for federated learning. IEEE Transactions on Wireless Communications, 2020.
[55] L. Yang, Y.z. J. Chen, M. Hajiesmaili, J. C. Lui, and T. Don. Distributed bandits with heteroge- neous agents. In IEEE International Conference on Computer Communications (INFOCOM), 2022.
[56] Z. Zhu, J. Zhu, J. Liu, and Y. Liu. Federated bandit: A gossiping approach. In Proc. of ACM Sigmetrics, 2021.
13


Reviews:
[{"review_id": "k9r7iXLVBXF", "reviewer": "Reviewer_BHsX", "summary": "This paper studies the problem of asynchronous multi-agent bandits when the agents have different local set of arms. The agents can pull any arm but only observe the feedback when pulling among their local set. \nThe authors propose both a lower bound and an algorithm with an upper bound scaling as the lower with an extra K multiplicative term.", "questions": "", "limitations": "", "rating": 7, "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": "Post-rebuttal: I want to thank the authors again for their detailed answers. I now clearly understand why using LCB is better than 'best empirical arm' during the exploitation phase.\n\nConcerning the lower bound, this would require a substantial modification of Theorem 1 (and its proof) and I would be grateful to the authors for communating the revised exact formulation of Theorem 1 as soon as available. \nOverall, I do trust the authors for carefully correcting Theorem 1, thus raising my score.\n\n------------------------------------------\n\nThe paper is well written and very clear. The ideas involved by this new setting are interesting and I thus think this paper is the ground for a great piece of work. Still, I have some small reservations concerning the proposed lower bounds and upper bounds, as I believe that both (and especially the latter) can be improved. I detail how below and let the authors answer in the rebuttal whether such improvements are indeed possible.\n\nAbout the lower bound: first I think the Theta/Theta_i* should be put in the left term instead, as it goes to infty. Otherwise the Omega(.) notation is a bit weird.\nMore importantly, I would have hoped such a bound to hold even when Theta/Theta_i* remains fixed. I think it is a major drawback in the current lower bound and the difficulty to prove a similar bound for a fixed ratio should be discussed.\n\nAbout the upper bound. First the presentation as an AAE algorithm with stages 1 and 2 is a bit awkward, since it seems that the set of active arms C_{j,t} is not necessarily decreasing in t. In particular, an inactive arm at some time step can be reactivated, as delta_t decreases, and thus the confidence interval grows. As a consequence, the current description of the algorithm is a bit counterintuitive and might be adjusted in a future version.\n\nI also think the algorithm can be improved (and eventually the extra K factor removed) with minor modifications. To do so, it seems that if agents pull the maximal empirical arm (instead of maximal LCB) in stage 2, then the regret caused by the second stage should be constant in T. (to prove such things, you can for example use a proof with ideas similar to 'Optimal Algorithms for Multiplayer Multi-Armed Bandits' by Wang et al.) If this is not a good idea, it should at least be discussed in the paper as to me the instinctive way to 'exploit' during stage 2 is to pull the best empirical arm, not the largest UCB.\n\nin stage 1, it seems that the K factor appears because the 'exploring' agent only pulls the optimal arm at least 1/K of her time. If instead she pulled her best (local) empirical arm with proba 1/2 and explored with proba 1/2, this might do the trick (at least for a single unique arm). (you can also adapt ideas from Wang et al. here I think)\n\n------- minor comments -------\n\n- Although being delayed to the Appendix, the related work section seems rather complete in my opinion. I just think the recent paper by Della Vecchia and Cesari is missing as a reference for asynchronous multi-agent bandits.\n\n- the activation rounds of each agent are here deterministic. Why not use stochastic activation instead? (as done in sleeping bandits and in the existing literature on asynchronous multi-agent bandits)\n\n- line 119: it seems you never exactly say that x_t(i) follows a (subgaussian) distribution of mean mu(i)\n\n- Algo 1: lines 3-5 -> it is a bit weird to repeat these lines twice at each round. I think it should be better handled for presentation purpose\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not concerned", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "i6e3PwPq8zy", "reviewer": "Reviewer_b73Y", "summary": "This paper considers a variant of the cooperative bandits where there are N agents cooperatively trying to find the best arm, but have certain constraints. First, each agent has a \"rate\" that is the number of time-steps after pulling an arm after which they can pull another arm. This rate can be different across different agents. Second, each agent has a subset of arms that are local which it can pull and see the observation and the rest are global which it can pull and only receive the feedback via communication from other agent. The broadcast information is assumed to be 0 cost and 0 delay. The goal of the agents is to minimize the total regret across the T time-steps. For this new setting of the problem, the paper provides an active arms elimination style algorithm that keeps playing the local arms, while collecting the broadcast for other global arms, until the confindence interval of some local arm does not overlap with that of a global/local arm and that the mean is lower.", "questions": "", "limitations": "", "rating": 7, "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": "Originality: The problem introduced in this paper is new and introduces a new twist to the cooperative bandit setting. This twist is well-motivated by practical applications where each agent can be thought of as a server in a distributed setting and the only communication with requests served by other servers is via the internal network. The algorithm considered in this paper is also novel and does not do the usual \"construct UCB and pick the largest arm\" type approach. In fact, the idea of playing only locally available arms and getting the feedback for the global arms via the network seems to be original. The paper also confirms their theory with simulations.\n\nQuality/Clarity: Overall the paper is well-written and clear to read. The paper explains the setup clearly, their algorithm is also described in detailed informally and overall very pleasant to read and understand. The simulations in the paper also are useful add and complements the theory thus, giving more confidence on the correctness of the main theorem without having to carefully check all the steps in the proof.\n\nSignificance: Since the problem is new the results obtained in this paper are new and significant. Moreover, the notion of public and private arms is an interesting dimension and is of potential interest beyond cooperative bandits. For instance, an interesting future direction is to study the same in the competitive environment. Here the dynamics of the agents will be completely different, and an agent will be incentivized to play global arms, even if they don't see feedback to \"block\" other agents.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Overall I do not find much limitations to the work in this paper. One suggestion would be to take a concrete application and described in detail how this setting can model that problem. I do not find this to be a major point, but just a minor comment on the presentation so that the results are widely appreciated in the conference.\n\nRegarding societal impact, since this is primarily a theory paper I do not forsee much impact beyond the general impact bandits as a field has.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "96U67HathkK", "reviewer": "Reviewer_rnQi", "summary": "The paper studies a cooperative multi-agent stochastic bandit problem with a setting in which each agent only have limited access to a local subset of arms and all the agents are asynchronous with different gaps between decision-making rounds. An algorithm is proposed for this setting and a regret bound is derived. ", "questions": "", "limitations": "", "rating": 5, "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": "The paper considers important aspects of cooperative multi-agent bandit problems, one is the heterogeneous setting in which each agent only has access to a subset of all arms, and the other is asynchronous sampling. Both two aspects have not been (fully) studied in the literature. \n\nMy main concern of the paper is its problem formulation. It is assumed that the agents are allowed to pull and receive a reward from any arm but only receive observations from local arms. That is to say, an agent may pull an arm without knowing the reward. Is there any application for such a setting? Meanwhile, it is also assumed that once each pulls an arm, it instantaneously forwards this observation to all other agents. Therefore, each agent can constantly be aware of all reward sampling information in the network, except for some of its own rewards. Since there is no reward distribution difference among the agents, the setting and assumptions imply that each agent can learn the best arm simply using the standard single-agent stochastic bandit algorithms. Although the asynchronous sampling brings difference and possibly complication, the over setting/assumption for the heterogeneous observability is not convincing and lacks applications. \n\nUpdate Sep 2: Thanks the authors for very detailed responses. After intensive discussion with other reviewers, I better understand the main technical contribution of the paper: improve the regret dependency on action rates in the asynchronous case. With this, I increase my score from 4 to 5. I suggest the authors to move the delay case results to the main paper, as it can deal with general non-incomplete graphs. The current main paper focuses on complete graphs, which is quite limited for a cooperative setting. My remaining concern is when dealing with non-complete graphs, the paper allows reward relays over the network, which simplifies the algorithm design and analysis. Another comment is that the current lower bound relies on a limiting condition, which is not a general lower bound. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "7X-_Ho38YA", "reviewer": "Reviewer_LVPx", "summary": "This paper studies an asynchronous distributed multi-arm bandit problem. In this problem, each agent can pull arms at a different rate. In addition, each agent can only observe the reward from a subset of arms. The reward observed by an agent is immediately broadcasted to all other agents. The question is to analyze regret. The paper provides both upper and lower bound results. \n\n", "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": "\n\nContribution: \n\tModeling: I believe it is important to have a clean model for distributed multi-arm bandit problem, in which each agent can pull arms at a different rate. I think many that have worked on distributed multi-armed problems secretly wondered this question (but I have not been following the literature for a while). The model, algorithmic, and lower bound results are quite clean. I think this \"co-optimization\" between model and upper/lower bound needs to be appreciated, e.g., the most clean model may have ugly upper/lower bound, and vise versa. \n\t\nBoth the algorithmic and the lower bound results are non-trivial. Most of the intuition explained in the papers is clear. The experiment results are also nice proof-of-concept. \n\t\nIn terms of writing, I see an effort was made here but it still feels like a difficult parse. A few examples: \n\n(i) When the authors describe intuition of the paper, they refer to prior works but related work section appears outside first 9 pages. Putting related work outside first 9 pages is a quite non-standard practice. It appears to be a symptom that the authors lost patience to carefully pack substance into 9 pages (just a speculation). Neurips becomes quite cut-throat in recent years and these \"details\" matter. \n\n(i) The number of symbols is also quite large, resulting in additional obstacles in reading. Some questions (a) what is alpha? It looks difficult to find its definition, (b) I cannot quite immediately tell a factor of $K$ gap as claimed by the authors from lower and upper bounds (theorem 1 & 2) (c) What happens when $\\Delta_i = 0$, it looks in upper bound, we get 0 divided by 0, and in lower bound, we get 0 in denominators (in Corollary). \n\nAlso, a gap of $k$ feels a quite serious problem. It smells like a trivial bound so some effort to explain this gap could be useful. \n\t\t\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see above. I feel it is mostly about being patient and carefully polish the first 9 pages. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers are mostly positive about this submission. They agree that the paper studies a new and relevant problem, and the techniques are non-trivial and interesting. The reviews also provide many directions for the paper to improve, e.g. (1) correcting and clarifying some technical details (2) adjusting the presentation order for better reader experience (3) strengthening the lower bound.
Decision: Accept (Poster)