Pith. sign in

REVIEW 3 major objections 6 minor 32 references

Learning in Strategic Queuing Systems with Small Buffers

T0 review · 3 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A one-packet server buffer keeps no-regret learning queues stable under a constant-factor capacity margin.

desk verdict Original buffer-of-one model with an interesting lower bound, but the main proof of stability has a load-bearing gap in Lemma 3 that ignores contention at empty servers. read the letter →

arxiv 2502.08898 v2 pith:GPPOG7AT submitted 2025-02-13 cs.GT cs.AIcs.MA

Ariana Abel , Yoav Kolumbus , Jeronimo Martin Duque , Cristian Palma Foster , Eva Tardos This is my paper · ORCID
classification cs.GTcs.AIcs.MA MSC 68M2091A2660K25
keywords strategicqueuingsystemsno-regretlearningsmallbuffersstabilitycarryovereffectsmulti-agentqueueinggames
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks whether a network of selfish routers, each running a simple no-regret learning rule, can keep packet queues bounded when servers have tiny buffers. Its main result is that it can: if every arrival rate is below 1/2 and the total arrival rate is below one-third of the total service capacity, then with a single-packet buffer at each server the expected number of packets in the system stays bounded by a time-independent constant, and no timestamps or priority rules are needed. A lower-bound example shows that a factor of 2 in capacity is necessary for such a guarantee, leaving a gap between 2 and 3. Simulations indicate that in typical randomized systems the practical transition from stable to unstable behavior occurs above 1/2 and below 1, better than the worst-case factor of 3.

What carries the argument

The load-bearing object is a potential function over T-step periods, Φ = Σ_i (N_i − (1/2 λ_i + 2δ)T)_+, where N_i is queue i's packet count at the start of the period and x_+ = max(x, 0). The proof shows that when Φ is large, a good period (empirical arrivals, service completions, and regrets all within δT of their expectations) makes Φ decrease by Ω(T), while a bad period can only increase it by nT and has probability at most η(m+2n). A stochastic drift theorem for sequences with bounded moments then converts the negative drift of Φ into a uniform-in-time bound on its moments. Within a good period, the argument splits into two cases: all servers busy more than half the time (total clearing dominates total arrivals), or some server empty more than half the time (no-regret learning forces a long queue to shrink). The one-packet server buffer is what lets a queue exploit low-capacity servers by sending to them rarely.

What would settle it

Run 1,000 simulations of, say, n = 10 queues with arrival rates near 1/2 sending to a single server of capacity μ near 1 with a one-packet buffer, under EXP3, and record the maximum queue length over T = 50,000. If any queue's length grows linearly in T even though total arrivals are below (1/3)μ, Lemma 3's clearing-rate assumption is violated; conversely, if all queues stay bounded in that regime, the contention concern does not bite. The same experiment with n = 2 and n = 100 isolates whether the gap is due to contention.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: in a repeated game with n queues and m servers, if each queue uses any learning rule with sublinear regret that holds with high probability, if λ_i < 1/2 for every queue, and if Σ_i λ_i < (1/3) Σ_j μ_j, then the expected total number of packets waiting in the system is bounded by a constant at all times, despite uncoordinated selfish choices and servers that pick uniformly among simultaneously arriving packets. The same conclusion does not require timestamps or priority for older packets, which the prior no-buffer model needed. The proof works period by period: with a long enough window, either every server is busy more than half the time, in which case total service exceeds total arrivals, or some server's buffer is empty more than half the time, in which case the no-regret guarantee forces any queue with many packets to clear packets at a positive linear rate. A constructed example with one queue and many low-capacity servers shows that a total capacity of at least twice the arrival rate is necessary for a no-regret outcome to be stable, so the sufficient factor of 3 is not tight.

Load-bearing premise

The proof leans on a step where a queue that keeps sending to a server whose buffer is empty is assumed to clear about half its packets, even though if many queues target that same server each individual attempt is accepted with probability 1/n.

Editorial extensions

