Learning Adaptive SED for heterogeneous load balancing
Abstract
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.
Related
- Lexicographic Minimax Load Balancing for T-Adaptive Segment Routing
- PA-CFL: Privacy-Preserving Adaptive Clustered Federated Learning Under Heterogeneous Data
- Marking-based load balancing Weighted Clustering Framework for Mobile ADHOC Network
- Bi-Mamba-Load: A bidirectional structured state space model with sequence relationship adaptive perception for electricity load forecasting
- Combining Weather Forecast Aggregation and State-Space Models for Adaptive Probabilistic Electricity Load Forecasting
BibTeX
@misc{kempen2026learning,
title = {{Learning Adaptive SED for heterogeneous load balancing}},
author = {Sanne van Kempen and Jaron Sanders and Fiona Sloothaak and Maarten G. Wolf},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.06881},
eprint = {2609.06881},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.06881},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Learning Adaptive SED for heterogeneous load balancing
AU - Sanne van Kempen
AU - Jaron Sanders
AU - Fiona Sloothaak
AU - Maarten G. Wolf
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.06881
UR - https://arxiv.org/abs/2609.06881
AB - 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.
ER -