Decentralized Learning in Online Queuing Systems
Authors: Flore Sentenac
Etienne Boursier
Vianney Perchet
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Queuing systems
Decentralized Learning
Multi-armed Bandits

Abstract: Motivated by packet routing in computer networks, online queuing systems are composed of queues receiving packets at different rates. Repeatedly, they send packets to servers, each of them treating only at most one packet at a time. In the centralized case, the number of accumulated packets remains bounded (i.e., the system is stable) as long as the ratio between service rates and arrival rates is larger than $1$. In the decentralized case, individual no-regret strategies ensures stability when this ratio is larger than $2$. Yet, myopically minimizing  regret disregards the long term effects due to the carryover of packets to further rounds. On the other hand, minimizing long term costs leads to stable Nash equilibria as soon as the ratio exceeds $\frac{e}{e-1}$. Stability with decentralized learning strategies  with a ratio below $2$ was a major remaining question. We first argue that for ratios up to $2$, cooperation is required for stability of learning strategies, as  selfish minimization of policy regret, a patient notion of regret, might indeed still be unstable in this case. We therefore consider cooperative queues and propose the first learning decentralized algorithm guaranteeing stability of the system as long as the ratio of rates is larger than $1$, thus reaching performances comparable to centralized strategies.

Decentralized Learning in Online Queuing Systems
Flore Sentenac" CREST, ENSAE Paris, Palaiseau, France flore. www.ssecogaaaailcccmmmm com
Etienne Boursier"
Centre Borelli, ENS Paris-Saclay, France etienne. wwwursieer@gmn @rgmmmill com
Vianney Perchet
CREST, ENSAE Paris, Palaiseau, France CRITEO AI Lab, Paris, France vianney. perchet www.maeesu.............uuummu org
Abstract
Motivated by packet routing in computer networks and resource allocation in radio networks, online queuing systems are composed of queues receiving packets different rates. Repeatedly, they send packets to servers, each of them treating only at most one packet a time. the centralized case, the number of accumulated
packets remains bounded (i.e., the system is stable) as long as the ratio between service rates and arrival rates is larger than In the decentralized case, individual no-regret strategies ensures stability when this ratio is larger than 2. Yet, myopically minimizing regret disregards the long term effects due to the carryover of packets to further rounds. On the other hand, minimizing long term costs leads to stable Nash equilibria as soon as the ratio exceeds e Stability with decentralized learning strategies with a ratio below was major remaining question. We first argue that for ratios up to 2, cooperation is required for stability of learning strategies, selfish minimization policy regret, a patient notion of regret, might indeed still be unstable in this case. We therefore consider cooperative queues and propose the first learning decentralized algorithm guarantecing stability of the system as long as the ratio of rates is larger than 1, thus reaching performances comparable to centralized strategies.
Introduction
Inefficient decisions in repeated games can stem from both strategic and learning considerations. First, strategic agents selfishly maximize their individual reward at others' expense. The price of anarchy (Koutsoupias and Papadimitriou 1999) measures this inefficiency as the social welfare ratio between the best possible situation and the worst Nash equilibrium. Although reaching the best collective outcome might be illusory for selfish agents, considering the worst Nash equilibrium complex interactions intervene and
might be too pessimistic. In games with external factors, might lead the agents to the best equilibrium. Instead, the price of stability (Schulz and Moses] 2003 measures the inefficiency by the social welfare ratio between the best possible situation and the best Nash equilibrium.
Second, the agents also have to learn their environment, by repeatedly experimenting different outcomes. Learning equilibria in repeated games is at the core of many problems in computer science and economies (Fudenberg et al. 1998 Cesa-Bianchi and Lugosi| 2006). The interaction between multiple agents can indeed interfere the learning process, potentially converging to no or bad equilibria. It is yet known that in repeated games, if all agents follow internal regret strategies, their actions converge in average to the set of correlated equilibria [art and Mas-Colell, 2000 Blum and Monsour 2007 Perchet 2014).
Equal contributions
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Many related results are known in the classical repeated games [see e.g., Dasa-Bianchi and Lugosi 2006 Roughgarden 2010], where single game is repeated over independent rounds (but the agents strategies might evolve and depend on the history). Motivated by packet routing in computer networks, Gaitonde and Tardos (2020a] introduced repeated game with a carryover feature: the outcome of round does not only depend on the actions of the agents, but also on the previous rounds. They consider heterogeneous queues sending packets to servers. If several queues simultaneously send packets to the same server, only the oldest packet is treated by the server.
Because of this carryover effect, little known about this type of game. In a first paper, Gaitonde and Tardos 2020a] proved that if queues follow suitable no-regret strategies, a ratio of 2 between server and arrival rates leads to stability of the system, meaning that the number of packets accumulated by each queue remains bounded. However, the assumption of regret minimization sort of reflects a myopic behavior and is not adapted to games with carryover. Gaitonde and Tardos [2020b] subsequently consider patient game, where queues instead minimize their asymptotic number of accumulated packets. A ratio only larger than - then guarantees the stability of the system, e-i
while a smaller ratio leads to inefficient Nash equilibria. As a consequence, going below the e-1 factor requires some level of cooperation between the queues. This result actually holds with perfect knowledge of the problem parameters and it remained even unknown whether decentralized learning strategies can be stable with a ratio below 2.
We first argue that decentralized queues need some level of cooperation to ensure stability with a ratio of rates below 2. Policy regret can indeed be seen patient alternative the regret notion. Yet even minimizing the policy regret might lead to instability when this ratio is below 2. An explicit decentralized cooperative algorithm called ADEQUA (A DEcentralized QUeuing Algorithm) is thus proposed. It is the first decentralized learning algorithm guaranteeing stability when this ratio is only larger than 1. ADEQUA does not require communication between the queues, but uses synchronisation between them to accurately estimate the problem parameters and avoid interference when sending packets. Our main result is given by Theorem below, whose formal version, Theorem in Section 4 also provides bounds on the number of accumulated packets.
Theorem 1 (Theorem informal). If the ratio between server rates and arrival rates is larger than 1 and all queues follow ADEQUA, the system is strongly stable
The remaining of the paper is organised as follows. The model and existing results are recalled in Section 2 Section 3 argues that cooperation is required to guarantee stability of learning strategies when the ratio of rates is below 2. ADEQUA is then presented in Section 4 along with insights for the proof of Theorem [ Section 5 finally compares the behavior of ADEQUA with no-regret strategies on toy examples and empirically confirms the different known theoretical results.
1.1 Additional related work
Queuing theory includes applications in diverse areas such as computer science, engineering, opera- tion research (Shortle et al., 20188 Borodii et al. 1996) for example use the stability theorem of Pemantle and Rosenthal| [1999], which was also used by Gaitonde and Tardos (2020b). to study the problem of packet routing through network. Our setting is the single-hop particular instance of throughput maximization in wireless networks. Motivated by resource allocation in multihop radio problem, packets can be sent through more general routing paths in the original problem. Tassiu- las and Ephremides) 1990) proposed a first stable centralized algorithm, when the service rates are known priori. Stable decentralized algorithms were later introduced in specific cases (Neely et al.) 2008 Jiang and Walrand 2009 Shah and Shin 2012). when the rewards X₂ (t) are observed before deciding which server to send the packet. The main challenge then is coordination and queues aim at avoiding collisions with each other. The proposed algorithms are thus not adapted to our setting, where both coordination between queues and learning the service rates are required. We refer the reader to Georgiadis et al. 2006 for an extended survey on resource allocation in wireless networks.
Krishnasamy et al. 2016) first considered online learning for such queuing systems model, in the simple case of a single queue. is a particular instance of stochastic multi-armed bandits, a celebrated online learning model, where the agent repeatedly takes an action within a finite set and observes its associated reward. This model becomes intricate when considering multiple queues, as they interfere when choosing the same server. It is then related to the multiplayer bandits problem which considers

