Efficient Decentralized Multi-agent Learning in Asymmetric Bipartite Queueing Systems

Daniel Freund (), Thodoris Lykouris () and Wentao Weng ()
Additional contact information
Daniel Freund: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142
Thodoris Lykouris: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142
Wentao Weng: Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142

Operations Research, 2024, vol. 72, issue 3, 1049-1070

Abstract: We study decentralized multiagent learning in bipartite queueing systems, a standard model for service systems. In particular, N agents request service from K servers in a fully decentralized way, that is, by running the same algorithm without communication. Previous decentralized algorithms are restricted to symmetric systems, have performance that is degrading exponentially in the number of servers, require communication through shared randomness and unique agent identities, and are computationally demanding. In contrast, we provide a simple learning algorithm that, when run decentrally by each agent, leads the queueing system to have efficient performance in general asymmetric bipartite queueing systems while also having additional robustness properties. Along the way, we provide the first provably efficient upper confidence bound–based algorithm for the centralized case of the problem.

Keywords: Machine Learning and Data Science; service systems; multiarmed bandits; decentralization (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.0291 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:72:y:2024:i:3:p:1049-1070

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().