Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
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. 


limitations_and_societal_impact: not apply
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: 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.
main_review: *  Pros
   - The paper studies the setting of decentralized control with
     carryover effects, and shows that decentralized policies with
     shared randomness can be as effective as centralized policies in
     acheiving stability. This is interesting from the theoretical
     perspective, characterizing the strength of decentralized
     policies.
   - The algorithm uses smoothed/regularized versions of the dominant
     matchings and BvN decompositions to ensure continuity of the
     matching with respect to the estimates. This might be of interest
     more broadly.
* Cons
   - The strong stability bounds are super-exponential in the number
     $K$ of servers, leading to impractically large coefficients even
     for $K$ as small as $5$. Since the shared numerics seems to
     suggest good performance of the algorithm, it would suggest that
     the theoretical analysis is not tight.
   - The algorithm requires a substantial amount of shared randomness,
     which may not be possible in practical settings without a
     substantial level of centralization.

Overall, I think the paper makes a valuable theoretical contribution
to the problem of decentralized control of queueing systems (or more
generally systems with carryover effects). 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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. 
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, 

Georgiadis, L., Neely, M.J. and Tassiulas, L., 2006. Resource allocation and cross-layer control in wireless networks. Now Publishers Inc.

It would be helpful if the authors can clarify why their problem cannot be solved with mainstream networking approaches. 

In 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, 

Dufossé, 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.

How is your “ordered Birkhoff” algorithm different from existing algorithms?
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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"). 
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:

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


2) 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:

a) How similar is the counterexample here to that used to prove Theorem 3?

b) 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?  


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


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

5) A conclusion section can be nice. Aren't there any interesting insights or future directions to pursue? I definitely think there are plenty. 



Minor Comments:

1) Line 117: "real number such that" - it's better to add eta there 
2)  Line 199: better to mention explicitly what "problem parameters". 
3) 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. 
4) Is "bistochastic" common? why not doubly stochastic? 
5) Since theorem 3 discusses regret, its definition should appear before it and not in Section 3. 
6) 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. 
7) Line 286 - extra space after "below". 
8) The proof of Lemma 3 uses the definition of P_j that only appears in Lemma 2. 
9) Lemma 6: strictly speaking, "no policy regret" was never defined, and indeed the phrasing in Proposition 1 is different. 
9) Line 569: change doesn't to "does not"
10) Line 587: "equation Equation (16)"
11) Line 605: "actually" is awkward 
12) Line 636: note that. Also, "It comes" is nonstandard. Use "It follows" or something else (repeated in several places). 
13) Missing periods after the equations in lines 645 and 646.
14) Line 652: If the last term is zero, then it's not ignored - please rephrase. 
15) Lemma 11/Line 699: why do you need to show that tao is bounded with probability 1? 
16) Line 712: Although I wish "sarcastically dominated" was a thing, that's a typo (: 

limitations_and_societal_impact: There is no negative societal impact since the paper is focused on the theory.
review_title: null

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)