Efficient Decentralized Multi-agent Learning in Asymmetric Bipartite Queueing Systems
针对二分排队系统中缺乏中央协调的场景，提出一种计算轻量、吞吐量最优的去中心化学习算法，使队列能高效学习调度策略，队列长度随系统规模多项式增长而非指数增长，实验显示收敛更快且更鲁棒。
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.