Learning Outcomes in Queueing Systems
summary
Queues arrive at rate λ, choose one server per round, and run no-regret learning while servers serve one random or timestamp-prioritized packet per round. Main claims: with uniform random selection selfish queues can require up to Θ(n) extra capacity, whereas with timestamp priority a factor of two server capacity above the coordinated optimum guarantees stability (tight). Proof uses a potential-function showing negative drift plus a Pimentel–Rosenthal concentration tool; multi-armed bandit intuition guides single-queue behavior.
AI-written summary · about
chapters (13)
- 0:00Intro
- 1:16Example of a repeated game: traffic routing
- 3:34Social Welfare: Price of Anarchy and Learning
- 4:03Social Welfare of Learning Outcomes
- 4:40Large population games: traffic routing
- 6:32Model of Learning in a Queuing System
- 7:58Our Main Question
- 10:48Baseline Measure: Coordinated Queues queues
- 12:02How Do Servers Choose Between Packets?
- 13:51Why Uniform Selection Fails
- 17:01Proof Ideas
- 21:00Extra Technical Details
- 23:16Summary and Future Directions
related talks
48mA Simple Condition for Constant Regret in Online Decision-Making
40mA Bayesian Approach to Online Resource Allocation
31mAvoiding Cascading Failures for Time-of-Use Pricing
30mOnline Paging with a Vanishing Regret
43mLearning about Auctions
44mParsimonious Learning-Augmented Algorithms
58mMemory-Regret Tradeoff for Online Learning
01h 14mCompetitive Analysis Meets Stochastic Input: Secretary Problems And Prophet Inequalities