PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Adaptive SED for heterogeneous load balancing

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

arXiv:2609.06881v1cs.LGmath.PR

TL;DR

The paper considers routing arrivals to two heterogeneous servers when their service rates are unknown and SED therefore cannot be implemented directly. It proposes LASED, which learns the rates while routing with forced exploration and episodic updates, and proves asymptotically bounded regret.

  • Problem

    In a two-server system with unknown service rates, the dispatcher needs to route arrivals according to SED without knowing the rates required by its decision rule.

    Source: §1 · p. 1

  • Method

    LASED learns service rates while routing, using forced exploration and episodic updates alongside empirical SED routing.

    Source: §1 · p. 2, §8 · p. 16

  • Results

    LASED achieves asymptotically bounded regret while learning SED routing.

    Source: §1 · p. 2, §8 · p. 16

  • Takeaways & Limitations

    In queueing systems with sensitive, state-dependent decision boundaries, balancing exploration and exploitation while routing can stop regret from growing.

    Source: §8 · p. 16

    Extending the regret analysis beyond two servers is left for future work because the learning difficulty scales with dimension.

    Source: §3.4 · p. 7

Abstract

from arXiv · show

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.

1 Introduction

The paper studies routing in a two-server system when service rates are unknown, so the dispatcher cannot directly implement SED. It motivates LASED as an online learning policy with bounded regret, using forced exploration and episodic updates.

1 Introduction

  • With unknown service rates, the dispatcher must minimize delays while learning the parameters needed to implement SED.The paper measures regret as the cumulative number of decisions that differ from SED.Source: §1 · p. 1
  • SED routes each arrival to the server with the smallest expected delay, using service rates in its decision rule.In the two-server system, the boundary between routing choices depends on the rate ratio r∗ = µ2/µ1.Source: §1 · p. 1
  • Even a small estimation error can make empirical SED disagree with SED across infinitely many states, producing linear regret.The paper's numerical example reports linear regret growth with only a 1% routing error, with faster growth at higher system load.Source: §1 · pp. 1–2

1.1 Contributions

  • LASED learns unknown service rates while routing, and its regret is asymptotically bounded, implying convergence to SED.Its analysis decomposes regret into exploration errors, estimation errors, and overflow events.Source: §1 · p. 2, §1.1 · p. 3

1 Introduction

  • LASED uses episodes that begin and end when the system is empty, with optional exploration followed by empirical SED routing.Estimators are updated between episodes; this structure avoids changing routing after every departure and makes departures between episodes independent.Source: §1 · p. 2
  • The paper bounds disagreement risk using concentration inequalities and drift analysis under λ < µ1 + µ2.The analysis shows agreement between LASED and SED in a growing region, while bounding the probability that queue lengths leave it.Source: §1 · pp. 2–3

2 System description

The system has two heterogeneous queues and routes each arrival immediately; SED(r) uses a rate-ratio parameter to choose a server. The section characterizes how parameter error changes routing decisions.

2.1 Load balancing between two queues

  • Arrivals follow a Poisson process, service times are independent exponential variables, and each server has an infinite-capacity queue with no jockeying.Service rates µ1 and µ2 are positive, and customers are routed immediately upon arrival.Source: §2.1 · p. 3

2.2 Routing using SED policies

  • SED(r) compares delay estimates r(q1 + 1) and q2 + 1, routing to a server attaining the minimum; SED corresponds to r = µ2/µ1.Ties are broken toward server 1 in the stated definition.Source: §2.2 · p. 3
  • SED(r) and SED(ˆr) disagree only for states between their decision boundaries, and closer parameters yield a smaller disagreement region.The boundary separation measure ur(m) decreases to zero as m grows.Source: §2.2 · p. 4
  • For r, ˆr ∈ R>0, if |r − ˆr| < ur(m), then for every q ∈ {0, …, m}², DSED(ˆr)(q) ∈ DSED(r)(q) (Lemma 1).Source: §2.2 · p. 4

3 Learning Adaptive SED

