Efficient Decentralized Multi-agent Learning in Asymmetric Bipartite Queueing Systems
- 1 May 2024
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 72 (3) , 1049-1070
Abstract
New Algorithm Enables Efficient Decentralized Learning in Bipartite Queueing Systems Bipartite queueing systems, where agents with individual job queues request service from a pool of heterogeneous servers, are standard models for service applications like data networks and call centers. Traditionally, a central controller schedules agent requests with full knowledge of system parameters. However, emerging applications require decentralized operation without this central coordination or complete system information. This presents challenges as agents lack the global knowledge needed to efficiently route jobs. Recent research into efficient decentralized learning algorithms for such systems faces limitations in nonoptimal throughput, demanding computations, or degrading efficiency with exponential queue growth. In contrast, this paper introduces an algorithm that enables queues to efficiently learn decentralized scheduling policies while ensuring throughput optimality. The approach is computationally lightweight, achieving queue length bounds that scale polynomially rather than exponentially in system size. Experiments demonstrate faster convergence and robustness of our algorithm compared with prior decentralized algorithms.Keywords
All Related Versions
This publication has 36 references indexed in Scilit:
- Two queues with non-stochastic arrivalsOperations Research Letters, 2014
- Service-Level Differentiation in Many-Server Service Systems via Queue-Ratio RoutingOperations Research, 2010
- Sufficient conditions for stability of longest-queue-first scheduling: second-order properties using fluid limitsAdvances in Applied Probability, 2006
- Scheduling Flexible Servers with Convex Delay Costs: Heavy-Traffic Optimality of the Generalized cμ-RuleOperations Research, 2004
- MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy trafficThe Annals of Applied Probability, 2004
- The Complexity of Optimal Queuing Network ControlMathematics of Operations Research, 1999
- Dynamic server allocation to parallel queues with randomly varying connectivityIEEE Transactions on Information Theory, 1993
- Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networksIEEE Transactions on Automatic Control, 1992
- The auction algorithm: A distributed relaxation method for the assignment problemAnnals of Operations Research, 1988
- Multi-Item AuctionsJournal of Political Economy, 1986