Learning Adaptive SED for heterogeneous load balancing

Sanne van Kempen; Jaron Sanders; Fiona Sloothaak; Maarten G. Wolf

cs.LGSep 7, 2026

Learning Adaptive SED for heterogeneous load balancing

Authors: Sanne van Kempen, Jaron Sanders, Fiona Sloothaak, Maarten G. Wolf

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.

Figures & tables

Panel of Figure 1 — Figure 1: A load balancing system with two heterogeneous servers and the SED routing policy.

\displaystyle N_{i}^{(k+1)}

\displaystyle=N_{i}^{(k)}+Z_{i}^{(k)},\qquad S_{i}^{(k+1)}=S_{i}^{(k)}+\sum_{j=1}^{Z_{i}^{(k)}}Y_{i,j}^{(k)},\qquad\hat{\mu}_{i}^{(k+1)}=\frac{N_{i}^{(k+1)}}{S_{i}^{(k+1)}}.

(4)

Algorithm 1 Learning Adaptive SED (LASED)

Panel of Figure 2 — Figure 2: Three pairwise decision boundaries in the three-dimensional case (left). An error in the service rate estimator $\hat{\mu}_{2}$ simultaneously shifts the two boundaries involving that server (right).

Figure 3: Geometry of the sets

\mathscr{C}_{r}

\mathscr{B}_{r}

, and

\mathscr{M}_{m}

in the plane

\mathbb{N}_{\geq 0}^{2}

for

\lambda=5

\mu_{1}=3

\mu_{2}=4

r=1/4

, and

m=35

. In this case, the line

q_{2}=\kappa_{r}-q_{1}

intersects the

q_{2}

-axis at

q_{2}=7

and the

q_{1}

-axis at

q_{1}=28

Panel of Figure 4 — Figure 4: Disagreement wedge and accumulated regret over time of ESED and LASED in a two-server system for different traffic intensities. The true service rates are $\mu_{1}=0.75$ and $\mu_{2}=0.91$ , while the empirical estimators are initialized at $\hat{\mu}_{1}=0.74$ and $\hat{\mu}_{2}=0.92$ .

Panel of Figure 5 — Figure 5: Performance of LASED and a Greedy policy in a two-server system for different traffic intensities. The true service rates are $\mu_{1}=\mu_{2}=1$ , while the empirical estimators are initialized at $\hat{\mu}_{1}=1$ and $\hat{\mu}_{2}=10$ .

Figure 8: Difference in expected regret between the LASED and Greedy policies. Each cell is based on 50 independent simulations of both policies. Each simulation runs for the duration of $10^{4}$ expected arrivals, hence the value in each cell is in $[-10^{4},10^{4}]$ .

Queueing Theory

See all 18 papers

Nonpreemptive Scheduling While Learning Context-Dependent Service Rates
Sep 29, 2026Wansoo Choi, Seoungbin Bae, Dabeen LeeQueueing Theory Contextual Bandits
Department of Mathematical Sciences, Seoul National University · Department of Industrial & Systems Engineering, KAIST
Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays
Jul 30, 2026Tianhang Lu, Runtian Ren, Shengcai Liu +1Competitive Analysis Learning-Augmented Algorithms
Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China
Learning While Scheduling Jobs under Context-Dependent Service Rates: An Anytime Rate-Optimal Algorithm
Oct 5, 2026Seoungbin Bae, Dabeen LeeMulti-Armed Bandits Contextual Bandits
Department of Industrial & Systems Engineering, KAIST · Department of Mathematical Sciences, Seoul National University

Sep 29, 2026J/K move · Enter open · S save

Nonpreemptive Scheduling While Learning Context-Dependent Service Rates

Wansoo Choi, Seoungbin Bae, Dabeen Lee

Department of Mathematical Sciences, Seoul National University · Department of Industrial & Systems Engineering, KAIST

Queueing Theory Contextual Bandits Real-Time Scheduling

Open paper AskPDF arXiv

We study nonpreemptive contextual queueing bandits in a single-server system. Each job is represented by a

d

-dimensional context vector; in each round, a job may arrive with its context drawn from an unknown distribution

\mathcal{D}

, and its departure probability is determined by a logistic model of that context vector with an unknown parameter

θ^*

. The server learns from service outcomes while deciding which waiting job to serve and whether to idle, aiming to minimize queue-length regret, the gap between its expected terminal queue length and the minimum achievable by an admissible policy. Once selected, a job must be served until completion, and we refer to this as the nonpreemptive setting. A central challenge is that, even with full model knowledge, the optimal policy cannot in general be characterized by a simple myopic rule, since the optimal action can change with the remaining horizon at the same queue state. Nevertheless, when the model and horizon are known, the optimal action can be obtained through a finite-horizon Bellman recursion. Motivated by this, we propose Learn--Clear--Plan (LCP), which estimates the system and uses the resulting Bellman recursion to make horizon-dependent decisions. LCP achieves

\widetilde{O}(\sqrt{d/T})

queue-length regret, while a lower-bound construction gives

Ω(\min\{1/\sqrt{d},\sqrt{d/T}\})

regret for every learning policy on some instance, establishing optimality up to polylogarithmic factors when

T\ge d^2

. When the horizon is unknown, no horizon-independent policy achieves vanishing regret against the finite-horizon optimum. We therefore use SEPT, the policy that serves a waiting job with the highest probability of departure, as a fixed reference, and suggest an estimated-SEPT algorithm that achieves a tracking error of

\widetilde{O}(\sqrt{d/t})

without knowing the model.

Abstract

Queueing Theory

Explore similar work

Nonpreemptive Scheduling While Learning Context-Dependent Service Rates

Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays

Learning While Scheduling Jobs under Context-Dependent Service Rates: An Anytime Rate-Optimal Algorithm