边学习边调度：在技能匹配中自适应优化客户与服务者配对收益
Learning payoffs while routing in skill-based queues
- 用线性规划基础解作为调度动作空间，实现动态学习与决策
- 理论证明算法达到多对数级遗憾，接近最优性能
- 适用于客户-服务者收益未知且环境变化的动态服务系统
受服务系统应用启发，本文研究需由具备相应技能的服务者处理的排队系统。目标是优化客户路由策略以最大化客户-服务者匹配总收益。假设客户-服务者相关的收益参数事先未知，提出一种机器学习算法，在最大化总收益的同时自适应学习这些参数，并证明其遗憾为多对数级。进一步通过推导遗憾下界，证明该算法在渐近意义上近乎最优（仅差对数项）。算法利用静态线性规划的基本可行解作为动作空间，其遗憾分析通过研究队列长度过程收敛至稳态行为来克服排队与学习之间的复杂耦合。数值实验验证了算法性能，并在时变参数场景下展示了其在非静态环境中的潜力。
原文摘要 · Abstract (English)
Motivated by applications in service systems, we consider queueing systems where each customer must be handled by a server with the right skill set. We focus on optimizing the routing of customers to servers in order to maximize the total payoff of customer--server matches. In addition, customer--server dependent payoff parameters are assumed to be unknown a priori. We construct a machine learning algorithm that adaptively learns the payoff parameters while maximizing the total payoff and prove that it achieves polylogarithmic regret. Moreover, we show that the algorithm is asymptotically optimal up to logarithmic terms by deriving a regret lower bound. The algorithm leverages the basic feasible solutions of a static linear program as the action space. The regret analysis overcomes the complex interplay between queueing and learning by analyzing the convergence of the queue length process to its stationary behavior. We also demonstrate the performance of the algorithm numerically, and have included an experiment with time-varying parameters highlighting the potential of the algorithm in non-static environments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。