Decentralized Learning in Online Queuing Systems
Year: 2022

Abstract:
Motivated by packet routing in computer networks and resource allocation in radio 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 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.

heading: 1 Introduction
text: Inefficient decisions in repeated games can stem from both strategic and learning considerations. First, strategic agents selfishly maximize their own 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 might be too pessimistic. In games with external factors, more complex interactions intervene and 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 economics [Fudenberg et al., 1998, Cesa-Bianchi and Lugosi, 2006]. The interaction between multiple agents can indeed interfere in the learning process, potentially converging to no or bad equilibria. It is yet known that in repeated games, if all agents follow no internal regret strategies, their actions converge in average to the set of correlated equilibria [Hart and Mas-Colell, 2000, Blum and Monsour, 2007, Perchet, 2014].
∗Equal contributions 35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Many related results are known in the classical repeated games [see e.g., Cesa-Bianchi and Lugosi, 2006, Roughgarden, 2010], where a 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 a repeated game with a carryover feature: the outcome of a 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 is 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 a patient game, where queues instead minimize their asymptotic number of accumulated packets. A ratio only larger than ee−1 then guarantees the stability of the system, while a smaller ratio leads to inefficient Nash equilibria. As a consequence, going below the ee−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 as a patient alternative to 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 1 below, whose formal version, Theorem 5 in Section 4, also provides bounds on the number of accumulated packets.
Theorem 1 (Theorem 5, 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 1. Section 5 finally compares the behavior of ADEQUA with no-regret strategies on toy examples and empirically confirms the different known theoretical results.

heading: 1.1 Additional related work
text: Queuing theory includes applications in diverse areas such as computer science, engineering, operation research [Shortle et al., 2018]. Borodin 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 a 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. Tassiulas and Ephremides [1990] proposed a first stable centralized algorithm, when the service rates are known a 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 Xk(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. It 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. It is thus even more closely related to 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 et al., 2020], this becomes harder with an asymmetric collision model as in competing bandits. However, some level of communication remains possible [Sankararaman et al., 2020, Basu et al., 2021]. 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 to a correlated equilibrium of the patient game described in Section 2.
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 [Bonnefoi 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.

heading: 2 Queuing Model
text: We consider a queuing system composed of N queues and K servers, associated with vectors of arrival and service rates λ,µ, where at each time step t = 1, 2, . . . , the following happens:
• each queue i ∈ [N ] receives a new packet with probability λi ∈ [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 j based on its past observations.
• Each server j ∈ [K] attempts to clear the oldest packet it has received, breaking ties uniformly at random. It succeeds with probability µj ∈ [0, 1] and otherwise sends it back to 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 Qit the number of packets in queue i at time t. Given a packet-sending dynamics, the system is stable if, for each i in [N ], Qit/t converges to 0 almost surely. It is strongly stable, if for any r, t ≥ 0 and i ∈ [N ], E[(Qit)r] ≤ Cr, where Cr is an arbitrarily large constant, depending on r 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, x(i) will denote the i-th order statistics of a vector x, i.e., λ(1) ≥ λ(2) ≥ . . . ≥ λ(N) and µ(1) ≥ . . . ≥ µ(K). Without loss of generality, we assume K ≥ N (otherwise, we simply add fictitious servers with 0 service rate). The key quantity of a system is its slack, defined as the largest real number η such that:
k∑ i=1 µ(i) ≥ η k∑ i=1 λ(i), ∀ k ≤ N.
We also denote by P ([K]) the set of probability distributions on [K] and by ∆ the margin of the system defined by
∆ := min k∈[N ]
1
k k∑ i=1 (µ(i) − λ(i)). (1)
Notice that the alternative system where λ̃i = λi + ∆ and µ̃k = µk has a slack 1. In that sense, ∆ is the largest margin between service and arrival rates that all queues can individually get in the system. Note that if η > 1, then ∆ > 0. We now recall existing results for this problem, summarized in Figure 1 below.
Theorem 2 (Marshall et al. 1979). For any instance, there exists a strongly stable centralized policy if and only if η > 1. Theorem 3 (Gaitonde and Tardos 2020a, informal). If η > 2, queues following appropriate no regret strategies are strongly stable. For each N > 0, there exists a system and a dynamic s.t. η > 2 − o(1/N), all queues follow appropriate no-regret strategies, but they are not strongly stable.
In the above theorem, an appropriate no regret strategy is a strategy such that there exists a 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.1 algorithm [Auer et al., 2002] where the k-th window has length 2k.
The patient queuing game G = ([N ], (ci)ni=1,µ,λ) is defined as follows. The strategy space for each queue is P ([K]). Let p−i ∈ (P ([K]))N−1 denote the vector of fixed distributions for all queues over servers, except for queue i. The cost function for queue i is defined as:
ci(pi,p−i) = lim t→+∞
T it /t,
where T it is the age of the oldest packet in queue i at time t. Bounding T i t is equivalent to boundingQ i t. Theorem 4 (Gaitonde and Tardos 2020b, informal). If η > ee−1 , any Nash equilibrium of the patient game G is stable.

heading: 3 The case for a cooperative algorithm
text: According to Theorems 3 and 4, queues that are patient enough and select a fixed randomization over the servers are stable over a larger range of slack η than queues optimizing their individual regret. A key difference between the two settings is that when minimizing their regret, queues are myopic, which is formalized as follows. Let a1:t = (a1, ..., at) be the vector of actions played by a queue up to time t and let νt(a1:t) be the indicator that it cleared a packet at iteration t. Classical (external) regret of queue i over horizon T is then defined as:
Rexti (T ) := max p∈P([K]) T∑ t=1 Eãt∼p[νt(a1:t−1, ãt)]− T∑ t=1 νt(a1:t).
Thus minimizing the external regret is equivalent to maximizing the instant rewards at each iteration, ignoring the consequences of the played action on 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 can be in the best interest of a queue, as it may give it priority in the subsequent iterations where it holds older packets. Since the objective is to maximize the total number of packets cleared, it seems adapted to minimize a patient version of the regret, namely the policy regret [Arora et al., 2012], rather than the external regret, which is defined by
Rpoli (T ) := max p∈P([K]) T∑ t=1 Eã1:t∼⊗ti=1p[νt(ã1:t)]− T∑ t=1 νt(a1:t).
That is, Rpoli (T ) is the expected difference between the number of packets queue i cleared and the number of packets it would have cleared over the whole period by playing a fixed (possibly random) action, taking into account how this change of policy would affect the state of the system.
However, as stated in Proposition 1, optimizing this patient version of the regret rather than the myopic one could not guarantee stability on a wider range of slack value. This suggests that adding only patience to the learning strategy of the queues is not enough to go beyond a slack of 2, and that any strategy beating that factor 2 must somewhat include synchronisation between the queues. Proposition 1. Consider the partition of the time t = 1, 2, . . . into successive windows, where wk = k
2 is the length of the k-th one. For any N ≥ 2, there exists an instance with 2N queues and servers, with slack η = 2−O ( 1 N ) , s.t., almost surely, each queue’s policy regret is o (wk) on all but finitely many of the windows, but the system is not strongly stable.
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, a set of system parameters, for which any no external regret policies were unstable, was exhibited. Whereas we exhibit in our case a specific strategy that satisfies the no policy regret condition, but is unstable.
Sketch of proof. Consider a system with 2N queues and servers with λi = 1/2N and µi = 1/N − 1/4N2 for all i ∈ [2N ]. The considered strategy profile is the following. For each k ≥ 0, the kth time window is split into two stages. During the first stage, of length dαwke, queues 2i and 2i+ 1 both play server 2i+ t (mod 2N) at iteration t, for all i ∈ [N ]. During the second stage of the time window, queue i plays server i+ t (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 is 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 α is tuned so that the queues still accumulate a linear portion of packets during each time window. For those appropriate α, the system is unstable.
Now suppose that queue i deviates from the strategy and plays a fixed action p ∈ P ([K]). In the first stage of each time window, queue i 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 a large number of times. Because of those collisions, it will accumulate many packets. In the detailed analysis, we demonstrate that, in the end, for appropriate values of α, queue i accumulates more packets than it would have without deviating.
According to Theorem 4, the factor ee−1 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 at each time step, independently from the number of accumulated packets. As a consequence, it is also a correlated equilibrium of the patient game and 1 can be seen as the correlated price of stability.

heading: 4 A decentralized algorithm
text: This section describes the decentralized algorithm ADEQUA, whose pseudocode is given in Algorithm 1. 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 a unique rank or id in [N ]. Moreover, the existence of a 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 collision information. On the other side, the shared randomness assumption is equivalent to the knowledge of a 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 ε-greedy strategy. With probability εt = (N +K)t− 1 5 , at each time step, queues explore the different parameters λi and µi as described below. Otherwise with probability 1 − εt, they exploit the servers. Each queue i then sends a packet to a server following a policy solely computed from its local estimates λ̂i, µ̂i of the problem parameters λ and µ. The shared randomness is here used so that exploration simultaneously happens for all queues. If exploration/exploitation was not synchronized between the queues, an exploiting queue could collide with an exploring queue, biasing the estimates λ̂i, µ̂i of the latter.
Algorithm 1: ADEQUA input : N (number of queues), i ∈ [N ] (queue id)
1 for t = 1, . . . ,∞ do 2 P̂ ← φ(λ̂, µ̂) and Â← ψ(P̂ ) where φ and ψ are resp. defined by Equations (3) and (4) 3 Draw ω1 ∼ Bernoulli((N +K)t− 1 5 ) and ω2 ∼ U(0, 1) // shared randomness 4 if ω1 = 1 then EXPLORE(i) // exploration 5 else Pull Â(ω2)(i) // exploitation 6 end
Exploration. When exploring, queues choose either to explore the servers’ parameters µk or the other queues’ parameters λi as described in Algorithm 2 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: µ̂ik is the empirical mean of server k observed by the queue i 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 a pairwise fashion. When queues i and j 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 a packet appeared during round t. In that case, we say that the queue i explores λj (and vice versa). To make sure that i and j are the only queues choosing the server k during this step, we proceed as follows:
• queues sample a matching π between queues at random. To do so, the queues use the same method to plan an all-meet-all (or round robin) tournament, for instance Berger tables [Berger, 1899], and choose uniformly at random which round of the tournament to play. If the number of queues N is odd, in each round of the tournament, one queue remains alone and does nothing.
• the queues draw the same number l ∼ U([K]) with their shared randomness. For each pair of queues (i, j) matched in π, associate k(i,j) = l + min(i, j) (mod K) + 1 to this pair. The queues i and j then send to the server k(i,j).
As we assumed that the server breaks ties in the packets’ age uniformly at random, the queue i clears with probability (1− λj2 )µ̄, where µ̄ = 1 K ∑K k=1 µk. Thanks to this, λj is estimated by queue i as:
λ̂ij = 2− 2Ŝij/µ̃i, (2)
where µ̃i = ∑K k=1N i kµ̂ i k∑K
k=1N i k
, N ik is the number of exploration pulls of server k by queue i and Ŝ i j is the
empirical probability of clearing a packet observed by queue i when exploring λj .
Algorithm 2: EXPLORE input :i ∈ [N ] // queue id 1 k ← 0 2 Draw n ∼ U([N +K]) // shared randomness 3 if n ≤ K then // explore µ 4 k ← n+ i (mod K) + 1 5 Pull k ; Update Nk and µ̂k 6 else // explore λ 7 Draw r ∼ U([N ]) and l ∼ U([K]) // shared randomness 8 j ← rth opponent in the all-meet-all tournament planned according to Berger tables 9 k ← l + min(i, j) (mod K) + 1 10 if k 6= 0 and packet appeared at current time step then // explore λj on server k 11 Pull k with most recent packet ; Update Ŝj and λ̂j according to Equation (2) 12 end 13 end
Remark 1. The packet manipulation when exploring λj strongly relies on 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 λj , queue j instead sends the packet generated at time t− 1 (if it exists), while queue i still sends the packet generated at time t. In that case, the clearing probability for queue i is exactly (1 − λj)µ̄, allowing to estimate λj . Anticipating the nature of the round t (exploration vs.
exploitation) can be done by drawing ω1 ∼ Bernoulli(εt) at time t − 1. If ω1 = 1, the round t is exploratory and the packet generated at time t− 1 is then kept apart by the queue j.
To describe the exploitation phase, we need a few more notations. We denote by BK the set of doubly stochastic matrices (non-negative matrices such that each of its rows and columns sums to 1) and by SK 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 φ : RN × RK → BK which, from (λ, µ), returns a doubly stochastic matrix P such that λi < (Pµ)i for any i ∈ [N ] if it exists (and the identity matrix otherwise).
A BvN (Birkhoff von Neumann) decomposition is a function ψ : BK → P(SK) that associates to any doubly stochastic matrix P a random variable ψ(P ) such that E[ψ(P )] = P ; stated otherwise, it expresses P as a convex combination of permutation matrices. For convenience, we will represent this random variable as a function from [0, 1] (equipped with the uniform distribution) to SK .
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µ)i packets at each step, which is larger than λi by definition), while a BvN decomposition describes the associated coupling to avoid collisions. Explicitly, the joint strategy is for each queue to draw a shared random variable ω2 ∼ U(0, 1) and to choose servers according to the permutation ψ(φ(λ, µ))(ω2)
Exploitation. In a decentralized system, each queue i computes a mapping Âi := ψ(φ(λ̂i, µ̂i)) solely based on its own estimates λ̂i, µ̂i. A shared variable ω2 ∈ [0, 1] is then generated uniformly at random and queue i sends a packet to the server Âi(ω2)(i). If all queues knew exactly the parameters λ, µ, the computed strategies Âi would be identical and they would follow the centralized policy described above.
However, the estimates (λ̂i, µ̂i) 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̂i, and thus collide a large number of times, which would impede the stability of the system. Regular enough dominant mappings and BvN decompositions are required, to avoid this phenomenon. The design of φ and ψ is thus crucial and appropriate choices are given in the following Sections 4.1 and 4.2. 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 a general result depending on the properties of φ and ψ, in Appendix A.
Remark 2. The exploration probability t− 15 gives the smallest theoretical dependency in ∆ in our bound. A trade-off between the proportion of exploration rounds and the speed of learning indeed appears in the proof of Theorem 1. Exploration rounds have to represent a small proportion of the rounds, as the queues accumulate 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 probability is given by Theorem 6 in Appendix A. Yet in Section 5, taking a probability t− 1 4 empirically performs better as it speeds up the exploration.

heading: 4.1 Choice of a dominant mapping
text: Recall that a dominant mapping takes as inputs (λ, µ) and returns, if possible, a doubly stochastic matrix P such that
λi < ∑K k=1 Pi,kµk for all i ∈ [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 a 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
φ(λ, µ) = arg min P∈BK max i∈[N ] − ln ( K∑ j=1 Pi,jµj − λi ) + 1 2K ‖P‖22. (3)
Although the objective function is non-smooth because of the max operator, it enforces fairness between queues and leads to a better regularity of the arg min. Remark 3. Computing φ requires solving a non-smooth strongly convex minimization problem. This cannot be computed exactly, but a good approximation can be quickly obtained using the scheme described in Appendix B. If this approximation error is small enough, it has no impact on the stability bound of Theorem 5. It is thus ignored for simplicity, i.e., we assume in the following that φ(λ, µ) is exactly computed at each step.
As required, φ always returns a matrix P satisfying that λ < Pµ if possible, since otherwise the objective is infinite (and in that case we assume that φ returns the identity matrix). Moreover, the objective function is 1K -strongly convex, which guarantees some regularity of the arg min, namely local-Lipschitzness, leading to Lemma 1 below.
Lemma 1. For any (λ, µ) with positive margin ∆ (defined in Equation (1)), if ‖(λ̂− λ, µ̂− µ)‖∞ ≤ c1∆, for any c1 < 12√e+2 , then
‖φ(λ̂, µ̂)− φ(λ, µ)‖2 ≤ c2K
∆ ‖(λ̂− λ, µ̂− µ)‖∞,
where c2 = 4(1−2c1)/ √ e−2c1 . Moreover, denoting P̂ = φ(λ̂, µ̂), it holds for any i ∈ [N ],
λi ≤ ∑K k=1 P̂i,kµk − ( 1−2c1√ e − 2c1 ) ∆.
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 ∆, in absence of collisions. Remark 4. An alternative dominant mapping without the regularizing term in Equation (3) can also be proposed. Yet, its local Lipschitz bound would also depend on the smallest difference between the λi or the µi, which can be arbitrarily small. If two parameters λi or µi are equal, this choice of dominant mapping might lead to unstable policies. Using a regularization term in Equation (3) thus avoids this problem, although a smaller dependency might be possible without this regularization term when the parameters λi and µi are very distinct.

heading: 4.2 Choice of a Birkhoff von Neumann decomposition
text: Given a doubly stochastic matrix P̂ , Birkhoff algorithm returns a convex combination of permutation matrices P [j] such that P̂ = ∑ j z[j]P [j]. The classical version of Birkhoff algorithm is noncontinuous in its inputs and it even holds for its extensions as the one proposed by Dufossé et al. [2018]. Yet it can be smartly modified as in ORDERED BIRKHOFF, described in Algorithm 3, to get a regular BvN decomposition defined as follows for any ω ∈ (0, 1):
ψ(P )(ω) = P [jω] (4) where P = ∑ j z[j]P [j] is the decomposition returned by ORDERED BIRKHOFF algorithm
and jω verifies ∑ j≤jω z[j] ≤ ω < ∑ j≤jω+1 z[j].
For a matrix P in the following, its support is defined as supp(P ) = {(i, j) | Pi,j 6= 0}. Algorithm 3: ORDERED BIRKHOFF
input :P̂ ∈ BK (doubly stochastic matrix), C ∈ RK×K (cost matrix) 1 j ← 1 2 while P̂ 6= 0 do 3 Ci,k ← +∞ for all (i, k) 6∈ supp(P̂ ) // remove edge (i, k) in induced graph 4 P [j]← HUNGARIAN(C) // matching with minimal cost w.r.t. C 5 z[j]← min(i,k)∈supp(P [j]) P̂i,k 6 P̂ ← P̂ − z[j]P [j] and j ← j + 1 7 end 8 return (z[j], P [j])j
Obviously Eω∼U(0,1)[ψ(P )(ω)] = P and permutations avoid collisions between queues. The difference with the usual Birkhoff algorithm happens at Line 4. 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 Hopcroft-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 (K3 instead of K2.5), it ensures to output the permutation matrices P [j] according to a fixed order defined below.
Definition 1. A cost matrix C induces an order ≺C on the permutation matrices defined, for any P, P ′ ∈ SK by
P ≺C P ′ iff ∑ i,j Ci,jPi,j < ∑ i,j Ci,jP ′ i,j .
This order might be non-total as different permutations can 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 ∈ RK×K and P ∈ BK , ORDERED BIRKHOFF outputs a sequence (z[j], P [j])j of length at most K2 −K + 1, such that
P = ∑ j z[j]P [j], where for all j, z[j] > 0 and P [j] ∈ SK .
Moreover if the induced order ≺C is total, z[j] is the j-th non-zero element of the sequence (zl(P ))1≤l≤K! defined by
zj(P ) = min (i,k)∈supp(Pj)
( P − j−1∑ l=1 zl(P )Pl ) i,k
(5)
where (Pj)1≤j≤K! is a ≺C -increasing sequence of permutation matrices, i.e., Pj ≺C Pj+1 for all j.
Lemma 2 is crucial to guarantee the regularity of ψ, given by Lemma 3.
Lemma 3. Consider ψ defined as in Equation (4) with a cost matrix C inducing a total order ≺C , then for any doubly stochastic matrices P, P ′∫ 1
0
1 (ψ(P )(ω) 6= ψ(P ′)(ω)) dω ≤ 22(K 2−K+1)‖P − P ′‖∞.
Lemma 3 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 a similar dependency in the stability bound of Theorem 5. The existence of a BvN decomposition with polynomial regularity constants remains unknown, even without computational considerations. The design of a better BvN decomposition is left open for future work and would directly improve the stability bounds, using the general result given by Theorem 6 in Appendix A. The number of accumulated packets yet remain reasonably small in the experiments of Section 5, suggesting that the bound given by Lemma 3 is not tight and might be improved in future work.

heading: 4.3 Stability guarantees
text: 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 parameters 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 a margin of order ∆, thanks to Lemmas 1 and 3. This finally ensures the stability of the system, as given by Theorem 5.
Theorem 5. For any η > 1, the system where all queues follow ADEQUA, for any queue i and any r ∈ N, there exists a constant Cr depending only on r such that
E[(Qit)r] ≤ CrKN ( N 5 2K 5 2 25(K 2−K+1)
(min(1,Kµ̄) ¯ λ)
5 4 ∆5
)r , for all t ∈ N.
As a consequence, for any η > 1, this decentralized system is strongly stable.
Despite yielding an exponential dependency in K2, this anytime bound leads to a first decentralized stability result when η ∈ (1, ee−1 ), which closes the stability gap left by previous works. Moreover it can be seen in the proof that the asymptotic number of packets is much smaller. It actually converges, in expectation, to the number of packets the queues would accumulate if they were following a stable centralized strategy from the beginning. As already noted by Krishnasamy et al. [2016] for a 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 in the perfect knowledge centralized case. This is empirically confirmed in Section 5.

heading: 5 Simulations
text: Figures 2 and 3 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 εt = (N +K)t− 1 4 for ADEQUA, as the exploration is too slow with εt of order t− 1 5 .
These figures illustrate the evolution of the average queue length on two different instances with N = K = 4. The code for the experiments is available at gitlab.com/f_sen/queuing_systems.
In the first instance shown in Figure 2, for all i ∈ [N ], λi = (N + 1)/N2. Moreover µ1 = 1 and for all i ≥ 2, µi = (N − 1)/N2. Here η < 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.1. Conversely, when the queues follow ADEQUA, after a learning phase, the queues reach equilibrium and all succeed in clearing their packets.
In the second instance shown in Figure 3, for all i ∈ [N ], λi = 0.55− 0.1 · i and µi = 2.1λi. 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 η > 2.
0.0 0.2 0.4 0.6 0.8 1.0
Iteration ×106
0
100
101
102
103
104
N um
be ro
fp ac
ke ts
ADeQuA EXP3.P.1
Figure 2: Hard instance, η < 2. 0.0 0.2 0.4 0.6 0.8 1.0 Iteration ×105
0
100
101
N um
be ro
fp ac
ke ts
ADeQuA EXP3.P.1
Figure 3: Easy instance, η > 2.

heading: 6 Conclusion
text: 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 guaranteeing stability of any queuing system with a slack larger than 1. Our stability bound presents an exponential dependency in the number of queues and remains open for improvement, e.g., through a better dominant mapping/BvN decomposition or a tighter analysis of ours. The proposed algorithm relies heavily on synchronisation between the queues, which all start the game simultaneously and share a 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 e.g., Shah and Shin, 2012].

heading: Acknowledgements
text: F. Sentenac was supported by IP 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 Ecodec/ANR-11-LABX-0047).

Review summaries:
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. 

The paper considers an online queueing system where multiple queues   are served by a set of servers. Each queue (if non-empty) sends a   packet to one of the servers. Each server serves the oldest packet   it receives, and returns the other packets to their respective   queues. The goal is to design a policy so that the queues remain   stable. Past work has shown that the stability of the system depends   on its /slack/, which is a measure that captures the ratio between   total service rate of a subset of servers and the total arrival rate   to a subset of queues. Specifically, it is known that if the slack   is strictly greater than one, then there exists centralized policies   that are (strongly) stable. On the other hand, restricting attention   to policies that are decentralized across queues, stable policies   were only known to exist when slack was strictly greater than two   (or greater than $e/(e-1)$ if the arrival rates and service rates   were known).    In this work, the authors propose a decentralized policy that   achieves stability for all values of slack strictly greater than   one, matching the stability regime for centralized policies. The   algorithm uses shared randomness to coordinate the queues' actions   to explore the arrival rates and the service rates, and then use the   estimates in the exploitation phase. The challenge is to ensure that   the queues avoid colliding on the same server; this is done using   smooth dominant mappings (which take the estimates and return a   bistochastic fractional matching between servers and queues) and   regular Birkhoff-von Neumann (BvN) decompositions (which take the   fractional bistochastic matching and yield a distribution over a   matching). The authors support their theoretical results through   numerical computations that show the performance of their proposed   algorithm.

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").