Decentralized Learning in Online Queuing Systems
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 \textit{stable}) 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 $\frac{e}{e-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 \textit{patient} 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.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
AIMD scheduling and resource allocation in distributed computing systems
We consider the problem of simultaneous scheduling and resource allocation of an incoming flow of requests to a set of computing units. By representing each computing unit as a node, we model the overall system as a mult…
Distributed ComputingSchedulingLFQ: Online Learning of Per-flow Queuing Policies using Deep Reinforcement Learning
The increasing number of different, incompatible congestion control algorithms has led to an increased deployment of fair queuing. Fair queuing isolates each network flow and can thus guarantee fairness for each flow eve…
Deep Reinforcement LearningFairnessManagementreinforcement-learning+1Queuing for Civility: Regulating Emotions and Reducing Toxicity in Digital Discourse
The pervasiveness of online toxicity, including hate speech and trolling, disrupts digital interactions and online well-being. Previous research has mainly focused on post-hoc moderation, overlooking the real-time emotio…
Transition of $α$-mixing in Random Iterations with Applications in Queuing Theory
Nonlinear time series models with exogenous regressors are essential in econometrics, queuing theory, and machine learning, though their statistical analysis remains incomplete. Key results, such as the law of large numb…
EconometricsTime SeriesA Hysteretic Q-learning Coordination Framework for Emerging Mobility Systems in Smart Cities
Connected and automated vehicles (CAVs) can alleviate traffic congestion, air pollution, and improve safety. In this paper, we provide a decentralized coordination framework for CAVs at a signal-free intersection to mini…
Q-Learningreinforcement-learningReinforcement Learning (RL)