One-packet buffers let no-regret learners keep queues stable, and the extra capacity needed is now exact
Synopsis
In a queuing system where each server holds a single packet, every queue runs an off-the-shelf no-regret learning algorithm without coordination or knowledge of service rates. Analysis shows a single queue's long-run throughput is at least the Hamacher sum of the service rates, a tight bound, and that a multi-queue system with arrival rates capped at λ needs an overprovisioning factor of exactly 1/(1-λ), tightening the prior 2-to-4 range to 2 at λ=1/2 and approaching 1 as λ vanishes.
Interpretation
With a one-packet buffer per server, a single queue running an ordinary no-regret learner can draw on the capacity of several servers at once instead of locking onto one best server. In the earlier bufferless model a packet could only be cleared in the step it was sent, so stability required one server whose service rate exceeded the arrival rate, reducing the task to finding that server. The analysis shows any no-regret learner attains long-run average throughput of at least the Hamacher sum of the service rates, the total odds divided by one plus the total odds, and that a stationary policy sampling arms in proportion to their odds attains this bound.
When many queues compete for buffered servers, the extra service capacity required for stability has an exact value rather than a range. Previously, with arrival rates capped at 1/2, the overprovisioning factor was only known to lie between 2 and 4. When every queue's arrival rate is at most λ, an overprovisioning factor of 1/(1-λ) is both sufficient and necessary under high-probability no-regret learning; at λ=1/2 this is 2, matching the existing lower bound, and it approaches 1 as λ shrinks.
The guarantee does not depend on how a server chooses among packets arriving in the same round. The stability result holds under arbitrary server priority rules. The matching single-queue example has no competing packets, so changing priorities alone cannot reduce the worst-case overprovisioning.
Perspective
The results assume a queuing model in which each server holds a single packet and queues use learning algorithms with the no-regret property, with the multi-queue result requiring high-probability no regret; the single-queue simulations use EXP3 on a three-arm and a seven-arm service-rate instance.
The multi-queue tightness comes from a single-queue example with no competing packets; how the required overprovisioning scales with buffer size, network topology and the feedback available to queues remains an open question.