---

multiple players simultaneously pulling arms. When several of them pull the same arm, a collision occurs and they receive no reward (Anandkumar et al.) 2010].
The collision model is here different as one of the players still gets a reward. is thus even more closely related competing bandits (Liu et al. 2020a b), where arms have preferences over the players and only the most preferred player pulling the arm actually gets the reward. Arm preferences are here not fixed and instead depend on the packets' ages. While collisions can be used as communication
tools between players in multiplayer bandits [Bistritz and Leshem 2018 Boursier and Perchet 2019
Mehrabian et al. 2020 Wang al., 2020]. this becomes harder with an asymmetric collision model as in competing bandits. However, some level of communication remains possible [Sankararaman
jtt al.) [2200] [asu et al., 202T]. In queuing systems, collisions are not only asymmetric, but depend
on the age of the sent packets, making such solutions unsuited.
While multiplayer bandits literature considers cooperative players, Boursier and Perchet 2020 showed that cooperative algorithms could be made robust to selfish players. On the other hand, competing bandits consider strategic players and arms as the goal is to reach a bipartite stable matching between them. Despite being cooperative, ADEQUA also has strategic considerations as the queues' strategy converges a correlated equilibrium of the patient game described in Section
An additional difficulty here appears as queues are asynchronous: they are not active at each round, but only when having packets left. This is different from the classical notion of asynchronicity [Bonefoo et al., 2017]. where players are active at each round with some fixed probability. Most strategies in multiplayer bandits rely on synchronisation between the players [Boursier and Perchet 2019] to avoid collisions. While such a level of synchronisation is not possible here, some lower level of synchronisation is still used to avoid collisions between queues.
2 Queuing Model
We consider queuing system composed of N queues and K servers, associated with vectors of arrival and service rates X, Jr, where at each time step f. = 1,2..... the following happens:
each queue i [N] receives new packet with probability A; E [0, 1], that is marked with the timestamp of its arrival time. If the queue currently has packet(s) on hold, it sends one of them to a chosen server based on its past observations.
Each server j E [K] attempts to clear the oldest packet it has received, breaking ties uniformly at random. succeeds with probability μJ E [o, 1] and otherwise sends it back its original queue, as well as all other unprocessed packets.
At each time step, a queue only observes whether or not the packet sent (if any) is cleared by the server. We note Qi the number of packets in queue at time f. Given a packet-sending dynamics, the system is stable if, for each in [N], Qi/t converges to 0 almost surely. is strongly stable, if for any r, è 2 O and i E [N], B[( < Cr, where C, is an arbitrarily large constant, depending on but not t. Without ambiguity, we also say the policy or the queues are (strongly) stable. Naturally, a strongly stable system is also stable [Gaitonde and Tardos 2020a].
In the following, zi()) will denote the i-th order statistics of a vector ær, i.e., A(1 2 A(2) 2 ... A(N) and ((1) 2 2 ((K)-- Without loss of generality, we assume K 2 (otherwise, we simply add fictitious servers with service rate). The key quantity of a system is its slack, defined as the largest
real number such that:
k
n
A ARS
i=1
We also denote by P ([K]) the set of probability distributions on [K] and by A the margin of the system defined by
& Σ (M -(())-
min RE[N] Te
Notice that the alternative system where ì, A + A and jis - μs has a slack 1. that sense, A the largest margin between service and arrival rates that all queues can individually get in the system. Note that if n) > 1, then A > O. We now recall existing results for this problem, summarized in Figure
D below.
3

---

Theorem 2 (Mrrhhal et al. 1979). For any instance. there exists strongly stable centralized policy and only if
Theorem 3 (Gaitonde and Tardos 2020a informal). 1f > 2, queues following appropriate regret strategies are strongly stable.
For each N >> 0, there exists system and dynamic 17 2 o(1/N), all queues follow appropriate no-regret strategies, but they are not strongly stable.
In the above theorem, appropriate regret strategy is a strategy such that there exists partitioning of the time into successive windows, for which the incurred regret is o (w) with high probability on any window of length w. This for example includes the EXP3.P. algorithm Auer et al. 2002] where the k-th window has length 2*.
The patient queuing game G = (c)) is defined as follows. The strategy space for each queue is P ([K]). Let p-; E (P (P((K))==Idenot denote the vector of fixed distributions for all queues over servers, except for queue The cost function for queue is defined as:
c. p.
lim /t/t,
t++20
where Tÿ is the age of the oldest packet in queue i at time t. Bounding Tद is equivalent to bounding Q Theorem (Gaitonde and Tardos 2020b informal). If > ف any Nash equilibrium of the patient game G is stable
Stable centralized strategies (Thm.)
Stable NE without learning (Thm.
No stable strategies
Stable no regret policies (Thm.
Stableddecentralized strategies (Thm.
0
2
Figure 1: Existing results depending on the slack r). Our result is highlighted in red.
3
The case for cooperative algorithm
According to Theorems and queues that are patient enough and select a fixed randomization over the servers stable over larger range of slack 7 than queues optimizing their individual regret. key difference between the two settings is that when minimizing their regret, queues are myopic, ...; to time / and let is (a1x)) be the indicator that it cleared a packet at iteration f. Classical (external)
which is formalized as follows. Let a1: (a1, [a1,...; ax) be the vector of actions played by queue up
regret of queue over horizon T' is then defined as:
R (T) = max
Σ Bas~pl (1 2.)1 - Σ (((a)))
(EP((K))
t=1
Thus minimizing the external regret is equivalent to maximizing the instant rewards at each iteration, ignoring the consequences of the played action the state of the system. However, in the context of queuing systems, the actions played by the queues change the state of the system. Notably, letting other queues clear packets subsequent iterations where it holds older packets. Since the objective is to maximize the total number of packets cleared, it seems adapted minimize patient version of the regret, namely the policy regret Arora el al. 2012), rather than the external regret, which is defined by
be in the best interest of queue, it may give it priority in the
T Ee (()x))) -E (((a))))
R (T)
max PEP([K)
That is, 12p00 is the expected difference between the number of packets queue i cleared and the number of packets would have cleared over the whole period by playing fixed (possibly random) action, taking into account how this change of policy would affect the state of the system.

---

However, as stated in Proposition I optimizing this patient version of the regret rather than the myopic one could not guarantee stability on wider range of slack value. This suggests that adding only patience to the learning strategy of the queues is not enough to go beyond slack of 2, and that any strategy beating that factor 2 must somewhat include synchronisation between the queues.
1.2.... into successive windows, where wa- = k2 is the length of the k-th one. For any N 2 2, there exists an instance with 2.N queues and servers, with slack 1l 2- O (+) s.t., almost surely, each queue's 's policy regret is o (wx) on all but finitely many of the windows, but the system is not strongly stable.
Proposition 1. Consider the partition of the time
To ease comparison, the formulation in the above proposition matches that of the counter-example used to prove Theorem 3 (Gaitonde and Tardos 2020a). In that counter-example, set of system parameters, for which any no external regret policies were unstable, was exhibited. Whereas we exhibit in our case specific strategy that satisfies the no policy regret condition, but is unstable.
Sketch of proof. Consider a system with 2N queues and servers with X; = 1/2N and μ4 = 1/N 1/4N² for all i [2N). The considered strategy profile is the following. For each k 2 0. the ht time window is split into two stages. During the first stage, of length [oww queues 2i and 2i + 1 both play server 2i + t (mod 2.N) iteration t, for all i [N]. During the second stage of the time window, queue plays server i ++ (mod 2N) at iteration t. This counter example, albeit very specific, illustrates well how when the queues are highly synchronised, it is better to remain synchronized rather than deviate, even if the synchronisation is suboptimal in terms of stability. The complete proof provided in Appendix C
Queues following this strategy accumulate packets during the first stage, and clear more packets than they receive during the second stage. The value of a is tuned so that the queues still accumulate a linear portion of packets during each time window. For those appropriate a, the system is unstable.
Now suppose that queue deviates from the strategy and plays fixed action first stage of each time window, queue can clear a bit more packets than it would by not deviating. However, during the second stage, it is no longer synchronised with the other queues and collides with them large number of times. Because of those collisions, it will accumulate many packets. In the detailed analysis, demonstrate that, in the end, for appropriate values of a, queue i accumulates more packets than it would have without deviating.
P ([K]). In the
According to Theorem 4. the factor - can be seen as the price of anarchy of the problem, as for slacks below, the worst Nash equilibria might be unstable. On the other hand, it is known that for any slack above 1, there exists a centralized stable strategy. This centralized strategy actually consists in queues playing the same joint probability each time step, independently from the number of accumulated packets. As a consequence, it is also correlated equilibrium of the patient game and 1 can be seen as the correlated price of stability.
A decentralized algorithm
This section describes the decentralized algorithm ADEQUA, whose pseudocode is given in Algo- rithm Due to space constraints, all the proofs are postponed to Appendix D ADEQUA assumes all queues a priori know the number N of queues in the game and have unique rank id in [N]. Moreover, the existence of shared randomness between all queues is assumed. The id assumption is required to break the symmetry between queues and is classical in multiplayer bandits without colli- sion information. On the other side, the shared randomness assumption is equivalent to the knowl- edge of common seed for all queues, which then use this common seed for their random generators. A similar assumption is used in multiplayer bandits [Bubeck et al. 2020].
ADEQUA is inspired by the celebrated e-greedy strategy. With probability & = (N + K)(- at each time step, queues explore the different parameters X; and (i; as described below. Otherwise with probability - ét, they exploit the servers. Each queue i then sends a packet to a server following a policy solely computed from its local estimates X², f² of the problem parameters À and μ. The shared randomness is here used so that exploration simultaneously happens for all queues. exploration/exploittion was not synchronized between the queues, an exploiting queue could collide with exploring queue, biasing the estimates X p of the latter.
5

---

Algorithm 1: ADEQUA
input: N (number of queues), E [M] (queue id)
for f 1,...,00 oc do
P + (AA, (i) and 1+-((P) where and v are resp. defined by Equations 3 and (4)
Draw W1 Bernoulli([N + K)t=b) and w2 10)
// shared randomness
if Wi = then EXPLORE(3)
// exploration exploitation
else Pull (1)
end
Exploration. When exploring, queues choose either to explore the servers' parameters μ4g or the other queues' parameters A; as described in Algorithm below. In the former case, all queues choose different servers at random (if they have packets to send). These rounds are used to estimate the servers means: iú the empirical mean of server is observed by the queue for such rounds. Thanks to the shared randomness, queues pull different servers here, making the estimates unbiased.
In the latter case, queues explore each other in pairwise fashion. When queues and explore each other at round t, each of them sends their most recent packet to some server k. chosen uniformly at random, if and only if packet appeared during round t. In that case, say that the queue explores X (and vice versa). To make sure that and are the only queues choosing the server l during this step, proceed as follows:
queues sample matching и between queues random. To do so, the queues use the same method to plan an all-mect-all (or round robin) tournament, for instance Berger tables [Berger] 1899), and choose uniformly at random which round of the tournament to play. the number of queues N is odd, in each round of the tournament,
queue remains alone and does nothing.
the queues draw the same number ~ U([{]] with their shared randomness. For each pair of queues (i,j) matched in æ,, associate k(s.)) = + min(i.j) (mod K) + this pair. The queues i and then send to the server k(i.))
As assumed that the server breaks ties in the packets' age uniformly at random, the queue clears with probability (1 A jz. where Jı 1 >kK K
Mk. Thanks to this, Xy is estimated by queue as:
X = = 2$
where Ø DK NEAL N is the number of exploration pulls of server l by queue and 83 is the ΣE_ No
empirical probability of clearing a packet observed by queue when exploring Ay.
Algorithm 2: EXPLORE
input:: E [N]
// queue id // shared randomness // explore
k 5-0
2 Draw n U(IN + KJ)
if n < K then
1: 4- n + (mod K) +
Pull k; Update N& and A
else
// explore X
Draw r ~ U(NN) and U(K))
// shared randomness
j +- th opponent in the all-meet-all tournament planned according to Berger tables
1 - 1 + min(i,j) (mod K) +
10
i & 0 and packet appeared at current time step then
// explore A, on server k
Pull with most recent packet; Update S, and 'n according to Equation 2
11
end
end
Remark 1. The packet manipulation when exploring AÚ strongly relies the servers tie breaking rules (uniformly at random). If this rule was unknown or not explicit, the algorithm can be adapted: when queue i explores Xj. queue j instead sends the pucket generated at time L- (if it exists), while queue still sends the packet generated at time I. that case, the clearing probability for queue exactly (1 - Tz, allowing to estimate Xj. Anticipating the nature of the round t (exploration vs.

---

exploitation) can be done by drawing wi ~ Bernoulli(Ee) at time t - 1. If w1 = 1, the round t is exploratory and the packet generated time 1 then kept apart by the queue j.
To describe the exploitation phase, we need few more notations. We denote by B k the set of doubly stochastic matrices (non-negative matrices such that each of its rows and columns sums to 1) and by K the set of permutation matrices in [K] (a permutation matrix will be identified with its associated permutation for the sake of cumbersomeness).
A dominant mapping is a function Φ IR- x R BB which, from (A,4), returns doubly stochastic matrix P such that X < (PH), for any E [N] if it exists (and the identity matrix otherwise).
ByN (Birkhoff von Neumann) decomposition is function vi : Bx + P(Gx) that associates to any doubly stochastic matrix P random variable th( such that Elp(()) P; stated otherwise, it expresses P as convex combination of permutation matrices. For convenience, we will represent this random variable as function from [0, 1] (equipped with the uniform distribution) to Gg.
Informally speaking, those functions describe the strategies queues would follow in the centralized case: a dominant mapping gives adequate marginals ensuring stability (since the queue i clears in expectation (Pμ)), packets at each step, which is larger than A, by definition), while BvN decomposition describes the associated coupling to avoid collisions. Explicitly, the joint strategy is for each queue to draw a shared random variable Wy Ld 1) and to choose servers according to the permutation ()(((,, (w2)
Exploitation. In a decentralized system, each queue i computes a mapping A' := ( (²)) solely based on its own estimates X jt. A shared variable w2 E [0, 1] is then generated uniformly at random and queue i sends packet to the server (T). If all queues knew exactly the parameters X, Jr. the computed strategies Å' would be identical and they would follow the centralized policy described above.
However, the estimates (}t, jit) are different between queues. The usual dominant mappings and BvN decompositions in the literature are non-continuous. Using those, even queues with close estimates could have totally different A', and thus collide a large number of times, which would impede the stability of the system. Regular enough dominant mappings and BvN decompositions to avoid this phenomenon. The design of & and io is thus crucial and appropriate choices are given in the following Sections I and Nonetheless, they can be used in some black-box fashion, so we provide for the sake of completeness sufficient conditions for stability, as well as general result depending on the properties of and v/, in Appendix A
required,
Remark 2. The exploration probability ビ gives the smallest theoretical dependency in A in our bound. A trade-off between the proportion of exploration rounds and the speed of learning indeed appears in the proof of Theorem / Exploration rounds have to represent small proportion of the rounds, as the queues accunulate packets when exploring. On the other hand, if queues explore more often, the regime where their number of packets decreases starts earlier. A general stability result depending on the choice of this probubilit given by Theorem 6 in Appendix A
Yet in Section 5 taking a probability t- empirically performs better as it speeds up the exploration.
4.1 Choice of a dominant mapping
Recall that a dominant mapping takes as inputs (A, ()) and returns, if possible, a doubly stochastic matrix P such that
A K -k=1 PLAME for all i e [N].
The usual dominant mappings sort the vector À and in descending orders Marshall et al. 1979). Because of this operation, they are non-continuous and we thus need to design regular dominant mapping satisfying the above property. Inspired by the log- barrier method, it is done by taking the minimizer of a strongly convex program as follows
1 PriMi 21) + 2K 1112
() = arg min max- In
(3)
PeBx (E[M]
7

---

Although the objective function is non mon-smooth because of the max operator, it enforces fairness between queues and leads to better regularity of the arg min.
Remark 3. Computing & requires solving non-smooth strongly convex minimization problem. This cannot be computed exactly, but good approximation can be quickly obtained using the scheme described in Appendix B If this approximation error is small enough, it has impact on the stability bound of ['Theorem 5 It is thus ignored for simplicity, i.e., we assume in the following that Φf Xx, 11) is exactly computed at each step.
As required, & always returns a matrix P satisfying that < Pi possible, since otherwise the objective is infinite (and in that case assume that ó returns the identity matrix). Moreover, the objective function is K -srrongly convex, which guarantees some regularity of the arg min, namely local-Lipschizzesss, leading
Cemmaabelons
Lemma 1. For any (2. p) with positive margin A (defined in Equation A, for any ei 2/042/ then
1 J. if (1(((2 X. -l)l S
C2K A
())(A))) 2)l22 S 11(A X, w)lloos
where 02 (1-2g)]/Ve22) Moreover, denoting P $(>, (1), it holds for any i E [N].
X A Pi.efle -
( (2-20 201
The first property guarantees that if the queues have close estimates, they also have close doubly stochastic matrices P. Moreover, the second property guarantees that any queue should clear its packets with a margin of order A, in absence collisions.
Remark 4. An alternative dominant mapping without the regularizing term in Equation ( can also be proposed. Yet, its local Lipschitz bound would also depend on the smallest difference between the >; or the pt, which can be arbitrarily small. If two parameters x or μa are equal, this choice of dominant mapping might lead to unstable policies. Using regularization term in Equation (3) thus avoids this problem, although a smaller dependency might be possible without this regularization term when the parameters x; and μr are very distinct.
4.2 Choice of a Birkhoff von Neumann decomposition
Given doubly stochastic matrix P, Birkhoff algorithm returns a convex combination of permutation matrices P[j] such that P = Σ, Pij] The classical version of Birkhoff algorithm is non- continuous in its inputs and it even holds for its extensions as the one proposed by Dufossé et al. [2018). Yet can be smartly modified in ORDERED BIRKHOFF, described in Algorithm get regular BvN decomposition defined as follows for any w E (0, 1):
(P)(w) P[in] where P= P[j is the decomposition returned by ORDERED BIRKHOFF algorithm
and in verifies
Σ < Σ zbi.
jSi+t1
For matrix P in the following, its support is defined supp(P) {(i,)) Pas # 0).
Algorithm 3: ORDERED BIRKHOFF
input:P E Bx (doubly stochastic matrix), C E kkkk K (cost matrix)
j
2 while P # 0 do
CiAb t +oo for all ki) & supp(P)
// remove edge (i,k) in induced graph matching with minimal cost w.r.t.
P[j HUNGARIAN(C)
z[j] + minp(i))esupp(P()) Pi.k
P -- p[j] and + j+l
end
8 return
(c11),P()))

---

Obviously Eu-, () [W)P) = P and permutations avoid collisions between queues. The difference with the usual Birkhoff algorithm happens Line Birkhoff algorithm usually computes any perfect matching in the graph induced by the support of p at the current iteration. This is often done with the Hoperoft-Karp algorithm, while it is here done with the Hungarian algorithm with respect to some cost matrix C. Although using the Hungarian algorithm slightly increases the computational complexity of this step (K instead of K225),, it ensures to output the permutation matrices P according to a fixed order defined below.
Definition 1. A cost matrix C' induces an order ze on the permutation matrices defined, for any P.P E Gx by
P P P if EngCrs < Eis
This order might be non-total different permutations have the same cost. However, if C' is drawn at random according to some continuous distribution, this order is total with probability 1. The order <c has to be the same for all queues and is thus determined beforehand for all queues.
Lemma 2. Given matrices C R KxK and P E Kx. ORDERED BIRKHOFF output sequence (=Ii), Pbi)ss of length at most K² - K + 1, such that
P= =b]Pb] where for all j. =[i] > 0 and Pbi E 6K.
Moreover if the induced order to is total, zli] the j-th non-zero element of the sequence (z(()))ssgk) defined by
j-1 P
(F
=
min (L.K)ss)pp(P))
(P-X
(P)))
(5)
where (Pi) <c-increasing sequence of permutation matrices, i.e. P3 <o for all j.
Lemma is crucial to guarantee the regularity of th, given by Lemma
Lemma 3. Consider va defined as in Equation with cost matrix C inducing a total order <c. then for any doubly stochastic matrices P
S.' (v(P)(w) + (PP) < - p'
Lemma indeed ensures that the probability of collision between two queues remains small when they have close estimates. Unfortunately, the regularity constant is exponential in K2, which yields similar dependency in the stability bound of Theorem The existence of BvN decomposition with polynomial regularity constants remains unknown, even without computational considerations. The design of better BvN decomposition is left open for future work and would directly improve the stability bounds, using the general result given by Theorem in Appendix A The number of accumulated packets yet remain reasonably small in the experiments of Section suggesting that the bound given by Lemma 3 is not tight and might be improved in future work.
4.3 Stability guarantees
This section finally provides theoretical guarantees on the stability of the system when all queues follow ADEQUA. The success of ADEQUA relies on the accurate estimation of all problem parame- ters by the queues, given by Lemma 9 in Appendix D.4] After some time the queues have tight estimations of the problem parameters. Afterwards, they clear their packets with margin of order A, thanks to Lemmas and 3. This finally ensures the stability of the system, as given by Theorem 5
Theorem 5. For any n > 1, the system where all queues follow ADEQUA, for any queue i and any r E N. there exists a constant C, depending only on r such that
N K (2222500-K+1) -K+""=++""""
B((O)) C.KN
for all N.
(min(1, Kū)A)* )
As a consequence, for any 1, this decentralized system is strongly stable.

---

Despite yielding an exponential dependency in K², this anytime bound leads to a first decentralized stability result when 7) E (1, ) which closes the stability gap left by previous works. Moreover can be seen in the proof that the asymptotic number of packets much smaller. It actually converges, in expectation, to the number of packets the queues would accumulate if they were following stable centralized strategy from the beginning. As already noted by Krishnasamy al. (2016) for single queue, the number of packets first increases during the learning phase and then decreases once the queues have tight enough estimations, until reaching the same state as the perfect knowledge centralized case. This is empirically confirmed in Section
5 Simulations
Figures 2 and compare on toy examples the stability of queues, when either each of them follows the no-regret strategy EXP3.P.1, or each queue follows ADEQUA. For practical considerations, we choose the exploration probability & (N + K)t- for ADEQUA, as the exploration too slow with Eg of order t 8.
These figures illustrate the evolution of the average queue length on two different instances with www.ee/eweninngntteeeeeeeeeeeeee N == K 4. The code for the experiments is available at http/laacoom/.seee/eeaaaaee
In the first instance shown in Figure 2 for all E [ A = (N + 1)/N2. Moreover μl1 = and for all i 2. μr (N 1) /N Here 7) < 2 and no-regret strategies are known to be unstable (Gaitonde) and Tardos 2020a It is empirically confirmed as the number of packets in each queue diverges when they follow EXP3.P.I Conversely, when the queues follow ADEQUA, after learning phase. the queues reach equilibrium and all succeed in clearing their packets.
In the second instance shown in Figure 3 for all E [V]. A 0.55 0.1 i and μ4; 2.11,, Here > 2 and both strategies are known to be stable, which is again empirically confirmed. However, ADEQUA requires more time to learn the different parameters, suggesting that individual no-regret
strategies might be better on easy instances where 7) > 2.
ADeQuA
Number of packets
Number of packets
EXP3.P.1
101
10P
101
10a
ADeQuA
EXP3.P1
0.8
1.0
0.2
0.4
Iteration
x10
Iteration
Figure 2: Hard instance, 2.
Figure 3: Easy instance, 1j >>> 2.
6 Conclusion
In this work, we showed that minimizing a more patient version of regret was not necessarily stable when the system's slack is smaller than two and we argued that some level of cooperation was then required between learning queues to reach stability. We presented the first decentralized learning algorithm guarantecing stability of any queuing system with slack larger than Our stability bound presents an exponential dependency in the number of queues and remains open for improvement, e.g., through better dominant mapping/BvN decomposition or tighter analysis of ours. The proposed algorithm relies heavily synchronisation between the queues, which all start the game simultaneously and share common time discretisation. In particular, the shared randomness assumption merely results from this synchronisation when the players use a common random seed. Stability of asynchronous queues thus remains open for future work, for which Glauber dynamics approaches used in scheduling problems might be of interest [see c.g., Shah and Shin 2012
10

---

Acknowledgements
Sentenac was supported by PARIS' PhD Funding. E. Boursier was supported by an AMX scholarship. V. Perchet acknowledges support from the French National Research Agency (ANR) under grant number #ANR-19-CE23-0026 as well as the support grant, as well as from the grant "Investissements d' Avenir" (LabEx Ccodec/ANR-11-LABB..
References
Animashree Anandkumar, Nithin Michael, and Ao Tang. Opportunistic spectrum access with multiple users: Learning under competition. In 2010 Proceedings IEEE INFOCOM, pages 1 1-9. IEEE, 2010.
Raman Arora, Ofer Dekel, and Ambuj Tewari. Online bandit learning against adaptive adversary: from regret to policy regret. In Proceedings of the 29th International Coference on International Conference Machine Learning, pages 1747-1754, 2012.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-77, 2002.
Soumya Basu, Karthik Abinav Sankararaman, and Abishek Sankararaman. Beyond log)(() regret for decentralized bandits in matching markets. arXiv preprint arXiv:2103.07501, 2021.
Johann Berger. Schach-jahrbuch fur 1899/1900 fortsetzung des schach-jahrbuches fur 1892/93. Verlag von Veit, 1899.
Garrett Birkhoff. Tres observaciones sobre el algebra lineal. Univ. Nac. Tucuman, Ser. A, 5:147-154, 1946.
Ilai Bistritz and Amir Leshem. Distributed multi-player bandits-a game of thrones approach. Advances in Neural Information Processing Systems (NeurlPS), 2018.
Avrim Blum and Yishay Monsour. Learning, regret minimization, and equilibria. Algorithmic Game Theory, 2007.
Rémi Bonnefoi, Lilian Besson, Christophe Moy, Emilie Kaufmann, and Jacques Palicot. Multi-armed bandit learning in iot networks: Learning helps even in non-stationary settings. In International Conference on Cognitive Radio Oriented Wireless Networks, pages 173-185. Springer, 2017.
Allan Borodin, Jon Kleinberg, Prabhakar Raghavan, Madhu Sudan, and David Williamson. Adver- sarial queueing theory. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 375-385, 1996.
Etienne Boursier and Vianney Perchet. SIC-MMAB: Synchronisation involves communication in multiplayer multi-armed bandits. In NIPS Proceedings, 2019.
Etienne Boursier and Vianney Perchet. Selfish robustness and equilibria in multi-player bandits. In Conference on Learning Theory, pages 530-581. PMLR, 2020.
Sébastien Bubeck. Convex optimization: Algorithms and complexity. arXiv preprint arXiv: 1405.4980, 2014.
Sébastien Bubeck, Thomas Budzinski, and Mark Sellke. Cooperative and stochastic multi-player multi-armed bandit: Optimal regret with neither communication nor collisions. urXiv preprint arXiv:201 arXiv:2011.03896, 1.03896, 2020.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Fanny Dufossé, Kamer Kaya, Ioannis Panagiotas, and Bora Uçar. Further notes on birkhoff von neumann decomposition of doubly stochastic matrices. Linear Algebra and its Applications, 554: 68-78, 2018
Drew Fudenberg, Fudenberg Drew, David K Levine, and David Levine. The theory of learning in games, volume 2. MIT press, 1998.

---

Jason Gaitonde and Eva Tardos. Stability and learning in strategic queuing systems. In Proceedings of the 21 ACM Conference on Economics and Computation, pages 319-347, 2020a.
Jason Gaitonde and Eva Tardos. Virtues of patience in strategic queuing systems. arXiv preprint OrXiv:2011.102000 2020b.
Leonidas Georgiadis, Michael Neely, and Leandros Tassiulas. Resource allocation and cross cross-layer control in wireless networks. Now Publishers Inc, 2006.
Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 6865):1177-11500 2000.
Libin Jiang and Jean Walrand. A distributed esma algorithm for throughput and utility maximization in wireless networks. IFEE/ACM Transactions on Networking, 18(3):960-975 972. 2009.
Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. In Annual Symposium Theoretical Aspects of Computer Science, pages 404-413. Springer, 1999.
Subhashini Krishnasamy, Rajat Sen, Ramesh Johari, and Sanjay Shakkottai. Regret of queueing bandits. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Gar- nett, editors, Advances Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016. URL https: http:///pooeeeen...eere www.eeedinnn..uuiiiiieeeee neurips cttccc//pppp pccppper/201///ilee 1400526666446Gd1166667766666
pdf
Lydia T Liu, Horia Mania, and Michael Jordan. Competing bandits in matching markets. In
International Conference on Artificial Intelligence and Statistics, pages 1618-1628. PMLR, 2020a.
Lydia T Liu, Feng Ruan, Horia Mania, and Michael Jordan. Bandit learning in decentralized matching markets. arXiv preprint arXiv:2012.07344. 2020b.
Albert W Marshall, Ingram Olkin, and Barry C Arnold. Inequalities: theory of majorization and its applications, volume 143. Springer, 1979.
Abbas Mehrabian, Etienne Boursier, Emilie Kaufmann, and Vianney Perchet. A practical algorithm for multiplayer bandits when arm means vary among players. International Conference on Artificial Intelligence and Statistics, pages 1211-1221. PMLR, 2020.
Michael J Neely, Eytan Modiano, and Chih-Ping Li. Fairness and optimal stochastic control for heterogeneous networks. IEEE/ACM Transactions On Networking, 16(2):396-409 2008.
Robin Pemantle and Jeffrey S Rosenthal. Moment conditions for sequence with negative drift to be uniformly bounded Ir. Stochastic Processes and their Applications, 92(1):143-155 1999.
Vianney Perchet. Approachability. regret and calibration: Implications and equivalences. Journal of Dynamics & Games, 1(2):181, 2014.
Tim Roughgarden. Algorithmic game theory. Communicationss of the ACM, 53(7):78-86, 2010.
Abishek Sankararaman, Soumya Basu, and Karthik Abinav Sankararaman. Dominate delete: Decentralized competing bandits with uniform valuation. arXiv preprint arXiv:2006. 15166, 2020.
Andreas Schulz and Nicolás Stier Moses. On the performance of user equilibria in traffic networks. In SODA, volume 3, pages 86-87, 2003.
Devavrat Shah and Jinwoo Shin. Randomized scheduling algorithm for queueing networks. The 2012.
Annals of Applied Probability,
John F Shortle, James M Thompson, Donald Gross, and Carl M Harris. Fundamentals of queueing theory, volume 399. John Wiley Sons, 2018
Leandros Tassiulas and Anthony Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. In 29th IEEE Conference on Decision and Control, pages 2130-2132. IEEE, 1990.
Po-An Wang, Alexandre Proutiere, Kaito Ariu, Yassir Jedra, and Alessio Russo. Optimal algorithms for multiplayer multi-armed bandits. In International Conference on Artificial Intelligence and Statistics, pages 4120-4129. PMLR, 2020.
12


Reviews:
[{"review_id": "myBc7_XFfU", "reviewer": "Reviewer_E9jT", "summary": "The paper proposed a distributed scheduling algorithm for N queues and K servers, with heterogeneous arrival rates for the queues and service rates for the servers. The rates are unknown to the players (each player is a queue). Each queue to which server (if any) to send a packet. A server that receives multiple packets attempts to serve the oldest one and ignores the others (e.g., sends them back). In the proposed algorithm, players explore the arrival and service rates on the fly. To exploit, players use their local estimated rates to compute a dominant mapping between queues and servers based. Then players use Birkhoff von Neumann decomposition to obtain a doubly stochastic matrix of the random strategies, which gives the dominant mapping on average. It is proved that the proposed algorithm is strongly stable for when the slack eta is greater than one (\"sum of service rate is larger than the sum of arrival rates\"). ", "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": "The paper is exciting and creative, solves a relevant problem, and is well-written. The proofs are sound and easy to follow. I recommend accepting the paper. There are only several issues that if resolved (or explained) can make the paper stronger:\n\n1) The model needs to be discussed and motivated in more detail. Why is this structure where packets are sent back and forth to servers natural or efficient? is there any simple  *distributed* mechanism that implements that without actually submitting the packets? in what application would this be the case? a stronger model takes into account collisions between queues that send packets to the same server. How much more difficult is this model and why? (the exploitation avoids collisions already, doesn't it?). Also, reading lines 102-104 it looks like a queue has to send a packet if it's not empty. Is this true? seems like an arbitrary limitation. \n\n\n2) That's of course subjective, but I didn't find Section 3 very interesting and it's not clear to me if it's relevant or delivers any strong point. The policy regret is only used in this section. As much as I understand, nobody proposed the policy regret as an alternative for queueing systems, so it's not very shocking that no-policy regret algorithms don't work. I do get why no policy regret is more suitable for queueing than simple regret. However, Proposition 1 doesn't even show that no-policy regret algorithms don't work, but that a very specific one doesn't work, that uses a lot of synchronization between the players. This is indeed a counterexample that shows that not *all* no policy regret algorithms work, but this sounds like a weak and esoteric point. It's possible that a smarter, less contrived no policy regret algorithm can have stability guarantees. It's probably hard to design and analyze such an algorithm, and it of course beyond the scope of this paper, but the result here doesn't say much about this possibility. Proposition 1 doesn't build the \"case for a cooperative algorithm\", since one can easily give a counterexample of a cooperative algorithm that doesn't work as well. Would this build the case against cooperative algorithms? I suggest moving this section to an appendix and tighten the language about what this result shows. The paper is exciting enough without this section, which delays the main point. The proposed cooperative algorithm seems like a breakthrough and it doesn't take away much from it if a no policy regret algorithm that can do the job exists out there.  Some technical questions:\n\na) How similar is the counterexample here to that used to prove Theorem 3?\n\nb) it looks like T needs to be infinity for Proposition 1 to make sense, but the regret definition uses finite T. Then, saying that the policy regret is o(w_k) on all but finitely many windows is a bit cumbersome. Can't you say that the overall regret is sublinear?  \n\n\n3) The common randomness assumption seems reasonable to me, but it needs more discussion. The reader needs to be convinced that no hidden coordination is assumed so initializing the players with a \"long random sequence\" (seed) is enough. Consider discussing that here and there near the places where the common randomness is used. \n\n\n4) The modification of the dominant mapping problem in (3) is nice, but I'm not sure if it's necessary. The cost is the assumption in Remark 3 that exact computation of a non-smooth problem is possible. This is perhaps the main weakness of the paper. Looking at the proof, I think there's some hope that working with the usual dominant mapping is possible. Line 272 says that the problem is that sorting the rates is non-continuous. Lines 255-257 imply the same (which might be an overstatement, by the way). However, the good event \\mathcal(E_t) happens infinitely often, as the proof shows, for any estimation error for the rates. When this error is smaller than the minimal gap between the rates, all players agree on the ranking/sorting of the rates. Doesn't this allow for the usual dominant mapping computation? are there any other issues that cannot be easily solved? this needs to be at least discussed in more detail since the question naturally raises and currently the paper doesn't justify the modification well enough. In fact, Remark 3 is suggesting something very similar: that if the approximation error is small, there is no impact on the stability. The paper is strong enough already, but if such an improvement is possible, I think it's a small price to pay to make the paper even stronger. \n\n5) A conclusion section can be nice. Aren't there any interesting insights or future directions to pursue? I definitely think there are plenty. \n\n\n\nMinor Comments:\n\n1) Line 117: \"real number such that\" - it's better to add eta there \n2)  Line 199: better to mention explicitly what \"problem parameters\". \n3) Algorithm 1: it's hard to understand what's phi, psi without reading the text. Please add some high-level names and add some minimal text in line 2, and references to where they're defined in the paper. It might be also a good opportunity to connect Algorithm 3 to Algorithm 1. \n4) Is \"bistochastic\" common? why not doubly stochastic? \n5) Since theorem 3 discusses regret, its definition should appear before it and not in Section 3. \n6) The fact that the main result of this paper is both the informal Theorem 1 and Theorem 5 is confusing, better to call them both Theorem 1. \n7) Line 286 - extra space after \"below\". \n8) The proof of Lemma 3 uses the definition of P_j that only appears in Lemma 2. \n9) Lemma 6: strictly speaking, \"no policy regret\" was never defined, and indeed the phrasing in Proposition 1 is different. \n9) Line 569: change doesn't to \"does not\"\n10) Line 587: \"equation Equation (16)\"\n11) Line 605: \"actually\" is awkward \n12) Line 636: note that. Also, \"It comes\" is nonstandard. Use \"It follows\" or something else (repeated in several places). \n13) Missing periods after the equations in lines 645 and 646.\n14) Line 652: If the last term is zero, then it's not ignored - please rephrase. \n15) Lemma 11/Line 699: why do you need to show that tao is bounded with probability 1? \n16) Line 712: Although I wish \"sarcastically dominated\" was a thing, that's a typo (: \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no negative societal impact since the paper is focused on the theory. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "Vk7FZQ_qLx", "reviewer": "Reviewer_fVk3", "summary": "The paper considers an online queueing system where multiple queues\n  are served by a set of servers. Each queue (if non-empty) sends a\n  packet to one of the servers. Each server serves the oldest packet\n  it receives, and returns the other packets to their respective\n  queues. The goal is to design a policy so that the queues remain\n  stable. Past work has shown that the stability of the system depends\n  on its /slack/, which is a measure that captures the ratio between\n  total service rate of a subset of servers and the total arrival rate\n  to a subset of queues. Specifically, it is known that if the slack\n  is strictly greater than one, then there exists centralized policies\n  that are (strongly) stable. On the other hand, restricting attention\n  to policies that are decentralized across queues, stable policies\n  were only known to exist when slack was strictly greater than two\n  (or greater than $e/(e-1)$ if the arrival rates and service rates\n  were known).\n\n  In this work, the authors propose a decentralized policy that\n  achieves stability for all values of slack strictly greater than\n  one, matching the stability regime for centralized policies. The\n  algorithm uses shared randomness to coordinate the queues' actions\n  to explore the arrival rates and the service rates, and then use the\n  estimates in the exploitation phase. The challenge is to ensure that\n  the queues avoid colliding on the same server; this is done using\n  smooth dominant mappings (which take the estimates and return a\n  bistochastic fractional matching between servers and queues) and\n  regular Birkhoff-von Neumann (BvN) decompositions (which take the\n  fractional bistochastic matching and yield a distribution over a\n  matching). The authors support their theoretical results through\n  numerical computations that show the performance of their proposed\n  algorithm.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "*  Pros\n   - The paper studies the setting of decentralized control with\n     carryover effects, and shows that decentralized policies with\n     shared randomness can be as effective as centralized policies in\n     acheiving stability. This is interesting from the theoretical\n     perspective, characterizing the strength of decentralized\n     policies.\n   - The algorithm uses smoothed/regularized versions of the dominant\n     matchings and BvN decompositions to ensure continuity of the\n     matching with respect to the estimates. This might be of interest\n     more broadly.\n* Cons\n   - The strong stability bounds are super-exponential in the number\n     $K$ of servers, leading to impractically large coefficients even\n     for $K$ as small as $5$. Since the shared numerics seems to\n     suggest good performance of the algorithm, it would suggest that\n     the theoretical analysis is not tight.\n   - The algorithm requires a substantial amount of shared randomness,\n     which may not be possible in practical settings without a\n     substantial level of centralization.\n\nOverall, I think the paper makes a valuable theoretical contribution\nto the problem of decentralized control of queueing systems (or more\ngenerally systems with carryover effects). ", "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": "5"}, "extra_text": {}}, {"review_id": "MMJHeZJEXk2", "reviewer": "Reviewer_7uFN", "summary": "For the recently proposed online queueing system, the authors presented several key results. First, they demonstrated that, when the slack is below 2, coorperation is necessary for the stability of the system by constructing a counterexample; second, they proposed a decentralized learning algorithm, and proved that it guarantees stability under the mild condition of the slack being larger than one.", "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": "The paper contains important new results and (counter)examples for online queueing system. The decentralized learning algorithm (ADEQUA) is an important contribution to this area of research, I could see it being further analyzed by many researchers in the future, and variations being proposed. The counterexample (in Proposition 1) and the main results (Theorem 5) fill in the gap of knowledge of this important problem. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "not apply", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "three"}, "extra_text": {}}, {"review_id": "2LCpfch_sK", "reviewer": "Reviewer_Vdob", "summary": "This paper studies a decentralized learning problem for queueing systems. In my opinion, the paper is difficult to follow. I could not understand the problem setup and the paper’s contributions. Also, the article has a strong economics component which I am not familiar with. ", "questions": "", "limitations": "", "rating": 5, "confidence": 1, "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": "From my understanding of the model in Sec. 2, and the cooperative algorithm in Sec. 3, it seems that the problem addressed is closely connected to scheduling/routing problems studied extensively in computer networks. See, for example, \n\nGeorgiadis, L., Neely, M.J. and Tassiulas, L., 2006. Resource allocation and cross-layer control in wireless networks. Now Publishers Inc.\n\nIt would be helpful if the authors can clarify why their problem cannot be solved with mainstream networking approaches. \n\nIn section 4.2, the authors propose an “ordered Birkhoff” algorithm, which seems to be a variation of the original Birkhoff algorithm. Many works in the literature study variants of the Birkhoff algorithm, but none of them are mentioned in the paper. See, for example, \n\nDufossé, F. and Uçar, B., 2016. Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices. Linear Algebra and its Applications, 497, pp.108-115.\n\nHow is your “ordered Birkhoff” algorithm different from existing algorithms?", "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": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper makes a clear contribution to the question of decentralized learning in queuing systems.
Thus, we decided to accept the paper.
Decision: Accept (Spotlight)