LASED learns unknown service rates through episodic exploration and empirical SED routing, and Theorem 1 establishes asymptotically bounded regret under stated conditions. The analysis relates routing mismatches to exploration, estimation error, and queue overflow, while discussing limits to irrational rate ratios and systems with more than two servers.

3.1 Algorithm description

  • Episodes begin and end with an empty system, and combine optional exploration for sufficient samples with exploitation using empirical SED routing.Estimators are updated between episodes using observed service completions.Source: §3.1 · p. 4

3.2 Regret definition

  • Regret counts cumulative routing decisions that differ from SED(r), measuring how quickly LASED learns the target routing behavior.Source: §3.2 · p. 4

3.3 Regret upper bound

  • Theorem 1 establishes asymptotically bounded regret for LASED with respect to SED.The theorem is stated under conditions on service rates and arrival rate.Source: §3.3 · p. 5
  • Regret can arise from exploration, ratio misestimation, or queue overflow; without these events, LASED agrees with SED within the safety region.The safety region is where the queue lengths stay below m(k).Source: §3.3 · pp. 5–6
  • The sequence m(k) balances estimation accuracy against making queue excursions outside the safety region sufficiently rare.Source: §3.3 · p. 6

3.4 Discussion

  • The guarantee assumes positive recurrence, a suitable exploration schedule, bounded service rates, and rational service rates.The bounded interval keeps rates away from zero and infinity; rationality supplies a positive separation from other fractions with bounded denominator.Source: §3.4 · p. 6
  • For irrational rate ratios, the proof argument breaks down because rationals can approximate them arbitrarily closely, so a regret bound needs another approach.Source: §3.4 · p. 6
  • With n servers, one service-rate estimation error affects n −1 decision hyperplanes, and extending the regret analysis is left for future work.The three-server case has three pairwise boundaries and a union of disagreement wedges.Source: §3.4 · p. 7

4 The SED(r) policy

The section establishes stability of SED(r) for every positive ratio under condition (7), then develops hitting-probability, busy-period tail, and hitting-time bounds. These analyses support the stability and busy-period properties used later in the paper.

4 The SED(r) policy

  • Condition (7) is sufficient for SED(r) stability for every r > 0, established with a Lyapunov function and negative drift outside a finite region.The direct Foster–Lyapunov analysis also supports bounds on return times, stationary-distribution moments, first-entrance probabilities, busy-period moments, and maximum queue length.Source: §4 · pp. 7–8

4.1 Hitting probability analysis

  • The hitting-probability analysis uses a supermartingale and optional stopping to bound the chance of reaching a large-queue region before returning to C_r.The stopped-process argument applies under condition (7).Source: §4.1 · pp. 8–9

4.2 Tail bound for the maximum queue length in a busy period

  • A gambler’s-ruin-style argument across C_r, B_r, and M_m bounds the probability that a busy period exceeds queue length m.The argument combines a nonzero chance of emptying before entering B_r with a bound on the boundary potential over B_r.Source: §4.2 · p. 9

4.3 Moment bounds for hitting times

  • Lemma 7 bounds the first and second moments of the time to hit the origin or B_r when starting in C_r.Lemma 8 then uses the Lemma 7 tail bound to bound the first and second moments of the return time to the origin.Source: §4.3 · p. 10

5 Proof of bounded regret

The proof bounds regret by controlling exploration, estimation errors, overflow, and episode arrival counts. It combines these bounds to complete the proof of Theorem 1.

5.1 Bounding the misestimation probability

  • For sufficiently large k, the misestimation probability decreases sufficiently fast, with Lemma 10’s bound stated to be o(k^-p) for every p > 0.The concentration inequality bounds deviations of the estimated ratio when at least m departures have been observed.Source: §5.1 · p. 11

5.2 Bounding the exploration probability

  • The probability that episode k starts with exploration decreases because departures grow linearly with high probability while the exploration threshold grows logarithmically.Regenerative episodes let the analysis condition on the history and use a uniform lower bound on observing departures from both servers when the estimate is sufficiently concentrated.Source: §5.2 · p. 11

