Skip to content

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

Oct 2026 · 0 citations
Computer Science

TL;DR

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.

View source

Similar papers

Nonpreemptive Scheduling While Learning Context-Dependent Service Rates

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.

Wan-Kyu Choi, Seoungbin Bae, Dabeen Lee · 0 citations
Preprint Nov 2026

A Parameter-Free Best-of-Both-Worlds Policy for Queueing Bandits

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...

Jongyeong Lee, Chansoo Kim · 0 citations
Open access Nov 2026

Prediction-Driven Non-Preemptive Scheduling with Bounded Overtaking: A Per-Job Wait Guarantee

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. · 0 citations
Preprint Nov 2026

Retrials in Loss Systems: Mean-Field Analysis, Erlang Bounds, and Power-of-$d$ Comparison

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
#edge computing Preprint Nov 2026

Minimizing Bottleneck Overload Risk in Online Edge Task Placement under Workload Uncertainty

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 Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

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.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.