If this is right

  • Small, realistic buffers (one packet per server) turn a system that previously needed timestamps and large capacity reserves into one stable under a constant-factor capacity margin.
  • Any queue learning algorithm with high-probability sublinear regret, bandit or full information, inherits the stability guarantee; EXP3.P is an explicit example.
  • A capacity ratio of at least 2 is necessary in the worst case, so there is a concrete gap between the necessary lower bound and the sufficient factor of 3.
  • In randomized simulations of 5-queue, 6-server systems, the stable-to-unstable transition occurs above arriving-load 1/2 and below 1, suggesting typical systems clear packets much better than the worst-case bound.
  • Because buffers smooth the payoff stream across rounds, stability can be achieved without priority to older packets, which the no-buffer model could not avoid.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the factor-3 bound is not tight, a natural next step is to construct no-regret systems stable at every capacity ratio in (2,3); the paper's lower-bound technique with round-robin sending to equal low-capacity servers is a starting point.
  • The proof's 'empty server' case implicitly treats a queue's packet as accepted whenever it reaches an empty buffer; in systems where n queues all target the same empty server, each attempt succeeds with probability 1/n, so the per-queue clearing rate underlying Lemma 3 may need a contention-aware version.
  • The buffer-as-smoothing idea suggests a testable hypothesis for other carryover games: mechanisms that let an agent commit a resource now and receive the outcome later should improve the stability of no-regret learning dynamics in budgeted auctions and investment settings.
  • One could extend simulations to buffer sizes b > 1; if stability thresholds fall monotonically with b, the single-packet result is just the endpoint of a continuum.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper studies a repeated game between learning queues and servers with single-packet buffers. In each step, each nonempty queue sends one packet to a server; each server with an empty buffer accepts one of the packets arriving at it, chosen uniformly at random, and then attempts service. The main result (Theorem 1) claims that if each queue's arrival rate is below 1/2, the total arrival rate is below one third of the total service rate, and every queue uses a learning algorithm with high-probability sublinear regret, then the expected total number of packets in the system is uniformly bounded in time. The proof uses a potential function over T-step periods, with two cases: all servers busy more than half the period, or some server empty more than half the period. The paper also gives a lower-bound example requiring a factor-2 capacity margin (Theorem 3) and presents EXP3 simulations suggesting that systems remain stable at capacity ratios above 1/2.

Significance. If the main theorem were correct, it would be a substantial advance over the buffer-free model of Gaitonde and Tardos: a single-slot server buffer would remove the need for timestamps and priorities and reduce the required capacity over-coordination factor from 'hugely increased' to 3. The lower-bound example and the simulation study are useful first steps and give the reader a concrete picture of the threshold behavior. However, the central proof rests on a misapplication of the no-regret condition, so the theoretical contribution is not established in the present form.

major comments (3)
  1. [Lemma 3] The first paragraph of Lemma 3 states that if a queue has packets in every step of the window, Condition 3 implies it clears at least (1/2 - δ)T packets whenever some server's buffer is empty more than half the period. This ignores the model's step 2(ii): an empty server accepts one packet uniformly at random among all packets that arrive at it. If n queues send to that server on an empty step, each queue's expected reward for that step is 1/n, not 1. Consequently, the realized reward of the benchmark action 'always send to this server' is at most (#empty steps)/(#contending queues), not #empty steps, and no-regret only forces a clearing rate of roughly 1/n of the empty-server steps. The theorem's assumptions allow λ_i between 1/(2n) and 1/2, so the claimed (1/2 - λ_i - 2δ)T decrease can be negative even when the lemma's premise holds. Since the open-server case is one of only two sources of the Ω(T) potential drop in the proof of Theorem 1, this invalidates the main stability proof.
  2. [Condition 3 / Lemma 5] Condition 3 and Lemma 5 presuppose a well-defined notion of regret with a high-probability guarantee, but the paper never specifies the counterfactual rewards of actions not chosen. In this model, if a queue had played a different action in earlier steps, the servers' buffer states would have evolved differently, so the reward of an unchosen server is not defined by the observed history. Standard bandit algorithms such as EXP3.P.1 guarantee regret only when rewards are independent of the player's own actions; that assumption is violated here because a queue's past choices determine whether a server is busy when the queue returns to it. Until a precise regret benchmark is given and an algorithm satisfying Condition 3 is exhibited under that benchmark, Lemma 5 is an assumption rather than a proved statement, and the theorem's hypothesis 'low regret with high probability' is not known to be instantiable.
  3. [Lemma 3, second case] The second half of Lemma 3 uses the quantity I, 'the number of steps queue i and the server were empty,' but Lemma 3's premise only asserts existence of some server that is empty more than half the steps; the proof does not show that this server is the one queue i sends to, nor that queue i's sends are the only ones contending for it. The inequality N'_i ≤ ... and the resulting potential decrease for queues with at least T packets therefore inherit the same unsupported clearing bound as the first paragraph. The proof would need an aggregate argument over all queues' no-regret guarantees rather than a per-queue bound against an unspecified empty server.
