# Decentralized Learning in Online Queuing Systems

arXiv: https://arxiv.org/abs/2106.04228 · HTML: https://mlsanity.com/paper/2106.04228/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 39 references that are in the map.
- First posted on arXiv 8 Jun 2021.

## Builds on (most cited first, 13 of 13)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Competing Bandits in Matching Markets](https://mlsanity.com/paper/1906.05363/) (2019)
- [SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits](https://mlsanity.com/paper/1809.08151/) (2018)
- [Bandit Learning in Decentralized Matching Markets](https://mlsanity.com/paper/2012.07348/) (2020)
- [Beyond log2(T) Regret for Decentralized Bandits in Matching Markets](https://mlsanity.com/paper/2103.07501/) (2021)
- [A Practical Algorithm for Multiplayer Bandits when Arm Means Vary Among Players](https://mlsanity.com/paper/1902.01239/) (2019)
- [Approachability, Regret and Calibration; implications and equivalences](https://mlsanity.com/paper/1301.2663/) (2013)
- [Multi-Armed Bandit Learning in IoT Networks: Learning helps even in non-stationary settings](https://mlsanity.com/paper/1807.00491/) (2018)
- [Selfish Robustness and Equilibria in Multi-Player Bandits](https://mlsanity.com/paper/2002.01197/) (2020)
- [Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions](https://mlsanity.com/paper/2011.03896/) (2020)
- [Stability and Learning in Strategic Queuing Systems](https://mlsanity.com/paper/2003.07009/) (2020)
- [Dominate or Delete: Decentralized Competing Bandits in Serial Dictatorship](https://mlsanity.com/paper/2006.15166/) (2020)
- [Virtues of Patience in Strategic Queuing Systems](https://mlsanity.com/paper/2011.10205/) (2020)

## Built on by (most cited first, 8 of 8)

- [A survey on multi-player bandits](https://mlsanity.com/paper/2211.16275/) (2022)
- [Queue Length Regret Bounds for Contextual Queueing Bandits](https://mlsanity.com/paper/2601.19300/) (2026)
- [Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret](https://mlsanity.com/paper/2606.09668/) (2026)
- [Learning in Strategic Queuing Systems with Small Buffers](https://mlsanity.com/paper/2502.08898/) (2025)
- [Learning to Schedule in Parallel-Server Queues with Stochastic Bilinear Rewards](https://mlsanity.com/paper/2112.06362/) (2021)
- [Constant or logarithmic regret in asynchronous multiplayer bandits](https://mlsanity.com/paper/2305.19691/) (2023)
- [Competitive Multi-armed Bandit Games for Resource Sharing](https://mlsanity.com/paper/2503.20975/) (2025)
- [Learning in Strategic Queuing with Geometric Recharge: From Bandits to Systems](https://mlsanity.com/paper/2610.19179/) (2026)

## Abstract (arXiv)

Motivated by packet routing in computer 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 textitstable) 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 fracee-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 textitpatient 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.