# Learning Adaptive SED for heterogeneous load balancing

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 56 references that are in the map.
- First posted on arXiv 7 Sep 2026.

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

- [Queueing Network Controls via Deep Reinforcement Learning](https://mlsanity.com/paper/2008.01644/) (2020)
- [Learning Unknown Service Rates in Queues: A Multi-Armed Bandit Approach](https://mlsanity.com/paper/1604.06377/) (2016)
- [Job Dispatching Policies for Queueing Systems with Unknown Service Rates](https://mlsanity.com/paper/2106.04707/) (2021)
- [Learning While Scheduling in Multi-Server Systems with Unknown Statistics: MaxWeight with Discounted UCB](https://mlsanity.com/paper/2209.01126/) (2022)
- [Efficient Reinforcement Learning for Routing Jobs in Heterogeneous Queueing Systems](https://mlsanity.com/paper/2402.01147/) (2024)
- [Learning-based Optimal Admission Control in a Single Server Queuing System](https://mlsanity.com/paper/2212.11316/) (2022)
- [Distributed Load Balancing with Workload-Dependent Service Rates](https://mlsanity.com/paper/2411.17103/) (2024)
- [Learning payoffs while routing in skill-based queues](https://mlsanity.com/paper/2412.10168/) (2024)

## Abstract (arXiv)

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.