aiqbench analysis
This research addresses the challenge of routing customers in heterogeneous load-balancing systems where service rates are initially unknown to the dispatcher. The authors propose an online learning algorithm that simultaneously estimates these rates and converges to the Shortest-Expected-Delay policy, achieving finite regret rather than the logarithmic growth typical of classical bandit problems. By balancing empirical routing with forced exploration phases, the method ensures sufficient sampling across servers, offering a theoretical advance for dynamic resource allocation in AI-driven infrastructure.
Learning Adaptive SED for heterogeneous load balancing
arXiv:2609.06881v1 Announce Type: new 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.
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.
Machine Learning (cs.LG); Probability (math.PR)
arXiv:2609.06881 [cs.LG]
(or arXiv:2609.06881v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2609.06881 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 238 words
Related coverage
Scalable Heterogeneous Graph Foundation Models for Data-Driven Optimal Power Flow in Smart Grids
arXiv · Sep 30, 2026
STHMoE: Hypergraph-Enhanced Heterogeneous Dependency Coordination for LLM-Based Urban Traffic Data Forecasting
arXiv · Sep 16, 2026
DEALS: Decentralized Expertise-Aware Load Serving for Multi-Agent LLM Systems
arXiv · Sep 30, 2026
From fragmented data to actionable design: Physics-calibrated learning for plastic upcycling
arXiv · Aug 5, 2026