# Efficient Reinforcement Learning for Routing Jobs in Heterogeneous Queueing Systems

arXiv: https://arxiv.org/abs/2402.01147 · HTML: https://mlsanity.com/paper/2402.01147/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Placed in RL for energy, networks and operations, one of 15 directions in Deep reinforcement learning methods.
- Builds on 10 of its 50 references that are in the map.
- First posted on arXiv 2 Feb 2024.

## Placed in

- Deep reinforcement learning methods / [RL for energy, networks and operations](https://mlsanity.com/deeprl/rl-for-energy-networks-and-operations/)

## Builds on (most cited first, 10 of 10)

- [Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer](https://mlsanity.com/paper/1701.06538/) (2017)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Global Optimality Guarantees For Policy Gradient Methods](https://mlsanity.com/paper/1906.01786/) (2019)
- [Learning Scheduling Algorithms for Data Processing Clusters](https://mlsanity.com/paper/1810.01963/) (2018)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/1910.08412/) (2019)
- [Queueing Network Controls via Deep Reinforcement Learning](https://mlsanity.com/paper/2008.01644/) (2020)
- [RL-QN: A Reinforcement Learning Framework for Optimal Control of Queueing Systems](https://mlsanity.com/paper/2011.07401/) (2020)
- [Learning and Information in Stochastic Networks and Queues](https://mlsanity.com/paper/2105.08769/) (2021)
- [Flexible Queueing Architectures](https://mlsanity.com/paper/1505.07648/) (2015)

## Built on by (most cited first, 7 of 7)

- [Queue Length Regret Bounds for Contextual Queueing Bandits](https://mlsanity.com/paper/2601.19300/) (2026)
- [Predictive Control and Regret Analysis of Non-Stationary MDP with Look-ahead Information](https://mlsanity.com/paper/2409.08434/) (2024)
- [Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret](https://mlsanity.com/paper/2606.09668/) (2026)
- [Natural Policy Gradient for Average Reward Non-Stationary RL](https://mlsanity.com/paper/2504.16415/) (2025)
- [Heterogeneous Vertiport Selection Optimization for On-Demand Air Taxi Services: A Deep Reinforcement Learning Approach](https://mlsanity.com/paper/2601.21316/) (2026)
- [Multi-Robot Multi-Queue Control via Exhaustive Assignment Actor-Critic Learning](https://mlsanity.com/paper/2604.03605/) (2026)
- [Learning Adaptive SED for heterogeneous load balancing](https://mlsanity.com/paper/2609.06881/) (2026)

## Abstract (arXiv)

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.