Efficient decentralized multi-agent learning in asymmetric queuing systems

Daniel Freund, Thodoris Lykouris, Wentao Weng
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:4080-4084, 2022.

Abstract

We study decentralized multi-agent learning in bipartite queuing systems, a standard model for service systems. In particular, N agents request service from K servers in a fully decentralized way, i.e, 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 queuing systems while also having additional robustness properties. Along the way, we provide the first UCB-based algorithm for the centralized case of the problem, which resolves an open question by Krishnasamy et al.

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-freund22a, title = {Efficient decentralized multi-agent learning in asymmetric queuing systems}, author = {Freund, Daniel and Lykouris, Thodoris and Weng, Wentao}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {4080--4084}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/freund22a/freund22a.pdf}, url = {https://proceedings.mlr.press/v178/freund22a.html}, abstract = {We study decentralized multi-agent learning in bipartite queuing systems, a standard model for service systems. In particular, N agents request service from K servers in a fully decentralized way, i.e, 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 queuing systems while also having additional robustness properties. Along the way, we provide the first UCB-based algorithm for the centralized case of the problem, which resolves an open question by Krishnasamy et al.} }
Endnote
%0 Conference Paper %T Efficient decentralized multi-agent learning in asymmetric queuing systems %A Daniel Freund %A Thodoris Lykouris %A Wentao Weng %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-freund22a %I PMLR %P 4080--4084 %U https://proceedings.mlr.press/v178/freund22a.html %V 178 %X We study decentralized multi-agent learning in bipartite queuing systems, a standard model for service systems. In particular, N agents request service from K servers in a fully decentralized way, i.e, 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 queuing systems while also having additional robustness properties. Along the way, we provide the first UCB-based algorithm for the centralized case of the problem, which resolves an open question by Krishnasamy et al.
APA
Freund, D., Lykouris, T. & Weng, W.. (2022). Efficient decentralized multi-agent learning in asymmetric queuing systems. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:4080-4084 Available from https://proceedings.mlr.press/v178/freund22a.html.

Related Material