5.3 Bounding the overflow probability

  • Overflow without exploration is analyzed as a busy period under SED(r), allowing the proof to use the busy-period bound from Lemma 6.Lemma 16 bounds the conditional overflow probability.Source: §5.3 · p. 12

5.4 Bounding the expected arrivals

  • Expected arrivals per episode are bounded by treating exploitation-only episodes as busy periods and bounding exploration arrivals by a construction-dependent constant.The resulting arrival-count bounds are combined with the regret decomposition.Source: §5.4 · p. 12

5 Proof of bounded regret

  • The regret decomposition tracks forced exploration, estimator errors, and queue overflow, then combines event-probability and arrival-count bounds to complete Theorem 1.Estimation errors are controlled with concentration inequalities, while overflow is analyzed using a Foster–Lyapunov approach.Source: §5.4 · p. 12

6 Related work

Prior work studies heterogeneous-server routing, SED analysis, and learning with unknown parameters. The paper distinguishes its state-dependent SED benchmark and sample-path regret from a closely related bandit-based model.

6 Related work

  • Heterogeneous load balancing lacks a known delay-optimal policy based only on instantaneous queue lengths in general, and SED is among several studied heuristic policies.Existing SED analysis remains partial, with results including two-server stationary-distribution representations and bounds on mean response time.Source: §6 · p. 12
  • Much prior heterogeneous-server work focuses on asymptotic regimes, while learning studies include bandit-inspired, policy-gradient, UCB-guided MaxWeight, and marginal-service-rate approaches.The paper’s episodic use of busy periods draws on regenerative learning approaches in queueing systems and admission control.Source: §6 · pp. 12–13
  • In the closest unknown-rate model, studies unobservable queues and static weighted random routing, whereas this paper uses state-dependent SED as its oracle and defines regret statewise.The prior work proves a regret upper bound but not a constant-regret guarantee; this paper analyzes regret at the sample-path level because SED’s stationary distribution is unknown.Source: §6 · p. 13

7 Numerical experiments

The experiments compare fixed-estimate ESED, episodic LASED, and a greedy policy across loads and initialization regimes. They show that learning and forced exploration help in some settings, but exploitation can suffice when both servers are sampled.

7.1 Empirical methods versus learning

  • Fixed-estimate ESED accumulates linear regret even with small estimation error, while LASED’s regret grows more slowly and converges to a constant at low loads.For LASED, convergence takes longer at high loads as its changing disagreement region is visited less frequently over time.Source: §7.1 · p. 13

7.2 When exploitation suffices

  • At loads ρ ∈{0.3, 0.6}, LASED’s regret converges to a finite limit, but at ρ = 0.9 convergence takes longer because long busy periods and large queues delay learning.Greedy accumulates less regret and has a comparable or lower customer count in this setup; its estimates converge faster because it updates after every service completion.Source: §7.2 · p. 14

7.3 When exploration is beneficial

  • With poor initialization (ˆr1 = 0.02 versus r∗= 2), Greedy leaves the actually faster second server underused and accumulates linear regret over the simulated horizon, while LASED explores both servers and quickly converges to SED.The setup uses λ = 1, µ1 = 5, µ2 = 10, and initial estimates ˆµ1 = 5 and ˆµ2 = 0.1.Source: §7.3 · p. 14

7.4 The exploration–exploitation trade-off

  • For homogeneous servers at low load with large initial estimation error, LASED has lower regret than Greedy because it samples both servers earlier.The cited cases are r = 1, ρ = 0.1, and ˆr1 = 0.1 or 10.Source: §7.4 · p. 15
  • For a large service-rate imbalance, LASED suffers at low load because short episodes trigger exploration often, while Greedy’s routing is robust to poor estimates.LASED improves as load increases because exploration is triggered less often.Source: §7.4 · p. 15
  • For homogeneous servers at high load with non-zero initial error, LASED suffers because busy periods delay its between-episode estimator updates, while Greedy adapts after each completion.The regret difference is not monotone in initial estimation error, and its effect also depends on load and the true service-rate ratio.Source: §7.4 · p. 15
  • Exploration is beneficial when Greedy fails to obtain enough observations, as when it incorrectly starves one server; with continuous samples from both servers, exploitation alone suffices.In the latter case, Greedy’s empirical estimates converge and it quickly approaches SED with little accumulated regret.Source: §7.4 · p. 15

