在未知服务速率下，实现多队列多服务器系统的稳定调度与学习。
Queueing Matching Bandits with Preference Feedback
- 基于UCB和汤普森采样设计自适应调度算法。
- 系统队列长度平均控制在$O(\min\{N,K\}/ε)$以内。
- 适合高并发场景下的动态资源分配研究者参考。
本文研究由$N$个队列与$K$个服务器组成的异构排队系统，作业随机到达队列，每个作业-服务器匹配的服务速率未知，以基于特征的多项式对数（MNL）函数建模。每时刻调度器将作业分配至服务器，各服务器根据偏好随机服务最多一个作业。目标是在学习服务速率的同时使系统稳定。我们提出基于上置信界（UCB）和汤普森采样（Thompson Sampling）的算法，在长时域$T$下实现系统稳定，平均队列长度为$O(\min\{N,K\}/ε)$，其中$ε$为系统流量松弛度。同时，算法达到次线性遗憾界$\tilde{O}(\min\{\sqrt{T} Q_{\max},T^{3/4}\})$，其中$Q_{\max}$为任意时间点的最大队列长度。实验验证了算法性能。
原文摘要 · Abstract (English)
In this study, we consider multi-class multi-server asymmetric queueing systems consisting of $N$ queues on one side and $K$ servers on the other side, where jobs randomly arrive in queues at each time. The service rate of each job-server assignment is unknown and modeled by a feature-based Multi-nomial Logit (MNL) function. At each time, a scheduler assigns jobs to servers, and each server stochastically serves at most one job based on its preferences over the assigned jobs. The primary goal of the algorithm is to stabilize the queues in the system while learning the service rates of servers. To achieve this goal, we propose algorithms based on UCB and Thompson Sampling, which achieve system stability with an average queue length bound of $O(\min\{N,K\}/ε)$ for a large time horizon $T$, where $ε$ is a traffic slackness of the system. Furthermore, the algorithms achieve sublinear regret bounds of $\tilde{O}(\min\{\sqrt{T} Q_{\max},T^{3/4}\})$, where $Q_{\max}$ represents the maximum queue length over agents and times. Lastly, we provide experimental results to demonstrate the performance of our algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。