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.

我们提出了一种基于低维度软阈值策略参数化的高效策略梯度算法 ACHQ，利用底层排队结构，针对中心队列向异构服务器系统中任务迅速路由的问题。我们为一般情况提供了静态点收敛保证，并且尽管参数化维度较低，但证明了 ACHQ 对于两个服务器的特殊情况收敛于近似全局最优解。模拟结果表明，与贪婪策略相比，ACHQ 在预期响应时间上提高了约 30%。