8 Conclusion

The conclusion argues that inaccurate service-rate estimates can create a suboptimal decision region large enough to produce linear regret. LASED combines forced exploration with episodic updates and is proved to achieve asymptotically bounded regret.

8 Conclusion

  • Small service-rate errors can create a large suboptimal decision region, which causes linear regret accumulation.The conclusion contrasts offline fixed estimates and online adjustment, neither of which works for all arrival and service rates.Source: §8 · p. 15
  • LASED learns service rates while applying SED, using forced exploration and episodic updates to ensure finite regret.Its analysis decomposes regret into exploration errors, estimation errors, and overflow events.Source: §8 · p. 16
  • The paper concludes that balancing exploration and exploitation in queues can stop regret from growing when decisions depend on sensitive, state-dependent boundaries.The conclusion frames this as a queueing-specific challenge rather than a standard learning setting.Source: §8 · p. 16

A.1 Proof of Theorem 1

The proof bounds several contributions to regret and combines those bounds to show convergence of the resulting sum. Its argument separately treats exploration, misestimation, overflow, and arrivals.

A.1 Proof of Theorem 1

  • The proof treats exploration, misestimation, and overflow as separate contributions, invoking lemmas to bound each term.The supplied proof passages identify these as distinct parts of the bound.Source: §A.1 · p. 19
  • For the arrivals term, the estimator and the stated bounds βr(7, 7) and γr(7, 7) lie in the interval [rmin, rmax], enabling an application of Lemma 17.The associated constant is stated to depend on system and algorithm parameters.Source: §A.1 · p. 19
  • The proof combines bounds for the terms in (14), bounding probabilities by 1 for the first k∗−1 episodes before applying the bounds valid for k ≥ k∗.The cited text states that the resulting sum in (50) converges as n →∞ when c1 > 2/θ∗.Source: §A.1 · p. 20

A.2 Proof of Lemma 2

The proof partitions the state space into two regions around the SED decision boundary and bounds the generator expression in each. It then invokes earlier inequalities to obtain the stated result.

A.2 Proof of Lemma 2

  • The proof partitions the state space into two regions and analyzes them separately.Region I satisfies q2 + 1 ≥ r(q1 + 1); Region II satisfies q2 < r(q1 + 1) − 1.Source: §A.2 · p. 20
  • In Region I, the proof uses the state inequality to bound (Lrϕr)(q) and then substitutes a bound involving δ1.The displayed inequalities compare the generator expression with terms involving queue lengths, rates, and arrival rate.Source: §A.2 · p. 20
  • The proof combines inequalities (63) and (67) to obtain the result, using elementary square inequalities for nonnegative variables and integer queue lengths.The passage explicitly invokes x2 + y2 and x2 ≥ x(x+1)/2 for x ∈N≥0.Source: §A.2 · p. 20

A.3 A version of Dynkin’s formula

The proof handles nonnegative f by applying Dynkin’s formula to bounded truncations f_n(x) = f(x) ∧ n, then passing to the limit. Monotone and dominated convergence justify the limiting terms.

A.3 A version of Dynkin’s formula

  • Applying Dynkin’s formula to f_n(x) = f(x) ∧ n makes the function bounded before the proof takes limits.The process is strong Markov, and its transition rates are uniformly bounded.Source: §A.3 · p. 21
  • Monotone convergence gives the limit of the expected stopped-function term because f_n increases pointwise to f.The truncations are nonnegative.Source: §A.3 · p. 21
  • Dominated convergence handles the generator term after pointwise convergence and an integrable bound are established.Finite rate sums support pointwise convergence, while the truncation inequality and assumption (68) provide integrability.Source: §A.3 · p. 21

