Efficient Reinforcement Learning for Routing Jobs in Heterogeneous Queueing Systems

📄 arXiv: 2402.01147v2 📥 PDF

作者: Neharika Jali, Guannan Qu, Weina Wang, Gauri Joshi

分类: cs.LG, cs.PF

发布日期: 2024-02-02 (更新: 2024-04-22)

备注: AISTATS 2024; Corrected typos

💡 一句话要点

提出ACHQ算法以高效路由异构排队系统中的作业

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 异构排队系统 强化学习 作业调度 策略梯度 低维参数化

📋 核心要点

  1. 核心问题：现有的强化学习方法在处理具有指数级状态空间的异构排队系统时效率低下，难以找到最优策略。
  2. 方法要点：提出ACHQ算法，通过低维软阈值策略参数化，利用排队结构来提高策略学习的效率。
  3. 实验或效果：仿真结果表明，ACHQ算法在期望响应时间上比贪婪策略提高了约30%。

📝 摘要（中文）

本文考虑了将到达中央队列的作业高效路由到异构服务器系统的问题。与同质系统不同，当队列长度超过某一阈值时，阈值策略被认为是最优的。然而，对于多服务器系统的最优策略仍然未知且难以找到。尽管强化学习在学习此类策略方面具有巨大潜力，但由于状态空间呈指数级增长，标准强化学习方法效率低下。为此，本文提出了ACHQ，一种基于低维软阈值策略参数化的高效策略梯度算法，利用了底层排队结构。我们为一般情况提供了平稳点收敛保证，并证明在两台服务器的特例中ACHQ收敛到近似全局最优解。仿真结果显示，与贪婪策略相比，期望响应时间提高了约30%。

🔬 方法详解

问题定义：本文旨在解决异构排队系统中作业路由的高效性问题。现有方法在面对状态空间指数级增长时，难以找到有效的最优策略，导致效率低下。

核心思路：论文提出的ACHQ算法通过低维软阈值策略参数化，旨在利用排队系统的结构特性来简化策略学习过程，从而提高效率。

技术框架：ACHQ算法的整体架构包括状态空间的简化、策略梯度的计算和收敛性分析等主要模块。算法通过对状态空间的低维映射，减少了计算复杂度。

关键创新：ACHQ算法的核心创新在于其低维软阈值策略参数化设计，使得在多服务器环境中能够有效收敛到近似全局最优解，这与传统的强化学习方法有本质区别。

关键设计：在参数设置上，ACHQ采用了低维参数化形式，损失函数设计为策略梯度形式，确保了收敛性和效率。此外，网络结构经过优化，以适应异构服务器的特性。

📊 实验亮点

实验结果显示，ACHQ算法在期望响应时间上比贪婪策略提高了约30%，证明了其在异构排队系统中的有效性和优越性。这一提升为实际应用中的作业调度提供了新的思路。

🎯 应用场景

该研究的潜在应用领域包括云计算、数据中心和制造业等需要高效作业调度的场景。通过优化作业路由策略，可以显著提高系统的响应速度和资源利用率，具有重要的实际价值和未来影响。

📄 摘要（原文）

We consider the problem of efficiently routing jobs that arrive into a central queue to a system of heterogeneous servers. Unlike homogeneous systems, a threshold policy, that routes jobs to the slow server(s) when the queue length exceeds a certain threshold, is known to be optimal for the one-fast-one-slow two-server system. But an optimal policy for the multi-server system is unknown and non-trivial to find. While Reinforcement Learning (RL) has been recognized to have great potential for learning policies in such cases, our problem has an exponentially large state space size, rendering standard RL inefficient. In this work, we propose ACHQ, an efficient policy gradient based algorithm with a low dimensional soft threshold policy parameterization that leverages the underlying queueing structure. We provide stationary-point convergence guarantees for the general case and despite the low-dimensional parameterization prove that ACHQ converges to an approximate global optimum for the special case of two servers. Simulations demonstrate an improvement in expected response time of up to ~30% over the greedy policy that routes to the fastest available server.