This paper proposes WISE (Widest Interval Selection with Elimination), achieving rate-optimal queue length regret at every sufficiently large time without knowing the horizon, and proves another lower bound that quantifies the increase in regret as the normalized capacity slack decreases.
Abstract
We study contextual queueing bandits, where a learner schedules jobs while learning unknown service rates modeled by logistic functions of job-server features. Performance is measured by queue length regret, the expected excess queue length at round $t$ relative to an oracle that knows the service rates. Existing decaying-regret guarantees either have a suboptimal decay rate or require a known fixed horizon. They also assume context-wise slack and a strictly positive minimum eigenvalue of the feature covariance. In this paper, we propose WISE (Widest Interval Selection with Elimination), achieving rate-optimal $\widetilde{\mathcal O}(t^{-1/2})$ queue length regret at every sufficiently large time without knowing the horizon. We assume capacity slack, meaning that expected incoming workload under best-server service is below service capacity, and impose no covariance lower bound. Our analysis uses a workload potential measuring the expected service attempts needed by waiting jobs on their best servers. Its drift on nonempty rounds combines a negative term ensured by capacity slack with errors from suboptimal service choices. Then an elliptical potential count bounds how often WISE selects wide confidence intervals, thereby limiting the number of rounds with large service errors. We also sharpen the arrival-rate dependence of an existing lower bound and make its dependence on feature dimension and server count explicit. We prove another lower bound that quantifies the increase in regret as the normalized capacity slack decreases; to our knowledge, this is the first such lower bound for CQB. Simulations show small regret even when context-wise slack fails.
Learn--Clear--Plan (LCP), which estimates the system and uses the resulting Bellman recursion to make horizon-dependent decisions, and suggests an estimated-SEPT algorithm that achieves a tracking error of $\widetilde{O}(\sqrt{d/t})$ without knowing the model.
We study online channel scheduling for a single queue served by $K$ channels under bandit feedback. We propose a simple best-of-both-worlds policy that explores when the queue is empty. During busy periods, it selects the empirical best channel while the prescribed conditions hold and, if any condition is violated, swi...
It is proved that any no-regret learner achieves a long-run average throughput of at least the Hamacher sum of the server rates, and that this bound is tight.
Before a programming deadline, many students’ programs queue for a few grading servers. Ordering them by predicted running time cuts the mean wait, but known bounds with predictions hold on average or against an optimum, not per job. We prove an identity for k non-preemptive, work-conserving servers with time limit L....
Ya-Zhou Guo, Ze-Xin Lin, Cheng-Yang Huo et al.· Mathematics· 0 citations
We consider a system of $N$ parallel, homogeneous servers, each with finite capacity $C$. Jobs requiring one unit of capacity arrive according to a Poisson process with total rate $N\lambda$ and have exponential service times with rate $\mu$. We study a decentralized random--retrial policy with $d$ attempts: upon arriv...
D. Cuesta, M. Jonckheere, B. Prabhu et al.· 0 citations
RBP places tasks in descending order of standard deviation, each on the server with the smallest post-assignment risk ratio, and refines the assignment with relocations and swaps within a finite per-period online budget, and minimize the largest risk ratio, attained at the risk bottleneck.
Lei Wang, W. Seah, Gang Xu et al.· 0 citations
Related blog posts
MIT News · Artificial Intelligence· news.mit.eduNov 17, 2026
By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.
Microsoft Research Blog· microsoft.comNov 16, 2026
AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.
MIT News · Artificial Intelligence· news.mit.eduNov 13, 2026