Queue Up Your Regrets: Achieving the Dynamic Capacity Region of Multiplayer Bandits
Authors: Ilai Bistritz
Nicholas Bambos
Venue: NeurIPS 2022 Accept (2022)
Keywords: Multi-agent learning
Multiplayer bandits
Queuing theory
Game theory

Abstract: Abstract Consider $N$ cooperative agents such that for $T$ turns, each agent n takes an action $a_{n}$ and receives a stochastic reward $r_{n}\left(a_{1},\ldots,a_{N}\right)$. Agents cannot observe the actions of other agents and do not know even their own reward function. The agents can communicate with their neighbors on a connected graph $G$ with diameter $d\left(G\right)$. We want each agent $n$ to achieve an expected average reward of at least $\lambda_{n}$ over time, for a given quality of service (QoS) vector $\boldsymbol{\lambda}$. A QoS vector $\boldsymbol{\lambda}$ is not necessarily achievable. By giving up on immediate reward, knowing that the other agents will compensate later, agents can improve their achievable capacity region. Our main observation is that the gap between $\lambda_{n}t$ and the accumulated reward of agent $n$, which we call the QoS regret, behaves like a queue. Inspired by this observation, we propose a distributed algorithm that aims to learn a max-weight matching of agents to actions. In each epoch, the algorithm employs a consensus phase where the agents agree on a certain weighted sum of rewards by communicating only $O\left(d\left(G\right)\right)$ numbers every turn. Then, the algorithm uses distributed successive elimination on a random subset of action profiles to approximately maximize this weighted sum of rewards. We prove a bound on the accumulated sum of expected QoS regrets of all agents, that holds if $\boldsymbol{\lambda}$ is a safety margin $\varepsilon_{T}$ away from the boundary of the capacity region, where $\varepsilon_{T}\rightarrow0$ as $T\rightarrow\infty$. This bound implies that, for large $T$, our algorithm can achieve any $\boldsymbol{\lambda}$ in the interior of the dynamic capacity region, while all agents are guaranteed an empirical average expected QoS regret of $\tilde{O}\left(1\right)$ over $t=1,\ldots,T$ which never exceeds $\tilde{O}\left(\sqrt{t}\right)$ for any $t$. We then extend our result to time-varying i.i.d. communication graphs.

Queue Up Your Regrets: Achieving the Dynamic Capacity Region of Multiplayer Bandits
Ilai Bistritz, Nicholas Bambos
Stanford University
bambss bstarergabrbbbbosottttttoooooo. @stanford.eeee
Abstract
Consider N cooperative agents such that for T turns, each agent n takes an ac- tion an and receives stochastic reward Tn (ai...., aN). Agents cannot observe the actions of other agents and do not know even their own reward function. The agents can communicate with their neighbors on connected graph G with diame- ter d (G). We want each agent n to achieve an expected average reward of at least Xn over time, for given quality of service (QoS) vector X. A QoS vector À is not necessarily achievable. By giving up on immediate reward, knowing that the other agents will compensate later, agents can improve their achievable capacity region. Our main observation is that the gap between X, and the accumulated reward of agent n, which we call the QoS regret, behaves like queue. Inspired by this observation, we propose distributed algorithm that aims to learn a max-weight matching of agents actions. In each epoch, the algorithm employs a consensus phase where the agents agree on certain weighted sum of rewards by commu- distributed nicating only O (d (G)) numbers every turn. Then, the algorithm successive elimination on a random subset of action profles to approximately maximize this weighted sum of rewards. We prove bound on the accumulated sum of expected QoS regrets of all agents, that holds if A is a safety margin ET away from the boundary of the capacity region, where êT >> 0 as - oc. This bound implies that, for large T, our algorithm can achieve any X in the interior of the dynamic capacity region, while all agents are guaranteed an empirical average expected QoS regret of Ô (1) over 1..... T which never exceeds Ó (VF) for any l. We then extend our result to time-varying i.i.d. communication graphs.
1 Introduction
Consider a group of artificial cooperative agents interacting in a shared environment. Each agent has reward rn (a) that is function of the actions of all agents and represents local perfor- mance metric. Examples include wireless devices, robots in a facility, or autonomous vehicles. The designer wants program these agents with distributed protocol that guarantees least certain average reward for each agent, which we term its QoS. Wireless devices interact by transmitting and interfering with each other over multiple channels, and the wireless protocol guarantees the adver- tised throughput for all of them. Multitasking robots interact by cooperating to make progress on their tasks at certain rate, following a distributed learning algorithm with this objective in mind. The main challenge in designing such a distributed protocol or algorithm is that the agents are local and do not know enough about each other to guarantee the QoS of their peers.
In data-driven decision- decision-making, agents do not know their reward function, and can only observe its value at the current action profile (t), known bandit feedback. The agents also do not know the reward functions of their peers, or even their bandit feedback. As a result, agents have to learn both how to optimize their reward function, and when to prioritize other agents instead.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

