aiqbench analysis
This research investigates packet routing in data center networks where queues utilize no-regret learning algorithms to manage servers with limited, single-packet buffers. The study establishes theoretical bounds on system stability and throughput, demonstrating that simple learning agents can achieve near-optimal performance even when competing for scarce resources. By resolving an open question regarding overprovisioning factors, the work provides critical insights into designing robust, self-optimizing network infrastructures without relying on global coordination.
Learning in Strategic Queuing with Geometric Recharge: From Bandits to Systems
arXiv:2610.19179v1 Announce Type: cross Abstract: We study packet routing in queuing systems where queues act as selfish, myopic agents that use no-regret learning algorithms to select servers with unknown service rates. To model the small buffers used in data centers, we assume that each server has a single-packet buffer. Even such a tiny buffer already captures the features of buffering: routers can exploit multiple servers while accepted packets remain in service, but packets can occupy servers for multiple rounds, complicating future service and learning. We first analyze a single queue routing packets to $m$ buffered servers with service rates $\mu_1, \dots, \mu_m$. This setting is equivalent to an instance of the recharging bandits problem with geometric recharge. We prove that any no-regret learner achieves a long-run average throughput of at least the Hamacher sum of the server rates, and that this bound is tight. Consequently, a single no-regret queue is stable if and only if its arrival rate is below the Hamacher sum of the server rates. Moreover, comparing against an optimal policy, we show that any no-regret learner is at least $0.77$-competitive, which is also tight. We then study multi-queue systems where $n$ queues with arrival rates $\lambda_1, \dots, \lambda_n$, each at most $\lambda_{\max}$, compete for service from $m$ buffered servers. We show that the smallest overprovisioning factor that guarantees the system to be stable under high-probability no-regret learning is $\frac{1}{1-\lambda_{\max}}$. Equivalently, in terms of the total arrival and service rates, the condition $\sum_{i=1}^n \lambda_i < (1-\lambda_{\max})\sum_{j=1}^m \mu_j$ is sufficient, and sometimes necessary, for stability under no-regret learning. In particular, for $\lambda_{\max} = 1/2$, this improves the upper bound of Abel et al. (EC 2026) from $3$ to $2$, matching their lower bound and resolving their open question.
Abstract:We study packet routing in queuing systems where queues act as selfish, myopic agents that use no-regret learning algorithms to select servers with unknown service rates. To model the small buffers used in data centers, we assume that each server has a single-packet buffer. Even such a tiny buffer already captures the features of buffering: routers can exploit multiple servers while accepted packets remain in service, but packets can occupy servers for multiple rounds, complicating future service and learning. We first analyze a single queue routing packets to $m$ buffered servers with service rates $\mu_1, \dots, \mu_m$. This setting is equivalent to an instance of the recharging bandits problem with geometric recharge. We prove that any no-regret learner achieves a long-run average throughput of at least the Hamacher sum of the server rates, and that this bound is tight. Consequently, a single no-regret queue is stable if and only if its arrival rate is below the Hamacher sum of the server rates. Moreover, comparing against an optimal policy, we show that any no-regret learner is at least $0.77$-competitive, which is also tight. We then study multi-queue systems where $n$ queues with arrival rates $\lambda_1, \dots, \lambda_n$, each at most $\lambda_{\max}$, compete for service from $m$ buffered servers. We show that the smallest overprovisioning factor that guarantees the system to be stable under high-probability no-regret learning is $\frac{1}{1-\lambda_{\max}}$. Equivalently, in terms of the total arrival and service rates, the condition $\sum_{i=1}^n \lambda_i < (1-\lambda_{\max})\sum_{j=1}^m \mu_j$ is sufficient, and sometimes necessary, for stability under no-regret learning. In particular, for $\lambda_{\max} = 1/2$, this improves the upper bound of Abel et al. (EC 2026) from $3$ to $2$, matching their lower bound and resolving their open question.
Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG); Performance (cs.PF)
arXiv:2610.19179 [cs.GT]
(or arXiv:2610.19179v1 [cs.GT] for this version)
https://doi.org/10.48550/arXiv.2610.19179 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 386 words
Related coverage
Choosing LLMs for Strategic Agent Interactions
arXiv · Oct 15, 2026
Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret
arXiv · Oct 7, 2026
Geometry-Aware Reinforcement Learning for 2D Irregular Nesting
arXiv · Jun 10, 2026
Constrained Command-Conditioned Reinforcement Learning with Bandit Strategy Selection in Real-Time Strategy Games
arXiv · Oct 10, 2026