minor comments (6)
  1. [Section 3] In the paragraph after Theorem 2, 'the change in this potential satisfies the conditions of Theorem 1' should refer to Theorem 2.
  2. [Section 3, Lemma 4] The line 'F or any constants δ >0 and η >0' has a missing space: it should read 'For any constants...'.
  3. [Theorem 3 proof] The sentence 'Assume that the server chooses a uniform random server at each step' should read 'the queue chooses a uniform random server at each step'.
  4. [Lemma 1 proof] The quantity 23/24 is an upper bound on the expected number of packets accepted per step, but the text calls it 'maximum expected service rate'; please clarify the distinction between acceptance into a buffer and service completion.
  5. [References] The two entries for Auer, Cesa-Bianchi, Freund, and Schapire (2002) are the same paper listed twice; please consolidate them.
  6. [Section 4.3] The claim that dynamics 'converge in last iterate (up to a small noise level)' is informal; please state the convergence notion precisely and quantify the noise level.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 1 is derived from stated no-regret and arrival-rate assumptions via a potential argument, not from its own conclusion.

full rationale

The paper's main derivation is self-contained. Theorem 1 is proved from the stated assumptions (Σ_i λ_i < (1/3)Σ_j μ_j, λ_i < 1/2, and high-probability low-regret learning) using a potential function and the Pemantle–Rosenthal negative-drift theorem. The key lemmas (Lemmas 2 and 3) rely on the three good-δ conditions, which are either concentration bounds (Lemmas 4 and 5) or the assumed no-regret guarantee; no fitted parameter is renamed as a prediction. The lower bound in Theorem 3 is constructed from an explicit no-regret sending strategy, so it is an input example rather than a restatement of the theorem's conclusion. Self-citations to Gaitonde and Tardos and to Kolumbus and Nisan are contextual and not load-bearing; no uniqueness theorem is imported from the authors' prior work to force the modeling choice. The potential issue in Lemma 3—that a queue's packet is treated as accepted whenever sent to an empty server, despite the model's uniform-random selection among simultaneous arrivals—is a potential soundness gap in the proof, not a circular derivation: Condition 3 is an input assumption, and the lemma's clearing bound is not equivalent to the stability conclusion by definition. Therefore no significant circularity is present.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The proof rests on standard moment arguments and the no-regret learning assumption. No free parameters are fitted; δ and η are proof constants chosen small. No new entities are postulated.

assumptions (3)
  • standard math Pemantle-Rosenthal theorem: a nonnegative sequence with negative drift when large and bounded p-th moments is uniformly bounded in L^r for r < p-1.
    Invoked as Theorem 2 in Section 3 to convert expected decrease of the potential function into a bounded expectation.
  • domain assumption Queues use learning algorithms with high-probability sublinear regret, for example EXP3.P.
    The main theorem's Condition 3 and Lemma 5 rely on this property; the paper cites Auer et al. 2002 for an algorithm that satisfies it.
  • standard math The goodδ concentration conditions hold with high probability for large T via Chernoff and union bounds.
    Used in Lemmas 4 and 5 to bound the probability that a period fails any of the three conditions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Learning in Strategic Queuing Systems with Small Buffers." pith.science (2026). https://pith.science/paper/GPPOG7AT

@misc{pith2026250208898,
  author       = {Pith},
  title        = {Pith review of: Learning in Strategic Queuing Systems with Small Buffers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GPPOG7AT}},
  note         = {Machine review of arXiv:2502.08898}
}
read the original abstract

We consider learning outcomes in games with carryover effects between rounds: when outcomes in the present round affect the game in the future. An important example of such systems is routers in networking, as they use simple learning algorithms to find the best way to deliver packets to their desired destination. This simple, myopic, and distributed decision process makes large queuing systems easy to operate, but at the same time, the system needs more capacity than would be required if all traffic were centrally coordinated. Gaitonde and Tardos (EC 2020 and JACM 2023) initiated the study of such systems, modeling them as an infinitely repeated game in which routers compete for servers and the system maintains a state (the number of packets held at each queue) that results from outcomes of previous rounds. However, their model assumes that servers have no buffers at all, so routers have to resend all packets that were not served successfully, which makes their system model unrealistic. They show that in their model, even with hugely increased server capacity relative to what is needed in the centrally coordinated case, ensuring that the system is stable requires the use of timestamps and priority for older packets. We consider a system with two important changes, which make the model more realistic and allow for much higher traffic rates: first, we add a very small buffer to each server, allowing the server to hold on to a single packet to be served later (if it fails to serve it immediately), and second, we do not require timestamps or priority to older packets. Using theoretical analysis and simulations, we show that when queues are learning, a small constant-factor increase in server capacity, compared to what would be needed if centrally coordinating, suffices to keep the system stable, even if servers select randomly among packets arriving simultaneously.