The QoS is often measured over time. Throughput in communication networks is measured over seconds, and progress policy is often dynamic and combines time-sharing and simultaneous access. For example, consider four agents and one resource, such that each agent can access the resource or not. If Agents 1 and 2 access the resource simultaneously, they each get zero reward, and the same is true for Agents 3 and 4, Otherwise, an agent gets a reward of by accessing the resource. This simple example arises in many applications. In wireless networks, fär away devices can share the same channel, but nearby devices have to pick different channels. In cloud computing, a job that requires little RAM can run simultaneously with RAM-intensivve one, but two RAM-intensive jobs cannot share the CPU simultaneously. Similarly, we cannot charge too many electric vehicles that share a transformer simultaneously. In all these cases, dynamic algorithms can achieve QoS vectors that static multiagent algorithms cannot, where agents learn when to access, but also, who to access with.
factory is measured over minutes. In resource allocation, the optimal
The main objective of this paper is to design distributed multiagent algorithm that can achieve any dynamically feasible QoS vectors based only on bandit feedbaak and minimal communication.
1.1 Our Contributions
We define the QoS regret of agent n. by R. (1) = max {o, Fn given a QoS vector A. Our main observation that R2 (L) behaves like a queue, which inspires an algorithm that learns to approximate max-weight matching between agents to actions to guarantee the sta- bility of these "queues". A perfect centralized mei-ht policy [1] plays the a that maximizes En by, Rn (t) rn (a) for some positive {bn.. To be able to learn this policy distributedly, our al- gorithm divides the time horizon of length T into epochs of length Er. In each epoch, agents use simultaneous distributed averaging (i.e., consensus) steps to agree on E bn R. (+) In (a (t + 1)) from recent turns, row stochastic communication matrix W. Then, agents use a distributed and scalable successive elimination to approximately maximize Σn R,, (t) rm (a). Our consensus step does not require a doubly stochastic W and converges in finite time.
We show that for large T, our algorithm can achieve any À in the interior of the dynamic capacity region, where all agents have an empirical average expected QoS regret of Ô (1) over time which never exceeds Ô (vt) for any t. Our algorithm only requires each agent to communicate O (d (G)) numbers each turn, where d (G') is the diameter of the communication graph G. Furthermore, for finite T, we bound the accumulated expected sum of QoS regrets as a function the epoch length E, and characterize the safety margin Eg away from the boundary of the capacity region that is required to make À feasible. We then prove QoS regret guarantees for i.i.d. time-varying communication graphs, modifying both the bound on the accumulated expected sum of QoS regrets and Eg. For this more complicated case, the communication overhead is O (log" F) per agent per turn.
1.2 Related Work
Our work brings together game theory, learning, and queuing theory. Aspects of learning in queuing were studied in [2-5]. Queuing games were studied in [6]. where each agent chooses which queue to join. In contrast, our analysis uses the observation that the QoS regret behaves like a queue, but no real backlogs exist. We consider general discrete games that may have nothing to do with queues.
Multiplayer bandits is an emerging field that studies how agents can learn to achieve a common goal [7-11] given bandit feedback of their unknown reward functions. Most works on multiplayer bandits assume the collision model, in which when multiple agents choose the same arm, they all receive zero reward [12-17]. Instead of the sum of rewards, our objective is to guarantee that the empirical average reward of each agent is at least a certain QoS. Multiplayer QoS bandits were studied in [18], assuming the collision model. However, [18] only achieves QoS vectors X for which there exists an a such that E fr, (a)) 2 An for all n. Compared to [18], our work considers general discrete game. But even for the collision model, for the example on the top of this page, two agents get zero reward in any static solution like [18], while we can achieve X, = 0.5 for all n.
Dynamic multiplayer bandits, where agents can join at different times, were studied in [12, 15, 17] under the collision model. More related to our work, [19], and recently [20], combined queuing with multiplayer bandits. In [19,20] each agent (queue) receives packets randomly, and each packet is

---

transmitted to a server of choice, where servers have constant [19] or igent-dependent [20] service rates. Each server can only process one received packet each turn, given selection rule. In contrast, our scenario has no actual queues or packets and considers general (discrete) game, so the "service rate" for each agent an arbitrary function of the actions of all agents (i.e., reward function).
In power control, [21]] can achieve any target QoS vector that is achievable by a static transmission power profile. The interaction between the wireless links, through the interference, a game with the transmission powers as the actions. From this point of view, our work generalizes [21] in two ways: from power control to general game (but discrete), and from a static dynamic solution.
2 Problem Formulation
We consider a general multiplayer aumti-armed bandit game. At every turn > 1, for T turns, each agent n in the set A {1, [L.....N] .V picks an action a, (t) {0. (O..... K 1}. The expected reward
for agent n is an unknown function of the actions of all agents jon (0...., K 11 + IR. Each agent only observes stochastic reward, rn (a (t)) [0, 1], such that pn, (a) = EE (r, (a)) and An (t) In (a (t)) Jm, (a (t)) independent over time and between agents. Agents only know
the action they played and cannot observe the actions of others.
Our goal is to design distributed algorithm for the cooperative agents, that dictates the actions an (1) (1)...., an (T') of each agent n, such that ideally
T Σ T
min
Nn (a (t))
An
An 2
i.., the empirical average of the expected reward of agent is least A, for all
The objective in (1) is only possible for certain QoS vectors A AN- The achievability region of the dynamic problem in (1) can be much larger than the static one which includes all À for which maxmin (Mn (a) Xn) 2 0. As an example, consider a game with N 2 and K = 2, n such that μ1 (1, = 1, #1 (0,0) = μr (0. = μn (1, = O and #2 (0, 1) = 1. μ1 (0, 0) = 42 (1, = #2 11 0. Then X maxmin44, (a) = 0 is obtained for any fixed 01, ag and no d1, A2 X are feasible. However, if the agents play (1,0) in even turns and (0, 1) in odd ones then + +E M4 (t)) EE= (t)) 1 X This simple example arises often when sime-sharing of resources is better than simultaneous access. In general, the optimal strategies can involve softer time-sharing or time-sharing between groups of agents, based on their characteristics.
This motivates defining the dynamic capacity region [1]:
Definition 1. Let E 2 O. The approximate dynamic capacity region of the game g (N, (0.... ... K - -1]nn ((n)nEN) is defined as the set:
C. (9) = Aw)...,))IIPPEA. s.t. Ep(a) un (a) An t Vn
where p (a) is the probability of a and A KN is the K N -th dimensional simplex. The (exact) dy- namic capacity region is then (g) & Co (g).
A learning algorithm that has knowledge of the game will need time to achieve (1), we can only hope to achieve (1) up to some --dependent error, which we term the QoS regret.
Definition 2. The QoS regret of agent n at turn defined as
R, (t) & max 0, Ant Emm(a(m)))
The expected QoS regret encodes that an agent "regrets" the total accumulated reward misses to have an expected empirical reward of at least X,, On the other hand, an agent with an empirical average reward of more than An does not require anything more so has zero QoS regret. Note that if the expected QoS regret of all agents is zero then (1) holds with probability 1.
3

---

Our contributions are novel distributed algorithm that can learn to achieve a target QoS vector, with the following performance guarantees:
bandit game, played for T turns. Let the agents run Algorithm! I on connected communication graph G, with epoch length For such that Er + oo + O (Er) for all n and TE RR. (1) = (VIEr) for all and where the expectation is with respect to the randomness of the algorithm and the rewards. To achieve this, each agent only needs to Gf G.
Theorem 1. Let G be a multiplayer
and Ex 0 as T + OC. If X E C (G), then for large enough T, we have + Et E (Ra (t)
communicate O (d (G)) numbers' per turn, where d (G) is the diameter
The QoS regret guarantees of Theorem I are asymptotic in T. For finite T, tradeoff arises between E { Rm (T)} } and the safety margin ET we have to take from the boundary of C (G) to guarantee this E [R. (T)). Theorem 2 in the next section analyzes this tradcoff explicitly and shows that ET - 0 as T + oo, which implies Theorem above as a special case. By tuning the epoch length E, we can make Ex smaller for finite T, at the price of increasing the expected QoS regret,
vice versa. As long as Ey increases with T. then Fr - O and our algorithm can achieve any À E C (G) for large enough T. Hence, if E, log T (or slower), then Theorem 1 implies that the empirical average expected QoS regret of all agents is Ô (1) and no expected QoS regret exceeds Ô (Vt) for any t. For finite/ E, these two bounds slightly improve to O (1) and O (Vl) respectively, as long À E Ceg (9).
In Section 12 in the appendix, we generalize Theorem for a stochastic time-varying i.i.d. commu- nication graph where only the union of the support set is assumed be connected. This requires some slight modifications to our algorithm, detailed in Algorithm 2, among them using the delay parameter DE = O (log² E). As a result, each agent needs to communicate O (log² E) numbers per turn.
might look tempting to view (I) as the two-player zero-sum game min max (A,, Ea pn (a)). Solving zero-sum games with bandit feedback is an PEAKN active field of research [22, Chapter 9]. The idea is that if the column and row players both use no-regret algorithm, then the empirical distribution of the action profiles is an -Nah equilibrium (NE) with vanishing er, and the empirical average cost of the row player converges to the value of the game. The convergence rate is then the regret of the row player, divided by T. It is an open question whether a convergence rate better than O (T-3) b) is possible [23, 24], which is achievable if both players use EXP3. To employ this technique in our scenario, one agent will have to operate as a leader that virtualizes the row player that picks p and the column player that picks n. This leader agent then broadcasts the chosen action profiles, which are propagated over G, so each agent sends O (N) numbers every turn. This approach, however, would fail to provide any QoS regret guarantees. First, the average cost of the row player is not the QoS regret of any of the agents in our game. Second, the fact that the distribution of play p (T)) is an eT-NE does not provide any Fuclidean distance convergence rate of p (T) the exact NE. Hence, there is no bound on the incurred QoS regret of p (T). Remarkably, our queuing approach to solving (1) not only circumvents these issues but achieves, for any X E C (G), an Ô (1) empirical average expected QoS regret over t = , for all agents, while the expected QoS regret is never worse than Ô (Vt) for any t and n. Furthermore, our communication overhead is only O (d per agent per turn.
3 Dynamic Multiplayer Bandit Algorithm
To tackle the problem in (I), we exploit the similarity between the QoS regret and a queue. We can think of a deterministic arrival flow with rate Xn and a service rate of r. (a (1)) for agent n at turn Then we can employ ideas from queuing theory to design our algorithm. In particular, max-weight matching of queues to service rates a centralized algorithm that achieves optimal throughput [25]. Note that in our case the service rate (the reward) is function of the actions of all agents. Hence, our algorithm has to learn to approximate a max- meight matching distributedly for our game model.
'These numbers are convex combinations of rewards, and their timestamps. They can be quantized with finite resolution without affecting our analysis since we only approximately optimize the weighted sum of rewards anyway. The communication overhead is reported for comparison purposes with other schemes that communicate rewards.

---

Our algorithm, detailed as Algorithm 1, divides the horizon into epochs. In each epoch, the agents treat their QoS regrets as fixed on their initial value, which is an approximation (Step 1). Based on these values the agents distributedly learn to maximize Σn= R, (t) an (a) for some positive {bn); ), using successive elimination (see Lemma 3). Much of the algorithm's 's efficiency stems from the fact that we do not care what {b,] are, as long as they are positive and constant over epochs. For stochastic time-varying i..d. communication graphs (Section 12 in the appendix), bn (t) will be time-varying as well, and then we need its expectation to be positive and constant over epochs.
Algorithm 1 has low runtime complexity per turn of O (Up, Dr + Sx) for agent n, which only computes linear combinations values from its Vn neighbors for Dg turns simultaneously, and goes over list of Sg action profiles.
Algorithm Dynamic Multiplayer Bandit QoS Learning
Initialization: Set the epoch index to e = and the successive climination index to / = O. Let W be the communication matrix (Definition 3). Let Sg min {[So log ET, K E], for some So > 0, for all i,
be the random subset size and DE > 0 be the delay parameter. Let b., = [WD8), j.s Input: A, 2 0 and agent index For each epoch e 2 0, each agent runs:
I' 1. Compute the QoS regret for epoch e, R max { Ant A En (a (F
2. Randomize actions a ...,.. o uniformly and independently over (0...., K - 13. Store their indices in the ordered set B (1,...: [g), where B (1) is the 1-th element.
3. Set 0 A. = 0 for all i I,..., Sg. set i, 1 and Te =eE
4. For T. St - E - (E turns):
(a) Set 6% = F, R, and 6% = for all m + n.
(b) Broadcast ((0T, +) De-1 to neighbors and receive {( T DE-1 from neighbors.
(c) Parallel DE Consensus Steps: Set 0,+1 = >m== Wn,m On VT = O,..., DE 1.
(d) Agreement: If you know 0f for DE < < 2D 1 then broadcast r).
(e) If you receive (0I, T) for DE < < 2DF -1 then set the weighted sum of rewards from T turns ago as S (t T) = 07.
(f) Play an (1) = dn (3()) and set Fa = Tn (a (1)).
(g) Update the number of visits 2/ + Us + to a (at . for B 2D
(h) Compute the confidence radius Pk 2(>0N bI R2)² lop E
and
max/
ja (1-
Au + S (t)2DD)
LA Pu Pk
UE Puk + Pk.
Uk
Uk
(i) Elimination: If |B] then delete from B all i such that Us < max Lij, and set / = 0.
jEB
Update the successive elimination index / + 1+1. 1.
5. Update the epoch index e +- -
End
3.1
Communication
To know the reward values of others, agents need to communicate. We assume that agents can send numbers over communication graph G, weighted by row-stochastic communication matrix W: Definition 3. Let G be the adjacency matrix of undirected connected graph, such that G agent n and agent m can communicate or that n = m. Let vn be the degree agent n G. Let W be matrix such that Wp,m > 0 if and only if Gn,m = 1 and Σm Wn,m = 1 for all n.
A key design question is how much should agents know about each other to achieve (1). A max- weight matching at turn is that maximizes EN R, (t) pm (a) for some positive (6,).. A
5

---

naive choice is to guarantee that all agents know all rewards before taking an action. This would re- quire each agent to send O (N) numbers per turn, so it is infeasible in large-scale networks. Instead, our algorithm requires communication overhead of O (d (G)), without sacrificing performance. This dramatic save in communication is possible since to guarantee stability, agents do not need to have the same coefficient b, in the sum. Hence, in Algorithm 1, agents run the consensus only until all local averages include all [ i (a (t)),, (where R. & R. (t)), even if not with equal b,.
In contrast to the distributed optimization literature [26], we do not need the communication matrix W to be doubly stochastic, which is hard to guarantee distributedly [27]. Since W is not doubly stochastic, our consensus cannot converge to the average reward. In fact, since we stop the consensus early after exactly Dg turns, it does not converge at all. However, after our consensus step, each agent has a weighted sum of rewards that includes all agents that have a positive QoS, with weights that depend on W. the next DE turns, agents propagate (Steps 4(d) and 4(e)) the weighted sum of rewards that Agent I obtained, such that they all eventually know it with zero error.
Our algorithm introduces delays so that agents can agree on Σm= b1.n R. (a (t + 1)), that Agent I obtained after the distributed averaging step (Steps 4(b) and 4(c)). If the diameter of G is d (G), then minimum of d (G) turns is necessary to guarantee that all agents contributed to En b Ra (a (t+ 1)). However, it is unnecessary to continue the consensus after this point, which is a major advantage of our consensus scheme over the classical one.
In Steps 4(b)-4(e), agents pipeline De simultaneous consensus algorithms that cannot be mixed since they are on the rewards generated at different turns from different action profiles.
In connected graph d (G) S N so Dg = N is always sufficient. However, usually, a tighter bound on d (G) is available. For a random Erdös-Rényi graph G (N.p), d (G) = O probability [28], and G (N, p) is connected with high probability for p clog N with > 1.
log with high Tog(Np)
In our scenario, an apriori bound on Σn= b1.- R2, ra (a), the effective reward for the successive elimination, is unknown to the agents but is needed to adjust the confidence radius Pk. Hence, at the beginning of each epoch (Step 4(a)), agents start a consensus averaging on {R.),. to obtain Σn bi.n R2 which bounds E M,, (a), but varies between epochs.
3.2 Distributed and Scalable Successive Elimination
In the second part of every epoch (Steps 4())-()), agents use the values they got in the commu- nication step to run distributed successive elimination on a random subset of the action profiles. In our case, the effective reward of "arm" at epoch is Σn bi.n R2 (a). In Step 2, each agent prepares a sequence of Sg actions independently and uniformly at random. This induces a sequence of Sg action profiles that all agents agree on their indices B {l...., SEY (which can include duplicates). Therefore, all agents count the same number of visits Va (t) for all a in Step 4(g). Moreover, all agents agree the same weighted sum of rewards for the action profile they played 2D turns ago, denoted by fu for & = B 2Dg). Hence, all agents compute the same confidence radius Pk: in Step 4(h), for all the action profiles indexed in B. As a result, all agents agree on when to eliminate an action profile from B in Step 4(i) and will skip it in their next cycle over the action profiles, which is indexed by I.
Restricting the search to a random subset of action profiles is done to improve the scalability of the algorithm, as we discuss in detail in Section 7 of the appendix. For Sg = K. no randomization is needed as agents can go over all the action profiles sequentially.
3.3 QoS Regret Guarantees
Theorem 2 below bounds the expected QoS regrets of the agents. The proof is given in the appendix. If the epoch length ET increases with T, then the theorem shows that E (R,, (t)} O (VErt) for any n, t and any À C (G). However, this does not provide a guarantee on the fraction of time during which the QoS regret of a specific agent is "large". A highly fluctuating QoS regret means that an agent has to wait a long time to be "compensated" for when was patient in favor of others. Hence, we also provide a general bound on 1 E'-1 ENi, b,,,, E { R., (4)), for positive (b,,.. } that specified below. Using this bound, the first part of Theorem 2 assumes fixed epoch length E

---

and that X E CeN (g) for E in (5), so À is far enough from the boundary of C (g). In this case, obtain lim sup, 2 Em= E (R, (t) < oc, so the empirical average of the expected QoS T-
regret of any agent is O (1). In the queuing literature, these stability notions are known as mean rate stability (i.e., sublinear expected QoS regret) and strong stability.
aalti-armed bandit game, played for T tuns. Let X E C Let the agents run Algorithm I with a row-stochastic W, connected G with diameter d (G), epochs of length E,, a random subset of action profiles of size SE S [So log E for some So > and 1.s Define the set of approximately optimal action profiles
Theorem 2. Let 9 be multiplayer
DE 2 d()). Let bag = [WDDe),,
N
N
log E v E
A" (a) = a
Onlon (a) 2 max
Onlin (a')
(4)
n2
12
and
8p min A (ca)
33 (So + 1) log E
DE
Eg
+ E
+ E
(5)
VE
Define
(A, = max min Ep (a) (a) An EB
(6)
PEARN
If X Cer (G) then the QoS regrets (Definition 2) satisfy
T-1 N
(2+ E
bE (Rn, (t) S 6),,E)
1=0==
where E {-} is over the rewards and the random subsets, and b >> 0 for all n.
Therefore, for any X Oeg (9), Algorithm achieves O (1) empirical average expected QoS regret for all n ,i.e. sims Ei-> E (Bn (1)} < os (strong stability) and E (Rn, (1) = O (Vi) T-xx0
for all n, t. Furthermore, if we pick Er such that Ex + Do and ET - 0 as T - oo, then for any E C Algorithm 1 achieves + ETD Σn (Rn (t)} O (Er) for all and (R., (t)) = (VErt) for all n, t (mean rate stability).
4 QoS Regret Stability Analysis
In this section, we break our analysis required to prove Theorem into lemmas and postpone the proofs to the appendix. The proof technique is inspired by the optimality proof of max- max-weight matching [25]. However, the QoS regret R, (t) does not behave like a standard queue. The main difference is that the service rate of agent which is its reward function, is not selected by centralized decision-make maker but is a function of the actions of the distributed agents. As opposed to standard queue, the "backlog" of the QoS regret is not sufficient statistic, since one has to remember Ant D I' (T) even if R,, (t) O. Since X,t D In (T) can get very negative "empty queues" (R,, (1) = 0) are much more likely in our problem. As we discuss in Section in the appendix, this fact be used improve the scalability of our algorithm, since agents with RR, (t) = O can be thought of as "passive". Moreover, our "arrival process" is deterministic, of An 1 reward points every turn for agent n, and the backlog is not an integer. As detailed next, some of these differences require careful analysis or affect the algorithm design. For example, while sublinearly increasing queue (in 7') is not strongly stable, in our case, as long as (T) > 0, agent n will asymptotically achieve its desired QoS in the empirical average sense.
T
Definition Define the matrix B = WDs,, , and denote its (i.j) element by big-- Define the following Lyapunov function such that L (0) = 0 and for all t >
N
L (())
b R& (1).
(8)
n=1
7

---

L (t) only uses the coefficients of Agent since all agents, that know their IDs, agree on the weighted sum of rewards that Agent sees. This forced agreement ensures that all agents will use the exact same weighted sum of rewards. However, Agent 1 does not know more than others and can be replaced by any of them.
The first lemma bounds the Lyapunov drift in each turn.
Lemma 1. The Lyupunov drift lurn 2 0 satisfies:
1t L (t) - 1+2 br. (t) (An, rn (a (t 1)))
(9)
The proof of Theorem 2 follows by upper bounding (L) - E (O)), where smaller bound implies smaller QoS regrets. The expectation (over the reward) of the upper bound of Lemma is minimized by the maximum weight matching a" (t 1) = arg max Σn bI,n (t) pm (a). The
two main obstacles our algorithm has to overcome to approximate max-weight matching the distributed nature the agents, and the unknown reward functions (bandit feedback). Distributed agents cannot deduce a" (t + 1) instantly every turn since they need time to agree the weighted sum of rewards. For this reason, our algorithm works in epochs. Working in epochs means that our algorithm treats the QoS regret R,, (t) as constant on its initial value R. - R, (Te - 1) throughout epoch e. The agents then aim to solve the following problem instead in every epoch
N
a = arg I11X
b Ry pn (a).
(10)
The next lemma bounds the resulting enror from solving (10) instead of the max-weight matching. Lemma 2. Define e (f) as the epoch such that Te(t) StS Te(t) +
Then
T ΣΣ
T-1
N
bLm (ai(t) (e(()
binntin (a" (t + 1)) R. (t) ETTaxA (11)
t=0 n=1
x=
In addition to solving (10) instead of the max-weight matching, working in epochs incurs an additive error of O (ET) again while replacing R, (t) with R. while bounding the drift in (9).
The other loss of Algorithm stems from learning a with bandit feedback. While dividing into epochs creates an additive error of O (ET), learning the optimal action profile a creates a multi- plicative error, so the larger the QuS regrets R, are, the larger this error is.
For this reason, we need to employ an algorithm that achieves sublinear regret in learning a Algorithm induces successive climination on random subset of Sg action profiles, with bi, Rr (a) as the reward function. The next lemma bounds the error (regret) of this successive elimination. Since agents only agree E bi R1 (a (f)) after 2Dg turns, successive elimination suffers from delayed feedback. While not our focus, we chose successive elimination over UCB since it is more robust to delays, as was shown in [29]. The restriction to random subset of Sg action profiles is done to improve scalability, but it leads to a worse regret than in the single-agent agent standard multi-armed bandits. Nevertheless, the regret is still sublinear in E and therefore good enough to prove our QuS regret bounds.
Lemma 3. Let Rt, = Rí (To 1) and define the set of approximately optimal action profiles as
Σm=1 EN Rs
Ri,HR (a)
Σn b1,n R,, (a')
log E
A
max a²
(12)
ΣN bI,n Rs
VE
Let at maintains
A
Define the filtration F. a ((a (1), (zn (1)DEN 1 << TT))).
Then Algorithm
T T 1
N
E
bi Rr (pn (a.) - (a 1))) Fe
n=1
33 (So 1og EVE 2Dg + E Sol4"1
Σ
b R
(13)
where E |Fe is over the rewards and the e-th subset of action profiles.
8

---

(e.g., of = 0.2). As a result, A is larger than the maximal skill of 5 Numerical Simulations
Our algorithm useful in any case where cooperative agents need to achieve a target QoS over time. Next, we tested our algorithm for wireless channel access and multitasking robots, two applications where smart time-sharing can significantly improve performance. For each experiment, we plot the sum of QoS regrets averaged over 100 realizations with one standard deviation shaded region.
5.1 Wireless Channel Access
Consider N devices and K channels, such that each device can choose to transmit packet on channel k 2 by playing a, k or not transmit at all by playing on = We consider "soft collisions" model where the success probability of transmitting a packet for device on channel k Sm..
is P 1+ I+
2 9m. [(m==k] for some channel gains {gn,m) ) and {9 This model generalizes the collision model [12, 14, 15], where multiple devices that pick the same channel all receive zero reward. As in practice, the geometry of the devices dictates how much they interfere with each other.
Fig. I(a) shows the sum of QoS regrets over time for N and K = We used SF
128, d (G) = 3 and E = 50SF. The channel gains were 91,4 91,3 92,4 93.2 0 and 91.2 = 93.4 100 such that In.m = Im.n for all m, and gî,1 = -2.2 = =93_3
94,4 = 0.1,
9i.1 02.2 = 93.33 -4,1 1. Hence devices and 2 are in proximity, and devices 3 and 4 are also in proximity, but far away from and 2. Then, devices 1 and 2 prefer channel & = 1 while devices X,, 0.499 for all n, which cannot be achieved with a static solution, but only if devices 1 and transmit simultancously each on their preferred channel. and in the next turn devices 2 and 4 do the same, and in round-robin manner. After a while, the QoS regrets stabilized on low values.
3 and 4 prefer channel & = 2. The QoS vector
Fig. 1(b) shows the sum of QoS regrets over time for N = 100 and K = 2 (one channel). The channel gains {gn, } and { {gh.n] were chosen independently and uniformly at random on [0, 1].
We used 5g = 104, E 5.5g, and d (G) = 4. The QoS of agent n was A, = 1.9 00.02 90% more than what almost perfect time-sharing can achieve. The stability of the QoS regrets is again evident, in agreement with the theory. Note that while there are KN = 2000 action profiles, considering only random subset of S 1 action profiles enough achieve this QoS.
N which
5.2 Multitasking Robots
Consider N robots and K = N tasks, such that the n-th robot is in charge of the n-th task. Each robot n has a skill of s for the k-thh task. Each turn, each robot can choose to work on the k-th task by playing an k. The reward of robot n is (a) - > {a.,, 3 8 + An, which models the rate at which this task progresses, where 2n is uniform noise on [-0.2, 0.2] that is i..d. over time and independent between agents. Hence, only one robot can measure the progress of certain task, but the others can still assist.
Fig. 2(a) shows the sum of QoS regrets time for N K = 4. We used E 5K
5120, (G)
3.
The QoS vector was A (0.8, 0.2,0.42 0.4) and the skill matrix was
0.5
0.4
0.2
0.2
0.5
0.4
0.2
0.3
0.25
0.5
0.6
0.3
0.25
0.4
0.2
0.6
a single robot so the robots had to cooperate on their tasks to achieve this QoS vector, Additionally, no static solution can support this A.
Fig. 2(b) shows the sum of QoS regrets for N and K 8. We used Se 1000, d dGG) and E 10Sg, A= (0.83, 0.79, 0.78, 0.71, 0.85, 0.76, 0.74, 0.86) and picked s uniformly and independently at random on (0.2, 1]. Note that while there are N = 8 action profiles, considering only random subset of S5: 10 action profiles was enough achieve this QoS.
In both figures, the sum of QoS regrets increases slowly with T, which for traditional queue would mean no strong stability but in our case means that the empirical average rewards converge to A.

---

10000
23000
6000
4000
10000
5000
200000
400000
620003
300000
1000000
1200003
0
200000 400000 G00030 800000 100300220003000000000
tine
tie
Figure 1: Sum of QoS regrets: channel access, N = 4, K = 3 (left) and N = 100, = 22 (right)
120000
300000
40000
00000
20000
20000
500000
1000300
1500000
2000000
2500003
3000000
250000 30000
20000000000000000000000000000000 Lms
Ene
Figure Sum of QoS regrets: multitasking robots, N = 4 (left) and N = 8 (right)
6 Conclusion
We studied how a team of agents can improve the Quality Service (QoS) of each by inducing dynamic behavior between them. The main observation that inspired our algorithm is that the QoS regret of each agent behaves like a queue. Then, our distributed algorithm learns to approximate max-weight matching of agents to actions to maximize the "throughout" going out of these virtual queues, that end, our algorithm works in epochs and employs simultaneous consensus averag- ing and distributed successive elimination feedback. Our main result shows that our algorithm can achieve all QoS vectors in the capacity region for large enough T,, where all agents have an empirical average expected QoS regret of Ó (1) over time which never exceeds (vt) for any t. Simulations demonstrate the effectiveness of our algorithm for channel access in wireless networks and multitasking robots.
random subset of action profiles and with delayed
We then extended our result for stochastic communication graphs that are i.i.d. over time. The com- munication graphs create dependencies between the rewards of the "arms" (i.c., action profiles) over time. While we were able to bypass these dependencies for the i..d. case, a Markov graph process, for example, will lead to restless bandits scenario instead where successive elimination does not work. While in principle it is easy to replace the successive elimination part of our algorithm, the new bandit algorithm will have be distributed, ideally with small communication overhead.
We considered an arbitrary discrete game where an exhaustive search necessary find an ap- proximately optimal action profile. However, applications often focus on more structured games. For example, in congestion games, best-response dynamics are guaranteed to converge to a Nash equilibrium. Hence, if a congestion game is designed such that all Nash equilibria are efficient, an exhaustive search is not needed [30]. Alternatively, the agents can directly solve their combinatorial optimization problem as team, leveraging its structure. Examples are the assignment problem, unconstrained submodular minimization, and shortest path [31]. Then the challenge is to design a distributed algorithm solve the combinatorial optimization based only on bandit feedback.
Our work introduces an analogy between multiagent QoS and queuing. By further studying this analogy we can leverage more tools from queuing theory to design dynamic distributed learning algorithms with strong performance guarantees. For example, scheduling algorithms with delay guarantees [32] can help to design QoS multiagent algorithms with better delay performance. An- other example to employ the "drift plus penalty" technique [25] to optimize an objective such as the sum of rewards while still guaranteeing some QoS for all agents.
10

---

References
[1] L. Tassiulas and A. Ephremides, "Stability properties of constrained queueing systems and scheduling policies for maximum throughput multihop radio networks," IEEE Transactions on Automatic Control, vol. 37, no. 12, pp. 1936-19488 1992.
[2] S. Krishnasamy, R. Sen, R. Johari, and S. Shakkottai, "Regret of queueing bandits," CoRR, abs/1604.06377, 2016.
[3] T. Stahlbuhk, B. Shrader, and E. Modiano, "Learning algorithms for minimizing queue length regret," IEEE Transactions on Information Theory, vol. 67, no. 3, pp. 1759-1781, 2021.
[4] K. Winner, G. Bernstein, and D. Sheldon, "Inference in partially observed queuing model with applications in ecology," in International Conference on Machine Learning. PMLR,
2015. pp. 221202220.
[5] S. Krishnasamy, A. Arapostathis, R. Johari, and S. Shakkottai, "On learning the ep rule in single and parallel server networks," in 2018 56th Annual Allerton Conference on Communi- cation, Control, and Computing (Allerton). IEEE, 2018, pp. 153-154.
[6] R. Hassin and M. Haviv, To queue or not to queue: Equilibrium behavior in queueing systems. Springer Science Business Media, 2003, vol. 59.
[7] S. Bubeck and T. Budzinski, "Coordination without communication: optimal regret in two players multi-armed bandits," Conference on Learning Theory. PMLR, 2020, pp. 916- 939.
[8] 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. PMLR, 2020, pp. 961-987.
[9] S. Bubeck, T. Budzinski, and M. Sellke, "Cooperative and stochastic multi-player multi-armed bandit: Optimal regret with neither communication nor collisions," in Conference on Learning Theory. PMLR, 2021, pp. 821-822.
[10] E. Boursier and Perchet, "Selfish robustness and equilibria in multi-player bandits," in Con- ference on Learning Theory. PMLR, 2020, pp. 530-581.
[11] I. Bistritz and N. Bambos, "Cooperative multi-player bandit optimization," Advances in Neural Information Processing Systems, vol. 33, 2020.
[12] E. Boursier and V. Perchet, "SIC-MMAB: synchronisation involves communication in multi- player multi-armed bandits," " in Advances in Neural Information Processing Systems, 2019, pp. 12 048 057.
[13] Alatur, K. Y. Levy, and A. Krause, "Multi-playee" bandits: The adversarial case," Journal of Machine Learning Research, vol. 21, p. 77, 2020.
[14] I. Bistritz and A. Leshem, "Distributed multi-player bandits-a game of thrones approach," in Advances in Neural Information Processing Systems, 2018, pp. 7222-7232.
[15] M. K. Hanawal and S. Darak, "Multi-player bandits: A trekking approach," IEEE Transactions on Automatic Control, 2021.
[16] D. Kalathil, N. Nayyar, and R. Jain, "Decentralized learning for multiplayer multiarmed ban- dits," IEEE Transactions on Information Theory, vol. 60, no. 4, pp. 2331-2345, 2014.
[17] Rosenski, O. Shamir, and L.. Szlak, "Multi-player bandits-a musical chairs approach," in International Conference Machine Learning. PMLR, 2016, pp. 155-163.
[18] I. Bistritz, T. Z. Baharav, A. Leshem, and N. Bambos, "One for all and all for one: Distributed learning of fair allocations with multi-player bandits." IEEE Journal on Selected Areas in In- formation Theory, vol. 2, no. 2, pp. 584-598, 2021.
[19] Sentenac, Boursier, and V. Perchet, "Decentralized learning in online queuing systems," Advances in Neural Information Processing Systems, vol. 34, pp. 501-118 2021.
[20] D. Freund, T. Lykouris, and W. Weng, "Efficient decentralized multi-agent learning in asym- metric queuing systems," arXiv preprint arXiv:2206.03322. 2022.
[21] G. J. Foschini and Z. Miljanic, "A simple distributed autonomous power control algorithm and its convergence," IEEE transactions on vehicular Technology, vol. 42, no. pp. 641-646, 1993.
11

---

[22] A. Slivkins, "Introduction to multi armed bandits," arXiv preprint arXiv:1904.07272, 2019.
[23] S. Rakhlin and K. Sridharan, "Optimization, learning, and games with predictable sequences," Advances in Neural Information Processing Systems, vol. 26, 2013.
[24] C.-Y. Wei and H. Luo, "More adaptive algorithms for adversarial bandits," in Conference On Learning Theory. PMLR, 2018. pp. 1263-1291.
[25] M. J. Neely, "Stochasticc network optimization with application to communication and queue-
ing systems," " Synthesis Lectures on Communication Networks, vol. 3, no. 1, pp. 1-211, 2010.
[26] A. Nedić and J. Liu, "Distributed optimization for control," Annual Review of Control, Robotics, and Autonomous Systems, vol. no. pp. 77-103, may 2018.
[27] K. I. Tsianos, S. Lawlor, and M. G. Rabbat, "Consensus-basee distributed optimization: Prac- tical issues and applications large-scale machine learning." " in 2012 50th annual allerton conference commanication, control, and computing (allerton). IEEE, 2012, pp. 1543- 1550.
[28] Chung and Lu, "The diameter sparse random graphs," Advances Applied Mathemat- ics, vol. 26, no. 4, pp. 257-279, 2001.
[29] T. Lancewicki, S. Segal, T. Koren, and Y. Mansour, "Stochastic multi-armed bandits with unrestricted delay distributions." arXiv preprint 2XXi:22006002436, 2021.
[30] D. Paccagnan, R. Chandan, B. L. Ferguson, and J. R. Marden, "Incentivizing efficient of shared infrastructure: Optimal tolls in congestion games," arXiv preprint arXiv:1911.09880 2019.
[31] K. Bernhard and J. Vygen, "Combinatorial optimization: Theory and algorithms," Springer, Third Edition, 2005., 2008
[32] M. J. Neely, E. Modiano, and C. E. Rohrs, "Dynamic power allocation and routing for time varying wireless networks," in IEEE INFOCOM 2003. Twenty-second Anmual Joint Confer- ence of the IEEE Computer and Communications Societies (IEEE Cat. No. 03CH37428), vol. 1. IEEE, 2003, pp. 745-755.
[33] Y. Zhu and R. Nowak, "On regret with multiple best arms," arXiv preprint arXiv:2006, 14785, 2020.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Limitations of the model are described in Section 2 and Section 3, and some mitigation is suggested in Section 7. (c) Did you discuss any potential negative societal impacts of your work? [N/A] As theory paper, the negative societal impacts are rather ambiguous.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes] All the details of our algorithm plement so no code is provided (given the instructions we do provide, it is not needed to reproduce the results). Section 5 includes all the details needed to reproduce the numerical experiments, which are of secondary importance since they are only meant validate the theoretical findings.
provided in Section 3. The algorithm is extremely simple to im-
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] The simulations can be easily on personal computer.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "wgHlxISSGxo", "reviewer": "Reviewer_2EXT", "summary": "The paper examines the problem of multi-agent bandits (with given initial actions) from a distributional (i.e. decentralized) point of view, in which the actions result in an optimal matching to agnostic agents. \nThe formulation belongs to the area of optimization using a game theory setting \nand, in their randomized technique, the authors suggest in each round the selection of a subset of available strategies. \nThe invariant of their algorithm in every iteration is the maximization of the expected (weighted) utility.\nFor the complexity of the algorithm, there is an upper bound in the expected utility which suffices as a guarantee in the chosen count of shared messages (O(communication graph's diameter)).", "questions": "Some questions were posed in the 'Weaknesses' section. Also: \n1. Is the set of actions common for all players (e.g. lines 90 and 191)? Therefore, is the difference located in the different rewards?\n2. Is the right hand side of (13) of O(communication graph's diameter)?\n3. How is parameter 'E' selected before (and during) Algorithm 1? \n4. Could the authors make a more direct comment on the individual accumulated Regret R(t) 'behaving like a queue' and the stability? I am not sure there is a theorem of queuing theory fashion here. \n5. Is the set of sets of approximately optimal action profiles reducing to a particular complexity class of games?\n", "limitations": "The paper has a theoretical character and aspires to suggest a complexity result through an optimization model. Given that this is a conference about Learning and related fields, \naccording to my opinion,\nthe authors are encouraged to involve a comment and designate how the optimization iterations of their algorithm track a learning course/task (e.g. based on some dataset) both in their model and in the 2 numerical simulations of this process.\n\nPOST REBUTTAL: After reviewing the authors' response to all reviewers and after the discussion with the other reviewers, I decided to increase my score to 'Accept'. It seems that the authors submitted an improved version of the Supplementary Material, with enhanced parts on the example of graphs with reference to time evolution. It seems that their effort used to create a novel work is reflected on their paper and answers.  \n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The formulation involving the suggested algorithm seems to be a novel model; the paper employs a method which doesn't seem to be already explored in this multiplayer setting for the purpose of achieving a feasible Quality of Service with a sublinear expected regret.\n\nThere are arithmetic examples of the model which demonstrate and strengthen the applicability of its theory.\n\nIt describes the problem of the reward maximization both with an intuitive and a rigorous way, which allows the reader to follow the developed model.\n\nIt seems technically sound, it involves a scalability part which makes it more realistic than a theoretical construction and it has the interesting idea/trick of the search to a limited random subset of action profiles. From a first reading, there doesn't seem to be any missing step or error in the proofs.\n\nWeaknesses: 1. Learning fashion could be discussed. The examples focus in the convergence of the algorithm to \\lambda. Is that the (machine) 'learning' context of the model? For example, would there be any setting using data (instead of random initial values) for the \\lambda inference or the learning of any other parameter? \nIt seems that the assumptions of p_n_k in 5.1 'help' the example to validate the model (although this is in enough as a sanity check for a new model; yet it also seems to restrict it).\n\nA possible interpretation is that the model belongs to Unsupervised Learning; in each epoch the regret is assessed (not in a gradient based way).\n\n2. Impact could be discussed. Could the authors elaborate on the impact of this model in comparison to existing models of bandits. The paper lacks any kind of comparisons to existing models, e.g. about the complexity of its algorithm, the convergence speed, any other metrics that exhibit superiority. Are there any such justifications of better results that make this algorithm needed? How is this model guaranteeing stability  of the QoS regrets differently from other algorithms?\n\n\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ZGaDnFOki2t", "reviewer": "Reviewer_1eJN", "summary": "The paper considers a system of $N$ cooperative agents who are trying to maximize their rewards in an online learning setting lasting $T$ time steps. Every agent's reward depends on the actions taken by all agents and not merely its own action, resulting in a multi-player MAB setting. Agents are allowed to communicate only over a fixed communication graph\n\nThe paper proposes an algorithm that attempts to mimic the celebrated MaxWeight algorithm, albeit in a decentralized manner, to ensure sublinear regret.", "questions": "\n1. The term \"stability\" needs to be defined in Sec. 2. The authors talk about stabilizing the regret queues without formally defining the term. Can you bring the definitions of strong stability and mean rate stability to Sec. 2?\n\n2. Regarding the definition of the capacity region in Eqn. 2, I'm a bit concerned about the fact that $C_{\\epsilon}$ doesn't seem to depend on the interference graph. \n- Please correct the LHS of the definition to $\\sum_a p(\\mathbf{a})$ instead of $\\sum_a \\mathbf{p}(\\mathbf{a})$. $\\mathbf{p}$ is a vector, $p(\\mathbf{a})$ is a scalar.\n- Also, (I might be mistaken here) shouldn't the RHS of the inequality be \"$\\geq \\lambda_n-\\epsilon$\" instead of \"$> \\lambda + \\epsilon$\"?\n\n3. On line 132, shouldn't that be $r_n(\\mathbf{a}(t))$?\n\n4. Please refer to Lemma 2 somewhere in Lines 138-140.\n\n5. I'm still not very clear about the tradeoffs that $E_T$ brings in. Regret scales with $\\sqrt{TE_T}$, so it needs to grow strictly slower than  $T,$ but what lower bounds its rate of growth (I'm guessing delay)? \n\n6. Communication graphs can change with time. T&E have a modified MaxWeight protocol for this as well, called \"Serve the Longest Connected Queue.\" Is there any possibility of leveraging this protocol to extend your analysis to include a time varying topology?", "limitations": "The work is theoretical and I don't see any potential negative societal impact.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper is well motivated, although concrete motivation is provided only in Sec. 5. I strongly recommend that the authors improve the explanation above Sec. 1.1 and situate the problem better.\n2. I like the approach taken by the authors. MWM has been a mainstay in networking and its usage in solving multi-player MAB algorithms is very interesting.\n3. The paper nicely follows Tassiulas and Ephremides's article, providing a capacity region, a (distributed) algorithm and stability guarantees. In my opinion, the discussion seems well rounded.\n\nWeaknesses:\n1. While the authors' attempt at introducing queueing and MW-related concepts to the machine learning community is laudable, I personally don't find much originality in either the algorithm or its analysis. \n\nConsensus algorithms and approximate MWM have been proposed and analyzed in various scenarios in the past. The present algorithm doesn't appear to be more than a rehash of standard decentralized MWM with standard action elimination.\n\n2. In fact, even the Lyapunov function is not non standard. Eqn (8) is the usual weighted 2-norm of the system backlog, and the proof of Lemma 8 (on pp 14) doesn't appear to contain anything surprising.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "KkmjoiBa-Z", "reviewer": "Reviewer_NWYo", "summary": "Let $L(a, n) := \\lambda_n - r_n(a)$. \nThis paper consider the minimax problem $p = \\arg\\min_{p \\in \\Delta(a)} \\max_n L(a, n)$ (This equivalence holds when the regret is non-negative). \nThe authors propose an algorithm to solve the above problem under the distributed setting, where $a = (a_1, \\ldots, a_N)$ is chosen by $N$ cooperative agents.\nParticularly, $p$ is approximated through $T$ deterministic distribution, i.e., $p \\approx \\frac{1}{T}\\sum_{t=1}^T \\delta_{a^t}$.", "questions": "The powerful tools in the literature of matrix game are missed, which can help improve the results greatly.", "limitations": "The powerful tools in the literature of matrix game are missed, which can help improve the results greatly.", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The above mentioned minimax problem is generally known as matrix game, which can be solved efficiently through the EXP3 algorithm with full observations, and the EXP3-IX algorithm with partial observations (see the book \"Bandit Algorithms\" for details).\nThe above two algorithms both have the regret bound $\\widetilde{O}(\\sqrt{K^NT})$, which is much better than Theorem 2, and holds under a broader condition when $\\lambda \\in C(\\mathcal{G})$.\nThe authors should incorporate the missing powerful tools into the distributed setting to improve their results.\nMoreover, the OMWU and PU algorithms in the literature of matrix game may help improve the $\\sqrt{T}$-regret to $\\log(T)$-regret.\n\nThe authors may also discuss the possibility to avoiding the exponential dependence on $N$ based on the potential game or other models.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept