We study decentralized multi-agent 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, 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 queueing systems while also having additional robustness properties. Along the way, we provide the first provably efficient UCB-based algorithm for the centralized case of the problem.
翻译：摘要：我们研究了分散式多智能体学习在二分队列系统中的应用，这是一种典型的服务系统模型。特别地，N个智能体以完全分散方式申请K个服务器提供服务，即通过运行相同的算法进行无需通信的处理。之前的分散式算法局限于对称系统，其性能在服务器数量不断增加时呈指数级减退，需要通过共享随机性和唯一的智能体身份进行通信，并且需要进行大量的计算。相比之下，我们提供了一种简单的分散式学习算法，当各个智能体分别运行时，能够使得队列系统在一般的非对称二分队列系统中具有高效的性能，并同时具有额外的鲁棒性。顺便提一句，我们还提供了该问题集中式情况下的第一个经过证明的有效 UCB 算法。
相关内容
微信扫码咨询专知VIP会员