Figures

Figures reproduced from arXiv: 2502.08898 by the authors.

Figure 1
Figure 1. A system with three queues and three servers in a single [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Empirical buildup of total queue sizes normalized by [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. A comparison of identical systems with and without buffers. [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Dynamics of probability distributions and the empirical play across different scenarios. [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references · 30 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION fin.entry add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION new.sentence output.state after.block = 'skip output.state before.all = 'skip after.sentence 'output.state := if if FUNCTION not #0 #1 if FUNCTION and 'skip pop #0 if FUNCTIO...

  2. [2]

    Schapire

    Peter Auer, Nicol \` o Cesa - Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM J. Comput. , 32(1):48--77, 2002

    work page 2002

  3. [3]

    The nonstochastic multiarmed bandit problem

    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

    work page 2002

  4. [4]

    Circumventing the price of anarchy: Leading dynamics to good behavior

    Maria - Florina Balcan, Avrim Blum, and Yishay Mansour. Circumventing the price of anarchy: Leading dynamics to good behavior. SIAM J. Comput. , 42(1):230--264, 2013

    work page 2013

  5. [5]

    Balseiro and Yonatan Gur

    Santiago R. Balseiro and Yonatan Gur. Learning in repeated auctions with budgets: Regret minimization and equilibrium. Manag. Sci. , 65(9):3952--3968, 2019

    work page 2019

  6. [6]

    Strategic Behavior and No-Regret Learning in Queueing Systems

    Lucas Baudin, Marco Scarsini, and Xavier Venel. Strategic behavior and no-regret learning in queueing systems. CoRR , abs/2302.03614, 2023

    work page Pith review arXiv 2023

  7. [7]

    A comprehensive survey of multiagent reinforcement learning

    Lucian Busoniu, Robert Babuska, and Bart De Schutter. A comprehensive survey of multiagent reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews) , 38(2):156--172, 2008

    work page 2008

  8. [8]

    Liquid welfare guarantees for no-regret learning in sequential budgeted auctions

    Giannis Fikioris and \'E va Tardos. Liquid welfare guarantees for no-regret learning in sequential budgeted auctions. In Proceedings of the 24th ACM Conference on Economics and Computation , pages 678--698, 2023

    work page 2023

Show all 32 references
  1. [9]

    Learning in budgeted auctions with spacing objectives

    Giannis Fikioris, Robert Kleinberg, Yoav Kolumbus, Raunak Kumar, Yishay Mansour, and \'E va Tardos. Learning in budgeted auctions with spacing objectives. arXiv preprint arXiv:2411.04843 , 2024

    2024 arXiv

  2. [10]

    Efficient decentralized multi-agent learning in asymmetric queuing systems

    Daniel Freund, Thodoris Lykouris, and Wentao Weng. Efficient decentralized multi-agent learning in asymmetric queuing systems. In Po - Ling Loh and Maxim Raginsky, editors, Conference on Learning Theory, 2-5 July 2022, London, UK , volume 178 of Proceedings of Machine Learning...

    2022

  3. [11]

    Quantifying the cost of learning in queueing systems

    Daniel Freund, Thodoris Lykouris, and Wentao Weng. Quantifying the cost of learning in queueing systems. In NeurIPS , 2023

    2023

  4. [12]

    Stability of decentralized queueing networks beyond complete bipartite cases

    Hu Fu, Qun Hu, and Jia'nan Lin. Stability of decentralized queueing networks beyond complete bipartite cases. In Kristoffer Arnsfelt Hansen, Tracy Xiao Liu, and Azarakhsh Malekian, editors, Web and Internet Economics - 18th International Conference, WINE 2022, Troy, NY, USA, D...

    2022

  5. [13]

    Stability and learning in strategic queuing systems

    Jason Gaitonde and \' E va Tardos. Stability and learning in strategic queuing systems. In P \' e ter Bir \' o , Jason D. Hartline, Michael Ostrovsky, and Ariel D. Procaccia, editors, EC '20: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, July 13...

    2020

  6. [14]

    The price of anarchy of strategic queuing systems

    Jason Gaitonde and \' E va Tardos. The price of anarchy of strategic queuing systems. J. ACM , 70(3):20:1--20:63, 2023

    2023

  7. [15]

    Budget pacing in repeated auctions: Regret and efficiency without convergence

    Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins. Budget pacing in repeated auctions: Regret and efficiency without convergence. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2...

    2023

  8. [16]

    Analysis of markovian arrivals and service with applications to intermittent overload

    Isaac Grosof, Yige Hong, and Mor Harchol - Balter. Analysis of markovian arrivals and service with applications to intermittent overload. CoRR , abs/2405.04102, 2024

    2024 arXiv

  9. [17]

    The RESET and MARC techniques, with application to multiserver-job analysis

    Isaac Grosof, Yige Hong, Mor Harchol - Balter, and Alan Scheller - Wolf. The RESET and MARC techniques, with application to multiserver-job analysis. SIGMETRICS Perform. Evaluation Rev. , 51(4):6--7, 2024

    2024

  10. [18]

    To Queue or Not to Queue: Equilibrium Behavior in Queueing Systems

    Refael Hassin and Moshe Haviv. To Queue or Not to Queue: Equilibrium Behavior in Queueing Systems . International Operations Resea. Springer US, 2003

    2003

  11. [19]

    Rational Queueing

    Refael Hassin. Rational Queueing . Chapman and Hall/CRC Series in Operations Research Series. CRC Press, 2020

    2020

  12. [20]

    Auctions between regret-minimizing agents

    Yoav Kolumbus and Noam Nisan. Auctions between regret-minimizing agents. In Proceedings of the ACM Web Conference 2022 , pages 100--111, 2022

    2022

  13. [21]

    How and why to manipulate your own agent: On the incentives of users of learning agents

    Yoav Kolumbus and Noam Nisan. How and why to manipulate your own agent: On the incentives of users of learning agents. Advances in Neural Information Processing Systems , 35:28080--28094, 2022

    2022

  14. [22]

    Papadimitriou

    Elias Koutsoupias and Christos H. Papadimitriou. Worst-case equilibria. In STACS 99, 16th Annual Symposium on Theoretical Aspects of Computer Science , pages 404--413. Springer, 1999

    1999

  15. [23]

    Regret of queueing bandits

    Subhashini Krishnasamy, Rajat Sen, Ramesh Johari, and Sanjay Shakkottai. Regret of queueing bandits. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain , pages 1669--1677, 2016

    2016

  16. [24]

    Markov games as a framework for multi-agent reinforcement learning

    Michael L Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994 , pages 157--163. Elsevier, 1994

    1994

  17. [25]

    Moment conditions for a sequence with negative drift to be uniformly bounded in L ^r

    Robin Pemantle and Jeffrey S Rosenthal. Moment conditions for a sequence with negative drift to be uniformly bounded in L ^r . Stochastic Processes and their Applications , 82(1):143--155, 1999

    1999

  18. [26]

    Intrinsic robustness of the price of anarchy

    Tim Roughgarden. Intrinsic robustness of the price of anarchy. J. ACM , 62(5):32:1--32:42, 2015

    2015

  19. [27]

    Decentralized learning in online queuing systems

    Flore Sentenac, Etienne Boursier, and Vianney Perchet. Decentralized learning in online queuing systems. In NeurIPS , 2021

    2021

  20. [28]

    Fundamentals of Queueing Theory

    John F Shortle, James M Thompson, Donald Gross, and Carl M Harris. Fundamentals of Queueing Theory . Wiley, 2018

    2018

  21. [29]

    Introduction to multi-armed bandits

    Aleksandrs Slivkins. Introduction to multi-armed bandits. Found. Trends Mach. Learn. , 12(1-2):1--286, 2019

    2019

  22. [30]

    Composable and efficient mechanisms

    Vasilis Syrgkanis and \' E va Tardos. Composable and efficient mechanisms. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013 , pages 211--220. ACM , 2013

    2013

  23. [31]

    Learning and Information in Stochastic Networks and Queues , chapter 6, pages 161--198

    Neil Walton and Kuang Xu. Learning and Information in Stochastic Networks and Queues , chapter 6, pages 161--198. 2021

    2021

  24. [32]

    Multi-agent reinforcement learning: A selective overview of theories and algorithms

    Kaiqing Zhang, Zhuoran Yang, and Tamer Ba s ar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of reinforcement learning and control , pages 321--384, 2021

    2021

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.