自适应学习服务速率，实现异构服务器的最优负载均衡。
Learning Adaptive SED for heterogeneous load balancing
- 在线学习算法边探索边优化路由策略。
- 理论证明可实现有限遗憾，非传统对数增长。
- 适合动态环境下的实时系统调度决策者。
我们研究一个具有未知异构服务速率的双服务器负载均衡系统。目标是按最短期望延迟（SED）策略分配任务，但该策略依赖于服务速率的准确知识。基于估计值的启发式策略表现不佳：由于估计误差，其与理想策略在状态空间的无限区域内存在分歧。为此，我们提出一种在线学习算法，在学习服务速率的同时收敛至SED策略。算法通过精心设计的强制探索阶段确保对两个服务器的充分采样。理论上证明该算法可实现有限遗憾，这与经典多臂赌博机中遗憾随时间对数增长的情形不同。数值实验验证了算法性能，并揭示了强制探索在特定场景下尤为有效。
原文摘要 · Abstract (English)
We study a two-server load balancing system with heterogeneous service rates that are a priori unknown to the dispatcher. The goal is to route customers according to the Shortest--Expected--Delay (SED) policy, but this requires knowledge of the service rates. Empirical policies that route based on estimates perform poorly: due to estimation error, the empirical policy disagrees with the oracle on an infinite region of the state space. We propose an online learning algorithm that converges to SED while learning the service rates. The algorithm carefully balances empirical SED routing with forced exploration phases that guarantee sufficient sampling of both servers. We prove that our algorithm achieves finite regret; this differs from classical Multi-Armed Bandit settings where regret typically grows logarithmically in time. Finally, numerical experiments demonstrate the performance of our algorithm and highlight the regimes in which forced exploration is especially beneficial.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。