A.4 Proof of Lemma 3

These appendix proofs establish bounds on hitting times, stopping probabilities, concentration, deviations, and exploration-episode lengths using drift, martingale, and strong-Markov arguments. Together, they provide uniform control of estimation errors and episode lengths under the stated conditions.

A.4 Proof of Lemma 3

  • Lemma 3 bounds the first and second moments of a hitting time using a Lyapunov function, drift conditions, and strong-Markov and integration arguments.For the second moment, the proof verifies the needed integrability condition despite unbounded one-step increments, using bounded jump rates and bounded expected queue sizes over finite intervals.Source: §A.4 · p. 22

A.5 Proof of Lemma 4

  • Lemma 4 establishes a supermartingale bound by combining negative drift before hitting C_r with uniformly bounded increments of the square-root Lyapunov function.The proof uses the total jump-rate bound λ + μ1 + μ2 to control the discretized process.Source: §A.5 · p. 23

A.6 Proof of Lemma 5

  • Lemma 5 applies optional stopping to the bounded stopped supermartingale W^(n∧T), with boundedness following from the process's entry into M through a boundary state.The proof first bounds the contribution when the stopped state lies in M, then applies Doob’s optional stopping theorem.Source: §A.6 · p. 24

A.7 Proof of Lemma 6

  • Lemma 6 uses the strong Markov property at the first hit of B to relate the probability of reaching zero before M to corresponding probabilities from boundary and interior states.The proof combines lower bounds for the two relevant infima, including a bound p for reaching zero before B from states in C.Source: §A.7 · pp. 24–25

A.8 Proof of Lemma 7

  • Lemma 7 lower-bounds the chance of reaching zero or the boundary within a time interval by requiring no arrivals and enough departures, then uses repeated attempts to bound hitting-time moments.With no arrivals, the departure rate remains at least μ1 ∧ μ2 while customers remain; after failed attempts, the process returns to C_r before trying again.Source: §A.8 · pp. 25, 27
  • For Lemma 7, each attempt has success probability at least p_r, yielding a geometric tail and bounds on the first and second moments uniformly over starting states y in C_r.The proof takes the maximum over y in C_r to obtain bounds (33) and (34).Source: §A.8 · p. 28

A.10 Proof of Lemma 10

  • For Lemma 10, the proof assumes r*=a/b in lowest terms and k≥exp(1/c1) before completing its bound.It uses the definition of m(k) and properties of N(k) in the derivation.Source: §A.10 · pp. 28–29

A.11 Proof of Lemma 12

  • Lemma 12 derives concentration bounds for empirical service-rate estimates and their ratio using exponential martingales and Ville’s inequality.The proof combines separate bounds for the relevant count deviations before concluding the ratio bound.Source: §A.11 · pp. 29–30

A.12 Proof of Lemma 13

  • Lemma 13 combines estimator concentration with an Azuma–Hoeffding bound on a martingale difference sequence to control the deviation under its stated condition.The proof concludes by combining the intermediate bounds (171), (173), (175), (180), and (185).Source: §A.12 · pp. 30–31

A.13 Proof of Lemma 14

  • Lemma 14 analyzes busy-period queue-reach probabilities conditional on an estimate close to the true rate and a sufficient sample count to establish its bound.When LASED uses SED with the estimated rate and no exploration phase, the episode is one busy period.Source: §A.13 · p. 31

A.15 Proof of Lemma 16

  • For Lemma 16, exploration adds at most 14 arrivals and leaves at most seven customers per queue; optional-stopping and monotonicity arguments yield the first- and second-moment bounds (38)–(39).The proof applies optional stopping to the Poisson arrival process and then uses Lemma 8 to obtain the stated bounds.Source: §A.15 · pp. 33–34
Loading 2609.06881v1…